akhauriyash/Code-Regression huggingface dataset:
U = 2*10**5
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, m, k = map(int, input().split())
ans = 0
for i in range(k+1):
    res = 1
    res *= comb(n-1, i)
    res *= m
    res %= MOD
    res *= pow(m-1, n-i-1, MOD)
    res %= MOD
    ans += res
    ans %= MOD
print(ans)

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------


int N;
int P[(1<<18)+1];
int D[1<<19];
int V[1<<19],W[1<<19];
int Q;
int T[1<<19],L[1<<19];
ll ret[1<<19];
vector<int> tar[1<<19];

vector<int> VV[1<<19];
vector<pair<int,ll>> cand[1<<19];

const int DI=12;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	for(i=1;i<=N;i++) {
		if(i>1) {
			P[i]=i/2;
			D[i]=D[i/2]+1;
			VV[i]=VV[i/2];
		}
		VV[i].push_back(i);
		cin>>V[i]>>W[i];
		
	}
	cin>>Q;
	FOR(i,Q) {
		cin>>T[i]>>L[i];
		tar[T[i]].push_back(i);
	}
	
	
	
	for(i=1;i<1<<DI;i++) if(i<=N) {
		vector<pair<ll,ll>> A;
		int len=VV[i].size();
		int mask;
		FOR(mask,1<<len) {
			int v=0,w=0;
			FOR(j,len) if(mask&(1<<j)) v+=V[VV[i][j]],w+=W[VV[i][j]];
			if(w<=100000) A.push_back({w,v});
		}
		
		sort(ALL(A));
		cand[i].push_back({0,0});
		FORR(a,A) {
			while(cand[i].size() && cand[i].back().first==a.first) cand[i].pop_back();
			if(cand[i].empty() || cand[i].back().second<a.second) {
				cand[i].push_back(a);
			}
		}
		
		FORR(t,tar[i]) {
			x=lower_bound(ALL(cand[i]),make_pair(L[t]+1,0LL))-cand[i].begin();
			x--;
			ret[t]=cand[i][x].second;
		}
	}
	
	for(i=1<<DI;i<1<<18;i++) if(i<=N) {
		vector<int> C;
		int p=0;
		FORR(c,VV[i]) {
			if(D[c]>=DI) C.push_back(c);
			else p=max(p,c);
		}
		
		
		FORR(t,tar[i]) {
			int len=C.size();
			int mask;
			FOR(mask,1<<len) {
				int v=0,w=0;
				FOR(j,len) if(mask&(1<<j)) v+=V[C[j]],w+=W[C[j]];
				if(w<=L[t]) {
					x=lower_bound(ALL(cand[p]),make_pair(L[t]-w+1,0LL))-cand[p].begin();
					x--;
					ret[t]=max(ret[t],cand[p][x].second+v);
				}
			}
		}
		
	}
	
	
	
	FOR(i,Q) cout<<ret[i]<<endl;
	
	
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 237812
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    bool ans =false;
    cin >>n;
    if(n<=9){
        cout<< "Yes";
    }
    else if(n>9&&n<=81){
        for(int i = 2; i<=9; ++i){
            if(n%i==0 && int(n/i)<= 9){
               ans = true;
            }
        } 
        if(ans){
            cout<< "Yes";
        }
        else{
            cout << "No";
        }
    }
    
    else{
        cout<< "No";
    }
    
    return 0;
}

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

#define ll long long
#define pb push_back
#define MP make_pair

#define MAX 1e9
#define MIN -1e9
#define MOD 1000000007

int main(){
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	int n, m, k;
	cin >> n >> m >> k;
	int a[n], b[m];
	ll prefix_suma[n+1] = {0}, prefix_sumb[m+1] = {0};
	ll total = MIN;
	for(int i=0; i<n; i++)
	    cin >> a[i];
	for(int i=0; i<m; i++)
	    cin >> b[i];
	for(int i=0; i<n; i++)
	    prefix_suma[i+1] = prefix_suma[i] + a[i];
	for(int i=0; i<m; i++)
	    prefix_sumb[i+1] = prefix_sumb[i] + b[i];
	for(ll i=0; i<=n; i++){
	    ll other = k - prefix_suma[i];
	    if(other < 0)
		continue;
	    int l = lower_bound(prefix_sumb, prefix_sumb+m+1, other) - prefix_sumb;
	    if(l > m || prefix_sumb[l] > other)
		l--;
	    total = max(total, i+l);
	}
	cout << total << "\n";
	return 0;
}


Measured memory_bytes: 8324
#define _USE_MATH_DEFINES
#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <complex>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <iterator>
using namespace std;

class SparseTable
{
private:
    vector<int> logTable;
    vector<vector<int> > data;
public:
    SparseTable(const vector<int>& v){
        int n = v.size();
        logTable.assign(n+1, 0);
        for(int i=2; i<=n; ++i)
            logTable[i] = logTable[i>>1] + 1;

        data.assign(1, v);
        for(int i=1; (1<<i)<=n; ++i){
            int len = 1 << i;
            data.push_back(vector<int>(n - len + 1));
            for(int j=0; j<n-len+1; ++j)
                data[i][j] = min(data[i-1][j], data[i-1][j+len/2]);
        }
    }
    int query(int a, int b){ // 区間[a,b)の最小値を返す
        int i = logTable[b-a];
        int len = 1 << i;
        return min(data[i][a], data[i][b-len]);
    }
};

const int INF = INT_MAX / 2;

void solve(const vector<int>& v, vector<int>& ans)
{
    int n = v.size();
    vector<int> pos(n);
    vector<vector<int> > v2(2, vector<int>(n, INF));
    for(int i=0; i<n; ++i){
        pos[v[i]] = i;
        v2[i%2][i] = v[i];
    }
    
    vector<SparseTable> st = {v2[0], v2[1]};
    priority_queue<int, vector<int>, greater<int> > pq;
    pq.push(st[0].query(0, n));
    set<int> usedPos;
    usedPos.insert(-1);
    usedPos.insert(n);

    ans.clear();
    while(!pq.empty()){
        int x = pq.top();
        pq.pop();

        int i = pos[x];
        auto it = usedPos.upper_bound(i);
        int b = *it;
        -- it;
        int a = *it;
        if((i - a) % 2 == 0)
            continue;

        int y = st[(b+1)%2].query(i+1, b);
        int j = pos[y];
        ans.push_back(x);
        ans.push_back(y);
        usedPos.insert(i);
        usedPos.insert(j);

        vector<int> tmp = {a, i, j, b};
        for(int k=0; k<3; ++k){
            if(tmp[k] + 1 == tmp[k+1])
                continue;
            int z = st[tmp[k+1]%2].query(tmp[k]+1, tmp[k+1]);
            pq.push(z);
        }
    }
}

int main()
{
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i=0; i<n; ++i){
        cin >> v[i];
        -- v[i];
    }

    vector<int> ans;
    solve(v, ans);
    for(int i=0; i<n; ++i)
        ++ ans[i];

    cout << ans[0];
    for(int i=1; i<n; ++i)
        cout << ' ' << ans[i];
    cout << endl;

    return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned int ui;
typedef pair<int, int> pi;

#define fi first
#define se second

int read() {
  int res = 0, w = 1; char c = getchar();
  while (!isdigit(c) && c != '-') c = getchar();
  if (c == '-') c = getchar(), w = -1;
  while (isdigit(c)) res = (res << 1) + (res << 3) + c - '0', c = getchar();
  return res * w;
}

const ll INF = 1e17;
const int N = 20;

int n, a[N];

ll dfs(int l, int r, int pl, int pr) {
  if (l + 1 == r) return 0;
  ll res = INF;
  for (int i = l + 1; i <= r - 1; i++) {
    res = min(res, dfs(l, i, pl, pl + pr) + dfs(i, r, pl + pr, pr) + 1ll * (pl + pr) * a[i]);
  } 
  return res;
}

int main() {
#ifdef dream_maker
//  freopen("tst.in", "r", stdin);
#else
  //freopen(".in", "r", stdin);
  //freopen(".out", "w", stdout);
#endif
  n = read();
  for (int i = 1; i <= n; i++) a[i] = read();
  cout << dfs(1, n, 1, 1) + a[1] + a[n] << endl;
  return 0;
}


Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double db;
typedef vector<ll> VI;
typedef vector<pair<ll,ll> > VII;
typedef map<ll,ll> mll;
typedef pair<ll,ll> pll;
//
#define M 1000000007
#define INF (ll)0x3f3f3f3f3f3f3f3f
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define F first
#define S second
#define itr iterator
#define GO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void fileioe(){
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout); 
	freopen("error.txt","w",stderr);
}

void error_out() { cerr << endl; }
template <typename Head, typename... Tail>
void error_out(Head H, Tail... T) {
  cerr << " " << H;
  error_out(T...);
}
void time_elapsed(){
  cerr<<"\nTime Elapsed : " << 1.0*clock() / CLOCKS_PER_SEC << " s\n";
}
#ifndef ONLINE_JUDGE
#define error(...) cerr << "[" << #__VA_ARGS__ << "]:", error_out(__VA_ARGS__)
#define fioe() fileioe()
#define time() time_elapsed()
#else
#define error(...) 1
#define fioe() 1
#define time() 1
#endif
const int maxr1=1e5+2,maxr2=1e2+2;
ll dp[maxr2][maxr1];
ll kanpsnak(ll arr[][2],ll ind,ll value,ll size){
	if(size==ind){
		if(value==0)
			return 0;
		return INF;
	}
	if(value<0)
		return INF;
	ll &ans=dp[ind][value];
	if(ans>-1){
		return ans;
	}
	ans=INF;
	ll ans1=kanpsnak(arr,ind+1,value,size);
	ll ans2=kanpsnak(arr,ind+1,value-arr[ind][1],size)+arr[ind][0];
	ans=min(ans1,ans2);
	return ans;
}
//
int main()
{
	GO
	//fioe();
	ll n,w;
	cin>>n>>w;
	ll arr[n+2][2];
	for(ll i=0;i<n;i++){
		cin>>arr[i][0]>>arr[i][1];
	}
	ll ans=0;
	memset(dp,-1,sizeof(dp));
	for(ll i=1;i<=1e5;i++){
		ll value=kanpsnak(arr,0,i,n);
		if(value<=w){
			ans=max(ans,i);
		}
	}
	cout<<ans<<endl;
	time();
	return 0;
}

Measured memory_bytes: 80000
#include<sstream>
using namespace std;
void replaceblank(string &s){
	for(int i=0;i<s.size();i++)if(s[i]<'0'||s[i]>'9')s[i]=' ';
}
int main(){
	string s; int ans=0,t;
	while(getline(cin,s)){
		replaceblank(s);
		stringstream ss; ss<<s;
		while(ss>>t)ans+=t;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 0
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
  long a=sc.nextLong();
  long b=sc.nextLong();
  
    long c=sc.nextLong();
  long d=sc.nextLong();
  System.out.println(Math.max(a*b,c*d));
}
}

Measured memory_bytes: 35340
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
typedef pair<ll, ll>P;
#define PI 3.14159265359
#define MOD 1000000007
const int MAX = 510000;
ll gcd(ll a, ll b){
    if (a % b == 0)
    {  return(b);}
    else{return(gcd(b, a % b));}
}
ll lcm(ll a, ll b)
{return a * b / gcd(a, b);}

int main(){
  int n,k;
  cin >>n>>k;
  cout<<(n-1+k-2)/(k-1);
}

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

using namespace std;
typedef long long ll;
const ll INF = 1LL << 50;

int solve();

ll gcd(ll p, ll q) {
	if (q == 0) { return p; }
	return gcd(q, p%q);
}

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

int solve() {

	int n;
	cin >> n;

	if (!n) { return 0; }

	vector< string > s(n);
	vector< string > code(n);
	set<char> b = { 'a', 'i', 'u', 'e', 'o' };
	int maxlen = 0;


	// 入力を受け取る
	for (auto &str : s)
		cin >> str;
	


	// tdn表記
	for (int i = 0; i < n; i++) {

		code[i] += s[i][0];

		for (int j = 1; j < s[i].length(); j++) {
			if (b.find(s[i][j - 1]) != b.end())
				code[i] += s[i][j];
		}

	}

	for (auto c : code) { maxlen = max(maxlen, static_cast<int>(c.length())); }

	for (auto &c : code) {
		int d = maxlen - static_cast<int>(c.length());
		for (int i = 0; i < d+1; i++) {
			c += '*';
		}
	}

	//for (auto c : code) { cout << c << endl; }


	int ans = -1;

	for (int i = 1; i < maxlen + 1; i++) {

		if (ans > 0) { break; }

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

				int jlen =i;
				int klen =i;

				//cout << code[j].substr(0, jlen) << " / " << code[k].substr(0, klen) << endl;

				if (code[j].substr(0, jlen) == code[k].substr(0, klen)) {
					j = n + 200; break;
				}
			}
			if (j == n - 1) { ans = i; }

		}

	}

	cout << ans << endl;

	return 1;
}


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

#define IOS             ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define watch(x);       cout << "\n" <<  #x << " is: " << x << "\n";
#define ll              long long int
#define ff              first
#define ss              second
#define all(a)          a.begin(),a.end()
#define pb              push_back
#define nl              cout<<"\n"
#define gcd(a,b)        __gcd(a,b)
#define sq(a)           (a)*(a)
#define loop(i,a,b)     for (int i = a; i <= b; i++)
#define rloop(i,a,b)    for (int i = a; i >= b; i--)
#define sz(a)           a.size()
#define mod             1000000007
#define PI              2*acos(0.0)

char a[7][7];
char b[7][7];
int n,m,k;
void matrix()
{
    loop(i,0,n-1)
    {
        loop(j,0,m-1)
        {
            b[i][j]=a[i][j];
        }
    }
}
void color(int i,int j)
{
    loop(x,0,n-1)
    {
        if(i&(1<<x))
        {
            loop(y,0,m-1) b[x][y]='@';
        }
    }
    loop(x,0,m-1)
    {
        if(j&(1<<x))
        {
            loop(y,0,n-1) b[y][x]='@';
        }
    }
}
bool check()
{
    int tot=0;
    loop(i,0,n-1)
    {
        loop(j,0,m-1)
        {
            if(b[i][j]=='#') tot++;
        }
    }
    if(tot==k) return true;
    else return false;
}
int main()
{
    IOS
    int T=1;
    //cin>>T;
    while(T--)
    {
        cin>>n>>m>>k;
        loop(i,0,n-1)
        {
            loop(j,0,m-1) cin>>a[i][j];
        }
        int total=0;
        loop(i,0,(1<<n)-1)
        {
            loop(j,0,(1<<m)-1)
            {
                matrix();
                color(i,j);
                if(check()) total++;
            }
        }
        cout<<total;

    }
    return 0;
}


Measured memory_bytes: 3632
N = int(input())
A = [0]*N
for i in range(N):
    A[i] = list(map(int, input().split()))
def solve(N,A):
    dp = [[0]*3 for i in range(N)]
    dp[0][0] = A[0][0]
    dp[0][1] = A[0][1]
    dp[0][2] = A[0][2]
    for i in range(1,N):
        dp[i][0] = max(dp[i-1][1],dp[i-1][2])+A[i][0]
        dp[i][1] = max(dp[i-1][0],dp[i-1][2])+A[i][1]
        dp[i][2] = max(dp[i-1][0],dp[i-1][1])+A[i][2]
    ans = max(dp[-1])
    return ans
print(solve(N,A))

Measured memory_bytes: 47288
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=1e3+5;
int a[MAXN][MAXN];
int n,m,A,B;
int main(){
	scanf("%d%d%d%d",&n,&m,&A,&B);
	for (int i=1;i<=B;i++){
		for (int j=1;j<=A;j++) a[i][j]=1;
	}
	for (int i=B+1;i<=n;i++){
		for (int j=A+1;j<=m;j++) a[i][j]=1;
	}
	for (int i=1;i<=n;i++){
		for (int j=1;j<=m;j++) printf("%d",a[i][j]);
		printf("\n");
	}
	return 0;
}


Measured memory_bytes: 5120
fun main(args: Array<String>) {
    val (N, K) = readInputLine().split(" ").map{it.toLong()}
    
    var ans = 0L
    
    ans += pow(N / K, 3L)
    
    if (K % 2L == 0L && N >= K / 2L) {
        ans += pow((N - K / 2L) / K + 1L, 3L)
    }
    
    println(ans)
}

fun readInputLine(): String {
    return readLine()!!
}

// x^y
fun pow(x: Long, y: Long): Long {
    var ret = 1L
    for (i in 1..y.toInt()) {
        ret *= x
    }
    return ret
}


Measured memory_bytes: 37872
#include <stdio.h>
int seen[8]={};

int dfs(int N,int G[8][8],int next){
    int flag = 1;
    for(int i = 0; i < N; i++){
        if(seen[i]==0){
            flag = 0;
            break;
        }
    }
    
    if(flag == 1){
        return 1;
    }
    
    int ret = 0;
    for(int i = 0; i < N; i++){
        if(seen[i])
            continue;
        if(G[next][i]==0)
            continue;
        
        seen[i]=1;
        ret += dfs(N,G,i);
        seen[i]=0;
    }
    
    return ret;
}

int main(void){
    // Your code here!
    int N,M;
    int G[8][8] = {};
    scanf("%d%d",&N,&M);
    
    for(int i = 0; i < M;i++){
        int a,b;
        scanf("%d%d",&a,&b);
        G[a-1][b-1]=1;
        G[b-1][a-1]=1;
    }
    
    seen[0]=1;
    int ret = dfs(N,G,0);
    
    printf("%d\n",ret);
}


Measured memory_bytes: 128
#line 2 "header.hpp"

//%snippet.set('header')%
//%snippet.fold()%
#ifndef HEADER_H
#define HEADER_H

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

// varibable settings
const long long INF = 1e18;
template <class T> constexpr T inf = numeric_limits<T>::max() / 2.1;

#define _overload3(_1, _2, _3, name, ...) name
#define _rep(i, n) repi(i, 0, n)
#define repi(i, a, b) for (ll i = (ll)(a); i < (ll)(b); ++i)
#define rep(...) _overload3(__VA_ARGS__, repi, _rep, )(__VA_ARGS__)
#define _rrep(i, n) rrepi(i, 0, n)
#define rrepi(i, a, b) for (ll i = (ll)((b)-1); i >= (ll)(a); --i)
#define r_rep(...) _overload3(__VA_ARGS__, rrepi, _rrep, )(__VA_ARGS__)
#define each(i, a) for (auto &&i : a)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define mt(...) make_tuple(__VA_ARGS__)
#define ub upper_bound
#define lb lower_bound
#define lpos(A, x) (lower_bound(all(A), x) - A.begin())
#define upos(A, x) (upper_bound(all(A), x) - A.begin())
template <class T> inline void chmax(T &a, const T &b) { if ((a) < (b)) (a) = (b); }
template <class T> inline void chmin(T &a, const T &b) { if ((a) > (b)) (a) = (b); }
template <typename X, typename T> auto make_table(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto make_table(X x, Y y, Z z, Zs... zs) { auto cont = make_table(y, z, zs...); return vector<decltype(cont)>(x, cont); }

#define cdiv(a, b) (((a) + (b)-1) / (b))
#define is_in(x, a, b) ((a) <= (x) && (x) < (b))
#define uni(x) sort(all(x)); x.erase(unique(all(x)), x.end())
#define slice(l, r) substr(l, r - l)

typedef long long ll;
typedef long double ld;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;

template <typename T>
using PQ = priority_queue<T, vector<T>, greater<T>>;
void check_input() { assert(cin.eof() == 0); int tmp; cin >> tmp; assert(cin.eof() == 1); }

#if defined(PCM) || defined(LOCAL)
#else
#define dump(...) ;
#define dump_1d(...) ;
#define dump_2d(...) ;
#define cerrendl ;
#endif

#endif /* HEADER_H */
//%snippet.end()%
#line 2 "solve.cpp"
template<class T=ll> using vec = vector<T>;
struct Fast { Fast() { std::cin.tie(0); ios::sync_with_stdio(false); } } fast;


int solve() {
    ll n;cin>>n;
    if (n%2==1){
        cout << 0 << endl;
        return 0;
    }
    else{
        ll ans = 0;
        ll mul = 10;
        while(true){
            ans += n / mul;
            if ((ld)mul*5 > 1e18 + 1) break;
            mul *= 5;
        }
        cout << ans << endl;
    }

    return 0; 
}


int main(){/*{{{*/
    solve();
    check_input();
    return 0;
}/*}}}*/


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

using namespace std;
typedef long long ll;
int main(){
  string S; cin >> S;
  ll cumul[S.size() + 10];
  for(int i = 0; i <= S.size(); i++){ cumul[i] = 0;}
  for(int i = 1; i <=  S.size(); i++){
    if(S[i - 1] == 'B'){ cumul[i] = cumul[i-1] + 1;}
   else{cumul[i] = cumul[i-1];} }
  
  ll sum = 0;
  
  for(int j = 1; j <= S.size(); j++)
      {if(S[j - 1] == 'W'){ sum += cumul[j];}}
  
  cout << sum << endl; return 0;}
  
  

Measured memory_bytes: 2180
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define int long long
int a[26];
signed main(){
	string s;
	cin>>s;
	rep(i,s.size())a[s[i]-'a']++;
	rep(i,26){
		if(a[i]==0){
			cout<<(char)('a'+i)<<endl;
			return 0;
		}
	}
	puts("None");
	return 0;
}


Measured memory_bytes: 512
#include <limits.h>
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define int long long
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPS(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define FOR(i, a, b) for (int i = (a), i##_len = (b); i <= i##_len; ++i)
#define REV(i, a, b) for (int i = (a); i >= (b); --i)
#define CLR(a, b) memset((a), (b), sizeof(a))
#define DUMP(x) cout << #x << " = " << (x) << endl;
#define INF 1001001001001001001ll
#define fcout cout << fixed << setprecision(10)

using namespace std;

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

    int n;
    cin >> n;


    vector<int> cnt(26);

    REP(i, n) {
        string s;
        cin >> s;


        vector<int> tmp(26);
        REP(j, s.size()) {
            if (i == 0) {
                cnt[s[j] - 'a']++;
                continue;
            }
            tmp[s[j] - 'a']++;
        }
        if (i == 0) continue;
        REP(j, cnt.size()) {
            cnt[j] = min(tmp[j], cnt[j]);
        }
    }

    string ans;
    REP(i, cnt.size()) {
        REP(j, cnt[i]) {
            ans += (char) ('a' + i);
        }
    }
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
inline void rd(int &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void rd(long long &x){
  int k, m=0;
  x=0;
  for(;;){
    k = getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
inline void wt_L(char a){
  putchar_unlocked(a);
}
inline void wt_L(long long x){
  char f[20];
  int m=0, s=0;
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    putchar_unlocked('-');
  }
  while(s--){
    putchar_unlocked(f[s]+'0');
  }
}
int N;
long long A[100000];
long long res[100000];
int main(){
  int i, j, k;
  long long x;
  rd(N);
  {
    int Lj4PdHRW;
    for(Lj4PdHRW=0;Lj4PdHRW<N;Lj4PdHRW++){
      rd(A[Lj4PdHRW]);
    }
  }
  for(i=1;i<N;i++){
    res[i] = A[i] - res[i-1];
  }
  x = (A[0] - res[N-1]) / 2;
  for(i=0;i<N;i++){
    if(i%2==0){
      res[i]+=x;
    }
    else{
      res[i]-=x;
    }
  }
  for(i=0;i<N;i++){
    res[i] *= 2;
  }
  for(i=0;i<N-1;i++){
    wt_L(res[(i+N-1)%N]);
    wt_L(' ');
  }
  wt_L(res[(i+N-1)%N]);
  wt_L('\n');
  return 0;
}
// cLay varsion 20190707-1

// --- original code ---
// int N; ll A[1d5];
// 
// ll res[1d5];
// {
//   int i, j, k;
//   ll x;
//   rd(N,A(N));
// 
//   rep(i,1,N) res[i] = A[i] - res[i-1];
// 
//   x = (A[0] - res[N-1]) / 2;
//   rep(i,N) res[i] if[i%2==0, +=, -=] x;
// 
//   rep(i,N) res[i] *= 2;
// 
//   rep(i,N-1){
//     wtSp(res[(i+N-1)%N]);
//   }
//   wt(res[(i+N-1)%N]);
// 
// }


Measured memory_bytes: 2816
#include <bits/stdc++.h>
using namespace std;
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define mp(a,b) make_pair((a),(b))
#define pb(a) push_back((a))
#define all(x) (x).begin(),(x).end()
#define uniq(x) sort(all(x)),(x).erase(unique(all(x)),end(x))
#define fi first
#define se second
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
void _dbg(string){cout<<endl;}
template<class H,class... T> void _dbg(string s,H h,T... t){int l=s.find(',');cout<<s.substr(0,l)<<" = "<<h<<", ";_dbg(s.substr(l+1),t...);}
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

#define INF 1120000000
#define long long long // for codeforces

int main(){
  int a,b,c;
  cin>>a>>b>>c;

  cout << a+b+c - max({a,b,c}) << endl;

  return 0;
}


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


public class Main {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();

		Set<Character> hs = new HashSet<>();
		for (int i = 0; i < n; i++) {
			char a = sc.next().toCharArray()[0];
			hs.add(a);
		}

		if (hs.size() == 3) {
			pr.println("Three");
		} else if (hs.size() == 4) {
			pr.println("Four");
		}
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(System.in);
		pr = new Printer(System.out);

		solve();

		pr.close();
		sc.close();
	}

	private static class Printer extends PrintWriter {
		Printer(PrintStream out) {
			super(out);
		}
	}
}


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

using namespace std;

int main()
{
    string s, t;
    cin >> s >> t;
    
    s = s + t[t.size()-1];
    
    if(s == t) {
        cout << "Yes" << endl;
    }
    else  cout << "No" << endl;
    
    
   
   return 0;
}

Measured memory_bytes: 3628
N,M = list(map(int,input().split()))
A = []
for i in range(N):
    A.append(tuple(map(int,input().split())))
f,s = 0,0
for i,j in sorted(A):
    f += j
    s += j * i
    #print(" ",j,s,dic[i],M)
    if(f >= M):
        print( s - i * (f-M) )
        break

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

using namespace std;

int main(void){
    string s, t;
    cin >> s >> t;
    int sum = 0;
    for(int i = 0; i < s.length(); i++){
        if(s[i] == t[i]) sum++;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 256
# coding: utf-8
# Your code here!

N = int(input())
d = list(map(int, input().split()))
dc = d[:]

ans = []

for i, v in enumerate(d):    
    for j, w in enumerate(dc):
        # print(i, j)
        if (i == j):
            continue        
        ans.append(v * w)

print(int(sum(ans)/2))

Measured memory_bytes: 9156
#include <algorithm>
#include <cmath>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <tuple>
#include <vector>

using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define reps(i, f, n) for (int i = (f); i < (n); i++)
#define repv(v) for (auto it = (v).begin(); it != (v).end(); it++)
ll const INF = 1LL << 60;

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

    vector<ll> X(N);
    rep(i, N) cin >> X[i];

    ll ans = 0;
    rep(i, N - 1) { ans += min(A * (X[i + 1] - X[i]), B); }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 4008
#include <bits/stdc++.h>
using namespace std;
int main(){
    int a,b;
    cin>>a>>b;
    if((4*a>=b)&&(b>=2*a)&&(b%2==0)){

        cout<<"Yes"<<endl;

    }
    else{
        cout<<"No"<<endl;
    }
}

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

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, pii> pipii;
typedef pair<pii, pii> piipii;

#define all(a) (a).begin(), (a).end()
#define sz(a) (int)(a).size()
#define eb emplace_back

ll dp[105][105][305];
int w[105], v[105];

int main(){
    int n, W;
    scanf("%d%d", &n, &W);
    for(int i=1;i<=n;i++) scanf("%d%d", &w[i], &v[i]);
    memset(dp, -1, sizeof(dp));
    dp[0][0][0] = 0;
    for(int i=1;i<=n;i++){
        for(int j=n;j>=0;j--){
            for(int k=n*3;k>=0;k--){
                if(dp[i-1][j][k] == -1) continue;
                dp[i][j][k] = max(dp[i][j][k], dp[i-1][j][k]);
                dp[i][j+1][k+w[i]-w[1]] = max(dp[i][j+1][k+w[i]-w[1]], dp[i-1][j][k] + v[i]);
            }
        }
    }
    ll ans = 0;
    for(int j=0;j<=n;j++){
        for(int k=0;k<=3*n;k++){
            ll T = j*1ll*w[1] + k;
            if(T <= W && dp[n][j][k] != -1) ans = max(ans, dp[n][j][k]);
        }
    }
    printf("%lld\n", ans);
}

Measured memory_bytes: 26496
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
long long n , k;
int a[200005];
int p[200005];
int t[200005];
int c[200005];
vector <long long> periods;
int nxt( int j){
return j%n + 1;
}
int main()
{
    cin >> n >> k;
    for(int i = 1 ; i <= n ; i++){
        cin >> a[i];
    }
    for(int i = 1 ; i <= 2*n ; i++){
        int j = (i-1)%n + 1;
        if(c[a[j]] == 0){
            c[a[j]] = j;
        }else{
            p[c[a[j]]] = j;
            t[c[a[j]]] = ( j - c[a[j]] + n - 1)%n + 1;
            c[a[j]] = j;
        }
    }
    for(int i = 1 ;i <= n; i++){
        //cout << p[i] << " " << t[i] << '\n';
    }
    long long period = 0;
    int pos = 1;
    period += t[pos] + 1;
    pos = nxt(p[pos]);
    while(pos!=1){
        period += t[pos] + 1;
        pos = nxt(p[pos]);
    }
    long long rest = (n*k)%period;
    pos = 1;
    while( rest > 0){
        if(rest > t[pos]){
            rest -= t[pos]+1;
            pos = nxt(p[pos]);
        }else{
            cout << a[pos] << " ";
            pos = nxt(pos);
            rest--;
        }
    }
    return 0;
}


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

int main() {
	string s;
	cin >> s;
	if (s.at(0) == s.at(2)) cout << "Yes" << endl;
	else cout << "No" << endl;
}


Measured memory_bytes: 3616
#include <iostream>
#include <algorithm>
#include <utility>
#include <string>
#include <vector>
#include <set>
#include <stack>
#include <queue>
#include <map>
#include <math.h>
#include <string.h>
#include <iomanip>
#include <numeric>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <functional>
#include <limits>

using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vll = vector<vl>;
using vpll = vector<pll>;

void debug_out() { cout << endl; }
 
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cout << H << " ";
  debug_out(T...);
}

#ifdef LOCAL
#define debug(...) cout << "debug: "; debug_out(__VA_ARGS__)
#else
#define debug(...) 
#endif

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; i--)
#define Rep(i, n) for (long long i = 0; i< (long long)(n); i++)
#define RRep(i,n) for (long long i = ((long long)(n)-1); i>=0; i--)
#define all(v) (v).begin(),(v).end()

struct Edge{
    int to;
    int weight;
    Edge(int t, int w) : to(t), weight(w){ }
};

struct edge{
    int from;
    int to;
    int weight;
    edge(int f,int t,int w) : from(f), to(t), weight(w){ }
};


using Graph = vector<vector<Edge>>;
using graph = vector<vector<int>>;
using edges = vector<edge>;

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

template <class T>
T gcd(T a, T b){
    if( b==0 ) return a;
    return gcd(b, a%b);
}

template <class T>
T lcm(T a, T b){
    return (a*b)/gcd(a,b);
}

bool isPalindrome(string s){
    string t = s;
    reverse(all(t));
    return s==t;
}

constexpr int INF = 1e9+7;

vector<int> dx = {-1,0,1,0};
vector<int> dy = {0,-1,0,1};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    if(s[2]==s[3] && s[4]==s[5]){
        cout << "Yes" << endl;
    }
    else{
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
n = int(input())
s = "MARCH"
cnt = [0, 0, 0, 0, 0]
for i in range(n):
    name = input()
    for j in range(len(s)):
        if name[0] == s[j]:
            cnt[j] += 1
cnt = [c for c in cnt if c > 0]
if len(cnt) < 3:
    print(0)
elif len(cnt) == 3:
    print(cnt[0]*cnt[1]*cnt[2])
elif len(cnt) == 4:
    ans = 0
    for i in range(4):
        ans += cnt[0]*cnt[1]*cnt[2]*cnt[3]//cnt[i]
    print(ans)
else:
    ans = 0
    for i in range(5):
        cnt_4 =[cnt[_] for _ in range(5) if _ != i]
        for j in range(4):
            ans += cnt_4[0]*cnt_4[1]*cnt_4[2]*cnt_4[3]//cnt_4[j]
    print(ans//2)

Measured memory_bytes: 3064
n = int(input())
A = list(map(int, input().split()))
B = [0 for i in range(n)]
C = [0 for i in range(max(A)+1)]
for i in A:
    C[i]+=1
for i in range(1, len(C)):
    C[i]+=C[i-1]
for i in range(0, n):
    B[C[A[i]]-1] = A[i]
    C[A[i]]-=1
print(" ".join(map(str, B)))


Measured memory_bytes: 242172
#include <iostream>
#include <bits/stdc++.h>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
using namespace std;
typedef long long ll;

int main() {
	// your code goes here
	
    int n;cin>>n;
    vector<int> arr(n);
    for(int i=0;i<n;i++) cin>>arr[i];
    sort(arr.begin(),arr.end());
    int count=0;
    for(int i=0;i<n-2;i++)
    {
      for(int j=i+1;j<n-1;j++)
      {
        for(int k=j+1;k<n;k++)
        {
          if(arr[i]!=arr[j]&&arr[j]!=arr[k]&&arr[i]!=arr[k])
          {
            if(arr[i]+arr[j]>arr[k]) count++;
          }
        }
      }

    }
    cout<<count<<endl;
	
	
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <cmath>
#include <cassert>
using namespace std;

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

    multiset<int> ms;
    for(int i=0; i<N; i++){
        auto itr = ms.upper_bound(A[i]);
        if(itr == ms.end()) ms.insert(A[i]);
        else{
            ms.erase(itr);
            ms.insert(A[i]);
        }
    }
    cout << ms.size() << endl;
    return 0;
}

Measured memory_bytes: 5376
#include<iostream>
#include<algorithm>
#include"stdio.h"
using namespace std;

#define N 100000
struct object{
    int weight;
    int price;
    
    bool operator < (const object &o) const {
        return (double)price / (double)weight > (double)o.price / (double)o.weight;
    }
};

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n,weight,index = 0;
    double totalPrice = 0;
    object o[N];
    cin >> n >> weight;
    
    for(int i = 0;i < n;++i){
        cin >> o[i].price >> o[i].weight;
    }
    
    sort(o,o + n);
    while(1){
        if(weight > o[index].weight){
            weight -= o[index].weight;
            totalPrice += o[index].price;
            if(index++ >= n){
                break;
            }
        }
        else{
            totalPrice += ((double)o[index].price / (double)o[index].weight * (double)weight);
            break;
        }
    }
    printf("%.8lf\n",totalPrice);
}



Measured memory_bytes: 3984
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<math.h>
#include<iomanip>
#include<set>
#include<numeric>
#include<cstring>
#include<cstdio>
#include<functional>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define REVERSE(v,n) reverse(v,v+n);
#define VREVERSE(v) reverse(v.begin(), v.end());
#define ll long long
#define pb(a) push_back(a)
#define INF 999999999
#define m0(x) memset(x,0,sizeof(x))
#define fill(x,y) memset(x,y,sizeof(x))



using namespace std;


int dy[4] = { 0,0,1,-1 };
int dx[4] = { 1,-1,0,0 };
int dxx[8] = { 0,0,1,1,1,-1,-1,-1 };
int dyy[8] = { 1,-1,0,1,-1,0,1,-1 };




ll gcd(ll x, ll y) {
	ll m = max(x, y), n = min(x, y);
	if (m%n == 0)return n;
	else return gcd(m%n, n);
}
ll lcm(ll x, ll y) {
	return x / gcd(x, y)*y;
}

ll myPow(ll x, ll n, ll m) {
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return myPow(x * x % m, n / 2, m);
	else
		return x * myPow(x, n - 1, m) % m;
}

long long nCr(int n, int r) {
	if (r > n / 2) r = n - r; // because C(n, r) == C(n, n - r)
	long long ans = 1;
	int i;

	for (i = 1; i <= r; i++) {
		ans *= n - r + i;
		ans /= i;
	}

	return ans;
}

ll F(ll a, ll b) {
	ll c1=0, c2=0;
	while (a > 0) {
		a /= 10;
		c1++;
	}
	while (b > 0) {
		b /= 10;
		c2++;
	}
	return max(c1, c2);
}

int a[300][300];
int main() {
	int N, M; cin >> N >> M;
	REP(i, N) {
		REP(j, M) {
			cin >> a[i][j];
		}
	}
	bool canceled[300];
	m0(canceled);
	int ans = INF;
	REP(k, M) {
		map<int, int>mp;

		REP(i, N) {
			REP(j, M) {
				if (canceled[a[i][j]])continue;
				mp[a[i][j]]++;
				break;
			}
		}

		int res = 0;
		for (auto x : mp) {
			res = max(res, x.second);
		}
		for (auto x : mp) {
			if (x.second == res) {
				canceled[x.first] = true;
				break;
			}
		}
		ans = min(ans, res);
	}
	cout << ans << endl;
}




Measured memory_bytes: 640
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define fi first
#define se second
#define endl '\n'
#define int int64_t
#define double long double
// mt19937 rnd(time(0));
// const double TIME_LIMIT = 1.8;
// Heuristic TL: clock() < TIME_LIMIT * CLOCKS_PER_SEC
const int MAXN = 200003;
const int INF = numeric_limits<int>::max() >> 3;
const int MOD = (int)998244353;

int cnt[2020];
int p10[MAXN];
signed main(){
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	// freopen("FDT.txt","r",stdin);
	string s;
	cin >> s;
	p10[0] = 1;
	for(int i = 1; i <= s.size() + 1; i ++) p10[i] = (p10[i - 1]*10)%2019;
	int cur = 0;
	int n = s.size();
	for(int i = n - 1; i >= 0; i --){
		cur = (cur + p10[n - 1 - i]*(s[i] - '0'))%2019;
		cnt[cur] ++;
	}
	cnt[0] ++;
	int ans = 0;
	for(int i = 0; i < 2019; i ++) ans += (cnt[i]*(cnt[i] - 1))/2;
	cout << ans;
}

Measured memory_bytes: 5360
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <numeric>
#define ll long long int
#define rep(i,n) for(int i=0;i<(n);i++)
#define pb push_back
using namespace std;
int mx4[] = {0,1,0,-1};
int my4[] = {1,0,-1,0};
int mx2[] = {1,0};
int my2[] = {0,1};

class DLine {
public:
	void solve(istream& in, ostream& out) {
        int n,x,y;
        in >> n >> x >> y;
        vector<int> ans(n);
        for(int i = 1;i < n;i++){
            for(int j = i + 1;j <= n;j++){
                ans[min(j - i,abs(j-y) + 1 + abs(x - i))]++;
            }
        }
        for(int i=1;i<n;i++){
            out << ans[i] << endl;
        }
	}
};

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

Measured memory_bytes: 256
# https://atcoder.jp/img/abc054/editorial.pdf
GC.disable
N, Ma, Mb = gets.chomp.split(" ").map(&:to_i)
a = []
b = []
c = []

N.times do
  abc = gets.chomp.split(" ").map(&:to_i)
  a << abc[0]
  b << abc[1]
  c << abc[2]
end

nmax = 40
abmax = 10
inf = c.max * N * 10

dp = Array.new(nmax+1){Array.new(nmax*abmax + 1){Array.new(nmax*abmax + 1, inf)}}
dp[0][0][0] = 0

(0...N).each do |i|
  (0..(nmax*abmax)).each do |ca|
    (0..(nmax*abmax)).each do |cb|
      next if dp[i][ca][cb] == inf
      dp[i+1][ca][cb] = [dp[i+1][ca][cb], dp[i][ca][cb]].min
      dp[i+1][ca+a[i]][cb+b[i]] = [dp[i+1][ca+a[i]][cb+b[i]], dp[i][ca][cb] + c[i]].min
    end
  end
end

ans = []
(1..(nmax*abmax)).each do |ca|
  (1..(nmax * abmax)).each do |cb|
    if ca*Mb == cb * Ma then
      ans << dp[N][ca][cb]
    end
  end
end

if ans.min == inf then
  puts -1
else
  puts ans.min
end


Measured memory_bytes: 127996
#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main() {

    string S;
    cin >> S;

    int length=0;
    int max_length=0;

    for(int i=0; i<S.length(); i++)
    {
        if(S[i]=='A' || S[i] =='C' || S[i] == 'G' || S[i] == 'T')
            length++;
        else
        {
            if(max_length < length)
            {
                max_length=length;
                length=0;
            }
            else
                length=0;
        }
    }
    
    if(max_length < length)
        max_length = length;

    cout<<max_length<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
using namespace std;
int main(){
	int c,max;
	int a,b;
	cin>>a>>b;
	max = a+b;
	c = a*b;
	if(c>max){
		max = c;
	}
	c = a-b;
	if(c>max){
		max = c;
	}
	cout<<max;
}

Measured memory_bytes: 256
#! /usr/bin/python3
# Palace

test = False

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

def main():
    d = {}
    for i in range(N):
        ave_T = T - (H[i] * 0.006)
        d['{}'.format(i+1)] = abs(A - ave_T)
    if test:
        print(d)

    min_k = min(d, key=d.get)
    print(min_k)


if __name__ == '__main__':
    main()


"""
https://note.nkmk.me/python-dict-value-max-min/
"""


Measured memory_bytes: 3316
#include<iostream>
#include<vector>
#include<set>
#include<stack>
#include<cmath>
#include<climits>
#include<cfloat>
using namespace std;

#define INF DBL_MAX
#define NONE INT_MAX
#define MAX 50.0

struct Point{double x,y;};
double dist(Point a,Point b){return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}

int main()
{
  int n,b,m,s,g;
  double x,y,M[1000][1000];
  while(cin>>n,n){
    vector<Point>building(n);
    for(int i=0;i<n;i++){
      cin>>b>>x>>y;
      b--;
      Point p={x,y};
      building[b]=p;
    }
    for(int i=0;i<n;i++)for(int j=0;j<n;j++){
      double t=dist(building[i],building[j]);
      if(i==j)M[i][j]=INF;
      else if(t>50.0)M[i][j]=INF;
      else M[i][j]=t;
    }

    cin>>m;
    for(int i=0;i<m;i++){
      cin>>s>>g;
      s--;g--;

      set<int>used;
      set<int>::iterator it;
      vector<double>d(n,INF);
      vector<int>p(n,NONE);
      d[s]=0;
      used.insert(s);
      while(used.size()!=n){
	bool end=true;
	double min=INF;
	int next,prev;
	for(int i=0;i<n;i++){
	  if(used.count(i))continue;
	  for(it=used.begin();it!=used.end();it++){
	    if(d[*it]+M[*it][i]<min){
	      min=d[*it]+M[*it][i];
	      next=i;
	      prev=*it;
	    }
	  }
	  if(min!=INF)end=false;
	}
	if(end)break;
	used.insert(next);
	p[next]=prev;
	d[next]=min;
      }

      stack<int>path;
      int t=g;
      while(p[t]!=NONE){
	path.push(p[t]);
	t=p[t];
      }
      if(path.size()&&path.top()==s){
	while(path.size()){
	  cout<<path.top()+1<<" ";
	  path.pop();
	}
	cout<<g+1<<endl;
      }else{
	puts("NA");
      }
    }
  }
}

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

int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int a,b,k,br=0;
    cin >> a >> b >> k;
    for (int i=min(a,b);i>=1;i--)
    {
        if(a%i==0 && b%i==0)
            br++;
        if(br==k)
        {
            cout << i;
            return 0;
        }
    }
}


Measured memory_bytes: 3612
#include <iostream>
#include <fstream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <utility>
#include <iomanip>
#include <chrono>
#include <random>
#include <bitset>

using namespace std;

#define sz(x) (int) x.size()
#define unique(x) x.erase(unique(x.begin(), x.end()), x.end())
#define all(a) a.begin(), a.end()
#define sqr(x) ((x) * (x)) 
#define y1 aksjdaskdjksjfksdjf
#define left kdnvldvoiwejifejg
#define right lkdsjflksdjfdjfk
#define prev asdasfsadjkjsdfjs
#define tm aklsjdasjdasjdkdjjf
#define lcm hddalkwjeidjjhasda
#define random_shuffle asdasdd

string s, t;
int a, b;
string go;

int main() { 

  cin >> s >> t;
  cin >> a >> b;
  cin >> go;

  if (go == s) {
    a--;
  } else {
    b--;
  }

  cout << a << " " << b << endl;

  return 0;
}


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

int main() {
    int n;
    cin >> n;
    string c;
    cin >> c;
    int cR = count(c.begin(), c.end(), 'R');
    cout << count(c.begin(), c.begin()+cR, 'W') << endl;
    return 0;
}

Measured memory_bytes: 3744
#include <bits/stdc++.h>
using namespace std;
constexpr int time_limit = 1950;
constexpr int iter_max = 2500000;
chrono::system_clock::time_point start, current;
int c[26];
int64_t s[366][26];


int64_t eval(const vector<int> &state, int d){
    int last[26] = {0};
    int64_t csum = 0;
    for(int i=0;i<26;++i) csum += c[i];
    int64_t decl = -csum;
    int64_t score = 0;

    for(int i=1;i<=d;++i){
        score += s[i][state[i]];
        decl += (i - last[state[i]])*c[state[i]];
        last[state[i]] = i;
        score += decl;
        decl -= csum;
    }
    return score;
}

vector<int> beam(int D, int w){
    map<int64_t, vector<int>, greater<int64_t>> mp;
    for(int i=0;i<26;++i){
        mp[eval(vector<int>{1, i}, 1)] = vector<int>{1, i};
    }
    for(int d=2;d<=D;++d){
        int cnt = 0;
        vector<vector<int>> states;
        for(auto p: mp){
            states.push_back(p.second);
            ++cnt;
            if(cnt >= w) break;
        }
        mp.clear();
        for(auto v: states){
            for(int i=0;i<26;++i){
                vector<int> state{v};
                state.emplace_back(i);
                mp[eval(state, d)] = state;
            }
        }
    }
    return mp.begin()->second;
}

int main(){
    start = chrono::system_clock::now();
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout.precision(12);
    cout.setf(ios_base::fixed, ios_base::floatfield);

    int d;
    cin >> d;
    for(int i=0;i<26;++i) cin >>c[i];
    for(int i=1;i<=d;++i){
        for(int j=0;j<26;++j) cin >> s[i][j];
    }

    auto ans = beam(d, 250);
    for(int i=1;i<=d;++i) cout << ans[i] + 1 << endl;

    return 0;
}

Measured memory_bytes: 12812