akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<=(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(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 Eunique(v) v.erase(unique(all(v)),v.end())
#define Eback(s) s.erase(s.end()-1,s.end())
#define rev(v) reverse(all(v))
#define minvec(v) *min_element(all(v))
#define maxvec(v) *max_element(all(v))
#define pb push_back
#define pf push_front
#define mod 1000000007
#define m_p make_pair
#define DOUBLE fixed << setprecision(15)
#define OK puts("OK")
#define OK1 puts("OK1")
#define OK2 puts("OK2")
#define SIZE(s) (int)s.size()
#define INF ((1LL<<62)-(1LL<<31))
#define zero(x,n) setw(x) << setfill('0') << n

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef vector<pair<int,int>> vpii;
typedef vector<pair<ll,ll>> vpll;
typedef vector<string> vs;
const double pi = acos(-1.0);

template<class A, class B>
ostream& operator<<(ostream& ost, const pair<A, B>&p) {
	ost << "{" << p.first << ", " << p.second << "} ";
	return ost;
}

template<class T>
ostream& operator<<(ostream& ost, const vector<T>&v) {
	ost << "{";
	for (int i = 0; i<(int)v.size(); i++) {
		if (i)ost << " ";
		ost << v[i];
	}
	ost << "} \n";
	return ost;
}

template<class A, class B>
ostream& operator<<(ostream& ost, const map<A, B>&v) {
	ost << "{";
	for (auto p:v) {
		ost << "{" << p.first << ", " << p.second << "} ";
	}
	ost << "} ";
	return ost;
}

template<class T>
inline bool chmax(T& a, T b){if(a<b){a=b;return true;} return false;}

template<class T>
inline bool chmin(T& a, T b){if(a>b){a=b;return true;} return false;}

ll gcd(ll x, ll y) {return __gcd(x,y);}
ll lcm(ll x, ll y) {return x/__gcd(x,y)*y;}

int main()
{
	ll n,m;
	cin >> n >> m;
	vvll v(n,vll(m));
	vll w(m);
	rep(i,n)rep(j,m) cin >> v[i][j];
	rep(i,m) cin >> w[i];
	rep(i,n){
		ll sum=0;
		rep(j,m){
			sum+=v[i][j]*w[j];
		}
		cout << sum << endl;
	}
	return 0;
}


Measured memory_bytes: 3172
#include<stdio.h>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int N=200100,P=1e9+7;
inline char gc(){
    static char buf[N],*s=buf,*t=buf;
    return s==t&&(t=(s=buf)+fread(buf,1,N,stdin),s==t)?EOF:*s++;
}
inline ll read(){
	ll x=0,f=0,c=getchar();
	for(;c>'9'||c<'0';f=c=='-',c=getchar());
	for(;c>='0'&&c<='9';c=getchar())
	x=(x<<1)+(x<<3)+c-'0';return f?-x:x;
}
inline void write(ll x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)write(x/10);putchar(x%10+'0');
}
int n,L,h[N],ne[N],to[N],f[N],g[N],ans;
inline void addl(int x,int y){
	ne[++L]=h[x];h[x]=L;to[L]=y;
	ne[++L]=h[y];h[y]=L;to[L]=x;
}
void dfs(int x,int fa){
	int k,fk=0;
	for(k=h[x];k;k=ne[k])
	if(to[k]!=fa){
		dfs(to[k],x);
		fk|=g[x]&g[to[k]];
		g[x]|=g[to[k]];
	}f[x]=0;
	while((1<<f[x])<=fk||((g[x]>>f[x])&1))f[x]++;
	g[x]=(g[x]>>f[x]<<f[x])|(1<<f[x]);
	ans=max(ans,f[x]);
}
int main(){
	//freopen("1.out","w",stdout);
	n=read();
	for(int i=1;i<n;i++)addl(read(),read());
	dfs(1,0);printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 6272
import java.util.*;
class Main{
public static void main(String[]args){
Scanner sc=new Scanner(System.in);
  int n=sc.nextInt();
  int m=sc.nextInt();
  long time=(n-m)*100;
  time+=1900*m;
  time*=(int)(Math.pow(2,m));
  System.out.println(time);
    

}
}


Measured memory_bytes: 35752
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

s_in = lambda: stdin.readline()[:-1]  # s = s_in()
d_in = lambda: int(stdin.readline())  # N = d_in()
ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N = d_in()
A_list = np.array(ds_in(), dtype=int)
B_list = np.array(ds_in(), dtype=int)

if sum(A_list) < sum(B_list):
    print(-1)
    exit()

diff = A_list - B_list
neg = - diff[diff < 0].sum()
ans = (diff < 0).sum()

plus = np.sort(diff)[::-1]
for p in plus:
    if neg <= 0:
        break
    ans += 1
    neg -= p

print(ans)


Measured memory_bytes: 32288
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <functional>
#include <numeric>
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main(void) {
	int K;
	cin >> K;
	string S;
	cin >> S;
	if (S.length() <= K) {
		cout << S << endl;
		return 0;
	}
	cout << S.substr(0, K) << "..." << endl;
	return 0;
}

Measured memory_bytes: 3640
#入力（後でいじる）
def pin(type=int):
    return map(type,input().split())
#どっかで最悪計算量の入力データを用意する関数を作ろう？

#solution:
def comp(p):#期待値
    return ((p+1)/2)
#潜 影 蛇 手 ! !
        
#input
N,k=pin()
S=input()
ans=""
for i in range(N):
    ans+=S[i] if i!=k-1 else chr(ord(S[i])+32)
print(ans)
#print(["NO","YES"][1-cond])

Measured memory_bytes: 38256
#include<stdio.h>
#include<stdlib.h>
#define NIL NULL


struct node{
  int key;
  struct node *right;
  struct node *left;
  struct node *parent;
};


typedef struct node * Node;

Node root;

Node treeMinimum(Node x){
  while (x->left != NIL){
    x = x->left;
  }
  return x;
}
 
 
 
Node IterativetreeSearch(Node u, int k){
 
  if(u == NIL || k == u -> key) return u;
  if(k < u -> key) return IterativetreeSearch(u -> left, k);
  else return IterativetreeSearch(u -> right, k);
 
}
 
 
 

Node treeSuccessor(Node x){
  Node y;
  if(x->right!= NIL){
    return treeMinimum(x->right);
  }
  y = x->parent;
 
  while(y != NIL && x == y->right){
    x = y;
    y = y->parent;
  }
  return y;
}
 
void treeDelete(Node z){
  Node y; 
  Node x;
 
}
 
void insert(int k){
  
  Node y = NIL;
  Node x = root;
  Node z;
 
  z = malloc(sizeof(struct node));
  z->key = k;
  z->left = NIL;
  z->right = NIL;
 
  while(x!= NIL){
    y = x;
    if(z->key < x->key){
      x = x->left;
    }
    else x = x->right; 
  }
  z->parent = y;
 
  if(y==NIL){
    root = z;
  }
  else if (z->key < y->key){
    y->left = z;
  }
   
  else y->right = z;
}
 
void inorder(Node u){
  if(u != NIL){
    inorder(u->left);
    printf(" ");
    printf("%d",u->key);
    inorder(u->right);
  }
  
}
 
 
 
 
void preorder(Node u){
   
   
  if (u != NIL) {
    printf(" ");
    printf("%d",u->key); 
    preorder(u->left);
    preorder(u->right);
     
  
     
  }
}
 
int main(){
  int n, i, x;
  char com[20];
  
  scanf("%d", &n);
 
  for (i=0;i<n;i++){
    scanf("%s", com);
    if (com[0]=='f'){
      scanf("%d",&x);
      Node t = IterativetreeSearch(root, x);
      if (t!=NIL){ 
	printf("yes\n");
      }
      else {
	printf("no\n");
      }
    }
    else if (com[0]=='i'){
      scanf("%d", &x);
      insert(x);
    } 
     
     
    else if ( com[0] == 'p' ){
     
      inorder(root);
      printf("\n");
      preorder(root);
      printf("\n");
        
    }
    else if (com[0]=='d'){
      scanf("%d", &x);
      treeDelete(IterativetreeSearch(root, x));
    }
  }

  
  return 0;
}

Measured memory_bytes: 19364
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dish = new int[5];
        for(int i = 0;i<dish.length;i++)dish[i]=sc.nextInt();
        int ans = 0;
        int max=0;
        for(int i = 0;i<dish.length;i++){
            int tmp = dish[i];
            while(tmp%10!=0){
                tmp++;
            }
            if(max<tmp-dish[i])max=tmp-dish[i];
            ans+=tmp;
        }
        System.out.println(ans-max);
    }
}


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

int main() {
  int N, W;
  cin>>N>>W;
  int w[N], v[N];
  for (int i=0; i<N; i++) cin>>w[i]>>v[i];
  long long dp[N][W+1];
  for (int i=0; i<=W; i++) {
    if (i >= w[0]) {
      dp[0][i] = v[0];
    } else {
      dp[0][i] = 0;
    }
  }
  for (int i=1; i<N; i++) {
    for (int j=0; j<=W; j++) {
      if (j >= w[i]) {
        dp[i][j] = max(dp[i-1][j-w[i]] + v[i], dp[i-1][j]);
      } else {
        dp[i][j] = dp[i-1][j];
      }
    }
  }
  cout<<dp[N-1][W]<<endl;
}

Measured memory_bytes: 78336
#include <bits/stdc++.h>
#define rep(a, b, c) for(int a = (b); a <= (c); ++ a)
#define per(a, b, c) for(int a = (b); a >= (c); -- a)
using namespace std;
template <class T> void rd(T &x){
  x = 0; int f = 1; char ch = getchar();
  while(ch < '0' || ch > '9'){ if(ch == '-') f = -1; ch = getchar(); }
  while(ch >= '0' && ch <= '9') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  x *= f;
}

typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 5e5 + 5;
int n;
int a[maxn], c[maxn];
ll ans;
vector <int> st[1048576 + 5];

void add(ll &a, ll b){ a = (a + b) % mod; }

ll qpow(ll x, ll n){ ll y = 1;
  for(; n; n >>= 1, x = x * x % mod)
	if(n & 1) y = y * x % mod;
  return y;
}

void work(int x, int op){
  if(!st[x].size()) return ;
  ll s0, s1;
  s0 = s1 = 0;
  for(int i = 0; i < st[x].size(); ++ i){
	int p = st[x][i];
	add(s1, s0 + 1);
	if(i < st[x].size() - 1){
	  add(s0, (c[st[x][i + 1]] - c[p]) * s1);
	}
  } 
  if(op) add(ans, s1);
  else add(ans, s0 + 1);
}

int main(){
  rd(n);
  rep(i, 1, n){
	rd(a[i]), a[i] ^= a[i - 1];
	st[a[i]].push_back(i);
	if(a[i] == 0) c[i] ++;
	c[i] += c[i - 1];
  }
  if(a[n]) work(a[n], 0);
  else{
	int all = (1 << 20) - 1;
	rep(i, 1, all) work(i, 1);
	ans = (ans + qpow(2, c[n] - 1)) % mod;
  }
  printf("%lld\n", ans);
  return 0;
}


Measured memory_bytes: 38388
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
using namespace std;

long long beki(long long x)
{
    long long ans = 1;
    long long i;
    for(i = 0;i < x;++i){
        ans *= 2;
    }
    return ans;
}

int main()
{
    long long n,k;
    long long i,j;
    cin >> n >> k;
    vector<long long>a(n);
    for(i = 0;i < n;++i){
        cin >> a.at(i);
    }
    long long temp0 = 0,temp1 = 0;
    long long max1 = 0;
    for(i = 0;i < n;++i){
        if(a.at(i) > max1){
            max1 = a.at(i);
        }
    }
    if(k > max1){max1 = k;}
    long long keta = 0;
    while(max1){
        max1 /= 2;
        ++keta;
    }
    --keta;
    vector<long long> aboutk(keta+1);
    for(i = 0;i <= keta;++i){
        if(k % 2){
            aboutk.at(i) = 1;
        }else{
            aboutk.at(i) = 0;
        }
        k /= 2;
    }
    bool flag = true;
    long long ans = 0;
    for(i = keta;i >= 0;--i){
        long long t = 1; t = t << i;
        for(j = 0;j < n;++j){
            if(a.at(j) & t){
                ++temp1;
            }else{
                ++temp0;
            }
        }
        if(flag && aboutk.at(i) == 0){
            ans += beki(i)*temp1;
        }else{
            ans += beki(i)*max(temp1,temp0);
            if(flag){
                if(temp1 >= temp0){
                    flag = false;
                }
            }
        }
        temp0 = 0; temp1 = 0;
    }
    cout << ans << endl;
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    int flag = 0;

    int a[n];
    for(int i = 0; i < n; i++)
    {
        cin >> a[i];
        if(a[i] % 2)
            flag = 1;
    }

    cout << (flag ? "first" : "second") << endl;

    return 0;
}


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

#define fi      first
#define se      second
#define mp      make_pair
#define pb      push_back
#define si(x)   scanf("%d", &x)
#define sl(x)   scanf("%lld", &x)
#define all(x)  x.begin(), x.end()

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef map<ll, ll> mll;
typedef pair<ll, ll> pll;
typedef map<int, int> mii;
typedef pair<int, int> pii;
typedef map<char, int> mci;
typedef map<char, char> mcc;
typedef pair<char, int> pci;
typedef map<string, int> msi;
typedef unsigned long long ull;

const int MAX = 200005;
const double EPS = 1e-11;
const ll MOD = 1000000007;
const double PI = 2 * acos(0.0);

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

    if (A == B) {
        puts("Draw");
    }
    else if (A == 1) {
        puts("Alice");
    }
    else if (B == 1) {
        puts("Bob");
    }
    else if (A > B) {
        puts("Alice");
    }
    else if (B > A) {
        puts("Bob");
    }

    return 0;
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll, ll> P;

#define fi first
#define se second
#define repl(i,a,b) for(ll i=(ll)(a);i<(ll)(b);i++)
#define rep(i,n) repl(i,0,n)
#define each(itr,v) for(auto itr:v)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define dbg(x) cout<<#x"="<<x<<endl
#define mmax(x,y) (x>y?x:y)
#define mmin(x,y) (x<y?x:y)
#define maxch(x,y) x=mmax(x,y)
#define minch(x,y) x=mmin(x,y)
#define uni(x) x.erase(unique(all(x)),x.end())
#define exist(x,y) (find(all(x),y)!=x.end())
#define bcnt __builtin_popcount

#define INF INT_MAX/3

const int N=1<<17;
const int NIL=INT_MIN;

int mini[N*2];
int lazy[N*2];

void init(){
  for(int i=0;i<N*2;i++)lazy[i]=NIL;
}

void setlazy(int k,int v){
  lazy[k]=v;
  mini[k]=v;
}

void push(int k){
  if(lazy[k]==NIL)return ;
  setlazy(k*2,lazy[k]);
  setlazy(k*2+1,lazy[k]);

  lazy[k]=NIL;
}

void fix(int k){
  mini[k]=min(mini[k*2],mini[k*2+1]);
}

void fill(int ql,int qr,int v,int k=1,int nl=0,int nr=N){
  if(nr<=ql||qr<=nl)return ;
  if(ql<=nl&&nr<=qr){
    setlazy(k,v);
    return ;
  }
  push(k);
  int nm=(nl+nr)/2;
  fill(ql,qr,v,k*2,nl,nm);
  fill(ql,qr,v,k*2+1,nm,nr);
  fix(k);
}

int minimum(int ql,int qr,int k=1,int nl=0,int nr=N){
  if(nr<=ql||qr<=nl)return INT_MAX;
  if(ql<=nl&&nr<=qr)return mini[k];
  push(k);
  int nm=(nl+nr)/2;
  int vl=minimum(ql,qr,k*2,nl,nm);
  int vr=minimum(ql,qr,k*2+1,nm,nr);
  return min(vl,vr);
}

int main(){
	cin.sync_with_stdio(false);
  init();
  int n,q;
  cin>>n>>q;
  fill(0,n,(1<<31)-1);
  rep(i,q){
    int t;
    cin>>t;
    if(!t){
      int a,b,c;
      cin>>a>>b>>c;
      fill(a,b+1,c);
    }else{
      int a,b;
      cin>>a>>b;
      cout<<minimum(a,b+1)<<endl;
    }
  }
	return 0;
}

Measured memory_bytes: 4952
def profit(array)
  return array[0] if array.size() == 1
  min = (array[0] > array[1]) ? array[1] : array[0]
  max_profit = array[1] - array[0]

  array.each_with_index do |num, i|
    next if (i < 2)
    if (num < min) then
      min = num
    else
      diff = num - min
      max_profit = diff if (diff > max_profit)
    end
  end

  return max_profit
end

n = gets.strip.to_i
input = []
n.times do |item|
  input << gets.strip.to_i
end

p(profit(input))

Measured memory_bytes: 7796
n,m,x = map(int, input().split())
a = list(map(int, input().split()))
l = []
before = 0
after = 0
for i in range(n+1):
  l.append(i)

for i in range(m):
  if a[i] < x:
    before += 1
  else:
    after += 1
print(min(before, after))

Measured memory_bytes: 3064
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <string.h>
#define s(n)                        scanf("%d",&n)
#define sc(n)                       scanf("%c",&n)
#define sl(n)                       scanf("%I64d",&n)
#define sf(n)                       scanf("%lf",&n)
#define ss(n)                       scanf("%s",n)
#define INF                         (int)1e9
#define EPS                         1e-9
#define bitcount                    __builtin_popcount
#define gcd                         __gcd
#define forall(i,a,b)               for(int i=a;i<b;i++)
#define foreach(v, c)               for( typeof( (c).begin()) v = (c).begin();  v != (c).end(); ++v)
#define all(a)                      a.begin(), a.end()
#define in(a,b)                     ( (b).find(a) != (b).end())
#define pb                          push_back
#define fill(a,v)                    memset(a, v, sizeof a)
#define sz(a)                       ((int)(a.size()))
#define mp                          make_pair
#define MOD                         1000000007
typedef long long ll;
/*For you see , each day i love you
 more.Today more than yesterday
  less than tomorrow.*/
using namespace std;

int main()
{
	int x;s(x);
	cout<<1-x<<endl;
	return 0;
}

Measured memory_bytes: 3744
my ($n) = split(/\s+/, <>);

my $s = 0;
for my $i (1..int(sqrt($n-1))) {
    if ($n % $i == 0) {
	$j = $n/$i-1;
	if (int($n/$j) == $n%$j) {
	    $s += $j;
	}
    }
}
print "$s\n";


Measured memory_bytes: 512
#include<stdio.h>

typedef struct{
  char str[33];
  int frec;
  struct wordlist *next;
}wordlist;
wordlist *top;
wordlist *now;
int main(){
  int i,j,mlen;
  char str[1001],max[33],a[33];
  wordlist *wi;
  fgets(str,1000,stdin);
  str[strlen(str)-1]=' ';
  for(i=0,j=0,top=NULL,mlen=0;str[i];i++){
    if(str[i]==' '){
      str[i]='\0';
      if(mlen<strlen(str+j)){
	strcpy(max,str+j);
	mlen=strlen(str+j);
      }
      if(top){
	for(wi=top;wi;wi=wi->next){
	  if(!strcmp(wi->str,str+j)){
	    wi->frec++;
	    break;
	  }
	}
	if(!wi){
	  now->next=malloc(sizeof(wordlist));
	  now=now->next;
	  strcpy(now->str,str+j);
	  now->frec=1;
	  now->next=NULL;
	}
      }else{
	top=malloc(sizeof(wordlist));
	strcpy(top->str,str+j);
	now=top;
	top->frec=1;
	top->next=NULL;
      }
      j=i+1;
    }
  }
  for(wi=top,mlen=0;wi;wi=wi->next){
    if(mlen<wi->frec){
      mlen=wi->frec;
      strcpy(a,wi->str);
    }
  }
  printf("%s %s\n",a,max);
  return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int main(){
    int x, a, ans = 0;
    cin >> x >> a;
    if(x < a){
        cout << 0 << endl;
    }else{
        cout << 10 << endl;
    }
    return 0;
}


Measured memory_bytes: 764
#include<stdio.h>

int main(){

   int n;      // input, n<=100
   int a[100];  // input, 0<= a[i] <1000
   int i;

   scanf("%d", &n);
   for(i=0;i<n;i++) scanf("%d", &a[i]);

   for(i=n-1;i>=0;i--){
      if(i==0) printf("%d\n", a[i]);
      else printf("%d ", a[i]);
   }

   return 0;
}

Measured memory_bytes: 596
#include<bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
using namespace std;
int main(){
  int k,s,ans=0;
  cin>>k>>s;
  rep(i,k+1)rep(j,k+1)if ( s-i-j>=0 and s-i-j<=k) ans++;
  cout<<ans<<endl;

  return 0;
}


Measured memory_bytes: 256
//Don't have to see. start------------------------------------------
var read = require('readline').createInterface({
  input: process.stdin, output: process.stdout
});
var obj; var inLine = [];
read.on('line', function(input){inLine.push(input);});
read.on('close', function(){
  obj = init(inLine);
  console.error("\n");
  var start = Date.now();
  Main();
  var end = Date.now() - start;
  myerr("time : " + end + "ms");
  myerr("memory : " + Math.round(process.memoryUsage().heapTotal / 1024) + "KB");
});
function makeClone(obj){return JSON.parse(JSON.stringify(obj));}
function nextInt(){return myconv(next(),1);} function nextStrArray(){return myconv(next(),2);}
function nextIntArray(){return myconv(next(),4);} function nextCharArray(){return myconv(next(),6);}
function next(){return obj.next();} function hasNext(){return obj.hasNext();}
function init(input){  
  return {
    list : input, index : 0, max : input.length,
    hasNext : function(){return (this.index < this.max);},
    next : function(){if(this.hasNext()){return this.list[this.index++];}else{throw "ArrayIndexOutOfBoundsException ‚There is no more input";}}
  };
}
function myout(s){console.log(s);}
function myerr(s){console.error("debug:" + require("util").inspect(s,false,null));}
//param "no" is
//unknown or outlier : return i. 1: parseInt.
//2: split space. 4: split space and parseInt.
//6: split 1 character. 7: split 1 character and parseInt.
//8: join space. 9: join nextline. 0: join no character.
function myconv(i,no){try{switch(no){case 1:return parseInt(i);case 2:return i.split(" ");case 4:return i.split(" ").map(Number);case 6:return i.split("");case 7:return i.split("").map(Number);case 8:return i.join(" ");case 9:return i.join("\n");case 0:return i.join("");default:return i;}}catch(e){return i;}}

//Don't have to see. end------------------------------------------
function Main(){
  var N = nextInt();
  myout(N * N);
}


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

const int64_t MOD = 1000000007;
typedef int64_t ll;
typedef uint64_t ull;

#define FOR(i, start, end) for(uint64_t i=start; i<end; i++)
#define REP(i, n) FOR(i, 0, n)

// 最大公約数gcd
// 最小公倍数lcm=m*n/gcd
uint64_t gcd(uint64_t m, uint64_t n) {
  uint64_t temp;
  while (m % n != 0){
    temp = n;
    n = m % n;
    m = temp;
  }
  return n;
}

uint64_t lcm(uint64_t m, uint64_t n) {
  return (m*n)/gcd(m,n);
}

// vector<vector<uint64_t> > v(n+1, vector<uint64_t>(n+1, 0))
// v[n][k]に組み合わせ数が入る。
void comb(vector<vector <uint64_t> > &v){
  for(uint64_t i = 0;i <v.size(); i++){
    v[i][0]=1;
    v[i][i]=1;
  }
  for(uint64_t k = 1;k <v.size();k++){
    for(uint64_t j = 1;j<k;j++){
      v[k][j]=(v[k-1][j-1]+v[k-1][j]);
    }
  }
}

// 掛け算オーバーフロー判定
bool is_product_overflow(uint64_t a, uint64_t b) {

	uint64_t prod = a * b;
	
	return (prod / b != a);
}

//素因数分解
void primeFactorization(uint64_t a, list<uint64_t> &factors){ //素因数分解を出力するプログラム
  long i,sq;
  if(a%2==0){ //偶数の場合
    factors.push_back(2);
    primeFactorization(a/2,factors); //2で割った値で再帰
    return;
  }
  sq = sqrt(a);
  for(i=3;i<=sq;i+=2){ //3以上√a以下の奇数の場合
	if(a%i==0){
	  factors.push_back(i);
      primeFactorization(a/i,factors); //割れた値で再帰
      return;
	}
  }
  //偶数でも3以上√a以下の奇数の場合でも割り切れない場合
  if(a!=1){ //aが1でないなら、a自身は素数
    factors.push_back(a);
  }
}

// フェルマーの小定理
// mod. m での a の逆元 a^{-1} を計算する
// (a/b)%m = a*movinv(b,m)%m  
int64_t modinv(int64_t a, int64_t m) {
    int64_t b = m, u = 1, v = 0;
    while (b) {
        int64_t t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m;
    if (u < 0) u += m;
    return u;
}

/* 
  //エラトステネスのふるい
  int maxNum = 100000;
  char isNotPrime[maxNum+1] = {};
  isNotPrime[0]=isNotPrime[1]=1;
  for(int i=2;i<maxNum;i++){
    if(isNotPrime[i]==1) continue;
    int num = i+i;
    while(num<=maxNum){
      isNotPrime[num]=1;
      num += i;
    }
  }
*/
// 円周率
// M_PI

// #include <iomanip> // setprecisionを使用するのに必要
// cout << std::fixed << std::setprecision(15) << y << endl;

// 昇順
// priority_queue<int, vector<int>, greater<int> > queue;

// 降順ソート vector<int> v;
// sort(v.begin(),v.end(),greater<int>());

signed main() {
  int n;
  cin >> n;
  
  // 1*2, 1*3, ....
  // 2*1
  
  // a*b+c=n
  
  ll count = 0;
  for(ll i=1;i<n;i++){
    int d = n/i;
    if(n%i==0){
      d--;
    }
    count += d;
    // i*1, i*2, i*d
  }

  cout << count << endl;
  return 0;
}



Measured memory_bytes: 3668
#include<cstdio>
using namespace std;
int main(){
    int a,b,flag=1;
    char s[12];
    scanf("%d %d",&a,&b);
    scanf("%s",s);
    for(int i=0;i<a+b+1;i++){
        if(i==a&&s[i]!='-'){
            flag=0;
        }
        else if(i!=a&&(s[i]>'9'||s[i]<'0')){
            flag=0;
        }
    }
    if(flag){
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
}

Measured memory_bytes: 128
use std::cmp::*;
use std::io::*;
use std::num::*;
use std::str::*;

mod i {
    use super::*;

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

    pub fn str() -> String {
        read()
    }

    pub fn s() -> Vec<char> {
        str().chars().collect()
    }

    pub fn i() -> i64 {
        read()
    }

    pub fn u() -> usize {
        read()
    }

    pub fn f() -> f64 {
        read()
    }

    pub fn c() -> char {
        read::<String>().pop().unwrap()
    }

    pub fn iv(n: usize) -> Vec<i64> {
        (0..n).map(|_| i()).collect()
    }

    pub fn uv(n: usize) -> Vec<usize> {
        (0..n).map(|_| u()).collect()
    }

    pub fn fv(n: usize) -> Vec<f64> {
        (0..n).map(|_| f()).collect()
    }

    pub fn cmap(h: usize) -> Vec<Vec<char>> {
        (0..h).map(|_| s()).collect()
    }
}

fn main() {
    let (n, p) = (i::u(), i::u());
    let a = i::uv(n);
    let odd = a.iter().filter(|k| *k % 2 == 1).count();
    let even = a.iter().filter(|k| *k % 2 == 0).count();

    let mut s = 1usize;
    for _ in 0..even {
        s *= 2;
    }
    let mut ans = 0;
    //oddをi個選ぶ
    for i in 0..(odd + 1) {
        if i % 2 != p {
            continue;
        }
        let mut combination = 1;
        for j in 0..i {
            combination *= odd - j;
            combination /= j + 1
        }
        ans += combination * s;
        //dbg!(ans, i, p);
    }
    println!("{}", ans);
}


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

int main(void){
    long int table[200001]={0}, i, n, a[200001], ans=0;

    scanf("%ld",&n);
    for(i=1;i<=n;i++){
        scanf("%ld",&a[i]);
        table[a[i]]++;
    }

    for(i=1;i<=n;i++){
        if(table[i] != 0){
            ans += table[i]*(table[i]-1)/2;
        }
    }

    for(i=1;i<=n;i++){

        if(table[a[i]]==1){
            printf("%ld\n",ans);
        }else if(table[a[i]]==2){
            printf("%ld\n",ans-1);
        }else{
            printf("%ld\n",ans-(table[a[i]]-1));
        }
    }

    return 0;
}


Measured memory_bytes: 5820
/*
ID: rchalam1
LANG: C++14
TASK:
*/
// For train.usaco.org, fill the template above.

// Competitive Coding Template

// GCC OPTIMIAZTION FLAGS
#ifdef ONLINE_JUDGE
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#endif

#include <bits/stdc++.h>

/*
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
*/
// All Includes for Competitive Coding Template

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;

using vi = std::vector<int>;
using vll = std::vector<long long>;
using vull = std::vector<unsigned long long>;

#define FOR(i, a, b) for (auto i = (a); i < (b); ++i)
#define F0R(i, a) FOR(i, 0, a)
#define ROF(i, a, b) for (auto i = (a); i >= (b); --i)
#define R0F(i, a) ROF(i, a, 0)
#define ITR(a, x) for (auto& a: x)

#define FSRT(set) sort((set).begin(),(set).end())
#define RSRT(set) sort((set).rbegin(),(set).rend())
#define CSRT(set, function) sort((set).begin(),(set).end(), (function))
#define TRS(set) sort((set).begin(),(set).end(), greater<>())
#define REV(set) reverse((set).begin(),(set).end());

#define ALL(set) (set).begin(), (set).end()

#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

// For stdio, call setIO() or setIO("").
void setIO(std::ifstream &readFile, std::ofstream &writeFile, const std::string &name = "", bool stdIO = false)
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);
	if(!name.empty() && !stdIO)
	{
		readFile.open(name + ".in");
		if(readFile.fail()) return;
		writeFile.open(name + ".out");
		std::cin.rdbuf(readFile.rdbuf());
		std::cout.rdbuf(writeFile.rdbuf());
	}
}

// To time program, create object Timer  to start timing, and call Timer.elapsed().
#include <chrono>

class Timer
{
	std::chrono::time_point<std::chrono::high_resolution_clock> m_beg;
public:
	Timer() : m_beg(std::chrono::high_resolution_clock::now())
	{}

	void reset()
	{ m_beg = std::chrono::high_resolution_clock::now(); }

	[[nodiscard]] long double elapsed() const
	{
		return std::chrono::duration_cast<std::chrono::duration<long double, std::ratio<1> >>(
				std::chrono::high_resolution_clock::now() - m_beg).count();
	}
};

// Defines datatype
using dt = int;
// Defines MAXN value
constexpr dt MAXN = 1e5 + 1;
// Defines Modulus
constexpr dt MOD = 1e9 + 7;
// Defines Floating Point Correction
constexpr long double EPS = 1e-9;

//*****
//START CODE BELOW
//*****

int main(int argc, char *argv[])
{
	static std::ifstream readFile;
	static std::ofstream writeFile;
	setIO(readFile, writeFile);
	int n;
	cin >> n;
	vector<int> students(n);
	for(int i = 1; i <= n; ++i)
	{
		int a;
		cin >> a;
		students[a - 1] = i;
	}
	for(auto &student : students) cout << student << ' ';
	cout << '\n';
}

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

using namespace std;

int cnt[5];

int main() {
  for (int i = 0; i < 3; ++i) {
    int a, b;
    scanf("%d %d", &a, &b);
    ++cnt[a];
    ++cnt[b];
  }
  for (int i = 1; i <= 4; ++i) if (cnt[i] >= 3) {
    puts("NO");
    return 0;
  }
  puts("YES");
  return 0;
}

Measured memory_bytes: 256
using System;
using System.CodeDom.Compiler;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using System.Xml;

class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		Console.WriteLine((N + 1) / 2);
	}
}

//string s = Console.ReadLine();
//int[] inputintArray = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();
//int H = inputintArray[0];
//int W = inputintArray[1];
//int N = int.Parse(Console.ReadLine());
//int[] a = Console.ReadLine().Split(' ').Select(i => int.Parse(i)).ToArray();

//Console.WriteLine(ans);
//Console.ReadKey();


Measured memory_bytes: 11220
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
from collections import Counter
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())
N = int(input())
MAX = 10 ** 9
d = defaultdict(int)
for i in range(N):
    a = round(float(input()) * MAX)
    two = 0
    while a % 2 == 0:
        two += 1
        a //= 2
    five = 0
    while a % 5 == 0:
        five += 1
        a //= 5
    d[(two, five)] += 1

ans = 0
for p1 in d.keys():
    for p2 in d.keys():
        if (p1[0] + p2[0] >= 18) and (p1[1] + p2[1] >= 18):
            if p1 < p2:
                ans += d[p1] * d[p2]
            elif p1 == p2:
                ans += d[p1] * (d[p1] - 1) // 2
print(ans)

Measured memory_bytes: 77048
#include<bits/stdc++.h>
using namespace std;
int main(){
    int dp[11][46] = {},i,j,k,x,y;dp[0][0] = 1;
    for(i=0;i<10;i++){
        for(j=i+1;j>=1;j--){
            for(k=i;k<=45;k++) dp[j][k] += dp[j-1][k-i];
        }
    }
    while(true){
        scanf("%d%d",&x,&y);
        if(x == 0 && y == 0) break;
        if(y > 45) printf("0\n");
        else printf("%d\n",dp[x][y]);
    }
    return 0;
}


Measured memory_bytes: 3140
# coding: utf-8

import sys
import math
from collections import Counter
import itertools
import fractions
from decimal import *
#import numpy as np
#from functools import reduce

# 入力を整数に変換して受け取る
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SR(): return sys.stdin.readline().rstrip()

ascii_lowercase = 'abcdefghijklmnopqrstuvwxyz'
ascii_uppercase = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
ascii_uppercase2 = 'ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ'

# リストを改行区切りで出力する
p2D = lambda x: print(*x, sep="\n")
p2E = lambda x: print(''.join(x))
p2S = lambda x: print(*x, sep=" ")

# ###########################################
a,b = input().split()
da = Decimal(a)
db = Decimal(b)

print(math.floor(da*db))

Measured memory_bytes: 10608
#include<cstdio>
#define max 10000
#define NIL -1

struct node{
	int p,l,r;
};
node t[max];
int n;

void preparse(int u){
	if(u == NIL) return ;
	printf(" %d",u);
	preparse(t[u].l);
	preparse(t[u].r);
}

void inparse(int u){
	if(u == NIL) return ;
	inparse(t[u].l);
	printf(" %d",u);
	inparse(t[u].r);
}

void postparse(int u){
	if(u == NIL) return ;
	postparse(t[u].l);
	postparse(t[u].r);
	printf(" %d",u);
}





int main(){
	scanf("%d",&n);
	int v,l,r,root;
	for(int i=0;i<n;i++) t[i].p=NIL;
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&v,&l,&r);
		t[v].l=l;
		t[v].r=r;
		if(l!=NIL) t[l].p=v;
		if(r!=NIL) t[r].p=v;		
	}
	
	for(int i=0;i<n;i++) if(t[i].p == NIL) root = i;
	printf("Preorder\n");
	preparse(root);
	printf("\n");
	printf("Inorder\n");
	inparse(root);
	printf("\n");
	printf("Postorder\n");
	postparse(root);
	printf("\n");
	 
}


Measured memory_bytes: 2688
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdint.h> // uint64_t

#define max(a,b) ((a) > (b) ? (a) : (b))
#define min(a,b) ((a) > (b) ? (b) : (a))

int get_int(void) {
  int num;
  scanf("%d", &num);
  return num;
}

// <arr[0]> <arr[1]> .. <arr[size-1]>
int fget_array(int *arr, int size) {
    int i;
    for(i = 0; i < size; i++) {
        scanf("%d", &arr[i]);
    }
    return 0;
}

#define HASH_SIZE 65536

#define NUM_MAX 200000

int main(void) {
    int num = get_int();
    static int arr[NUM_MAX+1];
    static int map[NUM_MAX];

    fget_array(&arr[1], num);
    int i;
    // 0 < a2 - h2 = h1 + a1 < NUM_MAX
    for(i = 1; i <= num; i++) {
        // diff
        if(i - arr[i] >= 0) map[i-arr[i]]++;
    }
    int64_t ans = 0;
    for(i = 1; i <= num; i++) {
        int sum = arr[i] + i;
        if(sum >= NUM_MAX) continue;
        if(i - arr[i] >= 0) map[i-arr[i]]--;
        ans += map[sum];
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 3272
#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(void){
    int n;
    double ans=0;
    cin>>n;
    double a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,a+n,greater<int>());
    for(int i=0;i<n-1;i++){
        for(int j=i+1;j<n;j++){
            double s=a[i]-a[j];
            double b=0;
            if(i>1)b=a[0]+a[1];
            else if(i==1){
                b+=a[0];
                if(j==2)b+=a[3];
                else b+=a[2];
            }else{
                if(j==1)b=a[2]+a[3];
                else if(j==2)b=a[1]+a[3];
                else b=a[1]+a[2];
            }
            ans=max(ans,b/s);
        }
    }
    printf("%.6lf\n",ans);
}

Measured memory_bytes: 3344
import heapq
n, m = map(int, input().split())
a = []
[heapq.heappush(a, -x) for x in map(int, input().split())] 
while m > 0:
    t = heapq.heappop(a)
    t /= 2
    m -= 1
    heapq.heappush(a, int(t))
print(sum([abs(x) for x in a]))

Measured memory_bytes: 16400
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ll n;
	cin>>n;
	ll ans=0;
	set<ll>s;
	for(ll k=2;k*k<=n;k++)
	{
		ll n1=n;
		if(n%k==0)
		{
			while(n1%k==0)
				n1/=k;
		}
		if(n1%k==1)
		{
			ans++;
			s.insert(k);
		}
		ll div=n/k;
		n1=n;
		if(n%div==0)
		{
			while(n1%div==0)
				n1/=div;
		}
		if(n1%div==1)
		{
			ans++;
			s.insert(div);
		}
	}
	if(n>2)
	{
		s.insert(n);
		s.insert(n-1);
	}
	s.insert(n);
	cout<<s.size();
}


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

class Program
{
    static void Main(string[] args)
    {
        var line = Console.ReadLine().ToCharArray();
        var before = line[0];
        var ans = "Good";
        for (int i=1;i<4;++i)
        {
            if (before == line[i])
            {
                ans = "Bad";
            }
            before = line[i];
        }
        Console.WriteLine(ans);
    }
}



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

using namespace std;

#define ok1 printf("ok1\n");
#define ok2 printf("ok2\n");
#define M 1000000000000000000LL
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,s,n) for(int i=(s);i<(n);i++)
#define repr(i,n) for(int i=n-1;i>=0;i--)
#define REPR(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 pb push_back
#define pf push_front
#define MIN(a,b) a=min((a),(b))
#define MAX(a,b) a=max((a),(b))
#define SIZE(v) (int)v.size()
#define Eunique(v) v.erace(unique(all(v)),v.end())
#define pvec(v)　rep(i,v.size()){cout << v[i] << " ";}
#define INF 0x3f3f3f3f
#define mset(m,v) memset(m,v,sezeof(m))
#define mod 1e9 +7;

const double pi = acos(-1.0);

typedef string ss;
typedef vector<int> vi;
typedef vector<string> vs;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vll> vvll;
typedef deque<ll> dll;
typedef pair<ll,ll> P;
ll dx[4] = {1,0,-1,0},dy[4] = {0,1,0,-1};

ll gcd(ll x,ll y)
{
    ll r;
    while((r = x % y) != 0)
    {
        x = y;
        y = r;
    }
    return y;
}

ll lcm(ll x,ll y)
{
    x /= gcd(x,y);
    y /= gcd(x,y);
    return (x*y);
}

int main()
{
    ll n,ans = 1;
    string s;
    cin >> n >> s;
    REP(i,1,n){
        if(s[i-1] != s[i])ans++;
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 512
def gcd(n,m):return gcd(m,n%m) if m and n else n+m
n=int(input())
h=list(map(int,input().split()))
l=[0]*n
r=[0]*n
a,s=0,0
for i in range(n):
  l[i]=a
  a=gcd(a,h[i])
  r[-i-1]=s
  s=gcd(s,h[-i-1])
ans=1
for i in range(n):
  ans=max(ans,gcd(l[i],r[i]))
print(ans)

Measured memory_bytes: 63984
N = int(input())
S = list(map(int,list(input())))
def judge(x,l):
  ret = False
  num = 0
  for a,n in enumerate(l):
    if n==x:
      ret = True
      num = a
      break
      
  return ret,num

ans = 0
for i in range(10):
  tf1,n1 = judge(i,S)
  if tf1:
    for j in range(10):
      tf2,n2 = judge(j,S[n1+1:])
      if tf2:
        for k in range(10):
          tf3,n3=judge(k,S[n1+n2+2:])
          if tf3:
            ans+=1

print(ans)

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string a;
	cin>>a;
	for(int i=0;i<a.size();i++){
		if(a[i]<=90)
		{
		cout<<"No";
		return 0;
		}
	} 
	if(a.size()==6){
		if(a[2]==a[3]){
			if(a[4]==a[5]){
			cout<<"Yes";
			return 0;
			}
		}
	}
	cout<<"No";
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define R register
#define mp make_pair
#define ll long long
#define pii pair<int, int>
using namespace std;
const int N = 1100, K = 22, mod = 1e9 + 7;

int n, k, a[K];
ll f[K][N], comb[N][N];

template <class T>
inline void read(T &x) {
    x = 0;
    char ch = getchar(), w = 0;
    while (!isdigit(ch)) w = (ch == '-'), ch = getchar();
    while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
    x = w ? -x : x;
    return;
}

inline ll addMod(ll a, ll b) {
    return (a += b) >= mod ? a - mod : a;
}

int main() {
    read(n), read(k);
    for (R int i = 1; i <= k; ++i) read(a[i]);
    for (R int i = 0; i <= n; ++i) {
        comb[i][0] = 1;
        for (R int j = 1; j <= i; ++j)
            comb[i][j] = addMod(comb[i - 1][j - 1], comb[i - 1][j]);
    }
    f[0][0] = 1;
    for (R int i = 1; i <= k; ++i)
        for (R int j = 0; j <= n; ++j)
            for (R int l = max(0, j - a[i]); l <= j; ++l)
                f[i][j] = (f[i][j] + f[i - 1][l] * comb[n - l][j - l] % mod * comb[n - j + l][a[i] - j + l]) % mod;
    cout << f[k][n] << endl;
    return 0;
}

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

using ll = long long int;

const int MAX = (int)(1e5 + 5);
const ll INF = (ll)(1e10 + 5);

const int MAX_N = (int)(1e5 + 5);

int q;

bool prime[MAX_N];

int cnt[MAX_N];

void prepare() {
  for (int i = 0; i < MAX_N; ++i) {
    prime[i] = true;
  }

  prime[0] = prime[1] = false;

  for (int i = 2; i < MAX_N; i += 2) {
    prime[i] = false;
  }

  prime[2] = true;

  for (int i = 3; i * i < MAX_N; ++i) {
    if (!prime[i]) continue;

    for (int j = i * i; j < MAX_N; j += i) {
      prime[j] = false;
    }
  }

  for (int i = 2; i < MAX_N; ++i) {
    int other = (i + 1) / 2;
    cnt[i] = cnt[i - 1] + (prime[i] && prime[other] ? 1 : 0);
  }
}

int main(void) {
  // Here your code !
  scanf("%d", &q);

  prepare();

  for (int i = 0; i < q; ++i) {
    int l, r;
    scanf("%d %d", &l, &r);

    printf("%d\n", cnt[r] - cnt[l - 1]);
  }

  return 0;
}


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

int main()
{
  int X, Y;
  cin >> X >> Y;
  
  if(Y % 2 == 0 && (2 * X <= Y && Y <= 4 * X)){cout << "Yes" << endl;}
  else{cout << "No" << endl;}
}

Measured memory_bytes: 3620
N = int(input())
A = [int(a) for a in input().split(" ")]

for i in range(N):
    if A[i] % 2 == 0:
        if A[i] % 3 != 0 and A[i] % 5 != 0:
            print('DENIED')
            exit()
print('APPROVED')

Measured memory_bytes: 9140
N, M = gets.split.map{|i|i.to_i}
X = gets.split.map{|i|i.to_i}
Y = gets.split.map{|i|i.to_i}
P = 10 ** 9 + 7
#warn X.inspect
#warn Y.inspect
XS = Array.new(N - 1){|i|(X[i + 1] - X[i]) * ((i + 1) * (N - i - 1))}
YS = Array.new(M - 1){|i|(Y[i + 1] - Y[i]) * ((i + 1) * (M - i - 1))}
#warn XS.inspect
#warn YS.inspect
puts XS.inject(0, :+) * YS.inject(0, :+) % P


Measured memory_bytes: 17044
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 505;

int i, j, d, tab[N][N], a, k, n, bat[N][N];
LL sum;

void prop(int a, int b) {
	int add = (bat[a][b] == 0);
	if (a > 0 && tab[a - 1][b] > tab[a][b] + add) {
		tab[a - 1][b] = tab[a][b] + add;
		//printf("A %d %d %d\n", a - 1, b, tab[a - 1][b]);
		prop(a - 1, b);
	}
	if (b > 0 && tab[a][b - 1] > tab[a][b] + add) {
		tab[a][b - 1] = tab[a][b] + add;
		//printf("B %d %d %d\n", a, b - 1, tab[a][b - 1]);
		prop(a, b - 1);
	}
	if (a < n - 1 && tab[a + 1][b] > tab[a][b] + add) {
		tab[a + 1][b] = tab[a][b] + add;
		//printf("C %d %d %d\n", a + 1, b, tab[a + 1][b]);
		prop(a + 1, b);
	}
	if (b < n - 1 && tab[a][b + 1] > tab[a][b] + add) {
		tab[a][b + 1] = tab[a][b] + add;
		//printf("D %d %d %d\n", a, b + 1, tab[a][b + 1]);
		prop(a, b + 1);
	}
}

int main() {
scanf("%d", &n);
for (i=0;i<n;i++) for(j=0;j<n;j++) {
	d = min(i, j);
	d = min(d, n - 1 - i);
	d = min(d, n - 1 - j);
	tab[i][j] = d;
}
for (k=1;k<=n*n;k++) {
	//printf("%d\n", k);
	scanf("%d", &a);
	a--;
	i = a / n;
	j = a % n;
	sum += tab[i][j];
	bat[i][j] = 1;
	prop(i, j);
}
printf("%lld\n", sum);
return 0;
}





Measured memory_bytes: 32128
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <math.h>
#include <deque>
using ll = long long;
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    string ans = "NO";
    if(b-a==c-b) ans = "YES";
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
N, M, V, P = map(int, input().split())
A = list(map(int, input().split()))
A.sort(reverse=True)
W = N - V

def isOk(n):
    if n < P:
        return True
    b = A[n]

    D = [max(0, a - b) for a in A][P - 1:]
    cnt = -(-(sum(D) - W) // W) + 1

    return max(max(D), cnt) <= M

ok = -1
ng = N
while ng - ok > 1:
    mid = (ng + ok) // 2
    if isOk(mid):
        ok = mid
    else:
        ng = mid

print(ng)

Measured memory_bytes: 14964
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back
#define INF (1e9+1)

int main(){
    int n,ma,mb;
    cin>>n>>ma>>mb;
    vector<int> a(n), b(n), c(n);
    rep(i,n)cin>>a[i]>>b[i]>>c[i];
    
    static int dp[41][401][401];
    rep(i,41)rep(j,401)rep(k,401)dp[i][j][k] = INF;
    dp[0][0][0] = 0;
    
    rep(i,n){
        rep(j,401){
            rep(k,401){
                dp[i+1][j][k] = dp[i][j][k];
                if(j-a[i]<0 || k-b[i]<0)continue;
                dp[i+1][j][k] = min(dp[i][j-a[i]][k-b[i]] + c[i], dp[i+1][j][k]);
            }
        }
    }
    
    int ans = INF;
    int k = 1;
    while(k*ma<401 && k*mb<401){
        ans = min(ans,dp[n][k*ma][k*mb]);
        k++;
    }
    if(ans==INF)cout<<-1<<endl;
    else cout<<ans<<endl;
}


Measured memory_bytes: 25984
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,y;cin>>n>>y;
  int k;
  for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++){
    	if(i+j>n)continue;
      k = n-(i+j);
      if(1000*i+5000*j+10000*k == y){cout<<k<<' '<<j<<' '<<i;return 0;}
      
    }
  cout<<-1<<' '<<-1<<' '<<-1;
}

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

using namespace std;

typedef long long ll;

int main(){
  int x, pre, post;
  cin >> x;
  pre = x / 100;
  post = x % 100;
  if(1<=pre && pre<=12){
    if(1<=post && post<=12) cout << "AMBIGUOUS" << endl;
    else cout << "MMYY" << endl;
  }
  else{
    if(1<=post && post<=12) cout << "YYMM" << endl;
    else cout << "NA" << endl;
  }
  return 0;
}

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

using namespace std;

int main()
{
    long n,k,i,sum=0;
    cin>>n>>k;
    
    long h[n];
    for(i=0;i<n;i++)
    {
        cin>>h[i];
    }
    
    sort(h,h+n);
    
    for(i=0;i<(n-k);i++)
    {
        sum = sum + h[i];
    }
    cout<<sum;

    return 0;
}


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

int main() {
    string S;
    cin >> S;
    int cnt, res=0;
    for (int i=0; i<S.size()-1; i++) {
        if (S.at(i)=='A' || S.at(i)=='C'|| S.at(i)=='G'||S.at(i)=='T') {
            cnt = 1;
            for (int j=i+1; j<S.size(); j++) {
                if (S.at(j)=='A' || S.at(j)=='C'|| S.at(j)=='G'||S.at(j)=='T') cnt++;
                else {
                    break;
                }
            }
            res = max(res, cnt);
        }
        cnt = 0;
    }
    if (S.at(S.size()-1)=='A' || S.at(S.size()-1)=='C'|| S.at(S.size()-1)=='G'||S.at(S.size()-1)=='T') {
        res = max(res, 1);
    }
    cout << res;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define rep1(i, n) for (ll i = 1; i <= (n); ++i)
#define rrep(i, n) for (ll i = (n - 1); i >= 0; --i)
#define perm(c) sort(ALL(c));for(bool c##p=1;c##p;c##p=next_permutation(ALL(c)))
#define ALL(obj) (obj).begin(), (obj).end()
#define pb push_back
#define to_s to_string
#define len(v) (ll)v.size()
#define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end())
#define print(x) cout << (x) << '\n'
#define debug(x) cout << #x << ": " << (x) << '\n'
using namespace std;
using ll = long long;
typedef pair<ll, ll> P;
typedef vector<ll> vec;
typedef vector<vector<ll>> vec2;
typedef vector<vector<vector<ll>>> vec3;
ll MOD = 1e9 + 7;
ll devc(ll x, ll y) { return 1 + (x - 1) / y; }
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; }

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout << fixed << setprecision(20);

    ll N;
    cin >> N;
    vec A(N + 1), B(N);
    rep(i, N + 1) cin >> A[i];
    rep(i, N) cin >> B[i];

    ll ans = 0;
    rep(i, N){
        if(B[i] >= A[i]){
            ll d = B[i] - A[i];
            ans += A[i] + min(A[i + 1], d);
            A[i + 1] = max(A[i + 1] - d, 0LL);
        }else{
            ans += B[i];
        }
    }

    print(ans);

    return 0;
}

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

int main(){
  vector<int> a(5);
  int b=10,c,cnt=0;
  for(int i=0; i<5; i++){
    cin >> a.at(i);
    if(0<a.at(i)%10 && a.at(i)%10<b){
      b=a.at(i)%10;
      c=i;
    }
  }
  for(int i=0; i<5; i++){
    if(i!=c && a.at(i)%10!=0) cnt+=a.at(i)+(10-a.at(i)%10);
    else cnt+=a.at(i);
  }
  cout << cnt << endl;
  return 0;
}

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;

int main() {
    int K, T, a, amax = 0;
    cin >> K >> T;
    rep(i, T) {
        cin >> a;
        amax = max(amax, a);
    }
    cout << max(0, amax - (K - amax + 1)) << endl;
}

Measured memory_bytes: 256