akhauriyash/Code-Regression huggingface dataset:
import math
n, m = map(int, input().split())
ans = 0
if n == m:
  ans = (math.factorial(n) * math.factorial(m)) * 2
elif  n + 1 == m or n == m + 1:
  ans = (math.factorial(n) * math.factorial(m))
else:
  ans = 0
ans = ans % (10 ** 9 + 7)
print(ans)

Measured memory_bytes: 11132
//long time no ac
#include<bits/stdc++.h>
using namespace std;

#define debug(x) cout<<#x<<" :: "<<x<<"\n";
#define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\n";
#define debug3(x,y,z) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<"\t"<<#z<<" :: "<<z<<"\n";


#define     SPEED     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define 	ll          long long int
#define 	pb          push_back
#define 	pii         pair<int,int>
#define 	vi          vector<int>
#define 	pll         pair<ll,ll>
#define 	vll         vector<ll>
#define 	ff          first
#define 	ss          second
#define 	all(a)      (a).begin(),(a).end()
#define 	sz(x)       (ll)x.size()
#define 	hell        1000000007
#define 	rep(i,n)    for(i=0;i<n;i++)
#define 	repe(i,a,b) for(i=a;i<b;i++)
#define 	lbnd        lower_bound
#define 	ubnd        upper_bound
#define 	bs          binary_search
#define 	mp          make_pair

ll power(ll a,ll b)
{
	if(b==0)
		return 1;
	if(b==1)
		return a;
	ll c=power(a,b/2);
	if(b%2==0)
		return((c%hell)*(c%hell))%hell;
	return ((((c%hell)*(c%hell))%hell)*(a%hell))%hell;
}

/********************************************************/

ll dp[1005][1005],n,m;
string s[1005];

ll f(ll x,ll y)
{
	if(x>n || y>m) return 0;
	if(x==n-1 && y==m-1) return 1;
	if(dp[x][y]==-1)
	{
		dp[x][y]=0;
		if(x+1<n && s[x+1][y]!='#')
			dp[x][y]=(dp[x][y]+f(x+1,y))%hell;
		if(y+1<m && s[x][y+1]!='#')
			dp[x][y]=(dp[x][y]+f(x,y+1))%hell;
	}
	// debug3(x,y,dp[x][y]);
	return dp[x][y]%hell;
}


int main()
{
	SPEED;
	ll k,t,c=0,i,j,cs=0;
	t=1;

	// cin>>t;
	// string s;
	while(t--)
	{
		cin>>n>>m;
		// n=s.length();
		// ll a[n];
		memset(dp,-1,sizeof(dp));
		rep(i,n)
		{
			cin>>s[i];
		}
		c=f(0,0);
		cout<<c;
		if(t!=0)
	   		cout<<"\n";
	}
	return 0;
}

Measured memory_bytes: 9344
#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  int arr[1000];
  for (int i = 0; i < n; i++)
    cin >> arr[i];
  sort(arr, arr + n);
  int sum = 0;
  for (int i = 0; i < k; i++)
    sum += arr[i];
  cout << sum;


  return 0;
}


Measured memory_bytes: 3628
/*
ID: 5ak0
PROG:
LANG: C++11
*/

#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define mpr make_pair

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 7;

int n, x, cnt1, cnt2;

int main(){
    #ifndef SAKO
    //freopen(".in", "r", stdin);
    //freopen(".out", "w", stdout);
    #endif // SAKO
    ios_base::sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i){
        cin >> x;
        if (x % 2 == 1)
            ++cnt1;
        else
            ++cnt2;
    }
    if (cnt1 % 2 == 1)
        return !(cout << "NO");
    if (cnt2 % 2 == 1 && cnt1 == 0)
        return !(cout << "NO");
    cout << "YES";

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
 
template <typename T> void print(T t) { cout<<t<<endl; }
template<typename T, typename... Args> void print(T t, Args... args) { cout<<t<<" "; print(args...); }

#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
#define int long long
#define double long double

int n;
vector<int>v[200005];
int mod=1e9+7;
int inverse[200005];
int powers[200005];
int ans=0;

int inv(int x)
{
    int r,y;
    for(r=1,y=mod-2;y>0;x=(x*x)%mod,y/=2)
        if(y%2==1)
            r=r*x%mod;
    return r;
}

int dfs(int pos,int par)
{
    if(v[pos].size()==1)
        return 1;

    vector<int>st;
    int sum=0;
    for(int j:v[pos])
    {
        if(j!=par)
        {
            int get=dfs(j,pos);
            st.push_back(get);
            sum+=get;
        }
    }
    int left=n-1-sum;
    if(left!=0)
        st.push_back(left);

    int start = inverse[n-1];
    int sum2=0;
    for(auto i:st)
    {
        sum2+=powers[i];
        sum2%=mod;
    }
    sum2-=v[pos].size()-1;
    sum2+=mod;
    sum2%=mod;
    start=(start*sum2)%mod;
    ans=(ans+1-start+mod)%mod;
    return sum+1;
}
int32_t main() 
{
    /* For each node find the prob that there are 
    atleast 2 subtrees which has atleast one black node. */

    /* Let n1,n2,n3 .. be the size of all subtrees connected to current vertex.
    Prob the curr vertex is white = 1/2
    prob atleast 2 subtrees which has atleast one black node = 
    1 - probability(all subtrees have white vertices) - probability(only 1 subtree has non zero black vertices)
    1 - ((1/2)^(n-1) + (1/2)^(n-1)*(2^n1 + 2^n2 ... 2^nx - x))

    Hence answer = summation for all non leaf vertices 
    of 1/2 * (1-((1/2)^(n-1)(2^n1+2^n2.... 2^nx-x+1)))
    Where x is the degree of the current vertex */

    IOS
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    int val=1;
    for(int i=0;i<n+2;i++)
    {
        inverse[i]=inv(val);
        powers[i]=val;
        val*=2;
        val%=mod;
    }
    int st=1;
    for(int i=1;i<=n;i++)
        if(v[i].size()!=1)
        {
            st=i;
            break;
        }
    dfs(st,0);
    print((ans*inverse[1])%mod);
}   


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

using namespace std;

typedef long long ll;

int main() {
	int n, x;
	ll k;
	cin >> n >> k;
	vector<ll> posi, nega;
	for (int i = 0; i < n; i++) {
		cin >> x;
		if (x >= 0) {
			posi.push_back(x);
		} else {
			nega.push_back(x);
		}
	}
	sort(posi.begin(), posi.end());
	sort(nega.begin(), nega.end());
	if (1LL * posi.size() * nega.size() >= k) {
		ll l = -1e18, r = 1e18;
		while (l <= r) {
			ll m = (l + r) / 2;
			ll cnt = 0;
			for (int i = 0; i < posi.size(); i++) {
				int sl = 0, sr = nega.size() - 1;
				while (sl <= sr) {
					int sm = (sl + sr) / 2;
					if (posi[i] * nega[sm] <= m) {
						sl = sm + 1;
					} else {
						sr = sm - 1;
					}
				}
				cnt += sr + 1;
			}
			if (cnt >= k) {
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		cout << l << endl;
	} else {
		k -= 1LL * posi.size() * nega.size();
		ll l = -1e18, r = 1e18;
		while (l <= r) {
			ll m = (l + r) / 2;
			ll cnt = 0;
			// printf("%lld, %lld, %lld\n", l, r, m);
			for (int i = 0; i < posi.size(); i++) {
				int sl = 0, sr = i - 1;
				while (sl <= sr) {
					int sm = (sl + sr) / 2;
					if (posi[i] * posi[sm] <= m) {
						sl = sm + 1;
					} else {
						sr = sm - 1;
					}
				}
				cnt += sr + 1;
			}
			// cout << cnt << endl;
			for (int i = 0; i < nega.size(); i++) {
				int sl = i + 1, sr = nega.size() - 1;
				while (sl <= sr) {
					int sm = (sl + sr) / 2;
					if (nega[i] * nega[sm] <= m) {
						sr = sm - 1;
					} else {
						sl = sm + 1;
					}
				}
				cnt += nega.size() - sl;
			}
			// cout << cnt << endl;
			if (cnt >= k) {
				r = m - 1;
			} else {
				l = m + 1;
			}
		}
		cout << l << endl;
	}
	return 0;
}

Measured memory_bytes: 2548
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <bitset>
#include <stack>
#include <cassert>
#include <iterator>
#include <fstream>
#define mod 1000000007ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 1003;

int n, cnt = 0, d;
char a[N][N];

char get(int d)
{
	return (char)(d % 26 + 'a');
}

void addHor(int y, int x)
{
	a[y][x] = get(d);
	a[y][x + 1] = get(d);
	d++;
}


void addVer(int y, int x)
{
	a[y][x] = get(d);
	a[y + 1][x] = get(d);
	d++;
}


void add7(int y, int x)
{
	addVer(y, x);
	addHor(y, x + 1);
	addHor(y, x + 3);

	addHor(y + 1, x + 2);
	addHor(y + 1, x + 5);

	addVer(y + 2, x + 2);
	addVer(y + 2, x + 4);
	addHor(y + 2, x + 5);

	addVer(y + 3,x);

	addVer(y + 4, x + 1);
	addVer(y + 4, x + 6);

	addVer(y + 5, x + 3);

	addHor(y + 6, x);
	addHor(y + 6, x+4);
}

void add6(int y, int x)
{
	addHor(y, x);
	addVer(y, x + 2);
	addHor(y+2, x+1);
	addVer(y+1, x);


	addVer(y+3, x);
	addHor(y+3 + 2, x + 1);


	addVer(y, x + 3);
	addHor(y + 2, x + 3 + 1);


	addHor(y + 3, x+3);
	addVer(y + 3, x +3+ 2);
	addHor(y + 3 + 2, x+3 + 1);
	addVer(y + 3 + 1, x+3);

}


void add5(int y, int x)
{

	addHor(y, x);
	addHor(y, x + 2);

	addHor(y + 4, x + 1);
	addHor(y + 4, x + 3);

	addVer(y + 1, x);
	addVer(y + 3, x);

	addVer(y, x+4);
	addVer(y + 2, x+4);

	addVer(y+1,x+1);
	addHor(y + 3, x + 2);
}

void add3(int y, int x)
{
	addHor(y,x);
	addVer(y+1, x);
	addVer(y, x+2);
	addHor(y+2, x+1);
}

void solve(int l, int r)
{
	if (r - l + 1 <= 2)
		return;


	if ((r - l + 1) == 7)
	{
		add7(l, l);
		return;
	}

	if ((r - l + 1) == 6)
	{
		add6(l, l);
		return;
	}

	if ((r - l + 1) == 5)
	{
		add5(l,l);
		return;
	}
	

	if ((r - l + 1) == 3)
	{
		add3(l, l);
		return;
	}

	if ((r - l + 1) == 6)
	{
		add6(l, l);
		return;
	}

	a[l][l] = get(d);
	a[l][l + 1] = get(d);
	d++;
	a[l][r] = get(d);
	a[l + 1][r] = get(d);
	d++;
	a[r][r] = get(d);
	a[r][r - 1] = get(d);
	d++;
	a[r][l] = get(d);
	a[r - 1][l] = get(d);
	d++;

	a[l + 1][l] = get(d);
	a[l + 1][l + 1] = get(d);
	d++;
	a[l][r - 1] = get(d);
	a[l + 1][r - 1] = get(d);
	d++;
	a[r - 1][r] = get(d);
	a[r - 1][r - 1] = get(d);
	d++;
	a[r][l + 1] = get(d);
	a[r - 1][l + 1] = get(d);
	d++;

	l += 2;
	r -= 2;
	solve(l, r);
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			a[i][j] = '.';

	if (n > 2)
		solve(1, n);
	else
	{
		cout << -1 << endl;
		return 0;
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
			cout << a[i][j];
		cout << endl;
	}
	return 0;
}

/*


100 20 81



*/

Measured memory_bytes: 2176
package main
  
import (
    "fmt"
)

const a = int(1e9)

func main() {
    var s int
    fmt.Scan(&s)

    x1 := (s - 1) / a
    y1 := 0
    x2 := 0
    y2 := s % a
    if y2 == 0 {
        y2 = a
    }
    x3 := x1 + 1
    y3 := a

    fmt.Printf("%d %d %d %d %d %d\n", x1, y1, x2, y2, x3, y3)
}


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

#define FOR(x,y,z) for(int x=y,x##_=z;x<=x##_;++x)
#define DOR(x,y,z) for(int x=y,x##_=z;x>=x##_;--x)
#define FOR_(x,y,z,s) for(int x=y,x##_=z;x<=x##_;x+=s)
#define FOR__(x,y,z) for(int x=y,x##_=z;x<=x##_;x<<=1)
#define EOR(x,y) for(int x##_=head[x],y=edge[x##_].e;x##_;y=edge[x##_=edge[x##_].to].e)
#define EGOR(x,y,z) for(int x##_=head[x],y=edge[x##_].e,z=edge[x##_].c;x##_;y=edge[x##_=edge[x##_].to].e,z=edge[x##_].c)

#define clr(x,y) memset(x,y,sizeof(x))
#define szf(x) sizeof(x)
#define min3(x,y,z) min(min(x,y),z)
#define max3(x,y,z) max(max(x,y),z)

#define read2(x,y) read(x),read(y)
#define read3(x,y,z) read(x),read(y),read(z)
#define read4(x,y,z,w) read3(x,y,z),read(w)
#define reads(str) sf("%s",str)

#define ts (*this)
#define sf scanf
#define pf printf

#define ll long long
#define ull unsigned long long
#define db double
#define ct clock_t
#define ck() clock()
#define rd rand()
#define rmx RAND_MAX
#define RD T*(rd*2-rmx)


using namespace std;

template<class T>bool tomin(T &x,T y){return x>y?x=y,1:0;}
template<class T>bool tomax(T &x,T y){return x<y?x=y,1:0;}
template<class T>void read(T &x){
	char c;
	x=0;
	int f=1;
	while(c=getchar(),c<'0'||c>'9')if(c=='-')f=-1;
	do x=(x<<3)+(x<<1)+(c^48);
	while(c=getchar(),c>='0'&&c<='9');
	x*=f;
}

const db Pi=acos(-1);
const int P=673;
int main(){
	srand(time(NULL));
	int L,R;
	read2(L,R);
	if(R-L+1>=P)puts("0");
	else{
			int ans=2e9;
			FOR(i,L,R)FOR(j,i+1,R)tomin(ans,(int)((ll)i*j%2019));
			pf("%d",ans);
	}
	return 0;
}


Measured memory_bytes: 256
// #pragma GCC target("avx")
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

// #include <string>
#include <iostream>
// #include <array>
#include <vector>
// #include <functional>

// #include <algorithm>
// #include <limits>
// #include <set>
#include <bitset>
#include <cassert>
using namespace std;
typedef long long ll;
bool is_on(int bit, vector<int> const &sw, int p)
{
    int sum_on = 0;
    for (auto &&s : sw)
    {

        if (bit & (1 << (s - 1)))
            sum_on++;
    }
    if (sum_on % 2 == p)
        return true;
    else
        return false;
}
void test_is_on()
{
    vector<int> v;
    v.push_back(1);
    v.push_back(2);
    assert(is_on(3, v, 0));
    vector<int> v2;
    v2.push_back(2);
    assert(is_on(3, v2, 1));
    cout << "passed" << endl;
}

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

    int N, M;
    cin >> N >> M;
    int k, p[M];
    vector<vector<int>> S;

    for (int i = 0; i < M; i++)
    {
        cin >> k;
        vector<int> v;
        for (int j = 0; j < k; j++)
        {
            int x;
            cin >> x;
            v.push_back(x);
        }
        S.push_back(v);
    }

    for (int i = 0; i < M; i++)
        cin >> p[i];

    int num_all_on = 0;
    for (int bit = 0; bit < (1 << N); ++bit)
    {
        bool all_on = true;
        for (int i = 0; i < M; i++)
        {
            if (!is_on(bit, S.at(i), p[i]))
            {
                all_on = false;
            };
        }
        if (all_on)
            num_all_on++;
    }

    cout << num_all_on << endl;
    // test_is_on();
}


Measured memory_bytes: 764
#include<iostream>
using namespace std;
long long int gcd(long long int a, long long int b)
{
	long long int aa = max(a, b), bb = min(a, b);
	if(bb == 0)
	return aa;
	return gcd(bb, aa%bb);
}
main()
{
	long long int n, k ,j;
	cin >> n;
	long long int i, sum = 0;
	for(i=1;i<=n;i++)
	 for(j=1;j<=n;j++)
	 for(k=1;k<=n;k++)
	 sum+=gcd(gcd(i,j), k);
	 
	cout << sum;
	
	return 0;
}

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

int main() {
    int n;
    vector<long int> a(100010);
    cin>>n;
    int oddcnt=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    for(int i=0;i<n;i++){
        if(a[i]%2==1) oddcnt++;
    }
    //cout<<oddcnt<<endl;
    cout<<((oddcnt%2==1)?"NO":"YES")<<endl;

}


Measured memory_bytes: 1024
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int main(){
 int i,j;
  int n,l;
  int *a;
  int count;
  int min=100,min_i;
  int cc;
  
  scanf("%d %d",&n,&l);
  a = malloc(sizeof(int)*n);
  a[0] = l;
  count = l;
  for(i=1;i<n;i++){
   a[i] = a[i-1] + 1;
   count += a[i];
  }
  for(i=0;i<n;i++){
    //printf("%d\n",a[i]);
  
  //  printf("cc=%d\n",cc);
   if(abs(a[i]) < min){
     min = abs(a[i]);
     min_i = i;
   }
  }
  //printf("%d\n",min);
  printf("%d\n",count-a[min_i]);
}


Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstdlib>

#define SIZE 8
#define WIDTH 4

using namespace std;

int distances[SIZE][SIZE][SIZE][SIZE][SIZE][SIZE][SIZE][SIZE];
int way[4] = { -1, 1, -WIDTH, WIDTH };

typedef struct{
	int v[SIZE];
} field_t;

void solve(){
	queue<field_t> q;

	q.push({ { 0, 1, 2, 3, 4, 5, 6, 7 } });

	while (!q.empty()){
		field_t a = q.front();
		q.pop();

		for (int i = 0; i < SIZE; i++){
			if (a.v[i] == 0){
				for (int j = 0; j < 4; j++){
					int newpos = i + way[j];
					if (newpos < 0 || newpos >= SIZE || abs(newpos%WIDTH - i%WIDTH) > 1) continue;
					int dist = distances[a.v[0]][a.v[1]][a.v[2]][a.v[3]][a.v[4]][a.v[5]][a.v[6]][a.v[7]];
					a.v[i]		= a.v[newpos];
					a.v[newpos]	= 0;
					if (distances[a.v[0]][a.v[1]][a.v[2]][a.v[3]][a.v[4]][a.v[5]][a.v[6]][a.v[7]]) {
						a.v[newpos] = a.v[i];
						a.v[i]		= 0;
						continue; 
					}
					distances[a.v[0]][a.v[1]][a.v[2]][a.v[3]][a.v[4]][a.v[5]][a.v[6]][a.v[7]] = dist + 1;
					q.push(a);
					a.v[newpos] = a.v[i];
					a.v[i]		= 0;
				}
				break;
			}
		}
	}
	distances[0][1][2][3][4][5][6][7] = 0;
}

int main(){
	solve();

	int a[SIZE];
	while (~scanf("%d%d%d%d%d%d%d%d", &a[0], &a[1], &a[2], &a[3], &a[4], &a[5], &a[6], &a[7]))
		cout << distances[a[0]][a[1]][a[2]][a[3]][a[4]][a[5]][a[6]][a[7]] << endl;
}

Measured memory_bytes: 65128
#define debug_interval ','
#define dump_interval ' '
#define debug_toggle 1

//{
#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
#define hi //cerr<<"hi"<<endl;
#define int long long
#define INT_MAX LLONG_MAX
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()
#define fi first
#define se second
#define mp make_pair
#define rev reverse
#define dans dump(ans)
//#define MOD 1000000007
#define amp(v,n) (v).count(n)?v[n]++:v[n]=1
#define sysp system("pause")
#define PI acos(-1)
#define ins insert
#define aer(v) (v).erase((v).begin(),(v).end()) 

//{
inline int toInt(string s){int v;istringstream sin(s);sin>>v;return v;}
template<class T> inline string toString(T x){ostringstream sout;sout<<x;return sout.str();}
template<class...A> inline void dump(){cout<<endl;}
template<class...A> inline void dump_rest() {cout<<endl;}
template<class T, class...A> inline void dump_rest(const T& first, const A&... rest){cout<<dump_interval<<first;dump_rest(rest...);}
template<class T,class...A> inline void dump(const T&first,const A&...rest){cout<<first;dump_rest(rest...);}
template<class...A> inline void debug(){cerr<<endl;}
template<class...A> inline void debug_rest() {cerr<<endl;}
template<class T, class...A> inline void debug_rest(const T& first, const A&... rest){cerr<<debug_interval<<first;debug_rest(rest...);}
template<class T,class...A> inline void debug(const T&first,const A&...rest){if(debug_toggle)cerr<<first,debug_rest(rest...);}
//}

typedef vector<int>vint;
typedef pair<int,int>pint;
typedef vector<pint>vpint;

template<typename A,typename B>inline void chmin(A &a,B b){if(a>b)a=b;}
template<typename A,typename B>inline void chmax(A &a,B b){if(a<b)a=b;}
template<int m>class mint{private:int i;public:mint() : i(0){}mint(int i): i((i%m+m)%m){}mint operator+(const mint& o){return o.i+i;}mint operator*(const mint& o){return o.i*i;}mint operator-(){return -i;}operator int() {return i;}};

//}

int a,b,c,n,m,k;
string s;

main(){
	cin>>a>>b>>k;
	vint v;
	for(int i=1;i<=min(a,b);i++){
		if(a%i==0&&b%i==0)v.pb(i);
	}
	dump(v[v.size()-k]);
}





Measured memory_bytes: 256
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <string>
#include <set>
#include <map>
#include <functional>
#include <cmath>
#include <cassert>
#define SIZE 305
#define MD 100002
#define MX 200005
#define MOD 998244353

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

int A[SIZE];
int dp[2][MX];
int dp2[MX];
ll rt2[SIZE];
ll rt3[SIZE];

int main()
{
	int n;
	scanf("%d",&n);
	int pos=0;
	memset(dp[pos],0,sizeof(dp[pos]));
	dp[pos][MD]=1;
	dp2[0]=1;
	int sum=0;
	for(int i=0;i<n;i++)
	{
		int a;
		scanf("%d",&a);
		sum+=a;
		pos^=1;
		for(int j=0;j<MX;j++)
		{
			dp[pos][j]=0;
			if(j-a>=0) dp[pos][j]+=dp[pos^1][j-a];
			if(j+a<MX) dp[pos][j]+=dp[pos^1][j+a]*2%MOD;
			if(dp[pos][j]>=MOD) dp[pos][j]-=MOD;
		}
		for(int j=MX-1;j>=a;j--)
		{
			dp2[j]+=dp2[j-a];
			if(dp2[j]>=MOD) dp2[j]-=MOD;
		}
	}
	rt2[0]=rt3[0]=1;
	for(int i=1;i<SIZE;i++)
	{
		rt2[i]=rt2[i-1]*2LL%MOD;
		rt3[i]=rt3[i-1]*3LL%MOD;
	}
	ll all=rt3[n];
	for(int i=MD;i<MX;i++)
	{
		all-=(ll) dp[pos][i]*3LL%MOD;
		if(all<0) all+=MOD;
	}
	//printf("%lld\n",all);
	if(sum%2==0)
	{
		all+=(ll) dp2[sum/2]*3LL%MOD;
		if(all>=MOD) all-=MOD;
	}
	printf("%lld\n",all);
	return 0;
}


Measured memory_bytes: 2560
#include <iostream>
#include <set>
#include <queue>
#include <vector>
#include <algorithm>
#include <cmath>
#include <string>
#include <cstring>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
#include <numeric>
#include <functional>

using namespace std;
#define ALL(x)              (x).begin(),(x).end()
typedef long long           ll;
#define REP(i, n)           for (ll i = 0 ; i < (ll)n ; ++i)
#define REPN(i, m, n)       for (ll i = m ; i < (ll)n ; ++i)
#define INF                 (ll)1e9
#define MOD                 (1000 * 1000 * 1000 + 7)
#define Ceil(x, n)          (((((x))+((n)-1))/n))
#define CeilN(x, n)         (((((x))+((n)-1))/n)*n)
#define FloorN(x, n)        ((x)-(x)%(n))
#define IsOdd(x)            (((x)&0x01UL) == 0x01UL)
#define IsEven(x)           (!IsOdd((x)))
#define M_PI                3.14159265358979323846
typedef pair<ll, ll>	    P;

/*-----------------------------------------------------------------------------
　処理
 -----------------------------------------------------------------------------*/
int main()
{
	ll N;
	cin >> N;
	vector<ll> A(N);
	for_each(ALL(A), [](ll &a){ cin >> a; });

	if (N == 1) {
		cout << 1 << endl;
		return 0;
	}

	auto getSt = [](ll a, ll b)
	{
		if (a == b) {
			return 0;
		} else if (a < b) {
			return 1;
		} else {
			return 2;
		}
	};

	ll status = getSt(A[0], A[1]);
	ll ans = 1;
	REPN(i, 1, N - 1) {
		int nextStatus = getSt(A[i], A[i + 1]);
		if (status == 0) {
			status = nextStatus;
		} else if (status == 1) {
			if (nextStatus == 2) {
				status = 0;
				ans++;
			}
		} else {
			if (nextStatus == 1) {
				status = 0;
				ans++;
			}
		}
	}

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


Measured memory_bytes: 1024
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"sort"
	"strconv"
)

var sc *bufio.Scanner

const BufferSize = 1024

func nextInt() int {
	if !sc.Scan() {
		panic(nil)
	}
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

var production bool

func debugf(format string, v ...interface{}) {
	if !production {
		fmt.Printf(format, v...)
	}
}

type bc struct {
	x int
	h int
}

type bcs []bc

func (b bcs) Len() int           { return len(b) }
func (b bcs) Less(i, j int) bool { return b[i].x < b[j].x }
func (b bcs) Swap(i, j int)      { b[i], b[j] = b[j], b[i] }

func answer(reader io.Reader, writer io.Writer) {
	sc = bufio.NewScanner(reader)
	buf := make([]byte, BufferSize)
	sc.Buffer(buf, 1e+6)
	sc.Split(bufio.ScanWords)
	n := nextInt()
	d := nextInt()
	a := nextInt()
	s := make([]bc, n)

	for i := range s {
		s[i].x = nextInt()
		s[i].h = nextInt()
	}
	sort.Sort(bcs(s))

	ans := 0

	bm := make([][]int, 0, n)

	admg := 0
	debugf("%v\n", s)
	for l := range s {
		if s[l].h <= 0 {
			continue
		}

		// proceed r
		//for r < n && s[r].x <= s[l].x+2*d {
		//	r++
		//}
		for len(bm) > 0 && bm[0][1] < s[l].x-2*d {
			admg -= bm[0][0]
			bm = bm[1:]
		}

		// drop bomb
		s[l].h -= admg
		if s[l].h > 0 {
			count := (s[l].h + a - 1) / a
			ans += count
			dmg := a * count
			admg += dmg
			s[l].h -= dmg
			bm = append(bm, []int{dmg, s[l].x})
			debugf("%d, %d, %v\n", l, count, s)
		} else {
			debugf("%d, %d, %v\n", l, 0, s)
		}
	}

	_, _ = fmt.Fprintf(writer, "%d", ans)
}

func main() {
	production = true
	answer(os.Stdin, os.Stdout)
}


Measured memory_bytes: 16640
#include "bits/stdc++.h"
using namespace std;
#define Rep(i,n) for(int i=0;i<(int)(n);i++)
#define For(i,n1,n2) for(int i=(int)(n1);i<(int)(n2);i++)
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define RREP(i,n) for(ll i=((ll)(n)-1);i>=0;i--)
#define FOR(i,n1,n2) for(ll i=(ll)(n1);i<(ll)(n2);i++)
#define put(a) cout<<a<<"\n"
#define all(a)  (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define oorret 0
#define oor(x) [&](){try{x;} catch(const out_of_range& oor){return oorret;} return x;}()
#define SZ(x) ((ll)(x).size())
typedef long long ll;
typedef pair<int, int> P;
template<typename T1,typename T2> inline bool chmin(T1 &a,T2 b){if(a>b){a=b;return 1;}return 0;}
template<typename T1,typename T2> inline bool chmax(T1 &a,T2 b){if(a<b){a=b;return 1;}return 0;}

ll pow(ll x,ll y){
    if(y<=0){return 1;}
    if(y%2==0){ll d = pow(x,y/2);return d*d;}
    else{return (x*pow(x,y-1));}
}

int main(){
    ll n,k;
    cin >> n >> k;
    ll res = k*pow(k-1,n-1);
    put(res);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;


int main(){
  int A, B;
  cin >> A >> B;

  if(B >= A && B%A==0) cout << A+B << endl;
  else cout << B-A << endl;
  
  return 0;
}


Measured memory_bytes: 256
#import sys
MOD = 10 ** 9 + 7
INFI = 10**10
#input = sys.stdin.readline
import math
from collections import deque
import itertools
import heapq
#import bisect
from fractions import Fraction
import copy
from functools import lru_cache
from collections import defaultdict
import pprint


def sosuhante(n):
    for k in range(2, int(math.sqrt(n))+1):
        if n% k ==0:
            return False
    return True
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

def kingaku(a,b,n):
    keta=len(str(n))
    return a*n+b*keta

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

#    h,w,a,b = map(int, input().split())
#    c = [[0 for j in range(n)] for i in range(n)]

def ret(a):
    c=[None]*(len(a)-1)
    if len(a)==1:
        return a[0]
    elif len(a)==0:
        return 0
    for i in range(1,len(a)):
        c[i-1]=abs(a[i]-a[i-1])
    return ret(c)

def soinsubunkai(n):
    a = []
    i = 1
    while i*i <= n:
        if n % i == 0 and i!=1:
            a.append(i)
            n=n//i

        if n% i !=0 or i==1:
            i += 1
    nokori=[n]
    return a + nokori

def main():
    x,y=map(int,input().split())
    ans="No"
    if y%2==0:
        if x>=-(y//-4):
            if x<=y//2:
                ans="Yes"
    print(ans)






if __name__ == "__main__":

    main()

Measured memory_bytes: 72624
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
const long long INF = numeric_limits<long long>::max();
int main()
{
    string S;
    cin >> S;
    if (S == "ABC") {
        cout << "ARC" << endl;
    } else {
        cout << "ABC" << endl;
    }
    return 0;
}

Measured memory_bytes: 3592
#include <iostream>
#include <string>
#include <queue>
using namespace std;


int main(){
	int n,q,temp,ttime,ntime=0;
	string tname,temps;
	queue<string> name;
	queue<int> time1;
	cin >> n >> q;
	int i=0;
	while(i!=n){
		cin >> tname >>ttime;
		name.push(tname);
		time1.push(ttime);
		i++;
	}
	while(!name.empty()){
		if(time1.front()>q){
			ntime+=q;
			name.push(name.front());
			time1.push(time1.front()-q);
			name.pop();
			time1.pop();
		}else{
			ntime+=time1.front();
			cout<< name.front()<<" "<< ntime<<endl;
			name.pop();
			time1.pop();
		}
	}
	return 0;
}

Measured memory_bytes: 6132
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
#define rep(i, n) for( int i = 0; i < n; i++ )

int main(){
    int n, x;
    while( cin >> n >> x, n){
        int count = 0;
        for( int i = 1; i < n; i++ ){
            for( int j = i+1; i+j < x, j < n; j++ ){
                for( int k = j+1; i+j+k <= x, k <= n; k++ ){
                    if( i+j+k == x ) count++;
                }
            }
        }
        cout << count << endl;
    }
}

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

int main(){
  char N[16];
  cin >> N;
  if (N[0] == '7' || N[1] == '7' || N[2] == '7') cout << "Yes" << "\n";
  else cout << "No" << "\n";
  
  return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int>> vvi;
typedef vector<vector<ll>> vvl;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a, b;
  cin >> a >> b;
  b++;
  ll ans = 0;
  for (int k = 0; k < 50; k++) {
    ll ca = (a >> (k + 1)) * (1LL << k) +
            max(0LL, a % ((1LL << (k + 1))) - (1LL << k));
    ll cb = (b >> (k + 1)) * (1LL << k) +
            max(0LL, b % ((1LL << (k + 1))) - (1LL << k));
    if ((cb - ca) % 2 == 1) {
      ans += (1LL << k);
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

void print(int A[], int n) {
	for (int i = 0; i < n; ++i) {
		if (i != 0)
			cout << " " << A[i];
		else
			cout << A[i];
	}
	cout << endl;
}


//1 bubbleSort(A, N) // N ??????????´?????????? 0-????????????????????? A
//2   flag = 1 // ????????£??\????´?????????¨??????
//3   while flag
//4     flag = 0
//5     for j ??? N-1 ?????? 1 ?????§
//6       if A[j] < A[j-1]
//7         A[j] ??¨ A[j-1] ?????????
//8         flag = 1

int main() {

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

	int A[n];
	for (int i = 0; i < n; ++i) {
		scanf("%d", A + i);
	}

//bubbleSort
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = n - 1; j > i; --j) {
			if (A[j] < A[j - 1]) {
				swap(A[j - 1], A[j]);
				++cnt;
			}
		}
	}

	print(A, n);
	cout << cnt << endl;

	return 0;
}

Measured memory_bytes: 3184
#coding:utf-8

N, K = list(map(int, input().split()))

h=[]
for i in range(N):
    h_i = int(input())
    h.append(h_i)

h = sorted(h)

min_val = 100000000000
for i in range(N-K+1):
    min_val = min(abs(h[i+K-1] - h[i]), min_val)
print(min_val)    


Measured memory_bytes: 8280
import Control.Applicative
import Control.Monad
import Control.Monad.ST
import Data.Functor
import Data.Function
import Data.Monoid
import Data.Maybe
import Data.List
import Data.Foldable (foldMap)
import Data.List.Split
import Data.Bits
import Data.Char
import Data.Ix
import Data.Ratio
import Data.Ord
import Data.Tuple
import Data.Array.IO
import Data.Array.ST
import Data.IORef
import Data.STRef
 
readInt = read :: String -> Int
readDouble = read :: String -> Double
getInt = readLn :: IO Int
getInts = map readInt . words <$> getLine
sjoin :: (Show a) => [a] -> String
sjoin = unwords . map show
cond :: a -> a -> Bool -> a
cond t f c = if c then t else f
apply2 :: (a -> a -> b) -> [a] -> b
apply2 f [x,y] = f x y
apply3 :: (a -> a -> a -> b) -> [a] -> b
apply3 f [x,y,z] = f x y z
fnBin :: (b -> c -> d) -> (a -> b) -> (a -> c) -> a -> d
fnBin op f g x = op (f x) $ g x
fnTuple :: (a -> b, a -> c) -> a -> (b, c)
fnTuple (f,g) a = (f a, g a)
replace :: (Eq a) => a -> a -> [a] -> [a]
replace x y = map (\z -> if z==x then y else z)
modifyArray :: (Ix i, MArray a e m) => a i e -> i -> (e -> e) -> m ()
modifyArray arr ix f = readArray arr ix >>= writeArray arr ix . f
-- end of templete

leap y = (mod y 400 == 0) || (mod y 100 /= 0 && mod y 4 == 0)

f :: (Int,Int,Int) -> (Int,Int,Int) -> Int
f (y',m',d') (yy,mm,dd) = g (y',m',d')
  where
    days y m
      | elem m [1,3,5,7,8,10,12] = 31
      | elem m [4,6,9,11] = 30
      | leap y && m==2 = 29
      | m==2 = 28
    g (y,m,d)
      | m==13 = g (y+1,1,d)
      | d==1+days y m = g (y,m+1,1)
      | (y/=yy || m/=mm) = (days y m + 1 - d) + g (y,m+1,1)
      | y==yy && m==mm = dd - d

main = do
    p <- getInts
    when (any (/=(-1)) p) $ do
        let [y1,m1,d1,y2,m2,d2] = p
        print $ f (y1,m1,d1) (y2,m2,d2)
        main

Measured memory_bytes: 5476
#include <bits/stdc++.h>
using namespace std;
#define FAST       			ios_base :: sync_with_stdio(false); cin.tie(NULL);

int main() {
  FAST;
  int N, M;
  cin >> N;
  vector<int> B(N + 1);
  for (int i = 2; i < N + 1; i++) {
    cin >> M;
    B.at(M)++;
  }
  for (int i = 1; i < N + 1; i++) {
    cout << B.at(i) << endl;
  }
}

Measured memory_bytes: 3992
#include <bits/stdc++.h>
using namespace std;
using ll =long long;
#define all(v) v.begin(),v.end()
 ll H,W;

vector<string> vec;
vector<ll> A{1,0,-1,0};
vector<ll> B{0,1,0,-1};
vector<ll> C{-2,-1,0,1,2};
vector<ll> D{-2,-1,0,1,2};
int main() {

  cin>>H>>W;
  ll Ch,Cw;
  cin>>Ch>>Cw;
  Ch--;
  Cw--;
  ll Dh,Dw;
  cin>>Dh>>Dw;
  Dh--;
  Dw--;
  
  vec=vector<string> (H);
  for(ll i=0;i<H;i++) {
cin>>vec[i];
  }
  
  vector<vector<ll>> note(H,vector<ll>(W,-1));
  
  deque<tuple<ll,ll,ll>> S;
  
  S.push_back(make_tuple(Ch,Cw,0));
  
  while(!S.empty()) {
ll nh,nw,a;
    tie(nh,nw,a)=S.front();
    S.pop_front();
    
    if(note[nh][nw]!=-1) {
      continue;
    }
    
  
note[nh][nw]=a;
      
    
    
  
    
    
    
    for(ll i=0;i<4;i++) {
ll kh,kw;
      kh=nh+A[i];
      kw=nw+B[i];
      
      if(kh<0||kh>=H||kw<0||kw>=W) {
continue;
      }
      
      if(vec[kh][kw]=='#') {
continue;
      }
      if(note[kh][kw]!=-1) {
continue;
      }
      
      S.push_front(make_tuple(kh,kw,a));
    }
    
    for(ll i=0;i<5;i++) {
for(ll j=0;j<5;j++) {
if(abs(C[i])+abs(D[j])<=1) {
continue;
}
  ll kh,kw;
  kh=nh+C[i];
  kw=nw+D[j];
 
     if(kh<0||kh>=H||kw<0||kw>=W) {
continue;
      }
      
      if(vec[kh][kw]=='#') {
continue;
      }
      if(note[kh][kw]!=-1) {
continue;
      }
  
  S.push_back(make_tuple(kh,kw,a+1));
              
}
    }
    
  }
  
cout<<note[Dh][Dw]<<endl;
}

    
    
    
      
      
    
  
  
  
  
  


Measured memory_bytes: 14520
n,d=map(int,input().split())
X=[list(map(int,input().split())) for _ in range(n)]
f=0
for i in range(n-1):
  for j in range(i+1,n):
    l=(sum((X[i][a]-X[j][a])**2 for a in range(d)))**(1/2)
    if int(l)==l:
        f+=1
print(f)

Measured memory_bytes: 3060
N=int(input())

a=input().strip().split(" ")
a=[int(j) for j in a]

M=int(input())

for i in range(M):
    c=a[:]
    Sum=0
    b=input().strip().split(" ")
    b=[int(j) for j in b]
    c[b[0]-1]=b[1]
    for k in range(len(c)):
        Sum+=c[k]

    print(Sum)


Measured memory_bytes: 3060
N = int(input())

ans = [0]*(N+1)
for x in range(1, int(N**0.5)):
    for y in range(1, int(N**0.5)):
        for z in range(1, int(N**0.5)):
            S = x**2 + y**2 + z**2 + x*y + y*z + x*z
            if 1 <= S <= N:
                ans[S] += 1
            else:
                break

for i in range(1, N+1):
    print(ans[i])

Measured memory_bytes: 9392
import heapq as hq

N, M = [int(_) for _ in input().split()]
A = []
for a in [int(_) for _ in input().split()]:
    hq.heappush(A, -a)

for _ in range(M):
    v = hq.heappop(A)
    hq.heappush(A, v / 2)
print(-sum([int(a) for a in A]))


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

using namespace std;

#define int long long

main(){
    //freopen("input.txt", "r", stdin);
    //freopen("a.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, a, b;
    cin >> n;
    vector < pair < int, int > > Q;
    for (int i = 1; i <= n; ++i){
        cin >> a >> b;
        /*b -= a;
        if (b < 0){
            cout << "No" << '\n';
            return 0;
        }*/
        Q.push_back({b, a});
    }
    sort(Q.begin(), Q.end());
    int t = 0;
    //cout << endl;
    for (auto key : Q){
        t += key.second;
        if (t > key.first){
            cout << "No" << '\n';
            return 0;
        }
    }
    cout << "Yes" << '\n';
    return 0;
}


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

int main()
{
    //freopen("STRING.inp", "r", stdin);
    int n,cnt=0;
    string A,B,C;
    int d[27];
    cin >> n >> A >> B >> C;
    for (int i=0; i<n; i++)
    {
        d[A[i]-97]=0;
        d[B[i]-97]=0;
        d[C[i]-97]=0;
        d[A[i]-97]++;
        d[B[i]-97]++;
        d[C[i]-97]++;
        //cout << max(d[A[i]-97],max(d[B[i]-97],d[C[i]-97])) << " ";
        cnt=cnt+3-max(d[A[i]-97],max(d[B[i]-97],d[C[i]-97]));
    }
    cout << cnt;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(ll i=0;i<n;i++)
#define repl(i,l,r) for(ll i=(l);i<(r);i++)
#define per(i,n) for(ll i=n-1;i>=0;i--)
#define lper(i,r,l) for(ll i=r-1;i>=l;i--)
#define fi first
#define se second
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define CST(x) cout<<fixed<<setprecision(x)
using ll=long long;
using vl=vector<ll>;
using vvl=vector<vector<ll>>;
using pl=pair<ll,ll>;
const ll MOD=1000000007;
const ll MOD9=998244353;
const int inf=1e9+10;
const ll INF=4e18;
const ll dy[4]={1,0,-1,0};
const ll dx[4]={0,-1,0,1};
int main(){
    ll N;cin>>N;
    ll ans=inf;
    rep(i,N+1){
        ll now=0;
        ll t=i;
        while(t)now+=t%6,t/=6;
        t=N-i;
        while(t)now+=t%9,t/=9;
        ans=min(ans,now);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <cstdio>

#define MOD 1000000007

#define MAXN 40

int d[MAXN+1][1<<17];

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

    int ans=1;
    for(int i=1; i<=n; i++)
        ans=1LL*ans*10%MOD;

    for(int i=1; i<=10; i++)
        d[1][(1<<(i-1))&((1<<(x+y+z))-1)]++;

    for(int i=1; i<n; i++){
        for(int j=0; j<(1<<(x+y+z)); j++) if(d[i][j]){
            for(int cif=1; cif<=10; cif++){
                int e=((j<<cif)&((1<<(x+y+z))-1))|((1<<(cif-1))&((1<<(x+y+z))-1));
                if(((e&(1<<(z-1)))==0)||(((e>>z)&(1<<(y-1)))==0)||(((e>>(z+y))&(1<<(x-1)))==0)){
                    d[i+1][e]+=d[i][j];
                    if(d[i+1][e]>=MOD)
                        d[i+1][e]-=MOD;
                }
            }
        }
    }

    for(int i=0; i<(1<<(x+y+z)); i++){
        ans-=d[n][i];
        if(ans<0)
            ans+=MOD;
    }

    printf("%d\n", ans);

    return 0;
}


Measured memory_bytes: 19200
#include <bits/stdc++.h>
#define lli long long int  

using namespace std;

int main() {
    lli n;
    cin>>n;
    lli x=100,ans=0;
    while(x<n)
    {
        x=floor(1.01*x);
        ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3720
#include <iostream>
using std::cin;
using std::cout;
using std::endl;

int main()
{
    int N, K, count = 0, tmp = 0;
    cin >> N >> K;
    for (int i = 0; i < N; i++)
    {
        cin >> tmp;
        count += (tmp >= K) ? 1 : 0;
    }
    cout << count << endl;
    return EXIT_SUCCESS;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
template <class T> void corner(bool flg, T hoge) {
    if (flg) {
        cout << hoge << endl;
        exit(0);
    }
}
#define all(v) v.begin(), v.end()
#define inputv(v, n)                                                           \
    vl v;                                                                      \
    rep(i, n) {                                                                \
        ll x;                                                                  \
        cin >> x;                                                              \
        v.push_back(x);                                                        \
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;
ll dp[1011][10011];
int main() {
    cin >> h >> n;
    vl A, B;
    rep(i, n) {
        cin >> x >> y;
        A.push_back(x);
        B.push_back(y);
    }

    rep(i, n) {
        rep(j, h + 1) {
        	//cout<<i<<" "<<j<<endl;
            if (i == 0 && j == 0)dp[i][j] = 0;
            else {
                x = INF;
                y = INF;
                if (i >= 1)x = dp[i - 1][j];
                y = dp[i][j - min(j, A[i])] + B[i];
                dp[i][j] = min(x, y);
            }
        }
    }

    cout << dp[n - 1][h] << endl;
}

Measured memory_bytes: 78464
#include <stdio.h>

int main(void){

  int A, B, C;

  scanf("%d %d %d",&A,&B,&C);

  if(A==5&&B==5&&C==7){

    printf("YES\n");

  }else if(A==5&&B==7&&C==5){

    printf("YES\n");

  }else if(A==7&&B==5&&C==5){

    printf("YES\n");

  }else{

    printf("NO\n");

  }

  return 0;

}


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


int main(){
  int64_t N, A, B;
  cin>>N>>A>>B;

  int64_t ans=N/(A+B)*A;
  int64_t amari = N%(A+B);
  if(amari<=A){
    ans += amari;
  }
  else{
    ans += A;
  }
  
  cout<<ans<<endl;
  
}

Measured memory_bytes: 3612
#include <stdio.h>

int main(void) {
	int i,j,k,n,d[3],tmp;

	scanf("%d",&n);
	for(i=0;i<n;i++) {
		scanf("%d %d %d",&d[0],&d[1],&d[2]);
		for(j=0;j<2;j++) {
			for(k=j+1;k<3;k++) {
				if(d[j]<d[k]) {
					tmp=d[j];
					d[j]=d[k];
					d[k]=tmp;
				}
			}
		}
		printf("%s\n",d[0]*d[0]==d[1]*d[1]+d[2]*d[2]?"YES":"NO");
	}
	return 0;
}

Measured memory_bytes: 580
n,t=[int(x) for x in input().split()]
w=[]
for i in range(n):
    w.append(int(input()))

totalw=sum(w)  
pmax=totalw
pmin=int(totalw/t)-1

def check(ptest):
    tk=1
    p=0
    global t
    global w
    global n
    i=0
    
    while i<n:
        p+=w[i]
        if p<=ptest:
            i+=1
        else:
            tk+=1
            p=0
            
        if tk>t:
            return 0
            #break   
    
    return 1
    
        
while (pmax-pmin)>1:
    pmid=(pmax+pmin)//2
    if check(pmid)==1:
        pmax=pmid
    else:
        pmin=pmid
        
print(pmax)



Measured memory_bytes: 9564
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<sstream>
#include<cmath>
#include<numeric>
#include<map>
#include<stack>
#include<queue>
using namespace std;
int inf = 1000000000;


int main(void) {

  string s;
  priority_queue<int> pq;
  while(cin >> s){
    if( s == "end" ) break;
    else if( s == "extract" ){
      cout << pq.top() << endl;
      pq.pop();
    }else{
      int n;
      cin >> n;
      pq.push(n);
    }
  }

  return 0;
}

// EOF

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

int H, W;
long long mod = 998244353;
vector<int> A[309];

int main() {
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		A[i].resize(W, 0);
		for (int j = 0; j < W; j++) cin >> A[i][j];
	}
	sort(A, A + H);

	for (int i = 0; i < W; i++) {
		int pos = 0;
		for (int j = 0; j < H; j++) {
			int cnt = 0; for (int k = 0; k < i; k++) { if (A[j][k] == 1) cnt++; }
			if (cnt == 0) { pos = j; }
		}
		for (int j = pos - 1; j >= 0; j--) {
			if (A[j][i] == 0) continue;
			for (int k = 0; k < W; k++) A[j][k] ^= A[pos][k];
		}
		sort(A, A + H);
	}

	vector<int> ZERO(W, 0);
	long long v = 1;
	for (int i = 0; i < H; i++) {
		if (A[i] == ZERO) { v *= 2; v %= mod; }
	}
	long long p = 1; for (int i = 0; i < H; i++) { p *= 2; p %= mod; }
	long long q = 1; for (int i = 0; i < W; i++) { q *= 2; q %= mod; }
	long long r = (p - v + mod)*q%mod;
	if (r % 2 == 1) r += mod; r /= 2;
	cout << r << endl;
	return 0;
}

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

using namespace std;
typedef long long ll;

bool ask (ll x)
{
    cout << "? " << x << endl;
    char c;
    cin >> c;
    return c == 'Y';
}

int main()
{
    ios_base::sync_with_stdio(0);
    ll cp = 1;
    while (ask (cp) && cp < 2e12)
    {
        cp *= 10;
    }

    if (cp > 1e12)
    {
        ll cp = 9;
        while (true)
        {
            if (ask (cp))
            {
                cout << "! " << cp / 10 + 1 << "\n";
                return 0;
            }
            cp = 10 * cp + 9;
        }
    }
    ll rp = cp / 10;

    ll lo = rp, hi = cp - 1;
    while (lo < hi)
    {
        ll mid = (lo + hi) / 2;
        if (ask (10 * mid))
        {
            hi = mid;
        }
        else
        {
            lo = mid + 1;
        }
    }
    cout << "! " << lo << "\n";
}

Measured memory_bytes: 632
#ifdef __LOCAL
  #define _GLIBCXX_DEBUG
#endif
#include <bits/stdc++.h>
using namespace std;
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;}
#define itn int
#define fi first
#define se second
#define intmax numeric_limits<int>::max()
#define llmax numeric_limits<ll>::max()
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(int)(n);i>=1;i--)
#define all(vec) vec.begin(),vec.end()
#define sortt(vec) sort((vec).begin(),(vec).end())
#define rsort(vec) sort((vec).rbegin(), (vec).rend())
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=998244353;
const int inf=1<<30;
const ll lnf=1ll<<60;

struct mint {
  ll x; // typedef long long ll;
  mint(ll x=0):x((x%mod+mod)%mod){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) { (x *= a.x) %= mod; return *this;}
  mint operator+(const mint a) const { return mint(*this) += a;}
  mint operator-(const mint a) const { return mint(*this) -= a;}
  mint operator*(const mint a) const { return mint(*this) *= a;}
  mint pow(ll t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }

  // for prime mod
  mint inv() const { return pow(mod-2);}
  mint& operator/=(const mint a) { return *this *= a.inv();}
  mint operator/(const mint a) const { return mint(*this) /= a;}
};
istream& operator>>(istream& is, mint& a) { return is >> a.x;}
ostream& operator<<(ostream& os, const mint& a) { return os << a.x;}

mint dp[1000010];

int main(){
  itn n,k; cin >> n >> k;
  dp[0]=1;
  dp[1]=-1;
  vector<int> l(k);
  vector<int> r(k);
  rep(i,k) cin >> l[i] >> r[i];
  rep(i,n){
    if(i>0) dp[i]+=dp[i-1];
    rep(j,k){
      mint x=dp[i];
      if(i+l[j]<n) dp[i+l[j]]+=x;
      if(i+r[j]+1<n) dp[i+r[j]+1]-=x;
    }
  }
  cout << dp[n-1] << endl;
}

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

int sg[100001];

int n, k;
int arr[100];

int main()
{
    cin >> n >> k;
    for (int i = 0; i != n; ++i) scanf("%d", &arr[i]);
    
    for (int x = 0; x <= k; ++x)
    {
        set<int> mex;
        
        for (int i = 0; i != n; ++i)
        {
            if (x - arr[i] < 0) break;
            
            mex.insert(sg[x - arr[i]]);
        }
        
        auto it = mex.begin();
        for (int i = 0; i != mex.size(); ++i)
        {
            if (i != *it)
            {
                sg[x] = i;
                break;
            }
            ++it;
        }
        if (it == mex.end())
            sg[x] = mex.size();
    }
    
    cout << (sg[k] ? "First" : "Second");
    return 0;
}   

Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <array>
#include <vector>
#include <math.h>
#include <algorithm>
#include <set>
#include <deque>
#include <utility>
#include <queue>

#define MAX 21
#define ll long long int
using namespace std;

int main(void)
{
	int i, j;
	int len;
	int len2;
	string s;
	int n;

	cin >> s;

	while (1) {
		n = 0;
		s.pop_back();

		len = s.length();
		len2 = len / 2;

		if (len % 2 == 0) {
			for (i = 0; i < len2; i++) {
				if (s[i] != s[i + len2]) {
					n = 1;
					break;
				}
			}
		}

		if (n == 1) {
			continue;
		}
		if (len % 2 == 1) {
			continue;
		}

		break;


	}

	len = s.length();
	cout << len << endl;


	return (0);
}

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

using namespace std;

int main()
{
    string a, b, c;
    cin>>a>>b>>c;
    a[0] -= 32;
    b[0] -= 32;
    c[0] -= 32;
    cout<<a[0]<<b[0]<<c[0]<<endl;
    return 0;
}


Measured memory_bytes: 3564
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long lli;

int main() {
		lli carry_n = 1e16;
		lli move_n;

		scanf("%lld", &move_n);
		for ( int i = 0; i < 5; i++ ) {
				lli t;
				scanf("%lld", &t);
				if ( carry_n > t ) carry_n = t;
		}

		lli x = (move_n - 1) / carry_n;

		lli tt = 5;
		printf("%lld\n", tt + x);

		return 0;
}


Measured memory_bytes: 128