akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using ll = long long;
using ld = long double;
const ll ATCODER_AMARI = 1000000007; //10^9 + 7
const ll INF = 10000000000000;


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

  vector<int> a(n+1,0); 
  rep(i,n+1) {
    if(i == 0) continue;
    cin >> a[i];
  }

  vector<int> b(n+1,0);
  int m = 0;

  for(int i = n; i >= 1; i--){
    int tmp = i;
    int tmp2 = i;
    int tmp_b = 0;
    while(tmp < n+1) {
      tmp_b += b[tmp];
      tmp_b %= 2;
      tmp += tmp2;
    }

    tmp_b += a[i];
    tmp_b %= 2;

    b[i] = tmp_b;
    if(b[i] == 1) m++;
    
  }

  cout << m << endl;

  rep(i,n+1) {
    if(i == 0) continue;
    if(b[i] == 1) {
      cout << i << endl;
    }
  }
}



Measured memory_bytes: 4856
n = int(input())
h = list(map(int, input().split()))

ans = True

for i in range(n-1,0,-1):
    if h[i-1] > h[i]:
        h[i-1] -= 1
for i in range(n-1,0,-1):
    if h[i-1] > h[i]:
        ans = False
        break

if ans:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 14396
N = int(input())
X = [[] for k in range(N)]
A = [0 for k in range(N)]

for k in range(N):
    A[k] = int(input())
    X[k] = [list(map(int, input().split())) for i in range(A[k])]
    

ans = [0]
for m in range(2**N)[::-1]:
    s = str(bin(m))[2:].zfill(N)
    li = list(s)
    li = [int(a) for a in li]
    chk = 1
    for k in range(N): # 証言を1人ぶんずつみていく
        if li[k] == 0: # 不親切の人の証言の場合
            pass
        elif A[k] == 0: # 証言していない場合
            pass
        else: # 正直者の人の証言だけ検証する
            for y in X[k]:
                if y[1] == li[y[0]-1]: #y[0]さんに関する仮定 ＝？ y[0]さんに関する証言
                    pass
                else: # 矛盾した
                    chk = 0
                        
    if chk == 1:
        ans.append(sum(li))
        break
    else:
        pass


print(max(ans))


Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
#define INF 10000000

set<pair<int, int> > s;
int x = -1, y = -1;
int tmp;

int prim(int v, vector<vector<pair<int, int> > > adjlist){

    priority_queue<pair<int, pair<int, int> > > wait;    // first := 候補辺のコスト   second　:= {from, to}
    vector<int> result(v, INF);               // 頂点iと木の間の最小コスト
    int ans = 0, size = 0;                    // 木のコスト　頂点数

    //初期条件
    result[0] = 0;
    wait.push({0, {-1, 0}});

    while(!wait.empty() && size < v){

        //候補辺のうち最小のものを取り出す
        int from = wait.top().second.first;
        int newpoint = wait.top().second.second;
        int newcost = -wait.top().first;
        if(from != -1 && x == -1) s.insert({from, newpoint});
        wait.pop();
        //cout << x + 1 << " " << y + 1 << " " << from + 1 << " " << newpoint + 1 << endl;


        if(result[newpoint] < newcost) continue;

        //出てきた頂点を木に追加
        ans += newcost;
        result[newpoint] = -INF;
        size++;

        // 新しい点から出ている辺をすべてなめる
        for(int i = 0; i < adjlist[newpoint].size(); i++){
            int nextpoint = adjlist[newpoint][i].second;
            int nextcost = adjlist[newpoint][i].first;
            
            if((x == nextpoint && y == newpoint) || (x == newpoint && y == nextpoint)){
                //cout << "ok" << endl;
                tmp = nextcost;
                //cout << tmp << endl;
                continue;
            }
            
            //より木に近くなった頂点があれば,　そこへの枝をqueueに追加
            if(result[nextpoint] > nextcost){
                result[nextpoint] = nextcost;
                wait.push({-nextcost, {newpoint, nextpoint}});
            }
        }
    }

    return ans;
}



int main(){

    int V, E; cin >> V >> E;                          // V:= 頂点の数    E:= 辺の数 
    vector<vector<pair<int, int> > > adjlist(V);      //first := コスト　second := 行先

    //入力
    for(int i = 0; i < E; i++){
        int a, b, c; cin >> a >> b >> c;              // a ,b 間に コスト c の辺がある
        a--; b--;
        adjlist[a].push_back(make_pair(c, b));
        adjlist[b].push_back(make_pair(c, a));      
    }

    int ans = prim(V, adjlist);
    //cout << ans << endl;
    int num = 0;
    int cost = 0;
    for(auto e : s){
        //cout << e.first + 1 << " " << e.second + 1 << endl;
        x = e.first;
        y = e.second;
        int w = prim(V, adjlist);
        //cout << "remove " << x + 1 << " " << y + 1 << " : w = " << w << endl;
        if(ans != w){
            //cout << u + 1 << " " << v + 1 << endl;
            //cout << "addcost " << tmp << endl;
            num++;
            cost += tmp;
        }
    }

    cout << num << " " << cost << endl;
    
    return 0;
}


Measured memory_bytes: 5036
#include<iostream>
using namespace std;
int main()
{
    int n1,n2,n3;
    cin>>n1>>n2>>n3;
    if(n3>n1&&n3<n2){
        cout<<"Yes"<<endl;
    }
    else if(n1==n2&&n1==n3){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
    return 0;
}


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

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


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

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

int main(void) {
	char input[100];
	int count[26]={0};
	int i,j,length;
	int kisuu_num=0;
	int kisuu_pos=-1;
	int kakeru[20];
	int waru_num=0;
	int waru[26000];
	long long result=1;
	int now_gcd;
	scanf("%s",input);
	length=strlen(input);
	for(i=0;i<length;i++)count[input[i]-'a']++;
	for(i=0;i<26;i++) {
		if(count[i]%2) {
			kisuu_num++;
			kisuu_pos=i;
		}
	}
	if(kisuu_num!=length%2) {
		puts("0");
	} else {
		length/=2;
		if(kisuu_pos>=0)count[kisuu_pos]--;
		for(i=0;i<26;i++) {
			count[i]/=2;
			for(j=2;j<=count[i];j++)waru[waru_num++]=j;
		}
		for(i=0;i<length;i++)kakeru[i]=i+1;
		for(i=0;i<length;i++) {
			for(j=0;j<waru_num;j++) {
				if((now_gcd=gcd(kakeru[i],waru[j]))>1) {
					kakeru[i]/=now_gcd;
					waru[j]/=now_gcd;
				}
			}
			result*=kakeru[i];
		}
		printf("%lld\n",result);
	}
	return 0;
}

Measured memory_bytes: 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <utility>

#include <cassert>
#include <cmath>
#include <cstdio>

using namespace std;

#define fi first
#define se second
#define mkp make_pair
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define FOR(i,a,b) for(ll i=(a); i < (b); i++)
#define RFOR(i,a,b) for(ll i=(b)-1; i >= (a); i--)
#define rep(i,n) FOR(i,0,(n))
#define rrep(i,n) RFOR(i,0,(n))

int main() {
	int a, b;
	cin >> a >> b;
	if(a+b==15)
		cout << "+" << endl;
	else if(a*b==15)
		cout << "*" << endl;
	else
		cout << "x" << endl;
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <climits>
#include <cassert>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define rep(i, a, b) for(int i = a, i##_END_ = b; i < i##_END_; ++i)
#define per(i, a, b) for(int i = (b)-1, i##_BEGIN_ = a; i >= i##_BEGIN_; --i)
typedef long long ll;
typedef double db;
const int inf = (int)1e9;
const ll linf = (ll)1e18;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define x first
#define y second
#define pb(x) push_back(x)
#define sz(x) (int)(x).size()
template<class T>
inline void read(T &x){
	char c; x = 0;
	bool neg = false;
	while(c = getchar(), c!='-' && (c<'0'||c>'9'));
	if(c == '-') neg = true, c = getchar();
	do x = (x*10) + (c^48);
	while(c = getchar(), c>='0'&&c<='9');	
	if(neg) x = -x;
}
template<class T>
inline void print(T x){
	if(x == 0){ putchar('0'); return;}
	if(x < 0){ putchar('-'); x = -x;}
	static char stk[30]; int top = 0;
	while(x) stk[++top] = x%10^48, x /= 10;
	while(top) putchar(stk[top--]);
}
#ifdef Leefir
	#define ast(x) assert(x)
	#define dig(...) fprintf(stderr, __VA_ARGS__)
#else
	#define ast(x) ;
	#define dig(...) ;
#endif

namespace Program{

const int N = (int)2e5;
const int VAL = (int)1e9;
int n, m;
int a[N+5];
void input(){
	scanf("%d %d", &n, &m);
	rep(i, 0, n) scanf("%d", &a[i]);
}
ll calc(int x){
	ll res = 0;
	int cnt = x, cur = -2;
	res = n*(ll)m*2;
	per(i, 0, n){
		res += a[i]*5LL;
		if(cur >= 0) res += -m + cur*(ll)a[i];
		if(--cnt == 0) cnt = x, cur += 2;
	}
//	printf("x %d  res %lld\n", x, res);
	return res;
}
void Main(){
	input();
	int L = 1, R = n;
	ll ans = linf;
	while(L < R){
		int mid1 = (L+R)/2;
		int mid2 = mid1+1;
		ll tmp1 = calc(mid1);
		ll tmp2 = calc(mid2);
		if(tmp1 < tmp2) ans = tmp1, R = mid1;
		else ans = tmp2, L = mid2;
	}
	cout << ans << endl;
}

} //namespace Program
int main(){
#ifdef Leefir
	dig("**********define Leefir***********\n");
#endif
	srand(time(NULL));
	
	Program::Main();
	
	return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<vector>
using namespace std;
int main()
{
    int lim,num,sum;
    vector<int>v1;
    while(cin>>num>>lim)
    {
        sum=0;
        for(int i=0;i<lim;i++)
        {
            int temp;
            cin>>temp;
            v1.push_back(temp);
            sum+=v1[i];
        }
        if(num>=sum)
        {
        cout<<(num-sum)<<endl;
        }
        else 
        {
        cout<<"-1"<<endl;
        }
        break;
    }
    
}

Measured memory_bytes: 3728
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <bitset>
#include <cassert>
#include <functional>

using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<ll, ll> P;
inline ll min(ll x, ll y) { return x < y ? x : y; }
inline ll max(ll x, ll y) { return x > y ? x : y; }

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)

int main() {
	int N;
	cin >> N;
	vector<int> A(N), B(N), C(N - 1);
	rep(i, N) {
		cin >> A[i];
		A[i]--;
	}
	rep(i, N) cin >> B[i];
	rep(i, N - 1) cin >> C[i];

	int total = 0;

	rep(i, N) {
		total += B[A[i]];
		if (i + 1 != N) {
			if (A[i] + 1 == A[i + 1]) {
				total += C[A[i]];
			}
		}
	}

	cout << total;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main() {
	int r,c;
	cin >> r >> c;
	int mat[r+1][c+1];
	for( int i=0; i<r; i++ ) {
		for( int j=0; j<c; j++ ) {
			cin >> mat[i][j];
		}
	}

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

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

	for( int i=0; i<r+1; i++ ) {
		for( int j=0; j<c+1; j++ ) {
			if( j > 0 ) { cout << " "; }
			cout << mat[i][j];
		}
		cout << endl;
	}
	return 0;
}

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

int main() {
  int n,T,c,t,i,min=100000000;
  cin>>n>>T;
  for(i=0;i<n;i++){
    cin>>c>>t;
    if(t<=T&&c<min)
      min=c;
  }
  if(min==100000000)
    cout<<"TLE"<<endl;
  else
  cout<<min<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
typedef pair<pii,ll> piii;
typedef pair<ll,pii> ipii;
#define MOD 1000000007
#define mod(a) ((a)%MOD)
#define pb push_back
#define ft first
#define sd second
#define mp make_pair
#define dbg(x) cerr<<#x<<" = "<<x<<"\n"
#define dbg2(x,y) cerr<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<"\n"
#define dbg3(x,y,z) cerr<<#x<<" = "<<x<<" , "<<#y<<" = "<<y<<" , "<<#z<<" = "<<z<<"\n"
#define INF (1LL<<60)
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;*/
#define sync ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(v) v.begin(),v.end()
#define endl '\n'
ll gcd(ll a,ll b){if(a==0) return b; return gcd(b%a,a);}
ll powm(ll base,ll exp,ll mod=MOD) {base%=mod;ll ans=1;while(exp){if(exp&1LL) ans=(ans*base)%mod;exp>>=1LL,base=(base*base)%mod;}return ans;}
 



vector<ipii> p;
ll dp[1003][20004];

bool comp(ipii a,ipii b){
     return (a.ft+a.sd.ft)<(b.ft+b.sd.ft);
}


int main(){
      sync;
      ll n;
      cin>>n;
      int f=0;
      for(int i=0;i<n;i++){
            ll w,s,v;
            cin>>w>>s>>v;
            if(s>10000) f=1;
            p.pb({s,{w,v}});
      }
       
        if(f){
            cout<<"Hold ON!"<<endl;
        }
        sort(all(p),comp);
        ll ans=0;
        for(int i=0;i<=20004;i++){
               dp[0][i]=(p[0].sd.ft<=i?p[0].sd.sd:0);
        }
        for(int i=1;i<n;i++){
             for(int j=0;j<=20000;j++){
                  if(j==0){
                       dp[i][j]=0;continue;
                  }
                  dp[i][j]=dp[i-1][j];
                  if(p[i].sd.ft<=j){
                        dp[i][j]=max(dp[i][j],dp[i-1][min(j-p[i].sd.ft,p[i].ft)]+p[i].sd.sd);
                  }
             }
        }

        for(int i=0;i<=20000;i++) ans=max(ans,dp[n-1][i]);
        cout<<ans<<endl; 
}

Measured memory_bytes: 156544
#include<stdio.h>
#define MAX 100000
#define NIL -1

void setDepth(int,int);
int setHeight(int);
int getSibling(int);
void print(int);

struct Node { int parent,left,right; };

struct Node T[MAX];
int n,D[MAX],H[MAX];

int main(){
  int v,l,r,i,root=0;
  scanf("%d",&n);
  for(i=0;i<n;i++)T[i].parent=NIL;

  for(i=0;i<n;i++){
    scanf("%d%d%d",&v,&l,&r);
    T[v].left = l;
    T[v].right = r;
    if(l != NIL)T[l].parent=v;
    if(r != NIL)T[r].parent=v;
  }

  for(i=0;i<n;i++)if(T[i].parent==NIL)root=i;

  setDepth(root,0);
  setHeight(root);

  for(i=0;i<n;i++)print(i);

  return 0;
}

void setDepth(int u,int d){
  if(u==NIL)return;
  D[u]=d;
  setDepth(T[u].left,d+1);
  setDepth(T[u].right,d+1);
}

int setHeight(int u){
  int h1=0,h2=0;
  if(T[u].left!=NIL)
    h1=setHeight(T[u].left)+1;
  if(T[u].right!=NIL)
    h2=setHeight(T[u].right)+1;
  return H[u]=(h1>h2 ? h1 : h2);
}

int getSibling(int u){
  if(T[u].parent==NIL)return NIL;
  if(T[T[u].parent].left!=u && T[T[u].parent].left!=NIL)
    return T[T[u].parent].left;
  if(T[T[u].parent].right!=u && T[T[u].parent].right!=NIL)
    return T[T[u].parent].right;
  return NIL;
}

void print(int u){
  printf("node %d: ",u);
  printf("parent = %d, ",T[u].parent);
  printf("sibling = %d, ",getSibling(u));
  int deg = 0;
  if(T[u].left != NIL)deg++;
  if(T[u].right != NIL)deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, ",D[u]);
  printf("height = %d, ",H[u]);

  if(T[u].parent == NIL){
    printf("root\n");
  }else if(T[u].left == NIL && T[u].right == NIL){
      printf("leaf\n");
    }else{
      printf("internal node\n");
  }
}


Measured memory_bytes: 2108
#include <stdio.h>
#define N 100000

int main(void){
    int n;
    int a[N+1];
    int memo0[N+1] = {};
    int memo1[N+1] = {};
    int i;
    int sum;
    
    
    scanf("%d", &n);
    for(i = 1; i <= n; i++){
        scanf("%d", &a[i]);
    }
    
    for(i = 1; i <= n; i++){
        if(i & 1){//i=2k+1
            memo0[i] = memo0[i-1] - a[i];
        }else{
            memo0[i] = memo0[i-1] + a[i];
        }
    }
    
    for(i = 1; i <= n; i++){
        if(i & 1){//i=2k+1
            memo1[i] = memo1[i-1] + a[i];
        }else{
            memo1[i] = memo1[i-1] - a[i];
        }
    }
    
    for(i = 1; i <= n; i++){
        if(i == n){
            //sum = memo0[n];
            sum = a[i] + (memo0[i-1]) + (memo1[n] - memo1[i]);
        }else if(i & 1){
            //sum = a[i] + (memo1[i-1]) + (memo0[n] - memo0[i]);
            sum = a[i] + (memo0[i-1]) + (memo1[n] - memo1[i]);
        }else{
            //sum = a[i] + (memo0[i-1]) + (memo1[n] - memo1[i]);
            sum = a[i] + (memo1[i-1]) + (memo0[n] - memo0[i]);
        }
        
        printf("%d ", sum);
    }
    
    return 0;
}

Measured memory_bytes: 2432
#include<stdio.h>

int main(){
	
	int a,b;
	int i=0;
	int c,z;
	
	while(1){
		scanf("%d %d",&a ,&b);
		
		if(a==0 && b==0) break;
		if(i!=0) printf("\n");
		
		z=0;
		
		for(i=a;i<=b;i++){
			c=0;
			if(i%4==0) c=1;
			if(i%100==0) c=-2;
			if(i%400==0) c=3;
			if(c>0){
				printf("%d\n",i);
				z++;
			}
		}
		
		if(z==0) printf("NA\n");
	}
	
return 0;
}

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

N,M = map(int,input().split())
ks = [list(map(int,input().split())) for _ in range(M)]
p = list(map(int,input().split()))

Ans = 0

for i in range(2**N):
    switchs = []
    su = 0
    for j in range(N):
        if ((i >> j) & 1):
            switchs.append(j+1)
    for k in range(M):
        count = len(set(switchs)&set(ks[k][1:]))
        if count % 2 == p[k]:
            su += 1
    if su == M:
        Ans += 1
print(Ans)
        
            

Measured memory_bytes: 41968
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define EPS 1e-10
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 16;

int t[MAX_N];
int tt[MAX_N][MAX_N];
int dp[1 << MAX_N];
int min_t[1 << MAX_N][MAX_N];
int n;

int main()
{
    while(1){
        scanf("%d",&n);
        if(n == 0){
            break;
        }
    	rep(i,n){
            scanf("%d",&t[i]);
            rep(j,n){
                scanf("%d",&tt[i][j]);
            }
    	}
        rep(i,(1<<n)){
            rep(j,n){
                int mn = t[j];
                rep(k,n){
                    if((1 << k) & i){
                        mn = min(mn,tt[j][k]);
                    }
                }
                min_t[i][j] = mn;
            }
        }
        rep(i,(1<<n)){
            dp[i] = INF;
        }
        dp[(1<<n)-1] = 0;
        for(int i = (1<<n)-2; i>=0; i--){
            rep(j,n){
                if(!((1 << j) & i)){
                    dp[i] = min(dp[i],dp[i|(1<<j)] + min_t[i][j]);
                }
            }
        }
        printf("%d\n",dp[0]);
    }
    return 0;
}

Measured memory_bytes: 7568
n = gets.to_i
v = gets.split.map(&:to_i)

odd = Hash.new(0).tap {|x| x[0] = 0}
even = Hash.new(0).tap {|x| x[0] = 0}
v.each_with_index do |vi, i|
  odd[vi] += 1 if i.odd?
  even[vi] += 1 if i.even?
end

odd = odd.sort{|a, b| b[1] <=> a[1]}
even = even.sort{|a, b| b[1] <=> a[1]}

ans = 0
if odd[0][0] != even[0][0]
  ans = n - odd[0][1] - even[0][1]
else
  ans = n - [odd[0][1] + even[1][1], odd[1][1] + even[0][1]].max
end
puts ans


Measured memory_bytes: 20344
/*                         _
                        _ooOoo_
                       o8888888o
                       88" . "88
                       (| -_- |)
                       O\  =  /O
                    ____/`---'\____
                  .'  \\|     |//  `.
                 /  \\|||  :  |||//  \
                /  _||||| -:- |||||_  \
                |   | \\\  -  /'| |   |
                | \_|  `\`---'//  |_/ |
                \  .-\__ `-. -'__/-.  /
              ___`. .'  /--.--\  `. .'___
           ."" '<  `.___\_<|>_/___.' _> \"".
          | | :  `- \`. ;`. _/; .'/ /  .' ; |
          \  \ `-.   \_\_`. _.'_/_/  -' _.' /
===========`-.`___`-.__\ \___  /__.-'_.'_.-'================

                  Please give me AC.
*/

#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <string>
#include <sstream>
#include <complex>
#include <bitset>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <chrono>
#include <random>

using namespace std;

using int64 = long long;
using uint64 = unsigned long long;
using vi = vector<int>;
using vl = vector<int64>;
using pii = pair<int, int>;
using pll = pair<int64, int64>;

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(v) (v).begin(), (v).end()
#define print(x) cout << (x) << '\n'
#define print2(x, y) cout << (x) << ' ' << (y) << '\n'
#define print3(x, y, z) cout << (x) << ' ' << (y) << ' ' << (z) << '\n'
#define printn(v) rep(i, (v).size() - 1) cout << (v)[i] << ' '; cout << (v)[n - 1] << '\n';
#define debug(x) cerr << #x << ": " << (x) << '\n'
#define debug2(x, y) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << '\n'
#define debug3(x, y, z) cerr << #x << ": " << (x) << ", " << #y << ": " << (y) << ", " << #z << ": " << (z) << '\n'
#define dbg(v) for (size_t _ = 0; _ < v.size(); ++_){cerr << #v << "[" << _ << "] : " << v[_] << '\n';}
// constant
const int INF = (1<<30) - 1;
const int64 INF64 = (1LL<<62) - 1;

template<typename T> T gcd(T a, T b) {
    if (a < b) return gcd(b, a);
    T r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

template<typename T> T lcm(const T a, const T b) {
    return a / gcd(a, b) * b;
}

template<typename T> bool chmin(T& a, const T& b) {
    if (a > b) return a = b, true; else return false;
}

template<typename T> bool chmax(T& a, const T& b) {
    if (a < b) return a = b, true; else return false;
}

// End of template.

int main() {
    cout << fixed << setprecision(15);
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    // cin.read(buf, sizeof buf); // 注意: ./a.out < in か pbp | ./a.out で入力すること

    string s;
    cin >> s;
    rep(i, s.length()) cout << 'x';
    cout << '\n';

    return 0;
}



Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a,b;
    int suma=0,sumb=0;
    for(int i=0;i<4;i++){
        cin >> a;
        suma += a;
    }
    for(int i=0;i<4;i++){
        cin >> b;
        sumb += b;
    }
    if(sumb > suma){
        cout << sumb << endl;
    }else{
        cout << suma << endl;
    }
    
    
}


Measured memory_bytes: 3104
#include<iostream>
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<map>
#include<fstream>
#include<string>
#include<sstream>
#include<iomanip>
#include<iostream>
#include<numeric>
using namespace std;

int main() {
	char s[3];
	for (int i = 0; i < 3; i++) {
		cin >> s[i];
	}
	int a = 0, b = 0, c = 0;
	for (int i = 0; i < 3; i++) {
		if (s[i] == 'a')
			a++;
		else if (s[i] == 'b')
			b++;
		else
			c++;
	}
	if (a == 1 && b == 1 && c == 1)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<math.h>
#include<queue>
#include<vector>
#include<climits>
#include<map>
#include<string>
#include<functional>
#include<iomanip>
#include<deque>
#include<random>
#include<set>
#include<bitset>
#include<cassert>

using namespace std;
typedef long long ll;
typedef double lldo;
#define mp make_pair
#define pub push_back
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define sz(x) int(x.size())
ll gcd(ll a, ll b) { if (a % b == 0) { return b; } else  return gcd(b, a % b); }
ll lcm(ll a, ll b) { if (a == 0) { return b; }return a / gcd(a, b) * b; }
template<class T>ll LBI(vector<T>& ar, T in) { return lower_bound(ar.begin(), ar.end(), in) - ar.begin(); }
template<class T>ll UBI(vector<T>& ar, T in) { return upper_bound(ar.begin(), ar.end(), in) - ar.begin(); }

ll k;
string s;

int main() {
	cin >> k;
	cin >> s;
	rep(i, min(k, (ll)sz(s)))cout << s[i];
	if (k < sz(s))cout << "..." << endl;
	return 0;
}

Measured memory_bytes: 3636
using System;

class Program {
    static void Main() {
        while (true) {
            var n = int.Parse(Console.ReadLine());
            if (n == 0)
                break;
            Console.WriteLine(NewNumber(n));
        }
    }

    static string NewNumber(int n) {
        return Convert.ToString(n, 8)
                      .Replace('7', '9')
                      .Replace('6', '8')
                      .Replace('5', '7')
                      .Replace('4', '5');
    }
}

Measured memory_bytes: 9008
#include <bits/stdc++.h>
using namespace std;
 
//Optimizations
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
//save time
#define endl '\n'
#define db(x) cerr << "> " << #x << ": " << x << endl
typedef long long ll;
 
//for sorting
#define all(a) a.begin(),a.end()
 
//Constants
#define PI   3.141592653593
#define MOD  1000000007LL
#define EPS  0.000000001
#define INF  0X3f3f3f3f
 
//loops
#define REP(i,n) 	    for(int i=0;i<(n);++i)
#define FOR(i,a,b)      for(int i=(a);i<(b);++i)
#define DFOR(i,a,b)     for(int i=(a);i>=(b);--i)
 
//vectors
#define vi vector<int>
#define vll vector<ll>
#define vii vector<pair<int,int>>
#define vlll vector<pair<ll,ll>>
#define pb 	push_back
 
//pairs
#define pi pair<int,int>
#define pll pair<ll,ll>
#define mp make_pair
#define F first
#define S second
 
//fast I/O
#ifndef _WIN32
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif
#define gc getchar
#define pc putchar
 
//If using cin and cout
#define IOS ios::sync_with_stdio(false)
#define TIE cin.tie(NULL);cout.tie(NULL)
 
//queue
#define di deque<int>
#define dll deque<ll>
#define qi queue<int>
#define PQ priority_queue
 
//general
#define E empty()
 
//Declare all variables and methods needed between this comment and the next one(OCD lol)
 ll MAXN = 0;
 const ll big = 1e18L;
int main(){
    int n , w ; cin >> n >> w ; 

    pll ar[n];
   REP(i, n){
         int weight, value; cin >> weight >> value;
        ar[i] =  {weight, value};
     //   dp[value] = weight;
   }
   for(auto el : ar){
       MAXN+=el.second;
   }
       vll dp(MAXN+1 , big);

   dp[0] = 0;
    REP(i, n){
        
       ll weight = ar[i].first, value = ar[i].second;
        for(ll i = MAXN-value; i >=0 ; --i){
          //  if(i != value)
            dp[i+value] = min(dp[i+value],dp[i]+ weight);
        }
    }
    ll res = 0;
    ll minw;
    for(ll i = MAXN; i>=0 ; --i ){
        if(dp[i] <= w){
        cout << i << endl;
        break;
        }
    }
    
   
}

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

int main(){
  string S;
  cin >>S;
  if((S.at(2)==S.at(3))&&(S.at(4)==S.at(5))){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;
  return 0;
}
     

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

int main(){
  int N;
  cin >> N;
  int a[N];
  rep(i,N)cin >> a[i];
  int temp[N];
  int ans[N];
  for(int i=N-1;i>=0;i--){
    temp[i]=0;
    for(int j=2;j<=N;j++){
      if((i+1)*j>N)break;
      temp[i]+=ans[(i+1)*j-1];
    }
    temp[i]%=2;
    if(temp[i]==a[i])ans[i]=0;
    else ans[i]=1;
  }
  int m=0;
  rep(i,N)if(ans[i]==1)m++;
  cout << m << endl;
  if(m==0){
    // cout << 0 << endl;
    return 0;
  }
  rep(i,N)if(ans[i]==1)cout << i+1 << ' ';
  cout << endl;
  // rep(i,N)cout << ans[i] << endl;
  return 0;
}


Measured memory_bytes: 3200
package main

import (
	"bufio"
	"fmt"
	"os"
)

var N, M, Q int

func main() {
	defer writer.Flush()
	N, M, Q = ReadInt(), ReadInt(), ReadInt()

	L := make([]int, M)
	R := make([]int, M)
	for i := 0; i < M; i++ {
		L[i], R[i] = ReadInt(), ReadInt()
	}
	sumTable := buildSumTable(L, R)

	for i := 0; i < Q; i++ {
		p, q := ReadInt(), ReadInt()
		Println(calcSum(sumTable, p, q))
	}
}

func buildSumTable(L, R []int) [][]int {
	sum := make([][]int, N+1)
	for i := 0; i < N+1; i++ {
		sum[i] = make([]int, N+1)
	}
	for i := 0; i < M; i++ {
		sum[L[i]][R[i]]++
	}
	for i := 1; i <= N; i++ {
		for j := 1; j <= N; j++ {
			sum[i][j] += sum[i-1][j]
			sum[i][j] += sum[i][j-1]
			sum[i][j] -= sum[i-1][j-1]
		}
	}
	return sum
}

func calcSum(sumTable [][]int, L, R int) int {
	return sumTable[R][R] - sumTable[R][L-1] - sumTable[L-1][R] + sumTable[L-1][L-1]
}

var reader = bufio.NewReader(os.Stdin)

func Scan(a ...interface{}) {
	if _, err := fmt.Fscan(reader, a...); err != nil {
		panic(err)
	}
}
func ReadInt() (i int) { Scan(&i); return }

var writer = bufio.NewWriter(os.Stdout)

func Println(a ...interface{}) { fmt.Fprintln(writer, a...) }


Measured memory_bytes: 9672
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
#include<set>
#include<complex>
#include<string>
#include<cstring>
using namespace std;
#define rep2(x,from,to) for(int x=(from);(x)<(to);(x)++)
#define rep(x,to) rep2(x,0,to)
#define INF 100000000
#define debug(x) cout<<#x<<": "<<x<<endl

#define all(x) x.begin(),x.end()
typedef pair<int,int> P;
typedef pair<int,P> PP;
int M;
int n,k;
int GCD;
int a[100005];
int gcd(int x,int y)
{
	if(x%y==0)return y;
	//if(x<y)return gcd(y,x);
	return gcd(y,x%y);
}
int main()
{
	cin>>n>>k;
	rep(i,n)cin>>a[i];
	GCD=a[0];
	rep(i,n-1)
	{
		GCD=gcd(GCD,a[i+1]);
	}
	if(k%GCD!=0)
	{
		cout<<"IMPOSSIBLE"<<endl;
		return 0;
	}
	M=a[0];
	rep(i,n)
	{
		M=max(M,a[i]);
	}
	if(M<k)
	{
		cout<<"IMPOSSIBLE"<<endl;
		return 0;
	}
	cout<<"POSSIBLE"<<endl;
	return 0;
}


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

#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define LL long long
#define pii pair <LL,LL>
#define fi first
#define se second
#define pb push_back
#define mpr make_pair

using namespace std;

const LL MOD=1e9+7;

LL n,m,s,x,y,z,zz,c[60],d[60],dist[60][3000];
bool vis[60][6000];
vector <pair <LL,pii> > g[60];
multiset <pair <LL,pii> > q;

int main()
{
	cin>>n>>m>>s;
	rep(i,m)
	{
		scanf("%lld%lld%lld%lld",&x,&y,&z,&zz);
		g[x].pb(mpr(y,mpr(z,zz)));
		g[y].pb(mpr(x,mpr(z,zz)));
	}
	repn(i,n) cin>>c[i]>>d[i];
	rep(i,55) rep(j,2995) dist[i][j]=1e18;
	dist[1][min(s,2600LL)]=0;
	q.insert(mpr(0,mpr(1,min(s,2600LL))));
	int cnt=0;
	while(!q.empty())
	{
		pair <LL,pii> p=*q.begin();
		//cout<<p.se.fi<<' '<<p.se.se<<' '<<p.fi<<endl;
		q.erase(q.begin());
		if(vis[p.se.fi][p.se.se]) continue;
		vis[p.se.fi][p.se.se]=true;
		//cnt++;
		LL tmp=p.se.se,addt=0;
		while(tmp<2500)
		{
			tmp+=c[p.se.fi];
			addt+=d[p.se.fi];
			if(dist[p.se.fi][tmp]>p.fi+addt)
			{
				dist[p.se.fi][tmp]=p.fi+addt;
				q.insert(mpr(dist[p.se.fi][tmp],mpr(p.se.fi,tmp))); 
			}
			else break;
		}
		rep(i,g[p.se.fi].size())
		{
			if(p.se.se>=g[p.se.fi][i].se.fi)
			{
				if(dist[g[p.se.fi][i].fi][p.se.se-g[p.se.fi][i].se.fi]>p.fi+g[p.se.fi][i].se.se)
				{
					dist[g[p.se.fi][i].fi][p.se.se-g[p.se.fi][i].se.fi]=p.fi+g[p.se.fi][i].se.se;
					q.insert(mpr(p.fi+g[p.se.fi][i].se.se,mpr(g[p.se.fi][i].fi,p.se.se-g[p.se.fi][i].se.fi)));
				}
			}
		}
	}
	for(int i=2;i<=n;i++)
	{
		LL ans=1e18;
		rep(j,2601) ans=min(ans,dist[i][j]);
		cout<<ans<<endl;
	}
	//cout<<cnt<<endl;
	return 0;
}

Measured memory_bytes: 200040
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.*;



public class Main {
	static int INF = 2 << 27;
	public static void main(String[] args) {	
		//FastScanner sc = new FastScanner();
		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		while(true) {
			int n = sc.nextInt();
			if(n == 0) break;
			int[] p = new int[n];
			int[] t = new int[n];
			for(int i = 0; i < n; i++) {
				p[i] = sc.nextInt();
				t[i] = sc.nextInt();
				if(i != 0) {
				}
			}
			int[][] dp = new int[n+1][4];
			for(int i = 0; i < dp.length; i++) {
				Arrays.fill(dp[i],INF);
			}
			dp[0][0] = 0;
			int BAD = -1;
			for(int i = 0; i < n; i++) {
				boolean ok = false;
				for(int k = 0; k < 4; k++) {
					if(dp[i][k] == INF) continue;
					int len = p[i];
					int time = t[i];
					if(i != 0) {
						len = Math.abs(p[i-1] - p[i]);
						time = t[i] - t[i-1];
					}
					
					if(k + 1 <= 3 && len*(k+1) <= time) {
						if(i != n-1) dp[i+1][k+1] = Math.min(dp[i+1][k+1], dp[i][k] + len);
						else dp[i+1][0] = Math.min(dp[i+1][0], dp[i][k] + len + p[i]);
						ok = true;
					}
					
					if(i != 0 && p[i-1]*(k+1) + p[i] <= time) {
						if(i != n-1) dp[i+1][1] = Math.min(dp[i+1][1], dp[i][k] + p[i-1] + p[i]);
						else dp[i+1][0] =         Math.min(dp[i+1][0], dp[i][k] + p[i-1] + p[i] + p[i]);
						ok = true;
					}
				}
				if(!ok && BAD == -1) {
					BAD = (i+1);
				}
			}
			int LOW = INF;
			for(int i = 0; i < 4; i++) {
				LOW = Math.min(dp[n][0],LOW);
			}
			if(BAD != -1) System.out.println("NG " + BAD);
			else System.out.println("OK " + LOW);
			
			
			
			
			
			
		}
	}
}

Measured memory_bytes: 31648
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<set>

#define ll long long
using namespace std;
ll n;
ll a[6];
ll ans;
ll m;

int main()
{
    cin>>n;

    for (int i=1; i<=5; ++i)
    {
        cin>>a[i];
        if (i==1) m=a[1];
        else 
        {
            if (a[i]<m)
                m=a[i];
        }
    }
    ans = n/m;
    if (n%m!=0)
        ans+=1;
    cout<<ans+4<<endl;
    return 0;
}



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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl




typedef long long ll;
const ll mod = 1e9+7;
const int maxn = 1010;

ll pw(ll x, ll y) {
    ll res=1;
    while (y) {
	if (y%2) {
	    res=res*x;
	    res%=mod;
	}
	x=x*x;
	x%=mod;
	y=y/2;
    }
    
    res%=mod;
    res+=mod;
    return res%mod;
}

ll add(ll x, ll y) {
    x %= mod;
    y %= mod;
    x += y;
    x %= mod;
    return x;
}


ll C[maxn][maxn];
ll fac[maxn*maxn], ifac[maxn*maxn], inv[maxn*maxn];

int n,a,b,c,d;


ll nck(int n, int k) {
    if (n<k) return 0;
    return C[n][k];
}

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

    for (int i=0; i<=1000; i++) {
	C[i][0] = C[i][i] = 1;
	for (int j=1; j<i; j++) {
	    C[i][j] = (C[i-1][j] + C[i-1][j-1])%mod;
	}
    }
    assert(C[4][2]==6);

    fac[0]=ifac[0]=1;
    for (int i=1; i<=1000000; i++) {
	fac[i]=fac[i-1]*i%mod;
    }
    
    inv[1]=1;
    for (int i=2; i<=1000000; i++) {
	inv[i] = (mod - (mod/i) * inv[mod%i] % mod) % mod;
    }

    for (int i=1; i<=1000000; i++) {
	ifac[i] = ifac[i-1]*inv[i]%mod;
    }
    assert(ifac[1] == 1);
    assert(inv[6] == ifac[3]);
    assert(inv[47] == pw(47, mod-2));



    cin>>n>>a>>b>>c>>d;

    vector<ll> dp(n+1, 0);//num ways to use j ppl at the current iteration
    dp[0] = 1;

    //iterate over group size
    for (int i=a; i<=b; i++) {
	vector<ll> nxt(n+1, 0);

	for (int j=0; j<=n; j++) {
	    if (dp[j] == 0) continue;
	    ll ways = 1;
	    for (int k=0; k<=n-j; k+=i) {
		if (k==0 || (c<=k/i && k/i<=d)) {
		    nxt[j+k] = add(nxt[j+k], dp[j]*ways);
		}

		//out of the remaining ppl, pick i ppl for the next group
		//now there are (k/i)+1 groups, and order that we picked them doesn't matter.
		ways = ways*nck(n-j-k, i)%mod*inv[k/i+1]%mod;
			
	    }
	}

	swap(nxt, dp);
    }


    cout<<dp[n]<<endl;    

    return 0;
}


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

int main(void){
    int a;
    string s;
    cin >> a >> s;
    if(a >= 3200){
        cout << s<< endl;
    }else{
        cout << "red" << endl;
    }
    return 0;
}


Measured memory_bytes: 256
from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]

L = defaultdict(int)
for a in A:
    L[a] += 1
Lkey = sorted(L, reverse = True)

for i in range(len(Lkey)):
    if L[Lkey[i]] >= 4:
        print(Lkey[i]**2)
        break
    elif L[Lkey[i]] >= 2:
        for j in range(i+1, len(Lkey)):
            if L[Lkey[j]] >= 2:
                print(Lkey[i] * Lkey[j])
                break
        break
else:
    print(0)

Measured memory_bytes: 18600
sieve = [True] * 100001
#one-based-index
def mark(sieve,x):
    for i in range(x+x,len(sieve),x):
        sieve[i] = False

for x in range(2,int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve,x)

sieve[0] = False
sieve[1] = False

for i in range(len(sieve)-2,2,-2):
    if sieve[i]:
        if not(sieve[(i+1)//2]):
            sieve[i] = False #2017likeでない

sieve[2] = False

cnt = [0] * 100002
for i,s in enumerate(sieve):
    if s:
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]

q = int(input())

for i in range(q):
    l, r = map(int,input().split())
    print(cnt[r] - cnt[l-1])

Measured memory_bytes: 4980
def games(n,v,c):
    sum = 0
    for i in range(int(n)):
        if v[i]-c[i]>=0:
            sum = sum+v[i]-c[i]
    return sum
n = input()
v=list(map(int, input().split()))
c=list(map(int, input().split()))
print(games(n,v,c))

Measured memory_bytes: 3060
N, K = map(int, input().split())
H = list(map(int, input().split()))

cost = [1e30 for _ in range(N)]
cost[0] = 0

for i in range(N):
  for k in range(i+1, min(N, i+K+1)):
    cost[k] = min(cost[k], cost[i] + abs(H[k] - H[i]))

print(cost[N-1])


Measured memory_bytes: 58848
k, n = map(int, input().split())
a = list(map(int, input().split()))
d = 0
for i in range(n-1):
    D = a[i+1] - a[i]
    if d < D:
        d = D

if d < k - a[-1] + a[0]:
    d = k - a[-1] + a[0]

print(k - d)

Measured memory_bytes: 26060
#include <bits/stdc++.h>
using namespace std;
#define double long double
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define sp(p) cout<<setprecision(16)<<fixed<<p<<endl;
#define debug(x) cerr<<#x<<": "<<x<<endl;
#define all(a) a.begin(),a.end()
#define SORT(a) sort(all(a))
#define rsort(a) sort(all(a),greater<>())
// #define judge(f,y,n) cout<<(f?y:n)<<"\n";
#define judge(f) cout<<(f?YES:NO)<<"\n";
#define debg(a) cout<<#a<<" "<<a<<endl;
#define show(a) for(cont &y:a){for(cont &x:y){cout<<x<<" ";}cout<<endl;}
template<class T>inline int out(const T &t){ print(t); putchar('\n'); return 0; }
template<class T>inline T gcd(T a,T b){if(b==0)return a; return(gcd(b,a%b));}
template<class T>inline T lcm(T a,T b){return a/gcd(a,b)*b;}
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> V;
const long long MOD=1000000007;
const long long INF = 1e18;
clock_t time_ini = clock();
double time_diff(){
  ll time_tmp = clock();
  const double time = static_cast<double>(time_tmp - time_ini) / CLOCKS_PER_SEC * 1000.0;
  return time;
}
#define saiaku if(time_diff() > 1990)
vector <ll> dp;

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

void solve_old(long long N, std::vector<long long> t, std::vector<long long> x, std::vector<long long> y){
    bool flg = false;
    for (ll i = 0; i < N; i++) {
        ll dt = (i ? t[i] - t[i-1] : t[i]);
        ll d = (i ? abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]) : abs(x[i]) + abs(y[i]));
        if (d <= dt && ((dt%2) == (d%2)) ) {
            flg = true;
        } else {
            flg = false;
            break;
        }
    }
    cout << (flg ? YES : NO) << "\n";
}

void solve(long long N, std::vector<long long> t, std::vector<long long> x, std::vector<long long> y){
    bool flg = true;
    for (ll i = 0; i < N; i++) {
        ll dt = (i ? t[i] - t[i-1] : t[i]);
        ll d = (i ? abs(x[i] - x[i-1]) + abs(y[i] - y[i-1]) : abs(x[i]) + abs(y[i]));
        if (!(d <= dt && ((dt%2) == (d%2))) ) {
            flg = false;
            break;
        }
    }
    judge(flg);
}

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


Measured memory_bytes: 2560
basea = ord("a")
basez = ord("z")

def slide(c):
  ordc = ord(c)  
  diff = ordc - basea
  diff += 1
  diff %= 26
  return chr(basea + diff)

while True:
  try:
    s = input()
    while True:
      if "the" in s or "this" in s or "that" in s:
        print(s)
        break
      s = "".join([slide(c) if basea <= ord(c) <= basez else c for c in s])
  except EOFError:
    break


Measured memory_bytes: 5568
#include<stdio.h>
int main(){
	int n,i,a[20]={},v[20]={};
	int tmp;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		
		scanf("%d%d",&a[i],&v[i]);
	}
	int j,h;
	for(j=0;j<n-1;j++){
		for(h=n-1;h>j;h--){
			
			if(v[h]>v[h-1]){
				tmp=v[h];
				v[h]=v[h-1];
				v[h-1]=tmp;
				tmp=a[h];
				a[h]=a[h-1];
				a[h-1]=tmp;
				
			}
		}
		
	}
	int max=v[0];
	for(i=1;i<n;i++){
		if(max==v[i]){
			if(a[0]>a[i]){
				tmp=a[0];
				a[0]=a[i];
				a[i]=tmp;
			}
		}
	}
	
	
	printf("%d %d\n",a[0],v[0]);
	return 0;
}

Measured memory_bytes: 1028
N = int(input())
A = list(map(int, input().split()))
sm1=0
sm2=0
cnt=0
cnt2=0

for i in range(N):
    sm1+=A[i]
    if i%2==1:
        if sm1>=0:               
            cnt+=sm1+1
            sm1=-1
    else:
        if sm1<=0:               
            cnt+=sm1*-1+1
            sm1=1

for i in range(N):
    sm2+=A[i]
    if i%2==1:
        if sm2<=0:
            cnt2+=sm2*-1+1
            sm2=1
    else:
        if sm2>=0:
            cnt2+=sm2+1
            sm2=-1
print(min(cnt,cnt2))

Measured memory_bytes: 19920
n, k = map(int, input().split())
a = list(map(int, input().split()))
mina = min(a)
idx = a.index(1)

left = idx
right = n-idx-1
ans = (left+(k-1)-1)//(k-1) + (right+(k-1)-1)//(k-1)

if left%(k-1)+right%(k-1)+1<=k:
    if left%(k-1) > 0 and right%(k-1) > 0:
        ans-=1
print(ans)



Measured memory_bytes: 20636
(setq n(read))
(setq a(*(-(read)(read))1000))
(setq ans 1000000000)
(setq id 0)
(dotimes(i n)
  (setq h(abs(- a(*(read)6))))
  (if(> ans h)(progn(setq id(1+ i))(setq ans h))))
(princ id)

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

using ll = long long;
using ull = unsigned long long;
using st = string;
using ch = char;
using db = double;
using bl = bool;
using vll = vector<long long>;
using vdb = vector<db>;
using vst = vector<st>;
using vch = vector<char>;
using vbl = vector<bl>;
using vvll = vector<vll>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
#define rep(i, m, n) for (ll i = (ll)(m); i < (ll)(n); i++)
#define vrep(i, vec) for(auto& i : vec)
#define vin(vec) for(auto& i : vec) cin >> i
#define all(v) v.begin(), v.end()
template<class T> inline bool chmin(T& a, T b){if(a > b){a = b;return true;} return false;}
template<class T> inline bool chmax(T& a, T b){if(a < b){a = b;return true;} return false;}
const ll mod = 1000000007;
const ll inf = 1LL << 60;
const db pi = acos(-1.0L);

int main(){
	ll n;
	cin >> n;
	n %= 10;
	if(n == 3) cout << "bon" << endl;
	else if(n == 0 || n == 1 || n == 6 || n == 8) cout << "pon" << endl;
	else cout << "hon" << endl;
}

Measured memory_bytes: 3624
/* 競プロ用のテンプレ
 * SKMT
 * 作成日   2020年09月06日  16:34
 * ファイル名    rp.cpp
 */
#include<bits/stdc++.h>
using namespace std;

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

int main(int argc, char const* argv[]){
	long long a,b;
	cin >> a>>b;
	if(a*b <= 0 || a-b == 0){
		cout <<"Zero"<< endl;
	}
	else if((a>0 && b>0) || ((b-a)+1)%2 ==0){
		cout << "Positive" << endl;
	}
	else if(((b-a)+1)%2 == 1){
		cout << "Negative" << endl;
	}
	return 0;
}


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

typedef long long ll;

int main() {
    int S, W;
    cin >> S >> W;
    if (W >= S) cout << "unsafe\n";
    else cout << "safe\n";
}


Measured memory_bytes: 3596
#include <iostream>
#include <utility>
#include <tuple>
#include <vector>
#include <algorithm>
#include <sstream>
using namespace std;

int main() {

int n; cin >> n;
int x, y;

using P = pair<int,int>;
vector<P> v;
while(cin >> x >> y) {
  v.push_back({x, y});
}
std::sort(v.begin(), v.end());

for(auto& p : v) cout << p.first << " " << p.second << endl;
}



Measured memory_bytes: 3872
#include<bits/stdc++.h>
#define FOR0(i,n) for(i=0;i<n;i++)
#define FOR(i,j,n) for(i=j;i<n;i++)
#define FORD(i,j,k) for(i=j;i>=k;i--)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define inf 1000000000
#define ninf -1000000000
#define endl '\n' 
#define she_told_me_dont_worry ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
// Use cout.flush() for interactive problems.
// Use this for increased stack size: g++ -o a.exe -Wl,--stack=256000000 -O2 source.cpp
inline long long  MAX2(long long  a, long long int b){return (a)>(b)?(a):(b);}
inline long long  MAX3(long long  a, long long  b,long long  c){return (a)>(b)?((a)>(c)?(a):(c)):((b)>(c)?(b):(c));}
inline long long  MIN2(long long  a, long long  b){return (a)<(b)?(a):(b);}
inline long long  MIN3(long long  a, long long b,long long c){return (a)<(b)?((a)<(c)?(a):(c)):((b)<(c)?(b):(c));}
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< ii > vii;
int main()
{
    she_told_me_dont_worry
    int n, m;
    int l, r;
    cin>>n>>m;
    int i;
    int ml = ninf, mr = inf;
    FOR0(i, m)
    {
        cin>>l>>r;
        ml = MAX2(ml, l);
        mr = MIN2(mr, r);
    }
    int ans = 0;
    if(mr >= ml) 
        ans = mr - ml + 1;
    cout<<ans;
    cerr <<endl<< "Time elapsed : " << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(void){
    int a,b,x,ans;
    cin>>a>>b>>x>>ans;
    if (a>2*b){
        ans=(x/500)*b;
        if (x%500!=0){
            ans+=b;
        }
    }
    else {
        ans=(x/1000)*a;
        if (x%1000!=0){
            if (x%1000<=500&&a>b){
                ans+=b;
            }
            else {
                ans+=a;
            }
        }
    }
    cout<<ans<<endl;
}



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

int main(){
	int n,m,c;
	cin >> n >> m >> c;
	
	vector<int> b(m);
	rep(i,m) cin >> b[i];
	
	vector<vector<int>> a(n,vector<int>(m));
	rep(i,n){
		rep(j,m){
			cin >> a[i][j];
		}
	}
	
	int res = 0;
	rep(i,n){
		int tmp = 0;
		rep(j,m){
			tmp += a[i][j] * b[j];
		}
		tmp += c;
		if(tmp>0) res++;
	}
	
	cout << res << endl;
	return 0;
}

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

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

using namespace std;

template<class T>
class fenwick_tree {
private:
    const size_t size;
    const std::function<T(T, T)> f;
    const T unit;
    std::vector<T> a;
public:
    fenwick_tree(size_t size, std::function<T(T, T)> f, T unit) : size(size), f(f), unit(unit), a(size, unit) { }

    void update(size_t i, T x) {
        for (size_t j = i; j < size; j |= j + 1) {
            a[j] = f(a[j], x);
        }
    }

    T query(size_t i) const {
        T result = unit;
        for (size_t j = i; j > 0; j = (j & (j + 1))) {
            result = f(result, a[--j]);
        }
        return result;
    }
};

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

    int N, Q;
    string S;
    cin >> N >> S >> Q;
    vector<int> s(N);
    vector<fenwick_tree<int>> fenwicks(26, fenwick_tree<int>(N, [](int x, int y) { return x + y; }, 0));
    REP(i, N) {
        s[i] = S[i] - 'a';
        fenwicks[s[i]].update(i, 1);
    }
    REP(_, Q) {
        int query_type;
        cin >> query_type;
        if (query_type == 1) {
            int i;
            char c;
            cin >> i >> c;
            --i;
            c -= 'a';
            char c_before = s[i];
            s[i] = c;
            if (c != c_before) {
                fenwicks[c_before].update(i, -1);
                fenwicks[c].update(i, 1);
            }
        } else { // if (query_type == 2) {
            int l, r;
            cin >> l >> r;
            --l;
            int cnt = 0;
            REP(c, 26) {
                if (fenwicks[c].query(r) - fenwicks[c].query(l) > 0) {
                    ++cnt;
                }
            }
            cout << cnt << '\n';
        }
    }
    cout << flush;

    return 0;
}


Measured memory_bytes: 55708