akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<stdbool.h>
typedef long long ll;
typedef long double ld;
#define rep(i,l,r)for(ll i=(l);i<(r);i++)
#define repp(i,l,r,k)for(ll i=(l);i<(r);i+=(k))
#define rrep(i,l,r)for(ll i=(l);i>=(r);i--)
#define INF (1LL<<60)
#define MOD1 1000000007
#define MAX_N (1 << 17)
#define YES printf("Yes\n")
#define NO printf("No\n")


void swap(ll *a, ll *b){ll c;c=*b;*b=*a;*a=c;}
ll max2(ll a,ll b){return a>=b?a:b;}
ll min2(ll a,ll b){return a>=b?b:a;}
ll minn(ll n, ll a[n]){ll b=INF;rep(i,0,n) b=min2(b,a[i]);return b;}
ll maxn(ll n, ll a[n]){ll b=-INF;rep(i,0,n) b=max2(b,a[i]);return b;}
ll ABS(ll a){return a>=0?a:(-a);}
ll POW(ll a, ll b){ll c=1;rep(i,0,b) c*=a;return c;}
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 upll(const void*a, const void*b){return*(ll*)a<*(ll*)b?-1:*(ll*)a>*(ll*)b?1:0;}
int downll(const void*a, const void*b){return*(ll*)a<*(ll*)b?1:*(ll*)a>*(ll*)b?-1:0;}
void sortup(ll*a,int n){qsort(a,n,sizeof(ll),upll);}
void sortdown(ll*a,int n){qsort(a,n,sizeof(ll),downll);}

typedef struct{
    ll aa;
    ll bb;
}frequent;

int main(void){
    // char ;
    ll n;
    scanf("%lld",&n);
    ll x[n],y[n],h[n];
    rep(i,0,n){
        scanf("%lld%lld%lld",&x[i],&y[i],&h[i]);
    }
    ll H,d=0,hma;
    rep(i,0,101){
        rep(j,0,101){
            d=0;
            hma=INF;
            rep(k,0,n){
                if(d==0){
                    if(h[k]>0){
                        H = h[k] + ABS(i-x[k]) + ABS(j-y[k]);
                        // printf("%lld ",H);
                        if(H>hma || H<1){
                            break;
                        }
                        d++;
                    }else{
                        hma = min2( ABS(i-x[k]) + ABS(j-y[k]) , hma);
                    }
                }else{
                    if( h[k] != max2( H - (ABS(i-x[k]) + ABS(j-y[k]) ) , 0 ) ) break;
                }
                if(k==n-1){
                    printf("%lld %lld %lld\n",i,j,H);
                    return 0;
                }
            }
        }
    }
    return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;
import static java.lang.Math.*;
class Main{
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		int map[][] = new int [105][105];
		int x = 0,
			last = 0;
		String temp [];
		while(true){
			
			temp  = sc.next().split(",");
			for(int i = 0; i < temp.length; i++){
				map[x][i] = Integer.parseInt(temp[i]);
			}
			x++;
			if(!sc.hasNext())break;
		}
	
		int Memo[][] = new int [105][105];
		Memo[0][0] = map [0][0];
		for(int i = 0; i < 100; i++){
			if(x/2 > i){
				Memo[i + 1][0] =  max(Memo[i][0], Memo[i][0]) + map[i + 1][0];
				for(int j = 1; j < 100; j++){  
					Memo[i + 1][j] = max(Memo[i][j], Memo[i][j - 1]) + map[i + 1][j];
				}
			}else {
				for(int j = 0; j  < 100; j++){
					Memo[i + 1][j] = max(Memo[i][j],Memo[i][j + 1]) + map[i + 1][j];
				} 
				
			} 
			  
		}
		/******************************************
		for(int i = 0; i < 100; i ++){
			for(int j = 0; j < 100; j++){
				System.out.print(Memo[i][j] + "|"); 
			}
			System.out.println();
		}	/************************
		for(int i = 0; i < 100; i ++){
			for(int j = 0; j < 100; j++){
				System.err.print(map[i][j] + "|");
			}
			System.out.println();
		}
		**********************************************/
		System.out.println(Memo[100][0] + last);
	}
} 

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

int main()
{
        int a, b, c;
        cin >> a >> b >> c;
        int counter = 0;

        for(int i = a; i <= b; i++) {
                if (c % i == 0) counter++;
        };

        cout << counter << endl;
        return 0;
}

Measured memory_bytes: 3080
import java.util.*;

public class Main {
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		long A = sc.nextLong();
		long B = sc.nextLong();
		long C = sc.nextLong();
		long D = sc.nextLong();
		
		long lcm = (C * D) / gcd(D, C);
		long b = B - (B/C) - (B/D) + (B/lcm);
		long a = (A-1) - ((A-1)/C) - ((A-1)/D) + ((A-1)/lcm);
		
		System.out.println(b-a);
	}		
	
	 private static long gcd(long a, long b) {
		    if (b == 0) {
		      return a;
		    }
		    return gcd(b, a%b);
		  }
}


Measured memory_bytes: 22608
import sys

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def solve(inputs):
    A = string_to_int(inputs[0])
    if sum(A) >= 22:
        return "bust"
    return "win"


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(1))
    print(ret)


Measured memory_bytes: 38256
n, k, q = [int(i) for i in input().split()]
a = [0] + [int(input()) for _ in range(q)]
score = [0] + [0] * n

for i in range(1, q + 1):
    score[a[i]] += 1
for i in range(1, n + 1):
    if score[i] - q + k > 0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 57560
#include<bits/stdc++.h>
#define int long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define PI acos(-1)
#define bp __builtin_popcountll
#define all(x) x.begin(),x.end()
#define sp fixed<<setprecision
#define pii pair<long long,long long>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int MOD = (1e9)+7;
const int N = 200005;

int root[N],siz[N];

int get_root(int c)
{
    if(root[c]==c)return c;
    return root[c] = get_root(root[c]);
}
void _union(int a, int b)
{
    a = get_root(a);
    b = get_root(b);
    if(a<=b)root[b]=a,siz[a]+=siz[b];
    else root[a]=b,siz[b]+=siz[a];
}
void init(int n)
{
    for(int i=1;i<=n;i++)root[i]=i,siz[i]=1;
}


signed main()
{
    FAST
    int tc=1;
    //cin>>tc;
    for(int ti=1;ti<=tc;ti++)
    {
        int n;
        cin>>n;
        init(n);
        vector<pair<pii,int>> a(n);
        for(int i=0;i<n;i++)
        {
            int x,y;
            cin>>x>>y;
            a[i] = {{x,y},i};
        }
        sort(all(a));
        set<int> s;
        for(int i=0;i<n;i++)
        {
            //for(int x:s)cout<<x<<" - ";cout<<endl;
            int now = a[i].ff.ss;
            if(!s.size()){s.insert(now);continue;}
            auto it = s.begin();
            if(*it > now){s.insert(now);continue;}
            int r = *it;
            vector<int> v;
            it++;
            while(it != s.end())
            {
                if(*it > now)break;
                _union(r,*it);
                v.pb(*it);
                it++;
            }
            for(auto u:v)s.erase(u);
            _union(now,r);
        }
        int ans[n];
        for(int i=0;i<n;i++)
        {
            int now = get_root(a[i].ff.ss);
            ans[a[i].ss] = siz[now];
        }
        for(int i=0;i<n;i++)cout<<ans[i]<<endl;
    }
    return 0;
}


Measured memory_bytes: 15244
N = int(input())
list_trans = [int(input()) for i in range(5)]

list_trans.sort()

if N % list_trans[0] == 0:
	time = N // list_trans[0]
elif N % list_trans[0] != 0:
	time = N // list_trans[0] + 1
print(time + 4)

Measured memory_bytes: 3060
//=============================================================
// Name        : d
// Date        : Thu Jul  4 09:41:30 CST 2019
// Accepted    : Thu Jul  4 09:59:37 CST 2019
// Author      : landcold7
// Description : Actions speak louder more than words
//=============================================================
#include <bits/stdc++.h>
using namespace std;

#define x first
#define y second
#define sz(x) ((int)(x).size())
#ifndef _has_trace
#define trace(...)
#endif
typedef long long ll;

const int mod = 1e9 + 7;

void solve() {
  int n, k;
  cin >> n >> k;
  const int maxn = 2400;
  vector<vector<int>> dp(maxn, vector<int>(maxn));
  for (int i = 0; i < maxn; ++i) {
    dp[i][0] = 1;
    for (int j = 1; j <= i; ++j) {
      dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
      dp[i][j] %= mod;
    }
  }
  for (int i = 1; i <= k; ++i) {
    int r = n - k;
    int x = dp[r + 1][i];
    int y = dp[k - 1][i - 1];
    cout << ((ll)x * y % mod) << "\n";
  }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}


Measured memory_bytes: 22912
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    int d = a - b;
    if(d<c){
      cout << c-d << endl;
    }else{
      cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
/*g++ main.cpp -o main.out*/
/*./main.out*/
/*std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);*/

#include<bits/stdc++.h>
using namespace std;

#define LL long long
#define Mod 1000000007
#define L_Mod 17100000013

const double eps = 1e-9;
const int INF = 0x3f3f3f3f;
const double PI = 3.1415926535;

#define NO_TLE std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

#define ree(n,a) memset(n,a,sizeof(n));

#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define red(i,l,u) for(int (i)=(int)(l);(i)>=(int)(u);--(i))

int a[100005];

int main()
{
    LL n;
    cin>>n;
    cout<<n*(n-1)/2<<endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>


int main(void)
{
	int a,b;
	scanf("%d %d",&a,&b);
	int k;
	if((a+b) % 2 == 1) printf("IMPOSSIBLE");
	else {
		k = (a+b)/2;
		printf("%d",k);
	}
	
	return 0;
}



Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <memory>
#include <string>

#include <algorithm>
#include <complex>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>

using namespace std;

#ifdef _MSC_VER
#define __typeof__ decltype
#endif

#define ITER(c)         __typeof__((c).begin())
#define FOREACH(it, c)  for (ITER(c) it=(c).begin(); it != (c).end(); ++it)
#define RITER(c)        __typeof__((c).rbegin())
#define RFOREACH(it, c) for (RITER(c) it=(c).rbegin(); it != (c).rend(); ++it)
#define REP(i, n)       REPEAT(i, 0, n)
#define REPEAT(i, k, n) for (int i = (k); i < (n); ++i)
#define REVREP(i, n)    for (int i = ((n)-1); i >= 0; --i)
#define FIND(c, n)      std::find((c).begin(), (c).end(), (n));
#define BSEARCH(c, n)   std::binary_search((c).begin(), (c).end(), (n))
#define LLPOW(p1,p2)    ((ll)pow((double)(p1), (int)p2))
#define ESIZEOF(A)      (sizeof(A)/sizeof((A)[0]))
#define MIN(p1,p2)      (((p1)<(p2))?(p1):(p2))
#define MAX(p1,p2)      (((p1)>(p2))?(p1):(p2))
#define CIN_NO_SYNC     do { cin.tie(0); ios_base::sync_with_stdio(false); } while(0)
#define GETSTR(p)       fgets((p), sizeof(p), stdin)
#define CHOMP(p)        do{ char *_q = (p) + strlen(p)-1; if(*_q == '\n') *_q = 0; } while(0)

int main(){
    int h, w;
    cin >> h >> w;

    int **t = new int*[h+1];
    REP(i,h+1){
        t[i] = new int[w+1];
    }
    REP(i,h+1) REP(j,w+1) t[i][j] = 0;

    REP(i,h) REP(j,w){
        int n;
        cin >> n;
        t[i][j] = n;
        t[i][w] += n;
        t[h][j] += n;
        t[h][w] += n;
    }
    REP(i,h+1){
        REP(j,w+1){
            cout << (j!=0?" ":"") << t[i][j];
        }
        cout << endl;
    }

    return 0;
}

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

using ll = long long;
using Pi = pair<int, int>;
using Pl = pair<ll, ll>;
using vint = vector<int>;
using vll = vector<ll>;
using uint = unsigned int;
using ull = unsigned long long;

template<typename T> using uset = unordered_set<T>;
template<typename T1, typename T2> using umap = unordered_map<T1, T2>;

constexpr int INF = (1 << 30) - 1;
constexpr ll LLINF = 1LL << 60;
constexpr int dy[] = {1, 0, -1, 0, 1, -1, -1, 1};
constexpr int dx[] = {0, 1, 0, -1, 1, 1, -1, -1};
constexpr char el = '\n';
constexpr int mod = 1000000007;

template<typename T> T gcd(T a, T b) { return (b ? gcd(b, a % b) : a); }
template<typename T> T lcm(T a, T b) { return (a / gcd(a, b) * b); }
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }

template<typename T>
ostream& operator <<(ostream &os, vector<T> &v) {
	for (auto &u : v) os << u << el;
	return (os);
}

template<typename T>
istream& operator >>(istream &is, vector<T> &v) {
	for (auto &u : v) is >> u;
	return (is);
}

template<typename T1, typename T2>
istream& operator >>(istream &is, pair<T1, T2> &p) {
	return (is >> p.first >> p.second);
}

int main() {
	ll X, K; cin >> X >> K;
	
	vll datl(K+1), datr(K+1);
	vll low(K+1), high(K+1);
	vll R(K+1);
	
	datl[0] = 0, datr[0] = X;
	low[0] = 0, high[0] = X, R[0] = 0;
	for (int i = 1; i <= K; i++) {
		cin >> R[i];
		ll diff = R[i] - R[i-1];
		tie(datl[i], datr[i], low[i], high[i]) = tie(datl[i-1], datr[i-1], low[i-1], high[i-1]);
		if (i & 1) {
			datl[i] -= diff;
			datr[i] -= diff;
		} else {
			datl[i] += diff;
			datr[i] += diff;
		}
		if (datl[i] < 0) {
			low[i] = min(low[i] - datl[i], high[i]);
			datl[i] = 0;
		}
		datr[i] = max(0ll, datr[i]);
		if (datr[i] > X) {
			high[i] = max(high[i] - (datr[i] - X), low[i]);
			datr[i] = X;
		}
		datl[i] = min(X, datl[i]);
	}
		
	int Q;
	cin >> Q;
	while (Q--) {
		ll t, a;
		ll pos;
		cin >> t >> a;
		pos = --upper_bound(begin(R), end(R), t) - begin(R);
		a = max(min(a, high[pos]), low[pos]);
		ll x = datl[pos] + (a - low[pos]);
		ll diff = t - R[pos];
		if (pos & 1) x = min(x + diff, X);
		else x = max(x - diff, 0ll);
		cout << x << el;
	}

	return (0);
}

Measured memory_bytes: 5120
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#ifdef XVENOM
	#define errp(...) fprintf(stderr, __VA_ARGS__)
	#define dbg(...) errp("[%s]: ", #__VA_ARGS__), dbg_str(__VA_ARGS__)
#else
	#define errp(...)
	#define dbg(...)
#endif
template <typename U, typename V> string to_string (pair<U, V>);
string to_string (const string& e_) { return "\"" + e_ + "\""; }
string to_string (char e_) { return "\'" + string(1, e_) + "\'"; }
string to_string (bool e_) { return e_ ? "true" : "false"; }
template <typename T> string to_string (T e_) {
	string s_ = "[ ";
	for (const auto& x_ : e_) s_ += to_string(x_) + " ";
	return s_ + "]";
}
template <typename U, typename V> string to_string (pair<U, V> e_) {
	return "(" + to_string(e_.first) + ", " + to_string(e_.second) + ")";
}
void dbg_str () { errp(" \n"); }
template <typename U, typename... V> void dbg_str (U u, V... v) {
	errp(" %s", to_string(u).c_str()); dbg_str(v...);
}
/* --- */

int main () {
	ios_base::sync_with_stdio(0); cin.tie(0);
	/* --- */
	ll n, a, b, c, d, e, time = 4, mn;
	cin >> n;
	cin >> a;
	cin >> b;
	mn = min(a,b);
	cin >> c;
	mn = min(mn,c);
	cin >> d;
	mn = min(mn,d);
	cin >> e;
	mn = min(mn,e);

	time += ceil((n*1.0)/(mn*1.0));
	cout << time;
}	

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

int main(){
	int n,k; cin>>n>>k;
	if(n%2==0&&k<=n/2) cout<<"YES"<<endl;
	else if(n%2==1&&k<=(n+(2-1))/2) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
int arr[200005];
int n;
long long check(int x)
{
    long long ans = 0;
    for(int i = 1;i <= n;i++)
        ans += abs(arr[i] - (1LL*x+i));
    return ans;
}
int main(int argc, char* args[])
{

    cin >> n;
    for(int i = 1;i <= n;i++)
        cin >> arr[i];
     long long lo = -1e9;
    long long hi = 1e9;
    while(hi-lo >= 3)
    {
         long long part = (hi-lo)/3;
         long long f1 = lo + part;
         long long f2 = hi - part;
        if(check(f1) <  check(f2))
            hi = f2;
        else
            lo = f1;
    }
    long long Best = 1e18;
    for(int i = lo;i <= hi;i++)
        Best = min(Best,check(i));
    cout << Best;
}


Measured memory_bytes: 1024
#include <iostream>

using namespace std;

void insertationSort(int a[]) {
	for (int i = 1; i < 3; i++) {
		int val = a[i];
		int j = i -1;
		while (j >= 0 && a[j] > val) {
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = val;
	}
}

int main() {
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	insertationSort(a);
	cout << a[0] << " " << a[1] << " " << a[2] << endl;
}

Measured memory_bytes: 3100
#include <iostream>
#include <string>
#include <iomanip>
#include <cmath>
using namespace std;

int main (void){  
    string s, t;
    int cnt = 0;
    cin >> s >> t;
    for (int i = 0; i < s.length(); i++) {
        if (s[i] == t[i]) {
            cnt++;
        }
    }

    if (s.length() == cnt) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    return 0;
}

Measured memory_bytes: 3600
#include<iostream>

using namespace std;

int main() {
	int N, A, B;
	cin >> N >> A >> B;

	int Q = N * A;

	if (Q < B) {
		cout << Q << endl;
	}
	else if (Q > B) {
		cout << B << endl;
	}
	else cout << Q << endl;

	return 0;
}

Measured memory_bytes: 256
#!/bin/sh
read a b
if [ $a -gt $b ] || [ $a -eq 1 ] && [ $b -ne 1 ] ; then
  echo "Alice"
elif [ $a -lt $b ] || [ $b -eq 1 ] && [ $a -ne 1 ] ; then
  echo "Bob"
elif [ $a -eq $b ] ; then
  echo "Draw"
fi
# read a b
# num1=`expr $a + $b`
# if [ $num1 -ge 24 ]; then
#   num2=`expr $num1 \- 24`
#   echo $num2
# else
#   echo $num1
# fi
# read a b c d
# num1=`expr $a \* $b`
# num2=`expr $c \* $d`
# if [ $num1 -gt $num2 ]; then
#   echo $num1
# else
#   echo $num2
# fi

Measured memory_bytes: 376
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<queue>
#include<map>
using namespace std;
#define REP(i, limit) for(int i=0; i< limit; ++i)
#define LINT long long

int main(){
  int N, H;
  cin>>N>>H;
  int a, b[N];
  int amax=0;
  REP(i, N){
    cin>>a>>b[i];
    amax=max(amax, a);
  }
  sort(b, b+N, greater<int>());
  int ans=1000000000;
  int work;
  REP(i, N){
    if(b[i]<amax) break;
    H -= b[i];
    if(H<=0){
      ans = min(ans, i+1);
      break;
    }
    if(amax==1) ans = min(ans, i+1 + H);
    else ans = min(ans, i+1 + (H+amax-1)/amax);
  }
  cout<<ans<<endl;


  return 0;
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
#define mp       make_pair
#define pb       push_back
#define all(x)   (x).begin(),(x).end()
#define YES() printf("YES\n")
#define NO() printf("NO\n")
#define Yes() printf("Yes\n")
#define No() printf("No\n")
using namespace std;

#define int long long
//typedef    long long          ll;
typedef    vector<bool>       vb;
typedef    vector<int>        vi;
typedef    vector<vb>         vvb;
typedef    vector<vi>         vvi;
typedef    pair<int,int>      P;
 
const int INF=1e+9;
const double EPS=1e-9;
const int MOD=1000000007;
 
const int dx[]={1,0,-1,0},dy[]={0,-1,0,1};

int n,ans = 0,a[100000],b[100000];

int calc(int k){
	int res = 0;
	for(int i = 0;i < n;i++){
		bool flag = true;
		for(int j = 0;j < 32;j++){
			if(((k >> j) & 1) < ((a[i] >> j) & 1)) flag = false;
		}
		if(flag) res += b[i];
	}
	return res;
}

signed main(){
	int k,ma = 0;
	cin >> n >> k;
	for(int i = 0;i < n;i++) cin >> a[i] >> b[i];
	for(int i = 32;i >= 0;i--){
		if((k >> i) & 1){
			ma = max(ma,calc(((k >> i) << i) - 1));
		}
	}
	ma = max(ma,calc(k));
	cout << ma << endl;
	return 0;
}

Measured memory_bytes: 1920
from fractions import gcd
n,k=map(int,input().split())
a=list(map(int,input().split()))
if n>=2:
  g=gcd(a[0],a[1])
  for j in range(1,n):
    g=gcd(g,a[j])
  m=max(a)
  if k<=m and k%g==0:print('POSSIBLE')
  else:print('IMPOSSIBLE')
else:
  if a[0]==k:print('POSSIBLE')
  else:print('IMPOSSIBLE')

Measured memory_bytes: 16240
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define RFOR(i,l,r) for(long long i=(l);i>=(r);--i)
#define RREP(i,n) RFOR(i,n-1,0)
#define RREPS(i,n) RFOR(i,n,1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define SZ(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true; }return false; }
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true; }return false; }
const int INF = 1e18;

int dep(int n){
    int ret = 0;
    while(n >= 2){
        n /= 2;
        ret++;
    }
    return ret;
}

int func(int n,int j){
    while(j--) n /= 2;
    return n;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //input
    int n; cin >> n;
    int v[n+1],w[n+1];
    REPS(i,n) cin >> v[i] >> w[i];
    int q; cin >> q;
    int M_L = 0;
    int t[q], l[q];
    REP(i,q){
        cin >> t[i] >> l[i];
        chmax(M_L,l[i]);
    }
    //半分全列挙
    int V = min((1ll << 9)-1, n);
    vector<vector<int>> dp(V+1,vector<int>(M_L+1,0));
    REPS(i,V) REP(j,M_L+1){
        chmax(dp[i][j], dp[i/2][j]);
        if(j - w[i] > -1) chmax(dp[i][j], dp[i/2][j-w[i]] + v[i]);
    }
    int z, o, ans, sumw, sumv, hoge[9];
    REP(i,q){
        if(t[i] <= V) cout << dp[t[i]][l[i]] << '\n';
        else{
            z = dep(t[i]) - 8;
            o = func(t[i],z);
            ans = 0;
            REP(j,z) hoge[j] = func(t[i],j);
            for(int b = 0; b < (1ll << z); b++){
                sumw = 0;
                sumv = 0;
                REP(j,z) if((b >> j) & 1){
                    sumw += w[hoge[j]];
                    sumv += v[hoge[j]];
                }
                if(l[i]-sumw > -1) chmax(ans, dp[o][l[i]-sumw] + sumv);
            }
            cout << ans << '\n';
        }
    }
}

Measured memory_bytes: 411044
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <string>
#include <stdlib.h>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <queue>
#include<unordered_map>
#define mod 1000000007
typedef unsigned long long int ll;
using namespace std;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    string s,t;
    cin>>s>>t;
    int c=0;
    for(int i=0;i<3;i++)
    {
        if(s[i]==t[i])
        c++;
    }
    cout<<c<<"\n";

    return 0;


    
    
}


Measured memory_bytes: 256
while True:
    try:
        y,m,d = map(int,input().split())
        if y < 1868 or (y == 1868 and m < 9):
            print("pre-meiji")
        elif y == 1868 and m == 9 and d < 8:
            print("pre-meiji")
        elif y < 1912 or (y == 1926 and m < 7):
            print("meiji",y - 1868 + 1,m,d)
        elif y == 1912 and m == 7 and d < 30:
            print("meiji",y - 1868 + 1,m,d)
        elif y < 1926 or (y == 1926 and m < 12):
            print("taisho",y - 1912 + 1,m,d)
        elif y == 1926 and m ==12 and d < 25:
            print("taisho",y - 1912 + 1,m,d)
        elif y <1989 or (y == 1989 and m == 1 and d < 8):
            print("showa",y - 1926 + 1,m,d)
        else:
            print("heisei",y - 1989 + 1,m,d)
    except EOFError:
        break

Measured memory_bytes: 7612
fun main(args: Array<String>) {
    val N = readLine()!!.toInt()
    val points = mutableListOf(Triple(0, 0, 0))
    for (n in 0 until N) {
        val (t, x, y) = readLine()!!.split(" ").map { it.toInt() }
        points.add(Triple(t, x, y))
    }
    var can = true
    for (i in 0 until N) {
        val p = points[i]
        val p1 = points[i + 1]
        val dt = p1.first - p.first
        val dist = kotlin.math.abs(p1.second - p.second) + kotlin.math.abs(p1.third - p.third)
        if (dt < dist) {
            can = false
        }
        if (dist % 2 != dt % 2) {
            can = false
        }
    }
    print(if (can) "Yes" else "No")
}


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

int main()
{
    int a, b, c;
    cin >> a >> b >> c;
    bool poor = false;
    if (a == b && a != c)
        poor = true;
    if (a == c && a != b)
        poor = true;
    if (c == b && a != c)
        poor = true;
    if (poor)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
    return 0;
}

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

using namespace std;
#define int long long
const int N = 666666 ,inf = 0x3f3f3f3f;

signed main(){
	int a,b,c;
	cin>>a>>b>>c;
	cout<<((int)ceil(a*1.0/b))*c;	
	return 0;
}

Measured memory_bytes: 3664
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

int main(){
	int n; cin >> n;
	vector<int> a(n);
	vector<int> b(n);
	for( int i = 0; i < n; ++i ){
		cin >> a[i];
		b[i] = a[i];
	}
	sort( b.begin(), b.end() );
	int maxv = b[n-1];
	int submaxv = b[n-2];
	for( int i = 0; i < n; ++i ){
		if( a[i] == maxv ){
			cout << submaxv << endl;
		} else {
			cout << maxv << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 3328
#define _USE_MATH_DEFINES
#define INF 10000000
#include <iostream>
#include <sstream>
#include <cmath>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>

using namespace std;

typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;

static const double eps = 1e-8;

int getAvr(int* p,int n){
	int sum = 0;
	for(int i=0;i<n;i++){
		sum += p[i];
	}

	return sum/3;
}

int main(){
	int n;	
	while(~scanf("%d",&n)){	
		if(n==0) break;
		
		for(int i=0;i<n;i++){
			int p[3];
			//math,english,japanese			
			scanf("%d %d %d",p,p+1,p+2);

			for(int i=0;i<3;i++){
				if(p[i]==100){
					printf("A\n");
					goto next;
				}
			}

			if(p[0] + p[1] >= 180 || getAvr(p,3) >= 80){
				printf("A\n");
			}

			else if(getAvr(p,3) >= 70
				|| (getAvr(p,3) >= 50 && (p[0] >= 80 || p[1] >= 80))){
				printf("B\n");
			}

			else{
				printf("C\n");
			}
next:;

		}
		
	}
}

Measured memory_bytes: 3044
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int MOD = (int)1e9 + 7;

bool check(vector<int>& a) {
    int n = a.size();
    vector<int> b(n);
    for (int i = 0; i < n; i++) {
        b[i] = abs(i - (n - i - 1));
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        if (a[i] != b[i]) return false;
    }
    return true;
}

int calc(int n) {
    int res = 1;
    for (int i = 0; i < n / 2; i++) {
        (res *= 2) %= MOD;
    }
    return res;
}

int main() {
    int n; cin >> n;
    vector<int> a(n);
    for (int& ai : a) cin >> ai;
    if (check(a)) {
        cout << calc(n) << endl;
    } else {
        cout << 0 << endl;
    }
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <string>


using namespace std;
int main()
{
	string s;
	cin >> s;
	int cnt = 0;
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'o') cnt++;
	}
	int y = 700;
	y += cnt * 100;
	cout << y << endl;

	return 0;
}



Measured memory_bytes: 256
n,m = map(int,input().split())
a = [int(x) for x in input().split()]
tmp = sum(a)
count = 0

for i in range(len(a)):
    if a[i] < tmp / 4 / m:
        continue
    else:
        count += 1

if count >= m:
    print("Yes")
else:
    print("No")


Measured memory_bytes: 2940
#include<bits/stdc++.h>
using namespace std;
//#include<boost/multiprecision/cpp_int.hpp>
//using boost::multiprecision::cpp_int;

#define int long long
#define cint cpp_int
#define endl "\n"
#define REP(i,a,n) for(int i=a;i<n;++i)
#define REPR(i,a,n) for(int i=a;i>n;--i)
#define RUP(a,b) ((a+b-1)/(b))
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define MOD 1000000007
#define INF LLONG_MAX/2
#define PI acos(-1.0)

typedef long long ll;
typedef pair<int,int> Pii;
typedef tuple<int,int,int> Tiii;
typedef vector<int> Vi;
typedef vector<Vi> VVi;
typedef vector<Pii> VPii;
typedef vector<string> Vs;

template<class T> inline bool chmax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T> inline bool chmin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T> void YesNo(T a) {cout<<(a?"Yes":"No")<<endl;}
template<class T> void YESNO(T a) {cout<<(a?"YES":"NO")<<endl;}
void vout(Vi &v){for(int i=0;i<(v).size();i++) cout<<v[i]<<" ";cout<<endl;}
void vvout(VVi &v){for(int i=0;i<(v).size();i++) vout(v[i]);}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a/gcd(a,b)*b;}
int mypow(int x, int n, int m){if(n==0)return 1;if(n%2==0)return mypow(x*x%m,n/2,m);else return x*mypow(x,n-1,m)%m;}
int digit(int k,int i){string s = to_string(k);return s[s.size()-i]-'0';}
void uniq(Vi &v){sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());}
int ctoi(char c){if(c>='0'&&c<='9'){return c-'0';}return 0;}
Vi accum(Vi v){Vi ret((v).size());ret[0]=v[0];REP(i,1,(v).size()) ret[i]=ret[i-1]+v[i];return ret;}
bool comp(Pii a,Pii b){
    if(a.second != b.second) return a.second<b.second;
    else return a.first<b.first;
}



void solve(std::string S, std::string T, long long A, long long B, std::string U){
    if(S==U) A--;
    if(T==U) B--;
    cout<<A<<" "<<B<<endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
signed main(){
    std::string S;
    std::cin >> S;
    std::string T;
    std::cin >> T;
    long long A;
    scanf("%lld",&A);
    long long B;
    scanf("%lld",&B);
    std::string U;
    std::cin >> U;
    solve(S, T, A, B, U);
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
#include<set>
#include<iomanip>
#include<cmath>
using namespace std;
typedef long long ll;
typedef long long int llint;
typedef pair<ll, ll> pa;
#define MM 1000000000
#define MOD MM+7
#define MAX 101000
#define MAP 110
#define initial_value -1
#define MAX_T 1001
#define Pair pair<int,int>
#define chmax(a,b) (a<b ? a=b:0)
#define chmin(a,b) (a>b ? a=b:0)
#define INF (1 << 29) //536870912
const long double PI = acos(-1);
const ll DEP = 1e18;
int dx[4] = {-1,0,1,0};
int dy[4] = {0,-1,0,1};
int main(){
    int a,b,t; cin >> a >> b >> t;
    int T = t/a;
    cout << T*b << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main{
  public static void main(String[]args){
    Scanner sc = new Scanner(System.in);
    int N = Integer.parseInt(sc.next());
    int H = Integer.parseInt(sc.next());
    int W = Integer.parseInt(sc.next());
    
    int ans = 0;
    for(int i = 0; i < N; i++){
      int a = Integer.parseInt(sc.next());
      int b = Integer.parseInt(sc.next());
      if(a >= H && b >= W){
        ans++;
      }
    }
    
    System.out.println(ans);
  }
}

Measured memory_bytes: 22612
// C++ 14
#include <bits/stdc++.h>
using namespace std;
template <typename T>  ostream& operator<<(ostream& os, const vector<T>& v)  {  os << "[";  for (int i = 0; i < v.size(); ++i) {  os << v[i];  if (i != v.size() - 1)  os << ", ";  }  os << "]";  return os;  }
template <typename T> void print(T v, string s = "\n") { cout << v << s; }
template <typename T> void in(T& v) { cin >> v; }
#define ll long long
#define loop(__x, __start, __end) for(int __x = __start; __x < __end; __x++)

int main() {
  int n;in(n);
  vector<ll> A(n);
  loop(i,0,n) in(A[i]);
  bool plus = false;
  bool minus = false;
  loop(i,0,n) plus |= A[i]>0, minus |= A[i]<0;
  vector<pair<int, int> > B;
  if (plus and minus) {
    int idx = -1;
    ll max_ = -1;
    loop(i,0,n) {
      if (max_ < abs(A[i])) {
        max_ = abs(A[i]);
        idx = i;
      }
    }
    
    loop(i,0,n) {
      if (i==idx) continue;
      A[i] += A[idx];
      B.emplace_back(idx, i);
    }
  }
  
  {
    plus = false;
    loop(i,0,n) plus |= A[i]>0;
    if (plus) {
      loop(i,0,n-1) B.emplace_back(i, i+1);
    }
    else {
      for (int i=n-2; i>=0;i--) B.emplace_back(i+1, i);
    }
  }
  
  {
    print(B.size());
    for (auto b: B) {
      cout << b.first + 1 << " " << b.second + 1 << endl;
    }
  }
  
  return 0;
}


Measured memory_bytes: 3592
def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

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

    
x,y=[int(i) for i in input().split()]

m=1000000007

    

if y<=2*x  and x<=2*y and (2*x-y)%3==0 and (2*y-x)%3==0:
    a=(2*y-x)//3
    b=(2*x-y)//3
    
    print(cmb(a+b,b,m))
else:
    print(0)

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

using namespace std;

int main()
{
    string S,T;
    getline(cin,S);
    getline(cin,T);

     if(S.substr(0,S.length())==(T.substr(0,(T.length()-1))))
   {
       cout << "Yes";
   }
   else
       cout<<"No";
    return 0;
}


Measured memory_bytes: 3596
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define rep(i, n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) do{}while(0)
#endif





ll n;

int main(){
	cin >> n;
	
	vector<ll> a(n);
	rep(i,n){
		cin >> a[i];
	}
	
	sort(a.begin(),a.end(),greater<ll>());
	priority_queue<ll> q;
	
	
	ll sum = 0;
	rep(i,SZ(a)){
		if ( i == 0 ){
			// 1人目は、心地よさa[i]の席を1個作る
			q.push(a[i]);
		}
		else {
			// それ以降の人は、席を消費して、心地よさa[i]の席を2個作る
			sum += q.top();
			q.pop();
			q.push(a[i]);
			q.push(a[i]);
		}
	}
	
	
	cout << sum << endl;
	
	return 0;
}




Measured memory_bytes: 6932
#include <bits/stdc++.h>
using namespace std;
int blk[100005];
int a[100005];
int aa[100005];
int bb[100005];
int main()
{
    int n,k;
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    n--;
    k--;
    int x=n/k;
    if(x*k!=n)
    {
        x++;
    }
    cout<<x<<endl;
}


Measured memory_bytes: 640
#include <stdio.h>

int main(void)	{

	int a, b;
	
	scanf("%d %d", &a, &b);
	
	if (a < b)	{
		printf("a < b\n");
	} else if (a > b)	{
		printf("a > b\n");
	} else	{
		printf("a == b\n");
	}
	
	return 0;
}


Measured memory_bytes: 2612
use std::io::stdin;

fn main() {
    let mut s = String::new();
    stdin().read_line(&mut s).ok();
    let s: String = s.trim().parse().unwrap();

    if (s.chars().nth(2) == s.chars().nth(3)) & (s.chars().nth(4) == s.chars().nth(5)) {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define big 1000000007

int main(){

    vector<int> a(5);
    rep(i,5){
    cin>>a[i];
    }
    int sum=0;
    int min=10;
    int last=0;
    rep(i,5){
        if(a[i]%10<=min && a[i]%10!=0){
            min=a[i]%10;
            last =i;
        }
    }
    rep(i,5){
        if(i==last){
            sum += a[i];
        }
        else{
            if(a[i]%10==0){
                sum +=a[i];
            }
            else{
            sum += a[i]+(10-a[i]%10);
            }
        }
    }
    cout<<sum<<endl;
    
    
}

Measured memory_bytes: 256
from collections import deque
def solve():
    H,W = map(int,input().split())
    Ch,Cw = map(lambda x:int(x)-1,input().split())
    Dh,Dw = map(lambda x:int(x)-1,input().split())
    A = [list(input()) for _ in range(H)]
    V = [[-1]*W for _ in range(H)]
    d = ((1,0),(0,1),(-1,0),(0,-1))

    def bfs_2d(sy,sx,v):
        que = deque()
        V[sy][sx] = v
        que.append((sy,sx))

        while que:
            uh, uw = que.popleft()
            for dy, dx in d:
                next_h = uh+dy
                next_w = uw+dx
                if 0 <= next_h < H and 0 <= next_w < W \
                    and A[next_h][next_w] == '.' \
                    and V[next_h][next_w] == -1:
                    V[next_h][next_w] = v
                    que.append((next_h,next_w))
    
    vertex = 0
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' or V[h][w] != -1:
                continue
            bfs_2d(h,w,vertex)
            vertex += 1

    G = [[] for _ in range(vertex)]
    used = [set() for _ in range(vertex)]
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                continue
            for dh in range(-2, 2+1):
                for dw in range(-2, 2+1):
                    if h + dh < 0 or H <= h + dh or w + dw < 0 or W <= w + dw:
                        continue
                    if A[h+dh][w+dw] == "#":
                        continue
                    if V[h][w] == V[h+dh][w+dw]:
                        continue
                    if V[h+dh][w+dw] in used[V[h][w]]:
                        continue
                    G[V[h][w]].append((V[h+dh][w+dw]))
                    used[V[h][w]].add((V[h+dh][w+dw]))
    
    # s = V[Ch][Cw]
    # g = V[Dh][Dw]

    # dist = [-1 for _ in range(vertex)]
    # que = deque()
    # dist[s] = 0
    # que.append(s)
    # while que:
    #     u = que.popleft()
    #     for v in G[u]:
    #         if dist[v] != -1:
    #             continue
    #         dist[v] = dist[u] + 1
    #         que.append(v)
    
    # print(dist[g])

    start_area_num = int(V[Ch][Cw])
    goal_area_num = int(V[Dh][Dw])

    visited = [False] * vertex
    visited[start_area_num] = True

    q = deque()
    q.append((start_area_num,0))
    while len(q) > 0:
        cur_area_num, warp_cnt = q.popleft()
        if cur_area_num == goal_area_num:
            print(warp_cnt)
            return
        
        for next_area_num in G[cur_area_num]:
            if not visited[next_area_num]:
                visited[next_area_num] = True
                q.append((next_area_num, warp_cnt+1))
    else:
        print(-1)

if __name__ == '__main__':
    solve()


Measured memory_bytes: 189696
#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define PER(i, a, b) for (int i = a; i >= b; --i)
#define RVC(i, S) for (int i = 0; i < S.size(); ++i)
#define mp make_pair
#define pb push_back
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define fi first
#define se second
using namespace std;
 
typedef long long LL;
typedef pair<int, int> pii;
typedef vector<int> VI;

int n, p;
LL f[55][2][2];
int main(){
	scanf("%d%d", &n, &p);
	f[0][0][0] = 1;
	REP(i, 1, n){
		int x; scanf("%d", &x);
		REP(j, 0, 1) REP(k, 0, 1){
			f[i][j][0] += f[i - 1][j][k];
			f[i][(j + x) % 2][1] += f[i - 1][j][k];
		}
	}
	printf("%lld\n", f[n][p][0] + f[n][p][1]);
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(){
  int N,Y;
  cin >> N >> Y;
  int x = -1,y = -1,z = -1;
  for(int i = 0;i < N + 1;i++)
    for(int j = 0;j < N - i + 1;j++){
      if(Y == 10000 * i + 5000 * j + 1000 * (N - i - j)){
        cout << i << " " << j << " " << N - i - j << endl;
        return 0;
      }
    }
  cout << x << " " << y << " " << z << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define int long long
#define mod (int)(1e9+7)
#define inf (int)(3e18)
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define P std::pair<int,int>
#define PiP std::pair<int,std::pair<int,int>>
#define all(v) v.begin(),v.end()
#define mkp std::make_pair
#define prique(T) std::priority_queue<T,vector<T>,greater<T>>
using namespace std;
template<class T> inline void chmax(T& a, T b) { a = std::max(a, b); }
template<class T> inline void chmin(T& a, T b) { a = std::min(a, b); }

bool prime(int x) {
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0)return false;
	}
	return x != 1;
}
int gcd(int x, int y) {
	if (y == 0)return x;
	return gcd(y, x % y);
}
int lcm(int x, int y) {
	return x / gcd(x, y) * y;
}
int kai(int x, int y) {
	int res = 1;
	for (int i = x - y + 1; i <= x; i++) {
		res *= i; res %= mod;
	}
	return res;
}
int mod_pow(int x, int y, int m) {
	int res = 1;
	while (y > 0) {
		if (y & 1) {
			res = res * x % m;
		}
		x = x * x % m;
		y >>= 1;
	}
	return res;
}
int comb(int x, int y) {
	if (y > x)return 0;
	return kai(x, y) * mod_pow(kai(y, y), mod - 2, mod) % mod;
}
int get_rand(int MIN, int MAX) {
	std::random_device rnd;
	std::mt19937 mt32(rnd());
	std::uniform_int_distribution<int>engine(MIN, MAX);
	return engine(mt32);
}
/*--------Library Zone!--------*/

int n, dp[100005][3];
int a[100005];
int b[100005];
int ans[100005];
signed main() {
	cin >> n;
	rep(i, n)cin >> a[i];
	int memo = 3;
	rep(i, n) {
		if (a[i] == 0) {
			ans[i] = memo;
			b[0]++; memo--;
		}
		else {
			ans[i] = b[a[i] - 1];
			b[a[i]]++;
			b[a[i] - 1]--;
		}
	}
	int res = 1;
	rep(i, n) {
		res *= ans[i];
		res %= mod;
	}
	cout << res << endl;
}


Measured memory_bytes: 4352
#n=int(input())
a,b,c,d=map(int,input().split())
#l=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
import fractions
lcm=(c*d)//fractions.gcd(c,d)#最小公倍数

brng=b-(b//c+b//d)+b//lcm
arng=(a-1)-((a-1)//c+(a-1)//d)+(a-1)//lcm
ans=brng-arng
print(ans)

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

struct ab{
	int a;
	int b;
};
int cmp(const void *a, const void*b)
{
	return ((ab*)a)->a - ((ab*)b)->a;
}
int main(void){
	//N回挿入するということで・・・
	//K番目に小さい数というのは
	//小さい数のbを見ていって
	//K番目のbの左のa
	ab ab[100000];
	long long N,K;
	cin >> N >> K;
	int i;
	for(i=0;i<N;i++){
		cin >> ab[i].a >> ab[i].b;
	}
	qsort(ab,N,sizeof(struct ab),cmp);
	long long count = 0;
	for(i=0;i<N;i++){
		count += ab[i].b;
		if(count >=K){
			cout << ab[i].a << endl;
			return 0;
		}
	}
	return 0;
}


Measured memory_bytes: 1788
n = int(input())
s = input()
a = [str(c) for c in s]

def sea(a, x, y, n):
  while x < n-1:
    if a[x] == 'W':
      break
    x += 1
    
  while y > 0:
    if a[y] == 'R':
      break
    y -= 1
  
  return[x, y]

z = [0, n-1]

z = sea(a, z[0] ,z[1], n)
c = 0
while z[0] < z[1]:
  a[z[0]], a[z[1]] = a[z[1]], a[z[0]]
  c += 1
  z = sea(a,z[0], z[1],n)
  
print(c)



Measured memory_bytes: 11032
INF = 10**9
while 1:
    n = input()
    if not n:
        break
    dp = [INF]*4
    dp[0] = 0
    pos = 0; time = 0
    k = -1
    ps = []; ts = []
    for i in xrange(n):
        p, t = map(int, raw_input().split())
        ps.append(p); ts.append(t)
    for i in xrange(n):
        p, t = ps[i], ts[i]
        d = abs(p - pos)
        can = False
        r = INF
        for j in xrange(3, -1, -1):
            if j<3:
                dp[j+1] = INF
            if dp[j] == INF:
                continue
            if j<3 and d*(j+1) <= t - time:
                can = True
                dp[j+1] = dp[j] + d
            if pos*(j+1) + p <= t - time:
                r = min(r, dp[j] + pos + p)
                can = True
        dp[1] = r
        dp[0] = INF
        if not can:
            k = i+1
            break
        pos, time = p, t
    if k!=-1:
        print "NG", k
        continue
    print "OK", (min(dp[1:]) + p)

Measured memory_bytes: 4296
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
using vi = vector<i64>;
using vvi = vector<vi>;
constexpr i64 MOD = 1e9 + 7;

i64 partition_count(int n, int m, i64 mod) {
    if (n < 0) return 0;
    // divide n (undistinguished) items into m (undistinguished) groups, groups can have 0 items
    vvi dp(m + 1, vi(n + 1));
    dp[0][0] = 1;
    for (int i = 1; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (j - i >= 0) {
                dp[i][j] = (dp[i - 1][j] + dp[i][j - i]) % mod;
            } else {
                dp[i][j] = dp[i - 1][j];
            }
        }
    }
    return dp[m][n];
}

int main() {
    int n, k;
    cin >> n >> k;
    cout << partition_count(n - k, k, MOD) << endl;
}


Measured memory_bytes: 4392
#include <bits/stdc++.h>
#include <boost/multiprecision/cpp_int.hpp>

#define int long long

#define override_rep(i, l, r, mes, ...) mes
#define rep1(i, n) for (int i = 0; i < n; i++)
#define rep2(i, l, r) for (int i = l; i < r; i++)
#define rep(...) override_rep(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)

using namespace std;
using P = pair<int, int>;
using ll = long long;
using ld = double;

using bint = boost::multiprecision::cpp_int;

constexpr int MOD = 1e9 + 7;

template<typename T, typename U>
istream& operator>>(istream& in, pair<T, U>& p) {
    in >> p.first >> p.second;
    return in;
}

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

// https://twitter.com/vane11ope ←フォローしましょう
// (ノ)>◡<(ヾ)ﾓﾁﾓﾁ
signed main(signed argc, char* argv[]) {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);

    int d,t,s;
    cin>>d>>t>>s;
    if(s*t<d)cout<<"No"<<endl;
    else cout<<"Yes"<<endl;
}


Measured memory_bytes: 3648
#include <algorithm>
#include <bits/stdc++.h>
#include <bitset>
#include <cassert>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <math.h>
#include <memory>
#include <queue>
#include <set>
#include <stack>
#include <utility>
#include <vector>
using namespace std;
#define REP(i, n) for (int64_t i = 0; i < (int64_t)n; i++)
#define REP_FOR(i, a, b) for (int64_t i = (int64_t)a; i < (int64_t)b; i++)
#define REP_REV(i, a, b) for (int64_t i = (int64_t)a; i > (int64_t)b; i--)
#define FORALL(v) (v).begin(), (v).end()
#define mp(a, b) make_pair(a, b)
#define eb(x) emplace_back(x)
#define F first
#define S second
typedef long long ll;
typedef long double ld;
typedef pair<int64_t, int64_t> pii;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pdd;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int64_t> vii;
typedef vector<vii> vvii;
const ll mod = 1e9 + 7;
const int64_t infi = 1147483600;
const ll infl = 4e18 + 5;
const char EOL = '\n';
//cout << fixed << setprecision(17) << res << endl;
const ll MOD = 998244353;

int main() {
    int64_t n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0;
    for (ll i = 0; i < n; ++i) {
        cin >> a[i];
        sum = sum + a[i];
    }

    ll i = 0;
    ll t = 0;
    for (; i < n; ++i) {
        t += a[i];
        if (t * 2 == sum) {
            cout << 0 << endl;
            return 0;
        } else if (t * 2 > sum){
            break;
        }
    }
    auto t2 = t * 2;
    auto p1 = t2 - sum;
    auto p2 = sum + 2 * a[i] - t2;
    auto ans = 0;
    // cat cerr << sum << "," << p1 << "," << p2 << endl;
    ans = min(p1, p2);
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
 
#define ll          long long int
#define ld          long double
#define pb          push_back
#define mp          make_pair
#define ff          first
#define se          second
#define endl        '\n'
#define fd(n)       fixed<<setprecision(n)
#define MAX         100000000000001
#define MAXN        200005
#define mod         1000000007
 
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    if(s[0]==s[1]&&s[1]==s[2]){
        cout<<"No";
    }
    else{
        cout<<"Yes";
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;
int v[200003],n,m,a,b;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>a>>b;
        if(a>b) swap(a,b);
        if(a!=1&&b!=n) continue;
        if(a==1) ++v[b];
        if(b==n) ++v[a];
        if(v[b]==2||v[a]==2) {cout<<"POSSIBLE";return 0;}
    }
    cout<<"IMPOSSIBLE";
    return 0;
}


Measured memory_bytes: 1024
n,t[32],z,a,i,w;main(y){for(scanf("%d %d",&w,&n);++i<=w;t[i]=i);for(i=0;i++<n;t[z]=a)scanf("%d,%d",&y,&z),a=t[y],t[y]=t[z];for(y=0;++y<=w;)printf("%d\n",t[y]);exit(0);}

Measured memory_bytes: 592