akhauriyash/Code-Regression huggingface dataset:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<utility>
#define root 1,1,n
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
const int N=2e5+4;
int n,A;
ll D;
struct Node {
	int p,h;
	friend bool operator <(const Node &a,const Node &b) {
		return a.p<b.p;
	}
}a[N];
ll temp[N];
int d[N];
inline int read() {
	int x=0,f=1;char c=getchar();
	while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
	while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
	return x*f;
}
inline void smax(int &x,int y) {
	x=x<y?y:x;
}
inline void smin(int &x,int y) {
	x=x>y?y:x;
}
ll mx[N<<2];
ll laz[N<<2];
inline void pushup(int rt) {
	mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
}
inline void pushdown(int rt) {
	if (laz[rt]) {
		mx[rt<<1]-=laz[rt];
		mx[rt<<1|1]-=laz[rt];
		laz[rt<<1]+=laz[rt];
		laz[rt<<1|1]+=laz[rt];
		laz[rt]=0;
	}
}
inline void build(int rt,int l,int r) {
	if (l==r) {
		mx[rt]=a[l].h;
		return ;
	}
	int mid=l+r>>1;
	build(lson);
	build(rson);
	pushup(rt);
}
inline void modify(int rt,int l,int r,int L,int R,int val) {
	if (L<=l&&r<=R) {
		mx[rt]-=val;
		laz[rt]+=val;
		return ;
	}
	pushdown(rt);
	int mid=l+r>>1;
	if (L<=mid) modify(lson,L,R,val);
	if (mid<R) modify(rson,L,R,val);
	pushup(rt);
}
inline pp query(int rt,int l,int r) {
	if (mx[rt]<=0) return make_pair(-1,-1);
	if (l==r) return make_pair(l,mx[rt]);
	pushdown(rt);
	int mid=l+r>>1;
	if (mx[rt<<1]>0) return query(lson);
	else if (mx[rt<<1|1]>0) return query(rson);
}
int main() {
//	freopen("in5.txt","r",stdin);
	n=read(),D=read(),A=read();
	for (register int i=1;i<=n;++i) {
		a[i].p=read(),a[i].h=read();
		if (a[i].h%A) (a[i].h/=A)+=1;
		else a[i].h/=A;
	}
	sort(a+1,a+n+1);
	for (register int i=1;i<=n;++i)
		temp[i]=a[i].p;
	for (register int i=1;i<=n;++i)
		d[i]=upper_bound(temp+1,temp+n+1,temp[i]+(D<<1))-temp-1;
	build(root);
	ll ans=0;
	while (1) {
		pp cur=query(root);
		int pos=cur.first,val=cur.second;
		if (pos==-1) break;
		ans+=val;
		modify(root,pos,d[pos],val);
	}
	printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 15620
/**
*    created: 10.07.2020 20:52:31
**/
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
// #include <boost/multiprecision/cpp_int.hpp>
// using bint = boost::multiprecision::cpp_int;
using namespace std;
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()
#define pcnt(bit) __builtin_popcountll(bit)
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;}
const long double pi = acos(-1.0);
const int MAX = 1000010;
const int INF = 1LL << 60;
const int MOD = 1000000007;
// const int MOD = 998244353;

signed main() {

    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int a, b; cin >> a >> b;
    rep(i,a) {
        string s; cin >> s;
        cout << s << endl;
        cout << s << endl;
    }
    return 0;
}

Measured memory_bytes: 3632
#ifdef local_mode
    #include <cstdio>
    #include <cassert>
#endif
#include <iostream>
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vector<int>> vii;
#define pb push_back
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)

int main() {
#ifdef local_mode
    ios_base::sync_with_stdio(0), cin.tie(0);
    assert(freopen("in", "r", stdin));
    assert(freopen("out", "w", stdout));
#endif
    
    string s, t;
    cin >> s >> t;

    if (s.length() != t.length()) {
        cout << "No";
        return 0;
    }

    for (int d = 0; d < s.length(); d++) {
        int i = 0;
        while (s[i] == t[(i + d) % t.length()]) i++;
        if (i == s.length()) {
            cout << "Yes";
            return 0;
        }
    }

    cout << "No";

    return 0;
}







































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

using namespace std;

int calc(int i, int count,int sum){
	if (count == 0){
		if (sum == i){
			return 1;
		}
		else{
			return 0;
		}
	}
	else{
		int count2 = 0;
		for (int j = 0; j < 10; j++){
			count2+=calc(i, count - 1, sum + j);
		}
		return count2;
	}

}

int main(){
	int i;
	while (cin >> i){
		cout << calc(i, 4, 0) << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
#include <cstdio>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <bitset>
#include <iterator>
#define rep(i, n) for(long long i = 0; i < (long long)(n); i++)
#define debug(x)  cout << #x << " = " << (x) << endl;
using namespace std;
typedef long long int LL;
typedef unsigned long long int ULL;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int> > v(m);
    rep(i, m) {
        int k;
        cin >> k;
        rep(j, k) {
            int x;
            cin >> x;
            v[i].push_back(x - 1);
        }
    }
    vector<int> p(m);
    rep(i, m) {
        cin >> p[i];
    }
    int ans = 0;
    for (int bit = 0; bit < (1 << n); bit++) {
        bool off_flag = false;
        rep(i, m) {
            int num_on = 0;
            for (int j: v[i]) {
                if (bit & (1 << j)) {
                    num_on++;
                }
            }
            //debug(num_on);
            if ((num_on % 2) == p[i]) {
                continue;
            } else {
                off_flag = true;
            }
        }

        if (off_flag == false){
            ans++;
        }
    }
    cout << ans << endl;
    return 0;
}


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

int n, m, c;
vector<int> b;
int res;

int main(void){
    cin >> n >> m >> c;
    b = vector<int>(m);
    for(int i = 0; i < m; i++) cin >> b[i];
    res = 0;
    for(int i = 0; i < n; i++){
        int sum = 0;
        for(int j = 0; j < m; j++){
            int a;
            cin >> a;
            sum += a*b[j];
        }
        if(sum + c > 0) res++;
    }
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 3580
#include<bits/stdc++.h>
using namespace std;
const int maxn=200010;
const long long mod=1e9+7;
long long a[maxn],sum[maxn];
int main()
{	
	int n;
	long long ans=0;
	cin>>n;
	memset(sum,0,sizeof(sum));
	for(int i=1;i<=n;i++)cin>>a[i];
	sum[n]=a[n];
	for(int i=n-1;i>0;i--)sum[i]+=sum[i+1]+a[i];
	for(int i=n-1;i>0;i--)sum[i]=sum[i]%mod;
	for(int i=1;i<n;i++)ans=(ans+a[i]*sum[i+1]%mod)%mod;
	cout<<ans<<endl;
return 0;
}


Measured memory_bytes: 6744
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<stdlib.h>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<iostream>
#include<cctype>
#include<map>
#include<stack>
#include<cstdlib>
#include<queue>
#include<vector>
#include<algorithm>
#include<bitset>
#include<algorithm>
#include<set>
#include<limits.h>
#include <list>

using namespace std;
typedef long int LD;
typedef long long int LLD;
typedef float F;
typedef double LF;
typedef unsigned int U;
typedef unsigned long int LU;
typedef unsigned long long int LLU;
typedef char C;


/*----------simple input section ------------ */
#define sf scanf
#define sfi(x) scanf("%d",&x)
#define sfc(x) scanf("%c",&x)
#define sfi2(x,y) scanf("%d%d",&x,&y)
#define sfl(x) scanf("%ld",&x)
#define sfll(x) scanf("%lld",&x)
#define sfd(x) scanf("%lf",&x)
#define sfu(x) scanf("%llu",&x)
#define sfs(x) scanf("%s",x)


/*----------simple input section ------------ */
#define pf printf
#define pfi(x) printf("%d\n",x)
#define pfl(x) printf("%ld\n",x)
#define pfll(x) printf("%lld\n",x)
#define pfu(x) printf("%llu\n",x)
#define pfs(x) printf("%s\n",x)
#define pfc(x) printf("%c\n",x)
#define pfd(x) printf("%lf\n",x)

/*----------file input section ------------ */

#define f_input  freopen("input.txt","r",stdin);
#define f_output freopen("output.txt","w",stdout);

#define pb(x) push_back(x)
#define PI acos(-1.0)
#define sq(x) (x)*(x)
#define mem(x,y) memset(x,y,sizeof(x))
#define TEST int cs,T;sfi(T);getchar();for(cs=1;cs<=T;cs++)
#define nn printf("\n")
// xx-> diagonal -> 8 horizontal/vertical->4

const int xx[] = {0, 1, 0, -1, -1, 1, -1, 1};
const int yy[] = {1, 0, -1, 0, 1, 1, -1, -1};

// KX-> Knight moves
const int kx[] = {-2, -1, 1, 2, 2, 1, -1, -2};
const int ky[] = {1, 2, 2, 1, -1, -2, -2, -1};


/******** debug **********/
#define chk1 printf("hi......1  \n")
#define chk2 printf("hi......2  \n")




#define mod 1000000007
#define eps 10e-8
#define sz 700
#define sz1 500005
#define sz2 15
/******* start my code ********/
LLD arr[sz2];
int main()
{
    int i,j,k;
    LLD ans,mul,mul2,mul3;
    sfll(arr[0]);
    sfll(arr[1]);
    sfll(arr[2]);
    ans=arr[0]*arr[1]*arr[2];
    sort(arr,arr+3);
    mul=arr[0]*arr[1];
    if(arr[2]%2==0)
    {
        pfi(0);
    }
    else
    {
        mul2=arr[2]/2;
        pfll((mul2+1)*mul-mul2*mul);
    }
    return 0;
}


/*

*/


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f(ll x){if(x==0) return 0;else return x%10+f(x/10);}
int main(){
    std::ios::sync_with_stdio(false);
    int k;cin>>k;
    int num=0;ll ans=1;ll p=1;
    while(num<k){
        cout<<ans<<endl;
        ll ans1=ans+p;
        ll ans2=ans+p*10;
        if(ans1*f(ans2)<=ans2*f(ans1)){ans=ans1;}
        else{ans=ans2;p*=10;}
        num++;
    }
    return 0;
}

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

using ll = long long;

template<typename T>
T gcd(T a, T b)
{
	if (a < b)	return gcd(b, a);
	T r;
	while ((r = a % b))
	{
		a = b;
		b = r;
	}
	return b;
}

template<typename T>
T lcm(T a, T b)
{
	return a * b / gcd(a, b);
}

template<typename T>
T ext_gcd(T a, T b, T& x, T& y)
{
	x = 1;
	y = 0;
	T x0 = 0, y0 = 1;
	while (b != 0)
	{
		T q = a / b;
		a -= q * b;
		swap(a, b);
		x -= q * x0;
		swap(x, x0);
		y -= q * y0;
		swap(y, y0);
	}
	return a;
}

template<typename T>
T inv_mod(T a, T mod)
{
	T t1, t2;
	ext_gcd(a, mod, t1, t2);
	t1 %= mod;
	if (t1 < 0)		t1 += mod;
	return t1;
}

template<typename T>
T combination_large(T n, T k, T mod)
{
	if (n < k || n < 0 || k < 0)	return 0;
	vector<T> inv(n + 1, 1), fact(n + 1, 1), fact_inv(n + 1, 1);
	for (T i = 2; i <= n; ++i)
	{
		inv[i] = mod - inv[mod % i] * (mod / i) % mod;
		fact[i] = (fact[i - 1] * i) % mod;
		fact_inv[i] = fact_inv[i - 1] * inv[i] % mod;
	}
	return fact[n] * (fact_inv[k] * fact_inv[n - k] % mod) % mod;
}

template<typename T>
T combination(T n, T k, T mod = 1)
{
	vector<vector<T>> table(n + 1, vector<T>(k + 1, 1));
	for (T i = 1; i <= n; ++i)
	{
		table[i][0] = 1;
		for (T j = 1; j <= n; ++j)
		{
			table[i][j] = (table[i - 1][j - 1] + table[i - 1][j]) % mod;
		}
	}
}


int main(int, char**)
{
	ll N;
	cin >> N;
	bool app = true;
	for (ll i = 0; i < N; ++i)
	{
		ll A;
		cin >> A;
		if (A % 2 == 0 && !(A % 3 == 0 || A % 5 == 0))
		{
			app = false;
		}
	}
	cout << (app ? "APPROVED" : "DENIED") << endl;

	return 0;
}


Measured memory_bytes: 256
match_num=[0,2,5,5,4,5,6,3,7,6]
N,M=map(int, input().split())
nums=sorted(list(map(int, input().split())),reverse=True)
INF=1000000
#max桁数
dp = [-INF for _ in range(N+1)]
dp[0]=0
usables=[]
for n in nums:
  usables.append(match_num[n])

for i in range(min(usables), N+1):
  tmp=[]
  for u in usables:
    if (i-u)>=0:
      tmp.append(dp[i-u])
  
  dp[i]=max(tmp)+1

remained_maches=N

ans=''  
for i in range(dp[N]):
  for j in range(M):
    if (remained_maches-usables[j])>=0:
      if dp[remained_maches]-1==dp[remained_maches-usables[j]]:
        ans+=str(nums[j])
        remained_maches-=usables[j]
        break
        
print(ans)

Measured memory_bytes: 3316
#include<iostream>
#include<algorithm>
using namespace std;
bool dp[1000001];
bool isprime(int& x){
  for(int i = 2 ; i * i <= x ; i++ ) if( x % i == 0) return true;
  return x == 1;
}
int solve(int i){
  while(true){
    if(dp[i] && !isprime(i)) return i;
    i--;
  }
}
int main(){
  int n,x,data,ans;
  dp[0] = true;
  while(cin >> n >> x , n){
    for(int i = 1 ; i <= x ; i++ ) dp[i] = false;
    for(int i = 0 ; i < n ; i++ ){
      cin >> data;
      for(int i = data ; i <= x ; i++ ) if(dp[i-data]) dp[i] = true;
    }
    if(ans = solve(x)) cout << ans << endl;
    else cout << "NA" << endl;
  }
}

Measured memory_bytes: 2136
#include<bits/stdc++.h>
using namespace std;
#define li long long
#define gc getchar()
#define pc putchar
li read(){
	li x = 0;
	int y = 0,c = gc;
	while(!isdigit(c)){
		y = c;
		c = gc;
	}
	while(isdigit(c)){
		x = (x << 1) + (x << 3) + (c ^ '0');
		c = gc;
	}
	return y == '-' ? -x : x;
}
void print(li q){
	if(q < 0){
		pc('-');
		q = -q;
	}
	if(q >= 10) print(q / 10);
	pc(q % 10 + '0');
}
int n;
int work(int q){
	int nw = 0;
	while(q){
		nw += q % 10;
		q /= 10;
	}
	return nw;
}
int main(){
	int i,as = 100000;
	n = read();
	for(i = 1;i < n;++i) as = min(as,work(i) + work(n - i));
	print(as);
	return 0;
}

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

int64_t calcGCD(int64_t a, int64_t b)
{
	while (a)
	{
		b %= a;
		std::swap(a, b);
	}
	return b;
}

int64_t calcLCM(const int64_t a, const int64_t b)
{
	// if (a * b == 0) return 0;
	return a / calcGCD(a, b) * b;
}

int pri2(int64_t);
int solve();

int main()
{
	printf("%d\n", solve());

	return 0;
}

int pri2(int64_t num)
{
	int ret{};
	while (num % 2 == 0)
	{
		ret++;
		num /= 2;
	}
	return ret;
}

int solve()
{
	int N;
	int64_t M;
	scanf("%d%lld", &N, &M);
	std::vector<int64_t> a(N);
	for (auto& e: a) scanf("%lld", &e);
	int div2{pri2(a.front())};
	for (auto& e: a)
	{
		if (e % 2 == 1) return 0;
		if (pri2(e) != div2) return 0;
		e /= 2;
	}
	int64_t lcm{1};
	for (auto& e: a)
	{
		lcm = calcLCM(lcm, e);
		if (lcm > M)
			return 0;
	}
	return M / lcm - M / (lcm * 2);
}

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

using namespace std;



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

    int N;
    cin >> N;
    vector<int> L(N);
    for (int i = 0; i < N; ++i) cin >> L[i];
    sort(L.begin(), L.end());
    int cnt = 0;
    for (int i = 0; i < N - 2; ++i) {
        for (int j = i + 1; j < N - 1; ++j) {
            auto itr = lower_bound(L.begin(), L.end(), L[i] + L[j]);
            int length = distance(itr, L.end());
            cnt += (N - j - 1) - length;
        }
    }
    cout << cnt << '\n';
}

Measured memory_bytes: 256
//Date and time of submission: 
 
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+5;

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	string s;
	cin>>s;
	ll cnt=0;
	for(char ch: s)
	{
	    cnt+=(ch=='+');
	    cnt-=(ch=='-');
	}
	cout<<cnt;
	return 0;
}


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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { cout << #a << " = " << a << endl; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }

typedef long long ll;
int const inf = 1<<29;

int main() {

  int N; cin >> N;
  int curr = 0;
  rep(i, N) {
    string s; cin >> s;
    if(s[0] == 'A') curr ++;
      else curr --;
    if(curr < 0) {cout << "NO" << endl; exit(0);}
  }
  if(curr == 0) cout << "YES" << endl;
  else cout << "NO" << endl;
  
  return 0;
}

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

int main() {
  string a;
  cin >> a;
  if(a =="RRR")
    cout << 3;
  if(a == "RRS" || a == "SRR" )
    cout << 2 ;
  if(a=="SSS")
    cout << 0 ;
  if(a=="RSR"||a=="RSS"||a=="SRS"||a=="SSR")
    cout << 1 ;
}


Measured memory_bytes: 3620
h,w,KK=map(int,input().split())

c=[list(input()) for _ in range(h)]


#縦の全探索

ans=0

#print(c)

for i in range(2**h):
    y=[]
    for j in range(h):
        if (i>>j)&1:
            y.append(j)
       
    for k in range(2**w):
        x=[]
        for l in range(w):
            if (k>>l)&1:
                x.append(l)
        tmp=0
        #print(bin(i),y,bin(k),x)
        for yy in range(h):
            for xx in range(w):
                if yy not in y and xx not in x:
                    #print(c)
                    if c[yy][xx]=="#":
                        tmp+=1
        if tmp==KK:
            ans+=1

print(ans)





Measured memory_bytes: 9236
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int D = Integer.parseInt(sc.next());
		sc.close();
		
		if(D == 25) {
			System.out.println("Christmas");
		}else if(D == 24){
			System.out.println("Christmas Eve");
		}else if(D == 23) {
			System.out.println("Christmas Eve Eve");
		}else {
			System.out.println("Christmas Eve Eve Eve");
		}
	}
}

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

using namespace std;
int main(){ 
    string s;
    cin >> s;
    if(s=="SUN") cout << 7 << endl;
    if(s=="MON") cout << 6 << endl;
    if(s=="TUE") cout << 5 << endl;
    if(s=="WED") cout << 4 << endl;
    if(s=="THU") cout << 3 << endl;
    if(s=="FRI") cout << 2 << endl;
    if(s=="SAT") cout << 1 << endl;

    return 0;
}

Measured memory_bytes: 3628
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <string>
#include <list>
#include <bitset>
#include <vector>
using namespace std;

#define I64d_OJ

//#ifdef I64d_OJ
//#define LL __int64
//#endif // I64d_OJ
#ifdef I64d_OJ
#define LL long long
#endif // I64d_OJ

typedef unsigned LL ULL;
typedef unsigned uint;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
typedef pair<LL,LL> pLL;
typedef vector<int> vi;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-f; ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}

#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define ls rt<<1
#define rs rt<<1|1
#define MID(a,b) (((LL)(a)+(LL)(b))>>1)
#define absx(a) ((a)<0?-(a):(a))
#define MK(a,b) make_pair(a,b)
#define PB(a) push_back(a)
#define lowbit(x) ((x)&-(x))

#define lc c[x][0]
#define rc c[x][1]

template< typename T >
inline void Max(T &a,T &b){if(a<b) a=b;}
template< typename T>
inline void Min(T &a,T &b){if(a>b) a=b;}

const double pi=(double)acos(-1.0);
const double eps=(double)1e-8;
const int INF = (int) 0x3f3f3f3f;
const int MOD = (int) 924844033;
const int MAXN =(int) 2e3+10;
const int MAXM = (int) 3e6+10;

///--------------------START-------------------------
int N,K;
LL g[MAXN*2],dp[MAXN*2][MAXN*2][2];
int id[MAXN*2];


void work(){
    scanf("%d%d",&N,&K);
    g[0]=1;
    for(int i=1;i<=N;i++) g[i]=g[i-1]*i%MOD;
    int curid=0;
    for(int i=1;i<=K;i++){
        for(int j=i;j<=N;j+=K){
            id[++curid]=j;
        }
    }
    for(int i=1;i<=K;i++){
        for(int j=i;j<=N;j+=K){
            id[++curid]=j;
        }
    }
//    for(int i=1;i<=curid;i++){
//        printf("%d ",id[i]);
//    }
//    printf("\n");
//    printf("curid = %d\n",curid);
//    dp[0][0][0]=1;
    for(int i=1;i<=N*2;i++){
        for(int j=0;j<=i;j++){
            if(id[i]<=K){
                if(i==1) dp[i][j][0]=j==0;
                else dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%MOD;
                dp[i][j][1]=0;
            }
            else{
                dp[i][j][0]=(dp[i-1][j][0]+dp[i-1][j][1])%MOD;
                if(j>0) dp[i][j][1]=dp[i-1][j-1][0];
            }
        }
    }
    LL ans=0;
    int tmp=1;
    for(int i=0;i<=N;i++){
        if(tmp==1){
            ans+=(dp[N*2][i][0]+dp[N*2][i][1])*g[N-i]%MOD;
        }
        else{
            ans+=MOD-(dp[N*2][i][0]+dp[N*2][i][1])*g[N-i]%MOD;
        }
        tmp*=-1;
    }
    printf("%lld\n",ans%MOD);
}

///--------------------END-------------------------
int main(){
#ifdef NNever
//freopen("data.in","r",stdin);
///freopen("out.txt","w",stdout);
#endif // NNever
    work();
    return 0;
}





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

//#define int long long
#define DBG 0
#define dump(o) if(DBG){cerr<<#o<<" "<<o<<endl;}
#define dumpc(o) if(DBG){cerr<<#o; for(auto &e:(o))cerr<<" "<<e;cerr<<endl;}
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define each(it,c) for(auto it=(c).begin();it!=(c).end();it++)
#define all(c) c.begin(),c.end()
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9 + 7);

signed main() {
	int N, W, H; cin >> N >> W >> H;
	vector<int> w(W + 1, 0);
	vector<int> h(H + 1, 0);
	rep(i, 0, N) {
		int x, y, k; cin >> x >> y >> k;
		w[max(0, x - k)]++;
		w[min(W, x + k)]--;
		h[max(0, y - k)]++;
		h[min(H, y + k)]--;
	}
	dumpc(h);
	dumpc(w);
	rep(i, 1, W + 1) {
		w[i] += w[i - 1];
	}
	rep(i, 1, H + 1) {
		h[i] += h[i - 1];
	}
	dumpc(h);
	dumpc(w);
	int a = max(
		*min_element(w.begin(), w.end() - 1),
		*min_element(h.begin(), h.end() - 1)
	);
	if (a == 0)cout << "No" << endl;
	else cout << "Yes" << endl;
	return 0;
}

Measured memory_bytes: 3616
use proconio::{fastout, input};

use std::cmp::Reverse;

#[fastout]
fn main() {
    // ref: https://atcoder.jp/contests/abc164/submissions/12364484
    input! {
        (n, m, s): (usize, usize, usize),
        edge: [(usize, usize, usize, usize); m],
        ex: [(usize, usize); n]
    };

    let mut g = vec![vec![]; n + 1];
    for (a, b, c, d) in edge {
        g[a].push((b, c, d));
        g[b].push((a, c, d));
    }

    let w = 50 * 50;
    let mut dp = vec![vec![std::usize::MAX; w + 1]; n + 1];
    dp[1][std::cmp::min(w, s)] = 0;

    let mut h = std::collections::BinaryHeap::new();
    h.push(Reverse((0, 1, std::cmp::min(w, s))));
    while let Some(Reverse((d, v, k))) = h.pop() {
        if d > dp[v][k] {
            continue;
        }

        // 金貨を交換せずに移動
        for &(u, a, b) in g[v].iter() {
            if a > k {
                // お金が足りなくて移動できない
                continue;
            }

            let d = d + b; // 移動後の時間
            if d < dp[u][k - a] {
                dp[u][k - a] = d;
                h.push(Reverse((d, u, k - a)));
            }
        }

        // 1回金貨を交換する
        let d = d + ex[v - 1].1;
        let k = std::cmp::min(k + ex[v - 1].0, w);
        if dp[v][k] > d {
            dp[v][k] = d;
            h.push(Reverse((d, v, k)));
        }
    }

    for dp in dp.into_iter().skip(2) {
        let ans = dp.into_iter().min().unwrap();
        println!("{}", ans);
    }
}


Measured memory_bytes: 4684
#include <bits/stdc++.h>
#define SORT(x) sort((x).begin(),(x).end())
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(ll i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define db(x) cout<<#x<<"="<<x<<endl
#define deb(x) each(x.begin(),x.end(),(int& y){cout << y <<" ";})
template<class T>bool maxi(T &a,const T &b){if(a<b){ a=b; return 1;} return 0;}
template<class T>bool mini(T &a,const T &b){if(b<a){ a=b; return 1;} return 0;}
#define y0 y3487465 //j0
#define j1 j1347829 //j1
#define INF2 4000000000000000037
#define INF 1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;

//const int MAXN=100010;
//ll dp[MAXN][MAXN];

void Main(){

  ll N;cin>>N;

  vector<ll> dp[100010];

  ll s[N];
  rep(i,N){
    cin>>s[i];
  }

  rep(c,N){ // c, k
    dp[c].emplace_back(0);
  }

  ll ans=0;

  ll nidome[N]={};

  reps(c,1,N){
    for(ll k=1;(k+1)*c<N-1;k++){
      dp[c].emplace_back(dp[c][k-1]+s[N-1-k*c]+s[k*c]);
      if(maxi(nidome[N-1-k*c],c)==0 or maxi(nidome[k*c],c)==0){
        continue;
      }
      maxi(ans,dp[c][k]);
    }
  }

  cout<< ans<<"\n";
}

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


Measured memory_bytes: 17396
#[allow(unused_imports)]
use std::cmp::{min,max};
#[allow(unused_imports)]
use std::collections::{BTreeMap,BTreeSet};
#[allow(unused_imports)]
use std::ops::*;
#[allow(unused_imports)]
use std::collections::BinaryHeap;

#[allow(unused_macros)]
macro_rules! tf {
    ($c:expr, $t:expr, $f:expr) => {{
        if $c { $t } else { $f }
    }};
}

fn main() {
    let ss: Vec<char> = read_line().chars().collect();
    let ts: Vec<char> = read_line().chars().collect();
    let mut map1 = BTreeMap::<char,char>::new();
    let mut map2 = BTreeMap::<char,char>::new();
    let n = ss.len();
    let mut res = true;
    for i in 0..n {
        let s = ss[i];
        let t = ts[i];
        if map1.get(&s).is_none() && map2.get(&t).is_none() {
            map1.insert(s, t);
            map2.insert(t, s);
        }
        else if map1.get(&s).is_some() && map2.get(&t).is_some() {
            if map1[&s] != t || map2[&t] != s {
                res = false;
            }
        }
        else {
            res = false;
        }
    }
    println!("{}", tf!(res, "Yes", "No"));
}

#[allow(dead_code)]
fn read_line() -> String {
    let mut ret = String::new();
    std::io::stdin().read_line(&mut ret).ok();
    ret.pop();
    //ret.pop();
    return ret;
}

#[allow(dead_code)]
fn read_i64() -> i64 {
    let ss = read_line();
    return ss.parse::<i64>().unwrap();
}

#[allow(dead_code)]
fn read_vec_i64() -> Vec<i64> {
    let mut res = vec![];
    let ss = read_line();
    for ts in ss.split_whitespace() {
        let x = ts.parse::<i64>().unwrap();
        res.push(x);
    }
    return res;
}

use std::fmt::Display;
#[allow(dead_code)]
fn write_vec<T: Display>(xs: &Vec<T>) {
    if xs.len() == 0 {
        println!("");
        return;
    }
    print!("{}", xs[0]);
    for i in 1..xs.len() {
        print!(" {}", xs[i]);
    }
    println!("");
}


Measured memory_bytes: 6396
import java.util.*;
public class Main{
    public static void main(String[] args)throws Exception{
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        long[] array = new long[n];
        long ans1 = 0;
        long ans2 = 0;



        for(int i = 1;i <= n;i++){//AN-Nを格納
            array[i-1] = sc.nextInt() - i;
        }

        Arrays.sort(array);//昇順ソート　降順は Arrays.sort(array,Collections.reverseOrder());

        long median1 = array[n/2];



        for(int i = 0;i < n;i++){//i=0,1,2,,,,n-1 で動作
            ans1 += Math.abs(array[i] - median1);
        }

        if(n!=1){
                long median2 = array[n/2-1];
                for(int i = 0;i < n;i++){//i=0,1,2,,,,n-1 で動作
                ans2 += Math.abs(array[i] - median2);
            } 
        }



        System.out.println(ans1>ans2?ans2:ans1);

    }
}

Measured memory_bytes: 84152
let () = Scanf.scanf "%d %d\n" @@ fun n m ->
  let acss = Array.init m @@ fun _ ->
    Scanf.scanf "%d %d\n" @@ fun a b ->
      a,
      Array.fold_left ( lor ) 0 @@
      Array.init b @@ fun _ -> Scanf.scanf "%d " @@ fun c -> 1 lsl (c - 1) in
  let dp = Array.make (1 lsl n) 1145141919 in
  dp.(0) <- 0;
  for i = 0 to (1 lsl n) - 1 do
    Array.iter (fun (a, cs) ->
      dp.(i lor cs) <- min dp.(i lor cs) (a + dp.(i))) acss
  done;
  Printf.printf "%d\n" @@
  if dp.((1 lsl n) - 1) = 1145141919
  then -1
  else dp.((1 lsl n) - 1)



Measured memory_bytes: 2688
import java.util.*;
import static java.lang.Integer.*;
import static java.lang.System.*;

public class Main {
	public static boolean[] node;
	public static int n;
	public static int m;
	public static int[][] ab;
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		n = parseInt(sc.next());
		m = parseInt(sc.next());
		ab = new int[m][2];
		for(i=0;i<m;i++) {
			ab[i][0] = parseInt(sc.next());
			ab[i][1] = parseInt(sc.next());
		}
		sc.close();
		int cnt=0;
		for (i = 0; i < m; i++) {
			node = new boolean[n];
			chkBridge(1, i);
			boolean f=false;
			for (j = 0; j < n; j++) {
				if(!node[j]) {
					f=true;
					break;
				}
			}
			if(f)cnt++;
		}
		out.println(cnt);
	}
	public static void chkBridge(int nd, int skip) {
		if(node[nd-1]) return;
		node[nd-1]=true;
		for (int i = 0; i < m; i++) {
			if(i==skip) continue;
			if(ab[i][0]==nd) chkBridge(ab[i][1], skip);
			if(ab[i][1]==nd) chkBridge(ab[i][0], skip);
		}
	}
}


Measured memory_bytes: 22444
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REPR(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define FOR(i, n, m) for (ll i = (n); i < (m); ++i)
#define FORR(i, n, m) for (ll i = (m) - 1; i >= (n); --i) 
#define FORE(x, xs) for (auto &x: (xs))
#define ALL(v) v.begin(), v.end()
#define ZERO(a) memset(a,0,sizeof(a))

const int INF = 1000000009;
const int MOD = 1000000007;
const double EPS = 1e-14;
const double PI = acos(-1);

const int MAX = 1e5+1;

ll N, M, Q;
vi adj[MAX];
int v, d, c;
int colors[MAX];
int dp[11][MAX];
int main() {
  cin >> N >> M;

  REP (j, 11) REP (i, N) dp[j][i] = INF;

  REP (i, M) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    adj[a].push_back(b);
    adj[b].push_back(a);
  }

  cin >> Q;
  REPR (i, Q) {
    cin >> v >> d >> colors[i];
    v--;
    dp[d][v] = i;
  }

  FORR (j, 1, 11) {
    REP  (i, N) {
      dp[j-1][i] = min(dp[j-1][i], dp[j][i]);
      REP (k, adj[i].size()) dp[j-1][adj[i][k]] = min(dp[j-1][adj[i][k]], dp[j][i]);
    }
  }

  REP (i, N) {
    int ans = dp[0][i];
    if (ans == INF) cout << 0 << endl;
    else cout << colors[ans] << endl;
  }

  return 0;
}

Measured memory_bytes: 11128
import Data.Array.IO
import Control.Applicative
import Data.List
import Control.Monad

getLineN :: Int -> IO [String]
getLineN n = replicateM n getLine

getNum = read <$> getLine :: IO Int
getNumList = map read.words <$> getLine :: IO [Int]

main = do
    [h,w] <- getNumList
    canvas <- getLineN h
    putStrLn.judge $ evaluate canvas h w
    
evaluate cs h w = all (== True) $ map f [(x,y) | x <- [0..h-1], y <- [0..w-1]] where
    f (x,y) = if cs .!! (x,y) == '.' then True else any (\pos -> cs .!! pos == cs .!! (x,y)) [(x-1,y),(x+1,y),(x,y+1),(x,y-1)]
    (.!!) cs (x,y) = if (x < 0 || x >= h || y < 0 || y >= w) then 'a' else (cs !! x) !! y    

judge True = "Yes"
judge False = "No"

Measured memory_bytes: 1020
#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
         string k;
         cin>>k;
         for(int i=0;i<k.size();i++)
         {
             if(k[i]=='?')
             {
                 k[i]='D';
             }
         }
         cout<<k<<endl;
        }




Measured memory_bytes: 3720
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep3(i,a,b) for(ll i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pq priority_queue
#define pb push_back
#define eb emplace_back
#define veci vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define vec2(a,b) vector<vec>(a,vec(b))
#define vec2ll(a,b) vector<vec>(a,vecll(b))
#define vec3(a,b,c) vector<vector<vec>>(a,vec2(b,c))
#define vec3ll(a,b,c) vector<vector<vecll>>(a,vec2ll(b,c))
#define fi first
#define se second
#define all(c) begin(c),end(c)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define lb(c,x) distance(c.begin(),lower_bound(all(c),x))
#define ub(c,x) distance(c.begin(),upper_bound(all(c),x))


using namespace std;
int in() {int x;cin>>x;return x;}
ll lin() {ll x;cin>>x;return x;}
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;}
template<class T> inline void print(pair<T,T> p){cout<<"("<<p.first<<","<<p.second<<") ";}
//template<class T> inline void print(vector<pair<T,T>> v){for(auto e:v)print(e); cout<<endl;}
//template<class T> inline void print(T v){for(auto e:v)cout<<e<<" ";cout<<endl;}
template<typename T>
istream& operator >> (istream& is, vector<T>& vec){
    for(T& x:vec) is >> x;
    return is;
}
const ll INF=1e9+7;

int main()
{
    ll h,w,k;
    cin >> h >> w >> k;
    vector<vector<char>> s(h,vector<char>(w,0));
    rep(i,h){
        rep(j,w){
            cin >> s[i][j];
        }
    }
    ll ans=INF;
    for(ll i=0;i<(1<<(h-1));i++){
        ll cnt=1;
        ll cnt_1=0;
        rep(j,h-1){
            if((i>>j) & 1){
                cnt++;
            }
        }
        vector<ll> a(cnt,0);
        ll bef=-1;
        bool ok=true;
        rep(j,w){
            ll num=0;
            ll r=s[0][j]-'0';
            a[num]+=r;
            for(ll t=0;t<h-1;t++){
                if((i>>t) & 1){
                    num++;
                }
                ll v=s[t+1][j]-'0';
                a[num]+=v;
            }
            bool flag=true;
            for(ll t=0;t<cnt;t++){
                if(a[t]>k){
                    flag=false;
                    break;
                }
            }
            /*cout << cnt << " ";
            rep(t,cnt){
                cout << a[t];
            }*/
            if(flag){
                continue;
            }
            else{
                cnt_1++;
                j--;
                if(j==bef){
                    ok=false;
                    break;
                }
                bef=j;
                a=vector<ll>(cnt);
            }
            
        }
        if(!ok) continue;
        //cout << endl;
        ans=min(ans,cnt-1+cnt_1);
        
    }
    cout << ans << endl;
    return 0;
} 


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <bitset>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <cstring>
#include <utility>
#include <vector>
#include <complex>
#include <valarray>
#include <fstream>
#include <cassert>
#include <cmath>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>

#define _overload(a, b, c, d, ...) d
#define _rep1(X, A, Y) for (int (X) = (A);(X) <= (Y);++(X))
#define _rep2(X, Y) for (int (X) = 0;(X) < (Y);++(X))
#define rep(...) _overload(__VA_ARGS__, _rep1, _rep2)(__VA_ARGS__)
#define rrep(X,Y) for (int (X) = Y-1;(X) >= 0;--(X))
#define all(X) (X).begin(),(X).end()
#define _size(X) (int)((X).size())
#define mod(n, m) (((n)%(m)+(m))%m)
#define fi first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> Pii;
typedef pair<ll,ll> Pll;
const int INFINT = 1 << 30;                          // 1.07x10^ 9
const ll INFLL = 1LL << 60;                          // 1.15x10^18
const double EPS = 1e-10;
const int MOD = 1000000007;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};

const int MAX_N = 100000;
int N;
int a[MAX_N], b[MAX_N];
int match[MAX_N];

vector<int> G[MAX_N];

bool dfs(int par, int v) {
    for (int i = 0; i < G[v].size(); ++i) {
        if (G[v][i] != par) {
            if (!dfs(v, G[v][i])) {
                return false;
            }
        }

    }

    if (match[v] < 0) {
        if (par < 0 || match[par] >= 0) return false;
        else match[v] = match[par] = v;
    }

    return true;
}

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

  cin >> N;
  rep(i, N-1) cin >> a[i] >> b[i];
  rep(i, N-1) { 
      --a[i]; --b[i]; 
      G[a[i]].push_back(b[i]);
      G[b[i]].push_back(a[i]);
  }


  memset(match, -1, sizeof(match));
  if (dfs(-1, 0)) {
      cout << "Second" << endl;
  } else {
      cout << "First" << endl;
  }
 
  return 0;
}


Measured memory_bytes: 7040
#include <bits/stdc++.h>
#include <array>
#define FOR(i,a,b) for(int i=(a);i<=(b);++i) 
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i) 
#define REP(i,n) for(int i=0;i<(n);++i)
#define RREP(i,n) for(int i=(n);i>0;--i)
#define CI cin>> 
#define CO cout<<
#define EN <<endl 
#define all(x) (x).begin(),(x).end() 
using namespace std;
template <typename T> istream & operator >> (istream & is, vector<T> & vec) { for (T& x : vec) is >> x; 	return is; }
using ll = long long;
using VI = vector<int>;

int main() {
	int n; CI n;
	vector<double> a(n); vector<string> b(n);
	double ans = 0;
	REP(i, n) {
		CI a[i] >> b[i];
		if (b[i] == "JPY")ans += a[i];
		else ans += 380000 * a[i];
	}

	CO ans EN;

	return 0;
}


Measured memory_bytes: 256
import java.util.*;

class Main{
    public static void main(String[]args){
		Scanner sc = new Scanner(System.in);
		int x = sc.nextInt();
		int y = sc.nextInt();
		int z = sc.nextInt();
		int retint = 0;
		x -= z;
		for(;x>=0;){
			retint++;
			x = x - y - z;
		}
		retint--;
		System.out.println(retint);
    }
}


Measured memory_bytes: 23764
#include <iostream>
#include <stdlib.h>
using namespace std;


struct robot{
    int X;
    int L;
    int XprL;
    int XmiL;
};

void swap(robot* a,robot* b){
    robot t=*b;
    *b=*a;
    *a=t;
}

int partition(robot* R,int left,int right){
    int i=left-1;
    for(int j=left;j<=right-1;j++){
        if(R[j].XprL<=R[right].XprL){
            i++;
            swap(&R[j],&R[i]);
        }
    }
    swap(&R[i+1],&R[right]);
    return i+1;
}

void qsort(robot *R,int Left,int Right){
    if(Left<Right){
        int middle=partition(R,Left,Right);
        qsort(R,Left,middle-1);
        qsort(R,middle+1,Right);
    }
}

int main(){
    int N;
    cin>>N;
    robot R[N];
    for(int i=0;i<N;i++){
        cin >> R[i].X >>R[i].L;
        R[i].XprL=R[i].X+R[i].L;
        R[i].XmiL=R[i].X-R[i].L;
    }

    qsort(R,0,N-1);

    int count=1;
    int comp=R[0].XprL;
    for(int i=0;i<N;i++){
        if((comp)<=(R[i].XmiL)){
            count ++;
            comp=R[i].XprL;
        }
    }

    cout << count;
    return 0;
}

Measured memory_bytes: 1792
use std::cmp;
use std::collections::*;

pub struct Scanner {
    line: Vec<String>,
    idx: usize,
}

#[allow(dead_code)]
impl Scanner {
    fn new() -> Scanner {
        return Scanner {
            line: vec![],
            idx: 0,
        };
    }
    fn next<T: std::str::FromStr>(&mut self) -> T {
        if self.idx == self.line.len() {
            let mut buffer = String::new();
            std::io::stdin().read_line(&mut buffer).ok();
            let a: Vec<&str> = buffer.trim().split(' ').collect();
            self.line = a.iter().map(|&s| String::from(s)).collect();
            self.idx = 0;
        }
        let ret: T = self.line[self.idx].parse::<T>().ok().expect("Parse error.");
        self.idx += 1;
        ret
    }
    fn next_string(&mut self) -> Vec<char> {
        let s: String = self.next();
        return s.chars().collect::<Vec<char>>();
    }
    fn next_vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        let mut v: Vec<T> = Vec::with_capacity(n);
        for _i in 0..n {
            v.push(self.next());
        }
        v
    }
}


fn main(){
    let mut scan = Scanner::new();
    let x: u64 = scan.next();

    let mut m: u64 = 100;
    let mut ans = 0;

    while m < x {
        ans += 1;
        m += m / 100;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2128
#include<bits/stdc++.h>
using namespace std;
int main(){
    int k;
    cin>>k;
    queue<string>lun;
    string s={'0'};
    for(int i=0;i<9;i++){
        s[0]++;
        lun.push(s);
    }
    for(int i=1;i<k;i++){
        string lf=lun.front();
        int ls=lf.size();
        if(lf[ls-1]=='0'){
            lun.push(lf+'0');
            lun.push(lf+'1');
        }
        else if(lf[ls-1]=='9'){
            lun.push(lf+'8');
            lun.push(lf+'9');
        }
        else{
            for(char j=lf[ls-1]-1;j<=lf[ls-1]+1;j++)lun.push(lf+j);
        }
        lun.pop();
    }
    cout<<lun.front()<<endl;
}

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

int main(){
  int N;
  cin >> N;
  
  int index=64;
  for (int i=0; i<7; i++){
    if (N/index>=1){
      break;
    }
    index/=2;
  }
  cout << index << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<ctime>
#include<string>
#include<cstring>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<bitset>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;

#define PI 3.141592653589793238462643383279
#define mod 1000000007LL
#define rep(i, n) for(i = 0;i < n;++i)
#define rep1(i, n) for(i = 1;i < n;++i)
#define per(i, n) for(i = n - 1;i > -1;--i)
#define int(x) int x; scanf("%d",&x)
#define int2(x, y) int x, y; scanf("%d%d",&x, &y)
#define int3(x, y, z) int x, y, z; scanf("%d%d%d",&x, &y, &z)
#define int4(v, x, y, z) int v, x, y, z; scanf("%d%d%d%d", &v, &x, &y, &z)
#define int5(v, w, x, y, z) int v, w, x, y, z; scanf("%d%d%d%d%d", &v, &w, &x, &y, &z)
#define ll2(x, y) ll x, y; cin >> x >> y;
#define scn(n, a) rep(i, n)cin >> a[i]
#define sc2n(n, a, b) rep(i, n)cin >> a[i] >> b[i]
#define pri(x) cout << (x) << "\n"
#define pri2(x, y) cout << (x) << " " << (y) << "\n"
#define pri3(x, y, z) cout << (x) << " " << (y) << " " << (z) << "\n"
#define pb push_back
#define mp make_pair
#define all(a) (a).begin(),(a).end()
#define endl "\n"
#define kabe puts("---------------------------")
#define kara puts("")
#define debug(x) cout << " --- " << (x) << "\n"
#define debug2(x, y) cout << " --- " << (x) << " " << (y) << "\n"
#define debug3(x, y, z) cout << " --- " << (x) << " " << (y) << " " << (z) << "\n"
#define X first
#define Y second
#define eps 0.0001
#define prid(x) printf("%.15lf\n", x)

int solve(int n, int cnt){
  if(n == 6174)return cnt;
  int a[4] = {n % 10, (n / 10) % 10, (n / 100) % 10, n / 1000};
  sort(a, a + 4);
  int mi = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
  int ma = a[3] * 1000 + a[2] * 100 + a[1] * 10 + a[0];
  return solve(ma - mi, cnt + 1);
}

signed main(void){
  int i, j;
  for(int testcase = 0;testcase >= 0;testcase++){
    int(n);
    if(!n)break;
    if(n % 1111 == 0)puts("NA");
    else pri(solve(n, 0));

//*/

//*/ break;
  }
  return 0;
}

Measured memory_bytes: 3200
#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 all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const int inf = 1001001001;
const int mod = 1000000007;

vector<P> g[100005];
vector<ll> ans(100005);
vector<bool> vi(100005);

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	rep(i, n - 1) {
		int a, b, c;
		cin >> a >> b >> c;
		a--; b--;
		g[a].emplace_back(b, c);
		g[b].emplace_back(a, c);
	}
	int q, k;
	cin >> q >> k;
	k--;
	queue<int> que;
	que.push(k);
	ans[k] = 0;
	vi[k] = true;
	while (que.size()) {
		int a = que.front(); que.pop();
		for (auto& c : g[a]) {
			if (vi[c.first]) continue;
			vi[c.first] = true;
			ans[c.first] = ans[a] + (ll)c.second;
			que.push(c.first);
		}
	}
	rep(ri, q) {
		int x, y;
		cin >> x >> y;
		x--; y--;
		ll j_ans = ans[x] - ans[k];
		j_ans += ans[y] - ans[k];
		printf("%lld\n", j_ans);
	}
	return 0;
}


Measured memory_bytes: 8820
#include <stdio.h>
#include <algorithm>
using namespace std;

int main()
{
	int n,i;
	long long sum=1;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
	{
		sum*=i;
		sum%=(1000000000+7);
	}
	printf("%lld\n",sum);
	return 0;
}


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

using namespace std;

int n;
int a[1000][1000];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=2;i++)
	for(int j=1;j<=n;j++)
	scanf("%d",&a[i][j]);
	
	for(int i=n-1;i>=1;i--)
	a[2][i]+=a[2][i+1];
	
	a[1][n]+=a[2][n];
	
	for(int i=n-1;i>=1;i--)
	a[1][i]+=max(a[2][i],a[1][i+1]);
	
	cout<<a[1][1];
	return 0;
}

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

int main()
{
    int A, B;
    cin >> A >> B;
    if (A % 3 == 0 || B % 3 == 0 || (A + B) % 3 == 0)
    {
        cout << "Possible" << endl;
    }
    else
    {
        cout << "Impossible" << endl;
    }
    return 0;
}

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

using namespace std;

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

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int N, K; cin >> N >> K;

	cout << (N % K == 0 ? 0 : 1) << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n)  for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define deb(x) cerr << #x <<": " << x << '\n';
#define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;
typedef long double ld;
typedef long long ll;

int main(){
    ios;
    int n; cin >> n;
    string s; cin >> s;
    if(n%2 != 0)cout << "No";
    else{
         bool flag = true;
        rep(i,n/2){
            if(s[i] == s[i+ n/2]);
            else flag = false;
        }
        cout << (flag? "Yes" : "No");
    }
    return 0;
    
}



Measured memory_bytes: 256
import Control.Monad

type Op = [String]

processTransform :: String -> [Op] -> IO String
processTransform str [] = do return str
processTransform str (op:ops) = do
  nextStr <- transformation str op
  processTransform nextStr ops

transformation :: String -> Op -> IO String
transformation str ["print", sa, sb] = do
  let [a, b] = map read [sa, sb]
  putStrLn $ take (b-a+1) . drop a $ str
  return str
transformation str ["reverse", sa, sb] = do
  let [a, b] = map read [sa, sb]
  return ((take a str) ++ (reverse $ take (b-a+1) . drop a $ str) ++ (drop (b+1) str))
transformation str ["replace", sa, sb, p] = do
  let [a, b] = map read [sa, sb]
  return ((take a str) ++ p ++ (drop (b+1) str))

main :: IO ()
main = do
  str <- getLine
  n <- readLn
  oplist <- replicateM n $ fmap words getLine
  processTransform str oplist
  return ()

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

#define mod (1000000007)
#define MAXN (20000010)

int h, w, k;
int fact[MAXN];
int rfac[MAXN];

int powmod(int a, int b) {
    int ret = 1;
    for (; b; b >>= 1) {
        if (b & 1) {
            ret = 1ll * ret * a % mod;
        }
        a = 1ll * a * a % mod;
    }
    return ret;
}

int main() {
    scanf("%d%d%d", &h, &w, &k);
    fact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = 1ll * fact[i - 1] * i % mod;
    }
    rfac[MAXN - 1] = powmod(fact[MAXN - 1], mod - 2);
    for (int i = MAXN - 2; i >= 0; --i) {
        rfac[i] = 1ll * (i + 1) * rfac[i + 1] % mod;
    }
    int inv6 = (mod + 1) / 6;
    int ans = 0;
    for (int x = 0; x <= h; ++x) {
        int y = k - x;
        if (y < 0 || y > w) continue;
        int tmp =
                1ll * fact[x + y + 1] % mod * (((2ll * x * y % mod + 3ll * x % mod) % mod + 3ll * y % mod) % mod + 6) %
                mod * rfac[x] % mod * rfac[y] % mod * inv6 % mod;
        tmp = (tmp - 1ll * fact[k] * rfac[x] % mod * rfac[y] % mod + mod) % mod;
        tmp = 1ll * tmp * fact[h] % mod * rfac[h - x] % mod;
        tmp = 1ll * tmp * fact[w] % mod * rfac[w - y] % mod;
        ans = (ans + tmp) % mod;
    }
    printf("%d\n", ans);
    return 0;
}

Measured memory_bytes: 156544
count=Array.new(26)
for i in 0..25 do
  count[i]=0
end

while str=gets do
  i=0
  str.downcase!
  ("a".."z").each do |let|
    count[i]+=str.count(let)
    i+=1
  end
end

j=0
("a".."z").each do |let2|
  puts "#{let2} : #{count[j]}"
  j+=1
end

Measured memory_bytes: 8632
#include<bits/stdc++.h>
using namespace std;
long long n,a[100005],b[100005],c[100005];
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i]>>b[i];
	memset(c,0,sizeof(c));
	for(int i=n-1;i>=0;i--)
	{
		c[i]+=c[i+1];
		a[i]+=c[i];
		long long add=((((a[i]+b[i]-1)/b[i])*b[i])-a[i]);
		c[i]+=add;
	}
	cout<<c[0]<<endl;
}

Measured memory_bytes: 2560