akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;

template <typename T> void read(T &x)
{
	x = 0; char c = getchar(); bool f = 0;
	while(!isdigit(c) && c!='-') c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(isdigit(c)) x = x*10+c-'0', c = getchar();
	if(f) x = -x;
}

typedef long long ll;

const int MX = 200005;
const ll oo = 1e16;

struct NODE
{
	int p;
	ll d;

	NODE (const int &p0 = 0, const ll &d0 = 0) : p(p0), d(d0) {}

	bool operator < (const NODE &t) const {return p < t.p;}
};

int N, Q, A, B;
set<NODE> hor, ver;
int p[MX];
ll add;

ll getf(const set<NODE> &st, int x)
{
	ll ret = +oo;
	auto t = st.upper_bound(NODE(x, 0));
	if(t != st.end()) ret = min(ret, t->d + abs(t->p-x));
	if(t != st.begin())
	{
		t--;
		ret = min(ret, t->d + abs(t->p-x));
	}
	return ret;
}

void insf(set<NODE> &st, NODE nd)
{
	nd.d -= add;
	while(1)
	{
		auto t = st.upper_bound(nd);
		if(t == st.end()) break;
		if(t->d >= nd.d+abs(nd.p-t->p)) st.erase(t);
		else if(t->d+abs(nd.p-t->p) <= nd.d) return;
		else break;
	}
	while(1)
	{
		auto t = st.upper_bound(nd);
		if(t == st.begin()) break;
		else t--;
		if(t->d >= nd.d+abs(nd.p-t->p)) st.erase(t);
		else if(t->d+abs(nd.p-t->p) <= nd.d) return;
		else break;
	}
	st.insert(nd);
}

int main()
{
	read(N), read(Q), read(A), read(B);
	for(int i=1; i<=Q; i++)
	{
		read(p[i]);
		if(i == 1)
		{
			hor.insert(NODE(A, abs(B-p[i])));
			ver.insert(NODE(B, abs(A-p[i])));
		}
		else
		{
			NODE its1(p[i-1], getf(hor, p[i])+add);
			NODE its2(p[i-1], getf(ver, p[i])+add);
			add += abs(p[i]-p[i-1]);
			insf(hor, its1);
			insf(ver, its2);
		}
	}
	ll ans = +oo;
	for(auto i : hor) ans = min(ans, i.d+add);
	for(auto i : ver) ans = min(ans, i.d+add);
	printf("%lld\n", ans);
	return 0;
}

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

int main() {
  int h,w;
  cin >> h >> w;
  
  vector<string> grid(h);
  for (int i = 0; i < h; i++){
    cin >> grid.at(i);
  }
  
  vector<string> temp(0);
  for (int i = 0; i < h; i++){
    if(grid.at(i).find('#')!=string::npos){
      temp.push_back(grid.at(i));
    }
  }

  vector<string> trans(w);
  for (int i = 0; i < w; i++){
    for (int j = 0; j < temp.size(); j++){
      trans.at(i).push_back(temp.at(j).at(i));
    }
  }

  vector<string> temp2(0);
  for (int i = 0; i < trans.size(); i++){
    if(trans.at(i).find('#')!=string::npos){
      temp2.push_back(trans.at(i));
    }
  }

  vector<string> ans(temp2.at(0).size());
  for (int i = 0; i < temp2.at(0).size(); i++){
    for (int j = 0; j < temp2.size(); j++){
      ans.at(i).push_back(temp2.at(j).at(i));
    }
  }
  
  for (int i = 0; i < ans.size(); i++){
    cout << ans.at(i) << endl;
  }

}

Measured memory_bytes: 3624
#include <stdio.h>
int linearSearch(int a[],int n,int key){
  int i;
  i=0;
  a[n]=key;
  while(a[i]!=key){
    i++;
  }
  return i!=n;
}


int main(void)
{
  int i,n,q,ans,a[10001],key;
  ans=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&a[i]);
    }

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&key);
    if(linearSearch(a,n,key)){
      ans++;
    }
  }
  printf("%d\n",ans);
  
  return 0;
}

Measured memory_bytes: 1860
n = int(input())
arr = []
for i in range(1,int(pow(n,1/2))+1):
  if n % i == 0:
    arr.append(i)
res = []
for i in range(len(arr)):
  for j in range(-arr[i]-1,int(pow(n,1/2)+1)):
    if (j + arr[i])**5 - j**5 == n:
      res = [j+arr[i],j]
      break
print(*res)

Measured memory_bytes: 9336
mod = 10**9+7
frac = [1]*200001
for i in range(2,200001):
    frac[i] = i * frac[i-1]%mod
fraci = [None]*200001
fraci[-1] = pow(frac[-1], mod -2, mod)
for i in range(-2, -200001-1, -1):
    fraci[i] = fraci[i+1] * (200001 + i + 1) % mod
def comb(a, b):
    if not a >= b >= 0:
        return 0
    return frac[a]*fraci[b]*fraci[a-b]%mod

def count(a, b):
    (r1, c1), (r2, c2) = RC[a], RC[b]
    if c2 < c1:
        return 0
    return comb(r2-r1 + c2-c1, r2-r1)

H, W, N = map(int, input().split())

RC = [list(map(int, input().split())) for _ in range(N)] + [[1, 1], [H, W]]
RC.sort()

dp = [0]*(N+2)
dp[0] += 1

for i in range(1, N+2):
    res = count(0, i)
    for k in range(1, i):
        res = (res - count(k, i)*dp[k]) % mod
    dp[i] = res

print(dp[-1])


Measured memory_bytes: 54860
import java.util.*;
public class Main{
public static void main(String[] args) throws Exception{
    	Scanner sc = new Scanner(System.in);
     	int a,b,c;
       	a = sc.nextInt();
       	b = sc.nextInt();
       	c = sc.nextInt();
    	System.out.println(c + " " + a + " " + b);
    }
}

Measured memory_bytes: 23124
#include <bits/stdc++.h>
using namespace std;
#define pp pair<int,int>
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define ll long long
#define ld long double
#define all(a) (a).begin(),(a).end()
#define mk make_pair
ll MOD=1000000007;
ll mod=998244353;
int inf=1000001000;
ll INF=1e18+5;


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


Measured memory_bytes: 256
#include<stdio.h>
int main(){
int N[4];
int i;
int seki=1,wa=0;

for(i=0;i<4;i++){
scanf("%d",&N[i]);
}

for(i=0;i<4;i++){

seki *= N[i];
wa += N[i];
}

if(seki == 252&& wa == 21)
printf("YES\n");

else
printf("NO\n");

  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

public class Main {
	static String[][] area;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(true){
			int H = sc.nextInt();
			int W = sc.nextInt();
			if(H == 0 && W == 0) break;
			area = new String[H][W];
			for(int i = 0; i < H; i++){
				String s = sc.next();
				for(int j = 0; j < W; j++){
					area[i][j] = s.substring(j, j+1);
				}
			}
			move(0,0);
		}
	}
	
	public static void move(int x,int y){
		if(area[x][y].equals(">")){
			area[x][y] = "*";
			move(x,y+1);
		}else if(area[x][y].equals("<")){
			area[x][y] = "*";
			move(x,y-1);
		}else if(area[x][y].equals("^")){
			area[x][y] = "*";
			move(x-1,y);
		}else if(area[x][y].equals("v")){
			area[x][y] = "*";
			move(x+1,y);
		}else if(area[x][y].equals(".")){
			System.out.println(y + " " + x);
		}else if(area[x][y].equals("*")){
			System.out.println("LOOP");
		}else{
			System.out.println(area[x][y]);
			System.err.println("error");
		}
	}
}

Measured memory_bytes: 24672
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define rep(N) for (int i = 0; i < N; ++i)
#define Rep(a, b) for (int i = a; i < b; ++i)
#define For(i, N) for (int i = 0; i < N; ++i)
#define all(v) v.begin(), v.end()
#define rev(v) v.rbegin(), v.rend()
#define makei(N) int N; cin >> N;
#define makel(N) ll N; cin >> N;
#define makes(s) string s; cin >> s;
#define maked(d) double d; cin >> d;
#define makev(v, N) vi v(N); rep(N)cin >> v[i];
#define mod 1000000007
#define re return 0
#define distance(x1,y1,x2,y2) sqrt((x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));

using namespace std;
using ll = long long int;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pii = pair<int, int>;
using pis = pair<int, string>;
using msi = map<string, int>;

template<typename T>
void say(T s) {
	cout << s << "\n";
}

template<typename T>
void say(vector<T> s) {
	auto itr = s.begin();
	cout << *(itr++);
	while (itr != s.end()) {
		cout << " " << *(itr++);
	}
	cout << "\n";
}

void yn(bool b) {
	if (b)say("Yes");
	else say("No");
}

template<typename T>
void maxi(T &a, T b) {
	a = max(a, b);
}

template<typename T>
void mini(T &a, T b) {
	a = min(a, b);
}

int main() {
	makei(a);
	makei(b);
	if (a + b == 15)say("+");
	else if (a*b == 15)say("*");
	else say("x");
}

Measured memory_bytes: 256
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7

s = input()
ans=1000
for i in range(len(s)-2):
    ans = min(ans,abs(int(s[i:i+3])-753))

print(ans)

Measured memory_bytes: 3060
N, M = map(int, input().split())
A = [input() for _ in range(N)]
B = "".join([input() for _ in range(M)])

Z = N - M + 1
ans = [["".join(A[i+k][j:j+M] for k in range(M)) == B for i in range(Z)] for j in range(Z)]
for b in ans:
    if True in b:
        print("Yes")
        break
else:
    print("No")


Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
int main(void){
    string n;
    cin >> n;
    if (n.at(0) == '7'||n.at(1) == '7'||n.at(2) == '7') {
        printf("Yes\n");
    }
    else{
        printf("No\n");
    }
}

Measured memory_bytes: 3588
#![allow(unused, non_snake_case, dead_code, non_upper_case_globals)]
use {
    proconio::{marker::*, *},
    std::{cmp::*, collections::*, mem::*},
};

#[fastout]
fn main() {
    input! {//
        l:i64,
        r:i64,d:i64
    }
    println!("{}", r / d - (l - 1) / d);
}


Measured memory_bytes: 2064
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 line = br.readLine();
        String split[] = line.split(" ", 0);
        int sort[] = new int[3];
        int temp;

        sort[0] = Integer.parseInt(split[0]);
        sort[1] = Integer.parseInt(split[1]);
        sort[2] = Integer.parseInt(split[2]);

        for (int j = 0; j < 3; j++) {
            for (int i = 1; i < 3; i++) {
                if (sort[i - 1] > sort[i]) {
                    temp = sort[i - 1];
                    sort[i - 1] = sort[i];
                    sort[i] = temp;
                }
            }
        }

        System.out.println(sort[0] + " " + sort[1] + " " + sort[2]);
    }
}

Measured memory_bytes: 16956
#include <cstdio>

using namespace std;

char s[500][501];
char s1[500][501];
char s2[500][501];

int main() {
    int h, w, i, j;
    
    scanf("%d %d", &h, &w);
    
    for (i = 0; i < h; i++) scanf("%s", s[i]);
    
    for (i = 0; i < h; i++) {
        for (j = 0; j < w; j++) {
            s1[i][j] = s2[i][j] = '.';
            
            if (s[i][j] == '#') {
                s1[i][j] = s2[i][j] = '#';
            } else if (i == 0) {
                s1[i][j] = '#';
            } else if (i == h - 1) {
                s2[i][j] = '#';
            } else if (j % 2 == 0) {
                s1[i][j] = '#';
            } else {
                s2[i][j] = '#';
            }
        }
        
        s1[i][j] = s2[i][j] = '\0';
    }
    
    for (i = 0; i < h; i++) printf("%s\n", s1[i]);
    puts("");
    for (i = 0; i < h; i++) printf("%s\n", s2[i]);
    
    return 0;
}


Measured memory_bytes: 1408
class T:
	def __init__(self, h, w):
		self.h = h
		self.w = w
		self.d = w*w + h*h
	def __lt__(self, other):
		return (self.d < other.d) or ((self.d == other.d) and self.h < other.h)
	def __gt__(self, other):
		return (self.d > other.d) or ((self.d == other.d) and self.h > other.h)

t = []
for i in range(1, 151):
	for j in range(i+1, 151):
		t.append(T(i, j))
t = sorted(t)

while True:
	h, w = map(int, input().split())
	if (h, w) == (0, 0):
		break
	hw = T(h, w)
	for i in range(len(t)):
		if hw < t[i]:
			print('{} {}'.format(t[i].h, t[i].w))
			break

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

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)
#define FORR(i, m, n) for(int i = m;i >= n;i--)
#define SORT(v, n) sort(v, v+n);
#define VSORT(v) sort(v.begin(), v.end());
#define llong long long
#define pb(a) push_back(a)

#define INF 100000000
#define MOD 1000000007
#define writeln(n) cout<<n<<endl
//setprecision(10);
using namespace std;
typedef pair<int, int> P;
typedef pair<llong, llong> LP;
typedef pair<int, P> PP;
typedef pair<llong, LP> LPP;
//vector<tuple<long long, long long, long long>>vec;

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

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

llong pownew(llong m, llong n) {
    if (n == 0) { return 1; }
    if (n % 2 == 0) { return pow(m*m, n/2); }
    return pow(m, n-1) * m;
}

bool isprime(int p) {
    if (p == 1) return false;
    for (int i = 2; i < p; i++) {
        if (p%i == 0) return false;
    }
    return true;
}

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

const int inf=100000000;

long long modpow(long long a, long long n, long long mod)
{
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

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


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n; cin>>n;
    string s; cin>>s;
    llong ans=1;
    llong mod=1000000007;
    vector<int> cnt(26,0);
    for(int i=0; i<n; i++)
    {
        cnt[s[i]-'a']++;
    }
    for(int i=0; i<26; i++)
    {
        ans=ans*(cnt[i]+1)%mod;
    }
    cout<<ans-1<<endl;
    return  0;
}


Measured memory_bytes: 512
#include<bits/stdc++.h>
//#include<iostream>
//#include<cstdio>
//#include<stdlib.h>
//#include<string.h>
//#include<algorithm>
using namespace std;
#define SPEED ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define READ freopen("in.txt","r",stdin)
#define WRITE freopen("out.txt","w",stdout);
#define pb push_back
#define mem(arr,val) memset(arr,val,sizeof(arr))
#define sf(x) scanf("%d",&x)
#define sf2(x,y) scanf("%d %d",&x,&y)
#define sf3(x,y,z) scanf("%d %d %d",&x,&y,&z)
#define sl(x) scanf("%lld",&x)
#define sl2(x,y) scanf("%lld %lld",&x,&y)

#define sl3(x,y,z) scanf("%lld %lld %lld",&x,&y,&z)
#define sd(x) scanf("%lf",&x);
#define pLL pair<long long,long long>
#define pDB pair<double,double>
#define ff first
#define sn second
#define PRINT_CASE  printf("Case %d: ",tc++)
#define PRINT_CASENL  printf("Case %d:\n",tc++)
//#define mx 100005
#define lnd tree[ind<<1]
#define rnd tree[(ind<<1)+1]
#define cnd tree[ind]
#define lndp b,(b+e)>>1,(ind<<1)
#define rndp ((b+e)>>1)+1,e,(ind<<1)+1
#define IN(a,x,y) (a>=x && a<=y)
#define popcountL __builtin_popcountll
#define popcount __builtin_popcount
/// int other=mask^((1<<n)-1);
typedef long long ll;
typedef long long int lln;
typedef pair<int,int> pii;
ll INF=1<<28;
//typedef long long lld;
const double PI=acos(-1.0);
//int fx[]={1,-1,0,0}; //direction array
//int fy[]={0,0,1,-1};
int dir[4][2]={1,0,-1,0,0,-1,0,1};
int knight[8][2]={1,2,1,-2,2,1,2,-1,-1,2,-1,-2,-2,1,-2,-1};
const long double EPS=1e-7;
//#define INF 10000

struct compare
{
  bool operator()(const pair<int,pii>& l, const pair<int,pii>& r)
  {
      if(l.ff==r.ff)
      {
          return l.sn.ff>r.sn.ff;
      }
      return l.ff<r.ff;
  }
};
// bool operator<(pair<int,pii> l, pair<int,pii> r)
//  {
//      if(l.ff==r.ff)
//      {
//          cout<<"ok "<<endl;
//          return l.sn.ff<r.sn.ff;
//      }
//      return l.ff>r.ff;
//  }

/////////////////////////////////////template sesh/////////////////////////////////////////////////////

///code goes from here
const int mx=300150;
///
int mod=1000000007;


int main()
{
//    SPEED;
//    mem(dp,-1);
    int t,tc=1;
//    sf(t);
    t=1;

    while(t--)
    {
        ll k;
        ll num=7;
        sl(k);
        int ans=-1;
        num%=k;
        for(int i=1;i<=3000000;i++)
        {
            if(num==0)
            {
                ans=i;
                break;
            }
            num*=10;
            num%=k;
            num+=7;
            num%=k;
        }
        cout<<ans<<endl;
    }


    return 0;
}



Measured memory_bytes: 3680
#include <iostream>

using namespace std;

int main()
{
    int t;

    cin >> t;
    while (t--) {
        int X, Y, W, H, x, y, n, ans = 0;

        cin >> X >> Y >> W >> H >> n;
        for (int i = 0; i < n; ++i) {
            cin >> x >> y;

            if (X <= x && x <= X + W && Y <= y && y <= Y + H)
                ++ans;
        }

        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 1160
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
  int N;
  cin>>N;
  for(int h=1;h<=3500;h++)
    for(int n=1;n<=3500;n++)
      if((4*h*n-N*h-N*n)>0 && N*h*n%(4*h*n-N*h-N*n)==0){
        cout<<h<<' '<<n<<' '<<N*h*n/(4*h*n-N*h-N*n)<<endl;
        return 0;
      }
}

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

signed main(void)
{
	int n, j;
	long long ans, sum;

	cin >> n;
	vector<int> a(3 * n);
	rep(i, 3 * n) cin >> a[i];
	sort(a.rbegin(), a.rend());
	ans = sum = 0;
	for(int i = n; i < n + n; i++)
	{
		ans += a[i];
	}
	j = 1;
	rep(i, n)
	{
		sum += a[j];
		j+=2;
	}
	ans = max(ans, sum);
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1408
package main

import "fmt"

func main(){
	var num string
	fmt.Scan(&num)
	nl := []rune(num)
	reverseNum := ""
	for _, element := range nl {
		if element == '1' { reverseNum += "9"}
		if element == '9' { reverseNum += "1" }
	}
	fmt.Printf(reverseNum)
}


Measured memory_bytes: 512
n, m = map(int, input().split())
apple = list(map(int, input().split()))
orange = []
count = 0
if n >= m:
    count = 1
else:
    apple = sorted(apple)
    for i in range(m-1):
        orange.append(apple[i+1] - apple[i])
orange = sorted(orange)

if count == 0:
    if len(orange) != 1:
        if n != 1:
            print(sum(orange[:-(n-1)]))
        else:
            print(sum(orange))
    else:
        print(orange[0])
else:
    print(0)

Measured memory_bytes: 20452
N = int(input())
a = list(map(int, input().split()))
num = float('inf')
for k in [0, 1]:
    s = 0
    tmp = 0
    for i in range(N):
        s += a[i]
        if i % 2 == k:
            if s <= 0:
                tmp += abs(s) + 1
                s = 1
        else:
            if s >= 0:
                tmp += abs(s) + 1
                s = -1
    num = min(tmp, num)

print(num)

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

int main(void)
{
	int a, b;
	string c, d;
	cin >> a >> b;

	rep(i, b) c += to_string(a);
	rep(i, a) d += to_string(b);
	cout << min(c, d) << endl;
	return 0;
}


Measured memory_bytes: 256
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

s,c=map(int,input().split())
if 2*s>=c:
    print(c//2)
else:
    print(s+(c-2*s)//4)

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

namespace A
{
    class Program
    {
        static void Main(string[] args)
        {
            string line = Console.ReadLine();
            int K = int.Parse(line);
            line = Console.ReadLine();
            string[] strs = line.Split(' ');
            int A = int.Parse(strs[0]);
            int B = int.Parse(strs[1]);
            for(int i = A; i <= B; i++)
            {
                if (i % K == 0)
                {
                    Console.WriteLine("OK");
                    return;
                }
            }

            Console.WriteLine("NG");
        }
    }
}


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

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

Node *root, *NIL;

Node * find(Node *u, int k) {
  while ( u != NIL && k != u->key ) {
    if ( k < u-> key ) u = u->left;
    else u = u->right;
  }
  return u;
}

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[0] == 'f' ) {
      scanf("%d", &x);
      Node *t = find(root, x);
      if ( t != NIL ) printf("yes\n");
      else printf("no\n");
    } else 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: 22068
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> ii;

int main() {
	int n; cin >> n;
	cout.precision(20);
	if (n % 2 == 0) cout << 1.0 / 2 << endl;
	else {
		int m = (n + 1) / 2;
		cout << 1.0*m / n << endl;
	}
}

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

const int nm = 1e3;
int n, m;
long long x, v[8][nm], sum, ans = -3e13;

int main() {
	cin >> n >> m;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++) {
			cin >> x;
			for (int k = 0; k < 8; k++)
				v[k][i] += 1 << j & k ? x : -x;
		}
	for (int i = 0; i < 8; i++) {
		sort(v[i], v[i] + n, greater<long long>());
		sum = 0;
		for (int j = 0; j < m; j++)
			sum += v[i][j];
		ans = max(ans, sum);
	}
	cout << ans << endl;
}


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

using namespace std;

int main() {

	int n, x, mini = 1e9, maxi = -1e9;

	scanf("%d", &n);

	for (int i=0; i<n; ++i) {
		scanf("%d", &x);

		if (x > maxi)
			maxi = x;
		if (x < mini)
			mini = x;
	}

	printf("%d\n", maxi - mini);

	return 0;
}

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

int main() {
	int k, x;
	cin >> k >> x;

	for (int i = x - k + 1; i < x + k; i++) {
		if (i != x - k + 1) {
			cout << " ";
		}
		cout << i;
		
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
N, M, X = map(int, input().split())
p = []
c = []
for i in range(N):
    new = [int(j) for j in input().split()]
    p.append(new[0])
    c.append(new[1:])
    
flag = 0
total = [0]*M
for i in range(N):
    for j in range(M):
        total[j] += c[i][j]

for j in range(M):
    if total[j] < X:
        flag = 1
        
if flag == 1:
    print(-1)
else:
    minimum = sum(p)
    for k in range(2**N):
        total = [0]*M
        total_p = 0
        for i in range(N):
            if ((k >> i) & 1):
                total_p += p[i]           
                for j in range(M):
                    total[j] += c[i][j]
            flag2 = 0
            for j in range(M):
                if total[j] < X:
                    flag2 = 1
            if flag2==0:
                if total_p < minimum:
                    #print(total, total_p)
                    minimum=total_p
    print(minimum)
                
    

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

int main(){
	int n,hundo[10],a,i;
	
	while(0<=scanf("%d",&a)){
		i=0;
	if(a==0){
		printf("\n");
		continue;
	}
		for(n=0;n<10;n++){
			hundo[n]=0;
		}
		
	for(n=9;0<=n;n--){
	if(pow(2,(double)n)<=a){
		a=a-pow(2,(double)n);
		hundo[n]=1;
			i++;
	}
	}
	
	for(n=0;n<10;n++){
		if(hundo[n]==1 && i>1){
			printf("%.0lf ",pow(2,(double)n));
			i--;
		}
			
	}
		
		for(n=10;;n--){
			if(hundo[n]==1){
				printf("%.0lf\n",pow(2,(double)n));
				break;
			}
		}
		
	}
	return 0;
	}

Measured memory_bytes: 0
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
struct team{
  int id,score,time,wrong[11];
  bool operator<(const team& a) const{
    return score == a.score ? (time == a.time ? id > a.id : time < a.time ) : score > a.score;
  }
};
int main(){
  int m,t,p,r,i,j,k;
  cin >> m >> t >> p >> r;
  while(m!=0){
    vector <team> teams;
    team te;
    for(j=0;j<11;j++) te.wrong[j]=0;
    te.score=0;
    te.time=0;
    for(i=1;i<=t;i++){
      te.id=i;
      teams.push_back(te);
    }
    int a,b,c,d;
    for(i=0;i<r;i++){
      cin >> a >> b >> c >> d;
      if(d==0){
	teams[b-1].score++;
	teams[b-1].time+=a+20*teams[b-1].wrong[c];
      }else{
	teams[b-1].wrong[c]++;
      }
    }
    sort(teams.begin(),teams.end());
    for(i=0;i<t;i++){
      if(i>0){
	if(teams[i-1].score==teams[i].score&&teams[i-1].time==teams[i].time) cout << "=";
	else cout << ",";
      }
      cout << teams[i].id;
    }
    cout << endl;
    cin >> m >> t >> p >> r;
  }
  return 0;
}

Measured memory_bytes: 1224
#include <iostream>
#include <unordered_map>
#include <utility>

using namespace std;

pair<int, int> get_max_element(unordered_map<int,int>& umap, int key_except=-1)
{
  int max_key = 0;
  int max_count = 0;
  for (auto& kv : umap) {
    const int& key = kv.first;
    const int& count = kv.second;

    if (count > max_count && key != key_except) {
      max_key = key;
      max_count = count;
    }
  }

  return make_pair(max_key, max_count);
}

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

  int count_even = (N+1)/2, count_odd = N/2;

  unordered_map<int,int> umap_even, umap_odd;

  for (int n=0; n<N; ++n) {
    auto& umap = n%2 ? umap_odd : umap_even;
    int v;
    cin >> v;
    if (umap.count(v)==0)
      umap.emplace(v,1);
    else
      umap.at(v)++;
  }

  auto kv_even = get_max_element(umap_even);
  auto kv_odd = get_max_element(umap_odd);
  int max_key_even, max_count_even;
  int max_key_odd, max_count_odd;
  max_key_even = kv_even.first;
  max_count_even = kv_even.second;
  max_key_odd = kv_odd.first;
  max_count_odd = kv_odd.second;

  int ops;
  if (max_key_even != max_key_odd) {
    ops = (count_even - max_count_even) + (count_odd - max_count_odd);
  } else {    
    auto kv_even2 = get_max_element(umap_even,max_key_even);
    int second_max_count_even = kv_even2.second;

    auto kv_odd2 = get_max_element(umap_odd,max_key_odd);
    int second_max_count_odd = kv_odd2.second;

    ops = min((count_even - second_max_count_even) + (count_odd - max_count_odd),
	      (count_even - max_count_even) + (count_odd - second_max_count_odd));
  }

  cout << ops << endl;
  
  return 0;
}


Measured memory_bytes: 4376
#include"bits/stdc++.h"
using namespace std;

int main() {
	vector<int> vec(100);
	int n;
	cin >> n;
	for (int i = 0; i < n ; i++) {
		cin >> vec.at(i);
	}

	sort(vec.begin(), vec.end());
	reverse(vec.begin(), vec.end());
	int alice=0, bob=0;
	for (int i = 0; i < n; i++) {
		if (i % 2 == 0) {
			alice += vec.at(i);
		}
		else {
			bob += vec.at(i);
		}
	}
	cout << alice - bob;

}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll MOD=(ll)1e9+7;
const ll MOD2=(ll)998244353;
const ll INF=(ll)1e18+10;
const double PI = 2.0*acos(0);

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 (a>b) { a=b; return 1; } return 0; }
int dy[]={-1,1,0,0};
int dx[]={0,0,-1,1};

void solve(int ca){
    ll X; cin>>X;
    ll a=100;
    for (int i = 1; i < 1e6; ++i) {
        a=(double)a*1.01;
        if(a>=X){
            cout<<i<<endl;
            return;
        }
    }
}

//#define MULTI
int main() {
#ifdef MULTI
    int N; cin>>N;
    for (int i = 0; i < N; ++i) {
        solve(i+1);
    }
#else
    solve(0);
#endif
    return 0;
}


Measured memory_bytes: 3636
/*~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=
*$* WRITER:kakitamasziru/OxOmisosiru *$*
~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=~=*/
#ifdef LOCAL_JUDGE
#define _GLIBCXX_DEBUG //FOR THE DEBUG! COMMENT OUT THIS WHEN SUBMITTING!
#endif
/* I REALLY HOPE MY WISH REACH YOU , ATCODER'S ONLINE JUDGE */
#define WOULD
#define YOU
#define PLEASE
#define ACCEPT
#define MY
#define SUBMISSION
/* I REALLY HOPE MY WISH REACH YOU , ATCODER'S ONLINE JUDGE */
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <iomanip>
#include <limits>//setprecision
//#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
//#include <unordered_set> //unordered_set
#include <stack> // stack
#include <deque> // deque
#include <math.h>//pow,,,
#include <cmath>//abs,,,
#include <bitset> // bitset
//It is so troublesome that I include bits/stdc++.h !
using namespace std;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
const long long INF = 100100100100;
const long long MOD = 1000000007;
typedef pair<int,int> P;

//Solve N^M. This, mod_pow use Iterative Square Method.
long long mod_pow(long long N, long long M) {
    if (M == 0) return 1;
    long long res = mod_pow((N * N) % MOD, M / 2);
    //最下位ビット(*N)が1の時は単独でNをかける
    if (M & 1) res = (res * N) % MOD;

    return res %= MOD;
}

long long gcd(long long a, long long b) {
    if (b == 0) return a;
    else return gcd(b, a % b);
}
long long lcm(long long a, long long b) {
    return a * b / gcd(a, b);
}

int main() {
    string S;cin >> S;
    int N = S.size();
    for(int i = 1;i<=N;i++){
        S.pop_back();
        if(S.size() % 2 != 0) continue;
        string T = S.substr(0,(N-i)/2);
        string R = S.substr((N-i)/2,(N-i)/2);
        if(T == R){
            cout << T.size()*2 << endl;
            return 0;
        }
    }
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define mymalloc(p,n) {p=malloc((n)*sizeof(*p));if((p)==NULL){printf("not enough memory\n");exit(1);};}

void print_array(int N, int *array){
    int i;
    for(i=0;i<N;i++){
        printf("%d", array[i]);
        if(i<N-1){printf(" ");}
    }
    printf("\n");
}
void printLn_array(int N, int *array){
    int i;
    for(i=0;i<N;i++){
        printf("%d\n", array[i]);
    }
}

int *readArray(int *num){
	int i,j;
	int *A;
	scanf("%d", num);
	mymalloc(A,*num);
	for(i=0;i<*num;i++){
		scanf("%d",&j);
		A[i]=j;
	}
	return A;
}

void insertSort(int N, int *array, int g, int *cnt){
    int i,j,key;
    for(i=g;i<N;i++){
        key=array[i];
        j=i-g;
        while(j>=0 && array[j]>key){
            array[j+g]=array[j];
            j-=g;
            (*cnt)++;
        }
        array[j+g]=key;
    }
}

	
main(){
    int i,j,n,cnt,m;
    int *A;
    int *G;
    cnt=0;
    A=readArray(&n);
    m=(int)(log(2*n+1)/log(3));
    mymalloc(G,m);
		for(i=0;i<m;i++){
			G[i]=0.5*(pow(3,m-i)-1);
		}
		for(i=0;i<m;i++){
			insertSort(n,A,G[i],&cnt);
		}
		printf("%d\n",m);
		print_array(m,G);
		printf("%d\n",cnt);
		printLn_array(n,A);
    return 0;
}

Measured memory_bytes: 4572
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <iterator>
#include <numeric>
#include <bitset>
#include <cassert>
#include <functional>

using namespace std;
using Graph = vector<vector<int>>;
typedef long long ll;
typedef pair<ll, ll> P;
inline ll min(ll x, ll y) { return x < y ? x : y; }
inline ll max(ll x, ll y) { return x > y ? x : y; }

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#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 all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << (x) << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define endl "\n"
const int MOD=1e9+7;
#ifndef HOME
#define cerr if(0)cerr
#endif

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    int a[m];
    set<int>s;
    for(int i=0;i<m;i++){
        cin>>a[i];
        s.insert(a[i]);
    }
    int dp[n+5];
    dp[0]=0;
    dp[1]=1;
    dp[2]=2;
    if(s.find(1)!=s.end()){
        //cerr<<1<<endl;
        dp[1]=0;
        dp[2]=1;
    }
    if(s.find(2)!=s.end()){
        dp[2]=0;
    }
    for(int i=3;i<=n;i++){
        if(s.find(i)!=s.end()){
            dp[i]=0;
        }else{
            dp[i]=(dp[i-1]+dp[i-2])%MOD;
        }
    }
    cout<<dp[n]%MOD<<endl;
    return 0;
    
}



Measured memory_bytes: 6528
import java.util.*;
import java.io.*;
import java.text.*;
import java.math.*;
import static java.lang.Integer.*;
import static java.lang.Double.*;
import java.lang.Math.*;

public class Main {

	public static void main(String[] args) throws Exception {
		new Main().run();
	}

	public void run() throws Exception {
		FastIO file = new FastIO();
		int a = file.nextInt();
		int b = file.nextInt();
		int c = 1;
		int d = 0;
		while (c < b) {
			c += a - 1;
			d++;
		}
		System.out.println(d);
	}

	public static class FastIO {
		BufferedReader br;
		StringTokenizer st;

		public FastIO() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	public static long pow(long n, long p, long mod) {
		if (p == 0)
			return 1;
		if (p == 1)
			return n % mod;
		if (p % 2 == 0) {
			long temp = pow(n, p / 2, mod);
			return (temp * temp) % mod;
		} else {
			long temp = pow(n, (p - 1) / 2, mod);
			temp = (temp * temp) % mod;
			return (temp * n) % mod;

		}
	}

	public static long pow(long n, long p) {
		if (p == 0)
			return 1;
		if (p == 1)
			return n;
		if (p % 2 == 0) {
			long temp = pow(n, p / 2);
			return (temp * temp);
		} else {
			long temp = pow(n, (p - 1) / 2);
			temp = (temp * temp);
			return (temp * n);

		}
	}

	public static long gcd(long x, long y) {
		if (x == 0)
			return y;
		else
			return gcd(y % x, x);
	}

	public static boolean isPrime(int n) {
		if (n <= 1)
			return false;
		if (n <= 3)
			return true;

		if (n % 2 == 0 || n % 3 == 0)
			return false;

		for (int i = 5; i * i <= n; i = i + 6)
			if (n % i == 0 || n % (i + 2) == 0)
				return false;

		return true;
	}
}
 

Measured memory_bytes: 21332
/*
このコード、と～おれ!
Be accepted!
∧＿∧　
（｡･ω･｡)つ━☆・*。
⊂　　 ノ 　　　・゜+.
　しーＪ　　　°。+ *´¨)
 　　　　　　　　　.· ´¸.·*´¨) ¸.·*¨)
		  　　　　　　　　　　(¸.·´ (¸.·'* ☆
					*/

#include <stdio.h>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstring>
#include <vector>
#include <numeric>
#include <iostream>
#include <random>
#include <map>
#include <unordered_map>
#include <queue>
#include <regex>

#pragma GCC optimize("Ofast")
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define rep1(i, n) for(int i = 1; i <= (n); ++i)
#define rep2(i, n) for(int i = 2; i < (n); ++i)
#define repr(i, n) for(int i = n; i >= 0; --i)
#define reprm(i, n) for(int i = n - 1; i >= 0; --i)
#define printynl(a) printf(a ? "yes\n" : "no\n")
#define printyn(a) printf(a ? "Yes\n" : "No\n")
#define printYN(a) printf(a ? "YES\n" : "NO\n")
#define printin(a) printf(a ? "possible\n" : "inposible\n")
#define printdb(a) printf("%.50lf\n", a)//少数出力
#define printdbd(a) printf("%.16lf\n", a)//少数出力(桁少なめ)
#define prints(s) printf("%s\n", s.c_str())//string出力
#define all(x) (x).begin(), (x).end()
#define allsum(a, b, c) ((a + b) * c / 2)//等差数列の和、初項,末項,項数
#define pb push_back
#define priq priority_queue
#define rpriq priq<int, vector<int>, greater<int>>
#define deg_to_rad(deg) (((deg)/360.0)*2.0*PI)
#define rad_to_deg(rad) (((rad)/2.0/PI)*360.0)
#define Please return
#define AC 0

using ll = long long;

constexpr int INF = 1073741823;
constexpr int MINF = -1073741823;
constexpr ll LINF = ll(4661686018427387903);
constexpr ll MOD = 1000000007;
const double PI = acos(-1);

using namespace std;

void scans(string& str) {
	char c;
	str = "";
	scanf("%c", &c);
	if (c == '\n')scanf("%c", &c);//最初の改行対策
	while (c != '\n' && c != -1) {
		str += c;
		scanf("%c", &c);
	}
}

void scanc(char& str) {
	char c;
	scanf("%c", &c);
	if (c == -1)return;
	while (c == '\n') {
		scanf("%c", &c);
	}
	str = c;
}

double acot(double x) {
	return PI / 2 - atan(x);
}

/*-----------------------------------------ここからコード-----------------------------------------*/


int main() {
	
	int n, k, l;
	scanf("%d%d%d", &n, &k, &l);
	printf("%d\n", max({n, k, l}) * 10 + n + k + l - max({n, k, l}));
	
	Please AC;
}


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

using namespace std;
typedef long long ll;
const int MAXN=2005,MOD=1e9+7;
int n,k,fac[MAXN*MAXN],inv[MAXN*MAXN],dp[MAXN][MAXN];

ll quick_pow(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1,a=a*a%MOD)
		if(b&1) ret=ret*a%MOD;
	return ret;
}
ll C(int a,int b)
{if(a<b) return 0;return 1ll*fac[a]*inv[a-b]%MOD*inv[b]%MOD;}

int main()
{
	scanf("%d%d",&n,&k);
	if(k==1) return puts("1"),0;
	fac[0]=dp[0][0]=1;
	for(int i=1;i<=n*k;i++) fac[i]=1ll*fac[i-1]*i%MOD;
	inv[n*k]=quick_pow(fac[n*k],MOD-2);
	for(int i=n*k-1;i>=0;i--) inv[i]=1ll*inv[i+1]*(i+1)%MOD;
	
	for(int i=0;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(j<=i) dp[i][j]=dp[i-1][j];
			else dp[i][j]=(dp[i][j-1]*C(i+(k-1)*j-1,k-2)%MOD+dp[max(0,i-1)][j])%MOD;
	
	ll res=1ll*dp[n][n]*fac[n]%MOD;
	printf("%lld",res);
	return 0;
}

Measured memory_bytes: 47360
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<pair<int, int>> X[1000];
int dist[1000];
int main() {
	int n, m, a, b, c;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> a >> b >> c;
		X[a].push_back(make_pair(b, c));
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < X[j].size(); k++) {
				dist[X[j][k].first] = max(dist[X[j][k].first], dist[j] + X[j][k].second);
			}
		}
	}
	cout << dist[n - 1] << endl;
	return 0;
}

Measured memory_bytes: 3148
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cassert>
#include <complex>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <numeric>
#include <sstream>
#include <ctime>
#include <cctype>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <deque>
#include <stack>
#include <memory.h>
using namespace std;
#define ll long long
#define mp make_pair
ll a,b,c; 
int main()
{
	cin>>a>>b>>c;
	if((a+b)>=c){
		cout<<"Yes";
	}
	else{
		cout<<"No";
	}
    return 0;
}


Measured memory_bytes: 256
import math
N, D = map(int, input().split())
x = []
for i in range(N):
  t = list(map(int, input().split()))
  x.append(t)

ans = 0
for i in range(N):
  for j in range(i+1, N):
    d = 0
    for k in range(D):
      d += (x[i][k] - x[j][k]) ** 2
    if round(math.sqrt(d)) ** 2 == d:
      ans += 1
print(ans)

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<queue>

using namespace std;

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

int main(){
    int n, m;
    cin >> n >> m;
    long int a[n];
    rep(i, n) cin >> a[i];
    priority_queue<long int> q;
    rep(i, n) q.push(a[i]);
    rep(i, m){
        int g = q.top();
        q.pop();
        g /= 2;
        q.push(g);

    }
    long int ans = 0;
    rep(i, n){
        ans += q.top();
        q.pop();
    }
    cout << ans << endl;
}

Measured memory_bytes: 2168
//FIRST THINK THEN CODE.

#include <bits/stdc++.h>
 
 
using namespace std;
 
typedef long long ll;
 
//#define MOD 998244353
#define rep(i,a,b) for(ll i=a;i<b;++i)
#define rrep(i,a,b) for(ll i=a;i>b;--i)
#define FOR(i,n)  for(ll i=0;i<n;i++)
#define vi vector<int>
#define vl vector<ll>
#define ld long double
#define vvi vector<vector<int>>
#define vvl vector<vector<long long>>
#define pii pair<int,int>
#define pll pair<long,long>
#define vpii vector<pii>
#define vpll vector<pll>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define bs binary_search
#define d1(x) cout<<(x)<<endl
#define d2(x,y) cout<<(x)<<" "<<(y)<<endl
#define d3(x,y,z) cout<<(x)<<" "<<(y)<<" "<<(z)<<endl
#define d4(a,b,c,d) cout<<(a)<<" "<<(b)<<" "<<(c)<<" "<<(d)<<endl
#define PI 3.1415926535897932384626433832795
#define fix(f,n) fixed<<setprecision(n)<<f
#define all(x) x.begin(),x.end()
#define rev(p) reverse(p.begin(),p.end());
#define endl "\n"
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define popcount(x) __builtin_popcountll(x)
#define sz(x) ((ll)x.size())
const int M=1000000007;
const int MM=998244353;
int begtime = clock();
#define end_routine() cout << "\n\nTime elapsed: " << (clock() - begtime)*1000/CLOCKS_PER_SEC << " ms\n\n";

 
ll newmod(ll a,ll b)
 {
  return ((a%b)+b)%b;
}
 
 
ll powM(ll a,ll b,ll m )
{ 
  if(m<=1)return 0;
  a%=m;
  ll ans=1LL;
  while(b)
  {
    if(b&1)ans=ans*a%m;
    a=a*a%m;
    b>>=1;
  }
 
return ans;
}


 
ll poww(ll a,ll b)
{ 
  
  ll ans=1;
  while(b)
  {
    if(b&1)ans=ans*a;
    a=a*a;
    b>>=1;
  }
 
return ans;

}

template<typename T,typename F>
void chmax( T &a,F b){
  if(b>a)a=b;
}

template<typename T,typename F>
void chmin( T &a,F b){
  if(b<a)a=b;
}

const ll N=5e5+5;


ll f(ll a,ll b){
  ll c=0;
  while(a||b){
    a/=10;
    b/=10;
    c++;
  }
  return c;
}


int main()
{ 

IOS;

ll n,k;

cin>>n>>k;

ll c=1;

string s;cin>>s;

for(int i=1;i<n;i++){
  if(s[i]!=s[i-1])c++;
}

ll ans=n-c;


ll y=max(0ll,c-2);

if(y&1){
  ll d=y/2+1;

ans+=2*min(d,k);
 chmin(ans,n-1);
cout<<ans;
return 0;
}

else {

ll d=y/2;
if(k>=d+1){
  ans+=2*d+1;
  chmin(ans,n-1);
  cout<<ans;
  return 0;
}
else if(k==d){
ans+=2*d;
 chmin(ans,n-1);
cout<<ans;
return 0;
}
else {
ans+=2*k;
cout<<ans;
 chmin(ans,n-1);
return 0;
}

}

//end_routine();

return 0;
 
}


Measured memory_bytes: 3728
//dragon->emperor
#include <bits/stdc++.h>

using namespace std;

/*************************************************/

#define mod 1000000007
#define mod2 998244353
const double pi = acos(-1);
#define inf (1ll<<61)-1

#define ll long long
#define ld  long double
#define floop(i,a,n) for(ll i=a;i<n;i++)
#define loopf(i,a,n) for(ll i=n-1;i>=a;i--)
#define space " "
#define TEST(t) ll t; cin>>t; while(t--)
#define r(n) ll n; cin>>n;
#define r1(a,n) ll a[n]; for(ll i=0;i<n;i++) cin>>a[i];
#define p1(a,n) for(ll i=0;i<n;i++) cout<<a[i]<<" "; cout<<endll;
#define p2(n) cout<<n<<" ";
#define p(n) cout<<n<<endll;

#define endll "\n"
#define pb push_back
#define mp make_pair
#define dec(n) fixed<<setprecision(n)
#define F first
#define S second

#define all(x) x.begin(), x.end()
#define sortall(x) sort(all(x))
#define reverseall(x) reverse(all(x))

typedef vector<ll> vl;
typedef pair<ll,ll> pll;
typedef map<ll,ll> mll;

bitset<200000>vis(0);
vector<bool> prime;

void primes(ll n)
{
    prime.resize(n+1);
    prime.assign(n+1,true);
    prime[0]=0;
    prime[1]=0;
    for(ll i=2; i*i<=n; i++)
    {
        if(prime[i])
        {
            for(ll j=(i*i); j<n; j=j+i) prime[j]=false;
        }
    }
}

void fast()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

ll gcd(ll x, ll y)
{
    if(x==0) return y;
    return gcd( y%x ,x);
}

ll powM(ll x, ll y, ll m)
{
    ll ans=1, r=1;
    x=x%m;
    while(r>0 && r<=y)
    {
        if(r & y)
        {
            ans=ans*x;
            ans=ans%m;
        }
        r=r<<1;
        x=x*x;
        x=x%m;
    }
    return ans;
}

ll powN(ll a,ll n)
{
    if(n==0) return 1;
    if(n==1) return a;
    ll u=powN(a,n/2);
    u=u*u;
    if(n%2) u=u*a;
    return u;
}

ll modinv(ll a,ll m)
{
    return powM(a,m-2,m);
}

ll ncr(ll n, ll r, ll m)
{
    if(n<r) return 0;
    if(n==r || r==0) return 1;
    if(r==1) return n;
    if(n-r<r) return ncr(n,n-r,m);
    ll a=n;
    ll b=r;
    for(ll i=1; i<r; i++)
    {
        a=(a*(n-i))%m;
        b=(b*(r-i))%m;
    }
    b=modinv(b,m);
    a=(a*b)%m;
    return a;
}

ll countbits(ll n)
{
    ll cot=0;
    while(n)
    {
        cot++;
        n >>= 1;
    }
    return cot;
}

ll check_prime(ll n)
{
    ll ans=1;
    for(ll i=2; i*i<=n; i++)
    {
        if(n%i==0) { ans=0; break;}
    }
    return ans;
}

ll SOD(ll n)
{
    ll sum=0;
    while(n>0)
    {
        sum+=n%10;
        n/=10;
    }
    return sum;
}

ll countsubstring(const string &s, ll n)
{
    ll count=0;
    string ttt="";
    for(ll i=0;i<=n;i++)
    {
        if(s.substr(i,ttt.size())==ttt) count++;
    }
    return count;
}

/*************************************************/
int main()
{    
    fast();
    ll t=1; 
    // cin>> t;
    while(t--)
    {
        ll n,k; cin>>n>>k;
        vector<ll> h(n);
        floop(i,0,n) cin>>h[i];
        vector<ll> dp(n,inf);
        dp[0]=0;
        floop(i,0,n)
        {
            floop(j,i+1,i+k+1)
            {
                if(j<n) dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]));
            }
        }
        cout<<dp[n-1]<<endll; 
    }
    return 0;
}

Measured memory_bytes: 4760
#define _USE_MATH_DEFINES

#include <iostream>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <set>
#include <utility>
#include <vector>
#include <list>
#include <algorithm>
#include <regex>
#include <cmath>
#include <map>
#include <iterator>
#include <climits>
#include <numeric>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <array>
#include <valarray>
#include <complex>
#include <random>
#include <functional>
#include <cassert>
#include <chrono>
#include <memory>

using namespace std;

#define int long long
//region TEMPLATE
////@formatter:off
#define double long double
typedef long long ll;
typedef unsigned long long ull;
template<typename T>void __read(T &a) { cin >> a; }
template<typename T, typename ... Args> void __read(T &a, Args &... args) { cin >> a;__read(args...);}
#define make(t, ...) t __VA_ARGS__; __read(__VA_ARGS__)
#define makev(a, n) VI a(n); FOR(n) cin >> a[i];
#define ALL(x) (x).begin(), (x).end()
#define RALL(x) (x).rbegin(), (x).rend()
#define FORIT(p) for(auto it = p.begin(); it != p.end(); it++)
#define FOR(b) for(signed i = 0; i <(b); i++)
#define FORE(i, l, r) for(int i = (l); i < (r); i++)
#define NFOR(i, n) for(int i = (((int) n)-1); i >= 0; i--)
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
typedef pair<int, int> PII;
typedef pair<pair<int, int>, int> PPII;
constexpr ll M7 = 1000000007ll;
constexpr ll M9 = 1000000009ll;
constexpr ll MFFT = 998244353ll;
template<class T> void outv(T &a) { for (auto &x : a) cout << x << ' '; }
static mt19937 rnd(static_cast<unsigned>(chrono::steady_clock::now().time_since_epoch().count())); // NOLINT(cert-err58-cpp)
auto __fast_io__ = (ios_base::sync_with_stdio(false), cin.tie(nullptr)); // NOLINT(cert-err58-cpp,cppcoreguidelines-interfaces-global-init)
////@formatter:on
//endregion



int32_t main() {
    make(int, n);
    makev(a, n);
    int res = 1;
    bool ok = true;
    for(int i = 0; i < n; ++i){
        if (a[i] == 0){
            res = 0;
            ok = true;
            break;
        }
        ok = ok && res <= LLONG_MAX / a[i] && res * a[i] <= 1'000'000'000'000'000'000LL;
        res *= a[i];
    }
    if (!ok) res = -1;
    cout << res;

    return 0;
}

Measured memory_bytes: 4024