akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#include <iostream>
#include <numeric>
#include <math.h>
#define ll  long long
#define ull unsigned long
#define mpa make_pair
#define pb push_back
#define ff first
#define pii pair<ll,ll>
#define dd double
#define trace(x) cerr << #x << " : " << x << endl
#define ss second
#define boost ios_base::sync_with_stdio(0)
#define forp(i,a,b) for(ll i=a;i<=b;i++)
#define rep(i,n)    for(ll i=0;i<n;++i)
#define ren(i,n)    for(ll i=n-1;i>=0;i--)
#define forn(i,a,b) for(ll i=a;i>=b;i--)
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(); i != (c).end();
#define sc(x) scanf("%lld",&x)
#define clr(x,val) memset(x,val,sizeof(x))
#define pr(x) printf("%lld\n",x) 
#define gc getchar
#define pdd pair<dd,dd>
#define prec(x) cout<<fixed<<setprecision(x)
using namespace std;
pii cord[1000005],quer[1000005];
int main(){
	ll n;
	set<string> col;
	cin>>n;
	for(ll i=1;i<=n;i++){
		string s;
		cin>>s;
		col.insert(s);
	}
	cout<<col.size();
}


Measured memory_bytes: 19120
#include<iostream>
#include<cstdio>
#include<queue>
#define Lens 105
using namespace std;
int N;
int A[Lens][Lens];
int d[Lens];
char c[Lens];
queue<int> Q;

int main()
{
	cin >> N;
	Q.push(1);
	
	for (int i = 1; i <= N; i++)
	{
		int k, n;
		cin >> k >> n;
		c[k] = 'w';
		for (int i = 0; i < n; i++)
		{
			int j;
			cin >> j;
			A[k][j] = 1;
		}
	}
	c[1] = 'g';
	while (Q.size())
	{
		int i = Q.front();
		Q.pop();
		for(int j=1;j<=N;j++)
		{
			if (A[i][j] == 1 && c[j] == 'w')
			{
				c[j] = 'g';
				d[j] = d[i] + 1;
				Q.push(j);
			}	 
		}
	}
	for (int i = 2; i <= N; i++)
	{
		if (c[i] == 'w')
			d[i] = -1;
	}	
	for (int i = 1; i <= N; i++)
	{
		cout << i << ' ' << d[i] << endl;
	}
	return 0;
}


Measured memory_bytes: 3128
N = int(input())
P = list(input().split())
Q = list(input().split())
for i in range(N):
    P[i] = int(P[i])
    Q[i] =  int(Q[i])
List = []
digit = list(int(i) for i in range(1,N+1))

def cur(n,N,x,List,kouho):
    if n ==0:
        List.append(x)
        return 0
    for i in kouho:
        
        x_new = x + [i]
        Index = kouho.index(i)
        new_kouho = kouho[0:Index]+kouho[Index+1:len(kouho)]
       
        cur(n-1,N,x_new,List,new_kouho)

x = []
cur(N,N,x,List,digit)

num_p = List.index(P)
num_q = List.index(Q)

print(abs(num_p-num_q))

Measured memory_bytes: 8948
#include <stdio.h>

int main(void) {

        int num1, num2, num3, dummy;

        

        scanf("%d%d%d", &num1, &num2, &num3);

        

        if(num1 > num2) {

            dummy = num1;

            num1 = num2;

            num2 = dummy;

        }

        if(num2 > num3) {

            dummy = num2;

            num2 = num3;

            num3 = dummy;

        }

        if(num1 > num2) {

            dummy = num1;

            num1 = num2;

            num2 = dummy;

        }

        

        printf("%d %d %d\n", num1, num2, num3);

        return 0;

}


Measured memory_bytes: 1940
#include <cstdio>

using namespace std;

typedef long long ll;

int n;
int a[111111];
int c[111111];

const ll mod = 1e9 + 7;

ll fact[111111], ifact[111111];

ll mod_pow(ll a, ll b, ll m) {
  if (b == 0) return 1;
  ll c = mod_pow(a*a%m, b/2, m);
  if (b%2 == 1) c = (c*a) % mod;
  return c;
}

ll C(ll n, ll r) {
  if (n < 0 || r < 0 || r > n) return 0;
  if (r > n/2) r = n - r;
  return fact[n] * ifact[n-r] % mod * ifact[r] % mod;
}

int main(void) {
  scanf("%d", &n);
  if (n == 1) {
    puts("1\n1");
    return 0;
  }
  fact[0] = ifact[0] = 1;
  for (int i = 1; i <= n+1; i++) {
    fact[i] = fact[i-1] * i % mod;
    ifact[i] = mod_pow(fact[i], mod-2, mod);
  }
  int x, y;
  for (int i = 0; i < n+1; i++) {
    scanf("%d", a+i);
    if (c[a[i]] > 0) {
      x = c[a[i]] - 1;
      y = i;
    }
    c[a[i]] = i + 1;
  }

  // printf("%d %d\n", x, y);
  int A = x;
  int B = n - y;
  for (int i = 1; i <= n+1; i++) {
    ll m = 0;
    m = C(A + B, i - 1);
    printf("%lld\n", ((C(n+1, i) - m)%mod + mod)%mod);
  }
  return 0;
}


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

int main() {
    int64_t a, b, c;
    cin >> a >> b >> c;
    int64_t d = c - (a + b);
    cout << (d > 0 && (4 * a * b < d * d) ? "Yes" : "No") << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<int>> v;
vector<string> w;
void foo(int a,int b){
    cout<<string(a,'.')<<w[b]<<endl;
    for(int x:v[b]){
        foo(a+1,x);
    }
}
int main(){
    cin>>n;
    v.resize(n);
    w.resize(n);
    for(int i=0;i<n;i++){
        int t;
        cin>>t>>w[i];
        if(t) v[t-1].push_back(i);
    }
    foo(0,0);
}

Measured memory_bytes: 1444
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char s[N];
struct Node{
	int x,mi;
	bool operator < (const Node &b)const{
		if((x>=0)!=(b.x>=0))return x>=0;
		if(x>=0)return mi>b.mi;
		return x+b.mi>b.x+mi;
	}
}a[N];
int main(){
	int n,sum=0,w,mi;scanf("%d",&n);
	for(int i=0;i<n;i++){
		mi=w=0;scanf("%s",s);
		for(int j=0;s[j];j++){
			if(s[j]=='(')w++;
			else w--,mi=min(mi,w);
		}
		sum+=w;
		a[i]={w,mi};
	}
	if(sum)return puts("No"),0;
	sort(a,a+n);
	for(int i=0;i<n;i++){
		if(sum+a[i].mi<0)return puts("No"),0;
		sum+=a[i].x;
	}
	puts("Yes");
	return 0;
}

Measured memory_bytes: 11336
#include <stdio.h>
main(void) {
int a,b,c,d,e,f;
scanf("%d%d%d",&a,&b,&c);
if(a>b){
d=a;
a=b;
b=d;
}
if(b>c){
e=b;
b=c;
c=e;
}
if(a>b){
f=a;
a=b;
b=f;
}
printf("%d %d %d\n",a,b,c);
return 0;
}

Measured memory_bytes: 596
from collections import Counter
 
N = int(input())
d = Counter(map(int, input().split()))
 
sticks_len = []
for k, v in d.items():
  if v >= 2:
    sticks_len.append(k)
  if v >= 4:
    sticks_len.append(k)
    
sticks_len.sort()
 
if len(sticks_len) >= 2:
  print(sticks_len[-1] * sticks_len[-2])
else:
  print(0)
 


Measured memory_bytes: 28116
import math,sys

n,p=map(int,sys.stdin.readline().split())
limit = int(p ** (1/n))+1
if limit==1:
    print(1)
elif n==1:
    print(p)
else:
    cnt,ans=0,1

    while p % 2 == 0:
        p /= 2
        cnt += 1
    ans *= 2 ** (cnt // n)
    
    for div in range(3, limit, 2):
        cnt = 0
        while p % div == 0:
            cnt += 1
            p /= div
        if cnt >= n:
            ans *= div ** (cnt // n)
    print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
vector<int> e[1000500];
int p[1000500];
int n;
void link(int a,int b) 
{
	e[a].push_back(b);
	e[b].push_back(a);
}

void dfs(int u,int fa) 
{
    for (int i=0;i<e[u].size();i++) 
	{
        int v=e[u][i]; 
		if (v==fa) continue;
        dfs(v,u);
    }
    if (!p[u] && !p[fa]) p[u] = p[fa] = 1; 
}

int main() {
    cin>>n;
    for (int i=1;i<n;i++) 
    {
    	int x,y;
    	cin>>x>>y;
    	link(x,y);
    }
    p[0] = 1;
    dfs(1,0);
    int ans = 1;
    for (int i=1;i<=n;i++) if (!p[i]) ans = 0;
    puts(!ans?"First":"Second");
    return 0;
}

Measured memory_bytes: 29184
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
typedef long long ll;
int main(){
	ll n, ans = 1, cou = 0;
	string str;
	cin >> n >> str;
	for(int i = 0;i < str.size();i++){
		int now = ((cou % 2 == 0) + (str[i] == 'B')) % 2;
		if(now){
			ans = (ans * cou) % MOD;
			cou--;
		}
		else {
			cou++;
		}
		if(cou < 0){
			cout << 0 << endl;
			return 0;
		}
	}
	for(int i = 1;i <= n;i++){
		ans = (ans * i) % MOD;
	}
	cout << (cou == 0 ? ans : 0) << endl;
}


Measured memory_bytes: 640
x = int(input())

poypoyo = 'po'
for i in range(1000):
    for j in range(1000):
        if i**5 - j**5 == x:
            print(i,j)
            quit()
            break
        if i**5 - (-j)**5 ==x:
            print(i,-j)
            quit()
            break
        po = 'po'
        poypoyo += po



Measured memory_bytes: 9292
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int K = sc.nextInt();
		sc.nextLine();
		String str = sc.nextLine();


		if(str.length() <= K) {
			System.out.println(str);
			return;
		}

		String str2 = str.substring(0,K) + "...";

		System.out.println(str2);

	}

}

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

using namespace std;

long long int rec(vector<int>& wt, vector<int>& val, int n, int w, vector<vector<long long int>>& dp){
    if(n==0 || w==0)
        return 0ll;
    if(dp[n][w]!=-1)
        return dp[n][w];
    if(wt[n-1]<=w){
        return dp[n][w] = max(val[n-1]+rec(wt,val,n-1,w-wt[n-1],dp), rec(wt,val,n-1,w,dp));
    } else {
        return dp[n][w] = rec(wt,val,n-1,w,dp);
    }
}

int main() {
    int n,w;
    cin>>n>>w;
    vector<int> val(n), wt(n);
    for(int i=0;i<n;i++){
        cin>>wt[i];
        cin>>val[i];
    }
    vector<vector<long long int>> dp(n+1, vector<long long int>(w+1, -1));
    cout<<rec(wt,val,n,w,dp)<<"\n";
}

Measured memory_bytes: 83260
#include<bits/stdc++.h>
using namespace std;
#define int long long int
signed main()
{
    int n,m,k;
    cin>>n>>m>>k;
    int a[n],b[m],mx=-1;
    for(int i=0;i<n;i++)
        cin>>a[i];
    for(int i=0;i<m;i++)
    cin>>b[i];
    vector<int>v1(n+1),v2(m+1);
    for(int i=0;i<n;i++)
    v1[i+1]=v1[i]+a[i];
    for(int i=0;i<m;i++)
       v2[i+1]=v2[i]+b[i];
    for(int i=0;i<=n;i++)
    {
        int best=k-v1[i];
        if(best<0)
            continue;
        int z=lower_bound(v2.begin(),v2.end(),best)-v2.begin();
        if(z>m || v2[z]>best)
            z--;
        mx=max(z+i,mx);
    }
    cout<<mx<<endl;
}



Measured memory_bytes: 9576
while n = gets.to_i
  break if n == 0
  gems = 21.times.map{ [0]*21 }
  n.times { x, y = gets.split(' ').map(&:to_i); gems[x][y] = 1 }
  x = 10; y = 10
  gets.to_i.times do |i|
    d, m = gets.split(' '); m = m.to_i
    case d
    when 'N' then (1..m).each{ |i| gems[x][y+i] = 0 }; y += m;
    when 'E' then (1..m).each{ |i| gems[x+i][y] = 0 }; x += m;
    when 'S' then (1..m).each{ |i| gems[x][y-i] = 0 }; y -= m;
    when 'W' then (1..m).each{ |i| gems[x-i][y] = 0 }; x -= m; end
  end
  if gems.flatten.all?{|v| v == 0} then puts "Yes"
  else puts "No"
  end
end

Measured memory_bytes: 9344
#include<iostream>

using namespace std;
const int SENTINEL=2000000000;
int cnt=0;
void merge(int A[],int n,int left,int mid,int right){
	int n1=mid-left;
	int n2=right-mid;
	int *L=new int[n1+1];
	int *R=new int[n2+1];
	for(int i=0;i<n1;++i) L[i]=A[left+i];
	for(int i=0;i<n2;++i) R[i]=A[mid+i];
	L[n1]=R[n2]=SENTINEL;
    int i=0,j=0;
    for(int k=left;k<right;k++){
    	cnt++;
    	if(L[i]<=R[j])A[k]=L[i++];
    	else A[k]=R[j++];
    }
    delete L;
    delete R;

}
void mergeSort(int A[],int n,int left,int right){
   if(left+1<right){
   		int mid=(left+right)/2;
   		mergeSort(A,n,left,mid);
   		mergeSort(A,n,mid,right);
   		merge(A,n,left,mid,right);
   }
}
int main(){
	int n;
	cin>>n;
	int *A=new int[n];
	for(int i=0;i<n;++i)cin>>A[i];

	mergeSort(A,n,0,n);
	
	for(int i=0;i<n;++i){
		if(i>0)cout<<' ';
		cout<<A[i];
	}
	cout<<endl;

	cout<<cnt<<endl;
	delete A;
	return 0;
}


Measured memory_bytes: 6892
function Main(input){
    const arr = input.split(' ').map(Number);
    let K = arr[3];
    let total=0;

    if(K>=arr[0]){
        total += arr[0];
        K -= arr[0];
    } else {
        total += K;
        console.log(total);
        return;
    }

    K -= arr[1];
    
    if(K>0){
        console.log(total-K)
    }else{
        console.log(total)
    }
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29732
N=int(input())
OTOSHIDAMA=0

for i in range(0,N):
  A,B=(input().split(" "))
  AA=float(A)
  if B=="BTC":
    AA=AA*380000
  
  OTOSHIDAMA+=AA
  #print(OTOSHIDAMA)
  
print(OTOSHIDAMA)

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

using namespace std;

#define debug(x) '[' << #x << " is: " << x << "] "
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.precision(10);
	cout << fixed;
	#ifndef ONLINE_JUDGE
	//	freopen("input.txt","r",stdin);
	#endif
	int n;
	cin>>n;
	vector<int> a(n);
	int mn = 1e9,mx = -1e9;
	int at1 = -1,at2 = -1;
	for(int i=0;i<n;i++){
		cin>>a[i];
		if(a[i] < mn)at1 = i;
		mn = min(mn , a[i]);
		if(a[i] > mx)at2 = i;	
		mx = max(mx , a[i]);
	}
	vector<pair<int,int>> event;
	if(at1 != at2){
		if(mx >= -mn){
			for(int i=0;i<n;i++){
				if(i == at2)continue;
				event.push_back({at2+1,i+1});
				a[i] += a[at2];
			}
			for(int i=1;i<n;i++){
				if(a[i-1] > a[i]){
					a[i]+=a[i-1];
					event.push_back({i,i+1});
				}
			}
		}else{
			for(int i=0;i<n;i++){
				if(i == at1)continue;
				event.push_back({at1+1,i+1});
				a[i] += a[at1];
			}
			for(int i=n-2;i>=0;i--){
				if(a[i] > a[i+1]){
					a[i]+=a[i+1];
					event.push_back({i+2,i+1});
				}
			}
		}
		cout << event.size() << '\n';
		for(auto i : event)
			cout << i.first << ' ' << i.second << '\n';
	}else{
		cout << 0 << '\n';
	}
	for(int i : a)
		cerr << i << ' ';
	cerr << '\n';
}	

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
ll n[10005];
int main()
{
	int n;
	int m;
	cin>>n;
	cin>>m;
	int temp=pow(100,n);
	if(m!=100) cout<<m*temp<<endl;
	else cout<<(m+1)*temp<<endl;
	return 0;
}

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

int main() {
	int n;
	cin >> n;
	vector<int> a(n), aa(n);
	for(int i=0; i<n; ++i) cin >> a[i], aa[i] = a[i];
	
	int ans = 1e9;
	for(int j=0; j<=a[0]; ++j) {
		// cout << j << endl;
		int ret = j;
		a[0] -= j;
		for(int i=1; i<n-1; ++i) {
			while(a[i]>0) {
				if(a[i-1] > 0) {
					a[i-1]--;
					a[i]--;
					ret += 2;
				} else {
					a[i]--;
					a[i+1]--;
					ret += 2;
				}
			}
		}
		ret += max(0, a[0]) + max(0, a[n-1]);
		// cout << ret << endl;
		for(int i=0; i<n; ++i) a[i] = aa[i];
		ans = min(ans, ret);
	}
	
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 3136
import java.text.DecimalFormat;
import java.util.stream.LongStream;
import java.util.stream.IntStream;
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        FastScanner sc = new FastScanner();
        PrintWriter out = new PrintWriter(System.out);

        AtCoder problem = new AtCoder(sc);
        problem.solve(out);

        out.flush();
    }

}

class AtCoder {

    final String S;

    AtCoder(FastScanner sc) {
        S = sc.next();
    }

    void solve(PrintWriter out) {
        out.println(S.matches("(hi)+") ? "Yes" : "No");
    }

}

// https://qiita.com/p_shiki37/items/a0f6aac33bf60f5f65e4
class FastScanner {

    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        if (hasNextByte()) {
            return buffer[ptr++];
        } else {
            return -1;
        }
    }

    private static boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    public boolean hasNext() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) {
            ptr++;
        }
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public long nextLong() {
        if (!hasNext()) {
            throw new NoSuchElementException();
        }
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }

    public int nextInt() {
        long nl = nextLong();
        if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) {
            throw new NumberFormatException();
        }
        return (int) nl;
    }

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


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

#define REP(i, e) for(int (i) = 0; (i) < (e); ++(i))
#define FOR(i, b, e) for(int (i) = (b); (i) < (e); ++(i))
#define ALL(c) (c).begin(), (c).end()
#define MIN(c) (*min_element(ALL(c))) 
#define MAX(c) (*max_element(ALL(c)))
#define ACC(c) (accumulate(ALL(c), 0))
#define MP(a, b) (make_pair((a), (b)))
#define ENDL "\n"
#define PRINT(x) cout << (x) << ENDL

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

inline int in(int& a) {return scanf("%d", &a);}
inline void out(int n) {printf("%d\n", n);}
template<typename T> inline void swap(T& a, T& b) {T tmp = a; a = b; b = tmp;}
auto pint_compare = [](pint x, pint y) -> bool{return (x.first < y.first);};


signed main(){
    int N;
    int x[50], y[50];
    map<pint, int> mp;
    cin >> N;
    REP(i, N){
        cin >> x[i] >> y[i];
    }
    REP(i, N){
        REP(j, N){
            if(i == j) continue;
            mp[pint(x[i] - x[j], y[i] - y[j])]++;
        }
    }
    int m = 0;
    for(auto i : mp){
        m = max(m, i.second);
    }
    PRINT(N - m);
    return 0;
}

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

using namespace std;
typedef long long ll;

#define rep(i, N) for (int i = 0; i < (int)N; i++)
const ll MOD = pow(10,9)+7;
const ll LLINF = pow(2,61)-1;
const int INF = pow(2,30)-1;

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

int main() {
  ll N, X; cin >> N >> X;
  ll g = gcd(N, X);
  ll result = (N-g)*3;
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

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

		final int n = sc.nextInt();
		final int k = sc.nextInt();

		int result = 1;
		for (int i = 0; i < n; i++) {
			if (result * 2 < result + k) {
				result = result * 2;
			} else {
				result = result + k;
			}
		}

		 System.out.print(result);

	}

}


Measured memory_bytes: 21844
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;
//const int MOD = 998244353;

long long int N, M, K, H, W, L, R;
//int N, M, K, H, W, L, R

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

	cin >> N;
	vector<pair<int, int>>v(N);
	for (auto &i : v)cin >> i.first >> i.second;
	vector<int>p(N);
	for (int i = 0; i < N; i++) {
		p[i] = i / (N / 2);
	}
	int ans = 0;
	vector<int>a(N/2);
	vector<int>b(N/2);
	vector<pair<int, int>>vp(N / 2);
	int ai = 0;
	int bi = 0;
	int box = 0;
	do {
		ai = 0;
		bi = 0;
		for (int i = 0; i < N; i++) {
			if (p[i])a[ai++] = i;
			else b[bi++] = i;
		}
		do {
			bool flag = false;
			for (int i = 0; i < N / 2; i++) {
				vp[i] = { v[a[i]].first - v[b[i]].first,v[a[i]].second - v[b[i]].second };
				if (a[i] < b[i])flag = true;
			}
			if (flag)continue;
			box = 0;
			for (int i = 0; i < N / 2; i++) {
				for (int j = i + 1; j < N / 2; j++) {
					if (vp[i].first*vp[j].second == vp[i].second*vp[j].first)box++;
				}
			}
			ans = max(ans, box);
		} while (next_permutation(b.begin(), b.end()));
	} while (next_permutation(p.begin(), p.end()));
	cout << ans << endl;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
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 long long LL;
const int64_t INF=1e18+1;
const int mod = 1000000007;

int T;
map<LL,LL>dp;
LL N,A,B,C,D;
LL f(LL x){
  	if(x==0)return dp[0]=0;
    if(x==1)return dp[1]=D;
	if(dp[x]>0)return dp[x];
  
	if(1e18/x<=D){dp[x]=1e18;}
    else{dp[x]=x*D;}
	dp[x]=min(dp[x],f(x/2)+A+(x%2)*D);
	dp[x]=min(dp[x],f(x/3)+B+(x%3)*D);
	dp[x]=min(dp[x],f(x/5)+C+(x%5)*D);
	dp[x]=min(dp[x],f((x+1)/2)+A+(2-x%2)*D);
	dp[x]=min(dp[x],f((x+2)/3)+B+(3-x%3)*D);
	dp[x]=min(dp[x],f((x+4)/5)+C+(5-x%5)*D);
	return dp[x];
}

int main(){
  cin>>T;
  for(int i=0;i<T;i++){
    cin>>N>>A>>B>>C>>D;
    dp.clear();
    cout<<f(N)<<endl;
  }
  return 0;                       
}

Measured memory_bytes: 4412
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush
from fractions import gcd
from copy import deepcopy
import math
import queue
#import numpy as np
#import sympy as syp(素因数分解とか)
Mod = 1000000007
import sys

sys.setrecursionlimit(100000) 
  
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

def factorial(i):
    if i == 1:
        return 1
    else:
        return i*factorial(i-1)
 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[py] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)




def main(): #startline--------------------------------------------
    n = int(input())
    p = sieve_of_eratosthenes(55555)
    res = []
    for i in p:
        if i % 5 == 1:
            res.append(i)
    print(*res[:n],sep = " ")
if __name__ == "__main__":
    main() #endline===============================================
    

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

int main(){
  int a,b,c,d;
  int count=0;
  cin >> a >> b >> c >> d;
  while(!(a<=0 || c<=0)){
    if(count%2==0){
    	c -= b;
    	count++;
    }
    else{
      a -= d;
      count++;
    }
  }
  if (a<=0)
    cout << "No" << endl;
  if (c<=0)
    cout << "Yes" << endl;
}

Measured memory_bytes: 3636
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

co = 0

for i in range(n):
    if a[i] % 2 == 1:
        co += 1
print("YES" if co % 2 == 0 else "NO")

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

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

	int temp = 0;
	for (int i = 0 ; i < m ; i++){
		int x;
		cin >> x;
		n -= x;
	}	

	if (n < 0){cout << -1 << endl;}
	else {cout << n << endl;}
	return 0;
}


Measured memory_bytes: 3624
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007

#A
def A():
    return

#B
def B():
    x1, y1, x2, y2 = LI()
    a = x2 - x1
    b = y2 - y1
    print(x2 - b, y2 + a, x1 - b, y1 + a)
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == '__main__':
    B()


Measured memory_bytes: 3700
#include<iostream>
#include<algorithm> 
#include<cstdio>
#include<cctype>
#include<string>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<unordered_map>
#include<map>
using namespace std;
//#define for(i,a,b) for(int i=(a);i<=(b);i++)
#define ppi pair<int,int>
typedef long long ll;
typedef unsigned long long ull;
const int inf = 0x3f3f3f3f;
const int N = 1005;
const double pi = acos(-1.0);
const ll mod = 1e9+7;
void init(){ios::sync_with_stdio(false);cin.tie(0);} 
template<class T>inline void read(T &res)
{
	char c;T flag=1;
	while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
	while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
int cnt[2020];
int main()
{
	init();
	string a;cin>>a;
	reverse(a.begin(),a.end());
	ll ans=0,c=1,r=0;
	for(int i=0;i<a.length();i++)
	{
		r=(r+c*(a[i]-'0'))%2019;
		c=c*10%2019;
		ans+=cnt[r]++;
	}
	cout<<ans+cnt[0];
	return 0;
}
/*
1817181712114

3
*/

Measured memory_bytes: 3768
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=int(a);i<int(b);++i)
using namespace std;
typedef long long ll;
int INF = (1LL << 30) - 1;
int MOD = 1e9+7;
main(){
    int a;
    cin >> a;
    cout << 3 * a * a << endl;
}

Measured memory_bytes: 256
from collections import defaultdict

MOD = 10**9 + 7
facts = defaultdict(int)


def factorize(n):
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
                facts[i] += 1
    if temp != 1:
        facts[temp] += 1


N = int(input())
for x in range(1, N+1):
    factorize(x)

ans = 1
for v in facts.values():
    ans *= (v+1)
    ans %= MOD

print(ans)


Measured memory_bytes: 3316
l = [[] for _ in range(3)]
for i in range(0, 3):
    l[i] = [int(_) for _ in input().split()]
t = [0, 0, 0]
for i in range(0, 3):
    for j in range(0, 3):
        t[i] += l[j][i]
p = (t[0] - t[1]) / 3
q = (t[0] - t[2]) / 3
if l[0][0]-p == l[0][1] and l[0][0]-q == l[0][2] and l[1][0]-p == l[1][1] and l[1][0]-q == l[1][2] and l[2][0]-p == l[2][1] and l[2][0]-q == l[2][2]:
    print('Yes')
else:
    print('No') 
    

Measured memory_bytes: 3064
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

int main() {
    LL n; cin >> n;
    LL ans = (LL)floor(sqrt((double)n));
    cout << ans * ans << endl;
}


Measured memory_bytes: 256
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int mod = 1e+9 + 7;

//マクロ
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = (ll)(n)-1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = (a); i <= (b); i++)
#define FORD(i, a, b) for (ll i = (a); i >= (b); i--)
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))
#define INF 1000000000000
#define MOD 10000007
#define PB push_back
#define MP make_pair
#define F first
#define S second

struct town
{
  int id, x, y;
};

int main()
{
  int n;
  cin >> n;
  vector<town> ts(n);
  vector<int> arr;
  rep(i, n)
  {
    int x, y;
    cin >> x >> y;
    arr.push_back(i);
    town t = {int(i), x, y};
    ts[i] = t;
  }
  ll count = 0;
  double sum = 0;
  do
  {
    rep(j, n - 1)
    {
      int i = arr[j];
      int k = arr[j + 1];
      ll xdiff = ts[i].x - ts[k].x;
      ll ydiff = ts[i].y - ts[k].y;
      double tmp = sqrt(xdiff * xdiff + ydiff * ydiff);
      sum += tmp;
    }
    count++;
  } while (next_permutation(arr.begin(), arr.end()));
  double ans = sum / count;
  printf("%.10f\n", ans);
  return 0;
}

Measured memory_bytes: 888
# coding: utf-8
N, Q = map(int,input().split())
#N,Q=map(int,input().split())
#親のノードを格納　2の親が4のとき par[2]=4
par=[0]
#木の深さを格納　根が2の深さが3の時 rank[2]=3
rank=[0]

#初期化
for i in range(1,N+1):
    par.append(i)
    rank.append(0)

#xの根を探す、同時に通過したノードすべてを根に直接つける
def find(x):
    #xの親がxならば根なのでxを返す
    if par[x]==x:
        return x
    else:
        #違う場合は親の親を捜し自分の親にする
        par[x] = find(par[x])
        #再帰的に行うと根が見つかる
        return par[x]

#xが属する木とyが属する木を併合する
def unite(x,y):
    #根を探す
    root_x=find(x)
    root_y=find(y)

    #根が同じなら元からつながっているので終わり
    if root_x == root_y:
        return

    #ランクが大きい木の根の直下にランクが小さい木を結合
    if rank[root_x] < rank[root_y]:
        par[root_x] = root_y

    else:
        par[root_y] = root_x

    #ランクが等しいときのみランクが増える#なぜ#yにxが結合？
    if rank[root_x]==rank[root_y]:
        rank[root_x]+=1

#xとyが同じ木に存在するかを調べる
def same(x,y):
    return find(x)==find(y)

#main
for i in range(Q):
    a,b=map(int,input().split())
    unite(a, b)
res = []
for i in range(1, N+1):
    res.append(find(i))
ans = len(set(res))-1
print(ans)

Measured memory_bytes: 86828
n = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    return divisors
p = make_divisors(n)
x = 0
i = 1
ans = 0
def countf(x):
    for j in range(1,x+2):
        if (1+j)*j//2 > x:
            return j - 1
while n != 1:
    if n % p[i] == 0:
        x += 1
        n = n // p[i]
    else:
        if x != 0:
            ans += countf(x)
            x = 0
        i += 1
ans += countf(x)
print(ans)

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

int n;
int a[100004];
int dp[100004];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++)
    {
        dp[i]=min(dp[i-1]+abs(a[i]-a[i-1]),dp[i-2]+abs(a[i]-a[i-2]));
    }
    cout<<dp[n-1];

    return 0;
}


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

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

int main() {
	int N; cin >> N;
	if(N < 1000) puts("ABC");
	else puts("ABD");
	return 0;
}


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

int main() {
	int n, m;
	while(cin >> n >> m && (n || m)){
		int place[1001] = {0}, p;
		for(int i = 0; i < n; ++i){
			for(int j = 0; j < m; ++j){
				scanf("%d", &p);
				if(p == 1)
					place[j]++;
			}
		}
		int rank[1001] = {0};
		for(int i = 0; i < m; ++i)
			rank[i] = place[i];
			
		sort(place, place + m, greater<int>());
		for(int i = 0; i < m; ++i){
			for(int j = 0; j < m; ++j){
				if(place[i] == rank[j]){
					if(i)
						cout << " ";
					cout << j + 1;
					rank[j] = -1;
					break;
				}
			}
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 1268
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>

using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);i++)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

typedef pair<int, int> P;
typedef pair<string, int> SP;
typedef long long ll;
typedef pair<ll, ll> PLL;

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n;
int a[200005];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;
  REP(i, n) cin >> a[i];
  ll a_s[200005];
  a_s[0] = 0;
  REP(i, n) {
    a_s[i + 1] = a_s[i] +  a[i];
  }

  int l = 1, r = 3;
  ll ans = LLINF;
  FOR(i, 2, n - 1) {
    while(l < i && abs((a_s[i] - a_s[l]) - a_s[l]) >= abs((a_s[i] - a_s[l + 1]) - a_s[l + 1])) l++;

    if(r <= i) r = i + 1;
    while(r < n && abs((a_s[n] - a_s[r]) - (a_s[r] - a_s[i])) >= abs((a_s[n] - a_s[r + 1]) - (a_s[r + 1] - a_s[i]))) r++;

    ll p = a_s[l], q = a_s[i] - a_s[l], t = a_s[r] - a_s[i], s = a_s[n] - a_s[r];
    ll mi = min(min(p, q), min(t, s));
    ll ma = max(max(p, q), max(t, s));
    ans = min(ans, ma - mi);
  }

  cout << ans << endl;
}


Measured memory_bytes: 2560
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

char dp[100001][3];

int main() {
  int N, K, R, S, P;
  cin >> N >> K >> R >> S >> P;
  string T;
  cin >> T;
  int64_t total = 0;
  for (size_t k = 0; k < K; ++k) {
    char past = '.';
    for (size_t i = 0, end = (N + K - 1) / K;  i < end; ++i) {
      if (k + i * K >= N) break;
      char out = T[k + i * K];
      if (out == 's') {
        if (past != 'r') {
          total += R;
          past = 'r';
        } else if (N > k + (i + 1) * K && T[k + (i + 1) * K] == 'p') {
          past = 'p';
        } else {
          past = 's';
        }
      } else if (out == 'p') {
        if (past != 's') {
          total += S;
          past = 's';
        } else if (N > k + (i + 1) * K && T[k + (i + 1) * K] == 'r') {
          past = 'r';
        } else {
          past = 'p';
        }
      } else {
        if (past != 'p') {
          total += P;
          past = 'p';
        } else if (N > k + (i + 1) * K && T[k + (i + 1) * K] == 's') {
          past = 's';
        } else {
          past = 'r';
        }
      }
    }
  }
  cout << total << endl;
  return 0;
}


Measured memory_bytes: 512
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long L, R, ans;
		L = sc.nextLong();
		R = sc.nextLong();
		sc.close();
		R = Math.min(R, L + 4038);
		ans = 2100;
		for (long i = L; i < R; i++) {
			for (long j = i + 1; j <= R; j++) {
				long a = (i * j) % 2019;
				if (ans > a) {
					ans = a;
				}
			}
		}
		System.out.println(ans);
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
const int N=20010;
const int C=30000;
int n;
int p[N];
int a[N],b[N];
int main(){
	scanf("%d",&n);
	for (int i=1; i<=n; ++i) scanf("%d",&p[i]);
	for (int i=1; i<=n; ++i){
		a[i]=a[i-1]+C;
	}
	for (int i=n; i>=1; --i){
		b[i]=b[i+1]+C;
	}
	int la=0;
	for (int i=1; i<=n; ++i){
		int now=a[p[i]]+b[p[i]];
		if (now<=la){
			int k=la-now;
			a[p[i]]+=k+1;
		}
		la=a[p[i]]+b[p[i]];
	}
	for (int i=1; i<=n; ++i) cout<<a[i]<<" ";
	cout<<'\n';
	for (int i=1; i<=n; ++i) cout<<b[i]<<" ";
}

Measured memory_bytes: 3996
D, G = map(int, input().split())
p_list = []
c_list = []
for i in range(D):
    list_for = list(map(int, input().split()))
    p_list.append(list_for[:][0])
    c_list.append(list_for[:][1])

memo = 0
count_list=[]
for i in range(1<<D):
    sum = 0
    count = 0
    lcount = 1
    del memo
    for j in range(D):
        if (i>>j)&1:
            sum += 100*(j+1)*p_list[j]+c_list[j]
            count += p_list[j]
        else:
            memo = j


    while G-sum > 0 and lcount<p_list[memo]:
        sum += 100*(memo+1)
        lcount += 1
        count += 1
    if sum >= G:
        count_list.append(count)

print(min(count_list))
#print(count_list)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <numeric>


int main()
{
	int a, b, c;

	std::cin >> a >> b >> c;

	int min = 100000000;

	min = std::min(a + b, min);
	min = std::min(a + c, min);
	min = std::min(b + c, min);

	std::cout << min << std::endl;
	
	return 0;
}

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

struct P{
    int alpha, beta;
};

P dp[32][32][32][32];

P rec(int l, int t, int r, int b, int acc, vector<vector<int> >& a){
    
    //cout << l << " " << t << " " << r << " " << b << " " << endl;
    P res;
    res.alpha = 0;
    res.beta = 0;    
    int sum = 0;
    //合計がアなら0を返す
    for(int i = t; i < b; i++){    
        for(int j = l; j < r; j++){
            sum += a[i][j];
        }
    }

    if(sum < acc){
        return res;
    }

    //分けて再帰呼び出し
    
    //縦
    for(int i = t + 1; i < b; i++){

        P left, right;

        //左
        if(dp[l][t][r][i].alpha != 0){
            left = dp[l][t][r][i];            
        }else{
            left = rec(l, t, r, i, acc, a);
        }

        //右
        if(dp[l][i][r][b].alpha != 0){
            right = dp[l][i][r][b];
        }else{
            right = rec(l, i, r, b, acc, a);
        }

        if(left.alpha != 0 && right.alpha != 0){
            if(res.alpha < left.alpha + right.alpha){
                res.alpha = left.alpha + right.alpha;
                res.beta = min(left.beta, right.beta);
            }else if(res.alpha == left.alpha + right.alpha){
                res.beta = max(res.beta, min(left.beta, right.beta));
            }
        }
    }

    //横
    for(int i = l + 1; i < r; i++){

        P left, right;

        //左
        if(dp[l][t][i][b].alpha != 0){
            left = dp[l][t][i][b];            
        }else{
            left = rec(l, t, i, b, acc, a);
        }

        //右
        if(dp[i][t][r][b].alpha != 0){
            right = dp[i][t][r][b];
        }else{
            right = rec(i, t, r, b, acc, a);
        }

        if(left.alpha != 0 && right.alpha != 0){
            if(res.alpha < left.alpha + right.alpha){
                res.alpha = left.alpha + right.alpha;
                res.beta = min(left.beta, right.beta);
            }else if(res.alpha == left.alpha + right.alpha){
                res.beta = max(res.beta, min(left.beta, right.beta));
            }
        }
    }

    if(res.alpha == 0){
        res.alpha = 1;
        res.beta = sum - acc;
    }

    dp[l][t][r][b] = res;
    return res;
}

int main(){

    while(1){
        
        memset(dp, 0, sizeof(dp));

        int num, power;
        int h, w, s; cin >> h >> w >> s;
        if(!h) break;

        int sum = 0;
        vector<vector<int> > a(h, vector<int> (w));
        for(int i = 0; i < h; i++){
            for(int j = 0; j < w; j++){
                cin >> a[i][j];
                sum += a[i][j];
            }
        }

        int acc = sum - s;
        P ans = rec(0, 0, w, h, acc, a);
        
        //答え
        cout << ans.alpha << " " << ans.beta << endl;
    }

    return 0;
}


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

using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
/*
200 380
300 550
500 850
1000 380*5*0.8
1200 550*4*0.85
1500 850*3*0.88

*/
int main(){
	int n;
	int dp[110]={0};
	rep(i,110) dp[i]=1<<20;
	int d[7][2];
	d[0][0]=2;
	d[0][1]=380;

	d[1][0]=3;
	d[1][1]=550;

	d[2][0]=5;
	d[2][1]=850;

	d[3][0]=10;
	d[3][1]=380*5*0.8;

	d[4][0]=12;
	d[4][1]=550*4*0.85;

	d[5][0]=15;
	d[5][1]=850*3*0.88;

	d[6][0]=0;
	d[6][1]=0;
	rep(i,6){
		// cout<<d[i][0]<<" "<<d[i][1]<<endl;
		dp[d[i][0]]=d[i][1];
	}
	dp[0]=dp[1]=300000;
	rep(i,56){
		rep(j,7){
			dp[i+d[j][0]]=min(dp[i+d[j][0]],dp[i]+d[j][1]);
		}
	}
	rep(i,57){
		// cout<<dp[i]<<endl;
	}
	while(cin>>n,n){
		cout<<dp[n/100]<<endl;
	}
}

Measured memory_bytes: 1160
def main():
    from collections import defaultdict
    from collections import deque
    import sys
    input = sys.stdin.readline
    dd = defaultdict(list)
    pq = defaultdict(int)

    N, Q = map(int, input().split())

    for _ in range(N-1):
        a,b = map(int, input().split())
        dd[a].append(b)

    for _ in range(Q):
        p,q = map(int, input().split())
        pq[p] += q
    
    answer = [0]*N
    queue = deque()
    queue.append(1)

    while queue != deque():
        tmp = queue.popleft()
        answer[tmp-1] += pq[tmp]
        for i in dd[tmp]:
            queue.append(i)
            answer[i-1] += answer[tmp-1]
            
    print(*answer)

if __name__ == '__main__':
    main()

Measured memory_bytes: 88396
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<iostream>
#include<numeric>
#include<cctype>
using namespace std;

int main() {
	int a, b;
	cin >> a >> b;
	if (a == 1)
		a += 13;
	if (b == 1)
		b += 13;
	if (a == b)
		cout << "Draw" << endl;
	else if (a > b)
		cout << "Alice" << endl;
	else
		cout << "Bob" << endl;
}

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

using namespace std;

typedef long long llint;

const llint MAXN = 100005;
const llint LOG = 35;
const llint INF = 100000000000007LL;

llint n, sol;
llint l[MAXN];
llint dp[MAXN] [LOG];

int main () {
	cin >> n;
	for (int i=1; i<=n; i++) {
		scanf("%lld", &l[i]);
	}
	for (int i=0; i<=n; i++) {
		for (int j=0; j<LOG; j++) {
			dp[i] [j]=INF;
		}
	}
	dp[0] [0]=0;
	for (int i=1; i<=n; i++) {
		llint val=log2(l[i]);
		llint pot=pow(2, val);
		for (int j=0; j<LOG; j++) {
			if (pot!=l[i]) {
				if (j>=val+1) {
					dp[i] [val]=min(dp[i] [val], dp[i-1] [j]);
				} else if (j>=1) {
					dp[i] [val]=min(dp[i] [val], dp[i-1] [j]+val+1-j);
				}
				if (j>=val) {
					dp[i] [val+1]=min(dp[i] [val+1], dp[i-1] [j]+1);
				} else {
					dp[i] [val+1]=min(dp[i] [val+1], dp[i-1] [j]+val+1-j);
				}
			} else {
				if (j>=val) {
					dp[i] [val]=min(dp[i] [val], dp[i-1] [j]);
				} else {
					dp[i] [val]=min(dp[i] [val], dp[i-1] [j]+val-j);
				}
			}
		}
		sol=min(dp[i] [val], dp[i] [val+1]);
	}
	cout << sol;
	return 0;
}

Measured memory_bytes: 28416
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long ans = 1;
        for (int i = 0; i < n; i++) {
            long t = sc.nextLong();
            ans = lcm(Math.max(t, ans), Math.min(t, ans));
        }

        System.out.println(ans);
        sc.close();
    }

    public static long gcd(long a, long b){
        if(a < b) return gcd(b, a);
        if(b == 0) return a;
        return gcd(b, a%b);
    }

    public static long lcm(long a, long b){
        long c = a / gcd(a, b);
        return b * c;
    }

}


Measured memory_bytes: 21844
#include <iostream>

using namespace std;

int N;

int a[105], b[105], c[105], d[105];

int C[220][220], F[220][220];

int p[220];  //parent
int check[220];

void FIND_PATH(int n) {
	check[n] = 1;
	if (p[2 * N + 1] != -1) { return; }
	//cout << "n= " << n << endl;
	for (int i = 0; i <= 2 * N + 1; i++) {
		if (i == n) { continue; }
		if (C[n][i] - F[n][i] > 0 && check[i] < 0) { p[i] = n; FIND_PATH(i); }
	}
};

void FLOW(int m) {

		F[p[m]][m] += 1;
		F[m][p[m]] -= 1;

	//cout << "m= " << m << endl;

	if (p[p[m]] >= 0) { FLOW(p[m]); }
}

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

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

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

	//=====================================
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (a[i] < c[j] && b[i] < d[j]) { C[i][j + N] = 1; }
		}
	}

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

	for (int i = 1; i <= N; i++) { C[i + N][2 * N + 1] = 1; }
     //=======================

	while (1) {
		//cout << "ret" << endl;
		for (int i = 0; i <= 2 * N + 1; i++) { p[i] = -1; check[i] = -1; }
		FIND_PATH(0);
			int J = 2 * N + 1;
		//while (p[J] >= 0) { cout << " " << J; J = p[J]; }cout << endl;
		if (p[2 * N + 1] >= 0) { FLOW(2 * N + 1); }
		else { break; }
	}

	int ans = 0;
	for (int i = 1; i <= N; i++) {
		ans += F[0][i];
	}

	cout << ans << endl;

	//system("pause");
	return 0;
}

Measured memory_bytes: 640
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x[] = new int[n];
        int y[] = new int[n];
        for(int i = 0 ; i < n ; i++)
            x[i] = sc.nextInt();
        for(int i = 0 ; i < n ; i++)
            y[i] = sc.nextInt();
        double p1 = 0;
        double p2 = 0;
        double p3 = 0;
        double maxp = 0;
        for(int i = 0 ; i < n ; i++)
        {
            double d = Math.abs(x[i] - y[i]);
            p1 += d;
            p2 += Math.pow(d,2);
            p3 += Math.pow(d,3);
            if(d > maxp)
                maxp = d;
        }
        System.out.println(p1);
        System.out.println(Math.sqrt(p2));
        System.out.println(Math.cbrt(p3));
        System.out.println(maxp);
    }
}


Measured memory_bytes: 26472
#include <bits/stdc++.h>
using namespace std;
/* * * *   * * *   	* * * */
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
#define ms(a,v) memset(a,v,sizeof a)
/* * * *   * * *   	* * * */
/* *
 *
 * Author: Hamkor
 *
 * */
int main(){
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n, k; cin>>n>>k;
	string s; cin>>s;
	int h = 0;
	for (int i=0; i<n-1; ++i) if (s[i] == s[i+1]) h++;
	cout<<min(n-1, h + 2*k);
    return 0;
}


Measured memory_bytes: 512