akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<map>
#include<vector>
#include<cmath>
#include<string>
#include <algorithm> 
using namespace std;

# define p(s) std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;

# define INF (int)10e9

int main()
{

    int n,m;cin >> n >> m;

    int x[100000];
    for(int i=0;i<m;i++){
        cin >> x[i];
    }

    if(n>=m) {
        p(0)
        return 0;
    }

    sort(x,x+m);

    int l[100000];
    for(int i=0;i<m-1;i++){
        l[i]=x[i+1]-x[i];
    }
    sort(l,l+(m-1),greater<>());

    int sum=0;
    for(int i=0;i<n-1;i++){
        sum += l[i];
    }

    p(x[m-1]-x[0]-sum)
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
int main()
{
	string s;
	cin>>s;
	long long i=0,sum=0;
	while(i<s.size())
	{
		sum=sum+(s[i]-'0');
		i++;
	}
	if(sum%9==0)
		cout<<"Yes";
	else
		cout<<"No";
}


Measured memory_bytes: 3728
import sys
input = sys.stdin.readline
from collections import defaultdict

def main():
    N = int(input())
    S = defaultdict(int)
    for _ in range(N):
        S[input().rstrip("\n")] += 1
    S = sorted(S.items(), key=lambda x:x[1])

    ans = []
    cnt = S[-1][1]
    for i in range(len(S)-1, -1, -1):
        if cnt == S[i][1]:
            ans.append(S[i][0])
        else:
            break

    ans.sort()
    for x in ans:
        print(x)

if __name__ == "__main__":
    main()

Measured memory_bytes: 43484
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FOR(i, s, n) for (int i = (s); i < (n); i++)
#define RFOR(i, s, n) for (int i = (n) - 1; i >= (s); i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define ALL(a) a.begin(), a.end()
const long long MOD = 1e9+7, INF = 1e18;
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;}

vector<vector<int> > calcNext(const string &S) {
    int n = (int)S.size();
    vector<vector<int> > res(n+1, vector<int>(26, n));
    for (int i = n-1; i >= 0; --i) {
        for (int j = 0; j < 26; ++j) res[i][j] = res[i+1][j];
        res[i][S[i]-'a'] = i;
    }
    return res;
}

signed main(){
	string s,t;
	cin>>s>>t;
	int now = 0;
	int loop = 0;
	int N = s.size();
	auto nex = calcNext(s);
	REP(i,t.size()){
		now = nex[now][t[i]-'a']+1;
		if(now==s.size()+1){
			loop++;
			now = nex[0][t[i]-'a']+1;
			if(now==s.size()+1){
				cout<<-1<<endl;
				return 0;
			}
		}
	}
	cout<<loop*N+now<<endl;
}


Measured memory_bytes: 24704
#include <iostream>
#include <cstdio>
#include <stdio.h>
using namespace std;
int main(){
	int w,n;
	int a,b,c;
	cin>>w;
	cin>>n;
	int num[30] = {0};
	for(int i=-0;i<w;i++){
		num[i] = i+1;
	}
	for(int j=0;j<n;j++){
		scanf("%d,%d",&a,&b);
		c = num[a-1];
		num[a-1] = num[b-1];
		num[b-1] = c;
	}
	for(int k=0;k<w;k++){
		printf("%d\n",num[k]);
	}

	return 0;
}

Measured memory_bytes: 1224
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
#define sayyes cout<<"Yes"<<endl;
#define sayno cout<<"No"<<endl;
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int mod =1e9+7;

struct mint
{
    ll x;
    //constructor
    mint(ll y=0):x((y%mod+mod)%mod){}

    
    mint operator-() const{return mint(-x);}

    mint& operator+=(const mint a)
    {
        if((x+=a.x)>=mod) x-=mod;
        return *this;
    }

    mint& operator-=(const mint a)
    {
        if((x+=mod-a.x)>=mod)x-=mod;
        return *this;
    }

    mint& operator*=(const mint a)
    {
        (x*=a.x)%=mod;
        return *this;
    }

    mint operator+(const mint a)const{
        mint res(*this);
        return res+=a;
    }

    mint operator-(const mint a)const
    {
        mint res(*this);
        return res-=a;
    }

    mint operator*(const mint a)const
    {
        mint res(*this);
        return res*=a;
    }

    mint pow(ll t)const{
        if(t==0)return 1;
        mint a=pow(t/2);
        a*=a;
        if(t%2==1)a*=2;
        return a;
    }

    mint inv() const{
        return pow(mod-2);
    }

    mint& operator/=(const mint a)
    {
        return (*this)*=a.inv();
    }

    mint operator/(const mint a)const{
        mint res(*this);
        return res/=a;
    }

};

mint choose(int n, int a)
{
    mint x=1,y=1;
    rep(i,a)
    {
        x*=n-i;
        y*=i+1;
    }
    return x/y;
}

int main()
{
    ll n;
    ll k;
    cin>>n>>k;
    vector<int> a(n);
    rep(i,n)
    {
        cin>>a[i];
    }
    ll back=0;
    ll front=0;
    rep(i,n-1)
    {
        for(int j=i+1;j<n;j++)
        {
            if(a[i]>a[j])back++;
            else if(a[i]<a[j])front++;
        }
        
    }
    ll temp=k*(k+1)/2%mod;
    ll temp2=k*(k-1)/2%mod;
    ll backall=back*temp%mod;
    ll frontall=front*temp2%mod;
    mint ans=(backall+frontall);
    cout<<ans.x;
}

Measured memory_bytes: 256
#!/usr/bin/env python
# -*- coding: utf-8 -*-
#
# FileName: 	B
# CreatedDate:  2020-07-29 14:22:57 +0900
# LastModified: 2020-07-29 14:45:16 +0900
#


import os
import sys
# import numpy as np
# import pandas as pd


def main():
    R, G, B, N = map(int, input().split())
    r_max = N//R
    g_max = N//G
    b_max = N//B
    cnt = 0
    for r in range(r_max+1):
        ans = r*R
        for g in range((N-r*R)//G+1):
            ans += g*G
            if (N-ans)%B==0:
                cnt += 1
            ans = r*R
    print(cnt)





if __name__ == "__main__":
    main()


Measured memory_bytes: 9192
#include <iostream>
using namespace std;
int main(void)
{
	int K;
	cin >> K;
	int count=0;
	for (int i = 1; i <= K; i = i + 2) {
		for (int j = 2; j <= K; j = j + 2) {
			count++;
		}
	}
	cout << count << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <cctype>
#define len length()
#define sz size()
#define rng(i, a, b) for(int i = a; i < b; i++)
#define rep(i, n) rng(i, 0, n)
#define srt(v) sort(v.begin(), v.end())
#define rev(s) reverse(s.begin(), s.end())
#define vi(a, n) vector<int> a(n)
#define vs(a, n) vector<string> a(n)
#define vc(a, n) vector<char> a(n)
#define psb(a) push_back(a)
#define ppb pop_back()
#define erc(S, i) S.erase(S.begin() + i)
#define ers(S, i, j) S.erase(S.begin() + i, S.begin() + j)
#define sp(n) cout << setprecision(n) << fixed
#define fst(s) s.at(0)
#define lst(s) s.at(s.len - 1)
using namespace std;

int main(){
    int N;
    cin >> N;
    vi(L,2*N);
    rep(i,2*N) cin >> L[i];
    srt(L);
    int ans=0;
    rep(i,N) ans += L[2*i];
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,k,a[301000],g;
int main(){
	cin>>k>>n;
	if (k&1){
		for (int i=1;i<=n;++i) a[g=i]=k/2+1;
		for (int t=n/2;t--;){
			if (--a[g]){
				for (int j=n-g;j--;) a[++g]=k;
			}else{
				--g;
			}
		}
		for (int i=1;i<=g;++i) printf("%d ",a[i]);
	}else{
		cout<<k/2;
		for (int t=n;--t;) printf(" %d",k);
	}
}

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

#define speed ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL);
#define ub(a,x) upper_bound(a.begin(),a.end(),x)-a.begin()
#define lb(a,x) lower_bound(a.begin(),a.end(),x)-a.begin()
#define ll long long
#define endl "\n"
#define all(v) v.begin(),v.end()
#define ff first
#define ss second
#define pb push_back
#define PI 3.1415926535897932384626
#define inf 1e18
#define forn(i, n) for (int i = 0; i < int(n); i++)
int main()
{
    speed;
    ll n;
    cin>>n;
    ll a[n],b[n];
    ll ctr=0;
    forn(i,n)
    {
        cin>>a[i];
        b[i]=a[i];
    }
    sort(a,a+n);
    forn(i,n)
    {
        if(a[i]!=b[i])
            ++ctr;
    }

    if(ctr>2)
        cout<<"NO"<<endl;
    else
        cout<<"YES"<<endl;
    return 0;
}




Measured memory_bytes: 256
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int M = sc.nextInt();
        int N = sc.nextInt();
        int sum = 0;

        for (int i = 0; i < N; i++) {
            sum += sc.nextInt();
        }

        if (sum > M) {
            System.out.println(-1);
        } else {
            System.out.println(M - sum);
        }
    }
}


Measured memory_bytes: 46260
#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
 
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
 
using namespace std;
 
typedef long long int ll;

int main(){
    int N;
    ll C;
 
    cin >> N >> C;
 
    vector<ll> x(N+1), v(N+1), vc(N+1);
    x[0] = 0;
    v[0] = 0;
    FOR(i,1,N+1)cin >> x[i] >> v[i];
 
    //vの累積和を求める
    vc[0] = v[0];
    FOR(i,1,N+1){
        vc[i] = vc[i-1] + v[i];
    }
 
    vector<ll> r(N+1);
    r[0] = 0;
    for(int i = 1; i <= N; i++){
        r[i] = max(r[i-1], vc[i]-x[i]);
    }
 
    vector<ll> l(N+1);
    l[N] = vc[N] - vc[N-1] - (C-x[N]);
 
    for(int i = N-1; i >= 1; i--){
        l[i] = max(l[i+1], vc[N]-vc[i-1]-(C-x[i]));
    }
 
    ll ans = 0;
    REP(i,N+1){
        //ケース1
        ll tmp = vc[i] -  x[i];
        if(tmp > ans)ans = tmp ;
 
        //ケース2
        if(i < N){
            tmp = vc[i] - 2 * x[i] + l[i+1];
            if(tmp > ans)ans = tmp ;
        }
    }
 
    for(int i = N; i >= 1; i--){
        //ケース3
        ll tmp = vc[N] -  vc[i-1] - (C - x[i]);
        if(tmp > ans)ans = tmp ;
 
        //ケース4
        tmp = vc[N] - vc[i-1] - 2 * (C - x[i]) + r[i-1];
        if(tmp > ans)ans = tmp ;
    }
    cout << ans << endl;
}

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

typedef long long ll;


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

    int N, M;

    cin >> N >> M;

    vector<vector<int> > s(M, vector<int>(N));
    vector<int> p(M);

    for(int i = 0; i < M; i++) {
        int k;
        cin >> k;
        vector<int> x(k);
        for(int j = 0; j < k; j++) {
            cin >> x[j];
            x[j]--;
        }
        s[i] = x;
    }

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

    int count = 0;

    for (int bit = 0; bit < (1 << N); bit++) {
        vector<bool> S(N, false);
        for (int i = 0; i < N; ++i) {
            if (bit & (1 << i)) {
                S[i] = true;
            }
        }
        count++;
        for (int i = 0; i < M; i++) {
            int c = 0;
            for(int j = 0; j < s[i].size(); j++) {
                if(S[s[i][j]]) c++;
            }
            //cerr << "x " << c << endl;
            if(c % 2 != p[i]) {
              //  cerr << i << endl;
                count--;
                break;
            }
        }
    }

    cout << count << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<utility>
#include<queue>
#include<string>
#include<cmath>
#include<tuple>
#include<algorithm>
#define INF 1111111111
using namespace std;
typedef pair<int,int> P;
typedef tuple<int,int,int> tup;
typedef long long ll;
vector<int> vec(100100);
vector<int> passed(100100);
vector<int> dx = {-1,1};
int n,k;

int main() {
  int T;
  cin >> n >> T;
  int c = 1001;
  int a,b;
  for(int i=0;i<n; i++){
    cin >> a >> b;
      if(b <= T){
        if(a < c)
          c = a;
      }
  }
  if(c == 1001)
    cout << "TLE" << endl;
  else
    cout << c << endl;
  
}

Measured memory_bytes: 1024
#include<iostream>
using namespace std;
int main(){
    int n,m,aij,bi;
    int i,j;
    int vector1[256][256];
    int vector2[256];
    int ans[256]={};
    int sum = 0;

    cin>>n>>m;
    //input vector1
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            cin>>vector1[i][j];
        }
    }
    //input vector2
    for(j=0;j<m;j++){
        cin>>vector2[j];
    }

    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            ans[i] += vector1[i][j] * vector2[j];
        }
        cout<<ans[i]<<endl;
    }
    
    return 0;
}


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

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define sz(vs) (ll)(vs.size())
#define rep(i,a,b) for (ll i = a; i < b; ++i)
#define rep_(i,a,b) for (ll i = a; i > b; --i)
#define endl '\n'
const ll mod = 1e9 + 7;

const ll maxn = 1e5;

ll n, m;
ll a[maxn];
vi g[maxn];
string s;
char c;

// #include "debug.h"
void solve() {
	int s, t, d;
	cin >> d >> t >> s;
	cout << ((s * t >= d) ? "Yes" : "No") << endl;
}

void aux() {
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cout<<fixed<<setprecision(10);
	aux();
	ll _ = 1;
	// cin>>_;
	while(_--) {
		solve();
	}
	return 0;
}

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

signed main() {
    int N, A, B;
    cin >> N >> A >> B;
    vector<int> X(N);
    rep(i, N) cin >> X[i];
    
    int ans = 0;
    rep(i, N - 1) {
        int a = A * (X[i + 1] - X[i]);
        int b = B;
        ans += min(a, b);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>

main(){

  int i,j;
  int A[101];
  int len, tmp, count=0;

  scanf("%d",&len);

  for(i=1; i<=len; i++){
    scanf("%d",&A[i]);
  }

  for(i=1; i<=len-1; i++){

    for(j=len; j >=i+1; j--){

      if(A[j] < A[j-1]){
	tmp = A[j];
	A[j] = A[j-1];
	A[j-1] = tmp;
	count++;
      }

    }

  }
  for(i=1; i<=len; i++){
    printf("%d",A[i]);
    if(i!=len){
      printf(" ");
    }
  }
  printf("\n%d\n",count);

return 0;

}

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

using namespace std;
 
const long long inf = 1e18;
#define ll long long
#define fr(i,a,n) for (int i=a;i<n;i++)
#define rfr(i,n,a) for (int i=n;i>=a;i--)
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll> 
#define endl "\n"
typedef vector<int> VI;
typedef vector<ll> VL;

ll n,m,k;
VI adj[100001];
int dp[100001];

int dfs(int u) {
	if (dp[u] != -1)
		return dp[u];
	dp[u] = 1;
	for (auto v:adj[u]) {
		dp[u] = max(1 + dfs(v),dp[u]);
	}
	return dp[u];
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	memset(dp,-1,sizeof dp);
	fr(i,0,m) {
		int x,y;
		cin >> x >> y;
		adj[x].pb(y);
	}
	int ans = 0;
	for (int i = 1;i <= n;i++) {
		ans = max(dfs(i),ans);
	}
	cout << ans-1 << endl;
	return 0;
}

Measured memory_bytes: 7552
#include<stdio.h>

int main(){
   int x,x1,x2,x3,glad;
   scanf("%d",&x);
   x1=x/500;
   x2=x%500;
   x3=x2/5;
   glad=x1*1000+x3*5;
   printf("%d",glad);
   return 0;
}

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

int main(){
  int a,b,c,d;
  int x,y;
  cin >> a >>b >>c >>d;
  x = 0;
  y = 0;
  while(a>0){
    a=a-d;
    x=x+1;
  }
  while(c>0){
    c=c-b;
    y=y+1;
  }
  if(x>=y){
    cout << "Yes";
  }else{
  cout << "No";
  }  
}

Measured memory_bytes: 3596
#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <stdio.h>

int main(){
  int a,b;
  std::cin >> a >> b;
  if(b%a==0){
    std::cout << a+b;
  }else{
    std::cout << b-a;
  }
  return 0;
}

Measured memory_bytes: 3632
#define _GLIBCXX_DEBUG
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <utility>
#include <string>
#include <map>
#include <list>
using namespace std;
typedef long long ll;
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define mp make_pair
#define pb push_back
const int INF = 1e9;
const ll LINF = 1e18;
const int MOD = 1e9+7;

ll N, A, B;
vector<ll> h(100010, 0);

// n回爆発を起こした時全ての魔物を消すことは可能か
bool check(int n) {
	if (n == 0) return false;
	ll res = 0;

	// 全ての魔物の体力をBずつ減らし、魔物を一体選んでその体力をさらにA-B減らす
	// これをT回行うので、全ての魔物の体力をB*Tずつ減らし、その上でT回に渡って
	// 1体の魔物の体力をA-B減らすこと
	for (int i = 0; i < N; i++) {
		ll tmp = h[i] - B*n;
		if (tmp <= 0) continue;
		res += (tmp - 1) / (A-B) + 1;
	}

	if (res <= n) return true;
	else return false;
}

// 全ての魔物を倒すのに必要な爆発の最小の回数を探索する
ll solve() {
	ll left = 0, right = 1e9;
	ll mid;

	while (left+1 < right) {
		mid = (left + right) / 2;
		if (check(mid)) right = mid;
		else left = mid;
	}

	return right;
}

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

	for (int i = 0; i < N; i++) cin >> h[i];
	cout << solve() << endl;
    return 0;
}


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

#include <algorithm>
#include <cassert>
#include <cfloat>
#include <complex>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

using namespace std;

#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define rep(i, n) for (ll i = 0; i < (n); ++i)
#define repLRE(i, l, r) for (ll i = (l); i <= (r); ++i)
#define rrepLRE(i, l, r) for (ll i = (l); i >= (r); --i)
#define Sort(v) sort(v.begin(), v.end())
#define rSort(v) sort(v.rbegin(), v.rend())
#define Reverse(v) reverse(v.begin(), v.end())
#define Lower_bound(v, x) \
  distance(v.begin(), lower_bound(v.begin(), v.end(), x))
#define Upper_bound(v, x) \
  distance(v.begin(), upper_bound(v.begin(), v.end(), x))

using ll = long long;
using ull = unsigned long long;
using P = pair<ll, ll>;
using T = tuple<ll, ll, ll>;
using vll = vector<ll>;
using vP = vector<P>;
using vT = vector<T>;
using vvll = vector<vector<ll>>;
using vvP = vector<vector<P>>;
using dqll = deque<ll>;

ll dx[9] = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
ll dy[9] = {0, 0, -1, 1, -1, 1, -1, 1, 0};

/* Macros reg. ends here */

const ll INF = 1LL << 50;

int main() {
  // ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(15);

  ll n;
  cin >> n;
  vll as(n);
  rep(i, n) cin >> as[i];
  Reverse(as);

  ll m = 2, M = 2;
  rep(i, n) {
    //cout << m << " " << M << endl;
    ll a = as[i], nm, nM;
    nm = ((m + a - 1) / a) * a;
    nM = (M / a + 1) * a - 1;
    if (nm > M || nM < m) {
      cout << -1 << endl;
      return 0;
    }
    m = nm;
    M = nM;
  }
  cout << m << " " << M << endl;

  return 0;
}


Measured memory_bytes: 4032
import sys
import fractions
sys.setrecursionlimit(100000)
def lcm(x,y):
    return x//fractions.gcd(x,y)*y

n = int(input())
a = list(map(int,input().split()))
LCM=a[0]
for i in a:
  LCM = lcm(LCM,i)
ans=0
for i in a:
  ans += LCM//i
  
print(int(ans)%1000000007)


Measured memory_bytes: 6112
#include<cstdio>
int N,K,P,fac[210],ifac[210];
long long inv(int a,int p=P){return a==1?1:(1+p*(a-inv(p%a,a)))/a%p;}
int C(int n,int m){return m<0||m>n?0:1ll*fac[n]*ifac[m]%P*ifac[n-m]%P;}
int calc(int a,int b,int k){
	if(a>k+1||b>k)return 0;
	int x=a>k,s=0;
	for(int i=k+1,j=b;j<=a+b-x;i+=k*2+3-a-b,j+=k*2+3-a-b)s=((s+P-C(a+b-x,i))%P+C(a+b-x,j))%P;
	for(int i=a+b-k-2,j=a+b*2-k*2-3;i>=0;i-=k*2+3-a-b,j-=k*2+3-a-b)s=((s+P-C(a+b-x,i))%P+C(a+b-x,j))%P;
	if(a+b-1<=k)s=(s+P-1)%P;
	if(a+b<=k)s=(s+P-1)%P;
	return s;
}
int main(){
	scanf("%d%d%d",&N,&K,&P);
	for(int i=*fac=1;i<=N;i++)fac[i]=1ll*fac[i-1]*i%P;
	ifac[N]=inv(fac[N]);
	for(int i=N;i;i--)ifac[i-1]=1ll*ifac[i]*i%P;
	int s=K>=N-1?fac[N]:0;
	for(int i=0;i<=N-3&&K-i>=(N-i)/2;i++){
		int t=K<N-2?0:N-i-2;
		for(int j=1;j<=K-i&&j<N-i-1;j++)t=(t+calc(j,N-i-j-1,K-i))%P;
		s=(s+1ll*fac[N]*ifac[N-i]%P*fac[N-i-1]%P*t)%P;
	}
	printf("%d\n",s);
}

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

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;

int main() {
  int n; cin >> n;
  vector <ll> a(n);
  for(auto &x : a) cin >> x;
  reverse(a.begin(), a.end());
  ll sum = 0;
  ll ans = 0;
  for(int i = 0; i < n - 1; i++) {
    sum = (sum + a[i]) % MOD;
    ans = (ans + sum * a[i + 1] % MOD) % MOD;
  }
  cout << ans << '\n';
}


Measured memory_bytes: 4844
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define until(x) while(!(x))
#define unless(x) if(!(x))
#define all(x) (x).begin(),(x).end()

map<int,int> m;
int32_t main(){
	int n,tmp;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>tmp;
		m[tmp]++;
	}
	int ans = 0;
	for(auto x: m){
		if(x.first>x.second){
			ans += x.second;
		}
		else {
			ans += x.second-x.first;
		}
	}
	cout<<ans;
}


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

int main() {
  int a,b;
  cin >> a >> b;
  if (a + b == 4) {
    cout << 2 << endl;
  } else if (a + b == 3) {
    cout << 3 << endl;
  } else {
    cout << 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 256
N, M = [int(i) for i in input().split()]
a = sorted([list(map(int,input().split())) for _ in range(N)], key=lambda x:x[0])

total_m, total_c = 0, 0
for money, count in a:
    if total_c + count >= M:
        total_m += (M-total_c)*money
        break
    total_m += count*money
    total_c += count
print(total_m)

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

ll mod_pow(ll n, ll p, ll mod){
    if(p==0) return 1;
    ll res = mod_pow(n*n%mod, p/2, mod);
    if(p%2==1) res = res * n % mod;
    return res;
}

int main(){
    ll N, M, K;
    cin >> N >> M >> K;
    ll mod = 1e9+7;

    vector<ll> fct(N*M-1,1);
    for(ll i=1; i<=N*M-2; i++){
        fct[i] = i * fct[i-1] % mod;
    }

    vector<ll> invfct(N*M-1,1);
    invfct[N*M-2] = mod_pow(fct[N*M-2], mod-2, mod) % mod;
    for(ll i=N*M-3; i>=1; i--){
        invfct[i] = (i+1)*invfct[i+1] % mod;
    }

    ll W = (fct[N*M-2]*invfct[K-2] % mod)*invfct[N*M-K] % mod;

    ll ans = 0;
    for(ll dx=1; dx<M; dx++){
        ll A = (N*N*(M-dx)) % mod;
        ans = (ans + A * dx % mod) % mod;
    }
    for(ll dy=1; dy<N; dy++){
        ll A = (M*M*(N-dy)) % mod;
        ans = (ans + A * dy % mod) % mod;
    }
    cout << (ans*W)%mod << endl;
}


Measured memory_bytes: 3328
S = list(input())
direction = ["N", "W", "S", "E"]
cnt = [0] * 4

for s in S:
    for i in range(4):
        if s == direction[i]:
            cnt[i] += 1

f1 = False
f2 = False

if (cnt[0] > 0 and cnt[2] > 0) or (cnt[0] == 0 and cnt[2] == 0):
    f1 = True
if (cnt[1] > 0 and cnt[3] > 0) or (cnt[1] == 0 and cnt[3] == 0):
    f2 = True

if f1 and f2:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 45168
import numpy as np
from itertools import combinations_with_replacement

N,M,X = map(int,input().split())
CA = []
for i in range(N):
  CA.append(list(map(int,input().split())))

OK = True
CA = np.array(CA)
sums = np.sum(CA,axis=0)
for i in range(1,M+1):
  if sums[i] < X:
    OK = False
    break

if OK == False:
  print(-1)
else:
  # As = []
  # for A in combinations_with_replacement(range(0, N), r=M):
  #   As.append(tuple(set(A)))
  # As = list(map(list, set(As)))
  min_ = sums[0]
  hoge = []
  kouho = list(range(1,N+1))
  for i in combinations_with_replacement(kouho, N):
    hoge.append(list(set(i)))
  hoge = list(map(list, set(map(tuple, hoge))))
  for i in hoge:
    mini_CA = []
    for j in i:
      mini_CA.append(CA[j-1])
    mini_CA = np.array(mini_CA)
    OK2 = True
    sums = np.sum(mini_CA,axis=0)
    for k in range(1,M+1):
      if sums[k] < X:
        OK2 = False
        break
    if OK2 == True and sums[0] < min_:
      min_ = sums[0]
  print(min_)

Measured memory_bytes: 197000
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
//cin.sync_with_stdio(false);
//streambuf
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
using vi = vector<int>;
using vll = vector<ll>;
using vpii = vector<pii>;
using ti3 = tuple<int, int, int>;
using vti3 = vector<ti3>;
template<class T, int s>using va = vector<array<T, s>>;
template<class T, class T2> using umap = unordered_map<T, T2>;
template<class T> using uset = unordered_set<T>;
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define ALL(a) a.begin(),a.end()
#define rep(i,a) for(int i=0;i<a;i++)
#define rep1(i,a) for(int i=1;i<=a;i++)
#define rrep(i,a) for(int i=a-1;i>=0;i--)
#define rrep1(i,a) for(int i=a;i;i--)
const ll mod = 1000000007;
#define REP rep
template<class T>using heap = priority_queue<T, vector<T>, greater<T>>;
template<class T>using pque = priority_queue<T, vector<T>, function<T(T, T)>>;
template <class T>
inline void hash_combine(size_t & seed, const T & v) {
	hash<T> hasher;
	seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
namespace std {
	template<typename S, typename T> struct hash<pair<S, T>> {
		inline size_t operator()(const pair<S, T> & v) const {
			size_t seed = 0;
			hash_combine(seed, v.first);
			hash_combine(seed, v.second);
			return seed;
		}
	};
	// Recursive template code derived from Matthieu M.
	template <class Tuple, size_t Index = std::tuple_size<Tuple>::value - 1>
	struct HashValueImpl{
		static void apply(size_t& seed, Tuple const& tuple){
			HashValueImpl<Tuple, Index - 1>::apply(seed, tuple);
			hash_combine(seed, std::get<Index>(tuple));
		}
	};
	template <class Tuple>
	struct HashValueImpl<Tuple, 0>{
		static void apply(size_t& seed, Tuple const& tuple){
			hash_combine(seed, std::get<0>(tuple));
		}
	};
	template <typename ... TT>
	struct hash<std::tuple<TT...>>{
		size_t operator()(std::tuple<TT...> const& tt) const{
			size_t seed = 0;
			HashValueImpl<std::tuple<TT...> >::apply(seed, tt);
			return seed;
		}
	};
}
template<class T>int id(vector<T> &a, T b) {
	return lower_bound(ALL(a), b) - a.begin();
}
//end of lib
int main() {
	int w;
	cin >> w;
	vi a(w), t(w, 0);
	rep(i, w)cin >> a[i];
	rep(i, w) {
		if (a[i] == 0)t[i] = 1e9;
		else if (i == 0)continue;
		else if (a[i] < 0)cmax(t[i],min(t[i - 1]-1, -a[i]));
		else cmax(t[i], t[i - 1] - 1);
	}
	rrep(i, w) {
		if (a[i] == 0 || i == w - 1)continue;
		if (a[i] < 0)cmax(t[i],min(t[i + 1]-1, -a[i]));
		else cmax(t[i], t[i + 1] - 1);
	}
	ll ans = 0;
	rep(i, w) {
		if (a[i] > 0)ans += min(a[i], t[i]);
	}
	cout << ans << endl;
}

Measured memory_bytes: 3644
#include<stdio.h>
int main(void){
  int n,m,i,j,k=0,o=0,p=9999999,s,t;
  scanf("%d %d",&n,&m);
  int l[m];
  int r[m];
  for(i=0;i<m;i++){
    scanf("%d %d",&l[i],&r[i]);
  }
  for(s=0;s<m;s++){
    if(o<l[s]){o=l[s];}
  }
  for(t=0;t<m;t++){
    if(p>r[t]){p=r[t];}
  }
  for(j=0;j<n;j++){
    if(o<=j+1&&j+1<=p){
      k=k+1;
    }
    else{
      k=k;
    }
  }
  printf("%d\n",k);
  return 0;
}


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

void makeVec(vector<long long> &vec){
    long long len = vec.size();
    for(long long i = 0; i < len; i++){
        cin >> vec[i];
    }
    return;
}

int main(){
    long long n, k;
    cin >> n >> k;
    vector<long long> h(n);
    makeVec(h);

    long long ans = 0;
    if(k >= n){
        cout << 0 << endl;
        return 0;
    }

    sort(h.begin(), h.end());
    ans = accumulate(h.begin(), h.end() - k, 0L);
    cout << ans << endl;
    return 0;
}

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

//素数判定関数
bool isPrime(int n){
    if (n < 2) return false;
    else if (n == 2) return true;
    else if (n % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtN = sqrt(n);
    for (int i = 3; i <= sqrtN; i += 2){
        if (n % i == 0){
            // 素数ではない
            return false;
        }
    }
    // 素数である
    return true;
}

int main(void){
    int n;
    cin >> n;
    int count = 0;
    for(int i=0; i<n; i++){
        int a;
        cin >> a;
        if(isPrime(a)) count++;
    }
    cout << count << endl;
    return 0;
}


Measured memory_bytes: 3076
#include<bits/stdc++.h>
using namespace std;
int main()
{
  int a[3];
  a[0]=0;a[1]=0;a[2]=0;
  int x,y;
  cin>>x>>y;
  a[x-1]=1;
  a[y-1]=1;
  if(a[0]==0)
    cout<<1<<"\n";
  else if(a[1]==0)
    cout<<2<<"\n";
  else
    cout<<3<<"\n";
  return 0;
}

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

int main()
{
  int n, m; cin >> n >> m;
  vector<vector<int>> tr(n, vector<int>(n, inf));
  rep(i, m) {
    int s, t, d; cin >> s >> t >> d;
    tr[s][t] = d;
  }
  vector<vector<int>> dp(1<<n, vector<int>(n, inf));
  dp[(1<<n)-1][0] = 0;

  for (int S=(1<<n)-1; S>=0; S--) {
    for (int v=0; v<n; v++) {
      for (int u=0; u<n; u++) {
        if (!(S>>u&1)) {
          dp[S][v] = min(dp[S][v], dp[S|1<<u][u] + tr[v][u]);
        }
      }
    }
  }
  if (dp[0][0] == inf) cout << -1 << endl;
  else cout << dp[0][0] << endl;

  return 0;
}



Measured memory_bytes: 6240
from collections import defaultdict

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

d = defaultdict(int)
for a in A:
    d[a] += 1

Q = int(input())
total = sum(A)
for _ in range(Q):
    b, c = map(int, input().split())
    if b not in d:
        print(total)
    else:
        total += (c - b) * d[b]
        d[c] += d[b]
        d[b] = 0
        print(total)

Measured memory_bytes: 21528
//AtCoder ABC111 C - /\/\/\/
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
int main() {
#if LOCAL&0
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
#endif
    ll n; cin>>n;
    vector<ll> vod; vod.reserve(n/2+1);
    vector<ll> vev; vev.reserve(n/2+1);
    unordered_map<ll,ll> map_od;
    unordered_map<ll,ll> map_ev;
    for(ll i=0;i<n;++i){
        ll v;
        cin>>v;
        if(i%2==0){
            vev.push_back(v);
            ++map_ev[v];
        } else {
            vod.push_back(v);
            ++map_od[v];
        }
    }
    vector<pair<ll,ll>> u_od(map_od.size());
    copy(map_od.begin(),map_od.end(),back_inserter(u_od));
    vector<pair<ll,ll>> u_ev(map_ev.size());
    copy(map_ev.begin(),map_ev.end(),back_inserter(u_ev));
    sort(u_od.begin(),u_od.end(),[](auto& a, auto& b){ return a.second>b.second;});
    sort(u_ev.begin(),u_ev.end(),[](auto& a, auto& b){ return a.second>b.second;});
    ll ans=0;
    if(u_od[0].first==u_ev[0].first){
        ll t0=u_od[0].second;
        if(u_ev.size()>=1) t0+=u_ev[1].second;
        ll t1=u_ev[0].second;
        if(u_od.size()>=1) t1+=u_od[1].second;
        ans=max(t0,t1);
    } else {
        ans=u_od[0].second+u_ev[0].second;
    }
    cout<<n-ans<<endl;
    return 0;
}


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

typedef long long ll;
#define REP(i,n) for(int i=0,_n=(int)(n);i<_n;++i)
#define ALL(v) (v).begin(),(v).end()
#define CLR(t,v) memset(t,(v),sizeof(t))
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T>void pv(T a,T b){for(T i=a;i!=b;++i)cout<<(*i)<<" ";cout<<endl;}
template<class T>void chmin(T&a,const T&b){if(a>b)a=b;}
template<class T>void chmax(T&a,const T&b){if(a<b)a=b;}


int nextInt() { int x; scanf("%d", &x); return x;}
ll nextLong() { ll x; scanf("%lld", &x); return x; }

const int MAX_N = 112345;
const ll INF = 1LL << 58;

struct BITMAX {
  int n;
  ll vs[MAX_N + 1];
  BITMAX() {
    this->n = MAX_N;
    clear();
  }
  void clear() {
    REP(i, n+1) vs[i] = -INF; // default value
  }
  void update(int idx, ll val) {
    for (int x = idx + 1; x <= n; x += x & -x) vs[x] = max(vs[x], val); // [idx, ∞] の範囲の最大値を val で更新しようと試みる
  }
  ll get(int idx) {
    ll val = -INF; // default value
    for (int x = idx + 1; x > 0; x -= x & -x) val = max(val, vs[x]); // [idx, ∞] の範囲の最大値を取得
    return val;
  }
};

ll X[MAX_N], V[MAX_N];
BITMAX bit;

ll solve(int N, ll C) {
  vector<ll> a(N+1);
  REP(i, N) a[i+1] = a[i] + (V[i]);
  REP(i, N) a[i+1] -= X[i];
  // pv(ALL(a));
  bit.clear();
  REP(i, N+1) bit.update(i, a[i]);

  ll best = bit.get(N);
  // cout << "best=" << best << endl;
  ll get = 0;
  for (int b = N-1; b >= 0; b--) {
    get += V[b];
    ll score = get - (C - X[b]) * 2;
    score += bit.get(b);
    // cout << b << ":" << score << endl;
    chmax(best, score);
  }
  return best;
}

int main2() {
  int N = nextInt();
  ll C = nextLong();
  REP(i, N) { 
    X[i] = nextLong();
    V[i] = nextLong();
  }
  ll ans1 = solve(N, C);
  reverse(V, V + N);
  reverse(X, X + N);
  REP(i, N) X[i] = C - X[i];
  ll ans2 = solve(N, C);
  ll ans = max(ans1, ans2);
  cout << ans << endl;
  return 0;
}

int main() {
  for (;!cin.eof();cin>>ws)
    main2();
  return 0;
}


Measured memory_bytes: 3456
import java.io.InputStream;
import java.io.PrintStream;
import java.util.*;

public class Main {

  public static void main(String[] args) {
    solve(System.in, System.out);
  }

  static void solve(InputStream is, PrintStream os) {
    Scanner sc = new Scanner(is);

    /* read */

    int n = sc.nextInt();
    int k = sc.nextInt();

    String s = sc.next();

    String result = s.substring(0, k - 1) + s.substring(k - 1, k).toLowerCase() + s.substring(k, n);

    os.println(result);
  }
}

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

#define rep(i, n) for(int i = 0; i<(n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
using namespace std;
typedef long long ll;

using pll = pair<ll, ll>;

int main() {
    int N, M;
    cin >> N >> M;
    vector<ll> A(N);
    rep(i, N) cin >> A[i];
    vector<pll> CB(M);
    rep(i, M) cin >> CB[i].second >> CB[i].first;

    sort(A.begin(), A.end());
    sort(CB.rbegin(), CB.rend());

    ll sum = 0;
    ll k = 0;
    for (auto cb: CB) {
        rep(i, cb.second) {
            if (k >= N) break;
            sum += max(A[k++], cb.first); // Aの小さい数字とCの大きい数字を比較して大きいほうを採用
        }
    }

    for (int i = k; i < N; i++) sum += A[i]; // 比較されていない残りのAを足す
    cout << sum << endl;
}


Measured memory_bytes: 2560
def getval():
    s = input()
    return s

def main(s):
    mod = 10**9 + 7
    #Remainders of 10**i%13
    rem = [1]
    for i in range(11):
        rem.append((rem[-1]*10)%13)
    #Digits of ?
    arr = []
    #Sum of existing integers mod 13
    init = 0
    for i in range(len(s)):
        if s[i]=="?":
            arr.append(len(s)-i-1)
        else:
            init += (int(s[i]) * rem[(len(s)-i-1)%12])%13
            init %= 13

    #DP for number of comb such that rem is j on ith ?
    dp = [[0 for i in range(13)]]
    dp[0][0] = 1
    for i in arr:
        temp = [0 for i in range(13)]
        prev = dp[-1]
        for j in range(13):
            for k in range(10):
                update = prev[j]
                temp[(j+k*rem[i%12])%13] += update
                temp[(j+k*rem[i%12])%13] %= mod
        dp.append(temp)

    print(dp[-1][(18-init)%13])
    
                
if __name__=="__main__":
    s = getval()
    main(s)

Measured memory_bytes: 100404
#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <string>
#include <set>
#include <map>
#define REP(i,n) for(ll i = 0; i < (ll)n; i++)
#define INF 1000000000000000
using namespace std;
typedef long long ll;
typedef double db;
typedef string str;

int main(){
  ll n;
  cin >> n;
  str s;
  cin >> s;
  ll a[n];
  ll b[n];
  REP(i,n){
    if(i==0){
      if(s[i]=='W'){
        a[i]=1;
      }else{
        a[i]=0;
      }
    }else{
      if(s[i]=='W'){
        a[i] = a[i-1]+1;
      }else{
        a[i] = a[i-1];
      }
    }
  }
  for(ll i = n-1; i >= 0; i--){
    if(i==n-1){
      if(s[i]=='E'){
        b[i] = 1;
      }else{
        b[i] = 0;
      }
    }else{
      if(s[i]=='E'){
        b[i] = b[i+1]+1;
      }else{
        b[i] = b[i+1];
      }
    }
  }
  ll ans = INF;
  REP(i,n){
    if(i==0) ans = b[i+1];
    else if(i==n-1) ans = min(ans,a[i-1]);
    else ans = min(a[i-1]+b[i+1],ans);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 5380
#include <bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pi M_PI
#define R cin>>
#define Z class
#define ll long long
#define ln cout<<'\n'
#define in(a) insert(a)
#define pb(a) push_back(a)
#define pd(a) printf("%.10f\n",a)
#define mem(a) memset(a,0,sizeof(a))
#define all(c) (c).begin(),(c).end()
#define iter(c) __typeof((c).begin())
#define rrep(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define REP(i,m,n) for(int i=(int)(m);i<(int)(n);i++)
#define rep(i,n) REP(i,0,n)
#define tr(it,c) for(iter(c) it=(c).begin();it!=(c).end();it++)
template<Z A>void pr(A a){cout<<a;ln;}
template<Z A,Z B>void pr(A a,B b){cout<<a<<' ';pr(b);}
template<Z A,Z B,Z C>void pr(A a,B b,C c){cout<<a<<' ';pr(b,c);}
template<Z A,Z B,Z C,Z D>void pr(A a,B b,C c,D d){cout<<a<<' ';pr(b,c,d);}
template<Z A>void PR(A a,ll n){rep(i,n){if(i)cout<<' ';cout<<a[i];}ln;}
ll check(ll n,ll m,ll x,ll y){return x>=0&&x<n&&y>=0&&y<m;}
const ll MAX=1000000007,MAXL=1LL<<61,dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
typedef pair<int,int> P;
typedef pair<int,P> PP;
map<string,int> ma;
void IN(string s){
  if(!ma.count(s)) {
    int k=ma.size();
    ma[s]=k;
  }
}
int d[6666][2222];

void Main() {
  int n,m,k;
  while(cin >> n >> m >> k && n) {
    ma.clear();
    k*=10;
    string ss,tt;
    cin >> ss >> tt;
    IN(ss);IN(tt);
    vector<P> v[n*2];
    rep(i,n) {
      string s,t;
      int z;
      cin >> s >> t >> z;
      IN(s);IN(t);
      v[ma[s]].pb(P(ma[t],z));
      v[ma[t]].pb(P(ma[s],z));
    }
    set<int> se;
    rep(i,m) {
      string s;
      R s;
      IN(s);
      se.in(ma[s]);
    }
    priority_queue<PP,vector<PP>,greater<PP> > que;
    rep(i,ma.size())rep(j,k+1)d[i][j]=MAX;
    d[ma[ss]][k]=0;
    que.push(PP(0,P(ma[ss],k)));
    while(!que.empty()) {
      PP p=que.top();que.pop();
      int x=p.S.F,cc=p.F,t=p.S.S;
      if(d[x][t]<cc) continue;
      rep(i,v[x].size()) {
        int y=v[x][i].F,c=v[x][i].S;
        c=t-c;
        if(c<0) continue;
        if(se.count(y)) c=k;
        if(d[y][c]<=d[x][t]+v[x][i].S) continue;
        d[y][c]=d[x][t]+v[x][i].S;
        que.push(PP(d[y][c],P(y,c)));
      }
    }
    int ans=MAX;
    rep(i,k+1) ans=min(ans,d[ma[tt]][i]);
    if(ans==MAX) ans=-1;
    pr(ans);
  }
}

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


Measured memory_bytes: 80712
n,h,l,a=gets.chomp.to_i,['M','A','R','C','H'],[0,0,0,0,0],0
n.times{i=h.index(gets.chomp[0]);i&&l[i]+=1}
5.times{|i|(i+1..4).each{|j|(j+1..4).each{|k|a+=l[i]*l[j]*l[k]}}}
p a


Measured memory_bytes: 1788
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header

int main() {
	int n, sum=0;
	cin >> n;
	vector<int> p(n);
	rep(i,n) cin >> p[i];
	sort(all(p));
	rep(i,n-1) sum+=p[i];
	cout << sum+p[n-1]/2 << endl;
	return 0;
}

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

int main( void )
{
    char c[9];
    rep(i,9)
        cin >> c[i];
    
    cout << c[0] << c[4] << c[8] << endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

int main(){
  int N;
  cin >> N;
  
  int a[N];
  for(int i=0;i<N;i++){
	cin >> a[i];
  }
  
  int count=1;
  bool c = true;

  for(int i=1;i<N;i++){
	  for(int j=0;j<i;j++){
      if(a[i] < a[j]){
        c = false;
        break;
      }
    }
	  if(c == true){
		  count++;
    }
    c = true;
  }
  
  cout << count << endl;
  return 0;
}

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

using namespace std;

int a[200001];
stack <int> s;
long long l[200001];
long long r[200001];
long long ans;

int main () {
	int n;
	cin >> n;
	for (int i = 1;i <= n;i ++) {
		cin >> a[i];	
	}
	for (int i = 1;i <= n;i ++) {
		l[i] = i;
		while (s.size () && a[i] < a[s.top ()]) {
			l[i] = l[s.top ()];
			s.pop ();
		}
		s.push (i);
	}            
	while (s.size ()) s.pop ();
	for (int i = n;i >= 1;i --) {
		r[i] = i;
		while (s.size () && a[i] < a[s.top ()]) {
			r[i] = r[s.top ()];
			s.pop ();
		}
		s.push (i);
	}
	for (int i = 1;i <= n;i ++) {
		long long left = i - l[i] + 1;
		long long right = r[i] - i + 1;
		ans += (left * right * a[i]);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 4992
import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        try (CustomReader in = new CustomReader()) {
            new Main().execute(in);
        } catch (IOException e) {
            e.printStackTrace();
        }
    }

    public void execute(CustomReader in) throws IOException {
        final String S = in.readLine();
        final String T = in.readLine();
        List<String> candidates = new ArrayList<>();

        for (int i = 0, bound = S.length() - T.length(); i <= bound; i++) {
            if (match(S, T, i)) {
                String key = S.substring(0, i).replace('?', 'a') + T + S.substring(i + T.length(), S.length()).replace('?', 'a');
                candidates.add(key);
            }
        }
        Collections.sort(candidates);

        System.out.println(candidates.size() > 0 ? candidates.get(0) : "UNRESTORABLE");
    }

    private boolean match(String s, String t, int pos) {
        for (int i = 0; i < t.length(); i++) {
            if ( s.charAt(pos+i) == '?'){
                continue;
            }if(s.charAt(pos + i) == t.charAt(i)) {
                continue;
            }
            return false;
        }
        return true;
    }

    static class CustomReader extends BufferedReader {

        private static final int DEFAULT_BUF_SIZE = 2048;
        // private static final int DEFAULT_BUF_SIZE = 4096;
        // private static final int DEFAULT_BUF_SIZE = 8192;
        //private static final int DEFAULT_BUF_SIZE = 16384;
        // private static final int DEFAULT_BUF_SIZE = 1048576;

        public CustomReader() throws IOException {
            super(new InputStreamReader(System.in), DEFAULT_BUF_SIZE);
        }

        public int[] readLineAsIntArray() throws IOException {
            String[] strArray = this.readLine().split(" ");
            int[] intArray = new int[strArray.length];
            for (int i = 0, n = strArray.length; i < n; i++) {
                intArray[i] = Integer.parseInt(strArray[i]);
            }
            return intArray;
        }

        public int[][] readAsIntMatrix(int rows, int columns) throws IOException {
            int[][] matrix = new int[rows][columns];
            for (int i = 0; i < rows; i++) {
                String[] r = this.readLine().split(" ");
                for (int j = 0; j < columns; j++) {
                    matrix[i][j] = Integer.parseInt(r[j]);
                }
            }
            return matrix;
        }
    }
}

Measured memory_bytes: 21204
#include<bits/stdc++.h>
#define mod 1000000007
#define int long long int
#define phi 1.6180339
#define rep(i,n) for(auto i=0;i<(n);i++)
#define endl "\n"
#define For(i,a,b) for(auto i=(a);i<(b);i++)
#define op1 cin.tie(NULL)
#define op2 cout.tie(NULL)
#define op3 std::ios_base::sync_with_stdio(false)
#define MAXX 100001
using namespace std;
int dp[100][MAXX];
int solve(vector<int> val,vector<int> weight,int value,int sumvalue,int i,int n)
{
    if(value==sumvalue) return 0;
    if(value<sumvalue) return INT_MIN;
    if(i>=n) return 0;
    if(dp[i][sumvalue]!=-1) return dp[i][sumvalue];
    return dp[i][sumvalue]=max(weight[i]+solve(val,weight,value,sumvalue+val[i],i+1,n),solve(val,weight,value,sumvalue,i+1,n));
}
void trozen()
{
    rep(i,100) rep(j,MAXX) dp[i][j]=-1;
    int n,sumvalue;
    cin>>n>>sumvalue;
    vector<int> val(n);
    vector<int> weight(n);
    rep(i,n) cin>>val[i]>>weight[i];
    cout<<solve(val,weight,sumvalue,0,0,n);

}
int32_t main()
{
    op1;op2;op3;
    /*#ifndef ONLINE_JUDGE
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    #endif*/
    trozen();
    return 0;
}


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

int main(int argc, const char * argv[]) {



    cin.tie(0);
    ios::sync_with_stdio(false);

    /////////////////////
    // Write code below /
    /////////////////////
    int A1,A2,A3;

    cin>>A1>>A2>>A3;

    if(A1 + A2 + A3 > 21)
        cout<<"bust"<<endl;
    else
        cout<<"win"<<endl;

    return 0;
}

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

#define rp(i, k, n) for (int i = k; i < n; i++)
typedef long long ll;

ll mod = 1e9 + 7;

int main() {
    int n;
    scanf("%d", &n);
    vector<int> H(n+1);
    rp(i, 0, n) scanf("%d", &H.at(i+1));
    vector<int> dp(n + 1);
    dp.at(2) = abs(H.at(2) - H.at(1));
    rp(i, 3, n+1) {
        int cost1 = abs(H.at(i) - H.at(i-1));
        int cost2 = abs(H.at(i) - H.at(i-2));
        dp.at(i) = min(dp.at(i-2) + cost2, dp.at(i-1) + cost1);
    }
    printf("%d", dp.at(n));
    return 0;
} 

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(int i=0;i<(n);i++)
int main(){
	int n;
	cin>>n;
	string s;
	int a=0,b=0,c=0,d=0;
	rep(i,n){
		cin>>s;
		if(s=="AC")a++;
		if(s=="WA")b++;
		if(s=="TLE")c++;
		if(s=="RE")d++;
	}
	cout<<"AC x "<<a<<"\n";
	cout<<"WA x "<<b<<"\n";
	cout<<"TLE x "<<c<<"\n";
	cout<<"RE x "<<d<<"\n";
	return 0;
}

Measured memory_bytes: 3624
#include <cstdio>
int main(){
	int a, b, c;
	scanf("%d %d %d",&a,&b,&c);
	if (a > b){
		if (c > a){
			printf("%d\n",c * 10 + a + b);
		}else{
			printf("%d\n",a * 10 + c + b);
		}
	}else{
		if (c > b){
			printf("%d\n",c * 10 + a + b);
		}else{
			printf("%d\n",b * 10 + a + c);
		}
	}
}

Measured memory_bytes: 128
n=int(input())
A=list(map(int,input().split()))
q=int(input())
m=list(map(int,input().split()))

sumlist=[]

for i in range(2**n):
    sumA=0
    for j in range(n):
        if ((i>>j) & 1):
            sumA+=A[j]
    sumlist.append(sumA)

for k in range(q):
    if m[k] in sumlist:
        print("yes")
    else:
        print("no")


Measured memory_bytes: 43076
#include<bits/stdc++.h>
#define pb push_back
#define pf push_front

using namespace std;	
typedef long long int lli;
lli n,k,m,t,a,b,l,r,temp1,temp2,s,x,y,temp,q,d,mod=1e9+7,w,p,c;
bool vis[200005];
lli cnt;

vector<lli>adj[200004];

void dfs(lli node)
{
	vis[node]=true;
	cnt++;
	for(auto x:adj[node])
	{
		if(!vis[x])
			dfs(x);
	}
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 	
	cin>>n>>m;
	
	lli mx=0;	
	
	
	for(int i=0;i<m;i++)
	{
		cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
	}
	
	for(int i=0;i<n;i++)
	{
		cnt=0;
		if(!vis[i])
		{
			dfs(i);
			mx=max(mx,cnt);
		}
	}
	cout<<mx<<endl;
}


Measured memory_bytes: 20948
#include <iostream>
#include <utility>
#include <vector>
#define inf 100000000

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

int N, C;
int map[11][11];
vector<int> G[11][11];
bool used[11][11];

int dfs(int posi, int posj, int val)
{
	if(posi < 0 || posj < 0 || posi + posj >= N) return 0;
	if(map[posi][posj] == 0) return -1;
	if(map[posi][posj] != val) return 0;
	if(used[posi][posj]) return 0;
	
	used[posi][posj] = true;
	
	const int vx[] = {0, 1, 1, 0, -1, -1};
	const int vy[] = {-1, -1, 0, 1, 1, 0};
	
	int ret = 1;
	bool flag = false;
	
	int ni, nj, res;
	for(int dir = 0; dir < 6; dir++){
		ni = posi + vx[dir], nj = posj + vy[dir];
		res = dfs(ni, nj, val);
		if(res == -1) flag = true;
		ret += res;
	}
	if(flag) ret = -1;
	return ret;
}

int count()
{
	int ret = 0;
	int res;
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(i + j >= N) continue;
			used[i][j] = false;
		}
	}
	
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			if(i + j >= N) continue;
			if(map[i][j] && !used[i][j]){
				res = dfs(i, j, map[i][j]);
				if(res == -1) continue;
				if(map[i][j] == C) ret -= res;
				else ret += res;
			}
		}
	}
	return ret;
}

int main(void)
{
	while(1){
		cin >> N >> C;
		if( N == 0 && C == 0) break;
		
		for(int i = 1; i <= N; i++){
			for(int j = 0; j < i; j++){
				cin >> map[j][i-j-1];
			}
		}
		
		int ans = -inf;
		for(int i = 0; i < N; i++){
			for(int j = 0; j < N; j++){
				if(i + j >= N) continue;
				if(map[i][j]) continue;
				
				map[i][j] = C;
				ans = max(ans, count());
				map[i][j] = 0;
			}
		}
		
		if(ans == -inf) ans = 0;
		cout << ans << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3016