akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;
public class Main{
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n=sc.nextInt(),count=0;
    long x=sc.nextLong();
    long[] a=new long[n];
    for(int i=0;i<n;i++)a[i]=sc.nextLong();
    Arrays.sort(a);
    while(x>0) {
    	x-=a[count];
    	if(x>=0)count++;
    	if(count==n) {
    		if(x!=0)count--;
    		break;
    	}
    }
    System.out.println(count);
  }
}


Measured memory_bytes: 21844
import itertools
import statistics
#n = int(input())
#n, d = list(input().split())
N = int(input())
X = list(map(int, input().split()))
sortedX = sorted(X)
mid_min = sortedX[N//2-1]
mid_max = sortedX[N//2]

for i in X:
    if i <= mid_min:
        print(mid_max)
    else:
        print(mid_min)



Measured memory_bytes: 27180
#include <iostream>

using namespace std;

int main()
{
    int n,k,t,sum=0;
    cin>>n>>k;
    int l[n];
    for(int i=0;i<n;i++)
    {
        cin>>l[i];
    }
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            if(l[i]<=l[j])
            {
                t=l[i];
                l[i]=l[j];
                l[j]=t;
            }
        }
    }
    for(int i=0;i<k;i++)
    {
        sum=sum+l[i];
    }
    cout<<sum;
    return 0;
}


Measured memory_bytes: 256
# We have two integers: A and B.
# Print the largest number among A + B , A − B , and A × B .
def main():
  a, b = input().split(' ')
  a, b = int(a), int(b)

  max = a + b
  if (a - b > max):
    max = a - b
  if (a * b > max):
    max = a * b
  
  print(max)


if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>

using namespace std;

int main(){
	int N = 0;
	int M = 0;
	long long ans = 0;
	cin >> N >> M;

	long long cake[1000][3];
	for(int i = 0; i < N; i++){
		cin >> cake[i][0] >> cake[i][1] >> cake[i][2];
	}

	for(int i = 0; i < pow(2, 3); i++){
		vector<long long> s;
		for(int j = 0; j < N; j++){
			long long p = 0;
			for(int k = 0; k < 3; k++){
				if((i & (1 << k)) > 0){
					p+=cake[j][k];
				} else {
					p-=cake[j][k];
				}
			}
			s.push_back(p);
		}
		sort(s.begin(), s.end(), greater<long long>());
		long long t = 0;
		for(int l = 0; l < M; l++){
			t += s[l];
		}
		ans=max(ans, t);
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <map>
#include <vector>
#include <cmath>

using namespace std;

void c_grid_repating2(void) {
	int h, w;
	char s[51][51];
	cin >> h >> w;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) cin >> s[i][j];
	}

	for (int j = 0; j < h; j++) {
		for (int i = 0; i < w; i++) {
			char org = s[j][i];
			char org_xp1;
			char org_xm1;
			char org_yp1;
			char org_ym1;
			if (org == '#') {
				if (i == 0) org_xm1 = '.';
				else        org_xm1 = s[j][i - 1];

				if (i == w - 1) org_xp1 = '.';
				else            org_xp1 = s[j][i + 1];

				if (j == 0) org_ym1 = '.';
				else        org_ym1 = s[j - 1][i];

				if (j == h - 1) org_yp1 = '.';
				else            org_yp1 = s[j + 1][i];

				if ((org_xm1 == '#') || (org_xp1 == '#') || (org_ym1 == '#') || (org_yp1 == '#')) continue;

				cout << "No" << endl;
				return;
			}
		}
	}
	cout << "Yes" << endl;
}

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

Measured memory_bytes: 3640
// A - K-City

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// const int INF = 2147483647;
// const ll INF = 9223372036854775807;
// const ll MOD = 1e9 + 7;

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

	int ans = (n - 1) * (m - 1);

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import collections,sys
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
n,q=LI()
ab=[LI() for _ in [None]*(n-1)]
px=[LI() for _ in [None]*q]
ans=[0]*(n+1)
graph={i:collections.deque() for i in range(1,n+1)}
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
for p,x in px:
    ans[p]+=x
seen=[0]*(n+1)
stack=[]
def dfs():
    seen[1]=1
    stack.append(1)
    while stack:
        s=stack.pop()
        if not graph[s]:
            continue
        for j in range(len(graph[s])):
            gno=graph[s].popleft()
            if seen[gno]:
                continue
            seen[gno]=1
            stack.append(gno)
            ans[gno]+=ans[s]
dfs()
print(*ans[1:])

Measured memory_bytes: 260528
#include <iostream>
#include <stack>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;

int main(){

	stack<int>S1;
	stack<pair<int, int> >S2;
	char ch;
	int sum = 0;
	for (int i = 0;cin>>ch; i++){
		if (ch == '\\')S1.push(i);
		else if (ch == '/' && S1.size() > 0){
			int j = S1.top(); S1.pop();
			sum += i - j;
			int a = i - j;
			while (S2.size() > 0 && S2.top().first > j){
				a += S2.top().second; S2.pop();
			}
			S2.push(make_pair(j, a));
		}
	}


	vector<int>ans;
	int t = 0;
	while (S2.size() > 0){ ans.push_back(S2.top().second); S2.pop(); }
	reverse(ans.begin(), ans.end());
	cout << sum << "\n";
	cout << ans.size();
	for (int i = 0; i < ans.size(); i++){
		cout << " ";
		t += ans[i];
		cout << ans[i];
	}cout << "\n";

	return 0;
}

Measured memory_bytes: 1288
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(a==b)
        cout<<"Draw"<<endl;
    if(a==1)
        a=1+13;
    if(b==1)
        b=1+13;
    if(a>b)
    cout<<"Alice"<<endl;
    if(a<b)
        cout<<"Bob"<<endl;

    return 0;

}


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


ull gcd(ull x, ull y){ return (x%y)? gcd(y, x%y) : y;}
ull lcm(ull x, ull y){ return x / gcd(x, y) * y;}

int main(){
    int n; cin >>n;
    vector<ull> t(100);
    ull ans = 0;
    for(int i=0; i<n; i++){
        cin >> t[i];
        if(i==0) ans = t[i];
        else{
            ans = lcm(ans, t[i]);
        }
    }
    cout << ans << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;

const int INF = 1000000000;

int main()
{
  int A, B, C, D, E, F;
  scanf("%d %d %d %d %d %d", &A, &B, &C, &D, &E, &F);
  int ans_water = -1, ans_sugar = -1;
  for (int op1 = 0; op1 * 100 * A <= F; ++op1) {
    for (int op2 = 0; op2 *100 * B <= F; ++op2) {
      int water = op1 * 100 * A + op2 * 100 * B;
      if (water == 0 or water > F) { continue; }
      int capa = E * water / 100;
      for (int op3 = 0; op3 * C <= capa; ++op3) {
        for (int op4 = 0; op4 * D <= capa; ++op4) {
          int sugar = op3 * C + op4 * D;
          if (sugar > capa) { continue; }
          if (sugar + water > F) { continue; }
          if (ans_water == -1) {
            ans_water = water;
            ans_sugar = sugar;
          }
          else if (ans_sugar * water < sugar * ans_water) {
            ans_water = water;
            ans_sugar = sugar;
          }
        }
      }
    }
  }
  printf("%d %d\n", ans_water + ans_sugar, ans_sugar);
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
//define
typedef pair<int,int>pi;
// #define int long long
#define rep(x,y) for(int i=x;i<y;i++)
#define REP(x,y) for(int j=x;j<y;j++)
#define Rep(x,y) for(int k=x;k<y;k++)
#define all(x) x.begin(),x.end()
#define pb() push_back()
#define mod 100000007
#define elif else if
#define str string

signed main(){
  int A,B,N,M,O,P,count=0,count2=0,Amax=0,imin=0,Amin=0;
  double d;
  char c;
  string S,T,R;
  cin>>N>>S>>T;
  rep(0,N){
    R+=S[i];
    R+=T[i];
  }
  cout<<R<<endl;
}


Measured memory_bytes: 256
package main

import (
    "fmt"
    "os"
)

func get_op(x int) string {
    if x == 1 {
        return "+"
    }
    return "-"
}

func main() {
    var abcd string
    fmt.Scan(&abcd)
    a := int(abcd[0]) - 48
    b := int(abcd[1]) - 48
    c := int(abcd[2]) - 48
    d := int(abcd[3]) - 48
    s := [][]int{ {-1, -1, -1}, {-1, -1, 1}, {-1, 1, -1}, {-1, 1, 1}, {1, -1, -1}, {1, -1, 1}, {1, 1, -1}, {1, 1, 1} }
    for _, v := range(s) {
        if (a + v[0] * b + v[1] * c + v[2] * d == 7) {
            op0 := get_op(v[0])
            op1 := get_op(v[1])
            op2 := get_op(v[2])
            fmt.Printf("%d%s%d%s%d%s%d=7\n", a, op0, b, op1, c, op2, d)
            os.Exit(0)
        }
    }
}


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

int main() {
  long long w, h, x, y;

  cin >> w >> h >> x >> y;

  cout << fixed << setprecision(12) << (w * h / 2.0L) << ' ' << (x + x == w && y + y == h) << endl;
}

Measured memory_bytes: 3772
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>
#include <climits>
#include <functional>

#define REP(i,n) for(int i = 0;i < n;i++)

using namespace std;
typedef long long ll;
const int INF = INT_MAX / 4;

const int max_n = 1e3;


bool needed(int N, int K, int* a, int c) {
  if (c >= N) return true;
  bool dp[N][K+1];
  REP(i, N) REP(j, K+1) dp[i][j] = false;

  REP(i, N) {
    dp[i][0] = true;
    for(int j = 1;j <= K;j++) {
      if (i != c && j == a[i]) dp[i][j] = true;
      else if (i != 0) {
	if (dp[i-1][j]) dp[i][j] = true;
	if (i != c && j >= a[i] && dp[i-1][j-a[i]]) dp[i][j] = true;
      }
    }
  }

  for (int i = max(K - a[c], 0);i < K;i++) {
    if (dp[N-1][i]) return true;
  }
  return false;
}


int bs(int N, int K, int* a) {
  int u = N, l = 0;
  while(u != l) {
    int c = (u + l) / 2;
    if (needed(N, K, a, c)) u = c - 1;
    else l = c;
    if (u - l <= 3) break;
  }
  for (int i = l;i <= u;i++) {
    if (needed(N, K, a, i)) return i;
  }
  return u + 1;
}


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

  int N, K;
  cin >> N >> K;
  int a[N];
  REP(i, N) cin >> a[i];

  sort(a, a + N);

  // int need = 0;
  // REP(i, N) {
  //   need += (int)(needed(N, K, a, i));
  // }
  int need = bs(N, K, a);

  cout << need << "\n";
  return 0;
}


Measured memory_bytes: 24704
#include <stdio.h>

int main(void)
{
	int A,B,C,D,E,K,jikan,oniku,s,aa;
	scanf("%d",&A);
	scanf("%d",&B);
	scanf("%d",&C);
	scanf("%d",&D);
	scanf("%d",&E);
	if(A<0)
	{
	K=A*-1;
	jikan=K*C+B*E+D;
	printf("%d\n",jikan);
	}
	else if(A==0){
		s=B-0;
		oniku=s*E+D;
		printf("%d\n",oniku);
	}
	else{
		s=B-A;
		aa=E*s;
		printf("%d\n",aa);
	}
	return 0;
}


Measured memory_bytes: 2104
/************************************
/ AUTHOR : YATHARTH GOSWAMI         /  
/ ALIAS : hacker_yg                 /
/ INSTITUTE : IIT Kanpur            /
************************************/
//          TEMPLATE                //

#include <bits/stdc++.h>

#define ll long long
#define MOD 1000000007
#define pb push_back
#define mp make_pair
#define F first
#define S second

using namespace std;

int main(){
    string s;
    cin >> s;
    if (s == "ABC") cout << "ARC";
    else cout << "ABC";
    return 0;
}




Measured memory_bytes: 3624
#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int,int> PP;

/*
    freopen("input","r",stdin);
    freopen("output","w",stdout);
*/

int N;

int W[2010], B[2010];

int DP[2010][2010];

int WW[2010][2010], WB[2010][2010], BW[2010][2010], BB[2010][2010];

bool OK[2010][2010];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    memset(DP, 0, sizeof(DP));
    memset(OK, 0, sizeof(OK));
    memset(W, 0, sizeof(W));
    memset(B, 0, sizeof(B));
    cin >> N;
    int k = 1;
    for (int i = 0;i < 2 * N;i++) {
        char c;
        int j;
        cin >> c >> j;
        if (c == 'W') W[j] = k;
        else B[j] = k;
        k++;
    }
    memset(WW, 0, sizeof(WW));
    memset(BW, 0, sizeof(BW));
    memset(WB, 0, sizeof(WB));
    memset(BB, 0, sizeof(BB));
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            if (W[i] >= W[j]) WW[i][j]++;
            if (W[i] >= B[j]) WB[i][j]++;
            if (B[i] >= B[j]) BB[i][j]++;
            if (B[i] >= W[j]) BW[i][j]++;
        }
    }
    for (int i = 1;i <= N;i++) {
        for (int j = 1;j <= N;j++) {
            WW[i][j] += WW[i][j - 1];
            BW[i][j] += BW[i][j - 1];
            WB[i][j] += WB[i][j - 1];
            BB[i][j] += BB[i][j - 1];
        }
    }
    for (int i = 0;i <= N;i++) {
        for (int j = 0;j <= N;j++) {
            if (i == N && j == N) continue;
            int k = DP[i][j];
            int u = i + j;
            if (i + 1 <= N) {
                int idx = W[i + 1] + i - WW[i + 1][i] + j - WB[i + 1][j];
                int nex = i + j + 1;
                if (OK[i + 1][j] == 0) {
                    DP[i + 1][j] = DP[i][j] + abs(idx - nex);
                    OK[i + 1][j] = 1;
                }
                else DP[i + 1][j] = min(DP[i + 1][j], DP[i][j] + abs(idx - nex));
            }
            if (j + 1 <= N) {
                int idx = B[j + 1] + j - BB[j + 1][j] + i - BW[j + 1][i];
                int nex = i + j + 1;
                if (OK[i][j + 1] == 0) {
                    DP[i][j + 1] = DP[i][j] + abs(idx - nex);
                    OK[i][j + 1] = 1;
                }
                else DP[i][j + 1] = min(DP[i][j + 1], DP[i][j] + abs(idx - nex));
            }
        }
    }
    cout << DP[N][N] << endl;
    return 0;
}

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

template<class T>
struct lazy_segment_tree{
  int n;
  vector<T> dat,lazy;
  T de,le;

  T f(T a,T b){
    return min(a,b);
  }
  T g(T& a,T b){
    a = b;
  }
  T h(T& a,T b){
    a = b;
  }

  lazy_segment_tree(){}
  lazy_segment_tree(int sz){
    n = 1;
    while(n<=sz)n<<=1;
    de = (1LL<<31)-1;
    le = (1LL<<31)-1;
    dat.resize(2*n-1,de);
    lazy.resize(2*n-1,le);
  }
  lazy_segment_tree(vector<T> const& v){
    int sz = v.size();
    n = 1;
    while(n<=sz)n<<=1;
    de = (1LL<<31)-1;
    le = (1LL<<31)-1;
    dat.resize(2*n-1,de);
    lazy.resize(2*n-1,le);
    for(int i=0;i<sz;++i){
      dat[i+n-1] = v[i];
    }
    for(int i=n-2;i>=0;--i){
      dat[i] = f(dat[i*2+1],dat[i*2+2]);
    }
  }

  void eval(int k,int l,int r){
    if(lazy[k]!=le){
      g(dat[k],lazy[k]);
      if(r-l>1){
        h(lazy[2*k+1],lazy[k]);
        h(lazy[2*k+2],lazy[k]);
      }
      lazy[k] = le;
    }
  }

  void update(int a,int b,T x,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    eval(k,l,r);
    if(b<=l||r<=a)return;
    if(a<=l&&r<=b){
      h(lazy[k],x);
      eval(k,l,r);
    }else{
      update(a,b,x,2*k+1,l,(r+l)/2);
      update(a,b,x,2*k+2,(r+l)/2,r);
      dat[k] = f(dat[2*k+1],dat[2*k+2]);
    }
  }

  T query(int a,int b,int k=0,int l=0,int r=-1){
    if(r<0)r=n;
    if(b<=l||r<=a)return de;
    eval(k,l,r);
    if(a<=l&&r<=b)return dat[k];
    T vl = query(a,b,2*k+1,l,(r+l)/2);
    T vr = query(a,b,2*k+2,(r+l)/2,r);
    return f(vl,vr);
  }

  T operator[](int k){
    return query(k,k+1);
  }

};

void RUQ(){
  int n,q;
  cin>>n>>q;
  lazy_segment_tree<int> seg(n);
  while(q--){
    int com;
    cin>>com;
    if(com){
      int i;
      cin>>i;
      cout<<(seg[i])<<endl;
    }else{
      int s,t,x;
      cin>>s>>t>>x;
      seg.update(s,t+1,x);
    }
  }
}

int main(){
  RUQ();
}


Measured memory_bytes: 4892
import sys

readline = sys.stdin.buffer.readline


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    m = sum(A) // 2

    s = 0
    c = 0
    while s < m:
        s += A[c]
        c += 1

    d1 = abs(sum(A[:c]) - sum(A[c:]))
    d2 = abs(sum(A[:c-1]) - sum(A[c-1:]))

    if d1 < d2:
        print(d1)
    else:
        print(d2)


main()


Measured memory_bytes: 21988
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
    int N, K, X, ans = 0;
    cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        cin >> X;
        if(K <= X)
            ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<map>
#include<algorithm>
#include<math.h>
#include<functional>
#include<set>
#include<queue>
#include<iomanip>
#include<assert.h>
#include<string>
typedef long long ll;

using namespace std;
const int N = 2e3 + 10 , MOD = 1e9 + 7;
ll C[N][N];
int n , k ;
void pre()
{
	for (int i = 0; i <= n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 || j == i)
				C[i][j] = 1;
			else
				C[i][j] = (i > 0 ? C[i - 1][j - 1] : 0) + (i > 0 ? C[i - 1][j] : 0);
			C[i][j] %= MOD;
		}
	}
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	
	cin >> n >> k;
	pre();
	int blue = k, red = n - k;
	for (int i = 1; i <= k; ++i) {
		long long ans = C[blue - 1][i - 1] * C[red + 1][i];
		cout << ans%MOD << endl;
	}

}

Measured memory_bytes: 30208
#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <string>
#include <sstream>
#include <cmath>
#include <functional>
#include <fstream>
#include <cstdlib>
typedef long long ll;
 
#define REP(i, N) for (int i = 0; i < (N); i++)
#define REPP(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define VSORT(c) sort((c).begin(),(c).end())
#define SZ(x) ((int)(x).size())
 
using namespace std;
int main(void){
    
    int N;
    cin >> N;
    ll temp;
    ll max = 0;
    ll min = 10e9;
    REP(i,N){
        cin >> temp;
        if(max < temp) max = temp;
        if(min > temp) min = temp;
    }
    
    cout << abs(max - min) << endl;
    
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio> 
#include <cstring>
#include <cmath>
#include <string>
using namespace std;

int main()
{
	string s;
	cin>>s;
	int ans=0;
	for(int i=s.size()-1;i>0;i--)
	{
		if(s[i]==s[i-1]) continue;
		else
		{
			ans++; 
		}
	}	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 512
N, M, Q = gets.chomp.split(" ").map(&:to_i)
QUE = Array.new(Q).map{
  gets.chomp.split(" ").map(&:to_i)
}

A = []
def srt(n, m)
  (calc; return) if n == 0
  (m..M).each{|j|
    A.push(j)
    srt(n-1, j)
    A.pop
  }
end

ANS = []
def calc()
  ANS << QUE.inject(0){|r, (a, b, c, d)|
    r + (A[b-1] - A[a-1] == c ? d : 0)
  }
end

srt(N, 1)

puts ANS.max


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

#define rep(i, a, b) for(int i = (a); i < (b); ++i)
#define per(i, a, b) for(int i = (b)-1; i >= (a); --i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second

template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<pii> vii;

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);

  int n;
  cin >> n;

  set<int> locs;
  map<int, int> beg, en;

  rep(i,0,n) {
    int a, b;
    cin >> a >> b;
    locs.insert(a);
    locs.insert(b+1);
    beg[a]++;
    en[b+1]++;
  }

  vi pos;
  for (auto x: locs) pos.pb(x);

  const int inf = 1e9+8;
  auto range = [&](int x) -> pii {
    int ba = n, eb = 0;
    pii ans = {inf, 0};
    rep(i,0,sz(pos)) {
      int loc = pos[i];
      ba -= beg[loc];
      eb += en[loc];
  //    cerr << loc << ' ' << ba << ' ' << eb << '\n';
      if (ba <= n-x-1 and eb <= x) {
        ckmin(ans.fst, pos[i]);
        ckmax(ans.snd, pos[i+1]-1);
      }
    }
    return ans;
  };


  int ans = 0;
  if (n%2==0) {
    pii a = range(n/2-1), b = range(n/2);
//    cerr << a.fst << ' ' << a.snd << '\n';
//    cerr << b.fst << ' ' << b.snd << '\n';
    int sa = a.snd-a.fst+1;
    int sb = b.snd-b.fst+1;
    ans = sa+sb-1;
  } else {
    pii a = range(n/2);
 //   cerr << a.fst << ' ' << a.snd << '\n';
    ans = a.snd-a.fst+1;
  }

  cout << ans << '\n';
}

Measured memory_bytes: 61032
my_input = input
 
def less_than(a, b):
    return a[0] < b[0] and a[1] < b[1]
 
n = int(my_input())
a = []
b = []
for _ in range(n):
    ax, ay = my_input().split()
    a.append((int(ax), int(ay)))
for _ in range(n):
    bx, by = my_input().split()
    b.append((int(bx), int(by)))
a = sorted(a, key=lambda x:x[1], reverse=True)
b = sorted(b, key=lambda x:x[0], reverse=False)
ans = 0
ii = set()
for j in range(n):
    for i in range(n):
        if i in ii:
            continue
        if less_than(a[i], b[j]):
            ans += 1
            ii.add(i)
            break
print(ans)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)
#define INF 999999999
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
typedef long long ll;
int dy[]={0, 0, 1, -1, 0};
int dx[]={1, -1, 0, 0, 0};

int main(int argc, char const *argv[]) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int h,w,cnt=0;
  cin>>h>>w;
  char s[50][50];
  FOR(i,1,h+1){
    FOR(j,1,w+1){
      cin>>s[i][j];
    }
  }
  FOR(i,1,h+1){
    FOR(j,1,w+1){
      if (s[i][j] == '#' && s[i][j - 1] != '#' && s[i - 1][j] != '#' && s[i][j + 1] != '#' && s[i + 1][j] != '#') cnt++;
    }
  }
  if(cnt==0) cout<<"Yes"<<endl;
  else  cout<<"No"<<endl;
  return 0;
}


Measured memory_bytes: 256
/*{{{*/
#include<bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define FOR(I, A, B) for (int I = (A); I <= (B); ++I)
#define REPR(I, N) for (int I = (N)-1; I >= 0; --I)
#define REPPR(I, A, B) for (int I = (A); I >= (B); --I)
#define FORS(I, S) for (int I = 0; S[I]; ++I)
#define RS(X) scanf("%s", (X))
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define CASET int ___T; scanf("%d", &___T); for(int cs=1;cs<=___T;cs++)
#define MP make_pair
#define PB emplace_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<LL> VL;
typedef vector<PII> VPII;
typedef pair<LL, LL> PLL;
typedef vector<PLL> VPLL;
template<class T> void _R(T &x) { cin >> x; }
void _R(int &x) { scanf("%d", &x); }
void _R(int64_t &x) { scanf("%lld", &x); }
void _R(double &x) { scanf("%lf", &x); }
void _R(char &x) { scanf(" %c", &x); }
void _R(char *x) { scanf("%s", x); }
void R() {}
template<class T, class... U> void R(T &head, U &... tail) { _R(head); R(tail...); }
template<class T> void _W(const T &x) { cout << x; }
void _W(const int &x) { printf("%d", x); }
void _W(const int64_t &x) { printf("%lld", x); }
void _W(const double &x) { printf("%.16f", x); }
void _W(const char &x) { putchar(x); }
void _W(const char *x) { printf("%s", x); }
template<class T, class U> void _W(const pair<T, U> &x) {_W(x.F); putchar(' '); _W(x.S);}
template<class T> void _W(const vector<T> &x) { for (auto i = x.begin(); i != x.end(); _W(*i++)) if (i != x.cbegin()) putchar(' '); }
void W() {}
template<class T, class... U> void W(const T &head, const U &... tail) { _W(head); putchar(sizeof...(tail) ? ' ' : '\n'); W(tail...); }
#ifdef HOME
#define DEBUG(...) {printf("[DEBUG] ");W(__VA_ARGS__);}
#else
#define DEBUG(...)
#endif
int MOD = 1e9 + 7;
void ADD(LL& x, LL v) {x = (x + v) % MOD; if (x < 0)x += MOD;}
/*}}}*/
void solve() {
	int k, n;
	R(k, n);
	VI v(n);
	int m = 0;
	REP(i, n) {
		R(v[i]);
		if (i) m = max(v[i] - v[i - 1], m);
	}
	m = max(m, v[0] + k - v[n - 1]);
	W(k - m);
}

int main() {

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

#define MULTITEST 0
#if MULTITEST
	CASET {
		solve();
	}
#else
	solve();
#endif
	return 0;
}


Measured memory_bytes: 4068
n, m = map(int, input().split())
l = []
r = []
for i in range(m):
    L, R = map(int, input().split())
    l += [L]
    r += [R]

l_max = max(l)
r_min = min(r)

print(max(r_min - l_max + 1, 0))

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

using namespace std;
using ll = int64_t;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using mii = map<int, int>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using tpi = tuple<int, int, int>;

using vqi = vector<queue<int>>;
using vpi = vector<pii>;
using bs = bitset<60>;
using vbi = vector<bs>;
constexpr ll MOD = 1e9 + 7;


int main() {
    int H, W;
    cin >> H >> W;

    vii diff(H + 1, vi(W + 1));
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int a;
            cin >> a;
            diff[i + 1][j + 1] = a;
        }
    }
    ll M = 0;
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            int b;
            cin >> b;
            ll tmp = abs(diff[i + 1][j + 1] - b);
            diff[i + 1][j + 1] = tmp;
            M = max(M, tmp);
        }
    }

    using DP=vector<vii>;
    ll max_k = 1 * (H + W) * M;
    DP dp(H + 1, vii(W + 1, vi(max_k + 1)));
    dp[1][1][diff[1][1]] = 1;

    for (int i = 1; i <= H; i++) {
        for (int j = 1; j <= W; j++) {
            int d = diff[i][j];
            for (ll k = 0; k <= max_k; k++) {
                if (dp[i][j - 1][abs(k - d)] == 1 || dp[i - 1][j][abs(k - d)] == 1) {
                    dp[i][j][k] = 1;
                }

                if (k + d <= max_k) {
                    if (dp[i][j - 1][k + d] == 1 || dp[i - 1][j][k + d] == 1) {
                        dp[i][j][k] = 1;
                    }
                }
            }
        }
    }

    for (ll i = 0; i <= max_k; i++) {
        if (dp[H][W][i] == 1) {
            cout << i << endl;
            return 0;
        }
    }
}


Measured memory_bytes: 332672
#include<bits/stdc++.h>
    using namespace std;
     
    #define m 1000000007
     
    long long powMod(long long x, long long k) {
    	if (k == 0)     return 1;
    	if (k % 2 == 0) return powMod(x*x, k/2);
    	else            return x*powMod(x, k-1) ;
    }
     
    int main(){
    	long long x;
    	cin >> x;
    	cout << powMod(2,2+x)-2 << endl;
    	return 0;
    }

Measured memory_bytes: 256
#include<cstdio>
#include<cstring>
#include<map>
#include<queue>
#include<algorithm>

using namespace std;

int ch,cv,S,T;
int now[9];
int dis[362900];
priority_queue<pair<int,int> > lst;

int fact[10];

inline int toint(int x[])
{
	int ret = 0;
	for (int i = 0; i < 9; ++ i) {
		int cnt = 0;
		for (int j = i + 1; j < 9; ++ j) cnt += (x[j] < x[i]);
		ret += fact[9 - i - 1] * cnt;
	}
	return ret;
}

static bool h[100];

inline void toarr(int n, int x[]) {
	for (int i = 0; i <= 10; ++ i) h[i] = false;
	for (int i = 1, j, l; i <= 9; ++ i) {
		int t = n / fact[9 - i];
		n -= t * fact[9 - i];
		for (j = 1, l = 0; l <= t; ++ j) {
			if (!h[j]) ++ l;
		}
		-- j; h[j] = true;
		x[i - 1] = j - 1;
	}
}

inline int getin()
{
	static int x[10];
	for(int i = 0;i < 9;i++)
	{
		scanf("%d",&x[i]);
	}
	return toint(x);
}


inline void add(int s,int d)
{
	if (dis[s] != -1)
	{
		if (dis[s] > d)
		{
			dis[s] = d;
			lst.push(make_pair(-d,s));
		}
	} else
	{
		dis[s] = d;
		lst.push(make_pair(-d,s));
	}
}

int main()
{
	fact[0] = 1;
	for (int i = 1; i < 10; ++ i) fact[i] = i * fact[i - 1];
	while(scanf("%d%d",&ch,&cv) == 2)
	{
		if (cv == 0 && ch == 0) break;
		S = getin();
		T = getin();
		
		while(!lst.empty()) lst.pop();
		memset(dis,255,sizeof(dis));
		add(S,0);
		while(!lst.empty())
		{
			int x = lst.top().second;
			int d = -lst.top().first;
			lst.pop();
			if (x == T) break;
			if (dis[x] != d) continue;
			
			int zero = 0,tmp = x;
			toarr(x,now);
			for(int i = 0;i < 9;i++)
			{
				if (now[i] == 0)
				{
					zero = i;
					break;
				}
			}
			int& p = now[zero];
			swap(p,now[(zero + 1) % 9]);
			add(toint(now),d + ch);
			swap(p,now[(zero + 1) % 9]);
			
			swap(p,now[(zero + 8) % 9]);
			add(toint(now),d + ch);
			swap(p,now[(zero + 8) % 9]);
			
			swap(p,now[(zero + 3) % 9]);
			add(toint(now),d + cv);
			swap(p,now[(zero + 3) % 9]);
			
			swap(p,now[(zero + 6) % 9]);
			add(toint(now),d + cv);
			swap(p,now[(zero + 6) % 9]);
		}
		
		printf("%d\n",dis[T]);
	}
	return 0;
}

Measured memory_bytes: 4392
#include<cstdio>
#include<algorithm>
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
using namespace std;
typedef long long ll;
const int maxn=200000+10,mo=1000000007,inf=1000000005;
int mi[maxn],c[maxn],w[maxn],cnt[maxn],fac[maxn],inv[maxn];
int i,j,k,l,t,n,m,ans,num,x,y;
int qsm(int x,int y){
    if (!y) return 1;
    int t=qsm(x,y/2);
    t=(ll)t*t%mo;
    if (y%2) t=(ll)t*x%mo;
    return t;
}
int C(int n,int m){
    if (n<m||m<0) return 0;
    return (ll)fac[n]*inv[m]%mo*inv[n-m]%mo;
}
int main(){
    scanf("%d%d%d",&n,&x,&y);
    fo(i,1,n) mi[i]=inf;
    fac[0]=1;
    fo(i,1,n) fac[i]=(ll)fac[i-1]*i%mo;
    inv[n]=qsm(fac[n],mo-2);
    fd(i,n-1,0) inv[i]=(ll)inv[i+1]*(i+1)%mo;
    fo(i,1,n){
        scanf("%d%d",&c[i],&w[i]);
        mi[c[i]]=min(mi[c[i]],w[i]);
        cnt[c[i]]++;
    }
    fo(i,1,n) 
        if (mi[i]!=inf){
            if (m==0) m=i;
            else if (mi[i]<mi[m]) m=i;
        }
    t=inf;
    fo(i,1,n)
        if (mi[i]!=inf&&i!=m) t=min(t,mi[i]);
    fo(i,1,n){
        if (w[i]!=mi[c[i]]&&w[i]+mi[c[i]]<=x) continue;
        if (c[i]!=m&&w[i]+mi[m]<=y) continue;
        if (c[i]==m&&w[i]+t<=y) continue;
        cnt[c[i]]--;
    }
    num=cnt[m];
    fo(i,1,n)
        if (mi[i]!=inf&&i!=m)
            if (mi[i]+mi[m]<=y) num+=cnt[i];
    ans=1;
    fo(i,1,n)
        if (mi[i]!=inf&&(i==m||mi[i]+mi[m]<=y)){
            ans=(ll)ans*C(num,cnt[i])%mo;
            num-=cnt[i];
        }
    printf("%d\n",ans);
}

Measured memory_bytes: 4864
S = input()
K = int(input())

length = len(S)

num_fixed = 0
pre_char = ''
count = 0
for i in range(length):
    now_char = S[i]
    if pre_char != now_char:
        num_fixed += count//2
        count = 0
    count += 1
    pre_char = now_char
    # print("pre_char:{}, now_char:{}, count:{}".format(pre_char, now_char, count))
num_fixed += count//2

# print(num_fixed)

if S[0] == S[length - 1]:
    head_length = 1
    head_char = S[0]
    for i in range(1, length):
        now_char = S[i]
        if now_char != head_char:
            break
        head_length += 1
    tail_length = 1
    tail_char = S[length - 1]
    for i in range(1, length):
        now_char = S[length - 1 - i]
        if now_char != tail_char:
            break
        tail_length += 1
    if length == head_length == tail_length:
        ans = length * K // 2
    else:
        ans = K * num_fixed - (K - 1) * (head_length // 2 + tail_length // 2 - (head_length + tail_length) // 2)
else:
    ans = num_fixed * K

print(ans)


Measured memory_bytes: 3064
import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	static String[] alphabet = { "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q",
			"r", "s", "t", "u", "v", "w", "x", "y", "z" };

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		BigInteger A = sc.nextBigInteger();
		BigInteger B = sc.nextBigInteger();
		if (A.compareTo(B) == 1) {
			System.out.println("GREATER");
		} else if (A.compareTo(B) == 0) {
			System.out.println("EQUAL");
		} else {
			System.out.println("LESS");
		}
	}

}

Measured memory_bytes: 21844
import java.util.*;
 
public class Main{
  public static void main(String[] args){
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int k=sc.nextInt();
    int[] h=new int[n];
    for(int i=0;i<n;i++){
      h[i]=sc.nextInt();
    }
    Arrays.sort(h);
    long ans=0;
    for(int i=0;i<n-k;i++){
      ans+=h[i];
    }
    System.out.println(ans);
  }
}

Measured memory_bytes: 64868
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
    string s;
    cin >> s;
    set<char> st;
    for (auto c : s)
    {
        if (st.count(c) == 1)
        {
            puts("no");
            return 0;
        }
        st.insert(c);
    }
    puts("yes");
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }

void solve();

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

    int T;
    // cin >> T;
    T = 1;

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

void solve() {
  ll n;
  cin >> n;

  if (n % 2) {
    cout << 0 << endl;
  } else {
    n /= 2;
    
    ll ans = 0;
    rep(i, 10000) {
      ans += n / 5;
      n /= 5;
    }
    cout << ans << endl;
  }
}


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

using namespace std;

int main()
{
    int N; cin >> N;
    
    vector<int> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];

    int ans;
    for (ans = 0; ; ans++) {
        for (int j = 0; j < N; j++) {
            if (A[j] == 0) goto fin;

            if (A[j] % 2 == 0) A[j] /= 2;
            else goto fin;
        }
    }

fin:
    cout << ans << endl;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

lst = list(map(int,input().split()))
#print(lst)
count5 = 0
count7 = 0
for i in lst:
    if i == 5:
        count5+=1
    elif i == 7:
        count7+=1

if count7==1 and count5 ==2:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 9032
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<cstring>
#include<climits>
#include<algorithm>
#include<vector>
#include<cmath>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<tuple>
#include<list>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vii vector<int>
#define vll vector<ll>
#define lb lower_bound
#define pb push_back
#define mp make_pair
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define INF (1 << 30) - 1
#define LLINF (1LL << 61) - 1
// #define int ll
using namespace std;
const int MOD = 1000000007;
const int MAX = 510000;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,x,l[110],ans=0,now=0;
    cin>>n>>x;
    rep(i,n){
        cin>>l[i];
    }
    ans++;
    rep(i,n){
        now+=l[i];
        if(now<=x) ans++;
        else break;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e9+7;



int main(){

    int n;
    cin>>n;

    if (n%1000 == 0){
        cout <<0<<endl;
    }else{
        cout<<1000-(n%1000)<<endl;
    }



}

Measured memory_bytes: 3616
import java.util.Scanner;

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

        int A = scanner.nextInt();
        int B = scanner.nextInt();

        for (int i = 1 ; i <= 1000 ; i++) {
            int eight = (int) (i * 0.08);
            int ten = (int) (i * 0.1);
            if (eight == A && ten == B) {
                System.out.println(i);
                return;
            }
        }

        System.out.println(-1);
    }
}


Measured memory_bytes: 23636
#![allow(unused_imports)]
use std::io::*;
use std::fmt::*;
use std::str::*;
use std::cmp::*;
use std::collections::*;

pub trait InputValue {
    fn parse(s: &str) -> Self;
}

pub fn read<T: InputValue>() -> T {
    let mut buf = String::new();
    let _ = stdin().read_line(&mut buf);
    T::parse(&buf.trim())
}

pub fn readn<T: InputValue>(n: usize) -> Vec<T> {
    let mut vec = vec![];
    for _ in 0..n {
        vec.push(read());
    }
    vec
}

macro_rules! parse_single_value {
    ($($t:ty),*) => {
        $(
            impl InputValue for $t {
                fn parse(s: &str) -> $t { s.parse().unwrap() }
            }
        )*
	}
}
parse_single_value!(i32, i64, f32, f64, usize, String);

macro_rules! parse_tuple {
	($($t:ident),*) => {
		impl<$($t),*> InputValue for ($($t),*) where $($t: InputValue),* {
			fn parse(s: &str) -> ($($t),*) {
				let mut tokens = s.split_whitespace();
				let t = ($($t::parse(tokens.next().unwrap())),*);
				t
			}
		}
	}
}
parse_tuple!(A, B);
parse_tuple!(A, B, C);

// ===

fn main() {
    let (a, b): (i32, i32) = read();
    println!("{}", a*b-a-b+1);
}


Measured memory_bytes: 4352
# include <bits/stdc++.h>
//# pragma GCC optimize("Ofast")
# define pb push_back
# define ll long long
# define fi first
# define se second
# define all(vc) vc.begin(),vc.end()
# define forn(i, n) for (int i = 0; i < int(n); i++)
# define ford(i, n) for (int i = int(n) - 1; i >= 0; i--)
# define fore(i, l, r) for (int i = int(l); i < int(r); i++)
# define fors(i, s) for (int i = 0; s[i]; i++)
# define in freopen("input.txt", "r", stdin)
# define out freopen("output.txt", "w", stdout)
# define speed ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
# define mkp make_pair
# define time cerr << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"
  
using namespace std;
  
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int N = 3e3 + 7;

string s, t;
int n, m, dp[N][N];

int main()
{
	speed;
	cin >> s >> t;
	int n = s.size(), m = t.size();
	forn( i, n + 1 ) {
		forn( j, m + 1 ) {
			if ( !i || !j ) dp[i][j] = 0;
			else if ( s[i - 1] == t[j - 1] ) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
			}
			else {
				dp[i][j] = max( dp[i - 1][j], dp[i][j - 1] );
			}
		}
	}
	int sz = dp[n][m];
	int i = n, j = m;
	char ans[sz + 1];
	ans[sz] = '\0';
	while ( i > 0 && j > 0 ) {
		if ( s[i - 1] == t[j - 1] ) {
			ans[sz - 1] = s[i - 1];
			i--;
			j--;
			sz--;
		}
		else if ( dp[i][j - 1] > dp[i - 1][j] ) {
			j--;
		}
		else {
			i--;
		}
	}
	cout << ans << endl; 
}

Measured memory_bytes: 35584
#include <cstdio>
#include <cstring>
int S[100001],dp[101][100001],n,k,a[100001],c;const int p=1e9+7;
int &s(int x){if(x<0)return c;else return S[x];}
int main()
{
	scanf("%d%d",&n,&k);for(int i=1;i<=n;++i)scanf("%d",&a[i]);for(int i=0;i<=k;++i)s(i)=1;
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<=k;++j)dp[i][j]=((s(j)-s(j-a[i]-1))%p+p)%p;
		for(int j=0;j<=k;++j)s(j)=(s(j-1)+dp[i][j])%p;
	}
	printf("%d\n",dp[n][k]);
}

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

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

    int ans = x / 500 * 1000 + x % 500 / 5 * 5;
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
def resolve():
    a, b = map(int, input().split())
    div_a = set(prime_factorize(a))
    div_b = set(prime_factorize(b))
    print(len(div_a & div_b) + 1)
    # print(div_a)
    # print(div_b)


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


if __name__ == "__main__":
    resolve()


Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

ll n, X;
ll x[200005];
ll y[200005];
ull ans = 18446744073709551615;

int main()
{
    cin>>n>>X;
    for(ll i = 1; i <= n; i++)
    {
        cin>>x[i];
        y[i] = y[i - 1] + x[i];
    }
    for(ll i = 1; i <= n; i++)
    {
        ull now = 0;
        ll k = 2;
        now += k * k * (y[n] - y[max(n - i, 0LL)]);
        for(ll j = n - i; j >= 1; j -= i)
        {
            now += (2 * k + 1) * (y[j] - y[max(j - i, 0LL)]);
            k++;
        }
        now += i * X;
        now += y[n] - y[max(n - i, 0LL)];
        ans = min(ans, now);
    }
    cout<<ans + n * X<<endl;
    return 0;
}


Measured memory_bytes: 3328
#include <iostream>

using namespace std;

#define REP(i, n) for(int i=0; i<n; i++)

typedef long long ll;

ll a, b;
ll q;
ll s[100010], t[100010];

ll findleft(ll start, bool isshrine) {
    ll idx=0;
    ll left=0;
    ll right;
    ll *array;
    if (isshrine) {
        right = a;
        array = s;
    } else {
        right = b;
        array = t;
    }

    while(right-left>1) {
        ll center = (right+left) / 2;
        if (array[center]>start) {
            right = center;
        } else if (array[center]<start) {
            left = center;
        } else {
            idx = center; break;
        }
        idx = left;
    }

    return idx;
}

ll findright(ll l, ll x, ll *array, ll length) {
    ll r;
    if (array[l]>=x || l==length-1) {
        r = l;
    } else {
        r = l+1;
    }

    return r;
}

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

    REP(i, a) {
        cin >> s[i];
    }

    REP(i, b) {
        cin >> t[i];
    }

    REP(i, q) {
        ll x;
        cin >> x;
    
        ll output = 1000000000000;

        ll left, right;
        // first
        ll tl, tr, sl, sr;
        sl = findleft(x, true);
        tl = findleft(x, false);

        sr = findright(sl, x, s, a);
        tr = findright(tl, x, t, b);
        
        left = min(abs(x-s[sl]), abs(x-t[tl]));
        right = min(abs(x-s[sr]), abs(x-t[tr]));

        // left
        ll l2, r2;
        if (abs(x-s[sl]) == left) {
            l2 = findleft(s[sl], false);
            r2 = findright(l2, s[sl], t, b);
            left += min(abs(s[sl]-t[l2]), abs(s[sl]-t[r2]));
        } else {
            l2 = findleft(t[tl], true);
            r2 = findright(l2, t[tl], s, a);
            left += min(abs(t[tl]-s[l2]), abs(t[tl]-s[r2]));
        }

        // left
        if (abs(x-s[sr]) == right) {
            l2 = findleft(s[sr], false);
            r2 = findright(l2, s[sr], t, b);
            right += min(abs(s[sr]-t[l2]), abs(s[sr]-t[r2]));
        } else {
            l2 = findleft(t[tr], true);
            r2 = findright(l2, t[tr], s, a);
            right += min(abs(t[tr]-s[l2]), abs(t[tr]-s[r2]));
        }

        cout << min(left, right) << endl;
    }
}


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

#define pb push_back
#define mp make_pair
#define f1 first
#define s2 second

#define fastio ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define debug(x...) cerr << "[" << #x << "]: " << x << "\n";

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pl;

ld const PI = 4*atan((ld)1);

int main()
{
	fastio;

	string s;
	cin >> s;

	cout << s;
	if (s.back() == 's') cout << "es";
	else cout << "s";
	cout << '\n';

	return 0;
}


Measured memory_bytes: 3660
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  while (n--) {
    string str;
    vector<int> vec = {0, 0, 0};
    int out = 0;
    while (cin >> str) {
      if (str == "HIT") {
        vec.push_back(1);
      }
      else if (str == "OUT") {
        ++out;
      }
      else if (str == "HOMERUN") {
        vec.push_back(1);
        for (int j = 0; j < 3; ++j)
          vec.push_back(0);
      }
      if (out == 3)
        break;
    }
    cout << accumulate(vec.begin(), vec.end() - 3, 0) << endl;
  }
}


Measured memory_bytes: 3056
from collections import defaultdict

mod = 10 ** 9 + 7

memo = defaultdict(int)


def cmb(n, r):
    if (n, r) in memo:
        return memo[(n, r)]

    if n < r or r < 0:
        return 0

    if r > n - r:
        return cmb(n, n - r)

    res = f[n] * pow(f[n - r], mod - 2, mod) * pow(f[r], mod - 2, mod) % mod
    memo[(n, r)] = res
    return res


n, k = map(int, input().split())

f = [1]
for i in range(1, 4000 + 10):
    f.append(f[-1] * i % mod)

for i in range(1, k + 1):
    print(cmb(n - k + 1, i) * cmb(k - 1, i - 1) % mod)


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

int main()
{
    int n , l;
    cin >> n >> l;
    string s[n];
    for (int i=0; i<n; i++) cin >> s[i];
    sort(s, s+n);
    for (int i=0; i<n; i++) cout << s[i];
    cout << endl;
}


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

int main()
{
	int N;
	cin >> N;
	char S[N];
	for (int i = 0; i < N; i++)
		cin >> S[i];

	bool flag = true;

	if (N % 2 == 1)
		flag = false;
	else {
		for (int i = 0; i < N/2; i++) {
			if (S[i] != S[i+N/2])
				flag = false;
		}
	}

	if (flag)
		cout << "Yes" << '\n';
	else
		cout << "No" << '\n';

	return 0;
}


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

int main() {
  int N,D,X;
  cin >> N >> D >> X;
  int sum=0;
  for(int i=0;i<N;i++){
    int a;
    cin >> a;
    sum+=1+(D-1)/a;
  }
  sum+=X;
  cout << sum;
}


Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
#define int long long
#define main signed main()
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define prec(n) fixed << setprecision(n)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
using namespace std;
using pii = pair<int, int>;
using vi = vector<int>;
using vd = vector<double>;
using vc = vector<char>;
using vb = vector<bool>;
using vs = vector<string>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvpii = vector<vpii>;
template<typename A> using fn = function<A>;
constexpr int INF = sizeof(int) == sizeof(long long) ? 1000000000000000000LL : 1000000000;
constexpr int MOD = 1000000007;
constexpr double PI = acos(-1);
template<typename A, typename B> bool cmin(A &a, const B &b) { return a > b ? (a = b, true) : false; }
template<typename A, typename B> bool cmax(A &a, const B &b) { return a < b ? (a = b, true) : false; }
constexpr bool odd(const int &n) { return n & 1; }
constexpr bool even(const int &n) { return !odd(n); }
void solve();
main { solve(); return 0; }
// clang-format on

template<typename V>
constexpr string join(const V &v, const string &sep) {
  stringstream ss;
  if (v.size()) ss << v[0];
  loop(i, 1, v.size()) ss << sep << v[i];
  return ss.str();
}

void solve() {
  vs t = {"* = ****",
          "* =* ***",
          "* =** **",
          "* =*** *",
          "* =**** ",
          " *= ****",
          " *=* ***",
          " *=** **",
          " *=*** *",
          " *=**** "};
  int n;
  vs v(8, "     ");
  vs outs;
  while (cin >> n) {
    rep(i, 5) {
      int x = n % 10;
      rep(j, 8) v[j][4 - i] = t[x][j];
      n /= 10;
    }
    ostringstream ss;
    for (auto &s : v) ss << s << endl;
    outs.pb(ss.str());
  }
  cout << join(outs, "\n");
}

Measured memory_bytes: 3400