akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

int main(){
    int x;  cin>>x;
    cout << !x << endl;
}


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

int main() {
	ios_base::sync_with_stdio( false );

	int D, N;
	cin >> D >> N;

	vector<int> a;
	for( int i = 1; a.size() < N; ++i ) {
		int x = i;
		int y = D;

		while( x % 100 == 0 && y-- ) {
			x /= 100;
		}

		if( y == 0 ) {
			a.push_back( i );
		}
	}

	cout << a.back() << endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define ALLR(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EMP emplace
#define EMPB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
#define Bit(n) (1LL << (n))
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

int N, C;
vector<pii> v[30];

vector<pii> f(vector<pii>& v) {
  vector<pii> res;
  sort(ALL(v));
  res.EMPB(v[0]);
  FOR(i, 1, SZ(v)) {
    if (v[i].first == res.back().second) {
      res.back().second = v[i].second;
    } else {
      res.EMPB(v[i]);
    }
  }
  return res;
}

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N >> C;
  REP(i, N) {
    int s, t, c;
    cin >> s >> t >> c;
    c--;
    v[c].EMPB(s, t);
  }
  REP(i, C) if (!v[i].empty()) v[i] = f(v[i]);
  int cum[200010] = {};
  REP(i, C) REP(j, SZ(v[i])) {
    cum[v[i][j].first*2-1]++;
    cum[v[i][j].second*2]--;
  }
  int ans = 0;
  FOR(i, 1, 200010) {
    cum[i] += cum[i-1];
    chmax(ans, cum[i]);
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4452
#include<bits/stdc++.h>
#define vd void
#define il inline
using namespace std;
typedef long long ll;
il ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
#ifdef mod
il int pow(int x,int y){
	int ret=1;
	while(y){
		if(y&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;y>>=1;
	}
	return ret;
}
#endif
int A[100010];
ll S[100010];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),m=gi(),v=gi(),p=gi(),ans=0;
	for(int i=1;i<=n;++i)A[i]=gi();
	std::sort(A+1,A+n+1);
	for(int i=1;i<=n;++i)S[i]=A[i]+S[i-1];
	for(int i=1;i<=n;++i){
		if(n-i+1<=p)++ans;
		else if(i>=v)ans+=A[i]+m>=A[n-p+1];
		else{
			int c=i+p-1,l=i+1,r=n-p+1;
			if(c>=v)ans+=A[i]+m>=A[r];
			else if(A[i]+m>=A[r]&&1ll*(A[i]+m)*(r-l+1)-S[r]+S[l-1]>=1ll*(v-c)*m)++ans;
		}
	}
	printf("%d\n",ans);
	return 0;
}



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

from collections import defaultdict

def main():
  n = int(input())
  sp = defaultdict(list)
  sp2number = {}
  for i in range(n):
    s, p = input().strip().split()
    p = int(p)
    sp[s].append(p)
    sp2number[(s, p)] = i + 1
  for key in sorted(sp.keys()):
    for score in sorted(sp[key], reverse=True):
      print(sp2number[(key, score)])

if __name__=='__main__':
  main()



Measured memory_bytes: 3316
#include <cstdio>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <typeinfo>
#include <numeric>
#include <functional>
#include <unordered_map>
#include <bitset>


using namespace std;
using ll = long long;
using ull = unsigned long long;

const ll INF = 1e16;
const ll MOD = 1e9 + 7;

#define REP(i, n) for(ll i = 0; i < n; i++)





int main() {
    int a, b;
    cin >> a >> b;
    cout << ((a + b == 15)? "+" : (a * b == 15)? "*" : "x") << endl;
}

Measured memory_bytes: 256
#https://atcoder.jp/contests/abc051/tasks/abc051_b
# -*- coding: utf-8 -*-
K,S = map(int,input().split())
ans = 0
for i in range(0,K+1):
  for j in range(0,K+1):
    z = S-i-j
    if 0 <= z <= K: ans +=1
print(ans)

Measured memory_bytes: 40684
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef long double ld;
const double pi=acos(-1.0);
const ll mod=pow(10,9)+7;
const ll INF=pow(2,31)-1;
typedef pair<int,int> P;
typedef vector<int> vi;

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

ll gcd(ll a , ll b){
	if(b == 0) return a;
	return gcd(b , a % b);	
}
ll lcm(ll a , ll b){
	ll g = gcd(a , b);
	ll lc = (a/g) * b;
	return lc;
}

int MAX_N=1e7;

int main(){
    ios::sync_with_stdio(false);
    int n,m; cin >> n;
    int sum=0;
    int a[MAX_N+5]={0};
    if(n==2) cout << 2 << endl;
    else{
        for(int i=1;i<(n);i++){
        a[i]=a[i-1]+i;
    }
    rep(i,n){
        if(a[i]<n&&n<=a[i+1]){
            m=i+1;
            break;
        }
    }
    for(int i=1;i<(m+1);i++){
        if(i!=a[m]-n){
            cout << i << endl;
        }
    }
    }
    return 0;
}

Measured memory_bytes: 39296
#include<stdio.h>
int main(void){
	int a;
	int b;
	int x;
	int y;
	scanf("%d ",&a);
	scanf("%d\n",&b);
	x=a*b;
	y=a*2+b*2;
	printf("%d ",x);
	printf("%d\n",y);
	return 0;
}



Measured memory_bytes: 2060
#include <iostream>
#include <fstream>
#include <typeinfo>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <iomanip>
#include <cctype>
#define syosu(x) fixed<<setprecision(x)
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<double,double> pdd;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<char> vc;
typedef vector<vc> vvc;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<P> vp;
typedef vector<vp> vvp;
typedef pair<int,P> pip;
typedef vector<pip> vip;
const int inf=1<<25;
const double pi=acos(-1);
const double eps=1e-8;
const vi emp;

int n;

int main(){
	while(1){
		cin>>n;
		if(!n) break;
		int ans=0,x,y,h,w,S;
		for(int i=0;i<n;i++){
			cin>>x>>y>>h>>w;
			S=x+y+h;
			if(S<=60&&w<=2) ans+=6;
			else if(S<=80&&w<=5) ans+=8;
			else if(S<=100&&w<=10) ans+=10;
			else if(S<=120&&w<=15) ans+=12;
			else if(S<=140&&w<=20) ans+=14;
			else if(S<=160&&w<=25) ans+=16;
		}
		cout<<ans*100<<endl;
	}
}

Measured memory_bytes: 1160
#include <stdio.h>

int main(void){
    int a,b;
    char op;
    while(1){
        scanf("%d %c %d\n",&a,&op,&b);
        switch(op){
            case '+':
                printf("%d\n",a + b);
                break;
            case '-':
                printf("%d\n",a - b);
                break;
            case '*':
                printf("%d\n",a * b);
                break;
            case '/':
                printf("%d\n",a / b);
                break;
            default:
                break;
        }
        if(op == '?'){
            break;
        }
    }
    return 0; /*0?????????*/
}

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

int main()
{
  int L;
  cin >> L;
  
  long double a = 0.333333333333;
  long double ans = (L*a);
  long double ans2 = ans*ans*ans;
  cout <<fixed<<setprecision(7)<< ans2;
    
  
 return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;

int main() {
	int N, dummy;
	dummy = scanf("%d", &N);

	vector<int> vi;
	map<int, int> mi;

	int tmp1;
	for (int i = 0; i < N; i++) {
		dummy = scanf("%d", &tmp1);
		vi.push_back(tmp1);
	}

	mi[0] = 0;
	mi[1] = abs(vi[1] - vi[0]);

	for (int i = 2; i < N; i++) {
		int tmp2 = mi[i-2] + abs(vi[i] - vi[i-2]);
		int tmp1 = mi[i-1] + abs(vi[i] - vi[i-1]);
		mi[i] = min(tmp1, tmp2);
	}
	
	printf("%d\n", mi[N-1]);
	
	return 0;
}


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

long long GCD(long long a, long long b){
  if(b==0) return a;
  else return GCD(b, a % b);
}
long long LCM(long long a, long long b) {
  long long g = GCD(a, b);
  return a / g * b;
}
int main() {
  long long A, B, C, D;
  cin >> A >> B >> C >> D;
  long long CD = LCM(C, D);
  cout << B - B/C - B/D + B/CD -(A-1) +(A-1)/C + (A-1)/D - (A-1)/CD << endl;
 
}

Measured memory_bytes: 3604
#include <stdio.h>
#include <math.h>

int p[10][10];

void drop(int x,int y){
	if(-1<x && x<10 && -1<y && y<10)p[x][y]++;
}

int main(void){

	int m,d;
	while(1){
		scanf("%d %d",&m,&d);
		if(m==0 && d==0)break;
		switch(m){
			case 2:d+=31;break;
			case 3:d+=60;break;
			case 4:d+=91;break;
			case 5:d+=121;break;
			case 6:d+=152;break;
			case 7:d+=182;break;
			case 8:d+=213;break;
			case 9:d+=244;break;
			case 10:d+=274;break;
			case 11:d+=305;break;
			case 12:d+=335;break;
		}
		switch(d%7){
			case 0:printf("Wednesday\n");break;
			case 1:printf("Thursday\n");break;
			case 2:printf("Friday\n");break;
			case 3:printf("Saturday\n");break;
			case 4:printf("Sunday\n");break;
			case 5:printf("Monday\n");break;
			case 6:printf("Tuesday\n");break;
		}
	}
	
	return 0;
}

Measured memory_bytes: 584
package main

import "fmt"

func main() {
	var K int
	fmt.Scan(&K)

	ans := 0
	for a := 1; a <= K; a++ {
		for b := 1; b <= K; b++ {
			for c := 1; c <= K; c++ {
				ans += gcd(a, gcd(b, c))
			}
		}
	}
	fmt.Println(ans)
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

Measured memory_bytes: 1776
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int main() {
  string str;
  int i;
  cin >> str;
  cin >> i;
  string out;
  for(int j = 0; j < str.size(); j++) {
    if(j % i == 0)
      out.push_back(str[j]);
  }
  cout << out << endl;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
#include <string>
#include <algorithm>
#include <unordered_map>
typedef long long ll;
int main()
{
    
    int n;
    cin >> n;
    unordered_map<string,ll>mp;
    string s;
    
    for(int i = 0;i < n;i++)
    {
        cin >> s;
        sort(s.begin(),s.end());
        mp[s]++;
    }
    
    ll res = 0;
    
    for(auto &x : mp)
    {
        res+=(x.second-1)*(x.second)/2;
    }
    
    cout << res << endl;
    
    return 0;
}

Measured memory_bytes: 7328
N = int(input())
dp = [[0 for i in range(3)] for j in range(N)]

#Lはa,b,c * Nを格納
L=[]
for i in range(N):
    a,b,c = map(int, input().split())
    L.append([a,b,c])

#N=0時は標準入力そのまま
dp[0][0] = L[0][0]
dp[0][1] = L[0][1]
dp[0][2] = L[0][2]

for i in range(1,N):
    dp[i][0] = max(dp[i-1][1],dp[i-1][2]) + L[i][0]
    dp[i][1] = max(dp[i-1][0],dp[i-1][2]) + L[i][1]
    dp[i][2] = max(dp[i-1][0],dp[i-1][1]) + L[i][2]
print(max(dp[N-1][0],dp[N-1][1],dp[N-1][2]))


Measured memory_bytes: 44148
#include <stdio.h>

int main(){
	int i,j;
	scanf("%d %d",&i,&j);
	if(j>i)
	{
		printf("%d",0);
		return 0;
	}
	else if(2*j>i){
		printf("%d",0);
		return 0;
	}	
	else
		printf("%d",i-2*j);
	return 0;
}

Measured memory_bytes: 128
import collections
import sys
N=int(input())
D = list(map(int, input().split())) 
M=int(input())
T = list(map(int, input().split())) 
D_count=collections.Counter(D)
T_count=collections.Counter(T)
for i in T:
    if D_count[i]<T_count[i]:
        print("NO")
        sys.exit()
print("YES")

Measured memory_bytes: 57016
using System;
using System.Collections.Generic;
using System.Linq;

namespace C___Go_to_School
{
    class Program
    {
        static void Main(string[] args)
        {
            var n = int.Parse(Console.ReadLine());
            var input = Console.ReadLine().Split(' ');
            var a = new Dictionary<int, int>();
            for (var i = 0; i < n; i++)
            {
                a.Add(i + 1, int.Parse(input[i]));
            }
            var b = a.OrderBy(x => x.Value)
                     .ToList();
            for (var i = 0; i < n; i++)
            {
                Console.Write(b[i].Key);
                if (i < n - 1)
                {
                    Console.Write(" ");
                }
            }
            Console.WriteLine();
        }
    }
}

Measured memory_bytes: 33884
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
const int maxn = 1e6+7;
int n;
long long seed;
inline long long rand(long long l, long long r) {
    static long long mo=1e9+7, g=78125;
    return l+((seed*=g)%=mo)%(r-l+1);
}
long long Max[10];
long long Min[10];
int main()
{
    int t;
	cin >> n;
        for(int i=0;i<10;i++)
            Max[i]=-1e15,Min[i]=1e15;
        long long x,y;
        for (int i = 0; i < n; i++)
        {
            cin>>x>>y;
            Max[0]=max(Max[0],x+y);
            Max[1]=max(Max[1],-x+y);
            Max[2]=max(Max[2],x-y);
            Max[3]=max(Max[3],-x-y);
            Min[0]=min(Min[0],x+y);
            Min[1]=min(Min[1],-x+y);
            Min[2]=min(Min[2],x-y);
            Min[3]=min(Min[3],-x-y);
        }
        long long ans = 0;
        for(int i=0;i<4;i++)
            ans=max(Max[i]-Min[i],ans);
        cout<<ans<<endl;
    }


Measured memory_bytes: 3640
#![allow(unused_imports)]
#![allow(non_snake_case)]
use std::cmp::*;
use std::collections::*;
use std::io::Write;

#[allow(unused_macros)]
macro_rules! debug {
    ($($e:expr),*) => {
        #[cfg(debug_assertions)]
        $({
            let (e, mut err) = (stringify!($e), std::io::stderr());
            writeln!(err, "{} = {:?}", e, $e).unwrap()
        })*
    };
}

fn main() {
    let s = read::<String>();
    println!("{}", s.replace(",", " "));
}

fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

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


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < n; ++i)
#define ALL(a) a.begin(), a.end()
ll dx[4] = { 0, 1, 0, -1 };
ll dy[4] = { 1, 0, -1, 0 };
const ll INF = 1l << 40;
const ll MOD = 1e9 + 7;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll N, K;
    cin >> N >> K;
    vector<vector<ll>> s(N); // s[種類]={おいしさ}
    rep(i, N)
    {
        ll t, d;
        cin >> t >> d;
        t--;
        s[t].push_back(d);
    }

    for (auto& v : s) {
        sort(v.rbegin(), v.rend());
        if (v.empty()) {
            v.push_back(-INF); // 番兵
        }
    }

    // sort(s.rbegin(), s.rend());
    // 「美味しさの最大値」の大きいネタ順
    sort(s.begin(), s.end(), [&](vector<long long> a, vector<long long> b) { return a[0] > b[0]; });

    ll cur = 0;
    priority_queue<ll> que; // sushiを全て入れる
    for (int i = 0; i < K; i++) { // とりあえずK個sushiを食う
        cur += s[i][0]; // 現在の値
        for (int j = 1; j < s[i].size(); j++) {
            que.push(s[i][j]);
        }
    }
    for (int i = K; i < N; i++) {
        for (int j = 0; j < s[i].size(); j++) {
            que.push(s[i][j]);
        }
    }

    ll res = cur + K * K; // 求めるスコア
    for (ll x = K - 1; x >= 1; x--) { // 種類を変える
        ll v = s[x][0]; // 今curに加えられている値
        ll w = que.top(); // priority_queueの上からの値
        if (v < w) {
            que.pop();
            cur += w;
            que.push(v);
            cur -= v;
        }
        res = max(res, cur + x * x);
    }
    cout << res << endl;

    return 0;
}

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

const int N = 50 + 5;

struct node{
  int a, b, c, d;
};

int n, m, Q;
node cur[N];
int a[N];
int mx = 0;

void DFS(int idx, int lo) {
  if (idx == n){
    int score = 0;
    for (int i = 0; i < Q; i++){
      if (a[cur[i].b - 1] - a[cur[i].a - 1] == cur[i].c)
        score += cur[i].d;
    }
    mx = max(mx, score);
    return;
  }
  for (int i = lo; i <= m; i++){
    a[idx] = i;
    DFS(idx + 1, i);
  }
}

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

    cin >> n >> m >> Q;
    for (int i = 0; i < Q; i++)
      cin >> cur[i].a >> cur[i].b >> cur[i].c >> cur[i].d;
    DFS(0, 1);
    cout << mx << endl;
}

Measured memory_bytes: 3636
#include <algorithm>
#include <vector>
#include <string>
#include <iostream>
using namespace std;

int main() {
	size_t n;
	cin >> n;
	vector<string> strs(n);
	for (auto& s: strs) {
		cin >> s;
		sort(s.begin(), s.end());
	}

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

	size_t t = 1;
	size_t r = 0;
	for (size_t i = 1; i < n; ++i) {
		if (strs[i - 1] == strs[i]) {
			++t;
		}
		else {
			r += t * (t - 1) / 2;
			t = 1;
		}
	}
	r += t * (t - 1) / 2;
	cout << r << endl;
}

Measured memory_bytes: 7296
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cassert>
#include <utility>
#include <functional>
#include <bitset>
#include <cstdint>

using namespace std;
using lli = long long int;
using i64 = int64_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

int main() {
  i64 n;
  vector<i64> a;
  cin >> n;
  read_n(a, 3 * n);

  sort(begin(a), end(a));
  i64 ans = 0;
  for (i64 i = 0; i < n; ++i) {
    a.pop_back();
    ans += a.back();
    a.pop_back();
  }
  cout << ans << '\n';
  return 0;
}



Measured memory_bytes: 2560
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000


int main(){
	int a[N];
	f(i, N)a[i] = 0;
	int n, k;
	int x, y, z;
	int s, ans;
	bool v = true;
	ans = 0;
	k = 0;
	scanf("%d", &n);
	f(i, n){
		scanf("%d", &a[i]);
		k = max(k, a[i]);
		ans += a[i];
	}
	ans -= (k / 2);
	printf("%d\n", ans);


	return 0;
}

Measured memory_bytes: 896
# A,Eが直接通信できれば全てのアンテナ間で通信ができる
import numpy as np
A = np.zeros(6)
for i in range(6):
    A[i] = int(input())
if A[4] - A[0] <= A[5]:
    print("Yay!")
else:
    print(":(")


Measured memory_bytes: 12488
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>

using namespace std;

typedef long long ll;
typedef double db;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<string> vs;
typedef vector<char> vc;
typedef queue<int> qi;
typedef pair<ll,ll> P;
typedef vector<P> vp;
typedef vector<vl> mat;
#define sort(a) sort(a.begin(),a.end())
#define reverse(a) reverse(a.begin(),a.end())
#define pb push_back
#define ft first
#define sd second
#define elif else if
#define unique(a) a.erase(unique(a.begin(),a.end()),a.end())
#define mp make_pair
#define fr(i,n)for(ll i=0;i<(n);i++)
ll n,a,b;
ll h[100010];
bool binary(ll s){
    ll total = s*b,c = 0;
    fr(i,n){
        if(h[i]>total)
        c +=(h[i]-total+a-b-1)/(a-b);
    }
    if(c<=s) return true;
    else return false;
}
int main(){
    cin>>n>>a>>b;
    fr(i,n)cin>>h[i];
    ll ok = 1e10,ng = -1;
    while(ok-ng>1){
        ll middle = (ok+ng)/2;
        if(binary(middle)){
            ok = middle;
        }else{
            ng = middle;
        }
    }
    cout << ok << endl;
}

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

int main(){
    int n, m, x;
    std::cin >> n >> m >> x;

    std::vector<int> a(n + 1, 0);
    int i;
    for(int j = 0; j < m; ++j){
        std::cin >> i;
        a.at(i) = 1;
    }

    int left = std::count(a.begin(), a.begin() + x + 1, 1);
    int right = std::count(a.begin() + x, a.end(), 1);

    if(left < right){
        std::cout << left << std::endl;
    }else{
        std::cout << right << std::endl;
    }

    return 0;
}


Measured memory_bytes: 256
fn main() {
    proconio::input! {
        n: usize,
        m: usize,
        sc: [(usize,i8);m],
    }
    let inf = std::i8::MAX;
    let mut a=vec![inf;n];
    for (s,c) in sc {
        if a[s-1]!=inf && a[s-1]!=c {
            println!("-1");
            return;
        }
        a[s-1]=c;
    }
    if n!=1 && a[0]==0 {
        println!("-1");
        return;
    }
    if a[0]==inf {
        a[0]=if n>1 {1} else {0};
    }
    for a in a.iter_mut() {
        if *a==inf {
            *a=0;
        }
    }
    println!("{}",itertools::join(a, ""));
}

Measured memory_bytes: 2136
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for (int i = (n)-1; i >=0; --i)
using namespace std;
using ll = long long;
using ld = long double;
using pi = pair<int,int>;

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 998244353;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, const mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}
// combination mod prime
// https://www.youtube.com/watch?v=8uowVvQ_-Mo&feature=youtu.be&t=1619
struct combination {
  vector<mint> fact, ifact;
  combination(int n):fact(n+1),ifact(n+1) {
    assert(n < mod);
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) fact[i] = fact[i-1]*i;
    ifact[n] = fact[n].inv();
    for (int i = n; i >= 1; --i) ifact[i-1] = ifact[i]*i;
  }
  mint operator()(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n]*ifact[k]*ifact[n-k];
  }
} c(200005);

int main() {
  ll n;
  cin >> n;

  map<string, int> m;
  string tmp;
  char last = '1';
  rep(i, n){
    cin >> tmp;
    if((i>0 && last!=tmp[0]) || m[tmp]>0) {
      cout << "No" << endl;
      return 0;
    }
    else m[tmp]++;
    last = tmp[tmp.size()-1];
  }

  
  cout << "Yes" << endl;
  return 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;

int main() {
	long long int N,S=0,keta=0,p=1,k=0;
	cin>>N;
	k=N;
	for(int i=N;i>0;i/=10)
	{
		keta++;
		p*=10;
	}
	for(int i=0;i<keta;i++)
	{
		p/=10;
		S+=k/p;
		k=k%p;
	}
	if(N%S==0)cout<<"Yes";
	else cout<<"No";
	}

Measured memory_bytes: 256
package main

import (
        "fmt"
)

func solution(x int) int {
        out := 0
        switch {
        case 400 <= x && x <= 599:
                out = 8
        case 600 <= x && x <= 799:
                out = 7
        case 800 <= x && x <= 999:
                out = 6
        case 1000 <= x && x <= 1199:
                out = 5
        case 1200 <= x && x <= 1399:
                out = 4
        case 1400 <= x && x <= 1599:
                out = 3
        case 1600 <= x && x <= 1799:
                out = 2
        case 1800 <= x && x <= 1999:
                out = 1
        }
        return out
}

func main() {
        var x int
        fmt.Scan(&x)
        fmt.Println(solution(x))
}

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

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  vector<int> box(N,0);
  vector<int> ans(N,0);
  int M;
  int k=0;
  for(int i=0;i<N;i++){
    cin >> a[i];
  }
  for(int i=N-1;i>=0;i--){
    int bin=0;
    for(int j=i;j<N;j=j+(i+1)){
      bin=bin+box[j];
    }
    bin=(bin+a[i])%2;
    if(bin==1){
      box[i]=1;
      ans[k]=i+1;
      k++;
    }   
  }
  
  cout << k << endl;
  for(int i=k-1;i>=0;i--){
    cout << ans[i] << " ";
  }
  return 0;
}

Measured memory_bytes: 3200
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

const (
	initialBufSize = 100000
	maxBufSize     = 1000000
)

var sc *bufio.Scanner

func initScanner(r io.Reader) *bufio.Scanner {
	buf := make([]byte, initialBufSize)

	sc := bufio.NewScanner(r)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords) // bufio.ScanLines
	return sc
}

func main() {
	sc = initScanner(os.Stdin)
	fmt.Println(resolve(parseProblem()))
}

func parseProblem() int {
	return scanInt(sc)
}

func resolve(x int) int {
	for i := 1; i <= x; i++ {
		if i*(i+1)>>1 >= x {
			return i
		}
	}
	panic(-1)
}

// snip-scan-funcs
func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	i, _ := strconv.Atoi(sc.Text())
	return int(i)
}
func scanString(sc *bufio.Scanner) string {
	sc.Scan()
	return sc.Text()
}

Measured memory_bytes: 1780
import java.util.*;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
        int b = sc.nextInt();
        int sum = 0;
        for(int i = 1; i <= (b - a) ; i++) {
            sum = i + sum;
        }
        System.out.println(sum - b);
	}
}

Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
int main(){
	string a,b="CODEFESTIVAL2016";
	cin>>a;
	int count=0;
	for(int i=0;i<16;i++){
		if(a[i]!=b[i]){
			count++;
		}
	}
	cout<<count<<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=sc.nextInt();
  long m=0,a=0, r=0,c=0, h=0;
	for(int i=0;i<n;i++){
      String s=sc.next().substring(0,1);
    	if(s.equals("M"))m++;
      else if(s.equals("A"))a++;
      else if(s.equals("R"))r++;
      else if(s.equals("C"))c++;
      else if(s.equals("H"))h++;
    }
  System.out.println(m*a*r+m*a*c+m*a*h+m*r*c+m*r*h+m*c*h+a*r*c+a*r*h+a*c*h+r*c*h);
}

}


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

int main() {
  int k,s; cin >>k >>s;
  int cnt = 0;
  for (int i=0; i<=min(k,s); i++){
    for (int j=i; j<=min(k,s-i); j++){
      if (s-(i+j)<=k){
        if (i==j) cnt++;
        else{cnt++; cnt++;}
      }
    }
  }
  int ans = cnt;
  
  cout <<ans;
  cout <<endl;
}


Measured memory_bytes: 256
#include<iostream>

int get_digit(int num){
    int digit=0;
    for(int i=0; num!=0 ;i++){
        num /=10;
        ++digit;
    }
    return digit;
}


int main()
{
    using namespace std;
    int N;
    cin >> N;//1 <= N <= 10^5
    
    int odd_digit_num=0;
    for(int n=1;n<=N;n++){
        //std::cout<<n <<" : "<<get_digit(n)<<std::endl;
        if(get_digit(n)%2==1){
            ++odd_digit_num;
        }
    }
    
    std::cout<<odd_digit_num<<std::endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<bitset>
#include<complex>
#include<cmath>
using namespace std;
template<typename __T>
inline void read(__T &x)
{
    x=0;
    int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')	f=-1;c=getchar();}
    while(isdigit(c))	{x=x*10+c-'0';c=getchar();}
    x*=f;
}
long long mod=1000000007;
int frac[66666],fracinv[66666];
long long qpow(long long a,long long b)
{
	long long ans=1;
	while(b)
	{
		if(b&1)	ans=ans*a%mod;
		b>>=1;
		a=a*a%mod;
	}
	return ans;
}
int n,m;
int a[20];
int C(int n,int m)
{
	if(n<m)	return 0;
	return 1ll*frac[n]*fracinv[m]%mod*fracinv[n-m]%mod;
}
int dp[20][66666];
int getcnt(int x)
{
	int sum=0;
	while(x)
	{
		x-=(x&-x);
		sum++;
	}
	return sum;
}
int main()
{
	read(n);
	read(m);
	for(int i=0;i<m;i++)
		read(a[m-i-1]);
	frac[0]=1;
	for(int i=1;i<=(1<<n);i++)
		frac[i]=1ll*frac[i-1]*i%mod;
	fracinv[(1<<n)]=qpow(frac[1<<n],mod-2);
	for(int i=(1<<n)-1;i>=0;i--)
		fracinv[i]=1ll*fracinv[i+1]*(i+1)%mod;
	dp[0][0]=1;
	for(int i=0;i<m;i++)
		for(int st=0;st<(1<<n);st++)
			if(dp[i][st])
			{//cout<<i<<' '<<st<<endl;
				dp[i+1][st]=(dp[i+1][st]+dp[i][st])%mod;
				for(int j=0;j<n;j++)
					if(!((st>>j)&1))
						dp[i+1][st|(1<<j)]=(dp[i+1][st|(1<<j)]+1ll*dp[i][st]*frac[1<<j]%mod*C((1<<n)-a[i]-st,(1<<j)-1))%mod;
			}
	int ans=0;
	for(int i=0;i<(1<<n);i++)
	{//cout<<"EM"<<i<<' '<<dp[m][i]<<endl;
		int t=getcnt(i);
		if(t&1)
			ans-=1ll*dp[m][i]*frac[(1<<n)-i-1]%mod;
		else
			ans+=1ll*dp[m][i]*frac[(1<<n)-i-1]%mod;
		ans%=mod;
	}
	ans=(ans+mod)%mod;
	cout<<1ll*ans*(1<<n)%mod<<endl;
	return 0;
}

Measured memory_bytes: 4352
#include <vector>
#include <iostream>
#include <map>
#include <string>
#include <utility>
#include <algorithm>
#include <stack>
#include <queue>
#include <list>
#include <functional>

const int INF = 1001001000;
const int MOD = (int)1e9 + 7;

using ll = long long;

using namespace std;

typedef pair<int,int> P;

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

int main(){
  int n,a;

  cin >> n >> a;
  int x;

  x = n%500;
  if( x <= a){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }

}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <stdio.h>

using namespace std;

static const double pi = 3.141592653589793;
typedef struct _point {
	double x;
	double y;
} point_t;

void print_point(point_t p1) {
	fprintf( stdout, "%.8f %.8f\n", p1.x, p1.y );
}

void koch(int number, point_t p1, point_t p2){
	if ( number == 0 ) {
		return;
	}

	point_t s, t, u;
	s.x = (2*p1.x+p2.x) / 3;
	s.y = (2*p1.y+p2.y) / 3;
	t.x = (p1.x+2*p2.x) / 3;
	t.y = (p1.y+2*p2.y) / 3;
	u.x = (t.x-s.x)*cos(pi/3)-(t.y-s.y)*sin(pi/3)+s.x;  
	u.y = (t.x-s.x)*sin(pi/3)+(t.y-s.y)*cos(pi/3)+s.y; 
	koch( number-1, p1, s );
	print_point( s );
	koch( number-1, s, u );
	print_point( u );
	koch( number-1, u, t );
	print_point( t );
	koch( number-1, t, p2 );
}

int main() {
	point_t p1, p2;
	p1.x = 0.0000;
	p1.y = 0.0000;
	p2.x = 100.0000;
	p2.y = 0.0000;
	int n;
	cin >> n;

	print_point( p1 );
	koch( n, p1, p2 );
	print_point( p2 );
	return 0;
}



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


using namespace std;

typedef long long ll;



int main() {
    int n;
    cin >> n;
    vector<vector<int> > arr(n, vector<int>(3));
    for(int i = 0; i < n; i++){
        cin >> arr[i][0] >> arr[i][1] >> arr[i][2];
    }
    vector<vector<int> > dp(n, vector<int>(3));
    dp[0] = arr[0];
    for(int i = 1; i < n; i++){
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
        dp[i][1] = max(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
        dp[i][2] = max(dp[i - 1][1], dp[i - 1][0]) + arr[i][2];
    }
    cout << max(dp[n - 1][0], max(dp[n - 1][1], dp[n - 1][2])) << endl;
}

Measured memory_bytes: 14096
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const int inf=1<<30;

int main(){
  string s; cin >> s;
  int n=s.size();
  string t;
  rep(i,n){
    if(s[i]=='?') t+='D';
    else t+=s[i];
  }
  cout << t << endl;
}

Measured memory_bytes: 3924
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int main() {
  string s;
  cin >> s;
  int c = 0;
  if (s[0] == '1') c++;
  if (s[1] == '1') c++;
  if (s[2] == '1') c++;
  cout << c << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef int64_t ll;
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) ((int)(v).size())
const int INF = 1e9;
const int MOD = 1e9 + 7;
const double PI = acos(-1);



int main(void) {
    string t;
    cin >> t;
    rep(i, SZ(t)) {
        if (t.at(i) == '?') t.at(i) = 'D';
    }
    cout << t << endl;
    return 0;
}

Measured memory_bytes: 3752
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  int n = s.size();
  string key = "keyence";
  REP(i,7){
    if(s[n-i-1]==key.back()) key.pop_back();
    else break;
  }
  
  if(s.substr(0,key.size())==key){
    cout << "YES" << '\n';
  }else{
    cout << "NO" << '\n';
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
 
static const double EPS = 1e-8;
static const double PI = 4.0 * atan(1.0);
static const ll INF = 1023456789;
 
#define REP(i,n)	for(int i=0;i<n;++i)
#define REPR(i,n)	for(int i=n-1;i>=0;--i)
#define FOR(i,s,n)	for(int i=s;i<n;++i)
#define FORR(i,s,n)	for(int i=n-1;i>=s;--i)
#define ALL(c)		(c).begin(),(c).end()
#define CLEAR(v)	memset(v,0,sizeof(v))
#define MP(a,b)		make_pair((a),(b))
#define ABS(a)		((a)>0?(a):-(a))
#define F			first
#define S			second
 
int main(int argc, char **argv) {
	int x, a, b;
	cin >> x >> a >> b;
	cout << ((x - a) % b) << endl;
	return 0;
}
 

Measured memory_bytes: 256
use proconio::{fastout, input, marker::Usize1};
use std::collections::VecDeque;

#[fastout]
fn main() {
    input! {
        n: usize,
        v: [(Usize1, Usize1, i64); n-1],
    }
    let mut join_list: Vec<Vec<(usize, i64)>> = Vec::new();
    for _ in 0..n {
        join_list.push(Vec::new());
    }
    for i in v.iter() {
        join_list[i.0].push((i.1, i.2));
        join_list[i.1].push((i.0, i.2));
    }

    let mut dist = vec![-1_i64; n];
    let mut node: VecDeque<usize> = VecDeque::new();
    let mut ans = vec![0; n];

    node.push_front(0);
    dist[0] = 0;

    while node.len() > 0 {
        let now_node = node.pop_back().unwrap();
        for i in join_list[now_node].iter() {
            if dist[i.0] < 0 {
                node.push_front(i.0);
                dist[i.0] = dist[now_node] + i.1;
                if dist[i.0] % 2 != 0 {
                    ans[i.0] = 1;
                }
            }
        }
    }

    for i in ans {
        println!("{}", i);
    }
}


Measured memory_bytes: 14864
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, x, n) for (int i = x; i < (n); i++)
#define all(n) begin(n), end(n)
struct cww
{
    cww()
    {
        ios::sync_with_stdio(false);
        cin.tie(0);
    }
} star;
const long long INF = numeric_limits<long long>::max();
typedef long long ll;
typedef vector<int> vint;
typedef vector<char> vchar;
typedef vector<vector<int>> vvint;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef unsigned long long ull;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}
int main()
{
    int N;
    cin >> N;
    vll A(N), S(N + 1);
    S[0] = 0;
    rep(i, N)
    {
        cin >> A[i];

        S[i + 1] = S[i] + A[i];
    }
    map<ll, ll> M;
    ll ans = 0;
    rep(i, N + 1)
    {
        M[S[i]]++;
    }
    for (auto i : M)
    {
        ans += ((i.second - 1) * i.second) / 2;
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 15872
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <utility>
#include <numeric>
#include <string>
#include <cstring>

using namespace std;

char moshimoshi[][6] = {"", ".,!? ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

int main(){
    int n; cin >> n;
    for(int i=0; i<n; i++){
        string str;
        cin >> str;
        int cnt[10] = {0}, num = 0;
        for(auto a : str){
            int b = a - 48;
            if(b != 0){
                cnt[b]++;
                num = b;
            }else{
                if(cnt[num] > 0){
                    cout << moshimoshi[num][(cnt[num]-1)%(strlen(moshimoshi[num]))];
                }
                for(int i=0; i<10; i++) cnt[i] = 0;
            }
        }
        cout << endl;
    }
    return 0;
}



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

using namespace std;

int main(void){
	int n,a,i,x=0,y=0;
	bool flag=false;
	cin >> n;
	for(i=0; i<n; i++){
		cin >> a;
		if(a%4==0){
			x++;
		}else if(a%2==0){
			flag = true;
		}else{
			y++;
		}
	}
	if(!flag){
		y--;
	}
	cout << ((x<y)?"No":"Yes") << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <iostream>
#include <functional>
#include <vector>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define rep1(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define per1(i,a,n) for (int i=a;i>n;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define endl "\n"
#define pi 3.14159265358979323846264338327950288419716939937510
#define IOS cin.sync_with_stdio(false);cin.tie(0);cout.tie(0);
//#pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll mod=1000000007;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll qpow(ll a,ll b){ll s=1;while(b>0){if(b%2==1){s=s*a;}a=a*a;b=b>>1;}return s;}
ll qpowmod(ll a, ll b, ll c){ll res, t;res=1;t=a%c;while(b){if(b & 1){res=res*t%c;}t=t*t%c;b>>=1;}return res;}
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;}
inline long long read(){long long k=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}return k*f;}
inline void write(long long x){if(x<0)x=-x,putchar('-');if(x>9)write(x/10);putchar(x%10+'0');}
// head
const int maxn=200005;
ll n,a[maxn],flag,now,tot;
vector<int> v;
int main()
{
    //IOS;
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    flag=0;
    now=1000;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    for(int i=2;i<=n+1;i++)
    {
        if(a[i-1]>a[i]&&flag==1)
        {
            v.push_back(a[i-1]);
            flag=0;
        }
        else if(a[i-1]<a[i]&&flag==0)
        {
            v.push_back(a[i-1]);
            flag=1;
        }
    }
    //v.push_back(a[n]);
    flag=0;
    for(auto &i:v)
    {
        //cout<<i<<endl;
        if(flag==0)
        {
            tot=now/i;
            now-=tot*i;
            flag=1;
        }
        else
        {
            now+=i*tot;
            flag=0;
        }
    }
    cout<<now<<endl;
    return 0;
}
/*

*/


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

#define dump(n) cout<<"# "<<#n<<'='<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;

const int INF=1e9;
const int MOD=1e9+7;
const double EPS=1e-9;

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}
template<typename T>
ostream& operator<<(ostream& os,const vector<T>& a){
	os<<'[';
	rep(i,a.size()) os<<(i?" ":"")<<a[i];
	return os<<']';
}

struct UnionFind{
	vi data;
	UnionFind(int size):data(size,-1){}
	int Find(int n){
		return data[n]<0?n:(data[n]=Find(data[n]));
	}
	void Unite(int a,int b){
		int ra=Find(a),rb=Find(b);
		if(ra!=rb){
			if(-data[ra]<-data[rb])
				swap(ra,rb);
			data[ra]+=data[rb];
			data[rb]=ra;
		}
	}
	int Size(int n){
		return -data[Find(n)];
	}
};

int main()
{
	for(int n,p1,p2;cin>>n>>p1>>p2 && n|p1|p2;){
		int m=p1+p2;
		UnionFind uf(m*2);
		rep(i,n){
			int x,y; string a; cin>>x>>y>>a; x--,y--;
			if(a=="yes"){
				uf.Unite(x,y);
				uf.Unite(m+x,m+y);
			}
			else{
				uf.Unite(x,m+y);
				uf.Unite(m+x,y);
			}
		}
		
		vvi eqs; // 同値類
		{
			vi flg(m);
			rep(i,m) if(!flg[i]){
				eqs.resize(eqs.size()+1);
				rep(j,m*2) if(uf.Find(j)==uf.Find(i)){
					eqs.back().push_back(j);
					flg[j%m]=1;
				}
			}
		}
		
		vi dcnt(eqs.size()); // 同値類に含まれるdivineの数
		rep(i,eqs.size()){
			for(int x:eqs[i])
				dcnt[i]+=x<m;
		}
		
		// dp[i+1][j]: eqs[i]までを使って，divineをj体にできるか．
		// dp[i+1][j]=  0: できない
		// dp[i+1][j]=  1: できる．eqs[i]をそのまま使う
		// dp[i+1][j]= -1: できる．eqs[i]を反転して使う
		// dp[i+1][j]=INF: できる．複数通りある(ambiguous)
		vvi dp(eqs.size()+1,vi(m+1,0));
		dp[0][0]=1;
		rep(i,eqs.size()){
			int a=dcnt[i],b=eqs[i].size()-dcnt[i];
			rep(j,m+1){
				if(dp[i][j]==INF)
					dp[i+1][j+a]=dp[i+1][j+b]=INF;
				else if(abs(dp[i][j])==1){
					if(dp[i+1][j+a]==0) dp[i+1][j+a]=1;
					else                dp[i+1][j+a]=INF;
					if(dp[i+1][j+b]==0) dp[i+1][j+b]=-1;
					else                dp[i+1][j+b]=INF;
				}
			}
		}
		
		if(abs(dp.back()[p1])!=1){
			cout<<"no"<<endl;
			continue;
		}
		
		vi ds;
		for(int i=eqs.size(),d=p1;i>0;i--){
			assert(abs(dp[i][d])==1);
			if(dp[i][d]==1){
				for(int x:eqs[i-1]) if(x<m)
					ds.push_back(x);
				d-=dcnt[i-1];
			}
			else{
				for(int x:eqs[i-1]) if(x>=m)
					ds.push_back(x-m);
				d-=eqs[i-1].size()-dcnt[i-1];
			}
		}
		sort(all(ds));
		for(int d:ds) cout<<d+1<<endl;
		cout<<"end"<<endl;
	}
}

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

long long a,b,c,k,ans;
int main() 
{ 

	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>a>>b>>c>>k;
    if(k <= a) cout << k << endl;
	else if(k <= a + b) cout << a << endl;
	else cout << a - (k - a - b) << endl;
	return 0;

} 


Measured memory_bytes: 3660
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<stdio.h>
#include<cmath>
#include<vector>
#include<utility>
#define FOR(i, a, b) for(int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define MOD 1000000007
using namespace std;

int main(void) {
	int x;
	int t = 0;
	int total = 0;
	cin >> x;
	while (1) {
		t++;
		total += t;
		if (total >= x) {
			cout << t << endl;
			break;
		}
	}
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int a,b,i,ans=0;
  vector<pair<int,int>> v;
  for(i=0;i<5;i++){
    cin>>a;
    b=(a+9)/10*10;
    v.push_back(make_pair(b-a,b));
  }
  sort(v.begin(),v.end());
  for(i=0;i<5;i++){
    ans+=v.at(i).second;
    if(i==4) ans-=v.at(i).first;
  }
  cout<<ans<<endl;
}

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	long long int n;
	cin>>n;
	if(n==7||n==5||n==3){
		cout<<"YES";
	}
	else{
		cout<<"NO";
	}
	return 0;
}

Measured memory_bytes: 3624
//
//  main.cpp
//  ABC 064 Insertion
//
//  Created by Shuangyi Zhang on 2017/6/24.
//  Copyright © 2017年 Shuangyi Zhang. All rights reserved.
//

#include <iostream>
#include <string>
using namespace std;
int main() {
    int n,p,q,l;
    string s,ans;
    cin>>n>>s;
    p=0,q=0,l=0;
    for (int i=0;i<=n-1;i++){
        if (s[i]=='('){
            p+=1;
        }else{
            q+=1;
        }
        if (q>p){
            l=max(l,q-p);
           
        }
        
    }
    for (int i=1;i<=l;i++){
        ans+='(';
    }
    ans+=s;
    for (int i=1;i<=p+l-q;i++){
        ans+=')';
    }
    cout<<ans<<endl;
  //  l=max(p,q)*2;
 //   p=0,q=0,z=0;
 //   for (int i=1;i<=l;i++){
//        if (z==n){
  //          z=i;
    //        break;
      //  }
        //if (s[z]=='('){
 //           p+=1;
   //     }else{
     //       q+=1;
  //      }
   //     if (p<q){
    //        a[i]='(';
     //   }else{
      //      a[i]=s[z];
       //     z+=1;
        //}
            
        
    //}
    
    return 0;
}


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


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

  ll t[2],a[2],b[2];
  rep(i,2)cin  >> t[i];
  rep(i,2)cin  >> a[i];
  rep(i,2)cin  >> b[i];

  ll cyc[2];
  cyc[0]=cyc[1]=0;
  rep(j,2) cyc[0]+=t[j]*a[j];
  rep(j,2) cyc[1]+=t[j]*b[j];
  //  cout << "cyc " << cyc[0] << " " << cyc[1] << endl;
  if(cyc[0]==cyc[1]){
    cout << "infinity" << endl;
    return 0;
  }
  if(cyc[0]<cyc[1]){
    swap(cyc[0],cyc[1]);
    rep(i,2) swap(a[i],b[i]);
  }
  if(a[0] > b[0]){
    cout << 0 << endl;
    return 0;
  }
  ll ub=cyc[0]/(cyc[0]-cyc[1]) + 10;
  ll lb=1;
  while(ub-lb>1){
    ll mid=(ub+lb)/2;
    ll dif=(mid-1)*(cyc[0]-cyc[1]) + (a[0]-b[0])*t[0];//p-q;
      //    ll p=(mid-1)*cyc[0]+a[0]*t[0];
      //    ll q=(mid-1)*cyc[1]+b[0]*t[0];
      //    if(p<=q){
    if(-dif>=0){
      lb=mid;
    }
    else{
      ub=mid;
    }
    if(dif==0){
      ll ans=(lb*2LL-1LL);
      ans--;
      cout << ans << endl;
      return 0;
    }
  }
  cout << (lb*2LL-1LL) << endl;
  
  //  cout << endl << endl;
  //  cout << static_cast<double>(clock()) / CLOCKS_PER_SEC << "s"<<endl;
  return 0;
    

}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
using namespace std;

#define X first
#define Y second
#define N 100010
#define M 11

typedef long long ll;
const int Mod=1000000007;
const int INF=1<<30;

int n,m;
int x[N],y[N];
int sx[N],sy[N];

int main()
{
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);
	
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++) scanf("%d",&x[i]),sx[i]=x[i]+sx[i-1],sx[i]%=Mod;
	for (int i=1;i<=m;i++) scanf("%d",&y[i]),sy[i]=y[i]+sy[i-1],sy[i]%=Mod;
	
	int t1=0,t2=0;
	for (int i=1;i<=n;i++)
	{
		t1+=1ll*i*x[i]%Mod;
		t1%=Mod;
		t1-=sx[i];
		t1%=Mod;
	}
	for (int i=1;i<=m;i++)
	{
		t2+=1ll*i*y[i]%Mod;
		t2%=Mod;
		t2-=sy[i];
		t2%=Mod;
	}
	int res=1ll*t1*t2%Mod;
	if (res<0) res+=Mod;
	printf("%d\n",res);
	
	return 0;
}

Measured memory_bytes: 1792