akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <vector>

template <class T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }

template <int MOD>
struct ModInt {
    using lint = long long;
    int val;

    // constructor
    ModInt(lint v = 0) : val(v % MOD) {
        if (val < 0) val += MOD;
    };

    // unary operator
    ModInt operator+() const { return ModInt(val); }
    ModInt operator-() const { return ModInt(MOD - val); }
    ModInt inv() const { return this->pow(MOD - 2); }

    // arithmetic
    ModInt operator+(const ModInt& x) const { return ModInt(*this) += x; }
    ModInt operator-(const ModInt& x) const { return ModInt(*this) -= x; }
    ModInt operator*(const ModInt& x) const { return ModInt(*this) *= x; }
    ModInt operator/(const ModInt& x) const { return ModInt(*this) /= x; }
    ModInt pow(lint n) const {
        auto x = ModInt(1);
        auto b = *this;
        while (n > 0) {
            if (n & 1) x *= b;
            n >>= 1;
            b *= b;
        }
        return x;
    }

    // compound assignment
    ModInt& operator+=(const ModInt& x) {
        if ((val += x.val) >= MOD) val -= MOD;
        return *this;
    }
    ModInt& operator-=(const ModInt& x) {
        if ((val -= x.val) < 0) val += MOD;
        return *this;
    }
    ModInt& operator*=(const ModInt& x) {
        val = lint(val) * x.val % MOD;
        return *this;
    }
    ModInt& operator/=(const ModInt& x) { return *this *= x.inv(); }

    // compare
    bool operator==(const ModInt& b) const { return val == b.val; }
    bool operator!=(const ModInt& b) const { return val != b.val; }
    bool operator<(const ModInt& b) const { return val < b.val; }
    bool operator<=(const ModInt& b) const { return val <= b.val; }
    bool operator>(const ModInt& b) const { return val > b.val; }
    bool operator>=(const ModInt& b) const { return val >= b.val; }

    // I/O
    friend std::istream& operator>>(std::istream& is, ModInt& x) noexcept {
        lint v;
        is >> v;
        x = v;
        return is;
    }
    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) noexcept { return os << x.val; }
};

constexpr int MOD = 1000000007;
using mint = ModInt<MOD>;

using lint = long long;

mint binom(lint n, lint m) {
    mint ret = 1;
    for (int i = 1; i <= m; ++i) {
        ret *= n - i + 1;
        ret /= i;
    }
    return ret;
}

bool solve() {
    int n, m;
    lint d;
    std::cin >> n >> d >> m;
    if (n == 0) return false;

    std::vector<mint> dp(n + 1, 0);
    dp[0] = 1;
    std::vector<mint> sum(n + 1, 0);

    mint ans = 0;
    for (int i = 1; i <= n; ++i) {
        sum[0] = 0;
        for (int j = 0; j < n; ++j) {
            sum[j + 1] = sum[j] + dp[j];
        }

        dp[0] = 0;
        for (int j = 1; j <= n; ++j) {
            dp[j] = sum[j] - sum[std::max(0, j - m + 1)];
        }

        ans += dp[n] * binom(d, i);
    }

    std::cout << ans << "\n";
    return true;
}

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

    while (solve()) {}

    return 0;
}



Measured memory_bytes: 3040
#include <stdio.h>
#include <string.h>
int main(void)
{
int a,b;
int x=0;
char s[6];

int i;
scanf("%d%d",&a,&b);
for(i=a;i<=b;i++){
	
	sprintf(s,"%d",i);
	if(s[0]==s[4]&&s[1]==s[3]){
		
		x++;
	}
	
	
	
	
	
}
printf("%d\n",x);
	return 0;
}

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

const int maxn = 2e5 + 10;
typedef long long int ll;
void solved(){
	int h1,h2,m1,m2,k;cin>>h1>>m1>>h2>>m2>>k;
	int len = (h2 - h1) * 60 + (m2 - m1);
	if(len > k){
		cout<<len - k<<endl;
	}else{
		cout<<"0"<<endl;
	}
}
int main(){
	solved();
	return 0;
}

Measured memory_bytes: 3632
#include <stdio.h>
 
int main()
{
  int a,b;
  scanf("%d%d",&a,&b);
  if (a == 1 || b == 1)
  {
    if (a == 1 && b != 1)
      printf("Alice");
    else if (a != 1 && b == 1)
      printf("Bob");
    else
      printf("Draw");
    return (0);
  }
  if (a > b)
    printf("Alice");
  else if (b > a)
    printf("Bob");
  else
    printf("Draw");
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define ll  long long int
#define ull unsigned long long 
#define ff first
#define ss second
#define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define pb push_back 
#define mp make_pair
#define inf 1000000000000000
#define mod 1000000007
#define ld long double
#define pll pair<ll,ll>
using namespace std;
#define use 1000000
vector<ll> fact(use,1),ifact(use,1);
ll bin_exp_mod(ll a, ll b,ll m)
{
    a%=m;
    ll ans=1;
    if(a==0) ans=0;

    while(b>0)
    {
        if(b&1) ans=(ans*a)%m;
        a=(a*a)%m;
        b>>=1;
    }
    return ans;
}

ll ncr(ll n,ll r)
{
    if(r>n)return 0;

    return fact[n]*ifact[r]%mod*ifact[n-r]%mod;
}


int main()
{ 
    
fast;

for(ll i=2;i<use;i++)
{
    fact[i]=fact[i-1]*i%mod;
    ifact[i]=bin_exp_mod(fact[i],mod-2,mod);
}

ll n,m;
cin>>n>>m;

ll ans=ncr(m,n)*fact[n]%mod;

ll cur=0;
ll sign=1;

for(ll i=0;i<=n;i++)
{
    ll x=ncr(n,i)*ncr(m-i,n-i)%mod*fact[n-i]%mod;
    x*=sign;
    cur=(cur+x+mod)%mod;
    sign=-sign;
}

ans=ans*cur%mod;
cout<<ans;

}


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

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

    if(S.at(K-1)=='A') S.at(K-1)='a';
    if(S.at(K-1)=='B') S.at(K-1)='b';
    if(S.at(K-1)=='C') S.at(K-1)='c';
    cout<<S<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#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() {
  int N;
  cin>>N;
  
  vector<ll>A(N);
  for(int i=0;i<N;i++)cin>>A[i];
  
   long long int ans=1;
  
  //sort(A.begin(),A.end());
  for(int i=0;i<N;i++){
    if(A[i]==0){
      ans=0;
      cout<<ans<<endl;
      return 0;
    }
  }
  
  long long int lim=(long long int)1e18;
  for(int i=0;i<N;i++){
    //int nextlen=log10(A[i]);
    if(ans>lim/(ll)A[i]){
      ans=-1;
      cout<<ans<<endl;
      return 0;
    }else{
    	ans*=A[i];
    }
    
  }
  
  cout<<ans<<endl;

}

Measured memory_bytes: 4020
N = int(input())
t = [0]*(N+1)
x = [0]*(N+1)
y = [0]*(N+1)
dt = [0]*N
dist = [0]*N
for i in range(1,N+1):
    t[i], x[i], y[i] = map(int, input().rstrip().split())

for j in range(1,N+1):
    dt[j-1] = t[j] - t[j-1]
    dist[j-1] = abs(x[j] - x[j-1]) + abs(y[j] - y[j-1])

Flag = "OK"
for k in range(N):
    if dt[k] < dist[k]:
        Flag = "NG"
    else:
        if (dt[k]-dist[k]) % 2 != 0:
            Flag = "NG"

if Flag == "OK":
    print("Yes")
else:
    print("No")

Measured memory_bytes: 48856
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin>>n;
	vector<int> v[n];
	int i;	
	int ans=0;
	int k=1;
	for(i=0;i<n;i++)
	{
		int x;
		cin>>x;           
		if(x!=k)
			ans++;
		else
			k++;
	}          
	cout<<(ans!=n ? ans : -1);
}


Measured memory_bytes: 4992
#include <iostream>
#include <stack>
#include <unordered_map>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <functional>
#include <iterator>
#include <tuple>

using namespace std;

int main() {
  int n;
  cin >> n;
  
  int result = 0;
  int old_b;
  for (int i = 0; i < n-1; i++) {
    int b;
    cin >> b;
    
    if (i == 0) {
      old_b = b;
    }
    
    result += min(old_b, b);
    if (i==n-2) {
      result += b;
    }
    
    old_b = b;
  }
  
  
  cout << result << endl;
  
  
}

Measured memory_bytes: 256
#include <stdio.h>

void merge(int*, int, int, int);
void mergeSort(int*, int, int);

int count=0;

int main(){
    int n,i,S[500000];

    scanf("%d",&n);

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

    mergeSort(S,0,n);

    for(i=0;i<n-1;i++) printf("%d ",S[i]);
    printf("%d\n",S[i]);

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

    return 0;
}

void merge(int *A, int left, int mid, int right){
    int i,j,k;
    int n1=mid-left;
    int n2=right-mid;
    int L[n1+1];
    int R[n2+1];

    for(i=0;i<n1;i++)   L[i]=A[left+i];
    for(i=0;i<n2;i++)   R[i]=A[mid+i];

    L[n1]=1000000001;
    R[n2]=1000000001;
    i=0;
    j=0;

    for(k=left;k<right;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i++;
        }else{
            A[k]=R[j];
            j++;
        }
        count++;
    }
}

void mergeSort(int *A, int left, int right){
    int mid;

    if(left+1<right){
        mid=(left+right)/2;
        mergeSort(A,left,mid);
        mergeSort(A,mid,right);
        merge(A,left,mid,right);
    }

}


Measured memory_bytes: 5760
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
   ll x;
   cin>>x;
   ll ans = 0;
   ans = (x/500)*1000;
   x -= (x/500)*500;
   ans += (x/5)*5;
   cout<<ans<<endl;
}


Measured memory_bytes: 256
import java.util.*;
public class Main
{
	public static void main(String arg[])
	{
		Scanner in=new Scanner(System.in);
		int n=in.nextInt();
		while(n-->0)
		{
			char ch[]=in.next().toCharArray();
			for(int i=0;i<ch.length;i++)
			{
				int c=0;
				if(ch[i]=='1')
				{
					while(ch[i]=='1')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{

						if(c%5==1)
							System.out.print(".");
						else if(c%5==2)
							System.out.print(",");
						else	if(c%5==3)
							System.out.print("!");
						else	if(c%5==4)
							System.out.print("?");
						else	if(c%5==0)
							System.out.print(" ");
					}
				}
				else if(ch[i]=='2')
				{
					while(ch[i]=='2')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%3==1)
							System.out.print("a");
						else if(c%3==2)
							System.out.print("b");
						else	if(c%3==0)
							System.out.print("c");
					}
				}
				else if(ch[i]=='3')
				{
					while(ch[i]=='3')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%3==1)
							System.out.print("d");
						else if(c%3==2)
							System.out.print("e");
						else	if(c%3==0)
							System.out.print("f");
					}
				}
				else if(ch[i]=='4')
				{
					while(ch[i]=='4')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%3==1)
							System.out.print("g");
						else if(c%3==2)
							System.out.print("h");
						else	if(c%3==0)
							System.out.print("i");
					}
				}
				else if(ch[i]=='5')
				{
					while(ch[i]=='5')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%3==1)
							System.out.print("j");
						else if(c%3==2)
							System.out.print("k");
						else	if(c%3==0)
							System.out.print("l");
					}
				}
				else if(ch[i]=='6')
				{
					while(ch[i]=='6')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%3==1)
							System.out.print("m");
						else if(c%3==2)
							System.out.print("n");
						else	if(c%3==0)
							System.out.print("o");
					}
				}
				else if(ch[i]=='7')
				{
					while(ch[i]=='7')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%4==1)
							System.out.print("p");
						else if(c%4==2)
							System.out.print("q");
						else	if(c%4==3)
							System.out.print("r");
						else	if(c%4==0)
							System.out.print("s");

					}
				}
				else if(ch[i]=='8')
				{
					while(ch[i]=='8')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%3==1)
							System.out.print("t");
						else if(c%3==2)
							System.out.print("u");
						else	if(c%3==0)
							System.out.print("v");
					}
				}
				else if(ch[i]=='9')
				{
					while(ch[i]=='9')
					{
						c++;
						i++;
					}
					if(ch[i]=='0')
					{
						if(c%4==1)
							System.out.print("w");
						else if(c%4==2)
							System.out.print("x");
						else	if(c%4==3)
							System.out.print("y");
						else	if(c%4==0)
							System.out.print("z");
					}
				}
			}
			System.out.println();
		}
	}
}

Measured memory_bytes: 12000
#include <cstring>
#include <sstream>
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <unordered_map>
#include <cmath>
#include <queue>
#include <set>
#include <numeric>
#include <stack>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define repr(i, n) for(ll i = n - 1; i >= 0; i--)
#define repone(i, n) for(ll i = 1; i <= (ll)(n); i++)
#define each(i, mp) for(auto i:mp)
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ll mod = 1000000007;
const ll inf = ll(1e9);
const ll half_inf = ll(1e5);
const ll ll_inf = ll(1e9) * ll(1e9);
typedef unordered_map<ll, ll> ump;
typedef pair<ll, ll> P;

ump mp;

int main() {
#ifdef MY_DEBUG
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wmissing-noreturn"
    while (true) {
        mp = ump();
#pragma clang diagnostic pop
#endif
        ll n;
        cin >> n;
        if (n % 2 == 0) {
            ll ans = 0;
            repone(i, n) {
                ans += n - i;
            }
            ans -= n / 2;
            cout << ans << endl;
            repone(i, n) {
                for (int j = i; j <= n; ++j) {
                    if (i != j && i + j != n + 1) printf("%lli %lli\n", i, j);
                }
            }
        } else {
            ll ans = 0;
            repone(i, n) {
                ans += n - i;
            }
            ans -= n / 2;
            cout << ans << endl;
            repone(i, n) {
                for (int j = i; j <= n; ++j) {
                    if (i == n && i != j) printf("%lli %lli\n", i, j);
                    else if (i != j && i + j != n) printf("%lli %lli\n", i, j);
                }
            }
        }


#ifdef MY_DEBUG
    }
#endif
    return 0;
}

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

long long n;
vector<int> edge[100005];
bool ch[100005] = {0};
long long dp[100005][2] = {0};

long long solve(int x);

int main() {
  cin >> n;
  for(int i = 0; i < n - 1; ++i) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    edge[x].push_back(y);
    edge[y].push_back(x);
  }
  cout << solve(0) << endl;
  return 0;
}

long long solve(int x) {
  ch[x] = 1;
  long long b = 1, w = 1;
  for(int i = 0; i < edge[x].size(); ++i) {
    if(!ch[edge[x][i]]) solve(edge[x][i]);
    if(dp[edge[x][i]][0] == 0) continue;
    b *= dp[edge[x][i]][1];
    b %= N;
    w *= (dp[edge[x][i]][0] + dp[edge[x][i]][1]) % N;
    w %= N;
  }
  dp[x][0] = b;
  dp[x][1] = w;
  return (dp[0][0] + dp[0][1]) % N;
}

Measured memory_bytes: 14336
#coding: utf-8

tfr = ((1, 2, 4, 3), (0, 3, 5, 2), (0, 1, 5, 4),
(0, 4, 5, 1), (0, 2, 5, 3), (1, 3, 4, 2))

label = list(map(int, input().split()))
q = int(input())
for i in range(q):
    t, f = map(int, input().split())
    idxt = label.index(t)
    idxf = label.index(f)
    idxr = tfr[idxt].index(idxf) + 1
    if idxr == 4:
        idxr = 0
    print(label[tfr[idxt][idxr]])


Measured memory_bytes: 5600
def aho(x):
    if x % 3 == 0:
        return True
    while x:
        if x % 10 == 3:
            return True
        x //= 10
    return False

n = int(input())
for i in range(1, n + 1):
    if aho(i):
        print(' ', i, sep='', end='')
print()




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

//const int maxn=1e5+5;
char s[105];
int main()
{
    scanf("%s",s+1);
    int m=strlen(s+1);
    for(int i=1;i<=m;i++)
    {//L, U, or D
        if(((i&1)&&(s[i]=='R'||s[i]=='U'||s[i]=='D'))||((i%2==0)&&(s[i]=='L'||s[i]=='U'||s[i]=='D')))
            continue;
        else
        {
            printf("No");
            return 0;
        }
    }
    printf("Yes");
    return 0;
}


Measured memory_bytes: 256
def gcd(a,b):
    while a%b!=0:
        a,b=b,a%b
    return b

a,b,k=map(int,input().split(" "))
g=gcd(a,b)
if k==1:
    print(g)
else:
    cnt = 1
    for n in range(2,g+1):
        if g%n==0:
            cnt+=1
            if cnt==k:
                print(int(g/n))
                break

Measured memory_bytes: 3064
#include<stdio.h>
int main(void)
{
  int a,b;
  scanf("%d%d",&a,&b);
  if((a+b)%2)
    {
      printf("%d\n",(a+b)/2+1);
    }
  else
    {
      printf("%d\n",(a+b)/2);
    }
  return 0;
}

Measured memory_bytes: 128
import itertools
N, T = map(int, input().split())
CT = list(map(lambda _ :list(map(int, input().split())), range(N)))
if min(CT ,key = (lambda ct:ct[1]))[1] > T:
    print('TLE')
else:
    print(min(filter(lambda ct: ct[1]<=T, CT), key=(lambda ct: ct[0]))[0])


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

#define int long long

#define rep(i,s,n) for(int i = s;i<n;i++)
#define repe(i,s,n) for(int i = s;i<=n;i++)
#define rrep(i,s,n) for(int i = (n)-1;i>=(s);i--)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define fi first
#define se second
#define chmin(a,b) a=min((a),(b))
#define chmax(a,b) a=max((a),(b))
typedef long long ll;
typedef pair<int,int>pint;
typedef vector<int>vint;
typedef vector<pint>vpint;
typedef pair<pint,int> P1;
typedef pair<int,pint> P2;
typedef pair<pint,pint> PP;
static const ll maxLL = (ll)1 << 62;
const ll MOD=1000000007;
const ll INF=1e18;

int N;
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

signed main() {
    std::cin >> N;
    auto v=prime_factorize(N);
    cout<<N<<":";
    rep(i,0,v.size()){
        rep(j,0,v[i].se)cout<<" "<<v[i].fi;
    }
    cout<<endl;

    return 0;
}



Measured memory_bytes: 3124
n,k = map(int,input().split())
*a, = map(int,input().split())
mod = 10**9+7

mae=0
ato=0
ans=0
sum = (k*(k-1))//2
for i in range(n):
    mae, ato = 0, 0
    for j in range(n):
        if a[i]>a[j]:
            if i<j:
                ato+=1
            else:
                mae+=1
    ans += (sum)*(mae+ato) + (ato*k)
    ans%=mod

print(ans)

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (ll i=0; i<(n); ++i)
typedef long long ll;
bool debug=false;
int main(){
  ll a,b; cin >> a >> b;
  cout << max(a+b, max(a-b,a*b));
  return 0;
}


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

int main(void) {
  int N;
  cin >> N;
  int X[MAX_N];
  int Y[MAX_N];
  int H[MAX_N];
  int BX, BY, BH;
  rep(i, N) {
    cin >> X[i] >> Y[i] >> H[i];
    if (H[i] != 0) {
      BX = X[i];
      BY = Y[i];
      BH = H[i];
    }
  }

  for (int cx = 0; cx <= 100; cx++) {
    for (int cy = 0; cy <= 100; cy++) {
      int ch = BH + abs(BX - cx) + abs(BY - cy);
      bool flag = true;
      rep(i, N) {
        int th = max(ch - abs(X[i] - cx) - abs(Y[i] - cy), 0);
        if (H[i] != th) {
          flag = false;
          break;
        }
      }
      if (flag) {
        cout << cx << " " << cy << " " << ch << endl;
        return 0;
      }
    }
  }
  return 0;
}


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

#define FOR(i, a, b) for(int i=(a); i<(b); i++)
#define RFOR(i, a, b) for(int i=(a); i>=(b); i--)
#define rep(i, n) FOR(i, 0, n)
#define rrep(i, n) RFOR(i, n, 0)
#define dump(x)  cout << #x << " = " << (x) << endl;

typedef long long ll;
typedef pair<int, int> ii;
const int mod = 1e9+7;
const ll INF = 1e18;
const int inf = 1e9;

void solve()
{
  int n,k; cin>>n>>k;
  vector<int> l(n, 0);
  rep(i,n) cin>>l[i];
  sort(l.rbegin(),l.rend());
  int ans=0;
  for (int i=0; i<k; i++) {
    ans+=l[i];
  }
  cout << ans << endl;
}

int main()
{
  solve();
  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <vector>

// Acknowledgement: Special thanks to kyomukyomupurin, who developed this
// template.
template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::pair<T, U>& p) {
  return os << '(' << p.first << ", " << p.second << ')';
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::vector<T>& vec) {
  int n = 0;
  for (auto e : vec) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::ostream& operator<<(std::ostream& os, const std::set<T>& st) {
  int n = 0;
  for (auto e : st) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T, class U>
std::ostream& operator<<(std::ostream& os, const std::map<T, U>& mp) {
  int n = 0;
  for (auto e : mp) os << (n++ ? ", " : "{") << e;
  return os << (n ? "}" : "{}");
}

template <class T>
std::istream& operator>>(std::istream& is, std::vector<T>& vec) {
  for (T& e : vec) is >> e;
  return is;
}

#ifdef LOCAL
#define debug(...) \
  std::cerr << "[" << #__VA_ARGS__ << "]: ", debug_out(__VA_ARGS__)
#else
#define debug(...)
#endif

void debug_out() { std::cerr << '\n'; }

template <class Head, class... Tail>
void debug_out(Head&& head, Tail&&... tail) {
  std::cerr << head;
  if (sizeof...(Tail) != 0) std::cerr << ", ";
  debug_out(std::forward<Tail>(tail)...);
}
using namespace std;
using int64 = long long;

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> c(m);
  cin >> c;
  vector<int> dp(n + 1, 1e8);
  dp[0] = 0;
  for (int i = 0; i < m; i++) {
    for (int j = c[i]; j < n + 1; j++) {
      dp[j] = min(dp[j], dp[j - c[i]] + 1);
    }
  }
  debug(dp);
  cout << dp[n] << endl;
  return 0;
}


Measured memory_bytes: 3168
#include <cstdio>
#include <cstdint>
#include <cctype>
#include <cmath>
#include <algorithm>
#include <vector>
#include <utility>
#include <string>

int main() {
  size_t N, K;
  scanf("%zu %zu", &N, &K);

  double res = 0;
  for (size_t i = 1; i <= N; ++i) {
    size_t j = i;
    size_t k = 0;
    while (j < K) {
      j <<= 1;
      ++k;
    }
    res += pow(0.5, k) / N;
  }
  printf("%.12f\n", res);
}


Measured memory_bytes: 384
import sys
sys.setrecursionlimit(10**8)
input = lambda: sys.stdin.readline()[:-1]
n,q=map(int,input().split())
ab=[tuple(map(int,input().split())) for i in range(n-1)]
px=[tuple(map(int,input().split())) for i in range(q)]
# ab.sort(key=lambda tup:(tup[0],tup[1]))
visited=[0]*(n+1)
cnt=[0]*(n+1)
data=[[] for i in range(n+1)]

for i in ab:
	data[i[0]].append(i[1])
	data[i[1]].append(i[0])
for j in px:
	cnt[j[0]]+=j[1]

visited[1]=1
stack=[1]

while stack:
	v=stack.pop()
	for to in data[v]:
		if visited[to]:
			continue
		visited[to]=1
		cnt[to]+=cnt[v]
		stack.append(to)

	
print(*cnt[1:])

Measured memory_bytes: 95924
<?php
fscanf(STDIN, "%d %d", $n, $m);
for ($i = 0; $i < $m; $i++) {
	fscanf(STDIN, "%d %d", $a, $b);
	$e[$a][] = $b;
	$e[$b][] = $a;
}
$x = 0;
path(1, array(1=>1));
echo $x;

function path($p, $done) {
	global $n, $e, $x;
	$done[$p] = 1;
	if (count($done) == $n) {
		$x++;
	} elseif (isset($e[$p])) {
		foreach ($e[$p] as $q) {
			if (!isset($done[$q])) {
				path($q, $done);
			}
		}
	}
}

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

string S;

int main() {
    cin >> S;
    bool f = true;
    for (int i = 0; i < 3; i++) {
        if (S[i] == S[i+1]) f = false;
    }

    if (f) cout << "Good" << endl;
    else cout << "Bad" << endl;
    
    return 0;
}


Measured memory_bytes: 256
//AtCoder DP D

//AnkitCode99 here....
//every ups and downs matter!

#include<bits/stdc++.h>
#define endl "\n"
#define Ryuga ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr)
typedef long long int ll;
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define pb push_back

using namespace std;

const ll sz=1e5+5;
const ll szz=1e6+6;
const ll mod=1e9+7;

ll n,w,wt[105],v[105],dp[105][sz];

ll knapsack(ll idx,ll W)
{
	if(W<0)
		return -1e16;

	if(idx==n)
		return 0;

	if(dp[idx][W]!=-1)
		return dp[idx][W];

	return dp[idx][W]=max(v[idx]+knapsack(idx+1,W-wt[idx]),knapsack(idx+1,W));
}

int main()
{
	Ryuga;

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

	clock_t startTime=clock();

	cin>>n>>w;
	memset(dp,-1,sizeof dp);
	rep(i,0,n)
	{
		cin>>wt[i]>>v[i];
	}

	cout<<knapsack(0,w);

	cerr << endl <<setprecision(20)<< double( clock() - startTime ) / (double)CLOCKS_PER_SEC<< " seconds." << endl;

}//Goodbye...

Measured memory_bytes: 85800
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder_20190707_1
{
    class Program
    {
        static void Main(string[] args)
        {
            char[] S = Console.ReadLine().ToCharArray();

            char[] reverseS = S.Reverse().ToArray();

            int count = 0;
   
            for(int i = 0; i < S.Length; i++)
            {
                if(S[i] != reverseS[i])
                {
                    count++;
                }
            }

            Console.Write(count / 2);
        }
    }
}


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

int main()
{
	while (1){


		int n, x;
		cin >> n >> x;
		if (n == 0 && x == 0) break;
		else{
			int s = 0;
			long l[10000][3];
			for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
			if (i + j + k == x && i != j && j != k && i != k){
				s++;
			}

			cout << s / 6 << endl;
		}
	}
	return 0;
}




Measured memory_bytes: 3080
#include<bits/stdc++.h>
using namespace std;
 
/*
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
 
typedef tree<int, null_type,
		less_equal<int>, 
		rb_tree_tag,tree_order_statistics_node_update> ordered_mset;
		
typedef tree<int, null_type,
		less<int>, 
		rb_tree_tag,tree_order_statistics_node_update> ordered_set;
*/
 
/*
 
PBDS
-------------------------------------------------
			0 based indexing
-------------------------------------------------			 
1) insert(value)
2) erase(value)
3) order_of_key(value) // Number of items strictly smaller than value
4) *find_by_order(k) : K-th element in a set (counting from zero)
 
*/
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
 
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());	

int n;
ll ara[3005];
ll dp[3005][3005][2];
bool flag[3005][3005][2];

ll f(int i,int j,int move)
{
	if(i>j) return 0;
	
	if(flag[i][j][move]) return dp[i][j][move];
	
	if(move)
	{
		ll a=f(i+1,j,move^1)-ara[i];
		ll b=f(i,j-1,move^1)-ara[j];
		
		flag[i][j][move]=1;
		return dp[i][j][move]=min(a,b);
	}
	
	else
	{
		ll a=f(i+1,j,move^1)+ara[i];
		ll b=f(i,j-1,move^1)+ara[j];
		
		flag[i][j][move]=1;
		return dp[i][j][move]=max(a,b);
	}
	
}

void solve()
{
	cin>>n;
	
	for(int i=0;i<n;i++) cin>>ara[i];
	
	cout<<f(0,n-1,0);
}
	
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	solve();
	
	cerr<<"\nTime elapsed: " << 1000.0 * clock() / CLOCKS_PER_SEC << " ms\n";
	
	return 0;
}


Measured memory_bytes: 158336
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ll_s long
#define mod 1000000007
#define forn(i,start,lim) for(ll i=start;i<lim;i++)
#define forn_d(i,start,lim) for(ll i=start;i>=lim;i--)
#define f first
#define s second
#define pb push_back
#define pf push_front
#define mp make_pair
#define debug1(a) cout<<"------\n"<<#a<<" = "<<a<<endl<<"------"<<endl
#define debug2(a,b) cout<<"--------------\n"<<#a<<" = "<<a<<" ; "<<#b<<" = "<<b<<endl<<"--------------"<<endl
#define debug3(a,b,c) cout<<"----------------------\n"<<#a<<" = "<<a<<" ; "<<#b<<" = "<<b<<" ; "<<#c<<" = "<<c<<endl<<"----------------------"<<endl
#define sz(a) (ll)(a.size())
#define debug4(a) cout<<"chu "<<a<<endl
#define endl "\n"

int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  ll n,W;
  cin>>n>>W;
  vector<ll> w(n),v(n);
  forn(i,0,n)
    cin>>w[i]>>v[i];
  vector<ll> dp(W+1), old_dp(W+1);
  forn(i,0,n){
    forn(weight,0,W+1){
      ll q1=0,q2=0;
      if(weight-w[i]>=0)
      q1 = old_dp[weight-w[i]]+v[i];
      q2 = old_dp[weight];
      dp[weight] = max(q1,q2);
    }
    old_dp=dp;
  }
  ll ans=dp[W];
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 4788
import sys

while True:
    n = int(sys.stdin.readline())

    if n == 0:
        break
    
    score_a = 0
    score_b = 0
    
    for i in range(n):
        a, b = map(int, sys.stdin.readline().strip().split())
        
        if a < b:
            score_b += b + a
        elif a > b:
            score_a += a + b
        else:
            score_a += a
            score_b += b
            
    print score_a, score_b

Measured memory_bytes: 4468
#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;

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

#define ll long long
#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#define sz size()
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ld long double
#define sqr(x) (x)*(x)
#define int ll

typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef pair < int, int > pii;
typedef vector < int >  vi;
typedef vector < vector < int> > vvi;
typedef pair < int, pair < int, int> > piii;
typedef vector < pair < int, int > > vpii;
typedef vector < ll >  vll;

bool valid(int x, int y, int n, int m){
    return x > 0 && x <= n && y > 0 && y <= m;
}

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

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

ld dist(ll x, ll y, ll x2, ll y2){
    return sqrt(sqr(x - x2) + sqr(y - y2));
}


void solve() {
    int n;
    cin >> n;
    vi a(n + 3);
    vi cnt(100100, 0);
    ll sum = 0;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        sum += a[i];
        cnt[a[i]]++;
    }
    int q;
    cin >> q;
    while(q--){
        int b, c;
        cin >> b >> c;
        int k = cnt[b];
        cnt[b] = 0;
        sum -= (k * b);
        sum += (k * c);
        cnt[c] += k;
        cout << sum << "\n";
    }
}

signed main() {
    fast_io;
    int t = 1;
    //cin >> t;
    while (t--) {
        solve();
    }
}





Measured memory_bytes: 4780
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;

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

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin >> n;
  ll ans = n * 10;
  for(auto p : divisor(n)) {
    ll q = n / p;
    ans = min(ans, p + q - 2);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"
using namespace std;
#ifdef _DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

//#define int long long
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(c) begin(c),end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return true; } return false; }

using Weight = int;
using Flow = int;
struct Edge {
	int s, d; Weight w; Flow c;
	Edge() {};
	Edge(int s, int d, Weight w = 1) : s(s), d(d), w(w), c(w) {};
};
bool operator<(const Edge &e1, const Edge &e2) { return e1.w < e2.w; }
bool operator>(const Edge &e1, const Edge &e2) { return e2 < e1; }
inline ostream &operator<<(ostream &os, const Edge &e) { return (os << '(' << e.s << ", " << e.d << ", " << e.w << ')'); }

using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

void add_arc(Graph &g, int s, int d, Weight w = 1) {
	g[s].emplace_back(s, d, w);
}
void add_edge(Graph &g, int a, int b, Weight w = 1) {
	add_arc(g, a, b, w);
	add_arc(g, b, a, w);
}

template<class T, class ...Tail>
void tied_sort(vector<T> &a, vector<Tail>&... tail) {
	int n = a.size();
	using S = tuple<T, Tail...>;
	vector<S> s(n);
	for (int i = 0; i < n; i++)
		s[i] = make_tuple(a[i], tail[i]...);
	sort(s.begin(), s.end());
	for (int i = 0; i < n; i++)
		tie(a[i], tail[i]...) = s[i];
}

signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N; cin >> N;
	if (N % 2) {
		cout << "First" << endl;
		return 0;
	}

	Graph g(N);
	rep(i, 0, N - 1) {
		int a, b; cin >> a >> b; a--, b--;
		add_edge(g, a, b);
	}
	vector<int> degree(N, 0);
	for (auto &es : g)for (auto &e : es) degree[e.d]++, degree[e.s]++;

	vector<int> idx(N);
	iota(all(idx), 0);

	tied_sort(degree, idx);
	reverse(all(degree));
	reverse(all(idx));

	dump(degree, idx);
	for (int i = 0; i < N; i++)
		degree[i] /= 2;


	using P = pair<int, int>;
	map<P, int> mp;

	vector<bool> vis(N);
	function<int(int, int)> dfs = [&](int u, int p) {
		if (vis[u])return 0;
		if (mp.count(P(u, p)))
			return mp[P(u, p)];
		vis[u] = true;
		int ret = 0;
		ret++;
		for (auto &e : g[u]) {
			if (vis[e.d])continue;
			ret += dfs(e.d, u);
		}
		return mp[P(u, p)] = ret;
	};



	for (int i = 0; i < N; i++) {
		if (degree[i] <= 2)break;
		vis.assign(N, false);
		vis[idx[i]] = true;
		int odd = 0;
		for (auto &e : g[idx[i]]) {
			int cnt = dfs(e.d, idx[i]);
			dump(e.d, cnt);
			if (cnt % 2)odd++;
		}
		dump(odd);
		if (odd >= 2) {
			cout << "First" << endl;
			return 0;
		}
	}
	dump(mp);
	cout << "Second" << endl;
	return 0;
}

Measured memory_bytes: 16752
import core.bitop;
import std.algorithm;
import std.ascii;
import std.bigint;
import std.conv;
import std.functional;
import std.math;
import std.numeric;
import std.range;
import std.stdio;
import std.string;
import std.random;
import std.typecons;
import std.container;

enum MAX = 1_000_100;
ulong MOD = 1_000_000_007;
ulong INF = 1_000_000_000_000;
alias sread = () => readln.chomp();
alias Pair = Tuple!(long, "a", long, "b");
alias PQueue(T, alias less = "a<b") = BinaryHeap!(Array!T, less);

void main()
{
    auto n = lread();
    if(n % 2)
    {
        writeln(0);
    }
    else
    {
        long five_cnt;
        n /= 2;
        while(n > 0)
        {
            n /= 5;
            five_cnt += n;
        }
        writeln(five_cnt);
    }
}

T lread(T = long)()
{
    return readln.chomp.to!T();
}

T[] aryread(T = long)()
{
    return readln.split.to!(T[])();
}

void scan(TList...)(ref TList Args)
{
    auto line = readln.split();
    foreach (i, T; TList)
    {
        T val = line[i].to!(T);
        Args[i] = val;
    }
}


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

// @@ !! LIM(f:gcd)
// --> f:gcd
// ---- inserted function gcd from util.cc
// g = eGCD(a, b, s, t)  --->  sa + tb = g
ll eGCD(ll a, ll b, ll& s, ll& t) {
  if (a == 0) {
    s = 0;
    t = 1;
    return b;
  }
  ll u = 0;
  ll g = eGCD(b % a, a, t, u);
  s = u - (b / a) * t;
  return g;
}

// gcd(0, x) = x, gcd(-x, y) = gcd(x, y)
ll gcd(ll a, ll b) {
  ll dummy1 = 0;
  ll dummy2 = 0;
  return eGCD(abs(a), abs(b), dummy1, dummy2);
}
// ---- end gcd
// @@ !! LIM  -- end mark --

int main(/* int argc, char *argv[] */) {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout << setprecision(20);

  ll N; cin >> N;
  ll cur;
  for (ll i = 0; i < N; i++) {
    ll t; cin >> t;
    if (i == 0) {
      cur = t;
    }else {
      ll g = gcd(cur, t);
      cur *= t / g;
    }
  }
  cout << cur << endl;

  return 0;
}



Measured memory_bytes: 3656
import itertools
import numpy as np

H, W, K = map(int, input().split())
C = np.array([[i for i in input()] for j in range(H)])
h = [i for i in range(H)]
w = [i for i in range(W)]
ans = 0
for i in range(1, H+1):
    h_list = list(itertools.combinations(h, i))
    for j in range(1, W+1):
        w_list = list(itertools.combinations(w, j))
        for k in h_list:
            for l in w_list:
                k = list(k)
                l = list(l)
                if len(k) == H:
                    c = C[:, l]
                    if np.sum(c == "#") == K:
                        ans += 1
                elif len(l) == W:
                    c = C[k, :]
                    if np.sum(c == "#") == K:
                        ans += 1
                else:
                    c = C[np.ix_(k, l)]
                    if np.sum(c == "#") == K:
                        ans += 1
print(ans)

Measured memory_bytes: 27240
/**
* Author :v-O_O-v
* Time: 17:28:01 13/06/2020 
**/
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream& operator<<(ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
typedef long long lint;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

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

    string s;
    cin >> s;
    cout << s.substr(0, 3) << '\n';
    return 0;
}
// Write Here


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

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll n;
    cin >> n;
    ll a[n+1], b[n];
    for(ll i = 0; i < n+1; ++i) cin >> a[i];

    ll res = 0;
    ll prev = a[0];
    ll zero = 0;
    for(ll i = 0; i < n; ++i){
        ll b;
        cin >> b;

        if(prev >= b){
            res += b;
            prev = a[i+1];
        }
        else {
            res += min(prev+a[i+1], b);
            prev = max(prev+a[i+1]-b, zero);
        }
    }
    cout << res << endl;
}

Measured memory_bytes: 1024
#include <cstdio>
#define MOD 1000000007
long long dp[100005], ans = 1;
int pre[100005], nxt[100005], in[100005], cnt[100005];
bool vis[100005];
int main()
{
	// freopen("AGC008-E.in", "r", stdin);
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", nxt + i);
		in[--nxt[i]]++;
	}
	for (int i = 0; i < n; i++)
	{
		if (in[i] > 2)
		{
			puts("0");
			return 0;
		}
		if (in[i] != 2 || vis[i])
			continue;
		int u = i;
		do
		{
			if (vis[u])
			{
				puts("0");
				return 0;
			}
			vis[u] = true;
			pre[nxt[u]] = u;
			u = nxt[u];
		}
		while (u != i);
	}
	for (int i = 0; i < n; i++)
	{
		if (in[i])
			continue;
		int u = i, link_len = 0, cyc_len = 0;
		while (!vis[u])
		{
			vis[u] = true;
			u = nxt[u];
			link_len++;
		}
		do
		{
			u = pre[u];
			cyc_len++;
		}
		while (in[u] == 1);
		if (link_len < cyc_len)
			ans = ans * 2 % MOD;
		else if (link_len > cyc_len)
		{
			puts("0");
			return 0;
		}
	}
	for (int i = 0; i < n; i++)
	{
		if (vis[i])
			continue;
		int u = i, len = 0;
		do
		{
			vis[u] = true;
			u = nxt[u];
			len++;
		}
		while (u != i);
		cnt[len]++;
	}
	for (int i = 1; i <= n; i++)
	{
		int coef = ((i & 1) && i != 1) + 1;
		dp[0] = 1;
		dp[1] = coef;
		for (int j = 2; j <= cnt[i]; j++)
			dp[j] = (dp[j - 2] * (j - 1) * i + dp[j - 1] * coef) % MOD;
		ans = ans * dp[cnt[i]] % MOD;
	}
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>  
using namespace std;
using ll = long long int;
#define rep(i,n) for(int i=0; i<(int)(n); i++)
using graph = vector<vector<char>>;

int main(){
  ll n,m; cin>>n;
  vector<ll> v(n);
  rep(i,n){cin>>v[i];}
  sort(v.begin(),v.end());
  
  cin>>m;
  vector<ll> vc(m);
  rep(i,m){cin>>vc[i];}
  sort(vc.begin(),vc.end());
  
  ll i=0;
  string  ans="YES";
  if(n<m){ans="NO";}
  else{
    rep(j,m){
      while(v[i]<vc[j]){i++;}
      if(v[i]==vc[j]){
        //cout<<i<<j<<endl;
        if(i==n-1&&j==m-1){break;}
        else{i++;continue;}}
      if(v[i]>vc[j]){ans="NO";break;}
      if(i==n-1&&j<m-1){ans="NO";break;}
    }
  }
  cout<<ans;
}



Measured memory_bytes: 3328
#include <bits/stdc++.h>
#include <algorithm>  
#include <unordered_set>
#include <cmath>
#define ll long long
using namespace std;

string n;

vector<int> pref;


bool isAllZero(int left, int right) {

	if (left > right) {
		return true;
	}

	ll sum = pref[right] - ((left == 0) ? 0 : pref[left - 1]);
	return sum == 0;
}

bool bad(int i, int j, int d1, int d2) {

	int nI = n[i] - '0';
	int nJ = n[j] - '0';

	return i == 0 && (d1 > nI ||
		(d1 == nI && isAllZero(i + 1, j - 1) && d2 > nJ));
}



bool bad(int i, int j, int k, int d1, int d2, int d3) {

	int nI = n[i] - '0';
	int nJ = n[j] - '0';
	int nK = n[k] - '0';

	return i == 0 && (d1 > nI ||
		(d1 == nI && isAllZero(i + 1, j - 1)
		&& (d2 > nJ || (d2 == nJ &&
			isAllZero(j + 1, k - 1) && d3 > nK))));
}


int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);



	ll k;

	cin >> n >> k;

	
	int len = n.size();
	
	vector<int> digits(len);

	for (int i = 0; i < len; i++) {
		digits[i] = n[i] - '0';
	}

	pref = vector<int>(len);
	pref[0] = digits[0];

	for (int i = 1; i < len; i++) {
		pref[i] = pref[i - 1] + digits[i];
	}

	ll ans = 0;

	if (k == 1) {
		ans = (len - 1) * 9 + int(n[0] - '0');
		cout << ans << endl;
	}
	else if (k == 2) {

		ans = 0;

		for (int i = 0; i < len; i++) {

			for (int j = i + 1; j < len; j++) {

				for (int d1 = 1; d1 <= 9; d1++) {

					for (int d2 = 1; d2 <= 9; d2++) {
						ans += !bad(i, j, d1, d2);
					}
				}
			}
		}

		cout << ans << endl;
	}
	else if (k == 3) {


		ans = 0;

		for (int i = 0; i < len; i++) {

			for (int j = i + 1; j < len; j++) {

				for (int k = j + 1; k < len; k++) {

					for (int d1 = 1; d1 <= 9; d1++) {

						for (int d2 = 1; d2 <= 9; d2++) {

							for (int d3 = 1; d3 <= 9; d3++) {

								ans += !bad(i, j, k, d1, d2, d3);
							}

						}
					}
				}
			}
		}

		cout << ans << endl;


	}











	return 0;
}

Measured memory_bytes: 3612
/*
* Note: This template uses some c++11 functions , so you have to compile it with c++11 flag.
*       Example:-   $ g++ -std=c++11 c++Template.cpp
*
* Author : Akshay Pratap Singh
* Handle: code_crack_01
*
*/
 
/********   All Required Header Files ********/
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

/*******  All Required define Pre-Processors and typedef Constants *******/
#define SCD(t) scanf("%d",&t)
#define SCLD(t) scanf("%ld",&t)
#define SCLLD(t) scanf("%lld",&t)
#define SCC(t) scanf("%c",&t)
#define SCS(t) scanf("%s",t)
#define SCF(t) scanf("%f",&t)
#define SCLF(t) scanf("%lf",&t)
#define MEM(a, b) memset(a, (b), sizeof(a))
#define FOR(i, j, k, in) for(int i=j ; i<k ; i+=in)
#define RFOR(i, j, k, in) for(int i=j ; i>=k ; i-=in)
#define REP(i, j) FOR(i, 0, j, 1)
#define RREP(i, j) RFOR(i, j, 0, 1)
#define all(cont) cont.begin(), cont.end()
#define rall(cont) cont.end(), cont.begin()
#define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
#define IN(A, B, C) assert( B <= A && A <= C)
#define MP make_pair
#define PB push_back
#define INF (int)1e9
#define EPS 1e-9
#define PI 3.1415926535897932384626433832795
#define MOD 1000000007
#define read(type) readInt<type>()
typedef long long int ll;
typedef unsigned long long int  ull;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<string> vs;
typedef vector<pii> vii;
typedef vector<ll> vll;
typedef vector<vi> vvi;

int main(){

  string s; cin >> s;

  bool a = false;
  bool b = false;
  bool c = false;

  REP(i, s.size()){

    if( s[i] == 'a' ) a = true;
    if( s[i] == 'b' ) b = true;
    if( s[i] == 'c' ) c = true;

  }

  if( a and b and c ) cout << "Yes" << endl;
  else cout << "No" << endl;

  return 0;

}


Measured memory_bytes: 768
#include<iostream>
#include<algorithm>
using namespace std;
void MatrixChain(int *p, int n, int **m, int **s)
{
	for (int i = 1;i <=n;i++)
		m[i][i] = 0;
	for (int r = 2;r <= n;r++)
	{
		for (int i = 1;i <= n - r + 1;i++)
		{
			int j = i + r - 1;
			m[i][j] = m[i + 1][j] + (p[i - 1] * p[i] * p[j]);
			s[i][j] = i;
			for (int k = i + 1;k < j;k++)
			{
				int t = m[i][k] + m[k + 1][j] + (p[i - 1] * p[k] * p[j]);
				if (t < m[i][j])
				{
					m[i][j] = t;
					s[i][j] = k;
				}
			}
		}
	}
}

void print(int i, int j, int **s)
{
	if (i == j)
		cout << "A" << i;
	else
	{
		cout << "(";
		print(i, s[i][j], s);
		print(s[i][j] + 1, j, s);
		cout << ")";
	}
}
int main()
{
	int n;
	cin >> n;
	int *tempP = new int[2 * n]; 
	int *p = new int[n + 1];   
	int **m = new int *[n + 1]; 
	int **s = new int *[n + 1]; 
	for (int i = 1; i <= n; i++)
	{
		m[i] = new int[n + 1];
		s[i] = new int[n + 1];
	}

	for (int i = 0; i < 2 * n; i++)
	{
		cin >> tempP[i];
	}

	for (int i = 0; i <= n; i++)
	{
		p[i] = (i == 0 ? tempP[0] : tempP[i * 2 - 1]);
	}
	MatrixChain(p, n, m, s);
	cout << m[1][n] << endl; 
	return 0;
}


Measured memory_bytes: 3148
#include<stdio.h>

int main()
{
	int n, A[101], B[101];
	scanf("%d", &n);
	int i;
	for (i = 0; i <= n - 1 ; i++)
	{
		scanf("%d", &A[i]);
	}
	int j;
	for (j = 0; j <= n - 2; j++)
	{
		B[j] = A[n - 1 - j];
	}
	B[n - 1] = A[0];
	for (j = 0; j <= n - 2; j++)
	{
		printf("%d ", B[j]);
	}
	printf("%d\n", B[n - 1]);
}

Measured memory_bytes: 1024