akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
  
#define int long long 
#define pb push_back
#define S second
#define F first
#define f(i,n) for(int i=0;i<n;i++)
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define vi vector<int>
#define pii pair<int,int>

const int N = 3e5 + 10;
vi row[N];
vi col[N];

void solve()
{
    int n,m,k;
    cin >> n >> m >> k;
    
    pii a[k];
    f(i,k) cin >> a[i].F >> a[i].S;
    
    f(i,k) row[a[i].F].pb(a[i].S);
    f(i,k) col[a[i].S].pb(a[i].F);
    
    int res = 0;
    
    f(i,k) res = max(res, (int)row[a[i].F].size() + (int)col[a[i].S].size() - 1);
    
    int mxr = 0;
    int mxc = 0;
    
    f(i,k) mxr = max(mxr, (int)row[a[i].F].size());
    f(i,k) mxc = max(mxc, (int)col[a[i].S].size());
    
    set<int> gor,goc;
    
    f(i,k) if((int)row[a[i].F].size() == mxr) gor.insert(a[i].F);
    f(i,k) if((int)col[a[i].S].size() == mxc) goc.insert(a[i].S);
    
    int ss = ((int)gor.size())*((int)goc.size());    
        
    if(ss > k) 
        res = max(res, mxr + mxc);
    else //very less pairs remove one by one
    {
        set<pair<int,int> > pp;
        
        for(auto x : gor)
            for(auto y : goc) pp.insert({x,y});
        
        f(i,k) if(pp.find(a[i]) != pp.end()) pp.erase(a[i]);
            
        if((int)pp.size() > 0) res = max(res , mxr + mxc);
        else res = max(res, mxr + mxc - 1);
    }
    
    cout << res;
}

signed main()
{
    fast;
    
    int t = 1;
    
//    cin >> t;
    
    while(t--)
        
    solve();
}

Measured memory_bytes: 69216
import java.util.*;
import java.io.*;
class Main{
  public static void main(String args[]){
    int a = readI(),b = readI(),h=readI(),m=readI();
    h = 60*h+m;
    double rada = 0.5*h,radb = m*6.0;
    double rad = Math.abs(rada-radb);
    if(rad>180){rad=360-rad;}
    rad = rad*2*Math.PI/360;
    double k = Math.sqrt(a*a+b*b-2*a*b*Math.cos(rad));
    pl(k+"");
  }

  public static long search(int now,int n,int m,int x,long nowm,int[]rikai,int money[],int[][]book,long min){
    boolean flg=true;
    nowm+=money[now];
    for(int i=0;i<m;i++){
      rikai[i]+=book[now][i];
      if(rikai[i]<x){
        flg=false;
      }
    }
    if(flg){
      if(min==-1||min>nowm){
        min = nowm;
      }
    }else{
      for(int i=now+1;i<n;i++){
        min = search(i,n,m,x,nowm,rikai,money,book,min);
      }
    }
    for(int i=0;i<m;i++){
      rikai[i]-=book[now][i];
    }
    nowm-=money[now];
    if(now!=n-1){
      min = search(now+1,n,m,x,nowm,rikai,money,book,min);
    }
    return min;
  }

  static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  public static void pr(String str){
    System.out.print(str);
  }
  public static void pl(String str){
    System.out.println(str);
  }
  public static String readL(){
    try{
      return br.readLine();
    }catch(IOException e){
      e.printStackTrace();
      return "";
    }
  }
  public static String readS(){
    StringBuilder sb = new StringBuilder();
    while(true){
      try{
        int k = br.read();
        if(k==-1||(char)k==' '||(char)k=='\n'){break;}
        sb.append((char)k);
      }catch(IOException e){
        e.printStackTrace();
      }
    }
    return sb.toString();
  }
  public static int readI(){
    return stoi(readS());
  }
  public static String[] readSs(){
    return readL().split(" ");
  }
  public static int[] readIs(){
    return stoi(readSs());
  }
  public static int stoi(String s){
    return Integer.parseInt(s);
  }
  public static int[] stoi(String s[]){
    int a[]=new int[s.length];
    for(int i=0;i<s.length;i++){
      a[i]=stoi(s[i]);
    }
    return a;
  }
  public static String itos(int i){
    return String.valueOf(i);
  }
  public static String[] itos(int[] a){
    String s[]=new String[a.length];
    for(int i=0;i<a.length;i++){
      s[i]=itos(a[i]);
    }
    return s;
  }
  public static String ctos(char c){
    return String.valueOf(c);
  }
  public static String cstos(char[] c){
    return new String(c);
  }
  public static char stoc(String s){
    return s.charAt(0);
  }
  public static char[] stocs(String s){
    return s.toCharArray();
  }
}


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


int main() {
  int n, k;
  cin >> n >> k;
  int a[n];
  rep(i, n) cin >> a[i];
  vector<int> num(n);
  rep(i, n) num[a[i]-1]++;
  sort(num.begin(), num.end(), greater<int>());
  int cnt = 0;
  for(int i = k; i < n; i++){
    if(num[i]) cnt += num[i];
    else break;
  }
  cout << cnt << endl;
}
 

Measured memory_bytes: 1792
def solve(x, y)
  100.times {|i|
    if (x >> i) & 1 != (y >> i) & 1
      return i + 1
    end
  }
end
n = gets.to_i
(n-1).times{|x|
  puts (x+1...n).map{|y| solve(x, y).to_s} * ' '
}


Measured memory_bytes: 2428
def main():
    N = input()
    lenN = len(N)
    listN = list(N)
    N2 = [int(i) for i in listN]
    bf = sum(N2)
    ans = 0
    for i, s in enumerate(N):            
        if s == '9':
           ans += 9
        else:
            if i == 0:
                ans += int(s)-1 + 9*(lenN - i - 1)
                break
            else:
                ans += 9*(lenN - i) - 1
                break
    ans = max(ans, bf)
    print(ans)

if __name__ == "__main__":
    main()


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

#define dump(x) cout << (x) << '\n'
#define Int int64_t
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
 
Int INF = 1e18;
int inf = 1e9;
Int mod = 1e9+7;

int main() {
    Int n;
    cin >> n;
    vector<Int> a(n);
    for (Int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<Int> b(n + 1, 0);
    for (Int i = 0; i < n; i++) {
        b[i + 1] = b[i] + a[i];
    }
    Int l = 1, m = 2, r = 3;
    Int res = max({b[n] - b[3], b[3] - b[2], b[2] - b[1], b[1] - b[0]}) - min({b[n] - b[3], b[3] - b[2], b[2] - b[1], b[1] - b[0]});
    while (r < n) {
        //cout << l << " " << m << " " << r << endl;
        Int mi = abs((b[l] - b[0]) - (b[m] - b[l]));
        while (l + 1 < m and abs((b[l + 1] - b[0]) - (b[m] - b[l + 1])) < mi) {
            mi = abs((b[l + 1] - b[0]) - (b[m] - b[l + 1]));
            l++;
        }
        mi = abs((b[n] - b[r]) - (b[r] - b[m]));
        while (r + 1 < n and abs((b[n] - b[r + 1]) - (b[r + 1] - b[m])) < mi) {
            mi = abs((b[n] - b[r + 1]) - (b[r + 1] - b[m]));
            r++;
        }
        Int ma = max({b[n] - b[r], b[r] - b[m], b[m] - b[l], b[l] - b[0]});
        mi = min({b[n] - b[r], b[r] - b[m], b[m] - b[l], b[l] - b[0]});
        res = min(res, ma - mi);
        m++;
        if (r == m) {
            r = m + 1;
        }
    }
    dump(res);
    return 0;
}

Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,m;
	while(cin>>n>>m)
	{
		set<int> k;
		int num;
		string s;
		map<int,int> mp;
		int penalty=0;
		for(int i=0;i<m;i++)
		{
			cin>>num>>s;
			if(s=="AC") k.insert(num);
			else
			{
				if(k.find(num)==k.end())mp[num]++;
			}
		}
		for(auto i=mp.begin();i!=mp.end();++i)
		{
			if(k.find(i->first)!=k.end()) penalty+=i->second;
		}
		cout<<k.size()<<" "<<penalty<<"\n";
	}
}

Measured memory_bytes: 4992
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    int N;
    cin >> N;
    vector<int> H(N);
    for (int& x : H) cin >> x;

    int last = 0;
    for (int x : H) {
        if (x - 1 >= last) {
            last = x - 1;
        }
        else if (x >= last) {
            last = x;
        }
        else {
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


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

long long n,a[2][105],dp[2][105];

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

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

    dp[0][0]=a[0][0];
    dp[1][0]=a[0][0]+a[1][0];

    for(int i=1;i<n;i++)
        dp[0][i]=dp[0][i-1]+a[0][i];

    for(int i=1;i<n;i++)
        dp[1][i]=max(dp[1][i-1]+a[1][i],dp[0][i]+a[1][i]);

    cout<<dp[1][n-1]<<endl;

    return 0;
}


Measured memory_bytes: 3660
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        while(true){
            int m = scan.nextInt();
            int f = scan.nextInt();
            int r = scan.nextInt();

            if(m == -1 && f == -1 && r == -1){
                break;
            }

            if(m == -1 || f == -1){
                System.out.println("F");
            }else if((m+f) >= 80){
                System.out.println("A");
            }else if((m+f) >= 65){
                System.out.println("B");
            }else if((m+f) >= 50){
                System.out.println("C");
            }else if((m+f) >= 30 && r >= 50){
                System.out.println("C");
            }else if((m+f) >= 30){
                System.out.println("D");
            }else{
                System.out.println("F");
            }
        }
    }
}



Measured memory_bytes: 26356
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using Edge = pair<int, ll>;
using Graph = vector<vector<int>>;
using WeightedGraph = vector<vector<Edge>>;
const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;
const ll MOD = 1000000007;

const int CASES = 4;

ll n;
vector<char> buf;
void rec(int idx, int num){
    if(idx == n){
        for(int i = 0; i < n; ++i){
            cout << buf[i];
        }
        cout << endl;
    }
    else{
        for(int i = 0; i <= num; ++i){
            char c = i + 'a';
            buf[idx] = c;
            bool f = true;
            int cnt = num;
            if(i==num)++cnt;
            rec(idx+1, cnt);
        }
    }
}

void solve() {
    cin >> n;
    buf.resize(n);
    rec(0, 0);
}

int main() {
#ifdef MYLOCAL
    vector<string> filenames {"input1.txt", "input2.txt", "input3.txt", "input4.txt", "input5.txt"};
    cout << "------------\n";
    for(int i = 0; i < CASES; ++i){
        ifstream in(filenames[i]);
        cin.rdbuf(in.rdbuf());
        solve();
        cout << "------------\n";
    }
#else

    solve();

#endif
    return 0;
}


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

int main(){
    string s;
    cin >> s;
    int n=s.size();
    vi a(n+1);
    int ten=1;
    for(int i=n-1;i>=0;i--){
        int kani=s[i]-'0';
        a[i]=kani*ten%2019;
        ten=ten*10%2019;
    }
    for(int i=n-1;i>0;i--){
        a[i-1]=(a[i-1]+a[i])%2019;
    }
    map<int,int> mp;
    for(int i=0;i<=n;i++){
        mp[a[i]]++;
    }
    int ans=0;
    for(auto x:mp){
        //cout << x.first << " " << x.second << endl;
        ans+=x.second*(x.second-1)/2;
    }
    cout << ans << endl;

}

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

using namespace std;
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef long long ll; typedef vector<int> VI; typedef pair<int,int> pii;
const int mod = (int)1e9 + 7;
void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2> void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }

	
int main()
{
	//cin.tie(0); ios_base::sync_with_stdio(false);
	int q;
	cin >>q;
	rep(zz, q){
		ll a,b;
		cin >>a >>b;
		if(a>b) swap(a,b);
		
		if(a==b){
			cout << 2*(a-1) <<"\n"; continue;
		}
		if(a+1 == b){
			cout << 2*a -2 <<"\n"; continue;
		}
		ll c = (ll)sqrt(a*b);
		if(c*c == a*b) c--;
		
		if(c*(c+1) >= a*b){
			cout << 2*c -2 <<"\n"; continue;
		}
		cout << 2*c -1 <<"\n";
	
	}
	
	
	
	return 0;
	
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.HashSet;
import java.util.stream.IntStream;
import java.util.Comparator;


public class Main {

	static int M;
	static int[] ss;
	static int[] sum2;

	static int max(int low, int high, int sumMax) {
		int mid = (low + high) / 2;
		if(sum2[mid] < sumMax) {
			if(low == mid) {
				return sum2[mid];
			}
			if(mid < high && !(sum2[mid+1] < sumMax) ) {
				return sum2[mid];
			}
			return max(mid, high, sumMax);
		}
		return max(low, mid, sumMax);
	}

	static int serach() {
		HashSet<Integer> pairs = new HashSet<>();
		for(int i = 0; i < ss.length; i++) {
			for(int j = 0; j < ss.length; j++) {
				pairs.add(ss[i]+ss[j]);
			}
		}
		sum2 = new int[pairs.size()];
		int c = 0;
		for(Integer n: pairs) {
			sum2[c++] = n;
		}
		Arrays.sort(sum2);
		int max = 0;
		for(int i = sum2.length-1; i >= 0; i--) {
			int m = M - sum2[i];
			if(m == 0) return M;
			if(m > 0) {
				max = Math.max(max, max(0, i, m) + sum2[i]);
				if(sum2[i] * 2 < max) {
					break;
				}
			}
		}
		return max;
	}

	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)){
			for(;;) {
				int N = sc.nextInt();
				M = sc.nextInt();
				if((M | N) == 0) break;
				ss = new int[N+1];
				for(int i = 0; i < N; i++) {
					ss[i] = sc.nextInt();
				}
				System.out.println(serach());
			}
		}
	}
}
	


Measured memory_bytes: 156932
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define fi first
#define se second
#define rep(i,n) for(int i=0;i<(n);i++)
int main(){
	ll a,b,c; cin>>a>>b>>c;
	if(a==b and b==c) cout<<1;
	else if(a==b or b==c or a==c) cout<<2;
	else cout<<3;
}


Measured memory_bytes: 3612
#include<iostream>
#include<cmath>
#include<iomanip>
#include<string>
#include<vector>
#include<stack>
#include<cstdlib>
#include<queue>
#include<list>
using namespace std;

int main(){
    int x, a, b;
    cin>>x>>a>>b;
    if(a-b>=0)cout<<"delicious"<<endl;
    else if(b-a<=x)cout<<"safe"<<endl;
    else cout<<"dangerous"<<endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std;

const int MAX_N=100001;


int main(){

	double ret[MAX_N];
	fill(ret,ret+MAX_N,0.0);

	// iツ嘉アツ姪堋づ泳ツ古つ連ツ堕アツつオツづ偲ヲツづェツづゥツ確ツ猟ヲツづーツ格ツ納
	vector<vector<double> > dp;
	vector<double> v(51,0.0);
	for(int i = 0; i < MAX_N; i++){
		dp.push_back(v);
	}
	//double dp[MAX_N][51];
	//for(int i = 0; i < MAX_N; i++)
	//	fill(dp[i],dp[i]+51,0.0);
	dp[1][1]=1.0;
	ret[1]=1.0;
	for(int i = 2; i < MAX_N; i++){
		double ss=0;
		// iツ嘉アツ姪堋づ泳ツ古つ連ツ堕アツつオツづ偲ヲツづェツづゥツ確ツ猟ヲツづーツ計ツ算
		for(int j = 0; j <= min(i,50); j++){
			// ツ債。ツ嘉アツミツス
			if(j==0){
				for(int k = 1; k <= min(i-1,50); k++){
					dp[i][j]+=dp[i-1][k]*(1-pow(0.5,k));
				}
			}
			// ツ連ツ堕アツ偲ヲツ督セ
			else{
				dp[i][j]=dp[i-1][j-1]*(pow(0.5,j-1));
				ss+=dp[i][j];
			}
		}
		ret[i]=ss+ret[i-1];
	}

	int n;
	while(cin>>n&&n!=0){
		//cout<<ret[n]<<endl;
		printf("%.3lf\n",ret[n]);
	}

	return 0;
}

Measured memory_bytes: 0
import numpy as np
import math

n,d=list(map(int, input().split()))
x = []
for i in range(n):
    x.append(list(map(int, input().split())))
xn =np.asarray(x)
cnt = 0
for i in range(n):
    for j in range(i+1,n):
        t = xn[i,:] - xn[j,:]
        t2 = np.square(t)
        t3 = np.sum(t2)
        if (np.sqrt(t3)).is_integer():
            cnt += 1
            
print(cnt)

Measured memory_bytes: 21760
N,Y=map(int,input().split(" "))
Y //= 1000

for i in range(N+1):
    j = N - i
    y = Y - 10 * i
    y -= j
    if y < 0:
        continue
    if y % 4 == 0 and y // 4 <= j:
        print(" ".join(map(str,[i,y//4,j-y//4])))
        exit()

print("-1 -1 -1")

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
int main() {
  int n, m, k, b, sum = 0;
  cin >> n >> m;
  vector<bitset<10>> a(m);
  vector<int> c(m);
  rep(i,m) {
    cin >> k;
    bitset<10> bs;
    rep(j,k) {
      cin >> b;
      bs.set(b-1);
    }
    a[i] = bs;
  }
  rep(i,m)
  {
    cin >> c[i];
  }
  rep(b,(1 << n)) {
    bitset<10> bit(b);
    rep(i,m)
      if (c[i] != (int) (a[i] & bit).count() % 2) {
        sum--;
        break;
      }
    sum++;
  }
  cout << sum;
}

Measured memory_bytes: 256
#pragma GCC optimize ("-O3")
    #include <bits/stdc++.h>  
     
    using namespace std;
     
    typedef long long ll;
    typedef long double ld;
    typedef pair<int,int> p32;
    typedef pair<ll,ll> p64;
    typedef pair<double,double> pdd;
    typedef vector<ll> v64;
    typedef vector<int> v32;
    typedef vector<vector<int> > vv32;
    typedef vector<vector<ll> > vv64;
    typedef vector<vector<p64> > vvp64;
    typedef vector<p64> vp64;
    typedef vector<p32> vp32;
    ll MOD = 998244353;
    #define forn(i,e) for(ll i = 0; i < e; i++)
    #define forsn(i,s,e) for(int i = s; i < e; i++)
    #define rforn(i,s) for(ll i = s; i >= 0; i--)
    #define rforsn(i,s,e) for(ll i = s; i >= e; i--)
    #define ln "\n"
    #define dbg(x) cout<<#x<<" = "<<x<<ln
    #define mp make_pair
    #define pb push_back
    #define fi first
    #define se second
    #define INF 1e18
    #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
    #define all(x) (x).begin(), (x).end()
    #define sz(x) ((ll)(x).size())
     
    ll mpow(ll a, ll b){
        if(b >= (MOD-1)) b %= (MOD-1);
        if(b==0) return 1;
        ll t1 = mpow(a,b/2);
        t1 *= t1;
        t1 %= MOD;
        if(b%2) t1 *= a;
        t1 %= MOD;
        return t1;
    }
     
    ll mpow(ll a, ll b, ll p){
        if(b==0) return 1;
        ll t1 = mpow(a,b/2,p);   t1 *= t1;
        t1 %= p;
        if(b%2) t1 *= a;
        t1 %= p;
        return t1;
    }
    ll modinverse(ll a, ll m){
        ll m0 = m; 
        ll y = 0, x = 1; 
        if (m == 1) return 0; 
        while (a > 1){
            ll q = a / m; 
            ll t = m; 
            m = a % m, a = t; 
            t = y; 
            y = x - q * y; 
            x = t; 
        }
        if (x < 0) x += m0; 
        return x; 
    }
    ll range(ll l, ll r){
        return l + rand()%(r-l+1);
    }
    
    ll n,k;
    ll N = 2e5 + 10;
    vector<ll>arr(N);
    
    bool check(ll no)
    {
        ll req = 0;
        for(ll i=0;i<n;i++)
        {
            if(no<arr[i])
            {
                req += (arr[i]/no);

                if(arr[i]/no==no && arr[i]%no != 0)req++;
            }
            
        }
        //cout<<no<<" "<<req<<endl;
        if(req<=k)return false;
        return true;
    }

    int main()
    {
        ll t=1;
        
        while(t--)
        {
            cin>>n>>k;
            for(ll i=0;i<n;i++)
            {
                cin>>arr[i];
            }
            
            ll r = 1e9 + 5;
            ll l = 0;

            while((r-l) > 1)
            {
                ll mid = (l+r)/2;
                if(check(mid))l=mid;
                else r = mid;
            }
            cout<<r<<endl;
        }
    }

Measured memory_bytes: 4676
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

int main(){
  int n,k;
  cin>>n>>k;

  ll ans=0;
  ans+=pow(n/k,3);
  if(k%2==0){
    ans+=pow((n+(k/2))/k,3);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdlib>

using namespace std;

int mem[1<<22];

int rec(int b,int *f,int *l){
  if(l-f==1){
    return 0;
  }else if(mem[b]>=0){
    return mem[b];
  }else{
    int m=99;
    for(int i=0;i<11;i++){
      if(!(b>>i*2&1)){
	auto it=partition(f,l,[&](int x){
	    return x>>i&1;
	  });
	if(it!=f&&it!=l){
	  m=min(m,1+max(rec(b|3<<i*2,f,it),rec(b|1<<i*2,it,l)));
	}
      }
    }
    return mem[b]=m;
  }
}

int main(){
  for(int n,m;cin>>m>>n,m;){
    int b[128];
    for(int i=0;i<n;i++){
      char s[12];
      cin>>s;
      b[i]=strtol(s,nullptr,2);
    }
    fill(begin(mem),end(mem),-1);
    cout<<rec(0,b,b+n)<<endl;
  }
}

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

int g[101],p[101],c;
int dp[100001];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++)
        cin>>p[i]>>g[i];
    for(int i=1; i<=100000; i++)
        dp[i]=m+1;
    for(int i=1; i<=n; i++)
        for(int j=100000; j>=g[i]; j--){
            dp[j]=min(dp[j],dp[j-g[i]]+p[i]);
            dp[j]=min(dp[j],m+1);
        }

    for(int j = 100000; j >= 0; j--)
        if(dp[j] <= m){
            cout << j;
            return 0;
        }

    return 0;
}


Measured memory_bytes: 640
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		final int A = in.nextInt();
		final int B = in.nextInt();
		final int C = in.nextInt();
		final int D = in.nextInt();
		final double T = (double) C / B;
		final double O = (double) A  / D;
		System.out.println((Math.ceil(T) <= Math.ceil(O)) ? "Yes" : "No");
	}
}

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

#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999

using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;

int iy[]={0, 0, 1, -1};
int ix[]={1, -1, 0, 0};

int a, b, c, d, f;
int w[32],s[3002];
double ma, e;
int g, m;
int main(){
	cin >> a >> b >> c >> d >> e >> f;
	w[0]++;
	s[0]++;
	for(int i=0;i<=30;i++){
		if(w[i]==1){
			for(int j=1;j<=30;j++){
				if(i+a*j<31) w[i+a*j]=1;
				if(i+b*j<31) w[i+b*j]=1;
			}
		}
	}
	for(int i=0;i<=3000;i++){
		if(s[i]==1){
			for(int j=1;j<=3000;j++){
				if(i+c*j<=f) s[i+c*j]=1;
				if(i+d*j<=f) s[i+d*j]=1;			
			}
		}
	}
	for(int i=1;i<=30;i++){
		for(int j=0;j<=3000;j++){
			if(w[i]==0||s[j]==0) continue;
			if(i*100+j>f) continue;
			if(ma < double(j)/(double(i)*100+double(j)) && double(e) >= double(j)/double(i)){
				ma = double(j)/(double(i)*100+double(j));
				g=i*100;
				m=j;
			}
		}
	}
	if(g==0&&m==0) g=a*100;
	cout << g+m << " " << m << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
int main() {
  int n, x = 0, sum = 0;
  cin >> n;
  int a[n + 1];
  rep(i,n)
  {
    cin >> a[i];
    sum += abs(x - a[i]);
    x = a[i];
  }
  a[n] = 0;
  sum += abs(x);
  x = 0;
  rep(i,n)
  {
    cout << (sum - (abs(x - a[i]) + abs(a[i] - a[i + 1])) + abs(x - a[i + 1]))
        << endl;
    x = a[i];
  }
}

Measured memory_bytes: 1664
# -*- coding utf-8 -*-

MOD = 10 ** 9 + 7

n = int(input())
an = list(map(int, input().split()))
an = [an[i] - (i+1) for i in range(n)]
an.sort()

if len(an) % 2 == 0:
    b = (an[n//2] + an[n//2 - 1])/2
else:
    b = an[n//2]

ans = int(sum([abs(a - b) for a in an]))

print(ans)

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

/*テストコードをコピーさせていただき、一度提出させていただきます*/

using LL = long long;
 
 int main() {
 
     int N;
     cin >> N;
 
     vector<int> a(N + 1);
     for (int i = 1; i <= N; i++) {
         cin >> a[i];
     }
 
     vector<int> ans;
     vector<int> b(N + 1, 0);
     for (int i = N; i >= 1; i--) {
         int sum = 0;
         for (int j = i; j <= N; j += i) {
             sum += b[j];
         }
         if ((sum + a[i]) % 2 == 1) {
             b[i]++;
             ans.push_back(i);
         }
     }
 
     reverse(ans.begin(), ans.end());
 
     cout << ans.size() << endl;
     for(auto x: ans) cout << x << " ";
 
 }

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

long n, ans;

void dfs(long x, bool seven, bool five, bool three) {
    if (x > n) {
        return;
    }
    if (seven && five && three) {
        ans++;
    }
    dfs(x * 10 + 7, true, five, three);
    dfs(x * 10 + 5, seven, true, three);
    dfs(x * 10 + 3, seven, five, true);
}

int main() {
    cin >> n;
    dfs(0, false, false, false);
    cout << ans << endl;
    return 0;
}

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

unsigned long long f(unsigned long long a){
  if(a % 2 == 1){
    return (a + 1) /2 % 2;
  } else{
    return a ^ ((a+1)/2%2);

  }
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << setprecision(20) << fixed;

  unsigned long long A, B;
  cin >> A >> B;
  cout << (f(B)^f(A-1)) <<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
#define ff first
#define ss second
#define endl "\n"
#define loop(i,s,e) for(int i=s;i<e;i++)
#define int long long
#define mp make_pair
#define pii pair<int,int>
#define mset(a,f)  memset(a , f , sizeof(a))
#define pb push_back
const int N = 2e6 + 6;
const int M = 1e9 + 7;
int A[N];
int n;

void solve()
{
	int a, b, c;
	cin >> a>> b >> c;

	swap(a,b);
	swap(a,c);

	cout << a << " " << b  << " " << c ;
}
 
int32_t main()
{
 
ios_base:: sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
    
 	
 	int t = 1;
 	// cin >> t;
 	while(t--)solve();
  
}


Measured memory_bytes: 256
s = gets.chomp!

head = s[0, 2].to_i
tail = s[2, 2].to_i

case head
when 0
    head_mm = 0
when 1..12
    head_mm = 1
when 13..99
    head_mm = 2
end

case tail
when 0
    tail_mm = 0
when 1..12
    tail_mm = 1
when 13..99
    tail_mm = 2
end

case [head_mm, tail_mm]
when [0,0], [0,2], [2,0], [2,2]
    puts "NA"
when [0, 1], [2,1]
    puts "YYMM"
when [1,0], [1,2]
    puts "MMYY"
when [1,1]
    puts "AMBIGUOUS"
end


Measured memory_bytes: 1788
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n = I()
nl = len(str(n))
nya = ['3','5','7']
def dfs(s):
    if len(s) > nl:
        return
    if len(s) >= 3:
        if s.count('7') >= 1 and s.count('5') >= 1 and s.count('3') >= 1:
            if int(s) <= n:
                global cnt
                cnt += 1
    for i in range(3):
        s += nya[i]
        dfs(s)
        s = s[:-1]
    return
cnt = 0
dfs('')
print(cnt)


Measured memory_bytes: 10368
#include <iostream>
#include <fstream>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <numeric>
#include <queue>
using namespace std;
 
#define LOCAL  1
#define UPLOAD 2
 
#define ll long long
const long long INF = 1LL << 60;
 
template <class T = long long> T input(){T x;cin >> x;return x;}
template <class T> void output(T x){cout << x << endl;}
#define debug(x) cerr << #x<< ": " << x<< '\n';
#define debugBit(x,n) cerr << #x<< ": " << std::bitset<n>(x) << '\n';
#define REP(i,M) for(int i=0;i<M;i++)
 
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;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
 
int main()
{
#if ENVIRONMENT == LOCAL
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
  
  ll N = input();
  ll R = input();

  if(N >= 10){
    output(R);
  }
  else{
    output(R + 100*(10-N));
  }
  
  return 0;
}

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

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

#define limit 50

bool graph[limit][limit] = {false};
bool pass[limit] = {false};

int ans = 0;

void dfs(int v, int n) {
    pass[v] = true;

    for (int v2 = 0; v2 < n; v2++) {
        if (!graph[v][v2])
            continue;
        if (pass[v2])
            continue;

        dfs(v2, n);
    }
}

//dfs問題

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

    int n, m;
    cin >> n >> m;

    vector<int> a(m), b(m);

    rep(i, m) {
        cin >> a[i] >> b[i];

        a[i]--;
        b[i]--;

        graph[a[i]][b[i]] = true;
        graph[b[i]][a[i]] = true;
    }

    int ans = 0;
    rep(i, m) {
        graph[a[i]][b[i]] = false;
        graph[b[i]][a[i]] = false;

        rep(j, n) pass[j] = false;

        dfs(0, n);

        bool bb = false;
        rep(j, n) if (pass[j] == false) bb = true;

        if (bb) {
            ans++;
        }

        graph[a[i]][b[i]] = true;
        graph[b[i]][a[i]] = true;
    }

    cout << ans << endl;
}

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

macro_rules! test {
    ($($input:expr => $output:expr),* $(,)*) => {
#[test]
        fn solve_test() {
            $(
                assert_eq!(solve($input), $output);
            )*
        }
    };
}
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

macro_rules! stdin {
    () => {{
        use std::io::Read;
        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }};
}

fn main() {
    println!("{}", solve(&stdin!()));
}
fn solve(src: &str) -> String {
    input! {
        source = src,
        s:String,
    }

    s[0..3].to_string()
}
test! {
    "takahashi" => "tak",
    "naohiro" => "nao",
}



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

using namespace std;

int main(){
	string num,tmp2;
	char tmp[1000000];
	int n,index;
	int leng;
	char c;
	int count;
	while(cin>>n,n){
		cin>>num;
		for(int i=0;i<n;i++){
			leng = num.length();
			c = num[0];
			count = 1;
			index = 0;
			for(int j=1;j<leng;j++){
				if(c == num[j]){
					count++;
				}else{
					if(count >= 10){
						tmp[index++] = count/10+48;
						tmp[index++] = count%10+48;
					}else{
						tmp[index++] = count+48;
					}
					tmp[index++] = c;
					c = num[j];
					count = 1;
				}
			}
			if(count >= 10){
				tmp[index++] = count/10+48;
				tmp[index++] = count%10+48;
			}else{
				tmp[index++] = count+48;
			}
			tmp[index++] = c;
			tmp2 = tmp;
			num = tmp2.substr(0,index);
		}
		cout<<num<<endl;
	}
	return 0;
}

Measured memory_bytes: 1400
import random
import time

def down_score(d, c, last_d, score):
    sum = 0
    for i in range(26):
        sum = sum + c[i]*(d-last_d[i])
        
    return int(score - sum)


def main():
    D = int(input())

    c = list(map(int, input().split()))

    s = [list(map(int, input().split())) for i in range(D)]

    start = time.time()
    
    last_d = [0 for i in range(26)]
    
    ans = []
    
    score1 = 0
    
    for i in range(D):
        max = 0
        idx = 0
        for j in range(26):
            if max < (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] != 0:
                max = s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2
                idx = j
            elif max == (s[i][j] + c[j] * (i-last_d[j])*(i-last_d[j]+1)/2) and c[j] * (i-last_d[j])*(i-last_d[j]+1)/2 > c[idx]* (i-last_d[idx])*(i-last_d[idx]+1)/2 and c[j] != 0:
                idx = j
            
        last_d[idx] = i+1
        score1 += s[i][idx]
        score1 = down_score(i+1,c,last_d,score1)
        
        ans.append(idx)

    while time.time() - start < 1.9:
        last_d = [0 for i in range(26)]
        score2 = 0  
        tmp1 = 0
        tmp2 = 1
        tmp3 = 2
        if random.randint(0,1):           
            d1 = random.randint(0,D-11) 
            d2 = random.randint(d1+1,d1+5)
            d3 = random.randint(d2+1,d2+5) 
            tmp1 = ans[d1]
            tmp2 = ans[d2]
            tmp3 = ans[d3]
            if random.randint(0,1):
                ans[d1] = tmp2
                ans[d2] = tmp1
                ans[d3] = tmp3
            else:
                ans[d1] = tmp1
                ans[d2] = tmp3
                ans[d3] = tmp2
                  
        else:
            d1 = random.randint(0,D-11) 
            d2 = random.randint(d1+1,d1+5)
            d3 = random.randint(d2+1,d2+5) 
            tmp1 = ans[d1]
            tmp2 = ans[d2]
            tmp3 = ans[d3]
            if random.randint(0,1):
                ans[d1] = tmp2
                ans[d2] = tmp3
                ans[d3] = tmp1
            else:
                ans[d1] = tmp3
                ans[d2] = tmp1
                ans[d3] = tmp2
            
        for i in range(D):
            score2 += s[i][ans[i]]
            last_d[ans[i]] = i+1
            score2 = down_score(i+1, c, last_d, score2)
        
        if score1 > score2:
            ans[d1] = tmp1
            ans[d2] = tmp2
            ans[d3] = tmp3
        else:
            score1 = score2
    
    for i in range(D):
        print(ans[i]+1)  

if __name__ == "__main__":
    main()


Measured memory_bytes: 9684
//Relive your past life.
//Face your demons.
//The past is never dead,it is not even past.
//The memories are not only the key to the past but...also to the future.
//coded in Rusty Lake
#include<cmath>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#include<bitset>
#include<cassert>
#include<cctype>
#include<cerrno>
#include<cfloat>
#include<ciso646>
#include<climits>
#include<clocale>
#include<complex>
#include<csetjmp>
#include<csignal>
#include<cstdarg>
#include<cstddef>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cwchar>
#include<cwctype>
#include<deque>
#include<exception>
#include<fstream>
#include<functional>
#include<iomanip>
#include<ios>
#include<iosfwd>
#include<iostream>
#include<istream>
#include<iterator>
#include<limits>
#include<list>
#include<locale>
#include<map>
#include<memory>
#include<new>
#include<numeric>
#include<ostream>
#include<queue>
#include<set>
#include<sstream>
#include<stack>
#include<stdexcept>
#include<streambuf>
#include<string>
#include<typeinfo>
#include<utility>
#include<valarray>
#include<vector>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#define ll   long long
#define pb   push_back
#define mp   make_pair
#define orz  1000000007
using namespace std;
int n,m;
char a[505][505],b[505][505];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)scanf(" %c",a[i]+j),b[i][j]=a[i][j];
    }
    for(int i=1;i<=m;++i){
        a[1][i]=b[n][i]='#';
        if(i&1){
            for(int j=2;j<n;++j)a[j][i]='#';
        }
        else{
            for(int j=2;j<n;++j)b[j][i]='#';
        }
    }
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)printf("%c",a[i][j]);
        printf("\n");
    }
    printf("\n");
    
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j)printf("%c",b[i][j]);
        printf("\n");
    }
    //system("pause");
    return 0;
}


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

using namespace std;
const int MAX = 2005;
const int MOD = 1000000007;
long long fac[MAX], finv[MAX], inv[MAX];

void COMinit()
{
	fac[0] = fac[1] = 1;
	finv[0] = finv[1] = 1;
	inv[1] = 1;
	for (int i = 2; i < MAX; ++i)
	{
		fac[i] = fac[i - 1] * i % MOD;
		inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
		finv[i] = finv[i - 1] * inv[i] % MOD;
	}
}

long long comb(long long n, long long k)
{
	if (n < k)
	{
		return 0;
	}
	if (n < 0 || k < 0)
	{
		return 0;
	}
	return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main(void)
{
	int n, k;
	cin >> n >> k;
	int r = n - k;
	COMinit();
	for (int i = 0; i < k; ++i)
	{
		cout << comb(k - 1, i) * comb(r + 1, i + 1) % MOD << endl;
	}
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
  char s[11], t[11];
  scanf("%s %s", &s, &t);
  int a, b;
  scanf("%d %d", &a, &b);
  char u[11];
  scanf("%s", &u);
  
  if (strcmp(s, u) == 0)
  {
    printf("%d %d", a-1, b);
  }
  else
  {
    printf("%d %d", a, b-1);
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>

using namespace std;

int main(){
	int n = 0;
	cin >> n;
	long long int m = 1000000007;
	long long int ans = 1;
	for(int d = 1; d <= n; d++){
		ans = ((ans % m) * (d % m)) % m;
	}
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N 100005
#define oo (1<<30)
#define L(__) (__ << 1)
#define R(__) (L(__)|1)
using namespace std;
vector<int> G[N]; set<int> S[4*N];
int n,cnt,u[N],v[N],nu[N],d[N],sz[N],zl[N],MA[4*N],A[4*N],MB[4*N],B[4*N],T[4*N],f[N];
void update(int t)
{
	MA[t]=min(MA[L(t)],MA[R(t)]);
	if(MA[t]==MA[L(t)]) A[t]=A[L(t)];
	else A[t]=A[R(t)];
	if(MA[L(t)]==MA[R(t)]){
		if(MB[L(t)]>MB[R(t)]) MB[t]=MB[R(t)],B[t]=B[R(t)];
		else MB[t]=MB[L(t)],B[t]=B[L(t)];
	  }
	else{
		if(MA[L(t)]>MA[R(t)]){
			MB[t]=min(MA[L(t)],MB[R(t)]);
			if(MB[t]==MA[L(t)]) B[t]=A[L(t)];
			else B[t]=B[R(t)];
		  }
		else{
			MB[t]=min(MA[R(t)],MB[L(t)]);
			if(MB[t]==MA[R(t)]) B[t]=A[R(t)];
			else B[t]=B[L(t)];
		  }
	  }
}
void dfs(int t,int fa)
{
	int i; d[t]=d[fa]+1,f[t]=fa,sz[t]=1;
	for(i=0;i<G[t].size();i++)
		if(G[t][i]!=fa)
			dfs(G[t][i],t),sz[t]+=sz[G[t][i]];
}
void DFS(int t,int fa)
{
	int i,p=0; nu[t]=++cnt;
	zl[t]=zl[t] ? zl[t] : t;
	for(i=0;i<G[t].size();i++)
		if(G[t][i]!=fa&&sz[G[t][i]]>sz[p]) p=G[t][i];
	if(p) zl[p]=zl[t],DFS(p,t);
	for(i=0;i<G[t].size();i++)
		if(G[t][i]!=fa&&G[t][i]!=p) DFS(G[t][i],t);
}
void TA(int t,int d){ T[t]+=d,MA[t]+=d,MB[t]+=d; return ;}
void push(int t)
{
	if(T[t]==0) return ;
	TA(L(t),T[t]);
	TA(R(t),T[t]);
	T[t]=0;
}
void Ins(int t,int l,int r,int l1,int r1,int x)
{
	int mid=(l+r)>>1;
	if(l>r1 || r<l1) return ;
	if(l>=l1&&r<=r1){
		TA(t,1);
		S[t].insert(x);
		return ;
	  }
	push(t);
	Ins(L(t),l,mid,l1,r1,x);
	Ins(R(t),mid+1,r,l1,r1,x);
	update(t);
}
void Del(int t,int l,int r,int l1,int r1,int x)
{
	int mid=(l+r)>>1;
	if(l>r1 || r<l1) return ;
	if(l>=l1&&r<=r1){
		TA(t,-1);
		S[t].erase(x);
		return ;
	  }
	push(t);
	Del(L(t),l,mid,l1,r1,x);
	Del(R(t),mid+1,r,l1,r1,x);
	update(t);
}
void ins(int t)
{
	int x=u[t],y=v[t];
	while(zl[x]!=zl[y]){
		if(d[zl[x]]<d[zl[y]]) swap(x,y);
		Ins(1,1,n,nu[zl[x]],nu[x],t);
		x=f[zl[x]];
	  }
	if(d[x]<d[y]) swap(x,y);
	Ins(1,1,n,nu[y]+1,nu[x],t);
}
int find(int t,int l,int r,int x)
{
	int mid=(l+r)>>1;
	if(S[t].size()) return (*S[t].begin());
	if(l==r) return 0;
	if(x<=mid) return find(L(t),l,mid,x);
	else return find(R(t),mid+1,r,x);
}
int del()
{
	int t,x,y;
	if(MB[1]>1) return 0;
	t=find(1,1,n,B[1]),x=u[t],y=v[t];
	while(zl[x]!=zl[y]){
		if(d[zl[x]]<d[zl[y]]) swap(x,y);
		Del(1,1,n,nu[zl[x]],nu[x],t);
		x=f[zl[x]];
	  }
	if(d[x]<d[y]) swap(x,y);
	Del(1,1,n,nu[y]+1,nu[x],t);
	return 1;
}
void build(int t,int l,int r)
{
	int mid=(l+r)>>1;
	if(l==r){ A[t]=l,MB[t]=oo; return ;}
	build(L(t),l,mid),build(R(t),mid+1,r);
	update(t);
}
int main()
{
	int i,x,y;
	scanf("%d",&n);
	build(1,1,n);
	for(i=1;i<n;i++){
		scanf("%d %d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	  }
	dfs(1,0);
	DFS(1,0);
	for(i=1;i<n;i++){
		scanf("%d %d",&u[i],&v[i]);
		ins(i);
	  }
	for(i=1;i<n;i++)
		if(!del()){ printf("NO"); return 0;}
	printf("YES");
	return 0;
}


Measured memory_bytes: 138112
#include<bits/stdc++.h>
using namespace std;
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define rep(i,n) for(int i=0; i<(n); ++i)
#define per(i,n) for(int i=n-1;i>=0;++i)
#define rep1(i,n) for(int i=1; i<=n; ++i)
#define per1(i,n) for(int i=n; i>=1; ++i)
#define debug cout << "line : " << __LINE__ << " debug" << endl
#define Dcout(N) cout << setprecision(20) << N << endl
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() ) //被り削除
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define INF 1e9
const int mod = 1000000007;
typedef long long ll;
//------------------------------------------------------------------------

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

  string s; cin >> s;
  rep(i,s.size()) cout <<"x";
  cout << endl;

  return 0;
}




Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<float.h>
#include<list>
#include <array>
#include <complex>
#include<stdio.h>
#include<string.h>
#include <bitset>

using namespace std;
#define int  long long

#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807LL
#define I64_MAX2 1223372036854775807LL
#define INF I64_MAX2
#define MOD 1000000007
#define MEM_SIZE 10000
#define DEBUG_OUT true
#define ALL(x) (x).begin(),(x).end()


template<typename T> void DEBUG(T e){if(DEBUG_OUT == false)return; std::cout << e <<" ";}
template<typename T> void DEBUG(const std::vector<T>& v){if(DEBUG_OUT == false)return;for(const auto& e : v){std::cout<< e << " "; } std::cout << std::endl;}
template<typename T> void DEBUG(const std::vector<std::vector<T> >& vv){if(DEBUG_OUT == false)return;for(const auto& v : vv){ DEBUG(v); } }
template<class T,class... Ts> void DEBUG(T d, Ts... e){if(DEBUG_OUT == false)return;DEBUG(d);DEBUG(e...);}
template <class T> void corner(bool flg, T hoge) {if (flg) {cout << hoge << endl; exit(0);}}
template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }



void solve(void)
{
  double N; cin>>N;
  for (int i = 1; i <= 500000; i++)
  {
    // if(i == 927)
    // {
    //   cout<<i*108;
    // }
    if((i*108)/100*100 == N * 100)
    {
      cout<<i<<endl;
      return;
    }
  }
  cout<<":("<<endl;
  return;
}
int32_t main(int32_t argc, const char *argv[])
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);

std::cout << std::fixed;
std::cout << std::setprecision(9);
solve();

return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;cin>>n>>m;
  vector<long long>a,b,c,d,e,f,g,h;
  for(int i=0;i<n;i++){
    long long x,y,z;cin>>x>>y>>z;
    a.push_back(x+y+z);
    b.push_back(x+y-z);
    c.push_back(x-y+z);
    d.push_back(x-y-z);
    e.push_back(-x+y+z);
    f.push_back(-x+y-z);
    g.push_back(-x-y+z);
    h.push_back(-x-y-z);
  }
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());
  sort(c.begin(),c.end());
  sort(d.begin(),d.end());
  sort(e.begin(),e.end());
  sort(f.begin(),f.end());
  sort(g.begin(),g.end());
  sort(h.begin(),h.end());
  long long A=0,B=0,C=0,D=0,E=0,F=0,G=0,H=0;
  for(int i=0;i<m;i++){
    A+=a[n-1-i];
    B+=b[n-1-i];
    C+=c[n-i-1];
    D+=d[n-i-1];
    E+=e[n-i-1];
    F+=f[n-i-1];
    G+=g[n-i-1];
    H+=h[n-i-1];
  }
  cout<<max({A,B,C,D,E,F,G,H})<<endl;
}


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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

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

  ll n;
  cin >> n;

  ll now = 0, ans = 0, t;

  for (ll i = n; i >= 1; i--) {
    now = 0;
    t = i;
    while (t > 0) {
      t /= 10;
      now++;
    }
    if (now % 2 == 1) {
      ans++;
    }
  }

  cout << ans << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;

int gcd(int m, int n) {
    int r = 0, a, b;
    a = (m > n) ? m : n;
    b = (m < n) ? m : n;
    r = b;
    while (a % b != 0) {
        r = a % b;
        a = b;
        b = r;
    }
    return r;
}

int main() {
    int N, X, result;
    cin >> N >> X;

    for (int i = 0; i < N; i++) {
        if (i == 0){
            int current;
            cin >> current;
            result = max(current - X, X - current);
        } else {
            int current;
            cin >> current;
            result = gcd(max(current - X, X - current), result);
        }
    }

    cout << result << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
typedef long long LL;
int N,k;
LL dp[6001][51];//i:値,j:何個パスしたか
LL dp2[6001][51];//保存用(nxt)
LL MOD=1e9+7;

void solve(int x){
	//パス&x番目の値を固定しない
	REP(i,6001){
		REP(j,51){
			if(dp[i][j]!=0){
				dp2[i-x-x][j+1]+=dp[i][j];
				dp2[i-x-x][j+1]%=MOD;
			}
		}
	}
	//パス&x番目の値固定
	REP(i,6001){
		REP(j,51){
			if(dp[i][j]!=0){
				dp2[i-x+x][j]+=(dp[i][j]*j);
				dp2[i-x+x][j]%=MOD;
			}
		}
	}
	//入れる&x番目の値固定しない
	REP(i,6001){
		REP(j,51){
			if(dp[i][j]!=0){
				dp2[i-x+x][j]+=(dp[i][j]*j);
				dp2[i-x+x][j]%=MOD;
			}
		}
	}
	//入れる&x番目の値固定
	REP(i,6001){
		REP(j,51){
			if(dp[i][j]!=0){
				//違うとき
				if(j!=0){
					dp2[i+x+x][j-1]+=(dp[i][j]*(j*j));
					dp2[i+x+x][j-1]%=MOD;
				}
				//同じ時
				dp2[i][j]+=dp[i][j];
				dp2[i][j]%=MOD;
			}
		}
	}
	
	//答えを移す
	REP(i,6001){
		REP(j,51){
			dp[i][j]=dp2[i][j];
			dp2[i][j]=0;
		}
	}
}


int main(){
	cin>>N>>k;
	dp[3000][0]=1;
	REP(i,N){
		solve(i+1);
		/*REP(i,14){
			cout<<3000-7+i<<endl;
			REP(j,3){
				cout<<dp[3000-7+i][j]<<" ";
			}
			cout<<endl;
		}
		cout<<endl;*/
	}
	cout<<dp[3000+k][0]<<endl;
}

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

using namespace std;


void solve() {
    int n, Y;
    cin >> n >> Y;
    Y /= 1000;
    Y -= n;
    auto gg = [](){
        cout << "-1 -1 -1\n";exit(0);
    };
    if (Y < 0 || Y > 9*n) {
        gg();
    }
    int lim = Y/9;
    for (int z = 0; z <= lim; z++) {
        int y = (Y - 9*z)/4;
        if (4*y+9*z != Y) continue;
        int x = n-y-z;
        if (x<0 || y<0 || z<0) continue;
        cout << z <<' '<<y<<' '<<x; return;
    }
    gg();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    cout << endl;
}


Measured memory_bytes: 256