akhauriyash/Code-Regression huggingface dataset:
import java.util.*;
public class Main{
	public static void main(String[] args){
    	Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int m = sc.nextInt();
      int[] x = new int[m];
      int[] y = new int[m];
      for(int i = 0;i < m;i++){
      	x[i]=sc.nextInt();
        y[i]=sc.nextInt();
      }
      boolean[] red = new boolean[n+1];
      int[] cnt = new int[n+1];
      for(int i = 1;i <= n;i++){
        cnt[i]=1;
        red[i]=false;
      }
      red[1]=true;
      for(int i = 0;i < m;i++){
      	if(red[x[i]])red[y[i]]=true;
        cnt[x[i]]--;
        cnt[y[i]]++;
        if(cnt[x[i]]==0)red[x[i]]=false;
      }
      int sum = 0;
      for(int i = 1;i <= n;i++)if(red[i])sum++;
      System.out.println(sum);
    }
}

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

using namespace std;

int main(int argc, const char *argv[])
{
  int n, k;
  cin >> n >> k;
  do {
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
      cin >> a[i];
    }

    // 累積和を計算
    vector<int> com_sums(n + 1, 0);
    for (int i = 0; i < a.size(); i++) {
      com_sums[i + 1] = com_sums[i] + a[i];
    }

    int result = com_sums[k] - com_sums[k - k];
    for (int i = k + 1; i < a.size(); i++) {
      result = max(result ,com_sums[i] - com_sums[i - k]);
    }
    cout << result << "\n";

    cin >> n >> k;
  } while(n != 0);

  return 0;
}


Measured memory_bytes: 3636
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
s = readline().rstrip()
q = int(readline())
queries = [[i for i in readline().split()] for _ in range(q)]

from collections import deque

d = deque([i for i in s])
rev = 1

for query in queries:
    if query[0] == '1':
        rev *= -1
    else:
        if rev == 1:
            if query[1] == '1':
                d.appendleft(query[2])
            else:
                d.append(query[2])
        else:
            if query[1] == '1':
                d.append(query[2])
            else:
                d.appendleft(query[2])

s = ''.join(d)
if rev == 1:
    print(s)
else:
    print(s[::-1])

Measured memory_bytes: 32100
function Main(input) {
	input = input.split("");
	var flag = true;
	if(input.length%2==1) flag = false;
	for(var i=0;i<input.length/2;i++){
		if(input[i*2]=="h"&&input[i*2+1]=="i"){
			
		}else{
			flag = false;
		}
		if(!flag){
			break;
		}
	}
if(flag){
	console.log("Yes")
}else{
	console.log("No")
}
}Main(require("fs").readFileSync("/dev/stdin", "utf8").trim());

Measured memory_bytes: 21956
#include <stdio.h>
#include <math.h>

int main () {
    int n;
    double s[1000];
    double m, a;
    
    scanf("%d", &n);
    while (n != 0) {
        m = 0;
        a = 0;
        for (int i = 0; i < n; i++) {
        scanf("%lf", &s[i]);
        m += s[i];
        }
        m = m / n;
        for (int i = 0; i < n; i++) {
        a += (s[i] - m) * (s[i] - m);
        }
        a = a / n;
        a = sqrt(a);
        printf("%lf\n", a);
        scanf("%d", &n);
    }
}


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


    int a,b,c;
    cin>>a>>b>>c;
    if(a+b==c){
        cout<<"Yes";
    }else if(a+c==b){
        cout<<"Yes";
    }else if(b+c==a){
        cout<<"Yes";
    }else{
        cout<<"No";
    }
 return 0;
}


Measured memory_bytes: 256
//
// Created by Sotetsu KOYAMADA on 2020/03/02.
//

#include <vector>
#include <iostream>

struct UnionFind
{
    std::vector<int> parents;
    UnionFind(int n) : parents(n) { for (int i = 0; i < n; ++i) parents[i] = i; }
    int root(int i) { return i == parents[i] ? i : root(parents[i]); }
    bool same(int i, int j) { return root(i) == root(j); }
    void unite(int i, int j) {
        if (same(i, j)) return;
        parents[root(i)] = root(j);
    }
};


int main()
{
    int n, q, c, x, y;
    std::cin >> n >> q;
    UnionFind uf(n);
    for (int i = 0; i < q; ++i) {
        std::cin >> c >> x >> y;
        if (c == 0) {
            uf.unite(x, y);
        } else {
            if (uf.same(x, y)) {
                std::cout << 1 << std::endl;
            } else {
                std::cout << 0 << std::endl;
            }
        }
    }
    return 0;
}



Measured memory_bytes: 3160
const input = require('fs').readFileSync('/dev/stdin', 'utf8');
const lines = input.split('\n');
const K = +lines[0];
const line2nd = lines[1].split(' ');
const A = +line2nd[0];
const B = +line2nd[1];

// console.log(`K=${K} A=${A} B=${B}`);

let isOK = false;
for (let i = A; i <= B; i++) {
    if (i % K === 0) {
        console.log('OK');
        isOK = true;
        return;
    }
}

if (!isOK) {
    console.log('NG');
}


Measured memory_bytes: 29624
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod107 1000000007
#define rep(i, n) for (int i = 0; i < n; ++i)
using Graph = vector<vector<int>>;
#define grepq priority_queue<double, std::vector<double>, std::greater<double>>
#define all(v) v.begin(), v.end()
#define PI acos(-1)

const ll INF = 10010001010;
const int inf = 1000034000;
typedef vector<ll> vecl;
typedef vector<int> veci;
typedef tuple<string, int, int> TUP;

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


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //cout << fixed << setprecision(15);
    int N;
    cin >> N;
    vector<int> P(N);
    int dif = 0;
    for (int i = 0; i < N; i++)
    {
        cin >> P[i];
        if(P[i] != i+1){
            dif++;
        }
    }
    if(dif > 2){
        cout << "NO" << endl;
    }
    else{
        cout << "YES" << endl;
    }
}


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

int main(){
	
	string s;
	cin >> s;
	set<char> se(s.begin(),s.end());
	for (char c='a'; c<='z'; c++){
		if (se.count(c)==0) {cout << c; return 0;}
	}
	cout << "None";
	
}



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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()

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

    cout << ((n[0] == '9' || n[1] == '9') ? "Yes" : "No") << "\n";

    return 0;
}


Measured memory_bytes: 3552
#include <bits/stdc++.h>
#define FOR(i, l, r) for(ll i = l; i < r; i++)
#define rep(i, N) FOR(i, 0, N)
using namespace std;

typedef long long ll;
typedef pair<int,int> P;
typedef vector<int> vi;
typedef vector<ll> vl;
const ll MOD = round(1e9+7);


int main() {
    int N; cin >> N;
    
    vector<bool> num(56565, true);
    num[1] = false; num[2] = true;
    for(int j = 2*2; j < 55565; j += 2){
        num[j] = false;
    }
    for(int i = 3; i*i < 55565; i+=2){
        if(num[i])
            for(int j = i*i; j < 55565; j += i*2){
                num[j] = false;
            }
    }

    queue<int> que;
    int tmp = 2;
    rep(i,N) {
        while(!num[tmp] || tmp%5 != 1) tmp++;
        que.push(tmp);
        tmp++;
    }

    while(!que.empty()){
        cout << que.front() << " ";
        que.pop();
    }
    return 0;
}


Measured memory_bytes: 3592
# AOJ 0240: Interest Rates
# Python3 2018.6.25 bal4u

while True:
	n = int(input())
	if n == 0: break	
	y = float(input())
	id, vmax = -1, 0
	for i in range(n):
		b, r, t = map(int, input().split())
		if t == 1: m = y*(r/100)+1
		else: m = (r/100+1)**y
		if id < 0 or m >= vmax: id, vmax = b, m
	print(id)


Measured memory_bytes: 5696
#include<bits/stdc++.h>
#define ll long long int
#define ld long double
#define vii vector<ll> 
#define pb push_back
#define fast ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;
const int MOD = 1e9 + 7, N = 1e5 + 3;
 
int main(){
    fast;
    ll n, m, k;
    cin >> n >> m >> k;
    ll a[n+1], b[m+1], prefix_sum[n+1], prefix_sum1[m+1];
    prefix_sum[0] = 0;
    prefix_sum1[0] = 0;
    for(int i = 1; i <= n; ++i){
        cin >> a[i];
        prefix_sum[i] = prefix_sum[i-1] + a[i];
    }
    for(int i = 1; i <= m; ++i){
        cin >> b[i];
        prefix_sum1[i] = prefix_sum1[i-1] + b[i];
    }
    ll mx = 0;
    for(int i = 0; i <= n; ++i){
        ll diff = k - prefix_sum[i], ans = 0;
        if(diff < 0)
            break;
        ll low = 1, high = m;
        while(low <= high){
            ll mid = (low + high)/2;
            if(prefix_sum1[mid] <= diff){
                ans = mid;
                low = mid + 1; 
            }
            else
                high = mid - 1;
        }
        mx = max(mx, i+ans);  
        // cout << i << ' ' << ans << ' ';
    }
    cout << mx;
    return 0;
}


Measured memory_bytes: 9888
#include<iostream>

using namespace std;

int main()
{
	int N;
	int ans = 0;
	string S;

	int x[26],y[26];

	cin >> N >> S;

	for(int i=0;i<26;i++)
	{
		x[i] = 0;
		y[i] = 0;
	}

	for(int i=0;i<N+1;i++)
	{
		for(int j=0;j<i;j++)
		{
			x[S[j]-'a']++;
		}
		for(int j=i;j<N;j++)
		{
			y[S[j]-'a']++;
		}
		int cnt = 0;
		for(int j=0;j<26;j++)
		{
			if(x[j]>0 && y[j]>0)
			{
				cnt++;
			}
			x[j] = 0;
			y[j] = 0;
		}
		ans = max(ans,cnt);
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        String s = sc.nextLine();
        int x = 0;

        for(int i = 0; i < 3; i++){
            if(s.charAt(i) == '1') x++;
        }

        System.out.println(x);

        sc.close();
    }
}

Measured memory_bytes: 22996
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define db double
#define pint pair<int,int>
#define mk(x,y) make_pair(x,y)
#define fir first
#define sec second
#define Rep(x,y,z) for(int x=y;x<=z;x++)
#define Red(x,y,z) for(int x=y;x>=z;x--)
using namespace std;
const int MAXN=1e6+5;
char buf[1<<12],*pp1=buf,*pp2=buf,nc;int ny;
inline char gc() {return pp1==pp2&&(pp2=(pp1=buf)+fread(buf,1,1<<12,stdin),pp1==pp2)?EOF:*pp1++;}
//inline char gc(){return getchar();}
inline int read(){
	int x=0;for(ny=1;nc=gc(),(nc<48||nc>57)&&nc!=EOF;)if(nc==45)ny=-1;if(nc<0)return nc;
	for(x=nc-48;nc=gc(),47<nc&&nc<58&&nc!=EOF;x=(x<<3)+(x<<1)+(nc^48));return x*ny;
}
int l[MAXN],r[MAXN],cnt[3],a[MAXN],n,c[3];char s[MAXN];
inline void Del(int x){cnt[a[x]]--,r[l[x]]=r[x],l[r[x]]=l[x];}
inline bool cmp(int x,int y){return cnt[x]<cnt[y];}
inline void Sort(){Rep(i,0,2)c[i]=i;sort(c,c+3,cmp);}
vector<int>S;
int main(){
//	freopen("std.in","r",stdin);
//	freopen("std.out","w",stdout);
	scanf("%s",s+1),n=strlen(s+1),a[0]=a[n+1]=-1;
	Rep(i,0,n+1)l[i]=i-1,r[i]=i+1;
	Rep(i,1,n){cnt[a[i]=s[i]-'A']++;if(a[i]==a[i-1])Del(i);}Sort();
	for(int i=r[0];i!=n+1;i=r[i])if(a[i]==c[2]&&a[l[i]]!=a[r[i]])S.push_back(i);
	for(int i=0;i<S.size()&&cnt[c[2]]!=cnt[c[1]];i++)Del(S[i]);S.clear();
	for(int i=r[0];i!=n+1;i=r[i])if(a[i]==c[2]&&a[l[i]]==c[0]&&a[r[i]]==c[0])S.push_back(i);
	for(int i=0;i<S.size()&&cnt[c[2]]!=cnt[c[1]];i++)Del(S[i]),Del(r[S[i]]);S.clear();
	for(int i=r[0];i!=n+1;i=r[i])if(a[i]==c[2]&&a[r[i]]==c[1])S.push_back(i);
	for(int i=0;i<S.size()&&cnt[c[1]]!=cnt[c[0]];i++)if(a[l[S[i]]]!=c[0]||a[r[r[S[i]]]]!=c[0])Del(S[i]),Del(r[S[i]]);S.clear();
	for(int i=r[0];i!=n+1;i=r[i])if(a[i]==c[2]&&a[l[i]]==c[1])S.push_back(i);
	for(int i=0;i<S.size()&&cnt[c[1]]!=cnt[c[0]];i++)if(a[r[S[i]]]!=c[0]||a[l[l[S[i]]]]!=c[0])Del(S[i]),Del(l[S[i]]);S.clear();
	if(cnt[0]==cnt[1]&&cnt[1]==cnt[2])for(int i=r[0];i!=n+1;i=r[i])putchar(s[i]);
	return 0;
}




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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
int main(){
  int n,m;cin>>n>>m;
  vector<vector<pair<int,int> > >vvi(n+10);
  pair<int,int> ans[m+10]={};
  for(int i=0;i<m;i++){
    int a,b;cin>>a>>b;
    vvi[a-1].pb(mp(b,i));
  }
  for(int i=0;i<n;i++)
    sort(ALL(vvi[i]));
  for(int i=0;i<n;i++)
    for(int j=0;j<vvi[i].size();j++){
      ans[vvi[i][j].S]=mp(i+1,j+1);
    }
  for(int i=0;i<m;i++){
    printf("%06d%06d\n",ans[i].F,ans[i].S);
  }
  return 0;
}


Measured memory_bytes: 7680
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main
{

	public static void main(String[] args)throws IOException
	{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String str;
		int premax=2;
		int[] h=new int[1000000];
		h[1]=0;h[2]=1;
		while((str=br.readLine())!=null)
		{
			int n=Integer.parseInt(str);
			if(premax<n)
			{
				for(int i=premax+1;i<=n;i++)
				{
					h[i]=h[i-1];
					if(i%2==0)
					{}
					else
					{
						for(int j=3;j<=(int)Math.sqrt(i);j+=2)
						{
							if(i%j==0){h[i]--;break;}
						}
						h[i]++;

					}
				}
				premax=n;
			}
			System.out.println(h[n]);


		}
	}

}

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

using namespace std;

const int N = 22, M = (1<<22), MOD = 1e9 + 7;
int dp[N][M], n, a[N][N];

inline int add(int a, int b){
	a += b;
	if(a >= MOD)a -= MOD;
	return a;
}

inline int sub(int a, int b){
	a -= b;
	if(a < 0)a += MOD;
	return a;
}

int find(int id, int mask){
	if(id < 0)return mask == 0;
	if(dp[id][mask] != -1)return dp[id][mask];

	dp[id][mask] = 0;
	for(int i=0;i<n;++i)if((mask & (1<<i)) && a[id][i])
		dp[id][mask] = add(dp[id][mask], find(id - 1, mask ^ (1<<i)));

	return dp[id][mask];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

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

	for(int i=0;i<n;++i)
		for(int mask=0;mask < (1<<n); ++mask)
			dp[i][mask] = -1;

	cout<<find(n - 1, (1<<n) - 1)<<"\n";
	return 0;
}


Measured memory_bytes: 215296
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  char N;
  int ans=0;
  cin >> N;
  if(N=='a'||N=='i'||N=='o'||N=='u'||N=='e'){
      cout << "vowel" << endl;
  }else{
    cout << "consonant" << endl;
  }
  
  return 0;
}

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

typedef long long ll;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
typedef pair<ll,ll> pii;
typedef vector<pii> vpii;

#define pb(x) push_back(x)
#define ppb() pop_back()
#define mp(x,y) make_pair(x,y)
#define mod 1000000007
#define FOR0(i,n) for(ll i=0;i<n;i++)
#define FOR(i,a,b) for(ll i = a; i < b; i++)
#define FORD(i,a,b) for(ll i=(a);i>=(int)(b);i--)
#define sf(n) scanf("%lld", &n)
#define sfc(x) scanf("%c", &x)
#define pf(x) printf("%lld", x)
#define pff(x) printf("%lf", x)
#define pfc(x) printf("%c", x)
#define pfs(x) printf("%s", x)
#define sf2(a,b) scanf("%lld %lld", &a, &b)
#define sf3(a,b,c) scanf("%lld %lld %lld", &a, &b, &c)
#define pfn(n) printf("%lld\n", n)
#define pfs(n) printf("%lld ", n)
#define ff first
#define ss second
#define mem(a,b) memset(a,b,sizeof(a))
#define sz size()
#define ll long long
#define fast ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);

bool prime[500010];
void SieveOfEratosthenes(ll n)
{
    memset(prime,true, sizeof(prime));

    for (ll p=2; p*p<=n; p++)
    {
        if (prime[p] == true)
        {
            for (ll i=p*p; i<=n; i += p)
                prime[i] = false;
        }
    }
}

ll power(ll x,ll y)
{
    if (y == 0)
        return 1;
    else if (y%2 == 0)
        return power(x, y/2)*power(x, y/2);
    else
        return x*power(x, y/2)*power(x, y/2);
}

ll power1(ll a,ll b){
	ll res=1;
	while(b){
		if(b&1){
			res*=a;
		}
		a=a*a;
		b>>=1;
	}
	return res;
}



ll mod_power(ll a,ll b,ll m){
	ll res=1;
	a%=m;
	while(b){
		if(b&1){
			res=res*a%m;
		}
		a=a*a%m;
		b>>=1;
	}
	return res;
}
ll printDivisors(ll n) 
{ 
	ll count=0;
    for (ll i=1; i<=sqrt(n); i++) 
    { 
        if (n%i == 0) 
        { 
            if (n/i == i) 
                count++; 
  
            else // Otherwise print both 
                printf("%d %d ", i, n/i); 
        } 
    } 
} 
bool isPrime(int n)
{
    if (n <= 1)  return false;
    if (n <= 3)  return true;

    if (n%2 == 0 || n%3 == 0) return false;

    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;

    return true;
}
ll par[1000001];
ll ranki[1000001]={0};

ll find(ll x){
	if(par[x]!=x){
		par[x] = find(par[x]);
	}
	return par[x];
}

void unionset(ll x,ll y){
	ll xr = find(x);
	ll yr = find(y);
	if(ranki[xr]>ranki[yr]){
		par[yr]=xr;
	}
	else if(ranki[xr]<ranki[yr]){
		par[xr]=yr;
	}
	else{
		par[yr] = xr;
		ranki[xr]++;
	}
}

vector<ll> v[100001];
ll vis[100001]={0};
void dfs1(ll s){
    vis[s]=1;
    FOR0(i,v[s].size()){
        if(!vis[v[s][i]]){
            dfs1(v[s][i]);
        }
    }
}

void dfs(ll s){
    stack<ll> st;
    st.push(s);
    vis[s]=1;
    while(!st.empty()){
        ll u = st.top();
        st.pop();
        FOR0(i,v[u].size()){
            if(!vis[v[u][i]]){
                st.push(v[u][i]);
                vis[v[u][i]]=1;
            }
        }
    }
}


int main(){
    fast
    ll n,k;
    cin>>n>>k;
    cout<<n-k+1<<endl;
}

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

int main () {
  int upper_limit_of_terms = 1,wanted_sum = 1;
  while (1) {
    int number_of_wanted_sum = 0;
    cin >> upper_limit_of_terms >> wanted_sum;
	if (upper_limit_of_terms == 0 && wanted_sum == 0) return 0;
	for (int i = upper_limit_of_terms;i>=3;--i) {
	  for (int j = upper_limit_of_terms-1;j>=2;--j) {
	    if (j > i) continue;
	    for (int k = upper_limit_of_terms-2;k>=1;--k) {
		  if (i == j || j == k || k == i || k > j) continue;
		  if (i+j+k == wanted_sum) ++number_of_wanted_sum;
		}
	  }
	}
	cout << number_of_wanted_sum << endl;
  }
  return 0;
}

Measured memory_bytes: 3080
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<iomanip>

using namespace std;
typedef long long ll;
const ll LINF = 1e18;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

double ev[302][302][302];
double pr[302][302][302];
int main(){
  int N,t;
  cin >> N;
  vector<int> cnt(4,0);
  for(int i=0;i<N;i++){
    cin >> t;
    cnt[t]++;
  }
  pr[cnt[1]][cnt[2]][cnt[3]] = 1;
  double dn = (double)N;
  for(int i=N;i>=0;i--){
    for(int j=N;j>=0;j--){
      for(int k=N;k>=0;k--){
        double tev=0,tpr;
        int s = i+j+k;
        if (pr[k+1][j][i] > 0){
          tpr = pr[k+1][j][i] * (k+1)/(s+1);
          pr[k][j][i] += tpr;
          tev += (ev[k+1][j][i] + dn/(s+1))*tpr;
        } 
        if (k-1 >= 0 && pr[k-1][j+1][i] > 0){
          tpr = pr[k-1][j+1][i] * (j+1)/s;
          pr[k][j][i] += tpr;
          tev += (ev[k-1][j+1][i] + dn/s)*tpr;
        } 
        if (j-1 >= 0 && pr[k][j-1][i+1] > 0){
          tpr = pr[k][j-1][i+1] * (i+1)/s;
          pr[k][j][i] += tpr;
          tev += (ev[k][j-1][i+1] + dn/s)*tpr;
        }
        ev[k][j][i] = tev/pr[k][j][i];
      }
    }
  }
  cout << fixed << setprecision(10) << ev[0][0][0] << endl;
  return 0;
}



Measured memory_bytes: 430336
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define INF 99999999999
#define rep(i,m,n) for(lli i = m;i < n;i++)
#define rrep(i,m,n) for(lli i=m-1;i>=n;i--)
#define pb(n) push_back(n)
#define UE(N) N.erase(unique(N.begin(),N.end()),N.end());
#define Sort(n) sort(n.begin(), n.end())
#define Rev(n) reverse(n.begin(),n.end())
#define Out(S) cout << S << endl
#define NeOut(S) cout << S
#define HpOut(S) cout << setprecision(20) << S << endl
#define Vecpr(K,L1,L2,N) vector<pair<L1,L2>> K(N)
#define Vec(K,L,N,S) vector<L> K(N,S)
#define DV(K,L,N,M,R) vector<vector<L>> K(N, vector<L>(M,R))
#define pint pair<lli,lli>
#define Lower(v,X) lower_bound(v.begin(),v.end(),X)-v.begin();
#define mod 1000000007
#define MAX 5100000
#define ceili(x,y) (x+y-1)/y  
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int main(){
  lli A,B,C,D,E,L,R,X,Y,W,H,N,M,K,sum=0,num=0,flag=0;string S,T;
  cin >> N;
  DV(G,pint,N,0,pint(0,0));//親の顔より見たグラフ(Graph[頂点][隣接頂点/距離])
  Vec(dist,int,N,0);//探索済みかどうか
  Vec(color,int,N,0);//こたえを入れる
  rep(i,0,N-1){
    cin >> X >> Y >> K;//頂点,隣接頂点,距離
    G[X-1].pb(pint(Y-1,K%2));//距離は偶奇が分かればおｋ
    G[Y-1].pb(pint(X-1,K%2));
  }
  queue<pint> que;
  que.push(pint(0,0));//全頂点は繋がっているので適当に頂点0を根にする。secondは色
  dist[0]=1;
  //BFS
  while(!que.empty()){
    auto Xq=que.front();que.pop();
    int v=Xq.first;//vertex
    int c=Xq.second;//color
    for(auto i:G[v]){
      int nv=i.first;
      int nc=i.second;
      if(dist[nv])continue;//2回目は探索しない
      dist[nv]++;
      //c^ncで偶奇判定する
      que.push(pint(nv,c^nc));
      color[nv]=c^nc;
    }
  }
  rep(i,0,N)Out(color[i]);
} 

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

#define f(i,a,b) for( ll i = a; i < b ; i++ ) 
#define af(i,a,b) for( ll i = a; i >= b ; i--)
#define rep(i,a,b,k) for(ll i = a; i < b ; i+= k )
#define arep(i,a,b,k) for( ll i = a; i >= b ; i-= k)
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define sz(a) (ll) a.size()
#define all(a) a.begin(), a.end()
#define sor(a) sort( a.begin(), a.end() )
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL)
#define inter ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)

// policy-based
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;	


using namespace std;


typedef long long ll; // int or long long
typedef long double ld;
typedef pair<ll,ll> ii ;
typedef vector<ll>  vi ;
typedef vector<ii> vii ;

/*
typedef tree<
ll,
null_type,
less<ll>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
*/
 
const ll MAX = 1e6+100;
const ll inf = 1e15;
const ll mod = 1e9+7;


ll a[MAX],b[MAX],n,k;


bool go(ll x){
	vi num;
	f(i,0,n) num.push_back(x/b[i]);
	sort(all(num));
	ll ans = 0;
	f(i,0,n) ans+= max(0LL,a[i]-num[i]);
	return ans<=k;
}


int main(){
	fastio;
	cin >> n >> k;
	f(i,0,n) cin >> a[i];
	f(i,0,n) cin >> b[i];
	sort(a,a+n);
	ll ini = 0,fin = 1e12;
	while(ini< fin){
		ll mid = (ini+fin)/2;
		if(go(mid)) fin = mid;
		else ini = mid+1;
	}
	cout << ini << endl;
}

Measured memory_bytes: 10008
import sys
from copy import deepcopy
def main():
    INF=sys.maxsize
    N,M,X=tuple(map(int,sys.stdin.readline().split()))
    B=[]
    for _ in [0]*N:B.append([int(x) for x in sys.stdin.readline().split()])
    T=[0 for _ in range(M+1)]
    T[0]=INF
    for p in range(1,2**N):
        TT=[0 for _ in range(M+1)]
        for i in range(N):
            f=(p>>i)&1
            if f>0:TT=list(map(lambda x:x[0]+x[1],zip(TT,B[i])))
        F=list(map(lambda x:x>=X,TT[1:]))
        #print(f'TT[0], T[0], ... = {TT[0]}, {T[0]}, {F}')
        if TT[0]<T[0] and all(F):T=TT
    print(T[0]) if T[0]!=INF else print('-1')
if __name__=='__main__':main()


Measured memory_bytes: 9252
#include <iostream>

using namespace std;

int main() {
	string SA, SB, SC;
	cin >> SA >> SB >> SC;

	int total_turn = SA.length() + SB.length() + SC.length();

	char turn = 'a';
	for (int i = 0; i < total_turn; i++) {
		//cout << "turn:" << (char)turn << endl;
		if (SA.length() == 0 && turn=='a') {
			cout << "A" << endl;
			return 0;
		}
		else if (SB.length() == 0 && turn == 'b') {
			cout << "B" << endl;
			return 0;
		}
		else if (SC.length() == 0 && turn == 'c') {
			cout << "C" << endl;
			return 0;
		}
		//cout << "---" << endl;
		if (turn == 'a') {
			turn = SA[0];
			SA = SA.erase(0, 1);
			//cout << SA << endl;
		}
		else if (turn == 'b') {
			turn = SB[0];
			SB = SB.erase(0, 1);
			//cout << SB << endl;
		}
		else if (turn == 'c') {
			turn = SC[0];
			SC = SC.erase(0, 1);
			//cout << SC << endl;
		}
	}
}


Measured memory_bytes: 256
N = int(input())
trains = []
for _ in range(N - 1):
    c, s, f = map(int, input().split())
    trains.append((c, s, f))

for start in range(0, N):
    now = 0
    for c, s, f in trains[start:]:
        if now < s:
            now = s
        now += (f - now % f) % f
        now += c
    print(now)


Measured memory_bytes: 3188
#include <algorithm>
#include <iomanip>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <vector>
#define SORT(a) sort(a.begin(), a.end())
#define RSORT(a) sort(a.rbegin(), a.rend())
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n; 0 <= i; i--)
#define FOR(i, start, end) for (int i = start; i < end; i++)
#define FORSTEP(i, start, end, step) for (int i = start; i < end; i += step)
#define RFOR(i, start, end) for (int i = start; end <= i; i--)
#define ALL(a) a.begin(), a.end()
#define MOD(a) a %= 1000000007
typedef long long ll;
const int INF32 = 2147483647;
const ll INF64  = 9223372036854775807;
using namespace std;
template <class T> inline bool chmin(T &a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T> inline bool chmax(T &a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

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

    int N;
    cin >> N;
    vector<int> a(N);
    REP(i, N) cin >> a[i];

    vector<int> ans;
    REP(i, N) {
        if (i % 2 == 0) {
            ans.push_back(a[i]);
        } else {
            ans.insert(ans.begin(), a[i]);
        }
    }
    if (N % 2 == 0) {
        REP(i, N) { cout << ans[i] << " "; }
    } else {
        RREP(i, N - 1) { cout << ans[i] << " "; }
    }
    cout << endl;

    return 0;
}

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

using namespace std;

int main()
{
	string s;

	cin >> s;

	int count=0;
	int max=0;
	for(int i=0;i<s.length();i++){
		if (s[i]=='A'||s[i]=='T'||s[i]=='C'||s[i]=='G'){
			count++;
			if (count> max){
				max=count;
			}
		}else{
			count=0;
		}
	}
	cout << max <<'\n';
}


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

using namespace std;

typedef long long ll;

ll gcd(ll a, ll b) {
  if (a < b) {
    swap(a, b);
  }
  
  if (b == 0) {
    return a;
  }
  
  return gcd(a % b, b);
}

ll lcm(ll a, ll b) {
  return a * b / gcd(a, b);
}

ll div(ll a, ll C, ll D) {
  return a - (a / C + a / D - a / lcm(C, D));
}

int main() {
  ll A, B, C, D;
  
  cin >> A >> B >> C >> D;
  
  cout << div(B, C, D) - div(A - 1, C, D)<< endl;
  
  return 0;
}


Measured memory_bytes: 256
# coding: utf-8
# Stable Sort 2018/3/12

class Card(object):
    def __init__(self, card):
        self.value = int(card[1])
        self.card = card

    def __repr__(self):
        return self.card


def BubbleSort(C, N):
    for i in range(N):
        for j in reversed(range(i+1, N)):
            if C[j].value < C[j-1].value:
                C[j], C[j-1] = C[j-1], C[j]
    return C


def SelectionSort(C, N):
    for i in range(N):
        minj = i
        for j in range(i, N):
            if C[j].value < C[minj].value:
                minj = j
        C[i], C[minj] = C[minj], C[i]
    return C


def isStable(inl, out):
    n = len(inl)
    for i in range(n):
        for j in range(i+1, n):
            for a in range(n):
                for b in range(a+1, n):
                    if inl[i].value == inl[j].value and inl[i] == out[b] and inl[j] == out[a]:
                        return False
    return True


def print_stable(inl, out):
    if isStable(inl, out):
        print "Stable"
    else:
        print "Not stable"


if __name__ == "__main__":
    N = int(raw_input())
    inputs = raw_input().split()
    C = []
    for i in inputs:
        C.append(Card(i))
    Cb = BubbleSort(list(C), N)
    print " ".join([i.card for i in Cb])
    print_stable(C, Cb)
    Cs = SelectionSort(list(C), N)
    print " ".join([i.card for i in Cs])
    print_stable(C, Cs)



Measured memory_bytes: 4760
using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static string InputPattern = "InputX";

    static List<string> GetInputList()
    {
        var WillReturn = new List<string>();

        if (InputPattern == "Input1") {
            WillReturn.Add("127");
            //4
        }
        else if (InputPattern == "Input2") {
            WillReturn.Add("3");
            //3
        }
        else if (InputPattern == "Input3") {
            WillReturn.Add("44852");
            //16
        }
        else {
            string wkStr;
            while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
        }
        return WillReturn;
    }

    static void Main()
    {
        List<string> InputList = GetInputList();
        int N = int.Parse(InputList[0]);

        //引出金額のList
        var HikidasiList = new List<int>();
        HikidasiList.Add(1);

        int wkVal = 1;

        for (int I = 1; wkVal < int.MaxValue; I++) {
            wkVal *= 6;
            if (N < wkVal) break;
            HikidasiList.Add(wkVal);
        }
        wkVal = 1;
        for (int I = 1; wkVal < int.MaxValue; I++) {
            wkVal *= 9;
            if (N < wkVal) break;
            HikidasiList.Add(wkVal);
        }

        //最小の引出回数なDP表[残金]
        var DPDict = new Dictionary<int, int>();
        DPDict[N] = 0;

        int Answer = int.MaxValue;
        for (int I = 1; I < Answer; I++) {
            foreach (int EachHikidasi in HikidasiList) {
                foreach (int EachKey in DPDict.Keys.ToArray()) {
                    int NewKey = EachKey - EachHikidasi * I;
                    if (NewKey < 0) continue;
                    int NewVal = DPDict[EachKey] + I;

                    if (DPDict.ContainsKey(NewKey) == false || DPDict[NewKey] > NewVal) {
                        DPDict[NewKey] = NewVal;
                    }
                }
            }
            if (DPDict.ContainsKey(0)) {
                Answer = DPDict[0];
            }
        }
        Console.WriteLine(Answer);
    }
}


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

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

    string ans;
    if(s[0] == s[1] && s[1] == s[2])
        ans = "Yes";
    else
    if(s[1] == s[2] && s[2] == s[3])
        ans = "Yes";
    else
        ans = "No";

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
s=input()
a,b=-1,-1
for i in range(len(s)-1):
    if s[i]==s[i+1]:
        a,b=i+1,i+2
        break
if a+b==-2:
    for i in range(len(s)-2):
        if s[i]==s[i+2]:
            a,b=i+1,i+3
            break
print(a,b)

Measured memory_bytes: 3188
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vs = vector<string>;
using msi = map<string, int>;
using mii = map<int, int>;
using psi = pair<string, int>;
using pii = pair<int, int>;
using vlai = valarray<int>;
#define rep(i,n) for(int i=0;i<n;i++)
#define range(i,s,n) for(int i=s;i<n;i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define INF 1E9
#define EPS 1E-9
#define MOD (ll)(1E9+7)
#define PI 3.1415926535897932384

template <class T>ostream &operator<<(std::ostream &o, const vector<T> &v)
{
	rep(i, v.size()) {
		o << (i > 0 ? " " : "") << v[i];
	}
	return o;
}



int main() {
	int a,b,cost;
	while (1) {
		cin >> a >> b>>cost;
		if (a == 0 && b == 0&&cost==0) break;
		double ma = -1;
		for (int i = 1; i <= cost ; i++) {
			for (int j = 1; j <= cost ; j++) {
				if ((floor(i*(100.0 + a) / 100.0) + floor(j*(100.0 + a) / 100.0)) == cost) {
					if (ma < (floor(i*(100.0+b)/100.0)+ floor(j*(100.0 + b) / 100.0))) {
						ma = floor(i*(100 + b) / 100.0) + floor(j*(100 + b) / 100.0);
					}
				}
			}
		}

		cout <<ma << endl;
	}
}



Measured memory_bytes: 3200
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
	int N; cin >> N;
	int a[N];
	rep(i, N) cin >> a[i];
	sort(a, a + N);
	cout << a[N - 1] - a[0] << endl;

    return 0;
}


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

int main(){
  char b;
  cin >> b;
  if(b == 'A') cout << 'T' << endl;
  else if(b == 'T') cout << 'A' << endl;
  else if(b == 'G') cout << 'C' << endl;
  else if(b == 'C') cout << 'G' << endl;
}

Measured memory_bytes: 256
def main():
    N = int(input())
    L = len(str(N))
    cand = []
    def dfs(s,N,cand):
        if s != '' and int(s) > N:
            return
        
        for i in ['3','5','7']:
            tmp = s + i
            if int(tmp) <= N:
                cand.append(tmp)
            dfs(tmp,N,cand)
    
    dfs('',N,cand)
    ans = 0
    for c in cand:
        if c.count('3') >= 1 and c.count('5') >= 1  and c.count('7') >= 1:
            ans += 1
    print(ans)
if __name__ == "__main__":
    main()

Measured memory_bytes: 77356
import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class Main {

	static final Scanner in = new Scanner(System.in);
	static final PrintWriter out = new PrintWriter(System.out,false);
	static boolean debug = false;

	static long req(int n, int k, long psum, int[] a) {
		int l = 0, r = k;
		long sub = 0, plu = 0;
		for (int i=l; i<r; i++) {
			if (a[i] < 0) sub += -a[i];
			else plu += a[i];
		}

		long res = 0;

		while (r <= n) {
			res = Math.max(res, Math.max(psum - plu, psum - sub));

			if (a[l] < 0) sub -= -a[l];
			else plu -= a[l];
			if (a[r] < 0) sub += -a[r];
			else plu += a[r];
			l++; r++;
		}

		return res;
	}

	static void solve() {
		int n = in.nextInt();
		int k = in.nextInt();
		int[] a = new int[n+1];
		int[] b = new int[n+1]; // rev

		long sum = 0;
		long psum = 0;

		for (int i=0; i<n; i++) {
			a[i] = in.nextInt();
			b[n-1-i] = a[i];
			sum += a[i];
			if (a[i] > 0) psum += a[i];
		}

		long ans = req(n, k, psum, a);

		out.println(ans);
	}

	public static void main(String[] args) {
		debug = args.length > 0;
		long start = System.nanoTime();

		solve();
		out.flush();

		long end = System.nanoTime();
		dump((end - start) / 1000000 + " ms");
		in.close();
		out.close();
	}

	static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

Measured memory_bytes: 34540
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define ll long long 
#define FI first 
#define SE second
#define pb push_back 
#define eb emplace_back
#define mod 1000000007
#define all(c) (c).begin(),(c).end()
#define LB  lower_bound
#define UB  upper_bound
#define max3(a,b,c) max(c,max(a,b))
#define min3(a,b,c) min(c,min(a,b))
#define mems(s, n) memset(s, n, sizeof(s))
#define NINF -1e18
#define INF 1e18
#define int ll int
#define double long double
#define OOK order_of_key  //no of elements less than
#define FBO find_by_order //iterator pointing kth element;indexing starts from 0
#define CK3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define CK4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl

typedef pair<int,int> PII;
typedef pair<pair<int,int>,int> PPII;
typedef pair<int,pair<int,int>> PIPI;
typedef map<int,int>MII;
typedef vector<int> VI;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

/*int power(int a, int b)
{int x=1,y=a;while(b>0){if(b%2){x =(x*y)%mod;}y =(y*y)%mod;b/=2;}return x%mod;}
*/


signed main()
{
ios::sync_with_stdio(false); cin.tie(0);
int T=1,T1=0;//cin>>T;
while(T1++<T)
{//cout<<"Case #"<<T1<<": ";
    int x,y;
    cin>>x>>y;
    y-=2*x;
    if(y>=0&&y<=2*x&&y%2==0)
    cout<<"Yes"<<endl;
    else
    cout<<"No"<<endl;
    
}


return 0;
}





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

#define mp make_pair
#define pb push_back 
#define pf push_front 
#define pbp pop_back
#define pfp pop_front 
#define sz(x) x.size()
#define all(x) x.begin(),x.end() 
#define ios_base ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define open(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define F first
#define S second

using namespace std;

typedef unsigned long long ul;
typedef long long ll;
typedef long double ld;

const int mod = 1e9+7;
const int N = 1e5+123;
const int inf = 1e9+123;
const long long INF = 1e18;
const double eps = 1e-5;
         
string s;
int x, y;
int c1, c2, c3, c4;
int main () {        
	ios_base
	cin >> s;
	for(int i = 0; i < sz(s); i ++){
		if(s[i] == 'S') c1 = 1;
		if(s[i] == 'E') c2 = 1;
		if(s[i] == 'N') c3 = 1;
		if(s[i] == 'W') c4 = 1;
	}
	if(c1 ^ c3 == 1) cout << "No";
	else if(c2 ^ c4 == 1) cout << "No";
	else cout << "Yes";
	return 0; 
}
 


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

int main(){
  int a[13]={0,0,3,0,1,0,1,0,0,1,0,1,0};
  int x,y;
  cin >> x >>y;
  if(a[x]==a[y]){
    cout<<"Yes"<<endl;
    return 0;
  }
  cout<<"No"<<endl;
  return 0;
}

  

Measured memory_bytes: 256
/**
*	  Name: Ajay
*	  Institute: IIITH 
*/

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <deque>
#include <vector>
#include <cstdlib>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <ctime>
#include <string.h>
#define ll long long
#define inf 0x7fffffff
#define mod 1000000007
#define pb push_back
#define ppi pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int>>
#define vii vector<ppi>
#define vll vector<ll>
#define mp make_pair
#define fi first
#define se second
using namespace std;

void fastio()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
}
void input()
{
  #ifndef ONLINE_JUDGE
  freopen("input.txt","r",stdin);
  freopen("output.txt","w",stdout);
  #endif
}

int main()
{      
  fastio();
  //input();
  int n,m,i,j,t;
  cin>>n>>m>>t;
  int a[n+1];
  int g[n+1]={0};
  for(i=1;i<=n;i++)
  	a[i]=m;
  int q=t;
  while(t--)
  {
  	int x;
  	cin>>x;
  	g[x]++;
  }
  for(i=1;i<=n;i++)
  {
  	if(a[i]-q+g[i]>0)
  		cout<<"Yes"<<"\n";
  	else
  		cout<<"No"<<"\n";
  }
  return 0;
}

Measured memory_bytes: 1408
w, h, n = gets.split.map(&:to_i)
x1, y1, x2, y2 = 0, 0, w, h
n.times do
  x, y, a = gets.split.map(&:to_i)
  case a
  when 1
    x1 = [x1, x].max
  when 2
    x2 = [x2, x].min
  when 3
    y1 = [y1, y].max
  when 4
    y2 = [y2, y].min
  end
end
if x2 - x1 >= 0 && y2 - y1 >= 0
  puts (x1 - x2) * (y1 - y2)
else
  puts 0
end


Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define sl(x) scanf("%lld",&x)
#define pl(x) printf("%lld\n",x) 
using namespace std;
const int N = 1e6+5;
const int mod = 998244353;
const int INF = 0x3f3f3f3f;
typedef long long ll;
ll inv(ll b)
{
	if(b == 1)
	return 1;
	return (mod-mod/b)*inv(mod%b)%mod;
}
ll fac[N];
ll C(ll n,ll m)
{
	ll t = (fac[m]*fac[n-m])%mod;
	return (fac[n]*inv(t))%mod;
}
ll ans[N][2];
int main()
{
	ll n,i,a,b,k;
	fac[0] = 1;
	fac[1] = 1;
	for(i = 2;i <= 3e5+5;i++)
	fac[i] = (fac[i-1]*i)%mod;
	sl(n);sl(a);sl(b);sl(k);
	ll cnt = 0;
	for(i = 0;i <= n;i++)
	{
		if(k-(i*a) >= 0 && (k-a*i)%b == 0 && (k-a*i)/b <= n)
		{
			ans[cnt][0] = i;
			ans[cnt++][1] = (k-a*i)/b;
		}
	}
	ll res=0;
	for(i = 0;i < cnt;i++)
	{
		res = (res+C(n,ans[i][0])*C(n,ans[i][1])%mod)%mod;
	}
	pl(res);
}

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

// ----------- define --------------
#define int long long
#define vi vector<int>
#define vc vector<char>
#define ii pair<int,int>
#define fi first
#define sc second
#define stoi stoll
#define all(x) (x).begin(),(x).end()
#define get_bit(x, k) ((x >> k) & 1)
// ---------------------------------

void MAIN() {
  int n;
  cin >> n;
  int ans = 0;
  map<pair<int, int>, int> m;
  for (int i = 0; i < n; i++) {
    double _; cin >> _;
    int t = llround(_ * 1e9);
    int ct = 0, cf = 0;
    while (t % 2 == 0) {
      t /= 2;
      ct++;
    }
    while (t % 5 == 0) {
      t /= 5;
      cf++;
    }
    for (auto &j : m) {
      if (j.fi.fi + ct >= 18 && j.fi.sc + cf >= 18) {
        ans += j.sc;
      }
    }
    m[ii(ct, cf)]++;
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int T = 1;
  // cin >> T;
  while (T--) MAIN();
}


Measured memory_bytes: 3748
#include <bits/stdc++.h>
#define l_ength size
const int inf = (1<<30);
const int mod = 1000000007;
using ll = long long;
using namespace std;

string strmax( string a, string b ){
	if( a.l_ength() == b.l_ength() ) return ( a > b ) ? a : b;
	else return ( a.l_ength() > b.l_ength() ) ? a : b;
}

vector<string> dp(10100);
const int gs[10] = {0, 2, 5, 5, 4, 5, 6, 3, 7, 6};

int main(){
	int n, m; cin >> n >> m;
	vector<char> match(m);
	for( auto &k : match ) cin >> k;
	fill_n( dp.begin(), 10000, "" );
	for( int i = 0; i <= n; ++i ){
		for( char k : match ){
			if( !( i != 0 && dp[i] == "") ){
				dp[i+gs[k-'0']] = strmax( dp[i+gs[k-'0']], dp[i]+k );
			}
		}
	}
	cout << dp[n] << endl;
}

Measured memory_bytes: 43776
n,k=map(int,input().split())
h=list(map(int,input().split()))

dp=[float('inf')]*n
dp[0]=0
for i in  range(1,n):
    for j in range(1,k+1):
        if i-j>=0:
            dp[i]=min(dp[i],dp[i-j]+abs(h[i]-h[i-j]))
print(dp[-1])

Measured memory_bytes: 55392
#include <iostream>
#include <algorithm>
#include <climits>
#include <string>
#include <vector>
#include <cmath>
using namespace std;

int N, K;
int dp[1010][1010];

int main() {
  cin >> N >> K;
  for (int i=0; i<K; i++) dp[0][i] = 1;
  for (int i=0; i<N; i++) {
    for (int k=0; k<K; k++) {
      for (int x=0; x<K; x++) {
        if (x == k) continue;
        dp[i+1][x] += dp[i][k];
      }
    }
  }
  int ans = 0;
  for (int i=0; i<K; i++) ans += dp[N-1][i];
  cout << ans << "\n";
  return 0;
}



Measured memory_bytes: 4224
#include <iostream>
#include <algorithm>
#include <cmath>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <string.h>
#include <stack>
#define Endl endl
#define mp make_pair
#define rep(N) for(int i=0;i<N;i++)
#define repj(N) for(int j=0;j<N;j++)
#define ll long long 
#define pii pair<int,int>
#define pll pair<ll,ll>
#define For(I,N) for(int I=0;I<N;I++)
#define cinone(N) int N;cin>>N;
#define scanfone(N) int N;cin>>N;
#define cinng(N,M) int N[M];for(int yiuytvnm=0;yiuytvnm<M;yiuytvnm++) cin>>N[yiuytvnm];
#define scanfng(N,M) int N[M];for(int qrwuoiq=0;qrwuoiq<M;qrwuoiq++) scanf("%d",&N[qrwuoiq]);
#define over(A) {cout<<A<<endl;exit(0);}
#define all(A) A.begin(),A.end()
typedef unsigned long long ull;
const int inf=1039074182;
using namespace std;
int n,k;
int a[100005];
vector <int> l;
vector <int> r;

int main()
{
//	freopen("input.txt","r",stdin);
	cin>>n>>k;
	for(int i=0;i<n;i++)
	{
		scanf("%d",a+i);
	}
	int p=0;
	r.push_back(0);
	while(a[p]<0 && p<n)
	{
		l.push_back(-a[p]);
		p++;
	}
	if(p!=n && a[p]==0) k--,p++;
	while(p!=n)
	{
//		cout<<p<<endl;
		r.push_back(a[p]);
		p++;
	}
	l.push_back(0);
	reverse(l.begin(),l.end());
//	for(int i=0;i<l.size();i++)
//	{
//		cout<<l[i]<<' ';
//	}
//	cout<<endl;
//	for(int i=0;i<r.size();i++)
//	{
//		cout<<r[i]<<' ';
//	}
//	cout<<endl;
	int res=inf;
	for(int i=0;i<=k;i++)//choose from l
	{
		if(l.size()-1<i) break;
		if(k-i>r.size()-1) continue;
		res=min(res,l[i]*2+r[k-i]);
		res=min(res,l[i]+2*r[k-i]);
		if(i==0) res=min(res,r[k-i]);
		if(i==k) res=min(res,l[i]);
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 1404
#include <bits/stdc++.h>
#define rep3(i, s, n, a) for (int i = (s); i < (int)(n); i += a)
#define rep2(i, s, n) rep3(i, s, n, 1)
#define rep(i, n) rep2(i, 0, n)

using namespace std;
using ll = long long;
using ull = unsigned long long;
using P = pair<int, int>;

int main(){
    int n;
    cin >> n;
    vector<int> h, dp(n);
    rep(i, n){
        int x;
        cin >> x;
        h.push_back(x);
    }
    dp[0] = 0;
    dp[1] = abs(h[1] - h[0]);
    rep2(i, 2, n) { 
        dp[i] = min(dp[i-1] + abs(h[i] - h[i - 1]), dp[i-2] + abs(h[i] - h[i - 2])); 
    }
    cout << dp[n-1] << endl;
    return 0;
}

Measured memory_bytes: 4228
#include <iostream>
using namespace std;
int main(void){
    int a,b,i,j,k,cnt=0,n;
    cin >> a >> b;
    for(i=0;i<=a;i++){
        for(j=0;j<=a;j++){
            n=b-i-j;
            if(n<=a and 0<=n) cnt++;
        }
    }
    cout << cnt << endl;
    
}


Measured memory_bytes: 256
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <vector>

#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)

using namespace std;
typedef long long ll;

int main() {
  string w;
  cin >> w;
  int c[26] = {};
  REP(i,0,w.size()) {
    c[w[i]-'a']++;
  }
  bool y = true;
  REP(i,0,26) {
    if(c[i] % 2) {
      y = false;
      break;
    }
  }
  cout << (y ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
n, m, r = gets.chomp.split(" ").map{|s| s.to_i}

a, b = r-n*m, n-1

if a < 0 then
  puts 0
else
  if a < b then
    a, b = b, a
  end
  
  res = 1
  for i in a+1..n+r-n*m-1
    res *= i
  end
  
  for i in 1..b
    res /= i
  end
  
  puts res
end

Measured memory_bytes: 12120
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>

using namespace std;

#define EPS 1e-10

double add(double a,double b){
  if(abs(a+b) < EPS*(abs(a)+abs(b)))return 0;
  return a+b;
}

struct P{
  double x,y;
  P(){}
  P(double x,double y): x(x),y(y) {}

  P operator + (P p){
    return P(add(x,p.x),add(y,p.y));
  }
  P operator - (P p){
    return P(add(x,-p.x),add(y,-p.y));
  }

  P operator * (double d){
    return P(x*d,y*d);
  }

  double dot(P p){
    return add(x*p.x,y*p.y);
  }
  double det(P p){
    return add(x*p.y,-y*p.x);
  }
};
bool cmp_x(const P& p,const P& q){
  if(p.x != q.x )return p.x < q.x;
  return p.y < q.y;
}

vector<P> convex_hull(vector<P> ps , int N)
{
  sort(ps.begin(),ps.end(),cmp_x);
  /*for(int i = 0 ; i < N ; i++ ){
    cout << ps[i].x << ' ' << ps[i].y << endl;
    }*/
  vector<P> qs(N*2);
  int k = 0;
  for(int i = 0 ; i < (int)ps.size() ; i++ ){
    while(k > 1 && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0 )k--;
    qs[k++] = ps[i];
  }

  for(int i=N-2,t = k ; i >= 0 ; i-- ){
    while(k > t && (qs[k-1]-qs[k-2]).det(ps[i]-qs[k-1]) <= 0 )k--;
    qs[k++] = ps[i];
  }
  qs.resize(k-1);
  return qs;
}

int main(){
  int n;

  while(cin >> n,n){
    vector<P> ps(n);
    char c;
    for(int i = 0 ; i < n ; i++ ){
      cin >> ps[i].x >>c>> ps[i].y;
    }
    vector<P> qs = convex_hull(ps, n);
    cout << ps.size()-qs.size() << endl;
  }
  return 0;
}

Measured memory_bytes: 1244
#include <iostream>
#include <string>
#include <vector>

#define rep(i, n) for (int i = 0; i < (n); ++i)

using std::cin;
using std::cout;
using std::endl;
using std::string;
using std::vector;

int main()
{
  int X;
  cin >> X;

  if (X == 3 || X == 5 || X == 7)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}


Measured memory_bytes: 256
def main18():
    num = int(input(""));
    buf = input("");
    bufs = buf.split();
    hai = [];
    for i in range(len(bufs)):
        hai.append(int(bufs[i]));
    manhidari = int(num/2);
    manmigi = manhidari + 1;
    kari = hai[:];
    kari.sort();
    hidarin = kari[manhidari-1];
    migin = kari[manmigi-1];

    for i in range(len(hai)):
        if hai[i] >hidarin:
            print(hidarin);
        else:
            print(migin);

if __name__ == '__main__':
    main18()


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

using namespace std;

using ll = long long;
using ld = long double;

const int INF = (1 << 30) - 1;
const ll INF64 = ((ll)1 << 62) - 1;
const double PI = 3.1415926535897932384626433832795;

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

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

	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;

		if (s == "Y") {
			cout << "Four" << endl;
			return 0;
		}
	}

	cout << "Three" << endl;
	return 0;
}


Measured memory_bytes: 256