akhauriyash/Code-Regression huggingface dataset:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    R, C, K = read_values()
    V = [0] * (R * C)
    for _ in range(K):
        r, c, v = read_values()
        r -= 1
        c -= 1
        V[r * C + c] = v
    
    dp = [[0] * (R * C) for _ in range(4)]
    for i in range(R * C):
        r = i // C
        c = i % C
        if c + 1 < C:
            # not take
            for k in range(4):
                dp[k][i + 1]= max(dp[k][i + 1], dp[k][i])

            # take 
            for k in range(3):
                dp[k + 1][i + 1] = max(dp[k + 1][i + 1], dp[k][i] + V[i])

        # next r
        if r + 1 < R:
            for k in range(4):
                dp[0][i + C] = max(dp[0][i + C], dp[k][i] + (V[i] if k < 3 else 0))

    res = 0
    for k in range(4):
        res = max(res, dp[k][-1] + (V[-1] if k < 3 else 0))
    print(res)


if __name__ == "__main__":
    main()



Measured memory_bytes: 426560
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long ll;
typedef pair<ll,ll> P;
const ll mod=1000000007;
const ll LINF=1LL<<60;
const int INF=1<<30;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int main(){
	ll n,c,k;cin>>n>>c>>k;
	vector<ll> t(n);
	for(ll i = 0; i < n; i++) {
		cin>>t[i];
	}
	sort(ALL(t));
	ll index = 0;
	ll ans = 0;
	while(index < n){
		auto x = upper_bound(t.begin() + index,t.end(),t[index] + k);
		ll id_up = distance(t.begin() + index,x);
		index = index + min(c,id_up);
		ans ++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3996
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define fi first
#define se second
#define sz(x) ((int)(x).size())
using ll=long long;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define MOD  1000000007
const ll INF=1e18;
template<class T>void show(vector<T>v){for (int i = 0; i < v.size(); i++){cerr<<v[i]<<" ";}cerr<<endl;}
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b){ a = b; return 1; } return 0; }



int main(int argc, char const *argv[]) {
  int n;
  cin >> n;
  vector<ll> a(n),b(n);
  rep(i,n) cin >> a[i];
  ll mx=-1, id;
  rep(i,n){
    b[i] = a[i];
    if (a[i] > mx) {
      chmax(mx, a[i]), id = i;
    }
  }
  sort(all(b));

  rep(i,n){
    if(i==id)cout << b[n-2] << endl;
    else cout << mx << endl;
  }
  
  return 0;
}

Measured memory_bytes: 6360
import Data.Bits
import Data.List
import Control.Monad
import Data.Array.Unboxed
import Data.Array.MArray
import Data.Array.ST
import Control.Monad.ST
import Data.Maybe (fromJust)
import qualified Data.ByteString.Lazy.Char8 as B
import Debug.Trace

main :: IO ()
main = do
  [n,x] <- map read.words <$> getLine :: IO [Int]
  ls <- map read.words <$> getLine :: IO [Int]

  print $ length $ takeWhile ( <= x) $ scanl (+) 0 ls


Measured memory_bytes: 892
// https://atcoder.jp/contests/dp/tasks/dp_b

#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <string>
#include <tuple>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF (1e9)
#define MOD (1e9 + 7)
#define LINF (1e18)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
// int gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// int lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<int> h(n + k, INF);
    REP(i, n) cin >> h[i];
    // 入力値の足場の高さHの差分の合計を最小化する
    vector<int> dp(n + k, INF);
    dp[0] = 0;
    REP(i, n - 1) {
        for (int j = 1; j <= k; j++) {
            dp[i + j] = min(dp[i + j], dp[i] + abs(h[i + j] - h[i]));
        }
    }
    cout << dp[n - 1] << endl;

    return 0;
}


Measured memory_bytes: 1024
import std.stdio;
import std.algorithm;
import std.string;
import std.range;
import std.array;
import std.conv;
import std.complex;
import std.math;
import std.ascii;
import std.bigint;
import std.container;
import std.typecons;

auto readInts() {
	return array(map!(to!int)(readln().strip().split()));
}
auto readInt() {
	return readInts()[0];
}
auto readLongs() {
	return array(map!(to!long)(readln().strip().split()));
}
auto readLong() {
	return readLongs()[0];
}

const real eps = 1e-10;

void main(){
	while(true) {
		auto n = readInt();
		if(n == 0) {
			return;
		}
		int[] s;
		int sum;
		for(int i; i < n; ++i) {
			s ~= readInt();
			sum += s[$-1];
		}
		sort(s);
		sum -= s[0] + s[$-1];
		writeln(sum/(n-2));
	}
}

Measured memory_bytes: 2472
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < int(n); i++)
#define rep1(i,n) for (int i = 1; i <= int(n); i++)
#define repR(i,n) for (int i = int(n)-1; i >= 0; i--)
#define rep1R(i,n) for (int i = int(n); i >= 1; i--)
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fst first
#define snd second
#define cauto const auto
#ifdef LOCAL
#define dump(...) cerr << "[" << __LINE__ << ":" << __FUNCTION__ << "] ", _dmp_(#__VA_ARGS__, __VA_ARGS__);
void _dmp_(const char*) { cerr << endl; }
template <class T, class... U>
void _dmp_(const char *s, T const& x, U const& ...y) { const char *o = "({[", *e = "]})"; for (int i = 0; *s != '\0'; cerr << *s++) { if (count(o,o+3,*s)) i++; if (count(e,e+3,*s)) i--; if (!i && *s == ',') break; } cerr << " = " << x; if (*s == ',') cerr << ", ", s++; _dmp_(s, y...); }
#else
#define dump(...)
#endif
using ll = long long;
#define int ll
template <class T> using pque_max = priority_queue<T>;
template <class T> using pque_min = priority_queue<T, vector<T>, greater<T> >;
#define CONAINER_OUTPUT os << "{"; for (auto const& x : v) os << " " << x; return os << " }";
template <class T> ostream& operator<<(ostream& os, vector<T> const& v) { CONAINER_OUTPUT }
template <class T> ostream& operator<<(ostream& os, deque<T> const& v) { CONAINER_OUTPUT }
template <class T> ostream& operator<<(ostream& os, set<T> const& v) { CONAINER_OUTPUT }
template <class T, class U> ostream& operator<<(ostream& os, map<T,U> const& v) { CONAINER_OUTPUT }
#undef CONAINER_OUTPUT
template <class T> istream& operator>>(istream& is, vector<T>& v) { for (auto& x : v) is >> x; return is; }
template <class T, class S> ostream& operator<<(ostream& os, pair<T,S> const& p) { return os << "(" << p.first << ", " << p.second << ")"; }
template <class T, class S> istream& operator>>(istream& is, pair<T,S> const& p) { return is >> p.first >> p.second; }
struct _Init_ { _Init_() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); } } _init_;

template <class T> void quit(T const& x) { cout << x << endl; exit(0); }
template <class T> bool chmin(T& x, T const& y) { if (x > y) { x = y; return true; } return false; }
template <class T> bool chmax(T& x, T const& y) { if (x < y) { x = y; return true; } return false; }
#define YesNo(c) ((c) ? "Yes" : "No")
////////////////////////////////

int n;
struct edge { int cost,to; };
vector<vector<edge> > g;
vector<int> d, used;

void dfs(int v, int x) {
    d[v] = x;
    used[v] = 1;
    for (cauto& e : g[v]) {
        if (used[e.to]) continue;
        dfs(e.to, x^e.cost);
    }
}

int32_t main() {
    cin >> n;
    g.resize(n);
    d.resize(n);
    used.resize(n);
    rep (i,n-1) {
        int u,v,w; cin >> u >> v >> w; u--,v--,w%=2;
        g[u].push_back({w,v});
        g[v].push_back({w,u});
    }
    dfs(0,0);
    rep (i,n) cout << d[i] << endl;
}


Measured memory_bytes: 9984
import heapq
n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(m):
  temp = heapq.heappop(a)
  heapq.heappush(a, (-1) * (-temp//2))

print(-sum(a))

Measured memory_bytes: 72216
import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
	int n =  sc.nextInt();
	int k =  sc.nextInt();
	Long count =	0L;
	Integer h[] = new Integer[n];

	for(int i=0;i<n;i++) {
		h[i] = sc.nextInt();
	}
	Arrays.sort(h,  Collections.reverseOrder());

	try {
		for(int i=0;i<k;i++) {
			h[i] = 0;
		}
	}
	catch(Exception e) {}
	finally{
		for(int i=0;i<n;i++) {
			count += h[i];
		}
	}
	System.out.println(count);
  }
}

Measured memory_bytes: 95356
#include<cstdio>
#include<cstdlib>
#include<string>
#include<iostream>
using namespace std;

struct Node {
	int key;
	Node *left, *right, *parent;
};

Node *root, *NIL;

void insert(int k) {
	Node *y=NIL;
	Node *x = root;
	Node *z;

	z = (Node *)malloc(sizeof(Node));
	z->key = k;
	z->left = NIL;
	z->right = NIL;

	while (x != NIL) {
		y = x;
		if (z->key < x->key) {
			x = x->left;
		}
		else {
			x = x->right;
		}
	}
	z->parent = y;
	if (y == NIL) {
		root = z;
	}
	else {
		if (z->key < y->key) {
			y->left = z;
		}
		else {
			y->right = z;
		}
	}
}

void inorder(Node *u) {
	if (u == NIL)return;
	inorder(u->left);
	printf(" %d", u->key);
	inorder(u->right);
}
void preorder(Node *u) {
	if (u == NIL)return;
	printf(" %d", u->key);
	preorder(u->left);
	preorder(u->right);
}

int main()
{
	int n, i, x;
	string com;
	scanf("%d", &n);

	for (i = 0; i < n; i++) {
		cin >> com;
		if (com == "insert") {
			scanf("%d", &x);
			insert(x);
		}
		else if (com == "print") {
			inorder(root);
			printf("\n");
			preorder(root);
			printf("\n");
		}
	}

	return 0;
}



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

int main(){
	int dx[4]={0,1,0,-1};
    int dy[4]={-1,0,1,0};
	int w,h;
	queue<pair<int,int>> q;

	while(cin>>w>>h && w>0){
		bool wall[4][h][w];
		rep(i,w) wall[0][0][i]=wall[2][h-1][i]=1;
		rep(i,h) wall[3][i][0]=wall[1][i][w-1]=1;
		// bool up[h][w],right[h][w],left[h][w],down[h][w];
		// rep(i,w-1) up[0][i]=down[h-1][w-2-i]=1;
		// rep(i,h) left[i][0]=right[i][w-1]=1;
		int d[h][w];
	    rep(i,h)rep(j,w)d[i][j]=INF;
		int y=0;
		while(y<h){
			int x;
			rep(j,w-1){
				cin>>x; //cout<<x;
				wall[1][y][j]=wall[3][y][j+1]=x;
				// right[y][j]=left[y][j+1]=x;
			}if(y!=h-1)rep(j,w){
				cin>>x; //cout<<x;
				wall[2][y][j]=wall[0][y+1][j]=x;
				// down[y][j]=up[y+1][j]=x;
			}
			y++;
		}
		// rep(i,h)rep(j,w){
		// 	rep(k,4)cout<<wall[k][i][j];
		// 	cout<<endl;
		// }
		d[0][0]=1;
	    q.push(make_pair(0,0));

		while(q.size()){
	        pair<int,int> p=q.front(); //qの最右を取り出す
	        q.pop(); //取り出したら削除
			//cout<<p.first<<" "<<p.second<<endl;
	        int prev=d[p.first][p.second]; //一手前の手数prev
	        rep(i,4){ //4方向探索
	            int cy=p.first+dy[i];
	            int cx=p.second+dx[i];
				if(0<=cy and cy<h and 0<=cx and cx<w){
					if(!wall[i][p.first][p.second] and d[cy][cx]==INF){ //通行可能かつ未到達
		                d[cy][cx]=prev+1;
		                q.push(make_pair(cy,cx)); //突っ込む
		            }
				}
	        }
	    }
		//rep(i,h)rep(j,w)cout<<d[i][j]<<endl;
		if(d[h-1][w-1]==INF) cout<<0<<endl;
	    else cout<<d[h-1][w-1]<<endl;
	}
	return 0;
}



Measured memory_bytes: 3036
#include <bits/stdc++.h>
#define N 1<<20
using namespace std;

struct P{
  int a,b,idx;
  P(){a=b=idx=0;}
  P(int a,int b,int idx):a(a),b(b),idx(idx){};
  bool operator < (const P &A) const{
    if(a!=A.a) return a>A.a;
    return b>A.b;
  }
};

char ch[N];
P r[N];
int n;

vector<int> Sort(){
    vector <int> R(n+1),res(n+1);
  
  for(int i=0;i<=n;i++) R[i]=ch[i];
  
  for(int i=1;i<=n;i*=2){
    for(int j=0;j<=n;j++)r[j]=P(R[j],(j+i<=n)? R[j+i]:0,j);
    sort(r,r+n+1);
    R[r[0].idx]=n;
    for(int j=1,C=n;j<=n;j++){
      if(r[j-1]<r[j]) C--;
      R[r[j].idx]=C;
    }

    //    for(int j=0;j<=n;j++)cout<<R[j]<<' ';
    //			   cout<<endl;

  }
  for(int i=0;i<=n;i++) res[R[i]]=i;
  return res;
}

int check(vector <int> &a,char *x){
  /*
  cout<<'!'<<endl;
  for(int i=0;i<n+1;i++){
    printf("%d %s\n",a[i],ch+a[i]);
  }
  cout<<'!'<<endl;
  */
  int L=0,M,R=n;
  int m=strlen(x);

  while(L<R){
    M=(L+R)/2;
    if(strncmp(ch+a[M],x,m)<0)L=M+1;
    else R=M;
  }

  return strncmp(ch+a[L],x,m)==0;
}

int main(){
  scanf("%s",ch);
  n=strlen(ch);
  int q;
  cin>>q;
  vector <int> Rank=Sort();
  char a[1001];

  while(q--){
    scanf("%s",a);
    printf("%d\n",check(Rank,a));
  }
  return 0;
}

Measured memory_bytes: 22176
-module('Main').
-export([main/1]).

main(_) ->
    {ok, [A, V]} = io:fread("", "~d ~d"),
    {ok, [B, W]} = io:fread("", "~d ~d"),
    {ok, [T]} = io:fread("", "~d"),
    D = V - W,
    case abs(B - A) =< T * D  of
        true ->
            io:format("YES~n");
        false ->
            io:format("NO~n")
    end,
    halt().


Measured memory_bytes: 21860
#include <bits/stdc++.h>
#include <iostream>
#include <string>
#include <algorithm> 
#include <cmath>
#include <cstdlib>
using namespace std;
#define ll long long 
#define gc getchar_unlocked
const int MOD = 1000000007;
const int MAXV = 1e5 + 10;
const int MAXN = 1e3 + 10;
const ll INF = 1e13;

ll dp[MAXV];
int N,W,V,wi[MAXN],vi[MAXN];

int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
  
	cin>>N>>W;
	int i;
	for(i=1;i<=N;i++)
	{
		cin>>wi[i]>>vi[i];
		V += vi[i];
	}

	for(i=1;i<=V;i++)
	    dp[i] = INF;
	dp[0] = 0;
	for(int item=1;item<=N;item++)
	{
		int w = wi[item], v = vi[item];
		for(i=V;i>=v;i--)
		{
			dp[i] = min(dp[i],dp[i-v] + w);
		}
	}
	for(i=V;i>=0;i--)
	{
		if(dp[i] <= W)
		{
			cout<<i<<"\n";
			break;
		}
	}
}

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

int main(){
    int n,k,x,y;cin >> n >> k >> x >> y;
    int sum = 0;

    if (k >= n){
        sum += n * x;
    } else {
        sum += k*x + (n-k)*y;
    }

    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 384
package main
 
import (
	"fmt"
)

func main() {
	var (
		a int
	)
	var o = "No"
	list := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 15, 21, 24, 27, 20, 28, 32, 36, 25, 30, 35, 40, 45, 42, 48, 54, 49, 56, 63, 64, 72, 81}
	fmt.Scanf("%d", &a)
	for _, r := range list {
		if r == a {
			o = "Yes"
		}
	}
	fmt.Print(o)
}

Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <algorithm>
#include <climits>
#include <cmath>
#include <utility>
#include <string>
#include <cstring>
#include <functional>

using namespace std;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int n;
	string s;

	cin >> n;
	cin >> s;

	int red = 0;
	for (int i = 0; i < n; ++i)
		if (s[i] == 'R')
			++red;

	if (red > n-red)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rep(i,l,r) for (int i=l;i<=r;i++)
using namespace std;
const int maxn=200500;
const int inf=1e9;
typedef long long ll;
const ll mm=1e9+7;
ll fac[4050000],inv[4050000];
int n,k;
ll f[2050][2050];
ll Pow(ll x,ll y){
    ll ans=1;
    while (y){
        if (y&1) ans=ans*x%mm;
        x=x*x%mm;
        y/=2;
    }
    return ans;
}
ll C(ll n,ll m){
    return fac[n]*inv[m]%mm*inv[n-m]%mm;
}
int main(){
    int N=4000000;
    fac[0]=1;
    rep(i,1,N) fac[i]=fac[i-1]*i%mm;
    inv[N]=Pow(fac[N],mm-2);
    for (int i=N;i>=1;i--) inv[i-1]=inv[i]*i%mm;
    //rep(i,1,10) printf("%lld %lld\n",fac[i],inv[i]);
    scanf("%d%d",&n,&k);
    f[0][0]=1;
    rep(i,1,n) rep(j,0,i){
        if (i-1>=j) f[i][j]=f[i-1][j];
        if (j) (f[i][j]+=C(n-i+(n-j+1)*(k-1)-1,k-2)*f[i][j-1]%mm*(n-j+1)%mm)%=mm;
    }
    if (k>1) printf("%lld\n",f[n][n]);
    else printf("%lld\n",f[n][0]);
    return 0;
}

Measured memory_bytes: 94464
#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;
#define int long long int


// quoted from beet-aizu
template <typename T,typename E, typename F, typename G, typename H>
struct LazySegmentTree{
    //using F = function<T(T,T)>;
    //using G = function<T(T,E)>;
    //using H = function<E(E,E)>;
    int n,height;
    F f;
    G g;
    H h;
    T ti;
    E ei;
    vector<T> dat;
    vector<E> laz;
    LazySegmentTree(F f,G g,H h,T ti,E ei):
        f(f),g(g),h(h),ti(ti),ei(ei){}

    void init(int n_){
        n=1;height=0;
        while(n<n_) n<<=1,height++;
        dat.assign(2*n,ti);
        laz.assign(2*n,ei);
    }
    void build(const vector<T> &v){
        int n_=v.size();
        init(n_);
        for(int i=0;i<n_;i++) dat[n+i]=v[i];
        for(int i=n-1;i;i--)
            dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
    }
    inline T reflect(int k){
        return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
    }
    inline void eval(int k){
        if(laz[k]==ei) return;
        laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
        laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
        dat[k]=reflect(k);
        laz[k]=ei;
    }
    inline void thrust(int k){
        for(int i=height;i;i--) eval(k>>i);
    }
    inline void recalc(int k){    
        while(k>>=1)
            dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
    }
    void update(int a,int b,E x){
        thrust(a+=n);
        thrust(b+=n-1);
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1){
            if(l&1) laz[l]=h(laz[l],x),l++;
            if(r&1) --r,laz[r]=h(laz[r],x);
        }
        recalc(a);
        recalc(b);
    }
    void set_val(int a,T x){
        thrust(a+=n);
        dat[a]=x;laz[a]=ei;
        recalc(a);
    }
    T query(int a,int b){
        thrust(a+=n);
        thrust(b+=n-1);
        T vl=ti,vr=ti;
        for(int l=a,r=b+1;l<r;l>>=1,r>>=1) {
            if(l&1) vl=f(vl,reflect(l++));
            if(r&1) vr=f(reflect(--r),vr);
        }
        return f(vl,vr);
    }
};

signed main(){
    
    int n, q; cin >> n >> q;
    auto f = [](int a, int b){ return min(a, b); };
    auto g = [](int a, int b){ return b != -1 ? b : a; };
    auto h = [](int a, int b){ return b != -1 ? b : a; };
    LazySegmentTree<int, int, decltype(f), decltype(g), decltype(h)> sg(f, g, h, INT_MAX, -1);
    sg.build(vector<int>(n, INT_MAX));
    for(int i = 0; i < q; i++){
        int com; cin >> com;
        if(!com){
            int s, t, x; cin >> s >> t >> x;
            sg.update(s, t + 1, x);
        }else{
            int s, t; cin >> s >> t;
            cout << sg.query(s, t + 1) << endl;
        }
    }
    return 0;
}



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

int t;
ll N, A, B, C, D;
map<ll, ll> memo;

ll solve(ll val)
{
    if(val==0) return 0;
    if(val==1) return D;
    if (memo.count(val)) return memo[val];

    ll l2 = (val/2)*2;
    ll r2 = ((val+1)/2)*2;
    ll l3 = (val/3)*3;
    ll r3 = ((val+2)/3)*3;
    ll l5 = (val/5)*5;
    ll r5 = ((val+4)/5)*5;
 
    ll res = 1e18;
    if (val < res/D) res = val*D;
    res = min(res, llabs(l2-val)*D + A + solve(l2/2));
    res = min(res, llabs(r2-val)*D + A + solve(r2/2));
 
    res = min(res, llabs(l3-val)*D + B + solve(l3/3));
    res = min(res, llabs(r3-val)*D + B + solve(r3/3));
 
    res = min(res, llabs(l5-val)*D + C + solve(l5/5));
    res = min(res, llabs(r5-val)*D + C + solve(r5/5));

    memo[val] = res;
    return res;
}

int main()
{
    cin >> t;
    while(t--)
    {
        cin >> N;
        cin >> A >> B >> C >> D;
        memo.clear();
        ll res = solve(N);
        cout << res << endl;
    }
    return 0;
}

Measured memory_bytes: 4360
x=int(input())
if x==1:
    print(0,-1)
    exit()
else:
    n5=[0]
    i=1
    for i in range(1,120):
        i5=i*(i*i)**2
        n5.append(i5)
        if abs(x-i5) in n5:
            print(n5.index(i5),-(x-i5)//abs(x-i5)*(n5.index(abs(x-i5))))
            break

Measured memory_bytes: 61840
#include<iostream>

using namespace std;

int main(){
int x;
int y;
int z;
cin >> x;
cin >> y;
cin >> z;
if (x < y ) {
  if (y < z){
cout << "Yes" << endl;
}
else if (y > z){
  cout << "No" << endl;
}} else {
cout << "No" << endl;
}
return 0;
}



Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int> > ba;
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        ba.push_back(make_pair(b,a));
    }
    sort(ba.begin(),ba.end());
    int ans=1,x=ba[0].first-1;
    for(int i=0;i<m;i++){
        if(ba[i].second<=x)continue;
        else{
            ans++;
            x=ba[i].first-1;
        }
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 1400
#include<bits/stdc++.h>
clock_t t=clock();
namespace IO
{
	using namespace std;
	char buf[1<<22],Out[1<<22],*p1=buf,*p2=buf;
	int p3=-1,f=0;
	inline void file()
	{
		#ifdef NTFOrz
		freopen("file.in","r",stdin);
		#endif
	}
	inline char getchar()
	{
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
	}
	inline void flush(){fwrite(Out,1,p3+1,stdout),p3=-1;}
	inline void check(){if (p3>(1<<21)) flush();}
	inline void putchar(char a){Out[++p3]=a;check();}
	inline void putline(string s)
	{
		int tmp=p3;
		while (p3-tmp<s.size()) putchar(s[p3-tmp]);
		putchar('\n');
	}
	inline char gc()
	{
		char c=getchar();
		while (!c||c=='\n'||c==' ') c=getchar();
		return c;
	}
	inline void chktime()
	{
		#ifdef NTFOrz
		printf("%dms\n",clock()-t);
		#endif
	}
}
namespace my_std
{
	using namespace std;
	#define getchar IO::getchar
	#define putchar IO::putchar
    #define Re register
    #define rep(i,a,b) for (Re int i=(a);i<=(b);i++)
    #define drep(i,a,b) for (Re int i=(a);i>=(b);i--)
    #define repv(i,v) for (Re int i=0;i<v.size();i++)
    #define go(u) for (Re int i=head[(u)];i;i=e[i].nxt)
    #define writesp(x) write(x),putchar(' '),IO::check()
    #define writeln(x) write(x),putchar('\n'),IO::check()
    #define mem(x,v) memset(x,v,sizeof(x))
    #define pb push_back
    #define fir first
    #define sec second
    #define MP make_pair
    typedef long long ll;
    typedef unsigned long long ull;
    typedef pair<int,int> pii;
    const int INF=0x7fffffff;
    inline int read()
    {
        ll sum=0,f=0;char c=getchar();
        while (!isdigit(c)) f|=(c=='-'),c=getchar();
        while (isdigit(c)) sum=(sum<<1)+(sum<<3)+(c^48),c=getchar();
        return f?-sum:sum;
    }
    void write(int k)
    {
        if (k<0) putchar('-'),k=-k;
        if (k>=10) write(k/10);
        putchar(k%10+48);
    }
	#define templ template<typename T>
    templ inline void chkmax(T &x,T y){if (x<y) x=y;}
    templ inline void chkmin(T &x,T y){if (x>y) x=y;}
}
using namespace my_std;
const int N=100010;
int n,m,ecnt,head[N],siz,flag,path,cnt[5],col[N];
ll ans;
struct edge{int to,nxt,dis;}e[N<<1];
inline void add_edge(int u,int v,int w){e[++ecnt].to=v,e[ecnt].nxt=head[u],e[ecnt].dis=w,head[u]=ecnt;}
inline int add(int x,int y){return x+y>=3?x+y-3:x+y;}
void dfs(int u)
{
	siz++,cnt[col[u]]++;
	go(u)
	{
		int v=e[i].to;
		path+=(e[i].dis==1);
		if (col[v]==INF)
		{
			col[v]=add(col[u],e[i].dis);
			dfs(v);
		}
		else if (col[v]!=add(col[u],e[i].dis)) flag=1;
	}
}
int main()
{
	IO::file();
	n=read(),m=read();
	rep(i,1,n) col[i]=INF;
	rep(i,1,m)
	{
		int u=read(),v=read();
		add_edge(u,v,1),add_edge(v,u,2);
	}
	rep(i,1,n) if (col[i]==INF)
	{
		siz=flag=path=col[i]=0;
		memset(cnt,0,sizeof(cnt));
		dfs(i);
		if (!flag)
		{
			if (cnt[0]&&cnt[1]&&cnt[2]) ans+=1ll*cnt[0]*cnt[1]+1ll*cnt[1]*cnt[2]+1ll*cnt[2]*cnt[0];
			else ans+=path;
		}
		else ans+=1ll*siz*siz;
	}
	cout<<ans<<endl;
	IO::flush();
	IO::chktime();
	return 0;
}

Measured memory_bytes: 12588
A, B, C, X, Y = map(int, input().split())
ans = 5000 * 1000000
for i in range(0, max(X, Y)*2 + 1, 2): 
        x = max(0, X - i//2)
        y = max(0, Y - i//2)
        ans = min(ans, A*x + B*y + C*i)
print(ans)

Measured memory_bytes: 3060
# cについて回す

a, b, c, x, y = gets.split.map(&:to_i)
# 最小値を更新していくので十分に大きい数を用意
cost = 2<<100
# cが取りうる値（ループの中で2倍しているので偶奇について考えなくていい）
0.upto([x, y].max) do |c_c|
    # puts "cc=#{c_c}"
    # 0枚もありうる
    a_c, b_c = [x-c_c, 0].max, [y-c_c, 0].max
    c_c*=2
    temp = a_c*a+b_c*b+c_c*c
    # puts "a,b,c=#{a_c},#{b_c},#{c_c}, sum: #{temp}"
    cost = [cost, temp].min
end

puts cost

Measured memory_bytes: 1788
/*BISMILLAH
THE WHITE WOLF
NO DREAM IS TOO BIG AND NO DREAMER IS TOO SMALL*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef vector<long long> vll;
typedef vector<int> vi;

#define io ios_base::sync_with_stdio(false)
#define pb push_back
#define eb emplace_back
#define mod   1000000007
#define PI 2*acos(0.0)
#define all(r)(r).begin(),(r).end()
#define dbg(a) cout<<#a<<" ->->->-> "<<a<<"\n"
#define inf 1000000000000000000
#define N 3007
int dirx[] = {1, -1,0, 0}, diry[] = {0, 0, 1, -1};


//=============================================ASIFAZAD==============================================//
ll dp[N][N][5];
int r, c, k;
ll inp[N][N];

ll rec(int x, int y, int it)
{
    if(x >= r || y >= c)
        return 0;
    if(dp[x][y][it] != -1)
        return dp[x][y][it];
    ll res = 0;
    res = max(rec(x, y+1, it), rec(x+1, y, 0));
    if(inp[x][y] && it <3)
        res = max(res, max(rec(x, y+1, it+1), rec(x+1, y, 0)) + inp[x][y]);
    return dp[x][y][it] = res;
}


int32_t main()
{
    io;
    memset(dp, -1, sizeof(dp));
    cin>>r>>c>>k;
    for(int i = 0; i< k; i++)
    {
        int x, y, v;
        cin>>x>>y>>v;
        x--;
        y--;
        inp[x][y] = v;
    }

    cout<<rec(0,0,0);
    return 0;
}


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

int main()
{

    int n, x, y;
    cin >> n >> x >> y;
    int dis[n + 3][n + 3];
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            dis[i][j] = fabs(i - j);
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            int p = fabs(i - x) + fabs(j - y) + 1;
            int q = fabs(i - y) + fabs(j - x) + 1;
            dis[i][j] = min(dis[i][j], min(p, q));
           // cout << dis[i][j] << " ";
        }
       // cout << "\n";
    }

    int ans[n + 10] = {0};
    for (int i = 1; i <= n; i++)
    {
        for (int j = i + 1; j <= n; j++)
            ans[dis[i][j]]++;
    }
    for (int i = 1; i < n; i++)
        cout << ans[i] << "\n";
    return 0;
}

Measured memory_bytes: 15872
require 'set'; require 'prime'; require 'pp'
INF=Float::INFINITY; MOD=10**9+7
n = gets.chomp.to_i
a = gets.chomp.split.map(&:to_i)
b = gets.chomp.split.map(&:to_i)

left = []
right = []

i = 0
j = 0
si = 0
sj = 0
while i < n && j < n
  while a[i] == a[i+1]
    i += 1
  end
  while b[j] == b[j+1]
    j += 1
  end
  if a[i] > b[j]
    j += 1
    sj = j
  elsif a[i] < b[j]
    i += 1
    si = i
  else
    left.push j - si + 1
    right.push i - sj + 1

    j += 1
    sj = j
    i += 1
    si = i
  end
end

# p left
# p right
lmax = left.max
rmax = right.max
if left.empty?
  puts 'Yes'
  puts b.join(' ')
elsif lmax + rmax > n
  puts 'No'
else
  puts 'Yes'
  rmax.times do
   b.unshift b.pop
  end
  puts b.join(' ')
end

Measured memory_bytes: 48560
#include <iostream>
#include <string>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <set>
#include <climits>
#include <map>

using namespace std;

long long MOD = 1000000007;
long long dp[52];
int main(){
  int N;
  cin >> N;
  string S1;
  string S2;
  cin >> S1;
  cin >> S2;

  if(S1[0] == S2[0]){
    dp[0] = 3;
  } else {
    dp[0] = 6;
  }

  for(int i = 1; i < N; i++){
    if(S1[i] == S2[i]){
      if(S1[i - 1] != S2[i - 1]){
        dp[i] = dp[i - 1];
      } else {
        dp[i] = (dp[i - 1] * 2) % MOD;
      }
    } else {
      if(S1[i - 1] == S2[i - 1]){
        dp[i] = (dp[i - 1] * 2) % MOD;
      } else if(S1[i - 1] == S1[i] || S2[i - 1] == S2[i]){
        dp[i] = dp[i - 1];
      } else {
        dp[i] = (dp[i - 1] * 3) % MOD;
      }
    }
  }

  cout << dp[N - 1] << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <atcoder/all>
typedef long long ll;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REP2(i, a, b) for(int i = a;i <= b;i++)
#define REPR(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define MOD 1000000007
#define PI 3.14159265358979323846
#define vi vector<int>
#define vll vector<ll>
#define vi2 vector<vector<int>>
#define eb emplace_back
#define fi first
#define se second
#define ALL(v) v.begin(), v.end()
#define sz(x) int(x.size())
using namespace std;
using namespace atcoder;
using P = pair<ll,ll>;
const int dx[]{0, 1, 0, -1, -1, -1, 1, 1}, dy[]{1, 0, -1, 0, -1, 1, -1, 1};
#define INT(name) int name;cin >> name;
#define VEC(type,name,n) vector<type> name(n);REP(i,n) cin >> name[i];

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;
}

int main()
{
  ll T;
  cin >> T;
  REP(i,T){
    ll N,M,A,B;
    cin >> N >> M >> A >> B;
    cout << floor_sum(N,M,A,B) << endl;
  }
}

Measured memory_bytes: 3628
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <tuple>
#include <map>
#include <queue>
#include <set>
typedef long long ll;
using namespace std;
#define rep(i, n) for (int i = 0; i < int(n); i++)
#define mod 1000000007
#define fst first
#define pb push_back

int main()
{
    string S,T;
    cin >> S >> T;
    int ans = 0;
    for(int i = 0; i <= 2; i++){
        if(S.at(i) == T.at(i)){
            ans++;
         }
        }  
        cout << ans << endl;
}

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

long long binpow(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

long long binpowmod(long long a, long long b, long long m) {
    a %= m;
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a % m;
        a = a * a % m;
        b >>= 1;
    }
    return res;
}

int gcd(int a, int b) {
    if (!a || !b)
        return a | b;
    unsigned shift = __builtin_ctz(a | b);
    a >>= __builtin_ctz(a);
    do {
        b >>= __builtin_ctz(b);
        if (a > b)
            swap(a, b);
        b -= a;
    } while (b);
    return a << shift;
}

int lcm (int a, int b) {
    return a / gcd(a, b) * b;
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	ll t;
	ll n,k,sum,extra;
	// cin>>t;
	// while(t--){
		
	// }
	cin>>n;
	n = n%10;
	if (n==2 || n==4 || n==5 || n==7 || n==9)
	{
		cout<<"hon";
	}
	else if(n==0 || n==1 || n==6 || n==8){
		cout<<"pon";
	}
	else{
		cout<<"bon";
	}
}

Measured memory_bytes: 3640
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		long dp[][] = new long[n + 1][n + 1];
		for ( int i = 1; i <= n; i++ ) {
			dp[i][i] = in.nextInt();
		}
		in.close();

		for ( int col = 2; col <= n; col++ ) {
			int r = 1, c = col;
			while ( c <= n ) {
				dp[r][c] = Math.max(dp[r][r] - dp[r + 1][c], dp[c][c] - dp[r][c - 1]);
				r++;
				c++;
			}
		}
		System.out.println(dp[1][n]);
	}
}

Measured memory_bytes: 130216
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
constexpr int MOD = 1000000007;
constexpr int INF = numeric_limits<int>::max() / 2;
typedef pair<int,int> P;
using Graph = vector<vector<int>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const double PI = acos(-1.0);
// cout << fixed << setprecision(14);
 
signed main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);

    int N;
    cin >> N;
    int A[N];
    rep(i,N) cin >> A[i];
    map<int, int> mp;
    int dp[N+1];
    dp[0] = 1;
    rep(i,N){
        if(i != 0){
            if(A[i] == A[i-1]){
                dp[i+1] = dp[i];
                continue;
            }
        }
        if(!mp[A[i]]){
            dp[i+1] = dp[i];
            mp[A[i]] = dp[i+1];
        }
        else{
            dp[i+1] = dp[i] + mp[A[i]];
            dp[i+1] %= MOD;
            mp[A[i]] = dp[i+1];
        }
    }
    cout << dp[N] << endl;
}

Measured memory_bytes: 15872
import sys
sys.setrecursionlimit(10**6)
A,B = map(int,input().split())
cnt = 0
tmp = A
while True:
    cnt += 1
    if tmp >= B:
        break
    else:
        tmp += (A - 1) 

if B ==1:
    print(0)
else:
    print(cnt)

Measured memory_bytes: 3060
#include <bits/stdc++.h>
using namespace std;
using ll=long long int;
using ld=long double;
using VI=vector<ll>;
using VD=vector<ld>;
using VVI=vector<VI>;
using VC=vector<char>;
using VVC=vector<VC>;
using VS=vector<string>;
using PLL =pair<ll,ll>;
using PLD=pair<ld,ld>;
using VPLL=vector<PLL>;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=(ll)(n)-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define FORD(i,a,b) for(ll i=(a);i>=(b);i--)
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define SIZE(x) ((ll)(x).size())
#define MAX(x) *max_element((x).begin(),(x).end())
#define MIN(x) *min_element((x).begin(),(x).end())
#define SORTR(x) sort((x).rbegin(),(x).rend())
#define SORT(x) sort((x).begin(),(x).end())
#define SUM(x) accumulate((x).begin(),(x).end(), 0)
#define FILL(x,a) fill(x.begin(),x.end(),a)
#define EACH(i,x) for(typeof((x).begin()) i=(x).begin(); i!=(x).end(); ++i)

const int INF  = 1<<30;
const ld EPS   = 1e-10;
const int MOD  = int(1e9)+7;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle,BidirectionalIterator last){reverse(middle, last); return next_permutation(first , last);}
#define COUT(x) cout<<x<<"\n"

int operate(int op,int num){
  int add=0;
  if(op==0) add=num;
  else add=-num;
  return add;
}


void Main()
{
	ll a,b,c,d;
	ll result=0;
	vector<char> ope(2);
	ope={'+','-'};
	string S;
    cin>>S;
    a=(int)S[0]-'0';
    b=(int)S[1]-'0';
    c=(int)S[2]-'0';
    d=(int)S[3]-'0';
	REP(i,2) {
      REP(j, 2) {
        REP(k, 2) {
          result = a;
          result += operate(i, b);
          result += operate(j, c);
          result += operate(k, d);
          if(result==7) {
            cout<<a<<ope[i]<<b<<ope[j]<<c<<ope[k]<<d<<"=7"<<endl;
            return;
          }
        }
      }
    }
	//cout << result << "\n";
	return;
}

int main()
{
	std::cin.tie(0);
	std::ios_base::sync_with_stdio(false);
	std::cout << std::fixed << std::setprecision(15);
	Main();
}


Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include<math.h>
#include<list>
#include <algorithm>
#include<set>
#include<vector>
#include<math.h>
#include<map>
#include<string>
#include <numeric>
#include <queue>
#include <sstream>
#include <bitset>
#include<stack>

using namespace std;
using ll = long long;
using vll = vector<long long>;
using sll = set<long long>;

template<typename T>
T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<typename T>
T lcm(T a, T b) { return a / gcd(a, b) * b; }

template<typename T>
map<T, T> getPrimeFactor(T n) {
	map<T, T> res;
	for (T i = 2; i * i <= n; ++i) {
		while (n % i == 0) {
			res[i] ++;
			n /= i;
		}
	}
	if (n != 1) res[n] = 1;
	return res;
}

template<typename T>
bool IsPrimeNumber(T num)
{
	if (num <= 2) return true;
	else if (num % 2 == 0) return false;

	double sqrtNum = sqrt(num);
	for (int i = 3; i <= sqrtNum; i += 2)
	{
		if (num % i == 0)
		{
			return false;
		}
	}

	return true;
}

long long modinv(long long a, long long m) {
	long long b = m, u = 1, v = 0;
	while (b) {
		long long t = a / b;
		a -= t * b; swap(a, b);
		u -= t * v; swap(u, v);
	}
	u %= m;
	if (u < 0) u += m;
	return u;
}


#define in(x) cin >> x
#define out(x) cout << x
#define outn(x) cout << x << '\n'
#define outs(x) cout << x << ' '
#define rep(i,s,e) for(ll i=s;i<e;i++)
#define repeq(i,s,e) for(ll i=s;i<=e;i++)

int main() {
	ll N, W;
	std::cin >> N >> W;

	ll w, v;
	vector<vll> dp(N + 1, vll(N*1000 + 1, 1e9+7));
	repeq(i, 0, N) {
		dp[i][0] = 0;
	}

	repeq(i, 1, N) {
		std::cin >> w >> v;
		repeq(j, 1, N * 1000) {
			if (j < v) {
				dp[i][j] = dp[i - 1][j];
			}
			else {
				dp[i][j] = min(dp[i - 1][j - v] + w, dp[i - 1][j]);
			}
		}
	}

	for (ll i = N * 1000; i >= 0; i--) {
		if (dp[N][i] <= W) {
			std::cout << i << endl;
			return 0;
		}
	}


	return 0;

}


Measured memory_bytes: 80256
#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <functional>
#include <algorithm>
#include <random>
#include <cmath>
#include <climits>
long long int shift_next(unsigned long long int n) {
	n ^= n << 13;
	n ^= n >> 7;
	n ^= n << 17;
	return n;
}

int main() {
	constexpr int shift = 16;
	constexpr int unshift = 64 - shift;
	std::vector<int> count(1 << (shift + 1), 0);
	int n, k, x0; std::cin >> n >> k >> x0;
	if (x0 == 0) {
		std::cout << 0 << std::endl;
		return 0;
	}
	long long int x = x0;
	for (auto i = 0; i < n; ++i) {
		count[(x >> unshift) + (1 << shift)]++;
		x = shift_next(x);
	}
	auto head = 0;;
	for (; head < count.size() && count[head] < k; ++head) {
		count[head + 1] += count[head];
	}
	auto rest = k;
	if (head != 0) rest -= count[head - 1];
	std::vector<long long int> suspects;
	x = x0;
	for (auto i = 0; i < n; ++i) {
		if (head == ((x >> unshift) + (1 << shift))) suspects.push_back(x);
		x = shift_next(x);
	}
	std::sort(suspects.begin(), suspects.end());
	std::cout << suspects[rest - 1] << std::endl;
}


Measured memory_bytes: 3200
#include <bits/stdc++.h>
#define FOR(i,k,n)  for(int i = (k);i < (n);++i)
#define REP(i,n)    FOR(i,0,n)
#define ALL(x)      begin(x),end(x)

using namespace std;
using vecint = vector<int>;
using ll = int64_t;

int main()
{
  int n,k;
  cin>>n>>k;
  vecint x(n);
  REP(i,n) cin>>x[i];
  int mn = 400000000;
  REP(i,n-k+1) {
    int l = x[i], r = x[i+k-1];
    int sum = r - l + min(abs(l), abs(r));
    mn = min(mn, sum);
  }
  cout<<mn<<endl;
  return 0;
}


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

using std :: max ;
using std :: min ;

int l [100010], r [100010], dp [100010] [2] ;

int main ( )  {
	int n, cnt ( 0 ) ;
	scanf ( "%d", & n ) ;
	
	for ( int i = 1 ; i <= n ; ++ i )  {
		static int x ;
		scanf ( "%d", & x ) ;
		l [i] = 31 - __builtin_clz ( x ), r [i] = l [i] + ( ( 1 << l [i] ) != x ) ;
		cnt += r [i] ;
		dp [i] [0] = max ( dp [i- 1] [0] + min ( r [i - 1], l [i] ), dp [i - 1] [1] + min ( l [i - 1], l [i] ) ) ;
		dp [i] [1] = max ( dp [i -1] [0] + min ( r [i - 1], r [i] ), dp [i - 1] [1] + min ( l [i - 1], r [i] ) ) ;
	}

	return printf ( "%d\n", cnt - max ( dp [n] [0], dp [n] [1] ) ), 0 ;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz size()
#define ll long long
#define all(_v) _v.begin(), _v.end()

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	ll a, b, c, d;
	cin >> a >> b >> c >> d;
	for(int i = 0; i <= 10000; ++i) {
        if(i & 1) a -= d;
        else c -= b;
        if(c <= 0 && a > 0) cout << "Yes", exit(0);
        else if(a <= 0) cout << "No", exit(0);
	}
	return 0;
}


Measured memory_bytes: 3656
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
	Scanner scan = new Scanner(System.in);
	String a = scan.next();
	String b =scan.next();
	int c = 0;
	int d = 0;
	if(a.equals("H")){
		c =0;
	} else if(a.equals("D")){
		 c = 1;
	}
	if(b.equals("H")){
		 d = 0;
	}else if(b.equals("D")){
		 d = 1;
	}
	if((c+d)%2==0){
		System.out.println("H");
	}else{
		System.out.println("D");
	}
 }
}

Measured memory_bytes: 21588
#include<bits/stdc++.h>
using namespace std;
#define LL long long 
int main(){
	LL n,k;
	cin>>n>>k;
	if(k%2==1){
		cout<<((LL)n/k)*((LL)n/k)*((LL)n/k);
	}
	else{
		LL ans=((LL)n/k)*((LL)n/k)*((LL)n/k);
		n=n+k/2;
		ans+=((LL)n/k)*((LL)n/k)*((LL)n/k);
		cout<<ans;
	}
	return 0;
} 

Measured memory_bytes: 256
import sys
import math
import bisect

def main():
    n = int(input())
    ans = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i % 2 == 0 and j % 2 == 1:
                ans += 1
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 3060
#include <cstdio>
#include <queue>
using namespace std;
const int MAX_N = 20;
// 隣接行列
// map[a][b] = a->bのコスト
const int MAX = 0x7fffffff;//通行不可を表す
int map[MAX_N+1][MAX_N+1];
// 街の総数，街道の総数
int n, m;

// そこまでのコスト-場所
typedef pair<int, int> node;
bool visited[MAX_N+1];
int solve(int from, int to) {
	fill(visited, visited + MAX_N+1, false);
	priority_queue< node, vector<node>, greater<node> > que;
	que.push(node(0, from));
	while (!que.empty()) {
		node point = que.top();
		que.pop();
		if (point.second == to) {
			return point.first;
		}
		for (int i = 1; i <= n; i++) {
			if (map[point.second][i] < MAX && !visited[i]) {
				que.push(node(point.first + map[point.second][i], i));
			}
		}
		visited[point.second] = true;
	}
	return -1;
}

int main () {
	scanf("%d", &n);
	scanf("%d", &m);
	//最大コストで初期化
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			map[i][j] = MAX;
	int a, b, c, d;
	for (int i = 0; i < m; i++) {
		scanf("%d,%d,%d,%d", &a, &b, &c, &d);
		map[a][b] = c;
		map[b][a] = d;
	}
	scanf("%d,%d,%d,%d", &a, &b, &c, &d);
	printf("%d\n", c - d - solve(a, b) - solve(b, a));
	return 0;
}

Measured memory_bytes: 1032
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time
    import sys

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

    def same(self, x, y):
        return self.__root(x) == self.__root(y)

    def union(self, x, y):
        x = self.__root(x)
        y = self.__root(y)

        if x != y:
            self.__table[x] = y


@mt
def slv(N, M, P, XY):
    P = [-1] + P
    # G = [i for i in range(N + 1)]

    uf = UnionFind()
    for x, y in XY:
        uf.union(x, y)

    ans = 0
    for i, p in enumerate(P):
        if uf.same(p, i):
            ans += 1

    return ans


def main():
    N, M = read_int_n()
    P = read_int_n()
    XY = []
    for _ in range(M):
        XY.append(read_int_n())

    print(slv(N, M, P, XY))


if __name__ == '__main__':
    main()

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

int main ()
{
    long long int sum= 0,count= 0;
    int n,i;
    cin >> n;
    long long int ans = 1e18;
    vector<int> arr(n);
    for (i = 0 ; i<n ;i++)
    {
        cin >> arr[i];
        sum += arr[i];
    }
    sum = sum /n;
    for ( i = 0 ; i < n ;i++)
    {
        count += pow(arr[i]-sum,2);
    }
    ans = min (count,ans);
    count = 0;
     for ( i = 0 ; i < n ;i++)
    {
        count += pow(arr[i]-sum-1,2);
    }
    ans = min (count,ans);
    count = 0;
     for ( i = 0 ; i < n ;i++)
    {
        count += pow(arr[i]-sum+1,2);
    }
    ans = min (count,ans);
    cout << ans <<endl;
    }


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

ll s[111111],n,t;
ll calc(ll m) {
  ll x=1,c=0,k=0;
  while(1) {
    while(k<n&&x+m>s[k]) k++;
    if(!k) break;
    if(k==n) {
      c++;
      break;
    }
    ll l=lower_bound(s,s+k,x)-s;
    ll y=max(1LL,m-abs(x-s[l]));
    if(l) y=max(y,m-abs(x-s[l-1]));
    c++;
    x+=y;
  }
  return c;
}

int main() {
  while(cin>>n>>t&&n) {
    for(ll i=0;i<n;i++)cin>>s[i];
    ll l=s[0]-1,r=1LL<<60;
    while(l+1<r) {
      ll m=(l+r)/2;
      if(calc(m)>=t) l=m;
      else r=m;
    }
    cout<<(calc(l)<t?-1:l)<<endl;
  }
  return 0;
}


Measured memory_bytes: 3836
#include<iostream>
#include<algorithm>
#include<ctime>
#include<vector>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<numeric>
#include<queue>
#include<deque>
#include<cfloat>
#include<functional>
#include<tuple>
#include<math.h>
#include<bitset>
#include<stack>
#include<set>
#include<random>
#include<stdlib.h>
#define rip(i,n) for(ll i=0;i<n;i++)
#define Rip(i,n) for(ll i=1;i<=n;i++)
#define all(V) V.begin(),V.end()
#define ll long long
#define ld long double
#define MOD 1000000007
#define mod 998244353
#define sec setprecision
#define Pair pair<ll,ll>
#define _CRT_SECURE_NO_WARNINGS
#pragma target("avx")
#pragma optimize("O3")
#pragma optimize("unroll-loops")
constexpr double eps = 1e-9;
constexpr double pi = 3.141592653589793238462643383279;
using namespace std;
ll gcd(ll a, ll b)
{
	if (a % b == 0)	return(b);
	else return(gcd(b, a % b));
}
ll lcm(ll a, ll b)
{
	return a * b / gcd(a, b);
}
ll pow(ll x, ll n) {
	x %= mod;
	if (n == 0)
		return 1;
	if (n % 2 == 0)
		return (pow((x * x)%mod , n / 2)%mod);
	else
		return (x * pow(x, n - 1))%mod;
}
int main() {
	ll n, k;
	cin >> n >> k;
	if (n != 1)cout << k * pow(k-1,n-1) << endl;
	else cout << k << endl;
}

Measured memory_bytes: 3640
S = list(input())
N = len(S)
ans = 0

for i in range(2**(N-1)):
    Scop = S[:] 
    for j in range(N-1):
        if i & 2**j:
            Scop[j] = Scop[j]+'+'
    ans += eval(''.join(Scop))
    #print(Scop)

print(ans)        

Measured memory_bytes: 3060