akhauriyash/Code-Regression huggingface dataset:
import java.util.Scanner;
import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long result = 0;
    char[] cs;
    String s;
    Map<String, Integer> map = new HashMap<String, Integer>();
    for(int i = 0, n = sc.nextInt(); i < n; i++) {
      cs = sc.next().toCharArray();
      Arrays.sort(cs);
      s = new String(cs);
      if (map.containsKey(s)) {
        result += map.get(s);
        map.put(s, map.get(s) + 1);
      } else
        map.put(s, 1);
    }
    System.out.println(result);
  }
}

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

int compare_int(const void *a, const void *b)
{
    return *(int*)a - *(int*)b;
}

int main(void){
	int n;
	scanf("%d",&n);
	int a[n];
	for(int i=0;i<n;i++) {scanf("%d",&a[i]);}
	qsort(a, n, sizeof(int), compare_int);
	
	int count=0;
	int samecount=0;
	int before=-1;
	for(int i=0;i<n;i++){
		if(before==a[i]){samecount++;}
		else{
			if(samecount%2==1){count++;}
			samecount=1;
		}
		before=a[i];
	}
	if(samecount%2!=0){count++;}
	
	printf("%d",count);
	
} 

Measured memory_bytes: 892
#include <iostream>
#include <vector>
#include <unordered_map>
#include <queue>
#include <cmath>

using namespace std;



int  main(){
    int N, K;
    cin >> N >> K;
    long long int h[N];
    for (int i = 0; i < N; i++){
        cin >> h[i];
    }
    long long int dp[N], mn;
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    for (int i = 2; i < N; i++){
        mn = 10000000000;
        for (int j = i-1; j > max(-1, i-1-K); j--){
            mn = min(mn, dp[j] + abs(h[j] - h[i]));
        }
        dp[i] = mn;

    }
    cout << dp[N-1] << endl;
}

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

int main() {
  long N;
  cin >> N;
  vector<long> A(N);
  for (long i = 0; i < N; i++) cin >> A.at(i);
  vector<long> R(N);
  R.at(0) = A.at(0);
  for (long i = 1; i < N; i++) {
    R.at(i) = R.at(i - 1) + A.at(i);
  }
  long sum = 0, cor = 0;
  for (long i = 0; i < N; i++) {
    if (i % 2 == 0) {
      if (R.at(i) + cor > -1) {
        long tmp = (R.at(i) + cor) - -1;
        cor -= tmp;
        sum += tmp;
      }
    } else {
      if (R.at(i) + cor < 1) {
        long tmp = 1 - (R.at(i) + cor);
        cor += tmp;
        sum += tmp;
      }
    }
  }
  long ans = sum;
  sum = 0, cor = 0;
  for (long i = 0; i < N; i++) {
    if (i % 2 == 1) {
      if (R.at(i) + cor > -1) {
        long tmp = (R.at(i) + cor) - -1;
        cor -= tmp;
        sum += tmp;
      }
    } else {
      if (R.at(i) + cor < 1) {
        long tmp = 1 - (R.at(i) + cor);
        cor += tmp;
        sum += tmp;
      }
    }
  }
  cout << min(ans, sum) << "\n";
}

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

using namespace std;

int g[100001], k[100001];

int main()
{
  int n;
  cin >> n;
  vector<int> v(n);
  for (int i = 0; i < n; i++)
    cin >> v[i];
  int gm, gmt = 0, km, kmt = 0;
  for (int i = 0; i < n; i++)
    if (i % 2 == 0)
    {
      g[v[i]]++;
      if (g[v[i]] > gmt)
      {
        gmt = g[v[i]];
        gm = v[i];
      }
    }
    else
    {
      k[v[i]]++;
      if (k[v[i]] > kmt)
      {
        kmt = k[v[i]];
        km = v[i];
      }
    }
  sort(g, g + 100001, greater<int>());
  sort(k, k + 100001, greater<int>());
  if (gm == km)
    cout << (g[1] > k[1] ? n - k[0] - g[1] : n - g[0] - k[1]) << endl;
  else
    cout << n - g[0] - k[0] << endl;

  return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>
int main(){
	int n,i,j,A[2000001],B[2000001],C[2000001],k=0;
	scanf("%d",&n);
	for(i=1;i<=n;i++){
		scanf("%d",&A[i]);
		if(k<A[i])
			k=A[i];
	}
	for(i=0;i<=k;i++)
		C[i]=0;
	for(j=1;j<=n;j++)
		C[A[j]]++;
	for(i=1;i<=k;i++)
		C[i]=C[i]+C[i-1];
	for(j=n;j>=1;j--){
		B[C[A[j]]]=A[j];
		C[A[j]]--;
	}
	for(i=1;i<=n;i++){
		printf("%d",B[i]);
		if(i<n)
			printf(" ");
	}
	printf("\n");
	return 0;
}


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

#define ll long long
#define fornum(A,B,C) for(A=B;A<C;A++)

using namespace std;

/////////////////////////////////////////////////////
#define pii pair<int,int>
#define pll pair<ll,ll>
#define piii pair<int,pii>
#define mp make_pair

ll N,Q;
ll A[101010],X[101010];
ll sm[101010], esm[101010];
ll i, j, k, ans;


int main(){
    scanf("%lld%lld", &N, &Q);
    if(N%2){
        A[0] = 0;
        j = 1;
        N++;
    }
    fornum(i,j,N){
        scanf("%lld", &A[i]);
    }
    fornum(i,0,Q){
        scanf("%lld", &X[i]);
    }
    fornum(i,0,N){
        sm[i + 1] = sm[i] + A[i];
    }
    for (i = 2; i <= N;i+=2){
        esm[i] = esm[i + 1] = esm[i - 1] + A[i - 1];
    }
    
    fornum(i,0,Q){
        if(N==2||abs(X[i]-A[N-3])>abs(X[i]-A[N-2])){
            printf("%lld\n", esm[N]);
            continue;
        }
        ll l = 2, r = N / 2;
        while(l<r){
            ll c = (l + r + 1) / 2;
            //printf("%lld:%lld,%lld:%lld\n", l, r,c, cc);
            if (abs(X[i]-A[N - c * 2 + 1]) > abs(X[i]-A[N - c]))
            {
                r = c-1;
            }else{
                l = c;
            }
        }
        ll a = l;
        printf("%lld\n", sm[N] - sm[N - a] + esm[N - a * 2]);
        /*
        l = 2;
        r = N / 2;
        while(l<r){
            ll c = (l + r) / 2;
            ll cc = ck(X[i], c);
            if (c>0&&abs(X[i]-A[N - c * 2]) <= abs(X[i]-A[N - c]-1))
            {
                l = c+1;
            }else{
                l = c;
            }
        }
        printf("%lld\n", sm[N] - sm[N - r] + esm[N - r * 2]);
        */
    }

    return 0;
}

Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i = 0; i < (n); i++)
#define all(v) v.begin(), v.end()
#define MOD 998244353
const int INF = 1LL<<30;

void add(ll& a, ll b){
    a = (a+b) % MOD;
}
void mul(ll& a, ll b){
    a = a*b % MOD;
}
 
ll power_mod(ll num, ll power){
    ll prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}
 
ll extgcd(ll a, ll b, ll& x, ll& y){
    ll d = a;
    if(b != 0){
        d = extgcd(b, a%b, y, x);
        y -= (a/b) * x;
    }else{
        x = 1; y = 0;
    }
    return d;
}
 
ll inv_mod(ll a){
    ll x, y;
    extgcd(a, MOD, x, y);
    return (MOD + x%MOD) % MOD;
}
 
vector<ll> fact, fact_inv;
 
void create_mod_tables(int num){
    fact.assign(num+1, 1);
    fact_inv.assign(num+1, 1);
    for(int i=1; i<=num; i++) fact[i] = fact[i-1] * i % MOD;
    fact_inv[num] = inv_mod(fact[num]);
    for(int i=num; i>0; i--) fact_inv[i-1] = fact_inv[i] * i % MOD;
}
 
ll comb_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD * fact_inv[k] % MOD;
}
 
ll perm_mod(int n, int k){
    return fact[n] * fact_inv[n-k] % MOD;
}


int main() {
    int N,M,K;
    cin>>N>>M>>K;
    create_mod_tables(300000);

    ll ans=0;
    for(int i=0;i<=K;i++){
        ll res=comb_mod(N-1,i);
        int num=N-i;
        mul(res,M);
        mul(res,power_mod(M-1,num-1));
        add(ans,res);
    }

    cout<<ans<<endl;
}

Measured memory_bytes: 7996
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)


N, M, K = map(int, input().split(" "))
uf = UnionFind(N)
deg = [1 for i in range(N)]
same = [0 for i in range(N)]

for _ in range(M):
    A, B = map(int, input().split(" "))
    uf.union(A - 1, B - 1)
    deg[A - 1] += 1
    deg[B - 1] += 1

for _ in range(K):
    C, D = map(int, input().split(" "))
    if uf.same(C - 1, D - 1):
        same[C - 1] += 1
        same[D - 1] += 1


ans = [uf.size(i) - deg[i] - same[i] for i in range(N)]
print(' '.join([str(a) for a in ans]))

Measured memory_bytes: 101536
n = int(input())
A = list(map(int, input().split()))
from collections import defaultdict as dd
dic = dd(lambda: 0)
for num in A:
  if num % 4 == 0:
    dic[2] += 1
  elif num % 2 == 0:
    dic[1] += 1
  else:
    dic[0] += 1
if dic[2] >= dic[0]:
  print("Yes")
elif dic[0] - dic[2] == 1 and dic[1] == 0:
  print("Yes")
else:
  print("No")

Measured memory_bytes: 62576
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int N;
char S[2005];
int A[2005], B[2005], Right[2005], Left[2005], Max[2005];
int sum, sum2;
int ans = 1000000005;
pair <int, int> X[2005];
void Read()
{

    cin.getline(S + 1, 2005);
    N = strlen(S + 1);
    for(int i = 1; i <= N; i++)
    {
        A[i] = S[i] - '0';
        sum += A[i];
    }
    cin.getline(S + 1, 2005);
    for(int i = 1; i <= N; i++)
        B[i] = S[i] - '0', sum2 += B[i];
}
inline int Val(int pos)
{
    if(pos <= 0)
        pos += N;
    if(pos > N)
        pos -= N;
    return B[pos];
}
void precalcLeftRight()
{
    for(int i = 1; i <= N; i++)
    {
        int j = 0;
        while(j > -N && Val(i + j) == 0)
            --j;
        Left[i] = j;
        j = 0;
        while(j < N && Val(i + j) == 0)
            ++j;
        Right[i] = j;
    }
}

void Solve(int d)
{
    int cnt = 0;
    for(int i = 1; i <= N; i++)
    {
        int pos = i + d;
        if(pos <= 0)
        pos += N;
    if(pos > N)
        pos -= N;
        if(B[pos] != A[i])
            X[++cnt] = make_pair(min(0, d + Left[pos]), max(0, d + Right[pos]));
    }
    sort(X + 1, X + cnt + 1);
    for(int i = 1; i <= cnt; i++)
    {
        Max[i] = max(Max[i - 1], X[i].second);
    }
    X[cnt + 1].first = min(d, 0);
    Max[0] = max(0, d);
    for(int i = cnt + 1; i >= 1; i--)
    {
        int l = X[i].first, r = Max[i - 1];
        ans = min(ans, (r - l) * 2 - max(d, -d) + cnt);
    }
}
int main()
{
    Read();
    if(sum2 == 0)
    {
        if(sum == 0)
            cout << "0\n";
        else
            cout << "-1\n";
        return 0;
    }
    precalcLeftRight();
    for(int d = -N + 1; d <= N - 1; d++)
        Solve(d);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
#!/usr/bin python3
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):      #初期化
        self.n = n
        # 親
        self.parents = [i for i in range(n)]
        # 木の深さ
        self.ranks = [0] * n
        # グループの要素数
        self.sizes = [1] * n

    def find(self, x):          #親を出力
        if self.parents[x] == x:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.ranks[x] < self.ranks[y]:
            self.parents[x] = y
            self.sizes[y] += self.sizes[x]
        else:
            self.parents[y] = x
            self.sizes[x] += self.sizes[y]
            if self.ranks[x]==self.ranks[y]:
                self.ranks[x] += 1

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def size(self, x):          #グループの要素数
        root = self.find(x)
        return self.sizes[root]

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if i == x}

    def group_count(self):      #グループの個数
        return len(self.roots())

    def all_group_members(self):      #グループのメンバー一覧
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

################

n, m = map(int, input().split())
uf = UnionFind(n)
for _ in range(m):
    a,b = map(int,input().split())
    uf.unite(a-1, b-1)
ret = 0
for i in uf.roots():
    ret = max(ret, uf.size(i))
print(ret)


Measured memory_bytes: 37384
import numpy as np

n, m = map(int, input().split())
x = np.array([[0]*(n+1) for i in range(m)])
for i in range(m):
    a = list(map(int, input().split()))
    x[i, 0:(a[0]+1)] = a
    
p = list(map(int, input().split()))
ans = 0

for i in range(2**n):
    switch = []
    counter = 1
    for j in range(n):
        if (i>>j & 1):
            switch.append(j+1)


    for l in range(m):
        set_switch = set(switch) & set(x[l,1:])
        if len(set_switch) % 2 == p[l]:
            counter *= 1
        else:
            counter *= 0
    ans += counter
print(ans)

Measured memory_bytes: 12452
#include <cstdio>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <iterator>
#define loop(i, a, b) for(int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;

using namespace std;
using LL = long long;
using ULL = unsigned long long;

int main() {
    int a, b, c, d; cin >> a >> b >> c >> d;

    long long area1 = a * b;
    long long area2 = c * d;
    if (area1 < area2) {
        cout << area2 << endl;
    } else if (area1 >= area2) {
        cout << area1 << endl;
    }

}


Measured memory_bytes: 888
#include"bits/stdc++.h"
using namespace std;
#define REP(k,m,n) for(int (k)=(m);(k)<(n);(k)++)
#define rep(i,n) REP((i),0,(n))
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using tp3 = tuple<int, int, int>;
using Mat = vector<vector<ll>>;
constexpr int INF = 1 << 28;
constexpr ll INFL = 1ll << 60;
constexpr int dh[4] = { 0,1,0,-1 };
constexpr int dw[4] = { -1,0,1,0 };
bool isin(const int H, const int W, const int h, const int w) {
    return 0 <= h && h < H && 0 <= w && w < W;
}
template<typename T>
T minch(T& l, T r) {
    return l = min(l, r);
}
template<typename T>
T maxch(T& l, T r) {
    return l = max(l, r);
}
template<typename T>
void output(const T& val) {
    cout << val << endl;
}
template<typename T>
void output(const vector<T>& vec, const bool newline = false) {
    for (const T& val : vec)cout << val << (newline ? '\n' : ' '); cout << endl;
}
template<typename T>
void output(const vector<vector<T>>& mat) {
    for (const auto& row : mat)output(row);
}
// ============ template finished ============

int main()
{
    ll X;
    cin >> X;
    ll money = 100;
    ll time = 0;
    while (money < X) {
        money *= 1.01;
        time++;
    }
    cout << time << endl;
    return 0;
}


Measured memory_bytes: 3632
S=input()
n=len(S)
sums=0
for i in range(2**(n-1)):
    op = [""]*n
    for j in range(n-1):
        if ((i >>j)) & 1: op[j] = "+"
    formula=""
    for s,o in zip(S, op):
        formula+=(s+o)
    sums+=eval(formula)
print(sums)

Measured memory_bytes: 3060
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int d[100000];
int u[200000];
int v[200000];
int par[200000];
int cnt[200000];
int ans[200000];

int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    
    if (x == y) return;
    
    par[x] = y;
    cnt[y] += cnt[x];
}

int main() {
    int n, m, i;
    vector <pair <int, int>> w;
    
    scanf("%d %d", &n, &m);
    
    for (i = 0; i < n; i++) scanf("%d", &d[i]);
    
    for (i = 0; i < m; i++) {
        scanf("%d %d", &u[i], &v[i]);
        
        u[i]--;
        v[i]--;
        
        w.push_back(make_pair(max(d[u[i]], d[v[i]]), i));
    }
    
    sort(w.begin(), w.end());
    
    for (i = 0; i < n * 2; i++) {
        cnt[i] = 1;
        par[i] = i;
    }
    
    for (i = 0; i < w.size(); i++) {
        int c = w[i].first;
        int p = w[i].second;
        int x = u[p];
        int y = v[p];
        
        if (find(x) == find(y) || find(x) == find(y + n)) {
            ans[p] = 1e9;
            
            continue;
        }
        
        if (cnt[find(x)] == 1 && cnt[find(y)] == 1) {
            if (d[x] != d[y]) {
                puts("-1");
                
                return 0;
            }
        }
        
        ans[p] = c;
        
        unite(x, y + n);
        unite(x + n, y);
    }
    
    for (i = 0; i < n; i++) {
        if (find(i) == find(0)) {
            putchar('B');
        } else {
            putchar('W');
        }
    }
    puts("");
    
    for (i = 0; i < m; i++) printf("%d\n", ans[i]);
    
    return 0;
}


Measured memory_bytes: 8432
#include <cstdio>
#include <cstring>
using namespace std;
char s[500100];
int main(){
    scanf("%s", s + 200010);
    int q;
    scanf("%d", &q);
    int flag = 1;
    int start = 200010;
    int end = start + strlen(s + start) - 1;
    #ifdef DEBUG
    printf("xss %d %d\n", start, end);
    #endif
    while(q --){
        int d;
        scanf("%d", &d);
        if(d == 1){
            flag = -flag;
        }
        else{
            int did;
            char ss[20];
            scanf("%d %s", &did, ss);
            if(did == 1){
                if(flag == 1){
                    s[-- start] = ss[0];
                }
                else{
                    s[++ end] = ss[0];
                }
            }
            else{
                if(flag == 1){
                    s[++ end] = ss[0];
                }
                else{
                    s[-- start] = ss[0];
                }
            }
        }
    }
    if(flag == 1){
        for(int i = start; i <= end; i ++){
            printf("%c", s[i]);
        }
    }
    else{
        for(int i = end; i >= start; i --){
            printf("%c", s[i]);
        }
    }
    printf("\n");
    return 0;
}


Measured memory_bytes: 768
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
using P = pair<int,int>;
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}

int main() {
  int n;
  cin >> n;
  ll ans=1;
  rep(i,n) {
    ll x;
    cin >> x;
    ans=lcm(ans,x);
  }

  cout << ans << endl;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int N, K;
  cin >> N >> K;
  vector<int> P(N), C(N);
  for (auto&& e : P) {
    cin >> e;
    e--;
  }
  for (auto&& e : C) {
    cin >> e;
  }
  vector<vector<int64_t>> nxt(31, vector<int64_t>(N, 0)), sum(40, vector<int64_t>(N, 0)),
      all(40, vector<int64_t>(N, 0));
  for (int i = 0; i < N; i++) {
    nxt[0][i] = P[i];
    sum[0][i] = all[0][i] = C[P[i]];
  }
  for (int k = 0; k + 1 < 31; k++) {
    for (int i = 0; i < N; i++) {
      nxt[k + 1][i] = nxt[k][nxt[k][i]];
      sum[k + 1][i] = sum[k][i] + sum[k][nxt[k][i]];
      all[k + 1][i] = max(all[k][i], sum[k][i] + all[k][nxt[k][i]]);
    }
  }
  int64_t res = -(INT64_C(1) << 58);
  for (int i = 0; i < N; i++) {
    int64_t tot = 0;
    int cur = i;
    for (int k = 0; k < 31; k++) {
      if (K & (INT64_C(1) << k)) {
        res = max(res, tot + all[k][cur]);
        tot += sum[k][cur];
        cur = nxt[k][cur];
      }
    }
  }
  cout << res << '\n';
  return 0;
}


Measured memory_bytes: 7688
S=list(input())
N=2**(len(S)-1)
ans=0
for i in range(N):
    A=S[0]
    I=i
    for j in range(len(S)-1):
        if I//(2**(len(S)-2-j))==1:
            A+="+"
        else:
            A+=""
        I%=(2**(len(S)-2-j))
        A+=S[j+1]
    ans+=eval(A)
print(ans)

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

int main(){
    
    
    long long a, b, x;
    cin >> a >> b >> x;
    
    long long r;
    if(a != 0){
        r = a%x;
    }else{
        r = a;
    }
    
    long long last = b%x;
    b -= last;
    if(r != 0)a += (x - r);
    
    
    //cout << a << " " << b << " " << endl;
    if(a > b){
        cout << 0 << endl;
        return 0;
    }
    
    
    //cout << a << " " << b << " " << endl;
    long long value = (b - a)/x + 1;
    
    cout << value << endl;
    
    
}


Measured memory_bytes: 3644
#include<bits/stdc++.h>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007

using namespace std;
typedef long long ll;
typedef pair<ll,ll> P1;
typedef pair<int,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<int,ll>Pil;
typedef pair<int,Pil>Piil;
typedef pair<P1,ll> P2;
typedef pair<string,string> Ps;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};
struct pos{
	// 1 変数を入れる;
	int x,y,sx,sy,cost;
};
ll a[16];

int main() {

	int n,k;
	cin>>n>>k;
	rep(i,n)cin>>a[i+1];

	ll ans=INF;
	rep(i,(1<<n)){
		ll t=0,a2[16]={};
		ll ma=0;
		a2[0]=0;
		rep(j,n){
			a2[j+1]=a[j+1];
			if(i&(1<<j)){
				if(a2[j+1]<=ma){
					t+=ma-a2[j+1]+1;
					a2[j+1]+=ma-a2[j+1]+1;
				}
			}
			ma=max(ma,a2[j+1]);
		}
		int s=0;
		ma=0;
		rep(l,n){
			if(a2[l+1]>ma)s++;
			ma=max(ma,a2[l+1]);
		}
		if(s>=k)ans=min(ans,t);
	}
	cout<<ans<<endl;

	return 0;
}


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


int main(){	
	long long A;
	long long B;
	scanf("%lld",&A);
	scanf("%lld",&B);
	int res = max(A+B, max(2*A-1,2*B-1));
	cout << res << endl;
	return 0;
}



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

using namespace std;
using ll = long long;

#define REP(i, n) for (ll i = 0; i < n; i++)
#define INF 9223372036854775807
#define all(x) (x).begin(), (x).end()

ll ts = 1000000007;

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

  ll n;
  cin >> n;

  vector<int> a(n);
  REP(i, n) { cin >> a[i]; }

  ll now = 0, ans = -1;
  REP(i, n - 1) {
    now = a[now] - 1;
    if (now == 1) {
      ans = i + 1;
      break;
    }
  }
  cout << ans << "\n";
}

Measured memory_bytes: 640
#include "bits/stdc++.h"

using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
constexpr ld EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max() / 2;
constexpr int MOD = 1e9 + 7;

template <typename T>
void printv(const vector<T> &v)
{
    int sz = v.size();
    for (int i = 0; i < sz; i++)
    {
        cout << v[i] << " \n"[i == sz - 1];
    }
}

template <typename T>
class FenwickTree
{
    int n;
    std::vector<T> bit;

  public:
    FenwickTree(int _n) : n(_n), bit(_n, 0) {}

    void add(int pos, const T &w)
    {
        assert(0 <= pos && pos < n);
        for (int i = pos; i < n; i |= i + 1)
            bit[i] += w;
    }
    // v[0] + ... + v[pos-1]
    T sum(int pos)
    {
        assert(0 <= pos && pos <= n);
        T res = 0;
        for (int i = pos - 1; i >= 0; i = (i & (i + 1)) - 1)
        {
            res += bit[i];
        }
        return res;
    }
    T sum(int l, int r)
    {
        assert(0 <= l && l <= r && r <= n);
        return sum(r) + (-sum(l));
    }
};

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

    int n, k;
    cin >> n >> k;
    while (k--)
    {
        int a, b;
        cin >> a >> b;
        int dist = min({a - 1, n - a, b - 1, n - b});
        cout << dist % 3 + 1 << endl;
    }
}


Measured memory_bytes: 3116
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <map>
#include <queue>
#include <set>
typedef long long ll;
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define mod 1000000007
#define fst first
#define pb push_back

int main()
{
    int N;
    cin >> N;
    int cmax = 100 / 4;
    int dmax = 100 / 7;
    for(int i = 0; i <= cmax; i++){
        for(int j = 0; j <= dmax; j++){
            if(i*4 + j*7 == N){
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>

int main(void) {
    int a, b, c;
    int x, y, z;
    int j;
    scanf("%d %d %d", &a, &b, &c);
    
    x = a; y = b; z = c;
    
    if (x > y){
        x = b;
        y = a;
    }
    if (y > z){
        j = y;
        y = z;
        z = j;
    }
    if (x > y){
        j = x;
        x = y;
        y = j;
    }
    printf("%d %d %d\n", x, y, z);
        return 0;
    }




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

#define rep(i,s,n) for (int i = (int)s; i < (int)n; i++)
#define ll long long
#define pb push_back
#define All(x) x.begin(), x.end()
#define Range(x, i, j) x.begin() + i, x.begin() + j

static const int MAX = 100005;
static const int WHITE = 0;
static const int BLACK = 1;
static const int NOT_COLLOR = -1;

vector<pair<int, int>> adj[MAX];
int color[MAX];
int p[MAX];
// 親ノードとの距離
int dist[MAX];

int N;

void solve() {
  rep(i, 0, MAX) {
    color[i] = NOT_COLLOR;
    p[i] = -1;
    dist[i] = -1;
  }
  dist[0] = 0;
  dist[1] = 0;
  color[0] = WHITE;

  queue<int> que;
  que.push(1);

  while(!que.empty()) {
    int u = que.front();
    que.pop();

    if (dist[u] % 2 == 0) {
      color[u] = color[p[u]];
    } else {
      if (color[p[u]] == WHITE) {
        color[u] = BLACK;
      } else {
        color[u] = WHITE;
      }
    }

    rep(i, 0, adj[u].size()) {
      int v = adj[u][i].first;
      if (color[v] != NOT_COLLOR) continue;
      que.push(v);
      p[v] = u;
      dist[v] = adj[u][i].second;
    }
  }

};

int main() {
  cin >> N;
  int u, v, w;
  rep(i, 1, N) {
    scanf("%d %d %d", &u, &v, &w);
    adj[u].pb(make_pair(v, w));
    adj[v].pb(make_pair(u, w));
  }
  adj[0].pb(make_pair(1, 0));

  solve();

  rep(i, 1, N + 1) {
    printf("%d\n", color[i]);
  }
};


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

int main() {
	int H, W;
	cin >> H >> W;
	
	while (H > 0 && W > 0) {
		for (int i=1; i<=H; i=i+1) {
			for (int j=1; j<=W; j=j+1) {
				if ((i+j) % 2 == 0)
					cout << '#';
				else
					cout << '.';
			}
			cout << endl;
		}
		cout << endl;
		cin >> H >> W;
	}

	return 0;
}


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

#define long long long

using namespace std;

const int N = 1e5+5;

int n;
int l[N], r[N];
long high, lz_l, lz_r;
multiset<long> L, R;

int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) scanf("%d %d", l + i, r + i), r[i] -= l[i];
    for(int i = 1; i <= n; i++) {
        high += l[i];
        L.emplace(l[i] + lz_l), R.emplace(l[i] - lz_r);
        while(*L.rbegin() - lz_l > *R.begin() + lz_r) {
            long l = *L.rbegin(), r = *R.begin();
            L.erase(L.find(l)), R.erase(R.find(r));
            L.emplace(r + lz_r + lz_l), R.emplace(l - lz_l - lz_r);
        }
        long pv = 0;
        while(!L.empty() && *L.begin() - lz_l - r[i + 1] <= 0) {
            high -= abs(*L.begin() - lz_l - pv) * L.size();
            pv = *L.begin() - lz_l;
            L.erase(L.begin());
        }
        high -= abs(pv - r[i + 1]) * L.size();
        lz_l += r[i + 1], lz_r += r[i];
    }
    long m = L.size(), pv = 0;
    for(long x : L) {
        high -= abs(x - lz_l - pv) * m--;
        pv = x - lz_l;
    }
    printf("%lld\n", high);

    return 0;
}

Measured memory_bytes: 10368
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    int ans = 0, Ag = 0, Ap = 0;
    cin >> s;
    for (unsigned int i = 0; i < s.size(); i++) {
        if (s[i] == 'g') {
            if (Ap < Ag) {
                Ap++;
                ans++;
            } else {
                Ag++;
            }
        } else {
            if (Ap < Ag) {
                Ap++;
            } else {
                Ag++;
                ans--;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<int> a(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  int ans = 0;
  while(true){
    for(int i = 0; i < n; i++){
      if(a[i] % 2 != 0){
        cout << ans << endl;
        return 0;
      }
    }
    for(int i = 0; i < n; i++){
      a[i] /= 2;
    }
    ans++;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3588
n, k = map(int, input().split())

if k == 0:
    print(n * n)
    exit()

ans = 0
for i in range(k+1, n+1):
    quo, rem = divmod(n, i)
    ans += quo * (i-k)
    if rem >= k:
        ans += rem - k + 1

print(ans)

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

int main()
{
	ll a;
	string b;
	cin >> a >> b;

	ll c=0;
	c += a*(b[0]-'0')*100;
	
	c += a*(b[2]-'0')*10;
	c += a*(b[3]-'0');
	cout<<c/100<<endl;
}

Measured memory_bytes: 3624
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }

/*
 <url:http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2224>
 問題文============================================================
 
 
 
 =================================================================
 解説=============================================================
 
 これ蟻本の問題にあるよな？
 ================================================================
 */

struct UnionFind{
    vector<int> parent, rank;
    UnionFind(int n) : parent(n, -1), rank(n, 0) { }
    int find(int x){
        if(parent[x] == -1) return x;
        else return (parent[x] = find(parent[x]));
    }
    bool unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y) return false;
        if(rank[x] < rank[y])
            parent[x] = y;
        else
            parent[y] = x;
        if(rank[x] == rank[y]) rank[x]++;
        return true;
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
};

typedef long double ld;
struct edge{
    int u,v; ld cost;
    edge(int u = 0,int v = 0,ld cost = 0):u(u),v(v),cost(cost){}
    bool operator < (const edge& e) const{
        return cost < e.cost;
    }
};
ld solve(){
    ld res = 0;
    int N,M; cin >> N >> M;
    vector<complex<ld>> ps(N);
    for(int i = 0; i < N;i++){
        ld x,y; cin >> x >> y;
        ps[i] = complex<ld>(x,y);
    }
    priority_queue<edge> pq;
    for(int i = 0; i < M;i++){
        int p,q; cin >> p >> q;
        p--; q--;
        ld cost = abs(ps[p]-ps[q]);
        res += cost;
        pq.push(edge(p,q,cost));
    }
    UnionFind UF(N);
    while(pq.size()){
        auto e = pq.top(); pq.pop();
        if(UF.same(e.u,e.v)) continue;
        res -= e.cost;
        UF.unite(e.u,e.v);
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(12) << solve() << endl;
    return 0;
}



Measured memory_bytes: 4260
// copied
#include<bits/stdc++.h>
#define gc getchar()
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define Rep(i,v) rep(i,0,(int)v.size()-1)
#define lint long long
#define db double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define debug(x) cerr<<#x<<"="<<x
#define sp <<" "
#define ln <<endl
using namespace std;
typedef pair<int,int> pii;
typedef set<int>::iterator sit;
const int N=100000;
inline int inn()
{
    int x,ch;while((ch=gc)<'0'||ch>'9');
    x=ch^'0';while((ch=gc)>='0'&&ch<='9')
        x=(x<<1)+(x<<3)+(ch^'0');return x;
}
struct P{
    int x,y,id,dis;
    inline int init() { return x=inn(),y=inn(); }
    inline int getdis(int r,int c)
    {
        if(x==0) return dis=y;
        if(y==c) return dis=c+x;
        if(x==r) return dis=c+r+(c-y);
        if(y==0) return dis=c+r+c+(r-x);
        return assert(0),0;
    }
    inline bool operator<(const P &p)const { return dis<p.dis; }
}p[N<<1];int s[N],vis[N];
#define on_bj(p) (p.x==0||p.x==r||p.y==0||p.y==c)
int main()
{
    int r=inn(),c=inn(),n=inn(),cnt=0;
    rep(i,1,n)
    {
        static P p1,p2;p1.init(),p2.init();
        if(!on_bj(p1)||!on_bj(p2)) continue;
        p[++cnt]=p1,p[cnt].id=i,p[++cnt]=p2,p[cnt].id=i;
    }
    rep(i,1,cnt) p[i].getdis(r,c);
    sort(p+1,p+cnt+1);int t=0;
    rep(i,1,cnt)
    {
        if(!vis[p[i].id]) vis[s[++t]=p[i].id]=1;
        else{
            if(s[t]!=p[i].id) return !printf("NO\n");
            vis[p[i].id]=0,t--;
        }
    }
    return !printf("YES\n");
}


Measured memory_bytes: 7472
def nyu():
    A,B,C,X,Y = map(int,input().split())
    return A,B,C,X,Y

def kansu(A,B,C,X,Y):
    sum = 0
    #(A+B)<=2C AとBの単品で終わらせる
    if A+B<=2*C:
        sum += A*X + B*Y    
        return sum
     #(A+B)>2C xかyの大きいほうだけ2c分買う。AとBの単品に置き換えて値段をみる 
    else:
        kosu_sa =0
        if X>Y:
            sum = X * 2 * C
            if A < 2*C:
                sum = (sum - 2*C*(X-Y))+A*(X-Y)

        else:
            sum = Y * 2 * C
            if B < 2*C:
                sum = (sum - 2*C*(Y-X))+B*(Y-X)
    return sum
        

A,B,C,X,Y = nyu()
print(kansu(A,B,C,X,Y))

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
stack<pair<int , int> > s2;

int getAreas(string str){
	stack<int> st;
	int sum = 0,idx,area=0;
	for(int i=0;i<str.size();i++){
		if(str[i]=='\\'){
			st.push(i);
		}else if(str[i]=='/' && !st.empty()){
				idx = st.top();
				sum += i - idx;
				area = i-idx;
				st.pop();

			while(!s2.empty() && s2.top().first > idx){
				area += s2.top().second; s2.pop();
			}
			s2.push(make_pair(idx,area));
		}
	}
	return sum;
}

int main(){
	std::vector<int> v;
	string str;
	cin >> str;
	cout << getAreas(str) << endl;

	while(!s2.empty()){
		v.push_back(s2.top().second);
		s2.pop();
	}
	reverse(v.begin(),v.end());
	cout << v.size();
	for(int i=0;i<v.size();i++){
		cout << " ";
		cout << v[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 1336
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for(int i = 1, i##_len = (n); i < i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define PRINT(A) std::cout << (#A) << ":" << (A) << std::endl;

typedef long long int ll;
const int MOD = 1e9 + 7;
const int INF = 1e9;

using namespace std;

int main() {
  struct Pos {
    int x;
    int y;
  };
  int H, W, D;
  cin >> H >> W >> D;
  map<int, Pos> m;
  REP(i, H) REP(j, W) {
    int A;
    cin >> A;
    m[A] = Pos{j, i};
  }
  auto sum = vector<int>(H * W + 1);
  for(int i = 1; i <= H * W; i++) {
    auto cur = m[i];
    if(i - D >= 1) {
      auto prev = m[i - D];
      sum[i] = sum[i - D] + abs(cur.x - prev.x) + abs(cur.y - prev.y);
    }
  }

  int Q;
  cin >> Q;
  REP(i, Q) {
    int L, R;
    cin >> L >> R;
    cout << sum[R] - sum[L] << endl;
  }
}


Measured memory_bytes: 7040
import java.util.*;
public class Main{
  public static void main (String args[]){
    Scanner sc = new Scanner(System.in);
    //
    String a = sc.next();
    String b = a.substring(2, 3);
    String c = a.substring(3, 4);
    String d = a.substring(4, 5);
    String e = a.substring(5, 6);
    
    String ans = "No";
    
    if(b.equals(c) && d.equals(e)){
      ans = "Yes";
    }
    
    System.out.println(ans);
  }
}


Measured memory_bytes: 21844
import java.util.Scanner;

public class Main {

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

		int r = sc.nextInt();
		int c = sc.nextInt();

		int sum = 0;

		int[][] arr = new int[r + 1][c + 1];

		for (int i = 0; i < r; i++) {
			for (int j = 0; j < c; j++) {
				sum += arr[i][j] = sc.nextInt();
			}
			arr[i][c] = sum;
			sum = 0;
		}

		for (int i = 0; i < c; i++) {
			for (int j = 0; j < r; j++) {
				sum += arr[j][i];
			}
			arr[r][i] = sum;
			sum = 0;
		}

		for (int i = 0; i < r; i++) {
			sum += arr[i][c];
		}
		arr[r][c] = sum;

		for (int i = 0; i < r + 1; i++) {
			for (int j = 0; j < c + 1; j++) {
				if (!(j == 0)) {
					System.out.print(" ");
				}
				System.out.print(arr[i][j]);
			}
			System.out.println();
		}

	}
}


Measured memory_bytes: 41504
s="1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51"
k=int(input())

x=s.split(", ")

print(x[k-1])

Measured memory_bytes: 2940
#include<stdio.h>

int main() {
	int m, n;
	int A[1001];
	scanf("%d%d", &n, &m);
	int sum = 0;
	for (int i = 0; i < n; i++) {
		scanf("%d", A+i);
		sum += A[i];
	}
	float thr = (float)sum / (4 * m);
	int able = 0;
	for (int i = 0; i < n; i++) {
		if (A[i] >= thr) able += 1;
	}
	if (able >= m) printf("Yes\n");
	else printf("No\n");

	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<set>
#include<queue>
using namespace std;

typedef long long ll;

int main() {
  int N, Y; cin >> N >> Y;
  int x = -1,y = -1,z = -1;
  for ( int i = 0; i <= N; i++ ) {
    for ( int j = 0; j <= N; j++ ) {
      int rem = N - (i+j);
      int tmp = Y;
      tmp -= 1000*i+5000*j;
      if ( tmp >= 0 && tmp == rem*10000 ) {
	x = rem;
	y = j;
	z = i;
	break;
      }
    }
  }
  
  for ( int i = 0; i <= N; i++ ) {
    for ( int j = 0; j <= N; j++ ) {
      int rem = N - (i+j);
      int tmp = Y;
      tmp -= 5000*i+10000*j;
      if (tmp >= 0 && tmp == rem*1000 ) {
	x = j;
	y = i;
	z = rem;
	break;
      }
    }
  }

  for ( int i = 0; i <= N; i++ ) {
    for ( int j = 0; j <= N; j++ ) {
      int rem = N - (i+j);
      int tmp = Y;
      tmp -= 10000*i+1000*j;
      if ( tmp >= 0 && tmp == rem*5000 ) {
	x = i;
	y = rem;
	z = j;
	break;
      }
    }
  } 

  if( x == -1 || y == -1 || z == -1 ) cout << -1 << " " << -1 << " "
					   <<-1 << endl;
  else cout << x << " " << y << " " << z << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pi 3.14159265359
#define int long long
#define pii pair<int,int>
#define ld long double
const int mod=1e9 + 7;
 
int dx[]={-1, 0, 1, 0};
int dy[]={0, -1, 0, 1};
 
 
 
 
int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
 

string s,t;
int n;
cin>>n;
cin>>s>>t;

 for(int i=0;i<s.length();i++)
 {
   cout<<s[i]<<t[i];
 }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    int a, b, c;
    cin >> a >> b >> c;
    vector<int>vec = {a,b,c};
    sort(all(vec));
    if (vec[0] + vec[1] == vec[2]){
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}

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

using namespace std;

#define MAX 514

string S;
int memo[MAX][MAX];

bool rec(int L,int R){
    int &res = memo[L][R];
    if(res != -1) return res;
    if(L > R) return 1;
    if(S[L] != 'm' || S[R] != 'w') return 0;
    res = 0;
    for(int i = L+1 ; i < R ; i++){
        if(S[i] == 'e'){
            res = max(res,rec(L+1,i-1)&rec(i+1,R-1));
        }
    }
    return res;
}

int main(){
    cin >> S;
    memset(memo,-1,sizeof(memo));
    cout << (rec(0,S.size()-1) ? "Cat" : "Rabbit") << endl;
    return 0;
}

Measured memory_bytes: 2232
#include <bits/stdc++.h>
using namespace std;
int dp[100007]={},b[100007]={};
int mod = (int)(1e9+7);
int main(){
    int n,m;
    cin >> n >> m;
    int a[m];
    for(int i=0;i<m;i++){
        cin >> a[i];
        b[a[i]]=1;
    }
    dp[0] = 1;
    if(!b[1]) dp[1] = 1; 
    for(int i=0;i<n-1;i++){
        int c=dp[i+1],d=dp[i];
        if(b[i]) d=0;
        if(b[i+1]) c=0;
        dp[i+2] = (c+d)%mod;
        if(b[i+2]) dp[i+2] = 0;
    }
    cout << dp[n] << endl;
}

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

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

int op_max(int a, int b){
    return max(a,b);
}
int emin(){
    return -1;
}

int target;

bool f(int v) {
     return v < target; }

signed main(){
    int N, Q; cin>>N>>Q;
    vec_int A(N);rep(i,N)cin>>A.at(i);

    segtree<int, op_max, emin> seg(A);

    rep(q, Q){
        int T, a, b;
        cin>>T>>a>>b;
        if(T==1){
            seg.set(a-1,b);
        }else if(T==2){
            cout<<seg.prod(a-1,b)<<endl;
        }else{
            target =  b;
            cout<<seg.max_right<f>(a-1)+1<<endl;
        }

    }


    return 0;
}

Measured memory_bytes: 8980
using System;
using System.Linq;

public class Program
{
    static void Main()
    {
        string[] input = Console.ReadLine().Split(' ');
        int n = int.Parse(input[0]);
        int m = int.Parse(input[1]);
        int[] count = new int[m];
        for (int i = 0; i < n; i++)
        {
            int[] array = Array.ConvertAll(Console.ReadLine().Split(' '), int.Parse);
            for (int j = 1; j <= array[0]; j++)
            {
                count[array[j] - 1]++;
            }
        }
        int ans = 0;
        foreach (int c in count)
        {
            if (c == n)
                ans++;
        }
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 13140
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <vector>

#define LL long long

using namespace std;

const int N = 200010;
int n, D, A;

struct T {
	int x, h;
}a[N];

LL f[N];

int nxt[N];

void update(int x, LL y) {
	for (; x <= n; x += x & -x)
		f[x] += y;
}

LL query(int x) {
	LL tot = 0;
	for (; x; x -= x & -x)
		tot += f[x];

	return tot;
}

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

	for (int i = 1; i <= n; i++)
		scanf("%d%d", &a[i].x, &a[i].h);

	sort(a + 1, a + 1 + n, [](const T &p, const T &q) {
		return p.x < q.x;
	});

	for (int i = 1, j = 1; i <= n; i++) {
		while (j <= n && a[j].x - a[i].x <= 2 * D)
			j++;

		nxt[i] = j;
	}

	LL ans = 0;

	for (int i = 1; i <= n; i++)
		update(i, a[i].h - a[i - 1].h);

	for (int i = 1; i <= n; i++) {
		LL t = query(i);
		if (t > 0) {
			LL c = t / A + (bool)(t % A);
			ans += c;

			update(i, -c * A);
			update(nxt[i], c * A);
		}
	}

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

	return 0;
}

Measured memory_bytes: 7720
#include <iostream>

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

int main() {
  uint32_t n = 0;
  std::cin >> n;

  uint32_t a = 0, b = 0;
  std::cin >> a;
  for (size_t i = 0; i < n - 1; i++) {
    std::cin >> b;
    if (a < b)
      a = (a * b) / gcd(a, b);
    else
      a = (a * b) / gcd(b, a);
  }

  std::cout << a << std::endl;

  return 0;
}


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

using namespace std;

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

#define F first
#define S second
#define PU push
#define PUF push_front
#define PUB push_back
#define PO pop
#define POF pop_front
#define POB pop_back

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

void solve(int test_case) {
	queue<char> arr[3];
	fill(arr,arr+3,queue<char>());
	string a,b,c;
	cin>>a>>b>>c;
	for(char ch:a)arr[0].push(ch);
	for(char ch:b)arr[1].push(ch);
	for(char ch:c)arr[2].push(ch);
	int person = 0;
	while(1){
		if(arr[person].empty()){
			cout<<(char)('A'+person);
			return;
		}
		char top = arr[person].front();
		arr[person].pop();
		person=(top-'a');
		//cerr<<person<<"\n";
	}
}

int main() {
	
	////// FILE BASED IO////
	//freopen("in", "r", stdin);
	//freopen("out", "w", stdout);
	///////////////
	
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin>>t;
	REP(i,1,t) {
		solve(i);
	}
}	


Measured memory_bytes: 3668
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(ll i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n;
string s, t;

int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	
	cin >> n >> s >> t;
	rep(i, 0, n-1){
		cout << s[i] << t[i];
	}
	cout << endl;
	return 0;
}

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

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

using namespace std;

class union_find{
	int n;
	vector<int> p;
public:
	union_find(int n):n(n),p(n,-1){}
	int find(int u){ return p[u]<0?u:p[u]=find(p[u]); }
	void unite(int u,int v){
		u=find(u); v=find(v);
		if(u!=v){
			if(p[v]<p[u]) swap(u,v);
			p[u]+=p[v]; p[v]=u; n--;
		}
	}
	bool is_same(int u,int v){ return find(u)==find(v); }
	int size()const{ return n; }
	int size(int u){ return -p[find(u)]; }
};

template<class T> struct interval{
	T l,r;
	interval(){}
	interval(const T& l,const T& r):l(l),r(r){}
	bool operator<(const interval& I)const{ return make_tuple(l,r)<make_tuple(I.l,I.r); }
};

template<class T>
vector<interval<T>> interval_union(vector<interval<T>> I){
	sort(I.begin(),I.end(),[](const interval<T>& a,const interval<T>& b){ return a.l<b.l; });

	int n=I.size();
	if(n==0) return {};

	vector<interval<T>> res;
	T l=I[0].l,r=I[0].r;
	for(int i=1;i<=n;i++){
		if(i==n || r<I[i].l){
			res.emplace_back(l,r);
			if(i<n){
				l=I[i].l;
				r=I[i].r;
			}
		}
		else if(r<I[i].r){
			r=I[i].r;
		}
	}
	return res;
}

int main(){
	int n; scanf("%d",&n);
	vector<int> x(n),y(n);
	rep(i,n) scanf("%d%d",&x[i],&y[i]), x[i]--, y[i]--;

	vector<int> p(n);
	iota(p.begin(),p.end(),0);
	sort(p.begin(),p.end(),[&](int i,int j){
		return x[i]<x[j];
	});

	union_find U(n);
	vector<interval<int>> H;
	vector<int> I,Y;
	int y_pre=-1;
	for(int i=n-1;i>=0;i--){
		int idx=p[i];
//printf("(%d, %d)\n",x[idx]+1,y[idx]+1);

		int l=upper_bound(Y.begin(),Y.end(),y[idx])-Y.begin();
		if(l<Y.size()){
//printf("  l = %d, unite(%d, %d), add [%d, %ld)\n",l,idx,I[l],l,Y.size());
			U.unite(idx,I[l]);
			H.emplace_back(l,Y.size()-1);
		}

		if(y[idx]>y_pre){
			I.emplace_back(idx);
			Y.emplace_back(y[idx]);
			y_pre=y[idx];
		}
//printf("  |Y| = %ld\n",Y.size());
	}

	for(auto J:interval_union(H)){
		for(int i=J.l;i<J.r;i++) U.unite(I[i],I[i+1]);
//		for(int i=J.l;i<J.r;i++) printf("unite %d %d\n",I[i],I[i+1]);
	}
	rep(i,n) printf("%d\n",U.size(i));

	return 0;
}


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

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

    int n;
    string s;
    cin >> n >> s;

    vector<int> wtoe(n), etow(n);

    int echange = 0;
    wtoe[0] = 0;
    for(int i = 1; i < n; ++i){
        if(s[i-1]=='W') ++echange;
        wtoe[i] = echange;
    }

    int wchange = 0;
    etow[n-1] = 0;
    for(int i = n-2; i >= 0; --i){
        if(s[i+1] == 'E') ++wchange;
        etow[i] = wchange;
    }
    
    int res = 1e9;
    rep(i, n){
        res = min(res, wtoe[i] + etow[i]);
    }
    cout << res << endl;


}

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

int main() {

	int a, b;
	double x,c;

	cin >> a >> b;

	if (x = (a + b) % 2 == 0) {
		c = (a + b) / 2;
	
	}else {
		c = (a + b) / 2 + 1;
	}

	cout << c << endl;
}

Measured memory_bytes: 256
a,b,c,d=map(int,input().split())
if a <= c <= b <= d:
    print(b-c)
elif c <= a <= b <= d:
    print(b-a)
elif a <= c <= d <= b:
    print(d-c)
elif c <= a <= d <= b:
    print(d-a)
else:
    print(0)

Measured memory_bytes: 3060