akhauriyash/Code-Regression huggingface dataset:
Scanf.scanf "%d" (fun n ->
    let a = Array.init (n + 1) (fun _ -> Scanf.scanf " %d" (fun a -> a)) in
    let hist = Array.make (n + 1) (-1) in
    let rec loop i =
        let q = a.(i) in
        if hist.(q) = -1 then (
            hist.(q) <- i;
            loop (i + 1)
        ) else
            i - hist.(q)
    in
    let dif = loop 0 in

    let extgcd x y =
        let rec eg r0 r1 a0 a1 b0 b1 =
            if r1 = 0 then a0 else
                let q1 = r0 / r1 in
                eg r1 (r0 mod r1) a1 (a0 - q1 * a1) b1 (b0 - q1 * b1)
        in
        eg x y 1 0 0 1
    in
    let inv x y = (* 1/x in mod y *)
        let c = extgcd x y in
        if c < 0 then c + y else c
    in

    let z = 1000000007 in
    let ( -@) a b = (((a - b) mod z) + z) mod z in
    let ( *@) a b = (a * b) mod z in
    let ( /@) a b = a *@ inv b z in

    let rec loop i a b acc1 c d acc2 =
        if i <= n + 1 then (
            let acc1 = acc1 *@ a /@ b in
            Printf.printf "%d\n" (acc1 -@ acc2);
            let acc2 = acc2 *@ c /@ d in
            loop (i + 1) (a - 1) (b + 1) acc1 (c - 1) (d + 1) acc2
        )
    in
    loop 1 (n + 1) 1 1 (n - dif) 1 1
)

Measured memory_bytes: 7532
import java.util.*;
import java.util.stream.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int mod = (int)1e9 + 7;
        String a = sc.next();
        if (a.equals("Sunny")) {
            System.out.println("Cloudy");
        } else if (a.equals("Cloudy")) {
            System.out.println("Rainy");
        } else {
            System.out.println("Sunny");
        }
    }

}


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

int asc(const void *a, const void *b) {
  return *(int *)a - *(int *)b;
}

int main() {
	int n;
	bool ans = true;
	cin >> n;
	string a;
	vector<string> s(n);
	char b;
	rep(i, n){
		cin >> a;
		if(i != 0){
			if(a[0] != b){
				ans = false;
			}
		}
		s[i] = a;
		b = a[a.size()-1];
	}
	if(ans != false){
		for(int i = 0; i < n; i++){
			for(int j = i+1; j < n; j++){
				if(s[i] == s[j]){
					cout << "No" << endl;
					return 0;
				}
			}
		}
	}else{
		cout << "No" << endl;
		return 0;
	}
	cout << "Yes" << endl;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,a) FOR(i,0,a)
typedef long long ll;

using namespace std;

int main()
{
    double a, b;
    cin >> a >> b;
    cout << (int)ceil((a + b) / 2) << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int num;
	string s;
	cin >> num >> s;
	if(num >= 3200){
		cout << s;
	}else{
		cout << "red";
	}
}

Measured memory_bytes: 256
#include<stdio.h>

#define MAX 100000


int p(int i) {
  return i/2;
}

int l(int i){
  return 2*i;
}

int r(int i){
  return 2*i+1;
}




int main(){
  int T,i,b,arry[MAX+1];
  int w,e,o;
 
  
  scanf("%d",&T);

  for(i=1;i<=T;i++){
    scanf("%d",&arry[i]);
  }

  for(i=1;i<=T;i++){
    printf("node %d: key = %d, ",i,arry[i]);
    if(p(i)>=1) printf("parent key = %d, ",arry[w=p(i)]);
    if(l(i)<=T) printf("left key = %d, ",arry[e=l(i)]);
    if(r(i)<=T) printf("right key = %d, ",arry[o=r(i)]);
    printf("\n");
  }

  return 0;
}
                  



Measured memory_bytes: 2056
#include <iostream>
#include <vector>
#include <numeric>

using namespace std;
using ull = unsigned long long;

int main(int argc, const char *argv[])
{
  int size;
  cin >> size;
  vector<int> a(size);
  vector<int> cnts(size + 1, 0);
  for (auto &n : a) {
    cin >> n;
    cnts[n]++;
  }

  ull sum = accumulate(cnts.begin(), cnts.end(), 0ull,
      [] (ull acc, ull n) { return acc + n * (n - 1) / 2; });
  for (auto n : a) {
    cout << sum - cnts[n] + 1 << "\n";
  }

  return 0;
}


Measured memory_bytes: 4096
A , B , M = map(int , input().strip().split())
a = list(map(int , input().strip().split()))
b = list(map(int , input().strip().split()))
ans = min(a) + min(b)

for i in range(M):
  x , y , c = map(int,input().strip().split())
  ans = min(a[x - 1] + b[y - 1] - c , ans) 

print(ans)

Measured memory_bytes: 18612
#pragma GCC target("avx")
#include <cstdio>

using namespace std;

using int64 = long long;

class Combination {
 public:
  constexpr Combination() { Build(); }
  static constexpr int mod_ = 1000000007;
  static constexpr int n_ = 800000;
  class LookupTable {
   public:
    int64 factorial_[n_];
    int64 inverse_[n_];
    int64 finverse_[n_];
  };
  LookupTable lt{};
  // return nCk
  constexpr int64 Get(int n, int k) const noexcept {
    if (n < k || n < 0 || k < 0) return 0;
    return lt.factorial_[n] * (lt.finverse_[k] * lt.finverse_[n - k] % mod_) %
           mod_;
  }

 private:
  constexpr void Build() noexcept {
    lt.factorial_[0] = 1;
    lt.factorial_[1] = 1;
    lt.finverse_[0] = 1;
    lt.finverse_[1] = 1;
    lt.inverse_[1] = 1;
    for (int i = 2; i < n_; ++i) {
      lt.factorial_[i] = lt.factorial_[i - 1] * i % mod_;
      lt.inverse_[i] = mod_ - lt.inverse_[mod_ % i] * (mod_ / i) % mod_;
      lt.finverse_[i] = lt.finverse_[i - 1] * lt.inverse_[i] % mod_;
    }
  }
};

template<typename T> void fastin(T& num) {
  T c;
  num = 0;
  c = getchar_unlocked();
  for (; (c > 47 && c < 58); c = getchar_unlocked()) num = (num << 3) + (num << 1) + c - 48;
}

Combination com;

int main() {
  int x, y; fastin(x); fastin(y);
 
  if ((x + y) % 3 != 0) {
    printf("%d\n", 0);
    return 0;
  }
 
  int nn = (x + y) / 3;
  int r = x - nn;
 
  int64 ans = com.Get(nn, r);
  printf("%lld\n", ans);

  return 0;
}


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

int main(){
  int N,K;
  cin>>N>>K;
  int elm[N];
  int min=0;
//ループ：elmの各要素の読取りと最小値の抽出。
  for(int i=0;i<N;i++){
    cin>>elm[i];
    if(i==0){
      min=elm[i];
    }else if(min>elm[i]){
      min=elm[i];
    }
  }
int kaisu=1;
int def=K;
 while(def<N){
    def+=(K-1);
    kaisu+=1;
  }
  cout<<kaisu<<endl;
}


Measured memory_bytes: 640
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author G. Guarnieri
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        Scanner in = new Scanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        public void solve(int testNumber, Scanner in, PrintWriter out) {
        /*
        Rating 1-399 : gray
        Rating 400-799 : brown
        Rating 800-1199 : green
        Rating 1200-1599 : cyan
        Rating 1600-1999 : blue
        Rating 2000-2399 : yellow
        Rating 2400-2799 : orange
        Rating 2800-3199 : red
         */
            Set<Integer> colors = new HashSet<>();
            int n = in.nextInt();
            int choosers = 0;
            for (int i = 0; i < n; i++) {
                int current = getColor(in.nextInt());
                if (current < 0) {
                    ++choosers;
                }
                else {
                    colors.add(current);
                }
            }
            out.printf("%d %d\n",
                       Math.max(colors.size(), 1),
                       colors.size() + choosers);
        }

        private int getColor(int score) {
            if (score < 400) {
                return 0;
            }
            else if (score < 800) {
                return 1;
            }
            else if (score < 1200) {
                return 2;
            }
            else if (score < 1600) {
                return 3;
            }
            else if (score < 2000) {
                return 4;
            }
            else if (score < 2400) {
                return 5;
            }
            else if (score < 2800) {
                return 6;
            }
            else if (score < 3200) {
                return 7;
            }
            else {
                return -1;
            }

        }

    }
}



Measured memory_bytes: 21844
#include<bits/stdc++.h>
using namespace std;
typedef long ll;
//#define max(x,y) ((x<y)?y:x)
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll n,m,k,l;
    cin>>n>>m>>k;
    ll a[200005]={0},b[200005]={0};
    a[0]=0,b[0]=0;
    for(int i=1;i<=n;i++)
    {
        
        cin>>l;
        a[i]=a[i-1]+l;
    }
    for(int i=1;i<=m;i++)
    {
        
        cin>>l;
        b[i]=b[i-1]+l;
    }
    ll j=0,x=m,mx=0;
    for( j=0;j<=n;j++)
    {
        
        while(b[x]+a[j]>k) x--;
        mx=max(mx,j+x);
       // cout<<mx<<endl;
    }
    cout<<mx<<endl;
    return 0;
} 

Measured memory_bytes: 6784
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include <iostream>
#include<string.h>     
#include<algorithm>
#define ll long long
#define hengheng main ()

using namespace std;
int hengheng
{
	ll a[10];
	ll b,c; ll t;
	while(scanf("%lld%lld%lld",&a[1],&a[2],&a[3])!=EOF)
	{
		sort(a+1,a+4);
		printf("%lld\n",a[1]*a[2]/2);
		
	}
	
	return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include<cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <deque>
#include <algorithm>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#include <iterator>
#include<iomanip>

using namespace std;

#define rep(i,a,b) for(int i=(a), i##_len=(b);i<i##_len;i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)

#define int ll
#define SZ(x) ((int)(x).size())
#define pb push_back
#define mp make_pair

typedef long long ll;
//typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<ll, int> pli;
typedef pair<double, double> pdd;
typedef vector<vector<int>> mat;
//typedef unsigned int uint;

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

const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)1e9 + 7;
const double EPS = 1e-9;

int dp[100010];
int N, W;
int w[110], v[110];

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

	cin >> N >> W;
	rep(i, 0, N)cin >> w[i] >> v[i];

	rep(i, 0, 100010)dp[i] = INF;
	dp[0] = 0;

	rep(i, 0, N)
	{
		rrep(j, 0, 100001)
		{
			if (dp[j] != INF)
			{
				chmin(dp[j + v[i]], dp[j] + w[i]);
			}
		}
	}

	int ans = -1;
	rep(i, 0, 100010)
	{
		if (dp[i] <= W)
		{
			chmax(ans, i);
		}
	}
	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 1024
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace contest_Csharp
{

    class Program
    {
        public static (long m, long s)[,] dp;
        public static long mod;
        
        public static List<int> getprimes(int n)
        {
            var result = new List<int>();
            result.Add(2);
            int i = 3;
            while (result.Last() <= n)
            {
                var flg = true;
                foreach(var p in result)
                {
                    if (i % p == 0)
                    {
                        flg = false;
                    } 
                }
                if (flg)
                    result.Add(i);
                i = i + 2;
            }
            return result;
        }
        static void Main(string[] args)
        {
            checked
            {
                var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
                Console.SetOut(sw);

                var vals = Console.ReadLine().Split(' ').
                    Select(x => long.Parse(x)).ToList();


                var a = vals[0];
                var b = vals[1];
                var c = vals[2];
                var d = vals[3];

                long[] A = { a * c, a * d, b * c, b * d };

                var ans = A.Max();
                
                Console.WriteLine(ans);

                Console.Out.Flush();
            }//cheked




        }
        static long gcd(long a, long b)
        {
            long large = Math.Max(a, b);
            long small = Math.Min(a, b);
            while (large % small != 0)
            {
                var S = small;
                small = large % small;
                large = S;
            }
            return small;
        }
    }

}




Measured memory_bytes: 28284
#写経
#https://atcoder.jp/contests/abc167/submissions/13218188

MAX = 100000000000
def resolve():
    N,M,X = map(int,input().split())
    A,C = [],[]
    for _ in range(N):
        c_a = list(map(int, input().split()))
        c = c_a.pop(0)
        A.append(c_a)
        C.append(c)
    
    def func(cost,a,i):
        if min(a) >= X:
            return cost
        elif i == N:
            return MAX
        total_A = [x+y for (x,y) in zip(a,A[i])]
        
        return min(func(cost + C[i],total_A,i+1),func(cost,a,i+1))

    ans = func(0,[0]*M,0) 
    if ans == MAX:
        print(-1)
    else:
        print(ans)
resolve()

Measured memory_bytes: 9256
def rank(x):
  if  400<=x<600:
    return 8
  elif  600<=x<800:
    return 7
  elif  800<=x<1000:
    return 6
  elif  1000<=x<1200:
    return 5
  elif  1000<=x<1400:
    return 4
  elif  1400<=x<1600:
    return 3
  elif  1600<=x<1800:
    return 2
  elif  1800<=x<2000:
    return 1

X=int(input())
print(rank(X))

Measured memory_bytes: 9184
#include<stdio.h>
#define N 2000000
int A[N],B[N],C[N];
int main(){
  int i,j,k=0,n;
   
   
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
    C[A[i]]++;
     
    if(k<A[i])k=A[i];
  }
  for(i=1;i<=k;i++){
    C[i]+=C[i-1];
  }
 
  for(i=0;i<n;i++){
    B[C[A[i]]-1]=A[i];
    C[A[i]]--;
  }
  for(i=0;i<n;i++){
    if(i!=n-1)
      printf("%d ",B[i]);
    else printf("%d\n",B[i]);
     
  }
   
   
  return 0;
}

 

Measured memory_bytes: 17892
#include <stdio.h>
int main(){
  int N;
  scanf("%d",&N);
  
  int hun,ten,one;
  hun=N/100;
  ten=(N-hun*100)/10;
  one=(N-hun*100-ten*10);
  
  if(hun==7 || ten==7 || one==7){
    printf("Yes\n");
  }	else{
    printf("No\n");
  }
  
  return 0;
}

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

using namespace std;

const int N = 2e5 + 10;

int a[N];
long long cnt[N];

int main() {
  int n;
  scanf("%d", &n);
  memset(cnt, 0, sizeof cnt);
  for (int i = 0; i < n; i++) {
    scanf("%d", a + i);
    cnt[a[i]]++;
  }
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += 1LL * (cnt[i] * (cnt[i] - 1)) / 2;
  }
  //cout << sum << endl;
  for (int i = 0; i < n; i++) {
    sum -= 1LL * (cnt[a[i]] * (cnt[a[i]] - 1)) / 2;
    printf("%lld\n", sum + 1LL * (cnt[a[i]] - 1) * (cnt[a[i]] - 2) / 2);
    sum += 1LL * (cnt[a[i]] * (cnt[a[i]] - 1)) / 2;
  }
  return 0;
}

Measured memory_bytes: 4864
from operator import itemgetter

n, m = map(int, input().split())
a = [0] * m
b = [0] * m

for i in range(m):
    a[i], b[i] = map(int, input().split())

ab = sorted([(a[i], b[i]) for i in range(m)], key=itemgetter(1))

# 前回除いた橋
removed = -1
ans = 0

for a, b in ab:
    # a が removed より大きい = まだ取り除いてない
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)

Measured memory_bytes: 26332
#!/usr/bin/env python3
import sys


def solve(N: int, S: str):
    dp = [[0] * (3 * N) for _ in range(3)]
    d = dict(zip('RGB', range(3)))
    dd = dict(zip(range(3), 'RGB'))
    S = [d[s] for s in S]
    for i in range(3):
        for j in range(N-1, -1, -1):
            dp[i][j] = dp[i][j+1] + (1 if S[j] == i else 0)
    #print(*dp, sep='\n')
    def f():
        for i in range(N-2):
            for j in range(i+1, N-1):
                c1, c2 = S[i], S[j]
                if c1 == c2:
                    continue
                c3 = 3 - c1 - c2
                di = j - i
                #print((i, j), dd[c1], dd[c2], dd[c3], j+1, j+di, j+di+1)
                #print(dp[c3][j+1], dp[c3][j+di])
                yield dp[c3][j+1] - dp[c3][j+di]
                yield dp[c3][j+di+1]
    print(sum(f()))


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    solve(N, S)

if __name__ == '__main__':
    main()


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

const int kN = 200'000 + 5;
const int kInf = 1'000'000'000 + 5;
int x[kN], y[kN];

int main() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d%d", &x[i], &y[i]);
    int a = min(*min_element(x, x + n), *min_element(y, y + n));
    int b = max(*max_element(x, x + n), *max_element(y, y + n));
    int c = -kInf, d = kInf;
    for (int i = 0; i < n; ++i) {
        c = max(c, min(x[i], y[i]));
        d = min(d, max(x[i], y[i]));
    }
    assert(c >= a && b >= d);
    long long ans = 1LL * (c - a) * (b - d);
    int df = b - a;
    vector<int> g(x, x + n);
    for (int i = 0; i < n; ++i) g.push_back(y[i]);
    for (int i = 0; i < n; ++i) if (x[i] > y[i]) swap(x[i], y[i]);
    sort(g.begin(), g.end());
    g.resize(unique(g.begin(), g.end()) - g.begin());
    vector<int> od(n);
    iota(od.begin(), od.end(), 0);
    sort(od.begin(), od.end(), [&](int i, int j) { return x[i] < x[j]; });
    int z = *min_element(y, y + n);
    multiset<int> p;
    for (int i = 0; i < n; ++i) p.insert(x[i]);
    for (int i = 0, j = 0; i < g.size(); ++i) {
        if (g[i] > z) break;
        while (j < n && x[od[j]] < g[i]) {
            p.erase(p.find(x[od[j]]));
            p.insert(y[od[j++]]);
        }
        ans = min(ans, 1LL * df * (*p.rbegin() - g[i]));
    }
    printf("%lld\n", ans);
    return 0;
}


Measured memory_bytes: 15600
n = int(input())
flag = 0
out = False
for j in range(n):
    ins = input().split()
    if(ins[0]==ins[1]):
        flag+=1
        if(flag==3):
            out=True
    else:
        flag = 0
if(out):
    print("Yes")
else:
    print("No")

Measured memory_bytes: 9184
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main(void){
    // Your code here!
    long long N, M, sum = 0;
    vector<long long> mass;
    vector<long long> diff;
    
    cin >> N >> M;
    for(long long i = 0; i < M; i++){
        long long temp;
        cin >> temp;
        mass.push_back(temp);
    }
    
    sort(mass.begin(), mass.end());
    
    for(int i = 0; i < M - 1; i++){
        diff.push_back(mass[i+1] - mass[i]);
        sum += mass[i+1] - mass[i];
    }
    
    sort(diff.begin(), diff.end(), [](long long a, long long b){ return a > b; });
    
    long long num_loop = min(N - 1, (long long)diff.size());
    for(int i = 0; i < num_loop; i++)
        sum -= diff[i];
    
    cout << sum << endl;
         
}


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

int main() {
    string a, b;
    cin >> a >> b;
    if(a.size() == b.size()) {
        for(int i = 0; i < a.size(); i++) {
            int an = a[i] - '0', bn = b[i] - '0';
            if(an > bn) {
                cout << "GREATER" << endl;
                return 0;
            } else if(an < bn) {
                cout << "LESS" << endl;
                return 0;
            }
        }
        cout << "EQUAL" << endl;
    }
    else if(a.size() > b.size()) cout << "GREATER" << endl;
    else cout << "LESS" << endl;

    return 0;
}

Measured memory_bytes: 256
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
amod4=list(map(lambda x:x%4, a))
d=Counter(amod4)
if n-d[0]-d[2]<d[0]+1:
  print('Yes')
elif d[2]==0 and n==2*d[0]+1:
  print('Yes')
else:
  print('No')


Measured memory_bytes: 20512
//#pragma once
#include <stdio.h>
#include <string>
#include <iostream>
#include <queue>
#include <algorithm>
#include <sstream>
#include <vector>
#include <math.h>
#include <set>
#include <map>
#include <numeric>
#include <bitset>
#include <iomanip>
#include <cctype>


using namespace std;
#define modd 1000000007


typedef pair<long long, long long> pl;


typedef string::const_iterator State;
class ParseError {};




#define ll long long




/*
class UnionFind {
public:
	vector <ll> par;
	vector <ll> siz;
	vector <ll> gr;

	// Constructor
	UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) ,gr(sz_){
		for (ll i = 0; i < sz_; ++i) par[i] = i;
	}
	void init(ll sz_) {
		par.resize(sz_);
		siz.assign(sz_, 1LL);  // resize だとなぜか初期化されなかった
		for (ll i = 0; i < sz_; ++i) par[i] = i; // 初期では親は自分自身
	}

	// Member Function
	// Find
	ll root(ll x) { // 根の検索
		while (par[x] != x) {
			x = par[x] = par[par[x]]; // x の親の親を x の親とする
		}
		return x;
	}

	// Union(Unite, Merge)
	bool merge(ll x, ll y) {
		x = root(x);
		y = root(y);
		if (x == y) return false;

		// merge technique（データ構造をマージするテク．小を大にくっつける）
		if (siz[x] < siz[y]) swap(x, y);
		siz[x] += siz[y];
		par[y] = x;
		return true;
	}



	bool issame(ll x, ll y) { // 連結判定
		return root(x) == root(y);
	}

	ll size(ll x) { // 素集合のサイズ
		return siz[root(x)];
	}


};*/


long long N, M, K, a, b, c, d, e, H, W, L;
ll A[200005] = {};
ll B[200005] = {};
ll C[200005] = {};
bool f, ff;
string S;
set <long long>sll;
pl bufpl;
vector <long long>vl[3];
vector <pl>vpl;
vector <string> vs;
set<ll> llset;

/*struct ST
{
	long long Kati;
	int bangou;

	bool operator<(const ST& another) const
	{
		return Kati < another.Kati;//比較
	};

};



vector <ST> vst;
ST st[200005];
ST bufst;
bitset<5000> bits;*/


long long modinv(long long aa, long long mm) {
	long long bb = mm, uu = 1, vv = 0;
	while (bb) {
		long long tt = aa / bb;
		aa -= tt * bb; swap(aa, bb);
		uu -= tt * vv; swap(uu, vv);
	}
	uu %= mm;
	if (uu < 0) uu += mm;
	return uu;
}



ll minn, maxx;
double ansa;
bool fl[30] = {};

string ss, sss;

int main() {


	cin >> a >> N >> M;

	e = 0;

	for (int i = 1; i < 100000000; i++) {

		b = a + i;
		c = 1;
		for (int j = 0; j < N; j++) {
			c *= b;
		}


		if (c > M) {
			break;
		}
		d = 0;
		while (c > 0) {
			d += c % 10;
			c /= 10;
		}

		if (d == i) {
			e++;
		}

		
	}


	cout << e<<endl;

	return 0;

}



Measured memory_bytes: 3164
#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <bitset>
#include <set>
#include <unordered_set>
#include <cmath>
#include <complex>
#include <deque>
#include <iterator>
#include <numeric>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <limits>
#include <iomanip>
#include <functional>
#include <cassert>
#include <atcoder/all>
using namespace std;

using ll=long long;
template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;
using vll = V<ll>;
using vvll = V<vll>;
#define ALL(v) v.begin(),v.end()
template < class T > inline bool chmax(T& a, T b) {if (a < b) { a=b; return true; } return false; }
template < class T > inline bool chmin(T& a, T b) {if (a > b) { a=b; return true; } return false; }
#define DEBUG_VLL(vec) for(int sz=0;sz<int(vec.size());sz++) std::cerr<<vec[sz]<<(sz==vec.size()-1?'\n':' ');

const long long MOD = 1000000007;
const long long HIGHINF = (long long)1e18;
const int INF = (int)1e9;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, q; cin >> n >> q;
    atcoder::dsu uni(n);
    for (int i = 0; i < q; i++) {
        int t, u, v; cin >> t >> u >> v;
        if (t == 0) uni.merge(u, v);
        else {
            cout << (uni.same(u, v) ? 1 : 0) << '\n';
        }
    }
    return 0;
}


Measured memory_bytes: 3940
<?php
// From https://qiita.com/yoshikyoto/items/6924478283dbdd549e4b
class Scanner {
    private $arr = [];
    private $count = 0;
    private $pointer = 0;
    public function next() {
        if($this->pointer >= $this->count) {
            $str = trim(fgets(STDIN));
            $this->arr = explode(' ', $str);
            $this->count = count($this->arr);
            $this->pointer = 0;
        }
        $result = $this->arr[$this->pointer];
        $this->pointer++;
        return $result;
    }
    public function hasNext() {
        return $this->pointer < $this->count;
    }
    public function nextInt() {
        return (int)$this->next();
    }
    public function nextDouble() {
        return (double)$this->next();
    }
}
// From https://qiita.com/yoshikyoto/items/6924478283dbdd549e4b
list($A)=sscanf(trim(fgets(STDIN)),"%d");
$p=array();
$sc = new Scanner();
for($i=0;$i<$A;$i++){
    $p[$i] = $sc->nextInt();
}
$buf = $p;
sort($buf);
$cnt=0;
for($i=0;$i<$A;$i++){
    if($p == $buf){
        printf("YES");
        exit;
    }
    if($p[$i] != $buf[$i]){
        $p[$i] = $buf[$i];
        $cnt++;
    }
    if($cnt == 3){
        printf("NO");
        exit;
    }
}
if($p == $buf){
    printf("YES");
    exit;
}
printf("NsO");
exit;

Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
#define REP(i,m,n) for(ll i=(ll)(m);i<(ll)(n);i++)
#define fi first
#define se second
long long mo = 1000000007;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
typedef pair<ll,Pll> Plp;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
template<class A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}cout << "\n";}
ld PI=3.14159265358979323846;

vector<vector<ll>> d(305, vector<ll>(305,1e18));

void warshall_floyd(int n) { // nは頂点数
  for (int i = 0; i < n; i++)      // 経由する頂点
    for (int j = 0; j < n; j++)    // 開始頂点
      for (int k = 0; k < n; k++)  // 終端
        d[j][k] = min(d[j][k], d[j][i] + d[i][k]);
}
int main(){
    ll N;
    cin >> N;
    vector<vector<ll>> A(N,vector<ll>(N)), G(N);
    rep(i,N){
        rep(j,N){
            cin >> A[i][j];
            d[i][j] = A[i][j];
        }
    }
    warshall_floyd(N);
    ll ans = 0;
    rep(i,N){
        REP(j,i+1,N){
            if(d[i][j] < A[i][j]){
                cout << -1 << endl;
                return 0;
            }else if(d[i][j] > A[i][j]){
                //d[i][j] = 1e18;
                //d[j][i] = 1e18;
                continue;
            }
            bool flag =false;
            rep(k,N){
                if(k==j||k==i)continue;
                if(d[i][j] == d[i][k] + d[k][j]){
                    flag = true;
                    break;
                }
            }
            if(flag)continue;
            ans += A[i][j];
        }
    }
    cout << ans << endl;
    /*
    UnionFind<ll> uf(N);
    rep(i,N){
        REP(j,i+1,N){
            //if(0 == j)continue;
            uf.merge(i,j,A[i][j]);
        }
    }
    ll ans = 0;
    rep(i,1)REP(j,i+1,N){
        ans += uf.diff(i,j);
    }
    rep(i,N)REP(j,i+1,N){
        //if(i == j) continue;
        if(A[i][j] != uf.diff(i,j)){
            if(A[i][j] < uf.diff(i,j)){
                ans += A[i][j];
            }else{
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << ans << endl;
    /*
    map<Pll,ll> mp;
    rep(i,N){
        ll mi = 1e18;
        ll id = -1;
        rep(j,N){
            if(i==j)continue;
            if(mi > A[i][j]){
                mi = A[i][j];
                id = j;
            }
        }
        G[i].push_back(id);
        G[id].push_back(i);
        mp[Pll(i,id)]++;
        mp[Pll(id,i)]++;
    }
    cout << N << endl;*/
}

Measured memory_bytes: 5084
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fastIO ios_base::sync_with_stdio(false), cin.tie(NULL)


int main() {
	fastIO;
	int n, m;
	cin >> n >> m;
	vector<ll> v(n);
	for (auto& i : v) {
		cin >> i;
	}
	vector<pair<ll, ll>> vv;
	for (int i = 0; i < m; i++) {
		ll b, c;
		cin >> b >> c;
		vv.push_back({c, b});
	}
	sort(v.begin(), v.end());
	sort(vv.rbegin(), vv.rend());
	int curr = 0, vvptr = 0;
	ll total = 0;
	while(curr < n && vvptr < m) {
		int st = curr, en = n-1, mid, ans=-1;
		while(st <= en) {
			mid = (st+en)/2;
			if (v[mid] <= vv[vvptr].first) {
				st = mid+1;
				ans = mid;
			}
			else {
				en = mid-1;
			}
		}
		if (ans == -1) {
			vvptr++;
			continue;
		}
		int dist = min(vv[vvptr].second, (ll)ans-curr+1);
		total += dist*vv[vvptr].first;
		curr = min(curr+vv[vvptr].second, (ll)ans+1);
		vvptr++;
	}
	for (int i = curr; i < n; i++) {
		total += v[i];
	}
	cout << total;


}


Measured memory_bytes: 6092
import heapq
H, W = map(int, input().split())
C = [[int(i) for i in input().split()] for j in range(10)]

MinCost = [10000 for i in range(10)]
MinCost[1] = 0
Fin = [False for i in range(10)]
Fin[1] = True
Q = []
heapq.heappush(Q, (0, 1))
while Q:
    nowCost, nowNode = heapq.heappop(Q)
    Fin[nowNode] = True
    for i in range(10):
        if i != nowNode and Fin[i] == False:
            if MinCost[i] > nowCost + C[i][nowNode]:
                MinCost[i] = nowCost + C[i][nowNode]
                heapq.heappush(Q, (nowCost + C[i][nowNode], i))

Total = 0
for i in range(H):
    A = [int(i) for i in input().split()]
    for a in A:
        if a >= 0:
            Total += MinCost[a]
print(Total)

Measured memory_bytes: 3188
import java.util.Scanner;

class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		while(true){
			int n = scan.nextInt();
			if(n == -1)break;
			
			double x = 1;
			double y = 0;
			
			for(int i = 2;i <= n; i++){
				double d = Math.sqrt(x * x + y * y);
				double dx = -y / d;
				double dy = x / d;
				x += dx;
				y += dy;
			}
			System.out.printf("%.2f\n%.2f\n", x, y);
		}
	}
}

Measured memory_bytes: 26140
using System;
using System.Linq;
using System.Collections;
using System.Collections.Generic;
using System.Text;


class Program
{
    static void Main(string[] args)
    {
        // 入力
        //var s = Console.ReadLine();
        var n = double.Parse(Console.ReadLine());
        //int[] n = Console.ReadLine().Split().Select(int.Parse).ToArray();

        double ans = 2 * n * Math.PI;
        // 出力
        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 27572
#include <stdio.h>

int main(void){
    int i,n;
    int h[20];
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",h+i);
    }
    int count = 1;
    int max = h[0];
    for(i=1;i<n;i++){
        if(h[i]<max)continue;
        else{
            max = h[i];
            count++;
        }
    }
    printf("%d\n",count);
    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <boost/range/adaptors.hpp>
#include <boost/range/irange.hpp>

using namespace std;
using namespace boost;
using namespace boost::adaptors;

int main() {
    int64_t n, d, a;
    cin >> n >> d >> a;

    vector<pair<int64_t, int64_t>> xh(n);
    for (auto&& t : xh) {
        cin >> t.first >> t.second;
    }

    sort(xh.begin(), xh.end());

    int64_t ans = 0;
    vector<pair<int64_t, int64_t>> tmp;
    int64_t cur = 0;
    int64_t damage = 0;
    for (auto i : irange(0L, n)) {
        while (cur < tmp.size() && xh[i].first >= tmp[cur].first) {
            damage -= tmp[cur].second;
            ++cur;
        }

        xh[i].second -= damage;
        if (xh[i].second <= 0) {
            continue;
        }

        int64_t m = (xh[i].second - 1) / a + 1;
        ans += m;
        damage += m * a;
        tmp.emplace_back(xh[i].first + 2 * d + 1, m * a);
    }

    cout << ans << endl;
}

Measured memory_bytes: 9200
#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, K;
  cin >> N >> K;
  map<int,int> mp;
  rep(i, N) {
    int a;
    cin >> a;
    mp[a]++;
  }
  if((int)mp.size() <= K) {
    cout << 0 << endl;
    return 0;
  }
  vector<P> ans;
  for (auto a : mp){
    ans.push_back(P(a.second,a.first));
  }
  sort(ans.begin(), ans.end());
  int ball = 0;
  int yobun = (int)ans.size() - K;
  rep(i, yobun) ball += ans[i].first;
  cout << ball << endl;
  return 0;
}

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

int main()
{
    cin.tie(0);
   	ios::sync_with_stdio(false);
    int H, W, h, w;
    cin >> H >> W >> h >> w;
    cout << (H - h) * (W - w) << endl;
    return 0;
}

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

using namespace std;
typedef long long ll;
const int MAXn = 1e6;

set<int> st;
map<int, bool> repeat, vis;

int main(){
	int n; cin >> n;
	for(int i = 0; i < n; i++){
		int x; cin >> x;
		if(st.count(x)) repeat[x] = true;
		st.insert(x);
	}
	int ans = 0;
	for(auto i:st){
		if(vis[i]) continue;
		for(int j = i+i; j <= MAXn; j += i){
			vis[j] = true;
		}
		ans += !repeat[i] and !vis[i];
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 59776
import sys
def input():
    return sys.stdin.readline()[:-1]
N = int(input())
S = input()
if N==1:
    print(1)
    exit()
pre = S[0]
flag = False
cnt = 1
for i in range(1,N):
    k = S[i]
    if pre==k:
        if flag:
            pass
        else:
            flag = True
    else:
        cnt += 1
        flag = False
    pre = k
print(cnt)

Measured memory_bytes: 3316
#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif

#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define pf push_front
#define pb push_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define rsz resize()
#define lb lower_bound
#define ub upper_bound
#define br cout << endl

typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); } 
int bit(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
int bit(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }

template<typename T>
void leftShift(vector<T> &v, ll k) { k %= sz(v); if(k < 0) k += sz(v); rotate(v.begin(), v.begin() + k, v.end()); }
template<typename T>
void rightShift(vector<T> &v, ll k) { leftShift(v, sz(v) - k); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
	uniform_int_distribution<ll> uid(l, r);
	return uid(rng);
}

inline int nxt() {
	int x;
	cin >> x;
	return x;
}

inline int nxtll() {
	ll x;
	cin >> x;
	return x;
}

void pr() {}
void sc() {}

template <typename Head, typename... Tail>
void pr(Head H, Tail... T) { cout << H << " "; pr(T...); }

template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#ifndef LOCAL
string to_string(__int128 x) {
	string s = "";
	bool neg = 0;
	if(x < 0) { s += "-"; neg = 1; }
	if(!x) s += '0';
	while(x) {
		int rem = x % 10;
		s += to_string(rem);
		x /= 10;
	}
	reverse(s.begin() + neg, s.end());
	return s;
}
#endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,int b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ans * 1LL * a) % mod;
		a = (a * 1LL * a) % mod;
		b >>= 1;
	}
	return ans;
}

/*
	Lookout for overflows!!
	Check array sizes!!
	Clear before test cases!!
	Use the correct modulo!!
	Check for corner cases!!
	Are you forgetting something?!
*/

const int N = 2e5 + 5;
int fact[N], ifact[N];

int ncr(int n,int k) {
	int ans = (fact[n] * 1LL * ifact[n - k]) % mod;
	return (ans * 1LL * ifact[k]) % mod;
}

ll sum(ll l, ll r) {
	l--;
	return r * (r + 1) / 2 - l * (l + 1) / 2;
}

void solve() {
	int n = nxt(), k = nxt();
	fact[0] = 1;
	ifact[0] = 1;
	fr(i, 1, N - 1) {
		fact[i] = (i * 1LL * fact[i - 1]) % mod;
		ifact[i] = pwr(fact[i], mod - 2);
	}
	int ans = 0;
	fr(i, k, n + 1) {
		ll maxsum = sum(n - i + 1, n);
		ll minsum = sum(0, i - 1);
		ans = (ans + maxsum - minsum + 1) % mod;
	}
	cout << ans;
}

signed main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	// cin >> t;
	t = 1;
	for(int tt = 1; tt <= t; tt++) {
		solve();
	}
	return 0;
}

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

using namespace std;

int main(void) {
    string S;
    cin >> S;
    if(S[0] == S[1] || S[0] == S[2] || S[1] == S[2]) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
    return 0;
}


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

namespace zyt
{
	int work()
	{
		int a, b;
		scanf("%d%d", &a, &b);
		if ((a & 1) ^ (b & 1))
			printf("IMPOSSIBLE");
		else
			printf("%d", (a + b) / 2);
		return 0;
	}
}
int main()
{
	return zyt::work();
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long  ll;
#define FOR(i,a,n) for(ll i=(ll)a;i<(ll)n;i++)
#define RFOR(i,a,n) for(ll i=(ll)n-1;i >= (ll)a;i--)
#define rep(i,n) FOR(i,0,n)
#define rrep(i,n) RFOR(i,0,n)
#define ALL(v) v.begin(), v.end()
#define bra(first,second) '(' << first << ',' << second << ')'
constexpr ll MOD = 1000000007;
//constexpr ll MOD = 998244353;
ll INF = 4001001001001001001;
long double EPS = 1e-9;
long double PI = 3.141592653589793238;
template<typename T>
void remove(std::vector<T>& vector, unsigned int index){
    vector.erase(vector.begin() + index);
}

using Graph = vector<vector<tuple<ll,ll,ll>>>;

// MOD確認

int main(){
    ll A,B,N;
    cin >> A >> B >> N;
    double a = min(N,B-1) / (double)B;
    double b = A * a;
    cout << floor(b) << endl;
}


Measured memory_bytes: 3788
a=int(input())
b=int(input())
c=int(input())
d=int(input())
e=int(input())

l=[a,b,c,d,e]
s=sum(l)
ll=[10-a%10,10-b%10,10-c%10,10-d%10,10-e%10]
for i in range(5):
        if ll[i]==10:
                ll[i]=0
ll.sort()

print(s+sum(ll[:4]))


Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define OP ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define F first
#define S second
#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 repr(i,n) for(int i = n - 1; i >= 0; --i)
#define Rep(i, a, n) for(int i = (a); i <=(n); ++i)
#define repst(i, n) for(auto it = n.begin(); it != n.end(); ++it)
#define Repr(i, a, n) for(int i = (n); i >= (a); --i)
typedef long long ll;
typedef std::vector<int> vi;
typedef std::pair<int, int> pii;
const int inf = int(1e9);
const int mod = inf + 7;
const double PI = acos(-1.0);
using namespace std;
const int N = 2e5 + 155;
template<typename T>
inline void read(T&x){
    x=0;int f=1;char ch = getchar();
    while(ch<'0' ||ch>'9'){ if(ch=='-')f=-1;ch=getchar(); }
    while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
    x*=f;
}

ll bp(ll a, ll n){
	ll r = 1;
	while(n) {
		if(n & 1) r = (r * a) % mod;
		a = (a * a) % mod;
		n >>= 1;
	}
	return r;
}

void solve() {
	int n;
	cin >> n;
	vector<char> prime (N+1, true);
	prime[0] = prime[1] = false;
	for (int i=2; i<=N; ++i)
		if (prime[i])
			if (i * 1ll * i <= n)
				for (int j=i*i; j<=N; j+=i)
					prime[j] = false;
	for(int i = n; i <= N; i++) {
		if (prime[i]) {
			cout << i;
			return;
		}
	}
}
 
int main(){
    OP
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    int t = 1;
    //cin >> t;
    for(int i = 1; i <= t; i++) {
        solve();
    }
    return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
int main(){
	long long int K; 
    cin >> K; 
	long long int A[50] = {}; 
	long long int Q, R; 
	Q = K / 50; 
	R = K % 50; 
	for(int i = 0; i < 50 - R; i++){
		A[i] = (long long) 49 - R; 
		A[i] += Q; 
	}
	for(int i = 50 - R; i < 50; i++){
		A[i] = (long long) 100 - R; 
		A[i] += Q; 
	}
	cout << 50 << endl; 
	for(int i = 0; i < 50; i++){
		cout << A[i] << " "; 
	}
}

Measured memory_bytes: 256
inf = 10**9
H, N = map(int, input().split())
AB = []
for n in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))
AB.sort(reverse=True, key=lambda x: x[0])
dp = [inf] * (H + 10 ** 4)
dp[0] = 0
for a, b in AB:
    for h in range(H):
        if dp[h] != inf:
            tmp = dp[h] + b
            if tmp < dp[h + a]:
                dp[h + a] = tmp
print(min(dp[H:]))


Measured memory_bytes: 41452
H, W, K = map(int, input().split())
Map = [[0] * (W + 1) for _ in range(H + 1)]
for _ in range(K):
    h, w, k = map(int, input().split())
    Map[h][w] = k

DP = [[[0] * (H + 1) for _ in range(W + 1)] for __ in range(4)]


for i in range(1, H + 1):
    for j in range(1, W + 1):
        x = Map[i][j]
        if Map:
            DP[0][j][i] = max(DP[0][j][i-1], DP[1][j][i-1], DP[2][j][i-1], DP[3][j][i-1], DP[0][j-1][i])
            DP[1][j][i] = max(DP[1][j - 1][i], DP[0][j-1][i] + x, DP[0][j][i-1] + x, DP[1][j][i-1] + x, DP[2][j][i-1] + x, DP[3][j][i-1] + x)
            DP[2][j][i] = max(DP[2][j - 1][i], DP[1][j-1][i] + x)
            DP[3][j][i] = max(DP[3][j - 1][i], DP[2][j-1][i] + x)

        else:
            DP[0][j][i] = max(DP[0][j][i-1], DP[1][j][i-1], DP[2][j][i-1], DP[3][j][i-1], DP[0][j-1][i])
            DP[1][j][i] = DP[1][j-1][i]
            DP[2][j][i] = DP[2][j-1][i]
            DP[3][j][i] = DP[3][j-1][i]

print(max(DP[0][W][H], DP[1][W][H], DP[2][W][H], DP[3][W][H]))

Measured memory_bytes: 429144
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<algorithm>
#include<queue>
#include<list>
#include<stack>
#include<cstdio>
#include<fstream>
#include<numeric>
#include<functional>
#include<utility>
#include<memory>
#include <cstring>
#include<bits/stdc++.h>
using namespace std;   
int main()
{
	int n,k,sum=0,ans=0,mn=9999999;
	cin>>n>>k;
	int a[1000];
	for (int i=0;i<n;i++)
	{
		cin>>a[i];
		sum=sum+a[i];
	}
	k=k-sum;
	ans+=n;
	sort(a,a+n);
	ans=ans+k/a[0];
	cout<<ans<<endl;
	return 0;
}

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

int main(){
  long long  N,M;
  cin>>N>>M;
  priority_queue<long long>PQ;
  long long temp;
  for(long long i=0;i<N;i++){
    cin>>temp;
    PQ.push(temp);
  }
  while(M>0){
    temp=PQ.top();
    PQ.pop();
    temp=temp/2;
    PQ.push(temp);
    M--;
  }
  long long  sum=0;
  for(long long i=0;i<N;i++){
    sum=sum+PQ.top();
    PQ.pop();
  }
  cout<<sum<<endl;
  return 0;
}

    
  

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
int main(){
    string o,e;
    cin>>o;
    cin>>e;
    string ans="";//コノジテンデハ、ハイレツノオオキサハ０デアル
    int ln=o.size()+e.size();
    //ans.resize(ln);
    for(int i=0;i<ln;i++){
        if(i%2==0){ 
            ans.push_back(i);
            ans.at(i)=o.at(i/2);

        }
        if(i%2==1){ 
            ans.push_back(i);
            ans.at(i)=e.at(i/2);}
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3596
N, S = map(int,input().split())
A = list(map(int,input().split()))
mod = 998244353
dp = [[0 for j in range(S + 1)] for i in range(N + 1)]
dp[0][0] = 1
for i in range(N) : 
    for j in range(S + 1) : 
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= mod 
        if j + A[i] <= S : 
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= mod
print(dp[N][S])

Measured memory_bytes: 147616
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

a, b = map(int, readline().split())
if a > 9 or b > 9:
    print(-1)
else:
    print(a * b)


Measured memory_bytes: 2940
s = list(input())
t = list(input())
s.sort()
#s.reverse()
t.sort()
t.reverse()
if (s[0]<t[0]):
    print("Yes")
else:
    if(len(s)<len(t)):
        flag = 0
        for i in range(1,len(s)):
            if (s[i-1]!=s[i]):
                flag += 1
        for j in range(1,len(t)):
            if (t[j-1]!=t[j]):
                flag += 1
        if (flag == 0):
            print("Yes")
        else:
            print("No")
    else:
        print("No")

Measured memory_bytes: 3064
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#pragma G++ optmize("ofast")
#pragma GCC optmize("ofast")
typedef long long ll;
inline ll read(){
    ll x=0ll,f=1ll;
    char ch=getchar_unlocked();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1ll;
        ch=getchar_unlocked();
    }
    while (ch<='9'&&ch>='0'){
        x=(x<<3ll)+(x<<1ll)+(ch-'0');
        ch=getchar_unlocked();
    }
    return x*f;
}
#define MAXN 100005
using namespace std;
ll f[MAXN],sum[MAXN],ans[MAXN];
int main(){
    ll sta[MAXN],top=1;
    ll n,m;
    n=read(),m=read();
    sta[top]=n;
    for (register ll i=0;i<m;++i){
        ll t;
        t=read();
        while (top>0&&t<=sta[top]) --top;
        sta[++top]=t;
        //将序列变成严格上升的
    }
    f[top]=1ll;
    for (register ll i=top;i>=1;--i){
        ll cur=sta[i];
        while (cur>sta[1]){
            register ll pos=lower_bound(sta+1,sta+1+top,cur)-sta-1;
            f[pos]+=f[i]*(ll)(cur/sta[pos]);cur%=sta[pos];
        }
        sum[cur]+=f[i];
    }
    for (register ll i=n;i>=1;--i){
        ans[i]=ans[i+1]+sum[i];
    }
    for (register ll i=1;i<=n;++i){
        printf("%lld\n",ans[i]);
    }
}

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

ll n,a,b,c,d;
ll mod = 1e9+7;
ll dp[1010][1010];

const ll MOD = 1000000007;
const int SIZE = 1010;
ll inv[SIZE],fac[SIZE],finv[SIZE];
void make(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<SIZE;i++){
        inv[i]=MOD-inv[MOD%i]*(MOD/i)%MOD;
        fac[i]=fac[i-1]*(ll) i%MOD;
        finv[i]=finv[i-1]*inv[i]%MOD;
    }
}

ll powmod(ll a, ll n){
    a%=mod;
    if(n==1) return a;
    if(n==0) return 1;
    if(n%2==0){
        return powmod(a,n/2)*powmod(a,n/2) %mod;
    }else{
        return powmod(a,(n-1)/2)%mod*powmod(a,(n-1)/2)%mod*a %mod;
    }
}

int main() {
    std::cin >> n>>a>>b>>c>>d;
    make();
    for (int i = 0; i <= n; i++) {
        dp[i][0]=1;
    }

    for (int j = 1; j <= n; j++) {
        for (int i = a; i <= b; i++) {
            dp[i][j]=dp[i-1][j]%MOD;
            for (int k = c; k <= d && j-k*i >= 0; k++) {
                dp[i][j] += dp[i-1][j - k*i] * fac[n-j+k*i] %MOD * finv[n-j] %MOD * finv[k] %MOD * powmod(finv[i],k) %MOD;
            }
            dp[i][j] %= MOD;
        }
    }
    std::cout << dp[b][n] << std::endl;
}


Measured memory_bytes: 8192
#include<bits/stdc++.h>
#define int long long
using namespace std;
int read(){
	int w=0,f=1;
	char c=' ';
	while(c<'0'||c>'9')c=getchar(),f=c=='-'?-1:f;
	while(c>='0'&&c<='9')w=w*10+c-48,c=getchar();
	return w*f;
}
const long long p=1e9+7;
int a[10003];
signed main(){
	int n=read();
	if(n<3) puts("0"),exit(0);
	if(n==3) puts("1"),exit(0);
	a[3]=a[4]=a[5]=1,a[6]=2;
	for(int i=7; i<=n; i++) { a[i]=1; for(int j=3; j+3<=i; j++) a[i]+=a[j],a[i]%=p; }
	printf("%lld\n",a[n]);
	return 0;
}


Measured memory_bytes: 3748