akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> P;
typedef long long ll;
typedef long double ld;
const int inf=1e9+7;
const ll longinf=1LL<<60;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define F first
#define S second

const int mx=200010;
const ll mod=1e9+7;

 
int main(){
  ll n,m;
  cin >> n >> m;
  vector<P> v;
  rep(i,n){
    int a,b; cin >> a >> b;
    v.emplace_back(a,b);
  }
  sort(v.begin(),v.end());
  
  ll ans=0,cnt=0;
  while(m>0){
    if(m<=v[cnt].S){ans=v[cnt].F; break;}
    m -= v[cnt].S;
    cnt++;
  }


  cout << ans << endl; 
  return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#define llint long long 

using namespace std;

llint N, M;

bool check(llint n)
{
	llint need = (n - N) * 2;
	if(n <= N) need = 0;
	if(need > M) return false;
	
	if( (M - need) >= 2*n ) return true;
	return false;
}

int main(void)
{
	cin >> N >> M;
	
	llint lb = 0, ub = 100000000000000, mid;
	while(ub - lb > 1){
		mid = (lb + ub) / 2;
		if(check(mid)) lb = mid;
		else ub = mid;
	}
	
	cout << lb << endl;
	return 0;
}

Measured memory_bytes: 256
import sys

input = sys.stdin.readline


def main():
    N, T = map(int, input().split())
    t = list(map(int, input().split()))

    ans = T * N
    for i in range(N - 1):
        diff = t[i + 1] - t[i]
        if diff < T:
            ans -= T - diff

    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 26744
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cassert>
#include <climits>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <fstream>

using namespace std;
#define TOSTRING(x) #x
#define SZ(x) (int)(x).size()
#define REP(i,n) for(int i=0;i<(n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REPR(i,n) for(int i=(n)-1;i>=0;i--)
#define ALL(s) (s).begin(), (s).end()
#define so(V) sort(ALL(V))
#define rev(V) reverse(ALL(V))
#define uni(v) v.erase( unique(ALL(v)) , v.end());
#define PAU system("pause")

typedef long long unsigned int llu;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef vector<vb> vvb;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;
const int INF = (1 << 28);
const ll LINF = 1e18;
const double PI = acos(-1);

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N, M;
	cin >> N >> M;
	vi ball(N,1);
	vb red(N, false);
	red[0] = true;
	REP(i, M) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		if (red[x])red[y] = true;
		ball[x]--;
		ball[y]++;
		if (ball[x] == 0)red[x] = false;
	}
	int ans = 0;
	REP(i, N) {
		if (red[i])ans++;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void)
{
	int a,i;
	long long l[90];
	l[0]=2;
	l[1]=1;
	scanf("%d",&a);
	if(a>1){
		for(i=2;i<a+1;i++){
			l[i]=l[i-1]+l[i-2];
		}
	}
	printf("%lld",l[a]);
	return 0;
}

Measured memory_bytes: 128
#include <stdio.h>
#include <stdlib.h>

#define MIN(A,B) \
  ( (B) < (A) ? (B) : (A) )
#define INFTY 19980725
#define N 100

/** ルータの総数 */
static int n;
/** ネットワークの隣接行列 */
static int g[ N + 1 ][ N + 1 ] = { { 0 } };
/** パケットの個数 */
static int p;

int
main (
  int   argc,
  char *argv[ ]
  )
{
  int i, j, k;

  /* ルータの個数の読み込みと隣接行列の初期化 */
  scanf ( "%d", &n );
  for ( i = 1; i <= n; ++i )
  for ( j = 1; j <= n; ++j )
  {
    g[ i ][ j ] = ( i == j ? 0 : INFTY );
  }

  /* ネットワーク状態の読み込み */
  for ( i = 0; i < n; ++i )
  {
    int r, k;

    scanf ( "%d%d", &r, &k );
    for ( j = 0; j < k; ++j )
    {
      int t;

      scanf ( "%d", &t );
      g[ r ][ t ] = 1;
    }
  }

  /* ワーシャルフロイド法による最短経路の算出 */
  for ( k = 1; k <= n; ++k )
  for ( i = 1; i <= n; ++i )
  for ( j = 1; j <= n; ++j )
  {
    g[ i ][ j ] = MIN( g[ i ][ j ], g[ i ][ k ] + g[ k ][ j ] );
  }

  /* パケット情報の読み込みと処理 */
  scanf ( "%d", &p );
  for ( i = 0; i < p; ++i )
  {
    int s, d, v;

    scanf ( "%d%d%d", &s, &d, &v );
    if ( g[ s ][ d ] + 1 <= v )
    {
      printf ( "%d\n", g[ s ][ d ] + 1 );
    }
    else
    {
      puts ( "NA" );
    }
  }

  return ( EXIT_SUCCESS );
}

Measured memory_bytes: 652
n=int(input())
a=[int(i) for i in input().split()]
k,m=0,abs(a[0])
for i in range(1,n):
    if abs(a[i])>m:
        m=abs(a[i])
        k=i
print(2*n-1)
for i in range(n):
    print(k+1,i+1)
if a[k]>=0:
    for i in range(1,n):
        print(i,i+1)
else:
    for i in range(1,n):
        print(n+1-i,n+1-i-1)



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

using namespace std;

long long mod_pow(long long a,long long b,long long mod){
	long long res=1,c=a;
	while(b){
		if(b&1) res=res*c%mod;
		c=c*c%mod;
		b/=2;
	}
	return res;
}

long long inv(long long a,long long mod){
	long long b=mod,p=1,q=0;
	while(b){
		long long c=a/b,d=a;
		a=b;
		b=d%b;
		d=p;
		p=q;
		q=d-c*q;
	}
	return (p+mod)%mod;
}
int fs=505050;
vector<long long> fact(fs),ifact(fs);
long long binom(int a,int b,long long mod){
	if(a<b) return 0;
	return fact[a]*ifact[b]%mod*ifact[a-b]%mod;
}

vector<long long> conv(vector<long long> &a,vector<long long> &b,long long mod){
	int n=a.size()+b.size();
	n--;
	vector<long long> res(n);
	for(int i=0;i<a.size();i++){
		for(int j=0;j<b.size();j++){
			res[i+j]=(res[i+j]+a[i]*b[j]%mod)%mod;
		}
	}
	return res;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n,k;
	cin >> n >> k;
	vector<long long> a(k);
	for(int i=0;i<k;i++) cin >> a[i];
	
	long long mod=1000000007;
	
	fact[0]=1;
	for(int i=1;i<fs;i++) fact[i]=fact[i-1]*i%mod;
	ifact[fs-1]=inv(fact[fs-1],mod);
	for(int i=fs-1;i>0;i--) ifact[i-1]=ifact[i]*i%mod;
	
	long long res=0;
	vector<long long> cur(1,1);
	for(int i=0;i<k;i++){
		vector<long long> te(n+1);
		for(int j=0;j<=n;j++){
			if(a[i]<j) break;
			long long v=binom(n-j,a[i]-j,mod)*ifact[j]%mod;
			te[j]=v;
		}
		cur=conv(cur,te,mod);
		if(cur.size()>=(n+4)) cur.resize(n+4);
	}
	cout << cur[n]*fact[n]%mod << "\n";
	return 0;
}

Measured memory_bytes: 10240
n, x = map(int, input().split())
a = list(map(int, input().split()))
a_asc = sorted(a)
ans = 0
for i in range(n):
    x -= a_asc[i]
    if x >= 0:
        ans += 1
print(ans - 1 if x != 0 and x > 0 else ans)

Measured memory_bytes: 3060
line = gets.chomp.split(" ")

size = line[0].to_i
a = line[1].to_i
b = line[2].to_i
dist1 = b - (a + size)
dist2 = a - (b + size)

if dist1 >= 0 && dist2 < 0
    puts dist1
elsif dist1 < 0 && dist2 >= 0
    puts dist2
else
    puts 0
end


Measured memory_bytes: 3836
#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
 
#define ll long long
#define int long long
#define rep(i,a,b) for (int i = a; i < b; ++i)
#define mod 1000000007
typedef pair<ll,ll> pll;
#define F first
#define S second
#define printer(v) for(auto f: v) cout<<f<<" "
#define pb push_back
#define mp make_pair
#define all(c) c.begin(), c.end()
#define ipair pair<int,int>
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL); 
    // cout << setprecision(12) << fixed;
    int x; cin>>x;
    for(int a=-1000; a<=1000; a++){
    	for(int b=-1000; b<=1000; b++){
    		if(pow(a,5)-pow(b,5)==x){
    			cout<<a<<" "<<b<<endl; return 0;
    		}
		}
    }
    return 0;
}

Measured memory_bytes: 4076
#include<bits/stdc++.h>
#define ll long long
#define f(a,b) for(int i=a;i<b;i++)
#define nitro cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define mod 1000000007
#define m 100007
using namespace std;
int dp[100005];
ll solve(int arr[],int n,int idx,int k)
{
    if(dp[idx]!=-1)
        return dp[idx];
    if(idx==n-1)
        return dp[idx]=0;
    if(idx>=n)
        return dp[idx]=INT_MAX;
    ll min_step=INT_MAX;
    for(int i=1;i<=k;i++)
        min_step=min(min_step,abs(arr[idx]-arr[idx+i])+solve(arr,n,idx+i,k));
    ll ans=0;
    ans+=min_step;
    return dp[idx]=ans;
}

int main()
{
    int n,k;
    cin>>n>>k;
    int arr[n];
    memset(dp,-1,sizeof(dp));
    for(int i=0;i<n;i++)
        cin>>arr[i];
    cout<<solve(arr,n,0,k)<<endl;
}


Measured memory_bytes: 15216
# C - Reconciled?

import math

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

b = 10**9 + 7

if abs(N-M) >= 2:
    print(0)
elif N == M:
    print((((math.factorial(N) % b) * (math.factorial(M) % b) % b) * 2) % b)
else:
    print((((math.factorial(N) % b) * (math.factorial(M) % b) % b)))

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

long long dp[150][101000];

int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
      
    long long n,k;
    cin>>n>>k;
    long long a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    long long mod=1e9+7;
    for(int i=0;i<=a[0];i++) dp[0][i]=1;
    for(int i=1;i<n;i++)for(int j=0;j<=k;j++){
        dp[i][j]=dp[i-1][j];
        if(j) dp[i][j]+=dp[i][j-1];
        if(j-a[i]>0) dp[i][j]+=mod-dp[i-1][j-a[i]-1];
        dp[i][j]%=mod;
    }
    cout<<dp[n-1][k]%mod<<endl;
}

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

int main(){
	int n, temp;
	cin >> n;
	vector<int> a(n,1e9), result(n,0);
	cin >> temp;
	a[0] = temp;
	a[1] = temp;
	for(int i=1;i<n-1;i++){
		cin >> temp;
		//result[i-1] = min(a[i-1],temp);
		a[i] = min(a[i], temp);
		a[i+1] = min(a[i+1],temp);
	}
	int sum = 0;
	for(int x: a){
		sum+= x;
	}
	cout << sum;
}


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

using namespace std;

int main()
{
    int k,n,a;
    vector <int> prices;
    cin >> n;
    if(1>n || n > 1000)
        return 0;
    cin >> k;
    if(1>k || k>1000)
        return 0;
    for(int i=0;i<n;i++){
        cin >> a;
        if(1>a || a>1000)
            return 0;
        prices.push_back(a);

    }
    int minindex=0,total=0;
    for(int i=0;i<k;i++){
        total = total + *min_element(prices.begin(),prices.end());
        minindex = min_element(prices.begin(),prices.end()) - prices.begin();
        prices[minindex] = 10001;
    }
    cout << total;
    return 0;
}


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

#define pb push_back
#define mp make_pair
#define X first
#define Y second
#define ll long long
#define pii pair<int, int>
#define is insert
#define er erase

using namespace std;

int solve();

#define TASK ""

int main()
{
    #ifdef DEBUG
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #else
        //freopen(TASK".in", "r", stdin);
        //freopen(TASK".out", "w", stdout);
    #endif // DEBUG
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}

ll K;
ll A;
ll B;

ll ans = 0;

int solve()
{
    cin >> K >> A >> B;
    if (B <= A + 2)
    {
        cout << 1 + K << '\n';
        return 0;
    }
    else
    {
        ll need = A - 1;
        if (need > K)
        {
            cout << 1 + K << '\n';
            return 0;
        }
        ans = A;
        K -= need;
        ans += (B - A) * (K / 2);
        K %= 2;
        ans += K;
        cout << ans << '\n';
    }
    return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
#define INF 1000000010
#define EPS 1e-9
#define F first
#define S second

#define debug(x) cout<<x<<endl;
#define repi(i,x,n) for(int i=x;i<n;i++)
#define rep(i,n) repi(i,0,n)
#define lp(i,n) repi(i,0,n)
#define repn(i,n) for(int i=n;i>=0;i--)
#define int long long
#define endl "\n"

typedef pair<int,int> PII;
typedef pair<int,string> PIS;
typedef pair<string,int> PSI;


signed main(){
  cin.tie(0);	
  ios::sync_with_stdio(false);
  int n,m;
  cin>>n>>m;
  int a=n*(n-1);
  a/=2;
  int b=m*(m-1);
  b/=2;
  cout<<a+b<<endl;

  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <algorithm>
#include <string>

using namespace std;
typedef long long ll;

int main(int argc, char *argv[]) {
  int a,b,c,x,y;
  cin>>a>>b>>c>>x>>y;
  int ans = 1000000000;
  int mx = max(x, y);
  for (int i = 0; i <= mx; i++) {
    int tx = max(x - i, 0) * a;
    int ty = max(y - i, 0) * b;
    int tc = i * 2 * c;
    ans = min(ans, tx + ty + tc);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
 string s;
  cin>>s;
  for(int i=1;i<4;i++){
    if(s[i]==s[i-1]){
     cout<<"Bad";
     return 0;
    }
  }
  cout<<"Good";
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<string.h>
#include<algorithm>
#define FOR(i,l,r) for(int i = l; i <= r; i++)
using namespace std;

const int MAXN = 100100;

int f[MAXN],l[MAXN],r[MAXN],q[MAXN];
int n;

int calc(int rt){
  f[rt] = 0;
  int tail = 0;

  for(int son = l[rt]; son > 0; son = r[son])
    calc(son);

  for(int son = l[rt]; son > 0; son = r[son])
    q[++tail] = f[son];

  if(tail>0){
    sort(q+1,q+tail+1);
    FOR(i,1,tail) q[i]+=(tail-i+1);
    FOR(i,1,tail) if(q[i]>f[rt]) f[rt] = q[i];
  }
  return f[rt];
}

int main(){
  cin >> n;
  FOR(i,1,n) l[i] = 0;
  FOR(i,1,n) r[i] = 0;
  FOR(i,2,n){
    int fa;
    scanf("%d",&fa);
    r[i] = l[fa];
    l[fa] = i;
  }
  cout << calc(1);
  return 0;
}


Measured memory_bytes: 6144
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long lint;
const int N=1000011;
const lint mo=998244353;
lint fac[N],inv[N];
int n,m;
lint C(int n,int m)
{
	if(n<m||n<0||m<0) return 0;
	return fac[n]*inv[m]%mo*inv[n-m]%mo;
}
lint ans;
lint pow(lint b,lint p)
{
	lint ret=1;
	while(p)
	{
		if(p&1ll) ret=ret*b%mo;
		b=b*b%mo;
		p>>=1;
	}
	return ret;
}

signed main()
{
//	freopen("yesorno.in","r",stdin);
//	freopen("yesorno.out","w",stdout);
	fac[0]=fac[1]=inv[0]=inv[1]=1;
	for(int i=2;i<=1000000;i++)
	{
		fac[i]=fac[i-1]*i%mo;
		inv[i]=inv[mo%i]*(mo-mo/i)%mo;
	}
	for(int i=2;i<=1000000;i++) inv[i]=inv[i-1]*inv[i]%mo;
	scanf("%d%d",&n,&m);
	if(n<m)swap(n,m);
	for(int i=1;i<=m;i++) (ans+=C(i*2,i)*C(n-i+m-i,n-i)%mo)%=mo;
	(ans*=inv[2]*pow(C(n+m,m),mo-2)%mo)%=mo;
	(ans+=n)%=mo;
	printf("%lld\n",ans);
}

Measured memory_bytes: 15872
#include <iostream>
#include <cmath>
#include <math.h>
#include <map>
#include <vector>
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <algorithm>
#include <string>
using namespace std;

int main() {
    int N, K;
    cin >> N >> K;
    vector<char> S(N);
    for (int i = 0; i < N; i++) {
        cin >> S.at(i);
    }
    
    S.at(K - 1) = tolower(S.at(K - 1));

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

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

using namespace std;

int main()
{
    long long n, i, aux=0, k, r;
    cin >> n >> k;
    for (i=0; i<n; i++)
    {
        cin >> r;
        aux=aux+2*min(r, abs(k-r));
    }
    cout << aux << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int x, f=0, a, y;
    
    scanf("%d",&x);
    
    y=x;
    while(1){
        f+=y%10;
        y=y/10;
        if(y==0) break;
    }
    
    a=x%f;
    if(a==0) printf("Yes\n");
    else     printf("No\n");
    return 0;
}

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

using namespace std;

#define FOR(i, j, k) for(int i = j; i < k; ++i)
#define rep(i, j) FOR(i, 0, j)
#define repr(i, j) for(int i = j; i >= 0; --i)
#define INF (1 << 30)
#define MOD 1e9 + 7

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

int num[5000];

int main() {
	int N;
	while(scanf("%d", &N), N) {
		memset(num, 0, sizeof(num));
		int ans = 0;
		rep(i, N) {
			scanf("%d", &num[i]);
			ans += num[i];
		}
		rep(i, N) {
			int sum = 0;
			FOR(j, i, N) {
				sum += num[j];
				ans = max(ans, sum);
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}

Measured memory_bytes: 3156
#include <bits/stdc++.h>
#define rep( i, n ) for (long long i = 0; i < ( long long )(n); i++)

using namespace std;
typedef long long ll;
typedef pair< int , int > P;

int main(){
  const int a[]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
  int k;
  cin>>k;
  cout<<a[k-1];
}

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

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

  int n[3];
  int M = N;
  for (int i=0; i<3; ++i) {
    n[2-i] = M % 10;
    M /= 10;
  }

  int ans = 111 * n[0] >= N ? 111 * n[0] : 111 * (n[0] + 1);
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main() {
    int N, x = 0, max = 0;
    char S;
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> S;
        x += S == 'I' ? 1 : -1;
        if (x > max) max = x;
    }
    cout << max << endl;
}

Measured memory_bytes: 256
n,t = map(int, input().split())
ct = [list(map(int, input().split())) for _ in range(n)]
ct.sort()
#print(ct)
ck =0
for i in range(n):
    if ct[i][1]<=t:
        ck =1
        break
if ck ==1:
    print(ct[i][0])
    exit()
print('TLE')

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

using namespace std;

#define JAM(x) cout << #x << " = " << x << "\n"
#define II() ({ int a ; read(a) ; a; })
#define LL() ({ ll a ; read(a) ; a; })
#define DD() ({double a; scanf("%lf", &a); a; })

//Fast Reader
template <class T>
inline bool read(T &x)
{
    int c = getchar();
    int sgn = 1;
    while (~c && c < '0' || c > '9')
    {
        if (c == '-')
            sgn = -1;
        c = getchar();
    }
    for (x = 0; ~c && '0' <= c && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
    x *= sgn;
    return ~c;
}

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef pair<int, int> PII;
typedef vector<PII> VPI;

const int INF = 2e9;
const int MX = 100005;
const int MOD = 1000000007;
const double PI = acos(-1.0);



long long int power(long long int a, long long int b)
{
    a %= MOD;
    long long int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}
bool isprime(int n)
{
    if (n == 1)
        return false;
    for (int i = 2; i * i <= n; i++)
    {
        if (n % i == 0)
            return false;
    }
    return true;
}

/*_______________________________________________*/



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long int n,i,j;
    cin>>n;
    vector<long long >dp(n+1);
    dp[0]=dp[1]=dp[2]=0;
    for(i=3;i<=n;i++)
    dp[i]=1;
    for(i=6;i<=n;i++)
    {
        for(j=3;j<=i-3;j++)
        {
            dp[i]=(dp[i]+dp[i-j])%MOD;
        }
    }
    cout<<dp[n];
}

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

double get_c(double a, double b){
  // a: water, b: sugar
  if(a == 0 && b == 0){
    return 0;
  }
  return 100 * b / (a + b);
}

int main(){
  // std::ifstream in("input.txt");
  // std::cin.rdbuf(in.rdbuf());
  
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E >> F;

  int maxc_water=0;
  int maxc_sugar=0;
  double maxc=0;
  for(int op1=0; op1<=F/(100*A); op1++){
    for(int op2=0; op2<=F/(100*B); op2++){
      for(int op3=0; op3<=F/C; op3++){
        for(int op4=0; op4<=F/D; op4++){
          int total_water = op1 * 100 * A + op2 * 100 * B;
          int total_sugar = op3 * C + op4 * D;

          double max_sugar = E/100.0 * total_water;
          if(max_sugar >= total_sugar && total_water + total_sugar <= F){
            // 溶けきる
            if(maxc <= get_c(total_water, total_sugar)){
              maxc = get_c(total_water, total_sugar);
              maxc_water = total_water;
              maxc_sugar = total_sugar;
            }
          }
        }
      }
    }
  }

  cout << maxc_water + maxc_sugar << ' ' << maxc_sugar << endl;

  return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#include <numeric>
typedef long long Int;
#define rep(i,a,b) for(Int i=a;i<b;++i)
#define rrep(i,a,b) for(Int i=a;i>=b;--i)
using namespace std;

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

    Int N; cin >> N;
    vector<Int> a(N);
    rep(i, 0, N) cin >> a[i];

    Int mina = *min_element(a.begin(), a.end());
    Int maxa = *max_element(a.begin(), a.end());

    Int res = LLONG_MAX;
    for(Int goal = mina; goal <= maxa; ++goal) {
        Int cost = 0;
        rep(i, 0, N) {
            cost += (goal-a[i]) * (goal-a[i]);
        }
        res = min(res, cost);
    }

    cout << res << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
//cout << setprecision(20) << 

int main() {
    ll h, w; cin >> h >> w;
    vector<string> board(h);
    map<int, int> h_whites;
    map<int, int> w_whites;
    for (int i = 0; i < h; ++i) {
        cin >> board[i];
        bool flag = true;
        for (int j = 0; j < w; ++j) {
            if (board[i][j] != '.') {
                flag = false;
                break;
            }
        }
        if (flag) h_whites[i] = 1;
    }
    for (int j = 0; j < w; ++j) {
        bool flag = true;
        for (int i = 0; i < h; ++i) {
            if (board[i][j] != '.') {
                flag = false;
                break;
            }
        }
        if (flag) w_whites[j] = 1;
    }

    // output
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            if (h_whites.count(i) || w_whites.count(j)) continue;
            cout << board[i][j];
        }
        if (!h_whites.count(i)) {
            cout << endl;
        }
    }
}

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

int t;
string s;
priority_queue<int>pq;

int main() {
    ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while (1) {
        cin>>s;
        if (s=="end") break;
        if (s=="extract") cout<<pq.top()<<'\n', pq.pop();
        else cin>>t, pq.push(t);
    }
}


Measured memory_bytes: 7012
#include<bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define pii pair<ll,ll>
#define F first
#define S second
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(ll i=a;i<=(ll)b;++i)
#define per(i,a,b) for(ll i=a;i>=(ll)b;--i)
#define ll long long
#define lowbit(x) ((x)&(-x))

bool ok(string s)
{
    int len=s.size();
    for(int i=0,j=len-1;i<j;++i,--j)
    {
        if(s[i]!=s[j]) return false;
    }
    return true;
}
int main()
{
    IOS
    double n; cin>>n;
    cout<<fixed<<setprecision(10);
    double ans=(n/3)*(n/3)*(n/3);
    cout<<ans<<"\n";
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i <= n; i++)
#define FORR(i, m, n) for(int i = m; i >= n; i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define VSORTR(v) sort(v.rbegin(), v.rend());
#define ALL(v) (v).begin(),(v).end()
 
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using P = pair<ll, ll>;

const ll MOD = 1e9 + 7;
// return a^b O(log b)
template<typename T>
T mypow(T a, T b){
    if (b == 0)
        return 1;
    T tmp = mypow(a, b / 2);
    if (b % 2)
        return (((tmp * tmp) % MOD) * a) % MOD;
    else
        return (tmp * tmp) % MOD;
}
// return nCk 前処理 O(N) + query あたり O(1)
static bool init = false;
const ll mmm = 4e5 + 10;
vector<ll> frc(mmm + 1, 1), inv(mmm + 1, 1);
long long comb(int n, int k){
	long long res = 1;
	if(!init){
		init = true;
		REP(i, mmm){
			frc[i + 1] = (frc[i] * (i + 1)) % MOD;
			inv[i + 1] = mypow(frc[i + 1], MOD - 2);
		}
	}
	if (k < 0 || n < k) return 0;
	res = (((frc[n] * inv[k]) % MOD) * inv[n - k]) % MOD;
    return res;
}

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

    ll n, k;
    cin >> n >> k;

    if (k >= n - 1) {
        ll res = comb(2 * n - 1, n - 1);
        cout << res << endl;
        return 0;
    }
    ll res = (1 + n * (n - 1)) % MOD; // 初期状態

    for (ll emp = 2; emp <= k; emp++) {
        // 0 人の部屋が emp コの組み合わせが新たに選べる
        ll x = n - emp;
        ll tmp = (comb(emp + (x - 1), x - 1) * comb(n, emp)) % MOD;
        res += tmp;
        res %= MOD;
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 6528
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const int inf = INT_MAX;
const ll INF = LLONG_MAX;
const ll MOD = 1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b, const ll mod=MOD) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b, const ll mod=MOD) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b, const ll mod=MOD) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b, const ll mod=MOD) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
int h, w, K;
vector<string> f;
vi used;

int calc(int k){
    int ret = __builtin_popcount(k);
    vi cnt(ret + 1);
    vi d(ret + 1);
    rep(j, w){
        fill(_all(d), 0);

        int di = 0;
        rep(i, h){
            if(f[i][j] == '1'){
                d[di]++;
            }
            if((k >> i) & 1){
                di++;
            }
        }
        bool update = false;
        rep(i, di + 1){
            if(d[i] > K) return inf;
            update |= (cnt[i] + d[i] > K);
        }
        if(update) ret++;
        rep(i, di + 1){
            cnt[i] = (update ? 0 : cnt[i]) + d[i];
        }
    }
    return ret;
}

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

    cin >> h >> w >> K;
    f.resize(h); for(auto& e : f) cin >> e;

    int res = inf;
    rep(k, bit(h - 1)){
        rep(_, 2){
            chmin(res, calc(k));
            rep(i, h) reverse(_all(f[i]));
        }
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
int main(){
  int n,k,ans;
  cin>>n>>k;
  ans=n;
  vector<int> a(n),b(n+1,0);
  priority_queue<int, vector<int>, greater<int> > que;
  rep(i,n){
    cin>>a[i];
    b[a[i]]++;
  }
  sort(b.rbegin(),b.rend());
  rep(i,k){
    ans-=b[i];
  }
  cout<<ans;
}

Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;

template <typename TYPE>
void print_vec(const vector<TYPE>& v){
	for(int i=0; i<v.size(); i++){
		cout << v[i] << " ";
	}
	cout << endl;
}

template <typename TYPE>
void print_vec2(const vector<vector<TYPE>>& v){
  cout << endl;
  for(int i=0; i<v[0].size(); i++) cout << i << "   "; 
  cout << endl;
	for(int i=0; i<v.size(); i++){
		cout << "i=" << i << ":   " << endl;
		for(int j=0; j<v[i].size(); j++){
			if(v[i][j] == 0) cout << "\x1B[0m" << v[i][j] << "   ";
      else cout << "\x1B[31m" << v[i][j] << "   ";//https://stackoverrun.com/ja/q/12618775
		}
		cout << "\x1B[0m" << endl;
	}
}
 
int main(){
  int D;
  cin >> D;
  vector<int> c(26, 0);
  for(int i=0; i<26; i++) cin >> c[i];
  vector<vector<int>> s(D, vector<int>(26, 0));
  for(int i=0; i<D; i++){
    for(int j=0; j<26; j++){
      cin >> s[i][j];
    }
  }


  int type = 0;
  vector<int> last(26, -1);
  for(int d=0; d<D; d++){
    
    ll score = 0;// d日目のみで得られるスコア
    for(int j=0; j<26; j++){
      vector<int>  saigo = last;
      ll get = s[d][j];
      saigo[j] = d;
      for(int k=0; k<26; k++){
        get -= c[k] * (d-saigo[k]);
      }
      if(get > score) type = j;      
    }

    last[type] = d;    
    cout << type + 1 << endl;
  }

  // B問題 　ローカル確認用
  // vector<int> t(D);
  // for(int i=0; i<D; i++){
  //   cin >> t[i];
  //   t[i]--;
  // }
  // // cout << " c: " ; print_vec(c);
  // // //cout << " s: " << endl; print_vec2(s);
  // // cout << " t: " ; print_vec(t);
  // //vector<vector<int>> last(D, vector<int>(26, 0));
  // vector<int> last(26, -1);
  // ll score = 0;
  // for(int d=0; d<D; d++){
  //   int type = t[d];
  //   score += s[d][type];
  //   last[type] = d;
  
    
  //   for(int i=0; i<26; i++){
  //     score = score - c[i] * (d - last[i]);
  //     //cout << " d: " << d << " i: " << i << " c[]: " << c[type] << " score: " << score << endl;
  //   }
  //   //cout << " c[3]: " << c[3] << " (d - last[3]): "<< (d - last[3]) << "  c[3] * (d - last[3]): " << c[3] * (d - last[3]) << endl;
  //   cout << score << endl;
  // }

    
}


Measured memory_bytes: 3656
#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#define rep(i,j,k) for(register int i = j; i <= k; i++)
#define dow(i,j,k) for(register int i = j; i >= k; i--)
#define ll long long
using namespace std;

inline int read() { 
	int s = 0, t = 1; char c = getchar();
	while( !isdigit(c) ) { if( c == '-' ) t = -1; c = getchar(); }
	while( isdigit(c) ) s = s * 10 + c - 48, c = getchar();
	return s * t;
} 

int n, sv, v, l, r, mid;
char c[10];
inline int get() { 
	scanf("%s",c+1);
	if( c[1] == 'V' ) exit(0);
	else if( c[1] == 'M' ) return 0;
	else return 1;
}

int main() { 
	n = read();
	printf("%d\n",0);
	fflush(stdout);
	sv = get();
	
	l = 1, r = n - 1;
	while( 1 ) { 
		mid = (l + r) >> 1;
		printf("%d\n",mid);
		fflush(stdout);
		v = get();
		
		if( mid & 1 ) { 
			if( v != sv ) { 
				l = mid + 1;
			} else r = mid - 1;
		} else { 
			if( v == sv ) { 
				l = mid + 1;
			} else r = mid - 1;
		}
	}	
	return 0;
}

Measured memory_bytes: 852
X, N = map(int, input().split())
p = list(map(int, input().split()))

if N ==0 or X < min(p) or X > max(p):
    print(X)
else:
    for n in range(N+1):
        if not X - n in p:
            print(X - n)
            break
        elif not X + n in p:
            print(X + n)
            break

Measured memory_bytes: 9092
#include<cstdio>
#include<iostream>
#include<string>
#include <algorithm>
#include<vector>
#include<queue>
using namespace std;
using ll = long long;

ll a[10000];
int main(){
	int N, M, X;
	cin >> N >> M >> X;
	for (int i = 0; i < M; i++) {
		cin >> a[i];
	}

	int r = 0, l = 0;
	for (int i = 0; i < M; i++ ) {
		if (a[i] > X) {
			r++;
		}
		else {
			l++;
		}
	}
	cout << min(r, l) << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;

typedef long long Int;
typedef pair<Int,Int> P;
#define print(x) cout<<(x)<<endl

#define INF10 10000000000
#define INF5 100000
#define EPS 1e-10
#define MOD 1000000007


struct masu {
	char clr;
	bool have_been = false;
};

struct pir {
	Int black;
	Int white;
};

vector<struct masu> S[410];

struct pir explore(Int i,Int j, Int H, Int W) {
	S[i][j].have_been = true;
	struct pir out = { 0,0 };
	if (i > 0 && S[i - 1][j].have_been == false && S[i-1][j].clr != S[i][j].clr) {
		struct pir tmp = explore(i - 1, j, H, W);
		out.black += tmp.black;
		out.white += tmp.white;
	}
	if (H-1 >i && S[i + 1][j].have_been == false&& S[i+1][j].clr != S[i][j].clr) {
		struct pir tmp = explore(i + 1, j, H, W);
		out.black += tmp.black;
		out.white += tmp.white;
	}
	if (j > 0 && S[i][j - 1].have_been == false&& S[i][j-1].clr != S[i][j].clr) {
		struct pir tmp = explore(i, j-1, H, W);
		out.black += tmp.black;
		out.white += tmp.white;
	}
	if (W-1 > j  && S[i][j + 1].have_been == false&& S[i][j+1].clr != S[i][j].clr) {
		struct pir tmp = explore(i, j+1, H, W);
		out.black += tmp.black;
		out.white += tmp.white;
	}
	if (S[i][j].clr == '#')out.black += 1;
	else out.white += 1;
	return out;
}


int main() {
	Int H, W; cin >> H >> W;
	for (Int i = 0; i < H; i++) {
		string ipt;
		cin >> ipt;
		for (Int j = 0; j < W; j++) {
			struct masu iptmasu = { ipt[j],false };
			S[i].push_back(iptmasu);
		}
	}



	Int score = 0;
	for (Int i = 0; i < H; i++) {
		for (Int j = 0; j < W; j++) {
			if (S[i][j].have_been == false) {
				struct pir tmp;
				tmp = explore(i, j, H, W);
				score += tmp.black*tmp.white;
			}
		}
	}
	print(score);



	



	return 0;
}

Measured memory_bytes: 13184
#include <stdio.h>
#include <stdlib.h>

int main(){
  int a,b,c;
  while(a<1||a>9){
    scanf("%d",&a);
  }
  while(b<1||b>9){
    scanf("%d",&b);
  } 
  while(c<1||c>9){
    scanf("%d",&c);
  }
  if(a==b && b==c){
    printf("No");
  }
  else if(a!=b && b!=c && a!=c){
    printf("No");
  }
  else printf("Yes");
  return 0;
}


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

#define ll long long
#define f(i,a,n) for (int i=a;i<n;i++)
typedef pair<ll, ll> pa;
const ll mod=1000000007;
int main(int argc, char const *argv[])
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    ll a, b;
    cin >> a >> b;
    ll s = 1, ans = 0;
    while (s < b) {
        s += a - 1;
        ans++;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <set>
#include <stack>
#include <stdlib.h>
#include <string>
#include <vector>

#define el endl
#define fd fixed
#define INF INT_MAX/2-1
#define pb push_back

using namespace std;

class Record
{
public:
  int t;
  int n;
  int m;
  int s;
};

int main() {
  int N, M, r, t, n, m, s, q, st, et, st_tmp;
  while (cin >> N >> M, N | M) {
    cin >> r;
    Record records[r];
    for (int i = 0; i < r; i++) {
      cin >> t >> n >> m >> s;
      records[i].t = t;
      records[i].n = n;
      records[i].m = m;
      records[i].s = s;
    }
    cin >> q;
    while (q--) {
      cin >> st >> et >> m;
      int i = 0, cnt = 0, ut = 0;
      for (int time = 540; time <= 1260; time++) {
        if (records[i].t == time) {
          if (records[i].m == m) {
            if (records[i].s) {
              if (cnt == 0) {
                if (time < st) {
                  st_tmp = st;
                } else {
                  st_tmp = time;
                }
              }
              cnt++;
            } else {
              cnt--;
              if (cnt == 0) {
                if (time > st) {
                  ut += time - st_tmp;
                } else {
                  st_tmp = 0;
                }
              }
            }
          }
          i++;
          time--;
        }
        if (time == et) {
          if (cnt > 0) {
            ut += et-st_tmp;
          }
          break;
        }
      }
      cout << ut << el;
    }
  }
}

Measured memory_bytes: 1172
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author houghstc
 */

#include <iostream>
#include <fstream>

#include <iostream>
#include <vector>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
#include <cstring>
#include <climits>

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

const int MOD = 1e9+7;

const int N = 1010;
char grid[N][N];
bool solved[N][N];
int d[N][N];
int h, w, ch, cw, dh, dw;

class DWizardInMaze {
public:
    void solve(std::istream& in, std::ostream& out) {
        in >> h >> w >> ch >> cw >> dh >> dw;
        for(int i = 1; i <= h; ++i) {
            for (int j = 1; j <= w; ++j) {
                in >> grid[i][j];
                solved[i][j] = false;
                d[i][j] = 1e9;
            }
        }

        deque<pii> dq;
        dq.push_back({ch, cw});
        d[ch][cw] = 0;

        while(dq.size())
        {
            auto [x, y] = dq.front();
            dq.pop_front();
            if(solved[x][y]) continue;
            solved[x][y] = true;
            if(x == dh && y == dw)
            {
                out << d[x][y] << endl;
                return;
            }
            //cout << "x: " << x << ", y: " << y << endl;
            for(int i = x-2; i <= x+2; ++i)
            {
                for(int j = y-2; j <= y+2; ++j)
                {
                    if(i >= 1 && i <= h && j >= 1 && j <= w && !solved[i][j] && grid[i][j] == '.')
                    {
                        if(abs(i-x) + abs(j-y) >= 2)
                        {
                            if(d[i][j] > d[x][y] + 1)
                            {
                                d[i][j] = d[x][y] + 1;
                                dq.push_back({i, j});
                            }
                        }
                        else
                        {
                            if(d[i][j] > d[x][y])
                            {
                                d[i][j] = d[x][y];
                                dq.push_front({i, j});
                            }
                        }
                    }
                }
            }
        }

        out << "-1" << endl;
        return;
    }
};


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    DWizardInMaze solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


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

        using namespace std;
        using namespace std;
        typedef long long ll;
        #define endl "\n";
        #define MAX 10000001+9   //Maximum array size;
        #define loop(n) for(ll i=0;i<n;i++)
        #define loop2(n) for(ll i=0;i<n;i+=2)
        #define all(v) v.begin(),v.end()
        #define sz(v)  v.size()
        typedef vector<ll> vi;
        typedef set<ll> si;

        void fast() {

            cin.tie(0);
            cin.sync_with_stdio(0);
        }

        int pow(int a, int b) {
            int pow = 1;
            loop(b)pow *= a;
            return pow;
            //thanks m7md :)
        }

        int main() {
            fast();
            //freopen("input.txt","r",stdin);
            int n;  cin>>n;
            int c[n];
            map<int,int>ma;
            for (int i = 0; i <n ; ++i) {
                cin>>c[i];
                ma[c[i]]=i+1;
            }
            for (int j = 1; j <=n ; ++j) {
                cout<<ma[j]<<" ";
            }
        }



Measured memory_bytes: 5888
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define FOR(i, m, n) for(ll i = m; i < (n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>; 
using vl = vector<ll>;
using vll = vector<vl>;
using pll = pair<ll, ll>;

ll N;
vll G;
vector<bool> seen;
vl cnt;

void dfs(ll p){
    seen[p] = true;
    for(auto np : G[p]){
        if(seen[np]) continue;
        cnt[np] += cnt[p];
        dfs(np);
    }
}

int main() {
    ll Q;
    cin >> N >> Q;
    G.resize(N);
    rep(i, N-1){
        ll a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    cnt.assign(N, 0);
    rep(i, Q){
        ll p, x;
        cin >> p >> x;
        p--;
        cnt[p] += x;
    }
    seen.assign(N, false);
    dfs(0);
    rep(i, N){
        cout << cnt[i] << " ";
    }
}

Measured memory_bytes: 177408
#include <bits/stdc++.h>
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++)
typedef long long ll;

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

  int t, x;
  cin >> t >> x;
  
  cout << (double)t/x << endl;
  return 0;
}


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

int main(void){
  int n,m,k,ans;
  
  cin >> n >> m >> k;
  ans = 0;
  for (int i=0; i<=n; i++){
    for (int j=0; j<=m; j++){
      int x;
      x = i*m+j*n-2*i*j;
//      cout << i << j << x << endl;
      if (x==k) ans=1;
    }
  }
  cout << (ans?"Yes":"No") << endl;
  return 0;
}


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


int main(){
	int i,n;
	cin >> n;
	for(i=1;i<=n;i++){
		if(i%3 == 0) cout << " " << i;	//3????????°
		else if(i/10000 == 3) cout << " " << i;
		else if((i%10000) / 1000 == 3) cout << " " << i;
		else if((i%1000) / 100 == 3 ) cout << " " << i;
		else if((i%100) / 10 == 3) cout << " " << i;
		else if((i%10) == 3) cout << " " << i;
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1164
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数

// デフォルト変数定義
int n,m,a,b,c,x,y,z;
double d,e,f;
string s,t;
//

signed main() {
  RAPID;
  IN(n);
  if(n%2==0) OUT(pow(n/2,2));
  else OUT((n/2+1)*(n/2));
}

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

#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=int(a);i<int(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)

#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=int(a)-1;i>=int(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)

#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
#define popcount(n) (__builtin_popcountll(n))

using namespace std;

template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}

using ll=long long;
using R=long double;
const R EPS=1e-9; // [-1000,1000]->EPS=1e-8 [-10000,10000]->EPS=1e-7
inline int sgn(const R& r){return(r > EPS)-(r < -EPS);}
inline R sq(R x){return sqrt(max<R>(x,0.0));}

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

// Problem Specific Parameter:

// Description: ?´????????????????????????????????§???? 
// TimeComplexity: ?????????$\mathcal{O}(n)$ ??´??°$\mathcal{O}(\log n)$
// Verifyed: AOJ DSL_1_A

class Union_find{
	public:
	    Union_find(int n){par.resize(n),iota(_all(par),0);}
	    int find(int x){return (par[x]==x)?x:par[x]=find(par[x]);}
	    void unite(int a,int b){a=find(a),b=find(b);par[a]=b;}
		bool same(int a,int b){return find(a)==find(b);}
	private:
		vector<int> par;
};

int main(void){
	int n,q;
	cin >> n >> q;
	Union_find uf(n);
	rep(loop,q){
		int type,x,y;
		cin >> type >> x >> y;
		if(type)
			cout << uf.same(x,y) << endl;
		else
			uf.unite(x,y);
	}	
	return 0;
}

Measured memory_bytes: 3200
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;

struct UnionFind {
    vector<ll> par;

    UnionFind(ll N) : par(N) {
        Rep (i, N) par[i] = i;
    }

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

    void unite (ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        if (rx == ry) return;
        par[rx] = ry;
    }

    bool same (ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        return rx == ry;
    }
};

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

    ll N, M;
    cin >> N >> M;
    vector<vector<ll>> language(M, vector<ll>());
    Rep (i, N) {
        ll K;
        cin >> K;
        Rep (j, K) {
            ll L;
            cin >> L;
            L--;
            language[L].push_back(i);
        } 
    }

    UnionFind uf(N);

    Rep (i, M) {
        ll n = language[i].size();
        Rep (j, n) {
            uf.unite(language[i][0], language[i][j]);
        }
    }

    Rep (i, N) {
        if (uf.root(i) != uf.root(0)) {
            cout << "NO\n";
            return 0;
        }
    }

    cout << "YES\n";
    return 0;
}

Measured memory_bytes: 5236
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include<iostream>

using namespace std;

struct Node{
  int key;
  Node *right, *left, *parent;
};

Node *root, *NIL;

Node * find(Node *u, int k)
{
  while(u != NIL && k != u->key)
    {
      if(k < u->key)
	u = u->left;
      else
	u = u->right;
    }

  return u;
}


void insert(int k){
  Node *y=NIL;
  Node *x=root;
  Node *z;

  z=(Node *)malloc(sizeof(Node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;

  while(x!=NIL)
    {
      y=x;
      if(z->key < x->key)
	{
	  x = x->left;
	}
      else
	{
	  x = x->right;
	}
    }

  z->parent = y;

  if(y == NIL)
    {
      root=z;
    }
  else
    {
      if(z->key < y->key)
	{
	  y->left = z;
	}
      else
	{
	  y->right = z;
	}
    }
}


void inoder(Node *u){
  if(u == NIL)
    return;
  inoder(u->left);
  printf(" %d", u->key);
  inoder(u->right);
}

void preoder(Node *u){
  if(u == NIL)
    return;
  printf(" %d", u->key);
  preoder(u->left);
  preoder(u->right);
}

int main(){
  int n, i, x;
  string com;

  scanf("%d", &n);

  for(i=0; i<n; i++)
    {
      cin >> com;
      
      if(com[0] == 'f')
	{
	  scanf("%d", &x);	  
	  Node *t=find(root, x);
	  
	  if(t != NIL)
	    printf("yes\n");
	  else
	    printf("no\n");
	}
      else if(com == "insert")
	{
	  scanf("%d", &x);
	  insert(x);
	}
      else if(com == "print")
	{
	  inoder(root);
	  printf("\n");
	  preoder(root);
	  printf("\n");
	}
    }

  return 0;
}



Measured memory_bytes: 22068
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

int main()
{
    char s[100005];
    int a[27];
    while(scanf("%s",s)!=EOF)
    {
        memset(a,0,sizeof(a));
        int len=strlen(s);
        for(int i=0;i<len;i++)
        {
            a[s[i]-'a']++;
        }
        int flag=0,n=0;
        for(int i=0;i<26;i++)
        {
            if(a[i]==0)
            {
                n=i;
                flag=1;
                break;
            }
        }
        if(flag)
        {
            printf("%c\n",n+'a');
        }
        else
        {
            printf("None\n");
        }
    }
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int bufN;
  cin >> bufN;
  int N= bufN;

  bool contain9= false;
  while(N > 0){
    if(N % 10==9){
      contain9= true;
      break;
    }
    N/= 10;
  }

  string ans= contain9 ? "Yes"
                       : "No";
  cout << ans << endl;
}

Measured memory_bytes: 256