akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <utility>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <iomanip>
#include <cstdio>
#include <stack>
#include <numeric>

using namespace std;
typedef  long long ll;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
#define  MP make_pair
#define  PB push_back
#define inf 1000000007
#define mod 1000000007
#define rep(i,n) for(int i=0;i<(int)(n);++i)

int res[1<<18][11];
ll dp[1<<18][42];
int n,x,y,z;
    
bool ok(int bits){
    int k = 0;
    rep(i,30){
        if((bits>>i)&1){
            k = i+1;
        }
    }
    if(k<x)return true;
    if(!((bits>>(x-1))&1)){
        return false;
    }
    if(k<x+y)return true;
    if(!((bits>>(x+y-1))&1)){
        return false;
    }
    if(k<x+y+z)return true;
    if(!((bits>>(x+y+z-1))&1)){
        return false;
    }
    return true;
}

ll ruijo(ll x,ll n){
	long long p,ans;
	if(n==0)return 1;
	if(n==1)return x;
	if(n%2){
		p = ruijo(x,n/2);
		ans = (x*p)%mod;
		ans = (ans*p)%mod;
		return ans;
	}else{
		p = ruijo(x,n/2);
		ans = (p*p)%mod;
		return ans;
	}
}

int main(){
    cin >> n;
    cin >> x >> y >> z;
    for(int bits = 0;bits < (1<<(x+y+z)); bits++){
        int k = 0;
        rep(i,18){
            if((bits>>i)&1){
                k = i+1;
            }
        }
        if(!ok(bits)){
            for(int i = 1;i<=10;i++){
                res[bits][i] = -1;
            }
        }else{
            for(int i = 1;i<=10;i++){
                int tmp = bits + (1<<(k+i-1));
                if(ok(tmp)){
                    if(k+i>=(x+y+z)){
                        res[bits][i] = -1;
                    }else{
                        res[bits][i] = tmp;
                    }
                }else{
                    rep(j,18){
                        if((bits>>j)&1){
                            if(ok(tmp>>(j+1))){
                                if(k+i-j-1>=(x+y+z)){
                                    res[bits][i] = -1;
                                }else{
                                    res[bits][i] = tmp>>(j+1);
                                }
                                break;
                            }
                        }
                    }
                }
            }   
        }
    }
    dp[0][0] = 1;
    rep(i,n){
        rep(bits,1<<(x+y+z)){
            for(int j=1;j<=10;j++){
                if(res[bits][j]!=-1){
                    dp[res[bits][j]][i+1] += dp[bits][i];
                    dp[res[bits][j]][i+1] %= mod;
                }
            }
        }
    }
    ll ans = 0;
    rep(bits,1<<(x+y+z)){
        ans += dp[bits][n];
        ans %= mod;
    }
    ll p = ruijo(10LL,n);
    cout << (p + mod - ans)%mod << endl;
    return 0;
}

Measured memory_bytes: 28160
# ESC ESC ESC  <-  ???
# C-g (many times if needed)

# C-x h  and  C-x C-x  <-  selection
# M-;  M- means option key  <- comment out

# C-h k  <-  help for key
# C-x 1  <-  close other windows

# def main():
#     print("Hello, world")

# if __name__ == "__main__":
#     main()
# 
# aaaa


# aaaa
# aaa


import sys


def main():
    input_snuke = input()
    ret = snuke(input_snuke)
    print(ret)
    print("Hello, world.", file=sys.stderr)

    return ret


def snuke(list_snuke):

    count_snuke = 0
    #list_snuke = input()
    for ch in list_snuke:
        if ch == '1':  # "1" is also available
            count_snuke += 1

    return count_snuke


if __name__ == '__main__':
    main()


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

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

  vector<pair<long, int>> shops(N);
  for (int i = 0; i < N; i++) {
    long A;
    int B;
    cin >> A >> B;
    shops.at(i) = make_pair(A, B * -1);
  }

  sort(shops.begin(), shops.end());

  long cost = 0;
  for (int i = 0; i < N; i++) {
    pair<long, int> shop = shops.at(i);
    int drink_count = min(M, shop.second * -1);
    cost += shop.first * drink_count;
    M -= drink_count;

    if (M == 0) {
      break;
    }
  }

  cout << cost << endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (register int i = a; i <= b; i++)

ll ans[1000010][4];
ll n, mod = 1e9 + 7;
inline void solve(int T) {
    cin >> n;
    ans[1][0] = 1;
    ans[1][1] = 1;
    ans[1][2] = 0;
    ans[1][3] = 8;
    rep(i, 2, n) {
        ans[i][0] = ans[i - 1][3] + ans[i - 1][0] * 9;
        ans[i][0] %= mod;
        ans[i][1] = ans[i - 1][3] + ans[i - 1][1] * 9;
        ans[i][1] %= mod;
        ans[i][2] = ans[i - 1][0] + ans[i - 1][1] + ans[i - 1][2] * 10;
        ans[i][2] %= mod;
        ans[i][3] = ans[i - 1][3] * 8;
        ans[i][3] %= mod;
    }
    cout << ans[n][2];
    
}
int main()
{
    // ios_base::sync_with_stdio(0);
    // cin.tie(0);
    // cout.tie(0);

    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
 
    int T = 1;
    // cin >> T;
    rep(i, 1, T) solve(i);
    
    // system("pause");
}

Measured memory_bytes: 34608
#include <iostream>
using namespace std;
int main(void){
    int a,b,c,d,e,i,k,o;
    cin>>a;
    cin>>b;
    cin>>c;
    cin>>d;
    cin>>e;
    i=0;
    if(a<0){
        k=a;
    while(1){
        if(k==0){break;}
        if(k<0){i=i+c;k++;}
        if(k==0){i=i+d;}
        }
        o=k;
        while(1){
        if(o==b){break;}
        if(o!=b){i=i+e;}
        o++;    
        }
    }
    else if(0<a){
        o=a;
        while(1){
        if(o==b){break;}
        if(o!=b){i=i+e;}
        o++;
    }
}cout<<i<<endl;
}


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

#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define ALL(x) (x).begin(), (x).end()
#define OUT(a) cout << (a) << "\n"

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

const ll MOD = 10e9 + 7;
ll dp[101][100001];

int main() {
    int r,d,x;
  	cin >> r >> d >> x;
  	auto f = [&]() {
      return r*x - d;
    };
  	for(int i=0; i<10; i++) {
		x = f();
      	cout << x << endl;
    }
    return 0;
}


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

long ipow(const long a, long n){
    long x=a, y=1;
    while(n>0){
        if(n&1){
            y*=x;
        }
        x*=x;
        n>>=1;
    }
    return y;
}

long fact(long p, const long n){
    long g=1;
    long d=2;
    long pd = ipow(d, n);
    for(;;){
        if(p%pd==0){
            p/=pd;
            g*=d;
        }else{
            break;
        }
    }
    for(d=3;; d+=2){
        pd = ipow(d, n);
        if(pd>p){
            break;
        }
        for(;;){
            if(p%pd==0){
                p/=pd;
                g*=d;
            }else{
                break;
            }
        }
    }
    return g;
}

int main(void){
    long n, p;
    cin >> n >> p;
    if(n==1){
        cout << p << endl;
    }else if(n>40 || (1<<n)>p){
        cout << 1 << endl;
    }else{
        cout << fact(p, n) << endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, N) for (int i = 0; i < (int)N; ++i)
#define all(a) (a).begin(), (a).end()
int first_fixed_size_subset(int n, int k) { return (1 << k) - 1; }

int next_fixed_size_subset(int n, int k, int& s) {
  int x = s & -s, y = s + x;
  s = (((s & ~y) / x) >> 1) | y;
  if (s >= (1 << n)) return 0;
  return s;
}

struct Card {
  int G, Y;
};

struct Elem {
  bool green;
  int v;
};

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

  vector<Card> C(N);
  rep(i, N) {
    if (i % 2 == 0) {
      cin >> C[i].G;
    } else {
      cin >> C[i].Y;
    }
  }
  rep(i, N) {
    if (i % 2 == 0) {
      cin >> C[i].Y;
    } else {
      cin >> C[i].G;
    }
  }

  int nGreen = (N + 1) / 2;
  int green = first_fixed_size_subset(N, nGreen);

  int ans = 1e9;

  do {
    int cost = 0;

    vector<Elem> sorting(N);
    rep(i, N) {
      if ((green >> i) & 1) {
        sorting[i] = Elem{true, C[i].G};
      } else {
        sorting[i] = Elem{false, C[i].Y};
      }
    }

    bool flag = true;
    for (int i = 0; flag; i++) {
      flag = false;
      for (int j = N - 1; j >= i + 1; --j) {
        if (sorting[j].v < sorting[j - 1].v) {
          swap(sorting[j], sorting[j - 1]);
          flag = 1;
          ++cost;
        }
      }
    }

    rep(i, N) {
      if (i % 2 == 0 && !sorting[i].green) {
        int j = i + 1;
        while (j < N && sorting[i].v == sorting[j].v && !sorting[j].green) ++j;
        if (j == N || sorting[i].v != sorting[j].v) goto end;
        for (int k = j; k > i; --k) {
          swap(sorting[k], sorting[k - 1]);
          ++cost;
        }
      }
      if (i % 2 == 1 && sorting[i].green) {
        int j = i + 1;
        while (j < N && sorting[i].v == sorting[j].v && sorting[j].green) ++j;
        if (j == N || sorting[i].v != sorting[j].v) goto end;
        for (int k = j; k > i; --k) {
          swap(sorting[k], sorting[k - 1]);
          ++cost;
        }
      }
    }

    ans = min(ans, cost);
  end:;
  } while (next_fixed_size_subset(N, nGreen, green));

  cout << (ans == 1e9 ? -1 : ans) << endl;

  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
#define ll long long
#define dd double
#define MOD1 1000000007
#define MOD2 998244353
#define nl cout<<endl
#define rt ll Q[100005]={0}
#define mp make_pair
#define test() ll t;cin>>t;while(t--)
#define pb push_back
#define ff first    
#define ss second
#define all(v) v.begin(),v.end()
#define s(ar,n) sort(ar,ar+n)
#define rs(ar,n) sort(ar, ar+n, greater<ll>()) 
#define oa(a,n) for(ll i=0;i<n;i++)cout<<a[i]<<" ";nl
#define cn(a,n) for(ll i=0;i<n;i++)cin>>a[i];
#define ov(a,n) for(ll i=n-1;i>=0;i--)cout<<a[i]<<" ";nl
#define ovp(a,n) for(ll i=0;i<n;i++)cout<<a[i].ff<<" "<<a[i].ss<<endl;
#define maxa(ar,N) *max_element(ar,ar+N)
#define mina(ar,N) *min_element(ar,ar+N)
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
typedef pair<ll,ll> pii;
ll powe(ll n,ll m){if(m==0)return 1;ll t=powe(n,m/2);if(m%2==0)return (t*t);return (((t*t))*n);}
ll mpowe(ll n,ll m,ll MOD){if(m==0)return 1;ll t=mpowe(n,m/2,MOD);t%=MOD;if(m%2==0)return (t*t)%MOD;return (((t*t)%MOD)*n)%MOD;}
ll logtwo(ll n){if(n==1)return 0;if(n==0) return -1;return logtwo(n/2)+1;}
int main()
{
    fastio();
    
    ll a;
    cin>>a;
    ll ans= a*a + a+ a*a*a;
    cout<<ans<<endl;
}

Measured memory_bytes: 3608
#include "bits/stdc++.h"
using namespace std;
typedef long long int lint;
typedef pair<lint, lint> plint;
typedef pair<double long, double long> pld;
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((lint)(x).size())
#define POW2(n) (1LL << (n))
#define FOR(i, begin, end) for(lint i=(begin),i##_end_=(end);i<i##_end_;i++)
#define IFOR(i, begin, end) for(lint i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define REP(i, n) FOR(i,0,n)
#define IREP(i, n) IFOR(i,0,n)
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; }
template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first + r.first, l.second + r.second); }
template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2>& l, const pair<T1, T2>& r) { return make_pair(l.first - r.first, l.second - r.second); }
const lint MOD = 1e9 + 7, INF = 1e18, MAX_N = 200000;

lint N, D;
lint cnt[13];
map<lint, bool> mp;
int main() {
	cin.tie(0); ios_base::sync_with_stdio(false);
	cin >> N;
	REP(i, N) {
		cin >> D;
		cnt[D]++;
	}

	vector<lint> di;
	REP(i, 13) {
		if (cnt[i] == 1) {
			di.push_back(i);
			mp[i] = false;
		}
		else if (cnt[i] == 2) {
			di.push_back(i);
			mp[i] = true;
		}
		else if (cnt[i] > 2) {
			cout << 0 << endl;
			return 0;
		}
	}
	lint M = SZ(di);
	lint maxv = 0;
	REP(i, 1 << M) {
		bool time[100] = { false };
		time[0] = true;
		time[24] = true;
		lint minv = 24, cnt = 1;
		REP(j, M) {
			if (!mp[di[j]]) {
				if ((i >> j) % 2 == 0) {
					if (time[di[j]]) minv = 0;
					time[di[j]] = true;
				}
				else {
					if (time[24 - di[j]]) minv = 0;
					time[24 - di[j]] = true;
				}
			}
			else {
				time[di[j]] = true;
				time[24 - di[j]] = true;
			}
		}
		REP(i, 23) {
			if (time[i + 1]) {
				chmin(minv, cnt);
				cnt = 1;
			}
			else {
				cnt++;
			}
		}
		chmin(minv, cnt);
		chmax(maxv, minv);
	}
	cout << maxv << endl;
}


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

const int N = 14;
int T[N];
int mem[1<<N];

int f(int used, int head, int d) {
  used |= (1<<head);
  for(int i = 1; i < 3; ++i) {
    bool flag = false;
    int u = T[head]+i*d;
    for(int j = lower_bound(T, T+N, u) - T;
        j < N && T[j] == u; ++j) {
      if(used & (1<<j)) continue;
      flag = true;
      used |= (1<<j);
      break;
    }
    if(!flag) return 0;
  }
  return used;
}

bool rec(int used) {
  int &res = mem[used];
  if(res != -1) return res;
  if(N - __builtin_popcount(used) == 2) {
    int tmp[2];
    for(int i = 0, j = 0; i < N; ++i) {
      if(used & (1<<i)) continue;
      tmp[j++] = T[i];
    }
    return res = (tmp[0] == tmp[1]);
  }
  res = 0;
  for(int i = 0; i < N; ++i) {
    if(used&(1<<i)) continue;
    for(int d = 0; d <= 1; ++d) {
      int nused = f(used, i, d);
      if(!nused) continue;
      if(rec(nused)) return res = true;
    }
  }
  return res = false;
}

int main() {
  string s;
  while(cin >> s) {
    int num[10];
    fill(num, num+10, 0);
    for(int i = 0; i < s.size(); ++i) ++num[s[i] - '0'];
    vector<int> v;
    for(char c = 1; c <= 9; ++c) {
      if(num[c] == 4) continue;
      for(int i = 0; i < s.size(); ++i) T[i] = s[i] - '0';
      T[N-1] = c;
      sort(T, T+N);
      fill(mem, mem+(1<<N), -1);
      if(rec(0)) v.push_back(c);
    }
    if(v.empty()) v.push_back(0);
    for(int i = 0; i < v.size(); ++i) {
      if(i) cout << " ";
      cout << v[i];
    }
    cout << endl;
  }
  return 0;
}

Measured memory_bytes: 1272
#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n;
	while (cin >> n) {
		if (n == 0) {
			break;
		}
		vector<long long int> data(n);
		int left = 0;
		int right = n-1;
		for (int i = 0; i < n; i++) {
			cin >> data[i];
		}
		int counter = 0;
		int tansa;
		cin >> tansa;
		while (true) {
			int half = (left+right) / 2;
			counter++;
			if (left == right) {
				break;
			}
			if (data[half] == tansa) {
				break;
			} else if (data[half] < tansa) {
				left = half+1;
			} else {
				right = half-1;
			}
			if (left > right) {
				break;
			}
		}
		cout << counter << endl;
	}
	return 0;
}

Measured memory_bytes: 1204
import heapq

def main():
    N, M = map(int, input().split())
    A = [-int(i) for i in input().split()]

    heapq.heapify(A)

    for i in range(M):
        x = heapq.heappop(A)
        heapq.heappush(A, x / 2)

    print(-1 * sum([int(x) for x in A]))

if __name__ == '__main__':
    main()


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

int main() {
  int n,x,two,fiv,now,i;
  while(cin>>x, x){
    two=fiv=0;
    for(i=1;i<=x;i++){
      now=i;
      while(1){
	if(now%2==0){
	  two++;
	  now/=2;
	}
	else if(now%5==0){
	  fiv++;
	  now/=5;
	}
	else break;
      }
    }
    cout << min(two,fiv) << endl;
  }
  
  return 0;
}
      
    
    

Measured memory_bytes: 1160
# coding: utf-8
    
def solve(N):
    ans = 0
    for i in range(1, N+1, 2):
        cnt = 0
        for j in range(1, N+1, 2):
            if i % j == 0:
                cnt += 1
        if cnt == 8:
            ans += 1
    return ans
            
        
if __name__ == "__main__":
    N = int(input())
    print(solve(N))
    


Measured memory_bytes: 2940
#include<stdio.h>
int main(){
  int h,i,j,n,w,is,ce,cm,me,mm;
  float fs;
  for(h=1;;h++){
    scanf("%d",&w);
    if(w==0)
       break;
    scanf("%d",&n);
    int e[n],m[n],s[n],ns,k[w+1][n];
    float p[n];
    ce=0;
    cm=0;
    me=0;
    mm=0;
    for(i=0;i<w+1;i++)
      for(j=0;j<n;j++)
	k[i][j]=0;
    ns=0;
    for(i=0,j=0;i<n;i++,j++){
      scanf("%d,%d",&m[j],&e[j]);
      if(w<e[j])
	j--;
      else
	p[j]=(float)m[j]/e[j];
    }
    n=j;
    for(i=0;i<n-1;i++)
      for(j=i+1;j<n;j++)
	if(p[i]<p[j]){
	  fs=p[i];
	  p[i]=p[j];
	  p[j]=fs;
	  is=m[i];
	  m[i]=m[j];
	  m[j]=is;
	  is=e[i];
	  e[i]=e[j];
	  e[j]=is;
	}
    i=0;
    for(;;){
      for(;i<n;i++)
	if(e[i]+ce<=w){
	  if(cm+m[i]>k[ce+e[i]][i]){
	    s[ns]=i;
	    ns++;
	    ce+=e[i];
	    cm+=m[i];
	    k[ce][i]=cm;
	    if(mm<cm){
	      mm=cm;
	      me=ce;
	    }else if(mm==cm)
	      if(me>ce)
		me=ce;
	    if(cm+p[i]*(w-ce)<mm)
	      break;
	  }
	}
      if(ns){
	ns--;
	i=s[ns];
	ce-=e[i];
	cm-=m[i];
	i++;
      }else
	break;
    }
    printf("Case %d:\n%d\n%d\n",h,mm,me);
  }
  return 0;
}

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

int main(){
    long long N;
    cin >> N;
    long long A[N+1];
    long long B[N];

    for(int i = 0; i <= N; i++){
        cin >> A[i];
    }
    for(int i = 0; i < N; i++){
        cin >> B[i];
    }
    long long ans = 0;
    for(int i = N-1; i >= 0; --i){
        if(A[i+1] >= B[i]){
            ans += B[i];
            A[i+1] -= B[i];
            B[i] = 0; 
        }else{
            ans += A[i+1];
            B[i] -= A[i+1];
            A[i+1] = 0;
        }

        if(A[i] >= B[i]){
            ans += B[i];
            A[i] -= B[i];
            B[i] = 0;
        }else{
            ans += A[i];
            B[i] -= A[i];
            A[i] = 0;
        }

    }
    cout << ans << endl;    

}

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

int main(int argc, char **argv)
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);

#ifdef LOCAL_DEFINE
   freopen("in.txt", "r", stdin);
#endif

   string s;
   cin >> s;
   for (int i = 0; i < 3; ++i)
   {
      if (s[i] == s[i + 1])
      {
         cout << "Bad\n";
         return 0;
      }
   }

   cout << "Good\n";
   return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int main() {
  int W, H , x ,y ,r;
  scanf("%d %d %d %d %d",&W,&H,&x,&y,&r);

  if(x-r<0 || x+r>W || y-r<0 || y+r>H) {
    printf("No\n");
  } else {
    printf("Yes\n"); 
  }


  return 0;
}


Measured memory_bytes: 2092
n = int(input())
if n <= 111:
    print(111)
elif n <= 222:
    print(222)
elif n <= 333:
    print(333)
elif n <= 444:
    print(444)
elif n <= 555:
    print(555)
elif n <= 666:
    print(666)
elif n <= 777:
    print(777)
elif n <= 888:
    print(888)
else:
    print(999)

Measured memory_bytes: 9064
n,m=map(int,input().split())
a=[[int(b) for b in input().split()] for _ in range(m)]
t=[0]*n
for i in range(m):
    t[a[i][0]-1] += 1
    t[a[i][1]-1] += 1
for i in range(n):
    print(t[i])

Measured memory_bytes: 3064
import io
import sys
from bisect import bisect_right, bisect_left
from collections import deque


def IN_S():
  return input()


def IN_I():
  return int(input())


def IN_L_I():
  return list(map(int, input().split()))


def IN_L_S():
  return list(map(str, input().split()))


def STR_SPLIT(s, n):
  for l in range(0, len(s), n):
    yield s[0 + l:n + l]


def T_IN():
  global test_str
  sys.stdin = io.StringIO(test_str[1:-1])


test_str = '''
7
1
0
3
4
1
2
1
'''


def MAIN():
  # T_IN()
  A()


def A():
  n = IN_I()

  l = deque([IN_I()])

  for i in range(0, n - 1):
    num = IN_I()

    idx = bisect_left(l, num)
    if idx == 0:
      l.appendleft(num)
    else:
      l[idx - 1] = num
    # print(l)

  print(len(l))
  return None


def B():
  return None


def C():
  return None


MAIN()


Measured memory_bytes: 49496
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (int i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define REPALL(i,v) for (int i = 0; i < v.size(); i++)
#define RREPALL(i,v) for (int i = v.size()-1; i >= 0; i--)
#define SORT(v) sort(v.begin(), v.end())
#define MIN_ELEMENT(v) min_element(v.begin(), v.end())
#define MAX_ELEMENT(v) max_element(v.begin(), v.end())
#define COUNT(v,n) count(v.begin(), v.end(), n);
void YES(bool flag) {cout<<(flag ? "YES" : "NO")<<endl;}
void Yes(bool flag) {cout<<(flag ? "Yes" : "No")<<endl;}
void yes(bool flag) {cout<<(flag ? "yes" : "no")<<endl;}
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e7;
const ll MOD = 1e9 + 7;

vector<int> num(26, INF);

int main()
{
    int n;
    cin>>n;
    REP(i,n) {
        string s;
        cin>>s;
        vector<int> nnum(26, 0);
        REPALL(j,s) {
            nnum[(int)(s[j] - 'a')]++;
        }
        REP(j,26) {
            num[j] = min(num[j], nnum[j]);
        }
    }
    string ans = "";
    REP(i,26) {
        REP(j,num[i]) {
            ans += (char)(i + 'a');
        }
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <map>
#define div 1000000000+7
using namespace std;
typedef long long ll;

int main(){
    string s;
    string t;
    int count = 0;
    cin >> s;

    while(count < s.length()){
        //cout << s[count] << endl;
        if(s[count] == 'd' && s[count+6] == 'r' && s[count+7] != 'a' && s[count+5] != 'd'){
            t += "dreamer";
            count += 7;
        }else if(s[count] == 'd'){
            t += "dream";
            count += 5;
        }else if(s[count] == 'e' && s[count+5] == 'r'){
            t += "eraser";
            count += 6;
        }else if(s[count] == 'e' && s[count+5] != 'r'){
            t += "erase";
            count += 5;
        }else{
            cout << "NO" << endl;
            return 0;
        }
    }
 //   cout << s << endl;
 //   cout << t << endl;

    if(s == t){
        cout << "YES" << endl;
    }else{
        cout << "NO" << endl;
    }

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; --i)
#define FOR(i, m, n) for (ll i = m; i < n; ++i)
#define FORR(i, m, n) for (ll i = m; i >= n; --i)
#define ALL(v) (v).begin(),(v).end()
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; }
const ll INF=1LL<<60;
const int inf=(1<<30)-1;
const int mod=1e9+7;
int dx[8]={1,0,-1,0,-1,-1,1,1};
int dy[8]={0,1,0,-1,-1,1,-1,1};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n;cin >> n;
    vector<ll> x(n),y(n);
    map<pair<int,int>,int> mp;
    REP(i,n){
        cin >> x[i] >> y[i];
    }
    REP(i,n){
        REP(j,n){
            if(i==j){
                continue;
            }
            mp[{x[j]-x[i],y[j]-y[i]}]++;
        }
    }
    int t=0;
    for(auto v:mp){
        chmax(t,v.second);
    }
    cout << n-t << endl;
}

Measured memory_bytes: 3808
/*Bismillahir Rahmanir Rahim*///{
#include <bits/stdc++.h>
#include <ext/numeric>
using namespace std; using __gnu_cxx::power;
using ll = long long; using ull = unsigned long long; using ld = long double;
const ll llinf = (1ll<<61)-1;
const double eps = 1e-6, ldeps = 1e-9;
struct Dbg {
static constexpr auto &os = cout;   // replace by cerr in interactive.
template<class C> static auto dud(C *x)->decltype(os << *x, 0);
template<class C> static char dud(...);
template<class C> typename enable_if<sizeof dud<C>(0)!=1, Dbg&>::type operator<<(const C &x) { os << x; return *this; }
template<class C> Dbg &dump(C b, C e) {
    *this << "\n[";
    int cur = 0;
    for (C i = b; i!=e and cur<26; i++, cur++) *this << ", "+2*(i==b) << *i;
    return *this << ']';
}
template<class C> typename enable_if<sizeof dud<C>(0)==1, Dbg&>::type operator<<(const C &x) {
    return dump(begin(x), end(x));
}
template<class C, size_t X> typename enable_if<!is_same<C, const char>::value, Dbg&>::type operator <<(C (&x)[X]) {
    return dump(begin(x), end(x));
}
template<class B, class C> Dbg &operator <<(const pair<B, C> &x) {
    return *this << '{' << x.first << ", " << x.second << '}';
}
Dbg &operator<<(ostream&(*x)(std::ostream&)) { os << x; return *this; }
} dbg;
void err(istringstream *iss) { delete iss; }
template<class C, class... Args> void err(istringstream *iss, const C &val, const Args &... args) {
    string name; *iss >> name; if (name.back()==',') name.pop_back();
    dbg << name << " = " << val << "; ", err(iss, args...);
}
#define bug(args...) dbg << __LINE__ << ": ", err(new istringstream(#args), args), dbg << endl
#define cbug(a, args...) if (a) bug(args);
#define ASSERT(a, o, b, args...) if (!((a)o(b))) bug(a, b, ##args), assert((a)o(b));
#define sl(a) int(strlen(a))
#define sz(a) int(a.size())
int T, Q, cn;//}
const int inf = 1000000007, mxn = 105;

int n, sum[mxn], c;

signed main() { cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit); cout.precision(11);
    cin >> n;
    // for (n = 4; n <= 100; n++) {
    //     memset(sum, 0, sizeof(sum)), c = 0;
    cout << (n*(n-2)+1)/2 << '\n';
    for (int i = 1; i <= n-1; i++) {
        for (int j = i+1; j <= n; j++) {
            if (i+j!=n+!(n&1)) cout << i << ' ' << j << '\n', c++, sum[i] += j, sum[j] += i;
        }
    }

    // ASSERT(c, ==, (n*(n-2)+1)/2)
    // for (int i = 2; i <= n; i++) {
    //     ASSERT(sum[i], ==, sum[1], i)
    // }
    // }
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mo=1e9+7;
const int len=2005;
const int maxn=4050;
const int maxm=8005;
const int lenn=8000;
int n;
int A[200005],B[200005];
LL ans;
LL fac[maxm],inv[maxm],F[maxn][maxn];
LL C(int x,int y)
{
	if(x<y) return 0;
	if(!y) return 1;
	return ((fac[x]*inv[y]%mo)*inv[x-y]%mo);
}
LL exgcd(LL a,LL b,LL &x,LL &y)
{
	if(!b){
		x=1,y=0;return a;
	}
	LL d=exgcd(b,a%b,x,y),z=x;//cout<<a<<" "<<b<<" "<<x<<" "<<y<<endl;
	x=y,y=z-a/b*y;
	return d;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d%d",&A[i],&B[i]);
	for(int i=1;i<=n;++i) ++F[len-A[i]][len-B[i]];
	for(int i=1;i<=(len<<1);++i)
	  for(int j=1;j<=(len<<1);++j)
	    F[i][j]=(F[i][j]+F[i-1][j]+F[i][j-1])%mo;
	for(int i=1;i<=n;++i) ans=(ans+F[len+A[i]][len+B[i]])%mo;
	//cout<<ans<<endl;
	fac[0]=1;
	for(int i=1;i<=lenn+1;++i) fac[i]=fac[i-1]*(LL)i%mo;
	LL x=0,y=0;
	exgcd(fac[lenn+1],mo,x,y);
	x=(x+mo)%mo;
	inv[lenn+1]=x;
	for(int i=lenn;i>=1;--i) inv[i]=inv[i+1]*(LL)(i+1)%mo;
	for(int i=1;i<=n;++i) ans=(ans-C((A[i]+B[i])<<1,A[i]<<1))%mo;
	ans=(ans+mo)%mo;
	ans=ans*inv[2]%mo;
	printf("%lld",ans);
	return 0;
}

Measured memory_bytes: 130048
#include<bits/stdc++.h>
#define REP(i,n) for(int i = 0; i < n; ++i)
#define REPR(i,n) for(int i = n; i >= 0; --i)
#define FOR(i,a,b) for(int i = (a); i < (b); ++i)
#define FORR(i, a, b) for(int i = b-1;i >= a;--i)
#define p(s) cout << (s) << endl
#define p2(s,t) cout << (s) << " " << (t) << endl 
#define ALL(v) (v).begin(), (v).end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

static const ll mod  = 1e9 + 7;
static const ll inf  = 1e18;

static const int White = 0;
static const int Gray = 1;
static const int Black = 2;

void pvector(vector<int> A){
    cout << "[vector]";
    for(int i = 0; i < A.size(); i++){
        cout << A[i] << " ";
    }
    cout << endl;
}

int main(){
    int a, p, b, c, n, ans, cnt = 0;
    cin >> a >> p;
    p((3* a + p )/2);
}

Measured memory_bytes: 256
from bisect import bisect_left, bisect_right
n = int(input())
l = list(map(int, input().split()))
l.sort()

ans = 0
for j in range(n):
    for k in range(j + 1, n):
        if l[j] == l[k]:
            continue

        ans += max(bisect_left(l, l[j]) - bisect_right(l, l[k] - l[j]), 0)

print(ans)


Measured memory_bytes: 9080
#include<bits/stdc++.h>
#define rep(i,a) for(int (i)=0; (i)<(a); (i)++)
#define rep2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define all(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
#define chmax(a,b) if(b>a) a = b
#define chmin(a,b) if(b<a) a = b
typedef long long ll;
using namespace std;

using namespace std;

bool dp[1000050];

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

        int n; cin >> n;
        vector<int> a(n);
        rep(i,n) cin >> a[i];
        sort(all(a));

        int ans = 0;
        rep(i,1000050) dp[i] = true;
        rep(i,n){
                if(i > 0 && a[i] == a[i-1]){
                        dp[a[i]] = false;
                        continue;
                }
                for(int x = 2;x*a[i]<1000050;x++){
                        dp[x*a[i]] = false;
                }

        }
        rep(i,n) if(dp[a[i]]) ans++;

        cout << ans << endl;

        return 0;
}


Measured memory_bytes: 5048
#include <bits/stdc++.h>
#define log(x) cout<<x<<endl
#define pb push_back
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;

int gcd(lint x, lint y){
  return y==0 ? x:gcd(y,x % y);
}

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

int dignum(int n) {
  int res = 0;
  while(n > 0) {
    res++;
    n /= 10;
  }
  return res;
}

int stringcount(string s, char c) {
  return count(s.cbegin(), s.cend(), c);
}

int lcm(lint x, lint y){
  return x/ gcd(x, y) * y;
}

int combi(int n, int r){
  int num = 1;
  for(int i = 1; i <= r; i++){
    num = num * (n - i + 1) / i;
  }
  return num;
}

int main(){
  string s;
  cin>>s;
  string result;
  for(int i=0;i<s.size();i++){
    if(s[i]=='?'){
      result+='D';
    }
    else{
      result+=s[i];
    }
  }
  cout<<result<<endl;
}

Measured memory_bytes: 3908
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

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

typedef long long ll;

using namespace std;

int main()
{
    int N;
    cin >> N;
    int d = 1;
    for(int i = 9; i >= 1; i--)
    {
        if(N % i == 0)
        {
            d = i;
            N = N / i;
            break;
        }
    }

    if(1 <= d && d <= 9 && 1 <= N && N <= 9)
        cout << "Yes" << endl;
    else 
        cout << "No" << endl;

    

    return 0;
}

Measured memory_bytes: 256
#include <iostream>

#define MAX_N 100

int N;
int A[MAX_N];

void bubble_sort() {
    int  counter=0;
    bool flag = true;
    while (flag) {
        flag = false;
        for (int j=N-1; j>=1; j--) {
            if (A[j] < A[j-1]) {
                std::swap(A[j], A[j-1]);
                counter++;
                flag = true;
            }
        }
    }

    for (int i=0; i<N-1; i++) std::cout << A[i] << ' ';
    std::cout << A[N-1] << std::endl;
    std::cout << counter << std::endl;
}

int main() {
    std::cin >> N;
    for (int i=0; i<N; i++) std::cin >> A[i];
    
    bubble_sort();

    return 0;
}



Measured memory_bytes: 3136
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args){

		solve_abcPpc_a();
	}
  
  	public static void solve_abcPpc_a(){

		Scanner sc = new Scanner(System.in);
		
		int[] a = {1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
		
		int K = sc.nextInt() - 1;

		System.out.println(a[K]);
		
		sc.close();
	}
}

Measured memory_bytes: 21332
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <bitset>
#include <utility>
#include <numeric>
#include <queue>

using ll = long long;
using namespace std;

constexpr int MOD = 1e9 + 7;
constexpr ll MOD_LL = ll(1e9) + 7;

int main(void) {
	string s;
	cin >> s;
	
	if( s[0] == s[1] || s[1] == s[2] || s[2] == s[3] ) cout << "Bad" << endl;
	else cout << "Good" << endl;
	
	return 0;
}


Measured memory_bytes: 256
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        FastScanner sc = new FastScanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        int n = sc.nextInt();
        int[] adresses= new int[n];
        for(int i=0; i<n; i++) adresses[i] = sc.nextInt();
        Arrays.sort(adresses);
        int dif = (adresses[n - 1] - adresses[0]);
        int ans = 0;
        if(dif % 2 == 0) ans = dif /2;
        else ans = dif / 2 + 1;
        out.println(ans);
        out.flush();

    }

    static class FastScanner {
        private BufferedReader reader = null;
        private StringTokenizer tokenizer = null;

        public FastScanner(InputStream in) {
            reader = new BufferedReader(new InputStreamReader(in));
            tokenizer = null;
        }

        public String next() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    return reader.readLine();
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }

            return tokenizer.nextToken("\n");
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 24804
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define MAX 510000
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

ll fac[MAX];
ll calc(ll a, ll b, ll p)
{
	if (b == 0) return 1;
	if (b % 2 == 0)
	{
		ll d = calc(a, b / 2, p);
		return (d * d) % p;
	}
	else
		return (a * calc(a, b - 1, p)) % p;
}
void COMinit(void)
{
	fac[0] = fac[1] = 1;
	for(int i = 2; i <= MAX; i++)
	{
		fac[i] = fac[i - 1] * i;
		fac[i] %= mod;
	}
}

ll nCr(ll n, ll r)
{
	if (n < r) return 0;
	ll denom = fac[r] * fac[n - r] % mod;
	return fac[n] * calc(denom, mod - 2, mod) % mod;
}

signed main(void)
{
	COMinit();
	int n, k;
	cin >> n >> k;
	vector<ll> vec(n);
	ll mx, mn;

	rep(i, n) cin >> vec[i];
	sort(vec.begin(), vec.end());
	mx = 0;
	for(int i = n - 1; i >= 0; i--)
	{
		mx += vec[i] * nCr(i, k - 1) % mod;
		mx %= mod;
	}
	reverse(vec.begin(), vec.end());
	mn = 0;
	rep(i, n)
	{
		mn += vec[i] * nCr(i, k - 1) % mod;
		mn %= mod;
	}
	ll ans = mx - mn;
	if (ans < 0) ans += mod;
	ans %= mod;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 4992
using System;
using System.Collections.Generic;
using System.Linq;

public class Hello
{
    private const ulong MOD9 = 1000000007;

    public static void Main()
    {
        var b = Console.ReadLine();
        switch (b[0])
        {
            case 'A':
                Console.WriteLine('T');
                break;
            case 'T':
                Console.WriteLine('A');
                break;
            case 'C':
                Console.WriteLine('G');
                break;
            case 'G':
                Console.WriteLine('C');
                break;
        }
    }
}


Measured memory_bytes: 11092
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		try (Scanner scanner = new Scanner(System.in)) {
			int result = 0;

			int a = scanner.nextInt();
			int b = scanner.nextInt();

			result = a < b ? a : b;

			int c = scanner.nextInt();
			int d = scanner.nextInt();

			result += c < d ? c : d;

			System.out.println(result);
		}
	}
}


Measured memory_bytes: 21716
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}

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

    ll N, M;
    cin >> N >> M;
    vec H(N);
    Rep (i, N) {
        cin >> H[i];
    }
    vector<bool> ans(N, true);
    while (M--) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        if (H[a] < H[b]) ans[a] =false;
        else if (H[a] == H[b]) {
            ans[a] = false;
            ans[b] = false;
        } else {
            ans[b] = false;
        }
    }

    ll cnt = 0;
    for (bool e : ans) {
        if (e) cnt++;
    }

    cout << cnt << endl;

}

Measured memory_bytes: 3944
#include <limits.h>
#include <stdio.h>
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <sstream>
#include <string>
#include <vector>

#include <bits/stdc++.h>

namespace test {
std::string to_string(char val) {
    return std::string(1, val);
    // return std::string{val};
}
}  // namespace test

using namespace std;

int main(void) {
    string s;
    cin >> s;
    int result1 = 0, result2 = 0;
    for (int i = 0; i < s.size(); i++) {
        if (i % 2 == 0) {
            if (s[i] - '0' == 0) {
                result1++;
            }
        } else {
            if (s[i] - '0' == 1) {
                result1++;
            }
        }

        if (i % 2 == 1) {
            if (s[i] - '0' == 0) {
                result2++;
            }
        } else {
            if (s[i] - '0' == 1) {
                result2++;
            }
        }
    }

    cout << min(result1, result2) << endl;

    return 0;
}

Measured memory_bytes: 512
from itertools import combinations

n = int(input())
r = range(n)
a = [(set(), set()) for _ in r]
for i in r:
  for _ in range(int(input())):
    x, y = map(int, input().split())
    a[i][y].add(x - 1)

fail = lambda x: not all(a[i][0].isdisjoint(x) and a[i][1] < x for i in x)

while all(map(fail, map(set, combinations(r, n)))):
  n -= 1
print(n)


Measured memory_bytes: 3064
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

#define ll long long

int main()
{
    ll N;
    ll sum = 0;
    std::cin >> N;

    std::map<ll, ll>A;

    for(ll i=0; i < N; i++) {
        ll x;
        std::cin >> x;
        sum += x;
        A[x]++;
    }
    
    ll Q;
    std::cin >> Q;
    ll q = Q;
    std::vector<ll> sum_list(Q);
    ll i = 0;

    while(q > 0) {
        //std::cout << "!??" << std::endl;
        ll B, C;
        std::cin >> B;
        std::cin >> C;
        ll diff = C - B;
        sum += diff * A[B];
        A[C] += A[B];
        A[B] = 0;
        sum_list[i] = sum;
        i++;
        q--;
    }

    for(ll j=0; j < Q; j++) {
        std::cout << sum_list[j] << std::endl;
    }
}

Measured memory_bytes: 9948
N, M = list(map(int, input().split(" ")))

e = [[] for i in range(N)]

for i in range(M):
    a, b = list(map(int, input().split(" ")))
    a-=1
    b-=1
    e[a].append(b)
    e[b].append(a)

ch = [False for i in range(N)]
right = []
ch[0]=True

now = 0
while 1:
    for i in e[now]:
        if ch[i] == False:
            ch[i] = True
            now = i
            right.append(i)
            break
    else:
        break

left = []

now = 0
while 1:
    for i in e[now]:
        if ch[i] == False:
            ch[i] = True
            now = i
            left.append(i)
            break
    else:
        break

res = left[::-1] + [0] + right
for i in range(len(res)):
    res[i] = str(res[i]+1)
print(len(res))
print(" ".join(res))


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

int main() {
	int a[4];
	int sum = 0;
	for(int i = 0; i < 4; ++i) {
		cin >> a[i];
		sum += a[i];
	}
	int ans = 1e9;
	for(int i = 0; i < 4; ++i) {
		for(int j = i + 1; j < 4; ++j) {
			ans = min(ans, abs(2 * (a[i] + a[j]) - sum));
		}
	}
	cout << ans << '\n';
	return 0;
}


Measured memory_bytes: 3112
x, k, d = map(int, input().split())

if abs(x) > k*d:
    res = abs(x) - k*d
else:
    # res = min(abs(x%d), abs((x%d)-d))
    res = (k*d - abs(x)) % (d*2)
    # res = abs((k*d)%x)
    if abs(x%d) <= abs((x%d)-d):
        k -= x // d
        if k % 2 == 0:
            res = abs(x%d)
        else:
            res = abs((x%d)-d)
    else:
        k -= x // d - 1
        if k % 2 == 0:
            res = abs((x%d)-d)
        else:
            res = abs(x%d)
print(res)


Measured memory_bytes: 9164
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

//partial_permutation nPr 順列
//first・・最初の数
//middle・・r(取り出す数)
//last・・n(全体数)
template<class Iter>
bool next_partial_permutation(Iter first, Iter middle, Iter last) {
    reverse(middle, last);
    return next_permutation(first, last);
}

int main() {

    long long N, C;
    cin >> N >> C;

    vector<vector<long long>> D(C, vector<long long>(C));
    for (int i = 0; i < C; i++)for (int j = 0; j < C; j++) cin >> D[i][j];

    vector<vector<long long>> c(N, vector<long long>(N));
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) cin >> c[i][j], c[i][j]--;

    vector<vector<long long >> A(3, vector<long long>(C, 0));
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) A[(i + j) % 3][c[i][j]]++;

    vector<long long> B(C);
    for (int i = 0; i < C; i++) B[i] = i;

    long long ans = LONG_LONG_MAX;
    do {
        long long sum = 0;
        for (int i = 0; i < 3; i++)for (int j = 0; j < C; j++)sum += D[j][B[i]] * A[i][j];
        ans = min(ans, sum);
    } while (next_partial_permutation(B.begin(), B.begin() + 3, B.end()));

    cout << ans << endl;

    return 0;
}














































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

using namespace std;

bool digit(char n){
  if('0' <= n && n <= '9') return true;
  else return false;
}

int main(void){
  int a, b;
  string str;
  bool ok = true;
  
  cin >> a >> b;
  cin >> str;
 
  for(int i = 0;i < a;i++){
    if(!digit(str[i])) ok = false;
  }
  
  if(str[a] != '-') ok = false;
  
  for(int i = a+1;i < a+1+b;i++){
    if(!digit(str[i])) ok = false;
  }
  
  cout << (ok ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
a = list(map(int,input().split()))

flag = 0
if a[0] == a[1] and a[1] == a[2] and a[0] == a[2]:
  flag = 1
elif a[0] != a[1] and a[1] != a[2] and a[0] != a[2]:
  flag = 1
  
if flag == 1:
  print("No")
else:
  print("Yes")


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

int main() {
  int a,b,c,d;
  int left,right;
  cin >> a >> b >> c >> d;
  left = a + b;
  right = c + d;
  if(left < right) cout << "Right" << endl;
  else if(left > right) cout << "Left" << endl;
  else cout << "Balanced" << endl;
}

Measured memory_bytes: 256
a,b,c,d=map(int,input())
if a+b+c+d==7:
    print(str(a)+'+'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
elif a+b+c-d==7:
    print(str(a)+'+'+str(b)+'+'+str(c)+'-'+str(d)+'=7')
elif a+b-c+d==7:
    print(str(a)+'+'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
elif a-b+c+d==7:
    print(str(a)+'-'+str(b)+'+'+str(c)+'+'+str(d)+'=7')
elif a+b-c-d==7:
    print(str(a)+'+'+str(b)+'-'+str(c)+'-'+str(d)+'=7')
elif a-b+c-d==7:
    print(str(a)+'-'+str(b)+'+'+str(c)+'-'+str(d)+'=7')
elif a-b-c+d==7:
    print(str(a)+'-'+str(b)+'-'+str(c)+'+'+str(d)+'=7')
elif a-b-c-d==7:
    print(str(a)+'-'+str(b)+'-'+str(c)+'-'+str(d)+'=7')

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

int main(){
  int A,B,C;
  cin >> A >> B >> C;
  int D=0;
  int E=0;
  if(A==5){
    D++;
  }
  else if(A==7){
    E++;
  }
  if(B==5){
    D++;
  }
  else if(B==7){
    E++;
  }
  if(C==5){
    D++;
  }
  else if(C==7){
    E++;
  }
  if(D==2&&E==1){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>  // clang-format off
using Int = long long;
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Sat Jun 13 21:41:36 JST 2020
 **/

template <class T, class S> T make_vec(S x) { return x; }
template <class T, class... Ts> auto make_vec(size_t n, Ts... ts) {
    return std::vector<decltype(make_vec<T>(ts...))>(n, make_vec<T>(ts...));
}

const Int B = 19;
signed main() {
    auto comb = make_vec<Int>(55, 55, 0);
    REP(i, 55 - 1) {
        comb[i][0] = 1;
        REP(j, i + 1) { comb[i + 1][j + 1] = comb[i][j] + comb[i][j + 1]; }
    }
    auto acc = make_vec<Int>(56, 56, 0);
    REP(i, 55) {
        REP(j, i + 1) { acc[i][j + 1] = acc[i][j] + comb[i][j]; }
    }
    auto calc = [&](Int n, Int r) { return std::max(0LL, acc[n][std::min(n, r) + 1] - 1); };
    Int n, K, s, t;
    std::cin >> n >> K >> s >> t;
    std::vector<Int> a(n);
    REP(i, n) std::cin >> a[i];
    std::vector<Int> bits;
    REP(k, B) {
        Int x = s >> k & 1, y = t >> k & 1;
        if (x == 1) {
            for (Int i = (Int)a.size() - 1; i >= 0; i--) {
                if ((a[i] >> k & 1) == 0) a.erase(a.begin() + i);
            }
        } else if (y == 0) {
            for (Int i = (Int)a.size() - 1; i >= 0; i--) {
                if ((a[i] >> k & 1) == 1) a.erase(a.begin() + i);
            }
        } else {
            bits.push_back(k);
        }
    }

    Int m = bits.size();
    std::vector<Int> b(a.size());
    REP(i, a.size()) {
        REP(j, m) { b[i] |= (a[i] >> bits[j] & 1) << j; }
    }

    __int128_t ans = 0;
    REP(S, 1 << m) {
        std::unordered_map<Int, Int> mp;
        for (Int x : b) mp[x & S]++;
        Int cnt = 0;
        for (auto& p : mp) cnt += calc(p.second, K);
        ans += cnt * (__builtin_popcount(S) % 2 ? -1 : 1);
    }
    std::cout << (Int)ans << std::endl;
}


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

const int mo=int(1e9+7);
int n,m,f[3010][3010][2],ans;

void upd(int &x,int y){if ((x+=y)>=mo)  x-=mo;}

void work()
{
	scanf("%d %d",&n,&m);
	for (int i=1; i<=n; i++)  f[0][i][0]=1;
	f[0][0][1]=1;
	for (int i=0; i<m; i++)
		for (int j=0; j<=n; j++)
			for (int k=0; k<2; k++)
				if (f[i][j][k])
					{
						if (j>1)
							{
								upd(f[i+1][j-1][k],f[i][j][k]);
								upd(f[i+1][j][k],f[i][j][k]);
							}else  if (j==1)
							{
								upd(f[i+1][0][1],f[i][j][k]);
								upd(f[i+1][1][1],f[i][j][k]);
							}
						if (j<=n-1)
							{
								upd(f[i+1][j+1][k],f[i][j][k]);
								upd(f[i+1][j][k],f[i][j][k]);
							}
					}
	for (int i=0; i<=n; i++)  upd(ans,f[m][i][1]);
	printf("%d",ans);
}

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


Measured memory_bytes: 70784