akhauriyash/Code-Regression huggingface dataset:
import sys
def input():
    return sys.stdin.readline()[:-1]

"""
H Wの後に
#.#.
###.
みたいな文字列を受け取る
"""
H,W = map(int,input().split(' '))
MAP = [['#']*(W+1)] + [None]*H

for i in range(1,H+1):
    MAP[i] = ['#'] + list(map(str,input()))
import queue
q = queue.Queue()


MAP[H][W] = 'G'
visited = [None]*(H+1)
for i in range(H+1):
    visited[i] = [False]*(W+1)

d_num = 0
for i in range(1,H+1):
    for j in range(1,W+1):
        if MAP[i][j]=='#':
            d_num += 1

def is_okay(x,y):
    if not (0<x<W+1) or not (0<y<H+1):
        return False
    if visited[y][x] or MAP[y][x]=='#':
        return False
    return True

n = 0
q.put([1,1,n])
ans = 10**7 + 7

while not q.empty():
    x,y,n = q.get()
    k = MAP[y][x]

    n += 1
    if k=='G':
        ans = min(ans,n)
        break

    if is_okay(x+1,y):
        q.put([x+1,y,n])
        visited[y][x+1] = True
    if is_okay(x-1,y):
        q.put([x-1,y,n])
        visited[y][x-1] = True
    if is_okay(x,y+1):
        q.put([x,y+1,n])
        visited[y+1][x] = True
    if is_okay(x,y-1):
        q.put([x,y-1,n])
        visited[y-1][x] = True


if not ans==10**7 + 7:
    ANS = H*W - ans - d_num
else:
    ANS = -1

print(ANS)

Measured memory_bytes: 3952
#include<stdio.h>

int main()
{
 int a,b,c;

 scanf("%d%d%d",&a,&b,&c);

 if((a==b)&&(b==c))printf("1\n");
 else if((a==b)||(b==c)||(a==c))printf("2\n");
 else printf("3\n");

 return 0;
}

Measured memory_bytes: 128
using System;
using System.Linq;
using System.Collections.Generic;
using System.IO;

public class Program
{

    public static void Main()
    {
        int[] n = Console.ReadLine().Split(' ').Select(a => int.Parse(a)).ToArray();
        string ans = "No";
        if (n[0] <= n[2] && n[2] <= n[1]) ans = "Yes";
        Console.WriteLine(ans);
    }

    static int[] s_to_i(string[] s)
    {
        int[] ret = Array.ConvertAll<string, int>(s, delegate (string value) { return int.Parse(value); });
        return ret;
    }
}

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

int main()
{
    int n, i, j, k, b, f, r, v;
    int num[4][3][10];
    
	for(i = 0; i < 4; i++){
		for(j = 0; j < 3; j++){
			for(k = 0; k < 10; k++){
                num[i][j][k] = 0;
			}
		}
	}

    cin >> n;
	for(i = 0; i < n; i++){
        cin >> b >> f >> r >> v;
        num[b - 1][f - 1][r - 1] = num[b - 1][f - 1][r - 1] + v;
	}

	for(i = 0; i < 4; i++){
		for(j = 0; j < 3; j++){
			for(k = 0; k < 10; k++){
                cout << " " << num[i][j][k];
			}
            cout << endl;
		}
		if(i < 3){
			for(k = 0; k < 20; k++){
				cout << "#";
			}
            cout << endl;
		}
	}

    return 0;
}

Measured memory_bytes: 1160
#define s(a,b) (t=a,a=b,b=t)
f(int*a){*a=(*a&7)<<4|*a>>4;}char p[9];m,a,b,c,t,r;main(n){while(scanf("%d",&n),n){r=1,a=22,b=37,c=52;while(n--){scanf("%s",p);m=*p-76;if(m%6==0){s(b,c);t=m>0?f(&c):f(&b);}else if(1<m&&m<8){s(a,b);t=m^7?f(&b):f(&a);}else{s(a,c);t=m>0?f(&c):f(&a);}r+=a>>4;}printf("%d\n",r);}}

Measured memory_bytes: 0
#include <bits/stdc++.h>
    using namespace std;
    typedef long long lint;
    typedef pair<int,int> pint;
    #define rep(i, n) for(int i = 0; i < n; i++)
    #define rep2(elem, vec) for(auto elem: vec)
    #define SORT(V) sort((V).begin(),(V).end())
    #define RSORT(V) sort((V).rbegin(), (V).rend())
    lint gcd(int a,int b){return b?gcd(b,a%b):a;}
    lint lcm(int a,int b){return a*b/gcd(a,b);}
    lint comb(int a,int b){return b?comb(a-1,b-1)*a/b:1;}

int main(){
    char a;
    cin >> a;
    cout << char(a+1);
    return 0;
}

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

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll, ll> pii;
typedef vector<pii> vii;
typedef vector<vi> vvi;
const int MOD = 1e9 + 7;

#define fastIO \
ios_base::sync_with_stdio(false); cin.tie(nullptr);
#define endl '\n'
#define pb push_back
#define ff first
#define ss second
#define mp make_pair 

int main() {
    fastIO;
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (auto& i : a)    cin >> i;
    if (n == k) {
        ll pdt = 1;
        for (auto i : a) {
            pdt = (pdt * i) % MOD;
        }
        if (pdt < 0)    pdt += MOD;
        cout << pdt << endl;
        return 0;
    }

    sort(a.begin(), a.end(), [](ll x, ll y){
        return abs(x) > abs(y);
    });

    bool zero = false;
    int pos = 0;
    for (auto i : a) {
        if (i == 0) zero = true;
        else if (i > 0) ++pos;
    }

    if (pos == 0 && k % 2 == 1) {
        if (zero)   cout << 0 << endl;
        else {
            ll pdt = 1;
            for (int i = n - 1; i >= n - k; i--) {
                pdt = (pdt * abs(a[i])) % MOD;
            }
            if (pdt < 0)    pdt += MOD;
            pdt *= -1;
            pdt %= MOD;
            if (pdt < 0)    pdt += MOD;
            cout << pdt << endl;
        }
        return 0;
    }

    int lastPos = -1, lastNeg = -1;
    bool neg = false;
    for (int i = 0; i < k; i++) {
        if (a[i] < 0)   neg = !neg;
        if (a[i] > 0)   lastPos = i;
        else if (a[i] < 0)  lastNeg = i;
        else {
            cout << 0 << endl;
            return 0;
        }
    }
    if (neg) {
        int nextPos = -1, nextNeg = -1;
        for (int i = k; i < n; i++) {
            if (a[i] > 0 && nextPos < 0)   nextPos = i;
            else if (a[i] < 0 && nextNeg < 0)  nextNeg = i;
        }
        cerr << nextPos << " " << nextNeg << endl;
        cerr << lastPos << " " << lastNeg << endl;
        if (nextPos < 0 && nextNeg < 0) {
            cout << 0 << endl;
            return 0;
        } else if (nextPos > 0 && nextNeg < 0) {
            assert(lastNeg >= 0);
            swap(a[nextPos], a[lastNeg]);
        } else if (nextPos < 0 && nextNeg > 0) {
            if (pos == 0) {
                // absolutely no positive values => k must be odd to get negative => case already taken
            }
            assert(lastPos >= 0);
            swap(a[lastPos], a[nextNeg]);
        } else if (nextPos > 0 && nextNeg > 0) {
            if (lastPos >= 0 && (lastNeg < 0 || a[lastNeg] * a[nextNeg] >= a[lastPos] * a[nextPos])) {
                swap(a[lastPos], a[nextNeg]);
            } else {
                swap(a[lastNeg], a[nextPos]);
            }
        }
    }

    ll pdt = 1;
    neg = false;
    for (int i = 0; i < k; i++) {
        if (a[i] < 0)   neg = !neg;
        pdt = (pdt * abs(a[i])) % MOD;
    }
    if (neg)    pdt *= 1;
    pdt = ((pdt % MOD) + MOD) % MOD;
    cout << pdt << endl;
    return 0;
}


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

int main()
{
  int a, b, c, tmp;
  
  cin >> a >> b >> c;
  
  if (a > b) { tmp = a; a = b; b = tmp; }
  if (a > c) { tmp = a; a = c; c = tmp; }
  if (b > c) { tmp = b; b = c; c = tmp; }

  cout << a << " " << b << " " << c << endl;

  return 0;
}


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

int main() {
 
  int N ;
  cin >>N ;
 if(N < 10 ){
   cout << N <<endl;
 }else if(N >=10 && N <100){
   cout << 9<<endl;
 }else if(N >=100 && N <1000){
   cout << 9+N-99 <<endl;
 }else if(N >=1000 && N < 10000){
   cout << 909<<endl;
 }else if(N >=10000 && N < 100000){
   cout << 9+900+N-9999 <<endl;
 }else if(N==100000){
   cout << 90909 <<endl;
}
}


Measured memory_bytes: 256
k = int(input())
if k % 2 == 0 or k % 5 == 0:
    print(-1)
    exit()
    
if k % 7 == 0:
    k //= 7

num = 1
plus = 10
for i in range(1, k + 1):
    if int(num) % k == 0:
        print(i)
        exit()
    num += plus
    num %= k
    plus *= 10
    plus %= k

print(-1)        

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

int main(){
    int N;
    cin >> N;
    map<string, int> mp;

    for (int i=0; i<N; i++){
        string key;
        cin >> key;
        mp[key] += 1;
    }
    int max = 0;
    for (auto itr = mp.begin(); itr != mp.end(); ++itr){
        // cout << itr->first << itr->second << endl;
        if (max < itr->second){
            max = itr->second;
        }
    }
    for (auto itr = mp.begin(); itr != mp.end(); ++itr){
        if (itr->second ==  max){
            cout << itr->first << endl;
        }
    }
    return 0;
}


Measured memory_bytes: 25216
def main():
    import sys
    import heapq
    from copy import deepcopy
    from collections import deque
    sys.setrecursionlimit(10 ** 6)
    input = sys.stdin.readline
    N, K = [int(x) for x in input().strip().split()]
    V = [int(x) for x in input().strip().split()]
    ans = -float('inf')
    for l in range(min(N, K)+1):
        for r in range(min(N, K)-l+1):
            vt = sorted(V[:l] + V[N-r:])
            c = 0
            i = 0
            for i in range(len(vt)):
                if c == (K-l-r):
                    break
                if vt[i] < 0:
                    vt[i] = 0
                    c += 1
                else:
                    break
            ans = max(ans, sum(vt))

    print(ans)

if __name__ == '__main__':
    main()

Measured memory_bytes: 3572
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		if (a < b) {
			System.out.println("a < b");
		} else if (a == b){
			System.out.println("a == b");
		} else {
			System.out.println("a > b");
		}
	}
	

}

Measured memory_bytes: 26056
#define LOCAL
#define _USE_MATH_DEFINES
#include <array>
#include <cassert>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iomanip>
#include <string>
#include <sstream>
#include <vector>
#include <queue>
#include <stack>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <complex>
#include <cmath>
#include <numeric>
#include <bitset>
#include <functional>
#include <random>
#include <ctime>

using namespace std;

template <typename A, typename B>
ostream& operator <<(ostream& out, const pair<A, B>& a) {
  out << "(" << a.first << "," << a.second << ")";
  return out;
}
template <typename T, size_t N>
ostream& operator <<(ostream& out, const array<T, N>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& a) {
  out << "["; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "]";
  return out;
}
template <typename T, class Cmp>
ostream& operator <<(ostream& out, const set<T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& v : a) { out << (first ? "" : ", "); out << v; first = 0;} out << "}";
  return out;
}
template <typename U, typename T, class Cmp>
ostream& operator <<(ostream& out, const map<U, T, Cmp>& a) {
  out << "{"; bool first = true;
  for (auto& p : a) { out << (first ? "" : ", "); out << p.first << ":" << p.second; first = 0;} out << "}";
  return out;
}
#ifdef LOCAL
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
#else
#define trace(...) 42
#endif
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
  cerr << name << ": " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
  const char* comma = strchr(names + 1, ',');
  cerr.write(names, comma - names) << ": " << arg1 << " |";
  __f(comma + 1, args...);
}

typedef long long int64;
typedef pair<int, int> ii;
const int64 INF = 1LL << 60;
const int MOD = 1e9 + 7;
mt19937 mrand(random_device{}());
int rnd(int x) { return mrand() % x; }

struct fast_ios {
  fast_ios() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
  };
} fast_ios_;

const int N = 2e5 + 10;
int64 a[N];
map<ii, int64> dp;
int n;

int64 solve(int pos, int picked) {
  if (picked > n / 2 || picked + (n - pos + 1) / 2 < n / 2) return -INF;
  if (pos >= n) return 0;
  ii cur = {pos, picked};
  if (dp.count(cur)) return dp[cur];
  int64 ret = solve(pos + 1, picked);
  ret = max(ret, a[pos] + solve(pos + 2, picked + 1));
  // trace(pos, picked, ret);
  return dp[cur] = ret;
}

int main() {
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%lld", &a[i]);
  }
  int64 ret = solve(0, 0);
  printf("%lld\n", ret);
  return 0;
}


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

int main(){
  int count=0;
  vector<int> v(3);
  r(i,3)cin >> v[i];
  sort(v.begin(),v.end());
  count+=v[2]-v[1];
  count+=(v[1]-v[0]+1)/2;
  if((v[1]-v[0])%2==1)count++;
  cout << count <<endl;
}


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

int main(){
    string S; cin >> S;
    ll K; cin >> K;
    ll size = S.size();
    bool jud = false;
    ll ans = 0;
    ll former=1;
    ll latter=1;

    if(size == 1){
        cout << K / 2 << endl;
    }

    else{

    rep(i,size-1){

        if(jud){
            jud = false;
            continue;
        }

        if(S[i]==S[i+1]){
            jud = true;
            ans++;
        }
    }

    if(K == 1){
        cout << ans << endl;
    }

    else{

    if(S[0]!=S[size-1]){
        cout << ans * K << endl;
    }

    else{
        rep(i,size-1){
            if(S[i] != S[i+1]){
                break;
            }
            former++;
        }
        for(ll i=size-1; i>=0; i--){
            if(S[i] != S[i-1]){
                break;
            }
            latter++;
        }

        if(former == size){
            cout << (size*K)/2 << endl;
        }

        else{

        ans = ans - former/2 - latter/2;

        cout << ans * K + former/2 + latter/2 + (former + latter)/2 * (K-1) << endl;
        }

    }
    }
    }
}


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

#define NREP() for(ll i = 0; i < n; i++)
#define MREP() for(ll j = 0; j < m; j++)
#define REP(i, n) for(ll i = 0; i < n; i++)
#define ALL(x) (x).begin(), (x).end()
#define MSG(x) cout << x << endl;
#define IPT(t, x) t ipt; cin >> ipt; x.push_back(ipt);
#define YN(x) x ? cout << "YES" << endl : cout << "NO" << endl;
#define Yn(x) x ? cout << "Yes" << endl : cout << "No" << endl;
#define yn(x) x ? cout << "yes" << endl : cout << "no" << endl;

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<vector<ll>> vvl;
typedef vector<string> vs;
typedef vector<vector<string>> vvs;

const static ll MOD = 1e9 + 7;
ll n, cnt, ans, tmp, sum, a, b, c, d, k, m, h, w, q, x, y;
string s, t;

int main() {
    cin >> s;
    set<char> st;

    REP(i, s.size()) {
        if (st.count(s[i]) == 0) {
            st.insert(s[i]);
        } else {
            MSG("no")
            exit(0);
        }
    }

    MSG("yes")
}


Measured memory_bytes: 256
package main

import "fmt"

func main() {
	var a, b string
	fmt.Scan(&a, &b)

	if a[0] == b[2] && a[1] == b[1] && a[2] == b[0] {
		fmt.Println("YES")
	} else {
		fmt.Println("NO")
	}
}


Measured memory_bytes: 512
char r[21],q[11];main(n,z){scanf("%s%d",q,&n);for(z=0;n;n--){scanf("%s",r);r[strlen(r)*2]=0;memcpy(r+strlen(r),r,strlen(r));if(strstr(r,q))z++;}printf("%d\n",z);exit(0);}

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

using namespace std;
using P = pair<long, long>;

typedef long long int ll;

#define EPS (1e-7)
#define INF (1e18)
#define PI (acos(-1))

#define sortv(xs) sort(xs.begin(), xs.end())
#define sortvinv(xs) sort(xs.begin(), xs.end(), greater<long>())
#define lbv(xs, x) lower_bound(xs.begin(), xs.end(), x) - xs.begin()
#define ubv(xs, x) upper_bound(xs.begin(), xs.end(), x) - xs.begin()
#define bs(xs, x) binary_search(xs.begin(), xs.end(), x)
#define index_of(as, x) \
  distance(as.begin(), lower_bound(as.begin(), as.end(), x))
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define concat(xs, ys) (xs).insert((xs).end(), (ys).begin(), (ys).end())

const int mod = 1000000007;

struct mint {
    ll x;
    mint(ll x=0):x(x%mod){}

    mint& operator+=(const mint a) {
        if((x += a.x) >= mod) x -= mod;
        return *this;
    }

    mint& operator-=(const mint a) {
        if (x < a.x) {
          x += mod;
        }
        x -= a.x;
        return *this;
    }

    mint& operator*=(const mint a) {
        x = (x * a.x) % mod;
        return *this;
    }

    mint& operator/=(const mint a) {
        *this *= a.inv();
        return *this;
    }

    mint operator+(const mint a) const {
        mint res(*this);
        return res += a;
    }

    mint operator-(const mint a) const {
        mint res(*this);
        return res -= a;
    }

    mint operator*(const mint a) const {
        mint res(*this);
        return res *= a;
    }

    mint operator/(const mint a) const {
        mint res(*this);
        return res /= a;
    }

    mint pow(ll n) const {
        mint a(*this);
        mint res = 1;
        while (n > 0) {
            if (n & 1) res *= a;
            a *= a;
            n >>= 1;
        }
        return res;
    }

    mint inv() const {
        return pow(mod - 2);
    }
};

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

  int a, b;
  cin >> a >> b;

  
  cout << 6-a-b << endl;
}


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

using ll = long long;
const int mod = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    double L;
    scanf("%lf", &L);
    printf("%.15lf\n", pow(L / 3, 3));
}

Measured memory_bytes: 256
def my_match s,t
  
  sl = s.length
  sl.times do |i|
    return false if s[i] != ?? and s[i] != t[i]
  end
  return true
end

def solve sp,t
  
  s = sp
  sl = s.length
  tl = t.length
  
  no = "UNRESTORABLE"
  return no if sl < tl
  
  if sp.include?(t)
    k = sp.index(t)
    s[k, tl] = t
    return s.gsub(??, ?a)
  end
  
  k = sl - tl
  anss = []
  k.downto(0) do |i|
    if my_match(sp[i,tl],t)
      tmp = String.new(sp)
      tmp[i,tl] = t
      anss << tmp.gsub(??, ?a)
    end
  end
  
  return anss.sort[0] if anss.size != 0 
  
  return no
end

sp = gets.chomp
t = gets.chomp

puts solve sp,t


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define     fast                    ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define     ll                      long long
#define     pb                      push_back
#define     M                       1000000007
using namespace std;
int main()
{
    ll n,x,sum=0;
    cin>>n;
    if(n<1200) cout<<"ABC"<<endl;
    else if(n<2800) cout<<"ARC"<<endl;
    else cout<<"AGC"<<endl;

}


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

using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef pair<ll, ll> LP;

const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1000000000000000000L;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int ddx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int extgcd(int a, int b, int& x, int&y) {
    int d = a;
    if(b != 0) {
        d = extgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }else {
        x = 1;
        y = 0;
    }
    return d;
}

int inv(int a) {
    int x, y;
    extgcd(a, MOD, x, y);
    return (x + MOD) % MOD;
}

ll wx[100], wy[100], r[100];

int main() {
    int a, b;
    cin >> a >> b;
    int cur = 1;
    int ans = 0;
    while(cur < b) {
        cur += a - 1;
        ans++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define mem( f, x ) memset( f, x, sizeof( f ) )
#define INF 0x3f3f3f3f
#define pii pair<int, int>
#define mk( x, y ) make_pair(x, y)
#define pk push_back
#define fi first
#define se second
using namespace std;
const int M = 15;
const int N = 15;
const int MAXN = 15;
const double PI = acos(-1.0);
double a, b, m, n;


int main( ){
    while( scanf( "%lf %lf %lf %lf", &a, &b, &m, &n ) != EOF ){
        double fen = 6*n;
        double shi = 30*m + 0.5*n;
        double dt = fabs( fen-shi );

        printf( "%.20lf\n", sqrt(a*a+b*b-2*a*b*cos(dt/180.0*PI)) );
    }
    return 0;
}


Measured memory_bytes: 4220
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#define N 300005
typedef long long ll;
using namespace std;

ll M = 998244353;
ll n, a, b, k, i, ans=0;
ll inv[N], fac[N], fiv[N];

ll comb(ll p) {
    return fac[n] * fiv[p] % M * fiv[n-p] % M;
}

int main() {
    cin >> n >> a >> b >> k;

    inv[1]=fac[1]=fiv[1]=inv[0]=fac[0]=fiv[0]=1;
    for (i = 2; i <= n; i++) {
        fac[i] = fac[i-1] * i % M;
        inv[i] = inv[M%i] * (M-M/i) % M;
        fiv[i] = fiv[i-1] * inv[i] % M;
    }

    for (i = 0; i <= n; i++) {
        if ((k-i*a) % b == 0 && k >= i*a && (k-i*a)/b <= n) {
            ans += comb(i) * comb((k-i*a)/b) % M;
        }
    }

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

Measured memory_bytes: 7296
N, Q = list(map(int, input().split()))
S = list(str(input()))
questions = [tuple(map(int, input().split())) for _ in range(Q)]
ACs = [0] * N

for i in range(len(S)-1):
    if S[i] == 'A' and S[i + 1] == 'C':
        ACs[i + 1] = ACs[i] + 1
    else:
        ACs[i + 1] = ACs[i]

for q in questions:
    print(ACs[q[1]-1] - ACs[q[0]-1])

Measured memory_bytes: 20472
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N,X;
  cin>>N>>X;
  vector<int>L(N+1);
  L.at(0)=0;
  for(int i=0;i<N;i++){
    int x=0;cin>>x;
    L.at(i+1)=L.at(i)+x;
  }
  int ans=0;
  for(int i=0;i<=N;i++){
    if(L.at(i)<=X){
      ans++;
    }
  }
  cout<<ans<<endl;
}


Measured memory_bytes: 3640
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = 1; i <= (n); ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define bit(n) (1<<(n))
#define fi first
#define se second
#define ii(x) int x; cin >> (x)
#define ii2(x, y) int x, y; cin >> (x) >> (y)
#define ii3(x, y, z) int x, y, z; cin >> (x) >> (y) >> (z)
#define yn(x, ok, ng) cout << ((x)?(ok):(ng)) << endl
using namespace std;
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<bool> vb;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
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;}
ll gcd(ll a, ll b) { return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b) { return a/gcd(a,b)*b;}
int const INF = 1001001001;

vector<int> G[100050];

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

int N,M;
cin >> N >> M;

vi H(N);
rep(i,N) cin >> H[i];
rep(i,M) {
    int a,b;
    cin >> a >> b;
    --a; --b;
    G[a].push_back(b);
    G[b].push_back(a);
}

int ans = 0;
rep(i,N) {
    if(SZ(G[i]) == 0) {
        ans++;
        continue;
    }
    bool ok = true;
    for(auto ni : G[i]) {
        if(H[i] <= H[ni]) ok = false;
    }
    if(ok) ans++;
}

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

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

double aver(double t, double x) {
  return t-x*0.006;
}

int main() {
  
  int n;
  cin >> n;
  double t;
  cin >> t;
  double a;
  cin >> a;
  
  int s;
  double answer=1000;
  for (int i=0; i<n; i++) {
    double h;
    cin >> h;
    if (abs(aver(t, h)-a)<answer) s=i+1;
    answer=min(answer, abs(aver(t, h)-a));
  }
  
  cout << s << endl;
}

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

int a, b, c, d, m , n;

int main () {
	cin >> a >> b >> c >> d;
	m = a * b;
	n = c * d;
	if (m == n){
		cout << m << endl;
	} else if (m > n) {
		cout << m << endl;
	} else {
		cout << n << endl;
	}
}

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

using ll = long long;
using namespace std;

#define rep(i, a) for (int i = 0; (i) < (int) (a); (i)++)
#define reps(i, a, b) for (int i = (int) (a); (i) < (int) (b); (i)++)
#define rrep(i, a) for (int i = (int) a-1; (i) >= 0; (i)--)
#define rreps(i, a, b) for (int i = (int) (a)-1; (i) >= (int) (b); (i)--)
#define MP(a, b) make_pair((a), (b))
#define PB(a) push_back((a))
#define all(v) (v).begin(), (v).end()
#define PERM(v) next_permutation(all(v))
#define UNIQUE(v) sort(all(v));(v).erase(unique(all(v)), v.end())
#define CIN(type, x) type x;cin >> x
#define TRUE__  "Yes"
#define FALSE__ "No"
#define PRINT(f) if((f)){cout << (TRUE__) << endl;}else{cout << FALSE__ << endl;}
#define YES(f) if((f)){cout << "YES" << endl;}else{cout << "NO" << endl;}
#define Yes(f) if((f)){cout << "Yes" << endl;}else{cout << "No" << endl;}
#define MINV(v) min_element(all(v))
#define MAXV(v) max_element(all(v))
#define MIN3(a, b, c) min(min(a, b), c)
#define MIN4(a, b, c, d) min(MIN3(a, b, c), d)
#define MIN5(a, b, c, d, e) min(MIN4(a, b, c, d), e)
#define MIN6(a, b, c, d, e, f) min(MIN5(a, b, c, d, e), f)
#define MAX3(a, b, c) max(max(a, b), c)
#define MAX4(a, b, c, d) max(MAX3(a, b, c), d)
#define MAX5(a, b, c, d, e) max(MAX4(a, b, c, d), e)
#define MAX6(a, b, c, d, e, f) max(MAX5(a, b, c, d, e), f)
#define RANGE(a, b, c) ((a) <= (b) && (b) < (c))
#define RANGE2D(a, b, c, d, e, f) (RANGE((a), (c), (e)) && RANGE((b), (d), (f)))
#define chmin(a, b) a = min(a, (b))
#define chmin3(a, b, c) a = MIN3(a, (b), (c))
#define chmin4(a, b, c, d) a = MIN4(a, (b), (c), (d))
#define chmin5(a, b, c, d, e) a = MIN5(a, (b), (c), (d), (e))
#define chmin6(a, b, c, d, e, f) a = MIN6(a, (b), (c), (d), (e), (f))
#define chmax(a, b) a = max(a, (b))
#define chmax3(a, b, c) a = MAX3(a, (b), (c))
#define chmax4(a, b, c, d) a = MAX4(a, (b), (c), (d))
#define chmax5(a, b, c, d, e) a = MAX5(a, (b), (c), (d), (e))
#define chmax6(a, b, c, d, e, f) a = MAX6(a, (b), (c), (d), (e), (f))
#define fcout cout << fixed << setprecision(12)

#define RS resize
#define CINV(v, N) do {\
	v.RS(N);\
	rep(i, N) cin >> v[i];\
} while (0);

#define RCINV(v, N) do {\
	v.RS(N);\
	rrep(i, N) cin >> v[i];\
} while (0);
#define MOD 1000000007

template<class T>
inline T GET() {
	T x;
	cin >> x;
	return x;
}


void init();
void solve();

signed main()
{
	init();
	solve();
}

int calc(ll a, ll x)
{
	ll k = 1LL << x;
	ll cnt = 0;
	cnt += (a+1) / k * k / 2;
	a = (a+1) % k - k / 2;
	cnt += max(a, 0LL);
	return cnt % 2;
}

void init()
{
	ll A, B;
	cin >> A >> B;
	ll res = 0;
	rep(i, 50) {
		ll t = 1LL << i;
		res += (calc(A-1, i+1) + calc(B, i+1)) % 2 * t;
	}
	cout << res << endl;
}

void solve()
{
}




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

int main(){
            int n;cin >>n;vector<int> h(n);
  rep(i,n)cin >> h[i];
  
  int ans=0;
 h.push_back(0);
  
      for(int i=0;i<100;i++){
        rep(j,n){
          if(h[j]>i&&h[j+1]<=i)ans++;}
      }
  cout <<ans<<endl;}


Measured memory_bytes: 256
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <iomanip>
#include <queue>
#include <deque>
#include <map>
#include <unordered_map>
#define rep(i,n) for(int i=0;i<n;i++)
#define repn(i,n) for(int i=1;i<=n;i++)
#define repr(e,x) for(auto& e:x)
using namespace std;
typedef long long ll;
typedef long double ld;

ll D;
ll c[26+1];
ll s[365+1][26+1];

ll last[365+1];

int main(){
    cin>>D;
    repn(i,26) cin>>c[i];
    repn(i,D) repn(j,26) cin>>s[i][j];

    //ll v=0;
    repn(d,D){
        ll maxi=0;
        ll k=0;
        repn(i,26){
            if(maxi<=s[d][i]){
                maxi=s[d][i];
                k=i;
            }
        }
        //cout<<idx<<':'<<maxi<<endl;
        //v+=maxi;
        //last[k]=d;
        //repn(i,26) v-=c[i]*(d-last[i]);
        cout<<k<<endl;
    }
}

Measured memory_bytes: 3712
#include <bits/stdc++.h>
#define rep(i, l, r) for(register int i = l; i < r; i++)
#define hrp(i, l, r) for(register int i = l; i <= r; i++)
#define rev(i, r, l) for(register int i = r; i >= l; i--)
#define ms(n, t) memset(n, t, sizeof(n))
#define U 10050
#define pb push_back
#define int ll
#ifndef JOEON
#define D(...)
#define R(x, l)
#define sp
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
template<typename tn> inline tn next(void);
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v);
signed main(void)
{
	#ifdef JOEON
//		freopen("C:\\Users\\Joeon\\Desktop\\IN.txt", "r", stdin);
//		freopen("C:\\Users\\Joeon\\Desktop\\OUT.txt", "w", stdout);
	#endif
	ios::sync_with_stdio(false);
	cin.tie(0);
	int a, b, c, d, e;
	cin>>a>>b>>c>>d>>e;
	if (b == d)
	{
		if (a == c) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
		return 0;
	}
	if (0 <= 1.0*abs(a-c)/(b-d) && 1.0*abs(a-c)/(b-d) <= e) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}
template<typename tn> inline tn next(void)
{
	tn k;
	cin>>k;
	return k;
}
template<typename tn> inline ostream& operator << (ostream& os, const vector<tn>& v)
{
	rep(i, 0, v.size()) os<<v[i]<<' ';
	return os;
}


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

int main(){
    long long int N;
    long long int ans = 0;
    vector<long long int> A;
    cin >> N;
    for(int i = 0; i < N; i++){
        long long int temp;
        cin >> temp;
        A.push_back(temp);
    }
    while(true){
        for(int i = 0; i < N; i++){
            if(A[i] % 2 == 0){
                A[i] /= 2;
            } else {
                cout << ans << endl;
                return 0;
            }
        }
        ans++;
    }
    return 0;
}

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

void solve()
{
    int X;
    cin >> X;
    string ans = (X>=30)?"Yes":"No";
    cout << ans << endl;
}

int main()
{
    cin.tie();
    ios::sync_with_stdio(false);
    // int ti = clock();
    // input();
    solve();
    // printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
    return 0;
}

Measured memory_bytes: 3584
#include <bits/stdc++.h>
#define ull unsigned long long int
#define ll long long int
#define LL_MAX 9223372036854775807
#define pb push_back
#define pf push_front
#define mp make_pair
#define popb pop_back
#define vl vector<ll>
#define bs(v, x) binary_search(v.begin(), v.end(), x)
#define popf pop_front
#define p() cout << '\n'
#define p0(x) cout << x << " "
#define p1(x) cout << x << '\n'
#define p2(x, y) cout << x << " " << y << '\n'
#define p3(x, y, z) cout << x << " " << y << " " << z << '\n'
#define printv(v)                   \
  for (ll i = 0; i < v.size(); ++i) \
    cout << v[i] << " ";            \
  cout << '\n'
#define pr1(x) cout << fixed << setprecision(15) << x << '\n'
#define mod 1000000007
#define mod1 998244353
#define fio                         \
  ios_base::sync_with_stdio(false); \
  cin.tie(NULL)
#define get(n) \
  ll n;        \
  cin >> n
#define getvec(v, n)         \
  vector<ll> v(n);           \
  for (ll i = 0; i < n; i++) \
    cin >> v[i];
#define getstr(s) \
  string s;       \
  cin >> s
#define all(x) x.begin(), x.end()
#define countBits(x) __builtin_popcount(x)
using namespace std;

void mainSolve()
{
  getstr(s);
  ll sum = 0;
  int n = s.length();
  for (int i = 0; i < n; i++)
  {
    sum += (s[i] - '0');
  }
  p1((sum % 9 == 0 ? "Yes" : "No"));
}

int main()
{
  fio;
#ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
  //get(t);
  ll t = 1;
  while (t--)
  {
    mainSolve();
  }
  return 0;
}


Measured memory_bytes: 3780
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        int count = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int k = 0; k < n; k++) {
            int a = sc.nextInt();

            // 2は素数。後続処理を簡素化するために個別に処理をする
            if (a == 2) {
                count++;
                continue;
            }

            // 2以外の偶数は素数ではないので飛ばす
            if ((a % 2) == 0) continue;

            // 奇数だけ判定する
            // エラトステネスの篩を利用
            int sqrt = (int) Math.sqrt(a);
            boolean isBreak = false;
            for (int i = 3; i <= sqrt; i += 2) {
                if ((a % i) == 0) {
                    isBreak = true;
                    break;
                }
            }
            if (!isBreak) {
                count++;
            }
        }
        System.out.println(count);
        sc.close();
    }
}



Measured memory_bytes: 40872
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
print(-(-N//K) - (N//K))

Measured memory_bytes: 5332
import java.util.Scanner;

public class Main {
	
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int K = sc.nextInt();
        
        int[] dp = new int[N+1];
        dp[0] = 1;
        for (int i = 1; i <= N; i++) {
        	dp[i] = Math.min(dp[i-1] * 2, dp[i-1]+K);
        }
        
        System.out.println(dp[N]);
    }
}




Measured memory_bytes: 23764
#include <bits/stdc++.h>
#define INF 100000007
#define rep(i, N) for(ll i = 0; i < N; i++)
#define rep2(i, j, k) for(ll i = j; i < k; i++)
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define chmax(x, y) x = max(x, y)
#define print(x) cout << x << "\n"
#define printv(vec) rep(i, vec.size()) cout << vec[i] << " "
#define ALL(v) v.begin(), v.end()
#define SUM(v) accumulate(ALL(v), 0)
#define MAX(v) *max_element(ALL(v))
#define MIN(v) *min_element(ALL(v))
#define SORT(v) sort(ALL(v))
#define REV(v) reverse(ALL(v))
typedef long long ll;
using namespace std;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vs = vector<string>;
using vvs = vector<vector<string>>;

void solve(){
	
	ll H, W, ch, cw, dh, dw;
	cin >> H >> W;
	cin >> ch >> cw;
	cin >> dh >> dw;
	vs S(H);
	rep(i, H) cin >> S[i];
	ll dir[] = {1, 0, -1, 0, 1};
	
	deque<pair<ll, ll>> q;
	vector<vector<ll>> dp(H, vector<ll>(W, INF));
	dp[ch - 1][cw - 1] = 0;
	q.push_back({ch - 1, cw - 1});
	ll x, y, nx, ny;

	while(!q.empty()){

		x = q.front().first;
		y = q.front().second;
		q.pop_front();
		
		rep2(i, -2, 3){
			rep2(j, -2, 3){
				nx = x + i;
				ny = y + j;
				if(ny < 0 || nx < 0 || nx >= H || ny >= W) continue;
				if(S[nx][ny] == '#') continue;
				if(dp[nx][ny] > dp[x][y] + 1){
					dp[nx][ny] = dp[x][y] + 1;
					q.push_back({nx, ny});
				}
			}
		}
		
		rep(i, 4){
			ny = y + dir[i];
			nx = x + dir[i + 1];
			if(ny < 0 || nx < 0 || nx >= H || ny >= W) continue;
			if(S[nx][ny] == '#') continue;
			if(dp[nx][ny] > dp[x][y]) {
				dp[nx][ny] = dp[x][y];
				q.push_front({nx, ny});
			}
		}
		
	}

	ll ans = dp[dh - 1][dw - 1];
	if(ans == INF) print(-1);
	else print(ans);	
}	

int main(){
	
	fastio;
	solve();
    
	return 0;
	
}


Measured memory_bytes: 12688
#include <iostream>
#include <vector>
#define FASTIO ios_base::sync_with_stdio (0);cin.tie (0);cout.tie (0);
#define INF 1e9 + 5

using namespace std;

int get_first_negative (vector<int>& vt) {
    int low = 0, high = vt.size () - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (vt[mid] < 0 && vt[max (mid - 1, 0)] >= 0) {
            return mid;
        } else if (vt[mid] >= 0) {
            low = mid + 1;
        } else if (vt[max (mid - 1, 0)] < 0) {
            high = mid - 1;
        }
    }
    return -1;
}

int get_first_zero (vector<int>& vt) {
    int low = 0, high = vt.size () - 1;
    while (low <= high) {
        int mid = (low + high) / 2;
        if (vt[mid] == 0 && vt[max (mid - 1, 0)]  == 1) {
            return mid;
        } else if (vt[mid] == 1) {
            low = mid + 1;
        } else if (vt[mid] == 0) {
            high = mid - 1;
        }
    }
    return -1;
}

int min_jumps (vector<int>& stones, int n, int k) {
    vector<int> dp(n, INF);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 1; j <= k; ++j) {
            dp[min (i + j, n - 1)] = min (dp[min (i + j, n - 1)], dp[i] + abs (stones[i] - stones[min (i + j, n - 1)]));
        }
    }
    return dp[n - 1];
}

int main () {
    FASTIO
    int n, k;
    cin >> n;
    cin >> k;
    vector<int> vt (n);
    for (int &elem: vt) {
        cin >> elem;
    }
    cout << min_jumps (vt, vt.size (), k);
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <iomanip>
#include <cmath>
#include <functional>
#include <algorithm>
#include <numeric>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <boost/range/irange.hpp>
#include <boost/container/static_vector.hpp>
#include <boost/utility/string_ref.hpp>

template <class Integer>
auto boost_irange(Integer last) { return boost::irange(static_cast<Integer>(0), last); }
template <class Integer>
auto boost_irange(Integer first, Integer last) { return boost::irange(first, last); }

class input
{
    std::istream& cin;

public:
    input() : cin(std::cin)
    {
        std::cin.tie(nullptr);
        std::ios::sync_with_stdio(false);
    }

    template <class T>
    inline input& operator>>(T& var)
    {
        cin >> var;
        return *this;
    }
    template <class T>
    inline input& operator,(T& var)
    {
        cin >> var;
        return *this;
    }

    template <class T>
    inline T read()
    {
        T var;
        cin >> var;
        return var;
    }

    template <class InputIterator>
    inline void read(InputIterator head, std::size_t n)
    {
        for (std::size_t i = 0; i < n; ++i) {
            cin >> *head;
            ++head;
        }
    }

    template <class T, class F>
    inline void online(std::size_t n, F&& f)
    {
        T var;
        for (std::size_t i = 0; i < n; ++i) {
            cin >> var;
            f(var);
        }
    }
};
template <class T, std::size_t n>
std::istream& operator>>(std::istream& in, std::array<T, n>& var)
{
    for (std::size_t i = 0; i < n; ++i) {
        in >> var[i];
    }
    return in;
}

class output
{
    std::ostream& cout;

public:
    class proxy
    {
        std::ostream& cout;

    public:
        proxy() : cout(std::cout) {}
        ~proxy() { cout << '\n'; }
        template <class T>
        proxy& operator,(T&& val)
        {
            cout << ' ' << val;
            return *this;
        }
    };

public:
    output() : cout(std::cout)
    {
        cout << std::fixed << std::setprecision(15);
    }

    template <class T>
    proxy operator<<(T&& val)
    {
        cout << val;
        return {};
    }
};

int main()
{
    input in;
    output out;

    int K, X;
    in >> K, X;

    for (int i = X - K + 1; i < X + K; ++i) {
        std::cout << i << " ";
    }

    return 0;
}


Measured memory_bytes: 256
import sys
import heapq
sys.setrecursionlimit(100002)
input=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(n):
  a[i]=-a[i]
heapq.heapify(a)
for i in range(m):
  heapq.heappushpop(a,-(-a[0]//2))
print(-sum(a))


Measured memory_bytes: 14204
n = int(input())
xl = [list(map(int, input().split())) for _ in range(n)]

distances = sorted([[x + l, x - l] for x, l in xl])

ans = 0
t = -float('inf')
for i in range(len(distances)):
    if t <= distances[i][1]:
        ans += 1
        t = distances[i][0]

print(ans)


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

   typedef long long ll;
   typedef pair<ll, ll> Pii;

   const double EPS = (1e-7);
   const ll INF =(1e13);
   const double PI = (acos(-1));
   const ll MOD = ll(1e9) + 7;

   #define REP(i, n) for(ll i = 0; i < (ll)(n); i++)
   #define REPR(i, n) for(ll i = n; i > -1; i--)
   #define FOR(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++)
   #define ALL(x) (x).begin(),(x).end()
   #define SORT(x) sort((x).begin(), (x).end())
   #define REVERSE(x) reverse((x).begin(), (x).end())
   #define SZ(x) ((ll)(x).size())
   #define pb push_back
   #define mp make_pair


   //chmax(a, b): a>bならaをbで更新　更新したときにtrueを返す
   //chmin(a, b): a<bならaをbで更新　更新したときにtrueを返す
   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; }

   #define dump(x) cerr<< #x << "= " << (x) << endl;

   ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
   ll pow(ll a, ll b){if (b == 0) return 1; else if (b % 2 == 0) return pow(a * a, b / 2); else return pow(a * a, b / 2) * a;}


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

const ll MAX_Klen = 1e5 + 1, MAX_D = 100;
string K;
ll K_len;
ll D;
ll dp[MAX_Klen + 1][MAX_D][2] = {};

inline ll mod(ll a, ll m){
  return ((a % m) + m) % m;
}

ll digit_dp(ll i = 0, ll x = 0, bool flag = true){
  if (dp[i][x][flag] >= 0) return dp[i][x][flag];
  else if (i == K_len){
    dp[i][x][flag] = (x == 0);
    return (x == 0);
  }
  else{
    ll ans = 0;
    if (flag){
      REP(k, K[i] - '0'){
        ans += digit_dp(i + 1, mod(x - k, D), false);
        ans %= MOD;
      }
      ans += digit_dp(i + 1, mod(x - (K[i] - '0'), D) , true);
      ans %= MOD;
    }
    else{
      REP(k, 10){
        ans += digit_dp(i + 1, mod(x - k, D), false);
        ans %= MOD;
      }
    }
    ans %= MOD;
    dp[i][x][flag] = ans;
    return ans;
  }
}
int main(){
  cin >> K >> D;
  K_len = K.size();
  REP(i, K_len + 1){
    REP(x, D){
      dp[i][x][true] = -1, dp[i][x][false] = -1;
    }
  }
  cout << mod(digit_dp() - 1, MOD)<< endl;
}


Measured memory_bytes: 17536
import java.util.*;
public class Main
{
  public static void main(String[] args)
  {
    Scanner sc=new Scanner(System.in);
    int n=sc.nextInt();
    int k=sc.nextInt();
    HashSet<Integer> h=new HashSet<Integer>();
    for(int j=1;j<=k;j++)
      h.add(sc.nextInt());
    while(!comp(n,h))n++;
    System.out.println(n);
  }
  public static boolean comp(int k,HashSet<Integer> h)
  {
    String s=Integer.toString(k);
    for(int i=0;i<s.length();i++)
    {
      int o=s.charAt(i)-'0';
      if(h.contains(o))
        return false;
    }
    return true;}}


Measured memory_bytes: 25044
#include <iostream>
#include <string>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <list>
#include <iomanip>
#include <vector>
#include <functional>
#include <algorithm>
#include <cstdio>
#include <random>
#include <ctime>
#include <cstdlib>
#include <unordered_map>
#include <string.h>
#include <iostream>

using namespace std;
typedef long long ll;
typedef pair<int, int> Pint;
typedef pair<ll, ll> Pll;
#define rep(begin, i, end) for (ll i = begin; i < (ll)(end); i++)
#define all(v) v.begin(), v.end()
const int MOD = 1000000007;

int main()
{
    string s;
    cin >> s;
    int N = s.size();
    rep(0, i, 8)
    {
        string sub1 = s.substr(0, i);
        string sub2 = s.substr(N + i - 7, 7 - i);
        if (sub1 + sub2 == "keyence")
        {
            cout << "YES" << endl;
            return 0;
        }
    }
    cout << "NO" << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define yes cout << "yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl
#define no cout << "no" << endl

const int INF = 1001001001;
const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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

int main() {
  int n, a, b;
  cin >> n >> a >> b;
  int ans = 0;
  int tmp;
  int sum;
  rep (i, n + 1) {
    string s = to_string(i);
    int sum  = 0;
    rep (j, s.size()) {
      sum += (s[j] - '0');
    }
    if (sum >= a && sum <= b) {
      // P(i);
      ans += i;
    }
  }
  P(ans);
  return 0;
}



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

int main(){
	int n,i,a,b,c;
  std::cin>>a;
  for(n=0,i=100000;a>n;++n){
	  i=i+i/20;
	  if(i%1000!=0){
		  b=i%1000;
		  i=i+1000-b;
		}
	}
  std::cout<<i<<std::endl;
	return 0;
	}

Measured memory_bytes: 1160
import sys
i=input
n = int(i())
r0 = int(i())
r1 = int(i())
x = r1-r0
y = min(r1,r0)
for i in map(int,sys.stdin.readlines()):
    a=i-y
    if x<a:
        x=a
        if 0>a:y=i
    elif y>i:y=i
print(x)

Measured memory_bytes: 19836
N = int(input())
S = input()
for i in range(N):
    if i == 0:
        num = S[i + 1:].count("E")
        num_min = num
    else:
        if S[i - 1] == "W":
            num += 1
        if S[i] == "E":
            num -= 1
        if num < num_min:
            num_min = num
print(num_min)

Measured memory_bytes: 3676
//By Ralif Rakhmatullin
#include<iostream>
#include<fstream>
#include<string>
#include<cstring>
#include<math.h>
#include<cassert>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<map>
#include<ctime>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<bitset>
#include<valarray>
#include<iterator>
#include<list>
#define ll long long
#define ull unsigned long long
#define mp make_pair
#define S second
#define ld long double
#define F first
#define y1 LOL
#define ld long double
#define pb push_back
#define len length
#define sz size
#define beg begin
const ll INF = (ll)1e18 + 123;
const int inf=(int)2e9 + 123; 
const int mod=1e9+7;
using namespace std;
int n, root;
vector<int> g[100011];
ll a[100011], p[100011];
void out(){
	cout << "NO";
	exit(0);
}
void dfs(int v = root, int par = -1){
	if((int)g[v].sz() == 1){
		p[v] = a[v];
		return;
	}
	ll sum = 0;
	for(auto to : g[v]){
		if(to == par)
			continue;
		dfs(to, v);
		sum += p[to];
	} 
	if(v == root){
		if(sum != a[v] * 2){
			out();
		}
		return;
	}
	if(sum > a[v] * 2)
		out();
	p[v] = a[v] * 2 - sum;
}
void check(int v = root, int par = -1){
	ll sum = p[v];
//	cerr << v << " ";
	if((int)g[v].sz() == 1)
		return;
	for(auto to : g[v]){
		if(to == par)
			continue;
		sum += p[to];
		check(to, v);
	}
	if(p[v] > sum / 2 || sum != a[v] * 2)
		out();
	for(auto to : g[v])
		if(to != par)	
			if(p[to] > sum / 2)
				out();
}
int main(){
	unsigned int FOR;
 	asm("rdtsc" : "=A"(FOR));
  	srand(FOR);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	cin >> n;
	for(int i = 1; i <= n; i ++)
		cin >> a[i];
	for(int i = 1; i < n; i ++){
		int x, y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	if(n == 2){
		if(a[1] != a[2])
			cout << "NO";
		else
			cout << "YES";
		return 0;
	}
	for(int i = 1; i <= n; i ++){
		if((int)g[i].sz() > 1)
			root = i;
	}
	dfs();
	check();
	cout << "YES";
	return 0;
}

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

int main()
{
  long long t1,t2;cin>>t1>>t2;
  long long a1,a2;cin>>a1>>a2;
  long long b1,b2;cin>>b1>>b2;
  long long a1g=(a1-min(a1,b1))*t1;
  long long a2g=(a2-min(a2,b2))*t2;
  long long b1g=(b1-min(a1,b1))*t1;
  long long b2g=(b2-min(a2,b2))*t2;
  if(a1g==0&&a2g==0||b1g==0&&b2g==0)cout<<0<<endl;
  else
  {
    long long p1=a1g+b1g;
    long long p2=a2g+b2g;
    if(p1==p2)cout<<"infinity"<<endl;
    else if(p1>p2)cout<<0<<endl;
    else
    {
      long long p=p1/(p2-p1);
      long long ans=p*2+1;
      if(p1%(p2-p1)==0)ans--;
      cout<<ans<<endl;
    } 
  }
}


Measured memory_bytes: 256