akhauriyash/Code-Regression huggingface dataset:
#include<stdio.h>
#include<stdlib.h>
int a[200005], b[200005];
int asc(const void* x, const void* y)
{
	if (a[*(int*)x] > a[*(int*)y])return 1;
	if (a[*(int*)x] < a[*(int*)y])return -1;
	if (b[*(int*)x] > b[*(int*)y])return 1;
	if (b[*(int*)x] < b[*(int*)y])return -1;
	return 0;
}
int main()
{
	int n, u, v;
	scanf("%d %d %d", &n, &u, &v);
	u--;
	v--;
	int i, j;
	for (i = 0; i < n - 1; i++)
	{
		scanf("%d %d", &a[2 * i], &b[2 * i]);
		a[2 * i]--;
		b[2 * i]--;
		a[2 * i + 1] = b[2 * i];
		b[2 * i + 1] = a[2 * i];
	}
	int c[200005];
	for (i = 0; i < 2 * n; i++)
		c[i] = i;
	qsort(c, 2 * n - 2, sizeof(int), asc);
	int p[100005], f[100005];
	for (i = 0; i < n; i++)
		p[i] = -1;
	p[v] = v;
	f[v] = 0;
	int q[100005], qq, qn;
	q[0] = v;
	qq = 1;
	int min, mid, max;
	while (qq > 0)
	{
		qq--;
		qn = q[qq];
		min = 0;
		max = 2 * n - 2;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (a[c[mid]] < qn)
				min = mid;
			else
				max = mid;
		}
		if (a[c[min]] != qn)
			min++;
		if (min < 2 * n - 2)
		{
			while (a[c[min]] == qn)
			{
				if (p[b[c[min]]] < 0)
				{
					p[b[c[min]]] = qn;
					f[b[c[min]]] = f[qn] + 1;
					q[qq] = b[c[min]];
					qq++;
				}
				min++;
				if (min == 2 * n - 2)
					break;
			}
		}
	}
	int r[40][100005];
	for (i = 0; i < n; i++)
		r[0][i] = p[i];
	for (j = 1; j < 40; j++)
		for (i = 0; i < n; i++)
			r[j][i] = r[j - 1][r[j - 1][i]];
	int po[100005];
	for (i = 0; i < n; i++)
		po[i] = 0;
	for (i = 0; i < n; i++)
		po[p[i]]++;
	int lca[100005];
	for (i = 0; i < n; i++)
		lca[i] = -1;
	j = u;
	lca[j] = j;
	q[0] = j;
	qq = 1;
	while (p[j] != j)
	{
		j = p[j];
		lca[j] = j;
		q[qq] = j;
		qq++;
	}
	while (qq > 0)
	{
		qq--;
		qn = q[qq];
		min = 0;
		max = 2 * n - 2;
		while (max - min > 1)
		{
			mid = (max + min) / 2;
			if (a[c[mid]] < qn)
				min = mid;
			else
				max = mid;
		}
		if (a[c[min]] != qn)
			min++;
		if (min < 2 * n - 2)
		{
			while (a[c[min]] == qn)
			{
				if (lca[b[c[min]]] < 0)
				{
					lca[b[c[min]]] = lca[qn];
					q[qq] = b[c[min]];
					qq++;
				}
				min++;
				if (min == 2 * n - 2)
					break;
			}
		}
	}
	int ans = 0;
	for (i = 0; i < n; i++)
		if (po[i] == 0)
			if (2 * f[lca[i]] > f[u])
				if (ans < f[i] - 1)
					ans = f[i] - 1;
	printf("%d\n", ans);
	return 0;
}

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

#define ld long double
#define sf scanf
#define pf printf
#define pb push_back
#define mp make_pair
#define PI ( acos(-1.0) )
#define IN freopen("input.txt","r",stdin)
#define OUT freopen("output.txt","w",stdout)
#define FOR(i,a,b) for(int i=a ; i<=b ; i++)
#define FORD(i,a,b) for(int i=a ; i>=b ; i--)
#define INF 1000000000
#define ll long long int
#define eps (1e-8)
#define sq(x) ( (x)*(x) )
#define all(x) x.begin(),x.end()
#define flog2(n) 64 - __builtin_clzll(n) - 1
#define popcnt(n) __builtin_popcountll(n)

using namespace std;

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

int d[3005][3005];

string s, t;

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

    cin >> s >> t;

    int m = s.length();
    int n = t.length();

    s = '0' + s;
    t = '1' + t;

    FOR (i, 1, m) {
    	FOR (j, 1, n) {
    		if (s[i] == t[j]) {
    			d[i][j] = d[i - 1][j - 1] + 1;
    		}
    		else {
    			d[i][j] = max(d[i - 1][j], d[i][j - 1]);
    		}
    	}
    }

	string res;

	int traceM = m, traceN = n;

	while (traceM && traceN) {
		if (s[traceM] == t[traceN]) {
			res += s[traceM];
			traceM--;
			traceN--;
		}
		else {
			if (d[traceM - 1][traceN] > d[traceM][traceN - 1]) {
				traceM--;
			}
			else {
				traceN--;
			}
		}
	}

	reverse(all(res));
	cout << res << endl;   
	
    return 0;
}

Measured memory_bytes: 35456
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
typedef long long ll;
vector <ll> a;
vector<ll> f;
ll n,k;
ll check(ll maxallowed)
{
	ll need = 0;
	for(ll i = 0; i<n ; i++)
	{
		if(a[i]*f[i]<=maxallowed)
			continue;
		else
		{
			need = need + a[i]-((maxallowed)/f[i]);
		}
	}
	if(need <=k)
		return 1;
	else
		return 0;
 
}
int	main()
{
   ios_base::sync_with_stdio(false); 
   cin.tie(NULL);
   cin>>n>>k;
   ll x;
   for(ll i=0; i<n ; i++)
   		{
   			cin>>x;
   			a.pb(x);
   		}
   	//cout<<"hey";
   for(ll i =0; i<n ; i++)
   		{
   			cin>>x;
   			f.pb(x);
   		}
   	//cout<<"hu";
   sort(a.begin(),a.end(),greater<ll>());
   sort(f.begin(),f.end());  	
   ll r = 1e12, l  = 0;
   // for(ll i = 0; i<n ; i++)
  	// 	if(a[i]*f[i]>r)
   // 			r = a[i]*f[i];
   
   	while(r-l>0)
   	{
   		ll mid = (l+r)/2;
   		if(check(mid))
   			r = mid;
   		else
   			l = mid+1;
   	}
   	// for(int i = max(r-5,(ll)0) ; i<=r+5 ; i++)
   	// 	if(check(i))
   	// 	{
   	// 		r = i;
   	// 		break;
   	// 	}
 
 	cout<<r<<endl;  	
 
 
	return 0;
}

Measured memory_bytes: 4848
import Control.Monad
import Data.List

main = do
  n <- read <$> getLine
  xs <- forM [1..n] $ \t -> do
    a <- read <$> getLine
    ys <- forM [1..a] $ \u -> do
      (x:y:yy) <- map read . words <$> getLine
      return (x,y)
    return . compose n 1 $ (sort ys)
  --putStrLn . show $ xs
  putStrLn . show $ solve n xs


compose :: Int -> Int -> [(Int,Int)] -> [Int]
compose n k [] = if n < k then [] else (-1):(compose n (k+1) [])
compose n k all@((x,y):xs) = if k == x then y:(compose n (k+1) xs) else (-1):(compose n (k+1) all)

solve :: Int -> [[Int]] -> Int
solve n xs =
  let comb = replicateM n [0,1]
      filtered = filter (calc' xs (replicate n (-1))) comb
  in maximum $ map (length . filter (== 1)) filtered

calc' xs ys zs = calc zs xs ys zs

calc :: [Int] -> [[Int]] -> [Int] -> [Int] -> Bool
calc ks [] ys [] = True
calc ks (x:xs) ys (z:zs) =
  if z == 0 then
    calc ks xs ys zs
  else
    if (and (map (\(xi,y) -> xi == y  || y == -1 || xi == -1) (zip x ys))) && (and (map (\(k,xi) -> xi == -1 || k == xi) (zip ks x))) then
      calc ks xs (map (\(xi,y) -> if y == -1 then xi else y) (zip x ys)) zs
    else
      False


Measured memory_bytes: 3964
/*Function Template*/
#include<bits/stdc++.h>
using namespace std;
const int mod = 1000000007;
#define rep(i, n) for(long long int i = 0; i < (n); i++)


int Len(int n) {
  int s=0;
  while(n!=0) s++, n/=10;
  return s;
}


int Sint(int n) {
  int m=0,s=0,a=n;
  while(a!=0) s++, a/=10;
  for(int i=s-1;i>=0;i--) m+=n/((int)pow(10,i))-(n/((int)pow(10,i+1)))*10;
  return m;
}


int Svec(vector<int> v){
  int n=0;
  for(int i=0;i<v.size();i++) n+=v[i];
  return n;
}


int GCD(int a,int b){
  int r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return b;
}


int LCM(int a,int b){
  int c=a,d=b,r,tmp;
/*自然数 a > b を確認・入替*/
  if(a<b){
    tmp=a,a=b,b=tmp;
  }
/*ユークリッドの互除法*/
  r=a%b;
  while(r!=0){
    a=b,b=r,r=a%b;
  }
  return c/b*d;
}


int Factorial(int n){
  int m=1;
  while(n>=1) m*=n,n--;
  return m;
}


/*↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓*/
int main() {
  int n;
  cin>>n;
  set<int> st;
  rep(i,n){
    int a;
    cin>>a;
    st.insert(a);
  }
  cout<<st.size()<<endl;
}

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

int main() {
  string S;
  cin >> S;
  
  if (S.at(0) == S.at(1) && S.at(0) == S.at(2) && S.at(0) == S.at(3)) {
    cout << "No" << endl;
  } else {
    if (S.at(0) == S.at(1)) {
      if (S.at(2) == S.at(3)) {
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    } else if (S.at(0) == S.at(2)) {
      if (S.at(1) == S.at(3)) {
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    } else {
      if (S.at(1) == S.at(2)) {
        cout << "Yes" << endl;
      } else {
        cout << "No" << endl;
      }
    }
  }
}


Measured memory_bytes: 256
/*
 * 2578.cc: Disciple Life is Hard
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_S = 100;
const int MAX_T = 100;
const int MAX_U = 100;
const int MAX_N = 100;
const int MAX_O = 100;
const int MAX_D = 100;

/* typedef */

/* global variables */

int es[MAX_T], cs[MAX_T], hs[MAX_N], as[MAX_N];
int ems[MAX_S + 1], hms[MAX_S + 1];
int dpc[MAX_T + 1][MAX_S + 1], dph[2][MAX_S * MAX_N + 1], dp[2][MAX_S + 1];

/* subroutines */

/* main */

int main() {
  int s, t, u, n, o, d;
  cin >> s >> t >> u >> n >> o >> d;

  for (int i = 0; i < t; i++) cin >> es[i] >> cs[i];
  for (int i = 0; i < n; i++) cin >> hs[i] >> as[i];

  memset(dpc, -1, sizeof(dpc));
  dpc[0][0] = 0;

  for (int i = 0; i < t; i++)
    for (int j = u - 1; j >= 0; j--)
      for (int k = s - es[i]; k >= 0; k--)
	if (dpc[j][k] >= 0) {
	  int j0 = j + 1;
	  int k0 = k + es[i];
	  int dp0 = dpc[j][k] + cs[i];
	  if (dpc[j0][k0] < dp0) dpc[j0][k0] = dp0;
	}

  int pmax = 0;
  for (int i = 1; i <= s; i++) {
    if (dpc[u][i] < pmax) dpc[u][i] = -1;
    else pmax = dpc[u][i];
  }
  //for (int i = 0; i <= s; i++) printf("%d ", dpc[u][i]); putchar('\n');

  memset(dph, -1, sizeof(dph));
  dph[0][0] = 0;
  int sn = s * n;
  int cur = 0, nxt = 1;
  
  for (int i = 0; i < n; i++) {
    memcpy(dph[nxt], dph[cur], sizeof(dph[cur]));
    int a = as[i], h = hs[i];

    while (a <= sn) {
      for (int j = sn - a; j >= 0; j--)
	if (dph[cur][j] >= 0) {
	  int j0 = j + a;
	  int dp0 = dph[cur][j] + h;
	  if (dph[nxt][j0] < dp0) dph[nxt][j0] = dp0;
	}
      a += as[i], h += hs[i];
    }

    cur ^= 1, nxt ^= 1;
  }

  for (int i = 1; i <= sn; i++)
    if (dph[cur][i] < dph[cur][i - 1]) dph[cur][i] = dph[cur][i - 1];

  //for (int i = 0; i <= sn; i++) printf("%d ", dph[cur][i]); putchar('\n');

  int m = 0;
  for (int i = 0; i <= s; i++)
    if (dpc[u][i] > 0) ems[m] = i, hms[m] = dph[cur][dpc[u][i]], m++;
  //for (int i = 0; i < m; i++) printf("%d %d\n", ems[i], hms[i]);

  memset(dp, -1, sizeof(dp));
  dp[0][s] = 0;
  cur = 0, nxt = 1;

  for (int i = 0; i < d; i++) {
    memset(dp[nxt], -1, sizeof(dp[nxt]));

    for (int j = s; j >= 0; j--)
      if (dp[cur][j] >= 0)
	for (int k = 0; k < m; k++)
	  if (j >= ems[k]) {
	    int j0 = min(j - ems[k] + o, s);
	    int dp0 = dp[cur][j] + hms[k];
	    if (dp[nxt][j0] < dp0) dp[nxt][j0] = dp0;
	  }

    cur ^= 1, nxt ^= 1;
  }
  //for (int i = 0; i <= s; i++) printf("%d ", dp[cur][i]); putchar('\n');

  int maxh = -1;
  for (int i = 0; i <= s; i++)
    if (maxh < dp[cur][i]) maxh = dp[cur][i];
  printf("%d\n", maxh);
  return 0;
}

Measured memory_bytes: 1292
N = int(input())
[*h] = map(int, input().split())
dp = [float('inf') for _ in range(N)]
dp[0] = 0
dp[1] = abs(h[0]-h[1])
for i in range(2, N):
    dp[i] = min(dp[i-1]+abs(h[i]-h[i-1]), dp[i-2]+abs(h[i]-h[i-2]))

print(dp[N-1])

Measured memory_bytes: 13980
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string s;
    cin>>s;
    long long k;
    cin>>k;
    long long a=1,b=0,c1=1,c2=1;
    long long n=s.size();
    long long renketu=0;
    for(int i=1;i<n;i++){
        if(s.at(i-1)==s.at(i)){
            a++;
        }
        else{
            b+=a/2;
            a=1;
        }
    }
    b+=a/2;
    if(n>=3){
        for(int i=1;i<n;i++){
            if(s.at(0)==s.at(i)){
                c1++;
            }
            else break;
        }
        for(int i=n-2;i>=0;i--){
            if(s.at(n-1)==s.at(i)){
                c2++;
            }
            else break;
        }
        if(s.at(0)==s.at(n-1)&&(c1*c2)%2==1) renketu=1;
    }
    bool onaji=true;
    for(int i=1;i<n;i++){
        if(s.at(i-1)!=s.at(i)){
            onaji=false;
            break;
        }
    }
    long long answer=0;
    if(onaji) cout<<n*k/2<<endl;
    else{
        answer=b*k+renketu*(k-1);
        cout<<answer<<endl;
    }
}


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

long myABS( long x )
{
	return ( x > 0 ? x : -x );
}

long gcd( long a, long b )
{
	return ( b == 0 ? a : gcd( b, a % b ) );
}

int main()
{
	long N, X;
	std::cin >> N >> X;

	long max = 1000000001;
	std::vector<long> v( N + 1 );
	for ( long i = 0; i < N; i++ )
	{
		std::cin >> v[i];
	}
	v[N] = X;

	if ( N == 1 )
	{
		max = myABS( X - v[0] );
	}
	else
	{
		std::sort( v.begin(), v.end() );

		std::vector<long> vv( N + 1 );
		for ( long i = 0; i < N; i++ )
		{
			vv[i] = v[i + 1] - v[i];
		}

		for ( long i = 0; i < N - 1; i++ )
		{
			long tmp = gcd( vv[i + 1], vv[i] );
			if ( tmp < max )
			{
				max = tmp;
			}
		}
	}

	std::cout << max << std::endl;

	return ( 0 );
}


Measured memory_bytes: 1792
package main

import (
	"fmt"
)

func gcd(a, b int) int {

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

func main() {
	var n int
	fmt.Scan(&n)

	var a, b int
	for i := 1; i < n+1; i++ {
		fmt.Scan(&a)
		if i == 1 {
			b = a
		} else {
			b = gcd(b, a)
		}
	}
	fmt.Println(b)
}

Measured memory_bytes: 5504
a,b = map(int,input().split())
s = input()
if s[a] != '-':
    print("No")
else:
    found = True
    for i in range(len(s)):
        if i != a and not s[i].isdigit():
            found = False
    if found:
        print("Yes")
    else:
        print("No")


Measured memory_bytes: 2940
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <numeric>
#include <cmath>
using namespace std;
int main() {
  int a, b, h, m;
  cin >> a >> b >> h >> m;
  double H, M, theta, r, PI = 3.141592653589793;
  M = m*6;
  H = h*30+m*0.5;
  theta = abs(M-H);
  r = sqrt(a*a+b*b-2*a*b*cos(PI*theta/180));
  printf("%.12f\n", r);
}

Measured memory_bytes: 3596
#include <algorithm>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define REP(i, n) for (int i = 0; i < n; i++)
using namespace std;

int n, A[100010], q, t;
int cnt;

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

int main() {
    cin >> n;
    REP(i, n) cin >> A[i];
    cin >> q;
    REP(i, q) {
        cin >> t;
        if (binarySearch(t)) {
            cnt++;
        }
    }
    cout << cnt << endl;
}


Measured memory_bytes: 3400
n, x, m =  map(int, input().split())
dic = {}
dic[x]=0
ans = [0]*(10**5+1)
ans[0]=x
a = x

for i in range(1, n):
  a = (a**2) % m
  ans[i]=ans[i-1]+a
  if a in dic:
    kuri = i - dic[a]
    kurisum =ans[i]-ans[dic[a]]
    nokori = n-i
    time = nokori//kuri
    amari = nokori%kuri
    if dic[a] == 0:
      amarisum = ans[amari-1]
    else:
      amarisum = ans[dic[a]-1+amari]-ans[dic[a]-1]
    print(ans[i-1]+amarisum+time*kurisum)
    quit()
  else:
    dic[a]=i
print(ans[n-1])

Measured memory_bytes: 76100
from itertools import count, takewhile
from functools import lru_cache
 
@lru_cache(maxsize=None)
def dfs(n):
  if n == 0: return 0
  
  max9 = max(takewhile(lambda x: x<=n, (9**i for i in count())))
  max6 = max(takewhile(lambda x: x<=n, (6**i for i in count())))
  return min(dfs(n-max9), dfs(n-max6))+1
 
print(dfs(int(input())))

Measured memory_bytes: 3572
n, k = map(int, input().split())
s = list(input())

import copy

# left to right, change L into R
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i, j in enumerate(s):
    if j == 'L':
        tmp_s[i] = 'R'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'R'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = cnt
# right to left, change L into R
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i in range(n-1, -1, -1):
    j = s[i]
    if j == 'L':
        tmp_s[i] = 'R'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'R'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = max(ans, cnt)

# left to right, change R into L
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i, j in enumerate(s):
    if j == 'R':
        tmp_s[i] = 'L'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'L'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = max(ans, cnt)

# right to left, change L into R
cnt = 0
tmp_s = copy.deepcopy(s)
flag = 1
for i in range(n-1, -1, -1):
    j = s[i]
    if j == 'R':
        tmp_s[i] = 'L'
        if flag:
            cnt += 1
            flag = 0
    else:
        tmp_s[i] = 'L'
        flag = 1

    if cnt >= k and flag:
        break

cnt = 0
for i in range(n):
    if tmp_s[i] == 'R' and i != n-1 and tmp_s[i+1] == 'R':
        cnt += 1
    elif tmp_s[i] == 'L' and i != 0 and tmp_s[i-1] == 'L':
        cnt += 1

ans = max(ans, cnt)

print(ans)

Measured memory_bytes: 92480
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<int,int> P;
const LL mod=1000000007;
const LL LINF=1LL<<60;
const int INF=1<<30;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};


vector<int> used;
bool f;
int c;

//loopの始点とcostを求める.
pair<int,int> rec(int u,vector<P> &next){
    c+=next[u].sc;
    if(used[next[u].fs]){
        f=true;
        return next[u];
    }
    used[u]=true;
    auto p = rec(next[u].fs,next);
    if(p.fs == u){
        f=false;
        return make_pair(p.fs,p.sc+next[u].sc);
    }
    else if(f){
        return make_pair(p.fs,p.sc+next[u].sc);
    }
    else{
        return p;
    }
}

int rec2(int u,int k,vector<P> &next){
    if(k==1) return u;
    if(k==0) return next.size();
    return rec2(next[u].fs,k-next[u].sc,next);
}


int main(){
    long n,k;cin >> n >> k;
    vector<int> a(n);
    used.resize(n+1);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<P> next(n,make_pair(-1,-1));
    vector<int> pos(200002,-1);
    for (int i = 0; i < 2; i++) {
        for (int j = n-1; j >= 0; j--) {
            if(next[j].fs==-1) next[j]=make_pair(pos[a[j]],(pos[a[j]]<=j+1?1:0));
            pos[a[j]]=(j+1)%n;
        }
    }
    if(next[n-1].fs==0) next[n-1].sc++;
    auto p = rec(0,next);
    int s;
    if(k<c) s=rec2(0,k,next);
    else s=rec2(p.fs,(k-c)%p.sc+p.sc,next);
    vector<int> ans;
    for (int i = s; i < n;) {
        if(next[i].sc){
            if(i!=n-1&&next[i].fs==0) break;
            ans.pb(a[i]);
            i++;
        }
        else{
            if(next[i].fs<i) break;
            i=next[i].fs;
        }
    }
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << (i==ans.size()-1?"\n":" ");
    }
    return 0;
}


Measured memory_bytes: 12532
//#define _GLIBCXX_DEBUG
#include "bits/stdc++.h"

using namespace std;

//------------------------------- Type Names -------------------------------//

using i64 = int_fast64_t;

using seika = string;
//{akari : 1D, yukari : 2D, maki : 3D} vector
template <class kizuna>
using akari = vector<kizuna>;
template <class yuzuki>
using yukari = akari<akari<yuzuki>>;
template <class tsurumaki>
using maki = akari<yukari<tsurumaki>>;
//{akane : ascending order, aoi : decending order} priority queue
template <class kotonoha>
using akane = priority_queue<kotonoha, akari<kotonoha>, greater<kotonoha>>;
template <class kotonoha>
using aoi = priority_queue<kotonoha>;

//------------------------------- Libraries ---------------------------------//

//------------------------------- Dubug Functions ---------------------------//

inline void print()
{
    cout << endl;
}
template <typename First, typename... Rest>
void print(const First &first, const Rest &... rest)
{
    cout << first << ' ';
    print(rest...);
}

//------------------------------- Solver ------------------------------------//

void solve()
{
    int n, k;
    cin >> n >> k;
    int ans = 0;
    while (n)
    {
        ans++;
        n /= k;
    }
    cout << ans << endl;
}

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


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
inline void in(int &x){
	char ch=getchar();
	int flag=1;
	while(!(ch>='0'&&ch<='9')) {
		if(ch=='-')
			flag*=-1;
		ch=getchar();
	}
	x=ch-'0';
	ch=getchar();
	while(ch>='0'&&ch<='9') {
		x=((x<<3)+(x<<1))+ch-'0';
		ch=getchar();
	}
	x*=flag;
}
int n,k,q,a[100005];
int main(){
	in(n);in(k);in(q);
	for(int i=1;i<=q;i++){
		int x;in(x);a[x]++;
	}
	for(int i=1;i<=n;i++){
		int now=k-q+a[i];
		if(now>0)printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}

Measured memory_bytes: 1024
n = int(input())
a = list(map(int, input().split()))

count=[0]*8
cnt = 0
for i in a:
    if i >=3200:
        cnt +=1
    else:
        count[i//400]+=1
cnt2= 0
for i in count:
    if i>0:
        cnt2+=1
if cnt2 == 0:
    print(1, cnt)
else:
    print(cnt2, cnt2+cnt)

Measured memory_bytes: 3064
import java.util.Scanner;
import java.util.Set;
import java.util.HashSet;

public class Main{
  static int n;
  static int[] a;

  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);

    n = sc.nextInt();
    a = new int[n];
    for(int i = 0; i < n; i++){
      a[i] = sc.nextInt();
    }

    Set< Integer > set = new HashSet< >();
    for(int i = 0; i < n; i++){
      set.add(a[i]);
    }

    int ans = set.size();
    if((n - ans) % 2 == 1){
      ans--;
    }

    System.out.println(ans);
  }
}



Measured memory_bytes: 52236
def partition(array, first, end):
    criteria = array[end]
    i_ins = first
    for i_cur in range(first, end):
        if array[i_cur] <= criteria:
            array[i_ins], array[i_cur] = array[i_cur], array[i_ins]
            i_ins += 1
    array[i_ins], array[end] = array[end], array[i_ins]
    return i_ins


def main():
    n = int(input())
    array = [int(x) for x in input().split()]
    i_ins = partition(array, 0, n-1)
    outputtxt = ""
    if i_ins != 0:
        outputtxt += " ".join([str(x) for x in array[:i_ins]]) + " "
    outputtxt += "[{}]".format(array[i_ins])
    if i_ins < n-1:
        outputtxt += " " + " ".join([str(x) for x in array[i_ins + 1:]])
    print(outputtxt)
    return


main()


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

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define forn(i,n) for(ll i=0;i<n;i++)
#define fore(i,a,b) for(ll i=a;i<=b;i++)
#define ford(i,n) for(ll i=n-1;i>=0;i--)
#define fi first
#define se second
#define endl "\n"
#define all(a) a.begin(),a.end()
#define sync ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define PI 3.14159265

/*************************************************************************************/
void file(){
	#ifndef ONLINE_JUDGE
    // for getting input from input.txt
    freopen("input.txt", "r", stdin);
    // for writing output to output.txt
    freopen("output.txt", "w", stdout);
    #endif
}
/*************************************************************************************/

const ll maxn=2e5+1,mod=1e9+7;



int main(){
    sync
    //file();
   	int n;
   	cin>>n;
   	vector<double> dp(n+1,0);
   	dp[0] = 1;
   	double ans = 0;
   	forn(i,n){
   	 	double x;
   	 	cin>>x;
   	 	for(int j = i+1;j>=0;j--){
   	 		if(j==0){
   	 			dp[j] = dp[j]*(1-x);
   	 		}
   	 		else{
   	 			dp[j] = dp[j-1]*x+dp[j]*(1-x);
   	 		}	
   	 	}
	}
		fore(i,1,n){
   	 		if(i>n/2) ans+=dp[i];
   	 	}
   	cout<<setprecision(10)<<fixed<<ans;
	return 0;
}


Measured memory_bytes: 256
inp = require('fs').readFileSync('/dev/stdin', 'utf8').trim().split('\n')
l = inp.shift().split(" ")
A = l.shift() * 1
B = l.shift() * 1
ans = -1
for (i=0; i<=10000; i++) {
    if (Math.floor(i*0.08) == A && Math.floor(i*0.1) == B) {
        ans = i;
        break;
    }
}
console.log(ans)

Measured memory_bytes: 21192
#include <bits/stdc++.h>
       
using namespace std;
typedef long long ll;
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; }
class ModInt {
  static int MOD;
  long long x;

 public:
  static void mod(int m) { MOD = m; }

  ModInt(long long v = 0) : x(v % MOD) {
    if (x < 0) x += MOD;
  }

  ModInt& operator+=(const ModInt& r) {
    x += r.x;
    if (x >= MOD) x -= MOD;
    return *this;
  }

  ModInt& operator-=(const ModInt& r) {
    x -= r.x;
    if (x < 0) x += MOD;
    return *this;
  }
  ModInt& operator*=(const ModInt& r) {
    x = (x * r.x) % MOD;
    return *this;
  }
  ModInt& operator/=(const ModInt& r) {
    *this *= r.inverse();
    return *this;
  }

  ModInt operator-() const { return ModInt(-x); }

  ModInt operator+(const ModInt& r) const { return ModInt(*this) += r; }
  ModInt operator-(const ModInt& r) const { return ModInt(*this) -= r; }
  ModInt operator*(const ModInt& r) const { return ModInt(*this) *= r; }
  ModInt operator/(const ModInt& r) const { return ModInt(*this) /= r; }
  bool operator==(const ModInt& r) const { return x == r.x; }
  bool operator!=(const ModInt& r) const { return x != r.x; }

  ModInt inverse() const {
    long long a = x, b = MOD, u = 1, v = 0, t;
    while (b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ModInt(u);
  }

  ModInt pow(long long n) const {
    if (n < 0) return pow(-n).inverse();

    ModInt ret(1), mul(x);
    while (n > 0) {
      if (n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream& operator<<(ostream& os, const ModInt& x) { return os << x.x; }

  friend istream& operator>>(istream& is, ModInt& x) { return is >> x.x; }

  int getMod() { return MOD; }

  long long val() { return x; }
};
int ModInt::MOD = 1000000007;

int main() {
  ModInt::mod(998244353);

  int N, S;
  cin >> N >> S;
  vector<int> A(N);
  for (int i = 0; i < N; ++i) {
    cin >> A[i];
  }

  enum State {
    PENDING,
    OPEN,
    CLOSED,
  };
  vector<vector<vector<ModInt>>> dp(
      N + 1, vector<vector<ModInt>>(S + 1, vector<ModInt>(3, 0)));
  dp[0][0][PENDING] = 1;

  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < S + 1; ++j) {
      dp[i + 1][j][CLOSED] += dp[i][j][CLOSED];
      dp[i + 1][j][OPEN] += dp[i][j][OPEN];
      dp[i + 1][j][CLOSED] += dp[i][j][OPEN];

      if (j - A[i] >= 0) {
        dp[i + 1][j][OPEN] += dp[i][j - A[i]][OPEN];
        dp[i + 1][j][CLOSED] += dp[i][j - A[i]][OPEN];
      }
      dp[i + 1][j][PENDING] += dp[i][j][PENDING];
      dp[i + 1][j][OPEN] += dp[i][j][PENDING];

      if (j - A[i] >= 0) {
        dp[i + 1][j][OPEN] += dp[i][j - A[i]][PENDING];
        dp[i + 1][j][CLOSED] += dp[i][j - A[i]][PENDING];
      }
    }
  }

  cout << dp[N][S][CLOSED] << endl;
  return 0;
}


Measured memory_bytes: 493056
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const double eps = 1e-7;
#define endl '\n'
#define pb(a) push_back(a)
#define ALL(x) x.begin(), x.end()
#define SIZE(x) int(x.size())
#define IOS ios::sync_with_stdio(0);

int n;
int a[N],b[N];
int main() {
	scanf("%d",&n);
	int x=0;
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),x^=a[i];
	for(int i=1;i<=n;++i) {
//		b[i]=a[1]^a[i]^b[1];
		b[i] = x^a[i];
	}
	for(int i=1;i<=n;++i) printf("%d ",b[i]);

	return 0;
	
} 

Measured memory_bytes: 5236
#include <iostream>
#include <assert.h>
#include <stdlib.h>
#include <time.h>
#include <stdio.h>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <string>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;

const int N = 1e5 + 2;

int n, a[4][N];
long long dp[N][4];

long long calc(int i, int prv)
{
    if (i == n)
    {
        return 0;
    }
    long long &ret = dp[i][prv];
    if (ret != -1)
    {
        return ret;
    }
    ret = 0;
    for (int j = 1; j <= 3; ++j)
    {
        if (j != prv)
        {
            ret = max(ret, calc(i + 1, j) + a[j][i]);
        }
    }
    return ret;
}

int main()
{
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 1; j <= 3; ++j)
        {
            cin >> a[j][i];
        }
    }
    cout << calc(0, 0) << endl;
    return 0;
}

Measured memory_bytes: 12800
import sys
N,L=map(int,input().split())
A=[int(i) for i in input().split()]
flag=True
a=-1
for i in range(N-1):
    if A[i+1]+A[i]>=L:
        flag=False
        a=i+1
        break
if flag:
    print('Impossible')
    sys.exit()
print('Possible')
for i in range(1,a):
    print(i)
for i in range(N-1,a,-1):
    print(i)
print(a)


Measured memory_bytes: 63984
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

def solve():
    N = int(readline())
    if N == 0:
        return False
    L = 0
    n_map = {}
    def get(s):
        nonlocal L
        if s in n_map:
            return n_map[s]
        n_map[s] = L
        L += 1
        return L-1

    G = [[] for i in range(2*N)]
    RG = [[] for i in range(2*N)]
    for i in range(N):
        a, b = readline().strip().split("-")
        ka = get(a); kb = get(b)
        G[ka].append(kb)
        RG[kb].append(ka)

    F = [[-1]*L for i in range(L)]
    for v in range(L):
        for w1 in G[v]:
            for w2 in G[v]:
                F[w1][w2] = 1
        for w1 in RG[v]:
            for w2 in RG[v]:
                F[w1][w2] = 1
    for v in range(L):
        for w1 in G[v]:
            for w2 in RG[v]:
                F[w1][w2] = F[w2][w1] = 0

    G0 = [[] for i in range(L)]
    for v in range(L):
        for w in range(L):
            if F[v][w] == 1:
                G0[v].append(w)
                G0[w].append(v)

    PS = []
    que = deque()
    for i in range(L):
        P = [-1]*L
        que.append(i)
        P[i] = 0
        while que:
            v = que.popleft()
            p = P[v]
            for w in G[v]:
                if P[w] != -1:
                    continue
                P[w] = p^1
                que.append(w)
            for w in G0[v]:
                if P[w] != -1:
                    continue
                P[w] = p
                que.append(w)
        PS.append(P)

    write("%d\n" % L)
    M = int(readline())
    for i in range(M):
        a, b = readline().strip().split("-")
        ka = n_map.get(a, -1); kb = n_map.get(b, -1)
        if ka == -1 or kb == -1:
            write("NO\n")
            continue
        write("YES\n" if PS[ka][kb] == 1 else "NO\n")
    return True
while solve():
    ...



Measured memory_bytes: 7060
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int main(){
  LL INF=1LL<<35;
  int H, N;
  cin >> H >> N;
  LL A[1010];
  LL B[1010];
  for(int i=0; i<N; i++) cin >> A[i] >> B[i];
  LL dp[10010];
  for(int i=0; i<=H; i++) dp[i]=INF;
  dp[0]=0;
  for(int i=1; i<=H; i++){
    for(int j=0; j<N; j++){
      if(i>=A[j]) dp[i]=min(dp[i], dp[i-A[j]]+B[j]);
      else dp[i]=min(dp[i],B[j]);
    }
  }
  cout << dp[H] << endl;
  
  return 0;
}

Measured memory_bytes: 384
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF= 1LL << 60;
#define REP(i,n) for(ll i=0; i<n; i++)
#define FOR(i,a,n) for(ll i=a; i<n; i++)
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n;
    string s;
    string ss= "ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZ";

    cin >> n >> s;
    REP(i,s.length()){
        cout << ss[s[i]-'A'+n];
    }cout << endl;
}

Measured memory_bytes: 256
#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <queue>
#include <cmath>
#include <stack>
#include <map>
#include <vector>
#include <algorithm>

#define int64 long long int
using namespace std;

void move(int *, int);
int ans(int num[100][50], int);

int main()
{
	int c, h, w, k;
	int num[100][50]={0};
	char buf[3];
	h=0, w=0, k=0;
	while((c = getchar()) != EOF){
		if('0' <= c && c <= '9'){
			buf[k] = c;
			k++;
		} else if(c == ',') {
			buf[k] = 0;
			num[h][w] = atoi(buf);
			k = 0;
			w++;
		} else {
			buf[k] = 0;
			num[h][w] = atoi(buf);
			k = 0;
			w = 0;
			h++;
		}
	}

	w = (h+1)/2;

	for(int i=w; i<h; i++)
		move(num[i], i-w+1);

	cout << ans(num, h) << '\n';

	return 0;
}

int ans(int num[100][50], int h){

	for(int i=h-1; i>0; i--){
		for(int j=0; j<i; j++){
			num[i-1][j] += max(num[i][j], num[i][j+1]);
		}
	}
	return num[0][0];
}

void move(int *a, int n)
{
	int b[50]={0};
	for(int i=0; i<50-n; i++)
		b[n+i] = a[i];
	for(int i=0; i<50; i++)
		a[i] = b[i];
	return;
}

Measured memory_bytes: 1156
#include <stdio.h>

int mark2num(char c) {
  if(c == 'S') return 0;
  if(c == 'H') return 1;
  if(c == 'C') return 2;
  if(c == 'D') return 3;
  return -1;
}

int num2mark(int num) {
  if(num == 0) return 'S';
  if(num == 1) return 'H';
  if(num == 2) return 'C';
  if(num == 3) return 'D';
  return 'Z';
}

void Out(int C[], int N) {
  int i;
  for(i = 0; i < N; i++) {
    if(i) printf(" ");
    printf("%c%d", num2mark(C[i]/9), C[i]%9+1);
  }
  puts("");
}

int B[55];

void BubbleSort(int A[], int N) {
  int C[55], tmp;
  int i, j;
  for(i = 0; i < N; i++) C[i] = A[i];
  for(i = 0; i < N-1; i++){
    for(j = N-1; j > i; j--) {
      if(C[j]%9 < C[j-1]%9) {
	tmp = C[j];
	C[j] = C[j-1];
	C[j-1] = tmp;
      }
    }
  }  
  Out(C, N);
  puts("Stable");
  for(i = 0; i < N; i++) B[i] = C[i];
}

void SelectionSort(int A[], int N) {
  int C[55], tmp, mni;
  int i, j;
  for(i = 0; i < N; i++) C[i] = A[i];
  for(i = 0; i < N; i++) {
    mni = i;
    for(j = i; j < N; j++) {
      if(C[j]%9 < C[mni]%9) mni = j;
    }
    if(mni != i) {
      tmp = C[i];
      C[i] = C[mni];
      C[mni] = tmp;
    }
  }
  Out(C, N);
  for(i = 0; i < N; i++) {
    if(C[i] != B[i]) {
      puts("Not stable");
      return;
    }
  }
  puts("Stable");
}

int main() {
  int N, A[55];
  int i;
  char c[3];
  scanf("%d", &N);
  for(i = 0; i < N; i++) {
    scanf("%s", c);    
    A[i] = mark2num(c[0]) * 9 + (c[1]-'0')-1;
  }
  BubbleSort(A, N);
  SelectionSort(A, N);
  return 0;
}

Measured memory_bytes: 612
using System;
public class Hello{
    
    public static void replace(string x,string y,string rep)
    {
        //forの中で0から文字数まで回してa~bの間ならみたいなコードにする
        int a=int.Parse(x);
        int b=int.Parse(y);
        string str="";
        int aida=0;
        for(int i=0;i<target.Length;i++)
        {
            if(i>=a&&i<=b)
            {
                str+=rep[aida];
                aida++;
            }
            else str+=target[i];
        }
        target=str;
    }
    
    public static void reverse(string x,string y)
    {
        int a=int.Parse(x);
        int b=int.Parse(y);
        string str="";
        int aida=b;
        for(int i=0;i<target.Length;i++)
        {
            if(i>=a&&i<=b)
            {
                str+=target[aida];
                aida--;
            }
            else str+=target[i];
        }
        target=str;
    }
    public static void print(string x, string y)
    {
        int a=int.Parse(x);
        int b=int.Parse(y);
        Console.WriteLine(target.Substring(a,b-a+1));
    }
    
    public static string target;
    
    public static void Main(){
        
        target=Console.ReadLine();
        int kaisu=int.Parse(Console.ReadLine());
        string [] str;
        
        for(int i=0;i<kaisu;i++)
        {
            str=Console.ReadLine().Split(' ');
            if(str[0]=="replace")replace(str[1],str[2],str[3]);
            else if(str[0]=="reverse")reverse(str[1],str[2]);
            else print(str[1],str[2]);
        }
    }
}



Measured memory_bytes: 20048
n, a, b, c = map(int, input().split())
s = [input() for _ in range(n)]
ans = []
flg = True
def adding(x, y):
    x += 1
    y -= 1

for i in range(n):
    if s[i] == 'AB':
        if a == b:
            if i < n-1:
                if s[i+1] == 'AC':
                    a += 1
                    b -= 1
                    ans.append('A')
                elif s[i+1] == 'BC':
                    b += 1
                    a -= 1
                    ans.append('B')
                else:
                    a += 1
                    b -= 1
                    ans.append('A')
            else:
                a += 1
                b -= 1
                ans.append('A')
        elif a < b:
            a += 1
            b -= 1
            ans.append('A')
        else:
            b += 1
            a -= 1
            ans.append('B')

    if s[i] == 'AC':
        if a == c:
            if i < n - 1:
                if s[i + 1] == 'AB':
                    a += 1
                    c -= 1
                    ans.append('A')
                elif s[i + 1] == 'BC':
                    c += 1
                    a -= 1
                    ans.append('C')
                else:
                    a += 1
                    c -= 1
                    ans.append('A')
            else:
                a += 1
                c -= 1
                ans.append('A')
        elif a < c:
            a += 1
            c -= 1
            ans.append('A')
        else:
            c += 1
            a -= 1
            ans.append('C')

    if s[i] == 'BC':
        if b == c:
            if i < n - 1:
                if s[i + 1] == 'AB':
                    b += 1
                    c -= 1
                    ans.append('B')
                elif s[i + 1] == 'AC':
                    c += 1
                    b -= 1
                    ans.append('C')
                else:
                    b += 1
                    c -= 1
                    ans.append('B')
            else:
                b += 1
                c -= 1
                ans.append('B')
        elif b < c:
            b += 1
            c -= 1
            ans.append('B')
        else:
            c += 1
            b -= 1
            ans.append('C')

    #print(a, b, c)
    if a < 0 or b < 0 or c < 0:
        flg = False
        break

if flg:
    print('Yes')
    print(*ans, sep='\n')

else:
    print('No')

Measured memory_bytes: 18700
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<cmath>
#include<iomanip>
#include<set>
#include<numeric>
#include<sstream>
#include<random>
#include<cassert>
using namespace std;
typedef long long ll;
#define rep(i, n) for (int i = 0; i < n; ++i)
#define rrep(i, st, n) for (int i = st; i < n; ++i)
using pii = pair<int, int>;
const int inf = 1e9 + 7;
int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {1, -1, 0, 0, -1, 1, 1, -1};
#define ceil(a, b) a / b + !!(a % b)

int main() {
    int n, t; cin >> n >> t;
    int a[n]; rep(i, n) cin >> a[i];
    int mmax = 0, c = 0, mmin = a[0];
    rrep(i, 1, n) {
        if (a[i] - mmin > mmax) {
            mmax = a[i] - mmin;
            c = 1;
        } else if (a[i] - mmin == mmax) {
            c++;
        }
        mmin = min(mmin, a[i]);
    }
    cout << c << endl;
}


Measured memory_bytes: 640
#include<iostream>
#include<algorithm>
#include<cmath>
#include<map>
#include<set>
#include<cstring>
#include<queue>
#include<stack>
#include<string>
#include<cstdio>
using namespace std;
typedef long long LL;
#define For(a,b,c) for(int a=b;a<=c;a++)
#define For_(a,b,c) for(int a=b;a>=c;a--)
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define pb push_back
#define debug(x) cout<<#x<<" "<<x<<" "
int read(){
    int r=0,f=1;
    char c=getchar();
    while(!isdigit(c)){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(isdigit(c)){
        r=(r<<1)+(r<<3)+c-'0';
        c=getchar();
    }
    return r*f;
}

int main(){
    int n;
    cin>>n;
    cout<<n+n*n+n*n*n;
    return 0;
}

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

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

    vector<pair<ll, ll>> p(N);
    rep(i, N) {
        int a, b;
        cin >> a >> b;
        p[i] = make_pair(a, b);
    }

    sort(p.begin(), p.end(), [&](const pair<ll, ll> x, pair<ll, ll> y) {return x.second < y.second;});

    ll time = 0;

    rep(i, N) {
        time += p[i].first;
        if (time > p[i].second) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;

    return 0;
}

Measured memory_bytes: 3328
#include<stdio.h>
#include<string.h>
int main()
{
    int i,j,lenw,lens,lent;
    char s[101],t[101],w[202];
    scanf("%s%s",&s,&t);
    lens=strlen(s);
    lent=strlen(t);
    lenw=lens+lent;
    for(i=0;i<lent;i++)
    {
        w[i]=t[i];
    }
    for(i=lent;i<lenw;i++)
    {
        w[i]=s[i-lent];
    }
    w[lenw]='\0';

    puts(w);

    return 0;
}


Measured memory_bytes: 128
#include<cstdio>
#include<algorithm>

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

using namespace std;

int m,n;
double p[16][16];

double dp[1<<16][16];
double dfs(int S,int pos){
	if(pos==n) return 1;
	if( S ==0) return 0;

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

	double res=0;
	rep(i,m) if(S&1<<i) { // 猫 i を派遣する
		double tmp=0,q=1;
		for(int j=pos;j<n;j++){ // j 番目の敵にやられた
			tmp+=q*(1-p[i][j])*dfs(S&~(1<<i),j);
			q*=p[i][j];
		}
		tmp+=q*dfs(S&~(1<<i),n); // ゴール
		res=max(res,tmp);
	}
	return dp[S][pos]=res;
}

int main(){
	scanf("%d%d",&m,&n);
	rep(i,m) rep(j,n) scanf("%lf",p[i]+j);

	rep(S,1<<m) rep(j,n) dp[S][j]=-1;
	printf("%.15f\n",dfs((1<<m)-1,0));

	return 0;
}

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

using namespace std;
using ll = long long;
int main(){
    int n;
    cin >> n;
    vector<ll> a(n);
    for(auto &e : a)cin >> e;
    vector<ll> dp(n+1);
    ll sum = a[0]; 
    for(int i = 2 ; i <= n ; i++){
        //3状態の場合分をiの偶奇で行う
        if(i % 2 == 0) {
            dp[i] = max(a[i-1] + dp[i-2], sum);
        } 
        else {

            dp[i] = max(a[i-1] + dp[i-2], dp[i-1]);
            sum += a[i-1];
        }
    }
    cout << dp[n] << endl;
    return 0;
}


Measured memory_bytes: 6396
#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<algorithm>
#include<numeric>
#include<cmath>
#include<queue>
#include<stack>
#include<list>
#include<unordered_map>
#include<unordered_set>

using namespace std;
typedef long long int ll;typedef pair<int, int> P;
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define ALL(a) (a).begin(),(a).end()

int main(void) {
	int n; cin >> n;
	vector<ll> v(n+1), vv(n);
	ll res = 0;
	rep(i, n + 1)cin >> v[i];
	rep(i, n)cin >> vv[i];
	rep(i, n) {
		if (v[i] >= vv[i])res += vv[i];
		else {
			res += v[i];
			vv[i] -= v[i];
			if (v[i + 1] >= vv[i]) {
				res += vv[i];
				v[i + 1] -= vv[i];
			}
			else {
				res += v[i + 1];
				v[i + 1] = 0;
			}
		}
	}
	cout << res << endl;
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
  
  int n;
  cin >> n;
  
  map<string,int> cnt;
  
  while(n--){
    string s;
    cin >> s;
    cnt[s]++;
  }
  
  cout << "AC" << " x " << cnt["AC"] << endl;
  cout << "WA" << " x " << cnt["WA"] << endl;
  cout << "TLE" << " x " << cnt["TLE"] << endl;
  cout << "RE" << " x " << cnt["RE"] << endl;
  
  return 0;
}


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

#define ll long long int
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define INF 0x3f3f3f3f
#define show(x) cerr<<#x<<" : "<<x<<'\n';
#define yogeshk972() cerr<<"\nTime Taken : "<<(float)(clock()-time_p)/CLOCKS_PER_SEC<<"\n";
clock_t time_p=clock();

using namespace std;
const int N=2e5+1, mod= 1e9+7;


int main(){
	ios_base::sync_with_stdio(0);	cin.tie(0);
	int n; ll res=0;
	cin>>n;
	vector<ll> f(2e3+1),l(n);
	
	for(int i=0;i<n;i++){
		cin>>l[i];
		f[l[i]]++;
	}
	
	for(int i=1;i<2e3+1;i++)f[i]+=f[i-1];
	
	sort(l.begin(),l.end());
	
	for(int i=0;i<n;i++){  
		for(int j=i+1;j<n;j++){
			int a=l[i],b=l[j];
			res+=f[a+b-1]-f[b-a] - (a>b-a) - 1;
		}
	}
	cout<<res/3;
	
    yogeshk972();
}


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

const int maxn = 2e5 + 12;
long long int cnt[12][12], ans, n;

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
	int f = i % 10;
	int s;
	int dc = i;
	while(dc) {
	    s = dc % 10;
	    dc /= 10;
	}
	cnt[f][s]++;
    }
    for (int i = 0; i < 10; i++) {
	for (int j = 0; j < 10; j++) {
	    ans += cnt[i][j] * cnt[j][i];
	}
    }
    cout << ans;
}


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



int main()
{
  int n;
  cin >> n;
  int ans = 0;

  while(n>1){
    n/=2;
    ans++;
  }

  cout << (1 << ans) << endl;

  return 0;
}

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

string s;
int cnt = 0;

int main () {
	cin >> s;
	for (char c = 'a'; c <= 'z'; c++){
		if (s.find(c) == -1){
			cnt++;
		}
	}
	if (cnt == 26 - s.length()){
		cout << "yes";
	} else {
		cout << "no";
	}
}

Measured memory_bytes: 3620
(declaim (optimize (speed 3) (debug 0) (safety 0)))

(let ((q (read))
      (h (read))
      (s (read))
      (d (read))
      (n (read))
      (p 0))
  (setf s (min (* 4 q) (* 2 h) s))
  (when (= (mod n 2) 1)
    (setf n (- n 1))
    (setf p 1))
  (if (< (+ (* d (/ n 2)) (* p s)) (* (+ p n) s))
    (setf a (+ (* d (/ n 2)) (* p s)))
    (setf a (* (+ p n) s)))
  (format t "~A~%" a))

Measured memory_bytes: 6504
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,input;
	cin>>n;
	map<int,int> m;
	for(int i = 0;i<n -  1;i++){
		cin>>input;
		m[input] += 1;
	}
	for(int i = 1;i<=n;i++){
		cout<<m[i]<<"\n";
	}
    return 0;
}


Measured memory_bytes: 13008
N,W = map(int,input().split())
dp = [0] + [float('inf')]*10**5

for _ in range(N):
    w,v = map(int,input().split())
    for j in range(10**5,v-1,-1):
        dp[j] = min(dp[j], dp[j-v] + w)
for i,x in enumerate(dp):
    if x <=W: ans = i
print(ans)


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

using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
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;}
#define ALL(a) (a).begin(), (a).end()
#define FOR(i, a, b) for (int i=(a);(i)<(b);(i)++)
#define REP(i, n) for (int i=0;(i)<(n);(i)++)
#define REPS(i, n) for (int i=1;(i)<=(n);(i)++)
#define RREP(i, n) for (int i=(x-1);(i)>=0;(i)--)
#define RREPS(i, n) for (int i=n;(i)>0;(i)--)
#define len(x) ((int)(x).size())
#define print(x) (cout<<(x)<<"\n")

// LIBRARY
// Union-Find
struct UnionFind {
    vector<int> data;
    UnionFind(int size):data(size, -1){}
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if (x==y) return;
        if (data[y]<data[x]) swap(x, y);
        data[x] += data[y];
        data[y] = x;
    }
    bool same(int x, int y) {
        return root(x)==root(y);
    }
    int root(int x) {
        return data[x]<0 ? x : data[x]=root(data[x]);
    }
    int size(int x) {
        return -data[root(x)];
    }
};

// SOLVE
signed main() {
    cin.tie(0);
   	ios::sync_with_stdio(false);
    
    int N, K, L; cin>>N>>K>>L;
    UnionFind road(N);
    UnionFind train(N);
    REP(i, K) {
        int p, q; cin>>p>>q; p--; q--;
        road.unite(p, q);
    }
    REP(i, L) {
        int p, q; cin>>p>>q; p--; q--;
        train.unite(p, q);
    }
    map<pair<int, int>, int> cnt;
    REP(i, N) {
        cnt[make_pair(road.root(i), train.root(i))]++;
    }
    REP(i, N) {
        print(cnt[make_pair(road.root(i), train.root(i))]);
    }
}

Measured memory_bytes: 13568
package main

import "fmt"

func main() {
	var N, M int
	fmt.Scan(&N, &M)
	A := make([]int, N)
	total := 0
	for i := 0; i < N; i++ {
		fmt.Scan(&A[i])
		total += A[i]
	}

	count := N
	for j := range A {
		if float64(A[j]) < float64(total)/float64(4*M) {
			count--
		}
	}

	if count >= M {
		fmt.Println("Yes")
	} else {
		fmt.Println("No")
	}
}

Measured memory_bytes: 512