akhauriyash/Code-Regression huggingface dataset:
N, K = map(int,input().split())
cost= input().split()
cost = [int(i) for i in cost]
ans_list = [0]*N
ans_list[1] = abs(cost[0] - cost[1])
for i in range(2,N):
  compare_num = 10**10
  for j in range(1,K+1):
    if i-j >=0:
      num = ans_list[i-j] + abs(cost[i-j]-cost[i])
      if compare_num >= num:
        compare_num = num
  ans_list[i] = compare_num
print(ans_list.pop())
    
    

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


int main(){

    int n,m;
    cin >> n >> m;

    if(n==1){
        int ans=0,s,c;
        if(m==0){
            cout << 0 <<endl;
            return 0;
        }else if(m==1){
            cin >> s >> c ;
            cout << c << endl;
            return 0;
        }

    }

    int a[n];

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

    bool te=true;
    int s,c;
    for(int i=0;i<m;i++){
        cin >> s >> c;
        if(s==1 && c==0){
            te=false;
        }
        if(a[s-1]==0){
            a[s-1]=c;
        }else if(a[s-1]==c){

        }else{
            te=false;
        }

    }

    if(n==1){

    }else if(a[0]==0){
        a[0]=1;
        }

    if(te){
        for(int i=0;i<n;i++){
            cout << a[i];
        }
        cout << endl;
    }else{
        cout << "-1" << endl;
    }

}


Measured memory_bytes: 256
// IO library
#include <cstdio>
#include <iomanip>
#include <ios>
#include <iostream>

// algorithm library
#include <algorithm>
#include <cmath>
#include <numeric>

// container library
#include <deque>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

// namespace
using namespace std;

// typedef
typedef long long ll;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<ll> VL;
typedef vector<VL> VVL;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VB> VVB;

// conversion
#define INT(c) static_cast<int>(c)
#define CHAR(n) static_cast<char>(n)
#define LL(n) static_cast<ll>(n)

// container
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define SORT(c) sort((c).begin(), (c).end())
#define GSORT(c) sort((c).begin(), (c).end(), greater<decltype((c).front())>())
#define SZ(x) (INT((x).size()))
#define MEMSET(c, v) memset((c), v, sizeof(c))

// repetition
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define REP(i, n) FOR(i, 0, n)
#define NREP(i, n) FOR(i, 1, n + 1)
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)
#define RREP(i, n) RFOR(i, n, 0)
#define RNREP(i, n) RFOR(i, n, 1)

// constant
// const ll MOD = 1e9 + 7;
// const int INF = 1<<25;
// const ll INF = 1LL<<50;
// const int dx[4] = {0, -1, 1, 0};
// const int dy[4] = {-1, 0, 0, 1};
// const int dx[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
// const int dy[8] = {-1, -1, -1, 0, 0, 1, 1, 1};

// debug
#define test(x) cout << #x << " = " << x << endl

// answer output
#define Yes(c) cout << ((c) ? "Yes" : "No") << endl;
#define YES(c) cout << ((c) ? "YES" : "NO") << endl;
#define yes(c) cout << ((c) ? "yes" : "no") << endl;

#define possible(c) cout << ((c) ? "possible" : "impossible") << endl;
#define POSSIBLE(c) cout << ((c) ? "POSSIBLE" : "INPOSSIBLE") << endl;


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


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

  int a, b, h;
  cin >> a >> b >> h;
  cout << (a + b) * (h / 2) << endl;
  return 0;
}

Measured memory_bytes: 256
while True:
    m,mn,mx = map(int,input().split())
    if m==0: break
    l = [int(input()) for _ in range(m)]
    r = []
    for i in range(mn,mx+1):
        r += [l[i-1]-l[i]]
    print(max([i+mn for i,x in enumerate(r) if x==max(r)]))

Measured memory_bytes: 7632
#include<bits/stdc++.h>
#define Mod 1000000007
#define N 5005
using namespace std;
int dp[N][N],n;char s[N];
inline int ksm(int x,int y){
	int ans1=1;while (y){
		if (y&1) ans1=1ll*ans1*x%Mod;
		y>>=1;x=1ll*x*x%Mod;
	}return ans1;
} 
int main(){
	scanf("%d",&n);scanf("%s",s+1);
	int m=strlen(s+1);dp[0][0]=1;
	for (int i=0;i<n;i++){
		for (int j=0;j<=i;j++){
			dp[i+1][j+1]=1ll*(dp[i+1][j+1]+1ll*dp[i][j]*2%Mod)%Mod;
			dp[i+1][max(0,j-1)]=1ll*(dp[i+1][max(0,j-1)]+dp[i][j])%Mod;
		}
	}
	//cerr<<dp[n][m]<<endl;
	printf("%lld\n",1ll*dp[n][m]*ksm(ksm(2,m),Mod-2)%Mod);
	return 0;
}

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

max_n = max(a)
a.remove(max_n)

half = max_n/2
tmp = float("inf")
result = 0
for i in a:
    if tmp > abs(half-i):
        tmp = abs(half-i)
        result = i
print(max_n, result)


Measured memory_bytes: 14432
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
//#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define for0(i, n) for(int i = 0; i < (n); i++)
#define for1(i, n) for(int i = 1; i <= (n);i++)
#define mp make_pair
#define all(x) x.begin(),x.end()
using namespace std;
int input() {
	int r;
	cin >> r;
	//scanf("%lld", &r);
	return r;
}
int n, ans;
string s;
signed main() {
	cin >> n >> s;
	int b = 0;
	for (char ch : s)b += (ch == 'B');
	for0(i, n) {
		if (s[i] != 'R')continue;
		for0(j, n) {
			if (s[j] != 'G')continue;
			ans += b;
			int p = max(i, j) + abs(i - j);
			if (0 <= p && p < n&&s[p] == 'B')ans--;
			p = min(i, j) - abs(i - j);
			if (0 <= p && p < n&&s[p] == 'B')ans--;
			if ((i + j) % 2 == 0) {
				p = (i + j) / 2;
				if (s[p] == 'B')ans--;
			}
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 3636
#include<stdio.h>
int main(void)
{
	int a,b,c;
	scanf("%d %d %d",&a,&b,&c);
	if(a==b){
		printf("%d\n",c);
	}
	else if(b==c){
		printf("%d\n",a);
	}
	else if(c==a){
		printf("%d\n",b);
	}
	return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MM = 1000000000;
const int MOD = MM + 7;
const int MAX = 510000;
#define rep(i, n) for(ll i=0; i<n; i++)
#define Rep(i, j, n) for(ll i=j; i<n; i++)
#define all(vec) vec.begin(), vec.end()
template<class T> inline bool chmin(T& a, T b) {if(a > b) {a = b; return true;} return false;}
template<class T> inline bool chmax(T& a, T b) {if(a < b) {a = b; return true;} return false;}
const ll INF = 1LL << 60;
const double pi = acos(-1.0);

int main() {
    int n; cin >> n;
    int ans = n * 800;
    ans -= n/15 * 200;
    cout << ans << endl;
}

Measured memory_bytes: 3560
#include<stdio.h>
#include<string.h>
 
int main(void){
	char s[200010]; scanf("%s", &s);
	char t[200010]; scanf("%s", &t);
	int count = 0;
 
	for(int i=0;i<strlen(s);i++){
		if(s[i] != t[i])count++;
	}
 
	printf("%d\n",count);
	return 0;
}

Measured memory_bytes: 2080
#include<stdio.h>
int main()
{
	int W,h,x,y,r;
	scanf("%d %d %d %d %d",&W,&h,&x,&y,&r);
	if(x+r > W ||x-r <0 ||y+r > h ||y-r < 0)
		printf("No\n");
	else
		printf("Yes\n");
	return 0;
}


Measured memory_bytes: 2128
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
typedef long long ll;
const int maxn=1e5+111;
int main(){
    ll pp=100;
    ll md;
    scanf("%lld",&md);
    ll ans=0;
    while(pp<md){
        pp=(ll)(1.0*pp*1.01);
        ++ans;
    }
    printf("%lld\n",ans);
    return 0;
}

Measured memory_bytes: 3832
n = int(input())
s = {}
for i in range(n):
    inp = input()
    try:
        s[inp] += 1
    except:
        s[inp] = 1
m = int(input())
for i in range(m):
    inp = input()
    try:
        s[inp] -= 1
    except:
        s[inp] = -1
print(max(max(s.values()),0))

Measured memory_bytes: 3060
#!/usr/bin/env python3
# -*- coding: utf-8 -*-


def main():
    S = int(input())

    result = []

    while S not in result:
        result.append(S)
        if S % 2 == 0:
            S = S // 2
        else:
            S = 3 * S + 1

    print(len(result) + 1)


if __name__ == "__main__":
    main()


Measured memory_bytes: 2940
import sys
input = sys.stdin.readline
n,m=map(int,input().split())
import heapq
A=[]
for i in range(n):
  a,b=map(int,input().split())
  A.append([a,-b])
A.sort(key=lambda x:(x[0],x[1]))
B=[]
heapq.heapify(B)
ans=0
c=0
for i in reversed(range(m)):
  while c<n:
    a,b=A[c]
    if i+a<=m:
      heapq.heappush(B,[b,a])
      c+=1
    else:
      break
  if len(B)==0:
    continue
  else:
    bb,aa=heapq.heappop(B)
    ans+=bb
print(-ans)




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

const int64_t MOD = 998244353;
void add(int64_t& a, int64_t b){
    a = (a+b) % MOD;
}
void mul(int64_t& a, int64_t b){
    a = a*b % MOD;
}

int64_t power_mod(int64_t num, int64_t power){
    int64_t prod = 1;
    num %= MOD;
    while(power > 0){
        if(power&1) prod = prod * num % MOD;
        num = num * num % MOD;
        power >>= 1;
    }
    return prod;
}

int nth_bit(int64_t num, int n){
    return (num >> n) & 1;
}

typedef pair<int, int> P;
int64_t dp[100000][32];

int main(){
    int N, M;
    cin >> N >> M;
    map<P, int> mp_in, mp_out;
    for(int i=0; i<M; i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        if(abs(a-b) >= 3){
            mp_out[{a, b}] = c;
        }else{
            mp_in[{a, b}] = c;
        }
    }

    int64_t free_out = (int64_t) (N-3) * (N-2) / 2;
    for(auto& p : mp_out){
        int i = p.first.first, j = p.first.second;
        if(mp_out.count({j, i})){
            if(p.second != mp_out[{j, i}]){
                cout << 0 << endl;
                return 0;
            }else if(i > j){
                free_out--;
            }
        }else{
            free_out--;
        }
    }
    int64_t ans_out = power_mod(2, free_out);

    if(mp_in.count({0, 0})){
        dp[0][mp_in[{0, 0}]*3] = 1;
    }else{
        dp[0][0] = dp[0][3] = 1;
    }

    vector<int> allowed_bits;
    for(int b=0; b<32; b++){
        if((nth_bit(b, 0) ^ nth_bit(b, 1) ^ nth_bit(b, 2)) == 0) allowed_bits.push_back(b);
    }

    for(int i=0; i<N-2; i++){
        vector<P> pts = {{i+1, i+1}, {i+2, i}, {i, i+2}, {i+1, i}, {i, i+1}};
        for(int b1 : allowed_bits){
            for(int b2 : allowed_bits){
                if(nth_bit(b1, 0) ^ nth_bit(b2, 0) ^ nth_bit(b2, 3) ^ nth_bit(b2, 4)) continue;
                bool ok = true;
                for(int k=0; k<5; k++) if(mp_in.count(pts[k]) && mp_in[pts[k]] != nth_bit(b2, k)) ok = false;
                if(ok) add(dp[i+1][b2], dp[i][b1]);
            }
        }
    }

    int64_t ans_in = 0;
    vector<P> pts = {{N-1, N-1}, {N-2, N-1}, {N-1, N-2}};
    for(int b1 : allowed_bits){
        for(int b2=0; b2<8; b2++){
            if(nth_bit(b1, 0) ^ nth_bit(b2, 0) ^ nth_bit(b2, 1) ^ nth_bit(b2, 2)) continue;
            bool ok = true;
            for(int k=0; k<3; k++) if(mp_in.count(pts[k]) && mp_in[pts[k]] != nth_bit(b2, k)) ok = false;
            if(ok) add(ans_in, dp[N-2][b1]);
        }
    }

    int64_t ans = ans_in * ans_out % MOD;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 28416
if __name__ == "__main__":
    N, M = [int(i) for i in input().split()]
    dic = {}
    result = 0
    for i in range(N):
        favs = [int(i) for i in input().split()][1:]
        for food in favs:
            num = dic.get(food, 0)
            num += 1
            dic[food] = num
            if num == N:
                result += 1
    print(result)


Measured memory_bytes: 3060
#include <cmath>
#include <cassert>
#include <iostream>
#include <iomanip>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

#define forsn(i,s,n) for (int i = (s);i < (int)(n);i++)
#define forn(i,n) forsn(i,0,n)
#define dforsn(i,s,n) for (int i = (n-1);i >= (int)(s);i--)
#define dforn(i,n) dforsn(i,0,n)
#define all(v) (v).begin(), (v).end()

int f[128][16];
int p[128][16];

bool biton(int mask, int pos) {
	return (mask & (1 << pos)) != 0;
}

bool broken(int mask) {
	forn(j, 5) if (!biton(mask, 2 * j) && !biton(mask, 2 * j + 1)) return true;
	return false;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n; cin >> n;
	forn(i,n) forn(per,10) cin >> f[i][per];
	forn(i,n) forn(j,11) cin >> p[i][j];
	

	int best = -1e9;
	forn(i, 1 << 10) {
		if (!i) continue;
		
		int value = 0;
		forn(j, n) {
			int c = 0;
			forn(k, 10) {
				c += (f[j][k] && biton(i, k));
			}
			value += p[j][c];
		}
		best = max(best,value);
	}
	cout << best << endl;
}



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

int main()
{
  ll n,d,count=0;
  cin >> n >> d;
  
  for (ll i=0; i<n; i++) {
    ll x,y;
    cin >> x >> y;
    double dis = sqrt(x*x + y*y);
    if (dis <= d) {
      count++;
    }
  }

  cout << count;
  return 0;
}

Measured memory_bytes: 3192
n,m = map(int,input().split())
ls = []
switch = [(i+1) for i in range(n)]
ls = [list(map(int,input().split())) for i in range(m)]
p = list(map(int,input().split()))

pattern = [bin(i)[2:].zfill(n) for i in range(2**n)]

ans = 0

for i in pattern:
    turn = []
    on = 0
    for j in range(n):
        if i[j] == '1':
            turn.append(switch[j])
    for k in range(m):
        count = 0
        for l in range(1,ls[k][0]+1):
            if ls[k][l] in turn:
                count += 1
        if count % 2 == p[k]:
            on += 1
    if on == m:
        ans += 1
            
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> sol1;
vector<int> sol2;
void dfs(int indx1,int indx2,vector<vector<int> > *g,vector<bool> *bio){
	//cout<<indx1+1<<" "<<indx2+1<<endl;
	if(indx1== -1 && indx2== -1) return;
	if(indx1>-1){
		(*bio)[indx1]=true;
	}
	if(indx2>-1){
		(*bio)[indx2]=true;
	}
	int nindx1=-1;
	int nindx2=-1;
	if(indx1 != -1){
	
		for(int i=0;i<(*g)[indx1].size();i++){
			if((*bio)[(*g)[indx1][i]]) continue;
			nindx1=(*g)[indx1][i];
		}
		sol1.push_back(indx1);
		(*bio)[indx1]=true;
	}
	if(indx2 != -1){
	
		for(int i=0;i<(*g)[indx2].size();i++){
			if((*bio)[(*g)[indx2][i]]  || (*g)[indx2][i]==nindx1) continue;
			nindx2=(*g)[indx2][i];
		}
		sol2.push_back(indx2);
		(*bio)[indx2]=true;
	}
	dfs(nindx1,nindx2,g,bio);
}
int main(){
	int n,m;
	cin>>n>>m;
	vector<vector<int> > graf(n);
	for(int i=0;i<m;i++){
		int a,b;
		cin>>a>>b;
		a--;
		b--;
		graf[a].push_back(b);
		graf[b].push_back(a);
	}
	vector<bool> bio(n,false);
	bio[0]=true;
	bio[graf[0][0]]=true;
	dfs(0,graf[0][0],&graf,&bio);
	reverse(sol1.begin(),sol1.end());
	//reverse(sol2.begin(),sol2.end());
	cout<<sol1.size()+sol2.size()<<endl;
	for(int i=0;i<sol1.size();i++) cout<<sol1[i]+1<<" ";
	for(int i=0;i<sol2.size();i++) cout<<sol2[i]+1<<" ";
}

Measured memory_bytes: 12092
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int k = sc.nextInt();
		String s = sc.next();
		
		// 計算
		long result = 0;
		int MOD = 1000000007;
		int n = s.length();
		Combination comb = new Combination(k+n);
		for(int i = 0; i <= k; i++){
		    result += pow(25, i, MOD)*comb.combination(i+n-1, n-1)%MOD*pow(26, k-i, MOD)%MOD;
		    result %= MOD;
		}
		
		// 出力
		System.out.println(result);
	}
	
	public static long pow(long a, long n, long MOD) {
		long res=1;
		while (n>0) {
			if ((n-n/2*2)==1) {
				res=(res*a)%MOD;
			}
			a=(a*a)%MOD;
			n>>=1;
		}
		return res%MOD;
	}
	
	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}

class Combination {
	static final int MOD = 1000000007;
	long[] fact;
	long[] invFact;
	long[] inv;
	
	public Combination (int n) {
		fact = new long[n+1];
		invFact = new long[n+1];
		inv = new long[n+1];
		fact[0] = 1;
		fact[1] = 1;
		invFact[0] = 1;
		invFact[1] = 1;
		inv[1] = 1;
		for (int i = 2; i < n+1; i++) {
			fact[i] = fact[i - 1] * i % MOD;
			inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
			invFact[i] = invFact[i - 1] * inv[i] % MOD;
		}
	}
	
	public long combination(int n, int k) {
		if (n < k || n < 0 || k < 0) {
			return 0;
		}
		return fact[n] * (invFact[k] * invFact[n - k] % MOD) % MOD;
	}
}


Measured memory_bytes: 76996
/*
    if you can't see the repay
    Why not just work step by step
    rubbish is relaxed
    to ljq
*/
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#include <cmath>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#include <vector>
#include <stdlib.h>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod =  (int)1e9+7;
const int MAX_N = 100025;
int eid,p[MAX_N];
ll dp[MAX_N][2];
struct edge
{
    int v,next;
}e[MAX_N<<2];
void init()
{
    memset(p,-1,sizeof(p));
    eid = 0;
}
void add(int u,int v)
{
    e[eid].v = v;
    e[eid].next =p[u];
    p[u] = eid++;
}
void dfs(int u,int fa)
{
    ll x = 1, y = 1;
    if(e[p[u]].next==-1&&e[p[u]].v == fa)
    {
        dp[u][0] = dp[u][1] = 1;
        return ;
    }
    for(int i = p[u];i+1;i=e[i].next)
    {
        int v = e[i].v;
        if(v==fa) continue;
        dfs(v,u);
        x = (x*((dp[v][0] + dp[v][1])%mod))%mod;
        y = (y*(dp[v][0]))%mod;
    }
    dp[u][0] = x,dp[u][1] = y;
}
int main()
{
    //ios::sync_with_stdio(false);
    //freopen("a.txt","r",stdin);
    //freopen("b.txt","w",stdout);
    int n,a,b;
    init();
    scanf("%d",&n);
    for(int i = 1;i<n;++i)
    {
        scanf("%d%d",&a,&b);
        add(a,b);
        add(b,a);
    }
    dfs(1,0);
    printf("%d\n",(dp[1][0]+dp[1][1])%mod);
    //fclose(stdin);
    //fclose(stdout);
    //cout << "time: " << (long long)clock() * 1000 / CLOCKS_PER_SEC << " ms" << endl;
    return 0;
}



Measured memory_bytes: 15636
#include "bits/stdc++.h"
using namespace std;
#ifndef LOCAL
#define endl '\n'
#endif

#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define pf push_front
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)x.size()
#define lb lower_bound
#define ub upper_bound

typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int pct(int x) { return __builtin_popcount(x); }
int pct(ll x) { return __builtin_popcountll(x); }
int bt(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))
int bt(ll x) { return 63 - __builtin_clzll(x); } // floor(log2(x))
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
ll cdiv(ll a, ll b) { return a / b + !(a < 0 || a % b == 0); }
int nxt_C(int x) { int c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }
ll nxt_C(ll x) { ll c = x & -x, r = x + c; return (((r ^ x) >> 2) / c) | r; }

vector<int> get_bits(int mask) {
	vector<int> bb;
	while(mask) { int b = bt(mask); bb.pb(b); mask ^= (1 << b); }
	reverse(all(bb));
	return bb;
}

int get_mask(vector<int> v) {
	int mask = 0;
	for(int x : v) { mask ^= (1 << x); }
	return mask;
}

template<typename T>
void uniq(vector<T> &v) { sort(all(v)); v.resize(unique(all(v)) - v.begin()); }

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ll rand(ll l, ll r){
	uniform_int_distribution<ll> uid(l, r);
	return uid(rng);
}

void sc() {}

template <typename Head, typename... Tail>
void sc(Head &H, Tail &... T) { cin >> H; sc(T...); }

#ifdef LOCAL
#define debug(...) cerr << "[L:" << __LINE__ << "][" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif

// #ifndef LOCAL
// string to_string(__int128 x) {
// 	string s = "";
// 	bool neg = 0;
// 	if(x < 0) { s += "-"; neg = 1; x = -x; }
// 	if(!x) s += '0';
// 	while(x) {
// 		int rem = x % 10;
// 		s += to_string(rem);
// 		x /= 10;
// 	}
// 	reverse(s.begin() + neg, s.end());
// 	return s;
// }
// #endif

const int mod = 1e9 + 7; // 998244353;

int pwr(int a,ll b) {
	int ans = 1;
	while(b) {
		if(b & 1) ans = (ans * 1LL * a) % mod;
		a = (a * 1LL * a) % mod;
		b >>= 1;
	}
	return ans;
}

/*
	Lookout for overflows!!
	Check array sizes!!
	Clear before test cases!!
	Use the correct modulo!!
	Check for corner cases!!
	Are you forgetting something?!
	Read problem statement carefully!!!
*/

const int N = 1e5 + 5;
vector<int> g[N];

int go(int u) {
    vector<int> z;
    for(int v : g[u]) {
        z.pb(go(v));
    }
    sort(all(z));
    reverse(all(z));
    int ans = 0;
    fr(i, 0, sz(z) - 1) {
        ans = max(ans, z[i] + i + 1);
    }
    return ans;
}

void solve() {
	int n;
    sc(n);
    fr(i, 2, n) {
        int p;
        sc(p);
        g[p].pb(i);
    }
    cout << go(1);
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	// cin >> t;
	for(int tt = 1; tt <= t; tt++) {
		solve();
	}
	return 0;
}

Measured memory_bytes: 16736
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
using namespace std;
 
#define REP(i,n) for(int i=0; i<n; ++i)
#define FOR(i,a,b) for(int i=a; i<=b; ++i)
#define FORR(i,a,b) for (int i=a; i>=b; --i)
#define pi M_PI
 
typedef long long ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef vector<VI> VVI;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

int main() {
    int t, n;
    int dx[] = {1,-1,0,0,1,-1}, dy[] = {0,0,1,-1,1,-1};
    while (cin >> t >> n && (t != 0 || n != 0)){
        map<P, int> w;
        while(n--){
            int x, y;
            cin >> x >> y;
            w[make_pair(x, y)] = 1;
        }
        int sx, sy;
        cin >> sx >> sy;
        map<P, int> dist; 
        queue<P> que;
        que.push(make_pair(sx, sy));
        dist[make_pair(sx, sy)] = 1;
        int ans = 0;
        while(!que.empty()){
            P p = que.front();
            que.pop();
            int i = p.first, j = p.second;
            ans++;
            if (dist[make_pair(i, j)] == t+1) continue;
            REP(k,6){
                int ii = i+dx[k], jj = j+dy[k];
                if (w[make_pair(ii, jj)] || dist[make_pair(ii, jj)] > 0) continue;
                dist[make_pair(ii, jj)] = dist[make_pair(i, j)] + 1;
                que.push(make_pair(ii, jj));
            }
        }
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 3436
#include<iostream>
#include<vector>
#include<string>
#include<set>
#include<algorithm>
using namespace std;
int main()
{
	string str;
	int n;
	cin >> n >> str;
	set<char> iset;
	int Max =0;
	int cnt;
	for (int i = 1; i < n; i++)
	{
		string temp = str;
		string substr1 = temp.assign(str.begin(), str.begin() + i);
		string substr2 = temp.assign(str.begin() + i, str.end());
		for (char c : substr1)
		{
			iset.insert(c);
		}
		cnt = 0;
		for (auto c : iset)
		{
			if (count(substr2.begin(),substr2.end(),c)!=0)
			{
				cnt++;
			}
		}
		Max = max(cnt, Max);
	}
	cout << Max << endl;
	return 0;
}

Measured memory_bytes: 256
n,k=map(int,input().split())
s=input()
j=1
cnt=1
while j<n:
    j*=2
    cnt+=1
if k>=cnt:print(min(s)*n)
else:
    if k==1:
        minstr=s+s[::-1]
    for i in range(k-1):
        s=s+s[::-1]
        minstr=s[:n]
        for j in range(n+1):
            if s[j:j+n]<minstr:
                minstr=s[j:j+n]
        s=minstr[::-1]
    if k>=2:
        minstr=minstr[::-1]+minstr
    ans=minstr[:n]
    for i in range(n+1):
        if ans > minstr[i:i+n]:
            ans=minstr[i:i+n]
    print(ans)

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vector<int>> mi;
typedef vector<vector<pair<int, int>>> w_graph;
typedef vector<vector<int>> uw_graph;




int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef DEBUG
	freopen("out.txt", "w", stdout);
#endif
	  
   int n, k;
   cin >> n >> k;
   vi a(n);
   for (int i = 0; i < n; i++) cin >> a[i];
   bool dp[(int)1e5 + 5];
   dp[0] = false;
   
   for (int i = 1; i <= k; i++){
   	  bool ft = true;
   	  for (int j = 0; j < n; j++){
  	  	  if (i >= a[j])
	  	  	 ft &= dp[i - a[j]];
   	  }
   	  dp[i] = !ft;
   }

   cout << (dp[k] ? "First" : "Second") << endl;

   return 0;
}


Measured memory_bytes: 384
#pragma GCC optimize ("O3")

#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include <prettyprint.hpp>
#define debug(...)  cerr << "[" << #__VA_ARGS__ << "]: ", d_err(__VA_ARGS__);
#else
#define debug(...) 83;
#endif

void d_err() {
    cerr << endl;
}

template <typename H, typename... T>
void d_err(H h, T... t) {
    cerr << h << " ";
    d_err(t...);
}

template <typename T>
void print(T x) {
    cout << x << endl;
}

#define ALL(x) (x).begin(), (x).end()
#define FOR(i, m, n) for (int i = (m); i < (n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define bcnt __builtin_popcountll

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<ll,ll> Pll;
typedef pair<int,int> Pin;

ll INF = 1e16;
int inf = 1e9;
ll MOD = 1e9+7;

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

ostream& operator << (ostream& os, const mint a) {
    os << a.x;

    return os;
}

const int NMAX = int(1e7);
ll fact[NMAX+1], finv[NMAX+1], inv[NMAX+1];

void comb_init(int N) {
    // init
    REP(i, 2) {
        fact[i] = 1;
        finv[i] = 1;
        inv[i] = 1;
    }

    FOR(i, 2, N+1) {
        fact[i] = fact[i-1] * i % MOD;
        inv[i] = MOD - MOD / i * inv[MOD % i] % MOD;
        finv[i] = finv[i-1] * inv[i] % MOD;
    }
}

mint comb(int n, int k) {
    if (n < k || n < 0 || k < 0) return 0;

    return mint(fact[n]) * finv[k] * finv[n-k];
}

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    
    int x, y;
    cin >> x >> y;

    comb_init(NMAX);

    mint ans = 0;

    REP(i, max(x, y) + 1) {
        if (i <= x && x <= 2 * i && i <= y && y <= 2 * i && x + y == 3 * i) {
            ans += comb(i, x - i);
        }
    }

    print(ans);
    
}


Measured memory_bytes: 237988
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;

int main()
{
    int a , b , c ,d; cin >> a >> b >> c >> d;
    int res1 = a / d + (a % d != 0);
    int res2 = c / b + (c % b != 0);
    if (res1 >= res2) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <stdio.h>
using namespace std;
#define int long long
int MOD = 1000000007;
vector<vector<int> > ed;
vector<vector<int> > w;
vector<int > V;
vector<int> X(16, 0);
vector<int> dp(1 << 16, -1);
int dfs(int a, int p) {
	int x = 0;
	for (int i = 0; i < ed[a].size(); i++) {
		if (ed[a][i] != p) {
			//cerr << "a" << endl;
			dfs(ed[a][i], a);
			X[V[ed[a][i]] ^ w[a][i]]++;
			x ^= w[a][i];
		}
	}
	V[a] = x;
	return V[a];
}
int rec(int a) {
	if (dp[a] != -1) {
		return dp[a];
	}
	vector<int> T;
	int b = a;
	for (int i = 0; i < 16; i++) {
		if (b % 2 == 1) {
			T.push_back(i);
		}
		b /= 2;
	}
	dp[a] = 1000000000;
	int aa = 0;
	int p;
	for (int i = 0; i < (int)T.size() - 1; i++) {
		for (int j = i + 1; j < (int)T.size(); j++) {
			aa = a ^ ((1 << T[i]) | (1 << T[j]));
			p = 1;
			if ((a & (1 << (T[i] ^ T[j]))) != 0) {
				p = 2;
			}
			dp[a] = min(dp[a], p + rec((a ^ ((1 << T[i]) | (1 << T[j]))) ^ (1 << (T[i]^T[j]))));
		}
	}
	for (int i = 0; i < (int)T.size(); i++) {
		dp[a] = min(dp[a], 1 + rec(a ^ (1 << T[i])));
	}
	return dp[a];
}
signed main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int N;
	cin >> N;
	ed.resize(N);
	w.resize(N);
	V.resize(N, 0);
	int a, b, c;
	for (int i = 0; i < N - 1; i++) {
		cin >> a >> b >> c;
		ed[a].push_back(b);
		w[a].push_back(c);
		ed[b].push_back(a);
		w[b].push_back(c);
	}
	dfs(0, -1);
	int s = 0;
	int res = 0;
	for (int i = 1; i < 16; i++) {
		//cerr << X[i] << endl;
		res += X[i] / 2;
		X[i] = X[i] % 2;
		s += (1 << i)*X[i];
	}
	//cerr << s << endl;
	dp[0] = 0;
	rec(s);
	//rec((1 << 16) - 1);
	cout << res + dp[s] << endl;
}

Measured memory_bytes: 18432
#include<bits/stdc++.h>
typedef long long ll;
#define REP(i,a,b) for(int i=a;i<b;i++)
#define IN(n) int n; cin>>n;
#define ARR(arr,i,n) int arr[n]; REP(i,0,n){cin>>arr[i];}
#define MOD 1000000007

using namespace std;

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

    // code comes here

    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i];
    }
    int countt=0;
    for(int i=1;i<n-1;i++){
        if((arr[i+1]>arr[i] && arr[i-1]<arr[i]) || (arr[i+1]<arr[i] && arr[i-1]>arr[i])){
            countt++;
        }
    }
    cout<<countt<<"\n";
    return 0;
}






Measured memory_bytes: 256
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF = 0x3f3f3f3f;
const ll mod  = 1e9 + 7;
const ll N = 2e5 + 5;

int n,a[N];
ll ans;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=2;i<=n;i++){
    	if(a[i]<a[i-1]) ans+=a[i-1]-a[i],a[i]=a[i-1];
    }
    cout<<ans;
    return 0;
}

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

int dp[14][1<<14];
int INF = 1000000000;
int n;

bool contained(string a, string b){
  if(a.length() > b.length()) return false;
  for(int i = 0; i <= b.length()-a.length(); ++i){
    bool f = true;
    for(int j = 0; j < a.length(); ++j){
      if(a[j] != b[i+j]){
        f = false;
        break;
      }
    }
    if(f) return true;
  }
  return false;
}

int match(string a, string b){
  int ret = 0;
  for(int i = 1; i < a.length(); ++i){
    bool f = true;
    for(int j = 0; j < i; ++j){
      if(b[b.length()-i+j] != a[j]){
        f = false;
        break;
      }
    }
    if(f) ret = max(ret,i);
  }
  //cout << a << " " << b << " " << ret << endl;
  return ret;
}

int memo_dp(int i, int bit, vector<string> &names){
  if(dp[i][bit] < INF){
    return dp[i][bit];
  }
  int bit_ = bit - (1<<i);
  for(int j = 0; j < n; ++j){
    if((bit_>>j)&1){
      dp[i][bit] = min(dp[i][bit],memo_dp(j,bit_,names)+(int)names[i].length()-match(names[i],names[j]));
    }
  }
  //cout << i << " " << bit << " " << dp[i][bit] << endl;
  return dp[i][bit];
}

int main(){
  while(cin >> n, n){
    vector<string> cities(n);
   
    for(int i = 0; i < n; ++i){
      cin >> cities[i];
    }

    vector<string> names;
    for(int i = 0; i < n; ++i){
      bool f = true;
      for(int j = 0; j < n; ++j){
        if(i == j) continue;
        if(contained(cities[i],cities[j])){
          f = false;
          break;
        }
      }
      if(f) names.push_back(cities[i]);
    }

    n = names.size();
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < (1<<n); ++j) dp[i][j] = INF;
    }

    for(int i = 0; i < n; ++i)
      dp[i][(1<<i)] = (int)names[i].length();
    
    int ans = INF;
    for(int i = 0; i < n; ++i){
      ans = min(memo_dp(i, (1<<n)-1, names), ans);
    }
    cout << ans << endl;
  }
  return 0;
}

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

using ll = long long;

const int MAXN = 3e5;
const int MAXM = 3e5;
int N, M;
int A[MAXN];

ll s1[MAXN];
ll s2[MAXN];

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> A[i]; A[i]--;
	}

	ll tot = 0;
	for (int i = 0; i < N-1; i++) {
		int cur = A[i];
		int nxt = A[i+1];
		if (cur > nxt) nxt += M;
		tot += nxt - cur;

		s1[cur+1] ++;
		s1[nxt+1] --;
		s2[cur+1] += cur;
		s2[nxt+1] -= cur;
	}
	for (int i = 1; i < 2*M; i++) {
		s1[i] += s1[i-1];
		s2[i] += s2[i-1];
	}

	ll ans = tot;
	for (int i = 0; i < M; i++) {
		ll cost = tot;
		cost -= (i-1) * s1[i] - s2[i];
		cost -= (i+M-1) * s1[i+M] - s2[i+M];
		ans = min(ans, cost);
	}
	cout << ans << '\n';

	return 0;
}


Measured memory_bytes: 4224
#include<stdio.h>
#define N 1000000
int main()
{
  int n,i,j,k,v,cnt=0,m=0,A[N],G[N];


  scanf("%d",&n);
   
  for(i = 0;i < n;i++)
    scanf("%d",&A[i]);
   
  G[0]=1;
  for(i = 1;G[i-1] <= n;i++)
  {
    m++;
    G[i]=G[i-1]*3+1;
    if(m>100)break;
  }

  for(i = m-1;i >= 0;i--)
  {
    for(j = G[i];j < n;j++)
    {
      v = A[j];
      k = j - G[i];
      while(k >= 0 && A[k] > v)
      {
        A[k+G[i]] = A[k];
        k -= G[i];
        cnt++;
      }
      A[k+G[i]] = v;
    }
  }
   
  printf("%d\n",m);
  for(i = m - 1;i > 0 ;i--)
    printf("%d ",G[i]);

  printf("%d\n%d\n",G[i],cnt);

  for(i = 0;i < n;i++)
    printf("%d\n",A[i]);

  return 0;
}
   


Measured memory_bytes: 5628
import scala.io.StdIn.{readLine,readInt}
import scala.collection.mutable.ArrayBuffer

case class Dice(var d:Array[String]) {
  private val s = Array(4,0,2,3,5,1)
  private val w = Array(2,1,5,0,4,3)
  private val h = Array(0,2,4,1,3,5)
  private val all = Array.ofDim[Array[String]](24)

  def rotateAll() = {
    all(0) = d
    all(1) = s.map(d)
    all(2) = s.map(all(1))
    all(3) = s.map(all(2))
    all(4) = w.map(d)
    all(5) = w.map(w).map(all(4))
    (0 to 17).foreach { s => all(s+6) = h.map(all(s)) }
  }

  def getAll = all

  override def toString() = d(0)
}

object Main extends App {
  val faces = readLine.split(" ")
  val n = readInt
  val dice = Dice(faces)

  dice.rotateAll()
  (0 until n).foreach { s =>
    val l =  readLine.split(" ")
    println(dice.getAll.find(t => t(0) == l(0) && t(1) == l(1)).get(2))
  }
}

Measured memory_bytes: 44180
#include<bits/stdc++.h>
#include<iomanip>
using namespace std;
typedef long long ll;
typedef long  l;
typedef pair<ll,ll> P;
#define rep(i,n) for(int i=0;i<n;i++)
#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()
const double PI=3.141592653589;
const int INF=1000000007;
const ll LMAX=1000000000000001;
int gcd(int a,int b){if(a<b)swap(a,b);int c=a%b;while(c!=0){a=b;b=c;c=a%b;}return b;}
ll lcm(ll a,ll b){return a*b/gcd(a,b);}
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};

int main(){
  int k, a, b; cin >> k >> a >> b;
  for(int i = a; i <= b; i++){
    if(i % k == 0){
      puts("OK");
      return 0;
    }
  }
  puts("NG");

  return 0;
}


Measured memory_bytes: 3620
#include <iostream>
#include <fstream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <ctime>
#include <cstring>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <list>
#include <stack>
#include <bitset>
#include <algorithm>
#include <iomanip>

using namespace std;

#define forn(i,n) for (int i = 0; i < int(n); i++)
#define ford(i,n) for (int i = int(n) - 1; i >= 0; i--)
#define fore(i,l,r) for (int i = int(l); i <= int(r); i++)
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define mp make_pair
#define pb push_back
#define ft first
#define sc second
#define x first
#define y second

template<typename X> inline X abs(const X& a) { return a < 0 ? -a : a; }
template<typename X> inline X sqr(const X& a) { return a * a; }

typedef long long li;
typedef long double ld;
typedef pair<int, int> pt;

const int INF = int(1e9);
const li INF64 = li(1e18);
const ld EPS = 1e-9;
const ld PI = acosl(ld(-1));

string s;

inline bool read()
{
	if (!getline(cin, s))
		return false;
	
	return true;
}

inline void solve()
{
	forn (i, 4)
		cout << s[i];
	cout << ' ';
	fore (i, 4, 11)
		cout << s[i];
	cout << endl;
}

int main()
{
#ifdef SU2_PROJ
	assert(freopen("input.txt", "r", stdin));
	assert(freopen("output.txt", "w", stdout));
#endif

	cout << setprecision(25) << fixed;
	cerr << setprecision(10) << fixed;

	srand(int(time(NULL)));

	assert(read());
	solve();

#ifdef SU2_PROJ
	cerr << "TIME: " << clock() << endl;
#endif

	return 0;
}


Measured memory_bytes: 256
'''
参考
https://drken1215.hatenablog.com/entry/2019/06/29/224100
dをソートし、d[N//2]-d[N//2-1]が解
'''
n = int(input())
d = list(map(int, input().split()))
d.sort()

print(d[n//2]-d[n//2-1])


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

bool EncountQ(int q[8][8],int r,int c){
    rep(i,8){
        if(q[r][i]==-1&&(i!=c)){
            return true;
        }
        if(q[i][c]==-1&&(i!=r)){
            return true;
        }
        if(q[r-i][c+i]==-1&&(r-i)>=0&&(c+i)<=7&&(i!=0)){
            return true;
        }
        if(q[r+i][c-i]==-1&&(r+i)<=7&&(c-i)>=0&&(i!=0)){
            return true;
        }
        if(q[r+i][c+i]==-1&&(r+i)<=7&&(c+i)<=7&&(i!=0)){
            return true;
        }
        if(q[r-i][c-i]==-1&&(r-i)>=0&&(c-i)>=0&&(i!=0)){
            return true;
        }
    }
    return false;
}

int main() {
    int k;
    cin>>k;
    int r[8],c[8];
    rep(i,k){
        cin>>r[i]>>c[i];
    }

    int prm[8]={0,1,2,3,4,5,6,7};

    do{
        int q[8][8]={};
        rep(i,8){
            q[i][prm[i]]=-1;
        }
        int countk=0;
        rep(i,k){
            rep(j,8){
                if(r[i]==j&&c[i]==prm[j]){
                    countk++;
                }
            }
        }
        if(countk==k){
            int count=0;
            rep(i,8){
                bool flg=EncountQ(q,i,prm[i]);
                if(flg==false){
                    count++;
                }else{
                    break;
                }
            }
            if(count==8){
                rep(i,8){
                    rep(j,prm[i]){
                        cout<<".";
                    }
                    cout<<"Q";
                    rep(j,7-prm[i]){
                        cout<<".";
                    }
                    cout<<endl;
                }
            }        
        }
    }while(next_permutation(prm,prm+8));
    return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;
typedef long long ll;
const ll mod=1000000007;

int main(){
    string S;
    cin>>S;
    int N=S.size();
    vector<int> s;
    for(int i=0;i<N;i++){
        if(S.at(i)=='R') s.push_back(1);
        else s.push_back(-1);
    }

    //cout<<s.size()<<endl;
    vector<int> ans(N);
    int memory=1;
    int num=0;
    for(int i=0;i<N;i++){
        if(s.at(i)==memory) num++;
        else{
            //cout<<num<<endl;
            if(memory==1){
                ans.at(i-1)+=(num+1)/2;
                ans.at(i)+=num/2;
            }

            else{
                ans.at(i-num-1)+=num/2;
                ans.at(i-num)+=(num+1)/2;
            }
            //for(int i=0;i<N;i++) cout<<ans.at(i)<<' ';
            //cout<<endl;

            num=1;
            memory*=(-1);
        }
    }

    ans.at(N-1-num)+=num/2;
    ans.at(N-num)+=(num+1)/2;

    for(int i=0;i<N;i++) cout<<ans.at(i)<<' ';
    cout<<endl;

    
}

Measured memory_bytes: 1528
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <cfloat>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <fstream>
#include <functional>
#include <bitset>
#define chmin(a, b) ((a)=min((a), (b)))
#define chmax(a, b) ((a)=max((a), (b)))
#define fs first
#define sc second
#define eb emplace_back
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
typedef tuple<int, int, int> T;

const ll MOD=1e9+7;
const ll INF=1e18;
const double pi=acos(-1);
const double eps=1e-10;

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

int main(){
    int n; cin>>n;
    vector<int> d(n);
    vector<int> cnt(13, 0);
    for(int i=0; i<n; i++){
        cin>>d[i];
        cnt[d[i]]++;
    }

    bool valid = true;
    vector<int> v2, v1;
    for(int i=0; i<13; i++){
        if(3 <= cnt[i]) valid = false;
        else if(cnt[i] == 2){
            v2.push_back(i);
            v2.push_back(24 - i);
        }
        else if(cnt[i] == 1){
            v1.push_back(i);
        }
    }

    if(!valid){
        cout << 0 << endl;
        return 0;
    }

    int ans = 0;
    for(int bit=0; bit<(1<<v1.size()); bit++){
        set<int> st;
        for(auto i:v2){
            st.insert(i);
        }

        for(int i=0; i<v1.size(); i++){
            if(i & bit){
                st.insert(24 - v1[i]);
            }
            else{
                st.insert(v1[i]);
            }
        }

        int pre = 0;
        int maxgap = 100;
        for(auto i:st){
            maxgap = min(maxgap, i - pre);
            pre = i;
        }

        ans = max(ans, maxgap);
    }

    cout << ans << endl;
}

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

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


Measured memory_bytes: 3096
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

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

    int a[n+n+n] = {};
    cout << "? ";
    srep(i, 1, n+1){
        cout << i;
        if(i == n){
            cout << endl;
        }else{
            cout << ' ';
        }
    }

    fflush(stdout);

    string s; cin >> s;
    int flag = 0;
    if(s[0] == 'B'){
        flag = 1;
    }

    int l = 1;
    int r = n + 1;

    while(r - l > 1){
        int m = (l + r) / 2;
        cout << "? ";
        srep(i, m, m+n){
            int ii = i;
            if(ii > 2*n)ii -= 2*n;
            cout << ii;
            if(i == m+n-1){
                cout << endl;
            }else{
                cout << ' ';
            }
        }
        fflush(stdout);
        cin >> s;
        if(flag == 0){
            if(s[0] == 'R'){
                l = m;
            }else{
                r = m;
            }
        }else{
            if(s[0] == 'R'){
                r = m;
            }else{
                l = m;
            }
        }
    }

    if(flag == 0){
        a[l] = 1;
        a[l+n] = 2;
    }else{
        a[l] = 2;
        a[l+n] = 1;
    }

    rep(i,n-1){
        cout << "? ";
        srep(j, l+1, l+n){
            int ii = j;
            if(ii > 2*n)ii -= 2*n;
            cout << ii;
            cout << ' ';
            
        }
        int ii = l + n + 1 + i;
        if(ii > 2* n)ii -= 2*n;
        cout << ii << endl;
        fflush(stdout);
        cin >> s;
        if(s[0] == 'R'){
            a[ii] = 1;
        }else{
            a[ii] = 2;
        }
    }

    rep(i,n-1){
        cout << "? ";
        srep(j, l+n+1, l+n+n){
            int ii = j;
            if(ii > 2*n)ii -= 2*n;
            cout << ii;
            cout << ' ';
            
        }
        int ii = l + 1 + i;
        if(ii > 2* n)ii -= 2*n;
        cout << ii << endl;
        fflush(stdout);
        cin >> s;
        if(s[0] == 'R'){
            a[ii] = 1;
        }else{
            a[ii] = 2;
        }
    }

    srep(i, 1, n*2+1){
        if(a[i] == 0){
            a[i] = a[i+2*n];
        }
    }

    cout << "! ";
    srep(i,1,2*n+1){
        if(a[i] == 1){
            cout << 'R';
        }else{
            cout << 'B';
        }
    }

    cout << endl;

    return 0;
}
 
 


Measured memory_bytes: 724
#include <cstdio>
#include <vector>
#include <algorithm>

int main() {

    int n, q;
    scanf("%d%d", &n, &q);

    std::vector<long long> qs;
    qs.push_back(n);

    for (int i = 0; i < q; i++) {

        long long qi;
        scanf("%lld", &qi);

        while (!qs.empty() && qs.back() >= qi)
            qs.pop_back();
        qs.push_back(qi);

    }

    std::vector<long long> ans(n+1);
    std::vector<long long> coef(qs.size());

    coef[coef.size()-1] = 1;
    for (int i = coef.size() - 1; i >= 0; i--) {
        
        long long cur = qs[i];

        while (cur > qs[0]) {
            int pos = std::upper_bound(qs.begin(), qs.begin() + i, cur) - qs.begin() - 1;
            coef[pos] += cur / qs[pos] * coef[i];
            cur %= qs[pos];
        }
        ans[cur] += coef[i];

    }

    for (int i = n - 1; i >= 1; i--)
        ans[i] += ans[i + 1];
    for (int i = 1; i <= n; i++)
        printf("%lld\n", ans[i]);

}


Measured memory_bytes: 4212
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <complex>

#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>

#include <stdexcept>

using namespace std;

// type alias
using ll = long long;
using ull = unsigned long long;
using comp = complex<double>;

const ll MOD = 1000000007LL;
const double PI = 3.14159265358979323846;

//conversion
//------------------------------------------
inline int toint(string s) { int v; istringstream sin(s); sin >> v; return v; }
template<class t> inline string tostring(t x) { ostringstream sout; sout << x; return sout.str(); }

//debug
#define DUMP(x)  cerr << #x << " = " << (x) << endl
#define DEBUG(x) cerr << #x << " = " << (x) << " (l" << __line__ << ")" << " " << __file__ << endl

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

	string N;
	cin >> N;
	N = "00" + N;
	reverse(N.begin(), N.end());

	ll no_incre_res, prev_no_incre_res = 0;
	ll incre_res, prev_incre_res = 1LL << 31;
	ll digit;
	bool increment = false;
	for (ll i = 0; i < N.size(); ++i) {
		digit = N[i] - '0';
		no_incre_res = min(prev_no_incre_res + digit, prev_incre_res + digit + 1);
		incre_res = min(prev_no_incre_res + 10 - digit, prev_incre_res + 10 - digit - 1);
		prev_no_incre_res = no_incre_res;
		prev_incre_res = incre_res;
	}

	cout << no_incre_res << endl;

	return 0;
}


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

using namespace std;

int n, a[100005];

int main(void)
{
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    sort(a + 1, a + 1 + n);
    printf("%d\n", a[n / 2 + 1] - a[n / 2]);
    return 0;
}

Measured memory_bytes: 640
k,a,b=map(int,input().split())
if b-a <= 2:
  print(k+1)
  exit()
if k-a<1:
  print(k+1)
  exit()
print(1 + (a-1) + (b-a)*((k-(a-1))//2) + (k-(a-1))%2)

Measured memory_bytes: 3064