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

string big(string T, string U){
  string ans = T;
  if(T.size() < U.size()){
    ans = U;
  }
  else if(T.size() == U.size()){
    for(int i=0; i<T.size(); i++){
      if(T.at(i) > U.at(i)){
        break;
      }
      else if(T.at(i) < U.at(i)){
        ans = U;
        break;
      }
    }
  }
  return ans;
}

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> vec(M);
  vector<int> match = {0,2,5,5,4,5,6,3,7,6};
  for(int i=0; i<M; i++){
    cin >> vec.at(i);
  }
  string dp[N+1];
  for(int i=0; i<N+1; i++){
    dp[i] = "";
  }
  for(int i=1; i<N+1; i++){
    for(int j=0; j<M; j++){
      int c = match[vec.at(j)]; //使うマッチ棒の数
      if(i - c < 0){
        continue;
      }
      if(i - c != 0 && dp[i-c] == ""){
        continue;
      }
      else{
        char x = '0' + vec.at(j);
        string S = dp[i-c] + x;
        string T = x + dp[i-c];
        dp[i] = big(dp[i],S);
        dp[i] = big(dp[i],T);
      }
    }
  }
  /*for(int i=0; i<N; i++){
    cout << i << " " << dp[i] << endl;
  }*/
  cout << dp[N] << endl;
}

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

int main() {
  int D;
  cin>>D;
  vector<int> sage(26);
  for(int i=0;i<26;i++){
    cin>>sage.at(i);
  }
  vector<vector<int>> man(D,vector<int>(26));
  for(int i=0;i<D;i++){
    for(int j=0;j<26;j++){
      cin>>man.at(i).at(j);
    }
  }
  vector<int> hini(D);
  vector<vector<int>> rkai(D+1,vector<int>(26,1));
  for(int i=0;i<D;i++){
    int A=0,W=man.at(i).at(0)-2*rkai.at(i).at(0)*sage.at(0);
    for(int j=1;j<26;j++){
      int Y=man.at(i).at(j)-2*rkai.at(i).at(j)*sage.at(j);
      if(Y>W){
        W=Y,A=j;
      }
      rkai.at(i+1).at(j)=rkai.at(i).at(j)+1;
    }
    hini.at(i)=A;
    rkai.at(i).at(A)=0;
    rkai.at(i+1).at(A)=1;
  }
  /*for(int i=0;i<D;i++){
    Z+=man.at(i).at(hini.at(i));
    for(int j=0;j<26;j++){
      Z-=rkai.at(i).at(j)*sage.at(j);
    }
    cout<<Z<<endl;
  }*/
  int a=167,b=167;
  for(int i=0;i<7167167;i++){
    a=i%D;
      b=i%26;
      int Z=0;
    if(rkai.at(a).at(b)==0){
      continue;
    }
    int K=rkai.at(a).at(b),C=0;
    for(int j=a;j<D;j++){
      if(rkai.at(j).at(b)==0){
        break;
      }
      else{
        C++;
      }
    }
    Z+=K*C*sage.at(b);
    Z+=man.at(a).at(b);
    int e=hini.at(a);
    C=0;
      int G;
    if(a==0){
      G=1;
    }
    else{
      G=rkai.at(a-1).at(e)+1;
    }
    for(int j=a;j<D;j++){
      if(rkai.at(j).at(e)==0&&j!=a){
        break;
      }
      else{
        C++;
      }
    }
    Z-=G*C*sage.at(e);
    Z-=man.at(a).at(e);
      if(Z>0){
        for(int j=a;j<D;j++){
      if(rkai.at(j).at(b)==0){
        break;
      }
      else{
        rkai.at(j).at(b)-=K;
      }
    }
        for(int j=a;j<D;j++){
      if(rkai.at(j).at(e)==0&&j!=a){
        break;
      }
      else{
        rkai.at(j).at(e)+=G;
      }
    }
        hini.at(a)=b;
      }
    }
    
  for(int i=0;i<D;i++){
    cout<<hini.at(i)+1<<endl;
  }
}

Measured memory_bytes: 3724
#[allow(unused_imports)]
use std::cmp::Ordering::{Equal, Greater, Less};
#[allow(unused_imports)]
use std::cmp::{max, min};
#[allow(unused_imports)]
use std::collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque};
#[allow(unused_imports)]
use std::io::{stdin, stdout, BufWriter, Write};
#[allow(unused_imports)]
use std::iter::FromIterator;

// author: Seong Yong-ju <sei40kr@gmail.com>

macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        println!(concat!($(stringify!($a), " = {:?}, "),*), $($a),*);
    }
}

fn main() {
    let n: i64;

    input! {
        n: i64,
    };

    let sqrt_n = (n as f64).sqrt() as i64;

    let mut divisors = (1..sqrt_n + 1)
        .filter(|k| n % k == 0)
        .flat_map(|k| vec![k, n / k])
        .collect::<Vec<_>>();
    divisors.sort();
    divisors.dedup();

    let ans = divisors
        .into_iter()
        .map(|d| d - 1)
        .filter(|&k| k != 0 && n / k == n % k)
        .sum::<i64>();

    println!("{}", ans);
}


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

signed main(){
  int a, b, c, d;
  cin >> a >> b >> c >> d;
  cout << max({a * c, a * d, b * c, b * d}) << endl;
}

Measured memory_bytes: 3636
#!/usr/bin/env python3
import sys

YES = "Yes"  # type: str
NO = "No"  # type: str

def solve(S):
    s = list(set(list(S)))
    if len(s) == 2 and S.count(s[0]) == 2:
        print("Yes")
    else:
        print("No")
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    S = next(tokens)  # type: str
    solve(S)

if __name__ == '__main__':
    main()


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

#define ll long long
#define endl '\n'
#define N 1e5+1;
#define INF 1e9

const ll MOD = 10e9+7;
ll max(ll a, ll b){return a > b ? a : b;}
ll min(ll a, ll b){return a < b ? a : b;}

vector<int> ans;
ll a[200001];
ll b[200001];
vector<int> sorted;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n; string str; ll ans=0; int w=0;
    cin >> n >> str;
    for(int i=0; i<n; i++)
        if(str[i] == '.') w++;
    int b=0;
    int m=w;
    for(int i=0; i<n; i++)
    {
        if(str[i]=='#')
            b++;
        else w--;
        m=min(m, w+b);
    }
    cout << m;
}





Measured memory_bytes: 720
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define REP(i, a, n) for (int i = a; i < (n); i++)
#define rrep(i, n, k) for (int i = (n); i >= (k); i--);
#define all(x) (x).begin(), (x).end()
#define vi vector<int>
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}
template<class T, class... Ts>auto make_vector(size_t a, Ts... ts){return vector<decltype(make_vector<T>(ts...))>(a, make_vector<T>(ts...));}
const int MOD = 1e9 + 7;
const int INF = 2e18;

signed main() {
    int N;
    cin >> N;
    vector<int> A(N);
    cin >> A;
    sort(A.begin(), A.end());
    vector<int> B(N);
    auto calc = [&]() {
        int temp = 0;
        for (int i = 1; i < N; i++) temp += abs(B[i - 1] - B[i]);
        return temp;
    };
    int ans = 0;
    if (N % 2 == 0) {
        for (int i = 0; i < N / 2; i++) {
            B[i * 2 + 1] = A[i];
            B[i * 2] = A[i + N / 2];
        }
        ans = max(ans, calc());
    } else {
        for (int i = 0; i < N / 2; i++) {
            B[i * 2 + 1] = A[i];
            B[i * 2] = A[i + N / 2 + 1];
        }
        B[N - 1] = A[N / 2];
        ans = max(ans, calc());

        for (int i = 0; i < N / 2; i++) {
            B[i * 2 + 2] = A[i];
            B[i * 2 + 1] = A[i + N / 2 + 1];
        }
        B[0] = A[N / 2];
        ans = max(ans, calc());
    }
    cout << ans << endl;
}


Measured memory_bytes: 1792
#include <iostream>
#include <vector>

using namespace std;

int main() {

    int N, M, C;
    cin >> N;
    cin >> M;
    cin >> C;

    vector<int> B(M);
    for (int i = 0; i < M; ++i) {
        cin >> B.at(i);
    }

    vector<vector<int>> A(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> A.at(i).at(j);
        }
    }

    int count = 0;
    for (int i = 0; i < N; i++) {
        int wa = 0;
        for (int j = 0; j < M; j++) {
            wa += A.at(i).at(j) * B.at(j);
        }

        if ((wa + C) > 0) {
            count ++;
        }
    }

    cout << count;
    return 0;
}

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

int main(){
    char c;

    cin >> c;

    if(c=='a'||c=='i'||c=='u'||c=='e'||c=='o'){
        cout << "vowel" << endl;
    }
    else{
        cout << "consonant" << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>

int main()
{
int A,B;
std::cin >> A >> B;

if(A == B)
{
std::cout << "Draw" << std::endl;
}
else if(A == 1)
{
std::cout << "Alice" << std::endl;
}
else if(B == 1)
{
std::cout << "Bob" << std::endl;
}
else if(A > B)
{
std::cout << "Alice" << std::endl;
}
else
{
std::cout << "Bob" << std::endl;
}

return 0;
}

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

template<typename T_char>
T_char ToUpper(T_char cX){return toupper(cX);}

int main(){
  int n, T; cin >> n >> T;
  vector<int> c(n), t(n);

  for(int i=0; i<n; ++i) cin >> c[i] >> t[i];

  int mn = 1001, cnt = 0;
  for(int i=0; i<n; ++i){
    if(t[i] <= T){
      mn = min(c[i], mn);
      cnt++;
    }
  }
  if(cnt == 0) cout << "TLE";
  else cout << mn;
}  


Measured memory_bytes: 3628
N, M = map(int, input().split())

ans = [0]*M

for i in range(N):
    K, *A = map(int, input().split())
    for j in range(K):
        ans[A[j]-1] = ans[A[j]-1] + 1

count = 0

for i in range(M):
    if ans[i]==N:
        count = count + 1

print(count)


Measured memory_bytes: 3060
import java.util.*;
import static java.lang.Integer.*;
import static java.lang.Long.*;
import static java.lang.Math.*;
import static java.lang.System.*;

public class Main {
	public static void main(String[] args) {
		int i,j;
		Scanner sc = new Scanner(in);
		int n = parseInt(sc.next());
		int a = parseInt(sc.next());
		int b = parseInt(sc.next());
		sc.close();
		out.println(abs(b-a)%2==1?"Borys":"Alice");
	}
}


Measured memory_bytes: 21844
/*The woods are lovely, dark and deep,
But I have promises to keep,
And miles to go before I sleep,
And miles to go before I sleep.*/

//PRABHJOT SINGH A.K.A. PRABHI
//~~~~~conquizztador~~~~~


#include<bits/stdc++.h>
using namespace std;
using lli = long long int;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
const int MOD = 1000000007;
const int MOD1 = 998244353;
const int maxn = 100010;
const int lim = (int)1e9;
int dp[2 * maxn][2];
int pre[2];
int GET(int val)
{
	if (val == 0)
		return 0;
	return GET(val % __builtin_popcount(val)) + 1;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n = 0; string s;
	cin >> n;
	cin >> s;
	int ones = count(s.begin(), s.end(), '1');
	int x = ones + 1, y = ones - 1;
	if (y != 0)
		dp[n - 1][0] = 1 % y;
	dp[n - 1][1] = 1 % x;
	for (int i = n - 2; i >= 0; --i)
	{
		if (y != 0)
			dp[i][0] = (2 * dp[i + 1][0]) % y;
		dp[i][1] = (2 * dp[i + 1][1]) % x;
	}
	for (int i = 0; i < n; ++i)
	{
		if (s[i] == '1')
		{
			if (y != 0)
			{
				pre[0] += dp[i][0];
				pre[0] %= y;
			}
			pre[1] += dp[i][1];
			pre[1] %= x;
		}
	}
	for (int i = 0; i < n; ++i)
	{
		int z = 0;
		if (s[i] == '1')
		{
			z = pre[0] - dp[i][0];
			if (z < 0)
				z += y;
		}
		else
		{
			z = pre[1] + dp[i][1];
			if (z >= x)
				z -= x;
		}
		if (s[i] == '1' && ones == 1)
			cout << "0" << endl;
		else
			cout << (GET(z) + 1) << endl;
	}
}

Measured memory_bytes: 5296
#include <iostream>
#include <cstring>

using namespace std;
int dp[2019];
string s;

int main(){
    cin >> s;
    int len = s.size();
    memset(dp, 0, sizeof(dp));
    dp[s[0]-'0'] = 1;
    long long ans = 0;
    for (int i = 1; i < len; i++){
        int tmp[2019];
        memset(tmp, 0, sizeof(tmp));
        int d = s[i]-'0';
        tmp[d] = 1;
        for (int j = 0; j < 2019; j++){
            int r = (j*10+d)%2019;
            if (r == 0) ans += dp[j];
            tmp[r] += dp[j];
        }
        for (int j = 0; j < 2019; j++) dp[j] = tmp[j];
    }
    cout << ans << endl;
}


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

int main(){
    ve<char> a = {'A','T','G','C'};
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0, cnt = 0;
    rep(i,n){
        bool flag = false;
        rep(cn,4){
            if(s[i] == a[cn]){
                cnt++;
                flag = true;
            }
        }
        if(flag) continue;
        ans = max(ans,cnt);
        cnt = 0;
    }
    ans = max(ans,cnt);
    cout << ans << endl;
    return 0;
}

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

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

using namespace std;
using ll = long long;
int mod = 1000000007;

void solve();

int main(void){
    int N, Z, W;
    cin >> N >> Z >> W;
    int A[N]; rep(i, N) cin >> A[i];
    if(N == 1) cout << abs(A[0]-W) << endl;
    else{
        cout << max( abs(A[N-1]-A[N-2]), abs(A[N-1]-W)) << endl;
    }
    return 0;
}

void solve(){}

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

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// Yes-Noを出力する問題で楽をする
void Ans(bool f){
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

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

int main(){
    ll n,m,x; cin >> n >> m >> x;
    VL c(n);
    VVL a(n, VL(m,0));
    rep(i,n){
        cin >> c[i];
        rep(j,m){
            cin >> a[i][j];
        }
    }

    ll ans = 10000000;
    ll all = 2 << n;
    
    rep(bit, all){
        ll cost = 0;
        VL know(m,0);
        rep(i,n){
            if(bit & (1 << i)){
                cost += c[i];
                rep(j,m){
                    know[j] += a[i][j];
                }
            }

            bool flag = true;
            rep(j,m){
                if(know[j] < x){
                    flag = false;
                    break;
                }
            }

            if(flag) chmin(ans, cost);
        }
    }

    if(ans == 10000000) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3636
#include<bits/stdc++.h>
#define ll long long
#define cla(a,b) memset(a,b,sizeof a)
using namespace std;
inline char nc()
{
    static char buf[100000],*p1=buf,*p2=buf;
    if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }
    return *p1++;
}
//#define  getchar() nc()
inline int read()
{
	int x = 0 , f = 1; char CH = getchar();
	while(CH<'0'||CH>'9') {if(CH=='-')f=0;CH=getchar();}
	while(CH>='0'&&CH<='9') {x=(x<<3)+(x<<1)+(CH-48);CH=getchar();}
	return f ? x : -x;
}
const int N=206;
int Q,n,m,vis[31];
inline bool work()
{
    int i,j;
    int ff,tot2,tot4=(n>>1)*(m>>1);
    if( (!(n&1)) && (!(m&1)) )		tot2=0;
    else if( (n&1) && (m&1) )		tot2=(n>>1)+(m>>1);
    else if( (n&1) && (!(m&1)) )	tot2=(m>>1);
    else tot2=(n>>1);
    for(i=1;i<=tot4;++i)
    {
    	ff=0;
        for(j=0;j<26;++j)
            if(vis[j]>=4)
            {
                ff=1; vis[j]-=4;
                break;
            }
        if(!ff) return false;
    }
    for(i=1;i<=tot2;++i)
    {
    	ff=0;
        for(j=0;j<26;++j)
            if(vis[j]>=2)
            {
                ff=1; vis[j]-=2;
                break;
            }
        if(!ff) return false;
    }
    return true;
}

int main(){
#ifdef	iloi 
	freopen("quilt6.in","r",stdin);
#endif
//  freopen("quilt.in","r",stdin);
//	freopen("quilt.out","w",stdout);
    int i,j;
    Q=1;
    while(Q--)
    {
        n=read(),m=read();
        char s[203][203];
        memset(vis,0,sizeof vis);
        for(i=1;i<=n;++i)	scanf("%s",s[i]+1);
        for(i=1;i<=n;++i)for(j=1;j<=m;++j) vis[s[i][j]-'a']++;
        if(work())
            printf("Yes\n");
        else
            printf("No\n");
    }
}

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

namespace Algorithm
{
    class Program
    {
        static void Main(string[] args)
        {

            var N = int.Parse(Console.ReadLine());
            var A = Console.ReadLine().Split().Select(int.Parse).ToArray();

            var set = new HashSet<int>();
            for (var i = 0; i < N; i++)
            {
                set.Add(A[i]);
            }

            Console.WriteLine(N == set.Count ? "YES" : "NO");
        }
    }
}


Measured memory_bytes: 42292
import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto N = readln.chomp.to!int;
    int[][][] MEMO;
    MEMO.length = N;
    foreach (i; 0..N) {
        auto A = readln.chomp.to!int;
        MEMO[i].length = A;
        foreach (j; 0..A) {
            auto xy = readln.split.to!(int[]);
            xy[0] -= 1;
            MEMO[i][j] = xy;
        }
    }

    int r;
    foreach (s; 0..(1<<N)) {
        int c;
        foreach (j; 0..N) if (s & (1<<j)) {
            ++c;
            foreach (xy; MEMO[j]) {
                auto x = xy[0];
                auto y = xy[1];
                if (!!(s & (1<<x)) != !!y) goto ng;
            }
        }
        r = max(r, c);
        ng:
    }
    writeln(r);
}

Measured memory_bytes: 256
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
A = [i - 1 for i in A]
res = B[A[0]]
for i in range(1,N):
    res += B[A[i]]
    if A[i] - A[i - 1] == 1:
        res += C[A[i - 1]]
print(res)
    

Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = (ll)1000000007 * 1000000007;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef long double ld;
typedef complex<ld> Point;
const ld eps = 1e-11;
const ld pi = acos(-1.0);
typedef pair<ll, ll> LP;
typedef pair<ld, ld> LDP;
typedef unsigned long long ul;

ll a[1 << 18];
stack<ll> num;
stack<int> id;
ll sum = 0;
void inse(ll n, int i) {
	if (n == 0)return;
	if ((!id.empty()) && id.top() == i) {
		num.top() += n;
	}
	else {
		num.push(n); id.push(i);
	}
}
void init() {
	sum = 0;
	while (!num.empty())num.pop();
	while (!id.empty())id.pop();
}
int main() {
	int n; cin >> n;
	rep(i, n) {
		cin >> a[i];
	}
	int le = 0; int ri = n + 1;
	while (ri - le > 1) {
		init();
		bool valid = true;
		int c = (ri+le)/2;
		//num.push(a[0]); id.push(1); sum = a[0];
		rep(i, n) {
			if (a[i] > sum) {
				inse(a[i] - sum, 1);
			}
			else {
				ll memo; int x;
				while (sum >= a[i]) {
					sum -= num.top();
					memo = num.top(); x = id.top();
					num.pop(); id.pop();
				}
				if (x + 1 <= c) {
					inse(a[i] - sum - 1, x);
					inse(1, x + 1);
				}
				else {
					ll loc;
					while (true) {
						loc = sum;
						if (!num.empty()) {
							memo = num.top();
							x = id.top(); sum -= num.top();
							num.pop(); id.pop();
							if (x + 1 <= c) {
								inse(loc - sum - 1, x);
								inse(1, x + 1);
								inse(a[i] - loc, 1);
								break;
							}
						}
						else {
							valid = false;
							break;
						}
					}
				}
			}
			sum = a[i];
			if (!valid)break;
			//cout << sum << endl;
		}
		if (valid)ri = c;
		else le = c;
	}
	//cout << num.size() << endl;
	cout <<ri<< endl;
	return 0;
}


Measured memory_bytes: 1792
#include <iostream>

using namespace std;

int main()
{
	unsigned long w, h, x, y;
	cin >> w >> h >> x >> y;

	cout << (long double)w * (long double)h / 2;
	
	if (w == x + x && h == y + y)
	{
		cout << " 1" << endl;
	}
	else
	{
		cout << " 0" << endl;
	}
	return 0;
}

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

using namespace std;
const int N = 1e5 + 5;

int nn, n;
int a[N << 1];

int small(int x, int y, int k) {
	return (a[x] <= k && a[y] <= k);
}

int big(int x, int y, int k) {
	return (a[x] > k && a[y] > k);
}

bool check(int k) {
	if (small(n, n - 1, k) || small(n, n + 1, k)) return 0;
	if (big(n, n - 1, k) || big(n, n + 1, k)) return 1;
	for (int i = 1; i < n - 1; i ++) {
		if (small(n - i, n - i - 1, k) || small(n + i, n + i + 1, k)) return 0;
		if (big(n - i, n - i - 1, k) || big(n + i, n + i + 1, k)) return 1;
	}
	return big(1, 1, k);
}

int main() {
	scanf("%d", &n);
	nn = 2 * n - 1;
	for (int i = 1; i <= nn; i ++) scanf("%d", &a[i]);
	int l = 1, r = nn, pos;
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) l = mid + 1;
		else r = mid;
	}
	printf("%d\n", r);
	return 0;	
}

Measured memory_bytes: 1152
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD = (int)1e9 + 7;
int INF = (int)2e18;
// Comment out below and program paste
// #include "UnionFind.h"
// #include "power.h"

signed main() {
    int a, b;
    cin >> a >> b;
    if (a > 0 && b > 0) {
        cout << "Positive" << endl;
    } else {
        if (a < 0 && b < 0) {
            int temp = b - a + 1;
            if (temp % 2 == 0) cout << "Positive" << endl;
            else cout << "Negative" << endl;
        } else {
            cout << "Zero" << endl;
        }
    }
}

Measured memory_bytes: 256
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Nikita Mikhailov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        DSumOfLargeNumbers solver = new DSumOfLargeNumbers();
        solver.solve(1, in, out);
        out.close();
    }

    static class DSumOfLargeNumbers {
        long mod = (long) 1e9 + 7;

        private long calc(long n, long k) {
            return ((n - k) * k + 1) % mod;
        }

        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.readInt() + 1;
            int k = in.readInt();

            long ta = 0;

            for (int i = k; i <= n; i++) {
                ta = (ta + calc(n, i)) % mod;
            }
            out.println(ta);

        }

    }

    static class FastScanner {
        private StringTokenizer st;
        private BufferedReader in;

        public FastScanner(final InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
        }

        public String readToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (final IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int readInt() {
            return Integer.parseInt(readToken());
        }

    }
}



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

// @author: pashka

int main() {
    ios::sync_with_stdio(false);

    int n, x, y;
    cin >> n >> x >> y;
    x--; y--;
    vector<int> cnt(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int d = min(abs(i - j), abs(i - x) + 1 + abs(j - y));
            cnt[d]++;
        }
    }
    for (int i = 1; i < n; i++) {
        cout << cnt[i] << "\n";
    }

    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int x, y;
    cin >> x >> y;
    if(y%2) {
        puts("No");
        return 0;
    }
    y /= 2;

    if(x <= y && y <= x*2) puts("Yes");
    else puts("No");
    return 0;
}

Measured memory_bytes: 3636
#include <stdio.h>
#include <math.h>
int isprime(int);
int main(){
  int a,j,n[10000],count=0;
  scanf("%d",&a);
  for(j=0;j<a;j++){
    scanf("%d",&n[j]);
    if(isprime(n[j])==0)
      count++;
  }
  printf("%d\n",count);
  return 0;
}
int isprime(n)
{
  int i=3;
  if (n==2) 
    return 0;
  if  (n<2||n%2==0)
    return 1;
  while (i<=sqrt(n)){
    if (n%i==0)
      return 1;
    i = i + 2;
  }
  return 0;
}

Measured memory_bytes: 632
# -*- coding:utf-8 -*-
from math import factorial

def solve():
    N, M = list(map(int, input().split()))
    MOD = 10**9+7
    """
    ありうるパターンは、
    
    ・NとMが同数
    ・NとMの差が1

    （例）
    ・2 2
    犬 猿 犬 猿
    この場合、犬と猿の位置を入れ替えたパターンもあるので×2

    ・2 3
    犬 猿 犬 猿 犬

    組み合わせの数は、順列の公式を使う
    
    ・順列の公式
    異なるn個のものからr個を取り出し並べる場合の数は
    nPr = n(n-1)(n-2)...(n-r+1) = n!/(n-r)!
    """

    def permutation_formula(n, r):
        return factorial(n) // factorial(n-r)

    if N == M:
        ans = (permutation_formula(N, N)%MOD) * (permutation_formula(M, M)%MOD) * 2
        print(ans%MOD)
        return
    elif abs(N-M) == 1:
        ans = (permutation_formula(N, N)%MOD) * (permutation_formula(M, M)%MOD)
        print(ans%MOD)
    else:
        print(0)
        return


if __name__ == "__main__":
    solve()


Measured memory_bytes: 4156
#include <iostream>

using namespace std;

int main() {

	while(true) {
		int n,s;
		cin >> n >> s;
		if (!n && !s) break;

		int ans = 0;

		for (unsigned i = 0; i < 1<<10; ++i) {
			int sum = 0, cnt = 0;
			for(unsigned j = 0; j < 10; ++j) {
				if ((i>>j)&1) {
					sum += j;
					cnt++;
				}
			}

			if (sum == s && cnt == n) ans++;
		}

		cout << ans << endl;
	}

	return 0;
}

Measured memory_bytes: 1160
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(x) x.begin(), x.end()
using namespace std;
typedef long long ll;
typedef pair<int, int> pair;
const int inf = 1000000000; //10^9
const ll inff = 1000000000000000000; //10^18

int main(){
    int a, b, c;
    cin >> a>> b>> c;
    if ((a < b) && (b < c)) cout << "Yes" << endl;
    else cout << "No" << endl;

    return 0;
}


Measured memory_bytes: 3088
N, M = list(map(int, input().split()))

WAs = [0] * (N + 1)
ACs = [0] * (N + 1)
for m in range(M):
  key, value = input().split()
  key = int(key)
  if value == 'WA' and ACs[key] == 0:
    WAs[key] += 1
  if value == 'AC':
    ACs[key] = 1

countWAs, countACs = 0, 0
for n in range(N + 1):
  if ACs[n] >= 1:
    countACs += ACs[n]
    countWAs += WAs[n]

#print(ACs)
#print(WAs)
print(str(countACs) + ' ' + str(countWAs))

Measured memory_bytes: 4596
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <numeric>
#include <functional>
#define REP(i, n) for(int i=0;i<n;++i)
#define INF 100000000
#define ll long long

using namespace std;

typedef pair<int, int> P;

int main(){
  int a, b;
  int m1, m2, n1, n2;
  int aa, bb, aaa, bbb;
  cin >> a >> b;

  m1 = a / 1000;
  m2 = (m1 % 10) * 10 + (m1/ 10);
  aa = a % 100;
  if(aa <= m2){
    aaa = a / 100;
  }else{
    aaa = a / 100 + 1;
  }

  n1 = b / 1000;
  n2 = (n1 % 10) * 10 + (n1/ 10);
  bb = b % 100;
  if(bb >= n2){
    bbb = b / 100;
  }else{
    bbb = b / 100 - 1;
  }

  cout << bbb - aaa + 1 << endl;

  return 0;
}

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

int N;
int *lst;

int main(){
    cin>>N;lst = new int[N-1];
    for(int i=0;i<N-1;i++){
        cin>>lst[i];
    }
    vector<int> V;
    for(int i=0;i<N-1;i++){
        auto it_1 = V.end()-1;
        if(i==0){
        V.push_back(lst[i]);
        V.push_back(lst[i]);
        }else{
            *it_1 = (min(*it_1,lst[i]));
            V.push_back(lst[i]);
        }
    }
    long long sum=0;
    auto it = V.begin();
    for(int i=0;i<N;i++){
        sum+=*it;
        it++;
    }
    cout<<sum<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#define NUM 255
using namespace std;
typedef long long ll;
#define int ll
int min(int a,int b){
  return (a<b)?a:b;
}
signed main(){
  int n,m,y,num,ma_c,mi_c;
  cin >> n >> m;
  while(n!=0){
   int c[m],x[n],low=100000000; 
   ma_c=-300,mi_c=300;
   vector<int> dp[20001];
    for(int i=0;i<m;i++){
      cin >> c[i];
      ma_c=(ma_c<c[i])?c[i]:ma_c;
      mi_c=(mi_c>c[i])?c[i]:mi_c;
    }
    for(int i=0;i<n;i++){
      cin >> x[i];
    }
    for(int i=0;i<=n;i++){
      for(int j=0;j<=NUM;j++){
        dp[i].push_back(-1);
      }
    }
    dp[0][128]=0;
    for(int i=1;i<=n;i++){
      for(int j=NUM-ma_c;j<=NUM;j++){
        if(dp[i-1][j]!=-1){
          if(dp[i][NUM]==-1)dp[i][NUM]=dp[i-1][j]+(x[i-1]-NUM)*(x[i-1]-NUM);
          else dp[i][NUM] = min(dp[i-1][j]+(x[i-1]-NUM)*(x[i-1]-NUM),dp[i][NUM]);
        } 
      }
      for(int j=-mi_c;j>=0;j--){
        if(dp[i-1][j]!=-1){
          if(dp[i][0]==-1)dp[i][0]=dp[i-1][j]+(x[i-1])*(x[i-1]);
          else dp[i][0] = min(dp[i-1][j]+(x[i-1])*(x[i-1]),dp[i][0]);
        } 
      }
      for(int j=0;j<=NUM;j++){
        for(int k=0;k<m;k++){
          num=j-c[k];
          if(num<0) continue;
          else if(num>NUM)continue;
          if(dp[i-1][num]!=-1){
            if(dp[i][j]==-1) dp[i][j]=dp[i-1][num]+(x[i-1]-j)*(x[i-1]-j);
            else dp[i][j]=min(dp[i-1][num]+(x[i-1]-j)*(x[i-1]-j),dp[i][j]);
          }
        }
//        cout << i<<" "<<j<<" "<<dp[i][j]<<endl;
      }
    }
//    for(int i=0;i<=n;i++){for(int j=0;j<=NUM;j++)cout <<dp[i][j]<<" ";cout << endl;}
    for(int i=0;i<=NUM;i++){
      if(dp[n][i]!=-1){
        low=min(low,dp[n][i]);
      }
    }
    cout << low<<endl;
    cin >> n >> m;
  }
}



Measured memory_bytes: 43876
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main() {
	int n;
	cin >> n;
	vector<int> d(n);
	rep(i, n) cin >> d[i];
	sort(all(d));
	ll ans = d[n/2] - d[n/2-1];
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
N = int(input()) #人数

state = []
for _ in range(N):
    A = int(input())
    for i in range(A):
        x, y = map(int, input().split())
        state.append([_, x-1, y])

ans = 0
import itertools
for i in itertools.product([1,0], repeat=N):
    tmp = sum(list(i))
    for j in state:
        if i[j[0]] == 1 and i[j[1]] != j[2]:
            tmp = 0
            break
    ans = max(ans, tmp)
print(ans)


Measured memory_bytes: 3064
//////////////////////////////
// Author: whatisit
// Date: 2020-05-14 21:28 
//////////////////////////////
#include <bits/stdc++.h>
using namespace std;

const int N = 101;
int x[N], ans = 1e9, n;

void solve() {
	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> x[i];
	}
	for (int i = 1; i <= 100; ++i) {
		int cur_dist = 0;
		for (int j = 0; j < n; ++j) {
			cur_dist += (x[j] - i) * (x[j] - i);
		}
		ans = min(cur_dist, ans);
	}
	cout << ans;
}

int main() {
	//cin.tie(0); ios_base::sync_with_stdio(0);
	solve();
	return 0;
}

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

string divide[4] = {"dream", "dreamer", "erase", "eraser"};
bool dp[100010];

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

    dp[0] = 1;
    for(int i = 0; i < S.size(); ++i){
        if(!dp[i])continue; // そこまでで矛盾があったらとりあえず無視
        for(string s : divide){
            if(S.substr(i, s.size()) == s){ // うまく切れたら先に進む
                dp[i + s.size()] = 1;
            }
        }
    }
    cout << (dp[S.size()] ? "YES" : "NO") << endl;
    return 0;
}


Measured memory_bytes: 512
#include <iostream>

int main() {
	int n, i;
	std::cin >> n;
	int array[n];
	
	for(i=0; i<n; i++) {
		std::cin >> array[i];
	}
	for(i=n-1; i>0; i--) {
		std::cout << array[i] << " ";
	}
	std::cout << array[0] << std::endl;
}

Measured memory_bytes: 1164
#include <iostream>
#include <string>
using namespace std;
int main()
{
    string s;
    cin >> s;
    int sc = 0, ans = s.size();
    for (auto c : s)
    {
        if (c == 'S')
            ++sc;
        if (c == 'T')
        {
            if (sc > 0)
            {
                --sc;
                ans -= 2;
            }
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define LL long long
#define Max 100005
#define Mod 1e9+7
const LL mod=1e9+7;
const LL inf=0x3f3f3f3f;
using namespace std;
int main()
{
    int h,w,H,W;
    scanf("%d%d%d%d",&H,&W,&h,&w);
    printf("%d\n",(H-h)*(W-w));
    return 0;
}


Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline


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


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


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


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


def read_str():
    return input().strip()


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


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

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

        error_print(e - s, 'sec')
        return ret

    return wrap


def BellmanFord(N, e, s, goal):
    dist = [sys.maxsize] * (N+1)
    dist[s] = 0
    for i in range(N+1):
        for u, v, c in e:
            if dist[v] > dist[u] + c:
                if i == N:
                    return 'inf'
                dist[v] = dist[u] + c
    return dist

@mt
def slv(N, M, P, ABC):
    g = [[] for _ in range(N+1)]
    for a, b, c in ABC:
        g[a].append(b)

    def r(s, e):
        q = deque()
        q.append(s)
        done = set([s])
        while q:
            u = q.popleft()
            for v in g[u]:
                if v not in done:
                    done.add(v)
                    q.append(v)
        return done

    d = set()
    for i in range(2, N):
        reachable = r(i, N)
        if N not in reachable:
            d.add(i)
    
    e = []
    sr = r(1, N)
    for a, b, c in ABC:
        if a not in d and b not in d and a in sr and b in sr:
            e.append((a, b, -(c - P)))

    d = BellmanFord(N, e, 1, N)
    if d == 'inf':
        return -1
    return max(0, -d[N])


def main():
    N, M, P = read_int_n()
    ABC = [read_int_n() for _ in range(M)]
    print(slv(N, M, P, ABC))

    # N = 2500
    # M = 5000
    # P = random.randint(0, 10**5)
    # P= 0
    # ABC = [
    #     [random.randint(1, N), random.randint(1, N), random.randint(1, 10**5)] for _ in range(M)
    # ]
    # print(slv(N, M, P, ABC))



if __name__ == '__main__':
    main()


Measured memory_bytes: 92760
//ex9_2
//TKC001

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 100000

typedef struct stack{
    char num;
    struct stack *next;
}stack;

void push(stack **stk, char num){
    stack *new = calloc(1, sizeof(stack));
    if(new == NULL) exit(1);

    new->num = num;
    new->next =*stk;
    *stk = new;
}

char pop(stack **stk){
    char num;
    stack *tmp = *stk;
    if(tmp == NULL) exit(1);
    num = tmp->num;
    *stk = tmp->next;

    free(tmp);
    return num;
}


int main(void){
    int i, count = 0;
    stack *stk = NULL, *comp = NULL;
    char str[SIZE+1], last, prelast, fromcomp;
    //入力
    scanf("%s", str);
    //スタックに文字列を追加
    for(i = 0; i < strlen(str); i++){
        push(&stk, str[i]);
    }

    if(strlen(str) == 1){
        count = 0;
    }
    else{
        while (1){
            last = pop(&stk);
            prelast = pop(&stk);
            //lastとprelastが同じならcompに移動、違ったら消し、countを増やす。
            if(last == prelast){
                push(&comp, last);
                push(&stk, prelast);
            }
            else{
                count++;
                //compの最後の要素はstkの最後の要素と隣り合うのでstkに移動
                if(comp != NULL){
                    fromcomp = pop(&comp);
                    push(&stk, fromcomp);
                }
            }

            if(stk == NULL || stk->next == NULL) break;
        }
    }
    //出力
    printf("%d", count*2);
  
    return 0;
}

Measured memory_bytes: 4952
#include <bits/stdc++.h>
#include <math.h>
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rrep(i, n) for(int i = 0; i <= (n); i++)
using namespace std;
typedef long long ll;
 
const ll INF = 1LL<<60;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
using Graph = vector<vector<int>>;

typedef pair<int, int> P;
typedef priority_queue<int, vector<int>, greater<int>> PQ;
const int MOD = 1000000007;

int main(){
   int N; cin >> N;
   vector<ll> A(N);
   rep(i,N) cin >> A[i];

   sort(A.begin(), A.end(), greater<ll>());
   ll ans = 0;
   ll dec = 0;
   rep(i,N){
       if (i == 0) continue;
       ans += A[dec];
       if (i%2==1)dec++;
   }
   cout << ans << endl;
}

Measured memory_bytes: 4840
#include <iostream>
#include <string>
#include <cmath>
using namespace std;

int x_0, y_0, x_1, y_1;
int q;
int x, y;

int choice();
int gaiseki(int, int, int, int);
int naiseki(int, int, int, int);
double norm(int, int);
int main(){
  cin >> x_0 >> y_0 >> x_1 >> y_1;

  cin >> q;
  string s[] = {"COUNTER_CLOCKWISE", "CLOCKWISE", "ONLINE_BACK", "ON_SEGMENT", "ONLINE_FRONT"};

  for(int i=0; i<q; i++){
    cin >> x >> y;
    cout << s[choice()] << endl;
  }

  return 0;
}

int choice(){
  if(gaiseki(x_1-x_0, y_1-y_0, x-x_0, y-y_0)>0) return 0;
  else if(gaiseki(x_1-x_0, y_1-y_0, x-x_0, y-y_0)<0) return 1;
  else{
    if(naiseki(x_1-x_0, y_1-y_0, x-x_0, y-y_0)<0){
      return 2;
    }else{
      if(norm(x-x_0, y-y_0)<=norm(x_1-x_0, y_1-y_0)) return 3;
      else return 4;
    }
  }
}

int gaiseki(int ax, int ay, int bx, int by){
  return ax*by - ay*bx;
}

int naiseki(int ax, int ay, int bx, int by){
  return ax*bx + ay*by;
}

double norm(int ax, int ay){
  return sqrt(ax*ax+ay*ay);
}



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

void solve()
{
    int x;
    cin >> x;
    vector<int> a;
    a.push_back(1);
    for (int i = 2; i <= 1000; i++)
    {
        for (int j = i * i; j <= 1000; j *= i)
        {
            a.push_back(j);
        }
    }
    sort(a.begin(), a.end());
    int ans = 0;
    if (x == *lower_bound(a.begin(), a.end(), x))
        ans = x;
    else
        ans = a[lower_bound(a.begin(), a.end(), x) - a.begin() - 1];
    cout << ans << endl;
}

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

Measured memory_bytes: 3608
def cat_snuke_and_a_voyage(N: int, M: int, ships: list)->bool:
    passable = [(False, False)] * (N-2)
    for a, b in ships:
        if a == 1:
            _, bN = passable[b-2]
            passable[b-2] = (True, bN)
            if bN:
                return True
        elif b == N:
            a1, _ = passable[a-2]
            passable[a-2] = (a1, True)
            if a1:
                return True
    return False


if __name__ == "__main__":
    M = 0
    N, M = map(int, input().split())
    ships = [tuple(map(int, input().split())) for _ in range(M)]
    yes = cat_snuke_and_a_voyage(N, M, ships)
    print('POSSIBLE' if yes else 'IMPOSSIBLE')


Measured memory_bytes: 41152
k = int(input())
s = input()
n = len(s)

mod = 10 ** 9 + 7
N = 2 * 10 ** 6 + 10

#逆元テーブル
inv_t = [0]+[1]
for i in range(2, N):
  inv_t += [inv_t[mod % i] * (mod - int(mod / i)) % mod]

#階乗計算
kai = [1, 1]
rev_kai = [1, inv_t[1]]
for i in range(2, N):
	kai.append(kai[-1] * i % mod)
	rev_kai.append(rev_kai[-1] * inv_t[i] % mod)

# コンビネーション計算
def cmb(n, r):
	return kai[n] * rev_kai[r] * rev_kai[n-r] % mod

dpi = 1

memo = [1]
for i in range(N):
    memo.append(memo[-1]*25 % mod)

for i in range(1, k+1):
    dpi = (dpi * 26) % mod + (cmb(n+i-1,n-1) * memo[i]) % mod
    dpi %= mod

print(dpi)

Measured memory_bytes: 234024
#include <stdio.h>
  
#define N 8
#define FREE 1
#define NOT_FREE -1

void putQueen(int);
void printBoard(void);
  
int Q[N][N];
int row[N],col[N],dpos[2*N-1],dneg[2*N-1];

void putQueen(int i){
  int j;
  if(i == N){
    printBoard();
    return;
  }

  for(j = 0; j < N; j++){
    if(col[j] == NOT_FREE || dpos[i+j] == NOT_FREE || dneg[i-j+N-1] == NOT_FREE) continue;
    row[i] = j;
    col[j] = dpos[i+j] = dneg[i-j+N-1] = NOT_FREE;
    putQueen(i+1);
    col[j] = dpos[i+j] = dneg[i-j+N-1] = FREE;
  }
}
    

void printBoard() {
    int i,j;
      
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            if(Q[i][j]) {
                if(row[i]!=j) return;
            }
        }
    }
      
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++) {
            if(row[i]==j) printf("Q");
            else printf(".");
        }
        printf("\n");
    }
}

int main() {
    int i,j,k,a,b;
      
    for(i=0; i<N; i++) {
        for(j=0; j<N; j++)
      Q[i][j] = 0;
    }
    scanf("%d",&k);
     
    for(i=0; i<k; i++) {
        scanf("%d%d",&a,&b);
        Q[a][b] = FREE;
    }
      
    for(i=0; i<N; i++) {
        row[i] = FREE;
        col[i] = FREE;
    }
      
    for(i=0; i<20; i++) {
        dpos[i] = FREE;
        dneg[i] = FREE;
    }
      
    putQueen(0);
    return 0;
}

Measured memory_bytes: 572
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <math.h>
#include <memory>
#include <cctype>
#include <cstring>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iomanip>
#include <unordered_set>
#include <unordered_map>
#include <cstdlib>
#include <random>
#include <chrono>
#include<iterator>
#include <locale>
 
/*,---.   ,--.                          ,--.
'   .-'  |  ,---.  ,--.,--. ,--.  ,--. `--'
`.  `-.  |  .-.  | |  ||  |  \  `'  /  ,--.
.-'    | |  | |  | '  ''  '   \    /   |  |
`-----'  `--' `--'  `----'     `--'    `--'*/
 
using namespace std;   
int n;
long long f(int pos, vector<long long> vals){
    if(pos == -1){
        return 0;
    }
    int zero = 0;
    int one = 0;
    vector<long long> zeroVal;
    vector<long long> oneVal;
    for(int i = 0;i<vals.size();i++){
        if(((vals[i])&(1<<pos)) != 0){
            oneVal.push_back(vals[i]);
        }else{
            zeroVal.push_back(vals[i]);
        }
    }
    if(zeroVal.size() == 0 || oneVal.size() == 0){
        return f(pos - 1, vals);
    }else{
        return min(f(pos - 1, zeroVal), f(pos - 1, oneVal)) + (1<<pos);
    }

}
int dp[200047];
int main(){
    int k;
    cin >> n >> k;
    vector<int> value(n);
    for(int i = 0;i<n;i++){
        cin >> value[i];
    }
    for(int i = 1;i<n;i++){
        dp[i] = 2000000000;
        for(int j = 1;j<=k;j++){
            if(i - j < 0){
                break;
            }
            dp[i] = min(dp[i], dp[i-j] + abs(value[i] - value[i - j]));
        }
    }
    cout<<dp[n-1];
    
    

}

Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <map>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <set>
#include <vector>
#include <queue>
#include <list>
#include <numeric>
#include <stdio.h>
#include <string>
#include <cstdlib>
#include <math.h>
#include <stack>
#include <climits>
#include <bitset>
#include <utility>


using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
// const ll INF = 1LL <<60;
const int INF = 10000;

//最小公倍数
ll gcd(ll x, ll y) {
  ll tmp = 0;
  if (x < y){
    tmp=x;
    x=y;
    y=tmp;
  }
  while (y > 0) {
    ll r = x % y;
    x = y;
    y = r;
  }
  return x;
}

//最大公倍数
ll lcm(ll x,ll y){
  return x/gcd(x,y)*y;
}

//階乗
ll kaijo(ll k){
    ll sum = 1;
    for (ll i = 1; i <= k; ++i)
    {
        sum *= i;
        sum%=1000000000+7;
    }
    return sum;
}

//for(int i = ; i < ; i++){}

ll lmax(ll s,ll t){
  if(s>t){
    return s;
  }
  else{
    return t;
  }
}

ll lmin(ll s,ll t){
  if(s<t){
    return s;
  }
  else{
    return t;
  }
}
// ここから開始


int main(){
  int n;
  cin>>n;
  int a[n];
  int sum = 0;
  for(int i = 0; i < n; i++) {
    cin>>a[i];
    sum+=a[i];
  }
  double av = (double)sum/(double)n;
  int av2 = sum/n;
  if(av-av2>0.5) av2++;
  ll ans = 0;
  for(int i = 0; i < n; i++) {
    ans+=pow(a[i]-av2, 2);
  }
  cout<<ans<<endl;
  return 0;
}


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

int main(){
    long long x,y;
    cin>>x>>y;
    int count=0;
    while(x<=y){
        count++;
        x*=2;
    }
    cout<<count<<endl;
}

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

int main(){
    long N;
    cin >> N;
    map<string, int> string_map;
    long res = 0;
    for(int i = 1; i <= N; i++){
        string S;
        cin >> S;
        sort(S.begin(), S.end());
        if(string_map.count(S)){
            res += string_map[S];
            string_map[S]++;
        }
        else{
            string_map[S] = 1;
        }
    }
    cout << res << endl;
}


Measured memory_bytes: 11136
N = int(input())
t = [list(map(int, input().split())) for i in range(N)]

if N == 1:
    if t[0][0] >= t[0][1] + t[0][2]:
        print("Yes")
    else:
        print("No")

else:
    for i in range(1,N):
        a = t[i][0] - t[i-1][0]
        b = abs(t[i][1] - t[i-1][1]) + abs(t[i][2] - t[i-1][2])
        if a >= b and a % 2 == b % 2:
            continue
        else:
            print("No")
            exit()
    print("Yes")

Measured memory_bytes: 27300