akhauriyash/Code-Regression huggingface dataset:
object Main extends App {
	val pw = new java.io.PrintWriter(System.out)
	
	@scala.annotation.tailrec
	def loop(start: Int, end: Int)(f: Int => Unit): Unit =
		if (start <= end) {
			f(start)
			loop(start + 1, end)(f)
		}
		
	val k, n = Scanner.nextInt()
	val a = Array.fill(n)(Scanner.nextInt())
	
	var max = a(0) + k - a(n-1)
	loop(1, n-1) { i => max = Math.max(max, a(i) - a(i-1)) }
	
	pw.println(k - max)
	pw.flush()
}

object Scanner {
	private val buf = new Array[Byte](1024); private var ptr = 0; private var len = 0

	@inline private def isPrintableChar(c: Int): Boolean = 33 <= c && c <= 126
	@inline private def hasNextByte(): Boolean = if (ptr >= len) { ptr = 0; len = System.in.read(buf); len > 0 } else true
	@inline private def hasNext(): Boolean = {
		while (hasNextByte() && !isPrintableChar(buf(ptr))) ptr += 1
		hasNextByte()
	}
	@inline private def readByte(): Byte = if (hasNextByte()) { val res = buf(ptr); ptr += 1; res } else -1

	def next(): String = {
		if(!hasNext()) ???
		val sb = new StringBuilder; var b = readByte()
		while (isPrintableChar(b)) { sb.append(b.toChar); b = readByte() }
		sb.toString
	}

	def nextInt(): Int = {
		val n = nextLong()
		if (n < Int.MinValue || Int.MaxValue < n) ???
		n.toInt
	}

	def nextLong(): Long = {
		if(!hasNext()) ???
		var minus = false; var b = readByte()
		if (b == '-') { minus = true; b = readByte() }

		@scala.annotation.tailrec
		def go (b: Byte, n: Long = 0): Long = if ('0' <= b && b <= '9') go(readByte(), n * 10 + b - '0') else if (minus) -n else n

		go(b)
	}

	def nextDouble(): Double = next().toDouble
}


Measured memory_bytes: 28220
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const double PI = acos(-1.0);
const int N = 200005;
const int MOD = 1e9 + 7;
const int inf = 1<<28;
typedef long long ll;

vector<int> g[N];
int a[N], ans[N];
bool vis[N];

void dfs(int x, int c)
{
	if(vis[x])
		return;
	vis[x] = 1;
	ans[x] += a[x] + c;

	for(int i = 0; i < g[x].size(); i++)
	{
		int v = g[x][i];
			dfs(v, ans[x]);
	}
}
int main()
{
   /* #ifndef ONLINE_JUDGE
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    #endif*/
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, q, z, x;
   	cin>>n>>q;

   	for(int i = 1; i < n; i++)
   	{
   		cin>>z>>x;
   		g[z].push_back(x);
   		g[x].push_back(z);
   	}
   	while(q--)
   	{
   		cin>>z>>x;
   		a[z] += x;
   	}

   	dfs(1, 0);
    for(int i = 1; i <= n; i++)
    	cout<<ans[i]<<' ';
}


Measured memory_bytes: 24320
#include<iostream>
#define rep(i,n) for(int i=0;i<n;++i)
using namespace std;

int N, ans;
string S;

int main() {
    cin >> N >> S;
    rep(i, 1000) {
        int c[3] = {i / 100, i / 10 % 10, i % 10};
        int f = 0;
        rep(j, N) {
            if (S[j] - '0' == c[f]) f++;
            if (f == 3) {
                ans++;
                break;
            }
        }
    }
    cout << ans << endl;
}

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

using ll = long long;
using ull = unsigned long long;

const double PI = acos(-1);
const int inf = 2e9;
const ll INF = 2e18;
const ll MOD = 1e9+7;

#define sz(s) (s).size()
#define pb push_back
#define fi first
#define se second
#define REP(i,n) for (int i = 0; i<n; i++)
#define ALL(a) begin(a), end(a)

int main (void) {
    int N;
    cin>>N;
    vector<vector<vector<bool>>> F(N,vector<vector<bool>>(5,vector<bool>(2)));
    vector<vector<int>> P(N,vector<int>(11));
    REP(i,N) {
        REP(j,5) {
            REP(k,2) {
                int temp;
                cin>>temp;
                if (temp==1) F[i][j][k] = true;
                else F[i][j][k] = false;
            }
        }
    }
    REP(i,N) {
        REP(j,11) {
            cin>>P[i][j];
        }
    }
    ll ans = -INF;
    REP(i,1<<10) {
        int t = i;
        vector<vector<bool>> S(5,vector<bool>(2));
        int open = 0;
        REP(j,5) {
            REP(k,2) {
                if (t%2 == 0) {
                    S[j][k] = true;
                    open++;
                }
                else {
                    S[j][k] = false;
                }
                t /= 2;
            }
        }
        if (open == 0) continue;
        vector<int> C(N,0);
        ll val = 0;
        REP(j,N) {
            REP(k,5) {
                REP(l,2) {
                    if (F[j][k][l]&&S[k][l]) C[j]++;
                }
            }
            val += P[j][C[j]];
        }
        ans = max(val,ans);
    }
    cout<<ans<<endl;
    return 0;
}

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

int main()
{
    int n, m;
    cin >> n >> m;
    vector<int> broken(n + 1);
    rep(i, m)
    {
        int a;
        cin >> a;
        broken[a] = 1;
    }
    vector<int> dp(n + 2);
    const int mod = 1000000007;
    dp[n] = 1;
    for (int i = n - 1; i >= 0; i--)
    {
        if (broken[i])
        {
            dp[i] = 0;
            continue;
        }
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod;
    }
    cout << dp[0] << endl;
    return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define INF 1000000000000000LL
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> PP;

int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
bool prime[1000005];
ll ans[501][501];

ll gcd(ll a,ll b){
	if(b==0LL)return a;
	return gcd(b,a%b);
}

ll lcm(ll a,ll b){
	ll g=gcd(a,b);
	a/=g;
	return a*b;
}

void solve(int n){
	if(n==2){
		printf("4 7\n23 10\n");
		return;
	}
	vector<ll> vec;
	memset(prime,true,sizeof(prime));
	for(ll i=2;i<1000005;i++){
		if(prime[i]){
			if(i!=2)vec.push_back(i);
			if(vec.size()>=n*2)break;
			for(ll j=2LL*i;j<1000005;j+=i){
				prime[j]=false;
			}
		}
	}
	deque<ll> x,y;
	for(int i=0;i<vec.size();i++){
		if(i%4==0){
			x.push_front(vec[i]);
		}
		if(i%4==1){
			y.push_front(vec[i]);
		}
		if(i%4==2){
			x.push_back(vec[i]);
		}
		if(i%4==3){
			y.push_back(vec[i]);
		}
	}
	set<ll> s;
	//printf("%d %d\n",(int)x.size(),(int)y.size());
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if((i+j)%2==0){
				int diff=(i-j)/2;
				//printf("%d %d\n",(i+j)/2,diff+n/2);
				ans[i][j]=x[(i+j)/2];
				ans[i][j]*=y[diff+n/2];
				assert(s.find(ans[i][j])==s.end());
				s.insert(ans[i][j]);
			}
		}
	}
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if((i+j)%2==1){
				ans[i][j]=1;
				for(int k=0;k<4;k++){
					int nx=j+dx[k];
					int ny=i+dy[k];
					if(nx>=0 && nx<n && ny>=0 && ny<n){
						ans[i][j]=lcm(ans[i][j],ans[ny][nx]);
					}
				}
				ans[i][j]++;
				assert(s.find(ans[i][j])==s.end());
				s.insert(ans[i][j]);
			}
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			for(int k=0;k<4;k++){
				int nx=j+dx[k];
				int ny=i+dy[k];
				if(nx>=0 && nx<n && ny>=0 && ny<n){
					assert(max(ans[i][j],ans[ny][nx])%min(ans[i][j],ans[ny][nx])==1LL);
				}
			}
			printf("%lld%c",ans[i][j],j+1==n?'\n':' ');
		}
	}
	return;
} 

int main(void){
	int n;
	scanf("%d",&n);
	solve(n);
	return 0;
}

Measured memory_bytes: 17536
N,Q=map(int,input().split())
S=input()
query=[list(map(int,input().split())) for _ in range(Q)]
table=[0 for _ in range(N)]
num=0
for i in range(N-1):
    if (S[i]=="A")and(S[i+1]=="C"):
        num=num+1
    table[i+1]=num
for i in range(Q):
    print(table[query[i][1]-1]-table[query[i][0]-1])

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

signed main(){
  
  int n;
  cin>>n;
  
  vector<int> v(n);
  vector<int> c(n);
  
  for(int i=0;i<n;i++) cin>>v[i];
  for(int i=0;i<n;i++) cin>>c[i];
  
  int ans = 0;
  
  for(int i=0;i<n;i++){
    int x = v[i] - c[i];
    if( x > 0 ) ans += x;
  }
  
  cout<<ans<<endl;
  
  return 0;
}


Measured memory_bytes: 256
#include<cstdio>
const int mod=1000000007;
int H,W;
long long K;
char s[1010][1010],tmps[1010][1010];
int pw(long long a,long long n){
	int b=1;
	for(;n;n>>=1)n%2?b=b*a%mod:1,a=a*a%mod;
	return b;
}
struct mat{
	int a[2][2];
	mat operator*(const mat&b)const{
		mat c;
		for(int i=0;i<2;i++)
			for(int j=0;j<2;j++)
				c.a[i][j]=(1ll*a[i][0]*b.a[0][j]+1ll*a[i][1]*b.a[1][j])%mod;
		return c;
	}
};
int main(){
	scanf("%d%d%lld",&H,&W,&K);
	for(int i=0;i<H;i++)scanf("%s",s[i]);
	bool hc=0,vc=0;
	for(int i=0;i<H;i++)if(s[i][0]=='#'&&s[i][W-1]=='#')hc=1;
	for(int i=0;i<W;i++)if(s[0][i]=='#'&&s[H-1][i]=='#')vc=1;
	if(!K||hc&&vc)return puts("1"),0;
	if(!hc&&!vc){
		int t=0;
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)t+=s[i][j]=='#';
		return printf("%d\n",pw(t,K-1)),0;
	}
	if(vc){
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)tmps[j][i]=s[i][j];
		int t=H;H=W;W=t;
		for(int i=0;i<H;i++)
			for(int j=0;j<W;j++)s[i][j]=tmps[i][j];
	}
	mat A={{{1,0},{0,1}}},B=(mat){{{0,0},{0,0}}};
	for(int i=0;i<H;i++){
		int pre=0,suf=0;
		for(int l=0,r=0;l<W;l=r){
			for(;r<W&&s[i][l]==s[i][r];r++);
			if(s[i][l]=='#'){
				if(l==0&&r==W){
					(B.a[0][0]+=W)%=mod;
					(++B.a[1][1])%=mod;
				}
				else if(l==0)pre=r;
				else if(r==W)suf=r-l;
				else{
					(B.a[0][0]+=r-l)%=mod;
					(++B.a[0][1])%=mod;
				}
			}
		}
		if(pre&&suf)(++B.a[1][1])%=mod;
		if(pre||suf){
			(B.a[0][0]+=pre+suf)%=mod;
			(++B.a[0][1])%=mod;
		}
	}
	for(K--;K;K/=2){
		if(K%2)A=A*B;
		B=B*B;
	}
	printf("%d\n",(A.a[0][1]+A.a[1][1])%mod);
}

Measured memory_bytes: 2176
a=input().split()
operator={
  '+':(lambda x,y:x+y),
  '-':(lambda x,y:x-y),
  '*':(lambda x,y:x*y),
  '/':(lambda x,y:float(x)/y)
}
stack=[]
for i,j in enumerate(a):
  if j not in operator.keys():
    stack.append(int(j))
    continue
  y=stack.pop()
  x=stack.pop()
  stack.append(operator[j](x,y))
print(stack[0])
    
  


Measured memory_bytes: 5600
def agc032_b():
    n = int(input())
    g = [[1]*n for _ in range(n)]
    for i in range(n//2):
        j = 2*(n//2)-1-i
        g[i][j] = 0
        g[j][i] = 0
    cnt = (sum([sum(row) for row in g]) - n) // 2
    print(cnt)
    for i in range(n):
        for j in range(i+1, n):
            if g[i][j]: print('{} {}'.format(i+1, j+1))

if __name__ == '__main__':
    agc032_b()

Measured memory_bytes: 9208
N = int(input())
A = [int(i) for i in input().split()]

ki = 0
gu4 = 0
for i in A:
    if i % 4 == 0:
        gu4 += 1
    elif i % 2 != 0:
        ki += 1

if N % 2 != 0:
    if ki <= gu4 + 1:
        print('Yes')
    else:
        print('No')
else:
    if ki <= gu4:
        print('Yes')
    else:
        print('No')

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

int main(){
  ll N;
  cin >> N;
  vector<ll> vec(N);
  for(int i=0;i<N;i++){
    cin >> vec[i];
  }
  ll st=0,ans=0;
  for(int i=1;i<N;i++){
    if(st+vec[i-1]>vec[i]){
      st=st+vec[i-1]-vec[i];
      ans+=st;
    }
    else{
      st=0;
    }
  }
  cout << ans <<endl;
}
      
    
      

Measured memory_bytes: 4776
K = int(input())

dig = 10
# dp[i][j] := jで始まるi桁のルンルン数の数
dp = [[0 for _ in range(10)] for _ in range(dig + 1)]

# 1桁
for j in range(0, 10):
    dp[1][j] = 1 # jで始まる1桁のルンルン数の数

# 2〜3桁
for i in range(2, dig + 1): # 2〜3桁
    dp[i][0] = dp[i - 1][0] + dp[i - 1][1]
    for j in range(1, 9):
        # jで始まるi桁のルンルン数の数 = j-1, j, またはj+1で始まるi-1桁のルンルン数の数
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j] + dp[i - 1][j + 1]
    dp[i][9] = dp[i - 1][8] + dp[i - 1][9]

####################################

ac = 0
for i in range(1, dig + 1):
    for j in range(1, 10):
        ac += dp[i][j]
        if ac >= K:
            ans = j * (10 ** (i - 1))
            break
    else:
        continue
    break

# MSBがjであるi桁の数字
rem = K - ac + dp[i][j]
while i > 1:
    if j == 0: # 次の桁は0か1
        jlist = [0, 1]
    elif j == 9: # 次の桁は8か9
        jlist = [8, 9]
    else:  # 次の桁はj-1かjかj+1
        jlist = [j - 1, j, j + 1]

    for j in jlist:
        if dp[i - 1][j] < rem:
            rem -= dp[i - 1][j]
        else:
            break
    i -= 1
    ans += j * 10 ** (i - 1)

print(ans)


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

int main(){
	string L,R,S;
  	int Q,type,rev,f;
  	char c;
  	cin >> S;
  	cin >> Q;
  	for(int i=0; i<Q;i++){
    	cin >> type;
      	if(type == 2){
        	cin >> f >> c;
          	f--;
          	if(rev) f=1-f;
          	if(f==0) L += c;
          	else R += c;
        }
    	else rev = 1 - rev;
    }
  	reverse(L.begin(),L.end());
  	string ans = L + S + R;
  	if(rev) reverse(ans.begin(), ans.end());
  	cout << ans << endl;
  	
}

Measured memory_bytes: 1348
<?php
fscanf(STDIN, "%d %d", $h, $w);
$input = [];
for ($i = 0; $i < $h; $i++) {
	$line = fgets(STDIN);
	for ($j = 0; $j < $w; $j++) {
		$input[$i][$j] = $line[$j];
	}
}
for ($i = 0; $i < $h; $i++) {
	for ($j = 0; $j < $w; $j++) {
		if ($input[$i][$j] === '.') {
			continue;
		}
		if ($input[$i-1][$j] === '#' || $input[$i+1][$j] === "#"
			|| $input[$i][$j-1] === '#' || $input[$i][$j+1] === "#") {
			continue;
		}
		echo "No\n";
		return;
	}
}
echo "Yes\n";

Measured memory_bytes: 4856
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        String S;
        Scanner sc = new Scanner(System.in);
        S = sc.next();
        System.out.println((S.charAt(2)==S.charAt(3) && S.charAt(4) == S.charAt(5)) ? "Yes" : "No");
    }
}


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

using namespace std;

int main() {
    std :: ios :: sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ///cout << "debug" << endl;
    //int ans = 0;
    int n, m;
    cin >> n;
    vector < int > dp(n + 1, 0);
    for(int i = 1 ; i <= n ; ++i) {
        for(int j = i ; j <= n ; j += i) {
            dp[j]++;
        }
    }
    long long ans = 0;
    for(int i = 1 ; i <= n ; ++i) ans += 1LL * i * dp[i];
    cout << ans << endl;
    return 0;
}



Measured memory_bytes: 42264
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using std::cin;
using std::cout;



int main(int argc, char* argv[])
{
  std::ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int N, H, W;
  cin >> N >> H >> W;

  cout << (N-H+1) * (N-W+1) << "\n";

  return 0;
}


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

sqx = int((2*x)**(1/2)) + 30
test = [1]*min(sqx,10000)
for i in range(2,min(sqx,10000)):
    for j in range(min(sqx,10000)):
        if (x+j)%i==0 and x+j>i:
            test[j] = 0
for i in range(min(sqx,10000)):
    if test[i]:
        print(x+i)
        exit()


Measured memory_bytes: 39280
n, m = map(int, input().split())
a = input()
ret = []
i = n
while i > 0:
    best = max(i - m, 0)
    if a[best] == '1':
        while best < i and a[best] == '1':
            best += 1
        if best == i:
            print(-1)
            exit()
    ret.append(i - best)
    i = best
print(' '.join(map(str, ret[::-1])))

Measured memory_bytes: 11124
#include<bits/stdc++.h>
using namespace std;
#define N 1055
#define ll long long
int mod = 1e9+7;
char ar[N][N];
int dp[N][N];
int main() {

    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) {
            scanf(" %c",&ar[i][j]);
        }
    }
    dp[0][1] = 1;
    for(int i=1; i<=n; ++i) {
        for(int j=1; j<=m; ++j) {
            if(ar[i][j] == '.')
                dp[i][j] = (dp[i-1][j] + dp[i][j-1])%mod;
        }
    }
    printf("%d",dp[n][m]);

    return 0;
}


Measured memory_bytes: 5376
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define mp make_pair
#define pb(x) push_back(x)
#define vll vector<long long>
#define pll pair<long long, long long>
#define mll map<long long, long long>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define gcd __gcd
#define clr(x) memset(x, 0, sizeof(x))
#define mod 1000000007LL
#define mod2 998244353LL
#define INF 1e18
 

typedef long long ll;
typedef long double ld;
typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> o_tree;


void solve()
{
  ll n;
  cin>>n;
  string s="ACL";
  for(ll i=0;i<n;i++)
  {
    cout<<s;
  }
  cout<<"\n";
}


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


if (fopen("input.txt","r" ))
  {
     freopen("input.txt", "r", stdin);
     freopen("output.txt", "w", stdout);
  }
cout<<setprecision(20);


ll t=1;


// cin>>t;


while(t--)
{
solve();
} 


return 0;
}

Measured memory_bytes: 3644
from collections import defaultdict

D = defaultdict(int)
N = int(input())

a = 2
while a * a <= N:
    if N % a:
        a += 1
    else:
        N //= a
        D[a] += 1

if N != 1:
    D[N] += 1

ans = 0
for k,v in D.items():
    i = 0
    while i*(i+1) <= v * 2:
        i += 1
    ans += i-1

print(ans)

Measured memory_bytes: 66100
N, M, Q = map(int, input().split())
ABCD = [tuple(map(int, input().split())) for _ in range(Q)]
ans, A = 0, [1] * (N - 1) + [0]
while A != [M] * N:
    if A[N - 1] < M:
        A[N - 1] += 1
    else:
        c = N - 2
        while A[c] == M:
            c -= 1
        A[c] += 1
        for i in range(c + 1, N):
            A[i] = A[c]
    ans = max(ans, sum([d for a, b, c, d in ABCD if A[b - 1] - A[a - 1] == c]))
print(ans)


Measured memory_bytes: 9160
#include<bits/stdc++.h>
using namespace std;
const long long INF = (1LL << 32);
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector<pair<ll, ll>> vp;
typedef vector<string> vs;
typedef vector<char> vc;
typedef list<ll> lst;
typedef pair<ll, ll> P;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/


int main() {
    ll a, b;
    cin >> n >> a >> b;
    cout<<((b-a)%2?"Borys":"Alice")<<endl;
}

Measured memory_bytes: 256
def solve(N, Y):
    for i in range(N + 1):
        for j in range(N + 1):
            if i + j > N:
                continue
            S = 10000 * i + 5000 * j + 1000 * (N - i - j)
            if S == Y:
                print(i, j, N - i - j)
                return
    print(-1, -1, -1)

N, Y = map(int, input().split())
solve(N, Y)

Measured memory_bytes: 3060
#include<stdio.h>
void trace(int A[],int N){
  int i;
  for( i = 0; i < N; i++){
    if ( i > 0 ) printf(" ");
    printf("%d",A[i]);
   }
   printf("\n");
}


void insertionSort(int A[],int N){
  int j, i, v;
  for ( i = 1; i < N; i++){
    v = A[i];
    j = i - 1;
    while ( j >= 0 && A[j] > v){
      A[j + 1] = A[j];
      j--;
    }
    A[j + 1] = v;
    trace(A,N);
  }
}

int main(){
  int N,i,j;
  int A[100];

  scanf("%d",&N);
  for ( i = 0; i < N; i++) scanf("%d", &A[i]);

  trace(A,N);
  insertionSort(A,N);

  return 0 ;
} 


Measured memory_bytes: 2752
#include <bits/stdc++.h>
using namespace std;
#define MOD 1000000007
#define ll long long
#define ull unsigned long long
#define si set <ll>
#define vi vector <ll>
#define popcount(x) __builtin_popcountll(x)
#define mii map <ll,ll>
#define vpi vector <pair <ll,ll> >
#define sz(c) (int)c.size()
#define fr first
#define ll long long
#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define sc second
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define mem0(a) memset(a,0,sizeof(a))
#define rep(i,a,n) for(ll i=a ; i<n ; i++)
#define ld long double
#define rall(a) (a).rbegin(),(a).rend()
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization ("unroll-loops")
 
 
 
ll power(ll b,ll e,ll m)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b%m,e/2,m)%m;
  return power(b*b%m,e/2,m);
}
ll power( ll b, ll e)
{
  if(b==0) return 0;
  if(e==0) return 1;
  if(e&1) return b*power(b*b,e/2);
  return power(b*b,e/2);
}  
bool isPowerOfTwo(ll x)
{
    // x will check if x == 0 and !(x & (x - 1)) will check if x is a power of 2 or not
    return (x && !(x & (x - 1)));
}


void solve()
{
  string s;
  cin>>s;
  ll n=s.size();
  ll r=0,p=0,ans=0;
  rep(i,0,n)
  {
    if(s[i]=='g')
    {
      if(r>p)
      { 
        p++;
        ans++;
      }
      else
      {
        r++;
      }
    }
    else
    {
      if(r>p)
      {
        p++;
      }
      else
      {
        ans--;
        r++;
      }
    }
  }
  cout<<ans;
}

int main()
{
  ll tt=1;
  // cin>>tt;
  while(tt--)
  {
    solve();
    cout<<"\n";
  }
}

Measured memory_bytes: 3696
#include<stdio.h>
 
 
int A[2005];
int n;
int sum;
 
int search(int i,int m){
  if(sum < m)return 0;
  if(m == 0)return 1;
  if(i >= n)return 0;
  return search(i+1,m) || search(i+1,m-A[i]);
}
 
 
int main(){
  int q,m;
  int i;
 
  sum = 0;
  scanf("%d",&n);
 
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
    sum+=A[i];
  }
  scanf("%d",&q);
 
  for(i=0;i<q;i++){
    scanf("%d",&m);
    if (search(0,m)){
      printf("yes\n");
    }else{
      printf("no\n");
    }
 
  }
  return 0;
}

Measured memory_bytes: 580
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    long long l[n+1];
    l[0]=2;
    l[1]=1;
    for(int i=2;i<n+1;i++){
        l[i]=l[i-1]+l[i-2];
    }
    cout<<l[n]<<endl;
}

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

int main()
{
    string s;
    cin>>s;
    
    int n=s.length();
    
    int k1=0,k2=0,k3=0;
    
    for(int i=0;i<n/2;i++)
    {
        if(s[i]!=s[n-i-1])
        {
            k1=1;
            break;
        }
    }
    string s2=s.substr(0,n/2);
    string s3=s.substr(n/2+1,n-1);
    for(int i=0;i<s2.length()/2;i++)
    {
        if(s2[i]!=s2[s2.length()-i-1])
        {
            k2=1;
            break;
        }
    }
    for(int i=0;i<s3.length()/2;i++)
    {
        if(s3[i]!=s3[s3.length()-i-1])
        {
            k3=1;
            break;
        }
    }
    if((k1+k2+k3)==0)
    cout<<"Yes";
    else
    cout<<"No";
    
    return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <vector>
#include <stack>
#include <set>
#define  STATE  30
using namespace std;
int dp[STATE][STATE][STATE][STATE];
vector <int> A, B, Y, Z, X;
stack <int> stk;
int n, m, r, state;
inline void init (void)
{
    Y.clear();
    Z.clear();
    X.clear();      
    A.resize(n);
    B.resize(m);
    for (int i=0;i<n;++i) cin>>A[i];
    for (int i=0;i<m;++i) cin>>B[i];
    state = STATE;
}
inline void toChomskyForm (int y)
{
    for (;;)
    {
        Z.push_back(stk.top()); stk.pop();
        Y.push_back(stk.top()); stk.pop();      
        if (stk.empty())
        {
           X.push_back(y);
           return ;
        }
        else
        {
            X.push_back(++state);     
            stk.push(state); 
        }
    }          
}
inline void makeGrammar (void)
{
    int k, y, tmp;
    for (int i=0;i<r;++i)          
    {
        cin>>k;    
        for (int j=0;j<k;++j)
        {
            cin>>tmp;    
            stk.push(tmp);
        }
        cin>>y;
        toChomskyForm (y);
    }   
}
inline vector < vector < set<int> > > CYK ( const vector <int> &A )
{
    int n = A.size();          
    vector < vector< set<int> > > dp(n,vector< set<int> >(n+1));
    for (int i=0;i<n;++i) dp[i][1].insert(A[i]);
    
    for (int len=2;len<=n;++len)
    for (int i=0;i<n;++i)
    for (int j=0;j<X.size();++j)
    for (int k=1;k<len;++k)
    {
        int ii = (i+k)%n;    
        if (dp[i][k].count(Y[j])&&dp[ii][len-k].count(Z[j])) 
           dp[i][len].insert(X[j]);
    }      
    return dp;   
}
inline vector < vector<int> > makeBitset ( const vector < vector < set<int> > > &A )
{
    int n = A.size();
    vector < vector<int> > ans(n,vector<int>(n+1,0));
    for (int i=0;i<n;++i)
    for (int w=0;w<=n;++w)
    for (int k=0;k<=STATE;++k)
        if (A[i][w].count(k)) ans[i][w] |= 1<<k;
    return ans;
}

inline void solve (void)
{
    vector < vector<int> > ai = makeBitset( CYK(A) );
    vector < vector<int> > bi = makeBitset( CYK(B) );
    memset (dp,-1,sizeof(dp));
    for (int i=0;i<n;++i)
    for (int j=0;j<m;++j) dp[i][0][j][0] = 0;
    
    for (int nn=0;nn<n;++nn)
    for (int mm=0;mm<m;++mm)
    for (int i=0;i<n;++i)
    for (int j=0;j<m;++j)
    {
        if (dp[i][nn][j][mm] == -1) continue;    
        for (int p=nn+1;p<=n;++p)
        for (int q=mm+1;q<=m;++q)
        {
            int ii = (i+nn)%n;
            int jj = (j+mm)%m;
            if (ai[ii][p-nn] & bi[jj][q-mm])
               dp[i][p][j][q] = max(dp[i][p][j][q],dp[i][nn][j][mm]+1);
        }
    }
    int ans = -1;
    for (int i=0;i<n;++i)
    for (int j=0;j<m;++j) ans = max(ans,dp[i][n][j][m]);   
    cout<<ans<<endl;
}
int main(void)
{
    ios_base :: sync_with_stdio(0);
    ///
    while (cin>>n>>m>>r && n && m && r)
    {
          init ();
          makeGrammar ();
          solve ();
    }
    return 0;    
}

Measured memory_bytes: 4588
inputs = readlines

input=[]
for i in 1..inputs.size do
    input.push(inputs[i-1].split)
end

n = input[0][0].to_i
k = input[0][1].to_i
s = input[1][0].split("")

stack = []
if s[0] == "0"
    stack.push(0)
end
count = 0
tar = s[0]

for i in 1..n do 
    if tar != s[i-1] 
        tar = s[i-1]
        stack.push(count)
        count = 1
    else
        count += 1
    end
end

stack.push(count)
if s[n-1] == "0"
    stack.push(0)
end


sum = stack[0]
max = 1
point = 2*k+1
2.step(stack.size,2) do |i|
    sum += stack[i-1]
    sum += stack[i]
    if i > point
        sum -= stack[i-1-point]
        sum -= stack[i-point]
    end
    if sum > max
        max = sum 
    end
end

if stack.size == 1
    max = n
end
p max

Measured memory_bytes: 7804
#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <math.h>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <stdlib.h>
#include <utility>
#include <set>
#include <map>
#include <string.h>
#include <cstring>
#include <queue>
 
using namespace std;


int main() {
    int k, n;
    cin >> k >> n;
    int ans=0;
    
    vector<int> a(n*2);
    for(int i=0; i<n; i++){
        cin >> a[i];
    }
    
    for(int i=n; i<n*2; i++){
        a[i]=a[i-n]+k;
    }
    
    ans = a[n-1] - a[0];
    for(int i=1; i<n; i++){
        ans = min(ans, a[i+n-1]-a[i]);
    }
    
    cout << ans << endl;
    
    return 0;
 }


Measured memory_bytes: 1792
#include<cmath>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cfloat>
 
using namespace std;
 
double EPS = 1e-10;
 
double add(double a, double b){
  if(abs(a+b) < EPS * (abs(a)+abs(b)))return 0;
  return a+b;
}
 
struct point{
  double x, y;
  point(){}
  point(double x,double y) : x(x) , y(y){}
 
  point operator + (point p){
    return point(add(x,p.x), add(y,p.y));
  }
 
  point operator - (point p){
    return point(add(x,-p.x), add(y,-p.y));
  }
 
  point operator * (double d){
    return point(x*d,y*d);
  }
};
 
struct segment{
  point a,b;
};
 
double dot(point a, point b) {
  return (a.x * b.x + a.y * b.y);
}
 
double cross(point a, point b) {
  return (a.x * b.y - a.y * b.x);
}
 
int is_intersected_ls(point a1, point a2, point b1, point b2) {
  return ( cross(a2-a1, b1-a1) * cross(a2-a1, b2-a1) < EPS ) &&
         ( cross(b2-b1, a1-b1) * cross(b2-b1, a2-b1) < EPS );
}

 double vec_abs(point a){
  return sqrt(a.x*a.x+a.y*a.y);
}

int ccw(point p0, point p1, point p2){
  point a = p1 - p0;
  point b = p2 - p0;
  if(cross(a,b)>EPS)return +1;
  if(cross(a,b)<EPS)return -1;
  if(dot(a,b)<-EPS)return +2;
  if(a.x*a.x+a.y*a.y<b.x*b.x+b.y*b.y)return -2;
  return 0;
}

int is_point_on_line(point a, point b, point c) {
  return cross(b-a, c-a)==0.0 &&
         (dot(b-a, c-a) > -EPS) &&
         (dot(a-b, c-b) > -EPS);
}

int inside(point p, point* ps, int n){
  segment t;
  t.a=t.b=p;
  t.b.x=10000000;
  ps[n]=ps[0];
  double ymx=-DBL_MAX,ymn=DBL_MAX;
  for(int i=0;i<n;i++){
    ymx=max(ymx,ps[i].y);
    ymn=min(ymn,ps[i].y);
  }
  if(t.a.y<=ymn||t.a.y>=ymx)return 0;
  /*
  double xmx=-DBL_MAX,xmn=DBL_MAX;
  for(int i=0;i<n;i++){
    xmx=max(xmx,ps[i].x);
    xmn=min(xmn,ps[i].x);
  }
  if(t.a.x<=xmn||t.a.x>=xmx)return 0;
  */

  int cnt1=0;
  for(int i=0;i<n;i++){
    if(is_point_on_line(t.a,t.b,ps[i]))cnt1++;
  }

  int cnt=0;
  for(int i=0;i<n;i++){
    if(is_intersected_ls(ps[i],ps[i+1],t.a,t.b))cnt++;
  }
  cnt-=cnt1;

  return cnt%2;
}

int main(void){
  int n;
  point p[4],k,s;
 
  cin >> n;
  while(n--){

    for(int i=0;i<3;i++)
      cin >> p[i].x >> p[i].y;
     
    cin >> k.x >> k.y >> s.x >> s.y;

    if(inside(k,p,3)!=inside(s,p,3))cout << "OK" << endl;
    else cout << "NG" << endl;
     
  }
 
  return 0;
}

Measured memory_bytes: 952
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<map>
#include<vector>
#include<queue>
#include<stack>
#include<climits>
#include<set>
#include<utility>
#include<typeinfo>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef set<int> S;
#define rep(i, n) for(int i=0; i<n; i++)
const ll MOD=1e9+7;

int main(){

	int d;
	cin >> d;
	if(d==25){
		cout << "Christmas" << endl;
	} else if(d==24){
		cout << "Christmas Eve" << endl;
	} else if(d==23){
		cout << "Christmas Eve Eve" << endl;
	} else {
		cout << "Christmas Eve Eve Eve" << endl;
	}

	return 0;
}


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

using namespace std;

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

    int ans = 0;
    for(int i=1; i<=N; i++) {
        if(to_string(i).size()%2) {
            ++ans;
        }
    }

    cout << ans << endl;
    return 0;
}


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

class Program
{
    static void Main(string[] args)
    {
        int N = Int32.Parse(Console.ReadLine());
        var a = Int32.Parse(N.ToString().Substring(N.ToString().Length - 1, 1));
        var josusi = "";
        if (a == 2
            || a == 4
            || a == 5
            || a == 7
            || a == 9)
        {
            josusi = "hon";
        }
        else if (a == 0
            || a == 1
            || a == 6
            || a == 8)
        {
            josusi = "pon";
        }
        else
        {
            josusi = "bon";
        }
        Console.WriteLine(josusi);
    }
}


Measured memory_bytes: 17488
#include <bits/stdc++.h>
#define rep(i,n) for(long long int i = 0; i < n; i++)
#define print(n) std::cout << n << std::endl
#define _print(n) std::cout << n
using namespace std;
typedef long long ll;
const int N = 1000000;

int main() {
    ll h, w;
    cin >> h >> w;

    ll s[55][55];

    for (ll i = 1; i <= h; ++i) {
        string S;
        cin >> S;
        for (ll j = 1; j <= w; ++j) {
            if (S[j - 1] == '#')s[i][j] = 9;
            else s[i][j] = 0;
        }
    }

    for (ll i = 1; i <= h; ++i) {
        for (ll j = 1; j <= w; ++j) {
            if(s[i][j] == 9){
                if(s[i - 1][j - 1] != 9)s[i - 1][j - 1]++;
                if(s[i - 1][j    ] != 9)s[i - 1][j    ]++;
                if(s[i - 1][j + 1] != 9)s[i - 1][j + 1]++;
                if(s[i    ][j - 1] != 9)s[i    ][j - 1]++;
                if(s[i    ][j + 1] != 9)s[i    ][j + 1]++;
                if(s[i + 1][j - 1] != 9)s[i + 1][j - 1]++;
                if(s[i + 1][j    ] != 9)s[i + 1][j    ]++;
                if(s[i + 1][j + 1] != 9)s[i + 1][j + 1]++;
            }
        }
    }
    for (ll i = 1; i <= h; ++i) {
        for (ll j = 1; j <= w; ++j) {
            if (s[i][j] == 9)_print('#');
            else _print(s[i][j]);
        }
        cout << endl;
    }
}

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

int main() {
  int h, w, k;
  cin >> h >> w >> k;
  vector<string> s(h);
  int ans = 0;
  for (int i = 0; i < h; i++) cin >> s[i];
  for (int i = 0; i < (1<<h); i++) {
    for (int j = 0; j < (1<<w); j++) {
      int count = 0;
      for (int x = 0; x < h; x++) {
        for (int y = 0; y < w; y++) {
          if (i>>x & 1) continue;
          if (j>>y & 1) continue;
          if (s[x][y] == '#') count++;
        }
      }
      if (count == k) ans++;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n, k = LI()
    q = []
    a = LI()
    l = 0
    r = max(a)+1
    while l+1 < r:
        m = (l+r) >> 1
        s = sum([math.ceil(i/m) for i in a])-n
        if s <= k:
            r = m
        else:
            l = m
    print(r)
    return

#Solve
if __name__ == "__main__":
    solve()


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

// int/long:            -2,147,483,648 - 2,147,483,647 (-2^31 <= int < 2^31)
// long/long long:      -9,223,372,036,854,775,808 - 9,223,372,036,854,775,807 (-2^63 <= long < 2^63)

#define INF (1<<30)
//1,073,741,824
//= 536,870,912 *2

#define MOD 1000000007

#define Rep0(i, n)      for (auto i=0; i<n; i++)
#define Rep1(i, n)      for (auto i=1; i<=n; i++)
#define Sort(P) sort(P.begin(), P.end())
#define Rev(P)  reverse(P.begin(), P.end())

int     main() {
        string S;
        cin >>S;
        char C=S.back();
        if (('2'==C)||('4'==C)||('5'==C)||('7'==C)||('9'==C))
                cout <<"hon" <<endl;
        else if ('3'==C)
                cout <<"bon" <<endl;
        else
                cout <<"pon" <<endl;
        return 0;
}

Measured memory_bytes: 3624
/*
 * a.cc: 
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>

using namespace std;

/* constant */

const int MAX_N = 100;

/* typedef */

struct Edge {
  int i, j, c;
  Edge() {}
  Edge(int _i, int _j, int _c): i(_i), j(_j), c(_c) {}
  bool operator<(const Edge &e) const { return c < e.c; }
};

typedef vector<Edge> ve;

struct UFT {
  int links[MAX_N], ranks[MAX_N], sizes[MAX_N];

  void clear(int n) {
    for (int i = 0; i < n; i++) links[i] = i, ranks[i] = sizes[i] = 1;
  }
  UFT() {}
  UFT(int n) { clear(n); }

  int root(int i) {
    int i0 = i;
    while (links[i0] != i0) i0 = links[i0];
    return (links[i] = i0);
  }

  int rank(int i) { return ranks[root(i)]; }
  int size(int i) { return sizes[root(i)]; }
  bool same(int i, int j) { return root(i) == root(j); }

  int merge(int i0, int i1) {
    int r0 = root(i0), r1 = root(i1), mr;
    if (r0 == r1) return r0;
    if (ranks[r0] == ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      ranks[r0]++;
      mr = r0;
    }
    else if (ranks[r0] > ranks[r1]) {
      links[r1] = r0;
      sizes[r0] += sizes[r1];
      mr = r0;
    }
    else {
      links[r0] = r1;
      sizes[r1] += sizes[r0];
      mr = r1;
    }
    return mr;
  }
};

/* global variables */

/* subroutines */

/* main */

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

  ve es;

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) {
      int ai;
      cin >> ai;
      if (ai >= 0) es.push_back(Edge(i, j, ai));
    }
  sort(es.begin(), es.end());

  UFT uft(n);
  int en = es.size(), sum = 0;

  for (int i = 0; i < en; i++) {
    Edge &ei = es[i];
    if (! uft.same(ei.i, ei.j)) {
      uft.merge(ei.i, ei.j);
      sum += ei.c;
    }
  }

  printf("%d\n", sum);
  return 0;
}

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

using namespace std;

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

  int n;
  cin >> n;

  vector<int> P(n);
  for (int& i : P) {
    cin >> i;
  }

  int m = P[0];
  int ans = 0;
  for (int i = 0; i < n; i++) {
    m = min(m, P[i]);
    if (m >= P[i]) ans++;
  }

  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <cstdio>
#include <ctype.h>
#include <functional>
#include <iostream>
#include <cassert>
#include <cfloat>
#include <climits>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
#define int long long
using namespace std;
int f(int b, int n) {
	int res = 0;
	while (n > 0) {
		res += n % b;
		n /= b;
	}
	return res;
}
signed main() {
	int n ,s;
	cin >> n;
	cin >> s;
	if (n == s) {
		if (f(n + 1, n) == s) {
			cout << n + 1 << endl;
		}
		return 0;
	}
	int a;
	if (n > s) {
		a = n - s;
	}
	else {
		a = s - n;
	}
	int res = 1000000000000;

	for (int i = 1; i*i <= a; i++) {
		if (a % i == 0) {
			if (f(i + 1, n) == s) {
				res = min(res, i + 1);
			}
			if (f((a / i) + 1, n) == s) {
				res = min(res, (a / i) + 1);
			}
		}
	}
	if (f(a + 1, n) == s) {
		res = min(res, a + 1);
	}
	if (res != 1000000000000) {
		cout << res << endl;
	}
	else {
		cout << -1 << endl;
	}
	return 0;
}

Measured memory_bytes: 256
use proconio::*;

fn calc(mut a: Vec<(u32, i32)>, item: (u32, i32)) -> Vec<(u32, i32)> {
    let mut b = a.iter().map(|a| (a.0 + item.0, a.1 + item.1)).collect::<Vec<_>>();
    let mut c = Vec::with_capacity(a.len() * 2);
    while !(a.is_empty() || b.is_empty()) {
        if a.last().unwrap().1 >= b.last().unwrap().1 {
            c.push(a.pop().unwrap());
        } else {
            c.push(b.pop().unwrap());
        }
    }
    for p in a.into_iter().chain(b.into_iter()).rev() {
        c.push(p);
    }
    c.reverse();
    let mut val = 0;
    for c in c.iter_mut() {
        val = std::cmp::max(val, c.0);
        c.0 = val;
    }
    c
}

#[fastout]
fn run() {
    input! {
        n: usize,
        mut item: [(u32, i32); n],
        q: usize,
        ask: [(usize, i32); q],
    }
    item.insert(0, (0, 0));
    let mut memo = vec![vec![]; n + 1];
    memo[1] = vec![(0, 0), item[1]];
    let batch = 9;
    for i in 2..=std::cmp::min(n, 1 << batch) {
        memo[i] = calc(memo[i / 2].clone(), item[i]);
    }
    for (start, width) in ask {
        let ans = if start < (1 << batch) {
            memo[start].iter().filter(|p| p.1 <= width).max().unwrap().0
        } else {
            let mut dp = vec![(0, 0)];
            let mut pos = start;
            while pos >= (1 << batch) {
                dp = calc(dp, item[pos]);
                pos /= 2;
            }
            let mut ans = 0;
            for &(v, w) in memo[pos].iter() {
                while let Some(p) = dp.last() {
                    if p.1 + w > width {
                        dp.pop();
                    } else {
                        break;
                    }
                }
                if let Some(p) = dp.last() {
                    ans = std::cmp::max(ans, v + p.0);
                }
            }
            ans
        };
        println!("{}", ans);
    }
}

fn main() {
    run();
}


Measured memory_bytes: 17516
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

in_n = lambda: int(readline())
in_nn = lambda: map(int, readline().split())
in_s = lambda: readline().rstrip().decode('utf-8')
in_nl = lambda: list(map(int, readline().split()))
in_nl2 = lambda H: [in_nl() for _ in range(H)]
in_map = lambda: [s == ord('.') for s in readline() if s != ord('\n')]
in_map2 = lambda H: [in_map() for _ in range(H)]
in_all = lambda: map(int, read().split())


def main():

    N, K = in_nn()

    X = []
    Y = []
    for i in range(N):
        x, y = in_nn()
        X.append(x)
        Y.append(y)

    sort_x = sorted(set(X))
    sort_y = sorted(set(Y))

    nx = len(sort_x)
    ny = len(sort_y)

    total_sum = [[0 for _ in range(nx + 1)] for _ in range(ny + 1)]

    for i in range(N):
        x, y = X[i], Y[i]
        ix = sort_x.index(x)
        iy = sort_y.index(y)
        total_sum[iy + 1][ix + 1] += 1

    for y in range(ny + 1):
        for x in range(nx):
            total_sum[y][x + 1] += total_sum[y][x]

    for x in range(nx + 1):
        for y in range(ny):
            total_sum[y + 1][x] += total_sum[y][x]

    def calc_area(u, d, l, r):
        return total_sum[d][r] - total_sum[u][r] - total_sum[d][l] + total_sum[u][l]

    ans = 10**19
    for y1 in range(ny + 1):
        for y2 in range(y1 + 2, ny + 1):
            for x1 in range(nx + 1):
                for x2 in range(x1 + 2, nx + 1):
                    if calc_area(y1, y2, x1, x2) >= K:
                        area = (sort_x[x2 - 1] - sort_x[x1]) * (sort_y[y2 - 1] - sort_y[y1])
                        ans = min(ans, area)

    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9404
#include<bits/stdc++.h>
using namespace std;
char s[200005],t[200005];
int h,w,n,sr,sc;
int walk1(){
	int l=1,r=h;
	for(int i=n;i>=1;i--){
		if(t[i]=='U')
			r=min(h,r+1);
		else if(t[i]=='D')
			l=max(l-1,1);
		if(s[i]=='U')
			l++;
		else if(s[i]=='D')
			r--;
		if(l>r)
			return 1;
	}
	return (sr<l||sr>r); 
}
int walk2(){
	int l=1,r=w;
	for(int i=n;i>=1;i--){
		if(t[i]=='L')
			r=min(w,r+1);
		else if(t[i]=='R')
			l=max(l-1,1);
		if(s[i]=='R')
			r--;
		else if(s[i]=='L')
			l++;
		if(l>r)
			return 1;
	}
	return (sc<l||sc>r); 
}
int main(){
	scanf("%d%d%d",&h,&w,&n);
	scanf("%d%d",&sr,&sc);
	scanf("%s",s+1);
	scanf("%s",t+1);
	if(walk1()||walk2())
		puts("NO");
	else puts("YES");
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define lli long long int

using namespace std;

int main()
{
    string a,b,c;
    cin>>a>>b>>c;
    lli len1,len2,len3,x=0,y=0,z=0;
    len1=a.length();
    len2=b.length();
    len3=c.length();
    lli flag=1;
    while(1)
    {
        if(flag==1&&x==len1)
        {
            cout<<"A\n";
            break;
        }
        else if(flag==2&&y==len2)
        {
            cout<<"B\n";
            break;
        }
        else if(flag==3&&z==len3)
        {
            cout<<"C\n";
            break;
        }
        else if(flag==1)
        {
            if(a[x]=='a')
            {
                flag=1;
            }
            else if(a[x]=='b')
            {
                flag=2;
            }
            else
            {
                flag=3;
            }
            x++;
        }
        else if(flag==2)
        {
            if(b[y]=='a')
            {
                flag=1;
            }
            else if(b[y]=='b')
            {
                flag=2;
            }
            else
            {
                flag=3;
            }
            y++;
        }
        else
        {
            if(c[z]=='a')
            {
                flag=1;
            }
            else if(c[z]=='b')
            {
                flag=2;
            }
            else
            {
                flag=3;
            }
            z++;
        }

    }

    //cout << "Hello world!" << endl;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define dd double
#define endl "\n"
#define pb push_back
#define all(v) v.begin(),v.end()
#define mp make_pair
#define fi first
#define se second
#define vll vector<ll>
#define pll pair<ll,ll>
#define fo(i,n) for(int i=0;i<n;i++)
#define fo1(i,n) for(int i=1;i<=n;i++)
ll mod=1000000007;
ll n,k,t,m,q,flag=0;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds; 
// #define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(a) -- no. of elements strictly less than a
// s.find_by_order(i) -- itertor to ith element (0 indexed)
ll min(ll a,ll b){if(a>b)return b;else return a;}
ll max(ll a,ll b){if(a>b)return a;else return b;}
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifdef NOOBxCODER
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else 
    #define NOOBxCODER 0
    #endif
    //cin>>t;
    t=1;
    while(t--){
        cin>>n; ll x, k;
        cin>>x>>k;
        cout<<(n+x-1)/x*k;





        
    }
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    return 0;
}


Measured memory_bytes: 3800
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <functional>
#include <vector>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cassert>
#define InfL 1000000000
#define InfLL 1000000000000000000LL
#define mod 1000000007
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=(n-1);(i)>=(0);(i)--)
using namespace std;
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<db> vd;

int main() {
	int K, A, B;
	cin >> K >> A >> B;
	string ans = "NG";
	for (int i = A; i <= B; i++) {
		if (i % K == 0)
			ans = "OK";
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    while (true) {
        int x, y;
        cin >>x >>y;
        if ((0==x)&&(0==y))
            break;
        if (y<x)
            swap(x, y);
        cout <<x <<" " <<y <<endl;
    }
    return 0;
}


Measured memory_bytes: 3112
#include<bits/stdc++.h>
#include <bitset>
using namespace std;
#define ll long long
#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define dcm(a) setprecision(a)<<fixed
#define MOD 1000000007
#define clr(memo, a) memset(memo,a,sizeof(memo))
#define PI acos(-1)
void add_self(int &a,int b){
a+=b;
if(a>=MOD)
    a-=MOD;
}
void sub_self(int &a,int b){
a-=b;
if(a<0)
    a+=MOD;


}
void solve()
{
int n,k;
cin>>n>>k;
vector<int> dp(k+5);
dp[0]=1;
for(int i=0;i<n;i++){
    int x;
    cin>>x;
vector<int> fake(k+5);
    for(int j=k;j>=0;j--){
        int temp=dp[j];
        int l=1+j;
        int r=j+min(x,k-j);
        if(l<=r){
            add_self(fake[l],temp);
            if(r+1<=k)
                sub_self(fake[r+1],temp);
        }
            }
    int pre=0;
    for(int j=0;j<=k;j++){
        add_self(pre,fake[j]);
        add_self(dp[j],pre);
    }
}

cout<<dp[k]<<endl;
}
int main()
{
    fast;
    solve();

    return 0;
}


Measured memory_bytes: 1024