akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;
#define MAX 500000
#define INF 2000000000

int L[MAX/2+2],R[MAX/2+2];
int t=0;

void merge(int A[],int n,int left,int mid,int right){
  int n1=mid-left;
  int n2=right-mid;
  int i,j;
  
  for(i=0;i<n1;i++){
    L[i]=A[left+i];
  }
  for(i=0;i<n2;i++){
    R[i]=A[mid+i];
  }
  L[n1]=INF;
  R[n2]=INF;
  i=0;
  j=0;
  for(int k=left;k<right;k++){
    t++;
    if(L[i]<=R[j]){
      A[k]=L[i];
      i+=1;
    }
    else{
      A[k]=R[j];
      j+=1;
    }
  }
}

void mergeSort(int A[],int n,int left,int right){
  if(left+1<right){
    int mid=(left+right)/2;
    mergeSort(A,n,left,mid);
    mergeSort(A,n,mid,right);
    merge(A,n,left,mid,right);
  }
}

int main(){
  int n,A[MAX];
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>A[i];
  }

  mergeSort(A,n,0,n);

  for(int i=0;i<n;i++){
    if(i!=0) cout<<" ";
    cout<<A[i];
  }
  cout<<endl;

  cout<<t<<endl;

  return 0;
}

Measured memory_bytes: 5064
#include<bits/stdc++.h>
#define S 2500005
#define N 1005
using namespace std;
typedef pair<int,int> P;
struct d{
  int a,b,c;
  d(){}
  d(int A,int B,int C){
    a=A,b=B,c=C;
  };
  bool operator<(const d&r)const{
    if(a!=r.a)return a<r.a;
    return b<r.b;
  }
};

int n,slen,tlen,r[S];
char s[S],t[N];
d ran[S];
P a[S];

void init(){
  for(int i=0;i<slen;i++)r[i]=s[i];
  int x=1;
  r[slen]=0;
  while(1){
    for(int i=0;i<slen;i++){
      int o=i+x;
      if(o>slen)o=slen;
      ran[i]=d(r[i],r[o],i);
    }
    sort(ran,ran+slen);
    int cnt=1;
    for(int i=0;i<slen;i++){
      r[ran[i].c]=cnt;
      if(ran[i].a==ran[i+1].a&&ran[i].b==ran[i+1].b)
	continue;
      cnt++;
    }
    if(x>slen)break;
    x*=2;
  }
  for(int i=0;i<slen;i++)a[i]=P(r[i],i);
  sort(a,a+slen);
}

bool bynary_search(){
  int L=0,R=slen;
  while(L<R){
    int M=(L+R)/2;
    if(strncmp(s+a[M].second,t,tlen)<0)L=M+1;
    else R=M;
  }
  if(!strncmp(s+a[L].second,t,tlen))return true;
  return false;
}

int main(){
  scanf("%s%d",s,&n);
  slen=strlen(s);
  init();  
  while(n--){
    scanf("%s",t);
    tlen=strlen(t);
    if(bynary_search())printf("1\n");
    else printf("0\n");
  }
  return 0;
}

Measured memory_bytes: 42144
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 999999999999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(30) << S << endl
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,S) vector<vector<L>> K(N,vector<L>(M,S))
#define TV(K,L,N,M,R,S) vector<vector<vector<L>>> K(N,vector<vector<L>>(M,vector<L>(R,S)))
#define pint pair<lli,lli>
#define paf(L,R) pair<L,R>
#define mod 1000000007
#define MAX 5100000
#define ALL(a)  a.begin(),a.end()
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int main(){
  lli C,D,E,F,N,M,K,L,R,X,Y,Z,H,W,sum=0,num=0,flag=0;string S,T;
  cin >> N;
  DV(A,lli,N+1,2,0);
  DV(dp,lli,N+1,3,0);
  rep(i,1,N+1)cin >> A[i][0] >> A[i][1] >> A[i][2];
  rep(i,1,N+1){
    dp[i][0]=max(dp[i-1][1],dp[i-1][2])+A[i][0];
    dp[i][1]=max(dp[i-1][0],dp[i-1][2])+A[i][1];
    dp[i][2]=max(dp[i-1][0],dp[i-1][1])+A[i][2];
  }
  Out(max(max(dp[N][0],dp[N][1]),dp[N][2]));
}

Measured memory_bytes: 11136
import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
from collections import deque
def getN():
    return int(input())
def getList():
    return list(map(int, input().split()))
import math

h, w = getList()
INF = 1000000000

dist = [[INF for i in range(w)] for j in range(h)]
grid = []
udlr = [(0, 1), (0, -1), (-1, 0), (1, 0)]

white = 0
for i in range(h):
    state = input().strip()
    grid.append(state)
    white += state.count(".")

dist[0][0] = 1
def bfs(grid, dist):
    q = deque([])
    q.append((0, 0))
    while(q):
        a, b = q.popleft()
        # print(a, b)
        cur = dist[a][b]
        for mv in udlr:
            c, d = mv
            e, f = a + c, b + d
            if e >= 0 and e < h and f >= 0 and f < w:
                if grid[e][f] == ".":
                    if dist[e][f] > cur + 1:
                        dist[e][f] = cur + 1
                        q.append((e, f))

bfs(grid, dist)

# for g in grid:
#     print(g)
# for d in dist:
#     print(d)
if dist[h-1][w-1] == INF:
    print(-1)

else:
    print(white - dist[h-1][w-1])


Measured memory_bytes: 40048
//ysh_gpta
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
using namespace std;
typedef long long ll;
#define vb vector<bool>
#define vi vector<ll>
#define vvi vector<vi>
#define pii pair<ll,ll>
#define vpii vector<pair<ll,ll> >
#define mkp make_pair
#define pb push_back
#define INF 1000000000000000
#define MOD 1000000007
#define ff first
#define ss second
#define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
//ll gcd( ll a, ll b ){if(b==0) return a; else return gcd( b, a%b );}
//ll ncr(ll n,ll r){ll ans=1;r=min(r,n-r);for (int i=1;i<=r;i++){ans*=(n-r+i);ans/=i;}return ans;}
//void printArray(vi &v){for(int i=0;i<v.size();i++) cout<<v[i]<<endl; cout<<endl; }

ll dp[405][405];
ll sum[405];

ll solve(ll i,ll j){
    assert(j>i);
    if(j-i==1)
    return 0;
    if(dp[i][j]!=-1)
    return dp[i][j];
    ll mn = LONG_LONG_MAX;
    for(ll k=i+1;k<j;k++)
    mn = min(mn,solve(i,k)+solve(k,j)+sum[j]-sum[i]);
    return dp[i][j] = mn;
}

int main(){
   FastIO
   ll n;
   cin>>n;
   vi v(n);
   sum[0] = 0;
   memset(dp,-1,sizeof(dp));
   for(int i=0;i<n;i++){
       cin>>v[i];
       sum[i+1] = sum[i]+v[i];
   }
//    for(ll l=2;l<=n;l++){
//        for(ll i=0;i<n-l+1;i++){
//            ll j=i+l-1;
//            if(l==2){
//                dp[i][j]=dp[i][j-1]+dp[i+1][j];
//            }else{
//                dp[i][j] = min(dp[i][j-1]+v[j]+sum[j]-sum[i],dp[i+1][j]+v[i]+sum[j+1]-sum[i+1]);
//            }
//        }
//    }
//    for(int i=0;i<n;i++){
//        for(int j=0;j<n;j++)
//        cout<<dp[i][j]<<" ";
//        cout<<endl;
//    }
   cout<<solve(0,n);
   return 0;
}

Measured memory_bytes: 1536
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
#define deb(x) cerr << "\n" \
                    << #x << "=" << x << "\n";
#define deb2(x, y) cerr << "\n"                   \
                        << #x << "=" << x << "\n" \
                        << #y << "=" << y << "\n";
#define w(x) \
  int x;     \
  cin >> x;  \
  while (x--)
const int N = 2e5+1;
int x[N],y[N],n;
char d[N];
void rotate() {
  
  for(int i=0;i<n;i++) {
    if(d[i] == 'R') d[i] = 'D';
    else
    if(d[i] == 'D') d[i] = 'L';
    else
    if(d[i] == 'L') d[i] = 'U';
    else
    if(d[i] == 'U') d[i] = 'R';
    //swap(x[i],y[i]);
    int temp = x[i];
    x[i] = y[i];
    y[i] = 200000 - temp;
  }
}

int solve1() {
  // U and R
  vector<vector<pair<int,char>>> v(2*N);
  int m = 2 * N;
  int ans = 1e16;
  for(int i=0;i<n;i++) {
    if(!(d[i] == 'R' || d[i] == 'U'))
      continue;
    v[x[i]+y[i]].emplace_back(x[i],d[i]);
  }
  for(int i=0;i<2*N;i++) {
    sort(v[i].begin(),v[i].end());
    if(!v[i].empty())
    for(int j=0;j<v[i].size()-1;j++) {
      if(!(v[i][j].second == 'R' && v[i][j+1].second == 'U'))
        continue;
      ans = min(ans, v[i][j+1].first - v[i][j].first);
    }
  }
  return ans*10;
}
int solve2() {
  // for U and D
  vector<vector<pair<int,char>>> v(N);
  int ans = 1e16;
  for(int i=0;i<n;i++) {
    if(!(d[i] == 'U' || d[i] == 'D'))
      continue;
    v[x[i]].emplace_back(y[i],d[i]);
  }
  for(int i=0;i<N;i++) {
    sort(v[i].begin(),v[i].end());
    if(!v[i].empty())
    for(int j=0;j<v[i].size()-1;j++) {
      if(!(v[i][j].second == 'U' && v[i][j+1].second == 'D'))
        continue;
      ans = min(ans,v[i][j+1].first - v[i][j].first);
    }
  }
  return ans*5;
}
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin>>n;
  for(int i=0;i<n;i++) {
    cin>>x[i]>>y[i]>>d[i];
  }
  int ans = 1e16;
  for(int i=0;i<4;i++) {
    ans = min(ans, solve1());
    ans = min(ans, solve2());
    rotate();
  }
  if(ans == 1e16) cout<<"SAFE\n";
  else 
  cout<<ans;
  return 0;
}

Measured memory_bytes: 27112
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1LL << 50;
ll dp[310][310];
ll cost[310][310];
string b[300];

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

	int H, W;
	cin >> H >> W;
	for(int i = 0; i < H; i++) {
		cin >> b[i];
	}

	ll ans = 0;
	for(int t = 0; t < W - 1; t++) {

		string s1, s2;
		for(int i = 0; i < H; i++) {
			s1 += b[i][t], s2 += b[i][t + 1];
		}
		memset(cost, 0, sizeof cost);
		for(int i = 0; i < H; i++) {
			int c1 = 0, c2 = 0;
			for(int j = 0; i + j < H; j++) {
				if(s1[j] == s2[i + j]) c1++;
				if(s1[i + j] == s2[j]) c2++;
			}
			cost[i][0] = c1;
			cost[0][i] = c2;
		}
		for(int i = 1; i < H; i++) {
			for(int j = 1; j < H; j++) {
				int c = cost[i - 1][j - 1];
				if(s1[H - 1 - (i - 1)] == s2[H - 1 - (j - 1)]) c--;
				cost[i][j] = c;
				/*cout << "i " << i << " j " << j << endl;
				cout << s1.substr(0, H - i) + " " + s2.substr(0, H - j) << endl;
				cout << c << endl;
				cout << endl;*/
			}
		}

		fill((ll*)begin(dp), (ll*)end(dp), INF);
		dp[0][0] = 0;
		for(int i = 0; i <= H; i++) {
			for(int j = 0; j <= H; j++) {
				if(i + 1 <= H) {
					dp[i + 1][j] = min(dp[i + 1][j], dp[i][j] + cost[i][j]);
				}
				if(j + 1 <= H) {
					dp[i][j + 1] = min(dp[i][j + 1], dp[i][j] + cost[i][j]);;
				}
			}
		}
		ans += dp[H][H];
	}

	cout << ans << endl;
}

Measured memory_bytes: 1920
# coding: utf-8


def x():
    n = input()
    a = map(int, raw_input().split())
    c = 0
    while True:
        for i in range(0, n):
            if a[i] % 2 == 0:
                a[i] /= 2
            else:
                return c
        c += 1

print x()


Measured memory_bytes: 2568
#include <iostream>
#include <string>
#include <utility>
#include <algorithm>
#include <vector>

using namespace std;

typedef pair<int,string> P;

vector<P> anime;
vector<P> fav;

bool Overlap(int x,int y) {
	int _max=max(x,y),_min=min(x,y);
	return (_max-_min)<30;
}

bool Check(P& p) {
	for(int i=0;i<fav.size();i++) {
		if(p.second!=fav[i].second&&Overlap(p.first,fav[i].first)) return true;
	}
	return false;
}

int main() {
	int n;
	while(cin>>n,n) {
		anime.clear();
		fav.clear();
		for(int i=0;i<n;i++) {
			string name;
			int weekday,start;
			cin>>name>>weekday>>start;
			start=weekday*1440+start/100*60+start%100;
			if(start<360) start+=1440*7;
			anime.push_back(P(start,name));
		}
		sort(anime.begin(),anime.end());
		int p;cin>>p;
		for(int i=0;i<p;i++) {
			string name;cin>>name;
			for(int i=0;i<n;i++) {
				if(anime[i].second==name) {
					fav.push_back(anime[i]);
					break;
				}
			}
		}
		bool ok=true;
		for(int i=0;i<p&&ok;i++) {
			for(int j=0;j<p&&ok;j++) {
				if(i!=j&&Overlap(fav[i].first,fav[j].first)) ok=false;
			}
		}
		if(!ok) {cout<<-1<<endl;continue;}
		anime.erase(remove_if(anime.begin(),anime.end(),Check),anime.end());
		vector<int> vst;
		int count=0;
		for(int i=0;i<anime.size();i++) {
			bool ok=true;
			for(int j=0;j<vst.size()&&ok;j++) {
				if(Overlap(anime[i].first,vst[j])) ok=false;
			}
			if(ok) {
				count++;
				vst.push_back(anime[i].first);
			}
		}
		cout<<count<<endl;
	}
}

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

using namespace std;

#define sp(x) cout<<setprecision(x);
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define all(a) (a).begin(), (a).end()
#define inf 10000000
#define linf INT64_MAX*0.99
#define print(s) cout<<(s)<<endl
#define lint long long
#define yes "Yes"
#define no "No"

typedef pair<int, int> P;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a,b; cin>>a>>b;
    int ans = (a-1)*(b-1);
    print(ans);
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using lint=int64_t;
using namespace std;

int main()
{
	int N;
	string S;

	cin >> N >> S;

	int ans=N;
	for(int i=0;i<N-1;i++)
	{
		if(S[i]==S[i+1])
			ans--;
	}

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



Measured memory_bytes: 512
#include<stdio.h>
int main(void)
{
	double a,b;
	scanf("%lf %lf",&a,&b);
	if(a>b){
		printf("GREATER\n");
	}
	else if(a<b){
		printf("LESS\n");
	}
	else{
		printf("EQUAL\n");
	}
	return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
static const int N=1000;
int lcs(string x,string y){
	int c[N+1][N+1];
	int m=x.size();
	int n=y.size();
	int max1=0;
	x=" "+x;
	y=" "+y;
	for(int i=0;i<=m;i++){
		c[i][0]=0;
	}
	for(int j=1;j<=n;j++){
		c[0][j]=0;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			if(x[i]==y[j]){
				c[i][j]=c[i-1][j-1]+1;
			}else{
				c[i][j]=max(c[i-1][j],c[i][j-1]);
			}
			max1=max(max1,c[i][j]);
		}
	}
	return max1;
}
int main(){
	string s1,s2;
	int n;
	std::cin>>n;
	for(int i=0;i<n;i++){
		std::cin>>s1>>s2;
		std::cout<<lcs(s1,s2)<<"\n";
	}
	return 0;
}


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

long long gcd(long long a, long long b)
{
	if (a < b) {
		long long t = a;
		a = b;
		b = t;
	}
 
	long long r = a % b;
	while (r != 0) {
		a = b;
		b = r;
		r = a % b;
	}
 
	return b;
}

int main(){
  int N;
  cin >> N;
  vector<long long > v(N);
  for(int i = 0; i < N; i++){
    cin >> v.at(i);
  }
  long long tmp = gcd(v[0], v[1]);
  
  for(int i = 2; i < N; i++){
    tmp = gcd(tmp, v[i]);
  }
  cout << tmp << endl;

}

Measured memory_bytes: 1024
from itertools import accumulate
import sys
from heapq import heappush, heappop

def main():
    input = sys.stdin.readline
    N, K = map(int, input().split())
    S = list(input())
    S[K-1] = S[K-1].lower()
    print("".join(S))

if __name__ == '__main__':
    main()


Measured memory_bytes: 3060
#include<iostream>
#include<string>
#include<stdio.h>
#include<cctype>
#include<algorithm>
#include<climits>
#include<cmath>
#include<map>
#include<vector>
#define INF INT_MAX
using namespace std;

int N;
int p[100];
int cnt;

int main(){
	cin >> N;
	for (int i = 1; i <= N; i++){
		cin >> p[i];
		if (p[i] != i)cnt++;
	}
	if (cnt == 2 || cnt == 0){
		cout << "YES" << endl;
	}
	else{
		cout << "NO" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
N = int(input())
life = list(map(int, input().split()))
while len(life) >1:
    life.sort()
    life_array = [life[0]] + [i%life[0] for i in life if i%life[0] !=0]
    life = life_array
    #for i in life_array:
        #if i not in life:
            #life.append(i)
 
print(life[0])


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

int descending_compare(const void *a, const void *b){
    if (*(int*)a > *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}

int ascending_compare(const void *a, const void *b){
    if (*(int*)a < *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}


int lower_bound(int *a, int n, int key){
    int left, mid, right;
    left = 0, right = n;
    mid = (left + right)/2;
    while ((left+1 != mid || mid+1 != right) && mid != left){
        if (key > a[mid]){
            left = mid;
        }else{
            right = mid+1;
        }
        mid = (left + right)/2;
    }
    if (a[left] >= key)return left;
    if (a[mid] >= key)return mid;
    if (a[right] >= key)return right;
    return n;
}

//greatest common divisor
unsigned long  gcd(unsigned long x, unsigned long y){
    if (y == 0){ 
        return x;
    }else if (x > y){
        return gcd(y, x % y);
    }else{
        return gcd(x, y % x);
    }
}



long long factorial(int x){
    long long rtn = 1;
    int i;
    for (i = x; i > 1; i--){
        rtn = (rtn*i);
    }
    return rtn;
}

int main(void){
    int x;
    int here = 0;
    int i;
    scanf("%d", &x);
    for (i = 0; here + (i+1) <  x; i++){
        here += (i+1);
    }
    printf("%d\n", i+1);

}


Measured memory_bytes: 128
#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)
#define sz(x) int(x.size())
using ll = long long;
using P = pair<int,int>;
const ll LLINF = numeric_limits<long long>::max();
const int mod = 1000000007;
const int INF = 1001001001;
 
int main()
{
    int N,M,X;
    cin >> N >>M >>X;
    vector <int> C(N);
    int  A[12][12];
    
    for(int i=0;i<N;i++){
        cin >> C[i];
        for(int j=0;j<M;j++){
             cin >> A[i][j];
             
        }
    }
    int ans = INF;
    
    
    
    rep(div,1<<(N)) {
        
        vector<int> id(M);
        bool flag = true;
        int cos=0; 
        //cout << "sss"<<div << endl;
        rep(i,N) {
        // cout << div;
        
            if (div>>i&1){
                for(int j=0;j<M;j++){
                    //cout << "j " << j  << endl;
                    //cout << "a "<<A[i][j] << endl;
                    id[j] += A[i][j];
                    //cout << "id "<<id[j] << endl;
                    
                }
                cos += C[i];
        
            }
        }
        for(int j=0;j<M;j++){
            //cout << id[j] << " ";  
            if(id[j] < X){
                flag=false;
            }
        }
        //cout << endl;
        if(flag){
            ans = min(ans, cos);
        }
    }   
    if(ans == INF){
        ans =-1;
    }
    cout << ans;
 
 
 
    return 0;
}

Measured memory_bytes: 3628
import java.util.*;
public class Main {
        public static void main(String[] args){
                Scanner sc = new Scanner(System.in);
                int a = sc.nextInt();
                int b = sc.nextInt();
                sc.close();
                b -= (a + 1);
                b = b * (b + 1) / 2;
                System.out.println(b - a);
        }
}

Measured memory_bytes: 35828
#include<bits/stdc++.h>
using namespace std;
int main(){

  int N;
  
  while(1){
    cin >>N;
    if(N == 0)break;
    vector<string> vec;
    for(int i=0 ; i < N ; i++){
      string in;
      cin >>in;
      vec.push_back(in);
    }
    
    bool flag=true;
    for(int i=0 ; i < N ; i++){
      if(vec[i] != "x"){
	bool left=false,right=false;
	int temp1,temp2;
	if(i-1>=0 && vec[i-1] != "x"){
	  stringstream ss;
	  ss << vec[i-1];
	  ss >>temp1;
	  left=true;
	}
	if(i+1 < N && vec[i+1] != "x"){
	  stringstream ss2;
	  ss2 << vec[i+1];
	  ss2 >> temp2;
	  right=true;
	}
	if((i+1)%2 == 0){
	  stringstream ss3;
	  int temp3;
	  ss3 << vec[i];
	  ss3 >> temp3;
	  if(left && temp3 <= temp1){
	    flag=false;
	  }
	  if(right && temp3 <= temp2){
	    flag=false;
	  }
	}else{
	  stringstream ss4;
	  int temp4;
	  ss4 << vec[i];
	  ss4 >> temp4;
	  if(left && temp4 >= temp1){
	    flag=false;
	  }
	  if(right && temp4 >= temp2){
	    flag=false;
	  }
	}
      }
    }
    if(flag){
      int mx=1e9+100,mn=-1e9-100; 
      bool flag2 = true;
      for(int i=0 ; i < N ; i++){
	if(vec[i] == "x"){
	  if((i+1)%2 == 0){
	    if(i-1 >= 0){
	      if(vec[i-1] == "x"){
		flag2=false;
	      }else{
		stringstream ss5;
		int temp5;
		ss5 << vec[i-1];
		ss5 >> temp5;
		mn = max(mn,temp5+1);
	      }
	    }
	    if(i+1 < N){
	      if(vec[i+1] == "x"){
		flag2=false;
	      }else{
		stringstream ss6;
		int temp6;
		ss6 << vec[i+1];
		ss6 >> temp6;
		mn = max(mn,temp6+1);
	      }
	    }
	  }else{
	    if(i-1 >= 0){
	      if(vec[i-1] == "x"){
		flag2=false;
	      }else{
		stringstream ss7;
		int temp7;
		ss7 << vec[i-1];
		ss7 >> temp7;
		mx = min(mx,temp7-1);
	      }
	    }
	    if(i+1 < N){
	      if(vec[i+1] == "x"){
		flag2=false;
	      }else{
		stringstream ss8;
		int temp8;
		ss8 << vec[i+1];
		ss8 >> temp8;
		mx = min(mx,temp8-1);
	      }
	    }
	  }
	}
      }
      if(flag2){
	if(mx == mn){
	  cout <<mx<<endl;
	}else if(mx > mn){
	  cout <<"ambiguous"<<endl;
	}else{
	  cout <<"none"<<endl;
	}
      }else{
	cout <<"none"<<endl;
      }
    }else{
      cout <<"none"<<endl;
    }
  }
  
  return 0;
}

Measured memory_bytes: 1304
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define ll long long int
#define pb push_back
#define mp make_pair
#define ld long double
#define sz(a) (ll)(a).size()
#define endl "\n"

typedef tree<pair<ll,ll> ,null_type,less<pair<ll,ll> >,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//K-th smallest
//cout << k << "kth smallest: " << *A.find_by_order(k-1) << endl;
//NO OF ELEMENTS < X
//cout << "No of elements less than " << X << " are " << A.order_of_key(X) << endl;

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

 	ll n, curr = 5, ans = 0;
 	cin >> n;
 	if(n % 2 == 1)
 	{
 		cout << 0 << endl;
 		return 0;
 	}   
 	for(ll i=1;;i++)
 	{
 		ll x = n / curr;
 		if(x == 0)
 		{
 			cout << ans << endl;
 			return 0;
 		}
 		ans += (x / 2);
 		curr *= 5;
 	}
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a)  (a).begin(),(a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
typedef pair<long long, long long> Pll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef vector<long long> vll;
typedef vector<vector<long long>> vvll;
template <typename T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template <typename T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL << 60;
const int INT_INF = 1 << 30;
#define MOD 1000000007LL
#define endl "\n"

bool func(vll v, ll num){
  ll n = v.size();
  ll sum = 0;
  for(int i = 0; i < n; i++){
    if(sum >= num) sum -= v.at(i);
    else sum += v.at(i);
  }
  ll sum2 = 0;
  for(int i = 0; i < n; i++){
    if(i == 0) sum2 -= v.at(i);
    else if(sum2 >= num) sum2 -= v.at(i);
    else sum2 += v.at(i);
  }
  return (sum == num) || (sum2 == num);
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  string s;
  cin >> s;
  ll N = s.size();
  ll x, y;
  cin >> x >> y;
  int count = 0;
  if(s.at(0) == 'F'){
    int i = 0;
    while(i < N && s[i] == 'F'){
      count++;
      i++;
    }
    x -= count;
  }
  vll xbox(0), ybox(0);
  ll tcount = 0, fcount = 0;
  for(int i = count; i < N; i++){
    if(s.at(i) == 'F'){
      while(i < N && s[i] == 'F'){
        fcount++;
        i++;
      }
      i--;
      if(tcount % 2 == 0) xbox.push_back(fcount);
      else ybox.push_back(fcount);
      fcount = 0;
    }
    else tcount++;
  }
  sort(ALL(xbox), greater<ll>()); sort(ALL(ybox), greater<ll>());
  if(func(xbox, x) && func(ybox, y)) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 384
#include<stdio.h>
int main()
{
  int a,b,c,d,i=0;
  scanf("%d%d%d%d",&a,&b,&c,&d);
  do{
    if(i%2==0){
      c=c-b;
    }
    else{
      a=a-d;
    }
    i++;
  }while(a>0&&c>0);
  if(a<=0)
    printf("No");
  if(c<=0)
    printf("Yes");
  return 0;
}



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

using namespace std;

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

  map<int, int> mp;
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    mp[a]++;
  }

  int ans = 0;
  for (auto i : mp) {
    ans += i.second % 2;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4864
def primeFactorization(n):
    num = n
    tmp = 3
    result = []
    
    while num % 2 == 0:
        result.append(2)
        num //= 2
    
    while tmp * tmp <= num:
        while num % tmp == 0:
            result.append(tmp)
            num //= tmp
        tmp += 2
    
    if tmp != 1:
        result.append(num)
    
    return result

if __name__ == "__main__":
    ab = input().split(" ")
    a = primeFactorization(int(ab[0]))
    b = primeFactorization(int(ab[1]))
    
    result = 1
    ptr_a = 0
    ptr_b = 0
    while ptr_a < len(a) and ptr_b < len(b):
        if a[ptr_a] == b[ptr_b]:
            result *= a[ptr_a]
            ptr_a += 1
            ptr_b += 1
        elif a[ptr_a] < b[ptr_b]:
            result *= a[ptr_a]
            ptr_a += 1
        else:
            result *= b[ptr_b]
            ptr_b += 1

    while ptr_a < len(a):
        result *= a[ptr_a]
        ptr_a += 1
    while ptr_b < len(b):
        result *= b[ptr_b]
        ptr_b += 1

    print(result)


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

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = std::int64_t;
using P = std::tuple<int,int>;

int N;
int A, B;
ll sum, mn = std::numeric_limits<ll>::max();

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

    std::cin >> N;

    for(int i=0;i<N;++i){
        std::cin >> A >> B;

        sum += A;

        if(B < A){
            mn = std::min<ll>(mn, B);
        }
    }

    mn = std::min(mn, sum);

    ll res = sum - mn;
    std::cout << res << std::endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
int main(){
	string s; int K;
    cin>>s>>K;
	vector<string> S;
	for(int i=0; i<s.size(); i++){
		string c;
		for(int j=0; j<5 && i + j < s.size(); j++){
			c += s[i+j];
			S.push_back(c);
		}
	}
	sort(S.begin(), S.end());
	S.erase(unique(S.begin(),S.end()),S.end());
    cout << S[K-1]<<endl;
	return 0;
}

Measured memory_bytes: 1660
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
static ull tenq = 1000000000;
static ull mod = tenq + 7;

using namespace std;

int main()
{
  ll N, K;
  cin >> N >> K;
  vector<ll> xs(N);
  vector<ll> ls, rs;
  ll num_l = N;
  for (auto i = 0; i < N; i++) {
    cin >> xs[i];
    if (num_l == N && xs[i] >= 0) {
      num_l = i;
    }
    if (xs[i] < 0) xs[i] *= -1;
  }
  ll lidx = max(0LL, num_l - K + 1);
  ll res = tenq * 1000;
  // l
  if (num_l >= K) {
    res = xs[lidx-1];
  }
  // r
  if (num_l + K - 1 < N) {
    res = min(res, xs[num_l + K - 1]);
  }
  for (auto i = 0; lidx + i + K - 1 < N && lidx + i < num_l; i++) {
    res = min(res, xs[lidx + i] * 2 + xs[lidx + i + K-1]);
    res = min(res, xs[lidx + i] + xs[lidx + i + K-1] * 2);
  }

  cout << res << endl;

  return 0;
}


Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) c.begin(),c.end()
static const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
static const int MOD = (int)(1e9 + 7);

class Dice {
private:
	//string d = "UFRLBD";
	string d = "RENSWL";
	map<char, string> mp;
public:
	vector<int> v; //UFRLBD:123456
	Dice(vector<int> v) :v(v) {
		mp[d[0]] = "2354";
		mp[d[1]] = "1463";
		mp[d[2]] = "1265";
		mp[d[3]] = "1562";
		mp[d[4]] = "1364";
		mp[d[5]] = "2453";
	};
	void roll(char c) {
		roll(mp[c]);
	}
	void roll(string s) {
		int tmp = v[s[0] - '1'];
		rep(i, 1, s.size())v[s[i - 1] - '1'] = v[s[i] - '1'];
		v[s[s.size() - 1] - '1'] = tmp;
	}
};

signed main() {

	for (int n; cin >> n&&n;) {
		vector<int> v(6); rep(i, 0, 6) { v[i] = i + 1; }
		Dice D(v);
		int ans = v[0];
		rep(i, 0, n) {
			string s; cin >> s;
			D.roll(s[0]);
			ans += D.v[0];
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 3000
n,m=map(int,input().split())
ks=[tuple(map(int,input().split())) for i in range(m)]
p=tuple(map(int,input().split()))

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

    #このパターンで電球が点灯するか調べる
    for k in range(m):
        set_s=set(ks[k][1:])
        on_num=len(set_s&set(on_swich))
        if on_num%2!=p[k]:break
    else:
        ans+=1
print(ans)

Measured memory_bytes: 3064
def solution(A):
	print('AC x ', A.count('AC'))
	print('WA x ', A.count('WA'))
	print('TLE x ', A.count('TLE'))
	print('RE x ', A.count('RE'))

if __name__ == "__main__":
	t = int(input())
	A = []
	for _ in range(t):
		A.append(input())
	solution(A)

Measured memory_bytes: 16300
#include <iostream>
#include <cstdio>
#include <vector>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <algorithm>
#include <utility>
#include <cstring>
#include <cmath>
using namespace std;


int main() {
    int y,m,d;
    scanf("%d/%d/%d",&y,&m,&d);
    if(y>2019){cout<<"TBD"<<endl;return 0;}
    if(y<2019){cout<<"Heisei"<<endl;return 0;}
    if(m>4){cout<<"TBD"<<endl;return 0;}
    cout<<"Heisei"<<endl;
    return 0;
}


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

int i;

int main()
{
    int k, n; //一周、軒数
    cin >> k >> n;
    int a[n];
    for (i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    int l[n];

    for (i = 0; i < n - 1; i++)
    {
        l[i] = a[i + 1] - a[i];
    }
    l[n - 1] = k + a[0] - a[n - 1];

    int max = 0;
    int start;
    int dist = 0;

    for (i = 0; i < n; i++)
    {
        if (max < l[i])
        {
            max = l[i];
            start = i;
        }
    }

    for (i = 0; i < n; i++)
    {
        if (i == start)
        {
            continue;
        }

        dist += l[i];
    }

    cout << dist << endl;
}

Measured memory_bytes: 1792
#include<stdio.h>
#include <iostream>
#include <math.h>
#include <numeric>
#include <vector>
#include <map>
#include <functional>
#include <stdio.h>
#include <array>
#include <algorithm>
#include <string>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <queue>
#include<iomanip>
#include<bitset>
#include<stack>
#include<set>
#include<limits>
#include <complex>
#include<cstdlib>
using namespace std;



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

vector<vector<int>>field;

int ob(const int num,const int way) {
	if (num == 0) {
		return way;
	}
	else if (num == 1) {
		return (way + 3) % 4;
	}
	else if (num == 2) {
		return (way + 2) % 4;
	}
	else if (num == 3) {
		return (way + 1) % 4;
	}
	else if (num == 4) {
		return -1;
	}
	else {
		assert(false);
	}
}

int memo[32][32][4];

int c[4];

struct aa {
	int ny;
	int nx;
	int co;
	int way;
};
class Compare {
public:
	//keiroが昇順に並ぶ
	bool operator()(const aa&l, const aa&r) {
		return l.co> r.co;
	}
};

int main() {
	while (1) {
		memset(memo, 999999, sizeof(memo));
		int w, h; cin >> w >> h;
		if (!w)break;
		field.clear();
		field.resize(h + 2);
		for (int i = 0; i < w + 2; ++i) {
			field[0].push_back(5);
		}
		for (int i = 0; i < h; ++i) {
			field[i + 1].push_back(5);
			for (int j = 0; j < w; ++j) {
				int s; cin >> s;
				field[i + 1].push_back(s);
			}
			field[i + 1].push_back(5);
		}
		for (int i = 0; i < w + 2; ++i) {
			field[h+1].push_back(5);
		}
		cin >> c[0] >> c[1] >> c[2] >> c[3];
		int sx, sy, gx, gy;
		sx = 1;
		sy = 1;
		gx = w;
		gy = h;
		priority_queue<aa, vector<aa>, Compare>que;
		que.push(aa{ sy,sx,0,2 });
		memo[sy][sx][2] = 0;
		while (!que.empty()) {
			aa atop(que.top());
			que.pop();
			for (int j = 0; j < 4; ++j) {
				const int acost = field[atop.ny][atop.nx] == j ? 0 : c[j];
				const int ncost = acost + atop.co;
				const int nway = ob(j, atop.way);
				const int newx = atop.nx + dx[nway];
				const int newy = atop.ny + dy[nway];
				if (field[newy][newx] != 5) {
					if (memo[newy][newx][nway]>ncost) {
						memo[newy][newx][nway] = ncost;
						que.push(aa{ newy,newx,ncost,nway });
					}
				}
			}
			
		}
		int ans = 889999999;
		for (int i = 0; i < 4; ++i) {
			ans = min(ans, memo[gy][gx][i]);
		}
		cout << ans << endl;
	}
	return 0;

}

Measured memory_bytes: 3112
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
   std::ios_base::sync_with_stdio(false);
   ll a, b, c,d;
   cin>>a>>b>>c>>d;
   
    if(b<=0 && d<=0 )
   cout<<a*c<<endl;
   else if(b<=0 && d>0 && c<=0)
   cout<<a*c<<endl;
   else if(b<=0 && c>0)
   cout<<b*c<<endl;
   else if(a<=0 && b>0 && d<=0)
   cout<<(a*c)<<endl;
   else if(a<=0 && b>0 && c<=0 && d>0)
   cout<<max(b*d, a*c)<<endl;
   else if(a<=0 && b>0 && c>0)
   cout<<(b*d)<<endl;
   else  if(a>0 && c>0)
   cout<<(b*d)<<endl;
   else if(a>0 && c<=0 && d>0)
   cout<<(d*b)<<endl;
   else if(a>0 && d<=0)
   cout<<(d*a)<<endl;
   
}

Measured memory_bytes: 3648
def in_range(x, y)
  x.between?(0, H-1) && y.between?(0, W-1)
end

def dfs(x, y)
  d = Array.new(H).map { Array.new(W, INF) }
  d[x][y] = 0
  que = [[x, y]]
  until que.empty?
    q = que.shift
    MOVE.each do |m|
      nx = q[0] + m[0]
      ny = q[1] + m[1]
      if in_range(nx, ny) && C[nx][ny] != '#' && d[nx][ny] == INF
        d[nx][ny] = d[q[0]][q[1]] + 1
        que << [nx, ny]
      end
    end
  end
  u = d.flatten.uniq
  u.delete(INF) if u.include?(INF)
  u.max
end

ans = 0
INF = 10**9
MOVE = [[0, -1], [1, 0], [0, 1], [-1, 0]]
H, W = gets.chomp.split.map(&:to_i)
C = []
H.times { C << gets.chomp }
H.times do |i|
  W.times do |j|
    next if C[i][j] == '#'

    u = dfs(i, j)
    ans = [ans, u].max
  end
end
puts ans

Measured memory_bytes: 14352
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

char s[3010];
int szS;
char t[3010];

int szT;

int f[3010][3010];
int r[3010][3010];

int doSearch(int pS, int pT)
{
	if (f[pS][pT] != -1)
		return f[pS][pT];
		
	if (s[pS] == t[pT])
	{
		f[pS][pT] = doSearch(pS - 1, pT - 1) + 1;
		r[pS][pT] = 0;
	}

	else
	{
		int lenA = doSearch(pS - 1, pT);
		int lenB = doSearch(pS, pT - 1);
		
		if (lenA > lenB)
		{
			f[pS][pT] = lenA;
			r[pS][pT] = -1;	//S
		}
		else
		{
			f[pS][pT] = lenB;
			r[pS][pT] = 1;	//T
		}

	}
	
	return f[pS][pT];
}

int main()
{
	for (int i = 0 ; i < 3010 ; i++)
		for (int j = 0 ; j < 3010 ; j++)
		{
			f[i][j] = -1;
			r[i][j] = -1;
		}
	
	scanf("%s\n", s);
	scanf("%s", t);
	
	szS = strlen(s);
	for (int i = szS ; i >= 1 ; i--)
	{
		s[i] = s[i - 1];
		f[i][0] = 0;
	}		
		
	szT = strlen(t);
	for (int i = szT ; i >= 1 ; i--)
	{
		t[i] = t[i - 1];		
		f[0][i] = 0;
	}
	
	f[0][0] = 0;

		
	int count = doSearch(szS, szT);
	
	std::vector<char> strR;
	int pS = szS;
	int pT = szT;
	
	while (count > 0)
	{
		if (r[pS][pT] == 0)
		{
			strR.push_back(s[pS]);			
			pS--;
			pT--;
			count--;
		}
		else if (r[pS][pT] == -1)
		{
			pS--;
		}
		else if (r[pS][pT] == 1)
		{
			pT--;
		}
	}
	
	for (int i = strR.size() - 1 ; i >= 0 ; i--)
		printf("%c", strR[i]);
	printf("\n");
	
	return 0;
}

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

using namespace std;
#define fordebug int hoge;cin>>hoge;
#define DEKAI 1000000007
#define INF (1<<28)
#define lp(i,n) for(int i=0;i<n;i++)
#define lps(i,j,n) for(int i=j;i<n;i++)
#define floot10 cout<<fixed<<setprecision(10);
#define int long long

double p[5000],q[5000],sump[5000],sumq[5000];
double memo[5000][5000];

signed main(){
	floot10;
	int n;
	cin>>n;
	lp(i,n) cin>>p[i+1];
	lp(i,n+1) cin>>q[i];
	sumq[0]=q[0];
	lp(i,n){
		sump[i+1]=sump[i]+p[i+1];
		sumq[i+1]=sumq[i]+q[i+1];
	}
	lps(i,1,n+1){
		lps(j,1,n+1){
			if(j>=i)memo[i][j]=INF;
			else memo[i][j]=0;
		}
	}
	lps(l,1,n+1){
		lps(i,1,n+2-l){
			int j=i+l-1;
			lps(k,i,j+1){
				double sum=sump[j]-sump[i-1];
				if(i==1) sum+=sumq[j];
				else{
					sum+=sumq[j]-sumq[i-2];
				}
				memo[i][j]=min(memo[i][j],sum-p[k]+memo[i][k-1]+memo[k+1][j]);
			}
		}
	}
	cout<<memo[1][n]+sump[n]+sumq[n]<<endl;
	return 0;
}


Measured memory_bytes: 7180
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
using namespace std;
int main()
{
  int N;
  cin >> N;
  string W[N];
  for(int i=0; i<N; ++i){
    cin >> W[i];
  }

  bool rule = true;
  for(int i=0; i<N-1; ++i){
    if(*(W[i].end()-1) != *W[i+1].begin()){
      rule = false;
    }
    for(int j=0; j<i+1; ++j){
      if(W[i+1] == W[j]){
        rule = false;
      }
    }
  }

  if(rule){
    cout << "Yes" << endl;
  }else{
    cout << "No" << endl;
  }


  return 0;
}


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

int main() {
    int N;
    cin >> N;
    long long int ans =0;

    for(int i=0; i<N; i++){
        int c;
        cin >> c;
        ans += c-1;
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.PrintWriter
import java.util.*
import java.math.*
import java.lang.*

val pw = PrintWriter(System.out)
val MOD: Long = (1e+9 + 7).toLong()

fun main(args: Array<String>) {
    val (a, b, c) = readListOfInt()
    val minDelicious = listOf(b, c).min()!!
    var num = when {
        minDelicious  >= c -> b + c // 美味しい解毒クッキーが毒クッキーより多い時
        a+minDelicious >= c -> b + c
        a + minDelicious + 1 == c -> b + c 
        else -> minDelicious + listOf(a+b+1, c).min()!!
    } 

    println(num)

    pw.flush()
}

/****** Decrared Functions and Data Structures ******/
// IO
fun read() = readLine()!!
fun readInt() = read().toInt()
fun readLong() = read().toLong()
fun readDouble() = read().toDouble()
fun readListOfString() = read().split(" ")
fun readListOfInt() = readListOfString().map { it.toInt() }
fun readListOfLong() = readListOfString().map { it.toLong() }
fun readListOfDouble() = readListOfString().map { it.toDouble() }

fun Double.format(digits: Int) = String.format("%.${digits}f", this)
fun Float.format(digits: Int) = String.format("%.${digits}f", this)

fun print(value: Any) { pw.print(value) }
fun println(value : Any) { pw.println(value) }

fun<T> permutations(src: List<T>): List<List<T>> {
    if(src.size == 1) return listOf(src)
    val perms = mutableListOf<List<T>>()
    val insertElement = src[0]
    permutations(src.drop(1)).forEach { perm ->
        for(i in 0..perm.size) {
            val newPerm = perm.toMutableList()
            newPerm.add(i, insertElement)
            perms.add(newPerm.toList())
        }
    }
    return perms
}

// return nCr, if you want nCr, please access v[n][r]
fun combinations(n: Long): List<List<Long>> {
    val v = (0..n).map { (0..n).map{0L}.toMutableList() }.toMutableList()
    for(i in 0 until v.size) {
        v[i][0] = 1L
        v[i][i] = 1L
    }
    for(i in 0 until v.size) {
        for(j in 1 until i) {
            v[i][j] = (v[i-1][j-1] + v[i-1][j] % MOD)
        }
    }
    val rtn = v.map { it.toList() }.toList()
    return rtn 
}

fun gcd(a: Long, b: Long): Long = 
if(b != 0L) a else gcd(b, a % b)

fun lcm(a: Long, b: Long) = 
if(b==0L) a else gcd(b, a % b)

fun sumDigits(num_: Long): Long {
    var num = num_
    var rtn: Long = 0
    while(num != 0.toLong()) {
        val tmp = num % 10
        rtn += tmp
        num /= 10
    }
    return rtn
}

fun isDecimal(v: Double): Boolean = ((v - Math.floor(v)) != 0.0)

// Data Structures
class Stack<T>(private var st: MutableList<T> = mutableListOf<T>()) {
    fun isEmpty() = st.isEmpty()
    fun top(): T = st.last()
    fun push(e: T) { st.add(e) }
    fun pop() { st = st.dropLast(1).toMutableList() }
}

class Queue<T>(private var que: MutableList<T> = mutableListOf<T>()) {
    fun isEmpty() = que.isEmpty()
    fun top(): T = que.first()
    fun push(e: T) { que.add(e) }
    fun pop() { que = que.drop(1).toMutableList() }
}


Measured memory_bytes: 37956
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
typedef pair<lint, lint> P;

signed main(){
	lint N, W; cin >> N >> W;
	vector<P> vec(N);
	for(int i = 0; i < N; i++) cin >> vec[i].first >> vec[i].second;
	sort(vec.begin(), vec.end());
	vector<lint> weight(N), value(N);
	for(int i = 0; i < N; i++) weight[i] = vec[i].first, value[i] = vec[i].second;
	vector<vector<lint> > dp(N + 10, vector<lint> (W + 10, 0));
	for(int i = 0; i < N - 1; i++){
		for(int w = 0; w < W; w++){
			if (w >= weight[i]) {
        if (dp[i + 1][w] < dp[i][w - weight[i]] + value[i]) {
          dp[i + 1][w] = dp[i][w - weight[i]] + value[i];
        }
      }
      if (dp[i + 1][w] < dp[i][w]) {
        dp[i + 1][w] = dp[i][w];
      }
    }
	}
	lint ans = 0;
    for(lint i = N - 1;i >= 0;--i){
        ans = max(ans, dp[i][W - 1] + value[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 71296
/// You just can't beat the person who never gives up
/// ICPC next year

///#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
///#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include<bits/stdc++.h>
using namespace std ;
const int N = 1e6+5 ,mod = 1e9+7 ;

int n ,k ,to[N] ;
vector<pair<int,int>> val_cnt ;
void init(){
    int i = 1 ;
    while(i<=n){
        int st = i ,en = n ;
        while(st<en){
            int mid = (st+en+1)/2 ;
            if(n/mid == n/i) st = mid ;
            else en = mid-1 ;
        }
        val_cnt.push_back({st,st-i+1});
        i = st+1 ;
    }
    sort(val_cnt.begin(),val_cnt.end());
    for(i=0;i<val_cnt.size();++i){
        int st = 0 ,en = val_cnt.size()-1 ;
        while(st<en){
            int mid = (st+en+1)/2 ;
            if(1ll * val_cnt[i].first * val_cnt[mid].first <= n) st = mid ;
            else en = mid-1 ;
        }
        to[i] = st ;
    }
}
int dp[2][N] ;
int solve2(){
    for(int i=k-1;i>=0;--i) for(int cur=0;cur<val_cnt.size();++cur){
        if(cur) dp[i&1][cur] = dp[i&1][cur-1] ;
        else dp[i&1][cur] = 0 ;
        if(i+1==k) dp[i&1][cur] = (0ll + dp[i&1][cur] + val_cnt[cur].second)%mod ;
        else dp[i&1][cur] = (0ll + dp[i&1][cur] + 1ll * val_cnt[cur].second * dp[i&1^1][to[cur]]%mod)%mod ;
    }
    return dp[0][val_cnt.size()-1] ;
}
bool Never_give_up(){
    cin >> n >> k ;
    init() ;
    cout << solve2() ;
    return 0;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("input.txt" ,"r" ,stdin);
    freopen("output.txt" ,"w" ,stdout);
#endif
    std::ios::sync_with_stdio(0);
    cin.tie(0) ,cout.tie(0);
    int t = 1 ;
    //cin >> t ;
    while(t--){
        Never_give_up();
    }
    return 0;
}

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


int main()
{
  	int n;
	cin >> n;
	int p[n];
	for (int i=0;i<n;i++){
		cin >> p[i];
	}
	int count;
	count = 0;
	for (int i=0;i<n-2;i++){
		if (p[i] < p[i+1] && p[i+1] < p[i+2]){
			count ++;
		}
		if (p[i] > p[i+1] && p[i+1] > p[i+2]){
			count ++;
		}


	}
  	cout << count << endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ff first
#define ss second
#define pii pair <int,int>
#define pll pair <ll,ll>
#define testcase() int t; cin>>t; while(t--)
#define forn(i,n) for(int i=0;i<n;i++)
#define forn1(i,n) for(int i=1;i<=n;i++)
#define vll vector <ll>
#define vi vector <int>
#define all(v) v.begin(),v.end()

ll M = 1e9 + 7;
double pi = acos(-1.0);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll powerm(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x)%M; y=y>>1; x=(x*x)%M;} return res%M; }
ll power(ll x,ll y){ ll res=1; while(y){ if(y&1) res=(res*x); y=y>>1; x=(x*x);} return res; }
ll gcd(ll a,ll b){if(b>a)return gcd(b,a); if(b==0)return a; return gcd(b,a%b);}

int main() {
	
	//ifstream cin("input.txt");
	//ofstream cout("output.txt");
	ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
	
	int n; ll k;
    cin>>n>>k;
    vll a(n);
    forn(i,n) cin>>a[i];
    if(k==0)
    {
        ll mx = 0;
        forn(i,n) mx = max(mx,a[i]);
        cout<<mx; return 0;
    }
    ll L = 0, R = *max_element(all(a)) + 2000;
    while(R-L>1)
    {
        ll mid = (L+R)/2;
        ll c = 0;
        forn(i,n)
        {
            ll g = (a[i]+mid-1)/mid - 1;
            c += g;
        }
        //cout<<mid<<' '<<c<<endl;
        if(c>k) L = mid;
        else R = mid;
    }
    cout<<R;

	return 0;
}


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

int sum[5];
int sum2[5];
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int a, b;
    while(cin >> a >> b && (a || b)){
        sum[0] = a + b;
        sum2[0] = sum[0];
        for(int i = 1; i < 5; ++i){
            int s1, s2;
            cin >> s1 >> s2;
            sum[i] = s1 + s2;
            sum2[i] = sum[i];
        }

        sort(sum, sum + 5);

        for(int i = 0; i < 5; ++i){
            if(sum2[i] == sum[4]){
                cout << char('A' + i) << " " << sum[4] << endl;
            }
        }
    }

    return 0;
}

Measured memory_bytes: 1204
#include "bits/stdc++.h"
using namespace std;

//#define int int64_t

#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,x,...) x
#define REP1(i, s, cond, cal) for (signed i = signed(s); i cond; i cal)
#define REP2(i, s, n) REP1(i, s, < signed(n), ++)
#define REP3(i, n) REP2(i, 0, n)
#define rep(...) CHOOSE((__VA_ARGS__,REP1,REP2,REP3))(__VA_ARGS__)

#define all(c) begin(c), end(c)
#define maxup(ans, x) (ans = (ans < x ? x : ans))
#define minup(ans, x) (ans = (ans > x ? x : ans))

#define breakif(cond) if(cond) break; else

template<typename T>
inline void input(vector<T>& v) { for (auto& x : v) cin >> x; }

//using VV = vector<vector<int>>;
//using V = vector<int>;
//using P = pair<int, int>;
//using IP = pair<int, P>;

typedef complex<double> P;
typedef vector<P> L;
namespace std {
	bool operator < (const P& a, const P& b) {
		return real(a) != real(b) ? real(a) < real(b) : imag(a) < imag(b);
	}
}
bool operator == (const L& a, const L& b) {
	if (a.size() != b.size()) return false;
	rep(i, a.size()) if (a[i] != b[i]) return false;
	return true;
}
P rs[] = { P(1, 0), P(0, 1), P(-1, 0), P(0, -1) };
L rotate(L line, int idx) {
	L ret = line;
	for (auto& x : ret) {
		x *= rs[idx];
	}
	return ret;
};
L move(L line) {
	P sub = *min_element(all(line));
	L ret = line;
	for (auto& x : ret) {
		x -= sub;
	}
	return ret;
};
L input() {
	int m; cin >> m;
	L l(m);
	rep(i, m) {
		int x, y; cin >> x >> y;
		l[i] = P(y, x);
	}
	return l;
};
bool equal(L l1, L l2) {
	L l22 = l2;
	reverse(all(l22));
	rep(i, 4) {
		if (move(l1) == move(rotate(l2, i)) || move(l1) == move(rotate(l22, i))) return true;
	}
	return false;
};

signed main() {
	int n;
	while (cin >> n && n) {
		vector<L> lines(n - 1);
		L line;

		line = input();
		stringstream ss;
		rep(i, n) {
			if (equal(line, input())) {
				ss << i + 1 << endl;
			}
		}
		ss << "+++++" << endl;
		cout << ss.str();
	}
}

Measured memory_bytes: 3168
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <numeric>
#include <utility>
#include <iomanip>

using namespace std;
using int64 = long long;

struct aaa{aaa(){cin.tie(nullptr); ios::sync_with_stdio(false); cout<<fixed<<setprecision(20);};}aaa;

int main() {
    int n;
    cin >> n;
    // vector<int> a(n);
    int64 ans = 0;
    int pre = 0;
    for (int i=0; i<n; i++) {
        // cin >> a[i];
        int a;
        cin >> a;
        if (a < pre)
            ans += pre - a;
        pre = max(pre, a);
    }
    cout << ans << endl;
}


Measured memory_bytes: 3192
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

int solve(int h, int a)
{
  int i = 0;
  for (; h > 0; ++i) {
    h -= a;
  }
  return i;
}

int main()
{
  int h, a;
  std::cin >> h >> a;

  std::cout << solve(h, a) << std::endl;
}


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

int main() {
    long long A = 100;
    long long X;
    cin >> X;

    for (int i=1; i<3761; i++) {
        A = A * 1.01;
        if (A >= X) {
            printf("%d",i);
            return 0;
        }
    }
}

Measured memory_bytes: 3768