akhauriyash/Code-Regression huggingface dataset:
/*** author: yuji9511 ***/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> lpair;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define print2(x,y) cout << (x) << " " << (y) << endl;
#define printa(x,n) for(ll i = 0; i < n; i++){ cout << (x[i]) << " \n"[i==n-1];};
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    ll A[200010], B[200010];
    cin >> N;
    rep(i,0,N){
        cin >> A[i];
    }
    rep(i,0,N) cin >> B[i];
    priority_queue<lpair, vector<lpair> > pq;
    rep(i,0,N) pq.push(make_pair(B[i], i));
    bool ok = true;
    ll ans = 0;
    while(not pq.empty()){
        lpair v = pq.top();
        pq.pop();
        ll idx = v.second;
        ll minus = B[(idx+1)%N] + B[(idx-1+N)%N];
        if(v.first < A[idx]){
            ok = false;
            break;
        }
        ll tt = v.first - A[idx];
        if(tt % minus == 0){
            B[idx] = A[idx];
            ans += tt / minus;
        }else{
            B[idx] -= minus * (tt / minus);
            if((tt/minus) != 0)pq.push(make_pair(B[idx], idx));
            ans += tt / minus;
        }
        // v.first %= minus;
        // B[idx] = v.first;x
        // if()

    }
    // printa(B, N);
    if(not ok){
        print(-1);
        return 0;
    }
    ok = true;
    rep(i,0,N){
        if(A[i] != B[i]){
            print(-1);
            return 0;
        }
    }
    print(ans);

}

Measured memory_bytes: 9584
using System;
using static System.Console;
using static System.Math;
using System.IO;
using System.Collections.Generic;
namespace I_am_the_green_coder{
    class Inonoa{
        // なんか入力用の関数作ったけどまだテストしてないので使う前に確かめて
        static void Main(){
            long n = long.Parse(Console.ReadLine());
            long[] a = ILongs();

            long[] ans = new long[n];


            ans[0] = 0;
            for(long i=0;i<n-1;i+=2){
                ans[0] += a[i];
                ans[0] -= a[i+1];
            }
            ans[0] += a[n-1];

            for(long i=1;i<n;i++){
                ans[i] = 2*a[i-1] - ans[i-1];
            }

            for(int i=0;i<n;i++){
                Console.Write(ans[i]);
                Console.Write(" ");
            }
        }

        static readonly long MOD = 1000000007;

        ///<summary>a_1, a_2, a_3, ...みたいなの</summary>
        static long[] ILongs(){
            string[] s = ReadLine().Split();
            long[] re = new long[s.Length];
            for(long i=0;i<s.Length;i++){
                re[i] = long.Parse(s[i]);
            }
            return re;
        }

        ///<summary>xooxoxoxxoxo...みたいなの</summary>
        static char[] IChars(){
            return ReadLine().ToCharArray();
        }

        ///<summary>n m とかをちょっとはやくかくだけ</summary>
        static string[] IStrings(){
            return ReadLine().Split();
        }

        ///<summary>n行の入力を取ったり</summary>
        static long[][] ILongLongs(long n){
            long[][] re = new long[n][];
            for(long i=0;i<n;i++){
                string[] s = ReadLine().Split();
                re[i] = new long[s.Length];
                for(long j=0;j<s.Length;j++){
                    re[i][j] = long.Parse(s[j]);
                }
            }
            return re;
        }

        ///<summary>n行の文字列を取ったり</summary>
        static char[][] ICharsChars(long n){
            char[][] re = new char[n][];
            for(long i=0;i<n;i++){
                re[i] = ReadLine().ToCharArray();
            }
            return re;
        }
    }
}

Measured memory_bytes: 29240
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int,int> pii;
const int maxn=1e5+7;
const ll modn=1000000007;
const int inf=2e9+7;
const double PI = acos(-1.0);
const double eps=1e-8;
inline int lowbit(int x){return x&-x;}
inline ll lowbit(ll x) {return x&-x;}
inline int CountOneBinary(ll num){int ans=0;while(num){if(num&1) ans+=1;num>>=1;}return ans;}
inline void read(int &x){char c;x=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';}
inline void read(ll &x){char c;x=0;for(c=getchar();c>'9'||c<'0';c=getchar());for(;c>='0'&&c<='9';c=getchar()) x=x*10+c-'0';}
inline ll qpow(ll x,ll y){ll ans=1;while(y){if(y&1) ans=ans*x%modn;x=x*x%modn;y>>=1;}return ans;}
inline double qpow(double x,ll y){double ans=1;while(y){if(y&1) ans=ans*x;x=x*x;y>>=1;}return ans;}
int n,k,d[20];
bool check(int x)
{
    while(x)
    {
        if(d[x%10]) return 0;
        x/=10;
    }
    return 1;
}
int solve()
{
    for(int i=n;i<n*100;i++)
    {
        if(check(i)) return i;
    }
    return -1;
}
int main()
{
    while(scanf("%d%d",&n,&k)==2)
    {
        memset(d,0,sizeof(d));
        for(int i=0;i<k;i++)
        {
            int tmp;
            scanf("%d",&tmp);
            d[tmp]=1;
        }
        printf("%d\n",solve());
    }
}


Measured memory_bytes: 256
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 K = sc.nextInt();
        for(int i=0; i<K; i++) {
            if(i%2==0) {
                if(A%2==0) {
                    A/=2;
                    B+=A;
                }else {
                    A = (A-1)/2;
                    B += A;
                }
            }else {
                if(B%2==0){
                    B/=2;
                    A+=B;
                }else {
                    B=(B-1)/2;
                    A+=B;
                }
            }
        }
        System.out.println(A+" "+B);
    }
}

Measured memory_bytes: 21844
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define rep(i,n) for (int i=0;i<(int)(n);i++)
#define codefor int test;scanf("%d",&test);while(test--)
#define INT(...) int __VA_ARGS__;in(__VA_ARGS__)
#define LL(...) ll __VA_ARGS__;in(__VA_ARGS__)
#define yn(ans) if(ans)printf("Yes\n");else printf("No\n")
#define YN(ans) if(ans)printf("YES\n");else printf("NO\n")
#define vector1d(type,name,...) vector<type>name(__VA_ARGS__)
#define vector2d(type,name,h,...) vector<vector<type>>name(h,vector<type>(__VA_ARGS__))
#define umap unordered_map
#define uset unordered_set
using namespace std;
using ll = long long;
const int MOD=1000000007;
//入力系
void scan(int& a){scanf("%d",&a);}
void scan(long long& a){scanf("%lld",&a);}
template<class T> void scan(T& a){cin>>a;}
template<class T> void scan(vector<T>& vec){for(auto&& it:vec)scan(it);}
void in(){}
template <class Head, class... Tail> void in(Head& head, Tail&... tail){scan(head);in(tail...);}
//出力系
void print(const int& a){printf("%d",a);}
void print(const long long& a){printf("%lld",a);}
void print(const double& a){printf("%.15lf",a);}
template<class T> void print(const T& a){cout<<a;}
template<class T> void print(const vector<T>& vec){if(vec.empty())return;print(vec[0]);for(auto it=vec.begin();++it!= vec.end();){putchar(' ');print(*it);}}
void out(){putchar('\n');}
template<class T> void out(const T& t){print(t);putchar('\n');}
template <class Head, class... Tail> void out(const Head& head,const Tail&... tail){print(head);putchar(' ');out(tail...);}
//デバッグ系
template<class T> void dprint(const T& a){cerr<<a;}
template<class T> void dprint(const vector<T>& vec){if(vec.empty())return;cerr<<vec[0];for(auto it=vec.begin();++it!= vec.end();){cerr<<" "<<*it;}}
void debug(){cerr<<endl;}
template<class T> void debug(const T& t){dprint(t);cerr<<endl;}
template <class Head, class... Tail> void debug(const Head& head, const Tail&... tail){dprint(head);cerr<<" ";debug(tail...);}
ll intpow(ll a, ll b){ ll ans = 1; while(b){ if(b & 1) ans *= a; a *= a; b /= 2; } return ans; }
ll modpow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; }
ll updivide(ll a,ll b){if(a%b==0) return a/b;else return (a/b)+1;}

int main(){
    INT(h,w);
    vector2d(char,maze,h,w);
    vector2d(int,dp,h,w);
    in(maze);
    rep(y,h){
        rep(x,w){
            if(y==0){
                if(x==0)dp[y][x]=(maze[y][x]=='#');
                else dp[y][x]=dp[y][x-1]+(maze[y][x]!=maze[y][x-1]);
            }else{
                if(x==0)dp[y][x]=dp[y-1][x]+(maze[y][x]!=maze[y-1][x]);
                else{
                    dp[y][x]=min(dp[y-1][x]+(maze[y][x]!=maze[y-1][x]),
                    dp[y][x-1]+(maze[y][x]!=maze[y][x-1]));
                }
            }
        }
    }
    out((dp[h-1][w-1]+1)/2);
}

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

int main(){
    int h, w;
    while(true){
        cin >> h >> w;
        if (h==0 && w==0) break;
        for (int i=0; i<h; i++){
            for (int j=0; j<w; j++){
                cout << "#";
            }
            cout << endl;
        }
        cout << endl;
    }
    return 0;
}


Measured memory_bytes: 3088
//Created by Kira

#include<bits/stdc++.h>
using namespace std;

#define IOS cin.sync_with_stdio(0);cin.tie(0); cout.tie(0);
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pii pair<int,int> 
#define pb push_back
#define vi vector<int> 
using ll = long long;
using ld =  long double;

const int mod = 1e9 + 7;

ll pwr(ll a, ll b);
    



int main(){
   IOS

   ll w, h, x, y; cin>>w>>h>>x>>y;

   ld area = (w*h)/2.0;

   cout<<fixed<<setprecision(10)<<area<<" ";

   if((w & 1) == 0 and (h & 1) == 0){
       if(x == w/2 and y == h/2){
           cout<<1<<"\n";
           return 0;
       }
   }

   cout<<0<<"\n";
   







    







}

ll pwr(ll a, ll b){
   a %= mod;	//Remove mod if not required
   ll res = 1;
   while(b > 0){
    if(b&1)
        res = res * a % mod;
        a = a * a % mod;
    b >>= 1;
    }

    return res;
}



Measured memory_bytes: 256
<?php
  
fscanf(STDIN,"%d",$n);
$h_li = explode(" ",trim(fgets(STDIN)));
$max = 0;
$count = 0;
foreach($h_li as $h){
  if($max<=$h){
    $max = $h;
    $count++;
  }
}

echo $count."\n";



Measured memory_bytes: 4728
#include<bits/stdc++.h>
using namespace std;
int n,a[200005],mx=0;
long long s=0;
int main() {
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		mx=max(mx,a[i]);
		s+=mx-a[i];
	}
	cout<<s;
}

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

using ll = long long;

const int MAX_N = 100010;
int par[MAX_N];
int rnk[MAX_N];
int siz[MAX_N];

void init(int n) {
    rep(i,n) {
        par[i] = i;
        rnk[i] = 0;
        siz[i] = 1;
    }
}

int find(int x) {
    if (par[x] == x) {
        return x;
    } else {
        return par[x] = find(par[x]);
    }
}

void unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    int s = siz[x] + siz[y];
    if (rnk[x] < rnk[y]) {
        par[x] = y;
    } else {
        par[y] = x;
        if (rnk[x] == rnk[y]) rnk[x]++;
    }
    siz[find(x)] = s;
}

bool same(int x, int y) {
    return find(x) == find(y);
}

int size(int x) {
    return siz[find(x)];
}

int main() {
    int n, q, c, x, y;
    cin >> n >> q;
    init(n);
    rep(i, q) {
        cin >> c >> x >> y;
        if (c) {
            if (same(x, y)) cout << "1\n";
            else cout << "0\n";
        } else {
            unite(x, y);
        }
    }
}


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

using namespace std;

typedef long long int ll;
typedef long double ld;

int main()
{
	ll n, ans=0,tmp=0;
	cin>>n;
	tmp=n;
	vector <char> v;
	while(n > 0)
	{
		if (n % 26 == 0) 
        {
            v.push_back('z');
            n--;
        } 
        else v.push_back('a' + (n%26) - 1);
        n /= 26;
	}
	reverse(v.begin(),v.end());
	for(auto i : v) cout << i;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define re return
typedef vector<int> vi;
typedef long long ll;
typedef pair<int, int> pii;
ll cnt[30];
int n;
string s;
ll ans=1; 
int main() { 
    //freopen("input.txt","r",stdin);
	//freopen("output.txt","w",stdout);
	cin>>n;
	cin>>s;
	for(int i=0;i<n;i++){
		cnt[s[i]-'a']++;
	}
	for(int i=0;i<26;i++){
		ans=ans*(cnt[i]+1)%(ll)(1e9+7);
	}
	cout<<ans-1<<endl;
    return 0; 
}

Measured memory_bytes: 512
import java.util.Scanner;

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();


		if(a <= c && c <= b) {
			System.out.println("Yes");
		}else {
			System.out.println("No");
		}

	}

}


Measured memory_bytes: 22612
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define oo 0x3f3f3f3f

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,k;
    cin>>n>>k;
    vector<array<ll,2>>A;
    int posCnt = 0;
    int mx = -1e9-1;

    for(int i=0; i<n; i++)
    {
        int x;
        cin>>x;
        mx=max(mx,x);
        posCnt += x >=0;
        A.push_back({abs(x), x < 0 ? -1 : x==0 ? 0 : 1});
    }
    sort(A.rbegin(),A.rend());

    ll res = 1;
    ll mod = 1e9+7;

    if(k == 1)return cout<<(mx+mod)%mod,0;

    if(posCnt == 0 || k==n) //all negative
    {
        res = 1;
        if(k&1)reverse(A.begin(),A.end());
        for(int i=0; i<k; i++)
            res = (res * (A[i][0] * A[i][1]))%mod;
        if(res < 0)res+=mod;
        return cout<<res,0;
    }

    int cnt = 0;

    ll lastNeg = 1;
    ll lastPos = 1;
    ll wasPos = 0;

    for(int i=0; i<k; i++)
        if(A[i][1] < 0)
        {
            res = (res*lastNeg)%mod;
            lastNeg=-A[i][0],cnt++;
        }
        else
        {
            res = (res*lastPos)%mod;
            lastPos = A[i][0];
            wasPos = 1;
        }

    if(!wasPos && cnt%2==1) //special case?
    {
        ll nxtPos = -1;

        for(int i=k; i<n; i++)
            if(A[i][1] >= 0)
        {
            nxtPos=A[i][0];
            break;
        }
        res = (res * lastPos)%mod;
        res = (res * nxtPos)%mod;
    }
    else if(cnt&1) //gotta get rid of minus
    {
        ll nxtNeg = 1;
        ll nxtPos = -1;

        for(int i=k; i<n; i++)
            if(A[i][1] < 0)
        {
            nxtNeg=-A[i][0];
            break;
        }

        for(int i=k; i<n; i++)
            if(A[i][1] >= 0)
        {
            nxtPos=A[i][0];
            break;
        }

        //case 1: get rid of lastPositive and add nxtNeg instead
        //case 2: get rid of lastNegative and add nxtPos instead

        if(nxtNeg < 0 && nxtPos >=0)
        {
                if(lastNeg * nxtNeg >= lastPos * nxtPos)
            {
                res = (res * lastNeg)%mod;
                res = (res * nxtNeg)%mod;
            }
            else
            {
                res = (res * lastPos)%mod;
                res = (res * nxtPos)%mod;
            }
        }
        else if(nxtNeg < 0)
        {
            res = (res * lastNeg)%mod;
            res = (res * nxtNeg)%mod;
        }
        else if(nxtPos >= 0)
        {
            res = (res * lastPos)%mod;
            res = (res * nxtPos)%mod;
        }
        else return SIGSEGV;
    }
    else
    {
        res = (res * lastPos)%mod;
        res = (res * lastNeg)%mod;
    }

    if(res < 0)res+=mod;

    cout<<res;
}


Measured memory_bytes: 7356
#include<iostream>
#include<cstdio>
typedef long long ll;
const int N=2e5+5;
int n;ll x[N],a[N];
int main() {
    scanf("%d",&n);
    for(int i=1;i<=n;i++) x[i]=n-i;
    for(int i=1;i<=n;i++) scanf("%lld",a+i),a[i]+=n-i;
    int p=n;ll now=x[n],ans=0;
    a[n+1]=-1;
    for(int i=n;i;i--) {
        if(p>i) p=i,now=x[i];
        if(a[i]==now) continue;
        while(p>1) {
            --p;
            if(x[p]==a[i]) break;
        }
        if(x[p]!=a[i]) return printf("-1"),0;
        ans+=i-p;
        now=x[p];
    }
    printf("%lld\n",ans);
    return 0;
}


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

namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            string S;
            S = Console.ReadLine();
            if (S == "Sunny")
            {
                Console.WriteLine("Cloudy");
            }
            else if (S == "Cloudy")
            {
                Console.WriteLine("Rainy");
            }
            else 
            {
                Console.WriteLine("Sunny");
            }
            Console.ReadKey();
        }
    }
}


Measured memory_bytes: 11092
a = 1
b = 1 
gets.to_i.times do
  a1, b1 = gets.split.map(&:to_i)
  r0 = (a - 1) / a1 + 1
  r1 = (b - 1) / b1 + 1 
  r = r0 > r1 ? r0 : r1 
  a = a1 * r 
  b = b1 * r
end
puts a + b

Measured memory_bytes: 1788
N = int(input())
a,b = (int(x) for x in input().split())

lis = []
lis = input().split()
lis = [int(s) for s in lis]

#print(lis)
a_num,b_num,c_num = 0,0,0

for i in range(N):
#    print(lis[i])
    if lis[i] <= a:
        a_num +=1
    elif lis[i] <= b:
        b_num +=1
    else:
        c_num +=1
"""
print("a_num"+str(a_num))
print("b_num"+str(b_num))
print("c_num"+str(c_num))
"""

if a_num == 0:
    print(0)
elif b_num == 0:
    print(0)
else:
    print(min(a_num,b_num,c_num))


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

long long s, a;
string st;
int main(){
	cin >> st;
	for(int i = 0; i < st.size(); i++){
		if(st[i] == 'S') s++;
		else {
			if(s > 0) s--;
			else a++; 
		}
	}
	a += s;
	cout << a;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define FOR(i,a,b) for(ll i=(a);i<=(b);i++)
#define ALL(x) (x).begin(),(x).end()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int main(){
  int n;
  cin >> n;
  set<int> s;
  REP(i,n){
    int y;
    cin >> y;
    s.insert(y);
  }
  if (n > s.size())
    cout << "NO" << endl;
  else
    cout << "YES" << endl;
}

Measured memory_bytes: 9600
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<climits>
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
#include<set>
#include<stack>
#include<functional>
#include<queue>
using namespace std;

vector<int> e[20];
bool used[20];

void dfs(int n){
    if(used[n]) return;
    used[n] = true;
    for(int i=0;i<e[n].size();i++){
        dfs(e[n][i]);
    }
    printf("%d\n",n+1);
}

int main(){
    int M,N,X,Y;
    cin>>M>>N;
    for(int i=0;i<N;i++){
        cin>>X>>Y; X--; Y--;
        e[Y].push_back(X);
    }
    for(int i=0;i<M;i++) dfs(i);
    return 0;
}

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

int main()
{
    int n;
    cin >> n;
    vector< int > a(n + 1), A(n + 1);
    vector< int > b(n), B(n);
    for (int i = 0; i < n + 1; i++) {
        cin >> a[i];
        A[i] = a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
        B[i] = b[i];
    }
    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += min(a[i], b[i]);
        if (a[i] > b[i]) {
            a[i] -= b[i];
            b[i] = 0;
        } else {
            b[i] -= a[i];
            a[i] = 0;
        }
        ans += min(a[i + 1], b[i]);
        if (a[i + 1] > b[i]) {
            a[i + 1] -= b[i];
            b[i] = 0;
        } else {
            b[i] -= a[i + 1];
            a[i + 1] = 0;
        }
    }
    long long ANS = 0;
    for (int i = n - 1; i >= 0; i--) {
        ANS += min(A[i + 1], B[i]);
        if (A[i + 1] > B[i]) {
            A[i + 1] -= B[i];
            B[i] = 0;
        } else {
            B[i] -= A[i + 1];
            A[i + 1] = 0;
        }
        ANS += min(A[i], B[i]);
        if (A[i] > B[i]) {
            A[i] -= B[i];
            B[i] = 0;
        } else {
            B[i] -= A[i];
            A[i] = 0;
        }
    }
    cout << max(ans, ANS) << endl;
    return 0;
}

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

using namespace std;

#define forn(i, n) for (ll i = 0; i < (ll) (n); ++i)
#define sz(a) static_cast<int>((a).size())
#define pb emplace_back
#define mp make_pair
#define endl '\n'
#define f first
#define s second

#ifdef SEREZHKA
#define dbg(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define dbg(...)
#endif

template<typename T>
void _dbg(const char* _s, T _h) { cerr << _s << " = " << _h << "\n"; }

template<typename T, typename... Ts>
void _dbg(const char*_s, T _h, Ts... _t) {
    int _b = 0;
    
    while (((_b += *_s == '(') -= *_s == ')') != 0 || *_s != ',')
        cerr << *_s++;
    
    cerr << " = " << _h << ",";
    _dbg(_s + 1, _t...);
}

using ll = long long;

const ll INF = static_cast<ll>(1e9) + 7ll;
const ll LINF = INF * INF;
const int MAXN = static_cast<int>(2e5) + 17;

struct line {
    long double k, b;
    line() = default;
    line(long double k, long double b) : k(k), b(b) { }
};

using pt = pair<long double, long double>;
#define x first
#define y second

pt inter(line l1, line l2) {
    pt p;
    p.x = (l2.b - l1.b) / (l1.k - l2.k);
    p.y = l1.k * p.x + l1.b;
    return p;
}

struct CHT {
    vector<line> L;
    vector<pt> P;

    CHT() {
        L = { line(-INF * INF, -INF * INF) };
        P.clear();
    }

    void add_line(ll k, ll b) {
        line nl(k, b);

        while (!P.empty() && P.back().y < k * P.back().x + b) {
            P.pop_back();
            L.pop_back();
        }

        P.pb(inter(L.back(), nl));
        L.pb(nl);
    }

    ll getmin(ll x) {
        int i = lower_bound(P.begin(), P.end(), pt(x, -INF * INF)) - P.begin();
        return L[i].k * x + L[i].b;
    }
};

int n;
ll C;
ll h[MAXN], dp[MAXN];

bool read() {
    if (!(cin >> n >> C))
        return false;

    forn (i, n)
        cin >> h[i];

    return true;
}

void solve() {
    CHT T;
    dp[0] = 0;
    T.add_line(2 * h[0], -(C + dp[0] + h[0] * h[0]));

    for (int i = 1; i < n; ++i) {
        dp[i] = h[i] * h[i] - T.getmin(h[i]);
        T.add_line(2 * h[i], -(C + dp[i] + h[i] * h[i]));
    }

    cout << dp[n - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);
    
#ifdef SEREZHKA
    freopen("file.in", "r", stdin);
#endif
    
    while (read())
        solve();
    
    return 0;
}



Measured memory_bytes: 18644
// Add compile option "-std=c++11" for C++11 compile.

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <regex>
#include <numeric>
using namespace std;

// Macro
#define rep(i, N) for(int i=0; i<(int)N; i++)
#define rrep(i, N) for(int i=(int)N-1; i>=0; i--)

// Type
template <typename T> using P = pair<T, T>;
using ll = long long;
using ull = unsigned long long;

// Constants
const ll INF = 1e18;
const ll MOD = 1000000007;

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

  int N = S.length();

  // 最初が黒
  int a = 0;
  rep(i, N) {
    if(i % 2 == 0 && S[i] != '0') {
      a++;
    } else if(i % 2 == 1 && S[i] != '1') {
      a++;
    }
  }

  // 最初が白
  int b = 0;
  rep(i, N) {
    if(i % 2 == 0 && S[i] != '1') {
      b++;
    } else if(i % 2 == 1 && S[i] != '0') {
      b++;
    }
  }

  cout << min(a, b) << endl;
  
  return 0;
}

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

int main() {
  int x;
  cin >> x;
  for (int i = 1; i <= x; i++) {
    if (i % 3 == 0) {cout << " " << i;}
    else{
      int j = i;
      while (j){
        if (j % 10 == 3) {
          cout << " " << i;
          break;}
        j /= 10;
      }
    }
  }
  cout << endl;
  return 0;
}

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

#define ll long long
#define endl '\n'

int n,k;

void test() {
    cin>>n>>k;
    vector<int> p(n);
    for (int& i:p) cin>>i;
    sort(p.begin(),p.end());
    int ans=0;
    for (int i=0; i<k; ++i) {
        ans+=p[i];
    }
    cout << ans << endl;
}

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

    // int t;
    // cin >> t;
    // while (t--) {
    //     test();
    // }
    test();
    return 0;
}

Measured memory_bytes: 3660
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<(int)n;i++)
 
int main()
{
  int N, M;
  cin >> N >> M;
  vector<int> roads(50), x(50), y(50);
  rep(i,N){roads.at(i)=0;}
  rep(i,M)
  {
    cin >> x.at(i) >> y.at(i);
    roads.at(x.at(i)-1)+=1;
    roads.at(y.at(i)-1)+=1;
  }
  rep(j,N){cout << roads.at(j) << endl;}
  return 0;
}


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

int main() {
  int x,a,b,c,d,y;
  std::cin >> x;
  a = x/100 ;
  b = x%100 ;
  c = b/10  ;
  d = b%10  ;
  y = a + c + d ;
  std::cout << y << '\n';
}

Measured memory_bytes: 256
#include <stdio.h>

typedef long long ll;

int a[2005];
int b[2005];
ll c[2005];
ll dist[1005];
int negative[1005];

ll INF = 1ll << 60;

int main(){

	int N, M;

	scanf("%d %d",&N,&M);

	int i,j;

	for (i = 0; i < M; i++) {
		scanf("%d %d %lld",&a[i],&b[i],&c[i]);
		c[i] = -c[i];
	}

	for (i = 0; i < N; i++) {
		dist[i] = INF;
	}
	dist[0] = 0ll;

	for (i = 0; i < N - 1; i++) {
		for (j = 0; j < M; j++) {
			if (dist[a[j] - 1] == INF) { continue; }
			if (dist[b[j] - 1] > dist[a[j] - 1] + c[j]) {
				dist[b[j] - 1] = dist[a[j] - 1] + c[j];
			}
		}
	}

	ll ans = dist[N - 1];

	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (dist[a[j] - 1] == INF) { continue; }
			if (dist[b[j] - 1] > dist[a[j] - 1] + c[j]) {
				dist[b[j] - 1] = dist[a[j] - 1] + c[j];
				negative[b[j] - 1] = 1;
			}
			if (negative[a[j] - 1] == 1) {
				negative[b[j] - 1] = 1;
			}
		}
	}

	if (negative[N - 1] == 1) {
		printf("inf\n");
	}
	else {
		printf("%lld\n",-ans);
	}

	return 0;
}

Measured memory_bytes: 256
def prime_factorize(n):
    a=[]
    while n%2==0:
        a.append(2)
        n //=2
    f=3
    while f**2<=n:
        if n%f==0:
            a.append(f)
            n //=f
        else:f +=2
    if n!=1:a.append(n)
    return a

a,b=map(int,input().split())
print(len(set(prime_factorize(a))&set(prime_factorize(b)))+1)

Measured memory_bytes: 3188
// 問題の URL を書いておく
// https://atcoder.jp/contests/abc115/tasks/abc115_d

#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>

using namespace std;

//#define ENABLE_PRINT

#if defined(ENABLE_PRINT)

#define Print(v) \
do {\
    cout << #v << ": " << v << endl; \
}while(0)

#define PrintVec(v) \
do {\
    for(int __i = 0; __i < v.size(); ++__i) \
    { \
        cout << #v << "[" << __i << "]: " << v[__i] << endl; \
    }\
}while(0)

#else

#define Print(v) ((void)0)
#define PrintVec(v) ((void)0)

#endif

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

using ll = int64_t;

const int MaxLayer = 51;

ll len[MaxLayer] = {}, p[MaxLayer] = {};

ll count(int layer, ll index)
{
    if(layer == 0)
    {
        return 1;
    }

    if(!(index >= 0 && index < len[layer]))
    {
        printf("layer: %d, index: %ld, len: %ld\n", layer, index, len[layer]);
        abort();
    }

    if(index == 0)
    {
        return 0;
    }
    auto center = (len[layer] - 1) / 2;

    if(index < center)
    {
        return count(layer - 1, index - 1);
    }
    if(index == center)
    {
        return p[layer - 1] + 1;
    }
    if(index == len[layer] - 1)
    {
        return p[layer];
    }
    return p[layer - 1] + 1 + count(layer - 1, index - len[layer - 1] - 2);
}

int main(int, const char**)
{
    ll n, x;
    cin >> n >> x;
    len[0] = 1;
    p[0] = 1;
    rep(i, n)
    {
        len[i + 1] = len[i] * 2 + 3;
        p[i + 1] = p[i] * 2 + 1;
    }

#if 0
    rep(i, n + 1)
    {
        printf("[%d]: len: %ld, p: %ld\n", i, len[i], p[i]);
    }
#endif
    auto c = count(n, x - 1);
    cout << c << endl;

#if 0
    cout << endl;
    int ly = 3;
    rep(i, len[ly])
    {
        cout << "i: " << i << ", count: " << count(ly, i) << endl;
    }
#endif
    return 0;
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
#define rep2(i, x, n) for(int i = x; i <= n; i++)
#define rep3(i, x, n) for(int i = x; i >= n; i--)
#define elif else if
#define sp(x) fixed << setprecision(x)
#define pb(x) push_back(x)
#define all(x) x.begin(), x.end()
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pil = pair<int, ll>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
const ll MOD = 1e9+7;
//const ll MOD = 998244353;
const int inf = 1e9;
const ll INF = 1e18;
const ld EPS = 1e-10;

int main(){
    string s, t;
    cin >> s >> t;
    vector<ll> ids[26];
    ll n = s.size();
    rep(i, n){
        int j = s[i]-'a';
        ids[j].pb(i);
    }
    //[0,now)
    ll now = 0;
    rep(i, t.size()){
        int j = t[i]-'a';
        ll k = now%n;
        if(ids[j].empty()) {cout << -1 << endl; return 0;}
        int a = lower_bound(all(ids[j]), k) - ids[j].begin();
        if(a == ids[j].size()) now += n+ids[j][0]-k;
        else now += ids[j][a]-k;
        now++;
    }
    cout << now << endl;
}

Measured memory_bytes: 1724
//Heaplax
#include<bits/stdc++.h>
#define LL long long
#define LOG(x) cerr<<#x<<" = "<<x<<endl
#define add_edge(u,v) nxt[++cnt]=head[u],head[u]=cnt,to[cnt]=v
#define open(x) freopen(#x".in","r",stdin),freopen(#x".out","w",stdout)
char ch;bool fs;void re(int& x)
{
	while(ch=getchar(),ch<33);
	if(ch=='-')fs=1,x=0;else fs=0,x=ch-48;
	while(ch=getchar(),ch>33)x=x*10+ch-48;
	if(fs)x=-x;
}
using namespace std;
int top,ans,st[30];
int main()
{
	// open(A);
	char tmp;
	while(scanf("%c",&tmp)!=EOF && isdigit(tmp))
		st[++top]=tmp-'0';
	int pre=0;
	for(int i=1;i<=top;++i)
	{
		if(st[i]>0)
			ans=max(ans,pre+st[i]-1+9*(top-i));
		pre+=st[i];
	}
	ans=max(ans,pre);
	printf("%d\n",ans);
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,a,n) for(int i=a; i<n; i++)
using namespace std;
typedef pair<int, int> pii;
typedef vector< vector<pii> > Graph;

struct Edge {
    int from, to, cost;
    Edge(int a, int b, int c) : from(a), to(b), cost(c) {};
};

int depth[100010];
void getDepth(Graph &G, int point) {
    for(size_t i=0; i<G[point].size(); i++) {
        int to = G[point][i].first;
        if(depth[to] != -1) continue;
        depth[to] = depth[point] + 1;
        getDepth(G, to);
    }
}

int main() {
    double p; cin >> p;
    int n; cin >> n;
    Graph G(n);
    vector<Edge> ve;
    rep(i,0,n-1) {
        int x, y, c;
        cin >> x >> y >> c;
        x--; y--;
        G[x].push_back(pii(y, c));
        G[y].push_back(pii(x, c));
        ve.push_back(Edge(x, y, c));
    }

    memset(depth, -1, sizeof(depth));
    depth[0] = 0;
    getDepth(G, 0);

    double E = 0.0;
    rep(i,0,ve.size()) {
        int x = depth[ ve[i].from ];
        int y = depth[ ve[i].to ];
        int d = max(x, y);
        E += ve[i].cost * pow(p, d);
    }

    double ans = 2 * E;
    rep(i,0,ve.size()) {
        int x = depth[ ve[i].from ];
        int y = depth[ ve[i].to ];
        int d = max(x, y);
        ans += E * pow(p, d);
    }

    cout << fixed << setprecision(10) << ans << endl;
}

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

static const int N = 100;

int main()
{
  int n, p[N + 1], m[N + 1][N + 1];
  cin >> n;
  for (int i = 1; i <= n; i++)
  {
    cin >> p[i - 1] >> p[i];
  }

  for (int i = 1; i <= n; i++)
    m[i][i] = 0;
  for (int l = 2; l <= n; l++)
  {
    for (int i = 1; i <= n - l + 1; i++)
    {
      int j = i + l - 1;
      m[i][j] = (1 << 21);
      for (int k = i; k <= j - 1; k++)
      {
        m[i][j] = min(m[i][j], m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]);
      }
    }
  }
  cout << m[1][n] << endl;
  return 0;
}


Measured memory_bytes: 3124
#include <bits/stdc++.h>
using namespace std; 
#define int int64_t
#define itn int
#define fi first
#define se second
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n,a,b,c;
  int hi,lo;
  vector<int> h;
  cin>>n>>a>>b;
  for(int i=0;i<n;i++){
    cin>>c;
    h.push_back(c);
  }
  hi=1e9,lo=0;
  while(hi-lo>1){
    int m=(hi+lo)/2;
    int sum=b*m,t=0;
    bool f=true;
    for(int i=0;i<n;i++){
      if(sum<h[i]){
	t+=(h[i]-sum)/(a-b);
	if((h[i]-sum)%(a-b)!=0) t++;
      }
    }
    //cout<<sum<<" "<<lo<<" "<<m<<" "<<hi<<"\n";
    if(t>m) f=false;
    if(f) hi=m;
    else lo=m;
  }
  cout<<hi<<"\n";
  return 0;
}


Measured memory_bytes: 4288
#[allow(unused_imports)]
use itertools::Itertools;
#[allow(unused_imports)]
use num::Integer;
#[allow(unused_imports)]
use proconio::derive_readable;
use proconio::fastout;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
#[allow(unused_imports)]
use std::cmp;
#[allow(unused_imports)]
use std::collections::*;

fn chmax<T: Ord + Copy>(y: T, x: &mut T) {
    *x = cmp::max(*x, y);
}

#[fastout]
fn main() {
    input! {
        r: usize,
        c: usize,
        k: usize,
        item: [(usize, usize, i64); k],
    }
    let mut field = vec![vec![0; c + 1]; r + 1];
    for (i, j, v) in item.into_iter() {
        field[i][j] = v;
    }
    let mut dp = vec![vec![vec![0; 4]; c + 1]; r + 1];
    for i in 1..=r {
        for j in 1..=c {
            let up = *dp[i - 1][j].iter().max().unwrap();
            chmax(up, &mut dp[i][j][0]);
            chmax(up + field[i][j], &mut dp[i][j][1]);
            for k in 0..=3 {
                chmax(dp[i][j - 1][k], &mut dp[i][j][k]);
                if let Some(l) = k.checked_sub(1) {
                    chmax(dp[i][j - 1][l] + field[i][j], &mut dp[i][j][k]);
                }
            }
        }
    }

    println!("{}", dp[r][c].iter().max().unwrap());
}


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

using namespace std;

typedef long long ll;

int main(int argc, char *argv[]) {
  ll n, K;
  cin >> K >> n;
  if (K % 2 == 0) {
    cout << K / 2;
    for (int i = 2; i <= n; i++) {
      cout << " " << K;
    }
    return 0;
  }
  vector<ll> a(n + 2);
  vector<int> b(n + 2, (K + 1) / 2);
  int p;
  for (p = n; p >= 0; p--) {
    a[p] = K * a[p + 1] + 1;
    if (a[p] > p) break;
  }
  ll S = a[p] - p;
  for (int j = p + 1; j <= n; j++) {
    int z = (S - 2) / (a[j] * 2);
    if (S < 2) {
      b[j] = 0;
      break;
    }
    b[j] = z + 1;
    S = S - z * a[j] * 2 - 2;
  }
  for (int i = 1; i <= n && b[i]; i++) {
    cout << b[i] << " ";
  }
  return 0;
}


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

int main() {
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;

    return 0;
}

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	ll N, k;
	cin >> N >> k;
	vector<int> v;

	for (int i = 0; i < N; i++)
	{
		ll t;
		cin >> t;
		v.push_back(t);
	}
	ll min = 0;
	ll max = 1000000000;
	int ans = -1;
	while (max >= min)
	{
		ll mid = (min + max) / 2;
		ll cnt = 0;
		if(mid == 0)
		{
			ans = 1;
			break;
		}
		for (auto i : v)
		{
			if(i == mid)
				continue;
			cnt += i / mid;
		}
		if (cnt <= k)
		{
			max = mid-1;
			int check = 0;
			if(max == 0)
			{
				ans = max+1;
				break;
			}
			for (auto i : v)
			{
				if(i == max)
					continue;
				check += i / max;
			}
			if(check > k)
			{
				ans = max +1;
				break;
			}
		}
		else
		{
			min = mid+1;
		}
		
	}
	cout << ans << endl;
}


Measured memory_bytes: 4232
#include<stdio.h>
#define M 3000
int main(){
  int x[M],y[M],i,count=0,tmp;

  for(i=0;i<M;i++){
    scanf("%d %d",&x[i],&y[i]);
    if(x[i] == 0 && y[i] == 0) break;
    count++;
  }

  for(i=0;i<count;i++){
    if(x[i] > y[i]){
      tmp = x[i];
      x[i] = y[i];
      y[i] = tmp;
    }
    printf("%d %d\n",x[i],y[i]);
  }
  return 0;
}



Measured memory_bytes: 2048
#include <stdio.h>

int main() 
{  
    int m, n;
    while(scanf("%d%d", &m,&n)!=EOF && m+n)
    {
        for (int i = 0; i < m; i++)
        {
            for (int j = 0; j < n; j++)
            {
                printf("#");
            }
            printf("\n");
        }
        printf("\n");
    }
    
   return 0;
} 


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

using namespace std;

vector<long long> v, sum;
vector<vector<long long>> memo;

long long solve(int a, int b){
	if(memo[a][b] != -1) return memo[a][b];
	if(a == b) return 0;
	if(a == b-1) return v[a] + v[b];

	long long sol = 4e18;

	for(int i=a; i<b; i++)
		sol = min((sum[b+1] - sum[a]) + solve(a, i) + solve(i+1, b), sol);
	return memo[a][b] = sol;
}

int main(){
	cin.tie(0);
	cin.sync_with_stdio(0);

	int N;
	cin >> N;
	v.resize(N);
	sum.resize(N+1, 0);
	memo.resize(N, vector<long long>(N, -1));
	for(auto &i : v) cin >> i;
	for(int i=1; i<=N; i++) sum[i] = sum[i-1] + v[i-1];
	cout << solve(0, N-1);
}


Measured memory_bytes: 1536
// B - バイナリハックイージー / Unhappy Hacking (ABC Edit) https://atcoder.jp/contests/abc043/tasks/abc043_b

  import io.Source

  object Main extends App {
    Source.stdin.getLines().foreach(l => println(solve(l)))

    def solve(s: String): String = {
      var a = ""
      s.foreach { c =>
        c match {
          case 'B' => a = if (a.length > 0) a.substring(0, a.length - 1) else a
          case ch => a += ch
        }
      }
      a
    }
  }


Measured memory_bytes: 25400
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <stack>
#include <queue>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <random>
#include <chrono>
#include <utility>
#include <numeric>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <sstream>
#include <assert.h>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <unordered_map>
using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(bool x) {cerr << (x ? "true" : "false");}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}

template<typename T, typename V> void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i : x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";} void _print() {cerr << "]\n";}
template <typename T, typename... V>void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef HOME
#warning CHECK int:ll::INT_MAX:LLONG_MAX
#define maxn 20
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define maxn 2000006
#define gcd __gcd
#define debug(x...)
#endif

#define ff first
#define endl '\n'
#define ss second
#define inf 0x3f3f3f3f
#define MOD 1000000007
#define PI 3.14159265358979323846264338327950L
#define f(i,x,n) for(int i=x;i<=n;i++)
#define fr(i,x,n) for(int i=x;i>=n;i--)
struct _ { ios_base::Init i; _() { ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL); } } _;

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


int main() {

	string s; cin >> s;
	map<char, int> f;
	for (auto i : s) f[i]++;

	cout << ((f.size() == 1) ? "No" : "Yes");

	return 0;
}

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

#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pii pair<int,int>
#define pll pair<ll,ll>
// pll pp; -> (pp.first,pp.second)
// vector<vl> pp(n,vl(2)); sort(pp.begin(),pp.end(),[](vl a,vl b){return a[0]<b[0];});

#define REP(i,n) for(ll (i)=0;(i)<(n);(i)++)
#define RREP(i,n) for(ll (i)=(n)-1;(i)>=0;(i)--)
#define DEBUG(x) cout << #x << ": " << x << endl
#define CHMAX(a,b) a=max((a),(b))
#define CHMIN(a,b) a=min((a),(b))
/*}}}*/
int main() {
  ll n;
  cin >> n;
  ll a[100000];
  REP(i,n) cin >> a[i];
  sort(a,a+n);
  ll ai = a[n-1];
  ll bi = ai;
  cout << ai << " ";
  ai /= 2;

  ll ng = n-1;
  ll ok = 0;
  while(abs(ok-ng)>1){
    ll m = (ok+ng)/2;
    if(a[m]<=ai) ok = m;
    else ng = m;
  }
  ll lb = a[ok];

  ng = 0,ok = n-1;
  while(abs(ok-ng)>1){
    ll m = (ok+ng)/2;
    if(a[m]>=ai) ok = m;
    else ng = m;
  }
  ll ub = a[ok];

  if(abs(ai-lb)<abs(ai-ub) || bi==ub) cout << lb << endl;
  else cout << ub << endl;

  return 0;
}


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

#define F first 
#define S second
#define PB push_back

using namespace std;

typedef long long LL;
typedef pair<int, int> PII;
typedef priority_queue<int> HEAP;
typedef priority_queue<int, vector<int>, greater<int> > RHEAP;

const int N = 100010, M = 1010;

int n;
int q[N];

int main()
{
	scanf("%d", &n);
	
	int cnt = 0;
	for (int i = 1; i <= n; i ++ )
	{
		int x;
		scanf("%d", &x);
		
		int l = 1, r = cnt;
		while (l < r)
		{
			int mid = l + r >> 1;
			if (q[mid] < x) r = mid;
			else l = mid + 1;
		}
		
		if (!cnt || q[cnt] >= x) q[ ++ cnt] = x;
		else q[r] = x;
	}
	
	printf("%d\n", cnt);
    return 0;
}

Measured memory_bytes: 4164
#include <iostream>
#include <cstring>
#include <cstdio>
#include <map>
#include <cmath>
#include <algorithm>
#include <iomanip>
using namespace std;
const int maxn=2e5+100;
const long double Pi=acos((long double)-1.0);
struct point {
  int x,y;
  bool operator<(const point &u) const{
    return x<u.x;
  }
};
point p[maxn];
void read(point &u){
  scanf("%d %d",&u.x,&u.y);
}

bool ok(point u,point v,point x){
  int mmx=min(u.x,v.x),mxx=max(u.x,v.x),mmy=min(u.y,v.y),mxy=max(u.y,v.y);
  return (x.x>=mmx && x.x<=mxx && x.y>=mmy && x.y<=mxy);
}
int f[maxn],a[maxn];
map<int,int> ma;
int mx[maxn*4],ql,qr;
void build(int o,int l,int r){
  mx[o]=0;
  if (l>=r) return;
  else {
     int mid=(l+r)>>1;
     build(o<<1,l,mid);
     build(o<<1|1,mid+1,r);
  }
}
void update(int o,int l,int r,int x){
  if (ql<=l && r<=qr){
    mx[o]=max(mx[o],x);
  } else {
    int mid=(l+r)>>1;
    if (ql<=mid) update(o<<1,l,mid,x);
    if (qr>mid) update(o<<1|1,mid+1,r,x);
    mx[o]=max(mx[o<<1],mx[o<<1|1]);
  }
}

int query(int o,int l,int r){
  if (ql<=l && r<=qr) return mx[o];
  else {
    int mid=(l+r)>>1;
    int ans=0;
    if (ql<=mid) ans=max(ans,query(o<<1,l,mid));
    if (qr>mid) ans=max(ans,query(o<<1|1,mid+1,r));
    return ans;
  }
}
int main()
{
    int i,j,n,cnt=0;
    point u,v;
    read(u);read(v);
    if (u.y>v.y) swap(u,v);
    cin>>n;
    for (i=1;i<=n;i++){
       read(p[cnt]);
       if (ok(u,v,p[cnt])) cnt++;
    }
    sort(p,p+cnt);
    if (u.y==v.y) {
        if (cnt) {
          long double ans=1ll*abs(u.x-v.x)*100-20+Pi*10;
          cout << setprecision(25) << ans <<endl;
        }
        else cout << setprecision(25) << 1ll*abs(u.x-v.x)*100 <<endl;
    } else {
      long double ans=1ll*abs(u.x-v.x)*100+1ll*abs(u.y-v.y)*100;
      if (u.x>v.x) reverse(p,p+cnt);
      for (i=0;i<cnt;i++) a[i]=p[i].y;
      sort(a,a+cnt);ma.clear();
      for (i=0;i<cnt;i++) ma[a[i]]=i+1;
      build(1,1,cnt);
      int k=0,k2;
      for (i=0;i<cnt;i++){
        ql=1;qr=ma[p[i].y];
        f[i]=query(1,1,cnt)+1;
        if (f[i]>k){k2=k;k=f[i];}
        ql=qr;
        update(1,1,cnt,f[i]);
      }
      ans=ans+(Pi*5-20)*k;
      if (k==abs(u.x-v.x)+1 || k==abs(u.y-v.y)+1) {
        ans=ans-(Pi*5-20)-20+10*Pi;
      }
      cout << setprecision(30) << ans <<endl;
    }
    return 0;
}


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

int main(){
    int a[5];
    for (int i = 0; i < 5; i++) {
       cin >> a[i];
    }
    int mi = 0;
    for (int i = 1; i < 5; i++) {
        if (a[i] % 10 == 0) continue;
        if (a[mi] % 10 > a[i] % 10) {
            mi = i;
        }
    }
    int ans = a[mi];
    a[mi] = 0;


    for (int i = 0; i < 5; i++) {
        if (a[i] % 10 != 0) {
            ans += a[i] + (10 - (a[i] % 10));
        }
        else 
            ans += a[i];
    }
    cout << ans << '\n';

}


Measured memory_bytes: 256
def main():
    n, y = (int(x) for x in input().split())
    y = y//1000

    for i in range(n+1):
        for j in range(n+1):
            k = n - (i + j)
            if k >= 0 and 10*i + 5*j + k == y:
                return [i,j,k]
    return [-1,-1,-1]

if __name__ == '__main__':
    print(*main())

Measured memory_bytes: 3060
import java.util.*;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] a = new int[N-1];
        int[] b = new int[N-1];
        for (int i=0; i<N-1; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }

        Ans ans = solve(N, a, b);

        System.out.println(ans.K);
        for (int i=0; i<N-1; i++) {
            System.out.println(ans.c[i]);
        }
    }

    private static Ans solve(int N, int[] a, int[] b) {
        Ans ans = new Ans(N);

        List<Integer[]>[] list = new ArrayList[N];
        for (int i=0; i<N; i++) {
            list[i] = new ArrayList<>();
        }
        for (int i=0; i<N-1; i++) {
            list[a[i]-1].add(new Integer[]{i, b[i]-1});
            list[b[i]-1].add(new Integer[]{i, a[i]-1});
        }

        for (int i=0; i<N; i++) {
            ans.K = Math.max(ans.K, list[i].size());
        }

        Queue<Integer> queue = new ArrayDeque();
        int[] color = new int[N];
        color[0] = 1;
        queue.add(0);
        while (queue.size() > 0) {
            int node = queue.poll();
            int coloring = 1;

            for (int i=0; i<list[node].size(); i++) {
                int edge = list[node].get(i)[0];
                int connect = list[node].get(i)[1];

                if (color[connect] != 0) continue;
                if (node != 0 && color[node] == coloring) coloring++;

                // System.err.println("node=" + (node+1) + ", edge=" + edge + ", connect=" + (connect+1) + ", color[" + (node+1) + "]=" + color[node] + ", coloring=" + coloring);
                color[connect] = coloring;
                ans.c[edge] = coloring;
                coloring++;

                queue.add(list[node].get(i)[1]);
            }
        }

        return ans;
    }

    public static class Ans {
        public int K;
        public int[] c;

        public Ans(int N) {
            K = 0;
            c = new int[N-1];
        }
    }
      }

Measured memory_bytes: 84828
n,z,w=map(int,input().split())
a=[int(_) for _ in input().split()]
a.reverse()
dp=[[0,0] for i in range(n)]
# dp[i][j] i番目までのカードを使用しjから始めた場合のゲームのスコア
for i in range(n):
    if i==n-1:
        score1=abs(w-a[0])
        score2=abs(z-a[0])
        dp[i][0]=score1
        dp[i][1]=score2
    else:
        score=abs(a[i+1]-a[0])
        dp[i][0]=score
        dp[i][1]=score
    for j in range(i):
        dp[i][0]=max(dp[i][0],dp[j][1])
        dp[i][1]=min(dp[i][1],dp[j][0])
print(dp[n-1][0])

Measured memory_bytes: 3308