akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define fi first
#define se second
#define rep(i,s,n) for(int i = s;i<n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
#define endl '\n'
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0)
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
const ll MOD=1000000007,INF=1ll<<60;
 
int N,M,A,B,C,K,Q;
string s;
int sum[100010];

signed main() {
    IOS();
    cin>>N>>Q>>s;
    rep(i,0,N-1){
        if(s[i]=='A'&&s[i+1]=='C'){
            sum[i+1]++;
            sum[i+2]++;
        }
    }
    rep(i,0,N){
        sum[i+1]+=sum[i];
    }
    
    while(Q--){
        int l,r;
        cin>>l>>r;
        int tmp=sum[r]-sum[l-1];
        if(r!=N)if(s[r-1]=='A'&&s[r]=='C')tmp--;
        if(l!=1)if(s[l-1]=='C'&&s[l-2]=='A')tmp--;
        cout<<tmp/2<<endl;
    }
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    
    return 0;
}

Measured memory_bytes: 1872
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <limits.h>
using namespace std;

int main(){
  int N, check = 0;
  string S ;
  cin >> N >> S ;
  if(N%2==1) check = 1 ;
  N /= 2 ;
  for(int i=0;i<N;i++){
    if(S[i] != S[i+N]) check = 1 ;
  }  
  if(check==1){
    cout << "No" << endl ;
  }  
  else{
    cout << "Yes" << endl ;
  }  
  return 0 ;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
class Main{
    public static void main(String[] a){
        for(int i = 1; i < 10; i ++){
            for(int j = 1; j < 10; j ++){
                int f = i*j;
                System.out.println(i + "x" + j + "=" + f );
            }    
        }
         
 
    }
}

Measured memory_bytes: 24152
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
using namespace std;

int main(){
  char s[128];
  while(fgets(s, sizeof(s), stdin)){
    rep(i, sizeof(s)) if(s[i] == '\n') s[i] = '\0';
    if(strcmp(s, ".") == 0) break;
    bool f = true;
    stack<char>st;
    for(int i = 0; s[i] != '\0'; ++i){
      if(s[i] == '(' || s[i] == '[') st.push(s[i]);
      else if(s[i] == ')' || s[i] == ']'){
	if(st.empty()){ f = false;break;}
	else{
	  if(s[i] == ')' && st.top() == '(') st.pop();
	  else if(s[i] == ']' && st.top() == '[') st.pop();
	  else {f = false;break;}
	}
      }
    } 
    if(f && st.empty()) puts("yes");
    else puts("no");
  }
  return 0;
}

Measured memory_bytes: 1124
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define ll long long
#define pi pair<int,int>
#define pl pair<ll,ll>
#define pd pair<double,double>
#define ld long double
#define pld pair<ld,ld>
#define lg length()
#define sz size()
#define vi vector<int>
#define vl vector<ll>
#define vp vector<pi>
#define vpl vector<pl>
#define pb push_back
#define INF 1000000005
#define LINF 1000000000000000005
using namespace std;
const int maxn = 1e5 + 100;
ll dp[maxn];
int32_t main()
{
	ios_base::sync_with_stdio(0); cin.tie(); cout.tie();
#ifdef LOCAL_DEFINE
	ifstream cin("input.txt");
#endif
	int N, W;
	cin >> N >> W;
	
	ll w, v;
	cin >> w >> v;
	// TODO how about j is larger than j??
	// j is exact j
	for (int i = 0; i < maxn; i++)dp[i] = INF;
	dp[v] = w;
	dp[0] = 0;
	// here is a special v
	int ans = v;
	for (int i = 2; i <= N; i++)
	{
		cin >> w >> v;
		for (int j = 1e5; j >= v; j--)
		{
			dp[j] = min(dp[j], dp[j - v] + w);
			if (dp[j] <= W) ans = max(j, ans);
		}
	}
	cout << ans << "\n";
}


Measured memory_bytes: 1024
#include<iostream>
#include<cmath>
#include<algorithm>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	int n;
	pair<long double,long double> p[4],vec[2];
	cin>>n;
	rep(j,n){
		rep(i,4)cin>>p[i].first>>p[i].second;
		rep(i,2){
			vec[i].first=p[i*2].first-p[i*2+1].first;
			vec[i].second=p[i*2].second-p[i*2+1].second;
		}
		double check=vec[0].first*vec[1].second-vec[0].second*vec[1].first;
		if(check==0)cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

Measured memory_bytes: 1228
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = double;
#define fi first
#define se second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define siz(v) (ll)(v).size()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define repi(i,x,n) for(ll i=x;i<(ll)(n);i++)
typedef pair<int,int> P;
typedef pair<ll,ll> PL;
const ll mod = 1000000007;
const ll INF = 1000000099;
vector<ll> dx={-1,1,0,0},dy={0,0,-1,1};
//cin.tie(0);
//ios::sync_with_stdio(false);



signed main(){
    ll n,Q;cin>>n>>Q;
    vector<vector<ll>> e(n+1,vector<ll>(0));
    vector<ll> node(n+1,0);
    vector<ll> ans(n+1,0);
    vector<bool> f(n+1,false);

    rep(i,n-1){
        ll a,b;cin>>a>>b;
        e.at(a).pb(b);
        e.at(b).pb(a);
    }

    rep(i,Q){
        ll p,x;cin>>p>>x;
        node.at(p)+=x;
    }

    queue<ll> q;
    q.push(1);
    q.push(0);

    while(!q.empty()){
        ll v=q.front();q.pop();
        ll score=q.front();q.pop();

        score+=node.at(v);
        f.at(v)=true;
        ans.at(v)=score;

        for(int i=0;i < siz(e.at(v));i++)
        {
            if(!f[e[v][i]]){
                q.push(e[v][i]);
                q.push(score);
            }
        }
    }

    for(int i=1;i<=n;i++){
        cout<<ans[i]<<(i==n ? '\n':' ');
    }

}

Measured memory_bytes: 21104
#include<cstdio>
int p[1<<17],s,i,n;
main(){for(i=2;i<1<<17;i++)for(s=2;!p[i]&&i*s<1<<17;p[i*s++]++);for(;scanf("%d",&n),n;printf("%d\n",s))for(i=2,s=0;!p[i]?s+=i,n--:n,n;i++);}

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

int main() {
  int n, k; cin >> n >> k;
  vector<int> v(n);
  for (int i = 0; i < n; i++) {
    cin >> v.at(i);
  }
  int cnt = 0;
  int right = 0;
  while (true) {
    if (cnt == 0) {
      right += k;
      cnt++;
    } else {
      right += k - 1;
      cnt++;
    }

    if (right >= n)
    break;
  }
  cout << cnt << endl;
}


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

#define ms(a,b) memset(a, b, sizeof(a))
#define rep(a,b,c) for(int a = (int)(b); a < (int)(c); a++)
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define m_p(a,b) make_pair(a, b)
#define lson l,mid,o << 1
#define rson mid + 1,r,o << 1 | 1
#define ls o << 1
#define rs o << 1 | 1
#define inf 0x3f3f3f3f

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair<int,int> pii;

inline bool isdigit(char& ch) {
	return ch >= '0' && ch <= '9';
}
template<class T>
void read(T &x) {
	x = 0;
	ll f = 1;char ch = getchar();
	for (;!isdigit(ch);ch = getchar()) 
		if (ch == '-') f = -1;
	for (; isdigit(ch);ch = getchar())
		x = (x << 1) + (x << 3) + ch - '0';
	x *= f;
}
template<class T>
inline void write(T x) {
	if (x == 0) {putchar('0');return ;}
	if (x < 0) {putchar('-');x = -x;}
	int _stk[65],_top = 0;
	for (;x;x /= 10) _stk[++_top] = x % 10 + 48;
	for (;_top;_top--)putchar(_stk[_top]);
}

int k;
string s = "ACL";
int main () {
	cin >> k;
	while(k--)
		cout << s;
	return 0;
}

Measured memory_bytes: 3592
from sys import exit
import math
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

x,n = mi()
p=li()
p.sort()

if n==0:
    print(x)
    exit()

dis=100000
q=0
for i in range(-200,200,1):
    if i in p:
        continue
    if abs(i-x) < dis:
        dis = abs(i-x)
        q=i
print(q)

Measured memory_bytes: 9196
#include <cstdio>
#include <cstring>
#include <cmath>
#include <map>
#include <stack>
#include <algorithm>
using namespace std;
const int Max = 2e5;

int n, m, a[55], x, y;

int main()
{
	scanf ("%d %d", &n, &m);
	for (int i = 1; i <= m; i++){
		scanf ("%d %d", &x, &y);
		a[x]++;
		a[y]++;
	}
	for (int i = 1; i <= n; i++){
		printf ("%d\n", a[i]);
	}
}

Measured memory_bytes: 128
N = int(input())

a = [list(map(int, input().split())) for _ in range(N)]

a = sorted(a, key=lambda x: x[1])

hours = 0

ans = "Yes"
for pair in a:
    hours += pair[0]
    deadline = pair[1]


    if hours > deadline:
        ans = "No"
        break

print(ans)

Measured memory_bytes: 48600
#include<bits/stdc++.h>
#define tcn cin.tie(0);
#define tct cout.tie(0);
#define pb push_back
#define ll long long
#define fr first
#define se second
#define TIME ios_base::sync_with_stdio(0);
using namespace std;

const long long N = 2e3 + 7;
const ll mod = 1e6 + 7;
ll n , m , a , b , c ,d ,cnt ;
long double p = 3.141592653589793;
string s;
char ch;
vector<int>v ,v1;
map<int , int>mp;
int main()
{
    TIME tcn tct
    cin >> m >> n;
    for( int i = 0;i < n;i ++ )
        cin >> a , cnt+=a;
    if( cnt > m )
        cout << -1;
        else
            cout << m - cnt;
}


Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <cmath>
int main()
{
    using namespace std;
    int a, b;
    cin >> a >> b;
    if (a == b)
    {
        for (int i = 0; i < a; i++)
        {
            cout << a;
        }
        
    }
    else
    {
        int resMax, resMin;
        resMax = max(a, b);
        resMin = min(a, b);
        for (int i = 0; i < resMax; i++)
        {
            cout << resMin;
        }
        
    }
    return 0;
}

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

int main()
{
  ll n;
  cin >> n;
  vector<ll> as(n);
  rep(i, n) cin >> as[i];

  vector<bool> v(1000001);

  sort(as.begin(), as.end());
  ll ans = 0;
  rep(i, n)
  {
    ll a = as[i];
    if (i == 0)
    {
      if (a == as[i + 1])
      {
        continue;
      }
    }
    else if (i == n - 1)
    {
      if (a == as[i - 1])
      {
        continue;
      }
    }
    else
    {
      if (a == as[i - 1] || a == as[i + 1])
      {
        if (a == as[i + 1])
          continue;
        ll num = a;
        while (num <= 1000000)
        {
          v[num] = true;
          num += a;
        }
        continue;
      }
    }
    if (v[a])
      continue;

    ans++;

    ll num = a;
    while (num <= 1000000)
    {
      v[num] = true;
      num += a;
    }
  }

  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 4840
#include <stdio.h>
int main(void){
    // Your code here!
    int a,b,c;
    
    scanf("%d",&a);
    scanf("%d",&b);
    scanf("%d",&c);
    
    if(a+b+c>=22)
    printf("bust");
    if(a+b+c<=21)
    printf("win");
    
    return 0;
}


Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N, K = map(int, input().split())
a = [0] + list(map(int, input().split()))
inf = 10 ** 12
dp = [[[inf] * (N + 1) for _ in range(K + 1)] for _ in range(N + 1)]
dp[0][0][0] = 0
for i in range(N):
  for j in range(K + 1):
    for k in range(N + 1):
      if dp[i][j][k] == inf: continue
      x = max(0, a[i + 1] - a[k])
      dp[i + 1][j][i + 1] = min(dp[i + 1][j][i + 1], dp[i][j][k] + x)
      if j < K: dp[i + 1][j + 1][k] = min(dp[i + 1][j][k], dp[i][j][k])
#print(dp)
res = inf
for j in range(K + 1): res = min(res, min(dp[-1][j]))
print(res)

Measured memory_bytes: 255112
def main():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    a_sum = [0]
    b_sum = [0] 

    max_counter = 0

    j = m

    for i in range(n):
        a_sum.append(a_sum[i] + a[i])

    for i in range(m):
        b_sum.append(b_sum[i] + b[i])

    for i in range(n + 1):
        if a_sum[i] > k:
            break

        while k < a_sum[i] + b_sum[j]:
            j -= 1
        
        max_counter = max(max_counter, i + j)

    print(max_counter)

if __name__ == '__main__':
    main()

Measured memory_bytes: 47480
using System.Collections.Generic;
using System;

public class hello
{
    public static void Main()
    {
        var s = Console.ReadLine().Trim();
        s = s.Replace("chicken", "c");
        s = s.Replace("egg", "e");
        getAns(s);
    }
    static void getAns(string s)
    {
        var res = new List<string>();
        var sL = s.Length;
        var t = "" + s[0];
        var pre = s[0];
        var maxL = 0;
        var ans = '@';
        for (int i = 1; i < sL; i++)
        {
            if (s[i] == pre)
            {
                if (t.Length > maxL)
                {
                    ans = t[t.Length - 1];
                    maxL = t.Length;
                }
                t = "" + s[i];
            }
            else t += s[i];
            pre = s[i];
        }
        if (t.Length > maxL) ans = t[t.Length - 1];
        Console.WriteLine(ans == 'e' ? "egg" : "chicken");
    }
}



Measured memory_bytes: 17904
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
 
string divide[4]={"dream","dreamer","erase","eraser"};
 
int main(){
  string s;
  cin >> s;
  reverse(s.begin(),s.end());
  for(int i=0;i<4;i++) reverse(divide[i].begin(),divide[i].end());
  
  bool can=true;
  for(int i=0;i<s.size();){
    bool can2=false;
    for(int j=0;j<4;++j){
      string d=divide[j];
      if(s.substr(i,d.size())==d){
        can2=true;
        i+=d.size();
      }
    }
    if(!can2){
      can=false;
      break;
    }
  }
  if(can){cout << "YES" << endl;}
  else{cout << "NO" << endl;}
  return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <utility>
#include <iomanip>
#include <tuple>
#include <cstdio>
#include <cmath>
using namespace std;
using ll = long long;
const int INF = 1e9;

int n;
int ans = INF;
vector<int> abc, l;
vector<pair<int, int>> now(4, pair<int, int>(0, 0));

void dfs(int depth) {
    if (depth == n) {
        int tmp = 0;
        for (int i = 0; i < 3; ++i) {
            if (now[i].second == 0) return;
            tmp += abs(abc[i] - now[i].first) + 10 * (now[i].second - 1);
        }
        ans = min(ans, tmp);
    } else {
        for (int i = 0; i < 4; ++i) {
            now[i].first += l[depth];
            now[i].second +=1;
            dfs(depth+1);
            now[i].first -= l[depth];
            now[i].second -= 1;
        }
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < 3; ++i) {
        int inp; cin >> inp;
        abc.push_back(inp);
    }

    for (int i = 0; i < n; ++i) {
        int inp; cin >> inp;
        l.push_back(inp);
    }
    dfs(0);
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){

  long long a,b,c,d;
  cin>>a>>b>>c>>d;
  
  long long x=a*c;
  long long y=b*d;
  long long z= a*d;
  long long z1= b*c;
  
  cout<<max(max(max(x,y),z),z1);
  
  
return 0;
}

Measured memory_bytes: 3556
#include <bits/stdc++.h>
using namespace std;
int H,W,ans,cnt;
char c;
int main()
{
	scanf("%d %d",&H,&W);
	for(int i=1;i<=H;i++)
	{
		for(int j=1;j<=W;j++)
		{
			scanf(" %c",&c);
			if(c=='#')
				cnt++;
		}
	}
	ans=H+W-1;
	//~ printf("%d %d\n",ans,cnt);
	
	if(cnt==ans)
	{
		printf("Possible");
		return 0;
	}
	printf("Impossible");

}


Measured memory_bytes: 256
// Written By Mahtab Tanim
#include<bits/stdc++.h>
using namespace std;
#define MP ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define nl "\n"
#define End return 0
#define ll long long int
#define mp make_pair
#define pb push_back
#define ull unsigned long long int
#define pi acos(-1)
#define forn(i,a,b) for (int i=a;i<=b;i++)
#define PI acos(-1)
int main()
{
double r;
cin>>r;
printf("%.4lf",r*3.1415*2);
End;
}


Measured memory_bytes: 3784
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  int l=a+b;
  int r=c+d;
  if(l>r)
    cout<<"Left"<<endl;
  else if(r>l)
    cout<<"Right"<<endl;
  else
    cout<<"Balanced"<<endl;
  
  
}

Measured memory_bytes: 3592
import std.stdio;
import std.string;
import std.conv;
import std.algorithm;

void main() {
  int N = to!int(readln.chomp);
  int[] arr = to!(int[])(readln.chomp.split);
  sort(arr);
  reverse(arr);
  int A, B;
  A = B = 0;

  for (int i = 0; i < N; i++) {
    (i & 1 ? B : A) += arr[i];
  }

  writeln(A - B);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define long long long
#define read cin >>
#define echo cout <<
#define fin << endl
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = (0); i < (n); ++i)

// for debug macro
bool global_debug_flag = false;
#define DEBUG(val) \
  if (global_debug_flag) cout << #val << " = " << val << endl

int main() {
  string s;
  cin >> s;
  reverse(s.begin(), s.end());
  vector<vector<int>> data(2, vector<int>(s.length() + 1));
  int x = s[0] - '0';
  data[0][0] = x;
  data[1][0] = 10 - x;
  FOR(i, 0, s.length() - 1) {
    int now = s[i + 1] - '0';
    data[0][i + 1] = min(data[0][i] + now, data[1][i] + now + 1);
    data[1][i + 1] = min(data[0][i] + 10 - now, data[1][i] + 10 - (now + 1));
  }

  REP(j, s.length()) {
    REP(i, 2) {
      DEBUG(i);
      DEBUG(j);
      DEBUG(data[i][j]);
    }
  }
  cout << min(data[0][s.length() - 1], data[1][s.length() - 1] + 1) << endl;
}


Measured memory_bytes: 13060
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H, W, K;
	cin >> H >> W >> K;
	vector<int> dp(W);
	vector<int> ndp = dp;
	dp[0] = 1;
	bool ok;
	int nk;
	for (int i = 0; i < H; i++) {
		ndp.clear();
		ndp.resize(W, 0);
		for (int j = 0; j < (1 << (W - 1)); j++) {
			ok = true;
			for (int jj = 0; jj < W - 2; jj++) {
				if (((j & (1 << jj)) != 0) && ((j & (1 << (jj + 1))) != 0)) {
					ok = false;
					break;
				}
			}
			if (ok) {
				//if (j == 1)cerr << "OK" << endl;
				for (int k = 0; k < W; k++) {
					nk = k;
					if (k > 0 && ((j & (1 << (k - 1))) != 0)) {
						nk = k - 1;
					}
					if (k < W - 1 && ((j & (1 << (k))) != 0)) {
						nk = k + 1;
					}
					/*if (j == 1 && k == 0) {
						cerr << "nk = " << nk << endl;
					}*/
					ndp[nk] = (ndp[nk] + dp[k]) % MOD;
				}
			}
		}
		dp = ndp;
	}
	cout << dp[K - 1] << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define all(v) v.begin(),v.end()
#define PB push_back
#define PI 3.1415926535897932384626433832795
#define what(x) cout<<#x<<" is "<<x<<endl;
using namespace std;


template <typename A, typename B>
string to_string(pair<A, B> p);

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);

string to_string(const string& s) {
  return '"' + s + '"';
}

string to_string(const char* s) {
  return to_string((string) s);
}

string to_string(bool b) {
  return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}

template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}

template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " + to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
//#define LOCAL
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

ll powmod(ll a,ll b,ll mod) {
    ll res=1;a%=mod;
    //assert(b>=0);
    for(;b;b>>=1){
        if(b&1)res=res*a%mod;a=a*a%mod;
    }
    return res;
}

void solve(){
	ll n;
	cin>>n;
	cout<<(1000-((n%1000==0)?1000:(n%1000)))<<'\n';
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int tc=1;
    // cin>>tc;
    while(tc--)solve();
}


Measured memory_bytes: 3592
#include <stdio.h>

int main(){
  long long int N, k=1LL, l=0LL, T=0LL;
  long long int X, Y, M, S=0LL;
  long long int U[200000];
  
  scanf("%lld %lld %lld", &N, &X, &M);
  for(int i=0;i<=(int)M;i++){
    U[i]=0LL;
  }
  while(k<=N){
    S+=X;
    U[(int)X]=k;
    X=(X*X)%M;
    if(X==0LL) break;
    if(U[(int)X]>0LL){
      Y=X;
      do{
        T+=Y;
        Y=(Y*Y)%M;
        l++;
      }while(X!=Y);
      long long int p=(N-k)/l;
      S+=T*p;
      long long int q=(N-k)%l;
      while(q>0LL){
        S+=X;
        X=(X*X)%M;
        q--;
      }
      break;
    }
    k++;
  }
  printf("%lld\n", S);
  return 0;
}

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

int main()
{
	int a,b,c,d,sum=0;
	char s[100];
    cin>>a>>b;
    if(a%500<=b)
        cout<<"Yes";
    else
    {
        cout<<"No";
    }
    
	
	
	return 0;
}
	

Measured memory_bytes: 764
#include <stdio.h>
#define MAX 100
int main(){
  int i,j,h,h1,w,w1,l,l1,l2;
  while(1){
      scanf("%d %d",&h,&w);
      if(h==0 & w==0){
        break;
      }

      l=h*h+w*w;
      l1=150*150;
        for(h1=1;h1<150;h1++){
          for(w1 =150;w1 >=h1+1;w1--){
            l2=h1 *h1 +w1 *w1 ;
            if(l<l2 && l1>l2 || l==l2 && h<h1 && l1>l2)
            {
              l1=l2;
              i=h1;
              j=w1;
            }
      }
    }
        printf("%d %d\n",i,j);
  }

  return 0;
}

Measured memory_bytes: 600
#include<stdio.h>
#include<string.h>

int main(){
	int w[11],k[11];
	int a,b;
	for(a=0;a<10;a++){
		scanf("%d",&w[a]);
	}
	for(a=0;a<10;a++){
		scanf("%d",&k[a]);
	}
	for(a=0;a<10;a++){
		for(b=a+1;b<10;b++){
			if(w[a]>=w[b])w[10]=w[a],w[a]=w[b],w[b]=w[10];
			if(k[a]>=k[b])k[10]=k[a],k[a]=k[b],k[b]=k[10];
		}
	}
	printf("%d %d\n",w[9]+w[8]+w[7],k[9]+k[8]+k[7]);
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<stdio.h>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<map>
#include<string.h>
#include<complex>
#include<math.h>
#include<queue>
#include<time.h>
using namespace std;
typedef long long int llint;
typedef pair<int, int> pint;
typedef pair<llint, llint> pllint;
typedef vector<int> vint;
typedef vector<llint> vllint;
typedef vector<pint> vpint;
typedef vector<string> vstring;
typedef vector<pair<llint, llint>> vpllint;
typedef vector<vector<int>> vvint;
typedef vector<vector<llint>> vvllint;
typedef vector<vector<pint>> vvpint;
typedef vector<bool> vbool;
#define rep(i,n) for(int i=0;i<n;i++)
#define drep(i,n) for(int i=n-1;0<=i;i--)
#define yes(ans) if(ans)cout<<"yes"<<endl;else cout<<"no"<<endl;
#define Yes(ans) if(ans)cout<<"Yes"<<endl;else cout<<"No"<<endl;
#define YES(ans) if(ans)cout<<"YES"<<endl;else cout<<"NO"<<endl;
#define POSSIBLE(ans) if(ans)cout<<"POSSIBLE"<<endl;else cout<<"IMPOSSIBLE"<<endl;
#define Pi 3.1415926535897932384626
#define mod llint(1e9+7)

class UnionFind {
public:
	//親の番号を格納する。親だった場合は-(その集合のサイズ)
	vector<int> Parent;

	//作るときはParentの値を全て-1にする
	//こうすると全てバラバラになる
	UnionFind(int N) {
		Parent = vector<int>(N, -1);
	}

	//Aがどのグループに属しているか調べる
	int root(int A) {
		if (Parent[A] < 0) return A;
		return Parent[A] = root(Parent[A]);
	}

	//自分のいるグループの頂点数を調べる
	int size(int A) {
		return -Parent[root(A)];//親をとってきたい
	}

	//AとBをくっ付ける
	bool connect(int A, int B) {
		//AとBを直接つなぐのではなく、root(A)にroot(B)をくっつける
		A = root(A);
		B = root(B);
		if (A == B) {
			//すでにくっついてるからくっ付けない
			return false;
		}

		//大きい方(A)に小さいほう(B)をくっ付けたい
		//大小が逆だったらひっくり返しちゃう。
		if (size(A) < size(B)) swap(A, B);

		//Aのサイズを更新する
		Parent[A] += Parent[B];
		//Bの親をAに変更する
		Parent[B] = A;

		return true;
	}
};

//aとbの最大公約数を求めるよ
long long GCD(long long a, long long b) {
	if (b == 0) return a;
	else return GCD(b, a % b);
}

// 返り値: a と b の最大公約数
// ax + by = gcd(a, b) を満たす (x, y) が格納される
long long extGCD(long long a, long long b, long long& x, long long& y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return a;
	}
	long long d = extGCD(b, a % b, y, x);
	y -= a / b * x;
	return d;
}

bool check(pllint a, pllint b) {
	return a > b;
}

// mod. m での a の逆元 a^{-1} を計算する
long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

//aCbを1000000007で割った余りを求める
llint convination(llint a, llint b) {
	llint ans = 1;
	for (llint i = 0; i < b; i++) {
		ans *= a - i;
		ans %= 1000000007;
	}
	for (llint i = 1; i <= b; i++) {
		ans *= modinv(i, 1000000007);
		ans %= 1000000007;
	}
	return ans;
}

//aのb乗をmodで割った余りを求める
llint power(llint a, llint b) {
	if (b == 1)return a;
	if (b == 0)return 1;
	llint tmp = power(a, (llint)b / 2);
	tmp *= tmp;
	tmp %= mod;
	if (b % 2 == 1) {
		tmp *= a;
		tmp %= mod;
	}
	return tmp;
}

int main() {
	int a, b;
	cin >> a >> b;
	cout << (llint)a * b / GCD(a, b) << endl;
	return 0;
}

Measured memory_bytes: 256
const bool TEST=1;
#include<iostream>
#include<cctype>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<cctype>
#include<cstring>
#include<utility>
#include<cmath>
#include<sstream>
#include<stack>
const int inf=0x7fffffff;
#define IF if(TEST)
#define FI if(!TEST)
#define gts(s) fgets((s),sizeof(s),stdin)
#define ALL(s) (s).begin(),(s).end()
#define MK(a,b) make_pair((a),(b))
typedef long long int LL;
typedef unsigned int U;
typedef unsigned long long ULL;
using namespace std;
typedef pair<int,int> Point;
template <typename T>
void pA(T *begin,int n){ for(int i=0;i<n;i++){ cout<<*(begin++); } printf("\n"); }
void sol(){
	ULL x;
	cin>>x;
	ULL r=x%11;
	if(r==0);
	else if(r<=6)r=1;
	else r=2;
	cout<<(x/11)*2+r<<endl;
}
int main()
{
	sol();
	return 0;
}
//C.cc
//generated automatically at Sat Jan 28 20:21:02 2017
//by xsthunder


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

int main()
{
	int a,b;
	scanf("%d %d",&a,&b);
	int mid = a+b;
	if(mid>9)printf("error");
	else printf("%d",mid);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void solve()
{
	int N, X;
	cin >> N >> X;
	vector<int> m(N);
	int sum = 0;
	int minM = 1e9;
	for (int i = 0; i < N; ++i)
	{
		cin >> m[i];
		sum += m[i];
		minM = min(minM, m[i]);
	}
	int ans = N;
	cout << ans + (X - sum) / minM << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 256
import java.util.*;

public class Main {

    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long p = sc.nextInt();

    public static void main(String[] args) {
        new Main().run();
    }

    void run() {

        char[] s = sc.next().toCharArray();

        long ans = 0;

        long sumMod = 0;

        Map<Long, Long> map = new HashMap<>();

//        map.put((long)0, (long)1);

        if (p == 2 || p == 5) {
            for (int i=0; i<n; i++) {
                if ((s[i]-'0') % p == 0) ans += i + 1;
            }
//            for (int i=n-1; 0<=i; i--) {
//                if ((s[i]-'0') % p == 0) ans += i + 1;
//            }

            System.out.println(ans);
            return;
        }

        for (int i=n-1; 0<=i; i--) {
            long tmp = s[i] - '0';
            tmp *= modPow(10, n-1-i);
            tmp %= p;
            sumMod += tmp;
            sumMod %= p;
            if (map.containsKey(sumMod)) {
                map.put(sumMod, map.get(sumMod)+(long)1);
            } else {
                map.put(sumMod, (long)1);
            }
        }

//        System.out.println(map);

        for (Long t: map.values()) {
            ans += t * (t - 1) / 2;
        }

//        System.out.println(ans);

        if (map.get((long)0) == null) {
            System.out.println(ans);
        } else {
            System.out.println(ans + map.get((long)0));
        }


    }

    long modPow(long x, long n) {
        long sum = 1;
        while (n > 0) {
            if ( (n & 1) == 1 ) {
                sum *= x;
                sum %= p;
            }
            x *= x;
            x %= p;
            n >>= 1;
        }
        return sum % p;
    }
}


Measured memory_bytes: 46372
#include<bits/stdc++.h>
#include<climits>
#define FOR(i,a,b) for(int i = (a);i<=(b);i++)
#define ROF(i,a,b) for(int i = (a);i>=(b);i--)
#define MST(a,x) memset(a,x,sizeof(a))
#define ll long long
#define PB push_back
#define PH push
#define MP make_pair
#define FT first
#define SD second
#define N 100005
#define M 10005
#define INF 1000000007
#define MOD 1000000007
#define MOD2 1000000009
#define eps 1e-7
using namespace std;
inline int Max(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^b;
}
inline int Min(int a,int b)
{
    return (((b-a)>>(32-1))&(a^b))^a;
}
int is_mul_overflow(ll a, ll b) {
        return LLONG_MAX / a < b;
}
int a[N];
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n,t;
    while(cin>>n>>t)
    {
        FOR(i,1,n)cin>>a[i];
        int num = 0,mx = 0,mn = INF;
        FOR(i,1,n)
        {
            if(a[i]-mn>mx)
            {
                mx = a[i]-mn;
                num = 1;
            }
            else if(a[i]-mn == mx)num++;
            mn = min(mn,a[i]);
        }
        cout<<num<<endl;
    }
    return 0;
}


Measured memory_bytes: 640
n = list(map(int,input().split()))

tairyoku1 = n[0]
tairyoku2 = n[2]

while True:
    tairyoku2 = tairyoku2 - n[1]
    if tairyoku2 <= 0:
        print("Yes")
        exit()
    tairyoku1 = tairyoku1 - n[3]
    if tairyoku1 <= 0:
        print("No")
        exit()

Measured memory_bytes: 61852
#include <algorithm>
#include <cassert>
#include <cfloat>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <deque>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <vector>
 
#define FOR(i,k,n) for (int (i)=(k); (i)<(n); ++(i))
#define rep(i,n) FOR(i,0,n)
#define all(v) begin(v), end(v)
#define debug(x) cerr<< #x <<": "<<x<<endl
#define debug2(x,y) cerr<< #x <<": "<< x <<", "<< #y <<": "<< y <<endl
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int> > vvi;
typedef vector<ll> vll;
typedef vector<vector<ll> > vvll;
typedef deque<bool> db;
template<class T> using vv=vector<vector< T > >;

void no() {
  printf("NO\n");
  exit(0);
}

void yes() {
  printf("YES\n");
  exit(0);
}

int main() {
  int n, a, b;
  ll c, d;
  scanf("%d%d%d %lld %lld", &n, &a, &b, &c, &d);
  int diff = abs(a - b);
  ll n1 = n - 1;
  if (n1 * d < diff) {
    no();
  }
  if (n1 * c <= diff) {
    yes();
  }

  FOR (i, 1, n-1) {
    ll left_min = c * i;
    ll left_max = d * i;
    ll right_min = c * (n1 - i);
    ll right_max = d * (n1 - i);
    if (diff + left_max >= right_min && right_max >= diff + left_min) {
      yes();
    }
  }
  no();

  return 0;
}


Measured memory_bytes: 888
#include<iostream>
using namespace std;
int main(){
    int n,x,d;
    cin>>n>>d>>x;
    int result=0;
    int factor=(d*(d+1))/2;
    for(int i=0;i<n;i++)
    {
        int element;
        cin>>element;
        int res=(d-1)/(element);
        result+=res+1;
    }
    result+=x;
    cout<<result;
}

Measured memory_bytes: 3600
N = int(input())
A = list(map(int, input().split()))

# 各山に降った雨の量
x = [-1] * N

# まずx[0]を求める
# x[0] = s - 2 * (A_2+A_4+...+A_N-1)
s = sum(A)
temp = 0
for i in range(2, N, 2):
    temp += A[i - 1]
x[0] = s - 2 * temp

# x[1],x[2],...,x[N-1]を漸化式から求める
for i in range(1, N):
    x[i] = 2 * A[i - 1] - x[i - 1]
print(*x)


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

int main() {
  int n, m;
  cin >> n >> m;
  int a[3]={0,0,0};
  rep(i,m) {
    int s, c;
    cin >> s >> c;
    if(n!=1&&s==1&&c==0) {
      cout << -1 << endl;
      return 0;
    }
    if(a[s-1]!=0&&a[s-1]!=c) {
      cout << -1 << endl;
      return 0;
    }
    a[s-1] = c;
  }
  if(n!=1&&a[0]==0) a[0]=1;
  rep(i,n) cout << a[i];
  cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long int a,b,k;cin>>a>>b>>k;
    bool yes = 1;
    for(int i=0;i<k;i++){
        if(yes){
            if(a%2==1) --a,b+=(a/2),a/=2;
            else b+=(a/2),a/=2;
            yes = 0;
        }
        else{
            if(b%2==1) --b,a+=(b/2),b/=2;
            else a+=(b/2),b/=2;
            yes = 1;
        }
    }
    cout<<a<<" "<<b<<endl;
    return 0;}

Measured memory_bytes: 384
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *                      # ll = deepcopy(l)
from heapq import *                     # heappush(hp,x)
from string import *                    # alpha = ascii_lowercase
from random import *                    # l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *                    # bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin                   # bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize                 # minn = -maxsize
from operator import *                  # d = sorted(d.items(), key=itemgetter(1))
from itertools import *                 # pre = [0] + list(accumulate(l))
from decimal import Decimal             # a = Decimal(a)    # use this for math questions
from collections import Counter         # d = dict(Counter(l))
from collections import defaultdict     # d = defaultdict(list)

'''
8
WRWWRWRR
'''

def solve(l):
	l = list(l)
	n = len(l)
	if(len(set(l)) == 1):
		return 0
	m1 = l.count('R')
	m2,m3,m4,m5 = 0,0,l.count('W'),l.count('R')
	f = 0
	for i in range(n):
		if(f and l[i] == 'R'):
			m2 += 1
		elif(l[i] == 'W'):
			f = 1
	reds = l.count('R')
	rs = 0
	for i in range(reds):
		if(l[i] == 'R'):
			rs += 1
	m3 = reds - rs
	# print(m1,m2,m3,m4,m5)
	return min(m1,m2,m3,m4,m5)
	

N = int(stdin.readline())
l = input()
ans = solve(l)
print(ans)



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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using ll = long long;

const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int INF = 1<<30;
const ll mod = 1000000007LL;

int main() {
  ll N;
  cin>>N;
  vector<ll> v(N);
  for(ll i = 0LL; i < N; i++) {
    int x;
    cin>>x;
    v[i]=x-1;
  }
  vector<ll> A(N),B(N);
  for(ll i = 0LL; i < N; i++){
    A[i]=1LL+(N+1LL)*i;
    B[N-1LL-i]=1LL+(N+1LL)*i;
  }
  for(ll i = 0LL; i < N; i++){
    A[v[i]]+=i;
  }
  for(ll i = 0LL; i < N; i++){
    cout<<A[i]<<" ";
  }
  cout<<endl;
  for(ll i = 0LL; i < N; i++){
    cout<<B[i]<<" ";
  }
  cout<<endl;
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define showmap(is, js, x) {rep(i, is){rep(j, js){cout << x[i][j] << " ";}cout << endl;}}
#define show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> llP;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    int a, b, q;
    cin >> a >> b >> q;
    vector<ll> s(a);
    vector<ll> t(b);
    vector<ll> x(q);
    rep(i, a) cin >> s[i];
    rep(i, b) cin >> t[i];
    rep(i, q) cin >> x[i];
    
    rep(i, q){
        int sitr = lower_bound(s.begin(), s.end(), x[i]) - s.begin();
        int titr = lower_bound(t.begin(), t.end(), x[i]) - t.begin();

        ll len = (ll)1e12;
        // =>=>
        if (sitr != a && titr != b) len = min(len, max(abs(x[i]-s[sitr]), abs(x[i]-t[titr])));
        // <=<= 
        if (sitr != 0 && titr != 0) len = min(len, max(abs(x[i]-s[sitr-1]), abs(x[i]-t[titr-1]))); 
        // 
        if (sitr != 0 && titr != b) {
            ll tlen = min(abs(x[i]-s[sitr-1]), abs(x[i]-t[titr]));
            len = min(len, tlen + abs(s[sitr-1] -  t[titr]));
        }
        if (sitr != a && titr != 0) {
            ll tlen = min(abs(x[i]-s[sitr]), abs(x[i]-t[titr-1]));
            len = min(len, tlen + abs(s[sitr] -  t[titr-1]));
        }
        cout << len << endl;
    }

}


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

int main(){
    int N;
    cin>>N;
    vector<int64_t> L(N+1);
    L[0]=2;L[1]=1;
    for(int i=2;i<=N;i++){
        L[i]=L[i-1]+L[i-2];
    }
    cout<<L[N]<<endl;
} 


Measured memory_bytes: 256
#include <stdio.h>
int  pop();
int push(int);
int d[11],top,n,i;
int main(){
  while(scanf("%d",&n)!=EOF){
  
      if(n==0){
	pop();
        printf("%d\n",d[top+1]);
	}
      else{
        d[i]=push(n);
      }
    
  }
  
  return 0;
}
int push(int x){
  top++;
  d[top]=x;
  return d[top];
}
int pop(){
  top--;
  return d[top+1];
}

Measured memory_bytes: 596
#include <iostream>
#include <string>
#include <list>

using namespace std;

string sa,sb,sc;
void turnA();
void turnB();
void turnC();


void turnA() {
    if ( sa.empty() ) {
        cout << 'A' << endl;
       // return 0;
    } else {
        char tmp = sa[0];
        if (tmp == 'a')
        {
            sa.erase(sa.begin());
            turnA();
        } else if (tmp == 'b')
        {
            sa.erase(sa.begin());
            turnB();
        } else {
            sa.erase(sa.begin());
            turnC();
        }
        
    }
}

void turnB() {
     if ( sb.empty() ) {
        cout << 'B' << endl;
       // return 0;
    } else {
        char tmp = sb[0];
        if (tmp == 'a')
        {
            sb.erase(sb.begin());
            turnA();
        } else if (tmp == 'b')
        {
            sb.erase(sb.begin());
            turnB();
        } else {
            sb.erase(sb.begin());
            turnC();
        }
        
    }
   
}


void turnC() {
    if ( sc.empty() ) {
        cout << 'C' << endl;
       // return 0;
    } else {
        char tmp = sc[0];
        if (tmp == 'a')
        {
            sc.erase(sc.begin());
            turnA();
        } else if (tmp == 'b')
        {
            sc.erase(sc.begin());
            turnB();
        } else {
            sc.erase(sc.begin());
            turnC();
        }
        
    }
    
}


int main() {
    
    cin >> sa >> sb >> sc;

    turnA();

    return 0;
}
    


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <utility>
#include <cmath>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <tuple>
#include <numeric>
#include <functional>
using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef pair<ll, ll> P;
#define rep(i, n) for(ll i = 0; i < n; i++)
#define exrep(i, a, b) for(ll i = a; i <= b; i++)
#define out(x) cout << x << endl
#define exout(x) printf("%.10f\n", x)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define pb push_back
#define re0 return 0
const ll mod = 1000000007;
const ll INF = 1e16;
const ll MAX_N = 100010;

int main() {
    ll n, m;
    cin >> n >> m;

    vl v(n, -1);
    bool ok = true;
    rep(loop, m) {
        ll s, c;
        cin >> s >> c;
        s--;
        if(s == 0 && c == 0) {
            ok = false;
        }
        if(v[s] == -1) {
            v[s] = c;
        }
        else {
            if(v[s] != c) {
                ok = false;
            }
        }
    }

    if(n == 1 && v[0] == -1) {
        out(0);
        re0;
    }

    if(n == 1 && v[0] == 0) {
        out(0);
        re0;
    }

    if(ok == false) {
        out(-1);
        re0;
    }

    rep(i, n) {
        if(v[i] == -1) {
            if(i == 0) {
                v[i] = 1;
            }
            else {
                v[i] = 0;
            }
        }
    }

    rep(i, n) {
        cout << v[i];
    }

    cout << endl;
    re0;
}

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

int judge(int i)
{
	int sum=0;
	while(i)
	{
		if(i&1)sum++;
		i>>=1;
	}
	return sum;
}

int res(int a,int b,int c)
{
	int x=(a&(1<<b)),y=(a&(1<<c));
	if((x&&y)||((!x)&&(!y)))return a;
	if(x)
	{
		a^=1<<b;
		a|=1<<c;
	}
	else
	{
		a^=1<<c;
		a|=1<<b;
	}
	return a;
}

int f[70000];

int n,m;

void print(int deep,int x)
{
	if(deep==n+1)return;
	print(deep+1,x>>1);
	printf("%d",x&1);
}

int a1[20],a2[20]; 

int main(void)
{
	int x=0,count;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		int y;scanf("%d",&y);
		x=(x|y)<<1;
	}
	x>>=1;	
	count=judge(x);
	int a=0,b=0;
	for(int i=1;i<=m;i++)
	{
		int y;
		scanf("%d",&y);
		for(int j=0;j<y;j++)
		if(i&1)
		{
			a=(a+1)*2;
			b*=2;
		}
		else
		{
			b=(b+1)*2;
			a*=2;
		}
	}

	a>>=1;b>>=1;
	int y,top1,top2,ans1=0xffffff,ans2=0xffffff;
	if(judge(x)==judge(a))
	{	
		y=a;top1=0,top2=0;
		for(int i=0;i<n;i++)
		if((x^y)&(1<<i))
		{
			if(y&(1<<i))a1[top1++]=i;
			else a2[top2++]=i;
		}
		ans1=0;
		for(int i=0;i<top1;i++)
		{
			ans1+=abs(a1[i]-a2[i]);
		}
	}
	if(judge(x)==judge(b))
	{
		y=b;top1=0,top2=0;
		for(int i=0;i<n;i++)
		if((x^y)&(1<<i))
		{
			if(y&(1<<i))a1[top1++]=i;
			else a2[top2++]=i;
		}
		ans2=0;
		for(int i=0;i<top1;i++)
		{
			ans2+=abs(a1[i]-a2[i]);
		}
	}
	printf("%d\n",min(ans1,ans2));
	/*
	int ans=0,flag=0;
	f[x]=2;
	while(true)
	{
		flag=0;
		for(int i=0;i<((1<<n)-1);i++)
		if(f[i]==2)
		for(int j=0;j<n;j++)
		for(int k=j+1;k<n;k++)
		if(f[res(i,j,k)]==0)
		{
			flag=1;
			int x;
			f[x=res(i,j,k)]=1;
			print(1,x);printf("\n");
		}
		printf("\n");
		ans++;
		for(int i=0;i<0xffff;i++)if(f[i]==1)f[i]=2;
		if(f[a]||f[b]){break;}
		if(flag==0){ans=-1;break;}
	}*/
	//	printf("%d\n",ans);
	return 0;
}

/*
6 3
1 0 0 1 0 1
1 3 2


*/

Measured memory_bytes: 1032
// Ivan Carvalho
// Problem H - Educational Dynamic Programming Contest - AtCoder
// Link : https://atcoder.jp/contests/dp
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1010;
const int MOD = 1e9 + 7;

char entrada[MAXN][MAXN];
int dp[MAXN][MAXN],vis[MAXN][MAXN];
int N,M;

int solve(int x,int y){

	if(x >= N || y >= M) return 0;
	if(entrada[x][y] == '#') return 0;

	if(vis[x][y]) return dp[x][y];
	if(x == N - 1 && y == M - 1) return dp[x][y] = 1;

	vis[x][y] = 1;
	return dp[x][y] = (solve(x+1,y) + solve(x,y+1)) % MOD;

}

int main(){

	scanf("%d %d",&N,&M);
	for(int i = 0;i<N;i++){
		scanf("%s",entrada[i]);
	}

	printf("%d\n",solve(0,0));

	return 0;

}

Measured memory_bytes: 12796
#include<stdio.h>
#include <stdlib.h>
#define FOR(i,a,b) for(int i=a;i<b;i++)

int main(){
	int n;
	scanf("%d",&n);

	int *a1 = (int *)calloc(n,sizeof(int));
	int *a2 = (int *)calloc(n,sizeof(int));
	FOR(i,0,n){
		scanf("%d",&a1[i]);
		a2[a1[i]]++;
	}

	int tmp = n-1,ans = 0;
	while(tmp>0){
		if(a2[tmp] != 2) ans++;
		tmp -= 2;
	}

	if(n%2 == 0 && a2[0] != 0) ans++;
	if(n%2 == 1 && a2[0] != 1) ans++;

	if(ans != 0) printf("0\n");
	else{
		int pow = 1;
		FOR(i,0,n/2) pow = (pow * 2) % 1000000007;
		printf("%d",pow);
	}
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
#define first ff
#define second ss
#define ll long long int
int main()
{
    int n;
    cin>>n;
    int a[n]={0},b[n]={0};
    int x,y;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    int mx=0;

    for(int i=0;i<n;i++){
         if(a[i]-b[i]>0) mx+=(a[i]-b[i]);
    }

cout<<mx;

}


Measured memory_bytes: 3604
import java.util.Scanner;
 
public class Main {
    static Scanner sc = new Scanner(System.in);
 
    public static void main(String[] args) {
        while (true) {
            int N = sc.nextInt();
            int D = sc.nextInt();
            if (N == 0) break;
            int sm = 0;
            Country[] cs = new Country[N];
            int mp = 0;
            int mc = 1;
            for (int i = 0; i < N; ++i) {
                cs[i] = new Country();
                sm += cs[i].m.length;
                if (cs[i].p > mp) {
                    mp = cs[i].p;
                    mc = 1;
                } else if (cs[i].p == mp) {
                    ++mc;
                }
            }
            boolean ok = true;
            for (int i = 0; i < sm; ++i) {
                int ci = -1;
                for (int j = 0; j < N && ci == -1; ++j) {
                    Country c = cs[j];
                    if (c.pos == -1) continue;
                    if (c.p == mp && mc == 1) {
                        int nmp = 0;
                        for (int k = 0; k < N; ++k) {
                            if (k == j) continue;
                            nmp = Math.max(nmp, cs[k].p);
                        }
                        if (c.p - c.m[c.pos] >= nmp - D) {
                            ci = j;
                        }
                    } else {
                        if (c.p - c.m[c.pos] >= mp - D) {
                            ci = j;
                        }
                    }
                }
                if (ci == -1) {
                    ok = false;
                    break;
                }
                cs[ci].p -= cs[ci].m[cs[ci].pos];
                cs[ci].pos--;
                mp = 0;
                mc = 0;
                for (int j = 0; j < N; ++j) {
                    if (cs[j].p > mp) {
                        mp = cs[j].p;
                        mc = 1;
                    } else if (cs[j].p == mp) {
                        ++mc;
                    }
                }
            }
            System.out.println(ok ? "Yes" : "No");
        }
    }
 
    static class Country {
        int[] m;
        int p, pos;
 
        Country() {
            int s = sc.nextInt();
            m = new int[s];
            for (int i = 0; i < s; ++i) {
                m[i] = sc.nextInt();
                p += m[i];
            }
            pos = m.length - 1;
        }
    }
 
}

Measured memory_bytes: 74456
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

ll mod(ll a){
  return (a % 1000000007);
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}

ll nCr(ll n,ll r){
  if(r == 1) return n;
  else if(r == 0) return 1;
  else return nCr(n-1,r-1)*n/r;
}

int main(){
  ll a,b,c,k; cin >> a >> b >> c >> k;
  
  ll x = max({a,b,c});
  
  cout << a + b + c - x + x*pow(2,k) << endl;
  
}

Measured memory_bytes: 256