akhauriyash/Code-Regression huggingface dataset:
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n - 1];
        int[] b = new int[n - 1];
        int[] c = new int[n];
        for (int i = 0 ; i < n - 1 ; i++) {
            a[i] = sc.nextInt() - 1;
            b[i] = sc.nextInt() - 1;
        }
        int sum = 0;
        for (int i = 0 ; i < n ; i++) {
            c[i] = sc.nextInt();
            sum += c[i];
        }
        Arrays.sort(c);

        int[] e = new int[n];
        e[a[0]] = c[n - 1];
        e[b[0]] = c[n - 2];
        for (int i = 2 ; i < n ; i++) {
            for (int j = 0 ; j < n - 1 ; j++) {
                if (e[a[j]] * e[b[j]] == 0 && e[a[j]] + e[b[j]] != 0) {
                    if (e[a[j]] == 0) {
                        e[a[j]] = c[n - 1 - i];
                        break;
                    } else {
                        e[b[j]] = c[n - 1 - i];
                        break;
                    }
                }
            }
        }

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

        System.out.print(e[n - 1]);
        System.out.println("");
    }

}

Measured memory_bytes: 42800
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }

    private void solve() throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer tokenizer = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(tokenizer.nextToken());
        int k = Integer.parseInt(tokenizer.nextToken());
        int value = 0;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
        tokenizer = new StringTokenizer(f.readLine());
        for (int i = 0; i < n; i++) {
            pq.add(Integer.parseInt(tokenizer.nextToken()));
        }
        for (int i = 0; i < k; i++) {
            value += pq.remove();
        }
        out.println(value);
        out.close();
    }
}


Measured memory_bytes: 33360
import sys
sys.setrecursionlimit(10**5)

n,k=map(int,input().split())
m=10**9+7
to=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(lambda x:int(x)-1, input().split())
  to[a].append(b)
  to[b].append(a)
frac=[1]*(10**5+1)
for i in range(1,10**5+1):
  frac[i]=frac[i-1]*i
  frac[i]%=m


def nPk(_n,_k):
  if _n<0 or _k<0 or _n-_k<0: return 0;
  a=frac[_n]
  b=frac[_n-_k]
  return (a*pow(b,m-2,m))%m


def dfs(_v, _u=-1):
  global ans
  for u in to[_v]:
    if u==_u: continue
    dfs(u, _v)
  p=len(to[_v])
  ans*=nPk(k,p+1) if _v==0 else nPk(k-2,p-1)
  ans%=m
    
    
ans=1
chk=[False]*n
dfs(0)
  
print(ans)

Measured memory_bytes: 115672
#include <bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
typedef pair<double, double> pdd;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<string> vs;
//const int mod = ;

int d[305][305][305];

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  string s;
  int k;
  cin >> s >> k;
  int n = s.size();
/*  if (k == n) {
    cout << n << endl; return 0;
  }*/
  for (int i = 0; i < n; ++i) {
    d[i][i][0] = 1;
  }
  int res = 0;
  for (int l = 2; l <= n; ++l) {
    for (int i = 0; i + l <= n; ++i) {
      int j = i + l - 1;
      for (int t = 0; t <= k; ++t) {
        d[i][j][t] = max(d[i+1][j][t], d[i][j-1][t]);
        if (s[i] == s[j]) d[i][j][t] = max(d[i][j][t], d[i+1][j-1][t] + 2);
        if (t) {
          d[i][j][t] = max(max(d[i][j][t], d[i+1][j-1][t-1] + 2), d[i][j][t-1]);
        }
        res = max(res, d[i][j][t]);
      }
    }
  }
  cout << max(1, res) << endl;
  return 0;
}

Measured memory_bytes: 110848
from collections import defaultdict
def D():
    N, M = map(int, input().split())
    edges = defaultdict(list)
    for i in range(M):
        A, B = map(int, input().split())
        edges[A].append(B)
        edges[B].append(A)
    
    ans = {}
    q = [(1, None)]
    seen = set(q)
    while q:
        cur, last = q.pop(0)
        ans[cur] = last
        for room in edges[cur]:
            if room not in seen:
                q.append((room, cur))
                seen.add(room)
    
    if len(ans) < N:
        print('No')
    else:
        print('Yes')
        for i in range(2, N+1):
            print(ans[i])

D()

Measured memory_bytes: 55168
/*
digu_J - Digvijay Janartha
NIT Hamirpur - INDIA
*/

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

const long long MOD = 998244353, N = 2e5 + 5;

long long dp[N], pre[N];

void test() {
    int n, k;
    cin >> n >> k;
    pair<int, int> p[k];
    for (int i = 0; i < k; ++i) {
        cin >> p[i].first >> p[i].second;
    }
    sort(p, p + k);
    dp[1] = pre[1] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 0; j < k; ++j) {
            dp[i] += (pre[max(0, i - p[j].first)] - pre[max(0, i - p[j].second - 1)]) % MOD + MOD;
            dp[i] %= MOD;
        }
        pre[i] = (pre[i - 1] + dp[i]) % MOD;
    }
    cout << dp[n] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifdef HOME
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i) {
        test();
    }
    return 0;
}


Measured memory_bytes: 6764
N,M,X = map(int,input().split())
pA = [0]*N
for i in range(N):
    pA[i] = list(map(int,input().split()))
C = [0]*12
A = [0]*12
for i in range(N):
    C[i] = pA[i][0]
    A[i] = pA[i][1:]
minprice = sum(C)+1


for i1 in range(2):
    for i2 in range(2):
        for i3 in range(2):
            for i4 in range(2):
                for i5 in range(2):
                    for i6 in range(2):
                        for i7 in range(2):
                            for i8 in range(2):
                                for i9 in range(2):
                                    for i10 in range(2):
                                        for i11 in range(2):
                                            for i12 in range(2):
                                                point = 0
                                                tasei = [0]*M
                                                price = 0
                                                itati = [i1,i2,i3,i4,i5,i6,i7,i8,i9,i10,i11,i12]
                                                for j in range(N):
                                                    price += itati[j]*C[j]
                                                    for k in range(M):
                                                        tasei[k] += itati[j]*A[j][k] 
                                               
            
                                                for i in range(M):
                                                    if tasei[i]>=X:
                                    
                                                        if i == M-1:
                                                            point = 1
                                                    else:
                                                        break
                                                    
                                                       
                                                
                                                if price < minprice and point == 1:
                                                    minprice = price
                                                  
if minprice == sum(C)+1:
    print(-1)
else:
    print(minprice)

Measured memory_bytes: 70760
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Sparsh Sanchorawala
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        ATheNumberOfEvenPairs solver = new ATheNumberOfEvenPairs();
        solver.solve(1, in, out);
        out.close();
    }

    static class ATheNumberOfEvenPairs {
        public void solve(int testNumber, InputReader s, PrintWriter w) {
            long n = s.nextLong(), m = s.nextLong();
            w.println(n * (n - 1) / 2 + m * (m - 1) / 2);
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }
}



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

int main() {
  string S;
  cin >> S;
  bool n = false;
  bool s = false;
  bool e = false;
  bool w = false;
  rep(i, S.size()) {
    if (S[i] == 'N') n = true;
    if (S[i] == 'S') s = true;
    if (S[i] == 'E') e = true;
    if (S[i] == 'W') w = true;
  }
  if (n == s && w == e) {
    cout << "Yes" << endl;
  }
  else {
    cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 3588
#include<bits/stdc++.h>
using namespace std;
long long n,a,z;
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)
	  cin>>a,z=(z+a)%2;
	if(z)cout<<"NO";else cout<<"YES";
	cout<<endl;
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define repo(i,n) for(int i = 1; i < (int)(n); i++)
#define pb push_back
#define mp make_pair
#define np next_permutation
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define mod 1000000007
#define pi acos(-1.0)
ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }
ll lcm(ll x, ll y) { return x / gcd(x, y) * y; }
ll jou(ll N, ll P){if(P==0) return 1;
    if(P%2==0){ll t = jou(N, P/2);return t*t % mod;
    }return (N * jou(N, P-1)) % mod;}  //jou(n,mod-2)で逆元
//intの最大値2147483647 ≒ 2×10^9
//long longの最大値9223372036854775807 ≒ 9×10^18
//'大文字'+=32;    で小文字に
//  cout << fixed << setprecision (20);   小数点以下2０桁まで
//実行時間制約2秒では２×10^8回くらいまで計算できる



//————————DFSグラフ木カウント————————————————

using Graph = vector<vector<int>>;

int main() {
    // 頂点数と辺数
    int n,m;
    cin >> n >> m;

    // グラフ入力受取 (ここでは無向グラフを想定)
    Graph G(n);
    rep(i,m) {
        int a,b;
        cin >> a >> b;
        G[a-1].pb(b-1);
        G[b-1].pb(a-1);
    }

    // BFS のためのデータ構造
    vector<int> dist(n, -1); // 全頂点を「未訪問」に初期化
    deque<pair<int,int>> que;
    vector<int> road(n);

  int ans=0;
  vector<bool> memo(n);
  
      dist[0]=0;
      auto x = mp(0,-1);
      que.pb(x);
      
      // BFS 開始 (キューが空になるまで探索を行う)
      while (!que.empty()) {
        auto v = que.front(); // キューから先頭頂点を取り出す
        que.pop_front();

        // v から辿れる頂点をすべて調べる
        for (int nv : G[v.fi]) {
            if (dist[nv] != -1 ) continue; // すでに発見済みの頂点は探索しない

            // 新たな白色頂点 nv について距離情報を更新してキューに追加する
            else {
            dist[nv] = v.fi;
            auto y = mp(nv,v.fi);
            que.pb(y);
            }
        }
      }      

repo(i,n){
    if(dist[i]==-1) {
        cout << "No" << endl;
        return 0;
    }
}

cout << "Yes" << endl;
repo(i,n){
    cout << dist[i]+1 << endl;
}



}

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

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

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

    int ans = 0;
    for (int i = 0; i < n; ++i) {
        int pick = 0;
        for (int j = 0; j < i+1; ++j) {
            pick += a[0][j];
        }
        for (int j = i; j < n; ++j) {
            pick += a[1][j];
        }
        if (ans < pick) ans = pick;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
function Main(input){
  input = input.split("\n");
  inputStr = input[0].split(" ");
  var X = Number.parseInt(inputStr[0]);
  var A = Number.parseInt(inputStr[1]);
  //三項演算子を使って値を出す
  console.log( X < A ? "0" : "10");
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
import java.util.*;

public class Main{

	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int c = sc.nextInt();
		
		int max = Math.max(a,b);
		max = Math.max(max,c);
		
		System.out.println(a+b+c - max);
	}
}

Measured memory_bytes: 23252
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<climits>
#include<string>
#include<vector>
#include<map>
#include<queue>
#include<set>
#include<algorithm>

#define ll long long
#define dl double
#define mod 1000000007
#define sz 1005

using namespace std;

int main()
{
    ll n,x,cnt=0;

    scanf("%lld",&n);

    map<ll, ll>mp;
    mp.clear();

    while(n--)
    {
        scanf("%lld",&x);

        mp[x]++;

        if(mp[x]==1)
            cnt++;

        else if(mp[x]==2)
        {
            cnt--;
            mp[x]=0;
        }
    }

    printf("%lld\n",cnt);

    return (0);
}




Measured memory_bytes: 6528
#include<stdio.h>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<algorithm>
#include<cmath>
#include<bitset>
#include<set>
 
#define Vsort(a) sort(a.begin(), a.end())
#define Vreverse(a) reverse(a.begin(), a.end())
#define Srep(n) for(int i = 0; i < (n); i++)
#define Lrep(i,a,n) for(int i = (a); i < (n); i++)
#define Brep(n) for(int bit = 0; bit < (1<<n); bit++)
#define rep2nd(n,m) Srep(n) Lrep(j,0,m)
#define vi vector<int>
#define vi64 vector<int64_t>
#define vvi vector<vector<int>>
#define vvi64 vector<vector<int64_t>>
#define P pair<int,int>
#define F first
#define S second
 
using namespace std;

int main(){
  int a,b;
  char op;
  cin >> a >> op >> b;
  if(op == '+') cout << a + b << endl;
  else cout << a - b << endl;
}

Measured memory_bytes: 3616
#include <iostream>
#include <fstream>
#include <iomanip>
#include <math.h>
#include <limits.h>
#include <algorithm>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <string>
#include <string.h>
#include <sstream>
#include <ctime>

using namespace std;

#define eps 1e-12
#define pi 3.14159265358979323846
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define bgn begin
#define ll long long
#define ld long double
#define ull unsigned long long
#define ii pair<ll,ll>









ll n,m,res;

void solve()
{
	cin>>n>>m;
	if(m>=2*n)
	{
		res=n+((m-(2*n))/4);
	}
	else
	{
		res=m/2;
	}
	cout<<res<<"\n";
}

int main()
{
	std::ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef localProject
	freopen("in.txt","r",stdin);
#endif
	solve();
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,j,n) for(int i=(int)(j);i<(int)(n);i++)
#define REP(i,j,n) for(int i=(int)(j);i<=(int)(n);i++)
#define MOD 1000000007
#define int long long
#define ALL(a) (a).begin(),(a).end()
#define vi vector<int>
#define vii vector<vi>
#define pii pair<int,int>
#define priq priority_queue<int>
#define disup(A,key) distance(A.begin(),upper_bound(ALL(A),(int)(key)))
#define dislow(A,key) distance(A.begin(),lower_bound(ALL(A),(int)(key)))
#define tii tuple<int,int,int>
#define Priq priority_queue<int,vi,greater<int>>
#define pb push_back
#define mp make_pair
#define INF (1ll<<60)
signed main(){
  int N,M; cin>>N>>M;
  vi A(M),B(M);
  rep(i,0,M){
    cin>>A[i];
    int X; cin>>X;
    rep(j,0,X){
      int Y; cin>>Y;
      B[i]+=(1ll<<Y-1);
    }
  }
  vi dp((1ll<<N),INF);
  dp[0]=0;
  rep(i,0,M){
    rep(j,0,(1ll<<N)){
      int X=B[i]|j;
      dp[X]=min(dp[X],dp[j]+A[i]);
    }
  }
  int ans=dp[(1ll<<N)-1];
  if(ans==INF) ans=-1;
  cout<<ans<<endl;
  }



Measured memory_bytes: 384
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

s = list(STR())
t = list(STR())
s.sort()
t.sort(reverse=True)
arr = [s, t]
arr.sort()
if arr[0] == s and s != arr[1]:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 5192
#include <iostream>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <functional>
using namespace std;
#define int long long
#define All(v) (v).begin(),(v).end()
int dy[8] = {-1,0,1,0,-1,1,1,-1};
int dx[8] = {0,1,0,-1,1,1,-1,-1};
const int mod = 1000000007;
const int inf = mod*mod;
const int d5 = 100100;
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    char c;
    cin>>c;
    int x=c;
    cout<<char(x+1)<<endl;
}

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<int, int>;
const int INF = 10101000;
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> g(n+10);
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> dist(n+10, INF);
    dist[0] = 0;
    vector<int> pre(n, 0);

    queue<int> q;
    q.push(0);
    while(!q.empty()) {
        int v = q.front();
        q.pop();
        for(auto p: g[v]) {
            if (dist[p] != INF) continue;
            dist[p] = dist[v] + 1;
            pre[p] = v;
            q.push(p);
        }
    }
    
    cout << "Yes" << endl;
    rep(i, n) {
        if (i == 0) continue;
        pre[i]++;
        cout << pre[i] << endl;
    } 
    return 0;
}

Measured memory_bytes: 10656
<?php
error_reporting(0);
//list($A,$B,$C,$D) = explode(" ",trim(fgets(STDIN)));
$N = trim(fgets(STDIN));
$ans = 1;
for($i=0;$i<$N;$i++) {
  $T=trim(fgets(STDIN));
  $ans = lcm($ans,$T);
}
//$a = explode(" ",trim(fgets(STDIN)));

printf("%d\n",$ans);

function gcd($a,$b) {
  if ($b == 0) return $a;
  return gcd($b,$a%$b);
}
function lcm($a,$b) {
  $l = gcd($a,$b);
  return $a / $l * $b;
}


Measured memory_bytes: 3700
#include <iostream>
#include <queue>
#include <map>

using namespace std;

typedef pair<int, int> P;

int n, q;
int fish[1000001];

int main() {
  cin >> n >> q;
  
  priority_queue<P> pq;
  
  for(int i = 0; i < q; i++) {
    int a, v;
    cin >> a >> v;
    fish[a] += v;
    pq.push(P(fish[a], a * (-1)));
    
    while(!pq.empty()) {
      P p = pq.top();
      p.second *= -1;
      if(p.first == fish[p.second]) {
        cout << p.second << ' ' << p.first << endl;
        break;
      }
      pq.pop();
    }
  }

  return 0;
}

Measured memory_bytes: 6008
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <algorithm>

using namespace std;

int main(){
    string S,T;
    cin >> S;
    cin >> T;
    string str(S);
    do{
        char beginStr = str[0];
        for(int i = 1; i < str.length(); i++){
            str[i - 1] = str[i];
        }
        str[S.length() - 1] = beginStr;
        if(str == T){
            cout << "Yes" << endl;
            return 0;
        }
    }while(str != S);
    cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ini(a,i) memset(a,i,sizeof(a))
#define pb push_back
#define ll long long
#define inf LLONG_MAX

void solve()
{
	ll n,i,c,ans,add;
	cin>>n;
	ans=0;
	for(i=2;i*i<=n;i++)
	{
		if(n%i)	continue;
		c=0;
		while(n%i==0)
		{
			n/=i;
			c++;
		}
		add=1;
		for(ll j=1;j<=50;j++)	
		{
			if((j*(j+1)/2)<=c)	add=j;
		}
		ans+=add;
	}

	if(n>1)	ans++;
	cout<<ans<<endl;
}


int main()
{
	std::ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	//ll tt;	cin>>tt;	while(tt--)
	{
		solve();
 	}
	cerr<<" Execution : "<<(1.0*clock())/CLOCKS_PER_SEC<<"s \n";
		
		
return 0;
}

Measured memory_bytes: 3800
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import array
from bisect import *
from collections import *
import fractions
import heapq
from itertools import *
import math
import random
import re
import string
import sys

def solve_1(N):
    N_str = str(N)
    ans = 0
    for i, ch in enumerate(N_str):
        if i == 0:
            ans += int(ch)
        else:
            ans += 9
    return ans

def solve_2(N):
    N_str = str(N)

    # N = 72543

    # 6XXXX
    ans = (int(N_str[0]) - 1) * 9 * (len(N_str) - 1)

    # 7XXXX
    flag = False
    for ch in N_str[1:]:
        if flag:
            ans += 9
        else:
            ans += int(ch)
            if ch != '0':
                flag = True

    # XXXX
    for i in range(1, len(N_str) - 1):
        ans += 81 * i

    return ans

def solve_slow_2(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 2
    return ans

# for n in range(1, 10000):
#     mine = solve_2(n)
#     gt = solve_slow_2(n)
#     if mine != gt:
#         print("error! n, mine, gt = ", n, mine, gt)
#         sys.exit(0)
#     else:
#         print(n, "ok")


def solve_3(N):
    N_str = str(N)
    size = len(N_str)

    # N = 72543

    # 6XXXX
    ans = (int(N_str[0]) - 1) * (((size - 1) * (size - 2)) // 2) * 81

    # 7XXXX
    # -> XXXX
    if size > 1:
        ans += solve_2(int(N_str[1:]))

    # XXXX
    for size in range(1, len(N_str)):
        ans += 9 * 9 * 9 * (size - 1) * (size - 2) // 2

    return ans

def solve_slow_3(n):
    ans = 0
    for i in range(1, n + 1):
        i_str = str(i)
        cnt = 0
        for ch in i_str:
            cnt += ch != '0'
        ans += cnt == 3
    return ans

# for n in range(1, 10000):
#     mine = solve_3(n)
#     gt = solve_slow_3(n)
#     if mine != gt:
#         print("error! n, mine, gt = ", n, mine, gt)
#         sys.exit(0)
#     else:
#         print(n, "ok")
        

def solve(N, K):
    if K == 1:
        return solve_1(N)
    elif K == 2:
        return solve_2(N)
    else:
        return solve_3(N)


N = int(input())
K = int(input())

print(solve(N, K))



Measured memory_bytes: 6412
#include<bits/stdc++.h>
using std::swap;
typedef long long i64;
const i64 inf=1ll<<60;
const int N=110007;
int n,v0[N],ps[N],pp=0;
char op[N];
i64 ans=0,s1[N],s2[N];
i64 min(i64 a,i64 b){return a<b?a:b;}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		if(i>1)scanf("%s",op+i);
		scanf("%d",v0+i);
		s1[i]=v0[i];
		if(op[i]=='-')v0[i]*=-1,ps[pp++]=i;
		ans+=v0[i];
		s2[i]=v0[i]+s2[i-1];
	}
	for(int i=n;i;--i)s1[i]+=s1[i+1];
	for(int i=1;i<pp;++i){
		int l=ps[i-1],r=ps[i];
		i64 v=s2[l]+s1[r]-(s2[r-1]-s2[l]);
		if(v>ans)ans=v;
	}
	printf("%lld\n",ans);
	return 0;
}

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

const int maxn = 1e5 + 10;

int a[maxn];

int main() {
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        scanf("%d", &a[i]);

    if(a[n] != 2){
        cout<<-1<<endl;
        return 0;
    }
    long long mn = 2, mx = 2;
    for(int i=n;i;i--) {
        long long x = mn / a[i] + (mn %a[i] != 0), y = mx/a[i];
        if(y * a[i] < mn) {
            cout<<-1<<endl;
            return 0;
        }
        mn = x * a[i];
        mx = (y * a[i]) + a[i] - 1;
    }
    cout<<mn<<' '<<mx<<endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <functional>
using namespace std;

typedef long long ll;


class segment_tree_l {
private:
	static const int MAX_N = 1 << 18;
	int num, dat[2 * MAX_N - 1];

	// TODO: change operator and its identity
	static const int INI = 0;
	int op(int a, int b) {
		return a^b;
	}

public:
	segment_tree_l(int n_) {
		if (n_ > MAX_N) cerr << "INVALID INPUT" << endl;
		num = 1;
		while (num < n_) num *= 2;
		for (int i = 0; i < 2 * num - 1; i++) dat[i] = INI;
	}

	// update the k-th value (0-indexed) to a
	void update(int k, int a) {
		k += num - 1;
		dat[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			dat[k] = op(dat[2 * k + 1], dat[2 * k + 2]);
		}
	}

	// get the value of the range [a, b)
	// k: the index of the node  
	// [left, right): the range corresponds to the k-th node
	// called like getval(a, b) or getval(a, b, 0, 0, num)
	int getval(int a, int b, int k = 0, int left = 0, int right = -1) {
		if (right < 0) right = num;
		if (right <= a || b <= left) return INI;
		if (a <= left && right <= b) return dat[k];
		int vleft = getval(a, b, 2 * k + 1, left, left + (right - left) / 2);
		int vright = getval(a, b, 2 * k + 2, left + (right - left) / 2, right);
		return op(vleft, vright);

	}
};

class segment_tree_r {
private:
	static const int MAX_N = 1 << 18;
	int num, dat[2 * MAX_N - 1];

	// TODO: change operator and its identity
	static const int INI = 0;
	int op(int a, int b) {
		return a + b;
	}

public:
	segment_tree_r(int n_) {
		if (n_ > MAX_N) cerr << "INVALID INPUT" << endl;
		num = 1;
		while (num < n_) num *= 2;
		for (int i = 0; i < 2 * num - 1; i++) dat[i] = INI;
	}

	// update the k-th value (0-indexed) to a
	void update(int k, int a) {
		k += num - 1;
		dat[k] = a;
		while (k > 0) {
			k = (k - 1) / 2;
			dat[k] = op(dat[2 * k + 1], dat[2 * k + 2]);
		}
	}

	// get the value of the range [a, b)
	// k: the index of the node  
	// [left, right): the range corresponds to the k-th node
	// called like getval(a, b) or getval(a, b, 0, 0, num)
	int getval(int a, int b, int k = 0, int left = 0, int right = -1) {
		if (right < 0) right = num;
		if (right <= a || b <= left) return INI;
		if (a <= left && right <= b) return dat[k];
		int vleft = getval(a, b, 2 * k + 1, left, left + (right - left) / 2);
		int vright = getval(a, b, 2 * k + 2, left + (right - left) / 2, right);
		return op(vleft, vright);

	}
};


int main() {
	int n; cin >> n;
	vector<int> a(n + 2);
	segment_tree_l l(n);
	segment_tree_r r(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		l.update(i, a[i]);
		r.update(i, a[i]);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++) {
		int lo = i, hi = n + 1;
		while (hi - lo > 1) {
			int mid = lo + (hi - lo) / 2;
			if (l.getval(i, mid) == r.getval(i, mid)) lo = mid;
			else hi = mid;
		}
		ans += lo - i;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 5120
'use strict';
process.stdin.on('data', function(chunk) {
  var inputs = chunk.toString().trim().split('\n').map(Number);
  for (var i = 0; i < inputs.length; i++) {
    if(inputs[i]=== 0 ) {
        break;
    }
    console.log('Case '+ (i + 1)+ ': '+inputs[i]);
  }
    
});
process.stdin.resume();
process.stdin.setEncoding('utf8');

Measured memory_bytes: 20572
import collections
def inpl(): return [int(i) for i in input().split()]


n = int(input())
v = inpl()
ans = len(v)
v1 = [v[i] for i in range(ans) if i%2 == 0]
v2 = [v[i] for i in range(ans) if i%2 == 1]
cv1 = collections.Counter(v1)
cv2 = collections.Counter(v2)
c11 = cv1.most_common()[0]
if len(cv1) != 1:
    c12 = cv1.most_common()[1]
else: c12 = [0,0]
c21 = cv2.most_common()[0] 
if len(cv2) != 1:
    c22 = cv2.most_common()[1]
else: c22 = [0,0]

if c11[0] == c21[0]:
    ans -= max(c12[1]+c21[1],c11[1]+c22[1])
else:
    ans -= c11[1]+c21[1]
print(ans)    

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

#define call_from_test
#ifndef call_from_test
#include<bits/stdc++.h>
using namespace std;
#endif
//BEGIN CUT HERE
template<typename T>
T extgcd(T a,T b,T& x,T& y){
  T d=a;
  if(b!=0){
    d=extgcd(b,a%b,y,x);
    y-=(a/b)*x;
  }else{
    x=1;y=0;
  }
  return d;
}

template<typename T>
T mod_inverse(T a,T mod){
  T x,y;
  extgcd(a,mod,x,y);
  return (x%mod+mod)%mod;
}
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  return 0;
}
#endif

#undef call_from_test

#endif
//BEGIN CUT HERE
template<typename T, size_t sz>
struct Combination{
  using ll = long long;
  array<T, sz> fact;

  T mod;
  Combination(T mod):mod(mod){init();}

  void init(){
    fact[0]=1;
    for(int i=1;i<(int)sz;i++)
      fact[i]=(ll)fact[i-1]*i%mod;
  }

  T mod_fact(T n,T& e){
    e=0;
    if(n==0) return 1;
    T res=mod_fact(n/mod,e);
    e+=n/mod;
    if(n/mod%2!=0)return res*(mod-fact[n%mod])%mod;
    return res*fact[n%mod]%mod;
  }

  T mod_comb(T n,T k){
    if(n==k||k==0) return 1;
    T e1,e2,e3;
    T a1=mod_fact(n,e1),a2=mod_fact(k,e2),a3=mod_fact(n-k,e3);
    if(e1>e2+e3) return 0;
    return a1*mod_inverse<ll>((ll)a2*a3%mod,mod)%mod;
  }
};
//END CUT HERE
#ifndef call_from_test
//INSERT ABOVE HERE
signed main(){
  cin.tie(0);
  ios::sync_with_stdio(0);

  int n;
  cin>>n;
  string s;
  cin>>s;

  vector<int> as(n);
  for(int i=0;i<n;i++) as[i]=s[i]-'1';

  const int sz = 1e6+10;
  Combination<int, sz> C(2);

  int is_one=0;
  for(int i=0;i<n;i++)
    if(as[i]&1) is_one^=C.mod_comb(n-1,i);

  if(is_one){
    cout<<1<<endl;
    return 0;
  }

  for(int i=0;i<n;i++){
    if(as[i]==1){
      cout<<0<<endl;
      return 0;
    }
    as[i]/=2;
  }

  int is_two=0;
  for(int i=0;i<n;i++)
    if(as[i]&1) is_two^=C.mod_comb(n-1,i);

  cout<<is_two*2<<endl;
  return 0;
}
/*
  verified on 2020/03/22
  https://atcoder.jp/contests/agc043/tasks/agc043_b
*/
#endif


Measured memory_bytes: 9116
n = int(input())
arr = list(map(int, input().split()))
sum1 = 0
sum2 = sum(arr)
min_ = 1<<60

for i in range(n-1):
    sum1 += arr[i]
    sum2 -= arr[i]
    min_ = min(min_, abs(sum1 - sum2))
print(min_)

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

int main(){
    ll a,b,c,k;
    cin>>a>>b>>c>>k;
    ll ans=0;
    if(k<=a){
    	ans=k;
	}
	else if(k>a&&k<=a+b){
		ans=a;
	}
	else{
		ans+=a;
		ans-=k-a-b;
	}
	cout<<ans<<endl;
	return 0;
}


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

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    ll n;
    cin >> n;
    vector<ll> a(n), sum(n+1);
    for(int i=0;i<n;i++){

    	cin >> a[i];
    	sum[i+1] = sum[i] + a[i];

    }
    ll ans = INF;
    for(int i=1;i<n;i++){
    	ans = min(ans, abs(sum[n] - sum[i] - sum[i]));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3456
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int N;
	cin >> N;
	int x,y,z;
	int c[10005]={0};
	for(x = 1; x <= 105; x++){
		for(y = 1; y <= 105; y++){
			for(z = 1; z <= 105; z++){
				int sum = x*x+y*y+z*z+x*y+z*x+y*z;
				if(sum < 10001){
					c[sum]++;
				}
			}	
		}		
	}	
	for(int i = 0;i < N;i++){
		cout << c[i+1] << endl;
	}			
	return 0;		
}

Measured memory_bytes: 3620
def resolve():
    MOD = 10 ** 9 + 7
    N = int(input())
    AB = [list(map(int, input().split())) for _ in range(N)]

    dp = [0] * (1 << N)
    dp[0] = 1

    bitcount = [0]
    for _ in range(N):
        bitcount += [i + 1 for i in bitcount]

    for bit in range(1 << N):
        i = bitcount[bit]
        for j in range(N):
            # i番目の男性とk番目の女性が相性○ かつ その女性がまだマッチング済みでない場合
            if ((bit >> j) & 1 == 0) and (AB[i - 1][j] == 1):
                # 今の状態からk番目の女性だけを新たにbit立てる
                dp[bit ^ (1 << j)] += dp[bit]
        dp[bit] %= MOD
    print(dp[-1])


if __name__ == "__main__":
    resolve()

Measured memory_bytes: 201512
#include<iostream>
#include<stdio.h>
#include<cctype>
using namespace std;

int main(){
	char ch;
	int counter[26];

	for (int i = 0; i < 26; i++){
		counter[i] = 0;
	}

	while (cin >> ch){
		if (islower(ch)){
			counter[ch - 'a']++;
		}
		else if (isupper(ch)){
			counter[ch - 'A']++;
		}
	}

	for (int i = 0; i < 26; i++){
		printf("%c : %d\n", i + 'a', counter[i]);
	}

	return 0;
}

Measured memory_bytes: 3224
#!/usr/bin/env ruby

require 'set'

class Hash
  def push(key, value)
    self[key] = [] if self[key] == nil
    self[key].push(value)
  end
end

class Array
  def lower_bound(value)
    left = -1;
    right = self.length;
    while left + 1 < right
      mid = left + (right - left) / 2;
      if self[mid] >= value
        right = mid
      else
        left = mid
      end
    end
    right
  end

  def unique
    res = [self.first]
    each_cons(2) do |a, b|
      if a != b
        res.push(b)
      end
    end
    res
  end
end

def get_ints
  gets.chomp.split.map(&:to_i)
end

def get_ints_minus_one
  get_ints.map { |x| x - 1 }
end

def get_int
  gets.chomp.to_i
end

N = get_int

puts N ** 3


Measured memory_bytes: 14476
#include <iostream>
#include <cmath>
using namespace std;
int main(void){
    int N,K;
    cin>>N>>K;
    int ans=1;
    for(int i=1;i<=N;i++){
        if(ans>=K) ans=ans+K;
        else ans=ans*2;
    }
    cout<<ans;
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std; 
  
int main()
{
   int count =0;int h;int a;
   cin >> h;
   cin >> a;
    
   while(h>0)
   {
       h=h-a;
       count++;
   }
   cout << count << endl;
   
   return 0;
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define fint register int
#define h 5001
#define p 7659834
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;//aim:c>b>a;
	int k;
	cin>>k;
	int ans=0;
	while(a>=b)
	b*=2,ans++;
	while(b>=c)
	c*=2,ans++;
	if(ans<=k)
	cout<<"Yes";
	else
	cout<<"No";
	return 0;
}

Measured memory_bytes: 3632
K, A, B = list(map(int, input().split()))

cur = 1

if B - A <= 2:
	print(1 + K)
	exit(0)

if K - (A - 1) < 0:
	print(1 + K)
	exit(0)

res = A + (K - (A - 1)) // 2 * (B - A)
if (K - (A - 1)) % 2 != 0:
	res += 1

print(res)

Measured memory_bytes: 3064
use std::io::*;
use std::str::*;

fn read<T: FromStr>(s: &mut StdinLock) -> Option<T> {
    let s = s
        .by_ref()
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok()
}

fn main() {
    let stdin = std::io::stdin();
    let r = read::<i32>(&mut stdin.lock()).unwrap();
    let s = 3 * r.pow(2);
    println!("{}", s);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h> 
#define rep(i,n) for(long long i = 0; i < (long long)(n); i++)
#define per(i,n) for(long long i = (long long)(n-1);i >= 0;--i)
#define REP(i,s,t) for(long long i=s;i<t;i++)
#define PER(i,s,t) for(long long i=s;i>t;--i)
#define all(x) x.begin(),x.end()
#define sp(n) setprecision(n)
typedef long long ll;
using namespace std;
int main(){
  int n;
  cin>>n;
  char c='H';
  map<string,int> m;
  bool ans=true;
  rep(i,n){
    string s;
    cin>>s;
    if(i==0){
      c=s[s.size()-1];
    }
    if(m.count(s)){
      ans=false;
    }
    else{
      m[s]=1;
    }
    if(i>0&&s[0]!=c){
      ans=false;
    }
    c=s[s.size()-1];
  }
  if(ans){
    cout<<"Yes"<<endl;
  }
  else cout<<"No"<<endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>

using namespace std; 

int main()
{
	int a,b,h,m;
	scanf("%d %d %d %d",&a,&b,&h,&m);
	
	double hag,mag,gap,ans;
	hag=360.0*(((double)h+(double)m/60.0)/12.0);
	mag=360.0*((double)m/60.0);
	if(hag>mag) gap=hag-mag;
	else gap=mag-hag;
	if(gap>180.0) gap=360.0-gap;
	
//	if(hag==mag) printf("%d",(b-a>0)?b-a:a-b);
//	else
	
		ans=sqrt((double)(a*a+b*b)-(double)(2.0*a*b)*cos(gap*acos(-1.0)/180.0));
	
	
	//cout<<cos(gap*3.14159265/180.0)<<endl;
	printf("%.20lf\n",ans);
	
	return 0;
} 

Measured memory_bytes: 4320
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<list>
#include<set>
#include<map>
#include<utility>
#include<queue>


#define rep(i,x) for(ll i=0;i<(int)(x);i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=((int)(x));i>0;i--)

#define all(x) (x).begin(),(x).end()
#define SZ(x) ((int)(x).size())
#define INF 2e9

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;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

using namespace std;

int main()
{
    ll n;
    cin >> n;
    vector<ll> v(n);
    vector<ll> t;

    rep(i, n){
        cin >> v[i];
    }
    sort(all(v));
    reverse(all(v));
    v.push_back(-1);
    ll cnt = 1;
    rep(i, n){
        if(v[i]==v[i+1]){
            cnt++;
        }else{
            if(cnt>=2 && cnt <4){
                t.push_back(v[i]);
            }else if(cnt >= 4){
                t.push_back(v[i]);
                t.push_back(v[i]);
            }
            cnt = 1;
        }
        if(t.size()==2) break;
    }
    if(t.size()<2){
        cout << 0;
        return 0;
    }

    ll ans = t[0]*t[1];
    cout << ans << endl;
}

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

using namespace std;

int main(void) {
	string S, beforeS = "", afterS = "";
	int Q,input,count = 0;
	bool flag = false;
	char inputC;
	cin >> S;
	cin >> Q;
	for (int i = 0; i < Q; i++) {
		cin >> input;
		if (input == 2) {
			cin >> input;
			if (input == 1 && !flag) {
				cin >> inputC;
				beforeS += inputC;
			}else if (input == 1 && flag) {
				cin >> inputC;
				afterS += inputC;
			}else if (input == 2 && !flag) {
				cin >> inputC;
				afterS += inputC;
			}else {
				cin >> inputC;
				beforeS += inputC;
			}
		}
		else {
			count++;
			flag = !flag;
		}
	}
	reverse(beforeS.begin(), beforeS.end());
	S = beforeS + S + afterS;
	if (count % 2 == 1) {
		reverse(S.begin(), S.end());
	}
	cout << S << endl;
	return 0;
}

Measured memory_bytes: 1348
#include<stdio.h>
#include<stdlib.h>

int main()
{
        char O[50];
        char E[50];
        int i=0;
        int j=0;
        int ii=0;
        int jj=0;
        int count;

        for(;;)
        {
                scanf("%c",&O[i]);
                if((O[i]=='\0')|(O[i]=='\n')) break;
                i++;
        }
        for(;;)
        {
                scanf("%c",&E[j]);
                if((E[j]=='\0')|(E[j]=='\n')) break;
                        j++;
        }
        count=i+j;
        for(;;)
        {
                if(ii<i){
                        printf("%c",O[ii]);
                        ii++;
                }
                if(jj<j){
                        printf("%c",E[jj]);
                        jj++;
                }
                if(ii+jj>=count) break;
        }
        printf("\0\n");
        return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        long tempt = Long.parseLong(sc.next());
        long tempa = Long.parseLong(sc.next());
        for (int i = 0; i < n - 1; i++) {
            long t = Long.parseLong(sc.next());
            long a = Long.parseLong(sc.next());
            if (t >= tempt && a >= tempa) {
                tempt = t;
                tempa = a;
            } else {
                long ratiot = tempt / t;
                if (tempt % t != 0) {
                    ratiot++;
                }
                long ratioa = tempa / a;
                if (tempa % a != 0) {
                    ratioa++;
                }
                tempt = Math.max(ratiot, ratioa) * t;
                tempa = Math.max(ratiot, ratioa) * a;
            }
        }
        System.out.println(tempt + tempa);
    }
}

Measured memory_bytes: 21716
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pii pair<int, int>
#define eb emplace_back
#define all(v) v.begin(), v.end()
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep3(i, l, n) for (int i = l; i < (n); ++i)
#define sz(v) (int)v.size()
const int inf = 1e9 + 7;
const ll INF = 1e18;
#define abs(x) (x >= 0 ? x : -(x))
#define lb(v, x) (int)(lower_bound(all(v), x) - v.begin())
#define ub(v, x) (int)(upper_bound(all(v), x) - v.begin())
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { if (a > b) { a = b; return 1; } return 0; }
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { if (a < b) { a = b; return 1; } return 0; }
template<typename T> T gcd(T a, T b) { if (b == 0) return a; return gcd(b, a % b); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<typename T> T pow(T a, int b) { return b ? pow(a * a, b / 2) * (b % 2 ? a : 1) : 1; }
const int mod = 1000000007;
ll modpow(ll a, int b) { return b ? modpow(a * a % mod, b / 2) * (b % 2 ? a : 1) % mod : 1; }
template<class T> ostream& operator<<(ostream& os, const vector<T>& vec) { for (auto &vi: vec) os << vi << " "; return os; }
template<class T, class U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << p.F << " " << p.S; return os; }
template<class T> inline void add(T &a, int b) { a += b; if (a >= mod) a -= mod; }



void solve();

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

    int T;
    // cin >> T;
    T = 1;

    while (T--) {
        solve();
    }
}

int n;
vector<ll> a, acc;
ll dp[404][404];

ll dfs(int l, int r) { // まとまりが l, r のときの, すべてバラバラにするコスト
  if (l == r) return dp[l][r] = 0;
  if (dp[l][r] != INF) return dp[l][r];

  ll ret = INF;
  rep3(i, l, r) {
    chmin(ret, dfs(l, i) + dfs(i + 1, r));
  }
  ret += acc[r + 1] - acc[l];
  // cout << l << " " << r << " " << ret << endl;

  return dp[l][r] = ret;
}

// https://kyopro-friends.hatenablog.com/entry/2019/01/12/231035
void solve() {
  // L のように l, r でやりたくなるが, 連続でない
  // 逆から見る
  // 順方向を考えれば, 合体は端
  
  cin >> n;
  a.resize(n);
  rep(i, n) cin >> a[i];

  acc.resize(n + 1);
  rep(i, n) acc[i + 1] = acc[i] + a[i];

  fill_n(*dp, 404 * 404, INF);
  cout << dfs(0, n - 1) << endl;
  // rep(i, n) { rep(j, n) cout << dp[i][j] << " "; cout << endl; }
}


Measured memory_bytes: 1536
import sys

import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline


def main():
    H, W, K = map(int, readline().split())
    S = read().split()
    S = list(map(lambda x: x.decode('UTF-8'), S))

    A = np.zeros([H, W], dtype=np.int32)
    h_num = 0
    ih = []
    for h in range(H):
        ii = 0
        for w in range(W):
            if S[h][w] == "#":
                if ii != 0:
                    h_num += 1
                    A[h:, w:] = h_num
                else:
                    h_num += 1
                    A[h:, :] = h_num
                    ii += 1
                    ih.append(h)

    h_num = 0
    if A[0, 0] == 0:
        for h in range(ih[0]+1):
            ii = 0
            for w in range(W):
                if S[h][w] == "#":
                    if ii != 0:
                        h_num += 1
                        A[0:h, w:] = h_num
                    else:
                        h_num += 1
                        A[0:h, :] = h_num
                        ii += 1

    for h in range(H):
        print(' '.join(map(str, A[h])))


main()


Measured memory_bytes: 15024
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
int gcd(int x, int y){int r;while((r=x%y)!=0)x=y,y=r;return y;}

int main(void){

    long int n,m;
    scanf("%ld %ld",&n,&m);
    printf("%ld\n",(m>1?m-2:1)*(n>1?n-2:1));
}


Measured memory_bytes: 1692
#include<cstdio>
#include<algorithm>
using namespace std;
int n;
long long w[51], sum;
bool Pos(long long T) {
	int i, ss = 0;
	for (i = 1; i <= n; i++) {
		int t = (w[i] + T) % (n + 1);
		if (t == n)return false;
		ss += t;
	}
	if (ss == sum - T)return true;
	return false;
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%lld", &w[i]);
		sum += w[i];
	}
	for (long long T = max(0ll, sum - n*n); T <= sum; T++) {
		if (Pos(T)) {
			printf("%lld\n", T);
			return 0;
		}
	}
}

Measured memory_bytes: 128
#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
#define mp  std::make_pair
#define ll long long int
#define abs(n) ((n>0)?(n):((n)*(-1)))
#define CEIL(a,b) (((a) + ((b)-1)) / (b))
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define REP(i,n) FOR(i,0,(n)-1)
#define VREP_ll(v) for(std::vector<ll>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VREP_int(v) for(std::vector<int>::iterator itr = (v).begin(); itr != (v).end();itr++)
#define VALL(v) ((v).begin(),(v).end())
#define errln(v) cerr << (v) << endl;
#define println(v) cout << (v) << endl;

int main(int argc, const char * argv[]) {
	int n,buf;
	cin >> n;
	vector<int> v;
	REP(i,n){
		cin >> buf;
		v.push_back(buf);
	}
	sort(v.begin(),v.end());
	double ret=v[0];
	FOR(i,1,n-1){
		ret = (ret+v[i])/2;
	}
	println(ret);
	return 0;
}


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

int main()
{
	int n;
	cin>>n;
	
	int ans[n+1]={0};
	
	for(int x=1;x*x<=n;x++)
	{
		for(int y=1;y*y<=n;y++)
		{
			for(int z=1;z*z<=n;z++)
			{
				int val=x*x+y*y+z*z + x*y +y*z +z*x;
				if(val<=n)
				{
					ans[val]++;
				}
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		cout<<ans[i]<<endl;
	}
	return 0;
}

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

int main(){
  int n;
  cin >> n;
  int a[n];
  for (int i=0;i<n;i++){
    cin >> a[i];
  }
  int count = 0;
  for (int i=0;i<n-1;i++) {
    for (int j=n-1;j>i;j--) {
      if (a[j] < a[j-1]) {
        int tmp = a[j];
        a[j] = a[j-1];
        a[j-1] = tmp;
        count += 1;
      }
    }
  }
  cout << a[0];
  for (int i=1;i<n;i++){
    cout << ' ' << a[i];
  }
  cout << endl << count << endl;
}


Measured memory_bytes: 3096