akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
const int INF=1e9;

ll comb[51][51];

int main(){
    for(int i=0;i<=50;i++){
        for(int j=0;j<=i;j++){
            if(j==0||j==i){
                comb[i][j]=1;
            }else{
                comb[i][j]=comb[i-1][j-1]+comb[i-1][j];
            }
        }
    }
    int n,a,b;
    cin>>n>>a>>b;
    ll v[n];
    for(int i=0;i<n;i++){
        cin>>v[i];
        v[i]=-v[i];
    }
    sort(v,v+n);
    ll sum[n];
    sum[0]=-v[0];
    for(int i=1;i<n;i++){
        sum[i]=-v[i]+sum[i-1];
    }
    pair<ll,int> ans;
    ll num=0;
    ans={0,1};
    for(int i=a;i<=b;i++){
        ll res=1;
        int ub=upper_bound(v,v+n,v[i-1])-v;
        int lb=lower_bound(v,v+n,v[i-1])-v;
        res*=comb[ub-lb][i-lb];
        if(ans.first*i<ans.second*sum[i-1]){
            ans={sum[i-1],i};
            num=res;
        }else if(ans.first*i==ans.second*sum[i-1]){
            num+=res;
        }
    }
    cout<<fixed<<setprecision(25)<<(double)ans.first/ans.second<<endl;
    cout<<num<<endl;
}


Measured memory_bytes: 256
// copied by Nurstan Duisengaliev
// skatal
#include <bits/stdc++.h>
 
#define ll long long
#define all(x) x.begin(), x.end()
#define in insert
#define mp make_pair
#define F first
#define S second
#define ppf pop_front
#define pb push_back
#define ppb pop_back
#define pf push_front
#define pii pair <int, int>
#define boost() ios_base::sync_with_stdio(0), cin.tie(0)
#define sz(x) (int)x.size()
 
using namespace std;             
 
const int N = (int)2e5 + 123;
const int mod = (int)1e9 + 7;
const ll INF = (ll)1e18 + 7;
string rev (string a) {
	reverse (all (a));
	return a;
}
void solve () {
	string a;
	cin >> a;
	string f = "", s = "";
	for (int i = 0; i < sz (a) / 2; i ++) {
		f += a[i];
	}
	for (int i = sz (a) / 2 + 1; i < sz (a); i ++) s += a[i];
	if (rev (f) == f && rev (s) == s && rev (a) == a) cout << "Yes";
	else cout << "No";
}   	
 
main () {
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
	boost ();
	int TT = 1;
//    cin >> TT;
	while (TT --) {
		solve ();
	}
	return 0;	
}

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

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define RREP(i, n ,N) for(ll i = (N-1); i >= (n); i--)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;


ll N, W;
ll w[110], v[110];
ll dp[101010];
int main(){
	cin >> N >> W;
	REP(i,0,N){
		cin >> w[i] >> v[i];
	}
	REP(i,0,101010){
		dp[i] = inf;
	}
	dp[0]=0;
	REP(i,0,N){
		RREP(nv,0,100001){
			if(dp[nv] + w[i] > W) continue;
			dp[nv + v[i]] = min(dp[nv + v[i]], dp[nv] + w[i]);
		}
	}
	ll ans = 0;
	REP(v,0,100001){
		if(dp[v] <= W) ans = max(ans, v);
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}

int main()
{
    string s;
    cin >> s;
    ll ans = 0;
    rep(i, sz(s)){
        if(i % 2 == 0){
            if(s.at(i) == 'p'){
                ans--;
            }
        }
        else{
            if(s.at(i) == 'g'){
                ans++;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3760
package main

import (
	"fmt"
)

func main() {
	var a, b, c int
	fmt.Scan(&a, &b, &c)

	if a >= c || b >= c {
		fmt.Println("No")
		return
	}

	if 4*a*b < (c-a-b)*(c-a-b) {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


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

#define MOD 998244353

using lint = long long int;
using pii = std::pair<int, int>;

using std::vector;
vector<pii> ve;
bool check[220][220];
vector<int> cou[220][220];

lint combi(lint n, lint r) {
	lint ret = 1;
	for (int i = 1; i <= r; i++) {
		ret *= (n - i + 1);
	}
	for (int i = 1; i <= r; i++) {
		ret /= i;
	}
	return ret;
}
lint my_pow(lint a, lint b, lint mod) { //a^b % mod
	lint ret = 1;
	a %= mod;
	while (b != 0) {
		if (b % 2 == 0) {
			a = (a * a) % mod;
			b /= 2;
		}
		else {
			ret = (ret * a) % mod;
			b--;
		}
	}
	return ret;
}
lint make(lint n) {
	lint ret = my_pow(2, n, MOD);
	for (int i = 0; i < 3; i++) {
		ret = (ret - combi(n, i) + MOD) % MOD;
	}
	return ret;
}
bool is_in(pii x, pii y, pii z) {
	int xx = y.first - x.first;
	int yy = y.second - x.second;

	int t_x = (z.first - x.first);
	int t_y = (z.second - x.second);

	if (yy * t_x == t_y * xx) {
		return true;
	}
	return false;
}
int main(void) {
	int N;
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		ve.push_back(pii(t1, t2));
	}
	sort(ve.begin(), ve.end());
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (!check[i][j]) {
				check[i][j] = true;
				check[j][i] = true;
				for (int k = 0; k < N; k++) {
					if (is_in(ve[i], ve[j], ve[k])) {
						for (int l = 0; l < cou[i][j].size(); l++) {
							check[k][cou[i][j][l]] = true;
							check[cou[i][j][l]][k] = true;
						}
						cou[i][j].push_back(k);
					}
				}
			}
		}
	}

	lint ans = make(N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (cou[i][j].size() >= 3) {
				ans = (ans - make(cou[i][j].size()) + MOD) % MOD;
			}
		}
	}

	printf("%lld", ans);

	return 0;
}

Measured memory_bytes: 2048
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iostream>
using namespace std;
#define re register
#define ll long long
inline int gi()
{
	int f=1,sum=0;char ch=getchar();
	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();}
	return f*sum;
}
const int N=400010;
int t[N],a[N],n;
int main()
{
	n=gi();for(int i=1;i<=n;i++)t[a[i]=gi()]++;
	ll ans=0;
	for(int i=1;i<=n;i++)ans+=1ll*t[i]*(t[i]-1)/2;
	for(int i=1;i<=n;i++)printf("%lld\n",ans-(t[a[i]]-1));
	return 0;
}


Measured memory_bytes: 3712
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

typedef pair<int, int> sight;

int main()
{
  int hope[1000][100];
  int h, n, m;
  while(cin >> n >> m){
    if(n == 0 && m == 0) break;
    else{
      vector<sight> s;
      for(int i = 0; i < m; i++){
	s.push_back(sight(0, i));
      }
      for(int i = 0; i < n; i++){
	for(int j = 0; j < m; j++){
	  cin >> h;
	  s[j].first -= h;
	}
      }
      sort(s.begin(), s.end());
      for(int i = 0; i < m; i++){
	if(i == m - 1) 	cout << s[i].second + 1;
	else cout << s[i].second + 1 << " ";	
      }
      cout << endl;
    }
  }
}

Measured memory_bytes: 1200
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <numeric>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <cassert>
#include <cstdarg>
#include <sys/time.h>
#include <fstream>
//#include "cout.h"

using namespace std;

#define SZ(x) ((int)x.size())
#define MSET(x,a) memset(x, a, (int)sizeof(x))
#define PB push_back
#define VI vector < int >
#define PII pair < int, int >
#define 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 FIT(it,v) for (__typeof((v).begin()) it = (v).begin(); it != (v).end(); it++)
#define OUT(A) cout << #A << " = "<< (A) << endl
#define OUT2(A, B) cout << "(" << #A << ", " << #B << ") = (" << (A) << ", "<< (B) << ")" << endl
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }

#define present(c, e) ((c).find((e)) != (c).end())
#define cpresent(c, e) (find(ALL(c), (e)) != (c).end())



void init() {

}

void input() {

}

void solve() {
  string s;
  cin >> s;
  REP(i, SZ(s)) {
    if (s[i] == '1') cout << 9;
    else cout << 1;
  }
  cout <<endl;
}

int main() {
	init();
	input();
	solve();
	return 0;
}


Measured memory_bytes: 256
n, m, x = map(int, input().split())

c = []
a = []
for i in range(n):
    tmp = list(map(int, input().split()))
    c.append(tmp[0])
    a.append(tmp[1:])

BASE = 1000000000000000
ans = BASE
def dfs(idx, num_list):
    global ans
    global c
    global a
    if idx == n:
        tmp_c_ans = 0
        tmp_a_ans = [0 for i in range(m)]
        for c_idx, c_include in enumerate(num_list):
            if c_include == 1:
                tmp_c_ans += c[c_idx]
                for a_idx, a_score in enumerate(a[c_idx]):
                    tmp_a_ans[a_idx] += a_score
        if all([t >= x for t in tmp_a_ans]):
            ans = min(ans, tmp_c_ans)
    else:
        dfs(idx + 1, num_list + [1])
        dfs(idx + 1, num_list + [0])

dfs(0, [])

if ans == BASE:
    ans = -1
print(ans)

Measured memory_bytes: 9076
///
// File:  a.go
// Author: ymiyamoto
//
// Created on Fri May 25 00:02:20 2018
//
package main

import (
	"fmt"
)

var S string

func main() {
	fmt.Scan(&S)
	if len(S) < 4 {
		fmt.Println("No")
		return
	}

	if S[:4] == "YAKI" {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

class D{
public:
    long long a;
    long long b;
    long long c;
    long long d;
    
    bool operator < (const D& o) const {
        return (d < o.d);
    }
};

int main(int argc, char **argv)
{
    int N, M, Q;
    std::cin >> N >> M >> Q;

    std::vector<D> data(Q);

    for(int i = 0; i < Q; i++){
        std::cin >> data.at(i).a >> data.at(i).b >> data.at(i).c >> data.at(i).d;
    }

    /*
    std::sort(data.begin(), data.end());

    for(int i = 0; i < data.size(); i++){
        std::cout << data.at(i).a
                  << " "
                  << data.at(i).b
                  << " "
                  << data.at(i).c
                  << " "
                  << data.at(i).d
                  << std::endl;
    }
    */

    std::vector<int> A(N);
    for(int i = 0; i < N; i++){
            A.at(i) = 1;
    }
    long long m = 0;
    int pt = N - 1;
    for(;;){
        /*
        for(int i = 0; i < data.size(); i++){
            std::cout << " " << A.at(i);
        }
        std::cout << std::endl;
        */

        long long sum = 0;
        for(int i = 0; i < Q; i++){
            long long Ab = A.at(data.at(i).b-1);
            long long Aa = A.at(data.at(i).a-1);
            if(Ab - Aa == data.at(i).c){
                sum += data.at(i).d;
            }
        }
        m = std::max(sum, m);

        if(A.at(0) == M) break;
        
        if(A.at(N-1) < M){
            A.at(N-1) += 1;
        }else{
            int v;
            for(int i = N-1; i >= 0; i--){
                if(A.at(i) < M){
                    v = A.at(i) + 1;
                    break;
                }
            }
            for(int i = N-1; i >= 0; i--){
                if(A.at(i) == M){
                    A.at(i) = v;
                }else{
                    A.at(i) += 1;
                    break;
                }
            }
        }
    }

    std::cout << m << std::endl;
    
}


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

class Program {
    static void Main (string[] args) {
          

        string[] a = Console.ReadLine ().Split(' ');
        
        int b = int.Parse(a[0]);
        int c = int.Parse(a[1]);
        int d = 0;
        int[] atr = new int[b];

        int min = 999999999;

        for(int i=1;i<=b;i++){
            d = c + i -1;
            atr[i -1] = d;
            min = System.Math.Min(min,System.Math.Abs(d));
        }

        if(d < 0){
            min = min * -1;
        }
        int ans = 0;

        for(int i =0;i < atr.Length;i++){
            if(atr[i] != min){
                ans = ans + atr[i];
            }
        }

        Console.WriteLine(ans);
    }
}

Measured memory_bytes: 11092
n,m,x=map(int,input().split())
*a,=map(int,input().split())
cst_0=0
cst_n=0
for i in range(1,x):
	if (x-i) in a:
		cst_0 += 1
for i in range(x+1,n):
	if i in a:
		cst_n += 1
ans=min(cst_0,cst_n)
print(ans)
	

Measured memory_bytes: 3060
package main

import (
	"fmt"
)

func sort(list []rune, desc bool) {
	eNum := len(list)
	for i := eNum; i > 0; i-- {
		for j := 0; j < i-1; j++ {
			if desc {
				if list[j] < list[j+1] {
					list[j], list[j+1] = list[j+1], list[j]
				}
			} else {
				if list[j] > list[j+1] {
					list[j], list[j+1] = list[j+1], list[j]
				}
			}
		}
	}
}


func sortRune(s string, desc bool) string {
	r := []rune(s)
	sort(r, desc)
	return string(r)
}

func main() {
	var s, t string
	fmt.Scan(&s, &t)

	ss := sortRune(s, false)
	tt := sortRune(t, true)

	if ss < tt {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}

}

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

int main() {
  int N;
  string S;
  int p , q;
  cin >> N >> S;
  p = 0;
  q = 0;
  while(q < N - 2){
    if(S.at(q) == 'A'){
      if(S.at(q + 1) == 'B'){
        if(S.at(q + 2) == 'C'){
          p = p + 1;
        }
      }
    }
  q = q + 1;
  }
  cout << p << endl;
}



Measured memory_bytes: 256
/*input
7
6 7 8
8 8 3
2 5 2
7 8 6
4 6 8
2 3 4
7 5 1
*/
#include<bits/stdc++.h>
using namespace std;
#define maxim 2048
#define fn(i,n) for(long long i=0;i<n;i++)
#define fn1(i,n) for(long long i=1;i<n;i++)
#define ll long long
int main()
{
	ll n;
	cin>>n;
	ll a[n],b[n],c[n];
	cin>>a[0]>>b[0]>>c[0];
	fn1(i,n)
	{
		cin>>a[i]>>b[i]>>c[i];
		a[i]=a[i]+max(b[i-1],c[i-1]);
		b[i]=b[i]+max(a[i-1],c[i-1]);
		c[i]=c[i]+max(a[i-1],b[i-1]);
	}
	cout<<max(a[n-1],max(b[n-1],c[n-1]))<<endl;
}

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

using namespace std;

int main(){
	string s;
	cin >> s;
	if (s == "RRR") cout << "3\n";
	else if (s == "RRS" || s == "SRR") cout << "2\n";
	else if (s == "SSS") cout << "0\n";
	else cout << "1\n";
	return 0;
}


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

using namespace std;

int main(){
  int i=0,j,k;
  string str;
  cin >> str;
  while(1){
      str.pop_back();
      if(str.substr(0,str.size()/2) == str.substr(str.size()/2)){
        break;
      }
  }
  cout << str.size();
  return 0;
}

Measured memory_bytes: 256
;; -*- coding:utf-8 -*-

(eval-when (:compile-toplevel :load-toplevel :execute)
  (defparameter OPT
    #+swank '(optimize (speed 3) (safety 1))
    #-swank '(optimize (speed 3) (safety 0) (debug 0))))

(defmacro print-line (obj &optional (stream '*standard-output*))
  `(prog1 (princ ,obj ,stream) (terpri ,stream)))


;; Hauptteil

;; alexandria
(defun make-permutation (set)
  (labels ((%permute (set res)
             (if (null set)
                 (list res)
                 (loop for node in set
                       append (%permute (remove node set) (cons node res))))))
    (%permute set nil)))

(defmacro split-and-bind (arg-lst string &body body)
  (let ((pos1 (gensym "POS"))
	(pos2 (gensym "POS"))
	(str-evaled (gensym "STR")))
    (labels ((expand (arg-lst &optional (init-pos1 t))
	       (if (null arg-lst)
		   body
		   `((let* ((,pos1 ,(if init-pos1 0 `(1+ ,pos2)))
			    (,pos2 (position #\space ,str-evaled :start ,pos1 :test #'char=))
			    (,(car arg-lst) (parse-integer ,str-evaled :start ,pos1 :end ,pos2)))
		       ,@(expand (cdr arg-lst) nil))))))
      `(let ((,str-evaled ,string))
	 ,@(expand arg-lst)))))

(defun valid-p (path adja-mat)
  (cond ((null (cdr path)) t)
        ((not (eql 1 (aref adja-mat (first path) (second path)))) nil)
        (t (valid-p (cdr path) adja-mat))))

(deftype uint nil `(integer 0 ,(expt 10 9)))
(defun main ()
  (let* ((n (read))
         (m (read))
         (adja-mat (make-array (list n n) :element-type 'bit :initial-element 0)))
    (dotimes (i m)
      (split-and-bind (a b) (read-line)
        (setf (aref adja-mat (- a 1) (- b 1)) 1
              (aref adja-mat (- b 1) (- a 1)) 1)))
    (print-line
     (loop for path in (make-permutation (loop for i from 1 below n collect i))
           count (valid-p (cons 0 path) adja-mat)))))

#-swank(main)


Measured memory_bytes: 10852
#in1 = '4 5 8'
#in2 = ['1 1', '1 4', '1 5', '2 3', '3 1', '3 2', '3 4', '4 4']
#in1 = '10 10 20'
#in2 = ['1 1', '1 4', '1 9', '2 5', '3 10', '4 2', '4 7', '5 9', '6 4', '6 6', '6 7', '7 1', '7 3', '7 7', '8 1', '8 5', '8 10', '9 2', '10 4', '10 9']
#in1 = '1000000000 1000000000 0'
#h, w, n = map(int, in1.split())
h, w, n = map(int, input().split())

idx1 = 0
ab = [[0 for i in range(2)] for j in range(n)]

black_cnt = [0] * 10
black_cnt[0] = (h - 2) * (w - 2)

if n != 0:
    while idx1 < n:
        x = input().split()
        #x = in2[idx1].split()
        ab[idx1] = [int(x[0]), int(x[1])]
        idx1 += 1

    myDict = {}
    for abitem in ab:
        if abitem[0] < 3:
            sr = 0
        else:
            sr = abitem[0] - 3
        if abitem[0] > h - 3:
            lr = h - 2
        else:
            lr = abitem[0]
        if abitem[1] < 3:
            sc = 0
        else:
            sc = abitem[1] - 3
        if abitem[1] > w - 3:
            lc = w - 2
        else:
            lc = abitem[1]

        for nowRow in range(sr, lr):
            for nowCol in range(sc, lc):
                key = str(nowRow) + ',' + str(nowCol)
                if key in myDict:
                    myDict[key] += 1
                else:
                    myDict[key] = 1

    for bcnt in myDict.values():
        black_cnt[bcnt] += 1
        black_cnt[0]    -= 1

for item in black_cnt:
    print(item)


Measured memory_bytes: 144864
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define all(c) c.begin(), c.end()
#define endl "\n"
#define sz(u) (int)(u.size())
#define L(x)(2*x)
#define R(x)(2*x+1)
#define M(x,y)((x+y)/2)
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
void solve(){
int n;
    cin>>n;
    n%=10;
    if(n==2 || n==4 || n==5 || n==7 || n==9)
        cout<<"hon";
    else if(n==0 ||n==1 || n==6 || n==8)
        cout<<"pon";
    else
        cout<<"bon";
    }
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();

}



Measured memory_bytes: 3652
import java.util.*;
import java.util.function.*;
import java.math.*;
public class Main {
    public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		int N = Integer.valueOf(s.next());
		int[] ret = new int[4];
		for(int i = 0; i < N; i++) {
			String now = s.next();
			switch(now) {
			case "AC":
				ret[0]++;
				break;
			case "WA":
				ret[1]++;
				break;
			case "TLE":
				ret[2]++;
				break;
			case "RE":
				ret[3]++;
				break;
			}
		}
		
		System.out.println("AC x " + ret[0]);
		System.out.println("WA x " + ret[1]);
		System.out.println("TLE x "+ ret[2]);
		System.out.println("RE x " + ret[3]);
	}
}

Measured memory_bytes: 58192
from sys import stdin
import math

n = stdin.readline().rstrip()

v = [int(x) for x in stdin.readline().rstrip().split()]
c = [int(x) for x in stdin.readline().rstrip().split()]

# print(n)
# print(v)
# print(c)

sum = 0
for i in range(len(v)):
    # print(i)
    if c[i] < v[i]:
        sum += v[i] - c[i]

print(sum)


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
const int    INF = 100000000;
const double EPS = 1e-10;
const int    MOD = 1000000007;
using namespace std;
typedef pair<int,int> P;

int n;
int dp[2][370][370];
struct info{
	int a, b, c;
} x[1000];

bool check(const info& left, const info& right)	{
	if(left.b < right.b) return true;
	else return false;
}

void solve(){
	rep(u,2) rep(i,370) rep(j,370) dp[u][i][j] = 0;
	rep(i,n){
		int a, b, c;
		cin >> a >> b >> c;
		x[i] = (info){a,b,c};
	}
	sort(x,x+n,check);
	int ho = 0, ge = 1;
	rep(i,n){
		int a = x[i].a, b = x[i].b, c = x[i].c;
		for(int j = 0; j < a; j++){
			for(int k = 0; k < 370; k++){
				dp[ge][b][k] = max(dp[ge][b][k],dp[ho][j][k]+c);
				dp[ge][k][b] = dp[ge][b][k];
			}
		}
		rep(j,370) rep(k,370) dp[ho][j][k] = dp[ge][j][k];
		swap(ho,ge);
	}
	int ans = 0;
	rep(u,2) rep(i,370) rep(j,370) ans = max(ans,dp[u][i][j]);
	cout << ans << endl;
}

int main(){
	while(cin >> n){
		if(n == 0) break;
		solve();
	}
}

Measured memory_bytes: 2256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    int sum = 0;
    rep(i, M) {
        int A; cin >> A;
        sum += A;
    }
    if (N - sum >= 0) {
        cout << N - sum << endl;
    } else {
        cout << -1 << endl;
    }

    return 0;
}


Measured memory_bytes: 3652
N,X=map(int,input().split())
L=list(map(int,input().split()))


if L[0]>X:
    print(1)
else:
    D=0
    i=0
    count=1
    while D<=X and i<=N-1:
        if D+L[i]<=X:
            D+=L[i]
            i+=1
            count+=1
        else:
            break
    print(count)
    

Measured memory_bytes: 3060
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

#define pb push_back
#define ri(x) scanf("%d",&x)
#define rii(x,y) ri(x),ri(y)
#define ms(obj,val) memset(obj,val,sizeof(obj))
#define ms2(obj,val,sz) memset(obj,val,sizeof(obj[0])*sz)
#define FOR(i,f,t) for(int i=f;i<(int)t;i++)
#define FORR(i,f,t) for(int i=f;i>(int)t;i--)

typedef long long ll;
typedef vector<int> vi;

const int MAXN=1e5;

int x, gcd = 0;
int N,K,A[MAXN];

int f(int a, int b) {return b ? f(b, a % b) : a;}

int main() {
	rii(N,K);
	FOR(i,0,N) ri(A[i]);
	FOR(i,0,N) gcd = f(gcd,A[i]);
	FOR(i,0,N) x = max(x, A[i]);
	printf("%sPOSSIBLE\n", K <= x && K % gcd == 0 ? "" : "IM");
}


Measured memory_bytes: 640
N = int(input())
A = list(map(int,input().split()))
B = list(A)
B.insert(0,0)
B.append(0)

S = 0
Slist = []
for i in range(len(B)-1):
    distance = abs(B[i] - B[i+1])
    Slist.append(distance)
    S += distance

for j in range(len(A)):
    print(S + abs(B[j]-B[j+2]) - Slist[j] - Slist[j+1])



Measured memory_bytes: 14040
package main

import (
	"fmt"
)

var N, A int
var dp [50 + 1][50 + 1][2500 + 1 + 50]int

func solve2(n, sum int, xs []int) (cnt int) {
	if dp[n][len(xs)][sum] != 0 {
		return dp[n][len(xs)][sum]
	}
	if len(xs) == 0 {
		if sum == A*n && n > 0 {
			cnt = 1
		}
		return
	}
	cnt += solve2(n, sum, xs[1:])
	//	if A*(n+1) == sum+xs[0] {
	//		cnt++
	//	}
	cnt += solve2(n+1, sum+xs[0], xs[1:])
	dp[n][len(xs)][sum] = cnt
	return cnt
}

var xs []int

//func solve(i, n, sum int) (cnt int) {
//	if dp[i][n][sum] != 0 {
//		return dp[i][n][sum]
//	}
//	if i == N {
//		if sum == A*n && n > 0 {
//			cnt = 1
//		}
//		return
//	}
//	cnt += solve(i+1, n, sum)
//	//	if A*(n+1) == sum+xs[0] {
//	//		cnt++
//	//	}
//	cnt += solve(i+1, n+1, sum+xs[i])
//	dp[i][n][sum] = cnt
//	return cnt
//}

func solve(_i, _n, _sum int) (cnt int) {
	dp[0][0][0] = 1
	for i := 0; i < N; i++ {
		for n := 0; n < N; n++ {
			for k := 0; k <= 2500; k++ {
				dp[i+1][n][k] += dp[i][n][k]
				dp[i+1][n+1][k+xs[i]] += dp[i][n][k]
			}
		}
	}

	for n := 1; n <= N; n++ {
		cnt += dp[N][n][A*n]
	}
	return
}

func main() {
	fmt.Scan(&N, &A)
	xs = make([]int, N)
	for i, _ := range xs {
		fmt.Scan(&xs[i])
	}
	fmt.Println(solve(0, 0, 0))
}


Measured memory_bytes: 52096
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
using namespace std;

char picture[110][110];

int main() {
	int h, w;
	cin >> h >> w;
	for (int i = 0; i <= h + 1; i++) {
		for (int j = 0; j <= w + 1; j++) {
			picture[i][j] = '#';
		}
	}
	for (int i = 1; i <= h; i++) {
		for (int j = 1; j <= w; j++) {
			cin >> picture[i][j];
		}
	}
	for (int i = 0; i <= h + 1; i++) {
		for (int j = 0; j <= w + 1; j++) {
			cout << picture[i][j];
		}
		cout << endl;
	}
	return 0;
}

Measured memory_bytes: 256
func readInt() -> Int {
    return Int(readLine()!)!
}

func readInts(separator: String.Element = " ") -> [Int] {
    return readLine()!.split(separator: separator).map { Int($0)! }
}

func mainA() {
    let x = readInt()
    print(x == 0 ? 1 : 0)
}
mainA()

Measured memory_bytes: 7752
//
//  respect the past, embrace the future
//

#include  <algorithm>
#include  <iostream>
#include  <climits>
#include  <cstdlib>
#include  <cstring>
#include  <cmath>
#include  <cstdio>
#include  <unordered_map>
#include  <map>
#include  <set>
#include  <stack>
#include  <string>
#include  <vector>
#include  <queue>

using namespace :: std;

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

#define W (ll) (1e1 + 7)
#define N (ll) (2e6 + 7)
#define M (ll) (1e9 + 7)
#define INF (ll) (2e18)
#define int long long
#define F first
#define S second

inline void fastInputOutput () {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
}

inline void ReadWriteFromFile () {
  freopen("../in.txt", "r", stdin);
  freopen("../out.txt", "w", stdout);
}

int32_t main (int32_t argc, char *argv[]) {
  fastInputOutput();
  // ReadWriteFromFile();
  
  int a, b;
  cin >> a >> b;
  int n = 1, ans = 0;
  while (n < b) {
    n = n + a - 1;
    ans++;
  }
  cout << ans;
}

Measured memory_bytes: 256
N, X = map(int,input().split())

m = []
m_min = 9999999
sum = 0
for i in range(N):
    m.append(int(input()))

    sum += m[i]

    if m[i] < m_min:
        m_min = m[i]

#最低一個ずつ作ったときのあまり
Z = X - sum

#あまりのお菓子のもとで作れるドーナツ＋N（最低1個ずつ作るため）
print(Z//m_min + N)



Measured memory_bytes: 38256
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools, os, pdb
sys.setrecursionlimit(10**7)
from queue import PriorityQueue
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def _I(): return int(sys.stdin.readline())
def _F(): return float(sys.stdin.readline())
def _pf(s): return print(s, flush=True)
def perr(s): return print(s, file=sys.stderr)
"""
"""
N = _I()
A = LI()

A = [[i, idx+1] for idx, i in enumerate(A)]
#  print(A)
A.sort(key=lambda x: x[0])
A = [str(i[1]) for i in A]
print(' '.join(A))


Measured memory_bytes: 113068
from itertools import permutations


n = int(input())
A = [i for i in range(1, n+1)]
P = tuple(map(int, input().split()))
Q = tuple(map(int, input().split()))
if P == Q:
    print(0)
    exit()
cnt = 0
for v in permutations(A, n):
    cnt += 1
    if v == P:
        a = cnt
    elif v == Q:
        b = cnt
print(abs(a - b))



Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
const int INF = 1001001001;

int main() {
int N,D;
cin >> N >> D;
int kanshi = 2*D+1;
if (N % kanshi == 0) cout << N/kanshi << endl;
else cout << N/kanshi+1 << endl;;

return 0;
}


Measured memory_bytes: 256
using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] arg){
        //string[] input = Console.ReadLine().Split(' ');
        int input = int.Parse(Console.ReadLine()); 
        int n = input % 10;

        switch(n){
            case 2:
            case 4:
            case 5:
            case 7:
            case 9:
                Console.WriteLine("hon");
                return;

            case 3:
                Console.WriteLine("bon");
                return;

            default:
                Console.WriteLine("pon");
                return;
        }
    }
}


Measured memory_bytes: 27492
import sys
H,W = [int(i) for i in input().split()]
A = [list(input().strip()) for j in range(H)]

q = [(0,0)]
while q:
  h,w = q.pop()
  if (h,w) == (H-1,W-1):
    A[h][w] = '.'
    break
  for dh,dw in [(1,0),(0,1)]:
    nh,nw = h+dh,w+dw
    if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '#':
      q.append((nh,nw))
      A[h][w] = '.'
      break
  else:
    print('Impossible')
    sys.exit()

for h in range(H):
  for w in range(W):
    if A[h][w] == '#':
      print('Impossible')
      sys.exit()
print('Possible')

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


int main(){
  int n,k;
  cin>>n>>k;
  vector<long long> vec(n);
  long long ans=0;
  
  rep(i,n){cin>>vec.at(i);}
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());
  if(k<n) {
    for(int i=k;i<n;i++)
    ans+=vec.at(i);
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

void main_()
{
    ll L, R;
    cin >> L >> R;

    ll ans = numeric_limits<ll>::max();
    if (R - L > 2018) {
        ans = 0;
    } else {
        for (ll i = L; i <= R - 1; ++i) {
            for (ll j = i + 1; j <= R; ++j) {
                ans = min(ans, i * j % 2019);
            }
        }
    }

    cout << ans << endl;
}
int main()
{
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);
    main_();
    return 0;
}


Measured memory_bytes: 256
import sys
N = int(input())
li = []
if N == 1:
    a = list(map(int,input().split()))
    print(1)
    sys.exit()   

for i in range(N):
    a = list(map(int,input().split()))
    li.append(a)

cross = []

##計算量に余裕があるので全探索します
for i in range(N):
    for j in range (i+1, N):
        a = [li[j][0]-li[i][0],li[j][1]-li[i][1]]
        if a[0] <= 0 and a[1] <= 0:
            b = [abs(li[j][0]-li[i][0]),abs(li[j][1]-li[i][1])]
            cross.append(b)
        elif a[0] < 0 and a[1] >= 0:
            c = li[j][1]-li[i][1]
            b = [abs(li[j][0]-li[i][0]),-c]
            cross.append(b) ####
        else:
            cross.append(a) 
lencross = len(cross)

res = 0
ans = []

for i in range (lencross):
    res = 0
    for j in range (lencross):
        if cross[i] == cross[j]:
            res += 1
    ans.append(res)
reduce = max(ans)

print(N - reduce)

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

const int N = 1e+6 + 5;
const long long mod = 1e+9 + 7;

long long gcd(long long a, long long b, long long& x, long long& y) {
	if (a == 0) 
	{
		x = 0; y = 1;
		return b;
	}
	long long x1, y1;
	long long d = gcd(b % a, a, x1, y1);
	x = y1 - (b / a) * x1;
	y = x1;
	return d;
}

long long get(long long a)
{
	long long x, y;
	long long d = gcd(a, mod, x, y);
	return (x % mod + mod) % mod;
}

long long fact(long long n)
{
	long long res = 1;
	for (int i = 1; i <= n; i++)
	{
		res *= i;
		res %= mod;
	}
	return res;
}

long long rfact(long long n)
{
	return get(fact(n));
}

void solve()
{
	long long x, y;
	cin >> x >> y;

	if (2 * y - x < 0 || (2 * y - x) % 3 != 0 || 2 * x - y < 0 || (2 * y - x) % 3 != 0)
	{
		cout << 0;
		return;
	}

	long long a = (2 * y - x) / 3;
	long long b = (2 * x - y) / 3;

	long long n = a + b, m = a;
	cout << (((fact(n) * rfact(n - m)) % mod) * rfact(m)) % mod;
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	//freopen("file.in", "r", stdin);//freopen("file.out", "w", stdout);

	int t = 1;
	//cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define M 1000000007
using namespace std;
int main() {
    string s; cin >> s;
    long long f[100002][4] = {};
    f[0][0] = 1;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == '?') f[i+1][0] = (3 * f[i][0]) % M;
        else f[i+1][0] = f[i][0];
        for (int j = 1; j < 4; j++)
            if (s[i] == '?')
                f[i+1][j] = (3 * f[i][j] + f[i][j-1]) % M;
            else if (s[i] == "ABC"[j-1])
                f[i+1][j] = (f[i][j] + f[i][j-1]) % M;
            else f[i+1][j] = f[i][j];
    }
    cout << f[s.size()][3] << endl;
}


Measured memory_bytes: 3584
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int A, N;
  cin >> A >> N;
  vector<string> num(A);
  for ( int i = 0; i < A; i++) {
    cin >> num.at(i);
  }
  for(int i = 0; i < N + 2; i++) {
    cout << "#";
  }
  cout << "" << endl;
  for (int i = 0; i < A; i++) {
    cout << "#" << num.at(i) << "#" << endl;
  }
  for(int i = 0; i < N + 2; i++) {
    cout << "#";
  }
  cout << "" << endl;

}

Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <list>
#define debug(x) cout << #x << ": " << (x) << endl
#define INF 1000000007
using namespace std;

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> P;
typedef vector<int> V;

bool isValidPoint(const P& p, int h, int w){
    return p.first > 0 && p.second > 0 &&
        p.first + 2 <= h && p.second + 2 <= w;
}

vector<ull> solve(ull h, ull w, const vector<P>& ps){
    vector<ull> res(10, 0);
    map<P, int> squares;

    for(P p : ps){
        for(int i = 0; i < 3; i++){
            for(int j = 0; j < 3; j++){
                int a = p.first;
                int b = p.second;
                P q = make_pair(a - i, b - j);
                if(isValidPoint(q, h, w)){
                    squares[q]++;
                }
            }
        }
    }

    for(auto kv : squares){
        res[kv.second]++;
        // cout << kv.first.first << ", " << kv.first.second << ": " << kv.second << endl;
    }
    ull s = 0;
    for(int i = 1; i < 10; i++){
        s += res[i];
    }
    res[0] = (h - 2) * (w - 2) - s;

    return res;
}

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

    ull h, w, n;
    cin >> h >> w >> n;
    vector<P> ps(n);
    for(int i = 0; i < n; i++){
        int a, b;
        cin >> a >> b;
        ps[i] = make_pair(a, b);
    }

    const vector<ull>& res = solve(h, w, ps);
    for(auto j : res){
        cout << j << endl;
    }

    return 0;
}


Measured memory_bytes: 43264
a,op,b=input().split()
while op != "?":
	a,b=int(a),int(b)
	if op=="+":
		print(a+b)
	elif op=="-":
		print(a-b)
	elif op=="*":
		print(a*b)
	else :
		print(a//b)
	a,op,b=input().split()


Measured memory_bytes: 5600
import sys
from bisect import *
from heapq import *
from collections import *
from itertools import *
from functools import *

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()

S = '1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51'
A = list(map(int, S.replace(' ', '').split(',')))
print(A[int(input()) - 1])

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,m,ans=0;
  cin >> n >> m;
  long long l[m],r[m],ruiseki[n+10]={};
  for(int i=0;i<m;i++){
    cin >> l[i] >> r[i];
    ruiseki[l[i]-1]++;
    ruiseki[r[i]]--;
  }
  for(int i=0;i<n;i++){
    if(ruiseki[i]==m){
      ans++;
    }
    ruiseki[i+1]+=ruiseki[i];
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2560
#include<bits/stdc++.h>
using namespace std;
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type,less<T>, rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define ff first
#define ss second

int main()
{
    ll a, b, g;
    cin >> a >> b;
    g = __gcd(a, b);

    ll i, ans = 1;

    for(i = 2; i <= sqrt(g); i++)
    {
        if((g%i) == 0)
        {
            while(g%i == 0)
                g /= i;
            ans++;
        }
    }

    if(g > 1)
        ans++;
    cout << ans;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<utility>
#include<cmath>
#include<climits>
#include<queue>
#include<stack>
#include<numeric>
#include<set>
#include<iomanip>
using namespace std;


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



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

  vector<int> a(n);
  rep(i,n) cin >> a[i];

  ll x1 = 0;
  rep(i, n){
    if(i % 2 == 1){
      x1 -= a[i];
    } else {
      x1 +=  a[i];
    }
  }

  vector<int> ans(n);
  ans[0] = x1;
  for(int i = 1; i < n; ++i){
    ans[i] = 2 * a[i - 1] - ans[i - 1];
  }

  rep(i, n) cout << ans[i] << " ";
  cout << endl;
}


Measured memory_bytes: 2048
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
int main(){
  int N,K;
  cin >> N >> K;
  vector<ll> x(N);
  for(int i = 0;i < N;i++)cin >> x[i];

  if(N == 1)cout << abs(x[0]) << endl;
  else{
    ll ans = 2 * 1e9;
    for(int i = 0;i < N;i++){
      if(i + K > N)break;
      else{
        ll d = x[i+K-1] - x[i] + min(abs(x[i+K-1]),abs(x[i]));
        ans = min(ans,d);
      }
    }

    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 1024
a, b, k = map(int, input().split())
if a + k <= b - k:
    l = [x for x in range(a, min(b, a + k))]
    r = [x for x in range(b, max(a, b - k), -1)]
    r = r[::-1]
    lr = l + r
else:
    lr = [x for x in range(a, b + 1)]
for x in lr:
    print(x)

Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
namespace IO
{
    char ibuf[(1<<21)+1],obuf[(1<<21)+1],st[15],*iS,*iT,*oS=obuf,*oT=obuf+(1<<21);
	inline char Get()
	{
        return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);
    }
    inline void Flush()
	{
        fwrite(obuf,1,oS-obuf,stdout);
        oS=obuf;
    }
    inline void Put(char x)
	{
        *oS++=x;
        if(oS==oT)
			Flush();
    }
   	inline int read()
	{
	   	register int x=0;
		register char ch=Get();
    	while(ch>'9'||ch<'0')
    		ch=Get();
    	while(ch>='0'&&ch<='9')
       		x=(x<<3)+(x<<1)+(ch^48),ch=Get();
       	return x;
	}
    inline void write(int x)  
	{  
		register int top=0;
    	while(x) 
			st[++top]=(x%10)+48,x/=10;
   		while(top)
			Put(st[top--]);
	}
}
using namespace IO;
const int N=200001,M=N<<3;
struct Edge
{
    int u,v,w,Next;
    Edge(){}
    Edge(int U,int V,int W,int NEXT)
    {
        u=U,v=V,w=W,Next=NEXT;
    }
    bool operator<(Edge a)const
    {
            return w<a.w;
    }
}edge[M];
int head[N],tot,f[N],d[N];
inline void add(int x,int y,int z)
{
    edge[++tot]=Edge(x,y,z,head[x]),head[x]=tot;
}
int find(int x)
{
    return x==f[x]? x:f[x]=find(f[x]);
}
bool cmp(int x,int y)
{
    int fx=find(x),fy=find(y);
    if(fx==fy)
        return false;
    if(fy>fx)
        f[fy]=fx;
    else
        f[fx]=fy;
    return true;
}
int main()
{
    register int n=read(),q=read();
    memset(d,0x3f,sizeof d);
    for(register int i=1,a,b,c;i<=q;++i)
    {
        a=read(),b=read(),c=read();
        add(a,b,c);
        d[a]=min(d[a],c+1),d[b]=min(d[b],c+2);
    }
    for(register int i=0;i<n;++i)
        d[i]=min(d[i],d[(i-1+n)%n]+2);
    for(register int i=0;i<n;++i)
        d[i]=min(d[i],d[(i-1+n)%n]+2);
    for(register int i=0;i<=n;++i)
        add(i,(i+1)%n,d[i]);
    sort(edge+1,edge+1+tot);
    for(register int i=1;i<n;++i)
		f[i]=i;
    register int lt=n;
	long long ans=0;
    for(register int i=1;i<=tot&&lt>1;++i)
        if(cmp(edge[i].u, edge[i].v))
            ans+=edge[i].w,--lt;
    return printf("%lld",ans),0;
}

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

using namespace std;

int main(void) {
	const string Male = "Male";
	const string Female = "Female";
	const string Vacant = "Vacant";
	int N;
	string ls, rs;
	cin >> N;
	int l = 0, r = N - 1;
	cout << 0 << endl;
	cin >> ls;
	cout << (N - 1) << endl;
	cin >> rs;
	int m = 0;
	int rest = 18;
	while(l < r && ls != Vacant && rs != Vacant) {
		int m = (l + r) / 2;
		cout << m << endl;
		--rest;
		string s;
		cin >> s;
		if(((m - l) % 2 == 0) != (s == ls)) {
			r = m;
			rs = s;
		} else {
			l = m;
			ls = s;
		}
	}
	for(int i = 0; i < rest; ++i) {
		string s;
		cout << 0 << endl;
		cin >> s;
	}
	return 0;
}



Measured memory_bytes: 852
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<tuple>
#include<map>
#include<queue>
#include <math.h>
#define rep(i, n) rep2(i,0,n)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
typedef long long ll;
using namespace std;
 
int main() {
	ll n;
	cin >> n;
	ll ans=2*n;
	rep2(i,1,2*sqrt(n)) {
		if (n%i == 0) ans = min(ans,i + n / i);
	}
	cout << ans-2 << endl;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cmath>
#include <iostream>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

constexpr static int MAXN = 3e5 + 10;
constexpr static int MAXL = 1e5 + 10;
constexpr static int N1 = (1 << 9);

int n;
int v[MAXN], w[MAXN];
int dp[N1][MAXL];

int dfs(int i, int vsum, int wsum, int L) {
    if (i < N1)
        return dp[i][L - wsum] + vsum;
    int r = dfs(i >> 1, vsum, wsum, L);
    if (wsum + w[i] <= L)
        r = max(r, dfs(i >> 1, vsum + v[i], wsum + w[i], L));
    return r;
}

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

    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> v[i] >> w[i];

    for (int i = 1; i < N1; i++) {
        for (int j = 0; j < MAXL; j++) {
            dp[i][j] = dp[i >> 1][j];
            if (j > 0)
                dp[i][j] = max(dp[i][j], dp[i][j - 1]);
            if (j >= w[i])
                dp[i][j] = max(dp[i][j], dp[i >> 1][j - w[i]] + v[i]);
        }
    }

    int q;
    cin >> q;
    while (q--) {
        int i, L;
        cin >> i >> L;
        cout << dfs(i, 0, 0, L) << '\n';
    }
}


Measured memory_bytes: 204884
#include <stdio.h>

int main(){
	int n,x1;
	
	scanf("%d",&n);
	
	//10で割った余りがx桁目
	x1 = n % 10;
	if(x1 == 2 || x1 == 4 || x1 == 5 || x1 == 7 || x1 == 9){
		printf("hon");
	}
	else if(x1 == 0|| x1 == 1 || x1 == 6|| x1 == 8){
		printf("pon");
	}
	else printf("bon");

	return 0;
}


Measured memory_bytes: 1732
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repr(i, n) for (int i = (n); i >= 0; --i)
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define FORR(i, m, n) for (int i = (m); i >= (n); --i)
#define equals(a, b) (fabs((a) - (b)) < EPS)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
const ll mod = 1000000007;
//const ll mod = 998244353;
const int inf = 1e9 + 10;
const ll INF = 1e18;
const ld EPS = 1e-10;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
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 (a>b) { a=b; return 1; } return 0; }



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

  ll n;
  cin >> n;
  vector<ll> a(n);
  rep(i, n) cin >> a[i];

  vector<ll> ans(n, 0);
  ll res = 0;
  vector<ll> idx, v;
  rep(i, n) {
    if (a[i] > res) {
      idx.push_back(i);
      v.push_back(res);
      res = a[i];
    }
  }
  reverse(idx.begin(), idx.end());
  reverse(v.begin(), v.end());
  ll m = idx.size();
  priority_queue<ll> pq;
  rep(i, n) pq.push(a[i]);
  ll cnt = 0;
  rep(i, m) {
    if (i) ans[idx[i]] += cnt * (v[i - 1] - v[i]);
    while (!pq.empty() && pq.top() != v[i]) {
      ll maxa = pq.top();
      pq.pop();
      ans[idx[i]] += maxa - v[i];
      cnt++;
    }
  }
  rep(i, n) cout << ans[i] << '\n';




  
  return 0;
}

Measured memory_bytes: 5100
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define gpf(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

ll n, e, T;
ll x[110000], f[110000];
ll ans;

int main(){
	scanf("%lld%lld%lld", &n, &e, &T);
	rep(i, 1, n) scanf("%lld", x + i);
	ll tmn = 1ll << 60;
	int j = 1;
	rep(i, 1, n){
		while (j <= n && (x[i] - x[j]) * 2 > T){
			tmn = min(tmn, f[j - 1] - 2 * x[j]);
			j++;
		}
		f[i] = f[i - 1] + T;
		f[i] = min(f[i], f[j - 1] + T);
		f[i] = min(f[i], tmn + 2 * x[i]);
	}
	printf("%lld\n", f[n] + e);
	return 0;
}

Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>    
#include<cmath>
#include<map>
#include<vector>
#include<math.h>
#include<stdio.h>
#include<queue>
#include<tuple>
#include<cassert>
#define int long long
using namespace std;
signed main() {
	for(int d=0;d<10;d++){
	int n, k, a = 0, sum = 0; string s; 
	cin >> n >> k;
string aa[213456], test[213456];
	if(n==0&&k==0){return 0;}
	for (int h = 0; h < n; h++) {
		cin >> s; aa[h] = s;
	}
	if (k == 2) {
		for (int h = 0; h < n; h++) {
			for (int i = h + 1; i < n; i++) {
				test[a] = aa[h] + aa[i]; a++;
				test[a] = aa[i] + aa[h]; a++;
			}
		}
	}
	if (k == 3) {
		for (int h = 0; h < n; h++) {
			for (int i = h + 1; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					test[a] = aa[h] + aa[i] + aa[j]; a++;
					test[a] = aa[h] + aa[j] + aa[i]; a++;
					test[a] = aa[i] + aa[h] + aa[j]; a++;
					test[a] = aa[i] + aa[j] + aa[h]; a++;
					test[a] = aa[j] + aa[h] + aa[i]; a++;
					test[a] = aa[j] + aa[i] + aa[h]; a++;
				}
			}
		}
	}
	if (k == 4) {
		for (int h = 0; h < n; h++) {
			for (int i = h + 1; i < n; i++) {
				for (int j = i + 1; j < n; j++) {
					for (int k = j + 1; k < n; k++) {
						test[a] = aa[h] + aa[i] + aa[j] + aa[k]; a++;
						test[a] = aa[h] + aa[i] + aa[k] + aa[j]; a++;
						test[a] = aa[h] + aa[j] + aa[i] + aa[k]; a++;
						test[a] = aa[h] + aa[j] + aa[k] + aa[i]; a++;
						test[a] = aa[h] + aa[k] + aa[i] + aa[j]; a++;
						test[a] = aa[h] + aa[k] + aa[j] + aa[i]; a++;
						test[a] = aa[i] + aa[h] + aa[j] + aa[k]; a++;
						test[a] = aa[i] + aa[h] + aa[k] + aa[j]; a++;
						test[a] = aa[i] + aa[j] + aa[h] + aa[k]; a++;
						test[a] = aa[i] + aa[j] + aa[k] + aa[h]; a++;
						test[a] = aa[i] + aa[k] + aa[h] + aa[j]; a++;
						test[a] = aa[i] + aa[k] + aa[j] + aa[h]; a++;
						test[a] = aa[j] + aa[h] + aa[i] + aa[k]; a++;
						test[a] = aa[j] + aa[h] + aa[k] + aa[i]; a++;
						test[a] = aa[j] + aa[i] + aa[h] + aa[k]; a++;
						test[a] = aa[j] + aa[i] + aa[k] + aa[h]; a++;
						test[a] = aa[j] + aa[k] + aa[h] + aa[i]; a++;
						test[a] = aa[j] + aa[k] + aa[i] + aa[h]; a++;
						test[a] = aa[k] + aa[h] + aa[i] + aa[j]; a++;
						test[a] = aa[k] + aa[h] + aa[j] + aa[i]; a++;
						test[a] = aa[k] + aa[i] + aa[h] + aa[j]; a++;
						test[a] = aa[k] + aa[i] + aa[j] + aa[h]; a++;
						test[a] = aa[k] + aa[j] + aa[h] + aa[i]; a++;
						test[a] = aa[k] + aa[j] + aa[i] + aa[h]; a++;
					}
				}
			}
		}
	}
	sort(test, test + a);
	for (int h = 1; h < a; h++) {
		if (test[h - 1] == test[h]) {
			sum++;
		}
	}
	cout << a - sum << endl;
	}
}


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

int main() {
    ll n,k,i,s=0,l; vector<ll>a; cin>>n>>k;
    for(i=0;i<n;i++) {cin>>l; a.pb(l);}
    sort(a.begin(),a.end());
    for(i=0;i<k;i++) {s+=a[i];} cout<<s;
    return 0;
}

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

int N, M, R, A[202][202], city[10];
int ans = 1e9;

int main() {
    scanf("%d %d %d", &N, &M, &R);
    for(int i=0; i<R; i++) scanf("%d", city+i);
    sort(city, city + R);
    for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) A[i][j] = 1e9;
    for(int i=0, x, y, z; i<M; i++) {
        scanf("%d %d %d", &x, &y, &z);
        A[x][y] = A[y][x] = z;
    }
    for(int k=1; k<=N; k++) for(int i=1; i<=N; i++) for(int j=1; j<=N; j++) A[i][j] = min(A[i][j], A[i][k] + A[k][j]);
    do {
        int cnt = 0;
        for(int i=0; i<R-1; i++) cnt += A[city[i]][city[i+1]];
        ans = min(ans, cnt);
    } while(next_permutation(city, city+R));
    printf("%d\n", ans);
}


Measured memory_bytes: 384