akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
int main() {
  string s,t; cin>>s>>t;
  for(int i=0; i<s.length(); i++){
    if(s.substr(i+1)+s.substr(0,i+1)==t){
      cout<<"Yes";
      return 0;
    }
  }
  cout<<"No";
}

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

int main() {
  int X;
  cin >> X;
  int N;
  cin >> N;
  
  int min = INF, num, def;
  vector<int> p(N);
  rep(i,N) cin >> p.at(i);
  bool nt = false;
  rep(i,102) {
    nt = false;
    rep(j,N){if(i == p.at(j)){nt = true; break;}}
    if(nt) continue;
    
    def = abs(i-X);
    
    if(min > def){
      min = def;
      num = i;
    }
  }
  
  cout << num << endl;
  
}


Measured memory_bytes: 3632
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
int main()
{
	int T;
	ll a,b,c,d;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
		if (d<b || a<b) {printf("No\n");continue;}
		ll x=(a%b);
		ll cha=(d%b);
		if (x>c && x<b || x+d<b) {printf("No\n");continue;}
		if (cha==0) 
		{
			if (a>=b)printf("Yes\n");
			else printf("No\n");
			continue;
		}
		else
		{
			ll t;
			if (c>=x)
			{
				t=(c-x)/cha+1;
				t=x+t*cha;
				if (t-cha>c)
				t-=cha;	
			}
			else t=x;
			ll ans=t;
			for(int i=1;i<=10000;i++)
			{
				if (t>=b)
				{
					x=t-b;
					t=(c-x)/cha+1;
					t=x+t*cha;
					if (t-cha>c)
					t-=cha;
					ans=min(ans,t);
				}
				else break;
			}
			if (ans<b)
			printf("No\n");
			else printf("Yes\n");
		}
	}
}

/* 14 9 7 13 */

Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int A, B, C;
    cin >> A >> B >> C;

    int ans = 0;
    int flag = A % 2 + B % 2 + C % 2;
    if (flag == 1 || flag == 2) {
        for (auto num : {&A, &B, &C})
            if (*num % 2 == flag - 1) (*num)++;
        ans++;
    }

    int max_ = max({A, B, C});
    for (int num : {max_ - A, max_ - B, max_ - C})
        ans += num / 2;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
using System;
class Program
{
    static void Main()
    {
        var N = int.Parse(Console.ReadLine());
        var S = Console.ReadLine();
        int left = 0;
        for (int i = 0; i < N; i++)
        {
            if (S[i] == '(')
            {
                left++;
            }
            else
            {
                if (left > 0)
                {
                    left--;
                }
                else
                {
                    S = "(" + S;
                    N++;
                    i++;
                }
            }
        }
        while (left-- > 0)
        {
            S = S + ")";
        }
        Console.WriteLine(S);
    }
}


Measured memory_bytes: 13140
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        // Your code here!
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        if(a + b + c == 17){
            System.out.println("YES");
        }else{
            System.out.println("NO");
        }
    }
}


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

int main(){
  vector<int> A(3);
  for (int i = 0; i < 3; i++) {
    cin >> A.at(i);
  }
  sort(A.begin(),A.end());
  cout << A.at(2)-A.at(0) << endl;
}


Measured memory_bytes: 256
package main

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

var sc *bufio.Scanner = func() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}()

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func main() {
	n := nextInt()
	ints := make([]int, n)
	for i := 0; i < n; i++ {
		ints[i] = nextInt()
	}
	sum := 0
	for i := 0; i < n; i++ {
		v := ints[i] - nextInt()
		if v >= 0 {
			sum += v
		}
	}
	fmt.Println(sum)
}


Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
//Author: Ezio Sam
/* Shorthands */
#define ll long long
#define pb push_back 
#define mp make_pair
#define sp ": "
#define cs "Case "
#define fi first
#define sn second 
#define po(x) x*x
/* STL */
#define vi vector<int>v
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mem(a,n) memset(a, n, sizeof(a));
#define all(x) x.begin(),x.end()
#define sz(x)  (int)x.size()
#define mx(v)  *max_element(v.begin(),v.end())
#define mxa(a) *max_element(a, a.size())
#define r(a) reverse(a.begin(),a.end())
/* loops */
#define fr(i,n)   for(__typeof(n) i=0;i<(n);i++)
#define fn(i,n)   for(__typeof(n)i=1;i<=(n);i++)
#define fa(i,a,n) for(__typeof(a)i=(a);i<=(b);i++)
/*Special*/
#define Ezio ios::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
#define db(something)   cerr<<#something<<" - "<<something<<"\n";         
int main()
{
  
   Ezio
   /*Variables*/
   /*Code*/
   string s;
   cin>>s;
   for(auto x:s){
     if(x=='7'){
         cout<<"Yes"<<endl;
         return 0;
       }
    }
    cout<<"No"<<endl;
   return 0;
}
    

Measured memory_bytes: 3632
#include <stdio.h>
int main(void){int a,b;
char op;

while(1){
scanf("%d %c %d",&a,&op,&b);
    // Your code here!
if(op=='?')break;
if(op=='+'){printf("%d\n",a+b);}
if(op=='-'){printf("%d\n",a-b);}
if(op=='*'){printf("%d\n",a*b);}
if(op=='/'){printf("%d\n",a/b);}
    
}
}


Measured memory_bytes: 2720
#include <iostream>
#include <vector>
using namespace std;
const int MOD = 1000000007;

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

    vector<bool> is_prime(n+1, true);
    is_prime[0] = is_prime[1] = false;
    for(int i = 2; i*i <= n; i++){
        if(is_prime[i]){
            for(int j = 2; i*j <= n; j++) is_prime[i*j] = false;
        }
    }
    vector<int> prime;
    for(int i = 0; i <= n; i++){
        if(is_prime[i]) prime.push_back(i);
    }

    vector<long long int> pfactor(prime.size(), 1);
    for(int i = 2; i <= n; i++){
        int num = i;
        for(int j = 0; num > 1 && j < prime.size(); j++){
            while(num % prime[j] == 0){
                pfactor[j]++;
                num /= prime[j];
            }
        }
    }

    long long int ans = 1;
    for(int i = 0; i < pfactor.size(); i++){
        ans *= pfactor[i];
        ans %= MOD;
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

int main()
{
    int n,arr[300005];
    cin>>n;
    int m=n*3;
    for(int i=0;i<m;i++)
    {
        cin>>arr[i];
    }
    sort(arr,arr+m);
    long long sum=0;
    int cnt=0;

   for(int i=m-2;cnt<n;i-=2)
   {
       sum+=arr[i];
       cnt++;
   }
   cout<<sum<<endl;
}


Measured memory_bytes: 1408
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define FOR(i,l,r) for(i=l;i<r;i++)
#define REP(i,n) FOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define P pair<ll,ll>
#define F first
#define S second
signed main(){
  ll N,i=0;cin>>N;while(i*(i-1)<2*N)i++;
  if(i*(i-1)==2*N){
    cout<<"Yes"<<endl<<i<<endl;ll j,k;
    REP(j,i-1){
      cout<<i-1;REP(k,j)cout<<" "<<j+1+k*(i-1)-k*(k+1)/2;
      REP(k,i-j-1)cout<<" "<<j+1+j*(i-1)-j*(j+1)/2+k;cout<<endl;
    }
    cout<<i-1;REP(k,i-1)cout<<" "<<1+k*(i-1)-k*(k-1)/2;cout<<endl;
  }
  else cout<<"No"<<endl;
  return 0;
}

Measured memory_bytes: 3640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, begin, end) for (int i = begin; i < (int)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    int D, G;
    cin >> D >> G;
    vector<int> p(D), c(D), point(D);
    rep(i, 0, D)
    {
        cin >> p.at(i) >> c.at(i);
        point.at(i) = p.at(i) * (i + 1) * 100 + c.at(i);
    }
    int ans = 1000;
    int count, sum, max;
    for (int tmp = 0; tmp < (1 << D); tmp++)
    {
        bitset<10> bit(tmp);
        sum = 0;
        count = 0;
        max = 0;
        rep(i, 0, D)
        {
            if (bit.test(i))
            {
                sum += point.at(i);
                count += p.at(i);
            }
            else if (max < i)
            {
                max = i;
            }
        }
        if (sum >= G)
        {
            if (ans > count)
            {
                ans = count;
            }
        }
        else
        {
            rep(j, 0, p.at(max))
            {
                count++;
                sum += 100 * (max + 1);
                if ((sum >= G) && (ans > count))
                {
                    ans = count;
                }
            }
        }
    }
    cout << ans << endl;
}

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

using namespace std;

vector<vector<int> > adjList;
bool visited[100010];
int dp[100010];
void dfs(int curr)
{
	if (visited[curr])
		return;
	visited[curr] = true;
	for (int i = 0; i < adjList[curr].size(); i++)
	{
		dfs(adjList[curr][i]);
		dp[curr] = max(dp[curr], 1 + dp[adjList[curr][i]]);
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	adjList.resize(n + 1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		adjList[a].push_back(b);
	}
	
	for (int i = 1; i <= n; i++)
		if (!visited[i])
			dfs(i);
	int out = 0;
	for (int i = 0; i <= n; i++)
		out = max(out, dp[i]);
	cout << out << endl;
}

Measured memory_bytes: 7552
/*
  #問題：
  


  #分析：
  #オブジェクト：
  
  #条件：
  

  #要求：
  

  #解法：
  
*/

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <fstream>
#include <sstream>
#include <set>
#include <map>
#include <vector>
#include <list>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>     //UWAGA - w czasie kompilacji musi byc znany rozmiar wektora - nie mozna go zmienic
#include <cassert>
#include <iomanip>        //do setprecision
#include <ctime>
#include <complex>
#include <initializer_list>
#define FOR(i,b,e) for(int i=(b);i<(e);++i)
#define FORQ(i,b,e) for(int i=(b);i<=(e);++i)
#define FORD(i,b,e) for(int i=(b)-1;i>=(e);--i)
#define REP(x, n) for(int x = 0; x < (n); ++x)

#define ST first
#define ND second
#define PB push_back
#define MP make_pair
#define LL long long
#define uLL unsigned LL
#define LD long double

const double pi = 3.141592653589793238462643383279502884197169399375105820974944592307816406286208998628034825342;
const int mod=1000000007;


const unsigned int BIT_FLAG_0 = (1<<0);
const unsigned int BIT_FLAG_1 = (1<<1);
const unsigned int BIT_FLAG_2 = (1<<2);
const unsigned int BIT_FLAG_3 = (1<<3);
const unsigned int BIT_FLAG_4 = (1<<4);
const unsigned int BIT_FLAG_5 = (1<<5);
const unsigned int BIT_FLAG_6 = (1<<6);
const unsigned int BIT_FLAG_7 = (1<<7);


#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>
using namespace std;
namespace mp = boost::multiprecision;

using Bint = mp::cpp_int;



int main(void){
  uLL N; // Nは「店」の数を表す． N<10^5
  uLL M; // Mは買いたい栄養ドリンクの本数． M<10^5
  cin>>N>>M;

  // A_{i}は，店S_iでの栄養ドリンクの「値段」． A_i < 10^9
  // B_{i}は，店S_iで買える栄養ドリンクの「本数」． B_i < 10^9

  // vector<uLL> A(N);
  // vector<uLL> B(N);
  uLL a,b;
  priority_queue < pair<uLL,uLL>, vector<pair<uLL,uLL>>, greater< pair<uLL,uLL> >  > que;
  vector< pair<uLL, uLL> > S(N);
  pair<uLL,uLL> T=MP(0,0);
  uLL num=0;
    
  Bint wallet=0;
  FOR(i,0,N){
    // cin>>A[i];                  // A_iは店S_iでの栄養ドリンクの値段
    // cin>>B[i];                  // B_iは店S_iで買える栄養ドリンクの「本数」
    cin>>a>>b;
    S[i].ST=a; S[i].ND=b;
    que.push(S[i]);
  }

  while( !que.empty() ){
    if(M < num) {break;}
    T=que.top();
    que.pop();
    a=T.ST; b=T.ND;
    wallet += a*b;
    num+=b;
    // cerr<<"wallet: "<<wallet<<"   num of Drink: "<<num<<endl;
  }

  while(1){
    if(M == num){break;}
    wallet -= a;
    num--;
    // cerr<<"wallet: "<<wallet<<"   num of Drink: "<<num<<endl;
  }
  // wallet += a;
  // num++;
  // cerr<<"wallet: "<<wallet<<"   num of Drink: "<<num<<endl;
  cout<<wallet<<endl;
  return 0;
}



Measured memory_bytes: 3956
import numpy as np
n = int(input())
A = [int(x) for x in input().split()]
sum_start_plus = 0
sum_start_minus = 0
ans_start_plus = 0
ans_start_minus = 0

# プラス始まりの場合を計算する
for i in range(n):
    sum_start_plus += A[i]
    if i % 2 == 0:
        if np.sign(sum_start_plus) == 1:
            continue
        else:
            ans_start_plus += abs(1 - sum_start_plus)
            sum_start_plus = 1
    else:
        if np.sign(sum_start_plus) == -1:
            continue
        else:
            ans_start_plus += abs(-1 - sum_start_plus)
            sum_start_plus = -1

# マイナス始まりの場合を計算する
for i in range(n):
    sum_start_minus += A[i]
    if i % 2 == 0:
        if np.sign(sum_start_minus) == -1:
            continue
        else:
            ans_start_minus += abs(-1 - sum_start_minus)
            sum_start_minus = -1
    else:
        if np.sign(sum_start_minus) == 1:
            continue
        else:
            ans_start_minus += abs(1 - sum_start_minus)
            sum_start_minus = 1

print(min(ans_start_plus, ans_start_minus))

Measured memory_bytes: 23336
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll l,r;
    cin >> l >> r;
    if(r-l+1 >= 2019){
        cout << 0 << endl;
        return 0;
    }
    ll sol = 2020;
    for(ll i = l; i <= r; i++){
        for(ll j = i+1; j <= r; j++){
            sol = min(sol,(i*j)%2019);
        }
    }
    cout << sol << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define lli long long int
using namespace std;
int main()
{
//fastio;
int a,b,c;
cin>>a>>b>>c;
int x;
x=10*a;
x+=b;
x+=c;
int y=10*b;
y+=a;
y+=c;
int q=10*c;
q+=a;
q+=b;

int z;
z=max(x,y);
z=max(z,q);
cout<<z;

}


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

char s[100009],s2[100009];
int mm,len;

int main(){
	cin>>s;	len=strlen(s);	mm=len-1;
	for(int i=0;i<len;i++){
		s2[mm]=s[i];	mm--;
	}
	for(int i=0;i<len;i++){
		if(s2[i]=='b'){
			s2[i]='d';	continue;
		}
		if(s2[i]=='d'){
			s2[i]='b';	continue;
		}			
		if(s2[i]=='p'){
			s2[i]='q';	continue;
		}		
		if(s2[i]=='q'){
			s2[i]='p';	continue;
		}
	}
	for(int i=0;i<len;i++){
		if(s[i]!=s2[i]){
			printf("No");	return 0;
		}
	}
	printf("Yes");
	return 0;
}

Measured memory_bytes: 384
import sys
sys.setrecursionlimit(1000000)
n=int(input())
visitedlist=[-1 for  i in range(n)]
kilist=[[] for i in range(n)]
anslist=[0 for i in range(n)]
searchedlist=[-1 for i in range(n)]
for i in range(n-1):
        a,b,c=map(int,input().split())
        kilist[a-1].append((b,c))
        kilist[b-1].append((a,c))        
def search(i):
        searchedlist[i-1]=1
        visitedlist[i-1]=1
        flag=0
        for j in kilist[i-1]:
            if visitedlist[j[0]-1]<0:
                visitedlist[j[0]-1]=1
                flag+=1
                anslist[j[0]-1]=anslist[i-1]+j[1]
        else:
            pass

        if flag>0:    
            for k in kilist[i-1]:
                if searchedlist[k[0]-1]==-1:
                    search(k[0])
q,k=map(int,input().split())
List=[0 for i in range(q)]
search(k)
for i in range(q):
    x,y=map(int,input().split())
    List[i]=anslist[x-1]+anslist[y-1]
for j in List:
    print(j)


Measured memory_bytes: 134740
s = input()

k = 0
devided = []
current = ""
for i in range( len( s ) ):
  #############################
  #print( i )
  #############################
  current += s[i]
  if i == 0:
    devided.append( current )
    current = ""
  elif current == devided[-1]:
    pass # 次と結合
  else:
    devided.append( current )
    current = ""
  
print( len( devided ) )
#############################
#print( devided )
#############################

Measured memory_bytes: 8296
#include <bits/stdc++.h>
		using namespace std;
		
		typedef long long ll;
		#define pi 3.14159265 
		#define EPS 1e-8
		
		#define mod 1000000007
		#define fi first
		#define se second
		#define mp make_pair
		#define pb push_back
		#define endl "\n"

		const ll INF=(ll)2e18;
		
		long long binpow(long long a, long long b, long long m) {
		a %= m;
		long long res = 1;
		while (b > 0) {
			if (b & 1)
				res = res * a % m;
			a = a * a % m;
			b >>= 1;
		}
		return res;
		}
		
		
		int main()
		{
			 ios_base::sync_with_stdio(false);
			 cin.tie(NULL);
			
			 ll a[3];
			 cin>>a[0]>>a[1]>>a[2];
			 swap(a[0],a[1]);
			 swap(a[0],a[2]);
			 cout<<a[0]<<" "<<a[1]<<" "<<a[2];
		}


Measured memory_bytes: 256
A, B, K = gets.chomp.split.map(&:to_i)

if K <= A
  A = A - K
  K = 0
end

if A <= K
  K = K - A
  A = 0
end

if K <= B
  B = B - K
  K = 0
end

if B <= K
  K = K - B
  B = 0
end

K.times do |i|
  if 1 <= A
    A -= 1
  elsif 1 <= B
    B -= 1
  else A == 0 && B == 0
    break
  end
end

puts ("#{A} #{B}")

Measured memory_bytes: 1788
// https://atcoder.jp/contests/abc076/tasks/abc076_c
// Difficulty: 820
// 2020/01/26 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define INF (1LL<<50)
#define MOD 1000000007

int main(){
    string S;
    string T;
    cin >> S;
    cin >> T;
    int S_len = S.length();
    int T_len = T.length();
    for(int i=S_len-T_len;i>=0;i--){
        bool OKflg = true;
        string S_sub = S.substr(i,T_len);
        for(int j=0;j<T_len;j++){
            if(S_sub[j]=='?')continue;
            if(S_sub[j]==T[j])continue;
            else OKflg = false;
        }
        if(OKflg){
            for(int k=0;k<S_len;k++){
                if(k!=i&&S[k]=='?'){
                    S[k]='a';
                }
            }
            S.replace(i,T_len,T);
            cout << S << endl;
            return 0;
        }
    }
    cout << "UNRESTORABLE" << endl;
    return 0;
}

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

using ll = long long;
using namespace std;

struct grid {
    int x, y;
};

int main() {
    int h, w;
    cin >> h >> w;
    vector<string> mp(h);
    for (int i = 0; i < h; i++) {
        cin >> mp[i];
    }
    int count[h][w] = {};
    for (int i = 0; i < h; i++) {
        for (int k = 0; k < w; k++) {
            count[i][k] = 1e9;
        }
    }
    count[0][0] = mp[0][0] == '#';
    for (int i = 0; i < h; i++) {
        for (int k = 0; k < w; k++) {
            if (i > 0) {
                count[i][k] = min(count[i][k], count[i - 1][k] + (mp[i - 1][k] == '.' && mp[i][k] == '#'));
            }
            if (k > 0) {
                count[i][k] = min(count[i][k], count[i][k - 1] + (mp[i][k - 1] == '.' && mp[i][k] == '#'));
            }
        }
    }
    cout << count[h - 1][w - 1] << endl;
    return 0;
}


Measured memory_bytes: 256
open System
open System.Collections.Generic

[<AutoOpen>]
module FastIO =
    let reader = new IO.StreamReader(new IO.BufferedStream(Console.OpenStandardInput()))
    let inline read f = reader.ReadLine() |> f
    let inline reada f = reader.ReadLine().Split() |> Array.map f
    let inline readChars() = read string |> Seq.toArray
    let inline readInts() = readChars() |> Array.map (fun x -> Convert.ToInt32(x.ToString()))

    let writer = new IO.StreamWriter(new IO.BufferedStream(Console.OpenStandardOutput()))
    let inline write (s: string) = writer.Write s
    let inline writeln (s: string) = writer.WriteLine s
    let inline puts (s: ^a) = string s |> writeln

    let inline ioDispose() =
        reader.Dispose()
        writer.Dispose()

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

// -----------------------------------------------------------------------------------------------------
let main() =
    let n = read int
    let st = SortedDictionary<string, int>(StringComparer.Ordinal)
    for i in 0 .. n - 1 do
        let s = read string
        if st.ContainsKey(s) then st.[s] <- st.[s] + 1 else st.Add(s, 1)
    let cnt = Seq.maxBy (fun (kv: KeyValuePair<string, int>) -> kv.Value) st
    for kv in st do
        if cnt.Value = kv.Value then puts kv.Key
    ()
// -----------------------------------------------------------------------------------------------------
main()
ioDispose()


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

//#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
//using namespace __gnu_pbds;

#define ss second
#define ff first
#define int long long
//#define double long double
#define pb push_back


const int N = 1e6 + 51 + 51, MOD = 1e9 + 7, mod = 998244353, INF = 3e18;

mt19937 Flash_new_51(51515);

using vi = vector <int>;
using vp = vector <pair <int, int>>;

//gp_hash_table<int, int> table;
int dp[N], dp1[N], a[20][20];

signed main() {
    #ifdef Flash
     freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int msk, n;
    cin >> n;
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) cin >> a[i][j];
    msk = (1 << n);
    vi ans;
    for (int mask = 5; mask < msk; mask++) {
        ans.clear();
        for (int j = 0; j < n; j++) {
            if ((mask >> j) & 1) ans.pb(j);
        }
        for (int i = 0; i < ans.size(); i++) {
            for (int j = i + 1; j < ans.size(); j++) {
                int l = ans[i], r = ans[j];
                dp1[mask] += a[l][r];
            }
        }
    }
    for (int mask = 0; mask < msk; mask++) {
        dp[mask] = dp1[mask];
        int sub = mask;
        for (; sub > 0; sub = (sub - 1) & mask) {
            dp[mask] = max(dp[mask], dp[sub] + dp[sub ^ mask]);
        }
    }
    cout << dp[msk - 1];

}


Measured memory_bytes: 4864
#include <stdio.h>
int main(void)
{
int x,y;
int a;
while(1){
scanf("%d%d",&x,&y);
if(x==0&&y==0)break;
if(x>y){
a=x;
x=y;
y=a;}
printf("%d %d\n",x,y);
}
}


Measured memory_bytes: 2024
#include <bits/stdc++.h> 
using namespace std;
const int N = 6000 + 5;

int main()
{
	int l,r,d;
	cin >> l >> r >> d;
	int z = (r/d-l/d);
	if(l%d == 0)
		z++; 
	cout << z << endl; 
	return 0;
}

Measured memory_bytes: 3616
#include <iostream>
#include <queue>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstdlib>
#include <map>
#include <memory.h>
#include <vector>
using namespace std;

#define rep(i, n) for(int i = 0; i < n; i++)
const double EPS = 1e-12;
const int INF = 1 << 29;

double cprob[100][100];
double P[110];
double T[110];
double V[110];

double comb(int n, int r){
  double res = 1.0;
  r = min(n - r, r);
  rep(i, r){
    res = res * (n - i) / (i + 1);
  }
  return res;
}

double getp(int M, int j, int id){
  double res = comb(M, j);
  rep(i, j) res *= P[id] / 100.0;
  rep(i, M - j) res *= (1 - P[id] / 100.0);
  return res;
}

int main(){
  int N, M, L;
  double prob, p, p2;
  while(cin >> N >> M >> L && (N || M || L)){
    rep(i, N){
      cin >> P[i] >> T[i] >> V[i];
    }
    rep(i, N)rep(j, M + 1) cprob[i][j] = getp(M, j, i);
    rep(i, N){
      prob = 0.0;
      rep(j, M + 1){
	p = getp(M, j, i);
	double need = (double)L / V[i] + j * T[i];
	rep(k, N){
	  double p1 = 0.0;
	  if(i == k) continue;
	  rep(l, M + 1){
	    p2 = cprob[k][l];
	    double ene = (double)L / V[k] + l * T[k];
	    if(ene > need) {
	      p1 += p2;
	    }
	  }
	  p *= p1;
	}
	prob += p;
      }
      cout << fixed << setprecision(12) << prob << endl;
    }
    
  }
  return 0;
}

Measured memory_bytes: 1080
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < n; i++)
#define MOD 1000000007
#define MOD2 998244353
#define INF ((1<<30)-1)
#define LINF (1LL<<60)
#define EPS (1e-10)
typedef long long Int;
typedef pair<Int, Int> P;

void str_replace(string &s, string target, string replacement) {
    if (!target.empty()) {
        string::size_type pos = 0;
        while ((pos = s.find(target, pos)) != string::npos) {
            s.replace(pos, target.length(), replacement);
            pos += replacement.length();
        }
    }
}

int64_t stoint64(string s) {
    int64_t ret = 0;
    int n = s.size();
    for (int i = 0; i < n; i++) {
        ret += (s[i] - '0') * pow(10, n-i-1);
    }
    return ret;
} 

int main() {
    Int a;
    string b;
    cin >> a >> b;
    str_replace(b, ".", "");
    Int ib = stoint64(b);   
    Int ans = a * ib / 100;
    printf("%lld\n", ans);
}

Measured memory_bytes: 3924
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

int main(int ac, char **av) {
  int n;
  while (cin >> n, n) {
    vector<int> a;
    for (int i = 0; i < n; i++) {
      int t;
      cin >> t;
      a.push_back(t);
    }
    auto mx = -1000000000;
    auto ms = a[0];
    for (auto it = ++begin(a); it != end(a); it++) {
      mx = max(mx, *it - ms);
      ms = min(ms, *it);
    }
    cout << mx << endl;
    n = 0;
  }
  return 0;
}

Measured memory_bytes: 3808
from bisect import bisect_left
from operator import mul
from functools import reduce

N, A, B = map(int, input().split())
V = list(map(int, input().split()))

V.sort(reverse=True)




def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

print(sum(V[:A])/len(V[:A]))

c = 0
for i in range(A-1, B):
    if V[i] == V[A-1]:
        c += 1
#print(V, V[A-1])

for i, v in enumerate(V):
    if v == V[A-1]:
        ia = i
        break
l = A - ia
maxl = V.count(V[A-1])
#print(A, ia, l, maxl, c)
if ia == 0:
    ans = 0
    for d in range(c):
        ans += cmb(maxl, l+d)
else:
    ans = cmb(maxl, l)
print(ans)

Measured memory_bytes: 3816
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int , int> P;
typedef pair<ll, ll> PL;
const int INT_INF = 2147483646;
const ll LL_INF = 9223372036854775807;

bool SecondCompare(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}
 
bool SecondCompareDes(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second>b.second;
}
 
ll a,b,c;
string s;

int main(){
    cin >> a >> b >> c;

    ll ans = 0;
    if(b >= c-1){
        ans = b+c;
    }
    else{
        if(a+b >= c-1){
            ans = b+c;
        }
        else{
            ans = b*2+a+1;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
import bisect

import sys
stdin=sys.stdin

ip=lambda: int(sp())
fp=lambda: float(sp())
lp=lambda:list(map(int,stdin.readline().split()))
sp=lambda:stdin.readline().rstrip()
yp=lambda:print('Yes')
np=lambda:print('No')

n=ip()
a=lp()
b=lp()
c=lp()

a.sort()
b.sort()
c.sort()
ans=0

for i in range(n):
  x=bisect.bisect_left(a,b[i])
  y=bisect.bisect_right(c,b[i])
  ans+=x*(n-y)
  
print(ans)




Measured memory_bytes: 29792
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;
using System.Text.RegularExpressions;

class Program
{
    const string Yes = "Yes";
    const string No = "No";
    const char White = '.';
    const char Black = '#';
    const long Mod = 1000000007;

    static void Main(string[] args) {
#if DEBUG
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var n = long.Parse(input.ReadLine());

        var x = Math.Max(n / 11 - 1, 0);

        n -= 11*x;

        x*=2;

        var b = true;
        while(n > 0) {
            n -= b ? 6 : 5;
            x++;
            b = !b;
        }

        return x;
    }

    static int[] ToIntArray(string strs, int n) {
        var ret = new int[n];
        var spl = strs.Split(' ');
        for (int i = 0; i < n; i++)
            ret[i] = int.Parse(spl[i]);
        return ret;
    }
}


Measured memory_bytes: 13140
import java.util.*;

public class Main {
    public static void main(String[] args){
        long INF = 1000000000000000001L;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long k = sc.nextLong();
        long[] aArray = new long[n];
        for (int i = 0; i < n; i++) {
            aArray[i] = sc.nextLong();
        }
        long l = -INF;
        long r = INF;
        aArray = Arrays.stream(aArray).sorted().toArray();
        while (l + 1 < r) {
            long x = (l + r) / 2L;
            long tot = 0L;
            boolean ok = false;

            for (int i = 0; i < n; i++) {
                int l2 = -1;
                int r2 = n;
                if (aArray[i] < 0L) {
                    while (l2 + 1 < r2) {
                        int c = (l2 + r2) / 2;
                        if (aArray[i] * aArray[c] < x) {
                            r2 = c;
                        } else {
                            l2 = c;
                        }
                    }
                    tot += n - r2;
                } else {
                    while (l2 + 1 < r2) {
                        int c = (l2 + r2) / 2;
                        if (aArray[i] * aArray[c] < x) {
                            l2 = c;
                        } else {
                            r2 = c;
                        }
                    }
                    tot += r2;
                }
                if(aArray[i] * aArray[i] < x) {
                    tot--;
                }
            }
            tot = tot / 2;
            if (tot < k) {
                ok = true;
            } else {
                ok = false;
            }
            if (ok) {
                l = x;
            } else {
                r = x;
            }
        }
        System.out.println(l);
    }
}

Measured memory_bytes: 62904
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define int ll
#define double ld
#define faster ios_base::sync_with_stdio(false);
typedef pair<int,int> pii;
///------------------------------------------------------------------------
const int inf=1e18;
const int mod=1e9+7;
ifstream in("input.txt");
ofstream out("output.txt");
signed main()
{
    int n;
    cin>>n;
    vector<int>vec(n);
    for(int i=0; i<n; i++)
        cin>>vec[i];
    vector<int>dp(n);
    dp[1]=abs(vec[1]-vec[0]);
    for(int i=2; i<n; i++)
    {
        dp[i]=min(dp[i-1]+abs(vec[i]-vec[i-1]),dp[i-2]+abs(vec[i]-vec[i-2]));
    }
    cout<<dp[n-1];
    return 0;
}


Measured memory_bytes: 1792
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N = int(read())

U = 10**6
is_prime = np.zeros(U, np.bool_)
is_prime[2] = 1
is_prime[3::2] = 1
for p in range(3, U, 2):
    if p * p >= U:
        break
    if is_prime[p]:
        is_prime[p * p::p * p] = 0

primes = is_prime.nonzero()[0]


def factor(N):
    div = primes[N % primes == 0]
    for p in div:
        e = 0
        while N % p == 0:
            e += 1
            N //= p
        yield (p, e)
    if N != 1:
        yield (N, 1)


A = np.zeros(100, np.int32)
for i in range(14):
    k = i * (i + 1) // 2
    A[k] = i
np.maximum.accumulate(A, out=A)

x = 0
for p, e in factor(N):
    x += A[e]
print(x)


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

typedef long long ll;
typedef long double ld;
#define pi 3.14159265359;
#define inf (1 << 21);
#define mod 1000000007;

int main() {
    ll N; cin >> N;
    ll Nsave = N;
    ll n = (ll)sqrt(N);
    vector<int> cnt(n);
    for (int i = 2; i < n; i++) {
        while (N % i == 0) {
            cnt.at(i)++;
            N /= i;
        }
    }
    bool prime = true;//最終的なNが素数かどうかを判定
    for (int i = 2; i < n; i++) {
        if (N % i == 0) {
            prime = false;
        }
    }
    ll ans;
    if (N == Nsave) {
        if (N == 1) {
            ans = 0;
        }
        else {
            ans = 1;
        }
    }
    else {
        if (prime && N != 1) {
            ans = 1;
        }
        else {
            ans = 0;
        }
        for (int i = 2; i < n; i++) {
            int k = 1;
            while (cnt.at(i) - k >= 0) {
                ans++;
                cnt.at(i) -= k;
                k++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 7220
N, K = map(int, input().split())
AList = list(map(int, input().split()))

l = 0
r = 10**9
while r-l > 1:
  x = (l + r)//2
  now = 0
  for a in AList:
    now += (a-1)//x
  f = lambda now : True if now <= K else False
  if f(now):
    r = x
  else:
    l = x
print(r)

Measured memory_bytes: 30740
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;

ll dp[105][100005];

int main(){
  ll N, W;
  cin >> N >> W;
  vector<vector<ll>> v;
  rep(i,N){
    ll a, b;
    cin >> a >> b;
    v.push_back({a,b});
  }

  rep(i,105) rep(j,100005) dp[i][j] = (ll)1e15;

  dp[0][0] = 0;
  dp[0][v[0][1]] = v[0][0];
  REP(i,1,N){
    rep(j,100005){
      dp[i][j] = dp[i-1][j];
      if(j-v[i][1] >= 0 && dp[i][j] > dp[i-1][j-v[i][1]] + v[i][0]){
        dp[i][j] = dp[i-1][j-v[i][1]] + v[i][0];
      }
    }
  }

  ll ret = 0;
  rep(i,100005){
    if(dp[N-1][i] <= W){
      ret = i;
    }
  }

  cout << ret << endl;
  
  return 0;
}


Measured memory_bytes: 82304
package main

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

func main() {
	var sc = bufio.NewScanner(os.Stdin)
	sc.Scan()
	s := strings.Split(sc.Text(), " ")
	A, _ := strconv.Atoi(s[0])
	B, _ := strconv.Atoi(s[1])
	if A <= 8 && B <= 8 {
		fmt.Print(`Yay!`)
	} else {
		fmt.Print(`:(`)
	}
}


Measured memory_bytes: 640
"""
Atcoder_Beginner_Contest_148
B

"""
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10000)

N = int(input())
S, T = input().split()

ans = []
for i in range(N):
    ans.append(S[i])
    ans.append(T[i])
print(''.join(ans))


Measured memory_bytes: 3060
N,M = map(int,input().split())
ps = []
for i in range(M):
    S = input().split()
    S[0] = int(S[0])
    ps.append(S)

question = [False for i in range(N)]
solved = [False for i in range(N)]
for i in range(M):
    posi = ps[i][0]-1
    if ps[i][1] =='AC':
        solved[posi] = True
pena = 0
AC = 0

for i in range(M):
    posi = ps[i][0]-1
    if ps[i][1] =='AC' and question[posi]==False:
        AC+=1
        question[posi] = True
    if ps[i][1] =='WA' and question[posi] == False and solved[posi]==True:
        pena+=1
        
print(AC,pena)

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

const int MAXN = 1.1e5;
int par[MAXN];
int getpar(int a) {
	return par[a] < 0 ? a : (par[a] = getpar(par[a]));
}
bool merge(int a, int b) {
	a = getpar(a);
	b = getpar(b);
	if (a == b) return false;
	if (-par[a] < -par[b]) swap(a, b);
	par[a] += par[b];
	par[b] = a;
	return true;
}

int diffs[MAXN];
int tots[MAXN];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	string S; cin >> S;
	int N = int(S.size());
	S = "a" + S + "a";
	for (int i = 0; i <= N; i++) {
		diffs[i] = (S[i+1] - S[i]);
	}

	for (int i = 0; i <= N; i++) {
		par[i] = -1;
	}
	for (int i = 0; i <= N; i++) {
		merge(i, N-i);
	}

	int Q; cin >> Q;
	while (Q--) {
		int l, r; cin >> l >> r; l--;
		merge(l, r);
	}

	for (int i = 0; i <= N; i++) {
		tots[getpar(i)] += diffs[i];
	}
	for (int i = 0; i <= N; i++) {
		if (tots[i] % 26 != 0) {
			cout << "NO" << '\n';
			exit(0);
		}
	}
	cout << "YES" << '\n';

	return 0;
}


Measured memory_bytes: 4856
use std::io::*;
use std::str::FromStr;

#[allow(dead_code)]
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

fn main() {
    let n = read::<usize>();
    let mut prev = 0;
    let mut ans = 0;
    let mut sum = 0;
    for _i in 0..n {
        let h = read::<usize>();
        if prev < h {
            sum = 0;
        } else {
            sum += 1;
        }
        prev = h;
        ans = std::cmp::max(ans, sum);
    }
    println!("{}", ans);
}


Measured memory_bytes: 4352
import math
 
 
def digitSum(n):
    s = str(n)
    array = list(map(int, list(s)))
    return sum(array)
 
 
n =  int(input())
 
# 0が多くなるようにする
rank = math.ceil(math.log10(n)) 
div =  n % 10**rank
if div == 0:
    print(10)
else :
    print(digitSum(int(n)))


Measured memory_bytes: 3060
/*Alohomora*/
#include<bits/stdc++.h>
#define ll         long long
#define fl(i,n)    for(i=0;i<n;i++)
#define fld(i,a,b) for(i=a;i>b;i--)
#define fli(i,a,n) for(i=a;i<n;i++)
#define inp(i,a,n) for(i=0;i<n;i++) {cin>>a[i];}
#define op(i,a,n)  for(i=0;i<n;i++) {cout<<a[i]<<" ";}
#define pb         push_back
#define mp         make_pair
#define mod1        987654319 
#define speedup    ios_base::sync_with_stdio(false),cin.tie(0)
using namespace std;
ll fact(ll n){ if(n==0){return 1;}return (n*fact(n-1))%mod1;}
ll power(ll x, ll y,ll mod){ll out = 1;while (y > 0){if (y & 1) out=(out*x)%mod;y = y>>1;x = (x*x)%mod;}return out%mod;}
ll inverse(ll a){return power(a,mod1-2,mod1);}
ll gcd(ll a,ll b){if(b==0){return a;}gcd(b,a%b);}
ll a[2000000];
void sieve(){ll i,j;fli(i,2,1000001){if(a[i]==0){for(j=i*i;j<1000001;j+=i){a[j]=1;}}}}
map<ll,vector<ll> >m1;
vector<ll>v1;
bool compar(const pair<ll,ll> &a, const pair<ll,ll> &b) 
{ 
    return (a.second < b.second);
} 
ll level[1000000];
vector<ll>root;
set<ll>s1;
void factorise(long long n) 
{ 
    while (!(n%2)) 
    { 
        n >>= 1; 
        s1.insert(2);
    } 
    for (long long i=3; i<=sqrt(n); i+=2) 
    { 
        while (n%i==0) 
        { 
        	s1.insert(i);
            n=n/i; 
        } 
    } 
  	if (n>2) 
  	{
       s1.insert(n);
	}
} 
void comp()
{
	ll l,i,j,k,q,n,d,m,temp=0,sum,count=0;
	cin>>n>>d;
	for(int i=1;i<=n;i++)
	{
		i+=2*d;
		count++;
	}
	cout<<count<<endl;
} 
int main()
{
	speedup;
	ll i=0,t;
	ll n;
	//cin>>t;
	t=1;
	while(t--)
	{
	 comp();
	}
}

Measured memory_bytes: 2304
#include <bits/stdc++.h>
#include <string>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <math.h>
#include <float.h>
#include <iomanip>
#include <iostream>
using namespace std;
 
int main(){

    int A,B;
    cin>>A>>B;
    cout <<6-A-B<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstring>
#include<cmath>

using namespace std;

int main() {
    int N, W;
    scanf("%d%d", &N, &W);
    int w[N];
    long long v[N];
    for(int i=0; i<N; i++) {
    	scanf("%d%lld", &w[i], &v[i]);
    }
    long long dp[W+1];
    memset(dp, 0, sizeof dp);
    for(int i=0; i<N; i++) {
    	for(int weight = W; weight>w[i]; weight--) {
    		if(dp[weight-w[i]] > 0) {
    			dp[weight] = max(dp[weight], dp[weight-w[i]]+v[i]);
    		}
    	}
    	dp[w[i]] = max(dp[w[i]], v[i]);
    }
    long long max_value = 0;
    for(int weight=0; weight<=W; weight++) {
    	max_value = max(max_value, dp[weight]);
    }
    printf("%lld\n", max_value);
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <algorithm>
#include <climits>
#include <numeric>
#include <iomanip>
#include <cmath>
#include <vector>
#include <set>
#include <unordered_set>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <unordered_map>

#define barsik ios::sync_with_stdio(false)
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)

typedef long long ll;
typedef std::vector<int> vi;
typedef std::pair <int, int> pii;
typedef std::unordered_set <int> u_si;

using namespace std;

int a, b, c, x, y;

void solve(){
    cin >> a >> b >> c >> x >> y;
    int money = 0;
    if(a + b > 2 * c){
        money += min(x, y) * 2 * c;
        int mn = min(x, y);
        x -= mn;
        y -= mn;
    }
    if(y > 0){
        money += (b * y < 2 * c * y) ? b * y : 2 * c * y;
    }
    if(x > 0){
        money += (a * x < 2 * c * x) ? a * x : 2 * c * x;
    }
    cout << money;
}

int main(){
    barsik;
    int q = 1;
    //cin >> q;
    while(q--) solve();
}



Measured memory_bytes: 256
#include <stdio.h>
int main(){
int a,b;
scanf("%d %d",&a,&b);
if(a>0){
printf("Positive\n");
}else if(a<=0 && b>=0){
printf("Zero\n");
}else if(b<0){
if((b-a+1)%2==0){
printf("Positive\n");
}else{
printf("Negative\n");
}
}
return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

using Data = int;
const int len = 1 << 18;

struct BIT {
  vector<Data> data;
  BIT() : data(len, 0) {}
  void update(int i, Data value) {
    for (; i < len; i |= i+1) data[i] += value;
  }
  Data query(int i) {
    Data s = 0;
    for (; i >= 0; i = (i&i+1)-1) s += data[i];
    return s;
  }
};

bool ok(const vecint& a, const int th) {
  ll n = a.size();
  vecint v(n*4);
  int offset = n*2;
  ll cnt = 0;
  ll sum = 0;
  REP(i,n) {
    v[offset] += 1;
    if (a[i] >= th) {
      offset -= 1;
      sum -= v[offset];
    } else {
      sum += v[offset];
      offset += 1;
    }
    cnt += sum;
  }
  ll m = n * (n+1) / 2;
  ll mid = m/2 + 1;
  return cnt >= mid;
}

int main()
{
  int n;
  cin>>n;
  vecint a(n);
  REP(i,n) cin>>a[i];
  vecint b = a;
  b.push_back(0);
  b.push_back(1000000007);
  sort(ALL(b));
  b.erase(unique(ALL(b)), end(b));
  int hi = b.size()-1;
  int lo = 0;
  while ((hi - lo) > 1) {
    int mid = (hi + lo) / 2;
    if (ok(a, b[mid])) {
      hi = mid;
    } else {
      lo = mid;
    }
  }
  cout << b[lo] << endl;
  return 0;
}


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

int main(){
  int a,b,c;
  
    cin>>a>>b>>c;
 int d[120];
  
 for (int i =0;i<b;i++)
     cin >>  d[i] ;
  
     int e=0,f=0;
  
 for(int i = c;i<a;i++){
  for(int j =0;j<b;j++){
    if( i == d[j]){
       e++;
    }
  }
 }
    for(int i = c;i>0;i--){
  for(int j =0;j<b;j++){
    if( i == d[j]){
       f++;
    }
  }
 }
    cout << min(e,f) <<endl;
}
  
    


Measured memory_bytes: 384
import java.util.*;

public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int a[] = new int[9];
    a[0] = sc.nextInt();
    a[1] = sc.nextInt();
    a[2] = sc.nextInt();
    a[3] = sc.nextInt();
    a[4] = sc.nextInt();
    a[5] = sc.nextInt();
    a[6] = sc.nextInt();
    a[7] = sc.nextInt();
    a[8] = sc.nextInt();
    
    int N = sc.nextInt();
    for(int i=0; i<N; i++) {
      int b = sc.nextInt();
      for(int j=0; j<9; j++) {
        if(a[j] == b) {
          a[j] = 0;
        }
      }
    }
    if(a[0] == 0 && a[1] == 0 && a[2] == 0) {
      System.out.println("Yes");
    } else if(a[0] == 0 && a[1] == 0 && a[2] == 0) {
      System.out.println("Yes");
    } else if(a[3] == 0 && a[4] == 0 && a[5] == 0) {
      System.out.println("Yes");
    } else if(a[6] == 0 && a[7] == 0 && a[8] == 0) {
      System.out.println("Yes");
    } else if(a[0] == 0 && a[3] == 0 && a[6] == 0) {
      System.out.println("Yes");
    } else if(a[1] == 0 && a[4] == 0 && a[7] == 0) {
      System.out.println("Yes");
    } else if(a[2] == 0 && a[5] == 0 && a[8] == 0) {
      System.out.println("Yes");
    } else if(a[0] == 0 && a[4] == 0 && a[8] == 0) {
      System.out.println("Yes");
    } else if(a[2] == 0 && a[4] == 0 && a[6] == 0) {
      System.out.println("Yes");
    } else {
      System.out.println("No");
    }
  }
}


Measured memory_bytes: 23124
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
	string A, B, C; cin >> A >> B >> C;
	char ch[3];
	ch[0] = A[0] - 32;
	ch[1] = B[0] - 32;
	ch[2] = C[0] - 32;
	for (int i = 0; i < 3; i++)cout << ch[i];
	cout << endl;
}

Measured memory_bytes: 256
X = int(input())
K = int(input())
r_lst = [int(_) for _ in input().split()]
Q = int(input())
t_lst, a_lst = [], []
for i in range(Q):
    buf = input().split()
    t_lst.append(int(buf[0]))
    a_lst.append(int(buf[1]))
    
pos_lst = []
for i, r in enumerate(r_lst):
    direc = "+" if i%2==0 else "-"
    pos_lst.append((r, direc))
for i, t in enumerate(t_lst):
    pos_lst.append((t, i))
pos_lst = sorted(pos_lst, key=lambda tup: tup[0])


left, right  = 0, X
val = [0, 0, X] 

direc = "-"
prv = 0
for pos in pos_lst:
#    print(left, right)
#    print(val)
#    print(pos)
#    print()
    
    elapsed = pos[0] - prv
    prv = pos[0]
    
    if direc == "+":
        val[0] = min(X, val[0] + elapsed)
        val[1] += elapsed
        val[2] = min(X, val[2] + elapsed)
        right = min(right, X - val[1])
    else:
        val[0] = max(0, val[0] - elapsed)
        val[1] -= elapsed
        val[2] = max(0, val[2] - elapsed)     
        left = max(left, -(val[1]))
        
    if pos[1] == "+" or pos[1] == "-":
        direc = pos[1]
    else: #is query
        a = a_lst[pos[1]]
        
        if a <= left:
            print(val[0])
        elif a >= right:
            print(val[2])
        else:
            print( a + val[1])

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

using namespace std;

const int NMAX = 1e5 + 10;
string s;
int ans[NMAX];

int main(){
    int i,j,nrR,nrL,lastR;
    cin >> s;
    for(i = 0 ; i < s.size() ;){
        nrR = nrL = 0;
        while(s[i] == 'R'){
            nrR++;
            i++;
        }
        lastR = i - 1;

        while(s[i] == 'L' && i < s.size()){
            nrL++;
            i++;
        }

        ans[lastR] = (nrR + 1) / 2 + nrL / 2;
        ans[lastR + 1] = nrL + nrR - ans[lastR];

    }

    for(i = 0 ; i < s.size() ; i++)
        cout << ans[i] << " ";

    return 0;
}


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

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pli = pair<ll, int>;

#define fi first
#define se second
#define pb push_back
#define sz(x) (int) ((x).size())
#define fast ios_base::sync_with_stdio(0); cin.tie(0);
#define testcase int _; cin >> _; while (_--)
#define all(x) ((x).begin(), (x).end())


/*A - NOT*/
void Solve() {
	int x;	cin >> x;
	cout << !x << "\n";
}

int main() {
	fast
	//testcase
		Solve();
	return 0;
}

Measured memory_bytes: 3604
//#include<bits/stdc++.h>	// 全てのヘッダーファイルをinclude
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<cmath>
#include<set>
#include<map>
#include<utility>	// wrap,pair
#define REP(i,n) for(int i=0;i<n;i++)
#define REPR (i,n) for(int i=n;i>0;i--)
#define FOR(i,m,n) for(int i=m;i<n;i++)
const int MOD{ int(1e9 + 7) };	// int 1000000007
const int inf{ int(1e9) };	// inf = 1000000000 // 1e9 はdouble型
using namespace std;
typedef long long ll;

// 最大公約数（ユークリッドの互除法）
int GCD(int x, int y) {
	if (x > y) {
		swap(x, y);
	}
	int r = y % x;
	while (r != 0) {
		y = x;
		x = r;
		r = y % x;
	}
	return x;
}

// 最小公倍数
int LCM(int x, int y) {
	ll gcd = GCD(x, y);
	return x * y / gcd;
}

// 素数判定(素数ならtrue,合成数ならfalse)
bool IsPrime(int num) {
	if (num < 2) return false; // 0,1
	else if (num == 2) return true;	// 2
	else if (num % 2 == 0) return false; // 偶数

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2) {
		if (num % i == 0) return false; // 割り切れたら素数ではない
	}
	return true; // 全部通ったら素数
}

// pairをsecond基準で昇順sort
// sort(vector_name.begin(),vector_name.end(),compare_by_b);
bool compare_by_b(pair<int, int>a, pair<int, int>b) {
	if (a.second != b.second) return a.second < b.second;
	else return a.first < b.first;
}

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

int main(void) {

	int n, k;
	cin >> n >> k;
	vector<int> h(n);
	REP(i, n) cin >> h[i];

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

	ll h_min = inf;
	for (int i = 0; i <= n - k; i++) {
		ll tmp = h[i + k - 1] - h[i];
		h_min = min(h_min, tmp);
	}
	cout << h_min << endl;

	return 0;
}

Measured memory_bytes: 640