akhauriyash/Code-Regression huggingface dataset:
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

struct edge {
    int to, cost;
};

void dfs(vector<vector<edge>>& tree, vector<int>& color, int v)
{
    for (auto& c : tree[v]) {
        if (color[c.to] != -1) continue;
        if (c.cost % 2 == 0)
            color[c.to] = color[v];
        else
            color[c.to] = 1 - color[v];
        dfs(tree, color, c.to);
    }
}
int main()
{
    int n;
    cin >> n;
    vector<vector<edge>> tree(n);
    vector<int> color(n, -1);
    for (int i = 0; i < n - 1; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        tree[u].push_back({v, w});
        tree[v].push_back({u, w});
    }
    color[0] = 1;
    dfs(tree, color, 0);
    for (int i = 0; i < n; i++) { cout << color[i] << endl; }
}

Measured memory_bytes: 8192
N, M, X = map(int, input().split())
C = [-1] * N
A = [[] for _ in range(N)]
for i in range(N):
    C[i], *A[i] = map(int, input().split())
ans = 10 ** 10
for p in range(1 << N):
    R = [0] * M
    c = 0
    for i in range(N):
        if p & (1 << i):
            c += C[i]
            for j in range(M):
                R[j] += A[i][j]
    for j in range(M):
        if R[j] < X: break
    else:
        ans = min(ans, c)
print(ans if ans != 10 ** 10 else -1)


Measured memory_bytes: 74176
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define pli pair<long long int,int>
#define pbi pair<bool,int>
#define pob pop_back
#define all(a) a.begin(),a.end()
#define fio ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0);
#define i64 long long int
#define mem(x,y) memset(x,y,sizeof(x))
#define fill(arr,b) fill(arr, arr+sizeof(arr)/sizeof(arr[0]), b)
#define maxarr(n,arr,m) m =-1e9;for(int i=0;i<n;i++)if(arr[i]>m) m=arr[i];
#define read freopen("input.txt","r",stdin);
#define sf second.first
#define ss second.second
const double pi = acos(-1.0);
const int maxn = (i64)1e9+7;

int main()
{
    int s,w;
    cin >> s >> w;
    if(w>=s) cout << "unsafe";
    else cout << "safe";
    return 0;
}


Measured memory_bytes: 3636
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int x;
    for (int i=1;i<=10000;i++){
        cin>>x;
        if (x==0)
            break;
        else
            cout<<"Case "<<i<<": "<<x<<endl;
    }
    return 0;
}



Measured memory_bytes: 3072
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makel(N) ll N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007
#define re return 0

using namespace std;
using ll = long long int;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

template<typename T>
void maxi(T &a, T &b) {
	a = max(a, b);
}

template<typename T>
void mini(T &a, T &b) {
	a = min(a, b);
}

int main() {
	int a, b;
	cin >> a >> b;
	if (a > b)say(a - 1);
	else say(a);
}

Measured memory_bytes: 256
a, b, c, d = gets.split.map(&:to_i)

cnt = 0
min_c = a % c == 0 ? (a / c) : (a / c + 1)
max_c = b / c

c_cnt = max_c - min_c + 1

min_d = a % d == 0 ? (a / d) : (a / d + 1)
max_d = b / d

d_cnt = max_d - min_d + 1

cd_lcm = c.lcm(d)

min_cd = a % d == 0 ? (a / cd_lcm) : (a / cd_lcm + 1)
max_cd = b / cd_lcm 

cd_cnt = max_cd - min_cd + 1

puts (b - a + 1 - (c_cnt + d_cnt - cd_cnt))


Measured memory_bytes: 14328
A = int(input())
B = int(input())
C = int(input())
X = int(input())

count=0
tot = 0
for i in range(A+1):
  for j in range(B+1):
    for k in range(C+1):
      tot = i*500 + j*100 + k*50
      if tot == X:
        count+=1
      
print(count)

Measured memory_bytes: 9116
#include<stdio.h>
#include <stdlib.h>
int compare_int(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}

int main()
{
int n;
int min;
int diff;
for( ; ; ){
scanf("%d", &n);
if(n==0)break;
int data[n];
for(int i=0; i<n; i++) scanf("%d", &data[i]);
qsort(data, n, sizeof(int), compare_int);
min=data[1]-data[0];
for(int i=2; i<n; i++){
diff=data[i]-data[i-1];
if(min>diff) min=diff;
}
printf("%i\n", min);
}
return 0;
}


Measured memory_bytes: 1912
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> pi;
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);
#define f first
#define s second

const int maxn = 300010;

int h,w,m;
int bombsc[maxn];
int bombsr[maxn];
map <pi, int> mp;

int32_t main() {
	FAST
	cin >> h >> w >> m;
	for (int i =0;i<m;i++) {
		int x,y; cin >> x >> y;
		mp[pi(x,y)] = 1;
		bombsr[x]++;
		bombsc[y]++;
	}
	
	vector <pi> rows, cols;
	
	for (int i =1;i<=h;i++) {
		if (bombsr[i] == 0) continue;
		rows.push_back(pi(bombsr[i], i));
	}
	
	for (int i =1;i<=w;i++) {
		if (bombsc[i] == 0) continue;
		cols.push_back(pi(bombsc[i],i));
	}
	
	sort(rows.rbegin(),rows.rend());
	sort(cols.rbegin(),cols.rend());
	
	int overcount = 1;
	for (int i =0;i< (int) rows.size() and rows[i].f == rows[0].f;i++) {
		for (int j =0;j< (int) cols.size() and cols[j].f == cols[0].f; j++) {
			int x = rows[i].s; int y = cols[j].s; 
			if (mp.find(pi(x,y)) == mp.end()) {
				overcount = 0;
				break;
			}
		}
		if (overcount == 0) break;
	}
	
	int rans = rows[0].f + cols[0].f;
	rans -= overcount;
	cout << rans;
	
}





Measured memory_bytes: 43704
#include<stdio.h>
int main()
{
    int n,a,b,aa,bb,tmp,sum=50;
    scanf("%d",&n);
    for(a=1;a<n/2+1;a++){
        b=n-a;
        aa=a;
        bb=b;
        tmp=0;
        //printf("%d,%d ",a,b);
        //printf("%d %d %d  ",n,a,b);
        while(1){
            //printf("%d ",a);
            tmp+=aa%10;
            //printf("%d",tmp);
            aa=aa/10;
            if(aa==0) break;
        }
        while(1){
            //printf("%d ",b);
            tmp+=bb%10;
            bb=bb/10;
            if(bb==0) break;
        }
        //printf("%d\n",tmp);
        if(tmp<sum) sum=tmp;
    }
    printf("%d\n",sum);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
const int N= 1e5 + 10;
using namespace std;
int ans, n;
int a[110];
char s[N];
int main() {
    cin >> n;
    cin >> s;
    ans = 1;
    for (int i = 1; i < n; ++i) if (s[i] != s[i - 1]) ans++;
        cout << ans;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 2e5 + 7, INF = 0x3f3f3f3f;
int dp[1000010][2];

int main(){
	ios::sync_with_stdio(false); cin.tie(nullptr);
	string s; cin >> s; s = '0' + s;
	vector<int> v;
	for(int i = 0; i < s.size(); ++ i){
		v.push_back(s[i] - '0');
	}
	int n = v.size();
	dp[0][0] = 0; dp[0][1] = INF;
	for(int i = 1; i < n; ++ i){
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + v[i];
		dp[i][1] = min(dp[i - 1][0] + 1, dp[i - 1][1] - 1) + 10 - v[i];
	}
	cout << min(dp[n - 1][0], dp[n - 1][1]) << '\n';
	return 0;
}

Measured memory_bytes: 15044
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()
a = []
for i in range(n):
    a.append(INT())

a.sort()
qa = deque(a)
qb = deque()

for i in range(len(qa)):
    if i % 4 == 0:
        qb.appendleft(qa.popleft())
    elif i % 4 == 1:
        qb.append(qa.pop())
    elif i % 4 == 2:
        qb.appendleft(qa.pop())
    else:
        qb.append(qa.popleft())

ans = 0
reg = inf
for i in range(len(qb)):
    if i < len(qb) - 1:
        tmp = abs( qb[i+1] - qb[i] )
    else:
        tmp = abs( qb[0] - qb[i])
    ans += tmp
    reg = min(reg, tmp)
ans -= reg
print(ans)

Measured memory_bytes: 14828
import numpy as np

N, L = [int(x) for x in input().split()]

s =0
for i in range(1, N+1):
    s += L+i-1

ss = np.zeros(N, dtype=int)
for k in range(1, N+1):
    ss[k-1] = s-(L+k-1)

dif = abs(ss - s)
print(*ss[np.where(dif==min(dif))])

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

int N;
bool visited[1005];
char a[1005][1005];
int cnt=0,k=0;
int cc;
int t[2];

void dfs(int pos){
  if(visited[pos])return;
  visited[pos]=true;
  cc++;
  for(int i=0;i<N;i++)
    if(a[pos][i]=='Y')
      dfs(i);
}

int main(){ 
  cin>>N;
  for(int i=0;i<N;i++){
    for(int j=0;j<N;j++){
      cin>>a[i][j];
      if(a[i][j]=='Y')cnt++;
    }
  }
  for(int i=0;i<N;i++){
    if(visited[i])continue;
    k++;
    cc=0;
    dfs(i);
    t[cc%2]++;    
  }
  cnt/=2;
  
  int total=N*(N-1)/2;
  
  if(N%2==1 || t[1]%2==1){
    if( (total-cnt)%2==1 )cout<<"Taro"<<endl;
    else cout<<"Hanako"<<endl;
    return 0;
  }
  
  if(t[0]==0&&t[1]==2){
    if( (total-cnt)%2==0 )cout<<"Taro"<<endl;
    else cout<<"Hanako"<<endl;
    return 0;
  }

  if(t[0]==1&&t[1]==2){
    cout<<"Taro"<<endl;
    return 0;
  }
  
  if( (total-cnt)%2==1 )cout<<"Taro"<<endl;
  else cout<<"Hanako"<<endl;
  
  return 0;
}

Measured memory_bytes: 4084
N,T = map(int,input().split())
t = [int(i) for i in input().split()]
dif = []
for i in range(N-1):
    dif.append(t[i+1]-t[i])
cnt = 0
for i in range(len(dif)):
    if dif[i] < T:
        cnt += dif[i]
    else:
        cnt += T

print(cnt+T) 

Measured memory_bytes: 25200
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

n,p = [int(i) for i in readline().split()]
s = input()

if p==2 or p==5:
    ans = 0
    for i,c in enumerate(s):
        if int(c)%p==0:
            ans += i+1
    print(ans)
    exit()
            



res = [0]*p
res[0] = 1
t = 1
now = 0
for i in s[::-1]:
    i = int(i)
    now += i*t
    now %= p
    res[now] += 1
    t = t*10%p

ans = 0    
for i in res:
    ans += i*(i-1)//2

print(ans)

Measured memory_bytes: 3508
#include <bits/stdc++.h>
#define ll long long
#define lld long double
#define MOD 1000000007
#define CAP 100000001
#define inf 1000000000000000000LL
#define pii pair<ll,ll>
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define endl '\n'
#define sz(v) v.size()
#define all(v)    v.begin(),v.end()
#define fast  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
ll power(ll x,ll y, ll md=MOD){ll res = 1;x%=md;while(y>0){if(y&1)res = (res*x)%md;x = (x*x)%md;y = y>>1;}return res%md;}
#define dbg(x) cout <<#x<<":"<<x<<endl;
ll max1(ll a, ll b, ll c=-inf, ll d=-inf) {ll mx1=(a>b)?a:b, mx2=(c>d)?c:d; return ((mx1>mx2)?mx1:mx2);}
#define int ll

ll r[100005], sz[100005];

ll root(ll x){
	if(r[x]!=x) return root(r[x]);
	return x;
}

void union1(ll a, ll b){
	ll r1 = root(a), r2 = root(b);
	if(r1==r2) return;
	if(sz[r1]>sz[r2]) swap(r1,r2);
	r[r1] = r2;
	sz[r2] += sz[r1];
}

signed main() {
	
	ll n;
	cin>>n;
	
	for(int i=0;i<100001;i++) r[i]=i, sz[i]=1;

	std::vector<pii > v(n);
	for(int i=0;i<n;i++) cin>>v[i].f>>v[i].s;

	sort(all(v));

	for(int i=1;i<n;i++){
		if(v[i].f==v[i-1].f) union1(v[i].s,v[i-1].s);
	}

	map<ll,ll> mp1;
	map<ll,pii > mp2;

	for(int i=0;i<n;i++) mp1[v[i].f]++;

	for(int i=0;i<n;i++){
		if(i==0||v[i].f!=v[i-1].f){
			mp2[root(v[i].s)].f+=mp1[v[i].f];
			mp2[root(v[i].s)].s++;
		}
	}

	ll ans=0;

	for(map<ll,pii >::iterator it = mp2.begin();it!=mp2.end();it++){
		ll temp = (it->s).s*sz[it->f] - (it->s).f;
		ans+=temp;
	}

	cout<<ans;

} 

Measured memory_bytes: 6528
from itertools import product

n, a, b, c = map(int, input().split())
l = [int(input()) for _ in range(n)]

abc = [a, b, c]

res = float('inf')
for p in product(range(4), repeat=n):
    le = [0, 0, 0, 0]
    count = [0, 0, 0, 0]
    for i, category in enumerate(p):
        le[category] += l[i]
        count[category] += 1
    tmp = 0
    if count[0] * count[1] * count[2] == 0:
        continue
    for i in range(3):
        tmp += abs(le[i] - abc[i]) + 10 * (count[i] - 1)
    res = min(res, tmp)

print(res)



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

typedef std::vector<std::vector<long long>> matrix;
typedef long long ll;

const ll mod = 1000000007;

int n;
ll k;
matrix a;
matrix dp;

matrix matmul(matrix x, matrix y){
	matrix res(n, std::vector<ll>(n));
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				res[i][j] += x[i][k]*y[k][j];
				res[i][j] %= mod;
			}
		}
	}
	return res;
}

int main(){
	std::cin >> n >> k;
	a = matrix(n, std::vector<ll>(n));
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			std::cin >> a[i][j];
		}
	}

	dp = matrix(n, std::vector<ll>(n));
	for(int i=0; i<n; i++){
		dp[i][i] = 1;
	}

	while(k){
		if(k & 1){
			dp = matmul(dp, a);
		}
		a = matmul(a, a);
		k /= 2;
	}

	ll ans=0;
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			ans += dp[i][j];
			ans %= mod;
		}
	}
	std::cout << ans << std::endl;
	return 0;

}

Measured memory_bytes: 384
#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>;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const ll INF = 1LL << 60;

int main() {
    

    ll N;
    cin >> N ;
    ll count_n = 0;

    rep(i,N){
        ll count = 1;
        if(((i+1)%2) == 1){
            //cout << i+1 << endl;
            rep(j,i){
                if(((i+1)%(j+1)) == 0){
                    count += 1;
                }
            }
            //cout << i+1 << " " << count << endl;
            if(count == 8){
                count_n += 1;
            }
        }
    }

    cout << count_n << endl;

}

Measured memory_bytes: 3612
N, L = map(int, input().split())

sums = 0
for i in range(N):
  sums += L + i

ans = 10 ** 9
cnt = 10 ** 9
for i in range(N):
  num = L + i
  if cnt >= abs(num):
    cnt = abs(num)
    ans = sums - num

print(ans)


Measured memory_bytes: 3060
import sys
n=int(input())
a=list(map(int,input().split()))
l=[]
free=0
for i in range(n):
    if 1<=a[i]<=399:
        l.append(1)
    elif 400<=a[i]<=799:
        l.append(2)
    elif 800<=a[i]<=1199:
        l.append(3)
    elif 1200<=a[i]<=1599:
        l.append(4)
    elif 1600<=a[i]<=1999:
        l.append(5)
    elif 2000<=a[i]<=2399:
        l.append(6)
    elif 2400<=a[i]<=2799:
        l.append(7)
    elif 2800<=a[i]<=3199:
        l.append(8)
    else:
        free+=1
    
if len(set(l))==0:
    print(1,free)
    sys.exit()
print(len(set(l)),len(set(l))+free)

Measured memory_bytes: 3316
# include <bits/stdc++.h>
# define ll long long
# define pb push_back
# define fi first
# define se second
# define mp make_pair
# define pr_double(x) cout << fixed << setprecision(10) << x
using namespace std;

ll n;
double dp[3001][3001];
double h[3001];

double solve (ll c, ll x)
{
    if(dp[c][x]> -0.9) return dp[c][x];
    if(x==0) return 1;
    if(c==0) return 0;
    else
    {
       double a = (solve(c-1,x)*(1-h[c]));
       double b = (solve(c-1,x-1)*(h[c]));
       dp[c][x]=a+b;
    }
    return dp[c][x];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    for(ll i=1;i<=n;i++) cin>>h[i];
    memset(dp,-1,sizeof(dp));
    ll len = (n+1)/2;
     // dp[i][j] -> means that with the i coins what is the probability of >=x heads
     // We need at least (n+1)/2 heads
     pr_double(solve(n,len));
}


Measured memory_bytes: 74368
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define ll long long
#define INF 1000000000000000000

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

    int N;
    cin >> N;
    vector<int> A(N);
    map<int, int> ma;
    rep(i, N) {
        cin >> A[i];
        ma[A[i]]++;
    }

    sort(all(A));

    ll ans = 0;
    int MAX = *max_element(all(A)) + 10;
    vector<bool> div(MAX, false);
    rep(i, N) {
        if (!div[A[i]] && ma[A[i]] == 1) {
            ans++;
        }
        for (int j = A[i]; j < MAX; j += A[i]) {
            div[j] = true;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 13464
#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    string s,t,res="";
    cin>>s>>t;
    int n=s.length(),m=t.length();
    int dp[n+1][m+1];
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=m;j++)
        {
            if(i==0||j==0)
                dp[i][j]=0;
            else if(s[i-1]==t[j-1])
                dp[i][j]=1+dp[i-1][j-1];
            else
                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
        }
    }
    int r=n,c=m;
    while(r>0 && c>0)
    {
        int val= dp[r][c];
        if(dp[r-1][c]!=val && dp[r][c-1]!=val)
        {
            res=t[c-1]+res;
            r--,c--;
        }
        else if(dp[r][c-1]==val)
            c--;
        else if(dp[r-1][c]==val)
            r--;
    }
    cout<<res<<endl;
    return 0;
}


Measured memory_bytes: 35456
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef long double ld;
#define pb emplace_back
#define emp emplace
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end()
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN = 200100;
const ll INF = 1e9;
const ll MOD = 1e9+7;

ll N,Q,a,b,c,d,e,M,X;
ll A[MAXN];
ll B[MAXN];
map<ll,ll> p;
ll ans;
vi V[MAXN];

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>M;
	while(M--){
		cin>>Q;
		while(Q--){cin>>a;A[a]++;}
	}
	for(int i=1;i<=N;++i)if(A[i]==0)++ans;
	cout<<ans;
}

Measured memory_bytes: 8388
package main

import (
	"fmt"
)

func main() {

	var A, B, C, D int
	fmt.Scanf("%d %d %d %d", &A, &B, &C, &D)

	flag := 0
	for {
		C = C - B
		if C <= 0 {
			flag = 0
			break
		}

		A = A - D
		if A <= 0 {
			flag = 1
			break
		}

	}

	if flag == 0 {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 1836
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x,self.dist[x]
        else:
            tmp=self.find(self.parents[x])
            self.parents[x]=tmp[0]
            self.dist[x]+=tmp[1]
            return self.parents[x],self.dist[x]
    
    def union(self,x,y,d):
        rx,_=self.find(x)
        ry,_=self.find(y)
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()


Measured memory_bytes: 74588
#include<iostream>
#define loop(i,a,b) for(int i=a;i<b;i++)
#define rep(i,a) loop(i,0,a)
using namespace std;

int main(){
	int n,m,tmp;
	cin>>n>>m;
	int a[m],b[n],num[n];
	rep(i,m){cin>>a[i];a[i]--;}
	rep(i,n)num[i]=0;
	rep(i,m){
		int f=0;
		rep(j,n){
			cin>>tmp;
			if(a[i]==(tmp-1))num[j]++;
			else f++;
		}
		num[a[i]]+=f;
	}
	rep(i,n)cout<<num[i]<<endl;
	return 0;
}

Measured memory_bytes: 1160
//
// imos-algorithm
//
// c.f.
//   https://imoz.jp/algorithms/imos_method.html
//
// verified
//   AOJ Course DSL_5_A Cumulative Sum - The Maximum Number of Customers
//

#include <iostream>
#include <vector>
using namespace std;

typedef pair<int,int> Interval; // means the interval [first, second)

// T: max value of intervals
int imos(const vector<Interval> &intervals, int T) {
    vector<int> nums(T+1, 0);
    for (auto interval : intervals) {
        nums[interval.first]++;
        nums[interval.second]--;
    }
    for (int t = 0; t < T; ++t) {
        nums[t+1] += nums[t];
    }

    int res = 0;
    for (int t = 0; t <= T; ++t) res = max(res, nums[t]);

    return res;
}

int main() {
    int N, T; cin >> N >> T;
    vector<Interval> intervals(N);
    for (int i = 0; i < N; ++i) cin >> intervals[i].first >> intervals[i].second;
    cout << imos(intervals, T) << endl;
}  


Measured memory_bytes: 3896
import java.util.Scanner;

public class Main {
	public static void main(String[] args){
		Scanner io = new Scanner(System.in);	
		long X = io.nextLong();
		long Y = io.nextLong();
		
		System.out.println((Math.abs(X-Y)<=1)?"Brown"
											: "Alice");
	}
}


Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int n, m;
vector<vector<int>> adj(100005);
bool vis[100005];
vector<int> ts;

void dfs(int u) {
    vis[u] = 1;

    for (int v : adj[u]) {
        if (!vis[v]) dfs(v);
    }

    ts.emplace_back(u);
}

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

//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
    }

    for (int i = 1; i <= n; i++) {
        if (!vis[i]) dfs(i);
    }

    reverse(ts.begin(), ts.end());

    vector<int> dp(n + 1);
    int ans = -1;
    for (int u : ts) {
        for (int v : adj[u]) {
            dp[v] = max(dp[v], dp[u] + 1);
        }
        ans = max(ans, dp[u]);
    }

    cout << ans << '\n';

//    for (int p : v) cout << p << ' ';
//    cout << '\n';
}


Measured memory_bytes: 8824
N, K = [int(n) for n in input().split()]

def n(x, n):
    return x * 2**(n-1)

ans =0
for i in range(1, N+1):
    j = 1
    while n(i, j) < K:
        j += 1
    ans += (1.0/N)*0.5**(j-1)
print(ans)

Measured memory_bytes: 3060
#include<cstdio>
using namespace std;
int main()
{
	int n,k[10000],i,flg,cnt;
	while(1){
		scanf("%d",&n);
		if(n==0){
			break;
		}
		flg=0;
		cnt=0;
		for(i=0;i<n;i++){
			scanf("%d",&k[i]);
			if(k[i]<2){
				flg++;
			}
			if(k[i]==0){
				cnt++;
			}
		}
		if(flg==n){
			printf("NA\n");
		}
		else if(cnt>0){
			printf("%d\n",n+1-cnt);
		}
		else{
			printf("%d\n",n+1);
		}
	}
	return 0;
}
	


Measured memory_bytes: 2804
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin>>n;
    vector<ll> f(n+1,0);
    for(ll i=1;i<=n;i++){
        for(ll j=i;j<=n;j+=i) f[j]++;
    }
    ll ans=0;
    for(ll i=1;i<=n;i++) ans+=i*f[i];
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 81372
#include <iostream>
#include <math.h>

using namespace std;

int main(void)
{
    int A1, A2, A3, min=1000;

    cin >> A1 >> A2 >> A3;

    if(min > abs(A1-A2)+abs(A2-A3)){
        min = abs(A1-A2)+abs(A2-A3);
    }
    if(min > abs(A1-A3)+abs(A3-A2)){
        min = abs(A1-A3)+abs(A3-A2);
    }
    if(min > abs(A3-A1)+abs(A1-A2)){
        min = abs(A3-A1)+abs(A1-A2);
    }

    cout << min << endl;

    return 0;
}

Measured memory_bytes: 256
import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy


if __name__ == "__main__":
    a,v = map(int,input().split())
    b,w = map(int,input().split())
    t = int(input())
    d = abs(a-b)
    vt = v*t
    wt = w*t
    b = d + wt
    if vt >= b:
        print("YES")
    else:
        print("NO")


Measured memory_bytes: 9612
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<map>
#include<bitset>

using namespace std;
using ll = long long;

#define rep(i, n) for(int i = 0;i < (n);i++)
#define repr(i, n) for(int i = (n);i >= 0;i--)
#define repf(i, m, n) for(int i = (m);i < (n);i++)
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1;} return 0;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1;} return 0;}
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
/*----------------------------------------------------------------------------------*/

// dp[i][j]
// i番目までを考えたとき
// 価値がjとなる
// 最小の重さ
// ll dp[110][100010];

int main() {
    int n; cin >> n;
    int W; cin >> W;
    vector<int> w(n), v(n);
    rep(i,n) cin >> w[i] >> v[i];

    vector<vector<ll>> dp(110, vector<ll>(100010, 1e12));
    dp[0][0] = 0;

    rep(i,n) {
        for (int j = 0; j <= 100000; j++) {
            if (v[i]+j <= 100000) chmin(dp[i+1][v[i]+j], dp[i][j]+w[i]);
            chmin(dp[i+1][j], dp[i][j]);
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= 100000; i++) {
        if (dp[n][i]<=W) chmax(ans, i);
    }
    cout << ans << endl;
    return 0;
}


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

int main(){
	int N;
	cin >> N;
    string S,T;
    cin >> S >> T;
	vector<int> p(N);

	for(int i = 0;i < N;i++){
        cout << S.at(i) << T.at(i);
	}

    cout << endl;

}



Measured memory_bytes: 764
X, Y = map(int, input().split())

ans = 0

if X == 1 and Y == 1:
    ans += 400000

if X == 1:
    ans += 300000
elif X == 2:
    ans += 200000
elif X == 3:
    ans += 100000

if Y == 1:
    ans += 300000
elif Y == 2:
    ans += 200000
elif Y == 3:
    ans += 100000

print(ans)



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

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

  int N, M;
  cin >> N >> M;
  vector<int> load(N, 0);
  for (int i = 0; i < M; ++i) {
    int a, b;
    cin >> a >> b;
    load.at(a - 1)++;
    load.at(b - 1)++;
  }

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

  return 0;
}


Measured memory_bytes: 256
<?php
$input = explode(' ', trim(fgets(STDIN)));

$a = (int)$input[0];
$b = (int)$input[1];
$c = (int)$input[2];

for ($i=1; $i <= $b ; $i++) { 
	if ($i*$a % $b === $c) {
		echo 'YES';
		exit();
	}
}
echo 'NO';

Measured memory_bytes: 4728
// Why am I so dumb? :c
#include <bits/stdc++.h>

#define pb push_back
#define mp make_pair

#define all(x) (x).begin(), (x).end()

#define fi first
#define se second

using namespace std;

typedef long long ll;

const int MAXN = (int)1e5 + 5;

pair<ll, int> arr[MAXN];

pair<ll, int> pt[MAXN];

ll col[MAXN];

ll ans[MAXN];

ll m, lim;

int n;

void solve() {                   
	scanf("%d %lld %lld", &n, &m, &lim);

	for (int i = 0; i < n; ++i) {
		scanf("%lld %d", &arr[i].fi, &arr[i].se);

		if (arr[i].se == 2) {
			arr[i].se = -1;
		}
	}

	for (int i = 0; i < n; ++i) {
		pt[i] = mp(arr[i].fi + arr[i].se * lim, i);
		pt[i].fi = (pt[i].fi % m + m) % m;
	}

	sort(pt, pt + n);
	ll one = 0;
	int p = 0;

	for (int i = 1; i < n; ++i) {
		if (arr[i].se == arr[0].se) {
			continue;
		}

		if (arr[0].se == 1) {
		    ll t = arr[i].fi - arr[0].fi;

		    if (t <= lim * 2) {
		    	ll add = ((2ll * lim - t) / m + 1ll) % n;
				one = ((one + add) % n + n) % n;
            }
		}
		else {
			ll t = arr[0].fi - arr[i].fi + m;

			if (t <= lim * 2) {
				ll add = ((2ll * lim - t) / m + 1ll) % n;
				one = ((one - add) % n + n) % n;
			}
		}
	}

    for (int i = 0; i < n; ++i) {
    	if (pt[i].se == 0) {
    		p = i;
    		break;
    	}
    }

    if (pt[p].fi == pt[(p + 1) % n].fi) {
    	if (arr[0].se == 1) {
    		p = (p + 1) % n;
    	}
    }

    for (int i = 0; i < n; ++i) {
    	col[(p + i) % n] = (one + i) % n;
    }

    for (int i = 0; i < n; ++i) {
    	ans[col[i]] = pt[i].fi;
    }

    for (int i = 0; i < n; ++i) {
    	printf("%lld\n", ans[i]);
    }
}

int main() {    
    int tt = 1;

    while (tt--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
using ll=long long;
using vec=vector<ll>;
using vect=vector<double>;
using Graph = vector<vector<ll>>;
#define loop(i,n) for(ll i=0;i<n;i++)
#define Loop(i, m, n) for(ll i = m;i < n;i++)
#define pool(i,n) for(ll i=n;i>=0;i--)
#define Pool(i, m, n) for(ll i=n;i>=m;i--)
#define MAX 99999999999ll
#define MIN -99999999999ll
#define setbit bitset<8>
#define flagcount __builtin_popcount
#define flag(x) (1<<x)
#define flagadd(bit,x) bit|=flag(x)
#define flagpop(bit,x) bit&=~flag(x) 
#define flagon(bit,i) bit&flag(i)
#define flagoff(bit,i) !(bit & (1<<i))
#define all(v) v.begin(),v.end()
#define low2way(v,x) lower_bound(all(v),x)
#define high2way(v,x) upper_bound(all(v),x)
#define count2way(v,x) high2way(v,x)-low2way(v,x)
#define lower(v,x) low2way(v,x)-v.begin() //1番左が0、もし見つから無いならｎを出力
#define higher(v,x) high2way(v,x)-v.begin()-1 //1番左が0、もし見つからないならn-1を出力（注意）
#define putout(a) cout<<a<<endl
#define putout2(a,b) putout(a);putout(b)
#define putout3(a,b,c) putout(a);putout(b);putout(c)
#define putout4(a,b,c,d) putout(a);putout(b);putout(c);putout(d)
#define putout5(a,b,c,d,e) putout(a);putout(b);putout(c);putout(d);putout(e)
#define Gput(a,b) G[a].push_back(b)
#define cin1(a) cin>>a
#define cin2(a,b) cin>>a>>b
#define cin3(a,b,c) cin>>a>>b>>c
#define cin4(a,b,c,d) cin>>a>>b>>c>>d
#define cin5(a,b,c,d,e) cin>>a>>b>>c>>d>>e
#define sum(v) accumulate(all(v), 0ll)
#define gcd(x,y) __gcd(x,y)
ll ctoi(char c){
	if(c>='0'&&c<='9'){
		return c-'0';
	}
	return 0;
}
ll lcm(ll x,ll y){
  ll z=gcd(x,y);
  return x*y/z;
}
ll primejudge(ll n){
  if(n<2)return 0;
  else if(n==2)return 1;
  else if(n%2==0)return 0;
  double sqrtn=sqrt(n);
  Loop(i,3,sqrtn+1){
     if(n%i==0){
        return 0;
     }
     i++;
  }
  return 1;
}
int main() {
  cout << fixed << setprecision(30);
  ll a,b;
  cin>>a>>b;
  if(a==b)putout("Yes");
  else putout("No");
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>


using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;

#define REP(i,n) for(int i = 0; i < (int)(n); ++i)
#define FOR(i,a,b) for(int i = (a); i < (int)(b); ++i)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(v) ((int)v.size())

#define pb push_back
#define mp make_pair
#define mt make_tuple

class UnionFind
{
public:
    UnionFind(){};
    ~UnionFind(){};
    void init(int num_entries) {
        num_entries_ = num_entries;
        par_.resize(num_entries_);
        rank_.resize(num_entries_, 0);
        member_num_.resize(num_entries_, 1);
        REP(i, num_entries_) {
            par_[i] = i;
        }
    }
    int find(int x) {
        if (par_[x] == x) return x;
        else return par_[x] = find(par_[x]);
    }
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (rank_[x] < rank_[y]) {
            par_[x] = y;
            member_num_[y] += member_num_[x];
            member_num_[x] = 0;
        } else {
            par_[y] = x;
            member_num_[x] += member_num_[y];
            member_num_[y] = 0;
            if (rank_[x] == rank_[y]) rank_[x]++;
        }
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) {
        return member_num_[this->find(x)];
    }
private:
    int num_entries_;
    std::vector<int> par_;
    std::vector<int> rank_;
    std::vector<int> member_num_;
};

int main(void)
{
    cin.sync_with_stdio(false);
    int N, M;
    cin >> N >> M;

    UnionFind uf;
    uf.init(N);

    REP(m, M) {
        int x, y, z;
        cin >> x >> y >> z;
        --x; --y;
        uf.unite(x, y);
    }

    set<int> s;
    REP(n, N) {
        s.insert(uf.find(n));
    }
    cout << SIZE(s) << endl;
    return 0;
}


Measured memory_bytes: 6144
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
int N_MAX = 10001;
int main()
{
  int n,a,b,i,j,k,res=0;
  int c[N_MAX],d[N_MAX];
  vector<int> v[N_MAX];
  queue<int> q;
  cin >> n;
  for(i=0;i<n-1;i++){
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }
  for(i=0;i<n;i++)
    cin >> c[i];
  sort(c,c+n,greater<int>());
  fill(d+1,d+n+1,0);
  q.push(1);
  i=0;
  while(q.size()){
    j=q.front(); q.pop();
    for(k=0;k<v[j].size();k++)
      if(d[v[j][k]]==0)
        q.push(v[j][k]);
    d[j]=c[i];
    res+=c[i];
    i++;
  }
  res-=c[0];
  cout << res << endl;
  for(i=1;i<n;i++)
    cout << d[i] << " ";
  cout << d[n] << endl;
  return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;

#define in(s) cin >> s
#define out(s) cout << s << endl
#define rep(i,n) for(int i=0; i<n; i++)
#define rept(i,a,b) for(int i=a; i<b; i++)
#define pcnt __builtin_popcount
#define pcntll(x) __builtin_popcountll(x)
#define DMAX DBL_MAX;
#define IMIN INT_MIN;
#define IMAX INT_MAX;

//const ll MOD = 1e9+7;
//const ll MOD = 998244353;
//const ll MAX = 3e5+1;
//const ll INF = 1e18;
//const ld PI = acos(-1L);

signed main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);

    int H, W, K;
    in(H); in(W); in(K);
    vector<vector<char>> c(H, vector<char> (W));
    rep(i, H) rep(j, W) in(c[i][j]);
    int bit = 1<<(H+W);
    vector<int> rows(W, 0);
    vector<int> cols(H, 0);
    int ans = 0;
    rep(b, bit) {
        rep(i, H) {
            cols[i] = (b >> i) & 1;
        }
        rept(i, H, H+W) {
            rows[i-H] = (b >> i) & 1;
        }
        int cnt = 0;
        rep(i, H) rep(j, W) {
            if (cols[i] != 1 && rows[j] != 1 && c[i][j] == '#') cnt++;
        }
        if (cnt == K) ans++;

    }
    out(ans);


    return 0;
}


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

int main() {
    while (true) {
        int n;
        cin >> n;
        if (!n) return 0;

        int sum = 0;
        for (int i = 1; i * i <= n; i++) {
            if (n % i == 0) {
                sum += i;
                if (i * i < n) sum += n / i;
            }
        }
        sum -= n;
        if (n == sum) {
            cout << "perfect number" << endl;
        } else if (n > sum) {
            cout << "deficient number" << endl;
        } else {
            cout << "abundant number" << endl;
        }
    }
}

Measured memory_bytes: 3052
program main
  implicit none
  integer :: i, n, x, m(1000), rem, add
  read(*, *) n, x
  m(:) = 0
  do i = 1, n
    read(*, *) m(i)
  end do
  rem = x - sum(m)
  add = rem / minval(m(1:n))
  write(*, "(i0)") n + add
end program main


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; i++)
#define rrep(i, n) for (int i = n - 1; i >= 0; i--)
using namespace std;
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long ll;
typedef pair<ll, ll> P;
const int MOD = 1000000007;
const int MOD2 = 998244353;
using Graph = vector<vector<int> >; // グラフ

int pos[100010];
int ans[100010];

void rec(int v, const Graph &G, vector<bool> &seen, vector<int> &order) {
    seen[v] = true;
    for (auto next : G[v]) {
        if (seen[next]) continue; // 既に訪問済みなら探索しない
        rec(next, G, seen, order);
    }
    order.push_back(v);
}

void dfs(int v, int p, vector<bool> &seen, const Graph &G){
    seen[v] = true;
    ans[v] = p;
    for(auto nv : G[v]){
        if (seen[nv]) continue;
        dfs(nv, v, seen, G);
    }
}

int main(){
    int n, m;
    cin >> n >> m;
    
    Graph g(n), rev(n), g2(n);

    rep(i, n+m-1){
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        rev[b].push_back(a);
    }

    vector<bool> seen(n, 0); // 初期状態では全ノードが未訪問
    vector<int> order; // トポロジカルソート順
    for (int v = 0; v < n; ++v) {
        if (seen[v]) continue; // 既に訪問済みなら探索しない
        rec(v, g, seen, order);
    }
    reverse(order.begin(), order.end()); // 逆順に

    rep(i, n) pos[order[i]] = i;

    int p;

    rep(i, n){
        if (rev[i].size() == 0){
            p = i;
            continue;
        }
        int tmp = 0;
        for(auto from : rev[i]){
            tmp = max(pos[from], tmp);
        }
        for(auto from : rev[i]){
            if (pos[from] == tmp){
                g2[from].push_back(i);
                break;
            }
        }
    }

    rep(i, n) seen[i] = 0;

    dfs(p, -1, seen, g2);

    rep(i, n) cout << ans[i] + 1 << endl;

    return 0;
}


Measured memory_bytes: 26876
use std::io::stdin;

fn main() {
    let mut c = String::new();
    let mut b = String::new();
    stdin().read_line(&mut c).unwrap();
    stdin().read_line(&mut b).unwrap();
    let c: Vec<isize> = c.trim().split_whitespace().flat_map(str::parse).collect();
    let b: Vec<isize> = b.trim().split_whitespace().flat_map(str::parse).collect();
    let (n, m, c) = (c[0], c[1], c[2]);

    println!("{}", (0..n).filter(|_| {
        let mut a = String::new();
        stdin().read_line(&mut a).unwrap();
        a.trim()
            .split_whitespace()
            .flat_map(str::parse::<isize>)
            .zip(b.iter())
            .map(|(aa, &bb)| aa * bb)
            .sum::<isize>() > -c
    }).count());
}


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

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

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

const int MAX = 2 * 1e3 + 5;
const int INF = 1e9;
const int MOD = 1e9 + 7;

int N, L[MAX];

int main(){
    cin >> N;
    rep(i, N) {
        cin >> L[i];
    }

    sort(L, L + N);

    int ans = 0;
    rep(i, N) {
        rep(j, i) {
            int a = L[j];
            int b = L[i];

            int r = lower_bound(L, L + N, a + b) - L;
            int l = i + 1;
            ans += max(0, r - l);
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(10000001)

N, M, Q = map(int, input().split())
a = []
b = []
c = []
d = []
for i in range(Q):
    abcd = list(map(int, input().split()))
    a.append(abcd[0])
    b.append(abcd[1])
    c.append(abcd[2])
    d.append(abcd[3])
A_max = 0
A = [1] * N
def DFS():
    global A_max
    d_sum = 0
    for i in range(Q):
        if A[b[i]-1] - A[a[i]-1] == c[i]:
            d_sum += d[i]
    A_max = max(A_max, d_sum)
    if A[0] == M:
        return
    elif A[N-1] != M:
        A[N-1] += 1
    else:
        tmp_index = N-1
        while True:
            tmp_index -= 1
            if A[tmp_index] != M:
                A[tmp_index:] = [A[tmp_index] + 1] * len(A[tmp_index:])
                break
    DFS()

DFS()
print(A_max)

Measured memory_bytes: 84312
#include <cstdio>

int n, nums[100];

long long data[100][21];
int dp[100][21];

long long search(int i, int v){
  if(dp[i][v]) return data[i][v];

  if (i == n-1){
    if (v == nums[n-1]) return 1;
    else return 0;
  }

  long long r;

  if(v-nums[i] < 0){
    r = search(i+1, v+nums[i]);
  }else if(v+nums[i] > 20){
    r = search(i+1, v-nums[i]);
  }else{
    r = search(i+1, v+nums[i])+search(i+1, v-nums[i]);
  }
  
  dp[i][v] = 1;
  return data[i][v] = r;
}

main(){
  scanf("%d",&n);
  for(int i=0;i<n;i++){
    scanf("%d", nums+i);
  }

  for(int i=0;i<100;i++) for(int j=0;j<21;j++) dp[i][j] = 0;

  printf("%lld\n", search(1,nums[0]));
 }
  

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
const in mdl=1000000007LL;
VVI psm,ppw,vl;
in n,c;
VI a,b;
VVI ts;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  psm.resize(409,VI(409));
  ppw=vl=psm;
  forv(i,psm){
    ppw[i][0]=1;
    for(in j=1;j<sz(psm[i]);++j){
      ppw[i][j]=ppw[i][j-1]*i%mdl;
    }
  }
  forv(i,psm){
    psm[i][0]=0;
    for(in j=1;j<sz(psm[i]);++j){
      psm[i][j]=(psm[i][j-1]+ppw[j][i])%mdl;
    }
  }
  cin>>n>>c;
  a.resize(n);
  b.resize(n);
  forn(i,n)
    cin>>a[i];
  forn(i,n)
    cin>>b[i];
  forn(i,n){
    forv(j,vl[i]){
      vl[i][j]=psm[j][b[i]]-psm[j][a[i]-1];
      if(vl[i][j]<0)
	vl[i][j]+=mdl;
    }
  }
  ts.resize(n+1,VI(c+1,0));
  ts[0][0]=1;
  forn(i,n){
    forn(o,c+1){
      forn(ad,c+1-o){
	ts[i+1][o+ad]+=ts[i][o]*vl[i][ad]%mdl;
      }
    }
    forn(o,c+1)
      ts[i+1][o]%=mdl;
  }
  cout<<ts[n][c]<<endl;
  return 0;
}


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

n = int(input())
a_list = list(map(int, input().split()))

s = 0
summation = 0
for i in a_list:
  s += i

for i in a_list:
  s -= i
  summation += i * (s)

print(summation % (10 ** 9 + 7))

Measured memory_bytes: 31600
#include <iostream>

using namespace std;


int main() {
    int a, b;
    while (true) {
        cin >> a >> b;
        if (a == 0 & b ==0) {
            break;
        } else {
            for (int i=0; i<a; i++) {
                for (int j=0; j<b; j++) {
                    cout << "#";
                }
                cout<<endl;
            }
            cout << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 3092
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = s; i < (int)(n); i++)
#define Clear(a) a = decltype(a)();
typedef long long ll;
typedef pair<int,int> p;
//const ll big=998244353;
const ll big=1000000007;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
ll max(ll x,ll y){
if(x>y)return x;
else return y;
}
ll min(ll x,ll y){
if(x<y)return x;
else return y;
}
ll expm(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||x==0)return x;
    if(y%2==1)return (expm(x,y-1)*x)%big;
    ll t=expm(x,y/2);
    return (t*t)%big;
}
ll exp(ll x,ll y){
    if(y==0)return 1;//0^0=1
    if(x==1||y==0)return x;
    if(y%2==1)return exp(x,y-1)*x;
    ll t=exp(x,y/2);
    return t*t;
}
ll inv(ll x){
    return expm(x,big-2);
}

ll com(ll x,ll y){
    if(y<0||y>x)return 0;
    ll ans=1;
    rep(i,y){
        ans*=(x-i);
        ans%=big;
    }
    rep(i,y){
        ans*=inv(i+1);
        ans%=big;
    }
    return (ans+big+1-1)%big;
}

int main(){
    ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cout << fixed << setprecision(0);
    /*--------------------------------*/
    
    int x,y;cin >> x >> y;
    if((x+y)%3!=0){
        cout << 0 << endl;
        return 0;
    }
    //C(3,2)=3...
    cout << com((x+y)/3,x-(x+y)/3) << endl;
}

Measured memory_bytes: 3648
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <set>
#include <cmath>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <numeric>
#include <sstream>

#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())

using namespace std;
typedef long long ll;

int main() {
#ifdef RUN_LOCAL
  ifstream in("../input.txt");
  cin.rdbuf(in.rdbuf());
#endif

  cin.tie(0);
  ios::sync_with_stdio(false);

  unsigned long long a = 100;
  unsigned long long x;
  cin >> x;
  unsigned long long cnt = 0;
  while (a < x)
  {
    a = a + a / 100;
    ++cnt;
  }

  cout << cnt << endl;


  return 0;
}


Measured memory_bytes: 3164
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(a) ((a) & -(a))
#define clean(a, b) memset(a, b, sizeof(a))
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
const int maxn = 2e5 + 9;

int _;

//========================================================================
int a[maxn];
//========================================================================
int main()
{
    int n,last=0;
    ll ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        if(i==1) 
        {
            last=a[i];
            continue;
        }
        if(a[i]>last) 
        {
            last=a[i];
        }
        else if(a[i]<last) 
        {
            ans+=last-a[i];
        }
    }
    printf("%lld\n",ans);
    return 0;
}



Measured memory_bytes: 4532
#include "bits/stdc++.h"
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
#include <queue>
#include <set>
#include <tuple>
using namespace std;

#define FOR(i,init,a) for(int i=init; i<a; i++)
#define rep(i,a) FOR(i,0,a)
#define rrep(i,a) for(int i=a; i>=0; i--)
#define rep1(i,a) for(int i=1; i<=a; i++)
#define cout1(a) cout << a << endl;
#define cout2(a,b) cout << a << " " << b << endl;
#define cout3(a,b,c) cout << a << " " << b << " " << c << endl;
#define cout4(a,b,c,d) cout << a << " " << b << " " << c << " " << d << endl;
#define mem(a,n) memset( a, n, sizeof(a))
#define all(a) a.begin(),a.end()
#define chmin(a,b) a=min(a,b);
#define chmax(a,b) a=max(a,b);

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> V;
typedef vector<V> VV;
typedef vector<VV> VVV;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LLINF = 1e18;
static const double pi = 3.141592653589793;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll N,P;
    cin>>N>>P;
    if(N==1){
        cout1(P)
        return 0;
    }
    
    map<ll,ll> dic;
    for(ll i=2;i*i<=P;i++){
        while(P%i==0){
            dic[i]++;
            P/=i;
        }
    }
    if(P>1) dic[P]++;
    ll ans=1;
    for(auto a:dic){
        
        while(a.second>=N){
            ans*=a.first;
            a.second-=N;
        }
    }
    cout1(ans)
}

Measured memory_bytes: 256
n = 2 * (10**6) + 10
mod = 10 ** 9 + 7
fact = [1]*(n+1)
rfact = [1]*(n+1)
r = 1
for i in range(1, n+1):
  fact[i] = r = r * i % mod
rfact[n] = r = pow(fact[n], mod-2, mod)
for i in range(n, 0, -1):
  rfact[i-1] = r = r * i % mod

# nPk (mod MOD) を求める
def perm(n, k):
  return fact[n] * rfact[n-k] % mod

# nCk (mod MOD) を求める
def comb(n, k):
  return fact[n] * rfact[k] * rfact[n-k] % mod

k = int(input())
s = input()

len_s = len(s)
ans = 0
for i in range(len_s,k+len_s+1):
    ans += (comb(i-1,len_s-1) * pow(25,i-len_s,mod) * pow(26,k+len_s-i,mod)) % mod
    ans %= mod
print(ans)

Measured memory_bytes: 117212
#include <stdio.h>

int main()
{
	int D, N, ans, step;
  	scanf("%d%d", &D, &N);
  	if (D == 2){
    	step = 10000; ans = 0;
      	for (int i = 0; i < N; i++){
        	ans += step;
          	if (ans % 1000000 == 0){
            	ans += step;
            }
        }
    } else if (D == 1){
    	step = 100; ans = 0;
      	for (int i = 0; i < N; i++){
        	ans += step;
          	if (ans % 10000 == 0){
            	ans += step;
            }
        }
    } else {
    	step = 1; ans = 0;
      	for (int i = 0; i < N; i++){
        	ans += step;
          	if (ans % 100 == 0){
            	ans += step;
            }
        }
    }
  	printf("%d", ans);
}

Measured memory_bytes: 128