akhauriyash/Code-Regression huggingface dataset:
[N,K] = list(map(int,input().split()))
[R,S,P] = list(map(int,input().split()))
T = input()

j_l = "rsp"
kachi = lambda k : j_l[ (j_l.find(T[k]) + 2) % 3 ]#勝つ手を表示する

rireki = []#出した手の履歴
score = [0,0,0] #出した手の回数を記録

for i in range(N): 
  if i-K >= 0: #K番目以降
    if kachi(i) != rireki[i-K]: #K回前の出した手と比べて、被ってない時、勝ち手を出す
      score[ (j_l.find(T[i])+ 2) % 3 ] += 1#出した手をスコアに足す
      rireki.append(kachi(i)) #履歴に出した手を加える
      #print(score)
    else: #引き分けの時
      rireki.append("hikiwake_or_make") #Kこ先の勝ち手ではないものを履歴に加える？
      #print(score)
  else: #K番以前
    score[ (j_l.find(T[i])+ 2) % 3 ] += 1 #勝つ手を出すだけ
    rireki.append(kachi(i)) #履歴に加える
    #print(score) 
tortal_score = R*score[0] + S*score[1] + P*score[2]

#print(rireki)

print(tortal_score)

Measured memory_bytes: 4212
N, H = ( int(i) for i in input().split() )
ka = []
kb = []
for i in range(N):
	a, b = ( int(i) for i in input().split() )
	ka.append(a)
	kb.append(b)
	
kb.sort()
kb.reverse()
ma = max(ka)

hp = H
res = 0
for b in kb:
	if b < ma:
		continue
	hp = hp - b
	res += 1
	if hp <= 0:
		break
else:
	res += (hp + ma - 1)//ma
	
print(res)
		

Measured memory_bytes: 11348
// Charan Sriramula
 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long int ll;
 
const ll lg=22;
const ll N=2e5+5;
const ll M=5e8;
const ll INF=1e18;
const ll mod=1e9+7;
const double PI = 3.14159265358979323846;
 
#define is(n) scanf("%d",&n)
#define io(n) printf("%d\n",n)
#define ls(n) scanf("%lld",&n)
#define lo(n) printf("%lld\n",n)
 
#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define GCD(a,b) __gcd((a),(b))
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcount(x)
#define LCM(a,b) ((a)*(b))/GCD((a),(b))
#define fast ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
template<typename T> T power(T x,T y,ll m){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}
 
inline ll mul(ll a, ll b, ll p){ return (a * 1ll * b) % p; }
inline ll sub(ll a, ll b, ll p){ ll c = a - b; if(c < 0) c += p; return c; }
inline ll add(ll a, ll b, ll p){ ll c = a + b; if(c > p) c -= p; return c; }
 
#define trace1(x)                cerr<<#x<<": "<<x<<endl
#define trace2(x, y)             cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z)          cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d)       cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e)    cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl

ll n,m,a[N],b[N],dp[2005][2005];

ll F(ll i,ll j)
{
    ll res=0;
    if(i==n||j==m){return 0;}
    if(dp[i][j]!=-1){return dp[i][j];}
    if(a[i]==b[j])
    {
        res=add(res,1LL,mod);
        res=add(res,F(i,j+1),mod);
        res=add(res,F(i+1,j),mod);
    }
    else
    {
        res=add(res,F(i,j+1),mod);
        res=add(res,F(i+1,j),mod);
        res=sub(res,F(i+1,j+1),mod);
    }
    return dp[i][j]=res;
}

int main()
{
    cin>>n>>m;
    memset(dp,-1,sizeof(dp));
    for(ll i=0;i<n;i++){cin>>a[i];}
    for(ll i=0;i<m;i++){cin>>b[i];}
    cout<<1+F(0,0)<<endl;
}


Measured memory_bytes: 33152
#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define FIO ios_base::sync_with_stdio(0); cin.tie(0);
#define MOD (1000000007LL)
vector <int> g[200003];
const int N = 200005;
int up[N], down[N], fac[N], inv[N], ways[N], res[N];
int m;
int add(int a, int b, int m){
  if(b < 0) b += m;
  int res = ((a % m) + (b % m)) % m;
  res %= m;
  return res;
}
 
int mul(int a, int b, int m){
  if(b < 0) b += m;
  int res = ((a % m) * (b % m)) % m;
  res %= m;
  return res;
}
 
int sub(int a, int b, int m){
  int res = (a - b + m) % m;
  res %= m;
  return res;
}

int modexp(int x, unsigned int y){
  int res = 1;
  x %= MOD;
  if(!y) return 0;
  while(y > 0){
    if(y & 1) res = mul(res, x, MOD);
    y >>= 1;
    x = mul(x, x, MOD);
  }
  return res;
}

int modularInverse(int a){
  return modexp(a, MOD - 2) % MOD;
}
void fact(){
        fac[0] = 1;
    for(int i = 1; i < N - 1; ++i){
        fac[i] = mul(i, fac[i - 1], MOD);
    }
    inv[0] = 1;
      for(int i = 1; i < N - 1; ++i){
        inv[i] = modularInverse(fac[i]);
    }
}
void dfs1(int x,int p){
    down[x] = 1;
    for (auto u: g[x]){
        if (u == p) continue;
        dfs1(u,x);
        down[x] = mul(down[x],1+down[u],m);
    }
}

void dfs2(int x,int p){
    vector<int> bache;
    for (auto u: g[x]){
        if(u == p) continue;
        bache.push_back(u);
    }
    int sz = bache.size();
    if(sz == 0) return;
    vector<int> pre(sz),suf(sz);
    pre[0] = (1 + down[bache[0]])%m;
    for (int i = 1; i < sz; i++){
        pre[i] = mul(pre[i-1],down[bache[i]]+1,m);
    }
    suf[sz-1] = (1 + down[bache[sz-1]])%m;
    for (int i = sz - 2;i >= 0; i--){
        suf[i] = mul(suf[i+1],down[bache[i]]+1,m);
    }
    
    for (int i = 0;i < sz; i++){
        int temp = 1;
        if(i > 0) temp = mul(temp,pre[i-1],m);
        if(i < sz-1) temp = mul(temp,suf[i+1],m);
        up[bache[i]] = (1 + mul(up[x],temp,m)) % m;
    } 
    for(auto u: g[x]){
        if(u == p) continue;
        dfs2(u,x);
    }
    
} 

int32_t main(){
    FIO
    int n;
    cin >> n >> m;

    for (int i = 1; i < n; i++){
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs1(1,-1);
    up[1] = 1;
    dfs2(1,-1);
    for (int i = 1; i <= n; i++) cout << (down[i] * up[i]) % m << '\n'; 
    }

Measured memory_bytes: 29440
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>

static const int MOD = 998244353;
using ll = int64_t;
using u32 = uint32_t;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

template <class T, class U>
vector<T> make_v(U size, const T& init){ return vector<T>(static_cast<size_t>(size), init); }

template<class... Ts, class U>
auto make_v(U size, Ts... rest) { return vector<decltype(make_v(rest...))>(static_cast<size_t>(size), make_v(rest...)); }

int main() {
    string s;
    cin >> s;
    int n = static_cast<int>(s.size());
    array<int, 3> cnt{}; int p = 0;
    for (int i = 0; i < n; ++i) {
        cnt[s[i]-'a']++;
        if(i && (s[i] == s[i-1])) p++;
    }
    if((cnt[0] == 0) + (cnt[1] == 0)+(cnt[2] == 0) == 2){
        puts("1");
        return 0;
    }else if(s.size() == 3){
        stack<string> q;
        map<string, int> m;
        q.emplace(s);
        while(!q.empty()){
            string w = q.top(); q.pop();
            m[w]++;
            for (int i = 0; i < 2; ++i) {
                if(w[i] != w[i+1]){
                    for (int j = 0; j < 3; ++j) {
                        if(w[i] != 'a'+j && w[i+1] != 'a'+j) {
                            string t = w;
                            t[i] = t[i+1] = static_cast<char>('a'+j);
                            if(!m[t]) q.emplace(t);
                        }
                    }
                }
            }
        }
        cout << m.size() << "\n";
        return 0;
    }
    auto dp = make_v(n+1, 3, 3, 2, 0);
    for (int i = 0; i < 3; ++i) dp[1][i][i][0] = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            for (int k = 0; k < 3; ++k) {
                for (int l = 0; l < 3; ++l) {
                    (dp[i+1][(j+l)%3][l][k == l] += dp[i][j][k][0]) %= MOD;
                    (dp[i+1][(j+l)%3][l][1] += dp[i][j][k][1]) %= MOD;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < 3; ++i) {
        (ans += dp[n][(cnt[1]+cnt[2]*2)%3][i][1]) %= MOD;
    }
    cout << ans + (p == 0) << "\n";
    return 0;
}


Measured memory_bytes: 123908
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
ll cou, w;
int main(void){
    // Your code here!
    string s;
    cin >> s;
    for (int i = 0; i < s.length(); i++){
        if (s[i] == 'W'){
            w++;
            cou += i;
        }
    }
    cout << cou - (w - 1) * (w) / 2 << endl;
}


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

int main(){
  int n;
  cin>>n;
  int sum=0;
  for(int i=0;i<10;i++){
    sum+=(n/(int)pow(10,i))%10;
  }
  if(n%sum==0)cout<<"Yes";
  else cout<<"No";
}

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

#define R0 register
#define iL inline
#define ll long long

#define gc getchar
#define pc putchar
#define sp pc(' ')
#define ln pc('\n')

template <class t>
iL void read(t &x) {
    R0 bool f = 0;
    R0 char c = gc();
    while ((c < '0' || c > '9') && c != '-') c = gc();
    if (c == '-') f = 1, c = gc();
    x = 0;
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ '0'), c = gc();
    f && (x = -x);
}

template <class t>
iL void print(t x) {
    if (x < 0) pc('-'), x = -x;
    if (x >= 10) print(x / 10);
    pc((x % 10) ^ '0');
}

template <class t>
iL t min(t a, t b) {
    return a < b ? a : b;
}

template <class t>
iL t max(t a, t b) {
    return a < b ? b : a;
}

template <class t>
iL void swap(t &a, t &b) { a ^= b ^= a ^= b; }

template <class t>
iL t lowbit(t x) { return x & -x; }

#define ex(a) print(a), ln, exit(0)

const int N = 100005, mod = 998244353;

ll qpow(ll base, int tms) {
    ll rtn = 1;
    while (tms) {
        if (tms & 1) rtn = (rtn * base) % mod;
        base = (base * base) % mod;
        tms >>= 1;
    }
    return rtn;
}

int n, m, d[N], c[N];
ll ans = 1;

int main() {
    read(n);
    for (R0 int i = 1; i <= n; ++i) read(d[i]), c[d[i]]++, m = max(m, d[i]);
    if (d[1] != 0 || c[0] != 1) ex(0);
    for (R0 int i = 1; i <= m; ++i) ans = (ans * qpow(c[i - 1], c[i])) % mod;
    print(ans), ln;
}

Measured memory_bytes: 1024
A,B,K = (int(i) for i in input().split())

takahashi = A
aoki = B

num = 1
while num <= K:
    if takahashi % 2 == 1:
        takahashi = takahashi - 1
    takahashi = int(takahashi / 2)
    aoki = aoki + takahashi
    num = num + 1
    if num > K:
        break
    if aoki % 2 == 1:
        aoki = aoki - 1
    aoki = int(aoki / 2)
    takahashi = takahashi + aoki
    num = num + 1

print(takahashi, aoki)


Measured memory_bytes: 3060
#include<iostream>
using namespace std;
int main()
{

    int n;
    cin>>n;
    int a[n+1];
    int ans=0;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        if(i%2!=0 && a[i]%2!=0)
            ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3628
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush, heapify
import math
import itertools
import random
 
# NO, PAY-PAY
#import numpy as np
#import statistics
#from statistics import mean, median,variance,stdev
 
INF = float('inf')
def inputInt(): return int(input())
def inputMap(): return map(int, input().split())
def inputList(): return list(map(int, input().split()))
 
def main():
    N = inputInt()
    ans = N**3
    print(ans)
    
if __name__ == "__main__":
	main()


Measured memory_bytes: 38896
#include<bits/stdc++.h>
#define ll long long
//#define N 500005
#define inf 1000000005
#define mod 998244353
#define put putchar('\n')
#define F(i,a,b) for (int i=a;i<=b;i++)
#define D(i,a,b) for (int i=a;i>=b;i--)
#define go(i,t) for (int i=head[t];i;i=Next[i])
#define sqr(x) ((x)*(x))
#define re register
#define mp make_pair
#define fi first
#define se second
#define M 10000005
#define pa pair <int,int>
using namespace std;
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void wr(ll x){if (x<0) {putchar('-');wr(-x);return;}if(x>=10)wr(x/10);putchar(x%10+'0');}
inline void wrn(ll x){wr(x);put;}inline void wri(ll x){wr(x);putchar(' ');}
inline void wrn(ll x,ll y){wri(x);wrn(y);}
int n,m;
signed main(){
	n=read();m=read();
	F(i,1,3){
		if ((n*m*i)&1) return puts("Yes"),0;
	}
	puts("No");
	return 0;
}

Measured memory_bytes: 256
// 三井住友信託銀行プログラミングコンテスト2019-D
// 2019.12.1 bal4u

#include <stdio.h>

int N;
char S[30005];
char a[1000];
int n[10], n10[100];

int main()
{
	int i, j, x, ans;
	
	scanf("%d%s", &N, S+1);
	for (i = 1; i <= N; ++i) {
		x = S[i] & 0xf;
		if (!n[x]) n[x] = i;
		for (j = 0; j < 10; ++j) if (n[j] > 0 && n[j] < i && !n10[10*j+x]) {
			n10[10*j+x] = i;
		}
		for (j = 0; j < 100; ++j) if (n10[j] > 0 && n10[j] < i) {
			a[j*10+x] = 1;
		}
	}
	
	ans = 0;
	for (i = 0; i < 1000; ++i) if (a[i]) ++ans;
	printf("%d\n", ans);
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
#define INF INT_MAX
#define ll  long long
#define ull unsigned long long
#define rep(i,n) for(ll i=0; i<n; ++i)
#define FOR(i, s, e) for(ll i=s; i<e; ++i)
#define MOD 1000000007
using namespace std;
template<class T> inline bool chmin(T& a, T b) { if(a>b) {a=b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) { if(a<b) {a=b; return true;} return false;}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll N, H; cin >> N >> H;
  vector<ll> a(N), b(N);
  vector<ll> nageru;
  ll a_max = 0, a_max_idx = 0;
  ll tmp;
  rep(i,N) {
    cin >> a[i] >> b[i];
    if(chmax(a_max, a[i])) a_max_idx = i;
  }
  ll ans = 0;

  rep(i, N) { if(b[i] >= a_max) nageru.push_back(b[i]); }
  sort(nageru.begin(), nageru.end(), greater<ll>());
  for(auto i:nageru) {
    H -= i;
    ++ans;
    if(H <= 0) goto done;
  }

  tmp = H/a_max;
  if(a_max * tmp < H) ++ans;
  ans += H/a_max;

done:
  cout << ans << endl;
}

Measured memory_bytes: 2936
import sys
input=sys.stdin.readline
n = int(input())
l = []
for _ in range(n):
    tmp = list(map(int,input().split()))
    sm = tmp[0] + tmp[1]
    l.append([tmp[0],tmp[1],sm])

l.sort(key=lambda x:x[2])
l.reverse()

t_sm=0
a_sm=0
cnt=0
for dish in l:
    if cnt%2==0:
        t_sm+=dish[0]
    else:
        a_sm+=dish[1]
    cnt+=1
print(t_sm-a_sm)

Measured memory_bytes: 59484
package main

import (
	"fmt"
)

func main() {
	var a, b, c, k int
	fmt.Scanf("%d %d %d %d", &a, &b, &c, &k)

	var sum int = 0
	if k <= a {
		sum = k
	} else if k <= a + b {
		sum = a
	} else {
		sum = a - (k - a - b)
	}
	fmt.Printf("%d", sum)
}


Measured memory_bytes: 1816
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=(0);i<(n);i++)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef long long ll;



int main(){
	ll s;
	int a,b,c,d;
	
	cin>>s;
	a=d=sqrt(s);
	if((ll)a*d<s){
		++a;
		if((ll)a*d<s)
			++d;
	}
	b=1,c=(ll)a*d-s;
	printf("0 0 %d %d %d %d\n",a,b,c,d);

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<(b);i++)
#define debug(x) cout<<#x<<"="<<x<<endl;
#define LL long long 
#define sz(x) x.size()
using namespace std;

int main(void)
{
	LL a,b;
	cin>>a>>b;
	int ans=0;
	while(a<=b)
	{
		ans++;
		a*=2ll;
	}
	cout<<ans;
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		String s = sc.next();
		String ans = "";
		for(int i = 0; i < s.length(); i++) {
			char c = s.charAt(i);
			c += n;
			if(c > 'Z')
				c -= 26;
			ans = ans + c;
		}
		System.out.println(ans);
	}

}


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

using namespace std;

int main() {
    int a,b;
    cin>>a>>b;
    int ans=max(a+b,a-b);
    ans=max(ans,a*b);
    cout<<ans<<endl;
    return 0;
}                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                          

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

int main() {

	int D, N;

	scanf("%d %d", &D, &N);

	if(D == 0) {
		if(N == 100) {
			printf("%d\n", 101);
		} else {
			printf("%d\n", N);
		}
	} else {
		int hoge = (int)pow(100, D);
		if(N == 100) {
			printf("%d\n", hoge * N + hoge);
		} else {
			printf("%d\n", hoge * N);
		}
	}

	return 0;
}

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

signed main() {
  int N;
  cin >> N;
  vector<pair<int, int>> v;
  for (int i = 0; i < N; i++) {
    int x, y;
    cin >> x >> y;
    v.push_back({x, y});
  }

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

  int ans = N;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      int p = v[i].first - v[j].first, q = v[i].second - v[j].second;

      if (p == 0 && q == 0) continue;

      map<pair<int, int>, int> mp;
      for (int a = 0; a < N; a++) mp[v[a]] = 1;

      for (int a = 0; a < N; a++) {
        int x = v[a].first - p, y = v[a].second - q;
        mp[{x, y}] = 0;
      }

      int tmp = 0;
      for (int a = 0; a < N; a++) {
        tmp += mp[v[a]];
      }

      ans = min(ans, tmp);
    }
  }

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define ALL(x) (x).begin(),(x).end() 
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define INF 1000000000
using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int main() {
    int A, B, C = 1+2+3;
    cin >> A >> B;

    cout << C - A - B << endl;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define faster ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define ll long long
#define FO(n) for (ll i = 0; i < n; i++)
#define endl "\n"
const long long int M = 10e9 + 7;
void solve()
{
  string a, b;
  cin >> a >> b;
  ll n = a.length();
  ll n1 = b.length();
  ll ans = 0;
  FO(n)
  {
    ll temp = i;
    ll count = 0;
    ll j = 0;
    while (j < n1 && i < n)
    {
      if (b[j] == a[i])
        count++;
      j++;
      i++;
    }
    i = temp;
    if (j == n1)
      ans = max(ans, count);
  }
  cout << max(0ll, n1 - ans) << endl;
}
int main()
{
  faster;
  //int t;
  //cin >> t;
  //while (t--)
  solve();
  return 0;
}

Measured memory_bytes: 3656
# 入力が10**5とかになったときに100ms程度早い
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


S = input()

from collections import Counter

count = Counter(S)

if count['x'] > 7:
    print('NO')
else:
    print('YES')


Measured memory_bytes: 3436
function main(input) {
  var args = input.split('\n');
  var array = args[0].split(' ')
  var N = parseInt(array[0], 10);
  var K = parseInt(array[1], 10);
    
  console.log(1+Math.ceil((N-K)/(K-1)));
}

main(require('fs').readFileSync('/dev/stdin', 'utf8'));

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

#define REP(i, x, n) for (int i = x; i < (int)(n); i++)
#define rep(i, n) REP(i, 0, n)
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define sz(x) (int)(x.size())
#define popcount(x) __builtin_popcount(x)
#define popcountll(x) __builtin_popcountll(x)
#define uniq(x) x.erase(unique(x.begin(), x.end()), x.end())
#define F first
#define S second
#define mp make_pair
#define eb emplace_back
#define pii pair<int, int>
#define pll pair<ll, ll>

using namespace std;

typedef long long ll;

/* --- INFやMODの値が適切か確認する --- */
// const int INF = 1 << 30;
// const ll INF = 1LL << 60;
// const ll MOD = 1000000007;

int f(int v) {
  int res = 0;
  while (v) {
    res += v % 10;
    v /= 10;
  }
  return res;
}

int main() {
  int n;
  cin >> n;
  int ans = 1000000000;
  REP(i, 1, n) {
    int j = n - i;
    ans = min(ans, f(i) + f(j));
  }
  cout << ans << endl;
}


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

using namespace std;

#define FOR(i, a, b) for(ll i = (a); i < (b); ++i)
#define FORR(i, a, b) for(ll i = (a); i > (b); --i)
#define REP(i, n) for(ll i = 0; i < (n); ++i)
#define REPR(i, n) for(ll i = n; i >= 0; i--)
#define FOREACH(x, a) for(auto &(x) : (a))
#define VECCIN(x)                                                              \
    for(auto &youso_ : (x)) cin >> youso_
#define mp make_pair
#define bitcnt __builtin_popcount
#define SZ(x) ((ll)(x).size())
#define All(a) (a).begin(), (a).end()
template <typename T = long long> inline T IN() {
    T x;
    cin >> x;
    return (x);
}
inline void CIN() {}
template <class Head, class... Tail>
inline void CIN(Head &&head, Tail &&... tail) {
    cin >> head;
    CIN(move(tail)...);
}
#define CINT(...)                                                              \
    int __VA_ARGS__;                                                           \
    CIN(__VA_ARGS__)
#define LCIN(...)                                                              \
    ll __VA_ARGS__;                                                            \
    CIN(__VA_ARGS__)
#define SCIN(...)                                                              \
    string __VA_ARGS__;                                                        \
    CIN(__VA_ARGS__)
#define Yes(a) cout << (a ? "Yes" : "No") << "\n"
#define YES(a) cout << (a ? "YES" : "NO") << "\n"
#define Printv(v)                                                              \
    FOREACH(x, v) { cout << x << " "; }                                        \
    cout << "\n";

typedef long long ll;
typedef unsigned long long ul;
typedef vector<int> V;
typedef vector<ll> VL;
typedef pair<ll, ll> PL;
typedef priority_queue<ll> PQ;
typedef priority_queue<ll, V, greater<ll>> PQG;

const int INF = 1e9;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;
const ll LINF = 1e18;
const ll dx[] = {1, -1, 0, 0};
const ll dy[] = {0, 0, 1, -1};

ll N;

int main() {
    cin >> N;
    REP(i,9) if(N<=(111*(i+1))){
        cout << 111*(i+1) << "\n";
        break;
    }
}

Measured memory_bytes: 256
#include <iostream>

using namespace std;

int N, x;
int ans[200005];
bool used[200005];

int main(void)
{
	cin >> N >> x;
	if(x == 1 || x == 2*N-1){
		cout << "No" << endl;
		return 0;
	}
	if(N == 2){
		cout << "Yes" << endl;
		cout << 1 << endl << 2 << endl << 3 << endl;
		return 0;
	}
	
	
	if(x != 2){
		ans[N] = x; used[x] = true;
		ans[N-1] = 1; used[1] = true;
		ans[N+1] = 2*N-1; used[2*N-1] = true;
		ans[N+2] = 2; used[2] = true;
	}
	else{
		ans[N] = x; used[x] = true;
		ans[N-1] = 2*N-1; used[2*N-1] = true;
		ans[N+1] = 1; used[1] = true;
		ans[N+2] = 2*N-2; used[2*N-2] = true;
	}
	
	int p = 1;
	for(int i = 1; i <= 2*N-1; i++){
		if(ans[i]) continue;
		while(used[p]) p++;
		ans[i] = p;
		used[p] = true;
	}
	
	cout << "Yes" << endl;
	for(int i = 1; i <= 2*N-1; i++) cout << ans[i] << endl;
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=2e5+5;

int A[N];

int main()
{
	int n; scanf("%d",&n);
	int mx = 0;
	ll res = 0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d", &A[i]);
		res += max(mx - A[i], 0);
		mx = max(mx, A[i]);
	}


	printf("%lld\n", res);
}


Measured memory_bytes: 4604
#include <bits/stdc++.h>
using namespace std;
int main() {
  long long N, answer = 0;
  cin >> N;
  int A[N], B[N], C[N];
  for (int i = 0; i < N; A[i++] *= -1) {
    cin >> A[i];
  }
  sort(A,A+N);
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }
  for (int i = 0; i < N; i++) {
    cin >> C[i];
  }
  sort(C,C+N);
  for (int i = 0; i < N; i++) {
    answer += (N-(upper_bound(A,A+N,-B[i])-A))*(N-(upper_bound(C,C+N,B[i])-C));
  }
  cout << answer;
}

Measured memory_bytes: 4704
T = int(input())
ABCD = [ list(map(int,input().split())) for _ in range(T)]
import fractions

def check(a,b,c,d):
    if b > d or a < b:
        print("No")
        return
    elif c >= b:
        print("Yes")
        return
    def_a = a % b
    a = def_a
    while True:
        a = (a + d) % b
        if a > c:
            print("No")
            return
        g = fractions.gcd(b,d)
        f = (b -a) // g
        if (b - a) % g == 0:
            f -= 1
        if g == 0 or c >= a + f * g:
            print("Yes")
            return
        print("No")
        return

for abcd in ABCD:
    check(abcd[0],abcd[1],abcd[2],abcd[3])


Measured memory_bytes: 5200
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
#define pb push_back
#define ld long double
#define f first
#define s second
#define in insert
#define sz(x) (int)x.size()
#define all(x) (x).begin(), (x).end()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int INF = 1e18 + 5;
const int mod = 1e9 + 7;
const int  N = 2e5 + 314;
const long double pi = 3.1415926535897932384626433832795;
void solve(){
	int l, r, d;
	cin>>l>>r>>d;
	cout<<r/d-(l-1)/d;	
}
signed main(){
	speed;
	int t=1;
	//cin>>t;
	while(t--)solve();
}

Measured memory_bytes: 3648
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <utility>
#include <cmath>
#include <tuple>
#include <queue>
#include <bitset>
#include <set>
#include <map>
#include <list>

using namespace std;

const long long MOD = 1000000007;

template <typename T> class Factorial {
  public:
    vector<T> fact;
    vector<T> factinv;
    Factorial(int N);
    static T bipow(T c, T n);
    static T square(T n);
    T conv(T n, T m) const;
    T perm(T n, T m) const;
};

template <typename T> Factorial<T>::Factorial(int N) : fact(N+1), factinv(N+1) {
  fact[0] = 1;
  for (int i = 1; i < N+1; i++) {
    fact[i] = fact[i-1]*static_cast<T>(i)%MOD;
  }
  factinv[N] = bipow(fact[N], MOD-2);
  for (int i = N; i > 0; i--) {
    factinv[i-1] = factinv[i]*static_cast<T>(i)%MOD;
  }
}

template <typename T> T Factorial<T>::bipow(T c, T n) {
  if (n == 0) {
    return 1;
  } else if(n == 1) {
    return c;
  } else if(n%2 == 0) {
    return square(bipow(c, n/2))%MOD;
  } else {
    return (static_cast<T>(c)*square(bipow(c, (n-1)/2)))%MOD;
  }
}

template <typename T> T Factorial<T>::square(T n) {
  return static_cast<long long>(n)*n%MOD;
}

template <typename T> T Factorial<T>::conv(T n, T m) const {
  if (n < m) {
    return 0;
  }
  return (((static_cast<long long>(fact[n])*factinv[m])%MOD)*factinv[n-m])%MOD;
}

template <typename T> T Factorial<T>::perm(T n, T m) const {
  if (n < m) {
    return 0;
  }
  return (static_cast<long long>(fact[n])*factinv[n-m])%MOD;
  }

void solve(long long X, long long Y){
  if ((X+Y)%3 != 0) {
    cout << 0 << endl;
  } else if ((X+Y)/3 > X || (X+Y)/3 > Y) {
    cout << 0 << endl;
  } else {
    Factorial<long long> f(static_cast<int>(X+Y));
    cout << f.conv((X+Y)/3, X - (X+Y)/3) << endl;
  }
}

int main(){
  long long X;
  scanf("%lld",&X);
  long long Y;
  scanf("%lld",&Y);
  solve(X, Y);
  return 0;
}


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

int main() {
	int m,d;
	int d10,d1;
	int ans = 0;
	cin >> m >> d;
	for(int i=4; i<=m; i++){
		for(int j=22; j<=d; j++){
			d10 = j / 10;
			d1 = j - d10 * 10;
			if(d10 > 1 && d1 > 1){
				if(d10 * d1 == i){
					ans += 1;
				}
			}
		}
	}
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int main(void){
	char d[3][4];
	cin>>d[0]>>d[1];
	if(d[0][0]==d[1][2]&&d[0][1]==d[1][1]&&d[0][2]==d[1][0]) cout<<"YES"<<endl;
	else cout<<"NO"<<endl;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
//#include <string>
//#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

vector<vector<LL>> ab(10);
vector<LL> color(10, 0);
LL n;
LL ans=0;
LL depth;

void dfs(LL s){
    //cout << s+1 << " " << depth << endl;
    if(depth==n){
        ans++;
        return;
    }

    for(int i=0; i<ab[s].size(); i++){
        if(color[ab[s][i]]==1){
            continue;
        }
        color[ab[s][i]]=1;
        depth++;
        dfs(ab[s][i]);
        color[ab[s][i]]=0;
        depth--;
    }
    return;
}

int main() {
    LL m;
    cin >> n >> m;
    LL tmp_a;
    LL tmp_b;
    for(int i=0; i<m; i++){
        cin >> tmp_a >> tmp_b;
        tmp_a--;
        tmp_b--;
        ab[tmp_a].push_back(tmp_b);
        ab[tmp_b].push_back(tmp_a);
    }

    color[0]=1;
    depth=1;
    dfs(0);

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3544
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <climits>
#include <map>
using namespace std;

#define N 200000

int n;
long long A[N + 1];
deque<long long> deq;

int main() {
    cin >> n;
    for ( int i = 1; i <= n; i++ ) {
        cin >> A[i];
    }
    
    for ( int i = 1; i <= n; i++ ) {
        if ( i % 2 != 0 ) {
            deq.push_back(A[i]);
        } else {
            deq.push_front(A[i]);
        }
    }
    
    if ( n % 2 != 0 ) {
        for ( int i = (int)deq.size() - 1; i >= 0; i-- ) {
            if ( i != deq.size() - 1 ) cout << " ";
            cout << deq[i];
        }
    } else {
        for ( int i = 0; i < deq.size(); i++ ) {
            if ( i != 0 ) cout << " ";
            cout << deq[i];
        }
    }
    
    cout << endl;
    
    return 0;
}

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


#define prec(i) cout << fixed << setprecision(i)

const long long int MOD = 1000000007;


int ctoi(char c) {
	if (c >= '0' && c <= '9')
		return c - '0';
	else
		return -1;
}


int main()
{
	prec(9);

	long long int n;
	double sum;

	cin >> n;

	vector<int> a(n);

	for(int i = 0; i < n; i++)
		cin >> a[i];

	for (int i = 0; i < n; i++)
		sum += 1 / (double)a[i];

	sum = 1 / sum;

	cout << sum << endl;

	return 0;

}

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

using namespace std;

#define DUMP(x) std::cerr << (#x) << " = " << (x) << "\n"
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP(i, k, n) for (int i = (k); i < (int)(n); ++i)
#define ALL(r) r.begin(), r.end()
#define YES puts("YES")
#define Yes puts("Yes")
#define NO puts("NO")
#define No puts("No")
#define IMP puts("IMPOSSIBLE")
#define Imp puts("Impossible")
#define imp puts("impossible")
#define M1 puts("-1")
#define pb push_back

template <typename T>
ostream &operator<<(ostream &os, vector<T> &v)
{
    os << "{";
    rep(i, v.size()) os << v[i] << (i == (int)v.size() - 1 ? "" : ", ");
    os << "}";
    return os;
}
template <typename T>
T dup(T x, T y)
{
    return (x + y - 1) / y;
};
template <typename A, size_t N, typename T>
inline void arrayFill(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }
struct in
{
    const size_t n = 0;
    in() = default;
    in(size_t n) : n(n){};
    template <typename T>
    operator T()
    {
        T ret;
        cin >> ret;
        return ret;
    }
    template <typename T>
    operator vector<T>()
    {
        assert(n != 0);
        vector<T> ret(n);
        for (auto &x : ret)
            cin >> x;
        return ret;
    }
};

using ll = int64_t;
using vint = vector<int32_t>;
using vvint = vector<vint>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pint = pair<int32_t, int32_t>;
using pll = pair<ll, ll>;
using setint = set<int32_t>;
using setstr = set<string>;
using qint = queue<int32_t>;
using qpint = queue<pint>;

constexpr std::int32_t INF = 1001001001;
constexpr std::int64_t LINF = 1001001001001001001;

#undef DUMP
#define DUMP(x)

void Main()
{
    ll n = in();
    vll a = in(3 * n);

    vll lsum(n + 1), rsum(n + 1);
    multiset<ll> l, r;

    rep(i, n)
    {
        l.insert(a[i]);
        r.insert(a[2 * n + i]);
    }

    lsum[0] = accumulate(ALL(l), 0LL);
    rsum[0] = accumulate(ALL(r), 0LL);

    for (int i = 0; i < n; ++i)
    {
        ll lmin = *l.begin();
        ll ml = a[n + i];
        DUMP(lmin);
        DUMP(ml);
        if (lmin < ml)
        {
            l.erase(l.begin());
            l.insert(ml);
            lsum[i + 1] = lsum[i] - lmin + ml;
        }
        else
        {
            lsum[i + 1] = lsum[i];
        }
    }

    for (int i = 0; i < n; ++i)
    {
        ll rmax = *r.rbegin();
        ll mr = a[n * 2 - i - 1];
        DUMP(mr);
        if (rmax > mr)
        {
            r.erase(prev(r.end()));
            r.insert(mr);
            rsum[i + 1] = rsum[i] - rmax + mr;
        }
        else
        {
            rsum[i + 1] = rsum[i];
        }
    }

    DUMP(lsum);
    DUMP(rsum);
    ll ans = -LINF;
    for (int i = 0; i <= n; ++i)
    {
        DUMP(lsum[i]);
        DUMP(rsum[n - i]);
        ans = max(ans, lsum[i] - rsum[n - i]);
    }
    cout << ans << endl;
}

int main()
{
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    std::cout << std::fixed << std::setprecision(15);
    Main();
    return 0;
}


Measured memory_bytes: 13568
#include <algorithm>/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
#include <utility>
#include <cstdio>
#include <vector>
#include <map>
#define pb push_back
#define mp std::make_pair
#define MOD 1000000007
typedef long long ll; 
ll arr[205], rem[205]; 
std::vector<ll> vec; 
std::map<std::vector<ll>, std::vector<std::pair<ll, ll> > > app; 
inline int calc(ll l, ll r)
{
	int res = 0; 
	ll cur = 0; 
	for (int i = 60; i >= 0; i--)
	{
		if ((l ^ r) & (1ll << i))
			return res + 1 - (l == cur); 
		if (l & (1ll << i))
		{
			res++; 
			cur |= 1ll << i; 
		}
	}
	return res; 
}
int main()
{
	// freopen("ARC086-F.in", "r", stdin); 
	int n;
	ll lim;
	scanf("%d%lld", &n, &lim); 
	for (int i = 0; i < n; i++)
		scanf("%lld", arr + i); 
	std::sort(arr, arr + n); 
	for (int k = 0; k <= 60; k++)
	{
		for (int i = 0; i < n; i++)
			rem[i] = arr[i] & (1ll << k) - 1; 
		std::sort(rem, rem + n); 
		for (int i = 0; i < n; i++)
		{
			if (i && rem[i - 1] == rem[i])
				continue; 
			vec.clear(); 
			ll mn = lim - k - calc((i ? rem[i - 1] : -1) + 1, rem[i]); 
			for (int j = 0; j < n; j++)
			{
				ll res = (arr[j] >> k) - (rem[i] > (arr[j] & (1ll << k) - 1)); 
				mn = std::min(mn, res); 
				vec.pb(res); 
			}
			if (mn < 0)
				continue; 
			std::sort(vec.begin(), vec.end()); 
			ll x = vec[0]; 
			for (ll &j : vec)
				j -= x; 
			app[vec].pb(mp(x - mn, x)); 
		}
	}
	ll ans = 0; 
	for (auto it : app)
	{
		std::sort(it.second.begin(), it.second.end()); 
		ll l = 0, r = -1; 
		for (auto x : it.second)
		{
			if (r < x.first)
			{
				ans += (r - l + 1) % MOD; 
				l = x.first; 
			}
			r = std::max(r, x.second); 
		}
		ans += (r - l + 1) % MOD; 
	}
	printf("%lld\n", ans % MOD);
	return 0; 
}


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

using namespace std;
#define ll long long
#define ff first
#define ss second
#define rep(i,a,b) for(ll i = a;i <= b;i++)
#define repv(i,a,b) for(ll i = a;i >= b;i--)
#define e endl
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
typedef pair<ll,ll> pp;


void solve(){
    string s;
    cin >> s;
    ll count = 0;
    for(ll i = 0;i < s.length();i++){
        count+=s[i]-'0';
    }
    if(count%9 == 0) cout << "Yes\n";
    else cout << "No\n";
}
        
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    //ll t; cin >> t; while(t--)
        solve();
}


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

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

  bool can = true;
  if(n%2 == 1) can = false;
  string s1 = s.substr(0, n/2);
  string s2 = s.substr(n/2, n/2);
  if(s1 != s2) can = false;
  if(can) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
#define dbg1(x) cerr<<#x<<"="<<(x)<<" "
#define dbg2(x) cerr<<#x<<"="<<(x)<<"\n"
#define dbg3(x) cerr<<#x<<"\n"
using namespace std;
#define reg register
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
	return x*f;
}
const int MN=25005,MK=405,P=1e9+7;
int Mul(int x,int y){return 1ll*x*y%P;}
int Add(int x,int y){return (x+y)%P;}
int fp(int x,int y){int r=1;for(;y;y>>=1,x=Mul(x,x))if(y&1)r=Mul(r,x);return r;}
int N,K,M,ans,a[MN],fac[MN],inv[MN],fi[MN];
int sf[MN][MK],f[MN][MK],sg[MN][MK],g[MN][MK];
bool chk1()
{
	static int ton[MK],num;
	reg int i;
	if(M<=K)return false;
	num=0;
	for(i=1;i<=K;++i)num+=!ton[a[i]]++;
	if(num==K) return true;
	for(i=K+1;i<=M;++i)
	{
		num-=!--ton[a[i-K]];
		num+=!ton[a[i]]++;
		if(num==K) return true;
	}
	return false;
}
int chk2()
{
	static int ton[MK],num;
	memset(ton,0,sizeof ton);
	reg int i;num=0;
	for(i=1;!ton[a[i]]&&i<=M;++i)num+=!ton[a[i]]++;
	return num;
}

int main()
{
	N=read(),K=read(),M=read();
	reg int i,j,Z=max(N,K);
	for(fac[0]=i=1;i<=Z;++i)fac[i]=Mul(fac[i-1],i);
	for(inv[0]=inv[1]=1,i=2;i<=Z;++i)inv[i]=Mul(inv[P%i],(P-P/i));
	for(fi[0]=i=1;i<=Z;++i)fi[i]=Mul(fi[i-1],inv[i]);
	for(i=1;i<=M;++i) a[i]=read();
	ans=Mul(N-M+1,fp(K,N-M));
	if(chk1()){return 0*printf("%d\n",ans);}
	f[0][0]=1;
	for(i=1;i<=N;++i)for(j=1;j<K;++j)
	{
		f[i][j]=Add(Mul(f[i-1][j-1],K-j+1),Add(sf[i-1][K-1],P-sf[i-1][j-1]));
		g[i][j]=Add(Mul(g[i-1][j-1],K-j+1),Add(sg[i-1][K-1],P-sg[i-1][j-1]));
		if(j>=M)g[i][j]=Add(g[i][j],f[i][j]);
		sf[i][j]=Add(sf[i][j-1],f[i][j]);
		sg[i][j]=Add(sg[i][j-1],g[i][j]);
	}
	if(chk2()==M)
	{
		int tmp=Mul(sg[N][K-1],Mul(fac[K-M],fi[K]));
		ans=Add(ans,P-tmp);
		printf("%d\n",ans);
		return 0;
	}
	else
	{
		int tmp=0,Mi,Ma,lm=chk2(),rm;
		reverse(a+1,a+M+1);rm=chk2();
		for(i=1;i<=N-M+1;++i)
		{
			int ii=i+lm-1,jj=N-i-M+1+rm,_1=0,_2=0;bool fl=ii==lm;
			for(j=lm;j<K;++j) _1=Add(_1,Mul(Mul(f[ii][j],Mul(fac[K-j],fi[K])),Mul(fac[K-lm],fi[K-j])));
			for(j=rm;j<K;++j) _2=Add(_2,Mul(Mul(f[jj][j],Mul(fac[K-j],fi[K])),Mul(fac[K-rm],fi[K-j])));
			tmp=Add(tmp,Mul(_1,_2));
		}
		ans=Add(ans,P-tmp);
		printf("%d\n",ans);
		return 0;
	}
}


Measured memory_bytes: 162232
#include<bits/stdc++.h>
#define start_routine cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false); int begtime = clock();
#define end_routine int endtime = clock(); cerr << endl << "Time elapsed: " << (endtime - begtime)*1000/CLOCKS_PER_SEC << " ms"; return 0;
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define int long long
#define mp make_pair
#define fr(i,a,b) for(i=a;i<b;i++)
#define mod 1000000007
#define FILEIO freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
using namespace std;

vector <int> v;
bool b[1000001] = {0};
void calculate()
{
	int i;
	fr(i,2,1000001)
	{
		if(b[i] == 0)
		{
			v.pb(i);
			int j;
			for(j = i*i; j<=1000000; j+=i) b[j] = 1;
		}
	}
}
signed main()
{
	//FILEIO
 	//start_routine
	
	calculate();
	int n,p;
	cin>>n>>p;

	int ans = 1;
	int i;
	fr(i,0,v.size())
	{
		if(p%v[i] == 0)
		{
			int temp =0;
			while(p%v[i] == 0)
			{
				temp++;
				p/=v[i];
			}
			int t = temp/n;
			while(t--)
			{
				ans *= v[i];
			}
		}
	}
	if(p != 1)
	{
		if(n == 1) return cout<<ans*p<<"\n",0;
		else cout<<ans<<'\n';
		return 0;
	}

	cout<<ans<<'\n';

 	//end_routine
}


Measured memory_bytes: 2424
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
LL N,X;
LL DFS(LL R,LL C)
{
	if(R>C)
		swap(R,C);
	if(R==0)
		return -C;
	LL num=C/R,res=C%R;
	return DFS(res,R)+num*R*2LL;
}
int main()
{
//	freopen("light.in","r",stdin);
//	freopen("light.out","w",stdout);
	scanf("%lld %lld",&N,&X);	
	printf("%lld\n",X+N-X+DFS(N-X,X));
	return 0;
}

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

const int MOD = (int)1e9+7;

int main(){
	int N,K;
	cin >> N >> K;
	vector<int> h(N);
	for(int i=0;i<N;i++)	cin >> h.at(i);

	int ans=0;
	for(int i=0;i<N;i++)	if(h.at(i)>=K)	ans++;
	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 640
N = int(input())
A = list(map(int,input().split()))

#for i in A:
for i in range(N):
    if A[i] % 2 == 0:
        if A[i] % 3 != 0 and A[i] % 5 != 0:
            print('DENIED')
            break
else:print("APPROVED")

Measured memory_bytes: 2940
n, m  = map(int, input().split())
pos = []
check = []
for i in range(n):
  a, b  = map(int, input().split())
  pos.append([a, b])

for i in range(m):
  c, d  = map(int, input().split())
  check.append([c, d])

for i in range(n):
  ans = 0
  k = 10**9
  for j in range(m):
    t = abs(pos[i][0] - check[j][0]) + abs(pos[i][1] - check[j][1])
    if k > t:
      k = t
      ans = j + 1
  print(ans)
      

Measured memory_bytes: 9156
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.stream.Stream;

public class Main {
    public static boolean find(int[] ary, int searchNum) {
        int start = 0;
        int end = ary.length - 1;

        while(start <= end) {
            int pivot = start + (end - start) / 2;

            if(ary[pivot] < searchNum) {
                start = pivot + 1;
            } else if(ary[pivot] > searchNum) {
                end = pivot - 1;
            } else {
                return true;
            }
        }
        return false;
    }
    
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int [] S = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int q = Integer.parseInt(br.readLine());
        int [] T = Stream.of(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();

        int count = 0;
        for(int i = 0; i < q; i++) {
            if(find(S, T[i])) {
                count++;
            }
        }
        System.out.println(count);
    }
}

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

int main() {
	double x1,x2,y1,y2,d;
	cin >> x1 >> y1 >> x2 >> y2;

	d = sqrt(pow(x1-x2,2) + pow(y1-y2,2));

	printf("%.5f\n",d);

	return 0;
}

Measured memory_bytes: 1236
#include<iostream>
using namespace std;
int main()
{
    int m,d;
    int count=0;
    cin>>m>>d;
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=d;j++)
        {
            int x=j%10;
            int y=j/10;
            if(x>=2 && y>=2)
            {
                if(x*y==i)
                {
                //cout<<i<<"-"<<j<<endl;
                count++;
                }
            }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define sz(v) (v).size()
#define all(v) (v).begin(),(v).end()
#define inf 1000000000
#define mod 1000000007
using namespace std;
template <class T> void chmax(T &x,T y){x=x>y?x:y;return;}
template <class T> void chmin(T &x,T y){x=x<y?x:y;return;}
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pi;

int n,a[15];

void dfs(int p,int maxn)
{
	if(p>n)
	{
		for(int i=1;i<=n;i++)
			cout<<char(a[i]+'a');
		cout<<endl;
		return;
	}
	for(int i=0;i<=maxn;i++)
	{
		a[p]=i;
		dfs(p+1,maxn);
	}
	a[p]=maxn+1;
	dfs(p+1,maxn+1);
	return;
}

int main()
{
	cin>>n;
	dfs(1,-1);
	return 0;
}

Measured memory_bytes: 3628
#pragma GCC optimize "03"
#include "bits/stdc++.h"
using namespace std;
 
#define ll long long int
#define ld long double
#define pi pair<int, int>
#define pb push_back
#define fi first
#define se second
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#ifndef LOCAL
#define endl '\n'
#endif
 
const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
 
signed main() {
	IOS;
	#ifdef LOCAL
		freopen("input.txt","r", stdin);
		freopen("output.txt","w",stdout);
	#endif
	int n, d;
	cin >> n >> d;
	cout << (n-1)/(2*d + 1) + 1;	
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
const int MAX = 2e5+10;

int a[MAX], s[MAX];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);

    for(int i = 0; i < n; ++ i) {
        scanf("%d", &a[i]);
        if(i) s[i] = s[i-1] + a[i];
        else s[i] = a[i];
    }

    int mx = s[k-1];
    for(int i = k; i < n; ++ i) {
        if(s[i] - s[i-k] > mx) mx = s[i] - s[i-k];
    }

    printf("%.12f\n", 0.5*(mx+k));
}


Measured memory_bytes: 1792
import java.io.IOException;
import java.util.Scanner;
class Main{
	public static void main(String[] args)throws NumberFormatException, IOException{
		Scanner scan = new Scanner(System.in);
		String answer = "";
		String temp = "";
		
		while(true){
			temp = scan.next();
			if(temp.equals("-")){
				break;
			}
			char[] targetChar = temp.toCharArray();
			int targetLength = temp.length();
			int shuffleTimes = scan.nextInt();
			int shuffleBegin = 0;
 
			for(int i =0; i<shuffleTimes; i++){
				shuffleBegin = scan.nextInt();
				answer = "";
				for(int j=0; j<(targetLength - shuffleBegin) ; j++){
					answer = answer + targetChar[j + shuffleBegin];
				}
				for(int j=0; j<shuffleBegin; j++){
					answer = answer + targetChar[j];
				}
				targetChar = answer.toCharArray();
			}
			System.out.println(answer);
		}
	}
}


Measured memory_bytes: 45860
N,C,K = list(map(int, input().split()))
t = []
for i in range(N):
	t.append(int(input()))

t.sort(reverse=True)
bus = 0
while t!=[]:
	init = t.pop()
	count = 1
	while t!=[]:
		if count >= C:
			break
		now = t[-1]
		if now - init > K:
			break
		t.pop()
		count += 1
	bus+=1

print(bus)

Measured memory_bytes: 7384