akhauriyash/Code-Regression huggingface dataset:
/*input
10 10
*/
/*

**************************
*						 *
* AUTHOR :: knight_coder *
*						 *
**************************

*/
#include<bits/stdc++.h>
#define lld          long long int
#define pb          push_back
#define ppb         pop_back
#define	endl		'\n'
#define mii         map<lld,lld>
#define msi         map<string,lld>
#define mis         map<lld, string>
#define mpi         map<pair<lld ,lld >,lld >
#define pii         pair<lld,lld>
#define vi          vector<lld>
#define vpi 		vector<pii>
#define vs          vector<string>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (lld)x.size()
#define hell        1000000007
#define rrep(i,m,n)	for(lld i=m;i>=n;i--)
#define rep(i,m,n)	for(lld i=m;i<n;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define what_is(x)  cerr << #x << " is " << x << endl;
#define pr(x) 		cout<< x << " ";
#define pre(x)		cout<< x << endl ;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; 
//change null_type to get ordered_map
#define N  100005
#define DEC(N)	cout << std::fixed; cout << setprecision(N);
void solve()
{
	lld x,y;
	cin >> x >> y;
	cout << ((y>=x)?"unsafe":"safe") << endl;
}
signed main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int tests=1;
	//cin>>tests;
	while(tests--)
	{
		solve();
	}
}

Measured memory_bytes: 3644
#include <bits/stdc++.h>
typedef long long lint;
using namespace std;

int n, m;
vector<pair<int, int>> ab;

int main() {
    cin >> n >> m;
    ab.resize(m);
    for (int i = 0; i < m; i++) {
        cin >> ab[i].first >> ab[i].second;
    }
    auto compare = [](pair<int, int> x, pair<int, int> y) { return x.second < y.second; };
    sort(ab.begin(), ab.end(), compare);
    // r~r+1を切った
    int r = -1;
    int ans = 0;
    for (int i = 0; i < m; i++) {
        if (r < ab[i].first) {
            r = ab[i].second - 1;
            ans++;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 1152
#include <iostream>

using namespace std;

int main()
{
    int w, h, x, y, r;
    cin >> w >> h >> x >> y >> r;
    if(x-r>=0 && y-r>=0 && x+r<=w && y+r<=h)
        cout << "Yes" << endl;
    else
        cout << "No" << endl;
}


Measured memory_bytes: 3092
def abc150_c_count_order():
    N = int(input())
    P = list(map(int, input().split()))
    Q = list(map(int, input().split()))

    def solve(items, current):
        if items == []:
            permutations.append(current)
            return
        for item in items:
            next = current + [item]
            new_items = [i for i in items if i != item]
            solve(new_items, next)

    permutations = []
    items = list(range(1, N+1))
    current = []
    solve(items, current)

    a = permutations.index(P)
    b = permutations.index(Q)
    print(abs(a - b))


##########
if __name__ == "__main__":
    abc150_c_count_order()


Measured memory_bytes: 8948
#include <bits/stdc++.h>
#include <unordered_set>
#include <random>
using namespace std;
#define ll long long
#define fr first
#define sc second
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()

vector<int> friendadj[110000];
vector<int> blockadj[110000];

int cnt;
int comp_num = 1;
int compsz[110000];
int ncomp[110000];

void dfs(int nd, int comp_num) {
	ncomp[nd] = comp_num;
	cnt++;
	for (int nxt : friendadj[nd]) {
		if (ncomp[nxt] != 0) continue;
		dfs(nxt, comp_num);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N, M, K; cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		friendadj[a].push_back(b);
		friendadj[b].push_back(a);
	}
	for (int i = 0; i < K; i++) {
		int a, b; cin >> a >> b;
		blockadj[a].push_back(b);
		blockadj[b].push_back(a);
	}

	for (int i = 1; i <= N; i++) {
		if (ncomp[i] == 0) {
			cnt = 0;
			dfs(i, comp_num);
			compsz[comp_num] = cnt;
			comp_num++;
		}
	}

	for (int i = 1; i <= N; i++) {
		int ans = compsz[ncomp[i]] - 1;
		int blocksz = 0;
		set<int> blocks, friends;
		for (int j : friendadj[i]) friends.insert(j);
		for (int j : blockadj[i]) blocks.insert(j);
		for (int j : blocks) if (ncomp[j] == ncomp[i]) blocksz++;
		ans -= friends.size();
		ans -= blocksz;
		cout << ans << ' ';
	}

	return 0;
}

Measured memory_bytes: 19820
# coding: utf-8
n, k = map(int, input().split())
p = list(map(int, input().split()))
res = [0]
ra = res.append
for i in range(n):
    ra(p[i] + res[i])

ans = 0
for i in range(n - k + 1):
    tmp = res[i + k] - res[i]
    if ans < tmp:
        ans = tmp

print((ans + k) / 2)



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

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

	int K;
	scanf("%d", &K);

	int A, B;
	scanf("%d %d", &A, &B);

	for (int i = A; i <= B; i++) {
		if (i % K == 0) {
			printf("OK");
			return 0;
		}
	}
	printf("NG");
	return 0;
}

Measured memory_bytes: 3828
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define p pair<int,int>
#define x first
#define y second
// num, 
p rot(p pt){
	p d;
	d.x = pt.y;
	d.y = -pt.x;
	return d;
}
vector<p> solve(vector<int> d){

	if(d.size() == 4){
		vector<p> ans;
		ans.push_back(p(0, 0));
		ans.push_back(p(1, 0));
		ans.push_back(p(1, 1));
		ans.push_back(p(0, 1));
		return ans;
	}

	vector<int> newd;
	int n = d.size();
	int sh = 0;
	for(int i = 0; i < d.size(); i++){
		if(d[i%n] == 90 && d[(i+1)%n] == 90 && d[(i+2)%n] == 270) sh = i;
	}
	for(int i = 0; i < d.size(); i++){
		newd.push_back(d[(i+sh)%n]);
	}

	//newd is d (question) wrapped around

	vector<int> dsmall;
	for(int i = 0; i < d.size(); i++){
		if(i != 1 && i != 2) dsmall.push_back(newd[i]);
	}

	vector<p> asmall = solve(dsmall); //solution to wrapped around

	/*for(int i = 0; i < dsmall.size(); i++){
		cout << dsmall[i] << " ";
	}
	cout << endl;

	for(int i = 0; i < dsmall.size(); i++){
		cout << asmall[i].x << "," << asmall[i].y << " ";
	}
	cout << endl;*/

	int nrot = 0;
	while((asmall[asmall.size()-1].y != asmall[0].y) || (asmall[asmall.size()-1].x > asmall[0].x)){
		nrot++;
		for(int i = 0; i < asmall.size(); i++){
			asmall[i] = rot(asmall[i]);
		}
	}

	/*cout << nrot << endl;
	for(int i = 0; i < dsmall.size(); i++){
		cout << asmall[i].x << "," << asmall[i].y << " ";
	}
	cout << endl;*/

	// asmall has horizontal right segment
	int sx = asmall[0].x;
	int sy = asmall[0].y;
	for(int i = 0; i < asmall.size(); i++){
		if(asmall[i].x > sx) asmall[i].x+=2;
		if(asmall[i].x < sx) asmall[i].x-=2;
		if(asmall[i].y > sy) asmall[i].y+=2;
		if(asmall[i].y < sy) asmall[i].y-=2;
	}
	vector<p> ans;
	ans.push_back(p(asmall[0].x+1,asmall[0].y));
	ans.push_back(p(asmall[0].x+1,asmall[0].y+1));
	ans.push_back(p(asmall[0].x,asmall[0].y+1));
	for(int i = 1; i < asmall.size(); i++){
		ans.push_back(asmall[i]);
	}
	for(int cc = 0; cc < 4-nrot; cc++){
		for(int i = 0; i < ans.size(); i++){
			ans[i] = rot(ans[i]);
		}
	}

	vector<p> finans;
	for(int i = 0; i < ans.size(); i++){
		finans.push_back(ans[(n-sh+i)%n]);
	}
	/*for(int i = 0; i < d.size(); i++){
		cout << d[i] << " ";
	}
	cout << endl;
	for(int i = 0; i < ans.size(); i++){
		cout << finans[i].x << "," << finans[i].y << " ";
	}
	cout << endl << endl;*/
	return finans;

}
int main(){
	int n;
	cin >> n;
	int a[n];
	int d = 0;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 0; i < n; i++){
		if(a[i] == 90) d++;
		if(a[i] == 270) d--;
	}
	int flip = 0;
	if(d == -4){
		flip = 1;
		d = -d;
	}
	if(d != 4){
		cout << -1 << endl;
		return 0;
	}
	vector<int> pr;
	for(int i = 0; i < n; i++) pr.push_back(a[i]);
	vector<p> ttt = solve(pr);
	for(int i = 0; i < ttt.size(); i++){
		cout << ttt[i].x+10000000 << " " << ttt[i].y+10000000 << endl;
	}
}


Measured memory_bytes: 3968
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
    cin >> s;
    for (int i = 0; i < s.length(); ++i) {
        if (s[i] == '9') {
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 256
// g++ -std=c++11 a.cpp
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<unordered_map>
#include<utility>
#include<cmath>
#include<random>
#include<cstring>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<typeinfo>
#define loop(i,a,b) for(int i=a;i<b;i++) 
#define rep(i,a) loop(i,0,a)
#define FOR(i,a) for(auto i:a)
#define pb push_back
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)
using namespace std;
//kaewasuretyuui
typedef long long ll;
//#define int ll
typedef int Def;
typedef pair<Def,Def> pii;
typedef vector<Def> vi;
typedef vector<vi> vvi;
typedef vector<pii> vp;
typedef vector<vp> vvp;
typedef vector<string> vs;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef pair<Def,pii> pip;
typedef vector<pip>vip;
#define mt make_tuple
typedef tuple<int,int,int> tp;
typedef vector<tp> vt;
template<typename A,typename B>bool cmin(A &a,const B &b){return a>b?(a=b,true):false;}
template<typename A,typename B>bool cmax(A &a,const B &b){return a<b?(a=b,true):false;}
//template<class C>constexpr int size(const C &c){return (int)c.size();}
//template<class T,size_t N> constexpr int size(const T (&xs)[N])noexcept{return (int)N;}
const double PI=acos(-1);
const double EPS=1e-9;
Def inf = sizeof(Def) == sizeof(long long) ? 2e18 : 1e9+10;
int dx[]={0,1,0,-1};
int dy[]={1,0,-1,0};
struct edge{int to,cap,rev;};//ikisaki youryou gyakuhen
class MF{//max flow
	public:
	int n;
	vector<vector<edge> >G;//[MAX];
	vi level,iter;//[MAX];
	MF(int size){
		n=size;
		G=vector<vector<edge> >(n);
	}
	void add_edge(int from, int to, int cap){
		edge q={to,cap,int(G[to].size())};
		G[from].push_back(q);
		q={from,0,int(G[from].size()-1)};
		G[to].push_back(q);
	}
	void bfs(int s){
		level=vi(n,-1);
		queue<int>q;
		level[s]=0;
		q.push(s);
		while(!q.empty()){
			int v=q.front();q.pop();
			for(int i=0;i<G[v].size();i++){
				edge &e=G[v][i];
				if(e.cap>0&&level[e.to]<0){
					level[e.to]=level[v]+1;
					q.push(e.to);
				}
			}
		}
	}
	int dfs(int v,int t, int f) {
		if(v==t)return f;
		for(int &i=iter[v];i<G[v].size();i++){
			edge &e=G[v][i];
			if(level[v]>=level[e.to]||e.cap<=0) continue;
			int d =dfs(e.to,t,min(f,e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
		return 0;
	}
	int mf(int s,int t) {//from s to t,ford_fulkerson
		int flow=0;
		while(1){
			bfs(s);
			if(level[t]<0)return flow;
			iter=vi(n);
			int f;
			while((f=dfs(s,t,inf))>0)flow+=f;
		}
	}
};
int main(){
	int n,m;
	cin>>n>>m;
	vs in(n);
	rep(i,n)cin>>in[i];
	
	MF mf(n+m+2);
	int s=n+m,t=s+1;
	int sx,sy,gx,gy;
	rep(i,n)rep(j,m)if(in[i][j]=='o'){
		mf.add_edge(i,n+j,1);
		mf.add_edge(n+j,i,1);
	}else if(in[i][j]=='S'){
		sx=i,sy=j;
		mf.add_edge(s,i,inf);
		mf.add_edge(s,n+j,inf);
	}else if(in[i][j]=='T'){
		gx=i,gy=j;
		mf.add_edge(i,t,inf);
		mf.add_edge(n+j,t,inf);
	}
	if(sx==gx||sy==gy)cout<<-1<<endl;
	else cout<<mf.mf(s,t)<<endl;
}










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

using namespace std;

int main()
{
    char S[3][7]={"Sunny","Cloudy","Rainy"};
    string input;
    cin>>input;
    if(input=="Sunny")
        cout<<S[1]<<endl;
    else if (input=="Cloudy")
        cout<<S[2];
   else
    cout<<S[0];
    return 0;
}


Measured memory_bytes: 256
integer N
character(10),allocatable,dimension(:)::S
integer,allocatable,dimension(:)::B
integer,allocatable,dimension(:)::num
integer tmpnum
character(10) tmp
read*,N
allocate(S(N),B(N),num(N))
do i=1,N
  read*,S(i),B(i)
  num(i)=i
end do
do i = 2,N
  do j = i, 2, -1 
    if (s(j) > s(j - 1)) exit
    if (s(j) < s(j - 1) )then
      tmp = s(j)
      s(j) = s(j - 1)
      s(j - 1) = tmp
      
      tmpnum = b(j)
      b(j)= b(j-1)
      b(j-1)= tmpnum
      
      tmpnum = num(j)
      num(j)= num(j-1)
      num(j-1)= tmpnum
    else
      if(b(j) > b(j-1) )then
            tmpnum = b(j)
      b(j)= b(j-1)
      b(j-1)= tmpnum
      
      tmpnum = num(j)
      num(j)= num(j-1)
      num(j-1)= tmpnum
      endif
    endif
  end do
end do

do i=1,N
  print"(I0)",num(i)
end do
end

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

int main(){
  int a,b,c;  
  cin>>a>>b>>c;
    
  int cnt = 0;  
  for(int x = a; x <= b; x++){
       if(c % x == 0) cnt++;
    }
 
    cout<<cnt<<endl;
}
    


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

signed main()
{
    int k, a, b;
    cin >> k >> a >> b;
    a = (a + k - 1) / k;
    a *= k;
    if (a <= b)
        cout << "OK";
    else
        cout << "NG";
}

Measured memory_bytes: 3596
#include<iostream>
#include<map>

using namespace std;

pair<long long, long long> calc(map<int, int> odd) {
    pair<long long, long long> o1, o2;
    o1 = o2 = make_pair(int(), 0); // 0を-1にすると事故る 2種類以上なかったら0が答え
    for (auto e : odd) {
        if (e.second > o1.second) {
            if (o1.second > o2.second) o2 = o1;
            o1 = e;
        } else if (e.second > o2.second) {
            o2 = e;
        }
    }
    // cout << o1.first << " " << o1.second << endl;
    // cout << o2.first << " " << o2.second << endl;
    o1.first += o2.first * 1e6;
    o1.second += o2.second * 1e6;
    return o1;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    int x[n];
    map<int, int> odd, even;
    for (int i = 0; i < n; ++i) { cin >> x[i]; if (i % 2 == 0) even[x[i]]++; else odd[x[i]]++; }
    if (n == 2) { // 第2候補までとれる条件
        if (x[0] == x[1]) cout << 1 << endl;
        else cout << 0 << endl;
        return 0;
    } else if (n == 3) {
        if (x[0] == x[2] && x[0] != x[1]) cout << 0 << endl;
        else if (x[0] == x[2] && x[0] == x[1]) cout << 1 << endl;
        else if (x[0] != x[2] && x[0] != x[1]) cout << 1 << endl;
        else cout << 1 << endl;
        return 0;
    }
    pair<long long, long long> tmp = calc(odd);
    // cout << tmp.first << " " << tmp.second << endl;
    pair<int, int> o1, o2;
    o1 = make_pair(tmp.first % 1000000, tmp.second % 1000000);
    o2 = make_pair(tmp.first / 1000000, tmp.second / 1000000);
    tmp = calc(even);
    pair<int, int> e1, e2;
    e1 = make_pair(tmp.first % 1000000, tmp.second % 1000000);
    e2 = make_pair(tmp.first / 1000000, tmp.second / 1000000);
    if (o1.first != e1.first) {
        cout << n - o1.second - e1.second << endl;
    } else {
        cout << n - max(o1.second + e2.second, o2.second + e1.second) << endl;
    }
}


Measured memory_bytes: 7680
IDENTIFICATION DIVISION.
PROGRAM-ID. PROGRAM_ID.

ENVIRONMENT DIVISION.
INPUT-OUTPUT SECTION.
FILE-CONTROL.
   SELECT SYSIN ASSIGN TO KEYBOARD ORGANIZATION LINE SEQUENTIAL.

DATA DIVISION.
FILE SECTION.
FD SYSIN.
   01 INDATA  PIC X(200000).
WORKING-STORAGE SECTION.
01 S          PIC X(200000).
01 T          PIC X(200000).
01 i          PIC 9(10) COMP.
01 ans        PIC 9(10) VALUE ZERO COMP.
01 len        PIC 9(10).
01 zs         PIC Z(9)9.

PROCEDURE DIVISION.
  OPEN INPUT SYSIN.
  READ SYSIN INTO INDATA.
  MOVE INDATA TO S.
  READ SYSIN INTO INDATA.
  MOVE INDATA TO T.
  CLOSE SYSIN.
  MOVE FUNCTION STORED-CHAR-LENGTH(S) TO len.
  PERFORM VARYING i FROM 1 BY 1 UNTIL len < i
    IF S(i : 1) NOT = T(i : 1)
      ADD 1 TO ans
    END-IF
  END-PERFORM.
  MOVE ans TO zs.
  DISPLAY FUNCTION TRIM(zs).
  STOP RUN.


Measured memory_bytes: 4360
#include <stdio.h>
int main () {
  int a,b;
  char op;
  while(1){
  scanf("%d %c %d",&a,&op,&b);
    if(op == '+'){
      printf("%d\n",a+b);
    } else if(op == '-'){
      printf("%d\n",a-b);
    } else if(op == '*'){
      printf("%d\n",a*b);
    } else if(op == '/'){
      printf("%d\n",a/b);
    } else {
      break;
    }
  }
  return 0;
}


Measured memory_bytes: 2104
n = int(input())
ac = 0
wa = 0
tle = 0
re = 0
for i in range(n):
    tmp = input()
    if tmp == "AC":
        ac += 1
    elif tmp == "WA":
        wa += 1
    elif tmp == "TLE":
        tle += 1
    else:
        re += 1
print("AC x " + str(ac))
print("WA x " + str(wa))
print("TLE x " + str(tle))
print("RE x " + str(re))

Measured memory_bytes: 9044
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;

struct ans{
	int n;
	ans *next;
};

int main(){
	//
	ans *start=new ans();
	start->next=NULL;
	ans *end=start,*buf;
	//
	char s[20];
	char *ps;
	int i,j;
	int n,m,a;
	int h,p,q;
	int line[100][1000];
	int x,y;
	while(fgets(s,sizeof(s),stdin)){
		ps=strtok(s," ");
		n=atoi(ps);
		ps=strtok(NULL," ");
		m=atoi(ps);
		ps=strtok(NULL," ");
		a=atoi(ps)-1;
		if(n==0 && m==0 && a==-1) break;
		memset(line,0,sizeof(line));
		for(i=0;i<m;i++){
			fgets(s,sizeof(s),stdin);
			ps=strtok(s," ");
			h=atoi(ps)-1;
			ps=strtok(NULL," ");
			p=atoi(ps)-1;
			ps=strtok(NULL," ");
			q=atoi(ps)-1;
			
			line[p][h]=(q-p);
			line[q][h]=(p-q);
		}
		x=a;
		for(y=999;y>=0;y--) x+=line[x][y];
		//
		buf=new ans();
		buf->n=x+1;
		buf->next=NULL;
		end->next=buf;
		end=buf;
		//
	}
	buf=start->next;
	delete start;
	while(buf!=NULL){
		cout<<(buf->n)<<endl;
		end=buf;
		buf=buf->next;
		delete end;
	}
	return 0;
}

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

int main() {
  string n;
  cin >> n;
  string ans = "ABC" + n;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3608
import java.util.Scanner;

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++) {
           String[] s=sc.next().split(":");
           double c=Math.abs(Double.parseDouble(s[0])*60-Double.parseDouble(s[1])*11)/2;
           double d=Math.min(c,360-c);
           System.out.println(d<30?"alert":d<90?"warning":"safe");
        }
    }
}


Measured memory_bytes: 29884
///   Journey to the End of earth   ///
/// Gunjan Kumar ///
#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// #include <functional> // for less 
// using namespace __gnu_pbds; 
using namespace std;
#define ll  long long
#define s(n) scanf("%d",&n)
#define ls(n) scanf("%lld",&n)
#define p(n) printf("%d",n)
// #define ln() printf("\n")
#define pln(n) printf("%d\n",n)
#define lpln(n) printf("%lld\n",n)
#define rep(i,a,n) for(int i=a;i<n;i++)
#define rev(i,a,n) for(int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define gcd __gcd
#define tc           ll t1; cin>>t1; while(t1--)
#define inp         ll n; cin>>n; ll arr[n]; rep(i,0,n) cin>>arr[i];
#define vect vector<ll>
#define sortv(v)       sort(v.begin(),v.end())
#define lower(v,n)    lower_bound(v.begin(),v.end(),n)-v.begin()
#define upper(v,n)    upper_bound(v.begin(),v.end(),n)-v.begin()
#define bitcount(n) __builtin_popcount(n)
#define ln <<endl
#define inf          LONG_MAX
#define ninf         LONG_MIN
#define fast         ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const   ll mod=1e9+7;
const ll N=1e5+5;



int main()
{

         ios_base::sync_with_stdio(false);
        
         ll n;
         cin >> n ;
         ll arr[n];
         rep(i,0,n)
         cin >> arr[i];
         int pos=0;
         ll ans=1000;
         ll temp=ans;
         ll share=ans/arr[0];
        // cout<<share<<endl;
         ans=ans-share*arr[0];
       //  cout<<ans<<endl;
         rep(i,1,n)
         {
            if(arr[i]>arr[i-1])
            {
              ans+=share*arr[i];
              temp=ans;
              share=ans/arr[i];
              ans=ans-share*arr[i];
            }
            else if(arr[i]<arr[i-1])
            {
              ans=temp;
              share=ans/arr[i];
              ans=ans-share*arr[i];
            }
         }
         cout<<temp;
         
        
     return 0;
}



Measured memory_bytes: 3604
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
using namespace std;
#define INF (1 << 30)
typedef pair<int, int> P;
int dist[1050];
vector<P> edge[1050], two;
int n, m, a, b, c;
void dijkstra(int start){
    fill(dist, dist + 1050, INF);
    dist[start] = 0;
    priority_queue<P> pq;
    pq.push(P(0, start));
    while(!pq.empty()){
	P tmp = pq.top();pq.pop();
	int from = tmp.second, r = tmp.first;
	if(dist[from] < r)continue;
	for(int i = 0;i < edge[from].size();i++){
	    int to = edge[from][i].first, d = edge[from][i].second;
	    if(dist[to] <= dist[from] + d)continue;
	    dist[to] = dist[from] + d;
	    pq.push(P(dist[to], to));
	}
    }
}

int main(){
    while(cin >> n >> m, n|m){
	for(int i = 1;i <= n + n;i++)edge[i].clear();
	two.clear();
	for(int i = 0;i < m;i++){
	    cin >> a >> b >> c;
	    edge[a].push_back(P(b, c));
	    edge[b].push_back(P(a, c));
	    edge[a + n].push_back(P(b + n, c));
	    edge[b + n].push_back(P(a + n, c));
	}
	for(int i = 1;i <= n;i++){
	    for(int j = 0;j < edge[i].size();j++){
		for(int k = j + 1;k < edge[i].size();k++){
		    two.push_back(P(edge[i][j].first, edge[i][k].first));
		}
	    }
	}
	for(int i = 0;i < two.size();i++){
	    a = two[i].first, b = two[i].second;
	    edge[a].push_back(P(b + n, 0));
	    edge[b].push_back(P(a + n, 0));
	}
	edge[n].push_back(P(n + n, 0));
	dijkstra(1);

	cout << dist[n + n] << endl;
    }
    return 0;
}

Measured memory_bytes: 1300
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main() {
	int N, K, Q;
	cin >> N >> K >> Q;
	vector<ll> A(N);
	for (int i = 0; i < N; ++i) { cin >> A[i]; }

	ll res = 1e18;
	for (int i = 0; i < N; ++i) {
		vector<ll> use;
		int l = -1, r = 0;
		while (r < N) {
			while ((r < N) && (A[r] >= A[i])) { ++r; }

			int len = r - l - 1;
			vector<ll> tmp(len);
			if (len >= K) {
				for (int j = l + 1; j < r; ++j) {
					tmp[j - l - 1] = A[j];
				}
				sort(tmp.begin(), tmp.end());
				for (int j = 0; j < (len - K + 1); ++j) {
					use.push_back(tmp[j]);
				}
			}
			l = r;
			++r;
		}
		
		if (use.size() >= Q) {
			sort(use.begin(), use.end());
			ll tmp = use[Q - 1] - use[0];
			res = min(res, tmp);
		}
	}

	cout << res << endl;

	return 0;
}


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

using namespace std;

typedef long long llong;
typedef unsigned long long ullong;
#define inf 1ll<<60
#define pqueue priority_queue
#define mp make_pair
#define pb push_back
#define fn fill_n
#define int llong
#define be(x) x.begin(), x.end()
typedef pair<int, int> P;


signed main(){
	int N;
	int ans;
	int in;
	multiset<int> s;
	cin >> N;
	for(int i = 0; i < N; i++){
		cin >> in;
		s.insert(in);
	}

	while(s.size() > 1){
		auto it = s.end();
		it--;
		int maxi = *it;
		it--;
		int mmaxi = *it;

		s.erase(maxi);
		if(maxi%mmaxi > 0)
			s.insert(maxi%mmaxi);
		if(s.size() == 0)
			s.insert(mmaxi);
	}

	cout << *s.begin() << endl;

	return 0;
}

Measured memory_bytes: 4992
N, M = map(int, input().split())
x = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    x[a-1].append(b-1)
    x[b-1].append(a-1)

flag = [False]*N
flag[0] = True
res = 0

def f(n):
    global res
    for fl in flag:
        if not fl:
            break
    else:
        res += 1
        return
    for i in x[n]:
        if flag[i]:
            continue
        flag[i] = True
        f(i)
        flag[i] = False
    return

f(0)
print(res)

Measured memory_bytes: 3064
/* ****Ragnar7 _Lawliet_**** */
/* First, solve the problem.Then write the code. */
#include<bits/stdc++.h>
#define ll          long long
#define ld 			long double
#define hell        1000000007
#define time        cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
using namespace std;
const ll N = 1e6+5;
vector<pair<ll,ll> > v[N];
ll dist[N];
void dijkstra(ll int x)
{
	dist[x]=0;
	priority_queue<pair<ll,ll> > q;
	q.push({0,x});
	while(!q.empty())
	{
		ll cur=q.top().second;
		q.pop();
		// if(!vis[cur])
		// cout<<cur<<endl;
		{
			// vis[cur]=1;
			for(auto i:v[cur])
			{
				// cout<<cur<<" "<<i.first<<endl;
				if(dist[i.first]>dist[cur]+i.second)
				{
					dist[i.first]=dist[cur]+i.second;
					q.push({-1*dist[i.first],i.first});
				}
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	#ifndef ONLINE_JUDGE
	freopen ("input.txt","r",stdin);
	// freopen ("output.txt","w",stdout);
	#endif
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		ll n,m;
		cin>>n>>m;
		ll ch,cw;
		cin>>ch>>cw;
		ll source = m*(ch-1) + cw-1;
		cin>>ch>>cw;
		ll dest =  m*(ch-1) + cw-1;
		char a[1005][1005];
		for(ll i=0;i<=n+2;i++)
			for(ll j=0;j<=m+2;j++)
				a[i][j] = '#';
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=m;j++)
				cin>>a[i][j];
		for(ll i=0;i<N;i++)
			dist[i] = hell;
		vector<ll> bc(2,0); bc[0] =1;bc[1]=-1;
		ll x,y;
		for(ll i=1;i<=n;i++)
		{
			for(ll j=1;j<=m;j++)
			{
				if(a[i][j]=='#')
					continue;
				x = (i-1)*m + j-1;
				for(auto k :bc)
				{
					y = (i-1+k)*m + j-1;
					if(a[i+k][j]=='.')
						v[x].push_back({y,0LL});
				}
				for(auto k :bc)
				{
					y = (i-1)*m + j+k-1;
					if(a[i][j+k]=='.')
						v[x].push_back({y,0LL});
				}

				for(ll k=max(1LL,i-2);k<=min(n,i+2);k++)
				{
					for(ll l=max(1LL,j-2);l<=min(m,j+2);l++)
					{
						y = (k-1)*m + l-1;
						if(x!=y and a[k][l] == '.')
							v[x].push_back({y,1LL});
					}
				}
			}
		}
		// for(ll i=0;i<n*m;i++)
		// {
		// 	cout<<i<<" ";
		// 	for(auto j:v[i])
		// 		cout<<j.first<<" ";
		// 	cout<<endl;
		// }
		dijkstra(dest);
		if(dist[source]==hell)
			cout<<-1;
		else
		cout<<dist[source];
		
	}

	
	time
	return 0;
}

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

int main() {
	int n, p;
	while(cin >> n >> p && (n || p)){
		int stone[51] = {0}, bowl = p, turn = 0, ans = -1;
		while(1){
			if(bowl > 0){
				bowl -= 1;
				stone[turn]++;
			}
			else{
				bowl += stone[turn];
				stone[turn] = 0;
			}
			
			if(stone[turn] == p){
				ans = turn;
				break;
			}
			turn++;
			if(turn == n)
				turn = 0;
		}
		cout << ans << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<map>
#include<vector>
#include<functional>
#include <random>

using namespace std;

int main(void) {
	int N, a[100000];
	int ans;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &a[i]);
	}

	ans = 2;
	for (int i = 0; i < N; i++) {
		if (a[i] % 2 == 1) {
			ans = 1;
		}
	}
	if (ans == 1) {
		printf("first\n");
	}
	else {
		printf("second\n");
	}
}


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

#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 VI         vector<int>
#define MOD 1000000007

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

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

const ll INF=(ll)1e19;
//const int INF=(1<<30);

int main(){
  int n,k;
  cin >> n >> k;
  string s;
  cin >> s;
  VI c0, c1;
  int cnt=1;
  if(s[0]=='0')c1.emplace_back(0);

  FOR(i,1,(int)s.size()){
    if(s[i]==s[i-1]){
      cnt++;
    }else if(s[i-1]=='0'){
      c0.emplace_back(cnt);
      cnt=1;
    }else{
      c1.emplace_back(cnt);
      cnt=1;
    }
  }
  if(s.back() == '0'){
    c0.emplace_back(cnt);
  }else{
    c1.emplace_back(cnt);
  }

  if(c0.size() <= k){
    cout << s.size() << endl;
    return 0;
  }

  int t=0;
  REP(i,k)t+=c0[i];
  REP(i,k+1)t+=c1[i];

  int ans=t;
  FOR(i,k,(int)c0.size()){
    t += c0[i];
    if(i+1 < c1.size())t += c1[i+1];
    t -= c0[i-k];
    t -= c1[i-k];
    chmax(ans,t);
  }
  cout << ans << endl;

}



Measured memory_bytes: 1020
#include <iostream>
#include <deque>

int main(){
    std::deque<int> deq;
    int q;
    std::cin >> q;
    for (int i{0};i<q;i++){
        int a,b,c;
        std::cin >> a;
        if(a==0){
            std::cin >> b >> c;
            if(b==0){deq.emplace_front(c);}
            if(b==1){deq.emplace_back(c);}
        }
        if(a==1){
            std::cin >> b;
            std::cout << deq[b] << std::endl;
        }
        if(a==2){
            std::cin >> b;
            if(b==0){deq.pop_front();}
            if(b==1){deq.pop_back();}
        }
    }
}


Measured memory_bytes: 4564
#include<bits/stdc++.h>
using namespace std;
int a[100001],dp[100001];
int solve(int n)
{
    dp[0]=0;
    dp[1]=abs(a[0]-a[1]);
    for(int i=2;i<n;i++)
    {
        int d=abs(a[i]-a[i-1]);
        int e=abs(a[i]-a[i-2]);
        dp[i]=min(dp[i-2]+e,dp[i-1]+d);
    }
    return dp[n-1];
}
int main()
{
    int n;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        cin >> a[i];
    }
    cout << solve(n) << endl;
}

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

int main() {
    ll n, a;
    cin >> n >> a;
    vector<int> A(a);
    
    for(int i = 0; i < a; i++) {
        cin >> A[i];
    }
    sort(A.begin(),A.end());
    reverse(A.begin(), A.end());
    for(int i = 0; i < a; i++) {
        n -= A[i];
        if(n <= 0) break;
    }
    if(n > 0) puts("No");
    if(n <= 0) puts("Yes");

    return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
using Pld = pair<ld, ld>;
using Vec = vector<ll>;
using VecP = vector<P>;
using VecB = vector<bool>;
using VecC = vector<char>;
using VecD = vector<ld>;
using VecS = vector<string>;
template <class T>
using Vec2 = vector<vector<T>>;
#define REP(i, m, n) for(ll i = (m); i < (n); ++i)
#define REPN(i, m, n) for(ll i = (m); i <= (n); ++i)
#define REPR(i, m, n) for(ll i = (m)-1; i >= (n); --i)
#define REPNR(i, m, n) for(ll i = (m); i >= (n); --i)
#define rep(i, n) REP(i, 0, n)
#define repn(i, n) REPN(i, 1, n)
#define repr(i, n) REPR(i, n, 0)
#define repnr(i, n) REPNR(i, n, 1)
#define all(s) (s).begin(), (s).end()
#define pb push_back
#define fs first
#define sc second
template <class T1, class T2>
bool chmax(T1 &a, const T2 b){if(a < b){a = b; return true;} return false;}
template <class T1, class T2>
bool chmin(T1 &a, const T2 b){if(a > b){a = b; return true;} return false;}
ll pow2(const int n){return (1LL << n);}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    for (const T &i : v) os << i << ' ';
    return os;
}
void co() { cout << '\n'; }
template <class Head, class... Tail>
void co(Head&& head, Tail&&... tail) {
    cout << head << ' ';
    co(forward<Tail>(tail)...);
}
void ce() { cerr << '\n'; }
template <class Head, class... Tail>
void ce(Head&& head, Tail&&... tail) {
    cerr << head << ' ';
    ce(forward<Tail>(tail)...);
}
void sonic(){ios::sync_with_stdio(false); cin.tie(0);}
void setp(const int n){cout << fixed << setprecision(n);}
constexpr int INF = 1000000001;
constexpr ll LINF = 1000000000000000001;
constexpr ll MOD = 1000000007;
constexpr ll MOD_N = 998244353;
constexpr ld EPS = 1e-11;
const double PI = acos(-1);

int main(void) {
    ll n, m;
    cin >> n >> m;
    scc_graph scc(n);
    while (m--) {
        ll a, b;
        cin >> a >> b;
        scc.add_edge(a, b);
    }

    auto v = scc.scc();
    co(v.size());
    for (auto &i : v) co(i.size(), i);

    return 0;
}


Measured memory_bytes: 41092
package main

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

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func minInt64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func maxInt64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func absInt64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumInt64(a []int64) int64 {
	var ret int64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcdInt64(m, n int64) int64 {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcmInt64(m, n int64) int64 {
	return m / gcdInt64(m, n) * n
}

// sort ------------------------------------------------------------

type int64Array []int64

func (s int64Array) Len() int           { return len(s) }
func (s int64Array) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s int64Array) Less(i, j int) bool { return s[i] < s[j] }

type xxx struct {
	x int
}

type sortArray []xxx

func (s sortArray) Len() int           { return len(s) }
func (s sortArray) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s sortArray) Less(i, j int) bool { return s[i].x < s[j].x }

// -----------------------------------------------------------------

func main() {
	s := readString()
	var x, y int
	zero := byte('0')
	one := byte('1')
	b := s[0]
	for i := 1; i < len(s); i++ {
		if s[i] == b {
			x++
			if s[i] == zero {
				b = one
			} else {
				b = zero
			}
		} else {
			b = s[i]
		}
	}
	b = s[len(s)-1]
	for i := len(s) - 2; i >= 0; i-- {
		if s[i] == b {
			y++
			if s[i] == zero {
				b = one
			} else {
				b = zero
			}
		} else {
			b = s[i]
		}
	}

	fmt.Println(min(x, y))
}


Measured memory_bytes: 896
from collections import deque

N = int(input())
R = [list(map(int,input().split())) for _ in range(N)]
B = [list(map(int,input().split())) for _ in range(N)]

graph = [[] for _ in range(2*N+2)] #残余グラフを構成　0を始点，1を終点とする

for i in range(N):
    forward = [2+i,1,None] #[行き先，流量，逆辺の情報]
    forward[2] = backward = [0,0,forward]
    graph[0].append(forward)
    graph[2+i].append(backward)

for i in range(N):
    forward = [1,1,None]
    forward[2] = backward = [2+N+i,0,forward]
    graph[2+N+i].append(forward)
    graph[1].append(backward)

for i in range(N):
    for j in range(N):
        if R[i][0]<B[j][0] and R[i][1]<B[j][1]:
            forward = [2+N+j,1,None]
            forward[2] = backward = [2+i,0,forward]
            graph[2+i].append(forward)
            graph[2+N+j].append(backward)

flow = 0
while True:

    queue = deque([0])
    level = [None for _ in range(2*N+2)]
    level[0] = 0

    while queue:
        node = queue.popleft()
        for adj,adjcap,_ in graph[node]:
            if adjcap>0 and level[adj] is None:
                level[adj] = level[node]+1
                queue.append(adj)

    if level[1] is None:
        break

    stack = [0]
    visited = [0 for _ in range(2*N+2)]
    visited[0] = 1
    parent = [None for _ in range(2*N+2)]
    parent[0] = 0
    #*it, = map(iter, graph)
    
    while stack:
        node = stack.pop()
        for adj,adjcap,adjrev in graph[node]:
            if not visited[adj] and adjcap>0 and level[node]<level[adj]:
                visited[adj] = 1
                parent[adj] = node
                stack.append(adj)
                
    if visited[1]:
        flow += 1
        node = 1
        prev = parent[node]
        while node != 0:
            for g in graph[prev]:
                adj,adjcap,adjrev = g
                if adj == node:
                    g[1] = 0
                    adjrev[1] = 1
            node = prev
            prev = parent[node]
            
print(flow)

Measured memory_bytes: 3948
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define repr(i, a, b) for(int i = a; i >= b; i--)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define Vp vector<pair<ll, ll>>
using ll = long long;
#define ALL(v) (v).begin(),(v).end()
#define endl "\n"
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define co(x) cout << x << endl
#define coel cout << endl
#define pb push_back
#define sz(v) ((ll)(v).size())
using namespace std;  
const double pi = acos(-1.0);
const ll MOD = 1e9 + 7;
const ll INF = 1LL << 60;
#define pp pair<ll, pair<ll, ll>> 
#define fi first
#define se second

////////////////////////////////////////////////////////


int main() {
    ll n; cin >> n;
    Vl a(n);
    rep(i, 0, n) cin >> a[i];
    sort(ALL(a), greater<ll>());
    ll ans = 0;
    ans += a[0];
    if(n == 2){
        co(ans);
        return 0;
    }
    ll t = 1;
    rep(i, 1, n){
        ans += a[i];
        t++;
        if(t == n-1) break;
        ans += a[i];
        t++;
        if(t == n-1) break;
    }
    co(ans);

    return 0;
}


Measured memory_bytes: 4780
#include <stdio.h>

int main(void)
{
	double r,area,circ;
	
	scanf( "%lf", &r );
	
	if((0<r)&&(r<10000))
	{
		area = r * r * 3.141592653589;
		circ = 2 * r * 3.141592653589;
		
		printf( "%lf %lf\n",area, circ );
	}
	return 0;
}



Measured memory_bytes: 2104
#include<iostream>
#include<string>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
using namespace std;

#define INF 1e9
#define rep(i,j,n) for(int (i)=(j);(i)<(n);(i)++)
#define rep2(i,j,n) for(int (i)=(j);(i)<=(n);(i)++)
#define all(i) (i).begin(),(i).end()
#define rall(i) (i).rbegin(),(i).rend()

typedef long long i64;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef vector<vs> vvs;

int main(){
  int a,b,c,d;
  cin>>a>>b>>c>>d;
  vi vec(101,0);
  rep2(i,a,b) vec[i]++;
  rep2(i,c,d) vec[i]++;
  int ans=0;
  rep2(i,0,100){
    if(vec[i]==2) ans++;
  }
  ans--;
  cout<<max(ans,0)<<endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<bitset>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<list>
#include<iomanip>
#include<cmath>
using namespace std;

#define repr(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define rep(i, n) repr(i, 0, n)
#define INF 2e9
#define MOD 1000000007
//#define MOD 998244353
#define LINF (long long)4e18
#define jck 3.141592

using ll = long long;
using Pi = pair<int,int>;
using Pl = pair<ll,ll>;


int dp[100010][3];
int main(){
    int N; cin >> N;
    rep(i,100010)rep(j,3) dp[i][j] = 0;
    rep(i,N){
        int a,b,c; cin >> a >> b >> c;
        dp[i+1][0] = max(dp[i][1]+a,dp[i][2]+a);
        dp[i+1][1] = max(dp[i][0]+b,dp[i][2]+b);
        dp[i+1][2] = max(dp[i][0]+c,dp[i][1]+c);
    }
    cout << max(dp[N][0],max(dp[N][1],dp[N][2])) << endl;
}



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

using namespace std;
 
#define rep2(x,fr,to) for(int (x)=(fr);(x)<(to);(x)++)
#define rep(x,to) for(int (x)=0;(x)<(to);(x)++)
#define repr(x,fr,to) for(int (x)=(fr);(x)>=(to);(x)--)
#define all(c) (c).begin(),(c).end()
#define sz(v) (int)(v).size()

typedef int64_t ll; typedef vector<int> VI; typedef pair<ll,ll> pii;
const int MD = 1e9+7; typedef vector<ll> VL;

void dbg(){ cerr << "\n"; }  
template <typename T,typename ...T2>
void dbg(const T& fst, const T2&...rst){ cerr << fst << ": "; dbg(rst...); }


int main()
{
	
	cin.tie(0); ios_base::sync_with_stdio(false);
	int n, k;
	cin >>n >>k;
	VI h(n);
	rep(i, n) cin >>h[i];
	sort(all(h));
	
	int ans = MD;
	rep(i, n-k+1){
		int w = h[i+k-1] - h[i];
		ans = min(ans, w);
	}
	cout <<ans <<"\n";
	return 0;
}


Measured memory_bytes: 640
N, M = map(int, input().split())
*a, = map(int, input().split())

tot = sum(a)

cnt = 0
for x in a:
    cnt += int(x * 4 * M >= tot)

print('Yes' if cnt >= M else 'No')

# 候補>=得票数の総和/4m
# 候補*4m>=得票数の総和


Measured memory_bytes: 2940
#include <stdio.h>

int main()
{
    int X;
    scanf("%d", &X);
    if(X>=400 && X<600){
        printf("%d",8);
        printf("\n");
    }else if(X>=600 && X<800){
        printf("%d",7);
        printf("\n");
    }else if(X>=800 && X<1000){
        printf("%d",6);
        printf("\n");
    }else if(X>=1000 && X<1200){
        printf("%d",5);
        printf("\n");
    }else if(X>=1200 && X<1400){
        printf("%d",4);
        printf("\n");
    }else if(X>=1400 && X<1600){
        printf("%d",3);
        printf("\n");
    }else if(X>=1600 && X<1800){
        printf("%d",2);
        printf("\n");
    }else if(X>=1800 && X<2000){
        printf("%d",1);
        printf("\n");
    }

    return 0;
}

Measured memory_bytes: 1724
#include<iostream>
#include<vector>
#include<algorithm>
#include<climits>
using namespace std;

const int MAX_N=100;

struct edge{
	int to,cap,rev;
};

vector<edge> G[MAX_N];
vector<int> check(MAX_N,0);

int dfs(int v,int t, int f ){
	if(v==t){return f;}
	check[v]=1;
	for(int i=0;i<G[v].size();i++){
		edge &e = G[v][i];
		if(check[e.to]==0 && e.cap > 0){
			int ff =dfs(e.to,t,min(f,e.cap));
			if(ff>0){
				e.cap -= ff;
				G[e.to][e.rev].cap += ff;
				return ff;
			}
		}
	}
	return 0;
}

int maxflow(int s,int t){
	int flow = 0;
	while(1){
		fill(check.begin(),check.end(),0);
		int f = dfs(s,t,INT_MAX);
		if(f==0){return flow;}
		flow += f;
	}
}

int main(){
	int V,E,s,t,c;
	cin >> V >> E;
	
	for(int i=0;i<E;i++){
		cin >> s >> t >> c;
		G[s].push_back((edge){t,c,G[t].size()});
		G[t].push_back((edge){s,0,G[s].size()-1});
	}
	
	cout << maxflow(0,V-1) << endl;
	return 0;
}

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

int main()
{
	using namespace std;
	int N;
	cin >> N;

	vector<int> L;
	L.resize(N);
	for (auto &v : L)
		cin >> v;

	bool waterFlag = false;
	bool end = true;
	int numOfWater = 0;
	while (true) {
		end = true;
		for (int i = 0; i < N; i++) {
			if (L[i] > 0) {
				waterFlag = true;
				end = false;
				L[i] -= 1;
			}
			else {
				if (waterFlag) {
					waterFlag = false;
					numOfWater++;
				}
			}
		}
		if (waterFlag == true) {
			waterFlag = false;
			numOfWater++;
		}
		if (end)
			break;
	}

	cout << numOfWater << endl;

}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]  
    n = int(input())
    a = [int(x) for x in input().split()]
    cnt = defaultdict(int)
    for e in a:
        cnt[e] += 1
    
    xd = 0
    for c in cnt:
        if cnt[c] == 2:
            xd += 1
    target = n // 2
    if n % 2 == 0:
        if xd == target and cnt[0] == 0:
            print(pow(2, xd, MOD))
            return
    else:
        if xd == target and cnt[0] == 1:
            print(pow(2, xd, MOD))
            return
        
    print(0)



    
t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""
a b a
d c d
a b a
"""


Measured memory_bytes: 21436
/*************************************************************
 * ?´???°?????°
 ************************************************************/
#include <stdio.h>

int main(){
        int  a, b, c;
        int  i, count = 0;
        char line[30];

        fgets(line, sizeof(line), stdin);
        sscanf(line, " %d %d %d", &a, &b, &c );

        for(i = 1; i <= c; i++ ){
                if(c % i == 0 && i >= a && i <= b ) count++;
        }

        printf("%d\n", count );

        return 0;
}

Measured memory_bytes: 604
#include <stdio.h>

typedef long long ll;

int main(void)
{
	ll n, d, i, ans = 0;

	scanf("%lld %lld", &n, &d);

	while (n--)
	{
		ll p, q;

		scanf("%lld %lld", &p, &q);

		if (p * p + q * q <= d * d)
			ans++;
	}

	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 1732
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define rep(i,n) for(ll i=0;i<n;++i)
#define ocut cout
#define ouct cout
#define itn int
int main(){
  int n;
  cin >> n;
  int p[n];
  int q=0,r,s=0;
  rep(i,n){
    cin >> p[i];
    if(p[i]>q){
      q=p[i];
      r=i;
    }
    s+=p[i];
  }
  s-=p[r]/2;
  cout << s;
}

Measured memory_bytes: 256
X, Y = map(int, input().split())


c = [0, 300000, 200000, 100000]

res = 0
if 0 <= X < 4:
    res += c[X]
if 0 <= Y < 4:
    res += c[Y]

if X == 1 and Y == 1:
    res += 400000

print(res)


Measured memory_bytes: 3064
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
typedef unsigned int uint;
using namespace std;

int main(){
  int N;
  cin >> N;
  int x[N];
  int tmp[N];
  for(int i=0;i<N;i++){
    cin >> x[i];
    tmp[i] = x[i];
  }

  sort(tmp,tmp+N);

  int med1 = tmp[N/2-1];
  int med2 = tmp[N/2];

  for(int i=0;i<N;i++){
    if(x[i]<=med1) cout << med2 << endl;
    else if(x[i]>=med2) cout << med1 << endl;
  }

  return 0;
}


Measured memory_bytes: 3712