akhauriyash/Code-Regression huggingface dataset:
# abc160_c.py
# https://atcoder.jp/contests/abc160/tasks/abc160_c

# C - Traveling Salesman around Lake /
# 実行時間制限: 2 sec / メモリ制限: 1024 MB
# 配点 : 300点

# 問題文
# 1周 K メートルの円形の湖があり、その周りに N軒の家があります。
# i番目の家は、湖の北端から時計回りに Aiメートルの位置にあります。
# 家の間の移動は、湖の周りに沿ってのみ行えます。
# いずれかの家から出発して N軒すべての家を訪ねるための最短移動距離を求めてください。

# 制約
#     2≤K≤106
#     2≤N≤2×105
#     0≤A1<...<AN<K
#     入力中のすべての値は整数である。

# 入力
# 入力は以下の形式で標準入力から与えられる。
# K N
# A1 A2 ... AN

# 出力
# いずれかの家から出発して N軒すべての家を訪ねるための最短移動距離を出力せよ。

# 入力例 1
# 20 3
# 5 10 15

# 出力例 1
# 10

# 1番目の家から出発し、2 番目、3 番目の家へ順に移動すると移動距離が 10になります。

# 入力例 2
# 20 3
# 0 5 15

# 出力例 2
# 10

# 2番目の家から出発し、1 番目、3 番目の家へ順に移動すると移動距離が 10 になります。


global FLAG_LOG
FLAG_LOG = False


def log(value):
    # FLAG_LOG = True
    # FLAG_LOG = False
    if FLAG_LOG:
        print(str(value))


def calculation(lines):
    # S = lines[0]
    # N = int(lines[0])
    K, N = list(map(int, lines[0].split()))
    values = list(map(int, lines[1].split()))
    # values = list(map(int, lines[2].split()))
    # values = list()
    # for i in range(N):
    #     values.append(int(lines[i]))
    # valueses = list()
    # for i in range(N):
    #     valueses.append(list(map(int, lines[i+1].split())))

    distances = list()
    distances.append(K+values[0] - values[N-1])
    for n in range(N-1):
        distances.append(values[n+1] - values[n])

    result = K - max(distances)

    return [result]


# 引数を取得
def get_input_lines(lines_count):
    lines = list()
    for _ in range(lines_count):
        lines.append(input())
    return lines


# テストデータ
def get_testdata(pattern):
    if pattern == 1:
        lines_input = ['20 3', '5 10 15']
        lines_export = [10]
    if pattern == 2:
        lines_input = ['20 3', '0 5 15']
        lines_export = [10]
    return lines_input, lines_export


# 動作モード判別
def get_mode():
    import sys
    args = sys.argv
    global FLAG_LOG
    if len(args) == 1:
        mode = 0
        FLAG_LOG = False
    else:
        mode = int(args[1])
        FLAG_LOG = True
    return mode


# 主処理
def main():
    import time
    started = time.time()
    mode = get_mode()
    if mode == 0:
        lines_input = get_input_lines(2)
    else:
        lines_input, lines_export = get_testdata(mode)

    lines_result = calculation(lines_input)

    for line_result in lines_result:
        print(line_result)

    # if mode > 0:
    #     print(f'lines_input=[{lines_input}]')
    #     print(f'lines_export=[{lines_export}]')
    #     print(f'lines_result=[{lines_result}]')
    #     if lines_result == lines_export:
    #         print('OK')
    #     else:
    #         print('NG')
    # finished = time.time()
    # duration = finished - started
    # print(f'duration=[{duration}]')


# 起動処理
if __name__ == '__main__':
    main()


Measured memory_bytes: 33772
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cfloat>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <queue>
#include <sstream>
#include <stack>
#include <time.h>
#include <vector>
#include <complex>
#include <map>
#include <set>
#include <iomanip>
#include <math.h>
#include <stdlib.h>
#include<list>
#include <utility>
#include <memory>
#include <cstring>
#include <fstream>
#include <numeric>
#include <assert.h>
using namespace std;
int a[100003];
int main(){
  int n,k,sml=100003,smlp=0;
  cin>>n>>k;
  for (int i=0;i<n;i++){
    cin>>a[i];
    if (sml>a[i]){
      sml=min(a[i],sml);
      smlp=i;
    }
  }
  int h=n-1-smlp,l=smlp,num=k-1;
  cout<<(h+l+num-1)/num;
  return 0;
}

Measured memory_bytes: 640
#include <stdio.h>

struct card{
	char mark[1];
	int value;
};

int main(){

	int N, min_j, flag=1, i, j;
	struct card c[36];
	struct card d[36];
	struct card temp;

	scanf("%d", &N);
	for(i=0; i<N; i++){
		scanf("%1s%d", c[i].mark, &c[i].value);
		d[i] = c[i];
	}

	//Bubble
	while(flag){
		flag = 0;
		for(i=N-1; i>=1; i--){
			if(c[i].value<c[i-1].value){
				temp = c[i];
				c[i] = c[i-1];
				c[i-1] = temp;
				flag = 1;
			}
		}

	}

	for(i=0; i<N; i++){
		if(i!=0){
			printf(" ");
		}
		printf("%s%d", c[i].mark, c[i].value);
	}
	printf("\nStable\n");


	//Select
	for(i=0; i<N; i++){
		min_j = i;
		for(j=i; j<N; j++){
			if(d[j].value<d[min_j].value){
				min_j = j;
			}
		}
		if(i!=min_j){
			temp = d[min_j];
			d[min_j] = d[i];
			d[i] = temp;
		}
	}

	flag = 0;

	for(i=0; i<N; i++){
		if(i!=0){
			printf(" ");
		}
		printf("%s%d", d[i].mark, d[i].value);
		if(c[i].mark[0]!=d[i].mark[0]){
			flag = 1;
		}
	}
	printf("\n");

	if(flag==0){
		printf("Stable\n");
	}else{
		printf("Not stable\n");
	}

	return 0;
}

Measured memory_bytes: 612
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb = new Scanner(System.in);
		int s = kb.nextInt();
		int p = 1000 - s % 1000;
		if (p == 1000) {
			System.out.println(0);
		} else {
			System.out.println(p);
		}
		kb.close();
	}

}


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

typedef pair<long long, long long> ld;
const int mod = 1e9 + 7;

ld G(ld a) {
	bool bo = 0;
	if((a.first > 0 && a.second < 0) || (a.first < 0 && a.second > 0)) bo = 1;
	a.first = abs(a.first);
	a.second = abs(a.second);
	long long c = __gcd(a.first, a.second);
	a.first /= c;
	a.second /= c;
	if(bo) a.first *= -1;
	return a;
}

int P(int a, int b) {
	if(b == 0) return 1;
	if(b & 1) return (long long)P(a, b - 1) * a % mod;
	int t = P(a, b / 2);
	return (long long)t * t % mod;
}

int n, o;
long long x, y;
ld a, b;
map<ld, int> ma[2];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; ++i) {
		cin >> x >> y;
		if(x != 0 || y != 0) {
			if(x == 0) {
				++ma[0][{0, 1}];
			} else if(y == 0) {
				++ma[1][{0, 1}];
			} else {
				ld xy = G({x, y});
				b = G({-y, x});
				a = xy;
				if((x > 0 && y < 0) || (x < 0 && y > 0)) {
					++ma[0][a];
				} else {
					++ma[1][b];
				}
			}
		} else {
			++o;
		}
	}
	long long fp = 1;
	for(pair<ld, int> e : ma[0]) {
		(fp *= (P(2, e.second) + P(2, ma[1][e.first]) - 1) % mod) %= mod;
	}
	for(pair<ld, int> e : ma[1]) {
		if(ma[0][e.first] == 0) {
			(fp *= P(2, e.second)) %= mod;
		}
	}
	(fp += o) %= mod;
	if(fp == 0) fp = mod - 1;
	else --fp;
	cout << fp << endl;
	return 0;
}


Measured memory_bytes: 28480
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cmath>

using namespace std;

typedef long long ll;

int main(){
    int K, S;
    cin >> K >> S;
    
    vector<int> temp;
    for(int X = 0; X <= K; X++){
        for(int Y = 0; Y <= K; Y++){
            if(X + Y <= S){
                temp.push_back(X + Y);
            }
        }
    }
    int ans = 0;
    for(int i = 0; i < temp.size(); i++){
        if(S - temp[i] <= K){
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 35044
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
    int n,m;
    cin >> n >> m;
    vector<vector<int>> g(n);
    rep(i,m){
        int a,b;
        cin >> a >> b;
        a--;b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    int flag = 0;
    for(auto i:g[0]){
        for(auto j:g[i]){
            if(j==n-1) flag = 1; 
        }
    }
    if(flag) cout << "POSSIBLE" << endl;
    else cout << "IMPOSSIBLE" << endl;
}


Measured memory_bytes: 15108
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fi first
#define se second
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define rep11(i, n) for (int i = 1; i < (int)(n); ++i)
#define repo(i, o, n) for (int i = o; i < (int)(n); ++i)
#define repm(i, n) for (int i = (int)(n)-1; i >= 0; --i)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pb(n) push_back(n)
#define mp make_pair
#define MOD 1002000007
#define INF LONG_LONG_MAX

int main(){
    string s;
    cin>>s;
    int co_0=0;
    int co_1=0;
    for(int i=0; i<s.size(); i++){
        if (s[i]=='0' && i%2==0){
            co_0++;
        }
        else if(s[i]=='1' && i%2==1){
            co_0++;
        }
        else if(s[i]=='1' && i%2==0){
            co_1++;
        }
        else if(s[i]=='0'&& i%2==1){
            co_1++;
        }
    }
    cout<<min(co_0,co_1)<<endl;
    
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define emp emplace

using namespace std;
using ll = long long;
using ii = pair<int, int>;

double pd[310][310][310];

int main()
{
	int n;
	scanf("%d", &n);
	int cnt[3] = {0};
	for (int i = 0; i < n; i++)
	{
		int x;
		scanf("%d", &x);
		cnt[x-1]++;
	}
	for (int s = 1; s <= n; s++)
	{
		for (int i = s; i >= 0; i--)
		{
			for (int j = s - i; j >= 0; j--)
			{
				int k = s - i - j;
				double p[3] = {(1. * i)/n, (1. * j)/n, (1. * k)/n};
				double pstay =  1. - p[0] - p[1] - p[2];
				
				if (i)
					pd[i][j][k] += p[0] * (1. + pd[i-1][j][k]);
				if (j)
					pd[i][j][k] += p[1] * (1. + pd[i+1][j-1][k]);
				if (k)
					pd[i][j][k] += p[2] * (1 + pd[i][j+1][k-1]);

				pd[i][j][k] += pstay;
				pd[i][j][k] /= (1. - pstay);
			}
		}
	}
	printf("%.15lf\n", pd[cnt[0]][cnt[1]][cnt[2]]);
	return 0;
}



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

typedef long long ll;
typedef long double ld;

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

    ll a, b;
    cin >> a >> b;
    ll n = __gcd(a, b);
    int cnt = 1;
    for(ll i=2; i*i<=n; i++){
        if(n%i == 0){
            while(n%i == 0) n /= i;
            cnt++;
        }
    }
    if(n > 1) cnt++;
    cout << cnt;
    return 0;
}


Measured memory_bytes: 256
//AUTHOR:BlackBox Inc.//
#include<bits/stdc++.h>
#include<unordered_map>
#include<tr1/unordered_map>
#define ll long long
#define ull unsigned long long
#define vi vector<int>
#define vlli vector<long long int>
#define vvi vector<vector<int>>
#define vpii vector<pair<int,int>>
#define vs vector<string>
#define lin1(x) ll int x; x = scan();
#define lin2(x,y) ll int x, y; x = scan(), y = scan();
#define lin3(x,y,z) ll int x, y, z; x = scan(), y = scan(), z = scan();
#define pb(x) push_back(x)
#define makep(x,y) make_pair(x,y)
#define mx(a,b) (a)>(b)?(a):(b)
#define mn(a,b) (a)<(b)?(a):(b)
#define fori(s,e) for(i=s;i<=e;i++)
#define forj(s,e) for(j=s;j<=e;j++)
#define fork(s,e) for(k=s;k<=e;k++)
#define rep(i,s,e) for(int i=s;i<=e;i++)
#define brep(i,s,e) for(int i=s;i>=e;i--)
#define all(x) x.begin(),x.end()
#define mem(x,y) memset(x,y,sizeof(x));
#define bits1(x) __builtin_popcount(x)
#define pi 3.14159265358979323846264338327950
#define MOD7 1000000007
#define MOD9 1000000009
#define fast std::ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
using namespace std::tr1;

int main()
{
#ifdef RAHUL
    freopen("input.txt","r",stdin);
#endif
ll n;
cin>>n;
std::vector<int >rohan(n);

for (int i = 0; i < n; ++i)
{
    /* code */
    cin>>rohan[i];
}

ll count=0;
for (int i = 1; i < n-1; ++i)
{
    if(rohan[i]>rohan[i-1] and rohan[i+1]>rohan[i]){
        count++;
        //cout<<rohan[i]<<"\n";
    }
    if(rohan[i]<rohan[i-1] and rohan[i+1]<rohan[i]){
        count++;
        //cout<<rohan[i]<<"\n";
    }


    // if (rohan[i-1]>rohan[i] and rohan[i-1]<rohan[i+1])
    // {
    //     /* code */
    //     count++;
    // }
    // if (rohan[i]<rohan[i-1] and rohan[i]>rohan[i+1])
    // {
    //     /* code */
    //     count++;
    // }

    // if (rohan[i-1]<rohan[i] and rohan[i]>rohan[i+1])
    // {
    //     /* code */
    //     count++;
    // }
    // if (rohan[i-1]<rohan[i] and rohan[i-1]>rohan[i+1])
    // {
    //     /* code */
    //     count++;
    // }
    // if (rohan[i-1]<rohan[i] and rohan[i]>rohan[i+1])
    // {
    //     /* code */
    //     count++;
    // }
    /* code */
}


cout<<count<<endl;




return 0;
}




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

using namespace std;

int N;
int a[100000];

int main(){
    cin >> N;
    for(int i=0;i<N;i++){
        cin >> a[i];
    }
    long long sum = abs(a[0]) + abs(a[N-1]);
    for(int i=0;i<N-1;i++){
        sum += abs(a[i]-a[i+1]);
    }
    cout << sum - abs(a[0]) - abs(a[0]-a[1]) + abs(a[1]) << endl;
    for(int i=1;i<N-1;i++){
        cout << sum - abs(a[i-1]-a[i]) - abs(a[i]-a[i+1]) + abs(a[i-1]-a[i+1]) << endl;
    }
    cout << sum - abs(a[N-1]) - abs(a[N-1]-a[N-2]) + abs(a[N-2]) << endl;
    return 0;
}

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

int main() {
  string s;
  cin >> s;
  int cnt = 0;
  for (int i = 0; i < int(s.size()); i++) {
    if (s[i] == '1') {
      cnt++;
    }
  }
  cout << cnt << endl; 
}

Measured memory_bytes: 256
//  ?????§??????????±?
#include <iostream>
#include <cstdlib>
using namespace std;

int main(){
    int n,q,s,t;
    long long nowtem=0;
    cin>>n>>q>>s>>t;
    long long mountain[200005],dmoun[200005];
    for(int i=0; i<=n; i++){
        cin>>mountain[i];
        if(i) dmoun[i]=mountain[i]-mountain[i-1];
    }
    dmoun[n+1]=0;
    for(int i=1; i<=n; i++){
        if(dmoun[i]>=0) nowtem-=s*dmoun[i];
        else nowtem+=t*abs(dmoun[i]);
    }
    for(int i=0; i<q; i++){
        long long l,r,x,newd=0,oldd=0;
        cin>>l>>r>>x;
        
        if(dmoun[l]>=0) oldd-=s*dmoun[l];
        else oldd+=abs(dmoun[l])*t;
        if(dmoun[r+1]>=0) oldd-=s*dmoun[r+1];
        else oldd+=abs(dmoun[r+1]*t);
        
        dmoun[l]+=x;
        if(r!=n) dmoun[r+1]-=x;
        
        if(dmoun[l]>=0) newd-=s*dmoun[l];
        else newd+=abs(dmoun[l])*t;
        if(dmoun[r+1]>=0) newd-=s*dmoun[r+1];
        else newd+=abs(dmoun[r+1]*t);
        long long d=newd-oldd;
        nowtem+=d;
        cout<<nowtem<<endl;
    }
    return 0;
}

Measured memory_bytes: 6216
#include<stdio.h>
int main(void)
{
	int a,b,x,y;
	char o;
	while (1){
		scanf("%d %c %d",&a,&o,&b);
		if(o=='?') break;
		if(o=='+'){
			x=a+b;
		}
		else if(o=='-'){
			x=a-b;
		}
		else if(o=='*'){
			x=a*b;
		}
		else if(o=='/'){
			x=a/b;
		}
		printf("%d\n",x);
	}
	return 0;
}



Measured memory_bytes: 2664
import heapq
n,m = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n):
  a[i] = -a[i]
heapq.heapify(a)

for _ in range(m):
  x = heapq.heappop(a)
  x = -1 * (-1 * x // 2)
  heapq.heappush(a, x)
print(-sum(a))

Measured memory_bytes: 72428
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
ll GetDigit(ll num){ return log10(num)+1; } //numの桁数を求める

int main()
{   
    int a,p;
    cin >> a >> p;
    cout << (a*3+p)/2 << endl;
    return 0;
}

Measured memory_bytes: 3624
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize("unroll-loops,no-stack-protector")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
typedef long long ll;
typedef long double ld;
typedef pair<long long ,long long> ii; 	


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll n,m;
	cin >> n >> m;
	vector <ll> arr(n+1,0);
	vector <bool> solve(n+1,false);
	for (int z=0;z<m;z++){
		ll k;string s;
		cin >> k >> s;
		if (solve[k]) continue;
		if (s == "WA") arr[k]++;
		else {
			solve[k] = true;
		}
	}
	ll ans1 = 0, ans2 = 0;
	for (int z=0;z<n+1;z++){
		if (solve[z]){
			ans1++;
			ans2+= arr[z];
		}
	}
	cout << ans1 << " " << ans2 << endl;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define fin freopen("input", "r", stdin);
#define fout freopen("output", "w", stdout);
#define wt(x) cerr << #x << ": " << x << " ";
#define whatis(x) {cerr << #x << ": " << x << endl;}
#define whatis2(x, y) {wt(x); wt(y); cerr << endl;}
#define whatis3(x, y, z) {wt(x); wt(y); wt(z); cerr << endl;}
#define whatis4(x, y, z, a) {wt(x); wt(y); wt(z); wt(a); cerr << endl;}
using namespace std;

typedef long long ll; typedef unsigned long long ull; typedef long double ld;
const ll MOD = 1000000007; const ld PI = acos(-1.0);

template <typename T> inline T bigMod(T A,T B,T M = MOD){A %= M;T ret = 1;while(B){if(B & 1) ret = (ret * A) % M;A = (A * A) % M;B = B >> 1;}return ret;}
template <typename T> inline T invMod (T A,T M = MOD){return bigMod(A,M-2,M);}

string s;
int n;

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

    cin >> n;
    cin >> s;

    ll ans = 0;
    map <char, int> mp;
    for (auto i : s) mp[i] += 1;

    ans = (ll) mp['R'] * mp['G'] * mp['B'];
    ll minus = 0;

    for (int diff = 1; diff < n; ++diff) {
        for (int i = 0; i + 2*diff < n; ++i) {
            int r, g, b;
            r = i;
            g = i + diff;
            b = i + diff + diff;
            /* whatis3(r, g, b); */
            if (s[r] != s[g] && s[g] != s[b] && s[b] != s[r]) minus += 1;
        }
    }



    cout << ans - minus << endl;
    /* whatis(ans); */
    /* whatis(minus); */
    /* whatis(ans - minus); */


    


    return 0;
}


Measured memory_bytes: 3624
#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

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

	long long A, B;
	long long result = 0;

	cin >> A >> B;

	long long iter = 2;
	
	long long a = A / 2, b = B / 2;

	if (B % 2 == 0)
		result = (b - a) % 2;
	else
		result = (b - a + 1) % 2;

	
	for (int i = 0; i < 63; i++) {
		long long tmp = iter << 1;

		long long k1 = A % tmp;
		long long K1 = A / tmp;

		long long k2 = B % tmp;
		long long K2 = B / tmp;
		
		if (K1 == K2) {
			if (k1 < iter)
				k1 = iter;

			if (k2 >= iter)
				result += iter * ((k2 - k1 + 1) % 2);
		}
		else {
			long long bit1 = 0;
			long long bit2 = 0;

			if (k1 >= iter)
				bit1 = ((tmp - k1) % 2);
			else
				bit1 = 0;

			if (k2 >= iter)
				bit2 = !(k2 % 2);
			else
				bit2 = 0;

			result += (bit1^bit2) * iter;
		}

		iter = iter << 1;

		if (A / iter == 0 && B / iter == 0)
			break;
	}

	cout << result;
}

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

int main(){
  int N;
  int64_t T;
  cin >> N >> T;
  vector<int64_t> time(N);
  for(int i=0; i<N; i++){
    cin >> time.at(i);
  }

  int64_t ans = 0;
  if(N > 1){
    for(int i=1; i<N; i++){
      int64_t mid = time.at(i) - time.at(i-1);
      if(mid < T){
        ans += mid;
      }
      else{
        ans += T;
      }
    }
  }
  ans += T;
  cout << ans << endl;
}


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

int n, x, a, b;

int main(){
	scanf("%d", &n);
	a = 10000000;
	b = -10000000;
	while(n--){
		scanf("%d", &x);
		a = min(a, x);
		b = max(b, x);
	}
	printf("%d\n", b - a);
	return 0;
}


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

int main() {
  char a, b, c, d;
  cin >> a >> b >> c >> d;
  
  if (a == b && b == c) {
    cout << "Yes" << endl;
  }
  else if (b == c && c == d) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
}

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

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

    int n;
    cin >> n;
    string S;
    vector<int> dct1(26);
    vector<int> dct2(26);
    cin >> S;
    for (int j = 0; j < S.length(); j++) {
        dct1[S[j] - 'a'] += 1;
    }
    //それ以降とのmin
    for (int i = 1; i < n; i++) {
        cin >> S;
        for (int j = 0; j < S.length(); j++) {
            dct2[S[j] - 'a'] += 1;
        }
        for (int j = 0; j < dct1.size(); j++) {
            dct1[j] = min(dct1[j], dct2[j]);
        }
        fill(dct2.begin(), dct2.end(), 0);
    }
    string ans = "";
    for (int i = 0; i < dct1.size(); i++) {
        for (int j = 0; j < dct1[i]; j++) {
            ans += ('a' + i);
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
n, m = map(int, input().split())
l = list(map(int, input().split()))

l.sort()
d = l[len(l)-1] - l[0]
distance = []
sum = 0

for j in range(len(l)-1):
    distance.append( l[j+1] - l[j] )

distance.sort(reverse=True)

if n >= m:
    print("0")
else:
    for i in range(n-1):
        sum += distance[i]
    print(d-sum)


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

const string YES = "Yes";
const string NO = "No";

void solve(long long A, long long B, long long C){
    if(A<=C && C<=B) cout << YES << endl;
    else cout << NO << endl;
    
}

int main(){
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    long long C;
    scanf("%lld",&C);
    solve(A, B, C);
    return 0;
}


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

int top, S[1000];

void push(int x){
    S[++top] = x;
}

int pop(){
    top--;
    return S[top+1];
}   

int main(){
    int a,b;
    top = 0;
    char s[100];

    while(scanf("%s",s) != EOF){
        if(s[0] == '+'){
            a = pop();
            b = pop();
            push(a+b);
        }else if(s[0] == '-'){
            b = pop();
            a = pop();
            push(a-b);
        }else if(s[0] == '*'){
            a = pop();
            b = pop();
            push(a * b);
        }else{
            push(atoi(s));
        }
    }
    printf("%d\n", pop());

    return 0;
}


Measured memory_bytes: 2104
#include <iostream>
#include <algorithm>
using namespace std;
static const int N = 100;

int main()
{
  int n, p[N + 1], m[N + 1][N + 1];
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> p[i - 1] >> p[i];
  }

  for (int i = 1; i <= n; i++)
    m[i][i] = 0;

  for (int l = 2; l <= n; l++)
  {
    for (int i = 1; i <= n - l + 1; i++)
    {
      int j = i + l - 1;
      m[i][j] = (1 << 21);
      for (int k = i; k <= j - 1; k++)
      {
        m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
      }
    }
  }
  cout << m[1][n] << endl;
  return 0;
}



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

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vll = vector<ll>;
using P = pair<int, int>;

const int INF = 1e9;
const ll INFLL = 1e18;
const int MOD = 1e9 + 7;
const int NIL = -1;
const ld PI = acosl(-1);

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

int main(){
    int l, r;
    cin >> l >> r;

    const int mod = 2019;
    ll ans = mod;
    for(ll i = l; i < r; i++){
        for(ll j = i+1; j <= r; j++){
            ll res = (i*j) % mod;
            ans = min(ans, res);
            if(res == 0){
                cout << ans << endl;
                return 0;
            }
        }
    }

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

Measured memory_bytes: 256
n,k = map(int,input().split())
s = list(input())
if(s[k-1]=='A'):
    s[k-1]='a'
    print(''.join(s))
if(s[k-1]=='B'):
    s[k-1]='b'
    print(''.join(s))
if(s[k-1]=='C'):
    s[k-1]='c'
    print(''.join(s))


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

int N, K;
const int MAX_N = 1.0e5 + 100;
int h[MAX_N];

int main() {
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> h[i];

    int dp[N];
    dp[0] = 0;
    for (int i = 1; i < N; i++) dp[i] = 1.0e9;

    for (int i = 0; i < N; i++) {
        for (int j = 1; j <= K && i + j < N; j++) {
            dp[i+j] = min(dp[i+j], dp[i] + abs(h[i] - h[i+j]));
        }
    }

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


Measured memory_bytes: 1024
{-# LANGUAGE BangPatterns #-}
import Control.Monad
import Data.Maybe
import Debug.Trace
import Data.List
import qualified Data.Map.Strict as Map
import qualified Data.IntMap.Strict as IntMap
import qualified Data.Set as Set
import qualified Data.IntSet as IntSet
import Data.Functor
import Data.Array
-- import Data.Array.Unboxed
import Control.Monad.ST
import Data.Array.ST

main :: IO ()
main = do
  n <- readLn :: IO Int
  ss <- replicateM n getLine :: IO [String]
  print $ solve ss

solve :: [String] -> Int
solve ss = (min endWithA startWithB) + orgAb 
  - if endWithA > 0 
      then if endWithA == startWithB && startWithB == aAndB then 1 else 0
      else 0
  where
    endWithA = sum $ map countA ss
    startWithB = sum $ map countB ss
    orgAb = sum $ map countAb ss
    aAndB = sum $ map countAandB ss

    countAb (s:[]) = 0
    countAb (s1:s2:s3) = (if s1 == 'A' && s2 == 'B' then 1 else 0) + countAb (s2:s3)
    countA s = if last s == 'A' then 1 else 0
    countB s = if head s == 'B' then 1 else 0
    countAandB s = if head s == 'B' && last s == 'A' then 1 else 0


Measured memory_bytes: 5500
import java.util.Scanner;

public class Main{
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		int N = scan.nextInt();
		int A[] = new int[N-1];
		int result[] = new int[N];
		for(int i=0;i<N-1;i++) {
			A[i]=scan.nextInt();
		}
		for(int i=0;i<N;i++) {
			result[i] = 0;
		}
		for(int i : A) {
			result[i-1]++;
		}for(int i : result) {
			System.out.println(i);
		}

	}
}

Measured memory_bytes: 61940
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <climits>

using namespace std;

typedef pair<int, pair<int, int> > edge;

int n, m, l;
int vtx[256][256];
	
int solve(vector< vector<edge> > e){
	
	for(int i=0; i<=n; ++i){
		for(int j=0; j<=l; ++j){
			vtx[i][j]=INT_MAX;
		}
	}
	
	priority_queue<edge, vector<edge>, greater<edge> > qu;
	qu.push(make_pair(0, make_pair(1,l)));//d, now, money
	vtx[1][l]=0;
	
	while(!qu.empty()){
		
		edge t = qu.top();
		int now = t.second.first, money = t.second.second;
		qu.pop();
		
		for(int i=0; i<e[now].size(); ++i){
			
			int nxt = e[now][i].first,
				dst = e[now][i].second.first,
				ene = e[now][i].second.second;
				
			if( money-dst>=0 && vtx[nxt][money-dst] > vtx[now][money] ){
				vtx[nxt][money-dst] = vtx[now][money];
				qu.push(make_pair(vtx[nxt][money-dst], make_pair(nxt, money-dst)));
			}//employ guard
			
			if( vtx[nxt][money] > vtx[now][money] + ene ){
				vtx[nxt][money] = vtx[now][money] + ene;
				qu.push(make_pair(vtx[nxt][money], make_pair(nxt, money)));
			}//no guard
		}
		
	}
	
	int res = INT_MAX;
	
	for(int i=0; i<=l; ++i){
		res = min(res, vtx[n][i]);
	}
	
	return res;
}


int main(){
	
	while(cin>>n>>m>>l, (n||m||l)){
	
		vector< vector<edge> > e(n+1);
		
		int a, b, c, d;
		
		for(int i=0; i<m; ++i){
			cin>>a>>b>>c>>d;
			e[a].push_back(make_pair(b, make_pair(c, d)));//nxt, dst, ene
			e[b].push_back(make_pair(a, make_pair(c, d)));
		}
		
		cout << solve(e) << endl;
	}
	
	return 0;
}
	

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

namespace atcoder172
{
    class Program
    {
        static void Main(string[] args)
        {

            var s = Console.ReadLine();
            var t = Console.ReadLine();

            int ans = 0;
            for(var i=0;i<s.Length;i++)
            {
                if(s[i] != t[i])
                {
                    ans++;
                }
            }

            Console.WriteLine(ans);

        }
    }
}


Measured memory_bytes: 27368
#include <iostream>
#define llint long long
#define inf 1e18

using namespace std;

llint a, b;

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> a >> b;
	if(b % a == 0){
		cout << -1 << endl;
		return 0;
	}
	
	for(int i = 1; i <= a; i++){
		llint m = (i*b+(a-1))/a*a;
		if(i + m - i*b > m/a){
			cout << m << endl;
			return 0;
		}
	}
	cout << -1 << endl;
	
	return 0;
}


Measured memory_bytes: 3212
#include<iostream>
#include<cmath>
int main()
{
	long long a,b;
	scanf("%lld%lld",&a,&b);
	if(a<=b)
	{
		if((a>=0&&b>=0)||(a<0&&b<0))
		printf("%lld",b-a);
		if(a<0&&b>=0)
		{
			if(b==0)
			printf("%lld",b-a);
			else
			{
				if(-a<b)
		        printf("%lld",1+a+b);
		        else
		        printf("%lld",1-a-b);
			}
		}
	}
	else
	{
		if(a>=0&&b<0)
		{
			if(a>=-b)
			printf("%lld",1+a+b);
			else
			printf("%lld",1-a-b);
		}
		if((a<0&&b<0)||(a>=0&&b>=0))
		{
			if(b!=0)
		    printf("%lld",2+a-b);
			else
			printf("%lld",1+a-b);
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class T>
T pow_ (T x, T n, T M){
    uint64_t u = 1, xx = x;
    while (n > 0){
        if (n&1) u = u * xx % M;
        xx = xx * xx % M;
        n >>= 1;
    }
    return static_cast<T>(u);
};

int main() {
    string s;
    cin >> s;
    ll ans = 1;
    ll p = 1;
    reverse(s.begin(),s.end());
    s[0]++;

    s += '0';
    int cur = 0;
    while(s[cur] == '2') {
        s[cur+1]++;
        s[cur] = '0';
        cur++;
    }
    if(s.back() == '0') s.pop_back();
    reverse(s.begin(),s.end());
    for (int i = 1; i < s.size(); ++i) {
        ans = (ans*3)%MOD;
        if(s[i] == '1'){
            (p *= 2) %= MOD;
            (ans += p) %= MOD;
        }
    }
    cout << ans << "\n";
    return 0;
}

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

int main() {
  
  int N, A, B;
  cin >> N >> A >> B;
  
  if (N * A >= B){
	cout << B << endl;
  }
  else if (N * A < B){
	cout << N * A << endl;
  }

 }

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

int n;
int p[1000001];
int main() {
    cin >> n;
    int cnt = 0;
    for ( int i = 1; i < n+1; i++ ) cin >> p[i];
    for ( int i = 1; i < n+1; i++ ) {
        if ( i < n ) {
            if ( p[i] == i ) {
                cnt += 1;
                p[i] = p[i+1];
                p[i+1] = i;
            }
        } else {
            if ( p[i] == i ) cnt += 1;
        }
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 640
// {{{
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
// }}}

using ll = long long;

int main() {
    ll D, N; cin >> D >> N;
    ll ans = 1;
    if (N == 100) N += 1;
    for (int i = 0; i < D; ++i) ans *= 100;
    ans *= N;
    cout << ans << 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;
using ll = long long;

ll mod = 1'000'000'000 + 7;

int main(){
    int N,K; cin >> N>>K;
    vector<ll> A(N),B(N);
    rep(i,N) cin>>A[i];

    sort(A.begin(), A.end());
    B=A;
    reverse(A.begin(), A.end());

    // すべて負のとき
    if(A[0]<0 && K%2==1){
        ll ans=1;
        rep(i,K){
            ans *= A[i];
            ans %= mod;
        }
        if(ans<0){
            ans += mod;
            ans %= mod;
        }
        cout << ans << endl;
        return 0;
    }

    // A,Bのポインタ
    int a=0,b=0;
    ll ans=1;
    while(K>=2){
        ll x,y;
        x = A[a]*A[a+1];
        y = B[b]*B[b+1];

        if(x<y){
            y %= mod;
            ans *= y;
            ans %=mod;
            b +=2;
            K -=2;
        }else{
            //x %= mod;
            ans *= A[a];
            ans %= mod;
            a += 1;
            K -= 1;
        }
    }

    if(K==1){
        ans *=A[a];
        ans %=mod;
    }

    if(ans<0){
        ans += mod;
        ans %= mod;
    }
    cout << ans << endl; 
}


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

int main()
{
	long long sol1 = 1, sol2 = 1, n, a;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a;
		sol1 *= 3LL;
		if (a % 2 == 0) sol2 *= 2LL;  
	}
	cout << sol1 - sol2;
	return 0;
}

Measured memory_bytes: 256
n = int(input())
s = list(input())

count=[]
for i in range(26):
	count.append(1)

for i in s:
	if i == "a":
		count[0]=count[0]+1
	elif i == "b":
		count[1]=count[1]+1
	elif i == "c":
		count[2]=count[2]+1
	elif i == "d":
		count[3]=count[3]+1
	elif i == "e":
		count[4]=count[4]+1
	elif i == "f":
		count[5]=count[5]+1
	elif i == "g":
		count[6]=count[6]+1
	elif i == "h":
		count[7]=count[7]+1
	elif i == "i":
		count[8]=count[8]+1
	elif i == "j":
		count[9]=count[9]+1
	elif i == "k":
		count[10]=count[10]+1
	elif i == "l":
		count[11]=count[11]+1
	elif i == "m":
		count[12]=count[12]+1
	elif i == "n":
		count[13]=count[13]+1
	elif i == "o":
		count[14]=count[14]+1
	elif i == "p":
		count[15]=count[15]+1
	elif i == "q":
		count[16]=count[16]+1
	elif i == "r":
		count[17]=count[17]+1
	elif i == "s":
		count[18]=count[18]+1
	elif i == "t":
		count[19]=count[19]+1
	elif i == "u":
		count[20]=count[20]+1
	elif i == "v":
		count[21]=count[21]+1
	elif i == "w":
		count[22]=count[22]+1
	elif i == "x":
		count[23]=count[23]+1
	elif i == "y":
		count[24]=count[24]+1
	elif i == "z":
		count[25]=count[25]+1

result=1
for i in count:
	result=result*i

print((result-1)%(10**9+7))

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

int main() {
  string S;
  cin >> S;
  
  int count = 0;
  int sum = 0;
  
  for (int i = 0; i < S.size(); i++) {
    if (S.at(i) == 'A') {
      count++;
    }
    else if (S.at(i) == 'B'){
       sum++;
    }

  }
  if ( count == 3 || sum ==3 ) {
    cout << "No" << endl;
  }
 
  else {
    cout << "Yes" << endl;
  }
   
 }



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

using namespace std;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define SORT(c) sort((c).bigin(), (c).end())

int main()
{

    int n, tsum, t[110], v[110], l[110], r[110];
    cin >> n;
    v[0] = 0;
    tsum = 0;
    l[0] = 0;
    r[0] = 0;
    FOR(i, 1, n + 1)
    {
        cin >> t[i];
        l[i] = tsum;
        tsum += t[i];
        r[i] = tsum;
    }
    FOR(i, 1, n + 1)
    cin >> v[i];
    v[n + 1] = 0;
    l[n + 1] = tsum;
    r[n + 1] = tsum;

    //REP(i, n + 2)
    //cout << l[i] << " " << r[i] << endl;
    double ans;
    for (double x = 0.0; x < tsum; x += 0.5)
    {
        double minV1 = 1000000;
        double minV2 = 1000000;

        REP(j, n + 2)
        {
            double hoge;
            if (x < (double)l[j])
            {
                hoge = (double)v[j] + ((double)l[j] - x);
            }
            else if (x < (double)r[j])
            {
                hoge = (double)v[j];
            }
            else
            {
                hoge = (double)v[j] + (x - (double)r[j]);
            }

            minV1 = min(minV1, hoge);

            if (x + 0.5 < (double)l[j])
            {
                hoge = (double)v[j] + ((double)l[j] - x - 0.5);
            }
            else if (x + 0.5 < (double)r[j])
            {
                hoge = (double)v[j];
            }
            else
            {
                hoge = (double)v[j] + (x + 0.5 - (double)r[j]);
            }

            minV2 = min(minV2, hoge);
        }

        //cout << minV1 << " " << minV2 << endl;

        ans += (minV1 + minV2) * 0.25;
    }

    cout << fixed << setprecision(10) << ans << endl;

    return 0;
}

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

int main() {
    int n, s, num, count=0, left, right, mid;
    cin >> n;
    int a[n];
    for (int i=0; i<n; i++) {
        cin >> a[i];
    }
    left = 0;
    right = n;
    cin >> s;
    for (int j=0; j<s; j++) {
        cin >> num;
        while (left < right) {
            mid = (left+right)/2;
            if (a[mid] == num) {
                count ++;
                break;
            } else if (num < a[mid]) {
                right = mid;
            } else if (num > a[mid]) {
                left = mid + 1;
            }
        }
        left = 0;
        right = n;
    }
    
    cout << count << endl;
}


Measured memory_bytes: 3484
# 整数の入力
a = int(input())
# スペース区切りの整数の入力
array = list(map(int, input().split()))

# そこまでで最も高い場所の高さ
t = array[0]

result = 1

for i in range(1, a):
    if array[i] >= t:
        t = array[i]
        result += 1

print(result)


Measured memory_bytes: 2940
#include<bits/stdc++.h>
	using namespace std;
	typedef long long ll;
	#define PI 3.14159265358979
	#define EPS 1e-8
	#define mod  1000000007
	#define fi first
	#define se second
	#define mp make_pair
	#define pb push_back
 
	const ll INF=1e18;	
	const int N=1e5+50;
 
	vector<ll > g[100050];
	vector<vector<ll> > dp(100050,vector<ll>(2,-1));
	ll count(ll i,ll par,ll col)
	{
		if(dp[i][col]!=-1)	
			return dp[i][col];
		ll ans=1;
		
		for(auto j:g[i])
		{
			if(j==par)
				continue;
			ll res=0;
			if(col==0)
			{
				res+=count(j,i,0);
				res%=mod;
				res+=count(j,i,1);
				res%=mod;
				ans*=res;
			
			}
			else
			{
				ans*=count(j,i,0);
			}
			ans%=mod;
		}
		return dp[i][col]=ans;
	}
	
	int main()
	{
		ios_base::sync_with_stdio(false);
		cin.tie(NULL);cout.tie(0);
		
		ll n;
		cin>>n;
			
		for(ll i=1;i<n;i++)
		{
			ll u,v;
			cin>>u>>v;
			g[u].pb(v);
			g[v].pb(u);
		}
		
		ll ans=count(1,-1,0);
		ans+=count(1,-1,1);
		ans%=mod;
		cout<<ans;
		
	}


Measured memory_bytes: 22420
(h,w,m),*s=[[*map(int,i.split())]for i in open(0)]
r,c=[0]*-~h,[0]*-~w
for x,y in s:
    r[x]+=1
    c[y]+=1
R,C=max(r),max(c)
print(R+C-(r.count(R)*c.count(C)==sum(r[x]+c[y]==R+C for x,y in s)))


Measured memory_bytes: 127216
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 全方位木DP、葉側と根側
N = ir()
graph = [[] for _ in range(N+1)]  # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

MOD = 10 ** 9 + 7

fact = [1] * (N + 10)
for n in range(1, N + 10):
    fact[n] = n * fact[n - 1] % MOD
fact_inv = [1] * (N + 10)
fact_inv[-1] = pow(fact[-1], MOD - 2, MOD)
for n in range(N + 9, 0, -1):
    fact_inv[n - 1] = fact_inv[n] * n % MOD

root = 1
parent = [0] * (N+1)
order = []
stack = [root]
while stack:
    cur = stack.pop()
    order.append(cur)
    for next in graph[cur]:
        if next == parent[cur]:
            continue
        parent[next] = cur
        stack.append(next)

size_down = [0] * (N+1)  # 1-indexed
dp_down = [1] * (N+1)  # 葉側の組み合わせ
for v in order[::-1]:
    dp_down[v] *= fact[size_down[v]]
    dp_down[v] %= MOD
    p = parent[v]
    s = size_down[v] + 1
    size_down[p] += s
    dp_down[p] *= fact_inv[s] * dp_down[v]
    dp_down[p] %= MOD

size_up = [N-x-1 for x in size_down]  # 自分含めない
dp_up = [1] * (N+1)  # 根側の組み合わせ
for v in order[1:]:
    p = parent[v]
    x = dp_down[p]
    x *= dp_up[p]
    x *= fact_inv[size_down[p]]
    x *= fact[size_down[v] + 1]
    x *= pow(dp_down[v], MOD-2, MOD)
    x %= MOD
    x *= fact[size_up[v]-1]
    x *= fact_inv[size_up[p]]
    dp_up[v] = x % MOD

size_up[1] = 0; dp_up[1] = 1
for xd, xu, sd, su in zip(dp_down[1:], dp_up[1:], size_down[1:], size_up[1:]):
    answer = xd * xu * fact[sd+su] * fact_inv[sd] * fact_inv[su] % MOD
    print(answer % MOD)


Measured memory_bytes: 125104
#include <iostream>
#include <vector>
#include <stack>

void fail() {
    std::cout << -1 << std::endl;
    exit(0);
}

int main() {
    int N;
    std::cin >> N;
    std::vector<int> b(N);
    for (auto& e : b) std::cin >> e;

    std::stack<int> ans;
    while (!b.empty()) {
        bool judge = false;
        for (int i = b.size() - 1; i >= 0; --i) {
            if (b[i] - i - 1 == 0) {
                ans.push(b[i]);
                b.erase(b.begin() + i);
                judge = true;
                break;
            }
        }
        if (!judge) fail();
    }

    while (!ans.empty()) {
        std::cout << ans.top() << std::endl;
        ans.pop();
    }
    return 0;
}


Measured memory_bytes: 256
while 1:
    n,m=map(int,input().split())
    if n==m==0:break
    ans=[[0,i+1] for i in range(m)]
    for i in range(n):
        a=list(map(int,input().split()))
        for j in range(m):
            if a[j]==1:
                ans[j][0]-=1
    ans.sort()
    ans2=[]
    for i in ans:
        ans2.append(i[1])
    print(' '.join(map(str, ans2)))


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

int main() {
  int n;
  cin >> n;
  vector<int>ki(100001);
  vector<int>gu(100001);
  rep(i,n){
    int a;
    cin >> a;
    if(i%2 == 0) ki[a]++;
    else gu[a]++;
  }
  int kimax = 0,kinem = 0,kmp = 0;
  int gumax = 0,gunem = 0,gmp = 0;
  for(int i = 0;i < 100001;i++){
    if(ki[i] > kimax){
      kinem = kimax;
      kimax = ki[i];
      kmp = i;
    }
    else if(ki[i] > kinem){
      kinem = ki[i];
    }
    if(gu[i] > gumax){
      gunem = gumax;
      gumax = gu[i];
      gmp = i;
    }
    else if(gu[i] > gunem){
      gunem = gu[i];
    }
  }
  int ans;
  if(kmp == gmp){
    if(kinem > gunem){
      ans = n-gumax-kinem;
    }
    else{
      ans = n-kimax-gunem;
    }
  }
  else{
    ans = n-kimax-gumax;
  }
  cout << ans << endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
 
#define ll long long
#define X first
#define Y second
#define MP make_pair
#define ld long double
 
using namespace std;
 
const int N = 1e5 + 12;
const ll mod = 1e9 + 7;

int dp[N], a[N], n;

int main () {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
 
    cin >> n;
    n = n * 2;
    for(int i = 1;i <= n;i++){
    	cin >> a[i];
    }

    sort(a + 1, a + n + 1);

    int res = 0;
    for(int i = 2;i <= n;i++){
    	dp[i] = max(dp[i - 1], dp[i - 2] + a[i - 1]);
    	//cout << dp[i] << " " << "\n" << "\n";
    	res = max(res, dp[i]);
    }
    cout << res;
}

Measured memory_bytes: 892
q = input().split()
q = [int(i) for i in q]

t = [q[0], q[1]]
a = [q[2], q[3]]

while True:
    a[0] = a[0] - t[1]
    if (a[0] <= 0):
        print("Yes")
        break

    t[0] = t[0] - a[1]
    if (t[0] <= 0):
        print("No")
        break



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

using namespace std;
#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define rep(i, n) for (int i = 0; i < (n); ++i)
#define sz(x) ll(x.size())
typedef long long ll;
//typedef pair<int, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = 10e10;
const ll MINF = -10e10;
//const int INF = INT_MAX;
#define mins(x, y) x = min(x, y)
#define maxs(x, y) x = max(x, y)

typedef priority_queue<P, vector<P>, greater<P> > PQ_ASK;
const int mod = 1000000007;
//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;

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

    if (s[0] != 'A') {
        cout << "WA" << endl;
        return 0;
    }

    bool b = [&] {
        int count = 0;
        for (int i = 2; i < s.size() - 1; i++) {
            if (s[i] == 'C') {
                count++;
            }
        }
        return count == 1;
    }();
    if (!b) {
        cout << "WA" << endl;
        return 0;
    }

    int count = 0;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] <= 'Z') {
            count++;
        }
    }

    if (count != 2) {
        cout << "WA" << endl;
        return 0;
    }

    cout << "AC" << endl;


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dis[2000005],f[100005],w[100005],cur;
vector<int>g[1000005];
vector<pair<int,int>>e[1000005],a;
queue<int>qu;
int get_f(int x)
{
	if(x==f[x])
		return x;
	return f[x]=get_f(f[x]);
}
void merge(int x,int y)
{
	if(w[x]!=cur)
	{
		w[x]=cur;
		a.push_back(make_pair(0,x));
		f[x]=x;
	}
	if(w[y]!=cur)
	{
		w[y]=cur;
		a.push_back(make_pair(0,y));
		f[y]=y;
	}
	f[get_f(x)]=get_f(y);
}
int main()
{
	int n,m,p,q,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&p,&q,&c);
		e[c].push_back(make_pair(p,q));
	}
	int sum=n;
	for(int i=1;i<=1000000;i++)
	{
		if(e[i].empty())
			continue;
		cur++;
		a.clear();
		for(int j=0;j<e[i].size();j++)
		{
			int x=e[i][j].first,y=e[i][j].second;
			merge(x,y);
		}
		for(int j=0;j<a.size();j++)
			a[j].first=get_f(a[j].second);
		sort(a.begin(),a.end());
		for(int j=0,k=0;j<a.size();j=k)
		{
			sum++;
			while(k<a.size()&&a[j].first==a[k].first)
			{
				g[sum].push_back(a[k].second);
				g[a[k++].second].push_back(sum);
			}
		}
	}
	for(int i=0;i<=sum;i++)
		dis[i]=-2;
	dis[1]=0;
	qu.push(1);
	while(!qu.empty())
	{
		int k=qu.front();
		qu.pop();
		for(int i=0;i<g[k].size();i++)
		{
			int v=g[k][i];
			if(dis[v]==-2)
			{
				dis[v]=dis[k]+1;
				qu.push(v);
			}
		}
	}
	printf("%d\n",dis[n]/2);	
	return 0;
}


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

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//int dx[] = { 1, -1 , 0 , 0 };
//int dy[] = { 0,  0,  1, -1 };
int dx[] = { 1, 0 };
int dy[] = { 0, 1 };
ll MOD = 1000000007;

unsigned long long str_to_int(std::string str) {
	unsigned long long ret;
	std::stringstream ss; ss << str;
	ss >> ret;
	return ret;
}

void solve(){
	string s,t;
	cin >> s >> t;
	string ans = "";
	rep(i,min(s.length(),t.length())){
		ans = ans + s[i] + t[i];
	}
	if(s.length() - t.length() == 1){
		ans = ans + s[s.length()-1];
	}
	P(ans);
}

int main() {
	solve();
	return 0;
}

Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn=5005,mod=1e9+7;

int dp[maxn][maxn],g[maxn],n,tmp[maxn];
struct edge
{
    int v,nxt;
}e[maxn<<1];
int head[maxn],kt,siz[maxn];

inline void adde(int u,int v) {e[++kt]=(edge){v,head[u]};head[u]=kt;}

template<typename T>
inline void read(T &x)
{
    char c;int f=1;
    while(!isdigit(c=getchar())) (c=='-')&&(f=-1);
    x=c^48;
    while(isdigit(c=getchar())) x=x*10+(c^48);
    x*=f;
}

void dfs(int u,int f)
{
    siz[u]=dp[u][1]=1;
    for(int i=head[u];i;i=e[i].nxt)
    {
        if(e[i].v==f) continue;
        int v=e[i].v;
        dfs(v,u);
        for(int j=1;j<=siz[u]+siz[v];++j) tmp[j]=0;
        for(int j=1;j<=siz[u];++j)
            for(int k=0;k<=siz[v];++k)
                tmp[j+k]=(tmp[j+k]+1ll*dp[u][j]*dp[v][k]%mod)%mod;
        siz[u]+=siz[v];
        for(int j=1;j<=siz[u];++j)
            dp[u][j]=tmp[j];
    }
    for(int i=2;i<=siz[u];i+=2)
        dp[u][0]=(dp[u][0]-1ll*dp[u][i]*g[i]%mod+mod)%mod;
}

int main()
{
    int u,v;
    read(n);
    for(int i=1;i<n;++i)
    {
        read(u);read(v);
        adde(u,v);adde(v,u);
    }
    g[2]=1;
    for(int i=4;i<=n;i+=2)
        g[i]=1ll*g[i-2]*(i-1)%mod;
    dfs(1,0);
    printf("%d\n",mod-dp[1][0]);
    return 0;
}

Measured memory_bytes: 58200
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = 1; i < (int)(n+1); i++)
int gcd(ll N){
    ll ans=1;
    for(ll i=sqrt(N)+1; 0<i; i--){
        if(N%i==0){
            ans=i;
          	break;
        }
    }
    return ans;
}
int digsum(ll N){
    bool a=true;
    ll ans=0;
    while(a==true){
        if(0<N){
            ans++;
            N-=N%10;
            N/=10;
        }
        else{
            a=false;
        }
    }
    return ans;
}
int main() {
    ll N;
    cin>>N;
     ll A=gcd(N);
     ll B=N/A;
    cout<<max(digsum(A),digsum(B))<<endl;
    }


Measured memory_bytes: 3656