akhauriyash/Code-Regression huggingface dataset:
using System;

namespace AtCoder
{
    class Program
    {
        static void Main(string[] args)
        {
            string[] n = Console.ReadLine().Split();
            int N = int.Parse(n[0]);
            int X = int.Parse(n[1]);
            int T = int.Parse(n[2]);
            if(N%X==0)
            {
                Console.WriteLine(T * N / X);
            }
            else
            {
                Console.WriteLine(T * (N / X + 1));
            }
        }
    }
}

Measured memory_bytes: 27516
#include <bits/stdc++.h>
#define xx first
#define yy second
#define mp make_pair
#define pb push_back
#define fill( x, y ) memset( x, y, sizeof x )
#define copy( x, y ) memcpy( x, y, sizeof x )
using namespace std;

typedef long long LL;
typedef pair < int, int > pa;

inline int read()
{
	int sc = 0, f = 1; char ch = getchar();
	while( ch < '0' || ch > '9' ) { if( ch == '-' ) f = -1; ch = getchar(); }
	while( ch >= '0' && ch <= '9' ) sc = sc * 10 + ch - '0', ch = getchar();
	return sc * f;
}

const int MAXN = 200020;

int q[MAXN], p[MAXN], n, T[MAXN], f[MAXN];

int main()
{
#ifdef wxh010910
	freopen( "data.in", "r", stdin );
#endif
	n = read();
	for( int i = 1 ; i <= n ; i++ ) q[ p[ i ] = read() ] = i;
	for( int i = n - 1 ; i ; i-- )
	{
		if( !T[ i + 1 ] )
		{
			if( q[ i ] > q[ i + 1 ] ) T[ i ] = 1, f[ i ] = i + 1;
			else T[ i ] = 0;
		}
		else
		{
			int cnt = 0;
			cnt += q[ f[ i + 1 ] ] < q[ i ];
			cnt += q[ i ] < q[ i + 1 ];
			cnt += q[ i + 1 ] < q[ f[ i + 1 ] ];
			if( cnt == 2 ) T[ i ] = T[ i + 1 ], f[ i ] = f[ i + 1 ];
			else T[ i ] = T[ i + 1 ] + 1, f[ i ] = i + 1;
		}
	}
	return printf( "%d\n", T[ 1 ] ), 0;
}


Measured memory_bytes: 3328
#include <iostream>
#include <string>
#include <vector>
#include <cmath>


using namespace std;
void chmin(int &a, int b) { if (a > b)a = b; }
//↑参照渡し:ポインタ私と同様、引数に用いた値も書き換えられるが
//中身は通常引数と同様に書ける

int N, A, B, C;
vector<int> L;


//DFSによる再帰
int rec(int i, int a, int b, int c) {
	if (i == N) {
		if (!a || !b || !c)return 50000;//A,B,Cいずれも竹は一本は使う
		return abs(a - A) + abs(b - B) + abs(c - C);//合体してできたa,b,cをA,B,Cにするコスト
	}

	//今ある竹を採用しない場合
	int res = rec(i + 1, a, b, c);

	//A,B,Cを使う場合
	chmin(res, rec(i + 1, a + L[i], b, c) + (a ? 10 : 0));
	chmin(res, rec(i + 1, a, b + L[i], c) + (b ? 10 : 0));
	chmin(res, rec(i + 1, a, b, c + L[i]) + (c ? 10 : 0));

	return res;

}



int main() {

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

	cout << rec(0, 0, 0, 0) << endl;

	return 0;
}



Measured memory_bytes: 256
n,k = map(int,input().split())	
a = list(map(int,input().split()))
ans = []

w = a.index(1)
if w%(k-1) ==0:
    x = w//(k-1)
else:
    x = w//(k-1) + 1

if (n-w-1)%(k-1) == 0:
    y = (n-w-1)//(k-1)
else:
    y = (n-w-1)//(k-1) + 1
ans.append(x+y)

for i in range(k):
    r = w-i
    if r%(k-1) ==0:
        x = r//(k-1)
    else:
        x = r//(k-1) + 1
    
    p = w+k-1-i
    if (n-p-1)%(k-1) == 0:
        y = (n-p-1)//(k-1)
    else:
        y = (n-p-1)//(k-1) + 1
    ans.append(x+y+1)

print(min(ans))

Measured memory_bytes: 14008
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define int ll
const int N=2e6+2;
int dp[N][2];
string s;int n;
int solve(int idx, int c)
{
	if(idx==n)return c;
	int &ret=dp[idx][c];
	if(ret!=-1)return ret;
	int val=s[idx]-'0';val+=c;
	ret=1e9;
	if(val<10)ret=min(ret,solve(idx+1,0)+val);
	ret=min(ret,solve(idx+1,1)+10-val);
	return ret;
}
int32_t main()
{
	#ifndef ONLINE_JUDGE
		freopen("in","r",stdin);
		freopen("out","w",stdout);
	#endif
	cin>>s;n=s.size();
	reverse(s.begin(),s.end());
	memset(dp,-1,sizeof dp);
	cout<<solve(0,0);


}

Measured memory_bytes: 98180
#include <stdio.h>

int main()
{
    int k, a, b, flag=0, i;
    scanf("%d %d %d", &k, &a, &b);
    for (i=a; i<=b; i++) {
        if (i%k==0) {
            flag=1;
            break;
        }
    }
    if (flag) printf("OK\n");
    else printf("NG\n");
    return 0;
}


Measured memory_bytes: 1616
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int main() {
	ll a, b, k;
	cin >> k >> a >> b;
	for (int i = 0; i * k <= b; i++)
	{
		if (a <= i * k && i * k <= b)
		{
			cout << "OK" << endl;
			return 0;
		}
	}
	cout << "NG" << endl;
	return 0;
}

Measured memory_bytes: 3592
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<iomanip>
#include<set>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=1e+18+1;
int INF=1e+9+1;
int main(){
	int N,K;
	scan(N>>K);
	if(K>(N-1)*(N-2)/2){
		prin(-1);
	}
	else{
		int M=N-1+((N-1)*(N-2)/2-K);
		prin(M);
		rep(i,N-1){
			printf("%d %d\n",1,i+2);
			M--;
		}
		for(int i=2;i<=N&&M>0;i++){
			for(int j=i+1;j<=N&&M>0;j++){
				printf("%d %d\n",i,j);
				M--;
			}
		}
	}
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int prime(int n)
{
    if(n<2)
    {
        return 0;
    }
    for(int i=3; i<=sqrt(n); i=i+2)
    {
        if(n%i==0)
        {
            return 0;
        }
    }
    return  1;
}
int main()
{
    int n;
    cin>>n;
    if(n==2)
    {
        cout<<2<<endl;
        return 0;
    }
    if(n%2==0)
    {
        n=n+1;
    }
    while(1)
    {
        if(prime(n))
        {
            cout<<n<<endl;
            return 0;
        }
        n=n+2;
    }

}

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

long a, b, g;

long gcd(long a, long b)
{
    if (a < b) swap(a, b);
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main()
{
    while (cin >> a >> b) {
        g = gcd(a, b);
        cout << g << " " << (a * b / g) << endl;
    }
    return 0;
}



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


#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <set>
#include <functional>
#include <cmath>
#include <numeric>
#include <iterator>

#define SIZE 100005
#define MOD 1000000007

using namespace std;

class CIrohasObsession {
public:
    int func(string price, int n, set<string> diff) {
        if (price != "") {
            int int_price = stoi(price);
            if (int_price >= n) {
                return int_price;
            } else if (int_price == 0) {
                return 100000000;
            }
        }
        int ans = 100000000;
        for (const auto &item : diff) {
            ans = min(ans, func(price + item, n, diff));
        }
        return ans;
    }

    void solve(std::istream &cin, std::ostream &cout) {
        int n, k;
        cin >> n >> k;
        set<string> set_dont_use;
        set<string> set_all{"1", "2", "3", "4", "5", "6", "7", "8", "9", "0"};
        for (int i = 0; i < n; ++i) {
            string tmp;
            cin >> tmp;
            set_dont_use.insert(tmp);
        }
        set<string> set_diff;
        set_difference(set_all.begin(), set_all.end(), set_dont_use.begin(), set_dont_use.end(),
                       inserter(set_diff, set_diff.end()));
        cout << func("", n, set_diff) << endl;
    }
};


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


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <iterator>
#include <climits>


#define rep(i, n) for(int i = 0, end = (int)(n); i < end; i++)

using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

inline int ctoi(char c) {
    return (int)(c -'0');
}

// ----------------------------------------------------------

int main() {
    string s;
    ll k;
    cin >> s;
    cin >> k;
    ll ans = 0;
    
    ll one_count = 0;
    ll target_ans;
    rep(i, s.length()) {
        if (s[i] == '1') {
            ++one_count;
        } else {
            target_ans = (ll)ctoi(s[i]);
            break;
        }
    }
    if (k <= one_count) {
        cout << '1' << endl;
    } else {
        cout << target_ans << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#import sys
#sys.setrecursionlimit(500000)　マージテクをちゃんとしていればこんなものはいらないはず……

class UF:
    #経路圧縮＋マージテクのunion find木
    def __init__(self,n):
        self.n = n
        self.parents = [-1] * (n+1) #1-indexedにするために１個足している
        self.rnks = [0] * (n+1)

    def find(self,n):
        if self.parents[n] < 0:
            return n
        else:
            return self.find(self.parents[n])


    def union(self,a,b):
        a_par = self.find(a)
        b_par = self.find(b)

        if a_par == b_par:
            return
        #union by rank
        if self.rnks[a_par] < self.rnks[b_par]: #ランクの高い方の根に低い方の根をつける　逆にしないように……！
            a_par,b_par = b_par,a_par
        if self.rnks[a_par] == self.rnks[b_par]:
            self.rnks[a_par] += 1
##        if self.size(a_par) < self.size(b_par): #parentsの値が負の数のとき、それはその木のサイズを表す。
##            a_par,b_par = b_par,a_par
        self.parents[a_par] += self.parents[b_par]
        self.parents[b_par] = a_par

    def size(self,n):
        par = self.find(n)
        return abs(self.parents[par])

    def is_same(self,a,b):
        return self.find(a) == self.find(b)



def main():
    n,m,k = map(int,input().split())
    uf = UF(n)
    block_lst = [0 for _ in range(n+1)]
    friend_lst = [0 for _ in range(n+1)]
    #友達リスト部分
    for i in range(m):
        a,b = map(int,input().split())
        friend_lst[a] += 1
        friend_lst[b] += 1
        uf.union(a,b)
    #print(friend_lst)

    #ブロックリスト部分
    for i in range(k):
        c,d = map(int,input().split())
        if uf.is_same(c,d):#c,dが同じ友達候補グループにない限り、解答には影響しない！
            block_lst[c] += 1
            block_lst[d] += 1
    #print(block_lst)
    #メイン処理
    answer = []

    for i in range(1,n+1):
        f_o_f = uf.size(i)
        answer.append(f_o_f - friend_lst[i] - block_lst[i] - 1)


    print(" ".join(map(str,answer)))






if __name__ == '__main__':
    main()


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

#define ll long long

ll dp[101][100005];
int w,n;
int a[101],b[101];

ll func(int pos,int capacity)
{
    if(pos==n)return 0LL;

    if(dp[pos][capacity]!=-1)return dp[pos][capacity];

    ll re=0,re1=0;

    if(capacity+a[pos]<=w)re+=b[pos]+func(pos+1,capacity+a[pos]);

    re1=func(pos+1,capacity);

    return dp[pos][capacity]=max(re,re1);

}

int main()
{
    memset(dp,-1,sizeof dp);

    scanf("%d%d",&n,&w);

    for(int i=0;i<n;i++)scanf("%d%d",a+i,b+i);

    printf("%lld\n",func(0,0));

    return 0;

}


Measured memory_bytes: 79104
#include <bits/stdc++.h>
#define PI 3.14159265359
#define NIL (-1)
#define LL long long
using namespace std;
const int64_t MOD = 1e9 + 7;
const int INF = INT_MAX;

int main() {
	int N, K;
	string S;
	cin >> N >> S >> K;

	char ch = S[K - 1];
	for (int i = 0; i < N; i++) {
		if (S[i] != ch) cout << '*';
		else cout << S[i];
	}
	cout << endl;
}

Measured memory_bytes: 3624
possible=[1,6,9,6**2,6**3,6**4,6**5,6**6,9**2,9**3,9**4,9**5]
dp=[10**18]*(10**5+1)
dp[0]=0
n=int(input())
for i in range(1,n+1):
  for j in possible:
    if i-j>=0:
      dp[i]=min(dp[i],1+dp[i-j])
print(dp[n])

Measured memory_bytes: 41836
#include <stdio.h>
#define N 8

int row[N], col[N], dpos[2*N-1], dneg[2*N-1];
int X[N][N];
 
void init(){
  int i, j;
  for(i=0; i<N; i++) row[i] = col[i] = 0;
  for(i=0; i<2*N-1; i++) dpos[i] = dneg[i] = 0;
  for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
      X[i][j] = 0;
    }
  }
}
 
void printBoard(){
  int i, j;
  for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
      if(X[i][j] == 1) {
    if(row[i] != j) return;
      }
    }
  }
  for(i=0; i<N; i++) {
    for(j=0; j<N; j++) {
      if(row[i] == j) printf("Q");
      else printf(".");
    }
    printf("\n");
  }
}
 
void putQueen(int i) {
  int j;
  if(i == N) {
    printBoard();
    return;
  }
 
  for(j=0; j<N; j++) {
    if(col[j] == 1 || dpos[i+j] == 1 || dneg[i-j+N-1] == 1) continue;
    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+N-1] = 1;
    putQueen(i+1);
    row[i] = col[j] = dpos[i+j] = dneg[i-j+N-1] = 0;
  }
}
 
int main() {
  int i, k, r, c;
   
  init();
   
  scanf("%d",&k);
  for(i = 0; i < k; i++) {
    scanf("%d%d",&r,&c);
    X[r][c] = 1;
  }
 
  putQueen(0);
   
  return 0;
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n)   for(int i=0; i<(int)(n); i++)
#define FOR(i,b,e) for(int i=(b); i<=(int)(e); i++)
#define DUMP(a, n) REP(_i, n) printf("%d%c", a[_i], _i + 1 == n ? '\n' : ' ')
#define DUMP2D(a, n, m) REP(_i, n) REP(_j, m) printf("%d%c", a[_i][_j], _j + 1 == m ? '\n' : ' '); puts("")

typedef long long ll;

ll n;
ll a[1000];

void solve() {
  string r = "APPROVED";
  REP(i, n) {
    if (a[i]%2 == 1) {
      continue;
    } else {
      if (a[i]%3==0 || a[i]%5==0) continue;
      else r = "DENIED";
    }
  }
  cout << r;
}

void input() {
  cin >> n;
  REP(i, n) cin >> a[i];
}
 
int main() {
  input();
  solve();
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pcc pair<char,char>
#define vi vector <int>
#define vl vector <ll>
#define sd(x) scanf("%d",&x)
#define slld(x) scanf("%lld",&x)
#define pd(x) printf("%d",x)
#define plld(x) printf("%lld",x)
#define pds(x) printf("%d ",x)
#define pllds(x) printf("%lld ",x)
#define pdn(x) printf("%d\n",x)
#define plldn(x) printf("%lld\n",x)
#define INF 2e9
#define INFLL 4e18
using namespace std;
ll powmod(ll base,ll exponent,ll mod){ // with mod < 1e9
	ll ans=1;
	while(exponent){
		if(exponent&1)ans=(ans*base)%mod;
		base=(base*base)%mod;
		exponent/=2;
	}
	return ans;
}
ll gcd(ll a, ll b){
	if(b==0) return a;
	else return gcd(b,a%b);
}
const int upperlimit = 1e6+100;
const int mod = 1e9+7;
int main() {
	int n;
	sd(n);
	n-=2;n*=180;
	pd(n);
	return 0;
}

Measured memory_bytes: 256
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"
#include "numeric"

using namespace std;

const long long int MOD = 1000000007;

long long int N, M, K, H, W, L, R;


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

	cin >> H >> W;
	vector<string>s(H);
	for (int i = 0; i < H; i++)cin >> s[i];
	vector<int>w(W);
	vector<int>h(H);
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (s[i][j] == '#') {
				w[j]++, h[i]++;
			}
		}
	}
	for (int i = 0; i < H; i++) {
		bool f = false;
		for (int j = 0; j < W; j++) {
			if (h[i] && w[j]) {
				cout << s[i][j];
				f = true;
			}
		}
		if(f)		cout << endl;
	}

	return 0;
}

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

using namespace std;
typedef long long ll;
const ll mx = 10000007;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
#define    ss   second
#define    ff   first
#define    pb   push_back
#define gcd(a, b) __gcd((a), (b))
#define lcm(a, b) ((a) / __gcd((a), (b)) * (b))
#define FIO ios_base::sync_with_stdio(false);  cin.tie(NULL);


int main() {
    FIO;
   string s;
   cin >> s;
   if(s == "ABC") {
    cout << "ARC" << endl;
   }
   else {
    cout << "ABC" << endl;
   }

   return 0;
}



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

const int N = 2e5 + 10;
int n, in[N], ans;
struct node {
    int id, num;
}a[N], b[N];

bool cmp(node x, node y) {
    return x.num < y.num;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &in[i]);
        if (i % 2) a[in[i]].num++;
        else b[in[i]].num++;
    }
    for (int i = 1; i <= 1e5; i++) {
        a[i].id = b[i].id = i;
        a[i].num = n / 2 - a[i].num, b[i].num = n / 2 - b[i].num;
    }
    sort(a + 1, a + 100000 + 1, cmp);
    sort(b + 1, b + 100000 + 1, cmp);
    if (a[1].id == b[1].id) {
        ans = min(a[1].num + b[2].num, a[2].num + b[1].num);
    } else ans = a[1].num + b[1].num;
    printf("%d\n", ans);
    return 0;
}


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

int main(){
	ll n,x;
	cin >> n >> x;
	vector<ll> a(n);
	rep(i,n) cin >> a[i];
	sort(a.begin(),a.end());
	int ans = 0;
	rep(i,n){
		if(i == n-1){
			if(a[i] == x) ans++;
		} else if(a[i] <= x){
			ans++;
			x -= a[i];
		}
	}
	cout << ans << endl;
    return 0;
}



Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

//最大公約数
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 /gcd(a,b) * b;
}

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}

// 素因数分解
vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

// 10進数から2進数
int binary(int bina){
    int ans = 0;
    for (int i = 0; bina>0 ; i++)
    {
        ans = ans+(bina%2)*pow(10,i);
        bina = bina/2;
    }
    return ans;
}





int main() {
    int n;
    cin >> n;
    vector<int> l(n);
    rep (i,n) {
      cin >> l[i];
    }
    sort (l.begin(),l.end());
    ll res = 0;

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

        int k = lower_bound(l.begin(),l.end(),l[i]+l[j])-l.begin();
        //cout << k << endl;
        res += max(k - (j+1),0);
      }
    }
    cout << res << endl;
}

Measured memory_bytes: 3704
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <complex>
#include <cstring>
#include <cstdlib>
#include <string>
#include <cmath>
#include <cassert>
#include <queue>
#include <set>
#include <map>
#include <valarray>
#include <bitset>
#include <stack>
#include <iomanip>
#include <fstream>
using namespace std;

#define REP(i,n) for(int i=0;i<(int)n;++i)
#define FOR(i,c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(), (c).end()
const int INF = 1<<29;
typedef long long ll;
typedef pair<int,int> pii;

const ll llmax = 2*1e18;

ll mul(ll a, ll b) {
  if (b == 0) return 0;
  if (a>llmax/b) return llmax;
  return a*b;
}
ll add(ll a, ll b) {
  if (a>llmax-b) return llmax;
  return a+b;
}

const ll mod = 1e9+7;
ll dp[2001];
string s[100];
int len[100];
ll num[2001];
ll hash[100][201];           // hash[i][j] = s[i]テ」ツ?ョテゥツ閉キテ」ツ?彬テ」ツ?ョPrefixテ」ツ?ョテ」ツδ湘」ツδε」ツつキテ」ツδ・
ll suffix[2001];                // suffix[i] = テゥツ閉キテ」ツ?品テ」ツ?ョSテ」ツ?ョSuffixテ」ツ?ョテ」ツδ湘」ツδε」ツつキテ」ツδ・
ll tsuffix[2001];

int main() {
  int n, m;
  ll K;
  while(cin>>n>>m>>K) {
    K--;
    REP(i,n) {
      cin >> s[i];
      len[i] = s[i].size();
      hash[i][0] = 0;
      REP(j,len[i]) {
        hash[i][j+1] = hash[i][j]*mod + s[i][j];
      }
    }
    memset(dp,0,sizeof(dp));
    dp[0] = 1;
    REP(j,m) {
      REP(i,n) {
        if (j+len[i] <= m) {
          dp[j+len[i]] = add(dp[j+len[i]], dp[j]);
        }
      }
    }
    if (dp[m] <= K) {
      puts("-");
      continue;
    }
    string S;
    num[0] = 1;

    REP(i,m) {
      ll t = 0;
      ll pre = 0;
      REP(j,26) {
        string SS = S + string(1,j+'a');
        REP(k,201) tsuffix[k+1] = suffix[k]*mod + (j+'a');
        REP(k,n) {
          for (int l=1; l<=min(i+1,len[k]); ++l) {
            if (m-(i+1-l+len[k]) < 0) continue;
            if (tsuffix[l] == hash[k][l]) {
              // cout << j << " " << k << " " << l << endl;
              t = add(t, mul(num[i+1-l], dp[m-(i+1-l+len[k])]));
            }
          }
        }
        // cout << t << " " << K << endl;
        if (t > K) {
          K -= pre;
          S = SS;
          break;
        }
        pre = t;
      }
      // cout << S << endl;

      suffix[0] = 0;
      for (int j=min(200,i); j>=0; --j) {
        suffix[j+1] = suffix[j] * mod + S[i];
      }
      
      REP(j,n) {
        if (i+1>=len[j] && suffix[len[j]]==hash[j][len[j]]) {
          num[i+1] = add(num[i+1], num[i+1-len[j]]);
        }
      }
    }
    cout << S << endl;
  }
}

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

typedef long long ll;

int main() {
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	// vector<int> a;
	int n, i = 1;
	while (cin >> n) {
		if (n == 0) {
			cout << i << "\n";
			break;
		}
		i++;
	}
	return 0;
}

Measured memory_bytes: 3524
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)
#define N 4050
#define INF 1000000000
typedef long long ll;
#define ALL(v) (v).begin(),(v).end()
#define SZ(x) int(x.size())
#define IN(a) cin>>(a)
#define OUT(a) cout<<(a)<<endl
typedef pair<int,int> P;
const int MAX = 1000005;
const int MOD = 1000000007;
ll dp[MAX][105];
int main(){
    string s;
    int d;
    cin>>s>>d;
    int same=0;
    REP(i,SZ(s)){
        REP(j,d){
            REP(k,10){
                dp[i+1][(j+k)%d]+=dp[i][j];
                dp[i+1][(j+k)%d]%=MOD;
            }
        }
        REP(j,s[i]-'0'){
            dp[i+1][(same+j)%d]++;
            dp[i+1][(same+j)%d]%=MOD;
        }
        same=(same+s[i]-'0')%d;
    }
    if(same==0)dp[SZ(s)][0]++;
    dp[SZ(s)][0]=(dp[SZ(s)][0]-1+MOD)%MOD;
    OUT(dp[SZ(s)][0]);
    return 0;
}

Measured memory_bytes: 10496
from collections import Counter as ct

n=int(input())
lists=list(map(int,input().split()))
wanted=dict(ct(lists))
if n>=2:
    numbers=0
    for i in wanted.keys():
        a=i-wanted[i]
        if a<0:
            numbers+=abs(a)
        elif a==0:
            numbers+=0
        if a>0:
            numbers+=wanted[i]
    print(numbers)
elif n==1:
    if lists==[1]:
        print(0)
    else:
        print(1)
    



Measured memory_bytes: 21740
#include <cmath>
#include <cstdio>
#include <limits>
#include <tuple>
#include <stack>
#include <queue>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <numeric>
#include <string>
#include <array>
#include <iomanip>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rrep(i, n) for (int i = n-1; i >= 0; --i)
#define REP(i, s, n) for (int i = s; i< (int)(n); ++i)
#define all(x) x.begin(), x.end()

using namespace std;
using ll = long long;
ll inf = ll(1e18);
using ll1d = vector<ll>;
using ll2d = vector<ll1d>;
using ll3d = vector<ll2d>;

class CombinationModM {
 public:
  ll M;

  vector<ll> factorial_n = vector<ll>(300001, 0);
  vector<ll> factorial_km2 = vector<ll>(300001, 0);

  explicit CombinationModM(const ll &m) {
    this->M = m;
    pre_calc();
  }

  ll calc(const ll &n, const ll &r) {
    if (n == 0 and r == 0) return 1;
    if (n < r and n < 0) return -1;
    ll tmp = factorial_km2[n - r] * factorial_km2[r] % M;
    return tmp * factorial_n[n] % M;
  }

 private:
  ll llpow(ll x, ll n) {
    ll ans = 1;
    while (n != 0) {
      if (n & 1) ans = ans * x % M;
      x = x * x % M;
      n = n >> 1;
    }
    return ans;
  }

  void pre_calc() {
    factorial_n[0] = 1;
    factorial_km2[0] = 1;
    for (ll i = 0; i < 300000; ++i) {
      factorial_n[i + 1] = factorial_n[i] * (i + 1) % M;
      factorial_km2[i + 1] = factorial_km2[i] * llpow(i + 1, M - 2) % M;
    }
  }

};

void solve(istream &ccin = cin, ostream &ccout = cout) {
  ll mod = ll(1e9) + 7;
  ll h, w, a, b;
  ccin >> h >> w >> a >> b;
  CombinationModM cmb(mod);
  ll cnt = 0;
  REP(i, b, w) {
    cnt += cmb.calc(h - a + i - 1, i) * cmb.calc(w - i + a - 2, a - 1) % mod;
    cnt %= mod;
  }

  ccout << cnt << endl;

}

int main() {
  ios::sync_with_stdio(false);
  solve();
  return 0;
}


Measured memory_bytes: 4992
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# 長さ3以上は使わないとしてよい

S = "$$" + read().rstrip().decode("utf-8")

# 最後の長さ　-> 文字列の個数
N = len(S)
INF = 10 ** 9
one = [-INF] * N; one[1] = 0
two = [-INF] * N; two[1] = 0
for i in range(2,N):
  x = two[i - 1] + 1

  if S[i] != S[i - 1]:
    y = one[i - 1] + 1
    if x < y:
      x = y
  one[i] = x
  x = one[i - 2] + 1
  if S[i - 1:i + 1] != S[i - 3:i - 1]:
    y = two[i - 2] + 1
    if x < y:
      x = y
  two[i] = x
answer = max(one[-1],two[-1])
print(answer)

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

int main()
{
	int a,b,c,d;
	cin >> a >> b >> c >> d;
	while(true)
	{
		c -= b;
		if (c <= 0)
		{
			cout << "Yes" << endl;
			return 0;
		}
		a -= d;
		if (a <= 0)
		{
			cout << "No" << endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 3632
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
 
def main():
    N, K = map(int, readline().split())
    p = [int(i) for i in range(N+1)]
    s = [0]
    for i in range(N+1):
        s.append(s[i]+p[i])
    ans = 0
    P = int(1e9)+7
    for k in range(K, N+2):
        ans += (s[-1]-s[-k-1])-(s[k]-s[0])+1
        ans %= P
    print(ans)
if __name__ == '__main__':
    main()

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

struct mp{
	int to,dis;
	mp(int x,int y):to(x),dis(y){}
};

void trip(int s, int f,uint64_t dist,vector<vector<mp>>&v,vector<uint64_t>&sh){
	for(auto&j:v.at(s)){
		if(j.to==f)continue;
		uint64_t tmp=dist+j.dis;
		sh.at(j.to)=tmp;
		trip(j.to,s,tmp,v,sh);
	}
}

int main(){
	cin.tie(0),ios::sync_with_stdio(false);
	int n; cin>>n;
	vector<vector<mp>>v(n+1);
	for(int i=1;i<n;++i){
		int a,b,c; cin>>a>>b>>c;
		mp x(a,c),y(b,c);
		v.at(a).emplace_back(y);
		v.at(b).emplace_back(x);
	}
	int q,k; cin>>q>>k;
	vector<uint64_t>sh(n+1);
	sh.at(k)=sh.at(0)=0;
	for(int i=1;i<v.size();++i){
		for(int j=0;j<v.at(i).size();++j){
			if(v.at(i).at(j).to==k){
				sh.at(i)=v.at(i).at(j).dis;
			}
		}
	}
	trip(k,-1,0,v,sh);
	for(int i=0;i<q;++i){
		int x,y; cin>>x>>y;
		cout<<sh.at(x)+sh.at(y)<<"\n"s;
	}
}

Measured memory_bytes: 15872
from collections import deque
import math

#入力
h,w,k=map(int,input().split())
a=[input() for i in range(h)]

for i in range(h):
  for j in range(w):
    if a[i][j]=='S':
      sy,sx=i,j

d=deque([[sy,sx]])
dist=[]
inf=-1
m=1000
for i in range(h):
  dist.append([inf]*w)
dist[sy][sx]=0

while len(d)!=0:
  b=d.popleft()
  p,q=b[0],b[1]
  for i in [[1,0],[0,-1],[-1,0],[0,1]]:
    by,bx=b[0]+i[0],b[1]+i[1]
    if bx>=0 and bx<w and by>=0 and by<h:
      if a[by][bx]!='#' and dist[by][bx]==-1:
        d.append([by,bx])
        dist[by][bx]=dist[p][q]+1

for i in range(h):
  for j in range(w):
    if dist[i][j]!=-1 and dist[i][j]<=k:
      m=min(m,0--min(i,h-1-i,j,w-1-j)//k)

print(m+1)

Measured memory_bytes: 61916
if __name__ == '__main__':
    from sys import stdin
    # from collections import defaultdict
    # from collections import deque
    # from collections import Counter
    # import copy
    # import numpy as np
    # import math
    # import random
    input = stdin.readline

    CONTEST_NUM = 26
    INFTY = 10**9

    d = int(input())
    cc = [0]+list(map(int, input().split()))
    ss = [[0]*(CONTEST_NUM+1) for _ in range(d)]
    for i in range(d):
        ss[i] = [0]+list(map(int, input().split()))

    last_day = [-1]*(CONTEST_NUM+1)
    content = 0

    def count_discontent(content, date):
        for contest in range(1, CONTEST_NUM+1):
            content -= cc[contest]*(date-last_day[contest])
        return content

    for date in range(d):
        # t = int(input())
        point = -INFTY
        for contest in range(1, CONTEST_NUM+1):
            get_point = ss[date][contest]+cc[contest]*(date-last_day[contest])
            if get_point > point:
                point = get_point
                t = contest

        content += ss[date][t]
        last_day[t] = date
        content = count_discontent(content, date)
        print(t)
            




Measured memory_bytes: 9400
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e7 + 1;
const long long MOD = 1000000007;
const long double PI = 3.1415926;
#define FOR(i,r,n) for(ll i = (ll)(r); i < (ll)(n); i++)
#define RFOR(i,r,n) for(ll i=(ll)(n-1);i>=r;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(x) x.begin(),x.end()
#define RALL(x) x.rbegin(),x.rend()
typedef long long int ll;
typedef vector<ll> vi;
typedef vector < pair<ll, ll > > vp;
typedef vector <string> vs;
typedef vector <char> vc;
typedef list <ll> lst;

ll n, m, k, ans = 0, sum = 0, cnt = 0;
string s;
char c;

#define Endl endl

/*--------------------template--------------------*/


int main()
{
	cin >> s;

	ll i = s.size();

	while (true) {
		if (i == 0) {
			cout << "YES" << endl;
			return 0;
		}
		if (s.substr(i - 5, 5) == "dream") {
			i -= 5;
		} else if (s.substr(i - 5, 5) == "erase") {
			i -= 5;
		} else if (s.substr(i - 6, 6) == "eraser") {
			i -= 6;
		} else if (s.substr(i - 7, 7) == "dreamer") {
			i -= 7;
		} else {
			cout << "NO" << endl;
			return 0;
		}
	}
}

Measured memory_bytes: 512
/*created by tanishk gupta*/
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define repl(i,a,n) for(long long int i=a;i<n;i++)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
typedef vector<int> VI;
typedef long long int ll;
typedef unsigned long long ull;
//typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll MOD=1e9+7;
const ll mod=1e9+7;
//const llint MOD;
const ll N=(ll)(1e6+1);
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
ll add(ll a,ll b){return ((a%MOD)+(b%MOD))%MOD;}
ll mul(ll a,ll b){return ((a%MOD)*(b%MOD))%MOD;}
ll sub(ll a,ll b){return ((a%MOD)-(b%MOD)+MOD)%MOD;}
ll binpow(ll x, ll y){ll z = 1;while(y){if(y & 1) z = mul(z, x);x = mul(x, x);y >>= 1;}return z;}
ll inv(int x){return binpow(x, MOD - 2);}
ll divide(ll x, ll y){return mul(x, inv(y));}
ll fact[N];
void precalc(){fact[0] = 1;for(ll i = 1; i < N; i++)fact[i] = mul(fact[i - 1], i);}
ll C(ll n, ll k){return divide(fact[n], mul(fact[k], fact[n - k]));}
//bool prime[N];
//void sieve() {for(int i=2;i<N;i++) {prime[i]=true;}for (int p=2; p*p<=N; p++){if (prime[p] == true){for (int i=p*p; i<=N; i += p)prime[i] = false;}}}
ll legendpow(ll n, ll p){ll total = 0;while (n){n /= p;total += n;}return total;}

//head==================================================================================



int main()
{
IOS;
int x;
cin>>x;
int ans=x ^ 1;
cout<<ans;

}

Measured memory_bytes: 3668
#include<iostream>
using namespace std;
int main(){
	int x;
	int i=1;
	while(1){
		cin>>x;
		if(x==0)
			break;
		//int y++;
		cout<<"Case "<<i<<": "<<x<<"\n";
		i++;
	}
	/*for(i=1;i++;i<=y)
		cout<<"Case "<<i<<": "<<x<<"\n";
	}*/
}

Measured memory_bytes: 1160
/*
        AOJ - ALDS1_2_A
        Date: 20190311
        Author: Mikoron * ♡mikoiwate_351♡
*/

#define N 101

#include<stdio.h>

int main(void) {
        int i, j, n, buf, count;
        int A[N];

        scanf("%d", &n);
        for(i = 0; i < n; i++) {
                scanf("%d", &A[i]);
        }
        count = 0;
        for(i = 0; i < n-1; i++) {
                for(j = n-1; j > i; j--){
                        if(A[j] < A[j-1]) {
                                buf = A[j];
                                A[j] = A[j-1];
                                A[j-1] = buf;
                                count++;
                        }
                }
        }
        for(i = 0; i < n; i++) {
                if(i > 0) printf(" ");
                printf("%d", A[i]);
        }
        printf("\n%d\n", count);
        return 0;
}



Measured memory_bytes: 2112
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		double[] x = new double[n];
		double[] y = new double[n];
		double d1 = 0;
		double d2 = 0;
		double d3 = 0;
		double d=0;
		double d4=0;
		for (int i = 0; i < n; i++) {
			x[i] = scanner.nextDouble();
		}
		for (int i = 0; i < n; i++) {
			y[i] = scanner.nextDouble();
		}
		for (int i = 0; i < n; i++) {
			if (x[i] > y[i]) {
				d1 = d1 + (x[i] - y[i]);
			} else {
				d1 = d1 + (y[i] - x[i]);
			}
		}
		for (int i = 0; i < n; i++) {
			if (x[i] > y[i]) {
				d=(x[i] - y[i]) * (x[i] - y[i]);
				d2 = d2 +d;
			} else {
				d=(y[i] - x[i]) * (y[i] - x[i]);
				d2 = d2 + d;
			}
		}
		for (int i = 0; i < n; i++) {
			if (x[i] > y[i]) {
				d=(x[i] - y[i]) * (x[i] - y[i])* (x[i] - y[i]);
				d3 = d3 +d;
			} else {
				d=(y[i] - x[i]) * (y[i] - x[i])* (y[i] - x[i]);
				d3 = d3 + d;
			}
		}
		for (int i = 0; i < n; i++) {
			if (x[i] > y[i]) {
				if (d4 < x[i] - y[i]) {
					d4 = x[i] - y[i];
				}
			} else {
				if (d4 < y[i] - x[i]) {
					d4 = y[i] - x[i];
				}
			}
		}
		System.out.println(d1);
		System.out.println(Math.sqrt(d2));
		System.out.println(Math.cbrt(d3));
		System.out.println(d4);

	}
}


Measured memory_bytes: 29088
// Written By NewbieChd
#include <cstdio>
#include <cctype>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

const int BUF = 1000000;
char buf[BUF], *p1, *p2;
inline char getChar() { return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, BUF, stdin), p1 == p2) ? EOF : *p1++; }
inline int read() {
    int f = 0;
    char c;
    while (!isdigit(c = getChar())) {}
    do
        f = f * 10 + (c ^ 48);
    while (isdigit(c = getChar()));
    return f;
}

const int maxN = 2003;
int n, a[maxN];
bool f[maxN][maxN];
inline int gcd(int x, int y) { return y ? gcd(y, x % y) : x; }

bool vis[maxN];
int deg[maxN];
vector<int> g[maxN];
void dfs(int x) {
    vis[x] = 1;
    for (int y = 1; y <= n; ++y)
        if (f[x][y] && !vis[y])
            g[x].push_back(y), ++deg[y], dfs(y);
}

priority_queue<int> que;

int main() {
    int i, x;
    n = read();
    for (i = 1; i <= n; ++i)
        a[i] = read();
    sort(a + 1, a + n + 1);
    for (i = 1; i <= n; ++i)
        for (x = i + 1; x <= n; ++x)
            f[i][x] = f[x][i] = gcd(a[i], a[x]) > 1;
    
    for (i = 1; i <= n; ++i)
        if (!vis[i])
            dfs(i);
    for (i = 1; i <= n; ++i)
        if (!deg[i])
            que.push(i);
    while (!que.empty()) {
        x = que.top(), que.pop();
        printf("%d ", a[x]);
        for (auto y : g[x])
            if (--deg[y] == 0)
                que.push(y);
    }
    return 0;
}


Measured memory_bytes: 4608
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0
for i in range(N):
  ans = ans + B[A[i] - 1]
  if i > 0 and A[i] == A[i-1] + 1:
    ans = ans + C[A[i-1] - 1]
print(str(ans))

Measured memory_bytes: 3064
class Dice
  #   1
  # 4 2 3 5
  #   6
  attr_reader :pips
  def initialize(*pips)
    @pips = pips
  end

  def rotate_s!
    pips = [5, 1, 3, 4, 6, 2].map { |i| i - 1 }
    @pips = @pips.values_at(*pips)
    self
  end

  def rotate_e!
    pips = [4, 2, 1, 6, 5, 3].map { |i| i - 1 }
    @pips = @pips.values_at(*pips)
    self
  end

  def rotate_n!
    pips = [2, 6, 3, 4, 1, 5].map { |i| i - 1 }
    @pips = @pips.values_at(*pips)
    self
  end

  def rotate_w!
    pips = [3, 2, 6, 1, 5, 4].map { |i| i - 1 }
    @pips = @pips.values_at(*pips)
    self
  end
end

pips = gets.split.map(&:to_i)
rotates = gets.chomp.downcase.chars
dice = Dice.new(*pips)
rotates.each do |rotate|
  dice.send("rotate_#{rotate}!")
end
puts dice.pips.first

Measured memory_bytes: 6116
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef vector<ll> vl;
typedef pair<ll,ll> P;
#define rep(i,n) for(ll i = 0; i < ll(n); i++)
#define all(v) v.begin() , v.end()
#define inputv(v,n) rep(i,n){\
    ll x;\
    cin>>x;\
    v.push_back(x);\
    }
const ll INF=99999999999999;
const ll MOD=1000000007;
ll c,d,e,f,p,t,ans=0;


ll n;
multiset<ll> k;
vl pp;
void input(void){
    cin>>n;
    rep(i,1<<n){
        cin>>c;
        k.insert(c);
    }
}

ll solve(void){
    auto i1=k.end();
    i1--;
    pp.push_back(*i1);
    rep(i,n){
    	//cout<<k.size()<<endl;
    	d=pp.size();
    	/*cout<<d<<endl;
    	rep(j,d){
    		cout<<pp[j]<<" ";
    	}
    	cout<<endl;*/
        rep(j,d){
            auto i1=k.lower_bound(pp[j]),i2=k.lower_bound(pp[j]);
            if(i1==k.begin()){
                return -1;
            }
            i1--;
            pp.push_back(*i1);
            k.erase(i1,i2);
        }
        sort(all(pp));
        reverse(all(pp));
    }
    return 0;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    input();
    if(solve()==0){
        cout<<"Yes"<<endl;
    }
    else{
        cout<<"No"<<endl;
    }
}

Measured memory_bytes: 14708
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cassert>
using namespace std;

int N;
vector<vector<int>> G;
vector<int> c;
vector<int> depth;

void dfs(int s){
    for(int t : G[s]){
        if(depth[t] != -1) continue;
        depth[t] = depth[s] + 1;
        dfs(t);
    }
}

int main(){
    cin >> N;
    G.resize(N);
    c.resize(N);
    depth.resize(N, -1);
    for(int i=0; i<N-1; i++){
        int a, b;
        cin >> a >> b;
        a--; b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }
    for(int i=0; i<N; i++)
        cin >> c[i];

    depth[0] = 0;
    dfs(0);

    vector<pair<int, int>> v(N);
    for(int i=0; i<N; i++){
        v[i] = make_pair(-depth[i], i);
    }
    sort(v.begin(), v.end());
    sort(c.begin(), c.end());

    vector<int> ans(N);
    for(int i=0; i<N; i++){
        ans[v[i].second] = c[i];
    }
    int sm = 0;
    for(int i=0; i<N-1; i++)
        sm += c[i];
    cout << sm << endl;
    for(int i=0; i<N; i++)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}

Measured memory_bytes: 1408
N, K = map(int, input().split())
As = list(map(int, input().split()))
M = [[] for i in range(200001)]
for i, a in enumerate(As):
  M[a].append(i)
S = []
for i, a in enumerate(As):
  l = M[a]
  index = l.index(i)
  if index+1 == len(l):
    n = l[0]+N
  else:
    n = l[index+1]
  S.append(n+1-i)
#print(S)
p = 0
while True:
  p = p+S[p%N]
  if p%N == 0:
    break
count = p//N
#print(count)
K = K%count
#print(K)
p = 0
s = []
while p < N*K:
  q = p+S[p%N]
  if q > N*K:
    s.append(As[p%N])
    p = p+1
  else:
    p = q
print(" ".join(map(str, s)))


Measured memory_bytes: 64320
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

N, X = map(int, input().split())

numP_N = [0]*N
numPB_N = [0]*N
numP_N[0] = 3
numPB_N[0] = 5
for i in range(1,N):
    numP_N[i] = numP_N[i-1] * 2 + 1
    numPB_N[i] = numPB_N[i-1] * 2 + 3

def rec(n, x):
    if n == 1:
        ans_1 = [0,0,1,2,3,3]
        return ans_1[x]

    if x == numPB_N[n-1]:
        return numP_N[n-1]

    elif x > numPB_N[n-2] + 2:
        return numP_N[n-2] + 1 + rec(n-1, x-numPB_N[n-2] - 2)

    elif x == numPB_N[n-2] + 2:
        return numP_N[n-2] + 1

    elif x == numPB_N[n-2] + 1:
        return numP_N[n-2]

    elif x < numPB_N[n-2] + 1:
        return rec(n-1, x-1)

print(rec(N,X))


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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define endl "\n"
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()

using namespace std;
using ll = long long;

const double PI = 3.14159265358979;

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

  sort(RALL(a));
  ll ans = 0;
  ll sign = 1;
  for(int i = 0; i < n; ++i)
  {
    ans += a[i] * sign;
    sign = -sign;
  }
  cout << ans;
}

int main()
{
  fastio;
  solve();

  return 0;
}

Measured memory_bytes: 3624
import math

N,D = map(int,input().split())

if D == 1:
    list_nd = [int(input()) for i in range(N)]
    print(N*(N-1)//2)


else:
    list_ND = [list(map(int,input().split())) for i in range(N)]

    count = 0

    for i in range(N):
        for j in range(i+1,N):
            s = 0

            for k in range(D):
                s += (list_ND[i][k] - list_ND[j][k])**2
    
            s = math.sqrt(s)

            if s.is_integer():
                count += 1

    print(count)

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

long long num[9]={9,2*90,3*900,4*9000,5*90000,6*900000,7*9000000,
		  720000000,81000000000};

int main()
{
  int n,k;

  while(1){
    cin>>n>>k;
    if(n+k==0)break;

    string ans="";
    int index=0;
    for(int i=0;i<9;i++){
      if(n<=num[i]){
	n--;
	int sum=pow(10,i)+n/(i+1);
	index=n%(i+1);
	for(int i=sum;i<sum+101;i++){
	  ostringstream s;
	  s<<i;
	  ans+=s.str();
	}
	break;
      }
      n-=num[i];
    }
    for(int i=index;i<k+index;i++)cout<<ans[i];
    cout<<endl;
  }
  return 0;
}

Measured memory_bytes: 1268
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define ii pair<int,int>
#define MAX 1000000007
using namespace std;

int main(void){
	int n,d;
	cin>>n>>d;
	cout<<(n+(2*d))/(2*d+1)<<endl;
	return 0;
}


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

int main(){
  int n;
  cin >> n;
  vector<long long> v(n);
  for(int i = 0; i < n; i++){
    cin >> v[i];
  }

  int count = 0;
  for(int i = 0; i < n; i++){
    if(v[i] == 1 || v[i] == 2 || v[i] == 3){
      count++; 
    }
    else if(v[i] % 2 == 0){ continue; }
    else if(v[i] > 2){
      bool f = true;
      for(int j = 3; j < sqrt(v[i]) + 2; j += 2){
        if(v[i] % j == 0){ f = false; break; }
      }
      if(f){ count++;}
    }
  }
  cout << count << endl;
}


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

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

const long long INF =1LL << 60;

int N;
long long h[1000010];

long long dp[1000010];

int main() {
  int N; cin >> N;
  for (int i = 0; i < N; i++) cin >> h[i];
  
  for (int i = 0; i < N; i++) dp[i] = INF;
  
  dp[0] = 0;
  
  for (int i = 1; i < N; i++) {
    chmin(dp[i], dp[i - 1] + abs(h[i] - h[i - 1]));
    if (i > 1) chmin(dp[i], dp[i - 2] + abs(h[i] - h[i - 2]));
  }
  
  cout << dp[N - 1] << endl;
}
    
    
    
    

Measured memory_bytes: 5120
N, M = map(int, input().split())
ans = 1
for i in range(1, M + 1):
  if i * i > M:
    break
  if M % i == 0 and i > ans and M / i >= N:
    ans = i
  if M % i == 0 and M / i > ans and i >= N:
    ans = int(M / i)
print(ans)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <limits>

using namespace std;

typedef long long ll;

int main (int argc, char* argv[]) {
	int n, k;
	string s;
	cin >> n >> k >> s;
	int res = 0;
	int regions = 0;
	for (int i = 0; i < s.size(); i++) {
		auto c = s[i];
		int count = 1;
		for (int j = i + 1; j < s.size() && s[j] == c; j++) {
			count++;
		}
		i += count - 1;
		res += count - 1;
		regions++;
	}

	while (regions > 1 && k > 0) {
		if (regions >= 3) {
			res += 2;
			regions -= 2;
		} else {
			res += 1;
			regions--;
		}
		k--;
	}

	cout << res << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
#include <list>
#include <limits>
#include <string>
#include <vector>
#include <stack>
using namespace std;
typedef long long ll;

int gcd(int a, int b){
    if(b == 0) return a;
    return gcd(b, a%b);
}

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    cout << min(min(a+b,b+c),a+c);
}

Measured memory_bytes: 256
#include <algorithm>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>

#define SREP(s,i,m) for(unsigned int i = s; i < m; ++i)
#define REP(i,m) SREP(0,i,m)

using namespace std;
#ifdef _MSC_VER
using LONG = __int64;
using ULONG = unsigned __int64;
#else
using LONG = long long int;
using ULONG = unsigned long long int;
#endif

int main(void) {
	string s;
	cin >> s;
	int head = 0;
	int tail = s.size() - 1;
	int cnt = 0;
	while(head <= tail) {
		if (s[head] == s[tail]) {
			head++;
			tail--;
		}
		else if (s[head] == 'x') {
			cnt++;
			head++;
		}
		else if (s[tail] == 'x') {
			cnt++;
			tail--;
		}
		else {
			cout << -1 << endl;
			return 0;
		}
	}
	cout << cnt << endl;
	return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <numeric>

using namespace std;
typedef long long ll;
const ll mod = 1e9 + 7;
const int MAXN = 200005;
/*
 左下の塊上一つの行を右に沿って枚挙するだけ。
 答えはその塊の右上のセルからその行に沿って右に行く途中加算する 始点からそこに着く方法数 * そこから終点へ着く方法数。
 */
int fact[MAXN + MAXN];

int int_pow(int x, int p) {
  int res = 1;
  while(p) {
    if (p & 1) {
      res = 1LL * res * x % mod;
    }
    x = 1LL * x * x % mod;
    p >>= 1;
  }
  return res;
}

int mod_inv(int x) {
  return int_pow(x, mod - 2);
}

int get_ways(int h, int w) {
  return 1LL * fact[h + w - 2] * mod_inv(fact[h - 1]) % mod * mod_inv(fact[w - 1]) % mod;
}

void solve() {
  for (int i = fact[0] = 1; i < MAXN + MAXN; i++) {
    fact[i] = 1LL * fact[i - 1] * i % mod;
  }
  int H, W, A, B;
  cin >> H >> W >> A >> B;
  int ans = 0;
  for (int i = B + 1; i <= W; i++) {
    ( ans += 1LL * get_ways( H - A, i ) * get_ways( A, W - i + 1 ) % mod ) %= mod;
  }
  cout << ans << endl;
}

int main(int argc, const char * argv[]) {
  solve();
  return 0;
}


Measured memory_bytes: 1920
#include <bits/stdc++.h>
#define FAST_INPUT ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long

using namespace std;

void solve() {
	int n; cin >> n;
	vector<vector<int>> nums(n, vector<int>(3));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> nums[i][j];
		}
	}

	vector<vector<int>> dp(n, vector<int>(3, 0));
	for (int i = 0; i < 3; i++) {
		dp[0][i] = nums[0][i];
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			int mx = 0;
			for (int k = 0; k < 3; k++) {
				if (j != k) {
					mx = max(mx, dp[i - 1][k]);
				}
			}
			dp[i][j] = mx + nums[i][j];
		}
	}

	cout << max({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << endl;

}

int main() {
    FAST_INPUT;

    solve();

    return 0;
}


Measured memory_bytes: 11264
package main

import ("fmt"
"math")


func main(){
	var  N int
	var X float64
	fmt.Scanf("%d",&N)
	

	X=(float64(N)/108)*100
	X=math.Trunc(X)
	if int(X*1.08)==N{
		fmt.Printf("%.0f\n",X)
	}else if int((X+1)*1.08)==N{
		fmt.Printf("%.0f\n",X+1)
	}else{
		fmt.Println(":(")
	}

	
}

Measured memory_bytes: 1836