akhauriyash/Code-Regression huggingface dataset:
// dp bottom up
/*    ####################  */
/*   # I_LOVE_THUY_LINH #  */
/*  ####################  */
#include <bits/stdc++.h>
#define ll long long
#define db double
#define ld long double
#define ii pair<int,int>
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define matrix vector<vector<ll>>
#define fir first
#define sec second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
#define uni(a) (a).erase(unique(all(a)),(a).end())
#define sz(a) int((a).size())
#define ms(s,val) memset(s,val,sizeof(s))
#define bitcount(n) __builtin_popcountll(n)
#define getbit(s,k) ((s >> k)&1)
#define turnbit(s,k) (s | (1<<k))
#define offbit(s,k) (s & ~(1<<k))
#define flipbit(s,k) (s ^ (1<<k))
#define prec(n) fixed<<setprecision(n)
#define sqr(x) (ll)(x)*(ll)(x)
#define lcm(a,b) ((ll)a/__gcd((ll)a,(ll)b)*(ll)(b))
#define gcd(a,b) __gcd(a,b)
using namespace std;
const int INF = int(1e9);
string s;
int K;

int main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> s;
    cin >> K;

    vector<vector<ll>> dp(K + 1,vector<ll> (2));
    dp[0][0] = 1;
    for (int i = 0; i < s.size(); i++){
        vector<vector<ll>> newdp(K + 1,vector<ll> (2));
        for (int nonzero = 0; nonzero <= K; nonzero++)
            for (bool low : {false,true})
                for (int dg = 0; dg < 10; dg++){
                    int newnonzero = nonzero + (dg != 0);
                    if ((dg > s[i] - '0' && !low)) break;
                    if (newnonzero > K) continue;
                    newdp[newnonzero][low || (dg < s[i] - '0')] += dp[nonzero][low];
                }
        dp = newdp;
    }

    ll ans = dp[K][0] + dp[K][1];
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#pragma GCC optimize("Ofast")
#include "bits/stdc++.h"

using namespace std;

typedef long int li;
typedef long double ld;
typedef long long ll;
typedef pair<li, li> pt;

#define fi first
#define se second
#define lson ((p<<1))
#define rson ((p<<1)+1)
#define mid ((L+R)>>1)
#define dump(x) cout << #x << " = " << x << endl
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

ll const INF = 1e12;

ll n, m, start;
bitset<1007> vis;
vector<li> g[1007], res, now;

void dfs(li v) {
    vis[v] = true;

    now.push_back(v);

    for(auto i : g[v]) {
        if(i == start && v != start && (res.size() == 0 || res.size() > now.size())) res = now;
        if(!vis[i]) dfs(i);
    }

    now.pop_back();
}

int main() {
    fastIO;
    cin >> n >> m;
    for(li i = 0; i < m; i ++) {
        li u, v;
        cin >> u >> v;
        g[--u].push_back(--v);
    }

    for(li i = 0; i < n; i ++) {
        start = i;
        dfs(i);
        vis.reset();
    }

    if(res.size() == 0) cout << -1;
    else {
        cout << res.size() << "\n";
        for(auto i : res) cout << i + 1 << "\n";
    }
}


Measured memory_bytes: 384
using System;
public class Pg
{
    public static void Main()
    {
        double x;
        while ((x = double.Parse(Console.ReadLine()))!=0)
        {
            var h = double.Parse(Console.ReadLine());
            Console.WriteLine(Math.Pow(x, 2) + (2 * x * Math.Sqrt(Math.Pow(h, 2) + Math.Pow(x, 2) / 4)));
        }
    }
}


Measured memory_bytes: 13940
/*
*Bismillahir Rahmanir Rahmin
* @Author: {{Syed Yasir Shahriar
{
/*//*\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\*/
 
//أعوذ بالله من الشيطان الرجيم
//بسم الله الرحمن الرحيم
 
/*//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\//\\*/
 
/*};/* @Date:   {{create_time}}typedef int MyCustomType;
* @Last Modified by:   mrinm
* @Last Modified time: 2020-06-21 21:09:11
*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define pll pair<ll,ll>
#define v vector<ll>
#define st stack<ll>
#define pq  priority_queue <int>
#define q queue<ll>
#define mod 1000000005
using namespace std;
 
 
int main(){
 /*    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif*/
     ios::sync_with_stdio(0);
      cin.tie(0),cout.tie(0);
     // ll t,a,b;
     // cin>>t;

      
      char ch;
      cin>>ch;

      if(isupper(ch)){
      	 cout<<"A"<<endl;
      }
      else{
      	 cout<<"a"<<endl;
      }


     
     return 0;
}

Measured memory_bytes: 3612
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long int
#define ordered_set tree < ll ,  null_type ,  less<ll> ,  rb_tree_tag ,  tree_order_statistics_node_update >
//added two more functions to set
//(1)*(set.find_by_order(k))[kth element in the sorted set] 
//(2)set.order_of_key(k)[count of elements strictly less than k]
typedef vector< int > vi;
typedef vector< ll > lvi;
typedef vector< vi > vvi;
typedef vector< lvi > lvvi;
typedef pair< int,int > ii;
typedef pair< ll,ll > lii;
#define sz(a) int((a).size())
#define pb push_back
#define all(c) (c).begin(),(c).end()
#define tr(c,i) for(auto i = (c).begin(); i != (c).end(); i++)//remember i is an iterator
#define present(c,x) ((c).find(x) != (c).end())//for sets,maps,multimaps
#define cpresent(c,x) (find(all(c),x) != (c).end())//for vectors
#define tc(t) int (t); cin>>(t);while((t)--)
#define ff first
#define ss second
#define mp make_pair
#define ld long double
#define ull unsigned long long int
#define mod 1000000007
ll dp[200][200][3];
string s[200];
ll h,w;
const int INF=1e7;
ll recurs(int i,int j,int cs)
{
	if(i<0 || j<0) return INF;
	if(dp[i][j][cs]!=-1) return dp[i][j][cs];
	if(cs==0)
	{
		if(i==0 && j==0)
		{
			if(s[i][j]=='#')
			{
				dp[i][j][cs]=1;
			}
			else 
			{
				dp[i][j][cs]=0;	
			}	
		}
		else if(s[i][j]=='#')
		{
			dp[i][j][cs]=1+min(recurs(i-1,j,1),recurs(i,j-1,1));
		}
		else 
		{
			dp[i][j][cs]=min(recurs(i-1,j,0),recurs(i,j-1,0));	
		}
	}
	else
	{
		if(i==0 && j==0)
		{
			if(s[i][j]=='#')
			{
				dp[i][j][cs]=0;
			}
			else 
			{
				dp[i][j][cs]=0;	
			}	
		}
		else if(s[i][j]=='#')
		{
			dp[i][j][cs]=min(recurs(i-1,j,1),recurs(i,j-1,1));
		}
		else 
		{
			dp[i][j][cs]=min(recurs(i-1,j,0),recurs(i,j-1,0));	
		}	
	}
	return dp[i][j][cs];
}
int main()
{
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);	
	cin>>h>>w;
	h--;
	w--;
	for(int i=0;i<=h;i++)
	{
		cin>>s[i];
	}
	for(int i=0;i<200;i++)
	{
		for (int j = 0; j < 200; ++j)
		{
			for(int k=0;k<3;k++)
			{
				dp[i][j][k]=-1;
			}
		}
	}
	cout<<recurs(h,w,0)<<endl;
	return 0;
}

Measured memory_bytes: 1280
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=505,M=1e5+5;
int n,m,Ans;
int x[M], y[M], F[N][N],cant[N];
int main(){
	scanf("%d%d",&n,&m);
	for (int i=1;i<=m;i++)
		scanf("%d%d",&x[i],&y[i]); 
	for (int i=1;i<=n;i++) F[i][i]=1;
	for (int i=1;i<=n;i++){
		for (int j=m;j>=1;j--){
			if (F[i][x[j]]&F[i][y[j]]) {cant[i]=1; continue;}
			if (F[i][x[j]]) F[i][y[j]]=1;
			if (F[i][y[j]]) F[i][x[j]]=1;
		}
	}
	
	for (int i=1;i<n;i++)
		for (int j=i+1;j<=n;j++){
			if (cant[i]|cant[j]) continue;
			int flg=1;
			for (int k=1;k<=n;k++)
				if (F[i][k]&F[j][k]){ flg=0; break;}
			Ans+=flg;
		}
	return printf("%d\n",Ans), 0;
}

Measured memory_bytes: 1792
//import java.util.Scanner;
import java.io.*;

class Main {
    public static void main(String[] args)throws IOException{ 
    	InputStreamReader in = new InputStreamReader(System.in);
        BufferedReader reader = new BufferedReader(in);
    	   	                                                 
    	String s = reader.readLine();
        String p = reader.readLine();        
        s = s + s;

        if(s.indexOf(p) != -1){
        System.out.println("Yes");
        }      
        else{
        System.out.println("No");
        }
    }
}

Measured memory_bytes: 24332
#include <stdio.h>
#include <stdlib.h>

typedef struct {
	long long key;
	int id;
} data;

typedef struct {
	data *obj;
	int size;
} max_heap;

void push(data x, max_heap* h)
{
	int i = h->size;
	data tmp;
	h->obj[(h->size)++] = x;
	while (1) {
		if (i == 0) break;
		else if (h->obj[i].key > h->obj[(i-1)/2].key) {
			tmp = h->obj[(i-1)/2];
			h->obj[(i-1)/2] = h->obj[i];
			h->obj[i] = tmp;
			i = (i - 1) / 2;
		} else break;
	}
}

data pop(max_heap* h)
{
	int i = 0, j;
	data output = h->obj[0], tmp;
	h->obj[0] = h->obj[--(h->size)];
	while (1) {
		if (i * 2 + 1 >= h->size) break;
		else if (i * 2 + 2 >= h->size) j = i * 2 + 1;
		else if (h->obj[i*2+1].key > h->obj[i*2+2].key) j = i * 2 + 1;
		else j = i * 2 + 2;
		if (h->obj[j].key > h->obj[i].key) {
			tmp = h->obj[j];
			h->obj[j] = h->obj[i];
			h->obj[i] = tmp;
			i = j;
		} else break;
	}
	return output;
}

int main()
{	
	int i, Q, q[200001];
	long long a[200001], b[200001];
	scanf("%d", &Q);
	for (i = 1; i <= Q; i++) {
		scanf("%d", &(q[i]));
		if (q[i] == 1) scanf("%lld %lld", &(a[i]), &(b[i]));
		else a[i] = 1 << 30;
	}
	
	long long min = b[1];
	data d;
	max_heap h[2];
	h[0].size = 0;
	h[1].size = 0;
	h[0].obj = (data*)malloc(sizeof(data) * (Q + 1));
	h[1].obj = (data*)malloc(sizeof(data) * (Q + 1));
	d.key = a[1];
	push(d, &(h[0]));
	d.key *= -1;
	push(d, &(h[1]));
	
	for (i = 2; i <= Q; i++) {
		if (q[i] == 2) {
			printf("%lld %lld\n", h[0].obj[0].key, min);
			continue;
		}
		if (a[i] >= h[0].obj[0].key && a[i] <= -h[1].obj[0].key) {
			d.key = a[i];
			push(d, &(h[0]));
			d.key *= -1;
			push(d, &(h[1]));
			min += llabs(h[0].obj[0].key - a[i]) + b[i];
		} else if (a[i] < h[0].obj[0].key) {
			d = pop(&(h[0]));
			d.key *= -1;
			push(d, &(h[1]));
			d.key = a[i];
			push(d, &(h[0]));
			push(d, &(h[0]));
			min += llabs(h[1].obj[0].key + h[0].obj[0].key) + llabs(h[0].obj[0].key - a[i]) + b[i];
		} else {
			d = pop(&(h[1]));
			d.key *= -1;
			push(d, &(h[0]));
			d.key = -a[i];
			push(d, &(h[1]));
			push(d, &(h[1]));
			min += llabs(h[0].obj[0].key - a[i]) + b[i];
		}
	}
	
	fflush(stdout);
	return 0;
}

Measured memory_bytes: 11840
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
#include <algorithm>
#include <math.h> 
#include <set>
#include <map>

using namespace std;

#define ll long long int
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repp(i, n) for(int i = 1; i <= n; i++)
#define sort(v) sort((v).begin(), (v).end())
#define riverse(v) reverse((v).begin(), (v).end())
using vi = vector<int>;
using vs = vector<string>;
using vll = vector<ll>;
using vvi = vector<vi>;
const ll MOD = 1e9 + 7;


int main() {
    int N;
    cin >> N;
    vi a(N);
    rep(i, N) cin >> a[i];
    int on = 1;
    bool frag = false;
    int ans = -1;
    rep(i, N) {
        on = a[on-1];
        if (on == 2) {
            ans = i + 1;
            break;
        }
    }
    cout << ans << endl;
}

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

#define REP(i,n) for(int i=0;i<n;i++)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define eb emplace_back

using i32 = int;
using i64 = long long;
using ll = long long;

using namespace std;

//last revised 13.Feb.2020
struct UnionFind{
public:
    static const int MAX_N = 200020;

    int par[MAX_N];
    int rank[MAX_N];

    UnionFind(int N){
        for(int i=0;i<N;i++){
            par[i] = i;
            rank[i] = 0;
        }
    }
    int find(int x){
        if(x == par[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;

        if(rank[x] < rank[y])par[x] = y;
        else{
            par[y] = x;
            if(rank[x] == rank[y])rank[x]++;
        }
    }
    bool same(int x,int y){
        return find(x) == find(y);
    }
};

template<class T> class Graph{
public:
    struct edge{
        int to;
        T cost;
        edge(int to,T cost):to(to),cost(cost){}
    };
    int N,M;
    vector<vector<edge>> g;
    Graph(int N,int M):N(N),g(N),M(M){}
    void add_edge(int a,int b,T cost = 1){
       g[a].emplace_back(b,cost);
    }
    void input(bool undirected = true,bool unweighted = true){
        for(int i = 0;i < M;i++){
            int a,b;
            T c = 1;
            cin >> a >> b;
            //a--,b--; // 1-indexed!!
            if(!unweighted) cin >> c;
            g[a].emplace_back(b,c);
            if(undirected) g[b].emplace_back(a,c);
        }
    }

};

template<class T> class MST : public Graph<T>,public UnionFind{
public:
    struct E{
        int from, to; T cost;
        E(int f,int t,T c):from(f),to(t),cost(c){}
    };
    static bool comp(const E& e1,const E& e2){
        return e1.cost < e2.cost;
    }
    int N,M;
    vector<E> es;

    vector<E> used; // edge of minimum spanning tree!
    MST(int N,int M):N(N),M(M),Graph<T>(N,M),UnionFind(N+1){}
    void add_edge(int a,int b,T c){
        Graph<T>::add_edge(a,b,c);
    }
    T kruskal();
};
template<class T>
T MST<T>::kruskal() {
    for(int i = 0;i < N;i++){
        for(auto e : Graph<T>::g[i]) es.emplace_back(i,e.to,e.cost);
    }
    sort(es.begin(),es.end(),comp);
    T res = 0;
    for(int i = 0;i < es.size();i++){
       auto e = es[i];
       if(!UnionFind::same(e.from,e.to)){
           UnionFind::unite(e.from,e.to);
           used.emplace_back(e);
           res += e.cost;
       }
    }
    return res;
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n,m;cin >> n >> m;
    MST<int64_t> G(n,m);
    G.input(true,false);
    cout << G.kruskal() << '\n';
}


Measured memory_bytes: 12532
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e3 + 5;
const ll mod = 1e9 + 7;
const double pi = acos(-1);
ll fastpow(ll b, ll e) {
    if (!e)
        return 1;
    ll ret = fastpow(b, e / 2);
    ret = (ret * ret) % mod;
    if (e % 2)
        ret = (ret * b) % mod;
    return ret;
}
ll modinv(ll x) {
    return fastpow(x, mod - 2);
}
double torad(double ang) {
    return ang * pi / 180.0;
}

double p[N], dp[N][N];
int main()
{
    ///smallest/largest case
    ///initialize
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &p[i]);
    }
    for (int i = 0; i <= n; i++) {
        if (i * 2 > n)
            dp[0][i] = 1;
        else
            dp[0][i] = 0;
        dp[i][n + 1] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            double a = dp[i - 1][j] * (1 - p[i]);
            double b = dp[i - 1][j + 1] * p[i];
            dp[i][j] = a + b;
        }
    }
    /*
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n + 1; j++)
            cout << dp[i][j] << ' ';
        cout << '\n';
    }
    */
    printf("%.9f", dp[n][0]);
    return 0;
}


Measured memory_bytes: 70656
// -*- mode:c++; coding:utf-8; indent-tabs-mode:nil; -*-
 
#include <iostream>
 
static void print_ints(const int as[], const unsigned int n) {
  const char* sep = "";
  for (unsigned int i = 0; i < n; ++i) {
    std::cout << sep << as[i];
    sep = " ";
  }
  std::cout << std::endl;
}

static unsigned int swap_count = 0;

static void print_swap_count(void) {
  std::cout << swap_count << std::endl;
}

static void swap(int* a, int* b) {
  ++swap_count;
  int tmp = *a;
  *a = *b;
  *b = tmp;
}

void bubble_sort(int as[], const unsigned int n) {
  for (unsigned int j = 0; j < n-1; ++j) {
    for (unsigned int i = n-1; i > j; --i) {
      if (as[i-1] > as[i]) {
        swap(&as[i-1], &as[i]);
      }
    }
  }
}
 
int main(void) {
  unsigned int n;
  std::cin >> n;
  int as[n];
  for (unsigned int i = 0; i < n; ++i) {
    std::cin >> as[i];
  }

  bubble_sort(as, n);
  print_ints(as, n);
  print_swap_count();

  return 0;
}
// end

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

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

    vector<int> v;
    for(int i = 0; i <= a; ++i){
        for(int j = 0; j <= b; ++j){
            for(int k = 0; k <= c; ++k){
                v.push_back(500*i + 100*j + 50*k);
            }
        }
    }

    int target;
    cin >> target;

    cout << count(v.begin(), v.end(), target) << endl;
}


Measured memory_bytes: 1400
import Control.Applicative
import Control.Monad

main :: IO ()
main = do
  ls <- map read . lines <$> getContents
  forM_ ls $ print . solve

solve :: Int -> Int
solve n = sum [1 | a <- [0..9], b <- [0..9], c <- [0..9], d <- [0..9], a+b+c+d == n]

Measured memory_bytes: 4488
def main():
    s = input()
    t = input()
    len_s = len(s)
    len_t = len(t)
    ans = float("inf")
    for i in range(len_s - len_t + 1):
        now = 0
        for j in range(len_t):
            if s[i + j] != t[j]:
                now += 1
        ans = min(ans, now)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9140
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main() {
  int N,sum=0;
  cin>>N;
  int d[N];
  for(int i=0;i<N;i++) cin>>d[i];
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      sum+=d[i]*d[j];
    }
  }
  cout<<sum<<endl;
}	


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <deque>
#include <climits>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
//#include <tuple>

#define break break
#define continue continue
#define INF INT_MAX>>1 
#define SIZE 100010
#define MOD 1000000007
#define rep(i, n) for(int i=0; i<(int)(n); i++)
#define rep2(i, from, to) for(int i=(from); i<(int)(to); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define LLPair pair<ll, ll>
#define vint vector<int>
#define vll vector<ll>
typedef long long ll;

using namespace std;


int main(void){
	string str; cin >> str;
	if(str == "SUN") cout << 7 << endl;
	if(str == "MON") cout << 6 << endl;
	if(str == "TUE") cout << 5 << endl;
	if(str == "WED") cout << 4 << endl;
	if(str == "THU") cout << 3 << endl;
	if(str == "FRI") cout << 2 << endl;
	if(str == "SAT") cout << 1 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define int long long
using namespace std;
typedef vector<int>   vint;
typedef pair<int,int> pint;

signed main()
{
    int N,X; cin>>N>>X;
    vint a(N);
    REP(i,N) cin>>a[i];

    sort(ALL(a));
    REP(i,N-1) a[i+1]+=a[i];

    int ans;
    if(a[N-1]<X) ans=N-1;
    else if(a[N-1]==X) ans=N;
    else{
        ans=upper_bound(ALL(a),X)-a.begin();
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 256
#include <iostream>

using namespace std;

#define MAX_N 200000

int main(int argc, const char * argv[]) {
    int n;
    int a[MAX_N];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    
    int i = n-1;
    while (i >= 0){
        cout << a[i] << " ";
        i -= 2;
    }
    if (i == -1) i = 0;
    else i = 1;
    while (i < n-1) {
        cout << a[i] << " ";
        i += 2;
    }
    cout << endl;
}

Measured memory_bytes: 2944
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <stack>
#include <queue>

#define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i)
#define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, 0, n)
#define REPC(x,c) for(const auto& x:(c))
#define VS vector<string>
#define VL vector<long long>
#define VI vector<int>
#define VVI vector<vector<int>>
#define VVL vector<vector<ll>>
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort(ALL(x))
#define RSORT(x) sort((x).rbegin(),(x).rend())
#define PAIR pair<ll,ll>
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

using  ll = long long;
constexpr int MOD = 1000000007;
using namespace std;

ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

VL prime_decomposition(ll n) {
	ll i = 2;
	VL table{};
	while (i * i <= n) {
		while (n % i == 0) {
			n /= i;
			table.emplace_back(i);
		}
		++i;
	}
	if (n > 1) {
		table.emplace_back(n);
		return table;
	}
	return table;
}

int main() {
	ll n, a;
	cin >> n >> a;
	cout << n * n - a << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>pii;
typedef vector<int>vi;

#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define fi first
#define se second
#define de(x) cout<<#x<<"="<<x<<endl;
#define dd(x) cout<<#x<<"="<<x<<" " ;
#define pb(x) push_back(x)
#define per(i,a,b) for(int i=(b)-1;i>=(a);--i)
const int N=2e6+5;
const ll mod=1e9+7;
const ll mod1=13;
char s[N];
int len;
ll dp[N][15];
ll dfs(int pos,ll sum){
	if(pos==0){
		
		if(sum==5)return 1;
		return 0;
	}
	if(dp[pos][sum]!=-1)return dp[pos][sum];
	ll cur=0;
	if(s[pos]!='?'){
		ll res=(sum*10ll+s[pos]-'0')%mod1;
		cur=dfs(pos-1,res);
		dp[pos][sum]=cur%mod;
		return cur%mod;
	}
	for(int i=0;i<=9;++i){
		ll res;
		res=(sum*10ll+i)%mod1;
		cur=((cur+dfs(pos-1,res))%mod+mod)%mod;	
	}
	dp[pos][sum]=cur%mod;
	return cur%mod;
}
int main()
{

	memset(dp,-1,sizeof(dp));
	scanf("%s",s+1);
	
	len=strlen(s+1);
	reverse(s+1,s+len+1);
	
	ll ans=dfs(len,0);
	cout<<ans<<endl;
	return 0;
}

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

typedef long long   signed int LL;
typedef long long unsigned int LU;

#define incID(i, l, r) for(int i = (l)    ; i <  (r); i++)
#define incII(i, l, r) for(int i = (l)    ; i <= (r); i++)
#define decID(i, l, r) for(int i = (r) - 1; i >= (l); i--)
#define decII(i, l, r) for(int i = (r)    ; i >= (l); i--)
#define  inc(i, n) incID(i, 0, n)
#define inc1(i, n) incII(i, 1, n)
#define  dec(i, n) decID(i, 0, n)
#define dec1(i, n) decII(i, 1, n)

#define inII(v, l, r) ((l) <= (v) && (v) <= (r))
#define inID(v, l, r) ((l) <= (v) && (v) <  (r))

#define PB push_back
#define EB emplace_back
#define MP make_pair
#define FI first
#define SE second
#define PQ priority_queue

#define  ALL(v)  v.begin(),  v.end()
#define RALL(v) v.rbegin(), v.rend()
#define  FOR(it, v) for(auto it =  v.begin(); it !=  v.end(); ++it)
#define RFOR(it, v) for(auto it = v.rbegin(); it != v.rend(); ++it)

template<typename T> bool   setmin(T & a, T b) { if(b <  a) { a = b; return true; } else { return false; } }
template<typename T> bool   setmax(T & a, T b) { if(b >  a) { a = b; return true; } else { return false; } }
template<typename T> bool setmineq(T & a, T b) { if(b <= a) { a = b; return true; } else { return false; } }
template<typename T> bool setmaxeq(T & a, T b) { if(b >= a) { a = b; return true; } else { return false; } }
template<typename T> T gcd(T a, T b) { return (b == 0 ? a : gcd(b, a % b)); }
template<typename T> T lcm(T a, T b) { return a / gcd(a, b) * b; }

// ---- ----

int main() {
	int q;
	cin >> q;
	inc(qq, q) {
		LL a, b, ans;
		cin >> a >> b;
		
		if(a == b) { ans = 2 * (a - 1); } else {
			LL v = 2 * max(0.0, sqrt(a * b) - 1.0);
			inc(i, 10) {
				if((v / 2) * ((v + 1) / 2) >= a * b) { break; }
				ans = v;
				v++;
				if(i == 9) { assert(false); }
			}
			ans -= 2;
		}
		
		cout << ans << "\n";
	}
	
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <fstream>
#include <string>
#include <vector>
#include <tuple>
#include <deque>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <bitset>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <numeric>
#include <string.h>
#define rep(i, x) for (int i = 0; i < (int)(x); i++)
#define repn(i, x) for (int i = 1; i <= (int)(x); i++)
#define repr(i, x) for (int i = ((int)(x) - 1); i >= 0; i--)
#define reprn(i, x) for (int i = ((int)(x)); i > 0; i--)
#define all(x) (x).begin(),(x).end()
typedef long long int64;
using namespace std;
const double PI = 3.14159265358979323846;
const double EPS = 1e-12;
const int INF = 1<<29;
const long long INFL = 1e18;
const int MOD = 1000000007;
const int MAX = 210000;

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

//逆元を求める関数
long long fac[MAX], finv[MAX], inv[MAX];
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
      fac[i] = fac[i-1] * i % MOD;
      inv[i] = MOD - inv[MOD%i] * (MOD/i) % MOD;
      finv[i] = finv[i-1] * inv[i] % MOD;
    }
}
//組み合わせ
long long COM (int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n-k] % MOD) % MOD;
}

void solve() {
		int64 n; cin >> n;
		vector<pair<int64, int64>> wk(n);
		rep (i, n) {
			cin >> wk[i].second >> wk[i].first;
		}
		sort(all(wk));
		int64 nt = 0;
		rep (i, n) {
			nt += wk[i].second;
			if (nt > wk[i].first) {
				cout << "No" << endl;
				return;
			}
		}
		cout << "Yes" << endl;
    return;
}

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



Measured memory_bytes: 3328
def kalin(s):
  N=len(s)
  for i in range(N//2):
    if s[i]!=s[-1-i]:
      return False
  return True

def strong(s):
  N=len(s)
  tail = (N-1)//2
  s0=s[0:tail]
  head = (N+3)//2
  s1=s[head-1:]
  # print('s0={} s1={}'.format(s0,s1))
  return kalin(s0) and kalin(s1) and kalin(s)  

if strong(input()):
  print('Yes')
else:
  print('No')

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n - 1; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define FORR(i,m,n) for(int i = m - 1; i >= n; i--)
#define ALL(v) v.begin(), v.end()
#define itn int
#define Yes() cout << "Yes" << endl
#define No() cout << "No" << endl
#define YES() cout << "YES" << endl
#define NO() cout << "NO" << endl
#define println(x) cout << x << endl
#define print(x) cout << x << " "
template<typename T, typename U>
inline bool CMAX(T &m, U x) { if (m < x) { m = x; return true; } return false; }
template<typename T, typename U>
inline bool CMIN(T &m, U x) { if (m > x) { m = x; return true; } return false; }

typedef long long lint;
typedef long double ldouble;
const int INF = 1e9;
const lint LINF = 1e18;
const int MOD = 1e9+7;
int main(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n){
        cin >> a[i];
    }
    bool flag = true;
    sort(ALL(a));
    REP(i,n - 1){
        if(a[i] == a[i + 1]){
            flag = false;
            break;
        }
    }
    if(flag){
        YES();
    }else{
        NO();
    }
    return 0;
}

Measured memory_bytes: 1024
loop {
  n, x = gets.split(" ").map(&:to_i)

  if n+x == 0
    break
  end

  y = 0

  for i in 1..n
    for j in i+1..n
      for k in j+1..n
        if i + j + k == x
          y += 1
        end
      end
    end
  end
  puts y    
}

Measured memory_bytes: 8704
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 305;
const int MOD = 1e9 + 7;

struct ModInt
{
  int val;

  ModInt (): val(0) {}

  ModInt (int _val): val(_val) {}

  ModInt operator+(ModInt b)
  {
    ModInt c(val + b.val);
    if (c.val >= MOD)
      c.val -= MOD;
    return c;
  }

  void operator+=(ModInt b)
  {
    val += b.val;
    if (val >= MOD)
      val -= MOD;
  }
};

ModInt dp[2][N][N][3];
int n, m;
vector <pair<int, int> > query[N];

int main()
{
  cin >> n >> m;


  for (int i = 0; i < m; i++)
  {
    int l, r, x;
    cin >> l >> r >> x;
    query[r].push_back({l, x});
  }
  /*
  for (int i = 0; i <= n; i++)
  {
    sort(query[i].begin(), query[i].end());
    vector <pair <int, int> > tmp;
    if (!query[i].empty())
      tmp.push_back(query[i][0]);

    for (int j = 0; j < (int)query[i].size(); j++)
    {
      if (j != (int)query[i].size() - 1)
      {
        if (query[i][j].first == query[i][j + 1].first && query[i][j].second != query[i][j + 1].second)
        {
          cout << 0 << '\n';
          return 0;
        }
        if (query[i][j].first < query[i][j + 1].first && query[i][j].second < query[i][j + 1].second)
        {
          cout << 0 << '\n';
          return 0;
        }
        if (query[i][j].second != query[i][j + 1].second)
          tmp.push_back(query[i][j + 1]), tmp.push_back(query[i][j]);
      }
      else
        tmp.push_back(query[i][j]);

    }
    query[i] = tmp;
  }
  */
  int ptr = 0;
  dp[ptr][0][0][1].val = 1;

  for (int i = 0; i <= n; i++)
  {
    for (int l1 = 0; l1 <= n; l1++)
      for (int l2 = 0; l2 <= n; l2++)
        for (int o = 0; o < 3; o++)
        dp[ptr ^ 1][l1][l2][o].val = 0;



    for (int l1 = 0; l1 <= i; l1++)
    {
      for (int l2 = 0; l2 <= i; l2++)
      {
        for (int last_el = 0; last_el < 3; last_el++)
        {
          int pos_r, pos_g, pos_b;

          if (last_el == 0)
          {
            pos_r = i;
            pos_g = l1;
            pos_b = l2;
          }
          else if (last_el == 1)
          {
            pos_r = l1;
            pos_g = i;
            pos_b = l2;
          }
          else if (last_el == 2)
          {
            pos_r = l1;
            pos_g = l2;
            pos_b = i;
          }

          bool ok = true;
          for (auto it : query[i])
          {
            int cnt = (int)(pos_r >= it.first) + (int)(pos_g >= it.first) + (int)(pos_b >= it.first);
            ok &= cnt == it.second;
          }

          if (!ok)
            dp[ptr][l1][l2][last_el].val = 0;

          dp[ptr ^ 1][pos_g][pos_b][0] += dp[ptr][l1][l2][last_el];
          dp[ptr ^ 1][pos_r][pos_b][1] += dp[ptr][l1][l2][last_el];
          dp[ptr ^ 1][pos_r][pos_g][2] += dp[ptr][l1][l2][last_el];
        }
      }
    }
    ptr ^= 1;
  }

  ModInt res;
  res.val = 0;

  for (int i = 0; i <= n; i++)
    for (int j = 0; j <= n; j++)
      for (int k = 0; k < 3; k++)
        res += dp[ptr ^ 1][i][j][k];

  cout << res.val << '\n';
  return 0;
}


Measured memory_bytes: 2432
#include<bits/stdc++.h>
// Begin Header {{{
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i,n) for(ll i=0; i<n; i++)
#define loop(i, j, n) for(ll i=j; i<n; i++)
#define all(x) (x).begin(), (x).end()
constexpr int INF  = 0x3f3f3f3f;
const long long mod=1e9+7;
const long double PI = acos(-1);
// }}} End Header

int main() {
	string s;
	cin >> s;
	cout << s.substr(0, 3) << endl;
	return 0;
}

Measured memory_bytes: 3596
#include<bits/stdc++.h>
using namespace std;
int const nax = 4e5 + 10;
int n, k , c;
char s[nax];

bool work[nax];

int dp[nax];
int dp2[nax];

int pref[nax];
int suf[nax];
int ex[nax];

int w[nax];

int main () {
    scanf("%d %d %d", &n, &k, &c);
    scanf("%s", s + 1);

    for (int i = 1 ;  i <= n ; ++ i)
        work[i] = s[i] == 'o';


    for (int i = 1 ; i <= n ; ++ i) {
        if (s[i] == 'o') {
            int last = i - c - 1;
            int toAdd = 0;
            if (last > 0) toAdd = max(toAdd, pref[last]);
            dp[i] = toAdd + 1;
        }

        pref[i] = max(pref[i - 1], dp[i]);
    }

    for (int i = n ; i >= 1 ; -- i) {
        if (s[i] == 'o') {
            int nxt = i + c + 1;
            dp2[i] = 1 + suf[nxt];
        }

        suf[i] = max(suf[i + 1], dp2[i]);
    }

    deque<pair<int, int>> d;

  /*  for (int i = 1 ; i <= n ; ++ i)
        fprintf(stderr, "%d ", pref[i]);

    fprintf(stderr, "\n");

    for (int i = 1 ; i <= n ; ++ i)
        fprintf(stderr, "%d ", suf[i]);
    fprintf(stderr, "\n");*/


    for (int i = 1 ; i <= n ; ++ i) {

        while (!d.empty() && c + d.front().first + 1  <= i) d.pop_front();
        int h = d.empty() ? 0 : d.front().second;

       // if (i == 5) fprintf(stderr, "huh %d %d\n", d.front().first, d.front().second);

        h = max(h, suf[i + 1] + pref[max(0, i - c - 1)]);



        if (s[i] == 'o') {
            while (!d.empty() && d.front().second <= dp[i] + suf[i + c + 1]) d.pop_back();
            d.emplace_back(i, pref[i] + suf[i + c + 1]);
        }

       // fprintf(stderr, "%d ", h);
        if (s[i] == 'o' && h < k) printf("%d\n", i);


    }

    fprintf(stderr, "\n");

}
/*
    Good Luck
        -Lucina
*/


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

long long gcd(long long a,long long b){
  if (a%b==0 )return b;
  else return gcd(b,a%b);
}
int main() {
  string n; cin>>n;
  int m=stoi(n);
  if(n.size()%2==0){
    int sum=0;
    int digit=n.size()/2;
    for(int i=0;i<digit;i++){
      sum+=pow(10,2*i);
    }
    cout<<sum*9<<endl;
  }
  else{
    int digit=n.size()/2;
    int sum=0;
    for(int i=0;i<digit;i++){
      sum+=9*pow(10,2*i);
    }
    cout<<sum+m+1-pow(10,n.size()-1)<<endl;
  }
}


Measured memory_bytes: 256
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
	string s;
	cin>>s;
	for(int i=0;i<s.length();i++)
	{
		if(s[i]=='7')
		{
			cout<<"Yes\n";
			return 0;
		}
	}
	cout<<"No\n";
}

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

int main() {
  int a, b, c, d;
  cin >> a >> b >> c >>d;
  
  if (a + b > c + d) {
    cout << "Left" << endl;
  }
  else if (a + b == c + d) {
    cout << "Balanced" << endl;
  }
  else {
    cout << "Right" << endl;
  }
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int ri,i;
  int sya=100000;
  int total,ans;
  scanf("%d",&ri);
  for(i=0;i<ri;i++){
    sya = sya * 1.05;
    if(sya%1000!=0){
      sya = sya-sya%1000+1000;
    }
  }
  printf("%d\n",sya);
  return 0;
}
    

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

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mp make_pair
#define pb push_back
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)

int main(){
  int N;
  cin >> N;
  int a[N];
  rep(i,N) cin >> a[i];
  int ans=INT_MAX;
  rep(i,N){
    int t=0;
    while(a[i]%2==0){
      a[i]/=2;
      t++;
    }
    ans = min(ans,t);
  }
  cout << ans << endl;

  return 0;

}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cmath>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <random>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <cstring>
#include <iomanip>
using namespace std;

#define int long long
#define double long double
#define mp make_pair
#define debug(x) cerr << #x << ": " << x << '\n';
#define fi first
#define se second
#define pb push_back
//typedef long long ll;
typedef pair<int, int> pii;
 
void fast() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
}

const int N = 2e5 + 10;
int a[N], b[N];

signed main() {
	fast();
	int n;
	cin >> n;
	set<pair<int, int>> se;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	for (int i = 0; i < n; i++) {
		cin >> b[i];
		se.insert(mp(b[i], i));
	}
	for (int i = 0; i < n; ) {
		int j = i;
		for (; j < n && a[j] == a[i]; j++) {
			se.erase(mp(b[j], j));
		}
		j = i;
		for (; j < n && a[j] == a[i]; j++) {
			if (b[j] == a[j]) {
				if (se.empty()) {
					cout << "No";
					return 0;
				}
				if (se.begin()->first != a[j]) {
					int ii = se.begin()->second;
					se.erase(se.begin());
					se.insert(mp(b[j], ii));
					swap(b[j], b[ii]);
				} else if (se.rbegin()->first != a[j]) {
					auto it = se.end();
					--it;
					int ii = it->second;
					se.erase(it);
					se.insert(mp(b[j], ii));
					swap(b[j], b[ii]);
				} else {
					cout << "No";
					return 0;
				}
			}
		}
		j = i;
		for (; j < n && a[j] == a[i]; j++) {
			se.insert(mp(b[j], j));
		}
		i = j;
	}
	cout << "Yes\n";
	for (int i = 0; i < n; i++) {
		cout << b[i] << ' ';
	}
	return 0;
}

Measured memory_bytes: 19244
#include <iostream>
#include <cstring>
using namespace std;
bool g[60][60];
bool visited[60];
int N;

void dfs(int x){
    if(visited[x]) return;
    visited[x] = true;
    for(int i = 0; i < N; ++i){
        if(g[x][i]) dfs(i);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    memset(g, false, sizeof(g));
    int M;
    cin >> N >> M;
    for(int i = 0; i < M; ++i){
        int a,b;
        cin >> a >> b;
        a--; b--;
        g[a][b] = g[b][a] = true;
    }

    int cnt = 0;
    for(int i = 0; i < N; ++i){
        for(int j = 0; j < N; ++j){
            if(!g[i][j]) continue;
            memset(visited, false, sizeof(visited));
            g[i][j] = g[j][i] = false;
            dfs(0);
            bool flag = true;
            for(int k = 0; k < N; ++k) if(!visited[k]) flag = false;
            if(!flag) cnt++;
            g[i][j] = g[j][i] = true;
        }
    }
    cout << cnt/2 << endl;
    return 0;
}
//Saw the editorial

Measured memory_bytes: 3612
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.InputStream;
import java.io.PrintWriter;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Set;
import java.util.Stack;
import java.util.TreeMap;
import java.util.TreeSet;

import static java.util.Comparator.*;

public class Main {
    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        Solver solver = new Solver(System.in, out);
        solver.solve();
        out.close();
    }
}
class Solver {
	Scanner sc;
	PrintWriter out;
    public Solver(InputStream in, PrintWriter out) {
    	sc = new Scanner(in);
    	this.out = out;
    }
    // ==========================================================
	List<PP> list = new ArrayList<>();
    public void solve() {
		int N = ni();
		int x, l;
		for (int i = 0; i < N; i++) {
			x = ni();
			l = ni();
			list.add(new PP(x-l, x+l));
		}
		list.sort(comparing(PP::getVal));
		int ans = 0, t = -1000000010;
		for(PP p : list) {
			if(t <= p.key) {
				ans++;
				t = p.val;
			}
		}
		out.println(ans);
    }
    // Set に入れるなら　PPKEY　を使う！
    static class PP{
    	public int key, val;
    	public PP(int key, int val) {
    		this.key = key;
    		this.val = val;
    	}
		public int getKey() {
			return key;
		}
		public void setKey(int key) {
			this.key = key;
		}
		public int getVal() {
			return val;
		}
		public void setVal(int val) {
			this.val = val;
		}
    }
    // ------------------------------------------
    // 入力
    // ------------------------------------------
    public int ni() {
    	return sc.nextInt();
    }
    public long nl() {
    	return sc.nextLong();
    }
    public String ns() {
    	return sc.next();
    }
    public char[] nc() {
    	return sc.next().toCharArray();
    }
    public int[] ndi(int N) {
    	int[] ans = new int[N];
    	for (int i = 0; i < N; i++) {
			ans[i] = ni();
		}
    	return ans;
    }
    public long[] ndl(int N) {
    	long[] ans = new long[N];
    	for (int i = 0; i < N; i++) {
			ans[i] = nl();
		}
    	return ans;
    }
    public String[] nds(int N) {
    	String[] ans = new String[N];
    	for (int i = 0; i < N; i++) {
			ans[i] = ns();
		}
    	return ans;
    }
    public char[][] ndc(int N) {
    	char[][] ans = new char[N][];
    	for (int i = 0; i < N; i++) {
			ans[i] = nc();
		}
    	return ans;
    }
    public int[][] nddi(int N, int S) {
    	int[][] ans = new int[N][S];
    	for (int i = 0; i < N; i++) {
			for (int j = 0; j < S; j++) {
				ans[i][j] = ni();
			}
		}
    	return ans;
    }
}


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

#define dump(...) do{print_vars(cout<<"# "<<#__VA_ARGS__<<'=',__VA_ARGS__);cout<<endl;}while(0)
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define all(c) begin(c),end(c)
#define mp make_pair
#define mt make_tuple

using uint=unsigned;
using ll=long long;
using ull=unsigned long long;
using vi=vector<int>;
using vvi=vector<vi>;
using vl=vector<ll>;
using vvl=vector<vl>;
using vd=vector<double>;
using vvd=vector<vd>;
using vs=vector<string>;
template<typename T,typename U>bool chmin(T& a,const U& b){return a>b?(a=b,1):0;}
template<typename T,typename U>bool chmax(T& a,const U& b){return a<b?(a=b,1):0;}

void print_vars(ostream&){}
template<typename Car,typename... Cdr>
void print_vars(ostream& os,const Car& car,const Cdr&... cdr){
	print_vars(os<<car<<(sizeof...(cdr)?",":""),cdr...);
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& p){
	return os<<'('<<p.first<<','<<p.second<<')';
}

template<int I,typename Tuple>
void print_tuple(ostream&,const Tuple&){}
template<int I,typename Car,typename... Cdr,typename Tuple>
void print_tuple(ostream& os,const Tuple& t){
	os<<get<I>(t)<<(sizeof...(Cdr)?",":"");
	print_tuple<I+1,Cdr...>(os,t);
}
template<typename... Args>
ostream& operator<<(ostream& os,const tuple<Args...>& t){
	print_tuple<0,Args...>(os<<'(',t);
	return os<<')';
}

template<typename Ch,typename Tr,typename C>
basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){
	os<<'[';
	for(auto i=begin(c);i!=end(c);++i)
		os<<(i==begin(c)?"":" ")<<*i;
	return os<<']';
}

constexpr int INF=1e9;
constexpr int MOD=1e9+7;
constexpr double EPS=1e-9;

bool calc(vi a,int m)
{
	vector<tuple<int,int>> cs={mt(-1,0)};
	repi(i,1,a.size()){
		if(a[i-1]>=a[i]){
			bool ok=false;
			per(j,a[i]){
				for(;;cs.pop_back()){
					int k,x; tie(k,x)=cs.back();
					if(k<=j)
						break;
				}
				int k,x; tie(k,x)=cs.back();
				if(k<j)
					x=0;
				else
					cs.pop_back();
				if(x+1<m){
					cs.emplace_back(j,x+1);
					ok=true;
					break;
				}
			}
			if(!ok)
				return false;
		}
		//dump(m,i,a[i],cs);
	}
	return true;
}

int main()
{
	#ifndef _GLIBCXX_DEBUG
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	constexpr char endl='\n';
	#endif

	for(int n;cin>>n&&n;){
		vi a(n);
		rep(i,n) cin>>a[i];

		int lo=1,hi=n;
		while(lo<hi){
			int mi=(lo+hi)/2;
			if(calc(a,mi))
				hi=mi;
			else
				lo=mi+1;
		}
		cout<<lo<<endl;
	}
}


Measured memory_bytes: 1808
#include<iostream>
#include<algorithm>
#include<set>
#include<vector>
#include<tuple>
#define TT std::tuple<int,int,int>
std::set<int> ap;
std::vector<TT> P;
int N;
int ans;
int main() {
	std::cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b;
		std::cin >> a >> b;
		P.push_back(TT{ a,b,0 });
	}
	for (int j = 0; j < N; j++) {
		int c, d;
		std::cin >> c >> d;
		P.push_back(TT{ c,d,1 });
	}
	std::sort(P.begin(), P.end());
	for (auto u : P) {
		int a, b, c;
		std::tie(a, b, c) = u;
		if (!c) {
			ap.insert(b);
		}
		else {
			for (int i = b; i >= 0; i--) {
				auto itr = ap.find(i);
				if(itr!=ap.end()){
					ans++;
					ap.erase(itr);
					break;
				}
			}
		}

	}
	std::cout << ans << std::endl;
	return 0;
}


Measured memory_bytes: 256
<?php
$n = int();
for($i = 1; $i <= $n; $i++){
  $count[$i] = 0;
}
for($i = 0; $i < $n-1; $i++){
  list($a, $b) = ints();
  $count[$a]++;
  $count[$b]++;
  $g[$a][] = $b;
  $g[$b][] = $a;
  $aArray[] = $a;
  $bArray[] = $b;
}
$max = max($count);
$root = array_search($max, $count);
dfs(-1, $root, 0);
echo $max,"\n";
for($i = 0; $i < $n-1; $i++){
  echo $color[$aArray[$i]][$bArray[$i]],"\n";
}

function dfs($before, $from, $prevColor){
  global $g, $color;
  $c = 1;
  foreach($g[$from] as $to){
    if($to != $before){
      while($c == $prevColor)$c++;
      $color[$from][$to] = $color[$to][$from] = $c;
      dfs($from, $to, $c);
      $c++;
    }
  }
}

function ints(){
  return array_map("intval", explode(" ", trim(fgets(STDIN))));
}
function int(){
  return intval(trim(fgets(STDIN)));
}

Measured memory_bytes: 98032
import sys
sys.setrecursionlimit(10**7)
import itertools


#debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    w, h, x, y = map(int, input().split())

    area = w * h
    half = area / 2.0

    if 2*x == w and 2*y == h:
        flag = 1
    else:
        flag = 0

    print(half, flag)

solve()

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)

int main() {
	int n;
	long double ans;
	cin>>n;
	vector <long double> val(n);
	rep(i,n)cin>>val[i];
	sort(val.begin(),val.end());
	ans=val[0];
	rep(i,n){
	    ans+=val[i];
	    ans/=2;
	}
	cout<<setprecision(10)<<ans;
	return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		byte a = scanner.nextByte();
		scanner.nextByte();
		scanner.nextByte();
		scanner.nextByte();
		byte e = scanner.nextByte();
		byte k = scanner.nextByte();

		if (e-a>k) System.out.println(":(");
		else System.out.println("Yay!");
	}
}

Measured memory_bytes: 22612
#include <iostream>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <string>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
using namespace std;
typedef long long unsigned int ll;

#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define SZ(x) ((int)(x).size())
#define m0(x) memset(x,0,sizeof(x))
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))

map<ll, ll> primeFactors(ll n)
{
    map<ll, ll> ret;
    while (n % 2 == 0)
    {
        if( ret.find(2) != ret.end() ) {
            ret[2]++;
        }
        else
        {
            ret[2] = 1;
        }
        n = n / 2;
    }
    for (ll i = 3; i <= sqrt(n); i = i+2)
    {
        while (n%i == 0)
        {
            if( ret.find(i) != ret.end() ) {
            ret[i]++;
        }
        else
        {
            ret[i] = 1;
        }
            n = n / i;
        }
    }
    if (n > 2)
        {
            if( ret.find(n) != ret.end() ) {
            ret[n]++;
        }
        else
        {
            ret[n] = 1;
        }
        }
    return ret;
}

void print_map(map<ll, ll> mp){
    for(auto itr = mp.begin(); itr != mp.end(); ++itr) {
        std::cout << "key = " << itr->first           // キーを表示
                        << ", val = " << itr->second << "\n";    // 値を表示
    }
}

// Returns nCr % p
ll nCrModp(ll n, ll r, ll p)
{
    ll C[r+1];
    memset(C, 0, sizeof(C));

    C[0] = 1;

    for (ll i = 1; i <= n; i++)
    {
        for (ll j = min(i, r); j > 0; j--)
            C[j] = (C[j] + C[j-1])%p;
    }
    return C[r];
}

int main()
{
    int N, A, B;
    cin >> N >> A >> B;
    int MAX = max(A, B);
    int MIN = min(A, B);
    if (A+B > N) {
        cout << MIN << " " << A + B - N<< endl;
    } else {
        cout << MIN << " " << 0 << endl;
    }

    return 0;
}



Measured memory_bytes: 256
s = list(input())
t = list(input())
ans = ""

for i in range(len(s)-len(t)+1):
    ok = 1
    memo = "".join(s[0:i])
    #print(memo)
    for j in range(len(t)):
        if s[i+j] != t[j] and s[i+j] != "?":
            #print(t[j])
            ok = 0
            break
        memo += t[j]

    if ok == 1:
        memo += "".join(s[i+j+1:])
        if ans == "":
            ans = memo
        if ans > memo:
            ans = memo


#s.replace(' ', '-')

if ans =="":
    print("UNRESTORABLE")
else:
    print(ans.replace("?","a"))

Measured memory_bytes: 3064