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

#define pii pair<int,int>
#define ff first
#define ss second
#define int long long

int dp[3001][3001];
pii nxt[3001][3001];
bool taken[3001][3001];
int n, m;
string s, t;

int32_t main()
{
    cin>>s>>t;
    n=s.length();
    m=t.length();
    
    for(int i=1; i<=n; ++i)
    {
        for(int j=1; j<=m; ++j)
        {
            if(s[i-1]!=t[j-1])
            {
                if(dp[i-1][j]<dp[i][j-1])
                {
                    dp[i][j]=dp[i][j-1];
                    nxt[i][j]={i, j-1};
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                    nxt[i][j]={i-1, j};
                }
            }
            else
            {
                dp[i][j]=dp[i-1][j-1]+1;
                nxt[i][j]={i-1, j-1};
                taken[i][j]=1;
            }
        }
    }
    // cout<<dp[n][m]<<"\n";
    string ans;
    int i=n, j=m;
    while(1)
    {
        if(taken[i][j])
            ans+=s[i-1];
        if(i==0 || j==0)
            break;
        tie(i, j)=nxt[i][j];
    }
    reverse(ans.begin(), ans.end());
    cout<<ans;
}


Measured memory_bytes: 220160
fun main(args: Array<String>){
    val keys = listOf(readLine()!!.toInt(),readLine()!!.toInt(),readLine()!!.toInt(),readLine()!!.toInt(),readLine()!!.toInt())
    val max = readLine()!!.toInt()
    var a : Boolean = false
    for (key in keys){
        for (key1 in keys){
            if(key - key1 > max) a = true
        }
    }
    println(if (a) ":(" else "Yay!")
}

Measured memory_bytes: 32300
#include <stdio.h>
int main(void)
{
    char S[1004];
    scanf("%s",S);
    int i=0;
    while(S[i]!='\0')
        i++;
    if(S[i-1]=='s')
    {
        S[i]='e';
        S[i+1]='s';
        S[i+2]='\0';
    }
    else
    {
        S[i]='s';
        S[i+1]='\0';
    }
    printf("%s\n",S);
    return(0);
}

Measured memory_bytes: 1648
from collections import defaultdict

N, K, *A = map(int, open(0).read().split())

x = [0] * (N + 1)
for i in range(N):
    x[i + 1] = x[i] + A[i]
    
y = [(x[i] - i) % K for i in range(N + 1)]

ctr = defaultdict(int)
ans = 0
for j in range(N + 1):
    ans += ctr[y[j]]
    ctr[y[j]] += 1
    if j - K + 1 >= 0:
        ctr[y[j - K + 1]] -= 1
print(ans)


Measured memory_bytes: 144972
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
	int mod = 1000000007;
  
  	int sub(int a, int b){
        a -= b;
        if(a < 0)a += mod;
        return a;
    }
  
    public int findNumWaysToDistributeCandies(int n, int k, int[] a) {
        int[][] prefix = new int[n+1][k+1];
        int[][] dp = new int[n+1][k+1];

        for(int i=0;i<=n;++i) {
            dp[i][0]=1;
            prefix[i][0]=1;
        }

        for(int i=1;i<=k;++i) {
            prefix[0][i]=1;
        }

        for(int i=1;i<=n;++i) {
            for(int j=1;j<=k;++j) {
                int low = (j-a[i]-1)>=0?prefix[i-1][j-a[i]-1]:0;
                int high = prefix[i-1][j];
                dp[i][j]=(sub(high,low))%mod;
                prefix[i][j]=(prefix[i][j-1]+dp[i][j])%mod;
            }
        }
        return dp[n][k];
    }

    public static void main(String[] args) {
        Main m = new Main();
        InputStreamReader r=new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(r);
        try {
            String[] line1 = reader.readLine().split(" ");
            int n = Integer.parseInt(line1[0]);
            int k = Integer.parseInt(line1[1]);
            int[] a = new int[n+1];
            String[] line2 = reader.readLine().split(" ");
            for(int i=0;i<n;++i) {
                a[i+1]=Integer.parseInt(line2[i]);
            }
            int res = m.findNumWaysToDistributeCandies(n,k,a);
            System.out.println(res);
        } catch (IOException e) {

        }
    }
}


Measured memory_bytes: 126036
//   _/                _/                 _/_/_/   _/
//_/_/_/_/   _/_/   _/_/_/_/   _/_/    _/       _/_/
// _/     _/    _/   _/     _/    _/  _/_/_/     _/
//_/     _/    _/   _/     _/    _/  _/    _/   _/
// _/_/   _/_/       _/_/   _/_/      _/_/     _/
#include<iostream>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<set>
#include<map>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int inf=1e9;
const ll INF=1e18;
const double pi=3.1415926535897932384626433832;
int main() {
  cin.tie(0),cout.tie(0);
  ios::sync_with_stdio(false);
  // 初めに思ったこと：重複していない値は全て残したい
  ll n,a,cnt=0;
  cin >> n;
  map<int,int> m;
  for(int i=0; i<n; i++) {
    cin >> a;
    m[a]++;
  }
  // 重複していたら1つを残して食べる
  for(auto p:m) {
    if(p.second>1) {
      cnt+=p.second-1;
    }
  }
  // 1回の操作で2つずつ減っていくので食べた数=cntは2の倍数である必要がある
  if(cnt%2==0) {
    cout << n-cnt << endl;
  }
  // cntが奇数のとき、1つしか残っていない数を余計に1つだけ食べている
  else {
    cout << n-cnt-1 << endl;
  }
}

Measured memory_bytes: 4992
// 154 C

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <numeric>
#include <queue>
#include <iomanip>

using namespace std;

int main(){
    long long int n, k;
    long double max=0, buf;
    cin >> n >> k;
    vector<long double> v, sum;
    int tmp;
    for(int i=0; i<n; i++){
        cin >> tmp;
        v.push_back((tmp+1.0)/2.0);
    }

    sum.push_back(0);
    for(int i=0; i<n; i++){
        sum.push_back(sum.at(i) + v.at(i));
    }

    for(int i=0; i<n-k+1; i++){
        buf = sum.at(i+k) - sum.at(i);
        if(max<=buf) max = buf;
    }
    cout << fixed << setprecision(6) << max << endl;
    return 0;
}


Measured memory_bytes: 12268
#include<bits/stdc++.h>
using namespace std;
#define ll long long 
// memo  fixed  setprecision(20);
using vvll = vector<vector<ll>>;
ll mod =1e9+7;
/*"itob" int to "N"base */           template<typename TypeInt> string itob(const TypeInt v, int base){static const char table[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";string ret;static numeric_limits<TypeInt> t;TypeInt n = v;if (t.is_signed) {if (v < 0) n *= -1;}while (n >= base) {ret += table[n%base];n /= base;}ret += table[n];if (t.is_signed) {if (v < 0 && base == 10) ret += '-';}reverse(ret.begin(), ret.end());return ret;}
/*"chmin" a = MAX*/                  template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
/*"chmax" a = MIN*/                  template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
/*"ctoi"  char to int*/              int ctoi(char c) {return c-'0';}
/*"gcd"   MAX Euclidean */           ll gcd(ll a,ll b){if(b==0)return a; return gcd(b,a%b);}
    /*"lcm"   MIN*/                      ll lcm(ll a,ll b){ll g = gcd(a,b);return a/g*b;}
/*"primecheck"If prime,return true.*/bool primecheck(ll n){if(n < 2) return false;else{for(int i = 2; i * i <= n; i++){if(n % i == 0) return false;}return true;}}
string  reverserange(string s,ll a,ll b){reverse(s.begin()+a-1,s.begin()+b); return s;}
ll modpow(ll a,ll n, ll mod){ll res = 1;while(n>0){if (n%2==1){res = res * a % mod;}a = a * a % mod;n/=2;}return res;}
int main() {
    int k;
    cin >> k;
    vector<ll>che(k+100);
    che.at(1)=7%k;
    for(int i=2;i<=k;i++){
        che.at(i)=(che.at(i-1)*10+7)%k;
    }
    for(int i=1;i<=k;i++){
        if(che.at(i)==0){
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
}
    



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

long calc_part(long s, long &n) {
  //cout << "calc_part( " << s << " )" ;//////////////
  long S=s;
  n=1;
  long d=10;
  while (s/d > 0) {
    long nn;
    S += calc_part(s%d, nn);
    S += s/d*nn;
    n += nn;
    d *= 10;
  }
  //cout << s << ":" << S << ", " << n << endl;
  return S;
}

int main() {
  long S;
  long n;
  cin >> S;
  cout << calc_part(S, n) << endl;
  return 0;
}


Measured memory_bytes: 256
open System

// prelude
let readStr () = stdin.ReadLine()

let readInt () = stdin.ReadLine() |> int
let readInts () = stdin.ReadLine().Split() |> Array.map int

let pair = function
| [|a; b|] -> (a, b)
| _ -> failwith "owatta"

let triple = function
| [|a; b; c|] -> (a, b, c)
| _ -> failwith "owatta"

let inc n = n + 1
let dec n = n - 1

let inline flip f a b = f b a
let rec fix f = fun x -> (f (fix f)) x

module Option =
  let getOr defaultValue = function
  | Some x -> x
  | None -> defaultValue

module Array =
  let modify (arr: _ []) i f =
    arr.[i] <- f arr.[i]

module Array2D =
  let modify (arr: _ [,]) i j f =
    arr.[i, j] <- f arr.[i, j]

// start
  
let N=101010
let isPrime =
  let primes=Array.create N true
  primes.[0] <- false
  primes.[1] <- false
  for p in 0..(N-1) do
    if primes.[p] then do
      let rec go i =
        if i>=N then ()
        else
          primes.[i]<-false
          go (i+p)
      go (2*p)
  Array.get primes

let like2017sum=
  let s=Array.init N (fun n -> if n%2=1&&isPrime n && isPrime ((n+1)/2) then 1 else 0)
  for i in 1..(N-1) do
    Array.modify s i ((+) s.[i-1])
  fun l r -> s.[r]-s.[l-1]

let Q=readInt()
for _ in 1..Q do
  let (l,r) = readInts() |> pair
  like2017sum l r
  |> printfn "%d"

Measured memory_bytes: 18988
N, M = gets.chop.split.map(&:to_i)
ac = 0
pn = 0

res_ac = Array.new(N,0)

res_pn = Array.new(N,0)

M.times do |i|
  p, s = gets.chop.split

  p = p.to_i

  if s == 'WA' && res_ac[p-1] == 0
    res_pn[p-1] += 1
  end

  if s == 'AC' && res_ac[p-1] == 0
    res_ac[p-1] = 1
    ac += 1
    pn += res_pn[p-1]
  end

end

puts ac
puts pn



Measured memory_bytes: 3324
#include <iostream>
#include <vector>
//#include <string>
#include <algorithm>
//#include <math.h>
//#include <queue>
//#include <stack>
//#include <iomanip>

// sometimes used
//#include <set>
//#include <map>
//#include <numeric>
//#include <list>
//#include <deque>
//#include <unordered_map>

typedef long long LL;
//typedef long double LD;
using namespace std;
 
//#define MOD 1000000007
//#define MAX 100100
//#define NIL -1

int main() {
    vector<LL> a(3);
    LL k;
    LL ans;
    cin >> a[0] >> a[1] >> a[2];
    cin >> k;

    sort(a.begin(), a.end());
    for(LL i=0; i<k; i++){
        a[2]*=2;
    }
    ans=a[0]+a[1]+a[2];
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 3584
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
#include <math.h>
#include <stack>
#include <map>
#define x first 
#define y second 
using namespace std;
typedef long long LL;
const int N = 1e5+5;
const int INF = 0x3f3f3f3f;
vector<string>a;
int main(){
  int n,m;
  a.clear();
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;++i){
    string tmp;cin>>tmp;
    a.push_back(tmp);
  }
  sort(a.begin(),a.end());
  for(int i=0;i<n;++i)cout<<a[i];
    printf("\n");
  return 0;
}

Measured memory_bytes: 256
# 初期入力
import sys
#input = sys.stdin.readline  #文字列では使わない
N = int(input())
num =[111,222,333,444,555,666,777,888,999]
for i in range(8):
    if N <= num[0]:
        ans =111
        break
    elif  num[i] < N <= num[i+1]:
        ans =num[i+1] 

print(ans)

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

struct Node {
	int next[26]{}, length{1 << 30};
	int path{1 << 30};
};

int main()
{
	char a[200000]{};
	scanf("%s", a);
	int n;
	n = strlen(a);
	std::vector<Node> dp(n + 1);
	for (int i = 0; i < 26; i++)
		dp[n].next[i] = n + 1;
	dp[n].length = 1;
	for (int i = n - 1; i >= 0; i--)
	{
		Node& node{dp[i]};
		for (int j = 0; j < 26; j++)
			node.next[j] = dp[i + 1].next[j];
		node.next[a[i] - 'a'] = i + 1;
		for (int j = 0; j < 26; j++)
			if (dp[node.next[j]].length + 1 < node.length)
			{
				node.length = dp[node.next[j]].length + 1;
				node.path = node.next[j];
			}
	}
	int index{};
	while (dp[index].path <= n)
	{
		index = dp[index].path;
		putchar(a[index - 1]);
	}
	for (int i = 0; i < 26; i++)
	{
		if (dp[index].next[i] == n + 1)
		{
			putchar(i + 'a');
			break;
		}
	}
	putchar('\n');
	
	return 0;
}

Measured memory_bytes: 22272
#include <stdio.h>
#include <string.h>
int main(void)
{
  char a, b;
  int tbl[256]={0};
  tbl['H']=+1;
  tbl['D']=-1;
  scanf("%c %c",&a, &b);
  printf("%c\n",tbl[a]*tbl[b]<0?'D':'H');
}



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

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

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

int main(){
  int N,K;
  cin >> N >> K;
  string S;
  cin >> S;
  char c=S.at(0);
  int count=0;
  bool flag=false;
  for(int i=1;i<N;i++){
    if(count==K){
      break;
    }
    if(c!=S.at(i)){
      S.at(i)=c;
      flag=true;
    }else{
      if(flag){
        count++;
        flag=false;
      }
    }
  }
  vector<int> v;
  int n=0;
  for(int i=0;i<N;i++){
    if(c==S.at(i)){
      n++;
    }else{
      v.push_back(n);
      n=1;
      c=S.at(i);
    }
  }
  v.push_back(n);
  int ans=0;
  for(int i=0;i<v.size();i++){
    ans+=v.at(i)-1;
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 1020
N, M, C = map(int, input().split())
Bs = list(map(int, input().split()))
As = [[int(i) for i in input().split()] for _ in range(N)]

ans = []
for A in As:
    ans.append(sum([a * B for a, B in zip(A, Bs)]) + C > 0)
print(sum(ans))


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

int main() {
    ll n,a,b,ans, m;

    cin >> n >> a>> b;

    ans = n / (a+b) * a;
    m = n % (a + b);

    if (m <= a) {
        ans += m;
    } else {
        ans += a;
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <limits.h>
#include <queue>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
#define REP(i, n) for(int i=0; i<n; i++)

int A[30];
int main(){
    string S;
    cin >> S;
    int N = S.length();
    //REP(i,N){
    //    char x = S[i];
    //    A[x-'a']++;
    //}

    int ans = 0;
    int head = 0, tail = N-1;
    while(head < tail){
        char first = S[head];
        char last = S[tail];
        if(last != first){
            if(last != 'x' && first != 'x'){
                ans = -1;
                break;
            }
            else if(last == 'x'){
                tail--;
                ans++;
            }
            else if(first == 'x'){
                head++;
                ans++;
            }
        }
        else{
            head++;
            tail--;
        }
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
#define rep(i, n) for(int i=0; i<((int)(n)); i++)
#define rep1(i, n) for(int i=1; i<=((int)(n)); i++)
#define rrep(i, n) for(int i=((int)(n)-1); i>=0; i--)
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
typedef pair<ll, ll> P;
typedef pair<ll, P> PP;
template<class T> bool chmin(T&x,T y){if(x>y){x=y;return true;}return false;}
template<class T> bool chmax(T&x,T y){if(x<y){x=y;return true;}return false;}
ll gcd(ll x, ll y){ if(x>y) swap(x, y);while(x!=0){ y%=x; swap(x, y); }return y; }
ll mpow(ll x, ll r){if(r==0) return 1;if(r%2==1){ return x*mpow(x, r-1)%mod; }else{ ll aa = mpow(x, r/2); return aa*aa%mod; }}

int main(){
	int N; cin >> N;
	vector<string> s;
	rep(i, N){
		string a; cin >> a;
		s.pb(a);
	}
	sort(ALL(s));
	int ans = 0;
	rep(i, N){
		if(i==0) ans = 1;
		else{
			if(s[i] != s[i-1]) ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 11660
#include<bits/stdc++.h>
using namespace std;
long long a,b,c,d,ans,k;
map<int,int>n;
int main()
{
	cin>>a>>b;
	n[0]++;
	while(a--)
	{
		cin>>c;
		d=(d+c)%b;
		n[d]++;
	}
	for(map<int,int>::iterator it=n.begin();it!=n.end();it++)
	{
		k=it->second;
		ans+=(k*k-k)/2;
	}
	cout<<ans<<endl;
}

Measured memory_bytes: 3200
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
  int a,b,c,x,y;
  cin >> a >> b >> c >> x >> y;
  cout << min({a*x+b*y,c*2*x+b*max(0,y-x),a*max(0,x-y)+c*2*y}) << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string.h>
#include <vector>
#include <limits>
#include <algorithm>
#include <stdlib.h>
#include <math.h>
#include <deque>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <assert.h>
#include <sstream>
#include <type_traits>
#define SET(x,y) x |= (1 << y)
#define CLEAR(x,y) x &= ~(1<< y)
#define READ(x,y) ((0u == (x & (1<<y)))?0u:1u)
#define TOGGLE(x,y) (x ^= (1<<y))
#define watch(x) cout << (#x) << " is " << (x) << endl
#define pb push_back
#define mp make_pair
#define si(n) scanf("%d",&n)
#define sf(n) scanf("%f",&n)
#define sl(n) scanf("%lld",&n)
#define slu(n) scanf("%llu",&n)
#define sd(n) scanf("%lf",&n)
#define ss(n) scanf("%s",n)
#define pnl printf("\n")
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pF first
#define pS second
#define CL(a,b) memset(a,b,sizeof(a))
#define sqr(x) ((x)*(x))
#define intLIMIT numeric_limits<int>
#define longLIMIT numeric_limits<long long>
#define GCD(a,b) __gcd((a),(b))
#define dbl(x) (double)(x)
#define vi vector <int>
#define vii vector < pair <int, int> >
#define vll vector <long long>
#define allof(x) (x).begin(), (x).end()
#define fastCin cin.sync_with_stdio(0);cin.tie(0)
#define scanUnsigned(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
#define printArr(a,l) cout<<#a<<": ";for(int i=0;i<(l);i++){cout<<a[i]<<" ";}cout<<endl
#define print2dArr(a,r,c) cout<<#a<<":\n";for(int i=0;i<(r);i++){for(int j=0;j<(c);j++){cout<<a[i][j]<<" ";}cout<<endl;}
char _;
using namespace std;
void PRINT (int x, int y) { for (int i = y-1; i >= 0; i--) { cout << READ(x,i); } cout << endl; }

vector<string>vec_splitter(string s){s+=',';vector<string>res;while(!s.empty()){res.push_back(s.substr(0,s.find(',')));s=s.substr(s.find(',')+1);}
return res;}
void debug_out(vector<string>__attribute__((unused))args,__attribute__((unused))int idx,__attribute__((unused))int LINE_NUM){cerr<<endl;}
template<typename Head,typename...Tail>void debug_out(vector<string>args,int idx,int LINE_NUM,Head H,Tail...T){if(idx>0)cerr<<", ";else cerr<<"Line("<<LINE_NUM<<") ";stringstream ss;ss<<H;cerr<<args[idx]<<" = "<<ss.str();debug_out(args,idx+1,LINE_NUM,T...);}
#ifdef LOCAL_DBG
#define dbg(...) debug_out(vec_splitter(#__VA_ARGS__), 0, __LINE__, __VA_ARGS__)
#else
#define dbg(...) 42
#endif

int main () {
	fastCin;
	string s;
	cin >> s;
	int sum = 0;
	for (int x = 0; x < s.length(); x++) {
		sum += s[x]-'0';
	}
	if (sum%9==0) {
		cout << "Yes\n";
	} else {
		cout << "No\n";
	}
	return 0;
}

Measured memory_bytes: 3492
#include <iostream>

using namespace std;

int main()
{
    string s;
    cin>>s;
    if(s == "Sunny")
        cout<<"Cloudy";
    else if (s == "Cloudy")
        cout<<"Rainy";
    else if(s == "Rainy")
        cout<<"Sunny";
    return 0;
}


Measured memory_bytes: 256
// 高橋くんは、自動販売機でジュースを買ったときの音が好きです。
// その音は 1 回
// A 円で聞くことができます。
// 高橋くんは B 円持っていますが、お気に入りの音を
// C 回聞くと満足するため、B 円で最大 C 回まで聞けるだけ聞きます。
// 高橋くんはお気に入りの音を何回聞くことになるでしょうか。

package main

import (
	"fmt"
)

func scannums(len int) (nums []int) {
	var num int
	for i := 0; i < len; i++ {
		fmt.Scanf("%d", &num)
		nums = append(nums, num)
	}
	return nums
}

func main() {
	res := scannums(3)
	if res[1]/res[0] < res[2] {
		fmt.Println(res[1] / res[0])
	} else {
		fmt.Println(res[2])
	}
}


Measured memory_bytes: 512
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
typedef int64_t int64;
typedef uint32_t uint;
typedef uint64_t uint64;
using namespace std;

//---

template <typename T>
inline void print(const T& rhs){ std::cout<<" = "<<rhs<<std::endl; }
template <typename T>
inline void print(const std::vector<T>& rhs){
    std::cout<<" = [ ";
    for(uint i=0; i<rhs.size(); ++i){ std::cout<<rhs[i]<<' '; }
    std::cout<<"]"<<std::endl;
}
template <typename T>
inline void print(const std::vector<std::vector<T>>& rhs){
    std::cout<<" = "<<std::endl;
    std::cout<<"[[ ";
    for(uint p=0; p<rhs.size(); ++p){
        if(p!=0){ std::cout<<" [ "; }
        for(uint q=0; q<rhs[p].size(); ++q){
            std::cout<<rhs[p][q]<<' ';
        }
        if(p!=rhs.size()-1){ std::cout<<"]"<<std::endl; }
    }
    std::cout<<"]]"<<std::endl;
}
template <typename TL, typename TR>
inline void print(const std::vector<std::pair<TR,TL>>& rhs){
    std::cout<<" = [";
    uint i=0;
    for(; i<rhs.size()-1; ++i){ std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"], "; }
    std::cout<<"[f: "<<rhs[i].first<<", s: "<<rhs[i].second<<"]]" << endl;
}
#define printn(var) {printf("%s", #var);print(var);}
#define printn_all(var) {printf("%s(%d): ", __func__, __LINE__);printf("%s", #var);print(var);}

//---

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    vector<int> v;
    v.push_back( 1 );
    for(int i=2; i<=31; ++i){
        int tmp = i*i;
        while(tmp <= 1000){
            v.push_back( tmp );
            tmp *= i;
        }
    }
    sort(v.begin(), v.end());
    
    int X; cin >> X;
    cout << v[ upper_bound(v.begin(), v.end(), X) - v.begin() - 1] << endl;
    
    return 0;
}

Measured memory_bytes: 256
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  n=I()
  ans=0

  _ba=0
  _b=0
  _a=0
  for _ in range(n):
    s=S()
    ans+=s.count('AB')

    if s[0]=='B':
      if s[-1]=='A':
        _ba+=1
      else:
        _b+=1
    else:
      if s[-1]=='A':
        _a+=1

  ans+=max(0,_ba-1)

  if _ba>0:
    if _b>0:
      ans+=1
      _b-=1
    if _a>0:
      ans+=1
      _a-=1

  if _b>0 and _a>0:
    ans+=min(_b,_a)

  return ans

# main()
print(main())


Measured memory_bytes: 7976
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<utility>
#include<vector>
#include<queue>
#include<functional>
#include<map>
#include<set>
using namespace std;
#define int long long
typedef pair<int, int> pii;
typedef priority_queue<pii, vector<pii>, greater<pii> > RPQ;
#define mk make_pair
#define INF (1 << 30)
#define INFL (1ll << 60ll)
#define mod 1000000007

int N, a[100100];

signed main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        cin >> a[i];
    }
    int cnt = 0;
    for(int i = 0; i < N; i++){
        int minj = i;
        for(int j = i; j < N; j++){
            if(a[j] < a[minj]){
                minj = j;
            }
        }
        if(i != minj){
            swap(a[i], a[minj]);
            cnt++;
        }
    }
    for(int i = 0; i < N; i++){
        cout << a[i] << ((i == N - 1) ? "\n" : " ");
    }
    cout << cnt << endl;


    return 0;
}

/*

*/


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

using namespace std;

const int MX = 100000;

vector<int> G[MX];
int vis[MX];
int x, y;

bool dfs(int v, int d = 1) {
	if (vis[v] == d) return false;
	if (vis[v] != 0) return true;
	
	vis[v] = d;
	(d == 1 ? x : y)++;
	
	bool ok = false;
	for (int u : G[v]) ok = dfs(u, d ^ 3) || ok;
	
	return ok;
}

int main() {
	int n, m;
	ignore = scanf("%d %d", &n, &m);
	for (int i = 0, u, v; i < m; i++) {
		ignore = scanf("%d %d", &u, &v);
		u--;
		v--;
		
		G[u].push_back(v);
		G[v].push_back(u);
	}
	
	long long ans = 0;
	for (int i = 0; i < n; i++)
		if (vis[i] == 0) {
			x = y = 0;
			if (dfs(i)) ans += (x + y) * (x + y - 1ll) / 2;
			else ans += x * 1ll * y;
		}
		
	printf("%lld\n", ans - m);
	
	return 0;
}


Measured memory_bytes: 6912
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author cksharma
 */

#include <bits/stdc++.h>
using namespace std;

class BContests {
public:
    void solve(istream& cin, ostream& cout) {
        ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
        cout.setf(ios::fixed); cout.precision(20);

        int first = 0, second = 0, third = 0;
        int N, A, B, P;
        cin >> N >> A >> B;
        for (int i = 0; i < N; ++i) {
            cin >> P;
            if(P <= A) first++;
            else if ( P <= B ) second++;
            else third++;
        }
        cout << min( first, min(second, third));
    }
};


int main() {
    BContests solver;
    std::istream& in(std::cin);
    std::ostream& out(std::cout);
    solver.solve(in, out);
    return 0;
}


Measured memory_bytes: 256
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n = int(input())
    H = list(map(int, input().split()))

    res = 0
    cnt = 0
    for i in range(1, n):
        if H[i - 1] >= H[i]:
            cnt += 1
        else:
            res = max(res, cnt)
            cnt = 0
    res = max(res, cnt)
    print(res)


if __name__ == '__main__':
    resolve()


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

int main(){
    unsigned long long int n,a,b,x,y,z;
    cin>>n>>a>>b;

    if((b-a)%2==0)
        cout<<(b-a)/2<<endl;
 else
    {
        x=0;
        y=a-1;
        z=n-b;
        if(y<z)
        {
            x+=y;
            b-=y;
            a=1;
            while((b-a)%2!=0)
            {
                x++;
                b--;
            }
            x+=(b-a)/2;
        }
        else{
            x+=z;
            a+=z;
            b=n;
            while((b-a)%2!=0)
            {
                x++;
                a++;
            }
            x+=(b-a)/2;
        }
        cout<<x<<"\n";
    }
    return 0;


}


Measured memory_bytes: 256
K, N = gets.chomp.split.map(&:to_i)
array = gets.chomp.split.map(&:to_i)
array.sort!

dist = []

dist.push array[0] + (K - array[-1])

tmp_dist = 0

array.each do |dist_by_top|
  dist.push dist_by_top - tmp_dist
  tmp_dist = dist_by_top
end

puts K - dist.max

Measured memory_bytes: 21872
import java.io.*;
import java.util.*;
import java.math.*;

class Main {
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static PrintWriter pw = new PrintWriter(System.out);
    public static String line;
    public static StringTokenizer st;
    public static ArrayList<ArrayList<Integer>> adjList;
    public static int[] dx = {-1, 0, 1, 0, -1, 1, 1, -1};
    public static int[] dy = {0, 1, 0, -1, 1, 1, -1, -1};
    public static int INF = 0x3f3f3f3f;
    public static int MOD = 1000000007;

    public static void main(String[] args) throws Exception{
        char[] s = br.readLine().toCharArray();
        int[] memo = new int[1 << 26];
        Arrays.fill(memo, INF);
        int mask = 0;
        int[] opt = new int[s.length];
        for(int i = 0; i < s.length; i++){
            mask ^= (1 << (s[i] - 'a'));
            if(Integer.bitCount(mask) <= 1){
                memo[mask] = 1;
                opt[i] = 1;
            } else{
                int min = Math.min(memo[mask], i);
                for(int j = 0; j < 26; j++){
                    min = Math.min(min, memo[mask ^ (1 << j)]);
                }
                memo[mask] = Math.min(min + 1, memo[mask]);
                opt[i] = min + 1;
            }
        }
        pw.print(opt[s.length-1] + "\n");


        pw.close(); 
        br.close();
    }
}

class Pair{
    public long x, y;

    Pair(long _x, long _y){
        x = _x;
        y = _y;
    }
}
class Point implements Comparable<Point>{
    public double x, y;

    Point(double x, double y){
        this.x = x;
        this.y = y;
    }

    public int compareTo(Point p){
        if(x != p.x) return x < p.x ? -1 : 1;
        else if(y != p.y) return y < p.y ? -1 : 1;
        return 0;
    }
}

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

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

using namespace std;
using lint=long long;

int main(){
	lint n; scanf("%lld",&n);
	vector<pair<int,int>> E(n-1);
	rep(i,n-1) scanf("%d%d",&E[i].first,&E[i].second), E[i].first--, E[i].second--;

	lint ans=n*(n+1)*(n+2)/6;
	rep(i,n-1){
		auto [u,v]=E[i];
		if(u>v) swap(u,v);
		ans-=(u+1LL)*(n-v);
	}
	printf("%lld\n",ans);

	return 0;
}


Measured memory_bytes: 4804
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false); cin.tie(0);
#define FOR(i,s,n) for(int i = (s); i < (n); i++)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) for(int i = (n); i >= 0; i--)
#define ALL(n) (n).begin(), (n).end()
#define RALL(n) (n).rbegin(), (n).rend()
#define ATYN(n) cout << ( (n) ? "Yes":"No") << '\n';
#define CFYN(n) cout << ( (n) ? "YES":"NO") << '\n';
#define OUT(n) cout << (n) << '\n';
using ll = long long;
using ull = unsigned long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;

int main(void)
{
    IOS
    int N; cin >> N;
    vector<int> a(N);
    REP(i,N) cin >> a[i];

    int ans = 1;
    // 0-no 1-up 2-down
    int nud = 0;
    FOR(i,1,N) {
        if (nud == 0) {
            if (a[i-1] < a[i]) nud = 1;
            else if (a[i-1] > a[i]) nud = 2;
        }
        
        if (nud == 1) {
            if (a[i-1] > a[i]) {
                ans++;
                nud = 0;
            }
        }
        if (nud == 2) {
            if (a[i-1] < a[i]) {
                ans++;
                nud = 0;
            }
        }
    }

    cout << ans << '\n';

    return 0;
}

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

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

    int num=0;
    int max=0;
    int st=0;
    while(st<=S.size()-T.size()){
        rep(i, T.size()){
            if(S[st+i]==T[i]) num++;
        }
        max=fmax(max, num);
        num=0;
        st++;
    }

    cout<<T.size()-max<<endl;
    return 0;
}

Measured memory_bytes: 3724
#define scanf_s scanf
#define gets_s gets
#include <stdio.h>
#include <string>
#include <iostream>
#include <math.h>
using namespace std;
#define MAX 201
#define _MAX 100
#define ABC 26
int main(void)
{
	int n;
	char str[MAX];
	long long int ans = 1;
	gets_s(str);
	for (int i = 0; str[i] != '\0'; ++i) {
		if ('a' <= str[i] && str[i] <= 'z') {
			str[i] = str[i] - 'a' + 'A';
		}
	}
	printf("%s\n", str);
}

Measured memory_bytes: 1088
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
using namespace std;

#define M 1046527

long long T[M];
//???????????\??¢??°
int h1(long long key) { return key % M; }

int h2(long long key) { return 1 + (key % (M - 1)); }

int h(long long key, int i) { return ((h1(key)) + i*h2(key)) % M; }

void insert(long long key)
{
	int i = 0;
	while (1) {
		int j = h(key, i);
		if (!T[j]) {
			T[j] = key;
			return;
		}
                else if (T[j] == key) return;
		else i++;
	}
}

bool find(long long key)
{
	int i = 0;
	while (1) {
		int j = h(key, i);
		if (T[j] == key) return 1;
		else if (!T[j]) return 0;
		else i++;
	}
}

long long getKey(char *p)
{
	long long key = 0;
	for (int i = (strlen(p) - 1); i >= 0; i--) {
		long long x;
		switch (p[i])
		{
		case 'A':
			x = 1; break;
		case 'C':
			x = 2; break;
		case 'G':
			x = 3; break;
		case 'T':
			x = 4; break;
		default:
			break;
		}
		key += x * pow(10, i);
	}
	return key;
}

int main()
{
	int n;
	char order[10], word[15];
	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%s %s", order, word);
		if (order[0] == 'i') insert(getKey(word));
		else if (find(getKey(word))) printf("yes\n");
		else printf("no\n");
	}
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> pi;
typedef pair<int,int> vi;

#define F first
#define S second
#define PB push_back
#define MK make_pair
#define REP(i, a, b) for (int i=a; i < b; i++)


bool sort_by(vi c, vi d){
	return c.S < d.S;
}

int main() {
	int a, b, c;
	cin >> a >> b >> c;
	int m1, m2, m3;
	if(a >= b  && a>= c){
		m1 = a;
		if(b>= c){
			m2=b;
			m3 = c;
		}
		else{
			m2 = c;
			m3=b;
		}
	}
	else if(b >= a && b >= c){
		m1 = b;
		if(a>= c){
			m2= a;
			m3 = c;
		}
		else{
			m2 = c;
			m3=a;
		}
	}
	else{
		m1 = c;
		if(a>= b){
			m2= a;
			m3 = b;
		}
		else{
			m2 = b;
			m3=a;
		}
	}
	
	int ans = 0;
	while(m2-m3 != 0){
		if(m2-m3 > 1){
			m3+= 2;
			++ans;
		}
		else{
			++m3;
			++m1;
			++ans;
		}
	}
	//cout << ans << endl;
	cout << ans + (m1-m2);
			

}


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

/**
 * Made by egor https://github.com/chermehdi/egor.
 * 
 * @author Azuz
 * 
 */
public class Main {

    void solve(Scanner in, PrintWriter out) {
      int n = in.nextInt();
      int[] arr = new int[n];
      
      int gcd = 0;

      boolean setwise = false;
      boolean pairwise = false;
      for (int i = 0; i < n; ++i) {
        arr[i] = in.nextInt();
        gcd = gcd(gcd, arr[i]);
      }

      if (gcd == 1) setwise = true;
      HashSet<Integer> set = new HashSet<>();
      boolean flag = true;
      for (int i = 0; i < n && flag; ++i) {
        int x = arr[i];
        if (x % 2 == 0) {
          if (set.contains(2)) {
            flag = false;
            break;
          }
          set.add(2);
          while (x % 2 == 0) x >>= 1;
        }

        for (int j = 3; j * j <= x; j += 2) {
          if (x % j == 0) {
            if (set.contains(j)) {
              flag = false;
              break;
            }
            set.add(j);
            while (x % j == 0) x /= j;
          }
        }

        if (x > 2) {
          if (set.contains(x)) {
            flag = false;
            break;
          }
          set.add(x);
        }
      }

      pairwise = flag;


      if (pairwise) {
        out.println("pairwise coprime");
      } else if (setwise) {
        out.println("setwise coprime");
      } else {
        out.println("not coprime");
      }
    }

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

    public static void main(String[] args) {
        try(Scanner in = new Scanner(System.in);
            PrintWriter out = new PrintWriter(System.out)) {
            new Main().solve(in, out);
        }
    }
}


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

int main() {
    int A, B, C;
    cin >> A >> B >> C;
    bool flag = false;

    for(int i = 1; i <= B; i++){ 
        if(i*A % B == C){
            flag = true;
        }
    }
    cout << (flag? "YES":"NO") << endl;

}

Measured memory_bytes: 256
#pragma GCC optimize ("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;

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

	char a[4];
	cin >> a;
	sort(a, a + 4);

	cout << ((a[0] == a[1] && a[2] == a[3] && a[0] != a[2]) ? "Yes" : "No")
			<< endl;
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
struct cww{cww(){ios::sync_with_stdio(false);cin.tie(0);}}star;
const long long INF = numeric_limits<long long>::max();
int main()
{
    int N, X;
    cin >> N >> X;
    vector<int> M( N );
    for( auto &x : M )
    {
        cin >> x;
        X -= x;
    }
    sort( begin( M ), end( M ) );
    int cnt = N;
    while( true )
    {
        REP( i, N )
        {
            if( M[ i ] <= X )
            {
                cnt++;
                X -= M[ i ];
                break;
            }
            if( X - M[ i ] < X )
            {
                cout << cnt << endl;
                return 0;
            }
        }
    }
    return 0;
}

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

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    int n;
    cin >> n;
    vector<int> a(n), t(n);
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }

    if (n == 1) {
        if (a.front() != t.front())
            cout << 0 << endl;
        else
            cout << 1 << endl;
        return 0;
    }

    bool possible = true;
    vector<pair<int, int>> range(n, make_pair(1, 1000000000));
    range.front().first = range.front().second = t.front();
    range.back().first = range.back().second = a.back();
    for (int i = 1; i < n; ++i) {
        if (t[i] != t[i - 1]) {
            range[i].first = range[i].second = t[i];
        } else {
            range[i].second = min(range[i].second, t[i]);
        }
    }
    for (int i = n - 2; i >= 0; --i) {
        if (a[i] != a[i + 1]) {
            if (range[i].first <= a[i] && a[i] <= range[i].second)
                range[i].first = range[i].second = a[i];
            else
                possible = false;
        } else {
            range[i].second = min(range[i].second, a[i]);
        }
    }

    if (!possible) {
        cout << 0 << endl;
        return 0;
    }

    ll ans = 1;
    constexpr ll mod = 1000000007;
    for (const auto &r : range) {
        ans *= r.second - r.first + 1;
        ans %= mod;
    }

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

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

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

int
main()
{
  int N;
  cin >> N;
  vector<int> d(N);
  for (int i = 0; i < N; i++)
  {
    cin >> d[i];
  }
  sort(d.begin(), d.end());
  int count = d[N / 2] - d[N / 2 - 1];
  cout << count << endl;
  return 0;
}


Measured memory_bytes: 640
/*                                  deepyadav442 --> :     c++14     <--                                */
#include<bits/stdc++.h>
#define mod 1000000007
#define ll long long
/*                                           input                    */
#define si(i) scanf("%d",&i)
#define sii(i,j) scanf("%d%d",&i,&j)
#define siii(i) scanf("%lld",&i)
#define sss(s) scanf("%s",s)
/*                                           output                   */
#define pi(i) printf("%d",i)
#define pii(i,j) printf("%d%d",i,j)
#define piii(i) printf("%lld",i)
#define space printf(" ")
#define newline printf("\n")
/*                                          loops &stls                      */
#define loop(i,s,n) for(i=s;i<n;i++)
#define looprev(i,s,n) for(i=s;i>=n;i--)
#define itervec vector<int>::iterator itv
#define iterrev vector<int>::reverse_iterator it
#define itermap map<string,int>::iterator itm
#define pb(S) push_back(S)
#define mp(i,j) make_pair(i,j)
#define f first
#define s second
#define MAX(a,b) 	(a>b) ? (a) : (b)
#define MIN(a,b) 	(a<b) ? (a) : (b)
using namespace std;
int main()
{
    char in[1001];
    sss(in);
    if(in[0]==in[2])
        cout<<"Yes"<<endl;
    else
        cout<<"No"<<endl;
    return 0;
}
/*   fast input output
inline ll input() //for input integers call it long long int n=input();
{
    ll n=0;
    char ch=getchar_unlocked();
    while( ch < '0' || ch > '9' )
    {
        ch=getchar_unlocked();
    }
    while( ch >= '0' && ch <= '9' )
    {
        n = (n<<3)+(n<<1) + ch-'0', ch=getchar_unlocked();
    }
    return n;
}
inline void output(ll n)     //for output call output(count) and then for space use put('\n');
{
    char b[35];
    ll i=0;
    do
    {
        b[i++]=n%10+48;
        n=n/10;
    }while(n!=0);
    --i;
    while(i>=0)
    putchar_unlocked(b[i--]);
}
inline void faststring(char *str)  //for entering a string use faststring(p);
{
    register char c = 0;
    register long long i = 0;
    while (c < 33)
    c = getchar_unlocked();
    while (c != '\n')
    {
        str[i] = c;
        c = getchar_unlocked();
        ++i;
    }
    str[i] = '\0';
}


*/


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
using ll = long long;

const ll MOD = 1e9 + 7;
const int MAX = 1010;
ll f[MAX], finv[MAX], tbl[MAX][MAX];

ll mod_pow(ll x, ll e) {
  ll v = 1;
  for (; e > 0; e >>= 1) {
    if (e & 1) {
      v = v * x % MOD;
    }
    x = x * x % MOD;
  }
  return v;
}

inline ll Comb(int n, int k) {
  if (k < 0 || k > n) {
    return 0;
  }
  return (f[n] * finv[k] % MOD) * finv[n - k] % MOD;
}

void init() {
  f[0] = 1;
  for (int i = 1; i < MAX; i++) {
    f[i] = f[i-1] * i % MOD;
  }
  finv[MAX-1] = mod_pow(f[MAX-1], MOD - 2);
  for (int i = MAX - 2; i >= 0; i--) {
    finv[i] = finv[i+1] * (i + 1) % MOD;
  }
  for (int i = 1; i < MAX; i++) {
    tbl[i][1] = 1;
    for (int j = 2; j < MAX; j++) {
      if (i * j >= MAX) {
        break;
      }
      tbl[i][j] = tbl[i][j-1] * Comb(i * j, i) % MOD;
    }
  }
}

int main() {
  init();
  int N, A, B, C, D;
  cin >> N >> A >> B >> C >> D;
  vector<vector<ll>> dp(N + 1, vector<ll>(N + 1, 0));
  dp[A-1][N] = 1;
  for (int k = A; k <= B; k++) {
    for (int n = 0; n <= N; n++) {
      (dp[k][n] += dp[k-1][n]) %= MOD;
      for (int m = C; m <= D; m++) {
        if (n < k * m) {
          break;
        }
        ll tmp = (Comb(n, k * m) * tbl[k][m] % MOD) * finv[m] % MOD;  
        (dp[k][n-k*m] += dp[k-1][n] * tmp % MOD) %= MOD;
      }
    }
  }
  cout << dp[B][0] << endl;
  return 0;
}


Measured memory_bytes: 16280
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int purchase = sc.nextInt();
        int ticket = sc.nextInt();
        Queue<Double> eachAmount = new PriorityQueue<>(purchase, Comparator.reverseOrder());
        for (int i = 0; i < purchase; i++) {
            eachAmount.add((double) sc.nextInt());
        }
        for (int i = 0; i < ticket; i++) {
            double max = eachAmount.poll();
            eachAmount.add(max / 2);
        }
        long sum = 0;
        for (double amount : eachAmount) {
            sum += Math.floor(amount);
        }
        System.out.println(sum);
    }
}

Measured memory_bytes: 62392
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		final long n = sc.nextInt();

		final String[] list = String.valueOf(n).split("");

		long total = 0;
		for (final String num : list) {
			total = total + Integer.parseInt(num);
		}

		if (n % total == 0) {
			System.out.print("Yes");
		} else {
			System.out.print("No");
		}

	}

}

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

#define int long long
#define rep(i,n) for(int i=0;i<(n);i++)
#define pii pair<int,int>

int N;
int A[200010];
int mem[1000010];
int num[1000010];

signed main()
{
    cin >> N;
    rep(i, N)
    {
        cin >> A[i];
        num[A[i]]++;
    }

    sort(A, A + N);

    int ans = 0;
    rep(i, N)
    {
        if(mem[A[i]] == 0 && num[A[i]] == 1)ans++;
        if(mem[A[i]] == 0)for(int j = A[i]; j <= 1000000; j += A[i])mem[j] = 1;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 20608
#include<iostream>
#include<string.h>
#include<string>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<bitset>
#include<math.h>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef long double db;
typedef vector<int> vi;
typedef pair<int,int> pii;
const int N=100000+100;
const db pi=acos(-1.0);
#define lowbit(x) (x)&(-x)
#define sqr(x) (x)*(x)
#define rep(i,a,b) for (register int i=a;i<=b;i++)
#define per(i,a,b) for (register int i=a;i>=b;i--)
#define go(u,i) for (register int i=head[u],v=sq[i].to;i;i=sq[i].nxt,v=sq[i].to)
#define fir first
#define sec second
#define mkp make_pair
#define pb push_back
#define maxd 998244353
#define eps 1e-8
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

inline ll readll()
{
    ll x=0;int f=1;char ch=getchar();
    while ((ch<'0') || (ch>'9')) {if (ch=='-') f=-1;ch=getchar();}
    while ((ch>='0') && (ch<='9')) {x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}

string s,t;

int main()
{
    cin >> t >> s;
    int n=s.size();
    string p="";
    rep(i,0,n-2) p=p+s[i];
    if (p==t) puts("Yes");else puts("No");
    return 0;
}

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

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

const int INF = 1e9 + 7;

using namespace std;

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

	int a, b, c, d;
	cin >> a >> b >> c >> d;

	cout << min(a, b) + min(c, d) << endl;


	return 0;
}


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

namespace AtCoder {
	class Program {
		#region Reserve
		static int cin() { return cin(-1); }
		static int cin(int D) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return int.Parse(s);
		}
		static long cln(long D = -1) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return D;
			return long.Parse(s);
		}
		static int[] cins(char spliter) {
			string s = Console.ReadLine();
			if (string.IsNullOrEmpty(s))
				return new int[] { };
			string[] ss = s.Split(spliter);
			var Res = new int[ss.Length];
			for (int i = 0; i < ss.Length; i++)
				Res[i] = int.Parse(ss[i]);
			return Res;
		}
		static int[] cins() { return cins(' '); }
		static void print(object j) { Console.WriteLine(j.ToString()); }
		static void print(string j) { Console.WriteLine(j); }
		static string read() { return Console.ReadLine(); }
		#endregion

		static void Main(string[] args) {
			var I = cins();
			int Q = I[0], H = I[1], S = I[2], D = I[3];
			var N = cin();
			var G = new int[] { Q*4,H*2,S};
			int OneL = G.Min();
			int TwoL = Math.Min(OneL * 2, D);
			print(((long)N)/2*TwoL+(N%2==1?OneL:0));
			read();
		}
	}
}


Measured memory_bytes: 13268
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

/* 値を入れ替える関数 */
void swap (int *x, int *y) {
    int temp;    // 値を一時保存する変数
    
    temp = *x;
    *x = *y;
    *y = temp;
}

/***
 * pivotを決め、
 * 全データをpivotを境目に振り分け、
 * pivotの添え字を返す
 ***/
int partition (int array[], int left, int right) {
    int i, j, pivot;
    i = left;
    j = right + 1;
    pivot = left;   // 先頭要素をpivotとする
    
    do {
        do { i++; } while (array[i] < array[pivot]);
        do { j--; } while (array[pivot] < array[j]);
        // pivotより小さいものを左へ、大きいものを右へ
        if (i < j) { swap(&array[i], &array[j]); }
    } while (i < j);
    
    swap(&array[pivot], &array[j]);   //pivotを更新
    
    return j;
}

/* クイックソート */
void quick_sort (int array[], int left, int right) {
    int pivot;
    
    if (left < right) {
        pivot = partition(array, left, right);
        quick_sort(array, left, pivot-1);   // pivotを境に再帰的にクイックソート
        quick_sort(array, pivot+1, right);
    }
}


int main(void){
    int i,j,k;
    int N;
    int d[100000],count;
    
    scanf("%d",&N);
    for(i = 0;i < N-1;i++){
        scanf("%d\n",&d[i]);
    }
    scanf("%d",&d[i]);
    
    quick_sort(d,0,N-1);
    
    count = d[N/2] - d[N/2-1];
    
    printf("%d\n",count);
    return 0;
}






Measured memory_bytes: 512