akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>

int main()
{
    int N,M;
    int A[10000];
    scanf("%d %d\n", &N, &M);
  
   int i=0;
    while(scanf("%d",&A[i])==1)
    {
      i++;
    }
  
   int sum;
   sum = 0;
  
   for(int k=0; k<M; k++)
   {
     sum += A[k];
   }
   
   if(sum <= N)
   {
     printf("%d\n",N-sum);
   }
   else
   { 
     printf("-1\n");
   }
  
   return 0;
}

Measured memory_bytes: 1748
n = int(input())
a_lst = []
b_lst = []

for i in range(0, n):
    a, b = [int(elem) for elem in input().split()]
    a_lst.append(a)
    b_lst.append(b)

tmp = zip(b_lst, a_lst)
tmp = sorted(tmp)
b_lst, a_lst = zip(*tmp)   

flag = 0
sums = 0
for i in range(0, len(a_lst)):
    sums += a_lst[i]
    if sums > b_lst[i]:
        flag = 1
        break

if flag == 0:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 49144
#include <iostream>
#include <cstdlib>
#include<string>
#include<stdlib.h>
using namespace std;

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


int main()
{
    int n,k;
    int num=1;
    
    cin>>n>>k;
    for(int i=0;i<n;i++){
        if(num*2<=num+k)num*=2;
        else num+=k;
    }
    cout<<num<<endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<map>
#include<math.h>
#include<queue>
#include<deque>
#include<stack>
#include<cstdio>
#include<utility>
#include<set>
#include<list>
#include<cmath>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int INF = 1e9;
int main() {
	int n;
	cin >> n;
	int a[200010];
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	deque<int>deq;
	for (int i = 0; i < n; ++i) {
		if (i % 2 == 0)deq.push_back(a[i]);
		else deq.push_front(a[i]);
	}
	if (n % 2 == 0) {
		for (int i = 0; i < n; ++i) {
			cout << deq.at(i) << " ";
		}
	}
	else {
		for (int i = n-1; i >=0; --i) {
			cout << deq.at(i) << " ";
		}
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 3840
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var scanner = bufio.NewScanner(os.Stdin)

func nextString() string {
	scanner.Scan()
	return scanner.Text()
}

func nextInt() int {
	n, err := strconv.Atoi(nextString())
	if err != nil {
		fmt.Printf("strconv.Atoi failed: %v\n", err)
	}
	return n
}

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func stringifyArray(arr []int) string {
	return strings.TrimRight(fmt.Sprintf("%+v", arr)[1:], "]")
}

func main() {
	scanner.Split(bufio.ScanWords)

	n := nextInt()
	m := make([][]int, n)
	sizes := make([][]int, n)
	for i := 0; i < n; i++ {
		sizes[i] = []int{nextInt(), nextInt()}
		m[i] = make([]int, n)
	}
	// fmt.Println(sizes)

	for w := 1; w < n; w++ {
		for i := 0; i < n-w; i++ {
			j := i + w
			minBetweenIandJ := 10000000
			for k := i; k < j; k++ {
				// fmt.Println(i, j, k, m[i][k], m[k+1][j], sizes[i][0]*sizes[k][1]*sizes[j][1])
				minBetweenIandJ = min(minBetweenIandJ, m[i][k]+m[k+1][j]+sizes[i][0]*sizes[k][1]*sizes[j][1])
			}
			m[i][j] = minBetweenIandJ
		}
	}
	// for i := 0; i < len(m); i++ {
	// 	fmt.Println(stringifyArray(m[i]))
	// }
	fmt.Println(m[0][n-1])
}



Measured memory_bytes: 1164
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6;
int gi() {
	int w=0;bool q=1;char c=getchar();
	while ((c<'0'||c>'9') && c!='-') c=getchar();
	if (c=='-') q=0,c=getchar();
	while (c>='0'&&c <= '9') w=w*10+c-'0',c=getchar();
	return q? w:-w;
}
LL f[N],pre[N],suf[N],ans=1LL<<60;
#define lc (i<<1)
#define rc (lc|1)
inline void build(int i,int l,int r) {
	if (l==r) pre[i]=f[l]-l,suf[i]=f[r]+r;
	else {
		int mid=(l+r)>>1;
		build(lc,l,mid);
		build(rc,mid+1,r);
		pre[i]=min(pre[lc],pre[rc]);
		suf[i]=min(suf[lc],suf[rc]);
	}
}
inline LL Q1(int i,int l,int r,int R) {
	if (r<=R) return pre[i];
	int mid=(l+r)>>1;
	return R<=mid?Q1(lc,l,mid,R):min(pre[lc],Q1(rc,mid+1,r,R));
}
inline LL Q2(int i,int l,int r,int L) {
	if (L<=l) return suf[i];
	int mid=(l+r)>>1;
	return mid<L?Q2(rc,mid+1,r,L):min(suf[rc],Q2(lc,l,mid,L));
}
inline void modify(int i,int l,int r,int k,LL w) {
	if (l==r) pre[i]=w-l,suf[i]=w+r;
	else {
		int mid=(l+r)>>1;
		k<=mid?modify(lc,l,mid,k,w):modify(rc,mid+1,r,k,w);
		pre[i]=min(pre[lc],pre[rc]);
		suf[i]=min(suf[lc],suf[rc]);
	}
}
inline void solve(int i,int l,int r) {
	if (l==r) ans=min(ans,pre[i]+l);
	else {
		int mid=(l+r)>>1;
		solve(lc,l,mid);
		solve(rc,mid+1,r);
	}
}
int main()
{
	int n=gi(),Q=gi(),A=gi(),last=gi(),i,x;LL tag=0,p;
	for (i=1;i<=n;i++) f[i]=i==A?0:1LL<<60;
	build(1,1,n);
	while (Q--) {
		x=gi();
		p=min(x+Q1(1,1,n,x),Q2(1,1,n,x)-x);
		tag+=abs(x-last);
		modify(1,1,n,last,p-abs(x-last));
		last=x;
	}
	solve(1,1,n);
	printf("%lld\n",ans+tag);
	return 0;
}

Measured memory_bytes: 16640
#include <iostream>
#include <string>
#include <vector>
#include <iomanip>
#include <algorithm>
#include <queue>
#include <bitset>
#include <map>
#include <math.h>
#include <utility>

using namespace std;

const double PI = acos(-1);

int main(){

    string S, T;

    cin >> S >> T;

    for (int i=0; i < S.size(); i++){
        if(S[i] != T[i]){
            cout << "No" << endl;
            return 0;
        }
    }
    
    cout << "Yes" << endl;
    
    return 0;
}


Measured memory_bytes: 3052
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)


H,W = map(int,input().split())
A = ""
for i in range(H):
    s = input()
    A += s
C = Counter(A)

c4,c2=0,0

for _,x in C.most_common():
    c4 += x//4
    c2 += (x%4)//2

g4 = (H//2)*(W//2)
g2 = (H//2)*(W%2)+(W//2)*(H%2)

if c4-g4 < 0:
    print("No")
elif (c2+(c4-g4)*2)  < g2:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 38768
from collections import deque
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
NV = 3*n
edges = [[]for _ in range(NV)]


def to_v(i, j):
    return 3*i+j


for _ in range(m):
    u, v = list(map(lambda x: int(x)-1, input().split()))
    for j in range(3):
        edges[to_v(u, j)].append(to_v(v, (j+1) % 3))
s, t = list(map(lambda x: int(x)-1, input().split()))
init_v = to_v(s, 0)
INF = 10**18
dist = [INF]*NV
dist[init_v] = 0
next_v = deque([init_v])
while next_v:
    v = next_v.popleft()
    for v2 in edges[v]:
        if dist[v2] <= dist[v]+1:
            continue
        dist[v2] = dist[v]+1
        next_v.append(v2)

print(dist[to_v(t, 0)]//3 if dist[to_v(t, 0)] != INF else -1)


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

int main(){
  int N;
  cin >> N;
  long long result = 0;
  for(int i = 0; i < N; i++){
    long long a;
    cin >> a;
    while(a % 2 == 0){
      result++;
      a = a/2;
    }
  }
  cout << result << endl;
}


Measured memory_bytes: 256
#include <iostream>
using namespace std;
int a,b;
int main() {
	cin>>a>>b;a+=11;b+=11;a%=13;b%=13;
	if(a==b)cout<<"Draw"<<endl;
	if(a<b)cout<<"Bob"<<endl;
	if(a>b)cout<<"Alice"<<endl;
	return 0;
}

Measured memory_bytes: 256
#include "stdio.h"
#include "stdlib.h"

int main(int argc,char *argv[]){
    int i;
    float result;
    float num ;
    int flag = 0;

    // 整数の入力
    scanf("%f", &num);

    if ((int)num == 1){
        printf("1");
        return 0;
    }  

    if (( (int)num & 1 ) == 1){
        flag = 1;
    }

    i = num / 2 ;
    
    if(flag == 1){
        i = i + 1;
    }
    result = i / num;

  printf("%f",result);
   
}

Measured memory_bytes: 128
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

#define INF (1<<30)

int w,h,m[20][20],ans;
int dx[4]={0,1,0,-1},dy[4]={1,0,-1,0};

inline int in(int x,int y) {
	return 0<=x&&x<w&&0<=y&&y<h;
}

void dfs(int x,int y,int t) {
	if(t>10) return;
	for(int i=0;i<4;i++) {
		int nx=x+dx[i],ny=y+dy[i];
		if(in(nx,ny)&&m[nx][ny]!=1) {
			while(in(nx,ny)) {
				if(m[nx][ny]==1) {
					m[nx][ny]=0;
					dfs(nx-dx[i],ny-dy[i],t+1);
					m[nx][ny]=1;
					break;
				}else if(m[nx][ny]==3) {
					ans=min(ans,t);
					return;
				}
				nx+=dx[i],ny+=dy[i];
			}
		}
	}
}

int main() {
	int sx,sy;
	while(scanf("%d %d",&w,&h),w||h) {
		for(int j=0;j<h;j++) {
			for(int i=0;i<w;i++) {
				scanf("%d",&m[i][j]);
				if(m[i][j]==2) {
					m[i][j]=0;
					sx=i,sy=j;
				}
			}
		}
		ans=INF;
		dfs(sx,sy,1);
		printf("%d\n",ans!=INF?ans:-1);
	}
}

Measured memory_bytes: 1028
#include <iostream>
#include <algorithm>
#include <string>
#include <numeric>
#include <math.h>
#include <vector>
#include <boost/math/common_factor_rt.hpp>
using namespace std;
#define rep(i, n) for(int i = 0;i < n;i++)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define ll long long
 
int main(){
  int s;
  cin >> s;
  
  int l[1000100]={};
  l[s]+=1;
  
   rep(i, 1000100){
    if(s%2==0) s/=2;
    else s=3*s+1;
     
    l[s]+=1;
    //cout << l[s] << s << endl;
    if(l[s]==2){
      cout << i+2 << endl;
      break;
    }
  }

  
}

Measured memory_bytes: 4096
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define rep(N) for(int i=0;i<N;i++)
#define repj(N) for(int j=0;j<N;j++)
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define For(I,N) for(int I=0;I<N;I++)
#define cinone(N) int N;cin>>N;
#define scanfone(N) int N;cin>>N;
#define cinng(N,M) int N[M];for(int yiuytvnm=0;yiuytvnm<M;yiuytvnm++) cin>>N[yiuytvnm];
#define scanfng(N,M) int N[M];for(int qrwuoiq=0;qrwuoiq<M;qrwuoiq++) scanf("%d",&N[qrwuoiq]);
#define over(A) {cout<<A<<endl;exit(0);}
typedef unsigned long long ull;
const int inf=103974182;
using namespace std;
char a[20];

bool all(int l,int r)
{
	for(int i=r;i>=l;i--)
	{
		if(a[i]!='9') return false;
	}
	return true;
}

int main()
{
//	freopen("input.txt","r",stdin);
	scanf("%s",a);
	int len=strlen(a);
	int ans=0;
	if(all(0,len-1)) over((len*9));
	cout<<(len-1)*9+a[0]-!all(1,len-1)-'0'<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main() {
    int a , b , c;
    cin >> a >> b >> c;
    int count = 0;
    for(int i = a; i <= b; i++){
        if(c % i == 0){
            count++;
        }
    }
    cout << count << endl;
}


Measured memory_bytes: 3096
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;

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

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

map<int, int> counter;
vector<ll> A;

vector<int> derive_binary(ll k, int len) {
    vector<int> binary_k;
    while (k > 0) {
        if (k % 2) {
            binary_k.push_back(1);
        } else {
            binary_k.push_back(0);
        }
        k >>= 1;
    }

    while (len > 0 && (int) binary_k.size() < len) {
        binary_k.push_back(0);
    }
    return binary_k;
}

void print_binary(vector<int> &b) {
    cout << "0b";
    for (int i = 0; i < (int) b.size(); i++) {
        cout << b[i];
    }
    cout << endl;
}

int main(void) {
    int N;
    ll K;
    cin >> N >> K;

    int len = 0;

    A.resize(N);
    for (int i = 0; i < N; i++) {
        ll x;
        cin >> x;
        A[i] = x;

        int j = 0;
        while (x > 0) {
            if (x % 2) {
                counter[j + 1]++;
            }
            j++;
            x >>= 1;
        }
        chmax(len, j);
    }

    ll ideal = 0;
    for (int i = len; i >= 1; i--) {
        ideal <<= 1;
        if (counter[i] < (N + 1) / 2) {
            ideal += 1;
        }
    }

#ifdef DEBUG
    printf("len: %d, ideal: %lld\n", len, ideal);
#endif

    vector<int> binary_k = derive_binary(K, 0);
    vector<int> binary_i = derive_binary(ideal, len);

    if (binary_k.size() < binary_i.size()) {
        for (int i = binary_k.size(); i < (int) binary_i.size(); i++) {
            binary_k.push_back(0);
        }
    } else if (binary_k.size() > binary_i.size()) {
        for (int i = binary_i.size(); i < (int) binary_k.size(); i++) {
            binary_i.push_back(binary_k[i]);
            // binary_i.push_back(0);
        }
    }

    reverse(binary_k.begin(), binary_k.end());
    reverse(binary_i.begin(), binary_i.end());

#ifdef DEBUG
    cout << "k: ", print_binary(binary_k);
    cout << "ideal: ", print_binary(binary_i);
#endif

    int pos = 0;
    vector<int> binary_ans;
    for (; pos < (int) binary_k.size(); pos++) {
        if (binary_k[pos] > binary_i[pos]) {
            binary_ans.push_back(binary_i[pos]);
            pos++;
            break;
        } else if (binary_k[pos] < binary_i[pos]) {
            binary_ans.push_back(0);
        } else {
            binary_ans.push_back(binary_k[pos]);
        }
    }
    while (pos < (int) binary_i.size()) {
        binary_ans.push_back(binary_i[pos]);
        pos++;
    }
#ifdef DEBUG
    print_binary(binary_ans);
#endif

    ll x = 0;
    for (int i = 0; i < (int) binary_ans.size(); i++) {
        x <<= 1;
        if (binary_ans[i]) {
            x += 1;
        }
    }

#ifdef DEBUG
    printf("x: %lld\n", x);
#endif

    ll ans = 0;
    for (int i = 0; i < N; i++) {
        ans += x ^ A[i];
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 1024
/*A - Weather Prediction*/

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

int main(){

	string day;

	cin >> day;

	if(day == "Sunny")
		cout << "Cloudy";
	
	if(day == "Cloudy")
		cout << "Rainy";
	
	if(day == "Rainy")
		cout << "Sunny";

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
 
int main(){
    int X, A, B;
    cin >> X >> A >> B;
    int C = B-A ; 
    if ( C <= 0 )  
    cout << "delicious" <<endl;
    if ( C > 0 && C <= X)  
    cout << "safe" <<endl;
    if ( C > 0 && C > X)  
    cout << "dangerous" <<endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {

		int n = sc.nextInt();
		int[] a = new int[n];

		for (int i = 0; i < n; i++) {
			a[i] = sc.nextInt();
		}

		int max = 0;
		for (int num : a) {
			if (max < num) {
				max = num;
			}
		}
		int min = 1000;
		for (int num : a) {
			if (min > num) {
				min = num;
			}
		}

		System.out.println(max - min);

	}
}

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

int main(){
  ios_base::sync_with_stdio(false);
  
  string a = "YAKI";
  string b;
    
  cin >> b;
  
  int f = 1;
  for(int i=0;i<4;i++){
    if(a[i] != b[i]){
      f = 0;
      break;
    }
  }
  
  if(f){
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
  
  return 0;
} 

Measured memory_bytes: 256
import sys

def I(): return int(sys.stdin.readline().rstrip())

N = I()
A = [-I() for i in range(N)]

# Aの最大非増加部分列の長さを求めればOK

from bisect import bisect,bisect_left

def LIS(l):  #リストlのLISの長さを求める
    dp = [float('inf')]*(len(l)+1)
    dp[0] = -float('inf')
    for i in range(len(l)):
        j = bisect(dp,l[i])
        dp[j] = l[i]
    return bisect_left(dp,float('inf'))-1

print(LIS(A))

Measured memory_bytes: 77748
//set many funcs template
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define inf 1072114514
#define llinf 4154118101919364364
#define mod 1000000007

int max(int a,int b){if(a>b){return a;}return b;}
int min(int a,int b){if(a<b){return a;}return b;}
int zt(int a,int b){return max(a,b)-min(a,b);}
int round(int a,int b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
int ceil(int a,int b){if(a%b==0){return a/b;}return (a/b)+1;}
int gcd(int a,int b){int c;while(b!=0){c=a%b;a=b;b=c;}return a;}
int lcm(int a,int b){int c=gcd(a,b);a/=c;return a*b;}
int nCr(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
int fact(int a){int i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
int pow(int a,int b){int i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
long long llmax(long long a,long long b){if(a>b){return a;}return b;}
long long llmin(long long a,long long b){if(a<b){return a;}return b;}
long long llzt(long long a,long long b){return llmax(a,b)-llmin(a,b);}
long long llround(long long a,long long b){if((a%b)*2 >= b){return (a/b)+1;}return a/b;}
long long llceil(long long a,long long b){if(a%b==0){return a/b;}return (a/b)+1;}
long long llgcd(long long a,long long b){long long c;while(b!=0){c=a%b;a=b;b=c;}return a;}
long long lllcm(long long a,long long b){long long c=llgcd(a,b);a/=c;return a*b;}
long long llnCr(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=(a+1-i);r/=i;}return r;}
long long llfact(long long a){long long i,r=1;for(i=1;i<=a;i++){r*=i;}return r;}
long long llpow(long long a,long long b){long long i,r=1;for(i=1;i<=b;i++){r*=a;}return r;}
double dbmax(double a,double b){if(a>b){return a;}return b;}
double dbmin(double a,double b){if(a<b){return a;}return b;}
double dbzt(double a,double b){return dbmax(a,b)-dbmin(a,b);}
int sortfncsj(const void *a,const void *b){if(*(int *)a>*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int sortfnckj(const void *a,const void *b){if(*(int *)a<*(int *)b){return 1;}if(*(int *)a==*(int *)b){return 0;}return -1;}
int llsortfncsj(const void *a,const void *b){if(*(long long *)a>*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int llsortfnckj(const void *a,const void *b){if(*(long long *)a<*(long long *)b){return 1;}if(*(long long *)a==*(long long *)b){return 0;}return -1;}
int dbsortfncsj(const void *a,const void *b){if(*(double *)a>*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}
int dbsortfnckj(const void *a,const void *b){if(*(double *)a<*(double *)b){return 1;}if(*(double *)a==*(double *)b){return 0;}return -1;}

int main(void){
    int i,j,sl,tl,f;
    char s[64],t[64];
    scanf("%s%s",s,t);
    sl=strlen(s);
    tl=strlen(t);
    for(i=sl-tl;i>=0;i--){
        f=1;
        for(j=0;j<tl;j++){
            if(s[i+j]!='?'&&s[i+j]!=t[j]){f=0;break;}
        }
        if(f){
            for(j=0;j<tl;j++){s[i+j]=t[j];}
            for(j=0;j<sl;j++){if(s[j]=='?'){s[j]='a';}}
            printf("%s\n",s);
            return 0;
        }
    }
    printf("UNRESTORABLE\n");
    return 0;
}

Measured memory_bytes: 128
import std.stdio, std.conv, std.string;
import std.algorithm, std.array, std.container, std.typecons;
import std.numeric, std.math;
import core.bitop;

T RD(T = string)() { static string[] ss; while(!ss.length) ss = readln.chomp.split; string res = ss[0]; ss.popFront; return res.to!T; }
string RDR()() { return readln.chomp; }
T[] ARR(T)(in string str) { return str.split.to!(T[]); }
size_t[] MAKE_IDX(alias less = "a < b", Range)(Range range) { auto idx = new size_t[](range.length); makeIndex!(less)(range, idx); return idx;}
size_t MIN_POS(alias less = "a < b", Range)(Range range) { auto r = minPos!(less)(range); return range.length - r.length; }

bool INSIDE(T)(T x, T b, T e) { return x >= b && x < e; }

long mod = pow(10, 9) + 7;
void moda(ref long x, long y) { x = (x + y) % mod; }
void mods(ref long x, long y) { x = ((x + mod) - (y % mod)) % mod; }
void modm(ref long x, long y) { x = (x * y) % mod; }

struct UnionFind
{
	void init(long n) { par = new long[](n); foreach (i; 0..n) par[i] = i; }
	long root(long i) { return par[i] == i ? i : (par[i] = root(par[i])); }
	bool same(long i, long j) { return root(i) == root(j); }
	void unite(long i, long j) { i = root(i); j = root(j); if (i == j) return; par[i] = j; }
	long[] par;
}

void main()
{
	auto N = RD!long;
	auto H = RD!long;
	auto a = new long[](N);
	auto b = new long[](N);
	long bestA;
	foreach (i; 0..N)
	{
		a[i] = RD!long;
		bestA = max(bestA, a[i]);
		b[i] = RD!long;
	}
	auto index = MAKE_IDX!"a > b"(b);
	long ans;
	foreach (i; index)
	{
		if (b[i] <= bestA) break;

		H -= b[i];
		++ans;
		if (H <= 0) break;
	}
	if (H > 0)
	{
		ans += H / bestA + (H % bestA == 0 ? 0 : 1);
	}

	writeln(ans);
	stdout.flush();
}

Measured memory_bytes: 5372
import java.util.Scanner;

public class Main{
  public static void main(String[] args){
	  Scanner sc = new Scanner(System.in);
	  int n=sc.nextInt();
	  for(int i=1;i<=9;i++) {
		  if(n%i==0&&(n/i)<=9) {
			  System.out.println("Yes");
			  System.exit(0);
		  }
	  }
	  System.out.println("No");
  }
}


Measured memory_bytes: 36008
n = int(input())
h = list(map(int, input().split()))
last = h[-1]
for i in range(n - 2, -1, -1):
    now = h[i]
    if now > last:
        now -= 1
    if now > last:
        print("No")
        exit()
    last = now
print("Yes")

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

#define LL long long
typedef pair<int, int> pii;

template< typename T > inline void read(T &x)
{
    static char _c;
    static bool _f;

    x = 0;
    _f = 0;
    _c = getchar();

    while(_c < '0' || '9' < _c) {if(_c == '-') _f = true; _c = getchar();}
    while('0' <= _c && _c <= '9') {x = (x << 1) + (x << 3) + (_c & 15); _c = getchar();}
    if(_f) x = -x;
}

template < typename T > inline void Min(T &x, T y) {if(y < x) x = y;}
template < typename T > inline void Max(T &x, T y) {if(x < y) x = y;}


#define lowbit(x) ((x) & -(x))
#define lson l,mid,id<<1
#define rson mid+1,r,id<<1|1
#define ls id<<1
#define rs id<<1|1
#define MID(l,r) ((l)+(((r)-(l))>>1))
#define fi first
#define se second
#define mk make_pair
#define pb push_back

const int INF = 0x3f3f3f3f;
const double pi = (double) acos(-1.0);
const double eps = (double) 1e-8;
const int MOD = (int) 1e9 + 7;
//const int MOD = (int) 998244353;
const int maxn = (int) 1e5 + 20;
const int maxm = (int) 1e6 + 20;

inline int sig(double x) {return x < -eps ? -1 : eps < x;}
LL fp(LL a, LL n, LL MOD)
{
    if(n < 0) a = fp(a, MOD - 2, MOD), n = -n;
    LL res = 1; for(; n; n >>= 1, a = a * a % MOD) if(n & 1) res = res * a % MOD; return res;
}

void work()
{
    LL a, b, c;
    read(a), read(b), read(c);
    puts((4 * a * b < (c - a - b) * (c - a - b) && c - a - b >= 0) ? "Yes" : "No");
}

int main(int argc, char **argv)
{
#ifdef yukihana0416
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif // yukihana0416
//    get_prime();
    int tc = 1;
//    read(tc);
    for(int ca = 1; ca <= tc; ca++)
    {
//        printf("Case #%d: ", ca);
        work();
    }
    return 0;
}


Measured memory_bytes: 256
/*
 *
 */
#include <cstdio>
#include <iostream>
#include <map>

using namespace std;

int main(){
    //freopen("c5.in", "r", stdin);
    int H, W;
    string s;
    map <char, int> m;
    cin >> H >> W;
    for (int i = 0; i < H; ++i) {
        cin >> s;
        for (int j = 0; j < W; ++j) {
            m[s[j]]++;
            //cout << s[j] << ", " << m[s[j]] << endl;
        }
    }

    int area1, area2, area3;
    area1 = (H / 2) * (W / 2);
    area2 = (H % 2) * (W / 2) + (H / 2) * (W % 2);
    area3 = (H % 2) * (W % 2);

    //cout << "area" << area1 << ", " << area2 << ", " << area3 << endl;
    // area1
    for (auto x: m) {
        //cout << x.first << ", " << x.second << endl;
        int p = x.second / 4;
        int q = x.second % 4;
        m[x.first] = q;
        area1 -= p;
    }
    // area2
    if (area1 < 0) {
        area2 += 2 * area1;
        area1 = 0;
    }
    for (auto x: m) {
        //cout << x.first << ", " << x.second << endl;
        int p = x.second / 2;
        int q = x.second % 2;
        m[x.first] = q;
        area2 -= p;
    }
    // area3
    for (auto x: m) {
        //cout << x.first << ", " << x.second << endl;
        int p = x.second;
        if (p == 1) {
            area3 -= 1;
            break;
        }
    }

    if (area1 == 0 & area2 == 0 & area3 == 0) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }
    return 0;
}


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

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;
typedef pair < ll, ll > pll;
typedef pair < int, ll > pil;
typedef pair < ll, int > pli;
typedef pair < int, int > pii;
typedef unsigned long long ull;

#define F first
#define S second
#define en end()
#define bg begin()
#define rev reverse
#define mp make_pair
#define pb push_back
#define y1 y1234567890
#define um unordered_map
#define all(x) x.bg, x.en
#define sqr(x) ((x) * (x))
#define sz(x) (int)x.size()
#define sqrll(x) ((x) * 1ll * (x))
#define forn(i, n) for (int i = 1; i <= n; i++)

const ll inf = (ll)1e18;
const ll mod = (ll)1e9 + 7;
const double pi = acos(-1.0);
const double eps = (double)1e-9;

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

const int N = 100500;

int n, cnt[N];
vector < int > v;

int main() {
	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	//srand(time(NULL));

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

	//cout << setprecision(10) << fixed;

	for (int i = 2; i <= 10000; i++) {
		bool ok = 1;
		for (int j = 2; sqr(j) <= i; j++) {
			if (i % j == 0) {
				ok = 0;
				break;
			}
		}
		if (ok)
			v.pb(i);
	}

	for (int i = 0; i < sz(v); i++) {
		for (int j = i + 1; j < sz(v); j++)
			cnt[v[i] + v[j]] += 2;
		cnt[v[i] + v[i]]++;
	}

	while (cin >> n)
		cout << cnt[n + 1] << endl;

	return 0;
}

Measured memory_bytes: 3244
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>

using namespace std;

inline int read()
{
  int x=0,f=1;char ch=getchar();
  while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
  while (isdigit(ch)) {x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
  return x*f;
}

const int maxn = 2e5+1e4;

int a[maxn];
int n;
int b[maxn];
long long ans;

int main()
{
  scanf("%d",&n);
  for (int i=1;i<=n;i++) 
    a[i]=read();
  if (a[1]!=0){
  	cout<<-1;
  	return 0;
  }
  for (int i=n;i>=2;i--)
  {
    //cout<<ans<<endl;
  	/*if (a[i]==0) continue;
  	if (a[i]==1) 
	  ans++;
  	else
  	{
  	  if (a[i]==a[i-1]+1) ans++;
  	  else
  	  {
	  if (a[i]==2) 
	    {
  	  	  if (a[i-1]==1) 
			ans++;
  	  	  else 
			ans=ans+2;
		}
	    else
	      {
	      	cout<<-1;
	      	return 0;
		  }
	  }
	}*/
    if (a[i+1]-1>a[i]){
    	cout<<-1;
    	return 0;
	}
	if (a[i]>i-1) {
		cout<<-1;
		return 0;
	}
	if (a[i]!=a[i+1]-1) ans=ans+(long long)a[i];
  }
  cout<<ans;
  
  return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main()
{
	long long x,a,b,c,d;
	scanf("%lld",&x);
	c=100;
	b=1;
	a=0;
	while(1){
		c=c+b;
		b=c/100;
		a++;
		// printf("%lld\n",c);
		if(c>=x){
			printf("%lld\n",a);
			break;
		}
	}
	return 0;
}

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

using namespace std;

int main() {
    int n;
    cin >> n;
    int min = 1000;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        if (tmp % 10 != 0 && tmp < min) {
            min = tmp;
        }
        sum += tmp;
    }

    if (sum % 10 != 0) {
        cout << sum << endl;
    } else if (min != 1000) {
        cout << sum - min << endl;
    } else {
        cout << 0 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>

char affine(char c, int a, int b) {
  return (a * (c - 'a') + b) % 26 + 'a';
}

int checkUniq(int a, int b) {
  int i;
  char flag[26];
  for (i = 0; i < 26; ++i) {
    flag[i] = 0;
  }
  for (i = 0; i < 26; ++i) {
    flag[affine('a' + i, a, b) - 'a']++;
  }
  for (i = 0; i < 26; ++i) {
    if (flag[i] != 1) {
      return 0;
    }
  }
  return 1;
}

int thisCheck(const char s[], int a, int b) {
  return 's' == affine(s[0], a, b)
    && 'i' == affine(s[-1], a, b)
    && 'h' == affine(s[-2], a, b)
    && 't' == affine(s[-3], a, b);
}

int thatCheck(const char s[], int a, int b) {
  return 't' == affine(s[0], a, b)
    && 'a' == affine(s[-1], a, b)
    && 'h' == affine(s[-2], a, b)
    && 't' == affine(s[-3], a, b);
}

int search(const char line[], int a, int b) {
  int i;
  char y;
  for (i = 3; i < strlen(line); ++i) {
    if (' ' == line[i]) continue;
    y = affine(line[i], a, b);
    if ((('t' == y && thatCheck(line + i, a, b))
	 || ('s' == y && thisCheck(line + i, a, b)))
	&& checkUniq(a, b)) {
      return 1;
    }
  }
  return 0;
}

void printAffineLine(char s[], int a, int b) {
  int i;
  for (i = 0; i < strlen(s); ++i) {
    putchar(' ' == s[i] ? s[i] : affine(s[i], a, b));
  }
  puts("");
}

int main(int argc, char *argv[]) {
  int n;
  scanf("%d\n", &n);
  while (n--) {
    char line[512];
    int a, b, flag = 0;
    scanf("%[^\n]\n", line);
    for (a = 0; a < 100 && !flag; ++a) {
      for (b = 0; b < 100 && !flag; ++b) {
	if (search(line, a, b)) {
	  printAffineLine(line, a, b);
	  flag = 1;
	  continue;
	}
      }
    }
  }
  return 0;
}

Measured memory_bytes: 396
#include <cstdio>
using namespace std;

int n, a, cnt1 = 0, cnt2 = 0;
int main(void) {
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a);
		if (a % 2) cnt1++;
		if (!(a % 4)) cnt2++;
	}
	if ((cnt1 <= cnt2) || (cnt1 + cnt2 == n && cnt1 - 1 <= cnt2))
		printf("Yes");
	else
		printf("No");
}

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

using namespace std;
const int MOD=1000000007;
int k,n,num[10000009];
long long b,dp[200000][109][2];
string s;
int get_digit()
{
    fill(num,num+1000009,-1);
    int n=s.size();
    s=" "+s;
    for (int i=1; i<=n; i++)
        num[i]=(int)(s[i]-48);
    return n;
}
long long digit_dp(int idx, int sum, int tight)
{
    if (idx==n+1)
        if (sum%k==0)
            return 1;
        else
            return 0;
    if (dp[idx][sum][tight]!=-1)
        return dp[idx][sum][tight];
    int res=0,limit;
    if (tight==0)
        limit=num[idx];
    else
        limit=9;
    for (int i=0; i<=limit; i++)
    {
        int new_tight=1;
        if (i==limit&&tight==0)
            new_tight=0;
        res=(res+digit_dp(idx+1,(sum+i)%k,new_tight))%MOD;
    }
    dp[idx][sum][tight]=res%MOD;
    return res%MOD;
}
int main()
{
    cin>>s>>k;
    n=get_digit();
    memset(dp,-1,sizeof(dp));
    b=digit_dp(1,0,0);
    cout << ((b-1)+MOD)%MOD;
    return 0;
}


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

int main() {
  string s,t,u;
  int a,b;
  cin >> s >> t >> a >> b >> u;
  
  if(s == u){
    cout << a-1 << " " << b << endl;
  }
  else if(t == u){
    cout << a << " " << b-1 << endl;
  }
}


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

#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define MAX 1000000007

using namespace std;
int main(void){
  int n;
  cin >> n;
  vector<int> num(1000001,0);
  set<int> numlist,uniquelist;
  rep(i,n){
    int work;
    cin >> work;
    numlist.insert(work);
    num[work]++;
  }
  rep(i,1000001){
    if(num[i] == 1){
      uniquelist.insert(i);
    }
  }
  rep(i,1000001){
    num[i] = 0;
  }
  

  for(auto iter = numlist.begin();iter != numlist.end();++iter){
    for(int j=2*(*iter);j<1000001;j+=(*iter)){
      num[j]++;
    }
  }

  int ans = 0;
  for(auto iter = uniquelist.begin();iter != uniquelist.end();++iter){
    if(num[*iter] == 0)ans++;
  }
  cout << ans << endl;
}


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

using namespace std;
int main(){
   int a,b;
   cin>>a>>b;
   string str1 = "",str2 = "";
   // cout<<a<<" "<<b;
   for(int i=0;i<b;i++)
      str1 += to_string(a);
   for(int i=0;i<a;i++)
      str2 += to_string(b);
   // cout<<str1<<"\n"<<str2;7
   
   if(str1<str2) cout<<str1;
   else cout<<str2;
   return 0;
}

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

int main(){
    vector<int> a(5);
    cin >> a.at(0) >> a.at(1) >> a.at(2) >> a.at(3) >> a.at(4);
    int ans = 0;
    rep(i,5){
        if(a.at(i) == 0) ans = i+1;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 3624
/*
    Problem 20
    https://atcoder.jp/contests/abc077/tasks/arc084_a
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>
#include <string>
#include <cmath>
#include <iomanip>
#include <queue>
#include <list>
#include <set>
#include <stack>
#include <cctype>
#include <cmath>
#include <bitset>

using namespace std;
/* typedef */
typedef long long ll;
/* constant */
/* global variables */
/* function */
/* main */
int main(){
    int N;
    cin >> N;
    vector<int> A(N), B(N), C(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    for (int i = 0; i < N; i++) cin >> B[i];
    for (int i = 0; i < N; i++) cin >> C[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    vector<ll> candidateC(N+1);
    for (int i = 0; i < N; i++) {
        int ind = upper_bound(C.begin(), C.end(), B[i]) - C.begin();
        candidateC[i] = N - ind;
    }
    candidateC[N] = 0;
    for (int i = N; i > 0; i--) candidateC[i-1] += candidateC[i];
    ll ans = 0;
    for (int i = 0; i < N; i++) {
        int ind = upper_bound(B.begin(), B.end(), A[i]) - B.begin();
        ans += candidateC[ind];
    }
    cout << ans << '\n';
}


Measured memory_bytes: 2176
using System;
using System.Collections.Generic;
using System.Linq;
using console = System.Console;

namespace AtCoderTemplate
{
    public class App
    {
        public static void Main(string[] args)
        {
            var p = (IEnumerable<int>)(console.ReadLine().Split().Skip(1).Concat(console.ReadLine().Split()).Select(s=>int.Parse(s)).OrderBy(i=>i));
            p = p.Skip(1).Zip(p,(a,b)=>a-b);
            console.WriteLine(p.Aggregate(p.First(),(s,n)=>gcd(s,n)));
        }
        public static int gcd(int a,int b)
        {
            return b == 0 ? a : gcd(b, a % b);
        }
    }
}

Measured memory_bytes: 25952
import math

a,b,h,m = map(float,input().split())

deg_h = h*30 + 30*(m/60)
deg_m = m*6

rad_h = deg_h*(math.pi/180)
rad_m = deg_m*(math.pi/180)

h_x = a*math.sin(rad_h)
h_y = a*math.cos(rad_h)

m_x = b*math.sin(rad_m)
m_y = b*math.cos(rad_m)

len = math.sqrt(pow((h_x-m_x),2)+pow((h_y-m_y),2))

print(len)


Measured memory_bytes: 9440
#include<iostream>
#include<algorithm>
#include<cstring>
#define INF 111111111
using namespace std;

long int cost[1000][1000],ans[1000];
int memo[1000];
int n,k,m,a,b,c;

void solve(int s){
  ans[a] = 0;

  while(true){
    int k = -1;

    for(int i=1;i<=n;i++){
      if(!memo[i] && (k == -1 || ans[i] < ans[k])) k = i;
    }

    if(k == -1) break;

    memo[k] = 1;

    for(int i=1;i<=n;i++) ans[i] = min(ans[i],ans[k]+cost[i][k]);
  }
}

int main(){

  while(true){
    cin >> n >> k;
    if(!n && !k) break;

    for(int i=0;i<1000;i++){
      for(int j=0;j<1000;j++) cost[i][j] = INF;
    }

    for(int i=0;i<k;i++){
      cin >> m;

      if(m){
	cin >> a >> b >> c;
	if(cost[a][b] > c) cost[a][b] = cost[b][a] = c;
      }

      if(!m){
	cin >> a >> b;

	for(int i=0;i<1000;i++) ans[i] = INF;
	memset(memo,0,sizeof(memo));
	solve(a);

	if(ans[b] < INF) cout << ans[b] << endl;
	if(ans[b] == INF) cout << -1 << endl;
      }
    }
  }
}

Measured memory_bytes: 8984
n, m = gets.split.map(&:to_i)
patterns = []

def dfs(array, patterns, limit)
  if array.length == limit
    patterns << array
  else
    dfs(array + [0], patterns, limit)
    dfs(array + [1], patterns, limit)
  end
  if array.empty?
    patterns
  end
end
dfs([], patterns, n)
# p patterns # => [[0, 0], [0, 1], [1, 0], [1, 1]]

rules = []
m.times do
  k, *s = gets.split.map(&:to_i)
  rules << s
end
ps = gets.split.map(&:to_i)
ps.each_with_index do |pnum, index|
  judge = (pnum == 0 ? :even : :odd)
  rules[index] = {switches: rules[index], judge: judge}
end
# p rules # => [{:switches=>[1, 2], :judge=>:even}, {:switches=>[2], :judge=>:odd}]

rules.each do |rule|
  break if patterns.empty?
  patterns.map! {|pattern|
    count = 0
    rule[:switches].each do |switch|
      count += pattern[switch-1]
    end
    if rule[:judge] == :even
      count.even? ? pattern : nil
    elsif rule[:judge] == :odd
      count.odd?  ? pattern : nil
    end
  }.compact!
end
# p patterns
puts patterns.count


Measured memory_bytes: 3964
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for( int i=a; i<b; i++ )
#define REP(i,n) rep(i,0,n)
#define INF 1000000
using lli = long long int;
using ulli = unsigned long long int;
typedef pair<int, int> P;

struct edge{ int u, v; lli cost; };
struct DirectedGraph
{
  int vertex_num;
  int edge_num;
  vector<edge> edge_list;
  vector< vector<int> > adj_list;
	vector< vector<lli> > distance_matrix;
};

// rand settings
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_int_distribution<int> randint25(0, 25); // []
std::uniform_real_distribution<double> rand_01(0.0, 1.0); // uniform distribution [0, 1]

template <typename T>
vector<int> argsort(const vector<T> &v) {

  // initialize original index locations
  vector<int> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](int i1, int i2) {return v[i1] < v[i2];});

  return idx;
}

template<typename T>
void displayVector(vector<T> v)
{
	lli n = v.size();
	REP(i,n){
		cout << v[i] << " " ;
	}
	cout << endl;
}

// SA parameter
double Tinit = 10000.0; // start temprature
double alpha = 0.9; // exponential coolong parameter


double Eval(vector<int> x, vector< vector<int> > A){
  double score = 0;
	REP(d, x.size() ){
		score += A[d][ x[d] ];
	}
	return score;
}

double State_Prob(double dE, double T){
  if(dE <= 1){
    return 1.0;
  }
  else{
    return exp(-dE/T);
  }
}


vector<int> Neighbor( vector<int> x )
{
	vector<int> res;
	uniform_int_distribution<int> randintD(0, x.size()-1);
	int change_num = 5;
	REP(i, change_num){
		x.at( randintD(mt) ) = randint25(mt);
	}

	return x;
}

vector<int> SA_Methd(vector<int> start, vector< vector<int> > A){
  vector<int> s = start; // state
  double e = Eval(s, A); // enegy
  vector<int> s_opt = s;
  double e_opt = e;
 	vector<int> s_next;
	double e_next;

  double T = Tinit; // temprature;

  while(T>1){
    // neighbor
    s_next = Neighbor(s);
    e_next  = Eval(s_next, A);

    if(e_next < e_opt){
      e_opt = e_next;
      s_opt = s_next;
    }

    if( rand_01(mt) < State_Prob(e_next-e, T) ){
      s = s_next;
      e = e_next;
    }

    T = alpha * T; // exponential cooling
  }

  return s_opt;
}



int main(){

	int D; cin >> D;
	vector<int> c(26);
	REP(i, 26){ cin >> c[i]; }

	vector< vector<int> > score(D);
	REP(i, D){
		score[i].resize(26);
		REP(j, 26){ cin >> score[i][j]; }
	}

	vector<int> state(D);
	REP(i, D){ state[i] = i%26; }

	state =  SA_Methd(state, score) ;
	REP(i, D){ cout << state[i]+1 << endl; }
	return 0;
}

Measured memory_bytes: 4352
import sys
import math
from heapq import *

stdin=sys.stdin

ns = lambda:stdin.readline().rstrip()
ni = lambda:int(stdin.readline().rstrip())
nm = lambda:map(int,stdin.readline().split())
nl = lambda:list(map(int,stdin.readline().split()))

N,K=nm()
A=nl()


A.sort()
ans_max=0
MOD=10**9+7


def comb(n,k):
    return (math.factorial(n)//math.factorial(n-k)*math.factorial(k))

#clc comb at high speed

p=MOD
fact=[1,1]
factinv=[1,1]
inv=[0,1]
for i in range(2,N+1):
    fact.append((fact[-1]*i)%p)
    inv.append((-inv[p%i]*(p//i))%p)
    factinv.append((factinv[-1]*inv[-1])%p)


def comb2(n,r,p):
    if(r<0) or (n<r):
        return 0
    r=min(r,n-r)
    return fact[n]*factinv[r]*factinv[n-r]%p 



for i in range(K-1,N):
    ans_max+=A[i]*comb2(i,K-1,p)
    ans_max=ans_max%MOD

A.sort(reverse=True)
ans_min=0
for i in range(K-1,N):
    ans_min+=A[i]*comb2(i,K-1,p)
    ans_min=ans_min%MOD

print((ans_max-ans_min)%MOD)


Measured memory_bytes: 20812
#include<iostream>

using namespace std;

int main(){
  int i;

  pair<int, int> a[6] = { make_pair(3, 4), make_pair(4, 3), make_pair(1, 4),
                          make_pair(-1, 5), make_pair(3, -1), make_pair(2, 1) };

  for(; ; ){
    string s;
    cin >> s;
    if(s == "#") break;

    int p = 0;
    for(i = 0; i < (int)s.size() && p != -1; ++i)
      p = s[i] == '0' ? a[p].first : a[p].second;

    cout << (p == 1 ? "Yes" : "No") << endl;
  }

  return 0;
}

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

int main() {
  ll n, m;
  cin >> n >> m;
  vector<ll> h(n);
  vector<ll> tenbodai(n, 0);

  for (int i = 0; i < n; i++) {
    cin >> h.at(i);
  }
  ll ans = 0;
  for (int i = 0; i < m; i++) {
    ll a, b;
    cin >> a >> b;
    ll x = min(a, b);
    ll y = max(a, b);
    
    if (h.at(x-1) == h.at(y-1)) {
      tenbodai.at(x-1)++;tenbodai.at(y-1)++;
      continue;
    }
    else if (h.at(x-1) <= h.at(y-1)) {
      tenbodai.at(x-1)++;
      continue;
    }
    else {
      tenbodai.at(y-1)++;
      continue;
    }
  }

   for (int i = 0; i < n; i++) {
     if (tenbodai.at(i) == 0) ans++;
   }
   cout << ans << endl;
   return 0;
}


Measured memory_bytes: 4804
//#define _GLIBCXX_DEBUG
#include <iostream>
#include <bits/stdc++.h>
    
    
using namespace std;
#define ll long long
#define ld long double
#define  P pair<ll,ll>
#define FOR(i,n,m) for(ll i=n; i<(ll)m;i++)
#define FORr(i,m,n) for(ll i=n; i>=(ll)m; i--)
#define FORm(i,m) for(auto i=m.begin();i!=m.end();i++)
#define sortAl(v) sort(v.begin(),v.end())
#define sortAlr(v) sort(v.begin(),v.end()); reverse(v.begin(),v.end())
#define cout(n) cout<<fixed<<setprecision(n)

const int MOD = 1e9 + 7;

// a^b O(log b)
template <typename T>
T mypow(T a, T b) {
  if (b == 0) return 1;
  T tmp = mypow(a, b / 2);
  if (b % 2)
    return (((tmp * tmp) % MOD) * a) % MOD;
  else
    return (tmp * tmp) % MOD;
}

// nCk O(n + klogMOD)
long long comb(int n, int k) {
  long long res = 1;
  k = std::min(n - k, k);
  for (int i = n - k + 1; i <= n; i++) res = (res * i) % MOD;
  for (int i = 1; i <= k; i++)
    res = (res *
           mypow(static_cast<long long>(i), static_cast<long long>(MOD - 2))) %
          MOD;
  return res;
}

// nHk = n+k-1 C k
long long H(int n, int k) { return comb(n + k - 1, k); }

// v[i][j] := iCj
std::vector<std::vector<long long>> comb2(int n) {
  std::vector<std::vector<long long>> v(n + 1,
                                        std::vector<long long>(n + 1, 0));
  for (int i = 0; i < (int)v.size(); i++) {
    v[i][0] = 1;
    v[i][i] = 1;
  }
  for (int j = 1; j < (int)v.size(); j++) {
    for (int k = 1; k < j; k++) {
      v[j][k] = (v[j - 1][k - 1] + v[j - 1][k]);
      v[j][k] %= MOD;
    }
  }
  return v;
}

long long comb3(int n, int k) {
  static bool initiated = false;
  static std::vector<long long> fact(200010, 1), inv(200010, 1);
  if (!initiated) {
    initiated = true;
    for (int i = 2; i <= 200000; i++) {
      fact[i] = fact[i - 1] * i % MOD;
      inv[i] = mypow(fact[i], (long long)MOD - 2);
    }
  }
  if (k < 0 || n < k) {
    return 0;
  }
  long long ret = fact[n] * inv[k] % MOD;
  ret = ret * inv[n - k] % MOD;
  return ret;
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x,y;
    cin>>x>>y;
    ll a = (x+y)/3;
    ll tx = x-a, ty = y-a;
    ll ans = comb(tx+ty, tx);
    if((x+y)%3!=0 || tx<0 || ty<0) cout<<0<<endl;
    else{
        cout<<ans<<endl;
    }

}

Measured memory_bytes: 256
N = list( map( int, list( input())))
check = 0
ans = 0
for n in range( len(N)):
    if check == 1:
        ans += 9
        continue
    if N[n] == 9:
        ans += 9
        continue
    if n == 0:
        ans += N[0]-1
        check = 1
        continue
    ans += 8
    check = 1
print( max(ans, sum(N)))

Measured memory_bytes: 3060
#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

#define MOD 100000
int w, h;
int dp[110][110][2][2];

int cnt(int x, int y) {
  int ans = 0;
  ans = (ans + dp[x][y][0][0]) % MOD;
  ans = (ans + dp[x][y][0][1]) % MOD;
  ans = (ans + dp[x][y][1][0]) % MOD;
  ans = (ans + dp[x][y][1][1]) % MOD;
  return ans;
}
int main() {
  while (cin >> w >> h) {
    if (w == 0 && h == 0) break;
    dp[0][0][0][0] = 1;
    dp[1][0][0][0] = 1;
    dp[0][1][1][0] = 1;
    for (int i=0; i<w; i++) {
      for (int j=0; j<h; j++) {
        if (i == 0 && j == 0) continue;
        dp[i+1][j][0][0] = (dp[i][j][0][0] + dp[i][j][0][1]) % MOD;
        dp[i][j+1][1][0] = (dp[i][j][1][0] + dp[i][j][1][1]) % MOD;
        dp[i+1][j][0][1] = dp[i][j][1][0];
        dp[i][j+1][1][1] = dp[i][j][0][0];
      }
    }
    cout << cnt(w-1, h-1) << "\n";
  }
  return 0;
}

Measured memory_bytes: 3188
using System;
using System.Collections.Generic;
using System.Linq;
using static System.Console;
using static System.Math;
 
class Program
{
    static void Main()
    {
        var VE = ReadLine().Split().Select(int.Parse).ToArray();
        var V = VE[0];
        var E = VE[1];
 
        var G = new List<int>[V];
        for (int i = 0; i < G.Length; i++) G[i] = new List<int>();
 
        for (int i = 0; i < E; i++)
        {
            var st = ReadLine().Split().Select(int.Parse).ToArray();
            G[st[0]].Add(st[1]);
        }
 
        SetOut(new System.IO.StreamWriter(OpenStandardOutput()) { AutoFlush = false });
        foreach (var i in TopologicalSort(G)) WriteLine(i);
        Out.Flush();
    }
 
    static public int[] TopologicalSort(List<int>[] G)
    {
         var r = new int[G.Length];
        var visited = new bool[G.Length];
        var a = G.Length;


        Action<int> DFS = null;
        DFS = v =>
          {
              if (visited[v]) return;
              visited[v] = true;
              foreach (var u in G[v])
              {
                  DFS(u);
              }
              r[--a] = v;
          };


        for (int i = 0; i < G.Length; i++)
        {
            DFS(i);
        }
        return r;


    }
}


Measured memory_bytes: 23388
use std::io::*;
use std::str::FromStr;
 
/* 
The read function reads a string according to each one. 
*/
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char) 
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}


//main function
fn main() {
    let a:i64 = read();
    println!("{}",a/3);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i = 0; i < (int)(n); ++i)
#define repr(i, n) for(int i = n;i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define MOD 1000000007
 
typedef long long ll;
 

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

    int k,s,ans = 0;
    cin >> k >> s;

    for(int i = 0; i <= k; ++i){
        for(int j = 0; j <= k; ++j){
            int z = s - i - j;
            if(0 <= z && z <= k) ans++;
        }
    }

    cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <string>
#include <queue>

#define MY_SIZE_MAX 100001
#define MY_VALUE_MAX 100001

using namespace std;

int main()
{
	int a[3];
	cin >> a[0] >> a[1] >> a[2];
	int k;
	cin >> k;
	int sel = -1;
	int idx = -1;
	for( int i = 0; i < 3; ++i)
	{
		if( sel < a[i] )
		{
			sel = a[i];
			idx = i;
		}
	}
	for( int i = 0; i < k; ++i )
	{
		sel *= 2;
	}
	for( int i = 0; i < 3; ++i )
	{
		if( i == idx ){ continue; }
		sel += a[i];
	}
	cout << sel << endl;
	return 0;
}

Measured memory_bytes: 256