akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>

int main(void){
    int A,B,C,D;
    int train,bus;
    char buf[100];

    do{
        fgets(buf, sizeof(buf), stdin);			//入力
        sscanf(buf, "%d", &A);		//数字にできる時のみ変換
    }while(!(1<=A && A<=1000));
    do{
        fgets(buf, sizeof(buf), stdin);			//入力
        sscanf(buf, "%d", &B);		//数字にできる時のみ変換
    }while(!(1<=B && B<=1000));
    do{
        fgets(buf, sizeof(buf), stdin);			//入力
        sscanf(buf, "%d", &C);		//数字にできる時のみ変換
    }while(!(1<=C && C<=1000));
    do{
        fgets(buf, sizeof(buf), stdin);			//入力
        sscanf(buf, "%d", &D);		//数字にできる時のみ変換
    }while(!(1<=D && D<=1000));
    
    if(A<=B)
        train=A;
    else
        train=B;
    
    if(C<=D)
        bus=C;
    else
        bus=D;
    
    printf("%d\n",train+bus);
}


Measured memory_bytes: 128
#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 fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

vector<ll> vec;

ll ans[111111];
ll cnt[111111];
ll P[111111];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll N; int n;
	cin>>N>>n;
	vec.pb(N);
	for(int i=0;i<n;i++)
	{
		ll x; cin>>x;
		while(!vec.empty()&&vec.back()>=x)
		{
			vec.pop_back();
		}
		vec.pb(x);
	}
	n=vec.size();
	cnt[n-1] = 1;
	for(int i=n-1;i>=0;i--)
	{
		ll coeff=cnt[i];
		ll cur=vec[i];
		if(i==0)
		{
			for(int j=0;j<cur;j++) ans[j]+=coeff;
			break;
		}
		while(cur>=vec[0])
		{
			int lb=lower_bound(vec.begin(),vec.end(),cur)-vec.begin();
			lb--;
			if(lb<0) break;
			ll quo = cur/vec[lb]; ll rem = cur%vec[lb];
			cnt[lb]+=quo*coeff;
			cur=rem;
		}
		if(cur>0) P[cur-1]+=coeff;
	}
	for(int i=N-2;i>=0;i--)
	{
		P[i]+=P[i+1];
	}
	for(int i=0;i<N;i++) ans[i]+=P[i];
	for(int i=0;i<N;i++)
	{
		cout<<ans[i]<<'\n';
	}
}


Measured memory_bytes: 4980
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int descending_compare(const void *a, const void *b){
    if (*(long long*)a > *(long long*)b){
        return -1;
    }else if (*(long long*)a == *(long long*)b){
        return 0;
    }else{
        return 1;
    }
}

int ascending_compare(const void *a, const void *b){
    if (*(int*)a < *(int*)b){
        return -1;
    }else if (*(int*)a == *(int*)b){
        return 0;
    }else{
        return 1;
    }
}


int lower_bound(int *a, int n, int key){
    int left, mid, right;
    left = 0, right = n;
    mid = (left + right)/2;
    while ((left+1 != mid || mid+1 != right) && mid != left){
        if (key > a[mid]){
            left = mid;
        }else{
            right = mid+1;
        }
        mid = (left + right)/2;
    }
    if (a[left] >= key)return left;
    if (a[mid] >= key)return mid;
    if (a[right] >= key)return right;
    return n;
}

//greatest common divisor
unsigned long gcd(unsigned long x, unsigned long y){
    if (y == 0){ 
        return x;
    }else if (x > y){
        return gcd(y, x % y);
    }else{
        return gcd(x, y % x);
    }
}

unsigned long lcm(unsigned long x, unsigned long y){
    unsigned long g = gcd(x, y);
    return x*y/g;

}



long long factorial(int x){
    long long rtn = 1;
    int i;
    for (i = x; i > 1; i--){
        rtn = (rtn*i);
    }
    return rtn;
}

/*
int struct_ascending_compare(const void *p, const void *q) {
return ((struct_name*)p)->member_name - ((struct_name*)q)->member_name;
}*/

/*unsigned long long pascal[100][100] = {0};
void make_pascal(void){
    for (int i = 0; i < 100; i++){
        pascal[i][0] = 1;
    }
    pascal[1][1] = 1;
    for (int i = 2; i < 100; i++){
        for (int j = 1; j < 100; j++){
           pascal[i][j] = (pascal[i-1][j-1]+pascal[i-1][j]);
        }
    }
}*/
long long mod = 1000000007;

long long mod_pow(long long x, long long n){
    long long res = 1;
    for(int i = 0;i < 60; i++){
        if(n >> i & 1) res = res * x % mod;
        x = x * x % mod;
    }
    return res;
}

long long a[105];

int main(void){
    int n;
    int bob = 0; 
    int alice = 0;
    scanf("%d", &n);
    for (int i = 0; i < n; i++){
        scanf("%lld", &a[i]);
    }
    qsort(a, n, sizeof(long long), descending_compare);
    for (int i = 0; i < n; i++){
        if (i % 2){
            bob += a[i];
        }else{
            alice += a[i];
        }
    }

    printf("%d\n", alice - bob);
    return 0;
}

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

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

typedef long long ll;

int main() {
    int v,e;cin>>v>>e;
    
    ll INF =10000000000007;
    
    ll a[v][v];
    rep(i,v){
        rep(j,v){
            if(i==j)a[i][j]=0;
            else a[i][j] = INF;
        }
    }
    
    rep(i,e){
        ll s,t,d;
        cin>>s>>t>>d;
        a[s][t]=d;
    }
    
    rep(k,v){
        rep(i,v){
            rep(j,v){
              if(a[k][j]!=INF && a[i][k]!=INF){
                a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
                }}
            }
        }
    
    rep(i,v){
        if(a[i][i]<0){
            cout<<"NEGATIVE CYCLE"<<endl;
            return 0;
        }
    }
    
    rep(i,v){
        rep(j,v){
            if(a[i][j]==INF)cout<<"INF";
            else cout<<a[i][j];
            
            if(j == v-1)cout<<endl;
            else cout<<" ";
        }
    }
    
 	return 0;
}


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

int main()
{
  int n;
  cin >> n;
  
  vector<int> c(n);
  for (int i = 0; i < n; i ++)
    cin >> c.at(i);
  
  sort(c.begin(), c.end(), greater<>{});
  
  int height = 0;
  int base_dia = 101;
  for (int i = 0; i < n; i ++)
  {
    if (c.at(i) < base_dia)
    {
      height ++;
      base_dia = c.at(i);
    }
  }
  
  cout << height;
  
  return 0;
}


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

int main(){
    int N;
    cin >> N;
    int A;
    vector<int> sya(N);
    
    for(int i = 0 ; i < N-1 ; ++i){
        cin >> A;
        sya.at(A-1) += 1;
    }
    
    for(int i = 0 ; i < N ; ++i){
        cout << sya.at(i) << endl;
    }
    
    return 0;
}

Measured memory_bytes: 4048
l = 'abcdefghijklmnopqrstuvwxyz'
mp = [0 for _ in list(l)]

while True:
    try:
        in_data = list(filter(lambda x: 97 <= ord(x) <= 122 , raw_input().lower()))
    except:
        break

    for s in in_data:
        mp[ord(s) - 97] += 1

for i,j in zip(l, mp):
    print "%s : %s" % (i, j)

Measured memory_bytes: 6428
#[allow(unused_imports)]
use std::io;
use std::io::stdin;
// use std::cmp;

fn read_line_as_vec() -> Vec<String> {
    let mut s = String::new();
    stdin().read_line(&mut s).expect("");
    s.split(' ').map(|x| x.to_string()).collect::<Vec<String>>()
}

fn main() {
    let ab = read_line_as_vec();
    let a = ab[0].trim();
    let b = ab[1].trim();
    let t = if a == b { "H" } else { "D" };
    println!("{}", t);
}


Measured memory_bytes: 4352
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int n,m;
struct node{
	int t,val;
}a[maxn];
bool cmp(node a,node b){
	return a.t<b.t;
}
priority_queue<int>q;
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++)scanf("%d %d",&a[i].t,&a[i].val);
	sort(a+1,a+n+1,cmp);
	int k=1;
	int ans=0;
	for(int i=1;i<=m;i++){//这里枚举的是剩余的天数 
		while(k<=n&&a[k].t<=i){
			q.push(a[k].val);
			k++;
		}
		if(!q.empty()){//每天只能取一个 
			ans+=q.top();
			q.pop();
		}
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 1660
use std::cmp::*;
use std::io::*;

fn dfs(v: usize, p: usize, g: &Vec<Vec<usize>>) -> usize {
    let mut ds = Vec::new();
    for &nv in g[v].iter() {
        if nv != p {
            ds.push(dfs(nv, v, &g));
        }
    }

    ds.sort();
    ds.reverse();
    let mut res = 0;
    for i in 0..ds.len() {
        res = max(res, ds[i] + i + 1);
    }
    res
}

fn main() {
    let mut s: String = String::new();
    stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let mut g = vec![Vec::new(); n];
    for i in 1..n {
        let a = itr.next().unwrap().parse::<usize>().unwrap() - 1;
        g[i].push(a);
        g[a].push(i);
    }

    println!("{}", dfs(0, 0, &g));
}


Measured memory_bytes: 34428
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;

int main(){
  int N;
  long int sum = 0;
  cin >> N;
  vector<long int> A;
  for(int i=0;i<N;i++){
    long int x;
    cin >> x;
    sum+=x;
    A.push_back(x);
  }

  long int LeftSum = 0;
  long int RightSum = sum;
  long int min = sum;
  for(int i=0;i<A.size();i++){
    if(min > abs((LeftSum+A[i]) - (RightSum-A[i]))){
      LeftSum += A[i];
      RightSum -= A[i];
      min = abs(LeftSum - RightSum);
    }
    else{
      break;
    }
  }

  cout << min << endl;
  
  return 0;
}


Measured memory_bytes: 2420
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
    return (ull)rng() % B;
}

int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n,m; cin >> n >> m;
	vector<int> a(n+2);
	while(m--){
		int x,y; cin >> x >> y;
		a[x]++;
		a[y]--;
	}
	for(int i=1;i<=n;i++){
		a[i]+=a[i-1];
	}
	int res=n+1;
	for(int i=1;i<=n;i++){
		if(a[i]>=1)res+=2;
	}
	printf("%d\n",res);
}


Measured memory_bytes: 3252
use std::io::*;
use std::str::*;

fn read<T: FromStr>() -> Option<T> {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let n: usize = read().unwrap();
    let k: usize = read().unwrap();

    if n < 10 {
        let score = k + 100 * (10 - n);
        println!("{}", score);
    } else {
        println!("{}", k);
    }
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long



#if 0
const int MOD = ;

inline int lgput(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans = (1LL * ans * a) % MOD;
        b >>= 1;
        a = (1LL * a * a) % MOD;
    }
    return ans;
}

inline void mod(int &x) {
    if(x >= MOD)
        x -= MOD;
}

inline void add(int &x, int y) {
    x += y;
    mod(x);
}

inline void sub(int &x, int y) {
    x += MOD - y;
    mod(x);
}

inline void mul(int &x, int y) {
    x = (1LL * x * y) % MOD;
}

inline int inv(int x) {
    return lgput(x, MOD - 2);
}
#endif

#if 0
int fact[], invfact[];

inline void prec(int n) {
    fact[0] = 1;
    for(int i = 1; i <= n; i++) {
        fact[i] = (1LL * fact[i - 1] * i) % MOD;
    }
    invfact[n] = lgput(fact[n], MOD - 2);
    for(int i = n - 1; i >= 0; i--) {
        invfact[i] = (1LL * invfact[i + 1] * (i + 1)) % MOD;
    }
}

inline int comb(int n, int k) {
    if(n < k) return 0;
    return (1LL * fact[n] * (1LL * invfact[k] * invfact[n - k] % MOD)) % MOD;
}
#endif

using namespace std;



int main() {
#if 0
    ifstream cin("A.in");
    ofstream cout("A.out");
#endif
    int i, m, d;
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> m >> d;
    int ans = 0;
    for(i = 10; i <= d; i++) {
        if(i / 10 >= 2 && i % 10 >= 2) {
            if((i / 10) * (i % 10) <= m) {
                ans++;
            }
        }
    }
    cout << ans;

    return 0;
}




Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<stack>
using namespace std;
typedef long long ll;
#define N 1000015
const int p=1e9+7;
int n,dp[N],s[N];
int main()
{
	scanf("%d",&n);
	dp[n]=n;s[n]=n;
	dp[n-1]=1ll*n*n%p;s[n-1]=(s[n]+dp[n-1])%p;
	for(int i=n-2;i>0;i--)
	{
		dp[i]=(dp[i]+dp[i+1])%p;
		dp[i]=(dp[i]+1ll*(n-1)*(n-1)%p)%p;
		dp[i]=(dp[i]+s[i+3])%p;
		dp[i]=(dp[i]+i+1)%p;
		s[i]=(s[i+1]+dp[i])%p;
	}
	printf("%d\n",dp[1]);
}


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

int main() {
  string s;
  cin >> s;
  for (int i = 0; i < s.size(); i++) {
    if (i == 5 || i == 13) {
      cout << " ";
    }
    else {
      cout << s[i];
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>

using namespace std;

int main(){
  int n,m;
  int p[100001], y[100001];

  cin >> n >> m;
  for(int i = 0; i < m; i++) cin >> p[i] >> y[i];

  vector<vector<int>> pre(100001);
  for(int i = 0; i < m; i++) pre[p[i]-1].push_back(y[i]);

  for(int i = 0; i < n; i++){
    sort(pre[i].begin(), pre[i].end());
  }

  // for(int i = 0; i < m; i++){
  //   for(auto a : pre[i]) cout << a << ',';
  //   cout << endl;
  // }

  for(int i = 0; i < m; i++){
    int v = p[i] - 1;
    // for(auto a : pre[i]) cout << a << endl;
    printf("%06d", v+1);

    int id = lower_bound(pre[v].begin(), pre[v].end(), y[i]) - pre[v].begin();
    printf("%06d\r\n", id+1);
  }



  return 0;
}

Measured memory_bytes: 7808
#include<stdio.h>
#define rep(i,N) for(int i=0;i<(int)N;i++)
int main(void)
{
  int N,M,A,B,count,H[100001]={0},low[100001]={0};
  count=scanf("%d %d",&N,&M);
  rep(i,N)count=scanf("%d",&H[i]);
  rep(i,M)
  {
    count=scanf("%d %d",&A,&B);A--,B--;
    if(H[A]<H[B])low[A]=1;
    else if(H[A]>H[B])low[B]=1;
    else low[A]=low[B]=1;
  }
  count=0;
  rep(i,N)count+=!low[i];
  return printf("%d\n",count),0;
}

Measured memory_bytes: 2464
fh = gets.to_i
oh = gets.to_i
ft = gets.to_i
total = gets.to_i

count = 0
while fh >= 0
#  puts "#{fh} 0 0"
  sub_total = 500*fh
  
  if sub_total > total
    fh -= 1
    next
  end
  if sub_total == total
    count += 1
    fh -= 1
    next
  end
  
  oh_tmp = oh
  while oh_tmp >= 0
    #puts "#{fh} #{oh_tmp} 0"
    sub_total = 500*fh + 100*oh_tmp

    if sub_total > total
      oh_tmp -= 1
      next
    elsif sub_total == total
      oh_tmp -= 1
      count += 1
      next
    end
    
    ft_tmp = ft
    while ft_tmp > 0
      #puts "#{fh} #{oh_tmp} #{ft_tmp}"
      sub_total = 500*fh + 100*oh_tmp + 50*ft_tmp
      ft_tmp -= 1
      if sub_total == total
        count += 1
      elsif sub_total < total
        break
      end
    end
    oh_tmp -= 1

  end

  fh -= 1
end

puts count

Measured memory_bytes: 1788
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int h,w,n;
	cin >> h >> w >> n;
	
	set<pii> st,table;
	for(int i=1;i<=n;i++) {
		int x,y;
		cin >> x >> y;
		for(int i=-2;i<=0;i++)
			for(int j=-2;j<=0;j++) {
				int nx = x + i , ny = y + j;
				if(nx >= 1 && ny >= 1 && nx+2 <= h && ny+2 <= w)
					st.insert(make_pair(nx,ny));
			}
		table.insert(make_pair(x,y));
	}
	
	ll ans[10] = {};
	for(pii p : st) {
		int cnt = 0;
		for(int i=0;i<=2;i++)
			for(int j=0;j<=2;j++)
				if(table.count(make_pair(p.first+i,p.second+j))==1)
					cnt++;
		ans[cnt]++;
	}
	ans[0] += (ll)(h-2)*(w-2) - (ll)st.size();
	for(int i=0;i<=9;i++)
		cout << ans[i] << endl;
	return 0;
}


Measured memory_bytes: 47104
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mx=1000000000ll;
LL S;
int main(){
	int i,j,k;
	scanf("%lld",&S);
	LL x1=mx,y2=(S+mx-1ll)/mx,x2=1ll,y1;
	y1=x1*y2-S;
	printf("%lld %lld %lld %lld %lld %lld\n",0ll,0ll,x1,y1,x2,y2);
	return 0;
}

Measured memory_bytes: 256
#from math import sqrt
#from heapq import heappush, heappop
#from collections import deque
#from functools import reduce

#a, b = [int(v) for v in input().split()]


def main():
    a1, a2, a3 = map(int, input().split())

    if a1 + a2 + a3 >= 22:
        print("bust")
    else:
        print("win")


main()


Measured memory_bytes: 2940
#include <stdio.h>
#include <string.h>
 
#define MAX 1000
 
char X[MAX], Y[MAX];
 
int LCS() {
    int i, j;
    int m = strlen(X);
    int n = strlen(Y);
    int c[m + 1][n + 1];
 
    for (i = 1; i <= m; i++) c[i][0] = 0;
    for (j = 0; j <= n; j++) c[0][j] = 0;
 
    for (i = 1; i <= m; i++) {
        for (j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1]) {
                c[i][j] = c[i - 1][j - 1] + 1;
            } else if (c[i - 1][j] >= c[i][j - 1]) {
                c[i][j] = c[i - 1][j];
            } else {
                c[i][j] = c[i][j - 1];
            }
        }
    }
 
    return c[m][n];
}
 
main() {
    int n, i;
 
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%s%s", X, Y);
        printf("%d\n", LCS());
    }
 
    return 0;
}



Measured memory_bytes: 5636
// taskkill -im A.exe -f
#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;

typedef tree<int, null_type, less<int>, rb_tree_tag,
        tree_order_statistics_node_update>
        PBDS;

#define int long long
#define endl "\n"
#define MOD 10
#define pb push_back
const int mxN = 1e6 + 500;
int ar[mxN];


int32_t main() {

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

#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif

	int T;
	// cin >> T;
	T = 1;

	while (T--) {

		int n, x, t, c = 0, ans = 0, l = 0;

		cin >> n >> x >> t;

		cout << ((n + x - 1) / x * t);

		cout << endl;
	}

	return 0;
}



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

#define reint register int
#define coint const int

using namespace std;

typedef long long ll;

coint SIZE = 100000 + 5;
coint MOD  = 1e9 + 7;

inline ll fastPow(register ll base, register ll xpow) {
    register ll res = 1;
    for (; xpow; base = base * base % MOD, xpow >>= 1)
        if (xpow & 1) res = res * base % MOD;
    return res;
}

inline int getint(void) {
    int x;
    scanf("%d", &x);
    return x;
}

struct Edge { int v, head; };

int  ecnt, head[SIZE];
Edge edge[SIZE << 1];

inline void addEdge(coint u, coint v) {
    edge[++ecnt] = (Edge){v, head[u]}, head[u] = ecnt;
    return;
}

ll fac[SIZE], inv[SIZE], facinv[SIZE], ans[SIZE];

inline ll A(coint n, coint m) {
    if (m > n) return 0;
    return fac[n] * facinv[n - m] % MOD;
}

int n, k;

void dfs(coint u, coint fa) {
    for (int i = head[u]; ~i; i = edge[i].head) {
        coint v = edge[i].v;
        if (v == fa) continue;
        dfs(v, u);
    }
    int cnt = 0;
    ll res = 1;
    for (int i = head[u]; ~i; i = edge[i].head) {
        coint v = edge[i].v;
        if (v == fa) continue;
        ++cnt, res = res * ans[v] % MOD;
    }
    //printf("%d, %d\n", k - 1 - (u != 1), cnt);
    res = res * A(k - 1 - (u != 1), cnt) % MOD;
    ans[u] = res;
    //printf("dfs(%d, %d), res = %lld\n", u, fa, res);
    return;
}

int main(void) {
    fac[0] = 1, facinv[0] = 1;
    for (reint i = 1; i < SIZE; ++i) inv[i] = fastPow(i, MOD - 2);
    for (reint i = 1; i < SIZE; ++i)
        fac[i] = fac[i - 1] * i % MOD, facinv[i] = facinv[i - 1] * inv[i] % MOD;
    ecnt = 0, memset(head, -1, sizeof head);

    n = getint(), k = getint();
    if (k == 1) { printf("%d\n", n == 1 ? 1 : 0); return 0; }
    for (reint i = 1; i < n; ++i) {
        coint u = getint(), v = getint();
        addEdge(u, v), addEdge(v, u);
    }
    dfs(1, 0);
    printf("%lld\n", ans[1] * k % MOD);
    return 0;
}



Measured memory_bytes: 8832
#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10000000)

MOD = 1000000007  # type: int


def solve(N: int):
    ans = 1
    for i in range(1, N+1):
        ans = (ans * i) % MOD

    print(ans)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    solve(N)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
#include <cstdio>

int N;
long long nr, ng, nb;
char S[4005];

int main() {
    scanf("%d", &N);
    while (getchar() != '\n')
        ;
    for (int i=0; i<N; ++i) {
        S[i] = (char)getchar();
        if (S[i] == 'R') ++nr;
        else if (S[i] == 'G') ++ng;
        else ++nb;
    }
    long long n = nr*ng*nb;
    for (int i=0; i<N; ++i) {
        for (int j=1; j<N; ++j) {
            int i2 = i+j, i3 = i+j*2;
            if (i3 >= N)
                break;
            if (S[i] != S[i2] && S[i2] != S[i3] && S[i] != S[i3])
                --n;
        }
    }
    printf("%lld", n);
}

Measured memory_bytes: 1736
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <iomanip>
#include <climits>
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<string> VS;
typedef vector< vector<int> > VVI;
typedef vector< vector<ll> > VVL;
typedef pair<int,int> PII;
typedef pair<ll,ll> PLL;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define all(a) (a).begin(),(a).end()
#define pf push_front
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define ub upper_bound
#define lb lower_bound

int main(){
  int N,M;
  cin>>N>>M;
  string S;
  cin>>S;
  VI X(N+1,-1);
  reverse(all(S));
  int tmp=1;
  rep(i,N+1){
    if(i==0) continue;
    int Y=-1;
    rep(j,M){
      if(i+j<=N and S[i+j]=='0'){
        X[i+j]=tmp;
        Y=i+j;
      }
    }
    i=Y;
    tmp++;
    if(Y==-1) break;
  }
  if(X[N]==-1){
    cout<<-1<<endl;
    return 0;
  }
  VI P(X[N]+1);
  rep(i,N+1) if(X[i]!=-1) P[X[i]]=i;
  rep(i,X[N]) cout<<P[X[N]-i]-P[X[N]-1-i]<<" ";
  cout<<endl;
}

Measured memory_bytes: 1408
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner scan = new Scanner(System.in);

		int X = scan.nextInt();
		int Y = scan.nextInt();

		if (Y%2 == 0 && 2*X <= Y && Y <= 4*X) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}

}

Measured memory_bytes: 35848
import std.stdio;
import std.conv;
import std.string;
import std.typecons;
import std.algorithm;
import std.array;
import std.range;
import std.math;
import std.container;
import std.datetime;

void main()
{
	int n;
	while (n = readln.chomp.to!int, n) {
		auto score = new int[](n);
		foreach (i; 0..n) {
			score[i] = readln.chomp.to!int;
		}
		auto x = score.reduce!("a+b", max, min);
		writeln((x[0]-x[1]-x[2])/(n-2));
	}
}

Measured memory_bytes: 1180
A, B, C, K = map(int, input().split())

total = 0

if K <= A:
    print(K)
    exit()
else:
    total += A
    K -= A

if K <= B:
    print(A)
    exit()
else:
    K -= B

if K <= C:
    total -= K
else:
    total -= C

print(total)


Measured memory_bytes: 61752
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define ld long double
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define _h cout<<"here"<<endl;
#define fill(a,v) memset(a,v,sizeof(a));
#define all(v) v.begin(),v.end()
#define rep(i,n) for(int i=0;i<n;i+=1)
#define prd(a,n) rep(i,n) cout<<a[i]<<" \n"[i==n-1];// printf("%s\n"," " );
#define ff first
#define ss second
#define pu push_back
const int inf = 1e9+10;
const ll INF = 2e18+10;
const int Mod = 1e9+7;
const int MAXN = 1000010;
const int N=2e5+10;
const int M=210;
const int M1=1e9+7;
const int M2=1e9+9;
const int base=131;
int main()
{
  ios::sync_with_stdio(0), cin.tie(0); cout.tie(0);
  // freopen("input.txt","r",stdin);
  // freopen("output.txt","w",stdout);
  int n;
  string s;
  cin>>n>>s;
  int cnt=0,ans=0;
  for(int i=0;i<n;i++)
  {
    if(s[i]=='R') cnt++;
  }
  for(int i=0;i<cnt;i++)
  {
    if(s[i]=='W') ans++;
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 3712
T = gets.to_i

def f(a, b, c, d)
  return false if a < b
  return false if d < b
  return true if c >= b

  g = b.gcd(d)
  b - g + a % g <= c
end 

T.times do
  a, b, c, d = gets.split.map(&:to_i)

  if f(a, b, c, d)
    puts 'Yes'
  else
    puts 'No'
  end
end


Measured memory_bytes: 1788
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
using namespace std;
#ifndef FAST_IO
 #define IOS ios_base::sync_with_stdio(false);cin.tie(nullptr);
#endif

#define FILE_IO freopen("input.txt","r",stdin)
#define int long long
#define f first
#define s second
#define endl '\n'
#define all(c) c.begin(),c.end()
#define bp __builtin_popcount
#define debug(x) cerr << #x << " = " << x << endl;

const int MOD = 1e9 + 7;
const int INF = 1e18;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>void print(T t){for(auto &it : t)cout<<it<<" ";}
inline int powerexp(int a, int b, int m = MOD){ int res = 1;while(b){if(b&1)res = res * a % m;a = a * a % m,b >>= 1;}return res % m;}
inline int modinv(int a){ return powerexp(a,MOD-2,MOD);}
inline int lcm(int a, int b){ int g = __gcd(a,b);return a/g*b;}
inline int add(int x, int y){ x += y; if (x >= MOD) x -=  MOD; return x;}
inline int mul(int x, int y){ return (x * 1ll * y) % MOD;}
inline int sub(int x, int y){ x -= y; if (x<0) x += MOD; return x ;}

//-------------------< start here >-------------------------// 
bool cmp(int a, int b){
  return a < b;
}
void solve(){
   int n, q;
   cin >> n;
   vector<int> v;
   for(int i = 0; i < n; i++){
	   int x;
	   cin >> x;
	   v.push_back(x);  
	 }
   cin >> q;
   for(int  i = 0; i < q; i++){
	  int cmd;
	  cin >> cmd;
	  if (cmd == 0){
		  int start , end;
		  cin >> start >> end;
		  auto ret = *min_element(v.begin() + start, v.begin() + end);  
		  cout << ret << endl;
		}
	  if (cmd == 1){
	    int start , end;
		  cin >> start >> end;
		  auto ret = *max_element(v.begin() + start, v.begin() + end);  
		  cout << ret << endl;	  
	  }   
	}
}

//-----------------------------
//comment from here for TOPCODER 
int32_t main(){
   IOS;
   solve();
   //find();
   #ifdef LOCAL_DEFINE
   cerr << "time elapsed " << (double)clock()/CLOCKS_PER_SEC << endl;
   #endif
}



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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

template<class T>bool chmax(T & a, const T & b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }

lli dp[100100];
bool vis[100100];

lli func(long long N){

    if(N<0)return INF;
    if(N==0)return 0;
    if(vis[N])return dp[N];
    vis[N]=true;

    lli rtn = INF;

    for(lli i=9;i<=N;i*=9){
        chmin(rtn,func(N-i)+1);
    }
    for(lli i=6;i<=N;i*=6){
        chmin(rtn,func(N-i)+1);
    }

    chmin(rtn,func(N-1)+1);

    return dp[N] = rtn;
}

int main(){
    // cout << fixed << setprecision(5);

    long long N;
    scanf("%lld",&N);
    cout<<func(N)<<endl;
    return 0;
}


Measured memory_bytes: 1408
use proconio::input;

const MOD: u64 = 1_000_000_007;

fn main() {
    input!(n: usize);

    // dp[i][j]: 長さ i, |{0,9} ∩ {A_i}| = j
    let mut dp = vec![[0; 3]; n + 1];
    dp[0][0] = 1;
    for i in 0..n {
        for j in 0..3 {
            // j を変えない: 1...8 + すでに使った j 個
            dp[i + 1][j] += dp[i][j] * (8 + j as u64);
            dp[i + 1][j] %= MOD;
        }
        for j in 0..2 {
            // j を増やす: 0, 9 - すでに使った j 個
            dp[i + 1][j + 1] += dp[i][j] * (2 - j as u64);
            dp[i + 1][j + 1] %= MOD;
        }
    }
    let ans = dp[n][2];

    println!("{}", ans);
}


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

int main()
{
    int a,b,c,d,e;
    int minnum= 10;
    int max,ans;
    int count = 0;
    cin >> a >> b >> c >> d >> e;
    if(a % 10 != 0)minnum = min(a % 10, minnum);
    if(b % 10 != 0)minnum = min(b % 10, minnum);
    if(c % 10 != 0)minnum = min(c % 10, minnum);
    if(d % 10 != 0)minnum = min(d % 10, minnum);
    if(e % 10 != 0)minnum = min(e % 10, minnum);
    
    if(a % 10 == 0){
        count++;
    }
    if(b % 10 == 0){
        count++;
    }
    if(c % 10 == 0){
        count++;
    }
    if(d % 10 == 0){
        count++;
    }
    if(e % 10 == 0){
        count++;
    }
   
    max = ceil(a / 10)*10 + ceil(b/10)* 10 + ceil(c/10)*10 + ceil(d/10)*10 + ceil(e/10)*10;
    ans = max - (10 - minnum);
    cout << ans + (10 *(5 - count)) << endl;
}



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

int main()
{
    int n;
    cin >> n;
    vector<ll> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
        if (a[i] == 0)
        {
            cout << 0 << endl;
            return 0;
        }
    }

    ll ans = a[0];
    for (int j = 1; j < n; j++)
    {
        ans *= a[j];
        if (ans < 0)
        {
            cout << "-1" << endl;
            return 0;
        }
    }
    if (0 < ans && ans <= 1000000000000000000)
    {
        cout << ans << endl;
    }
    else
        cout << "-1" << endl;
    // cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3960
/*痛みを受け取れ，痛みを知れ*/
#include<bits/stdc++.h>
#define f(i,a,b) for(register int i=a;i<=b;++i)
#define ff(i,a,b) for(register int i=a;i>=b;--i)
#define debug(x) cerr << #x << " : " << x << " " << endl
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<string, string> pss;
const ll mod = 1000007;
const int inf = 0x3f3f3f3f;
const double tiaohe = 0.57721566490153286060651209;
ll oula(ll x) { ll res = x;f(i, 2, x / i) { if (x % i == 0) { res = res / i * (i - 1);while (x % i == 0) x /= i; } }if (x > 1) res = res / x * (x - 1);return res; }
ll quickmod(ll a, ll n, ll m) { ll s = 1;while (n) { if (n & 1) { s = s * a % m; }a = (a*a) % m;n = n / 2; }return s; }
ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
void ex_gcd(ll a, ll b, ll &x, ll &y, ll &d) { if (!b) { d = a, x = 1, y = 0; } else { ex_gcd(b, a % b, y, x, d);y -= x * (a / b); } }
ll inv(ll t, ll p) { ll d, x, y;ex_gcd(t, p, x, y, d);return d == 1 ? (x % p + p) % p : -1; }
bool isPrime(ll x) { if (x == 2)return true;if (x % 2 == 0)return false;for (ll i = 2;i*i <= x;i++) if (x % i == 0)return false; return true; }
//double a = log(n) +tiaohe + 1.0 / (2 * n);
double eqa = (1 + sqrt(5.0)) / 2.0;
const int N = 6e5 + 5;
pii a[N];
int main()
{
	//freopen("in.txt", "r", stdin);
	ll n;
	while (cin >> n)
	{
		string s;
		cin >> s;
		vector<int> v1, v2;
		f(i, 0, (int)s.size() - 1)
		{
			if (s[i] == 'W')v1.emplace_back(i);
			else v2.emplace_back(i);
		}
		sort(v2.begin(), v2.end(), greater<int>());
		int ans = 0;
		f(i, 0, min((int)v2.size()-1,(int)v1.size()-1))
		{
			if (v2[i] > v1[i])ans++;
			else break;
		}
		cout << ans << endl;
	}
	return 0;
}


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

using namespace std;

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

    int ans = 0;
    for (int i = 0; i < S.size(); i++) {
        int num = 0;
        for (int j = i; i < S.size(); j++) {
            if (S[j] == 'A' or S[j] == 'C' or S[j] == 'G' or S[j] == 'T') {
                num++;
            } else break;
        }
        if (num > ans) ans = num;
    }

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

Measured memory_bytes: 256
import java.util.*;
public class Main{
  public static void main(String[] args){
    Scanner sc =new Scanner(System.in);
    int N =sc.nextInt();
    int V[] =new int[N];
    int C[] =new int[N];
    int x=0;
    for(int i=0;i<2*N;i++){
      if(i<N){V[i]=sc.nextInt();}
      else{C[i-N]=V[i-N]-sc.nextInt();
           if(C[i-N]>0){x=x+C[i-N];}}}
    System.out.println(x);
  }
}

Measured memory_bytes: 21844
n,m = list(map(int, input().split()))
h = list(map(int, input().split()))
hoge = [[] for _ in range(n)]
for i in range(m):
  a,b = list(map(int, input().split()))
  hoge[a - 1].append(b - 1)
  hoge[b - 1].append(a - 1)
  
cnt = 0
for i in range(n):
  if hoge[i]:
    flag = True
    for j in hoge[i]:
      if h[i] <= h[j]:
        flag = False
    if flag:
      cnt += 1
  else:
    cnt += 1
        
print(cnt)

Measured memory_bytes: 29260
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout<< (x) << " "

int main(){
    int h,w;cin>>h>>w;
    string s[h];
    string tmp;
    int hflag[h]={0},wflag[w]={0};
    rep(i,h){
        cin>>s[i];
        bool is_sharp=false;
        rep(j,w){
            if(s[i][j]=='#'){wflag[j]++;is_sharp=true;}
        }
        if(is_sharp)hflag[i]++;
    }
    rep(i,h){
        if(hflag[i]==0){continue;}
        rep(j,w){
            if(wflag[j]>0)printf("%c",s[i][j]);
        }
        printf("\n");
    }
}

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

typedef double DD;
const DD EPS = 1e-10;

struct Point3D {
    DD x, y, z;
    Point3D(DD x = 0.0, DD y = 0.0, DD z = 0.0) : x(x), y(y), z(z) {}
    friend ostream& operator << (ostream &s, const Point3D &p) {return s << '(' << p.x << ", " << p.y << ", " << p.z << ')';}
};

Point3D operator + (const Point3D &p, const Point3D &q) {return Point3D(p.x + q.x, p.y + q.y, p.z + q.z);}
Point3D operator - (const Point3D &p, const Point3D &q) {return Point3D(p.x - q.x, p.y - q.y, p.z - q.z);}
Point3D operator * (const Point3D &p, DD a) {return Point3D(p.x * a, p.y * a, p.z * a);}
Point3D operator * (DD a, const Point3D &p) {return Point3D(a * p.x, a * p.y, a * p.z);}
Point3D operator / (const Point3D &p, DD a) {return Point3D(p.x / a, p.y / a), p.z / a;}
Point3D cross (const Point3D &p, const Point3D &q) {
    return Point3D(p.y * q.z - p.z * q.y, p.z * q.x - p.x * q.z, p.x * q.y - p.y * q.x);
}
DD dot(const Point3D &p, const Point3D &q) {return p.x * q.x + p.y * q.y + p.z * q.z;}
DD abs(const Point3D &p) {return sqrt(dot(p, p));}
DD area(const Point3D &a, const Point3D &b, const Point3D &c) { return abs(cross(b - a, c - a)) / 2; }

struct Line3D : vector<Point3D> {
    Line3D(const Point3D &a = Point3D(), const Point3D &b = Point3D()) {
	this->push_back(a);
	this->push_back(b);
    }
    friend ostream& operator << (ostream &s, const Line3D &l) {return s << '{' << l[0] << ", " << l[1] << '}';}
};

struct Plane : vector<Point3D> {
    Plane(const Point3D &a = Point3D(), const Point3D &b = Point3D(), const Point3D &c = Point3D()) {
        this->push_back(a);
        this->push_back(b);
        this->push_back(c);
    }
    friend ostream& operator << (ostream &s, const Plane &p) {
        return s << '{' << p[0] << ", " << p[1] << ", " << p[2] << '}';
    }
};

vector<Point3D> crosspointSPL(const Line3D &s, const Plane &pl) {
    vector<Point3D> res;
    Point3D ph = cross(pl[1] - pl[0], pl[2] - pl[0]);
    DD baseLength = dot(s[1] - s[0], ph);
    if (abs(baseLength) < EPS) return vector<Point3D>();
    DD crossLength = dot(pl[0] - s[0], ph);
    DD ratio = crossLength / baseLength;
    if (ratio < -EPS || ratio > 1.0 + EPS) return vector<Point3D>();
    res.push_back(s[0] + (s[1] - s[0]) * ratio);
    return res;
}

Point3D my, en, bar[3];
int main() {
    while (cin >> my.x >> my.y >> my.z >> en.x >> en.y >> en.z) {
        for (int i = 0; i < 3; ++i) {
            cin >> bar[i].x >> bar[i].y >> bar[i].z;
        }
        Line3D myen(my, en);
        Plane barier(bar[0], bar[1], bar[2]);
        vector<Point3D> cps = crosspointSPL(myen, barier);
        if (cps.empty()) cout << "HIT" << endl;
        else {
            Point3D cp = cps[0];
            if (area(cp, bar[1], bar[2]) + area(cp, bar[2], bar[0]) + area(cp, bar[0], bar[1]) - area(bar[0], bar[1], bar[2]) > EPS)
                cout << "HIT" << endl;
            else
                cout << "MISS" << endl;
        }
    }
}


Measured memory_bytes: 1220
import sys
def input():
    return sys.stdin.readline()[:-1]
q,h,s,d=map(int,input().split())
n=int(input())
li=[[0.25,q],[0.5,h],[1,s]]
li.sort(key=lambda x: x[1]/x[0])
li=[[1,int(li[0][1]/li[0][0])],[2,d]]
li.sort(key=lambda x: x[1]/x[0])
# print(li)
ans=0
now=0
for i in range(2):
    ko=(n-now)//li[i][0]
    ans+=ko*li[i][1]
    now+=ko*li[i][0]
    now=int(now)
    # print(ans,now)
print(int(ans))

Measured memory_bytes: 38448
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
const ll INF=1LL<<60;
const int inf=1<<30;
const int mod=1e9+7;
const int MOD=998244353;
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;cin >> n >> k;
    vector<vector<int>> g(n);
    for(int i=0;i<n-1;i++){
        int a,b;cin >> a >> b;
        a--,b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    stack<int> st;
    ll ans=k;
    vector<bool> vis(n);
    vis[0]=true;
    st.push(0);
    while(!st.empty()){
        int p=st.top();
        st.pop();
        ll cnt=0;
        for(int x:g[p]){
            if(vis[x]){
                continue;
            }
            if(p==0){
                (ans*=k-1-cnt)%=mod;
            }
            else{
                (ans*=k-2-cnt)%=mod;
            }
            cnt++;
            st.push(x);
            vis[x]=true;
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 6520
#include<bits/stdc++.h>
using namespace std;
int n,mo,a[233];
void init()
{
	cin>>n>>mo;
	for(int i=1;i<=n;i++) cin>>a[i];
	
}
void work()
{
	for(int i=1;i<=n;i++) mo=mo-a[i];
	sort(a+1,a+n+1);
	int sum;
	sum=mo/a[1]+n;
	cout<<sum;	
}
int main()
{
	init();
	work();
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <map>
#include <set>
#include <queue>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define rep(i,a,b) for(int i = a; i <= b; i++)
#define dep(i,a,b) for(int i = a; i >= b; i--) 
#define Rep(i,a) for(int i = 0; i < a; i++)
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ab(x) ((x) < 0 ? -(x) : (x))
using namespace std;
typedef long long LL;
typedef map<int, int>::iterator mit;
typedef set<int ,int>::iterator sit;
const int N = 100010, mod = 1e9 + 7;
int c[N];
int pw(int a, int b) { int w = 1; for(;b;b >>= 1, a = 1LL * a * a % mod) if (b & 1) w = 1LL * w * a % mod; return w; }
int main() {
	int n; scanf("%d",&n);
	rep(i,1,n) { int a; scanf("%d",&a); c[a]++; }
	bool flag = true;
	rep(i,1,n - 1) if ((i & 1) != (n & 1) && c[i] != 2) flag = false;
	if (n & 1) if (c[0] != 1) flag = false;
	if (flag) printf("%d\n",pw(2,n/2)); else printf("%d\n",0);
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <math.h>
#define ALL(a)    a.begin(), a.end() 
#define rep(i, K, N)  for(long long int i = K; i <= N; i++)
#define ll long long int
using namespace std;

vector<ll> V;

void prime_factor(ll N){

bool C = 1;

while(C){

C = 0;

    rep(i, 2, sqrt(N)){

    if(N%i == 0){V.push_back(i);N /= i;C = 1;break;}
   
    }

}

V.push_back(N);

}

int main() {
ll N, Ans = 0;cin >> N;
if(N == 1){cout << 0;exit(0);}
map<ll, ll> M;

prime_factor(N);

rep(i, 0, V.size() - 1)M[V[i]]++;

for(auto x : M){
ll n = 1;
    while(1){
    if(x.second < (n*(n + 1))/2)break;
    Ans++;n++;
    }
}
cout << Ans;
}

Measured memory_bytes: 3728
#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
long long l,c,d1[310][310],d2[310][310];
void floyd(long long dist[310][310]){
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
}
int main(){
	//freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>m>>l;
	memset(d1,63,sizeof(d1));
	for(int i=1;i<=n;i++)
		d1[i][i]=0LL;
	while(m--){
		cin>>a>>b>>c;
		d1[a][b]=d1[b][a]=c;
	}
	floyd(d1);
	memset(d2,63,sizeof(d2));
	for(int i=1;i<=n;i++)
		d2[i][i]=0LL;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(d1[i][j]<=l)
				d2[i][j]=1;
		}
	}
	floyd(d2);
	int q;
	cin>>q;
	while(q--){
		cin>>a>>b;
		if(d2[a][b]>1e18)
			cout<<-1<<endl;
		else
			cout<<d2[a][b]-1<<endl;
	}
	return 0;
}


Measured memory_bytes: 2048
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 1e6 + 100 ;
 
 
long long dp[MAXN] , tmp[MAXN] , nx[MAXN] , a[MAXN] ; 
 
int32_t main(){
	//ios_base::sync_with_stdio(0) ;
	//cin . tie(0) ; cout . tie(0) ; 
 
	int n ; cin >> n ; 
	int e , t ; cin >> e >> t ; 
	for(int i = 0 ; i < n ; i ++)
		cin >> a[i] ; 
	int l = n - 1 ; 
	//cout << "Hir" << endl ; 
	for(int i = n - 1 ; i >= 0 ; i --){
		while(l > 0 && 2 * (a[i] - a[l - 1]) <= t)
			l -- ; 
		nx[i] = l ; 
	}
	//cout << "Hir" << endl ; 
	memset(dp , 63 , sizeof dp) ; 
	memset(tmp , 63 , sizeof tmp) ; 
	dp[0] = 0 ; 
	tmp[0] = -2 * a[0] ;
	//cout << 0 << ' ' << dp[0]<< ' '  << tmp[0]<< ' ' << '\n' ; 
	for(int i = 1 ; i <= n ; i ++){
		dp[i] = t + dp[nx[i - 1]] ;
		if(nx[i - 1]) dp[i] = min(dp[i] , 2 * a[i - 1] + tmp[nx[i - 1] - 1]) ;
		tmp[i] = min(tmp[i - 1] , dp[i] - 2 * a[i]) ; 
		//cout << i << ' ' << dp[i] << ' ' << tmp[i] << '\n' ; 
	}
	cout << dp[n] + e ; 
 
}

Measured memory_bytes: 22144
#pragma optimization_level 3
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#define F first
#define S second
#define vec vector
#define pb push_back
#define pll pair<ll,ll>
#define pdd pair<ld, ld>
#define pq priority_queue
#define umap unordered_map
#define uset unordered_set
#define pii pair<int, int>
#define pnn pair<Node*, Node*>
#define uid uniform_int_distribution
#define FILE ifstream in("input.txt");ofstream out("output.txt");
#define fast cin.tie(0);cout.tie(0);cin.sync_with_stdio(0);cout.sync_with_stdio(0);
using namespace std;
typedef string str;
typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

int main() {
    fast;
    ll a; cin>>a;
    vec<ll> m(a), dp(a);
    for(int q=0; q<a; q++) cin>>m[q];
    dp[1] = abs(m[1]-m[0]);
    for(int q=2; q<a; q++){
        dp[q] = min(dp[q-1]+abs(m[q]-m[q-1]), dp[q-2]+abs(m[q]-m[q-2]));
    }
    cout<<dp[a-1];
}

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

int main()
{
    string s; cin >> s;
    const int n = s.length();

    vector<int> col;
    int cnt = 1;
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i-1]) {
            cnt++;
        } else {
            col.push_back(cnt); cnt = 1;
        }
    }
    col.push_back(cnt);

    vector<int> ans(n, 0);
    int pos = 0, sum = 0;
    for (int i = 0; i < col.size(); i++) {
        if (i % 2 == 0) pos = sum + col[i];
        sum += col[i];

        if (i % 2 == 0) {
            ans[pos] += col[i] / 2;
            ans[pos - 1] += col[i] - col[i] / 2;
        } else {
            ans[pos] += col[i] - col[i] / 2;
            ans[pos - 1] += col[i] / 2;
        }
    }

    for (int i = 0; i < n; i++) {
        cout << (i ? " " : "") << ans[i];
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 1528
#include <iostream>
#include<set>
#include<vector>
#include<string>
using namespace std;
const int mod=1000000007;
int add(int a, int b)
{
	int c=a+b;
	if(c>=mod)c-=mod;
	return c;
}
int dif(int a, int b)
{
	int c=a-b;
	if(c<0)c+=mod;
	return c;
}
int mlt(int a, int b)
{
	long long c=a*1LL*b;
	return c%mod;
}
int bp(int a, int b)
{
	if(b==0)return 1;
	if(b%2==0)
	{
		int val=bp(a, b/2);
		return mlt(val, val);
	}
	if(b%2==1)
	{
		int val=bp(a, b-1);
		return mlt(val, a);
	}
}
int inv(int a)
{
	return bp(a, mod-2);
}
void outp(vector<vector<int>>&v)
{
	for(int i=0; i<v.size(); i++)
	{
		for(int j=0; j<v[i].size(); j++)cout<<v[i][j]<<' ';
		cout<<endl;
	}
	cout<<endl;
}
bool tst(string s, int k, int a, int b)
{
	if(b<a)return false;
	int cura=a, curb=b;
	for(int j=0; j<s.length(); j++)
	{
		if(s[j]=='0')
		{
			if(curb==k)
				curb--;
			else curb++;
			cura++;
			if(cura>curb)return false;
			if(cura<0)return false;
		}
		if(s[j]=='1')
		{
			curb--;
			cura--;
			if(cura<0)cura+=2;
			if(cura>curb)return false;
		}
		if(s[j]=='?')
		{
			cura--;
			if(cura<0)cura=1;
			curb++;
			if(curb>k)curb-=2;
			if(cura>curb)return false;
		}
	}
	return true;
}
bool check(string s, int k)
{
	if(k%2==0)
	{
		if(tst(s, k, 0, k))return true;
		if(tst(s, k, 1, k-1))return true;
		return false;
	}
	else
	{
		if(tst(s, k, 0, k-1))return true;
		if(tst(s, k, 1, k))return true;
		return false;
	}
}
int main()
{
	string s;
	cin>>s;
	int n=s.length();
	vector<int>l0(n+1), l1(n+1);
	int maxval=0;
	for(int i=1; i<=n; i++)
	{
		if(s[i-1]=='0')
		{
			l0[i]=l0[i-1]+1;
		}
		else{
			l0[i]=max(l0[i-1]-1, 0);
		}
		if(s[i-1]=='1')
		{
			l1[i]=l1[i-1]+1;
		}
		else{
			l1[i]=max(l1[i-1]-1, 0);
		}
		maxval=max(maxval, l0[i]);
		maxval=max(maxval, l1[i]);
	}
	if(check(s, maxval))cout<<maxval<<endl;
	else cout<<maxval+1<<endl;
}

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

int main() {
	ll L, N;
	cin >> L >> N;
	vector<ll> xr(N + 1);
	vector<ll> xl(N + 1);
	xr[0] = 0;
	xl[0] = 0;
	for (int i = 1; i <= N; ++i) {
		cin >> xr[i];
		xl[N - i + 1] = L - xr[i];
	}

	vector<ll> dr(N + 1, 0);
	vector<ll> dl(N + 1, 0);
	for (int i = 1; i <= N; ++i) {
		dr[i] += dr[i - 1] + xr[i];
		dl[i] += dl[i - 1] + xl[i];
	}

	ll res = 0;
	for (int i = 0; i <= N; ++i) {
		// 最初、右に進む
		int r = (N - i) / 2;
		int l = (N - i + 1) / 2;
		ll tmp_r = (dr[i + r] - dr[i] + dl[l])*2 + xr[i]*2;
		if ((N - i) % 2 == 0) { tmp_r -= xr[i + r]; }
		else { tmp_r -= xl[l]; }

		// 最初、左に進む
		r = (N - i + 1) / 2;
		l = (N - i) / 2;
		ll tmp_l = (dl[i + l] - dl[i] + dr[r])*2 + xl[i]*2;
		if ((N - i) % 2 == 0) { tmp_l -= xl[i + l]; }
		else { tmp_l -= xr[r]; }

		res = max({res, tmp_r, tmp_l});
	}

	cout << res << endl;

	return 0;
}


Measured memory_bytes: 6528