akhauriyash/Code-Regression huggingface dataset:
#xyzの全通り調べると間に合わない
#まず問題を分けよう
#先にxyだけ考えてみる
#xyの和をとってからそれとzの和をとるとき
#xyの和においてk番目以降の値を使うことは無い
#

def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 10**9 + 7

    x,y,z,k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    c = list(map(int, input().split()))
    a.sort(reverse=1)
    b.sort(reverse=1)
    c.sort(reverse=1)
    abc = []
    for i in range(x):
        for j in range(y):
            if i*j>k:
                continue
            for t in range(z):
                if i*j*t>k:
                    continue
                abc.append(a[i]+b[j]+c[t])
    abc.sort(reverse=1)
    for i in range(k):
        print(abc[i])

if __name__ == '__main__':
    main()

Measured memory_bytes: 105356
import java.util.Scanner;

public class Main {
	public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int x = sc.nextInt();
		sc.close();

		double y = 2.0 * x / a / b;
		if (y <= a) {
			double r = Math.atan2(b, y);
			System.out.println(180 * r / Math.PI);
		} else {
			double h = 2.0 * x / a / a - b;
			double r = Math.atan2(b - h, a);
			System.out.println(180 * r / Math.PI);
		}
	}
}


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

int main(void){
    int x, a, b;
    cin >> x >> a >> b;
    
    string s;
    if(a-b >= 0) s = "delicious";
    else if(x >= b-a) s = "safe";
    else s = "dangerous";

    cout << s << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef long double Double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)

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

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

typedef complex<double> P;

void solve(long long A, long long B, long long H, long long M) {
    double rad1 = 2 * M_PI * (H * 60 + M) / (12.0 * 60.0);
    double rad2 = 2 * M_PI * M / 60.0;
    printf("%.10lf\n", abs(1. * A * exp(P(0, rad1)) - 1. * B * exp(P(0, rad2))));
}

int main() {
    long long A;
    scanf("%lld", &A);
    long long B;
    scanf("%lld", &B);
    long long H;
    scanf("%lld", &H);
    long long M;
    scanf("%lld", &M);
    solve(A, B, H, M);
    return 0;
}


Measured memory_bytes: 4188
#include <iostream>
typedef long long int ll;
using namespace std;

int main() {
	ll a,b,c,d;
	cin>>a>>b>>c>>d;
	ll op1 = a*c;
	ll op2 = a*d;
	ll op3 = b*c;
	ll op4 = b*d;
	cout<<max(max(op1,op2),max(op3,op4))<<endl;
	return 0;
}

Measured memory_bytes: 3608
n, q = map(int, input().split())
g = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    g[a].append(b)
    g[b].append(a)

X = [0]*n
for i in range(q):
    p, x = map(int, input().split())
    p -= 1
    X[p] += x

s = []
visit = [-1]*n
s.append(0)
visit[0] = 0
while s:
    v = s.pop()
    for u in g[v]:
        if visit[u] == -1:
            X[u] += X[v]
            s.append(u)
            visit[u] = 0
print(*X)


Measured memory_bytes: 106956
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Scanner;

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

    static class DStaticSushi {
        public void solve(int testNumber, Scanner in, PrintWriter out) {

            int n = in.nextInt();
            long c = in.nextLong();
            long[] x = new long[n];
            long[] v = new long[n];
            long[] f = new long[n];
            long[] fm = new long[n];
            long[] g = new long[n];
            long[] gm = new long[n];

            long max = 0;

            for (int i = 0; i < n; i++) {
                x[i] = in.nextLong();
                v[i] = in.nextLong();
            }

            for (int i = 0; i < n; i++) {
                if (i == 0) {
                    f[i] = v[i] - x[i];
                    fm[i] = f[i];
                } else {
                    f[i] = f[i - 1] + v[i] - x[i] + x[i - 1];
                    fm[i] = Math.max(fm[i - 1], f[i]);
                }
            }

            for (int i = n - 1; i >= 0; i--) {
                if (i == n - 1) {
                    g[i] = v[i] - c + x[i];
                    gm[i] = g[i];
                } else {
                    g[i] = g[i + 1] + v[i] - (x[i + 1] - x[i]);
                    gm[i] = Math.max(gm[i + 1], g[i]);
                }
            }

            max = Math.max(max, gm[0]);
            max = Math.max(max, fm[n - 1]);
            for (int i = 0; i < n - 1; i++) {
                long cmp = f[i] - x[i] + gm[i + 1];
                max = Math.max(max, cmp);
            }

            for (int i = 1; i < n; i++) {
                long cmp = g[i] - (c - x[i]) + fm[i - 1];
                max = Math.max(max, cmp);
            }

            out.println(max);


        }

    }
}



Measured memory_bytes: 98000
#include <iostream>
#include <string>

using namespace std;

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

int main(){
  string s,t;
  cin >> s >> t;

  int ans = 0;
  rep(i,s.size())
    if(s[i] != t[i]) ans++;

  cout << ans << endl;
  
}

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

const int MOD=1000000007;
const int INF=0x3f3f3f3f;
const ll INFL=0x3f3f3f3f3f3f3f3f;

int main(){
	ll a,b,c,d;cin>>a>>b>>c>>d;
	vector<ll>A{a,b},B{c,d};
	ll Max=LLONG_MIN;
	rep(i,2)rep(j,2){
		Max=max(Max,A[i]*B[j]);
	}
	cout<<Max<<endl;
}

Measured memory_bytes: 3628
#!/usr/bin/env python3


def read_h(typ=int):
    return list(map(typ, input().split()))


def read_v(n, typ=int):
    return [typ(input()) for _ in range(n)]


def main():
    n, l = read_h()
    s = ''.join(sorted(read_v(n, typ=str)))
    print(s)


if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
N,A,B,C=map(int,input().split())
L=[0]*(N)
for i in range(N):
    L[i]=int(input())
    

def calc(m):
    s=[0,0,0,0]
    sy=-3
    for i in range(N):
        s[m%4]+=L[i]
        if m%4!=0:
            sy+=1
        m=m//4
    for i in range(1,4):
        if s[i]==0:
            return 10**9
    return abs(A-s[1])+abs(B-s[2])+abs(C-s[3])+sy*10
    
ans=10**9
for i in range(pow(4,N)):
    ans=min(ans,calc(i))
print(ans)
    

Measured memory_bytes: 42972
// D - Menagerie
#include <bits/stdc++.h>
using namespace std;

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

	vector<bool> q(N+1);
	for(int i=0; i<N; i++) q[i] = S[i]=='o'? true:false;
	q[N] = q[0];

	vector<bool> a(N+2);
	vector<bool> b0{1,1,0,0};
	vector<bool> b1{1,0,1,0};

	for(int i=0; i<4; i++){
		a[0] = b0[i]; a[1] = b1[i];

		for(int j=2; j<N+2; j++){

			if(a[j-1] && q[j-1]) a[j] = a[j-2];
			if(a[j-1] && !q[j-1]) a[j] = !a[j-2];
			if(!a[j-1] && q[j-1]) a[j] = !a[j-2];
			if(!a[j-1] && !q[j-1]) a[j] = a[j-2];

		}

		if(a[0]==a[N] && a[1]==a[N+1]) break;
	}

	if(a[0]==a[N] && a[1]==a[N+1])
		for(int i=0; i<N; i++) cout<<(a[i]?'S':'W');
	else cout<<"-1";
	cout<<"\n";
}


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

int main()
{
	std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    long test=1;
// 	cin>>test;	
	while(test--)
	{
	    long a,b=0,c=0,k,i,n,j,temp,mini,maxi,ans,q,sum,x,y;
	    cin>>n>>k>>x>>y;
	    if(n>=k)
	    sum=k*x;
	    else sum=n*x;
	    for(i=0;i<n-k;i++)
	    sum+=y;
	    cout<<sum;
	
	
    }
    
}


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

int main(void)
{
    int a,b,c,d,i,j;
    scanf("%d %d",&a,&b);
    c=b;
    for(i=0;c>0;i++)
    {
        c/=10;
    }
    for(j=1;j<=i;j++)
    {
        a*=10;
    }
    d=0;
    a+=b;
    for(i=0;i<=(a/2);i++)
        if(a==(i*i))
    {
        d=1;
        break;
    }
    if(d)
        printf("Yes");
    else
        printf("No");
    return 0;
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
    int W,H,x,y,r;
    cin >> W >> H >> x >> y >> r;
    if ((0<=(x-r)&&(x+r)<=W)&&(0<=(y-r)&&(y+r)<=H))cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    
    return 0;
}


Measured memory_bytes: 3116
s=input()
if len(s)<5:
  print('NO')
  exit()
while len(s)>=5:
  if s[len(s)-5:len(s)]=='dream' or s[len(s)-5:len(s)]=='erase':
    s=s[:len(s)-5]
  elif len(s)>=6 and s[len(s)-6:len(s)]=='eraser':
    s=s[:len(s)-6]
  elif len(s)>=7 and s[len(s)-7:len(s)]=='dreamer':
    s=s[:len(s)-7]
  else:
    print('NO')
    exit()
if len(s)==0:
  print('YES')
else:
  print('NO')

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define pi pair<int,int>
#define pl pair<long long,long long>
#define lg length()
#define pb push_back
ifstream in("file.in");
ofstream out("file.out");
#define MAXN 100005
#define INF 1000000005
#define LINF 1000000000000000005

int n,m,x,y,s,v[100005];

vector <int> g[100005],ans1,ans2;

void DFS(int nod, int p){
    v[nod]=1;
    if(p>=0) ans1.push_back(nod);
    else ans2.push_back(nod);
    for(int i : g[nod]){
        if(!v[i]){
            if(p==0){
                DFS(i,1);
                break;
            }
            else{
                DFS(i,p);
                return;
            }
        }
    }
    for(int i : g[nod]){
        if(!v[i]){
            DFS(i,-1);
            return;
        }
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=m;i++){
        cin >> x >> y;
        s=x;
        g[x].pb(y); g[y].pb(x);
    }
    DFS(s,0);
    cout << ans1.size()+ans2.size() << '\n';
    reverse(ans2.begin(),ans2.end());
    for(int i : ans2) cout << i << ' ';
    for(int i : ans1) cout << i << ' ';
}


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

int main() {
    string A;
    cin >> A;
    int N = (int)A.size();
    vector<long long> cnt(26);
    for (int i = 0; i < N; i++)
        cnt[A[i] - 'a']++;

    long long res = (long long)N * (N - 1) / 2;
    for (int i = 0; i < 26; i++) {
        res -= cnt[i] * (cnt[i] - 1) / 2;
    }

    cout << res + 1 << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <algorithm>
using namespace std;
template <typename T = int>
T in() {
    T temp; cin >> temp; return temp;
}

template <typename VType = int>
list<VType> const LR(VType start, VType end) {
    list<VType> ret; for (VType i = start; i < end; i++) ret.push_back(i); return move(ret);
}

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

    for (int i = 1; i <= N; i++) {
        cin >> A[i];
    }

    for (int i = 1; i <= N; i++) {
       cin >> B[i];
    }

    for (int i = 1; i < N; i++) {
        cin >> C[i];
    }
    int sum = 0;
        for (int i = 1; i <= N; i++) {

            sum += B[A[i]];
if (1 < i && ((A[i - 1] + 1) == A[i] )) sum += C[A[i - 1]];
        }
        cout << sum << endl;

    return 0;
}




Measured memory_bytes: 256
#include <functional>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <iomanip>
#include <vector>
#include <string>
#include <cstdio>
#include <queue>
#include <stack>
#include <cmath>
#include <map>
#include <set>
#if __cplusplus >= 201103L
#include <unordered_map>
#include <unordered_set>
#endif
#define ls x<<1
#define rs x<<1|1
#define fi first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define fun function
#define vi vector<int>
#define lowbit(x) x&(-x)
#define pii pair<int,int>
#define all(x) x.begin(),x.end()
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0);

using namespace std;

const int INF = 0x3f3f3f3f;
int a,b;
bool check(int x) {
	double s=floor(x*0.08);
	double ss=floor(x*0.1);

	int aa=(int)s;
	int bb=(int)ss;

	if(aa>=a && bb>=b)return true;
	else return false;
}

bool q(int x) {
	double s=floor(x*0.08);
	double ss=floor(x*0.1);

	int aa=(int)s;
	int bb=(int)ss;

	if(aa==a && bb==b)return true;
	else return false;
}

int main() {
	IOS;
#ifdef xiaofan
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
#endif


	cin>>a>>b;

	int l=1,r=1e8;
	int ans=-1;
	while(r>=l) {
		int mid=l+r>>1;
		if(check(mid)) {
			ans=mid;
			r=mid-1;
		} else {
			l=mid+1;
		}
	}
	if(q(ans))
		cout<<ans<<endl;
	else
		cout<<-1<<endl;



	return 0;
}



Measured memory_bytes: 256
while True:
  try:
    n = int(raw_input())
  except EOFError:
    break
  count = 0
  for a in range(0, 10):
    for b in range(0, 10):
      for c in range(0, 10):
        for d in range(0, 10):
          if (a + b + c + d) == n:
            count += 1
  print count

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

#define rep(i, a) for (int i = 0; i < (a); i++ )
#define FOR(i, m, n) for(int i = m; i < n; i++)
 
typedef pair<int,int> P;
typedef long long ll;
 
const int INF = 1001001001;
const int MOD = 1000000007;
const double PI=acos(-1);

ll num = 0;
ll N = 0;

void dfs(vector<int> &A, int d) {
    if (A.size()==d) {
        num++;
        if (num==N) {
            rep(i,A.size()) {
                cout << A[i];
            }
            cout << endl;
        }
    }
    else {
        if (A.size()==0) {
            rep(j,9) {
                A.push_back(j+1);
                dfs(A,d);
                A.pop_back();
            }
        }
        else {
            int n = A.back();
            for (int j = max(0,n-1); j<=min(n+1,9) ; j++) {
                A.push_back(j);
                dfs(A,d);
                A.pop_back();
            }
        }
    }
}

int main(){
    cin >> N;
    num = 0;
    int cnt = 1;
    while(num<N) {
        vector<int> A;
        dfs(A,cnt);
        cnt++;
    }
}

Measured memory_bytes: 3616
import math
n = int(input())

train_list = []
for i in range(n-1):
    array = list(map(int,input().split()))
    train_list.append(array)


for i in range(n-1):
    time = 0
    for j in range(i, n-1):
        if i == j:
            time += (train_list[i][0] + train_list[i][1])
        else:
            if train_list[j][1] // time >= 1:
                time = train_list[j][1]
                time += train_list[j][0]
            else:
                p = math.ceil((time - train_list[j][1])/train_list[j][2])
                time = train_list[j][1] + train_list[j][2] * p
                time += train_list[j][0]
    print(time)

print(0)



Measured memory_bytes: 3188
def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

a,b,c,k=n1()
if a+b>=k:
    print(min(a,k))
else:
    print(a-(k-a-b))

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

int main(){
	string s;
	cin >> s;
	while(s.size()){
		if(s.size() < 5){
			cout << "NO" << endl;
			return 0;
		}
		if(s.substr(s.size()-5) == "dream"){
			s.erase(s.size()-5);
		}else if(s.substr(s.size()-5) == "erase"){
			s.erase(s.size()-5);
		}else if(s.size() >= 6 && s.substr(s.size()-6) == "eraser"){
			s.erase(s.size()-6);
		}else if(s.size() >= 7 && s.substr(s.size()-7) == "dreamer"){
			s.erase(s.size()-7);
		}else{
			cout << "NO" << endl;
			return 0;
		}
	}
	cout << "YES" << endl;
	
	return 0;
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
#define pb push_back
#define sf scanf
#define pf prllf
using namespace std;
#define ll long long
const int N=2e6+9;
map<ll,ll>row,col;
map< pair<ll,ll>, bool>vis;
void slv()
{
    ll h,w,m;
    cin >> h >> w >> m;
    for(ll i=0;i<m;i++) {
        ll x,y;
        cin >> x >> y;
        row[x] ++;
        col[y] ++;
        vis[{x,y}]=true;
    }
    vector< pair<ll,ll> >vx,vy;
    ll mxx=0LL,mxy=0LL;
    for(ll i=1;i<=h;i++) {
        if(row[i]>mxx) {
            vx.clear();
            vx.push_back({row[i],i});
            mxx=row[i];
        } else if(row[i] == mxx) vx.push_back({mxx,i});
    }
    for(ll i=1;i<=w;i++) {
        //cout<<i<<" X "<<col[i]<<endl;
        if(col[i]>mxy) {
            vy.clear();
            vy.push_back({col[i],i});
            mxy=col[i];
        } else if(col[i] == mxy) vy.push_back({mxy,i});
    }
   // cout<<mxx<<" "<<mxy<<endl;
    ll ans=mxx+mxy-1;
    for(auto it1 : vx) {
        for(auto it2 : vy) {
            if(!vis[{it1.second,it2.second}]) {
                cout<<mxx+mxy<<endl;
                return ;
            }
        }
    }
    cout<<ans<<endl;
}
int main()
{
    ll t;
    t=1;
    for(int cs=1;cs<=t;cs++) {
        slv();
    }
    return 0;
}


Measured memory_bytes: 76404
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include<algorithm>
#include<sstream>
#include<iomanip>


using namespace std;



int main() {
	int n;
	cin >> n;
	vector<int> cnt(5);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		switch (s[0]) {
		case 'M': cnt[0]++;
			break;
		case 'A': cnt[1]++;
			break;
		case 'R': cnt[2]++;
			break;
		case 'C': cnt[3]++;
			break;
		case 'H': cnt[4]++;
			break;
		}
	}
	long long ans = 0;
	
	for (int i = 0; i < 3; i++) {
		for (int j = i + 1; j < 4; j++) {
			for (int k = j + 1; k < 5; k++) {
				ans += 1LL *cnt[i] * cnt[j] * cnt[k];
			}
		}
	}

	
	cout << ans << endl;
}

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

const int mod = 1e9 + 7;

typedef pair<int, int> pii;

const int MN = 100010;

int N, M;
int X[MN], Y[MN];
vector<pii> D;

int Xn;
vector<int> xx;
unordered_map<int, int> dx;

struct Fenwick {
    vector<int> tree;
    void init() {
        tree = vector<int>(Xn + 1, 0);
    }
    void upd(int idx, int val) {
        for(int i = idx + 1; i <= Xn; i += (i & -i)) tree[i] += val, tree[i] %= mod;
    }
    int quer(int a) {
        if(a >= Xn) a = Xn - 1;
        int ret = 0;
        for(int i = a + 1; i >= 1; i -= (i & -i)) ret += tree[i], ret %= mod;
        return ret;
    }
    int quer(int a, int b) {
        return (quer(b) + mod - quer(a - 1)) % mod;
    }
} fw;

bool cmp(pii a, pii b) {
    return a.first < b.first || (a.first == b.first && a.second > b.second);
}

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

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

    int pos = 0;
    for(int i = 0; i < N; i++) {
        while(pos < M && Y[pos] < X[i]) pos++;

        if(pos == 0 || pos == M) continue;

        D.push_back(pii(X[i] - Y[pos - 1], Y[pos] - X[i]));
    }

    sort(D.begin(), D.end(), cmp);
    D.resize(unique(D.begin(), D.end()) - D.begin());
    N = D.size();

    for(int i = 0; i < N; i++) {
        xx.push_back(D[i].second);
    }
    sort(xx.begin(), xx.end());
    xx.resize(unique(xx.begin(), xx.end()) - xx.begin());
    Xn = xx.size();
    for(int i = 0; i < Xn; i++) dx[xx[i]] = i;
    for(int i = 0; i < N; i++) D[i].second = dx[D[i].second];

    fw.init();
    int ans = 0;
    for(int i = N - 1; i >= 0; i--) {
        int t = 1 + fw.quer(D[i].second + 1, Xn - 1);
        fw.upd(D[i].second, t);

        ans += t;
        ans %= mod;
    }
    printf("%d", (ans + 1) % mod);
}


Measured memory_bytes: 6260
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <map>
#include <memory>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <sstream>
#include <unordered_map>
#include <vector>


#define INF 4000000000000000000LL
#define MOD 1000000007
#define ALL(x) std::begin(x), std::end(x)


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

  std::cout << std::fixed << std::setprecision(6);
  std::cerr << std::fixed << std::setprecision(6);

  int a[4];

  std::cin >> a[0] >> a[1] >> a[2] >> a[3];

  std::sort(a, a + 4);

  std::cout << (a[0] == 1 && a[1] == 4 && a[2] == 7 && a[3] == 9 ? "YES" : "NO") << std::endl;
  
  return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const mod = 1000000007

// 1MB
const ioBufferSize = 1 * 1024 * 1024

var sc = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Buffer(make([]byte, ioBufferSize), ioBufferSize)
	sc.Split(bufio.ScanWords)
	return sc
}()

func next() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func main() {
	a, b, c := nextInt(), nextInt(), nextInt()

	res := 0
	for ; a%2 != 1 && b%2 != 1 && c%2 != 1; {
		if a == b && b == c {
			fmt.Println(-1)
			return
		}
		a, b, c = (b+c)/2, (c+a)/2, (a+b)/2
		res++
	}

	fmt.Println(res)
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <map>
#include <math.h>
#include <complex>

using namespace std;

char decode(char s,int k){

    //cout<<s<<endl;

    for(int i=0;i<k;i++){
        if(s=='a') s='Z';
        else if(s=='A') s='z';
        else s=s-1;
        //cout<<s<<endl;
    }

      return s;

}

int main(){

    int n;
   
    while(cin>>n,n){

        string s;
        int k[100];

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

        cin>>s;

        for(int i=0;i<s.size();i++){
            cout<<decode(s[i],k[i%n]);
        }

        cout<<endl;

    }

    return 0;
}


Measured memory_bytes: 3132
import sys
from itertools import combinations

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60


def main():
    N, K, *A = map(int, read().split())

    ans = INF
    for comb in combinations(range(1, N), K - 1):
        included = set(comb)
        total = 0
        max_height = A[0]
        for i, a in enumerate(A[1:], 1):
            if a <= max_height:
                if i in included:
                    total += max_height - a + 1
                    max_height += 1
            else:
                max_height = a

        if ans > total:
            ans = total

    print(ans)
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
S = list(map(int,input().split()))
T = list(map(int,input().split()))
dp = [[0]*(M+1) for i in range(N+1)]

for n in range(N):
    for m in range(M):
        if S[n] == T[m]:
            dp[n+1][m+1] = (dp[n+1][m]+dp[n][m+1]+1)%mod
        else:
            dp[n+1][m+1] = dp[n+1][m]+dp[n][m+1]-dp[n][m]

print((dp[N][M]+1)%mod)

Measured memory_bytes: 330368
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v)   (v).begin(),(v).end()
#define debug(x) cerr<<#x<<": "<<(x)<<endl
#define INF      (int)1e9
#define EPS      (double)1e-9
#define MOD      ((int)1e9+7)
using namespace std;
typedef long long     llong;
typedef vector<int>   vi;
typedef vector<vi >   vvi;
typedef vector<vvi >  vvvi;
typedef pair<int,int> pii;
template<class Type> void line(const Type &a){int cnt=0;for(const auto &elem:a){if(cnt++)cout<<' ';cout<<elem;}cout<<endl;}

//解説参考.
int main(){
	int n;
	cin>>n;
	
	llong ans=0;
	for(llong i=1;i<=n;++i){
		llong tmp=n/i;
		ans+=i*tmp*(tmp+1)/2;
	}
	
	cout<<ans<<endl;
}

Measured memory_bytes: 3628
from collections import deque

stack = []
stack2 = []

input_line = input().rstrip()

menseki = 0

for i, s in enumerate(input_line):
    if s == "\\":
        stack.append(i)
    elif s == "/" and len(stack) > 0:
        j = stack.pop()
        menseki += (i - j)
        temp_menseki = 0
        while len(stack2) > 0 and j < stack2[-1][0]:
            temp_menseki += stack2.pop()[1]
                    
        stack2.append([j, temp_menseki + (i - j)])

print(menseki)
if len(stack2) > 0:
    print(len(stack2), " ".join([str(j[1]) for j in stack2]))
else:
    print("0")




Measured memory_bytes: 6672
#include <bits/stdc++.h>
#pragma once
using namespace std;
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;
typedef long double lb;
#define int long long
#define double long double
typedef pair<int,int> P;
const int MOD = 1000000007;
const ll INF = 1e16;
const double EPS = 1e-10;
const double PI = 3.141592653589793;
template<class T> inline bool chmin(T& a, T b){if(a>b){a = b;return 1;}return 0;}
template<class T> inline bool chmax(T& a, T b){if(a<b){a = b;return 1;}return 0;}
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 


////////////////////////////////////////////////////////////////////

////////////////////////////////////////////////////////////////////

string s;int n;
signed main(){
  cin>>s;
  n = s.length();
  reverse(s.begin(), s.end());
  s += '#';
  s += '#';
  string dream = "maerd", dreamer = "remaerd", erasE = "esare", eraser = "resare";
  int i = 0;bool ret = true;
  while(i < n){
    if(s[i] == 'm'){
      rep(j,5){
        if(i >= n || s[i++] != dream[j]){
          ret = false;break;
        }
      }
    }else if(s[i] == 'r' && s[i+1] == 'e' && s[i+2] == 'm'){
      rep(j,7){
        if(i >= n || s[i++] != dreamer[j]){
          ret = false;break;
        }
      }
    }else if(s[i] == 'r' && s[i+1] == 'e' && s[i+2] == 's'){
      rep(j,6){
        if(i >= n || s[i++] != eraser[j]){
          ret = false;break;
        }
      }
    }else if(s[i] == 'e'){
      rep(j,5){
        if(i >= n || s[i++] != erasE[j]){
          ret = false;break;
        }
      }
    }else{
      ret = false;break;
    }
  }
  cout << (ret ? "YES" : "NO") << endl;
}


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

int main() {
  string S;
  cin >> S;
  
  int ans = 700;
  for (int i=0; i<3; ++i) {
    if (S[i] == 'o') ans += 100;
  }
  cout << ans << endl;
  
  return 0;
}

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

int main(){
	int n,m,ans = 0;
	vector<int> h,v;

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		int hi;
		cin >> hi;
		h.push_back(hi);
		v.push_back(1);
	}

	for (int j = 0; j < m; j++) {
		int a, b;
		cin >> a >> b;
		if (h[a - 1] < h[b - 1]) {
			v[a - 1] = 0;
		}
		else if(h[a - 1] > h[b - 1]) {
			v[b - 1] = 0;
		}
		else {
			v[a - 1] = 0;
			v[b - 1] = 0;
		}
	}

	ans = count(v.begin(), v.end(), 1);

	cout << ans;
}

Measured memory_bytes: 4024
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>

using namespace std;
int A[100001];
int n;
int partition(){
	int i = -1;
	for (int j = 0; j < n - 1; ++j) if (A[j] <= A[n-1]) swap(A[++i], A[j]);
	swap(A[i + 1], A[n-1]);
	return i + 1;
}
int main(){
	scanf("%d",&n);
	for (int i = 0; i < n; ++i) scanf("%d",&A[i]);
	int pivot = partition();
	for (int i = 0; i < n; ++i){
		if (i != 0) cout << ' ';
		if (i == pivot){
			cout << '[' << A[i] << ']';
		}
		else cout << A[i];
	}
	cout << '\n';
}

Measured memory_bytes: 1592
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>   
using namespace std;
using namespace __gnu_pbds;
typedef long long ll; 
#define int long long
typedef unsigned long long lu;
typedef vector<ll> v;
typedef vector<vector<ll> > vv;
typedef vector<string>  vs;
typedef vector<pair<ll,ll>> vpr;
typedef vector<bool>vb;
typedef vector<double>vd;
typedef long double ld;
#define f(i,n) for(ll i = 0; i < n; i++)
#define ff(i,n) for(ll i=1;i<=n;i++)
#define pb push_back
#define mp make_pair
#define endl "\n"
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define amax(x,y) if(y>x) x=y;
#define amin(x,y) if(y<x)x=y;
#define bg(x) x.begin()
#define sz(x) (ll)x.size()
#define in(x,n) for(ll i=0;i<n;i++)cin>>x[i]
#define out(x,n) for(ll i=0;i<n;i++)cout<<x[i]<<" " 
#define mxt(a) *(max_element(a.begin(),a.end()))
#define mnt(a) *(min_element(a.begin(),a.end())
#define tc ll t;cin>>t;while(t--)
typedef pair<ll,ll> pi;
#define yes cout<<"YES\n";
#define no cout<<"NO\n";
#define yesno(f) if(f) yes else no
const v dx = {1, -1, 0, 0};
const v dy = {0, 0, 1, -1};
const ld PI = 2 * acos(0.0);
ll cel(ll x1,ll y1){if((x1%y1)==0)return x1/y1;else return x1/y1+1;}
ll power(ll a,ll b,ll m)
{
    if(b==0)
        return 1;
    ll d=power(a,b/2,m);
    d=(d*d)%m;
    if(b&1)
        d=(d*a)%m;
    return d;
}
const ll mod=1e9+7;
int MOD(int a)
{
    if(a<0)
        a+=mod;
    if(a>=mod)
        a%=mod;
    return a;
}
// set_name.find_by_order(k) It returns to an iterator to the kth element (counting from zero) in the set in O(logn) time
// set_name.order_of_key(k) It returns to the number of items that are strictly smaller than our item k in O(logn) time.
/*string operations :
str.substr (x,y) : returns a substring str[x],str[x+1],...str[x+y-1]
str.substr (x) : returns a substring str[x],... end of string
str.find(qtr) : returns the first occurenece of qtr in str */
int32_t main()
{
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    // freopen("input.txt", "r", stdin);
 
    // freopen("output.txt", "w", stdout);
    int n;cin>>n;
    v a(n);in(a,n);
    int x=0;
    f(i,n)
    x^=a[i];
    f(i,n)
    cout<<(x^a[i])<<" ";
    return 0;
}

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

#define int long long
#define For(i, a, b) for (int i = (a); i <= static_cast<int>(b); i++)
#define Forr(i, a, b) for (int i = (a); i >= static_cast<int>(b); i--)
#define rep(i, n) For(i, 0, n - 1)
#define repall(i, arr) for (auto& i : (arr))
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define dump(x) cerr << #x << " = " << (x) << '\n'
#define dump2(x, y) \
    cerr << #x << " = " << (x) << " " << #y << " = " << (y) << '\n'

template <typename T>
using pq = priority_queue<T>;
template <typename T>
using pqr = priority_queue<T, vector<T>, greater<T>>;
const int INF = INT_MAX / 2;
constexpr int MOD = 1e9 + 7;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vec>;

template <typename T1, typename T2>
ostream& operator<<(ostream& stream, const pair<T1, T2>& p) {
    return stream << p.first << " " << p.second;
}
template <typename T>
void print(const vector<vector<T>> matrix) {
    repall (vec, matrix)
        print(vec);
}
template <typename T>
void print(const vector<T> vec) {
    unsigned int len = vec.size();
    rep (i, len - 1)
        cout << vec[i] << ' ';
    cout << vec[len - 1] << '\n';
}
template <typename Arg>
void print(const Arg arg) {
    cout << arg << '\n';
}
template <typename Head, typename... Args>
void print(const Head head, const Args... args) {
    cout << head << " ";
    print(args...);
}
template <typename T>
T sum_(vector<T> vec, T init = 0) {
    return std::accumulate(all(vec), T(init));
}

void yn(bool tf) { print(tf ? "Yes" : "No"); }
void YN(bool tf) { print(tf ? "YES" : "NO"); }

template <typename T>
void init(vector<T>& v) {
    rep (i, v.size())
        cin >> v[i];
}

template <typename T, typename U>
void init(vector<T>& v, vector<U>& w) {
    assert(v.size() == w.size());
    rep (i, v.size())
        cin >> v[i] >> w[i];
}

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

// -------------------------------------------------------------------
// sort 1 2 3 4

signed main() {
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(false);
    char c;
    cin >> c;
    switch (c) {
        case 'A':
            print('T');
            break;
        case 'T':
            print('A');
            break;
        case 'G':
            print('C');
            break;
        case 'C':
            print('G');
            break;
    }

    return 0;
}


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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; ++i){
        cin >> h[i];
    }
    vector<int> dp(n);
    dp[1] = abs(h[1] - h[0]);
    for(int i = 2; i < n; ++i){
        dp[i] = min(dp[i-2] + abs(h[i-2] - h[i]),dp[i-1] + abs(h[i-1] - h [i]));
    }

    cout << dp[n-1] << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for (ll i = 0; i < (n); ++i)
#define RREP(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define ALL(v) (v).begin(), (v).end()

struct mint{
    static const long long MOD = 1000000007;

    long long v;

    mint() : v(0) {}
    mint(long long x){
        x = x % MOD;
        if(x < 0){ x += MOD; }
        v = x;
    }
    mint& operator+=(mint a){
        v += a.v;
        if(v >= MOD){ v -= MOD; }
        return *this;
    }
    mint& operator*=(mint a){
        v *= a.v;
        v %= MOD;
        return *this;
    }
    mint& operator-=(mint a){
        v -= a.v;
        if(v < 0){ v += MOD; }
        return *this;
    }
    mint& operator/=(mint a){
        return (*this) *= a.inv();
    }

    mint operator*(mint a) const{
        return mint(v) *= a;
    }

    mint operator+(mint a) const {
        return mint(v) += a;
    }

    mint operator-(mint a) const {
        return mint(v) -= a;
    }

    mint operator/(mint a) const {
        return mint(v) /= a;
    }

    mint pow(long long k) const {
        mint res(1),tmp(v);
        while(k){
            if(k&1) res *= tmp;
            tmp *= tmp;
            k >>= 1;
        }
        return res;
    }
    mint inv(){return pow(MOD - 2); }

    static mint comb(long long n, int k){
        mint res(1);
        for(int i = 0; i < k; ++i){
            res *= mint(n - i);
            res /= mint(i + 1);
        }
        return res;
    }

    static mint factorial(long long n){
        mint res(1);
        for(int i = n; i > 1; --i){
            res *= mint(i);
        }
        return res;
    }

    bool operator<(const mint &a) const {
        return v < a.v;
    };
};

mint operator*(long long l, mint r){ return r * l; }

std::ostream& operator<<(std::ostream& stream, const mint& m){
    stream << m.v;
    return stream;
}


int main(){
    ll n, m;
    cin >> n >> m;
    vector<ll> nr(n * m, 0), nc(n * m, 0);
    REP(i, n){
        ll ai;
        cin >> ai;
        nr.at(ai - 1)++;
        if(nr.at(ai - 1) > 1){
            cout << 0 << endl;
            return 0;
        }
    }
    REP(i, m){
        ll bi;
        cin >> bi;
        nc.at(bi - 1)++;
        if(nc.at(bi - 1) > 1){
            cout << 0 << endl;
            return 0;
        }
    }

    ll cnr = 0, cnc = 0;
    mint ans = 1;
    RREP(i, n * m){
        cnr += nr.at(i);
        cnc += nc.at(i);
        if(nr.at(i) && nc.at(i)){
            // ans *= 1;
        }else if(nr.at(i)){
            ans *= cnc;
        }else if(nc.at(i)){
            ans *= cnr;
        }else{
            const ll ncell = cnr * cnc;
            const ll nused = n * m - i - 1;
            ans *= (ncell - nused);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 18840
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main(void) {

    string S; cin >> S;
    ll K; cin >> K;
    set<char> S_set;

    ll S_duplication = 0;
    for (int i = 0; i < S.size()-1; ++i) {
        if(S[i]==S[i+1]){
            S_duplication++; i++;
        }
    }
    for (int i = 0; i < S.size(); ++i) {
        S_set.insert(S[i]);
    }

    if(S_set.size() == 1){
        cout<<(S.size()*K)/2<<endl;
    } else if(S[0]!=S[S.size()-1]){

        cout<<S_duplication*K<<endl;

    } else{
        ll a=0;
        for (int i = 0; i < S.size(); ++i) {
            if(S[0]!=S[i]) {break;}
            a++;
        }
        ll b=0;
        for (int i = S.size()-1; i > a; --i) {
            if(S[0]!=S[i]){break;}
            b++;
        }

        ll ans = S_duplication*K - ((a/2+b/2)-(a+b)/2)*(K-1);
        cout<<ans<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

int x[100000], y[100000];
set<pair<ll, int>> STX[100000], STY[100000];
vector<ll> VX2[100000], VY2[100000];
bool A[100000];
ll kotae;
ll D;
vector<int> VX, VY;
void sagasu(int a) {
	if (A[a]) return;
	A[a] = true;
	ll X = x[a] + y[a];
	ll Y = x[a] - y[a];
	int l = lower_bound(VX.begin(), VX.end(), X - D) - VX.begin();
	int r = upper_bound(VX.begin(), VX.end(), X - D) - VX.begin();
	vector<int> V;
	if (l != r) {
		auto itr = STX[l].lower_bound(mp(Y - D, 0));
		while (itr != STX[l].end() && (*itr).first <= Y + D) {
			V.pb((*itr).second);
			STX[l].erase(itr++);
		}
		int K = lower_bound(VX2[l].begin(), VX2[l].end(), Y + D) - lower_bound(VX2[l].begin(), VX2[l].end(), Y - D);
		kotae += K;
	}
	l = lower_bound(VX.begin(), VX.end(), X + D) - VX.begin();
	r = upper_bound(VX.begin(), VX.end(), X + D) - VX.begin();
	if (l != r) {
		auto itr = STX[l].lower_bound(mp(Y - D, 0));
		while (itr != STX[l].end() && (*itr).first <= Y + D) {
			V.pb((*itr).second);
			STX[l].erase(itr++);
		}
		int K = upper_bound(VX2[l].begin(), VX2[l].end(), Y + D) - upper_bound(VX2[l].begin(), VX2[l].end(), Y - D);
		kotae += K;
	}
	l = lower_bound(VY.begin(), VY.end(), Y - D) - VY.begin();
	r = upper_bound(VY.begin(), VY.end(), Y - D) - VY.begin();
	if (l != r) {
		auto itr = STY[l].lower_bound(mp(X - D, 0));
		while (itr != STY[l].end() && (*itr).first <= X + D) {
			V.pb((*itr).second);
			STY[l].erase(itr++);
		}
		int K = upper_bound(VY2[l].begin(), VY2[l].end(), X + D) - upper_bound(VY2[l].begin(), VY2[l].end(), X - D);
		kotae += K;
	}
	l = lower_bound(VY.begin(), VY.end(), Y + D) - VY.begin();
	r = upper_bound(VY.begin(), VY.end(), Y + D) - VY.begin();
	if (l != r) {
		auto itr = STY[l].lower_bound(mp(X - D, 0));
		while (itr != STY[l].end() && (*itr).first <= X + D) {
			V.pb((*itr).second);
			STY[l].erase(itr++);
		}
		int K = lower_bound(VY2[l].begin(), VY2[l].end(), X + D) - lower_bound(VY2[l].begin(), VY2[l].end(), X - D);
		kotae += K;
	}
	for (auto p : V) {
		sagasu(p);
	}
}

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


	int N, a, b;
	cin >> N >> a >> b;
	a--;
	b--;
	rep(i, N) cin >> x[i] >> y[i];
	D = (ll)abs(x[a] - x[b]) + (ll)abs(y[a] - y[b]);
	rep(i, N) {
		VX.pb(x[i] + y[i]);
		VY.pb(x[i] - y[i]);
	}
	sort(VX.begin(), VX.end());
	sort(VY.begin(), VY.end());
	
	rep(i, N) {
		int xi = lower_bound(VX.begin(), VX.end(), x[i] + y[i]) - VX.begin();
		STX[xi].insert(mp(x[i] - y[i], i));
		VX2[xi].pb(x[i] - y[i]);
		int yi = lower_bound(VY.begin(), VY.end(), x[i] - y[i]) - VY.begin();
		STY[yi].insert(mp(x[i] + y[i], i));
		VY2[yi].pb(x[i] + y[i]);
	}
	rep(i, 100000) {
		sort(VX2[i].begin(), VX2[i].end());
		sort(VY2[i].begin(), VY2[i].end());
	}

	sagasu(a);

	co(kotae / 2);


	Would you please return 0;
}

Measured memory_bytes: 40436
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer token = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(token.nextToken());
		int M = Integer.parseInt(token.nextToken());
		int[][] arr = new int[M][4];
		for(int i=0;i<M;i++) {
			token = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(token.nextToken());
			arr[i][1] = Integer.parseInt(token.nextToken());
			arr[i][2] = i;
		}
		
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
			
		});
		int[] arrC = new int[N+1];

		for(int i=0;i<M;i++) {
			arr[i][3] = ++arrC[arr[i][0]];
		}
		
		Arrays.sort(arr, new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[2] - o2[2];
			}
			
		});
		
		for(int i=0;i<M;i++) {
			System.out.println(leftPad(arr[i][0]) + leftPad(arr[i][3]));
		}
	}
	
	private static String leftPad(int num) {
		if(num > 99999) return ""+num;
		else if(num > 9999) return "0"+num;
		else if(num > 999) return "00"+num;
		else if(num > 99) return "000"+num;
		else if(num > 9) return "0000"+num;
		else if(num > 0) return "00000"+num;
		return "";
	}
}

Measured memory_bytes: 77876
#include <iostream>
#include <string>

using namespace std;

int main(){
    
    int H, W;
    cin >> H >> W;

    string S[H][W];

    int a, b;
    for (int i = 0; i < H; i++){
        for (int j = 0; j < W; j++){
            cin >> S[i][j];
            if (S[i][j] == "snuke"){
                a = i;
                b = j;
            }
        }
    }
    
    char B = b + 'A';
    cout << B << a + 1 << endl;

    return 0;
}

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

int main(){
    int h, w, k;
    long long dp[105][10], a[10][3], pr[10];
    scanf("%d%d%d", &h, &w, &k);
    fill(dp[0], dp[105], 0);
    dp[0][1] = 1;
    pr[0] = 1;
    for(int i = 1; i <= w; i++){
        pr[i] = 0;
        for(int j = 0; (j-1)*2 < i; j++){
            long long l = 1;
            for(int m = 1; m <= j; m++) l = l*(i-j+2-m)/m;
            pr[i] = (pr[i] + l) % md;
        }
    }
    for(int i = 1; i <= w; i++){
        a[i][0] = (i-3 >= 0 ? pr[i-3] : 1)*(w-i-1 >= 0 ? pr[w-i-1] : 1)%md;
        a[i][2] = (i-2 >= 0 ? pr[i-2] : 1)*(w-i-2 >= 0 ? pr[w-i-2] : 1)%md;
        a[i][1] = (i-2 >= 0 ? pr[i-2] : 1)*(w-i-1 >= 0 ? pr[w-i-1] : 1)%md;
    }
    for(int i = 1; i <= h; i++){
        for(int j = 1; j <= w; j++){
            for(int l = 0; l < 3; l++){
                if((j == 1 && l == 0) || (j == w && l == 2)) continue;
                dp[i][j] = (dp[i][j] + dp[i-1][j+l-1]*a[j][l])%md;
            }
        }
    }
    printf("%lld\n", dp[h][k]);
}


Measured memory_bytes: 256
#==========================================================
def General_Binary_Search(L,R,cond,Mode=True,Integer=True,ep=1/(1<<20)):
    """一般的な二部探索を行う.
    L:解の下限
    R:解の上限
    cond:条件(1変数関数,広義単調減少 or 広義単調減少を満たす)
    Mode:True->広義単調増加,False->広義単調減少
    Integer:解を整数に制限するか?
    ep:Integer=Falseのとき,解の許容する誤差
    """

    if Integer:
        if Mode:
            if not cond(R):
                return R+1
            L-=1
        else:
            if not cond(L):
                return L-1
            R+=1

        while R-L>1:
            C=L+(R-L)//2
            if cond(C)^Mode:
                L=C
            else:
                R=C
        if Mode:
            return R
        else:
            return L
    else:
        C=L+(R-L)/2
        while (R-C)>ep:
            if cond(C)^Mode:
                L=C
            else:
                R=C
            C=L+(R-L)/2
        return C
#==========================================================
def g(x):
    S=A[x]
    for i in range(N):
        if i!=x:
            if A[i]<=2*S:
                S+=A[i]
            else:
                return False
    return True
#==========================================================
N=int(input())
A=list(map(int,input().split()))

A.sort()
print(N-General_Binary_Search(0,N-1,g,True))

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

using namespace std;

const int N = (int)1e5+5;
int n, m, a[N], b[N];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
for (int i = 1; i <= n; ++i) if (m == 0 || b[m] != a[i]) b[++m] = a[i];
if (m == 1) { puts("1"); return 0; }
int mode = (b[1] < b[2] ? 1 : -1), res = 0;
for (int i = 1; i < m; ++i) {
if ((mode == 1 && b[i] < b[i + 1]) || (mode == -1 && b[i] > b[i + 1])) continue;
++res;
if (i + 1 < m) mode = (b[i + 1] < b[i + 2] ? 1 : -1);
}
printf("%d", res+1);
return 0;
}

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

tmp = 0
for i in range(N//2):
  tmp += A[2*i+1]
  
ans = []
if sum(A) > 2*tmp:
  ans.append(sum(A)-2*tmp)
else:
  ans.append(0)
  
for i in range(N-1):
  ans.append(2*A[i]-ans[-1])
print(*ans)


Measured memory_bytes: 20456
ls = []
r,c = map(int,input().split())
for i in range(0, r):
    ls.append(list(map(int,input().split())))
ls.append([])
for j in range(0, r):
    ls[j].append(sum(ls[j]))

for j in range(0, c+1):
    num = 0
    for k in range(0, r):
        num += ls[k][j]
    ls[r].append(num)
for z in range(0, r+1):
    print(*ls[z])

Measured memory_bytes: 8272
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<vector>
#include<string>
#include<bitset>
#include<queue>
#include<set>
#include<map>
using namespace std;
 
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define ROF(i,b,a) for (int i=(b);i>(a);--i)
#define REP(i,n) FOR(i,0,n)
#define PER(i,n) ROF(i,n-1,-1)
 
typedef int i32;
typedef long long int i64;
typedef unsigned long long int ui64;
typedef float f32;
typedef double f64;
typedef long double f128;
typedef pair<int,int> Pi;
 
constexpr int INF = 1e9 + 7;
constexpr int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
 
int main() {
    int N; cin>>N;
    int p[N]; REP(i,N) cin>>p[i];
    sort(p,p+N);
    p[N-1] /= 2;
    int sum = 0;
    REP(i,N) sum += p[i];
    cout << sum << endl;
}

Measured memory_bytes: 256
#読み込み部
N, u, v = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N-1)]

#グラフ作成部
graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)

#深さ優先探索
def dfs(v):
    dist = [-1] * (N+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist

DU,DV = dfs(u),dfs(v)
 
answer = 0
for u,v in zip(DU[1:],DV[1:]):
    if u < v:
        x = v - 1
        if answer < x:
            answer = x

print(answer)

Measured memory_bytes: 43508