akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
using ll =long long;
#define SORT(a) sort((a).begin(),(a).end())
#define rSORT(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
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; }
void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
const ll INF = 1LL << 60;
//Write From this Line

// auto mod int
// https://youtu.be/L8grWxBlIZ4?t=9858
// https://youtu.be/ERZuLAxZffQ?t=4807 : optimize
// https://youtu.be/8uowVvQ_-Mo?t=1329 : division
const int mod = 1000000007;
struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const {
    return pow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
mint f(int n){
	if(n == 0 ) return 1 ;
	mint res ;
	res = f(n/2);
	res *= res;
	if(n % 2) res *= 2;
	return res; 
}
mint choose(int n, int a){
	mint x = 1 , y = 1 ;
	rep(i,a){
		x *= (n-i);
		y *= i+1 ;
	}
	return x/y ;
}
int main()
{
	ll n , a , b; 
	cin >> n >> a >> b; 
	mint ans = f(n);
	ans -= 1;
	ans -= choose(n,a);
	ans -= choose(n,b);
	cout << ans.x << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;
int main(void) {
  int i,j;
  int m,t,p,r;
  while(1){
    cin>>m>>t>>p>>r;
    if(m==0 && t==0 && p==0 && r==0)break;
    pair<pii,int> p[50];
    rep(i,t){
      p[i].second=i+1;
      p[i].first.first=p[i].first.second=0;
    }
    int penalty[50][10]={};//team,prob                       
    rep(i,r){
      int time,team,pn,judge;
      cin>>time>>team>>pn>>judge;
      team--;pn--;
      if(judge){//WA                                         
        penalty[team][pn]++;
      }else{//AC                                             
        p[team].first.first++;
        p[team].first.second-=time+penalty[team][pn]*20;
      }
    }
    sort(p,p+t);
    cout<<p[t-1].second;
    for(i=t-2;i>=0;i--)
      if(p[i].first.first==p[i+1].first.first &&
         p[i].first.second==p[i+1].first.second)
        cout<<"="<<p[i].second;
      else
        cout<<","<<p[i].second;
    cout<<endl;
  }
}

Measured memory_bytes: 3084
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 = sc.nextInt();
    List<Integer> list = new ArrayList<>();
    for (int i = 0; i < n; i++) {
      list.add(sc.nextInt());
    }

    Integer max = Collections.max(list);
    long maxCount = list.stream().filter(l -> l == max).count();

    list.forEach(l -> {
      if(l == max && maxCount == 1) {
        List<Integer> removedMaxList = list.stream()
          .filter(li -> li != l)
          .collect(Collectors.toList());
        System.out.println(Collections.max(removedMaxList));
      } else {
        System.out.println(max);
      }
    });
  }
}


Measured memory_bytes: 99408
//
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
//
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

// solution 
use std::cmp;
#[allow(unused_mut)]
#[allow(non_snake_case)]
fn main() {
    input!{
        N: usize,
        A: [u32; N],
    }
    let mut count = 0;
    for &a in A.iter() {
        let mut res = a;
        while res > 0 {
            if res&1 == 0 {
                count += 1;
            } else {
                break;
            }
            res >>= 1;
        }
    }
    println!("{}", count);
}


Measured memory_bytes: 4352
#!/usr/bin/env PyPy3 submit
import sys
from collections import deque
from itertools import *
 
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
 
x = LS()
 
for i,xx in enumerate(x):
    if xx == '0':
        print(i+1)
        exit() 

Measured memory_bytes: 9116
#ifdef LOCAL
//#define _GLIBCXX_DEBUG
#endif
//#pragma GCC target("avx512f,avx512dq,avx512cd,avx512bw,avx512vl")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> P;
typedef pair<int, int> Pi;
typedef vector<ll> Vec;
typedef vector<int> Vi;
typedef vector<string> Vs;
typedef vector<char> Vc;
typedef vector<P> VP;
typedef vector<vector<ll>> VV;
typedef vector<vector<int>> VVi;
typedef vector<vector<char>> VVc;
typedef vector<vector<vector<ll>>> VVV;
typedef vector<vector<vector<vector<ll>>>> VVVV;

#define REP(i, a, b) for(ll i=(a); i<(b); i++)
#define PER(i, a, b) for(ll i=(a); i>=(b); i--)
#define rep(i, n) REP(i, 0, n)
#define per(i, n) PER(i, n, 0)
const ll INF=1e18+18;
const ll MOD=1000000007;
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl;
#define YES(n) cout << ((n) ? "YES" : "NO") << endl;
#define ALL(v) v.begin(), v.end()
#define rALL(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a,b)
#define Each(a,b) for(auto &a :b)
#define rEach(i, mp) for (auto i = mp.rbegin(); i != mp.rend(); ++i)
#ifdef LOCAL
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbgmap(mp) cerr << #mp << ":"<<endl; for (auto i = mp.begin(); i != mp.end(); ++i) { cerr << i->first <<":"<<i->second << endl;}
#define dbgset(st) cerr << #st << ":"<<endl; for (auto i = st.begin(); i != st.end(); ++i) { cerr << *i <<" ";}cerr<<endl;
#define dbgarr(n,m,arr) rep(i,n){rep(j,m){cerr<<arr[i][j]<<" ";}cerr<<endl;}
#define dbgdp(n,arr) rep(i,n){cerr<<arr[i]<<" ";}cerr<<endl;
#else
#define dbg(...)
#define dbgmap(...)
#define dbgset(...)
#define dbgarr(...)
#define dbgdp(...)
#endif
#define out(a) cout<<a<<endl
#define out2(a,b) cout<<a<<" "<<b<<endl
#define vout(v) rep(i,v.size()){cout<<v[i]<<" ";}cout<<endl
#define Uniq(v) v.erase(unique(v.begin(), v.end()), v.end())
#define fi first
#define se second

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

template<typename T1, typename T2>
ostream &operator<<(ostream &s, const pair<T1, T2> &p) { return s<<"("<<p.first<<", "<<p.second<<")"; }

template<typename T>istream& operator>>(istream&i,vector<T>&v)
{rep(j,v.size())i>>v[j];return i;}

// vector
template<typename T>
ostream &operator<<(ostream &s, const vector<T> &v) {
    int len=v.size();
    for(int i=0; i<len; ++i) {
        s<<v[i];
        if(i<len-1) s<<"	";
    }
    return s;
}

// 2 dimentional vector
template<typename T>
ostream &operator<<(ostream &s, const vector<vector<T> > &vv) {
    int len=vv.size();
    for(int i=0; i<len; ++i) {
        s<<vv[i]<<endl;
    }
    return s;
}

int solve(){
    string s;
    ll cnt = 0;
    cin>>s;
    ll n = s.length();
    rep(i,n){
        cnt += s[i]-'0';
    }
    Yes(cnt%9==0);
    return  0;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout<<std::setprecision(10);
//    ll T;
//    cin>>T;
//    while(T--)
    solve();
}


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

int main() {
  int x,n;
  cin >> x >> n;
  if(n==0) {
    cout << x << endl;
    return 0;
  }
  vector<int> p(n);
  vector<pair<int,int>> d(n);
  rep(i,n){
    int tmp;
    cin >> tmp;
    p.at(i) = tmp;
    int dist = tmp - x;
    if (dist == 0) d.at(i) = make_pair(dist,-1);
    else d.at(i) = make_pair(abs(dist),dist/abs(dist));  // 小さいなら -1
//    cout << d.at(i).first << d.at(i).second << endl;
  }

  sort(d.begin(),d.end());
  if (d.at(0).first != 0) {
    cout << x << endl;
    return 0;
  }

  pair<int,int> check = make_pair(1,-1);
  for (int i=1; i<n; i++)  {
    if(d.at(i) != check){
      if(check.second == -1)  {
        cout << x - check.first << endl;
        return 0;
      }  else {
        cout << x + check.first << endl;
        return 0;
      }
    }
    if(check.second == -1) {
      check.second *= -1;
    }  else {
      check.first++;
      check.second *= -1;
    }
  }

  if(check.second == -1)  {
    cout << x-check.first << endl;
  }  else {
    cout << x+check.first << endl;
  }
}

Measured memory_bytes: 3616
omori_num = int(input())
omori_data = input()
add_total = 0

data = omori_data.split(" ")
for j in range(omori_num):
    add_total += int(data[j])

min_minus = 10000000

for i in range(omori_num):
    add_1 = 0
    add_2 = 0
    
    for j in range(i+1):
        add_1 += int(data[j])
    add_2 = add_total - add_1
    if ((min_minus > (add_1 - add_2)) and (add_1 >= add_2)):
        min_minus = add_1 - add_2
    elif ((min_minus > (add_2 - add_1)) and (add_2 >= add_1)):
    	min_minus = add_2 - add_1
print(min_minus)

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

int main() {
  int d, n;
  cin >> d >> n;
  if (d == 0) {
    if (n == 100) cout << 101 << "\n";
    else cout << n << "\n";
  }
  if (d == 1) {
    if (n == 100) cout << 10100 << "\n";
    else cout << n * 100 << "\n";
  }
  if (d == 2) {
    if (n == 100) cout << 1010000 << "\n";
    else cout << n * 100 * 100 << "\n";
  }
}

Measured memory_bytes: 3604
#include<stdio.h>
int main(void)
{
	int x,y,yy,xx,i,k;
	char c;
	scanf("%d %d %c",&x,&y,&c);
	yy=(y-2)/2+1;  xx=(x-2)/2+1;
	for(k=0;k<y;k++){
		for(i=0;i<x;i++){
			if(k==0 || k==y-1){
				if(i==0 || i==x-1)	printf("+");
				else printf("-");
			}
			
			else{
				if(i==0 || i==x-1)	printf("|");
				else if(k==yy && i==xx)	printf("%c",c);
				else printf(".");
			}
		}
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 2588
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String  tmp  = sc.nextLine();
        int N = Integer.parseInt(tmp);
        String rmp  = sc.nextLine();
        String S[] = new String[N];
        if (N%2!=0){
            System.out.println("No");
            System.exit(0);
        }


        for (int i =0; i < N;i++){
            S[i] = rmp.substring(i,i+1);
        }
        for (int i = 0;i<N/2;i++){
            if(!S[i].equals(S[i+N/2])){
                System.out.println("No");
                System.exit(0);
            }
        }

        System.out.println("Yes");


    }
}


Measured memory_bytes: 23764
#include<iostream>
#include<string>
#include<algorithm>
#include <stdio.h>
#include<iostream>
using namespace std;
int main(){
int N;
cin >>N;
int k=N;
int sum=0;
while(N>0){
  sum+=N%10;
  N/=10;
}
if(k % sum ==0) cout<<"Yes"<<endl;
else cout<<"No"<<endl;

}


Measured memory_bytes: 256
;; -*- coding: utf-8 -*-
(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 2))
    #-swank '(optimize (speed 3) (safety 0) (debug 0)))
  #+swank (progn (ql:quickload '(:cl-debug-print :fiveam))
                 (shadow :run)
                 (use-package :fiveam)))
#+swank (cl-syntax:use-syntax cl-debug-print:debug-print-syntax)

;; BEGIN_INSERTED_CONTENTS
(defmacro dbg (&rest forms)
  #+swank
  (if (= (length forms) 1)
      `(format *error-output* "~A => ~A~%" ',(car forms) ,(car forms))
      `(format *error-output* "~A => ~A~%" ',forms `(,,@forms)))
  #-swank (declare (ignore forms)))

(defmacro define-int-types (&rest bits)
  `(progn
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "UINT~A" b)) () '(unsigned-byte ,b))) bits)
     ,@(mapcar (lambda (b) `(deftype ,(intern (format nil "INT~A" b)) () '(signed-byte ,b))) bits)))
(define-int-types 2 4 7 8 15 16 31 32 62 63 64)

(declaim (inline println))
(defun println (obj &optional (stream *standard-output*))
  (let ((*read-default-float-format* 'double-float))
    (prog1 (princ obj stream) (terpri stream))))

(defconstant +mod+ 1000000007)

;; Body

(defun main ()
  (let* ((n (read))
         (k (read)))
    (println (+ 1 (- n k)))))

#-swank(main)


;; For Test
#+swank
(defun io-equal (in-string out-string &optional (func #'main))
  (labels ((ensure-last-lf (s)
             (if (and (> (length s) 0)
                      (eql (char s (- (length s) 1)) #\Linefeed))
                 s
                 (uiop:strcat s uiop:+lf+))))
    (equal (ensure-last-lf out-string)
           (with-output-to-string (out)
             (let ((*standard-output* out))
               (with-input-from-string (*standard-input* (ensure-last-lf in-string))
                 (funcall func)))))))

#+swank
(defun get-clipbrd ()
  (with-output-to-string (out)
    (run-program "C:/msys64/usr/bin/cat.exe" '("/dev/clipboard") :output out)))

#+swank (defparameter *this-pathname* (uiop:current-lisp-file-pathname))
#+swank (defparameter *dat-pathname* (uiop:merge-pathnames* "test.dat" *this-pathname*))

#+swank
(defun run (&optional thing (out *standard-output*))
  (let ((*standard-output* out))
    (etypecase thing
      (null ; Runs #'MAIN with the string on clipboard
       (with-input-from-string (*standard-input* (delete #\Return (get-clipbrd)))
         (main)))
      (string
       (with-input-from-string (*standard-input* (delete #\Return thing))
         (main)))
      (symbol (5am:run! thing))
      (pathname ; Runs #'MAIN with the string in a text file
       (with-open-file (*standard-input* thing)
         (main))))))

#+swank
(defun gen-dat ()
  (uiop:with-output-file (out *dat-pathname* :if-exists :supersede)
    (format out "")))

#+swank
(defun bench (&optional (out (make-broadcast-stream)))
  (time (run *dat-pathname* out)))

#+swank
(test :sample
  )


Measured memory_bytes: 15336
import sys
from heapq import heappush, heappop
from operator import itemgetter

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q = map(int, readline().split())
    work = [0] * N
    for i in range(N):
        s, t, x = map(int, readline().split())
        work[i] = (x, s - x, t - x)
    query = list(map(int, read().split()))

    work.sort(key=itemgetter(1), reverse=True)
    hq = []
    ans = [0] * Q

    for i, d in enumerate(query):
        while work and work[-1][1] <= d:
            heappush(hq, work[-1])
            work.pop()
        while hq and hq[0][2] <= d:
            heappop(hq)
        if not hq:
            ans[i] = -1
        else:
            ans[i] = hq[0][0]

    print(*ans, sep='\n')
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 136036
def main():
  N=int(input())
  A=list(map(int,input().split()))
  s=sum(A)
  Q=int(input())
  d=[0]*(10**5 +1)#各数字の個数
  ans=[]
  for i in A:
    d[i]+=1

  for i in range(Q):
    B,C=map(int,input().split())
    s += (C-B)*d[B]
    ans.append(s)
    d[C]+=d[B]
    d[B]=0

  print("\n".join(map(str, ans)))
  #BC入力ごとに出力するよりまとめて出力した方が倍くらい早い

if __name__ == "__main__":
    main()

Measured memory_bytes: 96684
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <deque>
#include <string>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <climits>
#include <cstdlib>
#define endl '\n'
#define ll long long
#define mod 1000000007
#define NCONS 201
#define PLUS 0
#define MINUS 1

using namespace std;

vector<int> cur_vec;
vector<int> vec(4);
string str;

void dfs()
{
	if (cur_vec.size() == 3)
	{
		int cur = vec[0];
		for (int i = 0; i < 3; i++)
		{
			if (cur_vec[i] == PLUS)
				cur += vec[i+1];
			else
				cur -= vec[i+1];
		}
		if (cur == 7)
		{
			cout << vec[0];
			for (int i = 0; i < 3; i++)
			{
				char temp;
				if (cur_vec[i] == PLUS)
					temp = '+';
				else
					temp = '-';
				cout << temp << vec[i + 1];
			}
			cout << "=7" << endl;
			exit(0);
		}
		return ;
	}

	for (int i = 0; i < 2; i++)
	{
		cur_vec.push_back(i);
		dfs();
		cur_vec.pop_back();
	}
}

int main(void)
{
	cin.tie(NULL); ios_base::sync_with_stdio(false);
	cin >> str;
	for (int i = 0; i < 4; i++)
		vec[i] = str[i] - '0';
	dfs();
	return 0;
}

Measured memory_bytes: 888
// https://cf16-final-open.contest.atcoder.jp/tasks/codefestival_2016_final_f?lang=en
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("Ofast")
typedef vector<int> vi;
typedef long long lint;
typedef unsigned int uint;
typedef pair<int, int> pii;
typedef pair<lint, lint> pll;
typedef unsigned long long ulint;
#define endl '\n'
#define fst first
#define sed second
#define pb push_back
#define mp make_pair
#define rint register int
#define SZ(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define reveal(x) cerr << #x << " = " << (x) << endl
#define rep(it, f, e) for (rint it = (f); it <= (e); ++it)
#define per(it, f, e) for (rint it = (f); it >= (e); --it)
#define repe(it, x) for (auto it = (x).begin(); it != (x).end(); ++it)
const int MOD = 1e9 + 7;
int dp[305][305][305];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int n, m;
	cin >> n >> m;
	dp[0][1][1] = 1;
	auto chkMOD = [&] (int & x) {
		x >= MOD && (x -= MOD);
	};
	rep (i, 0, m - 1) rep (j, 1, min(n, i + 1)) {
		rep (k, 1, j) if (dp[i][j][k] != 0) {
			chkMOD(dp[i + 1][j + 1][k] += dp[i][j][k] * (0ll + n - j) % MOD);
			chkMOD(dp[i + 1][j][k] += dp[i][j][k] * (0ll + j - k) % MOD);
			chkMOD(dp[i + 1][j][j] += dp[i][j][k] * (0ll + k) % MOD);
		}
	}
	cout << dp[m][n][n] << endl;
	return 0;
}

Measured memory_bytes: 108800
#include <bits/stdc++.h>
#define N 505
#define ll long long int 	
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
using namespace std;

ll n,m,ar[N],sum,t,W,w[N],v[N],flag;

ll dp[N][200005];

ll f(int ind,int val)
{
	if(dp[ind][val]!=-1)
		return dp[ind][val];
	if(val==0)
		return dp[ind][val]=0;
	if(ind==n+1)
	{
		return dp[ind][val]=1e12;
	}
	return dp[ind][val]=min(f(ind+1,val),f(ind+1,val-v[ind])+w[ind]);
}

int main()
{
	fast;
	cin>>n>>W;
	fo(i,1,n)
		cin>>w[i]>>v[i];
	memset(dp,-1,sizeof(dp));
	for(int i=0;i<=1e5+100;i++)
	{
		f(1,i);
		fo(j,1,n)
			if(dp[j][i]<=W && dp[j][i]!=-1)
				sum=i;
	}
	cout<<sum;



}



/*     cd onedrive\desktop\kod
cls

Sinav:21-22 aralik
Aciklama: Muhtemelen 25 aralik
*/

Measured memory_bytes: 789376
#include <bits/stdc++.h>
    using namespace std;
    typedef long long lint;
    typedef pair<int,int> pint;
    typedef vector<int> vint;
    #define rep(i, n) for(int i = 0; i < n; i++)
    #define rep2(elem, vec) for(auto elem: vec)
    #define SORT(V) sort((V).begin(),(V).end())
    #define RSORT(V) sort((V).rbegin(), (V).rend())
    lint gcd(int a,int b){return b?gcd(b,a%b):a;}
    lint lcm(int a,int b){return a*b/gcd(a,b);}
    lint comb(int a,int b){return b?comb(a-1,b-1)*a/b:1;}
    int dx[4] ={1,0,-1,0},dy[4] = {0,1,0,-1};
    int MOD = 1e9+7;

int main(){
    int N,K;
    cin >> N >> K;
    vint p(N);
    vector<double> q(N+1);
    rep(i,N)cin >> p[i];
    q[0] = 0.0;
    rep(i,N) q[i+1] =q[i] + (double)(p[i]+1)/2;
    
    double ans =0;
    rep(i,q.size()-K){
        ans = max(q[i+K]-q[i],ans);
    }
    cout << fixed << setprecision(6);
    cout << ans;
    return 0;
}


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

ll solve() {
    ll H, W, N, a;
    cin >> H >> W >> N;
    vector<vector<ll>> X(H, vector<ll>(W));
    ll k = 0;
    for ( int i = 1; i <= N; i++ ) {
        cin >> a;
        while ( a > 0 ) {
            ll h = k / W;
            ll w = h % 2 == 0 ? k % W : (W - 1 - k % W);
            X[h][w] = i;
            k++;
            a--;
        }
    }

    for ( int h = 0; h < H; h++ ) {
        for ( int w = 0; w < W; w++ ) {
            cout << X[h][w] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

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

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

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main() {
    /* Input */
    string N;
    cin >> N;
    
    /* Main Logic */      
    int sum = 0;
    rep(i, (int)N.size()) {
        sum = sum + ctoi(N[i]);
    }

    /* Output */
    if(sum % 9) cout << "No" << endl;
    else cout << "Yes" << endl;
    return 0;
}

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

struct circle{
	double r,x,y;
};

int main(){
	int n;
	scanf("%d",&n);
	for(int x=0;x<n;++x){
		circle a,b;
		scanf("%lf %lf %lf %lf %lf %lf",&a.x,&a.y,&a.r,&b.x,&b.y,&b.r);
		double d = sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
		if(d>a.r+b.r){
			cout<<0<<endl;
		}else if(a.r+d<b.r){
			cout<<-2<<endl;
		}else if(b.r+d<a.r){
			cout<<2<<endl;
		}else{
			cout<<1<<endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1244
#include<cstdio>
#include<iostream>
using namespace std;
int n, k;
bool a[10];
bool check(int x) {
	for (; x; x /= 10)
		if (a[x%10]) return false;
	return true;
}
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 0, t; i < k; ++i)
		scanf("%d", &t), a[t] = 1;
	while (!check(n)) ++n;
	printf("%d\n", n);
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main()
{
	int n,k,x[100];
	int i,sum;
	while(scanf("%d",&n)!=EOF)
	{
		sum=0;
		scanf("%d",&k);
		for(i=0;i<n;i++)
		{
			scanf("%d",&x[i]);
		}
		for(i=0;i<n;i++)
		{
			if((k-x[i])>x[i])
			sum+=2*x[i];
			else sum+=2*(k-x[i]);
		}
		printf("%d\n",sum);
	}
	return 0;
}

Measured memory_bytes: 128
#include <cstring>
#include <map>
#include <unordered_map>
#include <string>
#include <list>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <cstdio>
#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int ui;
typedef pair<int, int> pii;

int gi() {
    int a;
    scanf("%d", &a);
    return a;
}

ll gli() {
    ll a;
    scanf("%lld", &a);
    return a;
}

int a[500];
int r[500];
int res = 1, k, n;

void tr(int g) {
    if (res >= g)
        return;
    for (int i = 0; i < n; i++)
        r[i] = a[i] % g;
    sort(r, r+n);
    int t = 0;
    int L = 0, R = n-1;
    while (L <= R) {
        if (r[L] == 0) {
            L++;
            continue;
        }
        if (r[R] == g) {
            R--;
            continue;
        }
        int v = MIN(r[L], g-r[R]);
        t += v;
        r[L] -= v;
        r[R] += v;
    }
    if (t <= k)
        res = g;
}

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

    n = gi();
    k = gi();
    int s = 0;
    for (int i = 0; i < n; i++) {
        a[i] = gi();
        s += a[i];
    }

    for (int i = 1; i*i <= s; i++)
        if (s%i == 0) {
            tr(i);
            if (i*i != s)
                tr(s/i);
        }

    printf("%d\n", res);

    return 0;
}


Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
B = [0] * n

for i in range(n):
  B[i] = a[i] - (i+1)
  
B.sort()
b = B[(n-1)//2]
ans = 0
for i in range(n):
  ans += abs(B[i] - b) 
  
print(ans)

Measured memory_bytes: 26832
#!/usr/bin/env python3

from collections import deque
from queue import PriorityQueue


def solve(N, M, A, B):
    ans = 0
    # 日付順にソートする
    all_works = deque(sorted(zip(A, B), key=lambda x: x[0]))
    pq = PriorityQueue(maxsize=N)

    for d in range(1, M+1):
        # print('d=', d)
        # 今日が期限の仕事があれば追加
        while all_works and all_works[0][0] == d:
            work = all_works.popleft()
            # 最小値優先なのでマイナスをつける
            pq.put(-work[1])
        if not pq.empty():
            work = pq.get()
            ans -= work

    return ans


if __name__ == '__main__':
    N, M = map(int, input().split())
    A = [0] * N
    B = [0] * N
    for idx in range(N):
        A[idx], B[idx] = map(int, input().split())

    ans = solve(N, M, A, B)

    print(ans)


Measured memory_bytes: 22156
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
  int n;
  std::cin >> n;

  std::vector<int> l(n);
  for (int i = 0; i < n; ++i)
    std::cin >> l[i];

  std::sort(l.begin(), l.end(), std::greater<int>());

  int res = 0;
  for (int i = 0; i < n; ++i) {
    for (int j = i + 1; j < n; ++j) {
      int ok = j;
      int ng = n;
      while (std::abs(ok - ng) > 1) {
        int mid = (ok + ng) / 2;
        if (l[mid] > l[i] - l[j])
          ok = mid;
        else
          ng = mid;
      }
      res += ok - j;
    }
  }

  std::cout << res << std::endl;

  return 0;
}


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

using namespace std;

#define int long long
#define all(v) begin(v), end(v)
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define reps(i, s, n) for(int i = (int)(s); i < (int)(n); i++)
#define min(...) min({__VA_ARGS__})
#define max(...) max({__VA_ARGS__})

template<class T1, class T2> void chmin(T1 &a, T2 b){if(a>b)a=b;}
template<class T1, class T2> void chmax(T1 &a, T2 b){if(a<b)a=b;}

using pint = pair<int, int>;
using tint = tuple<int, int, int>;
using vint = vector<int>;

const int inf = 1LL << 55;
const int mod = 1e9 + 7;

#define MAX_N 3000

struct edge {
  int to, cost;
  edge(){}
  edge(int to, int cost):to(to), cost(cost){}
};

vector<edge> graph[MAX_N];
int mincost[MAX_N];

signed main()
{
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  int N, M, K;
  cin >> N >> M >> K;
  rep(i, M) {
    int a, b, l;
    cin >> a >> b >> l;
    --a, --b;
    graph[a].emplace_back(b, l);
    graph[b].emplace_back(a, l);
  }
  priority_queue<pint, vector<pint>, greater<pint> > que;
  fill(all(mincost), inf);
  rep(i, K) {
    int s;
    cin >> s;
    --s;
    que.emplace(0, s);
    mincost[s] = 0;
  }

  while(que.size()) {
    pint p = que.top(); que.pop();
    int v = p.second;
    if(mincost[v] < p.first) continue;
    for(edge e : graph[v]) {
      if(mincost[v] + e.cost < mincost[e.to]) {
	mincost[e.to] = mincost[v] + e.cost;
	que.emplace(mincost[e.to], e.to);
      }
    }
  }

  int ans = 0;
  rep(i, N) {
    ans = max(ans, mincost[i]);
    for(edge e : graph[i]) {
      ans = max(ans, (mincost[i]+mincost[e.to]+e.cost+1)/2);
    }
  }
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 8872
#include <bits/stdc++.h>
#include <numeric>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
#define Graph vector<vector<int>>
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)
#define inf 1000000321

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


int main(){
    ll N;
    cin >> N;
    vector<ll> A(N);
    ll mae = 0;
    ll ans = 0;
    for(int i = 0;i < N;i++){
        cin >> A[i];
    }
    for(int i = 1;i < N;i++){
        if(A[i-1] > A[i]){
            ans += abs(A[i] - A[i-1]);
            A[i] = A[i-1];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 4836
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define VAL 100000
#define ll  long long int
#define INF 10000000000000000LL
#define pll pair<long long , long long>
const int MAX=1e6+9;
const ll MOD=998244353;
const int TOT_PRIMES=19;
const int MAX_A=70;
using namespace std;
int a[MAX];
int b[MAX];
multiset<int>st[MAX] , mx;
int main() 
{

	ios_base::sync_with_stdio(false); 
    cin.tie(NULL);  
    int n;
    cin>>n;
   int arr[n+1];
   int k;
   cin>>k;
   for(int i=1;i<=n;i++)
    cin>>arr[i];
  sort(arr+1, arr+n+1);
  int ans=0;
  for(int i=1;i<=k;i++)
    ans=ans+arr[i];
  cout<<ans;
}

Measured memory_bytes: 50496
from collections import defaultdict

N,M,Q=map(int,input().split())

Goal=[defaultdict(int) for _ in range(N)]
for i in range(M):
    L,R=map(int,input().split())
    Goal[L-1][R-1]+=1

Accumlate = [[0]*(N+1) for i in range(N)]
for g in range(N):
    for l in range(N):
        Accumlate[g][l+1]+=Accumlate[g][l]+Goal[g][l]

ans_list=[]
for l in range(Q):
    ans=0
    L,R=map(int,input().split())
    for l in range(L-1,R):
        ans+=Accumlate[l][R]-Accumlate[l][L-1]
    ans_list.append(ans)

for m in range(Q):
    print(ans_list[m])

Measured memory_bytes: 100088
def gcd(a,b):
  while b!=0:
    a,b=b,a%b
  return a

N = int(input())
A= list(map(int,input().split()))
output=0
KA=[0 for i in range(N)]
LA=[0 for i in range(N)]
GCD = []

for k in range(1,N):
        LA[k]=gcd(A[k-1],LA[k-1])

for k in range(1,N):
        KA[k]=gcd(A[N-k],KA[k-1])


for k in range(N):
        GCD.append(gcd(LA[k],KA[N-k-1]))
output = max(GCD)
print(output)

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

int N, M, K[11], S[11][11], P[11];
int ans;

void dfs(int depth, vector<int> on_off){
    if( depth == N ){

        bool flg;
        for(int i=0;i<M;i++){
            int res = 0;
            flg = true;
            for(int j=0;j<K[i];j++){
                res += on_off[ S[i][j]-1 ];
            }
            if( res % 2 != P[i] ){
                flg = false;
                break;
            }
        }

        if( flg ) ans++;

        return;
    }

    on_off[depth] = 0;
    dfs(depth+1, on_off);
    on_off[depth] = 1;
    dfs(depth+1, on_off);
    return;
}

int main(){
    cin >> N >> M;
    for(int i=0;i<M;i++){
        cin >> K[i];
        for(int j=0;j<K[i];j++) cin >> S[i][j];
    }
    for(int i=0;i<M;i++)    cin >> P[i];

    ans = 0;
    vector<int> on_off(N);
    dfs(0, on_off);
    cout << ans << endl;
}

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

int main(void){
	ios::sync_with_stdio(false);
	int N, K, i, j,a;
	cin >> N;
	int h[N];
	for (i = 0; i < N; i++) {
		cin >> h[i];
	}	
	a = h[0];
	for (i = 0; i < N-1; i++) {
		if (h[i + 1] > h[i]) {
			a += h[i + 1] - h[i];
		}
	}

	cout << a;
	return 0;
}


Measured memory_bytes: 256
<?php
	$input = [];
	$count = [];
    for ($i=0; $i < 3; $i++) { 
    	fscanf(STDIN, "%d %d", $a, $b);
    	$input[$a]++;
    	$input[$b]++;
    }
    for ($j=1; $j <= 4; $j++) { 
    	$count[$input[$j]]++;
    }
    echo $count[1] == 2 && $count[2] == 2?"YES":"NO";

Measured memory_bytes: 4728
from math import factorial
import collections

def permutations_count(n, r):
    ''' 順列 '''
    return factorial(n) // factorial(n - r)


def combinations_count(n, r):
    ''' 組み合わせ '''
    return factorial(n) // (factorial(n - r) * factorial(r))


n,p = map(int, input().split())
S = input()
su = 0

if p > 6 or p == 3:

    lis = []
    amari = 1
    lis.append(int(S[-1]) % p)

    for i in range(2, len(S)+1):
        amari = (amari * 10) % p
        lis.append((int(S[-1*i]) * amari + lis[i-2]) % p)

    c = collections.Counter(lis)

    for k in c:
        if c[k] > 1:
            su += combinations_count(c[k], 2)

    su += c[0]

    print(su)

else:
    S = S[::-1]
    for i in range(len(S)):
        if int(S[i]) % p == 0:
            su += len(S)-i
    print(su)

Measured memory_bytes: 17728
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define R cin>>
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}void pr(){ln;}
template<class A,class...B>void pr(const A &a,const B&...b){cout<<a<<(sizeof...(b)?" ":"");pr(b...);}
template<class A>void PR(A a,ll n){rep(i,n)cout<<(i?" ":"")<<a[i];ln;}
const ll MAX=1e9+7,MAXL=1LL<<61,dx[8]={-1,0,1,0,-1,-1,1,1},dy[8]={0,1,0,-1,-1,1,1,-1};
typedef pair<ll,ll> P;

void Main() {
  ll n;
  R n;
  map<string,int> m;
  rep(i,n) {
    string s;
    R s;
    m[s]++;
  }
  pr("AC","x",m["AC"]);
  pr("WA","x",m["WA"]);
  pr("TLE","x",m["TLE"]);
  pr("RE","x",m["RE"]);
}

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


Measured memory_bytes: 3680
#include<bits/stdc++.h>
using namespace std;
#define REP(i,m,n) for(int i=(m);i<(n);i++)
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const int inf=1e9+7;
ll dp[100010];
int main(){
    int n,k;cin>>n>>k;
    vector<int>h(n);
    rep(i,n)cin>>h[i];
    REP(i,1,k+1){
        ll mi=1000000007;
        rep(j,i)mi=min(mi,abs(h[i]-h[j])+dp[j]);
        dp[i]=mi;
    }
    REP(i,k+1,n){
        ll mi=1000000007;
        rep(j,k)mi=min(mi,abs(h[i]-h[i-j-1])+dp[i-j-1]);
        dp[i]=mi;
    }
    cout<<dp[n-1]<<endl;
}

Measured memory_bytes: 1408
#pragma warning(disable:4786)
#pragma warning(disable:4996)
#include<list>
#include<bitset>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<functional>
#include<string>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<utility>
#include<fstream>
#include<sstream>
#include<cmath>
#include<stack>
#include<assert.h>
using namespace std;

#define MEM(a, b) memset(a, (b), sizeof(a))
#define CLR(a) memset(a, 0, sizeof(a))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define ABS(X) ( (X) > 0 ? (X) : ( -(X) ) )
#define S(X) ( (X) * (X) )
#define SZ(V) (int )V.size()
#define FORN(i, n) for(i = 0; i < n; i++)
#define FORAB(i, a, b) for(i = a; i <= b; i++)
#define ALL(V) V.begin(), V.end()
#define IN(A, B, C)  ((B) <= (A) && (A) <= (C))

typedef pair<int,int> PII;
typedef pair<double, double> PDD;
typedef vector<int> VI;
typedef vector<PII > VP;

#define AIN(A, B, C) assert(IN(A, B, C))

//typedef int LL;
typedef long long int LL;
//typedef __int64 LL;

int n, s[102], dp[10004];

int main()
{
	dp[0] = 1;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int a;
		scanf("%d", &a);
		for (int j = 10000; j >= 0; j--) {
			if (dp[j]) dp[j + a] = 1;
		}
	}
	int ans = 0;
	for (int i = 1; i <= 10000; i++) {
		if (i % 10 == 0|| dp[i] == 0) continue;
		ans = MAX(ans, i);
	}
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 256
fn read_nums() -> Vec<i32> {
  let mut buf = String::new();
  std::io::stdin().read_line(&mut buf);
  buf.split_whitespace().map(|x| x.parse::<i32>().unwrap()).collect()
}

fn main() {
  let nums = read_nums();
  let a = nums.get(0).unwrap();
  let b = nums.get(1).unwrap();
  if a == b {
    println!("{}", a * 2);
    return;
  } else if a > b {
    println!("{}", a * 2 - 1);
    return;
  } else {
    println!("{}", b * 2 - 1);
    return;
  }
}

Measured memory_bytes: 4352
#include <iostream>
#include <iomanip>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <cstring>
#include <map>

#define rep(i, N) for (int i = 0; i < (int)N; i++)
using namespace std;
typedef long long ll;
const ll LLINF = 9223372036854775807;
const int MOD = 1000000007;

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

  int result = 0;
  char w[4] = {'A', 'C', 'G', 'T'};
  int tmp = 0;
  rep(i, S.length()) {
    if (find(w, w+4, S[i])!=w+4) tmp++;
    else tmp = 0;
    result = max(result, tmp);
  }
  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
 
#define hell                         1000000007
#define hell2                        998244353
#define lcm(a,b)                     (a*b)/__gcd(a,b)
#define ll                           long long
#define vll                          vector<ll>
#define pll                          vector< pair<ll,ll> >
#define pb                           push_back
#define all(v)                       v.begin(),v.end()
#define F                            first
#define S                            second
#define rep(i,a,b)                   for(ll i=a;i<b;i++)
#define ret(x)                       return cout<<x,0;
#define endl                           '\n'
 
const ll MAX=1000005;
const ll SQN=330;
const ll LG=31;
const double PI=atan(1)*4;
using namespace std;

ll n,k;
ll a[MAX];

bool check(ll mid) {
	//all elements must be <=mid
	ll cost=0;
	rep(i,0,n) {
		cost+=(ll)ceil((1.0*a[i])/(1.0*mid))-1LL;
	}
	return cost<=k;
}

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

    cin >> n >> k;
    rep(i,0,n) cin >> a[i];
    ll l=1,r=1e9;
    while(r-l>1) {
    	ll mid=(l+r)>>1;
    	if(check(mid)) r=mid;
    	else l=mid;
    }
    if(check(l)) ret(l);
    ret(r);

}


Measured memory_bytes: 5316
class BinaryTree {
  constructor() {
    this.root = null;
    BinaryTree.Node = BinaryTree.Node || BinaryTree._createNodeClass();
  }

  static _createNodeClass() {
    return class BinaryTreeNode {
      constructor(key, parent = null, left = null, right = null) {
        this.key = key;
        this.parent = parent;
        this.left = left;
        this.right = right;
      }

      getChildrenNumber() {return Number(this.left !== null) + Number(this.right !== null);}

      isLeftChild() {return this.parent ? this.parent.left === this : null;}

      getLeftOrRight() {return this.isLeftChild() ? 'left' : 'right';}

      getSuccessor() {
        let n;
        if (this.right !== null) {
          n = this.right;
          while (n.left !== null) n = n.left;
        } else {
          n = this.parent;
          while (!n.isLeftChild && n.parent != null) n = n.parent;
        }
        return n;
      }
    };
  }

  insert(key) {
    if (this.root === null) {
      this.root = new BinaryTree.Node(key);
      return;
    }
    let x = this.root, y;
    let newNode = new BinaryTree.Node(key);
    while (x !== null) {
      y = x;
      x = x[key < x.key ? 'left' : 'right'];
    }
    newNode.parent = y;
    y[key < y.key ? 'left' : 'right'] = newNode;
  }

  find(key, n = this.root) {
    if (n === null || n.key === key) return n;
    return this.find(key, n[key < n.key ? 'left' : 'right']);
  }

  delete(key) {
    const n = this.find(key);
    const leftOrRight = n.getLeftOrRight();
    switch (n.getChildrenNumber()) {
    case 0:
      n.parent[leftOrRight] = null;
      break;
    case 1:
      n.parent[leftOrRight] = n.left || n.right;
      n.parent[leftOrRight].parent = n.parent;
      break;
    default:
      const skey = n.getSuccessor().key;
      this.delete(skey);
      n.key = skey;
    }
  }

  printByIneorder() {
    let str = '';
    const innerFunc = (n) => {
      if (n === null) return;
      innerFunc(n.left);
      str += ` ${n.key}`;
      innerFunc(n.right);
    }
    innerFunc(this.root);
    console.log(str);
  }

  printByPreorder() {
    let str = '';
    const innerFunc = (n) => {
      if (n === null) return;
      str += ` ${n.key}`;
      innerFunc(n.left);
      innerFunc(n.right);
    }
    innerFunc(this.root);
    console.log(str);
  }

  print() {
    this.printByIneorder();
    this.printByPreorder();
  }
}

(function main(){
  const lines = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n');
  const n = Number(lines.shift());

  const tree = new BinaryTree();
  lines.forEach(function(cmd) {
    switch (cmd.charAt(0)) {
    case 'i': tree.insert(Number(cmd.split(' ')[1])); break;
    case 'f': console.log(tree.find(Number(cmd.split(' ')[1])) ? 'yes' : 'no'); break;
    case 'd': tree.delete(Number(cmd.split(' ')[1])); break;
    default: tree.print();
    }
  });
})();



Measured memory_bytes: 203292
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Welcome to my source code!

int main() {
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    c *= 2;
    int n = max(x, y), price, ans = 1e9;
    for (int i = 0; i <= n; i++) {
        price = c * i + a * max(x - i, 0) + b * max(y - i, 0);
        ans = min(ans, price);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d",&x);
#define scs(x) scanf("%s",x);
#define scl(x) scanf("%lld",&x);
#define rep(i,s,e) for(int i=s; i<=e; ++i)
#define dep(i,s,e) for(int i=s; i>=e; --i)
typedef long long ll;
using namespace std;
ll a[200005],b[200005];
int main(){
	ll n,cou=0;
	scl(n);
	rep(i,1,n){scl(a[i]);b[a[i]]++;}
	rep(i,1,n)if(b[i]>=2)cou+=b[i]*(b[i]-1)/2;
	rep(i,1,n){
		ll v=cou;
		cou-=b[a[i]]*(b[a[i]]-1)/2;
		b[a[i]]--;
		if(b[a[i]]>0)cou+=b[a[i]]*(b[a[i]]-1)/2;
		pf("%lld\n",cou);
		cou=v;
		b[a[i]]++;
	}
}

Measured memory_bytes: 4736
#include<iostream>
using namespace std;
int main()
{
    int a,b,c,d;
    int x,y;
    cin >> a>> b>> c >> d;
    x=(a+d-1)/d;
    y=(b+c-1)/b;
    if(x>=y)
    {
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
    return 0;
}


Measured memory_bytes: 3600
x, y = map(int, input().split())

if abs(x) < abs(y) :
    if x >= 0 :
        if y >= 0 :
            print(- x + y)
        else :
            print(- x - y + 1)
    else :
        if y >= 0 :
            print(x + y + 1)
        else :
            print(x - y + 2)
elif abs(x) == abs(y) :
    if x * y < 0 :
        print(1)
    else :
        print(0)
else :
    if x > 0 :
        if y > 0 :
            print(x - y + 2)
        else :
            print(x + y + 1)
    else :
        if y > 0 :
            print(- x - y + 1)
        else :
            print(- x + y)

Measured memory_bytes: 38384
N = int(input())
H = list(map(int, input().split()))
marks = [0]*N
for i in range(N-1):
  if H[i]>=H[i+1]:
    marks[i]=1
c = 0
lis = []
for i in range(N):
  if marks[i]==1:
    c+=1
  else:
    lis.append(c)
    c=0
print(max(lis))
  

Measured memory_bytes: 14252
//20190616
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, x;
    cin >> n >> x;
    int i;

    vector<int> l;
    int tmp;
    for(i=0;i<n;i++){
        cin >> tmp;
        l.push_back(tmp);
    }

    vector<int> d;
    d.push_back(0);
    for(i=1;i<n+1;i++){
        d.push_back(d[i-1]+l[i-1]);
    }

    int count = 0;
    for(i=0;i<n+1;i++){
        if(d[i]<=x)count++;
        else break;
    }
    cout << count << endl;

}


Measured memory_bytes: 256
#pragma region macro
#include <bits/stdc++.h>
using i64 = int_fast64_t;
#define repeat(i, a, b) for(int i = (a); (i) < (b); ++(i))
#define rep(i, n) repeat(i, 0, n)

namespace std {
template <typename A, typename B>
string to_string(pair<A, B> p);

string to_string(const string &s) {
    return '"' + s + '"';
}

string to_string(const char *s) {
    return to_string((string)s);
}

string to_string(bool b) {
    return (b ? "true" : "false");
}

string to_string(vector<bool> v) {
    bool first = true;
    string res = "{";
    for(int i = 0; i < static_cast<int>(v.size()); i++) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(v[i]);
    }
    res += "}";
    return res;
}

template <size_t N>
string to_string(bitset<N> v) {
    string res = "";
    for(size_t i = 0; i < N; i++) {
        res += static_cast<char>('0' + v[i]);
    }
    return res;
}

template <typename A>
string to_string(A v) {
    bool first = true;
    string res = "{";
    for(const auto &x : v) {
        if(!first) {
            res += ", ";
        }
        first = false;
        res += to_string(x);
    }
    res += "}";
    return res;
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
};  // namespace std
#pragma endregion

void solve() {
    int h, n;
    std::cin >> h >> n;
    std::vector<std::pair<int, int>> magics(n);
    rep(i, n) std::cin >> magics[i].first >> magics[i].second;
    std::vector<std::vector<i64>> dp(n + 10, std::vector<i64>(h + 10100, 1e9));
    rep(i, n + 10) dp[i][0] = 0;
    // DPループ
    for(int i = 0; i < n; ++i) {
        for(int w = 0; w <= h + 10000; ++w) {
            dp[i + 1][w] = std::min(dp[i + 1][w], dp[i][w]);
            if(w >= magics[i].first) dp[i + 1][w] = std::min(dp[i + 1][w], dp[i + 1][w - magics[i].first] + magics[i].second);
        }
    }
    std::cout << *std::min_element(dp[n].begin() + h, dp[n].begin() + h + 10000) << std::endl;
}

int main() {
    // std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    solve();
    return 0;
}

Measured memory_bytes: 163936