akhauriyash/Code-Regression huggingface dataset:
import sys
## io ##
def IS(): return sys.stdin.readline().rstrip()
def II(): return int(IS())
def MII(): return list(map(int, IS().split()))
#======================================================#

def main():
    n, m, q = MII()
    query = [MII() for _ in range(q)]

    def calc_point(lst):
        sumv = 0
        for a, b, c, d in query:
            if lst[b-1] - lst[a-1] == c:
                sumv += d
        return sumv

    def dfs(lst):
        len_lst = len(lst)
        if len_lst == n:
            return calc_point(lst)
        point = 0
        last_elm = lst[-1] if len_lst > 0 else 1
        for i in range(last_elm, m+1):
            point = max(point, dfs(lst+[i]))
        return point

    print(dfs([]))


if __name__ == '__main__':
    main()

Measured memory_bytes: 9156
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
typedef pair<int, int> pii;
#define F first
#define S second
pii p[maxn];
int c[maxn], d[maxn];
int id[maxn];
int r[maxn];
int main() {
	int n;
	scanf("%d", &n);
	for(int i = 0; i < n; i++) scanf("%d", &p[i].F), c[i] = p[i].F;
	for(int i = 0; i < n; i++) scanf("%d", &p[i].S), d[i] = p[i].S;
	sort(c, c + n);
	sort(d, d + n);
	for(int i = 0; i < n; i++) {
		if(c[i] > d[i]) return puts("No"), 0;
	}
	for(int i = 0; i < n; i++) {
		if(i && c[i] <= d[i - 1]) return puts("Yes"), 0;
	}
	sort(p, p + n);
	for(int i = 0; i < n; i++) id[i] = lower_bound(d, d + n, p[i].S) - d;
	for(int i = 0; i < n; i++) r[id[i]] = i;
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(id[i] == i) continue;
		int j = r[i];
		int k = id[i];
		swap(r[i], r[k]);
		swap(id[i], id[j]);
		cnt++;
	}
	if(cnt <= n - 2) puts("Yes");
	else puts("No");
	return 0;
}



Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 100000000;
#define rep1(i, n) for (ll i=0; i<(n); i++) 
#define rep2(i, k, n) for (ll i=k; i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


int main() {
    ll n, m;
    cin >> n >> m;
    vector<vector<ll> > py(m);
    rep1(i, m){
        vector<ll> res(3);
        cin >> res[0] >> res[1];
        res[2] = i;
        py[i] = res;
    }
    sort(py.begin(), py.end());
    vector<P> ans(m);
    ll count = 1;
    rep1(i, m){
        if (i==0){
            ans[py[i][2]] = make_pair(py[i][0], count);
        }
        else if (py[i][0]==py[i-1][0]){
            count++;
            ans[py[i][2]] = make_pair(py[i][0], count);
        }
        else{
            count = 1;
            ans[py[i][2]] = make_pair(py[i][0], count);
        }
    }
    rep1(i, m){
        cout << setfill('0') << right << setw(6) << ans[i].first;
        cout << setfill('0') << right << setw(6) << ans[i].second << endl;
    }
    //printf("%.12f", ans);
}

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

#define ll long long
#define Fi first
#define Se second
#define Pb push_back
#define INF 1e9
#define MOD 1e9+7

#define all(v) v.begin(),v.end()
#define output_s(a) printf("%s\n",(a).c_str())

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define Rep(i,n,m) for(int i=(int)(n);i<(int)(m);i++)
#define RepS(i,n,m) for(int i=(int)(n);i<=(int)(m);i++)
#define RRepS(i,n,m) for(int i=(int)(n);i>=(int)(m);i++)
#define RepA(x) for(auto item:(x))

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}    
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

//library----------------------------------------------

vector<int> v(10);

bool ok(int x){
    while(x){
        if(v[x%10])return false;
        x /= 10;
    }
    return true;
}

int main() {
    CIN(N,K);
    rep(i,K){
        CIN(D);
        v[D] = 1;
    }
    while(!ok(N)) N++;
    printf("%d\n",N);
    return 0;
}

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

int main()
{
    int H,W,k,ans=0;
    cin>>H>>W>>k;
    vector<string> c(H);
    rep(i,H) cin>>c[i];
    rep(bith,1<<H) rep(bitw,1<<W)
    {
        int count=0;
        rep(h,H) rep(w,W)
        {
            if(bith>>h&1) continue;
            if(bitw>>w&1) continue;
            if(c[h][w]=='#') count++;
        }
        if(count==k) ans++;
    }
    cout<<ans;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
#define WHOLE(v) (v).begin(), (v).end()
#define REV_WHOLE(v) (v).rbegin(), (v).rend()
using i64 = int64_t;
using namespace std;
template <size_t I, class H, class... T> struct TupleReaderWriter{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple_cat(tuple<H>(v),TupleReaderWriter<sizeof...(T)-1,T...>::r(i));}static void w(ostream&o,tuple<H,T...>&t,string d){TupleReaderWriter<I-1,H,T...>::w(o,t,d);o<<d<<get<I>(t);}};
template <class H, class... T> struct TupleReaderWriter<0,H,T...>{static tuple<H,T...> r(istream&i){H v;i>>v;return tuple<H>(v);}static void w(ostream&o,tuple<H,T...>&t,string d){o<<get<0>(t);}};
template<class T>istream&operator>>(istream&i,vector<T>&v){for(auto&x:v)i>>x;return i;}
template<class T>ostream&operator<<(ostream&o,vector<T>&v){string delim="";for(auto&x:v)o<<delim<<x,delim=" ";return o;}
template <class... T> istream& operator>>(istream&i,tuple<T...>& t) { t = TupleReaderWriter<sizeof...(T), T...>::r(i); return i; }
template <class... T> ostream& operator<<(ostream& o, tuple<T...>& t) { string delim = " "; TupleReaderWriter<sizeof...(T) - 1, T...>::w(o, t, delim); return o; }
template<typename T> using rev_priority_queue = priority_queue<T, vector<T>, greater<T>>;
template<typename T> using vector2d = vector<vector<T>>;
void R_YESNO(bool p) { cout << (p ? "YES" : "NO") << endl; }
void R_YesNo(bool p) { cout << (p ? "Yes" : "No") << endl; }
int main() {
    int N;
    string S;
    cin >> N >> S;
    R_YesNo(N % 2 == 0 && S.substr(0, N / 2) == S.substr(N / 2, N / 2));
    return 0;
}

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

ll gcd(ll a, ll b){return b!=0 ? gcd(b, a%b) : a;}
ll lcm(ll a, ll b){return a / gcd(a, b) * b;}

int main(){
	int n;
	cin >> n;
	
	ll ans = 1;
	rep(i, n){
		ll t;
		cin >> t;
		ans = lcm(max(t, ans), min(t, ans));
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <string>
#include <map>
#include <math.h>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <set>
#include <queue>
#include <sstream>
#include <stack>
#include <deque>
#include <memory.h>
#include <cassert>
#include <ctime>
#include <climits>
#include <list>
#include <time.h>
#include <unordered_map>
#include <bitset>
#include <exception>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned long long ull;
#define pb push_back
#define mp make_pair
#define FILE "file"
#define lc v << 1
#define rc (v << 1) + 1
#define inf 1e+9
#define linf ll(1e+18)
#define dinf 1e+14

typedef long long ll;
#define pb push_back
#define mp make_pair

ll getAbs(ll x) {
    if (x >= 0) {
        return x;
    } else {
        return -x;
    }
}

void solve()
{
    int N, K;
    cin >> N >> K;
    
    vector<ll> ar(N);
    for (int i = 0 ; i < N ; i++) {
        cin >> ar[i];
    }
    
    ll ans = linf;
    for (int i = 0 ; i <= N-K ; i++) {
        ans = min(ans, (ar[i+K-1]-ar[i]) + min(getAbs(ar[i+K-1]), getAbs(ar[i])));
    }
    
    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  //  freopen("/Users/bekhzodsoliev/Desktop/C++/cp/cp/file.in", "r", stdin);freopen("/Users/bekhzodsoliev/Desktop/C++/cp/cp/file.out", "w", stdout);
    
    int t = 1;
    //cin >> t;
    
    while(t--)
    {
        solve();
    }
    
    return 0;
}


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

int main(){
  int n; cin >> n;
  int A[n];
  for (int i=0; i<n; i++){
    cin >> A[i];
  }
  int cnt=0;
  for (int i=0; i<n; i++){
    while(A[i]%2==0){
      A[i] = A[i]/2;
      cnt++;
    }
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF LLONG_MAX-1
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(long long i=0;i<x;i++)
#define repn(i,x) for(long long i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<pair<string,P> >vec;
// vector<vector<int>> data(3, vector<int>(4));

void solve(long long N, long long x, vector<long long> a){
	vector<ll> mincost(N, INF);
	ll res = INF;
	rep(i,N) {
		ll now = 0;
		rep(j,N) {
			mincost[j] = min(mincost[j], a[(j+N-i)%N]);
		}
		rep(j,N) {
			now += mincost[j];
		}
		now += x*i;
		res = min(res, now);
	}
	cout << res << endl;
}

int main(){	
	long long x;
	long long N;
	scanf("%lld",&N);
	vector<long long> a(N-1+1);
	scanf("%lld",&x);
	for(int i = 0 ; i <= N-1 ; i++){
		scanf("%lld",&a[i]);
	}
	solve(N, x, a);
	return 0;
}



Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define Nmax 200010
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define REP(i,n)  FOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;

int main() {
	int Q;
	cin >> Q;
	int l,r;
	int nita[100010]={};
	bool reached[100010];
	FOR(i,2,100001){
		if(!reached[i]){
			for(int j=2;j*i < 100001;j++){
				reached[j*i]=true;
				nita[j*i]=1;//素数じゃないやつ1
			}
		}
	}
	FOR(i,2,100001){//素数が1でそれ以外0
		if(nita[i]==1) nita[i]=0;
		else if(nita[i]==0) nita[i]=1;
	}
	int s[100010]={};
	for(int i=1;i < 100001;i+=2){//2017に似た数かを判定
		if(nita[i]==1 && nita[(i+1)/2]==1) s[i]=1;
	}
	REP(i,100000) s[i+1] += s[i]; //累積和
	REP(i,Q){
		cin >> l >> r;
		int ans=s[r]-s[l-1];
		cout << ans << endl;
	}
		
	return 0;
}

Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
 
#define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define repa(i,a,n) for(int i=a;i<=n;i++)
#define repd(i,a,n) for(int i=a;i>=n;i--)
#define trav(a,x) for(auto& a:x)
#define all(c) c.begin(), c.end()
#define fst first
#define sec second
#define pb push_back
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX 100007
 
typedef vector<int> vi;
typedef pair<int,int> pii;

bool cmp(pii x,pii y)
{
  return x.sec<y.sec;
}
int32_t main()
{
  int n,m,x,y;
  std::vector<pii> v;

  cin>>n>>m;

  rep(i,m)
  {
    cin>>x>>y;
    v.pb(mp(x,y));
  }

  sort(all(v),cmp);
  int curr=0,cnt=0;
  rep(i,m)
  {
    if(v[i].fst>=curr)
    {
      cnt++;
      curr=v[i].sec;
    }
  }
  
  cout<<cnt<<endl;
}

Measured memory_bytes: 2420
#include<iostream>
#include<string>
using namespace std;
int main(){
  string str;
  while(cin>>str,str!="-"){
    int n;
    cin>>n;
    char str2[1300];
    for(int i=0;i<n;i++){
      int shu;
      cin>>shu;
      for(int i=0;i<shu;i++)
	str2[str.size()-shu+i]=str[i];
      for(int i=0;i<str.size()-shu;i++)
	str2[i]=str[shu+i];
      str2[str.size()]='\0';
      str=str2;
    }
   
    cout<<str2<<endl;
  }
  return 0;
}

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

    // 整数スキャン（複数）
    /*
    int x;
    scanf("%d",&x);
    int y;
    scanf("%d",&y);
    int z;
    scanf("%d",&z);

    // n個の整数のスキャン
    /*
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    */

    // 文字列スキャン
    /*
    string s;
    cin >> s;
    */

    // n個の文字列スキャン
    /*
    vector<string> slist;
    rep(i,n){
        string s;
        cin >> s;
        slist.push_back(s);
    }
    */

int main() {
    int n;
    scanf("%d",&n);
    ll a[n] = {};
    rep(i,n){
        scanf("%lld",&a[i]);
    }
    ll b[n] = {};

    drep(i,n){
        if(i==n-1){
            b[i] = 0;
        }else if(i==n-2){
            b[i] = abs(a[i]-a[i+1]);
        }else{
            b[i] = b[i+2] + abs(a[i]-a[i+2]);
            mins(b[i],b[i+1]+abs(a[i]-a[i+1]));
        }
    }


    int ans = 0;
    ans = b[0];
    cout << ans << endl;
    return 0;
}
 
 


Measured memory_bytes: 1792
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;

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

		// 入力値の取得
		int N = sc.nextInt();
		int K = sc.nextInt();
		Deque<Integer> temp = new ArrayDeque<>();
		
		int sum = 0;
		int max = 0;
		Object[] maxArray = null;
		for (int i = 0; i < N; i++) {
			int p = sc.nextInt();
			if (i < K) {
				sum +=p;
				temp.add(p);
				if (i == K - 1) {
					max = sum;
					maxArray = temp.toArray();
				}
			}
			else {
				sum = sum - temp.poll() + p;
				temp.add(p);
				if (sum > max) {
					max = sum;
					maxArray = temp.toArray();
				}
			}
		}
		
		// 結果の出力
		double result = 0;
		for (int i = 0; i < K; i++) {
			result += (1.0 + (int)maxArray[i]) / 2;
		}
		System.out.println(result);
		sc.close();
	}
}


Measured memory_bytes: 55108
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N,L;
ll a[100010];
int main(){
    cin>>N>>L;
	ll last=-1;
	for(ll i=0;i<N;i++){
		cin>>a[i];
	}
	for(ll i=0;i<N-1;i++){
		if(a[i]+a[i+1]>=L)last=i;
	}
	if(last==-1){
		cout<<"Impossible"<<endl;return 0;
	}
	cout<<"Possible"<<endl;
	for(ll i=0;i<last;i++){
		cout<<i+1<<endl;
	}
	for(ll i=N-2;i>last;i--){
		cout<<i+1<<endl;
	}
	cout<<last+1<<endl;	
    return 0;
}

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

int main() {
    int n;
    cin >> n;
    int a;
    int cnt = 0;
    for(int i = 0; i < n; i++)
    {
        cin >> a;
        while (a % 2 == 0) {
            cnt++;
            a /= 2;
        }
    }
    cout << cnt << endl;
}

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

#define fi first
#define se second

const int N = 200200;
const long long mod = 998244353;

using namespace std;

int n;
int a[N];

int main()
{
        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);
        ios_base::sync_with_stdio(0);

        cin >> n;
        for(int i = 1; i <= n; i++){
                cin >> a[i];
        }
        vector < int > res;
        for(int it = 0; it < n; it++){
                int h = 0;
                for(int i = 1, j = 1; i <= n; i++){
                        if(!a[i]){
                                continue;
                        }
                        if(a[i] == j){
                                h = i;
                        }
                        j++;
                }
                if(!h){
                        cout << -1 << "\n";
                        return 0;
                }
                res.push_back(a[h]);
                a[h] = 0;
        }
        for(int i = n - 1; i >= 0; i--){
                cout << res[i] << "\n";
        }
}


Measured memory_bytes: 256
N=int(input())
L=list(map(int,input().split()))
sort_L=sorted(L,reverse=True)
ans=0
for n in range(N-2):
    for o in range(n+1,N-1):
        lar=sort_L[n]
        kouho=sort_L[o+1:]
        mid=sort_L[o]
        sa=lar-mid
        left=0
        right=N-o-2
        if kouho[-1]>sa:
            ans+=right+1
        else:
            while right > left + 1:
                half = (right + left) // 2
                if kouho[half] <= sa:
                    right = half
                else:
                    left = half
            if kouho[right]<=sa and kouho[left]<=sa:
                continue
            elif kouho[right]>sa:
                ans+=right+1
            else:
                ans+=left+1
print(ans)


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




void LCS(string s, string p){
    
    int m=s.size()+1;
    int n=p.size()+1;

    int dp[m][n];

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++)
        {
            if(i==0 || j==0)
             dp[i][j]=0;

            else if(s[i-1]==p[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
      

   int idx = dp[m-1][n-1]; 
  
   char lcs[idx+1]; 
   lcs[idx] = '\0';  
  
   int i = m-1, j = n-1; 
   while (i > 0 && j > 0) 
   { 
      if (s[i-1] == p[j-1]) 
      { 
          lcs[idx-1] = s[i-1];  
          i--; j--; idx--;      
      } 
  
      else if (dp[i-1][j] > dp[i][j-1]) 
         i--; 
      else
         j--; 
   } 
  
   cout<<lcs;     
    return; 
}
int main() 
{

    string s;
    cin>>s;
    string p;
    cin>>p;
    LCS(s,p);
    return 0;
}


Measured memory_bytes: 35456
using System;

public class Program
{
    private int N;
    private int[] A;
    public void Solve()
    {
        var sc = new Scanner();
        N = sc.NextInt();
        A = sc.IntArray();
        long sum = 0;
        foreach (int i in A)
        {
            sum += i;
        }

        long sunuke = 0;
        long ans = long.MaxValue;
        for (int i = 0; i < N - 1; i++)
        {
            sunuke += A[i];

            ans = Math.Min(ans, Math.Abs(sum - 2 * sunuke));
        }
        
        Console.WriteLine(ans);
    }

    public static void Main(string[] args)
    {
        new Program().Solve();
    }
}

class Scanner
{
    public Scanner()
    {
        _pos = 0;
        _line = new string[0];
    }

    const char Separator = ' ';
    private int _pos;
    private string[] _line;

    #region スペース区切りで取得

    public string Next()
    {
        if (_pos >= _line.Length)
        {
            _line = Console.ReadLine().Split(Separator);
            _pos = 0;
        }

        return _line[_pos++];
    }

    public int NextInt()
    {
        return int.Parse(Next());
    }

    public long NextLong()
    {
        return long.Parse(Next());
    }

    public double NextDouble()
    {
        return double.Parse(Next());
    }

    #endregion

    #region 型変換

    private int[] ToIntArray(string[] array)
    {
        var result = new int[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = int.Parse(array[i]);
        }

        return result;
    }

    private long[] ToLongArray(string[] array)
    {
        var result = new long[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = long.Parse(array[i]);
        }

        return result;
    }

    private double[] ToDoubleArray(string[] array)
    {
        var result = new double[array.Length];
        for (int i = 0; i < array.Length; i++)
        {
            result[i] = double.Parse(array[i]);
        }

        return result;
    }

    #endregion

    #region 配列取得

    public string[] Array()
    {
        if (_pos >= _line.Length)
            _line = Console.ReadLine().Split(Separator);

        _pos = _line.Length;
        return _line;
    }

    public int[] IntArray()
    {
        return ToIntArray(Array());
    }

    public long[] LongArray()
    {
        return ToLongArray(Array());
    }

    public double[] DoubleArray()
    {
        return ToDoubleArray(Array());
    }

    #endregion
}

Measured memory_bytes: 31196
#include<cstdio>
#define MAX 10000
#define NIL -1

struct Node { int parent, left, right; };

Node T[MAX];
int n, D[MAX], H[MAX];

void setDepth(int u, int d) {
    if ( u == NIL ) return;
    D[u] = d;   //深さ設定
    setDepth(T[u].left, d + 1);
    setDepth(T[u].right, d + 1);
}

int setHeight(int u) {
    int h1 = 0, h2 = 0;
    if ( T[u].left != NIL )
      h1 = setHeight(T[u].left) + 1;
    if ( T[u].right != NIL )
      h2 = setHeight(T[u].right) + 1;
    return H[u] = ( h1 > h2 ? h1 : h2 );   //1番深い葉からの距離
}

//自分以外の兄弟を返す
int getSibling(int u){
    if ( T[u].parent == NIL ) return NIL;
    if ( T[T[u].parent].left != u && T[T[u].parent].left != NIL )
      return T[T[u].parent].left;
    if ( T[T[u].parent].right != u && T[T[u].parent].right != NIL )
      return T[T[u].parent].right;
    return NIL;
}

void print(int u) {
    printf("node %d: ", u);
    printf("parent = %d, ", T[u].parent);
    printf("sibling = %d, ", getSibling(u));
    int deg = 0;   //子供の数
    if ( T[u].left != NIL ) deg++;
    if ( T[u].right != NIL ) deg++;
    printf("degree = %d, ", deg);
    printf("depth = %d, ", D[u]);
    printf("height = %d, ", H[u]);
    
    if ( T[u].parent == NIL ) {
        printf("root\n");
    } else if ( T[u].left == NIL && T[u].right == NIL ) {
        printf("leaf\n");
    } else {
        printf("internal node\n");
    }
} 

int main() {
    int v, l, r, root = 0;
    scanf("%d", &n);
    
    for ( int i = 0; i < n; i++ ) T[i].parent = NIL;
    
    for ( int i = 0; i < n; i++ ) {
        scanf("%d %d %d", &v, &l, &r);   //節点の番号、左の子の番号、右の子の番号
        T[v].left = l;
        T[v].right = r;   //子がいない場合、-1(番兵)を代入
        if  ( l != NIL ) T[l].parent = v;   
        if  ( r != NIL ) T[r].parent = v;
    }
    
    for ( int i = 0; i < n; i++ ) if (T[i].parent == NIL ) root = i;   //根となる節点の番号を設定
    
    setDepth(root, 0);   //深さ：根からの距離
    setHeight(root);      //高さ：1番深い葉からの距離
    
    for ( int i = 0; i < n; i++ ) print(i);
    
    return 0;
}


Measured memory_bytes: 2744
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000100;

int main()
{
    int a,b,c;
	cin >> a >> b >> c;
	if((a == b && a != c) || (a == c && a != b) || (c == b && a != c)){
		cout << "Yes" << endl;
	}
	else
		cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9+7;

int main(void){

    int N; cin>>N;
    int minimum=1e+9, maximum=0;
    for (int i = 0; i < N; ++i) {
        int tmp; cin>>tmp;
        minimum = min(minimum, tmp);
        maximum = max(maximum, tmp);
    }
    cout<<maximum-minimum<<endl;

    return 0;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
from bisect import bisect_left, bisect_right


def read():
    N = int(input().strip())
    A = [int(input().strip()) for _ in range(N)]
    return N, A


def solve(N, A, INF=10**9+1):
    # LIS
    # dp[i]: 長さiの最長増加部分列(A[i]<A[j])のうち、最も小さい数字
    dp = [INF for i in range(N)]
    for i in range(N):
        a = A[N-i-1]
        idx = bisect_right(dp, a)
        dp[idx] = a
    return bisect_right(dp, INF-1)


if __name__ == '__main__':
    inputs = read()
    outputs = solve(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))


Measured memory_bytes: 13720
n=int(input())
s=[0]*n
ct=0
a=0
b=0
c=0
for i in range(n):
    s[i]=input()
for i in range(n):
    for j in range(len(s[i])):
        t=s[i]
        ts=list(t)
        ts.append(0)
        if ts[j]=='A' and ts[j+1]=='B':
            ct+=1
    if ts[0]=='B' and ts[len(s[i])-1]!='A':
        a+=1
    if ts[len(s[i])-1]=='A' and ts[0]!='B':
        b+=1
    if ts[0]=='B' and ts[len(s[i])-1]=='A':
        c+=1
ct += max(0,c -1)
if c !=0:
  if a > 0 and b >0:
    ct += 2 + min(a-1,b-1)
  elif a>0:
    ct += 1 + min(a-1,b)
  elif b>0:
    ct += 1 + min(a,b-1)
else:
  ct += min(a,b)
print(ct)

Measured memory_bytes: 3700
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

int c[1010][1010];

void lcs(char X[], char Y[]){
	int m = strlen(X);
	int n = strlen(Y);
	int i, j;
	for(i = 1;i <= m;i++)
		c[i][0] = 0;
	for(j = 1;j <= n;j++)
		c[0][j] = 0;
	for(i = 1;i <= m;i++){
		for(j = 1;j <= n;j++){
			if(X[i - 1] == Y[j - 1])
				c[i][j] = c[i - 1][j - 1] + 1;
			else
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
		}
	}
}

int main(void){
	int q, i;
	char A[1000], B[1000];
	scanf("%d", &q);
	for(i = 0;i < q;i++){
		scanf("%s", A);
		scanf("%s", B);
		lcs(A, B);
		printf("%d\n", c[strlen(A)][strlen(B)]);
	}
	return 0;
}

Measured memory_bytes: 6628
#include <cstdio>
#include <bitset>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 300;

int n;
char st[N + 5][N + 5];

bitset<2*N + 5> b[N + 5][N + 5];

int main() {
#ifdef Wearry 
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif

    scanf("%d", &n);
    for(int i = 0; i < n; ++i) { scanf("%s", st[i]); }
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            int d = (i - j + n) % n;
            for(int k = 0; k < n; ++k) {
                if(st[i][k] == st[j][(k + d) % n]) b[i][j][k] = b[i][j][k + n] = 1;
            }
        }
    }

    int ans = 0;
    for(int a = 0; a < n; ++a) {

        bitset<2*N + 5> res;
        for(int i = 0; i < n; ++i) res[i] = 1;

        for(int i = 0; i < n; ++i) {
            for(int j = i + 1; j < n; ++j) {
                int x = (i + a) % n, y = (j + a) % n;
                res = (res & (b[x][y] >> j));
            }
        }
        ans = (ans + res.count());
    }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 7552
#include<bits/stdc++.h>
using namespace std;
#define rep(i,x,y) for(int i=x;i<y;i++)
#define print(A,x,n) rep(i,0,n){cout<<(i ? " ":"")<<A[i]x;}cout<<endl;
#define pprint(A,y,m,n) rep(j,0,m){print(A[j],y,n);}
const long mod=1e9+7;
const int size=1e5;
const long inf=1e9;
int main(){
	int N;cin>>N;
	int ans = 0;
	for(int i=1;i<=N;i+=2){
		int cnt = 0;
		rep(j,1,i+1){
			if(i%j==0) cnt++;
		}
		if(cnt == 8) ans++;
	}cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
long long A, B;
int main(){
    int i, n;
    long long a, b, TA, TA2;
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%lld%lld",&a,&b);
        if(!i){
            A=a,B=b;
        }
        else{
            TA = (A+a-1)/a*a;
            TA2 = (B+b-1)/b*a;
            if(TA<TA2)A=TA2;
            else A = TA;
            B=A/a*b;
        }
    }
    printf("%lld\n",A+B);
}

Measured memory_bytes: 128
#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>

/* define */
#define Yes(X) puts ( X ? "Yes" : "No")
#define YES(X) puts ( X ? "YES" : "NO")
#define FOR(i, a, b) for ( int i = a; i < b ; i++)
#define REP(i, n) for ( int i = 0; i < n ; i++)
#define max(a, b) (((a) > (b)) ? (a) : (b))
#define min(a, b) (((a) < (b)) ? (a) : (b))
#define max3(a, b, c) ((max((a), (b)) > (c)) ? max((a), (b)) : (c))
#define min3(a, b, c) ((min((a), (b)) < (c)) ? min((a), (b)) : (c))

/* const */
const int MOD = (int)1e9 + 7;

/* alias */
typedef long long ll;
typedef unsigned  u;

/* function */
int cmp(const void *a, const void *b) {
	return *(int*)a - *(int*)b;
}
int cmp2(const void *a, const void *b) {
	return *(int*)b - *(int*)a;
}
int gcd(int a, int b) {
	if (b != 0)return gcd(b, a % b);
	return a;
}
ll Lgcd(ll a, ll b) {
	if (b != 0) return Lgcd(b, a % b);
	return a;
}
int lcm(int a, int b) {
	return a / gcd(a, b) * b;
}
ll Llcm(ll a, ll b) {
	return a / Lgcd(a, b) * b;
}


/* main */
int main() {
	int n, a[100000], f = 1;
	scanf("%d", &n);
	REP(i, n) scanf("%d", &a[i]);
	if (n % 3) f = 0;
	else {
		qsort(a, n, sizeof(int), cmp);
		FOR(i, 0, n / 3 - 1)	if (a[i] ^ a[i + 1]) f = 0;
		FOR(i, n / 3, n / 3 * 2 - 1)	if (a[i] ^ a[i + 1]) f = 0;
		FOR(i, n / 3 * 2, n - 1)	if (a[i] ^ a[i + 1]) f = 0;
		if ((a[0] ^ a[n / 3]) ^ a[n / 3 * 2]) f = 0;
	}
	int zf = 1;
	REP(i, n) if (a[i] != 0) zf = 0;

	Yes(f || zf);
	return 0;
}

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

int main() {
    int n;
    cin >> n;
    string s;
    cin >> s;
    int **tbl;
    tbl = new int*[n];
    for (int i = 0; i < n; ++i) {
        tbl[i] = new int[n];
        for (int j = 0; j < n; ++j) {
            tbl[i][j] = 0;
        }
    }
    int max_len = 0;
    for (int i = 0; i < n - 1; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (tbl[i][j] == -1) {
                continue;
            }
            int c = 0;
            while (i+c < n && j+c < n && i+c < j && s[i+c] == s[j+c]) {
                c++;
                tbl[i+c][j+c] = -1;
            }
            tbl[i][j] += c;
            if (c > max_len) {
                max_len = c;
            }
        }
    }
    cout << max_len << "\n";
    return 0;
}


Measured memory_bytes: 98048
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define ASSERT(C, ...) assert( (C) || (PRINT(__VA_ARGS__), false) )
template <class Head> void PRINT(Head head) {
    std::cout << head << "\n";
}
template <class Head, class... Tail> void PRINT(Head head, Tail... tail) {
    std::cout << head << " ";
    PRINT(tail...);
}

ll solve1(ll N, ll M, ll V, ll P, vector<ll>& A) {
    sort(A.begin(), A.end());
    if ( P >= V ) {
        //ll cr = A[N-1-(V-1)] - M;
        ll cr = A[N-P] - M;
        ll i = lower_bound(A.begin(), A.end(), cr) - A.begin();
        return N - i;
    } else {
        ll cr = A[N-1-(P-1)] - M;
        ll i0 = lower_bound(A.begin(), A.end(), cr) - A.begin();
        if ( i0 > V - P ) {
            return N - i0;
        } else {
            vector<ll> ca(N);
            ll sm = 0;
            for ( int i = 0; i < N; i++ ) {
                sm += A[i];
                ca[i] = sm;
            }
            for ( ll j = i0; j < N-P; j++ ) {
                ll rm = (V - P - j) * M;
                ll f = (A[j]+M) * (N-P-j) - (ca[N-P] - ca[j]);
                if ( f >= rm ) {
                    return N - j;
                }
            }
            return P;
        }
    }
    return -1;
}

ll solve2(ll N, ll M, ll V, ll P, vector<ll>& A) {
    sort(A.begin(), A.end(), greater<>());

    auto check = [&](ll x) {
        if ( x < P ) return true;
        ll c = (P-1) * M;
        if ( A[P-1] > A[x] + M ) return false;
        c += (N - x) * M;
        for ( int i = P-1; i < x; i++ ) {
            c += A[x] + M - A[i];
        }
        return c >= V * M;
    };

    ll l = 0, r = N;
    while ( r - l > 1 ) {
        ll m = (l + r) / 2;
        if ( check(m) ) l = m;
        else r = m;
    }
    return l + 1;
}
int test() {
    mt19937_64 mt64(0);
    uniform_int_distribution<ll> rnd(1, 100);
    uniform_int_distribution<ll> rnd1(1, 10);
    uniform_int_distribution<ll> rnd2(1, 10000);

    ll tmax = 100;
    for ( int t = 0; t < tmax; t++ ) {
        ll n = 1 + rnd(mt64);
        ll m = t < tmax/2 ? rnd1(mt64) : rnd2(mt64);
        ll v = 1 + rnd(mt64) % (n-1);
        ll p = 1 + rnd(mt64) % (n-1);
        vector<ll> a(n);
        for ( int i = 0; i < n; i++ ) {
            a[i] = (t < tmax/2 ? rnd1(mt64) : rnd2(mt64)) - 1;
        }
        if ( t == 16 ) {
            ll z = 1;
        }
        ll ans1 = solve1(n,m,v,p,a);
        ll ans2 = solve2(n,m,v,p,a);
        ASSERT(ans1 == ans2, t, ans1, ans2);
    }

    return 0;
}

int main() {
    //test();

    ll N, M, V, P;
    cin >> N >> M >> V >> P;
    vector<ll> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];
    }
    auto ans = solve2(N, M, V, P, A);
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long, long long> P;
struct edge{long long to,cost;};
const int inf = 1 << 27;
const long long INF = 1LL << 60;
const int COMBMAX = 1001001;
const long long MOD = 1000000007;
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define eachdo(v, e) for(const auto& e : (v))
#define all(v) (v).begin(), (v).end()
#define lower_index(v, e) (long long)distance((v).begin(), lower_bound((v).begin(), (v).end(), e))
#define upper_index(v, e) (long long)distance((v).begin(), upper_bound((v).begin(), (v).end(), e))
long long mpow(long long a, long long n, long long mod = MOD){long long res = 1; while(n > 0){if(n & 1)res = res * a % mod; a = a * a % mod; n >>= 1;} return res;}
void yn(bool j){cout << (j ? "Yes" : "No") << endl; return;}
template<class Head> void pt(Head&& head){cout << head << endl; return;}
template<class Head, class... Tail> void pt(Head&& head, Tail&&... tail){cout << head << " "; pt(forward<Tail>(tail)...);}
template<class T> void debug(T v){rep(i, v.size()) cout << v[i] << " " ; cout << endl;}
template<class T> void debug2(T v){rep(i, v.size()){rep(j, v[i].size()) cout << v[i][j] << " " ; cout << endl;}}
template<class T1, class T2> long long bcount(T1 v, T2 a){return upper_index(v, a) - lower_index(v, a);} 
template<class T1, class T2> inline bool chmin(T1 &a, T2 b){if(a > b){a = b; return true;} return false;}
template<class T1, class T2> inline bool chmax(T1 &a, T2 b){if(a < b){a = b; return true;} return false;}

int main(){
    ll N, K; cin >> N >> K;
    vector<ll> a(N), copy(N);
    rep(i, N) cin >> a[i];
    rep(i, N) --a[i]; 
    ll node = 0;
    rep(i, 62){
        rep(j, N) copy[j] = a[a[j]];
        if (K >> i & 1) node = a[node];
        a = copy;
    }
    pt(node + 1);
}

Measured memory_bytes: 6428
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
constexpr char ln =  '\n';
constexpr long long MOD = 1000000007LL;
constexpr long long INF = 1000100010001000100LL;
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define rept(i, j, n) for(int i=(j); i<(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


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

    int cnt = -1;
    map<int, int> mp;
    rep(i, n){
       int a; cin >> a;
       mp[a-1]++; mp[a]++; mp[a+1]++;
    }
    for(auto m: mp){
        if(cnt < m.second){
            cnt = m.second;
        }
    }
    cout << cnt << ln;
}

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

int main() {
  string S; cin>>S;
  if (S=="Sunny") cout<<"Cloudy"<<endl; 
  if (S=="Cloudy") cout<<"Rainy"<<endl; 
  if (S=="Rainy") cout<<"Sunny"<<endl; 
}


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

#define INCANT cin.tie(0), ios::sync_with_stdio(false), cout << fixed << setprecision(20)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define all(x) (x).begin(),(x).end()
#define out(a) cout << a << endl
#define PRINT(V) for (auto v : (V)) cout << v << " "

const int MOD = 1000000007;
const double PI = acos(-1.0);

int solve() {
    ll K, A, B;
    cin >> K >> A >> B;
    rep(i, 1000){
        if(A<=K*i && K*i<=B){
            return 1;
        }
    }
    return 0;
}
int main() {
    INCANT;
    int flag = solve();
    if(flag) out("OK");
    else out("NG");
    return 0;
}




Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <time.h>
#define rep(i,n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
using P  = pair<ll,ll>;
using vi = vector<ll>;
using vv = vector<vi>;
const ll INF = 1001001001001001;
const ll NUM = 1<<10;

int main(){
    int d,t,s;
    cin >> d >> t >> s;
    if(d<=t*s)cout<<"Yes\n";
    else cout<<"No\n";
    
    return 0;
}


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

int main() {
    int n ;
    cin >> n ;
    string s ;
    cin  >> s ;
    int res = 1 ;
    char t = s[0] ;
    rep(i, n){
        if(s[i] == t){
            continue ;
        }
        else {
            t = s[i] ;
            res++ ;
        }
    }
    cout << res << endl ;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()
using ll = long long;
const ll mod = 1000000007;
const ll INF = 100000000000000000LL;
signed main(){
    string s;
    rep(i,3){
        cin>>s;
        cout<<char(toupper(s[0]));
    }
    cout<<endl;
}

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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
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 (a>b) { a=b; return 1; } return 0; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

ll N, K;
vector<ll> pos, neg;
ll z = 0;

ll count_neg(ll x){
	//正×負で絶対値がx以上になるものを探す
	ll res = 0;
	for(auto val: pos){

		/*
		ll ng = -1;
		ll ok = neg.size();
		while(ok-ng>1){
			ll md = (ok+ng)/2;
			if(val*neg[md]>=x) ok = md;
			else ng = md;
		}
		res += (ll)neg.size() - ok;
		*/

		ll tmp = neg.end() - lower_bound(neg.begin(), neg.end(), (x+val-1)/val);
		res += tmp;
	}
	return res;
}

ll count_pos(ll x){
	ll res = 0;

	// 負×負で絶対値がx以下になるものを探す
	REP(i, neg.size()){
		ll val = neg[i];

		/*
		ll ok = -1;
		ll ng = i;
		while(ng-ok>1){
			ll md = (ok+ng)/2;
			if(val*neg[md]<=x) ok = md;
			else ng = md;
		}
		res += ng;
		*/

		ll tmp = upper_bound(neg.begin(), neg.begin()+i, x/val) -  neg.begin();

		res += tmp;
	}

	// 正×正で絶対値がx以下になるものを探す
	REP(i, pos.size()){
		ll val = pos[i];

		/*
		ll ok = -1;
		ll ng = i;
		while(ng-ok>1){
			ll md = (ok+ng)/2;
			if(val*pos[md]<=x) ok = md;
			else ng = md;
		}
		res += ng;
		*/

		ll tmp = upper_bound(pos.begin(), pos.begin()+i, x/val) -  pos.begin();

		res += tmp;
	}

	return res;
}

ll count(ll x){
	ll res = 0;
	ll zeros = N*(N-1)/2 - (N-z)*(N-z-1)/2;

	if(x<0){
		res += count_neg(-x);
	}else if(x==0){
		res += count_neg(0);
		res += zeros;
	}else{
		res += count_neg(0);
		res += zeros;
		res += count_pos(x);
	}

	return res;
}

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

    
    cin >> N >> K;
    vector<ll> A(N);
    REP(i, N) cin >> A[i];

    REP(i, N){
    	if(A[i]>0) pos.push_back(A[i]);
    	else if(A[i]==0) z++;
    	else neg.push_back(-A[i]);
    }
    sort(pos.begin(), pos.end());
    sort(neg.begin(), neg.end());

    //cout << pos << endl;
    //cout << neg << endl;

    const ll INF = (ll)1e18 + 5;

    ll ng = -INF;
    ll ok = INF;
    while(ok-ng>1){
    	ll md = (ok+ng)/2;
    	if(count(md)>=K) ok = md;
    	else ng = md;
    }

    cout << ok << endl;
    return 0;
}

Measured memory_bytes: 3956
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)
INF = 1<<32


def solve(N: int):

    print((N-1)//2)

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>

#define int long long

using namespace std;


class Solver {
};

signed main() {
	int n, m, p;
	cin >> n >> m >> p;
	vector<int> ds(m, 0);
	for (int i = 0; i < m; i++) {
		cin >> ds[i];
	}
	sort(ds.begin(), ds.end());

	vector<int> left(1,0);
	vector<int> right(1,0);
	for (int i = 0; i < m; i++) {
		if (ds[i] < p) {
			left.emplace_back(p - ds[i]);
			right.emplace_back(n - p + ds[i]);
		}
		else {
			left.emplace_back(n - ds[i] + p);
			right.emplace_back(ds[i] - p);
		}
	}

	sort(left.begin(), left.end());
	sort(right.begin(), right.end());
	int res = 1e9;
	for (int i = 0; i <=m; i++) {
		int low = min(left[i], right[m - i]);
		int high = max(left[i], right[m - i]);
		int tmp = low * 2 + high;
		tmp *= 100;
		res = min(res, tmp);
	}
	cout << res << endl;
}


Measured memory_bytes: 3272
class UnionFind():
  def __init__(self,n):
    self.n=n
    self.root=[-1]*(n+1)
    self.rank=[0]*(n+1)
  def FindRoot(self,x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.FindRoot(self.root[x])
      return self.root[x]
  def Unite(self,x,y):
    x=self.FindRoot(x)
    y=self.FindRoot(y)
    if x==y:
      return
    else:
      if self.rank[x]>self.rank[y]:
        self.root[x]+=self.root[y]
        self.root[y]=x
      elif self.rank[x]<=self.rank[y]:
        self.root[y]+=self.root[x]
        self.root[x]=y
        if self.rank[x]==self.rank[y]:
          self.rank[y]+=1
  def isSameGroup(self,x,y):
    return self.FindRoot(x)==self.FindRoot(y)
  def Count(self,x):
    return -self.root[self.FindRoot(x)]
  
n=int(input())
uf=UnionFind(n)
arr=[list(map(int,input().split()))+[i+1] for i in range(n)]
arr=sorted(arr,key=lambda x:x[0])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if y<=ty:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if ty2<=ty:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
arr=sorted(arr,reverse=True,key=lambda x:x[1])
x,y,i=arr[0]
tmp=[]
for tx,ty,j in arr:
  if x>=tx:
    uf.Unite(i,j)
    for tx2,ty2,j2 in tmp:
      if tx2>=tx:
        uf.Unite(j,j2)
    tmp=[]
  else:
    tmp.append([x,y,i])
    x=tx
    y=ty
    i=j
for i in range(1,n+1):
  print(uf.Count(i))

Measured memory_bytes: 56404
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n, k, d[1000], a[1000][1000], i, j, ans=0, cnt[1000]={0};
    cin >> n >> k;
    for(i=0;i<k;i++){
        cin >> d[i];
        for(j=0;j<d[i];j++){
            cin >> a[i][j];
            cnt[a[i][j]]++;
        }
    }
    for(i=1;i<=n;i++){
        if(cnt[i]==0) ans++;
    }
    cout << ans <<endl;
    return 0;
}



Measured memory_bytes: 4008
// 
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define e_b emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ipair;
typedef pair<ll,ll> lpair;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る
void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る


// void dfs(string cur,int nan){
//     if(nan==sou){
//         bef++;
//         if(bef==n){
//             ans=cur;
//             return;
//         }
//         return;
//     }
//     if(n<bef) return;
//     for(int i=1;i<=26;i++){
//         dfs(cur+char(96+i),nan+1);
//     }
//     return;
// }
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    ll sou=1;
    ll bef=0;
    ll n;
    string ans="";
    cin>>n;
    ll now=26;
    while(now<n){
        sou++;
        bef=now;
        now=now+ll(pow(26,sou));
    }
    // cout<<sou<<endl;
    vector<int> num;
    bef++;
    //cout<<bef<<endl;
    for(int i=sou-1;i>=1;i=i-1){
        int sou2=1;
        ll end=bef+ll(pow(26,i))-1; //ブロックの最後
        while(end<n){
            bef=end+1;
            end=bef+ll(pow(26,i))-1;
            sou2++;
            //cout<<end<<endl;
        }
        num.emplace_back(sou2);
        //if(sou2!=1) bef-=ll(pow(26,i));
    }
    //cout<<num<<endl;
    //cout<<ans<<endl;
    ll ind=bef-1;
    //cout<<ind<<endl;
    rep(i,sou-1){
        ans+=char(num[i]+96);
    }
    for(int i=1;i<=26;i++){
        ind++;
        if(ind==n){
            ans+=char(96+i);
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 4064
#include<stdio.h>
#include<stdlib.h>

struct node{
  struct node *right;
  struct node *left;
  struct node *parent;
  int key;
};
typedef struct node * Node;
#define NIL NULL

Node root;

/*Node treeMinimum(Node x){


}*/

/*Node treeMaximum(Node x){


}*/

/*Node treeSearch(Node u, int k){


}*/

/*Node treeSuccessor(Node x){


}*/

/*void treeDelete(Node z){
  Node y; // node to be deleted
  Node x; // child of y



}*/

void insert(int k){
  Node y = NIL;
  Node x = root;
  Node z;

  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
  while(x != NIL){
    y = x;
    if(z->key < x->key)  x = x->left;
    else x = x->right;
  }
  z->parent = y;
  if(y == NIL)  root = z;
  else if(z->key < y->key)  y->left = z;
  else y->right = z;
}

void inorder(Node u){
  if(u == NULL) return ;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}
void preorder(Node u){
  if(u == NIL) return;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}


int main(){
  int n, i, x;
  char com[20];
  scanf("%d", &n);

  for ( i = 0; i < n; i++ ){
    scanf("%s", com);
     if ( com[0] == 'i' ){
      scanf("%d", &x);
      insert(x);
    } else if ( com[0] == 'p' ){
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
    }
  }

  return 0;
}



Measured memory_bytes: 25136