akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef unsigned long long ULL;

int makePrime(int *prime, int max);
int main(){
    int N;
    int *prime;
    int *count,*sum;
    int prime_num;
    ULL i,j,k;
    int max;
    size_t size;
    ULL ans;

    scanf("%d",&N);
    max = 0;

    prime = (int*)calloc(N/2 + 2, sizeof(int));
    prime_num = makePrime(prime,N);
    count = (int*)calloc(N+1,sizeof(int));
    sum = (int*)calloc(N+1,sizeof(int));
    size = N + 1;
    int counter;
    /*
    printf("%d\n",size);
    printf("%X %X\n",count,sum);
    printf("%d %d\n",sizeof(count),sizeof(sum));
    printf("%d %d\n",sizeof(count)/sizeof(int),sizeof(sum)/sizeof(int));
    printf("%d\n",N);
    */
    for(i = 1; i <= N;i++){
        sum[i] = 1;
    }
    for(i=0; i<prime_num; i++){
        counter  = 1;
        for( j=prime[i]; j <= N; j *= prime[i]){
            for( k = j; k <= N; k += j){
                count[k] = counter;
            }
            counter++;
        }
        //printf("%dの数\n",prime[i]);
        for(j=prime[i]; j <= N; j += prime[i]){
            //printf("%d:%d\n",j,count[j]);
            sum[j] *= count[j] + 1;
        }
        //printf("\n");
    }
    ans = 1;
    for(i=2;i<=N;i++){
        ans += i * sum[i];
    }
    free(count);
    free(sum);
    printf("%llu\n",ans);
}
int  makePrime(int *prime, int max){
    int i,j;
    char *num;
    prime[0] = 2;
    int prime_num = 1;
    
    
    num = (char*)calloc(max+1,sizeof(char));
    for(i=0;i<=max;i++){
        num[i] = 0;
    }
    j=3;
    while(j <= max){
        //printf("%d\n",j);
        for(i = prime[prime_num-1] + prime[prime_num-1]; i <= max; i+=prime[prime_num-1]){
            num[i] = -1;
        }
        for(;j<=max;j+=2){
            if( num[j] != -1 ){
                prime[prime_num++] = j;
                j+=2;
                break;
            }
        }
        
    }
    free(num);
    return prime_num;
}


Measured memory_bytes: 81956
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String S = br.readLine();
        String T = br.readLine();
        String actualString = T.substring(0,T.length()-1);
        if(S.equals(actualString)){
            System.out.println("Yes");
        }
        else{
            System.out.println("No");
        }
    }
}


Measured memory_bytes: 32516
// while( !(succeed == try()) );

#include "bits/stdc++.h"
using namespace std;

// Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha


#define int long long int
#define loop(i,s,e) for(int i=s; i<e; i++)
#define endl '\n'
#define vii vector<int>
#define pii pair<int, int>
#define ff first
#define ss second
#define N 100001
#define pb push_back
#define INF LLONG_MAX
#define inf INT_MAX

void INP();

#define bug(...)        __f (#__VA_ARGS__, __VA_ARGS__)
#define rtn                                       if(0)return;
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { rtn cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{     rtn 
     const char* comma = strchr (names + 1, ',');
     cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}

// Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha // Alpha

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

void alpha()
{	
	int k;
	cin>>k;

	int sum = 0;

	loop(i,1,k+1){
		loop(j,1,k+1){
			loop(l,1,k+1){
				int t = gcd(i, j);
				int temp = gcd(t, l);
				sum+=temp;
			}
		}
	}
	

	cout<<sum;
}

int32_t main(){

	ios_base:: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	//INP();
    int t=1;
	//cin>>t;

  	while(t--) alpha();

	return 0;

}






















inline void INP()
{
      #ifndef ONLINE_JUDGE
          freopen("input.txt",  "r",  stdin);
          freopen("output.txt", "w", stdout);
      #endif
}
 
 

Measured memory_bytes: 3652
from collections import deque


k = int(input())

queue = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])

for _ in range(k):
    num = queue.popleft()
    a = num // 10
    b = num % 10

    if b != 0:
        queue.append(num*10 + b-1)

    queue.append(num*10 + b)
    
    if b != 9:
        queue.append(num*10 + b+1)

print(num)


Measured memory_bytes: 11964
#include<iostream>
#include <cstdio>
#include<cmath>
#include<vector>
#include<algorithm>

using namespace std;

////Nayeem Shahriar Joy,Applied Physics &Electronic Engineering,University of Rajshahi.

int main()

{
   vector<int>l;
   int a;
   for(int i=0;i<10;i++)

   {
       cin>>a;
       l.push_back(a);
   }
   sort(l.begin(),l.end());
   cout<<l[9]<<endl;
   cout<<l[8]<<endl;
   cout<<l[7]<<endl;
   return 0;
}

Measured memory_bytes: 3136
#include <set>
#include <map>
#include <list>
#include <stack>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <vector>
#include <string>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <utility>
#include <numeric>
#include <complex>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <cassert>
#include <iostream>
#include <iterator>
#include <algorithm>
using namespace std;

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

	int max_val = 0;

	for(int i = 0; i < N; ++i){
		int cnt = 0;
		for(int j = 0; j < N; ++j){
			if(s[i] == s[j]){
					cnt++;
			}			
		}
		for(int k = 0; k < M; ++k){
			if(s[i] == t[k]){
				cnt--;
			}
		}
		max_val = max(max_val, cnt);
	}

	cout << max_val << endl;

	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Math;
using MethodImplAttribute = System.Runtime.CompilerServices.MethodImplAttribute;
using MethodImplOptions = System.Runtime.CompilerServices.MethodImplOptions;
using LayoutKind = System.Runtime.InteropServices.LayoutKind;
using StructLayoutAttribute = System.Runtime.InteropServices.StructLayoutAttribute;
using FieldOffsetAttribute = System.Runtime.InteropServices.FieldOffsetAttribute;

class P
{
    static void Main()
    {
        var nk = Console.ReadLine().Split().Select(int.Parse).ToList();
        var d = Console.ReadLine().Split();
        while (true)
        {
            if(d.All(x => !nk[0].ToString().Contains(x)))
            {
                Console.WriteLine(nk[0]);
                return;
            }
            nk[0]++;
        }
    }
}


class PartialPersistentUnionFind
{
    public int Now { get; private set; }
    public int Size { get; private set; }
    int[] Parents;
    int[] Time;
    int[] Sizes;
    List<Tuple<int, int>>[] SizeHistories;

    public PartialPersistentUnionFind(int size)
    {
        Size = size;
        Parents = Enumerable.Range(0, Size).ToArray();
        Time = Enumerable.Repeat(int.MaxValue, Size).ToArray();
        Sizes = Enumerable.Repeat(1, Size).ToArray();
        SizeHistories = Enumerable.Repeat(0, Size).Select(_ => new List<Tuple<int, int>>() { new Tuple<int, int>(0, 1) }).ToArray();
    }

    public bool TryUnite(int x, int y)
    {
        Now++;
        x = Find(x);
        y = Find(y);
        if (x == y) return false;
        if (Sizes[x] < Sizes[y])
        {
            var tmp = x;
            x = y;
            y = tmp;
        }
        Parents[y] = x;
        Time[y] = Now;
        Sizes[x] += Sizes[y];
        SizeHistories[x].Add(new Tuple<int, int>(Now, Sizes[x]));
        return true;
    }
    public int Find(int i, int t = int.MaxValue - 1) => Time[i] <= t ? Find(Parents[i], t) : i;
    public int GetSize(int i, int t = int.MaxValue - 1)
    {
        var root = Find(i, t);
        return SizeHistories[root][~SizeHistories[root].BinarySearch(new Tuple<int, int>(t, int.MaxValue)) - 1].Item2;
    }
}

Measured memory_bytes: 15428
#include <iostream>
#include <vector>
#include <queue>
#include <map>
using namespace std;

typedef pair<long long, int> P;

struct edg{
    int p, q, c;
    edg(int p, int q, int c) : p(p), q(q), c(c){}
};

struct edge{
    int to;
    int cost;
    edge(int to, int cost) : to(to), cost(cost){}
};
struct D{
    vector< vector<edge> > graph;
    vector< long long > dist;

    void init(int size){
        dist.assign(size, 1e18);
        graph.assign(size, vector<edge>() );
    }

    void add_edge(int from, int to, int cost){
        graph[from].push_back(edge(to, cost));
    }

    void dijkstra(int from){
        priority_queue<P, vector<P>, greater<P> > q;
        dist[from] = 0;
        q.push(P(0, from));
        while(!q.empty()){
            P p = q.top();
            q.pop();
            int v = p.second;
            if(dist[v] < p.first)continue;
            for(int i = 0; i < graph[v].size(); i++){
                edge e = graph[v][i];
                if(dist[e.to] > dist[v] + e.cost){
                    dist[e.to] = dist[v] + e.cost;
                    q.push(P(dist[e.to], e.to));
                }
            }
        }
    }
};
int main(void){
    int n, m, cnt = 0;
    vector<edg> e;
    map<P, int> v;
    cin >> n >> m;
    for(int i=0;i<n;i++){
        v[P(i, 0)] = cnt++;
    }
    for(int i=0;i<m;i++){
        int p, q, c;
        cin >> p >> q >> c;
        p--;
        q--;
        e.push_back(edg(p, q, c));

        if(v.find(P(p, c)) == v.end()){
            v[P(p, c)] = cnt++;
        }
        if(v.find(P(q, c)) == v.end()){
            v[P(q, c)] = cnt++;
        }
    }

    D d;
    d.init(cnt);

    for(auto x: v){
        int p = x.first.first;
        int c = x.first.second;
        int s = x.second;
        int t = v[P(p, 0)];
        d.add_edge(s, t, 0);
        d.add_edge(t, s, 1);
    }

    for(int i=0;i<m;i++){
        int p = e[i].p;
        int q = e[i].q;
        int c = e[i].c;
        int s = v[P(p, c)];
        int t = v[P(q, c)];
        d.add_edge(s, t, 0);
        d.add_edge(t, s, 0);
    }

    d.dijkstra(v[P(0, 0)]);
    long long ans = d.dist[v[P(n-1, 0)]];
    if(ans > n) ans = -1;
    cout << ans << endl;
}


Measured memory_bytes: 76848
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

void finish() {
    cout << -1 << endl;
    exit(0);
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    int cnt[3] = {};
    for (auto c : s) cnt[(int) (c - 'a')]++;
    sort(cnt, cnt + 3);
    YES((cnt[0] == cnt[1] && cnt[1] == cnt[2])
            || (cnt[0] == cnt[1] && cnt[1] == cnt[2] - 1)
            || (cnt[0] == cnt[1] - 1 && cnt[1] == cnt[2]));
    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N,M,P;
    cin>>N>>M>>P;
    vector<vector<pair<int,int>>> graph(N);
    vector<vector<int>> graph2(N);
    for(int i=0;i<M;i++){
        int A,B,C;
        cin>>A>>B>>C;
        A--;
        B--;
        C=C-P;
        graph[A].push_back(make_pair(B,C));
        graph2[B].push_back(A);
    }
    vector<bool> visited(N,0);
    visited[N-1]=1;
    queue<int> q;
    q.push(N-1);
    while(!q.empty()){
        int curr=q.front();
        q.pop();
        for(int i=0;i<graph2[curr].size();i++){
            int temp=graph2[curr][i];
            if(!visited[temp]){
                visited[temp]=1;
                q.push(temp);
            }
        }
    }
    //bellman ford
    vector<int> dist(N,INT_MIN);
    dist[0]=0;
    vector<bool> visit(N,0);
    visit[0]=1;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            if(dist[j]==INT_MIN){
                continue;
            }
            for(int k=0;k<graph[j].size();k++){
                int next=graph[j][k].first;
                int val=graph[j][k].second;
                visit[next]=1;
                if(dist[next]<dist[j]+val){
                    dist[next]=dist[j]+val;
                }
                
            }
        }
    }
    for(int i=0;i<N;i++){
        for(int j=0;j<graph[i].size();j++){
            int k=graph[i][j].first;
            if(dist[i]==INT_MIN||dist[k]==INT_MIN){
                continue;
            }
            if(dist[k]<dist[i]+graph[i][j].second&&visited[k]){
                cout<<-1<<endl;
                return 0;
            }
            
        }
    }
    cout<<max(0,dist[N-1])<<endl;
    return 0;
    
    
    
}

Measured memory_bytes: 512
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> d(N);
  for(int i=0;i<N;i++){
    cin >> d[i];
  }
  sort(d.begin(),d.end());
  int x=0;
  for(int i=1;i<N;i++){
    if(d[i]>d[i-1]){
      x++;
    }
  }
  cout << x+1 << endl;
}
  

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef long long int ll;
ll max(ll a, ll b){
    return a > b? a : b;
}
bool comp(pair<ll,ll>p1, pair<ll, ll>p2)
{
    if(p1.ff > p2.ff)
        return true;
    if(p1.ff == p2.ff)
        return p1.ss > p2.ss;
    return false;
}
int main()
{
    ll n, m;
    cin >> n >> m;
    ll a[n] = {0};
    for(int i = 0; i < n; i++)
        cin >> a[i];
    sort(a, a + n);
    vector<pair<ll, ll> >v(m);
    for(int i = 0; i < m ;i++)
        cin >> v[i].ss >> v[i].ff;
    sort(v.begin(), v.end(), comp);
    // for(auto it : v)
    //     cout << it.ff << " " << it.ss << endl;
    ll sum = 0; 
    ll x = 0;
    for(int i = 0; i < n ;i++)
    {
        if(x >= m)
            sum += a[i];
        else
        {
            sum += max(a[i], v[x].ff);
            v[x].ss--;
            if(v[x].ss == 0)
                x++;
        }
  
    }
    cout << sum << endl;


    return 0;
}

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

using namespace std;
const int IINF = INT_MAX;
using ll = long long;
using P = pair<int,int>;
#define INF 100000000

int main(){
    int res;
    cin >> res;
    
    int a = res%10;
    
    if(a==3)  cout << "bon" << endl;
    else if(a==0 || a== 1 || a== 6 || a== 8) cout << "pon" << endl;
    else cout << "hon" << endl;
    
    return 0;	
}

Measured memory_bytes: 3624
import java.util.*;
import java.io.*;

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

        while(true) {
            int H = Integer.parseInt(sc.next());
            int W = Integer.parseInt(sc.next());
            if (H == 0 && W == 0) {
                break;
            }
            for (int i = 0; i < H; i++) {
                String S = "";
                for (int j = 0; j < W; j++) {
                    if ((i + j) % 2 == 0) {
                        S += "#";
                    } else {
                        S += ".";
                    }
                }
                out.printf("%s\n", S);
            }
            out.printf("\n");
        }
        out.flush();
    }
}


Measured memory_bytes: 55068
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
long Ri[202020];
long dp[202020];

int N;
pair<long, long> XD [202020];

int turnon (int i, long maxX)
{
	if (N == i + 1)
	{
		//ほかと相互作用しない場合はiを返す。
		return i;
	}
	if (XD[Ri[i+1]].first < maxX)
		return turnon (Ri[i+1], max (maxX, XD[Ri[i+1]].second));
	else
		if (XD[i+1].first < maxX)
			return Ri[i+1];
	return i;
}
int main(void)
{
	cin >> N;
	dp[N]=1;
	const long mod = 998244353;

	for (int i = 0; i < N; i++)
	{
		//e.resize (2);
		cin >> XD [i].first >> XD [i].second;
		XD [i].second += XD [i].first;
	}
	sort (XD, XD + N);
	
	for (int i = N-1; i >= 0; i--)
	{
		int Deleted = turnon (i, XD[i].second);
		Ri[i] = Deleted; //消去されるブロックの最大値
	}
	
	for (int i = N-1; i >=0;  i--)
		dp[i] = (dp[i+1] + dp[Ri[i]+1]) % mod;
		
	cout << dp [0] <<endl;
	return 0;
}

Measured memory_bytes: 6528
i,n,x,X,d;int gcd(int a,int b){if(a%b==0)return b;return(gcd(b,a%b));}main(){scanf("%d%d",&n,&X);for(i=0;i<n;i++){scanf("%d",&x);if(!i)d=abs(X-x);else d=gcd(d,abs(X-x));}printf("%d",d);}

Measured memory_bytes: 128
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll MOD = 1e9 + 7;

int main() {
	ll N, K;
	cin >> N >> K;
	vector<ll> A(N);
	for (int i = 0; i < N; i++) {
		cin >> A[i];
		A[i]--;
		A[i] %= K;
	}
	vector<ll> sum(N + 1);
	sum[0] = 0;
	for (int i = 0; i < N; i++) {
		sum[i + 1] = (sum[i] + A[i]) % K;
	}
	map<ll, int> cnt;
	cnt[sum[N]]++;
	ll ans = 0;
	for (int i = N - 1; i >= 0; i--) {
		if (i + K <= N) {
			cnt[sum[i + K]]--;
		}
		ans += cnt[sum[i]];
		cnt[sum[i]]++;
	}
	cout << ans << endl;
}


Measured memory_bytes: 15872
#include <iostream>
#include <stdio.h>
#include <vector>
#include <set>
#include <string.h>
using namespace std;

int main()
{
  int n = 0;
  scanf("%d", &n);
  int m = n+1;
  int mm = m*m;
  int i0 = 0;
  int j0 = 0;
  int k0 = 0;
  int value = -1;
  for(int i=0; i<n; i++){
    scanf("%d", &value);
    if(value == 1){
      i0 += 1;
    }else if(value == 2){
      j0 += 1;
    }else if(value == 3){
      k0 += 1;
    }
  }
  double p0 = 0;
  double p1 = 0;
  double p2 = 0;
  double p3 = 0;
  double denom = 0;
  vector<double> arr(m*m*m, 0);
  for(int k=0; k<m; k++){
    for(int j=0; j<m-k; j++){
      for(int i=0; i<m-j-k; i++){
        denom = i + j + k;
        p0 = 1. * (denom) / n;
        if(p0 > 0){
          arr[i*mm + j*m + k] = 1. / p0 - 1;
        }
        p1 = 1.* i / denom;
        p2 = 1.* j / denom;
        p3 = 1.* k / denom;
        if(i>0){
          arr[i*mm + j*m + k] += p1 * (arr[(i-1)*mm + j*m + k] + 1);
        }
        if(j>0){
          arr[i*mm + j*m + k] += p2 * (arr[(i+1)*mm + (j-1)*m + k] + 1);
        }
        if(k>0){
          arr[i*mm + j*m + k] += p3 * (arr[i*mm + (j+1)*m + k-1] + 1);
        }
      }
    }
  }
  printf("%.10lf\n", arr[i0*mm + j0*m + k0]);
}


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

typedef long long ll;
#define int         ll
typedef vector<int> vi;
#define test        int t; cin >> t; while(t--)
#define max(a,b)   (a>b?a:b)
#define min(a,b)   (a<b?a:b)
const int mod = 1000000007;



int div(int n) {
    int re = 0;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            re += 2;
            if (n / i == i) {
                re--;
            }
        }

    }
    return re;
}

int32_t main() {

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    if(n==2){
        cout<<1;
        return 0;
    }
    int ans=2;

    for (int i = 2; i * i <= n; ++i) {

        int n1 = n;
        if ((n1-1) % i == 0) {
            if((n1-1)/i==i) ans++;
            else ans+=2;
        }else{
            while(!(n1%i)){
                n1/=i;
            }
            if(n1%i==1) ans++;
        }

    }

    cout<<ans;

    return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n,q[200010];
ll c,f[200010],h[200010];
double cal(int j,int k)
{
	ll res=f[j]+h[j]*h[j]-f[k]-h[k]*h[k];
	return 1.0*res/(2.0*(h[j]-h[k]));
}
int main()
{
	scanf("%d%lld",&n,&c);
	for (int i=1;i<=n;i++)
	{
		scanf("%lld",&h[i]);
	}
	int l=1,r=0;
	f[1]=0;
	q[++r]=1;
	for (int i=2;i<=n;i++)
	{
		while (l<r && cal(q[l+1],q[l])<1.0*h[i])
		{
			l++;
		}
		//cerr<<q[l]<<" "<<q[l+1]<<" "<<cal(q[l+1],q[l])<<" "<<h[i]<<endl;
		f[i]=f[q[l]]+(h[i]-h[q[l]])*(h[i]-h[q[l]])+c;
		while (l<r && cal(q[r-1],q[r])>cal(q[r-1],i))
		{
			r--;
		}
		//cerr<<cal(q[r-1],q[r])<<" "<<cal(q[r-1],i)<<endl;
		//cerr<<i<<" "<<q[l]<<" "<<q[r]<<endl;
		q[++r]=i;
	}
	cout<<f[n]<<endl;
	return 0;
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
#include <unordered_map>
#include <queue>

using namespace std;
int N;
long long burger[51][2];

long long dp(int N,long long X) {
    long long res = 0;
    if(X==0)return 0;
    if(N==0)return 1;
    if(burger[N-1][0]+1>=X){
        return dp(N-1,X-1);
    }else{
        return burger[N-1][1]+1+dp(N-1,X-burger[N-1][0]-2);
    }
}
// 9
//BBPPPBPBPPPBB
//B,BPPPB,P,BPPPB,B

int main() {
    int i;
    long long X;
    cin>>N>>X;
    burger[0][0]=1;
    burger[0][1]=1;
    for(i=1;i<=N;i++){
        burger[i][0]=1+burger[i-1][0]+1+burger[i-1][0]+1;
        burger[i][1]=(burger[i-1][1]*2)+1;
        // cout<<burger[i][0]<<" "<<burger[i][1]<<endl;
    }
    cout<<dp(N, X);
    return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,a,n) for(int i  = (a); i < (n);i++)
typedef unsigned long long ull;
typedef long long ll;
using namespace std;

int main(){
  	int n,k,memo = 0,cnt = 0,ans = 0;
  	cin >> n >> k;
  	int a[n] = {0},b[n] = {0};
  
  	rep(i,0,n){
		cin >> a[i];
    }
  	sort(a,a+n);
  
  	rep(i,1,n){
      cnt++;
      if(a[i] != a[i-1]){
        b[memo] = cnt;
        cnt = 0;
        memo++;
        
      }
    }
  		cnt++;
        b[memo] = cnt;
  		memo++;
  
  	sort(b,b+memo);
  	if(memo > k){
    	rep(i,0,memo-k){
      		ans += b[i];
    	}
    }
  	
  	cout << ans << endl;
  	
	return 0; 
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using  ll=long long;
 
int main(){
  ll n,k=0;
  cin >> n;
  vector<ll> a(100000);
  for(int i=0;i<n;i++){
    ll x;
    cin >> x;
    k+=x;
    a[x-1]++;
  }
  
  ll q;
  cin >> q;
  
  for(int i=0;i<q;i++){
    ll b,c;
    cin >> b >> c;
    ll x=a[b-1];
    a[b-1]=0;
    a[c-1]+=x;
    k+=(c-b)*x;
    cout << k << endl;
  }
}

Measured memory_bytes: 4048
class Array
  def selection_sort
    data = self
    n = data.size
    cnt = 0
    0.upto(n - 2) do |i|
      min = i
      (i + 1).upto(n - 1) do |j|
        if data[j] < data[min]
          min = j
        end
      end
      if i != min
        tmp = data[i]
        data[i] = data[min]
        data[min] = tmp
        cnt += 1
      end
    end
    return [data, cnt]
  end
end

n = gets.to_i
nums = gets.chomp.split(" ").map(&:to_i)
sorted_nums, cnt = nums.selection_sort
puts "#{sorted_nums.join(" ")}\n#{cnt}"

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

int main() {
	//cout<<"GfG!";
	long long int n, h = 0, i = 1, j = 1, g = 0;
	cin>>n;
    while(500*i <= n)
    {
        if((n/(500*i)) == 0)
            break;
        else
        {
            h = 1000*i;
            i++;
        }
    }
    n -= (500*(i-1));
    while(5*j <= n)
    {
        if((n/(5*j)) == 0)
            break;
        else
        {
            g = 5*j;
            j++;
        }
    }
    cout<<(h+g);
	return 0;
}

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

using namespace std;

vector<int> G[200000];
bool used[200000];
void dfs(int n){
    used[n] = true;
    for(int i = 0; i < G[n].size(); i++){
        if(!used[G[n][i]]) dfs(G[n][i]);
    }
}

int main(){
    int N, M;
    cin >> N >> M;
    for(int i = 0;i < N; i++){
        int K;
        cin >> K;
        for(int j = 0; j < K; j++){
            int L;
            cin >> L;
            G[i].push_back(N+L-1);
            G[N+L-1].push_back(i);
        }
    }
    dfs(0);
    for(int i = 0; i < N; i++){
        if(!used[i]){
            cout << "NO" << endl;
            return 0;
        }
    }
    cout << "YES" << endl;
    return 0;
}

Measured memory_bytes: 8704
import sys
sys.setrecursionlimit(10**7)
from collections import defaultdict
def dfs(node_i, oe):
    if ans[node_i] != -1:
        return
    next_nodes = graph[node_i]
    ans[node_i] = oe
    for next_i, cost in next_nodes:
        dfs(next_i, (oe+cost)%2)
        

N = int(input())
ans = [-1 for i in range(N+1)]
graph = defaultdict(list)
for i in range(N-1):
    u, v, w = map(int, input().split())
    graph[u] += [(v, w)]
    graph[v] += [(u, w)]

dfs(1, 0)
for i in range(1, N+1):
    print(ans[i])

Measured memory_bytes: 163872
/*{{{*/
//#pragma GCC optimize("O3")

#include <bits/stdc++.h>

#ifdef __linux__
#define getchar getchar_unlocked
#define putchar putchar_unlocked
#endif

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

std::string Name = __FILE__;
std::string iput = Name.substr(0, Name.length() - 4) + ".in";
std::string oput = Name.substr(0, Name.length() - 4) + ".out";

template <class T> inline bool chkmin(T &x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T &x, T y) { return x < y ? x = y, true : false; }

template <class T> inline T &read(T &x)
{
    static int f;
    static char c; 
    for (f = 1; !isdigit(c = getchar()); ) {
        if (c == '-')
            f = -1;
    }
    for (x = 0; isdigit(c); c = getchar()) {
        x = x * 10 + c - 48;
    }
    return x *= f;
}
 
template <class T> inline void write(T x, const char p = '\n')
{
    static int top;
    static int s[30];
    if (x < 0) {
        x = -x;
        putchar('-');
    }
    do s[++ top] = x % 10 + 48;
    while (x /= 10);
    while (top)
        putchar(s[top --]);
    putchar(p);
}
/*}}}*/
 
const int maxn = 1e5 + 5;
 
int n;
int m;
int a[maxn];
long long ans;


void exec()
{
    read(n) *= 2;
    for (int i = 1; i <= n; ++ i) read(a[i]);
    std::sort(a + 1, a + n + 1);
    for (int i = 1; i <= n; ++ i)
        if (i & 1) ans += a[i];
    write(ans);
}

/*{{{*/
int main() 
{
    if (fopen(iput.c_str(), "r") != NULL) {
        freopen(iput.c_str(), "r", stdin);
        freopen(oput.c_str(), "w", stdout);
    }

    exec();

    fclose(stdin);
    fclose(stdout);

    return 0;
}
/*}}}*/




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

int a[3];

int main()
{
	a[0] = 1;
	char c1,c2;
	while(cin >> c1){
		cin.ignore();
		cin >> c2;
		swap(a[c1 - 'A'],a[c2 - 'A']);
	}
	for(int i = 0; i < 3; ++i){
		if(a[i])cout << (char)('A' + i) << endl;
	}
}

Measured memory_bytes: 1132
#include<iostream>
#include<cmath>
#include<vector>
#include<set>
#include<algorithm>
#include<tuple>
#include<utility>
#include<cctype>
#include<climits>
#include<map>
#include<queue>
#include<functional>

using namespace std;
template<class T> void chmax(T& a, T b) {if(a < b){a=b;}}
template<class T> void chmin(T& a, T b) {if(a > b){a=b;}}

#define REP(i,a,n) for(int i=a;i<n;++i)
#define RUP(a,b) ((a+b-1)/(b))
#define ENT "\n"
#define REV(v) reverse(v.begin(),v.end())
#define SRTV(v) sort(v.begin(),v.end())
#define SRTAG(a,n) sort(a,a+n,greater<>())
#define MOD 1000000007

typedef long long ll;
typedef tuple<int,int,bool> Tb;

int atcoder(){
    //入力
    string a,b,c;
    cin >> a >> b >> c;
    //処理
    //出力
    if(a[a.length()-1]==b[0] && b[b.length()-1]==c[0]) cout << "YES" << ENT;
    else cout << "NO" << ENT;
    return 0;
}

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int md=1000000007;
char c[3333];
int dp[3333][3333],n;
inline void upd(ll&x){if(x>=md)x-=md;}
int main(){
	scanf("%d%s",&n,c+1);
	dp[0][1]=1;
	int i,j;
	for(i=1;i<n;++i){
		if(c[i]=='<'){
			ll s(0);
			for(j=1;j<=i+1;++j){
				dp[i][j]=s;
				s+=dp[i-1][j];
				upd(s);
			}
		}else{
			ll s(0);
			for(j=i;j;--j){
				s+=dp[i-1][j];
				upd(s);
				dp[i][j]=s;
			}
		}
	}
	ll ans=0;
	for(i=1;i<=n;++i) ans+=dp[n-1][i];
	printf("%d\n",ans%md);
	return 0;
}

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

int main()
{
int n,k;
cin>>n>>k;
int  a[n+1];
for(int i=1;i<n+1;i++)
        cin>>a[i];
sort(a+1,a+n+1,greater<int>());
long long sum=0;

for(int i=k+1;i<n+1;i++)
{

    sum+=a[i];
}
cout<<sum;
 }






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

ans = float('inf')

for i in range(N-K+1):
    start = A[i]
    end = A[i+K-1]

    if start*end>0:
        dist = max(abs(start), abs(end))
    else:
        dist = abs(start)+abs(end)+min(abs(start), abs(end))

    ans = min(ans, dist)

print(ans)

Measured memory_bytes: 20160
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;


int main(void){
  int n,m,i,j,l,a[20],x[20][20],y[20][20];
  
  cin >> n;
  for (i=0;i<n;i++){
    cin >> a[i];
    for (j=0;j<a[i];j++){
      cin >> x[i][j] >> y[i][j];
      x[i][j]--;
    }
  }
  
  int t,ans=0,s;
  for (i=0;i<(1<<n);i++){
    t=i;
    int ho[20]={};
    bool rt[20]={false},pos=true;
    s=0;
    for (j=0;j<n;j++){
      if (t%2==1){
        if (ho[j]==-1){
          pos=false;
          break;
        }
        ho[j]=1;
        rt[j]=true;
        s++;
        for (l=0;l<a[j];l++){
          if (y[j][l]==1){
            if (ho[x[j][l]]==-1){
              pos=false;
              break;
            }
            ho[x[j][l]]=1;
          }else{
            if (ho[x[j][l]]==1){
              pos=false;
              break;
            }
            ho[x[j][l]]=-1;
          }
        }
        if (!pos) break;
        
      }
      t/=2;
      
    }
    
    for (j=0;j<n;j++){
      if ((ho[j]==1 && !rt[j]) || (ho[j]!=1 && rt[j])){
        pos=false;
        break;
      }
    }
    
    if (pos) ans=max(ans,s);
    
  }
  
  cout << ans << endl;
  
  return 0;
}

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

#define _CRT_SECURE_NO_WARNINGS

#define REP(i, n) for(decltype(n) i = 0; i < (n); i++)
#define REP2(i, x, n) for(decltype(x) i = (x); i < (n); i++)

#define ALL(a) (a).begin(),(a).end()
#define SORT(c) sort((c).begin(),(c).end())
#define DESCSORT(c) sort(c.begin(), c.end(), greater<int>())

using namespace std;

const int dy[] = { 0, 1, 0, -1 };
const int dx[] = { 1, 0, -1, 0 };

using LL = long long int;
using LD = long double;

const int INF = (1 << 30) - 1;
const LL INF64 = ((LL)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

using pii = pair<int, int>;
using pll = pair<LL, LL>;
using pdd = pair<double, double>;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vl = vector<LL>;
using vvl = vector<vl>;
using vvvl = vector<vvl>;
using vd = vector<double>;
using vvd = vector<vd>;
using vs = vector<string>;
using vb = vector<bool>;
using vvb = vector<vb>;

int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }
LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }

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

	int n;
	cin >> n;

	vi A(n);

	int cnt = 0;
	REP(i, n) {
		cin >> A[i];

		if (A[i] % 2 != 0) {
			cnt++;
		}
	}

	cout << (cnt % 2 == 0 ? "YES" : "NO") << endl;
	return 0;
}

Measured memory_bytes: 640
import java.util.*;
public class Main {
	Scanner s = new Scanner(System.in);
		void doIt(){
			// 自作クラス(Person)オブジェクトの並べ替え
			Person []personone = new Person[8];
			Person []result = new Person[8];
			Person []three = new Person[6];
			int count = 0;
			for(int j=0; j<3; j++){
				for(int i=0; i<8; i++){
					personone[i] = new Person(s.nextInt(), s.nextDouble());
				}
				Arrays.sort(personone);
				result[count] = personone[0];
				result[count+1] = personone[1];
				three[count] = personone[2];
				three[count+1] = personone[3];
				count+=2;
			}
			Arrays.sort(three);
			result[6] = three[0];
			result[7] = three[1];
			for(int i=0; i<8; i++){
				System.out.println(result[i].number+" "+result[i].time);
			}
		}
		public static void main(String[] args) {
			new Main().doIt();
		}
		class Person implements Comparable<Person>{ 
			int number;
			Double time;
			Person(int number, double time) {
				this.number = number;
				this.time = time;
				}
			@Override
			public int compareTo(Person o){
				return time.compareTo(o.time);
			}
		}
}

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

vector<vector<vector<double>>> dp;
int n;

double exp(int a1,int a2,int a3){
    if(dp[a1][a2][a3]>=0)return dp[a1][a2][a3];
    if(a1==0&&a2==0&&a3==0)return 0;
    double e1=0;
    double e2=0;
    double e3=0;
    if(a3>0)e1+=exp(a1,a2+1,a3-1)*a3;
    if(a2>0)e2+=exp(a1+1,a2-1,a3)*a2;
    if(a1>0)e3+=exp(a1-1,a2,a3)*a1;
    dp[a1][a2][a3]=(e1+e2+e3+n)/(a1+a2+a3);
    return dp[a1][a2][a3];
}

int main() {
    cin>>n;
    V num(3,0);
    rep(i,n){
        ll a;
        cin>>a;
        num[a-1]++;
    }
    dp.assign(310,vector<vector<double>>(310,vector<double>(310,-1)));
    cout<<fixed<<setprecision(10)<<exp(num[0],num[1],num[2])<<endl;
}


Measured memory_bytes: 237696
s1 = list(input())
s2 = list(input())

dp = [[0] * (len(s2) + 1) for i in range(len(s1) + 1)]

s1.insert(0, ' ')
s2.insert(0, ' ')

# 長さ計算
max_len = 0
for i in range(1, len(s1)):
    for j in range(1, len(s2)):
        if s1[i] == s2[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        max_len = max(max_len, dp[i][j])

# 復元
ans = []
i = len(s1)-1
j = len(s2)-1
while i > 0 and j > 0:
    if dp[i][j] == dp[i - 1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j - 1]:
        j -= 1
    else:
        ans.insert(0, s1[i])
        i -= 1
        j -= 1
print(''.join(ans))

Measured memory_bytes: 113628
nlines = gets.to_i
sides  = []

_ = gets.to_i
while line = gets do
  sides << line.split(/,/).map(&:to_i)
end

ends = []
1.upto(nlines) do |start|
  cur = start
  sides.each do |side|
    case cur
    when side[0]
      cur = side[1]
    when side[1]
      cur = side[0]
    end
  end
  ends[cur - 1] = start
end

puts ends

Measured memory_bytes: 8608
#include <stdio.h>

int main(void){
  int x, y, i, j, yo;
  
  scanf("%d %d", &x, &y);
  j = 0;
  
  for(i=0; i<=x; i++){
    yo = (x-i)*4 + i*2;
    if(y == yo){
      j = 1;
    }
  }
  
  if(j == 1){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
  
  return 0;
}


Measured memory_bytes: 1660
#include<cstdio>
#include<vector>
#include<algorithm>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll INF = 1000000000000000LL;

ll n, x[500000], y[500000];
P p[500000];

bool cmp_y(P p1, P p2) { return p1.second < p2.second; }

ll closest_pair(P* p, ll n) {
  if (n <= 1) return INF;
  ll m = n/2, h = p[m].first;
  ll ans = min(closest_pair(p, m), closest_pair(p+m, n-m));
  inplace_merge(p, p+m, p+n, cmp_y);
  vector<P> d;
  for (ll i = 0; i < n; i++) {
    ll temp = h - p[i].first;
    if (temp * temp >= ans) continue;
    for (ll j = d.size() - 1; j >= 0; j--) {
      ll dx = p[i].first - d[j].first;
      ll dy = p[i].second - d[j].second;
      if (dy * dy >= ans) break;
      ans = min(ans, dx * dx + dy * dy);
    }
    d.push_back(p[i]);
  }
  return ans;
}

int main() {
  scanf("%lld", &n);
  for (ll i = 0; i < n; i++) scanf("%lld%lld", &x[i], &y[i]), p[i] = P(x[i], y[i]);
  sort(p, p+n);
  printf("%lld\n", closest_pair(p, n));
}



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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

LL n, a, b, v[50];

LL c(LL x, LL y) {
	LL z = 1;
	inc(i, y) {
		z *= x - i;
		z /= i + 1;
	}
	
	return z;
}

int main() {
	cin >> n >> a >> b;
	inc(i, n) { cin >> v[i]; }
	
	sort(v, v + n, greater<LL>());
	
	LL sum = 0;
	inc(i, a) { sum += v[i]; }
	printf("%.8f\n", static_cast<double>(sum) / a);
	
	LL s, e, ans = 0;
	dec(i, n) { if(v[i] == v[a - 1]) { s = i; } }
	inc(i, n) { if(v[i] == v[a - 1]) { e = i; } }
	e++;
	if(s != 0) {
		ans = c(e - s, a - s);
	} else {
		incII(i, a, min(e, b)) { ans += c(e - s, i); }
	}
	cout << ans << endl;
	
	return 0;
}


Measured memory_bytes: 256
def main():
    N = int(input())
    d = [int(i) for i in input().split()]

    ans = 0
    for i in range(N-1):
        for j in range(i+1,N):
            ans += d[i] * d[j]
    
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
#include <iostream>
#include <bitset>

using namespace std;

int main(){
  unsigned int a,b;

  cin >> a;
  cin >> b;

  bitset<32> a1(a),a2(a),a3(a),b1(b);

  a1 &= b1;
  a2 |= b1;
  a3 ^= b1;
  cout << a1 << endl;
  cout << a2 << endl;
  cout << a3 << endl;

  return 0;
}



Measured memory_bytes: 3172
#include<bits/stdc++.h>
using namespace std;
int n;
map<int,int> res;
int ans;
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        res[a]++;
    }
    while(!res.empty()){
        map<int,int>::iterator it=res.end();
        it--;
        int now=it->first;
        int l2=2<<__lg(now);
        res[now]--;
        if(res[l2-now]>0){
            res[l2-now]--;
            ans++;
        }
        if(res[l2-now]==0)
            res.erase(l2-now);
        if(res[now]==0)
            res.erase(now);
    }
    cout<<ans<<endl;
    return 0;
}

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

int main() {
    int n; cin >> n;
    vector<int> w(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> w[i];
        sum += w[i];
    }

    int minAbs = (int)1e6;
    int tmp = 0;
    for (int i = 0; i < n; i++) {
        tmp += w[i];
        minAbs = min(minAbs, abs(2*tmp - sum));
    }
    cout << minAbs << endl;

    return 0;
}

Measured memory_bytes: 256
n = int(input())
S = list(map(int, input().split()))
q = int(input())
T = list(map(int, input().split()))
ans = 0

def solve(x):
    l = 0
    r = n - 1
    while l <= r:
        mid = (l + r) // 2
        # print(S[mid], n)
        if S[mid] == x:
            return True
        if S[mid] < x:
            l = mid + 1
        else:
            r = mid - 1

    return False

for i in range(q):
    if solve(T[i]):
        # print(T[i])
        ans += 1

print(ans)


Measured memory_bytes: 16716
N, W = map(int, input().split())
items = [list(map(int, input().split())) for _ in range(N)]
sum_v = sum([item[1] for item in items])
inf = float("inf")
dp = [[inf for _ in range(sum_v+1)] for _ in range(N+1)]


dp[0][0] = 0
for i in range(N):
    for j in range(sum_v+1):
        if j - items[i][1] >= 0:
            dp[i+1][j] = min(dp[i][j], dp[i][j - items[i][1]] + items[i][0])
        else:
            dp[i+1][j] = dp[i][j]
for v in range(sum_v, -1, -1):
    if dp[N][v] <= W:
        print(v)
        exit()



Measured memory_bytes: 315316
import heapq
from itertools import accumulate

# dijkstra shortest path solver
def min_cost(G, s, n):
    inf = float("inf")
    cost = [inf for _ in range(n)]
    cost[s] = 0
    q = list()
    heapq.heappush(q, (0, s))

    while (len(q) != 0):
    #while q:
        w,index = heapq.heappop(q)
        if cost[index] < w:
            continue
        for j in G[index]:
            c = cost[index] + G[index][j]
            if c < cost[j]:
                cost[j] = c
                heapq.heappush(q, (c, j))
    return cost

if __name__ == '__main__':
    money = 10**15

    # read inputs
    n, m, s, t = list(map(int,input().split()))
    # zero origin
    S = s-1
    T = t-1

    # create empty graph
    G = [{} for _ in range(n)] # JPY
    H = [{} for _ in range(n)] # SNK

    # set virtex with weight
    for i in range(m):
        u, v, p, q = list(map(int, input().split()))
        u -= 1
        v -= 1
        G[u][v] = p
        G[v][u] = p
        H[u][v] = q
        H[v][u] = q

    min_jpy = min_cost(G, S, n)
    min_snk = min_cost(H, T, n)
    total = [x+y for (x, y) in zip(min_jpy, min_snk)]
    # pre calc minimum cost for all year
    fl = list(accumulate(total[::-1], min))[::-1]

    for year in range(n):
        print(money - fl[year])

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

using namespace std;

typedef long long ll;

const ll maxx = 1e5 + 20;

ll sz, qu[maxx], n, q, t[maxx], ps[maxx], b[maxx];
stack<ll> stk;
vector<ll> v;

int main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> q;
	stk.push(n);
	for(ll i = 0; i < q; i++)
	{
		cin >> qu[i];
		while (stk.size() && stk.top() >= qu[i])
			stk.pop();
		stk.push(qu[i]);
	}
	while (stk.size()) v.push_back(stk.top()), stk.pop();
	for(ll i = 0; i < v.size(); i++) b[i] = -v[i];
	reverse(v.begin(), v.end());
	sz = v.size();
	t[sz-1] = 1;
	for(ll i = sz - 1; i >= 0; i--)
	{
		ll k = v[i];
		while (i && k >= v[0])
		{
			ll r = lower_bound(b + sz - i, b + sz, -k) - b;
//			cout << i << "     " << r << " " << b[r] << " " << k << endl;
			t[sz - r - 1] += (t[i] * (k / (-b[r])));
			k = (k % (-b[r]));
//			return 0; 
		}
		ps[k] += t[i];
//		if (i == 0) break;
	}
//	ps[n] = t[n];
	for(ll i = n - 1; i >= 0; i--) ps[i] = (ps[i+1] + ps[i]);
	for(ll i = 1; i <= n; i++) cout << ps[i] << '\n'; 
	return 0;
}

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

int main() {
  int N, T, ans=0;
  cin >> N >> T;
  int t[N];
  for(int i=0; i<N; i++) {
    cin >> t[i];
  }
  for(int i=0; i<N; i++) {
    if(t[i+1]-t[i]<=T&&i<N-1) {
      ans+=t[i+1]-t[i];
    }
    else {
      ans+=T;
    }
  }
  cout << ans << endl;
}

Measured memory_bytes: 1024
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <chrono>
#define _USE_MATH_DEFINES
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <iterator>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

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

const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const double EPS = 1e-8;
const int MOD = 1000000007; // 998244353;
const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1};
/*-------------------------------------------------*/
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  // freopen("input.txt", "r", stdin);

  vector<string> w{"Sunny", "Cloudy", "Rainy"};
  string s; cin >> s;
  int pos = find(ALL(w), s) - w.begin();
  cout << w[(pos + 1) % 3] << '\n';
  return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <limits.h>
#include <math.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>

typedef unsigned long long ULLONG;
typedef long long LLONG;
static const LLONG MOD_NUM = 1000000007;//998244353;

template<class _T> static void get(_T& a) {
	std::cin >> a;
}
template<class _T> static void get(_T& a, _T& b) {
	std::cin >> a >> b;
}
template<class _T> static void get(_T& a, _T& b, _T& c) {
	std::cin >> a >> b >> c;
}
template<class _T> static void getint(_T& a) {
	if (sizeof(_T) > sizeof(int)) {
		scanf("%lld", &a);
	}
	else {
		scanf("%d", &a);
	}
}

static void exec();

int main()
{
	exec();
	fflush(stdout);
	return 0;
}

static void exec()
{
	LLONG A, B, X;
	get(A, B, X);

	LLONG r = B / X;
	LLONG l = (A - 1LL) / X;
	if (A == 0) {
		l = -1;
	}
	printf("%lld\n", r - l);
}


Measured memory_bytes: 3712
n = gets.to_i

braces = gets.chomp.chars
rest_left_braces_num = 0
additional_right_braces_num = 0
braces.each do |c|
  if c == '('
    rest_left_braces_num += 1
  else
    if rest_left_braces_num == 0
      additional_right_braces_num += 1
    else
      rest_left_braces_num -= 1
    end
  end
end

puts '(' * additional_right_braces_num.abs + braces.join('') + ')' * rest_left_braces_num.abs

Measured memory_bytes: 1788
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)


n, m = map(int, input().split())

GRAPH = {i:[] for i in range(1, n + 1)}
for _ in range(m):
    x, y, z = map(int, input().split())
    GRAPH[x].append(y)
    GRAPH[y].append(x)

def dfs(now):
    SEARCHED[now] = True
    for v in GRAPH[now]:
        if SEARCHED[v]:
            continue
        next = v
        dfs(next)

SEARCHED = {i:False for i in range(1, n + 1)}
count = 0
for i in range(1, n + 1):
    if SEARCHED[i]:
        continue
    dfs(i)
    count += 1

print(count)


Measured memory_bytes: 127396