akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>

using namespace std;
using ll = long long;

template <typename K,typename V>
using umap = unordered_map<K,V>;
template <typename V>
using uset = unordered_set<V>;
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; }
#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(v) v.begin(),v.end()

#define endl "\n"
#define INF 1'000'000'000'000 //10^12
#define MOD 1'000'000'007
//グリッドグラフの範囲チェック
bool range_validation(int y,int x,int h,int w){
    return y>=0 && y<h && x>=0 && x < w;
}
//ビットカウント
int popcount(long bits){
    bits = (bits & 0x55555555) + (bits >> 1 & 0x55555555);
    bits = (bits & 0x33333333) + (bits >> 2 & 0x33333333);
    bits = (bits & 0x0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f);
    bits = (bits & 0x00ff00ff) + (bits >> 8 & 0x00ff00ff);
    return (bits & 0x0000ffff) + (bits >>16 & 0x0000ffff);
}

int gcd(ll a, ll b){
  if(b == 0){
    return a;
  }else{
    return gcd(b,a%b);
  }
}

vector<ll> sieve(ll n){
  vector<bool> is_prime(n+1,true);
  vector<ll> res;
  for(int i=2;i<=n;i++){
    if(is_prime[i]){
      res.push_back(i);
      for(int j=2*i;j<=n;j+=i){
        is_prime[j] = false;
      }
    }
  }
  return res;
}

vector<ll> divisor(ll n){
  vector<ll> list;
  for(int i=1;i*i<=n;i++){
    if(n%i==0){
      list.push_back(i);
      if(n/i != i){
        list.push_back(n/i);
      }
    }
  }
  return list;
}

umap<int,int> prime_factor(ll n){
  umap<int,int> fac;
  for(int i=2;i*i<=n;i+=2){
    if(n%i == 0){
      int count = 0;
      while(n%i == 0){
        count++;
        n /= i;
      }
      fac[i] = count;
    }
  }
  if(n!=1)fac[n] = 1;
  return fac;
}

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  int n;
  cin >> n;
  int x[n];
  int sum = 0;
  REP(i,n){
    cin >> x[i];
    sum += x[i];
  }
  int candi[2];
  candi[0] = sum / n;
  candi[1] = candi[0] + 1;
  int min = 10000000;
  REP(k,2){
    int temp = 0;
    REP(i,n){
      temp += (candi[k]-x[i])*(candi[k]-x[i]);
    }
    chmin(min,temp);
  }
  cout << min << endl;
  return 0;
}


Measured memory_bytes: 3604
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	int N;
	cin >> N;
	int X[200020];
	int tX[200020];

	for(int i = 0; i < N; i++) {
		cin >> X[i];
		tX[i] = X[i];
	}
	sort(tX, tX + N);
	int lm = tX[N / 2 - 1];
	int rm = tX[N / 2];

	for(int i = 0; i < N; i++) {
		if(X[i] <= lm) cout << rm << endl;
		else cout << lm << endl;
	}

	return 0;
}


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

long long N,K;
vector<long long> A;

bool isOK(long long mid){
  long long count=0;
  for(long long i=0;i<N;i++){
    if(A.at(i)==0){
      if(mid>=0)  count+=(N-(i+1));
    }
    else if(A.at(i)>0){
      long long tmp;
      if(mid>=0)  tmp=mid/A.at(i);
      else{
        long long mid_ab=-mid;
        tmp=-((mid_ab+A.at(i)-1)/A.at(i));
      }
      long long x=upper_bound(A.begin(),A.end(),tmp)-A.begin();
      x=x-(i+1);
      if(x>0) count+=x;
    }
    else if(A.at(i)<0){
      long long tmp;
      long long A_ab=-A.at(i);
      if(mid>=0)  tmp=-(mid/A_ab);
      else{
        long long mid_ab=-mid;
        tmp=(mid_ab+A_ab-1)/A_ab;
      }
      long long x=A.end()-lower_bound(A.begin()+i+1,A.end(),tmp);
      count+=x;
    }
  }
  if(count>=K)  return true;
  else  return false;
}

long long binary_search(){
  long long ng=-1e18-100;
  long long ok=1e18+100;
  while(abs(ok-ng)>1){
    long long mid=(ok+ng)/2;
    if(isOK(mid))  ok=mid;
    else  ng=mid;
  }
  return ok;
}

int main(){
  cin >> N >> K;
  A.resize(N);
  for(int i=0;i<N;i++)  cin >> A.at(i);

  sort(A.begin(),A.end());
  cout << binary_search() << endl;

  return 0;
}


Measured memory_bytes: 1792
#include<cstdio>
int main(){
	int n;
	scanf("%d",&n);
	--n;
	int ans=0;
	for(int l=1,r;l<=n;l=r+1)
	{
		r=n/(n/l);
		ans+=(r-l+1)*(n/l);
	}
	printf("%d",ans);
	return 0;
}

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

vector<int> G[100010];
int dp[100010];

int dfs(int v)
{
    int& res=dp[v];
    if (~res) return res;

    res=0;
    for(int u: G[v]) res=max(res, dfs(u)+1);
    return res;
}

int main()
{
    int n, m; cin>>n>>m;
    for(int i=0; i<m; ++i) {
        int x, y; cin>>x>>y;
        G[x-1].push_back(y-1);
    }
    fill(dp, dp+n, -1);

    for(int i=0; i<n; ++i) if (dp[i]<0) dfs(i);
    cout<<*max_element(dp, dp+n)<<endl;
}


Measured memory_bytes: 7424
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

int main()
{
    int k, n;
    cin >> k >> n;
    vector<int> a(n);
    for(int i=0; i<n; i++) cin >> a[i];

    int max_path = abs(a[1]-a[0]);
    for(int i=1; i<n-1; i++)
        max_path = max(max_path, abs(a[(i+1)]-a[i]));
    max_path = max(max_path, k - a[n-1] + a[0]);
    
    cout << k - max_path << endl;

    return 0;
}

Measured memory_bytes: 1024
# x k d

x, k, d = gets.split.map(&:to_i)

ans = 0
if x - (k-1)*d > 0
  ans = (x - k*d).abs
elsif x + (k-1)*d < 0
  ans = (x + k*d).abs
else
  if x > 0
    if (k - (x/d)).even?
      ans = (x - (x/d)*d).abs
    else
      ans = (x - ((x/d)+1)*d).abs
    end
  elsif x < 0
    if (k - (-x/d)).even?
      ans = (x + (-x/d)*d).abs
    else
      ans = (x + ((-x/d)+1)*d).abs
    end
  else # x == 0 
    if k.even?
      ans = 0
    else # k = odd
      ans = d
    end
  end
end

puts ans


Measured memory_bytes: 14300
#include<iostream>
using namespace std;
void ch(long long & n){
  if(!n)n = 0;
  else if(n%2)
	if(((n+1)/2)%2)n = 1;
	else n = 0;
  else if(n%4)n = n+1;
}
int main(){
  long long a,b;cin>>a>>b;
  a=a?a-1:0;
  ch(a);ch(b);
  cout<<(a^b)<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
map <int, int> Mx;
int main() {
	int N, i;
	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		int t;
		scanf("%d", &t);
		Mx[t]++;
		Mx[t - 1]++;
		Mx[t + 1]++;
	}
	int ans = 0;
	for (auto it : Mx) ans = max(ans, it.second);
	return !printf("%d\n", ans);
}

Measured memory_bytes: 4736
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define endl "\n"
#define se second
#define ll long long
#define inf 0x3f3f3f3f
#define fast    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int N = 5e5+10;
const ll mod = 998244353;
ll n;
pair<ll,ll>  arr[N];
ll a[N];ll cnt;ll mn=N;
int main()
{  fast
cin>>n;
for(int i=1;i<=n;i++){
cin>>arr[i].fi;arr[i].se=i;}
sort(arr+1,arr+n+1);
for(int i=n;i;i--){
	cnt++;
	mn=min(mn,arr[i].se);
	if(arr[i].fi!=arr[i-1].fi)
	a[mn]+=abs(arr[i].fi-arr[i-1].fi)*cnt;
}
for(int i=1;i<=n;i++)
cout<<a[i]<<"\n";
}

Measured memory_bytes: 6016
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define pb push_back
#define mp make_pair
#define rep(i,n) for(int i=0;i<(n);++i)

ll gcd(ll a,ll b){
	if(a%b==0) return b;
	else{
		a%=b;
		gcd(b,a);
	}
}

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;cin >> n;
	ll t=1,a=1;
	rep(i,n){
		ll T,A;cin >> T >> A;
		ll m=max((t+T-1)/T,(a+A-1)/A);
		t=T*m;
		a=A*m;
	}
	cout << a+t << endl;
}

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

int main() {
  int a = 1;
  int N,K;
  cin >> N >> K;
  
  for(int i=0;i<N;i++){
    if(a*2 >= a+K){
      a += K;
    }else{
      a *= 2;
    }
  }
  
  cout << a << endl;
    
}

Measured memory_bytes: 256
s = input()
for i in range(int(input())):
    lst = input().split()
    a,b = map(int, lst[1:3])
    if(lst[0] == "print"): print(s[a:b+1])
    elif(lst[0] == "reverse"): s = s[:a] + s[a:b+1][::-1] + s[b+1:]
    else: s = s[:a] + lst[-1] + s[b+1:]


Measured memory_bytes: 5612
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	int total=0;
	int tot=0;
	for (int i=0;i<a;i++)
	{
	
		int c;
		cin>>c;
		total+=c;
	    if (total<=b)
		 {
			tot+=1;
		}
	}
	cout<<tot+1<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll n;
  cin >> n;
  
  vector<ll> a(n);
  ll memo[200001] = {};
  for (int i = 0; i < n; i++){
    cin >> a[i];
    
    memo[a[i]]++;
  }

  ll sum = 0;
  for (int i = 1; i < n + 1; i++){
    sum += memo[i] * (memo[i] - 1)/2;
  }

  for (int i = 0; i < n; i++){
    cout << sum - memo[a[i]] + 1 << endl;
  }
  
  return 0;
}


Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define debug(x) cout<<#x<<": "<<x<<endl
typedef long long ll;
struct Point{double x,y;};
bool comp(Point a,Point b) {return (a.x==b.x ? a.y<b.y : a.x<b.x);}

int main(void){
	string s;
	int alpha[26]={};
	bool judge=false;
	cin>>s;
	rep(i,s.length()) alpha[s[i]-'a']++;
	rep(i,26) judge |= alpha[i] % 2;
	cout<< (judge ? "No" : "Yes") << endl;

	return 0;
}


Measured memory_bytes: 256
class Node:
    
    def __init__(self, i):
        self.end = i + 1
        self.days = {i}


N, M = list(map(int, input().split()))
BA = []
for i in range(N):
    a, b = list(map(int, input().split()))
    BA.append((b, a))

ans = 0
schedule = {}
BA.sort(reverse=True)
for b, a in BA:
    x = a
    if a in schedule:
        x = schedule[a].end
    if x > M:
        continue
    ans += b
    if x - 1 in schedule:
        w1 = schedule[x - 1]
        if x + 1 in schedule:
            w2 = schedule[x + 1]
            if len(w1.days) < len(w2.days):
                w1, w2 = w2, w1
            else:
                w1.end = w2.end
            w1.days |= w2.days
            for i in w2.days:
                schedule[i] = w1
            schedule[x] = w1
            w1.days.add(x)
        else:
            schedule[x] = w1
            w1.end += 1
            w1.days.add(x)
    elif x + 1 in schedule:
        w2 = schedule[x + 1]
        schedule[x] = w2
        w2.days.add(x)
    else:
        schedule[x] = Node(x)
print(ans)

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

long long N,K,ans=0;
vector<long long> a;
vector<long long> sum(1,0);
vector<long long> b;
long long bit[222222];

void add(long long a,long long w){
	for(long long x=a;x<=N+1;x+=x&-x)bit[x]+=w;
}

long long bit_sum(long long a) {
	long long ret=0;
	for(long long x=a;x>0;x-=x&-x)ret+=bit[x];
	return ret;
}

int main(){
	cin >> N >> K;
	for(int i=0;i<N;i++){
		long long tmp;
		cin >> tmp;
		a.push_back(tmp);
	}
	for(int i=0;i<N;i++){
		sum.push_back(sum[i]+a[i]);
	}
	for(int i=0;i<=N;i++){
		b.push_back(sum[i]-i*K);
	}
	vector<pair<long long,long long>> bb(N+1);
	for(int i=0;i<=N;i++){
		bb[i].first=b[i];
		bb[i].second=i+1;
	}
	sort(bb.begin(),bb.end());
	
	for(auto BB:bb){
		ans+=bit_sum(BB.second);
		add(BB.second,1LL);
	}
	
	cout << ans << endl;
	return 0;
}

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

int main(){
    int h, w;
    cin >> h >> w;
    int mat[h][w];
    char x;
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            cin >> x;
            mat[i][j] = x-'0';
        }
    }
    for(int i = 0; i < h; i++){
        for(int j = 0; j < w; j++){
            if(i && j)   mat[i][j] += min(mat[i-1][j], mat[i][j-1]);
            else if(i)  mat[i][j] += mat[i-1][j];
            else if(j)  mat[i][j] += mat[i][j-1];
        }
    }
    cout << mat[h-1][w-1] << endl;
    return 0;
}


Measured memory_bytes: 3112
#include<stdio.h>

int main(void){
  int A,B;
  scanf("%d%d",&A,&B);
  
  if(B>=0){
    if((A+B)>=A*B){
      printf("%d",A+B);
    }else{
      printf("%d",A*B);
    }
  }else{
    if((A-B)>=A*B){
      printf("%d",A-B);
    }else{
      printf("%d",A*B);
    }
  }
  
  return 0;
}

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

using namespace std;

long long poww(int t){
    long long res = t;
    for(int i = 0; i < 4; i++)
        res *= t;
    return res;
}

void Solve(){
    int n;
    cin>>n;
    long long a;
    int i = 0;
    while(true){
        a = poww(i);
        long long rest = a - n;
        if(rest <= 0){
            for(int j = 0; j >= -200; j--){
                long long k = poww(j);
                if(k == rest){
                    cout<<i<<" "<<j<<'\n';
                    return;
                }
            }
        }
        else{
            for(int j = 0; j <= 200; j++){
                long long k = poww(j);
                if(k == rest){
                    cout<<i<<" "<<j<<'\n';
                    return;
                }
            }
        }
        i++;
    }

}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int T = 1;
    //cin>>T;
    while(T--){
        Solve();
    }
}

Measured memory_bytes: 3608
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define repr(i, n) for(int i=(n-1); 1<=i; i--)
#define repr2(i, from, to) for(int i=(from-1); (int)(to)<=i; i--)
#define ALL(obj) (obj).begin(), (obj).end()
#define LLPair pair<ll, ll>
typedef long long ll;

using namespace std;

struct Point { int x, y; };
struct Edge { int to, cost; };
struct gNode { int from, to, cost; };
struct tNode { int value; int parent; vector<int> child; };


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

int gcd(int a, int b){ return a % b == 0 ? b : gcd(b, a%b); }
int lcm(int a, int b){ return a * b/ gcd(a, b); }
int extgcd(int a, int b, int& x, int& y){
	int d = a;
	if(b != 0){
		d = extgcd(b, a%b, y, x);
		y -= (a/b) * x;
	} else{
		x = 1; y = 0;
	}
	return d;
}
ll mod_pow(ll x, ll n){
	if(n == 0) return 1;
	ll res = mod_pow(x*x % MOD, n/2);
	if(n & 1) res = res * x % MOD;
	return res;
}

#define PT_SIZE 4010 //少し大きめにとること。
ll PascalsTriangle[PT_SIZE][PT_SIZE];
void initPascalsTriangle(){
	PascalsTriangle[0][0] = 1;
	rep(i, PT_SIZE-1){
		rep(j, i+1){
			PascalsTriangle[i+1][j] += PascalsTriangle[i][j];
			PascalsTriangle[i+1][j] %= MOD;
			PascalsTriangle[i+1][j+1] += PascalsTriangle[i][j];
			PascalsTriangle[i+1][j] %= MOD;
		}
	}
}

ll comb(int n, int k){
	return PascalsTriangle[n][k];
}


ll func2(int n, int k){
	return comb(n+k-1, k-1);
}

ll func(int n, int k){
	if(n < k) return 0;
	if(n == 0 && k == 0) return 1;
	if(k < 1) return 0;
	return func2(n-k, k);
}

int main(void){
	int n, k; cin >> n >> k;

	initPascalsTriangle();
	rep2(i, 1, k+1){
		ll b = func(k, i);
		ll r = 0;
		r += func(n-k, i-1); r %= MOD;
		r += func(n-k, i); r %= MOD;
		r += func(n-k, i); r %= MOD;
		r += func(n-k, i+1); r %= MOD;
		cout << (b*r) % MOD << endl;
	}
	return 0;
}

Measured memory_bytes: 124160
#include <bits/stdc++.h>
 #define rep(i,a,b) for (int i=a;i<b;i++)
 #define rep2(i,a,b) for (int i=a;i>=b;i--)
 #define mod 1000000007
 #define INF  1e9+5
 #define f first
 #define se second
 #define endl '\n'
 #define ll long long
 #define ii pair <int,int>
 #define pll pair <ll,ll>
 #define vi vector <int>
 #define vl vector <ll>
 #define vvi vector < vi >
 #define vii vector < ii >
 #define vvii vector < vii >
 #define vll vector < ll >
 #define mi map<int,int>
 #define mll map<ll,ll>
 #define mci map<char,int>
 #define msi map<string,int>
 #define vb  vector <bool>
 #define pb push_back
 #define mk make_pair
 #define sz(a) a.size()
 #define all(a) a.begin(),a.end()
 #define rall(a) a.rbegin(),a.rend()
 #define int long long int
 #define Anurag_Gupta ios_base::sync_with_stdio(false);
#define IIIT_ALLD    cin.tie(NULL);cout.tie(NULL);
using namespace std;
vi fact(1000007);
inline int mdpower(int a,int b)
{
    int res =1;
    while(b)
    {
        if(b&1) res = (res%mod*a%mod)%mod;
        b/=2;
        a = (a%mod*a%mod)%mod;
    }
    return res;
}
inline int power(int a,int b)
{
    int res =1;
    while(b)
    {
        if(b&1) res = (res*a);
        b/=2;
        a = a*a;
    }
    return res;
}

inline void factorial()
{
    fact[0]=1;
    for(int i=1;i<1000007;i++)
        fact[i] = (fact[i-1]%mod*i%mod)%mod;
}

inline int inverse(int a)
{
    return mdpower(a,mod-2);
}
int n,k;
int h[1000005];
int dp[1000005];
int solve(int idx)
{
	if(idx==n)
		return 0;
	if(idx>n)
		return INF;
	if(dp[idx]!=-1)
		return dp[idx];
	int m=INT_MAX;
	for(int i=1;i<=k;i++)
	{
		int sum=0;
		if((idx+i)<=n){
			sum=abs(h[idx]-h[idx+i])+solve(idx+i);
		m=min(m,sum);
	}
	}
	return dp[idx]=m;
}
 signed main()
 {
     Anurag_Gupta
     IIIT_ALLD
     
    

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


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

#define rep(i,n) for(int i = 0; i < (n); i++)
#define rrep(i,n) for(int i = (n)-1; i >= 0; i--)
#define rep1(i,n) for(int i = 1; i <= (n); i++)
#define rrep1(i,n) for(int i = (n); i > 0; i--)

#define ll long long
#define pi pair<int, int>
#define pll pair<ll, ll>

#define MOD 1000000007
#define INF 1000000000000000LL

using namespace std;

// DP[i][j]:i番目の数値まで見たときにi番目の数値がそれよりも左にある数値の中でj番目に小さい時のパターン数
ll dp[3001][3001];
ll dps[3001][3001];

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

  dp[0][0]=1;
  rep1(i, n){

    rep(j, i+1){
      dps[i-1][j] = dp[i-1][j];
      if(j)dps[i-1][j] += dps[i-1][j-1];
      dps[i-1][j] %= MOD;
    }

    rep(j, n){
      if(s[i-1]=='<'){
        dp[i][j] = dps[i-1][j-1];

        //for(int k=0; k<i; k++){
        //  if(k<j)dp[i][j] += dp[i-1][k];
        //}
      }else{
        dp[i][j] = dps[i-1][i-1];
        if(j)dp[i][j] -= dps[i-1][j-1];

        //for(int k=0; k<i; k++){
        //  if(k>=j)dp[i][j] += dp[i-1][k];
        //}
      }
      dp[i][j]%=MOD;
    }
  }

  ll result = 0;
  rep(j, n)result = (result+dp[n-1][j]+MOD)%MOD;
  cout<<result%MOD<<endl;

  return 0;

rep(i, n+1){
  rep(j, n+1)cout<<dp[i][j]<<' ';
  cout<<endl;
}

  return 0;
}

Measured memory_bytes: 120092
#include <assert.h>
#include <limits.h>
#include <cmath>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <complex>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cout << i << "\n"

// const ll MOD = 998244353;
const ll MOD = 1e9+7;

int main() {
  std::cin.tie(0);
  std::ios::sync_with_stdio(false);
  //問題文中の添え字が0-indexか1-indexか確認!

  ll H,W,h,w;
  std::cin>>H>>W;
  std::cin>>h>>w;
  std::cout<<(H-h)*(W-w);
  return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<algorithm>
#include<iostream>
#include<map>
using namespace std;
map<int,int>q;
int main(void)
{
     int i,j,k,n,m,s=0;
     scanf("%d",&n);
     for(i=0;i<n;i++)
     {
          scanf("%d",&k);
          if(q[k]==1)
               q[k]=0,s--;
          else
               q[k]=1,s++;
     }
     printf("%d\n",s);
     return 0;
}


Measured memory_bytes: 4864
#include<stdio.h>

int main(){
  int x,y,z;
  scanf("%d%d",&x,&y);
	while(1){
		z=x%y;
		if(z==0){
			printf("%d\n",y);
			break;
		}
			x=y;
			y=z;
	}
  return 0;
}



Measured memory_bytes: 2124
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<functional>
#include<cassert>

#define MAX 64
#define WMAX 1024
#define CAP_MAX 128

using namespace std;

int water[MAX];
int beaker[MAX];
bool vis[MAX];

bool dfs( int n, int num );
bool pour( int n, int w, int from, int now, int num );

bool pour( int n, int w, int from, int now, int num )
{
  if( w == 0 ){
    if( dfs( n, num ) ) return true;
    return false;
  }
  if( w < 0 || from >= n || now >= n ) return false;

  for(int i = from+1; i < n; ++i){
    if( beaker[i] == water[i] ) break;
    if( !vis[i] && beaker[i] > w ) return false;
  }
  
  int pre = -1;
  for(int i = now; i < n; ++i){
    if( !vis[i] && beaker[i] <= w ){
      if( pre == beaker[i] ) continue;

      water[i] += beaker[i];
      vis[i] = true;
      if( pour( n, w-beaker[i], from, i+1, num+1 ) ) return true;
      vis[i] = false;
      water[i] -= beaker[i];

      pre = beaker[i];
    }
  }
  return false;
}

bool dfs( int n, int num )
{
  if( num == n ){
    return true;
  }

  for(int i = 0; i < n; ++i){
    if( vis[i] && beaker[i] == water[i] ){
      water[i]=0;
      if( pour( n, beaker[i], i, i+1, num ) ) return true;
      water[i]=beaker[i];
    }
  }
  return false;
}

int main()
{
  while(true){
    int n;
    string res = "NO";

    cin >> n;
    if( n == 0 ) break;

    for(int i = 0; i < MAX; ++i){
      beaker[i] = 0;
      vis[i] = false;
      water[i] = 0;
    }

    for(int i = 0; i < n; ++i){
      cin >> beaker[i];
    }
    
    sort(beaker,beaker+n,greater<int>());
    water[0]=beaker[0];
    vis[0]=true;

    if( dfs( n, 1 ) ){
      res = "YES";
    }

    puts(res.c_str());
  }
  return 0;
}

Measured memory_bytes: 904
class Dice:
    def __init__(self,labels):
       self.stat =  labels
    
    def roll_E(self):
        self.stat[0],self.stat[2],self.stat[3],self.stat[5] = self.stat[3],self.stat[0],self.stat[5],self.stat[2]
        
    def roll_N(self):
        self.stat[0],self.stat[1],self.stat[5],self.stat[4] = self.stat[1],self.stat[5],self.stat[4],self.stat[0]
        
    def roll_S(self):
        self.stat[0],self.stat[1],self.stat[5],self.stat[4] = self.stat[4],self.stat[0],self.stat[1],self.stat[5]
        
    def roll_W(self):
        self.stat[0],self.stat[2],self.stat[5],self.stat[3] = self.stat[2],self.stat[5],self.stat[3],self.stat[0]
        
    def get_top(self):
        return self.stat[0]
        
    def get(self):
        return list(self.stat)
        
dice1 = Dice(input().split())
dice2 = Dice(input().split())

#print(dice1.get())
#print(dice2.get())
flag = False

for i in range(20):
    dice2.roll_N()
    #print(dice2.get())
    if dice1.get() == dice2.get() :
        flag = True
        break
    for j in range(20):
        dice2.roll_E()
        #print(dice2.get())
        if dice1.get() == dice2.get() :
            flag = True
            break
        for k in range(20):
            dice2.roll_S()
            #print(dice2.get())
            if dice1.get() == dice2.get() :
                flag = True
                break
if flag:print("Yes")
else:print("No")



Measured memory_bytes: 5572
//
// Created on 2019-02-09.
//
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }

#define REP(i,n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" \
                      << " " << __FILE__ << endl;

#define PB push_back
#define INF 1e9
#define MOD 1e9+7
#define EPS 1e-9

typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

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


    string b;
    cin >> b;

    if (b == "A") cout << "T" << endl;
    if (b == "T") cout << "A" << endl;
    if (b == "C") cout << "G" << endl;
    if (b == "G") cout << "C" << endl;

    return 0;

}

Measured memory_bytes: 256
program main
  implicit none
  integer :: h, n, i, j
  integer, allocatable :: m(:), a(:), b(:)
  read (*, *) h, n
  allocate (m(0:h), a(n), b(n))
  do i = 1, n
    read *, a(i), b(i)
  end do

  ! m(d) は d ダメージ与えるために必要な最小 MP
  m(:) = 10 ** 9
  m(0) = 0

  ! もらう DP
  do j = 1, h
    do i = 1, n
      m(j) = min(m(j), b(i) + m(max(0, j - a(i))))
    end do
  end do

  print "(i0)", m(h)
end program main


Measured memory_bytes: 256
h, w, m = map(int, input().split())

h_bomb = [0 for i in range(h)]
w_bomb = [0 for i in range(w)]
bomb_list = []

for i in range(m):
    hb, wb = map(int, input().split())
    h_bomb[hb-1] += 1
    w_bomb[wb-1] += 1
    bomb_list.append(tuple([hb, wb]))

h_bomb_max = max(h_bomb)
w_bomb_max = max(w_bomb)
h_bomb_line = []
w_bomb_line = []

for i in range(h):
    if h_bomb[i] == h_bomb_max:
        h_bomb_line.append(i)

for i in range(w):
    if w_bomb[i] == w_bomb_max:
        w_bomb_line.append(i)

bomb_set = set(bomb_list)

for i in h_bomb_line:
    for j in w_bomb_line:
        if (i+1, j+1) not in bomb_set:
            print(h_bomb_max+w_bomb_max)
            exit()

print(h_bomb_max + w_bomb_max -1)

Measured memory_bytes: 169064
#include <cstdio>
#include <cstring>
#define M 5070721
#define NIL (-1)
#define L 14
typedef long long ll;
char H[M][L];

int getChar(char ch){
	if(ch=='A')return 1;
	else if(ch=='C')return 2;
	else if(ch=='G')return 3;
	else if(ch=='T')return 4;
	else return 0;
}

ll getKey(char str[]){
	ll sum=0,p=1,i;
	int len=strlen(str);
	for(i=0;i<len;i++){
		sum+=p*(getChar(str[i]));
		p*=5;
	}
	return sum;
}

int h1(int key){
	return key%M;
}

int h2(int key){
	return 1+(key%(M-1));
}

int find(char str[]){
	ll key,i,h;
	key=getKey(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0)return 0;
	}
	return 0;
}

int insert(char str[]){
	ll key,i,h;
	key=getKey(str);
	for(i=0;;i++){
		h=(h1(key)+i*h2(key))%M;
		if(strcmp(H[h],str)==0)return 1;
		else if(strlen(H[h])==0){
			strcpy(H[h],str);
			return 0;
		}
	}
	return 0;
}


int main(void){
	int n;
	char str[L],com[9];
	for(int i=0;i<M;i++){
		H[i][0]='\0';
	}
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		scanf("%s %s",com,str);
		if(com[0]=='i'){
			insert(str);
		}else{
			if(find(str)){
				printf("yes\n");
			}else{
				printf("no\n");
			}
		}
	}
	return 0;
}


Measured memory_bytes: 72084
#include <stdio.h>

int main(void) {
	double r;
	double menseki,ensyu;
	
	scanf("%lf",&r);
	
	menseki = r * r * 3.141592653589;
	ensyu = (r + r) *3.141592653589;
	
	printf("%f %f\n",menseki,ensyu);
	
	
	

	return 0;
}

Measured memory_bytes: 648
/*input
6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10
*/
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef tree<long long, null_type, less<long long>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
#pragma GCC optimize("unroll-loops,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
typedef long long int ll;
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define sz(_a) (ll)(_a.size())
#define FILL(n) memset(n,0,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
const ll maxn=200005;
const ll maxlg=__lg(maxn)+2;
const ll INF64=8000000000000000000LL;
const int INF=0x3f3f3f3f;
 ll MOD=ll(1e9+7);
const ld PI=acos(-1);
const ld eps=1e-9;

ll mypow(ll a,ll b){
    if(b<=0) return 1;
    ll res=1LL;
    while(b){
        if(b&1) res=res*a%MOD;
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
int arr[maxn],ans[maxn];
vector<int> v[maxn];
void dfs(int u,int p,int sum){
    sum+=arr[u];
    ans[u]=sum;
    for(auto x:v[u]){
        if(x!=p){
            dfs(x,u,sum);
        }
    }
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
    int n,q;
    cin>>n>>q;
    REP(i,n-1){
        int a,b;
        cin>>a>>b;
        --a;
        --b;
        v[a].pb(b);
        v[b].pb(a);
    }
    REP(i,q){
        int a,b;
        cin>>a>>b;
        --a;

        arr[a]+=b;
    }
    dfs(0,-1,0);
    REP(i,n) cout<<ans[i]<<' ';
}

Measured memory_bytes: 27264
#include<iostream>
#include<vector>
#include<iomanip>
#include<cstdio>
using namespace std;

long double expected_value(int n) {
	return (2 + (n - 1)) / 2.0;
}

long double d_max(long double a, long double b) {
	return a > b ? a : b;
}

int main() {
	int n, k; cin >> n >> k;
	vector<int>p(n);
	vector<long double>e(n), sums(n);
	long double ans = 0;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		e[i] = expected_value(p[i]);
	}
	sums[0] = e[0];
	for (int i = 1; i < n; i++) {
		sums[i] = e[i] + sums[i - 1];
	}
	ans = sums[k - 1];
	for (int i = 0; i < n - k; i++) {
		long double t = sums[i + k] - sums[i];
		ans = d_max(ans, t);
	}
	printf("%.10Lf\n", ans);
}

Measured memory_bytes: 7296
#include "bits/stdc++.h"
using namespace std;
#define PB push_back
#define MP make_pair
#define REP(i,n) for(int i=0;i<(n);i++)

int N;
int L[256],R[256],O[256];
int S,A,C;
double mi;
int main(){
    while(cin>>N,N){
        REP(i,N)cin>>L[i];
        mi=1e9;
        REP(s,16)REP(a,16)REP(c,16){
            memset(O,0,sizeof(O));
            int t=s;
            double H=0;
            REP(i,N){
                t=(t*a+c)%256;
                R[i]=t;
                O[(L[i]+R[i])%256]++;
            }
            REP(i,256)if(O[i]){
                H-=O[i]*1.0/N*log(O[i]*1.0/N);
            }
            if(mi>1e-9+H){
                S=s;A=a;C=c;
                mi=H;
            }
        }
        cout<<S<<" "<<A<<" "<<C<<endl;
    }
}

Measured memory_bytes: 3336
#![allow(unused_imports, unused_macros, dead_code)]

macro_rules! min {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| min!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = min!($($ys),*);
        if $x < t { $x } else { t }
    }}
}
macro_rules! max {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        it.next().map(|z| it.fold(z, |x, y| max!(x, y)))
    }};
    ($x:expr) => ($x);
    ($x:expr, $($ys:expr),*) => {{
        let t = max!($($ys),*);
        if $x > t { $x } else { t }
    }}
}


macro_rules! ewriteln {
    ($($args:expr),*) => { let _ = writeln!(&mut std::io::stderr(), $($args),*); };
}
macro_rules! trace {
    ($x:expr) => { ewriteln!(">>> {} = {:?}", stringify!($x), $x) };
    ($($xs:expr),*) => { trace!(($($xs),*)) }
}
macro_rules! put {
    (.. $x:expr) => {{
        let mut it = $x.iter();
        if let Some(x) = it.next() { print!("{}", x); }
        for x in it { print!(" {}", x); }
        println!("");
    }};
    ($x:expr) => { println!("{}", $x) };
    ($x:expr, $($xs:expr),*) => { print!("{} ", $x); put!($($xs),*) }
}

const M: i64 = 1_000_000_007;

fn main() {
    let mut sc = Scanner::new();
    let n: usize = sc.cin();
    let k: usize = sc.cin();
    let s: usize = sc.cin();
    if s < 1000000000 {
        let mut ans = vec![0; n];
        for i in 0..k {
            ans[i] = s;
        }
        for i in k..n {
            ans[i] = s + 1;
        }
        put!(..ans);
    } else {
        let mut ans = vec![0; n];
        for i in 0..k {
            ans[i] = s;
        }
        for i in k..n {
            ans[i] = 1;
        }
        put!(..ans);
    }
}

use std::io::{self, Write};
use std::str::FromStr;
use std::collections::VecDeque;

struct Scanner { stdin: io::Stdin, buffer: VecDeque<String>, }
impl Scanner {
    fn new() -> Self { Scanner { stdin: io::stdin(), buffer: VecDeque::new() } }
    fn cin<T: FromStr>(&mut self) -> T {
        while self.buffer.len() == 0 {
            let mut line = String::new();
            let _ = self.stdin.read_line(&mut line);
            for w in line.split_whitespace() {
                self.buffer.push_back(String::from(w));
            }
        }
        self.buffer.pop_front().unwrap().parse::<T>().ok().unwrap()
    }
    fn chars(&mut self) -> Vec<char> { self.cin::<String>().chars().collect() }
    fn vec<T: FromStr>(&mut self, n: usize) -> Vec<T> { (0..n).map(|_| self.cin()).collect() }
}


Measured memory_bytes: 5372
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
#include<algorithm>//next_permutation
#define rep(i,n) for (int i = 0;i < (n);i++)
#define all(v) v.begin(),v.end()
#define dec(n) cout << fixed << setprecision(n);
#define large "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
#define small "abcdefghijklmnopqrstuvwxyz"
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
using vl = vector<ll>;
using vvl = vector<vl>;

ll gcd(ll a,ll b){
  if(b == 0) return a;
  return gcd(b , a % b);
}

const ll MOD = 1000000007;
const ll MAX = 2000001;

ll mod(ll a){
  return a % MOD;
}

ll lcm(ll a,ll b){
  return (a*b)/gcd(a,b);
}


int main(){
  ll n; cin >> n;
  
  vl max4(4); max4[1] = 1e9; max4[3] = 1e9; max4[2] = -1e9;
  vvl table(4,vl(2));
  
  rep(i,n){
    ll x,y; cin >> x >> y;
    
    if(x+y > max4[0]){
      max4[0] = x+y;
      table[0][0] = x; table[0][1] = y;
    }
    if(x+y < max4[1]){
      max4[1] = x+y;
      table[1][0] = x; table[1][1] = y;
    }
    if(y-x > max4[2]){
      max4[2] = y-x;
      table[2][0] = x; table[2][1] = y;
    }
    if(y-x < max4[3]){
      max4[3] = y-x;
      table[3][0] = x; table[3][1] = y;
    }
    
  }

  
  cout << max(max4[0]-max4[1],abs(table[2][0]-table[3][0])+
              abs(table[2][1]-table[3][1])) << endl;
  
}

Measured memory_bytes: 3648
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
using namespace std;

using ll = long long;
using P = pair<int, ll>;

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

    vector<P> ab(N);
    for (int i = 0; i < N; i++) {
        cin >> ab[i].first >> ab[i].second;
    }
    sort(ab.begin(), ab.end());

    ll idx = 0;
    for (int i = 0; i < N; i++) {
        idx += ab[i].second;
        if (K <= idx) {
            cout << ab[i].first << endl;
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using vi=vector<int>;
using vvi=vector<vi>;
using vs=vector<string>;
using msi=map<string,int>;
using mii=map<int,int>;
//using pii=pair<int,int>;
using vlai=valarray<int>;
using ll=long long;
using pii=pair<ll,ll>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1e9
#define EPS 1e-9
#define MOD (1e9+7)
void get(){}template<class H,class...T>void get(H&h,T&...t){cin>>h;get(t...);}
#define dcl(...) int __VA_ARGS__;get(__VA_ARGS__);

string hor(int x){return x>0?"R"s:"L"s;}
string ver(int y){return y>0?"U"s:"D"s;}

int main(){
    dcl(x0,y0,x,y);
    x-=x0,y-=y0;
    rep(i,abs(y))cout<<ver(y);
    rep(i,abs(x))cout<<hor(x);
    rep(i,abs(y))cout<<ver(-y);
    rep(i,abs(x)+1)cout<<hor(-x);
    rep(i,abs(y)+1)cout<<ver(y);
    rep(i,abs(x)+1)cout<<hor(x);
    cout<<ver(-y)<<hor(x);
    rep(i,abs(y)+1)cout<<ver(-y);
    rep(i,abs(x)+1)cout<<hor(-x);
    cout<<ver(y);
    cout<<endl;
    
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
class Program
    {
        static void Main(string[] args)
    	{
            string s = Console.ReadLine();
            if (s[0] == s[1] || s[1] == s[2] || s[2] == s[3]) Console.WriteLine("Bad");
            else Console.WriteLine("Good");
            
            
        }
    
    }
    //mcs Main.cs
    //mono Main.exe

Measured memory_bytes: 13140
#include<bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < (n); i++)

int main() {
    string s;
    cin >> s;
    string t;
    cin >> t;
    int a = s.size();
    rep(i, a) {
        char tmp = s[a-1];
      	for(int j = a-2; j >= 0; j--) {
        	s[j+1] = s[j];
        }
      	s[0] = tmp;
        
        if(s==t) {
            cout << "Yes" << endl;
            return 0;
        }
    }

    cout << "No" << endl;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

struct process{
  char name[10];
  int time;
};
  

int main() {
  int N, q;
  int spend_time;
  int time_i;
  int q_index = 0;
  int new_index;
  char name[10];
  struct process queue[100000];

  cin >> N >> q;

  for (int i = 0; i < N; i ++) {
    cin >> queue[q_index].name >> time_i;
    if (time_i <= q) {
      spend_time += time_i;
      cout << queue[q_index].name << " " << spend_time << endl;
    } else {
      queue[q_index].time = time_i - q;
      q_index ++;
      spend_time += q;
    }
  }

  while (q_index != 0) {
    new_index = 0;
    for (int i = 0; i < q_index; i ++) {
      if (queue[i].time <= q) {
        spend_time += queue[i].time;
        cout << queue[i].name << " " << spend_time << endl;
      } else {
        queue[new_index].time = queue[i].time - q;
        for (int j = 0; j < 10; j ++)
          queue[new_index].name[j] = queue[i].name[j];
        new_index ++;
        spend_time += q;
      }
    }
    q_index = new_index;
  }
  return 0;
}



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

using namespace std;

namespace mylib {
template<int mod>
struct ModInt {
	using ll = long long;
	int x;
	const static int M = mod;
	ModInt(ll x_) {
		x = x_ % mod;
		if (x < 0) x += mod;
	}
	ModInt() : ModInt(0) {}
	inline ModInt& operator+=(const ModInt rhs) {
		x += rhs.x;
		x %= mod;
		return (*this);
	}
	inline ModInt& operator-=(const ModInt rhs) {
		x += -rhs;
		return *this;
	}
	inline ModInt& operator*=(const ModInt rhs) {
		x = ((ll) x * rhs.x) % mod;
		return *this;
	}
	inline ModInt& operator/=(ModInt rhs) {
		return *this *= rhs.power(mod - 2);
	}
	inline ModInt power(ll p) {
		if (p == 0) return 1;
		if (p % 2 == 1) return (*this) * power(p - 1);
		ModInt t = power(p / 2);
		return t * t;
	}
	inline ModInt& operator=(const ModInt& rhs) {
		this->x = rhs.x;
		return *this;
	}
	inline int operator==(const ModInt& rhs) const {
		return this->x == rhs.x;
	}
	inline int operator!=(const ModInt& rhs) const {
		return !(*this != rhs);
	}
	inline ModInt operator++(signed unused) {
		ModInt res(*this);
		++(*this);
		return res;
	}
	inline ModInt& operator++() {
		(*this) += 1;
		return (*this);
	}
	inline ModInt operator--(signed unused) {
		ModInt res(*this);
		--(*this);
		return res;
	}
	inline ModInt& operator--() {
		(*this) -= 1;
		return (*this);
	}
	inline ModInt operator+() const {
		return (*this);
	}
	inline ModInt operator-() const {
		return (*this).x ? ModInt(mod - (*this).x) : ModInt(0);
	}
	friend const ModInt operator+(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) += rhs;}
	friend const ModInt operator-(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) -= rhs;}
	friend const ModInt operator*(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) *= rhs;}
	friend const ModInt operator/(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) /= rhs;}
	operator int() const { return x;}
	friend ostream& operator<<(ostream& lhs, const ModInt& rhs) {
		lhs << rhs.x;
		return lhs;
	}
	friend istream& operator>>(istream& lhs, ModInt& rhs) {
		long long t;
		lhs >> t;
		rhs = ModInt(t);
		return lhs;
	}
};
using modint = ModInt<1000000007>;
//using modint = ModInt<998244353>;
modint operator"" _mi(unsigned long long lit) {
	return modint(lit % modint::M);
}
}; // mylib
using namespace mylib;

modint solve() {
	int N;
	cin >> N;
	vector<int> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	sort(A.begin(), A.end());
	if (N % 2) {
		for (int i = 0; i < N; i++) {
			if (A[i] != (i + 1) / 2 * 2) return 0;
		}
	} else {
		for (int i = 0; i < N; i++) {
			if (A[i] != i / 2 * 2 + 1) return 0;
		}
	}
	modint res = 1;
	for (int i = 0; i < N / 2; i++) {
		res *= 2;
	}
	return res;
}

int main() {
	cout << solve() << endl;
}



Measured memory_bytes: 640
#include <stdio.h>

int a[2000010];
int l,r;

int main(){
	int n;
	scanf("%d",&n);
	while(n--){
		char s[99];
		scanf("%s",s);
		if(s[0]=='i')scanf("%d",a+r++);
		else if(s[6]==0){
			int t;
			scanf("%d",&t);
			for(int idx=r-1;idx>=l;idx--)if(a[idx]==t){
				a[idx]=-1;
				break;
			}
		}else if(s[6]=='F')while(a[--r]==-1);
		else while(a[l++]==-1);	
	}
	int f=0;
	for(int i=r-1;i>=l;i--)if(a[i]!=-1)printf(f++?" %d":"%d",a[i]);
	puts("");
}


Measured memory_bytes: 5608
// STACK.cpp
#include <iostream>
#include <stack>
#include <string>
using namespace std;
stack <int> stk;
string a;
string b="";
int c;
int t1;
int t2;
int main()
{
	getline(cin,a);
	for(int j=0;j<a.size();j++){
		if(a[j] == ' '){
			if(b == ""){continue;}
			c = stoi(b);
			stk.push(c);
			b = "";
			continue;
		}
		if(a[j] == '+'){
			t1 = stk.top();
			stk.pop();
			t2 = stk.top();
			stk.pop();
			stk.push(t2+t1);
			continue;
		}
		if(a[j] == '-'){
			t1 = stk.top();
			stk.pop();
			t2 = stk.top();
			stk.pop();
			stk.push(t2-t1);
			continue;
		}
		if(a[j] == '*'){
			t1 = stk.top();
			stk.pop();
			t2 = stk.top();
			stk.pop();
			stk.push(t2*t1);
			continue;
		}
		b += a[j];
	}
	cout << stk.top() << endl;
	cin.get();
	return 0;
}

Measured memory_bytes: 3140
//fold
#ifndef KHALIL
#include <bits/stdc++.h>
#else
#include "header.h"
#endif
#define endl '\n'
#define mp make_pair
#define tostr(x) static_cast<ostringstream&>((ostringstream()<<dec<<x)).str()
#define rep(i,begin,end) for(auto i = begin;i < end;i++)
#define repr(i,begin,end) for(auto i = begin-1;i >= end;i--)
#define pb push_back
#define sz(a) ((int)(a).size())
#define fi first
#define se second
#define abs(a) ((a) < (0) ? (-1)*(a) : (a))
#define SQ(a) ((a)*(a))
#define eqd(a,b) (abs(a-b)<1e-9)
#define X real()
#define Y imag()
using namespace std;
typedef long long ll;
typedef long double ld;
template <typename t> t in(t q){cin >> q;return q;}
template <typename T> ostream& operator<<(ostream& os, const vector<T>& v){os << "[";for (int i = 0; i < sz(v); ++i) { os << v[i]; if (i != sz(v) - 1) os << ",";}os << "]";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const map<T, S>& v){for (auto it : v)os << "(" << it.first << ":" << it.second << ")";return os;}
template <typename T, typename S>ostream& operator<<(ostream& os, const pair<T, S>& v){os << "(" << v.first << "," << v.second << ")";return os;}
const long double PI = acosl(-1);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng64(chrono::steady_clock::now().time_since_epoch().count());
inline int rand(int l,int r){return uniform_int_distribution<int>(l, r)(rng);}
inline ll rand(ll l,ll r){return uniform_int_distribution<ll>(l, r)(rng64);}
//endfold
#define  N  (200'005)
#define MOD (1'000'000'007ll)
#define OO (1'050'000'000)
#define OOL (1'100'000'000'000'000'000ll)



//global
vector<ll> base;

vector<ll> mul(vector<ll> a,vector<ll> b){
	vector<ll> res(sz(a));
	rep(i,0,sz(a)){
		res[i] = b[a[i]-1];
	}
	return res;
}

vector<ll> binpow(ll b) {
	vector<ll> res = base;
	while (b > 0) {
		if (b & 1)
			res = mul(res,base);
		base = mul(base,base);
		b >>= 1;
	}
	return res;
}
ll a[N];
ll d[N];
ll op[N];

int main(){
	//fold
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cout << setprecision(10);
	//endfold
	ll n;
	cin >> n;
	rep(i,1,n+1){
		cin >> a[i];
	}
	vector<ll> num;
	rep(i,2,n+1){
		d[i] = a[i]-a[i-1];
		num.push_back(d[i]);
	}
	ll m,k;
	cin >> m >> k;
	rep(i,1,n){
		base.push_back(i);
	}
	rep(i,0,m){
		cin >> op[i];
		op[i] -= 2;
		swap(base[op[i]],base[op[i]+1]);
	}
	base = binpow(k-1);
	num = mul(base,num);
	ll cur = a[1];
	rep(i,0,n){
		cout << cur << endl;
		if(i != n-1) cur += num[i];
	}
	return 0;
}

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

int main() {
	int table[101][10001];
	int N, W;
	cin >> N >> W;

	int v[1000];
	int w[1000];
	for (int i = 1; i <= N; i++)
	{
		cin >> v[i] >> w[i];
	}

	int res = -1;
	for (int i = 0; i < W; i++) 
		table[0][i] = 0;
	for (int i = 0; i < N; i++) 
		table[i][0] = 0;
	//cout << "v" << endl;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= W; j++) {
			if (0 <= j - w[i]) {
				table[i][j] = max(table[i - 1][j], table[i - 1][j - w[i]] + v[i]);
			}
			else table[i][j] = table[i - 1][j];
			res = max(res, table[i][j]);
		}
	}
	cout << res << endl;
	return 0;

}

Measured memory_bytes: 7016
import collections
import sys
import numpy as np
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
MOD = 10**9+7
import itertools
import math

n,a,b = map(int,input().split())
cnt = 0
ans = 0
for i in range(1,n+1):
    c = str(i)
    c_sum = 0
    for j in range(len(c)):
        c_sum += int(c[j])
    if c_sum>= a and c_sum<=b:
        ans += i
print(ans)

Measured memory_bytes: 19748
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define rrep(i,n) for(int i=(n);i>=0;--i)
#define ssort(n) sort((n).begin(),(n).end())
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define INF 10101010

int main()
{
    int a;
    cin >> a;
    cout << a+a*a+a*a*a << endl;
}

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

int main(){
    int a, b, k;
    cin >> a >> b >> k;

    if(b-a+1 < 2*k){
        for(int i=0; i<b-a+1; i++){
            cout << a+i << endl;
        }
    }else{
        for(int i=0; i<k; i++){
            cout << a+i << endl;
        }
        for(int i=0; i<k; i++){
            cout << b-k+1+i << endl;
        }
    }
  
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) for(ll i = 0; i < (ll)(n); ++i)

vector<pair<ll, ll>> prime_factor(int64_t n) {
  vector<pair<ll, ll>> ret;
  for(int64_t i = 2; i * i <= n; i++) {
    if (n % i == 0) ret.push_back(pair<ll,ll>(i, 0));
    while(n % i == 0) {
        ret.back().second++;
        n /= i;
    }
  }
  if(n != 1) ret.push_back(pair<ll,ll>(n, 1));
  return ret;
}

int main() {
    ll n, m; cin >> n >> m;
    auto primes = prime_factor(m);
    vector<vector<ll>> dp(primes.size() + 1, vector<ll>(n + 1, -1));
    dp[0][1] = 1;
    REP(i, primes.size()) {
        REP(j, n) if (dp[i][j] != -1) dp[i+1][j] = 0;
        dp[i+1][n] = dp[i][n];

        REP(j, n) if (dp[i][j] != -1) {
            if (j * primes[i].first >= n) {
                if (dp[i + 1][n] == -1) {
                    dp[i + 1][n] = j * primes[i].first;
                } else {
                    dp[i + 1][n] = min(dp[i + 1][n], j * primes[i].first);
                }
            } else if (dp[i + 1][j * primes[i].first] != 0) {
                dp[i + 1][j * primes[i].first] = 1;
            }
        }
        REP(j, n) if (dp[i + 1][j] != -1) {
            if (dp[i + 1][j] >= primes[i].second) continue;
            if (j * primes[i].first >= n) {
                if (dp[i + 1][n] == -1) {
                    dp[i + 1][n] = j * primes[i].first;
                } else {
                    dp[i + 1][n] = min(dp[i + 1][n], j * primes[i].first);
                }
            } else if (dp[i + 1][j] + 1 < dp[i + 1][j * primes[i].first]){
                dp[i + 1][j * primes[i].first] = dp[i + 1][j] + 1;
            } else if (dp[i + 1][j * primes[i].first] == -1){
                dp[i + 1][j * primes[i].first] = dp[i + 1][j] + 1;
            }
        }
    }
    cout << m / dp[primes.size()][n] << endl;
}

Measured memory_bytes: 8832
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
#define all(obj) (obj).begin(), (obj).end()
typedef long long int ll;
typedef long double ld;
using namespace std;


int main(int argc, char const *argv[]) {
  ll t, n;std::cin >> n;
  deque<ll> q;
  re(i, n){
    std::cin >> t;
    if(i%2!=n%2) q.push_front(t);
    else q.push_back(t);
  }
  while(!q.empty()){
    std::cout << q.front() << (q.size()==1?"\n":" ");
    q.pop_front();
  }
  return 0;
}


Measured memory_bytes: 3712
#include <iostream>
 
int main(){
    unsigned long long h, w;
    std::cin >> h >> w;
    if(h == 1 || w == 1) {
      std::cout << 1 << std::endl;
      return 0;
    }
    std::cout << ((h+1)/2)*((w+1)/2)+(h/2)*(w/2) << std::endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<utility>
#include<iostream>
using namespace std;
int main(){
    long long int ans=1,a=0,h,i;
    scanf("%lld\n",&h);
    while(h/2>0){
        a++;
        h=h/2;
    }
    a++;
    for(i=0;i<a;i++){
        ans=ans*2;
    }
    printf("%lld\n",ans-1);
    return 0;
}

Measured memory_bytes: 256