akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<vector>
#include<algorithm>
#include<utility>
#include<numeric>
#include<iostream>
#include<array>
#include<string>
#include<sstream>
#include<stack>
#include<queue>
#include<list>
#include<functional>
#include<set>
#include<complex>
#include<complex>
#define _USE_MATH_DEFINES

#include<math.h>
#include<map>

#define INF 200000000

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;

enum
{
	BOTTOM,
	LEFT,
	RIGHT,
	TOP
};

struct P
{
	double x, y;
	P(double x,double y) :x(x), y(y) {}
	P() :P(0, 0) {}
	P operator+(const P& v)const
	{
		return P(x + v.x, y + v.y);
	}
	P operator-(const P& v)const
	{
		return P(x - v.x, y - v.y);
	}
	P operator*(const double v)const
	{
		return P(x*v, y*v);
	}
	bool operator==(const P& v)const
	{
		return abs(x - v.x) <= 0.0000000000001&&abs(y - v.y) <= 0.00000000000001;
	}
	bool operator!=(const P& v)const
	{
		return abs(x - v.x) > 0.0000000000001 || abs(y - v.y) > 0.00000000000001;
	}

	double dot(const P& v)const
	{
		return x*v.x + y*v.y;
	}
	double cross(const P& v)const
	{
		return x*v.y - y*v.x;
	}
	double length()const
	{
		return sqrt(x*x + y*y);
	}
	double length2()const
	{
		return (x*x + y*y);
	}

	P unit()const
	{
		return P(x / length(), y / length());
	}
	
	bool operator<(const P& v)const
	{
		return x<v.x || (x == v.x) && y < v.y;
	}
	bool operator>(const P& v)const
	{
		return x>v.x || (x == v.x) && y > v.y;
	}
};

pair<P,P> cli(double a, double b, double c, double x1, double y1, double r)
{
	double l = a*a + b*b, k = a*x1 + b*y1 + c, d = l*r*r - k*k;
	if (d > 0)
	{
		double ds = sqrt(d), apl = a / l, bpl = b / l, xc = x1 - apl*k, yc = y1 - bpl*k, xd = bpl*ds, yd = apl*ds;
		return make_pair(P(xc - xd, yc + yd), P(xc + xd, yc - yd));
	}
	else
	{
		return make_pair(P(x1 - a*k / l, y1 - b*k / l), P(x1 - a*k / l, y1 - b*k / l));
	}
}

pair<P, P> cci(P p1, P p2, double r1, double r2)
{
	double a = p1.x - p2.x, b = p1.y - p2.y;
	return cli(a, b, 0.5*((r1 - r2)*(r1 + r2) - a*(p1.x + p2.x) - b*(p1.y + p2.y)), p1.x, p1.y, r1);
}

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

	double c1x, c1y, c1r, c2x, c2y, c2r;
	cin >> c1x >> c1y >> c1r >> c2x >> c2y >> c2r;
	P c1(c1x, c1y), c2(c2x, c2y);

	pair<P, P> cps = cci(c1, c2, c1r, c2r);
	if (cps.first > cps.second)
	{
		swap(cps.first, cps.second);
	}

	printf("%.10lf %.10lf %.10lf %.10lf\n", cps.first.x, cps.first.y, cps.second.x, cps.second.y);

	return 0;
}


Measured memory_bytes: 3296
#include <iostream>
#include <iomanip>

using namespace std;

void Cont(){
    int32_t N, M;
    cin >> N;
    cin >> M;
    for(int32_t i=0;i < M;i++){
        int Ai;
        cin >> Ai;
        N -= Ai;
        if(N<0){
            cout << "-1" << "\n";
            return;
        }
    }
    cout << N << "\n";
}


int main()
{
	std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Cont();
}





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

using namespace std;
using ll = long long;

int main() {
    int n, k; cin >> n >> k;
    vector <ll> vec;
    for (int i = 0; i < n; i++) {
        ll x; cin >> x;
        vec.push_back(x);
    }

    sort(vec.begin(), vec.end(), greater <ll>());
    for (int i = 0; i < n && i < k; i++) {
        vec[i] = 0;
    }

    ll sum = 0;
    for (int i = 0; i < n; i++) sum += vec[i];
    cout << sum << endl;
}

Measured memory_bytes: 2420
#include <bits/stdc++.h>
#include <vector>
#include <iostream>
#include<algorithm>
#include<string>
#include <map>
#include <queue>
#include <stack>
#include<set>

#define DIV 1000000007
#define TE 2e5
using namespace std;
using ll = long long;
using ldb = long double;

ll func(ll n, vector<ll>& p) {
	if (n == 0)return 0;
	if (p[n] != 0) return p[n];
	ll temp = n, ones = 0;
	while (temp) {
		if (temp % 2 == 1)ones++;
		temp /= 2;
	}
	p[n] = func(n % ones, p) + 1;
	return p[n];
}


int main() {
	int N; cin >> N;
	string x; cin >> x;
	ll ones = 0;
	for (int i = N - 1; i >= 0; i--) {
		if (x[i] == '1') ones++;
	}
	if (ones == 0)for (int i = 0; i < N; i++) cout << 1 << endl;
	else if (ones == 1) {
		for (int i = 0; i < N; i++) {
			if (x[i] == '1')cout << 0 << endl;
			else {
				if (i != N - 1)	cout << 1 << endl;
				else cout << 2 << endl;
			}
		}
	}
	else {
		vector<ll> bi0(TE + 1, 1), bi1(TE + 1, 1);
		ll m0 = 0, m1 = 0, two0 = 1, two1 = 1;
		for (int i = N - 1; i >= 0; i--) {
			if (x[i] == '1') {
				m0 = (m0 + two0) % (ones + 1);
				m1 = (m1 + two1) % (ones - 1);
			}
			bi0[i] = two0, bi1[i] = two1;
			two0 = (two0 * 2) % (ones + 1);
			two1 = (two1 * 2) % (ones - 1);
		}
		vector<ll> p(TE + 1);
		for (int i = 0; i < N; i++) {
			ll n;
			if (x[i] == '0')
				n = (m0 + bi0[i] + (ones + 1)) % (ones + 1);
			else
				n = (m1 - bi1[i] + (ones - 1)) % (ones - 1);
			cout << func(n, p) + 1 << endl;
		}
	}
}


Measured memory_bytes: 8416
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
#include<cassert>
using namespace std;

typedef long long ll;
const ll mod = 1000000007;
const ll INF = mod * mod;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<string> vs;

int main() {
	int a, b,c;
	cin >> a >> b ;
	if (b == 1)c = 0;
	else c = a - b;
	cout << c << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<math.h>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
using namespace std;

main(){
  int n,d,j;
  cin >> n >> d;
  vector<vector<int>> x(n,vector<int>(d));
  rep(ver,n)rep(hor,d) cin >> x[ver][hor];
  
  int count=0;
  rep(i,n)rep(j,i){
    int ans=0;
    rep(k,d) ans+=pow(abs(x[i][k]-x[j][k]),2);
    rep(k,ans+1) if(k*k==ans) count++;
  }
  cout << count << endl;

}  
  

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef map<int,int> mii;
typedef vector<int>vi;
#define pb push_back
#define sc(n) scanf("%d",&n)
#define lsc(n) scanf("%lld",&n)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(i=0;i<n;i++)
#define rep1(i,n) for(i=1;i<=n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define rev1(i,n) for(i=n;i>0;i--)
#define in insert
#define IT ::iterator
#define pr(n) printf("%d\n",n)
#define lpr(n) printf("%lld\n",n);
int a[100005],memo[100005],n,k;
ll mx=1e18;
ll dp(int i)
{
	ll ans=mx;
	int j;
	if(i==n-1)
	{
		return 0;
	}
	if(memo[i]!=-1)
	{
		return memo[i];
	}
	for(j=i+1;j<=i+k && j<n;j++)
	{
		ans=min(ans,dp(j)+(ll)abs(a[j]-a[i]));
	}
	
	memo[i]=ans;
	return memo[i];
}

int main()
{
	int i;
	cin >> n >> k;
	rep(i,n)
	{
		cin >> a[i];
	}
	memset(memo,-1,sizeof(memo));
	cout << dp(0) << endl;
    return 0;
}


Measured memory_bytes: 10500
#include <vector>
#include <queue>
using i64 = long long;

/*
 * delta(V v, fn (V t, i64 weight))
 * index(V v) -> int
 */
template<class V, class W, class Delta, class Index>
std::vector<i64> dial01(std::size_t N, W inf, V s, Delta delta, Index index) {
  std::vector<i64> dist(N, inf);
  using P = std::pair<V, W>;
  std::deque<P> que;
  dist[index(s)] = 0;
  que.push_back({ s, dist[index(s)]});
  while(!que.empty()) {
    V v = que.front().first;
    W d = que.front().second;
    que.pop_front();
    if(dist[index(v)] < d) continue;
    delta(v, [&](V t, i64 weight) {
        if(dist[index(t)] > dist[index(v)] + weight) {
          dist[index(t)] = dist[index(v)] + weight;
          if(weight == 0) que.push_front({ t, dist[index(t)] });
          else que.push_back({ t, dist[index(t)] });
        }
    });
  }
  return dist;
}

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define rep(i,s,e) for(i64 (i) = (s);(i) < (e);(i)++)
#define all(x) x.begin(),x.end()

template<class F>
struct lattice_delta {
  i64 H, W;
  F f;
  using P = std::pair<i64, i64>;
  lattice_delta(i64 H, i64 W, F f): H(H), W(W), f(f) {}
  template<class Func>
  void operator()(P v, Func func) {
    const static vector<i64> dx { 1, 0, -1, 0 };
    i64 i = v.first;
    i64 j = v.second;
    for(i64 q = 0; q < 2; q++) {
      i64 x = i + dx[q];
      i64 y = j + dx[q ^ 1];
      if(0 <= x && x < H && 0 <= y && y < W) {
        f(P(i, j), P(x, y), func);
      }
    }
  }
};

template<class F>
lattice_delta<F> make_lattice_delta(i64 H, i64 W, F f) { return lattice_delta<F>(H, W, f); }

struct lattice_index {
  i64 H, W;
  using P = std::pair<i64, i64>;
  lattice_index(i64 H, i64 W): H(H), W(W) {}
  i64 operator()(P v) {
    return v.first * W + v.second;
  }
};


int main() {
  cin.tie(nullptr);
  std::ios::sync_with_stdio(false);
  i64 H, W;
  cin >> H >> W;
  vector<string> S(H);
  rep(i,0,H) {
    cin >> S[i];
  }
  using P = std::pair<i64, i64>;
  vector<i64> dx { 1, 0, -1, 0 };
  auto delta = make_lattice_delta(H, W,
      [&](P v, P t, auto func) {
        if(S[v.first][v.second] != S[t.first][t.second] && S[t.first][t.second] == '#') func(t, 1);
        else func(t, 0);
        }
      );
  auto index = lattice_index(H, W);
  auto res = dial01(H * W, (i64)(1e9), P(0, 0), delta, index);
  auto ans = res[index({ H - 1, W - 1 })];
  if(S[0][0] == '#') {
    ans++;
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
import sys
import math

N = int(input())

ALPHABET = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
result = []

def alphabet_decimal(N):
    quotient = math.floor(N / len(ALPHABET))
    surplus = N % len(ALPHABET)
    quotient -= 1 if surplus == 0 else 0
    surplus = len(ALPHABET) if surplus == 0 else surplus
    result.append(surplus)
    if len(ALPHABET) < quotient:
        alphabet_decimal(quotient)
    elif len(ALPHABET) < N:
        result.append(quotient)
    return "".join([ALPHABET[i - 1] for i in reversed(result)])

print(alphabet_decimal(int(N)))


Measured memory_bytes: 9212
#include<cstdio>  
#include<iostream>  
#include<algorithm>  
#include<cstdlib>  
#include<cstring>
#include<string>
#include<climits>
#include<vector>
#include<cmath>
#define LL long long

using namespace std;

inline char nc(){
  static char buf[100000],*p1=buf,*p2=buf;
  if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
  return *p1++;
}

inline void read(int &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

inline void read(LL &x){
  char c=nc(),b=1;
  for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
  for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}

int wt,ss[19];
inline void print(int x){
	if (x<0) x=-x,putchar('-'); 
	if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}
inline void print(LL x){
	if (x<0) x=-x,putchar('-');
	if (!x) putchar(48); else {for (wt=0;x;ss[++wt]=x%10,x/=10);for (;wt;putchar(ss[wt]+48),wt--);}
}

LL n,m;

int main()
{
	cin>>n;
	m=n/11;
	if (n-11*m==0) cout<<2*m<<endl;
	else if (n-11*m>6) cout<<2*m+2<<endl;
	else cout<<2*m+1<<endl;
 
 return 0;
 
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
//#pragma GCC optimize("Ofast")
#define fori(a,b) for(int i=a;i<b;i++)
#define forj(a,b) for(int j=a;j<b;j++)
#define fork(a,b) for(int k=a;k<b;k++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define seto(x,i) memset(x,i,sizeof x)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define pf first
#define ps second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;

const int N=301;
ll n,m,L,q,a,b,c,dist[N][N],df[N][N];
bool vis[N];
vector<pii> gr[N];

void dfs()
{
    int v;
    fori(0,n)
    {
        v=300;
        forj(0,n)
            if(!vis[j]&&(dist[a][v]>dist[a][j]||dist[a][v]==dist[a][j]&&df[a][v]<df[a][j]))
                v=j;
        vis[v]=true;
        for(auto j:gr[v])
        {
            if(df[a][v]>=j.ps&&(dist[a][j.pf]>dist[a][v]||dist[a][j.pf]==dist[a][v]&&df[a][j.pf]<df[a][v]-j.ps))
            {
                dist[a][j.pf]=dist[a][v];
                df[a][j.pf]=df[a][v]-j.ps;
            }
            if(df[a][v]<j.ps&&j.ps<=L&&(dist[a][j.pf]>dist[a][v]+1||dist[a][j.pf]==dist[a][v]+1&&df[a][j.pf]<L-j.ps))
            {
                dist[a][j.pf]=dist[a][v]+1;
                df[a][j.pf]=L-j.ps;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("", "r", stdin);
    cin>>n>>m>>L;
    fori(0,m)
    {
        cin>>a>>b>>c; a--; b--;
        gr[a].push_back({b,c});
        gr[b].push_back({a,c});
    }
    fori(0,n)
    {
        forj(0,N)
        {
            dist[i][j]=INF;
            df[i][j]=-1;
        }
        a=i; dist[a][a]=0; df[a][a]=L; seto(vis,0);
        dfs();
    }
    cin>>q;
    fori(0,q)
    {
        cin>>a>>b; a--; b--;
        cout<<(dist[a][b]==INF? -1: dist[a][b])<<"\n";
    }
    return 0;
}


Measured memory_bytes: 4352
var N;
function c753(S) {
    var s = S - 0;
    if (s > N) return 0;
    var a753 = new Array(3).fill(0);
    var f = S.length >= 3 && S.split('').every(function(value) { 
        switch (value - 0) {
            case 7: 
                ++ a753[0];
                return true;
            case 5:
                ++ a753[1];
                return true;
            case 3:
                ++ a753[2];
                return true;
            default:
            return false;
            }
    });
    var result = (f && a753.every(function(value) { return value > 0; })) ? 1 : 0;
    for (var c of ['7', '5', '3']) result += c753(S + c);
    return result;
}

function Main(input) {
    N = input.split("\n")[0] - 0;
    var count = c753("");
    console.log(count);
}

Main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 10992
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <cmath>
#include <climits>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <utility>
#include <vector>
#include <functional>
#include <algorithm>

using namespace std;

#define cin_desync()                      \
	do {                                  \
		ios_base::sync_with_stdio(false); \
		cin.tie(0);                       \
	} while (0)                           \

#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
	cerr << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');
	cerr.write(names, comma - names) << " : " << arg1 << " | ";
	__f(comma + 1, args...);
}

#else
#define trace(...)
#endif // ifndef ONLINE_JUDGE

typedef long double ld;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int max_N = 2e5 + 10;
const int max_B = 25;

ll xor_pref[max_N], pref[max_N];

int main()
{
    cin_desync();

    int N;
    cin >> N;
    for (int i = 1; i <= N; ++i) {
        int x;
        cin >> x;

        xor_pref[i] = xor_pref[i - 1] ^ x;
        pref[i] = pref[i - 1] + x;
    }

    ll ans = 0;
    for (int i = 1; i <= N; ++i) {
        int low = i, high = N, best = i;
        while(low <= high) {
            int mid = (low + high) >> 1;
            int xor_sum = xor_pref[mid] ^ xor_pref[i - 1];
            ll sum = pref[mid] - pref[i - 1];

            if (xor_sum == sum) {
                best = mid;
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        ans += (best - i + 1);
    }

    cout << ans << endl;
}


Measured memory_bytes: 3456
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define ll long long
#define vi vector<int>
#define pii pair<int,int>
#define F first
#define S second
#define pb push_back
#define forn(b) for(int i = 0; i < b; i++)
#define rforn(b) for(int i = b - 1 ;i >= 0; i--)
#define It(m) for(auto it = m.begin(); it != m.end(); it++)
#define N 500500
#define PI 3.14159265358979323846264338327950L
#define speed ios_base :: sync_with_stdio(0);cin.tie(0);cout.tie(0);
    
const ll mod = (ll)1e9 + 7;
    
int main(){
    speed;
    string s; cin >> s;
    string ss = "";
    for(int i = s.size() - 1; i >= 0; i--) {
        ss += s[i];
        if(ss == "maerd" || ss == "remaerd" || ss == "esare" || ss == "resare") {
            ss = "";
        }
    }
    if(ss.size() == 0) {
        cout << "YES";
    }
    else {
        cout << "NO";
    }
    return 0;
}

Measured memory_bytes: 592
S = input()
N = len(S)
mod = 10 ** 9 + 7
dp = [[0] * 13 for _ in range(N + 1)]

dp[0][0] = 1
for i in range(N):
    s = S[i]
    if s == "?":
        for j in range(10):
            for k in range(13):
                dp[i + 1][(10 * k + j) % 13] += dp[i][k]
                dp[i + 1][(10 * k + j) % 13] %= mod
    else:
        j = int(s)
        for k in range(13):
            dp[i + 1][(10 * k + j) % 13] += dp[i][k]
            dp[i + 1][(10 * k + j) % 13] %= mod

print(dp[N][5] % mod)


Measured memory_bytes: 64032
#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <stack>
#include <tuple>
#include <bitset>
#include <algorithm>
#include <functional>
#include <utility>
#include <iomanip>

#define int long long int
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() )

using namespace std;

typedef pair<int, int> P;

const int INF = 1e15;
const int MOD = 1e9+7;

template <typename T>
using vector2 = vector<vector<T>>;
template <typename T>
vector2<T> initVec2(size_t n0, size_t n1, T e = T()){
    return vector2<T>(n0, vector<T>(n1, e));
}

template <typename T>
using vector3 = vector<vector<vector<T>>>;
template <typename T>
vector3<T> initVec3(size_t n0, size_t n1, size_t n2, T e = T()){
    return vector3<T>(n0, vector2<T>(n1, vector<T>(n2, e)));
}

class BinaryTrie{
    struct node{
        int d, l, r;
        node(int d) : d(d) {
            l = r = -1;
        }
    };

    public:
        vector<node> nodes;

        BinaryTrie(){
            nodes.push_back(node(0));
        }

        void add(string& s, int id){
            while(SZ(s) > nodes[id].d){
                if(s[nodes[id].d] == '0'){
                    if(nodes[id].l == -1){
                        nodes[id].l = SZ(nodes);
                        nodes.push_back(node(nodes[id].d + 1));
                    }
                    id = nodes[id].l;
                }else{
                    if(nodes[id].r == -1){
                        nodes[id].r = SZ(nodes);
                        nodes.push_back(node(nodes[id].d + 1));
                    }
                    id = nodes[id].r;
                }
            }
        }
};

int grundy(int h){
    if(h == 0){
        return 0;
    }

    int x = 1;
    while(h % (x * 2) == 0){
        x *= 2;
    }
    return x;
}

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

    int n, l;
    cin >> n >> l;

    BinaryTrie trie;
    rep(i, n){
        string s;
        cin >> s;
        trie.add(s, 0);
    }

    int sum = 0;
    stack<int> st;
    st.push(0);
    while(not st.empty()){
        int id = st.top();
        st.pop();

        if(trie.nodes[id].l == -1 && trie.nodes[id].r == -1){
            continue;
        }

        if(trie.nodes[id].l != -1){
            st.push(trie.nodes[id].l);
        }else{
            int h = l - trie.nodes[id].d;
            sum ^= grundy(h);
        }
        if(trie.nodes[id].r != -1){
            st.push(trie.nodes[id].r);
        }else{
            int h = l - trie.nodes[id].d;
            sum ^= grundy(h);
        }
    }

    cout << (sum == 0 ? "Bob" : "Alice") << endl;


    return 0;
}


Measured memory_bytes: 4916
# B - Unplanned Queries
n,m=map(int,input().split())
cnt=[0]*n
G=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    cnt[a-1]+=1
    cnt[b-1]+=1
for c in cnt:
    if c%2!=0:
        print('NO')
        exit()
print('YES')


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

bool is_sqr(int n) {
    for (int i = 1; i * i <= n; i++) {
        if (i * i == n) return true;
    }
    return false;
}

int main(){
    string a,b; cin >> a >> b;
    string ab = a + b;
    int n = stoi(ab);
    if  (is_sqr(n)) puts("Yes");
    else puts("No");
}

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

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
    int n;
    cin >> n;
    map<string, int> mp;
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        mp[s]++;
    }
    int c = 0;
    for(auto&& i : mp){
        c = max(c, i.second);
    }
    for(auto&& i : mp){
        if(c == i.second){
            cout << i.first << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 25216
#include <bits/stdc++.h>
using namespace std;
 
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(n);i--)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define Cout(n) cout<<(n)<<endl
#define INF 1000000000000000000LL

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;
typedef vector<string> vs;
const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << ", ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

ll gcd(ll x, ll y) { return (y == 0) ? x : gcd(y, x % y); }
ll lcm(ll x, ll y) { return x * y / gcd(x, y); }

int main()
{
	string s;
	cin >> s;
	Eunique(s);
	cout << SIZE(s)-1 << endl;
	return 0;
}


Measured memory_bytes: 512
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

vector<string> strs;

void generate_str(int itr, string str, char largest) {
    if (itr == 0) {
        strs.push_back(str);
        return;
    }

    for (char c = 'a'; c <= largest; c++) {
        generate_str(itr - 1, str + c, largest);
    }

    char new_largest = largest + 1;
    generate_str(itr-1, str + new_largest, new_largest);
}

int main() {
    int N; cin >> N;
    string str = "a";
    generate_str(N-1, str, 'a');
    for (int i = 0; i < strs.size(); i++) cout << strs[i] << endl;
    return 0;
}

Measured memory_bytes: 7796
#include<bits/stdc++.h>
#include<tr1/unordered_map>
#define pb push_back
#define pii pair<int,int>
#define SZ(x) (int)x.size()
#ifdef __linux__
#define getchar getchar_unlocked
#endif
#define mem(a,b) memset(a,b,sizeof(a))
#define  For(i,a,b) for(int i=a,i##E=b;i<=i##E;++i)
#define rFor(i,a,b) for(int i=a,i##E=b;i>=i##E;--i)
typedef long long LL;
using namespace std;
const int N=210;
const int inf=0x3f3f3f3f;
template<typename T>inline bool chkmin(T &a,const T &b){return a>b?a=b,1:0;}
template<typename T>inline bool chkmax(T &a,const T &b){return a<b?a=b,1:0;}
template<typename T>inline void read(T &x)
{
	x=0;int _f(0);char ch=getchar();
	while(!isdigit(ch))_f|=(ch=='-'),ch=getchar();
	while( isdigit(ch))x=x*10+ch-'0',ch=getchar();
	x=_f?-x:x;
}
inline void file()
{
#ifdef ztzshiwo
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
}
int A,B,n,D[N][N],d[N][N],G[N][N];
int main()
{
	file();
	read(A),read(B);
	n=100;
	For(i,1,A)For(j,1,B)read(d[i][j]);
	For(i,0,n)
		For(j,0,n)
			For(a,1,A)
				For(b,1,B)
				{
					//printf("(%d %d %d %d) %d\n",i,j,a,b,d[a][b]-a*i-b*j);
					chkmax(D[i][j],d[a][b]-a*i-b*j);
				}
	For(a,1,A)
		For(b,1,B)
		{
			G[a][b]=inf;
			For(i,0,n)
				For(j,0,n)
					chkmin(G[a][b],D[i][j]+a*i+b*j);
			if(G[a][b]!=d[a][b]){puts("Impossible");exit(0);}
		}
	puts("Possible");
	n=101;
	printf("%d %d\n",2*n,n*n+2*n-2);
	For(i,2,n)printf("%d %d %c\n",i-1,i,'X');
	For(i,2,n)printf("%d %d %c\n",n+i,n+i-1,'Y');
	For(i,1,n)For(j,1,n)printf("%d %d %d\n",i,j+n,D[i-1][j-1]);
	printf("%d %d\n",1,n+1);
	return 0;
}


Measured memory_bytes: 384
# from fractions import gcd
# mod = 10 ** 9 + 7
# N = int(input())
# a = list(map(int,input().split()))
# a,b,c = map(int,input().split())
# ans = [0] * N
# math.ceilで切り上げ
# dp = [[0] * 4 for i in range(3)] #2次元配列初期化
# dp = [[[0] * 2 for i in range(3)] for j in range(5)]
# (ord('A'))でASCII出力 Aは65
import math
import statistics
import string


def intinput():
    return int(input())
def listintinput():
    return list(map(int, input().split()))
def splitintinput():
    return map(int, input().split())
def factorialsurplus(x, y, z):  # xからyまでの階乗をzで割ったあまりを求める
    ret = 1
    for i in range(x, y + 1):
        ret = (ret * i) % z
    return (ret)
def isprime(x):
    if x == 1:
        return False
    if x == 2:
        return True
    sq = int(math.sqrt(x))
    for i in range(2,sq+1):
        if x % i == 0:
            return False
    return True
def hcfnaive(a,b):#最大公約数 math.gcdが使えない時の手段として入れとく。pythonが更新されたらいらなくなるはず
    if(b==0):
        return a
    else:
        return hcfnaive(b,a%b)

A, B = splitintinput()

for i in range(100001):
    if int(i * 0.08) == A and int(i*0.1) == B:
        print(i)
        break
else:
    print(-1)

Measured memory_bytes: 5380
#include<iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    if(a > b)
    {
        cout << "a > b" << endl;
    }
    else if(a < b)
    {
        cout << "a < b" << endl;
    }
    else
    {
        cout << "a == b" << endl;
    }
    return 0;
}

Measured memory_bytes: 1156
def main():
    n = int(input())
    robots = []
    for _ in range(n):
        x, l = map(int, input().split())
        robots.append((x-l, x+l))
    robots.sort(key=lambda x: x[1])
    count = 1
    robot = robots[0]
    for r in robots:
        if robot[1] <= r[0]:
            robot = r
            count += 1
    print(count)


if __name__ == "__main__":
    main()


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

using namespace std;
#define INF 1e10

struct Edge{
    int from;
    int to;
    int cost;
};


bool bellmanFord(vector<long> &d,
                const vector<Edge> edges,
                const int &V,
                const int &E)
{
    bool is_negativeloop = false;
    for(int i = 0;i < V;i++){
        for(int j = 0;j < E;j++){
            Edge current_edge = edges[j];
            if( d[current_edge.from] != INF && d[current_edge.to] > d[current_edge.from] + current_edge.cost){
                d[current_edge.to] = d[current_edge.from] + current_edge.cost;
                if(i == V-1) is_negativeloop = true;
            }
        }
    }
    return is_negativeloop;
}

int main()
{
    // ----- Input ----- //
    int V,E,r;
    int s,t;

    cin >> V >> E >> r;
    Edge temp;
    vector<Edge> edges; 
    vector<long> d(V,INF);
    
    for(int i = 0;i < E;i++){
        cin >> temp.from >> temp.to >> temp.cost;
        edges.push_back(temp);
    }
    d[r] = 0;

    bool is_negative_loop = bellmanFord(d,edges,V,E);
    if(is_negative_loop) cout << "NEGATIVE CYCLE" << endl;
    else{
        for(int i = 0;i < V;i++){
            if(d[i] == INF) cout << "INF" <<endl; 
            else cout << d[i] <<endl;
        }
    }

    return 0;
}




Measured memory_bytes: 3184
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 k = sc.nextInt();
        long[] h = new long[n];

        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }

        Arrays.sort(h);

        long diff = Long.MAX_VALUE;
        for (int i = 0; i <= n-k; i++) {
            diff = Math.min(diff, h[i+k-1] - h[i]);
        }

        System.out.println(diff);
    }
}



Measured memory_bytes: 50104
#include<stdio.h>
int main()
{
    int A,B,l;
    scanf("%d %d",&A,&B);
    A+B;
    A-B;
    A*B;
    l=A+B;
    if(A-B>l)
    l=A-B;
    if(A*B>l)
    l=A*B;
    printf("%d",l);
    return 0;
}

Measured memory_bytes: 1728
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace contest_Csharp
{
    class Program
    {


        static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            var vals = Console.ReadLine().Split(' ')
                .Select(x => int.Parse(x)).ToList();

            int H1 = vals[0];
            int M1 = vals[1];
            int H2 = vals[2];
            int M2 = vals[3];
            int K = vals[4];
            int ans = H2*60+M2-(H1*60+M1)-K;

            

            Console.WriteLine(ans);
            Console.Out.Flush();

        }



    }

}


Measured memory_bytes: 28276
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<map>
using namespace std;
int main() {
  long long x,y,ans=2000000005;
  cin >> x >> y;
  if(x<=y) {
    ans=min(ans,y-x);
  }
  if(-x<=y) {
    ans=min(ans,y+x+1);
  }
  if(x<=-y) {
    ans=min(ans,-y-x+1);
  }
  if(-x<=-y) {
    ans=min(ans,-y+x+2);
  }
  cout << ans << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <array>
#include <climits> // INT_MAX, LONG_MAX, LLONG_MAX, UINT_MAX, ULONG_MAX, ULLONG_MAX
#include <cmath>
#include <cstdint>
#include <cstring> // memset
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>

#define ALL(x) (x).begin(), (x).end()
#define INF 1e9
#define LOG(x) cout << #x << " = " << (x) << endl
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)

using namespace std;

int main() {
    ios::sync_with_stdio(false);

    set<int> s;
    REP(i, 3) {
        int ai;
        cin >> ai;
        s.insert(ai);
    }
    cout << s.size() << endl;
    
    return 0;
}


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

int N;
double x[10], y[10];
double d[10][10];

double distance(double x1, double y1, double x2, double y2) {
    double dx = x1 - x2;
    double dy = y1 - y2;
    return sqrt(dx*dx + dy*dy);
}

ll fact(int n) {
    ll ret = 1;
    for (int i = 2; i <= n; i++) {
        ret *= i;
    }
    return ret;
}

int main() {
     cout << fixed << setprecision(10);
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> x[i] >> y[i];
    }

    ll fact_n = fact(N-1);

    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            d[i][j] = distance(x[i], y[i], x[j], y[j]);
        }
    }

    double ans = 0;
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            ans += (d[i][j] * 2 * fact_n );
        }
    }

    ans /= fact_n;
    ans /= N;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cstring>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

int H, W, K, ans = 1e9;
char s[15][1005];
int g[15][1005];

inline int getSum(int a, int b, int c, int d){
    return g[c][d] - g[a-1][d] - g[c][b-1] + g[a-1][b-1];
}

bool cut[15];
int sum[15];
void dfs(int x, int cnt){
    if(x == H){
        for(int i = 1; i <= H; i++) sum[i] = 0;
        cut[H] = 1;
        for(int j = 1; j <= W; j++){
            int tsum = 0;
            for(int i = 1; i <= H; i++){
                tsum += s[i][j] - '0';
                if(tsum > K)    return;
                if(cut[i])  tsum = 0;
            }

            bool ok = true;
            int t = 0;
            for(int i = 1; i <= H; i++) sum[i] += s[i][j] - '0';
            for(int i = 1; i <= H; i++){
                t += sum[i];
                if(t > K)   ok = false;
                if(cut[i])  t = 0;
            }
            if(!ok){
                cnt++; j--;
                for(int i = 1; i <= H; i++) sum[i] = 0;
            }
        }
        ans = min(ans, cnt);
        return;
    }
    dfs(x+1, cnt);
    cut[x] = 1;
    dfs(x+1, cnt+1);
    cut[x] = 0;
}


int main(){
    read(H, W, K);
    for(int i = 1; i <= H; i++){
        scanf("%s", s[i]+1);
        for(int j = 1; j <= W; j++)
            g[i][j] = s[i][j] - '0';
    }
    for(int i = 1; i <= H; i++)
        for(int j = 1; j <= W; j++)
            g[i][j] += g[i-1][j] + g[i][j-1] - g[i-1][j-1];
    dfs(1, 0);
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep1(i, n) for (int i = 1; i <= (int)(n); i++)
#define rev(i, n) for(int i = (int)(n - 1); i >= 0; i--)
#define rev1(i, n) for(int i = (int)(n); i > 0; i--)
#define pb push_back
#define all(v) ((v).begin(), (v).end())
using ll = long long;
using P = pair<int, int>;
/* ------------------------------------------------ */
ll fact(int i) {       //階乗
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
ll gcd(ll a, ll b) {        //最大公約数
    if(b == 0) return a;
    return gcd(b, a % b); 
}
ll lcm(ll a, ll b) {      //最小公倍数
    return a * b / gcd(a, b);
}
int keta(ll n) {        //桁数を求める
    if(n == 0) return 1;
    int count = 0;
    while(n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
ll ketasum(ll n) {    //各桁の和
    ll sum = 0;
    while(n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
/* ------------------------------------------------ */

int main() {
    int k, a, b;
    cin >> k >> a >> b;
    if(a%k==0||b%k == 0) {
        cout <<"OK" << endl;
        return 0;
    }
    if(-ceil(a/k)+floor(b/k) > 0) cout << "OK" << endl;
    else cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3572
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <utility>
#include <iomanip>
#include <cmath>
#include <functional>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);++i)
#define rep(i,a,b) for(int i=a;i<(b);++i)
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
using ll = long long;
constexpr ll INF = 1LL << 60;
constexpr ll MOD = 1e9 + 7;

int main() {
    cin.tie(0); ios_base::sync_with_stdio(false);
    int N;cin>>N;
    vector<ll> a(N);
    REP(i,N) cin >> a[i];
    ll ans = 0;
    REP(i,N){
        rep(j,i+1,N){
            chmax(ans,abs(a[i]-a[j]));
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#define __USE_MINGW_ANSI_STDIO 0
#include <iostream>
#include <string>
#include <vector>
#include <stdio.h>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <set>
#include <numeric>
#include <bitset>
#include <map>
#include <limits.h>

using namespace std;

/// 各桁の和
int sumdigit(int x){
   int sum = 0;
    while(x != 0){
        sum += x % 10;
        x /= 10;    
    }
    return sum;
}
/// 最大公約数 
int gcd(int x, int y){
      if(x<y){
          int temp = x;
          x = y;
          y = temp;
      }
      int r = x % y;
       while(r!=0){
           x = y;
           y = r;
           r = x % y;
       }
      return y;
   }



int main(){
int N , M;
cin >> N >> M;
vector<pair<int,int>> cost(N);
for(int i = 0; i < N; i++){
    cin >> cost[i].first >> cost[i].second;
    
}
sort(cost.begin(),cost.end());
long long yen = 0;
int num = 0;

for(int i = 0; i < N; i++){
    for(int j = 1; j <= cost[i].second; j++ ){
        yen += cost[i].first;
        num++;
        if(num == M){
            cout << yen << endl;
            return 0 ;
        }
    }
}
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
    int K,N;
    cin >> K >> N;
    vector<int> A(N);
    for (int i = 0; i < N; i++)
    {
        cin >> A.at(i);
    }
    vector<int> Length(N, 0);
    for (int i = 0; i < N; i++)
    {
        int po = i+1;
        int po_ = i-1;
        if (po >= N)po = po-N;
        if (po_ < 0)po_ = po_+N;
        int popo = A.at(po) - A.at(i);
        if (popo < 0) popo = popo+K; 
        int popo_ = A.at(i) - A.at(po_);
        if (popo < 0) popo_ = popo_+K;
        int poi = min(abs(K-popo),abs(K-popo_));
        Length.at(i) = Length.at(i) + poi;
    }
    int out = *min_element(Length.begin(),Length.end());
    cout << out;
}

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

int main() {
  int n, k;
  cin >> n >> k;
  vector<int> l(n);
  
  for (int i = 0; i < n; i++) {
    cin >> l.at(i);
  }
  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());
  
  int sum = 0;
  for (int i = 0; i < k; i++) {
    sum += l.at(i);
  }
  
  cout << sum << endl;
  
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
//using P = pair<int,int>;
//pow(x,n)
//cout << fixed << setprecision(桁数);
//string = to_string(数値)
//int = stoi(文字列)
//(int)(char-'0')
//string = itoa(int)
//円周率: M_PI


int main() {
    int n; cin>>n;
    vector<int> h(n+1);
    rep(i,n) cin>>h[i+1];

    vector<int> sum(n+1,INF);
    sum[0]=0; sum[1]=0;

    sum[2]=abs(h[2]-h[1]);
    rep(i,n-2){
        sum[i+3]=abs(h[i+3]-h[i+2])+sum[i+2];
        chmin(sum[i+3],abs(h[i+3]-h[i+1])+sum[i+1]);
    }
    cout << sum[n] << endl;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cmath>

using namespace std;

int main(){
    int n;
    cin >> n;
    int array[100];
    bool flag=true;
    int count=0;
    for(int i=0;i<n;i++){
        cin >> array[i];
    }
    for(int i=0;i<n;i++){
        int minj=i;
        for(int j=i;j<n;j++){
            if(array[minj]>array[j]){
                minj=j;
            }
        }
        if(array[i]!=array[minj]){
            int tmp=array[i];
            array[i]=array[minj];
            array[minj]=tmp;
            count++;
        }
    }
    for(int i=0;i<n;i++){
        cout << array[i];
        if(i!=n-1){
            cout << " ";
        }
    }
    cout << endl;
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3100
//2018年  3月 24日 土曜日 03:23:51 JST
#include <bits/stdc++.h>
#define ADD(a, b) a = (a + ll(b)) % mod
#define MUL(a, b) a = (a * ll(b)) % mod
#define MAX(a, b) a = max(a, b)
#define MIN(a, b) a = min(a, b)
#define rep(i, a, b) for(int i = int(a); i < int(b); i++)
#define rer(i, a, b) for(int i = int(a) - 1; i >= int(b); i--)
#define all(a) (a).begin(), (a).end()
#define sz(v) (int)(v).size()
#define pb push_back
#define sec second
#define fst first
#define debug(fmt, ...) Debug(__LINE__, ":", fmt, ##__VA_ARGS__)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef pair<int, pi> ppi;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> mat;
typedef complex<double> comp;
void Debug() {cout << '\n'; }
template<class FIRST, class... REST>void Debug(FIRST arg, REST... rest){
	cout<<arg<<" ";Debug(rest...);}
template<class T>ostream& operator<<(ostream& out,const vector<T>& v) {
	out<<"[";if(!v.empty()){rep(i,0,sz(v)-1)out<<v[i]<<", ";out<<v.back();}out<<"]";return out;}
template<class S, class T>ostream& operator<<(ostream& out,const pair<S, T>& v){
	out<<"("<<v.first<<", "<<v.second<<")";return out;}
const int MAX_N = 200010;
const int MAX_V = 100010;
const double eps = 1e-6;
const ll mod = 1000000007;
const int inf = 1 << 29;
const ll linf = 1LL << 60;
const double PI = 3.14159265358979323846;
///////////////////////////////////////////////////////////////////////////////////////////////////

int N;
int A[MAX_N];
vector<int> G[MAX_N];

int loop(int v, int p) {
	int cnt = 0, ccnt = 0;
	int mv = 0;
	rep(i, 0, sz(G[v])) {
		int n = G[v][i];
		if(n == p) continue;
		int tmp = loop(n, v);
		// debug(n, tmp);
		if(tmp == inf) return inf;
		cnt += tmp;
		MAX(mv, tmp);
		ccnt++;
	}
	if(ccnt == 0) return A[v];
	else if(ccnt == 1) {
		if(A[v] != cnt) return inf;
		else {
			if(v == 0) return 0;
			else return cnt;
		}
	}
	else {
		if(cnt - A[v] < 0 || 2 * A[v] - cnt < 0) return inf;
		else {
			if(cnt - A[v] > cnt - mv) return inf;
			return 2 * A[v] - cnt;
		}
	}
}

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--; b--;
		G[a].pb(b);
		G[b].pb(a);
	}
	if(loop(0, -1) != 0) cout << "NO\n";
	else cout << "YES\n";
}

int main() {
#ifndef LOCAL
	ios::sync_with_stdio(false);
    cin.tie(0);
#endif
    cout << fixed;
	cout.precision(20);
	srand((unsigned int)time(NULL));
#ifdef LOCAL
	//freopen("in.txt", "wt", stdout); //for tester
    freopen("in.txt", "rt", stdin);
#endif	
	solve();
#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
	return 0;
}



Measured memory_bytes: 15104
#include <bits/stdc++.h>
using namespace std;
using LL = int64_t;
using Uint = uint32_t;
constexpr int INF = 1e9;
constexpr LL INFLL = 1e18;
constexpr int MOD = 998244353;
constexpr int MAX_N = 200000;
int n;
string x;
int cnt[MAX_N + 1];
void solve() {
    cin >> n >> x;
    for (int times = 1; times <= n; ++times)
        if (n % times == 0 && times % 2 == 1) {
            int len = n / times;
            string s = x.substr(0, len);
            for (char c : s)
                cnt[times] = (2 * cnt[times] + c - '0') % MOD;
            string invs = s;
            for (char &c : invs)
                c ^= 1;
            string t;
            for (int i = 0; i < times; ++i)
                if (~i & 1)
                    t += s;
                else
                    t += invs;
            if (t <= x)
                cnt[times] = (cnt[times] + 1) % MOD;
        }
    int ans = 0;
    for (int i = n; i >= 1; --i)
        if (n % i == 0 && i % 2 == 1) {
            for (int j = 3 * i; j <= n; j += 2 * i)
                if (n % j == 0)
                    cnt[i] = (cnt[i] - cnt[j] + MOD) % MOD;
            ans = (ans + 1ll * cnt[i] * n / i) % MOD;
        }
    cout << 2 * ans % MOD << "\n";
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T = 1;
    // cin >> T;
    for (int i = 1; i <= T; ++i)
        solve();
    return 0;
}

Measured memory_bytes: 1172
#include <iostream>
using namespace std;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;

const int MAX_N = 110;
const int MAX_V = 100100;

int N;
long long W, weight[MAX_N], value[MAX_N];

long long dp[MAX_N][MAX_V];

int main() {
    cin >> N >> W;
    for (int i= 0; i < N; i++) cin >> weight[i] >> value[i];

    for (int i = 0; i < MAX_N; i++) for (int j = 0; j < MAX_V; j++)  dp[i][j] = INF;

    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        for (int sum_v = 0; sum_v < MAX_V; sum_v++) {
            if (sum_v - value[i] >= 0) chmin(dp[i + 1][sum_v], dp[i][sum_v - value[i]] + weight[i]);
            chmin(dp[i + 1][sum_v], dp[i][sum_v]);
        }
    }

    long long res = 0;
    for (int sum_v = 0; sum_v < MAX_V; sum_v++) {
        if (dp[N][sum_v] <= W) res = sum_v;
    }
    cout << res << endl;
    return 0;
}

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

using namespace std;

#define pb push_back
#define mk make_pair
#define mod 1000000007
#define ff first
#define ss second

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

ll modpow(ll a, ll b){

    ll ans=1;
    while(b){
        if(b&1){
            ans=(ans*a)%mod;
        }
        a=(a*a)%mod;
        b=b/2;
    }
    return ans;
}

vector<int> vt[100010];

int ans[100010];
int in[100010];

int main(){


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

    for(int i = 0; i < m; i++) {
        int x,y;
        cin>>x>>y;
        vt[x].pb(y);
        in[y]++;
    }

    queue<int> q;

    int finAns = 0;

    for(int i = 1; i <= n; i++) {
        if(in[i] == 0) q.push(i);
    }

    while(!q.empty()) {
        int element = q.front();
        q.pop();

        for(int i = 0; i < vt[element].size(); i++) {
            ans[vt[element][i]] = max(ans[vt[element][i]], ans[element] + 1);
            finAns = max(finAns, ans[vt[element][i]]);
            in[vt[element][i]]--;
            if(in[vt[element][i]] == 0) {
                q.push(vt[element][i]);
            }
        }
    }
    cout<<finAns<<endl;

}


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

  int N;
  int A[210];

int main(){
    cin >> N;
	for(int i=0;i<N;i++) cin >> A[i];
//////////////////
   int count=0;
   while(true){
     bool exist_odd=false;
   	for(int i=0;i<N;i++){
    	 if(A[i]%2!=0) exist_odd=true; 
   	}
     if(exist_odd==true) break;
    for(int i=0;i<N;i++) A[i]/=2;
    count++;
   }
  cout << count <<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <set>
#include <cmath>
#include <tuple>
#include <cstring>
#include <map>
#include <iomanip>
#include <ctime>
#include <complex>
#include <cassert>
#include <climits>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define _ << " " <<
#define all(X) (X).begin(), (X).end()
#define len(X) (X).size()
#define Pii pair<int, int>
#define Pll pair<ll, ll>
#define Tiii tuple<int, int, int>
#define Tlll tuple<ll, ll, ll>

class SegTree_Delay {
public:
    int f;
    int INIT = INT_MAX;
    vector<int> dat, lazy;

    SegTree_Delay(int n) {
        f = 1;
        while (f < n) f *= 2;
        dat.assign(2 * f, INIT);
        lazy.assign(2 * f, INIT);
    }

    void eval(int k) {
        if (lazy[k] == INIT) return;
        if (k < f - 1) {
            lazy[2 * k + 1] = lazy[k];
            lazy[2 * k + 2] = lazy[k];
        }
        dat[k] = lazy[k];
        lazy[k] = INIT;
    }

    void update(int a, int b, int x, int k, int l, int r) {
        eval(k);
        if (a <= l && r <= b) {
            lazy[k] = x;
            eval(k);
        }
        else if (a < r && l < b) {
            update(a, b, x, k * 2 + 1, l, (l + r) / 2);
            update(a, b, x, k * 2 + 2, (l + r) / 2, r);
            dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }

    void update(int a, int b, int x) {
        update(a, b, x, 0, 0, f);
    }

    int query(int a, int b) {
        return query(a, b, 0, 0, f);
    }

    int query(int a, int b, int k, int l, int r) {
        eval(k);
        if (r <= a || b <= l) return INIT;
        if (a <= l && r <= b) return dat[k];
        else {
            int vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            int vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return min(vl, vr);
        }
    }
};


int main() {
    int n, q;
    cin >> n >> q;
    SegTree_Delay st = SegTree_Delay(n);
    while (q--) {
        int m;
        cin >> m;
        if (m) {
            int s, t;  cin >> s >> t;
            cout << st.query(s, t + 1) << endl;
        }
        else {
            int s, t, x;
            cin >> s >> t >> x;
            st.update(s, t + 1, x);
        }
    }
}



Measured memory_bytes: 4956