akhauriyash/Code-Regression huggingface dataset:
// #define _GLIBCXX_DEBUG // for STL debug (optional)
#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>
using namespace std;
using ll = long long int;
using int64 = long long int;
 
template<typename T> void chmax(T &a, T b) {a = max(a, b);}
template<typename T> void chmin(T &a, T b) {a = min(a, b);}
template<typename T> void chadd(T &a, T b) {a = a + b;}
 
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
const int INF = 1001001001;
const ll LONGINF = 1001001001001001LL;
const ll MOD = 1000000007LL;

int main() {
    set<int> S;
    int N; cin >> N;
    vector<int> P(N);
    for(int i=0; i<N; i++) {
        int v; cin >> v; v--;
        P[v] = i;
    }

    ll ans = 0;
    for(int i=N-1; i>=0; i--) {
        int k = P[i];

        // i より大きいもので近いやつ
        ll ub = (S.upper_bound(k) == S.end() ? N : *S.upper_bound(k));
        ll lb = (S.upper_bound(k) == S.begin() ? -1 : *prev(S.upper_bound(k)));
        
        // ub より大きいもの
        ll tu = ub;
        ll tl = lb;
        
        ll uc = (S.upper_bound(tu) == S.end() ? N : *S.upper_bound(tu));
        ll lc = (S.lower_bound(tl) == S.begin() ? -1 : *prev(S.lower_bound(tl)));
        
        // fprintf(stderr, "# lb = %lld, ub = %lld\n", lb, ub);
        // fprintf(stderr, "# lc = %lld, uc = %lld\n", lc, uc);
        
        ll L = k - (lb < 0 ? lb : lb - 1), R = (ub >= N ? ub : ub + 1) - k;
        ll X = max(1LL, lb - lc), Y = max(1LL, uc - ub);

        // どっちか満たしてれば 2 番目になるかも
        if(lb != -1 or ub != N) {
            // lb 側を含む
            if(lb != -1) {
                ll a1 = X * (ub == N ? R : R - 1);
                ans += a1 * (i + 1);
                // fprintf(stderr, "add 1: %lld\n", a1);
            }
            // ub 側を含む
            if(ub != N) {
                ll a2 = Y * (lb == -1 ? L : L - 1);
                ans += a2 * (i + 1);
                // fprintf(stderr, "add 2: %lld\n", a2);
            }
        }
        // fprintf(stderr, "i = %lld: L = %lld, R = %lld, X = %lld, Y = %lld\n", i+1, L, R, X, Y);
        S.insert(k);
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 5376
#define _USE_MATH_DEFINES

#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <bitset>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tl3;



const int BIG_NUM = 1e9;
const ll INF = 1000000000000000000;
const ll MOD = 1e9 + 7;
//const ll MOD = 998244353;



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

	k--;
	s[k] = 'a' + (s[k] - 'A');

	cout << s << endl;

}


Measured memory_bytes: 3556
#include<stdio.h>
#define size 100
#define length 1000

int A[size];
int stacksize=0;

int main()
{
        char B[length];

        scanf("%[^\n]*s", B);
        printf("%d\n",calc(B));
        return 0;
}


int pop(){
  if(stacksize <= 0)
  return 0;
  return A[--stacksize];
}

int push(int a){
  A[stacksize++]=a;
}

int d(char *w){
  if(*w == '+' || *w == '-'){
    w++;
    if(*w >= '0' && *w <= '9')
    return 1;
    return 0;
  }
  if (*w >= '0' && *w <= '9') return 1;
       return 0;
}

int number(char *w){

  int s=0,n=0;
  if(*w == '+'){
    w++;
  } else if (*w == '-') {
                s = 1;
                w++;
        }
        while (*w >= '0' && *w <= '9') {
                n = n * 10 + (*w - '0');
                w++;
        }
        if (s) return -n;
        return n;
}

int calc(char *w){
  int l, m, n;
  while (*w) {
    if (d(w)) {
        n = number(w);
        push(n);
  while (*w == '-' || *w == '+') {
        w++;
}
  while (n) {
    n /= 10;
    w++;
  }
} else {
  switch (*w) {
    case '+': l = pop();
              m = pop();
    push(m+l);
    break;
    case '-': l = pop();
              m = pop();
    push(m-l);
    break;
    case '*': l = pop();
              m = pop();
    push(m*l);
    break;
    case '/': l = pop();
              m = pop();
    if (l == 0) break;
    push(m/l);
    break;
    case '%': l = pop();
              m = pop();
    if (l == 0) break;
    push(m%l);
  }
    w++;
  }
}
  return pop();
}



Measured memory_bytes: 2108
#include <bits/stdc++.h>
#include <random>
using namespace std;
#define M 1000000007
#define pb emplace_back
#define F first
#define S second
#define PI acosl(-1.0)
#define mp(a, b) make_pair(a, b)
#define eps 1e-9
#define all(vec) vec.begin(), vec.end()
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define int long long
template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}
const int N = 2e5 + 10;
const int INF = 1LL << 60;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int RANDOM_GEN = uniform_int_distribution<int>(0, 10000)(rng);
int t = 1;


void solve()
{
	int s, w;
	cin>>s>>w;
	if(w >= s) cout << "unsafe" << '\n';
	else cout << "safe" << '\n';
}


signed main()
{
    FAST
    int Tests = 1;
    //cin>>Tests;
    while(Tests--)
    {
		//cout<<"Case #"<<(t++)<<": ";  
        solve();
    }
    return 0;
}


Measured memory_bytes: 3656
#include<iostream>
#include<iomanip>
#include<math.h>
#include<algorithm>
#include<utility>
#include<functional>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int, int> P;
LL a,b,c,d;
int main(){
    cin>>a;
    cout<<(a+1)*a/2;

        
    return 0;
}


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

int main() {
	int h, w;
	cin >> h >> w;
	vector<vector<int>>grid(h+2, vector<int>(w+2,0));
	queue<pair<int, int>>black;
	for (int i = 1; i < h + 1; i++) {
		for (int j = 1; j < w + 1; j++) {
			char x;
			cin >> x;
			if (x == '.')grid.at(i).at(j) = 1e9;
			else black.push({ i, j });
		}
	}
	while (black.size() >= 1) {
		int x = black.front().first;
		int y = black.front().second;
		if (grid.at(x - 1).at(y) > grid.at(x).at(y) + 1) {
			grid.at(x - 1).at(y) = grid.at(x).at(y) + 1;
			black.push({ x - 1,y });
		}
		if (grid.at(x + 1).at(y) > grid.at(x).at(y) + 1) {
			grid.at(x + 1).at(y) = grid.at(x).at(y) + 1;
			black.push({ x + 1,y });
		}
		if (grid.at(x).at(y - 1) > grid.at(x).at(y) + 1) {
			grid.at(x).at(y - 1) = grid.at(x).at(y) + 1;
			black.push({ x,y - 1 });
		}
		if (grid.at(x).at(y + 1) > grid.at(x).at(y) + 1) {
			grid.at(x).at(y + 1) = grid.at(x).at(y) + 1;
			black.push({ x,y + 1 });
		}
		black.pop();
	}
	int ans = 0;
	for (int i = 1; i < h + 1; i++) {
		for (int j = 1; j < w + 1; j++) {
			ans = max(ans, grid.at(i).at(j));
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 12432
#define _CRT_SECURE_NO_WARNINGS
#include<bits/stdc++.h>
#include<vector>
using namespace std;
#define read freopen("in.in","r",stdin)
#define write freopen("out.out","w",stdout)
#define FastIO ios::sync_with_stdio(0)
typedef long long ll;
int n; 
int cost[100005];
int memo[100005];
int dp(int idx) {
	if (idx > n)return 9999999;
	if (idx == n-1)return 0;
	int &ret = memo[idx];

	if (ret != -1)return ret;
	ret = min(dp(idx + 1) + abs(cost[idx + 1] - cost[idx]), dp(idx + 2) + abs(cost[idx] - cost[idx + 2]));
	return ret;
}
int main() {
	FastIO;
#ifndef ONLINE_JUDGE
	//write; read;
#endif 
	memset(memo, -1, sizeof memo);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> cost[i];
	cout << dp(0) << endl;
	
		
	return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
#define debug(x) cout<<#x<<": "<<(x)<<endl
using namespace std;
using ll = long long;
#define rep(i, s, n) for (int i = (s); i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
const ll MOD = 1e9+7;
ll LLINF = 1LL << 60;
int INF = INT_MAX;


int main(){
    ll n,k; cin>>n>>k;
    vector<ll> a(n);
    rep(i,0,n) cin>>a[i];
    vector<ll> memo(n+1,-1);
    ll now=a[0];
    vector<ll> v;
    while(memo[now]==-1){
        v.push_back(now);
        memo[now]=v.size();
        now=a[now-1];
    }
    ll left=memo[now]-1;
    ll loop=v.size()-left;

    if(v.size() >= k) cout<<v[k-1]<<endl;
    else{
        cout<<v[(k-left-1)%loop+left]<<endl;
    }
    
}


Measured memory_bytes: 8456
#include<stdio.h>

int main(){
    int n,a[3];
    scanf("%d",&n);
    a[0]=n/100;
    a[1]=(n-100*a[0])/10;
    a[2]=(n-100*a[0]-10*a[1]);
    
    for(int i = 0; i <3; i++)
    {
    if (a[i]==9) {a[i]=1;
    }else{
        
        if (a[i]==1) {
            a[i]=9;
        }
        
    }
    
    }
    printf("%d",100*a[0]+10*a[1]+a[2]);
    return 0;
}

Measured memory_bytes: 256
module Main where
-- import Debug.Trace
import Data.List
import qualified Data.Sequence as S
import qualified Data.ByteString.Char8 as B
import Data.Int
import Data.Char
import Data.Array
import Data.Maybe
import qualified Data.Map as M
import Data.Ord
import Data.Functor
import Control.Applicative
import Control.Monad

solve :: [Int] -> Int
solve l = iter cycles where
    iter [] = 0
    iter (c:cs) = cost c + iter cs 

    cost = iter 0 0 maxBound where
        iter c s m [] -- c: length of this cycle, s:sum of this cycle, m: minimum in this cycle.
            | c < 2 = s
            | otherwise = s + min (m*(c-2)) (ma*(c+1) + m)
        iter c s m (x:xs) = iter (c+1) (s+x) (min m x) xs

    sl = sort l
    ma = head sl  -- minimum in all
    permutation = M.fromList $ zip l sl

    cycles = iter [] l where
        iter cl [] = cl
        iter cl (x:xs)
            | elem x ul = iter cl xs
            | otherwise = iter (cycle:cl) xs where
                ul = concat cl
                cycle = iter [x] where
                    iter cl@(c:cs)
                        | v == c = [] 
                        | elem v cl = cl
                        | otherwise = iter (v:cl) where
                            v =  permutation M.! c 

readIntLn:: IO Int
readIntLn = (fst . fromJust . B.readInt) <$> B.getLine

readIntList:: IO [Int]
readIntList = map (fst . fromJust . B.readInt) . B.words <$> B.getLine

main :: IO() 
main = do
    _ <- readIntLn
    l <- readIntList

    print $ solve l 



Measured memory_bytes: 4296
// C++11
#include "bits/stdc++.h"
#include <sys/time.h>
#include <emmintrin.h>
#include <string>
#include <sstream>
#include <fstream>
#include <random>
#include <bitset>

using namespace std;

inline long long GetTSC() {
  long long lo, hi;
  asm volatile ("rdtsc": "=a"(lo), "=d"(hi));
  return lo + (hi << 32);
}
inline double GetSeconds() {
  return GetTSC() / 2.8e9;
}

const int M = 256;
const int XM = 20000;
const int CM = 16;
const long inf = pow(10,15);
long d[M];
long nd[M];
int xs[XM];
int cs[CM];

void solve(){
  double starttime = GetSeconds();
  while(1){
    int n,m;
    cin >> n >> m;
    if(n==0 && m==0) break;
    for(int i=0; i<m; i++){
      cin >> cs[i];
    }
    for(int i=0; i<n; i++){
      cin >> xs[i];
    }

    for(int i=0; i<M; i++){
      d[i] = inf;
    }
    d[128] = 0;
    for(int i=0; i<n; i++){
      int x = xs[i];
      for(int j=0; j<M; j++){
        nd[j] = inf;
      }
      for(int k=0; k<256; k++){
        long v = d[k];
        for(int j=0; j<m; j++){
          int c = cs[j];
          int nk = max(min(k+c,255),0);
          if(nd[nk] > v + pow(x-nk, 2)){
            nd[nk] = v + pow(x-nk, 2);
          }
        }
      }
      for(int j=0; j<M; j++){
        d[j] = nd[j];
      }
    }
    long t = inf;
    for(int j=0; j<M; j++){
      t = min(t, d[j]);
    }

    cout << t << endl;
  }

  return;
}

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




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

const double pi = 3.141592653589793;

int main() {
    ll N, M;
    cin >> N >> M;
    vector<ll> A(M);
    rep(i,M) cin >> A.at(i);
    ll total = 0;
    rep(i,M) total += A.at(i);
    if (total > N) cout << -1 << endl;
    else cout << N - total << endl;
}



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

ULL C[1001][1001] = {};

UL G[1000];
UL W;
const ULL M = 1000000;

struct Node {
	UL win, lose;
	UL p;
	UL nc = 0;
	UL z = 0;
	ULL dp = 1;
} V[1000];

int main() {
	C[0][0] = 1;
	for (UL i = 1; i <= 1000; i++) {
		C[i][0] = C[i - 1][0];
		for (UL j = 1; j < i; j++) C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;
		C[i][i] = C[i - 1][i - 1];
	}

	UL N; cin >> N;
	rep(i, N) G[i] = ~0u;
	rep(i, N - 1) {
		cin >> V[i].win >> V[i].lose;
		V[i].win--; V[i].lose--;
		G[V[i].lose] = i;
	}
	rep(i, N) if (G[i] == ~0u) W = i;
	V[N - 1].lose = W;
	G[W] = N - 1;
	rep(i, N - 1) {
		V[i].p = G[V[i].win];
		V[V[i].p].nc++;
	}

	queue<UL> Q;
	rep(i, N) if (V[i].nc == 0) Q.push(i);
	while (Q.size()) {
		UL p = Q.front(); Q.pop();
		if (p == N - 1) break;
		V[p].z++;
		UL e = V[p].p;
		V[e].z += V[p].z;
		ULL c = C[V[e].z][V[p].z];
		V[e].dp = V[e].dp * V[p].dp % M;
		V[e].dp = V[e].dp * c % M;
		V[e].nc--;
		if (V[e].nc == 0) Q.push(e);
	}

	cout << V[N - 1].dp << endl;

	return 0;
}



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

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

int main() {
  int n, m, x;
  cin >> n >> m >> x;
  int l = 0, r = 0;
  rep(i, m) {
    int a;
    cin >> a;
    if (a < x)
      l++;
    else
      r++;
  }
  cout << min(l, r) << endl;
  return 0;
}


Measured memory_bytes: 256
import std.algorithm;
import std.array;
import std.container;
import std.conv;
import std.math;
import std.range;
import std.stdio;
import std.string;
import std.typecons;

int readint() {
    return readln.chomp.to!int;
}

int[] readints() {
    return readln.split.map!(to!int).array;
}

void main() {
    auto q = BinaryHeap!(int[])(new int[2_000_001], 0);

    string s;
    while ((s = readln.chomp).length > 0) {
        if (s == "end")
            break;

        if (s[0] == 'e') { // extract
            writeln(q.front);
            q.popFront;
        }
        else {
            auto ss = s.split;
            int x = ss[1].to!int;
            q.insert(x);
        }
    }
}

Measured memory_bytes: 11048
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<sstream>
#define INF (1<<24)
using namespace std;
 
struct State{
  int pos;
  int S;
  int sw;
  State (int pos=-1,int S=-1,int sw=-1) : pos(pos),S(S),sw(sw){}
};
 
int n,m,k,flg;
vector <int> t[15];
vector <int> u[15];
bool vd[15][(1<<16)+1];
 
State  pi[15][(1<<16)+1];
string ps[15][(1<<16)+1];
queue < State > Q;
 
int start;
vector<string> ans;
 
void input();
void init();
//void print_bit(int);
void dijkstra();
string change(int x);
 
int main(){
  while(cin>>n>>m){
    if(n==0&&m==0)break;
    init();
    input();
    dijkstra();
  }
  return 0;
}
 
void init(){
  for(int i=0;i<15;i++){
    t[i].clear();
    u[i].clear();
    for(int j=0;j<=(1<<16);j++){
      vd[i][j]=false;
      pi[i][j]=State(-1,-1,-1);
      ps[i][j]="";
    }
  }
  while(!Q.empty())Q.pop();
  ans.clear();
  start=flg=0;
}
 
void input(){
  int a,b;
 
  for(int i=0;i<m;i++){
    cin>>a>>b;
    t[a-1].push_back(b-1);
    t[b-1].push_back(a-1);
  }
 
  for(int i=0;i<n;i++){
    cin>>a;
    if(a==1)start+=(1<<i);
  }
   
  for(int i=0;i<n;i++){
    cin>>a;
    for(int j=0;j<a;j++){
      cin>>b;
      if(b-1!=i)u[i].push_back(b-1);
    }
  }
}
 
void dijkstra(){
  State A,X;
  int p;
 
  A.pos=0;
  A.S=start;
  A.sw=-1;
  Q.push(A);
 
  while(!Q.empty()){
 
    A=X=Q.front();Q.pop();
 
 
    if(X.pos==n-1)flg=1;
 
    if(vd[X.pos][X.S]==true)continue;
    else vd[X.pos][X.S]=true;
 
    /*
    cout<<endl;
    cout<<ps[X.pos][X.S]<<endl;
    cout<<pi[X.pos][X.S].pos<< ' '; print_bit(pi[X.pos][X.S].S);
    cout<<X.pos<<' '; print_bit(X.S);
    cout<<endl;
    */
 
    for(int i=0;i<(int)t[X.pos].size();i++){
      p=t[X.pos][i];
      if(((X.S>>p)&1)==0)continue;
      if(vd[p][X.S]==true)continue;
      Q.push( State( p, X.S ,-1) );
      pi[p][X.S]=A;
      ps[p][X.S]="Move to room "+change(p)+".";
 
    }
 
    for(int i=0;i<(int)u[X.pos].size();i++){
      p=u[X.pos][i];
 
      if(p<=X.sw)continue;
      if(vd[X.pos][X.S^(1<<p)]==true)continue;
 
      Q.push( State( X.pos, X.S^(1<<p) ,p) );
 
      pi[X.pos][X.S^(1<<p)]=A;
      if((X.S>>p)&1) ps[X.pos][X.S^(1<<p)]="Switch off room "+change(p)+".";
      else           ps[X.pos][X.S^(1<<p)]="Switch on room "+change(p)+".";
 
    }
 
  }
   
  State I = pi[n-1][1<<(n-1)];
  if(vd[n-1][1<<(n-1)]==true){
    ans.push_back( ps[n-1][1<<(n-1)] );
 
    while(1){
      if(ps[I.pos][I.S]=="")break;
      ans.push_back( ps[I.pos][I.S] );
      I=pi[I.pos][I.S]; 
    }
    cout<<"You can go home in "<<ans.size()<<" steps."<<endl;
    for(int i=(int)ans.size()-1;i>=0;i--)cout<<ans[i]<<endl;

  }else if(flg==1){
    cout<<"You can not switch off all lights."<<endl;
  }else{
    cout<<"Help me!"<<endl;
  }
}
 
/*
vector <int> print_b;
void print_bit(int x){
  print_b.clear();
  for(int i=0;i<15;i++){
    print_b.push_back(x%2);
    x/=2;
  }
  for(int i=14;i>=0;i--){
    cout<<print_b[i];
  }
  cout<<endl;
}
*/

string change(int x){
  x++;
  string res;
  stringstream ss;
  ss<<x;
  ss>>res;
  return res;
}

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

int main() {
    int x;
    cin >> x;
    int ans = (x / 500) * 1000 + (x % 500 / 5) * 5;
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for(int i=0; i<(n); i++)
using namespace std;
using ll = long long;
int main()
{
    string a,b,c;
    cin >> a;
    cin >> b;
    cin >> c;
    char user = 'a';
    int size = a.size()+b.size()+c.size();
    rep(i, size){
        // cout << user <<endl;
        if(user=='a'){
            if(a.size() == 0) {user = 'a'; break;}
            user = a[0];
            a.erase(0,1);
        }else if(user=='b'){
            if(b.size() == 0) {user = 'b'; break;}
            user = b[0];
            b.erase(0,1);
        }else if(user=='c'){
            if(c.size() == 0) {user = 'c'; break;}
            user = c[0];
            c.erase(0,1);
        }
    }
    if(user=='a'){
        cout << 'A' << endl;
    }else if(user=='b'){
        cout << 'B' << endl;
    }else if(user=='c'){
        cout << 'C' << endl;
    }

    return 0;
}

Measured memory_bytes: 3636
// https://atcoder.jp/contests/abc169/tasks/abc169_e
#include <iostream>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <vector>
using namespace std;

int main()
{
    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i] >> b[i];
    }
    std::sort(a.begin(), a.end());
    std::sort(b.begin(), b.end());
    if (n & 1)
    {
        int ind = (n + 1) / 2 - 1;
        long long am = a[ind], bm = b[ind];
        long long ans = bm - am + 1;
        cout << ans << endl;
        return 0;
    }
    else
    {
        int ind = n / 2 - 1;
        long long am2 = a[ind] + a[ind + 1], bm2 = b[ind] + b[ind + 1];
        long long ans = bm2 - am2 + 1;
        cout << ans << endl;
        return 0;
    }
    return 0;
}


Measured memory_bytes: 6428
#include <bits/stdc++.h>
#define endl '\n'
#define ll long long
#define fo(i,n) for(i=0;i<n;++i)
#define forr(i,n) for(i=n-1;i>=0;--i)
using namespace std;

ll gcd(ll a,ll b){while(a&&b)a>b?a%=b:b%=a;return a+b;}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cerr<<"First never follows"<<endl;
	ll n, k, x, y, ans;
	cin>>n>>k>>x>>y;
	if(n<=k){
		ans = n*x;
		cout<<ans<<endl;
	}
	else{
		ans = k*x;
		ans = ans + (n-k)*y;
		cout<<ans<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <utility>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
using namespace std;
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) int((x).size())
#define OUT(x) cout << (x) << endl;
typedef long long ll;
typedef vector<bool> V;
typedef vector<vector<int>> VV;
typedef pair<int, int> P;
typedef map<string, int> M;
typedef unordered_map<int, int> HM;
typedef queue<int> Q;

int main(){
    int n,m;
    cin >> n >> m;
    V vec1(n, false), vec2(n, false);
    for (int i = 0; i < m; i++)
    {
        int a,b;
        cin >> a >> b;
        if (a == 1)
        {
            vec1[b-1] = true;
        }
        if (b == n)
        {
            vec2[a-1] = true;
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (vec1[i] == true && vec2[i] == true)
        {
            OUT("POSSIBLE");
            return 0;
        }
    }
    OUT("IMPOSSIBLE");
}

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


int main() {
    const int MAX = 200000;
    int a[MAX], n, rmin, dmax;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];


    rmin = a[0];
    dmax = -2000000000;
    for (int i = 1; i < n; i++) {
        dmax = max(dmax, a[i] - rmin);
        rmin = min(rmin, a[i]);
    }
    cout << dmax << endl;

    return 0;
}


Measured memory_bytes: 3880
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCoder
{
    class Program
    {
        static void Main()
        {
            Solve();

            Console.ReadKey();
        }

        static void Solve()
        {
            var str = IO.GetIntList();
            var ans = Math.Max(str[0] + str[1], Math.Max(str[0] - str[1], str[0] * str[1]));

            Console.WriteLine(ans);
        }
    }


    static class IO
    {
        static public string GetString() { return Console.ReadLine(); }
        static public int GetInt() { return int.Parse(Console.ReadLine()); }
        static public long GetLong() { return long.Parse(Console.ReadLine()); }
        static public List<string> GetStringList() { return Console.ReadLine().Split(' ').ToList(); }
        static public List<int> GetIntList() { return Console.ReadLine().Split(' ').Select(int.Parse).ToList(); }
        static public List<long> GetLongList() { return Console.ReadLine().Split(' ').Select(long.Parse).ToList(); }
        static public List<double> GetDoubleList() { return Console.ReadLine().Split(' ').Select(double.Parse).ToList(); }
        static public void WriteStrings<T>(IEnumerable<T> values) { foreach (var o in values) { Console.Write(o + " "); } }
    }
}

Measured memory_bytes: 13268
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/
const int mod = 1000000007;


int main() {
int N,K;
cin>>N>>K;
int A[N];
rep(i,N){
    cin>>A[i];
}
if(N<=K){
    cout<<1<<endl;
    return 0;
}
N--;
if(N%(K-1)==0){
    cout<<N/(K-1)<<endl;

}
else{
    cout<<N/(K-1)+1<<endl;
}


return 0;
}

Measured memory_bytes: 3940
#include<bits/stdc++.h>
#define ll double
#define fr(a,b) for(int i = a; i < b; i++)
#define mod 1000000007
#define triplet pair<int,pair<int,int>>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
 
ll dp[301][301][301];

 
int main(){
    fast_io;
    //cin>>t;
    int n,k;
    cin>>n>>k;
    vector<int>v(n);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    vector<int>dp(k+1,0);
    for(int i=0;i<=k;i++){
        for(int j : v){
            if(i>=j&&dp[i-j]==0){
                dp[i]=1;
            }
        }
    }
    if(dp[k]) cout<<"First";
    else cout<<"Second";
    return 0;
}

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

int main(int argc, const char * argv[]) {



    cin.tie(0);
    ios::sync_with_stdio(false);

    /////////////////////
    // Write code below /
    /////////////////////
    int r;

    cin>>r;

    cout<<r * r<<endl;


    return 0;
}

Measured memory_bytes: 256
inf=10**8
a,b,c,d,e,f=map(int,input().split())
a,b=100*a,100*b
DP=[inf]*(f+max(a,b)+1)
DP[a],DP[b]=0,0

for i in range(f+1):
    if DP[i]!=inf:
        DP[i+a]=DP[i]
        DP[i+b]=DP[i]
        for j in c,d:
            if 100*(DP[i]+j)/(i+j)<=100*e/(100+e):
                DP[i+j]=max(DP[i],DP[i]+j)

ans,index=0,[a,0]
for i in range(f+1):
    if DP[i]!=inf:
        if ans<100*DP[i]/i:
            ans=100*DP[i]/i
            index=[i,DP[i]]

print(*index)

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

int main(void)
{
  int64_t n;
  cin >> n;
  int res = 11;
  for(int i = 1; i <= n / i; i++)
  {
    if(n % i == 0)
    {
      int m = n / i;
      string sm = to_string(m);
      string si = to_string(i);
      int cnt = max(sm.size(), si.size());
      if(cnt < res)
      {
        res = cnt;
      }
    }
  }
  cout << res << endl;
}

Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace AOJ
{
    class Program
    {
        static void Main(string[] args)
        {
            var dic = new Dictionary<int, int>();
            var lis = new List<int>();
            var cnt = 0;
            dic.Add(0, 0);
            dic.Add(1, 0);
            for (int i = 2; i < 1000000; i++)
            {
                bool isPrime = true;
                foreach (var j in lis)
                {
                    if (j > Math.Sqrt(i)) break;
                    if (i % j == 0) { isPrime = false; break; }
                }
                if (isPrime) { lis.Add(i); cnt++; }; dic.Add(i, cnt);
            }


            int n; string s;
            while ((s = Console.ReadLine()) != null)
            {
                n = int.Parse(s);
                Console.WriteLine(dic[n]);
            }
        }
    }
}

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

int main(void) {
    int n, k;
    string s;
    cin >> n >> k >> s;
    switch (s[k - 1]) {
        case 'A':
            s[k - 1] = 'a';
            break;
        case 'B':
            s[k - 1] = 'b';
            break;
        case 'C':
        default:
            s[k - 1] = 'c';
            break;
    }
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>

double toRadian(int degree)
{
    return (degree / (180 / M_PI));
}

int main()
{
    int a, b, C;
    scanf("%d%d%d", &a, &b, &C);

    double S, L, h;
    S = (double)(a * b * sin(toRadian(C)) / 2);
    double c = sqrt(pow(a, 2) - 2*a*b*cos(toRadian(C)) + pow(b, 2));
    L = (double)(a + b + c);
    h = (double)(2 * S / a);
    printf("%lf\n%lf\n%lf\n", S, L, h);

    return 0;
}


Measured memory_bytes: 2120
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        System.out.println(str.replace("2017","2018"));
    }
}


Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //GCC5.4.1で配列の範囲外アクセスをエラーにする

//cmdで g++ test.cpp とするとコンパイルできる
//制限1秒なら10^6は余裕 10^7は多分間に合う 10^8はよほど単純でないと厳しい

#define ALL(x) x.begin(),x.end()
#define get_tp(t,i) get<i>(t)
#define len(x) (ll)(x.size())
typedef long long ll; //long long
typedef pair<int,int> pii; //pair<int,int>
typedef pair<long long,long long> pllll; //pair<ll,ll>
typedef vector<int> vi; //vector<int>
typedef vector<vector<int>> vvi; //vector<vector<int>>
typedef vector<ll> vll; //vector<long long>
typedef vector<vector<ll>> vvll; //vector<vector<long long>>
typedef priority_queue<int, vector<int>, greater<int> > gpq; //逆順priority_queue
typedef priority_queue<int> pq;

//const int MOD=998244353;
const int MOD=1000000007; //10^9+7
const long double PI=3.1415926535897932;

int main(){
    int N,M;
    cin>>N>>M;
    vector<tuple<ll,ll,ll>> cake(N);
    for(int i=0;i<N;i++){
        ll x,y,z;cin>>x>>y>>z;
        cake[i]=make_tuple(x,y,z);
    }
    
    ll ans;
    for(int p=0;p<8;p++){
        vll score(N);
        for(int i=0;i<N;i++){
            score[i]=get_tp(cake[i],0)*((p&1)?1:-1);
            score[i]+=get_tp(cake[i],1)*((p&2)?1:-1);
            score[i]+=get_tp(cake[i],2)*((p&4)?1:-1);
        }
        sort(ALL(score));
        reverse(ALL(score));
        ll sum=0;
        for(int i=0;i<M;i++){
            sum+=score[i];
        }
        if(p==0){
            ans=sum;
        }else{
            ans=max(ans,sum);
        }
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3632
N = int(input())
H = list(map(int, input().split(" ")))
H.reverse()
H.append(float('inf'))	# sentinel value
ans = 0
ind, counter = 0, 0

while ind < N:
  if H[ind] <= H[ind + 1]:
    counter += 1
    ind += 1
  else:
    ans = max(ans, counter)
    counter = 0
    ind += 1
print(max(ans, counter - 1))

Measured memory_bytes: 15020
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back

#define speed ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
signed main()
{
    speed
    int r;cin>>r;
    cout<<(3*r*r);
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i)
#define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i)
#define rreps(i, n) for (int i = ((int)(n)); i > 0; --i)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
#define repc2(i, s, n) for (int i = (s); i <= (int)(n); i++)
#define inf 2e9
#define linf 9000000000000000000ll
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int n;
vector<int> v;
vector<int> min_pf;

void prime_factorize_init(int n) {
    min_pf.resize(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (min_pf.at(i) == 0) {
            for (int mul = i; mul <= n; mul += i) {
                min_pf.at(mul) = i;
            }
        }
    }
}

void prime_factorize(int n, vector<int> &res) {
    if (n <= 1) return;
    while (n != 1) {
        res.push_back(min_pf.at(n));
        n /= min_pf.at(n);
    }
    res.erase(unique(res.begin(), res.end()), res.end());
}
vector<int> b(1000009);
int main() {
    cin >> n;
    v.resize(n);
    prime_factorize_init(1000000);
    rep(i, n) scanf("%d", &v[i]);
    bool is_pc = true;
    rep(i, n) {
        vector<int> pf;
        prime_factorize(v[i], pf);
        for (int p : pf) {
            b[p]++;
            if (b[p] > 1) {
                is_pc = false;
                break;
            }
        }
        if (!is_pc) break;
    }
    if (is_pc) {
        cout << "pairwise coprime" << endl;
    } else {
        if (accumulate(v.begin(), v.end(), 0, [](int m, int n) { return __gcd(m, n); }) == 1) {
            cout << "setwise coprime" << endl;
        } else {
            cout << "not coprime" << endl;
        }
    }

    return 0;
}

Measured memory_bytes: 14840
#include <iostream>
#include<math.h>
#include<string>
using namespace std;

bool Check(int num){
        for(int i=2; i<=sqrt(num); i++){
                int chnum = num;
                while(chnum%i==0){
                        chnum/=i;
                }
                if(chnum==1)return true;
        }
        return false;
}

int main() {
        int X;

        int ans=1;

        cin >> X;

        for(int i=2; i<=X; i++){
                if(Check(i))ans=i;
        }

        cout << ans << endl;

        return 0;
}

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

int main()
{
	int h, w, k;
	cin >> h >> w >> k;
	vector<string> ss(h);
	for (auto &&s : ss)
	{
		cin >> s;
	}

	int ans = 0;

	for (int S = 0; S < (1 << h); S++)
	{
		for (int T = 0; T < (1 << w); T++)
		{
			vector<string> ts(ss);

			for (int i = 0; i < h; i++)
			{
				if (S & (1 << i))
				{
					for (int j = 0; j < w; j++)
					{
						ts[i][j] = 'R';
					}
				}
			}

			for (int j = 0; j < w; j++)
			{
				if (T & (1 << j))
				{
					for (int i = 0; i < h; i++)
					{
						ts[i][j] = 'R';
					}
				}
			}

			int cnt = 0;
			for (int i = 0; i < h; i++)
			{
				for (int j = 0; j < w; j++)
				{
					if (ts[i][j] == '#')
					{
						cnt++;
					}
				}
			}

			if (cnt == k)
			{
				ans++;
			}
		}
	}

	cout << ans << endl;

	return 0;
}

Measured memory_bytes: 3632
#pragma GCC optimize ("O3")
#include<bits/stdc++.h>
using namespace std;

/// Info.
///****************************************************************************************************************************************///
/// author                : BAHAA El-DEEN OSAMA .
/// Problem name          : G - Mix Juice
/// Method                : brute force
/// Online judge          : vjudge(Contest)
/// Date                  : 8/6/2020
///****************************************************************************************************************************************///


vector<int>vec;
int k,sum=0,n,val;

int main()
{
cin>>n>>k;
for(int i=0;i<n;++i)
{
    cin>>val;
    vec.push_back(val);
}
sort(vec.begin(),vec.end());
for(int j=0 ;j<k;++j)
{
    sum+=vec[j];
}
cout <<sum <<endl;




return 0;
}


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

typedef unsigned long long ull;
typedef long long ll;
typedef long double ld;
const double pi = 3.14159265358979323846;

#define all(s) s.begin(),s.end()
#define allr(s) s.rbegin(),s.rend()
#define speed ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)

void rw()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif // ONLINE_JUDGE
}

int main()
{
	speed;
	//rw();

	float d, t, s;
	cin >> d >> t >> s;

	float c = d / s;

	cout << (c > t ? "No" : "Yes");



	return 0;
}


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


#define pub push_back
#define pob pop_back
#define fi first
#define se second
#define PI acos(-1.0)
#define emp emplace_back
#define INF 2e9
#define INFLL 9e18
#define EPS 1e-9
#define DEBUG 0
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))


#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin, (x).rend()

#define sz(a) int((a).size())


using namespace std;

typedef vector<int> vi;
typedef vector<int>::iterator iter;
typedef vector<vi> vvi;
typedef pair<int, int> pa;
typedef vector<pa> vii;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef double ld;


double logdob(ll number, ll base){
   return log2(number)*1.0/log2(base);
}

ll log(ll number,ll base){
    return log2(number)/log2(base);
}

ll power(ll x, ll y){
    return (pow(x, y) + EPS);
}



int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.precision(0);
    cout << fixed;
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);

    ull a;
    long double b;
    cin >> a >> b;
    cout << (ull)(a*b*1.0) << endl;
    return 0;
}



Measured memory_bytes: 3768
import std.stdio;
import std.ascii;
import std.conv;
import std.string;
import std.algorithm;
import std.range;
import std.functional;
import std.math;
import core.bitop;
import std.numeric;

alias lread = () => readln.chomp.to!long;
alias aryread = () => readln.split.to!(long[]);

void main()
{
    auto N = lread();
    string[] W = new string[](N);

    foreach (i; 0 .. N)
        W[i] = readln.chomp;

    if (W.dup.sort().uniq().array.length != W.length)
    {
        writeln("No");
        return;
    }

    bool flag = true;

    foreach (i; 1 .. N)
    {
        flag = flag && (W[i][0] == W[i - 1][$ - 1]);
    }
    (flag ? "Yes" : "No").writeln;
}


Measured memory_bytes: 256
#include <iostream>
#define MOD 1000000007;

using namespace std;
using ull = unsigned long long;

int main()
{
    int input, answer = 1;
    cin >> input;

    /// 階乗の要素を並べた配列
    ull factorial[input+1];

    for (int i = 1; i <= input; i++)
    {
        factorial[i] = i;
    }

    /// 素因数分解用の配列
    ull primes[input+1];

    for (int i = 0; i <= input; i++)
    {
        primes[i] = 0;
    }

    // 素因数分解
    for (int i = 2; i <= input; i++)
    {
        int prime = 2;
        while (factorial[i] != 1)
        {
            if (factorial[i] % prime == 0)
            {
                factorial[i] /= prime;
                primes[prime]++;
            }
            else
            {
                prime++;
            }
        }
    }

    /*
        105 % 12 = 9
        3 % 12 * 5 % 12 * 7 % 12 = 9
        (((1 * 3) % 12 * 5) % 12) * 7 % 12 = 9
    */
   for (int i = 2; i <= input; i++)
   {
       answer = (answer * (primes[i] + 1)) % MOD;
   }

    cout << answer << endl;

    return 0;
}

Measured memory_bytes: 888
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

int main(){
  int a,b,c;
  a=1;
  b=c=0;

  char d,e;
  while(scanf(" %c,%c",&d,&e) != EOF){
    if(d=='A'){
      if(e=='B') swap(a,b);
      else if(e=='C') swap(a,c);
    }else if(d=='B'){
      if(e=='A') swap(b,a);
      else if(e=='C') swap(b,c);
    }else{
      if(e=='A') swap(c,a);
      else if(e=='B') swap(c,b);
    }
  }

  if(a) printf("A\n");
  else if(b) printf("B\n");
  else printf("C\n");

  return 0;

  
  
}

Measured memory_bytes: 1112
use proconio::{input, marker::Usize1};

fn main() {
    input! {
        n: usize,
        pp: [Usize1; n],
    }

    let mut qq = vec![0; n];
    let mut max = 0;

    for i in 0..n {
        if pp[i] == 0 {
            qq[pp[i]] = 1;
        } else {
            qq[pp[i]] = qq[pp[i]-1] + 1;
        }
        max = std::cmp::max(max, qq[pp[i]]);
    }

    println!("{}", n-max);
}


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

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

    string s;
    cin>>s;

    if(s.at(0) == s.at(1) && s.at(0) == s.at(2) && s.at(1) == s.at(2))
    {
        cout<<"No"<<endl;
        return 0;
    }
    else
    {
        cout<<"Yes"<<endl;
        return 0;
    }

    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	static Scanner scanner;

	static int h;
	static int w;
	static int k;
	static String[][] S;
	public static void main(String[] args) {
	    scanner = new Scanner(System.in);

	    h=gi();
	    w=gi();
	    k=gi();
	    S = new String[h][w];

	    for (int i=0; i<h;i++) {
	    	String s=gs();
	    	for (int j=0; j<w; j++) {
	    		S[i][j]=String.valueOf(s.charAt(j));

	    	}
	    }
	    int c=0;
	    for (int i=0; i<Math.pow(2, h+w);i++) {
	    	int ik=f(i);
	    	if (ik==k) {
	    		c++;
	    	}
	    }



	    System.out.println(c);

//	    if (isNumber(s1) && isNumber(s2) && s.charAt(a) == '-') {
//	    	System.out.print("Yes");
//	    }else {
//	    	System.out.print("No");
//	    }



	}

	public static int f(int n) {
		int c=0;
		String t=String.format("%0"+ String.valueOf(h+w) + "d", Long.parseLong(two(n)));
		for (int i=0; i<h;i++) {
			char inh = t.charAt(i);
			if (inh=='1') {
				continue;
			}
	    	for (int j=0; j<w; j++) {
	    		char inw = t.charAt(h+j);
	    		if (inw=='1') continue;
	    		if (S[i][j].equals("#")) c++;
	    	}
	    }
		return c;
	}

	public static String two(int n) {
		StringBuilder sb = new StringBuilder();
		if(n==0) return "0";
		while(n>0) {
			int k=n%2;
			sb.insert(0, k);
			if (k==0) {
				n=n/2;
			} else {
				n= (n-1) /2;
			}
		}

		return sb.toString();
	}

	public static long d(long n) {
		String a=String.valueOf(n);
		return (long)a.length();
	}

	// 文字列として入力を取得
	public static String gs() {
		return scanner.next();
	}

	// intとして入力を取得
	public static int gi() {
		return Integer.parseInt(scanner.next());
	}

	// longとして入力を取得
	public static long gl() {
		return Long.parseLong(scanner.next());
	}

	// doubleとして入力を取得
	public static double gd() {
		return Double.parseDouble(scanner.next());
	}
}

Measured memory_bytes: 52208
n, k = map(int, input().split())
a = list(map(lambda x: int(x)-1, input().split()))

num = 0
li = [0]
flag = [True] * n
flag[0] = False

for i in range(k):
    num = a[num]
    if flag[num]:
        li.append(num)
        flag[num] = False
    else:
        break

d = li.index(num)
ans = (k-d)%(len(li)-d)+d
print(li[ans]+1)

Measured memory_bytes: 32380
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

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

int main(){
  ll a,b,k;cin>>a>>b>>k;
  ll ans1=a,ans2=b;
  if(a>=k) ans1=a-k;
  else{
    ans1 = 0;
    ans2 -= k-a;
  }

  if(ans1<0 or ans2<0){
    ans1=0;
    ans2=0;
  }
  cout<<ans1<<" "<<ans2<<endl;
}


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

int main() {
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,ans=0;
    cin>>n;
    for(int i=1;i<n;i++)
    {
        int tm=n-i;
        int a,b;
        for(int i=sqrt(tm);i>0;i--)
        {
          if(tm%i==0)
          {
              b=tm/i;
              a=i;
              if(a!=b)
              {
                  ans+=2;
              }
               else
              {
                  ans++;
              }
          }
        }
    }
    cout<<ans;
}


Measured memory_bytes: 3660
#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+5;
int T[N], n, rt;
int main(){
    scanf("%d", &n);
    rt = n-1;
    for(int i=0;i<n;i++){
        int a; scanf("%d", &a);
        if(a==1){ T[1] = 1; continue; }
        T[a] = T[a-1]+1;
        rt = min(rt, n-T[a]);
    }
    printf("%d", rt);
}

Measured memory_bytes: 1024
#include <cstdio>
#include <utility>
#include <typeinfo>
#include <cmath>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <vector>
#include <tuple>
#define REP(i,n) for(int i=0;i<n;i++)
typedef long long int ll;
using namespace std;
typedef vector<ll> vll;
typedef pair<ll,ll> pll;
typedef vector<pll> vpll;
typedef vector<string> vs;

int main()
{

    ll x,y;
    cin>>x>>y;
    cout<<x*y<<" "<<2*(x+y)<<endl;
    return 0;
}

Measured memory_bytes: 1160
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
L = LI()
A = [(L[i], i) for i in range(n)]
ans = [0] * n
A.sort()
min_ind = INF
for i in range(n - 1, 0, -1):
    min_ind = min(min_ind, A[i][1])
    if A[i - 1][0] < A[i][0]:
        ans[min_ind] += (A[i][0] - A[i - 1][0]) * (n - i)

ans[0] += A[0][0] * n
for j in ans:
    print(j)


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

int main()
{
    int n;cin>>n;
    int i;
    vector<int> dig(100,0);
    vector<int> ans(100,0);
    if(n==0)cout<<0<<endl;
    else if(n>0)
    {
        int m=n;
        int count=0;
        while(m>0)
        {
            dig.at(count)+=(m%2);
            count++;
            m/=2;
        }
        for(i=0;i<70;i++)
        {
            if(i%2==0)
            {
                ans.at(i)+=dig.at(i);
            }
            else
            {
                ans.at(i)+=dig.at(i);
                ans.at(i+1)+=dig.at(i);
            }     
            if(ans.at(i)>=2)
            {
                if(i%2==0)
                {
                    ans.at(i+1)+=ans.at(i)/2;
                    ans.at(i+2)+=ans.at(i)/2;
                    ans.at(i)%=2;
                }
                else if(ans.at(i+1)>0)
                {
                    ans.at(i)-=2;
                    ans.at(i+1)--;
                }
            }
        }
    }
    else
    {
        int m=abs(n);
        int count=0;
        while(m>0)
        {
            dig.at(count)+=(m%2);
            count++;
            m/=2;
        }
        for(i=0;i<70;i++)
        {
            if(i%2==0)
            {
                ans.at(i)+=dig.at(i);
                ans.at(i+1)+=dig.at(i);
            }
            else ans.at(i)+=dig.at(i);
            if(ans.at(i)>=2)
            {
                if(i%2!=0)
                {
                    ans.at(i+1)+=ans.at(i)/2;
                    ans.at(i+2)+=ans.at(i)/2;
                    ans.at(i)%=2;
                }
                else if(ans.at(i+1)>0)
                {
                    ans.at(i+1)--;
                    ans.at(i)-=2;
                }
            }
        }
    }
    int fir;
    for(fir=80;fir>=0;fir--)
    {
        if(ans.at(fir)!=0)break;
    }
    for(i=fir;i>=0;i--)cout<<ans.at(i);
    cout<<endl;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int n = scan.nextInt();
		scan.nextLine();
		
		int minVal=scan.nextInt(), maxVal=minVal;
		long sum=minVal;

		for(int i=0; i<n-1; i++) {
			int val = scan.nextInt();
			
			if(minVal > val) minVal = val;
			
			if(maxVal < val) maxVal = val;
			
			sum += val;
		}
		
		System.out.println(minVal + " " + maxVal + " " + sum);

	}

}






Measured memory_bytes: 41080
#include <iostream>
#include <cmath>
using namespace std;
int a[100005],dp[100005];
int main(int argc, char** argv) {
	int n,k;
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		cin >> a[i];
	dp[1]=0;
	for(int i=2;i<=n;i++)
	{
		dp[i]=1e9;
		for(int j=1;j<=min(k,i-1);j++)
			dp[i]=min(dp[i],dp[i-j]+abs(a[i]-a[i-j]));
	}
	cout << dp[n];
	return 0;
}

Measured memory_bytes: 1024