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

using i32 = int_fast32_t;
using i64 = int_fast64_t;
using u32 = uint_fast32_t;
using u64 = uint_fast64_t;
using f64 = double;
using f80 = long double;

#define FOR(v, a, b) for(i64 v = (a); v < (b); ++v)
#define FORE(v, a, b) for(i64 v = (a); v <= (b); ++v)
#define REP(v, n) FOR(v, 0, n)
#define REPE(v, n) FORE(v, 0, n)
#define REV(v, a, b) for(i64 v = (a); v >= (b); --v)
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define ITR(it, c) for(auto it = (c).begin(); it != (c).end(); ++it)
#define RITR(it, c) for(auto it = (c).rbegin(); it != (c).rend(); ++it)
#define EXIST(c,x) ((c).find(x) != (c).end())
#define fst first
#define snd second
#define UNIQ(v) (v).erase(unique(ALL(v)), (v).end())
#define bit(i) (1LL<<(i))

#ifdef DEBUG
#include <Mylib/Debug/debug.cpp>
#else
#define dump(...) ((void)0)
#endif

using namespace std;

template <typename I> void join(ostream &ost, I s, I t, string d=" "){for(auto i=s; i!=t; ++i){if(i!=s)ost<<d; ost<<*i;}ost<<endl;}
template <typename T> istream& operator>>(istream &is, vector<T> &v){for(auto &a : v) is >> a; return is;}
template <typename T> void pout(const T &value){std::cout << value << "\n";}
template <typename T, typename ...Args> void pout(const T &value, const Args&... args){std::cout << value << " ";pout(args...);}

template <typename T, typename U> bool chmin(T &a, const U &b){return (a>b ? a=b, true : false);}
template <typename T, typename U> bool chmax(T &a, const U &b){return (a<b ? a=b, true : false);}
template <typename T, size_t N, typename U> void fill_array(T (&a)[N], const U &v){fill((U*)a, (U*)(a+N), v);}
template <typename T> auto make_vector(int n, int m, const T &value){return vector<vector<T>>(n, vector<T>(m, value));}


struct Init{
  Init(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);
    cerr << fixed << setprecision(12);
  }
}init;



int main(){
  int N;

  while(cin >> N){
    N %= 10;
    
    if(N == 2 or N == 4 or N == 5 or N == 7 or N == 9) pout("hon");
    else if(N == 0 or N == 1 or N == 6 or N == 8) pout("pon");
    else pout("bon");
  }

  return 0;
}


Measured memory_bytes: 3660
n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
otarget = a[0]-1
ans = 0
ans += b[otarget]
for i in range(1, n):
	ntarget = a[i]-1
	ans += b[ntarget]
	if ntarget - otarget == 1:
		ans += c[otarget]
	otarget = ntarget
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
int n,a[100010];
int main(){
    cin>>n;
    if(n==1){
        cout<<"Yes"<<endl;
        return 0;
    }
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    bool ok=1;
    for(int i=n-2;i>=0;i--){
        if(a[i]>a[i+1])a[i]--;
        if(a[i]>a[i+1]){
            ok=0;
            break;
        }
    }
    if(ok)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
using namespace std;
int main() {
	int A, B, C, D, result;
	cin >> A;
	cin >> B;
	cin >> C;
	cin >> D;
	if (B > C&&D>A) {
		if (C <= A) {
			if (B >= D) {
				result = D - A;
				cout << result << endl;
			}
			else {
				result = B - A;
				cout << result << endl;
			}
		}else {
			if (B >= D) {
				result = D - C;
				cout << result << endl;
			}
			else {
				result = B - C;
				cout << result << endl;
			}
		}
	}
	else {
		cout << "0" << endl;
	}
}

Measured memory_bytes: 256
/*
    B - Unhappy Hacking (ABC Edit)
    https://atcoder.jp/contests/abc043/tasks/abc043_b
*/

#include <iostream>
#include <vector>

using namespace std;

#define ll long long
#define forn(i, s, n) for (int i = s; i < n; i++)
#define whilen(val, n) while(n-- && cin >> val)
#define r_1(v) cin >> v
#define r_2(v1, v2) cin >> v1 >> v2

int main() {
    vector<char> v;
    string s;
    cin >> s;
    forn(i, 0, s.length()) {
        if (s[i] != 'B') v.push_back(s[i]);
        else {
            if (!v.empty()) v.pop_back();
        }
    }
    if (s.size() <= 0) {
        cout << "(empty)";
        return 0;
    }

    forn(i, 0, v.size()) cout << v[i];

    return 0;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# coding: utf-8

def ri():
    return int(input())

def rl():
    return list(input().split())

def rli():
    return list(map(int, input().split()))

def main():
    a, b = rli()
    if (a + b) % 2 == 1:
        print("IMPOSSIBLE")
    else:
        print((a+b) // 2)


if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import java.util.Scanner;
import java.lang.Math;

public class Main {

	public static void main(String args[]){
		
		int n,r,p,c;
		int[] before,after;
		Scanner in = new Scanner(System.in);
		
		while(true){
			n = Integer.parseInt(in.next());
			r = Integer.parseInt(in.next());
			
			if(n==0 && r==0)break;
			
			before = new int[n];
			after = new int[n];
			
			for(int i=0;i<n;i++){
				before[i] = n-i;
			}
			
			for(int i=0;i<r;i++){
				p = Integer.parseInt(in.next())-1;
				c = Integer.parseInt(in.next());
				
				for(int j=0;j<n;j++){
					if(j < c ){
						after[j] = before[p+j];
					} else if( j < p+c ){
						after[j] = before[j-c];
					} else{
						after[j] = before[j];
					}
				}
				
				before = after;
				after = new int[n];
			}
			
			System.out.println(before[0]+"");
		}
		
		in.close();
	}
}

Measured memory_bytes: 36852
#include<bits/stdc++.h>
#include<bitset>
#include<random>
#include<time.h>

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;
const ll INF = 1LL << 60;

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



// Main Code

map<int, int> mp;

int main()
{
  int n;
  cin>>n;
  rep(i, 0, n)
  {
    int a;
    cin>>a;
    mp[a]++;
  }
  int ans = 0;
  for(auto x: mp)
  {
    int num = x.first;
    int co = x.s;
    if(num > co)
    {
      ans += co;
    }
    else if(num < co)
    {
      ans += (co - num);
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 4736
#include<bits/stdc++.h>
using namespace std;
int cnt[200000];
int main(){
  int N,Y,c,total;
  cin>>N>>Y;
  for(int i=0;i<=N;i++){
    for(int j=0;j<=N;j++){
      c=N-i-j;
      total=10000*i+5000*j+1000*c;
      if(total==Y&&c>=0){
        cout<<i<<' '<<j<<' '<<c<<endl;
        return 0;
      }
    }
  }
  cout<<' '<<-1<<' '<<-1<<' '<<-1<<endl;
}

Measured memory_bytes: 256
from itertools import accumulate
A = [a for a in range(1,41)]
A = list(accumulate(A))

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

N = int(input())
n = factorization(N)
cnt = 0
if N == 1:
    print(0)
else:
    for x in n:
        i = 0
        while x[1] >= A[i]:
            cnt += 1
            i += 1
    print(cnt)

Measured memory_bytes: 63640
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

typedef long double ld;

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

#define sz(x) ((int) (x).size())
#define TASK "text"

const int inf = (int) 1.01e9;
const long long infll = (long long) 1.01e18;
const ld eps = 1e-9;
const ld pi = acos((ld) -1);

#ifdef DEBUG
mt19937 mrand(300); 
#else
mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count()); 
#endif

int rnd(int x) {
  return mrand() % x;
}

void precalc() {
}

const int maxn = (int) 1e5 + 5;
int n, m;
vector<int> g[maxn];
vector<int> ids[maxn];

bool read() {
  if (scanf("%d%d", &n, &m) < 2) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    g[i].clear();
    ids[i].clear();
  }
  for (int i = 0; i < m; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    v--;
    u--;
    g[v].push_back(u);
    ids[v].push_back(i);
    g[u].push_back(v);
    ids[u].push_back(i);
  }
  return true;
}

int del[maxn];
vector<int> p;

void dfs(int v) {
  while (!g[v].empty()) {
    int u = g[v].back(), id = ids[v].back();
    if (del[id]) {
      g[v].pop_back();
      ids[v].pop_back();
      continue;
    }
    del[id] = true;
    dfs(u);
    p.push_back(v);
  }
}

void solve() {
  for (int i = 0; i < n; i++) {
    if (sz(g[i]) & 1) {
      printf("No\n");
      return;
    }
  }
  for (int v = 0; v < n; v++) {
    if (sz(g[v]) >= 6) {
      printf("Yes\n");
      return;
    }
  }
  {
    int cnt = 0;
    for (int v = 0; v < n; v++) {
      if (sz(g[v]) == 4) {
        cnt++;
      }
    }
    if (cnt >= 3) {
      printf("Yes\n");
      return;
    }
    if (cnt <= 1) {
      printf("No\n");
      return;
    }
  }
  for (int i = 0; i < m; i++) {
    del[i] = false;
  }
  int v = 0;
  while (sz(g[v]) != 4) {
    v++;
  }
  int u = v + 1;
  while (sz(g[u]) != 4) {
    u++;
  }
  p.clear();
  dfs(0);
  int vl = inf, vr = -inf;
  int ul = inf, ur = -inf;
  for (int i = 0; i < sz(p); i++) {
    if (p[i] == v) {
      vl = min(vl, i);
      vr = max(vr, i);
    }
    if (p[i] == u) {
      ul = min(ul, i);
      ur = max(ur, i);
    }
  }
  int x = (int) (vl <= ul && ul <= vr) + (int) (vl <= ur && ur <= vr);
  if (x == 1) {
    printf("No\n");
  } else {
    printf("Yes\n");
  }
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen(TASK ".in", "r", stdin));
  assert(freopen(TASK ".out", "w", stdout));
#endif
  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time %.2f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}


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

int Hash(string S, string T) {
	stack<char> ST;
	stack<int> ST2;
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '[') continue;
		if (S[i] == ']') {
			char C = ST.top();
			ST.pop();
			int A, B;
			A = ST2.top();
			ST2.pop();
			B = ST2.top();
			ST2.pop();
			int D;
			if (C == '+') D = A | B;
			if (C == '*') D = A & B;
			if (C == '^') D = A ^ B;
			ST2.push(D);
		}
		else {
			if ('a' <= S[i] && S[i] <= 'd') {
				ST2.push(T[S[i] - 'a'] - '0');
			}
			else {
				ST.push(S[i]);
			}
		}
	}
	return ST2.top();
}

int main() {
	string S;
	while (cin >> S) {
		if (S == ".") return 0;
		string T;
		cin >> T;
		int ANS1 = Hash(S, T), ANS2 = 0;
		for (T[0] = '0'; T[0] <= '9'; T[0]++) {
			for (T[1] = '0'; T[1] <= '9'; T[1]++) {
				for (T[2] = '0'; T[2] <= '9'; T[2]++) {
					for (T[3] = '0'; T[3] <= '9'; T[3]++) {
						if (ANS1 == Hash(S, T)) ANS2++;
					}
				}
			}
		}
		cout << ANS1 << ' ' << ANS2 << endl;
	}
}


Measured memory_bytes: 3136
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,v,sum=0;
    cin>>n;
    int x[n+5],xx[n+5];
    for(int i=0;i<n-1;i++)cin>>x[i];

    xx[0]=x[0];
    for(int i=1;i<n-1;i++)
    {
        xx[i]=min(x[i],x[i-1]);
    }
    xx[n-1]=x[n-2];

    for(int i=0;i<n;i++)
        sum+= xx[i];

    cout<<sum<<endl;
}


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

int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	bool frag = false;
	for (int i = 0; i < n; i++) {
		cin >> a[i];

		if (a[i] % 2 == 0) {
			if (a[i] % 3 != 0 && a[i] % 5 != 0) {
				frag = true;
			}
		}
	}

	if (frag) {
		cout << "DENIED" << endl;
	}
	else {
		cout << "APPROVED" << endl;
	}
	
}

Measured memory_bytes: 384
#pragma GCC optimize ("O3")
#include <iostream>
#include <iomanip>
#include <istream>
#include <ostream>
#include <sstream>
#include <iterator>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <bitset>
#include <utility>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <ctime>
#include <cctype>
#include <cstdlib>
#define IINF 1000000000
#define INF 9223372036854775807
#define MOD 998244353
#define mod 1000000007
#define INT_MAX_ 2147483647
#define EPS (1e-10)
#define REP(i, a, n) for (ll i = a; i < (ll)(n); i++)
#define REPE(i, a, n) for (ll i = a; i <= (ll)(n); i++)
#define rep(i,n)for (ll i = 0; i < (ll)(n); i++)
#define Endl endl
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define eb emplace_back
#define mmax(x,y)(x>y?x:y)
#define mmin(x,y)(x<y?x:y)
#define chmax(x,y) x=mmax(x,y)
#define chmin(x,y) x=mmin(x,y)
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define PI acos(-1.0)
#define me memset
#define bit(n,k) ((n>>k)&1)
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
typedef pair<int,int>Pin;
typedef pair<ll,ll>Pll;
template<class T> using V=vector<T>;
template<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T> >;
long long GCD(long long a, long long b) {return b?GCD(b,a%b):a;}
long long LCM(long long a, long long b) {return a/GCD(a,b)*b;}
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};
int ddx[8]={-1,0,1,0,1,1,-1,-1};
int ddy[8]={0,-1,0,1,1,-1,1,-1};
ll cmp1(pair<ll,ll> a,pair<ll,ll> b){
        if(a.se!=b.se)
        return a.se<b.se;
        else
        return a.fi>b.fi;
}
//----------------------------------------------------------------------

//----------------------------------------------------------------------
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    //-------------------------------  
    //ll begin_t=clock();
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //-------------------------------
    ll n;cin>>n;
    V<Pll>ab(n);
    for(ll i=0;i<n;i++){
        cin>>ab[i].fi>>ab[i].se;
    }
    if(n%2!=0){
        ll l,r;
        sort(all(ab));
        l=ab[n/2].fi;
        sort(all(ab),cmp1);
        r=ab[n/2].se;
        cout<<mmax(r-l+1,1)<<endl;
    }
    else{
        ll l1,r1,l2,r2;
        sort(all(ab));
        l1=ab[n/2-1].fi;
        l2=ab[n/2].fi;
        sort(all(ab),cmp1);
        r1=ab[n/2-1].se;
        r2=ab[n/2].se;
        double l = (double)(l1+l2)/2.0;
        double r = (double)(r1+r2)/2.0;
        cout<<(ll)((double)((double)r-(double)l)*2.0+1.0)<<endl;
    }
    //-------------------------------  
    //fclose(stdin);
    //fclose(stdout);
    //ll end_t=clock();cout<<"time="<<end_t-begin_t<<"ms"<<endl;
    //-------------------------------
    return 0;
}
//----------------------------------------------------------------------



















































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

int main()
{

        int a[32] = { 1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51 };

        int K;
        cin >> K;
        cout << a[K-1] << endl;


}


Measured memory_bytes: 256
from collections import defaultdict

D,G=map( int, raw_input().split() )
P=[ map( int, raw_input().split() ) for i in range(D) ] 

N=10**6
dp= [  float("inf") for i in range(N+1) ]
dp[0]=0

for idx, x  in enumerate(P):
	m=idx+1	#money
	p,c=x[0], x[1]/100
	for i in range(N,-1,-1):
		if dp[i]!=float("inf"):
			for j in range(p,-1,-1):	# j= problems count   , idx = index
				if j==p:
					dp[i+m*j+c]=min( dp[i+m*j+c] , dp[i]+j )
				else:
					dp[i+m*j]=min( dp[i+m*j] , dp[i]+j )



ans=float("inf")

for i in range(G/100,N):
	ans=min(ans, dp[i])

print ans



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

int main(){
	string str;
	
	getline(cin, str);
	
	for(int i=str.size()-1; i>=0; i--){
		if(str[i] >= 'A' && str[i] <= 'Z') str[i] += 'a' - 'A';
		else
		if(str[i] >= 'a' && str[i] <= 'z') str[i] += 'A' - 'a';
	}
	
	cout << str << endl;
	
	return 0;
}


Measured memory_bytes: 3160
#include <bits/stdc++.h>
using namespace std;
int read(){
	int sum=0,f=1;
	char s=getchar();
	while (s<'0' or s>'9'){
		if (s=='-')f=-1;
		s=getchar();
	}
	while (s>='0' and s<='9'){
		sum=sum*10+s-'0';
		s=getchar();
	}
	return sum*f;
}
int main(){
	long long x,a;
	a=100;
	cin>>x;
//x=1e18;
	long long cnt=0;
	while (a<x){
		cnt++;
		long long d=a/100;
//		cout<<d<<endl;
		a+=d;
	}
	cout<<cnt<<endl;
	return 0;
}



Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool chmax(T &a, T b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
inline bool chmin(T &a, T b)
{
    if (a > b)
    {
        a = b;
        return 1;
    }
    return 0;
}
typedef long long int ll;
    
#define EPS (1e-7)
#define INF (1<<30)
#define LLINF (1LL<<60)
#define PI (acos(-1))
#define MOD (1000000007)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

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

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> h(n);
    for(int i=0;i<n;i++){
        cin>>h[i];
    }
    for(int i=n-1;i>=1;i--){
        int merge = h[i-1]-h[i];
        if(merge > 0){
            if(merge==1){
                h[i-1]--;
            }else{
                cout<<"No"<<endl;
                return 0;
            }
        }
    }
    // for(auto a:h){
    //     cout<<a<<endl;
    // }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 640
import sys
from collections import deque

import numpy as np

input = sys.stdin.readline


def bfs(H, W, maze, dist, sh, sw):
    queue = deque([[sh, sw]])
    dist[sh][sw] = 0
    while queue:
        h, w = queue.popleft()
        for i, j in [(1, 0), (0, 1)]:
            next_h, next_w = h + i, w + j
            if not ((0 <= next_h <= H - 1) and (0 <= next_w <= W - 1)):
                continue
            if maze[next_h][next_w] and (dist[next_h][next_w] == -1):
                dist[next_h][next_w] = dist[h][w] + 1
                queue.append([next_h, next_w])


def main():
    H, W = map(int, input().split())
    A = np.full((H, W), False, dtype=bool)
    for i in range(H):
        A[i] = [True if s == "#" else False for s in input().rstrip()]

    n_path = np.sum(A) - 1
    dist = [[-1] * W for _ in range(H)]
    bfs(H, W, A, dist, 0, 0)

    if dist[H-1][W-1] == n_path:
        print("Possible")
    else:
        print("Impossible")


if __name__ == "__main__":
    main()


Measured memory_bytes: 12192
struct Scanner {
	handle: std::io::Stdin,
	buffer: std::collections::VecDeque<String>
}

impl Scanner {
	fn new() -> Scanner {
		Scanner {
			handle: std::io::stdin(),
			buffer: std::collections::VecDeque::new()
		}
	}
	fn next<T: std::str::FromStr>(&mut self) -> Result<T, T::Err> {
		if self.buffer.len() == 0 {
			loop {
				let mut available = String::new();
				self.handle.read_line(&mut available).unwrap();
				self.buffer = available.split_whitespace().map(String::from).collect();
				if self.buffer.len() > 0 {
					break;
				}
			}
		}
		T::from_str(&self.buffer.pop_front().unwrap())
	}
}

fn main() {
	let mut scanner = Scanner::new();
	let a: isize = scanner.next().unwrap();
	let b: isize = scanner.next().unwrap();
	println!("{}",a*b);
}


Measured memory_bytes: 2120
//***The night is the darkest just before the dawn***
 
#include<bits/stdc++.h>
using namespace std;
 
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define pb push_back
#define ll long long 
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i,n) for(i=0;i<n;i++)
#define forn(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define for1(i, n) for (ll i = 1; i <= (ll)(n); ++i)
#define ford(i, n) for (ll i = (ll)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (ll i = (ll)(a); i <= (ll)(b); ++i)
#define fora(it,x) for(auto it:x)
#define PI 3.14159265
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define endl "\n"
 
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpi;
typedef vector<vi> vvi;
typedef long long i64;
typedef vector<i64> vi64;
typedef vector<vi64> vvi64;
typedef pair<i64, i64> pi64;
typedef long double ld;
 
template<class T> bool uin(T &a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool uax(T &a, T b) { return a < b ? (a = b, true) : false; }

ll a[100002];
ll m=1e9+7;

ll fpow(ll a,ll p){
    if(p==0) return 1;
    ll b=fpow(a,p/2);
    if(p%2==0) return((b*b)%m);
    else return((((b*b)%m)*a)%m);
}
int main(){
    ll n,k,ans=0;
    cin>>n>>k;

    for(ll i=k;i>=1;i--){
        ll s=0,c=0;
        for(ll j=2*i;j<=k;j+=i){
            s=(s+a[j])%m;
            c++;
        }
        ll p=fpow(c+1,n);
        p=(p-s+m)%m;
        a[i]=p;
        p=(p*i)%m;
        ans=(ans+p)%m;
    }
    cout<<ans;
}

Measured memory_bytes: 4400
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <random>
#include <chrono>

using namespace std;
using namespace __gnu_pbds;

#define endl '\n'

typedef long long ll;
typedef pair<int, int> pii;
//typedef tree<int,null_type,less<int>,rb_tree_tag, tree_order_statistics_node_update> indexed_set;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	
	int a, b;
	cin >> a >> b;
	
	string s1 = "", s2 = "";
	
	for(int i = 0; i < a; i++)
		s1 += (char)(b + '0');

	for(int i = 0; i < b; i++)
		s2 += (char)(a + '0');
	
	if(s1 < s2)
		cout << s1 << endl;
	else
		cout << s2 << endl;
	return 0;
}


Measured memory_bytes: 256
n = int(input())
s = input()
ans = 0
for i in range(1000):
    i = str(i).zfill(3)
    f = True
    x = -1
    for j in range(3):
        x = s.find(i[j],x+1)
        f = f and bool(x >= 0)
    ans += f
print(ans)


Measured memory_bytes: 9256
#include <iostream>
#include <algorithm>


using namespace std;

typedef long long ll;

int main(){

    int n; 
    cin >> n;

    ll sum = 0;
    int mn = 0;

    for (int i = 0; i < n; i++){
        int temp;
        cin >> temp;

        mn = max(mn, temp);
        sum += temp;
    }

    sum -= (mn / 2);

    cout << sum << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;

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

template <typename T> inline string toString(const T &a){ostringstream oss; oss<<a; return oss.str();};

int main(){
    int n; cin>>n;
    string s; cin>>s;

    for(int bit=0; bit<(1<<2); bit++){
        string ans(n+10, 'a');

        if(bit & 1) ans[0]='W';
        else ans[0]='S';

        if(bit & 2) ans[1]='W';
        else ans[1]='S';

        for(int i=1; i<n-1; i++){
            if(ans[i]=='W' && s[i]=='o'){
                if(ans[i-1]=='W') ans[i+1]='S';
                else ans[i+1]='W';
            }
            else if(ans[i]=='W' && s[i]=='x'){
                if(ans[i-1]=='W') ans[i+1]='W';
                else ans[i+1]='S';
            }
            else if(ans[i]=='S' && s[i]=='o'){
                if(ans[i-1]=='W') ans[i+1]='W';
                else ans[i+1]='S';
            }
            else{
                if(ans[i-1]=='W') ans[i+1]='S';
                else ans[i+1]='W';
            }
        }

        bool ispossible=true;
        if(ans[n-1]=='W' && s[n-1]=='o'){
            if(!(ans[n-2]!=ans[0])) ispossible=false;
        }
        else if(ans[n-1]=='W' && s[n-1]=='x'){
            if(!(ans[n-2]==ans[0])) ispossible=false;
        }
        else if(ans[n-1]=='S' && s[n-1]=='o'){
            if(!(ans[n-2]==ans[0])) ispossible=false;
        }
        else{
            if(!(ans[n-2]!=ans[0])) ispossible=false;
        }

        if(ans[0]=='W' && s[0]=='o'){
            if(!(ans[n-1]!=ans[1])) ispossible=false;
        }
        else if(ans[0]=='W' && s[0]=='x'){
            if(!(ans[n-1]==ans[1])) ispossible=false;
        }
        else if(ans[0]=='S' && s[0]=='o'){
            if(!(ans[n-1]==ans[1])) ispossible=false;
        }
        else{
            if(!(ans[n-1]!=ans[1])) ispossible=false;
        }

        if(ispossible){
            for(int i=0; i<n; i++){
                cout << ans[i];
            }
            cout << endl;
            return 0;
        }
    }
    cout << -1 << endl;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define vsort(v) sort(v.begin(), v.end())
typedef long long ll;
using namespace std;
ll gcd(ll x, ll y)
{
	ll amari;
  	
  	while (y) {
    	amari = x % y;
      	x = y; y = amari;
    }
  	return x;
}
int main()
{
	ll A, B, C, D;
  	cin >> A >> B >> C >> D;
  	ll lcm = C * D / gcd(C, D);
  	ll until_B = B - B / C - B / D + B / lcm;
  	A--;
  	ll until_A = A - A / C - A / D + A / lcm;
  	cout << until_B - until_A << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int x,i,flg;
	scanf("%d",&x);
	flg=0;
	for(i=0;i<5;i++){
		if(x==7*i+1)	flg=1;
		if(x==7*i+2)	flg=2;
		if(x==7*i+3)	flg=3;
		if(x==7*i+4)	flg=4;
		if(x==7*i+5)	flg=5;
		if(x==7*i+6)	flg=6;
		if(x==7*i)	flg=7;
	}
	if(flg==1)	printf("fri\n");
	if(flg==2)	printf("sat\n");
	if(flg==3)	printf("sun\n");
	if(flg==4)	printf("mon\n");
	if(flg==5)	printf("tue\n");
	if(flg==6)	printf("wed\n");
	if(flg==7)	printf("thu\n");
	return 0;
}



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

string s[128];

int main() {
  cin >> s['a'] >> s['b'] >> s['c'];
  for (char c = 'a'; c <= 'c'; c++)
    reverse(s[c].begin(), s[c].end());
  char c = 'a';
  while (!s[c].empty()) {
   	char d = s[c].back(); s[c].pop_back();
    c = d;
  }
  cout << (char)toupper(c) << endl;
}

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

using namespace std;

int main(){
    int N,L;
	  cin >> N >> L;
  	
  	vector<string> v;
  	string s;
  	
  	for(int i = 0; i < N ; i++){
      cin >> s;
      v.push_back(s);
    }
  	
  	sort(v.begin(),v.end());
  
  	for(int i = 0; i < v.size(); i++){
      cout << v[i];
    }
  
	}

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

map<int, pair<int, int>> A;
vector<vector<bool>> board(3, vector<bool>(3, false));

bool bingo(){
  bool ans=false;
  for(int i=0;i<3;i++){
    ans |= board.at(i).at(0)&&board.at(i).at(1)&&board.at(i).at(2);
    ans |= board.at(0).at(i)&&board.at(1).at(i)&&board.at(2).at(i);
  }
  ans |= board.at(0).at(2)&&board.at(1).at(1)&&board.at(2).at(0);
  ans |= board.at(0).at(0)&&board.at(1).at(1)&&board.at(2).at(2);
  return ans;
}

int main(){
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      int tmp;
      cin>>tmp;
      A[tmp]=make_pair(i, j);
    }
  }
  
  int N;
  cin>>N;
  for(int i=0;i<N;i++){
    int b;
    cin>>b;
    if(A.count(b)){
      board.at(A[b].first).at(A[b].second)=true;
    }
  }
  
  if(bingo()){
    cout<<"Yes"<<endl;
  }
  else{
    cout<<"No"<<endl;
  }
}

Measured memory_bytes: 3620
package main

import (
	"bufio"
	"fmt"
	"os"
)

const (
	maxwh = 2000
)

func main() {
	// 入力
	r := bufio.NewReader(os.Stdin)
	var h, w int
	fmt.Fscan(r, &h, &w)
	r.ReadString('\n')
	var s [maxwh + 2][maxwh + 2]bool
	for y := 1; y <= h; y++ {
		line, _ := r.ReadString('\n')
		for x := 1; x <= w; x++ {
			s[x][y] = line[x-1] == '.'
		}
	}

	// 上下左右の計算
	var jo, ge, sa, yu [maxwh + 2][maxwh + 2]int
	for y := 1; y <= h; y++ {
		for x := 1; x <= w; x++ {
			if s[x][y] {
				jo[x][y] = jo[x][y-1] + 1
				sa[x][y] = sa[x-1][y] + 1
			}
		}
	}
	for y := h; y >= 1; y-- {
		for x := w; x >= 1; x-- {
			if s[x][y] {
				ge[x][y] = ge[x][y+1] + 1
				yu[x][y] = yu[x+1][y] + 1
			}
		}
	}

	// 最大値の計算
	res := 0
	for y := 1; y <= h; y++ {
		for x := 1; x <= w; x++ {
			v := jo[x][y] + ge[x][y] + sa[x][y] + yu[x][y] - 3
			if v > res {
				res = v
			}
		}
	}

	// 出力
	fmt.Println(res)
}


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

typedef long long int ll;
typedef pair<ll, ll> p_ll;
typedef vector<pair<ll, ll>> vec_p; //vector<pair<ll, ll>> pairs(n) ,pairs.at(i) = make_pair(i*i, i)

#define ture ture
#define flase false
#define falg flag

#define REP(i, x) for (ll i = 0; i < (ll)(x); i++)
#define REPS(i, x) for (ll i = 1; i <= (ll)(x); i++)
#define RREP(i, x) for (ll i = ((ll)(x)-1); i >= 0; i--)
#define RREPS(i, x) for (ll i = ((ll)(x)); i > 0; i--)
#define all(x) (x).begin(), (x).end()

const ll MOD = pow(10, 9) + 7;
const ll LLINF = pow(2, 61) - 1;//llの最大9*10^18
const int INF = pow(2, 30) - 1;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }

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

    ll N;
    string S;
    cin >> S;
    ll count = 0;
    ll ans = 0;

    REP(i,S.size()){
        ans = max(ans, count);
        if (S.at(i) == 'A' || S.at(i) == 'T' || S.at(i) == 'G' || S.at(i) == 'C'){
            count++;
        }
        else{
            count = 0;
        }
    }
    ans = max(ans, count);
    cout << ans << endl;

}


Measured memory_bytes: 256
n, k, q = map(int, input().split())

a = [-1] * q
for i in range(q):
    a[i] = int(input())

t = [0] * (n+1)
for i in range(q):
    t[ a[i] ] += 1

p = [0] * (n+1)
for i in range(1, n+1):
    p[i] = k - q + t[i]

for i in range(1, n+1):
    if p[i] > 0:
        print('Yes')
    else:
        print('No')


Measured memory_bytes: 52312
#include <iostream>
#include <iomanip>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <climits>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
typedef long long ll;
typedef pair<int,int> pii;
const int INF = 1<<29;
const double PI = acos(-1);
const double EPS = 1e-8;

struct P {
  int y, x, S;
  P(int y, int x, int S) : x(x), y(y), S(S) {}
};
char ba[30][30];
int rock[30][30];
int dist[30][30][1<<8];

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

int main() {
  int w,h;
  while(cin>>w>>h,w||h) {
    queue<P> Q;
    memset(dist,-1,sizeof(dist));
    int rocknum = 0;
    memset(rock, -1, sizeof(rock));
    map<char, int> mp;
    REP(i, h) {
      REP(j, w) {
        cin >> ba[i][j];
        if (ba[i][j] == '@') {
          dist[i][j][0] = 0;
          Q.push(P(i,j,0));
        }
        if (isupper(ba[i][j])) {
          if (mp.count(ba[i][j]) == 0) mp[ba[i][j]] = rocknum++;
        }
      }
    }
    int ans = -1;
    while(!Q.empty()) {
      P p = Q.front(); Q.pop();
      //cout << p.y << " " << p.x << " " << p.S << endl;
      //if (dist[p.y][p.x][p.S]>=0) continue;
      if (ba[p.y][p.x] == '<') {
        ans = dist[p.y][p.x][p.S];
        break;
      }
      REP(i, 4) {
        int yy = p.y+dy[i];
        int xx = p.x+dx[i];
        if (yy<0||yy>=h||xx<0||xx>=w) continue;
        if (ba[yy][xx] == '#') continue;
        
        int nS = p.S;
        if (islower(ba[yy][xx])) {
          char c = toupper(ba[yy][xx]);
          if (mp.count(c)) {
            nS ^= 1<<mp[c];
          }
        } else if (isupper(ba[yy][xx])) {
          if (!(nS >> mp[ba[yy][xx]] & 1)) continue;
        }
        //cout << yy  << ":" << xx << ":" << nS << " " << dist[yy][xx][nS] << endl;
        if (dist[yy][xx][nS] == -1) {
          dist[yy][xx][nS] = dist[p.y][p.x][p.S] + 1;
          Q.push(P(yy,xx,nS));
        }
      }
    }
    cout << ans << endl;
  }
}

Measured memory_bytes: 1908
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a, b, c, k;
	cin >> a >> b >> c >> k;
	while (k--)
	{
		if (b <= a)
		{
			b *= 2;
		}
		else if (c <= b)
		{
			c *= 2;
		}
	}
	if (c > b && b > a)
	{
		cout << "Yes" << endl;
	}
	else
	{
		cout << "No" << endl;
	}
	return 0;
}

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

int main() {
  int H,W,Z=0;
  cin>>H>>W;
  vector<vector<char>> p(H,vector<char>(W));
  for(int i=0;i<H;i++){
    for(int j=0;j<W;j++){
      cin>>p.at(i).at(j);
      if(p.at(i).at(j)=='.'){
        Z++;
      }
    }
  }
  queue<int> q;
  q.push(0);
  vector<vector<int>> r(H,vector<int>(W,-1));
  r.at(0).at(0)=1;
  while(!(q.empty())){
    int A=q.front()/W,B=q.front()%W;
    q.pop();
    if(A>0){
      if(r.at(A-1).at(B)==-1&&p.at(A-1).at(B)=='.'){
        r.at(A-1).at(B)=r.at(A).at(B)+1;
        q.push((A-1)*W+B);
      }
    }
    if(A<H-1){
      if(r.at(A+1).at(B)==-1&&p.at(A+1).at(B)=='.'){
        r.at(A+1).at(B)=r.at(A).at(B)+1;
        q.push((A+1)*W+B);
      }
    }
    if(B>0){
      if(r.at(A).at(B-1)==-1&&p.at(A).at(B-1)=='.'){
        r.at(A).at(B-1)=r.at(A).at(B)+1;
        q.push(A*W+B-1);
      }
    }
    if(B<W-1){
      if(r.at(A).at(B+1)==-1&&p.at(A).at(B+1)=='.'){
        r.at(A).at(B+1)=r.at(A).at(B)+1;
        q.push(A*W+B+1);
      }
    }
  }
  if(r.at(H-1).at(W-1)==-1){
    cout<<"-1"<<endl;
  }
  else{
    cout<<Z-r.at(H-1).at(W-1)<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main() {
	int k, a, b;
	cin >> k >> a >> b;
	if (a <= b / k * k) {
		cout << "OK" << endl;
	}
	else {
		cout << "NG" << endl;
	}
}

Measured memory_bytes: 3624
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <iomanip>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cassert>
#include <complex>
#include <stdio.h>
#include <time.h>
#include <numeric>
#include <random>
#include <unordered_map>
#include <unordered_set>
#define all(a) a.begin(),a.end()
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define pb push_back
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;
typedef complex<ld> com;
constexpr int inf = 1000000010;
constexpr ll INF = 1000000000000000010;
constexpr ld eps = 1e-12;
constexpr ld pi = 3.141592653589793238;
template<class T, class U> inline bool chmax(T &a, const U &b) { if (a < b) { a = b; return true; } return false; }
template<class T, class U> inline bool chmin(T &a, const U &b) { if (a > b) { a = b; return true; } return false; }

constexpr ll mod = 1000000007;

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(20);

	int n, k;
	cin >> n >> k;
	vector<ll> a(n);
	rep(i, n) cin >> a[i];
	sort(all(a)); reverse(all(a));
	int l = 0, r = n - 1;
	ll ans = 1;
	if (a[0] < 0 && (k & 1)) {
		rep(i, k) {
			ans *= a[i];
			ans %= mod;
		}
		if (ans < 0) ans += mod;
		cout << ans << '\n';
		return 0;
	}
	while (k) {
		if (k == 1) {
			ans *= a[l];
			ans %= mod;
			k--;
		}
		else {
			if (a[l] * a[l + 1] > a[r] * a[r - 1]) {
				ans *= a[l]; ans %= mod;
				ans *= a[l + 1]; ans %= mod;
				l += 2; k -= 2;
			}
			else {
				ans *= a[r]; ans %= mod;
				ans *= a[r - 1]; ans %= mod;
				r -= 2; k -= 2;
			}
		}
	}
	if (ans < 0) ans += mod;
	cout << ans << '\n';
}

Measured memory_bytes: 4728
import java.util.Scanner;

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

        int ans = 700;

        for (int i = 0; i < 3; i++) {
            if (s.charAt(i) == 'o') {
                ans += 100;
            }
        }

        System.out.println(ans);
    }
}

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

int main(){
  int N,cnt,flag;
  cin >> N;
  flag=0; //flagが0の時一回もcntに代入を行なっていないということ
  for(int i=0;i<N;i++){
    int n;
    cin >> n;
    if(n%2==0){
      //偶数だった時の処理
      int j=0;
      while(n%2==0){
        n/=2;
        j++;
      }
      if(flag==0){
        cnt=j;
        flag=1;
      }
      else if(j<cnt)cnt=j;
    }
    else {
      //奇数だった時の処理
      cnt=0;
      break;
    }
  }
  cout << cnt << endl;
}

Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
const int MOD = 1e9+7;
using ll = long long;
using vi = vector<int>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define ALL(x) x.begin(), x.end()
int main() {
  int a,b,c,d;
  cin >> a >> b >> c >> d;
  cout << c + b - d << " " << c + d - a << " " << a + b -d << " " << c + b - a;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
 
void solve()
{
	ll n;
	cin>>n;
	vector<ll> v;
	while(n!=0)
	{
		n--;
		v.push_back((n)%26);
		n /= 26;
	}
	for(int i = v.size()-1; i>=0; i--)
	{
		cout<<(char)('a'+v[i]);
	}
}
 
int main()
{
	ll t = 1;
	// cin>>t;
	while(t--)
	{
		solve();
	}
}

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

int dp[100010];

int main(){
    int N;
    cin >> N;
    dp[1] = 1;
    for(int i=0;i<=N;i++){
        int cnt = 1;
        while(true){
            cnt*=6;
            if(i+cnt>N) break;
            if(dp[i+cnt]){
                dp[i+cnt]=min(dp[i+cnt],dp[i]+1);
            }else{
                dp[i+cnt]=dp[i]+1;
            }
        }
        cnt = 1;
        while(true){
            cnt*=9;
            if(i+cnt>N) break;
            if(dp[i+cnt]){
                dp[i+cnt]=min(dp[i+cnt],dp[i]+1);
            }else{
                dp[i+cnt]=dp[i]+1;
            }
        }
        if(dp[i+1]){
            dp[i+1]=min(dp[i+1],dp[i]+1);
        }else{
            dp[i+1]=dp[i]+1;
        }
    }
    cout << dp[N] << endl;
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <algorithm>
#include <iomanip>
#include <math.h>
#include <string.h>
#include <cstdio>
#include <tuple>
#include <numeric>
#include <time.h>
#include <chrono>
#ifdef _MSC_VER
#  include <intrin.h>
#  define __builtin_popcount __popcnt
#endif
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define REP(i,a,b) for(ll i=a;i>b;i--)
#define CST(x) cout<<fixed<<setprecision(x)//小数点以下の桁数指定
#define ct(a) cout<<a<<endl
#define rep(i,n) for(int i=0;i<(n);i++)
#define repl(i,l,r) for(int i=(1);i<(r);i++)
#define per(i, n) for(int i = ((n)-1); i >= 0; i--)
static const double pi = 3.141592653589793;
using namespace std;
typedef long long ll;
const ll MOD = 998244353;
const ll INF = (1LL << 31) - 1;
const ll mod = 1e9 + 7;


ll N,K;
ll A[200001];
ll C[200001];
ll F[200001];


bool isOK(ll num) {
	ll cnt = K;


	FOR(i, 0, N) {
		ll x = A[i] - num / F[i];
		cnt -= max(x, 0LL);
	}


	if (cnt >= 0)return true;
	else return false;
}


ll binary_search() {

	ll left = -1, right = 1e12;
	while (right - left > 1) {
		ll mid = left + (right - left) / 2;

		if (isOK(mid))right = mid;
		else left = mid;
	}
	return right;
}


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


	cin >> N >> K;
	FOR(i, 0, N) {
		cin >> A[i];
	}
	sort(A, A + N);
	FOR(i, 0, N) {
		cin >> F[i];
	}
	sort(F, F + N);
	reverse(F, F + N);

	ll NUM = binary_search();

	cout << NUM << endl;
	


	return 0;
}

Measured memory_bytes: 6748
#include<bits/stdc++.h>
#define all(v) v.begin(),v.end()
using namespace std;
int main(){
	cin.tie(0);
    ios::sync_with_stdio(false);
    int n,a,b=0;
    cin>>n;
    a=n;
    while(a>0){
        b+=a%10;
        a/=10;
    }
    if(n%b==0)
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return(0);
}

Measured memory_bytes: 3664
#include<iostream>
using namespace std;
 
int main(void){
  int N;
  cin >> N;
  int A[2][110];
  for(int i=0;i<2;i++)
    for(int j=0;j<N;j++)
      cin >> A[i][j];
  
  int sum[110];
  for(int i=0;i<110;i++) sum[i]=0;
  int max=0;
  for(int i=0;i<N;i++){
    for(int j=0;j<=i;j++) sum[i]+=A[0][j];
    for(int j=i;j<N;j++) sum[i]+=A[1][j];
    if(max<sum[i]) max=sum[i];
  }
  cout << max << endl;
  return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
#include <numeric>
#include <string>
#include <stdio.h>
#include <set>
#include <iomanip>
using namespace std;

int main(){
  char c;
  cin >> c;
   if('A' <= c && c <= 'Z'){
        cout << "A";
    }else{
     cout << "a";
    }
  return 0;
}

Measured memory_bytes: 3628
#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef long long int int64;

#define MAX(a,b) ((a)>(b)?(a):(b))
#define MIN(a,b) ((a)<(b)?(a):(b))
#define ABS(a) ((a)>(0)?(a):-(a))

typedef struct listGraph{
  int v;
  int e;
  int *start;
  int *vertex;
  int *cost;
  int *next;
} graph;

graph* newGraph(const int v,const int e){
  graph *g=(graph *)malloc(sizeof(graph));
  g->v=v;
  g->e=0;
  g->start=(int *)malloc(sizeof(int)*v);
  int i;
  for(i=0;i<v;i++) g->start[i]=-1;
  g->vertex=(int *)malloc(sizeof(int)*e);
  g->cost=(int *)malloc(sizeof(int)*e);
  g->next=(int *)malloc(sizeof(int)*e);
  return g;
}

void freeGraph(graph *g){
  free(g->start);
  free(g->vertex);
  free(g->cost);
  free(g->next);
  free(g);
  return;
}

void addEdge(graph *g,int from,int to,int cost){
  int e=g->e;
  g->vertex[e]=to;
  g->cost[e]=cost;
  g->next[e]=g->start[from];
  g->start[from]=e;
  g->e++;
  return;
}

const int inf=1000*10000+1;

int bellmanFord(graph *g,int source,int *path){
  const int v=g->v;
  int i;
  for(i=0;i<v;i++) path[i]=inf;
  path[source]=0;
  for(i=0;i<v;i++){
    int j;
    for(j=0;j<v;j++){
      if(path[j]==inf) continue;
      int p;
      for(p=g->start[j];p!=-1;p=g->next[p]){
	int k=g->vertex[p];
	if(path[j]+g->cost[p]>=path[k]) continue;
	if(i==v-1) return 1;
	path[k]=path[j]+g->cost[p];
      }
    }
  }
  return 0;
}

void run(void){
  int v,e,r;
  scanf("%d%d%d",&v,&e,&r);
  graph *g=newGraph(v,e);
  int i;
  for(i=0;i<e;i++){
    int s,t,d;
    scanf("%d%d%d",&s,&t,&d);
    addEdge(g,s,t,d);
  }
  int *path=(int *)malloc(sizeof(int)*v);
  if(bellmanFord(g,r,path)){
    printf("NEGATIVE CYCLE\n");
  } else {
    for(i=0;i<v;i++){
      if(path[i]>=inf){
	printf("INF\n");
      } else {
	printf("%d\n",path[i]);
      }
    }
  }
  freeGraph(g);
  free(path);
  return;
}

int main(void){
  run();
  return 0;
}



Measured memory_bytes: 2104
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace AtCoder
{
    class Program
    {
        private static string Read() { return Console.ReadLine(); }
        private static int ReadInt() { return int.Parse(Read()); }
        private static long ReadLong() { return long.Parse(Read()); }
        private static double ReadDouble() { return double.Parse(Read()); }
        private static int[] ReadInts() { return Array.ConvertAll(Read().Split(), int.Parse); }
        private static long[] ReadLongs() { return Array.ConvertAll(Read().Split(), long.Parse); }
        private static double[] ReadDoubles() { return Array.ConvertAll(Read().Split(), double.Parse); }

        static long Gcd(long a, long b)
        {
            var v = new[] { a, b };
            while (v[1] != 0) { v = new[] { v[1], v[0] % v[1] }; }
            return v[0];
        }

        static long Lcm(long a, long b)
        {
            return a / Gcd(a, b) * b;
        }

        static long Count(long A, int C, int D)
        {
            return A - A / C - A / D + A / Lcm(C, D);
        }

        static long Solve(long A, long B, int C, int D)
        {
            return Count(B, C, D) - Count(A - 1, C, D);
        }

        static void Main(string[] args)
        {
            var V = ReadLongs();
            Console.WriteLine(Solve(V[0], V[1], (int)V[2], (int)V[3]));
        }
    }
}


Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
const int N=100009;
int n,a[N],ans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    sort(a+1,a+n+1);
    reverse(a+1,a+n+1);
    for(int i=1;i<=n;i++)
        if(i+1>a[i+1])
        {
            for(int j=i+1;a[j]==i;j++)
                ans^=1;
            ans|=(a[i]-i)&1;
            puts(ans? "First":"Second");
            return 0;
        }
    return 0;
}

Measured memory_bytes: 640
#include <cstdio>
#include <cmath>
#include <cstring>
#include <utility>
#include <queue>
#include <vector>
#include <string>
#include <set>
#include <functional>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long LL;
typedef pair<int,int> P;
int main() {
	int coin[]={1,5,10,50,100,500};
	int sum=0;
	for(int i=0;i<6;i++) {
		int c;
		scanf("%d",&c);
		sum+=coin[i]*c;
	}
	printf("%d\n",sum>=1000);
}

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

using namespace std;
 
typedef long long ll;
typedef long double ld;
typedef pair<int, int> Pii;
typedef pair<int, ll> Pil;
typedef pair<ll, ll> Pll;
typedef pair<ll, int> Pli;

#define fi first
#define se second

const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll MOD3 = 1812447359;
const ll INF = 1ll << 62;
const double PI = 2 * asin(1);

void yes() {printf("yes\n");}
void no() {printf("no\n");}
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

string S;
int N;
ll ans = 0;

int Solve(int turn, ll num, ll sum){
  if (turn == N){
    ans += sum + num;
    return 0;
  }

  ll now = S[turn] - '0';
  Solve(turn + 1, num * 10 + now, sum);
  Solve(turn + 1, 0, sum + num * 10 + now);

  return 0;
}

int main(){
  cin >> S;
  N = S.length();
  Solve(0, 0, 0);
  cout << ans / 2 << endl;

  return 0;
}


Measured memory_bytes: 3580
#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(void){
    bool x;
    cin >> x;
    cout << !x << endl;
    return 0;
}

Measured memory_bytes: 3612
#pragma GCC optimize("Ofast")
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int i,x,y;
	scanf("%d%d",&x,&y);
	for(i=0;i<=x;i++){
		int a=x-i;
		if(i*2+a*4==y){
			puts("Yes");
			return 0;
		}
	}
	puts("No");
}


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

#define fastio 			ios::sync_with_stdio(0);	cin.tie(0); cout.tie(0);  cout<<fixed;  cout<<setprecision(12);
#define randomINT 		mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
#define	newl 			cout<<"\n"
#define DISP(as)		for(auto it : as) cout<<it<<" ";newl;
#define all(x)         	(x).begin(),(x).end()
#define mset(x,val)    	memset(x,val,sizeof(x))
#define newl           	cout<<"\n"
#define pb             	push_back
#define mp             	make_pair
#define f 				first
#define s 				second
#define dline          cerr<<"///REACHED///\n";
#define deb1(x)        cerr<<#x<<" = "<<x<<'\n';
#define deb2(x,y)      cerr<<'['<<#x<<','<<#y<<"] = "<<'['<<x<<','<<y<<']'<<'\n';
#define deb3(x,y,z)    cerr<<'['<<#x<<','<<#y<<','<<#z<<"] = "<<'['<<x<<','<<y<<','<<z<<']'<<'\n';

typedef long long 				ll;
typedef long double 			ld;
typedef vector<ll> 				vll;
typedef pair<ll , ll> 			pll;
typedef pair<ld, ld> 			pld;
typedef unordered_map<ll, ll> 	um;
typedef vector<pll> 			vpll;

const ll 	MAX5 	= 	1e+5 + 7;
const ll 	MAX7 	= 	1e+7 + 7;
const ll 	MAXN 	= 	4 * MAX5;
const ll   	INF   	=  	0x7f7f7f7f7f7f7f7f;
const int  	INFi 	=  	0x7f7f7f7f;
const ll 	MOD		=  	1e+9 + 7;

vll adj[MAXN]; ll visit[MAXN] = {};
int dx8[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy8[] = {1, 1, 0, -1, -1, -1, 0, 1};
int dx4[] = {0, 1, 0, -1}, dy4[] = {1, 0, -1, 0};

// <------------- Declare Variables Here ------------> //

ll t = 1;
ll n, x, k, q, m, y, r, l, c, a;
string s;

// <------------- Implement Functions Here ----------> //

  

// <------------- Start of main() -------------------> //

void MAIN() {
	cin >> s;
	ll val, diff = 0, sum = 0;
	string S;
	val = (s.size() + 1)/2;
	
	if(s.size() & 1) {
		S = "";
		for(ll i=0;i<s.size();i++) S+='9';
		diff = stoull(S) - stoull(s);
	}
	S = "";
	for(ll i = 0;i<val;i++) {
		S += "09";
	}
	sum = stoull(S);
	cout<<sum - diff ;
}

int main() {
	fastio; randomINT;
	//cin >> t;
	while (t--) {
		MAIN();
	}
	return 0;
}


Measured memory_bytes: 12940