akhauriyash/Code-Regression huggingface dataset:
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>
using namespace std;
#define rg register
#define LL long long
#define __space putchar(' ')
#define __endl putchar('\n')
template <typename qwq> inline void read(qwq & x)
{
    x = 0;
    rg int f = 1;
    rg char c = getchar();
    while (c < '0' || c > '9')
    {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9')
    {
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    x *= f;
}
template <typename qaq> inline void print(qaq x)
{
    if (x < 0)
    {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int n,ans,last = -1;
int a[2333333];
bool lis,lds;//当前为不下降/不上升 
int main()
{
	read(n);
	for (rg int i = 1;i <= n;++i) read(a[i]);
	for (rg int i = 1;i <= n;++i)
	{
		if (!lis && !lds && last == -1)//一个序列开始 
		{
			++ans;
			last = a[i];
			continue;
		}
		if (!lis && !lds && last != -1)//一个序列的第二个数,判断该lis还是lds
		{
			if (last == a[i]) continue;//相等的话还看不出来
			else if (last > a[i]) lds = true;//不上升
			else if (last < a[i]) lis = true;//不下降
			last = a[i];
		}
		else if (lis)//不下降 
		{
			if (a[i] >= last) last = a[i];//满足 
			else last = -1,lis = false,--i;//不满足,重置序列 
			continue;
		}
		else if (lds)//不上升 
		{
			if (a[i] <= last) last = a[i];//满足
			else last = -1,lds = false,--i;//不满足,重置序列 
		}
	}
	print(ans);
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 99999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl
#define Vecpr(K,L1,L2,N) vector<pair<L1,L2>> K(N)
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,R) vector<vector<L>> K(N, vector<L>(M,R))
#define pint pair<int,int>
#define Lower(v,X) lower_bound(v.begin(),v.end(),X)-v.begin();
#define mod 1000000007
#define MAX 5100000
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
   lli A,B,C,L,R,N,M,K,X=0,Y=0,W,H=INF,sum=0,num=0,flag=0;string S,T,O;
   cin >> N;
   Vec(P,lli,N,0);
   Vec(Q,lli,0,0);
   rep(i,0,N)cin >> P[i];
   Sort(P);
   rep(i,1,N){
      if(P[i]==P[i-1]){
         Q.pb(P[i]);
         i++;
      }
   }
   if(Q.empty())sum=0;
   else{
      Sort(Q);Rev(Q);
      sum=Q[0]*Q[1];
   }
   Out(sum);
}

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

long long N,W;
vector<long long> w(110),v(110);
long long rec[110][100009];

long long dp(long long n,long long x){
  if(n==1){
    if(x>=w[1]){return v[1];}
    else{return 0;}
  }
  else{   
    if(x<w[n]){
      if(rec[n-1][x]==-1){rec[n-1][x]=dp(n-1,x);}
      return rec[n-1][x];}
    else{
      if(rec[n-1][x]==-1){rec[n-1][x]=dp(n-1,x);}
      if(rec[n-1][x-w[n]]==-1){rec[n-1][x-w[n]]=dp(n-1,x-w[n]);}
      return max(rec[n-1][x],rec[n-1][x-w[n]]+v[n]);}
  }
}  
    
int main(){
  cin >> N >> W;
  for(int i=1;i<=N;i++){cin >> w[i] >> v[i];}
  for(int i=1;i<=N;i++){
    for(int j=1;j<=W;j++){rec[i][j]=-1;}
  }
  cout << dp(N,W) << endl;
}

Measured memory_bytes: 79360
r,c = map(int,input().split())
i = 1
tb1 = [[0 for i in range(c+1)] for j in range(r+1)]
while i <= r:
    C = list(map(int,input().split()))
    for j in range(c):
        tb1[i-1][j] = C[j] 
    tb1[i-1][c] = sum(C) 
    i+=1
for i in range(c+1):
    tb1[r][i] = sum([row[i] for row in tb1])

for i in range(r+1):
    for j in range(c+1):
        if j == c:
            print(f"{tb1[i][j]}",end="")
        else:
            print(f"{tb1[i][j]} ",end="")
    print()



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

int main(void){
  long X, K, D, A;
  scanf("%ld %ld %ld",&X, &K, &D);
  if(X < 0) X = -X;
  //正の側で出来るだけ原点に近づくように移動した時の移動回数が、
  //Kを上回るかどうかで場合分け
  if(K >= X / D){
    K = K - X / D;
    X = X - (X / D) * D;
  }
  else{
    X = X - K * D;
    K = 0;
  }
  //移動後に残った移動回数Kが偶数か奇数かで場合分け
  if( K % 2 == 0) A = labs(X);
  else A = labs(X - D);
  printf("%ld",A);
  return 0;
}

Measured memory_bytes: 1700
package main
 
import (
    "bufio"
    "fmt"
    "os"
    "strconv"
    "math"
)

func main(){
    
    N := nextInt()
    K := nextInt()
    h := nextInts(N)
    
    dp := make([]int, N)
    for i:=0;i<N;i++ {
        dp[i] = math.MaxInt32
    }
    dp[0] = 0
    
    for i:=1;i<N;i++ {
        for j:=i-K;j<=i;j++ {
            if j < 0 {
                continue
            }
            dp[i] = Min([]int{dp[i], dp[j] + Abs(h[i] - h[j])});
        }
    }
    
	fmt.Println(dp[N-1])
}

/* templates */


func Max(a []int) int {
    r := a[0]
    for i := 0; i < len(a); i++ {
        if r < a[i] {
            r = a[i]
        }
    }
    return r
}
 
func Min(a []int) int {
    r := a[0]
    for i := 0; i < len(a); i++ {
        if r > a[i] {
            r = a[i]
        }
    }
    return r
}
 
func Sum(a []int) (r int) {
    for i := range a {
        r += a[i]
    }
    return r
}
 
func Abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
 
type Pair struct {
    a, b int
}
 
type Pairs []Pair
 
func (p Pairs) Len() int {
    return len(p)
}
 
func (p Pairs) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}
 
func (p Pairs) Less(i, j int) bool {
    return p[i].b < p[j].b
}
 
var nextReader func() string
 
func init() {
    nextReader = NewScanner()
}
 
func NewScanner() func() string {
    r := bufio.NewScanner(os.Stdin)
    r.Buffer(make([]byte, 1024), int(1e+11))
    r.Split(bufio.ScanWords)
    return func() string {
        r.Scan()
        return r.Text()
    }
}

func nextString() string {
    return nextReader()
}
 
func nextInt64() int64 {
    v, _ := strconv.ParseInt(nextReader(), 10, 64)
    return v
}
 
func nextInt() int {
    v, _ := strconv.Atoi(nextReader())
    return v
}
 
func nextInts(n int) []int {
    r := make([]int, n)
    for i := 0; i < n; i++ {
        r[i] = nextInt()
    }
    return r
}

func nextStrings(n int) []string {
    r := make([]string, n)
    for i := 0; i < n; i++ {
        r[i] = nextString()
    }
    return r
}

func nextFloat64() float64 {
    f, _ := strconv.ParseFloat(nextReader(), 64)
    return f
}


Measured memory_bytes: 2816
#include <iostream>
#include <vector>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i = 0 ; i < n ; i++)
using namespace std;
double p[100],w[100];
int id[100];
int to[100];

int memo[101][101];
int nCr(int n,int r){
	if(n == 0 && r == 0) return 1;
	else if(r < 0 || n < r) return 0;
	if(memo[n][r])return memo[n][r];
	return memo[n][r] = ( nCr(n-1,r-1) + nCr(n-1,r) ) % 100000007;
}	

int main(){
	int n;
	while(cin >> n && n){
		rep(i,n){
			cin >> p[i] >> id[i] >> w[i];
			to[id[i]] = i;
		}
		double ans = 0;
		long long ptn = 1;

		int r = n;
		bool done[100] = {0};
		
		vector< vector<int> > v;
		for(int i = 0 ; i < n ; i++){
			if(!done[i]){
				vector<int> h;
				h.push_back(i);
				done[i] = 1;
				int c = to[i];
				while(!done[c]){
					done[c] = 1;
					h.push_back(c);
					c = to[c];
				}
				v.push_back(h);
			}
		}
		rep(i,v.size()){
			vector<double> get(v[i].size());
			rep(j,v[i].size()){
				//long long start = 1 , sz = 1;
				get[j] += 1.0 / p[v[i][j]];
				int c = to[v[i][j]];
				rep(k,v[i].size()-1){
					get[j] += 1.0 / w[c];
					c = to[c];
				}
			}
			double mini = *min_element(get.begin(),get.end());
			long long start = 0 , sz = v[i].size();
			rep(j,v[i].size())if(get[j] <= mini + 1e-10)start++;
			ptn = (ptn*nCr(r,sz))%100000007;
			ptn = (ptn*start)%100000007;
			ans += mini;
			r -= sz;
		}
		
		printf("%.10f %d\n",ans,(int)ptn);
	}
}

Measured memory_bytes: 1016
let s = stdin.ReadLine()
let f = int s.[0..1]
let b = int s.[2..3]
let isM x = x > 0 && x < 13

if isM f && isM b then "AMBIGUOUS"
elif isM f then "MMYY"
elif isM b then "YYMM"
else "NA"
|> printfn "%s"


Measured memory_bytes: 13916
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
using namespace std;

#define rep(i,a,n) for(int (i)=(a); (i)<(n); (i)++)
#define repq(i,a,n) for(int (i)=(a); (i)<=(n); (i)++)
#define repr(i,a,n) for(int (i)=(a); (i)>=(n); (i)--)
#define all(v) begin(v), end(v)
#define pb(a) push_back(a)
#define fr first
#define sc second
#define INF 2000000000
#define int long long int

#define X real()
#define Y imag()
#define EPS (1e-10)
#define EQ(a,b) (abs((a) - (b)) < EPS)
#define EQV(a,b) ( EQ((a).X, (b).X) && EQ((a).Y, (b).Y) )
#define LE(n, m) ((n) < (m) + EPS)
#define LEQ(n, m) ((n) <= (m) + EPS)
#define GE(n, m) ((n) + EPS > (m))
#define GEQ(n, m) ((n) + EPS >= (m))

typedef vector<int> VI;
typedef vector<VI> MAT;
typedef pair<int, int> pii;
typedef long long ll;

typedef complex<double> P;
typedef pair<P, P> L;
typedef pair<P, double> C;

int const MOD = 1000000007;
ll mod_pow(ll x, ll n) {return (!n)?1:(mod_pow((x*x)%MOD,n/2)*((n&1)?x:1))%MOD;}
int madd(int a, int b) {return (a + b) % MOD;}
int msub(int a, int b) {return (a - b + MOD) % MOD;}
int mmul(int a, int b) {return (a * b) % MOD;}
int minv(int a) {return mod_pow(a, MOD-2);}
int mdiv(int a, int b) {return mmul(a, minv(b));}

namespace std {
    bool operator<(const P& a, const P& b) {
        return a.X != b.X ? a.X < b.X : a.Y < b.Y;
    }
}

int dp[301][301][301];

// i, x, l
int infomi[301][4], infoma[301][4];
int n, m;
int di[] = {1, 0, 0}, dj[] = {0, 1, 0}, dk[] = {0, 0, 1};
void chadd(int &a, int b) {a = madd(a, b);}

signed main() {
    cin >> n >> m;
    repq(i,0,n) rep(j,0,4) {
        infomi[i][j] = INF;
        infoma[i][j] = -1;
    }
    rep(i,0,m) {
        int l, r, x; cin >> l >> r >> x;
        infomi[r][x] = min(infomi[r][x], l);
        infoma[r][x] = max(infoma[r][x], l);
    }

    dp[0][0][0] = 1;
    int ans = 0;
    rep(i,0,n) rep(j,0,n) rep(k,0,n) {
        rep(s,0,3) {
            int z = max({i, j, k}) + 1;
            int ni = z*di[s] + (di[s]^1) * i;
            int nj = z*dj[s] + (dj[s]^1) * j;
            int nk = z*dk[s] + (dk[s]^1) * k;
            int x, y;
            if(ni == z) x = min(nj, nk), y = max(nj, nk);
            if(nj == z) x = min(ni, nk), y = max(ni, nk);
            if(nk == z) x = min(ni, nj), y = max(ni, nj);

            bool ok = true;
            if(infoma[z][3] > x) ok = false;
            if(infomi[z][2] <= x) ok = false;
            if(infoma[z][2] > y) ok = false;
            if(infomi[z][1] <= y) ok = false;
            if(ok) {
                if(z == n) chadd(ans, dp[i][j][k]);
                chadd(dp[ni][nj][nk], dp[i][j][k]);
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 213376
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 1e9 + 7;
const ll inf = (1 << 30) - 1;
const ll infll = (1LL << 61) - 1;

int N, K, ans;

template <typename T>
void print(vector<T> vec)
{
    int n = vec.size();
    for (int i = 0; i < n; i++)
    {
        cout << vec[i] << (i == n - 1 ? "\n" : " ");
    }
}

int main()
{
    while (cin >> N >> K)
    {
        if (N == 0 && K == 0)
            return 0;
        ans = 0;
        vector<int> v(N);
        vector<int> a;
        bool zero = false;
        for (int i = 0; i < K; i++)
        {
            int p;
            cin >> p;
            if (p == 0)
                zero = true;
            else
            {
                p--;
                a.push_back(p);
            }
        }

        sort(a.begin(), a.end());

        K = a.size();

        for (int i = 0; i < K; i++)
        {
            v[a[i]]++;
        }

        for (int i = 1; i < N; i++)
        {
            if (v[i] != 0)
                v[i] += v[i - 1];
            ans = max(v[i], ans);
        }

        for (int i = N - 2; i >= 0; i--)
        {
            if (v[i] != 0 && v[i + 1] != 0)
                v[i] = v[i + 1];
        }

        if (v[0] == 0)
            ans = max(ans, v[1] + 1);

        for (int i = 1; zero == true && i + 1 < N; i++)
        {
            if (v[i] == 0)
                ans = max(ans, v[i - 1] + v[i + 1] + 1);
        }

        cout << ans << endl;
    }
}


Measured memory_bytes: 3832
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define ll long long
#define fr(i,k,N) for(ll i=k; i<N;i++)
#define rep(i,N) for(ll i=0; i<N;i++)
#define alll(v) v.begin(),v.end()
using namespace std;
template <class X> void pr(X test){cout<<test<<endl;}
template <class X> void prr(X test){for(auto it:test){cout<<it<<endl;}cout<<endl;}
vector<ll> divv(ll n);

int main() {
    ll n,k;
    string s;
    cin>>n;
    ll u,v,w;
    unordered_map<ll, vector<pair<ll,ll>>> m;
    vector<ll> ans(n+1, -1);
    rep(i, n -1) {
        cin>>u>>v>>w;
        m[u].push_back(make_pair(v, w));
        m[v].push_back(make_pair(u, w));
    }
    queue<ll> q;
    q.push(u);
    ans[u] = 0;
    while(!q.empty()){
        auto start = q.front();
        q.pop();
        for(auto it:m[start]){
            if(ans[it.first] == -1) {
                if(it.second %2 == 0) ans[it.first] = ans[start];
                else ans[it.first] = (ans[start] +1 ) % 2;
                q.push(it.first);
            }
        }
    }
    vector<ll> g;
    rep(i, n) g.push_back(ans[i+1]);
    prr(g);


    return 0;
}

// return sorted 約数s 1 <= x <= n
vector<ll> divv(ll n) {
  vector<ll> v;
  for(ll i = 1; i*i <= n; i++) {
    if(n%i == 0) {
      v.push_back(i);
      if(i*i != n) v.push_back(n/i);
    }
  }
  sort(alll(v));
  return v;
}

class UF { // union find from https://github.com/kartikkukreja/blog-codes (MIT)
    // [usage]
    // auto uf = new UF(n);
    // uf->merge(a, b);
    // ...
public:
    int *id; // inner id
    int cnt; // number of all vartices
    int *sz; // sz[i] means size of i's set
    UF(int N)   {
        cnt = N;
        id = new int[N];
        sz = new int[N];
        for(int i=0; i<N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }
    ~UF() {
        delete [] id;
        delete [] sz;
    }
    int find(int p) {
        int root = p;
        while (root != id[root]) root = id[root];
        while (p != root) {
            int newp = id[p];
            id[p] = root;
            p = newp;
        }
        return root;
    }
    void merge(int x, int y) {
        int i = find(x);
        int j = find(y);
        if (i == j) return;
        
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        } else {
            id[j] = i;
            sz[i] += sz[j];
        }
        cnt--;
    }
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    int count() {
        return cnt;
    }
};

Measured memory_bytes: 15516
while True:
  a, op, b = map(str, input().split())
  a, b = int(a), int(b)
  if op == "?": break
  if op == "+": print(int(a + b))
  if op == "-": print(int(a - b))
  if op == "*": print(int(a * b))
  if op == "/": print(int(a / b))
  


Measured memory_bytes: 5600
// AOJ 2783 Parentheses
// 2018.2.2 bal4u

#include <stdio.h>
#include <string.h>

char s[50000];

int main()
{
	long long A, lo, hi, mi;

	scanf("%lld", &A);
	lo = 0, hi = A+1;
	while (hi - lo > 1) {
		mi = (lo + hi) >> 1;
		if ((mi*(mi+1)>>1) <= A) lo = mi; else hi = mi;
	}
	A -= lo*(lo+1) >> 1;

	if (A) {
		memset(s, ')', lo+2), s[lo+2] = 0;
		if (A < lo+2) s[A] = '(', A = -1;
		else A -= lo+2;
		printf(s);

		memset(s, '(', lo), s[lo] = 0;
		if (A >= 0) s[A] = '(';
		puts(s);
	} else {
		memset(s, ')', lo), s[lo] = 0; printf(s);
		memset(s, '(', lo); puts(s);
	}
	return 0;
}


Measured memory_bytes: 2080
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
using Graph = vector<vector<ll>>;

using namespace std;

map<ll,ll> primes;

/*
 * 計算クラス
 */
class Calc
{
    // 宣言
    ll a;

    public:
        // 素因数分解
        void decompositPrime(ll a);
};

/*
 * 素因数分解
 */
void Calc::decompositPrime(ll n)
{
    // 割る数の初期値
    a = 2;
    // √n ≧ a ( n ≧ a * a ) の間ループ処理
    while (n >= a * a) {
        // a で割り切れたら、a は素因数
        // そして、割られる数を a で割る
        // a で割り切れなかったら、 a を 1 増加させる
        if (n % a == 0) {
            primes[a]++;
            n /= a;
        } else {
            a++;
        }
    }
    // 最後に残った n は素因数
    primes[n]++;
}

/*
 * メイン処理
 */
int main()
{
    ll ans = 0;
    ll  iNum;

    
        // 計算クラスインスタンス化
        Calc objCalc;

            cin  >> iNum;
            if (iNum == 1)
            {
              cout << 0 << endl;
              return 0;
            }
            // 素因数分解
            objCalc.decompositPrime(iNum);
        
    ll cnt;
    for (auto && i : primes) {
      cnt = 1;
      //cout << i.first << ": " << i.second << endl;
      while (i.second - cnt >= 0) {
         i.second-=cnt;
         cnt++;
         ans++;
      }
      cnt = 1;
    }

    cout << ans << endl;

    // 正常終了
    return 0;
}

Measured memory_bytes: 3640
n = int(input())
s = input()
ans = 0
for i in range(1,n):
    #a = s[::]
    l,r = list(set(s[:i])),list(set(s[i:]))
    #print(l,r)
    tmp = 0
    if len(l)>len(r):
        for c in r:
            if c in l:  tmp += 1
        ans = max(ans,tmp)
    else:
        for c in l:
            if c in r:  tmp += 1
        ans = max(ans,tmp)
print(ans)


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

int main() {
  string s;
  cin >> s;
  
  string ans = "No";
  for (int i = 0; i <s.size(); i++) {
    if (s.at(i) == '9') {
      ans = "Yes";
    }
  }
  cout << ans << endl;
}
  

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

#define all(x) begin(x), end(x)

using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using f64 = double;
using p64 = pair<i64, i64>;

constexpr i64 INF = INT_FAST64_MAX / 2;

void solve() {
    i64 n, k;
    cin >> n >> k;
    vector<i64> a(n);
    for (auto& e : a) cin >> e;

    vector<i64> dp(k + 1);
    for (i64 i = 0; i <= k; i++) {
        for (auto& e : a) {
            if (i >= e) dp[i] |= !dp[i - e];
        }
    }

    cout << (dp[k] ? "First" : "Second") << endl;
}

int main() {
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
}


Measured memory_bytes: 3992
#pragma GCC target("avx")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <cctype>
#include <cerrno>
#include <cfloat>
#include <ciso646>
#include <climits>
#include <clocale>
#include <cmath>
#include <csetjmp>
#include <csignal>
#include <cstdarg>
#include <cstddef>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <regex>
#define rep(i,n) for(int i = 0; i < n; i++)
#define reps(i,j,n) for(int i = j; i < n; i++)
#define rrep(i,j,n) for(int i = j-1; i >= n; i--)
#define prec(n) fixed << setprecision(n)
#define print_array(v) rep(__k, v.size()) { cout << v[__k]; if(__k != v.size()-1) cout << " "; else cout << endl; }
#define YesorNo(a) printf(a?"Yes\n":"No\n")
#define fi first
#define se second
#define endl "\n"
using namespace std;

constexpr int inf = 2147483647;
constexpr int64_t inf64 = 9223372036854775807;
constexpr int mod = 1e9+7;

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

  int n, k;
  cin >> n >> k;
  vector<bool> ng(10, false);
  rep(i,k) {
    int d;
    cin >> d;
    ng[d] = true;
  }

  while (true) {
    string res = to_string(n);
    bool ok = true;
    rep(i,res.size()) {
      if(ng[res[i]-'0']) ok = false;
    }
    if(ok) {
      cout << res << endl;
      return 0;
    }
    n++;
  }
  return 0;
}

Measured memory_bytes: 256
/*****************************************************

@author: vichitr
Compiled On: 1st Sept 2019

*****************************************************/
#include<bits/stdc++.h>
#define MAX 9223372036854775807
#define endl "\n"
#define ll long long
#define int long long
#define double long double
#define pb push_back
#define pf pop_front
#define mp make_pair
#define ip pair<int, int>

#define loop(i,n) for(int i=0;i<n;i++)
#define loops(i,s,n) for(int i=s;i<=n;i++)
#define fast ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL)
using namespace std;

const ll MOD = 1009;
const ll SZ = 107;
const ll N = 5e5+7;

ll pwr(ll x, ll y)
{
    ll r = 1LL;
    while(y)
    {
        if(y&1)
            r = (r * x) % MOD;
        y >>= 1;
        x = (x * x) % MOD;
    }
    return r;
}

int inv(int x)
{
	return pwr(x, MOD-2ll);
}

int n, m; 

void solve()
{
	cin>>n;
	cout<<n*(n-1)/2;
	
}

signed main()
{
    fast;
    int t=1;
    // cin >>t;
    while(t--){
        solve();
        
    }
    return 0;
}

/*****************************


****************************/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;
const int INF=1000000000;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};

int main(){
    int n,q;
    cin >> n >> q;
    vector<LL> a(n),x(q);
    LL sum=0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum+=a[i];
    }
    for (int i = 0; i < q; i++) {
        cin >> x[i];
    }
    int k=n/2;
    int r=k+1;
    vector<LL> p;
    for (int r = k; r < n-1; r++) {
        int l=n-(r+1);
        p.pb(a[r-l]+(a[r]-a[r-l])/2+1);
    }
    vector<LL> ss(n+1,0);
    for (int i = 0; i < n; i++) {
        ss[i+1]=ss[i]+a[i];
    }
    vector<LL> sc(n+1,0),sk(n+1,0);
    int t=0; 
    for (int i = 0; i < n; i+=2) {
        sc[t+1]=sc[t]+a[i];
        t++;
    }
    t=0;
    for (int i = 1; i < n; i+=2){
        sk[t+1]=sk[t]+a[i];
        t++;
    }
    for (int i = 0; i < q; i++) {
        int s=upper_bound(ALL(p),x[i])-p.begin();
        LL ans=0;
        ans+=ss[n]-ss[n-(n+1)/2+s];
        if(n%2) ans+=sc[s];
        else ans+=sk[s];
        cout << ans << endl;
    }
    return 0;
}



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

int main(){
  int N, Y;
  cin >>N >>Y;
  
  int x=-1, y=-1, z=-1;
  bool flag = false;
  for (int i=N; i>-1; i--){
    for (int j=(N-i); j>-1; j--){
      if (Y == (10000*i + 5000*j + 1000*(N-i-j) )){
        x = i;
        y = j;
        z = (N-i-j);
        flag =true;
        //cout <<i <<" " <<j <<" " <<N-i-j <<endl;
        //break;
      }
      if(flag) break;
    }
    if(flag) break;
  }
  cout <<x <<" " <<y <<" " <<z <<endl;
    
}

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

const int N = 10005;
const int Q = 505;
int S[N];
int T[Q];

int main() {
    int n, q;
    cin >> n;
    for ( int i = 0; i < n; i++ ) {
        cin >> S[i];
    }
    cin >> q;
    for ( int i = 0; i < q; i++ ) {
        cin >> T[i];
    }
    
    int C = 0;
    for ( int i = 0; i < q; i++ ) {
        S[n] = T[i];
        int j = 0;
        while ( S[j] != S[n] ) {
            j++;
        } 
        if ( j != n ) {
            C++;
        }
    }
    
    cout << C << endl;
    
    return 0;
}

Measured memory_bytes: 3088
using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;
using System.Text.RegularExpressions;
 
class Program
{
    static void Main(){
        string pattern = @"^(dream|dreamer|erase|eraser)+$";
        Console.WriteLine(Regex.IsMatch(Console.ReadLine(), pattern) ? "YES" : "NO");
    }
}


Measured memory_bytes: 8056
from collections import deque
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
tree = [[] for i in range(N + 1)]
for i in range(N - 1):
    a, b = map(int, input().split())
    tree[a].append([a, b])
    tree[b].append([b, a])
val = [0] * (N + 1)
for i in range(Q):
    p, x = map(int, input().split())
    val[p] += x
ans = [-1] * (N + 1)
ans[1] = val[1]
bfs = deque(tree[1])
while bfs:
    p,n = bfs.popleft()
    if ans[n] == -1:
        ans[n] = val[n]+ans[p]
        for i in tree[n]:
            bfs.append(i)
print(' '.join(list(map(str,ans[1:]))))


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

ans = 0
for i in range(1, N+1):
    d1 = i % 10
    d1 += (i % 100) // 10
    d1 += (i % 1000) // 100
    d1 += (i % 10000) // 1000
    d1 += (i % 100000) // 10000
    if A <= d1 <= B:
        ans += i

print(ans)


Measured memory_bytes: 3060
#include<stdio.h>
int main()
{
	int a,b,c;
	int d;
	scanf("%d %d %d",&a,&b,&c);
	d=c-b;
	if(d%2==0)
	{
		printf("Alice");
	}
	else
	{
		printf("Borys");
	}
	return 0;
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    string S;
    cin >> S;

    ll N = stoi(S);

    ll f = 0;

    REP(i, S.length()){
        f += S[i]-'0';
    }

    // cout << N << " " << f << endl;
    if(N % f == 0){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}

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

signed main() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    };
    vector<int> c(n);
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    };
    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (v[i] > c[i]) {
            ans += v[i] - c[i];
        };
    };
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define SZ(x) (int)(x.size())
#define REP(i, n) for(int i=0;i<(n);++i)
#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define RREP(i, n) for(int i=(int)(n)-1;i>=0;--i)
#define RFOR(i, a, b) for(int i=(int)(b)-1;i>=(a);--i)
#define ALL(a) a.begin(),a.end()
#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<< endl;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using P = pair<int, int>;
const double eps = 1e-8;
const ll MOD = 1000000007;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
template <typename T1, typename T2>
bool chmax(T1 &a, const T2 &b) {
    if (a < b) { a = b; return true; }
    return false;
}
template <typename T1, typename T2>
bool chmin(T1 &a, const T2 &b) {
    if (a > b) { a = b; return true; }
    return false;
}
template<typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    os << "[";
    REP(i, SZ(v)) {
        if (i) os << ", ";
        os << v[i];
    }
    return os << "]";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const map<T1, T2> &mp) {
    os << "{";
    int a = 0;
    for (auto &tp : mp) {
        if (a) os << ", "; a = 1;
        os << tp;
    }
    return os << "}";
}
template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << p.first << ":" << p.second;
    return os;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);

    for (;;) {
        int n; cin >> n;
        if (n == 0) break;
        vi a(n);
        REP(i, n) cin >> a[i];
        int s = accumulate(ALL(a), 0);
        int ans = 0;
        REP(i, n) {
            ans += a[i] * n <= s;
        }
        cout << ans << endl;
    }

    return 0;
}



Measured memory_bytes: 3172
#coding:utf-8
#16D8101012J Ito Jun dj Python3

class UnionFind:
    def __init__(self,n):
        self.parent=[i for i in range(n+1)]
        self.rank=[0]*(n+1)
    def find(self,x):
        if self.parent[x] == x: # if x is x`s root
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def is_same_tree(self,x,y):
        return self.find(x) == self.find(y) 
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
        if self.rank[x] == self.rank[y]:
            self.rank[x] += 1
        
def main():
    n=list(map(int,input().split()))
    union=UnionFind(n[0])
    friends=[]
    question=[]
    for i in range(n[1]):
        a=tuple(map(int,input().split()))
        friends.append(a)
    for i in friends:
        union.union(i[0],i[1])
    m=int(input())
    for i in range(m):
        b=tuple(map(int,input().split()))
        question.append(b)
    for i in question:
        if union.find(i[0]) == union.find(i[1]):
            print("yes")
        else:
            print("no")
if __name__ == "__main__":
    main()


Measured memory_bytes: 24988
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
using System.IO;

class Program
{
    static void Main(string[] args)
    {
        long[] values = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
        long N = values[0];
        long A = values[1];
        long B = values[2];
        long[] X = Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
        long a = 0;
        long b = N - 1;
        for (int i = 1; i < N; ++i)
        {
            if ((X[i] - X[i - 1]) * A < B)
            {
                a += X[i] - X[i - 1];
                --b;
            }
        }
        Console.WriteLine(a * A + b * B);
    }
}


Measured memory_bytes: 12504
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
const ll MOD=1e9 + 7 ;
const ll dx[4] = { -1,1,0,0 };
const ll dy[4] = { 0,0,-1,1 };
const ll MAX =  4e3 + 30 ;
#define pb push_back
#define f first
#define s second
#define all(v) v.begin(),v.end()
ll n , x ;
map < ll , ll > odd , even;
vector < pair < ll , ll > > od , ev;
int main(){

    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n ;

    for(int i = 0 ; i < n ; ++i){
        cin >> x ;
        if(i&1)
            odd[x]++;
        else
            even[x]++;
    }
    ll ans = 0  , maxi = 0 , acc = 0;

    for(auto u : odd)
        od.pb({u.second,u.first});



    for(auto v : even)
        ev.pb({v.second , v.first});


    sort(all(od));
    sort(all(ev));
    reverse(all(od));
    reverse(all(ev));

    if(od[0].s == ev[0].s){
        if((int)od.size() == 1 && (int)ev.size()==1)
            return cout << n/2 << '\n' , 0;

        if((int)od.size() == 1)
            return cout << n - (int)ev[1].f << '\n' , 0;

         if((int)ev.size() == 1)
            return cout << n - (int)od[1].f << '\n' , 0;

        if((ev[0].f + od[1].f) > (od[0].f + ev[1].f))
            cout << n - (ev[0].f + od[1].f) << '\n';
        else
            cout << n - (od[0].f + ev[1].f) << '\n';

    return 0;
    }

    cout << n - od[0].f - ev[0].f << '\n';
    return 0;
}


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

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

            // 整数の入力
            long X = long.Parse(Console.ReadLine());
            long yokin = 100;
            long result = 0;

            while(yokin < X)
            {
                result++;
                yokin += yokin / 100;
            }

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 27380
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <math.h>
#include <bitset>
#include <queue>
#include <set>
#include <iomanip>
#include <math.h>
#include <assert.h>
// #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
constexpr long long int INFLL = 1001001001001001LL;
constexpr long long int infll = 1001001001001001LL;
constexpr int INF = 1000000007;
constexpr int inf = 1000000007;
const int mod = 1000000007;

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

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

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

inline double nCr(const int n, int r)
{
    if (n == 0)
    {
        return 0;
    }
    if (r == 0)
    {
        return 1;
    }
    if (r == 1)
    {
        return n;
    }
    if (n == r)
    {
        return 1;
    }

    if (r > n / 2)
    {
        r = n / 2;
    }

    double result = 1;
    for (double i = 1; i <= r; i++)
    {
        result *= (n - i + 1) / i;
    }

    return (result);
}

template <typename T>
T seinomi(T a)
{
    if (a > 0)
    {
        return a;
    }
    else
    {
        return 0;
    }
}

template <typename T>
map<T, T> soinsuubunkai(T n) //連想配列[素因数f.first][個数f.second]
{
    map<T, T> ret;
    for (T i = 2; i * i <= n; i++)
    {
        while (n % i == 0)
        {
            ret[i]++;
            n /= i;
        }
    }
    if (n != 1)
        ret[n] = 1;
    return ret;
}

template <typename T>
T ketasuu(T num)
{
    return std::to_string(num).length();
}

int kaizyou(int k)
{
    int sum = 1;
    for (int i = 1; i <= k; ++i)
    {
        sum *= i;
    }
    return sum;
}

template <class ForwardIt, class T>
void iota(ForwardIt first, ForwardIt last, T value)
{
    while (first != last)
    {
        *first++ = value;
        ++value;
    }
}

//nの階乗を計算
int factorial(int n)
{
    int answer = 1;
    while (n > 1)
    {
        answer *= n;
        n--;
    }
    return answer;
}
int comb(int n, int r)
{
    return factorial(n) / (factorial(r) * factorial(n - r));
}

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0)
    {
        if (n & 1)
            res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//小数点以下10桁テンプレート（main関数内の最初に貼付け）
//std::cout << std::fixed << std::setprecision(10);

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

int main(){
ll a,b;
cin>>a>>b;
if(a>1&&b>1){
if(a>b){
    cout<<"Alice"<<endl;
}else if(a==b){
    cout<<"Draw"<<endl;
}else{
    cout<<"Bob"<<endl;
}
}else{
    if(a==1&&b==1){
        cout<<"Draw"<<endl;
    }else if(a==1){
        cout<<"Alice"<<endl;
    }else{
        cout<<"Bob"<<endl;
    }
}
}










Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
long long n, a, b, ans;

int main(){
	cin >> n >> a >> b;
	if((a+b) % 2){
		ans = min(n-b+1,a)+(b-a)/2;
	}else ans = (b-a) / 2;
	cout << ans << '\n';
}

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

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

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main() {
  long long X;
  cin >> X;

  long long m = 100;
  long long count = 0;
  while (m < X) {
    m += m / 100;
    count++;
  }

  cout << count << endl;

  return 0;
}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
using P = pair<int, int>;
using vec = vector<int>;
using mat = vector<vector<int>>;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(v) v.begin(), v.end()
#define endl "\n"

constexpr int MOD = 1000000007;
const int INF = 1 << 30;

int main() {
    lint n, m;
    cin >> n >> m;

    if (n >= 2 && m >= 2) cout << (n-2) * (m-2) << endl;
    else if (n >= 2) cout << n-2 << endl;
    else if (m >= 2) cout << m-2 << endl;
    else cout << 1 << endl;
    return 0;
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
const double PI = acos(-1.0);
#define MOD 1000000007LL
#define endl "\n"

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  srand((unsigned)time(NULL));
  ll N;
  cin >> N;
  N--;
  string ans = "";
  while(N >= 0){
    ll num = N % 26LL;
    ans = (char)('a' + num) + ans;
    if(N < 26) break;
    N /= 26LL;
    N--;
  }
  cout << ans << endl;
}


Measured memory_bytes: 3652
#include <bits/stdc++.h>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
  string S;
  cin >> S;
  if (S.size()==2) {
    cout << S << endl;
  }
  else {
    cout << S.at(2) << S.at(1) << S.at(0) << endl;
  }
}


Measured memory_bytes: 3600
#include<bits/stdc++.h>
using namespace std;
string s;
int ans;
int main()
{
	cin>>s;
	int len=s.size();
	if(len&1)
	{
		int mid=len/2;
		for(int i=1;mid-i>=0;i++)
		{
			if(s[mid+i]!=s[mid-i])
			ans++;
		}
	}
	else
	{
		for(int i=0;i<len/2;i++)
		{
			if(s[i]!=s[len-1-i])
			ans++;
		}
	}
	cout<<ans;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<pii,int> ppii;
typedef pair<int,pii> pipi;
typedef pair<ll,ll> pll;
typedef pair<pll,ll> ppll;
typedef pair<ll,pll> plpl;
typedef tuple<ll,ll,ll> tl;
ll mod=1000000007;
ll mod2=998244353;
ll mod3=1000003;
ll mod4=998244853;
ll inf=1000000000000000000;
double pi=acos(-1.0);
#define rep(i,m,n) for(ll i=m;i<n;i++)
#define rrep(i,n,m) for(ll i=n;i>=m;i--)
int dh[4]={1,-1,0,0};
int dw[4]={0,0,1,-1};
int ddh[8]={-1,-1,-1,0,0,1,1,1};
int ddw[8]={-1,0,1,-1,1,-1,0,1};
ll lmax(ll a,ll b){
    if(a<b)return b;
    else return a;
}
ll lmin(ll a,ll b){
    if(a<b)return a;
    else return b;
}
ll gcd(ll a,ll b){
    if(a<b)swap(a,b);
    if(b==0)return a;
    if(a%b==0)return b;
    return gcd(b,a%b);
}
ll Pow(ll n,ll k){
    ll ret=1;
    ll now=n;
    while(k>0){
        if(k&1)ret*=now;
        now*=now;
        k/=2;
    }
    return ret;
}
ll beki(ll n,ll k,ll md){
  ll ret=1;
  ll now=n;
  while(k>0){
    if(k%2==1){
      ret*=now;
      ret%=md;
    }
    now*=now;
    now%=md;
    k/=2;
  }
  return ret;
}
ll gyaku(ll n,ll md){
  return beki(n,md-2,md);
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    ll n;cin>>n;
    ll a[n];
    ll cnt[n+1];
    fill(cnt,cnt+n+1,0);
    rep(i,0,n){
        cin>>a[i];
        cnt[a[i]]++;
    }
    if(n%2==0){
        for(int i=1;i<=n;i+=2){
            if(cnt[i]!=2){
                cout<<0<<endl;
                return 0;
            }
        }
    }
    else{
        if(cnt[0]!=1){
            cout<<0<<endl;
            return 0;
        }
        for(int i=2;i<=n;i+=2){
            if(cnt[i]!=2){
                cout<<0<<endl;
                return 0;
            }
        }
    }
    ll ans=beki(2,n/2,mod);
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
#include<cstdio>
#include<queue>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const int INF=1e9;

int main(){
    string s;cin>>s;
    ll bg=0,sm=0;
    ll ans=0;
    for(int i=0;i<(int)s.size();i++){
        if(s[i]=='<') bg++;
        else sm++;

        if(i==(int)s.size()-1||(s[i]=='>'&&s[i+1]=='<')){
            ll M=max(bg,sm),m=min(bg,sm);
            ans+=M*(M+1)/2;
            ans+=m*(m-1)/2;
            bg=sm=0;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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

int main(){
  string S;
  cin >> S;
  if("SUN" == S){
    cout << 7 << endl;
  }
  if("MON" == S){
    cout << 6 << endl;
  }
  if("TUE" == S){
    cout << 5 << endl;
  }
  if("WED" == S){
    cout << 4 << endl;
  }
  if("THU" == S){
    cout << 3 << endl;
  }
  if("FRI" == S){
    cout << 2 << endl;
  }
  if("SAT" == S){
    cout << 1 << endl;
  }
}

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

int main()
{
	int L;
	cin >> L;
	string s, t;
	cin >> s >> t;
	if (s + t > t + s) swap(s, t);
	string tmp;
	while (L % s.size()) {
		tmp += t;
		L -= t.size();
	}
	for (int i = 0; i < (L / (int)s.size()); i++) {
		cout << s;
	}
	cout << tmp << endl;
	return 0;
}


Measured memory_bytes: 1544
//header{{{
#include<bits/stdc++.h>
  
using namespace std;
 
#define rep(i,n) for(int i=0;i<(n);++i)
#define reps(i,n) for(int i=1;i<=(n);++i)
#define all(x) (x).begin(),(x).end()
#define setout(n,x) setw(n+1) << setfill(x)
#define Fixed fixed << setprecision(10)
#define int int64_t
using pii = pair<int,int>;
constexpr int INF  = 0x3f3f3f3f;
constexpr long long LINF = 0x3f3f3f3f3f3f3f3fLL;
constexpr int mod = 1e9+7; 
constexpr int MOD = 998244353;

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

template <class T> using min_heap = priority_queue<T,vector<T>,greater<T> >;
template <class T> using max_heap = priority_queue<T>;
template <class A, class B> using umap = unordered_map<A,B>;
  
int gcd(int a,int b){ return b ? gcd(b,a % b) : a;}
int lcm(int a,int b){ return a / gcd(a,b) * b;}

constexpr int dx[] = {1,0,-1,0,1,1,-1,-1};
constexpr int dy[] = {0,-1,0,1,1,-1,-1,1};
//}}}
//UnionFind{{{
struct UnionFind {
    vector < int > par;
    vector < int > siz;
 
    UnionFind(int n): par(n), siz(n, 1) { //初期化
        for(int i = 0; i < n; i++) par[i] = i;
    }
 
    int root(int x){ //根の更新＋判定
        if(par[x] == x) return x;
        else return par[x] = root(par[x]);
    }
 
    int size(int x){ //サイズ
        return siz[root(x)];
    }
 
    bool same(int x, int y){ //グループの判定
        return root(x) == root(y);
    }
 
    bool unite(int x, int y){ //つなげる
        if((x=root(x))==(y=root(y))) return false;
        if( siz[y] > siz[x] ) swap(x,y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }
};
//}}}
signed main(){
	cin.tie(0);
	ios::sync_with_stdio(false);

    int h,w,cnt = 0,res = 0;
    cin >> h >> w;

    UnionFind uf(h*w);
    vector<vector<int> > num(h,vector<int>(w));
    vector<string> mas(h);
    vector<int> sum(h*w);

    rep(i,h){
        cin >> mas[i];
        rep(j,w){
            num[i][j] = cnt;
            ++cnt;
        }
    }

    auto inside = [&](int y,int x){
        return (y < h && x < w && y >= 0 && x >= 0);
    };

    rep(i,h){
        rep(j,w){
            rep(k,4){
                int ny = i + dy[k];
                int nx = j + dx[k];
                if(inside(ny,nx) && mas[i][j] != mas[ny][nx]){
                    uf.unite(num[i][j],num[ny][nx]);
                }
            }
        }
    }

    rep(i,h){
        rep(j,w){
            if(mas[i][j] == '#'){
                sum[uf.root(num[i][j])]++;
            }
        }
    }

    rep(i,h){
        rep(j,w){
            if(mas[i][j] == '#'){
                res += uf.size(num[i][j]) - sum[uf.root(num[i][j])];
            }else{
                res += sum[uf.root(num[i][j])];
            }
        }
    }

    cout << res / 2 << '\n';

	return 0;
}


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

int ri() {
	int n;
	scanf("%d", &n);
	return n;
}
int main() {
	int n = ri();
	int a[n];
	int64_t sum = 0;
	for (int i = 0; i < n; i++) a[i] = ri(), sum += a[i];
	int64_t dp[n + 1][n + 1][2];
	memset(dp, 0, sizeof(dp));
	for (int i = n; i >= 0; i--) for (int j = n; j >= 0; j--) if (i + j < n) {
		dp[i][j][0] = std::max(dp[i + 1][j][1] + a[i], dp[i][j + 1][1] + a[n - j - 1]);
		dp[i][j][1] = std::min(dp[i + 1][j][0], dp[i][j + 1][0]);
	}
	std::cout << sum - 2 * dp[0][0][1] << std::endl;
	return 0;
}


Measured memory_bytes: 140928