akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <string.h>

char* make(char*s) {
	int i, j;
	static char out[52];
	for (i=0; i < 52 ;i++) out[i] = 0;
	out[0] = s[0];
	for (i=0, j=1; i+1 < strlen(s) ;i++) {
		if (s[i] == 'a' ||
			s[i] == 'i' ||
			s[i] == 'u' ||
			s[i] == 'e' ||
			s[i] == 'o') {
			out[j] = s[i+1];
			j++;
		}
	}
	return out;
}

char* check(int i, char*s) {
	int j;
	static char out[52] = {0};
	for (j=0; j < 52 ;j++) out[j] = 0;
	for (j=0; j < i ;j++) {
		out[j] = s[j];
	}
	return out;
}

int main() {
	int i, j, k, l, N, max;
	char s[51][52], sa[2][52];
	while (1) {
		max = 0;
		scanf("%d", &N);
		if (N == 0) break;
		for (i=0; i < N ;i++) {
			scanf("%s", &s[i]);
			strcpy(s[i], make(s[i]));
			if (max < strlen(s[i])) {
				max = strlen(s[i]);
				// max: printf("%d: %s\n", max, s[i]);
			}
		}
		for (i=1; i <= max ;i++) {
			for (j=0, l=0; j < N ;j++) {
				for (k=0; k < N ;k++) {
					strcpy(sa[0], check(i, s[j]));
					strcpy(sa[1], check(i, s[k]));
					if (j != k && !strcmp(sa[0], sa[1])) {
						l++;
					}
				}
			}
			if (l == 0) {
				printf("%d\n", i);
				break;
			}
		}
		if (l != 0) printf("-1\n");
	}
	return 0;
}

Measured memory_bytes: 644
from fractions import gcd
from functools import reduce
n=int(input())
a=list(map(int,input().split()))
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
k=0
m=lcm_list(a)-1
for i in range(n):
    k+=m%a[i]
print(k)

Measured memory_bytes: 5332
m, d = map(int, input().split())

if d == 28 and m == 2:
  print(1)
elif d == 30 and m in [4,6,9,11]:
  print(1)
elif d == 31 and m in [1, 3, 5, 7, 8, 10, 12]:
  print(1)
else:
  print(0)

Measured memory_bytes: 3060
#include <cstdio>
#include <vector>
using namespace std;
using Graph = vector< vector<int> >;

int dfs(Graph &G, int cur, int par=-1) {
    int grundy = 0;
    for(auto to : G[cur]) {
        if(to == par) continue;
        grundy ^= dfs(G, to, cur) + 1;
    }
    return grundy;
}

int main() {
    int N; scanf("%d", &N);
    Graph G(N);
    for(int i=0; i<N-1; i++) {
        int u, v; scanf("%d%d", &u, &v);
        u--; v--;
        G[u].push_back(v);
        G[v].push_back(u);
    }

    printf("%s\n", dfs(G, 0) ? "Alice" : "Bob");
    return 0;
}

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

int main() {
  int N;
  cin >> N;
  std::vector<long> a(3 * N);
  for (long& a_i: a) {
    std::cin >> a_i;
  }
  sort(a.rbegin(), a.rend());
  int team_num = a.size() / 3;

  // x o x o x o x x x
  long count = 0;
  for (int i = 0; i < team_num * 2; i++) {
    if (i % 2 == 1) {
      count += a.at(i);
    }
  }
  cout << count << endl;
}


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

bool ispal(string s, int st, int en)
{
    for(int i = st; i <= en; i++)
        if(s[i]!=s[en-i]) return false;
    return true;
}

int main()
{
 	string s;
 	cin >> s;
 	int n=s.size();
 	if(ispal(s, 0, n-1))
    {
        if(ispal(s, 0, (n-1)/2-1) and ispal(s, (n+3)/2, n-1)) cout << "Yes\n";
        else cout << "No\n";
    }
    else cout << "No\n";
}


Measured memory_bytes: 3648
import java.util.*;
public class Main {

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

    int k = sc.nextInt();
    int a = sc.nextInt();
    int b = sc.nextInt();

    for (int i = a; i <= b; i++) {
      if (i % k == 0) {
        System.out.println("OK");
        sc.close();
        return;
      }
    }
    System.out.println("NG");



    sc.close();

  }
}

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

int main(void){
    int n;
    vector<int> path[100010], miti;
    set<int> vis;
    map<int, int> map;
    cin >> n;
    for(int i=0;i<n-1;++i){
        int a, b;
        cin >> a >> b;
        path[a].push_back(b);
        path[b].push_back(a);
    }
    queue<int> que, ans;
    for(int i=0;i<path[1].size();++i){
        que.push(path[1][i]);
        map.insert(make_pair(path[1][i], 1));
    }
    vis.insert(1);
    while(!que.empty()){
        int now = que.front();
        que.pop();
        for(int i=0;i<path[now].size();++i){
            if(!vis.count(path[now][i])) que.push(path[now][i]);
            map.insert(make_pair(path[now][i], now));
        }
        if(now==n) break;
        vis.insert(now);
    }
    int now = n, cnt=0;
    while(true){
        if(now==1) break;
        miti.push_back(now);
        now = map.at(now);
        ++cnt;
    }
    int half = miti[(cnt-1)/2];
    vis.clear();
    for(int i=0;i<path[1].size();++i){
        if(!vis.count(path[1][i])){
            ans.push(path[1][i]);
            map.insert(make_pair(path[1][i], 1));
        }
    }
    cnt = 1;
    vis.insert(1);
    while(!ans.empty()){
        int now = ans.front();
        ans.pop();
        if(now==half) continue;
        ++cnt;
        for(int i=0;i<path[now].size();++i){
            if(!vis.count(path[now][i])) ans.push(path[now][i]);
            map.insert(make_pair(path[now][i], now));
        }
        vis.insert(now);
    }
    if(cnt>n/2) cout << "Fennec\n";
    else cout << "Snuke\n";
}

Measured memory_bytes: 15740
#include<bits/stdc++.h>
using namespace std;
set<string>ma;
unordered_set<string>unset;
int letter[26];
inline bool judge(string &s){
    int cont=0;
    memset(letter,0,sizeof(letter));
    string key;
    for(int i=0;i<s.size();i++){
        if(letter[s[i]-'a']==0){
            ++cont;
            letter[s[i]-'a']=cont;
            key.push_back('0'+cont);
        }else{
            key.push_back('0'+letter[s[i]-'a']);
        }
    }
    if(unset.find(key)==unset.end()){
        unset.insert(key);
        return true;
    }else{
        return false;
    }
}
 
 
void dfs(int loc,int &n,string &s){
    if(loc>n){
        if(judge(s)){
            ma.insert(s);
        }
        return;
    }
    for(int i=0;i<loc;i++){
        s.push_back('a'+i);
        dfs(loc+1,n,s);
        s.erase(s.end()-1);
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int n;
    cin>>n;
    string s="a";
    dfs(2,n,s);
    for(auto i=ma.begin();i!=ma.end();i++){
        cout<<(*i)<<endl;
    }
    return 0;
}

Measured memory_bytes: 24228
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))

def main():
    a, b = MII()
    if b%a == 0: print(a+b)
    else: print(b-a)

if __name__ == '__main__':
    main()


Measured memory_bytes: 2940
import numpy as np
def resolve():
    n, w = map(int, input().split())
    goods = np.array([list(map(int, input().split())) for _ in range(n)])
    dp = np.zeros([n + 1, w + 1], dtype=int)

    for i in range(1, n + 1):
        tmp = np.zeros(w + 1, dtype=int)
        tmp[goods[i - 1][0]:] = dp[i - 1][:-goods[i - 1][0]] + goods[i - 1][1]
        dp[i] = np.maximum(dp[i - 1], tmp)

    print(dp[n][w])
    
resolve()

Measured memory_bytes: 92852
#include <iostream>
#include <stdio.h>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cstring>
#include <algorithm>
#include <math.h>

using namespace std;

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

#define FOR(i,n,m) for(int i=n; i<(int)m; i++)
#define ROF(i,n,m) for(int i=n; i>(int)m; i--)
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define ri(a) scanf("%d",&a)
#define rii(a,b) ri(a),ri(b)
#define riii(a,b,c) rii(a,b),ri(c)
#define lri(a) scanf("%lld",&a)
#define lrii(a,b) lri(a),lri(b)
#define ms(obj,val) memset(obj,val,sizeof(obj))
#define all(x) x.begin(),x.end()
#define debug true
#define dprintf debug && printf

const int INF = 0x3f3f3f3f;
const ll INFLL = 1e18;
const int MOD = 1e9+7;
const int MAXN = 3e5+5;

ll BIT[MAXN];

void updBIT(int p, ll val){
    p += MAXN/2;
    for(; p < MAXN; p += p&-p) BIT[p] += val;
}

ll sumBIT(int p){
    p += MAXN/2;
    ll ret = 0;
    for(; p; p -= p&-p) ret += BIT[p];
    return ret;
}

int a[MAXN];
int n;

ll count(int x){
    ms(BIT, 0);
    int acum = 0;
    ll ret = 0;
    updBIT(0, 1);
    FOR(i,0,n){
        acum += (a[i] > x ? -1 : 1);
        ret += sumBIT(acum-1);
        updBIT(acum, 1);
    } 
    return ret;
} 

ll sum(ll x){
    return (x*(x+1))/2;
}

int main(){
    //ios_base::sync_with_stdio(false);
    //cin.tie(NULL);

    ri(n);
    FOR(i,0,n) ri(a[i]);

    int l = 0, r = INF;
    while(l < r){
        int mid = (l+r)>>1;
        if(count(mid) >= sum(n)/2 + 1) r = mid;
        else l = mid + 1;
    }
    printf("%d\n", r);

    return 0;
}


Measured memory_bytes: 2944
#include<iostream>
#include<vector>
#include<string>
#define rep(i, start, end) for (int i = (int)start; i < (int)end; ++i)
#define rrep(i, start, end) for (int i = (int)start - 1; i >= (int)end; --i)
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
template<typename T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return true;} return 0;}
template<typename T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return true;} return 0;}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    string S, T;
    int A, B;
    string U;
    cin >> S >> T >> A >> B >> U;
    cout << A - (S == U ? 1 : 0) << ' ' << B - (T == U ? 1 : 0) << 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 repr(i, n) for(int i = (n-1); i >= 0; --i)

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

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

const int MAX = 200005;
const int INF = 1001001001;
const int MOD = 1000000007;

struct mint {
    long long x;
    mint(long long x=0):x(x % MOD + (0 <= x ? 0 : MOD)) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint& a) { if ((x += a.x) >= MOD) x -= MOD; return *this; }
    mint& operator-=(const mint& a) { if ((x -= a.x) < 0) x += MOD; return *this; }
    mint& operator*=(const mint& a) { (x *= a.x) %= MOD; return *this; }
    mint operator+(const mint& a) const { return mint(x) += a; }
    mint operator-(const mint& a) const { return mint(x) -= a; }
    mint operator*(const mint& a) const { return mint(x) *= a; }

    // for prime mod
    mint inv() const {
        long long a = x, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        return mint(u);
    }
    mint& operator/=(const mint& a) { return *this *= a.inv(); }
    mint operator/(const mint& a) const { return mint(x) /= a; }
};
istream& operator>>(istream& is, const mint& a){ return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a){ return os << a.x; }

long long mod_pow(long long x, long long n, int M=1000000007) {
    long long ret = 1;
    while(n) {
        if(n & 1) (ret *= x) %= M;
        (x *= x) %= M;
        n >>= 1;
    }
    return ret;
}

struct prime_factorized {
    map<int, int> m;
    prime_factorized(int x=1) {
        for (int i = 2; i * i <= x; ++i) {
            while (x % i == 0) x/=i, m[i]++;
        }
        if (x > 1) m[x]++;
    }
    prime_factorized& lcm(const prime_factorized &a) {
        for (const pair<int, int> &p : a.m) {
            m[p.first] = max(m[p.first], p.second);
        }
        return *this;
    }
    prime_factorized& operator /= (const prime_factorized &a) {
        for (const pair<int, int> &p : a.m) {
            m[p.first] -= p.second;
        }
        return *this;
    }
    prime_factorized operator / (const prime_factorized &a) const {
        return prime_factorized(*this) /= a;
    }
    mint mod_num (int mod=1000000007) const {
        mint res = 1;
        for (const pair<int, int> &p : m) {
            if (p.second > 0) res *= mod_pow(p.first, p.second);
            else if (p.second < 0) res /= mod_pow(p.first, -p.second);
        }
        return res;
    }
};

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

    vector<int> A(N);
    for (int &i : A) cin >> i;

    prime_factorized lcm;
    for (int &i : A) {
        lcm.lcm(prime_factorized(i));
    }

    mint lcm2 = lcm.mod_num();

    mint ans = 0;
    for (int &i : A) {
        ans += lcm2 / i;
    }

    cout << ans << endl;
}

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

ll query(ll x,ll y){
  ll a=x; ll b=y;
  //n²<x*y<=n(n+1)または
  //n(n+1)<x*y<=(n+1)²
  ll k=x*y;
  ll nib=(x+y)/2;
  while(1){
    if(nib*nib<x*y){
      if((nib+1)*(nib+1)>=x*y){
        break;
      }else{
        a=nib; nib=(nib+b)/2;
      }
    }else{
      b=nib; nib=(a+nib)/2;
      if(a==nib){
        break;
      }
    }
  }
  if(nib*(nib+1)<x*y){
    return (nib-x)*2+1;
  }else{
    return (nib-x)*2;
  }
}

int main(){
  ll Q; cin >> Q;
  ll A,B,C;
  for(int i=0;i<Q;i++){
    cin >> A >> B;
    if(A>B){
      C=A; A=B; B=C;
    }
    cout << query(A,B)+A*2-2 << endl;
  }
}

Measured memory_bytes: 256
X,Y,A,B,C = list(map(int,input().split()))
p = sorted(list(map(int,input().split())),reverse=True)
q = sorted(list(map(int,input().split())),reverse=True)
r = sorted(list(map(int,input().split())),reverse=True)

taberu = p[0:X] + q[0:Y] + r
taberu.sort(reverse=True)

print(sum(taberu[0:X+Y]))


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

using ll = long long;
using namespace std;

void go(int x) {
   cout << x << endl;
   exit(0);
}

void solve() {
   int x, y;
   cin >> x >> y;
   if(x == 0 || y == 0) {
      if(x == 0) {
         if(y >= 0) go(y - x);
         else go(abs(y) + 1);
      } else if(y == 0) {
         if(x < 0) go(abs(x));
         else go(abs(x) + 1);
      }
   }
   if(x < y) {
      if(x * 1LL * y >= 0) {
         go(y - x);
      } else {
         go(1 + abs(abs(y) - abs(x)));
      }
   } else if(x == y) {
      go(0);
   } else {
      //x > y;
      if(x * 1LL * y >= 0) {
         go(2 + abs(abs(x) - abs(y)));
      } else {
         go(1 + abs(abs(x) - abs(y)));
      }

   }
}


int main() {
   cin.tie(0);
   cin.sync_with_stdio(0);
   
   int testcase = 1;
   // cin >> testcase;
 
   for(int i = 0; i < testcase; i++) {
      solve();
   }
 
   return 0;
}

Measured memory_bytes: 3660
import java.util.*;
public class Main{

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        
        StringBuilder sb = new StringBuilder();
        //入力
        while(sc.hasNext()){
            String str = sc.nextLine();
            sb.append(str.toLowerCase());
        }
        
        Map<Character,Integer> map = new HashMap<>();
        map.put('a',0);
        map.put('b',0);
        map.put('c',0);
        map.put('d',0);
        map.put('e',0);
        map.put('f',0);
        map.put('g',0);
        map.put('h',0);
        map.put('i',0);
        map.put('j',0);
        map.put('k',0);
        map.put('l',0);
        map.put('m',0);
        map.put('n',0);
        map.put('o',0);
        map.put('p',0);
        map.put('q',0);
        map.put('r',0);
        map.put('s',0);
        map.put('t',0);
        map.put('u',0);
        map.put('v',0);
        map.put('w',0);
        map.put('x',0);
        map.put('y',0);
        map.put('z',0);
        
        for(int i=0; i<sb.length(); i++){
            char c = sb.charAt(i);
            for(Character alphabet : map.keySet()){
                if(alphabet == c){
                    map.put(alphabet, map.get(alphabet)+1);
                }
            }
        }
        
        for(Character alphabet : map.keySet()){
            System.out.println(alphabet + " : " + map.get(alphabet));
        }


    }

}




Measured memory_bytes: 26836
#include<bits/stdc++.h>
using namespace std;
#define debug(x) cout << '>' << #x << ':' << x << endl;
#define ll long long

int main() {
	string s;
	cin >> s;
	int n = s.size();
	int ans = 1e9;
	for (int i = 0; i < 26; i++) {
		char c = 'a' + i;
		int num1 = -1;
		int cnt = 0;
		for (int j = n - 1; j >= 0; j--) {
			if (s[j] == c) {
				num1 = cnt;
				cnt = 0;
				break;
			} else
				cnt++;
		}
		int num2 = -1;
		for (int j = 0; j < n; j++) {
			if (s[j] == c) {
				num2 = max(num2, cnt);
				cnt = 0;
			} else
				cnt++;
		}
		int sum = max(num2, num1);
		if (num1 != -1){
			ans = min(ans, sum);
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3588
import std.stdio,std.string;
import std.conv,std.math;
void main(){
    int [] n = readln.chomp.split.to!(int[]);
    if((abs(n[0]-n[1])<=n[3] &&abs(n[1]-n[2])<=n[3])
    ||abs(n[0]-n[2])<=n[3]){
        writeln("Yes");
    }
    else{
        writeln("No");
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll, ll> P;
typedef vector<ll> VI;
typedef vector<VI> VVI;
const ll MOD = 1000000007;
const ll INF = 1073741823;
const ll LINF = 4611686018427387903;
#define REP(i, n) for (int i = 0; i < n; i++)
#define ALL(v) v.begin(), v.end()

int main() {
	string s, t;
	cin >> s >> t;
	REP(i,s.size()){
		if(s[i]!=t[i]){
			cout << "No" << endl;
			return 0;
		}
	}
	cout << "Yes" << endl;
	return 0;
	return 0;
}

Measured memory_bytes: 3596
#include <iostream>
#include <stdio.h>
#include <cmath>
#include <algorithm> // sort
#include <map>       // pair
#include <vector>
using namespace std;

#define REP(a,b) for(int i =(a);i < (b);i++)
#define FOR(n) for(int i = 0; i<(n); i++)
#define COUT(c)  cout<<(c)<<endl


const int INF = 100100100;
const int MOD = (int)1e9 +7;
const double EPS = 1e-9; 

typedef long long int ll;

//char in[120];
//ex. pair
//pair<pair<string,int>,int> p[110];

int main(){
    int n;cin>>n;
    if (n < 1200) COUT("ABC");
    else if (n < 2800) COUT("ARC");
    else COUT("AGC");
    return 0;    
}

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

using namespace std;

using ll = long long;

const ll MOD = 1000000007;

const int dx[4] = {+1, 0, -1, 0};
const int dy[4] = {0, -1, 0, +1};

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    int n, m; cin >> n >> m;
    vector<int> graph[n];
    for(int i=0;i<m;i++){
        int x, y, z;
        cin >> x >> y >> z; x--; y--;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }
    bool visited[n];
    memset(visited, false, sizeof visited);
    ll cnt = 0;
    for(int i=0;i<n;i++){
        if(!visited[i]){
            queue<int> Q;
            visited[i] = true;
            Q.push(i);
            while(!Q.empty()){
                int v = Q.front(); Q.pop();
                for(int u: graph[v]){
                    if(!visited[u]){
                        visited[u] = true;
                        Q.push(u);
                    }
                }
            }
            cnt++;
        }
    }
    cout << cnt << endl;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define UB upper_bound
#define LB lower_bound
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int a, b, h;

int main() {
	cin >> a >> b >> h;
	
	cout << (a + b) * h / 2 << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define mod 1000000007
#define inf 1000000000000000000
#define bpc(x) __builtin_popcountll(x)
#define autoit(x,it) for(auto it = x.begin(); it != x.end(); it++)
#define rep(n) for(ll i = 0; i < n; i++)
#define repi(i,n) for(ll i = 0; i < n; i++)

#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> 

using namespace std;

int main()
{
  FAST/**/
   
   ll x,y;
   cin>>x>>y;
   
   for(ll i=0;i<=x;i++)
   {
       if(i*2 + (x-i)*4 == y)
       {
           cout<<"Yes";
           return 0;
       }
   }
   
   cout<<"No\n";
   
   return 0;        
}  
  
          
   

Measured memory_bytes: 3632
#include <stdio.h>
#define MAX 100
#define INF 1000000
#define NIL -1

void MST();

int n;
int a[MAX][MAX];
int heap_size;
int key[MAX];
int pi[MAX];

main(){
  int i, j, total=0;
  scanf("%d",&n);
 
  for(i=0; i<n; i++){
    for(j=0; j<n; j++){
      scanf("%d",&a[i][j]);
    }
  }
 
  MST();
  for(i=0; i<n; i++) total+=key[i];
  printf("%d\n",total);
 
  return 0;
}


void MST(){
  int u, v, v1, flag[MAX], minv, i;
 
  for(u=0; u<n; u++){
    key[u]=INF;
    pi[u]=NIL;
    flag[u]=0;
  }
 
  key[0]=0;
 
  for(v1=0;v1<n; v1++){
   
    minv = INF;
    for ( i = 0; i < n; i++ ){
      if(flag[i]==1) continue;
      if(key[i]<=minv){
    u=i;
    minv=key[i];
      }
    }
   
    for(v=0; v<n; v++){
      if(a[u][v]==-1) continue;
      if(flag[v]==1) continue;
      if(a[u][v]<key[v]){
    pi[v]=u;
    key[v]=a[u][v];
      }
    }
    flag[u]=1;
  }
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
// #define LOCAL
#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif // LOCAL
int const nax = 3e5 + 10;

int n, t[nax];
string s[nax];

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

    for(int i = 1; i <= n; i++){
        cin >> s[i] >> t[i];
    }
    string tar;
    cin >> tar;
    for(int i = 1 ;i <= n; i ++){
        if(s[i] == tar){
            long long ans = 0;
            for(int j = i + 1 ;j <= n; j++)
                ans += t[j];
            cout << ans << '\n';
            return 0;
        }
    }
}
/*
    Good Luck
        -Lucina
*/


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

int main(void){
    int n;
    std::cin >> n;
    std::vector<int> x(n);
    int distance = 0;
    int answer = 1000000000;

    for(int i = 0; i < n; i++){
        std::cin >> x[i];
    }
    for(int i = 0; i < 100; i++){
        for(int j = 0; j < n; j++){
            distance += (i - x[j]) * (i - x[j]);
        }
        if(distance < answer){
            answer = distance;
        }
        distance = 0;
    }

    std::cout << answer << std::endl;    
    
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a*4-b<0 || (a*4-b)%2!=0 || b-a*2<0)cout<<"No\n";else cout<<"Yes\n";
	return 0;
}


Measured memory_bytes: 3616
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " = " << x << endl

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const ll Mod = 1e9 + 7;
const int Maxn = 1e5 + 10;
const ll Inf = 1e16;

ll a[3 * Maxn];
ll n;
multiset<ll> st; ll s = 0;

void add(ll x){
	st.insert(x);
	s += x;
	if(st.size() > n){
		s -= (*st.begin());
		st.erase(st.begin());
		//cerr << st.size() << '\n';
	}
}
ll dp[3 * Maxn], dp2[3 * Maxn];
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	//ll n;
	cin >> n;
	for(int i = 0; i < 3 * n; i++) cin >> a[i];
	
	st.clear(); s = 0;
	for(int i = 0; i < 3 * n; i++){
		add(a[i]);
		dp[i + 1] = s;
	}
	reverse(a, a + n + n + n);
	
	st.clear(); s = 0;
	for(int i = 0; i < 3 * n; i++){
		add(-a[i]);
		dp2[i + 1] = s;
	}
	ll ans = -Inf;
	//cerr << ans << '\n';
	for(int i = n; i <= n + n; i++) ans = max(ans, dp[i] + dp2[n + n + n - i]);
	cout << ans;
	return 0;
}



Measured memory_bytes: 12032
#define _LIBCPP_DEBUG 0
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
ll MOD = 1e9 + 7;


int main(void) {

    int N; cin>>N;
    vector<double> X(N);
    double ave=0;
    for (int i = 0; i < N; ++i) {
        cin>>X[i];
        ave += X[i];
    }
    ave /= N;
    ave = round(ave);

    ll ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += pow(abs(X[i]-ave), 2);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main() {
  int no_of_input;
  string input;
  cin >> no_of_input >> input;
  int ans = 0;
  input += '-';
  for(int i=0;i<no_of_input;){
    int pos = i;
    while(i<no_of_input&&input[i]==input[pos]){
      i++;
    }
    ans++;
  }
  cout << ans;
}

Measured memory_bytes: 512
# -*- coding: utf-8 -*-

def check_palindrome(S):
    for i in range(int(len(S) / 2)):
        if S[i] != S[-1 * (i + 1)]:
            return False
    return True

S = input()

if not check_palindrome(S):
    print('No')
else:
    if not check_palindrome(S[:int(len(S) / 2)]):
        print('No')
    else:
        if not check_palindrome(S[int(len(S) / 1) + 2:]):
            print('No')
        else:
            print('Yes')

Measured memory_bytes: 3064
// AOJ - ALDS1
// ALDS1_2_C - Stable sort
// https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/2/ALDS1_2_C

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

type card struct {
	suite string
	num   int
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func ssort(a []card) (sw int) {
	n := len(a)
	for i := 0; i < n; i++ { // i-1番目までソート済みとする
		minv := a[i].num // i番目の値とそのインデックスを覚えておく
		mini := i
		for j := i + 1; j < n; j++ { // i+1番目以降で、minvより小さい値を探す
			if minv > a[j].num { // a[j]の方がminvより小さい
				minv = a[j].num // minv, miniを更新
				mini = j
			}
		}
		if i != mini {
			a[mini], a[i] = a[i], a[mini] // i番目の値とmini番目の値を交換する
			sw++
		}
	}
	return
}

func bsort(a []card) (sw int) {
	n := len(a)
	for i := 0; i < n; i++ {
		for j := n - 1; j >= i+1; j-- {
			if a[j].num < a[j-1].num {
				a[j], a[j-1] = a[j-1], a[j]
				sw++
			}
		}
	}
	return
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanLines)
	sc.Scan()
	n, _ := strconv.Atoi(sc.Text())
	sc.Scan()
	ss := strings.Split(sc.Text(), " ")
	cards := make([]card, n)
	for i := 0; i < len(ss); i++ {
		cards[i].suite = string(ss[i][0])
		cards[i].num = int(ss[i][1] - '0')
	}
	ccb := make([]card, n)
	copy(ccb, cards)
	bsort(ccb)
	showCards(ccb)
	fmt.Println("Stable")
	ccs := make([]card, n)
	copy(ccs, cards)
	ssort(ccs)
	showCards(ccs)
	for i := 0; i < n; i++ {
		if ccs[i].suite != ccb[i].suite {
			fmt.Println("Not stable")
			return
		}
	}
	fmt.Println("Stable")
}
func showCards(c []card) {
	for i := 0; i < len(c); i++ {
		if i > 0 {
			fmt.Print(" ")
		}
		fmt.Printf("%s%d", c[i].suite, c[i].num)
	}
	fmt.Println()
}



Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PLL = pair<ll, ll>;
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repn(i,n) for(int i = 0; i <= (int)(n); i++)
#define srep(i,l,n) for(int i = l; i < (int)(n); i++)
#define srepn(i,l,n) for(int i = l; i <= (int)(n); i++)
#define drep(i,n) for(int i = (int)(n-1); i >= 0; i--)
#define drepn(i,n) for(int i = (int)(n); i >= 0; i--)
#define size(s) (int)s.size()
#define debug(var)  do{std::cout << #var << " : ";view(var);}while(0)
template<typename T> void view(T e){std::cout << e << std::endl;}
template<typename T> void view(const std::vector<T>& v){for(const auto& e : v){ std::cout << e << " "; } std::cout << std::endl;}
template<typename T> void view(const std::vector<std::vector<T> >& vv){ for(const auto& v : vv){ view(v); } }
template<typename T> inline istream& operator>>(istream &i, vector<T> &v) {rep(j, size(v)) i >> v[j]; return i;}
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> T gcd(T a, T b) {if(b==0)return a; else return gcd(b,a%b);}
template<class T> T lcm(T a, T b) {return a/gcd(a,b)*b;}
template<class T = int> using V = vector<T>;
template<class T = int> using VV = vector<V<T>>;
bool isIn(int i, int j, int h, int w) {return i >= 0 && i < h && j >= 0 && j < w;}
void Yes(){cout << "Yes" << endl;}
void No(){cout << "No" << endl;}
void YES(){cout << "YES" << endl;}
void NO(){cout << "NO" << endl;}
void err() {cout << -1 << endl;}
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
#define ep emplace_back

const int MOD = 1000000007;
const int INF = 1e9;

#define PI acos(-1);
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int ddx[8] = {1,1,1,-1,-1,-1,0,0};
int ddy[8] = {0,1,-1,0,1,-1,1,-1};


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int a, b, c, x;
    cin >> a >> b >> c >> x;
    int ans = 0;
    repn(i, a) repn(j, b) repn(k, c) {
        if(500 * i + 100 * j + 50 * k == x) ans++;
    }
    cout << ans << endl;
}

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

using namespace std;

typedef long long int ll;

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

    int n;
    cin >> n;
    int a[n];
    for(int i=0 ; i<n ; i++)
        cin >> a[i];
    ll cur=1,ans=0;
    for(int i=0 ; i<n; i++)
    {
        if(a[i]==cur)
            {
                cur++;
                continue;
            }
        else
        {
            ans++;
        }
    }
    if(ans==n)
        cout << -1;
    else
        cout << ans;
    return 0;
}


Measured memory_bytes: 1024
#include<stdio.h>
int main(void){
  char *s="python3 -c\""
"n,*a=map(int,open(0).read().split())\n"
"for i in range(n-1):a[i+1]+=a[i]\n"
"j,k,m=0,2,1e18\n"
"for i in range(1,n-1):\n"
" while abs(a[j]*2-a[i])>abs(a[j+1]*2-a[i]):j+=1\n"
" while abs(a[k]*2-a[i]-a[n-1])>abs(a[k+1]*2-a[i]-a[n-1]):k+=1\n"
" t=a[j],a[i]-a[j],a[k]-a[i],a[n-1]-a[k];m=min(m,max(t)-min(t))\n"
"print(m)\n"
"\"";
  system(s);
  return 0;
}            

Measured memory_bytes: 25340
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
	int a;
	scanf("%d",&a);
	while(a--){
		int b;
		int c,d;
		scanf("%d%d%d",&b,&c,&d);
		int ret=0;
		for(int i=0;i<d;i++){
			int e;
			double f;
			int g;
			scanf("%d%lf%d",&e,&f,&g);
			if(!e){
				int h=b;
				int v=0;
				for(int j=0;j<c;j++){
					v+=f*h;
					h-=g;
				}
				ret=max(ret,h+v);
			}else{
				int h=b;
				for(int j=0;j<c;j++){
					h=h+f*h-g;
				}
				ret=max(ret,h);
			}
		}
		printf("%d\n",ret);
	}
}

Measured memory_bytes: 1060
#include<bits/stdc++.h>
#define maxn 100000009
using namespace std;

int a[maxn];
int main()
{
	int t;
	while(cin>>t)
	{
		int con=0,num=0;
		for(int i=1;i<=t;++i)
		{
			cin>>a[i];
		}
		int k = a[1];
		for(int i =2;i<=t;++i)
		{
			if(k>=a[i])
			{
				num++;
				k=a[i];
			}
			if(k<a[i])
			{
				con = max(num,con);
				num = 0;
				k = a[i];
			}
		}
		con = max(con,num);
		cout<<con<<endl;
	}
}


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 ld = long double;
using P = pair<int, int>;

int main() {
	int n, m;
	cin >> n >> m;
	int ans = 0;
	if (n > 1) ans += n * (n - 1) / 2;
	if (m > 1) ans += m * (m - 1) / 2;
	cout << ans << endl;
}

Measured memory_bytes: 256
#!/usr/bin/env python3
from itertools import accumulate

def main():
    N = int(input())
    A = list(map(int, input().split()))
    accumA = list(accumulate(A[::-1]))[::-1]
    ans = 1
    ne = [0] * (N+1)
    ne[0] = 1

    if A[0] != 0:
        if A[0] == 1 and N == 0:
            print(1)
            exit()
        else:
            print(-1)
            exit()


    for i in range(1,N+1):
        if i == N:# 最後の深さ
            if ne[i-1] > A[i] or ne[i-1] * 2 < A[i]:
                print(-1)
                exit()
            else:
                ans += A[i]
        else:
            tmp_ne = min(ne[i-1]*2 - A[i], accumA[i+1])
            if tmp_ne < 0:
                print(-1)
                exit()
            else:
                ne[i] = tmp_ne
                ans += tmp_ne + A[i]
    print(ans)
    # print(ne,accumA)


if __name__ == "__main__":
    main()


Measured memory_bytes: 22764
import java.util.Scanner

object Main {
  def main(args: Array[String]) {
    val result = solve(new Scanner(System.in))
    if (result.length > 0) println(result)
  }

  def solve(in: String): String = solve(new Scanner(in))

  def solve(sc: Scanner): String = {
    val ABCDE = Array.fill(5)(sc.nextInt)

    val t = ABCDE.map(i => (i + 9) / 10 * 10).sum
    val m = ABCDE.map(_ % 10).filter(_ > 0)
    if (m.isEmpty) {
      t.toString
    } else {
      (t - (10 - m.min)).toString
    }
  }
}


Measured memory_bytes: 25672
import java.util.Scanner;

class Main
{
	public static void main(String args[])
	{
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		for (int i = 0; i < n; i++)
		{
			double xa = sc.nextDouble();
			double ya = sc.nextDouble();
			double ra = sc.nextDouble();
			double xb = sc.nextDouble();
			double yb = sc.nextDouble();
			double rb = sc.nextDouble();
			
			double distance = Math.sqrt((xa - xb) * (xa - xb) + (ya - yb) * (ya - yb));
			if (ra + rb < distance)
				System.out.println(0);
			else if (ra + rb > distance && distance + Math.min(ra, rb) < Math.max(ra, rb))
				System.out.println((ra < rb) ? -2 : 2);
			else
				System.out.println(1);
		}
	}
}

Measured memory_bytes: 12000
#include<stdio.h>

int main(){
    int n,s=0;
    scanf("%d",&n);
    int b[n-1];
    for(int i=0;i<n-1;i++){
        scanf("%d",&b[i]);
        if(i==0){
            s+=b[0];
        }
        if(i>0){
            if(b[i-1]<=b[i]){
                s+=b[i-1];
            }
            else{
                s+=b[i];
            }
        }
    }
    s+=b[n-2];
    printf("%d\n",s);
    return 0;
}


Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <utility>
#include <cmath>
#include <random>
#include <vector>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <algorithm>
using namespace std;

#define rep(i,n) for(int i = 0; i<n; ++i)
#define REP(i,n) for(int i = 1; i<=n; ++i)
#define all(x) begin(x),end(x)
#define show(obj) {for(auto x:obj)cout<<x<<' ';cout<<endl;}
#define line "----------"
typedef long long ll;
typedef pair<int,int> ip;
typedef pair<ll,ll> lp;
const int inf = 1001001000;
const ll INF = 1LL<<60;
const ll MOD = 1e9 + 7;

int main(){
	int N; cin>>N;
	string s; cin>>s;
	map<char,ll> cnt;
	rep(i,N){
		cnt[s[i]]++;
	}
	ll ans = 1;
	for(auto x:cnt){
		ans *= x.second+1;
		ans %= MOD;
	}
	cout<<--ans<<endl;
	return 0;
}

Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0, i##_len = (int)(n); i < i##_len; i++)
using Node = pair<int, vector<int>>; // 値, 隣接リスト
using NodeList = vector<Node>;
int main() {
    int n, q;
    cin >> n >> q;
    auto nodes = vector<Node>(n, Node(0, vector<int>(0)));
    rep(i, n - 1) {
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        nodes[a].second.push_back(b);
        nodes[b].second.push_back(a);
    }
    rep(i, q) {
        int p, x;
        cin >> p >> x;
        p--;
        nodes[p].first += x;
    }
    auto values = vector<int>(n, -1);
    function<void(int, int, int)> sumup = [&values, &nodes, &sumup](int index, int parent, int sum) {
        auto &node = nodes[index];
        values[index] = sum + node.first;
        auto &children = node.second;
        for (auto child : children) {
            if (child == parent) continue;
            sumup(child, index, values[index]);
        }
    };
    sumup(0, -1, 0);
    rep(i, n) {
        cout << values[i];
        cout << ((i < n - 1) ? " " : "\n");
    }
}


Measured memory_bytes: 31360
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,l,r) for(long long i=(l);i<(r);++i)
#define REP(i,n) FOR(i,0,n)
#define REPS(i,n) FOR(i,1,n+1)
#define int long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
const int MOD=1e9+7;
const int INF=1e18;
 
signed main(){
    int N,K;cin>>N>>K;
    double ans=0;
    REPS(i,N){
        double D=1.0/N;
        int C=i;
        while(C<K){
            C*=2;
            D/=2;
        }
        ans+=D;
    }
  	cout<<setprecision(20.20);
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<cstdio>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int main(){
    int N;
    cin>>N;
    int lis[200];
    int cou=0;
    for(int i=0;i<N;i++)cin>>lis[i];
    //sort(lis,lis+N);
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            for(int k=j+1;k<N;k++){
                int lislis[3];
                lislis[0]=lis[i];
                lislis[1]=lis[j];
                lislis[2]=lis[k];
                sort(lislis,lislis+3);
                if(lislis[0]+lislis[1]>lislis[2]&&lislis[0]!=lislis[1]&&lislis[1]!=lislis[2]&&lislis[0]!=lislis[2]){
                    cou++;
                    //printf("%d %d %d\n",i+1,j+1,k+1);
                }

            }
        }
    }
    cout<<cou<<endl;
    return 0;
}


Measured memory_bytes: 3196
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
 
  
  int n;
  cin>>n;
  set<string> ss;
  string s;
  for(int i=0;i<n;i++)
  {
      cin>>s;
      ss.insert(s);
  }
  cout<<ss.size();


}

Measured memory_bytes: 19188
#include <bits/stdc++.h>
using namespace std;
#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 all(x)     (x).begin(), (x).end()
#define SZ(x)      ((int) (x).size())
using ll = long long;

int main() {
  int n;
  cin >> n;
  vector <int> c(4, 0);
  vector <string> judge{ "AC", "WA", "TLE", "RE" };
  REP(i, n) {
	string s;
	cin >> s;
	REP(j, 4) {
	  if (judge[j] == s) {
		  c[j]++;
		}
	}
  }
  REP(i, 4) {
	cout << judge[i] << " x " << c[i] << endl;
  }
  return 0;
}


Measured memory_bytes: 3612
N = int(input())
a=[]
p = 0
for i in range(N):
    q=[int(j) for j in input().split()]
    a.append([q[0]-1,q[1]])
    p = max(p, q[1])

table=[0]*(p+1)
for i in range(len(a)):
    table[a[i][0]]+=1
    table[a[i][1]]-=1

for i in range(1,p+1):
    table[i]+=table[i-1]

ans=0
for i, val in enumerate(table):
    if val >= i and i <= N:
        ans = max(i, ans)

print(ans)



Measured memory_bytes: 24528
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline ll read(){
	ll x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(ll a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
inline int rnd(int x){
	return rand()%x;
}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int N=100005;
ll dp[N],tong[N];
vector<ll> a;
int n,q;
int main(){
	n=read(); q=read();
	a.resize(1); a[0]=n;
	for(int i=1;i<=q;i++){
		ll jb=read();
		while(a.size()&&a[a.size()-1]>=jb)a.pop_back(); a.push_back(jb);
	}
	dp[a.size()-1]=1;
	//for(unsigned i=0;i<a.size();i++)cout<<a[i]<<" SZBAKKING"<<endl;
	for(int i=a.size()-1;i;i--){
		ll de=a[i];
		for(int pos=i-1;de&&pos>=0;pos=lower_bound(a.begin(),a.begin()+pos,de)-a.begin()-1){
			//cout<<pos<<" "<<dp[i]<<" "<<i<<endl;
			dp[pos]+=de/a[pos]*dp[i]; de%=a[pos];
		}
		dp[0]+=de/a[0]*dp[i]; tong[de%a[0]]+=dp[i];
	}
	tong[a[0]]+=dp[0];
	for(int i=n;i;i--)tong[i]+=tong[i+1];
	for(int i=1;i<=n;i++)writeln(tong[i]);
}

Measured memory_bytes: 4212
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func main() {
	N := nextInt()
	colors := make([]int, N)

	for i := 0; i < N; i++ {
		colors[i] = -1
	}

	for i := 0; i < N; i++ {
		a := nextInt()
		x := binarysearch(colors, a)

		colors[x] = a
	}

	c := 0
	for i := 0; i < N; i++ {
		if colors[i] == -1 {
			break
		}
		c++
	}

	fmt.Println(c)
}

func binarysearch(arr []int, value int) int {
	l := -1
	r := len(arr)

	for r-l > 1 {
		m := l + (r-l)/2

		if arr[m] < value {
			r = m
		} else {
			l = m
		}
	}

	return r
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)

	return i
}


Measured memory_bytes: 4096
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vb vector< bool >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sort(a) sort(a.begin(),a.end())
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define moddd (1000*1000*1000+9)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
//cout<<fixed<<setprecision(15)<<ans;
 
template <typename T>
void printvec(vector<T>& vec){
	for(int i=0;i<vec.size();i++){
		cout<<vec[i]<<" ";
	}
	cout<<endl;
}

int sum(int num){
	int ret=0;
	while(num!=0){
		ret=ret+(num%10);
		num/=10;
	}
	return ret;
}

int main(){
	std::ios::sync_with_stdio(false); 
	int ttt=1;
	//cin>>ttt;
	while(ttt--){
		int n,i;
		cin>>n;
		int ans=INT_MAX;
		for(i=1;i<n;i++){
			ans=min(ans,sum(i)+sum(n-i));
		}
		cout<<ans;
	}
	return 0;
} 
 


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define F first
#define S second
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int A[2];
  cin >> A[0] >> A[1];
  sort(A,A+2);
  if (A[0] == 1 && A[1] == 2) {
    cout << 3 << endl;
  } else if (A[0] == 1 && A[1] == 3) {
    cout << 2 << endl;
  } else {
    cout << 1 << endl;
  }
  return 0;
}

Measured memory_bytes: 3644
let rec pow a b ret =
  if b = 0 then ret
  else if b mod 2 = 0 then pow (a*a) (b/2) ret
  else pow (a*a) (b/2) (ret*a);;
Scanf.scanf "%d %d" (fun n k -> print_int (k * pow (k-1) (n-1) 1))


Measured memory_bytes: 384
#!python3

import itertools


INF = 10 ** 5

# input
H, W, K = list(map(int, input().split()))
S = [[int(e) for e in input()] for _ in range(H)]


def solve(w, l):
    n = len(l) + 1
    ans = 0
    if n == 1:
        dp = 0
        for j in range(W):
            x = w[-1][j]
            if x > K:
                return INF
            dp += x
            if dp > K:
                ans += 1
                dp = x
    else:
        dp = [0] * n
        for j in range(W):
            x = [0] * n
            b = False
            for i in range(n):
                if i == 0:
                    x[i] = w[l[i]][j]
                elif i == n - 1:
                    x[i] = w[-1][j] - w[l[-1]][j]
                else:
                    x[i] = w[l[i]][j] - w[l[i-1]][j]
                if x[i] > K:
                    return INF
                dp[i] += x[i]
                if dp[i] > K:
                    b = True
            if b:
                dp = x
                ans += 1
    return ans


def main():
    w = [S[0]]
    for i in range(1, H):
        w.append([w[i-1][j] + S[i][j] for j in range(W)])

    ans = INF
    num_list = [i for i in range(H - 1)]
    for i in range(H):
        comb_list = itertools.combinations(num_list, i)
        for l in comb_list:
            ans = min(ans, i + solve(w, l))

    print(ans)


if __name__ == "__main__":
    main()


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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef vector<ll> vll;

ll dp(int mw, int n, int w[], int v[]){
	long memo[n+1][mw+1];
	int i , j;
//	memset(memo, 0, sizeof memo);
	for(i = 0; i <= n; i++){
		for(j = 0; j <= mw; j++){
			if(i ==0 || j ==0)
				memo[i][j] = 0;
			else if(w[i-1] <= j)
				memo[i][j] = max(v[i-1] + memo[i-1][j-w[i-1]], memo[i-1][j]);
			else
				memo[i][j] = memo[i-1][j];
//			cout << memo[i][j] << ' ';
		}
//		cout << endl;
	}
//	cout << i << ' ' << j << endl;
	return memo[n][mw];
}

int main() {
	int n, mw;
	cin >> n >> mw;
	int w[n],v[n];
	for(int i = 0; i < n; i++){
		cin >> w[i] >> v[i];
	}
	cout << dp(mw,n,w,v);
	return 0;
}


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

#define ll             long long
#define LL             long long
#define pii            pair<int, int>
#define pll            pair<ll, ll>
#define pil            pair<int, ll>
#define pli            pair<ll, int>
#define vi             vector<int>
#define vl             vector<ll>
#define vii            vector<pii>
#define vll            vector<pll>
#define vil            vector<pil>
#define vli            vector<pli>
#define pb             push_back
#define ppb            pop_back
#define mp             make_pair
#define ff             first
#define ss             second
#define TN             typename
#define all(v)         v.begin(), v.end()
#define fill(a, b)     memset(a, b, sizeof a)
#define endl           '\n'

template <TN T> T gcd(T a, T b) {return !b ? a : gcd(b, a % b);}
template <TN T> T lcm(T a, T b) {return a * (b / gcd(a, b));}
template <TN T> T sqr(T a) {return a * a;}
template <TN T> T cube(T a) {return a * a * a;}
template <TN T> inline void smin(T &a, T b) {a = a < b ? a : b;}
template <TN T> inline void smax(T &a, T b) {a = a > b ? a : b;}

int in() {int n; scanf("%d", &n); return n;}
ll Lin() {ll n; scanf("%lld", &n); return n;}
double Din() {double n; scanf("%lf", &n); return n;}

const ll inf = (ll)1e17;
const ll mod = (ll)1e9 + 7;
const int N = 3e3 + 5;

double dp[N];

int solve() {
	int n = in();
	dp[0] = 1;
	for (int coin = 1; coin <= n; coin++) {
		double p = Din();
		for (int i = n + 1; i >= 0; i--) {
			dp[i] = (i == 0 ? 0 : dp[i - 1] * p) + dp[i] * (1 - p);
		}
	}
	double ans = 0;
	for (int i = 0; i <= n; i++) {
		if(i > n - i) ans += dp[i];
	}
	printf("%.10f\n", ans);
	return 0;
}

int main() {
	int test = 1, tc = 0;
	//scanf("%d", &test);
	while (test--) {
		//printf("Case %d: ", ++tc);
		solve();
	}
	return 0;
}



Measured memory_bytes: 256