akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()

using namespace std;
using ll = long long;
using vpii = vector<pair<int, int>>;
using vpll = vector<pair<ll, ll>>;
// ceil() 切り上げ, floor() 切り捨て
// next_permutation(all(x))

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

	int L = 0, R = W, B = 0, T = H;
	for (int i = 0; i < N; i++)
	{
		int x, y, a;
		cin >> x >> y >> a;
		if (a == 1)
			L = max(L, x);
		if (a == 2)
			R = min(R, x);
		if (a == 3)
			B = max(B, y);
		if (a == 4)
			T = min(T, y);
	}
	if (L >= R || B >= T)
		cout << 0 << endl;
	else
		cout << (R-L) * (T-B) << endl;
}



Measured memory_bytes: 256
import java.util.Scanner;
class Main{
	public static void main(String[] args){
		Scanner scan = new Scanner(System.in);
		int n = scan.nextInt();
		for(int i = 0;i < n;i++){
			double[] x = new double[4];
			double[] y = new double[4];
			for(int j = 0;j < 4;j++){
				x[j] = scan.nextDouble();
				y[j] = scan.nextDouble();
			}
			double a1 = 0;
			double a2 = 0;
			double b1 = 0;
			double b2 = 0;
			if(x[0]-x[1] != 0){
				a1 = (y[0]-y[1])/(x[0]-x[1]);
				b1 = (x[0]*y[1] - x[1]*y[0])/(x[0]-x[1]);
			}else{
				a1 = 10000;
				b1 = x[0];
			}
			if(x[2] - x[3] != 0){
				a2 = (y[2]-y[3])/(x[2]-x[3]);
				b2 = (x[2]*y[3] - x[3]*y[2])/(x[2]-x[3]);
			}else{
				a2 = 10000;
				b2 = x[2];
			}
			if(a1 == a2){
				System.out.println("YES");
			}else{
				System.out.println("NO");
			}
		}
	}
}

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

#define REP(i,n) for(int i=0;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<29
#define LINF LLONG_MAX/3
#define MP make_pair
#define PB push_back
#define EB emplace_back
#define ALL(v) (v).begin(),(v).end()
#define debug(x) cerr<<#x<<":"<<x<<endl
#define debug2(x,y) cerr<<#x<<","<<#y":"<<x<<","<<y<<endl
#define CININIT cin.tie(0),ios::sync_with_stdio(false)
template<typename T> ostream& operator<<(ostream& os,const vector<T>& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; }

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;

ll R,C,N;
vector<ll> r,c,a;

vector<ll> rn,cn;
vector<bool> ru,cu;

ll mini[2];

void dfs(int s,int type,const vector<vector<pii>>& gr,const vector<vector<pii>>& gc){
    vector<pii> g;
    if(type==0) g=gr[s];
    else g=gc[s];
    if(type==0) ru[s]=true;
    else cu[s]=true;

    if(type==0){
        mini[0] = min(mini[0],rn[s]);
    }else{
        mini[1] = min(mini[1],cn[s]);
    }

    for(auto p : g){
        int v = p.first;
        int cost = p.second;
        int ntype = !type;
        if(ntype==0 and ru[v]) continue;
        if(ntype!=0 and cu[v]) continue;

        if(ntype==0) rn[v]=cost-cn[s];
        else cn[v]=cost-rn[s];
        dfs(v,!type,gr,gc);
    }
}

int main(){
    CININIT;
    cin>>R>>C;
    cin>>N;

    vector<vector<pii>> vr(R),vc(C);
    rn.assign(R,0);
    cn.assign(C,0);
    ru.assign(R,false);
    cu.assign(C,false);
    rep(i,N){
        ll rr,cc,aa;
        cin>>rr>>cc>>aa;
        rr--;
        cc--;
        r.push_back(rr);
        c.push_back(cc);
        a.push_back(aa);

        vr[rr].push_back(pii(cc,aa));
        vc[cc].push_back(pii(rr,aa));
    }

    for(int i=0;i<R;i++){
        if(!ru[i]){
            mini[0] = mini[1] = LINF;
            dfs(i,0,vr,vc);
            if(mini[0] + mini[1] < 0){
                cout << "No" << endl;
                return 0;
            }
        }
    }
    for(int i=0;i<C;i++){
        if(!cu[i]){
            mini[0] = mini[1] = LINF;
            dfs(i,1,vr,vc);
            if(mini[0] + mini[1] < 0){
                cout << "No" << endl;
                return 0;
            }
        }
    }

    for(int i=0;i<N;i++){
        ll b = rn[r[i]] + cn[c[i]];
        if(b!=a[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}


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

int main()
{
    int n, x;
    cin >> n >> x;

    int a[n];
    for(int i = 0; i < n; i++) cin >> a[i];

    long long ans = 0;
    for(int i = 1; i < n; i++){
        int t = a[i - 1] + a[i];
        if(t <= x) continue;
        ans += t - x;
        a[i] -= min(t - x, a[i]);
    }
    cout << ans << endl;

    return 0;
}


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

using namespace std;

int main(){
  int n,m,i,k;
  vector<string>N(100);
  vector<string>M(100);
  vector<int>tasuN(100);
  vector<int>mainasuN(100);
  //読み込み
  cin >> n;
  for(i=0; i<n; i++){
    cin >> N.at(i);
  }
  cin >> m;
  for(i=0; i<m; i++){
    cin >> M.at(i);
  }
  //+採点
  for(i=0; i<n; i++){
    for(k=0; k<=i; k++){
      if(N.at(i) == N.at(k)){
        tasuN.at(i) ++;
      }
    }
  }
  
  for(i=0; i<n; i++){
    for(k=0; k<m; k++){
      if(N.at(i) == M.at(k)){
        tasuN.at(i) --;
      }
    }
  }
  int Max=0;
  for(i=0; i<n; i++){
    if(tasuN.at(i) > Max){
      Max = tasuN.at(i);
    }
  }
  cout << Max << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<string>
#include <sstream>
using namespace std;
int main()
{
  string s;
  string a, b;
  int ai, bi;
  cin >> s;
  a=s.substr(0,2);
  b=s.substr(2,4);
  ai = atoi(a.c_str());
  bi = atoi(b.c_str());
  if(((ai==0)||(ai>=13&&ai<=99))&&(bi>=1&&bi<=12)) cout<<"YYMM";
  else if((ai>=1&&ai<=12)&&((bi==0)||(bi>=13&&bi<=99))) cout<<"MMYY";
  else if((ai>=1&&ai<=12)&&(bi>=1&&bi<=12)) cout<<"AMBIGUOUS";
  else cout<<"NA";
  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <ctype.h>

int main(){
    int count[26]={0};
    char ch;
    int i, num;

    while(scanf("%c", &ch)!=EOF){
        if(islower(ch)){
            num=ch-'a';
        }else if(isupper(ch)){
            num=ch-'A';
        }else{
            continue;
        }
        count[num]++;
    }
    for(i=0;i<26;i++){
        printf("%c : %d\n", 'a'+i, count[i]);
    }

    return 0;
}


Measured memory_bytes: 2676
mod = int(1e9) + 7

n = int(input())
s1 = input()
s2 = input()

if s1[0] == s2[0]:
    ans = 3
    i = 1
else:
    ans = 6
    i = 2
while i < n:
    #print(ans, i,s1[i],s2[i],s1[i-1],s2[i-1])
    if s1[i] == s2[i]:

        if s1[i-1] == s2[i-1]:
            ans *= 2
            ans %= mod
        i += 1
    else:

        if s1[i-1] == s2[i-1]:
            ans *= 2
            ans %= mod
        else:
            ans *= 3
            ans %= mod
        i += 2
print(ans)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#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 show(x) {for(auto i: x){cout << i << " ";} cout<<endl;}
#define showm(m) {for(auto i: m){cout << m.x << " ";} cout<<endl;}
typedef long long ll;
typedef pair<int, int> P;
ll gcd(int x, int y){ return y?gcd(y, x%y):x;}
ll lcm(ll x, ll y){ return (x*y)/gcd(x,y);}


int main()
{
    int n, m;
    cin >> n >> m;
    vector<P> a(m);
    rep(i, m){ 
        cin >> a[i].first >> a[i].second;
    }
    vector<int> keta(n, 10); //keta[0] 最上位

    rep(i, m){
        int tk = a[i].first-1;
        if (keta[tk] != 10 && keta[tk] !=  a[i].second){
            cout << "-1" << endl; return 0;
        } else {
            keta[tk] = a[i].second;
        }
    }

    rep(i, n){
        if (i== 0 && keta[i] == 0 && n != 1){
            cout << "-1" << endl; return 0;
        } else {
            if (keta[i] == 10){
                if (i == 0 && n != 1){
                    keta[i] = 1;
                } else {
                    keta[i] = 0;
                }
            }
        }
        cout << keta[i];
    }


}



Measured memory_bytes: 256
import itertools
import math

def dis(x1,y1,x2,y2):
 d = math.sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2))
 return d

N = int(input())
pos = []
for i in range(N):
  x,y = map(int,input().split())
  pos.append([x,y])

seq = []
for i in range(N): seq.append(i)
per = list(itertools.permutations(seq))

ave = 0
for i in range(len(per)):
  tmp = list(per[i])
  for j in range(len(tmp)):
    if(j != 0):
      ave += dis(pos[tmp[j-1]][0],pos[tmp[j-1]][1],pos[tmp[j]][0],pos[tmp[j]][1])
ave = ave/len(per)
print(ave)


Measured memory_bytes: 7972
// Author: droftware
#include <bits/stdc++.h>

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

#define TRACE
#ifdef TRACE
#define trace1(x)                cerr << #x << ": " << x << endl;
#define trace2(x, y)             cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
#define trace3(x, y, z)          cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
#define trace4(a, b, c, d)       cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
#define trace5(a, b, c, d, e)    cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
#define trace6(a, b, c, d, e, f) cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
#else
#define trace1(x)
#define trace2(x, y)
#define trace3(x, y, z)
#define trace4(a, b, c, d)
#define trace5(a, b, c, d, e)
#define trace6(a, b, c, d, e, f)
#endif
using namespace std;

const int N = 400+5;
int nums[N];
long long dp[N][N], pre[N];

long long solve(int i, int j){
	if(dp[i][j] != 0)
		return dp[i][j];
	if(i == j){
		dp[i][j] = 0;
		// trace3(i,j,dp[i][j]);
		return dp[i][j];
	} 
	long long res = LLONG_MAX;
	for(int k = i; k < j; ++k){
		res = min(res, solve(i,k) + solve(k+1,j) + pre[j] - pre[i-1]);
	}
	dp[i][j] = res;
	// trace3(i,j,dp[i][j]);
	return dp[i][j];
}


int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(NULL);
	int n;
	cin>>n;
	rep(i,1,n+1){
		cin>>nums[i];
		pre[i] = pre[i-1] + nums[i];
	}
	cout<<solve(1,n)<<endl;
}

Measured memory_bytes: 1536
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <complex>
#include <cctype>
#include <cassert>

using namespace std;

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

#define INF (1<<29)
#define INFL (1ll<<60)
#define EPS (1e-8)
#define PI (acos(-1))
#define MOD 1000000007ll

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

typedef long long ll;
typedef complex<double> P;
typedef complex<double> Vec;
typedef pair<int, int> pii;
typedef pair<int, pii> p;

int n;
vector<int> g[100000];

int dfs(int pos) {
	vector<int> v;
	REP(i, g[pos].size()) v.push_back(dfs(g[pos][i]));
	sort(ALL(v), greater<int>());
	
	int res = 0;
	REP(i, v.size()) chmax(res, v[i] + i + 1);
	return res;
}

int main() {
	cin >> n;
	FOR(i, 1, n) {
		int a;
		scanf("%d", &a);
		a--;
		g[a].push_back(i);
	}
	
	cout << dfs(0) << endl;
	
	return 0;
}

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

using namespace std;

const int N = 100100;

int v[N];

int main() {
	int n, T;
	scanf("%d %d", &n, &T);

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

	int m = 0;
	int d = 0;
	for (int i = n - 1; i >= 0; i--) {
		m = max(m, v[i]);
		d = max(d, m - v[i]);
	}

	int ans = 0;
	priority_queue<int> pq;
	for (int i = n - 1; i >= 0; i--) {
		pq.push(v[i]);
		while (pq.size() && pq.top() - v[i] == d) {
			ans++;
			pq.pop();
		}
	}

	printf("%d\n", ans);

	return 0;
}


Measured memory_bytes: 1276
#include <map>
#include <iostream>

using namespace std;

int main() {
  double x,y;
  map<int,int> group{
  	{1,1},{2,3},{3,1},{4,2},{5,1},{6,2},
		{7,1},{8,1},{9,2},{10,1},{11,2},{12,1}
  };

  cin >> x >> y;
  if (group.at(x) == group.at(y)) cout << "Yes" << endl;
  else cout << "No" << endl;
}



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

#define REP(i, n) for (ll (i) = 0 ; (i) < (ll)(n) ; ++(i))
#define REPN(i, m, n) for (ll (i) = m ; (i) < (ll)(n) ; ++(i))
#define REP_REV(i, n) for (ll (i) = (ll)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (ll (i) = (ll)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long

typedef pair<ll, ll> P;
ll bit_kosu[61];


int main(){
    int n, k;
    cin >> n >> k;
    vector<int> x(n);
    REP(i, n) cin >> x[i];
    sort(x.begin(), x.end());
    int ans = INF;

    REP(i, n-k+1) {
        ans = min(ans, abs(x[i]) + abs(x[i+k-1] - x[i]));
        ans = min(ans, abs(x[i+k-1]) + abs(x[i+k-1] - x[i]));
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 640
fun main(args: Array<String>) = println(run {
    val (n,m) = readLine()!!.split(" ").map { it.toInt() }
    val a = (1..m).map { readLine()!!.toInt() }

    val ok = BooleanArray(n+2) { a.binarySearch(it) < 0 }
    val dp = IntArray(n+2)
    dp[0] = 1
    for (i in 0..n-1) {
        if (ok[i+1]) dp[i+1] = (dp[i] + dp[i+1]) % 1000000007
        if (ok[i+2]) dp[i+2] = (dp[i] + dp[i+2]) % 1000000007
    }
    dp[n]
})

Measured memory_bytes: 44372
#include<iostream>
#include<string>
#include<deque>
using namespace std;
int n;
int main(){
	cin>>n;
	deque<int> Q;
	for(int i=0;i<n;i++){
		int a;
		cin>>a;
		if(i%2==0){
			Q.push_back(a);
		}
		else{
			Q.push_front(a);
		}
	}
	if(n%2==0){
		for(int i=0;i<n;i++){
			cout<<Q[i];
			if(i==n-1)
			cout<<"\n";
			else
			cout<<" ";
		}
	}
	else{
		for(int i=0;i<n;i++){
			cout<<Q[n-1-i];
			if(i==n-1){
				cout<<"\n";
			}
			else{
				cout<<" ";
			}
		}
	}
    return 0;
}

Measured memory_bytes: 3072
#include<stdio.h>
int main()
{
	int n,sum=0,i,a[3000];
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d ",&a[i]);
	}
	for(i=0;i<n;i++){
		sum = sum + a[i];
	}
	printf("%d",sum-n);
	return 0;
}

Measured memory_bytes: 128
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

const int cm = 1 << 17;
char cn[cm], * ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

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


	int H = getint(), N = getint();
	int goukei = 0;
	rep(i, N) goukei += getint();
	if (goukei >= H) printf("Yes");
	else printf("No");

	Would you please return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1LL<<60;
const int MOD = (int)1e9 + 7;

signed main() {
    int n;
    cin >> n;
    vector<int> v(n - 1);
    for (int i = 0; i < n - 1; i++) {
        cin >> v[i];
    }
    reverse(v.begin(), v.end());
    v.push_back(INF);
    int sum = v[0];
    for (int i = 0; i < n - 1; i++) {
        sum += min(v[i], v[i + 1]);
    }
    cout << sum << "\n";
}

Measured memory_bytes: 256
import java.util.*;
public class Main {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		ArrayList<String> expr = new ArrayList<String>();
		while(s.hasNext()){
			expr.add(s.next());
		}

		ArrayList<Integer> buffer = new ArrayList<Integer>();
		Integer left = 0;
		Integer right = 0;
		while(expr.size() > 0){
			if(expr.get(0).equals("+")){
				right = buffer.remove(buffer.size() - 1);
				left = buffer.remove(buffer.size() - 1);

				buffer.add(left + right);
				expr.remove(0);
			}
			else if(expr.get(0).equals("-")){
				right = buffer.remove(buffer.size() - 1);
				left = buffer.remove(buffer.size() - 1);

				buffer.add(left - right);
				expr.remove(0);
			}
			else if(expr.get(0).equals("*")){
				right = buffer.remove(buffer.size() - 1);
				left = buffer.remove(buffer.size() - 1);

				buffer.add(left * right);
				expr.remove(0);
			}
			else{
				buffer.add(toi(expr.remove(0)));
			}
		}
		System.out.println(buffer.get(0));
	}
	private static Integer toi(String b){
		return Integer.parseInt(b);
	}

}

Measured memory_bytes: 19356
#include <stdio.h>

int main(void) {
	int paper[14][14] = {{0},{0}}, x,y,size, i;
	const int range[3][13][2] = {
		{
			{0,0},
			{1,0},
			{-1,0},
			{0,1},
			{0,-1},
			{3,3},
			{3,3},
			{3,3},
			{3,3},
			{3,3},
			{3,3},
			{3,3},
			{3,3},
		},
		{
			{0,0},
			{1,0},
			{-1,0},
			{0,1},
			{0,-1},
			{-1,-1},
			{1,1},
			{1,-1},
			{-1,1},
			{3,3},
			{3,3},
			{3,3},
			{3,3},
		},
		{
			{0,0},
			{1,0},
			{-1,0},
			{0,1},
			{0,-1},
			{-1,-1},
			{1,1},
			{1,-1},
			{-1,1},
			{0,2},
			{0,-2},
			{-2,0},
			{2,0},
		}
	};
	
	while(scanf("%d,%d,%d", &x,&y,&size) != EOF){
		for(i = 0;13 > i; i++){
			if(range[size-1][i][0] == 3) break;
			paper[x+2+range[size-1][i][0]][y+2+range[size-1][i][1]]++;
		}
	}
	
		int blank = 0, most = -1;
		for(i = 0;100 > i; i++){
			if(paper[i/10+2][i%10+2] == 0) blank++;
			if(most < paper[i/10+2][i%10+2]) most = paper[i/10+2][i%10+2];
		}
		printf("%d\n%d\n", blank, most);
	return 0;
}

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

string s,t;

vector<int> z_algo(const string &str) {
    vector<int> pref(str.size());
    for(int i=1,j=0; i<str.size(); ++i) {
        if(pref[i-j]+i<pref[j]+j) {
            pref[i]=pref[i-j];
        } else {
            int x=max(0,pref[j]+j-i);
            while(x+i<str.size() && str[x+i]==str[x]) {
                ++x;
            }
            pref[i]=x;
            j=i;
        }
    }
    pref[0]=str.size();
    return pref;
}

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

    cin>>s>>t;

    string u=t+s;
    auto tmp=z_algo(u);
    vector<int> l_pref(tmp.begin()+t.size(),tmp.end());

    u=s+t;
    reverse(begin(u),end(u));
    tmp=z_algo(u);
    vector<int> r_pref(tmp.begin()+t.size(),tmp.end());
    reverse(begin(r_pref),end(r_pref));

    int ans=0;
    for(int i=0; i-1+t.size()<s.size(); ++i) {
        int l=l_pref[i];
        int r=r_pref[i-1+t.size()];
        if(l+r+1==t.size()) {
            ans++;
        }
    }

    cout<<ans<<endl;
}


Measured memory_bytes: 8616
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
if (sum(A)+sum(B)+sum(C))/3 == A[0]+B[1]+C[2] == A[2]+B[1]+C[0]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
#include<stdio.h>

int main(void){
	int n,a[10000],i,max=0,min=10000000;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d", &a[i]);
		if (max < a[i])
			max = a[i];
		if (min > a[i])
			min = a[i];
	}
	printf("%d\n",max-min);
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;
using ll = long long;

template<typename T>
void compress(const vector<T> &src, unordered_map<T, int> &zip, vector<T> &unzip){
    unzip = src;
    sort(unzip.begin(), unzip.end());
    unzip.erase(unique(unzip.begin(), unzip.end()), unzip.end());
    int i = 0;
    for (auto u : unzip) zip[u] = i++;
};

template<typename T>
struct BIT{
    vector<T> bit;
    BIT(int n) : bit(n, 0){}
    T range_sum(int i, int j) {return sum(j) - sum(i - 1);}
    // return sum of v[i] to v[j] including both ends.
    T sum(int j){
        T s = 0;
        for (; j >= 0; j = (j & (j + 1)) - 1) s += bit[j];
        return s;
    }
    void add(int k, T a) {for (; k < bit.size(); k |= k + 1) bit[k] += a;}
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N, K;
    cin >> N >> K;
    vector<ll> A(N, 0);
    for (auto & a : A) cin >> a;
    vector<ll> cum(N + 1, 0);
    for (int i = 0; i != N; ++i) cum[i + 1] = cum[i] + A[i] - K;
    unordered_map<ll, int> zip;
    vector<ll> unzip;
    compress(cum, zip, unzip);
    int n = unzip.size();
    BIT<ll> freq(n);
    for (auto c : cum) freq.add(zip[c], 1);
    ll ans = 0;
    for (auto c : cum){
        freq.add(zip[c], -1);
        ans += freq.range_sum(zip[c], n - 1);
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 14792
#include <bits/stdc++.h>
#include<cmath>
using namespace std;
#define int long long int
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define F first
#define S second
#define all(a) a.begin(),a.end()
#define endl '\n'
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mod 1000000007
#define inf 1e18
#define pf push_front
#define pob pop_back
#define pof pop_front
#define deb(x) cout<<#x<<" "<<x<<endl;
#define deb2(x,y) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<endl;
#define deb3(x,y,z) cout<<#x<<" "<<x<<" "<<#y<<" "<<y<<" "<<#z<<" "<<z<<endl;
#define file freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);

typedef pair<int,int> pi;
typedef pair<int,pair<int,int>> piii;
typedef vector<int> vi;
typedef vector<pi> vpi;
typedef vector<vi> vvi;

int32_t main()
{
   // boost
    int t=1;
  //  cin>>t;
    while(t--)
    {
        int n;
        cin>>n;

        int mx1=LLONG_MIN,mx2=LLONG_MIN,mn1=LLONG_MAX,mn2=LLONG_MAX;

        while(n--)
        {
            int x,y;
            cin>>x>>y;
            mx1=max(mx1,x+y);
            mn1=min(mn1,x+y);
            mx2=max(mx2,x-y);
            mn2=min(mn2,x-y);
        }
        cout<<max(mx1-mn1,mx2-mn2);
    }


    

}

Measured memory_bytes: 3628
object Main
{
    def main(args:Array[String]) =
    {
        val s = new java.util.Scanner(System.in)

        val a = s.nextInt
        val b = s.nextInt
        val c = s.nextInt
        val d = s.nextInt

        if(a + b == c + d)println("Balanced")
        else if(a + b > c + d)println("Left")
        else if(a + b < c + d)println("Right")
    }
}

Measured memory_bytes: 25892
# 20/5/28
import sys
sys.setrecursionlimit(3 * 10 ** 5)
input = sys.stdin.readline

def bfs(root):
    global AL, cnt, visited
    visited[root] = True
    for v in AL[root]:
        if not visited[v]:
            cnt[v] += cnt[root]
            bfs(v)

N, Q = [int(x) for x in input().split()]
AL = [[] for _ in range(N + 1)]
for i in range(1, N):
    a, b = [int(x) for x in input().split()]
    AL[a].append(b)
    AL[b].append(a)

cnt = [0] * (N + 1)
for j in range(Q):
    p, x = [int(x) for x in input().split()]
    cnt[p] += x

visited = [False] * (N + 1)
bfs(1)
s = " ".join(map(str, cnt[1:]))
print(s)

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

#define select(_1, _2, x, ...) x

#define repn(i, n) for (int i = 0; i < (n); i++)
#define repr(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, ...) select(__VA_ARGS__, repr, repn)(i, __VA_ARGS__)

#define rrepn(i, n) for (int i = (n - 1); i >= 0; i--)
#define rrepr(i, a, b) for (int i = (b - 1); i >= (a); i--)
#define rrep(i, ...) select(__VA_ARGS__, rrepr, rrepn)(i, __VA_ARGS__)

#define umax(m, x) (m = max(m, x))
#define umin(m, x) (m = min(m, x))

#define rng(v) v.begin(), v.end()
#define rrng(v) v.rbegin(), v.rend()

#define bit(x, n) ((x) >> (n) & 1)
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;

using ll = long long int;

using vi = vector<int>;
using vl = vector<ll>;
using vb = vector<bool>;
using vc = vector<char>;
using vs = vector<string>;

using vvi = vector<vector<int>>;
using vvl = vector<vector<ll>>;
using vvb = vector<vector<bool>>;
using vvc = vector<vector<char>>;
using vvs = vector<vector<string>>;

const int INF = 1e9;
const ll LINF = 1e18;

inline void yn(bool f) { cout << (f ? "Yes" : "No") << endl; }


int main() {
    int n;
    cin >> n;
    vi s(n);
    rep(i, n) cin >> s[i];
    int q;
    cin >> q;
    vi t(q);
    rep(i, q) cin >> t[i];

    int cnt = 0;
    rep(i, q)
        if (binary_search(rng(s), t[i])) cnt++;

    cout << cnt << endl;

    return 0;
}



Measured memory_bytes: 3344
#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++)
typedef long long ll;
const int mod = 1e9 + 7;
const int INF = 1e9;
int main(){
    int n; cin >> n;
    map<string, ll>  mp;
    rep(i,n){
        string s; cin >> s;
        sort(s.begin(), s.end());
        mp[s]++;
    }
    ll r = 0;
    for(map<string, ll>::iterator it = mp.begin(); it != mp.end(); it++){
        ll k = it->second;
        r += k*(k-1)/2;
        //cout << k << endl;
    }
    cout << r << endl;
    return 0;
}

Measured memory_bytes: 11136
#include <iostream>
#include <algorithm>
#include <utility>
#include <cmath>
#include <map>
using namespace std;
#define ll long long
#define rep(i, n) for(int i=0; i<n; ++i)

int main() {
  int n;
  string s;
  cin >> n >> s;
  int a1[26] = {};
  int a2[26] = {};
  int max = -1;
  int t;

  rep(i, n-1) {
    t = 0;
    for(int j=0; j<=i; ++j) {
      a1['z'-s[j]] = 1;
    }

    for(int k=i+1; k<n; ++k) {
      a2['z'-s[k]] = 1;
    }

    for(int l=0; l<26; ++l) {
      if(a1[l] == 1 && a2[l] == 1) {
        t += 1;
      }
      a1[l] = a2[l] = 0;
    }

    if(max < t) max = t;
  }

  cout << max << endl;

  return 0;
}


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

int main() {
  int N;
  string input_string;
  
  cin >> N;
  
  int sum_AC = 0;
  int sum_WA = 0;
  int sum_TLE = 0;
  int sum_RE = 0;
  for (int i = 0; i < N; i++) {
    cin >> input_string;
    
    if (input_string == "AC") sum_AC++;
    else if (input_string == "WA") sum_WA++;
    else if (input_string == "TLE") sum_TLE++;
    else if (input_string == "RE") sum_RE++;
  }
  
  cout << "AC x " << sum_AC << endl;
  cout << "WA x " << sum_WA << endl;
  cout << "TLE x " << sum_TLE << endl;
  cout << "RE x " << sum_RE << endl;
  
}

Measured memory_bytes: 3628
#include<bits/stdc++.h>
using namespace std ;
int main(){
    int K ;
    int a[100010] ;
    long long ansx[100010] , ansd[100010] ;
    bool flag ;
    flag = true ;
    cin >> K ;
    for( int i = 1 ; i <= K ; i++ )
        scanf( "%d" , &a[i] ) ;
    ansx[K + 1] = ansd[K + 1] = 2 ;
    for( int i = K ; i >= 1 ; i-- ){
        long long xiao = ( ansx[i + 1] + a[i] - 1 ) / a[i] ;
        long long da = ansd[i + 1] / a[i] ;
        if ( xiao > da ) flag = false ;
        ansx[i] = xiao * a[i] ;
        ansd[i] = da * a[i] + a[i] - 1 ;
    }
    if ( flag ) cout << ansx[1] << " " << ansd[1] << endl ;
    else cout << -1 << endl ;
    return 0 ;
}

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

using namespace std;

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

typedef long long ll;

const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    string s;
    cin >> n >> s;
    char tmp = s[0];
    int ans = 1;
    rep (i, n) {
        if (tmp == s[i]) continue;
        ans++;
        tmp = s[i];
    }
    cout << ans << endl;
    
    return 0;
}



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

int main() {
  int W,A,B;
  cin >> W >> A >> B;
  if(A+W<=B){
    cout << max(B-A-W,0) << endl;
  }
  else{
    cout << max(A-B-W,0) << endl;
  }
}

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

using namespace std;

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



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

    string a, b;
    cin >> a >> b;
    int n = stoi(a + b);
    int sq = sqrt(n);
    cout << (sq * sq == n ? "Yes" : "No");
}


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

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }

lli ext_gcd(lli a, lli b, lli &x, lli &y)
{
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    lli d = ext_gcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

lli mod_inverse(lli a, lli m)
{
  lli x, y;
  ext_gcd(a, m, x, y);
  return (m + x % m) % m;
}

constexpr lli mod = 1e9 + 7;
constexpr int N = 1e5 * 2 + 10;
lli fact[N];
lli fact_inverse[N];

lli nCr(lli n, lli r)
{
  return (((fact[n] * fact_inverse[r]) % mod) * fact_inverse[n - r]) % mod;
}
int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  fact[0] = 1;
  for (int i = 1; i < N; ++i) {
    fact[i] = (fact[i - 1] * i) % mod;
  }
  for (int i = 0; i < N; ++i) {
    fact_inverse[i] = mod_inverse(fact[i], mod);
  }

  int h, w, a, b;
  while (cin >> h >> w >> a >> b) {
    lli sum = 0;
    for (int i = 0; i < h - a; ++i) {
      int p = w - b - 1 + h - i - 1;
      int q = w - b - 1;
      lli x = nCr(b + i - 1, i) * nCr(p, q);
      (sum += x % mod) %= mod;
    }
    cout << sum << endl;
  }

  return 0;
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
using namespace std;
     
     
//#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long
#define sd(x) scanf("%d",&x)
#define sld(x) scanf("%lld",&x)
#define pld(x) printf("%lld\n",x)
#define pd(x) printf("%d\n",x)

#define pqueue priority_queue<int,vector<int>,greater<int >> 
     
     
int main(){

	int n; sd(n);

	int arr[n];

	for(int i =0 ; i< n ;i++){
		sd(arr[i]);
	}




	int max = 0;

	bool repeating = false;

	for(int i = 1; i< n ;i++){
		if(arr[max] < arr[i] ){
			repeating = false;
			max = i;

		

		}else if(arr[max] == arr[i]){
		 repeating = true;
	
		}
	}



    
	


    if(repeating == false){
    	for(int i = 0; i< n ; i++){
    		if(i != max)printf("%d\n",arr[max] );
    		else {
    			int temp = -1;
    			for(int i = 0 ; i< n; i++){
    				if(arr[i] > temp && arr[i] != arr[max] )temp = arr[i];

    			}

    			pd(temp);
    		}
    	}
    }else{
    	for(int i = 0; i< n; i++){
    		printf("%d\n",arr[max] );
    	}
    }     
     
        
    return 0;
}


Measured memory_bytes: 2432
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();
		int C = sc.nextInt();
		int D = sc.nextInt();
		int balance = (A + B) - (C + D);
		if (balance > 0) { 
			System.out.println("Left"); 
		} else if (balance == 0) {
			System.out.println("Balanced"); 
		} else {
			System.out.println("Right"); 
		}
	}
}


Measured memory_bytes: 21716
#include <bits/stdc++.h> // only for GCC
using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}

template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
typedef unsigned long long ULL;

#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define PB push_back
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

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

const double EPS = 1e-10;
const double PI  = acos(-1.0);

#define CLR(a) memset((a), 0 ,sizeof(a))

#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

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

int main() {
  int len[3];  
  int tri[4] = {};

  while(cin >> len[0] >> len[1] >> len[2]) {
    sort(len, len+3);
    int a = len[0], b = len[1], c = len[2];
    
    if(c >= a + b) break;
    tri[0]++;
    if(c*c == a*a + b*b) tri[1]++;
    else if(c*c < a*a + b*b) tri[2]++;
    else tri[3]++;
  }
  
  REP(i, 3) cout << tri[i] << ' ';
  cout << tri[3] << endl;
}

Measured memory_bytes: 1176
# 2つの入力を空白で分割し、数値化
a, b, k = map(int, input().split())

ans_a = max(0, a - k)
ans_b = None

if a - k < 0:
    ans_b = max(0, b - (k-a))
else:
    ans_b = b

print(str(ans_a) + " " + str(ans_b))

Measured memory_bytes: 2940
MOD = int(1e9+7)


def main():
    N, K = map(int, input().split())
    dp = [0] * (K+1)
    ans = 0
    for i in range(1, K+1)[::-1]:
        tmp = pow(K//i, N, MOD)
        for j in range(i*2, K+1, i):
            tmp = (tmp - dp[j]) % MOD
        dp[i] = tmp
        ans = (ans + tmp * i) % MOD
    print(ans)


if __name__ == "__main__":
    main()


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

typedef long long LL;
typedef unsigned long long ULL;

#define PrintLn(X) cout << X << endl
#define Loop(n) for(int loop_ = n; loop_; --loop_)
#define Rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define For(i, a, b) for(int i = a; i < (int)(b); ++i)

int a[100000];
int b[100000];
set<pair<int, int>> st;

LL H, W, N;
int exist(int a, int b){
	return (1 <= a && a <= H && 1 <= b && b <= W && st.count(pair<int, int>(a, b)));
}

int cou[9];

int main(void)
{
	LL ans[10] = {0};
	cin >> H >> W >> N;
	LL total = (H - 2) * (W - 2);

	Rep(i, N){
		cin >> a[i] >> b[i];
		st.insert(pair<int, int>(a[i], b[i]));
	}
	Rep(i, N){
		// xxx
		// xox
		// xxx
		Rep(x, 9){
			cou[x] = 0;
		}
		Rep(di, 5){
			Rep(dj, 5){
				if(exist(a[i] - 2 + di, b[i] - 2 + dj)){
					if(           di <= 2 &&            dj <= 2) cou[0]++;
					if(1 <= di && di <= 3 &&            dj <= 2) cou[1]++;
					if(2 <= di            &&            dj <= 2) cou[2]++;
					if(           di <= 2 && 1 <= dj && dj <= 3) cou[3]++;
					if(1 <= di && di <= 3 && 1 <= dj && dj <= 3) cou[4]++;
					if(2 <= di            && 1 <= dj && dj <= 3) cou[5]++;
					if(           di <= 2 && 2 <= dj           ) cou[6]++;
					if(1 <= di && di <= 3 && 2 <= dj           ) cou[7]++;
					if(2 <= di            && 2 <= dj           ) cou[8]++;
				}
			}
		}
		if(a[i] == 1) cou[0] = cou[1] = cou[3] = cou[4] = cou[6] = cou[7] = 0;
		if(b[i] == 1) cou[0] = cou[1] = cou[2] = cou[3] = cou[4] = cou[5] = 0;
		if(a[i] == 2) cou[0] = cou[3] = cou[6] = 0;
		if(b[i] == 2) cou[0] = cou[1] = cou[2] = 0;
		if(a[i] == H) cou[1] = cou[2] = cou[4] = cou[5] = cou[7] = cou[8] = 0;
		if(b[i] == W) cou[3] = cou[4] = cou[5] = cou[6] = cou[7] = cou[8] = 0;
		if(a[i] == H - 1) cou[2] = cou[5] = cou[8] = 0;
		if(b[i] == W - 1) cou[6] = cou[7] = cou[8] = 0;
		Rep(x, 9){
			if(cou[x])ans[cou[x]]++;
		}
	}

	For(i, 1, 10){
		ans[i] /= i;
	}

	ans[0] = total;
	For(i, 1, 10){
		ans[0] -= ans[i];
	}
	Rep(i, 10){
		PrintLn(ans[i]);
	}
	return 0;
}


Measured memory_bytes: 5760
#include <iostream>
#include <set>
#include <map>
#include <cmath>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <climits>
#include <math.h>
#include <cassert>
#include <unordered_map>
#include <chrono>
#include <random>
#include <ctime>
using namespace std;
#pragma warning(disable : 4996)
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

const ld PI = 3.14159265358979323846;
const ll MOD = 1e9 + 7;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll INF = 1e16;



int main() {
#ifdef _DEBUG
	freopen("input1.txt", "r", stdin);
	freopen("output2.txt", "w", stdout);
#endif
	srand(time(0));
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	cout << (n >= 30 ? "Yes" : "No");
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(signed i=0;i<n;++i)
#define repi(n) rep(i,n)
#define int long long
#define str string
#define vint vector<int>
#define pint pair<int,int>
#define pb(a) push_back(a)
#define all(v) v.begin(),v.end()
#define yn(b) cout<<((b)?"Yes":"No")<<endl
#define YN(b) cout<<((b)?"YES":"NO")<<endl
#define call(a) for(auto t:a)cout<<t<<" ";cout<<endl
#define ENDL printf("\n");
#define debg(a) cout<<#a<<":"<<a<<endl;
#define SORT(a) sort(all(a));
#define INF 1LL<<60
#define inf INF
#define out(i) cout<<i<<endl;
int min(int a,int b){if(a>b)return b;return a;}
int max(int a,int b){if(a>b)return a;return b;}

signed main(){
  int n;
  cin>>n;
  int md=n%11;
  n-=md;
  int res=n/11*2;
  if(md>0&&md<=6)res++;
  else if(md>6)res+=2;


  out(res);
  

  return 0;
}



Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#define N 5050
using namespace std;
const int Mod = 1e9 + 7;

inline void inc(int &x, const int &y) {
    x += y; if (x >= Mod) x -= Mod;
}

inline int MOD(const int &x) {
    return x >= Mod ? x - Mod : x;
}

int n, sz[N], f[N][N], t[N], c[N][N], fac[N], g[N];
vector<int> G[N];

void dfs(int u, int p) {
    sz[u] = f[u][1] = 1;
    for (int v : G[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int i = 0; i <= sz[u]; ++i)
            for (int j = 0; j <= sz[v]; ++j)
                t[i + j] = (t[i + j] + 1ll * f[u][i] * f[v][j])  % Mod;
        sz[u] += sz[v];
        for (int i = 0; i <= sz[u]; ++i)
            f[u][i] = t[i], t[i] = 0;
    }
    for (int i = 2; i <= sz[u]; i += 2)
        f[u][0] = (f[u][0] - 1ll * f[u][i] * g[i]) % Mod;
    if (f[u][0] < 0) f[u][0] += Mod;
}

int main() {
#ifdef isLOCAL
    freopen("work.in", "r", stdin);
    freopen("work.out", "w", stdout);
#endif

    cin >> n;

    for (int i = fac[0] = 1; i <= n; ++i)
        fac[i] = 1ll * fac[i - 1] * i % Mod;

    for (int i = 0; i <= n; ++i)
        for (int j = c[i][0] = 1; j <= i; ++j)
            c[i][j] = MOD(c[i - 1][j] + c[i - 1][j - 1]);

    g[0] = 1;

    for (int i = 2; i <= n; i += 2)
        g[i] = 1ll * g[i - 2] * (i - 1) % Mod;

    for (int i = 1, u, v; i < n; ++i) {
        scanf("%d%d", &u, &v);
        G[u].push_back(v);
        G[v].push_back(u);
    }

    dfs(1, 0);

    cout << Mod - f[1][0] << endl;

    return 0;
}


Measured memory_bytes: 198144
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>
#include<map>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
using P=pair<int,int>;
using lint=long long;
using ll=long long;
const lint inf=1e18+7;
const int MOD=1000000007;
signed main(){
  int n;cin>>n;
  vector<int> num(n+1,2);
  int res=1;
  for(int i=2;i<=n;++i){
    res+=num[i]*i;
    int buf=i;
    for(int j=1;j<=n;++j){
      if(buf*j>n)break;
      num[buf*j]+=1;
    }
  }
  rep1(i,4){
    //cout<<num[i]<<"\n";
  }
  cout<<res<<"\n";
  return 0;
}


Measured memory_bytes: 81396
#include<stdio.h>

int main (void) {
  long long int X;
  scanf("%lld",&X);

  long long int sum,tmp,ans;
  long long int i = 1;
  while(1){
    tmp += i;
    if(tmp>=X){
      ans = i;
      break;
    }
    i++;
  }

  printf("%lld\n",ans);

  return 0;
}


Measured memory_bytes: 128
N = gets.to_i 
X = Array.new(N).map{gets.split.map(&:to_i)}
     
puts X.inject{|a, x|
  r0 = (a[0] - 1) / x[0] + 1 
  r1 = (a[1] - 1) / x[1] + 1 
  r = r0 > r1 ? r0 : r1 
  x.map{|b| b * r} 
}.inject(:+)

Measured memory_bytes: 1788
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <tuple>
#include <utility>
#include <vector>
#define ll long long
#define double long double
#define itn int
#define endl '\n'
#define co(ans) cout<<ans<<endl
#define COYE cout<<"YES"<<endl
#define COYe cout<<"Yes"<<endl
#define COye cout<<"yes"<<endl
#define CONO cout<<"NO"<<endl
#define CONo cout<<"No"<<endl
#define COno cout<<"no"<<endl
#define FORE(i,a) for(auto &i:a)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define FFOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n)  FFOR(i,1,n)
#define PB push_back
#define MP make_pair
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort((V).begin(),(V).end())
#define REVERSE(V) reverse((V).begin(),(V).end())
#define EACH(V,i) for(typeof((V).begin()) i=(V).begin();i!=(V).end();++i)
#define INF ((1LL<<62)-(1LL<<31))
#define EPS 1e-10
#define PI 3.141592653589793238
#define MOD 1000000007
#define MAX 5100000
using namespace std;
using Graph=vector<vector<int>>;
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T>inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;
const int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
  ll H,W,h,w;
  cin>>H>>W>>h>>w;
  
  if(H%h==0 && W%w==0) CONo;
  else{
    COYe;
    ll A[H+1][W+1];
    RREP(i,H){
      RREP(j,W){
        if(i%h==0 && j%w==0) A[i][j]=(h*w-1)*500*(-1)-1;
        else A[i][j]=500;
      }
    }
    
    RREP(i,H){
      RREP(j,W){
        cout<<A[i][j]<<" ";
      }
      cout<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 3328
using System;

namespace ABC127B
{
    class Program
    {
        static void Main(string[] args)
        {
            var rDx = Console.ReadLine().Trim().Split(' ');
            var r = uint.Parse(rDx[0]);
            var D = uint.Parse(rDx[1]);
            var x_2000 = uint.Parse(rDx[2]);

            ulong x = x_2000;

            for (var i = 1; i <= 10; i++)
            {
                x = r * x - D;
                Console.WriteLine(x);
            }
        }
    }
}

Measured memory_bytes: 11092
import java.util.Scanner;

public class Main {

	static Scanner scanner;

	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    int n=gi();
	    
	    
        //System.out.println(n+m/2);
        if (n==3 || n==5 || n==7) {
        	System.out.print("YES");
        }else {
        	System.out.print("NO");
        }


	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 35636
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
class TEST{
	static void Main(){
		Sol mySol =new Sol();
		mySol.Solve();
	}
}
 
class Sol{
	public void Solve(){
		long Inf = (long) 1e18;
		long[] min = new long[N];
		for(int i=0;i<N;i++) min[i] = Inf;
		min[K] = 0;
		
		var q = new Queue<int>();
		q.Enqueue(K);
		while(q.Count>0){
			var now = q.Dequeue();
			foreach(var nxt in E[now]){
				if(min[nxt.Pos] != Inf) continue;
				min[nxt.Pos] = min[now] + nxt.Cost;
				q.Enqueue(nxt.Pos);
			}
		}
		
		var sb = new StringBuilder();
		foreach(var query in Query){
			int a = query[0], b = query[1];
			sb.AppendLine(String.Format("{0}",min[a] + min[b]));
		}
		Console.Write(sb.ToString());
	}
	int N;
	List<Pair>[] E;
	int Q,K;
	int[][] Query;

	public Sol(){
		N = ri();
		E = new List<Pair>[N];
		for(int i=0;i<N;i++) E[i] = new List<Pair>();
		for(int i=0;i<N-1;i++){
			var d = ria();
			E[d[0]-1].Add(new Pair(d[1]-1,d[2]));
			E[d[1]-1].Add(new Pair(d[0]-1,d[2]));
		}
		var dd = ria();
		Q = dd[0]; K = dd[1] - 1;
		Query = new int[Q][];
		for(int i=0;i<Q;i++){
			Query[i] = ria().Select(v => v-1).ToArray();
		}
	}
	class Pair{
		public int Pos;
		public long Cost;
		public Pair(int pos, long cost){
			Pos = pos; Cost = cost;
		}
	}
 
	static String rs(){return Console.ReadLine();}
	static int ri(){return int.Parse(Console.ReadLine());}
	static long rl(){return long.Parse(Console.ReadLine());}
	static double rd(){return double.Parse(Console.ReadLine());}
	static String[] rsa(char sep=' '){return Console.ReadLine().Split(sep);}
	static int[] ria(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>int.Parse(e));}
	static long[] rla(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>long.Parse(e));}
	static double[] rda(char sep=' '){return Array.ConvertAll(Console.ReadLine().Split(sep),e=>double.Parse(e));}
}

Measured memory_bytes: 48128
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    ll start=100,x;
    cin>>x;
    int cnt=0;
    while(start<x)
    {
        ll temp=start/100;
        start+=temp;
        cnt++;
    }
    cout<<cnt;
    return 0;
}






Measured memory_bytes: 3648
N=input()
A= map(int, raw_input().split())
B= map(int, raw_input().split())


if sum(B)>sum(A):
	print -1
	quit()

ans=0
L=[]
short_sum=0

for a,b in zip(A,B):
	if a<b:
		short_sum+=(b-a)
		ans+=1
	elif a>b:
		L.append(a-b)

L.sort(reverse=True)

if short_sum ==0:
	print 0
	quit()


for i, x in  enumerate(L):
	short_sum-=x
	if short_sum<=0:
		ans+=i+1
		break

print ans

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

int fib(int);
int *F;

int main(){
  int n,i;

  scanf("%d",&n);
  F=(int *)malloc(sizeof(int)*(n+1));
  for(i=0;i<=n;i++) F[i]=-1;

  printf("%d\n",fib(n));

  free(F);

  return 0;
}

int fib(int n){
  if(F[n]== -1){
    if(n==0||n==1) return F[n]= 1;
    return F[n]= fib(n-1)+fib(n-2);
  }
  else return F[n];
}
  

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

long long sum(long l,long r){
  return (l+r)*(r-l+1)/2;
}

int main(){
  int n,k;
  cin >> n >> k;
  long long ans=0;
  for(int i = k;i <= n+1; i++){
    long long small = sum(0,i-1);
    long long large = sum(n-i+1,n);
    //cout << small <<" " <<  large << endl;
    ans += large - small + 1;
  }
  cout << ans % 1000000007 << endl;
}

Measured memory_bytes: 3648