akhauriyash/Code-Regression huggingface dataset:
#pragma region include
#include "bits/stdc++.h"
#define ALL(obj) (obj).begin(),(obj).end()
#define RALL(obj) (obj).rbegin(),(obj).rend()
#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)
#define FOR(i,n,m) for(int i = (int)(n); i < int(m); i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int MOD = 1e9 + 7;
const int INF = 1e9;
const ll LLINF = 4e18;
void input() {}
template<typename... R> void input(int& f, R&... r) { scanf("%d", &f); input(r...); }
template<typename... R> void input(double& f, R&... r) { scanf("%lf", &f); input(r...); }
template<typename... R> void input(ll& f, R&... r) { scanf("%lld", &f); input(r...); }
template<typename... R> void input(char& f, R&... r) { scanf("%c", &f); input(r...); }
template<typename T, typename... R> void input(vector<T>& f, R&... r) { REP(i, f.size())input(f[i]); input(r...); }
#pragma endregion

struct mint {
private:
    ll x;
public:
    mint(ll x = 0) :x(x%MOD) {}
    mint& operator+=(const mint a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const mint a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint a) const{
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint a) const{
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint a) const{
        mint res(*this);
        return res *= a;
    }
    friend ostream& operator<<(ostream& os, const mint& n) {
        return os << n.x;
    }
};

//pow
template<typename T,typename U>
T pow(T n, U k) {
    T x = 1;
    while (k > 0) {
        if (k & 1) {
            x *= n;
        }
        n *= n;
        k >>= 1;
    }
    return x;
}

// comb (前計算O(NlogMOD) クエリO(1))
vector<mint> FACT, IFACT;

//template<typename T>
mint comb(int n, int r) {
    if (n < 0 || r < 0 || r > n) return 0;
    if (r > n / 2) r = n - r;
    return FACT[n] * IFACT[n - r] * IFACT[r];
}

int main() {
    int N, K; input(N, K);
    int MAX_N = N;
    FACT.resize(MAX_N + 1);
    IFACT.resize(MAX_N + 1);
    FACT[0] = 1;
    IFACT[0] = 1;
    for (int i = 1; i <= MAX_N; i++) {
        FACT[i] = FACT[i - 1] * i;
        IFACT[i] = pow(FACT[i], MOD - 2);
    }
    FOR(i, 1, K + 1) {
        cout << comb(K - 1, i - 1) * comb(N - K + 1, i) << endl;
    }
    getchar(); getchar();
}

Measured memory_bytes: 256
n, k = map(int, input().split())
l = []
for i in range(n):
    l.append(int(input()))

root = [1]*n

for i in range(n)[-2::-1]:
    num = 0
    for j in range(i + 1, i + 200):
        if j >= n:
            break
        if abs(l[i] - l[j]) <= k:
            num = max(num, root[j])
    root[i] += num

print(max(root))

Measured memory_bytes: 94740
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long int LL;
int a1[100010];
int a2[100010];
int a3[100010];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a1[i];
	}
	for(int i=1;i<=n;i++){
		cin>>a2[i];
	}
	for(int i=1;i<=n;i++){
		cin>>a3[i];
	}
	
	sort(a1+1,a1+n+1);
	sort(a2+1,a2+n+1);
	sort(a3+1,a3+n+1);
	LL j=1;
	LL k=1;
	long long int sum=0;
	for(int i=1;i<=n;i++){
		while(a1[j]<a2[i]&&j<=n){
			j++;
		}
		
		while(a3[k]<=a2[i]&&k<=n){
			k++;
		}
		
		sum=sum+(j-1)*(n-k+1);
	} 
	cout<<sum;
}


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

class Program {
    static void Main (string[] args) {
        var inp = Console.ReadLine().Split(' ');

        int n = int.Parse(inp[0]);
        long num = 0;
        for(int i = 1;i < n + 1;i++) {
            if(i % 3 == 0) {
                continue;
            }

            if(i % 5 == 0) {
                continue;
            }

            num += i;
        }

        Console.WriteLine(num);
    }
}

Measured memory_bytes: 27536
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

//size of longest common prefix between s and s[i,n-1]
//ex) pattern matching - string s=pattern+"#"+S
vector<int> Zalgorithm(const vector<ll> &s){//z[0]:=0
    int n=s.size();
    vector<int> z(n,0);
    int L=0,R=0;
    for(int i=1;i<n;i++){
        if(R<i){
            L=i;R=i;
            while(R<n&&s[R-L]==s[R]) R++;
            R--;
            z[i]=R-L+1;
        }else{
            int k=i-L;
            if(z[k]<R-i+1) z[i]=z[k];
            else{
                L=i;
                while(R<n&&s[R-L]==s[R]) R++;
                R--;
                z[i]=R-L+1;
            }
        }
    }

    z[0]=0;
    return z;
}

int main(){
  int N;
  cin>>N;
  vector<ll> A(N),B(N);
  rep(i,N) cin>>A[i];
  rep(i,N) cin>>B[i];

  vector<ll> C(2*N),D(N);
  rep(i,2*N) C[i]=A[i%N]^A[(i+1)%N];
  rep(i,N) D[i]=B[i]^B[(i+1)%N];

  vector<ll> S=D;
  S.push_back(-1);
  rep(i,C.size()) S.push_back(C[i]);

  vector<int> z=Zalgorithm(S);
  
  vector<pair<int,int>> ans;
  for(int i=N+1;i<=2*N;i++){
    if(z[i]==N) ans.push_back(mkp(i-N-1,A[i-N-1]^B[0]));
  }

  rep(i,ans.size()) cout<<ans[i].first<<" "<<ans[i].second<<endl;

  return 0;
}


Measured memory_bytes: 22188
#!/user/bin/env pypy3
import sys
from typing import List


def fast_input():
    return sys.stdin.readline()[:-1]


def is_all_even(nums: List[int]) -> bool:
    for n in nums:
        if n % 2 == 1:
            return False
    return True


def solve(n: int, nums: List[int]) -> int:
    manipulate_count = 0
    while is_all_even(nums):
        manipulate_count += 1
        nums = list(map(lambda x: int(x / 2), nums))
    return manipulate_count


def main():
    n = int(fast_input())
    a = list(map(int, fast_input().split()))
    result = solve(n, a)
    print(result)


main()


Measured memory_bytes: 10220
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

int main() {
	int H, W;
	cin >> H >> W;

	vector<vector<char>> g(H, vector<char>(W));
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			cin >> g[i][j];
		}
	}

	for (int i = 0; i < H; i++) {
		bool b = true;
		for (int j = 0; j < W; j++) {
			if (g[i][j] == '#') {
				b = false;
				break;
			}
		}
		if (b) {
			for (int j = 0; j < W; j++) {
				g[i][j] = 'd';
			}
		}
	}

	for (int i = 0; i < W; i++) {
		bool b = true;
		for (int j = 0; j < H; j++) {
			if (g[j][i] == '#') {
				b = false;
				break;
			}
		}
		if (b) {
			for (int j = 0; j < H; j++) {
				g[j][i] = 'd';
			}
		}
	}

	//for (int i = 0; i < H; i++) {
	//	for (int j = 0; j < W; j++) {
	//		cout << g[i][j];
	//	}
	//	cout << endl;
	//}

	for (int i = 0; i < H; i++) {
		bool f = false;
		for (int j = 0; j < W; j++) {
			if (g[i][j] != 'd') {
				cout << g[i][j];
				f = true;
			}
		}
		if (f) cout << endl;
	}
}

Measured memory_bytes: 3628
#include<stdio.h>

int main(void)
{
  int n,m;
  long x;
  scanf("%d %d %ld",&n,&m,&x);

  long c[n];
  long a[n][m];
  long long min=2000000LL;
  long long sum[1<<n][m];
  int flag=0;

  for(int i=0;i<n;i++){
    scanf("%ld",&c[i]);
    for(int j=0;j<m;j++){
      scanf("%ld",&a[i][j]);
    }
  }

  for(int i=0;i<(1<<n);i++){
    for(int j=0;j<m;j++){
      sum[i][j]=0;
    }
  }



  for(int bit=1;bit<(1<<n);bit++){ //0~2^n-1
    int count=0;
    long long money=0;

    for(int i=0;i<n;i++){ //0~n-1
      if(bit&(1<<i)){
        money+=c[i];
        for(int j=0;j<m;j++){
          sum[bit][j]+=a[i][j];
        }
      }
    }

    for(int k=0;k<m;k++){
      if(sum[bit][k]>=x){
        count++;
      }
    }

    if(money<min&&count==m){
      flag=1;
      min=money;
    }
  }



  if(flag==1){
    printf("%lld\n",min);
  }else{
    puts("-1");
  }

  return 0;
}


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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> ans(n);
    rep(i,2) {
        int cnt = 0;
        rep(j,n) {
            if (s[j] == 'R') cnt++;
            else {
                ans[j] += cnt/2;
                ans[j-1] += (cnt+1)/2;
                cnt = 0;
            }
        }
        reverse(ans.begin(), ans.end());
        reverse(s.begin(), s.end());
        rep(j,n) {
            if (s[j] == 'L') s[j] = 'R';
            else s[j] = 'L';
        }
    }
    rep(i,n) printf("%d\n", ans[i]);
    return 0;
}

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

int main(){
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  for(int j=0;j<(d-b);j++)cout << 'U';
  for(int j=0;j<(c-a);j++)cout << 'R';
  for(int j=0;j<(d-b);j++)cout << 'D';
  for(int j=0;j<(c-a)+1;j++)cout << 'L';
  for(int j=0;j<(d-b)+1;j++)cout << 'U';
  for(int j=0;j<(c-a)+1;j++)cout << 'R';
  cout << 'D' << 'R';
  for(int j=0;j<(d-b)+1;j++)cout << 'D';
  for(int j=0;j<(c-a)+1;j++)cout << 'L';
  cout << 'U' << endl;
  return 0;
}


Measured memory_bytes: 256
n = int(input())
s = []
for i in range(n):
    s.append(input())
m = int(input())
t = []
for i in range(m):
    t.append(input())
max_game = 0
for i in range(n):
    if max_game < s.count(s[i]) - t.count(s[i]):
        max_game = s.count(s[i]) - t.count(s[i])
print(max_game)


Measured memory_bytes: 3060
#include<iostream>
#include<vector>
#include<set>
using namespace std;

struct UnionFind{
    vector<long long> root;
    vector<long long> sizes;
    UnionFind(long long n): root(n + 1), sizes(n + 1,1){
        for(long long i = 0; i <= n; i++) root[i] = i;
    }
    long long find(long long x){
        if(x == root[x]) return x;
        return root[x] = find(root[x]);
    }
    void unite(long long x, long long y){
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(sizes[x] < sizes[y]) swap(x,y);
        root[y] = x;
        sizes[x] += sizes[y];
    }
    bool same(long long x, long long y){
        return find(x) == find(y);
    }
};

int main(){
    //input
    long long N, M;
    cin >> N >> M;
    long long i,X,Y,Z;
    UnionFind uf(N);
    for(i=1; i<=M; i++){
        cin >> X >> Y >> Z;
        uf.unite(X,Y);
    }
    set<long long> ss;
    for(i=1; i<=N; i++){
        ss.insert(uf.find(i));
    }

    //answer
    cout << ss.size() << endl;
    system("pause");
    return 0;
}

Measured memory_bytes: 6776
#include <iostream>
#include <string>
#include <sstream>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

ll stoll(string s) {
	stringstream ss(s);
	int ret; ss >> ret;
	return ret;
}

string s;
ll parse(int l, int r) {
	if (s[l] != '[') return stoll(s.substr(l, r-l))/2 + 1;
	
	priority_queue< ll, vector<ll>, greater<ll> > vote;
	int stack = 0, prev = l;
	for (int i=l; i<r; i++) {
		if (s[i]=='[') stack++;
		if (s[i]==']') stack--;
		if (stack==0) {
			vote.push(parse(prev+1, i));
			prev = i+1;
		}
	}
	
	int res = 0;
	int len = (int)vote.size();
	for (int i=0; i<=len/2; i++) { res += vote.top(); vote.pop(); }
	return res;
}

int main() {
	int n; cin >> n;
	for (int i=0; i<n; i++) {
		cin >> s;
		cout << parse(0, s.size()) << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1316
/*in the name of Allah the most beneficent the most merciful.*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define MAX 1e18
#define MIN -1e18
#define MOD 1000000007
//#define mod2 20071027
//#define MOD 998244353
#define base 139
// #define MOD 1000074259
#define base2 31
#define memz(a) memset(a, 0, sizeof(a))
#define memn(a) memset(a, -1, sizeof(a))
#define in1(a) scanf("%lld", &a)
#define in2(a, b) scanf("%lld%lld", &a, &b)
#define TC(c) printf("Case #%lld: ", ++c)
#define out(x) cout << #x << " -> " << x << endl;
#define FAST ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FILE   freopen("input.txt", "r", stdin);  freopen("out.txt", "w", stdout);
using namespace std;
const ll B = 20, N = 300010, M = 2000000;
ll a, b;
int solve()
{
    cin>>a>>b;
    for(int i=1;i<=3;i++)
        if(i!=a && i!=b)
            printf("%d\n", i);
    return 0;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    return solve();
}

Measured memory_bytes: 3688
import itertools

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

q_list = []

for i in range(Q):
    q_list.append(list(map(int, input().split(' '))))


def check(target, point, i):

    if len(q_list) == i:
        return point

    a = q_list[i][0]
    b = q_list[i][1]
    c = q_list[i][2]
    d = q_list[i][3]

    if target[b - 1] - target[a - 1] == c:
        point = check(target, point + d, i + 1)

    else:
        point = check(target, point, i + 1)

    return point


a_list = list(itertools.combinations_with_replacement(range(1, M+1), N))

result = max([check(target, 0, 0) for target in a_list])
print(result)


Measured memory_bytes: 25140
import java.math.*;
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		BigInteger a,b,c;
		Scanner cin = new Scanner(System.in);
		while(cin.hasNext()) {
			a = cin.nextBigInteger();
			b = cin.nextBigInteger();
			c = a.max(b);
			if(a.equals(c)&&!b.equals(c)) 
				System.out.println("GREATER");
			else if(b.equals(c)&&!a.equals(c))
				System.out.println("LESS");
			else 
				System.out.println("EQUAL");
		}
		cin.close();
	}

}

Measured memory_bytes: 25044
#include<stdio.h>
int main()
{
	char s1[101],s2[101],s3[201];
	int n;
	scanf("%d",&n);
	scanf("%s %s",s1,s2);
	int i=0,j=0;
	while(s1[j]!='\0'&&s2[j]!='\0')
	{
		s3[i++]=s1[j];
		s3[i++]=s2[j++];
	}
	s3[i]='\0';
	puts(s3);
	printf("\n");
	return 0;
}


Measured memory_bytes: 128
#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 if (a == b){
		cout << "a == b" << endl;
	}
	return 0;
}

Measured memory_bytes: 1156
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
int main()
{
    int x,y,z;
    cin>>x>>y>>z;
    if((x*100+y*10+z)%4==0)
        cout<<"YES";
    else
        cout<<"NO";
    cout<<nl;
    return 0;
}


Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define max0(a,b,c) max(max(a,b),c)
#define min0(a,b,c) min(min(a,b),c)
#define ft first
#define sc second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(v) (v).begin(),(v).end()
#define mod 1000000007
using namespace std;
using Graph = vector<vector<int>>;
typedef long long lint;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ldouble;
typedef vector<int> vec;
typedef vector<ll> lvec;
typedef vector<ull> ulvec;
typedef vector<double> dvec;
typedef vector<pair<int,int>> pvec;
typedef vector<pair<ll,ll>> plvec;
typedef vector<tuple<ll,ll,ll>> tvec;
typedef vector<string> svec;

const ll max_n=100000;

ll n,c,k,ans=0;
ll t[max_n+1];

void solve(){
    sort(t,t+n);
    ll p=0;
    while(p<n){
        ll m=upper_bound(t+p,t+n,t[p]+k)-t;
        if(m-p<=c){
            ans++;
            p=m;
        }else{
            ans++;
            p+=c;
        }
    }
    cout<<ans;
}

int main(){
    cin>>n>>c>>k;
    rep(i,n) cin>>t[i];
    solve();
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define bye return 0
#define Yes cout << "Yes" << "\n"
#define No  cout << "No" << "\n"
#define YES cout << "YES" << "\n"
#define NO cout << "NO" << "\n"
using namespace std;
int main(){
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    string s1;
    string s2;
    vector< vector<string> > v;
    int a, b, c, cnt=0, in=0;
    
    cin >> a >> b;

    for(int i=0; i<a; ++i){
    vector<string> raw;
    cin >> s1;
    raw.push_back(s1);
    v.push_back(raw);
      
    }

     for(int i=1; i<= b+2; ++i){
     	cout << "#";
     }
     cout << "\n";

     
     for(int i=0; i<v.size(); ++i){
        for(int j=0; j<1; ++j){
     	cout<< "#" << v[i][j] << "#" << "\n";
     	}
     }



     for(int i=1; i<= b+2; ++i){
     	cout << "#";
     }
     cout << "\n";



   bye;

}


Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

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

	int k;
	cin >> k;

	if (k == 3) {
		cout << "Yes\n";
		cout << "3\n";
		cout << "2 1 2\n";
		cout << "2 3 1\n";
		cout << "2 2 3\n";
	}
	else {

		int num = 0;
		for (int i = 0; i * i < 2 * k; i++) {
			if (i * (i + 1) == k * 2) {
				num = i;
				break;
			}
		}

		if (num == 0) cout << "No" << "\n";
		else {
			
			cout << "Yes" << "\n";
			cout << num + 1 << "\n";
			vector<vector<int>> ans(num, vector<int>(num));
			int cnt = 1;
			for (int i = 0; i < num; i++) {
				for (int j = 0; j < num - i; j++) {
					ans[i][j] = ans[num - j - 1][num - i - 1] = cnt++;
				}
			}

			for (int i = 0; i < num; i++) {
				cout << num << " ";
				for (int j = 0; j < num; j++) {
					cout << ans[i][j] << " ";
				}
			}
			
			cout << num << " ";
			for (int i = 0; i < num; i++) cout << ans[i][num - i - 1] << " ";

		}

	}

	return 0;
}

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

#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;

int main(){
    ll i,j;
    ll n,k;

    cin>>n>>k;
    ll a[n];

    for(i=0;i<n;i++){
        cin>>a[i];
    }
    ll suma[n+1];
    suma[0]=0;
    for(i=1;i<=n;i++){
        suma[i]=suma[i-1]+a[i-1];
    }

    vector<ll> b;
    for(i=0;i<n;i++){
        for(j=i;j<n;j++){
            b.push_back(suma[j+1]-suma[i]);
        }
    }

    int flag[46];
    for(i=0;i<46;i++) flag[i]=0;
    int rema[b.size()];
    for(i=0;i<b.size();i++) rema[i]=0;

    for(j=45;j>=0;j--){
        ll cnt=0;
        for(i=0;i<b.size();i++){
        if(rema[i]==0&&((b[i]>>j)&1==1)) cnt++;
        }


        if (cnt>=k){
            flag[j]=1;
            for(i=0;i<b.size();i++){
                if(rema[i]==0&&((b[i]>>j)&1==1)) cnt+=0;
                else rema[i]=1;
            }
        }
    }

    ll ans=0;
    for(j=45;j>=0;j--){
        ans*=2;
        ans+=flag[j];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 6252
package main

import (
	"fmt"
)

func pow(x, n, mod int64) int64 {
	if n == 0 {
		return 1
	}
	xx := x * x % mod
	r := pow(xx, n/2, mod)
	if n%2 == 1 {
		r = x * r % mod
	}
	return r
}

const mod = 1e9 + 7

func main() {
	var n, d int
	fmt.Scan(&n, &d)
	r := n / (d*2 + 1)
	if n%(d*2+1) > 0 {
		r++
	}

	fmt.Println(r)

}


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

int main(){
  while(true){
    int n, l, r, count = 0, A[60];
    cin>>n>>l>>r;
    if(!n&&!l&&!r) break;

    for(int i = 1; i <= n; i++){
      cin>>A[i];
    }
    
    for(int i = l; i <= r; i++){
      int flag = !(n%2);
      for(int j = 1; j <= n; j++){
	if(i%A[j] == 0){
	  if(j%2==1){
	    flag = true;
	    break;
	  }else{
	    flag = false;
	    break;
	  }
	}
      }
      if(flag)count++;
    }
    cout<<count<<endl;
  }
  return 0;
}


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

int main() {

  int n,k;
  cin >> n >> k;
  
  int count = 1;
  int a = 1;
  
  for(int i=0; i<n; i++) {
    
    a *= k;
      if(n < a)
        break;
    
    count ++;
  }
  cout << count << endl;
  
}

Measured memory_bytes: 256
#include<stdio.h>
int b_search(int);
int n;
int l[100000];
int main(){
  int i;
  int q;
  int q_n;
  int result=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)scanf("%d",&l[i]);
  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&q_n);
    result+=b_search(q_n);
  }
  printf("%d\n",result);
  return 0;
}
int b_search(int x){
  int i;
  int mid;
  int left=0;
  int right=n;
  while(left<right){
    mid=(left+right)/2;
    if(l[mid]==x){
      return 1;
    }
    else if(x<l[mid])right=mid;
    else left=mid+1;
  }
  return 0;
}



Measured memory_bytes: 2124
#include <iostream>
#include <math.h>
#include <vector>
using namespace std;
#define endl '\n'
#define M_PI 3.14159265358979323846

using namespace std;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    double x;
    cin >> x;
    cout << x * M_PI * 2;
    return 0;
}

Measured memory_bytes: 3800
#include <stdio.h>
    #include <math.h>
     
    int main(){            
      long a,b,r,tmp;
      long ans;
      int i;

      scanf("%ld %ld",&a,&b);

      ans = a * b;
 
      /* 自然数 a > b を確認・入替 */
  	  if( a < b ){
      	tmp = a;
   		a = b;
    	b = tmp;
      }
 
      /* ユークリッドの互除法 */
  	  r = a % b;
      while(r!=0){
      	a = b;
    	b = r;
    	r = a % b;
  	  }
      
      printf("%ld",ans/b);
      
      return 0;
    }

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

namespace ConsoleApplication6
{
    class Program
    {
        static void Main(string[] args)
        {
            var each = spr(RL()).Select(x => c2i(x)).ToList();
            var sock = each.Last();
            var mons = each.First();
            var ret=true;

            if(sock>mons*4) ret=false;
            if (ret) ret = sock % 2 == 0;
            if (ret) ret=(sock >= mons * 2);
            Console.WriteLine(bool2ret(ret));
            Console.ReadLine();

        }

        static string RL() { return Console.ReadLine().Trim(); }
        static IEnumerable<string> spr(string s) { return s.Split(' '); }
        static Int64 c2i(string c) { return Int64.Parse(c); }
        //static double c2d(string c) { return double.Parse(c); }
        static string bool2ret(bool b) { return b ? "Yes" : "No"; }
    }
}

Measured memory_bytes: 28188
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
#include <map>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

template<typename T>
map<T, long long> factorize(T x) {
  map<T, long long> res;
  for (long long i = 2; i * i <= x; ++i) {
    while (x % i == 0) {
      x /= i;
      res[i] += 1;
    }
  }
  if (x != 1) res[x]++;
  return res;
}

int main() {
  int n; cin >> n;
  vector<ll> fac(n+1, 0);

  for (int i = 1; i <= n; ++i) {
    for (auto itr : factorize(i)) {
      fac[itr.first] += itr.second;
    }
  }
  ll res = 0;
  for (auto itr : fac) if (itr > 73) res++;

  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i != j) {
        if (fac[i] >= 24 and fac[j] >= 2) res++;
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      if (i != j) {
        if (fac[i] >= 4 and fac[j] >= 14) res++;
      }
    }
  }

  ll tmp = 0;
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= n; ++j) {
      if (i != j) {
        for (int k = 0; k <= n; ++k) {
          if (i != k and j != k and fac[k] >= 2 and fac[i] >= 4 and fac[j] >= 4) {
            tmp++;
          }
        }
      }
    }
  }
  res += tmp / 2;

  cout << res << endl;
}


Measured memory_bytes: 256
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=1e9;
const ll INF=5e18;
using P=pair<int,int>;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  string s;
  int n,x[3]={},cnt,ans=0;
  cin >> n >> s;
  for(int i=0; i<1000; i++) {
    x[0]=i/100,x[1]=(i%100)/10,x[2]=i%10;
    cnt=0;
    for(auto p:s) {
      if((p-'0')==x[cnt]) {
        cnt++;
      }
      if(cnt==3) {
        ans++;
        break;
      }
    }
  }
  cout << ans << endl;
}


Measured memory_bytes: 384
from copy import deepcopy
from sys import stdin

def S(): return stdin.readline().rstrip()
def I(): return int(stdin.readline().rstrip())
def LS(): return list(stdin.readline().rstrip().split())
def LI(): return list(map(int,stdin.readline().rstrip().split()))
def R(x):
    r = round(x)
    if r+0.5 <= x:
        r += 1
    return r

n = S()

for i in range(3):
    if(n[i] == '7'):
        print('Yes')
        exit()

print('No')

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

using namespace std;

const int MAXN = 1e5 + 10;

int n;

int a[MAXN];

const int MOD = 1e9 + 7;

int main() {
    string s;
    cin >> s;

    if (s[2] == s[3] && s[4] == s[5])
        cout << "Yes";
    else
        cout << "No";
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <functional>
#include<vector>
#include<math.h>
#include<bitset>
#include<string>
#include <deque>
#include<queue>
#include<map>

using namespace std;
long long int A1[1008], A2[1008], B1[1008], B2[1008], C1[1008], C2[1008], D1[1008], D2[1008];

int main() {
	long long int N,M;
	cin >> N>>M;

	long long int a, b, c;
	for (long long int i = 0; i < N; i++) {
		cin >> a >> b >> c;
		//+++
		A1[i] = a + b + c;
		A2[i] = -a + b + c;
		B1[i] = a - b + c;
		B2[i] = a + b - c;
		C1[i] = -a - b + c;
		C2[i] = -a + b - c;
		D1[i] = a - b - c;
		D2[i] = -a - b - c;
	}
	
	sort(A1, A1 + N,greater<long long int>());
	sort(A2, A2 + N, greater<long long int>());
	sort(B1, B1 + N, greater<long long int>());
	sort(B2,B2 + N,greater<long long int>());
	sort(C1, C1 + N, greater<long long int>());
	sort(C2, C2 + N, greater<long long int>());
	sort(D1, D1 + N, greater<long long int>());
	sort(D2, D2 + N, greater<long long int>());

	for (int i = 0; i < M-1; i++) {
		A1[i + 1] += A1[i];
	}
	for (int i = 0; i < M - 1; i++) {
		A2[i + 1] += A2[i];
	}
	for (int i = 0; i < M - 1; i++) {
		B1[i + 1] += B1[i];
	}
	for (int i = 0; i < M - 1; i++) {
		B2[i + 1] += B2[i];
	}
	for (int i = 0; i < M - 1; i++) {
		C1[i + 1] += C1[i];
	}
	for (int i = 0; i < M - 1; i++) {
		C2[i + 1] += C2[i];
	}
	for (int i = 0; i < M - 1; i++) {
		D1[i + 1] += D1[i];
	}
	for (int i = 0; i < M - 1; i++) {
		D2[i + 1] += D2[i];
	}
	
	A1[M - 1] = max(A1[M - 1], A2[M - 1]);
	B1[M - 1] = max(B1[M - 1], B2[M - 1]);
	C1[M - 1] = max(C1[M - 1], C2[M - 1]);
	D1[M - 1] = max(D1[M - 1], D2[M - 1]);
	A1[M - 1] = max(A1[M - 1], B1[M - 1]);
	C1[M - 1] = max(C1[M - 1], D1[M - 1]);
	A1[M - 1] = max(A1[M - 1], C1[M - 1]);
	
	
	cout << A1[M - 1] << endl;
	return 0;
}


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

int main()
{
    int n,res;
    scanf("%d",&n);
    if(n%2==0) res=0;
    else res=1;
    res=(n/2)+res;
    printf("%d\n",res);
    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 rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using P = pair<ll, ll>;

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// Yes-Noを出力する問題で楽をする
void Ans(bool f){
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

//---------------------------

int main(){
    int n,k;
    cin >> n >> k;
    if(n%k) cout << 1 << endl;
    else cout << 0 << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;
typedef pair<ll,ll> pll;
const ll mod=1e9+7;
//const ll mod=998244353;
const ll inf=5e18;

ll solve(ll n) {
  ll res=0;
  while(n) {
    res+=n%10;
    n/=10;
  }
  return res;
}

int main() {
  ll n;
  cin >> n;
  ll sum=solve(n);
  if(n%sum==0) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

Measured memory_bytes: 256
#pragma GCC optimize("O3")

#define _GLIBCXX_DEBUG
#include <iostream>
#include <vector>
#include <string>
#include <string_view>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
using namespace std;

/*----------macros----------*/

//output================
#define endl '\n'
#define fcout(a) cout << fixed << setprecision((int)(a))

//typedef===============
typedef long long       ll;
typedef long double     ld;
typedef pair<int, int>  Pii;
typedef pair<ll, ll>    Pll;

//const number==========
constexpr ll INF9   = (ll)1e9 + 1;
constexpr ll INF18  = (ll)1e18 + 1;
constexpr ll MOD    = 1000000007;
constexpr ll MOD2   = 998244353;
constexpr ld PI     = 3.141592653589793L;

//member================
#define pb push_back
#define eb emplace_back
#define pf push_front
#define mp make_pair
#define fi first
#define se second

//others================
#define all(x)          (x).begin(), (x).end()
#define rall(x)         (x).rbegin(), (x).rend()
#define rep(i, n)       for(int i = 0; (i) < (n); ++(i))
#define reps(i, n)      for(int i = 1; (i) <= (n); ++(i))
#define rrep(i, n)      for(int i = n - 1; (i) >= 0 ; --(i))
#define repbit(bit, n)  for(int bit = 0; (bit) < (1 << (n)); ++(bit))
#define ifbit(bit, i)   if((bit) & (1 << (i)))
#define CtoI(c)         int((c)) - int('0')
#define ItoC(c)         char((c) + '0')

//functions=============
template<typename T1, typename T2>
inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }

template<typename T1, typename T2>
inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }

//vector<int> dx = {1, 0, -1, 0}, dy = {0, 1, 0, -1};
//vector<int> dx2 = { 1,1,0,-1,-1,-1,0,1 }, dy2 = { 0,1,1,1,0,-1,-1,-1 };


/*--------additional--------*/

int n, m, q;
vector<int> a(100), b(100), c(100), d(100);
ll ans = 0;

vector<int> A(10);

void dfs(int _dep, int _init){
    if(_dep == n){
        int res = 0;
        rep(i, q){
            if(A[b[i]] - A[a[i]] == c[i]) res += d[i];
        }
        chmax(ans, res);
    }
    else{
        for(int i = _init; i <= m; ++i){
            A[_dep] = i;
            dfs(_dep + 1, i);
        }
    }
}

/*----------main------------*/

int main() {
/*----------fastio----------*/
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    std::ios::sync_with_stdio(false);
/*----------solve-----------*/

    cin >> n >> m >> q;
    rep(i, q){
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        --a[i], --b[i];
    }

    dfs(0, 1);

    cout << ans << endl;

return 0;
}

Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
#define rep(i,n) for(long long i=0;i<(long long)(n);i++)
#define REP(i,k,n) for(long long i=k;i<(long long)(n);i++)
#define all(a) a.begin(),a.end()
#define eb emplace_back
#define lb(v,k) (lower_bound(all(v),k)-v.begin())
#define ub(v,k) (upper_bound(all(v),k)-v.begin())
#define fi first
#define se second
#define pi M_PI
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T,vector<T>,greater<T>>
using ll=long long;
using P=pair<ll,ll>;
using PP=tuple<ll,ll,ll>;
using S=multiset<ll>;
using vi=vector<ll>;
using vvi=vector<vi>;
using vvvi=vector<vvi>;
const ll inf=1001001001001001;
const int INF=1001001001;
const int mod=1000000007;
const double eps=1e-10;
template<class T> bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<class T> bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<class T> void out(T a){cout<<a<<'\n';}
template<class T> void outp(T a){cout<<'('<<a.fi<<','<<a.se<<')'<<'\n';}
template<class T> void outvp(T v){rep(i,v.size())cout<<'('<<v[i].fi<<','<<v[i].se<<')';cout<<'\n';}
template<class T> void outv(T v){rep(i,v.size()){if(i)cout<<' ';cout<<v[i];}cout<<'\n';}
template<class T> void outvv(T v){rep(i,v.size())outv(v[i]);}
template<class T> bool isin(T x,T l,T r){return (l)<=(x)&&(x)<=(r);}
template<class T> void YesNo(T b){if(b)out("Yes");else out("No");}
void decimal(int x){cout<<fixed<<setprecision(x);}
ll GCD(ll a,ll b){if(b==0) return a; return GCD(b,a%b);}
ll LCM(ll a,ll b){return(a/GCD(a,b))*(b/GCD(a,b))*GCD(a,b);}
ll POW(ll a,ll b){a%=mod;if(b==0)return 1;if(b&1)return a*POW(a,b-1)%mod;ll k=POW(a,b/2);return k*k%mod;}
vi calc(ll x){vi res;while(x>0){res.eb(x%10);x/=10;}reverse(all(res));return res;}

struct UnionFind{
	vi d;
	UnionFind(ll n=0):d(n,-1){}
	ll find(ll x){
		if(d[x]<0) return x;
		return d[x]=find(d[x]);
	}
	bool unite(ll x,ll y){
		x=find(x); y=find(y);
		if(x==y) return false;
		if(d[x]>d[y]) swap(x,y);
		d[x]+=d[y];
		d[y]=x;
		return true;
	}
	bool same(ll x,ll y){return find(x)==find(y);}
	ll size(ll x){return -d[find(x)];}
};

void solve(){
  int n,q;
  cin>>n>>q;
  UnionFind uf(n);
  rep(i,q){
  	int k,u,v;
  	cin>>k>>u>>v;
  	if(k==0) uf.unite(u,v);
  	else out(uf.same(u,v));
  }
}

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


Measured memory_bytes: 4708
import scala.annotation.tailrec
import scala.collection.mutable

object Main extends App {
  import scala.io.StdIn._
  solve
  @tailrec def solve: Unit = {
    val Array(w, h) = readLine.trim.split(' ').map(_.toInt)
    if (w == 0) return
    val maze = new Maze(h, w)
    for (i ← 0 until (2 * h - 1)){
      val line = readLine.trim.stripPrefix(" ").split(' ').map(_.toInt)
      if (i % 2 == 0){
        line.zipWithIndex.foreach{case (isBlocked, pos) ⇒ if (isBlocked == 1) maze.addWallVertical(i / 2, pos)}
      }else {
        line.zipWithIndex.foreach{case (isBlocked, pos) ⇒ if (isBlocked == 1) maze.addWallHorizontal(i / 2, pos)}
      }
    }
    val queue: mutable.PriorityQueue[(Cell, Int)] = mutable.PriorityQueue[(Cell, Int)]()(Ordering.by[(Cell, Int), Int]{case (_, d) ⇒ d}.reverse).also{p ⇒ p.enqueue((Cell(0, 0), 1))}
    val memo = Array.tabulate(h){_ ⇒ Array.tabulate(w){_ ⇒ Int.MaxValue}}.also{m ⇒ m(0)(0) = 1}
    val goal = Cell(w - 1, h - 1)
    while (queue.nonEmpty && queue.head._1 != goal) {
      val (current, distance) = queue.dequeue()
      if (memo(current.y)(current.x) == distance){
        for (neighbor ← maze.neighbors(current)) {
          if (memo(neighbor.y)(neighbor.x) > distance + 1){
            memo(neighbor.y)(neighbor.x) = distance + 1
            queue.enqueue((neighbor, distance + 1))
          }
        }
      }
    }
    println(
      if (queue.isEmpty) 0 else queue.head._2
    )
    solve
  }

  object Maze{
    private val relationNeighbor: List[Cell] = List(Cell(0, -1), Cell(-1, 0), Cell(0, 1), Cell(1, 0))
    private def selectNeighbor(selector: Int, list: List[Cell]): List[Cell] = {
      list match{
        case Nil ⇒ Nil
        case h::t if selector % 2 == 1 ⇒ h::selectNeighbor(selector / 2, t)
        case _::t ⇒ selectNeighbor(selector / 2, t)
      }
    }
  }
  class Maze(val height: Int, val width: Int) {
    private val mState: Array[Array[Int]] = Array.tabulate(height){_ ⇒ Array.tabulate(width){_ ⇒ 15}}//右下左上
    def addWallVertical(row: Int, position: Int): Unit = {
      mState(row)(position) &= 7
      mState(row)(position + 1) &= 13
    }
    def addWallHorizontal(row: Int, position: Int): Unit = {
      mState(row)(position) &= 11
      mState(row + 1)(position) &= 14
    }
    def neighbors(cell: Cell): List[Cell] = Maze.selectNeighbor(mState(cell.y)(cell.x), Maze.relationNeighbor.map(_ + cell)).filter(this.isContain)
    private def isContain(cell: Cell): Boolean = (0 until height).contains(cell.y) && (0 until width).contains(cell.x)
  }
  case class Cell(x: Int, y: Int) {
    def +(that: Cell): Cell = Cell(x + that.x, y + that.y)
  }
  implicit class ScopeFunc[T](private val value: T) {
    def let[A](func:T ⇒ A): A = func(value)
    def also(func:T ⇒ Unit): T = {
      func(value)
      value
    }
  }
}


Measured memory_bytes: 103128
#include <stdio.h>

int main(void){
	
	int x,y,d=100;
	
	scanf("%d",&x);
	scanf("%d",&y);
	
	while(d>0){
		d=x%y;
		x=y;
		y=d;
	}
	
	printf("%d\n",x);
	
	return 0;
}


Measured memory_bytes: 2100
N, K = gets.split.map(&:to_i)

min = [N, K-1].min
ans = 0
(1..min).each do |i|
  num = 0
  sum = i
  loop do
    break if sum >= K
    sum *= 2
    num += 1
  end

  t = (1.0/N) * (0.5**num)
  ans += t
end

if N >= K
  ans += (N-K+1).to_f/N
end

p ans


Measured memory_bytes: 1788
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long LL;
const int N=2e5+10;
LL n,m;
int first[N],tot=0,col[N];
struct node{int ne,to;}e[N*2];
LL wi=0,bl=0;
bool flag=1,ok[N];
LL read(){
	LL ans=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){ans=ans*10+c-48;c=getchar();}
	return ans*f;
}
void ins(int u,int v){e[++tot]=(node){first[u],v};first[u]=tot;}
void dfs(int x,int fa){
	ok[x]=1;
	for(int i=first[x];i;i=e[i].ne){
		if(!flag)return;
		int to=e[i].to;
		if(to==fa)continue;
		if(col[to]==col[x]){flag=0;return;}
		if(ok[to])continue;
		col[to]=col[x]^1;
		if(col[to]==2)bl++;else wi++;
		dfs(to,x);
	}
}
int main(){
	n=read();m=read();
	for(int i=1,a,b;i<=m;i++){
		a=read();b=read();ins(a,b);ins(b,a);
	}col[1]=2;bl++;
	dfs(1,0);
	if(flag)printf("%lld",bl*wi-m);
	else printf("%lld",n*(n-1)/2-m);
	return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
#include <math.h>
#define _GLIBCXX_DEBUG
using namespace std;
int main() {
  
  int A,B;cin>>A>>B;
  
  if(A*B%2==0){
    cout<<"No"<<endl;
  }
  else{
    cout<<"Yes"<<endl;
  }
}


Measured memory_bytes: 3516
n,l = map(int,input().split())
ans = 0
pie = l*n+(1+n)*n//2-n
max_a = l+n-1
min_a = l
if max_a<0:
    ans = pie-max_a
elif min_a<=0 and max_a>=0:
    ans = pie
elif min_a>0:
    ans = pie-min_a
print(ans)

Measured memory_bytes: 9168
#include "bits/stdc++.h"
using namespace std;

long long N, A[100000];
vector<vector<long long> > V;

long long DFS(long long P, long long Q) {
	if (V[P].size() == 1) return A[P];
	long long SUM = 0;
	for (long long NP : V[P]) {
		if (Q == NP) continue;
		long long X = DFS(NP, P);
		if (X == -1) return -1;
		if (X > A[P]) return -1;
		SUM += X;
	}
	if (SUM > A[P] * 2 || SUM < A[P]) return -1;
	return A[P] * 2 - SUM;
}

int main() {
	cin >> N;
	V.resize(N);
	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N - 1; i++) {
		long long S, T;
		cin >> S >> T;
		S--, T--;
		V[S].push_back(T);
		V[T].push_back(S);
	}
	for (int i = 0; i < N; i++) {
		if (V[i].size() == 1) {
			cout << (DFS(V[i][0], i) == A[i] ? "YES" : "NO") << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 11136
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

Mat = collections.namedtuple("Mat", "r c")

def mat_mul(ms):
    return Mat(ms[0].r, ms[-1].c)

def cost(m1, m2):
    return m1.r * m1.c * m2.c

def solve(n, ms):
    if n == 1: return 0

    dp = {}
    for i in range(n):
        dp[(i,i)] = 0

    for l in range(2, n+1):
        for i in range(n-l+1):
            #cost_min = math.inf
            cost_min = float("inf")
            for j in range(l-1):
                dbg("l, i, j: %d %d %d", l, i, j)
                m_lhs = mat_mul(ms[i:i+j+1])
                m_rhs = mat_mul(ms[i+j+1:i+l])
                dbg("m_lhs, m_rhs: %r %r", m_lhs, m_rhs)
                cost_lhs = dp[(i,i+j)]
                cost_rhs = dp[(i+j+1,i+l-1)]
                dbg("cost_lhs, cost_rhs: %d %d", cost_lhs, cost_rhs)
                cost_mul = cost(m_lhs, m_rhs)
                dbg("cost_mul: %d", cost_mul)
                cost_now = cost_mul + cost_lhs + cost_rhs
                dbg("cost_now: %d", cost_now)
                if cost_min > cost_now:
                    cost_min = cost_now
            dp[(i,i+l-1)] = cost_min

    dbg(dp)
    return dp[(0,n-1)]

def main():
    n = int(input())

    ms = []
    for _ in range(n):
        r,c = map(int, input().split())
        ms.append(Mat(r,c))

    print(solve(n, ms))

if __name__ == "__main__": main()

Measured memory_bytes: 9068
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>
#include<bitset>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define m0(x) memset(x,0,sizeof(x))
#define print(x) cout<<x<<endl;
#define pe(x) cout<<x<<" ";
#define lb(v,n) lower_bound(v.begin(), v.end(), n);
#define ub(v,n) upper_bound(v.begin(), v.end(), n);
#define int long long
#define all(x) (x).begin(), (x).end()

using namespace std;

const int MAX = 1010000;
const int MOD = (ll)1000000000 + 7;
const ll INF = 1e17;
const double pi = acos(-1);
const double EPS = 1e-10;

int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0, };
typedef pair<int, int>P;

char maze[1010][1010];
int H, W;
vector<int> bx, by;
vector<int>Bx[3000], By[3000];
signed main() {
	cin >> H >> W;
	REP(i, H) {
		REP(j, W) {
			cin >> maze[i][j];
			if (maze[i][j] == '#') {
				bx.pb(i); by.pb(j);
				Bx[0].pb(i); By[0].pb(j);
			}
		}
	}
	int ans = 0;
	bool ok = 0;
	while (!ok) {
		ok = true;
		int n = ans;
		//print(ans);
		REP(i, Bx[n].size()) {
			int x = Bx[n][i], y = By[n][i];
			REP(j, 4) {
				int nx = x + dx[j], ny = dy[j] + y;
				if (nx >= 0 && nx < H&&ny >= 0 && ny < W) {
					if (maze[nx][ny] == '.') {
						if(ok) {
							ans++;
							ok = 0;
						}
						maze[nx][ny] = '#';
						Bx[ans].pb(nx); By[ans].pb(ny);
					}
				}
			}
		}
	}
	/*REP(i, H) {
		REP(j, W) {
			cout << maze[i][j];
		}
		cout << endl;
	}*/
	print(ans);
}


Measured memory_bytes: 40868
#include <stdio.h>

int main(){
    int N;
    int i;
    int ret;
    int V[50];
    int C[50];
    scanf("%d",&N);
    for(i=0;i<N;i++){
        scanf("%d",&V[i]);
    }
    for(i=0;i<N;i++){
        scanf("%d",&C[i]);
    }
    ret = 0;
    for(i=0;i<N;i++){
        if (V[i]>C[i]){
            ret += (V[i]-C[i]);
        }
    }
    printf("%d\n",ret);
    return 0;
}

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

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<double> vd;
typedef vector<string> vs;
typedef pair<int, int> P;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

void YN(bool flg){if(flg) cout << "YES" << endl; else cout << "NO" << endl;}
void Yn(bool flg){if(flg) cout << "Yes" << endl; else cout << "No" << endl;}
void yn(bool flg){if(flg) cout << "yes" << endl; else cout << "no" << endl;}

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

int main()
{   
    int n;
    cin >> n;
    string s;
    cin >> s;
    int r = 0;
    rep(i, n) if(s[i] == 'R') r++;

    int ans = r, w = 0;
    rep(i, n) {
        if(s[i]=='R') --r;
        else ++w;
        ans = min(ans, max(r,w));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3736
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream &operator << (ostream& out,const pair<S,T>& o){
    out << "(" << o.first << "," << o.second << ")"; return out;
}

/*
<url:https://arc067.contest.atcoder.jp/tasks/arc067_c>
問題文============================================================
 1 から N までの番号のついた N 人の人がいます。
 以下の二つの条件を満たすように、彼らをいくつかのグループに分けたいです。
 
 どのグループも、そのグループに含まれる人数が A 人以上 B 人以下である。
 
 ちょうど i 人の人が含まれるようなグループの数を Fi で表したとき、
 すべての i について、Fi=0 または C≦Fi≦D が成り立っている。
 
 このようなグループ分けが何通りあり得るか求めてください。
 ただし、ある二つのグループ分けが異なるとは、二人の人の組であって、
 片方のグループ分けでは同じグループに含まれ、
 他方では同じグループに含まれないようなものが存在することを意味します。
 なお、答えは非常に大きくなることがあるので、109+7 で割った余りを出力してください。

 1≦N≦10^3
 1≦A≦B≦N
 1≦C≦D≦N
=================================================================

解説=============================================================

================================================================
*/
#define MAX_N 1005
const ll MOD = 1e9+7;
ll Inv[MAX_N];
ll fact[MAX_N];
ll factInv[MAX_N];
void Inv_init(){
    Inv[1] = 1;
    for(int i = 2; i < MAX_N; i++) Inv[i] = Inv[MOD%i] * (MOD - MOD/i) % MOD;
}
void fact_init(){
    fact[0] = fact[1] = factInv[0] = factInv[1] = 1;
    for(int i = 2; i < MAX_N; i++){
        fact[i] = (fact[i-1] * i) % MOD; factInv[i] = (factInv[i-1] * Inv[i])%MOD;
    }
}

// a^b % MOD;
ll powmod(ll a,ll b) {ll res=1;a%=MOD; for(;b;b>>=1){if(b&1)res=res*a%MOD;a=a*a%MOD;}return res;}
// 逆元 1/a % MOD
ll inversemod(ll a) { return powmod(a,MOD - 2);}
ll nCr(ll n,ll r) {
    if(n < r) return 0;
    return (fact[n] * (factInv[r] * factInv[n-r] % MOD)) % MOD;
}

void init(){
    Inv_init();
    fact_init();
}

ll N,A,B,C,D;
ll memo[MAX_N][MAX_N]; // memo[n][a] := 残り人数が n で 指定人数が a 以上の時の総数
void init2(){
    for(int i = 0; i < MAX_N;i++)for(int j = 0; j < MAX_N;j++) memo[i][j] = -1;
}
ll dfs(ll n,ll a){
    ll &res = memo[n][a];
    if(res != -1) return res;
    if(n == 0) return res = 1;
    if(n < a || a > B) return res = 0;
    
    res = 0;
    (res += dfs(n,a+1))%=MOD;
    ll F = 1;
    for(ll x = 1; x <= D; x++){
        if(a > n) break;
        (F *= nCr(n,a))%=MOD; (F *= Inv[x])%=MOD; n-=a;
        if(x >= C){ (res += F*dfs(n,a+1))%=MOD; }
    }
    return res;
}
ll solve(){
    ll res = 0;
    cin >> N >> A >> B >> C >> D;
    res = dfs(N,A);
    return res;
}
int main(void) {
	cin.tie(0); ios::sync_with_stdio(false);
    init();
    init2();
    cout << solve() << endl;
	return 0;
}


Measured memory_bytes: 8320
#include<bits/stdc++.h>
#define del(a,i) memset(a,i,sizeof(a))
#define ll long long
#define inl inline
#define il inl void
#define it inl int
#define ill inl ll
#define re register
#define ri re int
#define rl re ll
#define INF 0x3f3f3f3f
#define lowbit(x) (x&(-x))
#define mid ((l+r)>>1)
using namespace std;
template<class T>il read(T &x){
	x=0;int f=1;char k=getchar();
	for(;k>'9'||k<'0';k=getchar()) if(k=='-') f=-1;
	for(;k>='0'&&k<='9';k=getchar()) x=x*10+k-'0';
	x*=f;
}
template<class T>il _print(T x){
	if(x>9) _print(x/10);
	putchar(x%10+'0');
}
template<class T>il print(T x){
	if(x<0) putchar('-'),x=-x;
	_print(x);
}
int n,val;
int main(){
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	char flag=1;
	read(n);
	for(ri i=1;i<=n;++i){
		read(val);
		if(val%2==0) flag&=(val%3==0||val%5==0);
	}
	puts(flag?"APPROVED":"DENIED");
	return 0;
}

Measured memory_bytes: 256