akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
using namespace std;

int main()
{
  int n;
  string s;
  cin >> n >> s;
  for(int i=0; i<s.size(); i++)
    cout << (char)('A' + (s[i] + n - 'A') % 26);
  cout << endl;
  return 0;
}

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

typedef vector<int> veci;
typedef pair<int, int> pii;
typedef vector<pii> vecii;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef vector<ll> vecl;
typedef vector<pll> vecll;
#define EPS (1e-9)
#define MOD (1e9 + 7)
#define fi first
#define se second
#define endl '\n'

void solve() {
    int n;
    cin >> n;

    string s;
    cin >> s;

    vector<vector<int>> table(10);
    for (int i=0; i<n; ++i) {
        table[int(s[i] - '0')].push_back(i);
    }

    int cnt = 0;
    int p = 0;
    for (int i=0; i<10; ++i) {
        if (table[i].empty()) continue;

        for (int j=0; j<10; ++j) {
            p = table[i][0];
            auto it = lower_bound(table[j].begin(), table[j].end(), p+1);
            if (it==table[j].end()) continue;

            for (int k=0; k<10; ++k) {
                p = *it;
                auto it = lower_bound(table[k].begin(), table[k].end(), p+1);
                if (it!=table[k].end()) {
                    cnt += 1;
                }
            }
        }
    }
    cout << cnt << endl;
    return;
}

int main(int argc, char* argv[]) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#ifdef LOCAL_TEST
    (void)argc;
    const string strpath = string(argv[0]) + string("-test.in");
    freopen(strpath.c_str(), "r", stdin);
    int tcs;
    cin >> tcs;
    while (tcs-- > 0)
#endif
        solve();
}


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

using namespace std;
#define PI 3.1415926535897932384626433832795
#define MOD (1000000007)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repc(i, s, n) for (int i = (s); i <= (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define rrepc(i, s, n) for (int i = (s); i >= (n); i--)
typedef long long ll;
typedef unsigned long long ull;

int main()
{
	ll N, ans = 0;

	cin >> N;

	if (N < 2) ans = 0;
	else if (N % 2 == 0) {
		ll div = 10, num10 = N / 10;
		while (N / div > 0) {
			ans += N / div;
			div *= 10;
		}
		div = 5;
		while (num10 / div > 0) {
			ans += num10 / div;
			div *= 5;
		}
		div = 10;
		while (num10 / div > 0){
			ans -= num10 / div;
			div *= 10;
		}
	}
	else ans = 0;

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define be(v) (v).begin(),(v).end()
#define pb(q) push_back(q)
typedef long long ll;
using namespace std;
const ll mod=1000000007,N=200001;
#define doublecout(a) cout<<fixed<<setprecision(10)<<a<<endl;

ll fac[N],finv[N],inv[N];
void cominit(){
    fac[0]=fac[1]=1;
    finv[0]=finv[1]=1;
    inv[1]=1;
    for(int i=2;i<N;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=mod-inv[mod%i]*(mod/i)%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}

vector<vector<ll> > g(N);
ll pa[N],dpin[N],dpout[N],inl[N],outl[N];

ll in(int n){return (dpin[n]*finv[inl[n]])%mod;}
ll out(int n){return (dpout[n]*finv[outl[n]])%mod;}

void dfs1(ll now,ll p){
	pa[now]=p;
	ll ans=1,sum=0;
	for(auto& to:g[now]){
		if(to==p)continue;
		dfs1(to,now);
		sum+=inl[to];
		(ans*=in(to))%=mod;
	}
	(ans*=fac[sum])%=mod;
	inl[now]=sum+1;
	dpin[now]=ans;
}

void dfs2(ll now,ll p){
	vector<ll> v1,v2,v3,v4;
	for(auto& to:g[now]){
		if(to==p)v1.pb(1),v2.pb(1),v3.pb(0),v4.pb(0);
		else{
			v1.pb(in(to));
			v2.pb(in(to));
			v3.pb(inl[to]);
			v4.pb(inl[to]);
		}
	}
	int niko=g[now].size();
	for(int i=1;i<niko;i++) (v1[i]*=v1[i-1])%=mod,v3[i]+=v3[i-1];
	for(int i=niko-2;i>=0;i--) (v2[i]*=v2[i+1])%=mod,v4[i]+=v4[i+1];

	for(int i=0;i<niko;i++){
		int to=g[now][i];
		if(to==p) continue;
		ll ans=out(now),sum=outl[now];
		if(i>0) (ans*=v1[i-1])%=mod,sum+=v3[i-1];
		if(i<niko-1) (ans*=v2[i+1])%=mod,sum+=v4[i+1];
        (ans*=fac[sum])%=mod;
	    outl[to]=sum+1,dpout[to]=ans;
		dfs2(to,now);
	}
}

int main(){
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);
    cominit();
	ll n,a,b;
	cin>>n;
	for(int i=1;i<n;i++){
		cin>>a>>b;
		a--,b--;
		g[a].pb(b);
		g[b].pb(a);
	}
	dfs1(0,-1);
	dpout[0]=1;outl[0]=0;
	dfs2(0,-1);
	for(int i=0;i<n;i++){
		ll sum=outl[i],ans=out(i);
		for(auto& to:g[i]){
			if(to==pa[i])continue;
			sum+=inl[to];
			(ans*=in(to))%=mod;
		}
		(ans*=fac[sum])%=mod;
		cout << ans << endl;
	}
	return 0;
}


Measured memory_bytes: 36224
#include<algorithm>
#include<bitset>
#include<climits>
#include<cmath>
#include<cstdlib>
#include<iomanip>
#include<iostream>
#include<map>
#include<numeric>
#include<queue>
#include<set>
#include<string>
#include<time.h>
#include<tuple>
#include<utility>
#include<vector>

using namespace std;
const long mod = 1000000007;
long gcd(long x, long y) { if (x > y) { return gcd(y, x); } long r; while (y != 0) { r = x % y; x = y; y = r; }return x; }
long lcm(long x, long y) { return(x / gcd(x, y)) * y; }

int main() {

	long res = 0;
	long N; cin >> N;
	vector<long> A(N), B(N), C(N - 1);

	for (int i = 0; i < N; i++) cin >> A[i];
	for (int i = 0; i < N; i++) cin >> B[i];
	for (int i = 0; i < N - 1; i++) cin >> C[i];

	res += accumulate(B.begin(), B.end(), 0);

	for (int i = 1; i < N; i++) if (A[i - 1] == A[i] - 1) res += C[A[i - 1] - 1];

	cout << res << endl;
}

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

using namespace std;

int main(void){
  int N, M, C;
  cin >> N; cin >> M; cin >> C;
  vector<int> B(M);
  vector< vector<int> > A(N, vector<int>(M));
  int i, j;
  int count = 0;

  //input
  for(i=0; i<M; i++)
    cin >> B[i];
  for(i=0; i<N; i++)
    for(j=0; j<M; j++)
      cin >> A[i][j];

  //calculation of sumation
  int sum;
  for(i=0; i<N; i++){
    sum = 0;
    for(j=0; j<M; j++)
      sum += A[i][j]*B[j];
    sum += C;
    //count
    if(sum > 0)
      count ++;
  }

  //output
  cout << count << endl;

  return 0;
}


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

int main(){
  int n;
  cin >> n;
  if(n%2 == 0) cout << n/2 << endl;
  else cout << n/2+1 << endl;
}

Measured memory_bytes: 256
import itertools

A=range(0,int(input())+1)
B=range(0,int(input())+1)
C=range(0,int(input())+1)
X=int(input())

cnt=0

for a,b,c in itertools.product(A,B,C):
    if 500*a+100*b+50*c==X:
        cnt += 1
    
print(cnt)

Measured memory_bytes: 39408
N = int(input())
a = list(map(int, input().split()))

a1h = a[:N]
a2h = [-ai for ai in a[2 * N:]]

import heapq
heapq.heapify(a1h)
heapq.heapify(a2h)

sum1 = [sum(a1h)]
sum2 = [sum(a2h)]
for k in range(N, 2 * N):
    sum1.append(sum1[-1] + a[k] - heapq.heappushpop(a1h, a[k]))
    sum2.append(sum2[-1] + -a[-k - 1] - heapq.heappushpop(a2h, -a[-k - 1]))

print(max(map(sum, zip(sum1, sum2[::-1]))))


Measured memory_bytes: 39124
#include <bits/stdc++.h>
#include <iomanip>
#include <math.h>
#include <unistd.h>
#include <stdio.h>
#define all(a) (a).begin(),(a).end()
#define vecin(a) rep(i,a.size())cin >> a[i]
#define vecout(a) rep(i,a.size()){cout << a[i];cout << (i == a.size() - 1 ? "\n":" ");}
#define rep(i,x) for(ll i = 0;i<x;i++)
#define REP(i,x) for(ll i = 1;i<=x;i++)
#define mp make_pair
using ll = long long;
using ld = long double;
using namespace std;
using dou = double;
const ll inf = 2147483647;
const ll INF = 1LL << 60;
const dou pi = 3.14159265358;
const ll mod = 1000000007LL;
//const ll mod = 998244353LL;
typedef pair<ll,ll> P;
using graph = vector<vector<ll>>;
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;}
template<class T> inline bool change(T a,T b){if(a > b){swap(a,b);return true;}return false;}
ll gcd(ll a,ll b){
    if(a < b)swap(a,b);
    if(a % b == 0)return b;
    else return gcd(b,a%b);
}
ll lcm(ll a,ll b){
    return a / gcd(a,b) * b;
}

//素数判定O(sqrt(N))
bool isp(ll n){
    bool res = true;
    if(n == 1)return false;
    else{
        for(ll i = 2;i * i <= n;i++){
            if(n % i == 0){
                res = false;
                break;
            }
        }
        return res;
    }
}
const ll cmax = 1000000;
ll fac[cmax], finv[cmax], inv[cmax];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (ll i = 2; i < cmax; i++){
        fac[i] = fac[i - 1] * i % mod;
        inv[i] = mod - inv[mod%i] * (mod / i) % mod;
        finv[i] = finv[i - 1] * inv[i] % mod;
    }
}

// 二項係数計算
ll nCk(ll n, ll k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
}
//nのm乗をMODで割ったあまりO(logm)
ll modpow(ll n,ll m,ll MOD){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n) % MOD;
        m >>= 1;
        n *= n;
        n %= MOD;
    }
    return res;
}
ll mypow(ll n,ll m){
    if(m == 0)return 1;
    if(m < 0)return -1;
    ll res = 1;
    while(m){
        if(m & 1)res = (res * n);
        m >>= 1;
        n *= n;
    }
    return res;
}
//printf("%.10f\n", N);
/*  vector<ll> vec = {1,2,5,6,8,9,10};
    cout << binary_search(all(vec),5) << endl; -> true*/
/*
    vector<ll> vec = {1,2,5,6,8,9,10};
    auto n = upper_bound(all(vec),4);
    cout << *n << endl; -> 5*/
 
//    cout << fixed << setprecision(15);


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll N;
    cin >> N;
    vector<ll> vec(N);
    vecin(vec);
    vector<ll> bits(65);
    rep(i,N){
        ll cnt = 0;
        while(vec[i]){
            if(vec[i]&1)bits[cnt]++;
            vec[i] /= 2;
            cnt++;
        }
    }
    //vecout(bits);
    ll num = 1;
    ll ans = 0; 
    rep(i,65){
        ll cnt = num * bits[i] % mod * (N - bits[i]) % mod;
        ans += cnt;
        ans %= mod;
        num *= 2LL;
        num %= mod;
    }
    cout << ans << endl;
}

Measured memory_bytes: 5532
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <functional>
#define ll long long
using namespace std;


int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
    int n, h, w;
    cin >> n >> h >> w;
    int cnt = 0;
    int a[1010], b[1010];
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        if (a[i] >= h && b[i] >= w) {
            cnt++;
        }
    }
    cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
typedef struct{
  char c;
  int value;
}Trump;

int isStable(Trump in[],Trump out[],int n){
  int i,j,a,f,p,flag=0;
  for(i=0;i<n;i++){
    if(in[i].value==out[i].value && in[i].c==out[i].c)continue;
    f=0;
    for(j=0;j<n;j++){
      if(in[i].value==out[j].value){
        f=1;
        p=0;
        for(a=i-1;a>=0;a--)
          if(in[a].c==out[j].c)p=1;
        if(in[i].c!=out[j].c && p==0){
          flag=1;
        }
      }
      if(f==1)break;
    }
    if(flag==1)return 0;
  }
  return 1;
}

int main(){
  int i,j,minj,n,flag=0,f,p,a;
  char m;
  Trump C[36],D[36],E[36],t;
  scanf("%d%c",&n,&m);
  for(i=0;i<n;i++){
    scanf("%c%d%c",&C[i].c,&C[i].value,&m);
    E[i]=D[i]=C[i];
  }

  
  for(i=0;i<n;i++)
    for(j=n-1;j>i;j--)
      if(C[j].value<C[j-1].value){
        t=C[j-1];
        C[j-1]=C[j];
        C[j]=t;
      }

  for(i=0;i<n-1;i++)printf("%c%d ",C[i].c,C[i].value);
  printf("%c%d\n",C[i].c,C[i].value);
  
  
  if(isStable(E,C,n))printf("Stable\n");
  else printf("Not stable\n");
  


  int d;
  flag=0;
  for(i=0;i<n;i++){
    minj=i;
    for(j=i+1;j<n;j++)
      if(D[j].value<D[minj].value){
        minj=j;
      }
    t=D[minj];
    D[minj]=D[i];
    D[i]=t;
  }
  for(i=0;i<n-1;i++)printf("%c%d ",D[i].c,D[i].value);
  printf("%c%d\n",D[i].c,D[i].value);
  

  if(isStable(E,D,n))printf("Stable\n");
  else printf("Not stable\n");
  return 0;
}




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

namespace AtCoder.Contest.A
{
	class Program
	{
		public static void Main(string[] args)
		{
			var sw = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
			Console.SetOut(sw);

			Scanner cin = new Scanner();

			int x = cin.nextInt();
			int t = cin.nextInt();

			Console.WriteLine(Math.Max(x - t, 0));

			Console.Out.Flush();
		}
	}

	class Scanner
	{
		string[] s;
		int i;

		char[] cs = new char[] { ' ' };

		public Scanner()
		{
			s = new string[0];
			i = 0;
		}

		public string next()
		{
			if (i < s.Length) return s[i++];
			string st = Console.ReadLine();
			while (st == "") st = Console.ReadLine();
			s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
			if (s.Length == 0) return next();
			i = 0;
			return s[i++];
		}

		public int nextInt()
		{
			return int.Parse(next());
		}

		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextInt() + add;
			}
			return Array;
		}

		public long nextLong()
		{
			return long.Parse(next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextLong() + add;
			}
			return Array;
		}

		public double nextDouble()
		{
			return double.Parse(next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++)
			{
				Array[i] = nextDouble() + add;
			}
			return Array;
		}
	}
}

Measured memory_bytes: 11092
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <functional>

using namespace std;
 
#define mod 1000000007
#define FOR(x,to) for(int x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define long long long
inline int rei(){int x;cin>>x;return x;}
inline long rel(){long x;cin>>x;return x;}
inline string res(){string x;cin>>x;return x;}
//------------------------------------------------------- 
int U[2000][2000];
int D[2000][2000];
int L[2000][2000];
int R[2000][2000];
bool Map[2000][2000];
void Calc(){
	int H = rei();
	int W = rei();
	for(int i=0;i<H;i++){
		string S = res();
		for(int j=0;j<W;j++){
			if(S[j] == '#'){
				Map[i][j] = true;
			}
		}
	}
	for(int j=0;j<W;j++){
		if(!Map[0][j]){
			U[0][j] = 1;
		}
	}
	for(int i=1;i<H;i++){
		for(int j=0;j<W;j++){
			if(!Map[i][j]){
				U[i][j] = U[i-1][j]+1;
			}
		}
	}
	for(int j=0;j<W;j++){
		if(!Map[H-1][j]){
			D[H-1][j] = 1;
		}
	}
	for(int i=H-2;i>=0;i--){
		for(int j=0;j<W;j++){
			if(!Map[i][j]){
				D[i][j] = D[i+1][j]+1;
			}
		}
	}
	for(int i=0;i<H;i++){
		if(!Map[i][0]){
			L[i][0] = 1;
		}
	}
	for(int i=0;i<H;i++){
		for(int j=1;j<W;j++){
			if(!Map[i][j]){
				L[i][j] = L[i][j-1]+1;
			}
		}
	}
	for(int i=0;i<H;i++){
		if(!Map[i][W-1]){
			R[i][W-1] = 1;
		}
	}
	for(int i=0;i<H;i++){
		for(int j=W-2;j>=0;j--){
			if(!Map[i][j]){
				R[i][j] = R[i][j+1]+1;
			}
		}
	}
	int ans = 0;
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			ans = max(ans,U[i][j]+D[i][j]+R[i][j]+L[i][j]-3);
		}
	}
	cout << ans << endl;
}
int main(int argc,char** argv){
	ios::sync_with_stdio(false), cin.tie(0);
	cout.tie(0); Calc(); return 0;
}

Measured memory_bytes: 66688
#include <iostream>

int main(){
  int h,w,i,q;

  std::cin >> h>> w;
  while(h != 0 && w != 0){
    for (i = 0; i < h; i++) {
      /* code */
      for (q = 0; q < w; q++) {
        if((i + q)%2 == 0){
          std::cout << "#";
        }else{
          std::cout << ".";
        }
      }
      std::cout << '\n';
    }
    std::cout  << '\n';
    std::cin >> h>> w;
  }
  return 0;
}



Measured memory_bytes: 3088
// https://atcoder.jp/contests/abc074/tasks/abc074_b
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define REP(i, n) FOR(i, 0, n)
#define FOR(i, s, n) for (int i = (s), i##_len = (n); i < i##_len; ++i)
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k, t, sum = 0;
    cin >> n >> k;
    REP(i, n) {
        cin >> t;
        sum += min(abs(k - t), t) * 2;
    }
    cout << sum << endl;
    return 0;
}


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

int main(){
/*    string s;
    cin >> s;
    if(s[1] > s[2]){
        cout<<"large"<<endl;
        s.replace(2, 1, s.substr(1,1));
    }else if(s[1] < s[2]){
        
    }
    cout << s << endl;    
    */
   int i;
   int tmp;
   int num = 0;
   cin >> i;
   int i2 = i / 100;
   int i1 = i / 10 - i2 * 10;
   int i0 = i - (i / 10) * 10;
//   cout<<"i2 = " << i2 << " i1 = " << i1 << " i0 = " << i0 << endl;
//   if()
    //100の位と10の位を比較
    int a[9] = {111,222,333,444,555,666,777,888,999};
    int min = 10000;
    for(int j = 0; j < 9; j++){
        tmp = a[j] - i;
        if((min > tmp) && (tmp >= 0)){
//            cout<<"tmp = "<<tmp<<endl;
//            cout<<"j = "<<j<<endl;
            min = tmp;
            num = j;
        }
    }
    i = a[num];
  
    cout<< i << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <cmath>

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

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

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

  int a = std::max(A * B, C * D);
  cout << a << endl;

  return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <vector>

#include <limits.h>

using namespace std;

typedef long long ll;

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;
}

const ll INF = LONG_LONG_MAX / 2;
const ll MAX_COST = 1000 * 1000 * 1000;

static ll do_solve(map<ll, ll> &dp, const ll n, const ll A, const ll B, const ll C, const ll D) {
    if (dp.find(n) != dp.end()) {
        return dp[n];
    }

    ll ans = INF;

    vector<ll> muls = {2, 3, 5};
    vector<ll> costs = {A, B, C};
    for (int i = 0; i < (int) muls.size(); i++) {
        const ll mul = muls[i];
        {
            const ll next = n / mul;
            if (next == 0) continue;
            ll cand = 0;
            cand += D * (abs(next * mul - n));
            cand += costs[i];
            cand += do_solve(dp, next, A, B, C, D);
            chmin(ans, cand);
        }
        {
            ll next = (n + mul - 1) / mul;
            ll cand = 0;
            cand += D * (abs(next * mul - n));
            cand += costs[i];
            cand += do_solve(dp, next, A, B, C, D);
            chmin(ans, cand);
        }
    }

    // It is always better to apply x2, x3, or x3 even if D == 1 and A, B, C == 10 ^ 9.
    if (n <= 2 * MAX_COST) {
        chmin(ans, n * D);
    }

    dp[n] = ans;
    return ans;
}

ll solve(const ll N, const ll A, const ll B, const ll C, const ll D) {
    map<ll, ll> dp;
    dp[0] = 0;
    dp[1] = D;
    return do_solve(dp, N, A, B, C, D);
}

int main(void) {
    int T;
    cin >> T;

    while (T-- > 0) {
        ll N, A, B, C, D;
        cin >> N >> A >> B >> C >> D;

        cout << solve(N, A, B, C, D) << endl;
    }

    return 0;
}


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

int main(){
  vector<vector<char>>  vec(3,vector<char>(3));
  for(int i=0;i<3;i++){
    for(int j=0;j<3;j++){
      cin>>vec.at(i).at(j);
    }
  }
  cout<<vec.at(0).at(0)<<vec.at(1).at(1)<<vec.at(2).at(2)<<endl;
  
}

Measured memory_bytes: 256
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols
    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])
    return ret


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_map_as_int(H):
    '''
    #→1,.→0として読み込む
    '''
    ret = []
    for _ in range(H):
        ret.append([1 if s == '#' else 0 for s in read()[:-1]])
        # 内包表記はpypyでは若干遅いことに注意
        # #numpy使うだろうからこれを残しておくけど
    return ret


MOD = 10**9 + 7
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right

N = read_a_int()
A = read_ints()
# counterすればよくね？
A_cnt = Counter(A)
# だけどTLEになるそう
# 同じ整数の個数をカウントした数をnとするとnC2の合計がそのボールを選ぶ通りの数
# nC2とn-1C2の差はn-1

total = 0
for _, v in A_cnt.items():
    total += v * (v - 1) // 2

for a in A:
    print(total - (A_cnt[a] - 1))


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

vector<long long> altura;

long long dp[100005];
int n;
long long solve(int atual){
    if(dp[atual] != -1) return dp[atual];
    if(atual < n-2){
        dp[atual] = min(abs(altura[atual] - altura[atual+1]) + solve(atual+1), abs(altura[atual] - altura[atual+2]) + solve(atual+2));
    }else if(atual == n-2){
        dp[atual] = abs(altura[atual] - altura[atual+1]);
    }else{
        dp[atual] = 0;
    }
    return dp[atual];
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++){
        long long v;
        cin >> v;
        altura.push_back(v);
        dp[i] = -1;
    }
    cout << solve(0) << endl;
    return 0;
}


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

unsigned long long int N, X, L[60] = {1}, P[60] = {1};

unsigned long int p_calc(unsigned long long N, unsigned long long X)
{
  if (X < 1)
  {
    return 0;
  }
  else if (N == 0)
  {
    return 1;
  }
  else if (X <= 1 + L[N - 1])
  {
    return p_calc(N - 1, X - 1);
  }
  // else if (X == 2 + L[N - 1])
  // {
  //   return P[N - 1] + 1;
  // }
  else // if (X <= 2 + 2 * L[N - 1])
  {
    return P[N - 1] + 1 + p_calc(N - 1, X - 1 - L[N - 1] - 1);
  }
  // else if (X == 3 + 2 * L[N - 1])
  // {
  //   return 2 * P[N - 1] + 1;
  // }
}

int main()
{
  unsigned int a, b, c, sum, count = 0, temp = 0;
  cin >> N >> X;
  // N = 2, X = 7;
  // N = 50, X = 4321098765432109;

  for (int i = 1; i <= N; i++)
  {
    L[i] = 2 * L[i - 1] + 3;
    P[i] = 2 * P[i - 1] + 1;
  }
  // cout << L[N] << endl;
  // cout << P[N] << endl;
  cout << p_calc(N, X) << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,n) for(int i=(a); i<(n); i++)
#define all(v) v.begin(), v.end()
#define fi first
#define se second
using namespace std;
using ll = long long;
using P = pair<int, int>;
const int INF = 1e9;
const int MOD = 1e9+7;
vector<bool> isp;

void sieve(int N) {
	isp.assign(N+1, true);
	isp[0] = false;
	isp[1] = false;
	for (int i=2; pow(i,2)<=N; i++) {
		if (isp[i]) for(int j=2; i*j<=N; j++) isp[i*j] = false;
	}
}

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

	sieve(100100);

	vector<bool> a(100100, false);
	rep(i, 100100) {
		if (i%2 && isp[i]) {
			if (isp[(i+1)/2]) a[i] = true;
		}
	}

	// rep(i, 100) cout << ans[i] <<" ";
	// cout << endl;

	vector<int> s(100101, 0);
	rep(i, 100100) {
		s[i+1] = s[i]+a[i];
	}

	// rep(i, 100) cout << s[i] <<" ";
	// cout << endl;

	int q; cin >> q;
	rep(i, q) {
		int l, r; cin >> l >> r;
		cout << s[r+1]-s[l] << endl;
	}
}

Measured memory_bytes: 1024
import java.io.InputStreamReader;
import java.util.Scanner;
 
public class Main {
	public static void main(String[] args) {
		try(Scanner scan = new Scanner(new InputStreamReader(System.in))){
			int N = scan.nextInt();

			int[] a = new int[N];
			long min = 999999999;
			
			for(int i = 0; i<N; i++){
				a[i] = scan.nextInt();
			}
			
			for(int i = -100; i<=100; i++){
                                long cost=0;
				for(int j = 0; j<N; j++){
long temp = a[j] - i;
				        cost+=temp*temp;
			        }
if(min>cost){
min=cost;
}
			}
			System.out.print(min);;
		}
	}
}

Measured memory_bytes: 9300
s1,s2 = [gets,gets].map(&:chomp).sort_by(&:size)

dp = Array.new(s1.size+1){Array.new(s2.size+1,0)}

s1.size.times do |y|
  dp[y+1][0] = y+1
end
s2.size.times do |x|
  dp[0][x+1] = x+1
end

1.upto(s1.size) do |y|
  1.upto(s2.size) do |x|
    if s2[x-1] == s1[y-1]
      dp[y][x] = dp[y-1][x-1]
    else
      dp[y][x] = [dp[y-1][x], dp[y][x-1], dp[y-1][x-1]].min + 1
    end
  end
end

puts dp[s1.size][s2.size]

Measured memory_bytes: 16708
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <climits>
#include <cfloat>
using namespace std;

int main()
{
    for(;;){
        string s;
        getline(cin, s);
        if(s == "END OF INPUT")
            return 0;

        int n = s.size();
        int num = 0;
        for(int i=0; i<n; ++i){
            if(s[i] == ' '){
                cout << num;
                num = 0;
            }else{
                ++ num;
            }
        }
        cout << num << endl;
    }
}

Measured memory_bytes: 0
import java.util.*;

public class Main {
    static void swap(int[] A, int i, int j) {
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }

    static int bubbleSort(int[] A, int N) {
        int flag = 1;
        int count = 0;
        while(flag == 1) {
            flag = 0;
            for(int j = N-1; j >=1; j--) {
                if(A[j] < A[j-1]) {
                    swap(A, j, j-1);
                    flag = 1;
                    count++;
                }
            }
        }
        return count;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++) a[i] = sc.nextInt();

        int c = bubbleSort(a, n);

        System.out.print(a[0]);
        for(int i = 1; i < n; i++) System.out.print(" " + a[i]);
        System.out.println();
        System.out.println(c);
    }
}


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

/*
 * 希尔排序思路：
 * 1. 选择增量进行分组
 * 2. 在每组内进行插入排序
 * 3. 缩小增量再执行1、2，直到增量为1（增量为1时也要在执行一次）
 */

long long cnt;
int a[1000001];
int n;
vector<int> G;

// 间隔为g的插入排序
void insertionSort(int a[], int n, int g){
    for (int i = g; i < n; i++){
        int v = a[i];
        int j = i - g;
        while(j >= 0 && a[j] > v){// 在每个分组内，进行插入排序
            a[j+g] = a[j];
            j -= g;
            cnt++;
        }
        a[j+g] = v;
    }
}

void shellSort(int a[], int n){
    // 生成间隔数列G
    int h = 1;
    while(h <= n){
        G.push_back(h);
        h = 3*h+1;
    }
    // 指定插入间隔g = G[i]
    for (int i = G.size()-1; i >= 0; i--){
        insertionSort(a, n, G[i]);
    }
}

int main(){
    cin>>n;
    for (int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    cnt = 0;
    shellSort(a, n);
    cout<<G.size()<<endl;

    for (int i = G.size()-1; i >= 0; i--){
        if (i != 0){
            printf("%d ", G[i]);
        }else{
            printf("%d\n", G[i]);
        }
    }
    printf("%d\n", cnt);
    for (int i = 0; i < n; i++){
        printf("%d\n", a[i]);
    }
    return 0;
}


Measured memory_bytes: 7156
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <cstdint>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <cctype>
#include <functional>
#include <ctime>
#include <cmath>
#include <limits>
#include <numeric>
#include <type_traits>
#include <iomanip>
#include <float.h>
#include <math.h>
using namespace std;
using ll = long long;


unsigned euclidean_gcd(unsigned a, unsigned b) {
    if (a < b) return euclidean_gcd(b, a);
    unsigned r;
    while ((r = a % b)) {
        a = b;
        b = r;
    }
    return b;
}

class UnionFind {
public:
    vector <ll> par;
    vector <ll> siz;
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL) {
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    ll root(ll x) {
        while (par[x] != x) {
            x = par[x] = par[par[x]];
        }
        return x;
    }
    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

long long modinv(long long a, long long mod) {
    return modpow(a, mod - 2, mod);
}

int main() {
    string a, b, c;
    cin >> a >> b >> c;
    queue<char> aa;
    queue<char> bb;
    queue<char> cc;
    for (int i = 0; i < a.size(); i++) {
        aa.push(a[i]);
    }
    for (int i = 0; i < b.size(); i++) {
        bb.push(b[i]);
    }
    for (int i = 0; i < c.size(); i++) {
        cc.push(c[i]);
    }
    int i = 0;
    while (true) {
        if (i == 0) {
            if (aa.empty()) {
                cout << 'A' << endl;
                break;
            }
            i = aa.front() - 'a';
            aa.pop();
        }
        else if (i == 1) {
            if (bb.empty()) {
                cout << 'B' << endl;
                break;
            }
            i = bb.front() - 'a';
            bb.pop();
        }
        else{
            if (cc.empty()) {
                cout << 'C' << endl;
                break;
            }
            i = cc.front() - 'a';
            cc.pop();
        }
    }
}

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

int main(){
    int N;  cin >> N;
    vector<int> H(N);
    for(int i=0; i<N; i++) cin >> H[i];

    int ans = 0;
    int cnt = 0;
    for(int i=1; i<N; i++){
        if(H[i-1] >= H[i]) cnt++;
        else cnt = 0;

        ans = max(ans, cnt);
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
D, G=list(map(int, input().split()))
PC=[0]+[list(map(int, input().split())) for _ in range(D)]

def function(G, i):
    # print("i:",i)
    if i==0:
	    return 1001
    n=min(G//(i*100), PC[i][0])
    # print("n:",n)
    s=n*i*100
    # print("s:",s)
    if n==PC[i][0]:
        s+=PC[i][1]
        # print("s:",s)
    if s<G:
        n+=function(G-s, i-1)
        # print("n:",n)
    return min(n, function(G,i-1))
print(function(G, D))


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

#define rep(i,n) for(int i=0; i<(n); i++)
#define reps(i,n) for(int i=1; i<(n); i++)
#define pii pair<int,int>
#define all(x) (x).begin(), (x).end()
#define int long long
#define setout(n,x) setw(n) << setfill(x)
#define Fixed fixed << setprecision(10)
const int INF = 0x3f3f3f3f;
const long long LINF = 0x3f3f3f3f3f3f3f3fLL;
const long long mod = 1000000007;
using namespace std;
long long h[10000010],x[10000010];

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

  int r,g,b;
  cin>>r>>g>>b;

  r=r*100+g*10+b;
  if(r%4==0) cout<<"YES"<<'\n';
  else cout<<"NO"<<'\n';
}



Measured memory_bytes: 256
#include <cassert>
#include <cstdio>
#include <cmath>
#include <iostream>
#include <iomanip>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <numeric>
#include <algorithm>

using namespace std;
using lint = long long;
constexpr int MOD = 1000000007, INF = 1010101010;
constexpr lint LINF = 1LL << 60;

template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
	for (const auto &e : vec) os << e << (&e == &vec.back() ? "\n" : " ");
	return os;
}

#ifdef _DEBUG
template <class T>
void dump(const char* str, T &&h) { cerr << str << " = " << h << "\n"; };
template <class Head, class... Tail>
void dump(const char* str, Head &&h, Tail &&... t) {
	while (*str != ',') cerr << *str++; cerr << " = " << h << "\n";
	dump(str + (*(str + 1) == ' ' ? 2 : 1), t...);
}
#define DMP(...) dump(#__VA_ARGS__, __VA_ARGS__)
#else 
#define DMP(...) ((void)0)
#endif

int main() {

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

	int a, b;
	cin >> a >> b;

	string A = string(b, a + '0');
	string B = string(a, b + '0');

	if (A < B) cout << A << "\n";
	else cout << B << "\n";

	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 < n; i++)

string n;
int ans = 0;

void calc(string num){
    int c_3 = 0, c_5 = 0, c_7 = 0;
    rep(i, num.size()){
        if(num[i] == '3') c_3++;
        if(num[i] == '5') c_5++;
        if(num[i] == '7') c_7++;
    }
    if(c_3 == 0 || c_5 == 0 || c_7 == 0)
        return;
    else if(stoi(num) <= stoi(n)){
        ans++;
    }
}
void dfs(int dp, string num){
    if(dp == n.size()){
        return;
    }
    rep(i, 3){
        if(i == 0){
            num.push_back('3');
            calc(num);
            dfs(dp+1, num);
        }
        if(i == 1){
            num[dp] = '5';
            calc(num);
            dfs(dp+1, num);
        }
        if(i == 2){
            num[dp] = '7';
            calc(num);
            dfs(dp+1, num);
        }
    }
}
int main(void){
    cin >> n;
    dfs(0, "");
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
	int n,a[200001],i,max1,max2,index1,index2;
	scanf("%d",&n);
	scanf("%d",&a[1]); max1=a[1]; index1=1;
	scanf("%d",&a[2]);
	if(a[1]<a[2]){
		max2=max1;
		max1=a[2];
		index2=index1;
		index1=2;
	}else{
		max2=a[2];
		index2=2;
	}
	for(i=3;i<=n;i++){
		scanf("%d",&a[i]);
		if(a[i]>max1){
			max2=max1;
			max1=a[i];
			index2=index1;
			index1=i;
		}else if(a[i]>max2){
			max2=a[i];
			index2=i;
		}
	}
	
	for(i=1;i<=n;i++){
		if(i==index1)printf("%d\n",max2);
		else printf("%d\n",max1);
	}
		
	return 0;
}

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

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if(c <= b)
    cout << "delicious" << endl;
  else if(c - b <= a)
    cout << "safe" << endl;
  else
    cout << "dangerous" << endl;
}

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

#define MAX_V 100001
#define INF (1<<29)

using namespace std;

typedef pair<int,int> P;

vector<int>G[MAX_V];
vector<P> bridge;
int pnum[MAX_V],lowest[MAX_V],num;
bool used[MAX_V];

int dfs(int v,int prev){
  pnum[v]=num,lowest[v]=num;
  num++;
  used[v]=true;

  for(int i=0;i<G[v].size();i++){
    int nx=G[v][i];
    if(!used[nx]){
      dfs(nx,v);
      lowest[v]=min(lowest[v],lowest[nx]);
      if(pnum[v]<lowest[nx])
        bridge.push_back(make_pair(min(v,nx),max(v,nx)));
    }
    else if(nx!=prev){
      lowest[v]=min(lowest[v],pnum[nx]);
    }
  }
}

int main(void){
  int n,m;
  cin >> n >> m;
  for(int i=0;i<m;i++){
    int a,b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  fill(used,used+MAX_V,false);
  fill(lowest,lowest+MAX_V,INF);
  fill(pnum,pnum+MAX_V,INF);
  num=0;
  bridge.clear();
  dfs(0,-1);
  sort(bridge.begin(),bridge.end());
  //bridge.erase(unique(bridge.begin(),bridge.end()),bridge.end());
  for(int i=0;i<bridge.size();i++)
    cout << bridge[i].first << " " << bridge[i].second << endl;

  return 0;
}

Measured memory_bytes: 5996
#include <stdio.h>

int main(void)
{
    // N:人数, K:開始時のポイント, Q:正解が出た回数, i番目に正解したのは参加者Ai
    // 正解した人以外のN-1人のポイントが1減る
    // 終了時にポイントが0以下の参加者は敗退する
    int N, K, Q, A[100000], P[100000], i, j, s; // P:参加者のポイント

    scanf("%d %d %d", &N, &K, &Q);

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

    for(j=0; j<N; j++){
	P[j] = K; // ポイントを初期化
	P[j] -= Q; // 正解が出た回数だけ全員のポイントを減らす
    }

    for(i=0; i<Q; i++){
	s = A[i]-1; // 正解した人の番号をsに代入
	P[s]++; // 正解した人のポイントを1増やす
    }

    for(j=0; j<N; j++){
	if(P[j] > 0){
	    printf("Yes\n");
	}

	else{
	    printf("No\n");
	}
    }

    return 0;
}

Measured memory_bytes: 1280
// Hail god Yato
 
#include <bits/stdc++.h> 
using namespace std;
 
#define hs ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef long long ll;
const ll MOD = 1000000007;
const ll INF = 1e18;
const ll MAX = 500005;
//
//

struct mi {
    ll v; explicit operator ll() const { return v; }
    mi() { v = 0; }
    mi(ll _v) { 
        v = (-MOD < _v && _v < MOD) ? _v : _v % MOD;
        if (v < 0) v += MOD;
    }
    friend bool operator==(const mi& a, const mi& b) { 
        return a.v == b.v; }
    friend bool operator!=(const mi& a, const mi& b) { 
        return !(a == b); }
    friend bool operator<(const mi& a, const mi& b) { 
        return a.v < b.v; }
   
    mi& operator+=(const mi& m) { 
        if ((v += m.v) >= MOD) v -= MOD; 
        return *this; }
    mi& operator-=(const mi& m) { 
        if ((v -= m.v) < 0) v += MOD; 
        return *this; }
    mi& operator*=(const mi& m) { 
        v = v*m.v%MOD; return *this; }
    mi& operator/=(const mi& m) { return (*this) *= inv(m); }
    friend mi pow(mi a, ll p) {
        mi ans = 1; assert(p >= 0);
        for (; p; p /= 2, a *= a) if (p&1) ans *= a;
        return ans;
    }
    friend mi inv(const mi& a) { assert(a.v != 0); 
        return pow(a,MOD-2); }
        
    mi operator-() const { return mi(-v); }
    mi& operator++() { return *this += 1; }
    mi& operator--() { return *this -= 1; }
    mi operator++(int) { mi temp; temp.v = v++; return temp; }
    mi operator--(int) { mi temp; temp.v = v--; return temp; }
    friend mi operator+(mi a, const mi& b) { return a += b; }
    friend mi operator-(mi a, const mi& b) { return a -= b; }
    friend mi operator*(mi a, const mi& b) { return a *= b; }
    friend mi operator/(mi a, const mi& b) { return a /= b; }
    friend ostream& operator<<(ostream& os, const mi& m) {
        os << m.v; return os;
    }
    friend istream& operator>>(istream& is, mi& m) {
        ll x; is >> x;
        m.v = x;
        return is;
    }
};

typedef vector<mi> vmi;
typedef pair<mi,mi> pmi;
typedef vector<pmi> vpmi;
mi facs[MAX];
mi facInvs[MAX];
 
mi choose(mi _a, mi _b) {
    ll a = (ll) _a, b = (ll) _b;
    if (b > a) return 0;
    if (a < 0) return 0;
    if (b < 0) return 0;
    mi cur = facs[a];
    cur = cur * facInvs[b];
    cur = cur * facInvs[a-b];
    return cur;
}
 
void initFacs() {
    facs[0] = 1;
    facInvs[0] = 1;
    for(int i = 1; i < MAX; i++) {
        facs[i] = (facs[i-1] * i);
        facInvs[i] = inv(facs[i]);
    }
}

void solve(){
    initFacs();
    
    int n, m;
    cin>>n>>m;
    mi ans = 0;
    ans = choose(m, n)*facs[n];
    // ans = ans*ans;
    mi derangements = 0;
    int cur = 1;
    for(int i = 1; i <= n; i++){
        derangements += cur*choose(n, i)*choose(m-i, n-i)*facs[n-i];
        cur = cur*-1;
    }
    // cout<<derangements<<"\n";
    derangements *= ans;
    ans *= ans;
    cout<<ans - derangements;
}
int main(){ 
        hs;
        ll t;
        t=1;
        // cin>>t;
        for (int i=1; i<=t; i++){
                //cout<<"Case #"<<i<<": ";
                solve();
         }
        return 0; 
}

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

int main(){
    int N; cin >> N;
    vector<int> A, B, C;
    int a;
    for (int i = 0; i < N; i++)    {cin >> a; a--; A.push_back(a);}
    for (int i = 0; i < N; i++)    {cin >> a; B.push_back(a);}
    for (int i = 0; i < N-1; i++)  {cin >> a; C.push_back(a);}
    
    int points = 0;
    for (int i = 0; i < N; i++)
    {
        points += B[A[i]];
        //cout << B[A[i]] << endl;
        if(i-1>=0 && A[i] - A[i-1] ==1) points += C[A[i-1]];
    }
    
    cout << points << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for (int i=0;i<(n);i++)
#define int long long  
#define INF 1145141919810893
signed main(){
    string S;
    int G[104][104][30]={};
    cin >> S;
    bool c=0;
    int N=S.size();
    REP(i,N){
        G[0][i][S[i]-'a']=1;
    }
    REP(i,N){
        if(i==0)continue;
        REP(j,N-i){
            REP(k,26){
                if(G[i-1][j][k]==1 || G[i-1][j+1][k]==1){
                    G[i][j][k]=1;
                }
            }
        }
    }
    REP(i,N){
        REP(k,26){
            c=0;
            REP(j,N-i){
                if(G[i][j][k]==0){
                    c=1;
                }
            }
            if(c==0){
                cout << i << endl;
                return 0;
            }
        }
    }
    
	return 0;
}


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

using namespace std;
#define mod 1000000007
#define ll long long

int main(){
   ll n,m;
   cin>>n;
   ll mo;
   m=n/500;
   ll ans=m*1000;
   mo=n%500;
   m=mo/5;
   ans+=5*m;
   cout<<ans<<endl;
}

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

int main(void) {
  int A, B, C, K;
  cin >> A >> B >> C >> K;

  int maxABC = max(A, max(B, C));
  int maxABCpowK = maxABC;
  while (K--) maxABCpowK *= 2;
  int answer = A + B + C - maxABC + maxABCpowK;
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
#include <sstream>
#include <iomanip>
using namespace std;
typedef long long int ll;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define YES cout << "YES" << endl
#define Yes cout << "Yes" << endl
#define NO cout << "NO" << endl
#define No cout << "No" << endl

const int mod = 1000000007;
#define PI 3.14159265359;

void P(int x) {cout << x << endl;}
void P(long x) {cout << x << endl;}
void P(double x) {cout << x << endl;}
void P(ll x) {cout << x << endl;}
void P(string x) {cout << x << endl;}
void P(char x) {cout << x << endl;}

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


int main() {
  int n;
  cin >> n;
  int ans = 0;
  rep (i, n) {
    ans += i + 1;
  }
  P(ans);
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>

using namespace std;

int n, s[102];

int main()
{
    cin >> n;
    int S = 0;
    for(int i = 1;i <= n;i++)
        cin >> s[i], S += s[i];
    sort(s + 1, s + n + 1);
    bool ok = 0;
    if(S % 10 != 0)  {
        cout << S << "\n";
        return 0;
    }
    for(int i = 1;i <= n;i++)  {
        if((S - s[i]) % 10 != 0)  {
            S -= s[i];
            ok = 1;
            break;
        }
    }
    if(ok == 0)  {
        S = 0;
    }
    cout << S << "\n";
    return 0;
}


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

using namespace std; using ll=long long; const int INF=1e9; using P=pair<int,int>;

int main() {
  int a,b,c,d,e,f; cin>>a>>b>>c>>d>>e>>f;
  double mx=-1, ee=(double)e/100.0; int ax=-1,ay=-1;

  set<int> w, v;
  for(int i=0;i<=30;i++) {
    for(int j=0;j<=30;j++) {
      int wt = 100 * (a * i + b * j);
      if (0 < wt && wt < f) w.insert(wt);
    }
  }
  for(int i=0;i<=f/c;i++) {
    for(int j=0;j<=f/c;j++) {
      int vv = i*c + j*d;
      if (vv < f) v.insert(vv);
    }
  }

  for(int x:w) {
    for(int y:v) {
      if (x+y > f) continue;
      double zz = (double)y / (double)x;
      if (mx < zz && zz < ee + 1e-6) {
        mx=zz; ax=x+y; ay=y;
      }
    }
  }

  cout<<ax<<" "<<ay<<endl;
}

Measured memory_bytes: 384
from collections import deque


def main():
    s = input()
    q = int(input())
    d = deque(s)
    is_reversed = False

    for _ in range(q):
        query = list(input().split())

        if query[0] == "1":
            if is_reversed:
                is_reversed = False
            else:
                is_reversed = True

        elif query[0] == "2":
            if query[1] == "1":
                if is_reversed:
                    d.append(query[2])
                else:
                    d.appendleft(query[2])
            elif query[1] == "2":
                if is_reversed:
                    d.appendleft(query[2])
                else:
                    d.append(query[2])

    if is_reversed:
        print(*(list(d)[::-1]), sep="")
    else:
        print(*list(d), sep="")


if __name__ == "__main__":
    main()


Measured memory_bytes: 120260
import sys
import math
input = sys.stdin.readline

#intの場合
  
A, B ,N  = map(int,input().split())

if N > B - 1 and A <= B:
  print (A-1)
elif A > B  and N >= B - 1 :
  N = B - 1
  y = math.floor( A * N /B) - A * math.floor( N / B)
  print(y )
# A < B < N
else :
  y = math.floor( A * N /B) - A * math.floor( N / B)
  print(y )


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

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

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

using namespace std;

int main() {
  string s;
  cin >> s;
  int result = 0;

  int start = -1;
  rep(i, s.length()) {
    if (s[i] == 'A') {
      start = i;
      break;
    }
  }
  int end = -1;
  for (int i = s.length() - 1; i >= 0; i--) {
    if (s[i] == 'Z') {
      end = i;
      break;
    }
  }

  cout << (end - start + 1) << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;

typedef long long ll;
typedef pair<int, int> P;

const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1000000000000000000L;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
const int ddx[] = {1, 1, 0, -1, -1, -1, 0, 1};
const int ddy[] = {0, 1, 1, 1, 0, -1, -1, -1};

int d[10][10];

int main() {
    int H, W;
    cin >> H >> W;
    rep(i, 10) {
        rep(j, 10) {
            cin >> d[i][j];
        }
    }

    rep(k, 10) {
        rep(i, 10) {
            rep(j, 10) {
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }

    int ans = 0;
    rep(i, H) {
        rep(j, W) {
            int a;
            cin >> a;
            if(a != -1) ans += d[a][1];
        }
    }
    cout << ans << endl;
}


Measured memory_bytes: 256