akhauriyash/Code-Regression huggingface dataset:
import sys
input = sys.stdin.readline


class SegmentTree0():
    """
    0-indexed Segment Tree
    """
    def __init__(self, n_, ele_id, op_func):
        self.n = 1 << (n_ - 1).bit_length()  # size
        self.data = [ele_id] * (2 * self.n - 1)  # binary tree (0-indexed)
        self.ele_id = ele_id  # identity element
        self.op_func = op_func  # binary operation of monoid

    def __getitem__(self, i):
        return self.data[i + self.n - 1]

    def build(self, data_init):
        for i in range(len(data_init)):
            self.data[i + self.n - 1] = data_init[i]  # set data in leaf
        for i in range(self.n - 2, -1, -1):
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

    def update(self, i, x):
        # change i-th element to x (i : 0-indexed)
        i += self.n - 1
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2  # go to parenet-node
            self.data[i] = self.op_func(self.data[2 * i + 1],
                                        self.data[2 * i + 2])

    def query(self, a, b):
        # query for interval [a, b) (a, b : 0-indexed)
        return self.query_(a, b, 0, 0, self.n)

    def query_(self, a, b, k, l, r):
        if r <= a or b <= l:
            # [a, b) and [l, r) have no intersection
            return self.ele_id
        if a <= l and r <= b:
            # [a, b) includes [l, r)
            return self.data[k]
        else:
            # [a, b) and [l, r) have some overlap
            child_l = self.query_(a, b, 2 * k + 1, l, (l + r) // 2)
            child_r = self.query_(a, b, 2 * k + 2, (l + r) // 2, r)
            return self.op_func(child_l, child_r)


n, q = map(int, input().split())
ele_id = 0
op_func = lambda a, b: a + b
st_rsq = SegmentTree0(n, ele_id, op_func)
for _ in range(q):
    com, x, y = map(int, input().split())
    if com == 0:
        x -= 1
        st_rsq.update(x, st_rsq[x] + y)
    elif com == 1:
        x -= 1
        y -= 1
        ans = st_rsq.query(x, y + 1)
        print(ans)



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


int main() {
  long d;
  cin>>d;
  vector<long>c(26);
  rep(i,26){
    cin>>c.at(i);
  }
  vector<vector<long>>s(d,vector<long>(26));
  rep(i,d){
    rep(j,26){
      cin>>s[i][j];
    }
  }
  rep(i,d){
    long ans=0;
    rep(j,26){
      if(s[i][ans]<=s[i][j]){
        ans=j;
      }
    }
    cout<<ans+1<<endl;
  }
  
}




Measured memory_bytes: 3720
#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,n) for(int i = 0; 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 show(x) cout<<#x<<" = "<<x<<endl;
#define PQ(T) priority_queue<T,v(T),greater<T> >
#define bn(x) ((1<<x)-1)
#define dup(x,y) (((x)+(y)-1)/(y))
#define newline puts("")
#define v(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
typedef long long int ll;
typedef unsigned uint;
typedef unsigned long long ull;
typedef pair<int,int> P;
typedef set<int> S;
typedef queue<int> Q;
typedef queue<P> QP;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<P> vp;
inline int in() { int x; scanf("%d",&x); return x;}
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
const int MOD = 1000000007;
#define dame { puts("-1"); return 0;}
#define yn {puts("YES");}else{puts("NO");}

class Combi {
private:
  v(ll) fac, inv, finv;
  void init(ll N) {
    fac[0] = fac[1] = 1; inv[1] = 1; finv[0] = finv[1] = 1;
    for (ll i = 2; i < N; i++) {
      fac[i] = fac[i - 1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
      finv[i] = finv[i - 1] * inv[i] % MOD;
    }
  }
public:
  Combi(int N) : fac(N + 1), inv(N + 1), finv(N + 1) { init(N + 1); }
  ll Cmod(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
  }
  ll Pmod(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * finv[n - k] % MOD;
  }
};
  
int main() {
  ll N,M,K;
  cin >> N >> M >> K;
  Combi C = Combi(N*M);
  ll ans = 0;
  srep(w,1,M) {
    ans += (ll)(M-w) * N * N * (ll)w;
    ans %= MOD;
  }
  srep(h,1,N) {
    ans += (ll)(N-h) * M * M  * (ll)h;
    ans %= MOD;
  }
  cout << ans*C.Cmod(N*M-2,K-2) % MOD << endl;
  return 0;
}

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

int main(){
    ll x, ans, num;
    cin >> x;
    ans = 0;
    num = 100;
    while(num < x){
        num = num * 1.01;
        ans ++;
    }
    cout << ans <<endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <utility>
#include <vector>
#include <cmath>
#include <map>

using namespace std;

int n, m;

map<int, vector<pair<int, int>>> uvw;
int col[100000];

void color(int i, int c)
{
    if (col[i] != -1) return;

    col[i] = c;

    for (auto vw : uvw[i])
    {
        color(vw.first, c ^ vw.second);
    }
}

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

    cin >> n >> m;

    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        uvw[u - 1].insert(uvw[u - 1].end(), make_pair(v - 1, w % 2));
        uvw[v - 1].insert(uvw[v - 1].end(), make_pair(u - 1, w % 2));
    }

    for (int i = 0; i < n; i++)
    {
        col[i] = -1;
    }
    
    int ans = 0;
    for (size_t i = 0; i < n; i++)
    {
        if (col[i] == -1) {
            color(i, 0);
            ans++;
        }
    }
    
    cout << ans << "\n";
    
    return 0;
}

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

using namespace std;
#define rep(i,n) for(int i=0;i<(n);i++)

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

#define MAX 100005
#define INF 1001001001

int main(int, char**)
{
  int n;
  cin >> n;
  vector<P> a(n);
  rep(i,n) cin >> a[i].first >> a[i].second;

  sort(a.begin(), a.end());
  for (auto e : a) cout << e.first << " " << e.second << endl;

  return 0;
}



Measured memory_bytes: 3616
# 凸包 Monotone Chain O(nlogn)
def det(p, q):
    return p[0]*q[1] - p[1]*q[0]
def sub(p, q):
    return (p[0]-q[0], p[1]-q[1])
def get_convex_hull(points):
    n = len(points)
    points.sort()
    size_convex_hull = 0
    ch = []
    for i in range(n):
        while size_convex_hull > 1:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    t = size_convex_hull
    for i in range(n-2, -1, -1):
        while size_convex_hull > t:
            v_cur = sub(ch[-1], ch[-2])
            v_new = sub(points[i], ch[-2])
            if det(v_cur, v_new) > 0:
                break
            size_convex_hull -= 1
            ch.pop()
        ch.append(points[i])
        size_convex_hull += 1

    return ch[:-1]

N = int(input())
XY = [list(map(int, input().split())) for _ in range(N)]
ps = [(0, 0)]
for x, y in XY:
    ps_new = ps[:]
    for x_, y_ in ps:
        ps_new.append((x+x_, y+y_))
    ps = get_convex_hull(ps_new)
ans = 0
for x, y in ps:
    ans = max(ans, x*x+y*y)
print(ans ** 0.5)


Measured memory_bytes: 43376
#include <bits/stdc++.h>
#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define dump(x) cout << #x << " = " << (x) << endl;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;

signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int X, A;
  cin >> X >> A;
  if(X < A) {
    cout << 0 << endl;
  } else {
    cout << 10 << endl;
  }
  return 0;
}

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

using namespace std;

inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}
template<class T> inline T sqr(T x) {return x*x;}

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<int, int> pii;
typedef long long ll;

#define all(a)  (a).begin(),(a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define pb push_back
#define mp make_pair
#define each(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)
#define exist(s,e) ((s).find(e)!=(s).end())
#define range(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  range(i,0,n)
#define clr(a,b) memset((a), (b) ,sizeof(a))
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

const double eps = 1e-10;
const double pi  = acos(-1.0);
const ll INF =1LL << 62;
const int inf =1 << 29;

int nexts[10010];

int main(void){
	int n,k,m;
	while(cin >> n >> k >> m){
		if(n==0)
			break;
		int size=n;
		for(int i=1;i<n;++i) nexts[i]=i+1;
		nexts[n]=1;
		int cur=m;
		int prev=(m==1)?n:m-1;
		while(size!=1){
			nexts[prev]=nexts[cur];
			cur=nexts[prev];
			size--;
			int num=(k-1)%size;
			while(num--){
				prev=cur;
				cur=nexts[cur];
			}
		}
		cout << cur << endl;
	}
	return 0;
}

Measured memory_bytes: 1200
from collections import Counter

n = int(input())
ls = list(map(int, input().split()))

ac = Counter(ls[::2]).most_common(2)
bd = Counter(ls[1::2]).most_common(2)

if ac[0][0] != bd[0][0]:
    print(n-ac[0][1]-bd[0][1])
else:
    if len(ac) == 1 or len(bd) == 1:
        print(n//2)
    else:
        print(n-max(ac[0][1] + bd[1][1], ac[1][1] + bd[0][1]))

Measured memory_bytes: 15588
#include <bits/stdc++.h>
#define MAXN 100100
#define pii  pair<int, int>
#define pll  pair<long long, long long>
#define ss second
#define ff first
 
using ll = long long;
using namespace std;
const int mod = 1e9 + 7;

int main(){
    int x, y, a, b;
    cin >> x >> y >> a >> b;
    x = abs(a - x);
    y = abs(b - y);
    string ans;
    ans.append(x, 'R');
    ans.append(y, 'U');
    ans.append(x, 'L');
    ans.append(y, 'D');
    ans.append(1, 'D');
    ans.append(x + 1, 'R');
    ans.append(y+1, 'U');
    ans.append(1, 'L');
    ans.append(1, 'U');
    ans.append(x + 1, 'L');
    ans.append(y + 1, 'D');
    ans.append(1, 'R');

    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1000000007;
#define INF 1LL<<30
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()

vector<vector<int>> G;

int main(){
    int n;
    cin>>n;
    G.resize(n);

    int a[n-1],b[n-1];
    rep(i,n-1){
        cin>>a[i]>>b[i];
        a[i]--,b[i]--;
        G[a[i]].push_back(b[i]);
        G[b[i]].push_back(a[i]);
    }
    vector<int> c(n);
    rep(i,n) cin>>c[i];
    sort(all(c));
    reverse(all(c));
    ll ans=0;
    for(int i=1;i<n;i++) ans+=c[i];

    queue<int> que;
    vector<int> d(n,-1);
    ll seek=0;
    que.push(0);
    while(!que.empty()){
        int v=que.front();
        que.pop();
        d[v]=c[seek];
        seek++;
        for(int nv : G[v]){
            if(d[nv]!=-1) continue;
            que.push(nv);
        }
    }

    cout<<ans<<endl;
    rep(i,n) cout<<d[i]<<" ";
    cout<<endl;
}


 

Measured memory_bytes: 1152
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <queue>
using namespace std;
typedef long long int ll;
typedef long double ld;
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; }
const long long INF = 1LL << 60;
typedef pair<ll,ll> pairs;
vector<pairs> p;
bool pairCompare(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.first < secondElof.first;
}
bool pairCompareSecond(const pair<double,ll>& firstElof, const pair<double,ll>& secondElof){
    return firstElof.second < secondElof.second;
}
#define MAX_N 100100
#define MOD 1000000007
bool x[MAX_N];
ll num[MAX_N];
ll fibl[MAX_N]={0};
// 四方向への移動ベクトル
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

ll fib(ll a){
    if (fibl[a]!=0)return fibl[a];
    if (a==0){
        return 0;
    }else if (a==1){
        return 1;
    }
    return fibl[a]=fib(a-1)+fib(a-2);
}
 
ll eratosthenes(ll n) {
    int p = 0;
    for (ll i=0; i<=n; ++i) x[i] = true;
    x[0] = x[1] = false;
    for(int i=2; i<=n; ++i) {
        if(x[i]) {
            p++;
            for(int j=2*i; j<=n; j+=i) x[j] = false;
        }
        
        num[i] = p;
    }
    return p;
}
 
ll gcd(ll a,ll b){
    if (a%b==0)return(b);
    else return(gcd(b,a%b));
}
 
ll keta(ll N){
    int tmp{};
    while( N > 0 ){
        tmp += ( N % 10 );
        N /= 10;
    }
    N = tmp;
    return N;
}

void  base_num(ll data,ll base){
    if(data==0) return;
    ll next=abs(data)%abs(base);
    if(data<0) next=(abs(base)-next)%abs(base);
    base_num((data-next)/base,base);
    cout << next;
}



int main(){
    ll n,k,ans=INF;
    cin >> n >> k;
    ll x[n];
    for (ll i=0;i<n;i++){
        cin >> x[i];
    }
    vector<ll> p,m;
    for (ll i=0;i<n;i++){
        if (x[i]>=0){
            if (i>0){
                for (ll j=i-1;j>=0;j--){
                    m.push_back(abs(x[j]));
                }
            }
            for (ll j=i;j<n;j++){
                p.push_back(abs(x[j]));
            }
            break;
        }
    }
    if (x[n-1]<0){
        for (ll j=n-1;j>=0;j--){
            m.push_back(abs(x[j]));
        }
    }
    p.push_back(INF);
    m.push_back(INF);
    for (ll i=0;i<p.size();i++){
        ll c=0;
        c=p[i]*2;
        if (k==i+1){
            ans=min(ans,c/2);
            break;
        }else if (m.size()-1>=k-i-1 and k-i-2>0){
            c+=m[k-i-2];
            ans=min(ans,c);
        }
    }
    for (ll i=0;i<m.size();i++){
        ll c=0;
        c=m[i]*2;
        if (k==i+1){
            ans=min(ans,c/2);
            break;
        }else if (p.size()-1>=k-i-1 and k-i-2>=0){
            c+=p[k-i-2];
            ans=min(ans,c);
        }
    }
    if (k==1){
        cout << min(p[0],m[0]) << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}




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

using namespace std;
using ll = long long;

template <typename K,typename V>
using umap = unordered_map<K,V>;
template <typename V>
using uset = unordered_set<V>;
#define REP(i,n) for(int i=0;i<n;i++)
#define REPD(i,n) for(int i=n-1;i>=0;i--)
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define ALL(v) v.begin(),v.end()

#define INF 1'000'000'000'000 //10^12
#define MOD 1'000'000'007

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(15);
  
  ll n;
  cin >> n;
  int digit;
  string s = "";
  while ( n > 0){
    digit = n%26;
    if(digit == 0){
      s.insert(s.begin(),'z');
      n = (n-26)/26;
    }else{
      s.insert(s.begin(),(char)('a'+digit-1));
      n = (n-digit)/26;
    }
  }
  cout << s << endl;
  return 0;
}

Measured memory_bytes: 3620
# coding: utf-8
# Your code here!
import fractions

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

N = int(input())
arr = list(map(int, input().split()))
LCM = arr[0]
ctr = 0

for i in range(1, N):
    LCM = lcm(LCM, arr[i])

for j in range(N):
    ctr += (LCM - 1) % arr[j]

print(ctr)

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

#define FOR(i, a, b) for(long long int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;



int main(void) {
	int n;
	int mid;
	int left, right;
	
	cin >> n;
	mid = n / 2;
	vector<int>x(n);
	vector<int>y(n);
	FOR(i, 0, n - 1) {
		cin >> x[i];
		y[i] = x[i];
	}
	sort(x.begin(), x.end());
	right = x[mid];
	left = x[mid - 1];
	FOR(i, 0, n-1) {
		if (y[i] < right) {
			cout << right << endl;
		}
		else {
			cout << left << endl;
		}
	}
	
	return 0;
}


Measured memory_bytes: 3712
#include <bits/stdc++.h>
using namespace std;
#define inf 999999999
#define loop(i, a, b) for (int i = (a), i##len = (b); i < i##len; ++i)
#define rep(i, n) loop(i, 0, n)
#define lin long long

lin a, b, c, k;

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

    lin res;
    if(k % 2 == 0)
        res = a - b;
    else
        res = b - a;

    cout << res << endl;
    
    return 0;
}


Measured memory_bytes: 764
#include <bits/stdc++.h>
using namespace std;
#define LL long int
#define MOD (LL)pow(10,9) + 7

int main(){
    int a[3][3];
    for(int i = 0; i < 3; ++i){
        for(int j = 0; j < 3; ++j)cin >> a[i][j];
    }

    int n;
    cin >> n;
    bool f[3][3] = {};

    for(int i = 0; i < n; ++i){
        int b;
        cin >> b;
        bool ch = false;
        for(int j = 0; j < 3; ++j){
            for(int k = 0; k < 3; ++k){
                if(a[j][k] == b){cerr << "a" << endl;
                    f[j][k] = true;
                    ch = true;
                    break;
                }
            }
            if(ch)break;
        }
    }
    int w = 0;

    for(int i = 0; i < 3; ++i){
        if(f[i][0])w++;
    }
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }
    w = 0;
    for(int i = 0; i < 3; ++i){
        if(f[i][1])w++;
    }
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }
    w = 0;
    for(int i = 0; i < 3; ++i){
        if(f[i][2])w++;
    }
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }
    w = 0;
    for(int i = 0; i < 3; ++i){
        if(f[0][i])w++;
    }
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }
    w = 0;
    for(int i = 0; i < 3; ++i){
        if(f[1][i])w++;
    }
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }
    w = 0;
    for(int i = 0; i < 3; ++i){
        if(f[2][i])w++;
    }
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }
    w = 0;
    for(int i = 0; i < 3; ++i){
        if(f[i][i])w++;
    }
    cerr << w << endl;
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }
    w = 0;
    for(int i = 0; i < 3; ++i){
        if(f[i][2 - i])w++;
    }
    if(w == 3){
        cout << "Yes" << endl;
        return 0;
    }

    cout << "No" << endl;


    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
#define swap(type ,a ,b) {type t; t=a; a=b; b=t;}

int main(){
    int i,n,tmp,a;
    double res;
    res = 0;
    cin >> n;
    for(i=0;i<n;i++){
        cin >> tmp;
        res += 1./(double)tmp;
    }
    cout << 1./res << endl;
}

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

int main() {
	char a[3][3];
	for (int i = 0;i < 3;i++) {
		for (int j = 0;j < 3;j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 0;i < 3;i++) {
		cout << a[i][i];
	}
	cout << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define N ((1<<17)+3)
#define LL long long
using namespace std;
vector<int> son[N];
vector<pair<LL,LL> > dp[N];
LL mid,dis[N];
vector<pair<LL,LL> > temp;
bool DFS(int u,int fr){
    dp[u].clear();
    for(int i:son[u]) 
        if(!DFS(i,u))
            return false;
    if(son[u].size()==0){
        dp[u].push_back(make_pair(0,0));
    }else{
        temp.clear();
        int l=son[u][0],r=son[u][1];LL limit=mid-dis[l]-dis[r];
        if(dp[l].size()>dp[r].size()) swap(l,r);
        for(int i=0,p=0;i<dp[l].size()&&p<dp[r].size();i++){
            while(p+1<dp[r].size() && dp[l][i].second+dp[r][p+1].first <= limit) p++;
            if(dp[l][i].second+dp[r][p].first <= limit) 
                temp.push_back(make_pair( dp[l][i].first+dis[l],dp[r][p].second+dis[r] ));
        }
        for(int i=temp.size()-1;i>=0;i--) 
            temp.push_back(make_pair(temp[i].second,temp[i].first));
        sort(temp.begin(),temp.end());
        for(pair<LL,LL> x:temp){
            if(dp[u].size()==0|| x.second < dp[u][dp[u].size()-1].second )
                dp[u].push_back(x);
        }
    }
    return dp[u].size()!=0;
}

int n,fa[N];

int main(){
    scanf("%d",&n);
    for(int i=2;i<=n;i++) scanf("%d%lld",&fa[i],&dis[i]),son[fa[i]].push_back(i);
    LL l=-1,r=1e12;//(]
    while(l+1<r){
        mid=(l+r)>>1;
        if(!DFS(1,0)) l=mid;
        else r=mid;
    }
    cout<<r<<endl;
    return 0;
}

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

using namespace std;

#define SZ(x) (int)(x.size())

using ll = long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1ll<<50;

template<typename T>
void printv(const vector<T>& s) {
  for(int i=0;i<(int)(s.size());++i) {
    cout << s[i];
    if(i == (int)(s.size())-1) cout << endl;
    else cout << " ";
  }
}


int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int k, x; cin >> k >> x;
  for(int i=-1000000;i<=1000000;++i) {
    if(abs(x-i) < k) {
      cout << i << " ";
    }
  }
  cout << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b,c,d,e,f,g,h,i,j;
    cin>>a;
    int ar[a];
    map<int,int>m;
    map<int,int>::iterator it;
    for(i=0; i<a; i++)
    {
        cin>>ar[i];
        m[ar[i]]++;
    }
    c=0;
    int ans=0;
    d=0;
    for(it=m.begin(); it!=m.end(); it++)
    {
        if((*it).first<(*it).second)
        {
            int k;
            k=(*it).second-(*it).first;


            ans+=k;

        }
        else if((*it).first>(*it).second)
        {
            ans+=(*it).second;
        }
    }
    cout<<ans<<endl;
    m.clear();
}


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

#define REP( i, n )     for( int (i) = 0; (i) < (n); (i)++ )
#define ALL( a )        (a).begin(), (a).end()

using namespace std;
using ll = long long;
using P = pair<int, int>;

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; }

const int INF = 1e9 + 1;
const ll LINF = 1e18;
const int MOD = 1e9 + 7;

ll gcd( ll a, ll b ){
    if( b == 0 ) return a;
    else return gcd( b, a % b );
}

int main(){
    ll a, b; cin >> a >> b;
    ll lcm = a * b / gcd( a, b );
    cout << lcm << endl;
}

/*

*/

Measured memory_bytes: 256
n=int(input())
lst=list(map(int,input().split()))

count=0
for j in range(n-1,0,-1):
    for i in range(j):
        if lst[i]>lst[i+1]:
            lst[i],lst[i+1]=lst[i+1],lst[i]
            count+=1

print(" ".join(map(str,lst)))
print(count)



Measured memory_bytes: 5600
#include <bits/stdc++.h>
using namespace std;
#define lll __int128
typedef long long ll;
typedef pair<int,int> pii;
typedef double lf; const lf err=1e-7;
#define repeat(i,a,b) for(int i=(a),iE=(b);i<iE;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,iE=(a);i>=iE;i--)
#define mst(a,x) memset((a),(x),sizeof(a))
#define qwq {cout<<"qwq"<<endl;}
#define orz(x) {cout<<#x": "<<x<<endl;}
const int N=110;
const int inf=1e9;
const int mod=1e9+7;
//#define int ll
ll k,x;
signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>k>>x;
	if(k*500>=x)cout<<"Yes"<<endl;else cout<<"No"<<endl;
	return 0;
}

Measured memory_bytes: 256
def gcd(x,y):
    if y == 0: return x
    else: return gcd(y,x%y)

def lcm(x,y): return x*y//gcd(x,y)

def f(x):
    cnt = 0
    while(x%2==0):
        x //= 2
        cnt += 1
    return cnt

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
na = [i//2 for i in a]

t = f(na[0])
for i in range(1,n):
    if t != f(na[i]):
        print(0)
        exit()

l = na[0]
for i in range(1,n): l = lcm(l,na[i])

if m < l:
    ans = 0
else:
    ans = 1 + (m-l)//(2*l)

print(ans)

Measured memory_bytes: 15060
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[40]={1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51};
int main()
{
	ios::sync_with_stdio(false);cin.tie(0);
	int n;
	cin >> n;
	cout << a[n-1] << endl;
	return 0;
} 

Measured memory_bytes: 256
#define _USE_NATH_DEFINES
#include<cstdio>
#include <iostream>
#include<sstream>
#include<fstream>
#include<iomanip>
#include<algorithm>
#include<cmath>
#include<complex>
#include <string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<bitset>
#include<numeric>
#include<limits>
#include<climits>
#include<cfloat>
#include<functional>
#include<iterator>
#include <random>

using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
using ll = long long;
#define EPS 1e-9
const int inf = 1e9 + 7;
const ll mod = 1e9 + 7;

int main() {
	int n;
	cin >> n;
	--n;
	vector<int> a(n+2, inf);
	rep(i, n) cin >> a[i + 1];
	ll ans = 0;
	rep(i, n + 1) ans += min(a[i], a[i + 1]);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 1000;
struct node{
	ll x, y, z;
}a[MAXN + 5];
int kx, ky, kz;
bool operator < (node p, node q) {
	return p.x*kx + p.y*ky + p.z*kz < q.x*kx + q.y*ky + q.z*kz;
}
int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	for(int i=1;i<=N;i++)
		scanf("%lld%lld%lld", &a[i].x, &a[i].y, &a[i].z);
	long long ans = 0;
	for(kx=-1;kx<=1;kx+=2)
		for(ky=-1;ky<=1;ky+=2)
			for(kz=-1;kz<=1;kz+=2) {
				sort(a+1, a+N+1);
				long long Sx = 0, Sy = 0, Sz = 0;
				for(int i=N;i>=N-M+1;i--) {
					Sx += a[i].x;
					Sy += a[i].y;
					Sz += a[i].z;
				}
				ans = max(ans, Sx*kx + Sy*ky + Sz*kz);
			}
	printf("%lld\n", ans);
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
//Σkの計算
int sigma(int n)
{
    int sum=0;
    sum = n*(n+1)/2;
    return sum;
}

int main()
{
    int n;
    int sum=0;
    cin>>n;


    cout<<sigma(n)<<"\n";
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define endl "\n"

#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);

#define vi vector<int>
#define vl vector<ll>
#define vvi vector<vector<int>>
#define vvl vector< vector<long long>>
#define mi map<int,int>
#define pi pair<int,int>

#define Fori(i,a,b) for(int i=a; i<b; i++)
#define Ford(i, a, b) for(int i=a; i>=b; i--)

#define pb push_back
#define mp make_pair

#define read(a, n) for(int i=0; i<n; i++) cin >> a[i];
#define print(x) cout << "X: == " << x << endl;
#define printMap(a) for(auto it=a.begin() ; it!= a.end() ; it++) {cout << it->first << "  " << it->second << endl; }
#define printVector(a) for(auto it = a.begin() ; it!= a.end() ;it++) {cout << *it << endl;}

using namespace std;
int main() {
    IOS
    ll n;
    cin >> n;
    int a = 1000;
    if(n % a == 0) {
        cout << "0\n";
        return 0;
    } 
    int x = n / a;
    x++;
    cout << x * a - n << endl;
    return 0; 
}

Measured memory_bytes: 3644
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <algorithm>
#include <set>
#include <map>
using namespace std;

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

	int d, n;
	cin >> d >> n;
	if (n == 100) n++;
	for (; d > 0; d--) n *= 100;
	cout << n << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <climits>
#include <iomanip>
#include <set>
#include <map>
using namespace std;
typedef long long ll;
int main(){
  ll l,r,d;
  cin >> l >> r >> d;
  cout << r / d - (l - 1) / d << endl;
}

Measured memory_bytes: 3604
#include<stdio.h>
int main(){
    int k,s,a,b,c,cnt=0;
    scanf("%d %d", &k, &s);
    for(a=0; a<=k; a++){
        for(b=0; b<=k; b++){
            c=s-a-b;
            if(c<=k && c>=0)
              cnt++;
        }
    }
    printf("%d",cnt);
    return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#define ll long long int
#define MOD 1000000007
#define INF 1e18

using namespace std;

int main(void){
  ll d;
  cin >> d;
  
  d -= 22;
  if (d == 0)
    cout << "Christmas Eve Eve Eve" << endl;
  else if (d == 1)
    cout << "Christmas Eve Eve" << endl;
  else if (d == 2)
    cout << "Christmas Eve" << endl;
  else if (d == 3)
    cout << "Christmas" << endl;


  return 0;
}


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

int main(){
  int n, m, total=0, can=0;
  cin >> n >> m;
  vector<int> a(n);
  rep(i,n){
    cin >> a[i];
    total += a[i];
  }
  rep(i,n){
    if(a[i]*4*m<total) continue;
    can++;
  }
  if(can >= m) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

Measured memory_bytes: 3632
#include<stdio.h>
int main(void){
  int N,H[20],i,j,c=0;
  scanf("%d",&N);
  for(i=0;i<=N-1;i++){
    scanf("%d",&H[i]);
  }
  for(i=1;i<=N-1;i++){
    for(j=0;j<=i-1;j++){
      if(H[i]<H[j]){
        break;
      }
      if(j==i-1)
        c++;
    }
  }
    printf("%d",c+1);
    return 0;
  }

Measured memory_bytes: 128
//Compete against Yourself.
#include <bits/stdc++.h>
#define _ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define int long long
#define sz(i) (int)(i.size())
#define F first
#define S second
#define L long double
#define P pair<int, int>
const int inf = 0x3f3f3f3f3f3f3f3LL;
const int mod = (int)1e9 + 7;
using namespace std;
#if LOCAL
#include "../../tr.h"
#else
#define tr(...)
#define endl '\n'
#endif
template<class T> void smin(T& a, T val) {if (a > val) a = val;}template<class T> void smax(T& a, T val) {if (a < val) a = val;}
const int N = 5*(int)1e5 + 10;

int n, m;

int32_t main(){_
   
   cin>>n>>m;

   map<int, bool> gotAC;
   map<int, int> count;

   int penalty = 0, ac = 0;
   for (int i = 0; i < m; ++i)
   {
      int id;
      string status;
      cin >> id >> status;
      if(gotAC.count(id)){
         continue;
      }
      else{
         if(status == "AC"){
            gotAC[id] = 1;
         }
         else{
            count[id]++;
         }
      }
   }
      
   int was = 0;
   for(auto it: gotAC){
      was += count[it.F];
   }

   cout<<gotAC.size()<<" "<<was;

   return 0;
}

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

typedef long long ll;

ll n;
ll Num[200005];
ll Sum[200005];

int main(){
    scanf("%lld", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld", &Num[i]);
        Sum[i] = Sum[i - 1] + Num[i];
    }
    ll Min = 1e15;
    for(int i = 1; i < n; i++){
        ll a = Sum[i];
        ll b = Sum[n] - Sum[i];
        a -= b;
        if(a < 0) a = -a;
        Min = min(Min, a);
    }
    printf("%lld",Min);
    return 0;


}


Measured memory_bytes: 3328
func readInts() -> [Int] {
    return readLine()!.split(separator: " ").map { Int($0)! }
}

func main() {
    let line = readLine()!
    let ints = line.map { (char) -> Int in
        let s = String(char)
        return Int(s)!
    }
    let count = ints.filter {$0 == 1}.count

    print("\(count)")
}

main()


Measured memory_bytes: 7940
#include<stdio.h>

int main(){
	int js=0;
	char a[4];
	gets(a);
	for (int i=0;i<4;i++){
		for(int j=i+1;j < 4;j++){
			if (a[j] == a[i]){
				js++;
			}
		}
	}
	if (js == 2){
		printf("Yes");
	}
	else{
		printf("No");
	}
} 

Measured memory_bytes: 128
#include<bits/stdc++.h>
#include<iostream>
#include<vector>
#include<algorithm>
#include<set>
#include<iomanip>
#include<queue>
#include<cmath>
#include<stack>
#include <map>
#define ll long long int
#define skip cin>>ws;
#define vll vector<ll> 
#define vb vector<bool>
#define vpll vector<pair<ll,ll>>
#define vvll vector<vector<ll>>
#define pll pair<ll,ll>
#define vs vector<string>
#define vvpll vector<vector<pair<ll, ll>>>
#define pb push_back
#define pob pop_back()
#define MOD (ll)(1e9 + 7)
#define test ll t; cin>>t; while(t--)

using namespace std;

void enter(vll &ar)
{
    ll n = ar.size();

    for(ll i=0;i<n;i++)
    {
        cin>>ar[i];
    }
}

void show(vll &a)
{
    ll n = a.size();

    for(ll i=0;i<n;i++)
    {
        cout<<a[i]<<" ";
    }
    cout<<"\n";
}

void SieveOfErat1sthenes(int n, vll &pri) 
{ 
    vb prime(n+1, true); 
   
    for (int p=2; p*p<=n; p++) 
    { 
        
        if (prime[p] == true) 
        { 
            pri.pb(p);
            
            for (int i=p*p; i<=n; i += p) 
                prime[i] = false; 
        } 
    } 
}

ll mo(ll a)
{
    return a%MOD;
}

bool compare(pll a, pll b)
{
    return a.first>b.first;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    ll n, k;
    cin>>n>>k;

    vll a(n);
    enter(a);

    vll fwin(k+1), swin(k+1);

    for(ll i=1;i<=k;i++)
    {
        for(ll j=0;j<n;j++)
        {
            if(a[j]>i) break;
            fwin[i] = (fwin[i]|(!swin[i-a[j]]));
        }

        for(ll j=0;j<n;j++)
        {
            if(a[j]>i) break;
            swin[i] = (swin[i]|(!fwin[i-a[j]]));
        }
    }

    if(fwin[k])
    {
        cout<<"First\n";
    }
    else
    {
        cout<<"Second\n";
    }

    return 0;
}


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

using namespace std;
#define ll long long
const int N = 1e6 + 5;
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int k ;
    cin >> k;
    string s;
    cin >> s;
    if (s.size() <= k) cout << s ;
    else {
        for(int i = 0 ; i < k ; i++) cout << s[i];
        cout <<"...";
    }
    return 0;
}

Measured memory_bytes: 3652
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
import collections
import math
import itertools
import heapq as hq
ceil = math.ceil
n,m = ma()
class unionfind():
    def __init__(self,n):
        self.par = list(range(n))
        self.size = [1]*n
        self.rank = [0]*n
        self.n = n
    def root(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

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

    def unite(self,x,y):
        x = self.root(x)
        y = self.root(y)
        if x==y:return
        else:
            if self.rank[x] < self.rank[y]:
                 x,y = y,x
            if self.rank[x] == self.rank[y]:
                self.rank[x]+=1
            self.par[y] = x
            self.size[x] +=self.size[y]
    def get_size(self,x):
        x = self.root(x)
        return self.size[x]
    def parent_set(self):
        for x in range(self.n):
            self.root(x)
        s = set()
        for par in self.par:
            s.add(par)
        return s
uf = unionfind(n)
for i in range(m):
    a,b = ma()
    a-=1;b-=1
    uf.unite(a,b)
ans = 0
for i in range(n):
    ans=max(ans,uf.get_size(i))
print(ans)


Measured memory_bytes: 78836
#include <iostream>
#include <vector>
#include <cmath>

using namespace std;
typedef long long ll;

int main(){
    ll q;
    cin >> q;
    vector<pair<ll, ll>> x(q);
    for(int i = 0; i < q; ++i){
        cin >> x.at(i).first >> x.at(i).second;
    }
    for(const auto p : x){
        ll a = p.first, b = p.second;
        if(abs(a - b) <= 1){
            cout << 2 * min(a, b) - 2 << endl;
        }else{
            ll c = (ll)(sqrt((long double)a * b));
            if(c * c == a * b){
                c--;
            }
            if(c * (c + 1) >= a * b){
                cout << 2 * c - 2 << endl;
            }else{
                cout << 2 * c - 1 << endl;
            }
        }
    }
    return 0;
}


Measured memory_bytes: 256
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        List<Integer> ls = new ArrayList<Integer>();
        int num = sc.nextInt();
        int cost = sc.nextInt();
        for(int i = 0; i < num; i++){
            ls.add(sc.nextInt());
        }
        ls.sort(Comparator.nullsFirst(Comparator.naturalOrder()));

        int sum = 0;
        int count = 0;
        for(int i = 0; i < num; i++){
            cost -= ls.get(i);
            count++;
            if(cost <= 0)
                break;
        }
        if(cost != 0)
            count--;
        System.out.println(count);
    }
}

Measured memory_bytes: 21972
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <climits>
#include <unordered_map>
#include <functional>
#include <queue>

#define rep(i, n) for(int i = 0, end = (int)(n); i < end; i++)

#define p2(a, b) cout << a << "\t" << b << endl
#define p3(a, b, c) cout << a << "\t" << b << "\t" << c << endl

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

inline int ctoi(char c) {
    return (int)(c -'0');
}

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

int main() {
    ll a, b;
    cin >> a >> b;
    cout << (((a*b)%2) ? "Odd" : "Even") << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include<algorithm>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111;
const int c_mINF = -1111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };


int myMax(int num[], int length);
int myMin(int num[], int length);

int main() {
	int N,M,X,Y;
	scanf("%d%d%d%d", &N,&M,&X,&Y);
	int x[200], y[200];
	for (int i = 0; i < N; i++)scanf("%d", &x[i]);
	for (int i = 0; i < M; i++)scanf("%d", &y[i]);


	int m = myMax(x, N);
	int m2 = myMin(y, M);

	
	if (m<m2 && X<=m && Y>=m2)printf("No War");
	else printf("War");
	

}

//---配列の最大値を求める---
int myMax(int num[], int length) {
	int temp = c_mINF;
	for (int i = 0; i < length; i++) {
		temp = max(temp, num[i]);
	}
	return temp;
}

//---配列の最小値を求める---
int myMin(int num[], int length) {
	int temp = c_INF;
	for (int i = 0; i < length; i++) {
		temp = min(temp, num[i]);
	}
	return temp;
}

/*         提出前の確認事項

・デバッグ用の関数は＜＜コメント化＞＞しているか？
・すべての＜＜入力例＞＞は試したか？
・＜＜限界値分析＞＞はしたか？
・＜＜出力の改行＞＞の有無は確認したか？
・文字列の＜＜スペル＞＞は確認したか？
・＜＜解の存在性＞＞は確認したか？
　　　　　　　　↓
	 ＜＜提出先＞＞に注意して提出！！
*/

Measured memory_bytes: 128
import sys

input = sys.stdin.readline


def nap(n, cap):
    mxk = 0
    inf = 10 ** 10
    wei = [0] + [inf] * 100000
    for _ in range(n):
        w, v = map(int, input().split())
        for vk in range(100000, v - 1, -1):
            nw = wei[vk - v] + w
            if nw > cap: continue
            if wei[vk] > nw:
                wei[vk] = nw
                if vk > mxk:
                    mxk = vk
    return mxk


n, cap = map(int, input().split())
print(nap(n, cap))


Measured memory_bytes: 5432
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define LL long long
using namespace std;
const LL Maxn = 100010;
LL a[Maxn], b[Maxn], n;
LL c[Maxn], cl;
int main() {
	LL i, j, k;
	scanf("%lld", &n);
	for(i = 1; i <= n; i++) scanf("%lld", &a[i]);
	for(i = 1; i <= n; i++) scanf("%lld", &b[i]);
	LL sum = 0, ans = 0;
	for(i = 1; i <= n; i++){
		if(a[i] > b[i]) c[++cl] = a[i]-b[i];
		else if(a[i] < b[i]) sum += b[i]-a[i], ans++;
	}
	if(sum <= 0){ printf("0\n"); return 0; }
	sort(c+1, c+cl+1);
	for(i = cl; i >= 1; i--){
		sum -= c[i]; ans++;
		if(sum <= 0) break;
	}
	if(sum > 0) printf("-1\n");
	else printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 2176
W, H, N = map(int, input().split())
w, h = 0, 0

for _ in range(N):
    x, y, a = map(int, input().split())
    if a == 1:
        # 黒の領域(x軸)を増やす
        w = max(w, x)
    elif a == 2:
        # 白の領域(x軸)を削る
        W = min(W, x)
    elif a == 3:
        # 黒の領域(y軸)を増やす
        h = max(h, y)
    else:
        # 白の領域(y軸)を削る
        H = min(H, y)

if W < w or H < h:
    print(0)
else:
    print((W-w)*(H-h))

Measured memory_bytes: 3064
N, K = map(int, input().split())
A = map(int, input().split())
A = [x-1 for x in A] # 0-indexedに変換

here = 0
visited = set()
route = []

while here not in visited:
    visited.add(here)
    route.append(here)
    here = A[here]

loopStart = route.index(here)

if K <= loopStart:
    ans = route[K]
else:
    lenCycle = len(route) - loopStart
    ans = route[loopStart + (K - loopStart) % lenCycle]

print(ans + 1)

Measured memory_bytes: 124440
# -*- coding: utf-8 -*-
# D

import sys
import itertools
from collections import defaultdict, deque
from heapq import heappush, heappop
import math
import bisect

input = sys.stdin.readline

# 再起回数上限変更
# sys.setrecursionlimit(1000000)

mod = 10**9 + 7
s = int(input())
max_len = s//3+2

dp = [[0] * (s+1) for _ in range(max_len)]
dp[0][0]=1
# print(dp)

for i in range(1, max_len):
    tmp = dp[i-1]
    cumsum = list(itertools.accumulate(tmp))
    # print(cumsum)
    for a in range(s+1):
        if a>=3:
            dp[i][a] = (cumsum[a-3] + dp[i][0]) % mod


ans = 0
for e in dp:
    ans += e[s]
print(ans % mod)

Measured memory_bytes: 79504
# coding: utf-8
import sys

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, M = lr()
AB = [lr() for _ in range(N)]
AB.sort()
drink = 0
answer = 0
for i in range(N):
    cost = AB[i][0]
    limit = AB[i][1]
    if drink + limit < M:
        answer += cost * limit
        drink += limit
    else:
        x = M - drink
        answer += cost * x
        break

print(answer)


Measured memory_bytes: 27840
import java.util.Scanner;

public class Main {
	
	/*
	public int[][] adj = 
		{
			{0,1,0,0,0,0,0,0,0,0,0,0,0,0,0},
			{0,0,1,0,0,0,0,0,0,0,0,0,0,0,0},
			{0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
			{0,0,0,0,1,0,0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,1,0,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,1,0,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0,1,0,0,0,0,0},
			{0,0,0,0,0,0,0,0,0,0,1,0,0,0,0},
			{0,0,0,0,0,0,0,0,0,0,0,1,0,0,0},
			{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0},
			{0,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
			{0,0,0,0,0,0,0,0,0,0,0,0,0,0,1},
			{1,0,0,0,0,0,0,0,0,0,0,0,0,0,0},
		};
	*/
	
	public static int[] print_num = 
		{0,1,2,3,4,5,6,7,8,9,5,4,3,2,1};
	
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		for(int i = 0; i < n; i++){
			int from = sc.nextInt();
			int to = sc.nextInt();
			
			if(from > to){
				if(from <= 5){
					from = 15 - from;
					to = 15 - to;
				}else if(to <= 5){
					to = 15 - to;
				}else{
					to += 15;
				}
			}
			
			boolean first = true;
			for(int j = from; j <= to; j++){
				
				System.out.print((first ? "" : " ") + print_num[j % 15]);
				
				if(first){
					first = false;
				}
			}
			System.out.println();
		}
		
	}
	
}

Measured memory_bytes: 12000
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _1_7_D
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] str = Console.ReadLine().Split(' ');
            int n = int.Parse(str[0]);
            int m = int.Parse(str[1]);
            int l = int.Parse(str[2]);
            long[,] arrayA = new long[n, m];
            long[,] arrayB = new long[m, l];
            long[,] arrayC = new long[n, l];
            string[] strA = new string[m];
            long sumC = 0;
            for(int i = 0; i < n; i++)
            {
                strA = Console.ReadLine().Split(' ');
                for (int j = 0; j <m; j++)
                {
                    arrayA[i, j] = long.Parse(strA[j]);
                }
            }
            for (int i = 0; i < m; i++)
            {
                strA = Console.ReadLine().Split(' ');
                for (int j = 0; j < l; j++)
                {
                    arrayB[i, j] = long.Parse(strA[j]);
                }
            }
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < l; j++)
                {
                    for (int g = 0; g < m; g++)
                    {
                        sumC = sumC + (arrayA[i, g] * arrayB[g, j]);
                    }
                    arrayC[i, j] = sumC;
                    sumC = 0;
                }
            }
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < l-1; j++)
                {
                    Console.Write("{0} ", arrayC[i, j]);
                }
                Console.Write(arrayC[i, l-1]);
                Console.Write("\n");
            }
        }
    }
}



Measured memory_bytes: 17984
n = input()
a,b,c = [int(n[i]) for i in range(len(n))]

if a > b:
  print(a*111)
elif a == b:
  if b >= c:
    print(a*111)
  else:
    print((a+1)*111)
else:
  print((a+1)*111)
  

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

int main(){
    int a, b, C;
    cin >> a >> b >> C;
    double C2=2*M_PI*C/360;
    double S, L, h;
    S=1.0/2*a*b*sin(C2);
    double c=sqrt(a*a+b*b-2*a*b*cos(C2));
    L=a+b+c;
    h=b*sin(C2);
    std::cout<<std::fixed<<std::setprecision(10) << S << endl;
    std::cout<<std::fixed<<std::setprecision(10) << L << endl;
    std::cout<<std::fixed<<std::setprecision(10) << h << endl;
}


Measured memory_bytes: 3580
#include <bits/stdc++.h>
#ifdef LOCAL
#include "debuger.hpp"
#else
#define DUMP(...) 1145141919810
#define CHECK(...) (__VA_ARGS__)
#endif

int main() {
  int n;
  scanf("%d", &n);
  std::map<std::pair<int, int>, int> map;
  for (int i = 0; i < n; ++i) {
    double x;
    scanf("%lf", &x);
    long long w = llround(x * 1e9);
    int two = 0, five = 0;
    while (w % 2 == 0) w /= 2, ++two;
    while (w % 5 == 0) w /=5, ++five;
    map[{two, five}]++;
  }
  long long result = 0;
  for (const auto& a : map) {
    for (const auto& b : map) {
      if (a.first.first + b.first.first >= 18 &&
          a.first.second + b.first.second >= 18) {
        if (a < b)
          result += a.second * 1LL * b.second;
        else if (a == b)
          result += a.second * 1LL * (a.second - 1) / 2;
      }
    }
  }
  printf("%lld\n", result);
}


Measured memory_bytes: 3836
import numpy as np
n=int(input())
arr = np.array([int(i) for i in input().split()])
mod = 10**9+7
sm=0

for i in range(60):
    c1 = np.count_nonzero(arr & 1)
    sm += 2 ** i * c1 * (n-c1)
    arr >>= 1

print(sm%mod)

Measured memory_bytes: 68832