akhauriyash/Code-Regression huggingface dataset:
s = gets
k = gets.to_i
strings = []
i = 0

("a".."z").each do |x|
  if i >= 5
    break
  end
  y = x
  if s.include?(y)
    strings[i] = y
    i += 1
    ("a".."z").each do |x1|
      if i >= 5
        break
      end
      y1 = x + x1
      if s.include?(y1)
        strings[i] = y1
        i += 1
        ("a".."z").each do |x2|
          if i >= 5
            break
          end
          y2 = y1 + x2
          if s.include?(y2)
            strings[i] = y2
            i += 1
            ("a".."z").each do |x3|
              if i >= 5
                break
              end
              y3 = y2 + x3
              if s.include?(y3)
                strings[i] = y3
                i += 1
                ("a".."z").each do |x4|
                  if i >= 5
                    break
                  end
                  y4 = y3 + x4
                  if s.include?(y4)
                    strings[i] = y4
                    i += 1
                  end
                end
              end
            end
          end
        end
      end
    end
  end
end

puts strings[k-1]


Measured memory_bytes: 3836
package main

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

type operation struct {
	a, b int
}

type byA []operation

func (a byA) Len() int           { return len(a) }
func (a byA) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
func (a byA) Less(i, j int) bool { return a[i].a < a[j].a }

func main() {
	n := getInt()
	k := getInt()

	os := make([]operation, n)
	for i := range os {
		os[i].a = getInt()
		os[i].b = getInt()
	}

	sort.Sort(byA(os))

	for i, count := 0, 0; ; {
		switch {
		case count+os[i].b < k:
			count += os[i].b
			i++
		default:
			fmt.Println(os[i].a)
			return
		}
	}
}

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

var scanner = wordScanner()

func wordScanner() *bufio.Scanner {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)
	return sc
}

func getInt() int {
	scanner.Scan()
	i, err := strconv.Atoi(scanner.Text())
	if err != nil {
		panic(err)
	}
	return i
}

func getString() string {
	scanner.Scan()
	s := scanner.Text()
	return s
}


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

int main(){
    int h, n; cin >> h >> n;
    P a[n]; rep(i, n) cin >> a[i].first >> a[i].second;

    vector<vector<int> > dp(n+1, vector<int>(h+1, 1e8));
    rep(i, n+1) dp[i][0] = 0;
    loop(i, 1, n+1)loop(j, 1, h+1){
        if(j - a[i-1].first > 0) dp[i][j] = min(dp[i-1][j], dp[i][j-a[i-1].first] + a[i-1].second);
        else dp[i][j] = min(dp[i-1][j], a[i-1].second);
    }
    cout << dp[n][h] << endl;

    return 0;
}

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

bool isPalindrome(int n) {
    string s = to_string(n),
           rs = s;
    reverse(rs.begin(), rs.end());
    return s == rs;
}

int main() {
    int A, B;
    cin >> A >> B;

    int ans = 0;
    for (int n = A; n <= B; n++) {
        if (isPalindrome(n))
            ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main() {

	char weather[7];

	scanf("%s", &weather);
	if (weather[0] == 'S') {
		printf("Cloudy");
	}else {
		if (weather[0] == 'C') {
			printf("Rainy");
		}else {
			printf("Sunny");
		}
	}
	return 0;
}

Measured memory_bytes: 128
N = int(input())
H = list(map(int, input().split()))
ans = "Yes"
for i in range(N - 1, 1, -1):
    if H[i - 1] - H[i] >= 2:
        ans = "No"
    elif H[i] < H[i - 1]:
        H[i - 1] -= 1

print(ans)

Measured memory_bytes: 63856
#include <cmath>
#include <iostream>

int main()
{
    int K, A, B;
    std::cin >> K >> A >> B;

    int i = std::ceil(double(A) / K);
    int j = std::floor(double(B) / K);

    if (i <= j)
    {
        std::cout << "OK" << std::endl;
    }
    else
    {
        std::cout << "NG" << std::endl;
    }
}


Measured memory_bytes: 3592
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a, b, temp, ans = 1;
int main()
{
	cin >> a >> b;
	temp = __gcd(a,b);
	for (ll i = 2; i * i <= temp; i++)
	{
		if (temp % i == 0)
		{
			ans++;
			while (temp % i == 0)
			{
				temp /= i;
			}
		}
	}
	if (temp > 1)ans++;
	cout << ans; 
	return 0;
} 

Measured memory_bytes: 3572
#include<bits/stdc++.h>
#include<cstring>
#include<climits>
using namespace std;
#define add(x) accumulate(x)
#define sz(x) (int)(x).size()
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define all(x) x.begin(), x.end() 
#define rep(i, a, b) for (int i=a; i<(b); i++)
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pll;
typedef vector<ll> vll;
typedef vector<pll> vpll;
const ll mod = 1000000007;
const ll INF = 1e18;
const ll MAX = 100001;
ll countCostDP(ll *A, ll n){
	ll dp[n] = {};
	dp[n-2] = abs(A[n-1] - A[n-2]);
	for(int i=n-3;i>=0;i--){
		ll j1 = abs(A[i]-A[i+1]);
		j1 += dp[i+1];
		ll j2 = abs(A[i]-A[i+2]);
		j2 += dp[i+2];
		dp[i] = min(j1, j2);
	}
	/*for(int i=0;i<n;i++){
		cout << dp[i] << " ";
	}
	cout << endl;*/
	ll ans = dp[0];
	return ans;
}
ll countCost(ll *A, ll n){
	if(n < 2){
		return 0;
	}
	else if(n == 2){
		ll ans = abs(A[0] - A[1]);
		return ans;
	}
	ll j1 = countCost(A+1, n-1);
	ll j2 = countCost(A+2, n-2);
	ll diff1 = abs(A[1] - A[0]);
	j1 += diff1;
	ll diff2 = abs(A[2] - A[0]);
	j2 += diff2;
	ll ans = min(j1,j2);
	return ans;
			
}
void solve(){
	ll n;
	cin >> n;
	ll A[n];
	for(int i=0;i<n;i++){
		cin >> A[i];
	}
	ll ans = countCostDP(A,n);
	cout << ans << endl;
	return;
}
int main(int argc, char const *argv[])
{
	/*hs;
	#ifndef ONLINE_JUDGE
    //for getting input from input.txt
    freopen("input.txt", "r", stdin);
    //for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif*/

    ll t = 1;
    while(t--){
    	solve();
    }
	return 0;
}

Measured memory_bytes: 1792
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <utility>

#define reps(i,f,n) for(int i=f; i<int(n); ++i)
#define rep(i,n) reps(i,0,n)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;

const int INF = 1000000007;

signed main()
{
    int h, w;
    cin >> h >> w;
    
    vector<string> S(h);
    rep(i, h){
        cin >> S[i];
    }
    
    int ans = 0;
    
    rep(i, w-1){
        vvi cost(h+1, vi(h+1, 0));
        
        reps(diff, -h, h+1){ // b-a
            for(int a=h-1; a>=0; --a){
                int b = a + diff;
                if(b<0 || b>=h) continue;
                cost[a][b] = cost[a+1][b+1] + (S[h-a-1][i] == S[h-b-1][i+1]);
            }
        }
        
        vvi dp(h+1, vi(h+1, INF));
        dp[0][0] = 0;
        
        rep(a, h+1){
            rep(b, h+1){
                if(a) dp[a][b] = min(dp[a][b], dp[a-1][b] + cost[a-1][b]);
                if(b) dp[a][b] = min(dp[a][b], dp[a][b-1] + cost[a][b-1]);
            }
        }
        
        ans += dp[h][h];
    }
    
    cout << ans << endl;
}


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

int main(){
    ll N;
    string S;
    cin >> N >> S;
    ll ans = 0, mx = 0;
    rep(i, 0, N){
        if(S[i]=='I') mx++;
        if(S[i]=='D') mx--;
        ans = max(mx, ans);
    }
    cout << ans << endl;
    return 0;
}

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

#define X first
#define Y second
#define ll long long
#define MP make_pair
#define PB push_back

using namespace std;

const int MAXN=2e5;

ll n;
ll vis[MAXN+5],lje[MAXN+5];
ll rj;
ll tur[(1<<19)];
ll dp[MAXN+5];
ll trn;

void update(ll cvor, ll a, ll b, ll x, ll y, ll vrj){
	
//		cout<<"\n 1 \n";
	if(b<x || a>y){
		return;
	}
	if(a>=x && b<=y){
		tur[cvor]=max(tur[cvor],vrj);
		return;
	}
	update(cvor*2,a,(a+b)/2,x,y,vrj);
	update(cvor*2+1,(a+b+1)/2,b,x,y,vrj);
}

ll nadi(ll x){
	trn=0;
	while(x>0){
		trn=max(trn,tur[x]);
		x/=2;
	}
	return trn;
}

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

	cin>>n;
	//tur[1]=n;
	for(int i=0; i<n; i++){
		cin>>vis[i];
	}
	for(int i=0; i<n; i++){
		cin>>lje[i];
	//	cout<<"\n 1 \n";
		dp[i]=nadi(vis[i]+(1<<18)-1)+lje[i];
		rj=max(rj,dp[i]);
		update(1,1,(1<<18),vis[i],(1<<18),dp[i]);
	}
	cout<<rj<<"\n";
	
	return 0;
}

Measured memory_bytes: 11416
#include<iostream>
#include <complex>

using namespace std;

int main()
{
	int a1, a2, a3;
	int res[6];
	int ans = 1000000;
	for (int i = 0; i < 6; i++)
	{
		res[i] = 0;
	}
	cin >> a1 >> a2 >> a3;

	res[0] += abs(a2 - a1);
	res[0] += abs(a3 - a2);

	res[1] += abs(a3 - a1);
	res[1] += abs(a2 - a3);

	res[2] += abs(a1 - a2);
	res[2] += abs(a3 - a1);

	res[3] += abs(a3 - a2);
	res[3] += abs(a1 - a3);

	res[4] += abs(a1 - a3);
	res[4] += abs(a2 - a1);

	res[5] += abs(a2 - a3);
	res[5] += abs(a1 - a2);

	for (int i = 0; i < 6; i++)
	{
		if (ans > res[i])
		{
			ans = res[i];
		}
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m;
    vector<int> v;
    cin >> n >> m;
    for (int i = 0; i < m;i++){
        int num;
        cin>>num;
        v.push_back(num);
    }
    int sum = 0;
    for (int i = 0; i < m;i++){
        sum += v[i];
    }
    if(sum==n)
    cout<<"0";
    else if(sum<n)
        cout << n - sum;
    else
        cout << "-1";
    return 0;
}

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

int main(){
    string s;
    cin >> s;
    if (s.at(2) == s.at(3) && s.at(4) == s.at(5)) {
        cout << "Yes" << endl;
    }
    else cout << "No" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
using ll = long long;
using P = pair<int,int>;
template <class T> void chmin(T &a, const T &b) noexcept { if (b < a) a = b; }
template <class T> void chmax(T &a, const T &b) noexcept { if (a < b) a = b; }
void debug_out() { cout << "\n"; }
template <class T, class... Args>
void debug_out(const T &x, const Args &... args) { cout << x << " "; debug_out(args...);}
#ifdef _DEBUG
  #define debug(...) debug_out(__VA_ARGS__)
#else
  #define debug(...) 
#endif

int main() {
  std::cin.tie(nullptr);
  std::ios_base::sync_with_stdio(false);
  std::cout << std::fixed << std::setprecision(15);
  int n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i,n) cin >> a[i];
  sort(all(a));
  int sum = 0;
  rep(i,k) sum += a[i];
  cout << sum << endl;
  return 0;
}

Measured memory_bytes: 3644
#include<bits/stdc++.h>
using namespace std;
int main(){
  int A,B,H,M;
  double ax, ay, bx, by, ans;
  
  cin >> A >> B >> H >> M; 
 
  double a_pi, b_pi;
  a_pi = (double(H) + double(M)/60.0)/6.0;
  b_pi = double(M)/30.0;
  
  ax = double(A) * sin(M_PI*a_pi);
  ay = double(A) * cos(M_PI*a_pi);
  bx = double(B) * sin(M_PI*b_pi);
  by = double(B) * cos(M_PI*b_pi);
  
  ans = sqrt((ax-bx)*(ax-bx) + (ay-by)*(ay-by));

  cout << setprecision(20)  << ans << endl;
}

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

#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    if(n==25){
        cout << "Christmas"<<endl;
    }
    else if(n==24){
        cout << "Christmas Eve"<<endl;
    }
    else if(n==23){
        cout << "Christmas Eve Eve"<<endl;
    }
    else{
        cout << "Christmas Eve Eve Eve"<<endl;
    }
    return 0;
}



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

#define MAX 2000001
#define VMAX 10000

int main(){
  unsigned short *A,*B;

  int C[VMAX+1];
  int n,i,j;
  scanf("%d",&n);

  A = malloc(sizeof(short)*n+1);
  B = malloc(sizeof(short)*n+1);

  for (i=0;i<=VMAX;i++) C[i]=0;
  for (i=0;i<=n;i++) B[i]=0;
  for (i=0;i<=n;i++) A[i]=0;

  for(i=0;i<n;i++){
    scanf("%hu",&A[i+1]);
    C[A[i+1]]++;

  }

for (i=1;i<=VMAX;i++) C[i]=C[i]+C[i-1];

 for(j=1;j<=n;j++){
   B[C[A[j]]]=A[j];
   C[A[j]]--;
 }

 for(i=1;i<=n;i++){
   if (i>1) printf(" ");
   printf("%d",B[i]);
 }
 printf("\n");

 return 0;
}



  



Measured memory_bytes: 9584
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> P;

bool compare_by_b(P a, P b)
{
    if (a.second != b.second)
    {
        return a.second < b.second;
    }
    else
    {
        return a.first < b.first;
    }
}

int main()
{
    int N, M;
    cin >> N >> M;
    vector<P> pairs(M);
    for (int i = 0; i < M; ++i)
    {
        int a, b;
        cin >> a >> b;
        pairs[i] = make_pair(a - 1, b - 1);
    }
    sort(pairs.begin(), pairs.end(), compare_by_b);
    int ans = 0, x = -1;
    for (int i = 0; i < M; ++i)
    {
        if (pairs[i].first > x)
        {
            x = pairs[i].second - 1;
            ++ans;
        }
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1024
H, W = list(map(int, input().split(' ')))
S = [[] for i in range(H)]
for i in range(H):
    S_temp = input()
    for s in S_temp:
        S[i].append(s)

T = [[0 for j in range(W)] for i in range(H)]
for i in range(H):
    for j, sj in enumerate(S[i]):
        if sj != '.':
            T[i][j] = sj
            continue

        count = 0
        if 0 <= i-1 and 0 <= j-1 and S[i-1][j-1] == '#':
            count += 1
        if 0 <= i-1 and S[i-1][j] == '#':
            count += 1
        if 0 <= i-1 and j+1 < W and S[i-1][j+1] == '#':
            count += 1
        if 0 <= j-1 and S[i][j-1] == '#':
            count += 1
        if j+1 < W and S[i][j+1] == '#':
            count += 1
        if i+1 < H and 0 <= j-1 and S[i+1][j-1] == '#':
            count += 1
        if i+1 < H and S[i+1][j] == '#':
            count += 1
        if i+1 < H and j+1 < W and S[i+1][j+1] == '#':
            count += 1
            
        T[i][j] = count

for i in range(H):
    for j in range(W):
        print(T[i][j], end='')
    print('')


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

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
const ll mod = 1000000007;
ll N;
ll dpZERO[1005000];
ll sumdpZERO[1005000];
int main() {
    //cout.precision(10);
    cin >> N;
    dpZERO[0] = 1;
    dpZERO[1] = 1;
    dpZERO[2] = 1;
    sumdpZERO[0] = 1;
    sumdpZERO[1] = 2;
    sumdpZERO[2] = 3;
    for(int i = 3; i <= N; i++) {
        dpZERO[i] = (sumdpZERO[i - 1] - dpZERO[i - 2] + mod) % mod;
        sumdpZERO[i] = (sumdpZERO[i - 1] + dpZERO[i]) % mod;
        //cout << i << " " << dpZERO[i] << endl;
    }
    ll ans = 0;
    for(ll i = 0; i <= N - 2; i++) {
        ll now = dpZERO[i] * (N - 1) % mod;
        now = (now * (N - 1)) % mod;
        ans = (ans + now) % mod;
        ll hoge = min(i + 2, N - 1) * dpZERO[i] % mod;
        ans = (ans + hoge) % mod;
        //cout << i << " " << ans << endl;
    }
    //cout << endl;
    ans = (ans + dpZERO[N - 1] * (N)) % mod;
    //ans = (ans + dpZERO[N]) % mod;
    cout << ans << endl;
    return 0;
}


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

int main()
{
    int d,n;
    scanf("%d%d",&d,&n);
    if(n==100)
        n++;
    printf("%d",n);
    for(int i = 0; i < d; i++)
        printf("00");
    printf("\n");
    return 0;
}


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

int r;

int main() {
  cin >> r;
  cout << r * r << endl;
  return 0;
}


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

using namespace std;

int main () {
    int H, W;
    cin>>H>>W;
    for (int i = 0; i < W+2; i++) cout<<"#";
    cout<<endl;
    
    for (int i = 0; i < H; i++) {
        cout<<"#";
        string str;
        cin>>str;
        cout<<str;
        cout<<"#"<<endl;
    }

    for (int i = 0; i < W+2; i++) cout<<"#";
    cout<<endl;
    return 0;
}

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

using namespace std;

const long long int MOD=1e9+7;

long long int modinv(long long int  a, long long int m) {
    long long int b = m, u = 1, v = 0;
    while (b) {
        long long int t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

int main() {
    long long int X, Y;
    cin >> X >> Y;
    
    if((X+Y)%3!=0) {
        cout << 0 << endl;
        return 0;
    }
    if((X+Y)/3>X || (X+Y)/3>Y) {
        cout << 0 << endl;
        return 0;
    }
    
    long long int minXY=min(X-(X+Y)/3, Y-(X+Y)/3);
    long long int ans=1;
    long long int tmpans=1;
    for(int n=1; n<=minXY; n++) {
        ans *= ((X+Y)/3+1-n);
        ans %= MOD;
        
        tmpans *= n;
        tmpans %= MOD;
    }
    
    cout << ans * modinv(tmpans, MOD) % MOD << endl;


    return 0;
    
}

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

int main(int argc, char const *argv[]) {
    int a, b, C;
    cin >> a >> b >> C;

    double S, L, h;
    S = (a * b * sin(C*PI/180))/2;
    
    double c = sqrt(a*a + b*b - 2*a*b*cos(C*PI/180));
    L = a + b + c;
    h = 2 * S / a;
    
    cout << fixed << setprecision(10) << S << ' ' << L << ' ' << h << endl;

    return 0;
}



Measured memory_bytes: 3432
X = int(input())

if X < 4:
    ans = 1
else:
    ans = 2 ** 2
    for b in range(2, X + 1):
        p = 2
        while True:
            tmp = b ** p
            if tmp <= X:
                ans = max(ans, tmp)
                p += 1
            else:
                break

print(ans)

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

#define inf 1e9+1

vector<vector<int>>dp;

string getLCS(string &s1,string &s2,int len){
        //cout<<len<<"\n";
        int i=s1.length(),j=s2.length();
        string s;
        while(len){
                //cout<<s<<", "<<len<<" "<<i<<" "<<j<<"\n";
            if(s1[i-1]==s2[j-1]){
                s = s1[i-1]+s;
                i--;
                j--;
                len--;
            }else{
                //cout<<"dpl: "<<dp[i+1][j]<<" "<<dp[i][j+1]<<"\n";
                if(dp[i-1][j]>dp[i][j-1]){
                    i--;
                }else{
                    j--;
                }
            }
        }
        return s;
}


void solve(){
    string s1,s2;cin>>s1>>s2;
    int sz1 = s1.length(),sz2 = s2.length();
    dp.resize(sz1+1,vector<int>(sz2+1,0));

    for(int i=1;i<=sz1;i++){
        for(int j=1;j<=sz2;j++){
            if(s1[i-1]==s2[j-1]){
                dp[i][j] = dp[i-1][j-1]+1;
            }else{
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    cout <<getLCS(s1,s2,dp[sz1][sz2])<<"\n";
}

int main(){



    int t=1;//cin>>t;
    while(t--){
        solve();
    }
    return 0;
}


Measured memory_bytes: 35584
#include <cstdio>
#include <set>
#define M 1000001
using namespace std;

int a[M];
int main(){
  set<int> s;
  int t,u;
  s.insert(1);
  s.insert(2);
  s.insert(3);
  s.insert(5);
  set<int>::iterator ite=s.begin();
  while((t=*ite)<M){
    if(t*2>t)s.insert(t*2);
    if(t*3>t)s.insert(t*3);
    if(t*5>t)s.insert(t*5);
    ite++;
  }
  for(ite=s.begin();*ite<M;ite++)a[*ite]=1;
  for(t=0;t<M;t++)a[t]+=a[t-1];
  for(;scanf("%d",&t),t;printf("%d\n",a[u]-a[t-1]))
    scanf("%d",&u);
}

Measured memory_bytes: 4960
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
struct xxx{int a,id;}d[100100];
long long ans[100100];
bool cmp(xxx a,xxx b){return a.a==b.a?a.id<b.id:a.a>b.a;}
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",&d[i].a),d[i].id=i;
	sort(d+1,d+n+1,cmp);int sum=0,Min=1e9+7;
	for(int i=1;i<=n;i++)
	{
		int j=i+1;
		while(j<=n&&d[j].a==d[i].a)j++;
		j--;sum+=j-i+1;Min=min(Min,d[i].id);
		ans[Min]+=(long long)(d[i].a-d[j+1].a)*(long long)sum;
		i=j;
	}
	for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
	return 0;
 } 

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

int main () {
  string a, b;
  cin >> a >> b;
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  while(a.size() < b.size()) a += "0";
  while(b.size() < a.size()) b += "0";
  reverse(a.begin(), a.end());
  reverse(b.begin(), b.end());
  if(a < b) cout << "LESS" << endl;
  if(a > b) cout << "GREATER" << endl;
  if(a == b) cout << "EQUAL" << endl;
}

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

int main() {
  int N, M;
  scanf("%d", &N);

  int sum = 0;
  vector<int> T(N, 0);
  for (int i = 0; i < N; i++) {
    scanf("%d", &T.at(i));
    sum += T.at(i);
  }

  scanf("%d", &M);
  vector<pair<int, int>> D(M, make_pair(0, 0));
  for (int i = 0; i < M; i++) {
    int P, X;
    scanf("%d%d", &P, &X);
    D.at(i) = make_pair(P - 1, X);
  }

  for (int i = 0; i < M; i++) {
    int diff = T.at(D.at(i).first) - D.at(i).second;
    printf("%d\n", sum - diff);
  }
  return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python3
def main():
    N = int(input())
    S = input()

    res = 0
    R, G, B = S.count('R'), S.count('G'), S.count('B')
    for i in range(N - 2):
        for j in range(i + 1, N - 1):
            k = j + j - i
            if k >= N:
                continue
            if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                res += 1
    print(R * G * B - res)


if __name__ == '__main__':
    main()


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

void swap(int& a ,int& b)
{
  int tmp=a;
  a=b;
  b=tmp;    
}

using namespace std;

int main()
{
   int N,i,j,num;
   int swapcnt=0;
   int min=0;
   bool needswap=0;
   vector<int> v;
   cin >> N;
   for(i=0;i<N;i++)
   {
    cin >> num;
    v.push_back(num);
   }
    
    for(i=0;i<N;i++)
    {
        min=i;
        needswap=0;
        for(j=i;j<N;j++)
        {
            if(v[j]<v[min])
            {
                min=j;
                needswap=1;
            }
        }
        if(needswap)
        {
            swap(v[i],v[min]);
            swapcnt++;
        }
    }
    for(vector<int>::iterator iter = v.begin();iter != v.end()-1; iter++)
    {
        cout<<*iter<<' ';
    }
    cout<<v[N-1]<<endl;
    cout<<swapcnt<<endl;
}


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

int main(){
  int n;
  cin >> n;
  map<string, int> cnt;
  rep(i,n){
    string s;
    cin >> s;
    cnt[s]++;
  }
  for (string s : {"AC", "WA", "TLE", "RE"}){
    cout << s << " x " << cnt[s] << endl;
  }
  return 0;
}

Measured memory_bytes: 3636
#pragma GCC optimize ("-O3")
#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// using namespace __gnu_pbds;
//#include <boost/multiprecision/cpp_int.hpp>
//using namespace boost::multiprecision;
using namespace std;

#define all(c) (c).begin(),(c).end()
#define endl "\n"
#define ff first
#define ss second
#define allr(c) (c).rbegin(),(c).rend()
#define ifr(i, begin, end) for (__typeof(end) i = (begin) - ((begin) > (end)); i != (end) - ((begin) > (end)); i += 1 - 2 * ((begin) > (end)))
#define pof pop_front
#define pob pop_back
#define pb emplace_back
#define pf emplace_front
#define fstm(m,n,r) m.reserve(n);m.max_load_factor(r)
#define mp make_pair
#define mt make_tuple
#define inf LLONG_MAX
#define os tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
//order_of_key (k) : Number of items strictly smaller than k .
//find_by_order(k) : K-th element in a set (counting from zero).
const double PI = acos(-1);
typedef complex<double> cd;
typedef long long ll;
ll gcd(){return 0ll;} template<typename T,typename... Args> T gcd(T a,Args... args) { return __gcd(a,(__typeof(a))gcd(args...)); }
typedef map<ll,ll> mll;
typedef map<string,ll> msll;
typedef unordered_map<ll,ll> umap;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef long double ld;
#define mod 1000000007 
#define N 100001

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
    #endif
    // int T;cin>>T;while(T--) 
    {
        ll a, b, c, d;
        cin>>a>>b>>c;
        ll ans = b/c;
        ans-=((a-1)/c);
        cout<<ans<<endl;
    }
    return 0;
}

Measured memory_bytes: 3580
import java.util.Scanner;
 
public class Main{
 
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  String a = sc.next();
  String b = sc.next();
  
 
  if ( a.equals("H") && b.equals("H")) 
   System.out.println("H");
  if ( a.equals("H") && b.equals("D")) 
   System.out.println("D");
  if ( a.equals("D") && b.equals("H"))
   System.out.println("D");
  if ( a.equals("D") && b.equals("D")) 
   System.out.println("H");
 
 }
 
}

Measured memory_bytes: 23124
N, M, X = map(int, input().split())
CA = [tuple(map(int, input().split())) for _ in range(N)]

ans = None
for bit in range(1 << N):
    atotals = [0] * M
    ctotal = 0
    for i in range(N):
        if bit & (1 << i):
            ca = CA[i]
            for j, a in enumerate(ca[1:]):
                atotals[j] += a
            ctotal += ca[0]

    if all(map(lambda atotal: atotal >= X, atotals)):
        if ans is None:
            ans = ctotal
        else:
            ans = min(ans, ctotal)
if ans is None:
    print(-1)
else:
    print(ans)

Measured memory_bytes: 9192
def main():
    INF = 10 ** 6
    H, W = list(map(int, input().split(' ')))
    A = [input() for _ in range(H)]
    d = [[INF for _ in range(W)] for _ in range(H)]
    # 距離テーブルの初期化
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                d[h][w] = 0
    # 黒マスまでの横方向の最短距離を出す
    for h in range(H):
        # 左から右方向へ探索
        for w in range(1, W):
            d[h][w] = min(d[h][w], 1 + d[h][w - 1])
        # 逆方向
        for w in range(W - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h][w + 1])
    # 縦方向も同様に探索
    for w in range(W):
        for h in range(1, H):
            d[h][w] = min(d[h][w], 1 + d[h - 1][w])
        for h in range(H - 2, -1, -1):
            d[h][w] = min(d[h][w], 1 + d[h + 1][w])
    # 黒マスまでの最長距離が答え
    ans = 0
    for h in range(H):
        for w in range(W):
            ans = max(ans, d[h][w])
    print(ans)


if __name__ == '__main__':
    main()

Measured memory_bytes: 84140
#include<iostream>
using namespace std;
const int N=2e5+5;
int a[N];
int main()
{
	int n,i,max1=0,max2=0,p;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>a[i];
		if(a[i]>max1){
			max1=a[i];
			p=i;
		}
	}
	
	for(i=1;i<=n;i++)
		if(i!=p && a[i]>max2)
			max2=a[i];
	
	for(i=1;i<=n;i++)
		if(i!=p)
			cout<<max1<<endl;
		else
			cout<<max2<<endl;
	return 0;
}

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

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

    int N; cin >> N;
    string s; cin >> s;
    int Q; cin >> Q;

    unordered_map<char, set<int>> mci;
    for (int i = 0; i < (int)s.size(); ++i) mci[s[i]].insert(i);

    for (int i = 0; i < Q; ++i) {
        int q; cin >> q;
        if (q == 1) {
            int iq; char c;
            cin >> iq >> c; --iq;
            mci[s[iq]].erase(iq);
            mci[c].insert(iq);
            s[iq] = c;
        } else {
            int lq, rq;
            cin >> lq >> rq; --lq, --rq;
            int ans = 0;
            for (char c = 'a'; c <= 'z'; ++c) {
                auto it = mci[c].lower_bound(lq);
                if (it != mci[c].end() && *it <= rq) ++ans;
            }
            cout << ans << '\n';
        }
        //cout << "s=" << s << '\n';
    }
}


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

int main()
{
	int n;
	cin >> n;
	map<int, int> mp;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		if (mp.count(a)) mp[a]++;
		else mp[a] = 1;
	}

	int ans = 0;
	for (const auto& item : mp) {
		if (item.first <= item.second) ans += item.second - item.first;
		else ans += item.second;
	}
	cout << ans << endl;
}


Measured memory_bytes: 4736
#include <iostream>

using namespace std;

int main()
{
    long a,b,v,w,t;
    cin>>a>>v>>b>>w>>t;
    if(a+(v*t)==b+(w*t)){
        cout<<"YES";
    }
    else if(a-(v*t)==b-(w*t)){
        cout<<"YES";
    }
    else if(a<b){
        if(a+(v*t)>b+(w*t)){
            cout<<"YES";
        }
        else{
            cout<<"NO";
        }
    }
    else if(a>b){
        if(a-(v*t)<b-(w*t)){
            cout<<"YES";
        }
        else{
            cout<<"NO";
        }
    }

    return 0;
}


Measured memory_bytes: 3636
import java.util.*;
import java.io.*;

class Main
{

	

	private static boolean exhaustiveSearch(int[] a, boolean[] memo, int currentIndex, int sum) {

		memo[sum] = true;

		if (currentIndex >= a.length) 
			return false;

		return exhaustiveSearch(a, memo, currentIndex + 1, sum) || exhaustiveSearch(a, memo, currentIndex + 1, sum + a[currentIndex]);

	}


	public static void main(String[] args) {
		try(Scanner reader = new Scanner(new InputStreamReader(System.in)))
		{

			boolean[] memo = new boolean[2001];
			for (int i = 0; i < memo.length; i++) 
				memo[i] = false;

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

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

			Main.exhaustiveSearch(a, memo, 0, 0);

			reader.nextLine();
			
			int q = reader.nextInt();

			for (int i = 0; i < q; i++) 
				System.out.println(memo[reader.nextInt()] ? "yes" : "no");
			


		}catch (Exception e) {
			e.printStackTrace();
		}
		
	}
}

Measured memory_bytes: 26752
#include <bits/stdc++.h>
using namespace std;
using lint = long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T> void assign(V<T>& v, int n, const T& a = T()) { v.assign(n, a); }
template<class T, class... U> void assign(V<T>& v, int n, const U&... u) { v.resize(n); for (auto&& i : v) assign(i, u...); }

struct M {
  using T = lint;
  static T op(const T& a, const T& b) { return max(a, b); }
  static constexpr T e() { return numeric_limits<T>::min(); }
};

template<class M> struct ST {
  using T = typename M::T;
  int n;
  V<T> t;

  ST(int n) : n(n) {
    t.assign(2 * n, M::e());
  }

  void build() {
    for (int i = n - 1; i; i--) t[i] = M::op(t[2 * i], t[2 * i + 1]);
  }

  T get(int l, int r) {
    T resl = M::e(), resr = M::e();
    for (l += n, r += n; l < r; l >>= 1, r >>= 1) { 
      if (l & 1) resl = M::op(resl, t[l++]); 
      if (r & 1) resr = M::op(t[--r], resr);
    }
    return M::op(resl, resr);
  }

  void set(int i, const T& a) {
    for (t[i += n] = a; i >>= 1;) t[i] = M::op(t[2 * i], t[2 * i + 1]);
  }
};

int main() {
  cin.tie(NULL); ios::sync_with_stdio(false);
  int n, m, k; cin >> n >> m >> k;
  V<lint> a(n); for (int i = 0; i < n; i++) cin >> a[i];
  VV<lint> dp; assign(dp, 2, n + 1);
  for (int i = 1; i < k + 1; i++) {
    ST<M> st(n + 1);
    for (int j = 0; j < n + 1; j++) st.t[j + n + 1] = dp[i - 1 & 1][j];
    st.build();
    for (int j = i; j < n + 1; j++) {
      dp[i & 1][j] = i * a[j - 1] + st.get(max(j - m, 0), j);
    }
  }
  cout << *max_element(dp[k & 1].begin(), dp[k & 1].end()) << '\n';
}

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

using namespace std;

const int maxn = 1e5 + 5;
const long long mod = 998244353;

long long d[maxn], vf[maxn], fact[maxn];

long long x, y;

void invmod(long long a, long long n, long long &x, long long &y) {
	if (n == 0) {
		x = 1, y = 0;
		return;
	}
	long long x1, y1;
	invmod(n, a % n, x1, y1);
	x = y1;
	y = x1 - (a / n) * y1;
}

long long findinv(long long nr)  {
    invmod(nr, mod, x, y);
    x %= mod;
    while(x < 0)
        x += mod;
    return x;
}

long long put(long long a, long long n)  {
    long long ans = 1LL;
    while(n)  {
        if(n % 2)  {
            ans *= a;
            ans %= mod;
        }
        a *= a;
        a %= mod;
        n /= 2;
    }
    return ans;
}

int main()  {
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
        cin >> d[i], vf[d[i]]++;
    if(d[1] != 0 or vf[0] > 1)  {
        cout << "0";
        return 0;
    }
    fact[1] = 1;
    fact[0] = 1;
    for(int i = 2;i <= n;i++)
        fact[i] = fact[i - 1] * i, fact[i] %= mod;
    long long ans = 1LL;
    int ram = n - 1;
    vf[0] = 1;
    for(int i = 1;i <= n;i++)  {
        ram -= vf[i];
        if(ram > 0 && vf[i] == 0)  {
            cout << "0";
            return 0;
        }
        ans *= put(vf[i - 1], vf[i]);
        ans %= mod;
    }
    cout << ans;
	return 0;
}


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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n, q = LI()
ans = (n-2) * (n-2)
min_x_list = [-n]
min_x_idx = [0]
min_y_list = [-n]
min_y_idx = [0]
idx = 1
for _ in range(q):
    a, b = LI()
    min_x = -min_x_list[-1]
    min_y = -min_y_list[-1]
    if a == 1:
        if min_x > b:
            min_x_list.append(-b)
            min_x_idx.append(idx)
            idx += 1
            ans -= min_y - 2
        else:
            r = br(min_x_list, -b)
            i = min_x_idx[r]
            r = br(min_y_idx, i)
            ans -= -min_y_list[r-1] - 2

    elif a == 2:
        if min_y > b:
            min_y_list.append(-b)
            min_y_idx.append(idx)
            idx += 1
            ans -= min_x - 2
        else:
            r = br(min_y_list, -b)
            i = min_y_idx[r]
            r = br(min_x_idx, i)
            ans -= -min_x_list[r-1] - 2
print(ans)


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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

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



signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  
  ll n; cin>>n;
  ll ans=1000-n%1000;
  if(ans==1000) ans=0;
  cout<<ans<<endl;
  
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }


lli dp[5100][5100];

void func(long long N, std::string S){

    lli ans = 0;
    for(lli i=N-1;i>=0;i--){
        for(lli j = N-1;j>i;j--){
            if((S[i]==S[j])){
                chmax(dp[i][j],dp[i+1][j+1]+1);
            }
        }
    }

    REP(i,0,N)REP(j,0,N){
        chmax(ans,min(dp[i][j],(lli)abs(i-j)));
    }

    cout<<ans<<endl;


}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    std::string S;
    std::cin >> S;
    func(N, S);
    return 0;
}


Measured memory_bytes: 200960
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/



int main() {
int K,S;
cin>>K>>S;
ll count=0;
rep(i,K+1){
  rep(j,K+1){
    if((i+j<=S)&&(S-i-j<=K)){
      count++;
    }

  }
}
cout<<count<<endl;
return 0;
}




Measured memory_bytes: 256
#include<bits/stdc++.h>
#define MOD 1000000007
using namespace std;
 
int prm[10000], ins[10000], n, m;
long long f1[100100], f2[100100];

int setp(int k){
  int p = 0;
  bool isp[k+1];
  for(int i = 0; i <= k; i++) isp[i] = true;
  isp[0] = isp[1] = false;
  for(int i = 2; i <= k; i++){
    if(isp[i]){
      prm[p++] = i;
      for(int j = 2*i; j <= k; j += i) isp[j] = false;
    }
  }
  return p;
}

void setf(int k){
  f1[1] = 1;
  for(int i = 1; i <= k; i++) f1[i+1] = f1[i]*(i+1) % MOD;
  long long y = f1[k+1]; f2[k+1] = 1;
  for(int i = MOD-2; i; i/=2){
    if(i&1) f2[k+1] = f2[k+1] * y % MOD;
    y = y*y % MOD;
  }
  for(int i = k; i >= 0; i--) f2[i] = f2[i+1]*(i+1)%MOD;
}

int main(){
  int r = 0, k, p;
  long long ans = 1;
  scanf("%d%d", &n, &m);
  k = sqrt(1.0*m);
  p = setp(k);
  setf(n+50);
  for(int i = 0; i < p && m != 1; i++){
    int j;
    for(j = 0; m % prm[i] == 0; j++, m/=prm[i]);
    if(j) ins[r++] = j;
  }
  if(m-1) ins[r++] = 1;
  for(int i = 0; i < r; i++)
    ans = ans*f1[n-1+ins[i]]%MOD*f2[n-1]%MOD*f2[ins[i]]%MOD;
  printf("%lld\n", ans);
}

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

int main() {
    int N, X;
    cin >> N >> X;

    vector<int> m(N);
    int m_min = 1e9;
    for (int i = 0; i < N; ++i) {
        cin >> m[i];
        X -= m[i];
        if (m_min > m[i]) {
            m_min = m[i];
        }
    }
    cout << X / m_min + N << endl;
    return 0;
}


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

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define vi vector<ll>
#define sll(x) scanf("%lld",&x)
#define prll(x) printf("%lld ",x)
#define pri(x) printf("%d ",x)
#define si(x) scanf("%d",&x)
#define el printf("\n")
#define pb push_back
#define f first
#define s second
#define arrondi(a) (long long)floor(a+0.5);
#define NIL -1
ll N=500005;
ll MAX=9223372036854775807;
ll MOD=1000000007;
long double PI =4*atan(1);

int main()
{
	IOS;
    cout.precision(30);
    int n,l; cin >> n >> l; ll ans=0,s=0;
    for (int i=1;i<=n;i++)
    {
        s+=l+i-1;
    }
    ll diff=100000000,rep=0;
    for (ll i=1;i<=n;i++)
    {
        ans=0;
        for (ll j=1;j<=n;j++)
        {
            if (i!=j)
            {
                ans+=l+j-1;
            }
        }
        if (abs(ans-s)<diff)
        {
            rep=ans;
            diff=abs(ans-s);
        }
    }
    cout << rep;
    return 0;
}


Measured memory_bytes: 256
import bisect
from collections import deque

n = int(input())
l = deque([int(input())])

for i in range(1, n):
  a = int(input())
  p = bisect.bisect_left(l,a)
  if p == 0:
    l.appendleft(a)
  else:
    l[p-1] = a

print(len(l))

Measured memory_bytes: 7284
n,m = map(int,input().split())
can = []
for _ in range(n):
  can.append(list(map(int,input().split())))
can.sort()
pool = []
import heapq
here = 0
ans = 0
for i in range(1,m+1):
  while can[here][0] == i:
    heapq.heappush(pool,-can[here][1])
    here += 1
    if here == n:
      here -= 1
      break
  if pool != []:
    ans += heapq.heappop(pool)
print(-ans)

Measured memory_bytes: 31968
N = gets.to_i

words = []
ok = true
N.times do |i|
  word = gets.chomp
  ok = false if i > 0 && (words.include?(word) || word[0] != words[i-1][-1])
  words << word
end

if ok
  puts 'Yes'
else
  puts 'No'
end

Measured memory_bytes: 1788
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i,n) for(long long i = 0; i < (n); ++i)
#define ll long long
#define P pair<ll,ll>
#define all(v) (v).begin(),(v).end()

const ll mod = 1e9+7;
const ll INF = 1e18;
const double pi = acos(-1.0);

int main(void)
{
    ll n,a,b;
    string s;
    cin>>n>>a>>b>>s;
    ll ta=0,tb=0;
    rep(i,n){
        if(s[i]=='a' && ta+tb<a+b){
            cout<<"Yes"<<endl;
            ta++;
        }else if(s[i]=='b' && ta+tb<a+b && tb<b){
            cout<<"Yes"<<endl;
            tb++;
        }else cout<<"No"<<endl; 
    }
    return 0;
}

Measured memory_bytes: 3696
#include <bits/stdc++.h>
using namespace std;
const int N = 200005;
typedef long long LL;
int n,a[N],l,r;
LL ans,asum,xsum;
int main() {
	scanf("%d",&n);
	for(int i=0; i<n; i++) scanf("%d",&a[i]);
	l=r=asum=xsum=0;
	while(r<=n) {
	//	cout << l << ' ' << r << endl;
	//	cout << asum << ' ' << xsum << endl;
		if(asum==xsum) {
			ans+=r-l;
			asum+=a[r];
			xsum^=a[r++];
		} else {
			asum-=a[l];
			xsum^=a[l++];
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 1152
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <random>
#include <chrono>
#include <tuple>
#include <random>
#include <cmath>

using namespace std;

typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

const ll SIZE = 1e6 * 2 + 10, INF = 1e9 * 1e7 + 10, MOD = 1e9 + 7;

ll dp[SIZE][2][2];

int main()
{
    fastInp;

    
    ll n;
    cin >> n;
    vector<ll> vec1(n), vec2(n);

    map<ll, ll> mp1, mp2;
    for (auto &cur : vec1) cin >> cur;
    for (auto &cur : vec2) cin >> cur;

    for (auto cur : vec1) {
        mp1[cur]++;
    }

    for (auto cur : vec2) {
        mp2[cur]++;
    }

    ll sh = 0;

pair<ll, ll> mn2 = {-INF, INF};
    for (auto cur : mp1) {
        ll am = cur.second, vl = cur.first;
mn2.first = max(mn2.first, am);
        mn2.second = min(mn2.second, am);
        if (am > n - mp2[vl]) {
            cout << "No";
            return 0;
        }
    }

    pair<ll, ll> mn = {-INF, INF};
    for (auto cur : mp2) {
        ll am = cur.second, vl = cur.first;
        mn.first = max(mn.first, am);
        mn.second = min(mn.second, am);
        if (am > n - mp1[vl]) {
            cout << "No";
            return 0;
        }
    }

    cout << "Yes\n";
    bool fl = true;
    for (int i = 0; i < vec2.size(); i++) {
        if (vec2[(i + n / 2) % n] == vec1[i]) fl = false;
    }

    if (fl) {
        for (int i = 0; i < vec2.size(); i++) {
            cout << vec2[(i + n / 2) % n] << " ";
        }
        return 0;
    } else {
        vector<ll> check;
        for (int i = 0; i < n; i++) check.push_back(i);
        std::random_device rd;
        std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
        shuffle(check.begin(), check.end(), rng);
        check.insert(check.begin(), mn.first);
        check.insert(check.begin(), mn.second);
        check.insert(check.begin(), mn2.first);
        check.insert(check.begin(), mn2.second);
        for (int k = 0; k < n; k++) {
            bool fl = true;
            for (int i = 0; i < vec2.size(); i++) {
                if (vec2[(i + check[k]) % n] == vec1[i]) fl = false;
            }

            if (fl) {
                for (int i = 0; i < vec2.size(); i++) {
                    cout << vec2[(i + check[k]) % n] << " ";
                }
                return 0;
            }
        }
    }

    return 0;
}

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

using namespace std;

int main() {
	int tmp, N, ans = 0;
	vector<int> L;
	cin >> N;
	for(int i=0;i<2*N;i++) {
		cin >> tmp;
		L.push_back(tmp);
	}
	sort(L.begin(), L.end());
	for(int i=0;i<2*N;i+=2) {
		ans += L[i];
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define all(v) ((v).begin()),((v).end())
#define ll long long
#define fastIO cout << fixed << setprecision(12), ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
double const EPS = 1e-12, PI = acos(-1);
const int N = 3e5 + 9, M = 5e3 + 9, OO = 1e9 + 7, MOD = 1e9 + 7;
const ll inf = 1e18;

vector<ll> freq[26];

int main() {
  fastIO;
#ifdef LOCAL
  freopen("input.in", "rt", stdin);
#endif
  string str1, str2;
  cin >> str1 >> str2;
  for (int i = 0; i < (int)str1.size(); ++i) {
//    char me = str1[i];
    freq[str1[i] - 'a'].push_back(i);
  }
  ll prv = 0;
  ll ans = 0;
  int n = str1.size();
  for (int i = 0; i < (int)str2.size(); ++i) {
    int me = str2[i] - 'a';
    if(freq[me].size() == 0) {
      cout << -1;
      return 0;
    }
  }
  for (int i = 0; i < (int)str2.size(); ++i) {
    int me = str2[i] - 'a';
    int it = lower_bound(freq[me].begin(), freq[me].end(), prv) - freq[me].begin();
    if(it == (int)freq[me].size()) {
//      if(freq[me].size() == 0) {
//        cout << -1;
//        return 0;
//      }
      ll ana = freq[me][0] + 1;
      ans += (n - prv);
      ans += ana;
      prv = ana;
    } else {
      ans += (freq[me][it]  - prv + 1);
      prv = freq[me][it] + 1;
    }
  }
  cout << ans;
  return 0;
}


Measured memory_bytes: 1736
#include <bits/stdc++.h>
 
using namespace std;
 
int main()
{
  int a[7]={1,2,4,8,16,32,64};
   int n;
  cin>>n;
  int i;
  for(i=0;i<7;++i)
  {
    if(a[i]>n)
        break;
  }
  
  printf("%d",a[i-1]);
     
 
    
}

Measured memory_bytes: 256