akhauriyash/Code-Regression huggingface dataset:
#![allow(unused_imports)]
use std::cmp::*;
use std::collections::*;
use itertools::Itertools;
use num::clamp;
use proconio::{input, marker::*, fastout};
use superslice::*;

#[fastout()]
fn main() {
    input! {
        n: usize,
        ab: [(Usize1, Usize1); n-1],
        mut c: [usize; n],
    }
    c.sort();

    let mut g = vec![Vec::new(); n];
    for &(a, b) in &ab {
        g[a].push(b);
        g[b].push(a);
    }

    let mut cs = vec![0; n];
    let mut que = Vec::new();
    que.push(0);
    cs[0] = c.pop().unwrap();
    while let Some(node) = que.pop() {
        for &next in &g[node] {
            if cs[next] > 0 {
                continue;
            }
            cs[next] = c.pop().unwrap();
            que.push(next);
        }
    }
    let mut sum = 0;
    for (a, b) in ab {
        sum += min(cs[a], cs[b]);
    }
    println!("{}", sum);
    for c in cs {
        print!("{} ", c);
    }
}


Measured memory_bytes: 3228
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <complex>

using namespace std;
using i64 = int_fast64_t;
using u64 = uint_fast64_t;
using i32 = int_fast32_t;
using u32 = uint_fast32_t;

#define int i64

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; }
const int INF = 1LL << 60;

signed main() {
	int n, k;
	cin >> n >> k;
	vector<int> h(n, 0);
	for(int i = 0; i < n; i++) cin >> h[i];

	vector<int> dp(n, INF);

	dp[0] = 0;
	for(int i = 1; i < n; i++) {
		for(int j = 1; j <= k; j++) {
			if(i >= j) chmin(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
		}
	}

	cout << dp[n - 1] << endl;
	
	return 0;
}


Measured memory_bytes: 1792
#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=500000004;
const double EPS=1e-6;
const double PI=acos(-1.0);
int ABS(int a){return max(a,-a);}
long long ABS(long long a){return max(a,-a);}
int p[110000];

int main(){
	int a;scanf("%d",&a);
	for(int i=0;i<a;i++)scanf("%d",p+i);
	std::sort(p,p+a);
	int ret=0;
	int now=0;
	int cur=0;
	for(int i=0;i<a;i++){
		if(now!=p[i]){
			if(now<=cur){
				ret+=cur-now;
			}else{
				ret+=cur;
			}
			now=p[i];
			cur=1;
		}else cur++;
	}
				if(now<=cur){
				ret+=cur-now;
			}else{
				ret+=cur;
			}
	printf("%d\n",ret);
}

Measured memory_bytes: 512
#include <stdio.h>
 
int cal(int z){
	int temp, fin;
	temp=z%1000;
	if(temp>0){
		fin=1000-temp;
	}
	else{
		fin=0;
	}
	return fin;
}
 
int main(){
	double x,y;
	scanf("%lf", &x);
	printf("%d",cal(x));
	return 0;
}

Measured memory_bytes: 1724
import sys
sys.setrecursionlimit(1000000)

from collections import defaultdict

N, M = map(int, input().split())
A = sorted(list(map(int, input().split())))

dict = defaultdict(int)

for i in range(M):
  B, C = map(int, input().split())
  dict[C] += B

idx = 0
for k, v in sorted(dict.items(), key=lambda x: -x[0]):
  for _ in range(v):
    if idx+1 <= len(A):
      if A[idx] < k:
      	A[idx] = k
      	idx += 1
      else:
        print(sum(A))
        exit()
    else:
      print(sum(A))
      exit()
      
      
print(sum(A))


Measured memory_bytes: 31780
#include<iostream>
using namespace std;
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cmath>
#define int long long int
const int N=200000+100;
int tree1[4*N+1]={0};
int lazy1[4*N+1]={0};
int tree2[4*N+1]={0};
int lazy2[4*N+1]={0};
void update(int tree[],int lazy[],int start,int end,int left,int right,int val,int index)
{
	if(lazy[index]!=0)
	{
		tree[index]=max(tree[index],lazy[index]);
		if(start!=end)
		{
			lazy[2*index]=max(lazy[2*index],lazy[index]);
			lazy[2*index+1]=max(lazy[2*index+1],lazy[index]);
		}
		lazy[index]=0;
	}
	if(left>end||start>right)
	{
		return ;
	}
	if(start>=left&&end<=right)
	{
		tree[index]=max(tree[index],val);
		if(start!=end)
		{
			lazy[2*index]=max(lazy[2*index],val);
			lazy[2*index+1]=max(lazy[2*index+1],val);
		}
		return ;
	}
	else
	{
		int mid=(start+end)/2;
		update(tree,lazy,start,mid,left,right,val,2*index);
		update(tree,lazy,mid+1,end,left,right,val,2*index+1);
		tree[index]=max(tree[2*index],tree[2*index+1]);
	}
}
int max_query(int tree[],int lazy[],int start,int end,int left,int right,int index)
{
	if(lazy[index]!=0)
	{
		tree[index]=max(tree[index],lazy[index]);
		if(start!=end)
		{
			lazy[2*index]=max(lazy[2*index],lazy[index]);
			lazy[2*index+1]=max(lazy[2*index+1],lazy[index]);
		}
		lazy[index]=0;
	}
	if(left>end||start>right)
	  return -1;
	if(start>=left&&end<=right)
	  return tree[index];
	else
	{
		int mid=(start+end)/2;
		int x=max_query(tree,lazy,start,mid,left,right,2*index);
		int y=max_query(tree,lazy,mid+1,end,left,right,2*index+1);
		return max(x,y);
	}
}
int binary_search(int start,int end,int tree[],int lazy[],int x,int n)
{
	if(start>end)
	{
		return -1;
	}
	else
	{
		int mid=(start+end)/2;
		int val=max_query(tree,lazy,0,n-1,start,mid,1);
		if(val>=x)
		{
			int point=mid;
			int y=binary_search(start,mid-1,tree,lazy,x,n);
			if(y==-1)
			  return point;
			else
			   return y;
		}
		else
		  return binary_search(mid+1,end,tree,lazy,x,n);
	}
}
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n,q;
	cin>>n>>q;
	int total=(n-2)*(n-2);
	while(q--)
	{
		int query,x;
		cin>>query>>x;
		x--;
		if(query==1)
		{
			int index=binary_search(0,n-1,tree2,lazy2,x,n);
			if(index==-1)
			  index=n-1;
			int initial=1;
			int final=index-1;
			int removed=(final-initial+1);
			total-=removed;
			update(tree1,lazy1,0,n-1,x,x,index,1);
			//update(tree2,lazy2,0,n-1,1,index,x,1);
		}
		else
		{
			int index=binary_search(0,n-1,tree1,lazy1,x,n);
			if(index==-1)
			  index=n-1;
			int initial=1;
			int final=index-1;
			int removed=(final-initial+1);
			total-=removed;
			update(tree2,lazy2,0,n-1,x,x,index,1);
			//update(tree1,lazy1,0,n-1,1,index,x,1);
		}
	}
	cout<<total<<endl;
}


Measured memory_bytes: 11804
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define int long long int
#define pb push_back
#define mk make_pair
#define flp(i, n) for(int i=0; i<n; i++)
//#define flp(i, k, n) for(int i=k; i<n; i++)

#define F first
#define S second

int32_t main(void)
{
	int k, n, ans=0, max_d=-1LL;
	cin>>k>>n;
	int a[n+1], d[n]={0};
	flp(i, n) cin>>a[i];
	a[n]=k+a[0];
	flp(i, n){
		d[i]=a[i+1]-a[i];
		if(max_d<d[i]) max_d=d[i];
		ans+=d[i];
	}
	//flp(i, n) cout<<d[i]<<" ";
	//cout<<"\n";
	cout<<ans-max_d<<"\n";
	return 0;
}


Measured memory_bytes: 3328
import sys
import numpy as np

# input = sys.stdin.readline

s = input()

if len(s) % 2 != 0:
    print("No")
else:
    for i in range(0, len(s), 2):
        if (s[i:i+2] != "hi"):
            print("No")
            break
    else:
        print("Yes")

Measured memory_bytes: 21408
#include <iostream>
#include <string>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <cmath>

using namespace std;

typedef long long int ll;

#define all(x) x.begin(),x.end()

const ll mod = 998244353;
const ll INF = 1e9;
const ll MAXN = 1e9;

vector<ll> fact,inv;

ll f(ll a,ll b, ll p)  // a^b mod pを求める
{
  if (b == 0)
  {
    return 1;
  }else if (b % 2 == 0)
  {
    ll d = f(a,(ll)b/2,p);  //a^b = a^(2k) = (a^k)^2  k = b / 2
    return d * d % mod;
  }else
  {
    return a * f(a,b-1,p) % mod;
  }
}

void init(ll n)
{
  fact.resize(n+1,(ll)1);
  inv.resize(n+1,(ll)1);

  for(int i = 2; i <= n; i++)  //　nまでの階乗を求める
  {
    fact[i] = fact[i-1] * i % mod;
  }
  for(int i = 2; i <= n; i++)  //a^(-1) mod p = a^(p-2) mod p  ここをもう少し早くできるぽい
  {
    inv[i] = f(fact[i],mod-2,mod) % mod;
  }
}

ll comb(ll n,ll k)  //n_C_k
{
  if (n < k)
  {
    return 0;
  }
  return (fact[n] * inv[k] % mod) * inv[n-k] % mod;
}

int main()
{
  ll n,a,b,k;
  cin >> n >> a >> b >> k;

  init(n);
  ll ans = 0;
  for(ll x = 0; x <= n; x++){
    if((k-x*a) % b != (ll)0) continue;
    ll y = (ll)(k-x*a)/b;
    if(y < 0 || n < y) continue;
    //cout << "x = "  << x << " y =  " << y << endl;
    //cout << "xa+by = " << x*a + b*y << endl;
    ans += (comb(n,x) % mod) * comb(n,y) % mod;
    ans %= mod;
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 4992
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <numeric>
#include <math.h>
#include <map>
using namespace std;
typedef long long int ll;

constexpr ll mod=998244353;

ll mod_pow(ll a,ll b){
    a%=mod;
    if(b==0)return 1;
    if(b==1)return a;
    ll res=mod_pow(a,b/2)%mod;
    res*=res; res%=mod;
    if(b%2)res*=a;
    return res%mod;
}

ll dp[3030][3030];

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,s; cin >> n >> s;
    vector<int> a(n);
    for(int i=0;i<n;i++){
        cin >> a[i];
    }
    sort(a.begin(), a.end());
    dp[0][0]=1;
    ll res=0;
    for(int i=0;i<n;i++){
        for(int j=3000;j>=0;j--){
            if(j+a[i]<=3000)(dp[i+1][j+a[i]]+=dp[i][j])%=mod;
            (dp[i+1][j]+=dp[i][j]*2)%=mod;
        }
    }
    cout << dp[n][s] << endl;
}

Measured memory_bytes: 74660
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
//#include<bits/stdc++.h>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

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


	ll kotae = 0;
	char c = '<';
	int kazu1 = -1, kazu2 = 0;
	while (c >= '<') {
		kazu1++;
		while ((c = getchar_unlocked()) == '<') kazu1++;
		if (c == '>') kazu2++;
		while ((c = getchar_unlocked()) == '>') kazu2++;
		if (kazu1 > kazu2) kotae += ((ll)kazu1 * (kazu1 + 1) + (ll)kazu2 * (kazu2 - 1)) >> 1;
		else kotae += ((ll)kazu1 * (kazu1 - 1) + (ll)kazu2 * (kazu2 + 1)) >> 1;
		kazu1 = 0;
		kazu2 = 0;
	}

	printf("%lld", kotae);

	Would you please return 0;
}

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

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

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

const int MAX = 1e5 + 5;
const int INF = 1001001001;
const int MOD = 1e9 + 7;

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

    vector<int> P(N);
    rep(i, N) cin >> P[i];

    int mi = INF;
    int ans = 0;
    rep(i, N) {
        if (mi > P[i]) {
            ans++;
            mi = P[i];
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 1024
# -*- coding: utf-8 -*-
 
import math
import itertools
import sys
import copy
 
# 入力
#A, B, C, D = map(int, input().split())
#L = list(map(int, input().split()))
#S = list(str(input()))
#N = int(input())
s = str(input())

cflag = False
for i in range(len(s)) :
  if s[i] == "C" :
    cflag = True
  if cflag == True and s[i] == "F" :
    print ("Yes")
    exit()
print ("No")


Measured memory_bytes: 38384
using System;
using System.Linq;
using System.Collections.Generic;

namespace _0030
{

    struct ID
    {
        internal int X;
        internal int Y;
        internal long Hight;
    }
    

    class Program
    {
        

        static void Main(string[] args)
        {
            int n = int.Parse(Console.ReadLine());

            string[] str;
            int[] x = new int[n];
            int[] y = new int[n];
            long[] h = new long[n];
            int xx = 0;
            int yy = 0;
            long hh = 0;
            for (int i = 0; i < n; i++)
            {
                str = Console.ReadLine().Split(' ');
                x[i] = int.Parse(str[0]);
                y[i] = int.Parse(str[1]);
                h[i] = long.Parse(str[2]);
                if(h[i] >= 1)
                {
                    xx = x[i];
                    yy = y[i];
                    hh = h[i];
                }
            }

            //Console.WriteLine($"{xx} {yy} {hh}");

            long H;                      
            bool find = true;
            long HH = 0;

            var list = new List<ID>();

            for (int i = 0; i <= 100; i++)
            {
                for (int j = 0; j <= 100; j++)
                {                    
                    find = true;
                    H = hh + Math.Abs(xx - i) + Math.Abs(yy - j);
                    H = Math.Max(H, 0);
                    for (int k = 0; k < n; k++)
                    {
                        HH = H - Math.Abs(x[k] - i) - Math.Abs(y[k] - j);
                        HH = Math.Max(HH, 0);
                        if(HH != h[k])
                        {
                            find = false;
                        }                       
                    }
                    if (find)
                    {
                        var id = new ID
                        {
                            X = i,
                            Y = j,
                            Hight = H
                        };
                        list.Add(id);
                    }

                }
            }

            if(list.Count == 1)
            {
                Console.WriteLine($"{list[0].X} {list[0].Y} {list[0].Hight}");
            }



        }
    }
}

Measured memory_bytes: 13268
import Base.parse
import Base.StringVector
using Printf

parse(::Type{String},  str::AbstractString) = str

isdelim(x::UInt8, xs::Set{UInt8}) = x in xs

function myreaduntil(s::IO, delims::Set{UInt8})::Vector{UInt8}
    out = StringVector(0)
    c::UInt8 = 0x00
    while !eof(s)
        c = read(s, UInt8)
        if !isdelim(c, delims)
            break
        end
    end
    push!(out, c)
    if eof(s)
        return out
    end
    while !eof(s)
        c = read(s, UInt8)
        if isdelim(c, delims)
            break
        end
        push!(out, c)
    end
    return out
end

delimset = Set([0x0a, 0x20])

function readword(io::IO = stdin, delims = delimset)::String
    word = myreaduntil(io, delims)
    i = length(word)
    if i == 0 || word[i] != 0x0a
        return String(word)
    elseif i < 2 || word[i-1] != 0x0d
        return String(resize!(word,i-1))
    else
        return String(resize!(word,i-2))
    end
end

pread(ty) = parse(ty, readword())

reads(tys...)::Tuple{tys...} = Tuple{tys...}(pread(ty) for ty in tys)

readvec(tys::Tuple , len::Signed)::Vector{Tuple{tys...}} = @inbounds Tuple{tys...}[reads(tys...) for i in 1:len]

readvec(ty::Type, len::Signed)::Vector{ty} = @inbounds ty[pread(ty) for i in 1:len]

function readmat(ty::Type, s...)::Matrix{ty}
    v = Matrix{ty}(undef, s...)
    @inbounds for i = 1:s[1]
        v[i,:] = readvec(ty, s[2])
    end
    v
end

function main()
    a,b = reads(Int,String)
    bi,bf = map(x -> parse(Int, x), split(b, '.'))
    ans = a*bi+a*bf÷100
    @printf("%i\n",ans)
end

main()


Measured memory_bytes: 198676
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()
#define debug(x) cerr << #x << " is " << x << endl

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

const int INF = 1e9 + 7;

signed main()
{
	IO_OP;
	
	int n;
	cin >> n;
	n %= 1000;
	cout << (1000 - n) % 1000 << endl;	
	
}





Measured memory_bytes: 3636
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())

# i-bit目とj-bit目を入れ替える
def swap_digit(num:int, i:int, j:int):
    if num & (1<<i) and not (num & (1<<j)):
        return num - (1<<i) + (1<<j)
    
    elif not (num & (1<<i)) and num & (1<<j):
        return num + (1<<i) - (1<<j)
    
    else:
        return num
    

# 2つの数のbitが異なる桁を特定する
def different_digit(n: int, a: int, b: int):
    ret = n-1

    for digit in range(n-1, -1, -1):
        if (a^b) & (1<<digit):
            return digit
        
    return ret

# 上位bitから再帰的に決める
def rec(n: int, a: int, b: int):
    if n == 1:
        return [a,b]
    
    dd = different_digit(n,a,b)
    
    a = swap_digit(a, n-1, dd)
    b = swap_digit(b, n-1, dd)
    na = a & ((1<<(n-1)) - 1)
    nb = b & ((1<<(n-1)) - 1)
    
        
    first = rec(n-1, na, na^1)
    latte = rec(n-1, na^1, nb)

    if a & (1<<(n-1)):
        ret = list(map(lambda x: x + (1<<(n-1)), first)) + latte
    else:
        ret = first + list(map(lambda x: x + (1<<(n-1)), latte))

    return [swap_digit(reti, n-1, dd) for reti in ret]


n,a,b = li()
if bin(a).count('1') % 2 == bin(b).count('1') % 2:
    print("NO")
    
else:
    print("YES")
    print(*rec(n,a,b))

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

using namespace std;
using ll = long long;
using edge = struct {int to; ll cost;};

#define mod 1000000007
#define REP(i, n) for (int i = 0; i < n; i++)
#define INF (1 << 29)


//long C(long n, long r);
//long long gcd(long long a, long long b);
//long long lcm(long long a, long long b);


void solve()
{
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    for(int i = 0; i <= a; i++){
        for(int j = 0; j <= b; j++){
            for(int k = 0; k <= c; k++){
                if(500*i+100*j+50*k == x) ans++;
            }
        }
    }
    cout << ans << "\n";
}

int main()
{
    solve();
    return 0;
}

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

int main() {
  int N, K, x, a, sum;
  sum = 0;
    cin >> N >> K;
  for (int i = 0; i < N; i++){
    cin >> x;
     a = K - x;
    if (a < 0){
      a = -1 * a;
    }
    
    if (a < x)
      sum += 2 * a;
    else 
      sum += 2 * x;
  }
  cout << sum << endl;
}
    

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

const ll inf=1LL<<62;
const int vmax=100010;
struct node{int to;ll cost;};
vector<node> graph[vmax];
ll sdist[vmax],tdist[vmax];


void dijkstra(int n,ll* dist,int s){
	fill(dist,dist+n,inf);
	using state=tuple<ll,int>;
	priority_queue<state,vector<state>,greater<state>> q;
	dist[s]=0;q.push(state(0LL,s));
	while(!q.empty()){
		ll cost,v; tie(cost,v)=q.top();q.pop();
		if(dist[v]<cost) continue;
		for(auto &e:graph[v]){
			int nv=e.to;
			ll ncost=cost+e.cost;
			if(dist[nv]>ncost){
				dist[nv]=ncost;
				q.push(state(ncost,nv));
			}
		}
	}
	return;
}

vector<ll> sd,td;

const int qn=1<<17;
vector<ll> data[1<<18];

void init(int n){
	rep(i,n){
		int sidx=lower_bound(sd.begin(),sd.end(),sdist[i])-sd.begin();
		int tidx=lower_bound(td.begin(),td.end(),tdist[i])-td.begin();
		data[sidx+qn-1].emplace_back(tidx);
		sort(data[sidx+qn-1].begin(),data[sidx+qn-1].end());
	}
	for(int i=qn-2;i>=0;--i){
		int left=2*i+1,right=2*i+2;
		copy(data[left].begin(),data[left].end(),back_inserter(data[i]));
		copy(data[right].begin(),data[right].end(),back_inserter(data[i]));
		sort(data[i].begin(),data[i].end());	
	}
	return;
}

ll query(int a,int b,int k,int l,int r,int x){
	if(b<=l||r<=a) return 0LL;
	if(a<=l&&r<=b){
		ll ret=data[k].end()-lower_bound(data[k].begin(),data[k].end(),x);
		return ret;
	}
	int m=(l+r)/2;
	return query(a,b,2*k+1,l,m,x)+query(a,b,2*k+2,m,r,x);
}

int main(void){
	int n,m;
	cin >> n >> m;
	rep(i,m){
		int a,b,c;
		cin >> a >> b >> c;
		graph[a].push_back({b,c});
		graph[b].push_back({a,c});
	}
	dijkstra(n,sdist,0);
	dijkstra(n,tdist,n-1);

	rep(i,n) sd.emplace_back(sdist[i]),td.emplace_back(tdist[i]);
	sort(sd.begin(),sd.end()),sort(td.begin(),td.end());

	sd.erase(unique(sd.begin(),sd.end()),sd.end());
	td.erase(unique(td.begin(),td.end()),td.end());

	init(n);
	int q;
	cin >> q;
	rep(loop,q){
		ll fs,fg;
		cin >> fs >> fg;
		int sidx=upper_bound(sd.begin(),sd.end(),fs)-sd.begin();
		int tidx=lower_bound(td.begin(),td.end(),fg)-td.begin();
		cout << query(0,sidx,0,0,qn,tidx) << endl;
	}
	return 0;
}

Measured memory_bytes: 42956
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace AtCoder.C
{
    public class Program
    {
        public static void Main() { var r = GetResult(); Debug.WriteLine(r); Console.Write(r); }

        private static object GetResult()
        {
            var (X, N) = Read2Longs();
            if (N == 0) return X;

            var P = ReadLongs();

            if (!P.Contains(X)) return X;


            for (int i = 1; ; i++)
            {
                var up = X + i;
                var down = X - i;

                if (!P.Contains(down))
                {
                    return down;
                }

                if (!P.Contains(up))
                {
                    return up;
                }

                P.Remove(down);
                P.Remove(up);
            }

            return null;
        }

        #region Console.Read

        public static string ReadText() { return Console.ReadLine(); }
        public static List<string> ReadTexts() { return Console.ReadLine().Split(' ').ToList(); }
        public static long ReadLong() { return long.Parse(Console.ReadLine()); }
        public static (long, long) Read2Longs() { var ls = ReadLongs(); return (ls[0], ls[1]); }
        public static (long, long, long) Read3Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2]); }
        public static (long, long, long, long) Read4Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3]); }
        public static (long, long, long, long, long) Read5Longs() { var ls = ReadLongs(); return (ls[0], ls[1], ls[2], ls[3], ls[4]); }
        public static List<long> ReadLongs() { return Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToList(); }

        #endregion
    }
}


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

// Macros
#define F  first
#define S  second
#define PB push_back

// Rename Datatypes
using ll  = long long;
using ld  = long double;
using pii = pair<int,int>;

// Common Functions
ll fastpow(ll a, ll ex){ ll res = 1; while(ex){ if(ex & 1) res *= a; a *= a; ex >>= 1; } return res; }
ll fastpow(ll a, ll ex, ll m){ a %= m; ll res = 1; while(ex){ if(ex & 1) res = (a*res) % m; a = (a*a) % m; ex >>= 1; } return res; }
ll modinverse(ll a, ll m){ ll m0 = m, y = 0, x = 1; while (a > 1){ ll q = a / m; a %= m; swap(a,m); x -= q*y; swap(x,y); } if(x < 0) x += m0; return x; }

// HELPERS
//  Tedious Grid Movements
vector<pii> moves_grid = { {0,1} , {0,-1} , {1,0} , {-1,0} };
inline bool move_okay(int x, int y, int n, int m) { return 0 <= x and x < n and 0 <= y and y < m; }
//  Remember:
//   * vec.assign() GOOD; vec.resize() BAD
//   * comparator uses <

// Output, Common Containers
template <typename T> ostream& operator << (ostream &os, const vector<T> &v) { for (T i : v) os << i << ' '; return os; }
template <typename T> ostream& operator << (ostream &os, const set<T> &v)    { for (T i : v) os << i << ' '; return os; }
template <typename T, typename S> ostream& operator << (ostream &os, const pair<T,S> &v) { os << "(" << v.F << "=>" << v.S << ") "; return os; }
template <typename T, typename S> ostream& operator << (ostream &os, const map<T,S> &v)  { for (auto i : v) os << i << ' '; return os; }

// Debugging
#ifdef SANYAM1101
	#define trace(args...) do{ cerr << "TRACE ON! (Line: " << __LINE__ << ")\n"; auto _stream = istringstream{string{#args}}; d_f(_stream, args); } while(0)
	void d_f(__attribute__((unused)) istringstream& _stream) {}
	template<typename Head, typename... Tails> void d_f(istringstream& _stream, Head H, Tails... T) { string _name; _stream >> _name; if(_name.back() == ',') _name.pop_back(); cerr << "\t" << _name << " <=> [" << H << "]\n"; d_f(_stream, T...); }
#else
	#define trace(args...)
#endif


// CODE STARTS HERE

void solve(){
	int n, m;
	cin >> n >> m;

	vector<vector<int>> adj(n + 1);
	while(m--){
		int s, t;
		cin >> s >> t;
		adj[s].push_back(t);
	}

	ld ans = 1e18;

	vector<ld> dp(n + 1);
	dp.back() = 0;

	for(int i = n - 1; i; --i){
		for(int j = n - 1; j; --j){
			ld su = 0, maxx = 0;
			for(auto ng: adj[j]){
				su += dp[ng];
				maxx = max(maxx, dp[ng]);
			}

			bool block = (i == j) and adj[j].size() > 1;

			dp[j] = 1 + (su - (block ? maxx : 0))
			            / (adj[j].size() - block);
		}

		ans = min(ans, dp[1]);
	}

	cout << ans << "\n";
}

signed main (void){
	// Fast_IO
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	// Set Fixed Notation (default sucks), High Precision for Floating-Point Output
	cout << fixed << setprecision(20);

	// Multiple TCs
	int tt = 1;
	// cin >> tt;
	while(tt--) solve();
}


Measured memory_bytes: 4708
package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
	"strconv"
)

const INFINITY = math.MaxInt64/2 - 1

func exec(stdin *Stdin, stdout *Stdout) {
	n := stdin.ReadInt()
	k := stdin.ReadInt()
	a := stdin.ReadIntSlice(n)

	sort.Ints(a)

	if a[len(a)-1] < k {
		stdout.Println("IMPOSSIBLE")
		return
	}

	if a[len(a)-1] == k {
		stdout.Println("POSSIBLE")
		return
	}

	gcd := a[0]
	for i := 1; i < n; i++ {
		gcd = Gcd(gcd, a[i])
	}

	if k%gcd == 0 {
		stdout.Println("POSSIBLE")
	} else {
		stdout.Println("IMPOSSIBLE")
	}
}

func Gcd(x, y int) int {
	if x < y {
		x, y = y, x
	}

	for y > 0 {
		x, y = y, x%y
	}

	return x
}

func main() {
	stdout := NewStdout()
	defer stdout.Flush()
	exec(NewStdin(bufio.ScanWords), stdout)
}

type Stdin struct {
	stdin *bufio.Scanner
}

func NewStdin(split bufio.SplitFunc) *Stdin {
	s := Stdin{bufio.NewScanner(os.Stdin)}
	s.stdin.Split(split)
	s.stdin.Buffer(make([]byte, bufio.MaxScanTokenSize), INFINITY)
	return &s
}

func (s *Stdin) Read() string {
	s.stdin.Scan()
	return s.stdin.Text()
}

func (s *Stdin) ReadInt() int {
	n, _ := strconv.Atoi(s.Read())
	return n
}

func (s *Stdin) ReadFloat64() float64 {
	n, _ := strconv.ParseFloat(s.Read(), 64)
	return n
}

func (s *Stdin) ReadIntSlice(n int) []int {
	a := make([]int, n)
	for i := 0; i < n; i++ {
		a[i] = s.ReadInt()
	}
	return a
}

func (s *Stdin) ReadStringSlice(n int) []string {
	a := make([]string, n)
	for i := 0; i < n; i++ {
		a[i] = s.Read()
	}
	return a
}

func (s *Stdin) ReadFloat64Slice(n int) []float64 {
	a := make([]float64, n)
	for i := 0; i < n; i++ {
		a[i] = s.ReadFloat64()
	}
	return a
}

type Stdout struct {
	stdout *bufio.Writer
}

func NewStdout() *Stdout {
	return &Stdout{bufio.NewWriter(os.Stdout)}
}

func (s *Stdout) Flush() {
	s.stdout.Flush()
}

func (s *Stdout) Println(a ...interface{}) {
	fmt.Fprintln(s.stdout, a...)
}

func Min(a int, b ...int) int {
	for _, v := range b {
		if v < a {
			a = v
		}
	}
	return a
}

func Max(a int, b ...int) int {
	for _, v := range b {
		if a < v {
			a = v
		}
	}
	return a
}

func Abs(x int) int {
	if x > 0 {
		return x
	} else {
		return x * -1
	}
}

func Pow(x, y int) int {
	z := 1
	for y > 0 {
		if y%2 == 0 {
			x *= x
			y /= 2
		} else {
			z *= x
			y -= 1
		}
	}
	return z
}

func CreateMatrix(x, y int) [][]int {
	matrix := make([][]int, x)
	for i := 0; i < x; i++ {
		matrix[i] = make([]int, y)
	}
	return matrix
}


Measured memory_bytes: 3072
a, b, k = gets.chomp.split.map(&:to_i)

if a >= k
  a = a - k
  k = 0
end

if a <= k
  k = k - a
  a = 0
end

if b >= k
  b = b - k
  k = 0
end

if b <= k
  b = 0
  k = b - a
end

k.times do |i|
  if a >= 1
    a -= 1
  elsif b >= 1
    b -= 1
  elsif a == 0 && b == 0
    break
  end
end

print("#{a} #{b}")

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=350;
int main(){
    int n,x,maxx=0,cnt=0;;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(maxx<=x){
            cnt++;
            maxx=x;
        }
    }
    cout<<cnt<<endl;
    return 0;
}


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

int N[4];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    /* Nの取得 */
    cin >> N[0] >> N[1] >> N[2] >> N[3];
    
    /* Nのソート */
    sort(N, N + 4);
    
    /* 結果の出力 */
    if ((N[0] == 1) && (N[1] == 4) && (N[2] == 7) && (N[3] == 9)) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define vi vector<int>
#define vb vector<bool>
#define pii pair<int,int>
#define mod 1000000007
#define ss second
#define ff first
#define vpii vector<pii>
#define vvi vector<vi>
#define pb push_back
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int k,n;
    cin>>k>>n;
    if(k*500>=n)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 256
// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll [[maybe_unused]] = long long;
using ull [[maybe_unused]] = unsigned long long;
using ld [[maybe_unused]] = long double;

[[maybe_unused]] static constexpr int mod = (int)1e9 + 7;
[[maybe_unused]] static constexpr int inf = 100100100;
[[maybe_unused]] static constexpr ll linf = 1e18;
[[maybe_unused]] static constexpr double eps = 1e-9;
[[maybe_unused]] static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, a, b) for (ll i = a; i < b; ++i)
#define rrrep(i, a, b) for (ll i = a; i >= b; --i)
#define all(obj) begin(obj), end(obj)
#define rall(obj) rbegin(obj), rend(obj)
#define pb push_back
#define fst first
#define snd second


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    cout << A * B - A - B + 1 << endl;
}


Measured memory_bytes: 256
def min3(x, y, z):
    inf = 10 ** 9
    m1 = min(x)
    m2 = min(y)
    m3 = min(z)
    i1 = x.index(m1)
    i2 = y.index(m2)
    i3 = z.index(m3)
    if abs((i1 - i2) * (i2 - i3) * (i3 - i1)):
        return m1 + m2 + m3
    re1 = re2 = re3 = inf
    if i1 == i2 or i1 == i3:
        x[i1] = inf
        re1 = min3(x, y, z)
        x[i1] = m1
    if i1 == i2 or i2 == i3:
        y[i2] = inf
        re2 = min3(x, y, z)
        y[i2] = m2
    if i3 == i2 or i1 == i3:
        z[i3] = inf
        re3 = min3(x, y, z)
        z[i3] = m3
    return min(re1, re2, re3)

def dot(A, B):
    C = []
    for x in zip(*B):
        s = 0
        for y, z in zip(A, x):
            s += y * z
        C.append(s)
    return C

gs, cn = map(int, input().split())
d = [list(map(int, input().split())) for _ in range(cn)]
c = [list(map(int, input().split())) for _ in range(gs)]
cc = [[0] * cn for _ in range(3)]
for i in range(gs):
    ci = c[i]
    for j in range(gs):
        cc[(i + j) % 3][ci[j] - 1] += 1
ds = []
for i in range(3):
    ds.append(dot(cc[i], d))
print(min3(ds[0], ds[1], ds[2]))


Measured memory_bytes: 5620
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

bool IsValid(int N, string &S, int x, int y, int z) {
  char a = '0' + x;
  char b = '0' + y;
  char c = '0' + z;
  vector<char> chars({a, b, c});
  int pos = 0;
  for (int i = 0; i < 3; ++i) {
    while (pos < N and S[pos] != chars[i]) {
      ++pos;
    }
    if (pos == N) {
      return false;
    }
    ++pos;
  }
  return true;
}

int main() {
  int N;
  cin >> N;
  string S;
  cin >> S;
  int ans = 0;
  for (int x = 0; x <= 9; ++x) {
    for (int y = 0; y <= 9; ++y) {
      for (int z = 0; z <= 9; ++z) {
	if (IsValid(N, S, x, y, z)) {
	  ++ans;
	}
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>
#include<unordered_set>
#include<bitset>
#include<complex>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

//typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector< vector<int> > mat;

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD =  (int)1e9 + 7;
const double EPS = 1e-9;

int N, K;
int A[1010];
bool use[1000010];
vector<int> sumv;

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

	cin >> N >> K;
	rep(i, 0, N)
	{
		cin >> A[i];
		if (i > 0)A[i] += A[i - 1];
	}

	rep(i, 0, N)rep(j, i, N)
	{
		if (i == 0)
		{
			sumv.push_back(A[j]);
		}
		else
		{
			sumv.push_back(A[j] - A[i - 1]);
		}
	}

	fill(use, use + SZ(sumv), true);

	int ans = 0;
	rrep(i, 0, 40)
	{
		int cnt = 0;
		rep(j, 0, SZ(sumv))
		{
			if (!use[j])continue;
			if ((sumv[j] >> i) & 1)
			{
				cnt++;
			}
		}

		if (cnt < K)continue;
		ans += 1LL << i;

		rep(j, 0, SZ(sumv))
		{
			if (!((sumv[j] >> i) & 1))
			{
				use[j] = false;
			}
		}
	}

	cout << ans << endl;

	return 0;
}

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

int main() {
	
	int M , D;
	cin >> M >> D;
	int ans = 0;
	for(int k = 1;k<=M;k++) {
    	for(int i = 0;i<10;i++){
    	    for(int j = 0;j<10;j++) {
    	        
    	            if(i<2 || j<2) continue;
    	            int n  = 10*j  + i;
    	            if(n>D)
    	            continue;
    	            if(i*j==k)
    	                ans++;
    	        }
    	    }
	}
	cout<<ans<<"\n";
	return 0;
}

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

int main() {

	int A, B;
	cin >> A >> B;

	if (A - B * 2 > 0) {
		cout << A - B * 2 << endl;
	}
	else {
		cout << "0" << endl;
	}

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    int max = 0;
    char c = 'a';
    int counter;
    for(int i = 0;i < n;i++) {
        counter = 0;
        for(int j = 0;j < 26;j++) {
            if(count(s.begin(),s.begin() + i,c + j) != 0 && count(s.begin() + i,s.end(),c + j) != 0) {
                counter++;
            }
        }
        if(max < counter) {
            max = counter;
        }
    }
    cout << max << endl;
}


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

int main() {
  int N,M;
  cin >> N >> M;
  vector<int> A(N);
  int sum = 0;
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
    sum += A.at(i);
  }
  int count = 0;
  for (int i = 0; i < N; i++) {
    if(A.at(i)*(4*M) >= sum) count++;
  }
  if(count >=  M) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


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

using namespace std;

typedef long long ll;

#define sz(x) ((int)(x).size())
#define in(x) int x;cin>>x
#define bit(n) (1<<(n))

#define out(x) cout<<(x)<<endl;
#define err(x) cerr<<(x)<<endl;
#define errr(x,y) cerr<<(x)<<" "<<(y)<<endl;

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

#define i5 100002

int main(){
	int n, m, x, a[101], l=0, r=0;
	bool ab[101] = {};
	cin >> n >> m >> x;
	int t;
	rep(i, m){
		cin >> t;
		ab[t] = true;
	}

	rep(i, x) if(ab[i]) ++l;
	rep(i, n-x) if(ab[i+x]) ++r;

	cerr << l << " " << r << endl;

	cout << (l>r ? r : l) << endl;

	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

class Main {

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

        String a = sc.next();
        String b = sc.next();

        char[] charArray1 = a.toCharArray();
        char[] charArray2 = b.toCharArray();

        for (int i = 0; i < a.length() - 1; i++) {
            System.out.print(charArray1[i]);
            System.out.print(charArray2[i]);
        }
        if (a.length() == b.length()) {
            System.out.print(charArray1[a.length() - 1]);
            System.out.println(charArray2[b.length() - 1]);
        } else if (a.length() > b.length()) {
            System.out.println(charArray1[a.length() - 1]);
        }
    }
}


Measured memory_bytes: 21716
#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{

  int n;
  int data[4][100005];
  int dp[4][100005];
  int ans;
  cin >> n;
  for(int i=1; i<=n; i++) cin >> data[1][i] >> data[2][i] >> data[3][i];
  
  dp[1][1] = data[1][1];
  dp[2][1] = data[2][1];
  dp[3][1] = data[3][1];
  for(int i=2; i<=n; i++){
    dp[1][i] = max(dp[2][i-1],dp[3][i-1]) + data[1][i];
    dp[2][i] = max(dp[1][i-1],dp[3][i-1]) + data[2][i];
    dp[3][i] = max(dp[2][i-1],dp[1][i-1]) + data[3][i];
  }
  ans = max(dp[1][n],dp[2][n]);
  cout << max(ans,dp[3][n]) << endl;
  return 0;
}


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

int num[100100];

int main(){
    int N; cin >> N;
    for(int i=0; i<N; i++){
        int a; cin >> a;
        if(a<=N) num[a]++;
    }
    int ans=0;
    for(int i=1; i<=N; i++){
        if(num[i]>=i) ans+=i;
    }
    cout << N-ans << endl;
}

Measured memory_bytes: 384
# URL : https://atcoder.jp/contests/abc179/tasks/abc179_b
n = int(input())
d = [list(map(int, input().split())) for _ in range(n)]
ok = False


def f(p):
    return p[0] == p[1]


for i in range(n - 2):
    a = True
    for j in range(3):
        a &= f(d[i + j])
    ok |= a
if ok:
    print('Yes')
else:
    print('No')


Measured memory_bytes: 9176
#include <bits/stdc++.h>
#define mem(i,a) memset(i,a,sizeof(i))
#define PI acos(-1.0)
#define DMAX 200000+5
#define MOD 20190823
#define eps 1e-8
#define mp make_pair
#define INF 1000000000+9
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
template<class T> inline void read(T &x){
    x=0; 
    T f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-'){
            f=-1;
        }
        ch=getchar();
    }
    while(ch<='9' && ch>='0'){
        x=x*10+(ch-'0');
        ch=getchar();
    }
    x*=f;
}
ll a,b,c;
map<ll,ll> m;
int main(){
    read(a),read(b);
    c=a*b;
    if(c%2==0){
        cout<<"Even"<<endl;
    }
    else{
        cout<<"Odd"<<endl;
    }
    return 0;
}

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

// #include "../cxx-prettyprint/prettyprint.hpp" // vecの内容をきれいに表示

using namespace std;
typedef long long ll;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)

#define max(p,q)((p)>(q)?(p):(q))
#define min(p,q)((p)<(q)?(p):(q))
#define INF ((1LL<<62)-(1LL<<31)) /*オーバーフローしない程度に大きい数*/
#define MOD 1000000007

int main(){
// ここに処理を記述

	// 入力受け取り
	int N, W;
	cin >> N >> W;

	vector< vector<int> > val;
	int temp1, temp2;
	val.push_back({0, 0}); // 1-indexed
	for(int i=0; i<N; i++){
		cin >> temp1 >> temp2;
		val.push_back({temp1, temp2}); // val[i][0] = w[i] val[i][1] = v[i]
	}

	// dpテーブル : 
	vector< vector<ll> > dp(N+1, vector<ll>(W+1, 0));
	FOR(i,1,N+1){
		REP(j,W+1){
			if(j - val[i][0] >= 0){
				dp[i][j] = max(dp[i-1][j],dp[i-1][j-val[i][0]] + val[i][1]);
			}
			else{
				dp[i][j] = dp[i-1][j];
			}
		}
	}

	// cout << dp << "\n";

	ll ans = dp[N][W];

	cout << ans << "\n";

return 0;
}

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

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int a,b,c; cin >> a >> b >> c;
    if(b/a > c) cout << c << ln;
    else cout << b/a << ln;
    return 0;
}

Measured memory_bytes: 256
import math
from functools import reduce

def gcd(v1, v2):
    if v1 == 0 or v2 == 0:
        return max(v1, v2)
    if v1 % v2 == 0:
        return v2
    return gcd(v2, v1%v2)

N = int(input())
A = list(map(int, input().split()))

print(reduce(gcd, A))

Measured memory_bytes: 14756
#include<iostream>
#include<sstream>
#include<fstream>
#include<cstdio>
#include<vector>
#include<list>
#include<stack>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<cmath>
#include<cstdlib>
using namespace std;

int main(){
	vector<int> args(3);
	while(cin>>args[0]>>args[1]>>args[2], args[0]||args[1]||args[2]){
	sort(args.begin(),args.end());
	int n;
	cin>>n;
	double d  = args[0]*args[0] + args[1]*args[1];
	//cout<<args[0]<<":"<<args[1]<<endl;
	for(int x=0;x<n;++x){
		int r;
		cin>>r;
		if(4*r*r>d){
			cout<<"OK"<<endl;
		}else{
			cout<<"NA"<<endl;
		}
	}
	}
	return 0;
}

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

using namespace std;

using ll = long long;

constexpr char newl = '\n';

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

    int x, y;
    cin >> x >> y;

    bool f = false;
    for (int i = 0; i <= x; i++) {
        int j = x - i;
        if (2 * i + 4 * j == y) {
            f = true;
            break;
        }
    }
    cout << (f ? "Yes" : "No") << newl;

    return 0;
}

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

#define ll long long int

using namespace std;

int main() {
    ll n;
    cin >> n;
    vector<ll> V(n+1, 1);

    for (ll i = 2; i <= n; ++i) {
        ll p = i;
        while (p <= n) {
            ++V[p];
            p += i;
        }
    }

    ll res = 0;
    for (ll i = 1; i <= n; ++i) {
        res += i * V[i];
    }

    cout << res << endl;
}


Measured memory_bytes: 81388
use std::io::Read;
use std::cmp::{max, min};

fn main() {
    let mut buf = String::new();
    std::io::stdin().read_to_string(&mut buf).unwrap();

    let answer = solve(&buf);

    println!("{}", answer);
}

fn solve(input: &str) -> String {
    let mut iterator = input.split_whitespace();

    let n: usize = iterator.next().unwrap().parse().unwrap();

    let mut vec: Vec<i64> = Vec::with_capacity(n);
    for _i in 0..n {
        vec.push(iterator.next().unwrap().parse().unwrap());
    }

    let mut ans: i64 = vec[1] - vec[0];
    let mut min_value: i64 = vec[0];
    for i in 1..n {
        ans = max(ans, vec[i] - min_value);
        min_value = min(min_value, vec[i]);
    }

    return ans.to_string();
}



Measured memory_bytes: 9024
import java.util.*;
//import java.util.stream.Collectors;

public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		int n = Integer.parseInt(sc.next());
		int k = Integer.parseInt(sc.next());
		int result = 0;
		for(int i=0; ; i++){
			if(Math.pow(k, i) > n){
				result = i;
				break;
			}
		}
		System.out.println(result);
	}
}


Measured memory_bytes: 35348
a = []
for i in range(6):
    a.append(input())

b = 0
for i in range(5):
    if b == 1:
        break
    for j in range(4-i):
        ans = abs(int(a[i]) - int(a[j+1]))
        if ans > int(a[5]):
            print(':(')
            b = 1
            break
        
    if i == 4 and b == 0:
        print('Yay!')

Measured memory_bytes: 3064
///*** author: HM Imu SC ***\\\

#include<bits/stdc++.h>

using namespace std;

#define tillEnd() int t,testCase=1;scanf("%d",&t);while(t--)
#define FEO(container) for(auto ith : container)
#define FEIO(container) for(int i=0; i<container.size();i++)
#define showCase(str) cout<<"Case "<<testCase<<": "<<str<<endl;testCase++
#define read_auto() freopen("in.txt","r",stdin)
#define write_auto() freopen("out.txt","w",stdout)
#define read_write_auto() read_auto();write_auto()
#define to_order() ofstream order("test_cases.txt")
#define space << " " <<
#define get_random(a,b) rand()%(b-a+1)+a
#define lint long long int
#define INF(x) INT_MAX-x
#define boost_io() ios_base::sync_with_stdio(false);cin.tie(false)

int main(){

    int n,x;

    cin>>n;

    vector<int> a,b,c;

    while(n--){
        cin>>x;
        a.push_back(x);
    }

    for(int i=a.size();i--;){
        cin>>x;
        b.push_back(x);
    }

    for(int i=a.size()-1;i--;){
        cin>>x;
        c.push_back(x);
    }

    int previous=-1;

    int total=0;

    FEO(a){

        total+=b[ith-1];

        if(ith-1==previous){
            total+=c[previous-1];
        }

        previous=ith;
    }

    cout<<total<<endl;

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;

vector<pair<ll, ll> > prime_factorize(ll N) {
    vector<pair<ll, ll> > res;
    for (ll a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        ll ex = 0; // 指数

        // 割れる限り割り続ける
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // その結果を push
        res.push_back({a, ex});
    }

    // 最後に残った数について
    if (N != 1) res.push_back({N, 1});
    return res;
}


void Main()
{
    ll n;
    cin >> n;

    vector<ll> primeCnt(n+1);
    for (ll i = 2; i <= n; i++) {
        auto primes = prime_factorize(i);
        rep(j, primes.size()) {
            ll v = primes[j].first;
            primeCnt[v] += primes[j].second;
        }
    }
    
    ll MOD = 1000000007;
    ll res = 1;
    rep(i, primeCnt.size()) {
        res = (res * (1 + primeCnt[i])) % MOD;
    }
    put(res);
}
signed main(){ Main();return 0;}

Measured memory_bytes: 3636