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

using namespace std;
typedef long long int ll;
typedef pair<int, int> ii;
#define DEBUG freopen("in.txt", "r", stdin);

struct fastio {
    fastio() {
        ios::sync_with_stdio(false);
        cout << setprecision(10) << fixed;
        cin.tie(0);
    }
};

fastio _fast_io;

const int N = 105;
int h, w;
bool H[N], W[N];
char a[N][N];

int main() {
    cin >> h >> w;
    for (int i = 0; i < h; ++i) {
        for (int j = 0; j < w; ++j) {
            cin >> a[i][j];
            if (a[i][j] == '#') {
                H[i] = true;
                W[j] = true;
            }
        }
    }
    for (int i = 0; i < h; ++i) {
        bool ok = false;
        for (int j = 0; j < w; ++j) {
            if (H[i] && W[j]) {
                ok = true;
                cout << a[i][j];
            }
        }
        if (ok)
            cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3664
import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		// TODO 自動生成されたメソッド・スタブ

		//入力の準備
		Scanner scan = new Scanner(System.in);

		//入力値を受け取る
		String str = scan.next();
		//受け取った文字を数値に変換
		int x = Integer.parseInt(str);

		//xを３乗する
		int anser = 0;
		double y = (double)x;

		double z = Math.pow(y,3.0);
		anser = (int)z;
		


		System.out.println( anser );

		//scan.close();
	}
}



Measured memory_bytes: 26044
# = map(int, input().split())
n = int(input())
# = input()
# = list(map(int, input().split()))

nlst = []
for i in range(1, int(n**(1/2))+1):
	if n%i == 0:
		nlst.append(i)

x = nlst[len(nlst)-1]
print(x + n//x - 2)



Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <sstream>
#include <math.h>
#include <queue>
#include <map>
#include <set>
#include <ios>     // std::left, std::right
#include <iomanip> // std::setw(int), std::setfill(char)
using namespace std;

int main(){
  long long N,M;
  cin>>N>>M;
  vector<vector<long long>> G(N);
  long long u,v,S,T;
  for(int i=0;i<M;++i){
    cin>>u>>v;
    u--;v--;
    G[u].push_back(v);
  }
  cin>>S>>T;
  S--;T--;
  long long used[3][N];
  for(int i=0;i<N;++i){
    for(int j=0;j<3;++j){
    used[j][i]=(-1);}
  }
  queue<long long> que;
  queue<long long> que_step;
  que.push(S);
  que_step.push(0);
  used[0][S]=0;
  long long first,first_step;
  while(que.size()){
    //numがスタート地点
    int num=que.front();
    que.pop();
    int num_step=que_step.front();
    que_step.pop();
    for(int i=0;i<G[num].size();++i){
      first=G[num][i];
      if(used[(num_step+1)%3][first]==(-1)){
            //usedにしてキューにぶち込む
            que.push(first);
            que_step.push(num_step+1);
            used[(num_step+1)%3][first]=num_step+1;
          }
    }
    if(used[0][T]!=-1){
      break;
    }
  }
  if(used[0][T]<0){
    cout<<-1<<"\n";
  }else{
  cout<<used[0][T]/3<<"\n";}
return 0;
}

Measured memory_bytes: 8064
n, a, b = map(int, input().split())
if a % 2 == b % 2:
    print(abs(b - a) // 2)
else:
    ans1 = ((min(a, b)) * 2 + abs(b - a)) // 2
    ans2 = ((n - max(a, b)) * 2 + abs(b - a) + 1) // 2
    print(min(ans1, ans2))

Measured memory_bytes: 3060
import java.util.Scanner;

public class Main {

	@SuppressWarnings("resource")
	public static void main(String args[]) {
		Scanner scanner = new Scanner(System.in);
		int a = scanner.nextInt();
		int b = scanner.nextInt();
		int max = Math.max(a + b, a - b);
		max = Math.max(max, a * b);

		System.out.println(max);

	}
}


Measured memory_bytes: 21844
#include<stdio.h>
int main()
{
int A,B,C,D,L,R;

while (scanf("%d%d%d%d",&A,&B,&C,&D)!=EOF)
{
L=A+B;

R=C+D;

if(L>R)

printf("Left\n");

else if(L<R)

printf("Right\n");

else if(L=R)

printf("Balanced\n");

}
return 0;
}

Measured memory_bytes: 128
/*
Author : N_o_o_B
Created : April 19 2020 17:34:38 
*/
#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;
*/
#define TRACE
#ifdef TRACE
#define trace(...) { cerr<<"[ "; __trace__(#__VA_ARGS__, __VA_ARGS__);}
#undef endl
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const pair<Arg1,Arg2> &x) {
    return out<<"("<<x.first<<","<<x.second<<")";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const vector<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
ostream& operator << (ostream& out, const set<Arg1> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1,typename Arg2>
ostream& operator << (ostream& out, const map<Arg1,Arg2> &a) {
    out<<"[";for(const auto &x:a)out<<x<<",";return out<<"]";
}
 
template <typename Arg1>
void __trace__(const string name, Arg1&& arg1){
    cerr << name << " : " << arg1 << " ] " << endl;
}
 
template <typename Arg1, typename... Args>
void __trace__(const string names, Arg1&& arg1, Args&&... args){
    const string name = names.substr(0,names.find(','));
    cerr<<name<<" : "<<arg1<<" | ";
    __trace__(names.substr(1+(int)name.size()), args...);
}
#else
    #define trace(args...)
#endif
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pair<int,int>> vii;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<pair<ll,ll>> vll;
typedef vector<vl> vvl;
//typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
#define fori(i,n) for(int i=0;i<n;i++)
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define repd(i,a,b) for(int i=a;i>=b;i--)
#define ford(i,n)  for(int i=n-1;i>=0;i--)
#define trav(x,a) for(auto& x:a)
#define all(x) x.begin(),x.end()
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define fi first
#define se second
clock_t time_p=clock();
void time_taken()
{
    time_p=clock()-time_p;
    cerr<<"Time Taken : "<<(float)(time_p)/CLOCKS_PER_SEC<<"\n";
}
//const ll mod=998244353;
const ll mod=1e9+7;
const ll INF=1e18;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cout.precision(12);cout << fixed;

    int n,m;
    cin >> n >> m;
    ll sum = 0;
    fori(i,m){
        int x;
        cin >> x;
        sum += x;
    }
    if(sum > n){
        cout << -1 << endl;
    }
    else{
        cout << (n - sum) << endl;
    }
    



    time_taken();
    return 0;
}

Measured memory_bytes: 3772
def prime(n):
  if n==1:
    return False
  elif n==2:
    return True
  else:
    for i in range(2,int((n)**(1/2))+1):
      if n%i==0:
        return False
    return True
list=[True]*100001
for i in range(1,100001):
  if not prime(i):
    list[i]=False
list1=[0]
count=0
for i in range(1,100001):
  if i%2==1:
    if list[i] and list[(i+1)//2]:
      count+=1
  list1.append(count)
n=int(input())
for i in range(n):
  a,b=map(int,input().split())
  print(list1[b]-list1[a-1])


Measured memory_bytes: 5164
#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() {
    long double L;
    cin >> L;
    cout << setprecision(10) << L * L * L / 27.0 << endl;
    return 0;
}

Measured memory_bytes: 256
N=int(input())
A=list(map(int,input().split()))
count=0
max_count=0
for i in range(N-1):
    if A[i]>=A[i+1]:
        count+=1
    else:
        max_count=max(max_count,count)
        count=0
max_count=max(max_count,count)
print(max_count)

Measured memory_bytes: 14252
S = input()
mode = 0
now = 0
k = []
for i in range(len(S)):
    if str(S[i]) == "A" or str(S[i]) == "T" or str(S[i]) == "G" or str(S[i]) == "C":
        if mode == 0:
            mode = 1
            now += 1
        else:
            now += 1
    else:
        k.append(now)
        now = 0
        mode = 0
k.append(now)
if len(k) == 0:
    print(0)
else:
    print(max(k))

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

int t[5002];

int main(){
  int n;

  while(cin >> n, n){
    for(int i = 0; i < n; i++){
      cin >> t[i];
    }

    int ans = INT_MIN;

    for(int i = 0; i < n; i++){
      int sum = 0;

      for(int j = i; j < n; j++){
        sum += t[j];
        ans = max(ans, sum);
      }
    }

    cout << ans << endl;
  }
}

Measured memory_bytes: 1172
#include<bits/stdc++.h>
#ifdef ONLINE_JUDGE
#define endl '\n'
#ifndef CODE_JAM
#undef CASE_INFO
#endif
#else
#pragma GCC optimize "trapv"
#endif
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define rep(n) for(int i = 0; i < n; i++)
#define repj(n) for(int j = 0; j < n; j++)
#define all(p) p.begin(), p.end()
#define count_1(p) __builtin_popcountll(p)
#define count_0(p) __builtin_ctzll(p)
using namespace std;
template<class X=int>inline X mid(X s,X e){return (s+(e-s)/2);}
template<class X=int>inline X len(X s,X e){return (e-s+1);}
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
const int MOD = 1e9 + 7;
const int oo = 987654321;
const ll OO = 1e18;

void solve() {
	int n, d;
	cin >> n >> d;
	vector<pii> A(n);
	rep(n) cin >> A[i].F >> A[i].S;
	function<long long(pii)> dist = [](const pii& a) -> long long {
		return 1LL*a.F*a.F + 1LL*a.S*a.S;
	};
	sort(all(A), [&](const pii &a, const pii &b) {
			return dist(a) < dist(b);
	});
	cout << upper_bound(all(A), d, [&](const int& d, const pii& a){
			return dist(a) > 1LL*d*d;
	}) - A.begin() << endl;
}

signed main() {
	clock_t start = clock();
	int T = 1;
	#ifdef TEST_CASES
	cin >> T;
	#endif
	for(int t = 1; t <= T; t++) {
		#ifdef CASE_INFO
		cout << "Case #" << t << ": ";
		#endif
		solve();
	}
	cerr << (double)(clock() - start)/CLOCKS_PER_SEC << "\n";
	return 0;
}


Measured memory_bytes: 4892
while True:
    try:
        # a >=b
        a, b = sorted(map(int, input().strip("\n").split(" ")), reverse=True)
        d = a * b

        # calc. gcm by　ユークリッド互除法
        while True:
            c = a % b
            # print("{0} {1} {2}".format(a, b, c))
            if c == 0:
                break
            else:
                a, b = sorted([b, a % b], reverse=True)
        gcm = b
        lcm = d / gcm
        # print("gcm is {}".format(b))
        print("{0:d} {1:d}".format(int(gcm), int(lcm)))

        #print("{0} {1}".format(a, b))
        #a, b = sorted([b, a % b], reverse=True)
        #print("{0} {1}".format(a, b))

    except EOFError:
        break  # escape from while loop

Measured memory_bytes: 6732
import sys
N, M, P = map(int, input().split())

Edgeinv = [[] for _ in range(N+1)]
Edge = [[] for _ in range(N+1)]
inf = 2*10**10
Edgenum = [tuple(map(int, sys.stdin.readline().split())) for _ in range(M)]
for a, b, c in Edgenum:
    Edgeinv[b].append(a)
    Edge[a].append(b)

used = set([N])
stack = [N]
while stack:
    vn = stack.pop()
    for vf in Edgeinv[vn]:
        if vf not in used:
            used.add(vf)
            stack.append(vf)

used2 = set([1])
stack = [1]
while stack:
    vn = stack.pop()
    for vf in Edge[vn]:
        if vf not in used2:
            used2.add(vf)
            stack.append(vf)

Edgenum = [(a, b, c) for a, b, c in Edgenum if a in used and b in used]

used &= used2

dp = [-inf]*(N+1)
dp[1] = 0
for i in range(N-1):
    dp2 = dp[:]
    for a, b, c in Edgenum:
        dp2[b] = max(dp2[b], dp[a] + c - P)
    dp = dp2[:]

Dp = dp[:]
for i in range(N):
    dp2 = dp[:]
    for a, b, c in Edgenum:
        dp2[b] = max(dp2[b], dp[a] + c - P)
    dp = dp2[:]

if any(Dp[i] < dp2[i] for i in used):
    print(-1)
else:
    print(max(0, Dp[N]))

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

int main() {
  int K;
  string S;
  cin >> K;
  cin >> S;
  
  if(S.size() <= K){
    cout << S;
  }
  
  else{
    for(int i=0;i < K;i++){
      cout << S.at(i);
  	}
    cout << "...";
  }
}

Measured memory_bytes: 3564
#coding:utf-8
N = int(input())
ls_ab = []
for n in range(N):
    a,b = map(int,input().split())
    ls_ab.append([a,b])
ans = 0
for a,b in ls_ab[::-1]:
    a+=ans
    ans += b - ((a-1) % b + 1)
print (ans)

Measured memory_bytes: 20392
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <climits>

using namespace std;
typedef long long int ll;
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
ll MOD = 1000000007;
#define INF (1e9)

ll gcd(ll a, ll b) { return b ? gcd(b,a%b) : a;}
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
typedef pair <ll,ll> P;


int main()
{
    ll x, a, b;
    cin >> x >> a >> b;
    if (abs(x-a) > abs(x-b)) {
        cout << "B" << endl;
    } else cout << "A" << endl;
    return 0;
}


Measured memory_bytes: 256
import sys
menu = []
for i in range(5):
  menu.append(int(input()))
maxtmp = 0
for i in range(5):
  tmp = 10 - (menu[i] % 10) if menu[i] % 10 else 0
  menu[i] += tmp
  if (maxtmp < tmp):
    maxtmp = tmp
print(sum(menu) - maxtmp)

Measured memory_bytes: 3060
#include <cstdio>
#define N 100005
int n, m, ans, a[N], pr[N];

int f(int p) {
	if(pr[p]==p) return p;
	return pr[p] = f(pr[p]);
}

int main() {
	int i, x, y;
	scanf("%d%d", &n, &m);
	for(i=1; i<=n; i++) scanf("%d", a+i), pr[i] = i;
	while(m--) {
		scanf("%d%d", &x, &y);
		if(f(x) != f(y)) pr[f(y)] = f(x);
	}
	for(i=1; i<=n; i++) if(f(i)==f(a[i])) ans++;
	printf("%d", ans);
	return 0;
}

Measured memory_bytes: 896
#include <bits/stdc++.h>
 
using namespace std;
 
#define rep(i, n) for(int i=0; i<(n); i++)
#define FOR(i, m, n) for(int i=(m);i<(n);i++)
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define SORT(x) sort((x).begin(),(x).end())
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define REVE(x) reverse((x).begin(),(x).end())
#define mp make_pair
#define pb push_back
#define chmax(x,y) x = max(x,y)

 
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<vector<int> > VVI;
typedef pair<int, int> PII;
typedef long long LL;
typedef vector<bool> VB;
typedef vector<LL> VL;
typedef vector<vector<long long>> VVLL;
typedef vector<set<int>> VSI;
const int MOD = 1e9+7;
const int INF = 1e9;
const LL LINF = 1e18;
int gcd(int a, int b)
{
   if (a%b == 0)
   {
       return(b);
   }
   else
   {
       return(gcd(b, a%b));
   }
}

int lcm(int a, int b)
{
   return a * b / gcd(a, b);
}
struct UnionFind {
    VI d;
    UnionFind(int n = 0): d(n,-1) {}
    int find(int x) {
        if(d[x] < 0) return x;
        return d[x] = find(d[x]);
    }
    bool unite(int x,int y) {
        x = find(x); y = find(y);
        if(x == y) return false;
        if(d[x] > d[y]) swap(x,y);
        d[x] += d[y];
        d[y] = x;
        return true;
    }
    bool same(int x,int y) { return find(x) == find(y); }
    int size(int x) { return -d[find(x)]; }
};
int deg[100005];
VI to[100005];

struct mint {
  LL x; // typedef long long ll;
  mint(LL x=0):x((x%MOD+MOD)%MOD){}
  mint operator-() const { return mint(-x);}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x += MOD-a.x) >= MOD) x -= MOD;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= MOD;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
  mint pow(LL t) const {
    if (!t) return 1;
    mint a = pow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  // for prime mod
  mint inv() const {
    return pow(MOD-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.inv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};

mint f(int n) {
    if(n == 0) return 1;
    mint x = f(n/2);
    x *= x;
    if(n%2 == 1) x *= 2;
    return x;
}

mint choose(int n,int a) {
    mint x = 1, y = 1;
    rep(i,a) {
        x *= n-i;
        y *= i+1;
    }
    return x/y;
}		

int main() {
  int x,y;
  cin >> x >> y;

  for(int i = 0 ; i <= 100; i++) {
    for(int j = 0 ; j <= 100; j++) {
      if(i+j == x) {
        if(2*i + 4*j == y) {
          cout << "Yes" << endl;
          return 0;
        }
      }
    }
  }
  cout << "No" << endl;
}


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

vector<int> store(200007, 1e9);

int main()
{
    int n, k;
    cin >> n >> k;
    int tmp;
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        scanf("%d", &tmp);
        if (store[tmp] == 1e9) store[tmp] = 0;
        store[tmp]++;
        if (store[tmp] == 1) cnt++;
    }

    if (cnt <= k) {printf("0\n"); return 0;}

    sort(store.begin(), store.end());

    int ans = 0;
    for (int i = 0; i < n; i++) {
        if (store[i] == 1e9) break;

        ans += store[i];
        cnt--;
        if (cnt-k == 0) break;
    }

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


Measured memory_bytes: 1024
#include<bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
typedef long long ll;
#define rep(i,n) for(ll i=0, i##_len=(n); i<i##_len; ++i)
#define REP(i,num,n) for(ll i=num, i##_len=(n); i<i##_len; ++i)
#define repprev(i,a,b) for(ll i=b-1;i>=a;i--)
#define reprev(i,n) repprev(i,0,n)
using namespace std;
#define sz(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<class T> int former(const vector<T> &v, T x){
   return upper_bound(v.begin(),v.end(),x) - v.begin() - 1;
}
template<class T> int latter(const vector<T> &v, T x){
    return lower_bound(v.begin(),v.end(),x) - v.begin();
}
#define pb push_back
#define mp make_pair
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
#define BIT_FLAG_0 (1<<0) // 0000 0000 0000 0001
#define BIT_FLAG_1 (1<<1) // 0000 0000 0000 0010
#define BIT_FLAG_2 (1<<2) // 0000 0000 0000 0100
#define BIT_FLAG_3 (1<<3) // 0000 0000 0000 1000
#define BIT_FLAG_4 (1<<4) // 0000 0000 0001 0000
#define BIT_FLAG_5 (1<<5) // 0000 0000 0010 0000
#define BIT_FLAG_6 (1<<6) // 0000 0000 0100 0000
#define BIT_FLAG_7 (1<<7) // 0000 0000 1000 0000
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
const ll LLINF = 1LL<<60;
const int INTINF = 1<<29;

const int MAX = 510000;
const int MOD = 1000000007;

long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

struct UnionFind {
    vector<ll> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(ll n) : par(n, -1) { }
    void init(ll n) { par.assign(n, -1); }

    ll root(ll x) {
        if (par[x] < 0) return x;
        else return par[x] = root(par[x]);
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    bool merge(ll x, ll y) {
        x = root(x); y = root(y);
        if (x == y) return false;
        if (par[x] > par[y]) swap(x, y); // merge technique
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    ll size(ll x) {
        return -par[root(x)];
    }
};


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

bool search(vector<int> A, int n, int key){
    int i = 0;
    A[n] = key;
    while(A[i] != key) i++;
    return i != n;
}

int main(void) {
	int n;
	cin >> n;
	vector<int> s(n+1);
	rep(i,n) cin >> s[i];
	int q;
	cin >> q;
	int ans = 0;
	int t;
	rep(i,q) {
           cin >> t;
           if(search(s,n,t)) ans++;
        }
	cout << ans << endl;
	
}


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

using namespace std;
using ll = long long;
using P = pair<int,int>;
using Graph = vector<vector<int>>;

int main(void) {
    int n, k;
    cin >> n  >> k;
    vector<int> x(n);
    rep(i, n) cin >> x[i];

    ll ans = 1e15;
    rep(i,n-k+1) {
        ll left = x[i];
        ll right = x[i+k-1];
        ll tmp = min(abs(left) + abs(right-left), abs(right) + abs(right - left));
        ans = min(ans, tmp);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 640
#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
#define ll long long

int d = 365;
vector<vector<int>> s(d+1, vector<int>(26+1, 0));
vector<int> c(26+1);
vector<int> t(d);

ll calc(vector<int> out) {
    ll score = 0;
    vector<ll> last(26, 0);
    //
    // d = i+1
    for(int i = 0; i < out.size(); i++) {
        last[out[i]] = i+1;
        for(int j = 0; j < 26; j++) {
            score -= c[j]*((i+1)-last[j]);
        }
        score += s[i][out[i]];
    }
    return score;
}

void init() {
    cin >> d;
    for(int i = 0; i < 26; i++) cin >> c[i];
    for(int i = 0; i < d; i++) {
        for(int j = 0; j < 26; j++) {
            cin >> s[i][j];
        }
    }
    return;
}

int main() {
    init();
    /////////////////
    vector<int> t(d, 1);
    //vector<ll> ans(d, 0);
    vector<ll> last1(26+1, 0), last2(26+1, 0);
    vector<ll> last(26+1, 0);
    vector<int> out;
    ll v = 0;
    ll tmp1 = 0, tmp2 = 0;
    ll ans = 0;
    ll tmp = 0;
    for(int i = 0; i < d; i++) {
        ll max_v = 0;
        int best = 0;
        for(int j = 0; j < 26; j++) {
            out.push_back(j);
            tmp = calc(out);
            if(max_v < tmp) {
                max_v = tmp;
                best = j;
            }
            out.pop_back();
            /*
            if(tmp2 < tmp1) {
                tmp2 = tmp1;
                last1 = last2;
                last2[j] = i+1;
                t[i] = j+1;
                last[j] = i+1;
                best = j+1;
            }
            */
            // v -= c[j]*((i+1)-last[j]);
        }
        out.push_back(best);
        //cout << max_v << endl;
    }
    
    for(int i = 0; i < d; i++) {
        //cout << "i: " << i << " " << t[i] << endl;
        cout << out[i]+1 << endl;
    }
    //cout << max_v << endl;
    return 0;
}

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

int main(){
  int A,B;
  cin>>A>>B;
  int a;
  
  while(A<=B){
    int S;
    S=A;
    int i;
    int A2=0;
    for(i=1;i<=5;i++){
      int x,v;
      x=S%10;
      S=S/10;
      v=A2*10;
      A2=x+v;
      }
    if(A2==A){
      a=a+1;
    }
    A=A+1;
  }
  
  cout<<a<<endl;
}

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

using namespace std;

int h, w;
vector<string> grid;

void checkAndErase() {
    for (int i = h - 1; i >= 0; --i) {
        bool flag = true;
        for (int j = 0; j < w; ++j) {
            if (grid[i][j] == '#') {
                flag = false;
                break;
            }
        }

        if (flag) {
            grid.erase(grid.begin() + i);
        }
    }

    h = grid.size();
    if (h == 0) return; 

    w = grid[0].size();

    for (int i = w - 1; i >= 0; --i) {
        bool flag = true;
        for (int j = 0; j < h; ++j) {
            if (grid[j][i] == '#') {
                flag = false;
                break;
            }
        }

        if (flag) {
            for (int j = 0; j < h; ++j) {
                auto idx = grid[j].begin() + i;
                grid[j].erase(idx, idx + 1);
            }
        }
    }
}

void print() {
    for (auto e: grid) {
        cout << e << endl;
    }
}

int main() {
    scanf("%d %d", &h, &w);
    for (int i = 0; i < h; ++i) {
        string str; cin >> str;
        grid.push_back(str);
    }

    checkAndErase();
    print();

    return 0;
}

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

using ll=long long;
int main(){
    int h,w;
    cin>>h>>w;
    ll m;
    cin>>m;
    vector<string> a(h);
    for(int i=0;i<h;i++) cin>>a[i];

    vector<vector<ll>> dpP(h,vector<ll>(w));
    vector<vector<ll>> dpM(h,vector<ll>(w));
    ll ans=0;
    dpP[0][0]=a[0][0]-'0';
    dpM[0][0]=1;

    const int SIZE=5000;
    vector<vector<ll>> comb(SIZE,vector<ll>(SIZE,1));
    for(int i=2;i<SIZE;i++){
        for(int j=1;j<i;j++){
            comb[i][j]=(comb[i-1][j-1]+comb[i-1][j])%m;
        }
    }
    auto Move=[&](int ti,int tj,int fi,int fj){
        if(a[ti][tj]=='*'){
            dpP[ti][tj]+=dpP[fi][fj];
            dpM[ti][tj]+=dpP[fi][fj];
        }
        else if(a[ti][tj]=='+'){
            ans+=dpP[fi][fj]*comb[h-1-ti+w-1-tj][h-1-ti];
            ans%=m;
            dpP[ti][tj]=dpM[ti][tj]=comb[ti+tj][ti];
        }
        else{
            int d=(a[ti][tj]-'0');
            if(isdigit(a[fi][fj])){
                dpP[ti][tj]+=dpP[fi][fj]*10+dpM[fi][fj]*d;
                dpM[ti][tj]+=dpM[fi][fj];
            }
            else{
                dpP[ti][tj]+=dpM[fi][fj]*d;
                dpM[ti][tj]+=dpM[fi][fj];
            }
        }
        dpP[ti][tj]%=m;
        dpM[ti][tj]%=m;
    };
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            if(i+1<h) Move(i+1,j,i,j);
            if(j+1<w) Move(i,j+1,i,j);
        }
    }
    ans+=dpP[h-1][w-1];

    
    ans%=m;
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 261824
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <bits/stdc++.h>
using namespace std;

int charKind(int n, string s){
  int ans = 0;

  for(int i = 1; i < n; i++){ 
    int kinds = 0;
    for(char c = 'a'; c <= 'z'; c++){
    bool left = false, right = false;
      /*左の探索*/
      for(int j = 0; j < i; j++)
        if(s[j] == c)
          left = true;

      /*右の探索*/
      for(int j = i; j < n; j++)
        if(s[j] == c)
          right = true;

      /*左右が同じ文字か比較*/
      if(left && right)
        kinds++;
    }
    if(ans < kinds)
      ans = kinds;
  }
  return ans;
}


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

  cout << charKind(n, s) << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <queue>
#include <deque>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, up) for (ll i = 0; i < up; ++i)
#define repp(i, up) for (ll i = 0; i <= up; ++i)
#define rrep(i, lo, up) for (ll i = lo; i < up; ++i)
#define rrepp(i, lo, up) for (ll i = lo; i <= up; ++i)
#define eep(i, lo, up) for ((i) = (lo); (i) < (up); ++(i))
#define eepp(i, lo, up) for ((i) = (lo); (i) <= (up); ++(i))

#define rdi(i) ll i; scanf("%lld", &i)
#define rds(s) string s; cin >> s
#define rdc(c) char c; cin >> c

#define INF 10000000000
#define MOD 1000000007

ll gcd(ll a, ll b)
{
    if (a < b) {
        return gcd(b, a);
    }
    ll r;
    while (r = a % b) {
        a = b;
        b = r;
    }
    return b;
}

int main()
{
    ll n, m, q;
    cin >> n >> m >> q;
    vector<pair<pair<ll, ll>, pair<ll, ll>>> qs(q);
    rep(i, q) {
        cin >> qs[i].first.first >> qs[i].first.second >> qs[i].second.first >> qs[i].second.second;
        --qs[i].first.first;
        --qs[i].first.second;
    }

    vector<ll> is(10);
    ll result = 0;
    eepp(is[0], 1, m) {
        eepp(is[1], is[0], m) {
            eepp(is[2], is[1], m) {
                eepp(is[3], is[2], m) {
                    eepp(is[4], is[3], m) {
                        eepp(is[5], is[4], m) {
                            eepp(is[6], is[5], m) {
                                eepp(is[7], is[6], m) {
                                    eepp(is[8], is[7], m) {
                                        eepp(is[9], is[8], m) {

                                            ll work = 0;

                                            rep(i, q) {
                                                ll a = qs[i].first.first;
                                                ll b = qs[i].first.second;
                                                ll c = qs[i].second.first;
                                                ll d = qs[i].second.second;

                                                if (is[b] - is[a] == c) {
                                                    work += d;
                                                }
                                            }

                                            result = max(result, work);
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << result << endl;
    return 0;
}

Measured memory_bytes: 3192
#include "bits/stdc++.h"
using namespace std;

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

#define fill(a,x) memset(a,x,sizeof(a))
#define pb push_back
#define sz(x) (int)x.size()
#define F first
#define S second
#define FOR(i,a,b) for(int i = a; i<=b; ++i)
#define NFOR(i,a,b) for(int i = a; i>=b; --i)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
const ll INF = 1e18;
const ll mod = 1e9+7;
const int N = 5e5+10;

int a[N];
int main(){
fast;

int n,k;
cin>>n>>k;

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

sort(a,a+n);

int ans =0;
for(int i=0;i<k;i++) {
    ans+=a[i];
}

cout<<ans<<endl;
return 0;
}

Measured memory_bytes: 3648
n,m=gets.split.map(&:to_i)
xs = gets.split.map(&:to_i).sort
distances = Array.new(m-1)

(0..xs.length-2).each_with_index do |_, i|
  distances[i] = xs[i+1]-xs[i]
end

distances = distances.sort
p distances[0..-n].inject(:+) || 0

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

int main(){
  int a,b,n;
  cin >> n >> a;
  int rslt = 1;
  for(int i=1;i<n;i++)
  {
    cin >> b;
    if(a<=b){rslt++;a=b;}
  }
  cout << rslt;
}

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

using namespace std;

const int N = 1e5 + 1;

int n;
int a[N][4], cache[N][4];

int dp(int i, int act) {
    if (i > n) return 0;
    if (cache[i][act] != -1) return cache[i][act];

    int ans = 0;

    for (int j = 1; j <= 3; j++) {
        if (j == act) continue;
        ans = max(ans, dp(i + 1, j) + a[i][act]);
    }

    return cache[i][act] = ans;
}

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

    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int act = 1; act <= 3; ++act) {
            cin >> a[i][act];
        }
    }

    fill(*cache, *cache + N * 4, -1);

    cout << max({dp(1, 1), dp(1, 2), dp(1, 3)});

    return 0;
}



Measured memory_bytes: 14424
#include <bits/stdc++.h>
 
#define _overload(_1,_2,_3,name,...) name
#define _rep(i,n) _range(i,0,n)
#define _range(i,a,b) for(int i=(int)(a);i<(int)(b);++i)
#define rep(...) _overload(__VA_ARGS__,_range,_rep,)(__VA_ARGS__)
 
#define _rrep(i,n) _rrange(i,n,0)
#define _rrange(i,a,b) for(int i=(int)(a)-1;i>=(int)(b);--i)
#define rrep(...) _overload(__VA_ARGS__,_rrange,_rrep,)(__VA_ARGS__)
 
#define _all(arg) begin(arg),end(arg)
#define uniq(arg) sort(_all(arg)),(arg).erase(unique(_all(arg)),end(arg))
#define getidx(ary,key) lower_bound(_all(ary),key)-begin(ary)
#define clr(a,b) memset((a),(b),sizeof(a))
#define bit(n) (1LL<<(n))
 
// #define DEBUG
 
#ifdef DEBUG
    #define dump(...) fprintf(stderr, __VA_ARGS__)
#else
    #define dump(...)
#endif
 
template<class T>bool chmax(T &a, const T &b) { return (a<b)?(a=b,1):0;}
template<class T>bool chmin(T &a, const T &b) { return (b<a)?(a=b,1):0;}
 
using namespace std;
using ll=long long;
using vi=vector<int>;
using vll=vector<ll>;
 
const double EPS = 1e-10;
const double PI = acos(-1.0);
const ll inf =1LL << 62;
const ll mod=1000000007LL;
const int dx[4]={1,0,-1,0};
const int dy[4]={0,1,0,-1};
 
 
ll extgcd(ll a,ll b,ll& x,ll& y){x=1,y=0;ll g=a;if(b!=0) g=extgcd(b,a%b,y,x),y-=a/b*x;return g;}
ll ADD(const ll &a, const ll &b,const ll &mod) { return (a+b)%mod;}
ll SUB(const ll &a, const ll &b,const ll &mod) { return (a-b+mod)%mod;}
ll MUL(const ll &a, const ll &b,const ll &mod) { return (1LL*a*b)%mod;}
ll DIV(const ll &a, const ll &b,const ll &mod) {ll x,y; extgcd(b,mod,x,y);return MUL(a,(x+mod)%mod,mod);}
 
random_device rd;
mt19937 mt(rd());
uniform_int_distribution<int> dice(1,6);
uniform_real_distribution<double> score(0.0,10.0);

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

    ll Q;
    for(int n, S, W; cin >> n >> S >> W >> Q, n;){
        vll a(n);
        {
            int g = S;
            rep(i, n){
                a[i] = (g / 7) % 10;
                if(g % 2 == 0) g = (g / 2);
                else           g = (g / 2) ^ W;
            }
        }

        int res = 0;
        if(Q == 2 or Q == 5){
            int nzero = 0;
            rep(i, n){
                if(a[i] != 0) nzero++;
                if(a[i] % Q == 0) res += nzero;
            }
        }
        else {
            vll sum(n + 1);
            ll k = 1LL;
            rrep(i, n){
                sum[i] = ADD(MUL(a[i], k, Q), sum[i + 1], Q);
                k = MUL(k, 10LL, Q);
            }

            map<ll, int> dic;
            rep(i, n){
                if(a[i] != 0) dic[sum[i]]++;
                res += dic[sum[i + 1]];
            }
        }

        cout << res << endl;
    }

    return 0;
}

Measured memory_bytes: 9988
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y,cot=0,sum=0;
    int a[]={1,3,5,7,8,10,12},b[]={4,6,9,11};
    cin>>x>>y;
    if(x>=1 && y<=12)
    {
        for(int i=0;i<7;i++)
        {
            if(a[i]==x) cot++;
            if(a[i]==y) cot++;
            if(cot==2) break;
        }
        if(cot!=2)
        {
            for(int i=0 ;i<4 ;i++)
            {
                if(b[i]==x) sum++;
                if(b[i]==y) sum++;
                if(sum==2) break;
            }
        }
        if(sum==2 || cot ==2) cout<<"Yes\n";
        else cout<<"No\n";
    }

    return 0;
}


Measured memory_bytes: 256
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,x = map(int,input().split())
    s = [list(map(int,input().split())) for i in range(n)]
    ans = float("inf")

    for b in range(1<<n):
        cost = 0
        k = [0]*m
        for i in range(n):
            if b&(1<<i): #i番の本を選んでいたら
                cost += s[i][0] #i番の本の値段を足す
                for j in range(m):
                    k[j] += s[i][j+1] #選んだ本で得られる理解度をトピックごとに合計していく
        if cost < ans and all([i >= x for i in k]):
            ans = cost
    if ans == float("inf"):
        print(-1)
    else:
        print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()


Measured memory_bytes: 69112
import java.io.IOException;
import java.io.InputStream;
import java.util.NoSuchElementException;

public class Main {
    public static void main(String[] args) {
        FS fs = new FS();
        int n = fs.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++){
            a[i]= fs.nextInt();
        }
        int p = partition(a, 0, n - 1);
        StringBuilder sb = new StringBuilder();
        for (int i=0;i<a.length;i++){
            if (i==p){
                sb.append("["+a[i]+"] ");
                continue;
            }
            sb.append(a[i]+" ");
        }
        sb.deleteCharAt(sb.length()-1);
        System.out.println(sb);
    }

    private static int  partition(int[] a, int p, int r) {
        int x = a[r];
        int i = p-1;
        for (int j =p;j<r;j++){
            if (a[j]<=x){
                i++;
                exchange(a,j,i);
            }
        }
        exchange(a,i+1,r);
        return i+1;
    }

    private static void exchange(int[] a,int i, int j) {
        int tep = a[j];
        a[j]=a[i];
        a[i]=tep;
    }
  static  class FS {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int buflen = 0;

    private boolean hasNextByte() {
        if (ptr < buflen) {
            return true;
        } else {
            ptr = 0;
            try {
                buflen = in.read(buffer);
            } catch (IOException e) {
                e.printStackTrace();
            }
            if (buflen <= 0) {
                return false;
            }
        }
        return true;
    }

    private int readByte() {
        return hasNextByte() ? buffer[ptr++] : -1;
    }

    private boolean isPrintableChar(int c) {
        return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
        while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    public boolean hasNext() {
        skipUnprintable();
        return hasNextByte();
    }

    public String next() {
        if (!hasNext()) throw new NoSuchElementException();
        StringBuilder sb = new StringBuilder();
        int b = readByte();
        while (isPrintableChar(b)) {
            sb.appendCodePoint(b);
            b = readByte();
        }
        return sb.toString();
    }

    public int nextInt() {
        return (int) nextLong();
    }

    public long nextLong() {
        if (!hasNext()) throw new NoSuchElementException();
        long n = 0;
        boolean minus = false;
        int b = readByte();
        if (b == '-') {
            minus = true;
            b = readByte();
        }
        if (b < '0' || '9' < b) {
            throw new NumberFormatException();
        }
        while (true) {
            if ('0' <= b && b <= '9') {
                n *= 10;
                n += b - '0';
            } else if (b == -1 || !isPrintableChar(b)) {
                return minus ? -n : n;
            } else {
                throw new NumberFormatException();
            }
            b = readByte();
        }
    }
}
}


Measured memory_bytes: 43244
def solve(K):
    a = 7 % K
    for i in range(1, K+1):
        if a == 0:
            return i
        a = (a * 10 + 7) % K
    return -1 

        

def solve0(K):
    a = 7
    for i in range(0, 10000):
        if a % K == 0:
            return i
        a = a*10+7
    return -1

K = int(input())
print(solve(K))


Measured memory_bytes: 9052
object Main extends App {
  val inputs: Seq[String] = scala.io.Source.stdin.getLines().toList
  
  val nums = inputs.head.split(" ").map(_.toInt)
  val animals = nums(0)
  val legs    = nums(1)

  println(solve(animals, legs))

  def solve(animals: Int, legs: Int): String = {
    // 足の数が偶数でない場合No
    if (legs % 2 == 0) {
      // 4で割り切れない奇数は繰り上げ
      val bird = legs / 2
      val kame = scala.math.ceil(legs / 4.asInstanceOf[Double]).toInt

      if ((kame to bird).contains(animals)) {
        return "Yes"
      }
    }

    return "No"
  }
}

Measured memory_bytes: 54864
var
  x, y, s: longint;
begin
  read(x, y);
  case x of
    1: inc(s, 300000);
    2: inc(s, 200000);
    3: inc(s, 100000);
  end;
  case y of
    1: inc(s, 300000);
    2: inc(s, 200000);
    3: inc(s, 100000);
  end;
  if (x = 1) and (y = 1) then inc(s, 400000);
  writeln(s);
end.


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

int comp(const void* a, const void* b){
	return *(int*)a - *(int*)b;
}

int main() {
	string r, g, b, ans;
	int answ;
	cin >> r >> g >> b;
	ans = g + b;
	answ = atoi(ans.c_str());
	if(answ % 4 == 0){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}
}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <numeric>
#include <list>
#include <assert.h>
#include <math.h>
#include <valarray>
#include <stdio.h>
#include <algorithm>
#include <set>
#include <complex>
#include <list>

using namespace std;
typedef long long int LL;
typedef pair<long long int, long long int> pii;
typedef pair<double, double> pdd;

#define SORT(c) sort((c).begin(),(c).end())
#define BACKSORT(c) sort((c).begin(),(c).end(),std::greater<LL>())
#define FOR(i,a,b) for(LL i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)

LL pow(LL a,LL b) {
	if (b == 1) {
		return a;
	}else
		if (b == 0) {
			return 1;
		}else
			if (b % 2 == 0) {
				return pow(a, (LL)(b / 2))*pow(a, (LL)(b / 2));
			}
			else {
				return a*pow(a, (LL)((b-1) / 2))*pow(a, (LL)((b - 1) / 2));
			}
}

int main()
{
	LL N, A;
	cin >> N >> A;
	LL cost = N;
	LL n = 2;
	
	LL Nsqrt = (LL)floor(sqrt(N));
	LL m = 0;
	LL k = 1;
	while (true) {
		if (n - m >= 0 && pow(Nsqrt, n - m)*pow(Nsqrt + 1, m) < N) {
			m++;
		}
		else {
			while (true) {
				if (Nsqrt != 1 && n - m - k >= 0 && pow(Nsqrt, n - m - k)*pow(Nsqrt + 1, m)*pow(Nsqrt - 1, k) >= N) {
					k++;
				}
				else {
					k--;
					break;
				}
			}
			break;
		}
	}
	LL newcost = Nsqrt*(n-m-k)+ (Nsqrt + 1)*m+ (Nsqrt - 1)*k + A*(n - 1);
	if (newcost < cost) {
		cost = newcost;

		while (true) {
			n++;

			FOR(i, 1, Nsqrt) {
				if (pow(i,n) >= N) {
					Nsqrt = i-1;
					
					break;
				}
			}
			m = 0;
			k = 1;
			while (true) {
				if (n-m>=0&&pow(Nsqrt, n - m)*pow(Nsqrt + 1, m) < N) {
					m++;
				}
				else {
					while (true) {
						if (Nsqrt!=1&&n - m - k >= 0 && pow(Nsqrt, n - m - k)*pow(Nsqrt + 1, m)*pow(Nsqrt - 1, k) >= N) {
							k++;
						}
						else {
							k--;
							break;
						}
					}
					break;
				}
			}
			newcost = Nsqrt*(n - m - k) + (Nsqrt + 1)*m + (Nsqrt - 1)*k + A*(n - 1);
			if (newcost > cost) {
				break;
			}
			else {
				cost = newcost;
			}
			if (Nsqrt == 1) { break; }
		}
	}

	cout << cost << endl;
	
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

#define INF 1<<30
#define LINF 1ll<<60ll
#define MOD 1000000007
#define pb(a) push_back(a)

#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload3(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)

#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)

#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))

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

#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl

int main(){
    int n,m;
    cin>>n;
    vi t(n);
    int sum=0;
    REP(i,n){
        cin>>t[i];
        sum+=t[i];
    }
    cin>>m;
    REP(i,m){
        int p,x;
        cin>>p>>x;
        cout<<sum-(t[p-1]-x)<<endl;
    }
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100000
#define NIL -1

struct Node_struct{int p, l, r, s;}; 
typedef struct Node_struct Node;

void print(int );
void calcDepth(int ,int );
int Height(int );
int sib(int );

Node T[MAX];
int D[MAX],H[MAX];

int main()
{
  int i,l,r,n,id,root = NIL;
  scanf("%d",&n);
  for(i = 0;i < n;i++) T[i].p = T[i].l = T[i].r = NIL;
  for(i = 0;i < n;i++)
    {
      scanf("%d %d %d",&id,&l,&r);
      T[r].p = T[l].p = id;
      T[id].l = l;
      T[id].r = r;
    }
  for(i=0; i<n; i++)
    {
      if(T[i].p == -1) root = i;
    }
  calcDepth(root, 0);
  Height(root);

  for(i = 0;i < n;i++) print(i);
  
  return 0;
}
void calcDepth(int u, int p)
{
  if(u == NIL) return;
  D[u] = p;
  calcDepth(T[u].r,p + 1);
  calcDepth(T[u].l,p + 1);
}
void print(int u)
{
  int deg = 0;
  printf("node %d: parent = %d, sibling = %d, ", u, T[u].p,sib(u));
  if( T[u].l != NIL)deg++;
  if( T[u].r != NIL)deg++;
  printf("degree = %d, ",deg);
  printf("depth = %d, height = %d, ",D[u],H[u]);
  if(T[u].p == NIL) printf("root");
  else if(T[u].l == NIL && T[u].r == NIL) printf("leaf");
  else printf("internal node");
  printf("\n");
}
int Height(int u)
{
  int a = 0,b = 0;
  if(T[u].l != NIL)
    {
      a = Height(T[u].l) + 1;
    }
  if(T[u].r != NIL)
    {
      b = Height(T[u].r) + 1;
    }
  if(a > b) return H[u] = a;
  else return H[u] = b;
}
int sib(int u)
{
  if(T[u].p == NIL) return NIL;
  if(T[T[u].p].l != u && T[T[u].p].l != NIL) return T[T[u].p].l;
  if(T[T[u].p].r != u && T[T[u].p].r != NIL) return T[T[u].p].r;
  return NIL;
}
  
  

  
      
      
      



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

static const int N = 1000;

int lcs(string X, string Y) {
	int c[N + 1][N + 1];
	int m = X.size();
	int n = Y.size();
	c[0][0] = 0;
	int maxl = 0;
	X = ' ' + X;
	Y = ' ' + Y;
	for (int i = 1; i <= m; i++) c[i][0] = 0;
	for (int i = 1; i <= n; i++) c[0][i] = 0;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (X[i] == Y[j]) { 
				c[i][j] = c[i - 1][j - 1] + 1; 
			}else{
				c[i][j] = max(c[i - 1][j], c[i][j - 1]);
			}
			maxl = max(maxl, c[i][j]);
		}
	}
	return maxl;
}

int main()
{
	int n;
	string s1, s2;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> s1 >> s2;
		cout << lcs(s1, s2) << endl;
	}
    return 0;
}

Measured memory_bytes: 6928