akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>

int main (void) {
    int a, b;
    scanf("%d%d", &a, &b);

    if ( a + b > a - b  ) {
        if ( a + b > a * b ) {
            printf("%d\n", a + b);
        }
        else {
            printf("%d\n", a * b);
        }
    }
    else {
        if ( a - b > a * b ) {
            printf("%d\n", a - b);
        }
        else {
            printf("%d\n", a * b);
        }
    }
    return 0;
}

Measured memory_bytes: 128
n,k=map(int,input().split())
a=[int(i) for i in input().split()]
w=[1]
x=set([1])
for i in range(k):
    t=a[w[-1]-1]
    if t in x: break
    x.add(t)
    w.append(t)
p=w.index(t)
k-=p
loop=len(w)-p
print(w[p+k%loop])

Measured memory_bytes: 121944
## coding: UTF-8
from decimal import *
from itertools import permutations, combinations,combinations_with_replacement,product
import math
from math import gcd

N = int(input())
S = input()

r_list = []
g_list = []
b_list = []

for i in range(N):
    if(S[i] == 'R'):
        r_list.append(i)
    elif(S[i] == 'G'):
        g_list.append(i)
    else:
        b_list.append(i)

#print('r:{}, g:{}, b:{}'.format(r_list, g_list, b_list))

R_count = len(r_list)
G_count = len(g_list)
B_count = len(b_list)
#print(R_count * G_count * B_count)

b_num_list = [0 for i in range(N)]
for i in range(B_count):
    b_num_list[b_list[i]] += 1
#print('b_num_list:{}'.format(b_num_list))
    

counter = R_count * G_count * B_count
NG_list = []
for i in range(R_count):
    for j in range(G_count):
        r = r_list[i]
        g = g_list[j]
        hit_count = 0
        #if( (g+g-r) in b_list):
        #print('g+g+r:{}'.format(g+g-r))
        if(g+g-r >= 0 and g+g-r <= N-1): #and b_num_list[g+g-r] == 1)
            #print('b_num_list[g+g-r]:{}'.format(b_num_list[g+g-r]))
            if(b_num_list[g+g-r] == 1):
                hit_count += 1
        #if( (g+r)%2 == 0 and ((g+r)/2) in b_list ):
        if( (g+r)%2 == 0 and b_num_list[int((g+r)/2)] == 1):
            hit_count+=1
        #if( (r-g+r) in b_list):
        if(r+r-g >= 0 and r+r-g <= N-1 ):#and b_num_list[r+r-g] == 1):
            if(b_num_list[r+r-g] == 1):
                hit_count+=1
        counter -= hit_count
print(counter)
   


Measured memory_bytes: 10092
use std::io::*;

fn main() {
    let mut w = String::new();
    let mut s = String::new();
    stdin().read_line(&mut w).unwrap();
    let w = w.trim().to_lowercase();
    stdin().read_to_string(&mut s).unwrap();
    println!("{}",
        s.split_whitespace().fold(0, |a,e| {
            if e.to_lowercase() == w { a+1 } else { a }
        }));
}



Measured memory_bytes: 5052
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int> P;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 1000000000
#define LLINF 1000000000000000ll
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define all(x) (x).begin(),(x).end()
#define sq(x) ((x)*(x))
#define rep(i,n) for(int (i)=0;(i)<(int)(n);(i)++)
#define repn(i,a,n) for(int (i)=(a);(i)<(int)(n);(i)++)
#define EQ(a,b) (abs((a)-(b))<eps)
template<class T> void chmin(T& a,const T& b){if(a>b)a=b;}
template<class T> void chmax(T& a,const T& b){if(a<b)a=b;}
int N;
ll x;
ll a[2010];
ll b[2010][2010];
int main(){
	cin >> N >> x;
	for(int i=0;i<N;i++)cin >> a[i];
	ll ans = LLINF;
	for(int i=0;i<N;i++)b[i][0]=a[i];
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			b[j][i+1]=min(b[j][i],a[(j+i+1)%N]);
		}
	}
	for(int i=0;i<N;i++){
		ll ret = x*i;
		for(int j=0;j<N;j++){
			ret += b[j][i];
		}
		ans = min(ans,ret);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 31744
#include<bits/stdc++.h> 
//#define <- プログラムの文字列を置換する
//typedef <- 新しい型に名前を付けるためのキーワード

using namespace std;

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

const long long MOD = 1e9 + 7;
const long long INF = 1e15;
const int INF_INT = 1e9;

template<class TYPE>
struct edge{
    TYPE to,cost; 
    edge(TYPE t,TYPE c){
        to = t;
        cost = c;
    }
};

int main(){
    int a,b;
    cin >> a >> b;
    int ans = max(a+b,max(a-b,a*b));
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3572
#include <iostream>
#include <string>
#include <map>
#include <queue>
#include <algorithm>
#include <vector>
#include <math.h>
#include <bitset>
#include <cmath>
#include <set>
#include <queue>
#include <stack>

typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define rep_r(i,s,n)for(ll i = n-1;i>=s;i--)
using namespace std;
static const ll MOD = 1e9 + 7;
static const ll INF = 1e25;
static const ll MAX_N = 100001;


ll p[8];
ll q[8];
int main() {
	ll n; cin >> n;
	rep(i, 0, n)cin >> p[i];
	rep(i, 0, n)cin >> q[i];

	vector<int> v;

	rep(i, 0, n)v.push_back(i+1);

	int a = 0;
	int b = 0;
	int k = 0;
	do {
		k++;

		//p
		bool p_match = true;
		rep(i, 0, n) p_match &= p[i] == v[i];
		if(p_match)a = k;

		bool q_match = true;
		rep(i, 0, n) q_match &= q[i] == v[i];
		if (q_match) b = k;
	} while (next_permutation(v.begin(),v.end()));


	cout << abs(a - b) << endl;

	return 0;
}



Measured memory_bytes: 256
#![allow(unused_imports)]

use text_io::*;
use proconio::*;
use std::collections::*;
use itertools::Itertools;
use std::process::exit;
use std::cmp::*;
use num::*;
use num::integer::Roots;

fn main() {
    input! {
    a:String,
    }
    let a=a.chars().collect_vec();
    let mut v:Vec<char>=Vec::new();
    for i in 0..a.len() {
        if a[i]=='?' {v.push('D')}
        else { v.push(a[i]) }
    }
    let v:String=v.iter().collect();
    println!("{}",v)
}

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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> P;
constexpr double EPS = 1e-12;
constexpr int INF = numeric_limits<int>::max()/2;
constexpr int MOD = 1e9+7;

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

    string s,t;cin>>s>>t;
    string res="";
    for(int i=0;i<(int)s.length();i++){
        res += s[i];
        if(i<(int)t.length()) res += t[i];
    }
    cout<<res<<endl;
}


Measured memory_bytes: 256
N=int(input())
p=list(map(int,input().split()))

sort_p=sorted(p)
cnt=0

#i,jにpとソートしたpを代入して比較
for i,j in zip(p,sort_p):
  if i != j:
    cnt += 1

if cnt <= 2:
  print("YES")
else:
  print("NO")

Measured memory_bytes: 3060
def main():
    n = int(input())
    import numpy as np
    ans = np.zeros((10,10))
    for i in range(1,n+1):
        h,t = str(i)[0],str(i)[-1]
        ans[int(h)-1][int(t)-1]+=1
    s = 0
    for i in range(10):
        for j in range(10):
            s += ans[i][j]*ans[j][i]

    print(int(s))
if __name__ == "__main__":
    main()

Measured memory_bytes: 12884
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int N = 1e6 + 5;
ll MOD = 1e9 + 7 ;
ll fact[N] , inv[N] ;
ll ways[N] ;

ll BigMod (ll b , ll p) {
    if (p == 0) return 1LL ;
    ll t = BigMod(b,p/2) ;
    t = (t*t)%MOD ;
    if (p&1) return (t*b)%MOD ;
    return t ;
}


int main () {

    fact[0] = inv[0] = 1;
    for (ll i = 1; i < N ; i++) {
        fact[i] = (fact[i-1]*i)%MOD ;
        inv[i] = BigMod(fact[i],MOD-2) ;
    }
    ll n ;
    cin >> n ;
    ll ans = 0 ;
    for (ll K = (n+1)/2 ; K < n ; K++) {
        ll cur = ( fact[K-1]*fact[K] ) % MOD ;
        cur *= inv[2*K-n] ;
        cur %= MOD ;
        ways[K] = cur ;
    }
    ll subs = 0 ;
    for (ll i = (n+1)/2 ; i < n ; i++) {
        ll cur_way = ways[i] - subs ;
        cur_way %= MOD ;
        subs += cur_way ; subs %= MOD ;
        ll cur = cur_way*i ;
        cur %= MOD ;
        ans += cur ;
        ans %= MOD ;
    }
    ans += MOD ;
    ans %= MOD ;
    cout << ans ;
}


Measured memory_bytes: 21632
s = input()
i = len(s) - 1
while i > 0:
    exist = False
    if (s[i] == "m" and s[i - 4:i + 1] == "dream") or (s[i] == "e" and s[i - 4:i + 1] == "erase"):
        exist = True
        i -= 5
    elif s[i] == "r":
        if s[i - 6:i + 1] == "dreamer":
            i -= 7
            exist = True
        elif s[i - 5:i + 1] == "eraser":
            i -= 6
            exist = True
    if exist == False:
        break
if exist:
    print("YES")
else:
    print("NO")

Measured memory_bytes: 3188
#include <iostream>
#include <array>
#include <vector>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef vector<LL> VEC;
typedef vector<VEC> VVEC;
typedef  pair<LL,LL> P;


const LL INF=1<<30;
const LL MOD=1000000007;




int main(){
    LL n;
    string s;
    cin>>n>>s;
    if(n==1)cout<<1<<endl;
    else{
    LL suu[26]={0};
    for(int i=0;i<n;++i){
        suu[s[i]-'a']++;
    }
    for(int i=0;i<26;++i){
        suu[i]++;
    }
    LL ans=1;
    for(int i=0;i<26;++i){
        (ans*=suu[i])%=MOD;
    }
    ans--;
    ans%=MOD;
    cout<<ans<<endl;
    }
}



Measured memory_bytes: 512
n = int(input())
a = list(map(int, input().split()))
b = [0 for _ in range(n)]
c = []

for i in range(n,0,-1):
    tmp = sum(b[i-1::i])
    if tmp%2!=a[i-1]:
        b[i-1] = 1
        c.append(str(i))
        
print(len(c))
if len(c)!=0:
    print(" ".join(c))


Measured memory_bytes: 17224
from heapq import*
I=float("inf")
def m():
 n=int(input())
 A=[]
 for _ in[0]*n:
  e=list(map(int,input().split()))
  A+=[zip(e[2::2],e[3::2])]
 d=[0]+[I]*n
 H=[(0,0)]
 while H:
  u=heappop(H)[1]
  for v,c in A[u]:
   t=d[u]+c
   if d[v]>t:
    d[v]=t
    heappush(H,(t,v))
 print('\n'.join(f'{i} {d[i]}'for i in range(n)))
m()


Measured memory_bytes: 40088
import sys


def resolve(in_):
    n = int(next(in_))
    c = next(in_).strip()

    ans = 0
    left = 0
    right = len(c) - 1
    while left < right:
        if c[left] == 'R':
            left += 1
            continue
        if c[right] == 'W':
            right -= 1
            continue
        left += 1
        right -= 1
        ans += 1

    return ans


def main():
    answer = resolve(sys.stdin)
    print(answer)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9240
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
 
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
 
#define start_routine() int begtime = clock();
#define end_routine() int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0
#define speed() cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(false)
// #define exit(a, b) return cout << a, b;
 
// debugger
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cout << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#define debug(stuff) cout << #stuff << ": " << stuff <<endl
#define debugc(stuff) cout << #stuff << ": "; for(auto x: stuff) cout << x << " "; cout << endl;
// 
 
#define loop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(), v.end() 
 
#define print(stuff) cout << stuff << endl
#define printc(stuff) for(auto x: stuff) cout << x << " "; cout << endl;
#define printPrec(stuff) cout << fixed << setprecision(15) << stuff << endl;
#define len length
#define ret0 return 0
#define ret return 
 
 
#define ll long long
#define ld long double
#define fi first
#define endl '\n'
#define se second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define fill(ar, x) memset(ar, x, sizeof ar)
 
#define vl vector<ll> 
#define sl set<ll>
#define pll pair<ll, ll>
#define mll map<ll, ll> 
#define pq priority_queue<ll>
 
// typedef tree<ll,null_type,less<ll>,rb_tree_tag,
// tree_order_statistics_node_update> indexed_set;
 
#define inf (long long int) 1e18
#define eps 0.000001
#define mod 1000000007
#define mod1 998244353
#define MAXN (ll)2e5+5
 
void solve(){
    ll n, k, q;
    cin>>n>>k>>q;
    ll f[n+1] = {0};
    for(ll i=0; i<q; i++){
        ll x;
        cin>>x;
        f[x]++;
    }
    ll p[n+1];
    loop(i,1,n+1){
        p[i] = k - (q-f[i]);
    }
    loop(i,1,n+1){
        if(p[i] > 0){
            print("Yes");
        }
        else print("No");
    }
}
 
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
   
    ll t = 1;
    // cin>>t;
    while(t--){
        solve();
    }

}


Measured memory_bytes: 2176
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<utility>
#include<algorithm>
#include<cstdio>
#include<iomanip>
#include<queue>
#include<stack>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)

using namespace std;



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

    ll K, T;
    cin >> K >> T;
    vector<ll> a(T);
    Rep (i, T) {
        cin >> a[i];
    }

    sort(a.begin(), a.end(), greater<ll>());
    ll s = 0;
    for (ll i = 1; i < T; i++) {
        s += a[i];
    }

    cout << max(ll(0), a[0] - s - 1) << "\n";
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>	
#include<map>
#include<set>
#include<utility>
#include<cmath>
#include<cstring>
#include<queue>
#include<stack>
#include<cstdio>
#include<sstream>
#include<iomanip>
#include<assert.h>
#include<ctime>
#include<cstdlib>
#include<numeric>
#include<typeinfo>
#include<cstdio>
#include<cctype>
#include<list>
using namespace std;
typedef long long ll;
#define loop(i,a,b) for(i=a;i<b;i++)
#define rloop(i,a,b) for(i=a;i>=b;i--)
const int inf=1e8;
const ll INF=1e16;
#define MOD 1000000007
#define mod 1000000009

 
int main(){
	int i,n,q,j;
	cin>>n;
	vector<int> s(n+1);
	loop(i,0,n){
		cin>>s[i];
	}
	cin>>q;
	int sum=0;
	loop(i,0,q){
		int t;
		cin>>t;
		s[n]=t;
		j=0;
		while(s[j]!=s[n]){
			j++;
		}
		if(j!=n){
			sum++;
		}
	}
	cout<<sum<<endl;
}

Measured memory_bytes: 3072
#include<iostream>
#include<string.h>
#include<cstdio>
#include<algorithm>
#include<stack>
#include<queue>
#include<vector>
#include<cmath>
#include<utility>
#define ll long long int
#define ld long double
#define INF 1000000000
#define EPS 0.0000000001
#define rep(i,n) for(i=0;i<n;i++)
using namespace std;
typedef pair<int, int> P;

string str;

int main()
{
  int n,i,j,k;
  cin>>n;
  rep(i,n){
    int out=0;
    int score=0;
    bool first=false;
    bool second=false;
    bool third=false;

    while(1){
      cin>>str;
      if(str=="OUT"){
	out++;
	if(out==3)break;
      }
      if(str=="HIT"){
	if(first){
	  if(second){
	    if(third)
	      score++;
	    else
	      third=true;
	  }
	  else
	    second=true;
	}
	else
	  first=true;
      }
      if(str=="HOMERUN"){
	score++;
	if(first){
	  first=false;
	  score++;
	}
	if(second){
	  second=false;
	  score++;
	}
	if(third){
	  third=false;
	  score++;
	}
      }
    }	

    cout<<score<<endl;
  }
}

Measured memory_bytes: 1208
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rep2(j,n) for(int j = 0; j < (n); ++j)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define rng(a) a.begin(),a.end()
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define limit(x,l,r) max(l,min(x,r))
#define lims(x,l,r) (x = max(l,min(x,r)))
#define isin(x,l,r) ((l) <= (x) && (x) < (r))
#define pb push_back
#define sz(x) (int)(x).size()
#define pcnt __builtin_popcountll
#define uni(x) x.erase(unique(rng(x)),x.end())
#define snuke srand((unsigned)clock()+(unsigned)time(NULL));
#define show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
template<typename T>inline istream& operator>>(istream&i,v(T)&v)
{rep(j,sz(v))i>>v[j];return i;}
template<typename T>string join(const v(T)&v)
{stringstream s;rep(i,sz(v))s<<' '<<v[i];return s.str().substr(1);}
template<typename T>inline ostream& operator<<(ostream&o,const v(T)&v)
{if(sz(v))o<<join(v);return o;}
template<typename T1,typename T2>inline istream& operator>>(istream&i,pair<T1,T2>&v)
{return i>>v.fi>>v.se;}
template<typename T1,typename T2>inline ostream& operator<<(ostream&o,const pair<T1,T2>&v)
{return o<<v.fi<<","<<v.se;}
template<typename T>inline ll suma(const v(T)& a) { ll res(0); for (auto&& x : a) res += x; return res;}
const double eps = 1e-10;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}
const int MX = 200005;

int main() {
  double T,X;
  cin >> T >> X;
  cout << T / X << endl;
  return 0;
}

Measured memory_bytes: 256
from collections import deque
N=int(input())
A=[list(map(int,input().split())) for i in range(N)]
B=[list(map(int,input().split())) for i in range(N)]
V=N*2+2
G=[[] for i in range(V)]
L=[0]*V
I=[0]*V
INF=10**15
def ae(fr,to,ca):
  global G
  G[fr].append([to,ca,len(G[to])])
  G[to].append([fr,0,len(G[fr])-1])

def bfs(s):
  global INF,L,V,G
  L=[-1]*V
  Q=deque()
  L[s]=0
  Q.append(s)
  while(len(Q)):
    x=Q.popleft()
    for i in range(len(G[x])):
      if G[x][i][1]>0 and L[G[x][i][0]]<0:
        L[G[x][i][0]]=L[x]+1
        Q.append(G[x][i][0]) 

def dfs(v,t,f):
  global I,G,V
  if v==t:
    return f
  for i in range(I[v],len(G[v])):
    if G[v][i][1]>0 and L[v]<L[G[v][i][0]]:
      d=dfs(G[v][i][0],t,min(f,G[v][i][1]))
      if d>0:
        G[v][i][1]-=d
        G[G[v][i][0]][G[v][i][2]][1]+=d
        return d
    I[v]+=1
  return 0

def mf(s,t):
  global L,I,INF,V
  fl=0
  while(True):
    bfs(s)
    if L[t]<0:
      break
    I=[0]*V
    f=0
    while(True):
      f=dfs(s,t,INF)
      if f<=0:
        break
      fl+=f
  return fl

for i in range(N):
  ae(0,i+1,1)
  ae(N+i+1,N*2+1,1)
  for j in range(N):
    if A[i][0]<B[j][0] and A[i][1]<B[j][1]:
      ae(i+1,N+j+1,1)
print(mf(0,N*2+1))

Measured memory_bytes: 75928
// review
#include <iostream>
#include <cmath>
using namespace std;

typedef long long ll;
const int MAXN = 100010;
ll n;

int numOfDigits(ll v) {
  int cnt = 0;
  while (v > 0) {
    v /= 10;
    cnt++;
  }
  return cnt;
}

void solve() {
  int val = 10000;
  for (ll i=1;i<=sqrt(n);i++) {
    if (n % i == 0) {
      val = min(val, max(numOfDigits(i), numOfDigits(n / i)));
    }
  }
  cout << val << endl;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define retunr return
#define pb push_back
#define mp make_pair
#define null NULL
#define sc(x) scanf("%d", &x)
#define sc64(x) scanf("%I64d", &x)
#define pr(x) printf("%d", (x))
#define sp putchar(' ')
#define ln putchar('\n')
#define pr64(x) printf("%I64d", (x))
#define rep(i,l,r) for (int i = l, lim = r;i <= lim; ++i)
#define repr(i,l,r) for (int i = r, lim = l;i >= lim; --i)
#define fi first
#define se second
#define SET(__set, val) memset(__set, val, sizeof __set)
#define fill(a,v,n) memset((a),(v),sizeof(a[0])*(n))
#define copy(a,b,n) memcpy((a),(b),sizeof(a[0])*(n))
#define ALL(x) (x.begin(),x.end())
#define prf(x) printf("%.20f", x)
#define for_each_edge(u) for(int i = point[u];i;i=G[i].n)
typedef unsigned int uint;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define N 300010
#define M 1024
#define MOD 1000000007
void _add(int &a, int b){a = (a+b)%MOD;}
void _sub(int &a, int b){a = (a+MOD-b)%MOD;}
void _mul(int &a, int b){a = (ll)a*b%MOD;}
void _max(int &a, int b){a = max(a,b);}
void _min(int &a, int b){a = min(a,b);}
ll gcd(ll a, ll b){if(!b)return a;return gcd(b,a%b);}
ll pw(ll a, ll b){ll res(1);while(b){if(b&1)res=res*a%MOD;a=a*a%MOD;b>>=1;}return res;}
ll pwM(ll a, ll b, ll mod){ll res(1);while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;}

const int infi = 2147483647;
const ll infl = 9223372036854775807ll;
const db PI = 3.14159265358979323846;

/*
struct E{
	int v, w, n;
}G[N];
int cnt, point[N];
void adde(int u, int v, int w = 0){
	G[++cnt]=(E){v,w,point[u]},point[u]=cnt;
	G[++cnt]=(E){u,w,point[v]},point[v]=cnt;
}
void Ginit(){
	cnt = 0;
	SET(point,0);
}
*/
/*
struct hh{
	int a, b;
	bool operator < (const hh &x) const{
		if(a==x.a)return b<x.b;
		return a<x.a;
	}
}a[N];
*/
int n;
int cnt[2][N], a[N];
const int off = 100000;
void upd(int p, int d){
	for(d;d<=n+off;d+=d&-d)cnt[p][d]++;
}
int ask(int p, int d){
	int res(0);
	for(d;d>0;d-=d&-d)res+=cnt[p][d];
	return res;
}
int p[N];
bool check(int k){
	SET(cnt,0);
	p[0] = 0;
//	int tmp = 0, la = 0;
	ll res(0);
	rep(r,1,n){
		p[r] = p[r-1] + (a[r] <= k);
		int x = p[r]-(r/2);
		res += a[r]<=k;
		if(r&1){
			res += ask(0,x-2+off);
			res += ask(1,x-1+off);
			x = p[r-1] - (r)/2;
			upd(1,x+off);
		}else{
			res += ask(0,x-1+off);
			res += ask(1,x-1+off);
			x = p[r-1] - (r)/2;
			upd(0,x+off);
		}
	}
//	pr(k),sp,pr(res),ln;
	ll m = (ll)n*(ll)(n+1)/2ll;
	return res >= m/2+1;
}
int main(){
//	freopen("1", "r", stdin);
	sc(n);
	rep(i,1,n)sc(a[i]);
	int l = 1, r = 1e9, k = -1;
	while(l <= r){
		int mid = (l+r)>>1;
		if(check(mid)){
			k = mid;
			r = mid-1;
		}
		else
			l = mid+1;
	}
	pr(k),ln;
/*
	int Case;
	sc(Case);
	rep(ca, 1, Case){
	    printf("Case #%d: ", ca);
	}
*/
	return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,(n)-1,0)
#define all(v) v.begin(), v.end()
#define endk '\n'
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ld eps = 1e-10;
template<typename T1, typename T2> inline void chmin(T1 &a, T2 b){if(a>b) a=b;}
template<typename T1, typename T2> inline void chmax(T1 &a, T2 b){if(a<b) a=b;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<ll> A(n); rep(i, n) cin >> A[i];
  sort(all(A));
  if(n % 2) {
    ll ans = 0;
    {
      ll tmp = abs(A[0]-A[n/2]);
      rep(i, n/2) {
        if(i) tmp += abs(A[n-1-(i-1)]-A[i]);
        tmp += abs(A[i]-A[n-1-i]);
      }
      chmax(ans, tmp);
    }
    {
      ll tmp = abs(A[n-1]-A[n/2]);
      rep(i, n/2) {
        if(i) tmp += abs(A[i-1]-A[n-1-i]);
        tmp += abs(A[i]-A[n-1-i]);
      }
      chmax(ans, tmp);
    }
    cout << ans << endk;
  } else {
    ll ans = 0;
    {
      ll tmp = abs(A[0]-A[n/2]);
      rep(i, n/2-1) {
        tmp += abs(A[i]-A[n-1-i]);
        tmp += abs(A[i+1]-A[n-1-i]);
      }
      chmax(ans, tmp);
    }
    {
      ll tmp = abs(A[n-1]-A[n/2-1]);
      rep(i, n/2-1) {
        tmp += abs(A[i]-A[n-1-i]);
        tmp += abs(A[i]-A[n-1-i-1]);
      }
      chmax(ans, tmp);
    }
    cout << ans << endk;
  }
  return 0;
}


Measured memory_bytes: 3988
#include <iostream>
#include <string>
using namespace std;
int main(void){
  string word;
  cin >> word;

  int n = word.length();

  int ans = 0;
  int l = 0;

  for(int i=0;i<n;i++){
    for(int j=i;j<n;j++){
      //cout << "word[" << j << "]=" << word[j] << endl;
      if(word[j] == 'A'||word[j] =='T'||word[j] == 'G'||word[j] == 'C'){
          if(j == n-1){
            l++;
            ans = max(ans,l);
            l =0;
            //cout << "finish" << endl;
            //cout << l << endl;
          }
          else{
            l++;
            //cout << "l++" << endl;
            //cout << l << endl;
          }
      }
      else{
      	ans = max(ans,l);
        l = 0;
        //cout << "not ATGC" << endl;
        //cout << l << endl;
      break;
      }
    }
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
typedef long long ll;
ll gi(){
	ll x=0,f=1;
	char ch=getchar();
	while(!isdigit(ch))f^=ch=='-',ch=getchar();
	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
	return f?x:-x;
}
int x[200010],dv[200010],m,L[200010],R[200010],c[200010];
std::vector<int>P[200010];
int fl[262147],fr[262147];
int main(){
#ifdef XZZSB
	freopen("in.in","r",stdin);
	freopen("out.out","w",stdout);
#endif
	int n=gi(),V=gi();
	for(int i=1;i<=n;++i)x[i]=gi();
	for(int i=V,j=0;~i;i>>=1,++j){
		dv[j]=i;P[m=j].push_back(0);
		for(int l=1,r;l<=n;l=r+1){
			r=l;while(r<n&&x[r+1]-x[r]<=i)++r;
			P[j].push_back(r);
			if(!j)for(int o=l;o<=r;++o)L[o]=l,R[o]=r;
		}
		if(!i)break;
	}
	for(int i=0;i<1<<m;++i){
		for(int j=1;j<=m;++j){
			if((i>>j-1)&1)continue;
			int p;
			if(fl[i]==n)p=n;
			else p=*std::upper_bound(P[j].begin(),P[j].end(),fl[i]);
			fl[i|(1<<j-1)]=std::max(fl[i|(1<<j-1)],p);
		}
	}
	for(int i=0;i<1<<m;++i)fr[i]=n+1;
	for(int i=0;i<1<<m;++i){
		for(int j=1;j<=m;++j){
			if((i>>j-1)&1)continue;
			int p;
			if(fr[i]==1)p=1;
			else p=*--std::lower_bound(P[j].begin(),P[j].end(),fr[i]-1)+1;
			fr[i|(1<<j-1)]=std::min(fr[i|(1<<j-1)],p);
		}
	}
	for(int i=0;i<1<<m;++i){
		int l=fl[i]+1,r=fr[((1<<m)-1)^i]-1;
		if(l>r)++c[1];
		else if(*std::lower_bound(P[0].begin(),P[0].end(),l)>=r)++c[l],--c[r+1];
	}
	for(int i=1;i<=n;++i)c[i]+=c[i-1];
	for(int i=1;i<=n;++i)puts(c[i]?"Possible":"Impossible");
	return 0;
}


Measured memory_bytes: 14708
/*input
4 2 6
*/
#include<bits/stdc++.h>
using namespace std;

#define int long long 
#define double long double
#define f first
#define s second
#define mp make_pair
#define pb push_back
#define RE(i,n) for (int i = 1; i <= n; i++)
#define RED(i,n) for (int i = n; i > 0; i--)
#define REPS(i,n) for(int i = 1; (i*i) <= n; i++)
#define REP(i,n) for (int i = 0; i < n; i++)
#define FOR(i,a,b) for (int i = a; i < b; i++)
#define REPD(i,n) for (int i = n-1; i >= 0; i--)
#define FORD(i,a,b) for (int i = a; i >= b; i--)
#define remax(a,b) a = max(a,b)
#define remin(a,b) a = min(a,b)
#define all(v) v.begin(),v.end()
#define pii pair<int,int>
#define mii map<int,int>
#define vi vector<int>
#define vvi vector<vi>
#define WL(t) while(t --)
#define gcd(a,b) __gcd((a),(b))
#define lcm(a,b) ((a)*(b))/gcd((a),(b))
#define print(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout << *it << " "; cout << endl;
#define debug(x) cout << x << endl;
#define debug2(x,y) cout << x << " " << y << endl;
#define debug3(x,y,z) cout << x << " " << y << " " << z << endl;
const int INF = 1e18+1;
const int MOD = 1e9+7;
const double PI = 3.14159265358979323846264338;

int fast_ex(int a,int n,int m){
  if(n == 0)return 1;
  if(n == 1)return a;
  int x = 1;
    x *= fast_ex(a,n/2,m);
    x %= m;
    x *= x;
    x %= m;
    if(n%2)x*= a;
    x %= m;
    return x;
}


void solve(){
	 int k,a,b;
	 cin >> k >> a >> b;
	 int one = k-(a-1);
	 int ans2 = ((one)/2)*(b-a)+a;
	 if(one%2 == 1)ans2++;
	 cout << max(k+1,ans2);
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  //freopen(".in","r",stdin);freopen(".out","w",stdout);
  int t = 1;//cin >> t;
  WL(t)solve();
  return 0;
}

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

int gcd(int m,int k){
    if(m<k) swap(m,k);
    if(!k) return m;
    else return gcd(m%k,k);
}


int add(int x,int y){
    x+=y;
    if (x>=mod) x%=mod;
    if(x<0) {
        x%=mod;
        x+=mod;
        if(x==mod) x=0;
    }return x;
}

int mul(int a,int b){
    ll c=ll(a)*ll(b)%mod;
    return c;
}
int a[302],b,c,d,dp[2][301][301][301];

int main()
{
    string s;int y;
    cin>>s>>y;
    int k=0,ss=0;
    ref(i,s.size()){
        if(s[i]=='0'){

            a[k]=ss;
            k++;
            ss=0;
        }
        else{
            ss++;
            if(i==s.size()-1) a[k]=ss;
        }
    }
    int su=a[0],dpp[301][301];
    ref(i,k+1){
        int sv=su;
        su+=a[i+1];

        if(i) for(int j=sv;j<=s.size()-k;j++)
            ref(h,s.size()-k+1){

                if(j==sv){
                    dp[0][i][j][h]=dpp[i-1][h];
                }
                else {
                    dp[0][i][j][h]=(((dp[0][i][j-1][h]-dp[1][i-1][j-a[i]-1][h])%mod-dp[0][i-1][j-a[i]-1][h])%mod+(dp[0][i-1][j][h]+dp[1][i-1][j][h])%mod)%mod;
                    if(h) dp[1][i][j][h]=((dp[1][i][j-1][h-1]+dp[0][i-1][j-a[i]-1][h-1])%mod+dp[1][i-1][j-a[i]-1][h-1])%mod;
                    }
                if(j<=su&&j>=sv) dpp[i][h]=add(add(dpp[i][h],dp[0][i][j][h]),dp[1][i][j][h]);
            }
            else {
                dp[0][i][a[0]][0]=1;
                dpp[0][0]=1;
            for(int g=a[0]+1;g<=s.size()-k;g++) {
                dp[1][i][g][g-a[0]]=1;
                if(g<=su&&g>=sv) dpp[i][g-a[0]]=1;
            }
        }
    }
    int ans=0;
    if(y<=s.size()-k)
        ref(i,y+1) ans=add(ans,dp[0][k][s.size()-k][i]);
    else ref(i,s.size()-k+1) ans=add(ans,dp[0][k][s.size()-k][i]);

    cout<<ans;
    return 0;

}

Measured memory_bytes: 56632
#include <iostream>
#include <cmath>
#include <vector>
#include <map>
#include <iomanip>
#include <algorithm>
#include <sstream>
#include <string>
#include <math.h>
#include <set>
using namespace std;
typedef long long ll;
 
int main() {
	ios::sync_with_stdio(false);
	int a, b = 1;
	cin >> a;
	while (b <= a) b *= 2;
	cout << b / 2;
}   

Measured memory_bytes: 256
import os

import itertools
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 998244353

N, S = list(map(int, sys.stdin.buffer.readline().split()))
A = list(map(int, sys.stdin.buffer.readline().split()))


def test(N, S, A):
    A = np.array(A)
    ret = 0
    for choices in itertools.product([True, False], repeat=N):
        choices = np.array(choices, dtype=bool)
        if A[choices].sum() == S:
            ret += 2 ** (N - choices.sum())
    print(ret)


# test(N, S, A)

# # dp[i][s]: i まで見て和が s である数 / 2^(使った数)
# dp = [[0] * (S + 1) for _ in range(N + 1)]
# dp[0][0] = 1
# for i, a in enumerate(A):
#     dp[i + 1] = list(dp[i])
#     for s in reversed(range(S - a + 1)):
#         dp[i + 1][s + a] += dp[i][s] / 2
# print(dp[-1][S] * (2 ** N))


div2 = pow(2, MOD - 2, MOD)
# dp[s]: i まで見て和が s である数 / 2^(使った数)
dp = [0] * (S + 1)
dp[0] = 1
for i, a in enumerate(A):
    for s in reversed(range(S - a + 1)):
        dp[s + a] += dp[s] * div2
        dp[s + a] %= MOD
print(dp[S] * pow(2, N, MOD) % MOD)


Measured memory_bytes: 68572
#include <bits/stdc++.h>
//#include "bits/stdc++.h"
#include <atcoder/all>

using namespace std;
using namespace atcoder;
typedef long long ll;

/*
#define i_7 (ll)(1E9+7)
//#define i_7 998244353
#define i_5 i_7-2
ll mod(ll a){
    ll c=a%i_7;
    if(c>=0)return c;
    return c+i_7;
}
void Add(ll &pos,ll val){pos=mod(pos+val);}
void mod_print(ll k){
    ll P=50000;
    rep(y,1,P){
        ll x=mod(y*k);
        
        if(abs(x)<=P||x+P>=i_7){
            if(x+P>=i_7){
                x-=i_7;
            }
            cout<<x<<"/"<<y<<endl;
            //cout<<setprecision(5)<<(dd)x/(dd)y;
            return;
        }
    }
    cout<<"nun"<<endl;
}
*/

#include "boost/multiprecision/cpp_int.hpp"
#include "boost/multiprecision/cpp_dec_float.hpp"
namespace mp = boost::multiprecision;
typedef mp::cpp_int LL;
typedef mp::number<mp::cpp_dec_float<1024>> DD;// 仮数部が1024ビットの浮動小数点数型(TLEしたら小さくする)

typedef long double dd;
typedef pair<ll,ll> l_l;
typedef pair<dd,dd> d_d;
ll inf=(ll)1E16;
#define rep(i,l,r) for(ll i=l;i<=r;i++)
#define rrep(i,r,l) for(ll i=r;i>=l;i--)
#define pb push_back
ll max(ll a,ll b){if(a<b)return b;else return a;}
ll min(ll a,ll b){if(a>b)return b;else return a;}
void Max(ll &pos,ll val){pos=max(pos,val);}//Max(dp[n],dp[n-1]);
void Min(ll &pos,ll val){pos=min(pos,val);}
dd EPS=1E-12;
#define fastio ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define fi first
#define se second

#define SORT(v) sort(v.begin(),v.end())
#define ERASE(v) v.erase(unique(v.begin(),v.end()),v.end())
#define POSL(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define POSU(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
template<class T,class S>
inline bool chmax(T &a, S b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}
template<class T,class S>
inline bool chmin(T &a, S b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
#define endl "\n"  //インタラクティブで消す！！！！！！！！！！！！！！！！！！！！！
#define all(c) c.begin(),c.end()
typedef vector<ll> vl;


using mint = modint998244353;
//using mint = modint1000000007;
//////////////////////////

struct S{
    mint sum;
    ll size;
};
struct F{
    mint a,b;
};
S op(S l,S r){
    return S{l.sum+r.sum,l.size+r.size};
}
S e(){
    return S{0,0};
}
S mapping(F f,S x){
    return S{f.a*x.sum+f.b*x.size,x.size};
}
F composition(F f,F g){
    return F{f.a*g.a,f.a*g.b+f.b};
}
F id(){
    return F{1,0};
}

int main(){fastio
    ll n,q;cin>>n>>q;
    vector<S> A(n);rep(i,0,n-1){ll x;cin>>x;A[i].sum=x;A[i].size=1;}
    lazy_segtree<S,op,e,F,mapping,composition,id>seg(A);
    while(q--){
        ll t;cin>>t;
        if(t==0){
            ll l,r,b,c;cin>>l>>r>>b>>c;
            seg.apply(l,r,F{b,c});
        }else{
            ll l,r;cin>>l>>r;
            cout<<seg.prod(l,r).sum.val()<<endl;
        }
    }
    
    return 0;
}


Measured memory_bytes: 31444
#include <bits/stdc++.h>
using namespace std;
int main() {
	string tmp = "AKIHABARA";
	string a;
	cin >> a;
	for (int mask = 0; mask < (1 << 4); ++ mask) {
		string s;
		int cnt = 0;
		for (int i = 0; i < (int) tmp.length(); ++ i) {
			if (tmp[i] == 'A') {
				if (mask >> cnt & 1) s += 'A';
				cnt ++;
			}
			else {
				s += tmp[i];
			}
		}
		if (s == a) return 0 * puts("YES");
	}
	puts("NO");
}


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

#define pb push_back
#define mp make_pair
#define sz(x) (int)(x).size()
#define li long long
#define ld long double
#define x first
#define y second
#define pt pair<int, int>
#define pll pair<li, li>
#define forn(i, t) for(int i = 0; i < (t); i++)
#define fore(i, f, t) for(int i = (f); i < (t); i++)
#define forr(i, f, t) for(int i = (f) - 1; i >= (t); i--)
#define all(x) (x).begin(), (x).end()
#define ins insert

using namespace std;


const int INF = 1e9;
const int MOD = 1e9 + 7;
const li INF64 = 1e18;
const ld EPS = 1e-7;

mt19937 myrand(time(NULL));

const int N = 100 * 1000 + 13;

int n;
li a[N];


bool read(){
	if(scanf("%d", &n) != 1)
		return 0;
	forn(i, n)
		scanf("%lld", &a[i]);
	return 1;
}


void solve(){
	li ans[N];
	memset(ans, 0, sizeof(ans));
	/*while (*max_element(a, a + n) != 0){
		ans[max_element(a, a + n) - a]++;
		printf("%d ", max_element(a, a + n) - a);
		int k = *max_element(a, a + n), pos = -1;
		forn(i, n)
			if (a[i] == k)
				pos = i;
		a[pos]--;
	}*/
	li pr[N];
	multiset<li> cur;
	li sum = 0;
	li cnt = 0;
	pr[0] = 0;
	fore(i, 1, n + 1)
		pr[i] = max(pr[i - 1], a[i - 1]);
	forr(i, n, 0){
		if (i != n - 1)
			sum += cnt * (pr[i + 1] - pr[i]);
		cur.insert(a[i]);
		while (!cur.empty() && pr[i] < *cur.rbegin()){
			sum += (*cur.rbegin()) - pr[i];
			cnt++;
			cur.erase(--cur.end());
		}
		ans[i] = sum;
	}
	forn(i, n - 1)
		ans[i] = ans[i] - ans[i + 1];
	forn(i, n)
		printf("%lld\n", ans[i]);
}


int main(){
	#ifdef _DEBUG
		freopen("input.txt", "r", stdin);
	#endif
	while(read())
		solve();
	return 0;
}

Measured memory_bytes: 7424
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <iterator>
#include <typeinfo>
using namespace std;


// define list


namespace  math{
    const double PI = 3.14;
    const int INF = 1000000007;
    int GCM(int a,int b); //最大公約数
    int LCM(int a,int b); //最小公倍数
    int Pemu(int n,int r); //順列
    int Comb(int n,int m); //組み合わせ
    int Digit(int N); //桁和
    
    int GCM(int a,int b){
        if(a<b){
            swap(a,b);
        }
        int r = a%b;
        while (r!=0)
        {
            a=b;
            b=r;
            r=a%b;
        }
        return b;
    }

    int LCM(int a,int b){
        return a*(b/GCM(a,b));
    }

    int Pemu(int n,int r){
        int ans = n;
        for(int i=1;i<r;i++){
            ans*=(ans-i);
        }
        return ans;
    }

    int Comb(int n,int m){
        int a=n,b=m;
        for(int i=1;i<m;i++){
            a *= (a-i);
        }
        for(int i=1;i<m;i++){
            b *= (b-i);
        }
        
        return a/b;
    }

    int Digit(int N){
        if(N<10){
            return N;
        }
        int r = 0;
        while (N>=10)
        {
            r += (N%10);
            N /= 10;
        }
        r += N;
        return r;
    }
}

namespace SubLib{
    #define int long long
    #define double long double
    #define incin(n) int (n); cin >> (n);
    #define strcin(s) string (s); cin >> (s);
    #define incin2(a,b) int a,b; cin >> a >> b; 
    #define rap(n,i) for(int (i) = 0;i<(n);(i)++)
    #define input(n,v) (v) = SubLib::Input((n),(v))
    #define all(v) (v).begin(),(v).end()
    using intv = vector<int>;
    using strv = vector<string>;
    using charv = vector<char>;
    template <class T1>
    using pvec = vector<pair<T1,T1>>;
    template <typename T> vector<T> Input(int n,vector<T> v){
        for(int i=0;i<n;i++){
            cin >> v.at(i);
        }
        return v;
    }
}

using namespace math;
using namespace SubLib;

signed main(){
    incin(n);
    strcin(s);
    rap(s.size(),i){
        s[i] += n;
        if(s[i] > 90){
            s[i] -= 26;
        }
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 256
n = int(input())
abc = []
for i in range(3):
  abc += [[int(i) for i in input().split()]]
ps = sum(abc[1])
for i in range(n-1):
  if abc[0][i]+1 == abc[0][i+1]:
    ps += abc[2][abc[0][i]-1]
print(ps)

Measured memory_bytes: 3060
import java.util.Scanner

import scala.collection.Searching._
import scala.annotation.tailrec
import scala.collection.immutable.Queue

class IUnionFind(val size: Int) {

  private case class Node(var parent: Option[Int], var treeSize: Int)

  private val nodes = Array.fill[Node](size)(new Node(None, 1))

  def union(t1: Int, t2: Int): IUnionFind = {
    if (t1 == t2) return this

    val root1 = root(t1)
    val root2 = root(t2)
    if (root1 == root2) return this

    val node1 = nodes(root1)
    val node2 = nodes(root2)

    if (node1.treeSize < node2.treeSize) {
      node1.parent = Some(t2)
      node2.treeSize += node1.treeSize
    } else {
      node2.parent = Some(t1)
      node1.treeSize += node2.treeSize
    }
    this
  }

  def connected(t1: Int, t2: Int): Boolean = t1 == t2 || root(t1) == root(t2)

  @tailrec
  private def root(t: Int): Int = nodes(t).parent match {
    case None => t
    case Some(p) => root(p)
  }
}


object Main {
  def solve(sc: => Scanner): Unit = {
    println(if (sc.nextInt * sc.nextInt % 2 == 0) ("Even") else ("Odd"))
  }

  def main(args: Array[String]): Unit = {
    val sc: Scanner = new Scanner(System.in)
    solve(sc)
  }
}



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

int main() {
    int n;
    cin >> n;
    int a[n+1], b[n+1], c[n];
    rep1(i,n+1) cin >> a[i];
    rep1(i,n+1) cin >> b[i];
    rep1(i,n) cin >> c[i];

    int prev = -100;
    int ans=0;
    for(int i=1;i<n+1;i++)
    {
        if (i!=1)
            prev = a[i-1];
        ans += b[a[i]];
        if (a[i] == prev+1)
            ans += c[prev];
    }

    cout << ans;

    return 0;
}


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

#define mem(arr, i) fill(arr, arr + sizeof(arr), i)
#define MEM(arr, i) memset(arr, i, sizeof(arr))
#define Push push_back
#define Pair make_pair
#define ALL(x) x.begin(), x.end()
#define X first
#define Y second
#define ACCEL ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
typedef unsigned long long ull;
typedef long long lli;
typedef pair<int,int> pii;
typedef pair<lli,lli> pll;
typedef pair<pll,lli> p3l;
typedef vector<int> vcI;
typedef vector<lli> vcL;
typedef vector<pii> vPI;
typedef vector<pll> vPL;
typedef vector<p3l> v3L;
typedef vector<vcL> vvL;
//typedef priority_queue<T> prior_S<T>;
//typedef priority_queue< T, vector<T>, greater<T> > prior_B<T>;
const double PI = 3.141592653589793;
const lli I_MAX = 1LL << 60;
      lli   mod = 1000000007;

/// templates ///

const lli maxN = 2E5;

vcL inv(maxN+5, 1);
vcL fac(maxN+5, 1);

void ADD(lli &x, lli y) {
	x += y;
	if (x >= mod) x -= mod;
	if (x < 0) x += mod;
}

void MUL(lli &x, lli y) {
	x *= y;
	x = (x % mod + mod) % mod;
}

lli mypow(lli b, lli e) {
	lli ans = 1;
	while (e) {
		if (e & 1) MUL(ans, b);
		MUL(b, b);
		e >>= 1;
	}
	return ans;
}

lli modinv(lli n) {
	return mypow(n, mod - 2);
}

void calcInv(lli n) {
	for (int i = 2; i <= n; ++i) {
		inv[i] = (mod - mod / i) * inv[mod % i] % mod;
	}
}

void calcFac(lli n) {
	for (int i = 2; i <= n; ++i) {
		fac[i] = fac[i - 1] * i % mod;
	}
}

lli cm(lli a, lli b) {
	lli ans = 1;
	if (a < b) return 0;

	MUL(ans, inv[fac[a - b]]);
	MUL(ans, inv[fac[b]]);
	MUL(ans, fac[a]);

	return ans;
}

lli Lucas(lli n, lli m) {
	if (m == 0) return 1;
	return cm(n % mod, m % mod) * Lucas(n / mod, m / mod) % mod;
}

lli doLucas(lli n, lli m) {
	calcInv(mod);
	calcFac(mod);
	return Lucas(n, m);
}

/// coding area ///

const lli maxn = 1E5;

void precal() {

	return;
}

void solve() {
	lli n, w, v = 0;
	cin >> n >> w;
	
	lli cost[n][2];
	for (int i = 0; i < n; ++i) {
		cin >> cost[i][0] >> cost[i][1];
		v += cost[i][1];
	}
	
	vcL knap(v + 5, 1E12);
	knap[0] = 0;
	
	for (int i = 0; i < n; ++i) {
		for (int j = v; j-cost[i][1] >= 0; --j) {
			knap[j] = min(knap[j], knap[j - cost[i][1]] + cost[i][0]);
		}
	}
	
	for (int i = v; i >= 0; --i) {
		if (knap[i] <= w) {
			cout << i << '\n';
			return;
		}
	}
}

int main() {
	precal();
	int t = 1;
	#ifdef LOCAL
		t = INT_MAX;
	#else
		ACCEL;
	#endif
//	cin >> t;
	for (int i = 1; i <= t; ++i) {
//		printf("Case #%d: ", i );
		solve();
	}
	return 0;
}




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

int main() {
    string s;
    getline(cin,s);
//    cout << s << "\n";
//    cout << s.length();

    if(s[0] != 'A'){
        cout << "WA";
        return 0;
    }
    int c_count = 0;

    for(int i = 1; i<s.length(); i++){

        if(i>=2 && i<= s.length()-2){

            if(s[i] == 'C'){
                c_count += 1;
            }else{
                if(isupper(s[i])) { // cが大文字のとき
                    cout << "WA";
                    return 0;
                }
            }
        }else if(isupper(s[i])) { // cが大文字のとき
            cout << "WA";
            return 0;
        }
    }

    if(c_count == 1){
        cout << "AC";
    }else{
        cout << "WA";
    }


    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int N;
    cin >> N;
    vector<ll> A(N);
    vector<ll> add(N);
    for(int i = 0; i < N; i++){
        cin >> A[i];
    }
    for(int i = N - 1; i >= 0; i--){
        add[i] = (i == N - 1 ? A[i] : add[i + 1] + A[i]);
        add[i] %= 1000000007;
    }
    ll ans = 0;
    for(int i = 0; i < N - 1; i++){
        ans += (A[i] * add[i + 1]) % 1000000007;
        ans %= 1000000007;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 6412
#include <stdio.h>

int main(){
	int k;
	int a;
	int b;
	scanf("%d", &k);
	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: 1728
#include<bits/stdc++.h>
#define N 1000000
using namespace std;

int n;
char s[N];
bool used[N];

bool check(int d){
  int cnt=0,t;
  queue<int> qi,qj;
  for(int i=0;i<n;i++)used[i]=false;
  for(int i=n-1;i>=0;i--){
    if(cnt==d)break;
    if(s[i]=='I')qi.push(i);
    if(s[i]=='O'&&qi.size()){
      used[i]=true;
      cnt++;
      t=qi.front();
      used[t]=true;
      qi.pop();
    }
    if(cnt==d)break;
  }
  if(cnt<d)return false;
  cnt=0;
  for(int i=0;i<n;i++){
    if(cnt==d)return true;
    if(!used[i]&&(s[i]=='J'||s[i]=='I'))qj.push(i);
    if(used[i]&&s[i]=='O'&&qj.size())cnt++,qj.pop();
    if(cnt==d)return true;
  }
  return false;
}

int bynary_search(){
  int l=0,r=n,m;
  while(l<r){
    m=(l+r)/2;
    if(check(m))l=m+1;
    else r=m;
  }
  if(check(l+1))return l+1;
  if(check(l))return l;
  return l-1;
}

int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>s[i];
  cout<<bynary_search()<<endl;
  return 0;
}

Measured memory_bytes: 4820
#include <iostream>
#include <stdlib.h>
#include <string>
#include <algorithm>
#include <utility>
#include <set>
#define llint long long
#define mod 1000000007

using namespace std;

string s, t;

int tz[500005];
int Z[3600005], z[3600005];
int dp[3600005];

void z_algorithm(string s, int z[])
{
	z[0] = s.size();
	
	int x = 0, y = 0;
	for(int i = 1; i < s.size(); i++){
		if(i > y){
			z[i] = 0;
			for(int j = 0; j < s.size(); j++){
				if(i+j > s.size() || s[i+j] != s[j]) break;
				z[i]++;
			}
			x = i, y = i + z[i] - 1;
		}
		else if(i + z[i-x] <= y) z[i] = z[i-x];
		else{
			z[i] = y-i+1;
			for(int j = y-i+1; j < s.size(); j++){
				if(i+j > s.size() || s[i+j] != s[j]) break;
				z[i]++;
			}
			x = i, y = i + z[i] - 1;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s >> t;
	
	z_algorithm(t, tz);
	int p = t.size();
	for(int i = 1; i < t.size(); i++){
		if(t.size() % i == 0 && tz[i] == t.size()-i){
			p = i;
			break;
		}
	}
	//for(int i = 0; i < t.size(); i++) cout << tz[i] << " "; cout << endl;
	llint mul = t.size() / p;
	t = t.substr(0, p);
	
	string tmp = s;
	llint rep = (t.size()+s.size()-1)/s.size()+1; s = "";
	for(int i = 0; i < rep; i++) s += tmp;
	
	int n = s.size() * 2, m = t.size();
	string S = t + "#" + s + s;
	z_algorithm(S, Z);
	
	for(int i = 0; i < n; i++) z[i] = Z[i+m+1];
	
	for(int i = 0; i < n; i++){
		if(z[i] == m && i+m <= n) dp[i+m] = max(dp[i+m], dp[i] + 1);
	}
	int ans = 0;
	for(int i = 0; i <= n; i++) ans = max(ans, dp[i]);
	if(s.size() % m == 0 && ans >= n / m - 1) ans = -1;
	if(ans != -1) ans /= mul;
	cout << ans << endl;
	
	return 0;
}

Measured memory_bytes: 49372
import java.util.Scanner;

public class Main{
	static int ans = 0;
	static long N;
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		dfs(0,0,0,0);
		System.out.println(ans);
	}

	private static void dfs(long n, int x3, int x5, int x7) {
		if(x3>0&&x5>0&&x7>0&&n<=N) ans++;
		if(n*10<N) {
			dfs(n*10+3,x3+1,x5,x7);
			dfs(n*10+5,x3,x5+1,x7);
			dfs(n*10+7,x3,x5,x7+1);
		}
	}
}

Measured memory_bytes: 23764
import java.io.*;
import java.util.*;


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();

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

		List<Integer> tt = new ArrayList<>(n + 1);
		List<Integer> vv = new ArrayList<>(n + 1);
//		tt.add(0);
//		vv.add(0);
		int tsum = 0;
		for (int i = 0; i < n - 1; i++) {
			tsum += t[i];
			tt.add(tsum);
			vv.add(v[i]);
		}
		tsum += t[n - 1];
		tt.add(tsum);
		vv.add(v[n - 1]);
		vv.add(0);

		int m = 10;
		double p = 0;
		double ans = 0;
		int maxi = 0;
		for (int i = 1; i <= tsum * m; i++) {
			double x = (double)i / m;
			double tmp = x;
			tmp = Math.min(tmp, -(x - tsum));
			if (x >= tt.get(maxi)) {
				maxi++;
			}
			maxi = Math.min(maxi, tt.size() - 1);
			tmp = Math.min(tmp, vv.get(maxi));
			for (int j = 0, size = tt.size(); j < size; j++) {
				if (x <= tt.get(j)) {
					tmp = Math.min(tmp, -(x - tt.get(j)) + vv.get(j));
					tmp = Math.min(tmp, -(x - tt.get(j)) + vv.get(j + 1));
				} else {
					tmp = Math.min(tmp, (x - tt.get(j)) + vv.get(j));
					tmp = Math.min(tmp, (x - tt.get(j)) + vv.get(j + 1));
				}
			}

			ans += (p + tmp) / m / 2;

			p = tmp;
		}

		pr.printf("%.4f\n", ans);
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}


Measured memory_bytes: 24404