akhauriyash/Code-Regression huggingface dataset:
/*	MASTER HAS FAILED MORE TIMES
	THAN BEGINNER HAS EVER TRIED
*/

#include <bits/stdc++.h>

using namespace std;

#define endl             '\n'
#define all(a)           a.begin(), a.end()
#define mem(a, n)        memset(a, n, sizeof(a))
#define Unique(n)        (n).erase(unique(all(n)), (n).end())
#define NumofDigits(n)   ((long long)log10(n)+1)
#define repeat(i, a, n)  for(int i=a; i<n; i++)
#define isPowerOfTwo(n)  (n && !(n & (n - 1)))

typedef long long ll;
typedef long double ld;

int sieve(int n);
unsigned long long pow(long long base, long long power);
long long gcd(long long a, long long b){ return a%b ? gcd(b, a%b) : b; }
long long lcm(long long a, long long b){ return a*b/gcd(a, b); }

void quicken(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); }
void file(){
    #ifdef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif /*ONLINE_JUDGE*/
}

int main(){
    quicken();

    ll q, h, s, d, mini, n;
    cin >> q >> h >> s >> d >> n;

    /** q, z%4==0
        h, x%2==0
        s, any c
        d, any v

        mini = min(2*q, h)
        mini = min(2*mini, s)

        s & d :
        s = 1, d = 2

        2*s < d ? s is optimal -> ans = n * min(mini, s)
        2*s = d ? doesn't matter -> ans = n * min(mini, s)
        2*s > d ? d is optimal -> ans = n * min(mini, d/2)

    mini = min({q/0.125, h/0.25, s/0.5, d});
    cout << n*mini/2 + (n%2)*min({q/0.25, h/0.5, s/1.0}); **/

    mini = min({8*q, 4*h, 2*s, d});
    if(n%2==0) cout << n/2 * mini;
    else cout << n/2 * mini + min({4*q, 2*h, s});

    return 0;
}

unsigned long long pow(long long base, long long power){ /// mod?
    if(power==0) return 1;
    if(power==1) return base;

    unsigned long long ans = pow(base, power/2); /// mod?
    ans *= ans; /// ((ans%mod)*(ans%mod))%mod;

    if(power&1) return ans*base; /// ((ans%mod)*(base%mod))%mod;
    return ans;
}

int sieve(int n){
    int c = 0;
    vector<bool> isPrime(n+1, true);
    isPrime[0] = isPrime[1] = 0;

    for(long long i=2; i*i<=n; i++)
        if(isPrime[i])
            for(long long j=i*2; j<=n; j+=i)
                isPrime[j] = 0;
    repeat(i, 0, n+1)
        if(isPrime[i]) c++;
    return c; /// primeCount [1:n]
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
long long xsum(int x, int y, int z){
	return x*x+y*y+z*z+x*y+y*z+z*x;
}
int main(){
	int n;
	cin >> n; 

	int mx=sqrt(n)+1;
	vector<int> f(n+1,0);
	for(int x=1; x<=mx; ++x){
		int tmp=xsum(x,x,x);
		if(tmp<=n) ++f[tmp];
		else break;
	}
	for(int x=1; x<=mx; ++x){
		for(int z=1; z<=mx; ++z){
			if(x==z) continue;
			int tmp=xsum(x,x,z);
			if(tmp<=n) f[tmp]+=3;
			else break;
		}
	}
	for(int x=1; x<=mx; ++x){
		for(int y=x+1; y<=mx; ++y){
			for(int z=y+1; z<=mx; ++z){
				int tmp=xsum(x,y,z);
				if(tmp<=n) f[tmp]+=6;
				else break;
			}
		}
	}
	
	for(int i=1; i<=n; ++i) cout << f[i] << endl;
}

Measured memory_bytes: 3656
#include<iostream>
#include<cstring>
#include<string>
using namespace std;
int min(int a,int b){
    if(a>b)
    return b;
    else return a;
}
char s[1000009],t[1000089];
int main(){
cin>>s>>t;
int ans=32487203;
for(int i=0;i+strlen(t)<=strlen(s);i++){
    int h=0;
    for(int j=0;j<strlen(t);j++){
        if(s[i+j]!=t[j])
        h++;
       

    } ans=min(ans,h);
}
cout<<ans<<endl;
   system("pause");
}

Measured memory_bytes: 3168
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll MOD = 1000000007;
constexpr ll INF = 1ll<<60;

int main(int argc, char **argv)
{
	ll N; cin >> N;
	if (N & 1)
		std::cout << 0 << std::endl;
	else
	{
		ll res{0};
		ll t{5};
		while (true)
		{
			res += (N/(2*t));
			if (t*5 > N) break;
			t*=5;
		}
		std::cout << res << std::endl;
	}
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
 int a,b,c;
 cin>>a>>b>>c;
 if(a==b&&(a!=c))
 {
    cout<<"Yes"<<endl;
 }else if(b==c&&a!=b)
 {
    cout<<"Yes"<<endl;
}else if(a==c&&a!=b)
{
    cout<<"Yes"<<endl;
}else
{
    cout<<"No"<<endl;
}
return 0;
}

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

#define rep(i,n) for(int i = 0; i < n; i++)
const int INF = 1e9;

int main()
{
	int d, g;
	cin >> d >> g;
	vector <int> p(d);
	vector <int> c(d);
	vector <int> s(d);
	rep(i, d) {
		cin >> p[i] >> c[i];
		s[i] = 100 * (i + 1) * p[i] + c[i];
	}

	int ans = INF;
	int sum = 0;
	int re;
	int pm = 0;
	for (int bit = 0; bit < (1 << d); bit++) {
		vector <int>  repro;
		for (int i = 0; i < d; i++) {
			if (bit & (1 << i)) {
				sum += s[i];
				pm += p[i];
			}
			else {
				repro.push_back(i);
			}
		}
		re = g - sum;
		if (re <= 0) {
			ans = min(ans, pm);
		}
		else {
			int tsum = 0;
			bool flag = false;
			sort(repro.begin(), repro.end(), greater<int>());
			for (int v : repro) {
				for (int k = 0; k < p[v]; k++) {
					if (tsum >= re) {
						flag = true;
						break;
					}
					tsum += (v + 1) * 100;
					pm++;
				}
				if (flag)  break;
			}
			ans = min(ans, pm);
		}
		pm = 0;
		sum = 0;
	}
	cout << ans << endl;
}

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

int main(){
  int N,Y;
  cin >> N >> Y;
  int total=0;
  bool check=false;
  int resa=-1,resb=-1,resc=-1;
  for(int a=0; a<=N;a++){
    for(int b=0; a+b<=N;b++){
      int c=N-a-b;
      total = 10000*a + 5000*b + 1000*c;
      if(total==Y){
        resa=a;
        resb=b;
        resc=c;
      }
    }
  }
  cout<<resa<<" "<<resb<<" "<<resc<<endl;
}
    
       

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

#define int long long
#define FOR(i, l, r) for (int i=(l); i<(r); ++i)
#define RFOR(i, r, l) for (int i=(r); i>(l); --i)
#define vi vector<int>
#define popcount __builtin_popcountll

const int INF = 1LL<<60;
const int MOD = 1000000007;

template<typename T> istream &operator>>(istream &is, vector<T> &vec){ for (auto &v : vec) is >> v; return is; }
template<typename T> istream &operator>>(istream &is, T arr[]){ for (auto &x : arr) is >> x; return is; }

template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";
}

template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}

template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}

template <typename A>
string to_string(A x[], int n) {
    string result = "{";
    FOR(i, 0, n) {
        if (i!=0) result += ", ";
        result += to_string(x[i]); 
    }
    return result + "}";
}

string bin_string(int x) {
    const int d = 64;
    string result(d, ' ');
    RFOR(i, d-1, -1) result[d-1-i] = '0'+((x&1LL<<i)!=0);
    return result;
}

vector<int> getZ(string s) {
    int n = s.size();
    vector<int> z(n);
    int x = 0, y = 0;
    FOR(i, 1, n) {
        z[i] = max(0LL, min(z[i-x], y-i+1));
        while (i+z[i] < n && s[z[i]] == s[i+z[i]]) {
            x = i;
            y = i+z[i];
            ++z[i];
        }
    }
    return z;
}

int powa(int base, int exp) {
    if (exp<=0) return 1;
    if (base<=0) return 0;
    int val = powa(base, exp>>1);
    val = val*val % MOD;
    if (exp&1) {
        val = val*base % MOD;
    }
    return val;
}

signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    int R,C;
    cin >> R >> C;
    vector<vi> A(R, vi(C)), B(R, vi(C));
    cin >> A >> B;

    const int BIG = 80*160+10;
    bitset<2*BIG> dp[C];
    dp[0][BIG] = 1;
    FOR(r, 0, R) FOR(c, 0, C) {
        int shift = abs(A[r][c]-B[r][c]);
        if (c!=0) dp[c] |= dp[c-1];
        dp[c] = dp[c]<<shift | dp[c]>>shift;
    }

    int res=0;
    while (!dp[C-1][BIG+res]) ++res;
    cout << res;
}

Measured memory_bytes: 640
/*
 * 0004_Simultaneous_Equation.c
 *
 *  Created on: 2019/06/09
 *      Author: nagashima
 */

#include <stdio.h>
#include <math.h>

int main(void){
	double x,y;
	double a,b,c,d,e,f;

	while(scanf("%lf%lf%lf%lf%lf%lf",&a,&b,&c,&d,&e,&f)!= EOF){
		y=(c*d-a*f)/(b*d-a*e);
		x=(c-b*y)/(a);
		printf("%.3f %.3f\n",x,y);
	}

	return 0;
}



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

int X[110], Y[110], H[110], n;
int main()
{
	scanf("%d", &n);
	for(int i=0;i<n;i++)
		scanf("%d %d %lld", &X[i], &Y[i], &H[i]);

	int hh;
	for(int x=0;x<=100;x++)
		for(int y=0;y<=100;y++)
		{
			hh = -1;
			for(int i=0;i<n;i++)
				if(H[i]>0)
				{
					if(hh==-1)
						hh = H[i] + abs(x-X[i]) + abs(y-Y[i]);
					else if(hh != H[i] + abs(x-X[i]) + abs(y-Y[i]))
					{
						hh = -2;
						break;
					}
				}
			if(hh==-2) continue;

			for(int i=0;i<n;i++)
				if(H[i]==0)
				{
					
					if(hh - abs(x-X[i]) - abs(y-Y[i])>0)
					{
						hh = -2;
						break;
					}
				}
			if(hh==-2) continue;
			
			return 0*printf("%d %d %lld\n", x, y, hh);
		}
    return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

class C
{
	static void Main()
	{
		var n = int.Parse(Console.ReadLine());
		var p = Console.ReadLine().Split().Select(int.Parse).ToArray();

		var m = new int[n];
		var j = 0;
		p.Aggregate(1 << 30, (a, x) => m[j++] = Math.Min(a, x));
		Console.WriteLine(Enumerable.Range(0, n).Count(i => p[i] <= m[i]));
	}
}


Measured memory_bytes: 43904
import java.util.Scanner;

class Main{




	public static void main(String[] args) {





		Scanner sc = new Scanner(System.in);			//文字の入力
		int n = sc.nextInt();
		String s = sc.next();
		
		int ans = 0;
		int x = 0;
		for(int i = 0;i < n;i++){
			if(s.charAt(i) == 'I'){
				x++;
			}else{
				x--;
			}
			
			ans = Math.max(ans, x);
		}
System.out.println(ans);

	}
}


class Pair implements Comparable{
	Character from;
	int end;
	@Override
	public int compareTo(Object other) {
		Pair otherpair = (Pair)other;

		return end - otherpair.end;
	}
}




Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
int main(void) {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    while(cin >> n >> k) {
        int ans = 1;
        while(n--) {
            if(ans * 2 > ans + k) ans += k;
            else ans *= 2;
        }
        cout << ans << endl;
    }
}


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

using namespace std;

int timeNeeded(int time){
    if (time%10==0){
        return time;
    }else{
        return time - (time%10) + 10;
    }
}

int main() {
    int a, min=10, min_idx=-1, res;
    vector<int> time;
    for (int i=0; i<5; i++){
        cin >> a;
        time.push_back(a);
        if ((a%10)!=0 && ((a%10)<min)){
            min = (a%10);
            min_idx = i;
            // cout << "min idx " << min_idx << endl;
        }
    }

    if (min_idx==-1){
        res = 0;
        for(int i=0; i<5; i++){
            res += time[i];
        }
    }else{
        // cout << "min idx " << min_idx << endl;
        res = time[min_idx];
        // cout <<  "cur is " << res << endl;
        for(int i=0; i<5; i++){
            if (i != min_idx) {
                res += timeNeeded(time[i]);
                // cout << "cur is " << res << endl;
            }
        }        
    }

    cout << res << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // sort
#include <map> // pair
#include <queue>
#include<iomanip>
#include <cmath>
#include <set>
#include <unordered_set>

#define ABS(x) ((x)>0?(x):-(x))
#define MIN(x,y) ((x)>(y)?(y):(x))
#define MAX(x,y) ((x)<(y)?(y):(x))

#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

#define INF 1000000000

using namespace std;
typedef long long ll;

ll newton(long long int a, long long int  b)
{
	if(a==b)
		return a;
	while(a != 0 && b != 0)
	{
		if(a > b)
		{
			b += a;
			a = b-a;
			b -= a;
		}
		b %= a;
	}
	return a;
}

struct UnionFind {
	vector<int> p;
	UnionFind(int N):p(N)
	{
		for(int i=0; i< N; i++)
		{
			p[i] = i;
		}
	}
	int root(int x)
	{
		if(p[x] == x)
			return x;
		return p[x] = root(p[x]);
	}
	void unite(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		if(rx == ry) return;
		p[rx] = ry;
	}
	bool issame(int x, int y)
	{
		int rx = root(x);
		int ry = root(y);
		return rx == ry;
	}
};

//大きな数に対する割り算をするとき、MODを指定することで掛け算の値に変換できる

ll div2mul_calc(ll a, ll b, ll m)
{
	if (b == 0) {
        return 1;
    } else if (b % 2 == 0) {
        ll d = div2mul_calc(a, b / 2, m);
        return (d * d) % m;
    } else {
        return (a * div2mul_calc(a, b - 1, m)) % m;
    }
}
ll div2mul(ll n, ll mod)
{
	return div2mul_calc(n, mod-2, mod);
}

ll twoRow(ll a, ll b, ll mod)
{
	ll ret = 1;
	for(ll i = 1 ;i <= a+b;++i)
	{
		ret *= i;
		ret %= mod;
	}
	for(ll i = 1 ;i <= a;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	for(ll i = 1 ;i <= b;++i)
	{
		ret *= div2mul(i,mod);
		ret %= mod;
	}
	return ret;
}

struct edge {
    int from; //出発点
    int to;   //到達点
    int cost; //移動コスト
};

vector< ll > divisor(ll n) {
  vector< ll > ret;
  for(ll i = 1; i * i <= n; i++) {
    if(n % i == 0) {
      ret.push_back(i);
      if(i * i != n) ret.push_back(n / i);
    }
  }
  sort(ret.begin(), ret.end());
  return (ret);
}
/*
*/

int main()
{
	ll i,j,k;
	ll N,M;
	vector<ll> A;
	vector<ll> F;
	vector<pair<ll,ll> > T;
	cin >> N >> M;
	for(i=0;i<N;++i)
	{
		cin >> k;
		A.push_back(k);
	}
	for(i=0;i<N;++i)
	{
		cin >> k;
		F.push_back(k);
	}
	sort(A.begin(), A.end());
	sort(F.begin(), F.end());
	for(i=0;i<N;++i)
	{
		T.push_back(make_pair(A[i]*F[N-i-1], F[N-i-1]));
	}
	sort(T.begin(), T.end());
	ll top,bot;
	top = -1;
	bot = 1000000000000000001;
	while(bot-top>1)
	{
		ll mid = (top+bot)/2;
		j=0;
		for(i=0;i<N;++i)
		{
			auto l = T[i];
			if(l.first>mid)
				j += (l.first-mid+l.second-1)/l.second;
		}
		// cout << mid << " " << j << endl;
		if(j > M)
		{
			top = mid;
		}
		else
		{
			bot = mid;
		}
	}
	cout << bot << endl;
	return 0;
}




















Measured memory_bytes: 9456
n=int(input())
a=list(map(int, input().split()))
total=0
b=[0]*n
a_cycle=a*2

for i in range(n):
  total+=a[i]
a_tot=0
for j in range(n//2):
  a_tot+=a_cycle[2*j+1]
b[0]=total-2*a_tot
for i in range(1,n):
  b[i]=2*a[i-1]-b[i-1]
print(*b)

Measured memory_bytes: 15260
N = int(input())
s = []
subtractable = []
total = 0
for i in range(N):
    si = int(input())
    s.append(si)
    if si % 10 != 0:
        subtractable.append(si)
    total += si
if total % 10 != 0:
    ans = total
else:
    if subtractable == []:
        ans = 0
    else:
        subtractable.sort()
        ans = total - subtractable[0]
print(ans)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
#include <math.h>
#include <algorithm>
#include <functional>
#include<iostream>
#include <string>
using namespace std;
typedef long long ll;
#define pb pushback
#define fr(i,n) for(int i=0;i<n;i++)
#define fro(i,j,n) for(int i=j;i<n;i++)
#define ifr(i,n) for(int i=n-1;i>=0;i--)


int main() {
    int n;
	cin >> n;
      cout << n*n*n << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <string>

using namespace std;

#define loop(i,a,b) for(int i=(a); i<(int)(b); i++)
#define rep(i,b) loop(i,0,b)

char grid[110][110];

int main(){
    int w,h;
    while(cin>>h>>w, h||w){
        bool vis[110][110]={};
        rep(y,h) cin>>grid[y];
        int px=0, py=0;
        bool loop=false;
        while(1){
            if(vis[py][px]){
                loop=true; break;
            }
            vis[py][px]=true;
            char c=grid[py][px];
            if(c=='.') break;
            else if(c=='>') px++;
            else if(c=='^') py--;
            else if(c=='<') px--;
            else if(c=='v') py++;
        }
        if(loop) cout<<"LOOP"<<endl;
        else cout<<px<<" "<<py<<endl;
    }

}

Measured memory_bytes: 1188
#include <bits/stdc++.h>
using namespace std;
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
    enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
    ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
    *this << "[";
    for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
    ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
typedef long long ll;

void solve()
{
	int k;
	cin>>k;
	string s;
	cin>>s;
	int n = s.length();
	if (n<=k) {
		cout << s << "\n";
		return;
	}
	string t=s.substr(0,k);
	cout << t << "...\n";
}

int main()
{
	fastIO;
	int t=1;
	// cin>>t;
	while (t--) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 3656
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int main(){
    ll n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a.at(i);
        a.at(i)--;
    }

    ll ans = 0;
    ll cur = 0;
    for(int i = 0; i < n && cur != 1; ++i){
        cur = a.at(cur);
        ans++;
    }

    if(cur == 1){
        cout << ans << endl;
    }else{
        cout << -1 << endl;
    }
    return 0;
}


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

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define ff first
#define endl "\n"
#define ss second
#define maxn 2000006
#define pb push_back
#define ll long long
#define lll __int128
#define vll vector<ll>
#define mll map<ll,ll>
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define pll pair<ll,ll>
#define ull unsigned long long
#define f(i,x,n) for(ll i=x;i<=n;i++)
#define fr(i,x,n) for(ll i=x;i>=n;i--)
inline ll min(ll a, ll b, ll c) { return min(min(a, b), c);}
inline ll max(ll a, ll b, ll c) { return max(max(a, b), c);}
inline void fastio() {ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);}

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



int main() {
	fastio();

	int n, k; cin >> n >> k;
	vector<int> a(n + 1, 0); f(i, 1, n) cin >> a[i];

	vector<vector<int>> dp(101, vector<int>(100001, 0));
	// dp[1][0]=1;
	// f(j,1,k) dp[1][j]=1+dp[1][j-1];
	// Base case
	dp[1][0] = 1;
	f(j, 1, a[1]) dp[1][j] = (1 + dp[1][j - 1] % MOD) % MOD;
	f(j, a[1] + 1, k) dp[1][j] = (dp[1][j] % MOD + dp[1][j - 1] % MOD) % MOD;
	// (i,j) tells no. of ways of giving i childs atmost j candies 
	// dp[i][j] contains dp[i][j - 1] + dp[i][j];
	f(i, 2, n) {
		f(j, 0, k) {
			// dp[i][j]+=dp[i][j-1];
			// dp[i][j]+=(dp[i-1][j]-dp[i-1][max(0ll,j-a[i]-1)]);
			// f(z,max(0ll,j-a[i]),j) dp[i][j]+=dp[i-1][z];
			if (j == 0) dp[i][j] += 1;
			else {
				dp[i][j] = (dp[i][j] % MOD + (dp[i - 1][j] % MOD - ((j - a[i] >= 1) ? dp[i - 1][max(0ll, j - a[i] - 1)] : 0) % MOD + MOD) % MOD) % MOD;

				dp[i][j] = (dp[i][j] % MOD + dp[i][j - 1] % MOD) % MOD;
			}
		}
	}

	// debug(dp);

	cout << (dp[n][k] % MOD - dp[n][k - 1] % MOD + MOD) % MOD;
	// cout<<dp[n][k];

	return 0;
}


Measured memory_bytes: 41848
import sys
INF = 10 ** 10
MOD = 10 ** 9 + 7
from collections import deque

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

Measured memory_bytes: 3444
#include<iostream>
#include <malloc.h>
using namespace std;
int n;
int preorder[102];
int visit[102];
int inorder[102];
bool first = true;

struct Node {
	int id;
	Node* left;
	Node* right;
};

pair<int, int > findRoot(int left, int right) {//中序遍历中，这颗树所有节点的范围
	//返回第一个数为找到的根节点的节点号，后一个数为根节点在后序遍历的下标
	for (int i = 0; i < n; i++) {
		if (visit[preorder[i]] == 0) {
			for (int j = left; j <= right; j++) {
				if (inorder[j] == preorder[i]) {
					return make_pair(preorder[i], j);
				}
			}
		}
	}

	return make_pair(0, 0);
}
Node* buildTree(int left, int right) {
	if (left > right) {
		return NULL;
	}

	pair<int, int> rootInfo = findRoot(left, right);
	Node* root = (Node *)malloc(sizeof(Node));
	root->id = rootInfo.first;

	root->left = buildTree(left, rootInfo.second - 1);
	root->right = buildTree(rootInfo.second + 1, right);

	return root;
}

void postorder(Node* root) {
	if (root == NULL) {
		return;
	}
	postorder(root->left);
	postorder(root->right);
	if (first) {
		cout << root->id;
		first = false;
	}
	else {
		cout << " ";
		cout << root->id;
	}
}


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> preorder[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> inorder[i];
	}
	Node* root = buildTree(0,n-1);
	postorder(root);

	cout << endl;
}




Measured memory_bytes: 3100
#include<bits/stdc++.h>
using namespace std;
#define reg register
typedef long long ll;
#define MOD 998244353
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
static char buf[100000],*p1=buf,*p2=buf;
inline int read(void){
	reg char ch=getchar();
	reg int res=0;
	while(ch<'0'||'9'<ch)ch=getchar();
	while('0'<=ch&&ch<='9')res=10*res+ch-'0',ch=getchar();
	return res;
}

const int MAXC=3000+5;
const int MAXD=3000+5;

int a,b,c,d;
int f[MAXC][MAXD];

int main(void){
	a=read(),b=read(),c=read(),d=read();
	f[a][b]=1;
	for(reg int i=a;i<=c;++i)
		for(reg int j=b;j<=d;++j)
			if(i!=a||j!=b)
				f[i][j]=((1ll*f[i-1][j]*j%MOD+1ll*f[i][j-1]*i%MOD)%MOD-1ll*f[i-1][j-1]*(i-1)%MOD*(j-1)%MOD+MOD)%MOD;
	printf("%d\n",f[c][d]);
	return 0;
}

Measured memory_bytes: 38796
#ifndef HOME
	#pragma GCC target("avx")
	#pragma GCC optimize("Ofast")
	#pragma GCC optimize("unroll-loops")
	#pragma comment(linker, "/stack:200000000")
	#pragma GCC target("sse,sse2,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#endif

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/standard_policies.hpp>

#define MAX(a, b) __builtin_ia32_pmaxsd128(a, b)
#define MIN(a, b) __builtin_ia32_pminsd128(a, b)

#include <bits/stdc++.h>
#include <immintrin.h>
using namespace std;

using namespace __gnu_cxx;
using namespace __gnu_pbds;

template <class key_type>
using superTree = tree<key_type, null_type, less<key_type>, 
					   rb_tree_tag, tree_order_statistics_node_update>;
using v4si = int __attribute__ ((vector_size(16)));

const int MOD = 1000000007;

inline int _(int x, int y) {
	x += y;
	if (x >= MOD) { return x - MOD; }
	if (x < 0)    { return x + MOD; }
	return x; }

inline void __(int &x, int y) {
	x = _(x, y); }

/*
 * TO DO:
 *	
 * - long long instead of int
 * - bigger array sizes
 * - array / list instead of map / set
 * - can bruteforce with tricks pass system tests? 
 *
 * - NEVER STOP THINKING / CODING !!!
 */

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
#ifdef HOME
	freopen("cf.in", "r", stdin);
	freopen("cf.out", "w", stdout);
#endif		
	string s; cin >> s;
	long long ans = 0;
	for (int i = s.length() - 1, j = i; i >= 0; --i) {
		if (s[i] == 'B') {
			ans += (j - i); --j; } }
	cout << ans;
	return 0; }


Measured memory_bytes: 720
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
#include <cmath>
#include <cstdint>
#include <complex>

using namespace std;

int main()
{
    int64_t x, y;
    cin >> x >> y;
    
    int c = 0;
    for(int64_t i = x; i <= y; i*=2)
        c++;
    
    cout << c << endl;
    
    return 0;
}


Measured memory_bytes: 256
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N = INT()
S = input().split()

if len(set(S)) == 4:
	print("Four")
else:
	print("Three")


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

int main()
{
	int A, B, C, D;
	std::cin >> A >> B >> C >> D;
	if (A + B == C + D) {
		std::cout << "Balanced" << std::endl;
	} else if (A + B > C + D) {
		std::cout << "Left" << std::endl;
	} else if (A + B < C + D) {
		std::cout << "Right" << std::endl;
	}
	return 0;
}

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

int n;
int number[51]['z'-'a'+1];
int main(){
  std::cin>>n;
  std::string temp;
  for(int i=0;i<n;++i){
    std::cin>>temp;
    for(size_t j=0;j<temp.size();++j)
      ++number[i][temp[j]-'a'];
  }
  
  int temp2=1000;
  for(int i=0;i<'z'-'a'+1;++i){
    temp2=1000;
    for(int j=0;j<n;++j)
      temp2=std::min(temp2,number[j][i]);
    for(int j=0;j<temp2;++j)
      std::cout<<static_cast<char>(i+'a');
  }
  std::cout<<std::endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repb(i, a, b) for (int i = (a); i < (b); i++)
#define ALL(a) (a).begin(),(a).end()
#define PRINT(V) for(auto v:(V))cout<<v<<" "<<endl
inline ll GCD(ll a, ll b){return b ? GCD(b, a % b) : a;}
const int MOD = 1000000007;

int main()
{
    ll N;
    cin >> N;
    vector<double> x(N);
    vs u(N);
    double ans = 0.0;
    rep(i, N)
    {
        cin >> x[i] >> u[i];
        if(u[i] == "JPY")
        {
            ans += x[i];
        }
        else
        {
            ans += x[i] * 380000.0;
        }
    }
    cout << ans << endl;
}

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

int binMod(vector<int> &b, int val){
    int d = 0;
    int N = b.size();
    for(int i = 0; i < N; i++){
        d = ((d << 1) + b[i]) % val;
    }
    return d;
}

int mod2pow(int n, int val){
    int d = 1;
    for(int i = 0; i < n; i++){
        d = (d << 1) % val;
    }
    return d;
}

ll modpow(ll a, ll n, ll mod){
    ll res = 1;
    while( n > 0){
        if(n&1){
            if(n & 1) res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

int main(void){
    int N;
    string X;
    cin >> N >> X;

    vector<int> b(N);
    int pc = 0;
    for(int i = 0; i < N; i++){
        b[i] = (X[i] == '0')?0 : 1;
        if(b[i] == 1) pc++;
    }

    vector<int> mod_up(N,0), mod_down(N,0);
    int up = 0, down = 0;
    if(pc < N){
        up = binMod(b, pc+1);
    }

    if(pc > 1){
        down = binMod(b, pc-1);
    }


    for(int i = 0; i < N; i++){
        
        int mod = 0;

        if(b[i] == 0){
            mod = (up + modpow(2, N-i-1, pc+1) ) % (pc + 1);
        } else {
            if(pc == 1) {
                cout << 0 << endl;
                continue;
            }
            mod = (down - modpow(2, N-i-1, pc-1));
            while(mod < 0) mod += pc-1;
            mod = mod % (pc-1);
        }

        int cnt = 1;
        while(mod > 0){
            mod = mod % __builtin_popcount(mod);
            cnt++;
        }
        cout << cnt << endl;
    }

    return 0;
}


Measured memory_bytes: 5920
object Main extends App {
  val sc = new java.util.Scanner(System.in)
  val n, c = sc.nextInt()
  val sts = Array.fill(c)(List[(Int, Int)]())
  for (_ <- 1 to n) {
    val s, t, c = sc.nextInt() - 1
    sts(c) ::= (s, t)
  }

  def merge(st: List[(Int, Int)]): List[(Int, Int)] = {
    var res = List[(Int, Int)]()
    var last = -1
    for ((s, t) <- st) {
      if (last == s) {
        res = (res.head._1, t) :: res.tail
      } else {
        res ::= (s, t)
      }
      last = t
    }
    res
  }

  val st = sts.flatMap(st => merge(st.sorted))
  val a = Array.fill(100001)(0)
  for ((s, t) <- st) {
    a(s) += 1
    a(t+1) -= 1
  }
  val ans = a.scanLeft(0)(_ + _).max
  println(ans)
}


Measured memory_bytes: 73288
fun main(args: Array<String>) {
    val (h, a) = readLine()!!.split(' ').map(String::toDouble)
    val aList = readLine()!!.split(' ').map(String::toLong)
    if (aList.sum()>=h) {
        println("Yes")
    } else {
        println("No")
    }
}

Measured memory_bytes: 49584
#include <iostream>

int bubbleSort(int* a, int n) {
    int count = 0;
    bool flag = true;
    while (flag) {
        flag = false;
        for (int j = n - 1; j > 0; j--) {
            // 配列の最後の要素から値をチェックする。
            // もし、配列の要素の値がソートできたら、flagはfalseのまま。
            if (a[j] < a[j - 1]) {
                // ひとつ前の要素の値のほうが大きいので、
                // 値を入れ替える。
                int tmp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = tmp;
                flag = true;
                count++;
            }
        }
    }
    return (count);
}

int main() {
    int count;
    int n;      // 数列の長さ (0 < n < 101)
    std::cin >> n;

    int* a = new int[n];
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }

    count = bubbleSort(a, n);

    for (int i = 0; i < n; i++) {
        std::cout << a[i];
        if (i == n - 1)
            std::cout << std::endl;
        else
            std::cout << ' ';
    }
    std::cout << count << std::endl;

    return (0);
}



Measured memory_bytes: 3088
#include<stdio.h>

#define MAX 100
static const int I=(1<<21);
static const int W=0;
static const int G=1;
static const int B=2;


int n, Q[MAX][MAX];

int prim(){
  int u,minv,i,v;
  int d[MAX],p[MAX],color[MAX];

  for(i=0;i<n;i++){
    d[i]=I;
    p[i]=-1;
    color[i]=W;
  }

  d[0]=0;

  while(1){
    minv=I;
    u=-1;
    for( i=0;i<n;i++){
      if(minv>d[i]&&color[i]!=B){
	u=i;
	minv=d[i];
      }
    }

    if(u==-1) break;
    color[u]=B;

    for(v=0;v<n;v++){
      if(color[v]!=B&&Q[u][v]!=I){
	if(d[v]>Q[u][v]){
	  d[v]=Q[u][v];
	  p[v]=u;
	  color[v]=G;
	}
      }
    }
  }

  int sum=0;
  for(i=0;i<n;i++){
    if(p[i]!=-1) sum+=Q[i][p[i]];
  }

  return sum;
}


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

   for(i=0;i<n;i++){
      for(j=0;j<n;j++){
	int e;
	scanf("%d" ,&e);
	      Q[i][j]=(e==-1)?I:e;
	      }
      }

      printf("%d",prim());

      printf("\n");
      return 0;
   }
	



Measured memory_bytes: 2044
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define vi vector<int>
#define srt(a) sort(a.begin(), a.end());
#define se second
#define fi first
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cout.precision(10);
    cout << fixed;
    LL n,k; 
    cin>>n>>k;
    vector <LL> v(n);
    forn(i,n) cin>>v[i];
    srt(v);
    reverse(all(v));
    LL an = 0;
    for(int i=k;i<n;i++){
        an += v[i];
    }
    cout<<an<<endl;
    return 0;
}



Measured memory_bytes: 1792
H,W=map(int,input().split())
A=[list(input()) for i in range(H)]

for i in reversed(range(H)):
  if A[i]==["."]*W:
    A.pop(i)
    
for j in reversed(range(W)):
  flag=0
  for i in range(len(A)):
    if A[i][j]=="#":
      flag=1
  if flag==0:
    for i in range(len(A)):
      A[i].pop(j)

for i in range(len(A)):
	print("".join(A[i]))

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

using namespace std;
using ll = long long;

#define REP(i,m,n) for(ll (i)=(m),i##_len=(n);(i)<(i##_len);++(i))
#define FORR(i,v) for(auto (i):v)
#define ALL(x) (x).begin(), (x).end()
#define _PR(x) cout << (x) << endl
#define _PS(x) cout << (x) << " "
#define SZ(x) ((int)(x).size())
#define MAX(a,b) (((a)>(b))?(a):(b))
#define MIN(a,b) (((a)<(b))?(a):(b))
#define pb push_back

int main()
{
    string S;
    cin >> S;
    ll N = S.length();
    vector<ll> A(N+1, -1);

    if(S[0] == '<') A[0] = 0;
    REP(i,0,N-1){
        if((S[i] == '>') && (S[i+1] == '<')) A[i+1] = 0;
    }
    if(S[N-1] == '>') A[N] = 0;

    ll pos = 0, cnt, tmp;
    if(A[0] == 0){
        cnt = 1;
        while(S[pos] == '<'){
            ++pos;
            A[pos] = MAX(cnt,A[pos]);
            ++cnt;
        }
    }

    while(pos < N){
        if(A[pos] != 0) ++pos;
        else{
            cnt = 1;
            tmp = pos;
            --pos;
            while(S[pos] == '>'){
                A[pos] = MAX(cnt,A[pos]);
                --pos;
                ++cnt;
            }
            cnt = 1;
            pos = tmp;
            while(S[pos] == '<'){
                ++pos;
                A[pos] = MAX(cnt,A[pos]);
                ++cnt;
            }
        }
    }

    if(A[N] == 0){
        cnt = 1;
        pos = N-1;
        while(S[pos] == '>'){
            A[pos] = MAX(cnt,A[pos]);
            --pos;
            ++cnt;
        }
    }

    ll sum = 0;
    REP(i,0,N+1) sum += A[i];
    _PR(sum);

    return 0;
}

/*



*/

Measured memory_bytes: 4740
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

S = str(input())
T = str(input())

if T[:-1] == S:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 65560
#include<string>
#include<vector>
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<stack>
#include<queue>
#include<cmath>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<cstring>
#include<sstream>
#include<cassert>
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define repe(X,Y) for ((X) = 0;(X) < (Y);++(X))
#define peat(X,Y) for (;(X) < (Y);++(X))
#define all(X) (X).begin(),(X).end()

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;





int main()
{
    string a[3];
    cin >> a[0] >> a[1] >> a[2];
    
    rep(i, 3) {
        cout << (char)('A' + (a[i][0] - 'a'));
    }
    cout << endl;
    
    return 0;
    
}


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

using namespace std;

#define LL long long
int n, m, k[12];
int s[12][12];
int p[12];
int ans = 0;

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> k[i];
		for (int j = 0; j < k[i]; j++) {
			cin >> s[i][j]; s[i][j]--;
		}
	}
	for (int i = 0; i < m; i++) {
		cin >> p[i];
	}
	int lim = (1 << n);
	for (int i = 0; i < lim; i++) {
		bool jud = true;
		for (int j = 0; j < m; j++) {
			int cnt = 0;
			for (int K = 0; K < k[j]; K++) {
				if ((i >> s[j][K]) % 2 == 1)cnt++;
			}
			if (cnt % 2 != p[j]) jud = false;
		}
		if (jud)ans++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
N, X, Y = gets.split.map(&:to_i)

ans = [0] * (N - 1)

1.upto(N - 1) do |i|
  (i + 1).upto(N) do |j|
    l1 = (j - i).abs
    l2 = (X - i).abs + 1 + (Y - j).abs
    l3 = (X - j).abs + 1 + (Y - i).abs
    min = [l1, l2, l3].min
    ans[min - 1] += 1
  end
end

puts ans.join("\n")

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

int jump(int n,int K,vector<int>& h,vector<int>& level)
{
    int L = K;
    if(level[n] == -1)
    {
        const int BIG_BANG = 1 << 30;
        int mini = BIG_BANG;
        
        if(n <= K)
        {
            L = n;
            L--;
        }
        for(int j = 1;j <= L;j++)
        {
            mini = min(mini,abs(h[n] - h[n - j]) + jump(n - j,K,h,level));
        }
        level[n] = mini;
    }
    return level[n];
}

int main()
{
    int N,K;
    cin >> N >> K;

    vector<int> h(N + 1);
    vector<int> level(N + 1, -1);

    for(int i = 1;i <= N;i++)
    {
        cin >> h[i];
    }
    level[0] = 1 << 30;
    level[1] = 0; 
    
    cout << jump(N,K,h,level) << endl;

}

Measured memory_bytes: 10368
#include<bits/stdc++.h>
#define maxn 3005
#define mod 1000000007
#define count 500000004ll
using namespace std;

int n,q;
int a[maxn];
long long ans;
int dp[maxn][maxn];

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

int work(int x,int k)
{
	int temp=1;
	for(;k;k>>=1,x=1ll*x*x%mod)
		if(k&1)
			temp=1ll*temp*x%mod;
	return temp;
}

int main()
{
	n=read(), q=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			dp[i][j]=a[i]<a[j];
	
	for(int i=1;i<=q;i++)
	{
		int x=read(), y=read();
		dp[x][y]=dp[y][x]=count*(dp[x][y]+dp[y][x])%mod;
		for(int j=1;j<=n;j++)
			if(j!=x && j!=y)
			{
				dp[j][x]=dp[j][y]=count*(dp[j][x]+dp[j][y])%mod;
				dp[x][j]=dp[y][j]=count*(dp[x][j]+dp[y][j])%mod;
			}
	}
	
	for(int i=1;i<=n;i++)
		for(int j=1;j<i;j++)
			ans+=dp[i][j];
	
	cout<<ans%mod*work(2,q)%mod<<endl;
	
//	system("pause");
	return 0;
}



Measured memory_bytes: 38864
#include <bits/stdc++.h>
using namespace std;
int main(){

string S;
  cin >> S;
  if((S == "abc") || (S == "acb") || (S == "bac") || (S == "bca") || (S == "cab") || (S == "cba")){
  cout << "Yes" << endl;
  }
  
  else cout << "No" << endl;
  
return 0;
  
}


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

int main(){
        int a,b,solv;
        scanf("%d %d",&a,&b);
        if(a >= 10 || b >= 10){
                printf("-1\n");
        }else{
                solv = a * b;
                printf("%d\n",solv);
        }
        return 0;
}


Measured memory_bytes: 256
import collections

def main():
    n = input()
    a = map(int, raw_input().split())
    odd = [a[2 * i] for i in range(n/2)]
    even = [a[2*i + 1] for i in range(n/2)]
    codd = collections.Counter(odd)
    ceven = collections.Counter(even)
    coddmostitem = codd.most_common()[0][0]
    coddmosttimes = codd.most_common()[0][1]
    cevenmostitem = ceven.most_common()[0][0]
    cevenmosttimes = ceven.most_common()[0][1]
    if coddmostitem == cevenmostitem:
        if coddmosttimes > cevenmosttimes:
            if len(ceven) == 1:
                cevennoreplace = 0
            else:
                cevennoreplace = ceven.most_common()[1][1]
            coddnoreplace = codd.most_common()[0][1]
        if coddmosttimes < cevenmosttimes:
            if len(codd) == 1:
                coddnoreplace = 0
            else:
                coddnoreplace = codd.most_common()[1][1]
            cevennoreplace = ceven.most_common()[0][1]
        else:
            if len(ceven) == 1:
                cevennoreplace = 0
                coddnoreplace = coddmosttimes
            elif len(codd) == 1:
                cevennoreplace = cevenmosttimes
                coddnoreplace = 0
            elif codd.most_common()[1][1] >= ceven.most_common()[1][1]:
                cevennoreplace = ceven.most_common()[0][1]
                coddnoreplace = codd.most_common()[1][1]
            elif codd.most_common()[1][1] < ceven.most_common()[1][1]:
                cevennoreplace = ceven.most_common()[1][1]
                coddnoreplace = codd.most_common()[0][1]
    else:
        coddnoreplace = coddmosttimes
        cevennoreplace = cevenmosttimes
    coddreplace = n/2 - coddnoreplace
    cevenreplace = n/2 - cevennoreplace
    print(coddreplace+cevenreplace)

if __name__ == '__main__':
    main()


Measured memory_bytes: 20420
import sys
from collections import deque
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())
def LS(): return list(sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))

def Main():
    k = I()
    a,b = IL()
    l = list(range(a,b+1))
    for rep in l:
        if rep%k==0:
            print('OK')
            exit()
    else:
        print('NG')
    return

if __name__=='__main__':
    Main()

Measured memory_bytes: 9444
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#define ll long long
using namespace std;
const int maxn=500010,mod=1e9+7;
ll n,x;
bool v[maxn];
void read(ll &k)
{
	int f=1;k=0;char c=getchar();
	while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar();
	while(c<='9'&&c>='0')k=k*10+c-'0',c=getchar();
	k*=f;
}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
int main()
{
	read(n);
	ll now=1;
	for(int i=1;i<=n;i++)read(x),now=now/gcd(now,x)*x;
	printf("%lld\n",now);
}

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

#define MAX 200002

int n;
vector<int> v[MAX];

deque<tuple<long long int, long long int,long long int> > dp[MAX];

long long int p2[MAX];

#define MOD 1000000007

int sz[MAX];
int dep[MAX];
int mx[MAX];
vector<int> ds[MAX];
inline void dfs2(int b,int pr=-1) {
	mx[b] = 0;
	for (int go : v[b]) {
		dfs2(go, b);
		mx[b] = max(mx[b], mx[go] + 1);
		ds[b].push_back(mx[go] + 1);
	}
}
inline void dfs(int b, int pr = -1,int d=0,int consider=0) {
	dep[d]++;
	sz[b] = 1;
	sort(ds[b].begin(), ds[b].end(), greater<int>());
	ds[b].push_back(0);
	for (int go : v[b]) {
		if (go != pr) {
			int nex = 0;
			if (ds[b][0] == mx[go] + 1) {
				if(ds[b].size()>=1)nex = max(nex,ds[b][1]);
			}
			else {
				nex = max(nex,ds[b][0]);
			}
			dfs(go, b,d+1,nex-1);
			sz[b] += sz[go];
			if (dp[b].size() < dp[go].size())swap(dp[b], dp[go]);
			for (int k = 0; k < dp[go].size(); k++) {
				long long int a0 = get<0>(dp[b][k]);
				long long int a1 = get<1>(dp[b][k]);
				long long int a2 = get<2>(dp[b][k]);
				long long int b0 = get<0>(dp[go][k]);
				long long int b1 = get<1>(dp[go][k]);
				long long int b2 = get<2>(dp[go][k]);
				long long int c0 = a0*b0;
				long long int c1 = a1*b0 + a0*b1;
				long long int c2 = a0*b2 + a1*b1 + a1*b2 + a2*b0 + a2*b1 + a2*b2;
				if (c0 >= MOD)c0 %= MOD;
				if (c1 >= MOD)c1 %= MOD;
				if (c2 >= MOD)c2 %= MOD;
				dp[b][k] = make_tuple(c0, c1, c2);
			}
			dp[go].clear();
		}
	}
	for (int i = 0; i < min((int)dp[b].size(),consider); i++) {
		get<0>(dp[b][i]) += get<2>(dp[b][i]);
		get<0>(dp[b][i]) %= MOD;
		get<2>(dp[b][i]) = 0;
	}
	dp[b].push_front(make_tuple(1, 1,0));
	return;
}

int main() {
	p2[0] = 1;
	for (int i = 1; i < MAX; i++) {
		p2[i] = p2[i - 1] * 2LL;
		if (p2[i] >= MOD)p2[i] %= MOD;
	}
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int a;
		scanf("%d", &a);
		v[a].push_back(i);
	}
	dfs2(0);
	dfs(0);
	long long int ans = p2[n];
	for (int i = 1; i < dp[0].size(); i++) {
		long long int tmp = get<1>(dp[0][i]);
		tmp *= p2[n+1-dep[i]];
		tmp %= MOD;
		ans += tmp;
		ans %= MOD;
	}
	printf("%lld\n", ans);
	return 0;
}

Measured memory_bytes: 205824
#include <iostream>

int main(){
   std::string S;
   std::cin >> S;

   int count[2] = {0,0};
   for(int i=0; i<S.size(); ++i){
      if(S[i]=='0') ++count[0];
      else ++count[1];
   }
   std::cout << (count[0]<count[1] ? count[0]*2 : count[1]*2) << std::endl;
   return 0;
   /*
   bool flag = 0
   while(flag){
      for(int i=0; i<S.size()-1; ++i){
	 if(int(S[i])+int(S[i+1])==1){
	    S.erase(S.begin()+i);
	    S.erase(S.begin()+i);
	    count += 2;
	    --i;
	 }
      }

   }*/
}


Measured memory_bytes: 512
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"
#include "cassert"
#include "ctime"

using namespace std;

constexpr long long int MOD = 1000000007;
//constexpr int MOD = 1000000007;
//constexpr int MOD = 998244353;
//constexpr long long int MOD = 998244353;
constexpr double EPS = 1e-12;

//int N, M, K, T, H, W, L, R;
long long int N, M, K, T, H, W, L, R;



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

	cin >> H >> W;
	vector<string>s(H);
	for (auto &i : s)cin >> i;
	vector<int>xnum(W);
	vector<int>ynum(H);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (s[i][j] != '.') {
				xnum[j]++;
				ynum[i]++;
			}
		}
	}
	int ans = 0;
	for (int loop = 0; loop < 26; loop++) {
		for (int i = 0; i < H; i++) {
			for (int j = 0; j < W; j++) {
				if (!ynum[i] && !xnum[j])continue;
				if (s[i][j] != '.')continue;
				int ay, ax, by, bx, cy, cx, dy, dx;
				ay = by = cy = dy = i, ax = bx = cx = dx = j;
				while (ay >= 0 && s[ay][ax] == '.') ay--;
				while (by < H&&s[by][bx] == '.')by++;
				while (cx >= 0 && s[cy][cx] == '.')cx--;
				while (dx < W && s[dy][dx] == '.')dx++;
				if (ay >= 0 && by < H&&s[ay][ax] == s[by][bx]&&s[ay][ax]!='.') {
					ynum[ay]--;
					ynum[by]--;
					xnum[ax]--;
					xnum[bx]--;
					s[ay][ax] = s[by][bx] = '.';
					ans += 2;
				}
				if (ay >= 0 && cx >= 0 && s[ay][ax] == s[cy][cx] && s[ay][ax] != '.') {
					ynum[ay]--;
					ynum[cy]--;
					xnum[ax]--;
					xnum[cx]--;
					s[ay][ax] = s[cy][cx] = '.';
					ans += 2;
				}
				if (ay >= 0 && dx < W && s[ay][ax] == s[dy][dx] && s[ay][ax] != '.') {
					ynum[ay]--;
					ynum[dy]--;
					xnum[ax]--;
					xnum[dx]--;
					s[ay][ax] = s[dy][dx] = '.';
					ans += 2;
				}
				if (by < H && cx >= 0 && s[by][bx] == s[cy][cx] && s[by][bx] != '.') {
					ynum[by]--;
					ynum[cy]--;
					xnum[bx]--;
					xnum[cx]--;
					s[by][bx] = s[cy][cx] = '.';
					ans += 2;
				}
				if (by < H && dx < W && s[by][bx] == s[dy][dx] && s[by][bx] != '.') {
					ynum[by]--;
					ynum[dy]--;
					xnum[bx]--;
					xnum[dx]--;
					s[by][bx] = s[dy][dx] = '.';
					ans += 2;
				}
				if (cx >= 0 && dx < W && s[cy][cx] == s[dy][dx] && s[cy][cx] != '.') {
					ynum[cy]--;
					ynum[dy]--;
					xnum[cx]--;
					xnum[dx]--;
					s[cy][cx] = s[dy][dx] = '.';
					ans += 2;
				}
			}
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3372