akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <iostream>
#include <map>
#include <queue>
#include <functional>
#include <array>
#include <set>
#include <utility>
 
struct Status
{
    std::array<int, 16> board;
    int distance{}, h{}, empty{};
    bool operator>(const Status &) const;
};
 
bool Status::operator>(const Status &tmp) const
{
    return this->distance + this->h > tmp.distance + tmp.h;
}
 
void shift_empty(Status&, int);
 
int main()
{
    Status start;
    for (int i{}; i < 16; i++)
    {
		scanf("%d", &start.board[i]);
		start.board[i]--;
		if (start.board[i] >= 0)
			start.h += std::abs(start.board[i] % 4 - i % 4) + std::abs(start.board[i] / 4 - i / 4);
		else
			start.empty = i;
    }
    std::priority_queue<Status, std::vector<Status>, std::greater<Status>> pq;
    std::set<std::array<int, 16>> done;
    pq.push(start);
 
    while (!pq.empty())
    {
        Status min{pq.top()};
        pq.pop();
        if (done.find(min.board) != done.end())
            continue;
        done.insert(min.board);
        if (min.h == 0)
        {
            printf("%d\n", min.distance);
            break;
        }
        min.distance++;
        if (min.empty % 4)
        {
            shift_empty(min, 0);
            auto next{done.find(min.board)};
            if (min.distance + min.h <= 45 && done.find(min.board) == done.end())
                pq.push(min);
            shift_empty(min, 2);
        }
        if (min.empty % 4 < 3)
        {
            shift_empty(min, 2);
            auto next{done.find(min.board)};
            if (min.distance + min.h <= 45 && done.find(min.board) == done.end())
                pq.push(min);
            shift_empty(min, 0);
        }
        if (min.empty >= 4)
        {
            shift_empty(min, 1);
            auto next{done.find(min.board)};
            if (min.distance + min.h <= 45 && done.find(min.board) == done.end())
                pq.push(min);
            shift_empty(min, 3);
        }
        if (min.empty < 12)
        {
            shift_empty(min, 3);
            auto next{done.find(min.board)};
            if (min.distance + min.h <= 45 && done.find(min.board) == done.end())
                pq.push(min);
            shift_empty(min, 1);
        }
    }
    return 0;
}
 
void shift_empty(Status& tmp, int com)
{
    const int dir[4]{-1, -4, 1, 4};
    std::swap(tmp.board[tmp.empty], tmp.board[tmp.empty + dir[com]]);
    tmp.empty += dir[com];
    tmp.h = 0;
    for (int i{}; i < 16; i++)
		if (i != tmp.empty)
        	tmp.h += std::abs(tmp.board[i] % 4 - i % 4) + std::abs(tmp.board[i] / 4 - i / 4);
    return;
}


Measured memory_bytes: 142480
use proconio::input;

fn main() {
    input! {
        n: usize,
    }

    if n % 2 != 0 {
        println!("{}", 0);
        return;
    }

    let mut count = 0;
    let mut div = 10;
    while n >= div {
        count += n / div;
        div *= 5;
    }

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


Measured memory_bytes: 2108
#include <iostream>
#include <string>

#define min(a, b) (a < b ? a : b)
using namespace std;

int main()
{
    string S;
    int day;

    cin >> S >> day;
    char answer;

    for(int i = 0; i < min(S.size(), day); i++)
    {
        if(i == day - 1 || S[i] != '1')
        {
            answer = S[i];
            break;
        }
    }

    cout << answer;
    return 0;
}


Measured memory_bytes: 256
A, B = list(map(int, input().split()))

ans = -1
i = 1
while i < 2000:

    a = int(i * 1.08) - i
    b = int(i * 1.1) - i
    if A == a and B == b:
        ans = i
        break
    i += 1
print(ans)


Measured memory_bytes: 39024
"""
author : halo2halo
date : 30, Jan, 2020
"""

import sys

# import itertools
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

N = int(readline())
LR= [map(int, readline().split()) for _ in range(N)]


ans=0
for i,j in LR:
    ans+=j-i+1
    

print(ans)


Measured memory_bytes: 12500
N = int(input())

dic = dict()
count = 0
for i in range(N):
    t = input()
    if t not in dic:
        dic[t] = 1
        if count==0:
            count += 1
    if t in dic:
        dic[t] += 1
        if count < dic[t]:
            count = dic[t]

ans = list()
for s in dic.keys():
    if dic[s] == count:
        ans.append(s)

ans.sort()

[print(s) for s in ans]
    

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

int main(){
	int n, max = 0;
	int a[100]={0};
	while(cin >> n){
		a[n]++;
		if(max < a[n]) max = a[n];
	}
	for(int i = 0; i < 100; i++){
		if(a[i] == max) cout << i << endl;
	}
}

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

#define FOR(i,a,b)  for(ll (i)=a;(i)<(b);++(i))
#define RFOR(i,a,b) for(ll (i)=a;(i)>=(b);--(i))
#define REP(i,n)    FOR(i,0,n)
#define RREP(i,n)   RFOR(i,n,0)
#define ALL(v)      (v).begin(),(v).end()
#define BIT(n)      (1LL<<(n))
#define IN(x,l,r)   ((l)<=(x)&&(x)<=(r))
#define LEN(s)      (string(s)).length()
#define NPOS        string::npos
#define SHOW(x)     cout<<#x<<" = "<<x<<endl
#define SORT(v)     sort(ALL(v))
#define SZ(v)       (ll)(v).size()
#define UNIQ(v)     SORT(v);(v).erase(unique(ALL(v)),(v).end())
#define PERM(v)     for(bool p=1;p;p=next_permutation(ALL(v)))
#define PQ(T)       priority_queue<T,vector<T>,greater<T>>

template<class T>string join(const vector<T>& v,string d=" ")
{stringstream s;REP(i,SZ(v))s<<d<<v[i];return s.str().substr(LEN(d));}

template<class T>ostream& operator<<(ostream& s,const vector<T>& v)
{s<<"{";if(SZ(v))s<<join(v,", ");s<<"}";return s;}

template<class T>bool contain(const string& s,const T& v)
{return s.find(v)!=NPOS;}

template<class T,class U>string& replace(string& s,const T& f,const U& t)
{for(auto p=s.find(f);p!=NPOS;p=s.find(f,p+LEN(t)))s.replace(p,LEN(f),t);}

const ll INF = 1e15;
const ll MOD = 1e9+7;
const double EPS = 1e-10;

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

int main() {
    ll N; cin >> N;
    vector<ll> A(N); REP(i, N) cin >> A[i];
    
    SORT(A);
    
    vector<ll> B(N+1, 0);
    REP(i, N) B[i+1] = B[i] + A[i];
    
    ll ans = 1;
    RREP(i, N-2) {
        if (2 * B[i+1] >= A[i+1]) ans++;
        else break;
    }
    cout << ans << endl;
    
    return 0;
}

Measured memory_bytes: 1792
<?php
$n = intval(fgets(STDIN));
$str = str_split(trim(fgets(STDIN)));
$l = count($str);
$c = 0;
for($i = 0; $i <= 999; $i++){
    $pin = sprintf("%03d", $i);
    $k = 0;
    for($j = 0; $j < $l; ++$j){
        if($str[$j] == $pin[$k])$k++;
        if($k == 3){
            $c++;
            break;
        }
    }
}
echo $c;

Measured memory_bytes: 6648
#include <cstdio>
#include <iostream>
#include <string>
using namespace std;
int main(int argc, char** argv)
{
	(void)argc;
	(void)argv;
	int N;
	char S1[54]={};
	char S2[54]={};
	(void)scanf("%d",&N);
	(void)scanf("%s",S1);
	(void)scanf("%s",S2);

	const int64_t MOD = 1000000007;
	int64_t ans = 0;
	int LastMode = 0;
	for(int i=0;i<N;i++){
		int nowMode = 1; // 縦
		if (S1[i] == S1[i+1]){
			nowMode = 2; // 横
			i++;
		}

		if (LastMode == 1){
			if (nowMode==1){
				// 縦縦: *=2;
				ans = (ans * 2) % MOD;
			}else{//nowMode ==2
				// 縦横: *=2;
				ans = (ans * 2) % MOD;
			}
		}else if(LastMode==2){
			if (nowMode==1){
				// 横縦　*=1;

			}else{//nowMode ==2
				// 横横 *=3;
				ans = (ans * 3) % MOD;
			}
		}else{ // LastMode==0
			if (nowMode==1){
				ans = 3;
			}else{//nowMode ==2
				ans = 6;
			}
		}
		LastMode = nowMode;
	}
	printf("%ld\n",ans);

	return 0;
}


Measured memory_bytes: 256
fun main(args: Array<String>) {
    val (N, P) = listOfInt()
    val S = next().map { it - '0' }
    var ans = 0L
    if (10 % P == 0) { //P = 2, 5
        repeat(N) { r ->
            if (S[r] % P == 0) ans += r + 1
        }
        println(ans)
        return
    }
    val d = IntArray(N + 1)
    var ten = 1
    for (n in (0 until N).reversed()) {
        val a = S[n] * ten % P
        d[n] = (d[n + 1] + a) % P
        ten *= 10; ten %= P
    }
    val c = IntArray(P)
    for (n in (0 .. N).reversed()) {
        ans += c[d[n]]
        c[d[n]] += 1
    }
    println(ans)
}
fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map(String::toInt)


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

using namespace std;
typedef long long ll;

int main () {
    int N, M;
    cin >> N >> M;
    int K, A;
    vector<int> ans(M);
    for (int i = 0; i < N; ++i) {
        cin >> K;
        for (int j = 0; j < K; ++j) {
            cin >> A;
            ans.at(A-1)++;
        }
    }

    int cnt = 0;
    for (int i = 0; i < M; ++i) {
        if (ans.at(i) == N) cnt++;
    }

    cout << cnt << endl;

}



Measured memory_bytes: 256
import sys
from collections import deque
d = [(1,0),(-1,0),(0,1),(0,-1)]
def bfs(sy,sx): #スタートまたは各汚れ間の最短路を計算
    dist = [[-1]*w for i in range(h)]
    dist[sy][sx] = 0
    q = deque([(sy,sx)])
    while q:
        y,x = q.popleft()
        for dy,dx in d:
            y_ = y+dy
            x_ = x+dx
            if 0 <= y_ < h and 0 <= x_ < w:
                if dist[y_][x_] < 0 and s[y_][x_] != "x":
                    dist[y_][x_] = dist[y][x] + 1
                    q.append((y_,x_))
    return dist

po = [1<<i for i in range(11)] #1<<iの前処理(いらないかも??)
while 1:
    w,h = map(int, sys.stdin.readline().split())
    if w == 0:
        break
    s = [sys.stdin.readline() for i in range(h)]
    p = [] #スタート、汚れを保存
    for y in range(h):
        for x in range(w):
            if s[y][x] == "o":
                p.append((y,x))
                break
    for y in range(h):
        for x in range(w):
            if s[y][x] == "*":
                p.append((y,x))
    """↑スタートの座標を常にp[0]に保存したかったからこうやってループを分けた"""
    n = len(p)
    dist = [[float("inf")]*n for i in range(n)] #スタート及び各汚れ間の最短路
    f = 0
    for i in range(n):
        di = bfs(*p[i]) #*listとすると、list[0],list[1],list[2],…と同値なので複数引数の場合にこうやって書くと楽
        for j in range(n):
            dist[i][j] = di[p[j][0]][p[j][1]]
            if dist[i][j] < 0:
                f = 1 #もしたどりつけない点があったら終了
                break
    if f:
        print(-1)
        continue
    """以下bitDP"""
    ma = po[n] #最大状態ma = 111…1+1
    dp = [[float("inf")]*(n) for i in range(ma)] #最後に消したところからの最短路を見る必要があるため2次元(dp[b][i] := 汚れを消した状態がbかつ最後に消した汚れが汚れiの時の最短路)
    dp[1][0] = 0
    for b in range(ma): #b := 汚れを消した部分を表す
        for j in range(n):
            if (b&po[j]):continue #もし汚れjが消えてたら飛ばす
            b_ = b|po[j] #b_ := 新たに汚れjを削除
            for i in range(n):
                if not b&po[i]:continue
                #汚れiを最後に消したときのb,b_について比較
                if dp[b_][j] > dp[b][i]+dist[i][j]:
                    dp[b_][j] = dp[b][i]+dist[i][j]
    print(min(dp[ma-1])) #全部消したときの最短路を出力



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

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define REPr(i, n) for(int i = (n)-1; i >= 0; --i)
#define FORq(i, m, n) for(int i = (m); i <= (n); ++i)
#define FORqr(i, m, n) for(int i = (n); i >= (m); --i)
#define MP make_pair
#define SIN(x, S) (S.count(x) != 0)
#define M0(x) memset(x, 0, sizeof(x))
#define FILL(x, y) memset(x, y, sizeof(x))
#define MM(x) memset(x, -1, sizeof(x))
#define ALL(x) (x).begin(), (x).end()
#define DB(x) cerr << #x << " = " << x << endl
#define DB2(x, y)                                                              \
    cerr << "(" << #x << ", " << #y << ") = (" << x << ", " << y << ")\n";
#define DEBUG                                                                  \
    int x12345;                                                                \
    cin >> x12345;
typedef pair<int, int> PII;
typedef pair<long long, long long> PLL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
const long long MOD = 1e9 + 7;
///////////////////////////////////////////////
// for template
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;
}
///////////////////////////////////////////////
/// 🍈( '-' 🍈 |AC|
int main() {
    int a; cin >> a;
    cout << a + a*a + a*a*a << endl;
}

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

int main(){
  int N;
  vector<long> A;
  cin >> N;
  for(int i=0; i<N; i++){
    long a; cin >> a;
    A.push_back(a);
  }
  sort(A.begin(), A.end(), greater<int>());
  int n=4;
  long tmp=A[0];
  long num=1;
  long ans=1;
  for(int i=1; i<N; i++){
    if(tmp==A[i]){
      num++; continue;
    }
    if(num>=2){
      if(n==4 && num>=4){
        cout << tmp*tmp << endl;
        return 0;
      }else if(n==2 && num>=2){
        ans*= tmp;
        cout << ans << endl;
        return 0;
      }else if(n==4 && num>=2){
        ans *= tmp;
        n=2;
      }
    }
    tmp = A[i];
    num=1;
  }
  if(n==4 && num>=4){
    cout << tmp*tmp << endl;
    return 0;
  }else if(n==2 && num>=2){
    ans*= tmp;
    cout << ans << endl;
    return 0;
  }
  cout << "0" << endl;
  return 0;
}

Measured memory_bytes: 1400
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <sstream>
#include <iostream>
#include <iomanip>
#define _USE_MATH_DEFINES
#include <cmath>
#include <climits>
#include <cstdlib>
#include <cstring>
#include <cfloat>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cassert>
using namespace std;

#define EPS 1e-12
#define ull unsigned long long
#define ll long long
#define VI vector<ll>
#define PII pair<ll, ll> 
#define VVI vector<vector<ll> >
#define REP(i,n) for(int i=0,_n=(n);(i)<(int)_n;++i)
#define RANGE(i,a,b) for(int i=(int)a,_b=(int)(b);(i)<_b;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
#define ALLR(c) (c).rbegin(), (c).rend()
#define PB push_back
#define MP(a, b) make_pair(a, b)
#define POPCOUNT __builtin_popcount
#define POPCOUNTLL __builtin_popcountll
#define CLEAR(table, v) memset(table, v, sizeof(table));
#define PRINT1(table, D0) REP(d0, D0) cout<<table[d0]<<" "; cout<<"\n";
#define PRINT2(table, D0, D1) REP(d0, D0) { REP(d1, D1) cout<<table[d0][d1]<<" "; cout<<"\n"; }
#define PRINT3(table, D0, D1, D2) REP(d0, D0) { REP(d1, D1) { REP(d2, D2) cout<<table[d0][d1][d2]<<" "; cout<<"\n"; } cout<<"\n"; }
#define UNIFORM_DOUBLE(a, b) (((b-a)*(double)rand()/RAND_MAX)+a) // [a, b) 
#define UNIFORM_LL(a, b) (ll)UNIFORM_DOUBLE(a, b) // [a, b) 
#define IN(v, lo, hi) ((lo)<=(v) && (v)<(hi))
#define DD(v) cout<<#v<<": "<<v<<endl
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const map<T0, T1>& v) { for( typename map<T0, T1>::const_iterator p = v.begin(); p!=v.end(); p++ ){os << p->first << ": " << p->second << " ";} return os; }
template <typename T0, typename T1> std::ostream& operator<<(std::ostream& os, const pair<T0, T1>& v) { os << v.first << ": " << v.second << " "; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<T>& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << " "; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const vector<vector<T> >& v) { for( int i = 0; i < (int)v.size(); i++ ) { os << v[i] << endl; } return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const set<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }
template <typename T> std::ostream& operator<<(std::ostream& os, const deque<T>& v) { vector<T> tmp(v.begin(), v.end()); os << tmp; return os; }

#define MOD 1000000007LL
#define INF (1LL<<60)

int main() {
	//ios::sync_with_stdio(false);
	string s;
	while(cin>>s) {
		ll ans = s.size()*2;
		REP(ci, 26) {
			char c = 'a'+ci;
			ll lans = 0;
			string ss(s);
//			DD(c);
			while(ss.size()) {
				bool ok=true;
				for(auto c0 : ss) if(c!=c0) ok=false;
				if(ok) {
					ans = min(ans, lans);
					break;
				}
				string ns(ss.size()-1, ' ');
				REP(i, ss.size()-1) {
					ns[i] = ss[i]==c ? ss[i] : ss[i+1];
				}
//				DD(ns);
				ss = ns;
				lans++;
			}
		}
		
		cout<<ans<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 256
// Problem Code: abc158_d

#include <iostream>
#include <string>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
	int Q;
	string S;
	bool flip = false;
	
	cin >> S >> Q;
	deque<char> D(S.begin(), S.end());
	
	while (Q--) {
		char C;
		int q, F;
		cin >> q;
		if (q == 1)
			flip = !flip;
		else {
			cin >> F >> C;
			if (--F ^ flip)
				D.push_back(C);
			else
				D.push_front(C);
		}
	}
	
	if (flip)
		reverse(D.begin(), D.end());
	
	for (char c: D)
		cout << c;
	
	return 0;
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
typedef  long long  ll;
ll inf=1000000000000000,mod=1000000007;

int main(){
    ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        // #ifndef ONLINE_JUDGE
        //     freopen("input.txt","r",stdin);
        //     freopen("output.txt","w",stdout);
        // #endif
        ll sum=0;ll n;cin>>n;
        for(ll i=1;i<=n;i++){
            for(ll j=1;j<=n;j++){
                for(ll k=1;k<=n;k++){
                    sum+=__gcd(__gcd(i,j),k);
                }
            }
        }
        cout<<sum;

}


Measured memory_bytes: 3640
using System.Linq;
using System;
class asd
{
    static void Main()
    {
        while (true)
        {
            /////////////////////////////////////////////////////////////// 
            int[] n = Console.ReadLine().Split().Select(int.Parse).ToArray();
            if (n.Sum() == 0) { break; }
            int[] a = new int[n[0]];
            for (int i = 0; i < a.Length; i++)
            { a[i] = int.Parse(Console.ReadLine()); }
            int maxgap = 0;
            int NUM = 0;
            for (int i = n[2]; i >= n[1]; i--)
            {
                if (maxgap < a[i-1] - a[i ])
                {
                    maxgap = a[i - 1] - a[i]; NUM = i ;
                }
            }
            Console.WriteLine(NUM);
            /////////////////////////////////////////////////////////////// 
        }
    }
}

Measured memory_bytes: 9704
import sys
from operator import itemgetter
from heapq import heappush, heappop
input = sys.stdin.readline


def simulate(camels):
    camels.sort(key=itemgetter(0))
    queue = []
    ans = 0
    for k, l, r in camels:
        ans += l
        if len(queue) < k:
            # ok
            heappush(queue, l - r)
        else:
            heappush(queue, l - r)
            d = heappop(queue)
            ans -= d
    return ans


def solve():
    n = int(input())
    camels = [tuple(map(int, input().split())) for _ in range(n)]

    ans = 0
    camels_l = []
    camels_r = []
    for k, l, r in camels:
        if k == n or l == r:
            ans += l
        elif l > r:
            camels_l.append((k, l, r))
        else:
            # r > l
            camels_r.append((n - k, r, l))

    ans += simulate(camels_l)
    ans += simulate(camels_r)

    print(ans)


t = int(input())
for _ in range(t):
    solve()


Measured memory_bytes: 60228
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;
#define rep(i,n) for(int i = 0; i < ((int)(n)); i++)   // 0-indexed昇順

int main() {
    ll N;
    cin >> N;
    vector<ll> A(N), B;
    rep (i, N) cin >> A[i];
    copy(A.begin(), A.end(), back_inserter(B));
    //rep (i,N) cout << B[i] << " ";
    //cout << endl;
    sort(A.begin(), A.end());
    //rep (i,N) cout << A[i] << " ";
    //cout << endl;
    ll HN = N/2;
    rep (i,N) {
        auto P = lower_bound(A.begin(), A.end(), B[i]);
        int j = P - A.begin();
        if (j < HN) cout << A[HN] << endl;
        else cout << A[HN-1] << endl;
    }
}


Measured memory_bytes: 5488
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000007

int main() {
  
  int N;
  string S;

  cin >> N >> S;
  int b = 0,w = 0;
  for(int i = 0;i < N;i++) {
    if(S.at(i) == '.') w++;
  }
  S = 'a' + S + 'a';

  int ans = 10000000;
  for(int i = 0;i < S.size();i++) {
    int sum;
    if(S.at(i) == '#') b++;
    else if(S.at(i) == '.') w--;
    sum = b+w;
    ans = min(ans,sum);
  }
  
  cout << ans << endl;


}



Measured memory_bytes: 772
#include<iostream>
#include<algorithm>
#include <string>
#include <cstring>
#include<climits>
#include <vector>
#include <queue>
#include <stack>
#include <map>

using namespace std;
typedef long long ll;
pair<ll, ll > a[200001];

int main() {
	cin.sync_with_stdio(0); cin.tie(0); cout.tie(NULL);
	
	int n;
	ll D, A;
	cin >> n >> D >> A;
	for (int i = 0; i < n; i++) {
		cin >> a[i].first >> a[i].second; 
	}

	sort(a, a + n);

	queue<pair<ll, ll>> s;
	ll cnt = 0;
	ll ans = 0;

	for (int i = 0; i < n; i++) {
		while (!s.empty() && s.front().first < a[i].first) {
			cnt -= s.front().second;
			s.pop();
		}
		a[i].second -= cnt * A;
		if (a[i].second <= 0)continue;
		else {
			ll t = a[i].second / A;
			if (a[i].second % A != 0)t += (ll)1;
			ans += t;
			cnt += t;
			s.push({ a[i].first + D + D, t });
		}
	}

	cout << ans << '\n';





}

Measured memory_bytes: 4992
N,M,Q = map(int,input().split())
src = [list(map(int,input().split())) for _ in range(M)]
query = [list(map(int,input().split())) for _ in range(Q)]
arr2 = [[0]*N for _ in range(N)]
csum2 = [[0]*N for _ in range(N)]
for l,r in src:
    l -= 1
    r -= 1
    arr2[l][r] += 1
csum2[0][0] = arr2[0][0]
for i in range(1,N):
    csum2[i][0] = csum2[i-1][0] + arr2[i][0]
    csum2[0][i] = csum2[0][i-1] + arr2[0][i]

for l in range(1,N):
    for r in range(1,N):
        csum2[l][r] = arr2[l][r] + csum2[l-1][r] + csum2[l][r-1] - csum2[l-1][r-1]

for p,q in query:
    p -= 1
    q -= 1
    if p == 0:
        print(csum2[q][q])
    else:
        print(csum2[q][q] - csum2[q][p-1] - csum2[p-1][q] + csum2[p-1][p-1])


Measured memory_bytes: 79156
#include <stdio.h>

typedef unsigned long ulong;

ulong diff(ulong a, ulong b){
    return __builtin_ctzl(a^b);
}

ulong hd(ulong a, ulong b){
    return __builtin_popcountl(a^b);
}

ulong bit_remove(ulong a, ulong n){
    ulong low  = a & ((1<<n)-1);
    ulong high = (a >> (n+1)) << n;
    return high | low;
}

ulong bit_insert(ulong a, ulong n, ulong b){
    ulong low  = a & ((1<<n)-1);
    ulong high = (a >> n) << (n+1);
    return high | (b<<n) | low;
}
#define N 22
long data[1<<N];

void solve(const long n, const long a, const long b, const size_t sp, const size_t ep, const long mask){
    if(n==1){
        data[sp+0] = a;
        data[sp+1] = b;
        return;
    }
    ulong d = diff(a&mask, b&mask);
    ulong nmask = mask ^ (1<<d);
    ulong e = __builtin_ctzl(nmask);
    ulong aa = nmask & a;//bit_remove(a, d);
    ulong ab = nmask & (a ^ (1<<e));//bit_remove(a, d) ^ 1;
    ulong bb = nmask & b;//bit_remove(b, d);
    const size_t mp = (sp+ep)/2;
    //printf("%ld %ld %ld\n", aa, ab, bb);
    solve(n-1, aa, ab, sp, mp, nmask);
    solve(n-1, ab, bb, mp, ep, nmask);
    for(size_t i=sp; i<mp; i++){
        //data[i] = bit_insert(data[i], d, (a&(1<<d)) >> d);
        data[i] |= a&(1<<d);
    }
    for(size_t i=mp; i<ep; i++){
        //data[i] = bit_insert(data[i], d, (b&(1<<d)) >> d);
        data[i] |= b&(1<<d);
    }
}

int main(void){
    long n, a, b;
    scanf("%ld %ld %ld", &n, &a, &b);
    if(__builtin_popcountl(a)%2 == __builtin_popcountl(b)%2){
        printf("NO\n");
        return 0;
    }
    solve(n, a, b, 0, 1<<n, 0xFFFFFFFFFFFFFFFF);
    const size_t m = 1<<n;
    printf("YES\n");
    for(size_t i=0; i<m-1; i++){
        printf("%ld ", data[i]);
    }
    printf("%ld\n", data[m-1]);
    return 0;
}


Measured memory_bytes: 2048
#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
#include <numeric>
#include <queue>
#include <sstream>
#include <string>
#include <string.h>
#include <tuple>
#include <vector>

#define REP(i,x) for(int i{ 0 }; i < (int)(x); i++)
#define REPC(i,x) for(int i{ 0 }; i <= (int)(x); i++)
#define RREP(i,x) for(int i{ (int)(x) - 1 }; i >= 0 ;i--)
#define RREPC(i,x) for(int i{ (int)(x)}; i >= 0; i--)
#define REP1O(i,x) for(int i{ 1 }; i < (int)(x); i++)
#define REP1C(i,x) for(int i{ 1 }; i <= (int)(x); i++)

#define PB push_back
#define MP make_pair
#define F first
#define S second
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int64_t ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvll;
typedef pair<int, int> pii;
typedef tuple<int, int, int> tupiii;
typedef tuple<ll, ll, ll> tuplll;

const int INTMAX = 2147483647;
const ll LLMAX = 9223372036854775807;
const int MOD = 1000000007;

template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
inline void swap(ll& a, ll& b) { a ^= b; b ^= a; a ^= b; }
inline void swap(int& a, int& b) { a ^= b; b ^= a; a ^= b; }


void n() {
	cout << "No" << endl;
}
void y() {
	cout << "Yes" << endl;
}

int main()
{
	int a, b;
	cin >> a >> b;

	if (a == 2)
	{
		if (b == 2)
			y();
		else
			n();
	}

	else if (a == 4 || a == 6 || a == 9 || a == 11)
	{
		if (b == 4 || b == 6 || b == 9 || b == 11)
			y();
		else
			n();
	}

	else
	{
		if (b == 4 || b == 6 || b == 9 || b == 11 || b == 2)
			n();
		else
			y();
	}

}


Measured memory_bytes: 256
n = int(input())


def devide2(x):
    ar = []
    ar.append([1, x])
    for i in range(2, int(-(-x ** 0.5 // 1)) + 1):
        if x % i == 0:
            ar.append([i, x // i])
    return ar


kumi = devide2(n)
# print(kumi)

ans = 10 ** 12 + 1000
for i in range(len(kumi)):
    ans = min(ans, sum(kumi[i]))

print(ans - 2)


Measured memory_bytes: 3464
#include <bits/stdc++.h>
using namespace std;
// define
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define ADD(a, b) a = (a + b) % mod
#define SUB(a, b) a = (a+mod-b)%mod
#define MUL(a, b) a = (((a)%mod) * ((b)%mod)) % mod
#define rollcall cout << "I'm Sucu." << endl;
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define fi first
#define se second
// typedef
typedef complex<double> Point;
typedef pair<int, int> P;
typedef pair<int, P> PP;
typedef pair<P, int> Pi;
typedef vector<int> vi;
typedef deque<int> dq;
const int inf = 1e9+7;
const int INF = 1e18+7;
const int mod = 1e9+7;
// int sum = accumulate(a, a+n, 0LL);
// int mx = max_element(a, a+n);
// int mn = min_element(a, a+n);
// int cnt = count(a, a+n, k);

int a[200000], b[200000], dp[200000];
signed main(){
  int n, m;cin >> n >> m;
  rep(i,m)cin >> a[i];
  rep(i,m)b[a[i]] = 1;
  dp[0] = 1, dp[1] = 1;
  if(a[0] == 1)dp[1] = 0;
  
  repi(i,2,n+1){
    if(b[i] == 1)continue;
    dp[i] = dp[i-1] + dp[i-2];
    dp[i] %= mod;
  }
  cout << dp[n] << endl;
  return 0;
}


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

using namespace std;


int main() {


	int a, MAX, ans;
	ans = a = 0;
	MAX = 105000;
	vector<int> prm(MAX);

	cin >> a;


	// 2から5000までの倍数マスに１代入
	for (int i = 2; i < 50001; i++)
	{
		if (i > 2 && i % 2 == 0) continue;

		for (int k = 2; k < 52000; k++)
		{
			if (i * k < MAX) { prm[i * k] = -1; }
			else { break; }
		}
	}

	for (int m = a; m < MAX; m++)
	{
		if (prm[m] != -1) {
			ans = m;
			break;
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <string>
#include <utility>
#include <queue>
#include <algorithm>
#include <map>
#include <cmath>
using namespace std;

#define ll long long
#define pb push_back

int main(){

	int N, M;
	int arr[35];
	for(int i = 0; i < 35; i ++){
		arr[i] = 0;
	}

	cin >> N >> M;
	for(int i = 0; i < N; i ++){
		int m;
		cin >> m;
		for(int j = 0; j < m; j ++){
			int a;
			cin >> a;
			arr[a]++;
		}
	}
	int ans = 0;
	for(int i = 1; i <= M; i ++){
		if(arr[i] == N)ans++;
	}
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
n, m, x = map(int, (input().split()))
lst = [list(map(int, input().split())) for i in range(n)]

ans = float('inf')
flg = 0

for i in range(2 ** n):
    chk = [0] * (m + 1)
    for j in range(n):
        if i >> j & 1:
            for k in range(m + 1):
                chk[k] += lst[j][k]
    if all([chk[i] >= x for i in range(1, m + 1)]):
        ans = min(ans, chk[0])
        flg = 1

print(ans if flg else '-1')

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

#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define repr(i,n) for(int i=(int)(n-1);i>=0;i--)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb(s) push_back(s)
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout << #x" = " << x << endl
#define print(x) cout << x << endl
#define maxch(x,y) x=max(x,y)
#define minch(x,y) x=min(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt(x) bitset<32>(x).count()

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<P, int> PPI;
typedef pair<int, P> PIP;
typedef pair<ll, ll> PL;
typedef pair<P, ll> PPL;
typedef set<int> S;

#define INF INT_MAX/3
#define MAX_N 1000000001

string s[20];

ll calc(int p, int q) {
  bool add = false;
  if ('0' <= s[p][s[p].length() - 1] && s[p][s[p].length() - 1] <= '9') {
    return s[p][s[p].length() - 1] - '0';
  } else if (s[p][s[p].length() - 1] == '+') {
    add = true;
  }

  ll ans = ((add) ? 0 : 1);
  repl(i, p + 1, q) {
    if ('0' <= s[i][s[i].length() - 1] && s[i][s[i].length() - 1] <= '9') {
      if (add) ans += (s[i][s[i].length() - 1] - '0');
      else ans *= (s[i][s[i].length() - 1] - '0');
    } else {
      int j = i++;
      while(i < q && s[j].length() < s[i].length()) i++;
      if (add) ans += calc(j, i);
      else ans *= calc(j, i);
      i--;
    }
  }

  return ans;
}

int main(){
  cin.sync_with_stdio(false);
  int n;

  while(cin >> n, n) {
    rep(i, n) cin >> s[i];
    print(calc(0, n));
  }

  return 0;
}

Measured memory_bytes: 3124
#include<iostream>
#include <iomanip>
using namespace std;
int main(){
    double a;
    cin>>a;
    double const PI=3.14159265358979323846;
    cout<<setiosflags(ios::fixed)<< setprecision(7)<<PI*a*a<<" "<<PI*a*2<<endl;
    return 0;
}


Measured memory_bytes: 3232
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;
// Welcome to my source code!

const int MAX_N = 1e5;
const int MOD = 1000000007;

int h[MAX_N];

ll mod_pow(ll a, ll b, ll p) {
    if (b == 0) return 1;
    if (b & 1) return (a * mod_pow(a, b - 1, p)) % p;
    ll t = mod_pow(a, b / 2, p);
    return (t * t) % p;
}

int main() {
    int n;
    cin >> n;
    for (int i = 0, a; i < n; i++) {
        cin >> a;
        h[a]++;
    }
    ll ans = 0;
    if (n & 1) {
        if (h[0] != 1) {
            if (n != 1) {
                cout << 0 << endl;
                return 0;
            } else {
                cout << 1 << endl;
                return 0;
            }
        }
        bool flag = true;
        for (int i = 1; i < n; i++) {
            if (i & 1) {
                if (h[i]) flag = false;
            } else {
                if (h[i] != 2) flag = false;
            }
        }
        if (flag) ans = mod_pow(2, n / 2, MOD);
        else {
            cout << 0 << endl;
            return 0;
        }
    } else {
        if (h[0]) {
            cout << 0 << endl;
            return 0;
        }
        bool flag = true;
        for (int i = 1; i < n; i++) {
            if (i % 2 == 0) {
                if (h[i]) flag = false;
            } else {
                if (h[i] != 2) flag = false;
            }
        }
        if (flag) ans = mod_pow(2, n / 2, MOD);
        else {
            cout << 0 << endl;
            return 0;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
# -*- coding: utf-8 -*-

N = int(input())

ans = 0
for i in range(N, -1, -1):
    if i % 2 != 0:
        # 約数の個数
        res = 0
        for j in range(1, i+1):
            if i % j == 0:
                res += 1
        if res == 8:
            ans += 1
print(ans)

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

#define fori(i, ini, lim) for(int i = int(ini); i < int(lim); i++)
#define ford(i, ini, lim) for(int i = int(ini); i >= int(lim); i--)

#define debug(x) cout << "> " << #x << " = " << x << endl;
#define debug_at(arr, at) cout << "> " << #arr << "[" << at << "] = " << arr[at] << endl;
#define debug_pair(p) cout << "> " << #p << " = (" << p.first << ", " << p.second << ")" << endl;

using namespace std;

vector<string> grid;

bool solve() {
    vector<string> vec(grid);
    int n = grid.size();
    int m = grid[0].size();
    fori(i, 0, n) {
        int at = n - i - 1;
        fori(j, 0, m) {
            int last = m - j - 1;
            vec[i][j] = grid[at][last];
        }
    }
    return grid == vec;
}

int main() {
    ios_base::sync_with_stdio(false);

    string s;
    while(cin >> s) {
        grid.push_back(s);
    }
    bool ans = solve();
    cout << (ans ? "YES" : "NO") << '\n';

    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,b,a) for(int i=b;i>=a;i--)
#define efo(i,u,v) for(int i=BB[u],v=B[BB[u]][1];i;v=B[i=B[i][0]][1])
#define mset(a,x) memset(a,x,sizeof(a))
using namespace std;
typedef long long ll;
char ch;
int read(){int n=0,p=1;for(ch=getchar();ch<'0' || '9'<ch;ch=getchar())if(ch=='-') p=-1;for(;'0'<=ch && ch<='9';ch=getchar()) n=n*10+ch-'0';return n*p;}
const int N=205,M=2e7+5;
int n,m,a[N],d[N<<1],pr[M];
bool b[M],c[M],bz[M];
void prep()
{
	mset(bz,1);
	bz[0]=bz[1]=0;
	fo(i,2,m)
	{
		if(bz[i]) pr[++pr[0]]=i;
		fo(j,1,pr[0])
		{
			ll x=(ll)i*pr[j];
			if(x>m) break;
			bz[x]=0;
			if(i%pr[j]==0) break;
		}
	}
}
const int V=N<<3,INF=1e9;
const int E=10*V*V;
int B0,BB[V],pos[V],B[E][2];
bool vis[V];
void link(int u,int v){B[++B0][1]=v,B[B0][0]=BB[u],BB[u]=B0;}
bool match(int x)
{
	if(vis[x]==1) return 0;
	vis[x]=1;
	efo(i,x,y)
		if(!pos[y] || match(pos[y]))
		{
			pos[y]=x;
			return 1;
		}
	return 0;
}
int main()
{
	n=read();
	fo(i,1,n) a[i]=read(),b[a[i]]=1,m=max(m,a[i]);
	++m;
	prep();
	fo(i,1,m) c[i]=b[i]^b[i-1];
	fo(i,1,m) if(c[i]) d[++d[0]]=i;
	fo(i,1,d[0])if(d[i]&1)
		fo(j,1,d[0])if(!(d[j]&1))
			if(bz[abs(d[i]-d[j])]) link(i,d[0]+j);
	int cnt=0,odd=0,even=0;
	fo(i,1,d[0]+d[0])
	{
		mset(vis,0);
		if(match(i)) ++cnt;
	}
	fo(i,1,d[0])if(d[i]&1) ++odd;else ++even;
	int ans=cnt+((odd-cnt)/2)*2+((even-cnt)/2)*2;
	if((odd-cnt)%2==1) ans+=3;
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 47360
#include <bits/stdc++.h>
#define maxn 105
#define int long long 
using namespace std;
int w[maxn], v[maxn], dp[100005];
main(){
	ios::sync_with_stdio ( false );
	cin.tie(0);
	int n, maxw;
	cin >> n >> maxw;
	for ( int i=0; i<n; ++i )
		cin >> w[i] >> v[i];
	for ( int i=0; i<n; ++i )
		for ( int j=maxw; j>=w[i]; --j )
			dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
	cout << dp[maxw] << '\n';
	return 0;
}


Measured memory_bytes: 1024
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

  public static void main(String[] args) {
    InputReader in = new InputReader(System.in);
    PrintWriter out = new PrintWriter(System.out);

    int n = in.nextInt();
    int k = in.nextInt();
    int[] h = new int[n];
    for (int i = 0; i < n; i++) {
      h[i] = in.nextInt();
    }

    h = mergeSort(h);

    int min = Integer.MAX_VALUE;

    for (int i = k - 1; i < n; i++) {
      min = Math.min(h[i] - h[i - k + 1], min);
    }

    out.println(min);

    out.close();
  }

  static class InputReader {
    public BufferedReader reader;
    public StringTokenizer tokenizer;

    public InputReader(InputStream stream) {
      reader = new BufferedReader(new InputStreamReader(stream), 32768);
      tokenizer = null;
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }
  }

  static void print(int[] arr) {
    Arrays.stream(arr).forEach(i -> System.out.print(i + " "));
    System.out.println();
  }

  public static int[] mergeSort(int[] a) {
    if (a.length <= 1)
      return a;

    int mid = a.length / 2;
    int[] left = new int[mid];
    int[] right = new int[a.length - mid];

    for (int i = 0; i < mid; ++i)
      left[i] = a[i];

    for (int i = mid; i < a.length; ++i)
      right[i - mid] = a[i];

    return merge(mergeSort(left), mergeSort(right));
  }

  public static int[] merge (int[] l, int[] r) {
    int[] merged = new int[l.length + r.length];

    int i = 0, j = 0, k = 0;
    while (i < l.length && j < r.length) {
      if (l[i] <= r[j])
        merged[k++] = l[i++];
      else
        merged[k++] = r[j++];
    }

    while (i < l.length)
      merged[k++] = l[i++];
    while (j < r.length)
      merged[k++] = r[j++];

    return merged;
  }

}



Measured memory_bytes: 40768
lengthList :: Integer -> [Integer] -> [Integer]
lengthList k [a2,a1] = [(a1+k-a2), (a2-a1)]
lengthList k (x:xs) = [(last xs) + k - x] ++ [x - (head xs)] ++ tail (lengthList k xs)

minLength :: Integer -> [Integer] -> Integer
minLength k xs = k - (maximum $ lengthList k xs)

toInt :: String -> Integer
toInt x = read x :: Integer

main = do
    kn <- getLine
    aList <- getLine
    let k = head $ map toInt $ words kn
        aList' = reverse $ map toInt $ words aList 
    print $ minLength k aList'

Measured memory_bytes: 106876
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
int main()
{
     ll n;
     cin>>n;
     ll ans[n];
     ll a[n-1];
     for(ll i=0;i<n-1;i++)   cin>>a[i];
     ans[0] = a[0];
     ans[n-1] = a[n-2];
     for(ll i=0;i<n-2;i++)   ans[i+1] = min(a[i],a[i+1]);
     ll sum = 0;
     for(ll i=0;i<n;i++)   sum+=ans[i];
     cout<<sum;
}

Measured memory_bytes: 384
/*   _/                _/                 _/_/_/   _/
  _/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
   _/     _/    _/   _/     _/    _/  _/_/_/     _/
  _/     _/    _/   _/     _/    _/  _/    _/   _/
   _/_/   _/_/       _/_/   _/_/      _/_/     _/ */
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
using ll=long long;
const int MOD=1e9+7;
const double pi=3.14159265358979323846;
const int inf=2e9;
const ll INF=1e18;
using P=pair<int,int>;
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  ll h,w;
  cin >> h >> w;
  if(h==1||w==1) {
    cout << 1 << endl;
  }
  else if(h*w%2) {
    cout << h*w/2+1 << endl;
  }
  else {
    cout << h*w/2 << endl;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
int main(){
  ll N; cin>>N;
  ll a=N%10;
  if(a==3) cout<<"bon"<<endl;
  else if(a==0 || a==1 || a==6 || a==8) cout<<"pon"<<endl;
  else cout<<"hon"<<endl;
}

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

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vllin3(a,b,c,n) vll (a)(n);vll (b)(n);vll (c)(n);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vlling(x,n) (x).assign(n,0);FOR(i,0,n-1){cin >>(x)[i];}
#define vlling2(a,b,n) (a).assign(n,0);(b).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i];}
#define vlling3(a,b,c,n) (a).assign(n,0);(b).assign(n,0);(c).assign(n,0);FOR(i,0,n-1){cin >>(a)[i]>>(b)[i]>>(c)[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;

vll w;
vll v;
vll d;
vvll m;

ll solve(ll i,ll vi){
	if(vi<=0) return 0;
	if(vi>d[i]) return 1e13;
	if(i==0){
		return (vi<=v[0]?w[0]:1e13);
	}
	if(m[i][vi]<1e13) return m[i][vi];
	return m[i][vi]=min(solve(i-1,vi),solve(i-1,vi-v[i])+w[i]);
}

signed main(){
	llin(n);
	llin(wm);
	vlling2(w,v,n);
	m.assign(n,vll(100001,1e13));
	d.assign(n,0);
	d[0]=v[0];
	FOR(i,1,n-1){
		d[i]=d[i-1]+v[i];
	}
	rFOR(i,0,100000){
		if (solve(n-1,i)<=wm){
			sal(i);
			return 0;
		}
	}
}


Measured memory_bytes: 79488
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main(){
  long long int n;
  cin>>n;
 long long int arr[n];
 for( long long int i=0;i<n;i++)cin>>arr[i];

 sort(arr,arr+n);
 int flag=1;

 for(long long int i=0;i<n-1;i++){
    if(arr[i]==arr[i+1]){
        flag=0;
        break;

    }



 }


 if(flag)cout<<"YES";
 else cout<<"NO";



 return 0;
}


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

#define rep(i, n) for (int i = 0; i < int(n); i++)
#define rrep(i, n) for (int i = int(n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

inline void yes() { cout << "Yes" << endl; exit(0); }
inline void no() { cout << "No" << endl; exit(0); }
inline i64 gcd(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); if (a % b == 0) return b; return gcd(b, a % b); }
inline i64 lcm(i64 a, i64 b) { if (min(a, b) == 0) return max(a, b); return a / gcd(a, b) * b; }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> inline void amax(T &x, T y) { x = max(x, y); }
template <typename T> inline void amin(T &x, T y) { x = min(x, y); }
template <typename T> inline T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

void solve() {
  int n;
  cin >> n;
  int x = n % 10;
  if (x == 3) {
    cout << "bon" << endl;
  } else if (x == 0 || x == 1 || x == 6 || x == 8) {
    cout << "pon" << endl;
  } else {
    cout << "hon" << endl;
  }
}


Measured memory_bytes: 3628
import std.algorithm;
import std.array;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

T read(T)() { return readln.chomp.to!T; }
T[] reads(T)() { return readln.split.to!(T[]); }
alias readint = read!int;
alias readints = reads!int;

void calc(int k, string s) {
    bool[string] d;
    for (int i = 1; i <= 5; i++) { // 長さ i の部分文字列を求める
        for (int j = 0; j < s.length; j++) { // s[j] からの部分文字列
            if (j + i > s.length) break;

            string t = s[j..j+i];
            d[t] = true;
        }
    }

    writeln(d.keys.sort().take(k)[$-1]);
}

void main() {
    string s = readln.chomp;
    int k = readint;

    calc(k, s);
}


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

typedef long long ll;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<ll,ll> pll;
typedef vector<bool> vb;
const ll oo = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-9;
#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define FOR(i,a,b) for (ll i = (a); i < (b); i++)
#define FORD(i,a,b) for (ll i = (b)-1; i >= (a); i--)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define has(c,i) ((c).find(i) != end(c))
#define DBGDO(X) ({ if(1) cerr << "DBGDO: " << (#X) << " = " << (X) << endl; })

bool go() {
	ll n; cin >> n;
	vl a(n);
	FOR(i,0,n) cin >> a[i];
	
	ll sum = 0, sum1 = 0;
	FOR(i,0,n) sum += a[i], sum1 += i+1;
	
	if (sum % sum1) return false;
	
	ll k = sum/sum1;

	FOR(i,0,n) {
		ll d = a[(i+1)%n] - a[i] - k;
		if (d > 0) return false;
		if (d % n) return false;
	}
	return true;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	cout << (go() ? "YES" : "NO") << endl;
	/*  6  9 12 10  8
	 *   3  3 -2 -2 -2
	 *   0  0 -5 -5 -5
	 *
	 *
	 *
	 *
	 */
}



Measured memory_bytes: 1024
import itertools
x = int(input())
count = 0
c=list(map(int, input().split()))
c_list = list(itertools.combinations_with_replacement(c, 3))
for i in range(len(c_list)):
  if c_list[i][0] != c_list[i][1] and c_list[i][1]!= c_list[i][2] and c_list[i][2] != c_list[i][0]:
    if c_list[i][0] + c_list[i][1]  > c_list[i][2] and c_list[i][1] + c_list[i][2] > c_list[i][0] and c_list[i][0] + c_list[i][2] > c_list[i][1]:
      count += 1
print(count)

Measured memory_bytes: 21244
#!/usr/bin/perl
use Data::Dumper;
my ($n) = map {$_ - 0} split(/\s+/o,<STDIN>);

if( $n==1 ){
  print "0\n"; exit(0);
}

my @nd = ();
$#nd = $n - 1;

for(my $i=0;$i<$n-1;$i++){
  my ($u,$v,$w) = map {$_ - 0} split(/\s+/o,<STDIN>);
  $u --;
  $v --;
  $nd[$u]->{l}->{$v} = $w;
  $nd[$v]->{l}->{$u} = $w;
}

my @t = (0);
$nd[0]->{dist} = 0;

while( $#t >= 0 ){
  my @newt = ();
  foreach my $tt (@t){
    foreach my $nn_i ( keys %{$nd[$tt]->{l}} ){
      my $w = $nd[$tt]->{l}->{$nn_i};
      push(@newt,$nn_i);
      $nd[$nn_i]->{dist} = $nd[$tt]->{dist} + $w;
      delete $nd[$nn_i]->{l}->{$tt};
    }
  }
  @t = (@newt);
}

#print Dumper(@nd);

for(my $i=0;$i<$n;$i++){
  my $r = ( $nd[$i]->{dist} % 2 );
  print "$r\n";
}

exit(0);



Measured memory_bytes: 64384
N, L = [int(s) for s in input().split(' ')]
ret = 0
start = L + 1 - 1
end = L + N - 1
if start * end <= 0:
    ret = [L + i - 1 for i in range(1, N + 1)]
elif start < 0:
    ret = [L + i - 1 for i in range(1, N)]
else:
    ret = [L + i - 1 for i in range(2, N + 1)]

print(sum(ret))



Measured memory_bytes: 3060