akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> iint;
typedef pair<ll,ll> llll;
#define ALL(x) (x).begin(),(x).end()
const ll zero = 0;
const ll INF = 9223372036854775807; //10^18
const int inINF = 2147483647; //10^9
const ll MOD = 1000000007; //10^9+7
const ll MOD2 = 998244353;
void Yes() {printf("Yes\n");}
void No() {printf("No\n");}
void YES() {printf("YES\n");}
void NO() {printf("NO\n");}

int main(){
    ll N, K;
    cin >> N >> K;
    vector<ll> a(N);
    for (int i = 0; i < N; i++) {
        cin >> a[i]; a[i]--;
    }
    
    ll M = 1;
    while(1 <= (K>>M)) M++;
    
    vector<vector<int>> x(M, vector<int> (N));
    for (int i = 0; i < N; i++) {
        x[0][i] = a[i];
    }
    for (int m = 1; m < M; m++) {
        for (int i = 0; i < N; i++) {
            x[m][i] = x[m-1][x[m-1][i]];
        }
    }

    ll ans = 0;
    for (ll m = M-1; m >= 0; m--) {
        if(1 & (K>>m)){
            ans = x[m][ans];
        }
    }
    printf("%lld\n", ans+1);

}

Measured memory_bytes: 52392
#include <stdio.h>

int main(){
  char s[200010];
  scanf("%s",s);
  int len=strlen(s);
  int sum=0;
  for(int i=0;i<len;i++)sum+=s[i]-'0';
  if(sum%9==0){
    puts("Yes");
  }else{
      puts("No");
  }
}

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

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i,n) for(int i=0;i<n;i++)
#define repp(i,n) for(int i=1;i<=n;i++)

const ll mod = 998244353;

int xx[4] = {1,-1,0,0}, yy[4] = {0,0,1,-1};
char s[1000][1000];
int N,M,K;
int ans = 1e9;

int dist[1000][1000];

bool inbound(int y, int x){
	return x >= 1 && x <= M && y >= 1 && y <= M;
}

int main() {
	scanf("%d%d%d",&N,&M,&K);
	repp(i,N) scanf("%s", s[i]+1);
	queue<pii> q;
	repp(i,N) repp(j,M){
		dist[i][j] = 1e9;
		if( s[i][j] == 'S' ){
			dist[i][j] = 0;
			q.push({i,j});
		}
	}

	while( !q.empty() ){
		int y = q.front().Fi, x = q.front().Se;
		q.pop();
		rep(d,4){
			int ny = y + yy[d], nx = x + xx[d];
			if( !inbound(ny,nx) ) continue;
			if( s[ny][nx] == '#' ) continue;
			if( dist[ny][nx] > dist[y][x] + 1 ) {
				dist[ny][nx] = dist[y][x] + 1;
				q.push({ny,nx});
			}
		}
	}

	repp(i,N) repp(j,M){
		if( dist[i][j] > K ) continue;
		ans = min(ans, (i-1+K-1)/K);
		ans = min(ans, (j-1+K-1)/K);
		ans = min(ans, (N-i+K-1)/K);
		ans = min(ans, (M-j+K-1)/K);
	}
	printf("%d\n",ans+1);

}


Measured memory_bytes: 4992
import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)

def main():
    N = int(input())
    repn = [[] for _ in range(N)]
    for i in range(N - 1):
        a, b = map(int, input().split())
        repn[a - 1].append((b - 1, i))
        repn[b - 1].append((a - 1, i)) # (to, id)
    M = int(input())

    """
    一般に頂点vと頂点tvの間の辺を出力する再帰関数dfsを用意する。
    頂点vからdfsしたとして、頂点tvにたどり着いたところから再帰がスタート。
    まず辺を格納するedgesを空にして、dfs(e[0], tv, v)が成り立つなら
    v-...-e-tvのパスが確定しているのでeとtvを繋ぐパスe[1]をedgeに加える。
    これを順に再帰で繰り返す。
    """
    edges = []
    def dfs(v, tv, p=-1):
        if v == tv:
            edges[:] = []
            return True
        for e in repn[v]:
            if e[0] == p:
                continue
            if dfs(e[0], tv, v):
                edges.append(e[1])
                return True
        return False

    """
    M個の各条件に対してパスの情報を記録するのにはビットを用いると良い。
    具体的にはedgesetと言うM個の整数配列を用意して、i番目のクエリに対して
    uiとviを繋ぐ辺が[ej1,ej2,...,ejk]だったとすると、これはedgeset[i]の
    j1,j2,...,jk番目のビットを立てて保持しておく。
    　→　あとで包除原理する際に楽。
    """

    edgeset = [0] * M
    for i in range(M):
        u, v = map(int, input().split())
        dfs(u - 1, v - 1)
        for id in edges:
            edgeset[i] |= 1 << id

    """
    ここから包除原理。M個の条件のうちどの条件だけを考慮するかは(1 << M)通りの選択があることに注意。
    """

    ans = 0
    for i in range(1 << M):
        mask = 0
        for j in range(M):
            if (i >> j) & 1:
                mask |= edgeset[j]
        white = bin(mask).count("1")
        val = 1 << (N - 1 - white)
        if bin(i).count("1") % 2 == 0:
            ans += val
        else:
            ans -= val
    print(ans)

if __name__ == "__main__":
    main()


Measured memory_bytes: 43804
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
template<typename T> bool chmax(T &a,T b){if(a<b){a=b;return true;}return false;}
template<typename T> bool chmin(T &a,T b){if(a>b){a=b;return true;}return false;}
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define all(vec) vec.begin(),vec.end()
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int,int> pii;
typedef tuple<ll,ll,ll> tlll;
typedef tuple<int,int,int> tiii;
const ll mod=1e9+7;
const ll inf=1ll<<60;

int main(){
  ll ans=inf;
  int n,m,x; cin >> n >> m >> x;
  vector<ll> c(n);
  vector<vector<ll> > a(n,vector<ll>(m));
  rep(i,n){
    cin >> c[i];
    rep(j,m) cin >> a[i][j];
  }
  rep(i,(1ll<<n)){
    vector<ll> b(n,0);
    ll sum=0;
    rep(j,n){
      if(i&(1ll<<j)){
        sum+=c[j];
        rep(k,m){
          b[k]+=a[j][k];
        }
      }
    }
    bool f=1;
    rep(k,m){
      if(b[k]<x) f=0;
    }
    if(f) chmin(ans,sum);
  }
  if(ans!=inf) cout << ans << endl;
  else cout << -1 << endl;
}

Measured memory_bytes: 3640
object Main {
  def main(args: Array[String]): Unit = {
    for(line <- io.Source.stdin.getLines() if line != "0 0") {
      val H = line.split(" ")(0).toInt
      val W = line.split(" ")(1).toInt

      for (i <- 0 until H) {
        if (i == 0 || i == H - 1) {
          println("#" * W)
        }
        else {
          println("#" + ("." * (W - 2) +"#"))
        }
      }
      println()
    }
  }
}

Measured memory_bytes: 45880
//Sani buyuk Osman Pasa Plevneden cikmam diyor.
//FatihSultanMehmedHan
//Abdulhamid Han Elmuzaffer Daima
//Bismillahirrahmanirrahim

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include <bits/stdc++.h>

using namespace std;

typedef long long int lo;
typedef pair< int,int > PII;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(lo i=1;i<=n;i++)
#define mid (start+end)/2
#define ort (bas+son)/2

const lo MAX = -1000000000000000000; 
const lo MIN = 1000000000000000000; 
const lo inf = 1000000000; 
const lo KOK = 100000; 
const lo LOG = 30; 
const lo li = 2000005; 
const lo mod = 1000000007; 

lo n,m,cev,b,a[li],k;
string s;
vector<lo> v;

inline lo solve(){
	scanf("%lld %lld",&n,&m);
	FOR{
		scanf("%lld",&a[i]);
	}
	for(lo i=1;i<n;i++){
		if(a[i+1]-a[i]<m) cev+=a[i+1]-a[i];
		else cev+=m;
	}
	printf("%lld\n",cev+m);
	return 0;
}

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


Measured memory_bytes: 1792
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
	int n; cin >> n;
	vector<int>l(n);
	for(int i=0; i<n; i++){
		cin >> l[i];
	}
	int ret = 0;
	for(int i=0; i<n-2; i++){
		for(int j=i+1; j<n-1; j++){
			for(int k=j+1; k<n; k++){
				if(l[i]==l[j] || l[i] == l[k] || l[j] == l[k]) continue;
				if(l[i]+l[j] > l[k] && l[i]+l[k] > l[j] && l[j]+l[k] > l[i]){
					ret++;
				}
			}
		}
	}
	cout << ret << endl;
	return 0;
}

Measured memory_bytes: 3660
#include<bits/stdc++.h>
#define ll long long
using namespace std;
void c_p_c(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
}
int minCost(ll *h,int n,int k){
	ll dp[n];
	dp[0] = 0;
	for(int i=1;i<k;i++){
		ll ans = INT_MAX;
		for(int j=0;j<i;j++)
			ans = min(ans, dp[j]+abs(h[i]-h[j]));
		dp[i] = ans;
	}
	for(int i=k;i<n;i++){
		ll ans = INT_MAX;
		for(int j=i-k;j<i;j++)
			ans = min(ans, dp[j]+abs(h[i]-h[j]));
		dp[i] = ans;
	}
	return dp[n-1];
}
int main()
{
	c_p_c();
	int n,k;
	cin>>n>>k;
	ll h[n];
	for(int i=0;i<n;i++)
		cin>>h[i];
	if(k>n)
		k = n;
	cout<<minCost(h,n,k)<<"\n";
}

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<vector<int>> acc(2*k+1, vector<int>(2*k+1));
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        char c;
        cin >> c;
        if (c == 'W') y += k;
        x %= 2*k, y %= 2*k;
        acc[x+1][y+1]++;
    }

    for (int i = 0; i + 1 <= 2*k; i++) {
        for (int j = 0; j + 1 <= 2*k; j++) {
            acc[i+1][j+1] += acc[i][j+1] + acc[i+1][j] - acc[i][j];
        }
    }

    int ans = 0;
    vector<pair<int, int>> v = { { 0, 0 }, { -k, -k }, { -k, k }, { k, k }, { k, -k } };
    for (int i = 0; i <= k; i++) {
        for (int j = 0; j <= k; j++) {
            int can = 0;
            for (auto& e : v) {
                int ax = i + e.first, ay = j + e.second;
                int bx = ax + k, by = ay + k;
                for (auto& f : { &ax, &ay, &bx, &by }) {
                    *f = max(0, *f);
                    *f = min(2*k, *f);
                }
                can += acc[bx][by] - acc[bx][ay] - acc[ax][by] + acc[ax][ay];
            }
            ans = max(ans, can);
            ans = max(ans, n - can);
        }
    }

    cout << ans << endl;
}



Measured memory_bytes: 16000
#include <bits/stdc++.h>
 
using namespace std;
 
int main(){
 	int n; cin >> n;
  	string rocks;
  	cin >> rocks;
  	int x=0, ans;
    for(int i=0;i<n;i++){
    	if(rocks[i]=='R')
      		x++;
    }
  	ans=x;
  	for(int i=0;i<x;i++){
    	if(rocks[i]=='R')
          ans--;
    }
  	cout << ans;
}

Measured memory_bytes: 3720
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<functional>
#include<algorithm>
#include<stdlib.h>
#include<string>
#include<string.h>
#define _USE_MATH_DEFINES
#include<math.h>
#include<deque>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<iostream>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,a,b) for(auto i=a;i<b;i++)
#define all(_x) _x.begin(), _x.end()
#define r_sort(_x) sort(_x.begin(), _x.end(), std::greater<int>())
#define vec_cnt(_a, _n) (upper_bound(all(_a), _n) - lower_bound(all(_a), _n))
#define vec_unique(_a) _a.erase(std::unique(all(_a)), _a.end());
#define vvec vector<vector<ll>>
ll gcd(ll a, ll b) { return a % b == 0 ? b : gcd(b, a % b); }
ll lcm(ll a, ll b) { return (a / gcd(a, b)) * b; }
#define INF 1 << 30
const int mod = 1000000007;
ll power(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x *= x; p /= 2; } else { a *= x; p--; } }return a; }
ll mpower(ll x, ll p) { ll a = 1; while (p > 0) { if (p % 2 == 0) { x = x * x % mod; p /= 2; } else { a = a * x % mod; p--; } }return a; }
ll c(ll n, ll k) { ll a = 1; rep(i, 1, k) { a *= n - i + 1; a /= i; }return a; }
ll mc(ll n, ll m) { ll k = 1, l = 1; rep(i, n - m + 1, n + 1) k = k * i % mod; rep(i, 1, m + 1) l = l * i % mod; l = mpower(l, mod - 2); return k * l % mod; }

int main(void) {
	ll N, k, k2, x, sum = 0;
	cin >> N;
	x = (ll)sqrt(N);
	rep(i, 1ll, x + 1) {
		if (N % i)continue;
		k = N / i;
		if (k - 1 && N / (k - 1) == i) {
			sum += k - 1;
		}
		if (i - 1 && N / (i - 1) == k) {
			sum += i - 1;
		}
	}
	printf("%lld\n", sum);
	return 0;
}

Measured memory_bytes: 256
n = int(input())
a = list(map(int,input().split()))
a_dic = {}
for i in range(n):
    if a[i] not in a_dic:
        a_dic[a[i]] = 0
    a_dic[a[i]] += 1
a_key = list(a_dic.keys())
a_val = list(a_dic.values())
#print(a_key,a_val)
ans = 0

for i in range(len(a_key)):
    if a_key[i] > a_val[i]:
        ans += a_val[i]
    else:
        ans += a_val[i] - a_key[i]

print(ans)


Measured memory_bytes: 69032
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <bitset>
using namespace std;
typedef long long ll;
#define rep(i,s,n)for(ll i = s;i<n;i++)
#define repe(i,s,n)for(ll i = s;i<=n;i++)

bool F[100][10] = {};
ll P[100][11] = {};

int getMatchNum(int n, int i) {
	int num = 0;
	int d = 0;
	while (i) {
		if (i % 2 == 1 && F[n][d]) {
			num++;
		}
		i = i >> 1;
		d++;
	}

	return num;
}

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

	rep(i, 0, N) {
		rep(j, 0, 10) {
			cin >> F[i][j];
		}
	}

	rep(i, 0, N) {
		rep(j, 0, 11) {
			cin >> P[i][j];
		}
	}

	ll maxV = -1 << 30;
	for (int i = 1; i < 1 << 10; i++) {
		ll margin = 0;
		rep(n, 0, N) {
			ll m = getMatchNum(n, i);
			margin += P[n][m];
		}
		maxV = max(maxV, margin);
	}

	cout << maxV << endl;
	return 0;
}

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

int n,m;
ll ans,x;
priority_queue<ll> Q;

int main(){
	scanf("%d%d",&n,&m);
	ans=0;
	for(int i=0;i<n;i++){
		scanf("%lld",&x);
		Q.push(x);
	}
	for(int i=0;i<m;i++){
		x=Q.top();Q.pop();
		Q.push(x>>1);
	}
	while(!Q.empty()){
		x=Q.top();Q.pop();
		ans+=x;
	}
	printf("%lld",ans);
	return 0;
}


Measured memory_bytes: 1400
#include <iostream>
using namespace std;
int main() {
    int n, k; cin >> n >> k;
    int a[n]; for (int i = 0; i < n; i++) cin >> a[i];
    long long s[n+1], L[n+1], R[n+1];
    s[0] = L[0] = R[n] = 0;
    for (int i = 0; i < n; i++) {
        s[i+1] = s[i] + a[i];
        L[i+1] = L[i] + max(0, a[i]);
        R[n-i-1] = R[n-i] + max(0, a[n-i-1]);
    }
    long long ans = 0;
    for (int i = 0; i+k <= n; i++)
        ans = max(ans, max(0LL, s[i+k] - s[i]) + L[i] + R[i+k]);
    cout << ans << endl;
}


Measured memory_bytes: 2944
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

mat = [[True]*H for i in [0]*W]
for x,y in bk:
	mat[x][y] = False

cnt = 0
al = len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in bk:
		if x > 0 and mat[x-1][y]:
			mat[x-1][y] = False
			new.append((x-1,y))
		if x < W-1 and mat[x+1][y]:
			new.append((x+1,y))
			mat[x+1][y] = False
		if y > 0 and mat[x][y-1]:
			new.append((x,y-1))
			mat[x][y-1] = False
		if y < H-1 and mat[x][y+1]:
			new.append((x,y+1))
			mat[x][y+1] = False
	al += len(new)
	bk = new
	cnt += 1
print(cnt)




Measured memory_bytes: 117684
import sys

n=int(input())
li=list(map(int,input().split()))
li.sort()

mi,mx=li[0],li[-1]
ans=10**9
t=10**9
if mi==mx:
    print(0)
    sys.exit()

for i in range(mi,mx):
    ans=min(ans,t)
    t=0
    for j ,item in enumerate(li):
       t+=(li[j]-i)**2
       
print(ans)

Measured memory_bytes: 3064
// 
#include <bits/stdc++.h>
#define endl "\n"
#define rep(i,n) for(int i=0;i<int(n);i++)
#define e_b emplace_back
#define sz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> ipair;
typedef pair<ll,ll> lpair;
template <class T>ostream &operator<<(ostream &o,const vector<T>&v) //vectorの中身を見る
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}
void map_p(map<int,int>& d){cout<<"map: ";for(auto a : d){cout<<"{"<<a.first<<":"<<a.second<<"}";}cout<<endl;} //mapの中身を見る
void set_p(set<int>& d){cout<<"set: ";for(int a : d){cout<<a<<" ";}cout<<endl;} //setの中身を見る


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(12);

    int n;
    cin>>n;
    map<string,int> a;
    a["AC"]=0,a["WA"]=1,a["TLE"]=2,a["RE"]=3;
    vector<int> ans(4,0);
    vector<string> name={"AC","WA","TLE","RE"};
    rep(i,n){
        string s;
        cin>>s;
        ans[a[s]]++;
    }
    rep(i,4){
        cout<<name[i]<<" x "<<ans[i]<<endl;
    }
    return 0;
}

Measured memory_bytes: 3668
package main

import (
	"fmt"
	"sort"
)

func main() {
	var N, M, answer, jumpLimit int
	fmt.Scan(&N, &M)
	numList := make([]int, M)
	for i := 0; i < M; i++ {
		fmt.Scan(&numList[i])
	}
	sort.Sort(sort.IntSlice(numList))

	if M <= N {
		fmt.Println(0)
	} else {
		dList := make([]int, M-1)
		for i := 0; i < M-1; i++ {
			dList[i] = numList[i+1] - numList[i]
		}
		sort.Sort(sort.IntSlice(dList))

		jumpList := make([]int, N-1)
		for i := 0; i < N-1; i++ {
			jumpList[i] = dList[M-2-i]
		}

		jumpLimit = N - 1
		if jumpLimit != 0 {
			for i := 0; i < jumpLimit; i++ {
				dList[M-2-i] = 0
			}
		}
		answer = Sum(dList)
		fmt.Println(answer)
	}

}

func Sum(a []int) int {
	s := 0
	for _, n := range a {
		s = s + n
	}
	return s
}


Measured memory_bytes: 5504
require 'prime'

P = 1_000_000_007

Inv = Hash.new do |h, i|
  h[i] = P - (P / i) * h[P % i] % P
end
Inv[1] = 1

def nCr(n, r)
  Frac[n] * Inv[Frac[n - r] * Frac[r] % P] % P
end

N, M = gets.split.map(&:to_i)

xs = M.prime_division.map{|n, i| i}
Frac = [1]
for i in 1..(N + 30)
  Frac << Frac.last * i % P
end

ans = 1
xs.each do |x|
  ans = ans * nCr(N + x - 1, x) % P
end

puts ans


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

using namespace std;

#define INF 1001000100010001000
#define MOD 1000000007
#define EPS 1e-10
#define int long long
#define rep(i, N) for (int i = 0; i < N; i++)
#define Rep(i, N) for (int i = 1; i < N; i++)
#define For(i, a, b) for (int i = (a); i < (b); i++)
#define pb push_back
#define eb emplece_back
#define mp make_pair
#define i_i pair<int, int>
#define vi vector<int>
#define vvi vector<vi >
#define vb vector<bool>
#define vvb vector<vb >
#define vp vector< i_i >
#define all(a) (a).begin(), (a).end()
#define Int(x) int x; scanf("%lld", &x);
#define int2(x, y) int x, y; scanf("%lld %lld", &x, &y);
#define int3(x, y, z) Int(x); int2(y, z);
#define fir first
#define sec second
#define ffir first.first
#define fsec first.second
#define sfir second.first
#define ssec second.second

//int dxy[5] = {0, 1, 0, -1, 0};
// assign avl ncm dijkstra geo2 kruskal graph uf lca BIT
// matrix dinic next_combination

signed main()
{
    Int(n);
    cout << "ABC" << n << endl;

    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

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

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1 << 30;
// clang-format on

ll N, K;
int a[MAX_N], b[MAX_N];

int main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N >> K;
  REP(i, N) cin >> a[i] >> b[i];

  priority_queue<P, vector<P>, greater<P>> q;

  REP(i, N) q.push(P(a[i], b[i]));

  int ans = 0;
  ll num = 0;
  while (!q.empty()) {
    P p = q.top();
    q.pop();
    num += p.second;
    if (num >= K) {
      ans = p.first;
      break;
    }
  }
  cout << ans << endl;

  return 0;
}


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

int main() {
  
  int N;
  cin >> N;
  
  vector<int> nums(N);
  for(int i=0; i<N; i++){ cin >> nums.at(i); }
  
  int count = 0;
  for(int i=1; i<N-1; i++){
  	if(nums.at(i-1)<nums.at(i) && nums.at(i)<nums.at(i+1)){
    	count++;
    }else if(nums.at(i-1)>nums.at(i) && nums.at(i)>nums.at(i+1)){
    	count++;
    }
  }
  
  cout << count << endl;
}

Measured memory_bytes: 256
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

// doot diddly donger cuckerino Hahahahahah
// Created by White Knife on 15/04/20.
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#pragma GCC target("popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;

// @formatter:off
#define F               first
#define S               second
#define all(x)          (x).begin(), (x).end()
#define sz(x)           (long long) (x).size()
#define sim             template<typename T
#define ris             return *this
#define dor             > debug & operator <<
#define eni(x)          sim > typename enable_if<sizeof dud<T>(0) x 1, debug&>::type operator<<(T i)
sim> struct rge { T b, e; };
sim> rge<T> range(T i, T j) { return rge<T>{i, j}; }
sim> auto dud(T *x) -> decltype(cerr << *x, 0);
sim> char dud(...);
struct debug {
#ifdef LOCAL
  ~debug() { cerr << endl; }
  eni(!=) { cerr << boolalpha << i; ris; }
  eni(==) { ris << range(all(i)); }
  sim, typename U dor(pair<U, T> d) { ris << "(" << d.first << ", " << d.second << ")"; }
  sim dor(rge<T> d) { *this << "["; for (auto it = d.b; it != d.e; ++it) *this << ", " + 2 * (it == d.b) << *it; ris << "]"; }
#else
  sim dor(const T&) { ris; }
#endif
};
#define pr(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;

using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vpii = vector<pii>;
using vpll = vector<pll>;
template <typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const ld PI = acos(-1);

template <typename T> T gcd(T x, T y) { return (y == 0) ? x : gcd(y, x % y); }
template<typename T> inline T mini(T& x, T y) { return x = min(x, y); }
template<typename T> inline T maxi(T& x, T y) { return x = max(x, y); }
template <typename T> T rand(T x, T y) { return rand() % (y - x + 1) + x; }
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
// @formatter:on


class B1 {
public:
  
  void solveOne(istream &cin, ostream &cout) {
  
  }
  
  void solve(std::istream &cin, std::ostream &cout) {
    ld x;
    cin >> x;
    ll res = 0;
    ll bal = 100;
    while (bal < x) {
      bal += bal / 100;
      ++res;
    }
    cout << res << '\n';
  }
};

int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
	B1 solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 3692
#include<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
int main()
{
	int n;cin>>n;cout<<(n-2)*180<<endl;
}


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

// 入力
int N, A[409], B[409];
int num[409][409];
bool used[409][409];

// DP の計算
int mod = 1000000007;
int dp[139][409][409][2];

void solve(int pos) {
	// ステップ 1. p を動かす
	for (int i = N; i >= 2; i--) {
		for (int j = 1; j <= N; j++) {
			dp[pos - 1][i - 1][j][0] += dp[pos - 1][i][j][0];
			dp[pos - 1][i - 1][j][0] %= mod;
		}
	}

	// ステップ 2. 変換する
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dp[pos - 1][i][j][1] = dp[pos - 1][i][j][0];
		}
	}

	// ステップ 3. q を動かす
	for (int i = 1; i <= N; i++) {
		for (int j = N; j >= 2; j--) {
			dp[pos - 1][i][j - 1][1] += dp[pos - 1][i][j][1];
			dp[pos - 1][i][j - 1][1] %= mod;
		}
	}

	// ステップ 4. DP の遷移を行う
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (used[i][j] == false) continue;
			int L = (((N / 3) - pos) * 3 + 1) - num[i][j];
			if (L <= 0 || L > (N / 3) - (pos - 1)) continue;
			dp[pos][i - 1][j - 1][0] = (1LL * L * dp[pos - 1][i][j][1]) % (1LL * mod);
		}
	}
}

int main() {
	// 入力
	cin >> N;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 1; i <= N; i++) cin >> B[i];

	// 前処理
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			bool I[409];
			for (int k = 1; k <= N; k++) I[k] = false;
			for (int k = 1; k <= i - 1; k++) I[A[k]] = true;
			for (int k = 1; k <= j - 1; k++) I[B[k]] = true;
			for (int k = 1; k <= N; k++) { if (I[k] == true) num[i][j]++; }
			if (I[A[i]] == false && I[B[j]] == false) used[i][j] = true;
			if (A[i] == B[j]) used[i][j] = false;
		}
	}

	// DP の計算
	dp[0][N][N][0] = 1;
	for (int i = 1; i <= N / 3; i++) {
		solve(i);
	}

	// 答えを出力
	long long ret = dp[N / 3][0][0][0];
	for (int i = 1; i <= N; i++) {
		if (i % 3 == 0) continue;
		ret *= (1LL * i);
		ret %= mod;
	}
	cout << ret << endl;
	return 0;
}

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

int main(){
    ll N;
    cin >> N;
    map<ll,ll> A;
    ll tmp;
    rep(i,N){
        cin >> tmp;
        A[tmp]++;
    }
    ll size = A.size();
    ll cnt = 0;
    for(auto& p:A){
        if(p.second >= 2){
            if(p.second % 2 == 0){
                cnt++;
            }
        }
    }
    cnt = cnt % 2;

    cout << size - cnt << endl;
}
/*
1 3 5 2 1 3 2 8 8 6 2 6 11 1 1
1 3 5 2 1 3 2 8 8 6 2 6 11
1 3 5 2 1 3 8 8 6 6 11


*/

Measured memory_bytes: 6528
#include <iostream>
#include <string>

using namespace std;

int main() {
  string S;
  cin >> S;

  char c = S[0];
  for (int i = 1; i < 3; i++) {
    if (c != S[i]) {
      cout << "Yes" << endl;
      return 0;
    }
    c = S[i];
  }
  cout << "No" << endl;

  return 0;
}


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

int main() {
	ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int n,k;
	cin>>n>>k;

	vector<int> v(n+1);
	vector<int> dp(n+1);
	
	for(int i=1;i<=n;i++)
		cin>>v[i];
	

	for(int i=2;i<=n;++i) {
		int min_val=dp[i-1]+abs(v[i]-v[i-1]);

		for(int j=max(1,i-k);j<i;++j) 
			min_val = min(min_val,dp[j]+abs(v[i]-v[j]));
	
		dp[i] = min_val;
	}

	cout<<dp[n];

	return 0;
}

Measured memory_bytes: 3964
#include <algorithm>     //sort,二分探索,など
#include <bitset>        //固定長bit集合
#include <cmath>         //pow,logなど
#include <complex>       //複素数
#include <deque>         //両端アクセスのキュー
#include <functional>    //sortのgreater
#include <iomanip>       //setprecision(浮動小数点の出力の誤差)
#include <iostream>      //入出力
#include <iterator>      //集合演算(積集合,和集合,差集合など)
#include <map>           //map(辞書)
#include <numeric>       //iota(整数列の生成),gcdとlcm(c++17)
#include <queue>         //キュー
#include <set>           //集合
#include <stack>         //スタック
#include <string>        //文字列
#include <unordered_map> //イテレータあるけど順序保持しないmap
#include <unordered_set> //イテレータあるけど順序保持しないset
#include <utility>       //pair
#include <vector>        //可変長配列

using namespace std;
typedef long long ll;

//マクロ
//forループ関係
//引数は、(ループ内変数,動く範囲)か(ループ内変数,始めの数,終わりの数)、のどちらか
//Dがついてないものはループ変数は1ずつインクリメントされ、Dがついてるものはループ変数は1ずつデクリメントされる
#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define REPD(i, n) for (ll i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (ll i = a; i <= (ll)(b); i++)
#define FORD(i, a, b) for (ll i = a; i >= (ll)(b); i--)
//xにはvectorなどのコンテナ
#define ALL(x) (x).begin(), (x).end() //sortなどの引数を省略したい
#define SIZE(x) ((ll)(x).size())      //sizeをsize_tからllに直しておく
#define MAX(x) *max_element(ALL(x))   //最大値を求める
#define MIN(x) *min_element(ALL(x))   //最小値を求める
//定数
#define INF 1000000000000 //10^12:極めて大きい値,∞
#define MOD 10000007      //10^9+7:合同式の法
#define MAXR 100000       //10^5:配列の最大のrange(素数列挙などで使用)
//略記
#define PB push_back //vectorヘの挿入
#define MP make_pair //pairのコンストラクタ
#define F first      //pairの一つ目の要素
#define S second     //pairの二つ目の要素

signed main()
{
    int X, A, B;
    A = 0;
    B = 0;
    cin >> X;

    int i = 0;
    int j = 0;
    int k = 0;
    int l = 0;
    
    int C = 0;
    int D = 0;

    while(true){
        C = pow(i, 5)-pow(j, 5);
        if(C==X){
            cout << i <<' '<< j << endl;
            break;
        }else if(C<X){
            i++;
        }else{
            j++;
        }
        D = pow(k, 5)-pow(l, 5);
        if(D==X){
            cout << k <<' '<< l << endl;
            break;
        }else if(D<X){
            l--;
        }else{
            k++;
            l = 0;
        }

    }

    
    
}

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

int main()
{
    int a, b;
    int area, length;
    cin >> a >> b;
    area = a * b;
    length = a * 2 + b * 2;
    cout << area << " " << length << endl;
    return 0;
}



Measured memory_bytes: 3020
import math
import copy
from copy import deepcopy
import sys
import fractions
import numpy as np
from functools import reduce
# import statistics
import heapq
sys.setrecursionlimit(3000)

# input = sys.stdin.readline
# sys.setrecursionlimit(10**6)

# ===FUNCTION===

def getInputInt():
    inputNum = int(input())
    return inputNum


def getInputListInt():
    outputData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData


def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList


def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList


# ===CODE===

n, k = map(int, input().split())
data = list(map(int, input().split()))

ans = 0

for i in range(1, min(n, k)+1, 1):
    for j in range(i+1):
        l = j
        r = n-(i-j)

        d = data[:l]
        d += data[r:]
        d.sort()

        del_num = min(k-i, i)
        for l in range(del_num):
            if d[l] >= 0:
                del_num = l
                break
        ans = max(ans, sum(d[del_num:]))

print(ans)

Measured memory_bytes: 13684
#include<iostream>
using namespace std;
int main()
{
	int pa[10003] = { 0 };
	int va[2000][2];
	int n, m;
	int i, j;

	cin >> n >> m;

	for (i = 0; i < n; i++)
	{
		cin >> va[i][0] >> va[i][1];
	}

	for (i = 0; i < n; i++)
	{
		if (va[i][0] > pa[va[i][1]])
		{
			pa[va[i][1]] = va[i][0];
		}
	}

	for (i = 0; i < m; i++)
	{
		if (pa[i] > 0)
		{
			for (j = 0; j < n; j++)
			{
				if (i + va[j][1] <= m && pa[i] + va[j][0] > pa[i + va[j][1]])
				{
					pa[i + va[j][1]] = pa[i] + va[j][0];
				}
			}
		}
	}

	int mx = 0;
	for (i = 1; i <= m; i++)
	{
		if (mx < pa[i])
		{
			mx = pa[i];
		}
	}

	cout << mx << endl;

	return 0;
}

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

int main()
{
    int N;
    cin >> N;
    vector<int> s;
    s.resize(N+1);
    int m = sqrt(N);
    for (int x=1; x<=m; ++x) {
        for (int y=1; y<=m; ++y) {
            for (int z=1; z<=m; ++z) {
                int i = x*x+y*y+z*z+x*y+y*z+z*x;
                if (i <= N) {
                    s[i]++;
                }
            }
        }
    }
    for (int n=1; n<=N; ++n) {
        cout << s[n] << endl;
    }
    return 0;
}


Measured memory_bytes: 3120
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef double DB;

#define F(i,a,b) for(int i=(a);i<=(b);++i)
#define R(i,n) for(int i=0;i<(n);++i)
#define fill(a,b) memset(a,b,sizeof(a))

const int maxn = 1e5 + 10;
int a[maxn],b[maxn];
int n;

int main()
{
//	freopen("test.txt","r",stdin);
	scanf("%d",&n);	
	R(i,n)
	{
		scanf("%d",a+i);
		b[i] = a[i];
	}
	sort(b,b+n);
	int cnt = 0;
	R(i,n)
	{
		int p = lower_bound(b,b+n,a[i]) - b;
		if((p - i)%2 != 0) ++cnt;
	}
	assert(!(cnt&1));
	printf("%d\n",cnt/2);
	return 0;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
const ll inf=1e12;
const double eps=1e-9;

int main(void)
{
    map<pll,ll> Foxmap;
    int N;
    cin >> N;
    ll ans=0;
    vector<pll> xy(N);
    for(int i=0;i<N;i++)
    {
        ll x,y,w;
        cin >> x >> y>> w;
        Foxmap[pll(x,y)]=w;
        xy[i]=pll(x,y);
    }
    for(int i=0;i<N;i++)
    {
        ll s1=0,s2=0,s3=0,s4=0;
        //各点を中心として,4つの1*1の正方形にして考えると...
        //左上
        s1=Foxmap[pll(xy[i].first,xy[i].second)]+Foxmap[pll(xy[i].first-1LL,xy[i].second)]+Foxmap[pll(xy[i].first-1LL,xy[i].second-1LL)]+Foxmap[pll(xy[i].first,xy[i].second-1LL)];
        //左下
        s2=Foxmap[pll(xy[i].first,xy[i].second)]+Foxmap[pll(xy[i].first-1LL,xy[i].second)]+Foxmap[pll(xy[i].first-1LL,xy[i].second+1LL)]+Foxmap[pll(xy[i].first,xy[i].second+1LL)];
        //右下
        s3=Foxmap[pll(xy[i].first,xy[i].second)]+Foxmap[pll(xy[i].first+1LL,xy[i].second)]+Foxmap[pll(xy[i].first+1LL,xy[i].second+1LL)]+Foxmap[pll(xy[i].first,xy[i].second+1LL)];
        //右上
        s4=Foxmap[pll(xy[i].first,xy[i].second)]+Foxmap[pll(xy[i].first+1LL,xy[i].second)]+Foxmap[pll(xy[i].first+1LL,xy[i].second-1LL)]+Foxmap[pll(xy[i].first,xy[i].second-1LL)];
        //cout << s1 << ' ' << s2 << ' ' << s3 << ' ' << s4 << endl;
        ans=max(ans,s1);
        ans=max(ans,s2);
        ans=max(ans,s3);
        ans=max(ans,s4);
    }
    cout << ans << ' ' << '/' << ' ' << 1 << endl;
}


Measured memory_bytes: 60640
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> P;
typedef pair<ll, P> P3;
typedef pair<P ,P> PP;
constexpr ll MOD = ll(1e9) + 7;
constexpr int IINF = INT_MAX;
constexpr ll LLINF = LLONG_MAX;
constexpr int MAX_N = int(1e5) + 5;
constexpr double EPS = 1e-9;
constexpr int di[] = {0, 1, 0, -1}, dj[] = {1, 0, -1, 0};
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i > 0; i--)
#define SORT(v) sort((v).begin(), (v).end())
#define SORTR(v) sort((v).rbegin(), (v).rend())
#define ALL(v) (v).begin(), (v).end()

int main() {
    int n, cnt = 0;
    cin >> n;
    for(int i=1;i<=n;i++){
        int d = i, k = 0;
        while(d > 0){
            d /= 10;
            k++;
        }
        if(k%2) cnt++;
    }
    cout << cnt << endl;
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
void printAns(int arr[], int len) {
	using std::cout;
	using std::endl;
	for (int i = 0; i < len; i++)
	{
		if (i)
			cout << " ";
		cout << arr[i];
	}
	cout << endl;
}
int main() {
	using namespace std;
	int len;
	cin >> len;
	int* arr = new int[len];
	for (int i = 0; i < len; i++)
		cin >> arr[i];
	int step = 0;
	for (int i = 0; i < len; i++) {
		int min = i;
		for (int j = i + 1; j < len; j++) {
			if (arr[j] < arr[min]) {
				min = j;
			}
		}
		if (min != i) {
			swap(arr[i], arr[min]);
			step++;
		}
	}
	printAns(arr, len);
	cout << step << endl;
	return 0;
}


Measured memory_bytes: 3088
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
#define deb(x) cout<<#x<<" "<<x<<endl;
#define print(arr,n) for(int i=0;i<n;++i) { cout<<arr[i]<<" "; } cout<<endl;
#define ub(x,el) upper_bound(x.begin(),x.end(),el) - x.begin()
#define lb(x,el) lower_bound(x.begin(),x.end(),el) - x.begin();
#define bs(x,el) binary_search(x.begin(),x.end(),el)
#define MOD 1000000007
#define finish return 0
using namespace std;
using namespace __gnu_pbds; 
typedef long long int ll;
typedef tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
template<int D, typename T> struct Vec : public vector<Vec<D - 1, T>> { static_assert(D >= 1, "Vector dimension must be greater than zero!"); template<typename... Args> Vec(int n = 0, Args... args) : vector<Vec<D - 1, T>>(n, Vec<D - 1, T>(args...)) { }}; template<typename T> struct Vec<1, T> : public vector<T> { Vec(int n = 0, T val = T()) : vector<T>(n, val) { } };
inline ll mod(ll x) { return (x%MOD + MOD)%MOD; }
ll power(ll x,ll y, ll p) { ll res = 1; x = x % p; while (y > 0) { if (y & 1) res = (res*x) % p; y = y>>1; x = (x*x) % p;   } return res; } 
ll power(ll x,ll y) { ll res = 1; while (y > 0) { if (y & 1) res = (res*x); y = y>>1; x = (x*x);   } return res; } 
ll mod(ll num, ll den){ return mod(mod(num) * power(den,MOD-2,MOD)); }
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
	double pi = acos(-1);
	double R;
	cin>>R;
	double ans = 2*pi*R;
	cout<<ans<<endl;
}

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

#define int long long

int N,M;
int done[100010];

struct NODE{
	int pos,cost,now;
};
bool operator <(const NODE &a,const NODE &b){
	return a.cost > b.cost;
}

vector<NODE> g[100010];
int h[100010];

signed main(){
	cin >> N >> M;
	int X;
	cin >> X;
	for(int i = 0 ; i < N ; i++) cin >> h[i];
	for(int i = 0 ; i < M ; i++){
		int a,b,c;
		cin >> a >> b >> c;
		--a,--b;
		if( h[a] - c >= 0 ) g[a].push_back({b,c,-1});
		if( h[b] - c >= 0 ) g[b].push_back({a,c,-1});		
	}
	priority_queue<NODE> Q;
	Q.push({0,0,X});
	while( Q.size() ){
		auto q = Q.top(); Q.pop();
		if( done[q.pos]++ ) continue;
		if( q.pos == N-1 ){
			cout << q.cost + abs(h[q.pos]-q.now) << endl;
			return 0;
		}
		for( auto e : g[q.pos] ){
			int cst = e.cost;
			int nextH = q.now - e.cost;
			if( nextH < 0 ) cst += -nextH, nextH = 0;
			if( nextH > h[e.pos] ) cst += nextH-h[e.pos], nextH = h[e.pos];
			
			Q.push({e.pos,q.cost+cst,nextH});
		}
	}
	cout << -1 << endl;
	
}

Measured memory_bytes: 41648
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
#define FOR(i,a,b) for(int i=(a); i<(b); i++)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
typedef long long ll;
int main(){
    cout<< fixed<< setprecision(10);
    int n,k; cin >> n;
    if(n % 2) k = (n+1) / 2;
    else k = n / 2;
    double ans = (double)k/n;

    cout << ans <<endl;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
A = tuple(map(int, input().split()))
MOD = 10 ** 9 + 7

if K == N:
    ans = 1
    for x in A:
        ans = (ans * x) % MOD
    print(ans)
    exit()

plus, minus = [], []
for a in A:
    if a >= 0:
        plus.append(a)
    else:
        minus.append(a)

plus.sort(reverse=True)
minus.sort()

if not plus:
    ans = 1
    if K % 2:
        # 答えは負値になるので絶対値小さいのを取る
        for x in minus[-K:]:
            ans = (ans * x) % MOD
    else:
        # 答えは非負値になるので絶対値大きいのを取る
        for x in minus[:K]:
            ans = (ans * x) % MOD
    print(ans)
    exit()

idx = 0
for i in range(2, N, 2):
    if K - i < 0:
        break
    if not len(plus) >= K - i + 2:
        idx += 2
        continue
    if len(minus) >= i:
        if minus[i - 2] * minus[i - 1] < plus[K - i + 1] * plus[K - i]:
            break
        else:
            idx += 2

ans = 1
for x in minus[:idx] + plus[:K - idx]:
    ans = (ans * x) % MOD
print(ans)


Measured memory_bytes: 31776
#include <bits/stdc++.h>
#define int long long
#define double long double
#define INF 1e18
using namespace std;
int x[200], y[200];
int xmin,xmax,ymin,ymax, N;
signed main() {
  int mx[4] = { -1, 0, 1, 0 }, my[4] = { 0, -1, 0, 1 };
  while(cin>>N,N!=0) {
    xmin=xmax=ymin=ymax=0;
    for (int i = 0; i <= N; i++) {
      x[i] = 0; y[i] = 0;
    }
    for (int i = 1; i < N; i++) {
      int n,d; cin>>n>>d;
      x[i] = x[n]+mx[d];
      y[i] = y[n]+my[d];
      xmin = min(x[i], xmin);
      xmax = max(x[i], xmax);
      ymin = min(y[i], ymin);
      ymax = max(y[i], ymax);
    }
    int w = xmax-xmin+1, h = ymax-ymin+1;
    cout << w << " " << h << endl;
  }  
}



Measured memory_bytes: 3084
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		
		int a=sc.nextInt();
		int b=sc.nextInt();
		int c=sc.nextInt();
		int k=sc.nextInt();
		
		int ans=0;
		
		if(k<=a)ans=k;
		else if(k<=a+b)ans=a;
		else if(k<=a+b+c)ans=a-(k-a-b);

		
		
		
		System.out.println(ans);
		
		
	}

}


Measured memory_bytes: 35712
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    N,M=MI()
    S=LI()
    T=LI()
    
    dp=[[0]*(M+1) for _ in range(N+1)]
    dp[0][0]=1
    #dp[i][j]はSのi文字目，Tのj文字目を使う時の通り数
    cumsum=[[0]*(M+2) for _ in range(N+2)]
    #2D累積和
    
    for i in range(1,N+2):
        cumsum[i][1]=1
    for j in range(1,M+2):
        cumsum[1][j]=1
    
    for i in range(N):
        for j in range(M):
            if S[i]==T[j]:
                dp[i+1][j+1]=(cumsum[i+1][j+1])%mod
                
            cumsum[i+2][j+2]=(cumsum[i+2][j+1]+cumsum[i+1][j+2]-cumsum[i+1][j+1]+dp[i+1][j+1])%mod
            
    print(cumsum[-1][-1])
    """
    for i in range(N+2):
        print(' '.join(map(str, cumsum[i])))
        
    for i in range(N+1):
        print(' '.join(map(str, dp[i])))"""

main()


Measured memory_bytes: 104284
def add word
	@dic[hashF word] << word
end

def hashF word
    temp = word.dup
	temp.gsub!("A", "1")
	temp.gsub!("C", "2")
	temp.gsub!("G", "3")
    temp.gsub!("T", "4")
	return temp.to_i(5) % @dic.length
end

def find word
    @dic[hashF word].include? word
end

n = gets.to_i
@dic = Array.new(n){[]}
n.times{
	command, word = gets.chomp.split
	case command
	when "insert"
		add word
	else
		puts (find word) ? "yes" : "no"
	end
}

Measured memory_bytes: 209996
import java.util.*;

public class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int money = sc.nextInt();
		int x = -1;
		int y = -1;
		int z = -1;
		
		for(int i = 0; i <= n; i++) {
			for(int j = 0; j <= n - i; j++) {
					if(i * 10000 + j * 5000 + (n - i - j) * 1000 == money) {
						x = i;
						y = j;
						z = n - i - j;
						break;
				}
			}
		}
		
		System.out.println(x + " " + y + " " + z);
	}
}


Measured memory_bytes: 23252
#include <iostream>
#include <iomanip>
#include <stdio.h>
#include <set>
#include <vector>
#include <map>
#include <cmath>
#include <algorithm>
#include <memory.h>
#include <string>
#include <sstream>
#include <cstdlib>
#include <ctime>
#include <cassert>

using namespace std;

typedef long long LL;
typedef pair<int,int> PII;

#define MP make_pair
#define PB push_back
#define FF first
#define SS second

#define FORN(i, n) for (int i = 0; i <  (int)(n); i++)
#define FOR1(i, n) for (int i = 1; i <= (int)(n); i++)
#define FORD(i, n) for (int i = (int)(n) - 1; i >= 0; i--)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR0(A,n) { cout << #A << " = "; FORN(_,n) cout << A[_] << ' '; cout << endl; }

#define MOD 1000000007
#define INF 2000000000

int GLL(LL& x) {
    return scanf("%lld", &x);
}

int GI(int& x) {
    return scanf("%d", &x);
}

const int MAXN = 105;
const int MAXS = 105;

int ok[MAXN * MAXS];

int n;

int main() {
    GI(n);

    memset(ok, 0, sizeof ok); ok[0] = 1;

    int s;

    FORN(i, n) {
        GI(s);
        
        FORD(j, MAXN * MAXS) {
            if (j - s >= 0 && ok[j - s]) {
                ok[j] = 1;
            }
        }
    }

    FORD(j, MAXN * MAXS) {
        if (j % 10 != 0 && ok[j]) {
            printf("%d\n", j);
            return 0;
        }
    }

    printf("0\n");
    return 0;
}

Measured memory_bytes: 256
a,b,c=map(int,input().split())
k = int(input())
flag = False
for i in range(1,k+2):
    for j in range(1,k-i+3):
        for d in range(1,k-i-j+4):
            if (a*(2**(i-1)))<(b*(2**(j-1)))<(c*(2**(d-1))):
                flag = True
                
if flag == True:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 9136
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<string> split(const string &s, char delim) {
  vector<string> elems;
  string item;
  for (char ch: s) {
    if (ch == delim) {
      if (!item.empty()) {
        elems.push_back(item);
      }
      item.clear();
    }
    else {
      item += ch;
    }
  }
  if (!item.empty()) {
    elems.push_back(item);
  }
  return elems;
}

string to_str_with_zero(int i, int w) {
  ostringstream sout;
  sout << std::setfill('0') << std::setw(w) << i;
  string s = sout.str();
  return s;
}

int letter_to_int(char c) {
  return tolower(c) - 'a';
}

int compare_array(vector<int> a1, vector<int>a2) {
  if (a1.size() != a2.size()) {
    return a1.size() - a2.size();
  }
  for (int i=0; i<a1.size(); i++) {
    if (a1.at(i) != a2.at(i)) {
      return a1.at(i) - a2.at(i);
    }
  }
  return 0;
}

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

char int_to_char(int a) {
  if (a == -1) {
    return 'z';
  }
  else {
    return 'a' + a;
  }
}

long nCr(int n, int r) {
    long ans = 1;
    for (int i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (int i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}

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

int divide_count(int a, int divider) {
  int r = 0;
  while(a % divider == 0) {
    a /= divider;
    r++;
  }
  return r;
}

bool is_prime(int a) {
  int i = 2;
  while(i * i <= a) {
    if(a % i == 0) {
      return false;
    }
    i++;
  }
  return true;
}

vector<vector<int>> all_comb(int n, int k) {
  vector<vector<int>> combs(nCr(n, k), vector<int>(k));
  for(int i=0; i<k; i++) {
    combs[0][i] = i;
    combs[1][i] = i;
  }
  
  for(long i=1; i<nCr(n, k); i++) {
    int p = 1;
    while(combs[i][k - p] == n - p) {
      p++;
      if(p > k) {
        break;
      }
    }
    combs[i][k - p]++;
    int q = combs[i][k - p];
    for(int j=1; j<p; j++) {
      combs[i][k - p + j] = q + j;
    }

    if(i < nCr(n, k) - 1) {
      for(int j=0; j<k; j++) {
        combs[i + 1][j] = combs[i][j];
      }
    }
  }

  return combs;
}

int main() {
  std::cout << std::setprecision(9);
  int n;
  cin >> n;
  string c;
  cin >> c;
  vector<char> c_c(c.begin(), c.end());

  int l = 0;
  int r = n - 1;
  int ans = 0;
  while(true) {
    while(c_c[l] == 'R') {
      l++;
    }
    while(c_c[r] == 'W') {
      r--;
    }
    if(l < r) {
      c_c[l] = 'R';
      c_c[r] = 'W';
      ans++;
    }
    else {
      break;
    }
  }
  cout << ans << endl;
}

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

#define int long long
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
template<typename T, typename U> inline bool chmax(T &a, const U &b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
template<typename T, typename U> inline bool chmin(T &a, const U &b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
struct Init {
    Init() {
        cout << fixed << setprecision(20);
    };
} init;

int N;
signed main() {
    cin >> N;
    cout << N * (N + 1) / 2 - N;
}


Measured memory_bytes: 256