akhauriyash/Code-Regression huggingface dataset:
{-# LANGUAGE BangPatterns #-}
import qualified Data.ByteString.Char8 as BS
import Data.Array.Unboxed
import Data.Array.ST
import Control.Monad

-- Input: s t
-- Output: arr
--   (arr ! i) ! j == length of lcs of (drop i s, drop j t)
lcsTable :: BS.ByteString -> BS.ByteString -> UArray (Int, Int) Int
lcsTable xs ys = runSTUArray $ do
  arr <- newArray ((0,0), (n,m)) 0
  forM_ [0..n-1] $ \i -> do
    forM_ [0..m-1] $ \j -> do
      let x = xs `BS.index` i
          y = ys `BS.index` j
      if x == y then do
        a <- readArray arr (i, j)
        writeArray arr (i+1, j+1) $! a+1
      else do
        a <- readArray arr (i+1, j)
        b <- readArray arr (i, j+1)
        writeArray arr (i+1, j+1) $! max a b
  return arr
  where n = BS.length xs
        m = BS.length ys

solve :: BS.ByteString -> BS.ByteString -> String
solve !s !t = let !table = lcsTable s t
                  !n = BS.length s
                  !m = BS.length t
                  recon !i !j acc | i == 0 || j == 0 = acc
                                  | x == y = recon (i-1) (j-1) (x : acc)
                                  | table!(i-1,j) >= table!(i,j-1) = recon (i-1) j acc
                                  | otherwise = recon i (j-1) acc
                    where x = BS.index s (i-1)
                          y = BS.index t (j-1)
              in recon n m []

main = do
  s <- BS.getLine
  t <- BS.getLine
  -- BS.length s <= 3000, BS.length t <= 3000, BS.all isAsciiLower s, BS.all isAsciiLower t
  putStrLn (solve s t)


Measured memory_bytes: 71676
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <climits>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>

#define REP(i,n) for(auto i=0;i<n;++i)
#define REPR(i,n) for(auto i=n;i>=0;--i)
#define REPI(itr,v) for(auto itr=v.begin();itr!=v.end();++itr)
#define REPIR(itr,v) for(auto itr=v.rbegin();itr!=v.rend();++itr)
#define FOR(i,a,b) for(auto i=a;i<b;++i)
#define SORT(v,n) sort(v, v+n)
#define SORTV(v) sort(v.begin(), v.end())
#define ALL(v) v.begin(),v.end()
#define llong long long
#define ll long long
#define INF 999999999
#define MOD 1000000007
#define pb push_back
#define pf push_front
#define MP make_pair
#define SV(n,v) {int tmp;for(int i=0;i<n;++i){scanf("%d",&tmp);v.push_back(tmp);}}

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

using namespace std;

typedef pair<int,int> pii;

int main(){

  int h, w;
  string s[50];

  cin >> h >> w;
  REP(i,h){
    cin >> s[i];
  }

  REP(i,h){
    REP(j,w){
      if(s[i][j] == '#'){
        bool f = false;
        REP(k,4){
          int x = j + dx[k], y = i + dy[k];
          if(x >= 0 && x < w && y >= 0 && y < h){
            if(s[y][x] == '#'){
              f = true;
              break;
            }
          }
        }
        if(!f){
          cout << "No\n";
          return 0;
        }
      }
    }
  }

  cout << "Yes\n";
  return 0;
}



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

using namespace std;

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

int dp[1000001][2] = {};

int main(){
    string n;
    cin >> n;
    reverse(begin(n), end(n));
    n += "0";
    int m = n.size();
    int ans = 0;
    for(int i = 0; i <= m; i++){
        for(int j = 0; j < 2; j++){
            dp[i][j] = INF;
        }
    }
    dp[0][0] = 0;
    for(int i = 0; i < m; i++){
        int t = n[i] - '0';
        dp[i + 1][0] = min(dp[i][0] + t, dp[i][1] + t + 1);
        dp[i + 1][1] = min(dp[i][0] + (10 - t), dp[i][1] + (10 - (t + 1)));
    }
    cout << dp[m][0] << endl;
    return 0;
}


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

using namespace std;

#define int long long

const int big = 1e18;

void solve() {
    int n, v, u;
    cin >> n >> v >> u;
    --v;
    --u;
    vector <vector <int> > g(n);
    for (int i = 0; i < n - 1; ++i) {
        int tv, tu;
        cin >> tv >> tu;
        --tv;
        --tu;
        g[tv].push_back(tu);
        g[tu].push_back(tv);
    }
    vector <int> dist1(n, big), dist2(n, big);
    queue <int> q;
    q.push(v);
    dist1[v] = 0;
    while (!q.empty()) {
        int tv = q.front();
        q.pop();
        for (auto tu : g[tv]) {
            if (dist1[tu] > dist1[tv] + 1) {
                dist1[tu] = dist1[tv] + 1;
                q.push(tu);
            }
        }
    }
    q.push(u);
    dist2[u] = 0;
    while (!q.empty()) {
        int tv = q.front();
        q.pop();
        for (auto tu : g[tv]) {
            if (dist2[tu] > dist2[tv] + 1) {
                dist2[tu] = dist2[tv] + 1;
                q.push(tu);
            }
        }
    }
    int ma = 0, bv = 0;
    for (int i = 0; i < n; ++i) {
        if (g[i].size() == 1 && ma < dist2[i] && dist1[i] < dist2[i]) {
            ma = dist2[i];
            bv = i;
        }
    }
    cout << ma - 1;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    solve();
    return 0;
}


Measured memory_bytes: 8064
#include <bits/stdc++.h>
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>*/
 
#define pll              pair <long long,long long>
#define pb               push_back
#define ll               long long
#define ff               first
#define ss               second
#define D(x)             cerr<<#x " = "<<(x)<<endl
#define vll              vector <ll>
#define IOS              ios_base::sync_with_stdio(0); cin.tie(NULL);
#define endl             '\n'   
using namespace std;
const ll N=2e5+2;
ll connected;
ll root[N], sz[N];
ll n;

void init()
{
	for(ll i=1;i<=n;i++)
	{
		root[i]=i;
		sz[i]=1;
	}
	connected=n;
}

ll rt(ll k)
{
	while(k!=root[k])
	{
		root[k]=root[root[k]];
		k=root[k];
	}
	return k;
}

void merge(ll u, ll v)
{
	ll rt1=rt(u);
	ll rt2=rt(v);

	if(rt1==rt2)
		return;

	connected--;

	if(sz[rt1]>sz[rt2])
		swap(rt1, rt2);

	sz[rt2]+=sz[rt1];
	sz[rt1]=0;
	root[rt1]=root[rt2];
}
int main()
{
    IOS
 	// freopen("input.txt","r",stdin);
 	// freopen("output.txt","w",stdout);
 	// freopen("error.txt","w",stderr);
    cin>>n;
    init();
    ll m;
    cin>>m;
    for(ll i=0;i<m;i++)
    {
    	ll x,y;
    	cin>>x>>y;
    	merge(x,y);
    }
    ll mx=0;
    for(ll i=1;i<=n;i++)
    {
    	mx=max(mx,sz[i]);
    }
    cout<<mx<<endl;
    return 0;
}

Measured memory_bytes: 6776
import java.util.*;
import java.util.Collections;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] S = sc.next().toCharArray();

        int CI = S[0] - 'a';
        char[] alpha = new char[26];
        char ch = 'a';
        for (int i = 0; i < 26; i++){
            alpha[i] = ch++;
        }

        System.out.println(alpha[CI + 1]);
    }
}


Measured memory_bytes: 22996
#include <vector> 
#include <list> 
 #include <map>
 #include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
using namespace std;

//conversion
//------------------------------------------
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();}

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

//typedef
//------------------------------------------
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long LL;

//container util
//------------------------------------------
#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())

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

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

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

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

#define YES_ cout<<"YES"<<endl;return 0;
#define NO_ cout<<"NO"<<endl;return 0;

int main(){
 
    int A=0,B=0;
    int N;
    cin>>N;
    VI a(N);
    REP(i,N){
        cin>>a[i];
    }
    sort(ALL(a),std::greater<int>());

    REP(i,SZ(a)){
        if(i%2==0){
            A+=a[i];
        }
        else{
            B+=a[i];
        }
    }
    cout<<A-B<<endl;


}


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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int k, x;
  cin >> k >> x;
  if(500 * k >= x) puts("Yes");
  else puts("No");
  return 0;
}

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

int main(){
  int N;
  string S;
  cin >> N >> S;
  for(int i=0;i<S.size();i++){
    char C=S.at(i)+N;
      char D=C-26;
    if(C<='Z'){
      cout << C;
    }
    else{
      cout << D;
    }
  }
  cout << endl;
}  

Measured memory_bytes: 256
N, M = map(int, input().split())
ex = []
i = 2
while i**2 <= M:
    j = 0
    while M % i == 0:
        M //= i
        j += 1
    if j != 0:
        ex.append(j)
    i += 1
if M > 1: # M is a prime.
    ex.append(1)

mod = 10**9+7
ans = 1
for e in ex: # (e+N-1) choose e
    temp = 1
    for i in range(e):
        temp *= (e+N-1 - i)
    for i in range(e):
        temp //= (e - i)
    ans *= temp
    ans %= mod
print(ans)

Measured memory_bytes: 3064
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>

int main() {

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

    if (a >= k) {
        printf("%ld %ld", a - k, b);
    } else if (a + b >= k) {
        printf("%d %ld", 0, a + b - k);
    } else {
        printf("%d %d", 0, 0);
    }


    return 0;

}


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

int main()
{
	string b;
	cin >> b;
	if (b == "A")
		cout << "T";
	else if (b == "C")
		cout << "G";
	else if (b == "G")
		cout << "C";
	else if (b == "T")
		cout << "A";
		
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int mod=1e9+7;
const int N=2e3+5;
ll dp[N][N];
ll maxn;

struct nobe{
ll v,p;
}a[N];

bool cmp(nobe a,nobe b){
return a.v>b.v;
}

int main(){
ll n;
cin>>n;
for(ll i=0;i<n;i++){
    cin>>a[i].v;
    a[i].p=i+1;
}
sort(a,a+n,cmp);
for(ll i=0;i<=n;i++)
    for(ll j=0;j<=n;j++){
    if(i+j==n) {
        maxn=max(maxn,dp[i][j]);
        break;
        }
    int k=i+j;
    dp[i+1][j]=max(dp[i+1][j],dp[i][j]+abs(a[k].p-i-1)*a[k].v);
    dp[i][j+1]=max(dp[i][j+1],dp[i][j]+abs(a[k].p-n+j)*a[k].v);
}
cout<<maxn<<endl;
return 0;
}

Measured memory_bytes: 26252
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <functional>
#include <utility>
#include <tuple>
#include <cctype>
#include <bitset>
using namespace std;
#define INF 0x3f3f3f3f
#define INFLL 0x3f3f3f3f3f3f3f3fLL
#define MOD 1000000007
#define mp make_pair
#define mt make_tuple
#define pb push_back
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pint;
typedef pair<ll,ll> pll;
typedef tuple<int,int,int> tint;
typedef vector<int> vint;
typedef vector<ll> vll;
int dx[8]={0,0,-1,1,1,1,-1,-1};
int dy[8]={-1,1,0,0,1,-1,1,-1};
const int SIZE=100050;
//ここまでテンプレ
int main(){
	int A,B,C,X;
	cin>>A>>B>>C>>X;
	int ans=0;
	for(int i=0;i<=A;i++)
		for(int j=0;j<=B;j++)
			for(int k=0;k<=C;k++)
				if(i*500+j*100+k*50==X)
					ans++;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = ((int)(n)-1); i >= 0; i--)
#define all(x) (x).begin(),(x).end()
 
using namespace std;
using ll = long long;
 
struct edge { int to, cost; };
 
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> P;
 
const int INF = 1e9;
const double EPS = 1e-10;
const int MOD = 1e9+7;
const double PI = acos(-1.0);
 
const int mx4[] = {0,1,0,-1};
const int my4[] = {1,0,-1,0};
const int mx8[] = {0,1,1,1,0,-1,-1,-1};
const int my8[] = {1,1,0,-1,-1,-1,0,1};

int main(){
	int n,m;
	cin >> n >> m;
	vector<P> v;
	int a,b;
	rep(i,n){
		cin >> a >> b;
		v.emplace_back(a,b);
	}

	sort(all(v));

	int sum = 0,j = 0;
	priority_queue<int> que;
	for(int i = 0; i <= m; i++){
		while(j < n && v[j].first <= i){
			que.push(v[j++].second);
		}
		if(que.size()){
			sum += que.top();
			que.pop();
		}
	}

	cout << sum << endl;

	return 0;
}

Measured memory_bytes: 1908
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long n,a,b;
    cin>>n>>a>>b;
    long long c=n/(a+b);
    long long d=n%(a+b);
    long long e;
    if(d>=a)
        e=a;
    else
        e=d;
    c=c*a;
    cout<<c+e;
    return 0;
}


Measured memory_bytes: 256
from re import match
s, t = input().replace('?', '.'), input()

for i in range(len(s) - len(t) + 1)[::-1]:
    if match(s[i:i + len(t)], t):
        key = (s[:i] + t + s[i + len(t):]).replace('.', 'a')
        print(key)
        break
else:
    print('UNRESTORABLE')


Measured memory_bytes: 3188
n, x = map(int, raw_input().split())
s = n
r = 1
if n - x > x:
    a, b = n - x ,x
else:
    a, b = x, n - x
while r > 0:
    q = a / b
    r = a % b
    if r > 0:
        s += 2 * q * b
    else:
        s += (2 * q - 1) * b
    a, b = b, r
print s

Measured memory_bytes: 2568
#import sys
#input = sys.stdin.readline
#input = sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode()

#import numpy as np


def main():
	s=input()

	if s==s.capitalize():
		print("A")
	else:
		print("a")







if __name__ == "__main__":
	main()


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

string s[200];
int c[200], l[200];

int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
        for (auto j : s[i]) l[i] += (j == '.');
        for (int j = 0; j < m; j++) c[j] += (s[i][j] == '.');
    }
    for (int i = 0; i < n; i++)
    {
        bool tag = 0;
        for (int j = 0; j < m; j++)
            if (l[i] != m && c[j] != n) cout << s[i][j], tag = 1;
        if (tag) puts("");
    }
    return 0;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

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

constexpr double PI = 3.14159265358979323846;
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

class DFriction {
public:
    void solve(istream& cin, ostream& cout) {
      SPEED;
      int h, w; cin >> h >> w;
      int ans = 0;
      vector<vector<char>> mat(w, vector<char>(h));
      rep(i, h) {
        rep(j, w) {
          cin >> mat[j][i];
        }
      }

      rep(i, w-1) {
        vector<vector<int>> cost(h+1, vector<int>(h+1));
        for(int k=-h+1; k<h; k++) {
          int cnt = 0;
          for(int a=0; a<h; a++) {
            auto b = a+k;
            if (b < 0 || h <= b) continue;
            if (mat[i][a] == mat[i+1][b]) cnt++;
            cost[h-1-a][h-1-b] = cnt;
          }
        }

        vector<vector<int>> dp(h+1, vector<int>(h+1, INT_MAX/2));
        dp[0][0] = 0;
        rep(j, h+1) {
          rep(k, h+1) {
            if (j+1 <= h) {
              chmin(dp[j+1][k], dp[j][k] + cost[j][k]);
            }
            if (k+1 <= h) {
              chmin(dp[j][k+1], dp[j][k] + cost[j][k]);
            }
          }
        }
        ans += dp[h][h];
      }
      cout << ans << endl;

    }
};

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

Measured memory_bytes: 1152
//Date and time of submission: 
 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5;
ll n,l;
int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin>>n>>l;
	string s[n];
	for(ll i=0;i<n;i++)
	cin>>s[i];
	sort(s,s+n);
	for(ll i=0;i<n; i++)
	cout<<s[i];
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,n,m) for(int i = (n); i <(m); i++)
#define rrep(i,n,m) for(int i = (n) - 1; i >=(m); i--)
#define pvec(vec) {for (auto v: vec) cout << v << ' '; cout << endl;}
#define pivec(vec) {rep(i, 0, vec.size()) cout << i << ':' << vec[i] << ' '; cout << endl;}

using namespace std;
using ll = long long;

int main()
{
    int a;
    cin >> a;

    cout << a + a*a + a*a*a << endl;
    return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const int INF=1001001001;
vector<pair<int64_t,int64_t>>prime_factorize(int64_t x){
  vector<pair<int64_t,int64_t>>p;
  for(int64_t i=2;i*i<=x;i++){
    int cnt=0;
    if(x%i==0){
    while(x%i==0){cnt++;x/=i;}
    p.push_back(make_pair(i,cnt));
    }
  }
  if(x!=1){p.push_back(make_pair(x,1));}
  return p; 
}
int main() {
  int N;
  string s;
  cin>>N>>s;
  map<char,int64_t>k;
  for(int i=0;i<N;i++){
    k[s[i]]++;
  }
  int64_t sum=k['R']*k['G']*k['B'];
  int64_t cnt=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      if(2*j-i<N){
        if(s[2*j-i]!=s[i]&&s[2*j-i]!=s[j]&&s[i]!=s[j]){
          cnt++;
        }
      }
    }
  }
  cout<<sum-cnt<<endl;
  return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
#define ss second
#define ff first
#define all(x) x.begin(), x.end()
#define DEBUG

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;

const ll oo = 1e17 + 7;
const ll mod = 1e9 + 7, maxn = (5 * 1e5) + 10, maxm = (3e6) + 2;
const double PI = acos(-1);

int main (){
    ios_base::sync_with_stdio(false);
    ll n, d, a, ans = 0;

    cin >> n >> d >> a;

    vector<pii> vs(n);

    for (auto &i: vs) cin >> i.ff >> i.ss;

    sort(all(vs));

    ll dano = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;

    for (int i=0; i<n; i++){
        ll x, h;
        tie(x, h) = vs[i];

        h = (h - 1)/a + 1;
        while (!q.empty() and q.top().ff < x) dano -= q.top().ss, q.pop();
        if (dano >= h) continue;
        
        q.push({x+2*d, h-dano});
        ans += h-dano;
        dano += h-dano;
    }

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

Measured memory_bytes: 8448
N = int(input())
A = [int(c) for c in input().split()]
B = [int(c) for c in input().split()]

total = 0
for i in range(N):
  defeat_i = min(A[i], B[i])
  A[i] -= defeat_i
  defeat_i1 = min(A[i+1], B[i] - defeat_i)
  A[i+1] -= defeat_i1
  total += defeat_i + defeat_i1

print(total)
  

Measured memory_bytes: 18624
#include <bits/stdc++.h>
#define PREP(i, s, x) for(ll i = (s); i < (x); i++)
#define MREP(i, s, x) for(ll i = (s); i >= (x); i--)
#define REP(i, x) PREP(i, 0, x)
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
template<typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); }
template<typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// variable -------------------------------------------

constexpr ll INF = (1ll << 60);
constexpr ll MOD = 1000000007ll;

// struct ---------------------------------------------

// function -------------------------------------------

ll f(string b){
    ll res = 0;
    res += (b[0] - '0') * 100;
    res += (b[2] - '0') * 10;
    res += b[3] - '0';
    return res;
}

// main -----------------------------------------------

int main() {
    ll a;
    string b;
    cin >> a >> b;
    ll bb = f(b);
    ll ans = a * bb;
    cout << ans / 100 << endl;

    return 0;
}


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

vector<char> vec;

void vecerase(int i){
	for(int j = 2;j >= 0;j--){
		vec.erase(vec.begin() + (i + j));
	}
	vec.insert(vec.begin() + i,'x');
}

void voice(){
	for(int i = 0;i < vec.size();i++){
		if(vec[i] == 'm'){
			if(vec[i+1] == 'e'){
				if(vec[i+2] == 'w'){
					vecerase(i);
				}
				else if(vec[i+2] == 'x'){
					if(vec[i+3] == 'w'){
						vec.erase(vec.begin() + i+2);
						vecerase(i);
					}
				}
			}
			else if(vec[i+1] == 'x'){
				if(vec[i+2] == 'e'){
					if(vec[i+3] == 'w'){
						vec.erase(vec.begin() + i+1);
						vecerase(i);
					}
					else if(vec[i+3] == 'x'){
						if(vec[i+4] == 'w'){
							vec.erase(vec.begin() + i+3);
							vec.erase(vec.begin() + i+1);
							vecerase(i);
						}
					}
				}
			}
		}
	}
}

int main(){
	int n;
	string s;
	cin >> s;
	for(int i = 0;i < s.size();i++){
		vec.push_back(s[i]);
	}
	vec.push_back('.');
	n = vec.size();
	while(1){
		voice();
		if(n == vec.size())break;
		n = vec.size();
	}
	if(n == 2 && vec[0] == 'x')cout << "Cat" <<endl;
	else cout << "Rabbit" <<endl;

	return 0;
}

Measured memory_bytes: 3172
#include<iostream>
#include<algorithm>
#include<vector>
#define PP std::pair<int,int>
#define LL long long
int N;
int P[200010];
int D[200010];
int ans=1<<30;
int main(){
    std::cin>>N;
    for(int i=1;i<=N;i++){
        std::cin>>P[i];
        D[P[i]]=i;
    }
    int res=0;
    for(int i=1;i<=N+1;i++){
        if(D[i]>D[i-1])res++;
        else{
            ans=std::min(ans,N-res);
            res=1;
        }
    }
    std::cout<<ans<<std::endl;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;
int v[14],a,b,c,d;
int main()
{
    cin>>a>>b>>c>>d;
    v[a]++;
    v[b]++;
    v[c]++;
    v[d]++;
    if(v[1] && v[9] && v[7] && v[4])cout<<"YES\n";
    else cout<<"NO\n";
    return 0;
}


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

int n, mid, l, r, ty;
string s;

int check(int i)    {
    cout << i << '\n'; cout.flush();
    cin >> s;
    if(s == "Male") return 1;
    else if(s == "Female") return 2;
    else return 0;
}

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

    cin >> n;
    int l = 0, r = n - 1;
    int las = check(0);
    if(!las) return 0;
    int lasr = check(n - 1); if(!lasr) return 0;

    while(l + 1 != r)    {
        int mid = (l + r) / 2;
        int tmp = check(mid);
        if(abs(tmp - las) != mid % 2) r = mid;
        else l = mid;
    }

    las = check(l); cout.flush();
    if(!las) return 0;
    else {
        cout << r << '\n'; cout.flush();
    }

    return 0;
}


Measured memory_bytes: 976
#include<iostream>
#include<algorithm>
#include<functional>
#include<cmath>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<deque>
using namespace std;
#define ll long long
const int mod = 1000000007;
const int MOD = 998244353;
const ll INF = 1000000000000000000;

int B[110];
int main()
{
	int N;
	cin >> N;
	for (int i = 0; i < N - 1; i++) cin >> B[i];
	int ans = 0;
	ans += B[0] + B[N - 2];
	for (int i = 0; i < N - 2; i++) {
		ans += min(B[i], B[i + 1]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3624
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int x = Integer.parseInt(br.readLine());
		System.out.println(x*x*x);
	}
}

Measured memory_bytes: 24128
import java.util.Scanner;

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 tmp;
        if(a > b){
            tmp = b;
            b = a;
            a = tmp;
        }
        if(a > c){
            tmp = c;
            c = a;
            a = tmp;
        }
        if(b > c){
            tmp = c;
            c = b;
            b = tmp;
        }
        System.out.println(a + " " + b + " " + c);
    }
}


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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

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

using ll = long long;

using namespace std;

int main() {
  in(int, n);
  out(1110 - n);
}


Measured memory_bytes: 3584
import sys
readline = sys.stdin.readline
from heapq import heapify, heappush, heappop

def main():
    N, K = map(int, readline().rstrip().split())
    V = list(map(int, readline().rstrip().split()))
    V_rev = V[::-1]
    res = 0
    for x in range(min(N, K)+1):
        for y in range(min(N, K)-x+1):
            z = K - x - y
            temp = V[:x] + V_rev[:y]
            heapify(temp)
            for _ in range(z):
                if temp:
                    m = heappop(temp)
                    if m >= 0:
                        heappush(temp, m)
                        break
                else:
                    break

            res = max(res, sum(temp))
    
    print(res)


if __name__ == '__main__':
    main()

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

//ただの辺
struct edge {
    using lint = long long int;
    int to;
    lint cost;
    //引数一つの時は距離1
    edge(int t, lint c = 1) : to(t), cost(c) {
    }
};

// 木のlcaをキビキビ計算
// depend:edge
struct lowest_common_ancestor {
    using G = vector<vector<edge>> &;
    G g;
    int sz;
    int root;
    int log;
    vector<int> dep;
    vector<vector<int>> parent;
    lowest_common_ancestor(G _g, int _root)
        : g(_g), sz(_g.size()), root(_root), dep(_g.size()) {
        log = 1;
        while (1 << log < sz) log++;
        parent.assign(log, vector<int>(sz, -1));
    }
    // parent[0]埋め、深さ埋め
    void dfs(int now, int p, int d) {
        parent[0][now] = p;
        dep[now] = d;
        for (int i = 0; i < (int)g[now].size(); i++) {
            int next = g[now][i].to;
            if (next != p) dfs(next, now, d + 1);
        }
    }
    // 前計算を済ませる O(nlog n)
    void build() {
        dfs(root, -1, 0);
        for (int i = 1; i < log; i++) {
            for (int j = 0; j < sz; j++) {
                if (parent[i - 1][j] == -1)
                    parent[i][j] = -1;
                else
                    parent[i][j] = parent[i - 1][parent[i - 1][j]];
            }
        }
    }
    // uとvのlcaを求める O(log sz)
    int query(int u, int v) {
        if (dep[u] > dep[v]) swap(u, v);
        for (int i = 0; i < log; i++) {
            if ((dep[v] - dep[u]) & (1 << i)) v = parent[i][v];
        }
        if (u == v) return u;
        for (int i = log - 1; i >= 0; i--) {
            if (parent[i][u] != parent[i][v])
                u = parent[i][u], v = parent[i][v];
        }
        return parent[0][u];
    }
};

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

int main() {
    int n, u, v;
    cin >> n >> u >> v;
    u--, v--;
    vector<vector<edge>> g(n);
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    lowest_common_ancestor lca(g, u);
    lca.build();
    int ans = lca.dep[v] - 1;
    //高橋がiとその親の間を往復したい
    for (int i = 0; i < n; i++) {
        //高橋が青木より先にiとvのlcaにたどり着けるか
        int l = lca.query(i, v);
        int d_v = lca.dep[v];
        int d_l = lca.dep[l];
        if (g[i].size() > 1) {
            continue;
        }
        if (d_v < 2 * d_l) {
            continue;
        } else if (d_v == 2 * d_l) {
            chmax(ans, d_l);
            continue;
        } else {
            int cand = 0;
            cand += lca.dep[i];
            int dist = d_v - 2 * d_l;
            cand += dist - 1;
            chmax(ans, cand);
        }
    }
    cout << ans << endl;
}

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

typedef long long ll;
typedef vector<ll> vl;
typedef long double ld;
typedef vector<ld> vd;
typedef bool bl;
typedef vector<bl> vb;
 
const ll e5 = 1 << 20;
const ll mod = 998244353;
const ll e3 = 1 << 13;
const ll INF = 1ll << 60;
 
int main() {
  int n;
  cin >> n;

  typedef pair<int, int> pair;
  vector<pair> ab(n, make_pair(0, 0));

  rep(i, n) {
    cin >> ab[i].first >> ab[i].second;
  }

  std::sort(
    ab.begin(),
    ab.end(),
    [](const pair& x, const pair& y){return x.second < y.second;}
  );

  int sum = 0;
  bool able = true;
  rep(i, n) {
    sum += ab[i].first;
    int limit = ab[i].second;
    if(sum > limit) {
      able = false;
      break;
    }
  }

  if (able) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }

  return 0;
}

Measured memory_bytes: 1920
def examD():
    N, M = LI()
    right = defaultdict(int)
    for _ in range(M):
        a, b = LI()
        right[b] = max(right[b],a)
    ans = 0; cur = 0
    for i in range(1,N+1):
        if right[i]>cur:
            ans +=1
            cur = i-1
    print(ans)

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examD()


Measured memory_bytes: 17812
#include <bits/stdc++.h>
using namespace std;
int n,h[100005],dp[100005],k;
int f(int i)
{
	if(i==(n-1) )
	return 0;
	if(dp[i]!=-1)
	return dp[i];
	int ans= abs(h[i]-h[i+1])+f(i+1);
	for(int j=2;j<=k;j++)
	if( (i+j)<n)
		ans=min(ans,abs(h[i]-h[i+j])+f(i+j));
	return dp[i]=ans;
}
int main()
{
	cin>>n>>k;
	for(int i=0;i<n;i++)
	cin>>h[i];
	memset(dp,-1,sizeof(dp));
	cout<<f(0)<<endl;
	return 0;
}

Measured memory_bytes: 5760
using System;
using System.Collections.Generic;
using System.Text;

namespace codeTester.contest190622
{
    class ProblemC
    {
        static List<long> values = new List<long>();
        static long answer = 0;

        public static void Main(string[] args)
        {
            Input();
            Logic();
            Output();
        }

        static void Input()
        {
            values = ReadSpaceSeparatedValues();
        }

        public static List<long> ReadSpaceSeparatedValues()
        {
            List<long> values = new List<long>();
            string[] inputs = Console.ReadLine().Split(' ');
            foreach (string input in inputs)
            {
                values.Add(long.Parse(input));
            }

            return values;
        }

        static void Logic()
        {
            long A = values[0];
            long B = values[1];
            long C = values[2];
            long D = values[3];
            long CDLCM = (C * D) / Gcd(C, D);
            // まず 1 から B までの間でどうなのかを単に割り算で判定
            // 次に 1 から A - 1 までの間でどうなのかを判定
            // 最後引き算、かな。
            long dividableByCIn1ToB = B / C;
            long dividableByDIn1ToB = B / D;
            long dividableByCDIn1ToB = B / CDLCM;
            long dividableByCOrDIn1ToB = dividableByCIn1ToB + dividableByDIn1ToB - dividableByCDIn1ToB;
            long dividableByCIn1ToBeA = (A - 1) / C;
            long dividableByDIn1ToBeA = (A - 1) / D;
            long dividableByCDIn1ToBeA = (A - 1) / CDLCM;
            long dividableByCOrDIn1ToBeA = dividableByCIn1ToBeA + dividableByDIn1ToBeA - dividableByCDIn1ToBeA;
            long dividableByCOrDInAToB = dividableByCOrDIn1ToB - dividableByCOrDIn1ToBeA;
            long undividableByCorDInAToB = (B - A + 1) - dividableByCOrDInAToB;
            answer = undividableByCorDInAToB;
        }

        public static long Gcd(long a, long b)
        {
            if (a < b)
                // 引数を入替えて自分を呼び出す
                return Gcd(b, a);
            while (b != 0)
            {
                var remainder = a % b;
                a = b;
                b = remainder;
            }
            return a;
        }

        static void Output()
        {
            Console.WriteLine(answer.ToString());
        }
    }
}


Measured memory_bytes: 11220
#include <bits/stdc++.h>
using namespace std;
#define ll int64_t
#include <cstdlib> 
#include <math.h>
#include<cstdio>
#include<cstring>
#define FOR(I, A, B) for (int I = (A); I <= (B); I++)
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fo(i,n) for(int i=0;i<n;i++)
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define dbg(x) cout << #x << " = " << x << endl
#define dbg2(x,y) cout << #x << " = " << x << ", " << #y << " = " << y << endl
#define dbg3(x,y,z) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl
#define dbg4(x,y,z,q) cout << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << ", " << #q << " = " << q << endl
#define scan(char_array) scanf("%[^\n]s",&char_array);


const int N=105;
ll powers[N];
ll primes[N];


void sieve()
{
  
  
  for(ll i=2;i<=N;i++)
  {
    if(primes[i]==-1)
    {
        for(ll j=i;j<=N;j+=i) primes[j]=i;
        
     }
   }

}

int main(){
    ll n;
    IOS
    cin>>n;
    fo(i,N){
        primes[i]=-1;
        powers[i]=0;
    }
  
    set<ll> st;
    ll tmp=1;
    sieve();
    FOR(i,2,n){
        ll tmp=i;
        while(tmp>1){
            ll y=primes[tmp];
            ll count=0;
            st.insert(y);

            while(tmp%y==0){
                tmp=tmp/y;
                count++;
            }
            powers[y]=(powers[y]+count); 
        }
    }
    //dbg("vfdvfd");
    std::vector<ll> primes;
    for(auto oo:st){
    	primes.pb(oo);
    	//dbg2(oo,powers[oo]);
    }
    ll ans=0;
    ll nn=sz(primes);
    fo(i,nn){
    	if(powers[primes[i]]>=14){
    		fo(j,nn){
    			if(j!=i&&powers[primes[j]]>=4){
    				ans++;
    			}
    		}
    	}
    }
    fo(i,nn){
    	if(powers[primes[i]]>=24){
    		fo(j,nn){
    			if(j!=i&&powers[primes[j]]>=2){
    				ans++;
    			}
    		}
    	}
    }
    fo(i,nn){
    	if(powers[primes[i]]>=74){
    		ans++;
    		
    	}
    }
    fo(i,nn){
    	if(powers[primes[i]]>=4){
    		FOR(j,i+1,nn-1){
    			if(j!=i&&powers[primes[j]]>=4){
    				fo(k,nn){
    					if(k!=i&&k!=j&&powers[primes[k]]>=2){
    						ans++;
    						//dbg3(i,j,k);
    					}
    				}
    			}
    		}
    	}
    }
    cout<<ans<<endl;




  }

Measured memory_bytes: 256
/**
 *    author  : 𝒌𝒚𝒐𝒎𝒖𝒌𝒚𝒐𝒎𝒖𝒑𝒖𝒓𝒊𝒏
 *    created : 2020-04-02 11:05:58
**/

#include <iostream>
#include <deque>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <complex>
#include <numeric>
#include <bitset>
#include <cassert>
#include <cctype>
#include <iomanip>
#include <random>
#include <utility>
#include <chrono>

using namespace std;

using int64 = long long;

template<class T> using binary_heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
template<class T> std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) { os << '{'; size_t n = vec.size(); for (size_t i = 0; i < n; ++i) { os << vec[i]; if (i != n - 1) os << ','; } os << '}'; return os; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) { return os << '{' << p.first << " " << p.second << '}'; }
template<class T, class U> std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) { os << '{'; for (auto it = mp.begin(); it != mp.end(); ++it) { os << '{' << it->first << ':' << it->second << '}'; if (it != --mp.end()) os << ','; } os << '}'; return os; }
template<class T> std::ostream& operator<<(std::ostream& os, const std::set<T>& st) { os << '{'; for (auto it = st.begin(); it != st.end(); ++it) { os << *it; if (it != --st.end()) os << ','; } os << '}'; return os; }
template<class T> std::istream& operator>>(std::istream& is, std::vector<T>& vec) { size_t n = vec.size(); for (size_t i = 0; i < n; ++i) is >> vec[i]; return is; }

#define all(_) begin(_), end(_)
#define rall(_) rbegin(_), rend(_)

#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...) 1728
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}

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

  int h, w; cin >> h >> w;
  vector<string> s(h); cin >> s;
  int white = 0;

  for (int i = 0; i < h; ++i) {
    for (int j = 0; j < w; ++j) {
      white += s[i][j] == '.';
    }
  }

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

  const int inf = 1e9;

  vector<vector<int>> dis(h + 1, vector<int>(w + 1, inf));

  dis[0][0] = 0;

  queue<pair<int, int>> que;
  que.push({0, 0});

  auto In = [&](int x, int y) -> bool {
    return x >= 0 && x < h && y >= 0 && y < w && s[x][y] != '#';
  };

  while (!que.empty()) {
    pair<int, int> cur = que.front(); que.pop();
    for (int i = 0; i < 4; ++i) {
      int nx = cur.first + dx[i], ny = cur.second + dy[i];
      if (!In(nx, ny) || dis[nx][ny] != inf) continue;
      dis[nx][ny] = dis[cur.first][cur.second] + 1;
      que.push({nx, ny}); 
    }
  }
  if (dis[h - 1][w - 1] == inf) {
    cout << -1 << endl;
  } else {
    cout << white - dis[h - 1][w - 1] - 1 << endl;
  }

  return 0;
}

Measured memory_bytes: 256
#include <iomanip>
#include <iostream>
#include <string>

int main()
{
    int n , k , cnt{};
    std :: cin >> n >> k;

    std :: string str;
    std :: cin >> str;

    for(int i = 0 ; i < n - 1 ; i++)
        if(str.at(i) == str.at(i + 1))
            cnt++;

    std :: cout << (cnt + 2 * k <= n - 1 ? cnt + 2 *  k : n - 1) << '\n';
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
#define MAXN 200100
#define pii pair<int,int>
#define ff first
#define ss second
#define ll long long
#define in_range(x, y, n) (x >= 0 and x<n and y >=0 and y<n)
using namespace std;
const ll mod = 1e9 + 7;

ll fexp(ll a, ll b){
    ll ans = 1;

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

int main (){
    ios_base::sync_with_stdio(false);
    ll n;
    cin >> n;

    vector<ll> v(n);
    map<ll, ll> freq;

    for (int i=0; i<n; i++){
        cin >> v[i];
        freq[v[i]]++;
    }

    ll con = n -1;

    while (con > 0){
        if (freq[con] != 2){
            cout << "0" << endl;
            return 0;
        }
        con -= 2;
    }

    if (n%2 == 1 and freq[0] != 1) cout << "0" << endl;
    else cout << fexp(2LL, n/2LL) << endl;
    return 0;
}

Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
const int N = 301000;
int n,p[N],val[N],sum,f[N][2];
struct BIT{
	stack<int> c[N];
	void modify(int x,int k){
		for(int i=x;i;i-=i&-i) if(c[i].empty()||c[i].top()<=k) c[i].push(k);
	}
	void erase(int x,int k){
		for(int i=x;i;i-=i&-i) if(!c[i].empty()&&c[i].top()==k) c[i].pop();
	}
	int query(int x){
		int ans=-1e9;
		for(int i=x;i<=n;i+=i&-i) if(!c[i].empty()) ans=max(ans,c[i].top());
		return ans;
	}
}t[2];
bool check(int cnta,int cntb,int mxa,int mxb){
	int tmp=t[sum+cnta-cntb&1].query(mxb+1);
	if(tmp>=sum+cnta-cntb&&sum+cnta-cntb>=0) return 1;
	tmp=t[sum-cnta+cntb&1].query(mxa+1);
	if(tmp>=sum-cnta+cntb&&sum-cnta+cntb>=0) return 1;
	return 0;
}
int main(){
	read(n);
	for(int i=1;i<=n;i++)
		read(p[i]);
	int mx=0;
	for(int i=1;i<=n;i++)
		val[i]=p[i]>mx,mx=max(p[i],mx),sum+=val[i];
	t[0].modify(n,0);
	for(int i=n;i;i--){
		f[i][0]=t[0].query(p[i])+val[i]+1;
		f[i][1]=t[1].query(p[i])+val[i]+1;
		t[val[i]^1].modify(p[i],f[i][0]);
		t[val[i]].modify(p[i],f[i][1]);
	}
	int cnta=0,cntb=0,mxa=0,mxb=0;
	if(!check(0,0,0,0)){puts("-1");return 0;}
	for(int i=1;i<=n;i++){
		t[val[i]^1].erase(p[i],f[i][0]);
		t[val[i]].erase(p[i],f[i][1]);
		sum-=val[i];
		if(check(cnta+(p[i]>mxa),cntb,max(mxa,p[i]),mxb)){
			putchar('0');
			cnta+=p[i]>mxa;
			mxa=max(mxa,p[i]);
		}
		else{
			putchar('1');
			cntb+=p[i]>mxb;
			mxb=max(mxb,p[i]);
		}
	}
	puts("");
	return 0;
}


Measured memory_bytes: 417792
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;

int main(){
    char a; cin >> a;

    if (a >= 'a' && a <= 'z'){
        cout << "a" << endl;

    }
    else{
        cout << "A" << endl;
    }
   
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define double long double
#define int long long
#define mii map<int,int>
#define pii pair<int,int>
#define low lower_bound
#define upp upper_bound
#define mod 1000000007 //10^9+7
#define inf (int)50000000000 //5･10^10
#define rep(i,n) for(int i=0;i<n;i++)
#define all(vec) vec.begin(),vec.end()
#define vsort(vec) sort(all(vec))
#define vrever(vec) reverse(all(vec));
#define vunsort(vec) vsort(vec); vrever(vec);
#define bisea binary_search
#define cend cout<<endl;
#define F first
#define S second
using namespace std;
signed main() {
  int n;
  string s;
  cin>>n>>s;
  int cnt[26];
  rep(i,26) cnt[i]=0;
  rep(i,n) cnt[s[i]-'a']++;
  int ans=1;
  rep(i,26) {
    ans*=(cnt[i]+1);
    ans%=mod;
  }
  cout<<ans-1<<endl;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, s, t) for(int i = (s), mi = (t); i <= mi; i++)
#define dwn(i, s, t) for(int i = (s), mi = (t); i >= mi; i--)

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == '-') f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - '0'; c = getchar(); }
	return x * f;
}

#define maxn 100010
#define maxm 100010

int n, A[maxn], B[maxn], num[maxn], cntn, tot[maxn];

namespace G {
	int m, head[maxn], nxt[maxn], to[maxn], fa[maxn], cnte[maxn];
	void init() {
		rep(i, 1, n) fa[i] = i;
		return ;
	}
	int findset(int x) { return x == fa[x] ? x : fa[x] = findset(fa[x]); }
	void AddEdge(int a, int b) {
		to[++m] = b; nxt[m] = head[a]; head[a] = m;
		int u = findset(a), v = findset(b);
		if(u != v) fa[v] = u, cnte[u] += cnte[v];
		cnte[u]++;
		return ;
	}
}
bool vis[maxn];

int main() {
	n = read(); int X = 0;
	rep(i, 1, n) num[++cntn] = A[i] = read(), X ^= A[i];
	rep(i, 1, n) B[i] = read();
	
	num[++cntn] = X;
	sort(num + 1, num + cntn + 1);
	cntn = unique(num + 1, num + cntn + 1) - num - 1;
	rep(i, 1, n) {
		int t = lower_bound(num + 1, num + cntn + 1, A[i]) - num; A[i] = t;
		tot[t]++;
		t = lower_bound(num + 1, num + cntn + 1, B[i]) - num;
		if(B[i] != num[t]) return puts("-1"), 0;
		B[i] = t;
		tot[t]--;
	}
	int inB = 0;
	rep(i, 1, cntn) {
		if(abs(tot[i]) > 1) return puts("-1"), 0;
		if(tot[i] == -1) {
			if(inB) return puts("-1"), 0;
			inB = i;
		}
	}
	if(inB && num[inB] != X) return puts("-1"), 0;
	
	G::init();
	rep(i, 1, n) if(A[i] != B[i]) G::AddEdge(B[i], A[i]);
	int Xp; rep(i, 1, cntn) if(num[i] == X) Xp = i;
	int u = G::findset(Xp), ans = G::cnte[u]; vis[u] = 1;
	rep(i, 1, cntn) {
		u = G::findset(i);
		if(!vis[u] && G::cnte[u]) vis[u] = 1, ans += G::cnte[u] + 1;
	}
	printf("%d\n", ans);
	
	return 0;
}

Measured memory_bytes: 5376