akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
#define range(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,b) for(int i = 0; i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define show(x)  cerr << #x << " = " << (x) << endl;
using namespace std;

template<typename T>
ostream& operator << (ostream& os, vector<T>& v){
	rep(i,v.size()){ os << v[i] << (i == v.size() - 1 ? "" : " "); } return os;
}
template<typename T>
istream& operator >> (istream& is, vector<T>& v){
	for(T& x: v){ is >> x; } return is;
}

struct Data{
	int t, c, sum;
	Data(int t, int c, int sum = 0) : t(t), c(c), sum(sum) { }
	bool operator < ( const Data &right ) const {
		return t < right.t;
	}
};

void returnLane(int time, queue<Data>& a, queue<Data>& b){
	vector<Data> nextLane;
	while(not a.empty() and time >= a.front().t + a.front().sum){
		auto p = a.front(); a.pop();
		p.c--;
		p.sum = time;
		if(p.c == 0) continue;
		nextLane.emplace_back(p);
	}
	sort(all(nextLane));
	for(auto i : nextLane) b.emplace(i);
}

int main(){
	int n;
	while(cin >> n,n){
		vector<pair<int, int>> a(n);
		rep(i,n){
			cin >> a[i].first >> a[i].second;
			a[i].second *= 2;
		}

		queue<Data> lane1, lane2;

		vector<pair<int, int>> tmp(all(a));
		sort(all(tmp));
		for(auto i : tmp) lane1.emplace(i.first, i.second, 0);

		int ans = 0;
		while(not lane1.empty() or not lane2.empty()){
			ans++;
			returnLane(ans, lane1, lane2);
			returnLane(ans, lane2, lane1);
		}
		cout << ans << endl;
	}
}



Measured memory_bytes: 3092
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <functional>

using namespace std;

#define fst first
#define scd second
#define PB push_back
#define MP make_pair
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define omajinai ios::sync_with_stdio(false);cin.tie(0)
#define rep(i,x) for(int i=0;i<(int)(x);++i)
#define rep1(i,x) for(int i=1;i<=(int)(x);++i)

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

template<typename T>T& max(T&a,T&b){if(a>=b)return a;return b;}
template<typename T>T& min(T&a,T&b){if(a<b)return a;return b;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>T get(){T a;cin>>a;return a;}
template<typename T>T rev(T a){reverse(all(a));return a;}
template<typename T>vector<T>&sort(vector<T>&a){sort(all(a));return a;}

const int inf = 1e9;
const ll linf = 3e18;
const double eps = 1e-9;

#define int unsigned int

int p[70010];
int j[70010];

signed main()
{
   int n;
   while (cin >> n, n) { 
       int a = 0;

       rep(i, n) {
           cin >> p[i];
           a += p[i];
       }

       rep(i, n - 1) {
           cin >> j[i];
       }

       sort(j, j + n - 1, greater<int>());

       int ans = a * n;

       rep(i, n - 1) {
           a += j[i];
           n -= 1;
           int v = a * n;
           ans = max(ans, v);
       }

       cout << ans << endl;
   }
}

Measured memory_bytes: 1680
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> P;
map <int,int> mp;
vector<int> V;
#define INF (1<<29)
#define INFLL (1ll<<58)
#define EPS (1e-10)
static const int MAX=1e5;
static const int MOD=1e9+7;
static const int NMAX=1000;
static const int MMAX=1000;
int dx[4]={0,1,0,-1},dy[4]={-1,0,1,0};
ll N,M,k;
int main(){
    cin.tie(0);  ios::sync_with_stdio(false);
    
    cin>>N>>M>>k;

    for(int i=0;i<=M;i++){
        for(int j=0;j<=N;j++){
            if(j*(M-i)+i*(N-j)==k){
                
                cout<<"Yes"<<"\n";
                return 0;
            }
        }
    }
    cout<<"No"<<"\n";
    return 0;
}


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

int main()
{
  int n, k, ans = 0;
  cin >> n >> k;
  vector<bool> flag;
  for(int i=0; i<n; i++)
    flag.push_back(true);
  
  for(int i=0; i<k; i++)
  {
    int d;
    cin >> d;
    for(int j=0; j<d; j++)
    {
      int a;
      cin >> a;
      flag[--a] = false;
    }
  }
  
  for(int i=0; i<n; i++)
  {
    if(flag[i])
      ans++;
  }
  
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 3624
#include<bits/stdc++.h>
using namespace std;
int main(){
	int a , b , c , d ,l1=0,l2=0,l=0 ;
	scanf("%d%d%d%d",&a,&b,&c,&d);
	if(a>=c)
	l1=a;
	else 
	l1=c;
    if(b<=d)
	l2=b;
	else
	l2=d;
	l=l2-l1;
	if(l<=0)
	printf("0");
	else
	printf("%d",l);
	
}

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

using namespace std;

void solve(void)
{
	int n;
	cin >> n;
	int ans = 0;
	int acnt = 0, bcnt = 0, gachiryoto = 0;
	while(n--)
	{
		string s;
		cin >> s;
		if (s.front() == 'B' && s.back()  == 'A') gachiryoto++;
		else if (s.front() == 'B') bcnt++;
		else if (s.back()  == 'A') acnt++;
		for (int i = 0; i < s.size()-1; i++)
		{
			if (s[i] == 'A' && s[i+1] == 'B') ans++;
		}
	}
	//cout << ans << ' ' << acnt << ' ' << bcnt << ' ' << gachiryoto << endl;
	ans += min(acnt, bcnt);
	if (gachiryoto)
	{
		ans += gachiryoto - (acnt == 0 && bcnt == 0);
	}
	cout << ans << endl;
}

int main()
{
	solve();
	//cout << "yui(*-v・)yui" << endl;
	return 0;
}


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

int main()
{
  string s;
  cin >> s;
  int n=s.length();
  long long int ans=0;

  for(int i=0;i<(1<<(n-1)); i++){
    long long int sum=0;
    long long int tmp=s[0] -'0';
    for(int j=0;j<n-1; j++){
      if(i & (1 << j)){
	sum += tmp;
	tmp = 0;
      }
      tmp = tmp*10 +s[j+1]-'0';
    }
    sum += tmp;
    ans += sum;
  }
  cout<< ans <<endl;
}


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

const long mod = 1000000007;
long fact[100001];

void calc_fact()
{
  fact[0] = 1;
  for (int i = 1; i <= 100000; i++)
    fact[i] = fact[i - 1] * i % mod;
}

int main()
{
  long N, M;
  cin >> N >> M;
  calc_fact();
  if (1 < abs(N - M))
    cout << 0 << endl;
  else if (abs(N - M) == 1)
  {
    cout << fact[N] * fact[M] % mod << endl;
    return 0;
  }
  else
    cout << fact[N] * fact[M] % mod * 2 % mod << endl;
  return 0;
}

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

int inf = 10000001;

int main(){
    int n, m;cin >> n >> m;
    vector<int> a(m);
    vector<int> b(m);
    vector<int> c(m);
    vector<vector<int> > dp(n+1, vector<int>(n+1));
    for(int i = 0; i<m;++i){
        cin >> a[i] >> b[i] >> c[i];
        a[i]--;b[i]--;
    }
    for(int i = 0; i<n;++i){
        for(int l = 0; l < n; ++l){
            if(i == l){dp[i][l] = 0;}
            else{dp[i][l] = inf;}
        }
    }
    for(int i = 0; i<m;++i){
        dp[a[i]][b[i]] = min(dp[a[i]][b[i]], c[i]);
        dp[b[i]][a[i]] = min(dp[b[i]][a[i]], c[i]);
    }
    for(int k = 0; k<n;++k){
        for(int i = 0; i<n;++i){
            for(int l = 0; l<n; ++l){
                dp[i][l] = min(dp[i][l], dp[i][k]+dp[k][l]);
            }
        }
    }
    int ans = m;
    int j = 0;
    for(int i = 0; i<m; ++i){
        j = 0;
        for(int l = 0; l<n; ++l){
            if(dp[l][a[i]] + c[i] == dp[l][b[i]]){j = 1;}   
        }
        if(j == 1){ans--;}
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <complex>

using namespace std;
typedef long long ll;

typedef double R;
typedef complex<R> P;

R cross(const P &a, const P &b) { return imag(conj(a)*b); }
R dot(const P &a, const P &b) { return real(conj(a)*b); }

struct C {
    P p;
    R r;
    C () {};
    C (P p, R r) : p(p), r(r) {};
};

C c[2];
int solve() {
    for (int i = 0; i < 2; i++) {
        R x, y, r;
        cin >> x >> y >> r;
        c[i] = C(P(x, y), r);
    }
    R dist = abs(c[0].p - c[1].p);
    if (c[0].r > c[1].r + dist) return 2;
    if (c[1].r > c[0].r + dist) return -2;
    if (c[0].r + c[1].r >= dist) return 1;
    return 0;
}


int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cout << solve() << endl;
    }
    return 0;
}

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

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

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

    char inp[n + 3];
    scanf("%s", inp);

    int ans = 0;
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 10; j++)
            for (int k = 0; k < 10; k++) {
                char num[3];
                num[0] = i + '0';
                num[1] = j + '0';
                num[2] = k + '0';

                int cnt = 0;
                for (int p = 0; p < n; p++) {
                    if (inp[p] == num[cnt]) {
                        cnt++;
                        if (cnt == 3)
                            break;
                    }
                }

                if (cnt == 3)
                    ans++;
            }
    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

fn main() {
    input!{
        a: usize,
        b: usize,
        c: usize,
        x: usize,
    }

    let mut cnt = 0;
    for i in 0..(a+1) {
        for j in 0..(b+1) {
            for k in 0..(c+1) {
                let sum = 500 * i + 100 * j + 50 * k;
                if sum == x {
                    cnt += 1
                }
            }
        }
    }
    println!("{}", cnt);
}


Measured memory_bytes: 4352
#!/usr/bin/env python3
import sys
import collections as cl


def II(): return int(sys.stdin.readline())


def MI(): return map(int, sys.stdin.readline().split())


def LI(): return list(map(int, sys.stdin.readline().split()))


def main():
    N = input()

    print("No" if N[0] == N[1] == N[2] else "Yes")


main()


Measured memory_bytes: 64988
def main():
  import sys
  input=sys.stdin.readline
  n,q=map(int,input().split())
  s=input()
  
  ac=[0]*(n+1)
  for i in range(1,n):
    if s[i-1]=='A' and s[i]=='C':
      ac[i+1]=ac[i]+1
    else:
      ac[i+1]=ac[i]  
  
  for i in range(q):
    l,r=map(int,input().split())
    if l==1:
      ans=ac[r]-ac[l-1]
    elif s[l-2]=='A' and s[l-1]=='C':
      ans=ac[r]-ac[l-1]-1
    else:
      ans=ac[r]-ac[l-1]
    print(ans)
    
if __name__=='__main__':
  main()
    

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

int main(){
    int h, w;
    cin >> h >> w;
    vector<string> f(h);
    rep(i,h) cin >> f[i];

    vector<vector<int>> x(h, vector<int>(w)), y(h, vector<int>(w));
    rep(i,h){
        int cnt = 0;
        vector<int> itr;
        rep(j,w){
            if(f[i][j] == '.'){
                cnt++;
                itr.push_back(j);
            }
            else{
                for(auto p : itr) x[i][p] = cnt;
                cnt = 0;
                itr.clear();
            }
        }
        if(!itr.empty()) for(auto p : itr) x[i][p] = cnt;
    }

    rep(j,w){
        int cnt = 0;
        vector<int> itr;
        rep(i,h){
            if(f[i][j] == '.'){
                cnt++;
                itr.push_back(i);
            }
            else{
                for(auto p : itr) y[p][j] = cnt;
                cnt = 0;
                itr.clear();
            }
        }
        if(!itr.empty()) for(auto p : itr) y[p][j] = cnt;
    }
    int ans = 0;
    rep(i,h) rep(j,w) ans = max(ans, x[i][j] + y[i][j] - 1);
    cout << ans << endl;
}

Measured memory_bytes: 42244
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
#define maxn 101000

int main()
{
	LL n;
	scanf("%lld",&n);
	if (n&1) printf("%lld\n",n*2);
	else printf("%lld\n",n);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<stdio.h>
using namespace std;
#define endl ("\n")
#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define f(i,s,n)        for(int i=s;i<n;i++)
int si= 2000005;
void io()
{
    ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
}
int dp[200005];
int a[200005];
int k;
int abc(int n)
{
    dp[1]=abs(a[1]-a[0]);
    for(int i=2;i<n;i++)
    {
        int g=INT_MAX;
        for(int j=1;j<=k;j++)
        {
            if(i-j>=0)
            {
             g=min(g,dp[i-j]+abs(a[i-j]-a[i]));
            }
        }
        dp[i]=g;
    }
    return dp[n-1];
}
void solve()
{
  int n;
  cin>>n;
  cin>>k;
  f(i,0,n)
  cin>>a[i];
  memset(dp,0,sizeof(dp));
  cout<<abc(n)<<endl;
}
int32_t main()
{
    io();
    solve();
    return 0;
}

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

int a,b,c,d;

int main(){
    while(cin>>a>>b>>c>>d) {
        if(a+b>c+d){
            cout<<"Left"<<endl;
        }
        else if(a+b<c+d){
            cout<<"Right"<<endl;
        }
        else {
            cout<<"Balanced"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using LL  = long long;
using VI  = vector<LL>;
using VVI = vector<VI>;
using VB  = vector<bool>;
using VS  = vector<string>;
using PII = pair<LL, LL>;
using VP  = vector<PII>;
#define PB           push_back
#define MP           make_pair
#define SZ(a)        LL((a).size())
#define EACH(x, c)   for (auto x : (c))
#define ALL(c)       (c).begin(), (c).end()
#define REVERSE(c)   reverse(ALL(c))
#define SORT(c)      stable_sort(ALL(c))
#define RSORT(c)     stable_sort((c).rbegin(), (c).rend())
#define FSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first < y.first;});
#define FRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.first > y.first;});
#define SSORT(c)     stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second < y.second;});
#define SRSORT(c)    stable_sort(ALL(c), [] (auto& x, auto& y) {return x.second > y.second;});
#define FOR(i, a, b) for (LL i = (a); i < (b); ++i)
#define REP(i, n)    FOR(i, 0, n)
#define $(x) {cout << #x << " = " << (x) << endl;}

const LL MOD = 1e9 + 7;
inline LL mod_add(LL a, LL b) { return (a + b) % MOD; }
inline LL mod_sub(LL a, LL b) { return (a + MOD - b) % MOD; }
inline LL mod_mul(LL a, LL b) { return ((a % MOD) * (b % MOD)) % MOD; }
LL mod_bipow(LL x, LL y) {   // x^y by bisection method
    if (y == 0) return 1;
    else if (y == 1) return x % MOD;
    else if (y % 2 == 0) {
        LL val = mod_bipow(x, (LL)(y / 2));
        return mod_mul(val, val);
    } else {
        LL val = mod_bipow(x, (LL)(y / 2));
        return mod_mul(mod_mul(val, val), x);
    }
}
LL mod_inv(LL x) { return mod_bipow(x, MOD - 2); }   // x^{-1} = x^{MOD-2} (MOD: prime number)
LL mod_div(LL a, LL b) { return mod_mul(a, mod_inv(b)); }   // a/b = a*b^{-1}

int main() {
	LL H, W;
    cin >> H >> W;
    vector<VB> A(H, VB(W));
    REP(i, H) {
        string s;
        cin >> s;
        REP(j, W) {
            A[i][j] = s[j] == '.' ? true : false;
        }
    }

    VVI dp(H, VI(W));
    dp[0][0] = 1;
    REP(i, H) {
        REP(j, W) {
            if (!A[i][j]) continue;
            if (j + 1 < W && A[i][j + 1]) {
                dp[i][j + 1] = mod_add(dp[i][j + 1], dp[i][j]);
            }
            if (i + 1 < H && A[i + 1][j]) {
                dp[i + 1][j] = mod_add(dp[i + 1][j], dp[i][j]);
            }
        }
    }
	cout << dp[H - 1][W - 1] << endl;
    return 0;
}


Measured memory_bytes: 8320
#include<cstdio>
#include<cmath>
int main(void){
  double q,x;
  for( ; ; ){
    scanf("%lf",&q);
    if(q == -1) break;
    x = q / 2;
    while(fabs(pow(x,3) - q) >= 0.00001 * q) x = x - ((pow(x,3) - q) / (3 * pow(x,2)));
    printf("%.6f\n",x);
  }
}


Measured memory_bytes: 1136
attrs = Array.new
while line = $stdin.gets
  attrs << line.chomp.split
end

N, K = attrs[0].map{|a| a.to_i}

if N%K ==0 then
  puts 0
elsif N < K then
  a = N
  b = K-N
  puts [a,b].min
elsif N < 2*K then
  a = 2*K-N
  b = N-K
  puts [a,b].min
else
  n = N - (N/(2*K)).to_i * 2 * K
  if n < K then
    a = n
    b = K-n
    puts [a,b].min
  else
    a = 2*K-n
    b = n-K
    puts [a,b].min
  end
end

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

int main(){
  string s;
  cin >> s;
  bool ans = false;
  vector<char> letter(4);
  for(int i = 0;i<4;i++){
    letter.at(i) = s.at(i);
  }
  if(letter.at(0) == letter.at(1) && letter.at(2) == letter.at(3)&& letter.at(0)!=letter.at(2) 
  || letter.at(0) == letter.at(2) && letter.at(1) == letter.at(3)&& letter.at(0)!=letter.at(1)
  ||letter.at(0) == letter.at(3) && letter.at(2) == letter.at(1)&& letter.at(0)!=letter.at(1)){
    ans = true;
  }
  if(ans){
    cout << "Yes" << endl;
  }else cout << "No" << endl;
}


Measured memory_bytes: 256
a, b, c, d = $stdin.gets.chomp.split('').map(&:to_i)

answers = []
answers << "#{a}+#{b}+#{c}+#{d}"
answers << "#{a}+#{b}+#{c}-#{d}"
answers << "#{a}+#{b}-#{c}+#{d}"
answers << "#{a}+#{b}-#{c}-#{d}"
answers << "#{a}-#{b}+#{c}+#{d}"
answers << "#{a}-#{b}+#{c}-#{d}"
answers << "#{a}-#{b}-#{c}+#{d}"
answers << "#{a}-#{b}-#{c}-#{d}"

answers.each do |answer|
  if eval(answer) == 7
    puts answer + "=#{eval(answer)}"
    exit
  end
end


Measured memory_bytes: 1788
#include <bits/stdc++.h>
#ifdef HIRO
#define d(f_, ...) printf((f_), ##__VA_ARGS__)
#else
#define d(f_, ...)
#endif

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector< pair<int, int> > vii;
typedef vector< pair<long long, long long> > vllll;
typedef map<int, int> mii;
typedef map<long long, long long> mllll;
typedef queue<int> qi;
typedef queue< pair<int, int> > qp;
#define mp make_pair
#define pi 3.14159265358979323846
#define MAX max_element
#define MIN min_element
#define all(v) v.begin(), v.end()
#define gt(T) greater<T>()
#define sum(v) accumulate(v.begin(), v.end(), 0)
#define uni(v) do{ \
  sort(v.begin(), v.end()); \
  decltype(v)::iterator result = unique(v.begin(), v.end()); \
  v.erase(result, v.end()); \
}while(0)
#define fi(init, n) for(int i = init; i < n; ++i)
#define fj(init, n) for(int j = init; j < n; ++j)
#define fk(init, n) for(int k = init; k < n; ++k)
#define zero(x) memset(x, 0, sizeof(x))
#define negative(x) memset(x, ~0, sizeof(x))
#define bitsum(x) __builtin_popcount(x)
const ll MOD = 1e9 + 7;
const int INF = 1e9;
const int di[] = { 0, 1, 0, -1 };
const int dj[] = { 1, 0, -1, 0 };

template<typename T>
T gcd(T a, T b) {
	return b ? gcd(b, a % b) : a;
}
template<typename T>
T lcm(T a, T b) {
	return a * b / gcd(a, b);
}
template<typename T>
int finder(vector<T> vec, T number) {
	auto itr = find(vec.begin(), vec.end(), number);
	size_t index = distance(vec.begin(), itr);
	if (index != vec.size()) return 1;
	else return 0;
}
ll frac(ll n){
	if (n == 0) return 1;
	return (n * frac(n - 1)) % MOD;
}
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(int argc, char** argv) {
#ifdef HIRO
  string quiz(argv[1]);
  string id(argv[2]);
  string filename("input/" + quiz + "/" + id + ".txt");
  ifstream fin(filename);
  if (fin.peek() == ifstream::traits_type::eof()) {
    cout << "No input.";
    return 0;
  }
  ifstream cin(filename);
  std::cin.rdbuf(cin.rdbuf());
#endif
  ll ans = 0;
  ll n;
  cin >> n;

  // bottle neck
  ll bn = (ll)2e15, x;
  fi(0, 5) {
    cin >> x;
    chmin(bn, x);
  }
  // 4 + ceil(total / bottle_neck)
  ans = 4 + (n + bn - 1) / bn;
  cout << ans << endl;
  return 0;
}



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

int main(){
  int n;
  cin >> n;
  vector<long long> a(n);
  for(int i=0;i<n;i++)
    cin >> a[i];
  
  long long min=1000000000000000000LL, sum1=a[0], sum2=0;
  for(int i=1;i<n;i++){
    	sum2+=a[i];
  }
  if(abs(sum1-sum2)<min) min=abs(sum1-sum2);
  for(int k=1;k<n-1;k++){
    sum1+=a[k];
    sum2-=a[k];
    if(abs(sum1-sum2)<min) min=abs(sum1-sum2);
  }
  	
  	
  
  cout << min;
  
  
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <list>
#include <string>
#include <stack> // s.top()
#include <bitset>
#include <queue> // s.front()
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define print(x) cout<<(x)<<endl
#define INF10 1001001001 
#define INF5 100000
#define EPS 1e-10



int main() {
	int a, b; cin >> a >> b;
	int mx = a + b;
	mx = max(mx, a - b);
	mx = max(mx, a*b);
	cout << mx << endl;



	return 0;
}


Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: UTF-8 -*-
import time
import sys
import io
import re
import math
import itertools
import collections
#sys.stdin=file('input.txt')
#sys.stdout=file('output.txt','w')
#10**9+7
mod=1000000007
#mod=1777777777
pi=3.141592653589
xy=[(1,0),(-1,0),(0,1),(0,-1)]
bs=[(-1,-1),(-1,1),(1,1),(1,-1)]
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0

#n=int(raw_input())
cnt=0
while 1:
    try:
        n,w,h=map(str,raw_input().split(','))
        b=float(w)/(float(h)**2)
        if b>=25.0:
            cnt=1
            print n
    except:
        if cnt==0:
            print '????????????'
        break
exit()

Measured memory_bytes: 7060
while True:
  try:
    plst = list(map(int, input().split()))
    
    horse = [4, 1, 4, 1, 2, 1, 2, 1]
    min_num = 100000
    min_horse = horse[:]
    
    for _ in range(8):
      #乗車不能人数
      num = sum([max(0, plst[j] - horse[j]) for j in range(8)])
      
      #人数が最小値と等しく、並びの数値が小さければ更新
      if num == min_num and min_horse > horse:
        min_horse = horse[:]
      
      #人数が最小値より小さければ更新
      elif num < min_num:
        min_num = num
        min_horse = horse[:]
      
      #馬を回転
      horse.append(horse.pop(0))

    print(" ".join(map(str, min_horse)))

  except EOFError:
    break


Measured memory_bytes: 5612
#![allow(unused_imports)]
use itertools::Itertools;
use num_traits::clamp;
use ordered_float::OrderedFloat;
use proconio::{fastout, input, marker::*};
use std::cmp::*;
use std::collections::*;
use superslice::*;

#[fastout()]
fn main() {
    input! {
        n: usize, k: usize,
        mut a: [i64; n],
    }
    let m = 1000000007i64;
    let mod_product = |acc: i64, &value: &i64| {
        (acc * value).rem_euclid(m)
    };

    if k == n || k % 2 == 1 && a.iter().all(|v| *v <= 0) {
        a.sort_by_key(|v| -*v);
        let ans = a.iter().take(k).fold(1, mod_product);
        println!("{}", ans);
        return;
    }

    a.sort_by_key(|v| Reverse(v.abs()));
    let mut plus = Vec::new();
    let mut minus = Vec::new();
    for i in 0..n {
        if a[i] >= 0 {
            plus.push(a[i]);
        } else {
            minus.push(a[i]);
        }
    }

    let mut ppos = 0;
    let mut mpos = 0;
    let mut vals = Vec::new();
    let mut retry = false;
    while vals.len() < k {
        if vals.len() < k - 1 && ppos + 1< plus.len() && mpos + 1 < minus.len() {
            if plus[ppos] * plus[ppos+1] < minus[mpos] * minus[mpos+1] {
                vals.push(minus[mpos]);
                vals.push(minus[mpos+1]);
                mpos += 2;
            } else {
                vals.push(plus[ppos]);
                vals.push(plus[ppos+1]);
                ppos += 2;
            }
        } else if vals.len() < k - 1 && mpos + 1 < minus.len() {
            vals.push(minus[mpos]);
            vals.push(minus[mpos+1]);
            mpos += 2;
        } else if ppos < plus.len() {
            vals.push(plus[ppos]);
            ppos += 1;
        } else {
            retry = true;
            break;
        }
    }
    let ans = if !retry {
        vals.iter().fold(1, mod_product)
    } else {
        a.sort_by_key(|v| v.abs());
        assert!(k < n);
        a.iter().take(k).fold(1, mod_product)
    };
    println!("{}", ans);
}


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

int main(){
	string S;
	cin >> S;
	int D=1024;
	for (int i=0;i+2<S.size();i++){
		D=min(D,abs(100*(S[i]-'0')+10*(S[i+1]-'0')+S[i+2]-'0'-753));
	}
	cout << D << endl;

	return 0;
}


Measured memory_bytes: 256
import Data.Char

cntChar x c = length . filter (==c) $ x
cntAlpha x = map (cntChar x) ['a'..'z']

printCnt cntResult = putStr . unlines . zipWith (++) (map ((++ " : ") . (:[])) ['a'..'z']) $ map show cntResult

main =
    getContents >>= printCnt . cntAlpha . map toLower

Measured memory_bytes: 3828
import java.util.ArrayList;
import java.util.*;

class Main{
        public static void main(String[] args){

                ArrayList<String> array = new ArrayList<String>();
                ArrayList<String> arraySub;
                Scanner scan = new Scanner(System.in);

                //scan
                String substring = scan.nextLine();
                int outNum = scan.nextInt();

                for(int i = 0; i < substring.length(); i++){
                        String subText = substring.substring(i);

                        //part of outNum
                        for(int j = 0; j < subText.length() && j < outNum; j++){
                                array.add(subText.substring(0, j+1));
                                //array = new ArrayList<String>(new HashSet<>(array));
                        }
                }

                //hashset
                arraySub = new ArrayList<String>(new HashSet<>(array));

                //sort
                Collections.sort(arraySub);

                //output
                System.out.println(arraySub.get(outNum - 1));

        }
}

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

#define MOD 1000000007
#define ll long long int
#define floop(i,a,b) for(ll i=a;i<b;i++)
#define all(v) v.begin(),v.end()


int solve(){
 
    ll a; cin>>a;
    cout<<a + a*a + a*a*a<<endl;

return 0;
}

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

    ll t; t=1;
    //cin>>t;

    while(t--)
       solve();
    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#ifdef LOCAL
#include "lib/debug.hpp"
#else
#define debug(...) 1
#endif
#define ALL(a) (a).begin(), (a).end()
#define rep(i, n) REP(i, 0, (n))
#define repc(i, n) REPC(i, 0, (n))
#define REP(i, n, m) for (int i = (int)(n); i < (int)(m); i++)
#define REPC(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define REPCM(i, n, m) for (int i = (int)(n); i >= (int)(m); i--)
using namespace std;
using ll = int_fast64_t;
using pr = pair<ll, ll>;
using vll = vector<ll>;
using vpr = vector<pr>;
template<class T> inline bool chmin(T& a, const T& b) { if (a > b) { a = b; return true; } else return false; }
template<class T> inline bool chmax(T& a, const T& b) { if (a < b) { a = b; return true; } else return false; }
struct FenwickTree {
  int N;
  vll bit;
  FenwickTree(int n) : N(n), bit(n+2, 0) {}
  void add(int i, ll a) {
    while(i <= N) {
      bit[i] += a;
      // chmax(bit[i], a);
      i += (i & -i);
    }
  }
  ll sum(int i) {
    ll res = 0;
    while(i > 0) {
      res += bit[i];
      // chmax(res, bit[i]);
      i -= (i & -i);
    }
    return res;
  }
  int lower_bound(ll w) {
    int k = 1;
    while(k <= N) k *= 2;
    k /= 2;
    int x = 0;
    while(k > 0) {
      if(x+k <= N && bit[x+k] < w) {
        w -= bit[x+k];
        x += k;
      }
      k /= 2;
    }
    return x+1;
  }
};

void answer() {
  int n, q;
  string s;
  cin >> n >> s >> q;
  vector<FenwickTree> fts;
  rep(i, 26) {
    fts.emplace_back(FenwickTree(n));
  }
  rep(i, n) {
    fts[s[i]-'a'].add(i+1, 1);
  }
  rep(i, q) {
    int c;
    cin >> c;
    if(c==1) {
      int x;
      char after;
      cin >> x >> after;
      if(s[x-1] != after) {
        fts[s[x-1]-'a'].add(x, -1);
        s[x-1] = after;
        fts[s[x-1]-'a'].add(x, 1);
      }
    } else {
      int x, y;
      cin >> x >> y;
      int ans = 0;
      rep(i, 26) {
        if(fts[i].sum(y) - fts[i].sum(x-1) > 0) ans++;
      }
      cout << ans << "\n";
    }
  }
}
int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  answer();
  return 0;
}

Measured memory_bytes: 105340
s = gets.to_i

def f(n)
  ret = 0
  if n.even?
    ret = n /2
  else
    ret = 3 * n + 1
  end
  ret
end


list = []
list[0] = s
i = 1
loop do
  break if list[i-1] == 4 || list[i-1] == 2 || list[i-1] == 1
  v = f(list[i-1])
  list[i] = v
  i += 1
end

ans = 10000000
for i in 0..(list.size - 2) do
  for j in (i+1)..(list.size - 1) do
    v1 = list[i]
    v2 = list[j]
    if v1 == v2 && j < ans
      ans = j
    end
  end
end

if ans == 10000000
  ans = list.size + 3
end

puts ans

Measured memory_bytes: 3836
def computeGCD(x, y): 
  
    if x > y: 
        small = y 
    else: 
        small = x 
    for i in range(1, small+1): 
        if((x % i == 0) and (y % i == 0)): 
            gcd = i 
              
    return gcd 
a,b,c=map(int,input().split())
r=computeGCD(a,b)
if c%r==0:
  print('YES')
else:
  print('NO')

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

int main() {
	int k, n;
	cin >> n >> k;
	vector<int> bond(n);
	for (int i = 0; i < n; i++) {
		cin >> bond.at(i);
	}
	sort(bond.begin(), bond.end());
	reverse(bond.begin(), bond.end());
	int sum = 0;
	for (int i = 0; i < k; i++) {
		sum += bond.at(i);
	}
	cout << sum << endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		char[]s = sc.next().toCharArray();
		char[]t = sc.next().toCharArray();
		
		int n = s.length;
		int cnt = 0;
		
		for(int i = 0 ; i < n ;i++) {
			if(s[i] != t[i]) {
				cnt++;
				}
			}
		
		System.out.println(cnt);
		}
}


Measured memory_bytes: 41696
// Verified

#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <vector>

using namespace std;

int main() {
  int N;

  cin >> N;
  long long a;
  vector<long long> S(N + 1, 0);
  for (int i = 0; i < N; ++i) {
    cin >> a;
    S[i + 1] = S[i] + a;
  }
  sort(S.begin(), S.end());

  long long ans = 0;
  long long prev = S[0];
  long long c = 0;
  for (size_t i = 1; i < N + 1; ++i) {
    const auto e = S[i];
    if (prev == e) {
      ++c;
      continue;
    }
    if (c > 0) {
      ans += (c + 1) * c / 2;
      c = 0;
    }
    prev = e;
  }
  if (c > 0)
    ans += (c + 1) * c / 2;

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


Measured memory_bytes: 1792
import sys
from math import ceil, floor
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def main():
    s = input()
    if s[2] == s[3] and s[4] == s[5]:
        print('Yes')
    else:
        print('No')
    return

if __name__ == '__main__':
    main()

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

int main()
{
  int n;
  cin>>n;
  long long a[n],b[n];
  for(int i=0;i<n;i++)
    cin>>a[i];
  for(int i=0;i<n;i++)
    cin>>b[i];
  
  long long sum = 0;
  vector<long long> v;
  
  int ans = 0;
  for(int i=0;i<n;i++)
  {
    if(a[i]>b[i])
      v.push_back(a[i]-b[i]);
    else if(a[i]<b[i])
    {
      sum += (b[i]-a[i]);
      ans++;
    }
  }
  
  if(ans==0)
  {
  	cout<<0;
  	return 0;
  }
  sort(v.begin(),v.end(),greater<>() );
  
  for(int i=0;i<v.size();i++)
  {
    if(sum<=v[i])
    {
      sum = 0;
      ans = ans + i + 1;
      break;
  	}
    sum = sum - v[i];
  }
  if(sum==0)
    cout<<ans;
  else
    cout<<-1;
}

Measured memory_bytes: 2428
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

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

    static class D {
        private static long MOD = (long) (1e9 + 7);

        public void solve(int testNumber, MyScanner in, PrintWriter out) {
            int N = in.Int();
            int K = in.Int();

            long ans = 0;
            for (long i = K; i <= N + 1; i++) {
                long a = (i * (i - 1)) / 2;
                long b = ((N + (N - i + 1)) * i) / 2;
                ans += b - (a - 1);
                ans %= MOD;
            }
            out.println((ans + MOD) % MOD);
        }

    }

    static class MyScanner {
        private BufferedReader in;
        private StringTokenizer st;

        public MyScanner(InputStream stream) {
            in = new BufferedReader(new InputStreamReader(stream));
        }

        public String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    String rl = in.readLine();
                    if (rl == null) {
                        return null;
                    }
                    st = new StringTokenizer(rl);
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int Int() {
            return Integer.parseInt(next());
        }

    }
}



Measured memory_bytes: 25796
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
ll dp[100005];
int main()
{
   ll n;
   cin>>n;
   ll a[n];
   for(int i=0;i<n;i++){
    cin>>a[i];
   }
   dp[n-1]=0;
   for(int i=n-2;i>=0;i--){
    if(i==n-2){
        dp[i]=abs(a[i+1]-a[i]);
    }
    else{
    dp[i]=min(dp[i+1]+abs(a[i+1]-a[i]),dp[i+2]+abs(a[i+2]-a[i]));
    }
   }
   cout<<dp[0];
    return 0;
}


Measured memory_bytes: 5052
#include<bits/stdc++.h>
using namespace std;
int main(){
  int N;
  cin >> N;
  int H[N];
  string ans = "Yes";
  for (int i = 0; i < N; i++)
    cin >> H[i];
  for (int i = 1; i < N; i++){
    if (H[i] < H[i-1]){
      ans = "No";
      break;
    }
    else if (H[i] >= H[i-1]+1){
      H[i] -= 1;
    }
    else if (H[i] = H[i-1]){
      continue;
    }
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <vector>
#include <map>

#define PI 3.14159265359	

using namespace std;

int main(){
	int n, m, k;
	cin >> n >> m;
	vector<vector<int> > a(n, vector<int>(m));
	vector<int> b(m);
	for (int i = 0; i < n; i++){
		for (int j = 0; j < m; j++){
			cin >> a[i][j];
		}
	}
	for (int i = 0; i < m; i++) cin >> b[i];
	for (int i = 0; i < n; i++){
		k = 0;
		for (int j = 0; j < m; j++){
			k += a[i][j] * b[j];
		}
		cout << k << endl;
	}
}

Measured memory_bytes: 3140
use std::io::*;
use std::str::FromStr;

fn main() {
	let (k,n): (u32, usize) = (read(), read());
	let a1: u32 = read();
	let mut ak = a1;
	let mut al: u32;
	let mut max: u32 = 0;
	for _ in 1..n {
		al = read();
		if max < al - ak { max = al - ak; }
		ak = al;
	}
	if max < a1 + k - ak { max = a1 + k - ak; }
	println!("{}", k - max);
}

fn read<T: FromStr>() -> T {
	let stdin = stdin();
	let stdin = stdin.lock();
	let token: String = stdin
		.bytes()
		.map(|c| c.expect("failed to read char") as char)
		.skip_while(|c| c.is_whitespace())
		.take_while(|c| !c.is_whitespace())
		.collect();
	token.parse().ok().expect("failed to parse token")
}



Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 5;
int y,n,a,b,c;
int main() {
	scanf("%d%d%d",&a,&b,&c);
	bool f=0;
	if(a==b&&a!=c) f=1;
	if(a==c&&a!=b) f=1;
	if(b==c&&a!=b) f=1;
	printf("%s\n",f?"Yes":"No");
	return 0;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void){

  int n;
  scanf("%d", &n);
  int divisor;
  int count = 0;
  for (int i = 1; i <= n; i += 2) {
    divisor = 0;
    for (int j = 1; j <= i; j++) {
      if (i%j == 0) {
        divisor++;
      }
    }
    if (divisor == 8) {
      count++;
    }
  }
  printf("%d\n", count);

  return 0;
}

Measured memory_bytes: 128
N, M = gets.split.map(&:to_i)
a = M.times.map{gets.split.map(&:to_i)}

a.uniq!
h = a.to_h

if a.size != h.size
  puts '-1'
elsif h.invert.key(1) == 0 && N != 1
  puts '-1'
else
  ret = 0
  h.each do |key, value|
    ret += value * 10 ** (N - key)
  end
  if ret.to_s.size < N
    ret += 10 ** (N - 1)
    puts ret
  elsif ret.to_s.size > N
    puts '-1'
  else
    puts ret
  end
end

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

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) for (int i = 0; i < (n); i++)
#define ALL(a) (a).begin(), (a).end()

int main() {
    int N;
    cin >> N;
    if (N < 1000) {
        cout << "ABC" << endl;
    }
    else {
        cout << "ABD" << endl;
    }
    return 0;
}

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

int main() {
	ll N;
	cin >> N;
	ll h, n, w;
	for(h=1;h<=3500LL;h++) {
		for(n=h;n<=3500LL;n++) {
			if(4*h*n <= N*(n+h)) continue;
			w = (N*h*n) / (4*h*n - N*(n+h));
			if(4*w*h*n == N*(n*w+h*w+h*n) and h <= n and n <= w) {
				cout << h << " " << n << " " << w << endl;
				return 0;
			}
		}
	}
}

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

using namespace std;
typedef long long ll;
typedef vector<ll> vl;
typedef vector<string> vs;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;
struct Edge {
	ll to;
 	ll cost;
 };
using Graph = vector<vector<Edge>>;

const int MAX = 10000000;
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
/***** define constant start *******/
const ll MOD = 1000000007;
const double PI = 3.1415926535897932;
const ll INF = LLONG_MAX;
string abc = "abcdefghijklmnopqrstuvwxyz";
string ABC = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
/****** define constant end ********/
long long modpow(long long a, long long n, long long mod) {
  long long res = 1;
  while (n > 0) {
	if (n & 1)
	  res = res * a % mod;
	a = a * a % mod;
	n >>= 1;
  }
  return res;
}
/****** define variable start ******/
ll s;
/******* define variable end *******/
int solve() {
	cin >> s;
	vector<vector<ll>> dp(s / 3 + 1, vl(s+1, 0));
	dp[0][0] = 1;
	vector<vector<bool>> flag(s / 3 + 1, vector<bool>(s+1, false));
	flag[0][0] = true;
		REP(j, s+1){
			ll sum = 0;
			FOR(k, 3, j+1){
				if(j - k >= 0 && flag[0][j-k]){
					sum += dp[0][j-k];
					sum %= MOD;
					flag[0][j] = true;
				}
			}
			dp[0][j] += sum;
			dp[0][j] %= MOD;
		}
	ll ans = 0;
	ans += dp[0][s] % MOD;
	ans %= MOD;

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

int main() {
	// clock_t start = clock();
	cout << std::fixed << std::setprecision(10);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int end_solve = solve();
	/*
	clock_t end = clock();
	const double time = static_cast<double>(end - start) / CLOCKS_PER_SEC *
	1000.0; printf("time %lf[ms]\n", time);
	*/

	return end_solve;
}


Measured memory_bytes: 13872
#include <bits/stdc++.h>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define Rreps(i,n,e) for(int i = n - 1; i >= e; --i)
#define Rrep(i,n) Rreps(i,n,0)
#define ALL(a) a.begin(), a.end()
#define fi first
#define se second
#define endl "\n"
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

//const ll MOD = 998244353;
const ll MOD = (1e+9) + 7;
const ll INF = 2e+9 + 10;
typedef pair<ll, ll> P;

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

  int N; cin >> N;
  vec P(N), Q(N);
  rep(i, N) cin >> P[i];
  rep(i, N) cin >> Q[i];

  vec v(N);
  reps(i, 0, N) v[i] = i+1;

  int now = 0, p, q;
  do {
    if(v == P) p = now;
    if(v == Q) q = now;
    ++now;
  } while(next_permutation(ALL(v)));

  cout << abs(p-q) << endl;

  return 0;
}

Measured memory_bytes: 256
//http://abc058.contest.atcoder.jp/tasks/arc071_a
#include <iostream>
using namespace std;

int n;
string S[50];

int count[50][26];
const int a = int('a');

void readInput(){
    cin >> n;
    for(int i=0; i<n; i++){
        cin >> S[i];
    }
}

int main(void){
    readInput();
    for(int i=0; i<n; i++){
        int size = S[i].size();
        for(int j=0; j<size; j++){
            int c = int(S[i][j])-a;
            ::count[i][c]++;
        }
    }
    int min;
    for(int i=0; i<26; i++){
        min = 10000;
        for(int j=0; j<n; j++){
            if(min > ::count[j][i]){
                min = ::count[j][i];
            }
        }
        for(int j=0; j<min; j++){
            cout << char(i+a);
        }
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
int n,k;
long long ans;
int main()
{
    scanf("%d%d",&n,&k);
    for(int b=k+1;b<=n;b++)
    {
        ans+=n/b*(b-k);
        if(k>0)ans+=max(0,n%b-k+1);
        else ans+=max(0,n%b-k);
    }
    printf("%lld",ans);
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main{
	 public static void main(String args[]){
		 Scanner std = new Scanner(System.in);
		 int n = std.nextInt();
		 int[] w = new int[n];
		 int a = 0;
		 int b =0;
		 for(int i=0;i<n;i++) {
			 w[i] = std.nextInt();
			 b += w[i];
		 }

		 int last =b;
		 for(int i=0;i<n;i++) {
			 b -= w[i];
			 a += w[i];
			 int dis = Math.abs(b-a);
			 if(dis>last) {
				 break;
			 }
			 last = dis;
		 }
		 System.out.println(last);
	 }
}


Measured memory_bytes: 22996
use std::io::*;
use std::str::FromStr;

//https://qiita.com/tubo28/items/e6076e9040da57368845
fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

//最大公約数を求める
fn gcd(x: usize, y: usize) -> usize {
    if x == 0 {
        return y;
    } else {
        return gcd(y % x, x);
    }
}

//refer
//https://drken1215.hatenablog.com/entry/2018/10/17/091800
fn main() {
    let n: usize = read();
    let m: usize = read();
    let s: Vec<char> = read::<String>().chars().collect();
    let t: Vec<char> = read::<String>().chars().collect();

    //最小公倍数を求める
    let g = gcd(n, m);
    let l = n * (m / g);
    //互いに素を求める
    let n_p = n / g;
    let m_p = m / g;

    let mut ans_flag = true;
    //同じところを参照して、一致しているか判定する
    //★互いに素な数に対して、i(=0..g)をかけることで問題文の文字列Xの条件を見ていくことになる
    for i in 0..g {
        if s[i * n_p] != t[i * m_p] {
            ans_flag = false;
        }
    }

    if ans_flag {
        println!("{}", l);
    } else {
        println!("-1");
    }
}


Measured memory_bytes: 2816
#define _CRT_SECURE_NO_WARNINGS
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// #define int ll
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pii;
#define all(c) begin(c), end(c)
#define loop(i,a,b) for(ll i=a; i<ll(b); i++)
#define rep(i,b) loop(i,0,b)
#define loopi(i,a,b) for(ll a=a;i<=ll(b);i++)
#define repi(i,b) loopi(i,1,b)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
template<class T> ostream & operator << (ostream &os, vector<T> const &);
template<int n, class...T>
typename enable_if<(n>=sizeof...(T))>::type
_ot(ostream &, tuple<T...> const &){}
template<int n, class...T>
typename enable_if<(n< sizeof...(T))>::type
_ot(ostream &os, tuple<T...> const &t){
    os << (n==0?"":" ") << get<n>(t); _ot<n+1>(os, t);
}
template<class...T>
ostream & operator << (ostream &os, tuple<T...> const &t){
    _ot<0>(os, t); return os;
}
template<class T, class U>
ostream & operator<<(ostream &os, pair<T,U> const &p){
    return os << "(" << p.first << ", " << p.second << ") ";
}
template<class T>
ostream & operator<<(ostream &os, vector<T> const &v){
    rep(i,v.size()) os << v[i] << (i+1==(int)v.size()?"":" "); return os;
}
#ifdef DEBUG
#define dump(...) (cerr << #__VA_ARGS__ << " = " << mt(__VA_ARGS__) \
                   << " [" << __LINE__ << "]" << endl)
#else
#define dump(...)
#endif
void fastios(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    // #define endl "\n"
}
template<class T>
size_t uniq(vector<T> &v){
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    return v.size();
}
template<class T>
size_t uniq(T *l, size_t n){
    sort(l,l+n);
    return unique(l,n) - l;
}
#define mems(arr,val) memset(arr,val,sizeof(arr));
int const mod = 1000000007;
int const inf = numeric_limits<int>::max()/10;

int popcount(unsigned long long x){
    static int dp[66000];
    if(dp[65535] != 16) for(int i = 0; i < 65536; i++) dp[i] = (i&1) + dp[i>>1];
    int res = 0;
    while(x) res += dp[x&65535], x >>= 16;
    return res;
}

int solve(ll s, ll d){
    //if(s <= 0 && d >= 0) return __builtin_popcount(-s) + __builtin_popcount(d);
    if(s <= 0 && d >= 0) return popcount(-s) + popcount(d);
    else if(s >= 0 && d >= 0){
        int j = 0;
        int ans = 0;
        while(s < d){
            if((s>>j&1) && (d>>j&1)){
                s += 1LL<<j;
                d -= 1LL<<j;
                ans += 2;
            } else if((s>>j&1) ^ (d>>j&1)){
                s += 1LL<<j;
                ans ++;
            }
            j++;
        }
        return ans;
    } else return solve(-d,-s);
}

signed main(){
    fastios();
    int N;
    cin >> N;
    rep(i,N){
        ll s,d;
        cin >> s >> d;
        cout << solve(s,d) << endl;
    }
}

Measured memory_bytes: 1456
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

int main(int argc, char *argv[])
{
  int N, tmp = 0, v = 0;
  cin >> N;

  tmp = N;
  while (tmp > 0) {
    v += (tmp % 10);
    tmp /= 10;
  }

  if (N % v == 0) {
    puts("Yes");
  } else {
    puts("No");
  }
}


Measured memory_bytes: 256