akhauriyash/Code-Regression huggingface dataset:
n, x = map(int, input().split())

lengthOfBurger = [1]
numberOfPadi = [1]

for i in range(50):
    lengthOfBurger.append(1 + lengthOfBurger[-1] + 1 + lengthOfBurger[-1] + 1)
    numberOfPadi.append(numberOfPadi[-1] + 1 + numberOfPadi[-1])
A = []
def solution(k, end):
    if end == 0:
        A.append(0)
        return 0
    if end == lengthOfBurger[k]:
        A.append(numberOfPadi[k])
        return 0
    elif end == lengthOfBurger[k] + 1:
        A.append(numberOfPadi[k] + 1)
        return 0
    if end <= lengthOfBurger[k - 1] + 1:
        return solution(k - 1, end - 1)
    elif end <= lengthOfBurger[k - 1] + 2:
        return solution(k - 1, end - 1)
    elif end <= 2 * lengthOfBurger[k - 1] + 3:
        return solution(k - 1, lengthOfBurger[k - 1]+1) + solution(k - 1, end - 2 - lengthOfBurger[k - 1])
    else:
        print("NG")
        return -1

solution(n, x)

print(sum(A))

Measured memory_bytes: 3064
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define szz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

void solve() {
	int c[3] = {};
	string s; cin >> s;
	for(char ch : s) c[ch-'a']++;
	sort(c, c+3);
	if(c[2] - c[0] <= 1) puts("YES");
	else puts("NO");
}

int main(){
	int Tc = 1; // scanf("%d\n", &Tc);
	for(int tc=1;tc<=Tc;tc++){
		solve();
	}
	return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
char str[200010];
int main() {
	scanf ( "%s", str );
	ll cnt[26];
	memset ( cnt, 0, sizeof ( cnt ) );
	ll n = strlen ( str );
	for ( int j = 0; j < n; j++ )
		cnt[str[j] - 'a']++;
	ll ans = 0, l = 0;
	for ( int j = 0; j < 26; j++ )
		l = l + ( ( cnt[j] * ( cnt[j] - 1 ) )  / 2 ) ;
	ans = ( ( n * ( n - 1 ) ) / 2 );
	ans = 1 + ans - l;
	cout << ans;
	return 0;
}


Measured memory_bytes: 384
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct {
  double x;
  double y;
  double r;
  int c;
  int under;
} circle;
// distance between (x1,y1) and (x2,y2)
double cdis(double x1, double y1, double x2, double y2) {
  return sqrtl((x1 - x2) * (x1 - x2) +
               (y1 - y2) * (y1 - y2));
}
int max(int x, int y) {
  if(x > y)
    return x;
  else
    return y;
}

circle data[30];
circle zero;
// removed?
int check[100000000] = {0};
int cntc[4] = {0};
int cdata[4][10] = {0};
int n;

void memoset();
int solve(int now);

int main() {
  int i, j;
  zero.x = zero.y = zero.r = 0.0;
  zero.under = zero.c = 0;
  while(1) {
    scanf("%d", &n);
    if(n == 0) break;
    for(i = 0; i < 4; ++i)
      for(j = 0; j < 6; ++j) cdata[i][j] = -1;
    for(i = 0; i < 4; ++i) cntc[i] = 0;
    for(i = 0; i < (1 << n); ++i) check[i] = -1;
    for(i = 0; i < n; ++i) data[i] = zero;
    for(i = 0; i < n; ++i) {
      scanf("%lf %lf %lf %d", &data[i].x, &data[i].y,
            &data[i].r, &data[i].c);
      --data[i].c;
      cdata[data[i].c][cntc[data[i].c]] = i;
      ++cntc[data[i].c];
    }
    memoset();
    printf("%d\n", solve(0));
  }
  return 0;
}

void memoset() {
  int i, j;
  for(i = 0; i < n; ++i)
    for(j = i + 1; j < n; ++j) {
      double rsum = data[i].r + data[j].r;
      if(rsum >
         cdis(data[i].x, data[i].y, data[j].x, data[j].y))
        data[j].under += (1 << i);
    }
}
int solve(int now) {
  if(check[now] != -1) return check[now];
  int ans = 0, next = 0, i, j, k;
  for(i = 0; i < 4; ++i) {
    for(j = 0; j < cntc[i]; ++j)
      for(k = 0; k < cntc[i]; ++k) {
        next = now;
        int nx = cdata[i][j], ny = cdata[i][k];
        if(j != k && ((1 << nx) & now) != (1 << nx) &&
           ((1 << ny) & now) != (1 << ny) &&
           ((data[nx].under & now) == data[nx].under) &&
           ((data[ny].under & now) == data[ny].under)) {
          next += (1 << nx) + (1 << ny);
          ans = max(ans, solve(next) + 2);
        }
      }
  }
  check[now] = ans;
  return ans;
}


Measured memory_bytes: 67248
X = int(input())

c = []
for i in range(1, int((X+1)**(1/2))+1):
    if i != 0 and X % i == 0:
        c.append([i, X//i])

for x1, x2 in c:
    for b in range(-1000, 1000):
        if b != 0:
            if (x1+b)**3 * (2*b+x1) + (b**2) * (x1**2 + 3*x1*b+3*(b**2)) == x2:
                print(x1+b, b)
                break

Measured memory_bytes: 67652
S=input()
N=len(S)
X=[1,10,9,12,3,4]
Y=[0,0,0,0,0,0]
nowmod=0
modprime=10**9+7
for i in range(N):
    if S[-i-1]=="?":
        Y[i%6]+=1
    else:
        nowmod+=X[i%6]*int(S[-i-1])
        nowmod%=13
#print(nowmod,Y)
#?は0~9まで選べる
M=max(Y)
dp=[[0 for j in range(13)]for i in range(M+1)]
#dp[i][j]:全部でi個あるグループの総和がmod 13でjになるパターン数(mod 10**9+7)
dp[0][0]=1
for i in range(M):
    for k in range(10):
        for j in range(13):
            dp[i+1][(k+j)%13]+=dp[i][j]
            dp[i+1][(k+j)%13]%=modprime
table=[[dp[Y[i]][j] for j in range(13)]for i in range(6)]
ans=[[0 for j in range(13)] for i in range(7)]
ans[0][0]=1
for i in range(6):
    for j in range(13):
        for k in range(13):
            ans[i+1][(j+(X[i]*k))%13]+=ans[i][j]*table[i][k]
            ans[i+1][(j+(X[i]*k))%13]%=modprime
print(ans[6][(5-nowmod)%13])


Measured memory_bytes: 45660
#include <iostream>
using namespace std;
 
long long N, ans = 0;
 
int main() {
	cin >> N;
	for (int i = 1; i <= N; i++) {
		if (i % 3 != 0 && i % 5 != 0) {
			ans += i;
		}
	}
 
	cout << ans;
}

Measured memory_bytes: 3620
#include <bits/stdc++.h>
#include <assert.h>
using namespace std;
using i64 = long long;

int main()
{
  i64 n;
  string s;
  cin >> n >> s;
  vector<i64> cntw(n), cntb(n);
  for (i64 i = 0; i < n; i++)
  {
    if (s[i] == '#')
      cntb[i]++;
    if (i != 0)
      cntb[i] += cntb[i - 1];
  }
  for (i64 i = n - 1; 0 <= i; i--)
  {
    if (s[i] == '.')
      cntw[i]++;
    if (i != n - 1)
      cntw[i] += cntw[i + 1];
  }
  i64 ans = cntb[n - 1];
  for (i64 i = 0; i < n; i++)
    ans = min(ans, cntw[i] + (i != 0 ? cntb[i - 1] : 0));
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 3716
n = int(input())
a = [0] * n
b = [0] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())

count = 0
for i in reversed(range(n)):
    c = b[i] * (-(-a[i] // b[i])) - a[i]
    #for j in range(i):
    #    a[j] += c
    count += c
    if i >= 1:
        a[i-1] += count
print(count)


Measured memory_bytes: 21524
# /usr/bin/python
# -*- coding: utf-8 -*-
import sys


R,G,B,N = map(int, input().split())
ans = 0
for r in range(N//R+1):
  ret = N - R*r
  for g in range(ret//G+1):
    rest = ret-g*G
    if rest<0: continue
    if rest==0 or rest%B==0:
      ans += 1
print(ans)

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

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  if (A == B){
    if (A != C){
      cout << "Yes" << endl;
      return 0;
    }
  }
  if (A == C){
    if (A != B){
      cout << "Yes" << endl;
      return 0;
    } 
  }
  if (B == C){
    if (B != A){
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  
  cout << "No" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int a,b,d,r;
	double f;
	scanf("%d %d",&a,&b);
	d=a/b;
	r=a%b;
	f=(double)a/b;
	printf("%d %d %.5lf\n",d,r,f);
	return 0;
}

Measured memory_bytes: 636
import Control.Monad
import Control.Applicative
import Data.List
import Data.Array
import Data.Maybe
import Data.Bits
import Data.Ord
import qualified Data.ByteString.Char8 as BS
import qualified Data.Set as Set
import Debug.Trace

listToTuple2 [a,b] = (a,b)
listToTuple3 [a,b,c] = (a,b,c)
listToTuple4 [a,b,c,d] = (a,b,c,d)

getWords = getLine >>= return . words

readIntBS = fst . fromJust . BS.readInt


main :: IO ()
main = do
  (a,b) <- listToTuple2 . map read . words <$> getLine

  print $ a * b - (a+b-1)

  return ()


Measured memory_bytes: 508
import sys

def calc(x, n, p1, p2):
    dp = []
    for i in range(n):
        dp.append( [0] * (x + 1) )

    pocket = x
    for i in range(n):
        for j in range(x + 1):
            dp[i][j] = dp[i - 1][j]
            if j - p1[i] >= 0:
                dp[i][j] = max(dp[i][j], dp[i][j - p1[i]] + p2[i])
            pocket = max(pocket, (x - j) + dp[i][j])

    return pocket

def main():
    n,d,x = map(int, sys.stdin.readline().split())

    pp = []
    for i in range(d):
        pp.append( list(map(int,sys.stdin.readline().split())) )

    curr_x = x
    for i in range(d - 1):
        curr_x = calc(curr_x, n, pp[i], pp[i + 1])

    print(curr_x)

if __name__ == '__main__':
    main()

Measured memory_bytes: 12352
import Data.List

ans :: Int -> Int -> [[Int]]
ans 0 _ = [[]]
ans 1 _ = [[1]]
ans num max =
  let is = reverse $ [1 .. (minimum [num,max]) ]
      i = map (\i -> map (i:) (ans (num-i) i) ) is
      j = concat i
  in
    j

to_str :: [Int] -> String
to_str [] = []
to_str (x:[]) = show x
to_str (x:xs) =
  (show x)++(' ':(to_str xs))

main = do
  l <- getContents
  let n  = map read $ lines l :: [Int]
      n' = takeWhile (/=0) n
      o  = map (\x -> map to_str $ ans x x) n'
  mapM_ (mapM_ putStrLn) o

Measured memory_bytes: 5432
import sys
#input = sys.stdin.readline

def io_generator():
	return input()
	
def ioByFile(fn='inputFile.txt'):
	with open(fn) as f:
		for line in f:
			yield line[:-1]

#+++++ +++++ +++++#
		
def main(a_io):
	n = int(a_io())
	ww=list(map(int, a_io().split()))
	
	ss=sum(ww)
	left=0
	min_diff = ss
	for i in ww:
		left+=i
		diff = abs((ss-left)-left)
		if diff < min_diff:
			min_diff=diff
		else:
			break
	
	print(min_diff)
	
	
#+++++ +++++ +++++#

if __name__ == "__main__":
	io= lambda : io_generator()
	if sys.platform =='ios':
		testInput=ioByFile()
		io=lambda : next(testInput)
	main(io)

Measured memory_bytes: 3064
#include <stdio.h>

#define SIZE 31

int main()
{
  int cnt;
  int N,M,K;
  int A;
  int count[SIZE] = {0,};
  int i,j;
  int found=0;

  cnt = scanf("%d %d", &N, &M);

  for (i=0; i<N; i++) {
    cnt = scanf("%d", &K);
    for (j=0; j<K; j++) {
      cnt = scanf("%d", &A);
      count[A]++;
    }
  }
  for (i=1; i<=M; i++) {
    if (count[i] == N) found++;
  }

  printf("%d", found);

  return 0;
} 

Measured memory_bytes: 128
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cmath>
#include<map>
#include<cstdio>
#include<stack>
#include<queue>
#include<fstream>
#include<cstdio>
#include<deque>

using namespace std;
#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(i,s,n) for(int i=(s);i>=(g);(i)--)
#define all(a) (a).begin(),(a).end()
#define reall(a) (a).rbegin(),(a).rend()
#define pb push_back
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
const double PI = acos(-1.0);

typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef deque<ll> dll;
ll mod = 1e9 + 7;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);

	long long n;
	cin >> n;
	vector<long long> a(n);
	deque<long long> b;
	deque<long long>::iterator it;
	for (int i = 0; i < n; i++)
		cin >> a[i];


	for (int i = 0; i < n; i++) {
		if (i % 2 != n % 2)
			b.push_front(a[i]);
		else
			b.push_back(a[i]);
	}
	for (it = b.begin(); it != b.end(); it++)
		cout << *it << " ";
	cout << endl;
	return 0;
}

Measured memory_bytes: 5376
#include<iostream>
#include<map>
#include<vector>

using namespace std;

int main(){
  int n;cin >> n;
  vector<pair<int, int>> vec(n);
  for(auto&&e : vec)cin >> e.first >> e.second;

  map<pair<int,int>,int>mp;

  int sum = 0;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < n; ++j){
      if(i == j)continue;
      pair<int,int>dif = make_pair(vec[i].first - vec[j].first, vec[i].second - vec[j].second);
      mp[dif]++;
      if(sum < mp[dif])sum = mp[dif];
    }
  }
  cout << n - sum << endl;
  return 0;
}


Measured memory_bytes: 384
def check(p):
    i = 0
    for j in range(k):
        s = 0
        while s + w[i] <= p:
            s += w[i]
            i += 1
            if i == n:
                return n
    return i


def binary_search():
    left = 0
    right = 100000 * 10000
    while right - left > 1:
        mid = (left + right) // 2
        v = check(mid)
        if v >= n:
            right = mid
        else:
            left = mid
    return right

n, k = map(int, input().split())
w = [int(input()) for _ in range(n)]
ans = binary_search()
print(ans)


Measured memory_bytes: 9560
n,h = map(int,input().split())
l = sorted([list(map(int,input().split())) for _ in range(n)])[::-1]
a,b = l[0]
cou = 0
if b>=h:
  print(1)
  exit()
l1 = sorted([i for j,i in l[1:]])[::-1]
for k in l1:
  if a<k:
    cou += 1
    h -= k
    if h<=0:
      print(cou)
      exit()
    elif h-b<=0:
      print(cou+1)
      exit()
h -= b
cou += 1
if h<=0:
  print(cou)
else:
  t = -(-h//a)
  print(cou+t)

Measured memory_bytes: 29620
// ------------------------------------
// Date:2018/ 2/24
// Problem:AGC 002 KnotPuzzle c.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto&& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()

using ll = long long;

#define MOD 1000000007

int main()
{
  int N,L,sum;
  cin >> N >> L;
  vector<int> a(N);
  REP(i,N) cin >> a[i];
  
  // a[0]+a[1]>=Lの時
  REP(i,N-1) {
    if (a[i]+a[i+1]>=L) {
      cout << "Possible" << endl;
      FOR(j,1,i+1) cout << j << endl;
      RFOR(j,i+1,N) cout << j << endl;
      return 0;
    }
  }
  cout << "Impossible" << endl;
  return 0;
}



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

#define mod 1000000007 
#define check exit(0)
#define nl cout<<endl;
#define ordered_set tree<int,null_type,less_equal<int>,rb_tree_tag,tree_order_statistics_node_update>
#define ll long long int
#define trace(x) cerr<<#x<<" : "<<x<<endl;
#define deb(v) for(int i=0;i<v.size();i++) {cout<<v[i]; (i==v.size()-1) ? cout<<"\n":cout<<" "; }
#define jaldi ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

using namespace __gnu_pbds;
using namespace std;

int main()
{
    jaldi
    ll k,n;
    cin>>k>>n;
    vector<ll> v(n);
    for(ll &x:v) cin>>x;

    ll ans=0;
    for(int i=1;i<n;i++) { ans+=v[i]-v[i-1];}
    ans+=(k-v[n-1]+v[0]);

    ll fans=LLONG_MAX;
    for(int i=1;i<n;i++)
    {
        fans=min(fans,ans-(v[i]-v[i-1]));
    }
    fans=min(fans,ans-(k-v[n-1]+v[0]));
    cout<<fans;
    return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <ctime>
#include <map>
#include <queue>

using namespace std; using ll=long long; using P=pair<ll,ll>; const int INF=1e9; const ll LNF=1e18;

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

  int an = 0;
  for(P x : mp) {
    //cout << x.first << " " << x.second << endl;
    if (x.first <= x.second) an += x.second - x.first;
    else an += x.second;
  }
  cout << an << endl;
}

Measured memory_bytes: 4736
s = int(input())
ac = 0
wa = 0
tle = 0
re = 0
for i in range(1,s+1):
    ch = input()
    if ch == "AC":
        ac += 1
    elif ch == "WA":
        wa += 1
    elif ch == "TLE":
        tle +=1
    elif ch == "RE":
        re += 1

print("AC x "+str(ac))
print("WA x "+str(wa))
print("TLE x "+str(tle))
print("RE x "+str(re))

Measured memory_bytes: 9196
fun main(args: Array<String>) {
    var (H, W) = listOfInt()
    val M = mutableListOf<MutableList<Int>>()
    for (h in 0 until H) {
        M.add(next().map{ if (it == '.') 0 else 1 }.toMutableList())
    }
    var f = false
    fun yoko() {
        for (h in (0 until H).reversed()) {
            var sum = 0
            for (w in 0 until W) sum += M[h][w]
            if (sum == 0) {
                M.removeAt(h)
                H--
                f = true
            }
        }
    }
    fun tate() {
        for (w in (0 until W).reversed()) {
            var sum = 0
            for (h in (0 until H).reversed()) sum += M[h][w]
            if (sum == 0) {
                for (h in (0 until H).reversed()) M[h].removeAt(w)
                W--
                f = true
            }
        }
    }
    do {
        f = false
        yoko()
        tate()
    } while (f)
    repeat(H) {
        println(M[it].joinToString(separator = "") { if (it == 0) "." else "#" })
    }
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }


Measured memory_bytes: 37908
#include<bits/stdc++.h>
using namespace std;
#define inf 1e9
#define ll long long 
#define M 1000000007
#define P pair<int,int>
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define rep(i,n) FOR(i,0,n)
const int vx[4] = {0,1,0,-1};
const int vy[4] = {1,0,-1,0};
#define PI 3.14159265

int n;
bool c[200][200];
int ans;

int main(){
  cin>>n;
  rep(i,n){
    int a,b;
    cin>>a>>b;
    c[b][a] = true;
  }
  vector<P> v;

  rep(i,n){
    int a,b;
    cin>>a>>b;
    v.push_back(P(b,a));
  }

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

  rep(i,n){
    P p = v[i];
    int x=-1,y=-1;
    rep(j,p.second){
      rep(k,p.first){
        if(c[k][j]){
          x = j; y =k;
        }
      }
    }
    if(x!=-1){
      c[y][x] = false;
      ans++;
    }
  }

  cout<<ans<<endl;

  return 0;
}




Measured memory_bytes: 256
s = input()
if int(s[0:4])>2019:
    print("TBD")
    exit()
elif int(s[5:7])>4:
    print("TBD")
    exit()
elif int(s[6])==4 and int(s[8:10])>30:
    print("TBD")
else:
    print("Heisei")

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (a * b) % mod
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;

class BIT{
public:
	int n = 1;
	vector<int> bit;
	void init(int N){	//[1, N]のBIT作成
		while(n < N+1)n *= 2;
		bit.resize(n+1);
		fill(all(bit), 0);
	}
	void add(int i, int x){
		while(i <= n){bit[i] += x;i += i&-i;}
	}
	int get(int i){
		int s = 0;
		while(i > 0){s += bit[i];i -= i&-i;}
		return s;
	}
	int lower_bound(int k, int ret = -1){	//ret=見つからなかったときに返すidx
		int lb = 0, ub = n+1;
		while(ub-lb > 1){
			if(get((lb+ub)/2) >= k)ub = (lb+ub)/2;
			else lb = (lb+ub)/2;
		}
		return ub == n+1 ? ret : ub;
	}
};

int a[200000], b[200000];
int n;
BIT bit;
int solve(int mid){
	bit.init(2*n+1);
	int sum = n+1, ans = 0;
	rep(i,n){
		ans += bit.get(sum);
		if(a[i] >= mid)sum++;
		else sum--;
		bit.add(sum, 1);
	}
	return ans;
}

signed main(){
	scanf("%lld", &n);
	rep(i,n)scanf("%lld", &a[i]);
	rep(i,n)b[i] = a[i];
	sort(b, b+n);
	
	int lb = 0, ub = n;
	while(ub-lb > 1){
		int mid = (ub+lb)/2;
		if(solve(b[mid]) >= n*(n+1)/2/2)lb = mid;
		else ub = mid;
	}
	//printf("%lld\n", lb);
	printf("%lld\n", b[lb]);
	return 0;
}






Measured memory_bytes: 3840
N,D=map(int,input().split())
l=[list(map(int,input().split())) for i in range(N)]
ans=0
for i in range(N):
    for j in range(i+1,N):
        r=0
        for k in range(D):
            r+=(l[i][k]-l[j][k])**2
        r=r**0.5
        if r==int(r):
            ans+=1
print(ans)


Measured memory_bytes: 3188
#include <cstdio>

const double kProbability = 1.0f / 6.0f;
const int kMaxSquare = 128;
const int kMaxTurn = 128;

enum BoardState{
	BLANK, LOSE, BACK
};

BoardState board[kMaxSquare];

double bp(const int N, const int T){
	double prob[kMaxTurn][kMaxSquare];
	for (int i = 0; i <= T; i++)
		for (int j = 0; j <= N; j++)
			prob[i][j] = 0.0f;
	prob[0][0] = 1.0f;

	for (int t = 0; t < T; t++){
		for (int n = 0; n < N; n++){
			if (prob[t][n] == 0.0f) continue;
			for (int dice = 1; dice <= 6; dice++){
				int pos = (n + dice <= N) ? n + dice : N - (n + dice - N);
				switch (board[pos]){
				case BLANK:
					prob[t + 1][pos] += prob[t][n] * kProbability;
					break;
				case LOSE:
					prob[t + 2][pos] += prob[t][n] * kProbability;
					break;
				case BACK:
					prob[t + 1][0] += prob[t][n] * kProbability;
				}
			}
		}
	}

	double res = 0.0f;
	for (int i = 1; i <= T; i++)
		res += prob[i][N];
	return res;
}

int main(){
	while (1){
		int N, T, L, B;
		scanf("%d %d %d %d", &N, &T, &L, &B);
		if (N == 0) return 0;
		for (int i = 0; i <= N; i++) 
			board[i] = BLANK;
		for (; L > 0; L--){
			int l;
			scanf("%d", &l);
			board[l] = LOSE;
		}
		for (; B > 0; B--){
			int b;
			scanf("%d", &b);
			board[b] = BACK;
		}
		printf("%.6f\n", bp(N, T));
	}
}

Measured memory_bytes: 1172
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
res = sum(B)
#print(res)
for i in range(n-1):
    if A[i+1] == A[i] + 1:
        #print(A[i+1], A[i])
        #print(C[i])
        res += C[A[i]-1]
print(res)

Measured memory_bytes: 3064
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int x  =sc.nextInt();
    int y = sc.nextInt();
    String ans = "No";
    if((y-2*x) >= 0 && (y-2*x)%2==0 && (4*x-y)>=0 &&(4*x-y)%2==0){
    	ans = "Yes";
    }

    System.out.println(ans);
    sc.close();
  }
}


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

using namespace std;

int main() {
  int a, b, c, d, e, f = 0;
  cin >> a;
  b = (a % 10);
  c = (a / 10 % 10);
  d = (a / 100 % 10);
  e = (a / 1000 % 10);
  if ((b == c && c == d) || (c == d && d == e)) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
N = int(input())

ans = 0   # ABが含まれる最大数

cnt1 = 0  # BではじまりAでおわる
cnt2 = 0  # Aでおわる
cnt3 = 0  # Bで始まる
for _ in range(N):
    s = input().strip()
    ans += s.count('AB')
    if s[0] == 'B' and s[-1] == 'A': cnt1 += 1
    elif s[-1] == 'A': cnt2 += 1
    elif s[0] == 'B':  cnt3 += 1


if cnt1 > 0:
    # Aでおわる
    if cnt2 > 0:
        ans += 1
        cnt2 -= 1
    # BではじまりAでおわる
    ans += cnt1 - 1
    # Bではじまる
    if cnt3 > 0:
        ans += 1
        cnt3 -= 1
    # Aでおわる/Bではじまる
    ans += min(cnt2,cnt3)
else:
    ans += min(cnt2,cnt3)

print(ans)


Measured memory_bytes: 3064
import string


def solve():
    s = read()
    result = think(s)
    write(result)


def read():
    n = read_int(1)[0]
    s = []
    for _ in range(n):
        s.append(read_line())
    return s


def read_int(n):
    return list(map(lambda x: int(x), read_line().split(' ')))[:n]


def read_float(n):
    return list(map(lambda x: float(x), read_line().split(' ')))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(s):
    dictionary_of_histogram = {}
    for line in s:
        key_of_histgram = make_key_for_histgram(line)
        if key_of_histgram in dictionary_of_histogram:
            dictionary_of_histogram[key_of_histgram] += 1
        else:
            dictionary_of_histogram[key_of_histgram] = 1

    result = 0
    for k, v in dictionary_of_histogram.items():
        if v >= 2:
            result += combination_2(v)
    return result


def make_key_for_histgram(s):
    key = ''
    for c in string.ascii_lowercase:
        count = s.count(c)
        if count > 0:
            key += ',{0:s}{1:d}'.format(c, count)
    return key


def combination_2(n):
    return (n * (n - 1)) // 2


def write(result):
    print(result)


if __name__ == '__main__':
    solve()

Measured memory_bytes: 81496
#include <iostream>
#include <iomanip> //! for setprecision(10)
#include <math.h>
#include <algorithm>
#include <functional> 
#include <string>
#include <vector>

#include <cstring>
#include <set>
#include <map>
#include <queue>
#include <utility>

using namespace std;

typedef long long LL;

#define dump(c) { for (auto it = c.begin(); it != c.end(); ++it) if (it == c.begin()) cout << *it; else cout << ' ' << *it; cout << endl; } 
#define rep(i,n) for (int i = 0; i < (n); ++i)

const int MOD = 1000000007;

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

    int N, K;
    cin >> N >> K;
    vector<LL> p(N);
    rep(i, N) cin >> p[i];

    int sum = 0;
    rep(i, K) sum += p[i];

    int maxSum = sum;
    int maxHead = 0;

    for (int i = 0; i+K < N; ++i) {
        sum += p[i+K] - p[i];
        if (maxSum < sum) {
            maxSum = sum;
            maxHead = i+1;
        }
    } 

    double ans = 0;
    rep(i, K) {
        ans += (1.0 + p[i+maxHead]) / 2;
    }

    printf("%.6f\n", ans);

    return 0;
}


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

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;
typedef vector<int> vi;
#define rep(i, n) for(int i = 0; i < n; ++i)
#define rInt(a) scanf("%d",&a);

main(){
   int n; rInt(n);
   int val;
   map<int,int> m;
   rep(i,n){
        scanf("%d",&val);
        if(m.count(val)>0) m[val]++;
        else m[val] = 1;
   }
   int counter = 0;
   for(map<int,int>::const_iterator it = m.begin(); it != m.end(); ++it ){
      int val = it->first;
      int cant = it->second;
      if(cant>val) counter += (cant-val);
      else if(cant<val) counter += cant;
    }
   cout << counter << endl;
}

Measured memory_bytes: 4736
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>

int main() {
  int M = 1e6;
  std::vector<int> p(M+1, 1);
  p[0] = p[1] = 0;
  for (int i = 2; i*i <= M; ++i) {
    if (!p[i]) continue;
    for (int j = i*i; j <= M; j += i)
      p[j] = 0;
  }

  std::vector<int> q;
  for (int i = 2; i <= M; ++i)
    if (p[i]) q.push_back(i);

  while (true) {
    int N, P;
    scanf("%d %d", &N, &P);
    if (N == -1 && P == -1) break;

    std::vector<int> C;
    auto it = std::upper_bound(q.begin(), q.end(), N);
    for (int i = 0; i < P; ++i)
      for (int j = 0; j <= i; ++j)
        C.push_back(it[i]+it[j]);

    std::sort(C.begin(), C.end());
    printf("%d\n", C[P-1]);
  }
}



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

int main() {
  
  int N;
  cin >> N;
  int flag = 0;
  
  for(int i=1; i<=9; i++){
  	for(int j=1; j<=9; j++){
    	if(i*j==N) flag = 1;
    }
  }
  
  if(flag==1) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define PI 3.141592653
#define rep(i,a,n) for(int i=a;i<(int)n;++i)
#define SZ(x) ((int)(x).size())	//size() unsigned -> int
#define descSort(a) sort(a.begin(),a.end(),std::greater<int>())
using namespace std;
typedef long long ll;
const ll INF = 1e9 + 7;
ll gcd(ll x,ll y){
    if(x%y==0)return y;
    return gcd(y,x%y);
}
int main(void){
    ll n;
    cin>>n;
    ll ans=n/11;
    ans*=2;
    ll mod=n%11;
    if(mod!=0){
        if(mod<=6){
            ans++;
        }else ans+=2;
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  vector<int>vec (N);
  for (int i = 0; i < N; i++){
    cin >> vec.at(i);
  }
  sort(vec.begin(), vec.end());
  int sum = 1;
  for (int i = 1; i < N; i++){
    if (vec.at(i - 1) < vec.at(i)){
    sum++;
    }
  }
  cout << sum << endl;
}



Measured memory_bytes: 3608
#include <bits/stdc++.h>
#define FORR(i, a, b)  for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b)  for (int i = (b); i >= (a); --i)
#define REPP(i, a, b)  for (int i = (a); i < (b); ++i)
#define REPD(i, a, b)  for (int i = (b); i > (a); --i)
#define fi             first
#define se             second
#define mp             make_pair
#define pb             push_back
#define pf             push_front
#define cmin(a, b)     if ((a) > (b)) (a) = (b)
#define cmax(a, b)     if ((a) < (b)) (a) = (b)
#define BIT(x, i)      (((x) >> (i)) & 1)
#define MASK(i)        (1LL << (i))
#define debug(x)       cout << (x) << "\n"
#define endl           "\n"
#define ii             pair <int, int>
#define ll             long long
#define reset(x)       memset(x, 0, sizeof(x))
#define mem(a, x)      memset(x, (a), sizeof(x))
#define task           ""
#define IO             freopen (task".inp","r",stdin),freopen (task".out","w",stdout);

using namespace std;

const int mod = 1007050321;
const int base = 521;
const int MOD = 998244353;
const int inf = 2e9;
const int N = 2e5 + 5;

int n, s;
vector<vector<int>> dp;

int main() {
    ios_base :: sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin >> n >> s;
    dp.resize(n+1, vector<int>(s+1));
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= s; ++j)
            dp[i][j] = 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i) {
        int x;
        cin >> x;
        for (int j = 0; j <= s; ++j) {
            dp[i][j] += 1LL * 2 * dp[i-1][j] % MOD;
            if (j >= x)
                dp[i][j] += dp[i-1][j-x];
            dp[i][j] %= MOD;
        }
    }
    cout << dp[n][s];
    return 0;
}


Measured memory_bytes: 38584
#define fi first
#define se second
#define mp make_pair
#define pb push_back

#define LOCAL 1

#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define dbg(...) cout<<#__VA_ARGS__ ": ["; for(auto e: __VA_ARGS__){cout<<e<<", ";} cout<<"]\n"
#define dbg1(...) cout<<#__VA_ARGS__ " "<< __VA_ARGS__ 
#else
#define dbg(...) 1;
#define dbg1(...) 1;
#endif

typedef long long ll;
typedef unsigned long long ull;
constexpr int R=5e6+69, INF=2e9+6969;

int x,n;
set <int> s;

int main()
{
	cin>>x>>n;
	for(int i=0;i<n;++i)
	{
		int aa;
		cin>>aa;
		s.insert(aa);
	}
	int licz=0;
	while(true)
	{
		if(s.find(x-licz)==s.end())
		{
			printf("%d\n", x-licz);
			break;
		}
		if(s.find(x+licz)==s.end())
		{
			printf("%d\n", x+licz);
			break;
		}
		licz++;
	}
	return 0;
}


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

int main(){
  int x1,y1,x2,y2;
  cin>>x1>>y1>>x2>>y2;
  cout<<x2-y2+y1<<' '<<x2-x1+y2<<' '<<x1-y2+y1<<' '<<y1+x2-x1;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void _main() {
  unsigned long long a, b, x;
  cin >> a >> b >> x;

  if (0 == a) cout << b/x + 1 << "\n";
  else cout << (b/x - (a-1)/x) << "\n";
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define loop(i,a,b) for(int i=a;i<b;i++)
#define test() int t;cin>>t;loop(test,1,t+1)
#define pb push_back
#define eb emplace_back
#define mkp make_pair
#define nl cout<<"\n"
#define sp cout<<" "
#define F first
#define S second
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<pii>
#define vll vector<pll>
#define prsp(v) loop(i,0,v.size())cout<<v[i],sp;nl;
#define prpsp(v) loop(i,0,v.size())cout<<v[i].F<<" "<<v[i].S<<" , ";nl;
#define prnl(v) loop(i,0,v.size())cout<<v[i],nl;nl;
#define prpnl(v) loop(i,0,v.size())cout<<v[i].F<<" "<<v[i].S,nl;nl;
#define MOD 1000000007
#define mod(n) (((n%MOD)+MOD)%MOD)
#define all(x) x.begin(),x.end()

const int N = 1e5+5;
int dx[] = {1,0,-1,0};
int dy[] = {0,1,0,-1};

ll c2( ll n )
{
    ll ans = n*(n-1);
    ans /= 2;
    return ans;
}

int main() 
{
    fastio();

    ll r,g,b,n;
    cin>>r>>g>>b>>n;

    ll ans = 0;
    loop(i,0,n/r+1)
    {
        ll rem = n - r*i;
        loop(j,0,rem/g+1)
        {
            ll remm = rem - j*g;
            if( remm%b == 0 )
                ans++;
        }
    }
    cout<<ans,nl;

    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>

int main() {
  unsigned N, M;
  std::cin >> N >> M;
  std::vector<std::vector<unsigned>> nm(N, std::vector<unsigned>(M));
  for (unsigned i = 0; i < N; ++i) {
    for (unsigned j = 0; j < M; ++j) {
      std::cin >> nm[i][j];
    }
  }
  unsigned min = N;
  std::vector<unsigned> cnt(M+1, 0);
  std::vector<unsigned> cur(N, 0);
  std::vector<bool> used(M, false);
  for (unsigned i = 0; i < M - 1; ++i) {
    std::fill(cnt.begin(), cnt.end(), 0);
    for (unsigned j = 0; j < N; ++j) {
      ++cnt[nm[j][cur[j]]];
    }
    unsigned max = 0;
    unsigned index = 0;
    for (unsigned j = 1; j <= M; ++j) {
      if (max < cnt[j]) {
        max = cnt[j];
        index = j;
      }
    }
    min = std::min(max, min);
    used[index] = true;
    for (unsigned j = 0; j < N; ++j) {
      while (used[nm[j][cur[j]]]) {
        ++cur[j];
      }
    }
  }
  std::cout << min << std::endl;
  return 0;
}

Measured memory_bytes: 640
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
    int N,L;
    cin>>N>>L;
    int aho[100000];
    int ans=0,ansnum;
    for(int i=0;i<N;i++)cin>>aho[i];
    for(int i=0;i<N-1;i++){
        if(ans<aho[i]+aho[i+1]){
            ans=aho[i]+aho[i+1];
            ansnum=i;
        }
    }
    if(L<=ans){
        puts("Possible");
        for(int i=0;i<ansnum;i++)cout<<i+1<<endl;
        for(int i=N-2;ansnum<i;i--)cout<<i+1<<endl;
        cout<<ansnum+1<<endl;
    }
    else puts("Impossible");
    return 0;
}


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

int main()
{
    int n;
    cin >> n;
    int now = 0;
    for (int i = 0; i < n; i++)
    {
        int x;
        scanf("%d", &x);
        if (x == now + 1)
            now = x;
    }
    if (now == 0)
        printf("-1\n");
    else
        printf("%d\n", n - now);
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
    int h,w,a,b;
    cin >> h >> w >> a >> b;
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(i<b&&j<a) cout << 1;
            else if(b<=i&&a<=j) cout << 1;
            else cout << 0;
        }
        cout << endl;
    }
}

Measured memory_bytes: 1280
class UnionFind:

    def __init__(self, N):
        self.parent = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N

    def find(self, n):
        if self.parent[n] != n:
            self.parent[n] = self.find(self.parent[n])
        return self.parent[n]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
            self.size[x] += self.size[y]
        else:
            self.parent[x] = y
            self.size[y] += self.size[x]
            if self.rank[x] == self.rank[y]:
                self.rank[y] = self.rank[y] + 1

    def same(self, x, y):
        return self.find(x) == self.find(y)

N, M, K = map(int, input().split())

UF = UnionFind(N)
F = [[] for _ in range(N)]
B = [[] for _ in range(N)]

for _ in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    F[a].append(b)
    F[b].append(a)

for _ in range(K):
    c, d = map(int, input().split())
    c, d = c - 1, d - 1
    B[c].append(d)
    B[d].append(c)

for i in range(N):
    for f in F[i]:
        UF.union(i, f)

ans = [UF.size[UF.find(i)]-1 for i in range(N)]

for i in range(N):
    ans[i] -= len(F[i])

for i in range(N):
    for b in B[i]:
        if UF.same(i, b):
            ans[i] -= 1

print(*ans, sep=' ')


Measured memory_bytes: 48428
#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    int mod = 1000000007;
    long long sum = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> A[i];
        sum += A[i];
        sum %= mod;
    }
 
    long ans = 0;
 
    //i について全探索する
    for (int i = 0; i < N; i++)
    {
        //A[i+1] ... A[N] の値を更新する
        sum -= A[i];
        if (sum < 0) sum += mod;
 
        ans += A[i] * sum;
        ans %= mod;
    }
 
    cout << ans << endl;
}

Measured memory_bytes: 4024
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;

int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n; cin >> n;
  if (n == 1 << __lg(n)) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
    auto write = [](int i, int j) -> void {
      cout << i << ' ' << j << '\n';
    };
    write(1, 2), write(n + 1, n + 2);
    write(2, 3), write(n + 2, n + 3);
    write(3, n + 1);
    for (int i = 4; i < n; i += 2) {
      write(1, i), write(1, i + 1);
      write(i, n + i + 1), write(i + 1, n + i);
    }
    if (~n & 1) {
      int x = n & -n;
      write(x, n);
      write(n - x + 1, 2 * n);
    }
  }
}

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

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

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

//typedef
//------------------------------------------
typedef long long LL;
typedef unsigned long long ULL;
typedef vector<LL> VLL;
typedef vector<VLL> VVLL;
typedef vector<string> VS;
typedef pair<LL, LL> PLL;

//container util
//------------------------------------------
#define ALL(a)  (a).begin(),(a).end()
#define PB push_back
#define MP make_pair
#define SORT(c) sort((c).begin(),(c).end())
#define COUT(x) cout<<x<<endl

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

//constant
//--------------------------------------------
const double PI = acos(-1.0);
const LL MOD = 1e9 + 7;
const ULL INF= 1e18;
const int dx[]{ 1,-1,0,0 }, dy[]{ 0,0,1,-1 };

//function
//--------------------------------------------
LL gcd(LL, LL);
bool isEven(LL);
void coutY();
void coutN();

int main() {
	LL k, x; cin >> k >> x;
	FOR(i, x - k + 1, k + x)cout << i << ' ';
}

LL gcd(LL a, LL b) {
	if (a == 0 || b == 0)return 0;
	if (a < b)swap(a, b);
	if (a % b == 0)return b;
	else gcd(b, a % b);
}
bool isEven(LL a) {
	return !((bool)(a % 2));
}
void coutY() {
	cout << "Yes" << endl;
	return;
}
void coutN() {
	cout << "No" << endl;
	return;
}

Measured memory_bytes: 256
#include<iostream>

using namespace std;

int main(){
  int N, M;

  cin >> N >> M;

  int numN = 1;
  for(int i = 1; i <= 2; i++){
    numN = numN * (N - i + 1) / i;
  }

  int numM = 1;
  for(int i = 1; i <= 2; i++){
    numM = numM * (M - i + 1) / i;
  }

  cout << numN + numM << endl;

  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

int main(){
  int N;
  cin >> N;
  set<int> s;
  int d;
  rep(i,N){
    cin >> d;
    s.insert(d);
  }
  cout << s.size() << endl;
  return 0;

}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <queue>

#define MAXN 55
#define MAXSILVER 2500

using ll = long long int;
std::vector< std::vector< std::pair<int, std::pair<int, ll> > > > g(MAXN);
//silver, transaction time for each gold
std::pair<ll, ll> trans[MAXN];
ll dist[MAXN][MAXSILVER];

std::pair<ll, std::pair<int, int> > mp(ll x, int y, int z)
{
    return std::make_pair(x, std::make_pair(y, z));
}

void solve(int start, int silver)
{
    std::priority_queue< std::pair<ll, std::pair<int, int> >,
                        std::vector< std::pair<ll, std::pair<int, int> > >,
                            std::greater<std::pair<ll, std::pair<int, int> > > > s;
    s.push(mp(0, start, silver));
    dist[start][silver] = 0;

    while (!s.empty())
    {
        std::pair<ll, std::pair<int, int> > top = s.top();
        s.pop();
        ll curdist = top.first;
        int v = top.second.first, silv = top.second.second;
        if (curdist > dist[v][silv]) continue;
//        if (s.size() > 100000) std::cout << s.size() << "\n";

        for (ll j = 1; j*trans[v].first + silv <= MAXSILVER-2; ++j)
        {
            ll t = j*trans[v].second;
            int nextsilv = silv + j*trans[v].first;

            if (dist[v][silv] + t < dist[v][nextsilv])
            {
                dist[v][nextsilv] = dist[v][silv] + t;
                s.push(mp(curdist + t, v, nextsilv));
            }
        }

        for (std::pair< int, std::pair<int, int> > nxtpr : g[v])
        {
            int nxt = nxtpr.first;
            int silvtaken = nxtpr.second.first;
            ll timetaken = nxtpr.second.second;

            if (silv - silvtaken < 0) continue;
            int nxtsilver = silv - silvtaken;

            if (dist[v][silv] + timetaken < dist[nxt][nxtsilver])
            {
                dist[nxt][nxtsilver] = dist[v][silv] + timetaken;
                s.push(mp(curdist + timetaken, nxt, nxtsilver));
            }
        }
    }
}

int main()
{
    int n, m, s;
    std::cin >> n >> m >> s;

    s = std::min(s, MAXSILVER-3);
    int x, y, a, b;
    while (m--)
    {
        std::cin >> x >> y >> a >> b; --x; --y;
        g[x].push_back(std::make_pair(y, std::make_pair(a, b)));
        g[y].push_back(std::make_pair(x, std::make_pair(a, b)));
    }

    for (int i = 0; i < n; ++i)
        std::cin >> trans[i].first >> trans[i].second;

    for (int i = 0; i < n; ++i)
        for (int j = 0; j < MAXSILVER-2; ++j)
            dist[i][j] = 1e15;
    solve(0, s);

    for (int i = 1; i < n; ++i)
    {
        ll ans = 1e15;
        for (int j = 0; j < MAXSILVER-2; ++j)
        {
            ans = std::min(ans, dist[i][j]);
        }

        std::cout << ans << "\n";
    }
}


Measured memory_bytes: 68972
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#define rep(i,a,n) for(ll i =(a);i<(n);i++)
#define urep(i,a,n) for(ll i = (a);i>=(n);i--)
#define all(x) (x).begin(),(x).end()
#define INF 1e9
const int mod = 1e9 + 7;
typedef long long ll;
using namespace std;
ll dx[4] = { 1,-1,0,0 };
ll dy[4] = { 0,0,1,-1 };
ll N, M, Q, H, W, D, L, R, K, X;
ll A;
ll B;
ll ans;
string S;
bool Prime[100001];
ll anstable[100001];
ll gcd(ll a, ll b) {
	if (b == 0)return a;
	else return gcd(b, a%b);
}
int main() {
	rep(i, 2, 100001)Prime[i] = true;
	for (int i = 2; i <= 100000; i++) {
		if (Prime[i] == true) {
			for (int j = i*2; j <= 100000; j += i) {
				Prime[j] = false;
			}
		}
	}
	rep(i, 2, 100001) {
		if (Prime[i] && Prime[(i + 1) / 2])anstable[i]++;
		anstable[i] += anstable[i - 1];
	}
	cin >> Q;
	rep(i, 0, Q) {
		ll l, r;
		cin >> l >> r;
		cout << anstable[r] - anstable[l-1] << endl;
	}
	cin >> ans;
	return 0;
}

Measured memory_bytes: 1536
n = int(input())
a = list(map(int, input().split()))

safe = set()
for i in range(n - 1):
    for j in range(i + 1, n):
        pro = a[i] * a[j]

        digit = [pro % (10 ** k) // (10 ** (k - 1)) for k in range(1, 10)]

        while digit[-1] == 0:
            digit = digit[:-1]

        if len(digit) == 1:
            safe.add(pro)
            continue

        flag = True
        for k in range(len(digit) - 1):
            if digit[k + 1] - digit[k] != -1:
                flag = False
                break

        if flag:
            safe.add(pro)

if safe:
    print(max(safe))
else:
    print(-1)


Measured memory_bytes: 5624
import java.util.*;

public class Main {
    public static Scanner Scan = new Scanner(System.in);

    public static void main(String[] args) {
        long x = Scan.nextLong();
        long k = Scan.nextLong();
        long d = Scan.nextLong();

        x = Math.abs(x);
        long cnt = Math.min(k, x / d);
        x -= cnt * d;
        k -= cnt;
        if(k % 2 == 1) x = Math.abs(x - d);

        System.out.println(x);
    }
}

Measured memory_bytes: 35904
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	int N;
	cin >> N;
	vector<pair<int, int>> A(N);
	for (int i = 0; i < N; ++i) {
		cin >> A[i].first;
		A[i].second = i + 1;
	}
	sort(A.begin(), A.end());
	for (auto &e : A) {
		cout << e.second << " ";
	}
	cout << endl;
}


Measured memory_bytes: 1664
/*																													   
 Templatka c++ Kacper Fis																							   																											   //
*/																													  
																								   
#include <bits/stdc++.h>																							   
																													   
using namespace std; 																								   
		
const double eps = 1e-9;																							   
const int INF = 1000000001;																						   
const float PI = 3.14;																								   
typedef long long LL;																								   
																													   
typedef vector<int> vi;																								   
typedef list<int> li;																								   
typedef queue<int> qi; 																								   
typedef pair<int,int> ii; 																							   
typedef map<string,int> msi; //np msi['nazwa'] = 'liczba'															   
typedef vector<ii> vii; //vector par<int>, do tworzenia tablicy dla grafów wagowych #dijkstra #Bellman_Ford			   
typedef priority_queue< ii, vector<ii>, greater<ii> > pq; //kolejka priorytetowa vectorów par(top()=min) #dijkstra	   
																													   																				   
vector<ii>::iterator iter;																							   
																													   																				   
#define print_list(x) for(it = (x).begin(); it != (x).end(); it++) {cout << *it << " ";}							   
#define print_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++) {cout << *it2 << " ";}						   
#define search_list(x) for(it = (x).begin(); it != (x).end(); it++)													   
#define search_vector(x) for(it2 = (x).begin(); it2 != (x).end(); it2++);											   
#define pb(x) push_back(x) 																							   
#define pf(x) push_front(x)																							   
#define mp(x, y) make_pair(x, y)                                                                                       
///////////////////////////////////////////////GLOBAL DEFINITIONS////////////////////////////////////////////////////////


///////////////////////////////////////////////////FUNCTIONS/////////////////////////////////////////////////////////////


/////////////////////////////////////////////////////MAIN////////////////////////////////////////////////////////////////
int main()																					 
{ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);                  												       
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < m; i++){
		int x;
		cin >> x;
		n -= x;
	}
	
	if(n < 0) cout << -1 << endl;
	else cout << n << endl;
	
	
	

	
	return 0;
 }


Measured memory_bytes: 3656