akhauriyash/Code-Regression huggingface dataset:
# ABC138D - Ki (main, dfs, global variables) 1617ms
import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)


def dfs(v: int, p: int) -> None:
    for u in T[v]:
        if u != p:  # p: parent -> skip
            cnt[u] += cnt[v]  # cumulative sum
            dfs(u, v)


def main():
    # Ai (A[i][0]) may be not a parent of Bi (A[i][1])
    global T, cnt
    N, Q = tuple(map(int, input().split()))  # vertices and queues
    E = tuple(tuple(map(int, input().split())) for _ in range(N - 1))
    P = tuple(tuple(map(int, input().split())) for _ in range(Q))
    T = [[] for _ in range(N + 1)]  # tree, (N+1: 1-idx -> 0-idx)
    for a, b in E:
        T[a] += [b]
        T[b] += [a]
    cnt = [0] * (N + 1)
    for p, x in P:
        cnt[p] += x  # increase vertex p by x
    dfs(1, -1)
    print(*cnt[1:])


if __name__ == "__main__":
    main()

Measured memory_bytes: 265788
from itertools import combinations
N = int(input())
K = int(input())
s = []
n = N
while(N > 0):
    if N > 10:
        s.append(9)
    else:
        s.append(N-1)
    N = N // 10
ans = 0
for x in combinations(s, K):
    tmp = 1
    for i in range(K):
        tmp *= x[i]
    ans += tmp

if K == 1:
    print(ans + 1)
    exit(0)

for x in combinations(range(len(s)-1), K - 1):
    tmp = (10**(len(s)-1))*(s[-1]+1)
    for j in range(9, 0, -1):
        if K-1 == 2:
            for k in range(9, 0, -1):
                if tmp + ((10**x[1])*j) + ((10**x[0])*k) <= n:
                    ans += k
                    break

        elif K - 1 == 1:
            if tmp + ((10 ** x[0]) * j) <= n:
                ans += j
                break


print(ans)


Measured memory_bytes: 3188
#include<bits/stdc++.h>
#define PI 3.1415926535897932384626433832795
#define ll long long
#define MP make_pair
#define IN insert
#define PB push_back
#define fr first
#define se second
#define sf scanf
#define pf printf
#define debug(x) cout<<"---------"<<x<<endl;
#define LEN(a) sizeof(a)/sizeof(a[0])
#define MEM(arr,k) memset(arr,k,sizeof arr)
#define input freopen("input","r",stdin)
#define output freopen("output","w",stdout)


int X8[] = {0, 1, 0, -1, 1, -1, 1, -1};
int Y8[] = {1, 0, -1, 0, 1, -1, -1, 1};
int X4[]={+1,-1,+0,+0};
int Y4[]={+0,+0,+1,-1};

using namespace std;

int main()
{

		int n,a,b;
		cin>>n>>a>>b;
		cout<<min(n*a,b)<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
  int x, y;
  int cnt[12] = {0};

  cin >> x >> y;
  cnt[x-1]++; cnt[y-1]++;

  string ans = "Yes";

  if (cnt[1] != 0) {
    ans = "No";
  } else if (cnt[3] + cnt[5] + cnt[8] + cnt[10] == 1) {
    ans = "No";
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
using namespace std;

//===
template<uint_fast64_t p>
struct ModInt {
    using uint = uint_fast64_t;
    uint d;

    ModInt(const uint x = 0):d((x % p + p) % p) {};
    
    ModInt operator + (const ModInt x) const noexcept {
        if (d + x.d >= p) return ModInt(d + x.d - p);
        else return ModInt(d + x.d);
    };
    ModInt operator - (const ModInt x) const noexcept {
        if (d - x.d < 0) return ModInt(d - x.d + p);
        else return ModInt(d - x.d);
    };
    ModInt operator * (ModInt x) const noexcept {
        return ModInt(d * x.d);
    }
    ModInt operator / (ModInt x) const noexcept {
        ModInt inv(1);
        uint exp = p - 2;
        while (exp) {
            if (exp & 1) inv *= x;
            x *= x, exp >>= 1;
        }

        return ModInt(d * inv.d);
    }

    ModInt &operator += (const ModInt x) noexcept {return *this = *this + x;};
    ModInt &operator -= (const ModInt x) noexcept {return *this = *this - x;};
    ModInt &operator *= (const ModInt x) noexcept {return *this = *this * x;};
    ModInt &operator /= (const ModInt x) noexcept {return *this = *this / x;};
    void operator ++ () noexcept {*this = *this + 1;};
    void operator ++ (int) noexcept {*this = *this + 1;};
    void operator -- () noexcept {*this = *this - 1;};
    void operator -- (int) noexcept {*this = *this - 1;};

    bool operator == (const ModInt x) noexcept {return d == x.d;};
    bool operator != (const ModInt x) noexcept {return d != x.d;};

    ModInt operator + (const uint x) const noexcept {return *this + ModInt(x);};
    ModInt operator - (const uint x) const noexcept {return *this - ModInt(x);};
    ModInt operator * (const uint x) const noexcept {return *this * ModInt(x);};
    ModInt operator / (const uint x) const noexcept {return *this / ModInt(x);};
    
    ModInt operator += (const uint x) noexcept {return *this = *this + x;};
    ModInt operator -= (const uint x) noexcept {return *this = *this - x;};
    ModInt operator *= (const uint x) noexcept {return *this = *this * x;};
    ModInt operator /= (const uint x) noexcept {return *this = *this / x;};
};
template<uint_fast64_t p>
ostream &operator << (ostream &stream, const ModInt<p> &mi) {
    return stream << mi.d;
};
template<uint_fast64_t p>
istream &operator >> (istream &stream, ModInt<p> &mi) {
    uint_fast64_t a;
    stream >> a;
    mi = ModInt<p>(a);
    return stream;
};
//===

#define sum(X) ((X) * (X + 1) / 2)
using mint = ModInt<1'000'000'007>;
using ll = long long;

int main() {
    ll n, k;
    ll a[2005];
    mint ans;

    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
 
    for (int i = 0; i < n; i++) {
        mint cnt(0);
        for (int j = i + 1; j < n; j++) {
            if (a[i] > a[j]) {
                cnt++;
            }
        }
 
        mint cnt2(0);
        for (int j = 0; j < n; j++) {
            if (a[i] > a[j]) {
                cnt2++;
            }
        }
 
        ans += cnt * k;
        ans += cnt2 * sum(k - 1);
    }
 
    cout << ans << endl;
 
    return 0;
}


Measured memory_bytes: 256
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }

fun main(args: Array<String>) {
    val (a, b, c) = readInts()
    val (N) = readInts()

    val max = listOf(a, b, c).max()!!

    println((a + b + c + max * Math.pow(2.0, N.toDouble()) - max).toInt())
}

Measured memory_bytes: 35952
import sys
import math

lines = sys.stdin.readlines()
N = int(lines[0])
X = []

for i in range(N):
  Si = str(lines[i+1].split('\n')[0])
  X.append(Si)

X.sort()

z = 1
for i in range(N-1):
  if X[i] != X[i+1]:
    z +=1
print(z)


Measured memory_bytes: 38132
#include<stdio.h>

int main(){

    int X;
    int a,b; // 500円、50円の枚数

    scanf("%d", &X);

    a = X / 500;
    b = (X % 500) / 5;

    printf("%d\n", 1000*a + 5*b);

    return 0;
}


Measured memory_bytes: 128
#include <stdio.h>
int main(void){
    int A,B,K;
    int i=0,d=0;
    scanf("%d %d %d",&A,&B,&K);
    for(i=A;i<A+K;i++){
        if(i<=B)printf("%d\n",i);
    }
    for(i=B-K+1;i<=B;i++){
        if(A+K<=i)printf("%d\n",i);
    }
}


Measured memory_bytes: 128
#include <algorithm>
#include <iostream>
#include<cstdio>
#include<vector>
#include <functional>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;

bool cmp(pair<int,int> &a,pair<int,int> &b){
    return a.first > b.first;
}


int main() {

    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n;i++){
        cin >> v[i];
    }
    vector<pair<int,int>> cnt1(MAXN), cnt2(MAXN);
    for (int i = 0; i < n;i++){
        if(i%2)
            cnt2[v[i]].first++, cnt2[v[i]].second = v[i];
        else
            cnt1[v[i]].first++, cnt1[v[i]].second = v[i];
    }
    sort(cnt1.begin(), cnt1.end(), cmp);
    sort(cnt2.begin(), cnt2.end(), cmp);
    int ans = MAXN;
    if(cnt1[0].second == cnt2[0].second){
        ans = min({ans, n - cnt1[0].first - cnt2[1].first, n - cnt1[1].first - cnt2[0].first});
    }else{
        ans = n - cnt1[0].first - cnt2[0].first;
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 5088
#include <iostream>
#include <math.h>
#include <algorithm>
#include <set>
#include <map>
#include <string>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i=s;i<n;i++)
#define repe(i,s,n)for(ll i=s;i<=n;i++)
#define rep_r(i,s,n)for(ll i=n-1;i>=s;i--)
#define repe_r(i,s,n)for(ll i=s;i<=n;i++)
static const ll MOD = 1e9 + 7;
static const ll MAX_L = (ll)1 << 55;

int main() {
	ll n, a, b; cin >> n >> a >> b;
	if (b > a) {
		ll t = b;
		b = a;
		a = t;
	}

	cout << b << " " << max(b - (n - a), (ll)0) << endl;

	return 0;
}

Measured memory_bytes: 256
import scala.io.StdIn.readLine

object Main {
  def main(args:Array[String]) = {
    var n = readLine.trim.toInt
    while( n != 0 ) {
      var sum = 0
      val cnt = readLine.trim.toInt
      for(i<-1 to cnt) {
        val s = readLine.trim.split(" ").map(_.toInt)
        sum += s(1)-s(0)
      }
      if(sum >= n) println("OK")
      else println(n-sum)
      n = readLine.trim.toInt
    }
  }
}

Measured memory_bytes: 44556
words = [['null','one pair','three card','four card'], ['','','two pair','full house']]

while True:
    try:
        cards = list(int(x) for x in input().split(","))
        cards = sorted(cards,reverse=False)
        isStright = True
        pairCard = -1
        pairNum = 0
        pairIndex = 0
        
        tmp = cards[0]
        for i in range(1,5):
            if tmp + 1 != cards[i]:
                isStright = False
            if tmp == cards[i]:
                if pairNum >= 1 and pairCard != cards[i]:
                    pairIndex = 1
                pairNum += 1
                pairCard = cards[i]
            tmp = cards[i]
                
        if isStright or (cards[0] == 1 and cards[1] == 10 and cards[2] == 11 and cards[3] == 12 and cards[4] == 13):
            ans = "straight"
        else:
            ans = words[pairIndex][pairNum]
        print(ans)
    except:
        break


Measured memory_bytes: 5600
#!/usr/bin/env python3
import sys
from collections import deque

INF = float("inf")

XX = [1, -1, 0, 0]
YY = [0, 0, 1, -1]


def main():

    H, W = map(int, input().split())
    S = [input() for _ in range(H)]

    dist = [[-1]*W for _ in range(H)]

    ans = 0
    for h in range(H):
        for w in range(W):
            # スタート位置 (h, w)
            if S[h][w] == "#":
                continue
            # 距離
            dist = [[INF]*W for _ in range(H)]

            dist[h][w] = 0
            q = deque([(h, w, 0)])
            while len(q) > 0:
                y, x, p = q.popleft()
                # 上下左右に移動可能ならば、移動して更新する
                for dx, dy in zip(XX, YY):
                    if y + dy < 0 or y + dy >= H:
                        continue
                    if x + dx < 0 or x + dx >= W:
                        continue
                    if S[y+dy][x+dx] == "#":
                        continue
                    if p + 1 < dist[y+dy][x+dx]:
                        dist[y+dy][x+dx] = p+1
                        q.append((y+dy, x+dx, p+1))

            # 一番遠く
            toku = -1
            I, J = -1, -1
            for i in range(H):
                for j in range(W):
                    if dist[i][j] != INF:
                        if dist[i][j] >= toku:
                            I, J = i, j
                        toku = max(dist[i][j], toku)
            if toku >= ans:
                ans = max(toku, ans)
                # print("start: ", h, w, " goal: ", I, J, " dist: ", toku)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 46300
n, m = map(int, input().split())
h = [0] + list(map(int, input().split()))

bl = [True] * (n + 1)
for i in range(m):
    a, b = map(int, input().split())
    if h[a] > h[b]:
        bl[b] = False
    elif h[a] < h[b]:
        bl[a] = False
    else:
        bl[a], bl[b] = False, False
print(sum(bl) - 1)


Measured memory_bytes: 20124
n = int(input())
l = list(map(int, input().split()))
l.sort()
out = 0
for i in range(n-2):
  k = i+2
  a = 1
  for j in range(i+1, n-1):
    a -= 1
    while k < n and l[k] < l[i] + l[j]:
      a += 1
      k += 1
    else:
      out += a
print(out)

Measured memory_bytes: 3316
/* ＵＴＦ－８ */
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <array>
#include <queue>
#include <stack>
#include <algorithm>
#include <tuple>
#include <numeric>
#include <type_traits>
#include <limits>

#include <stdio.h>
#include <unistd.h>
#include <fcntl.h>
#include <string.h>
#include <math.h>

#define USE_COLORED 1

#ifdef USE_COLORED
static const char stdout_pre[]  = "\033[1m"; // bold black
static const char stderr_pre[]  = "\033[31;1m"; // bold red
static const char stdxxx_post[] = "\033[m";

// 当然ながら GCC(g++)/libstdc++ 依存
#include <ext/stdio_filebuf.h>
using stdio_filebuf = __gnu_cxx::stdio_filebuf<char>;
class colored_stdio_filebuf : public stdio_filebuf {
private:
	const char* const pre_;
	const char* const post_;

public:
	colored_stdio_filebuf(FILE* fp, const char* pre, const char* post) : stdio_filebuf(fp, std::ios_base::out), pre_(pre), post_(post)
	{
	}

protected:
	std::streamsize xsputn(const char* s, std::streamsize count) override
	{
		stdio_filebuf::xsputn(pre_, strlen(pre_));
		auto ret = stdio_filebuf::xsputn(s, count);
		stdio_filebuf::xsputn(post_, strlen(post_));
		return ret;
	}
};
#endif

int main()
{
#ifdef USE_COLORED
	if (getenv("DEBUG")) {
		std::cout.rdbuf(new colored_stdio_filebuf(stdout, stdout_pre, stdxxx_post));
		std::cerr.rdbuf(new colored_stdio_filebuf(stderr, stderr_pre, stdxxx_post));
	} else
#endif
	{
		int fd = open("/dev/null", O_WRONLY);
		dup2(fd, 2);
		close(fd);
	}
	
	int N;
	std::cin >> N;

	int s = (int)sqrt(N);
	std::cout << s*s << "\n";
}


Measured memory_bytes: 256
/**
 * Created by hiramekun at 23:05 on 2019-10-29.
 */
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using vb = vector<bool>;
using P = pair<ll, ll>;
template<typename T> using pq = priority_queue<T>;
template<typename T> using minpq = priority_queue<T, vector<T>, greater<T>>;
template<typename T, typename K> using ump = unordered_map<T, K>;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll e5 = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);

#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = ll(n - 1); i >= 0; i--)
#define each(i, mp) for(auto& i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()

template<class T>
ostream &operator<<(ostream &out, const vector<T> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << ' ';
    return out;
}

template<class T>
istream &operator>>(istream &in, vector<T> &list) {
    ll n = list.size();
    rep(i, n) in >> list[i];
    return in;
}

template<class T>
ostream &operator<<(ostream &out, const vector<vector<T>> &list) {
    ll n = list.size();
    rep(i, n) out << list[i] << '\n';
    return out;
}

/* ------------- ANSWER ------------- */
/* ---------------------------------- */
// 素因数分解
map<ll, ll> prime_factor(ll n) {
    map<ll, ll> mp;
    for (ll i = 2; i * i <= n; ++i) {
        while (n % i == 0) {
            mp[i]++;
            n /= i;
        }
    }
    if (n != 1) mp[n]++;
    return mp;
}

// 素数判定
bool is_prime(ll n) {
    for (int i = 2; i * i <= n; i++) if (n % i == 0) return false;
    return n != 1;
}

// 約数列挙
vector<ll> divisor(ll n) {
    vector<ll> res;
    for (ll i = 1; i * i <= n; ++i) {
        if (n % i == 0) {
            res.emplace_back(i);
            if (i != n / i) res.emplace_back(n / i);
        }
    }
    return res;
}

void solve() {
    ll n;
    cin >> n;
    vl div = divisor(n);
    ll ans = 0;
    ans += div.back();
    ans += n / ans;
    ans -= 2;
    cout << ans << '\n';
}

int main() {
#ifdef MY_DEBUG
    while (true) {
#endif
        solve();
#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
#define rep(i, n) for(int i=0;i<(n);++i)
using namespace std;

int main(){
    int x, y;
    cin >> x >> y;
    rep(i, x+1){
        if(i*2+(x-i)*4 == y){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3636
# -*- coding: utf-8 -*-

"""
コッホ曲線
参考：https://www.mynote-jp.com/entry/2016/04/30/201249
　　　https://atarimae.biz/archives/23930
・回転行列を使うと、向きの変わった座標が出せる。
・そのために行列の計算方法も確認。
　→m行n列成分は、「左の行列のm行目」と「右の行列のn列目」の内積
"""

from math import sin, cos, radians

N = int(input())

def dfs(p1x, p1y, p2x, p2y, depth):
    if depth == N:
        return
    sx = p1x + (p2x-p1x)/3
    tx = p1x + (p2x-p1x)/3*2
    sy = p1y + (p2y-p1y)/3
    ty = p1y + (p2y-p1y)/3*2
    # s,tを基準の位置として左回りに60度回転させる
    ux = sx + (tx-sx) * cos(radians(60)) - (ty-sy) * sin(radians(60))
    uy = sy + (tx-sx) * sin(radians(60)) + (ty-sy) * cos(radians(60))
    # 再帰が終了した場所から出力していけば、線分上の各頂点の順番になる
    dfs(p1x, p1y, sx, sy, depth+1)
    print(sx, sy)
    dfs(sx, sy, ux, uy, depth+1)
    print(ux, uy)
    dfs(ux, uy, tx, ty, depth+1)
    print(tx, ty) 
    dfs(tx, ty, p2x, p2y, depth+1)

print(0, 0)
dfs(0, 0, 100, 0, 0)
print(100, 0)



Measured memory_bytes: 5780
#include <iostream>
#include <map>
#include <string>
#include <vector>

using namespace std;

int main() {
  int N, K;
  cin >> N >> K;

  int ret = 0;
  int tmp;
  for(int i=0; i<N; ++i) {
    cin >> tmp;
    if (tmp >= K)
      ret++;
  }

  cout << ret << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        
        int max = Math.max(Math.max(a, b), c);
        int sum = a + b + c;
        
        int goal = max * 3;
        if ((goal - sum) % 2 == 1) {
            goal += 3;
        }
        
        System.out.println((goal - sum) / 2);
    }
}


Measured memory_bytes: 23124
#include <cstdio>
int main (){
    int n,k;scanf ("%d%d",&n,&k);
    if (k==1||k==2*n-1){puts("No");return 0;}
    int now=0;
    puts("Yes");
    for (int i=1;i<n-1;i++){
        ++now;if (now<=k+1&&now>=k-1) {i--;continue;}
        printf ("%d\n",now);
    }
    printf ("%d\n%d\n%d\n",k-1,k,k+1);
    for (int i=1;i<n-1;i++){
        ++now;if (now<=k+1&&now>=k-1) {i--;continue;}
        printf ("%d\n",now);
    }
    return 0;
}

Measured memory_bytes: 1536
#include<iostream>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<math.h>
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>(b);i--)
using namespace std;

int main(void) {
	char moji[2];
	cin >> moji;
	if ((moji[0] == '9') || (moji[1] == '9')) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using std::cout;
using std::endl;
using std::cin;

int main(){
	int n, k; cin >> n >> k; std::vector<int> a(n);
	for(int i = 0; i < n; i++) cin >> a[i];
	
	int pos = 0, c = 0;
	while(pos < n) {
		pos += k;
		pos--;
		c++;
		
		if(pos == n - 1) {
			break;
		}
	}
	
	cout << c << endl;
	return 0;
}


Measured memory_bytes: 640
// CPP program to print the Kth prime greater than N 
#include <bits/stdc++.h> 
using namespace std; 

// set the MAX_SIZE of the array to 10^6 
const int MAX_SIZE = 1e6; 

// initialize the prime array 
bool prime[MAX_SIZE + 1]; 

void sieve() 
{ 

  // set all numbers as prime for time being 
  memset(prime, true, sizeof(prime)); 

  for (int p = 2; p * p <= MAX_SIZE; p++) { 

    // if prime[p] is not changed, then it is a prime 
    if (prime[p] == true) { 

      // update all multiples of p 
      for (int i = p * p; i <= MAX_SIZE; i += p) 
        prime[i] = false; 
    } 
  } 
} 
// Function to find the kth prime greater than n 
int kthPrimeGreaterThanN(int n, int k) 
{ 

  int res = -1; 
  // looping through the numbers greater than n 
  for (int i = n + 1; i < MAX_SIZE; i++) { 

    // decrement k if i is prime 
    if (prime[i] == true) 
      k--; 

    // store the kth prime greater than n 
    if (k == 0) { 
      res = i; 
      break; 
    } 
  } 

  return res; 
} 
bool isPrime(int n) 
{ 
    // Corner cases 
    if (n <= 1)  return false; 
    if (n <= 3)  return true; 
  
    // This is checked so that we can skip  
    // middle five numbers in below loop 
    if (n%2 == 0 || n%3 == 0) return false; 
  
    for (int i=5; i*i<=n; i=i+6) 
        if (n%i == 0 || n%(i+2) == 0) 
           return false; 
  
    return true; 
} 

// Driver code 
int main() 
{ 

  sieve(); 
  int n , k = 1; 
  cin>>n;
  if(isPrime(n)) cout<<n;
  else
  cout << kthPrimeGreaterThanN(n, k); 
  return 0; 
} 


Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <utility>
#include <stack>
#include <queue>
#include <sstream>
#include <fstream>
#include <cstring>

using namespace std;
#define int long long

int num[100000] = {};
template<typename T>
void remove(std::vector<T>& vector, unsigned int index)
{
	vector.erase(vector.begin() + index);
}


signed main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N; i++) {
		int x;
		cin >> x;
		num[x]++;
	}
	int cnt = 0;
	for (int i = 0; i < 100000; i++) {
		if (num[i] != 0) {
			cnt++;
		}
	}
	if (cnt % 2 == 0) cout << cnt - 1 << endl;
	else cout << cnt << endl;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int S[3],ord[3],res;
char s[3][4010];
bool mat[3][3][4010];
int main(){
	memset(mat,true,sizeof(mat));
	for(int i=0;i<3;i++)scanf("%s",s[i]),S[i]=strlen(s[i]),res+=S[i];
	for(int i=0;i<3;i++)for(int j=0;j<3;j++){
		if(i==j)continue;
		for(int k=0;k<S[i];k++){
			for(int l=0;l<S[j]&&k+l<S[i];l++)if(s[i][k+l]!='?'&&s[j][l]!='?'&&s[i][k+l]!=s[j][l]){mat[i][j][k]=false;break;}
			if(mat[i][j][k])res=min(res,(S[0]+S[1]+S[2])-min(S[j],S[i]-k));
//			printf("%d ",mat[i][j][k]);
		}
//		puts("");
	}
	for(int i=0;i<3;i++)ord[i]=i;
	do{
		for(int j=0;j<S[ord[0]];j++)for(int k=j;k<max(S[ord[0]],j+S[ord[1]]);k++){
			if(!mat[ord[0]][ord[1]][j])continue;
			if(!mat[ord[0]][ord[2]][k])continue;
			if(!mat[ord[1]][ord[2]][k-j])continue;
			res=min(res,max(S[ord[0]],max(j+S[ord[1]],k+S[ord[2]])));
		}
	}while(next_permutation(ord,ord+3));
	printf("%d\n",res);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
int n;
int a[300000];
int b[300000];
int flag[300000];
int num=0;
int main()
{
    cin>>n;
    for (int i=1; i<=n; ++i)
        scanf("%d",&a[i]);

    for (int i=n; i>=1; --i)
    {
        int now=0;
        for (int j=n/i; j>=2; --j)
            now=now^b[i*j];
        b[i]=now^a[i];
        num+=b[i];

    }

    cout<<num<<endl;
    for (int i=1; i<=n; ++i)
        if (b[i]==1)
            printf("%d ",i);

    return 0;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define ull unsigned ll
#define pb push_back
#define mp make_pair
 
using namespace std;


int main(){
	ll d,t,s;cin>>d>>t>>s;
	if(d>t*s)cout<<"No";
	else cout<<"Yes";
	return 0;
}
	

	



Measured memory_bytes: 3640
import java.util.*

fun main(args: Array<String>) {
    val sc = Scanner(System.`in`)
    val a = sc.nextLong()
    val b = sc.nextLong()
    val c = sc.nextLong()
    val left = 4 * a * b
    val right = (c-a-b)*(c-a-b)
    if (c - a - b > 0 && left < right) {
        println("Yes")
    } else {
        println("No")
    }
}

Measured memory_bytes: 31264
#include <bits/stdc++.h>

using namespace std;

#define rep(i,m,n) for(int (i)=(int)(m);i<(int)(n);i++)
#define rep2(i,m,n) for(int (i)=(int)(n)-1;i>=(int)(m);i--)
#define REP(i,n) rep(i,0,n)
#define REP2(i,n) rep2(i,0,n)
#define FOR(i,c) for(decltype((c).begin())i=(c).begin();i!=(c).end();++i)
#define ll long long
#define ull unsigned long long
#define all(hoge) (hoge).begin(),(hoge).end()
#define en '\n'
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
constexpr long long MOD = (ll) 1e9 + 7;
typedef vector<ll> Array;
typedef vector<Array> Matrix;


template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

struct Edge {
	ll to, cap, rev;
	Edge(ll _to, ll _cap, ll _rev) {
	to = _to; cap = _cap; rev = _rev;
	}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph& G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
	G[from].push_back(Edge(to, cap, (ll)G[to].size()));
	if (revFlag)G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

ll n;
ll a[20];
ll dp[20][2];

ll dfs(ll i, ll j){
	
	if(dp[i][j]!=-1) return dp[i][j];
	if(i==n) return !j;
	if(j==1){
		ll ret=0;
		if(a[i]%2==0) ret += dfs(i+1, 0)+3*dfs(i+1,1);
		else ret += 2*dfs(i+1,0)+3*dfs(i+1, 1);
		return dp[i][j]=ret;

	}else{
		ll ret=0;
		if(a[i]%2==0) ret += 2 * dfs(i+1, 0);
		else ret += dfs(i+1, 0);
		return dp[i][j]=ret;
	}
}

void solve(){
	cin>>n;
	REP(i,n) cin>>a[i];
	memset(dp,-1,sizeof(dp));
	cout<<dfs(0,1)<<en;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    solve();
	//ll t;cin>>t;REP(i,t) solve();

    return 0;
}


Measured memory_bytes: 256
using System;

public class p0516{
	public p0516 ()
	{
		string str;
		string[] st;
		int[] a = new int[100000];
		int n, m, s, t;
		
		while ((str=Console.ReadLine()) != null && str != "0 0") {
			st = str.Split ();
			n = int.Parse (st [0]);
			m = int.Parse (st [1]);
			
			for (int i = 0; i < n; ++i)
				a [i] = int.Parse (Console.ReadLine ());
			s = t = 0;
			
			for (int i = 0; i < m; ++i)
				t += a [i];
			
			for (int i = m; i < n; ++i) {
				t += (a [i] - a [i - m]);
				s = Math.Max (t, s);
			}
			
			Console.WriteLine ("{0}", s);
		}
	}
	
	public static int Main(string[] args){
		new p0516();
		return 0;
	}
}

Measured memory_bytes: 6536
#include <bits/stdc++.h>
using namespace std;

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    long long N;cin >> N;
    long long B[N-1]={0};
    long long A[N]={0};
    for (long long i=0;i<N-1;i++) cin >> B[i];
    //for(int i=0;i<N-1;i++) cout << B[i] <<endl;
    A[0] = B[0];
    A[N-1] = B[N-2];

    for(long long i = N-2;i>0;i--){
        //cout << B[i] <<" "<<B[i-1] << endl;
        A[i] = min(B[i],B[i-1]);
    }

    long long sum = 0;
    for(long long i=0;i<N;i++){
        sum += A[i];
    }
    cout << sum << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <map>
using namespace std;



vector<int> get_primes(int n){
  //
  int lim = sqrt(n) + 1;
  vector<bool> is_primes(n, true);
  for(int i = 2; i <= lim; i++){
    if(!is_primes[i]) continue;

    for (int j = i*2; j <= n; j+=i) {
      is_primes[j] = false;
    }
  }

  //
  vector<int> primes;
  for (int i = 2; i <= n; ++i) {
    if(is_primes[i])
      primes.push_back(i);
  }

  return primes;
}


int dfs(vector<long long> &factors, int i, long long N, long long M){
  if(i == factors.size()){
//    cout << N << " " << M << endl;
    return max(to_string(N).size(), to_string(M).size());
  }

  int ret1 = dfs(factors, i+1, N/factors[i], M*factors[i]);
  int ret2 = dfs(factors, i+1, N, M);

  return min(ret1, ret2);

}


int main() {

  long long N, i = 0, lim = pow(10, 6) + 1;
  cin >> N;


  // 素因数分解
  long long N1 = N;
  vector<long long> factors;
  vector<int> primes = get_primes(lim);
  while(N1 >= primes[i] && i < primes.size()){

    if(N1 % primes[i] == 0){
      N1 /= primes[i];
//      cout << "N1 " << N1 << " primes[i] " << primes[i] << endl;
      factors.push_back(primes[i]);

    }else{
     i++;
    }
  }
  if(N1 > 1) {
    factors.push_back(N1);
  }

//  for(long long n: factors) cout << n << " ";
//  cout << endl;

  cout << dfs(factors, 0, N, 1) << endl;

  return 0;
}



Measured memory_bytes: 1020
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
DAGになってる！！ 
コスト求めるのがO(m)でいける
*/

ll n,m;
double ans=1e9;
V<ll> v[601];

int main(void){
	cin>>n>>m;
	rep(i,m){
		ll s,t;
		cin>>s>>t;
		v[s].push_back(t);
	}
	reg(i,1,n){
		double d[601]={};
		ireg(j,1,n-1){
			int ma = 0;
			rep(k,v[j].size()){
				if(d[v[j][k]]>d[v[j][ma]])ma=k;
				d[j]+=d[v[j][k]];
			}
			if(i==j && v[j].size()>1){
				d[j]-=d[v[j][ma]];
				d[j]/=v[j].size()-1;
			}else{
				d[j]/=v[j].size();
			}
			d[j]+=1;
		}
		// reg(j,1,n)cerr<<d[j]<<" ";
		// cerr<<endl;
		ans=min(ans,d[1]);
	}
	cout<<fixed<<setprecision(15)<<ans<<endl;
	return 0;
}

Measured memory_bytes: 2560
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    string s,t;
    cin>>s>>t;
    for(int i=s.size()-t.size();i>=0;i--){
        bool ok=true;
        for(int j=0;j<t.size();j++){
            //cout<<s[i+j]<<t[j]<<endl;
            if(s[i+j]!='?' && s[i+j]!=t[j]){
                //<<"X"<<endl;
                ok=false;
                break;
            }
        }
        if(ok==true){
            for(int k=0;k<s.size();k++){
                if(k==i){
                    cout<<t;
                    k+=t.size()-1;
                }
                else{
                    if(s[k]=='?')cout<<'a';
                    else cout<<s[k];
                }
            }
            cout<<endl;
            //cout<<i<<endl;
            return 0;
        }
    }
    cout<<"UNRESTORABLE"<<endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i<(int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using Graph = vector<vi>;  // vi <=> vl
using P = pair<int, int>;  // int <=> ll
const int MOD = 1e9+7;
const double EPS = 1e-9;

int main() {
  int n; cin >> n;
  int even = n/2;
  double odd = n-even;
  double ans = odd / n;
  printf("%.8f\n", ans);
  return 0;
}


Measured memory_bytes: 256
n,c=map(int,input().split())
d=[]
for i in range(c):
  d.append(list(map(int,input().split())))
col=[]
for i in range(n):
  col.append(list(map(int,input().split())))
lc1=[]
lc2=[]
lc3=[]
for i in range(c):
  ccount1=0
  ccount2=0
  ccount3=0
  for j in range(n):
    for k in range(n):
      if (j+k)%3==0:
        ccount1+=d[col[j][k]-1][i]
      elif (j+k)%3==1:
        ccount2+=d[col[j][k]-1][i]
      else:
        ccount3+=d[col[j][k]-1][i]
  lc1.append(ccount1)
  lc2.append(ccount2)
  lc3.append(ccount3)
min=10**10
for i in range(c):
  for j in range(c):
    for k in range(c):
      if i==j or j==k or i==k:
        pass
      else:
        if min>lc1[i]+lc2[j]+lc3[k]:
          min=lc1[i]+lc2[j]+lc3[k]
print(min)


Measured memory_bytes: 44636
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int dx[4] = {-1, 0, 0, 1};
const int dy[4] = {0, -1, 1, 0};

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 31;
// clang-format on

int main(void)
{
  ll N;
  cin >> N;
  cout << (N * (N - 1)) / 2 << endl;
  return 0;
}


Measured memory_bytes: 888
#include<iostream>
#include<algorithm>
using namespace std;

int main(){
  int N;cin>>N;
  int p[N+10];
  int m=0;
  int sum=0;
  for(int i=0;i<N;i++){
    cin>>p[i];
    sum+=p[i];
    m=max(m,p[i]);
  }
  cout<<sum-(m/2)<<endl;
}

Measured memory_bytes: 256
line = input().split(' ')
a = int(line[0])
b = int(line[1])
c = int(line[2])
d = int(line[3])

if abs(a - c) <= d:
    print ('Yes')
elif abs(a - b) <= d and abs(b - c) <= d:
    print ('Yes')
else:
    print ('No')

Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#define llint long long
#define mod 1000000007

using namespace std;

struct SegTree{
	int size;
	vector<llint> seg;
	
	SegTree(){}
	SegTree(int size){
		this->size = size;
		seg.resize(1<<(size+1));
	}
	
	void init()
	{
		for(int i = 0; i < (1<<(size+1)); i++) seg[i] = 0;
	}
	
	void update(int i, llint val)
	{
		i += (1 << size);
		seg[i] = val;
		while(i > 1){
			i /= 2;
			seg[i] = (seg[i*2] + seg[i*2+1]) % mod;
		}
	}

	llint query(int a, int b, int k, int l, int r)
	{
		if(b < l || r < a) return 0;
		if(a <= l && r <= b) return seg[k];
		llint lval = query(a, b, k*2, l, (l+r)/2);
		llint rval = query(a, b, k*2+1, (l+r)/2+1, r);
		return (lval + rval) % mod;
	}
	llint query(int a, int b)
	{
		return query(a, b, 1, 0, (1<<size)-1);
	}
};

llint n, m;
llint p[100005], q[100005];
vector<llint> vecx, vecy;
vector<llint> compX, compY;
vector<llint> vec[100005];
SegTree seg(17);

void comp(vector<llint> &vec, vector<llint> &compX)
{
	for(int i = 0; i < vec.size(); i++) compX.push_back(vec[i]);
	sort(compX.begin(), compX.end());
	compX.erase(unique(compX.begin(), compX.end()), compX.end());
	for(int i = 0; i < vec.size(); i++) vec[i] = lower_bound(compX.begin(), compX.end(), vec[i]) - compX.begin()+1;
}

int main(void)
{
	cin >> n >> m;
	for(int i = 0; i < n; i++) cin >> p[i];
	for(int i = 0; i < m; i++) cin >> q[i];
	
	llint l, r;
	for(int i = 0; i < n; i++){
		l = upper_bound(q, q+m, p[i])-q-1, r = l+1;
		if(l >= 0 && r < m){
			vecx.push_back(p[i] - q[l]);
			vecy.push_back(q[r] - p[i]);
		}
	}
	
	comp(vecx, compX);
	comp(vecy, compY);
	llint H = compY.size(), W = compX.size();
	
	for(int i = 0; i < vecx.size(); i++) vec[vecy[i]].push_back(vecx[i]);
	for(int i = 1; i <= H; i++){
		sort(vec[i].rbegin(), vec[i].rend());
		vec[i].erase(unique(vec[i].begin(), vec[i].end()), vec[i].end());
	}
	
	seg.update(0, 1);
	for(int i = 1; i <= H; i++){
		for(int j = 0; j < vec[i].size(); j++){
			seg.update(vec[i][j], seg.query(0, vec[i][j]));
		}
	}
	llint ans = seg.query(0, W);
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 11628
#include <cstdio>
#include <string>

using namespace std;

int main(void){
    char taro_tmp[500], hanako_tmp[500];
    string taro, hanako;
    int n, p_taro, p_hanako;
  
    p_taro = p_hanako = 0;

    scanf(" %d", &n);
    
    for (int i = 0; i < n; i++){
        scanf(" %s %s", taro_tmp, hanako_tmp);
        taro = taro_tmp;
        hanako = hanako_tmp;

        if (taro > hanako){
            p_taro += 3;
        }
        else if (taro < hanako){
            p_hanako += 3;
        }
        else if (taro == hanako){
            p_hanako++;
            p_taro++;
        }   
    }
    
    printf("%d %d\n", p_taro, p_hanako);
    
    return 0;
}


Measured memory_bytes: 2804
#include<stdio.h>

int main(){
  int year,mon,day,lastd,scan;
  int days[] = { 32, 29, 32, 31, 32, 31, 32, 32, 31, 32, 31, 32 };

  //入力取得
  scan = scanf("%d/%d/%d",&year,&mon,&day);

  lastd = days[mon-1];
  //うるう年
  if(mon == 2){
    if( year % 4 == 0 && year % 100 != 0 || year % 400 == 0 ) lastd = 30;
  }

  if(0 < day && day < lastd){
    //月が１～4か
    if(mon<5){
      //2019年までであれば'Heisei'
      if(year < 2020){
        printf("Heisei\n");
      }
      //月が5以上12以下で2018年までであれば'Heisei'
    }else if(mon < 13 && year < 2019){
      printf("Heisei\n");
    }else{
      //条件に当てはまらなければ'TBD'
      printf("TBD\n");
    }
  }else{
    printf("入力された日付が存在しません。\n");
  }
  return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;

#define repi(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
#define rep(i, n) repi(i, 0, n)
#define all(x) (x).begin(), (x).end()

inline void Main() {
  // code
  int a, b;
  cin >> a >> b;

  if(1 <= a && a <= 9 && 1 <= b && b <= 9) {
    cout << a * b << endl;
  } else {
    cout << -1 << endl;
  }
}

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(20);
  Main();
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
template<class T> istream& operator >> (istream& s, vector<T>& v)
{ for (T& x: v) { s >> x; } return s;}
void yes(){ cout << "Yes" << endl; }
void no(){ cout << "No" << endl; }

int main(){
    int a,b,c; cin >> a >> b >> c ;
    cout << a*b*c/max(a,max(b,c)) /2 << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)

const ll INF = 10010001010;
const int inf = 1000034000;
typedef vector<ll> vecl;
typedef vector<int> veci;
typedef tuple<string, int, int> TUP;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed << setprecision(15);
    int N;
    cin >> N;
    string S;
    cin >> S;
    string T;
    cin >> T;
    for (int i = 0; i < N;i++)
    {
        cout << S[i];
        cout << T[i];
    }
    cout << endl;
}


Measured memory_bytes: 3544
#include<bits/stdc++.h>
#define int long long
using namespace std;
constexpr int mod=1e9+7;
bool tmp[16][16];
int dp[16][16];
signed main(){
    int a,b,n,x,y;
    while(cin>>a>>b,a){
        for(int i=0;i<16;i++)
            for(int j=0;j<16;j++)
                tmp[i][j]=dp[i][j]=0;
        cin>>n;
        for(int i=0;i<n;i++){
            cin>>x>>y;
            tmp[x-1][y-1]=1;
        }
        dp[0][0]=1;
        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                if(tmp[i][j])
                    continue;
                if(i!=0)
                    dp[i][j]=dp[i-1][j];
                if(j!=0)
                    dp[i][j]+=dp[i][j-1];
            }
        }
        cout<<dp[a-1][b-1]<<endl;
    }
}



Measured memory_bytes: 3024
#include <bits/stdc++.h>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    set<int> s;
    for (int i = 0; i < 3; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    cout << ((s.size() == 2) ? "Yes\n" : "No\n");

    return 0;
}


Measured memory_bytes: 256
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <iostream>
#include <iostream>
#include <fstream>
#include <numeric>
#include <cstring>
#include <cassert>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <cmath>
#include <set>
#include <map>
#include <functional>
#include <bitset>
#include <iomanip>
#include <stack>
#include <list>
using namespace std;
#define     loop(n,i,a)     for(ll i=a;i<n;i++)
#define     loopR(n,i,a)    for(ll i=n-1;i>=a;i--)
#define     all(arr,n)      arr,arr+n
#define     allv(v)         (v).begin(),(v).end()
#define     rallv(v)        (v).rbegin(),(v).rend()
#define     m_p             make_pair
#define     ll              long long
#define     pii             pair<ll,ll>
#define     vi              vector<int>
#define     vll             vector<ll>
#define     vii             vector<pair<ll,ll>>
#define     sz(x)           (int)x.size()
#define     pb              push_back
#define     endl            "\n"
#define     Endl            "\n"
#define     f               first
#define     s               second
#define     mem(dp,n)       memset(dp,n,sizeof dp)
int dx[] = { 1 , 0 ,-1 , 0 ,-1 ,-1 , 1 , 1 };
int dy[] = { 0 , 1 , 0 ,-1 ,-1 , 1 ,-1 , 1 };
int KnightI[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
int KnightJ[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
template<typename T>
void max_self(T &a,T b){
    a=max(a,b);
}
template<typename T>
void min_self(T &a,T b){
    a=min(a,b);
}
void fast(){
    std::ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
}
vector<string> vec_splitter(string s) {
    s += ',';
    vector<string> res;
    while(!s.empty()) {
        res.push_back(s.substr(0, s.find(',')));
        s = s.substr(s.find(',') + 1);
    }
    return res;
}
void debug_out(
        vector<string> __attribute__ ((unused)) args,
        __attribute__ ((unused)) int idx,
        __attribute__ ((unused)) int LINE_NUM) { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(vector<string> args, int idx, int LINE_NUM, Head H, Tail... T) {
    if(idx > 0) cerr << ", "; else cerr << "Line(" << LINE_NUM << ") ";
    stringstream ss; ss << H;
    cerr << args[idx] << " = " << ss.str();
    debug_out(args, idx + 1, LINE_NUM, T...);
}
#define debug(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
const ll mxN=2e4+10,oo=0x3f3f3f3f,MOD=998244353;
const double PI = acos(-1);

void solve(){
    ll n;
    cin>>n;
    ll res=(n/500)*1000;
    n%=500;
    res+=(n/5)*5;
    cout<<res<<endl;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    fast();
    solve();
}

Measured memory_bytes: 3568
#include <bits/stdc++.h>
using namespace std;
#define NDEBUG
#include <cassert>
#define rep(i,a,n) for (int i=a;i<n;i++)

 
// ------------------------------------------------------------------------------------------
int a;
double b;
double c;
string d;
double r = 0.0;
int main()
{
    cin >> a;
    rep(i, 0, a) {
       cin >> c >> d;
       if (d == "JPY") {
           r = r + c;
       }
       else if (d == "BTC")
       {
           r = r + c * 380000.0;
       }
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 256
#include <cassert>
#include <algorithm>
#include <array>
#include <bitset>
#include <cctype>
#include <cstdint>
#include <cmath>
#include <complex>
#include <chrono>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>
#include <random>
#include <memory>
#include <utility>
#include <limits>
#include "limits.h"
 
#define rep(i, a, b) for (long long (i) = (a); (i) < (b); (i)++)
#define all(i) i.begin(), i.end()
#define debug(...) std::cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

void debug_out(){std::cerr<<std::endl;}

template<typename Head,typename... Tail>
void debug_out(Head h,Tail... t){
  std::cerr<<" "<<h;
  debug_out(t...);
}
 
template <typename T1, typename T2>
std::ostream& operator<<(std::ostream& os, std::pair<T1, T2> pa) {
  return os << pa.first << " " << pa.second;
}
 
template <typename T>
std::ostream& operator<<(std::ostream& os, std::vector<T> vec) {
  for (int i = 0; i < vec.size(); i++)os << vec[i] << (i + 1 == vec.size() ? "" : " ");
  return os;
}
 
template<typename T1,typename T2>
inline bool chmax(T1& a,T2 b){return a<b && (a=b,true);}
 
template<typename T1,typename T2>
inline bool chmin(T1& a,T2 b){return a>b && (a=b,true);}
 
long long pow_mod(long long a, long long b, long long mod=-1) {
  if(b==0)return 1;
  if ((a == 0)||(mod!=-1&&(a+mod)%mod==0)) {
    return 0;
  }
  long long x = 1;
  while (b > 0) {
    if (b & 1) {
      x = (mod!=-1)?(x * a) % mod:x*a;
    }
    a = (mod!=-1)?(a * a) % mod:a*a;
    b >>= 1;
  }
  return x;
}

// const long long MOD = 998244353;
const long long MOD = 1e9 + 7;

using ll = long long;
using P=std::pair<long long,long long>;

int main() {
  std::cin.tie(nullptr);
  std::ios::sync_with_stdio(false);

  std::string s;
  std::cin>>s;

  rep(i,0,s.size())std::cout<<"x";

  std::cout<<"\n";

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main()
{
    int s,i[58]={};
    while(1)
    {
        s=getchar();
        if(s==EOF)break;
        i[s-65]++;
    }
    for(s=0;s<26;s++)
    printf("%c : %d\n",s+97,i[s]+i[s+32]);
}



Measured memory_bytes: 2112
#include <iostream>
using namespace std;
using ll = long long int;
int main() {
    ll N;
    cin >> N;
    ll sum = 0;
    for (ll i = 0; i < N; i++) {
        ll li, ri;
        cin >> li >> ri;
        sum += (ri - li + 1);
    }
    cout << sum << endl;
}

Measured memory_bytes: 256
import Foundation

#if swift(>=4.0)
extension String {
    func split(by separator: String) -> [String] {
        return self.components(separatedBy: separator)
    }
    func toArray() -> [String] {
        return self.map{String($0)}
    }
}
func exponentiate(_ lhs: Int, _ rhs: Int) -> Int {
    return (0..<rhs).reduce(1){i,_ in i*lhs}
}
#else
extension String {
    func split(by separator: String) -> [String] {
        return self.componentsSeparatedByString(separator)
    }
    var count: Int {
        return self.characters.count
    }
    func toArray() -> [String] {
        return self.characters.map{String($0)}
    }
    func uppercased() -> String {
        return self.uppercaseString
    }
    func lowercased() -> String {
        return self.lowercaseString
    }
}
//extension Array where Element == String {
//    func joined(separator separator: String) -> String {
//        return self.joinWithSeparator(separator)
//    }
//}
extension Array where Element: Comparable {
    func max() -> Element? {
        return self.maxElement()
    }
    func min() -> Element? {
        return self.minElement()
    }
    func sorted() -> Array {
        return self.sort()
    }
    func reversed() -> Array {
        return self.reverse()
    }
//    func enumerated() -> [(Int, Element)] {
//        return self.enumerate()
//    }
    mutating func sort() {
        self.sortInPlace()
    }
}
extension Array {
    init(repeating: Element, count: Int) {
        self.init(count: count, repeatedValue: repeating)
    }
}
func stride<T: Strideable>(from start: T, to end: T, by stride: T.Stride) -> StrideTo<T> {
    return start.stride(to: end, by: stride)
}
func exponentiate(lhs: Int, _ rhs: Int) -> Int {
    return (0..<rhs).reduce(1){i,_ in i*lhs}
}
#endif
func readInt() -> Int? {
    return Int(readLine()!)
}
func readStringSplit(by separator: String) -> [String] {
    return readLine()!.split(by: separator)
}
func readIntSplit(by separator: String) -> [Int] {
    return readLine()!.split(by: separator).map{Int($0)!}
}

/*************** テストスペース ***************/

//func gcd(x: Int, _ y: Int) -> Int {
//    if y == 0 {
//        return x
//    } else {
//        return gcd(y, x%y)
//    }
//}

/*************** メインプログラム ***************/

let N = readInt()!
let X = readIntSplit(by: " ")
let sortedX = X.sorted()
var center = sortedX[N/2]
for i in X {
    if i < center {
        print(center)
    } else {
        print(sortedX[N/2-1])
    }
}


Measured memory_bytes: 13880
#include <iostream>
#include <string>

using namespace std;

int main() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    int count = 1;  // at least one charcter exists
    char t = s[0];
    for (int i = 1; i < n; ++i) {
        if (t != s[i]) {
            ++count;
            t = s[i];
        }
    }

    cout << count << '\n';
}


Measured memory_bytes: 512
n = int(input())
l = list(map(int,input().split()))
m = int(input())
p_x = []
for i in range(m):
  p_x.append(list(map(int,input().split())))
for i in range(m):
  p = p_x[i][0]
  x = p_x[i][1]
  print(sum(l) - l[p-1] + x) 

Measured memory_bytes: 3060