akhauriyash/Code-Regression huggingface dataset:
# from math import factorial,sqrt,ceil,gcd
# from itertools import permutations as permus
# from collections import deque,Counter
# import re
# from functools import lru_cache # 簡単メモ化 @lru_cache(maxsize=1000)
# from decimal import Decimal, getcontext
# # getcontext().prec = 1000
# # eps = Decimal(10) ** (-100)

# import numpy as np
# import networkx as nx
# from scipy.sparse.csgraph import shortest_path, dijkstra, floyd_warshall, bellman_ford, johnson
# from scipy.sparse import csr_matrix
# from scipy.special import comb

# slist = "abcdefghijklmnopqrstuvwxyz"
N = int(input())
arrA = [list(map(int,input().split())) for _ in range(N)]
arrA.sort(key = lambda x:x[1])
num = 0
for arr in arrA:
    num += arr[0]
    if num > arr[1]:
        print("No")
        exit()

print("Yes")
# print(*ans)   # unpackして出力。間にスペースが入る
# for row in board:
#     print(*row,sep="")    #unpackして間にスペース入れずに出力する
# print("{:.10f}".format(ans))
# print("{:0=10d}".format(ans))


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

int main() {
  long long N;
  cin >> N;
  long long sum=0,n=N;
  while(n>0){
    sum+=n%10;
    n/=10;
  }
  if(N%sum==0) cout << "Yes" << endl;
  else cout << "No" << endl;
}


Measured memory_bytes: 256
from itertools import permutations

n = int(input())
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))

L = list(permutations(range(1, n + 1)))
# print(L)
p = L.index(P)
q = L.index(Q)

print(abs(p - q))

Measured memory_bytes: 8052
#include <iostream>

using namespace std;

int main()
{
    long long int a, b, n, k;
    cin >> a >> b >> n;
    if ((n - 1) % b > n % b)
    {
        k = (n - 1) % b;
    }
    else
    {
        if (n < b)
            k = n % b;
        else
        {
            k = b - 1;
        }
    }

    cout << ((a * k) / b) - a * (k / b);

    return 0;
}

Measured memory_bytes: 3624
<?php
list($h, $w) = explode(" ", trim(fgets(STDIN)));
for($i = 0; $i < $h; $i++){
    $line = trim(fgets(STDIN));
    for($j = 0; $j < $w; $j++){
        $map[$i][$j] = $line[$j];
    }
}

for($i = 0; $i < $h; $i++){
    for($j = 0; $j < $w; $j++){
        if($map[$i][$j] == "#"){
            $y[$i] = true;
            $x[$j] = true;
        }
    }
}

for($i = 0; $i < $h; $i++){
    for($j = 0; $j < $w; $j++){
        if(isset($y[$i]) && isset($x[$j])){
            echo $map[$i][$j];
        }
    }
    if(isset($y[$i]))echo "\n";
}


Measured memory_bytes: 4728
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using VL = vector<ll>;
#define FOR(i,a,n) for(int i=(a);i<(n);++i)
inline void init() { cin.tie(nullptr); cout.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }
template<class T>inline istream& operator>>(istream& is, vector<T>& v) { for (auto& a : v)is >> a; return is; }
template<class T>inline void print(const T& a) { cout << a << "\n"; }
template<class T>inline void print(const vector<T>& v) { for (int i = 0; i < v.size(); ++i)cout << v[i] << (i == v.size() - 1 ? "\n" : " "); }

//merge [l,m) with [m,r)
void Merge(VL& dat, VL& tmp, int l, int m, int r) {
    int i = l, j = m, k = l;
    for (; i < m || j < r; ++k) {
        if (i == m)
            tmp[k] = dat[j++];
        else if (j == r)
            tmp[k] = dat[i++];
        else if (dat[i] < dat[j])
            tmp[k] = dat[i++];
        else
            tmp[k] = dat[j++];
    }
    for (k = l; k < r; ++k)
        dat[k] = tmp[k];
}

void MergeSort(VL& a) {
    int n = a.size();
    VL tmp(n);
    for (int range = 1; range < n; range *= 2) {
        for (int i = 0; i < n; i += range * 2) {
            if (i + range < n)
                Merge(a, tmp, i, i + range, min(i + range * 2, n));
        }
    }
}

int main() {
    init();
    
    int n, k; cin >> n >> k;
    VL h(n); cin >> h;
    MergeSort(h);
    ll ans = 0;
    FOR(i, 0, n - k)ans += h[i];
    print(ans);

    return 0;
}

Measured memory_bytes: 6368
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    scanf("%d",&n);
    int a[n][3];
    for(int i = 0; i < n; i++){
        scanf("%d %d %d",&a[i][0], &a[i][1], &a[i][2]);
    }
    int dp[n][3];
    dp[0][0] = a[0][0];
    dp[0][1] = a[0][1];
    dp[0][2] = a[0][2];
    for(int i = 1; i < n; i++){
        for(int j = 0; j < 3; j++){
            dp[i][j] = a[i][j] + max(dp[i-1][(j+1)%3],dp[i-1][(j + 2)%3]);
        }
    }
    printf("%d\n",max(dp[n-1][0],max(dp[n-1][1],dp[n-1][2])));
    return 0;
}

Measured memory_bytes: 2560
n, k = map(int, input().split())
A = list(map(lambda x: int(x)-1, input().split()))
bit = k.bit_length()
table = [[0]*n for _ in range(bit)]
table[0] = A

for i in range(1, bit):
    for j in range(n):
        table[i][j] = table[i-1][table[i-1][j]]

ans = 0
for i in reversed(range(bit)):
    if (1 << i) <= k:
        k -= 1 << i
        ans = table[i][ans]
print(ans+1)

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

#define int long long

#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}

signed main(){
    string s;cin>>s;

    if(s.size()<26){
        for(char c='a';c<='z';c++){
            if(find(all(s),c)!=s.end())continue;
            s+=c;
            break;
        }
        cout<<s<<endl;
        return 0;
    }

    int pos=-1;
    rep(i,25)if(s[i]<s[i+1])pos=i;
    if(pos==-1){
        cout<<-1<<endl;
        return 0;
    }

    char x=s[pos];
    s=s.substr(0,pos);
    for(char c=x+1;c<='z';c++){
        if(find(all(s),c)!=s.end())continue;
        s+=c;
        break;
    }
    cout<<s<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define FIO ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define DEBUG(x)           cout << '>' << #x << ':' << x << endl;
#define forn(i,n)          for(int i=0;i<(int)n;++i)
#define for1(i,n)          for(int i=1;i<=(int)n;++i)
#define forr(i,n)          for(int i=(int)n-1;i>=0;--i)
#define forre(i,a,b)       for(int i=(int)b;i>=(int)a;--i)
#define fore(i,a,b)        for(int i=(int)a;i<=(int)b;++i)
#define input(arr,n)       for(int i=0;i<n;i++)cin>>arr[i]
#define output(arr,n)      for(int i=0;i<n;i++)cout<<arr[i]<<" "
#define for_each(arr)      for(auto& it:arr)cout<<it<<" "
#define ff                 first
#define ss                 second
#define PI                 acos(-1.0)
#define all(a)             a.begin(),a.end()
#define rall(a)            a.rbegin(),a.rend()
#define Unique(a)          sort(all(a)),a.erase(unique(all(a)),a.end())
#define pb(x)              push_back(x)
#define eb(x)              emplace_back(x) 
#define ppb(x)             pop_back(x)
#define pf(x)              push_front(x)
#define ppf(x)             pop_front(x)
#define in(x,y)            insert({x,y})
#define Sort(a)            sort(a.begin(),a.end())
#define mem(arr,a)         memset(arr,a,sizeof arr)
#define ins(a)             insert(a)
#define max2(a,b)          max(a,b)
#define max3(a,b,c)        max(a,max(b,c))
#define max4(a,b,c,d)      max(a,max3(b,c,d))
#define min2(a,b)          min(a,b)
#define min3(a,b,c)        min(a,min(b,c))
#define min4(a,b,c,d)      min(a,min3(b,c,d))
typedef long long ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<char> vc;
typedef vector<double> vd;
/*inline int two(int n) { return 1 << n; }
inline int test(int n, int b) { return (n>>b)&1; }
inline void Set(int & n, int b) { n |= two(b); }
inline void Reset(int & n, int b) { n &= ~two(b); }
inline int last_bit(int n) { return n & (-n); }
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }*/
/*int fx[]= {0,0,1,-1,-1,1,-1,1};
int fy[]= {1,-1,0,0,-1,1,1,-1};
int fx1[]={0,1,1,1,0,-1,-1,-1};
int fy1[]={1,1,0,-1,-1,-1,0,1};*/

ll a,b,c,n,ans,cn1,cn2,cn3,t;
string s,s1,s2;

vector<int>v1;

bool is_prime(int lm){
	for(int i=2;i*i<=lm;i++){
		if(lm%i==0)return false;
	}
	return true;
}
int main()
{
    FIO;
   // #ifndef ONLINE_JUDGE
   // freopen("input.txt","r",stdin);
   // freopen("output.txt","w",stdout);
   // #endif
    cin>>n;
    while(true){
    	if(is_prime(n)){
    		cout<<n<<endl;
    		return 0;
    	}
    	++n;
    }
    
    #ifdef ONLINE_JUDGE
    cerr<<"Time elapsed: "<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
    #endif
   return 0;
}
 

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;

ll dp[100010][2];
const ll INF=1e18;

void chmax(ll &a,ll b){
    if(a<b) a=b;
}

int main(){
  int N;
  cin>>N;
  vector<ll> A(N);
  rep(i,N) cin>>A[i];

  for(int i=0;i<=N;i++) for(int j=0;j<2;j++) dp[i][j]=-INF;
  dp[0][0]=0;
  for(int i=0;i<N;i++){
      for(int j=0;j<2;j++){
          if(dp[i][j]==-INF) continue;
          
          if(A[i]%2){
              chmax(dp[i+1][1],dp[i][j]+A[i]/2);
              if(j==1) chmax(dp[i+1][0],dp[i][j]+A[i]/2+1);
          }else{
              chmax(dp[i+1][0],dp[i][j]+A[i]/2);
              if(j==1&&A[i]>0) chmax(dp[i+1][1],dp[i][j]+A[i]/2);
          }
      }
  }

  cout<<max(dp[N][0],dp[N][1])<<endl;

  return 0;
}


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


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


    
    
    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define ll long long 
using namespace std;
int main() {
    ll n, i, sum=0, dummy, med, A;
    scanf("%lld", &n);
    vector<ll> a(n+1);

    for(i=1; i<=n; i++) {
        scanf("%lld", &A);
        a[i] = A-i;
    }
    
    sort(a.begin() + 1, a.end());

    med = a[n/2+1];

    for(i=1; i<=n; i++) {
        sum += abs(a[i]-med);
    }

    printf("%lld\n", sum);
}


Measured memory_bytes: 1792
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int N = sc.nextInt();
    int K = sc.nextInt();
    int[] p = new int[N];
    int sum = 0;
    for (int i =0; i < N; i++) {
      p[i] = sc.nextInt();
    }
    Arrays.sort(p);
    for (int j = 0; j < K; j++) {
      sum += p[j];
    }
    System.out.println(sum);
  }
}


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

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define siz(x) (x).size()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a / gcd(a, b) * b; }
int mpow(int a, int b) {
	if (b & 1)return a * mpow(a, b - 1);
	return mpow(a * a, b >> 1);
}
int mpow(int a, int b, int m) {
	if (b & 1)return a * mpow(a, b - 1, m) % m;
	return mpow(a * a % m, b >> 1, m) % m;
}
vector<vector<int>> graph;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n; cin >> n;
	graph.resize(n + 1);
	for (int i = 1; i < n; i++) {
		int x; cin >> x;
		graph[x].push_back(i);
	}
	for (int i = 1; i <= n; i++) {
		cout << graph[i].size() << '\n';
	}
	return 0;
}

Measured memory_bytes: 14268
#include <bits/stdc++.h>
#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++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;
 
//const int dx[] = {1, 0, -1, 0, 1, -1, -1, 1};
//const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
 
int main()
{
	int n;
	cin >> n;
	int a[n];
	REP(i, n) cin >> a[i];
	bool current = 0;
	int sum = 0;
	int max = 0;
	REP(i, n){
		if (a[i] == 1){
			if (current) sum++;
			else sum = 1;
			current = 1;
		}
		else {
			current = 0;
			sum = 0;
		}
		if (max < sum) max = sum;
	}

	cout << max + 1 << endl;

}



Measured memory_bytes: 3120
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

int main(){
    const int maxSize = 300001;
	vector<long long> inv(maxSize);
	vector<long long> fact(maxSize);
	vector<long long> factInv(maxSize);
	for(int i=0;i<2;i++) inv[i] = fact[i] = factInv[i] = 1;
	for(int i=2;i<maxSize;i++){
		inv[i] = inv[MOD % i] * (MOD - MOD / i) % MOD;
		fact[i] = fact[i-1] * i % MOD;
		factInv[i] = factInv[i-1] * inv[i] % MOD;
	}
	auto comb = [&](int n, int r){
		if(n < r || r < 0) return 0LL;
		return fact[n] * factInv[n-r] % MOD * factInv[r] % MOD;
	};
    long long N, A, B, K; cin >> N >> A >> B >> K;
    long long res = 0;
    for(int i=0;i<=N;i++){
        if(K - A*i < 0) break;
        if((K - A*i)%B != 0) continue;
        int j = (K - A*i)/B;
        res += comb(N, i) * comb(N, j);
        res %= MOD;
    }
    cout << res << endl;
}

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

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<ll> vi;
typedef vector<ii> vii;
#define REP(i,n) for (ll i = 0; i < n; ++i)
#define FOR(i,m,n) for (ll i = m; i < n; ++i)

const ll MAX = 1e5+10;
const ll MOD = 1e9+10;

ll N;
ll ga, sa, ba, gb, sb, bb;

inline ll range(ll a, ll b, ll n) {
    if (a < b) return n;
    else return 0;
}

int main() {
    cin >> N;
    cin >> ga >> sa >> ba >> gb >> sb >> bb;
    ll G, S;

    ll mx = N;

    G = range(ga, gb, N);
    for (ll g = 0; g <= G; g += ga) {
        S = range(sa, sb, N-g);
        for (ll s = 0; s <= S; s += sa) {
            ll n = N-g-s;
            ll b;
            if (ba < bb) {
                b = n/ba*ba;
                n = n-b;
            } else {
                b = 0;
            }
            
            n += g/ga*gb;
            n += s/sa*sb;
            n += b/ba*bb;
            mx = max(mx, n);
        }
    }

    vii p;
    if (ga > gb) p.push_back(make_pair(ga, gb));
    if (sa > sb) p.push_back(make_pair(sa, sb));
    if (ba > bb) p.push_back(make_pair(ba, bb));

    if (p.size() == 0) {
        cout << mx << endl;
    } else if (p.size() == 1) {
        N = mx;
        ll a = p[0].first, b = p[0].second;
        ll n = N/b*b;
        ll m = N-n;
        cout << m + n/b*a << endl;
    } else if (p.size() == 2){
        N = mx;
        ga = p[0].first, gb = p[0].second;
        sa = p[1].first, sb = p[1].second;
        for (ll g = 0; g <= N; g += gb) {
            ll n = N-g;
            ll s = n/sb*sb;
            n -= s;

            n += g/gb*ga;
            n += s/sb*sa;
            if (n > mx) mx = n;
        }

        cout << mx << endl;
    } else {
        N = mx;
        G = range(gb, ga, N);
        for (ll g = 0; g <= G; g += gb) {
            S = range(sb, sa, N-g);
            for (ll s = 0; s <= S; s += sb) {
                ll n = N-g-s;
                ll b;
                if (bb < ba) {
                    b = n/bb*bb;
                    n = n-b;
                } else {
                    b = 0;
                }
                
                n += g/gb*ga;
                n += s/sb*sa;
                n += b/bb*ba;
                mx = max(mx, n);
            }
        }
        
        cout << mx << endl;
    }
}

Measured memory_bytes: 256
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

x, y, a, b, c = map(int, readline().split())
p = sorted(list(map(int, readline().split())), reverse=True)
q = sorted(list(map(int, readline().split())), reverse=True)
r = list(map(int, readline().split()))
r += p[:x] + q[:y]
r.sort(reverse=True)
print(sum(r[:x + y]))


Measured memory_bytes: 21600
n,m = map(int,input().split())
sc = [list(map(int,input().split())) for _ in range(m)]
for i in range(1000):
    num = str(i)

    #もし取り出した値がn桁かつすべての条件と矛盾しないならば表示して終了
    if len(num) == n and all(num[s-1] == str(c) for s,c in sc):
        print(i)
        exit()
        
print(-1)


Measured memory_bytes: 2940
N = int(input())
A = [int(i) for i in input().split()]
A.sort(reverse=True)

log = []

# すべて正
if A[-1] > 0 :
    a = A.pop()
    b = A.pop()
    log.append([a, b])
    A.append(a - b)
# すべて負
elif A[0] < 0 :
    a = A.pop(0)
    b = A.pop()
    log.append([a, b])
    A = [a-b] + A
    
i = 1
while A[i] > 0 :
    a = A.pop()
    log.append([a, A[i]])
    A.append(a-A[i])
    i += 1
    
while i < len(A) :
    log.append([A[0], A[i]])
    A[0] -= A[i]
    i += 1
    
print(A[0])
for l in log :
    print(l[0], l[1])
    

Measured memory_bytes: 67692
def main_c(X_list, N, M):
    
    X_list_s = sorted(X_list)
    D_list = [X_list_s[i+1] - X_list_s[i] for i in range(M-1)]
    D_list_s = sorted(D_list)
    
    if M > N:
        res = sum(D_list_s[:(M - N)])
    else:
        res = 0
        
    return res

if __name__ == "__main__":
    N, M = map(int, input().split())
    X_list = list(map(int, input().split()))
    res = main_c(X_list, N, M)
    print(res)

Measured memory_bytes: 13968
#include <stdio.h>

int main() {
  int n,i,j,k,l,m,t;
  int G[101][101];

  scanf("%d",&n);

  for(i=0; i<n+1; i++)
    for(j=0; j<n+1; j++) {
      G[i][j] = 0;
    }

  for(i=0; i<n; i++){
    scanf("%d %d ",&k,&l);

    for(j=0; j<l; j++) {
      scanf("%d",&m);
      G[k-1][m-1] = 1;
    }
  }

  for(i=0; i<n; i++){
    for(j=0; j<n; j++) {
      printf("%d",G[i][j]);
      if(j != n-1) printf(" ");
    }
    printf("\n");
  }

  return 0;
}



Measured memory_bytes: 2052
n=int(input())
a=list(map(int,input().split()))
b=[0]
c=[0]
for i in a:
  b+=[b[-1]+i]
for i in a[::-1]:
  c+=[c[-1]+i]
c=c[::-1]
print(min(abs(b[i]-c[i])for i in range(1,n+1)))

Measured memory_bytes: 34700
#include<bits/stdc++.h>
// #include "/Users/Coder_Jay/Desktop/Codeforces/header.h"
 
// Competetive Template:
typedef long long int lli;
typedef unsigned long long int ulli;
typedef long double ldb;
 
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ba  back
#define si size()
#define be begin()
#define en end()
#define le length()
#define mp make_pair 
#define mt make_tuple
#define fi first
#define se second
#define gcd __gcd
#define maxe *max_element
#define mine *min_element
 
#define forz(i,n) for(long long int i=0;i<n;i++)
#define rep(i,k,n) for (lli i = k; i <= n; i++)
#define deci(n)  fixed<<setprecision(n)
#define high(n) __builtin_popcount(n)
#define parity(n) __builtin_parity(n)
#define ctz(n)  __builtin_ctz(n)
#define mod 1000000007
#define mod2 998244353
#define kira ios::sync_with_stdio(0), cin.tie(0),cout.tie(0)
#define  START      auto start = chrono::steady_clock::now()
#define END         auto end = chrono::steady_clock::now()

using namespace std;
typedef pair <lli,lli> pll;
 
// CODE BEGINS :

int main()
{
    kira; START;

    lli n, m, pro=1; cin>>n>>m;

    lli arr[n];
    forz(i,n)
    {
        lli t; cin>>t;
        arr[i]=(t/2);
        pro = pro * arr[i];
    }

    lli d = arr[0];
    
    for(lli i=1; i<n; i++) d = (d*arr[i])/(__gcd(d,arr[i]));

    // cout<<d<<endl;
    
    forz(i,n)
    {
        if((d/arr[i])%2==0)
        {
            cout<<0<<endl;
            return 0;
        }
    }
    
    lli cnt=(m/d);
    
    if(cnt%2==0) cout<<(cnt/2)<<endl;
    else cout<<(cnt/2)+1<<endl;

    END;
    return 0;
}





















Measured memory_bytes: 1024
N = int(input())
ans = -1
bef = -1
for i in range(N):
    now = int(input())
    if now - bef > 1:
        ans = -1
        break
    elif now - bef == 1:
        ans += 1
        bef = now
    else:
        ans += now
        bef = now
 
print(str(ans))

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

int main() {

	ll a,b,c,k;
	cin>>a>>b>>c>>k;
	if(k<=a)
	    cout<<k;
	else if(k<=(a+b))
	    cout<<a;
	else 
	    cout<< a - (k-(a+b));
	return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
#define vll vector<ll>
#define vi vector<int>
#define vpll vector<pair<ll,ll>>
#define pii pair<int,int>
#define REP(i,a) for(int (i)=0; (i)<(a); (i)++)
#define RREP(i,a) for(int (i)=a-1; (i)>=(0); (i)--)
#define REP2(i,a,b) for(int (i)=(a); (i)<(b); (i)++)
#define MOD 1000000007
#define ALL(v) v.begin(), v.end()
#define m0(x) memset(x,0,sizeof(x))
typedef long long ll;

using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int N;
  cin>>N;
  vi p(N),q(N);
  REP(i,N){
    cin>>p[i];
    q[i]=p[i];
  }
  sort(ALL(p));
  int cnt =0;
  REP(i,N){
    if(p[i]!=q[i])cnt++;
  }
  if(cnt==0 || cnt ==2){
    cout<<"YES";
  }else{
    cout<<"NO";
  }

  return 0;
}


Measured memory_bytes: 256
N = int(input())
li = [ int(it) for it in input().split() ]


def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
  
lg = [0]*N
lr = [0]*N

lg[0] = li[0]
for i in range(N-1):
  lg[i+1] = gcd(lg[i],li[i+1])
lr[-1] = li[-1]
for i in range(N-1):
  lr[-2-i] = gcd(lr[-1-i],li[-i-2])
#print ( lg , lr ) 

s = 0
for i in range(N):
  if (0<i and i<N-1):
    s = max(s,gcd(lg[i-1],lr[i+1]))
  if (i==0):
    s = max(s,lr[i+1])
  if (i==N-1):
    s = max(s,lg[i-1])
print (s)   
    

  


Measured memory_bytes: 63984
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {

    int n;
    int next[];
    boolean used[];

    public void solve() throws IOException {
        n = nextInt();
        next = new int[n];
        for (int i = 0; i < n; i++) {
            next[i] = nextInt() - 1;
        }
        int cnt = 0;
        used = new boolean[n];
        int k = 0;
        while(k != 1 && !used[k]){
            used[k] = true;
            k = next[k];
            cnt++;
        }
        if(k == 1) out.print(cnt);
        else out.print(-1);

    }


    BufferedReader br;
    StringTokenizer sc;
    PrintWriter out;

    public static void main(String[] args) throws IOException {
        Locale.setDefault(Locale.US);
        new Main().run();
    }

    void run() throws IOException {
        try {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
//            br = new BufferedReader(new FileReader("queue.in"));
//            out = new PrintWriter(new File("queue.out"));
            solve();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

    String nextToken() throws IOException {
        while (sc == null || !sc.hasMoreTokens()) {
            try {
                sc = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                return null;
            }
        }
        return sc.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
}

Measured memory_bytes: 35716
#include<bits/stdc++.h> 
using namespace std; 
typedef  pair<int, int> iPair; 
//#define mod 1000000007
#define pb push_back
typedef long long ll;
typedef long double ld;
#define FOR(i,n) for(i=0;i<n;i++)
#define FORE(i,n) for(i=0;i<=n;i++)
 
 
ll gcd(ll a , ll b)
{
   if(b==0) return a;
   a%=b;
   return gcd(b,a);
   
}
    
ll maxl(ll a,ll b){
    if(a>b)return a;
    return b;
}
 
ll minl(ll a,ll b){
    if(a>b)return b;
    return a;
}
 
ll mod = 998244353;
 
ll mulmod(ll a, ll b,ll c){ 
    ll res = 0; 
    a = a % c; 
    while (b > 0){ 
        if (b % 2 == 1){ 
            res = (res + a) % c;
        }
        a = (a * 2) % c; 
        b /= 2; 
    } 
    return res % c; 
}
 
int binarySearch(int arr[], int l, int r, int x) 
{ 
    if (r >= l) { 
        int mid = l + (r - l) / 2; 
        if (arr[mid] == x) 
            return mid; 
        if (arr[mid] > x) 
            return binarySearch(arr, l, mid - 1, x); 
        return binarySearch(arr, mid + 1, r, x); 
    } 
    return -1; 
} 
 
int a[100005];
int tree[200005];
 
void build(int st,int low,int high){
    if(low==high){
        tree[st] = a[high]%2;
        return;
    }
    int mid = low+(high-low)/2;
    build(2*st,low,mid);
    build(2*st+1,mid+1,high);
    tree[st] = tree[2*st]+tree[2*st+1];
}
 
void update(int st,int start,int end,int ind,int val){
    if(start==end){
        tree[st] = val%2;
        return;
    }
    int mid = start+(end-start)/2;
    if(ind<=mid){
        update(2*st,start,mid,ind,val);
    }
    else update(2*st+1,mid+1,end,ind,val);
    tree[st] = tree[2*st]+tree[2*st+1];
}
 
int query(int st,int start,int end,int low,int high){
    if(start>high || end<low)return 0;
    int mid = start + (end-start)/2;
    if(start==low && end==high){
        return tree[st];
    }
    if(low>mid)return query(2*st+1,mid+1,end,low,high);
    if(high<=mid)return query(2*st,start,mid,low,high);
    return query(2*st,start,mid,low,mid)+query(2*st+1,mid+1,end,mid+1,high);
}

int main()
{
        ios_base::sync_with_stdio(false);
        int n;
        cin >> n;
        multiset<ll> s;
        multiset<ll> S;
        ll m = pow(2,n);
        for(int i=0;i<m;i++){
            int temp;
            cin >> temp;
            s.insert(temp);
        }
        S.insert(*s.rbegin());
        auto it = --s.end();
        s.erase(it);
        while(S.size()!=m){
            vector<ll> t;
            for(auto it=S.begin();it!=S.end();++it){
                auto it1 = s.lower_bound(*it);
                if(it1==s.begin()){
                    cout << "No" << endl;
                    return 0;
                }
                it1--;
                t.pb(*it1);
                s.erase(it1);
            }
            for(int i=0;i<t.size();i++)S.insert(t[i]);
        }
        cout << "Yes" << endl;
        return 0;
}

Measured memory_bytes: 14068
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#define int long long
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
#endif
#define ff first
#define ss second
#define endl "\n"
#define all(c) c.begin(),c.end()
template<typename T>void print(T t){for(auto &it:t)cout<<it<<" "; cout<<endl;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void solve(){
    string s;
    cin>>s;
    puts(s>"2019/04/30"?"TBD":"Heisei");
}
int32_t main(){
  IOS;
  solve();
  //debug();
 #ifdef LOCAL_DEFINE
 cerr<<"time elapsed "<<(double)clock()/CLOCKS_PER_SEC<<endl;
 #endif	
}


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

using namespace std;

typedef long long ll;
int n;
ll arr[200100];
ll psum[200100];

int main() {
	int i;

	scanf("%d",&n);
	for (i=0;i<n;i++) scanf("%lld",&arr[i]);
	psum[0] = arr[0];
	for (i=1;i<n;i++) psum[i] = psum[i-1]+arr[i];
	ll sum = psum[n-1];
	ll mini = 1LL<<60;
	for (i=0;i<n-1;i++) {
		mini = min(mini,abs(psum[i]-(sum-psum[i])));
	}
	printf("%lld\n",mini);

    return 0;
}


Measured memory_bytes: 3328
import math
N=int(input())
if N==2:
  print(1)
  exit()
def yaku(n):
    a=set()
    s=int(math.sqrt(n))
    for i in range(2,s+1):
        if n%i==0:
            a.add(i)
            a.add(n//i)
    return a
ans=len(yaku(N-1))+1
a=yaku(N)
for i in a:
    n=N
    while n%i==0:
        n=n//i
    if n%i==1:
        ans+=1
print(ans+1)

Measured memory_bytes: 3828
#include<iostream>
#include<cstdio> 
#include<algorithm>
using namespace std;
const int N=100005;
int n;
int a[N];
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&a[i]);
	int Min=*min_element(a+1,a+n+1),Max=*max_element(a+1,a+n+1);
	if(Max>=n)
	{
		printf("No");
		return 0;
	}
	if(Max-Min>1)
	{
		printf("No");
		return 0;
	}
	if(Max==Min) 
	{
		if(Min==1||Min+1==n) printf("Yes");
		else if(Min*2>n) printf("No");
		else printf("Yes");
		return 0;
	}
	int cnt=0;
	for(int i=1;i<=n;i++)
		if(a[i]==Min) cnt++;
	n-=cnt;
	Max-=cnt;
	if(Min<cnt) printf("No");
	else if(Max*2>n) printf("No");
	else printf("Yes");
	return 0;
}

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

s = sorted(a,reverse=True)
mod = 10**9 + 7
ans = 1

if k % 2 == 1 and s[0] < 0:
        for i in range(k):
            ans = ans * s[i] % mod
        print(ans)
        exit()

l = 0
r = n - 1
if k % 2 == 1:
  ans = ans * s[l]
  l += 1

for _ in range(k // 2):
  ml = s[l] * s[l + 1]
  mr = s[r] * s[r - 1]
  if ml > mr:
    ans = ans * ml % mod
    l += 2
  else:
    ans = ans * mr % mod
    r -= 2

print(ans)

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

int main(){
    char S[11], T[11], U[11];
    int a, b;
    cin >> S >> T;
    cin >> a >> b;
    cin >> U;
    if (strcmp(S, U) == 0) a--;
    if (strcmp(T, U) == 0) b--;

    cout << a << " " << b << endl;

    return 0;
}

Measured memory_bytes: 256
#include <set>
#include <map>
#include <list>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define inf 1e+9
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin(), v.end()
#define MSG(a) cout << #a << " " << a << endl;
#define REP(i, x, n) for(int i = x; i < n; i++)
template<class T, class C> void chmax(T& a, C b){ a>b?:a=b; }
template<class T, class C> void chmin(T& a, C b){ a<b?:a=b; }

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

    int n,k,ans=0;
	//string s;
	cin >> n >> k;
	//cin >> s;

	if(n+k >= n-k && n+k >= n*k){
		cout << n+k << endl;
	}
	else if(n-k >= n+k && n-k >= n*k){
		cout << n-k << endl;
	}	
	else{
		cout << n*k << endl;
	}

	
}

Measured memory_bytes: 256
#include<iostream>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
string s0;
int ans;
queue<string>que;
stack<string>sta;
int d(string s,int al) {
    if (al == 25) { 
		que.push(s);
		ans++;
        //cout<<"push"<<endl;
		return 0; }
	for (unsigned int i = 0; i <s.size() ;i++) {
        //cout<<s[i]<<"   "<<char('z' - al-1)<<endl;
		if (s[i] == 'z' - al-1) {
			s[i] = 'z' - al ; 
            //cout<<a[k-1]<<endl;
			d(s, al + 1);
            s[i]='z' - al-1;
		}
		if (s[i] == 'z' - al ) return 0;	
	}
	d(s, al + 1);
    return 0;
}
int main() {
	while (1) {
		cin >> s0;
		if (s0 == "#")return 0;
		ans = 0;
        //cout<<s0<<endl;
		d(s0, 0);

		if (ans < 11) {
			string w[10];
			for (int i = 0; i < ans; i++) {
				w[i] = que.front();
				que.pop();
			}
			sort(w, w + ans);
			cout << ans << endl;
			for (int i = 0; i < ans; i++)
				cout << w[i] << endl;
		}
		else {
			string f[5], e[5];
			for (int i = 0; i < 5; i++) {
				f[i] = que.front();
				que.pop();
				e[i] = que.front();
				que.pop();
			}
			while (1) {
				if (que.empty())break;
				for (int i = 0; i < 5; i++) {
					if (f[i] > que.front()) {
						que.push(f[i]);
						f[i] = que.front();
						break;
					}
					if (e[i] < que.front()) {
						que.push(e[i]);
						e[i] = que.front();
						break;
					}
				}
				que.pop();
			}
			sort(f, f + 5);
			sort(e, e + 5);
			cout << ans << endl;
			for (int i = 0; i < 5; i++)
				cout << f[i] << endl;
			for (int i = 0; i < 5; i++)
				cout << e[i]<<endl;
		}
	}
}


Measured memory_bytes: 4448
import sys
input = sys.stdin.readline

def main():
    x = int(input())
    p = [0, 1]
    i = 2
    while p[-1] <= x*x:
        p.append(pow(i, 5))
        i += 1

    p_ = set(p)
    for z in p:
        if z - x in p_:
            print(int(pow(z, 1/5)), int(pow(z-x, 1/5)))
            return

        if x - z in p_:
            print(int(pow(abs(x-z), 1/5)), int(-pow(z, 1/5)))
            return


main()


Measured memory_bytes: 9576
#include<bits/stdc++.h>
using namespace std;
//当学生i进入的时候有A[i]个 
const int N=1E5+7;
struct stu {
	int a,b;
	bool friend operator<(const stu &x,const stu &y){
		return x.a<y.a;
	}
}arr[N];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&arr[i].a);
		arr[i].b=i;
	}
	sort(arr+1,arr+1+n);
	for(int i=1;i<=n;i++)	cout<<arr[i].b<<" " ;
	return 0;
} 

Measured memory_bytes: 1536
n, k = [int(e) for e in input().split()]
h = [int(e) for e in input().split()]

import numpy as np

h = np.array(h)
dp = np.zeros(n)

dp[0] = 0
dp[1] = abs(h[1]-h[0])

for i in range(2,n):
    l =i-k if i-k >= 0 else 0
    dp[i] = np.min(dp[l:i]+np.abs(h[i]-h[l:i]))


print(int(dp[-1]))

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

main(){
    while(1){
        int n;cin>>n;
        if(!n)exit(0);
        vector<set<int>> v;
        rep(i,n){
            int m;cin>>m;
            v.push_back(set<int>());
            rep(_,m){
                int x;cin>>x;
                v.back().insert(x);
            }
        }
        int k;cin>>k;
        set<int> s;
        rep(i,k){
            int x;cin>>x;
            s.insert(x);
        }
        bool flag=false;int pre;
        rep(i,n){
            bool f=true;
            for(auto e:s){
                f&=(v[i].count(e)>0);
            }
            if(f){
                if(flag){
                    cout<<-1<<endl;
                    goto end;
                }
                else{
                    flag = true;
                    pre = i+1;
                }
            }
        }
        if(flag){
            cout<<pre<<endl;
        }
        else cout<<-1<<endl;
        end:;
    }
}


Measured memory_bytes: 3452
#include <stdio.h>
#include <limits.h>
void swap(int *a , int *b){
    int t = *a;
    *a = *b;
    *b = t;
}
int INF = INT_MAX / 10;

int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
int lcm(int m, int n ){if((0 == m )||( 0 == n ))return 0;
    return ((m / gcd(m, n)) * n);
}

int main(void){
    int N,M,i,x,tmp,r,TLCM,j,k,dif = 0,a,Ntemp,Mtemp;
    int l=0;
    int difsum=0;
    int str[1000];
    int max=0,min=100;
    
    scanf("%d %d",&N,&M);
    
    for(i=0; i<N; i++){
        scanf("%d", &str[i]);
    }
    
    int tlcm = lcm(N,M);
    int gNum =  tlcm / M;
    
    for(k=0; k<gNum; k++){
    
        for(j=0; j<M; j++){
    
            if(str[l]>=max){
                max=str[l];
            }
    
            if(str[l]<=min){
                min=str[l];
            }
    
    
            l++;
            if(l==N){
                l=0;
            }
        }
        difsum += max - min;
        max=-INF;
        min=INF;
    }
    
    
    printf("%d\n",difsum);
    
    return 0;
}



Measured memory_bytes: 2680
#!/usr/bin/env python3
N, Y = map(int, input().split())
for i in range(0, N + 1):
    x = 4/5*i + Y/5000 - N
    y = -9/5*i - Y/5000 + 2*N
    z = i
    if (x.is_integer() & y.is_integer()):
        # print(0 <= x <= N, 0 <= y <= N)
        # print(int(x), int(y), z)
        if ((0 <= x <= N) & (0 <= y <= N)):
            print(int(x), int(y), z)
            break
else:
    print("-1 -1 -1")

Measured memory_bytes: 3064
#include "bits/stdc++.h"
#define _overload3(_1,_2,_3,name,...) name
#define _rep(i,n) repi(i,0,n)
#define repi(i,a,b) for(int i=int(a),i##_len=(b);i<i##_len;++i)
#define MSVC_UNKO(x) x
#define rep(...) MSVC_UNKO(_overload3(__VA_ARGS__,repi,_rep,_rep)(__VA_ARGS__))
#define all(c) c.begin(),c.end()
#define mp make_pair
#define write(x) cout<<(x)<<"\n"
using namespace std; typedef long long ll;
typedef vector<int> vi; typedef vector<ll> vll; template<class T>using vv = vector<vector<T>>;
template<class T>vv<T> vvec(size_t n, size_t m, T v) { return vv<T>(n, vector<T>(m, v)); }
template<class T>bool chmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template<class T>bool chmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
constexpr int INF = 1 << 28, MOD = 1e9 + 7; constexpr ll LINF = 1ll << 60;
struct aaa { aaa() { cin.tie(0); ios::sync_with_stdio(0); }; }aaaa;

int main() {
    ll N, X;
    cin >> N >> X;
    vll B(N), L(N), U(N);
    rep(i, N) {
        cin >> B[i] >> L[i] >> U[i];
    }

    ll D0 = 0;
    vector<pair<ll, int>> Dmax(N);
    rep(i, N) {
        D0 += -B[i] * L[i];
        Dmax[i] = mp(B[i] * L[i] + (X - B[i]) * U[i], i);
    }
    sort(all(Dmax));
    reverse(all(Dmax));

    vll Dint(N);
    rep(i, N - 1) Dint[i + 1] = Dmax[i].first + Dint[i];

    ll ng = -1;
    ll ok = X * N;
    while (ok - ng > 1) {
        ll mid = ng + (ok - ng) / 2;

        int n_full = mid / X;
        ll rest = mid - n_full * X;

        bool canWin = false;
        rep(i, N) {
            ll D = D0 + Dint[n_full];
            if (i < n_full) {
                D += Dmax[n_full].first - Dmax[i].first;
            }

            int i_orig = Dmax[i].second;
            if (rest > B[i_orig]) {
                D += B[i_orig] * L[i_orig] + (rest - B[i_orig]) * U[i_orig];
            }
            else {
                D += rest * L[i_orig];
            }

            if (D >= 0) {
                canWin = true;
                break;
            }
        }

        if (canWin) ok = mid;
        else ng = mid;
    }

    write(ok);
}

Measured memory_bytes: 4992
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            StringBuilder sb = new StringBuilder();

            string input;

            while (!string.IsNullOrEmpty(input = Console.ReadLine()))
            {
                double[] memo = new double[10];
                memo[0] = double.Parse(input);

                for (int i = 1; i < 10; i++)
                {
                    if (i % 2 == 1) memo[i] = memo[i - 1] * 2;
                    else memo[i] = memo[i - 1] / 3;
                }
                double sum = memo.Sum();
                sb.AppendLine(sum.ToString());
            }
            Console.Write(sb);
        }
    }
}

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

#define rep(i, n) for(int i = 0; i < (n); i++)
#define repp(i, l, r) for(int i = (l); i < (r); i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
#define perr(i, l, r) for(int i = ((r)-1); i >= (l); i--)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007
#define IINF 1000000000
#define LINF 1000000000000000000
#define SP <<" "<<
#define CYES cout<<"Yes"<<endl
#define CNO cout<<"No"<<endl
#define CFS cin.tie(0);ios::sync_with_stdio(false)

typedef long long LL;
typedef long double LD;

struct SegmentTree {
private:
  int n;
  vector<pair<LL,LL>> node;
  vector<LL> pos;

public:
  SegmentTree(int sz, vector<LL> v) {
    n = 1; while(n < sz) n *= 2;
    node.resize(2*n-1, {0,0});
    pos = v;
  }

  LL get(int x) {
    LL ans=0;
    int p = x;
    x += (n - 1);
    ans += node[x].first*pos[p]+node[x].second;
    while(x > 0) {
      x = (x - 1) / 2;
      ans += node[x].first*pos[p]+node[x].second;
    }
    return ans;
  }

  void add(int a, int b, int x, int y, int k=0, int l=0, int r=-1) {
    if(r < 0) r = n;
    if(r <= a || b <= l) return;
    if(a <= l && r <= b){
      node[k].first += x;
      node[k].second += y;
      return;
    }
    add(a, b, x, y, 2*k+1, l, (l+r)/2);
    add(a, b, x, y, 2*k+2, (l+r)/2, r);
  }
};

struct SegmentTree2 {
private:
  int n;
  vector<int> node;

public:
  SegmentTree2(int sz) {
    n = 1; while(n < sz) n *= 2;
    node.resize(2*n-1, 0);
  }

  int get(int x) {
    int ans=0;
    x += (n - 1);
    ans += node[x];
    while(x > 0) {
      x = (x - 1) / 2;
      ans += node[x];
    }
    return ans;
  }

  void add(int a, int b, int k=0, int l=0, int r=-1) {
    if(r < 0) r = n;
    if(r <= a || b <= l) return;
    if(a <= l && r <= b){
      node[k]++;
      return;
    }
    add(a, b, 2*k+1, l, (l+r)/2);
    add(a, b, 2*k+2, (l+r)/2, r);
  }
};

struct query{
  int c;
  int a;
  int b;
};

int main(){
  int q;
  cin >> q;
  vector<query> qq(q);
  map<LL,int> mp;
  rep(t,q){
    cin >> qq[t].c;
    if(qq[t].c==1){
      cin >> qq[t].a >> qq[t].b;
      mp[qq[t].a]=-1;
    }
  }
  int sz = mp.size();
  int idx=0;
  vector<LL> v(sz);
  for(auto &p:mp){
    v[idx]=p.first;
    p.second=(idx++);
  }
  SegmentTree seg(sz, v);
  SegmentTree2 sv(sz);
  LL tl=0;
  LL c,a,b;
  int ttt=0;
  rep(t,q){
    if(qq[t].c==1){
      a=qq[t].a;
      b=qq[t].b;
      tl+=b;
      idx = mp[a];
      seg.add(0,idx,-1,a);
      seg.add(idx,sz,1,-a);
      sv.add(idx,sz);
      ttt++;
    }else{
      int l=-1,r=sz-1,mid;
      while(r-l>1){
        mid=(l+r)/2;
        if(sv.get(mid)<(ttt+1)/2){
          l=mid;
        }else{
          r=mid;
        }
      }
      cout << v[r] SP seg.get(r)+tl << endl;
    }
  }
  return 0;
}


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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m = M) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

int exp(int n, int k) {
  if (k == 0) return 1;
  if (k == 1) return n;
  int ax = exp(n, k / 2);
  ax = mod(ax * ax);
  if (k % 2) ax = mod(ax * n);
  return ax;
}

int gcd(int a, int b) {
  if (a == 0)
    return b;
  else
    return gcd(b % a, a);
}
//#define MULTIPLE_TEST_CASE
void solution() {
  int n;
  cin >> n;
  int sum = 0;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    ans = mod(ans + mod(sum * x));
    sum = mod(sum + x);
  }
  cout << ans << endl;
}

int32_t main() {
  DESYNC;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int t = 1;
#ifdef MULTIPLE_TEST_CASE
  cin >> t;
#endif
  while (t--) solution();
}


Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int max_n=200005;
typedef pair<int,int> P;
#define fi first
#define se second
const ll inf=0x3f3f3f3f3f3f3f3f;
int n;
P p[max_n];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d%d",&p[i].fi,&p[i].se);
        if(p[i].fi>p[i].se)swap(p[i].fi,p[i].se);
    }
    sort(p+1,p+n+1);
    ll ans=inf;
    ll mx1=inf,mx2=-inf,mx3=inf,mx4=-inf;
    for(int i=1;i<=n;i++){
        mx1=min(mx1,p[i].fi*1ll),mx2=max(mx2,p[i].fi*1ll);
        mx3=min(mx3,p[i].se*1ll),mx4=max(mx4,p[i].se*1ll);
    }
    ans=min(ans,(mx4-mx3)*(mx2-mx1));
    multiset<int> s;
    for(int i=1;i<=n;i++)s.insert(p[i].fi);
    for(int i=1;i<=n;i++){
        int x=*s.begin(),y=*s.rbegin();
        ans=min(ans,(y-x)*(mx4-mx1));
        s.erase(s.find(p[i].fi));
        s.insert(p[i].se);
    }
    int x=*s.begin(),y=*s.rbegin();
    ans=min(ans,(y-x)*(mx4-mx1));
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 11136
#include<iostream>
#include<iomanip>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<string>
#include<algorithm>
#include<functional>
#include<math.h>
#include<unordered_set>
using namespace std;
 
int main() {
	unsigned long long X, Y;
	int cnt = 0;
 
	cin >> X >> Y;
	while (X <= Y) {
		X *= 2;
		cnt++;
	}
 
	cout << cnt << endl;
 
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define mx 1000000007
#define FF first.first
#define FS first.second
#define S second
typedef pair<int,int> P;
typedef pair<P,int> PP;
int main()
{
	int n,m,s;
	int a,b,c;
	int i,j;
	
	PP p[2000];
	
	cin>>n>>m>>s;
	int d[n];
	
	for(i=0;i<m;i++){
		cin>>a>>b>>c;
		p[i]=PP(P(a,b),c);	
	}
	
	for(i=0;i<n;i++) d[i]=mx;
	
	d[s]=0;
	
	int cnt=0,flg1=0;
	
	while(true){
		bool flg=false;
		for(i=0;i<m;i++){
			PP x=p[i];
			if(d[x.FF]!=mx && d[x.FS]>d[x.FF]+x.S){
				d[x.FS]=d[x.FF]+x.S;
				flg=true;
			}
		}
		if(!flg) break;
		if(cnt==n-1){
			flg1=1;
			break;
		}
		cnt++;
	}
	
	if(flg1==1) cout<<"NEGATIVE CYCLE"<<endl;

	else{
		for(i=0;i<n;i++){
			if(d[i]==mx) cout<<"INF"<<endl;
			else cout<<d[i]<<endl;
		}
	}	
	
	return 0;
}	


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
#define INF 1<<30
#define endl '\n'
#define maxn 100005
#define tc printf("Case %d: ", cs)
#define tcn printf("Case %d:\n", cs);
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
typedef long long ll;
const double PI = acos(-1.0);
#define dbg(x) cerr << #x << " = " << x << endl;
#define dbg2(x, y) cerr << #x << " = " << x << ", " << #y << " = " << y << endl;
#define dbg3(x, y, z) cerr << #x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;
#define dbg4(w,x, y, z) cerr << #w << " = " << w << ", " <<#x << " = " << x << ", " << #y << " = " << y << ", " << #z << " = " << z << endl;


int main()
{
    FASTIO
    /*
    //double start_time = clock();
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
    freopen("error.txt", "w", stderr);
#endif
//*/
    int T;
    //cin >> T;
    T = 1;
    for (int cs = 1; cs <= T; cs++) {
        string s;
        cin >> s;
        int n = s.length();
        for (int i = 0; i < n - 1; i++) {
            if (s[i] == s[i + 1]) {
                cout << i + 1 << " " << i + 2 << endl;
                return 0;
            }
            else if (i < n - 2 && s[i] == s[i + 2]) {
                cout << i + 1 << " " << i + 3 << endl;
                return 0;
            }
        }
        cout << "-1 -1\n";
    }

    //double end_time = clock();
    //printf( "Time = %lf ms\n", ( (end_time - start_time) / CLOCKS_PER_SEC)*1000);
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
    
#define int long long
    
#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,m,n) for(int i=m;i<n;i++)
#define FORR(i,m,n) for(int i=m;i>=n;i--)
#define pb(x) push_back(x) 
#define SORT(x) sort((x).begin(),(x).end())
#define INF 99999999999
    
using namespace std;
    
int dy[4]={1, -1, 0, 0};
int dx[4]={0, 0, 1, -1};

char march[]={'M', 'A', 'R', 'C', 'H'};

bool check(char ch){
    REP(i, 5){
        if(ch==march[i]) return true;
    }
    return false;
}

int32_t main(){
    int n;
    cin >> n;
    string s[n];
    map<char, int> m;
    REP(i, 5) m[march[i]]=0;
    REP(i, n){
        cin >> s[i];
        if(check(s[i][0])){
            m[s[i][0]]++;
        }
    }

    int ans=0;
    REP(i, 32){
        int cnt=0, res=1;
        REP(j, 5){
            if(i & (1 << j)){
                cnt++;
                res*=m[march[j]];
            }
        }
        
        if(cnt==3){
            ans+=res;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 6144
//AGC Backfront
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> vec(N);
  for(int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  vector<int> pos(N);
  for(int i=0; i<N; i++){
    int x = vec.at(i);
    pos.at(x-1) = i;
  }
  int ans = 0;
  int j = 0;
  int j_pos = -1;
  int cnt = 0;
  while(j < N){
    if(j_pos == -1){
      j_pos = pos.at(j);
      j++;
      cnt++;
      continue;
    }
    else{
      if(pos.at(j) > j_pos){
        j_pos = pos.at(j);
        j++;
        cnt++;
        continue;
      }
      else{
        ans = max(ans,cnt);
        cnt = 0;
        j_pos = -1;
        continue;
      }
    }
  }
  ans = max(ans,cnt);
  cout << N - ans << endl;
}

Measured memory_bytes: 1792