akhauriyash/Code-Regression huggingface dataset:
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using datas=pair<ll,ll>;
using tdata=pair<ll,datas>;
using vec=vector<ll>;
using mat=vector<vec>;
using pvec=vector<datas>;
using pmat=vector<pvec>;
#define For(i,a,b) for(i=a;i<b;i++)
#define bFor(i,a,b) for(i=a;i>=b;i--)
#define rep(i,N) For(i,0,N)
#define rep1(i,N) For(i,1,N)
#define brep(i,N) bFor(i,N-1,0)
#define all(v) (v).begin(),(v).end()
#define allr(v) (v).rbegin(),(v).rend()
#define vsort(v) sort(all(v))
#define vrsort(v) sort(allr(v))
#define mod 1000000007
#define endl "\n"
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"")<<i;f=1;}cout<<endl;}while(0)

long mmid(long a,long b,long c){return a<b?(b<c?b:max(a,c)):(b>c?b:min(a,c));}

ll modinv(ll a) {
  ll b=mod,u=1,v=0,t;
  while(b){
    t=a/b;
    a-=t*b; swap(a,b);
    u-=t*v; swap(u,v);
  }
  return (u+mod)%mod;
}

ll moddevide(ll a,ll b){return (a*modinv(b))%mod;}

ll modncr(ll n,ll r){
  ll i,plus=1;
  rep(i,r){
    plus=(plus*(n-i))%mod;
    plus=moddevide(plus,i+1);
  }
  return plus;
}

ll modncrlistp[200000],modncrlistm[200000];

ll modncrs(ll n,ll r){
  ll i,j;
  if(modncrlistp[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistp[i])break;
    }
    if(i<0){
      modncrlistp[0]=1;
      rep1(i,n+1){
        modncrlistp[i]=(modncrlistp[i-1]*i)%mod;
      }
    }else{
      For(j,i+1,n+1){
        modncrlistp[j]=(modncrlistp[j-1]*j)%mod;
      }
    }
  }
  if(modncrlistm[n]==0){
    for(i=n;i>=0;i--){
      if(modncrlistm[i])break;
    }
    if(i<0){
      modncrlistm[0]=1;
      rep1(i,n+1){
        modncrlistm[i]=(modncrlistm[i-1]*modinv(i))%mod;
      }
    }else{
      For(j,i+1,n+1)modncrlistm[j]=(modncrlistm[j-1]*modinv(j))%mod;
    }
  }
  return (((modncrlistp[n]*modncrlistm[r])%mod)*modncrlistm[n-r])%mod;
}

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

ll countdigits(ll n){
  ll ans=0;
  while(n){n/=10;ans++;}
  return ans;
}

ll sumdigits(ll n){
  ll ans=0;
  while(n){ans+=n%10;n/=10;}
  return ans;
}

vec eratosthenes(ll N){
  ll i;
  vec ch(N+1,1),p;
  ch[0]=ch[1]=0;
  rep(i,N+1){
    if(ch[i]){
      p.push_back(i);
      for(ll j=2;i*j<=N;j++){
        ch[i*j]=0;
      }
    }
  }
  return ch;
}
int main(){
  ll i,j,N,K,cnt=0;
  string ss;cin>>ss;
  N=ss.size();
  cin>>K;
  vector<string> v(N*K);
  rep(j,K){
    rep(i,N-j){
      v[cnt++]=ss.substr(i,j+1);
    }
  }
  v.resize(cnt);
  vsort(v);
  set<string> se;
  rep(i,cnt){
    auto p=se.insert(v[i]);
    if(p.second){
      K--;
      if(!K){
        cout<<v[i]<<endl;
        return 0;
      }
    }
  }
}


Measured memory_bytes: 1664
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int height = sc.nextInt();
        int width = sc.nextInt();;
        int[][] matrix = new int[height][width];
        int[] matrix2 = new int[width];
        
        //入力
        for(int hei = 0; hei < height; hei++){
            for(int wid = 0; wid < width; wid++){
                matrix[hei][wid] = sc.nextInt();    
            }
        }
        
        //入力
        for(int wid = 0; wid < width; wid++){
            matrix2[wid] = sc.nextInt();
        }
        
        // 出力
        for(int hei = 0; hei < height; hei++){
            int sumMultiplication = 0;
            for(int wid = 0; wid < width; wid++){
                sumMultiplication += matrix[hei][wid] * matrix2[wid];
                if(wid == width-1){
                    System.out.println(sumMultiplication);
                    continue;
                }
            }
        }
    }
}


Measured memory_bytes: 40548
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        MyScanner in = new MyScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        A solver = new A();
        solver.solve(1, in, out);
        out.close();
    }

    static class A {
        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int X = in.Int();
            if (X < 600) out.println(8);
            else if (X < 800) out.println(7);
            else if (X < 1000) out.println(6);
            else if (X < 1200) out.println(5);
            else if (X < 1400) out.println(4);
            else if (X < 1600) out.println(3);
            else if (X < 1800) out.println(2);
            else if (X < 2000) out.println(1);
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    return null;
                }
            }
            return st.nextToken();
        }

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

    }
}



Measured memory_bytes: 32840
from sys import stdin
import math
A, B, C, D, E, F = [int(x) for x in stdin.readline().rstrip().split()]

water = set()
for i in range(0, F//(100*A)+1):
    for j in range(0, F//(100*B)+1):
        water.add(A*i*100+B*j*100)

sugar = set()
capa = math.ceil(F/100)*E
for k in range(0, capa//C+1):
    for l in range(0, capa//D+1):
        sugar.add(C*k+D*l)

W = 0
S = 0
conc = 0
#print(water)
#print(sugar)
for w in water:
    for s in sugar:
        tmp = 0
        if w + s > F:
            continue
        if w+s == 0:
            continue
        if s > (w / 100)*E:
            continue
        tmp = (100*s)/(w+s)
        if tmp >= conc:
            conc = tmp
            W = w
            S = s
        #print(conc,w,s)
print(W+S,S)

Measured memory_bytes: 3316
n,m = map(int,input().split())
h = list(map(int,input().split()))
road = []
for i in range(m):
    road.append(list(map(int,input().split())))

good = set(range(1,n+1))
for i in range(m):
    if h[road[i][0]-1] < h[road[i][1]-1]:
        good.discard(road[i][0])
    elif h[road[i][1]-1] < h[road[i][0]-1]:
        good.discard(road[i][1])
    else:
        good.discard(road[i][0])
        good.discard(road[i][1])

print(len(good))


Measured memory_bytes: 40472
#include <bits/stdc++.h>
#define INF LLONG_MAX
#define uInt long long
#define rep(i,n) for(int i=0; i<n; ++i)
using namespace std;
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;}

uInt mem[1100];

int main() {
  int N; cin >> N;
  int n = 1;
  for(int i=N; i>0; --i) {
    n = n*i;
    for(int j=2; j<=i; ++j) {
      while(n%j == 0 && n != 1) {
        n = n/j;
        mem[j]++;
      }
    }
  }
  uInt ans = 1;
  for(int i=0; i<1100; ++i) {
    if(mem[i] > 0)
      ans = (ans*(mem[i]+1))%1000000007;
  }
  cout << ans << endl;
}


Measured memory_bytes: 256
n = int(input())
h = list(map(int, input().split()))
cnt = 0
cnt_max = 0
for i in range(1, n):
    if h[i - 1] >= h[i]:
        cnt += 1
        cnt_max = max(cnt, cnt_max)
    else:
        cnt = 0
print(cnt_max)


Measured memory_bytes: 63856
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int n,m;
vector<int> p;
int main(void){
  while(1){
    cin >> n >> m; if(!n) break;
    p.clear();
    for(int i = 0; i < n; i++){
      int a;
      cin >> a;
      p.push_back(a);
    }
    for(int i = 0; i < n; i++){
      for(int j = i; j < n; j++){
	p.push_back(p[i] + p[j]);
      }
    }
    p.push_back(0);
    sort(p.begin(),p.end());
    int ret = 0;
    for(int i = 0; i < (int)p.size() && p[i] < m; i++){
      ret = max(ret,*(upper_bound(p.begin(),p.end(),m - p[i]) - 1) + p[i]);
    }
    cout << ret << endl;
  }
}

Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sc(n) scanf("%d",&n)
#define scl(n) scanf("%lld",&n)
#define pr(n) printf("%d",n)
#define prl(n) printf("%lld",n)
#define nl printf("\n")
#define fr(i,n) for(i=1;i<=n;i++)

typedef long long ll;
ll A[100010];
int main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    int t=1,n,i,j;
    cin>>n;
    fr(i,n)cin>>A[i];
    A[n+1]=0;
    ll tot =0;
    for(int i=1;i<=(n+1);i++)
        tot += 1ll*abs(A[i]-A[i-1]);
    fr(i,n)
    {
        int b4 = i-1;
        int nex = (i+1);
        ll dist = abs(A[nex]-A[b4])-(abs(A[i]-A[b4])+abs(A[nex]-A[i]));
        cout<<tot+dist<<"\n";}



    
    return 0;
}

Measured memory_bytes: 2048
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<stdio.h>
#include<vector>
using namespace std;
#define int long long
#define rep(s,i,n) for(int i=s;i<n;i++)
#define c(n) cout<<n<<endl;
#define ic(n) int n;cin>>n;
#define sc(s) string s;cin>>s;
#define mod 1000000007
#define inf 1000000000000000007
#define f first
#define s second
#define mini(c,a,b) *min_element(c+a,c+b)
#define maxi(c,a,b) *max_element(c+a,c+b)
//printf("%.12Lf\n",c);
int keta(int x){
	rep(0,i,30){
		if(x<10){
			return i+1;
		}
		x=x/10;
	}
}
int gcd(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return bb;
		}	
		bb=bb%aa;
		if(bb==0){
			return aa;
		}
	}
}	
int lcm(int x,int y){
	int aa=x,bb=y;
	rep(0,i,1000){
		aa=aa%bb;
		if(aa==0){
			return x/bb*y;
		}	
		bb=bb%aa;
		if(bb==0){
			return x/aa*y;
		}
	}
}
bool p(int x){
	if(x==1)return false;
	rep(2,i,sqrt(x)+1){
		if(x%i==0&&x!=i){
			return false;
		}
	}	
	return true;
}
int max(int a,int b){
	if(a>=b)return a;
	else return b;
}
int min(int a,int b){
	if(a>=b)return b;
	else return a;
}	
int n2[41];		
int nis[41]; 
int nia[41];
int mody[41];
int nn;
int com(int n,int y){
	int ni=1;
	for(int i=0;i<41;i++){
		n2[i]=ni;
		ni*=2;
	}
	int bunsi=1,bunbo=1;
	rep(0,i,y)bunsi=(bunsi*(n-i))%mod;
	rep(0,i,y)bunbo=(bunbo*(i+1))%mod;
	mody[0]=bunbo;
	rep(1,i,41){
		bunbo=(bunbo*bunbo)%mod;
		mody[i]=bunbo;
	}
	rep(0,i,41)nis[i]=0;
	nn=mod-2;
	for(int i=40;i>=0;i-=1){
		if(nn>n2[i]){
			nis[i]++;
			nn-=n2[i];
		}
	}
	nis[0]++;
	rep(0,i,41){
		if(nis[i]==1){
			bunsi=(bunsi*mody[i])%mod;
		}
	}
	return bunsi;
}
int yakuwa(int n){
	int sum=0;
	rep(1,i,sqrt(n+1)){
		if(n%i==0)sum+=i+n/i;
		if(i*i==n)sum-=i;
	}
	return sum;
}	
bool hei(int n){
	rep(0,i,100){
		if(i*i==n){
			return true;
		}
	}
	return false;
}
int pow(int b,int a){	
	int aa=1;
	rep(0,i,a)aa*=b;	
	return aa;
}		
int ma[32769][15];
int a[15];
int x[15][15],y[15][15];
signed main(){
	ic(n)
	rep(0,i,n){
		cin>>a[i];
		rep(0,j,a[i]){
			cin>>x[i][j]>>y[i][j];
		}
	}	
	for(int bit=0;bit<(1<<n);bit++)rep(0,i,n)if(bit&(1<<i))ma[bit][i]=1;
	int ans=0;
	rep(0,i,pow(2,n)){
		int sum=0;
		rep(0,j,n)rep(0,k,a[j])if(ma[i][j]==1&&ma[i][x[j][k]-1]!=y[j][k])sum++;
		if(sum==0){
			int cnt=0;
			rep(0,j,n)if(ma[i][j]==1)cnt++;
			ans=max(ans,cnt);
		}
	}
	c(ans)
}	

Measured memory_bytes: 4096
import java.util.Scanner;

public class Main {

	static final int MOD = 1000000007;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		char[] l = sc.next().toCharArray();
		sc.close();
		long[][] dp = new long[l.length + 1][2];
		dp[0][0] = 1;
		dp[0][1] = 0;
		for (int i = 1; i <= l.length; i++) {
			if (l[i - 1] == '0') {
				dp[i][0] = dp[i - 1][0];
				dp[i][1] = (dp[i - 1][1] * 3) % MOD;
			} else {
				dp[i][0] = (dp[i - 1][0] * 2) % MOD;
				dp[i][1] = (dp[i - 1][0] + dp[i - 1][1] * 3) % MOD;
			}
		}
		System.out.println((dp[l.length][0] + dp[l.length][1]) % MOD);

	}

}

Measured memory_bytes: 29168
n,k=map(int,input().split())
A=sorted(map(int,input().split()))

def cmb(n,r,mod):
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod

mod=10**9+7
N=10**5
g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

ans=0
for i in range(n-k+1):
    ans+=cmb(n-1-i,k-1,10**9+7)*(A[-i-1]-A[i])%(10**9+7)
    ans%=10**9+7
print(ans)

Measured memory_bytes: 20160
// https://ei1333.github.io/luzhiled/
// http://beet-aizu.hatenablog.com/entry/2017/01/04/113233
// http://www.prefield.com/algorithm/
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using vl = vector<ll>;
using vd = vector<ld>;
using vs = vector<string>;
using vb = vector<bool>;
using vvl = vector<vector<ll>>;
using vvd = vector<vector<ld>>;
using vvs = vector<vector<string>>;
using vvb = vector<vector<bool>>;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
template<class T> using vc = vector<T>;
template<class T> using vvc = vector<vector<T>>;
using Graph = vector<vector<ll>>;
const ll INF = 1LL << 60;
void init() {cin.tie(0);ios::sync_with_stdio(false);cout << fixed << setprecision(15);}
const ll tl= 1'000'000'007;
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REREP(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, a, n) for (ll i = a; i < n; i++)
#define REFOR(i, n, a) for (ll i = n; i >= a; i--)
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define debug cout << "line : " << __LINE__ << " debug" << endl;
#define ini(...) int __VA_ARGS__; in(__VA_ARGS__)
#define inl(...) long long __VA_ARGS__; in(__VA_ARGS__)
#define ind(...) long double __VA_ARGS__; in(__VA_ARGS__)
#define ins(...) string __VA_ARGS__; in(__VA_ARGS__)
#define inc(...) char __VA_ARGS__; in(__VA_ARGS__)
void in(){} template <typename T,class... U> void in(T &t,U &...u){ cin >> t; in(u...);}
void out(){cout << endl;} template <typename T,class... U> void out(const T &t,const U &...u){ cout << t; if(sizeof...(u)) cout << " "; out(u...);}
template<typename T>void die(T x){out(x); exit(0);}
#define in1(A) REP(i,A.size()) in(A[i]);
#define in2(A,B) REP(i,A.size()) in(A[i],B[i]);
#define in3(s,t,u) REP(i,sz(s)){in(s[i] , t[i] , u[i]);}
#define in4(s,t,u,v) REP(i,sz(s)){in(s[i] , t[i] , u[i] , v[i]);}
#define each(x,v) for(auto& x : v)
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
struct Point{ ld x,y; };
ld dist(Point a, Point b){return sqrt(abs(a.x-b.x)*abs(a.x-b.x)+abs(a.y-b.y)*abs(a.y-b.y));} // ２点間の距離 
ll gcd(ll a, ll b) { return b != 0 ? gcd(b, a % b) : a; }
ll lcm(ll a,ll b){ return a / gcd(a,b) * b;} 
ll fact(ll n){ if(n < 2) return 1; return (n * fact(n-1))%tl; } //階乗
inline ll updiv(ll a,ll b){ return (a + b - 1) / b; } //切り上げ
template<typename T,typename U>ll ceil(T a,U b){return (a + b - 1) / b;}
template <class A, class B> inline bool chmax(A &a, const B &b) { return b > a && (a = b, true); }
template <class A, class B> inline bool chmin(A &a, const B &b) { return b < a && (a = b, true); }
//-------------------------------------------------------------------------------------------------
int main(){
    init();
    inl(x,y);
    
    
    out(x+y/2);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main() {
    int N; cin >> N;
    int cnt = 0;
    for (int i = 1; i <= N; i++) {
        if (i % 2) cnt++;
    }
    cout << fixed << setprecision(9) << (double)cnt / N << endl;
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

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

alp = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

def main():
    ids = {}
    for i in range(26):
        ids[alp[i]] = i
    n = ri()
    s = input()
    ans = ""
    for c in s:
        to = (ids[c]+n)%26
        ans += alp[to]
    print(ans)


if __name__ == '__main__':
    main()


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

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int res = -1;
	for(int t = 0; t < 120; t++) {
		int T;
		T = 60 * t + c;
		if(T % (a+b) <= a) {
			res = T;
			break;
		}
	}
	cout << res << endl;
}

Measured memory_bytes: 1164
///بِسْمِ الّٰلهِ الرَّحْمٰنِ الرَحِيْمِ
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pi acos(-1.0)
int main()
{
     ios_base::sync_with_stdio(false);cin.tie(NULL);
     int i,n,t,p=INT_MAX,j=0,x,a=0,b,l=0,r=0,y,k,c,sum=0,m,d;

     cin>>n>>t;
     string s[n];
     for(i=0;i<n;i++){
        cin>>s[i];
     }
     sort(s,s+n);
     for(i=0;i<n;i++){
        cout<<s[i];
     }


     return EXIT_SUCCESS;
}




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

int main() {
    stack<int> s;
    string str;

    while (cin >> str) {
        if (str[0] == '+') {
            auto rhs = s.top(); s.pop();
            auto lhs = s.top(); s.pop();
            s.push(lhs + rhs);
        }
        else if (str[0] == '-') {
            auto rhs = s.top(); s.pop();
            auto lhs = s.top(); s.pop();
            s.push(lhs - rhs);
        }
        else if (str[0] == '*') {
            auto rhs = s.top(); s.pop();
            auto lhs = s.top(); s.pop();
            s.push(lhs * rhs);
        }
        else {
            s.push(std::atoi(str.c_str()));
        }
    }

    cout << s.top() << endl;
    return 0;
}


Measured memory_bytes: 3184
def v_block():
    block.insert(0, [' ']*5)
    for l, line in enumerate(block):
        if line[q-1:q+p-1] != [' ']*p:
            break
    else:
        l += 1
    block[l-1][q-1:q+p-1] = ['*']*p
    return delete()


def h_block():
    for _p in range(p):
        block.insert(0, [' ']*5)
    for l, line in enumerate(block):
        if line[q-1] == '*':
            break
    else:
        l += 1
    for _l in range(l-1, l-p-1, -1):
        block[_l][q-1] = '*'
    return delete()
                

def delete():
    b = len(block)
    l = 0
    while 0 < b:
        if block[l] == [' ']*5 or block[l] == ['*']*5:
            del block[l]
        else:
            l += 1
        b -= 1


def count():
    x = 0
    for line in block:
        for b in line:
            if b == '*':
                x += 1
    else:
        print(x)


while True:
    n = int(input())
    if n == 0:
        break
    block = [[' ']*5]
    for i in range(n):
        d, p, q = map(int, input().split())
        if d == 1:
            v_block()
        else:
            h_block()
    else:
        count()

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

#define MAX_N 200005
#define MAX_M 100005

#define pb push_back
#define mp make_pair
#define all(V) (V).begin(),(V).end()
#define reset(V) (V).clear();(V).resize(0);

#define sq(x) ((x)*(x))
#define abs(x) ((x)>0?(x):(-(x)))

#define fi first
#define se second

#define LL_inf (1LL<<60)
#define full_inf 0x7fffffff
#define half_inf 0x3fffffff
#define inf 0x3fffffff

#define MOD 1000000007LL

#define cpx_mod(x) (((LD)(((LL)x.real())%MOD)),((LD)(((LL)x.imag())%MOD)))


using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int,int> pii;
typedef pair<LL,LL> pil;
typedef pair<LL,string> pls;
typedef complex<LD> Complex;
typedef long double LD;
int n,m;
int main(){
	scanf("%d %d",&n,&m);
	printf("%s\n",((n+1)/2>=m)?"YES":"NO");
	return 0;
}

Measured memory_bytes: 256
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;

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

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read::<String>()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn main() {
    let v: Vec<usize> = read_vec();
    let (x, y, z) = (v[0], v[1], v[2]);
    let n = x + y + z;
    let mut a = vec![0i64; n];
    let mut b = vec![0i64; n];
    let mut c = vec![0i64; n];

    for i in 0..n {
        let v = read_vec::<i64>();
        a[i] = v[0];
        b[i] = v[1];
        c[i] = v[2];
    }

    let a_minus_b = a
        .iter()
        .zip(b.iter())
        .map(|(x, y)| x - y)
        .collect::<Vec<_>>();

    let sorted_idx = argsort(&a_minus_b);

    let mut sorted_a = vec![0i64; n];
    let mut sorted_b = vec![0i64; n];
    let mut sorted_c = vec![0i64; n];

    for i in 0..n {
        let idx = sorted_idx[i];
        sorted_a[i] = a[idx];
        sorted_b[i] = b[idx];
        sorted_c[i] = c[idx];
    }

    let mut heap_forward = BinaryHeap::new();
    let mut sum_forward = vec![0i64; n];

    for i in 0..n {
        heap_forward.push(-(sorted_b[i] - sorted_c[i]));
        sum_forward[i] = sorted_b[i] - sorted_c[i];
        if i > 0 {
            sum_forward[i] += sum_forward[i - 1];
        }
        if heap_forward.len() > y {
            sum_forward[i] += heap_forward.pop().unwrap();
        }
    }

    let mut heap_backward = BinaryHeap::new();
    let mut sum_backward = vec![0i64; n];

    for i in (0..n).rev() {
        heap_backward.push(-(sorted_a[i] - sorted_c[i]));
        sum_backward[i] = sorted_a[i] - sorted_c[i];
        if i < n - 1 {
            sum_backward[i] += sum_backward[i + 1];
        }
        if heap_backward.len() > x {
            sum_backward[i] += heap_backward.pop().unwrap();
        }
    }

    let mut ans = sorted_c.iter().sum::<i64>();
    ans += (y - 1..n - x)
        .map(|i| sum_forward[i] + sum_backward[i + 1])
        .max()
        .unwrap();
    println!("{}", ans);
}

fn argsort<T: std::cmp::Ord + std::marker::Copy>(v: &Vec<T>) -> Vec<usize> {
    let mut sort_v = Vec::new();
    for i in 0..v.len() {
        sort_v.push((v[i], i));
    }
    sort_v.sort();
    sort_v.iter().map(|x| x.1).collect::<Vec<usize>>()
}


Measured memory_bytes: 16624
F_str = input().split()
F = [int(f) for f in F_str]
N = F[0]
M = F[1]

WA_list = [0 for _ in range(N)]
AC_list = [0 for _ in range(N)]

for i in range(M):
    S_str = input().split()
    S = [str(s) for s in S_str]
    if(S[1] == "AC"):
        AC_list[int(S[0])-1] = 1
    elif(AC_list[int(S[0])-1] != 1):
        WA_list[int(S[0])-1] += 1

WA_count = 0
AC_count = 0

for i in range(N):
    if(AC_list[i] == 1):
        AC_count += 1
        WA_count += WA_list[i]

print(AC_count, WA_count)

Measured memory_bytes: 4784
program ABC162D
    implicit none
    integer(8)::N,r,g,b,i,j,ans
    character(4000)::S
    read*,N,S
    r=0
    g=0
    b=0

    do i=1,N
        if(S(i:i)=="R")r=r+1
        if(S(i:i)=="G")g=g+1
        if(S(i:i)=="B")b=b+1
    end do

    ans=r*g*b

    do i=1,N
        do j=1,N
            if(i+2*j<=N)then
                if(S(i:i)/=S(i+j:i+j).and.S(i+j:i+j)/=S(i+2*j:i+2*j).and.S(i+2*j:i+2*j)/=S(i:i))then
                    ans=ans-1
                end if
            end if
        end do
    end do

    print'(i0)',ans
end program ABC162D

Measured memory_bytes: 2928
#include <bits/stdc++.h>
#define mk make_pair
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
ll a[2020010];
int main(){
    int n;
    while(cin>>n){
        ll ans=0, tmp=0, sm=0, tmp1;
        for(int i=0; i<n; ++i){
            scanf("%lld",a+i);
            sm+=a[i];
        }
        ans=sm;
        for(int i=0; i<n; ++i){
            tmp+=a[i];
            tmp1=sm-tmp;
            ans=min(ans, abs(tmp1-tmp));
        }
        cout<<ans<<endl;
    }
  return 0;
}




Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
 
int main() {
  ll a;
  double b;
  cin >> a >> b;
  
  ll b100 = b*100 + 0.5;
  ll ans = a*b100/100;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3732
#include <stdio.h>
#include <algorithm>
using namespace std;


int n, m, X, Y, z;
int x[120], y[120];

int main(){
    scanf("%d %d %d %d", &n, &m, &X, &Y);
    for(int i=0; i<n; i++)
        scanf("%d", &x[i]);
    for(int i=0; i<m; i++)
        scanf("%d", &y[i]);

    sort(x, x+n);
    sort(y, y+m);
    int a = x[n-1]+1;
    int b = y[0];
    bool war = true;
    int num = -1;
    for(int i=a; i<=b; i++){
        if(i > x[n-1] && i <= y[0] && i > X && i <= Y){
            war = false;
            num = i;
            break;
        }
    }
    /*for(int i=0; i<n; i++)
        printf("%d ", x[i]);
    printf("\n");
    for(int i=0; i<m; i++)
        printf("%d ", y[i]);
    printf("\n");
    printf("%d   %d %d\n", num, a, b);*/
    if(war){
        printf("War\n");
    } else {
        printf("No War\n");
    }

}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a; i< (int)(b); ++i)
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
typedef long double ld;
using ll=long long;
using namespace std;
const int mod=1e9+7;
const ll inf = 1LL << 60;
const ld pi = (acos(-1));
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; }


int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(20);
  
  ll n,k,r,s,p; cin >> n >> k >> r >> s >> p;
  string T; cin >> T;
  ll res=0;
  rep(i,0,k){
      int t=i;
      string ns;
      while(t<n){
          ns+=T[t];
          t+=k;
      }
      int suc=0;
      rep(i,0,ns.length()){
          char c=ns[i];
          if(suc) suc=0;
          else{
              if(i && ns[i]==ns[i-1]){
                  suc=1;
                  continue;
              }
          }
          if(c=='r') res+=p;
          if(c=='p') res+=s;
          if(c=='s') res+=r;
      }
  }
  cout << res << endl;
}

Measured memory_bytes: 640
L, R = map(int, input().split())

ans = 10 ** 9
# (i×j)%Qを最小化する作業は、i%Qとj%Qをそれぞれ最小化する作業とは等価ではない。[2007 2018]で試すとよい
for i in range(L, min(L + 2019, R + 1)):
    for j in range(i+1, min(L + 2019, R + 1)):
        ans = min(ans, (i*j) % 2019)
        
print(ans)

Measured memory_bytes: 3060
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <x86intrin.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define V vector
template <typename T> bool chmin(T &a, const T &b) {if(a > b){a = b; return true;} return false;}
template <typename T> bool chmax(T &a, const T &b) {if(a < b){a = b; return true;} return false;}
template<typename A, size_t N, typename T> void Fill (A (&array)[N], const T & val) {fill ((T*)array, (T*)(array+N), val);}
V<int> dx = {-1, 1,  0, 0, -1, -1,  1, 1};
V<int> dy = { 0, 0, -1, 1, -1,  1, -1, 1};

int n;
V<int> a(2e5+1, -1), b(2e5+1, -1);
V<set<int>> st(2e5+1);//st[i]:i個ある文字のset
map<int, int> ma, mb;//ma[i]:aに入ってるiの個数
map<int, queue<int>> ia, ib;//ia[i]:aにあるiのindex
V<int> ans(2e5+1, -1);

int get_any (map<int, int> &mp, int x) {//x以外をとる
    for (auto p : mp) {
        if (p.first != x) return p.first;
    }
    return 0;
}

void use(int x, int y) {//aからx(ia[x][0])を,bからy(ib[y][0])を使う
    int cnt_x = ia[x].size() + ib[x].size();
    st[cnt_x].erase(x);
    if (cnt_x - 1 > 0) st[cnt_x - 1].emplace(x);
    
    int cnt_y = ia[y].size() + ib[y].size();
    st[cnt_y].erase(y);
    if (cnt_y - 1 > 0) st[cnt_y - 1].emplace(y);
    
    ans[ia[x].front()] = y;
    ia[x].pop();
    ib[y].pop();

    ma[x]--; mb[y]--;
    if (ma[x] == 0) ma.erase(x);
    if (mb[y] == 0) mb.erase(y); 
}

int main () {
    cin >> n;
    rep(i, n) {
        int a; scanf("%d", &a);
        ma[a]++;
        ia[a].emplace(i);
    }
    rep(i, n) {
        int b; scanf("%d", &b);
        mb[b]++;
        ib[b].emplace(i);
    }
    for (int i = 1; i <= n; i++) {
        int cnt = ia[i].size() + ib[i].size();
        if (cnt > n) {
            puts("No");
            return 0;
        }
        if (cnt > 0) st[cnt].emplace(i);
    }
    puts("Yes");
    for (int i = n; i > 0; i--) {
        if (st[i].size() == 2) {//xとyがi個ずつ
            auto itr = st[i].begin();
            int x = *itr;
            itr++;
            int y = *itr;
            if (ia[x].size() == 0) swap(x, y);
            use(x, y);
        }
        else if (st[i].size() == 1) {
            int z = *st[i].begin();//絶対使う
            int x, y;
            if (ia[z].size() > 0) {
                x = z;
                y = get_any(mb, x);
            }
            else {
                y = z;
                x = get_any(ma, y);
            }
            use(x, y);
        }
        else {
            int x = get_any(ma, -1);
            int y = get_any(mb, x);
            use(x, y);
        }
    }
    rep(i, n) printf("%d ", ans[i]);
    cout << endl;
    return 0;
}

Measured memory_bytes: 330580
from collections import deque

K = int(input())
Q = list(range(1, 10))

for i in range(K):
    x = Q[i]
    y = x%10
    if y != 0:
        Q.append(10*x + y-1)
    Q.append(10*x + y)
    if y != 9:
        Q.append(10*x + y+1)

print(Q[K-1])

Measured memory_bytes: 16120
n = int(input())
a = list(map(int, input().split()))
ans = 1
trend = '-'
pre = a[0]
for now in a:
    if (trend=='<' and pre>now) or (trend=='>' and pre<now):
        ans += 1
        trend = '-'
    else:
        if pre<now:
            trend = '<'
        elif pre>now:
            trend = '>'
    pre = now
print(ans)

Measured memory_bytes: 15020
h = int(input())
l = [int(i) for i in input().split()]

for i in range(h):
    node = i + 1
    key = l[i]
    if i == 0:
        parent = None
    else:
        parent = l[(i - 1) // 2]

    if 2 * i + 1 < len(l):
        left = l[2 * i + 1]
    else:
        left = None

    if 2 * i + 2 < len(l):
        right = l[2 * i + 2]
    else:
        right = None

    s = "node {}: key = {}, ".format(node, key)
    if parent:
        s += "parent key = {}, ".format(parent)
    if left:
        s += "left key = {}, ".format(left)
    if right:
        s += "right key = {}, ".format(right)
    print(s)



Measured memory_bytes: 5628
s = int(input())
a, b = s // 100, s % 100
x = "YY" if a == 0 or a > 12 else "MM"
y = "YY" if b == 0 or b > 12 else "MM"
if x != y:
    print(x + y)
else:
    print("NA" if x == "YY" else "AMBIGUOUS")


Measured memory_bytes: 9064
a, b = map(int, input().split())
k = 50
ans = []
for _ in range(k):
    ans += [['#'] * (2 * k)]
for _ in range(k):
    ans += [['.'] * (2 * k)]

for i in range(a - 1):
    ans[(i // k) * 2][(i % k) * 2] = '.'
for i in range(b - 1):
    ans[(i // k) * 2 + k + 1][(i % k) * 2] = '#'

print('{} {}'.format(2*k, 2*k))
for i in range(2 * k):
    for j in range(2 * k):
        print(ans[i][j], end='')
    print()

Measured memory_bytes: 4468
#include<iostream>
#include<iomanip>
using namespace std;
long double L, R, P, E, T, L1, L2; int K;
long double dfs(int C, long double l, long double r, long double w) {
	long double a1, a2, m = (l + r) / 2.0;
	if (C == 0 && L1 <= m && m < L2)return w;
	if (C == 0)return 0;
	if (L1 <= l && r <= L2)return w;
	if (r <= L1 || L2 <= l)return 0;
	if (m <= T) { a1 = P; a2 = 1.0 - P; }
	else { a1 = 1.0 - P; a2 = P; }
	long double A1 = dfs(C - 1, l, m, w*a1);
	long double A2 = dfs(C - 1, m, r, w*a2);
	//cout << C << ' ' << l << ' ' << r << ' ' << A1 << ' ' << A2 << endl;
	return A1 + A2;
}
int main() {
	cin >> K >> L >> R >> P >> E >> T;
	L1 = T - E, L2 = T + E;
	cout << fixed << setprecision(20) << dfs(K, L, R, 1.0) << endl;
	return 0;
}

Measured memory_bytes: 1300
N,W = [int(i) for i in input().split()]
wv = [[int(i) for i in input().split()] for j in range(N)]
dp = [[0]*(W+1) for i in range(N+1)]
for i in range(1, N+1):
    for j in range(1, W+1):
        if 0 <= j-wv[i-1][0]:
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-wv[i-1][0]] + wv[i-1][1])
        else:
            dp[i][j] = dp[i-1][j]
print(dp[-1][-1])

Measured memory_bytes: 120172
N = int(input())
H = list(map(int,input().split()))
dp = [0]*N
dp[1]=abs(H[1]-H[0])
for i in range(2,N):
    dp[i] = min(dp[i-1]+abs(H[i]-H[i-1]),dp[i-2]+abs(H[i]-H[i-2]))
print(dp[N-1])

Measured memory_bytes: 13928
#include <iostream>
#include <algorithm>
using namespace std;
int f[100001], n, a, res = 0;
int main(void){
    // Your code here!
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        f[a]++;
    }
    for (int i = 0; i < 99999; i++) {
        int sum = f[i] + f[i + 1] + f[i + 2];
        res = max(res, sum);
    }
    cout << res << endl;
}


Measured memory_bytes: 640
import java.io.IOException;
import java.util.NoSuchElementException;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;

import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws IOException {
        try (
            BufferedReader reader = new BufferedReader(
                new InputStreamReader(System.in))) {
            final String s = reader.readLine();
            final int len = s.length();

            int cnt = 0;
            for (int i = 0; i < len; i++) {
                if (s.charAt(i) == '+') cnt++;
                else cnt--;
            }

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


Measured memory_bytes: 22484
#include <bits/stdc++.h>
using namespace std;
#define F first  
#define S second
#define ll long long
#define pb push_back
#define pr pair<ll,ll>

const ll N=1e5+9,mod=1e9+7,inf=1e18;

int main()
{
	ll n,m;cin>>n>>m;
	vector<string> vc[n+6];
	for(int i=1;i<=m;i++)
	{
		ll p;string s;
		cin>>p>>s;
		vc[p].pb(s);

	}

	ll sum=0,cnt=0;
	for(int i=1;i<=n;i++)
	{

		for(int j=0;j<vc[i].size();j++)
		{
			if(vc[i][j]=="AC")
			{
				sum+=j;
				cnt++;
				break;
			}
		}
	}
	cout<<cnt<<" "<<sum<<"\n";
	
	
	return 0;
}


Measured memory_bytes: 10368
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;


template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}

// 繰り返し二乗法
ll pow2(ll n, ll p, ll mod) {
	if (p == 0 || n == 1) {
		return 1;
	}
	else {
		ll ret = pow2(n * n % mod, p / 2, mod);
		if (p % 2 == 1) {
			ret *= n;
		}
		return ret % mod;
	}
}


#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	ll K;
	cin >> K;

	ll num = 0;
	map<ll, bool> dic;
	dic[0] = true;

	ll ans = 0;
	while (true) {
		ans++;
		num = 10 * num + 7;
		num %= K;
		if (dic[num]) {
			if (num == 0) {
				cout << ans << endl;
			}
			else {
				cout << -1 << endl;
			}
			return 0;
		}
		dic[num] = true;
	}

}


Measured memory_bytes: 66104
#include <iostream>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <vector>
#include <map>
#include <list>
#include <stack>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
#define pr(num) printf("%lld\n", num)
#define max(a, b) ((a)>(b) ? (a):(b))
#define min(a, b) ((a)<(b) ? (a):(b))
#define INF 1000000000000000000
#define MOD 1000000007LL
#define MAX 100010
#define BLACK 0
#define WHITE 1
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
typedef map<ll, ll> Map;

int main(void) {
    ll N;
    cin >> N;
    ll p;
    ll i;
    ll ans=0;
    ll max=0;
    
    for(i=0; i<N; i++) {
        cin >> p;
        ans+=p;
        max=max(p, max);
    }
    
    pr(ans-max/2);
    
    
}


Measured memory_bytes: 256
n = int(input())

times = n
table = []
for _ in range(times):
    a = int(input())
    temp = []
    for _ in range(a):
        x , y = map(int,input().split())
        temp.append([x-1,y])
    table.append(temp)  


def check(i,n):
    flg = True
    for j in range(n):
        if i>>j & 1:
            for x,y in table[j]:
                if (i>>x)&1 != y:
                    flg = False
                    return flg
    return flg
ans = 0
for i in range(2**n):
    if check(i,n):
        ans = max(bin(i).count("1"),ans)

print(ans)

Measured memory_bytes: 3064
#include <stdio.h>

int main(){
	int n,i,max=0,nmax=1000000000,a[100];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf(" %d",&a[i]);
		if(a[i]>=max)max=a[i];
		if(a[i]<=nmax)nmax=a[i];
	}
	printf("%d\n",max-nmax);
	return 0;
}


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

int main() {
    int N, M;
    cin >> N >> M;
    int sum = 0;
    rep(i, M) {
        int tmp;
        cin >> tmp;
        sum += tmp;
        if (sum > N) {
            cout << "-1" << endl;
            return 0;
        }
    }
    cout << N - sum << endl;
    return 0;
}


Measured memory_bytes: 3536
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pii=pair<int,int>;
#define For(i,a,b) for(int i=a;i<=b;i++)
#define F first
#define S second
#define all(x) x.begin(),x.end()
#define sz(x) ((int)x.size())
#define MOD (ll)(1e9+7)
#define INF (9e18)
#define EPS (1e-6)
#define debug(...) do{\
	cerr<<__PRETTY_FUNCTION__<<" - "<<__LINE__<<\
	" : ("#__VA_ARGS__<<") = ";\
	_OUT(__VA_ARGS__);\
}while(0)
template<typename T>void _OUT(T x){cerr<<x<<endl;}
template<typename T,typename...I>void _OUT(T x,I ...tail){cerr<<x<<", ";_OUT(tail...);}
void INIT(){
	ios::sync_with_stdio(false); cin.tie(0);
}

int gcd(int a,int b) { return b==0?a:gcd(b,a%b); }
int lcm(int a,int b) { return a/gcd(a,b)*b; }
int fpow(int b,int p){
	b%=MOD;
	int ans=1;
	while(p>0){
		if(p&1) ans=(ans*b)%MOD;
		p/=2;
		b=(b*b)%MOD;
	}
	return ans;
}

int32_t main() {
	INIT();
	//code...
	string s; cin>>s; s+='R';
	int n=sz(s);
	vector<int> ans(n,0);
	int l=0,r=0;
	int i=1;
	while(i<n){
		if(s[i]=='R' && s[i-1]=='L'){
			int a=(i-l)/2,b=(i-l)/2+(i-l)%2;
			if((r-l)%2) swap(a,b);
			ans[r-1]=a; ans[r]=b;
			l=i;
		}
		else if(s[i]=='L' && s[i-1]=='R'){
			r=i;
		}
		i++;
	}
	For(j,0,n-2) cout<<ans[j]<<" \n"[j==n-1];
	return 0;	
}






















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

int cnt=0;

void insertionSort(vector<int> &A,int n,int g){
  for(int i=g;i<n;i++){
    int v = A.at(i);
    int j=i-g;
    while(j>=0 && A.at(j)>v){
      A.at(j+g)=A.at(j);
      j-=g;
      cnt++;
    }
    A.at(j+g)=v;
  }
}

void shellSort(vector<int> &A,int n){
  cnt=0;
  int m=int(log(2*n-1)/log(3)) ;
  if(n==1){
    m=1;
  }
  vector<int> G(m);
  cout << m << endl;
  for(int k=0;k<m;k++){
    G.at(m-k-1)=(pow(3,k+1)-1)/2;
  }
  for(int h=0;h<m-1;h++){
    cout << G.at(h) << ' ';
  }
  cout << G.at(m-1) << endl;
  
  for(int i=0;i<m;i++){
    insertionSort(A, n, G.at(i));
  }
}

int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for(int i=0;i<N;i++){
    cin >> A.at(i);
  } 

  shellSort(A,N);
  cout << cnt << endl;

  for(int k=0;k<N;k++){
    cout << A.at(k) << endl;
  }


}


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

const ll INF = 1e18;

int main() {
  int n, k;
  cin >> n >> k;
  vector<ll> h(n + 2, 0);
  for (int i = 0; i < n; i++) {
    cin >> h[i + 1];
  }
  vector<vector<ll>> dp(n + 2, vector<ll>(n + 2, INF));
  dp[0][0] = 0;
  for (int i = 0; i < n + 1; i++) {
    for (int j = 0; j < i + 1; j++) {
      for (int t = 0; t < j + 1; t++) {
        dp[i + 1][j] = min(dp[i + 1][j], dp[i - t][j - t] + max(0LL, h[i + 1] - h[i - t]));
      }
    }
  }
  cout << dp[n + 1][k] << endl;
}


Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;
 
public class Main{
	static boolean[] d=new boolean[10];
	static boolean check(int x){
		String str=Integer.toString(x);
		for(int i=0;i<str.length();i++) if(d[str.charAt(i)-'0']) return false;
		return true;
	}
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext()){
			int n=sc.nextInt();
			int k=sc.nextInt();
			Arrays.fill(d,false);
			for(int i=0;i<k;i++) d[sc.nextInt()]=true;
			for(int i=n;;i++){
				if(check(i)){
					System.out.println(i);
					break;
				}
			}
		}
	}
}

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

int main(){
  int n,k;
  cin >> n >> k;
  vector<int> p;
  for(int i=0;i<n;i++){
    int t;
    cin >> t;
    p.push_back(t);
  }
  int sum = 0;
  sort(p.begin(),p.end());
  for(int i=0;i<k;i++){
    sum += p[i];
  }

  cout << sum << endl;
}

Measured memory_bytes: 3628
#include<iostream>
#include<string>
using namespace std;
int main() {
	int n, p[10], a = 0, b = 0, c = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		if (a <= p[i]) {
			a = p[i];
		}
	}
	for (int j = 0; j < n; j++) {
		if (a == p[j] && c == 0) {
			p[j] = p[j] / 2;
			c++;
		}
		b = b + p[j];
	}
	cout << b << endl;
	return 0;
}


Measured memory_bytes: 256
import sys
from collections import deque
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return list(map(int, sys.stdin.readline().split()))

def main():
    n, k = LI()
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        a, b = LI()
        g[a].append(b)
        g[b].append(a)

    s = 1
    Q = deque([s])
    ans = k
    Qappend = Q.append
    searched = [0] * (n+1)
    searched[s] = 1
    while len(Q) != 0:
        temp = 1
        v = Q.popleft()
        if v == s:
            cand = k - 1
        else:
            cand = k - 2
        for i in g[v]:
            if searched[i] == 1:
                continue
            searched[i] = 1
            temp = temp * cand % MOD
            cand -= 1
            Qappend(i)
        ans = ans * temp % MOD
    print(ans % MOD)


if __name__ == "__main__":
    main()


Measured memory_bytes: 30120
#include<stdio.h>
#include<algorithm>
using namespace std;
int b[110];
int dp[110][110];
int tmp[110][110];
int n;
inline int ABS(int a){return max(a,-a);}
int ad[110][110];
int solve(int l,int r){
	if(~dp[l][r])return dp[l][r];
	if(l==r)return dp[l][r]=0;
	int sz=(r-l+n)%n;
	for(int i=0;i<=sz;i++){
		tmp[l][i]=-99999999;
	}
	tmp[l][0]=0;
	for(int i=0;i<sz;i++){
		dp[l][ad[l][i]]=tmp[l][i];
		int t=ABS(b[l]-b[ad[l+1][i]]);
		for(int j=sz-i;j>=1;j--){
			tmp[l][i+j]=max(tmp[l][i+j],tmp[l][i]+t+solve(ad[l][i+1]%n,ad[l][i+j]));
		}
	}
	//printf("%d %d: %d\n",l,r,tmp[(r-l+n)%n]);
	return dp[l][r]=tmp[l][sz];
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		int a;scanf("%d",&a);for(int i=0;i<a;i++)scanf("%d",b+i);
		n=a;
		for(int i=0;i<110;i++)for(int j=0;j<110;j++)ad[i][j]=(i+j)%n;
		int ret=0;
		for(int i=0;i<a;i++)for(int j=0;j<a;j++)dp[i][j]=-1;
		for(int i=0;i<a;i++){
			ret=max(ret,solve(i,(i+a-1)%a));
		}
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 1156
#include <iostream>

using namespace std;
bool TestPythagoras(int a,int b,int c)
{
   if(a*a==b*b+c*c)
    return true;
   else return false;
}

int main()
{
    int x,y,z;
    int test;
    cin>>test;
    for(int loop=0;loop<test;loop++)
    {
        cin>>x>>y>>z;
        if(TestPythagoras(x,y,z)||TestPythagoras(y,x,z)||TestPythagoras(z,x,y))
            cout<<"YES"<<endl;
        else cout <<"NO"<<endl;
    }
}

Measured memory_bytes: 1152
#include <stdio.h>

int main(void)
{
    double v;
    int n;

    while (scanf("%lf", &v) != EOF) {
        for (n = 1; v * v >= 19.6 * (5 * n - 5); n++)
            ;
        printf("%d\n", n);
    }

    return 0;
}

Measured memory_bytes: 628
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>
#include <map>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
#define mii map<int, int>
#define msi map<string, int>
#define vi vector<int>
#define vl vector<ll>
#define MOD 1000000007
#define INF 1e9
#define showVector(v) rep(i,0,v.size()){p(v[i]);p(" ")} pl("")
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
using namespace std;

// 素数判定 O(√n)
bool is_prime(int n){
    for(int i = 2; i * i <= n; i++){
        if(n % i == 0) return false;
    }
    return true;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;

}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int main() {
    int r, D, x;
    cin >> r >> D >> x;
    rep(i, 0, 10) {
        x = r * x - D;
        cout << x << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<array>
#include<vector>
#include <algorithm>
#include <stdio.h>
#include <string>
#include <utility>
#include <set>
#include <map>
#include <tuple>
#include<cmath>

using lli = long long int;
using namespace std;
#define sort(X) sort(X.begin(),X.end())

int inf = 1000000007;
int K;

int main() {
	cin >> K;
	vector<long> A(K);
	long L, R;
	for (int i = 0; i < K; i++)cin >> A[i];
	L = R = 2;
	for (int i = K - 1; i >= 0; i--) {
		//最小化
		L = A[i] * ceil(L / (A[i] + .0));
		//最大化
		R = A[i] * (R / A[i]) + A[i] - 1;
	}
	if (L > R)cout << -1 << endl;
	else cout << L << " " << R << endl;
	return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int mod = 1000000007;

int main() {
    ios::sync_with_stdio(false);
    int r, d, x;
    cin >> r >> d >> x;
    for (int i = 1; i <= 10; i++) cout << r * x - d << ' ', x = r * x - d;
}


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

a, b = max(a, b), min(a, b)
d = a - b

if d % 2 == 0:
    ans = d // 2
    print(ans)
    exit()

count = 0
add = b-1
c = a - (add+1)
count += add+1
count += (c-1)//2
pat1 = count

count = 0
add = n-a
c = b + (add+1)
count += add + 1
count += (n-c)//2
pat2 = count

print(min(pat1, pat2))

Measured memory_bytes: 3064
use strict;
use warnings;

sub main {
    my $i=0;
    my ($N,@A,@B,@C);
    while(<STDIN>){
        chomp;
        if($i==0){
            ($N) = split(/ /,$_);
        } elsif($i==1) {
            @A = split(/ /, $_);
        } elsif($i==2) {
            @B = split(/ /, $_);
        } elsif($i==3) {
            @C = split(/ /, $_);
        }
        $i++;
    }
    print solver($N,\@A,\@B,\@C);
}
main() unless caller;

sub solver {
    my ($N,$A,$B,$C) = @_;
    my $ans = 0;
    for(0..$N-1){
        $ans+=$B->[$_];
    }
    for my $i(0..$N-2) {
        if($A->[$i] + 1 == $A->[$i+1]){
            $ans+=$C->[$A->[$i]-1];
        }
    }
    return $ans;
}

Measured memory_bytes: 640
#include <iostream>
#include<sstream>
#include<vector>
#include<iterator>
#include<utility>
#include<climits>
using namespace std;

typedef pair<int, long long> Edge;

void dfs(int pos, long long cost, const vector<vector<Edge>>&edge, vector<long long>& dist)
{
	if(cost > dist[pos])
		return;

	dist[pos] = cost;
	for(auto it=edge[pos].begin(); it!=edge[pos].end(); it++)
		dfs(it->first, cost+it->second, edge, dist);
}

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

	vector<vector<Edge>> edge(N);
	for(int i=0; i<N-1; i++)
	{
		int a, b;
		long long c;
		cin >> a >> b >> c;

		a--;
		b--;

		edge[a].emplace_back(make_pair(b, c));
		edge[b].emplace_back(make_pair(a, c));
	}

	int Q, K;
	cin >> Q >> K;
	K--;

	vector<long long> dist(N, LLONG_MAX);
	dfs(K, 0, edge, dist);

	for(int i=0; i<Q; i++)
	{
		int x, y;
		cin >> x >> y;

		x--;
		y--;

		cout << dist[x] + dist[y] << endl;
	}


	return 0;
}


Measured memory_bytes: 14336