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

typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<ld,ld> pdd;
typedef vector<ll> vll;
typedef vector<ld> vld;
typedef vector<pll> vpl;
typedef vector<vll> vvll;

#define ALL(a) a.begin(),a.end()
#define SZ(a) ((int)a.size())
#define FI first
#define SE second
#define REP(i,n) for(int i=0;i<((int)n);i++)
#define REP1(i,n) for(int i=1;i<((int)n);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define PB push_back
#define EB emplace_back
#define MP(a,b) make_pair(a,b)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define GET_POS(c,x) (lower_bound(c.begin(),c.end(),x)-c.begin())
#define yes cout<<"Yes"<<endl
#define YES cout<<"YES"<<endl
#define no cout<<"No"<<endl
#define NO cout<<"NO"<<endl
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL

const int inf = 1e9;
const ll linf = 1LL << 50;
const double eps = 1e-10;
const int MOD = 1e9 + 7;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

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

  ll n;
  cin>>n;
  vll a(3),b(3);
  REP(i,3)cin>>a[i];
  REP(i,3)cin>>b[i];

  vll dp(5010);
  for(ll i=0; i<5010; i++){
    vll t(3);
    REP(j,3){
      if(i>=a[j])
        t[j]=dp[i-a[j]]+b[j];
    }
    dp[i]=max({t[0],t[1],t[2],i});
  }

  vll dp2(5010*5010);
  for(ll i=0; i<5010*5010; i++){
    vll t(3);
    REP(j,3){
      if(i>=b[j])
        t[j]=dp2[i-b[j]]+a[j];
    }
    dp2[i]=max({t[0],t[1],t[2],i});
  }

  ll tmp=dp[n];
  ll ans=dp2[tmp];
  cout<<ans<<endl;

}



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

public class Main {
    PrintWriter out = new PrintWriter(System.out);
    // no self-loop or multiple edges
    public static void main(String[] args) throws Exception {
        Main main = new Main();
//        main.solve();
        System.out.println(main.solve());
    }
    long solve(){
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt(), n = sc.nextInt();
        int[] cur = new int[H+1], next = new int[H+1];
        Arrays.fill(cur,Integer.MAX_VALUE/2);
        cur[H] = 0;
        for(int i=0;i<n;i++){
            Arrays.fill(next,Integer.MAX_VALUE/2);
            int a = sc.nextInt(), b = sc.nextInt();
            if(a>H){
                System.arraycopy(cur, 0, next, 0, H+1);
                next[0] = Math.min(next[0], b);
            } else{
                for(int j=H; j>H-a; j--) next[j] = cur[j];
                for(int j=H-a;j>0;j--){
                    next[j] = Math.min(next[j+a]+b,Math.min(cur[j],cur[j+a]+b));
                }
                next[0] = cur[0];
                for(int j=a;j>=0;j--){
                    next[0] = Math.min(next[0],Math.min(cur[j]+b,next[j]+b));
                }
            }
            System.arraycopy(next, 0, cur, 0, H+1);
        }
        long ans = cur[0];
        sc.close();
        return ans;
    }
}



Measured memory_bytes: 26328
X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
AB = [a + b for a in A for b in B]
AB = sorted(AB, reverse=True)[:K]
ABC = [ab+c for ab in AB for c in C]
ABC = sorted(ABC, reverse=True)[:K]

for abc in ABC:
    print(abc)

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

using namespace std;

int main(){
    long long int N,ans=0;
    cin >> N;

    for(long long int i=2;i*i<=N;i++){
        if(N%i==0){
            long long int a,b;
            a = i-1;
            b = N/i -1;

            if(N/a == N%a){
                ans += a;
            }

            if(N/b == N%b){
                ans += b;
            }
        }
    }

    if(N!=1 && N/(N-1) == N%(N-1)){
        ans += N-1;
    }

    cout << ans << endl;
}

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

int main(){
    int N;
    int maxi = 0;
    string tmp;
    map<string,int> buf;
    cin >> N;
    for(int i = 0;i < N;i++){
        cin >> tmp;
        buf[tmp] += 1;
        maxi = max(maxi,buf[tmp]);
    }

    for(const auto& x : buf){
        if(x.second == maxi) cout << x.first << endl;
    }
    return 0;
}

Measured memory_bytes: 25216
#include<iostream>
using namespace std;
int main(){
	int a,b;
	char op;
	cin>>a;
	getchar();
	cin>>op>>b;
	int ans=0;
	if(op=='+'){
		ans=a+b;
	}
	else if(op=='-'){
		ans=a-b;
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    long[] a = new long[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextLong();
    }
    ArrayList<Integer> p = new ArrayList<Integer>();
    ArrayList<Integer> q = new ArrayList<Integer>();
    p.add(0);
    for(int i = 1; i < n; i++) {
      if(a[i] < a[i - 1]) {
        q.add(i - 1);
        p.add(i);
      }
    }
    q.add(n - 1);
    long ans = 1000;
    long kabu = 0;
    for(int i = 0; i < p.size(); i++) {
      long a1 = a[p.get(i)];
      long t = (ans / a1);
      kabu += t;
      ans -= (a1 * t);
      long a2 = a[q.get(i)];
      ans += (a2 * kabu);
      kabu = 0;
    }
    System.out.println(ans);
  }
}


Measured memory_bytes: 35840
import java.io.IOException;
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		long x_shomikigen = scan.nextLong();
		long a_before = scan.nextLong();
		long b_eatDay = scan.nextLong();

		long point = 0;

		point -= a_before;
		point += b_eatDay;

		if (point <= 0) {
			System.out.println("delicious");
		} else if (point <= x_shomikigen) {
			System.out.println("safe");
		} else {
			System.out.println("dangerous");
		}
	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 27040
#include<iostream>
#include <iomanip>

#define PI 3.14159265359	

using namespace std;

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

}

Measured memory_bytes: 3076
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--) 
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
#define downque(que) priority_queue<ll> que;
#define upque(que) priority_queue<ll, vector<int>, greater<int>> que;
typedef long long ll;
typedef vector<vector<int>> Matrix;
const int MOD = 1e9 + 7;
const int MAX = 1e7;
const int INF = numeric_limits<int>::max();

int main(){
ll a,b,n; cin>>n>>a>>b;
ll res=(n/(a+b))*a;

res+=min((n%(a+b)),a);
cout<<res<<endl;

}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
#define rep(i, n) for(int i=0;i<n;i++)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define szz(x) (int)(x).size()
#define Fi first
#define Se second
typedef long double ldouble;

int A[100010], N;
map <ll, int> X;

void solve() {
	scanf("%d", &N);
	ll s = 0, ans = 0;
	X[0] = 1;
	for(int i=1;i<=N;i++) {
		int x; scanf("%d", &x);
		s += x;
		ans += X[s];
		X[s]++;
	}
	printf("%lld\n", ans);
}

int main() {
	//DM(); return 0;
	int tc = 1; // scanf("%d", &tc);
	for(int t=1;t<=tc;t++) {
	//	printf("Case #%d: ", t);
		solve();
	}
	return 0;
}


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

int main() {
    int n, t[100100], x[100100], y[100100];
    cin >> n;
    t[0] = x[0] = y[0] = 0;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> x[i] >> y[i];
    }

    bool can = true;
    for (int i = 0; i < n; i++) {
        int T = t[i + 1] - t[i];
        int D = abs(x[i + 1] - x[i]) + abs(y[i + 1] - y[i]);
        if (T < D) {
            can = false;
            break;
        }
        if (T % 2 != D % 2) {
            can = false;
            break;
        }
    }

    if (can) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

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

int main() {
  int n;
  cin >> n;
  vector<int> a(n+2);
  map<int,int> cnt;
  rep(i,n) {
    int ni; cin >> ni;
    cnt[ni]++;
    cnt[ni+1]++;
    cnt[ni-1]++;
  }

  int ans = 0;
  for (auto p : cnt) {
    ans = max(ans, p.second);
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 7972
#include<stdio.h>
#include<string.h>
#define Q_MAX 100000

typedef struct pp{
  char name[100];
  int t;
}P;

P Q[Q_MAX+1];
int head, tail, n;

void enqueue(P x){
  Q[tail] = x;
  tail = (tail+1)%Q_MAX;
}

P dequeue(){
  P res = Q[head];
  head = (head+1)%Q_MAX;
  return res;
}

int empty(){
  return (head==tail?1:0);
}

int main(){
  int elaps,c;
  int i, q;
  P u;
  elaps=0;
  scanf("%d %d", &n, &q);
  head = 1;
  tail = n+1;

  for ( i = 1; i <= n; i++){
    scanf("%s", Q[i].name);
    scanf("%d", &Q[i].t);
  }

  while(empty()==0){
    u = dequeue();
    if(u.t > q){
      u.t -= q;
      enqueue(u);
      elaps += q;
    }else{
      elaps += u.t;
      printf("%s %d\n",u.name, elaps);
    }
  }
  return 0;
}



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

#define int long long

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

int N, x;
int a[2000];
multiset<int> cds;

signed main() {
    cin >> N >> x;
    for (int i = 0; i < N; i++) {
        cin >> a[i];
    }
    int ans = LLONG_MAX;
    for (int i = 0; i < N; i++) {
        int cur = i * x;
        for (int j = 0; j < i; j++) {
            cds.insert(a[j]);
        }
        for (int j = 0; j < N; j++) {
            cds.insert(a[(i + j) % N]);
            cur += *cds.lower_bound(0);
            cds.erase(cds.lower_bound(a[j]));
        }
        cds.clear();
        ans = min(ans, cur);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 384
def solve(Switch, K, P):
    count = 0
    for l_1 in K:
        total = 0
        for i_1 in l_1:
            total += Switch[i_1-1]
        if total % 2 != P[count]:
            return False
        count += 1
    return True

n,m = map(int,input().split())
k = []
for _ in range(m):
    s = list(map(int,input().split()))
    k.append(s[1::])
p = list(map(int,input().split()))

ans = 0

for i in range(2**n):
    switch = [0]*n
    for j in range(n):
        if ((i >> j) &1):
            switch[j] = 1
    if solve(switch, k, p):
        ans+=1

print(ans)

Measured memory_bytes: 9164
import java.util.Scanner;

public class Main {
	
	public static int size = 5;
	public static int interval = 100;
	
	public static int head=0, tail=0;
	
	public static boolean isFull() {
		return (tail-head >= size) ? true : false;
	}
	
	public static boolean isEmpty() {
		return (tail-head <=0 ) ? true : false;
	}

	public static void enqueue(Item[] queue, Item x) throws Exception {
		if (isFull()) 
			throw new Exception("Error: The queue is full!");
		queue[tail%size] = x;
		tail ++;
	}
	
	public static Item dequeue(Item[] queue) throws Exception {
		if (isEmpty())
			throw new Exception("Error: The queue is empty");
		Item headItem = queue[head%size];
		queue[head%size] = null;
		head ++;
		return headItem;
	}
	
	public static int process(Item i, int interval) {
		int time = i.getTime();
		if (time<=interval) {
			i.setTime(0);
			return time;
		} else {
			i.setTime(time-interval);
			return interval;
		}
	}
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		size = sc.nextInt();
		interval = sc.nextInt();
		Item[] queue = new Item[size];
		
		int atime = 0;
		
		try {
			for (int i=0; i<size; i++) {
				enqueue(queue, new Item(sc.next(), sc.nextInt()));
			}
			sc.close();
			
			while (!isEmpty()) {
				Item item = dequeue(queue);
				atime += process(item, interval);
				if (item.getTime() == 0) {
					System.out.println(item.getName() + " " + atime);
				} else {
					enqueue(queue, item);
				}
			}
		
		} catch (Exception e) {
			e.printStackTrace();
		}
	}

}

class Item {
	private String name;
	private int time;
	public String getName() {
		return name;
	}
	public int getTime() {
		return time;
	}
	public void setName(String name) {
		this.name = name;
	}
	public void setTime(int time) {
		this.time = time;
	}
	public Item(String name, int time) {
		super();
		this.name = name;
		this.time = time;
	}
	
}


Measured memory_bytes: 71592
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <utility>
#include <algorithm>
#include <map>
#include <cassert>
using namespace std;
#define REPP(i,a,b) for(int i = (a); i < (b); ++i)
#define REP(i,a) for(int i = 0; i < (a); ++i)
#define PER(i,a) for(int i = (a) - 1; i >= 0; --i)
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define MP make_pair

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

const int maxn = 1e5 + 5;
int w[105], v[105];
ll dp[maxn];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);
    REP(i, n) scanf("%d%d", w + i, v + i);
    REP(i, n) for (int j = k; j > 0; j--) {
        if (j >= w[i]) dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
    }
    cout << dp[k] << endl;
    return 0;
}


Measured memory_bytes: 1024
import numpy as np
A = np.array([list(map(int,list(input().split()))) for i in range(3)])
N = int(input())
b = [int(input()) for i in range(N)]

hit = np.zeros_like(A)

for n in b:
	hit[A == n] = 1
if np.sum(np.sum(hit, 0) == 3):
	print('Yes')
elif np.sum(np.sum(hit, 1) == 3):
	print('Yes')
elif hit[0, 0] + hit[1, 1] + hit[2, 2] == 3:
	print('Yes')
elif hit[2, 0] + hit[1, 1] + hit[0, 2] == 3:
	print('Yes')
else:
	print('No')

Measured memory_bytes: 12488
#include<vector>
#include<iostream>
#include <algorithm>
#define rep(i,n) for(int i = 0; i < (n); i++)
using namespace std;

void output(vector<int> B, int s) {
    rep(i, s - 1) cout << B.at(i) << " ";
    cout << B.at(s - 1) << endl;
}

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    rep(i,N) cin >> A.at(i);

    bool flag = true;
    int i = 0;
    int counter = 0;
    while(flag){
        flag = false;
        for(int j = N - 1; j >= i + 1;j--){
            if(A.at(j - 1) > A.at(j)){
                swap(A.at(j), A.at(j - 1));
                flag = true;
                counter++;
            }
        }
        i++;
    }
    output(A, N);
    cout << counter << endl;
}


Measured memory_bytes: 3160
#include <bits/stdc++.h>
#define DEBUG if(0)
#define lli long long int
#define ldouble long double
using namespace std;

const lli mod = 1e9 + 7, inf = LONG_LONG_MAX;
const int maxN = 2e5; int n, k;
lli a[maxN];
vector<lli> neg, pos;
vector<double> nacc, pacc;

int main()
{
  while (scanf("%d %d", &n, &k) != EOF)
  {
    neg.clear(), pos.clear(); int zeros = 0;
    for (int i = 0; i < n; i++)
    {
      scanf("%lld", &a[i]);
      if (a[i] < 0) neg.push_back(a[i]);
      else if (a[i] == 0) zeros++;
      else pos.push_back(a[i]);
    }
    sort(neg.begin(), neg.end());
    sort(pos.begin(), pos.end());
    reverse(pos.begin(), pos.end());

    nacc.resize(neg.size() + 1);
    nacc[0] = 0;
    for (int i = 0; i < neg.size(); i++)
      nacc[i + 1] = nacc[i] + log10(-neg[i]);

    pacc.resize(pos.size() + 1);
    pacc[0] = 0;
    for (int i = 0; i < pos.size(); i++)
      pacc[i + 1] = pacc[i] + log10(pos[i]);

    lli hehe = 0;
    if (neg.size() + pos.size() >= k)
    {
      double ans = -1; int ww = 0, wi, wj;
      for (int i = 0; i <= pos.size() && i <= k; i++)
        if (!((k - i) & 1) && (k - i) <= neg.size())
        {
          double w = pacc[i] + nacc[k - i];
          if (w > ans)
            ans = w, wi = i, wj = k - i, ww = 1;
        }
      if (ww)
      {
        hehe = 1;
        for (int i = 0; i < wi; i++)
          hehe = hehe * pos[i] % mod;
        for (int j = 0; j < wj; j++)
          hehe = (hehe * neg[j] % mod + mod) % mod;
      }

      if (ww == 0 && zeros == 0)
      {
        reverse(pos.begin(), pos.end());
        reverse(neg.begin(), neg.end());

        nacc.resize(neg.size() + 1);
        nacc[0] = 0;
        for (int i = 0; i < neg.size(); i++)
          nacc[i + 1] = nacc[i] + log(-neg[i]);

        nacc.resize(neg.size() + 1);
        nacc[0] = 0;
        for (int i = 0; i < neg.size(); i++)
          nacc[i + 1] = nacc[i] + log(-neg[i]);

        ans = inf;
        for (int i = 0; i <= pos.size() && i <= k; i++)
          if (((k - i) & 1) && (k - i) <= neg.size())
          {
            double w = pacc[i] + nacc[k - i];
            if (w < ans)
              ans = w, wi = i, wj = k - i, ww = 1;
          }
        if (ww)
        {
          hehe = 1;
          for (int i = 0; i < wi; i++)
            hehe = hehe * pos[i] % mod;
          for (int j = 0; j < wj; j++)
            hehe = (hehe * neg[j] % mod + mod) % mod;
        }
      }
    }

    printf("%lld\n", hehe);
  }
  return 0;
}

Measured memory_bytes: 8488
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>

#define int long long
#define REP(i,a,n) for(int i=a;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define REV(i,a,n) for(int i=n;i>=a;--i)
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
#define show(n) cerr<<#n<<" = "<<n<<endl
#define showp(n) cerr<<n.fs<<", "<<n.sc<<endl
#define shows(n) for(auto z:n){cerr<<z<<", ";}cerr<<endl
#define showsp(n) for(auto z:n){cerr<<z.fs<<" "<<z.sc<<", "}cerr<<endl

#define yes puts("Yes")
#define no puts("No")
#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

inline void io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}
inline int  in(){int n;scanf("%lld",&n);return n;}
inline void out(int n){printf("%lld\n",n);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;

vi table;

int n;
int ans=INF;

void ume(){
    int six=6;
    while(true){
        if(six>100000) break;
        table.pb(six);
        six*=6;
    }
    int nine=9;
    while(true){
        if(nine>100000) break;
        table.pb(nine);
        nine*=9;
    }
    sort(rall(table));
}

void dfs(int zan, int num){
    //show(ans);
    if(num>=ans) return;
    if(zan < 6){
        ans = min(num+zan,ans);
        return;
    }

    int c=0;
    rep(i,table.size()){
        if(c>1) break;
        if(table[i]>zan) continue;
        dfs(zan-table[i],num+1);
        c++;
    }
}

signed main(){
    io();

    ume();
    n=in();
    //shows(table);

    dfs(n, 0);
    out(ans);

    return 0;
}


Measured memory_bytes: 256
package main

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

// input scanner
var sc = bufio.NewScanner(os.Stdin)

const (
	initialBufSize = 10e4
	maxBufSize     = 10e6
)

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

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

func nextInt64() int64 {
	a, _ := strconv.ParseInt(next(), 10, 64)
	return a
}

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

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

func nextInt64s(n int) []int64 {
	ret := make([]int64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextInt64()
	}
	return ret
}
func nextFloats(n int) []float64 {
	ret := make([]float64, n)
	for i := 0; i < n; i++ {
		ret[i] = nextFloat64()
	}
	return ret
}
func nextStrings(n int) []string {
	ret := make([]string, n)
	for i := 0; i < n; i++ {
		ret[i] = next()
	}
	return ret
}

// util
func max(l []int) (int, int) {
	idx := 0
	ans := l[idx]
	for i, n := range l {
		if n > ans {
			idx = i
			ans = n
		}
	}
	return idx, ans
}

func min(l []int) (int, int) {
	idx := 0
	ans := l[idx]
	for i, n := range l {
		if n < ans {
			idx = i
			ans = n
		}
	}
	return idx, ans
}

var mod = 1000000007

func mul(a int, b int) int {
	return (a * b) % mod
}

func power(x int, y int) int {
	if y == 0 {
		return 1
	} else if y%2 == 0 {
		ans := power(x, y/2) % mod
		ans = mul(ans, ans)
		return ans
	} else {
		ans := power(x, y/2) % mod
		ans = mul(mul(ans, ans), x)
		return ans
	}
}

func genPrime(n int) []int {
	check := make([]int, n+1)
	ps := make([]int, 0, n)
	for i := 2; i <= n; i++ {
		if check[i] == 0 {
			ps = append(ps, i)
		}
		for j := i * i; j <= n; j += i {
			if check[j] == 0 {
				check[j] = 1
			}
		}
	}
	return ps
}

func minPrimeFactors(n int) []int {
	pf := make([]int, n+1)
	for i := 2; i <= n; i++ {
		if pf[i] != 0 {
			continue
		}
		pf[i] = i
		for j := i * i; j <= n; j += i {
			if pf[j] == 0 {
				pf[j] = i
			}
		}
	}
	return pf
}

// main
func main() {
	buf := make([]byte, initialBufSize)
	sc.Buffer(buf, maxBufSize)
	sc.Split(bufio.ScanWords)
	n := nextInt()
	a := make([]int, n)
	var amax int
	for i := 0; i < n; i++ {
		a[i] = nextInt()
		if a[i] > amax {
			amax = a[i]
		}
	}
	mpf := minPrimeFactors(amax)
	var ans int
	m := make(map[int]int, n)
	for i := 0; i < n; i++ {
		pf := make(map[int]int, n)
		ai := a[i]
		for ai > 1 {
			pf[mpf[ai]]++
			ai = ai / mpf[ai]
		}
		for p, c := range pf {
			if c > m[p] {
				m[p] = c
			}
		}
	}
	ab := 1
	for x, c := range m {
		ab = mul(ab, power(x, c))
	}
	// fmt.Println("m", m)
	for i := 0; i < n; i++ {
		b := mul(ab, power(a[i], (mod-2)))
		ans = (ans + b) % mod
	}
	fmt.Println(ans)
}


Measured memory_bytes: 22912
a = gets.chomp.split(//)
s = a.count('S')
n = a.count('N')
e = a.count('E')
w = a.count('W')
if s > 0 && a.count('N') > 0 && e > 0 && w > 0
    puts 'Yes'
elsif s == 0 && n == 0 && e > 0 && w > 0
    puts 'Yes'
elsif s == 0 && n == 0 && e == 0 && w == 0
    puts 'Yes'
elsif s > 0 && n > 0 && e == 0 && w == 0
    puts 'Yes'
else
    puts 'No'
end

Measured memory_bytes: 1788
n,k = map(int,input().split())
a = list(map(int,input().split()))
n -= k
k -= 1
p = 1
if n <= 0:
    print(p)
else:
    if n % k == 0:
        print(p + n // k)
    else:
        print(p + n // k + 1)

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

using namespace std;

using ll = long long;

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

    string s;
    cin >> s;
    for (auto &c : s) {
        if (c == '1') c = '9';
        else c = '1';
    }

    cout << s << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int, char**)
{
	unsigned long long n, k, a = 1000000000;
	cin >> n >> k;
	vector<unsigned long long> t;
	t.resize(n);
	for (int i = 0; i < n; i++) {
		cin >> t[i];
	}
	sort(t.begin(), t.end());

	for (int i = 0; i <= n - k; i++) {
		unsigned long long x = t[i+k-1] - t[i];
		if (a > x)
			a = x;
	}

	cout << a << endl;
	return 0;

}


Measured memory_bytes: 1024
import sys

read = sys.stdin.buffer.read
input = sys.stdin.buffer.readline
inputs = sys.stdin.buffer.readlines


#mod=10**9+7
# rstrip().decode('utf-8')
# map(int,input().split())
#import numpy as np


def main():
	n=int(input())
	
	ans1=0
	ans2=0
	
	for i in range(1,n+1):
		a=int(str(i)[0])
		b=i%10
		
		if b==0:
			continue
		k=len(str(i))
		if k==1:
			ans2+=1
		elif a>b:
			ans1+=(10**(k-1)-1)//9
		elif a<b:
			ans1+=(10**(k-2)-1)//9
		else:
			ans1+=(10**(k-2)-1)//9+1+(int(str(i)[1:])-a)//10
			ans2+=1
	print(ans1*2+ans2)
	
	
	
	
	


if __name__ == "__main__":
	main()


Measured memory_bytes: 41324
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cctype>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<(n);i++)
#define loop(i,a,n) for(i=a;i<(n);i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef vector<string> vs;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int n;
  cin>>n;
  vi a(n),b(n);
  rep(i,n)cin>>a[i]>>b[i];
  ll ans=0;
  ll t=0;
  vector<int> p;
  rep(i,n){
    if(a[i]<b[i]) ans+=b[i];
    if(a[i]==b[i]) t+=a[i];
    if(a[i]>b[i]) p.push_back(b[i]);
  }
  
  if(ans==0){
    cout<<0<<endl;
    return 0;
  }
  ans+=t;
  sort(all(p));

  loop(i,1,p.size())ans+=p[i];

  cout<<ans<<endl;
}



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

using ll = long long;
using ull = unsigned long long;
using ld = long double;

#define MOD 1000000007LL

#define rep(i, n) for(ll (i) = 0LL;(i) < (ll)(n);(i)++)
#define rep2(i, s, e) for(ll (i) = (ll)(s);(i) < (ll)(e);(i)++)
#define repi(i, n) for(ll (i) = 0LL;(i) <= (ll)(n);(i)++)
#define repi2(i, s, e) for(ll (i) = (ll)(s);(i) <= (ll)(e);(i)++)
#define per(i, n) for(ll (i) = (ll)(n) - 1LL;(i) >= 0LL;(i)--)
#define per2(i, s, e) for(ll (i) = (ll)(s) - 1LL;(i) >= (ll)(e);(i)--)
#define peri(i, n) for(ll (i) = (ll)(n);(i) >= 0LL;(i)--)
#define peri2(i, s, e) for(ll (i) = (ll)(s);(i) >= (ll)(e);(i)--)
#define iter(i, it) for(auto &(i): (it))

template<typename T, typename U> ostream& operator<<(ostream &s, const pair<T, U> m) {
    cout << "(" << m.first << ", " << m.second << ")";
    return s;
}
template<typename T, typename U> ostream& operator<<(ostream &s, const map<T, U> m) {
    ll c = 0;
    cout << "{ ";
    iter(i, m) cout << i << (c++ == m.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const vector<T> &v) {
    cout << "{ ";
    rep(i, v.size()) cout << v[i] << (i == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}
template<typename T> ostream& operator<<(ostream &s, const list<T> &v) {
    ll c = 0;
    cout << "{ ";
    iter(i, v) cout << i << (c++ == v.size() - 1 ? " " : ", ");
    cout << "}";
    return s;
}

int main(void) {
    ll N;
    cin >> N;
    if(N < 1000) cout << "ABC";
    else cout << "ABD";
    cout << endl;
    return 0;
}


Measured memory_bytes: 3612
#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif

    int n;
    cin >> n;
    int a = 0, b = 0, c = 0, ans = 0;
    for (int i = 0; i < n; ++i) {
        string s;
        cin >> s;
        for (int j = 0; j + 1 < (int)s.size(); ++j) {
            if (s.substr(j, 2) == "AB") ++ans;
        }   
        if (s[0] == 'B' && s.back() == 'A') ++c;
        else if (s[0] == 'B') ++b;
        else if (s.back() == 'A') ++a;
    }   
    
    if (a) {
        cout << ans + c + min(a, b) << '\n';
    }   
    else {
        if (c) {
            cout << ans + c - 1 + (bool)b << '\n';
        }
        else {
            cout << ans << '\n';
        }   
    }   

}


Measured memory_bytes: 256
import Control.Monad
import Control.Applicative
readDigits = map read <$> words <$> getLine :: IO [Int]
main = do
    [n,m] <- readDigits
    matrix <- replicateM n $ readDigits
    vector <- replicateM m $ readLn :: IO [Int]
    putStr $ unlines [show . sum $ zipWith (*) m vector | m<-matrix] 


Measured memory_bytes: 7548
#include<stdio.h>

int A[2000],M[2000],i,q,n,count=0;

int solve(int p,int t){

if(t==0){
printf("yes\n");
 return 1; 
 }else if(t < 0){
  return 0;
 }
  if(p >= n){return 0;}
 if(solve(p+1,t-A[p]))return 1;

 if(solve(p+1,t)) return 1;

 return 0;
}
int main(){
scanf("%d",&n);
for(i=0;i<n;i++){
scanf("%d",&A[i]);
}
scanf("%d",&q);
for(i=0;i<q;i++){
scanf("%d",&M[i]);
}
 for(i = 0; i < q;i++){
   if(!solve(0,M[i])){
printf("no\n");
   }
 }
   // count++;
   // }
return 0;
}

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

#define d(x) cerr << #x ":" << x << endl;
#define dd(x, y) cerr << "(" #x "," #y "):(" << x << "," << y << ")" << endl
#define rep(i, n) for (int i = (int)(0); i < (int)(n); i++)
#define repp(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
#define all(v) v.begin(), v.end()
#define dump(v)                  \
    cerr << #v ":[ ";            \
    for (auto macro_vi : v) {    \
        cerr << macro_vi << " "; \
    }                            \
    cerr << "]" << endl;
#define ddump(v)                           \
    cerr << #v ":" << endl;                \
    for (auto macro_row : v) {             \
        cerr << "[";                       \
        for (auto macro__vi : macro_row) { \
            cerr << macro__vi << " ";      \
        }                                  \
        cerr << "]" << endl;               \
    }
using lint       = long long;
const int INF    = 1e9;
const lint LINF  = 1e18;
const lint MOD   = 1e9 + 7;
const double EPS = 1e-10;

int main() {
    string S;
    cin >> S;
    int N    = S.size();
    int head = 0, tale = N;

    int ans = 0;
    while (head < tale) {
        if (S[head] == S[tale - 1])
            head++, tale--;
        else {
            if (S[head] == 'x') {
                ans++;
                head++;
            } else if (S[tale - 1] == 'x') {
                ans++;
                tale--;
            } else {
                cout << -1 << endl;
                return 0;
            }
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 512
N, M = map(int, input().split())
starts = set([])
ends = set([])

for _ in range(M):
    a, b = map(int, input().split())
    if a == 1 or b  == 1:
        starts.add(a if b == 1 else b)
    if a == N or b == N:
        ends.add(a if b == N else b)

ans = "POSSIBLE" if len(starts&ends)>=1 else "IMPOSSIBLE"
print(ans)

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

int main(){
  int h,w;
  cin >> h >> w;
 
  string s[h];
  rep(i,h) cin >> s[i];
  
  rep(i,w+2) cout << "#";
  cout << endl;
  
  rep(i,h) cout << "#" << s[i] << "#" << endl;
  
  rep(i,w+2) cout << "#";
  cout << endl;

}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author aajisaka
 */

#include<bits/stdc++.h>

using namespace std;

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

#define SPEED ios_base::sync_with_stdio(false);cin.tie(nullptr)
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using ll = long long;
using P = pair<ll, ll>;

constexpr double PI = 3.14159265358979323846;
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

class FDistinctNumbers {
public:

    void solve(istream& cin, ostream& cout) {
      SPEED;
      int n; cin >> n;
      vector<int> c(n+1);
      rep(i, n) {
        int a; cin >> a;
        c[a]++;
      }

      vector<int> d(n+1);
      for(int i=1; i<=n; i++) {
        d[c[i]]++;
      }

      vector<ll> sumkd(n+1);
      vector<ll> sumd(n+1);
      rep(i, n) {
        sumkd[i+1] += sumkd[i] + (i+1)*d[i+1];
        sumd[i+1] += sumd[i] + d[i+1];
      }

      vector<ll> f(n+1);
      for(int i=1; i<=n; i++) {
        f[i] = sumkd[i]/i + (sumd[n] - sumd[i]);
      }
      int p = 1;
      vector<int> ret(n);
      for(int i=n; i>=1; i--) {
        while(p <= n && i <= f[p]) {
          p++;
        }
        ret[i-1] = p-1;
      }

      for(auto& e: ret) {
        cout << e << '\n';
      }
    }
};

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

Measured memory_bytes: 11392
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>

int max(int a,int b){
	if(a>b)return a;
	return b;
}

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

int compare_char(char *a,char *b){
	return strcmp(a,b);
}

int intsort(const void *a, const void *b){
	return *(int*)b - *(int*)a;
	/*qsort(a,aの配列数,sizeof(int),intsort);*/
}

int longsort(const void *a, const void *b){
	long *A=(long *)a;
	long *B=(long *)b;
	if(*A>*B) return -1;
	if(*A<*B) return 1;
	return 0;
}

int main(){
  int i,N,t=1;
  long min,cnt,now;
  scanf("%d",&N);
  scanf("%ld",&min);
  if(min<0)t=-1;
  min=labs(min);
  cnt=min;
  for(i=1;i<N;i++){
    scanf("%ld",&now);
    if (now<0){
      t*=-1;
    }
    now=labs(now);
    if(min>now)min=now;
    cnt+=now;
  }
  if(t==1){
    printf("%ld\n",cnt);
  }else{
    printf("%ld\n",cnt-min*2);
  }
  return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define rep(i, n) for(int (i)=0 ;i <(n); ++(i))
#define REP(i,m,n) for(int (i) = (m); (i) <= (n); ++(i))
#define yorn(f) puts((f)?"Yes":"No")
#define YORN(f) puts((f)? "YES":"NO")
typedef long long ll;
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  if(b/a <= c) cout << b/a << endl;
  else cout << c << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;


const int MAX_N = 100010;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n; cin >> n;
	VE a(n); rep(i, n)cin >> a[i];
	int ans = 0;
	rep(i, n - 2) {
		vector<P> tmp;
		tmp.push_back(make_pair(a[i],1)); tmp.push_back(make_pair(a[i + 1],2));
		tmp.push_back(make_pair(a[i + 2],3));
		sort(ALL(tmp));
		if (tmp[1].second == 2) {
			ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
using ll = long long;

int main(int argc, char const* argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll A, B, C, K;
    cin >> A >> B >> C >> K;
    cout << (K % 2 == 0 ? A - B : B - A) << endl;
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(){
  long long n,ans=1,mod=1e9+7;
  string s;
  cin >> n >> s;
  map<char, int> mp;
  for(int i=0;i<n;i++){
    mp[s[i]]++;
  }
  for(char c='a';c<='z';c++){
    ans*=(mp[c]+1);
    ans%=mod;
  }
  cout << ans-1 << endl;
  return 0;
}


Measured memory_bytes: 512
aaaa = input()
A = [int(x) for x in input().split()]

s1 = False
for i in range(len(A)):
  ts1 = sum(A[:i+1])
  ts2 = sum(A[i+1:])
  if ts1 >= ts2 and s1:
    print(min(abs(ts1-ts2),abs(s1-s2)))
    break
  s1 = sum(A[:i+1])
  s2 = sum(A[i+1:])

Measured memory_bytes: 3064
#include <iostream>
#include <string>
using namespace std;
int main(){
int a[100];
int b;
b=0;
while(b<100){
a[b]=0;
b=b+1;}
int n;
while(cin >>n){
a[n]=a[n]+1;}
int c;
c=0;
b=0;
while(b<100){
if(a[b]>c){c=a[b];}
b=b+1;}
b=0;
while(b<100){
if(c==a[b]){cout <<b<<endl;}
b=b+1;}
}

Measured memory_bytes: 1160
#include<iostream>
 #include<stdio.h>
 #include<string>
 #include<math.h>
 #include<iomanip>
 #include<algorithm>
 #include<string.h>
 #include<cctype>
 #include<map>
 #include<set>
 #include<vector>
 #include<sstream>
 #include<stack>
 #include<queue>
 #include<functional>
 #include<utility>
 
 using namespace std;
 
 long long int arr[1000000+5];
 
 int main()
 {
   int N;
   while(cin>>N&&N)
   {
     map<int,int> mm;
     map<int,int>::iterator iter;
     long long int num;
     long long int result;
     bool flag=false;
     for(int i=0;i<N;i++) 
     {
       cin>>num;
       mm[num]++;
       if(mm[num]>(N/2))
       {
         flag=true;
         result=num;                  
       }        
     }
     if(!flag) cout<<"NO COLOR"<<endl;
     else cout<<result<<endl;
   }
   //while(1);
   return 0;
 }

Measured memory_bytes: 4520
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

int main() {
	// cin の高速化らしい
	ios::sync_with_stdio(false);
	cin.tie(0);

	int n, k;
	cin >> n >> k;
	vector<pair<int, int>> sushi;

	for (int i = 0; i < n; i++) {
		int t, d;
		cin >> t >> d;
		t--;
		sushi.push_back({ d, t });
	}
	sort(sushi.begin(), sushi.end()); // おいしさ順に昇順ソート
	reverse(sushi.begin(), sushi.end()); // 昇順から降順へ
	vector<bool> usd(n, false); // n個の配列にすべてfalse
	long long ans = 0;
	long long score = 0;
	int cnt = 0;
	// k個に選ばれなかった寿司達
	priority_queue<int> unused_repr;
	// k個に選ばれたが二個目以上だった寿司達
	// 小さいものから取り出せる優先度付きキュー
	priority_queue<int, vector<int>, greater<int>> used_subj;

	for (int i = 0; i < n; i++) {
		auto sus = sushi[i];
		int d = sus.first;
		int t = sus.second;
		if (usd[t]) {
			if (i < k) {
				score += d;
				// この種類が二個以上のときは消される予備軍として保管
				used_subj.push(d);
			}
		}
		else {
			usd[t] = true;
			if (i < k) {
				score += d + 2 * cnt + 1;
				cnt++;
			}
			else {
				// k+1番目以降の寿司で使われていないものは追加される予備軍として保管
				unused_repr.push(d);
			}
		}
	}

	ans = score;
	while (!unused_repr.empty() && !used_subj.empty()) {
		int repr = unused_repr.top();
		unused_repr.pop();
		int subj = used_subj.top();
		used_subj.pop();
		score += (long long)repr - subj + 2 * cnt + 1;
		cnt++;
		ans = max(ans, score);
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1524
#include <stdio.h>

int A[1000000],n;

int binarySearch(int key){
	int lef = 0;
	int rig = n;
	int mid;
	while(lef < rig){
		mid=(lef+rig)/2;
		if(key==A[mid]) return 1;
		if(key>A[mid]) lef=mid+1;
		else if (key<A[mid]) rig=mid;
			}
	return 0;
}

int main(){
	int i,q,k,sum=0;
scanf("%d",&n);
for(i=0;i<n;i++)
{
	scanf("%d",&A[i]);
}

scanf("%d",&q);
for(i=0;i<q;i++){
	scanf("%d",&k);
	if(binarySearch(k)) sum++;
}
printf("%d\n",sum);

return 0;
}

Measured memory_bytes: 988
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <cctype>
#include <cmath>
#include <bitset>
#include <set>
#include <tuple>
#include <iomanip>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; --i)
#define FOR(i,k,n) for(int i=(k);i<(int)(n);++i)
#define all(i,n) (i),(i+n)

int dx4[4]={1,0,-1,0};
int dy4[4]={0,-1,0,1};
int dx8[8]={1,0,-1,1,-1,1,0,-1};
int dy8[8]={1,1,1,0,0,-1,-1,-1};

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

const int INF = 1e9;
const ll LLINF = 1e18;
const int MAX_V = 1e6+1;
const ll mod = 1000000007;

// --------------------------------------
int n;
int a[100005];
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);

  cin >> n;

  int ma = -INF;
  REP(i, n) {
    cin >> a[i];
    ma = max(a[i], ma);
  }

  sort(a, a + n);

  int ma2 = ma / 2;
  int b = INF;
  int c = a[0];
  REP(i, n - 1) {
    if(abs(ma2 - a[i]) <= b) {
      c = a[i];
      b = abs(ma2 - a[i]);
    } else {
      break;
    }
  }

  cout << ma << " " << c << endl;
}


Measured memory_bytes: 640
//
// Created by 遠藤護 on 7/18/18.
//
#include <iostream>
using namespace std;

int main() {
    int N;
    int a[100];
    cin >> N;
    for (int i = 0; i < N; ++i) cin >> a[i];

    int ans = 0;
    for (int i = 1; i < N; ++i){
        if (a[i-1] == a[i]) {
            ans ++;
            a[i] = 101;
        }
    }

    cout << ans << endl;
}


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

// dp[ni][vi]
int64_t dp[101][101010];

int main() {
	int64_t n, W;
	cin >> n >> W;
	vector< int64_t > w(n), v(n);
	for (int i=0; i<n; ++i) cin >> w[i] >> v[i];
	fill_n(dp[0], 101010, 1e9+1);
	dp[0][0] = 0;
	
	for (int ni=0; ni<n; ++ni) {
		for (int vi=0; vi<101010; ++vi) {
			dp[ni+1][vi] = dp[ni][vi];
			if (vi-v[ni] < 0) continue;
			dp[ni+1][vi] = min(dp[ni+1][vi], dp[ni][vi-v[ni]] + w[ni]);
		}
	}

	int64_t ans = 0;
	for (int64_t i=0; i<101010; ++i) {
		if (dp[n][i] > W) continue;
		ans = max(ans, i);
	}
	cout << ans << endl;
	/*
	for (int i=0; i<=n; ++i) {
		for (int wi=0; wi<=W; ++wi){
			cout << dp[i][wi] << " ";
		}
		cout << endl;
	}
	*/
  return 0;
}


Measured memory_bytes: 80000
#include <bits/stdc++.h>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	#include <cstring>
	#include <chrono>
	#include <complex>
	#define endl "\n"	
	typedef long long LL;
	#define ll long long int
	#define vi vector<int>
	#define vll vector<ll>
	#define vvi vector < vi >
	#define pii pair<int,int>
	#define pll pair<long long, long long>
	#define mod 1000000007
	#define mod2 998244353
	#define INFINITE 1000000000000000001;
	#define all(c) c.begin(),c.end()
	#define sz(v) ((ll)(v).size())
	#define mp(x,y) make_pair(x,y)
	#define mem(a,val) memset(a,val,sizeof(a))
	#define eb emplace_back
	#define pb push_back
	#define f first
	#define s second
	#define dbg(a) cout<<#a<<" --> "<<(a)<<"\n";
	#define forn(i,n) for (ll i=0; i<(n); ++i)
	#define fornd(i,n) for (ll i=(n)-1; i>=0; --i)	
	#define forab(i,a,b) for (ll i=(a); i<=(b); ++i)
	#define read(a) ll a; cin >> a;
	#define reads(s) string s; cin >> s;
	#define readb(a, b) ll a, b; cin >> a >> b;
	#define readc(a, b, c) ll a, b, c; cin >> a >> b >> c;
	#define readarr(a, n) int a[(n) + 1] = {}; forab(i, 0, (n-1)) {cin >> a[i];}
	#define readmat(a, n, m) int a[n + 1][m + 1] = {}; forab(i, 1, n) {forab(j, 1, m) cin >> a[i][j];}
	#define readv(A,n) vll A(n,0); forn(i,n) cin>>A[i]; 
	#define print(a) cout << a << endl;
	#define printarr(a, n) forab (i, 1, n) cout << a[i] << " "; cout << endl;
	#define printv(v) for (int i: v) cout << i << " "; cout << endl;
	#define printmat(a, n, m) forab(i, 1, n) {forab (j, 1, m) cout << a[i][j] << " "; cout << endl;}
	 
	#define INF (1e18+5)
	#define inf (1e9+5)
	int dx[4] = { 0, 0, 1, -1 };
	int dy[4] = { 1, -1, 0, 0 };
	// 8-directions
	//int dx[]={1,1,1,0,0,-1,-1,-1};
	//int dy[]={-1,0,1,-1,1,-1,0,1};
	#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
	using namespace std;
	int begtime = clock();
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	mt19937_64 rngb(chrono::steady_clock::now().time_since_epoch().count()); // can give negative values too
	bool isPowerOfTwo(int x) {
    return x && (!(x & (x - 1)));
	}
	int takemod(int x) {
    return (x % mod + mod) % mod;
	}
 
		ll power(ll a, ll b)	//a is base, b is exponent
		{
			if(b==0)
				return 1;
			if(b==1)
				return a;
			if(b%2 == 1)
				return (power(a,b-1)*a)%mod;
			ll q = power(a,b/2);
			return (q*q)%mod;
		}
 
	
	void solve()
	{
		ll n,ans=0;
		cin>>n;
		vll A(n);
		
		forn(i,n)
		{
			cin>>A[i];
		}
		vll pre(1,0);
		fornd(i,n)pre.pb(pre.back()+A[i]);
		forn(i,n)
		{
			//dbg(pre[n-i-1])
			ans=(ans%mod+((A[i]%mod)*(pre[n-i-1]%mod)))%mod;
		}
		
			
		cout<<ans<<endl;
	}
	int main()
	{	
		#ifndef ONLINE_JUDGE
		freopen("input.txt","r",stdin);
		freopen("output.txt","w",stdout);
		#endif
		fast_io;
		int T=1;
		//cin>>T;
		// cin.ignore(); must be there when using getline(cin, s)
		while(T--)
		{
			solve();
		}
		
		return 0;
	}

	
	

Measured memory_bytes: 6968
import bisect

n,k = map(int,input().split())
x = list(map(int,input().split()))

x.sort()

if x[-1] <= 0:
  print(abs(x[n-k]))
  exit()
elif x[0] >= 0:
  print(x[k-1])
  exit()

ans = []
if 0 not in x:
  x = [-10**10]*(10**6) + x + [10**10]*(10**6)
  ind = bisect.bisect_left(x,0)
  ans.append(abs(x[ind-k]))
  ans.append(x[ind+k-1])

  for i in range(ind-k+1,ind+k-1):
    a = 2*abs(x[i])+x[i+k-1]
    b = abs(x[i])+2*x[i+k-1]
    ans.append(min(a,b))
    
  print(min(ans))
  
else:
  x = [-10**10]*(10**6) + x + [10**10]*(10**6)
  ind = bisect.bisect_left(x,0)
  ans.append(abs(x[ind-k+1]))
  ans.append(x[ind+k-1])
  
  for i in range(ind-k+2,ind+k-1):
    a = 2*abs(x[i])+x[i+k-1]
    b = abs(x[i])+2*x[i+k-1]
    ans.append(min(a,b))
    
  print(min(ans))

Measured memory_bytes: 47708
#include <bits/stdc++.h>
using namespace std;
int main(){
    long long int n = 100;
    long long int y = 1;
    long long int f;
    cin >> f;
    while(1){
        n =  n + n / 100;
        if(f <= n){
            cout << y << endl;
            break;
        }
        y++;
    }
    return 0;
}

Measured memory_bytes: 3636