akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> VI;
 
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; }
#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<int(b);++i)
#define rep(...) _overload3(__VA_ARGS__,repi,_rep,)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
const int mod=1e9+7;

ll c[51][51];

template< typename T >
struct BinaryIndexedTree {
  vector< T > data;
  int n;
 
  BinaryIndexedTree(int sz) {
    n=sz;
    data.assign(++sz, 0);
  }
 
  T sum(int k) { //0-indexed
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }
 
  void add(int k, T x) { 
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
 
  T sum_between(int i, int j){
      if(i>j)return 0;
      return sum(j)-sum(i-1);
  }
 
  // data[0]+...+data[ret+1] >= x
  int lower_bound(T w){
    if(w<=0)return 0;
    int x=0;
    int k=1;
    while(2*k<=n)k<<=1;
    for(;k>0;k/=2){
      if(x+k<=n&&data[x+k]<w){
        w-=data[x+k];
        x+=k;
      }
    }
    return x+1;
  }
};

int main(){
  
  int n;cin>>n;
  ll q[n],a[n],b[n];
  vector<ll> zipa;
  rep(i,n){
    cin>>q[i];
    if(q[i]==1){
      cin>>a[i]>>b[i];
      zipa.push_back(a[i]);
    }
  }
  sort(all(zipa));
  zipa.erase(unique(all(zipa)),zipa.end());
  int asz=zipa.size();
  BinaryIndexedTree<ll> BIT1(asz),BITv(asz);
  ll B=0;int ctr=0;
  rep(i,n){
    if(q[i]==1){
      int j=lower_bound(all(zipa),a[i])-zipa.begin();
      BIT1.add(j,1);
      BITv.add(j,a[i]);
      B+=b[i];
      ctr++;
    }
    else{
      ll res=B;
      int mid=(ctr+1)/2;
      int k=BIT1.lower_bound(mid)-1;
      ll midvalue=BITv.sum_between(k,k)/BIT1.sum_between(k,k);
      cout<<midvalue<<" ";
      ll forward=BIT1.sum(k-1)*midvalue-BITv.sum(k-1);
      ll backward=BITv.sum_between(k+1,asz-1)-BIT1.sum_between(k+1,asz-1)*midvalue;
      cout<<res+forward+backward<<endl;
    }
  }
}

Measured memory_bytes: 9716
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    H = INT()
    s = "{:b}".format(H)
    print(int(s[0] * len(s), 2))


if __name__ == '__main__':
    main()


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

// コンテスト中のみ
#define int long long

#define ll long long
#define rep(i,n) for(int i = 0; i < (n); i++)
#define P pair<ll,ll>
#define ld long double
ll INF = (1LL << 60);
int MOD = 1000000007;

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	string s; cin >> s;
	ll now = 0;
	rep(i, s.size()) {
		now += s[i] - '0';
	}
	if (now % 9 == 0)cout << "Yes" << endl;
	else cout << "No" << endl;
	return 0;
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
using ll = long long;

int main() {
    string S;
    cin >> S;

    vector<ll> a(S.size() + 1, 0);

    rep(i, S.size()) {
        if (S[i] == '<') chmax(a[i + 1], a[i] + 1);
    }

    for (int i = S.size() - 1; i >= 0; i--) {
        if (S[i] == '>') chmax(a[i], a[i + 1] + 1);
    }

    ll sum = 0;
    rep(i, a.size()) sum += a[i];
    cout << sum << endl;
}


Measured memory_bytes: 4740
#include<iostream>
#include <algorithm>
#include<string>
#include <bitset>
#include <vector>
#include <functional>
#include <climits>
using namespace std;
//int a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, ans = 0;
long long a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, i = 0, j = 0, k = 0, l = 0, ans = 0;
//cout << LONG_MAX << endl;
//string s[1001];
long long n, m;
long long x[1001] = {}, y[1001] = {}, z[1001] = {}, num[1001] = {};
long long xx[1001] = {}, yy[1001] = {}, zz[1001] = {};

void BubSort()
{
	long long i, j, temp;

	for (i = 0; i < n - 1; i++) {
		for (j = n - 1; j > i; j--) {
			if (num[j - 1] < num[j]) {
				temp = num[j];        /* 交換する */
				num[j] = num[j - 1];
				num[j - 1] = temp;

				temp = x[j];        /* 交換する */
				x[j] = x[j - 1];
				x[j - 1] = temp;

				temp = y[j];        /* 交換する */
				y[j] = y[j - 1];
				y[j - 1] = temp;

				temp = z[j];        /* 交換する */
				z[j] = z[j - 1];
				z[j - 1] = temp;
			}
		}
	}
}
int main()
{
	cin >> n;
	cin >> m;
	for (a = 0; a < n; a++)
	{
		cin >> xx[a];
		cin >> yy[a];
		cin >> zz[a];
	}
	ans = LLONG_MIN;
	int sign[2];
	sign[0] = 1;
	sign[1] = -1;
	for (a = 0; a < n; a++)
	{
		x[a] = xx[a];
		y[a] = yy[a];
		z[a] = zz[a];
	}
	for (e = 0; e < 2; e++)
	{
		for (f = 0; f < 2; f++)
		{
			for (g = 0; g < 2; g++)
			{
				/*for (a = 0; a < n; a++)
				{
				x[a] = xx[a];
				y[a] = yy[a];
				z[a] = zz[a];
				}*/
				for (a = 0; a < n; a++)
				{
					num[a] = sign[e] * x[a] + sign[f] * y[a] + sign[g] * z[a];
				}
				BubSort();
				b = 0;
				c = 0;
				d = 0;
				for (a = 0; a < m; a++)
				{
					b += x[a];
					c += y[a];
					d += z[a];
				}
				ans = max(ans, abs(b) + abs(c) + abs(d));
				b = 0;
				c = 0;
				d = 0;
				for (a = n - 1; a > n - m - 1; a--)
				{
					b += x[a];
					c += y[a];
					d += z[a];
				}
				ans = max(ans, abs(b) + abs(c) + abs(d));
			}
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <numeric>
#include <unordered_map>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <memory>
#include <iomanip>
#include <type_traits>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
constexpr long long MOD = 1e9 + 7;
constexpr long long MAX = 1000000;

//long long MOD = 998244353;
constexpr ll INF = 1e17;
constexpr double PI = 3.141592653589793;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

ll h, w;
vector<ll> dx = { -1, 0, 1, 0 };
vector<ll> dy = { 0, -1, 0, 1 };


bool isInField(ll x, ll y) {
    bool f = x >= 0 && x < w && y >= 0 && y < h;
    return f;
}

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

    ll n, k;
    cin >> n >> k;
    vector<ll> h(n);
    for (ll i = 0; i < n; i++)
    {
        cin >> h[i];
    }

    sort(h.rbegin(), h.rend());


    ll ans = 0;
    for (ll i = 0; i < n; i++)
    {
        if (i < k) {
            continue;
        }

        ans += h[i];
    }

    cout << ans << "\n";

    return 0;
}



Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define COUT(x) cout<<(x)<<endl
#define dump(x)  cout << #x << " = " << (x) << endl;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;
using M = map<int,int>;
using PQ = priority_queue<int>;
using PQG = priority_queue<int, vector<int>, greater<int>>;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

int main() {
  ll n; string s; cin >> n >> s;
  map<char, ll> m;
  for(auto c : s) {
    if (m[c]) m[c]++;
    else m[c]=1;
  }
  ll ans = m['R']*m['G']*m['B'];

  ll sub = 0;
  for (ll j = 0; j < n; j++) {
    for (ll k = 0; k < n; k++) {
      ll i = 2*j-k;
      if (i >= n || i < 0) continue;
      if (i >= j || j >= k) continue;
      bool ok = (s[i] != s[j]) && (s[i] != s[k]) && (s[j] != s[k]);
      if (ok) sub++;
      /*
      if (ok) {
        dump(i);
        dump(j);
        dump(k);
        cout << s[i] << s[j] << s[k] << endl;;
      }
      */
    }
  }
  ans-=sub;
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3636
# coding: utf-8
# Your code here!
# coding: utf-8
import sys
sys.setrecursionlimit(10000000)

#const
dxdy=((1,0),(0,1))
# my functions here!
def pin(type=int):
    return map(type,input().rstrip().split())

def resolve():
    N,=pin()
    A=list(pin())
    from collections import Counter as ct
    a=ct(A)
    t=(a.items())
    #print(t)
    
    Sum=0
    for l in a.values():
        Sum+=(l*(l-1))//2 
    ans=[0]*N
    for j in a.items():
        x,y=j
        ans[x-1]=Sum-((y*(y-1))//2)+(((y-2)*(y-1))//2)     
    for i in A:
        print(ans[i-1])
"""         
#printデバッグ消した？
#前の問題の結果見てないのに次の問題に行くの？
"""
"""
お前カッコ閉じるの忘れてるだろ
"""
import sys
from io import StringIO
import unittest


class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)

    def test_入力例_1(self):
        input = """5
1 1 2 1 2"""
        output = """2
2
3
2
3"""
        self.assertIO(input, output)

    def test_入力例_2(self):
        input = """4
1 2 3 4"""
        output = """0
0
0
0"""
        self.assertIO(input, output)

    def test_入力例_3(self):
        input = """5
3 3 3 3 3"""
        output = """6
6
6
6
6"""
        self.assertIO(input, output)

    def test_入力例_4(self):
        input = """8
1 2 1 4 2 1 4 1"""
        output = """5
7
5
7
7
5
7
5"""
        self.assertIO(input, output)


if __name__=="__main__":resolve()

Measured memory_bytes: 100804
N = int(input())
A = list(map(int,input().split()))

dp = [[[0.0 for k in range(N+1)] for j in range(N+1)] for i in range(N+1)]
dp[0][0][0] = 0

a,b,c = 0,0,0
for i in range(N):
    if A[i] == 1:
        a += 1
    elif A[i] == 2:
        b += 1
    else:
        c += 1

for k in range(c+1):
    for j in range(b+c-k+1):
        for i in range(a+b+c-k-j+1):
            if i==j==k==0:
                continue
            temp = N
            if i!=0:
                temp += dp[i-1][j][k]*i
            if j!=0:
                temp += dp[i+1][j-1][k]*j
            if k!=0:
                temp += dp[i][j+1][k-1]*k
            dp[i][j][k] = temp/(i+j+k)

print(dp[a][b][c])

Measured memory_bytes: 259080
#include <iostream>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <queue>
#include <stack>
#include <list>
#include <utility>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
#include <unordered_map>
#include <climits>

typedef long long ll;
const int MOD = pow(10,9)+7;
const ll LMAX = 100000000000000000;

using namespace std;
int in(){
    int temp;
    scanf("%d",&temp);
    return temp;
}

ll lin(){
    ll temp;
    scanf("%lld",&temp);
    return temp;
}


int main() {

    ll N = lin(); ll K = lin();
  
    if( N % 3 == 0 || K % 3 == 0){
        cout << 0 << endl;
        return 0;
    }
    
    ll diffmin = LMAX;
    ll temp;
    
    priority_queue<ll> pq;
    
    
    
    if (N >= 4){
        /////三分割横
        for(auto i = 1; i <= N-2; i ++){
            pq.push(i * K);
            pq.push((N-i)/2 * K);
            pq.push((N - (N-i)/2 - i)*K);
            
            temp = pq.top();
            pq.pop();
            pq.pop();
            temp-=pq.top();
            pq.pop();
            
            if (diffmin > temp) diffmin = temp;
            pq.empty();
        }
        
    }

    
    if (K >= 4){
        /////三分割縦
        for(auto i = 1; i <= K-2; i ++){
            pq.push(i * N);
            pq.push((K-i)/2 * N);
            pq.push((K - (K-i)/2 - i)*N);
            
            temp = pq.top();
            pq.pop();
            pq.pop();
            temp-=pq.top();
            pq.pop();
            
            if (diffmin > temp) diffmin = temp;
            pq.empty();
        }
    }
    

    
    /////二分割横
    for(auto i = 1; i <= N-1; i ++){
        pq.push(i * K);
        pq.push((N-i) * (K/2));
        pq.push((N-i)*(K-K/2));
        
        temp = pq.top();
        pq.pop();
        pq.pop();
        temp-=pq.top();
        pq.pop();
        
        if (diffmin > temp) diffmin = temp;
        pq.empty();
        
    }
    
    /////二分割縦
    for(auto i = 1; i <= K-1; i ++){
        pq.push(i * N);
        pq.push((K-i) * (N/2));
        pq.push((K-i) * (N-N/2));
        
        temp = pq.top();
        pq.pop();
        pq.pop();
        temp-=pq.top();
        pq.pop();
        
        if (diffmin > temp) diffmin = temp;
            pq.empty();
        }

    
    cout << diffmin << endl;
    return 0;
    
    
}





Measured memory_bytes: 256
while (True):
    n, r = map(lambda i: int(i), input().split())
    if n == 0:
        break

    inds = [i for i in reversed(range(1, n+1))]

    for i in range(r):
        p, c = map(lambda j: int(j), input().split())
        inds = inds[p-1:p-1+c] + inds[:p-1] + inds[p-1+c:]

    print(inds[0])



Measured memory_bytes: 5620
#include<bits/stdc++.h>
using namespace std;
#define mx 86800000
int main()
{
  int n,k,p[100001],s=0,i,j;
  cin>>n>>k;
  for(i=0;i<n;i++){
    cin>>p[i];
  }
  sort(p,p+n);
  for(i=0;i<k;i++){
    s+=p[i];
  }
  cout<<s;

}


Measured memory_bytes: 3648
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int INF = 1000000007;
using ll = long long;
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    int ans = (n - 1 + k - 1 - 1) / (k - 1);
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 256
class InputLine
  def self.to_s
    gets.chomp
  end

  def self.to_i
    InputLine.to_s.to_i
  end
  
  def self.to_f
    InputLine.to_s.to_f
  end

  def self.to_sa
    InputLine.to_s.split(' ')
  end

  def self.to_ia
    InputLine.to_sa.map(&:to_i)
  end
  
  def self.to_fa
    InputLine.to_sa.map(&:to_f)
  end
end

def main(argv)
  n = InputLine.to_i
  l = InputLine.to_ia.sort

  c = 0
  n.times do |i|
    ((i + 1)...n).each do |j|
      next if l[i] == l[j]
      ((j + 1)...n).each do |k|
        next if (l[i] == l[k]) || (l[j] == l[k])
        c += 1 if l[i] + l[j] > l[k]
      end
    end
  end
  puts c.to_s
end

if self.to_s == 'main' then
  main(ARGV)
end

Measured memory_bytes: 14332
#include<cstdio>
#include<algorithm>
using namespace std;
int nw,n,l[105],x,dp[2][105][505],sum[2][105][505],sum2[2][105][505],ans=0,fac[105];
const int mod=1e9+7;
bool cmp(int a,int b){return a>b;}
int M(int x){return x>=mod?x-mod:x;}
signed main()
{
	scanf("%d%d",&n,&x);
	fac[0]=1;
	for(int i=1;i<=n;i++)fac[i]=1ll*fac[i-1]*i%mod;
	for(int i=1;i<=n;i++)scanf("%d",&l[i]);
	sort(l+1,l+n+1,cmp);
	nw=0;dp[0][1][l[1]]=1;
	for(int k=l[1];k<=x;k++)sum[0][1][k]=1,sum2[0][1][k]=l[1];
	for(int i=2;i<=n;i++)
	{
		nw=!nw;
		for(int j=1;j<=min(x/l[i],i);j++)
		{
			for(int k=1;k<=x;k++)
			{
				dp[nw][j][k]=sum[nw][j][k]=sum2[nw][j][k]=0;
				if(k-l[i]>=0)dp[nw][j][k]=dp[!nw][j-1][k-l[i]];
				dp[nw][j][k]=(dp[nw][j][k]+1ll*dp[!nw][j][k]*(k-j*(l[i]-1)))%mod;
				dp[nw][j][k]=(dp[nw][j][k]+1ll*M(sum[!nw][j][k-1]-sum[!nw][j][max(0,k-l[i])]+mod)*2*j)%mod;
				if(l[i]>=2&&k>=2)
				{
					dp[nw][j][k]=(dp[nw][j][k]+1ll*M(l[i]-k-1+mod)*M(sum[!nw][j+1][k]-sum[!nw][j+1][max(2,k-l[i]+1)]+mod)%mod*j*(j+1))%mod;
					dp[nw][j][k]=(dp[nw][j][k]+1ll*M(sum2[!nw][j+1][k]-sum2[!nw][j+1][max(2,k-l[i]+1)]+mod)*j*(j+1))%mod;
				}
				sum[nw][j][k]=M(sum[nw][j][k-1]+dp[nw][j][k]);
				sum2[nw][j][k]=(sum2[nw][j][k-1]+1ll*dp[nw][j][k]*k)%mod;
				//printf("#2%d %d %d %d\n",i,j,k,dp[nw][j][k]);
			}
		}
	}
	for(int i=1;i<=n;i++)ans=(ans+1ll*dp[nw][i][x]*fac[i])%mod;
	printf("%d\n",ans);
	return 0;
 } 

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

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin>>s;
    long long n=0;
    for(int i=0;i<s.size();i++){
        n+=s[i]-48;
    }
    if(n%9==0){
        cout<<"Yes\n";
    }else{
        cout<<"No\n";
    }
return 0;


}

//      *   *  *****  *   *  *   *   ****  ****    ****     **  ***
//     *   *  *      **  *  *   *  *      *   *  *        * *  *  *
//    *****  *****  * * *  *   *  *      ****   *       *  *    *
//   *   *      *  *  **  *   *  *      *  *   *       *****  *
//  *   *  *****  *   *   ***    ****  *   *   ****      *  ****

//     ****  *   *  *   *   ***   *   *  *****  *   *
//    *     *   *  *   *  *   *  *   *  *      *   *
//    ***  *****  *   *  *****  * * *  ****   *   *
//      *   *    *   *  *   *  * * *  *      *   *
//  ****   *     ***   *   *   * *   *****   ***

//        ********                                 . O .
//      *           *                               . .
//     *            * *       * ********
//    * ***********    *    *  *         *
//    *                 * *      *********
//                      *                 *
//                 *   *
//                   *  *
//                     **
//                   *  **  *
//              *  *    * **
//                *     ** * *
//            *   **   ** * *  * *
//           *    * * * * * *   **
//          **************************


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

int main() {
  int num,limit;
  int cnt = 0;
  int tmpHeight;
  
  cin >> num >> limit;
  
  for(int i = 0; i < num; i++){
    cin >> tmpHeight;
    if(tmpHeight >= limit) cnt++;
  }
  
  cout << cnt;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;

int main()
{
    int n; cin>>n;
    ll s=0;
    map<ll, ll> mp; mp[0]++;
    for(int i=1; i<=n; i++){
        ll a; cin>>a;
        s+=a;
        mp[s]++;
    }
    ll ans=0;
    for(auto p:mp){
        ans+=(p.second*(p.second-1)/2);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 12800
#include <stdio.h>

#define MAX 100001
#define NIL -1

typedef struct Node_ {
    int parent;
    int leftChild;
    int rightSibling;
} Node;

static Node Tree[MAX];
int Depth[MAX];

static void setDepth(int i, int depth)
{
    Depth[i] = depth;
    if (Tree[i].leftChild != NIL) {
        setDepth(Tree[i].leftChild, depth + 1);
    }
    if (Tree[i].rightSibling != NIL) {
        setDepth(Tree[i].rightSibling, depth);
    }
}

static void printNode(int i)
{
    printf("node %d: parent = %d, depth = %d, ", i, Tree[i].parent, Depth[i]);

    if (Tree[i].parent == NIL) {
        printf("root, ");
    } else if (Tree[i].leftChild == NIL) {
        printf("leaf, ");
    } else {
        printf("internal node, ");
    }

    printf("[");
    int child = Tree[i].leftChild;
    for (int j = 0; child != NIL; j++) {
        if (j > 0) {
            printf(", ");
        }
        printf("%d", child);
        child = Tree[child].rightSibling;
    }
    printf("]\n");
}

int main()
{
    int n;

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        Tree[i].parent = Tree[i].leftChild = Tree[i].rightSibling = NIL;
    }

    for (int i = 0; i < n; i++) {
        int id, k;
        int l = 0;
        scanf("%d %d", &id, &k);
        for (int j = 0; j < k; j++) {
            int c;
            scanf("%d", &c);
            if (j == 0) {
                Tree[id].leftChild = c;
            } else {
                Tree[l].rightSibling = c;
            }
            Tree[c].parent = id;
            l = c;
        }
    }

    int root = 0;

    for (int i = 0; i < n; i++) {
        if (Tree[i].parent == NIL) {
            root = i;
            break;
        }
    }

    setDepth(root, 0);

    for (int i = 0; i < n; i++) {
        printNode(i);
    }

    return 0;
}


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

#define f first
#define s second
#define pb push_back
#define all(v) (v).begin(), (v).end()
#define debug(v) cout << #v << ":\t" << v << endl

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;

const ll N = 1e5 + 1;
const ll INF = 1e18 + 7;

ll n, k, w[N], v[N], dp[N], res;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	fill(dp, dp + N, INF);
	
	cin >> n >> k;
	for (ll i = 1; i <= n; ++i) {
		cin >> w[i] >> v[i];
	}
	
	dp[0] = 0;
	for (ll i = 1; i <= n; ++i) {
		for (ll j = N - 1; j >= v[i]; --j) {
			dp[j] = min(dp[j], dp[j - v[i]] + w[i]);
		}
	}
	
	res = 0;
	for (ll i = 1; i < N; ++i) {
		if (dp[i] <= k) res = i;
	}
	cout << res;
	
	return 0;
}


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

int main(){
    ll n ,k;
    cin>>n>>k;
    ll arr[n];
    ll dp[n];
    for(ll i=0;i<n;i++)cin>>arr[i];
    for(ll i=0;i<n;i++)dp[i]=10000000000;
    dp[0]=0;
    for(ll i=0;i<n;i++){
       for(ll j=1;j<=k;j++){
           if(i+j<n){
               dp[i+j]=min(dp[i+j],dp[i]+abs(arr[i]-arr[i+j]));
           }
       }
    }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i = a; i < b; ++i)
#define all(c) c.begin(), c.end()
#define gmax(x,y) x=max(x,y)
#define gmin(x,y) x=min(x,y)
#define gadd(x,y) x=add(x,y)
#define gmul(x,y) x=mul(x,y)
using namespace std;

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

const int N = 2e5 + 5;

int dpf[N], dpb[N];

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n,k,c;
	cin >> n >> k >> c;
	string s;
	cin >> s;
	vector<int> pos;
	rep(i,0,n)if(s[i] == 'o')pos.push_back(i);

	// back
	dpb[0] = s[0] == 'o';
	rep(i,1,n){
		if(s[i] == 'o'){
			auto pri = lower_bound(all(pos), i-c);
			if(pri != pos.begin()){
				--pri;	
				int loc = *pri;
				gmax(dpb[i], dpb[loc] + 1);
			}
			else gmax(dpb[i],1);
		}
		gmax(dpb[i],dpb[i-1]);
	}

	// forward
	dpf[n-1] = s[n-1] == 'o';
	for(int i = n-2;i>=0;--i){
		if(s[i] == 'o'){
			auto pri = upper_bound(all(pos), i+c);
			if(pri != pos.end()){
				int loc = *pri;
				gmax(dpf[i], dpf[loc] + 1);
			}
			else gmax(dpf[i],1);
		}
		gmax(dpf[i],dpf[i+1]);
	}

	vector<int> ans;
	vector<int> cnt(n+c+1);
	gmax(c,1);
	rep(i,0,n+c){
		int tot = 0;
		tot += (i-c>=0?dpb[i-c]:0);
		tot += (i+1<n?dpf[i+1]:0);
		if(tot >= k){
			++cnt[max(i-c+1,0)];
			--cnt[i+1];
		}
	}
	int rsum = 0;
	rep(i,0,n){
		rsum += cnt[i];
		if(s[i] == 'o' && rsum == 0){
			cout << i + 1 << '\n';
		}
	}
}


Measured memory_bytes: 5004
#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
#define fil(x) memset(x, 0, sizeof(x))
#define fillb(x) memset(x,false,sizeof(x))
#define fillm(x) memset(x, -1, sizeof(x))
#define mp make_pair
#define pll pair<int, int>
#define pf printf
#define sf scanf
#define all(x) x.begin(),x.end()
#define pb push_back
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define np std::string::npos
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<n;i++)
#define fof(i,a,b) for(int i=a;i<=b;i++)
#define off(i,a,b) for(int i=a;i>=b;i--)
#define of(i,n) for(int i=n-1;i>=0;i--)
#define stl(i,x) for(auto i=x.begin(); i!=x.end();i++)
#define highest(x) numeric_limits<x>::max()
#define lowest(x) numeric_limits<x>::min()
#define Inf INFINITY
#define minv(v) *min_element(v.begin(),v.end())
#define maxv(v) *max_element(v.begin(),v.end())
#define cases(cs,t) for(int cs=1;cs<=t;cs++)
#define PI acos(-1)
#define nl endl

typedef unsigned long long lll;
typedef long long ll;
int knigtx8[] = {2, 2, -2, -2, 1, 1, -1, -1}; ///knight move in chess
int knigty8[] = {1, -1, 1, -1, 2, -2, 2, -2}; ///knight move in chess
int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}; ///for 8 directions
int dy8[] = {1,-1, 1, -1, 0, 0, -1, 1}; ///for 8 directions
int dx4[] = {0, 0, 1, -1}; ///for 4 directions
int dy4[] = {1, -1, 0, 0}; ///for 4 directions
const int maxx=100005;

//this fuction sorts vector pair according to first element in descending order.
bool sortinrev(const pair<int,int> &a,const pair<int,int> &b)
{
    return a.first>b.first;
}
ll pw(ll a, ll b)
{
    ll ans = 1;
    for(ll i = 1; i <= b; ++i)
        ans = (ans * a);
    return ans;
}
template<typename T>inline T Bigmod(T base, T power, T MOD){
    T ret=1;
    while(power)
    {
        if(power & 1)ret=(ret*base)%MOD;
        base=(base*base)%MOD;
        power>>=1;
    }
    return ret;
}

int main()
{
    IOS;
    int n;cin>>n;
    cout<< n + (n*n) + (n*n*n)<<endl;
    return 0;
}

///Alhamdulillah


Measured memory_bytes: 3648
#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 2e5 + 5;
int n, a[N];
long long res;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &a[i]);
		a[i] -= i;
	}
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; ++ i) {
		res += abs(a[i] - a[(n + 1) / 2]);
	}
	printf("%lld", res);
}

Measured memory_bytes: 1024
H,W = (int(i) for i in input().split())
Y = []
for i in range(W+2):
    Y.append('#')
    
Z = [Y]
for i in range(H):
    tmp = str(input())
    X = ['#']
    X.append(tmp)
    X.append('#')
    Z.append(X)

Z.append(Y)
for i in range(H + 2):
    print(''.join(Z[i]))



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

struct test {
  string name;
  int point;
  int index;

  bool operator<( const test& right ) const {
    return name == right.name ? point > right.point : name < right.name;
  }
};

int main() {
  int N;
  cin >> N;
  vector<test> T(N);
  for (int i = 0; i < N; i++) {
    cin >> T[i].name >> T[i].point;
    T[i].index = i + 1;
  }

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

  for (int i = 0; i < N; i++) {
    cout << T[i].index << endl;
  }
}


Measured memory_bytes: 256
N, M = map(int, input().split())
mod = 10**9+7
# コンビネーションクラスの作成


class Data():
    def __init__(self):
        self.power = 1
        self.rev = 1


class Combi():
    def __init__(self, N, mod):
        self.lists = [Data() for _ in range(N+1)]
        self.mod = mod
        for i in range(2, N+1):
            self.lists[i].power = ((self.lists[i-1].power)*i) % self.mod
        self.lists[N].rev = pow(self.lists[N].power, self.mod-2, self.mod)
        for j in range(N, 0, -1):
            self.lists[j-1].rev = ((self.lists[j].rev)*j) % self.mod

    def combi(self, K, R):
        if K < R:
            return 0
        else:
            return ((self.lists[K].power)*(self.lists[K-R].rev)*(self.lists[R].rev)) % self.mod


c = Combi(10**6, mod)
ans = (c.lists[M].power*c.lists[M-N].rev)**2 % mod
for k in range(1, N+1):
    s = (-1)**((k-1) % 2)
    t = c.combi(N, k)
    u=((c.lists[M-k].power*c.lists[M-N].rev)**2) % mod
    v=(c.lists[M].power*c.lists[M-k].rev) % mod
    ans -= s*t*u*v
print(ans % mod)

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

int main() {
    string str[3];
    for(int i = 0; i < 3; i++) {
        cin >> str[i];
    }
    cout << str[0][0] << str[1][1] << str[2][2] << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
R, C, K = list(map(int, input().split()))

d = [[[0] * (C+1) for _ in range(R+1)] for _ in range(4)]
t = [[0] * (C+1) for _ in range(R+1)]

for i in range(K):
    r,c,v = list(map(int, input().split()))
    t[r][c] = v

for i in range(R+1):
    for j in range(C+1):
        for k in range(4):
            if i!=0:
                d[0][i][j] = max(d[0][i][j], d[k][i-1][j])
                d[1][i][j] = max(d[1][i][j], d[k][i-1][j] + t[i][j])

            if j!=0:
                d[k][i][j] = max(d[k][i][j], d[k][i][j-1])
                if k != 0:
                    d[k][i][j] = max(d[k][i][j], d[k-1][i][j-1] + t[i][j])

a = 0
for i in range(4):
    a = max(a, d[i][-1][-1])
print(a)


Measured memory_bytes: 431080
#include <algorithm>
#include <bitset>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <cctype>
#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <ctime>
#include <deque>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <list>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll=long long;
using ld=long double;
//#define int long long
//#define _CRT_SECURE_NO_WARNINGS
#define rep(i, n) for (int i = 0; i < n; i++)
#define _GLIBCXX_DEBUG
const int MOD = 1e9 + 7;
const int INF = 1e18 + 9;
constexpr long double pi = 3.141592653589793238462643383279;
int fact(int i) {
    if (i == 0) return 1;
    return (fact(i - 1)) * i;
}
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}
int lcm(int a, int b) {
    return a * b / gcd(a, b);
}
int keta(int n) {
    if (n == 0) return 1;
    int count = 0;
    while (n != 0) {
        n /= 10;
        count++;
    }
    return count;
}
int ketasum(int n) {
    int sum = 0;
    while (n != 0) {
        sum += n % 10;
        n /= 10;
    }
    return sum;
}
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
int a, b, x;
int main(void){
    cin >> a >> b >> x;
    if (x >= a && x <= (a + b))cout << "YES" << endl;
    else cout << "NO"<< endl;
    return 0;
}

Measured memory_bytes: 3648
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

int main ()
{
	int n;
	cin >> n;
	vector<pair<int, int>> v;

	for (int i=0; i<n; ++i)
	{
		int x;
		cin >> x;
		v.push_back(make_pair(i, x));
	}

	sort(v.begin(), v.end(), [](pair<int, int> x, pair<int, int> y) { return x.second < y.second; });

	//        m
	//     1 [2] 3
	//  0    [2] 3
	//  0 [1]    3
	//  0 [1] 2   

	vector<int> ans(n);
	int m = n >> 1;
	for (int i=0; i<n; ++i)
	{
		if (i < m)
		{
			ans[v[i].first] = v[m].second;
		}
		else
		{
			ans[v[i].first] = v[m-1].second;
		}
	}

	for (auto a : ans)
	{
		cout << a << endl;
	}
	return 0;
}

Measured memory_bytes: 4848
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,r;
cin>>n>>r;
if(n>=1&&n<=100&&r>=0&&r<=4111){
    if(n>=10)
        cout<<r<<endl;
    else
        cout<<(r+100*(10-n))<<endl;
}


return 0;}


Measured memory_bytes: 3632
#include <bits/stdc++.h>
#define REP(i, n) REPI(i, 0, n)
#define REPI(i, a, b) for (int i = (int)(a) ; i < (int)(b) ; i++)

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


using ll = long long;
using namespace std;

int main()
{
    int K, A, B;
    cin >> K;
    cin >> A >> B;
    for (A; A <= B ; A++)
    {
        if (A % K == 0)
        {
            cout << "OK" << endl;
            break;
        }
    }
    if (A > B)
    {
        cout << "NG" << endl;
    }
    return 0;
}


Measured memory_bytes: 3636
import java.util.Scanner;

public class Main
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		
		for(; ;)
		{
			double x = scanner.nextDouble();
			double h = scanner.nextDouble();
			if(x==0 && h==0)
			{
				break;
			}
			
			System.out.println(String.format("%1$.6f", x*(x + 2*Math.sqrt((x*x)/4 + h*h))));
		}
	}
}

Measured memory_bytes: 28172
# coding: utf-8

import sys
import math
import collections
import itertools
INF = 10 ** 13
MOD = 10 ** 9 + 7
def input() : return sys.stdin.readline().strip()
def lcm(x, y) : return (x * y) // math.gcd(x, y)
def I() : return int(input())
def LI() : return [int(x) for x in input().split()]
def RI(N) : return [int(input()) for _ in range(N)]
def LRI(N) : return [[int(x) for x in input().split()] for _ in range(N)]
def LS() : return input().split()
def RS(N) : return [input() for _ in range(N)]
def LRS(N) : return [input().split() for _ in range(N)]
def PL(L) : print(*L, sep="\n")
def YesNo(B) : print("Yes" if B else "No")
def YESNO(B) : print("YES" if B else "NO")

N = I()
A = LI()

A = sorted([[a, i] for i, a in enumerate(A)], reverse=True, key=lambda x : x[0])

dp = [[0] * (N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N-i):
        dp[i+1][j] = max(dp[i+1][j], dp[i][j] + A[i+j][0] * (A[i+j][1] - i))
        dp[i][j+1] = max(dp[i][j+1], dp[i][j] + A[i+j][0] * ((N-j-1) - A[i+j][1]))

res = 0
for i in range(N):
    res = max(res, dp[i][N-i])

print(res)


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

//#define int long long
typedef long long ll;
#define double long double
#define vec vector
#define pb push_back
#define unset unordered_set
#define ii pair<int, int>
#define X first
#define Y second
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define FORE(i, a, b) for(int i = (a); i <= (b); i++)
#define FORD(i, a, b) for(int i = (a); i >= (b); i--)
#define bitcount(n) __builtin_popcountll(n)
typedef vector<int> vi;
template <typename T,typename U>
std::pair<T,U> operator+(const std::pair<T,U> & l,const std::pair<T,U> & r) {
  return {l.first+r.first,l.second+r.second};
} 
typedef void (*callback_function)(void); // type for conciseness
const long long ZERO = 0LL;
const long long INF64 = 1e18;
const int INF32 = 1e9;
const int MOD = 1e9 + 7;
const double PI = acos(-1.0L);
const double EPS = static_cast<double>(1e-9);
#define min(a, b) (((a)<(b))?(a):(b))
#define max(a, b) (((a)>(b))?(a):(b))

ll powMod(ll a, ll m) { // a^m % MOD
	a %= MOD;
	long long res = 1;
	while (m > 0) {
		if (m & 1)
			res = res * a % MOD;
		a = a * a % MOD;
		m >>= 1;
	}
	return res;
}

const int maxV = 10; // we need inv(3) only
ll inv[maxV];
ll inverse(int q) { // q<maxV; WORKs only with MOD prime!
	inv[1] = 1LL;
	for(int i = 2; i < maxV; ++i)
	    inv[i] = (MOD - (MOD/i) * inv[MOD%i] % MOD) % MOD;
	return inv[q];
}




//#undef int
int main() {
//#define int long long
	ios_base::sync_with_stdio(false); cin.tie();
	//auto beginProgram = chrono::steady_clock::now();
//	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);

	int a, b, c; cin >> a >> b >> c;
	if(c < max(a, b) && c > min(a, b))
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
	
  //auto endProgram = chrono::steady_clock::now();
  return 0;
}


Measured memory_bytes: 256
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

from collections import Counter

n = ni()
d = list(li())

m = ni()
t = list(li())

dcnt = Counter(d)
tcnt = Counter(t)

exist = True

for tkey, tval in tcnt.items():
    if tval > dcnt[tkey]:
        exist = False
        
print("YES" if exist else "NO")

Measured memory_bytes: 57312
# B
N = int(input())
T, A = list(map(int, input().split()))
H = list(map(int, input().split()))

m = 10**5+1
m_index = -1
for i in range(N):
    H[i] = abs(A - (T - H[i]*0.006))
    if m > H[i]:
        m = H[i]
        m_index = i
        
print(m_index + 1)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef map<int,int> mii;
typedef map<ll,ll> mll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll>   vl;
#define f(i,n)  for(i=0;i<n;i++)
#define f1(i,n)  for(i=1;i<n;i++)
#define fr(i,n) for(i=n-1;i>=0;i--)
#define em emplace_back
#define mp make_pair
#define in insert
#define fi first
#define sc second
#define b begin
#define e end
#define er erase
#define l length
#define c clear
#define si size
#define fastio ios_base::sync_with_stdio(false);cin.tie(0);
const double pi=3.141592653;
const ll infi=1000000001;
const ll MOD=1000000007;
const ll mod=998244353;
const string no="NO\n",yes="YES\n";

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

// ll con(vl v[],ll hai[],ll sz){
//     ll count=0;
//     for(int i=1;i<sz;i++){
//         if(hai[i]==0){
//             count++;
//             dfs(v,i,hai);
//         }
//     }
    // return count;
// }

// void gcde(int a,int b,int *x,int *y){
//     if(a==0){
//         *x=0;
//         *y=1;
//         return;
//     }    
//     int x1,y1;
//     gcde(b%a,a,&x1,&y1);
    
//     *x=y1-(b/a)*x1;
//     *y=x1;
// }


// ll recur(vl v,ll in,ll m,ll n){
//     if(in==-1)  return 1000000000001;
//     ll d,e,c;
//     d=max(m/v[in],n*v[in]);
//     c=recur(v,in-1,m/v[in],n*v[in]);
//     e=recur(v,in-1,m,n);
//     return min(c,min(e,d));
// }

// ll bexpo(ll a,ll p){
//     ll x=1;
//     while(p){
//     if(p&1){
//         x=(x*a)%mod;
//     }
//     a=(a*a)%mod;
//     p>>=1;
//     }
//     return x;
// }
// ll fact[500001],invf[500001];
// int dx[8]{-1,0,0,1,-1,-1,1,1};
// int dy[8]{0,-1,1,0,-1,1,-1,1};
// ll dp[200001];
int l=0;
 void dfs(vi v[],int node,int hai[]){
    hai[node]=1;
    l++;
    for(auto i:v[node]){
        if(hai[i]==0){
            dfs(v,i,hai);
        }
    }
}

int main() {
    fastio
    int n,m,a,b,i,j;
    cin>>n>>m;
    vector<int> v[n+1];
    f(i,m){
        cin>>a>>b;
        v[a].em(b);
        v[b].em(a);
    }
    int vis[n+1]{};
    int ans=0;
    f1(i,n+1){
        if(vis[i]==0){
            dfs(v,i,vis);
            ans=max(ans,l);
            l=0;
        }
    }
    cout<<ans;

	return 0;
}

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

int main() {
  string s;

  while(cin >> s) {
    int I = 0, J = 0;

    for(int i = 0; i < s.size()-2; i++) {
      if(s.substr(i, 3) == "JOI") I++;
      if(s.substr(i, 3) == "IOI") J++;
    }

    cout << I << endl;
    cout << J << endl;
  }
}

Measured memory_bytes: 1212
#include<stdio.h>
int main()
{
	char s[100000];
	int n,i,p;
	while(~scanf("%d",&n))
	{
		p=0;
		scanf("%s",s);
		for(i=0;i<n;i++)
		{
			if(s[i]!=s[i+1])
			p++;
			else
			continue;
		}
		printf("%d\n",p);
	}
	return 0;
}

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

using namespace std;
typedef long long ll;

int N = 26;
int D;
ll c[26];
ll s[366][36];
int t[366];

void input(){
    cin >> D;
    for(int i = 0; i < N; i++) cin >> c[i];
    for(int i = 1; i <= D; i++){
        for(int j = 0; j < N; j++) cin >> s[i][j];
    }
    for(int i = 1; i <= D; i++) {
        cin >> t[i];
        t[i]--;
    }
}

ll calc_score(){
    vector<int> last(N);
    ll S = 0;
    for(int d = 1; d <= D; d++){
        last[t[d]]  = d;
        for(int i = 0; i < N; i++){
            S -= c[i]*(d-last[i]);
        }
        S += s[d][t[d]];
        cout << S << endl;
    }
    return max(1000000+S, (ll)0);
}

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

Measured memory_bytes: 3748
N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(2001 * N + 10)] for _ in range(N + 2) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 1000):
      	
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)


Measured memory_bytes: 304192
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );
using namespace std;
using ll = long long;
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 ll INF = 1e9;
const ll MOD = 1e9 + 7;


struct UnionFind {
    vector<int> par;
    vector<int> sizes;
    vector<int> maxs;
    vector<int> mins;

    UnionFind(int n) :
            par(n), sizes(n, 1), maxs(n), mins(n) {
        rep(i, n) par[i] = i;
        rep(i, n) maxs[i] = i;
        rep(i, n) mins[i] = i;
    }

    int root(int x) {
        if (x == par[x]) return x;
        else return par[x] = root(par[x]);
    }

    bool merge(int x, int y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (sizes[x] < sizes[y]) swap(x, y);
        par[y] = x;
        maxs[x] = max(maxs[y], maxs[x]);
        mins[x] = min(mins[y], mins[x]);
        sizes[x] += sizes[y];
        return true;
    }

    bool same(int x, int y) {
        return root(x) == root(y);
    }

    int size(int x) {
        return sizes[root(x)];
    }

    int getMax(int x) {
        return maxs[root(x)];
    }

    int getMin(int x) {
        return mins[root(x)];
    }

};


int main(){
    int n;
    cin >> n;
    using P = pair<int, int>;
    vector<P> x(n), y(n);
    rep(i, n){
        cin >> x[i].first >> y[i].first;
        x[i].second = i;
        y[i].second = i;
    }

    sort(all(x));
    sort(all(y));

    using edge = tuple<int, int, int>;
    priority_queue<edge, vector<edge>, greater<edge>> que;
    rep(i, n-1){
        que.push(edge{x[i+1].first-x[i].first, x[i].second, x[i+1].second});
        que.push(edge{y[i+1].first-y[i].first, y[i].second, y[i+1].second});
    }

    int ans = 0;
    UnionFind uf(n);
    while(que.size() != 0){
        int cost, u, v;
        tie(cost, u, v) = que.top();
        que.pop();
        if(uf.merge(u, v)) ans += cost;
    }

    cout << ans << endl;
}

Measured memory_bytes: 6516
mod=10**9+7
N=10**4
g1=[1,1]
g2=[1,1]
inverse=[0,1]

for i in range(2,N+1):
    g1.append((g1[-1]*i)%mod)
    inverse.append((-inverse[mod%i]*(mod//i))%mod)
    g2.append((g2[-1]*inverse[-1])%mod)

def cmb(n,r):
    if (r<0 or r>n):
        return 0
    r=min(r,n-r)
    return g1[n]*g2[r]*g2[n-r]%mod


n,k=map(int,input().split())
for i in range(1,k+1):
    if i>n-k+1:
        print(0)
    else:
        print(cmb(n-k+1,i)*cmb(k-1,i-1)%mod)

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

int main() {
  int N, M;
  cin >> N >> M;
  vector<int> s(M), c(M);
  for (int i = 0; i < M; ++i)
    cin >> s[i] >> c[i];

  string n;
  for (int i = 0; i < N; ++i)
    n += '0';
  int ans = -1;
  for (int i = 0; i < 1000 && ans == -1; ++i) {
    n = to_string(i);
    if (n.size() != N)
      continue;

    bool flag = true;
    for (int j = 0; j < M; ++j)
      if (n[s[j] - 1] != c[j] + '0')
        flag = false;

    if (flag)
      ans = i;
  }

  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define GET_MACRO(_1, _2, _3, NAME, ...) NAME
#define _repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define _rep(i,n) _repl(i,0,n)
#define rep(...) GET_MACRO(__VA_ARGS__, _repl, _rep)(__VA_ARGS__)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream &o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream &o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000

vector<int> zAlgorithm(const vector<int> &s){
  int n = s.size();
  vector<int> a(n+1,0);
  int i=1, j=0;
  while(i<n){
    while(i+j<n && s[j] == s[i+j]) j++;
    a[i] = j;
    if(j==0){i++; continue;}
    int k = 1;
    while(i+k<n && k+a[k]<j) a[i+k]=a[k], k++;
    i += k;
    j -= k;
  }
  return a;
}

int main(){
  int n;
  cin>>n;
  vector<int> vec(n);
  rep(i,n) scanf("%d", &vec[i]);

  vector<int> v = zAlgorithm(vec);

  rep(i,1,n) if(n%i==0){
    if(v[i] == n-i){
      cout << n/i << endl;
      return 0;
    }
  }

  cout << 1 << endl;

  return 0;
}

Measured memory_bytes: 4460
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int n,x;
    cin >> n >> x;
    int sum = 0;
    int ans = 1;
    for(int i = 0;i < n;i++){
        int a;
        cin >> a;
        sum += a;
        if(sum <= x){
            ans++;
        }
    }
    
    cout << ans << endl;
    
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;

int main() {
	int N, K; cin >> N >> K;

	if (K == 1) {
		cout << 0 << endl; return 0;
	}
	N -= K;
	cout << N << endl;
	return 0;
}


Measured memory_bytes: 256
import sys
from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt, ceil, floor
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
sys.setrecursionlimit(10**7)

# 4近傍（右, 下, 左, 上）
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]


def inside(y: int, x: int, H: int, W: int) -> bool: return 0 <= y < H and 0 <= x < W


def main():
    X, Y = input().split()
    if X == Y:
        print("=")
    else:
        print("<" if X < Y else ">")


if __name__ == '__main__':
    main()


Measured memory_bytes: 3896
import sys
import math
from collections import deque
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N, A, B = IL()

if (B - A)%2 == 0:
  print((B - A)//2)
else:
  ans = min(A - 1, N - B)
  print(ans + (B - A)//2 + 1)

Measured memory_bytes: 38384
n = int(input())
x = "abcdefghijklmnopqrstuvwxyz"
s = ""
while True:
  if n%26 == 0:
    s = "z"+s
    n -= 26
    n =n//26
  else:
    s = x[n%26-1]+s
    n = n//26
  if n==0:
    break
print(s)

Measured memory_bytes: 61756
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <string>
#include <cmath>
#include <utility>


using namespace std;

int main(void){

	int n;

	cin >> n;

	vector<int> a(0);
	map<int, int> mp;

	int t;
	for (int i = 0; i < n; i++){
		cin >> t;
		if (mp.find(t) != mp.end()){
			mp[t]++;
		}
		else {
			mp[t]++;
			a.push_back(t);
		}
	}

	int num = 0;
	for (int i = 0; i < a.size(); i++){
		if (mp[a[i]] >= a[i]){
			num += mp[a[i]] - a[i];
		}
		else
			num += mp[a[i]];
	}

	cout << num << endl;

	return 0;	
}

Measured memory_bytes: 5112