akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<string.h>
int main()
{
	char s[102];
	scanf("%s", s);
	int i, n = strlen(s);
	for (i = 0; i < n; i++)
	{
		if (i % 2 == 0 && s[i] == 'L')
		{
			printf("No\n");
			return 0;
		}
		if (i % 2 == 1 && s[i] == 'R')
		{
			printf("No\n");
			return 0;
		}
	}
	printf("Yes\n");
	return 0;
}

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

typedef long long ll;

void print(int n,vector<int> a){
  cout << a[0];
  for(int i=1;i<n;i++) cout << " " << a[i];
  cout << endl;
}

int main(){
  int n,count=0;
  bool flag = true;
  cin >> n;
  vector<int> a(n);
  for(int i=0;i<n;i++) cin >> a[i];
  for(int i=0;i<n;i++){
    int minj = i;
    for(int j=i;j<n;j++){
      if(a[j] < a[minj]) minj = j;
    }
    if(minj != i){
      int tmp = a[i];
      a[i] = a[minj];
      a[minj]= tmp;
      count++;
    }
  }
  print(n,a);
  
  cout << count << endl;
  return 0;
}



Measured memory_bytes: 3148
#include <stdio.h>

int main(void)
{
	int a, b, c;
	
	scanf("%d %d %d", &a, &b, &c);
	
	if (a && b || c){
		printf("Open\n");
	}
	else {
		printf("Close\n");
	}
	
	return (0);
}

Measured memory_bytes: 584
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始

int main(){
  int n;
  string s;
  cin>>n>>s;
  int cnt = 0;
  int ans = 0;
  for(int i = 0; i < n; i++){
    if(s[i]=='I') cnt++;
    else cnt--;
    ans = max(cnt,ans);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
using namespace std;
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#define rep(i, n) for (int i=0; i<n; i++)
int N;
string s;
int w[200005],b[200005];

int main() {
  cin >> N;
  cin >> s;
  int white=0;
  rep(i, N) {
    if (s[i]=='.') white++;
  }
  int cnt = min(white,N-white);
  rep(i, N) { // 自分含めてi番目から左までに黒が何個あるか
    if (i==0) b[0] = s[0]=='#'?1:0;
    else b[i] = s[i]=='#'?b[i-1]+1:b[i-1];
  }
  for(int i=N-1; i>=0; i--) { // 自分含めてi番目から右までに白が何個あるか
    if (i==N-1) w[i] = s[i]=='.'?1:0;
    else w[i] = s[i]=='.'?w[i+1]+1:w[i+1];
  }
  rep(i, N) {
    if (i==0) continue;
    cnt = min(cnt, w[i]+b[i-1]);
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 5288
import itertools

s = input()
n = len(s)
ans = 0

for item in itertools.product([0, 1], repeat=n-1):
    s_new = s[0]
    for i in range(len(item)):
        if item[i]:
            s_new += '+' + s[i+1]
        else:
            s_new += s[i+1]
    ans += sum([int(item) for item in s_new.split('+')])
print(ans)


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

int main(){
  int c[9];
  for(int i = 0; i < 9; i++){
    cin >> c[i];
  }
  if (!(c[0] - c[1] == c[3] - c[4] && c[0] - c[1] == c[6] - c[7]) ||
      !(c[0] - c[2] == c[3] - c[5] && c[0] - c[2] == c[6] - c[8]) ||
      !(c[0] - c[3] == c[1] - c[4] && c[0] - c[3] == c[2] - c[5]) ||
      !(c[0] - c[6] == c[1] - c[7] && c[0] - c[6] == c[2] - c[8])
    ){
      cout << "No";
      return 0;
    }
  cout << "Yes";
  return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#include <iomanip>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int mx2[] = {1,0};
int my2[] = {0,1};

class ATransfer {
public:
	void solve(istream& in, ostream& out) {
        int a, b, c; in >> a >> b >> c;
	    if(c - a + b >= 0) out << c - a + b << endl;
	    else out << 0 << endl;
	}
};

int main() {
	ATransfer solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		System.out.println(new Main().weather_prediction(scanner.nextLine()));
		scanner.close();
	}
	
	public String weather_prediction(String weather) {
		String[] predictions = {"Sunny", "Cloudy", "Rainy"};
		int i;
		for(i = 0; i < 3; i++) {
			if(weather.equals(predictions[i])) {
				break;
			}
		}
		return predictions[(i + 1) % 3];
	}
}


Measured memory_bytes: 21844
#include <bits/stdc++.h>
using namespace std;
#define  rep(i, n) for(int i = 0; i < n; i++) 
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define INF 1000000000
typedef long long int LL;


int main(){
    int N,K; cin >> N >> K;
    vector<LL> h(N);

    rep(i,N){
       cin >> h[i];
    }

    sort(all(h));

  
    LL temp = INF;
    rep(j,N-K+1){
        temp = min(temp,h[j+K-1] - h[j]);
    }

    cout << temp << endl;
    
}

Measured memory_bytes: 1024
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <numeric>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
#define eb emplace_back
#define F first
#define S second
#define all(obj) (obj).begin(), (obj).end()
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<ll, ll> mpll;
typedef unordered_map<char, ll> mpcl;
typedef unordered_map<string, ll> mpsl;
typedef pair<ll, ll> P;
typedef vector<ll> vl;
typedef vector<vl> vvl;
template<typename T> using PQ = priority_queue<T>;
template<typename T> using minPQ = priority_queue<T, vector<T>, greater<T>>;

ll inl() {
    ll x;
    cin >> x;
    return (x);
}

string ins() {
    string x;
    cin >> x;
    return (x);
}

int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
#pragma clang diagnostic pop
#endif

        ll x = inl(), y = inl(), z = inl(), k = inl();
        vl a(x), b(y), c(z);
        rep(i, x) a[i] = inl();
        rep(i, y) b[i] = inl();
        rep(i, z) c[i] = inl();

        sort(all(a), greater<>());
        sort(all(b), greater<>());
        sort(all(c), greater<>());

        vl ans;
        rep(i, x) {
            rep(j, y) {
                if ((i + 1) * (j + 1) > k) break;
                rep(l, z) {
                    if ((i + 1) * (j + 1) * (l + 1) > k) break;
                    ans.eb(a[i] + b[j] + c[l]);
                }
            }
        }
        sort(all(ans), greater<>());
        rep(i, k) cout << ans[i] << endl;


#ifdef MY_DEBUG
    }
#endif
    return 0;
}

Measured memory_bytes: 1404
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <math.h>
#include <string>
#include <numeric>
#include <queue>
#include <cstdio>
#include <cstring>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;++i)
#define rep1(i,n) for(ll i=1;i<n;++i)
#define mrep(i,n) for(ll i=n;i>=0;--i)
#define all(a) (a).begin(),(a).end()
#define vl vector<ll>
#define vvl vector<vector<ll> >
#define vb vector<bool>
#define vvb vector<vector<bool> >
#define pl pair<ll,ll>
#define inf 1001001001001001000
#define mod 1000000007
//#define mod 998244353
#define pi 3.1415926535
using namespace std;
struct __INIT{
    __INIT(){
        cin.tie(0);
        ios::sync_with_stdio(false);
        cout<<fixed<<setprecision(15);
    }
}__init;

int main(){
    ll x;
    cin>>x;
    if(x == 0) cout<<1<<endl;
    else cout<<0<<endl;
    return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
using i64=long long;
int read(){int x;scanf("%d",&x);return x;}
int main()
{
    i64 now=100,ans=0,X;cin>>X;
    while(now<X) ++ans,now+=now/100;
    printf("%lld",ans);
}


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

typedef long long LL;
#define dbg(x) cerr << #x"=" << x << endl;
int n;

int main(){
    //freopen("in.txt", "r", stdin);
    ios::sync_with_stdio(0); cin.tie(0);
    while(cin >> n){
        vector<int> p(n);
        for(int i = 0; i < n; ++i) cin >> p[i];
        int ans = 0;
        for(int i = 1; i < n-1; ++i){
            bool f = (p[i] > p[i-1]) && (p[i] > p[i+1]);
            int a = p[i-1];
            int b = p[i+1];
            if(a > b) swap(a, b);
            if(p[i] > a && p[i] < b) ++ans;
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
const long double PI = (acos(-1));
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
int ctoi(char c)
{
    switch (c)
    {
    case '0':
        return 0;
    case '1':
        return 1;
    case '2':
        return 2;
    case '3':
        return 3;
    case '4':
        return 4;
    case '5':
        return 5;
    case '6':
        return 6;
    case '7':
        return 7;
    case '8':
        return 8;
    case '9':
        return 9;
    default:
        return 0;
    }
}
int main()
{
    int n, k;
    cin >> n >> k;
    int ans = 1;
    for (int i = 0; i < n; i++)
    {
        if (ans <= k)
        {
            ans *= 2;
        }
        else
        {
            ans += k;
        }
    }
    cout << ans << endl;
}

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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  for(int i=0;i<50000000;i++){
    if(a%2==1||b%2==1||c%2==1){cout << i << endl; return 0;}
    int aa = (b+c) / 2;
    int bb = (a+c) / 2;
    int cc = (a+b) / 2;
    a = aa; b = bb; c = cc;
  }
  cout << -1 << endl;
  return 0;
}

Measured memory_bytes: 256
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int a [] = new int [N];
		
		for (int i=0; i<N; i++)
			a[i]=sc.nextInt();
		
		Arrays.sort(a);
		int min = a[0];
		int max = a[N-1];
		
		long ans = 1000000000;
		for (int j=min; j<max+1; j++){
			long temp = 0;
			for (int i=0; i<N; i++){
				temp=temp+(a[i]-j)*(a[i]-j);
			}
			ans = Math.min(ans, temp);
			
		}
		System.out.println(ans);
		sc.close();
	}

}

Measured memory_bytes: 21716
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
#pragma GCC optimize("O3")
#include<bits/stdc++.h>
#define mod 1000000007
#define mod1 998244353
#define INF LLONG_MAX
#define NINF LLONG_MIN
#define inf 1e18
#define all(v) v.begin(),v.end()
#define T ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define rep1(i,a,n) for(ll i=a;i<=(long long)n;++i)
#define rep2(i,n,a) for(ll i=n;i>(long long)a;--i)
#define rep3(i,n,a) for(ll i=n;i>=(long long)a;--i)
#define repi(i,a,n) for(int i=a;i<=(int)n;++i)
#define repl(i,a,n) for(int i=a;i<(int)n;++i)
#define PI 3.141592653589793238510
#define en '\n'
#define MAX 100005
#define less_time ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define debug cout<<"HERE"<<en;
#define setbits(x)  __builtin_popcountll(x)
#define zrobits(x)  __builtin_ctzll(x)
#define ps(x,y) fixed<<setprecision(y)<<x
#define mk(arr,n,type) type *arr=new type[n];
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define vc vector
#define vi vc<int>
#define mii unordered_map<int,int>
#define pql priority_queue<int>
#define pqs priority_queue<int,vi,greater<int>>
#define vll vector<long long>
#define pll pair<long long,long long>
#define pl pair<int,int>
#define eb emplace_back
#define pb push_back
#define mp make_pair
typedef long long ll;
typedef long double ld;
using namespace std;
using namespace std::chrono;
int main(){
    less_time;
    int n;
    cin>>n;
    int h[MAX]={0};
    repi(i,1,n)cin>>h[i];
    int dp[MAX];
    repl(i,0,MAX)dp[i]=INT_MAX;
    dp[1]=0;
    dp[2]=abs(h[2]-h[1]);
    repi(i,3,n)
    {
      dp[i]=min(dp[i],dp[i-1]+abs(h[i]-h[i-1]));
      dp[i]=min(dp[i],dp[i-2]+abs(h[i]-h[i-2]));
    }
    cout<<dp[n];
return 0;
}


Measured memory_bytes: 1024
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();// nこの希望
		long a[] = new long[n + 1];
		long ru[] = new long[n +1];
		a[0] = 0;
		ru[0] = 0;
		for (int i = 1; i <= n; i++) {
			a[i] = sc.nextLong();
			ru[i] = ru[i - 1] + a[i];
			}

		Arrays.sort(ru);




		long sta, gol;
		sta = 0;
		gol = 0;
		long same, ans;
		ans = 0;

		for (int i = 1; i <= n ; i++) {
			if (ru[i - 1] - ru[i] != 0) {
				gol = i;

				same = gol - sta;

				ans = ans + cou(same);
				sta = gol;

			}
		}
		same=n+1-sta;
		ans=ans+cou(same);
		System.out.println(ans);
	}

	public static long cou(long a) {
		long c;
		c = a * (a - 1);

		c = c / 2;
		return c;
	}

}

Measured memory_bytes: 84872
#include <iostream> 
#include <vector> 
#include <algorithm> 
#include <bits/stdc++.h> 
#include <stdlib.h> 
#include <stdio.h> 
#include <functional> 
#include<math.h> 
#include<cstring>
using namespace std;
int main(void){
    // Your code here!
    vector<int> vec(10);
    vec.at(1) = 2;
    vec.at(2) = 5;
    vec.at(3) = 5;
    vec.at(4) = 4;
    vec.at(5) = 5;
    vec.at(6) = 6;
    vec.at(7) = 3;
    vec.at(8) = 7;
    vec.at(9) = 6;
    
    int N,M;
    cin >> N >> M;
    vector<int> a(0);
    for(int i = 0; i < M; i++){
        int y;
        cin >> y;
        a.push_back(y); 
        
    }
    vector<int> dp(N+1);
    
    for(int i = 0; i <= N; i++) dp.at(i) = -100;
    dp.at(0) = 0;
    //使う数字の数
    
    for(int i = 1; i <= N; i++){
        for(int x : a){
            if(i >= vec.at(x)){
                if(dp.at(i-vec.at(x)) +1 > dp.at(i)){
                    dp.at(i) = dp.at(i-vec.at(x)) + 1;
                }
            }
        }
    }
   
    
    sort(a.begin(),a.end());
    reverse(a.begin(),a.end());
    int z = dp.at(N);
    int p = 0;
    while(p < z){
        for(int x : a){
            if(N >= vec.at(x) && dp.at(N-vec.at(x)) == dp.at(N) - 1){
                cout << x;
                N = N - vec.at(x);
                p++;
                break;
            }
        }
    }
    


}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define pi pair<int, int>
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define deb(x) cout << #x << ":" << x << endl;
/* freopen("input.txt", "r", stdin); */
/* freopen("output.txt", "w", stdout); */
const ll inf = 1e17 + 7, MOD = 1e7 + 9;


int main() {
	fastio();
	string s;
	cin >> s;
	if(s == "ABC")
		cout << "ARC\n";
	else
		cout << "ABC\n";
	return 0;
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
#define rep(i,m) for(long long i=0; i<m; i++)
#define per(i,m) for(long long i=m-1; i>=0; i--)
#define FOR(i,n,m) for(long long i=n; i<m; i++)
#define ROF(i,n,m) for(long long i=m-1; i>=n; i--)
#define SORT(v,n) do{sort(v,v+n);reverse(v,v+n);}while(0)
#define all(x) (x).begin(),(x).end()
#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
typedef pair<ll, ll> LP;

ll POW(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW(x*x,n/2)%MOD;
  return x%MOD*POW(x,n-1)%MOD;
}

ll POW2(ll x,ll n){
  if(n==0)return 1;
  if(n%2==0)return POW2(x*x,n/2);
  return x*POW2(x,n-1);
}

ll gcd(ll u, ll v) {
  ll r;
  while (0 != v) {
    r = u % v; u = v; v = r;
  }
  return u;
}

ll lcm(ll u, ll v) {
  return u*v/gcd(u,v);
}
 
ll KAI(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI(m-1)%MOD;
}
 
ll KAI2(ll m)
{
  if(m<0) return 0;
  if(m==0) return 1;
  return m*KAI2(m-1);
}

ll extGCD(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = extGCD(b, a%b, y, x);
    y -= a / b * x;
    return d;
}
 
inline ll mod(ll a, ll m) {
    return (a % m + m) % m;
}
 
ll modinv(ll a) {
    ll x, y;
    extGCD(a, MOD, x, y);
    return mod(x, MOD);
}
 
ll COM(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI(m)%MOD*modinv(KAI(n)%MOD*KAI(m-n)%MOD)%MOD;
}

ll COM2(ll m,ll n)
{
  if(m<n) return 0;
  if(n<0) return 0;
  if(n==0) return 1;
  if(m==n) return 1;
  return KAI2(m)/KAI2(n)/KAI2(m-n);
}

ll DEC(ll x,ll m,ll n)
{
  return x%POW(m,n+1)/POW(m,n);
}

ll keta(ll x,ll n)
{
  if(x==0)return 0;
  return keta(x/n,n)+1;
}

ll DIV(ll x,ll n)
{
  if(x==0)return 0;
  return x/n+DIV(x/n,n);
}

ll ORD(ll x,ll n)
{
  if(x==0)return INF;
  if(x%n!=0)return 0;
  return 1+ORD(x/n,n);
}

int main()
{
  ll a,b,c;
  cin >> a >> b >> c;
  printf("%lld",(a*3+b)/2);
}


Measured memory_bytes: 256
#include <stdio.h>
int main()
{
  int a,b,c,d,s,t;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  s = a+b+c+d;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  t = a+b+c+d;
  if(s<t) printf("%d\n",t);
  else printf("%d\n",s);
  return 0;
}

Measured memory_bytes: 0
package main

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

func main() {
	N := readInt()
	K := readInt()
	A := readInts(N)
	F := readInts(N)

	sort.Ints(A)
	sort.Sort(sort.Reverse(sort.IntSlice(F)))

	l := -1            // ng
	r := A[N-1] * F[0] // ok
	for r > l+1 {
		m := l + (r-l)/2
		isOk := func(x int) bool {
			result := 0
			for i := 0; i < N; i++ {
				t := A[i] - x/F[i]
				if t > 0 {
					result += t
				}
			}
			return result <= K
		}
		if isOk(m) {
			r = m
		} else {
			l = m
		}
	}
	fmt.Println(r)
}

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

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

func readString() string {
	stdinScanner.Scan()
	return stdinScanner.Text()
}

func readInt() int {
	result, err := strconv.Atoi(readString())
	if err != nil {
		panic(err)
	}
	return result
}

func readInts(n int) []int {
	result := make([]int, n)
	for i := 0; i < n; i++ {
		result[i] = readInt()
	}
	return result
}


Measured memory_bytes: 6656
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;cin>>n;
    set<int> neighbors[n];
    rep(i,n-1){
        int x,y;cin>>x>>y;
        x--;y--;
        neighbors[x].insert(y);
        neighbors[y].insert(x);
    }
    vector<vector<ll> > dp(2,vector<ll>(n,-1));
    function<ll(int,int,bool)> solve = [&](int now, int parent, bool is_white){
        ll res = 1LL;
        if(dp[is_white][now]!=-1){return dp[is_white][now];}
        if(parent!=-1&&neighbors[now].size()==1){return 1LL;}
        if(parent==-1&&neighbors[now].size()==0){return 1LL;}
        for(auto child: neighbors[now]){
            ll tmp = 0;
            if(child==parent){continue;}
            tmp += solve(child, now, true);
            if(is_white){
                tmp += solve(child, now, false);
            }
            tmp %= MOD;
            res *= tmp;
            res %= MOD;
        }
        DEBUG{
            printf("now: %d, parent: %d, color: %d, res: %lld\n",now,parent,is_white,res);
        }
        DEBUG{cout <<"now: "<<now<<" res : "<< res << endl;}
        return dp[is_white][now] = res;
    };
    ll r = solve(0,-1,true) + solve(0,-1,false);
    r %= MOD;
    cout << r << endl;
    return 0;
}


Measured memory_bytes: 28400
#include <stdio.h>

main(){
    int N,K;
    scanf("%d", &N);
    scanf("%d", &K);
    int i, s=1;
    for(i=1; i<=N; i++){
        if(s*2<s+K){
            s*=2;
        }
        else{
            s=s+K;
       }
    }
    printf("%d", s);
}


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

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let nums: Vec<i32> = s
        .trim()
        .split_whitespace()
        .map(|x| x.parse().ok().unwrap())
        .collect();
    let x = nums[0];
    let y = nums[1];

    let mut res = None;

    'outer: for i in 0..x+1 {
        for j in 0..x+1-i {
            if i * 10000 + j * 5000 + (x - i - j) * 1000 == y {
                res = Some((i, j, x - i - j));
                break 'outer;
            }
        }
    }

    let (res_0, res_1, res_2) = res.unwrap_or((-1, -1, -1));
    println!("{} {} {}", res_0, res_1, res_2);
}


// fn main() {
//     let mut s = String::new();
//     stdin().read_line(&mut s).ok();
//     let nums: Vec<i32> = s
//         .trim()
//         .split_whitespace()
//         .map(|x| x.parse().ok().unwrap())
//         .collect();
//     let x = nums[0];
//     let y = nums[1];
// 
//     let max_yen_num = y / 1000;
//     let yen_num_diff = max_yen_num - x;
// 
//     // yen_num_diff $B$,(B 4 (1000 -> 5000) * i + 9 (1000 -> 10000) * j $B$G3d$j@Z$l$k$+$r9M$($k(B
//     let nine_space = yen_num_diff / 9;
//     let nine_space_diff = yen_num_diff % 9;
//     let (four_space, nine_space) = match nine_space_diff {
//         0 => (0, nine_space),
//         3 => (3, nine_space - 1),
//         4 => (1, nine_space),
//         7 => (4, nine_space - 1),
//         8 => (2, nine_space),
//         _ => (-1, -1),
//     };
//     if nine_space < 0 {
//         let four_space = -1;
//     }
// 
//     if four_space == -1 {
//         println!("{} {} {}", -1, -1, -1);
//     } else {
//         println!("{} {} {}", nine_space, four_space, x - nine_space - four_space);
//     }
// }


Measured memory_bytes: 4352
# B - Shift Only

N = input()
A = list(map(int, input().split()))
ans = 0

# リストの要素がすべて偶数かどうか判定
while all(a % 2 == 0 for a in A):
	# リストの要素をすべて2で割る
	A = [a / 2 for a in A]
	ans += 1
	
print(ans)

Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<bitset>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1<<30;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[8]={1,0,-1,0,1,1,-1,-1} , dy[8]={0,1,0,-1,1,-1,1,-1} ;

struct UnionFind{
   vector<int> par;
   vector<ll> ran;
   UnionFind(int n):par(n,-1),ran(n){}
   int find(int x){
       if(par[x]<0)return x;
       int y = find(par[x]);
      ran[x] += ran[par[x]];
      return par[x] = y;
   }
   bool unite(int x,int y,ll z,int k){
       x=find(x);
       y=find(y);
       if(x==y)return false;
       ran[x]-=z*par[y];
       ran[y]-=z*par[x];
       par[k]=par[x]+par[y];
       par[x]=k;
       par[y]=k;
       return true;
   }

   bool same(int x,int y){
       return find(x)==find(y);
   }
};


int main(){
    int n;
    cin>>n;
    vector<pair<ll,pint>> v;
    int x,y,z;
    rep(i,n-1){
        scanf("%d%d%d",&x,&y,&z);
        v.push_back({z,{x-1,y-1}});
    }
    UnionFind uf(2*n);
    sort(v.rbegin(),v.rend());
    rep(i,n-1){
        uf.unite(v[i].second.first, v[i].second.second, v[i].first,n+i);
    }
    rep(i,n){
        uf.find(i);
        printf("%lld\n",uf.ran[i]);
    }
}

Measured memory_bytes: 5616
/*input
4
3 0 0
1 1 1
9 4 1
0 1 2
*/
fn read_line() -> String {
    let mut return_ = format!("");
    std::io::stdin().read_line(&mut return_).ok();
    return_.pop();
    return_
}

fn main() {
    let mut v: Vec<u32>;
    let mut tot_team: u32;
    for _ in 0..read_line().parse::<usize>().unwrap() {
        tot_team = 0;
        v = read_line()
            .split_whitespace()
            .map(|x| x.parse().unwrap())
            .collect();
        while v[2] > 0 && v[1] > 0 && v[0] > 0 {
            v[2] = v[2] - 1;
            v[1] = v[1] - 1;
            v[0] = v[0] - 1;
            tot_team = tot_team + 1;
        }
        while v[1] > 0 && v[0] > 1 {
            v[0] = v[0] - 2;
            v[1] = v[1] - 1;
            tot_team = tot_team + 1;
        }
        while v[0] > 2 {
            v[0] = v[0] - 3;
            tot_team = tot_team + 1;
        }
        println!("{}", tot_team);
    }
}



Measured memory_bytes: 5028
#include <bits/stdc++.h>
using namespace std;
//#define int long long
typedef pair<int,int> ii;
typedef tuple<int,int,int> iii;
#define ll long long
#define miniiPQ priority_queue<ii,vector<ii>,greater<ii> >
#define minPQ priority_queue<int,vector<int>,greater<int> >
#define PQ priority_queue<int>
#define iiPQ priority_queue<ii>
#define US unordered_set<int>
#define UMS unordered_multiset<int>
#define UM unordered_map<int>
#define ST stack<int>
 
void m1(){
  int n; cin >> n;
  int arr[n+5];
  UMS s;
  for(int i=0;i<n;++i){
     cin >> arr[i];
     s.insert(arr[i]);
  }
  int ans = 0;
  bool ok;
  for(int i=0;i<n;++i){
    s.erase(s.find(arr[i]));
    ok = true;
    for(int j=1;j*j<=arr[i];++j){
      if(arr[i]%j == 0){
        if(s.find(j) != s.end() || s.find(arr[i]/j) != s.end()){
          ok = false;
          break;
        }
      }
    }
    s.insert(arr[i]);
    if(ok){++ans;}
  }
  cout << ans;
}
 
/*
void m2(){
  int t; cin >> t;
  while(t--) m1();
}
*/
 
int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  //freopen("in.txt","r",stdin);
  m1();
  //m2();
}

Measured memory_bytes: 12188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.InteropServices;
using System.Text;

namespace AC
{
    class Program
    {
        static void Main(string[] args)
        {
            var input = ReadArrayInt();
            var N = input[0];
            var X = input[1];
            var T = input[2];
            var ans = T * (N / X);
            if (N % X != 0) ans += T;

            Console.WriteLine(ans);
            Console.ReadLine();
        }

        static string Read() { return Console.ReadLine(); }
        static int ReadInt() { return int.Parse(Read()); }
        static long ReadLong() { return long.Parse(Read()); }
        static string[] ReadArrayString() { return Read().Split(' '); }
        static int[] ReadArrayInt() { return Read().Split(' ').Select(s => int.Parse(s)).ToArray(); }
        static long[] ReadArrayLong() { return Read().Split(' ').Select(s => long.Parse(s)).ToArray(); }
    }
}

Measured memory_bytes: 28256
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i==n-1];};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll s,t,p,q,M,y;
    cin >> s >> t >> p >> q >> M >> y;
    ll val = (s^t);
    print(val^y);

}


Measured memory_bytes: 3188
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    public class Code20171216C
    {
        static void Main(string[] args)
        {
            string s1 = Console.ReadLine();
            string s2 = Console.ReadLine();

            var ret = funcMain(s2);
            Console.WriteLine(ret);
        }

        static public string funcMain(string arg1)
        {
            int ret = 0;
            var list1 = arg1.Split().Select(s => int.Parse(s)) ;
            var list2 = list1.GroupBy(g=>g).Select(s=> new { idx = s.Key, cnt = s.Count() });
            
            ret = list2.Select(s => s.cnt >= s.idx ? s.cnt - s.idx : s.cnt).Sum();

            return ret.ToString();
        }
    }
}

Measured memory_bytes: 32092
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cmath>
#include <cstdio>
#include <cctype>
#include <vector>
#include <string>
#include <cctype>
#include <cstring>
#include <sstream>
#include <iomanip>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;
typedef stringstream strstm;
#define pb push_back
#define PI acos(-1.0)
#define CLR(a) MST(a,0);
#define E 2.718281829459
#define lowbit(x) (x & (-x))
#define DBG(x) cout << (x) << " ";
#define MST(a,b) memset(a,b,sizeof(a));
#define _for(i,a,b) for(int i = (a); i < (b); ++i)
#define _rep(i,a,b) for(int i = (a); i <= (b); ++i)
#define _ech(x,z) for(auto x = z.begin(); x != z.end(); ++x)


int main(int argc, char const *argv[])
{	
	int N, A; cin >> N >> A;
	if(	N % 500 <= A) cout << "Yes" << endl;
	else cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 888
def CanIGetEnoughSkills(SkillPoints,M,X):
    for _ in range(M):
        if SkillPoints[_]<X:
            return False
        else:
            pass
    return True


N,M,X=map(int,input().split())
books=[]
for n in range(N):
    array= list(map(int,input().split()))
    books.append(array)
# print(books)

BookCost=[]
GetSkillPoints=[]
for i in range (N):
    BookCost.append(int(books[i][0]))
    GetSkillPoints.append(books[i][1:])

temp_cost=10**9

for Cart in range (2**len(GetSkillPoints)):
    TotalCost=0
    SkillPoints=[0]*M
    
    for book in range(len(GetSkillPoints)):
        if (Cart>>book)&1==0:
            continue
        TotalCost+= BookCost[book]
        for skillelement in range(M):
            SkillPoints[skillelement]+=GetSkillPoints[book][skillelement]

    # print(TotalCost,SkillPoints)
    if CanIGetEnoughSkills(SkillPoints,M,X)== True:
        temp_cost=min(temp_cost,TotalCost)

Answer=temp_cost
if Answer==10**9:
    Answer=-1
    
print(Answer)

Measured memory_bytes: 9260
#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int>G[100010];
int fa[100010],rudu[100010];
queue<int>qq;
int main(){
	cin>>n>>m;
	for(int i=1;i<=n-1+m;i++){
		int x,y;
		cin>>x>>y;
		G[x].push_back(y);
		rudu[y]++;
	}
	for(int i=1;i<=n;i++)if(rudu[i]==0){
		qq.push(i);
		break;
	}
	while(!qq.empty()){
		int x=qq.front();
		qq.pop();
		for(auto y:G[x]){
			rudu[y]--;
			if(!rudu[y]){
				qq.push(y);
				fa[y]=x;
			}
		}
	}
	for(int i=1;i<=n;i++)cout<<fa[i]<<endl;
	return 0;
}


Measured memory_bytes: 7040
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define nl "\n"
#define rep(i,n) for(ll i=0; i<(n); i++)
typedef vector<ll> vl;
typedef vector<vector<ll>> matrix;//matrix A(n, vl(m)); //n*m行列
typedef vector<string> vs;
typedef pair<ll,ll> pl;
typedef vector<pl> vp;
typedef vector<bool> vb;
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define sortup(V) sort(V.begin(), V.end())
#define sortdown(V) sort(V.rbegin(), V.rend())
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;}
ll llpow(ll e,ll x){ll res=1LL;while(x){if(x&1)res*=e;e*=e;x/=2;}return res;}
#define INF ((1LL<<62)-(1LL<<31))
#define MOD 1000000007 //998244353

ll gcd(ll A, ll B){
    if(A<B) swap(A,B);
    while(B){
        ll w = A%B;
        A = B;
        B = w;
    }
    return A;
}

ll lcm(ll A, ll B){return A/gcd(A,B)*B;}

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

    // solution comes here

    ll H, W;
    cin >> H >> W;
    ll N;
    cin >> N;
    vl a(N);
    rep(i, N) cin >> a[i];

    vl col(H*W);
    ll idx=0;
    rep(i, N) rep(j, a[i]) col[idx++] = i+1;

    idx=0;
    matrix ans(H, vl(W));
    rep(i, H) rep(j, W) {
        if(i%2) ans[i][W-1-j] = col[idx++];
        else    ans[i][j]     = col[idx++];
    }

    rep(i, H){
        rep(j, W) cout << ans[i][j] << " ";
        cout << nl;
    }

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  int n, t;
  cin >> n >> t;
  vector<int> a(n);
  rep(i, n) cin >> a.at(i);
  int mn = a.front();
  map<int, int> mp;
  rep2(i, 1, n){
    if(mn > a.at(i)){
      mn = a.at(i);
    }else{
      mp[a.at(i)-mn]++;
    }
  }
  auto itr = mp.rbegin();
  cout << itr->second << endl;
  return 0;
}

Measured memory_bytes: 8264
#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define inf 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define f first
	#define s second
	
	using namespace std;
	int main()
	{
		std::ios::sync_with_stdio(false);
		ll t;
        cin >> t;
        map<string, int> check;
        int count = 0;
        while(t--){
            string s;
            cin >> s;
            if(check.count(s)==0){
                count++;
                check[s]++;
            }
            else{
               continue;
            }

        }
        cout << count << endl;
		return 0;
	}


Measured memory_bytes: 19160
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rep2(r, aa, bb) for (int r = (aa)-1; r >= (bb); r--)
#define be(x) (x.begin(), x.end())
#define pb(t) push_back(t)
#define ll long long
#define mp(a, b) make_pair(a, b)
int main(){
	int h, n, s=0;
	cin>>h>>n;
	vector<int>A(n);
	rep(i,0,n){
		cin>>A[i];
		s+=A[i];
	}
	if(s>=h)cout<<"Yes\n";
	else cout<<"No\n";
}


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

typedef unsigned long long int ull;

#define NMAX 100000
#define KMAX 100000
#define HMAX 1000000000

ull hi[NMAX];

ull comp(const void *a, const void *b) {
    return *(ull*)a - *(ull*)b;
}

int main(int ac, char **av) {
  ull N, K, i, j, res, t;

  scanf("%d %d", &N, &K);
  for (i = 0; i < N; i++) {
    scanf("%d", hi + i);
  }

  qsort(hi, N, sizeof(ull), comp);

  res = HMAX;

  for (i = 0; i <= N - K; i++) {
    t = hi[i + K - 1] - hi[i];
    if (t < res) {
      res = t;
    }
  }

  printf("%d\n", res);
  return 0;
}

Measured memory_bytes: 1788
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
d=[0]*41
t=[0]*41
p=2**40
x=0
y=1
ans=0
for i,j in enumerate(bin(k)[::-1]):
    if j=="b": break
    if j=="1": d[i]=1

for i in a:
    for j,k in enumerate(bin(i)[::-1]):
        if k=="b": break
        if k=="1": t[j]+=1
for i in range(40,-1,-1):
    if d[i]==1 and t[i]>n//2-(n+1)%2:
        y=0
    elif d[i]==1 and t[i]<=n//2:
        x+=p
    elif y==0 and t[i]<=n//2:
        x+=p
    p//=2
for i in a:
    ans+=x^i
print(ans)

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for (int i = 0; i < (int)(n); i++)
#define FOR(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define FORR(i, a, b) for (int i = (int)(b)-1; i >= (int)(a); i--)

#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUG_VEC(v) cerr<<#v<<": ";REP(__i,(v).size())cerr<<((v)[__i])<<", ";cerr<<endl
#define PRINT(x) cout << x << endl
#define all(x) x.begin(),x.end()

int main() {
    int N;
    cin >> N;
    vi A(N);
    int cpattern=1;
    int tmpcnt = 0; //0の数
    ll ans =0;
    for(int i=0;i<N;i++){
        cin >> A[i];
        if(A[i]==0)tmpcnt++;
    }

    for(int i=3;i>=1;i--){ //色のパターン
        if(tmpcnt==0)break;
        cpattern *= i;
        tmpcnt--;
    }

    vi can_color(N+1,0); //使える色
    can_color[0]=3;

    ll cnt = 1;
    for(int i=0;i<N;i++){
        int ai = A[i];
        cnt *= can_color[ai];
        can_color[ai]--;
        can_color[ai+1]++;
        cnt %= 1000000007;
    }

    cout << cnt << endl;

}

Measured memory_bytes: 1024
#include<iostream>
#include<vector>
#include<cmath>
#include<string>
#include<algorithm>
#include<map>
#include<utility>
#include<cstdio>
#include<cctype>
#include<bits/stdc++.h>

using namespace std;
using ll = long long;
const long long INF = 1LL<<60;

typedef pair<ll,ll> Pair;

int main(){

ll x;

cin >> x;

if(400 <= x && x <= 599) cout << "8" << endl;
else if(600 <= x && x <= 799) cout << "7" << endl;
else if(800 <= x && x <= 999) cout << "6" << endl;
else if(1000 <= x && x <= 1199) cout << "5" << endl;
else if(1200 <= x && x <= 1399) cout << "4" << endl;
else if(1400 <= x && x <= 1599) cout << "3" << endl;
else if(1600 <= x && x <= 1799) cout << "2" << endl;
else if(1800 <= x && x <= 1999) cout << "1" << endl;

return 0;

}   


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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> v2l;
typedef vector<bool> vb;
typedef vector<vb> v2b;

const ll AMAX = 1e13;

struct node {
    vl dp1;
    vb dp2;
    int sz;
};

node dfs(vi e[], int a[], int x, int p) {
    node ret;
    ret.sz = 1;
    ret.dp1 = {a[x]};
    ret.dp2 = {a[x] > 0};

    for (int y : e[x]) {
        if (y == p) {
            continue;
        }

        node t = dfs(e, a, y, x);
        ret.dp1.resize(ret.sz + t.sz, AMAX);
        ret.dp2.resize(ret.sz + t.sz, false);

        for (int i = ret.sz - 1; i >= 0; i--) {
            for (int j = t.sz - 1; j >= 0; j--) {
                if (j > 0) {
                    ret.dp1[i+j] = min(ret.dp1[i+j], ret.dp1[i] + t.dp1[j]);
                    ret.dp2[i+j] = ret.dp2[i+j] || ret.dp2[i] && t.dp2[j];
                }
                if (t.dp1[j] < 0 || t.dp2[j]) {
                    ret.dp1[i+j+1] = min(ret.dp1[i+j+1], ret.dp1[i]);
                    ret.dp2[i+j+1] = ret.dp2[i+j+1] || ret.dp2[i];
                }
            }
            ret.dp1[i] = min(AMAX, ret.dp1[i] + t.dp1[0]);
            ret.dp2[i] = ret.dp2[i] && t.dp2[0];
        }

        ret.sz += t.sz;
    }

    return ret;
}

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vi e[n];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        u--, v--;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    node res = dfs(e, a, 0, -1);

    for (int i = 0; i < n; i++) {
        if (res.dp1[i] < 0 || res.dp2[i]) {
            cout << i << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 2176
import sys
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()

from collections import defaultdict

def main():
    N, K = LI()
    A = LI_()
    edges = defaultdict(list)
    for i, a in enumerate(A[1:], 1):
        edges[a].append(i)

    global ans
    ans = 0
    if A[0] != 0:
        ans += 1
    def DFS(v, parent):
        global ans
        height = 0
        for to in edges[v]:
            height = max(height, DFS(to, v))
        if parent != 0 and height >= K - 1:
            height = -1
            ans += 1
        return height + 1
    DFS(0, 0)
    return ans

print(main())

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

#define endl "\n"
#define all(x) x.begin(),x.end()
#define pb push_back
#define ff first 
#define ss second 
#define pii pair<int,int>
#define vi vector<int>
#define vc vector<char>
#define vii vector<pii>
#define vvi vector<vi>
#define fori(i,n) for(int i=1;i<=n;++i)
#define forn(i,n) for(int i=0;i<n;++i)
#define sz(x) int(x.size())
#define error(x) cout<<#x<<" "<<x<<endl
#define IOS  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)

const int N=100*1000;
const int mod=1e9+7;

int min3(int a,int b,int c){return min(a,min(b,c));}
int max3(int a,int b,int c){return max(a,max(b,c));}
int min4(int a,int b,int c,int d){return min(min(a,b),min(c,d));}
int max4(int a,int b,int c,int d){return max(max(a,b),max(c,d));}

//#define int int64_t
//int a[N+2];

int32_t  main(){
	IOS;
  string s;cin>>s;
  map<char,int>mm;
  for(auto it:s)mm[it]++;
  for(auto it:mm){
    if(mm[it.first]%2){
      cout<<"No\n";
      return 0;
    }
  }
  cout<<"Yes\n";

  return 0;
}



Measured memory_bytes: 256
#include <stdio.h>

int main(void){
    
    int n,x,i,j,k,kei=0;
    
    while(1){
        scanf("%d %d",&n,&x);
        if(n ==0 && x ==0){
            break;
        }
        for(i=1;i<n-1;i++){
            for(j=i+1;j<n;j++){
                for(k=j+1;k<n+1;k++){
                    if(i+j+k==x){
                        kei +=1;
                    }
                }
            }
        }
        printf("%d\n",kei);
        kei =0;
    }
}


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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if (A % 2 || B % 2 || C % 2) return cout << 0 << "\n", 0;
  if (A == B && B == C) return cout << -1 << "\n", 0;
  int cnt = 0;
  while (true) {
    if (A % 2 || B % 2 || C % 2) break;
    int a = A, b = B, c = C;
    A = b / 2 + c / 2;
    B = a / 2 + c / 2;
    C = a / 2 + b / 2;
    cnt++;
  }
  cout << cnt << "\n";
}

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

bool contains(const int s[], int n, int x) {
	for (int i = 0; i < n; i++) {
		if (s[i] == x) return true;
	}
	return false;
}

int main () {
	int n;
	cin >> n;
	int S[n];
	for (int i = 0; i < n; i++) {
		cin >> S[i];
	}
	int q, cnt = 0;
	cin >> q;
	for (int i = 0; i < q; i++) {
		int x;
		cin >> x;
		if (contains(S, n, x)) {
			cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 1200
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;

int main() {
double h,w,bmi;
int n;
char a,b;
while(cin>>n>>a>>w>>b>>h){
	bmi=w/(h*h);
	if(bmi>=25){
		cout<<n<<endl;
	}
}
	return 0;
}

Measured memory_bytes: 1232
Option Strict On
Module problemC

    Sub Main()
        Dim x As Integer = Integer.Parse(Console.ReadLine)
        Dim o As Integer = x Mod 10
        Dim t As Integer = (x Mod 100 - o) \ 10
        Dim p As Integer = 0

        Select Case o
            Case 1 To 5
                p = 1
            Case 2 To 9
                p = 2
        End Select

        If t > 0 Then
            p += t * 2
        End If

        Console.WriteLine(Convert.ToInt32(x >= p * 100))
    End Sub

End Module


Measured memory_bytes: 11220
#include <bits/stdc++.h>
#define rep(i, a, n) for (int i = a; i < n; i++)
#define repr(i, a, n) for (int i = n - 1; i >= a; i--)
using namespace std;
using ll = long long;
using P = pair<int, int>;
template <typename T> void chmin(T &a, T b) { a = min(a, b); }
template <typename T> void chmax(T &a, T b) { a = max(a, b); }

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

  int n;
  cin >> n;
  while (n > 0) {
    if (n % 10 == 7) {
      cout << "Yes" << endl;
      return 0;
    }
    n /= 10;
  }
  cout << "No" << endl;
}


Measured memory_bytes: 3652
#define _USE_MATH_DEFINES
 
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using ld = long long;
 
constexpr ll MOD = 1000000007;
 
#ifndef ONLINE_JUDGE
template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {o << "{"; for (auto &x : obj) o << " (" << x.first << " : " << x.second << ")" << ","; o << " }"; return o;}
template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const multiset<T>&obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {o << "["; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "]"; return o;}
template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {o << "(" << obj.first << ", " << obj.second << ")"; return o;}
template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;}
void print_sim_py(void) {cout << endl;}
template <class Head> void print_sim_py(Head&& head) {cout << head;print_sim_py();}
template <class Head, class... Tail> void print_sim_py(Head&& head, Tail&&... tail) {cout << head << " ";print_sim_py(forward<Tail>(tail)...);}

#define print(...) print_sim_py(__VA_ARGS__);
#else
#define print(...);
#endif

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

	ll ans;
	ll n,x,m;

	cin >> n >> x >> m;
	
    vector<ll> sum_a(m+1,0);
	map<ll,ll> mem;

	ll sum = 0;

	ll first_i=0, final_i=0;
    for(ll i=0; i<n; i++){
		print(x)
		if(mem.find(x)!=mem.end()){
			first_i = mem[x];
			final_i = i;
			break;
		}
		sum += x;
		mem[x] = i;
		sum_a[i+1] = sum;
        x = (x*x)%m;
	}

	ll times = 0;
	ll bsec = sum;
	ll sec = 0;
	ll asec = 0;
	ll md = 0;
	if(final_i!=first_i){
		times = (n-first_i)/(final_i - first_i);
		md = (n-first_i)%(final_i - first_i);
		
		print(first_i, final_i)
		bsec = sum_a[first_i];
		sec = sum_a[final_i] - sum_a[first_i];
		asec = sum_a[first_i+md] - sum_a[first_i];
	}

	print(bsec, sec,asec, first_i,final_i, sum, times, md)

	ans = bsec + sec*times + asec;

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


Measured memory_bytes: 7112