akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <functional>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
#define rep1(i,n) for(int i=1;i<=(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;
typedef pair<int,int> P;
int h,w,qx,qy,ax,ay;
string s[30];
short int dp[30][30][30][30][2];	//1->Qwin,-1->Awin.0->?
//qx,qy,ax,ay,turn=0->queen
int dx[5]={0,1,0,-1,0},dy[5]={0,0,1,0,-1};
vector<P> exits;
bool is(int x,int y){
	if(x<0||h<=x||y<0||w<=y||s[x][y]=='#') return false;
	return true;
}
void init(){
	exits.clear();
	rep(i,h) rep(j,w) rep(k,h) rep(l,w) rep(turn,2) dp[i][j][k][l][turn]=0;
}
void showdp(int i,int j,int k,int l,int turn,int value){
	printf("dp[%d][%d][%d][%d][%d]=%d\n",i,j,k,l,turn,value);
}
int main(){
	while(true){
		cin>>w>>h;
		if(w==0) break;
		init();
		rep(i,h) cin>>s[i];
		rep(i,h) rep(j,w){
			if(s[i][j]=='Q') qx=i,qy=j;
			if(s[i][j]=='A') ax=i,ay=j;
			if(s[i][j]=='E') exits.pb(P(i,j));
		}
		bool update=true;
		for(P ex : exits){
			int x=ex.fs,y=ex.sc;
			rep(i,h) rep(j,w) dp[x][y][i][j][0]=1;
		}
		rep(i,h) rep(j,w) rep(turn,2) dp[i][j][i][j][turn]=-1;
		while(update){
			update=false;
			//turn=0
			rep(i,h) rep(j,w) rep(k,h) rep(l,w){
				if(dp[i][j][k][l][0]!=0) continue;
				bool allcant=true,canwin=false;
				rep(di,5){
					int nx=i+dx[di],ny=j+dy[di];
					if(!is(nx,ny)) continue;
					if(dp[nx][ny][k][l][1]==1) canwin=true;
					if(dp[nx][ny][k][l][1]!=-1) allcant=false;
				}
				if(canwin){
					dp[i][j][k][l][0]=1;
//					showdp(i,j,k,l,0,1);
					update=true;
					continue;
				}
				if(allcant){
					dp[i][j][k][l][0]=-1;
//					showdp(i,j,k,l,0,-1);
					update=true;
					continue;
				}
			}
			//turn=1
			rep(i,h) rep(j,w) rep(k,h) rep(l,w){
				if(dp[i][j][k][l][1]!=0) continue;
				bool allcant=true,canwin=false;
				rep(di,5){
					int nx=k+dx[di],ny=l+dy[di];
					if(!is(nx,ny)) continue;
					if(dp[i][j][nx][ny][0]==-1) canwin=true;
					if(dp[i][j][nx][ny][0]!=1) allcant=false;
				}
				if(canwin){
					dp[i][j][k][l][1]=-1;
//					showdp(i,j,k,l,1,-1);
					update=true;
					continue;
				}
				if(allcant){
					dp[i][j][k][l][1]=1;
//					showdp(i,j,k,l,1,1);
					update=true;
					continue;
				}
			}
		}
//		rep(i,h) rep(j,w) rep(k,h) rep(l,w) rep(turn,2) showdp(i,j,k,l,turn,dp[i][j][k][l][turn]);
		switch(dp[qx][qy][ax][ay][0]){
			case -1:
				puts("Army can catch Queen.");
				break;
			case 0:
				puts("Queen can not escape and Army can not catch Queen.");
				break;
			case 1:
				puts("Queen can escape.");
				break;
		}
	}
}

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

int main(void){
	int a,b,c,minn;
	cin>>a>>b>>c;
	minn=a+b;
	if(minn>a+c)
		minn=a+c;
	if(minn>b+c)
		minn=b+c;
	cout<<minn<<endl;
}

Measured memory_bytes: 256
import sys
from copy import deepcopy

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    def meguru_bisect(ok, ng):
        while abs(ok - ng) > 1:
            mid = (ok + ng) // 2
            if is_ok(mid):
                ok = mid
            else:
                ng = mid
        return ok

    def is_ok(x):
        B = deepcopy(A)
        total = m * v
        target = B[x] + m
        for i in range(n):
            if i <= x:
                B[i] += m
                total -= m
            else:
                if n - (p - 1) <= i:
                    B[i] += m
                    total -= m
                else:
                    if B[i] > target:
                        return False
                    else:
                        total -= target - B[i]
                        B[i] = target
        return total <= 0

    n, m, v, p = map(int, input().split())
    A = sorted(list(map(int, input().split())))
    ng, ok = n, -1
    res = meguru_bisect(ng, ok)
    print(n - res)


if __name__ == '__main__':
    resolve()


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

int main(){
  int N;
  cin>>N;
  bool frag=true;
  for(int i=0;i<N;++i){
    int A;
    cin>>A;
    if(A%2==0){
      if(A%3!=0 && A%5!=0) frag=false;
    }
  }

  if(frag) cout<<"APPROVED"<<endl;
  else cout<<"DENIED"<<endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<int,int> Pi;
#define rep(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define fi first
#define se second
#define endl "\n"

template<typename T> inline bool chmax(T &a, T b){if(a<b){a=b;return true;}return false;}
template<typename T> inline bool chmin(T &a, T b){if(a>b){a=b;return true;}return false;}
template<typename T> ostream& operator<<(ostream& s,const complex<T>& d) {return s<<"("<<d.real()<<", "<<d.imag()<< ")";}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const pair<T1,T2>& d) {return s<<"("<<d.first<<", "<<d.second<<")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& d){int len=d.size();rep(i,len){s<<d[i];if(i<len-1) s<<" ";}return s;}
template<typename T> ostream& operator<<(ostream& s,const vector<vector<T>>& d){int len=d.size();rep(i,len){s<<d[i]<<endl;}return s;}
template<typename T> ostream& operator<<(ostream& s,const set<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T> ostream& operator<<(ostream& s,const multiset<T>& v){s<<"{ ";for(auto itr=v.begin();itr!=v.end();++itr) {if (itr!=v.begin()) {s<< ", ";}s<<(*itr);}s<<" }";return s;}
template<typename T1, typename T2> ostream& operator<<(ostream& s,const map<T1,T2>& m){s<<"{"<<endl;for(auto itr=m.begin();itr!=m.end();++itr){s<<" "<<(*itr).first<<" : "<<(*itr).second<<endl;}s<<"}"<<endl;return s;}

const ll mod=1e9+7;
const ll inf=1e17;
const int INF=1e9;
const double EPS=1e-10;
const double PI=acos(-1);

int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll len=0;//答えの長さ
    ll now=0;
    ll cnt;
    while(now<n){
        len++;
        cnt=1;
        rep(_,len) cnt*=26;
        now+=cnt;
    }
    ll diff=n-(now-cnt)-1;
    string ans;
    cnt/=26;
    rep(i,len){
        ll x=diff/cnt;
        ans+=(char)'a'+x;
        diff-=cnt*x;
        cnt/=26;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3624
s = int(input())
flag = [0] * 1000000
flag[s] = 1
a = s
i = 1

while True:
    i += 1
    if a % 2 == 0:
        a //= 2
    else:
        a = 3*a + 1
    
    if flag[a] == 1:
        break
    else:
        flag[a] = 1

print (i)

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

int main() {
	
	int n;
	cin>>n;
	int k=0;
	//n=min(n,(180-n));
	for(int i=1;i<=360;i++)
	{
	    if((i*n)%360==0)
	    {
	        k=i;
	        break;
	    }
	}
	cout<<k;
	return 0;
}


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

void check_num(int i){
	int x = i;
	if(x % 3 == 0 || x % 10 == 3){
		cout << ' ' << i;
	}
	else{
		do{
			x /= 10;
			if(x && x % 10 == 3){
				cout << ' ' << i;
				break;
			}
		}while(x);
	}
}
int main(){
	int n, i = 1;
	cin >> n;
	for(i = 1; i <= n; i++){
		check_num(i);
	}
	cout << endl;
}

Measured memory_bytes: 1164
import java.awt.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        // write your code here
        Scanner sc = new Scanner(System.in);

        int h = sc.nextInt();
        int w = sc.nextInt();

        String[][] meiro = new String[h][];
        int white = 0;
        for (int i = 0; i < h; i++) {
            meiro[i] = sc.next().split("");
            for (String v: meiro[i]
                 ) {
                if (v.equals(".")) {
                    white++;
                }
            }
        }
        Queue<Point> queue = new ArrayDeque<>();
        queue.add(new Point(0, 0));

        // 上下左右（分岐先）の座標を配列に入れておくと、forループで回して処理できるので便利
        int[] dx = {0, 1, 0, -1};
        int[] dy = {-1, 0, 1, 0};

        int[][] searched = new int[h][w];
        int ans = - 1;
        while (!queue.isEmpty()) {
            Point p = queue.poll();
            if (p.x == w - 1 && p.y == h - 1) {
                ans = searched[p.y][p.x];
                break;
            }
            for (int k = 0; k < 4; k++) {
                int x = p.x + dx[k];
                int y = p.y + dy[k];
                // 分岐先の座標が、2つのif文の条件を満たすなら先頭に追加
                if (x >= 0 && x < w && y >= 0 && y < h) {
                    if (meiro[y][x].equals(".") && searched[y][x] == 0) {
                        searched[y][x] = searched[p.y][p.x] + 1;
                        queue.add(new Point(x, y));
                    }
                }
            }
        }

        if (ans != - 1) {
            ans = white - (ans + 1);
        }

        System.out.println(ans);
    }
}

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

int main()
{
    int a,b;
    cin>>a>>b;
    if((a==1 || a==2) && (b==1 || b==2))
        cout<<3<<endl;
    else if((a==2 || a==3) && (b==2 || b==3))
        cout<<1<<endl;
    else
        cout<<2<<endl;
    return 0;
}


Measured memory_bytes: 3556
#include <bits/stdc++.h>
#define MAX_V 100000
#define INF 1e9
using namespace std;

//????????¨????§???????(???????????????????????????????????????)
struct edge{int to, cap,cost,rev;};
int V;                         //????????°
vector<edge> G[MAX_V];         //??°???????????£??\???????????¨???
int dist[MAX_V];               //???????????¢
int prevv[MAX_V],preve[MAX_V]; //??´??????????????¨???

// from??????to??????????????????cap????????????cost???????????°????????????????????????
void add_edge(int from,int to,int cap,int cost){
  G[from].push_back((edge){to,cap,cost,G[to].size()});
  G[to].push_back((edge){from,0,-cost,G[from].size()-1});
}

//s??????t????????????f???????°??????¨???????±???????
//??????????????´???-1?????????
int min_cost_flow(int s,int t,int f){
  int res=0;
  while(f>0){
    //????????????????????????????????????,s-t????????????????±???????
    fill(dist,dist+V,INF);
    dist[s]=0;
    bool update = true;
    while(update){
      update = false;
      for(int v=0; v<V ;v++){
	if(dist[v]==INF) continue;
	for(int i=0; i<G[v].size(); i++){
	  edge &e = G[v][i];
	  if(e.cap > 0 && dist[e.to] > dist[v]+e.cost) {
	    dist[e.to] = dist[v] + e.cost;
	    prevv[e.to] = v;
	    preve[e.to] = i;
	    update = true;
	  }
	}
      }
    }
    if(dist[t]==INF) return -1; //????????\??????????????????
    
    //s???t?????????????????£??????????????????
    int d = f;
    for(int v=t; v!=s; v=prevv[v])d=min(d,G[prevv[v]][preve[v]].cap);
    f -= d;
    res += d*dist[t];
    for(int v=t; v!=s; v=prevv[v]){
      edge &e = G[prevv[v]][preve[v]];
      e.cap -= d;
      G[v][e.rev].cap += d;
    }
  }
  return res;
}

int main(){
  int E,F;
  cin>>V>>E>>F;
  for(int i=0;i<E;i++){
    int u,v,c,d;
    cin>>u>>v>>c>>d;
    add_edge(u,v,c,d);
  }
  cout <<min_cost_flow(0,V-1,F)<<endl;
}

Measured memory_bytes: 5588
///***Bismillahir Rahmanir Rahim***///

///*********************************///
///******Ashraful Haque Toni********///
///********Dept. of CSE,JnU*********///
///email:ashrafulhaquetoni@gmail.com///
///*******contact:01640690531*******///
///*********************************///


#include<bits/stdc++.h>

using namespace std;

#define         ash ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define         pb push_back
#define         mp make_pair
#define         sc(n) scanf("%d",&n);
#define         scl(n) scanf("%I64d",&n);
#define         sc2(m,n) scanf("%d%d",&m,&n);
#define         sc2l(m,n) scanf("%I64d%I64d",&m,&n);
#define         pf printf
#define         Big(x,y) max(x,y);
#define         Small(x,y) min(x,y);
#define         input(array,size) for(int i=0;i<size;i++)cin>>array[i];
#define         newline pf("\n");
#define         f(s,l,in) for(ll i=s;i<l;i+=in)
#define         Max INT_MAX
#define         Min INT_MIN
#define         pi acos(-1.0)
#define         Memset(a,val) memset(a,val,sizeof(a));

const int mod =1e9+7;
const int N =5e6+5;
typedef long long ll;



int main()
{

    ash;

    ll a,b,c,d,cnt=0;
    cin>>a>>b>>c>>d;

    ll lcm=(c*d)/__gcd(c,d);

    ll cnt1=b/c,cnt2=b/d,cnt3=b/(lcm);
    cnt=cnt1+cnt2-cnt3;

    ll cn1=(a-1)/c,cn2=(a-1)/d,cn3=(a-1)/(lcm);

    ll cn=cn1+cn2-cn3;

    ll f=cnt-cn;

    ll re=((b-a)+1)-f;

    //if(a%2==0&&b%2==0)re++;

    cout<<re<<endl;


    //cout<<cnt<<endl;
    return 0;
}




Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < int(n); i++)
using namespace std;
using ll = long long;
const int INF = (1<<30)-1;
const long long LINF = (1LL<<62)-1;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n;
  string s;
  cin >> n >> s;
  int ans = 0;
  rep(i, 1000) {
    vector<int> num(3);
    int tmp = i;
    for (int j = 2; j >= 0; j--) {
      num[j] = tmp%10;
      tmp /= 10;
    }
    int idx = 0;
    rep(j, n) {
      if (num[idx] == s[j]-'0')
        idx++;
      if (idx == 3) {
        ans++;
        break;
      }
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3700
import java.util.*;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		for (int i=0; i<N; i++){
			if (sc.next().contains("Y")){
				System.out.println("Four");
				System.exit(0);
			}
		}
		System.out.println("Three");
	}

}


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

int main() {
	int N, T, t[200000], ans = 0;
	cin >> N >> T;
	for (int i = 0; i < N; ++i) cin >> t[i];
	for (int i = 1; i < N; ++i) {
		if (t[i] - t[i - 1] > T) ans += T;
		else ans += t[i] - t[i - 1];
	}
	cout << ans + T;
}

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


#define li          long long int
#define rep(i,to)   for(li i=0;i<((li)(to));i++)
#define repp(i,start,to)    for(li i=(li)(start);i<((li)(to));i++)
#define pb          push_back
#define sz(v)       ((li)(v).size())
#define bgn(v)      ((v).begin())
#define eend(v)     ((v).end())
#define allof(v)    (v).begin(), (v).end()
#define dodp(v,n)       memset(v,(li)n,sizeof(v))
#define bit(n)      (1ll<<(li)(n))
#define mp(a,b)     make_pair(a,b)
#define rin rep(i,n)
#define EPS 1e-12
#define ETOL 1e-8
#define MOD 1000000007
typedef pair<li, li> PI;

#define INF bit(60)

#define DBGP 1


#define idp if(DBGP)
#define F first
#define S second
#define p2(a,b)     idp cout<<a<<"\t"<<b<<endl
#define p3(a,b,c)       idp cout<<a<<"\t"<<b<<"\t"<<c<<endl
#define p4(a,b,c,d)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<endl
#define p5(a,b,c,d,e)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<endl
#define p6(a,b,c,d,e,f)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<endl
#define p7(a,b,c,d,e,f,g)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<endl
#define p8(a,b,c,d,e,f,g,h)     idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<endl
#define p9(a,b,c,d,e,f,g,h,i)       idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<endl
#define p10(a,b,c,d,e,f,g,h,i,j)        idp cout<<a<<"\t"<<b<<"\t"<<c<<"\t"<<d<<"\t"<<e<<"\t"<<f<<"\t"<<g<<"\t"<<h<<"\t"<<i<<"\t"<<j<<endl
#define foreach(it,v)   for(__typeof((v).begin()) it=(v).begin(); it!=(v).end(); ++it)
#define p2p(x)      idp p2((x).F, (x).S)
#define dump(x,n)   idp{rep(i,n){cout<<x[i]<<" ";}puts("");}
#define dump2(x,n)  idp{rep(i,n){cout<<"["<<x[i].F<<" , "<<x[i].S<<"] ";}puts("");}
#define dumpi(x)    idp{foreach(it, x){cout<<(*it)<<" ";}puts("");}
#define dumpi2(x)   idp{foreach(it, x){cout<<"["<<(it)->F<<" , "<<(it)->S<<"] ";}puts("");}

#define read2d(a,w,h)   rep(i,h)rep(j,w)cin>>a[i][j]
#define dump2d(a,w,h)   rep(i,h){rep(j,w)cout<<a[i][j]<<" ";puts("");}

typedef pair<li, li> PI;

li a[100100];
li x[100100] = {0};

int main() {
    li n;
    cin >> n;
    rin{
        cin >> a[i];
        if (a[i] % 2 != (n + 1) % 2) {
            puts("0");
            return 0;
        }
        x[a[i]]++;
    }
    li res = 1;
    for (li i = (n + 1) % 2; i < n; i += 2) {
        if (x[i] != 2) {
            if (i == 0 && x[i] == 1)continue;
            puts("0");
            return 0;
        }
        res *= 2;
        res %= MOD;
    }
    cout << res << endl;

    return 0;
}

Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,x;
    int num=0;
    scanf("%d %d %d %d", &a,&b,&c,&x);
    for(int i=0;i<=a;i++){
        for(int j=0;j<=b;j++){
            for(int q=0;q<=c;q++){
                int sum=0;
                sum+=(500*i)+(100*j)+(50*q);
                if (sum==x){
                    num+=1;
                }
            }
        }
    }
    printf("%d", num);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <fstream>
#define inputtxt() std::ifstream in("input.txt"); std::cin.rdbuf(in.rdbuf())
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define foreach(e, v) for (auto e : v)
#define all(obj) (obj).begin(), (obj).end()
#define rall(obj) (obj).rbegin(), (obj).rend()
#define collect(arr, size) rep(i,size) cin >> arr[i];

inline int calc_loss(int n){
    return (10 - (n % 10)) % 10;
}

using intpair = pair<int,int>;
int main(){
    vector<int> dishes(5);
    priority_queue<intpair,vector<intpair>, greater<intpair>> q;
    rep(i,5){
        int temp; cin >> temp;
        q.push(intpair(calc_loss(temp),temp));
    }
    int res = 0;
    rep(i, 4){
        res += q.top().first + q.top().second;
        q.pop();
    }
    res += q.top().second;
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
//#include <atcoder/all>
//using namespace atcoder;
using namespace std;
#define all(v) v.begin(), v.end()
using in = int64_t;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define Yes cout<<"Yes"<<endl
#define No cout<<"No"<<endl
#define yes cout<<"yes"<<endl
#define no cout<<"no"<<endl
#define YES cout<<"YES"<<endl
#define NO cout<<"NO"<<endl
const double PI=3.14159265358979323846;
const in MOD = 1000000007;
const in INF=1e18+7;
const int inf=1e9+7;
using P=pair<int,int>;
vector<int> dx={0,1,-1,0};
vector<int> dy={1,0,0,-1};


int main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cout << fixed << setprecision(10);
    int n,k;
    cin>>n>>k;
    vector<int> a(n);
        rep(i,n) cin>>a.at(i);
        rep(i,n) a[i] %=k;
    vector<int> sum(n,0);
    sum[0]=a[0];
    rep(i,n-1) sum[i+1]=(a[i+1]+sum[i])%k;
    rep(i,n){
        sum[i]=(i+1)-sum[i]+k;
        sum[i] %= k;
    }
    map<int,in> x;
    rep(i,min(n,k-1)) x[sum[i]] ++;
    int key=0;
    in ans=0;
    rep(i,n){
        ans += x[key];
        key ++;
        key -= a[i];
        key += k;
        key %= k;
        x[sum[i]] --;
        if(i+k<=n) x[sum[i+k-1]] ++;
    }
    cout<<ans<<endl;
}/*
./problem.exe
*/

Measured memory_bytes: 17200
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define PB(a) push_back(a)
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)))
#define repp(i,a,b) for(int i = (int)(a) ; i < (int)(b) ; ++i)
#define repm(i,a,b) for(int i = (int)(a) ; i > (int)(b) ; --i)

const int MC = 100010;
int N;
vector<int> V[MC];
int p[MC];
int d[MC];
queue<int> Q;
int c;

int halt(){
	printf("First\n");
	return 0;
}

int main(){
	scanf("%d" , &N);
	repp(i,1,N){
		int a,b;
		scanf("%d%d" , &a , &b);
		V[a].PB(b);
		V[b].PB(a);
	}
	repp(i,1,N+1){
		p[i] = -1;
		d[i] = (int)V[i].size();
		if(d[i] == 1) Q.push(i);
	}
	while(!Q.empty()){
		int x = Q.front(); Q.pop();
		p[x] = 0;
		++c;
		for(auto u : V[x]){
			if(p[u] < 0){
				--d[u];
				if(d[u] == 1) Q.push(u);
			} else if(p[u] == 0){
				++p[x];
			}
		}
		if(p[x] > 1) return halt();
		if(c == N && p[x] != 1) return halt();
	}
	printf("Second\n");
	return 0;
}


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

using namespace std;

using ll = long long;
using P = pair<int, vector<ll> >;

constexpr char newl = '\n';

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

    int t;
    cin >> t;

    for (int loop = 0; loop < t; loop++) {
        int n;
        cin >> n;

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

        string s;
        cin >> s;

        if (s.back() == 1) {
            cout << 1 << newl;
            continue;
        }

        vector<P> v;
        v.push_back(P(0, {}));
        for (int i = n - 1; i >= 0; i--) {
            if (v.back().first == (s[i] - '0')) {
                v.back().second.push_back(a[i]);
            } else {
                int nex = 1 - v.back().first;
                v.push_back(P(nex, {a[i]}));
            }
        }

        for (auto& p : v) {
            sort(p.second.begin(), p.second.end());
        }

        int sz = v.size();
        vector<ll> buf;
        bool f = true;
        for (int i = 0; i < sz; ++i) {
            if (v[i].first == 0) {
                for (ll x : v[i].second) buf.push_back(x);
            } else {
                auto memo = buf;
                int sz2 = memo.size();
                int rank = 0;
                for (int j = 59; j >= 0; j--) {
                    int pivot = -1;
                    for (int k = rank; k < sz2; k++) {
                        if (memo[k] >> j & 1) {
                            pivot = k;
                            break;
                        }
                    }

                    if (pivot == -1) continue;
                    swap(memo[pivot], memo[rank]);
                    
                    for (int k = 0; k < sz2; k++) {
                        if (k != rank && (memo[k] >> j & 1)) memo[k] ^= memo[rank];
                    }

                    for (ll& x : v[i].second) {
                        if (x >> j & 1) x ^= memo[rank];
                    }
                    ++rank;
                }

                for (ll x : v[i].second) {
                    if (x != 0) {
                        f = false;
                        break;
                    }
                }

                if (!f) break;
            }
        }

        cout << !f << newl;
    }

    return 0;
}

Measured memory_bytes: 3560
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc=new Scanner(System.in);
    String str=sc.next();
    if(str.equals("Sunny")){
      System.out.println("Cloudy");
    }
    if(str.equals("Cloudy")){
      System.out.println("Rainy");
    }
    if(str.equals("Rainy")){
      System.out.println("Sunny");
    }
  }
}

Measured memory_bytes: 23252
#include<iostream>
#include<string>
#include<iomanip>
#include<cmath>
#include<vector>
#include<algorithm>
#include<utility>

using namespace std;

#define int long long
#define endl "\n"

constexpr long long INF = (long long)1e18;
constexpr long long MOD = 1'000'000'007; 

struct fast_io {
	fast_io(){
		std::cin.tie(nullptr);
		std::ios::sync_with_stdio(false);
	};
} fio;

int solve(int N, int K){
	int x = 0;
	vector<vector<int>> dp;
	vector<int> num;
	num.push_back(0);
	
	for(int i = 1; i * i <= N; i++){
		num.push_back(i);
		num.push_back(N/i);
	}
	
	sort(num.begin(), num.end());
	num.erase(unique(num.begin(), num.end()), num.end());
	
	dp.resize(num.size(), vector<int>(K+1));
	
	for(int j = 1; j < num.size(); j++){
		dp[j][0] = 1;
	}
	
	for(int i = 0; i < K; i++){
		
		for(int j = 0; j + 1 < num.size(); j++){
			int k = (int)num.size() - j - 1;
			dp[j+1][i+1] += dp[k][i] * (num[j+1] - num[j]) % MOD;
			dp[j+1][i+1] %= MOD;
			
			
			dp[j+1][i+1] += dp[j][i+1];
			dp[j+1][i+1] %= MOD;
		}
	}
	
	return dp[num.size()-1][K];
}

signed main(){
	cout<<fixed<<setprecision(10);
	
	int N, K;
	
	cin>>N>>K;
	
	cout<<solve(N, K)<<endl;
	
	
	return 0;
}

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

int main(){
    int k, a, b;
    cin >> k >> a >> b;
    bool check = 0;
    rep(i, a, b+1){
        if (i % k == 0) check = 1; 
    }
    if (check == 1) cout << "OK" << endl;
    else cout << "NG" << endl;
    return 0;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(void){
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a < b){
		if(b < c){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}else{
		printf("No\n");
	}
	return 0;
}


Measured memory_bytes: 2076
#include<stdio.h>

int main(void){
	int i,s,t,n,ans[10],c;
	
	while(scanf("%d",&n)!=EOF){
		s=512;
		c=0;
		while(1){
			if(n>=s){
				n-=s;
				ans[c]=s;
				c++;
			}
			if(n==0)break;
			s/=2;
		}
		
		for(i=c-1;i>=0;i--){
			printf("%d",ans[i]);
			if(i>0)printf(" ");
			else printf("\n");
		}
		
	}
	return 0;
}

Measured memory_bytes: 0
#include <stdio.h>
#include <iostream>
#include <vector>
#include <cassert>
#include <algorithm>
#include <cstdlib>
#include <string>
#include <math.h>
#include <map>
#include <set>
#include <queue>
#include <bitset>
using namespace std;

long long int n, k;
long long int a[100001];
long long int res = 0;

//ユークリッドの互除法
long long int gcd(long long int a, long long int b)
{
    if (a < b)
    {
        gcd(b, a);
    }
    long long int r;
    while ((r = a % b))
    {
        a = b;
        b = r;
    }
    return b;
}

int main()
{

    cin >> n;

    cin >> res;

    for (int i = 1; i < n; i++)
    {
        long long int a;
        cin >> a;
        res = gcd(a, res);
    }

    cout << res;
    return 0;
}

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

using ll = long long;

///////////////////////////////////////////////////////////////////////////////
template<typename T>
struct BIT {
  int n;
  vector<T> d;
  int curr;
  BIT(int n=0):n(n),d(n+1) {
    curr = 1;
    while (curr < d.size()) curr <<= 1;
  }

  // i 番目の値に x を足す O(log D)
  void add(int i, T x=1) {
    for (i++; i <= n; i += i&-i) {
      d[i] += x;
    }
  }

  // ０番目からi番目までの和を求める O(log D)
  T sum(int i) {
    T x = 0;
    for (i++; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }

  // [l, r) の和を求める
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }

  // BIT上の二分探索 bit.sum(v) >= w となる最小の v を求める O(log D)
  int lower_bound(T w) {
    int i = 0;
    for(int k = curr; k > 0; k >>= 1) {
      if(i + k < d.size() && d[i + k] < w) {
        w -= d[i + k];
        i += k;
      }
    }
    return i;
  }
};
///////////////////////////////////////////////////////////////////////////////

// Range Sum Query https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_B
void aoj_dsl_2_b() {
  int n, q;
  cin >> n >> q;
  BIT<ll> bit(n);

  rep(i, q) {
    int t, x, y; cin >> t >> x >> y;
    if (t == 0) {       // a[x-1] に y を加算する
      bit.add(x-1, y);
    } else {            // a[x-1] ... a[y-1] の和を求める
      cout << bit.sum(x-1, y) << endl;;
    }
  }
}


// https://judge.yosupo.jp/problem/static_range_sum
void static_range_sum() {
  int n, q; cin >> n >> q;
  BIT<ll> bit(n);
  rep(i, n) {
    int a; cin >> a;
    bit.add(i, a);
  }

  rep(i, q) {
    int l, r; cin >> l >> r;
    ll ans = bit.sum(r-1);
    if (l > 0) ans -= bit.sum(l-1);
    cout << ans << endl;
  }
}

// https://judge.yosupo.jp/problem/point_add_range_sum
void point_add_range_sum() {
  int n, q;
  cin >> n >> q;
  BIT<ll> bit(n);
  rep(i, n) {
    int a;
    cin >> a;
    bit.add(i, a);
  }

  rep(i, q) {
    int t; cin >> t;
    if (t == 0) {
      int p, x; cin >> p >> x;
      bit.add(p, x);
    } else {
      int l, r;
      cin >> l >> r;
      cout << bit.sum(l, r) << endl;
    }
  }
}

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

  aoj_dsl_2_b();
  // static_range_sum();
  // point_add_range_sum();

  return 0;
}



Measured memory_bytes: 3580
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
#include <cmath>

#define INF_LL 9000000000000000000
#define INF 2000000000

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

using namespace std;

typedef long long ll;
typedef pair<int, int> PII;

class Union_find{
private:
	vector<int> par;
	vector<int> rank;
	int n;

public:
	Union_find(int a){
		n = a;
		for(int i = 0;i < n;i++){
			par.push_back(i);
			rank.push_back(0);
		}
	}

	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;

		if(rank[x] < rank[y]){
			par[x] = y;
		}else{
			par[y] = x;
			if(rank[x] == rank[y]) rank[x]++;
		}
	}

	bool same(int x, int y){
		return find(x) == find(y);
	}
};

int main(void){
	int a, b;
	cin >> a >> b;
	if(a < 0 && b < 0){
		if((b - a + 1) % 2 == 0){
			cout << "Positive" << endl;
			return 0;
		}else{
			cout << "Negative" << endl;
			return 0;
		}
	}else if(a <= 0 && 0 <= b){
		cout << "Zero" << endl;
		return 0;
	}else{
		cout << "Positive" << endl;
		return 0;
	}
}


Measured memory_bytes: 256
# try AfterContestCase
from collections import deque
from math import ceil
import sys
input = sys.stdin.readline

def main():
    N,D,A = map(int,input().split())
    XH = sorted([[int(i) for i in input().split()] for _ in range(N)],key=lambda x: x[0])

    ans = 0
    index = deque()
    damage = 0
    for i in range(N):
        # 爆弾が届かない場合
        while index:
            if index[0][0] + 2*D < XH[i][0]:
                _,c = index.popleft()
                damage -= A * c
            else:
                break
        
        # 爆弾投下
        XH[i][1] -= damage

        # 生き残り
        if XH[i][1] > 0:
            count = ceil(XH[i][1]/A)
            damage += count * A
            index.append([XH[i][0],count])
            ans += count

    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 123100
import java.util.Scanner;

public class Main {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int A = sc.nextInt();
		int B = sc.nextInt();

		if(A < B) {
			System.out.println("a < b");
		}
		else if(A > B) {
			System.out.println("a > b");
		}
		else if(A == B) {
			System.out.println("a == b");
		}
	}
}

Measured memory_bytes: 26224
import java.io.{BufferedOutputStream, BufferedReader, InputStreamReader, PrintWriter}

object Main {
  def main(args: Array[String]): Unit = {
    val in = new BufferedReader(new InputStreamReader(System.in))
    val out = new PrintWriter(new BufferedOutputStream(System.out))
    val Array(n, m, x, y) = in.readLine().split("\\s+").map(_.toInt)
    val xs = in.readLine().split("\\s+").map(_.toInt)
    val ys = in.readLine().split("\\s+").map(_.toInt)

    val xsMax = (xs ++ Array(x)).max
    val ysMin = (ys ++ Array(y)).min

    out.println(
      if (xsMax >= ysMin) {
        "War"
      } else {
        "No War"
      }
    )

    out.flush()
  }
}


Measured memory_bytes: 25540
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <sstream>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <numeric>
#include <cctype>
#include <tuple>
#include <array>
#include <cassert>

// BEGIN CUT HERE
#ifdef _MSC_VER
#include <agents.h>
#endif
// END CUT HERE 

#define FOR(i, a, b) for(int i = (a); i < (int)(b); ++i)
#define rep(i, n) FOR(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define REV(v) v.rbegin(), v.rend()
#define UNIQUE(v) v.erase(unique(ALL(v)), v.end())
#define MEMSET(v, s) memset(v, s, sizeof(v))
#define MP make_pair
#define MT make_tuple

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef unsigned long long ull;

int vis[400][7][7][7][7][3][3];
int ng[400][3][3];

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

int dx2[] = { 0, 1, 0, 1 };
int dy2[] = { 0, 0, 1, 1 };

int n;
void dfs(int d, int lt, int rt, int lb, int rb, int x, int y){
	if (lt > 6 || rt > 6 || lb > 6 || rb > 6) return;
	if (d == n){
		//cout << lt << ' ' << rt << ' ' << lb << ' ' << rb << endl;
		throw 1;
		return;
	}
	if (ng[d][x][y] || vis[d][lt][rt][lb][rb][x][y]) return;
	vis[d][lt][rt][lb][rb][x][y] = 1;
	++lt, ++rt, ++lb, ++rb;
	int pos = y * 3 + x;
	if (pos == 0) lt = 0;
	if (pos == 2) rt = 0;
	if (pos == 6) lb = 0;
	if (pos == 8) rb = 0;

	FOR(k, 1, 3) rep(dir, 4){
		int nx = x + dx[dir] * k;
		int ny = y + dy[dir] * k;
		if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
		dfs(d + 1, lt, rt, lb, rb, nx, ny);
	}
	dfs(d + 1, lt, rt, lb, rb, x, y);
}

int main(){
	while (cin >> n, n){
		MEMSET(vis, 0);
		MEMSET(ng, 0);

		rep(d, n) rep(y, 4) rep(x, 4){
			int a;
			cin >> a;
			if (!a) continue;
			int xx = x - 1, yy = y - 1;
			rep(dir, 4){
				int nx = xx + dx2[dir], ny = yy + dy2[dir];
				if (nx < 0 || nx >= 3 || ny < 0 || ny >= 3) continue;
				ng[d][nx][ny] = 1;
			}
		}

		try{
			 dfs(0, 0, 0, 0, 0, 1, 1);
			 cout << 0 << endl;
		}
		catch(int x){
			cout << 1 << endl;
		}
	}


	return 0;
}

Measured memory_bytes: 35092
n, m, x = map(int, input().split())

CA = [list(map(int, input().split())) for _ in range(n)]

ans = 10 ** 21
for b in range(2 ** n):
  A = [0] * m
  c = 0
  for i in range(n):
    if (1 & (b >> i)):
      c += CA[i][0]
      for itr, a in enumerate(CA[i][1:]):
        A[itr] += a
  if all(a >= x for a in A):
    ans = min(ans, c)

if ans == 10 ** 21:
  ans = -1
  
print(ans)

Measured memory_bytes: 9244
n = int(input())
s = str(input())
count = 0
if n % 3 == 1 or n % 3 == 0:
  for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
      count += 1
elif n % 3 == 2:
  for i in range(n-2):
    if s[i] == 'A' and s[i+1] == 'B' and s[i+2] == 'C':
      count += 1
print(count)


Measured memory_bytes: 9188
#include <bits/stdc++.h>
#include <cmath>
#include <iostream>
using namespace std;
typedef long long ll;
#define INF 1LL<<62
#define inf 1000000007

int main() {
	ll n;	
	cin>>n;ll k=n%10;
	if(n%10==3){
		cout << "bon";
	}

	else if(k==0||k==1||k==6||k==8){
		cout << "pon";
	}
	else{
		cout <<"hon";
	}
	// your code goes here
	return 0;
}

Measured memory_bytes: 3524
def roll(die,dir)
  case dir.chomp
  when "north"; die[:top],die[:south],die[:bottom],die[:north] = die[:south],die[:bottom],die[:north],die[:top]
  when "south"; die[:top],die[:south],die[:bottom],die[:north] = die[:north],die[:top]   ,die[:south],die[:bottom]
  when "east";  die[:top],die[:west], die[:bottom],die[:east]  = die[:west], die[:bottom],die[:east] ,die[:top]
  when "west";  die[:top],die[:west], die[:bottom],die[:east]  = die[:east], die[:top]   ,die[:west] ,die[:bottom]
  end
  return die
end


while (n=gets.to_i)>0
  die=[
    [:top,   1],
    [:bottom,6],
    [:north, 2],
    [:south, 5],
    [:east,  4],
    [:west,  3],
  ].to_h

  n.times{
    die = roll(die,gets)
  }

  p die[:top]
end

Measured memory_bytes: 8808
#include<time.h>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
//jks函数:返回0表示x,返回1表示y,返回2表示一样
int jks(char x[200],char y[200])
{
	int lenx,leny,len,i,xi,yi;//len是较短的字符串的长度
	lenx=strlen(x);
	leny=strlen(y);
	if(lenx<leny)
		len=lenx;
	else
		len=leny;
	for(i=0;i<=len-1;i++)
	{
		xi=x[i];
		yi=y[i];
		if(xi>yi)
			return 0;
		if(xi<yi)
			return 1;
	}
	if(lenx>leny)
		return 0;
	if(lenx<leny)
		return 1;
	return 2;
}
int main()
{
	int n,i,scorea=0,scoreb=0,t;
	
	char a[200],b[200];
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		scanf("%s",a);
		scanf("%s",b);
		t=jks(a,b);
		if(t==0)
			scorea+=3;
		if(t==1)
			scoreb+=3;
		if(t==2)
		{
			scorea++;
			scoreb++;
		}
	}
	printf("%d %d\n",scorea,scoreb);
	return 0;
}


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

using namespace std;

#define int long long
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))

typedef pair<int,int> PI;
typedef pair<int,pair<int,int>> PII;
static const int INF=1010000000000000017LL;
static const double eps=1e-12;
static const double pi=3.14159265358979323846;
static const int dx[4]={1,-1,0,0};
static const int dy[4]={0,0,1,-1};
static const int ddx[8]={1,-1,0,0,1,1,-1,-1};
static const int ddy[8]={0,0,1,-1,1,-1,1,-1};

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

map<string,int> mp;
string S[4]={"AC","WA","TLE","RE"};

signed main(){
    int N;
    cin>>N;
    for(int i=0;i<N;++i){
        string s;
        cin>>s;
        mp[s]++;
    }
    for(int i=0;i<4;++i){
        cout<<S[i]<<" x "<<mp[S[i]]<<endl;
    }
}

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

#define ALL(v) (v).begin(), (v).end()
#define rep(i, n) for (ll i = 0, __##i##_length = (n); i < __##i##_length; i++)
#define rep_reverse(i, n) for (ll i = (n)-1; 0 <= i; i--)
#define FOR(i, from, to) for (ll i = (from), __##i##_end = (to); i < __##i##_end; i++)
#define FOR_REVERSE(i, from, to) for (ll i = (to)-1, __##i##_end = (from); __##i##_end <= i; i--)
#define foreach(e, v) for (const auto e : (v))
#define vfree(v) std::vector<int>().swap(v)
#define DEBUG(x) cout << #x << " = " << (x) << endl

using namespace std;
typedef int64_t ll;
typedef vector<ll> llv;
typedef vector<llv> llvv;

int main()
{
    ll N;
    cin >> N;
    llv A(N * 3);
    rep(i, 3 * N)
    {
        cin >> A[i];
    }
    sort(ALL(A));
    ll ans = 0;
    rep(i, N)
    {
        ans += A[N + 2 * i];
    }
    cout << ans << endl;
}


Measured memory_bytes: 2560
#include<bits/stdc++.h>
#include<cstring>
#include<cmath>
#include<iterator>
#include<cstdlib>
#define IOS   ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ses   "\n"
#define whp   " "
#define mxi 99999
#define mp make_pair
#define PII pair<int, int>
#define pf printf
#define sf scanf
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define PI acos(-1)
#define sz(a) long long(a.size())
#define ff first
#define ss second
#define forch(it,s) for(auto it:s)
#define each(it,s) for(auto it = s.begin(); it != s.end(); ++it)
#define rep0(i,a,b) for(int i=a; i<b; i++)
#define rep1(i,a,b) for(int i=a; i<=b; i++)
#define rep0in(i,a,b) for(int i=a-1; i>=b; i--)
#define rep1in(i,a,b) for(int i=a; i>b; i--)
#define repv(i,a) for(auto i=a.begin(); i!=a.end();++i)

///priority_queue <int, vector<int>, greater<int>> g
#define MS(a,b) memset(a,b,sizeof(a));

typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ll fx[4]= {1,-1,0,0};
ll fy[4]= {0,0,1,-1};

typedef vector<ll> vll;
typedef vector<string> vss;
typedef vector<pair<ll,ll > > vpr;
typedef vector<pair<string,ll > > vspr;
typedef list<ll> li;
typedef list<string> ls;
typedef list<pair<ll,ll> > lpr;
typedef list<pair<string,ll> > lspr;

bool rs(ll a, ll b){return(a>b);}
ll spd(ll n){ if(n%2==0)return 2; for(ll i=3; i*i<=n; i++){if(n%i==0)return i;}return n;}

int main(){

ll n; cin>>n;ll a[n];
for(ll i=0; i<n; i++){
    cin>>a[i];
}
ll profit=1000;
ll z=0;
for(ll i=0; i<n; i++){
    if(a[i]==a[z])continue;
    if(a[i]>a[z]){
        ll d=a[i]-a[z];
        ll share=profit/a[z];
        ll r=profit%a[z];
        profit+=((d*share));
        z=i;
    }
    if(a[i]<a[z]){
        z=i;
    }
}
cout<<profit<<endl;
//cout<<1300%115<<endl;


return 0;
}



Measured memory_bytes: 3672
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sort(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=998244353;
const int inf=1<<30;
const ll lnf=1ll<<60;

struct mint{
  ll x;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const{return mint(-x);}
  mint& operator+=(const mint a){
    if((x+=a.x)>=mod) x-=mod;
    return *this;
  }
  mint& operator-=(const mint a){
    if((x+=mod-a.x)>=mod) x-=mod;
    return *this;
  }
  mint& operator*=(const mint a){
    (x*=a.x)%=mod;
    return *this;
  }
  mint operator+(const mint a) const{
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const{
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const{
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const{
    if(!t) return 1;
    mint a=pow(t>>1);
    a*=a;
    if(t&1) a*=*this;
    return a;
  }

  // for prime mod
  mint inv() const{
    return pow(mod-2);
  }
  mint& operator/=(const mint a){
    return (*this)*=a.inv();
  }
  mint operator/(const mint a) const{
    mint res(*this);
    return res/=a;
  }
};

mint dp[3030][3030];

int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  dp[a][b]=1;
  for(int i=a;i<=c;i++)for(int j=b;j<=d;j++){
      if(a<i) dp[i][j]+=dp[i-1][j]*j;
      if(b<j) dp[i][j]+=dp[i][j-1]*i;
      if(a<i&&b<j) dp[i][j]-=dp[i-1][j-1]*(j-1)*(i-1);
  }
  cout << dp[c][d].x << endl;
}

Measured memory_bytes: 75356
def u(a,b):
  if(a<b):
    z = b
    b = a
    a = z
  r = a % b
  while(r!=0):
    a = b
    b = r
    r = a % b
  return b
 
l = int(input())
s = 0
for i in range(1,l+1):
  for i2 in range(1,l+1):
    z = u(i,i2)
    for i3 in range(1,l+1):
      z2 = u(i3,z)
      s+=z2
print (s)

Measured memory_bytes: 9144
//入力候補

#include<iostream>
#include<utility>
#include<string>
#include<vector>
#include<algorithm>
#include<deque>
#include<queue>
#include<set>
#include<map>

using namespace std;
#define LL long long

int main() {
	while(1) {
		int n;
		char k;
		map<string, int> dict;//単語、単語の出現数
		vector<pair<int, string>> talf;//各頭文字の先頭
		string ans;

		cin >> n;
		if (!n) break;
		cin.ignore();
		for (int i = 0; i < n; i++) {
			string s;
			getline(cin, s);


			auto pbegin = s.begin();

			while (pbegin != s.end()) {
				auto pend = pbegin;
				while (pend != s.end() && *pend != ' ')//文字列の終わりか対象の文字までイテレータを動かす
					pend++;
				string word = string(pbegin, pend);
				if (dict.find(word) == dict.end()) dict[word] = 0;
				dict[word]++;
				if (pend != s.end())
					pend++;
				pbegin = pend;
			}
		}
		cin >> k;
		
		auto itr = dict.begin();
		while (itr != dict.end()) {
			string nword = itr->first;
			if (nword[0] == k) //頭文字の一致
				talf.push_back(make_pair(-(itr->second), nword));
			itr++;
		}
		
		if (talf.empty())ans = "NA";
		else {
			sort(talf.begin(), talf.end());
			for (int i = 0; i < talf.size(); i++) {
				if (i > 4)break;
				if(i) ans += " ";
				ans += talf[i].second;
			}
		}
		
		cout << ans << endl;
	}
	return 0;
}



Measured memory_bytes: 3220
#include <stdio.h>

int A[100000000], n;

int binarySearch(int key)
{
    int left = 0;
    int right = n;
    int mid;
    while (left < right)
    {
        mid = (left + right) / 2;
        if (key == A[mid])
            return 1;
        if (key > A[mid])
            left = mid + 1;
        else if (key < A[mid])
            right = mid;
    }
    return 0;
}

int main()
{
    int i, q, k, sum = 0;

    scanf("%d", &n);
    for (i = 0; i < n; i++)
        scanf("%d", &A[i]);

    scanf("%d", &q);
    for (i = 0; i < q; i++)
    {
        scanf("%d", &k);
        if (binarySearch(k))
            sum++;
    }
    printf("%d\n", sum);

    return 0;
}


Measured memory_bytes: 2996
#include <bits/stdc++.h>
#include<vector>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main() {
  int a,b,c,d;
  cin>>a>>b>>c;
  d=c/a;
   cout<<d*b;
}

Measured memory_bytes: 256
n,k = input().split()
n = int(n)
k = int(k)
nums = [float(i)/2+0.5 for i in input().split()]
ma = sum(nums[0:k])
now = ma
for i in range(n-k):
  now = now - nums[i] + nums[i+k]
  if now>ma:
    ma = now
print(ma)

Measured memory_bytes: 23588
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <fstream>
#include <sstream>
using namespace std;

const unsigned long long BASE = 1e9 + 7;

int main()
{
    int n, k;
    cin >> n >> k;
    int * a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (i >= k)
        {
            cout << (a[i] > a[i - k] ? "Yes" : "No") << endl;
        }
    }

    delete[] a;
    return 0;
}


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

int main()
{
    int n;
    int count = 0;
    vector<int> d(100);

    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>d.at(i);
    }
    for(int i=0;i<n;i++)
    {
        for(int j=n-1;j>0;j--)
        {
            if(d.at(j) > d.at(j-1))
            {
                int small = d.at(j-1);
                d.at(j-1) = d.at(j);
                d.at(j) = small;
            }
        }
        if(i == 0)
        {
            count++;
        }else{
            if(d.at(i) == d.at(i-1))
            {
                continue;
            }else{
                count++;
            }
        }
    }
    cout<<count<<endl;
}

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

#define REP(i,num) for(int i=0;i<(num);++i)
#define ALL(c) c.begin(),c.end()
#define PRINTALL(c) for(auto& x:c){cout<<x<<' ';}cout<<endl;
#define PAIRCOMP(c,comp) [](const pair<ll,ll>& lhs,const pair<ll,ll>& rhs){return lhs.c comp rhs.c;}

using namespace std;
using ll = long long;

constexpr ll atcoder_mod = 1e9+7;

template<typename T=int>
T in(){T x; cin >> x; return (x);}
template<typename T=int,typename C=vector<T>>
C vecin(int N){C x(N);REP(i,N){x[i]=in<T>();}return move(x);}

void vout(){cout << endl;}
template<typename Head,typename... Tail>
void vout(Head&& h,Tail&&... t){cout << ' ' << h;vout(forward<Tail>(t)...);}
void out(){cout << endl;}
template<typename Head,typename... Tail>
void out(Head&& h,Tail&&... t){cout << h;vout(forward<Tail>(t)...);}

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

	vector<vector<int>> P(10,vector<int>(10,0));
	vector<vector<pair<int,int>>> F(3);
	F[0] = {make_pair(0,-1),make_pair(-1,0),make_pair(0,0),make_pair(1,0),make_pair(0,1)};
	F[1] = {make_pair(-1,-1),make_pair(0,-1),make_pair(1,-1),make_pair(-1,0),make_pair(0,0),
		    make_pair(1,0),make_pair(-1,1),make_pair(0,1),make_pair(1,1)};
	F[2] = {make_pair(0,-2),make_pair(-1,-1),make_pair(0,-1),make_pair(1,-1),
		    make_pair(-2,0),make_pair(-1,0),make_pair(0,0),make_pair(1,0),make_pair(2,0),
		    make_pair(-1,1),make_pair(0,1),make_pair(1,1),make_pair(0,2)};
	string S;
	while(cin>>S){
		int x,y,s;
		sscanf(S.c_str(),"%d,%d,%d",&x,&y,&s);
		s--;
		for(int i=0,ei=F[s].size();i<ei;i++){
			int nx = x+F[s][i].first,ny = y+F[s][i].second;
			if(0<=nx && nx<10 && 0<=ny && ny<10){
				P[ny][nx]++;
			}
		}
	}
	int num=0,dep=0;
	REP(i,10){
		REP(j,10){
			if(P[i][j]==0) num++;
			dep = max(dep,P[i][j]);
		}
	}
	out(num);
	out(dep);
	return 0;
}


Measured memory_bytes: 3184