akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <cmath>

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e10;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;


int main() {

    int a, b;
    cin >> a >> b;


    cout << a * b - a - b + 1 << endl;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define yorn(f) cout<<((f)?"Yes":"No")<<endl
#define YORN(f) cout<<((f)?"YES":"NO")<<endl
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define println(x) cout << x << endl
using namespace std;
int main()
{
    string s;
    cin >> s;
    cout << "2018" << s.substr(4) << endl;
    return 0;
}

Measured memory_bytes: 3624
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    a = list(map(int, input().split()))

    MAX = int(1e5)
    count = [0] * (MAX + 1)

    for t in a:
        if t > 0:
            count[t-1] += 1
        if t < MAX:
            count[t+1] += 1
        count[t] += 1
    
    max_ = count[0]
    for i in range(1, MAX+1):
        max_ = max(max_, count[i])
    print(max_)

if __name__ == "__main__":
    main()

Measured memory_bytes: 13304
#include<iostream>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if((a>=1 && a<=9) && (b>=1 && b<=9)){
        cout<<a*b<<endl;
    }
    else{
        cout<<-1<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int maxN = 2e5 + 55;

int x;

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

    cin >> x;

    ll a = x / 500;
    x %= 500;

    ll b = x / 5;
    x %= 5;

    cout << a * 1000 + b * 5 << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<iostream>

int main(){
    int n,min,max,value;
    std::cin >> n;
    int a[n];
    std::cin >> a[0] >> a[1];
    if (a[0]>a[1]) min = a[1];
    else min = a[0];
    value = a[1] - a[0];
    max = value;
    for (int i=2; i<n; i++){
        std::cin >> a[i] ;
        if (min>a[i]){
            min = a[i];
        }else{
            value = a[i] - min;
            if (value>max){
                max = value;
            }
        }
    }
    
    std::cout << max << '\n';
    return 0;
}



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

using namespace std;
#define ll long long
#define endl '\n'
int main()
{
double a,b;
cin>>a>>b;
double temp=(a+b)/2;
ceil(temp)==floor(temp)?cout<<setprecision(10)<<temp<<endl:cout<<"IMPOSSIBLE"<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

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

using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;

const ll inf = 1e16;

ll solve(ll x, ll y) {
  return x <= y ? y - x : inf;
}

int main(void){
  ll x, y;
  cin >> x >> y;
  ll mi = solve(x, y);
  mi = min(mi, solve(x, -y) + 1);
  mi = min(mi, solve(-x, y) + 1);
  mi = min(mi, solve(-x, -y) + 2);
  cout << mi << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define MOD 100000
using namespace std;

int main(){
  int n,m;
  int d[100000],a,cnt[100000] = {};
  cin >> n >> m;
  for(int i = 0;i < n - 1;i++) cin >> d[i];
  int now = 0;
  for(int i = 0;i < m;i++){
    cin >> a;
    for(int j = min(now,now + a);j < max(now,now + a);j++){
      cnt[j]++;
    }
    now = now + a;
  }
  int res = 0;
  for(int i = 0;i < n - 1;i++){
    res = (res + d[i] * cnt[i]) % MOD;
  }
  cout << res << endl;
  return 0;
}

Measured memory_bytes: 3872
n = int(input())
A = [int(input()) for i in range(n)]
B = A[:]

D = {}
A.sort()
for i in range(n):
    D[A[i]] = i

for i in range(n):
    B[i] = D[B[i]]

# print(B)
ans = 0
for i in range(n):
    if i % 2 != B[i] % 2:
        ans += 1
print((ans+1) // 2)

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


int solve(void){
  int N;
  
  cin >> N;
  
  int num[N-1];
  for(int i=0; i<N-1; i++){
    cin >> num[i];

  }
  
  int ans = 0;
  ans += num[0];
  ans += num[N-2];
  

  
  if (N != 2){
    for(int i=0; i<N-2; i++){
      ans += min(num[i], num[i+1]);
    }
  }
  
  cout << ans << endl;
  return ans;
}


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

Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <cassert>
#include <typeinfo>
#include <vector>
#include <stack>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#include <random>
#include <complex>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef vector<pll> vpll;
typedef pair<P,int> pip;
typedef vector<pip> vip;
const int inf=1<<30;
const ll INF=1ll<<62;
const double pi=acos(-1);
const double eps=1e-7;
const ll mod=1e9+7;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

string s;

int main(){
	cin>>s;
	for(int i=0;i<s.size()-1;i++){
		if(s.substr(i,2)=="AC"){
			cout<<"Yes"<<endl;
			return 0;
		}
	}
	cout<<"No"<<endl;
}

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

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
		String w1 = b.readLine();
		String w2 = b.readLine();
		String s1 = Arrays.stream(w1.split("")).sorted().collect(Collectors.joining());
		String s2 = Arrays.stream(w2.split("")).sorted(Comparator.reverseOrder()).collect(Collectors.joining());
		String a = s2.compareTo(s1) > 0 ? "Yes" : "No" ;
		System.out.println(a);
	}
}

Measured memory_bytes: 28500
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) x
#define WATCH(x) TRACE( cout << #x" = " << x << endl)
#define PRINT(x) TRACE(printf(x))
#define WATCHR(a, b) TRACE( for(auto c = a; c != b;) cout << *(c++) << " "; cout << endl)
#define WATCHC(V) TRACE({cout << #V" = "; WATCHR(V.begin(), V.end()); } )
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x).size()
#define mp make_pair
#define st first
#define nd second

using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using ld = long double;
using pll = pair<ll, ll>;
using vll = vector<ll>;
using pll = pair<ll, ll>;

void buff() { ios::sync_with_stdio( false ); cin.tie( nullptr ); }

constexpr ll MOD = 1e9 + 7;

inline ll pow_mod( ll a, ll b, ll mod = 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;
}
// End of template code!
int main() 
{
    buff();
    int len; cin >> len; 
    string s, t;
    cin >> s >> t;
    for(int i = 0; i < len; ++i) {
        cout << s[i] << t[i];
    }
    return 0;
}



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

int main() {
  int H, W;
  int j;
  while (true) {
    cin >> H >> W;
    if (H == 0 && W == 0) return 0;
    for (int i = 0; i < H; i++) {
      for (int j = 0; j < W; j++) {
        if ((i + j) % 2 == 0)
          cout << "#";
        else
          cout << ".";
      }   
      cout << endl;
    }   
    cout << endl;
  }
}

Measured memory_bytes: 3076
#include <iostream>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <string.h>
#include <vector>
#include <queue>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <numeric>
#include <iomanip>

// output
#define SPBR(w, n) std::cout<<(w + 1 == n ? '\n' : ' ');
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
// utility
#define ALL(i) (i).begin(), (i).end()
#define FOR(i, a, n) for(int i=(a);i<(n);++i)
#define RFOR(i, a, n) for(int i=(n)-1;i>=(a);--i)
#define REP(i, n) for(int i=0;i<int(n);++i)
#define RREP(i, n) for(int i=int(n)-1;i>=0;--i)
#define IN(a, x, b) (a<=x && x<b)
#define OUT(a, x, b) (x<a || b<=x)
template<class T> inline T chmax(T & a, const T b) { return a = (a < b) ? b : a; }
template<class T> inline T chmin(T& a, const T b) { return a = (a > b) ? b : a; }

// type/const
#define int ll
using ll = long long;
using ull = unsigned long long;
using ld = long double;
const int MOD = 1000000007;
/* const int MOD = 998244353; */
const int INF = 1e18;
const double PI = acos(-1);

using namespace std;
struct INIT { INIT(){
  cin.tie(0); ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
}}INIT;


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

  vector<int> A(N);
  REP(i, N) cin >> A[i];

  int ans = 0;
  if(A[0] > K){
    ans += A[0]-K;
    A[0] = K;
  }
  FOR(i, 1, N){
    if(A[i-1]+A[i] > K){
      ans += (A[i-1]+A[i])-K;
      A[i] -= (A[i-1]+A[i])-K;
    }
  }

  cout << ans << "\n";

  return 0;
}

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

using ll = long long;
using ld = long double;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define sz(v) (int)v.size()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return false;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
const char EOL = '\n';

void solve();

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

void solve() {
    int a, b, c, d, e, f;
    cin >> a >> b >> c >> d >> e >> f;
    int ans = 0;
    int anss = 0;
    double mx = 0;
    REP(i, 31) {
        REP(j, 31) {
            int w = i * a * 100 + j * b * 100;
            if (w > f) break;
            REP(k, 3000) {
                REP(l, 3000) {
                    int s = c * k + d * l;
                    if (s > w / 100 * e) break;
                    if (s + w > f) break;
                    if (chmax(mx, (100.0 * s) / (w + s))) {
                        ans = w + s;
                        anss = s;
                    }
                }
            }
        }
    }
    cout << (ans == 0 ? 100 * a : ans) << " " << anss << EOL;
}



Measured memory_bytes: 256
#include<bits/stdc++.h> 
using namespace std;
struct P{int a,b;}q[200005];
int k,l=100000,r=100000;
bool book[100005];
int main(){
    scanf("%d", &k);
    q[l]={1,1};
    while(l<=r){
    	P x=q[l++];
        if(book[x.a]) continue; book[x.a]=1;
        if(x.a==0){printf("%d\n",x.b);break;}
        q[--l]={x.a*10%k,x.b};
        q[++r]={(x.a+1)%k,x.b+1};
    }
}
//首先我们会发现，任意一个数可以由1开始+1（数字总和+1）或*10（数字总和不变）来得到
//（x9+1是特例，但x9+1明显可以由更优的(x+1)0得到） 
//所以我们可以把数字看成一个个图，起点为x=1，那么按照x到x+1的边权为1 ，x到x*10的边权为0建图 
//那么我们的目标是什么呢？我们发现只要我们凑出一个数x，使x为k的倍数即可，那我们对于一个数字，如果它连向的数字为k的倍数
//我们就让它连向0，最终我们求的就是1到0的最短路
//这是一个01bfs，我们可以使用双端队列来解决 
//时间复杂度O(k) 

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
using namespace std;
#define rep(i,x) for(int i = 0; i < x; i++)
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int,int> P;
typedef pair<ll,ll> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<vector<vector<int>>> vvvi;
const ll N = 1e9+7;
const int n_max = 1e5+10;

int main(){
    int n,w_max; cin >> n >> w_max;
    vector<int> v(n),w(n);
    rep(i,n) cin >> v[i] >> w[i];
    int dp[110][10100] = {};
    rep(i,n+1){
        if(!i)continue;
        rep(j,w_max+1){
            if(j >= w[i-1])dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]] + v[i-1]);
            else dp[i][j] = dp[i-1][j];
        }
    }

    cout << dp[n][w_max] << endl;
    return 0;

}


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

int main()
{
    int a,b;
    cin >> a >> b;
    if(a > b) swap(a,b);
    i64 c = 0;
    rep(i,b) c = c*10 + a;

    cout << c << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <math.h>
using namespace std;
int main(void){
    int a, b;
    int out;
    cin >> a >> b;
    out = b;
    if (b == 100){
        out++;
    }
    for (int i = 0; i < a; ++i){
        out *= 100;
    }
    cout << out << endl;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();

        int frag = x % 100;
        int num = x / 100;
        if (frag <= num * 5) {
            System.out.println(1);
        } else {
            System.out.println(0);
        }

        sc.close();
    }

}


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

const int INF = INT_MAX / 2;

int main() {
    ll N; cin >> N;
    vector<ll> dist(N, INF);
    vector<vector<pair<ll,ll>>> G(N);
    for (int i = 0; i < N-1; i++)
    {
        int a, b, c; cin >> a >> b >> c;
        a--; b--;
        G[a].push_back(make_pair(c, b));
        G[b].push_back(make_pair(c, a));
    }
    ll Q, K; cin >> Q >> K;
    K--;

    dist[K] = 0;
    queue<ll> pos;
    pos.push(K);
    while (!pos.empty())
    {
        ll from = pos.front(); pos.pop();
        for (auto to: G[from])
        {
            if(dist[to.second]!=INF) continue;
            dist[to.second] = dist[from] + to.first;
            pos.push(to.second);
        }
    }
    
    for (int i = 0; i < Q; i++)
    {
        ll x, y; cin >> x >> y;
        x--; y--;
        cout << dist[x] + dist[y] << endl;
    }
    
}

Measured memory_bytes: 10240
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll n, m, ans, cnt;
string s;
int a[100010];
map<int,int> mp;

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

  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  while (1) {
    bool f = 0;
    for (int i = 0; i < n; i++) {
      if (a[i] != 0) {
        for (int j = i; j < n; j++) {
          if (a[j] != 0) a[j]--;
          else break;
        }
        cnt++;
        f = 1;
        break;
      }
    }
    if (!f) {
      cout << cnt << endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 256
l,r = map(int,input().split())
if r-l>=2019:
  print(0)
  exit()
l = l%2019
r = r%2019
ans = 2018
for i in range(l,r):
  for j in range(l+1,r+1):
    ans = min(ans,i*j%2019)
print(ans)

Measured memory_bytes: 3064
import sys
X, N = map(int, input().split())
p = list(map(int, input().split()))
P = set(p)
a = 1000
c = -101
if N == 0:
    print(X)
    sys.exit()
if X not in P:
    print(X)
    sys.exit()
for i in range(-1, 102):
    if i in P:
        continue
    if abs(i - X) == a:
        c = min(c, i)
    elif abs(i - X) < a:
        c = i
        a = abs(i - X)
print(c)

Measured memory_bytes: 9200
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


int main(){
  lll ii,jj,kk;
  vector<int> ret;

  int n,m;


  cin >> n >> m;

  vector<int> a(m);  
  lll sum = 0;
  for(ii=0;ii<m;ii++){
    cin >> a[ii];
    sum += a[ii];
  }
  if(sum <= n){
    cout << (n - sum) << endl;
  }
  else{
    cout << -1 << endl;;
  }
  return 0;
}


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

int n;

string a[10] = {"", ".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

int main(){
//	cin.tie(0);
//	ios::sync_with_stdio(false);
	cin >> n;
	for(int i=0; i<n; ++i){
		string s;
		cin >> s;
		string t;
		for(int i=0; i<s.size(); ++i){
			char c = s[i];
			int j = i;
			while(c == s[i]) ++i;
			if(c != '0') t += a[c-'0'][(i-j-1)%(int)(a[c-'0'].size())];
			else --i;
		}
		cout << t << "\n";
	}
}


Measured memory_bytes: 3044
/*

    HARSH KHATRI
    DA-IICT     

		 */

           	 

#include <bits/stdc++.h>

#define LOCAL 0
bool debug = true;

using namespace std;

int main(void) {
	
	if(LOCAL) {
    	freopen("in.txt", "r", stdin);
	    freopen("out.txt", "w", stdout);
	}

	int i, j, k, x, y, s, f, n, m, cnt = 0;
	scanf("%d %d", &n, &m);
	vector<pair<int, int>> q;

	for(i=0; i<m; i++) {
	 	scanf("%d %d", &x, &y); x--; y--;
		q.push_back(make_pair(min(x,y), max(x,y)));
	}
	sort(q.begin(), q.end(), [](pair<int, int>& l, pair<int, int>& r) {
	   	if(l.first==r.first) return l.second<r.second;
		else return l.first<r.first;
	});
	
	for(i=0; i<m; i++) {
		x = q[i].first; y = q[i].second;
		j = i+1; 
		while(j<m && q[j].first<y) { y = min(y, q[j].second); j++; }
		if(j==m) j--;
		if(q[j].first>=y) j--;
		cnt++;
		i = j;			 	
	}	

	printf("%d\n", cnt);
}

Measured memory_bytes: 1528
#define	_USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cfloat>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <string>
#include <set>
using namespace std;
int main(){
	
	bool p[50001]={false};
	
	p[2]=true;
	for(int i=3;i<50001;i+=2){
		bool f=false;
		for(int j=3;j<=sqrt(i);j+=2){
			if(i%j==0){
				f=true;
				break;
			}
		}
		if(!f)
			p[i]=true;
	}
	
	int n;
	while(cin>>n,n!=0){
		int count=0;
		for(int i=0;i<=n/2;i++){
			if(p[n-i]&&p[i]){
			count++;
			}
			
		}
		
					
				
		cout<<count<<endl;
	}
	
	
	
}

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

int main() {
	
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    
    long long n,m,k,count=0,ans=0,sum=0,l,r,i,j,x,y;
    cin>>n>>k;
 
    for(i=0;i<=n;i++)
    {
        if((i*2+(n-i)*4)==k)
        count=1;
    }
    if(count==1)
    cout<<"Yes";
    else
    cout<<"No";
	return 0;
}

Measured memory_bytes: 3652
#include<iostream>
#define R(i,n)for(int i=0;i<=n;i++)
using namespace std;
int a,H,W,A,c[10][10];
main(){
cin>>H>>W;
R(i,9)R(j,9)
  cin>>c[i][j];
R(k,9)R(i,9)R(j,9)c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
R(i,H-1)R(j,W-1){
cin>>A;
a+=c[A>=0?A:1][1];
}
cout<<a;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
char num[1010101]; int arr[1010101],ans;
main()
{
	scanf("%s",num);
	int len=strlen(num);
	for(int i=0;i<len;i++) arr[i+1]=num[i]-'0';
	for(int i=len;i>=1;i--)
	{
		if(arr[i]<5) ans+=arr[i], arr[i]=0;
		else if(arr[i]==5)
		{
			if(arr[i-1]<5) ans+=arr[i], arr[i]=0;
			else ans+=10-arr[i], arr[i]=0, arr[i-1]++;
		} else
		{
			ans+=10-arr[i]; arr[i]=0; arr[i-1]++;
		}
	} ans+=arr[0]; printf("%d",ans);
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=200005;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while (!isdigit(ch)&&ch!='-')
		ch=getchar();
	if (ch=='-')
		f=-1,ch=getchar();
	while (isdigit(ch))
		x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x*f;
}
int n,Len,T;
int x[N],w[N],res[N];
vector <int> v1,v2;
int s1,s2;
bool check(int x){
	int L,R;
	if (!w[0])
		L=(x-1)>>1,R=x>>1;
	else
		L=x>>1,R=(x-1)>>1;
	LL tot=1LL*(L/s1)*Len+v1[L%s1]
		  +1LL*(R/s2)*Len+v2[R%s2];
	return tot<=(T<<1);
}
int main(){
	n=read(),Len=read(),T=read();
	v1.clear();
	v2.clear();
	for (int i=0;i<n;i++){
		x[i]=read(),w[i]=read()&1;
		if (w[i])
			res[i]=(x[i]+T)%Len;
		else
			res[i]=((x[i]-T)%Len+Len)%Len;
		if (!w[i])
			v2.push_back(x[i]-x[0]);
		else
			v1.push_back((x[0]-x[i]+Len)%Len);
	}
	if (v1.empty()||v2.empty()){
		for (int i=0;i<n;i++)
			printf("%d\n",res[i]);
		return 0;
	}
	sort(res,res+n);
	sort(v1.begin(),v1.end());
	s1=v1.size(),s2=v2.size();
	int L=1,R=T<<1,ans=0;
	while (L<=R){
		int mid=(L+R)>>1;
		if (check(mid))
			L=mid+1,ans=mid;
		else
			R=mid-1;
	}
	int p0;
	if (ans==0)
		p0=w[0]?(x[0]+T)%Len:(x[0]+Len-T)%Len;
	else {
		if (!w[0])
			L=(ans-1)>>1,R=ans>>1;
		else
			L=ans>>1,R=(ans-1)>>1;
		int tot=L/s1*Len+v1[L%s1]+R/s2*Len+v2[R%s2];
		T=(T<<1)-tot;
		LL p=(R/s2*Len+v2[R%s2])-(L/s1*Len+v1[L%s1]);
		if (w[0]^(ans&1))
			p+=T;
		else
			p-=T;
		p/=2;
		p0=((p+x[0])%Len+Len)%Len;
	}
	int p=lower_bound(res,res+n,p0)-res;
	if (w[0]^(ans&1)){
		if (n>2&&res[(p+1)%n]==res[p])
			p=(p+1)%n;
	}
	else
		if (n>2&&res[(p+n-1)%n]==res[p])
			p=(p+n-1)%n;
	for (int i=0;i<n;i++)
		printf("%d\n",res[(p+i)%n]);
	return 0;
}

Measured memory_bytes: 2892
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<ll,ll> P;

void Main() {
  ll r;
  R r;
  pr(r*r);
}

int main(){ios::sync_with_stdio(0);cin.tie(0);Main();return 0;}


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

int gcd(int a, int b) {
  if(a < b) return gcd(b, a);
  int r;
  while ((r=a%b)) {
    a = b;
    b = r;
  }
  return b;
}

int main(){
  int N,X;
  cin >>N >>X;
  int x[N+1];
  for (int i=0;i<N;i++){
    cin >>x[i];
  }
  x[N]=X;
  sort(x,x+N);
  int ans=x[1]-x[0];
  for (int i=0;i<N;i++){
    ans=gcd(ans,x[i+1]-x[i]);
  }
  cout<<abs(ans)<<endl;
  return 0;
}


Measured memory_bytes: 640
#include<iostream>
#include<vector>
using namespace std;
int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,919,929,937,941,947,953,967,971,977,983,991,997};
int main(){
  int n;
  cin >> n;
  long long ans=1;
  vector<long long> q(168,1);
  for(int i=1;i<=n;i++){
    for(int j=0;j<168&&p[j]<=i;j++){
      int tmp=i,cnt=0;
      while(tmp%p[j]==0){
        tmp/=p[j];
        cnt++;
      }
      q[j]+=cnt;
    }
  }
  for(int i=0;i<168;i++){
    ans=(ans*q[i])%1000000007;
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long LL;
#define SORT(c) sort((c).begin(),(c).end())

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

using namespace std;
int main(void)
{
  for(;;){
    int n;
    cin >> n;
    if(!n) return 0;
    vector<int> a,b;
    a.resize(n);
    b.resize(n);
    REP(i,n) cin >> a[i] >> b[i];
    int asum=0,amax=0,bsum=0;
    REP(i,n){
      asum+=a[i];
      amax=max(amax,a[i]);
      bsum+=b[i];
    }
    int dp[4096];
    REP(i,2048) dp[i]=0;
    dp[0]=1;
    REP(i,n) for(int j=1000;j>=0;--j){
      if(a[i]==amax) continue;
      if(dp[j]){
	dp[j+a[i]]+=dp[j];
	dp[j+a[i]+b[i]]+=dp[j];
      }
    }
    int answer=asum+bsum;
    if(asum<amax*2){
      for(int i=amax;dp[i]==0;--i) answer++;
    }
    cout << answer << endl;
    


  }
}

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

using namespace std;

int main(){

    int x,y;
    while(scanf("%x %x",&x,&y)!=EOF){
        if(x>y) printf(">");
        else if(x<y)printf("<");
        else printf("=");

        printf("\n");
    }
    return 0;
}


Measured memory_bytes: 256
// B - YYMM or MMYY

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const int MOD = 1e9 + 7;

int main() {
	string S;
	cin >> S;

	string left = S.substr(0, 2);
	string right = S.substr(2, 2);

	string ans;
	if (left >= "01" && left <= "12") {
		if (right >= "01" && right <= "12") {
			ans = "AMBIGUOUS";
		} else {
			ans = "MMYY";
		}
	} else {
		if (right >= "01" && right <= "12") {
			ans = "YYMM";
		} else {
			ans = "NA";
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())
l=[a,b,c,d,e]
lastindex=0
tenmod=[a%10,b%10,c%10,d%10,e%10]
times=tenmod.count(0)
if times!=0:
  for i in range(times):
    tenmod.remove(0)
if times!=5:
  key=min(tenmod)
else:
  key=0
alltime=0
lastflag=0
for i in range(5):
  if l[i]%10==0:
    alltime+=l[i]
  elif l[i]%10==key and lastflag==0:
    alltime+=l[i]
    lastflag+=1
  else:
    alltime+=int(l[i]/10)*10+10
print(alltime)


Measured memory_bytes: 3064
#include <iostream>
using namespace std;
int main(){
    int h,n,sum=0;
    cin >> h >> n;
    for(int i=0;i<n;i++){
        int t;
        cin >> t;
        sum += t;
    }
    if(h <= sum){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>

using namespace std;

int h, w, s;
int p[32][32], sum[32][32];
pair<int, int> dp[32][32][32][32];

int getSum(int sy, int sx, int gy, int gx)
{
	int ret = sum[gy][gx];
	if (sy) ret -= sum[sy - 1][gx];
	if (sx) ret -= sum[gy][sx - 1];
	if (sy && sx) ret += sum[sy - 1][sx - 1];
	
	return (ret);
}

pair<int, int> calc(int sy, int sx, int gy, int gx)
{
	if (~dp[sy][sx][gy][gx].first) return (dp[sy][sx][gy][gx]);
	
	int cost = sum[h - 1][w - 1] - getSum(sy, sx, gy, gx);
	if (cost > s) return make_pair(0, -1);
	pair<int, int> res = make_pair(1, -cost);
	pair<int, int> a, b, c;
	
	for (int i = sy; i <= gy - 1; i++){
		a = calc(sy, sx, i, gx); b = calc(i + 1, sx, gy, gx);
		if (a.first == 0 || b.first == 0) continue;
		c = make_pair(a.first + b.first, min(a.second, b.second));
		if (res < c) res = c;
	}
	
	for (int i = sx; i <= gx - 1; i++){
		a = calc(sy, sx, gy, i); b = calc(sy, i + 1, gy, gx);
		if (a.first == 0 || b.first == 0) continue;
		c = make_pair(a.first + b.first, min(a.second, b.second));
		if (res < c) res = c;
	}
	
	return (dp[sy][sx][gy][gx] = res);
}

int main()
{
	while (scanf("%d %d %d", &h, &w, &s) && w){
		for (int i = 0; i < h; i++)
			for (int j = 0; j < w; j++)
				scanf("%d", &p[i][j]);
		
		for (int i = 0; i < 32; i++)
			for (int j = 0; j < 32; j++)
				for (int k = 0; k < 32; k++)
					for (int l = 0; l < 32; l++)
						dp[i][j][k][l].first = dp[i][j][k][l].second = -1;
		
		memset(sum, 0, sizeof(sum));
		
		for (int i = 0; i < h; i++){
			for (int j = 0; j < w; j++){
				sum[i][j] += p[i][j];
				if (i) sum[i][j] += sum[i - 1][j];
				if (j) sum[i][j] += sum[i][j - 1];
				if (i && j) sum[i][j] -= sum[i - 1][j - 1];
			}
		}
		
		pair<int, int> res = calc(0, 0, h - 1, w - 1);
		printf("%d %d\n", res.first, s + res.second);
	}
	
	return (0);
}

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

struct P{
	int x,y;
};
bool e[5001][5001];

bool exist(int x,int y){
	if(x<0||5000<x||y<0||5000<y)return false;
	return e[x][y];
}
int main(){
	int n;
	P pole[3000];
	while(cin>>n,n){
		int ans=0;
		memset(e,false,sizeof(e));
		for(int i=0;i<n;i++){
			int x,y;
			cin>>x>>y;
			pole[i].x=x;
			pole[i].y=y;
			e[x][y]=true;
		}
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				int dx,dy;
				dx=pole[i].x-pole[j].x;
				dy=pole[i].y-pole[j].y;
				if(exist(pole[i].x+dy,pole[i].y-dx) && exist(pole[j].x+dy,pole[j].y-dx)
					|| exist(pole[i].x-dy,pole[i].y+dx) && exist(pole[j].x-dy,pole[j].y+dx))
				{
					ans = max(ans,dx*dx+dy*dy);
				}
			}
		}
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 25616
#include <stdio.h>
#include <string.h>
int main()
{
    char o[50],e[50],s[100];
    int i,j,a,b,c;
    gets(o);
    gets(e);
    a=strlen(o);
    b=strlen(e);
    if(a-b)
        c=1;
    else
        c=0;
    j=0;
    for(i=0;o[i];i++)
    {
        s[j]=o[i];
        j+=2;
    }
    j=1;
    for(i=0;e[i];i++)
    {
        s[j]=e[i];
        j+=2;
    }
    s[j-1+c]='\0';
    puts(s);
    return 0;
}


Measured memory_bytes: 128
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())


N = inp()
AA = inpl()
BB = inpl()

# In[]:
# N = 3
# AA = [3, 4, 3]
# BB = [3, 2, 3]

cards = []
for i,(a,b) in enumerate(zip(AA,BB)):
    if i%2 == 0:
        cards.append((a, b, i))
    else:
        cards.append((b, a, i))


n = (N+1)//2

# In[]:
def solve(ii):
    tmp = 0
    # print(ii)
    for _ in range(N):
        next = []
        for k, i in enumerate(ii):
            if i == 0:
                tmp += k
            else:
                next.append(i-1)
        ii = next[:]
    # print(tmp)
    return tmp



# In[]:
ans = INF
for Acards in itertools.combinations(cards, n):
    Ais = sorted([(Acard[0], Acard[2]) for Acard in Acards])

    ii = set([i for A,i in Ais])
    Bis = []
    for a,b,i in cards:
        if i not in ii:
            Bis.append((b,i))
    Bis.sort()

    nums = []
    ii = []
    for i in range(N):
        if i%2 == 0:
            n,i = Ais[i//2]
        else:
            n,i = Bis[i//2]
        nums.append(n)
        ii.append(i)

    # print(nums,ii)
    if nums != sorted(nums):
        continue
    else:
        ans = min(ans,solve(ii))


if ans == INF:
    print(-1)
else:
    print(ans)


Measured memory_bytes: 50328
#include <iostream>
#include <numeric>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
using namespace std;
using ll=long long;
#define rep(i,a,b) for(ll i=a;i<b;i++)
inline constexpr int intpow(ll a,ll b){
    if(b==0) return 1;
    ll ans=intpow(a,b/2);
    return ans*ans*(b&1?a:1);
}
int main(){
    int a,b,k;
    cin>>a>>b>>k;
    int cnt=0;
    rep(i,1,110){
        if((a%i==0)&&(b%i==0)){
            cnt++;
        }
    }
    int cnt2=0;
    rep(i,1,110){
        if((a%i==0)&&(b%i==0)){
            cnt2++;
        }
        if(cnt-cnt2==k-1) {
            cout<<i;
            return 0;
        }
    }
}

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

int main() {
	string s;
	cin >> s;
	int ryaku = s.length() - 2;
	cout << s[0] << ryaku << s[s.length()-1];
	return 0;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, x = 0, m = 0;
  string s;
  cin >> n >> s;
  for (int i = 0; i < n; i++) {
    if (s[i] == 'I') {
      x += 1;
      m = max(x, m);
    } else {
      x -= 1;
      m = max(x, m);
    }
  }
  cout << m << '\n';
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <list>
#include <string>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <iomanip> // setprecisionを使用するのに必要 cout << fixed << setprecision(15) << p でpを小数点以下15桁表示
#include <set>
using namespace std;
#define REPD(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) REPD(i, 0, n)
#define DIV0 1000000007
typedef long long ll;
#define fin(ans) cout << (ans) << '\n'
/*

*/
int main()
{
    int N,Q;
    int A;
    ll total = 0;
    int cnt[100005] = {0};
    cin >> N;
    REP(i,N){
        cin >> A;
        cnt[A]++;
        total += A;
    }
    //fin(total);
    cin >> Q;
    int B,C;
    REP(i,Q){
        cin >> B >> C;
        //BがCに変わる
        total += cnt[B]*(C-B);
        cnt[C] += cnt[B];
        cnt[B] = 0;
        fin(total);
    }
    return 0;
}

Measured memory_bytes: 3544
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <string>
#include <utility>
#include <map>
#include <deque>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)(n);i++)
#define Rep(i,n) for(int i=0;i<=(int)(n-1);i++)
typedef long long ll;
typedef map<int,int> mint;
typedef pair<int,int> pint;
typedef pair<ll,ll> pll;
typedef deque<pair<ll,ll>> dep;
int dx[]={-1,0,1,0};
int dy[]={0,-1,0,1};
int inf=1e9+1000;
const int mod=1e9+7;
ll infi=1e18+100;

//x=10111;
//x<<2 = 1011100 (右シフト),x>>2 = 101 (左シフト)
//(x>>2)&1 = 101 & 001 = 1
//iビット目は、(x>>i) & 1 でわかる(x>>i)%2 でもよい


int sx,sy,tx,ty;


int main(){
	cin>>sx>>sy>>tx>>ty;
	int dx=tx-sx;
	int dy=ty-sy;
	
	string ans;
	
	rep(i,dx) ans+='R';
	rep(i,dy) ans+='U';
	rep(i,dx) ans+='L';
	rep(i,dy+1) ans+='D';
	rep(i,dx+1) ans+='R';
	rep(i,dy+1) ans+='U';
	ans+='L';
	ans+='U';
	rep(i,dx+1) ans+='L';
	rep(i,dy+1) ans+='D';
	ans+='R';
	
	cout<<ans<<endl;
	
	  return 0;
  }

Measured memory_bytes: 256
#include <iostream>
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <cassert>

typedef long long ll;
using namespace std;

const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

int main(void){
    int n;cin >> n;
    vector<ll> c(n);
    for(int i=0;i<n;i++){
        cin >> c[i];
    }
    sort(c.rbegin(),c.rend());
    mint ans = 0;
    for(int i=0;i<n;i++){
        ans += (mint)c[i] * (mint)(i+2);
    }
    mint f = (mint)4;
    f = f.pow((ll)n-1);
    ans *= f;
    cout << ans.x << '\n';
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define ll long long
#define _GLIBCXX_DEBUG
const ll MOD = 1000000007;
const int MAX = 510000;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i=0; i<N; i++) cin >> a[i];
  int ans = 0;
  for (int i=1; i<N; i++) {
    if (a[i-1]==a[i]) {
      ans++;
      i++;
    }
  }
  cout << ans << endl;
}

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

#define REP(i,init, n) for(lli i=init;i<n;i++)
#define REPE(i,init, n) for(lli i=init;i<=n;i++)
#define REPIT(it,container) for(auto it = container.begin(); it != container.end(); it++)
#define REPIT_R(it,container) for(auto it = container.rbegin(); it != container.rend(); it++)

#define ARRAY_LENGTH(array) (sizeof(array) / sizeof(array[0]))

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

int main() {
    lli x, a;
    cin >> x >> a;
    if (x < a)
        cout << 0 << endl;
    else
        cout << 10 << endl;
}


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

#define rep(i, N) for (int i = 0; i < N; i++)
#define pb push_back

typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<ll, ll> ll_ll;
struct edge { int v, w; };
const int INF = INT_MAX / 2;
const int MOD = 1e9 + 7;
const ll e18 = 1e18;

int main() {
	int N; cin >> N;
	vector<int> a(N);
	rep(i, N) cin >> a[i];
	bitset<4000001> b;
	b[0] = true;
	rep(i, N) b |= b<<a[i];
	int A = 0;
	rep(i, N) A += a[i];
	for (int x = 0; ; x++)
		if (x * 2 >= A && b[x]) {
			cout << x << endl;
			break;
		}
}


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

int main() {
  int n, k, kakikae = 0;
  cin >> n >> k;
  map<int, int> a;//valueは登場回数
  for (int i = 0; i < n; i++) {
    int ai; cin >> ai;
    if (a.count(ai)) a[ai]++;
    else a[ai] = 1;
  }
  int syurui = a.size(); //a.size()→kにしたい
  if (syurui <= k) goto OUT; 
  for (int i = 1; i < n; i++) {//まずは1回しか出て来ないやつから消したい
    for (auto p: a) {
      if (p.second == i) {
        syurui--;
        kakikae += i;
        if (syurui <= k) goto OUT; 
      }
    }
  }
  OUT:
  cout << kakikae;
}

Measured memory_bytes: 12900
#pragma GCC optimize("O3")
#include <bits/stdc++.h>

using namespace std;

int64_t n;
vector<pair<int64_t, int64_t>> tasks;

int main(void) {
    int64_t i, a, b, sum=0;
    bool ok = true;
    cin >> n;
    for (i = 0; i < n; i++) {
        cin >> a >> b;
        tasks.push_back(make_pair(b, a));
    }
    sort(tasks.begin(), tasks.end());
    for (auto p : tasks) {
        sum += p.second;
        if (sum > p.first) {
            ok = false;
            break;
        }
    }
    cout << (ok ? "Yes" : "No") << endl;

    return 0;
}


Measured memory_bytes: 6384
#include <bits/stdc++.h>
#define fast ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define ii pair<int,int>
#define F first
#define S second
#define pb push_back
#define pf push_front
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define fore(i,a,b) for(int i = a;i < b; i+= 1)
#define forr(i,a) for(int i = a; i >= 0; i--)
#define fori(i,m) for(auto i = m.begin(); i != m.end(); i++) 
#define sz(s) int(s.size())
#define cls(a,car) memset(a,car,sizeof (a))
using namespace std;
typedef long long ll;
const int N = 1 * 1e5 + 5;
const ll mod = 1e9 + 7;
const int INF = INT_MAX;
const ll INFCAD  = ll(INT_MAX) * 2 + 1;
//freopen("","r",stdin);
//freopen("","w",stdout);
int main(){
    int a,b;
    char s;
    cin >> a >> s >> b;
    if(s == '-')
        cout << a - b << '\n';
    else
        cout << a + b << '\n';
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
#define INF LONG_LONG_MAX
#define MINF LONG_LONG_MIN
#define MAX_INT 100000
#define MOD 1000000007
#define forf(i,a,b) for(int i=a;i<=b;i++)

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

void solve()
{
    ll n;cin>>n;
    cin>>n;
    ll ans=0;
    forf(i,1,n)
    forf(j,1,n)
    forf(k,1,n)
    {
        ans+=_gcd(i,_gcd(j,k));
    }
    cout<<ans;
}
    
    
int main()
{
    IOS;
    
    //ll t;cin>>t;while(t--)
        solve();
 
    return 0;
}

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

public class Main {
	FastScanner in = new FastScanner(System.in);
	PrintWriter out = new PrintWriter(System.out);
	
	public void run() {
		while (true) {
			int n = in.nextInt(), q = in.nextInt();
			if (n == 0) break;
			
			int[] date = new int[1000];
			for (int i = 0; i < n; i++) {
				int m = in.nextInt();
				for (int j = 0; j < m; j++) {
					int x = in.nextInt();
					date[x]++;
				}
			}
			
			int max = 0;
			int res = 0;
			for (int i = 0; i < date.length; i++) {
				if (q <= date[i] && max < date[i]) {
					res = i;
					max = date[i];
				}
			}
			System.out.println(res);
		}
		
		out.close();
	}

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

	public void mapDebug(int[][] a) {
		System.out.println("--------map display---------");

		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a[i].length; j++) {
				System.out.printf("%3d ", a[i][j]);
			}
			System.out.println();
		}

		System.out.println("----------------------------");
		System.out.println();
	}

	public void debug(Object... obj) {
		System.out.println(Arrays.deepToString(obj));
	}

	class FastScanner {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;

		public FastScanner(InputStream stream) {
			this.stream = stream;
			//stream = new FileInputStream(new File("dec.in"));

		}

		int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}

		boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		boolean isEndline(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

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

		int[] nextIntArray(int n) {
			int[] array = new int[n];
			for (int i = 0; i < n; i++)
				array[i] = nextInt();

			return array;
		}

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

		long[] nextLongArray(int n) {
			long[] array = new long[n];
			for (int i = 0; i < n; i++)
				array[i] = nextLong();

			return array;
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		double[] nextDoubleArray(int n) {
			double[] array = new double[n];
			for (int i = 0; i < n; i++)
				array[i] = nextDouble();

			return array;
		}

		String next() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		String[] nextStringArray(int n) {
			String[] array = new String[n];
			for (int i = 0; i < n; i++)
				array[i] = next();

			return array;
		}

		String nextLine() {
			int c = read();
			while (isEndline(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndline(c));
			return res.toString();
		}
	}
}

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

#define li long long int
#define rep(i, to) for (li i = 0; i < ((li)(to)); i++)
#define repp(i, start, to) for (li i = (li)(start); i < ((li)(to)); i++)

#define EPS 1e-12

#define DEBUG_PRINT 1
#define idp if (DEBUG_PRINT)
#define p2(a, b) idp cout << a << "\t" << b << endl
#define p3(a, b, c) idp cout << a << "\t" << b << "\t" << c << endl
#define p4(a, b, c, d) idp cout << a << "\t" << b << "\t" << c << "\t" << d << endl
#define p5(a, b, c, d, e) idp cout << a << "\t" << b << "\t" << c << "\t" << d << "\t" << e << endl
#define p6(a, b, c, d, e, f) idp cout << a << "\t" << b << "\t" << c << "\t" << d << "\t" << e << "\t" << f << endl
#define p7(a, b, c, d, e, f, g) idp cout << a << "\t" << b << "\t" << c << "\t" << d << "\t" << e << "\t" << f << "\t" << g << endl
#define p8(a, b, c, d, e, f, g, h) idp cout << a << "\t" << b << "\t" << c << "\t" << d << "\t" << e << "\t" << f << "\t" << g << "\t" << h << endl
#define p9(a, b, c, d, e, f, g, h, i) idp cout << a << "\t" << b << "\t" << c << "\t" << d << "\t" << e << "\t" << f << "\t" << g << "\t" << h << "\t" << i << endl
#define p10(a, b, c, d, e, f, g, h, i, j) idp cout << a << "\t" << b << "\t" << c << "\t" << d << "\t" << e << "\t" << f << "\t" << g << "\t" << h << "\t" << i << "\t" << j << endl


typedef pair<li, li> PI;

li a[200100];
li n;

int main(void)
{
    cin >> n;
    rep(i, n) {
        cin >> a[i];
    }
    a[n] = 0xFFFFFFF;
    li res = 0;
    li right = 0;

    li now_xor = 0;
    li now_sum = 0;

    rep(i, n) {
        while (right < n && ((now_xor ^ a[right]) == (now_sum + a[right]))) {
            now_xor ^= a[right];
            now_sum += a[right];
            right++;
        }
        res += right - i;

        if (right == i) {
            right++;
        }
        now_sum -= a[i];
        now_xor ^= a[i];
    }
    cout << res << endl;


    return 0;
}

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

using namespace std;

typedef long long ll;

int main(){
  ll A[222222];
  ll N;
  cin >> N;
  ll i;
  for(i=0;i<=N-1;i++)
    cin >> A[i];
  ll sum[222222] = {0}; //sum[i]=A[i]までの和
  sum[0] = A[0];
  for(i=1;i<=N-1;i++){
    sum[i] = (sum[i-1] + A[i]) % 1000000007;
  }
  ll ans = 0;
  for(i=0;i<=N-2;i++)
    ans = (ans + A[i] * (sum[N-1] - sum[i])) % 1000000007;
  if(ans < 0) ans += 1000000007;
  cout << ans << endl;
}

Measured memory_bytes: 6904
x,k,d=map(int,input().split(" "))
x=abs(x)
d=abs(d)
if x>k*d:
    print(x-k*d)
else:
    a=x//d
    k-=a
    x-=a*d
    if k%2==0:
        print(x)
    else:
        print(d-x)

Measured memory_bytes: 9172
#include <iostream>

using namespace std;

int main()
{
	int P, Q, R;


	cin >> P >> Q >> R;

	if (Q <= P && R <= P)
	{
		cout << Q + R;
	}
	else if (P <= Q && R <= Q)
	{
		cout << P + R;
	}
	else
	{
		cout << P + Q;
	}


	return 0;
}


Measured memory_bytes: 256
lima = 0
tujuh = 0
a = [int(tmp) for  tmp in input().split()]
for i in range(3) :
  if a[i] == 5 :
    lima += 1
  elif a[i] == 7 :
    tujuh += 1
if lima==2 and tujuh == 1 :
  print("YES")
else :
  print('NO')

Measured memory_bytes: 3060
#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <iomanip>
#include <vector>
#include <utility>
#include <numeric>
#include <stack>
#include <queue>
using namespace std;
#define ll long long
#define INF 1000000007
int h,w;
int m[50][50];
void dfs(int k,int n){
    m[k][n]=0;
    for(int i=-1;i<=1;i++){
        for(int j=-1;j<=1;j++){
            if(i==0&&j==0)continue;
            int ni=k+i;
            int nj=n+j;
            if(0<=ni&&ni<h&&0<=nj&&nj<w&&m[ni][nj]==1)dfs(ni,nj);
        }
    }
    return;
}
int count(){
    int re=0;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(m[i][j]==1){
                dfs(i,j);
                re++;
            }
        }
    }
    return re;
}
int main(){
    while(1){
        cin>>w>>h;
        if(h==0&&w==0)break;
        for(int i=0;i<h;i++){
            for(int j=0;j<w;j++){
                cin>>m[i][j];
            }
        }
        cout<<count()<<endl;
    }
    return 0;
}



Measured memory_bytes: 3180