akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline
from itertools import accumulate

N,W = map(int,input().split())
WV = [[int(i) for i in input().split()] for _ in range(N)]

MINW = WV[0][0]

# それぞれの重さについての価値のリスト
W0 = sorted([0] + [v for w,v in WV if w == MINW])
W1 = sorted([0] + [v for w,v in WV if w == MINW+1])
W2 = sorted([0] + [v for w,v in WV if w == MINW+2])
W3 = sorted([0] + [v for w,v in WV if w == MINW+3])

# 累積和
W0 = tuple(accumulate(W0))
W1 = tuple(accumulate(W1))
W2 = tuple(accumulate(W2))
W3 = tuple(accumulate(W3))

ans = 0
for w0 in range(len(W0)):
    for w1 in range(len(W1)):
        for w2 in range(len(W2)):
            for w3 in range(len(W3)):
                # tmp: 状態(w0,w1,w2,w3)での重さ
                tmp = (len(W0) - (w0 + 1)) * MINW
                tmp += (len(W1) - (w1 + 1)) * (MINW+1)
                tmp += (len(W2) - (w2 + 1)) * (MINW+2)
                tmp += (len(W3) - (w3 + 1)) * (MINW+3)

                # ナップサックに入る場合
                if tmp <= W:
                    # tmp: 価値の総和
                    tmp = W0[-1] - W0[w0]
                    tmp += W1[-1] - W1[w1]
                    tmp += W2[-1] - W2[w2]
                    tmp += W3[-1] - W3[w3]
                    ans = max(ans, tmp)

print(ans)

Measured memory_bytes: 3444
#include "bits/stdc++.h"
using namespace std;
struct Card{char suit,value;};

void bubble(struct Card aa[], int n) {
	for (int i = 0; i<n; i++) {
		for (int j = n-1; j>=i+1; j--) {
			if(aa[j].value < aa[j-1].value){
				swap( aa[j-1],aa[j]);
			}
		}
	}
}

void sectionsort(struct Card aa[], int n) {
	for (int i = 0; i<n; ++i) {
		int minj=i;
		for (int j = i; j<n; j++) {
			if(aa[j].value<aa[minj].value){minj=j;}
		}
			swap(aa[i], aa[minj]);
		}
}
void print(struct Card aa[],int N){
	for (int i = 0; i < N; ++i) {
			if(i>0)cout<<" ";
			cout<<aa[i].suit<<aa[i].value;
	}
	cout<<endl;
}
bool isStable(struct Card c1[],struct Card c2[],int n){
	for (int i = 0; i < n; ++i) {
		if (c1[i].suit!=c2[i].suit) {
			return false;
		}
	}return true;
}

int main() {
	Card c1[100],c2[100];
	int n;
	cin>>n;
	for (int i = 0; i < n; ++i) {
		cin>>c1[i].suit>>c1[i].value;
	}
	for (int i = 0; i < n; i++) {c2[i]=c1[i];}
	bubble(c1, n);
	sectionsort(c2, n);
	print(c1,n);
	cout<<"Stable"<<endl;
	print(c2,n);
	if (isStable(c1,c2,n)) {
		cout<<"Stable"<<endl;
	} else{
		cout<<"Not stable"<<endl;
	}
}


Measured memory_bytes: 3108
#include <iostream>

using namespace std;
typedef long long int ll;

int main(void){
  ll N,A,B;
  cin >> N >> A >> B;
  ll set = A + B;
  ll num = (ll)(N/set);
  ll rem = N - num*set;
  ll sum = num * A;
  if(rem <= A){
    sum = sum + rem;
  }else{
    sum = sum + A;
  }
  cout << sum << endl;
  return 0;
  
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <complex>
#include <queue>
#include <deque>
#include <cmath>
#define FOR(i,a,b) for(int i=(a);i<(int)(b);i++)
#define REP(i,a) FOR(i,0,a)
#define FORE(i,a,b) for(int i=(a);i<=(int)(b);i++)
using namespace std;
typedef complex<int> cl;
typedef pair<long double,int> pr;
typedef pair<pr,int> ppr;
typedef vector<pr> vpr;
const int INF=1<<30;
const int dx[]={0,1,0,-1},dy[]={1,0,-1,0};

double DP[51][5001]={};
int main() {
	int X,Y,Z;
	int tmp;
	while(cin >> X >> Y >>Z && X){
		REP(i,51)
			REP(j,5001)
				DP[i][j]=0;
	int event[51][2]={};
	int eye[10]={};
	REP(i,X)
		cin >> eye[i];
	REP(i,Z){
		cin >> tmp ;
		cin >>event[tmp][0] >> event[tmp][1];
	}
	DP[0][0]=1;
	
	REP(i,Y)
		FORE(k,0,5000){
				double par=(DP[i][k]/(long double)X);
				if(par==0) continue;
			REP(j,X){
				int money=k;
				int next=min(Y,i+eye[j]);
				switch(event[next][0]){
					case 1:
						next+=event[next][1];
						break;
					case 2:
						money+=event[next][1];
						break;
					case 3:
						money-=event[next][1];
						money=max(0,money);
						break;
				}
				next=min(Y,next);
				DP[next][money]+=par;
			}
		}
	long double mean=0;
	FORE(i,0,5000){
		mean+=(long double)i*DP[Y][i];
	//	if(DP[Y][i])
//	cout << DP[Y][i] << " " <<i << endl;
	}
	cout << (int)mean<< endl;	
	
	}
	return 0;
}

Measured memory_bytes: 3152
#include <bits/stdc++.h>
#define rep(i, a, n) for(int i = a; i < n; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define int long long
#define all(a) a.begin(), a.end()
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef pair<int, int> P;
const int mod = 1000000007;
const int INF = 1e12;

int digitSum(int n){
   int res = 0;
   while(n){
       res += n % 10;
       n /= 10;
   }
   return res;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    vector<int> ans;
    rep(i, 1, 10) ans.push_back(i);
    ans.push_back(19);
    int last = 19;
    while(ans.size() < k){
        int now = digitSum(last);
        int add = 1;
        while((last + add) * digitSum(last + add * 2) > (last + add * 2) * digitSum(last + add)){
            add *= 10;
        }
        last += add;
        ans.push_back(last);
    }
    rep(i, 0, k){
        cout << ans[i] << endl;
    }
}

Measured memory_bytes: 256
MOD = 1000000007

def F(k, s):
    return dp[k][s]

def solve(n):
    resp = 0
    n = map(int, str(n))
    pref = 0
    for i in range(len(n)):
        for d in range(n[i]):
            resp += F(len(n) - i - 1, (pref - d) % D)
            resp %= MOD
        pref -= n[i]
        pref %= D
    return resp


K = raw_input()
D = input()

# dp[i][j] = cant de numeros de i digitos con suma % d = j
dp = [[0] * D for _ in range(len(K) + 1)]
dp[0][0] = 1
for i in range(1, len(K) + 1):
    for j in range(D):
        for d in range(10):
            dp[i][j] += dp[i - 1][(j - d) % D]
            dp[i][j] %= MOD

resp = solve(K) - 1
if sum(map(int, str(K))) % D == 0:
    resp += 1
print(resp % MOD)


Measured memory_bytes: 41372
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef pair<int, int> P;

int main(){
  int n, k;
  cin >> n >> k;
  priority_queue<ll> q;
  rep(i, n){
    ll a;
    cin >> a;
    q.push(a);
  }
  if(n >= k){
    rep(i, k){
      q.pop();
    }
  }else{
    cout << 0 << endl;
    return 0;
  }
  ll cnt = 0;
  while(!q.empty()){
    ll qq = q.top(); q.pop();
    cnt += qq;
//cout << qq << endl;
  }
  cout <<  cnt << endl;
}


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

#define __STDC_FORMAT_MACROS
#define p64 PRId64

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR (i, 0, n)
#define ALL(f, x, ...)                                                         \
    ([&] (decltype ((x)) ALL) {                                                \
        return (f) (begin (ALL), end (ALL), ##__VA_ARGS__);                    \
    }) (x)

using namespace std;
using ll = int64_t;

int main() {
    int X, Y, Z;
    cin >> X >> Y >> Z;
    cout << Z << " " << X << " " << Y << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll      	long long int
#define PI      	acos(-1)
#define read    	freopen("in.txt","r",stdin)
#define uu      	first
#define vv      	second
#define write   	freopen("out.txt","w",stdout)
#define pii     	pair<int,int>
#define pll         pair<ll,ll>
#define INF     	1e9
#define EPS     	1e-8
#define MAX     	1000006
#define MOD     	1000000007
#define fastRead 	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
int n;
ll dp[(1<<21) + 100];
int ara[30][30];


ll solve(int mask) {

    if( mask == (1<<n) -1 ) return 1;

    ll &ret = dp[mask];
    if( ret != -1) return ret;

    ret = 0;

    int id = __builtin_popcount(mask);

    for(int i = 0 ; i < n ; i++ ) {
        if( ara[id][i] && (mask & (1<<i) ) ==0 ) {
            ret = ( ret + solve(mask | (1<<i) ) %MOD ) %MOD;
        }
    }
    return ret;
}

int main()
{
    fastRead;
    cin>>n;
    for(int i =0 ; i < n ; i++ ) {
        for(int j = 0 ; j < n ; j++ ) {
            cin>>ara[i][j];
        }
    }

    memset(dp , -1 , sizeof dp);
    cout<<solve(0)<<endl;
    return 0;
}


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

using namespace std;

typedef unsigned long long ull;
#define loop(i,a,b) for(int i=(a);i<ull(b);++i)
#define rep(i,n) loop(i,0,n)
#define all(a) (a).begin(), (a).end()

const double eps = 1e-10;
const double pi  = acos(-1.0);
const double inf = (int)1e8;

int main(){
	int n;
	cin >> n;
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	a--; b--; c--; d--;
	int ret = inf;

	for(int i = 1; i <= n; i++){
		ret = min(abs(a%i-b%i)+abs(a/i-b/i)+abs(c%i-d%i)+abs(c/i-d/i), ret);
	}
	cout << ret << endl;
}

Measured memory_bytes: 1164
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

#define POS(i,j) ((i)*m+(j))

int calcMax(int *a,int *b,int n,int m,int *maxRef){
  int cnt[301];
  int i;
  for(i=0;i<=m;i++) cnt[i]=0;
  for(i=0;i<n;i++){
    cnt[a[POS(i,b[i])]]++;
  }
  int max=0;
  int maxIndex=0;
  for(i=1;i<=m;i++){
    if(max<cnt[i]){
      max=cnt[i];
      maxIndex=i;
    }
  }
  *maxRef=max;
  return maxIndex;
}

void run(void){
  int n,m;
  scanf("%d%d",&n,&m);
  int *a=(int *)calloc(n*m,sizeof(int));
  int i,j;
  for(i=0;i<n;i++){
    for(j=0;j<m;j++){
      scanf("%d",a+POS(i,j));
    }
  }
  int assign[300];
  for(i=0;i<n;i++) assign[i]=0;
  int can[300];
  for(i=1;i<=m;i++) can[i]=1;
  int min=n;
  for(i=0;i<m-1;i++){
    int max;
    int index=calcMax(a,assign,n,m,&max);
    can[index]=0;
    min=MIN(min,max);
    for(j=0;j<n;j++){
      while(!can[a[POS(j,assign[j])]]) assign[j]++;
    }
  }
  printf("%d\n",min);
  return;
}

int main(void){
  run();
  return 0;
}


Measured memory_bytes: 512
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<stack>
#include<cstring>
#include<utility>
#include<cmath>
#include<assert.h>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>

#define int long long
using namespace std;
#define rep(i, n) for(int i=0;i<(n);++i)
typedef pair<int, int> pii;
const int INF = 1l << 60;
#define u_b upper_bound
#define l_b lower_bound

int N;
int X[1010], Y[1010];
int U[1010], V[1010];//u=x+y,v=x-y
bool even;

signed main() {
    cin >> N;
    rep(i, N) {
        cin >> X[i] >> Y[i];
        if (i == 0) {
            if ((X[i] + Y[i]) % 2 == 0) {
                even = true;
            } else {
                even = false;
            }
        }
        if (even) {
            --X[i];
        }
        if ((X[i] + Y[i]) % 2 == 0) {
            cout << -1 << endl;
            return 0;
        }
        U[i] = X[i] + Y[i];
        V[i] = X[i] - Y[i];
    }
    int m;
    m = even ? 32 : 31;
    cout << m << endl;
    if (even)cout << "1 ";
    rep(i, 31) {
        cout << (i ? " " : "") << (1ll << i);
    }
    cout << endl;
    rep(i, N) {
        if (even)cout << "R";
        int u = (U[i] + (1ll << 31) - 1) / 2;
        int v = (V[i] + (1ll << 31) - 1) / 2;
        rep(j, 31) {
            if (u % 2 && v % 2)cout << "R";
            else if (u % 2 == 0 && v % 2 == 0)cout << "L";
            else if (u % 2)cout << "U";
            else cout << "D";
            u /= 2;
            v /= 2;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 256
// ALDS1_4_C: Dictionary

use std::collections::HashSet;

fn scan<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let a = s.trim().parse().ok().unwrap();
    a
}

fn scan_tuple() -> (String, String) {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let mut it = s.split_whitespace();
    let a = it.next().unwrap().to_string();
    let b = it.next().unwrap().to_string();
    (a, b)
}

fn main() {
    let n: usize = scan();
    let mut h = HashSet::new();

    for _ in 0..n {
        let (com, key): (String, String) = scan_tuple();
        match &com[..] {
            "insert" => {
                h.insert(key.clone());
            },
            "find" => {
                if h.contains(&key) {
                    println!("yes");
                } else {
                    println!("no");
                }
            },
            _ => {
                // Do nothing.
            }
        }
    }
}


Measured memory_bytes: 31492
#include <stdio.h> 
int main(void){ 
int a=0,b=0; 
scanf("%d %d",&a,&b); 
if(a>b) {printf("a > b\n");}
else if(a<b) {printf("a < b\n");} 
else {printf("a == b\n");} 
return 0;
}

Measured memory_bytes: 580
#include <bits/stdc++.h>
using namespace std;
int main() {
string S,T;
int A,B;
string U;
cin>>S>>T;
cin>>A>>B;
cin>>U;
if(S==U){
    A-=1;
}else{
    B-=1;
}
cout<<A<<" "<<B<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAX_N 100005

ll T;
int N;
ll s[MAX_N],t[MAX_N];

int main(){
  fill(s,s+MAX_N, (1LL<<60) );
  fill(t,t+MAX_N, (1LL<<60) );
  cin>>T>>N;
  for(int i=0;i<N;i++)cin>>s[i]>>t[i];
  ll ans=0,sum=0;
  int f=0;
  for(int i=0;i<N;i++){
    ll key=s[i]+T;
    while(f<N&&t[f]<key){
      sum+=(t[f]-s[f]);
      f++;
    }
    ll d=(s[f]<key?d=key-s[f]:0LL);
    ans=max(ans, sum+d);
    sum-=(t[i]-s[i]);
  }
  cout<<ans<<endl;
  return 0;
}

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

int bubbleSort(int A[],int N){
	int sw=0;
	bool flag=1;
	for(int i=0;flag;i++){
		flag=0;
		for(int j=N-1;j>=i+1;j--){
			if(A[j]<A[j-1]){
				swap(A[j],A[j-1]);
				flag=1;
				sw++;
			}
		}
	}
	return sw;
}

int main(){
	int A[100],N,sw;
	cin>>N;
	for(int i=0;i<N;i++) cin>>A[i];
	
	sw=bubbleSort(A,N);
	
	for(int i=0;i<N;i++){
		if(i)cout<<" ";
		cout<<A[i];
	}
	cout<<endl;
	cout<<sw<<endl;
	
	return 0;
}

Measured memory_bytes: 3096
import std.conv, std.stdio, std.string;
import std.algorithm, std.array, std.bigint, std.container, std.math, std.range, std.regex, std.typecons;
import core.bitop, core.thread;

class EOFException : Throwable { this() { super("EOF"); } }
string[] tokens;
string readToken() { for (; tokens.empty; ) { if (stdin.eof) throw new EOFException; tokens = readln.split; } auto token = tokens[0]; tokens.popFront; return token; }
int readInt() { return readToken().to!int; }
long readLong() { return readToken().to!long; }
real readReal() { return readToken().to!real; }

void chmin(T)(ref T t, in T f) { if (t > f) t = f; }
void chmax(T)(ref T t, in T f) { if (t < f) t = f; }

int binarySearch(T)(in T[] as, in bool delegate(T) test) { int low = -1, upp = cast(int)(as.length); for (; low + 1 < upp; ) { int mid = (low + upp) >> 1; (test(as[mid]) ? low : upp) = mid; } return upp; }
int lowerBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a < val)); }
int upperBound(T)(in T[] as, in T val) { return as.binarySearch((T a) => (a <= val)); }


int N;
long M;
int[] X, Y;

int[][] graph, children;
long[] dp0, dp1;
long[][] ls, rs;

void dfs0(int u, int p) {
  foreach (v; graph[u]) {
    if (v != p) {
      children[u] ~= v;
    }
  }
  foreach (v; children[u]) {
    dfs0(v, u);
  }
  dp0[u] = 1;
  foreach (v; children[u]) {
    (dp0[u] *= (dp0[v] + 1)) %= M;
  }
}

void dfs1(int u) {
  foreach (j, v; children[u]) {
    dp1[v] = 1;
    (dp1[v] *= dp1[u]) %= M;
    (dp1[v] *= ls[u][j]) %= M;
    (dp1[v] *= rs[u][j + 1]) %= M;
    ++dp1[v];
  }
  foreach (v; children[u]) {
    dfs1(v);
  }
}

void main() {
  try {
    for (; ; ) {
      N = readInt();
      M = readLong();
      X = new int[N - 1];
      Y = new int[N - 1];
      foreach (i; 0 .. N - 1) {
        X[i] = readInt() - 1;
        Y[i] = readInt() - 1;
      }
      graph = new int[][N];
      foreach (i; 0 .. N - 1) {
        graph[X[i]] ~= Y[i];
        graph[Y[i]] ~= X[i];
      }
      children = new int[][N];
      dp0 = new long[N];
      dfs0(0, -1);
      ls = new long[][N];
      rs = new long[][N];
      foreach (u; 0 .. N) {
        ls[u] = new long[children[u].length + 1];
        rs[u] = new long[children[u].length + 1];
        ls[u][0] = 1;
        foreach (j, v; children[u]) {
          ls[u][j + 1] = (ls[u][j] * (dp0[v] + 1)) % M;
        }
        rs[u][children[u].length] = 1;
        foreach_reverse (j, v; children[u]) {
          rs[u][j] = (rs[u][j + 1] * (dp0[v] + 1)) % M;
        }
      }
      dp1 = new long[N];
      dp1[0] = 1;
      dfs1(0);
      foreach (u; 0 .. N) {
        long ans = 1;
        (ans *= dp1[u]) %= M;
        (ans *= ls[u][children[u].length]) %= M;
        writeln(ans);
      }
      debug {
        writefln("dp0 = %s", dp0);
        writefln("dp1 = %s", dp1);
      }
    }
  } catch (EOFException e) {
  }
}


Measured memory_bytes: 29564
import java.util.Scanner;


public class Main{

	public static void main(String args[]){
	int i,j,k,min,m;
	Scanner sc=new Scanner(System.in);
	int n=Integer.parseInt(sc.next());
	int a[]=new int[n+1];
	for(i=0;i<n;i++){
		a[i]=Integer.parseInt(sc.next());
	}
int count=0;
	for(i=0;i<n;i++){
		min=i;
		m=a[i];
		for(j=i;j<n;j++){
		if(a[j]<a[min]){
		min=j;	
		}
		}
		if(min!=i){
			count++;
		}
		a[i]=a[min];
		a[min]=m;
	}
	
	for(i=0;i<n;i++){
		System.out.print(a[i]);
		System.out.print((i==n-1) ?"\n":" " );
	}
	System.out.println(count);
	}
}

Measured memory_bytes: 17304
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <vector>
#include <list>
#include <map>
#include <set>
using namespace std;

long long p[88];

int main()
{
	memset(p,0,sizeof(p));
	p[0]=2;
	p[1]=1;
	for(int a=2;a<=86;a++)
	{
		p[a]=p[a-1]+p[a-2];
	}
	int n;
	while(cin>>n)
	{
		cout<<p[n]<<endl;
	}
}

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

using namespace std;

const int MOD = 1e9 + 7;
const long long INF = 1e18;
const int MaxN = 2e5 + 15;
const int MaxC = 1e6;

long long C;
long long dp[MaxN];
int h[MaxN];
int n;

struct Line{
    long long A, B;

    long long getX(long long x)
    {
        return A * x + B;
    }
};

struct LiChaoTree{
    Line tree[MaxC * 4];


    void add(int x, int l, int r, Line line)
    {
        if(!tree[x].A)
        {
            tree[x] = line;
            return;
        }
        if(l == r)
        {
            if(tree[x].getX(l) > line.getX(l))
                tree[x] = line;
        }else
        {
            int mid = (l + r) / 2;

            bool betterL = line.getX(l) < tree[x].getX(l);
            bool betterMid = line.getX(mid) < tree[x].getX(mid);

            if(betterMid)
                swap(line, tree[x]);

            if(betterL != betterMid)
            {
                add(x + x, l, mid, line);
            }else
            {
                add(x + x + 1, mid + 1, r, line);
            }
        }
    }

    void add(long long a, long long b)
    {
        add(1, 1, MaxC, Line{a, b});
    }
    long long get(int x)
    {
        long long curRes = tree[1].getX(x);
        int l = 1, r = MaxC;
        int v = 1;

        while(l < r)
        {
            if(!tree[v].A)
                break;

            int mid = (l + r) / 2;
            if(mid >= x)
            {
                r = mid;
                v += v;
            }else
            {
                l = mid + 1;
                v += v + 1;
            }

            if(tree[v].A)
                curRes = min(curRes, tree[v].getX(x));
        }

        return curRes;
    }
} liChaoTree;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//    freopen("input.txt", "r", stdin);

    cin >> n >> C;
    for(int i = 1; i <= n; ++i)
        cin >> h[i];

    liChaoTree.add(-2 * h[1], (long long) h[1] * h[1]);

    for(int i = 2; i <= n; ++i)
    {
        dp[i] = C + (long long) h[i] * h[i] + liChaoTree.get(h[i]);
        liChaoTree.add(-2 * h[i], dp[i] + (long long) h[i] * h[i]);
    }

    cout << dp[n] << '\n';

    return 0;
}



Measured memory_bytes: 37376
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, P> PP;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  // ワーシャルフロイド
  int n; cin >> n;
  ll dist[n][n];
  vector<PP> v;
  FOR(i,0,n){
    FOR(j,0,n){
      if(i==j) dist[i][j] = 0;
      else dist[i][j] = 1e15;
    }
  }
  FOR(i,0,n) {
    FOR(j,0,n) {
      int in; cin >> in;
      if(j > i) {
        v.push_back(PP(in, P(i, j)));
      }
    }
  }
  sort(v.begin(), v.end());
  ll ans = 0;
  FOR(i,0,v.size()) {
    int x = v[i].second.first;
    int y = v[i].second.second;
    ll cost = v[i].first;
    FOR(k,0,n) dist[x][y] = min(dist[x][y], dist[x][k] + dist[k][y]);
    FOR(k,0,n) dist[y][x] = min(dist[y][x], dist[y][k] + dist[k][x]);
    if(dist[x][y] > cost) {
      ans += cost;
      dist[x][y] = cost;
      dist[y][x] = cost;
    } else if(dist[x][y] < cost) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2168
#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>

int main()
{
    int n = 0, m = 0;

    int inputsize = 0, cache1 = 0, cache2 = 0;
    std::cin >> n >> m;
    std::vector<std::vector<int>> paths(n + 1);
    while (inputsize < m) {
        std::cin >> cache1 >> cache2;
        paths[cache1].push_back(cache2);
        paths[cache2].push_back(cache1);
        inputsize++;
    }

    std::queue<int> search_queue;
    search_queue.push(1);

    std::vector<int> guide(n + 1);
    for (auto& e : guide) {
        e = 0;
    }
    guide[1] = 1;

    int searched = 0;

    while (!search_queue.empty()) {
        auto searching = search_queue.front();
        for (int i = 0; i < paths[searching].size(); i++) {
            int adding = paths[searching][i];

            if (guide[adding] == 0) {
                search_queue.push(adding);
                guide[adding] = searching;
            }
        }
        searched++;
        search_queue.pop();
    }

    if (searched == n) {
        std::cout << "Yes\n";
        for (int i = 2; i < guide.size(); i++) {
            std::cout << guide[i] << "\n";
        }
    } else {
        std::cout << "No\n";
    }

    return 0;
}


Measured memory_bytes: 9636
#include <stdio.h>
int main(){
	int i,a,b,x,y;
	for(;;){
		scanf("%d",&i);
		if(i==0)break;
		x=0;y=0;
		for(; i>0; i--){
			scanf("%d %d",&a,&b);
			if(a>b)x+=a+b;
			if(b>a)y+=a+b;
			if(a==b){x+=a;y+=b;}
		}
		printf("%d %d\n",x,y);
	}
	return 0;
}

Measured memory_bytes: 600
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 1; i <= (n); i++)
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(),(x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size()) //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x)) //最大値を求める
#define MIN(x) *min_element(ALL(x)) //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define inf 2147483647 //int値の最大値
#define MOD 1000000007 //10^9+7:合同式の法
#define MAXR 100000 //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first //pairの一つ目の要素
#define S second //pairの二つ目の要素
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
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;
}
int gcd(int a, int b) {
    if (b==0) return a;
    else return gcd(b, a%b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int two(int n){
	ll ans=1;
	rep(i,n){
		ans*=2;
	}
	return ans;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);
    
    int b,f,r,v;
    int n;
    cin>> n;
    int A[5][4][11];

    rep(i,4)rep(j,3)rep(k,10)A[i][j][k]=0;
    
    rep(i,n){
        cin>>b>>f>>r>>v; A[b][f][r]+=v;
        }
        rep(a,4){
            if(a>1)cout<<"####################\n";
            rep(c,3){
                rep(d,10){
                   
                    cout<< " "<<A[a][c][d];

                }
                cout<<endl;
            }
        }


    
}


Measured memory_bytes: 3216
#include <iostream>
#include <math.h>
using namespace std;

int main(){
	int num ;
	cin >> num;
	for(int j = 1;j<= num; j++){
	double x[2],y[2],r[2],r2[2];
	for(int i =0;i<=1;i++){
		cin >> x[i];
		cin >> y[i];
		cin >> r[i];
	}
	double d;
	d = sqrt((x[0]-x[1])*(x[0]-x[1])+(y[0]-y[1])*(y[0]-y[1]));
	if((r[0]+r[1])<d) cout << 0 << endl;
	else if(r[0]+d < r[1]) cout << -2 << endl;
	else if(r[1]+d < r[0]) cout << 2 << endl;
	else cout << 1 << endl;
	}
	return 0;
}

Measured memory_bytes: 0
N = int(input())
s = list(map(int, input().split()))
ans = 0
for C in range(1,N):
    t = 0
    for x in range(C, N-1-C if (N-1)%C != 0 else N//2, C):
        t += s[x] + s[-x-1]
        ans = max(ans, t)
print(ans)

Measured memory_bytes: 14332
s=list(input())
K=int(input())
A=[chr(ord('a') + i) for i in range(26)]+[chr(ord('a') + i) for i in range(26)]
for i in range(len(s)):
  a=A.index(s[i])
  if i==len(s)-1:
    K%=26
    s[i]=A[a+K]
    break
  if s[i]=='a':
    continue
  if K>=26-a:
    K-=(26-a)
    s[i]='a'
  else:
    continue
print(*s,sep='')

Measured memory_bytes: 6968
#include <iostream>
#include<string>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<queue>
#include<deque>
#include<regex>
#include<stack>
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
#include<iomanip>
#define rep(i,n) for(int i=0;i<n;i++)

typedef int long long ll;
using namespace std;
typedef pair<int,int> P;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
const ll MOD=1e9+7;
static const int MAX = 100;
static const int INF = (1<<23);
template<class T> T gcd(T a, T b){return b? gcd(b,a%b) : a;}
template<class T> T lcm(T a,T b){return a / gcd(a,b)*b;}

int main(){
int n,m;
cin>>n>>m;
if(n==m){
    cout<<"Yes"<<endl;
}else{
    cout<<"No"<<endl;
}




return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <utility>

using namespace std;

#define REP(i,n)	for(int i=0, i##_len=(n); i<i##_len; ++i)

#define INF 		2000000007
#define MOD			998244353
#define MAX 		100005

typedef unsigned int 			uint;
typedef unsigned long long int	ull;
typedef long long int 			ll;


int main(){
	int A,P;cin>>A>>P;

	cout << ((A*3+P)/2) << endl;

	return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int N = 0;
    int A = 0, B = 0;
    int P[100];
    int q1 = 0, q2 = 0, q3 = 0;
    int ans = 0;

    //入力
    cin >> N >> A >> B;
    
    for(int i=0; i<N; i++){
        cin >> P[i];
    }
    
    //処理
    for(int i=0; i<N; i++){
        if(P[i]<=A){
            q1++;
        }
    }
    for(int i=0; i<N; i++){
        if(P[i]>A && P[i]<=B){
            q2++;
        }
    }
    for(int i=0; i<N; i++){
        if(P[i]>B){
            q3++;
        }
    }
    
    ans = q1;
    if(ans > q2){
        ans = q2;
    }
    if(ans > q3){
        ans = q3;
    }

    //出力
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <stack>
#define rep(i, s, g) for (i = s; i < g; i++)
using namespace std;

int main(void)
{
    int pages;

    cin >> pages;
    if(pages%2==1) cout << (pages/2)+1 << endl;
    else cout << pages/2 << endl;
}

Measured memory_bytes: 256
import static java.lang.System.out;
import java.util.Scanner;


public class Main {
    public static void main(String...args) {

        int S = new Scanner(System.in).nextInt();
        int timer = (60 * 60);
        int h = S / timer;
        int m = S % timer / 60;
        int s = S % timer % 60;
        out.println(h + ":" + m + ":" + s);
    }


}

Measured memory_bytes: 26216
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(v) v.begin(),v.end()
#define mem(arr) memset(arr, 0, sizeof(arr))
#define ff first
#define ss second
#define int long long int
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int N = 1e6 + 20;
vector<int> g[N];
vector<int> vis(N);
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int tc = 1;
    while(tc--){
        int n;
        cin >> n;
        string s;
        cout << "0\n";
        cout << flush;
        cin >> s;
        if(s == "Male"){
            int l = 0, r = n - 1;
            while(l <= r){
                int mid = (l + r) / 2;
                cout << mid << '\n';
                cout << flush;
                string str;
                cin >> str;
                if(str == "Vacant"){
                    return 0;
                }
                if(mid % 2){
                    if(str == "Female"){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }else{
                    if(str == "Male"){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
            }
        }else{
           int l = 0, r = n - 1;
            while(l <= r){
                int mid = (l + r) / 2;
                cout << mid << '\n';
                cout << flush;
                string str;
                cin >> str;
                if(str == "Vacant"){
                    return 0;
                }
                if(mid % 2){
                    if(str == "Male"){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }else{
                    if(str == "Female"){
                        l = mid + 1;
                    }else{
                        r = mid - 1;
                    }
                }
            } 
        }
    }
}

Measured memory_bytes: 32084
#include<stdio.h>
#include<math.h>
#include <stdlib.h>
int main()
{
  int a[5],i,min,min_n,total,loss;
  scanf("%d", &a[0]);
  scanf("%d", &a[1]);
  scanf("%d", &a[2]);
  scanf("%d", &a[3]);
  scanf("%d", &a[4]);
  min=10;
  min_n=0;
  for(i=0;i<5;i++){
    if(a[i]%10<min && a[i]%10!=0){
      min=a[i]%10;
      min_n=i;
    }
  }
  total=0;
  loss=0;
  for(i=0;i<5;i++){
    if(a[i]%10!=0 && i!=min_n){
      loss += 10-a[i]%10;
    }
    total += a[i];
  }
  
  printf("%d",total+loss);
  
  return 0;

}

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

string str;

int find_str(){
	if(str.find("the",0) != string::npos)
		return 1;

	if(str.find("this",0) != string::npos)
		return 1;

	if(str.find("that",0) != string::npos)
		return 1;

	return 0;
}

int main(){
	int i,j;
	while(getline(cin,str)){
		for(i = 0;i < 26;i++){
			for(j = 0;j < str.size();j++){
			if('a'<=str[j]&&str[j]<='z'){
				if(25<(int)str[j]+1-'a'){
					str[j] = 'a';
				}else{
					str[j] = str[j] + 1;
				}
			}
			}
			if(find_str()){
				cout<<str<<endl;
				break;
			}
		}
	}
	return 0;
}

Measured memory_bytes: 1172
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
xy = [LIST() for _ in range(N)]

def dist(p1, p2):
	return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)**(1/2)

ans = 0
for n in permutations(range(N)):
	tmp = 0
	for i in range(N-1):
		tmp += dist(xy[n[i]], xy[n[i+1]])
	ans += tmp
print(ans/factorial(N))


Measured memory_bytes: 5844
#include<stdio.h>
int bit[100001];
int n;
void add(int i,int x){
	while(i<=n){
		bit[i]+=x;
		i+=i&-i;
	}
}

int sum(int i){
	int s=0;
	while(i>0){
		s+=bit[i];
		i-=i&-i;
	}
	return s;
}

int main(){
	int i;
	scanf("%d",&n);
	for(i=0;i<=n;i++)bit[i]=0;
	for(i=0;i<n;i++){
		int a,b;
		scanf("%d %d",&a,&b);
		a--;b--;
		add(a,1);
		add(b+1,-1);
	}
	int ans=0;
	for(i=1;i<=n;i++)if(sum(i)>=i)ans=i;
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1412
#include"bits/stdc++.h"
using namespace std;
using ll=long long;
using ull=unsigned long long;
constexpr auto inf=static_cast<ll>(1e18);
template<typename T=ll>inline T in(){T ret;cin>>ret;return ret;}
template<typename T=ll>inline auto vec2(size_t h,size_t w,T v=T()){return vector<vector<T>>(h,vector<T>(w,v));}
inline void setp(int n){cout<<fixed<<setprecision(n);}
inline void delnl(){cin.ignore(numeric_limits<streamsize>::max(),'\n');}

int main()
{
    vector<bool>foo(101,false);
    for(ll i=1;i<=9;++i){
        for(ll j=1;j<=9;++j){
            foo[i*j]=true;
        }
    }
    cout<<(foo[in()]?"Yes":"No")<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>

using namespace std;

int kei(long long int n) {
	int a = 1;
	while (n/10 != 0) {
		a++;
		n /= 10;
	}
	return a;
}

int main() {
	long long int n;
	cin >> n;
	int aa = kei(n);
	for (long long int i = 1; i*i <= n; i++) {
		if (n % i == 0) {
			aa = min(aa, max(kei(i), kei(n/i)));
		}
	}
	cout << aa << endl;
	return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize(3, "Ofast", "inline")

#include <bits/stdc++.h>

#define start ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ll long long
#define int ll
#define ls st<<1
#define rs st<<1|1
#define pii pair<int,int>
#define rep(z, x, y) for(int z=x;z<=y;++z)
#define com bool operator<(const node &b)
using namespace std;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int maxn = (ll) 3e5 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f;
int T = 1;

void solve() {
    int n;
    cin >> n;
    cout << (1000 - n % 1000) % 1000;
}

signed main() {
    start;
    while (T--)
        solve();
    return 0;
}

Measured memory_bytes: 3652
/*
 * atcoder/dp_2nd/j.cpp
 */

// C++ 14
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstring> // memset
#include <cassert>

using namespace std;

#define ll long long
#define MOD 1000000007

#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)
template <class T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template <class T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }

const int MAX = 320;
ll N;
int A[4] = {0};
double E[MAX][MAX][MAX] = {0};

void input() {
  cin >> N;
  int a;
  loop(n,0,N) {
    cin >> a;
    A[a]++;
  }
}

// 期待値の初期条件
// E(I,J,K) = 0
// 期待値の遷移
// E(i,j,k) =
//   E(i,j,k) * (N-i-j-k)/N +
//   E(i-1,j,k) * i/N +
//   E(i+1,j-1,k) * j/N +
//   E(i,j+1,k-1) * k/N +
//   1
// N * E(i,j,k) - (N-i-j-k) * E(i,j,k) = i * E(i-1,j,k) + j * E(i+1,j-1,k) + k * E(i,j+1,k-1) + N
// (i+j+k) * E(i,j,k) = ...
// E(i,j,k) = { i * E(i-1,j,k) + j * E(i+1,j-1,k) + k * E(i,j+1,k-1) + N } / (i+j+k)

void solve() {
  // 各皿の枚数は過程でNまで達する可能性があるのでNまでループを回す必要がある.
  for (int k=0; k<=N; k++) for (int j=0; j<=N; j++) for (int i=0; i<=N; i++) {
    if (i+j+k == 0) { E[i][j][k] = 0; continue; }
    E[i][j][k] = N;
    if (i-1>=0) E[i][j][k] += i * E[i-1][j][k];
    if (j-1 >= 0) E[i][j][k] += j * E[i+1][j-1][k];
    if (k-1 >= 0) E[i][j][k] += k * E[i][j+1][k-1];
    E[i][j][k] *= 1.0 / (i+j+k);
    // cout << "(" << i << ", " << j << ", " << k << ") = " << E[i][j][k] << endl;
  }
  cout << E[A[1]][A[2]][A[3]] << endl;
}

int main() {
  cout.precision(15);
  input();
  solve();
  return 0;
}


Measured memory_bytes: 241792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(var, begin, end) for (int var = (begin); var < (end); var++)
#define RFOR(var, begin, end) for (int var = (begin) - 1; var >= (end); var--)
#define REP(var, length) FOR(var, 0, length)
#define RREP(var, length) RFOR(var, length, 0)
#define SORT(vector) sort(vector.begin(), vector.end())

const ll MOD = 1e9 + 7;
const int MAX = 1e6 + 1;

vector<int> memo;
vector<int> amt;

int func(int n) {
  if (memo[n] > 0) {
    return memo[n];
  }
  if (n == 0) {
    return 0;
  }
  int ret = 1e9;
  REP(i, amt.size()) {
    if (amt[i] > n) {
      continue;
    }
    ret = min(ret, func(n - amt[i]) + 1);
  }
  memo[n] = ret;
  return ret;
}

void solve(istream& cin, ostream& cout) {
  int n;
  cin >> n;
  memo = vector<int>(n + 1, -1);
  set<int> amount;

  for (int i = 1; i < MAX; i *= 6) {
    amount.insert(i);
  }

  for (int i = 1; i < MAX; i *= 9) {
    amount.insert(i);
  }

  for (set<int>::iterator itr = amount.begin(); itr != amount.end(); itr++) {
    amt.push_back(*itr);
  }

  cout << func(n) << endl;
}

#ifndef TEST
int main() {
  solve(cin, cout);
}
#endif


Measured memory_bytes: 5972
n,m=map(int,input().split())

M=[]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    M.append([a,b])
M.sort()
#print(M)

ans=0
nL=M[0][0]
nR=M[0][1]
for i in range(m):
    L=M[i][0]
    R=M[i][1]
    if nR<=L:
        ans+=1
        nL=L
        nR=R
    else:
        nL=L
        nR=min(nR,R)
ans+=1
print(ans)

Measured memory_bytes: 20072
#include <chrono>
#include <iostream>

using namespace std;
using namespace std::chrono;

int main() {
  auto start = high_resolution_clock::now();

  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int a, t;
  cin >> a >> t;
  cout << 2 * t - a << endl;

  cerr << "Total execution time : " << duration_cast<milliseconds>(high_resolution_clock::now() - start).count() << " ms" << endl;

  return 0;
}


Measured memory_bytes: 256
h,w,k=map(int,input().split())
pos=[0]*(h*w+1)
for i in range(h):
  tmp=list(map(int,input().split()))
  for j in range(w):
    pos[tmp[j]]=[i+1,j+1]
cs=[[0] for _ in range(k+1)]
for i in range(1,k+1):
  for j in range(1,(h*w-i)//k+1):
    x1,y1=pos[i+k*(j-1)][1],pos[i+k*(j-1)][0]
    x2,y2=pos[i+k*j][1],pos[i+k*j][0]
    cs[i].append(abs(y2-y1)+abs(x2-x1)+cs[i][j-1])
q=int(input())
for i in range(q):
  l,r=map(int,input().split())
  tmp=l%k
  if tmp==0:
    tmp=k
  l,r=(l-tmp)//k,(r-tmp)//k
  print(cs[tmp][r]-cs[tmp][l])

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

using namespace std;

#define LL long long
#define DD double
#define Pb push_back
#define Bp pop_back
#define Pf push_front
#define Fp pop_front
#define Ub upper_bound
#define Lb lower_bound
#define In insert
#define All(x) x.begin(), x.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define fast ios_base::sync_with_stdio(0);cin.tie(0)
#define X first
#define Y second
#define mx1 10
#define mx2 110
#define mx3 1010
#define mx4 10010
#define mx5 100010
#define mx6 1000010

typedef vector<LL> Vl;
typedef vector<DD> Vd;
typedef vector<bool> Vb;
typedef vector<Vl> VVl;
typedef pair<LL, LL> Pll;
typedef pair<DD, DD> Pdd;
typedef vector<Pll> Vpl;
typedef vector<Pdd> Vpd;
typedef queue<LL> Ql;
typedef stack<LL> Sl;
typedef deque<LL> Dl;

LL _set(LL N, LL pos) {return N = N | (1 << pos);}
LL _reset(LL N, LL pos) {return N = N & ~(1 << pos);}
bool _check(LL N, LL pos) {return (bool)(N & (1 << pos));}
bool _upper(char a) {return a >= 'A' && a <= 'Z';}
bool _lower(char a) {return a >= 'a' && a <= 'z';}
bool _digit(char a) {return a >= '0' && a <= '9';}

LL dx[] = {1, -1, 0, 0, -1, -1, 1, 1};
LL dy[] = {0, 0, 1, -1, -1, 1, -1, 1};

///**************************DONE****************************///

int main()
{
    int n;
    cin >> n;
    
    if(n % 1000)
        cout << 1000 - n % 1000 << '\n';
    else
        cout << 0 << '\n';
    return 0;
}


Measured memory_bytes: 3632
#include<stdio.h>
int main(){
  int i,j,v,k,N;
  int A[10000];
  scanf("%d",&N);
  for(i=0;i<N;i++){
    scanf("%d",&A[i]);
  }
  for(i=0;i<N;i++){
    if(i==N-1)
      printf("%d\n",A[i]);
    else
      printf("%d ",A[i]);
  }
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while(j>=0 && A[j]>v){
      A[j+1]=A[j];
      j--;
      A[j+1]=v;
    }
    for(k=0;k<N;k++){
      if(k==N-1)
	printf("%d\n",A[k]);
      else
	printf("%d ",A[k]);
    }
  }
  return 0;
}

  



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


int N,M,X,Y;

int main(){
	cin >> N >> M >> X >> Y;
	int x[N+1],y[M+1];
	int maxx=X, miny=Y;
	for(int i=0;i<N;i++){
		cin >> x[i];
		if(maxx < x[i]) maxx=x[i];
	}
	for(int i=0;i<M;i++){
		cin >> y[i];
		if(miny > y[i]) miny=y[i];
	}

	if(maxx < miny) cout << "No War" << endl;
	else cout << "War" << endl;
	return 0;
}


Measured memory_bytes: 256
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;


public class Main {
	public static void main(String[] args) {

		Scanner sc=new Scanner(System.in);

		int h=sc.nextInt();
		int w=sc.nextInt();


		String[][] field=new String[h][w];
		
		Queue<Point> q=new LinkedList<Point>();

		for(int i=0;i<h;i++) {

			String buf=sc.next();
			

			field[i]=buf.split("");
			
			if(buf.contains("#")) {
				
				for(int j=0;j<w;j++) {
					if(field[i][j].equals("#")) {
						q.add(new Point(i,j));
					}
				}
				
			}
			
			

		}
		
		
		//8方向を下から右回り。
		int[] vy= {1,1,0,-1,-1,-1,0,1};
		int[] vx= {0,1,1,1,0,-1,-1,-1};

		while(!q.isEmpty()) {
			
			Point tyakumokuBomb=q.poll();
			
			
			for(int j=0;j<8;j++) {
				int nextY=tyakumokuBomb.y+vy[j];
				int nextX=tyakumokuBomb.x+vx[j];
				
				if(isoutoffiled(nextY, nextX, h, w)) {
					continue;
				}
				
				if(field[nextY][nextX].equals(".")) {
					field[nextY][nextX]=String.valueOf(1);
					
				}else if(!field[nextY][nextX].equals("#")) {
					int numofbomb=Integer.parseInt(field[nextY][nextX])+1;
					field[nextY][nextX]=String.valueOf(numofbomb);
				}
				
			}
		}
		
		for(int i=0;i<h;i++) {
			for(int j=0;j<w;j++) {
				
				if(field[i][j].equals(".")) {
					System.out.print(0);
				}else {
					System.out.print(field[i][j]);
				}
			}
			
			System.out.println();
		}
		
		sc.close();


	}
	
	public static boolean isoutoffiled(int nextY,int nextX,int h,int w) {
		
		return nextY<=-1 || nextY>=h || nextX<=-1 || nextX>=w;
		
	}
	



}

class Point{
	
	int y;
	int x;
	
	public Point(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
	
	
	
}


Measured memory_bytes: 23892
#include <stdio.h>

int main()
{
	int n, x, m;
	scanf("%d %d", &n, &x);
	int min = 1000;
	for(int i=1; i<=n; ++i){
		scanf("%d", &m);
		x -= m;
		min = m < min ? m : min;
	}
	printf("%d", n + x / min);
	return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<cctype>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;

inline LL read() {
	LL x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
	for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}



int main() {
//	freopen("a.in", "r", stdin);
	LL k = read(), a = read(), b = read();
	if (a + 2 >= b) {
		cout << k + 1; return 0;
	}
	if (k <= a) {
		cout << k + 1; return 0;
	}
	LL ans = a;
	k -= a - 1;
	ans += (k / 2) * (b - a);
	if (k & 1) ans ++;
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
/// You just can't beat the person who never gives up
/// ICPC next year

#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6+5 ;

int n ,a[N] ,b[N] ;
vector<int> xra ,xrb ;
/**
    a(i+k) ^ x = b(i)
    a(i+k+1) ^ x = b(i+1)
    a(i+k) ^ a(i+k+1) = b(i) ^ b(i+1)
**/

int F[N];
vector<int> pat ,str ;
int getNextLen(int len, int c){
  while(len>=pat.size() || len && c != pat[len])
    len = F[len-1];
  if(c == pat[len]) ++len;
  return len;
}

void computeF(){
  for(int i = 1 ; i<pat.size(); ++i)
    F[i] = getNextLen(F[i-1], pat[i]);
}

vector<int> search(){
  int len = 0;
  vector<int> res;
  for(int i = 0 ; i<str.size() ; ++i){
    len = getNextLen(len, str[i]);
    if(len==pat.size()) res.push_back(i-len+1);
  }
  return res;
}
void kmp(vector<int> aa,vector<int> bb){
    pat = aa ;
    str = bb ;
    computeF();
    auto ans = search();
    vector<pair<int,int>> out ;
    for(auto go:ans) if(go<n) out.push_back({go,b[0]^a[go]});
    sort(out.begin(),out.end());
    for(auto go:out) printf("%d %d\n",go.first,go.second);
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;++i){
        scanf("%d",a+i);
        if(i) xra.push_back(a[i]^a[i-1]);
    }
    for(int i=n;i<n+n+n;++i){
        a[i] = a[i-n] ;
        xra.push_back(a[i]^a[i-1]);
    }
    for(int i=0;i<n;++i){
        scanf("%d",b+i);
        if(i) xrb.push_back(b[i]^b[i-1]);
    }
    kmp(xrb,xra);
    return 0;
}


Measured memory_bytes: 27116
a = int(input())
x1 = list(map(int,input().split()))
x2 = list(map(int,input().split()))
ans = 0
num1 = 0
for i in range(a):
  num1 += x1[i]
  num2 = 0
  for j in range(i,a):
    num2 += x2[j]
  num3 = num1 + num2
  ans = max(ans,num3)
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#include<chrono>
using namespace std;
using ll = long long;

int main() {
  string S;
  cin >> S;
  int count = 0;
  string a, b = "";
  for (int i = 0; i < S.size(); i++) {
    a += S[i];
    if (a != b) {
      b = a;
      count++;
      a = "";
    }
  }
  cout << count << endl;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int) (n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int) (n); i++)
#define _GLIBCXX_DEBUG

int l, r, d, ans=0;
int main(){
    cin >> l >> r >> d;
    for(int i = l; i <= r; i++){
        if(i%d == 0) ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
template<typename A, typename B> inline bool chmax(A &a, B b) { if (a<b) { a=b; return 1; } return 0; }
template<typename A, typename B> inline bool chmin(A &a, B b) { if (a>b) { a=b; return 1; } return 0; }
typedef long long ll;
typedef pair<int, int> pii;
const ll INF = 1e9+100;
const ll MOD = 1e9+7;
const bool debug = 0;
//-----------------------------------------------//

int N, C;
int s[112345], t[112345], c[112345];
int imos[212345];
int sum[212345];

int main() {
	cin >> N >> C;
	REP(i, N) scanf("%d %d %d", s + i, t + i, c + i);
	
	REP(i, C) {
		memset(imos, 0, sizeof(imos));
		
		REP(j, N) if (i == c[j] - 1) imos[s[j]*2 - 1]++, imos[t[j]*2 + 1]--;
		REP(j, 212345-1) {
			imos[j + 1] += imos[j];
			sum[j] += imos[j] >= 1;
		}
	}
	
	cout << *max_element(sum, sum + 212345) << endl;
	
	return 0;
}

Measured memory_bytes: 3072