akhauriyash/Code-Regression huggingface dataset:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.TreeMap;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {
	public static void main(String[] args) {
		try(Scanner sc = new Scanner(System.in)) {
			int n = sc.nextInt();
			List<Integer> a =  IntStream.range(0, n).mapToObj(x->sc.nextInt()).collect(Collectors.toList());
			int q = sc.nextInt();
			for(int i = 0; i < q; i++) {
				int cmd = sc.nextInt();
				int b = sc.nextInt();
				int e = sc.nextInt();
				if(cmd == 0) {
					System.out.println(Collections.min(a.subList(b, e)));
				}
				else {
					System.out.println(Collections.max(a.subList(b, e)));
				}
			}	
		}
	}

}



Measured memory_bytes: 36816
/*Author - Shubham Gupta (@shubham107)*/
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<ll> vl;		typedef vector<int> vi;
typedef vector<vl> vvl;	  	typedef vector<vi> vvi;
typedef pair<ll, ll> pll;	typedef pair<int, int> pii;
#define int ll
#define forn(i,n) for(int i=0;i<n;i++)
#define rforn(i,n) for(int i=n-1;i>=0;i--)
#define forne(i,n) for(int i=1;i<=n;i++)
#define forse(i,s,e) for(int i=s;i<e;i++)
#define rforse(i,s,e) for(int i=e-1;i>=s;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define MOD 1000000007
#define F first
#define S second
#define pb push_back
#define fill(a,x) memset(a,x,sizeof a);
#define trav(a,x) for(auto &a:x)
#define INF	int(1e17)
#ifdef SHUBHAM107
#include "../code-pieces/trace.h"
#else
#define trace(args...)
#endif

ll modpow(ll a, ll b, ll m = MOD) {
	a %= m; ll res = 1; while (b) {if (b & 1)res = res * a % m; a = a * a % m; b >>= 1;}
	return res;
}
ll bpow(ll a, ll b) {ll res = 1; while (b) {if (b & 1)res = res * a; a = a * a; b >>= 1;} return res;}
ll modinv(ll a) {return modpow(a, MOD - 2, MOD);}
void graph(vvi &adj, int m) {int x, y; forn(i, m) {cin >> x >> y; adj[x - 1].pb(y - 1); adj[y - 1].pb(x - 1);}}

const int mxM = 25e2, mxN = 50;
typedef vector<vector<pair<int,pii>>> vvpiii;
typedef pair<int, pii> ppii;
vector<pii> city(mxN);
int n, m, s;
ll dist[50][mxM + 5];
void djik(vvpiii &adj){
	priority_queue<ppii> q;
	q.push({0, {0, s}});
	while(!q.empty()){
		ppii cur = q.top();
		q.pop();
		int cit = cur.S.F, dis = -cur.F, stat = cur.S.S;
		trace(cit, dis, stat);
		if(dist[cit][stat] < dis) continue;
		trav(to, adj[cit]){
			int edge = to.S.S, silver = to.S.F;
			if(stat >= silver && dist[to.F][stat-silver] > edge + dis){
				dist[to.F][stat-silver] = edge + dis;
				q.push({-(edge + dis), {to.F, stat-silver}});
			}
		}
		if(stat+city[cit].F <= mxM && dist[cit][stat+city[cit].F] > city[cit].S + dis){
			dist[cit][stat+city[cit].F] = city[cit].S + dis;
			q.push({-(city[cit].S + dis), {cit, stat+city[cit].F}});
		}
	}
}

void solve() {
	cin >> n >> m >> s;
	s = min(s, mxM);
	vvpiii adj(n);
	int u, v, a, b;
	forn(i, m){
		cin >> u >> v >> a >> b;
		u--, v--;
		adj[u].pb({v, {a, b}});
		adj[v].pb({u, {a, b}});
	}
	forn(i, n) forn(j, mxM) dist[i][j] = INF;
	forn(i, n) cin >> city[i].F >> city[i].S;
	djik(adj);
	forne(i,n-1){
		int minm = INF;
		forn(j, mxM) minm = min(minm, dist[i][j]);
		cout << minm << '\n';
	}
}
signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef SHUBHAM107
	freopen("inp.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
	freopen("err.txt", "w", stderr);
#endif
	int t = 1;
	// cin >> t;
	while (t--) {
		solve();
	}
}


Measured memory_bytes: 6256
//		HYSO SERIOUS? WHY SO SERIOUS                            RIOUS? WHY SO SERIOUS? WHYSO SERIO
//		 ERIOUS? WHY SO SERIOUS ? WHY                          WHY SO SERIOUS? WHY SOSERIOUSWHYS
//		       OSERIOUS? WHY SO SERIOU         SERIOUS        ERIOUS? WHY SO SERIOUS? WHYS
//		          WHY SO SERIOUS? WHY SOSERIOUS? WHYSOSERIOUS? WHY SO SERIOUS?WHY SO SE
//		           ERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SOSERIO
//		           WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WH
//		            SERIOUS?WHYSO SERIOUS? WHY SO SERIOUS? WHY SO SERIOUS? WHYSO SE
//		              ?WHYSOSERIOUS?WHY SO SERIOUS? WHY SO SERIOUS?WHYSO SERIOUS?
//		                           OSERIOUS? WHY SO SERIOUS?WHYSOSER
//		                                 HYSOSERIOUS?WHYSOSERI
//		                                     SOSERIOUS?W
//		                                         SER
//		                                          W
 
#include <iostream>
using namespace std;
#include<bits/stdc++.h>
#include <algorithm>
#define ll long long int
#define read(a) long long int a; cin>>a;
#define readstr(s) string s; cin>>s;
#define readarr(a,l) long long int a[l]={0}; for(ll i=0;i<l;i++) cin>>a[i];
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define rloop(i,a,b) for(ll i=a;i>b;i--)
#define ff first
#define ss second
#define readmtrx(i,j,a,b) ll arr[a][b]={0};for(ll i=0;i<a;i++)for(ll j=0;j<b;j++) cin>>arr[i][j];
#define v(pi) vector<ll>pi
#define vp(pi) vector<pair<ll,ll>>pi
#define fast ios_base::sync_with_stdio(false);cin.tie(0);
#define pb(p) push_back(p)
#define mp make_pair
#include <cmath>
#include <map>
#define mi(lol) map<ll,ll>lol
 
int main() {
	fast;
char c;
  cin>>c;c++;
  cout<<c;
 
	return 0;
}

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

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

  vector<int> A(N);
  int tot = 0;
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    tot += A.at(i);
  }

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

  for (int i = 0; i < N; i++) {
    if (tot % 10 != 0) break;
    if (A.at(i) % 10 != 0) tot -= A.at(i);
  }

  if (tot % 10 == 0)
    cout << 0 << endl;
  else
    cout << tot << endl;
}

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

    
int main()
{
   int n,ans=0,a[100006],d;
   cin>>n;
   for(int i=1;i<=n;i++){ 
       cin>>a[i];
   } 
   sort(a+1,a+n+1);
   if(n%2==0){ 
       int go=(n/2);
       cout<<a[go+1]-a[go]<<endl; 
   } 
   else cout<<0<<endl; 
   for(int i=1;i<=n;i++){ 
   //    cout<<a[i]<<" ";
   }
   
   

    return 0;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define MAX 100005
long long arr[MAX];
int main()
{
    long long n, k, a, b;
    long long i, cnt=0;
    cin >> n >> k;
    vector <bool> ans(n+1, true);
    for(i=1;i<=n;i++) cin >> arr[i];
    for(i=0;i<k;i++){
        cin >> a >> b;
        if(arr[a] < arr[b]) ans[a] = false;
        else if(arr[a] > arr[b]) ans[b] = false;
        else{
            ans[a] = false;
            ans[b] = false;
        }
    }
    for(i=1;i<=n;i++){
        if(ans[i]) cnt++;
    }
    cout << cnt << endl;
    return 0;
}



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

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

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

    int n;cin>>n;
    vector<int> d(n+1,0),pos(n+1,0);
    for(int i=1;i<=n;i++) cin>>d[i];
    sort(d.begin(),d.end());
    bool f=1;
    for(int i=1;i<=n;i++){
        if(f) pos[i]=-d[i];
        else pos[i]=d[i];
        f = !f;
        //cout<<pos[i]<<endl;
    }
    int res=100;
    for(int i=0;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            int dif=abs(max(pos[i],pos[j])-min(pos[i],pos[j]));
            res = min(res,min(dif,24-dif));
        }
    }
    cout<<res<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
int N,Ma,Mb;
int A[50];
int B[50];
int C[50];
int dp[501][501];
int dp2[501][501];

int main(){
	cin>>N>>Ma>>Mb;
	REP(i,N){
	    cin>>A[i]>>B[i]>>C[i];
	}
	REP(i,501){
	    REP(j,501){
	        dp[i][j] =1000000;
	        dp2[i][j]=1000000;
	    }
	}
	dp[0][0]=0;
	dp2[0][0]=0;
	REP(i,40){
	    REP(j,501-A[i]){
	        REP(k,501-B[i]){
	            if(dp[j][k]!=1000000){
	               dp2[j+A[i]][k+B[i]]=min(dp2[j+A[i]][k+B[i]],dp[j][k]+C[i]);
	            }
	        }
	    }
	    REP(j,501){
	        REP(k,501){
	            dp[j][k]=dp2[j][k];
	        }
	    }
	}
	int ans=1000000;
	int t1=Ma;
	int t2=Mb;
	/*REP(i,11){
	    REP(j,11){
	        cout<<dp[i][j]<<" ";
	    }
	    cout<<endl<<endl;
	}*/
	while(1){
	   //cout<<t1<<endl;
	   if(t1>500||t2>500){
	      break;
	   }
	   ans=min(dp[t1][t2],ans);
	   t1+=Ma;
	   t2+=Mb;
	}
	if(ans==1000000){
	   cout<<-1<<endl;
	}else{
           cout<<ans<<endl;
        }
	return(0);
}

Measured memory_bytes: 2176
import java.util.*;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    long[] a = new long[N];
    long x = 0, y = 0;
    long sum = 0;
    long min, gap;
    for(int i = 0; i < N; i++) {
      a[i] = sc.nextLong();
      sum += a[i];
    }
    min = Math.abs(a[0] - (sum - a[0]));
    for(int i = 0; i < N - 1; i++) {
      x += a[i];
      y = sum - x;
      gap = Math.abs(x - y);
      if(min > gap) {
        min = gap;
      }
    }
    System.out.println(min);
  }
}


Measured memory_bytes: 65876
#include <iostream>
#include <set>
#include <map>
using namespace std;

int M,N;
map<pair<set<int>,set<int>>,int> m;
char F[129][12];

int dfs(set<int> ob,set<int> fe){
    if(ob.size()<=1) return (M-(int) fe.size());
    if(m.count({ob,fe})) return m[{ob,fe}];
    int res = 1e9;
    set<int> fe2 = fe;
    for(auto x:fe){
        set<int> ob0,ob1;
        for(auto y:ob){
            if(F[y][x]=='0') ob0.insert(y);
            else ob1.insert(y);
        }
        fe2.erase(x);
        res = min(res,max(dfs(ob0,fe2),dfs(ob1,fe2)));
        fe2.insert(x);
    }
    return m[{ob,fe}] = res;
}

int main(){
    while(cin >> M >> N && N>0){
        m.clear();
        for(int i=0;i<N;i++) for(int j=0;j<M;j++) cin >> F[i][j];
        set<int> ob,fe;
        for(int i=0;i<N;i++) ob.insert(i);
        for(int j=0;j<M;j++) fe.insert(j);
        cout << dfs(ob,fe) << endl;
    }
}
/*
#if
全探索するとO(2^n)かかるように見えるが、featureの状態を考えると、{質問されてyes,質問されてno,質問されていない}
の3状態しかない。つまり、ありえる状態はO(3^m)しかなく、メモ化再帰を行うことで十分間に合う。
setで状態を管理したが計算時間的に重くなってしまった気がする。
#endif
*/


Measured memory_bytes: 32328
#include <iostream>
#include <string>

using namespace std;


int main(void){
    int n;
    cin >> n;
    string s;
    cin >> s;
    int count=0;
    for(auto x: s){
        if(x=='R'){
            count++;
        }
    }
    cout << (count > n/2 ? "Yes":"No") << endl;
    return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define MAXN 1010
#define MO 1000000007
#define LL long long
int cnt,s1,s2,f1,f2,n,m;
LL k;
char s[MAXN][MAXN];
LL PowMod(LL a,LL b)
{
	b%=(MO-1);
	LL ret=1;
	while(b)
	{
		if(b&1) ret=ret*a%MO;
		a=a*a%MO;
		b>>=1;
	}
	return ret;
}
struct maz
{
	LL a[2][2];
	maz(){memset(a,0,sizeof a);};
	maz operator*(maz &m)
	{
		maz ret;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				for(int k=0;k<2;k++)
					ret.a[i][j]=(ret.a[i][j]+a[i][k]*m.a[k][j]%MO)%MO;
		return ret;
	}
};
int main()
{
	scanf("%d%d%lld",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s[i]+1);
		for(int j=1;j<=m;j++)
			if(s[i][j]=='#')
			{
				cnt++;
				s1+=(s[i-1][j]=='#');
				s2+=(s[i][j-1]=='#');
			}
		if(s[i][1]=='#'&&s[i][m]=='#') f2++;
		if(i==n)
		{
			for(int j=1;j<=m;j++)
				if(s[1][j]=='#'&&s[n][j]=='#') f1++;
		}
	}
	if((f1&&f2)||k==0)
	{
		printf("1\n");
		return 0;
	}
	else if(f1==0&&f2==0)
	{
		printf("%lld\n",PowMod(cnt,k-1));
		return 0;
	}
	if(f1==0)
	{
		swap(f1,f2);
		swap(s1,s2);
	}
	maz A,ans;
	A.a[0][0]=cnt,A.a[1][0]=s1,A.a[1][1]=f1;
	ans.a[0][0]=ans.a[1][1]=1;
	k--;
	while(k)
	{
		if(k&1) ans=ans*A;
		A=A*A;
		k>>=1;
	}
	printf("%lld\n",(ans.a[0][0]-ans.a[1][0]+MO)%MO);
}

Measured memory_bytes: 1280
from functools import reduce
import math

def main():
    # 文字列の2進数を数値にする
    # '101' → '5'
    # 文字列の頭に'0b'をつけてint()にわたす
    # binary = int('0b'+'101',0)

    # 2進数で立っているbitを数える
    # 101(0x5) → 2
    # cnt_bit = bin(5).count('1')
    
    # N! を求める
    # f = math.factorial(N)
    
    # 切り捨て
    # 4 // 3
    # 切り上げ
    #-(-4 // 3)
    
    # 初期値用:十分大きい数(100億)
    INF = float("inf")
    
    # 1文字のみを読み込み
    # 入力:2
    # a = input().rstrip()
    # 変数:a='2'
    
    # スペース区切りで標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a, b, c, d = (int(_) for _ in input().split())  
    # 変数:a=2 b=4 c=5 d =7
    
    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2 4 5 7
    # a = list(int(_) for _ in input().split())
    # 変数:a = [2, 4, 5, 7]    

    # 1文字ずつ標準入力を配列として読み込み
    # 入力:2457
    # a = list(int(_) for _ in input())
    # 変数:a = [2, 4, 5, 7]    
    a, b, c = (int(_) for _ in input().split())
    
    print(min(a+b,b+c,a+c))
    
if __name__ == '__main__':
    main()


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

signed main(){
  int N, A;
  cin >> N >> A;
  
  vector<int> W(N+1);
  vector<int> V(N+1);
  for( int i = 1; i <= N; i++ ) cin >> W.at(i) >> V.at(i);
  
  vector<vector<int>> dp(N+1, vector<int>(A+200000));
  dp.at(0).at(0) = 0;
  
  //i番目までの荷物で重さj以下にしたときの価値の最大値
  for( int i = 1; i <= N; i++ ){
    for( int j = 0; j <= A; j++ ){
      if( j-W.at(i) >= 0 ){ 
        dp.at(i).at(j) = max(dp.at(i-1).at(j), dp.at(i-1).at(j-W.at(i))+V.at(i));
      }else{ //i番目の荷物を使わない場合i-1番目と結果は一緒
        dp.at(i).at(j) = dp.at(i-1).at(j);
      }
    }
  }
  
  cout << dp.at(N).at(A) << endl;
  
}


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

int main(){
  priority_queue<int> Q;
  string n;
  while(cin >> n && n != "end"){
    if(n == "insert"){
      int a;
      cin >> a;
      Q.push(a);
    }
    if(n == "extract"){
      int m = Q.top();
      Q.pop();
      cout << m << endl;
    }  
  }
}

#if 0
????????????????????\??????????????????????????°??????????????????. ??????, cin??????while???????????????????????????????????£?????????, ???????????????????????????????????¨????????????, ?????????. ???????????´???????????±??¢??¬??????????????¨?°???\??????. ???????????????15????¨??????§?????£???.
#endif

Measured memory_bytes: 5716
import heapq

n, m = map(int, input().split())
t_r_list = []
for i in range(n):
    t_r_list.append(list(map(int, input().split())))

t_r_list.sort()
que = []
total = 0
l = 0
for j in range(1, m + 1):
    while True:
        if l == n:
            break
        if t_r_list[l][0] != j:
            break
        heapq.heappush(que, -t_r_list[l][1])
        l += 1

    if que:
        total -= heapq.heappop(que)


print(total)

Measured memory_bytes: 72792
#include <iostream>
using namespace std;
int w, h;
char data[50][50];
int cnt;
char bw;
bool flag;

void rec(int x, int y) {
  static int d[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
  data[y][x] = '#';
  cnt++;
  for(int i = 0; i < 4; i++) {
    int nx = x + d[i][0];
    int ny = y + d[i][1];
    if(nx < 0 || nx >= w) continue;
    if(ny < 0 || ny >= h) continue;
    if(data[ny][nx] == '#') continue;
    if(data[ny][nx] != '.') {
      if(bw == '.') bw = data[ny][nx];
      else if(data[ny][nx] != bw) flag = false;
      continue;
    }
    rec(nx, ny);
  }
}

int main() {
  while(1) {
    cin >> w >> h;
    if(w == 0 && h == 0) break;
    for(int i = 0; i < h; i++) {
      for(int j = 0; j < w; j++) {
	cin >> data[i][j];
      }
    }
    int numW = 0;
    int numB = 0;
    for(int i = 0; i < h; i++) {
      for(int j = 0; j < w; j++) {
	if(data[i][j] == '.') {
	  cnt = 0;
	  bw = '.';
	  flag = true;
	  rec(j, i);
	  if(flag) {
	    if(bw == 'B') numB += cnt;
	    else if(bw == 'W') numW += cnt;
	  }
	}
      }
    }
    cout << numB << ' ' << numW << endl;
  }
  return 0;
}

Measured memory_bytes: 0
a,b,c=map(int,input().split())
d=0
if a==b==c and a%2==0:
    print(-1)
else:
    while a%2==0 and b%2==0 and c%2==0:
        a,b,c=(b+c)//2,(a+c)//2,(a+b)//2
        d+=1
    print(d)

Measured memory_bytes: 61588
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1
//{
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1;
#define cni cin

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

int n,ans;
string s;

main(){
	cin>>n>>s;
	string t;
	rep(i,n-1){
	    int tmp=0;
	    t+=s.back();
	    s.pop_back();
	    //cout<<s<<' '<<t<<endl;
	    set<char> p,q;
	    for(auto x:s)p.insert(x);
	    for(auto x:t)q.insert(x);
	    for(auto x:p)if(q.count(x))tmp++;
	    chmax(ans,tmp);
	}
	dans;
}



Measured memory_bytes: 256
import sys
input = sys.stdin.readline
li = [int(i) for i in input().split()]
A = li[0]
B = li[1]
K = li[2]
A-=K
de = 0
if A <= 0 :
    de = abs(A)
    A = 0
B -= de
if B <= 0 :
    B = 0
print(A,B)

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

int main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  if(a + b > c + d)
    cout << "Left" << endl;
  else if(a + b < c + d)
    cout  << "Right" << endl;
  else
    cout << "Balanced" <<endl;
}

Measured memory_bytes: 256
#include<stdio.h>

int dp[45];

int fib(int n){
  if(n == 1 || n == 0){
    dp[n] = 1;    
    return 1;
  }else{
    if(dp[n] != -1){
      return dp[n];
    }
    dp[n] = fib(n-1)+fib(n-2);
  }
  return dp[n];
}

int main(){
  int n,ans,i;

  for(i = 0; i < 45; i++){
    dp[i] = -1;
  }
  scanf("%d",&n);

  ans = fib(n);

  printf("%d\n",ans);
  return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
typedef long long ll;
static const int MAX=100;
int N;
ll T;      
using namespace std;
ll gcd(ll a,ll b){//最大公約数
    if(b==0)return a;
    return gcd(b,a%b);//ユーグリッドの互除法
}
ll lcm(ll a,ll b){//最小公倍数
    ll g=gcd(a,b);
    return a/g*b;
}
int main(){
    cin>>N;
    ll ans=1ll;
    for(int i=0;i<N;i++){
        cin>>T;
        ans=lcm(ans,T);
    }
    cout<<ans<<"\n";
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#define r(i,n) for(int i=0; i<n; i++)
using namespace std;
int main(void){
  int n;
  int a[110];
  int sum=0;
  cin >> n;
  r(i,n){
    cin >> a[i];
    sum+=a[i];
  }
  sort(a, a+n);

  if(sum%10==0){
  r(i,n){
    if(a[i]%10!=0){cout << sum-a[i] << endl;return 0;}
  }cout << 0 << endl;
}else{cout << sum << endl;}

  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))

int main() {
  int a,b,c,x;
  scanf("%d\n",&a);
  scanf("%d\n",&b);
  scanf("%d\n",&c);
  scanf("%d\n",&x);

  int count=0;
  int res;
  for (size_t i = 0; i <=a; i++) {
    for (size_t j = 0; j <= b; j++) {

      res=x-500*i-100*j;
      if (res>=0 &&res % 50 == 0 && res / 50 <= c) {
        count++;
      }
    }
  }
  printf("%d\n",count );
  return 0;
}


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

int main(){
  int n, x, y;
  cin >> n >> x >> y;
  vector<int> cnt(n);
  
  for(int i = 1; i < n; i++){
    for(int j = i + 1; j <= n; j++){
      int d = min(j-i, abs(x-i)+1+abs(y-j));
      cnt[d]++;
    }
  }
  for(int i = 1; i < n; i++){
    cout << cnt[i] << endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m;
    cin >> n >> m;
    vector<int> fac;
    for(int i=1;i*i<=m;++i)
    {
        if(i*i==m)
        {
            fac.push_back(i);
        }
        else if(m%i==0)
        {
            fac.push_back(i);
            fac.push_back(m/i);
        }
    }
    sort(fac.begin(),fac.end());
    for(int i=fac.size()-1;i>=0;--i)
    {
        if(m/fac[i]>=n)
        {
            cout << fac[i] << endl;
            return 0;
        }
    }

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <climits>
#include <iostream>
#include <string>
#include <utility>
#include<vector>
#include<iomanip>
#include<map>
#include <queue>
#include<cmath>
#include<cstdio>
#include<iomanip>
#include<set>
#include <bits/stdc++.h>
 
using namespace std;
using ll = long long int;
 
#define REP(i,n) for(ll i=0;i<(ll)(n);i++) //REP(i, 5) cout<<i;
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define MOD 1000000007 //10^9+7
//#define MOD 1
 
ll gcd(ll a, ll b) {
  ll tmp;
  if ( b > a) {
    tmp = a;
    a = b;
    b = tmp;
  }
  while (a % b !=0) {
    tmp = b;
    b = a % b;
    a = tmp;
  }
  return b;
}
 
const int MAX = 2000;

long long fac[MAX], finv[MAX], inv[MAX];
 
// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


void sosuu(ll n, vector<ll> &v){

  vector<ll> num(n, 0);

  FOR(i, 1, sqrt(n)){
    if(num[i]==0){
      FOR(j, 0, n/i){
        num[i+(j*i)] = 1;
      }
    }
  }
  REP(i, n){
    if(num[i]==0) v.push_back(i+1);
  }
}

ll GetDigit(ll num){
    ll digit=0;
    while(num!=0){
        num /= 10;
        digit++;
    }
    return digit;
}

ll power(ll a, ll b){
  ll ans = 1;
  if(b%2==0){
    REP(i, b/2){
      ans *= a;
      if(ans>1000000000){
        return -1;
      }
    }
    return ans * ans;
  }else{
    b = b/2;
    REP(i, b){
      ans *= a;
      if(ans>1000000000){
        return -1;
      }
    }
    return ans * ans* a;
  }
}

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main(void){
  
  char x;
  cin>>x;
  if('A'<=x && x<='Z') cout<<"A"<<endl;
  else cout<<"a" <<endl;
  return 0;
  
}

Measured memory_bytes: 3720
#include <bits/stdc++.h>
#include <cmath>
#include <iomanip>
using namespace std;
 
#define f first
#define s second
 
#define pb push_back
#define pp pop_back
#define mp make_pair
 
#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()
#define clr(a,v) memset(a, v, sizeof(a))
 
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
#define per(i, l, r) for (int i = (l); i >= (r); i--)
#define reflex ios_base::sync_with_stdio(false)
 
#define nl '\n'
#define ioi exit(0);
 
 
#define PI 3.14159265
 
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
 
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int N= (int)2e5 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
//const int mod = 1000000007;
const ll linf = (ll)1e18 + 7;
const ll limit = 2e9;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};
const int kx[] = {-1,1,2,2,1,-1,-2,-2};
const int ky[] = {2,2,1,-1,-2,-2,-1,1};
 
//const int mod = 998244353;
 
struct dsu{
	int parent[N];
	int cont;
	void make_set(int n){
		for(int i = 1; i <= n; i++)
			parent[i] = i;
		cont = n;
	}
	
	int find_set(int v){
		if(v == parent[v])
			return v;
		return find_set(parent[v]);
	}
	
	void union_sets(int a, int b){
		a = find_set(a);
		b = find_set(b);	
		if(a != b){
			parent[b] = a;
			cont--;
		}
	}
};


int main()
{	
	int r, c, n; cin>> r >> c>> n; 
	cout<< ceil(n*1.0/max(r,c));
	return 0;
}


Measured memory_bytes: 256
x, y =[int(i) for i in input().split()]
a = [1,3,5,7,8,10,12]
b = [4,6,9,11]
if (x in a) and (y in a):
  print("Yes")
elif (x in b) and (y in b):
  print("Yes")
else:
  print("No")

Measured memory_bytes: 3060
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <iostream>
using namespace std;
int main()
{
	int a, i, b;
	scanf("%d %d",&a,&b);
	if((a * b) % 2 == 1)
	{
		printf("Odd\n");
	}
	else
	{
		printf("Even\n");
	}
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

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

    int n = sc.nextInt();
    int[] d = new int[n];

    for(int i = 0; i < n; i++){
      d[i] = sc.nextInt();
    }

    Arrays.sort(d);
    
    System.out.println(d[n / 2] - d[n / 2 - 1]);
  }
}


Measured memory_bytes: 59140
H, W = map(int, input().split())
A = [[i for i in input()] for _ in range(H)]

cnt = 0
for y in range(H) :
  cnt += A[y].count('#')

y, x = 0, 0
cnt -= 1
while not (y == H - 1 and x == W - 1) :
  if x + 1 < W and A[y][x + 1] == '#' :
    cnt -= 1
    x += 1
    continue
  
  if y + 1 < H and A[y + 1][x] == '#' :
    cnt -= 1
    y += 1
    continue

  break

if cnt == 0 :
  print('Possible')
else :
  print('Impossible')

Measured memory_bytes: 38384
#include <bits/stdc++.h>
using namespace std;
using Int = long long;
int main() {
    Int N; cin >> N;
    vector<int> V(N); for (auto &v : V) cin >> v;
    cout << accumulate(begin(V), end(V), 0LL) - N * (N + 1) / 2 << endl;
    return 0;
}



Measured memory_bytes: 3200
#include <cstdio>
#include <cstring>
#include <vector>
#define MAXN 20
#define MAXS 33000
#define LL long long
using namespace std;

const LL P=1000000007;

int n,m,maxs;
int w[MAXN][MAXN];
LL f[MAXN][MAXS];
vector< pair<int,LL> > trans[MAXS];
LL g[MAXS],p2[MAXS];

void pre_gao(int x){
	for(int y=x;;y=(y-1)&x){
		LL res=1;
		int cnt=0;
		for(int i=1;i<=n;i++)
			if((1<<(i-1))&y){
				int temp=0;
				for(int j=i+1;j<=n;j++)
					if(((1<<(j-1))&x) && !((1<<(j-1))&y) && w[i][j])
						temp++;
				res=res*((1LL<<temp)-1)%P;
			}else if((1<<(i-1))&x){
				for(int j=i+1;j<=n;j++)
					if(((1<<(j-1))&y) && w[i][j])
						cnt++;
			}
		res=res*p2[cnt]%P;
		if(res) trans[x].push_back(make_pair(y,res));
		if(!y) break;
	}
	int temp=0;
	for(int i=1;i<=n;i++)
		for(int j=i+1;j<=n;j++)
			if(w[i][j] && ((1<<(i-1))&x) && ((1<<(j-1))&x))
				temp++;
	g[x]=1;
	while(temp--) g[x]=g[x]*2%P;
}

inline void update(LL &x,LL y){ x=(x+y)%P; }

int main(){
#ifdef DEBUG
	freopen("F.in","r",stdin);
#endif
	p2[0]=1;
	for(int i=1;i<MAXS;i++) p2[i]=p2[i-1]*2%P;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		w[x][y]=1;
	}
	maxs=1<<n;
	for(int i=0;i<maxs;i++) pre_gao(i);
	f[0][maxs-1]=1;
	LL ans=0;
	for(int i=0;i<n;i++)
		for(int j=0;j<maxs;j++)
			if(f[i][j]){
				for(int k=0;k<trans[j].size();k++)
					if((trans[j][k].first&3)==3)
						update(f[i+1][trans[j][k].first],f[i][j]*trans[j][k].second);
					else if((trans[j][k].first&3)==0)
						update(ans,f[i][j]*trans[j][k].second%P*g[trans[j][k].first]);
			}
	LL temp=1;
	for(int i=1;i<=m;i++) temp=temp*2%P;
	ans=(temp-ans+P)%P;
	printf("%lld\n",ans);
}


Measured memory_bytes: 120060
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        HashSet<Character> set = new HashSet<>();
        for (int i = 0; i < N; i++) {
            String s = scan.next();
            char c = s.toCharArray()[0];
            set.add(c);
        }
        if (set.size() == 3) {
            System.out.println("Three");
        } else {
            System.out.println("Four");
        }
    }
}


Measured memory_bytes: 23252
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <cmath>

using namespace std;
typedef pair<long long int, long long int> P;
typedef pair<P, long long int> PI;

vector<long long int> Pall[100001];

void solve()
{
	int N, K;
	cin >> N >> K;
	vector<int> h(N);
	for (int i = 0; i < N; ++i)
	{
		cin >> h[i];
	}
	sort(h.begin(), h.end());
	int ans = 1e9;
	for (int i = 0; i < N - K + 1; ++i)
	{
		ans = min(ans, h[i + K - 1] - h[i]);
	}
	cout << ans << endl;
}

int main()
{
	solve();
	return(0);
}

Measured memory_bytes: 2944
#include <iostream>
#include <vector>
#include <algorithm>
#include <math.h>

using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::sort;

vector<int> make_prime(int n, int p) {
	int cnt = 0;
	int number = n+1;
	vector<int> res;
	while (cnt < p) {
		bool flag = true;
		if (number == 1) {
			number++;
			continue;
		}
		for (int i = 2; i <= sqrt(number); i++) {
			if (number % i == 0) {
				flag = false;
				break;
			}
		}
		if (flag) {
			res.push_back(number);
			cnt++;
		}
		number++;
	}
	return res;
}

int matsuzaki(int n, int p) {
	int res;
	vector<int> sum;
	vector<int> prime = make_prime(n, p);
	for (int i = 0; i < p; i++) {
		for (int j = i; j < p; j++) {
			sum.push_back(prime[i] + prime[j]);
		}
	}
	sort(sum.begin(), sum.end());
	/*for (auto itr = sum.begin(); itr != sum.end(); ++itr) {
		cout << *itr << ", ";
	}
	cout << endl;
	*/
	res = sum[p-1];
	return res;
}

int main(void) {
	while (1) {
		int N, P;
		cin >> N >> P;
		if (N == -1 and P == -1) {
			break;
		}
		int res = matsuzaki(N, P);
		cout << res << endl;
	}
	return 0;
}



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

using namespace std;
 
#define MD 1000000007
typedef long long int ll;

int main(){
    int h,w,d;
    cin>>h>>w>>d;
    map<int,int> mp_h,mp_w;
    for(int i=1;i<=h;i++){
        for(int j=1;j<=w;j++){
            int tmp;
            cin>>tmp;
            mp_h[tmp]=i;mp_w[tmp]=j;//各値のx,y座標を管理
        }
    }
    
    vector<int> dis(h*w*1);
    for(int i=h*w;i>=1;i--){//DPモドキ．末尾から埋めてく
        if((i+d)>h*w){
            dis[i]=0;
        }else{
            dis[i]=dis[i+d]+abs(mp_h[i]-mp_h[i+d])+abs(mp_w[i]-mp_w[i+d]);
        }
    }
    
    int q;
    cin>>q;
    vector<int> ans(q);
    for(int i=0;i<q;i++){
        int l,r;
        cin>>l>>r;
        ans[i]=dis[l]-dis[r];
    }
    for(int i=0;i<q;i++){
        cout<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 10368
// Practice 40 hours a day to become Ling Ling
// Code by Nguyen Huu Lam
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

typedef long long LL;

#define y0 Sword_Art_Online
#define y1 Your_lie_in_April
#define yn Darling_in_the_Franxx
#define tm Plastic_Memories
#define lr Charlotte
#define norm Weathering_with_you
#define left Violet_Evergarden
#define have Date_a_live
#define ends Your_name
#define prev Five_centimeters_per_second
#define hash Silent_voice
#define endl "\n"

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

LL Rand(LL l, LL h){
    return uniform_int_distribution<LL>(l, h)(rng);
}

template <typename T> void read(T &t){
    t = 0; char ch = getchar(); int f = 1;
    while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
    do { (t *= 10) += ch - '0'; ch = getchar(); } while (isdigit(ch)); t *= f;
}

const LL MaxN = 1 + 1e5;

LL n, a[MaxN];
string s;

void InOut(){
    #define TASK "ABC"
    freopen(TASK".inp","r",stdin);
    freopen(TASK".out","w",stdout);
}

int main(){
    // InOut();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> s;
    for(int i = 0 ; i < s.length(); ++i)
    if(s[i] == '?') s[i] = 'D';
    cout << s << endl;

    return 0;
}

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

int main() {
  int N;
  string S[200000];
  cin >> N;

  for (int i = 0; i < N; ++i) cin >> S[i];

  sort(S, S + N); //Sをソート

  int counter = 1;
  bool res = true;
  for (int i = 1; i < N; ++i) {
    if (S[i] != S[i - 1]) ++counter;
  }
  cout << counter << endl;
}

Measured memory_bytes: 9896
#include <stdio.h>
 
int main( void )
{
	char s[1+1];
	scanf("%s", s ) ;
	printf( s[0] == 'A' ? "T\n" : (s[0] == 'C' ? "G\n" : (s[0] == 'G' ? "C\n" : "A\n"))) ;
	return 0 ;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> // Common file
#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define pb push_back
#define ll long long
#define all(x) x.begin() , x.end()
#define mod(x,m) ((x%m + m )%m)
using namespace std;
using namespace __gnu_pbds;
void OJ();

template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag,
        tree_order_statistics_node_update>;

#define ld long double

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

    ld tot = 1e18 , res = 1;
    int n; cin >> n; vector<ld> vec(n);
    for ( ld& i : vec ) cin >> i , res *= (i == 0 ? 0 : 1);

    if ( res == 0 )
        return cout << 0 , 0;

    for ( ld i : vec ){
        ld div = tot / res;
        if ( i > div )
            return cout << -1 , 0;
        res *= i;
    }
    cout << fixed << setprecision(0) << res;
    return 0;
}

void OJ(){
#ifndef ONLINE_JUDGE
    freopen( "C:\\Users\\ehab\\Desktop\\Code Forces\\CF\\in.txt" , "r" , stdin  );
    // freopen( "C:\\Users\\ehab\\Desktop\\Code Forces\\CF\\out.txt", "w" , stdout );
#endif // ONLINE_JUDGE
}
/*ll binEXP( ll x , ll pw , ll MOD )
{ ll res=1; while(pw>0){ pw%2 ? res *= x : 0; x *= x; x%=MOD; pw /= 2; res%= MOD; } return res%=MOD; }*/

Measured memory_bytes: 4764
import java.util.Scanner;

public class Main {
	static Scanner sc = new Scanner(System.in);
	static int N, K;

	public static void main(String[] args) throws Exception {
		N = sc.nextInt();
		K = sc.nextInt();
		sc.nextLine();
		int[][] c = new int[K][N / 2];
		boolean[][] f = new boolean[K][N];
		int[] count = new int[N];
		for (int i = 0; i < K; ++i) {
			String[] line = sc.nextLine().split(" ");
			for (int j = 0; j < N / 2; ++j) {
				c[i][j] = Integer.parseInt(line[j]) - 1;
				count[c[i][j]]++;
				f[i][c[i][j]] = true;
			}
		}
		int[] ans = new int[N];
		int[] used = new int[K];
		for (int i = 0; i < 3 * N / 8; ++i) {
			int idx = 0;
			int max = 0;
			for (int j = 0; j < N; ++j) {
				if (ans[j] != 0) {
					continue;
				}
				if (max < count[j]) {
					idx = j;
					max = count[j];
				}
			}
//			System.out.println(idx + " " + max);
			ans[idx] = 1;
			for (int j = 0; j < K; ++j) {
				if (f[j][idx]) {
					used[j]++;
					if (used[j] == N / 8) {
						for (int k = 0; k < N / 2; ++k) {
							count[c[j][k]]--;
						}
					}
				}
			}
		}
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < N; ++i) {
			sb.append(ans[i]);
		}
		System.out.println(sb.toString());
	}

}

Measured memory_bytes: 14000
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;
#define rep( i, n, m ) for(int i = ( n ); i < ( m ); i++)
#define rep_d( i, n, m ) for(int i = ( n ) - 1; i >= ( m ); i--)
#define sort_asc( X ) sort(( X ).begin(), ( X ).end())
#define sort_desc( X ) sort(( X ).begin(), ( X ).end(), greater <>())

template <class T> bool chmax( T& a, T b );
template <class T> bool chmin( T& a, T b );
int* eratosthenes( int N );
bool bit_search( int pattern, int N );
template <class T> void cumulative_sum( T array, size_t N );

const ll INF = 1LL << 60;
const int k_mod = 1e9 + 7;

typedef struct {
	vector <int> to;
	int cost;
	int dist;
} edge;
int main( void ){
	edge E;
	int N, Q;
	cin >> N >> Q;
	vector <edge> array( N );
	rep( i, 0, N - 1 ){
		int a, b;
		cin >> a  >> b;
		a--;
		b--;
		array[ a ].to.push_back( b );
		array[ b ].to.push_back( a );
		array[ a ].cost = 0;
	}
	rep( i, 0, Q ){
		int e, cost;
		cin >> e >> cost;
		array[ e - 1 ].cost += cost;
	}
	array[ 0 ].dist = 0;
	rep(i, 1, N)
		array[i].dist = -1;
	stack <pair<int, int>> dfs;
	dfs.push( make_pair(0, 1) );
	while(!dfs.empty()){
		pair<int, int> e = dfs.top(); dfs.pop();
		for(auto to:array[e.first].to){
			if (array[to].dist != -1)
				continue;
			dfs.push(make_pair(to, e.second+1));
			array[to].dist = e.second;
		}
	}
	stack <int> st;
	st.push( 0 );
	while(!st.empty()){
		int e = st.top(); st.pop();
		for(auto to: array[ e ].to){
			if (array[e].dist > array[to].dist)
				continue;
			st.push(to);
			array[to].cost += array[e].cost;
		}
	}
	rep(i,0,N){
		cout << array[i].cost << " ";
	}
	cout << endl;
}

int* eratosthenes( int N ){
	int* prime_array = new int[ N + 1 ];
	int lim = N;
	prime_array[ 0 ] = 0;
	prime_array[ 1 ] = 0;
	rep( i, 2, N + 1 ){
		prime_array[ i ] = 1;
	}
	rep( i, 2, lim ){
		if (prime_array[ i ] == 0)
			continue;
		lim = N / i;
		for(int j = i * 2; j < N + 1; j += i){
			prime_array[ j ] = 0;
		}
	}
	return prime_array;
}
template <class T> void cumulative_sum( T array, size_t N ) {
	rep( i, 1, N + 1 ){
		array[ i ] += array[ i - 1 ];
	}
}
template <class T> bool chmax( T& a, T b ) {
	if (a < b){
		a = b; return true;
	}
	return false;
}
template <class T> bool chmin( T& a, T b ) {
	if (a > b){
		a = b; return true;
	}
	return false;
}
bool bit_search( int pattern, int N ){
	int cnt = 0;
	rep( bit, 0, N ){
		if (pattern & ( 1 << bit )){
			cnt++;
		}
	}
	return true;
}


Measured memory_bytes: 17140
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<n; ++i)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
using namespace std;
using ll = int64_t;
using ld = long double;
using P = pair<int, int>;
using vs = vector<string>;
using vi = vector<int>;
using vvi = vector<vi>;
const int INF = 100010001;
const ll LINF = (ll)INF*INF*10;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    string s;
    cin >> s;

    int ans = 0;
    vi Z;
    rep(ii, n-1) {
        Z.resize(n-ii);
        Z[0] = n-ii;
        int i = 1, j = 0;
        while(i < n-ii) {
            while(i+j < n-ii and s[j] == s[i+j]) ++j;
            Z[i] = j;
            ans = max(ans, min(i, j));

            if(!j) {
                ++i;
                continue;
            }
            int k = 1;
            while(k < j and k+Z[k] < j) {
                Z[i+k] = Z[k];
                ans = max(ans, min(i+k, Z[k]));
                k++;
            }
            i += k;
            j -= k;
        }
        s = s.substr(1);
    }

    cout << ans << endl;
}

Measured memory_bytes: 384
import math
def lcm(a,b):
    A,B=a,b
    while b!=0:
        a,b=b,a%b
    return A*B//a
 
def count(a,b,c):
    return b//c-(a-1)//c
 
A,B,C,D=map(int,input().split())
C_count = count(A,B,C)
D_count = count(A,B,D)
CD_count = count(A,B,lcm(C,D))
ans = B - (A - 1) - (C_count + D_count - CD_count)
print("{}".format(ans))

Measured memory_bytes: 3064
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Mar  1 19:29:34 2019

@author: nakamuratakayuki
"""
S = input()
S1 = int(S[0:2])
S2 = int(S[2:4])

ans0 = 0
if 1 <= S2 <= 12:
    ans0 += 1
if 1 <= S1 <= 12:
    ans0 += 2
    
ans =''
if ans0 == 0:
    ans = 'NA'
if ans0 == 1:
    ans = 'YYMM'
if ans0 == 2:
    ans = 'MMYY'
if ans0 == 3:
    ans = 'AMBIGUOUS'
    
print(ans)

Measured memory_bytes: 3064
#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def Y():
    print("Yes")


def N():
    print("No")


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


if "7" in S():
    Y()
else:
    N()


Measured memory_bytes: 9060
import java.util.*;
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner scn = new Scanner(System.in);
		String s = scn.next();
      	int check = 0;
		if (s.charAt(0) != 'A') {
			check = 1;
		}
      	if (s.charAt(1) == 'C') {
			check = 1;
		}
		int count =0;
		for (int i=2;i<s.length()-1; ++i) {
			if (s.charAt(i)=='C') {
				count = count + 1;
			}
		}
		if (count != 1) {
			check = 1;
		}
		for (int i=1;i<s.length(); ++i) {
			if (s.charAt(i)!='C' && (s.charAt(i)<'a' || s.charAt(i)>'z')) {
				check = 1;
			}
		}
      if(check == 0){
		System.out.println("AC");
      }else{
        System.out.println("WA");
      }
	}
}


Measured memory_bytes: 35544
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Solver {
    Scanner sc = new Scanner();

    public void Solve() {
        var N = sc.nextInt();
        var A = sc.ArrayLong(N);
        var dp = new long[N + 1, 2];
        for (int i = 0; i < N; i++) {
            if (i == 0) {
                dp[i + 1, 0] = A[i];
                dp[i + 1, 1] = A[i] * -1;
            } else {
                dp[i + 1, 0] = Math.Max(dp[i, 0] + A[i], dp[i, 1] - A[i]);
                dp[i + 1, 1] = Math.Max(dp[i, 0] - A[i], dp[i, 1] + A[i]);
            }
        }
        WriteLine(dp[N, 0]);
    }

}

class Scanner {
    string[] s;
    int i;

    char[] cs = new char[] { ' ' };

    public Scanner() {
        s = new string[0];
        i = 0;
    }

    public string next() {
        if (i < s.Length) return s[i++];
        string st = Console.ReadLine();
        while (st == "") st = Console.ReadLine();
        s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
        if (s.Length == 0) return next();
        i = 0;
        return s[i++];
    }

    public int nextInt() {
        return int.Parse(next());
    }
    public int[] ArrayInt(int N, int add = 0) {
        int[] Array = new int[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextInt() + add;
        }
        return Array;
    }

    public long nextLong() {
        return long.Parse(next());
    }

    public long[] ArrayLong(int N, long add = 0) {
        long[] Array = new long[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextLong() + add;
        }
        return Array;
    }

    public double nextDouble() {
        return double.Parse(next());
    }

    public double[] ArrayDouble(int N, double add = 0) {
        double[] Array = new double[N];
        for (int i = 0; i < N; i++) {
            Array[i] = nextDouble() + add;
        }
        return Array;
    }
}

class Program {
    static void Main(string[] args) {
        Solver s = new Solver();
        s.Solve();
    }
}


Measured memory_bytes: 29276
import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    private static final int INF = (int) 1e9 + 5;

    private static void solve(Scanner scanner, PrintWriter writer) {
        int n = scanner.nextInt();
        int[] stones = new int[n];
        for (int i = 0; i < n; i++) {
            stones[i] = scanner.nextInt();
        }


        int[] dp = new int[n];
        for (int i = 1; i < n; i++) {
            dp[i] = Math.min(dp[i - 1] + Math.abs(stones[i] - stones[i - 1]), (i - 2 < 0) ? Integer.MAX_VALUE : dp[i - 2] + Math.abs(stones[i] - stones[i - 2]));
        }

        writer.println(dp[n - 1]);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        PrintWriter writer = new PrintWriter(System.out);
        solve(scanner, writer);
        scanner.close();
        writer.close();
    }
}


Measured memory_bytes: 51084
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e5 + 7;

vector <string> ve;
int main()
{
    ios::sync_with_stdio(0);
    int n;
    cin>>n;
    string s;
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        cin>>s;
        sort(s.begin(), s.end());
        ve.push_back(s);
    }
    sort(ve.begin(),ve.end());
    int x = 1;
    for(int i = 1; i < n; i++)
    {
        if(ve[i] == ve[i-1])
        {
            ans += x;
            x++;
        }
        else x = 1;
    }
    cout<<ans<<endl;

    return 0;
}



Measured memory_bytes: 5876
var n,m:longint;
    i,j,k:longint;
    a:array[0..10,0..10]of longint;
    x:longint;
    ans:longint;
begin
  readln(n,m);
  for i:=0 to 9 do
  begin
    for j:=0 to 9 do
    read(a[i,j]);
    readln;
  end;
  for k:=0 to 9 do
  for i:=0 to 9 do
  for j:=0 to 9 do
  if a[i,j]>a[i,k]+a[k,j] then a[i,j]:=a[i,k]+a[k,j];
  for i:=1 to n*m do
  begin
    read(x);
    if x<>-1 then inc(ans,a[x,1]);
  end;
  writeln(ans);
end.

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
int main(void)
{
	int n;
	cin>>n;
	if(n%10==3)
	cout<<"bon\n";
	else if(n%10==0 || n%10==1 || n%10==6 || n%10==8)
	cout<<"pon\n";
	else
	cout<<"hon\n";
}

Measured memory_bytes: 3636
n, q = map(int, input().split())
s = input()
qs = [map(int, input().split()) for _ in range(q)]

accum = [0 for _ in range(n + 1)]

for i in range(1, n):
    accum[i + 1] = accum[i]
    if s[i - 1] == 'A' and s[i] == 'C':
        accum[i + 1] += 1

for (l, r) in qs:
    print(accum[r] - accum[l])


Measured memory_bytes: 52080
#include <bits/stdc++.h>
#define rep(i, a) for (int i = (int)0; i < (int)a; ++i)
#define rrep(i, a) for (int i = (int)a - 1; i >= 0; --i)
#define REP(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define RREP(i, a, b) for (int i = (int)a - 1; i >= b; --i)
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define popcount __builtin_popcount
using ll = long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 60;

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

ll gcd(ll n, ll m)
{
	ll tmp;
	while (m != 0)
	{
		tmp = n % m;
		n = m;
		m = tmp;
	}
	return n;
}

ll lcm(ll n, ll m)
{
	return abs(n) / gcd(n, m) * abs(m); //gl=xy
}

using namespace std;

//高速な素因数分解O(logN)
template<typename T>
vector<T> sieve(T n){//n以下の整数について最小の素因数を調べる
    vector<T>prime(n+1);
		for(int i=0;i<=n;++i)prime[i]=i;
    for(int i=2;i*i<=n;i++){
        if(prime[i]<i)continue;
				for(int j=i*i;j<=n;j+=i){
					if(prime[j]>=i)prime[j]=i;
				}
    }
    return prime;
}

template<typename T>
vector<T> osa_k(T n,const vector<T>& min_factor){//min_factorはsieveで求めた配列を使う
  vector<T> ret;
  while(n>1){
		if(ret.empty()||min_factor[n]!=ret.back())ret.push_back(min_factor[n]);
		n/=min_factor[n];
	}
  return ret;
}

void solve()
{
	ll n;
	cin>>n;
	ll nn=n;
	vector<int>v;
	for(ll i=2;i*i<=n;++i){
		if(nn%i==0)v.pb(i);
		while(nn%i==0)nn/=i;
	}
	if(nn!=1)v.pb(nn);
	int m=v.size();
	ll ans=0;
	rep(bit,1<<m){
		int num=popcount(bit);
		if(num==0)continue;
		ll val=1;
		rep(i,m){
			if(bit&(1<<i)){
				val*=v[i];
			}
		}
		ans+=(ll)pow(-1,num-1)*(n/val);
	}
	ans=n-ans;
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout << fixed << setprecision(15);
	solve();
	return 0;
}



Measured memory_bytes: 3368