akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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;
}

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

int main() {
   int N, T;
   cin >> N >> T;
   ll t[N];
   ll ans = 0;
   ll tmpS = 0;
   ll tmpE = T;
   for (int i = 0; i < N; i++) {
      cin >> t[i];
      if (i == 0) continue;
      if (tmpE < t[i]) {
         ans += tmpE - tmpS;
         tmpS = t[i];
         tmpE = t[i] + T;
      } else {
         tmpE = t[i] + T;
      }
   }
   ans += tmpE - tmpS;
   cout << ans << endl;
   return 0;
}


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

using namespace std;

int main(){
	int n;
	scanf("%d", &n);
	long long arr[n];
	for(int i = 0; i < n; i++){
		scanf("%lld", &arr[i]);
	}	
	long long soma = 0;
	long long mini = 1e9 + 7;
	for(int i = 0; i < n - 1; i++){
		if(arr[i] < 0){
			arr[i] *= -1LL;
			arr[i + 1] *= -1LL;
		}
		mini = min(mini, arr[i]);
		soma += arr[i];
	}
	if(arr[n - 1] < 0LL){
		if((arr[n - 1] * -1LL) >= mini){
			soma -= (mini * 2);
			soma += -1LL * arr[n - 1];
		}else{
			soma += arr[n - 1];
		}
	}else{
		soma += arr[n - 1];
	}
	printf("%lld\n", soma);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
       
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

  vector<int> v(N), w(N);
  for (int i = 0; i < (int)(N); ++i) cin >> v[i] >> w[i];

  vector<int> dp(W + 1, 0);
  for (int i = 0; i < (int)(N); ++i) for (int j = 0; j < (int)(W + 1); ++j) if (j - w[i] >= 0) chmax(dp[j], dp[j - w[i]] + v[i]);
  cout << dp[W] << endl;

  return 0;
}



Measured memory_bytes: 3152
n = int(input())
n4 = int(n/4)
ans = 'No'
if n%4 == 0:
    ans = 'Yes'
else :
    for i in range(n4+1):
         res = n - 4 * i
         if res%7 == 0:
             ans = 'Yes'

print(ans)






Measured memory_bytes: 2940
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
  let stdin = stdin();
  let stdin = stdin.lock();
  let token: String = stdin
    .bytes()
    .map(|c| c.expect("failed to read char") as char)
    .skip_while(|c| c.is_whitespace())
    .take_while(|c| !c.is_whitespace())
    .collect();
  token.parse().ok().expect("failed to parse token")
}

fn main() {
  let a = read::<i32>();
  let b = read::<i32>();

  if b % a == 0 {
    println!("{}", a + b);

  } else {
    println!("{}", b - a);

  }
}



Measured memory_bytes: 4352
#include <iostream>
using namespace std;
int main(){
    int A,B,C,X;
    cin>>A>>B>>C>>X;
    int sum=0;
    for(int i=0;i<=A;i++){
        for(int j=0;j<=B;j++){
            for(int k=0;k<=C;k++){
               int tmp=i * 500 + j * 100 + k * 50;
               if(tmp==X)sum++;
            }
        }
    }
    cout<<sum<<endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <map>

using namespace std;

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    vector<vector<int>> vvi;
    vvi = vector<vector<int>>(3,vector<int>(3,0));
    for (int i = 0; i < 3; ++i)
    {
        for (int j = 0; j < 3; ++j)
        {
            cin >> vvi[i][j];
        }
    }
    for (int a = 0; a <= 100; ++a)
    {
        for (int b = 0; b <= 100; ++b)
        {
            for (int c = 0; c <= 100; ++c)
            {
                if(((vvi[0][0] - a) == (vvi[0][1] - b)) && ((vvi[0][1] - b) == (vvi[0][2] - c)))
                {   
                    if(((vvi[1][0] - a) == (vvi[1][1] - b)) && ((vvi[1][1] - b) == (vvi[1][2] - c)))
                    {
                        if(((vvi[2][0] - a) == (vvi[2][1] - b)) && ((vvi[2][1] - b) == (vvi[2][2] - c)))
                        {
                            cout <<  "Yes" << endl;
                            return 0;
                        }
                    }
                }
            }
        }
    }
    cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
/**
* Author: Luis Alberto Herrera Gomez
* Tags: 
*/

#include <algorithm>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> ii;
typedef vector<pair<int, pair<string, int>>> vii;

bool comparator(const pair<int, pair<string, int>>& a, const pair<int, pair<string, int>>& b)
{
    if (a.second.first != b.second.first)
        return a.second.first < b.second.first;
    return a.second.second > b.second.second;
}

int main()
{
    int N;

    cin >> N;

    vii v(N);
    string s;
    int p;
    for (int i = 0; i < N; ++i) {
        cin >> s >> p;
        v[i] = make_pair(i + 1, make_pair(s, p));
    }

    sort(v.begin(), v.end(), comparator);

    for (int i = 0; i < N; ++i)
        cout << v[i].first << "\n";

    return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int, P: "List[int]"):
    ans = [P[0]]
    
    for i in range(1, N):
        if P[i] < ans[-1]:
            ans.append(P[i])

    print(len(ans))

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, P)

if __name__ == '__main__':
    main()


Measured memory_bytes: 26496
from sys import stdin
# import math
import numpy as np
# N = int(stdin.readline().rstrip().split()[0])
# A = [int(x) for x in stdin.readline().rstrip().split()]
# N, X = [int(x) for x in stdin.readline().rstrip().split()]
# S = [int(x) for x in stdin.readline().rstrip().split()]
N = int(stdin.readline().rstrip().split()[0])
H = [int(x) for x in stdin.readline().rstrip().split()]
H = np.array(H)

ans = 0
for i in range(N):
  max_m = H[:i+1].max()
  if max_m==H[i]:
    ans += 1

print(ans)

Measured memory_bytes: 12440
N = int(input())

a = []
a.append(N)
for i in range(1, 1000000):
    if a[i - 1] % 2 == 0:
        a.append(int(a[i - 1] / 2))
    else:
        a.append(a[i - 1] * 3 + 1)

s = set()
for i in range(1000000):
    if a[i] in s:
        print(i + 1)
        break
    else:
        s.add(a[i])


Measured memory_bytes: 10968
import java.util.Scanner;

class Main{


	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);			//文字の入力

		String n = sc.next();
		int y = Integer.parseInt(n.substring(0,4));
		int m = Integer.parseInt(n.substring(5,7));
		int d = Integer.parseInt(n.substring(8));
	//	System.out.println(y + " " + m + " " + d);
		if(y >= 2019 && m > 4){
			System.out.println("TBD");
		}else{
			System.out.println("Heisei");

		}
	}
}



Measured memory_bytes: 21844
mod=10**9+7
N=int(input())
A = list(map(int,input().split()))
B=[0]*N
for i in range(N):
 B[i]=str(bin(A[i]))
f=0
for i in range(2,62):
 d=0
 e=0
 for j in range(N):
  g=62-len(B[j])
  if i<g:
   e+=1
  elif B[j][i-g]=="1":
   d+=1
  else:
   e+=1
 f+=(d*e*pow(2,61-i,mod))%mod
 f%=mod
print(f)


Measured memory_bytes: 132484
N, M, C = map(int, input().split())
B = list(map(int, input().split()))
A = [[] for i in range(N)]
for i in range(N):
    A[i] = list(map(int, input().split()))
count = 0
for i in range(len(A)):
    _sum = 0
    for j in range(len(B)):
        for k in range(len(A[i])):
            if j == k:
                _sum += B[j] * A[i][k]
    if _sum + C > 0:
        count += 1
print(count)

Measured memory_bytes: 3064
// In the name of god
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <ctime>
#include <queue>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <bitset>
#define sqr(a) ((a)*(a))
#define all(a) (a).begin(), (a).end()
using namespace std;
 
template <typename T>
T next_int() {
    T x = 0, p = 1;
    char ch;
    do { ch = getchar(); } while(ch <= ' ');
    if(ch == '-') {
        p = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    return p * x;
}
 
string next_token() {
    char ch;
    string ans = "";
    do { ch = getchar(); } while(ch <= ' ');
    while(ch > ' ') {
        ans += ch;
        ch = getchar();
    }
    return ans;
}
 
const long long INF = (long long)1e18;
const int INFINT = (int)1e9 + 227 + 1;
const int MAXN = (int)1e6 + 227 + 1;    
const int MOD = (int)1e9 + 7;
const long double EPS = 1e-9;
 
long long bin_pow(long long a, long long b) {
    if(!b) return 1;
    long long ans = bin_pow(a, b / 2);
    ans = ans * ans;
    if(b % 2) ans = ans * a;
    return ans;
}

long long dp[51][51];

int main() {
    // freopen(".in", "r", stdin);

    dp[0][0] = 1;
    for(int i = 0; i <= 50; i++) {
        for(int j = 0; j <= 50; j++) {
            if(i) {
                dp[i][j] += dp[i - 1][j];
                if(j) {
                    dp[i][j] += dp[i - 1][j - 1];
                }
            }
        }
    }

    int n, m; cin >> n >> m;

    int a[2] = {0, 0};
    for(int i = 0; i < n; i++) {
        a[next_int<int>() % 2]++;
    }

    long long ans = 0;
    if(m == 0) {
        for(int num = 0; num <= a[1]; num += 2) {
            ans += dp[a[1]][num] * bin_pow(2, a[0]);
        }
    } else {
        for(int num = 1; num <= a[1]; num += 2) {
            ans += dp[a[1]][num] * bin_pow(2, a[0]);
        }
    }

    cout << ans << "\n";
}


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

#define loop(i, a, b) for (int i = (a); i < (b); ++i)
#define rep(i, n) for (int i = 0; i < n; ++i)
#define dump(a) cerr << #a << " = " << (a) << "(L:" << __LINE__ << ")" << endl

// pair<long long, string>;
struct Node {
    long long cost;
    pair<string, string> sp;
    bool operator<(const Node& o) const { return cost < o.cost; }
    bool operator>(const Node& o) const { return cost > o.cost; }
    Node(long long cost, string sl, string sr) : cost(cost), sp(sl, sr) {}
};

bool is_kaibun(const string& s) {
    rep(i, s.size()) {
        if (s[i] != s[s.size() - 1 - i]) {
            return false;
        }
    }
    return true;
}

bool startswith(const string& s, const string& t) {
    return s.substr(0, t.size()) == t;
}

string reverse(const string& s) {
    auto t = s;
    reverse(t.begin(), t.end());
    return move(t);
}

void solve(long long N, std::vector<std::string> S, std::vector<long long> C) {
    long long ans = 1LL << 60;
    set<pair<string, string>> visit;
    priority_queue<Node, vector<Node>, greater<Node>> Q;
    rep(i, N) Q.emplace(C[i], S[i], "");
    while (!Q.empty()) {
        auto p = Q.top();
        Q.pop();
        if (visit.find(p.sp) != visit.end()) continue;
        visit.insert(p.sp);

        if (is_kaibun(p.sp.first + p.sp.second)) {
            ans = min(ans, p.cost);
        } else {
            if (p.sp.first.size() < p.sp.second.size()) {
                auto t = reverse(p.sp.second);
                rep(i, N) {
                    auto mn = min(S[i].size(), t.size());
                    bool ok = true;
                    rep(k, mn) {
                        if (S[i][k] != t[k]) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) {
                        Q.emplace(p.cost + C[i], S[i].substr(mn),
                                  reverse(t.substr(mn)));
                    }
                }
            } else {
                auto t = p.sp.first;
                rep(i, N) {
                    auto mn = min(S[i].size(), t.size());
                    auto s = reverse(S[i]);
                    bool ok = true;
                    rep(k, mn) {
                        if (s[k] != t[k]) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) {
                        Q.emplace(p.cost + C[i], t.substr(mn),
                                  reverse(s.substr(mn)));
                    }
                }
            }
        }
    }

    if (ans == 1LL << 60) ans = -1;
    cout << ans << endl;
}

int main() {
    long long N;
    scanf("%lld", &N);
    std::vector<std::string> S(N);
    std::vector<long long> C(N);
    for (int i = 0; i < N; i++) {
        std::cin >> S[i];
        scanf("%lld", &C[i]);
    }
    solve(N, std::move(S), std::move(C));
    return 0;
}


Measured memory_bytes: 3756
#include <iostream>
#include <vector>
#include <algorithm>
#define pi pair<int,int>

using namespace std;


class UnionFind{
 public:
	vector<int> parent;
	
	UnionFind(int N): parent(vector<int>(N,-1)){}
	
	int root(int A){
	 	if( parent[A] < 0) return A;
		return parent[A] = root(parent[A]);
	}

	int size(int A){
		return -parent[root(A)];
	}

	bool uni(int A,int B){
	        A = root(A);
		B = root(B);
		if( A == B) 
			return false;
		if(size(A) < size(B)) swap(A,B);
		parent[A] += parent[B];
		parent[B] = A;
		return true;
	}
};





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

	vector<pi> vec(m);	
	for(auto& i : vec)     {
                scanf("%d %d", &i.first, &i.second);
		i.first--;
		i.second--;
	}
		

	vector<long long> res(m);
	res[m - 1] = (long long)n * ( n - 1) / 2;
	//cout << res[m -1] << endl;
	UnionFind Uni(n);
	for(int i = m - 1; i > 0; i--){
		res[i-1] = res[i];
		if(Uni.root(vec[i].first) != Uni.root(vec[i].second))
		{
			res[i - 1] -= (long long) Uni.size(vec[i].first) * Uni.size(vec[i].second);
			Uni.uni(vec[i].first, vec[i].second); 
		}
	}
	
	for(auto& i : res)
		cout << i << endl;
	
	
	return 0;
}

Measured memory_bytes: 3328
import sys

# ?????????????§?????????¢????±??????????
def get_distance(pre_x, pre_y, x, y):
    if (x > pre_x and y > pre_y) or (x < pre_x and y < pre_y):
        # ????????????
        x_num = abs(x - pre_x)
        y_num = abs(y - pre_y)
        if x_num >= y_num:
            return x_num
        else:
            return y_num
    else:
        return abs(x - pre_x) + abs(y - pre_y)

line1 = sys.stdin.readline().strip().split(' ')
w, h, n = [int(i) for i in line1]
#print(w, h, n)

start_line = sys.stdin.readline().strip().split(' ')
pre_x = int(start_line[0])
pre_y = int(start_line[1])

nums = 0
for i in range(n-1):
    #print('pre:', pre_x, pre_y)
    next_line = sys.stdin.readline().strip().split(' ')
    x = int(next_line[0])
    y = int(next_line[1])
    #print('now:', x, y)
    # ?????¢????±???????
    nums += get_distance(pre_x, pre_y, x, y)

    pre_x = x
    pre_y = y

print(nums)

Measured memory_bytes: 7808
#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cctype>
using namespace std;
int main()
{
	int now=0,seat=0,tot=0;
	bool flag=0;
	char c;
	while((c=getchar())!=10)
	{
		(((c=='A')&&(!flag))?(seat=now,flag=1):((c=='Z')?(tot=(now-seat+1)):(tot=tot)));
		now++;
	}
	printf("%d",tot);
	putchar(10);
	return 0;
}

Measured memory_bytes: 256
import java.io.IOException;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);

        int count = 0;

        int x = sc.nextInt();
        int y = sc.nextInt();

        for(int i=x; i<=y; i++) {
        	String[] line = Integer.toString(i).split("");
        	if(line[0].equals(line[4]) && line[1].equals(line[3])) {
        		count++;
        	}
        }

        System.out.println(count);

        sc.close();
    }
}

Measured memory_bytes: 63996
import sys
sys.setrecursionlimit(10**9)
n,m,k=map(int,input().split())
friend=[[] for _ in range(n)]
block=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    friend[a].append(b)
    friend[b].append(a)
for _ in range(k):
    c,d=map(int,input().split())
    c-=1
    d-=1
    block[c].append(d)
    block[d].append(c)
seen=[-1]*n
def dfs(graph,v,top):
    seen[v]=top
    top_count[top]+=1
    for nv in graph[v]:
        if seen[nv]!=-1:
            continue
        dfs(graph,nv,top)
top=0
top_count=[0]
for v in range(n):
    count=0
    if seen[v]!=-1:
        continue
    dfs(friend,v,top)
    top_count.append(0)
    top+=1


for i in range(n):
    ans=top_count[seen[i]]-len(friend[i])-1
    cnt=0
    for v in block[i]:
        if seen[v]==seen[i]:
            cnt+=1
    ans-=cnt
    print(ans,end=' ')

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

int Q, acc[100100];

/*
・素数判定
  > O(√n)
[使用例] YES(isPrime(998244353));
*/

bool isPrime(ll n) {
  if (n < 2) return false;
  for (ll i = 2; i * i <= n; ++i) {
    if (n % i == 0) return false;
  }
  return true;
}

signed main() {

  cin >> Q;

  for (int i = 3; i <= 100000; i += 2) {
    acc[i - 1] = acc[i - 2];
    acc[i] = acc[i - 1];
    if (isPrime(i) && isPrime((i + 1) / 2)) acc[i]++;
  }

  while (Q--) {
    int l, r;
    cin >> l >> r;
    cout << acc[r] - acc[l - 1] << endl;
  }

}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  string s, t;
  cin >> s >> t;
  int ans = t.size();
  for(int i = 0; i <= s.size()-t.size(); i++){
    int cnt = 0;
  	for(int j = 0; j < t.size(); j++){
      if(s.at(i+j) != t.at(j)) cnt++;
    }
    if(cnt < ans) ans = cnt;
  }
  cout << ans << endl;
}

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

int main(){
  long long x;
  cin >> x;
  long long ans = 0;
  ans += x/11;
  ans *= 2;
  if (x % 11 > 6)
    ans += 2;
  else if (x % 11 > 0)
    ans += 1;
  cout << ans << endl;
}


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


int main() {
	std::string str;
	std::cin >> str;
	char res = 0;
	long long int k;
	std::cin >> k;
	for (auto i = 0; i < k && i < str.size(); ++i) {
		if (str[i] != '1') {
			res = str[i];
			break;
		}
	}
	if (res != 0) {
		std::cout << res << std::endl;
	}
	else {
		std::cout << str[k - 1] << std::endl;
	}
}

Measured memory_bytes: 256
n,m = input().split()
n = int(n)
m = int(m)
mlist = input().split(" ")
intmlist = [int(s) for s in mlist]
intmlist.sort(reverse=True)
# mlist = []
# for i range(0,m):
    # mlist.append(input())
# print(intmlist)

for i in range(0,m):
    n = n - intmlist[i]
    if n < 0:
        print(-1)
        break
    if i == m - 1:
        print(n) 
# if sumday > n:
#     print(-1)
# else:
#     print(n - sumday)

Measured memory_bytes: 10008
#include<iostream>
#include<stdlib.h>
#include<vector>
#include<algorithm>
#include<stdio.h>
#include<string>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<limits.h>
#include<cmath>
#include<queue>
#define rep(i,n) for(ll i = 0; i < (ll)n; i++)
#define swap(a,b) a^=b;b^=a;a^=b;
#define chmax(a,b) {if(a < b) a = b;}
#define chmin(a,b) {if(a > b) a = b;}
using namespace std;
typedef long long ll;
ll gcd(ll, ll);
vector<bool> to_binary(int);
int sum(vector<int>);
int min(vector<int>);
int max(vector<int>);
ll nCr(ll n, ll r);

const ll INF = 1LL << 60;

typedef tuple<ll, ll> mtupl;

bool mycomp(mtupl x, mtupl y) {
	return get<1>(x) < get<1>(y);
}

vector<vector<ll>> memo;

ll get(int x, int y) {
	if (memo[x][y] != -1)
		return memo[x][y];

	if (x == 0) return 1;
	if (y < x) return 0;

	memo[x][y] = get(x, y - 1) + get(x - 1, y - 1);
	return memo[x][y];
}

ll mpow(ll a, ll b) {
	ll ans = 1;
	for (ll i = 0; i < b; i++) {
		ans *= a;
		ans %= 1000000007;
	}
	return ans;
}

ll nCr(ll n, ll r) {
	ll res = 1;
	for (int i = 0; i < r; i++) {
		res *= (n - i);
	}
	for (int i = 1; i <= r; i++) {
		res /= i;
	}
	return res;
}

int vsum(vector<int> v) {
	int res = 0;
	for (auto it = v.begin(); it != v.end(); it++)
		res += *it;
	return res;
}
int vmin(vector<int> v) {
	int min = INT32_MAX;
	for (auto it = v.begin(); it != v.end(); it++)
		min = std::min(min, *it);
	return min;
}
int vmax(vector<int> v) {
	int max = INT32_MIN;
	for (auto it = v.begin(); it != v.end(); it++)
		max = std::max(max, *it);
	return max;
}

ll gcd(ll A, ll B) {
	if (A == 0 || B == 0) return max(A, B);
	int r = A % B;
	while (r != 0) {
		A = B;
		B = r;
		r = A % B;
	}

	return B;
}

vector<bool> to_binary(int x) {
	vector<bool> res;
	while (x != 0) {
		res.push_back(x % 2);
		x /= 2;
	}
	return res;
}

template<int index>
bool comp(tuple<ll, ll, ll, ll> a, tuple<ll, ll, ll, ll> b) {
	return get<index>(a) < get<index>(b);
}

int vector_finder(std::vector<ll> vec, ll number) {
	auto itr = std::find(vec.begin(), vec.end(), number);
	size_t index = std::distance(vec.begin(), itr);
	if (index != vec.size()) { // 発見できたとき
		return index;
	}
	else { // 発見できなかったとき
		return 0;
	}
}


int len(int x) {
	return (int)log10(x) + 1;
}

int same_vec(vector<int> a, vector<int> b) {
	int res = 1, num = a.size();
	for (int i = 0; i < num; i++) {
		if (a[i] != b[i]) {
			res = 0;
			break;
		}
 	}
	return res;
}


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

	int N;
	cin >> N;

	vector<int> A(N);
	vector<int> B(N);
	vector<int> C(N);

	ll ans = 0;
	ll tmp;
	
	rep(i, N)
		cin >> A[i];
	rep(i, N) {
		cin >> tmp;
		ans += tmp;
	}
	rep(i, N - 1)
		cin >> C[i];


	for (int i = 0; i < N - 1; i++) {
		if (A[i] + 1 == A[i + 1])
			ans += C[A[i] - 1];
	}

	cout << ans << endl;

ProgramEndPointLabel:;

	//Program End
	system("pause");

	return 0;
}




Measured memory_bytes: 504
#include<iostream>
#include<cstdio>
using namespace std;
int h[105];
int main(void)
{
    int n,sum=0;
    scanf("%d" ,&n);
    for(int i=0;i<n;i++)
        scanf("%d" ,&h[i]);
    sum=h[0];
    for(int i=1;i<n;i++)
    {
        if(h[i]>h[i-1])
            sum+=h[i]-h[i-1];
    }
    printf("%d" ,sum);
    return 0;
}


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

#define rep(i,n) for(int i=0;i<(n);++i)
#define FOR(i,n,j) for(int i=(j);i<(n);++i)
#define ssort(n) sort((n).begin(),(n).end())
#define rsort(n) sort((n).begin(),(n).end(),greater<int>())
#define mp make_pair
using ll=long long;
using ld=long double;
typedef pair<int,int> P;
typedef pair<P,int> COST;
#define repl(i,n) for(ll i=0;i<(n);++i)
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
using Graf=vector<vector<int>>;
#define MAX 1000000007

int main()
{
    int n;
    cin >> n;
    vector<string> s(n);
    rep(i,n)cin >> s[i];
    int count=0;
    int a_b_exist=0;
    int a,b;a=b=0;
    rep(i,n){
        if(s[i][0]=='B'&&s[i][s[i].size()-1]=='A'){
            a_b_exist++;
        }
        if(s[i][0]=='B'){
            b++;
        }
        if(s[i][s[i].size()-1]=='A'){
            a++;
        }
    }
    count=min(a,b);
    if(a==b&&b==a_b_exist&&count>0){
        count--;
    }
    rep(i,n){
        rep(j,s[i].size()-1){
            if(s[i][j]=='A'&&s[i][j+1]=='B'){
                count++;
            }
        }
    }
    cout << count << endl;
}

Measured memory_bytes: 3708
def solve(h_list):
  ans = 0
  h_max = h_list[0]
  for h in h_list:
    if h >= h_max:
      ans += 1
      h_max = h

  return ans

def main():
  n = int(input())
  h_list = list(map(int, input().split()))
  
  ans = solve(h_list)
  print(ans)

main()

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

using namespace std;

int main() {
	int n;
	scanf("%d", &n);
	vector <int> a(n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	vector <int> h(n);
	for (int i = 0; i < n; i++) {
		if (i & 1) h[0] -= a[i];
		else h[0] += a[i];
	}
	for (int i = 1; i < n; i++) {
		h[i] = 2 * a[i - 1] - h[i - 1];
	}
	for (int i = 0; i < n; i++) {
		printf("%d ", h[i]);
	}
	return 0;
}


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

const int N = 2e3+3;
int n, l[N];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> l[i];
    }
    sort(l,l+n);
    int ans = 0;
    for (int i = 0; i < n-2; i++) {
        int pt = i+2;
        for (int j = i+1; j < n; j++) {
            while (pt < n && l[pt] < l[i] + l[j]) pt++;
            ans += pt-(j+1);
            //cout << i << ' ' << j << ": " << pt << '\n';
        }
    }
    cout << ans << '\n';
}



Measured memory_bytes: 256
import sys

input = sys.stdin.readline

def main():
    N = int(input())
    A = []
    B = []
    C = []
    for i in range(N):
        a, b, c = map(int, input().split())
        A.append(a)
        B.append(b)
        C.append(c)

    dpa = [0] * N
    dpb = [0] * N
    dpc = [0] * N

    dpa[0] = A[0]
    dpb[0] = B[0]
    dpc[0] = C[0]

    for i in range(1, N):
        dpa[i] = max(dpb[i - 1] + A[i], dpc[i - 1] + A[i])
        dpb[i] = max(dpa[i - 1] + B[i], dpc[i - 1] + B[i])
        dpc[i] = max(dpa[i - 1] + C[i], dpb[i - 1] + C[i])

    print(max(dpa[N - 1], dpb[N - 1], dpc[N - 1]))


if __name__ == "__main__":
    main()


Measured memory_bytes: 26852
a,b,c=map(int,input().split())
if a%2==b%2 and b%2==c%2:
    a,b,c=sorted([a,b,c])
    ans=(c-a)//2+(c-b)//2
else:
    ax=a+(a%2==b%2 or a%2==c%2)
    bx=b+(b%2==a%2 or b%2==c%2)
    cx=c+(c%2==a%2 or c%2==b%2)
    a,b,c=sorted([ax,bx,cx])
    ans=(c-a)//2+(c-b)//2+1
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
string s;
int l;
int main(){
    cin>>s;
    l=s.size();
    for(int i=0;i<l;i++)
        if(s[i]=='C')
            for(int j=i+1;j<l;j++)
                if(s[j]=='F')
                {
                    cout<<"Yes"<<endl;
                    return 0;
                }
    cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
Q = int(input())
L = []
R = []
for i in range(Q):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
m = max(R)

primes = [2]
is_prime = [0, 0, 1]
count_like = [0, 0, 0]
for n in range(3, m+1):
    if n % 2 == 0:
        is_prime.append(0)
        count_like.append(count_like[n-1])
    else:
        i = 0
        p = primes[i]
        while p <= n**(1/2):
            if n % p == 0:
                is_prime.append(0)
                count_like.append(count_like[n-1])
                break
            i += 1
            p = primes[i]
        else:
            primes.append(n)
            is_prime.append(1)
            if is_prime[int((n+1)/2)]:
                count_like.append(count_like[n-1]+1)
            else:
                count_like.append(count_like[n-1])

for i in range(Q):
    print(count_like[R[i]]-count_like[L[i]-1])

Measured memory_bytes: 13800
#include <cstdio>
#include <cmath>
#include <algorithm>
#define eps 1e-10
#define pi 3.14159265358979
using namespace std;
int main() {
    int m, n;
    while (scanf("%d",&m)) {
        if (m==0) break;
        double a=0.0, b=0.0;
        double arg=360.0;
        for (int i=0; i<m-1; i++) {
            int v; scanf("%d",&v);
            a+=sin((double)v/180.0*pi);
            arg-=v;
        }
        a+=sin(arg/180.0*pi);
        arg=360.0;
        scanf("%d",&n);
        for (int i=0; i<n-1; i++) {
            int v; scanf("%d",&v);
            b+=sin((double)v/180.0*pi);
            arg-=v;
        }
        b+=sin(arg/180.0*pi);
        if (abs(a-b)<eps) puts("0");
        else if (a-eps>b) puts("1");
        else puts("2");
    }
}

Measured memory_bytes: 0
#include <iostream>
#include <vector>

typedef long long ll;

int main(){
   ll H;
   std::cin >> H;

   ll N = 0;
   while(H){
      H /= 2;
      ++N;
   }
   std::vector<ll> dp(N,0);
   dp[0] = 1;
   for(int i=1; i<N; i++){
      dp[i] = dp[i-1]*2 + 1;
   }
   std::cout << dp[N-1] << std::endl;
   return 0;
}


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

using namespace std;

#define nfs                      \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);            \
    cout.tie(nullptr);

int main() {
    nfs;

    int n;
    cin >> n;
    int a[n], b[n], c[n];
    int dp[3][n];

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

    dp[0][0] = a[0];
    dp[1][0] = b[0];
    dp[2][0] = c[0];

    for (int i = 1; i < n; ++i) {
        dp[0][i] = a[i] + max(dp[1][i - 1], dp[2][i - 1]);
        dp[1][i] = b[i] + max(dp[0][i - 1], dp[2][i - 1]);
        dp[2][i] = c[i] + max(dp[0][i - 1], dp[1][i - 1]);
    }

    cout << max({dp[0][n - 1], dp[1][n - 1], dp[2][n - 1]}) << "\n";
}

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

using namespace std ;

#define inf 0x3f3f3f3f
#define ll long long

ll n , s ;

ll f( ll b , ll n ) {
    return n < b ? n : f( b , n / b ) + n % b ;
}

int main() {
    scanf( "%lld%lld" , &n , &s ) ;
    if( s > n ) return puts( "-1" ) , 0 ;
    if( s == n ) return printf( "%lld\n" , n + 1 ) , 0 ;
    ll m = sqrt( n ) + 1 ;
    for( ll i = 2 ; i <= m ; i ++ ) {
        if( f( i , n ) == s ) 
            return printf( "%lld" , i ) , 0 ;
    }
    ll ans = 1e11 ; n -= s ;
    for( ll i = 1 ; i * i <= n ; i ++ ) {
        if( n % i == 0 ) {
            ll b = n / i + 1;
            if( f ( b , n + s ) ==  s ) ans = min ( ans , b ) ;
        }
    }
    printf( "%lld\n" , ans != 1e11 ? ans : -1 ) ;
    return 0 ;
} 

Measured memory_bytes: 256
#![allow(non_snake_case)]

fn read_line() -> String {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().to_string()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    read_line()
        .split_whitespace()
        .map(|e| e.parse().ok().unwrap())
        .collect()
}

fn read_tuple<T: std::str::FromStr + Copy>() -> (T, T) {
    let v: Vec<T> = read_vec();
    (v[0], v[1])
}

fn main() {
    let (N, M) = read_tuple::<usize>();
    let mut cities = vec![vec![]; N+1];
    for i in 0..M {
        let (P, Y) = read_tuple::<usize>();
        cities[P].push((Y, i));
    }
    for p in 1..N+1 {
        cities[p].sort();
    }
    let mut ids = vec![String::new(); M];
    for p in 1..N+1 {
        for j in 0..cities[p].len() {
            let mut s = (j+1).to_string();
            while s.len() < 6 {
                s = "0".to_string() + &s;
            }
            s = p.to_string() + &s;
            while s.len() < 12 {
                s = "0".to_string() + &s;
            }
            ids[cities[p][j].1] = s;
        }
    }
    for id in ids {
        println!("{}", id);
    }
}


Measured memory_bytes: 19964
#include <stdio.h>

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>

using namespace std;
typedef long long llong;

static bool isPalindrome(const string& s) {
  int ss = 0;
  int se = s.size() - 1;
  while (ss < se) {
    if (s[ss] != s[se])
      return false;
    ++ss;
    --se;
  }
  return true;
}

void BStringPalindrome(std::istream& in, std::ostream& out) {
  string s;
  in >> s;
  const int n = s.size();
  int b1 = 0;
  int e1 = (n - 1) / 2 - b1;
  int b2 = (n + 3) / 2 - 1;
  int e2 = n - b2;
  if (isPalindrome(s) &&
      isPalindrome(s.substr(b1, e1)) &&
      isPalindrome(s.substr(b2, e2))) {
    out << "Yes\n";
  } else {
    out << "No\n";
  }
}

int main(int argc, char** argv) { BStringPalindrome(cin, cout); return 0; }


Measured memory_bytes: 888
# coding: utf-8
# Your code here!

def floor_sum(n,m,a,b):
    ans = n*(b//m)
    b %= m
    while True:
        ans += (n-1)*n//2*(a//m)
        a %= m
        y_max = (a*n + b)//m
        if y_max == 0:
            return ans
        b -= y_max*m #now we have  x_max = -(b//a)
        ans += (n + b//a)*y_max
        n = y_max
        b %= a
        m,a = a,m

import sys
readline = sys.stdin.readline
read = sys.stdin.read

T = int(readline())
for i in range(T):
    N, M, A, B = map(int, readline().split())
    print(floor_sum(N, M, A, B))


Measured memory_bytes: 70784
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int x[111]={0},y[111]={0};
vector<pair<int,int>>mm[16];
int n;
int sta[16]={0};
int solve(int num){
    for(int i=1;i<=n;i++,num/=2)
        sta[i]=num%2;
    for(int i=1;i<=n;i++){
        int flag = 1 ;
        for(auto pp:mm[i]){
            if(sta[pp.first]!=pp.second)
                flag = 0;
        }
        if(flag != sta[i])
            return 0;
    }
    int ret =0 ;
    for(int i=1;i<=n;i++)
        ret+=sta[i];
    return ret;
}
int main()
{
    //cout << (1<<15) << endl;
    cin >> n;
    for(int i=1;i<=n;i++){
        int num,a,b;
        cin >> num;
        while(num--){
            cin >>a >> b;
            mm[i].push_back({a,b});
        }
    }
    int ans = 0 ;
    for(int i=0;i<(1<<n);i++){
        //cout <<
        ans = max(ans,solve(i));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3604
from itertools import groupby
MOD = 10**9+7
input()
S = input()
T = input()
def f(s): return list(map(lambda p: len(list(p[1])), groupby(s)))
A = f(f(S))
p2 = 0
p3 = 1
if len(A) > 1:
    Av = A[S[0]!=T[0]::2]
    Ah = A[S[0]==T[0]::2]
    p2 += sum(Av)-len(Av)+len(Ah)
    p3 += sum(Ah)-len(Ah)
elif S[0]==T[0]:
    Av = A[S[0]!=T[0]::2]
    p2 += sum(Av)-len(Av)
else:
    Ah = A[S[0]==T[0]::2]
    p3 += sum(Ah)-len(Ah)
    p2 += len(Ah)
print(pow(2,p2,MOD)*pow(3,p3,MOD)%MOD)

Measured memory_bytes: 3064
#include <cmath>
#include <chrono>
#include <random>
#include <ctime>
#include <algorithm>
#include <iosfwd>
#include <iostream>
#include <list>
#include <ostream>
#include <streambuf>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;

typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define fori(i, n) for(ll i = 0; i < (n); ++i)
#define forI(i, n) for(ll i = 1; i <= (n); ++i)
#define pll pair<ll, ll>
#define ff first
#define ss second

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("fast-math")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")

#define pt pair<ll, ll>
#define x first
#define y second

pll operator+ (pll a, pll b){ return {a.x + b.x, a.y + b.y}; }

ll rand0m() {
    return (ull(rand()) << 15ull | ull(rand()));
}                   //[0 ... n)
ll rand0m(ll x) {
    return rand0m() % x;
}               //[0 ... n)
ll rand0m(ll minn, ll maxx) {
    return rand0m(maxx - minn + 1) + minn;
}   //[minn ... maxx]

const ll MAXN = 1e6 + 1;
const ll mod = 1e9 + 7;
const ll INF = 2e9 + 1000;

ll n, m;
string s[1000];
ll dp[1000][1000];

void solve(){
    cin >> n >> m;
    fori(i, n) cin >> s[i];
    dp[0][0] = 1;
    fori(i, n){
        fori(j, m){
            if(s[i][j] == '#') continue;
            if(i) dp[i][j] = dp[i - 1][j];
            if(j) dp[i][j] += dp[i][j - 1];
            if(dp[i][j] >= mod) dp[i][j] -= mod;
        }
    }
    cout << dp[n - 1][m - 1];
}

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

    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //stress();
    solve();
}

Measured memory_bytes: 9600
import sys;input=sys.stdin.readline
import sys
mod = pow(10, 9) + 7
sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    if   y == 0: return 1
    elif y == 1	 : return x % mod
    elif y % 2 == 0 : return power(x, y//2)**2 % mod
    else: return power(x, (y-1)//2)**2 * x % mod
    
def mul(a, b):
    return ((a % mod) * (b % mod)) % mod

def div(a, b):
    return mul(a, power(b, mod-2))
def div2(a, b):
    return mul(a, modinv(b))

def modinv(a):
    b, u, v = mod, 1, 0
    while b:
        t = a//b
        a, u = a-t*b, u-t*v
        a, b, u, v = b, a, v, u
    u %= mod
    return u

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod
    import sys
    mod = pow(10, 9) + 7
    sys.setrecursionlimit(pow(10, 8))

NNN = (10**6)
g1 = [1, 1]
g2 = [1, 1]
inverse = [0, 1]

for i in range( 2, NNN + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

from collections import deque
N, = map(int, input().split())
d = [list() for _ in range(N+1)]
d2 = [list() for _ in range(N+1)]
for _ in range(N-1):
    a, b = map(int, input().split())
    d[a].append(b)
    d[b].append(a)

queue=deque([1])
vs = set([1])
vs_bfs = list()
parents = [0] * (N+1)
while queue:
    v = queue.popleft()
    vs_bfs.append(v)
    for u in d[v]:
        if u in vs:
            continue
        parents[u] = v
        vs.add(u)
        queue.append(u)
        d2[v].append(u)

dp1 = [0 for _ in range(N+1)]
sss = [0 for _ in range(N+1)]
for v in vs_bfs[::-1]:
    t = 1
    ts = []
    for u in d2[v]:
        t = mul(dp1[u], t)
        ts.append(sss[u])
    st = sum(ts)
    sss[v] = st + 1
    for tt in ts:
        t = mul(cmb(st, tt, mod), t)
        st -= tt
    dp1[v] = t
#print(dp1)

for v in vs_bfs:
    if v == 1:
        continue
    p = parents[v]
#    print(dp2[p])
    dp1[v] = mul(
            div2(dp1[p], cmb(N-1, sss[v], mod)),
            cmb(N-1, N-sss[v], mod))

#print(dp2)

for x in dp1[1:]:
    print(x)


Measured memory_bytes: 162640
#include <iostream>
#include <string>
#include <vector>
#define rep(i, n) for (int i = 0; i < n; ++i)
using namespace std;

int main(int argc, char* argv[]) {
  int N, K;
  cin >> N >> K;
  if (K == 1) {
    cout << 0 << endl;
    return 0;
  }
  if ((N - K) >= 0) {
    cout << N - K << endl;
  }
  return 0;
}


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

struct node{
  struct node *r;
  struct node *l;
  struct node *p;
  int key;
};
typedef struct node * Node;
#define N NULL

Node root;
void insert(int);
void inorder(Node);
void preorder(Node);
Node find(Node, int);

int main(){
  int s, i, x;
  char c[20];

  scanf("%d", &s);
 
  for (i = 0; i < s; i++){
    scanf("%s",c);

    if (c[0] == 'f'){
      scanf("%d", &x);
      
      Node t = find(root, x);
      if(t != N) printf("yes\n");
      if(t == N) printf("no\n");

    }

    if (c[0] == 'i'){
      scanf("%d", &x);
      insert(x);
    }

    if (c[0] == 'p'){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }

  }
  return 0;
}

void insert(int k){
  Node y = N;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->l = N;
  z->r = N;
 
  while(x != N){
    y=x;
    if(z->key < x->key) x = x->l;
    else x = x->r;
  }
  z->p = y;
  if(y == N)root = z;
  else if(z->key < y->key) y->l = z;
  else y->r = z;
}

void inorder(Node u){
  if(u != N){
    inorder(u->l);
    printf(" %d",u->key);
    inorder(u->r);
  }
}
void preorder(Node u){
  if(u != N){
    printf(" %d",u->key);
    preorder(u->l);
    preorder(u->r);
  }
}

Node find(Node u, int k){
  while(u != N && k != u->key){
    if(k < u->key) u = u->l;
    else u = u->r;
  }
  return u;
}

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

int main(){
  ll n; cin >> n;
  vector<string> ans;
  map<string,ll> m;
  ll maxnum=0;
  rep(i,n){
    string s;
    cin >> s;
    if(m.count(s)>0) m.at(s)+=1;
    else m.insert(make_pair(s,1));
    maxnum=max(maxnum,m.at(s));
  }
  
  for(auto e:m){
    if(e.second==maxnum){
      ans.push_back(e.first);
    }
  }
  sort(ans.begin(), ans.end());
  for(auto t:ans){
    cout << t << endl;
  }


}

Measured memory_bytes: 27252
N = int(input())
A = list(map(int,input().split()))

ans = 1
A.sort()
if N % 2 == 1 and not A.count(0) == 1:
    ans = 0

s = -1
if N % 2 == 1:
    A.remove(0)
    s = 2
else:
    s = 1

for i in range(0, len(A), 2):
    if A[i] == A[i + 1] == s:
        ans *= 2
    else:
        ans = 0
    s += 2
    
print(ans % 1000000007)



Measured memory_bytes: 14004
#include <iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int ss[13], hs[13], cs[13], ds[13];
  for (int i = 0; i < 13; i++) {
    ss[i] = 0;
    hs[i] = 0;
    cs[i] = 0;
    ds[i] = 0;
  }
  char mark;
  int val;
  for (int i = 0; i < n; i++) {
    cin >> mark >> val;
    if (mark == 'S') {
      ss[val - 1]++;
    }
    if (mark == 'H') {
      hs[val - 1]++;
    }
    if (mark == 'C') {
      cs[val - 1]++;
    }
    if (mark == 'D') {
      ds[val - 1]++;
    }
  }

  for (int i = 0; i < 13; i++) {
    if (ss[i] == 0) {
      cout << "S " << i + 1 << endl;
    }
  }
  for (int i = 0; i < 13; i++) {
    if (hs[i] == 0) {
      cout << "H " << i + 1 << endl;
    }
  }
  for (int i = 0; i < 13; i++) {
    if (cs[i] == 0) {
      cout << "C " << i + 1 << endl;
    }
  }
  for (int i = 0; i < 13; i++) {
    if (ds[i] == 0) {
      cout << "D " << i + 1 << endl;
    }
  }
}


Measured memory_bytes: 3084
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
using namespace std;
typedef long long ll;
int main(){
  ll sina,kenn;
  cin >> sina >> kenn;
  priority_queue<ll> ne;
  for(int i = 0;i <= sina - 1;i++){
    ll a;
    cin >> a;
    ne.push(a);
  }
  for(int i = 0;i <= kenn - 1;i++){
    ll now = 0;
    now = ne.top();
    ne.pop();
    ne.push(now / 2);
  }
  ll kotae = 0;
  for(int i = 0;i <= sina - 1;i++){
    ll price = 0;
    price = ne.top();
    ne.pop();
    kotae += price;
    //cout << price << endl;
  }
  cout << kotae << endl;
}

Measured memory_bytes: 1400
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int abc[] = new int[3];
		for (int i = 0; i < 3; i++) {
			abc[i] = sc.nextInt();
		}
		int K = sc.nextInt();
		Arrays.sort(abc);
		for (int i = 1; i <= K; i++) {
			abc[2] = abc[2] * 2;
		}
		System.out.println(abc[0] + abc[1] + abc[2]);
	}
}

Measured memory_bytes: 23252
/*
参考
ブログ
https://qiita.com/keymoon/items/11fac5627672a6d6a9f6
コード
https://github.com/key-moon/Library/blob/master/src/Algorithm/String/rolling%20hash.csx
verify;
https://atcoder.jp/contests/abc141/tasks/abc141_e

基本的にはstringで使うことを前提にしている
vector<int>で使う場合は+129を1LL<<32とかにする

最初にinit()を呼び出してbaseを決める必要がある
*/

#include <cstdio>
#include <cstdlib>
#include <string>
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include <map>
#include <set>
#include <tuple>
#include <iomanip>
#include <functional>
#include <bits/stdc++.h>

using namespace std;
using ll=long long int;
#define bit(n,k) ( (n>>k)&1 )

//+++++++++++++++++++++++++++++

using u64=uint_fast64_t;
//vector<int> or string
template<typename T>
struct RollingHash{
    static const u64 MASK30=((u64)1<<30)-1;
    static const u64 MASK31=((u64)1<<31)-1;
    static const u64 MOD=((u64)1<<61)-1;
    static const u64 POSITIVIZER=MOD*7;
    static u64 base;
    static int sz;
    static vector<u64> power;
    vector<u64> hash;

    RollingHash(const T &v){
        int vz=(int)v.size();
        if(vz>sz){
            power.resize(vz+1);
            for(int i=sz+1;i<=vz;i++){
                power[i]=calc_mod( mul(power[i-1],base) );
            }
            sz=vz;
        }
        hash.assign(vz+1,0);
        for(int i=1;i<=vz;i++){
            hash[i]=calc_mod( mul(hash[i-1],base)+v[i-1] );
        }
    }

    static void init(){
        srand((unsigned)time(NULL));
        base=rand()%(1<<8)+129;
        power.push_back(1);
    }


    inline u64 get(int begin,int len){
        return calc_mod(hash[begin+len]+POSITIVIZER-mul(hash[begin],power[len]));
    }

    inline u64 mul(u64 l,u64 r){
        u64 lu=l>>31;
        u64 ld=l&MASK31;
        u64 ru=r>>31;
        u64 rd=r&MASK31;
        u64 middle=ld*ru+lu*rd;
        return ((lu*ru)<<1)+ld*rd+((middle&MASK30)<<31)+(middle>>30);
    }

    inline u64 calc_mod(u64 x){
        x=(x&MOD)+(x>>61);
        if(x>=MOD) x-=MOD;
        return x;
    }
};
template<typename T>
using RH=RollingHash<T>;
using RHs=RollingHash<string>;

template<typename T> u64 RollingHash<T>::base;
template<typename T> int RollingHash<T>::sz=0;
template<typename T> vector<u64> RollingHash<T>::power;


//+++++++++++++++++++++++++++++++++++

signed main(){
    string T,P;
    cin>>T>>P;
    RHs::init();
    RHs t(T),p(P);
    for(int i=0;i+P.size()<=T.size();i++){
        if(t.get(i,P.size())==p.get(0,P.size())){
            cout<<i<<"\n";
        }
    }
}


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

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 (b < a) {
    a = b;
    return true;
  }
  return false;
}

const long long INF = 1LL << 60;

long long h[100010];
long long dp[100010];

long long rec(int i) {
  // メモしてあるならその結果を返し即座に抜ける
  if (dp[i] < INF) return dp[i];
  
  // ベースケース
  if (i == 1) return 0;

  long long res = INF;
  chmin(res, rec(i-1) + abs(h[i] - h[i-1]));
  if (3 <= i) chmin(res, rec(i-2) + abs(h[i] - h[i-2]));

  dp[i] = res; // メモする
  return res;
}

int main() {
  int N; cin >> N;
  for (int i = 1; i <= N; i++) cin >> h[i];
  for (int i = 0; i < 100010; i++) dp[i] = INF;
  cout << rec(N) << endl;
  return 0;
}

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

int main(){
  int n,m; cin >>n >>m;
  int cnt = n-1;
  dsu d(n);
  rep(i,m){
    int a,b; cin >>a >>b;
    a--; b--;
    d.merge(a,b);
  }
  rep(i,n){
    if(d.leader(i)!=i) cnt--;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 3796