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

#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 reps(i, n) for (int i = 1; i <= int(n); i++)
#define rreps(i, n) for (int i = int(n); i >= 1; i--)
#define repc(i, n) for (int i = 0; i <= int(n); i++)
#define rrepc(i, n) for (int i = int(n); i >= 0; i--)
#define repi(i, a, b) for (int i = int(a); i < int(b); i++)
#define repic(i, a, b) for (int i = int(a); i <= int(b); i++)
#define all(a) (a).begin(), (a).end()
#define bit32(x) (1 << (x))
#define bit64(x) (1ll << (x))
#define sz(v) ((int) v.size())

using namespace std;

using i64 = long long;
using u64 = unsigned long long;
using f80 = long double;
using vi32 = vector<int>;
using vi64 = vector<i64>;
using vf80 = vector<f80>;
using vstr = vector<string>;

void yes() { cout << "Yes" << endl; exit(0); }
void no() { cout << "No" << endl; exit(0); }
template <typename T> class pqasc : public priority_queue<T, vector<T>, greater<T>> {};
template <typename T> class pqdesc : public priority_queue<T, vector<T>, less<T>> {};
template <typename T> void amax(T &x, T y) { x = max(x, y); }
template <typename T> void amin(T &x, T y) { x = min(x, y); }
template <typename T> T exp(T x, i64 n, T e = 1) { T r = e; while (n > 0) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
template <typename T> istream& operator>>(istream &is, vector<T> &v) { for (auto &x : v) is >> x; return is; }
template <typename T> ostream& operator<<(ostream &os, vector<T> &v) { rep(i, v.size()) { if (i) os << ' '; os << v[i]; } return os; }
void solve(); int main() { ios::sync_with_stdio(0); cin.tie(0); cout << fixed << setprecision(16); solve(); return 0; }

const int INF = 1001001001;
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};

u64 gcd(u64 a, u64 b) {
  if (min(a, b) == 0) {
    return max(a, b);
  }
  if (a % b == 0) {
    return b;
  } else {
    return gcd(b, a % b);
  }
}

u64 lcm(u64 a, u64 b) {
  if (min(a, b) == 0) {
    return max(a, b);
  }
  return a / gcd(a, b) * b;
}

void solve() {
  int n;
  u64 m;
  cin >> n >> m;
  vector<u64> a(n);
  vector<f80> p(n);
  cin >> a >> p;
  rep(i, n) p[i] /= 100;
  vector<f80> c(1 << n);
  auto check = [](u64 a, u64 b, u64 m) {
    u64 g = gcd(a, b);
    a /= g;
    int c = 0;
    while (a >= 10) c++, a /= 10;
    while (b >= 10) c++, b /= 10;
    if (c >= 19) return false;
    return a * b <= m;
  };
  reps(i, (1 << n) - 1) {
    u64 acc = 0;
    f80 percent = 1;
    bool ok = true;
    rep(j, n) if (i >> j & 1) {
      if (!check(acc, a[j], m)) {
        ok = false;
        break;
      }
      acc = lcm(acc, a[j]);
      percent *= p[j];
    }
    if (ok) {
      c[i] = (m / acc) * percent;
    }
  }
  rep(i, n) rep(s, 1 << n) if (s >> i & 1) {
    c[s] -= c[s ^ (1 << i)];
  }
  cout << abs(c[(1 << n) - 1]) << endl;
}



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

int main(){
  int N,D,X;  cin >> N >> D >> X;
  int a;
  int ate = 0;
  for(int i = 0;i < N;i++){
    cin >> a;
    for(int i = 0;;i++){
      if((i*a+1) <= D)ate++;
      else break;
    }
  }

  cout << X + ate << endl;
}


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

using namespace std;

#define N 120000

int n,a[N],q[N],m,b[10];
map<int,int> vis,mp;

void solve(int x,int y){
	mp.clear();
	b[0]=x; b[1]=y; b[2]=x^y;
	for (int i=0;i<n;++i){
		++mp[b[i%3]];
	}
	if (b[0]^b[1]^b[(n-1)%3]) return;
	if (b[(n-2)%3]^b[(n-1)%3]^b[0]) return;
	if (mp[b[0]]==vis[b[0]]&&mp[b[1]]==vis[b[1]]&&mp[b[2]]==vis[b[2]]){
		puts("Yes");
		exit(0);
	}
}

int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;++i){
		scanf("%d",a+i);
		if (!vis[a[i]]) q[++m]=a[i];
		++vis[a[i]];
	}
	if (m>3){puts("No"); return 0;}
	for (int i=1;i<=m;++i)
		for (int j=1;j<=m;++j) solve(q[i],q[j]);
	puts("No");
	
	return 0;
}
			

Measured memory_bytes: 4480
// By Shreehari Bodas

#include <bits/stdc++.h>

using namespace std;

const int MOD=1e9+7;

int search(int b[], int m, int s){
	int start=0,end=m-1;
	bool flag=false;
	while(start<=end){
		int mid=(start+end)/2;
		if(b[mid]==s){
			flag=true;
			return mid;
		}
		else if(b[mid]>s) end=mid-1;
		else if(b[mid]<s) start=mid+1;
	}
	if(flag==false) return m;
}

long long int pow(long long int a, long long int b){
	if(b==0) return 1;
	long long int res=pow(a,b/2);
	if(b%2 ==1) return res*res*a;
	else if(b%2 ==0) return res*res;
}

int main(){

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

	if(a>=k) cout<<k;
	else if(a+b>=k) cout<<a;
	else cout<<2*a+b-k;

	return 0;
} 

Measured memory_bytes: 3592
#pragma comment(linker, "/STACK:500000000")
#define _CRT_SECURE_NO_WARNINGS
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <exception>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <math.h>
#include <set>
#include <stack>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <time.h>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const double PI = acos(-1.0);
const double EPS = 1e-9;
const int INF = static_cast<int>(2e9);


int main() {
	//freopen("1.in", "rt", stdin);
	//freopen("out.txt", "wt", stdout);
	int n;
	scanf("%d", &n);
	vector<int> a;
	while (n--) {
		int v;
		scanf("%d", &v);
		if (a.empty() || a.back() != v) {
			a.push_back(v);
		}
	}
	int res = 1;
	for (int i = 1; i < (int)a.size() - 1; ++i) {
		if ((a[i - 1] < a[i] && a[i] > a[i + 1]) ||
			(a[i - 1] > a[i] && a[i] < a[i + 1])) {
			++res;
			++i;
		}
	}
	printf("%d\n", res);
	return 0;
}

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

#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif

//{{{
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
// clang-format off
#define debug(args...) {vector<string> _v = split(#args, ','); err(_v.begin(), args); cerr<<endl;}
vector<string> split(const string& s, char c) {vector<string> v; stringstream ss(s); string x; while
(getline(ss, x, c)) v.push_back(x); return v;} void err(vector<string>::iterator) {}
template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args)
{cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; err(++it, args...);}
// clang-format on
//}}}

const int N = 1e5 + 10;
int T;

LL dp[N];
int n, W;

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
// freopen("out", "w", stdout);
#endif

    while (cin >> n >> W)
    {
        clr(dp, -1);
        dp[0] = 0;

        int w, v;

        for (int i = 1; i <= n; i++)
        {
            cin >> w >> v;
            for (int j = W; j >= w; j--)
            {
                dp[j] = max(dp[j], dp[j - w] + v);
            }
        }

        LL ans = 0;
        for (int i = 0; i <= W; i++)
        {
            ans = max(ans, dp[i]);
        }
        cout << ans << endl;
    }

    return 0;
}


Measured memory_bytes: 4412
#include "stdio.h"

int main()
{
	//変数を立てて初期化
	//それぞれ、見た回数、比の高橋側と青木側、票数の高橋側と青木側
	int N = 0;
	int T[1010], A[1010];
	long long int voteT = 0, voteA = 0;
	for (int i = 0; i < 1010; i++) {
		T[i] = 0;
		A[i] = 0;
	}

	//見た回数と比を入力
	scanf("%d",&N);
	for (int i = 0; i < N; i++) {
		scanf("%d %d", &T[i], &A[i]);
	}

	//投票数の初期値は１回目に見たときの票数
	voteT = T[0];
	voteA = A[0];

	//ループ回数確認用の変数
	long long int count = 0;

	//１回目に見たときの投票数を初期値としてるのでi=1でi=Nまでループ
	for (int i = 1; i < N; i++) {
		//カウンタを初期化する
		count = 0;

		//小細工そのいち
		//比が前と一致するなら投票数が変化していないのでwhileをスキップする
		if ((T[i] == T[i - 1]) && (A[i] == A[i - 1]))
			count = -1;

		//小細工そのに
		//１：１なら大きいほうに合わせる
		if ((T[i] == 1) && (A[i] == 1)) {
			if (voteT >= voteA)
				voteA = voteT;
			else
				voteT = voteA;

			count = -1;
		}

		//ループに入るのであれば事前にカウンタを動かしておきたいコーナー
		if (count != -1) {
			//比の示す一番近い値に投票数から近づいて、見つけたらカウントをそこにジャンプさせる
			//まあ比が投票数より大きかったら意味ないんだけども

			if (voteT >= T[i]) {
				for (int j = 0; j < T[i]; j++) {
					if ((voteT - j) % T[i] == 0) {
						count = voteT / T[i];
						break;
					}
				}
			}

			//Aでも同じことをやる
			if (voteA >= A[i]) {
				for (int j = 0; j < A[i]; j++) {
					if ((voteA - j) % A[i] == 0) {
						//もしAのほうがカウンタ大きくなるんだったらこっちに合わせるよ
						//合わせなくていいんだったらそのまんま
						if (count < voteA / A[i])
							count = voteA / A[i];
						else
							break;
					}
				}
			}
		}
		

		//スキップできるように、count==-1ならループに入らないようにしてある
		while (count!=-1) {


			//比をカウンタ倍した値がすでに決まってる投票数以上なら、
			//投票数を更新し、ループを抜ける
			//（比を満たす、今より大きな数を出していけば答えは出るだろ）
			if ((T[i] * count >= voteT) && (A[i] * count >= voteA)) {
				voteT = T[i] * count;
				voteA = A[i] * count;
				break;
			}

			//ループ回数カウンタ
			count++;
		}
	}

	//結果を表示する
	printf("%lld",voteT+voteA);

    return 0;
}

Measured memory_bytes: 256
(let ((n (read-line))
    (ans "No"))
    (if (eq (char n 1) (char n 2))
        (if (eq (char n 0) (char n 1))
            (setq ans "Yes")
            (if (eq (char n 1) (char n 3))
                (setq ans "Yes")
            )
        )
        
    )
    (format t "~A~%" ans)
)

Measured memory_bytes: 23760
#include <string>
#include <stack>
#include <iostream>
using namespace std;
int main()
{
    string word;
    stack<int> S;
    int a,b,c,sum;
    while(cin >> word)
    {
        if(word == "+")
        {
            a = S.top();
            S.pop();
            b = S.top();
            S.pop();
            c = a+b;
            S.push(c);
        }
        else    if(word == "-")
                {
                    b = S.top();
                    S.pop();                  
                    a = S.top();
                    S.pop();
                    c = a-b;
                    S.push(c);
                }
                else    if(word == "*")
                        {
                            a = S.top();
                            S.pop();
                            b = S.top();
                            S.pop();
                            c = a*b;
                            S.push(c);
                        }
                        else    S.push(stoi(word));
    }
    sum = S.top();
    cout << sum << endl;
}


Measured memory_bytes: 3200
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, K):
    ans = 0
    for i in range(1, N+1):
        if i < K:
            n = math.ceil(math.log2(K / i))
        else:
            n = 0
        ans += (1./N) * (1./(2**n))
    return ans


def main():
    N, K = read_int_n()
    print(slv(N, K))


if __name__ == '__main__':
    main()


Measured memory_bytes: 6888
#include <bits/stdc++.h>
#define INF 1e9
#define all(v) v.begin(), v.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define max(v) *max_element(v.begin(), v.end())
#define min(v) *min_element(v.begin(), v.end())
using namespace std;

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

    while(true){
        int h, w;
        cin>>h>>w;
        if(h == 0 && w == 0){
            break;
        }
        rep(i, h){
            rep(j, w){
                if(i == 0 || i == h-1 || j == 0 || j == w-1){
                    cout<<"#";
                }
                else{
                    cout<<".";
                }
                if(j == w-1){
                    cout<<endl;
                }
            }
        }
        cout<<endl;
    }
    return 0;
}


Measured memory_bytes: 3100
/*
        Author: Prokash
                CSE48, JU

*/

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

typedef long long ll;
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
int main()
{
    FAST;
    ll n,g,t,in;
    vector<ll>v;
    cin>>t;
    while(t--)
    {
        cin>>in;
        v.push_back(in);
    }
    g=v[0];
    for(int i=1;i<v.size();i++)
    {
        g=((v[i])/(__gcd(v[i],g)))*g;
    }
    cout<<g<<endl;
    return 0;
}

Measured memory_bytes: 384
#include <iostream>

using namespace std;

int Bit(int num, int pos)
{
    return (num & (1 << pos)) ? 1 : 0;
}

bool Good(const string &str, int mask)
{
    int sum = str[0] - '0';
    for (int i = 0; i < 3; i += 1) {
        sum += (str[i + 1] - '0') * (Bit(mask, i) == 1 ? 1 : -1);
    }
    return sum == 7;
}

void Print(const string &str, int mask)
{
    for (int i = 0; i < 3; i += 1) {
        cout << str[i] << (Bit(mask, i) == 1 ? '+' : '-');
    }
    cout << str.back() << "=7\n";
}

int main()
{
    string str;
    getline(cin, str);

    for (auto i = 0; i < (1 << 3); i += 1) {
        if (Good(str, i)) {
            Print(str, i);
            return 0;
        }
    }

    return 0;
}


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

int N, Q;
int A[110000];
int B[110000];
int C[110000];

int main(void){

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

    int inst[110000] = {0};

    long long total = 0;

    for (int i = 0;i < N;i++) total += A[i];
    for (int i = 0;i < N;i++) inst[A[i]]++;
//    cout << total << endl;
//    for (int i = 1;i <= N;i++) cout << inst[i] <<",";
//    cout << endl;

    for (int i = 0;i < Q;i++){
//        cout << C[i] << "," << B[i] << endl;
        total = total + (C[i] - B[i]) * inst[B[i]];
        cout << total << endl;
        inst[C[i]] = inst[C[i]] + inst[B[i]];
        inst[B[i]] = 0;
    }

    return 0;
}

Measured memory_bytes: 5192
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

def main():
    a = ii()
    print(a+(a**2)+(a**3))




if __name__ == "__main__":
    main()

Measured memory_bytes: 61672
#include <stdio.h>


int main(int argc, const char * argv[])
{
    int i;
    int j;
    for(i = 1; i < 10; i++){
        for(j = 1; j < 10; j++){
            printf("%dx%d=%d\n",i,j,i*j);
        }
    }
    return 0;
}

Measured memory_bytes: 524
#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstring>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <vector>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define show(x) cout << #x << " = " << x << endl;
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
ll ok[55][55];
ll d[55][55];
/*int main(){
    rep(i,51){
        rep(j,51){
            for(int k = 1;k <= 50;k++){
                if(i%k == j){
                    ok[i][j] = 1LL<<k;
                    break;
                }
            }
            if(ok[i][j]==0){
                ok[i][j] = 1LL<<60;
            }
            d[i][j] = ok[i][j];
        }
    }
    rep(k,51){
        rep(i,51){
            rep(j,51){
                d[i][j] = min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    rep(i,51){
        rep(j,51){
            if(d[i][j] < ok[i][j]){
                cout << i << " " << j << endl;
                show(ok[i][j]);
                show(d[i][j]);
            }
        }
    }
    
}*/
int main(){
    string s;
    cin >> s;
    bool cnt[26]={};
    int n = (int)s.size();
    rep(i,n){
        cnt[s[i]-'a'] = true;
    }
    if(s.size()<26){
        cout << s;
        rep(i,26){
            if(!cnt[i]){
                cout << (char)('a'+i)<< endl;
                return 0;
            }
        }
    }else{
        bool used[26] = {};
        rep(i,26){
            used[s[n-1-i]-'a'] = true;
            if(i==0)continue;
            for(char j = s[n-1-i]+1 ; j <='z'; j++){
                if(used[j-'a']){
                    rep(hoge,n-1-i){
                        cout << s[hoge];
                    }
                    cout << j << endl;
                    return 0;
                }
            }
        }
    }
    cout << -1 << endl;
}

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

int main()
{
    int n;
    cin>>n;
    int d;
    d=n%10;
    if(d==3){cout<<"bon"<<endl;}
    else if(d==2||d==4||d==5||d==7||d==9){cout<<"hon"<<endl;}

    else {cout<<"pon"<<endl;}
    return 0;
}

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

int main() {
  int n, m, ans;
  cin >> n >> m;
  ans = n;
  rep(i, m) {
    int tmp;
    cin >> tmp;
    ans -= tmp;
  }
  if (ans < 0) {
    cout << -1 << endl;
  } else {
    cout << ans << endl;
  }
}

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

int main(){
char s[4]; int ans=0;
scanf("%s",s);
    if(s[0]==s[1]){
        if((s[2]==s[3]) && (s[0]!=s[2])){
            ans++;
        }
    }else if((s[0]==s[2]) && (s[1]==s[3]) && (s[0] != s[1])){
        ans++;
    }else if((s[0]==s[3]) && (s[1]==s[2]) && (s[0] != s[1])){
        ans++;
    }
    if(!ans){
        cout << "No" << endl;
        }else{
            cout << "Yes" << endl;
        }

return 0;
}

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

int main() {

    int N;
    cin >> N;
    int d[N];
    rep(i, N) cin >> d[i];

    set<int> values;
    rep(i, N) values.insert(d[i]);

    cout << values.size() << endl;


    return 0;
}

Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

int main(){
	IOS;
	string s;
	cin >> s;
	int ans = 0;
	string prv = "";
	string cur = "";
	for(int i = 0; i < s.size(); i++){
		cur += s[i];
		if(cur != prv){
			prv = cur;
			cur = "";
			ans++;
		}
	}		
	cout << ans;
	return 0;
}


Measured memory_bytes: 720
package main

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

func main() {
	sc.Split(bufio.ScanWords)
	s, t := next(), next()

	ok := true
	for i := 0; i < len(s); i++ {
		ok = true
		for j := range t {
			if s[(i+j)%len(s)] != t[j] {
				ok = false
				break
			}
		}
		if ok {
			break
		}
	}

	if ok {
		puts("Yes")
	} else {
		puts("No")
	}
	wt.Flush()
}

var (
	sc  = bufio.NewScanner(os.Stdin)
	rdr = bufio.NewReaderSize(os.Stdin, 1000000)
	wt  = bufio.NewWriter(os.Stdout)
)

func next() string {
	sc.Scan()
	return sc.Text()
}

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

func nextFloat64() float64 {
	f, _ := strconv.ParseFloat(next(), 64)
	return f
}

func nextInts(n int) []int {
	slice := make([]int, n)
	for i := 0; i < n; i++ {
		slice[i] = nextInt()
	}
	return slice
}

func nextFloat64s(n int) []float64 {
	slice := make([]float64, n)
	for i := 0; i < n; i++ {
		slice[i] = nextFloat64()
	}
	return slice
}

func nextMega() string {
	buf := make([]byte, 0, 1000000)
	for {
		l, p, _ := rdr.ReadLine()
		buf = append(buf, l...)
		if !p {
			break
		}
	}
	return string(buf)
}

func putf(format string, a ...interface{}) {
	fmt.Fprintf(wt, format, a...)
}

func puts(a ...interface{}) {
	fmt.Fprintln(wt, a...)
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
#define ll long long int
#define inf 1e18
#define mod 1000000007
#define setbits(x) __builtin_popcount(x)
using namespace std;

//-------------------------------------------------------
vector<ll>prefix;
vector<vector<ll>>dp;

ll func(ll i, ll j) {
	if (i >= j) {
		return 0;
	}
	if (dp[i][j] != -1) {
		return dp[i][j];
	}

	ll ans = inf;
	ll sum = prefix[j] - ((i == 0) ? 0 : prefix[i - 1]);
	for (ll cut = i; cut < j; cut++) {
		ll left = func(i, cut);
		ll right = func(cut + 1, j);
		ans = min(ans, sum + left + right);
	}
	return dp[i][j] = ans;
}

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

	prefix.resize(n);
	prefix[0] = a[0];
	for (ll i = 1; i < n; i++) {
		prefix[i] = prefix[i - 1] + a[i];
	}

	dp.resize(n + 1, vector<ll>(n + 1, -1));
	cout << endl << func(0, n - 1);
	return 0;
}

Measured memory_bytes: 4932
#ifdef DEBUG
#define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>

using namespace std;

#define mp make_pair
#define pb push_back
#define sz(s) ((int) ((s).size()))

#ifdef DEBUG
#define eprintf(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#else
#define eprintf(...) ;
#endif

typedef long long ll;
typedef long double ld;

const int inf = (int) 1.01e9;
const ld eps = 1e-11;
const ld pi = acos(-1.0L);

mt19937 mrand(random_device{} ());
int rnd(int x) {
  return mrand() % x;
}

const int mod = (int) 1e9 + 7;

void add(int & x, int y) {
  if ((x += y) >= mod) {
    x -= mod;
  }
}

int sum(int x, int y) {
  add(x, y);
  return x;
}

int mult(int x, int y) {
  return (ll) x * y % mod;
}

int power(int x, ll p) {
  int res = 1;
  while (p) {
    if (p & 1) {
      res = mult(res, x);
    }
    x = mult(x, x);
    p >>= 1;
  }
  return res;
}

int inv(int x) {
  return power(x, mod - 2);
}

void precalc() {
}

const int maxn = 550;

int n;
char s[maxn][maxn];

bool read() {
  if (scanf("%d", &n) < 1) {
    return false;
  }
  for (int i = 0; i < n; i++) {
    scanf("%s", s[i]);
  }
  return true;
}

int empty[maxn];

void solve() {
  bool was = false;
  int mx = 0;
  for (int i = 0; i < n; i++) {
    empty[i] = 1;
    int waspoint = false;
    for (int j = 0; j < n; j++) {
      if (s[j][i] == '#') {
        empty[i] = 0;
        was = true;
      } else {
        waspoint = true;
      }
    }
    if (waspoint) {
      mx++;
    }
  }
  if (!was) {
    printf("-1\n");
    return;
  }
  int mn = inf;
  for (int i = 0; i < n; i++) {
    int cnt = 0;
    for (int j = 0; j < n; j++) {
      if (s[i][j] == '.') {
        cnt++;
      }
    }
    int cur = cnt;
    if (empty[i]) {
      cur++;
      if (s[i][i] == '#') {
        cur++;
      }
    }
    mn = min(mn, cur);
  }
  printf("%d\n", mn + mx);
}

int main() {
  precalc();
#ifdef DEBUG
  assert(freopen("text.in", "r", stdin));
  assert(freopen("text.out", "w", stdout));
#endif

  while (read()) {
    solve();
#ifdef DEBUG
    eprintf("Time: %.3f\n", (double) clock() / CLOCKS_PER_SEC);
#endif
  }
  return 0;
}



Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
#define uint unsigned int
#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, a, b) for (int i = (a); i < (b); ++i)
#define FORR(i, a, b) for (int i = (a); i >= (b); --i)
#define ALL(a) (a).begin(), (a).end()
#define ALLR(a) (a).rbegin(), (a).rend()
#define SZ(a) ((int)(a).size())
#define PB(a) push_back(a)
#define EMP emplace
#define EMPB(...) emplace_back(__VA_ARGS__)
#define MP(a, b) make_pair(a, b)
#define MT(...) make_tuple(__VA_ARGS__)
#define Bit(n) (1LL << (n))
using namespace std;
using pii = pair<int, int>;
template <class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
template <class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
const int MOD = 1000000007;
const int INF = 1LL << 30;
const double EPS = 1e-10;

int H, W;
string s[510], x[510], y[510];

signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> H >> W;
  REP(i, H) {
    cin >> s[i];
    x[i] = y[i] = string(W, '.');
  }
  REP(i, W) {
    x[0][i] = '#';
    y[H-1][i] = '#';
  }
  FOR(i, 1, H-1) {
    REP(j, W) {
      if (j & 1) y[i][j] = '#';
      else x[i][j] = '#';
    }
  }
  REP(i, H) REP(j, W) if (s[i][j] == '#') {
    if (j & 1) x[i][j] = '#';
    else y[i][j] = '#';
  }
  REP(i, H) cout << x[i] << endl;
  cout << endl;
  REP(i, H) cout << y[i] << endl;

  return 0;
}

Measured memory_bytes: 1536
import math

n = int(input())
a = list(map(int,input().split()))

flag_zero = 0
sum = 0
for i in range(n):
  if a[i]==0:
    flag_zero = 1
  else:
    sum += math.log10(a[i])

if flag_zero == 1:
  print(0)
elif sum > 18:
  print(-1)
else:
  sum = 1
  for i in range(n):
    sum *= a[i]
  if sum > 10**18:
    print(-1)
  else:
    print(sum)


Measured memory_bytes: 22532
#include<bits/stdc++.h>
#define ll long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
static const ll MAX = 1000000000000000;
static const int NIL = -1;
using namespace std;
const long double EPS = 0.0000000001;
const long double PI = (acos(-1));

#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

vector<pair<long long, long long> > prime_factorize(long long N) {
    vector<pair<long long, long long> > res;
    for (long long a = 2; a * a <= N; ++a) {
        if (N % a != 0) continue;
        long long ex = 0; // exponential

        // divide as much as you can
        while (N % a == 0) {
            ++ex;
            N /= a;
        }

        // push the result
        res.push_back({a, ex});
    }

    // last num (if the lasting n is prime number and not 1)
    if (N != 1) res.push_back({N, 1});
    return res;
}

int main() {
    ll n,p; cin >> n >> p;
    ll ans = 1;
    vector<pair<long long, long long>> f = prime_factorize(p);

    rep(i,f.size()){
        if(f[i].second >= n) ans *= pow(f[i].first,f[i].second/n);
    }
    cout << ans;
    return 0;
}


Measured memory_bytes: 3812
#include<bits/stdc++.h>
using namespace std;
const int N=3e5;
int a[N],b[N];
int main(){
	int n;scanf("%d",&n);
	for(int i=0;i<n;i++)scanf("%d%d",a+i,b+i);
	sort(a,a+n),sort(b,b+n);
	printf("%d",(b[n/2]+b[(n-1)/2]-a[n/2]-a[(n-1)/2])/(n%2?2:1)+1);
	return 0;
}

Measured memory_bytes: 5400
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <complex>
#include <ctime>
#include <cstdlib>

using namespace std;

inline int to_int(string s) {int v; istringstream sin(s); sin >> v; return v;}
template<class T> inline string to_str(T x) {ostringstream sout; sout << x; return sout.str();}

typedef long long ll;

int main()
{
	int n;
	while(cin >> n, n)
	{
		vector<unsigned int> S;
		unsigned int mx = 0, a;
		unsigned int sum = 0;
		for(int i = 0; i < n; i++)
		{
			cin >> a; sum += a;
		}
		S.push_back(0);
		for(int i = 0; i < n-1; i++)
		{
			cin >> a;
			S.push_back(a);
		}
		sort(S.begin()+1, S.end(), greater<int>());
		 
		for(int i = 0; i < n; i++)
		{
			sum += S[i];
			mx = max(mx, sum * (n - i));
		}

		cout << mx << endl;
	}
}

Measured memory_bytes: 1600
#include<cstdio>
#include<iostream>
#include<cstring>
#define RG register
using namespace std;
int n,d,T;
template<typename I> inline void read(I &ot){
	I ch=getchar(), x=0, f=1;
	while(ch<'0' || ch>'9'){if(ch=='-') f=-1; ch=getchar();	}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0'; ch=getchar();	}
	ot=x*f;}
template<typename I, typename... U> inline void read(I &x,U&... y){read(x); read(y...);}
int main()
{
	//freopen("Cookie Breeding Machine.in","r",stdin);
	read(T);
	while(T--)
	{
		read(n,d);
		if((n-1)%2==0) printf("%d\n",127*(n-1)+d);
		else printf("%d\n",127*(n-1)+(127^d));
	}
	return 0;
}

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

int main() {
  int r, d, x;
  cin >> r >> d >> x;
  ll now = x;
  for (int i = 1; i <= 10; i++) {
    now *= r;
    now -= d;
    cout << now << endl;
  }
}


Measured memory_bytes: 3508
"use strict";
function I(t,i){this._s=t.split("\n"),this._c=0,this._l=0,this._f=i||Number}I.prototype.a=function(t){var i=this._s[this._l];if(i){var s=i.trim().split(" "),h=s[this._c];return this._c++,s.length===this._c&&(this._c=0,this._l++),t?t(h):this._f(h)}},I.prototype.l=function(t){var i=this._s[this._l];if(i)return this._c=0,this._l++,i.split(" ").map(t||this._f)},module.exports=I;

function main(input) {
  var o = new I(input);

  var h = o.a();
  var w = o.a();

  var a = [];
  for (var i = 0; i < h; i++) {
    a.push(o.a(String).split(""));
  }

  var stack = [];
  for (var i = 0; i < h; i++) {
    for (var j = 0; j < w; j++) {
      if (a[i][j] === "#") {
        stack.push({i, j});
      } 
    }
  }

  var count = 0;
  // console.log({a, stack})
  while (stack.length > 0) {
    count += 1;
    var newStack = [];
    var len = stack.length;
    for (var k = 0; k < len; k++) {
      var grid = stack.pop();
      var i = grid.i;
      var j = grid.j;
      // console.log({i, j})
      if (i - 1 >= 0 && i - 1 < h && a[i - 1][j] === ".") {
        a[i - 1][j] = "#";
        newStack.push({i: i - 1, j: j});
      }
      if (i + 1 >= 0 && i + 1 < h && a[i + 1][j] === ".") {
        a[i + 1][j] = "#";
        newStack.push({i: i + 1, j: j});
      }
      if (j - 1 >= 0 && j - 1 < w && a[i][j - 1] === ".") {
        a[i][j - 1] = "#";
        newStack.push({i: i, j: j - 1});
      }
      if (j + 1 >= 0 && j + 1 < w && a[i][j + 1] === ".") {
        a[i][j + 1] = "#";
        newStack.push({i: i, j: j + 1});
      }
    }

    stack = newStack;
  }

  console.log(count - 1);  
}


main(require("fs").readFileSync("/dev/stdin", "utf8"));


Measured memory_bytes: 105616
//
// Created by Kiran Chavhan on 15/08/2020.
//

#include<bits/stdc++.h>

#define int long long
#define MOD 1000000007
#define sort(a) sort(a.begin(),a.end())
#define endl '\n'

using namespace std;

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    string s;
    cin>>s;
    int cnt=0,x=0;
    for(int i=0;i<s.length();i++){
        
        if(s[i]=='R'){
            cnt++;
            x=max(x,cnt);
        }
        else if(s[i]=='S'){
            cnt=0;
            x=max(x,cnt);
        }
        
    }
    cout<<x;

}

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

int main(void) {
    char s[4];

    cin >> s;

    if(s[0] != s [1] && s [1] != s [2] && s [2] != s [0])
        cout << "Yes" << endl;
    else
        cout << "No" << endl;

    return 0;
}

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

using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;

#define REPS(i, a, n) for (int i = (a); i < (n); ++i)
#define REP(i, n) REPS(i, 0, n)
#define RREP(i, n) REPS(i, 1, n + 1)
#define DEPS(i, a, n) for (int i = (a); i >= n; --i)
#define DEP(i, n) DEPS(i, n, 0)

#define vint(v, n) vector<int> v(n); REP(i,n) cin >> v[i];
#define vvint(v, w, n) vector<int> v(n); vector<int> w(n); REP(i,n) cin >> v[i] >> w[i];
#define vlint(v, n) vector<ll int> v(n); REP(i,n) cin >> v[i];
#define vdouble(v, n) vector<double> v(n); REP(i,n) cin >> v[i];
#define vvdoube(v, n1, n2) vector<vector<double> > v(n1, vector<double>(n2, 0)); REP(i,n1) REP(j,n1) cin >> v[i][j];
#define string(x) string x; cin >> x;
#define vstring(v, n) vector<string> v(n); REP(i,n){string a; std::cin >> a; v.push_back(a); }

#define all(v) (v).begin(), (v).end()
#define rall(v) (v).begin(), (v).end(), std::greater<int>()
#define len(v) (v).length()

static const string abet("abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");
static const long long int MOD = 1000000007;
static const double PI=3.1415926535897932;
static const int INF = 0x3f3f3f3f;
static const int INFTY = (1 << 29);
static const long long LINFTY = (1LL << 32);

static const int dy4[]={0, 0, 1, -1};
static const int dx4[]={1, -1, 0, 0};
static const int dx8[] = {1, 1, 1, 0, 0, -1, -1, -1};
static const int dy8[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int coin_optimize(int N, vector<int> c) {

  vector<int> dp(N+1, INF); dp[0]=0;

  REP(i, c.size()) REPS(j, c[i], N+1) dp[j] = min(dp[j], dp[j-c[i]]+1);

  return dp[N];
}


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

  int N, M;
  cin >> N >> M;
  vint(c, M);

  cout << coin_optimize(N, c) << endl;

}

Measured memory_bytes: 3224
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define INF 1073741824
#define ll long long
#define PI (2*acos(0.0))
using namespace std;
char gap = 32;
template<typename T> 
ostream& operator<<(ostream &os, const vector<T> &v) { 
    os << '{'; 
    for (const auto &x : v) os << gap << x;
        return os << '}'; 
}
template<typename A, typename B> 
ostream& operator<<(ostream &os, const pair<A, B> &p) {
        return os << '(' << p.first << gap << p.second << ')';
}
void dbg_out() { cerr << endl; }
template<typename Head, typename... Tail> 
void dbg_out(Head H, Tail... T) { 
    cerr << ' ' << H;
     dbg_out(T...); 
}
#define dbg(...) cerr << '(' << #__VA_ARGS__ << ')'<<':', dbg_out(__VA_ARGS__)
#define fastIO ios_base::sync_with_stdio(false); cin.tie(NULL);
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<ll,ll>
#define x first
#define y second
#define vi vector<int>
#define vll vector<ll>
#define on(val,pos) val|(1<<pos)
#define off(val,pos) val&(~(1<<pos))
#define check(val,pos) (val&(1<<pos))
#define all(n) n.begin(),n.end()
//first four adjacent,second four corner
//int row[8]={0,-1,0,1,1,-1,-1,1};
//int col[8]={-1,0,1,0,-1,-1,1,1};
//using namespace __gnu_pbds;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

int main(){
    //freopen("000input.txt","r",stdin);
    ll sum=0,tem=0,mod=1e9+7,i,n,val;
    fastIO
    cin>>n;
    for(i=0;i<n;i++){
        cin>>val;
        sum=(sum+tem*val)%mod;
        tem=(tem+val)%mod;
    }
    cout<<sum<<endl;
    //free();   //if pointer array
    return 0;
}


Measured memory_bytes: 3660
--{-# LANGUAGE OverloadedStrings #-}
--{-# LANGUAGE OverloadedLists   #-}
{-# LANGUAGE BangPatterns      #-} --引数に!
{-# LANGUAGE MultiWayIf        #-}
{-# LANGUAGE TupleSections     #-}

import Data.Bits
import Data.Foldable (foldlM,foldrM)
import Data.Maybe (fromJust)
import Data.List
--import Data.Matrix.Unboxed
import Data.Array  --変数衝突
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
import Data.Graph
--import Data.Vector as V　--変数衝突
import qualified Data.Vector.Unboxed as V
import Control.Monad
import Control.Monad.State
import Control.Monad.ST
import qualified Data.ByteString.Lazy.Char8 as B
import Debug.Trace

type Ans = Int

whites' :: String -> Int -> [Int]
whites' [] _ = []
whites' (x:xs) cnt = if x == '.' then (cnt+1):(whites' xs (cnt+1)) else cnt:(whites' xs cnt)

whites s n = 0:(whites' s n)

blacks' :: String -> Int -> [Int]
blacks' [] _ = []
blacks' (x:xs) cnt = if x == '#' then (cnt+1):(blacks' xs (cnt+1)) else cnt:(blacks' xs cnt)

blacks s n = 0:(blacks' s n)

solve :: [Int] -> [Int] -> [Int]
solve [] _ = []
solve (x:xs) (y:ys) = (x+y):(solve xs ys)

main :: IO ()
main = do
  n <- readLn :: IO Int
  s <- getLine
  traceShowM $ ((blacks s 0), (reverse (whites (reverse s ) 0)))
  print $ minimum $ solve (blacks s 0) (reverse (whites (reverse s ) 0))


Measured memory_bytes: 138620
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;

int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	int n; cin>>n;

	string a,b;
	cin>>a>>b;
	string s="";
	int cnt=0;
	int i=0;
	int j=0;
	while (i<n or  j<n) {
		if(cnt%2==0) {
			s+=a[i];
			i++;
		}
		else{
			s+=b[j];
			j++;
		}
		cnt++;
	}

	cout<<s<<endl;
	return 0;
}


Measured memory_bytes: 256
#pragma gcc optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(V) (V).begin(),(V).end()
#define SORT(V) sort(ALL(V)) //小さい方からソート
#define REV(V) reverse(ALL(V)) //リバース
#define RSORT(V) SORT(V);REV(V) //大きい方からソート
#define NPN(V) next_permutation(ALL(V)) //順列
#define pb(n) push_back(n)
#define endl '\n'
#define Endl '\n'
#define DUMP(x)  cout << #x << " = " << (x) << endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define Yay(n) cout << ((n) ? "Yay!": ":(") << endl
#define RAPID cin.tie(0);ios::sync_with_stdio(false)
#define IN(n) cin >> n
#define IN2(a,b) cin >> a >> b
#define IN3(a,b,c) cin >> a >> b >> c 
#define IN4(a,b,c,d) cin >> a >> b >> c >> d
#define VIN(V) for(int i = 0; i < (V).size(); i++) {cin >> (V).at(i);}
#define OUT(n) cout << n << endl
#define VOUT(V) REP(i, (V).size()) {cout << (V)[i] << endl;}
#define VOUT2(V) REP(i, (V).size()) {cout << (V)[i] << " ";} cout<<endl;

// 型マクロ定義
#define int long long
#define P pair<ll,ll>
#define Vi vector<ll>
#define Vd vector<double>
#define Vs vector<string>
#define Vc vector<char>
#define M map<ll,ll>
#define S set<ll>
#define PQ priority_queue<ll>
#define PQG priority_queue<ll,V,greater<ll>
//

const int MOD = 1000000007;
const int INF = 1061109567;
const double EPS = 1e-10;
const double PI  = acos(-1.0);

int gcd(int a,int b){return b?gcd(b,a%b):a;} //最小公倍数
string toStrUp(string str){char diff = 'A'-'a';REP(i,str.size()) str[i] += diff;return str;}
string gCh(string str, int key){return str.substr(key,1);}

signed main() {
  RAPID;
  // デフォルト変数定義
  int n,m,a,b,c,d,x,y,z;
  string s,t;
  //

  // ここから
  IN3(a,b,c);
  if(a==b && b==c) OUT(1);
  else if((a==b) || (b==c) || (a==c)) OUT(2);
  else OUT(3);
}

Measured memory_bytes: 256
from bisect import bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N):
    for j in range(i):
        m = L[i]-L[j]
        k = bisect_right(L, m)
        n = max(0, j-k)
        ans+=n
print(ans)

Measured memory_bytes: 44332
#include <iostream>
using namespace std;
int main(){
  int a=0;
  int b=0;

  cin >> a >> b;



  int conta = (a+b)/2;
  int a2=b-conta;
  a2=a2*-1;
  int a1=a-conta;
  if(a2==a1){
    cout << conta;}
  else{
    cout <<"IMPOSSIBLE" ;
  }
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <functional>
#include <math.h>
using namespace std;

#define ll long long
//#define int long long
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;

#define dump(x)  cerr << #x << " = " << (x) << endl; 
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl; 


typedef pair<int, int> P;
struct Point{
	int x, y;
};
int dx[4] = { 0, 1, 0, -1 };
int dy[4] = {1,0,-1,0};



int n;
int v[100001];
int even[100001], odd[100001];
int even1[100001], odd1[100001];

int main(){

	cin >> n;
	for (int i = 0; i < n; i++){
		cin >> v[i];
		if (i % 2 == 0) even[v[i]]++;
		else odd[v[i]]++;
	}
	for (int i = 0; i <=100000; i++){
		even1[i] = even[i];
		odd1[i] = odd[i];
	}

	sort(even, even + 100000, greater<int>());
	sort(odd, odd + 100000, greater<int>());

	int max_even;
	int max_odd;

	for (int i = 0; i <= 100000; i++){
		if (even1[i] == even[0]) max_even = i;
		if (odd1[i] == odd[0]) max_odd = i;
	}
	if (max_even != max_odd){
		cout << n - even[0] - odd[0] << endl;
	}
	else{
		cout << min(n - even[0] - odd[1], n - even[1] - odd[0]) << endl;
	}

	return 0;
}


Measured memory_bytes: 2176
#include <algorithm>
#include<iostream>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<list>
#include<map>
#include<set>
#include<string>
#include <sstream>
#include<bitset>

#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<limits.h>
const int INF = 0x7fffffff;
using lll = long long;
using ull = unsigned long long;
using namespace std;


map<int,int> prime_factor(lll n){
  map<int,int> factor;
  lll ii;
  for(ii=2;ii*ii<=n;ii++){
    while( n % ii == 0){
      //cout << "ii" << ii << endl;
      factor[ii]++;
      n = n / ii;
    }
  }
  
  if(n != 1){
    factor[n] = 1;
  }
  
  return factor;
}

int main(){
  lll ii,jj,kk;
  vector<int> ret;

  map<int,int> m;

  lll n ;

  cin >> n;

  m = prime_factor(n);
  lll num,cnt,sum;
  sum = 0;
  for(pair<int,int> p : m){
    //cout << "key:" << p.first << "val:" << p.second << endl;
    num = p.second;
    cnt = 1;

    while(num >= 0){
      num-=cnt;
      cnt+=1;
      if(num >= 0){
       sum++;
      }
    }
    
  }

  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 3636
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fi first
#define se second
typedef pair<ll,ll> P;
#define Mod 1000000007
using VP = vector<P>; using VVP = vector<VP>;
using VI = vector<ll>; using VVI = vector<VI>; using VVVI = vector<VVI>;
#define INF 1ll<<59

int main(){
    ll i,j;
    ll n;
    cin>>n;
    vector<string> st(n);
    for(i=0;i<n;i++){
        string s;
        cin>>s;
        vector<ll> v;
        for(j=0;j<s.size();j++) {
            ll p=s[j]-'a';
            v.pb(p);
        }
        sort(v.begin(),v.end());
        st[i]="";
        for(j=0;j<v.size();j++) st[i]+=char('a'+v[j]);
    }

    map<string,ll> ma;
    for(i=0;i<n;i++) ma[st[i]]++;
    ll ans=0;
    for(auto it=ma.begin();it!=ma.end();++it){
        ll x=it->second;
        ans+=x*(x-1)/2;
    }
    cout<<ans<<endl;

    return 0;
}

Measured memory_bytes: 13568
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>

using namespace std;

int main() {
  int N, K;
  string S;
  cin >> N >> K >> S;
  vector<char> digarr;
  vector<int> numarr;
  char prevc = -1;
  int cur = -1;
  for (int i = 0; i < S.length(); i++) {
    if (S[i] != prevc) {
      digarr.push_back(S[i]);
      numarr.push_back(0);
      cur++;
      prevc = S[i];
    }
    numarr[cur]++;
  }
  vector<int> sumarr(numarr.size());
  sumarr[0] = numarr[0];
  for (int i = 1; i < numarr.size(); i++) {
    sumarr[i] = sumarr[i-1] + numarr[i];
  }
  int res = -1;
  for (int i = 0; i < digarr.size(); i++) {
    if (digarr[i] == '0') {
      int sum = sumarr[min({i + 2*K-1, (int)numarr.size()-1})];
      if (i - 2 >= 0) {
        sum -= sumarr[i-2];
      }
      res = max({res, sum});
    }
  }
  if (res == -1) {
    res = S.length();
  }
  cout << res << endl;
  return 0;
}


Measured memory_bytes: 1400
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <map>
#include <numeric>
#include <cmath>
#include <set>
#include <sstream>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <complex>
#include <string.h>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <iomanip>
#include <sys/time.h>
#include <tuple>
#include <random>
using namespace std;

#define endl '\n'
#define ALL(v) (v).begin(), (v).end()
#define RALL(v) (v).rbegin(), (v).rend()
#define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end())

typedef long long ll;
typedef long double ld;
typedef pair<int, int> P;
typedef complex<double> comp;
typedef vector< vector<ld> > matrix;
struct pairhash {
public:
    template<typename T, typename U>
    size_t operator()(const pair<T, U> &x) const {
	size_t seed = hash<T>()(x.first);
	return hash<U>()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2);
    }
};
const int inf = 1e9 + 9;
const ll mod = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1);

int n, m;
int p[100100], y[100100];

void solve() {
    string res[m];
    vector<P> vec[n+1];
    for (int i = 0; i < m; i++) {
        vec[p[i]].push_back(P(y[i], i));
    }

    char buf[50];
    for (int i = 1; i <= n; i++) {
        sort(ALL(vec[i]));
        for (int j = 0; j < (int)vec[i].size(); j++) {
            int idx = vec[i][j].second;
            sprintf(buf, "%06d%06d", i, j+1);
            res[idx] = buf;
        }
    }

    for (int i = 0; i < m; i++) {
        cout << res[i] << endl;
    }
}

void input() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) cin >> p[i] >> y[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);

    input();
    solve();
}


Measured memory_bytes: 13184
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cstdio>
#include <cmath>
#include <tuple>
#include <iomanip>
#include <numeric>
#include <unordered_map>
#include <sstream>   
#include<limits.h>
#include<list>
#include <array>
using namespace std;
#define i64  long long
#define int  long long
 
#define I32_MAX 2147483647
#define I64_MAX 9223372036854775807
#define INF I64_MAX
#define MOD 1000000007


void solve(void)
{ 
  int H,W;
  cin>>H>>W;
  vector<vector<char> > mat(H,vector<char>(W));
  for (int i = 0; i < H; i++)
  {
    for (int j = 0; j < W; j++)
    {
      cin>>mat[i][j];
    }
  }

  for (int i = 0; i < H; i++)
  {
    for (int k = 0; k < 2; k++)
    {    
    for (int j = 0; j < W; j++)
    {
      cout<<mat[i][j];
    }
    cout<<endl;
    }

  }
  
  
  return;
  
}



int32_t main(int32_t argc, const char *argv[])
{
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);

  // std::cout << std::fixed;
  // std::cout << std::setprecision(8);

  solve();

 
  return 0;
}

Measured memory_bytes: 256
import collections
N=int(input())
Branch=[[] for i in range(N)]
for i in range(N-1):
  a,b,c=map(int,input().split())
  Branch[a-1].append([b-1,c])
  Branch[b-1].append([a-1,c])
Q,K=map(int,input().split())
Dist=[float("Inf") for i in range(N)]
flag = [0 for i in range(N)]

que=collections.deque()
que.append(K-1)
Dist[K-1]=0
while len(que):
  u=que.pop()
  for i,j in Branch[u]:
    if Dist[i]==float("Inf"):
      Dist[i]=Dist[u]+j
      que.append(i)

  
for i in range(Q):
  x,y = map(int,input().split())
  print(Dist[x-1]+Dist[y-1])
  

Measured memory_bytes: 52852
n,m,c = map(int,input().split())
b = list(map(int,input().split()))
a = list(list(map(int,input().split())) for _ in range(n))

answer = 0
for i in range(n):
    checker = c
    for j in range(m):
        checker += a[i][j]*b[j]
    if checker > 0:
        answer += 1

print(answer)


Measured memory_bytes: 3064