akhauriyash/Code-Regression huggingface dataset:
n = int(input())

ans = 0
if n > 99998:
  ans = 90909
elif n > 9998:
  ans = 909+n-9999
elif n > 998:
  ans = 909
elif n > 98:
  ans = 9+n-99
elif n > 8:
  ans = 9
else:
  ans = n

print(ans)

Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define rep(i,n) for(int i=0;i<n;i++)
#define mod 1000000007 // 10^9+7
#define INF 99999999999 //10^12-1
#define dev 998244353 //tenka1
#define P pair<int,int>
#define F first
#define S second
int n,x,d=0,cnt=0;
int l[150];
signed main(){
    cin>>n>>x;
    rep(i,n)cin>>l[i];
    for(int i=0;d<=x&&i<n;i++){
        d+=l[i];
        cnt++;
    }
    if(d<=x)cout<<n+1<<endl;
    else cout<<cnt<<endl;
    return 0;
}


Measured memory_bytes: 256
#EDP-E
import sys
n, W = map(int, sys.stdin.readline().split())

dp = [dict() for _ in range(n)]
w, v = map(int, sys.stdin.readline().split())
dp[0][v] = w

for i in range(1, n):
    w, v = map(int, sys.stdin.readline().split())
    dp[i][v] = min(w , dp[i].get(v, w))
    for vb, wb in dp[i-1].items():
        dp[i][vb] = min(dp[i].get(vb, wb), wb)
        tmp = min(wb + w, dp[i].get(vb+ v, wb+w))
        if tmp <=W:
            dp[i][v+ vb] = tmp
    #print(dp[i])

print(sorted(dp[-1].items())[-1][0])

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

using namespace std;

typedef long long ll;
typedef long double ld;
#define F first
#define S second

int32_t main(){
	int a, b, c, d, a1 = 0, b1 = 0;
	cin >> a >> b >> c >> d;
	while (a > 0){
		a -= d;
		a1 ++;
	}
	while (c > 0){
		c -= b;
		b1 ++;
	}
//	cout << a1 << ' ' << b1 << endl;
	if (a1 >= b1){
		cout << "Yes";
	}else{
		cout << "No";
	}
}


Measured memory_bytes: 3624
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
int main(void){
    // Your code here!
    int n,x;
    cin>>n>>x;
    int s[n];
    for(int i=0;i<n;i++){
        int a;
        cin>>a;
        s[i]=a;
    }
    int ans=0;
    sort(s,s+n);
    for(int i=0;i<n;i++){
        if(s[i]<=x){
            x-=s[i];
            ans++;
        }
        else break;
    }
    if(ans==n && x>0)ans--;
    cout<<ans<<endl;
}


Measured memory_bytes: 256
def solve():
    S = input()
    q = int(input())
    flg = 0
    li = ["", ""]
    for _ in range(q):
        Q = input().split()
        if Q[0] == "1":
            flg = 1 - flg
        else:
            li[(int(Q[1]) - 1 + flg) % 2] += Q[2]
    if flg:
        S = S[::-1]
    print(li[flg][::-1] + S + li[1 - flg])
solve()


Measured memory_bytes: 4456
n,d = map(int,input().split(" "))
ar = []
count = 0
for i in range(n):
    l = list(map(int,input().split(" ")))
    ar.append(l)
for i in range(n):
    for j in range(i+1,n):
        c = 0
        for k in range(d):
            c += (ar[i][k] - ar[j][k]) ** 2
        for l in range(0,c+1):
            if l ** 2 == c:
                count += 1
print(count)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <math.h>
#include <complex>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <functional>
#include <assert.h>
#define int long
#define ll long long
#define rng(i,a,b) for(int i=int(a);i<int(b);i++)
#define rep(i,b) rng(i,0,b)
#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)
#define per(i,b) gnr(i,0,b)
#define pb push_back
#define mk make_pair
#define all(x) x.begin(),x.end()
#define SZ(x) x.size()
#define fi first
#define se second
const int INF = 1e9;
using namespace std;

template<class t> using vc=vector<t>;
template<class t> using vvc=vc<vc<t>>;

using pi=pair<int,int>;
using vi=vc<int>;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(20);

    double N,M,D; cin >> N >> M >> D;
    if(D==0) cout << (M-1.0)/N << endl;
    else cout << (M-1.0)*2.0*(N-D)/N/N << endl;
}


Measured memory_bytes: 256
////*24-AUG-19*///
//Why do we fall?//
// So we can learn to pick ourself up!//
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define int long long
#define endl "\n"
#define F first
#define S second
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define fr(a,b,c) for(int a=b; a<c; a++)
#define frr(a,b,c) for(int a=b;a>=c;a--)
#define pb push_back
#define pii pair<int,int>
#define R(a) ll a; cin >> a;
#define RA(a, n) ll a[(n) + 1] = {}; fr(i, 1, (n)+1) {cin >> a[i];}
#define RM(a, n, m) int a[n + 1][m + 1] = {}; fr(i, 1, n) {fr(j, 1, m) cin >> a[i][j];}
#define reset(X) memset(X, 0, sizeof(X))
const int inf = 1e18;
const int mod=1e9+7;
unsigned int power(int x, unsigned int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;
    }
    return res;
}
bool isPrime(int n)
{   if (n <= 1)  return false;
    if (n <= 3)  return true;
    if (n%2 == 0 || n%3 == 0) return false;
    for (int i=5; i*i<=n; i=i+6)
        if (n%i == 0 || n%(i+2) == 0)
           return false;
    return true;
    }
//z function -  z[i] is the length of the longest common prefix between s and the suffix of s starting at i
vector<int>z_function(string s) {
    int n = (int) s.length();
    vector<int> z(n);
    for (int i = 1, l = 0, r = 0; i < n; ++i) {
        if (i <= r)
            z[i] = min (r - i + 1, z[i - l]);
        while (i + z[i] < n && s[z[i]] == s[i + z[i]])
            ++z[i];
        if (i + z[i] - 1 > r)
            l = i, r = i + z[i] - 1;
    }
    return z;
}
signed main()
{
    fastio;
    int a,b,h,w;
    cin>>h>>w>>a>>b;
    fr(i,0,h)
    {
        fr(j,0,w)
        {
            if(i<b&&j<a)
            {
                cout<<0;
            }
            if(i<b&&j>=a)
            {
                cout<<1;
            }
            if(i>=b&&j<a)
            {
                cout<<1;
            }
            if(i>=b&&j>=a)
                cout<<0;
        }
        cout<<endl;
    }

}


Measured memory_bytes: 1280
#include <bits/stdc++.h>
#include<utility>
#include<algorithm>

#define pan(i,n) for(int i=0;i<n;i++)
#define pans(i,n,a) for(int i=a;i<n;i++)
#define ll long long int
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define INF 1e9+7
#define PI 3.141592653
#define inf 100007
#define P pair<ll,ll>

using namespace std;

int main(){
    int k;
    cin>>k;
    int no=0;
    queue<ll> q;
    for (int i = 1; i < 10; i++)
    {
        if(no!=k){
            q.push(i);
            no++;
        }
        else break;
    }
    ll ans=no;
    no=0;
    while(no!=k){
        ll x=q.front();
        ans=q.front();
        q.pop();
        if(x%10 != 0) q.push( (10*x)+(x%10)-1 );
        q.push( (10*x)+(x%10) );
        if(x%10 != 9) q.push( (10*x)+(x%10)+1 );
        no++;
    }
    cout<<ans;
}

Measured memory_bytes: 1792
#include <vector>
#include <math.h>
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <iomanip>
#include <deque>

typedef long long ll;
#define rep(i, a, n) for(int i = a; i<n; i++)
#define ALL(a) begin(a), end(a)
using namespace std;
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
vector<int> vec;

int N, H[101010], dp[101010];
int main() {
    int N;
    cin >> N;
    rep(i, 0, N) cin >> H[i];
    rep(i, 0, N) dp[i] = 1000000000;
    dp[0] = 0;
    rep(i, 0, N) {
        chmin(dp[i + 1], dp[i] + abs(H[i] - H[i + 1]));
        chmin(dp[i + 2], dp[i] + abs(H[i] - H[i + 2]));
    }
    cout << dp[N - 1] << endl;
    return 0;
}

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

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef int _loop_int;
#define REP(i,n) for(_loop_int i=0;i<(_loop_int)(n);++i)
#define FOR(i,a,b) for(_loop_int i=(_loop_int)(a);i<(_loop_int)(b);++i)
#define FORR(i,a,b) for(_loop_int i=(_loop_int)(b)-1;i>=(_loop_int)(a);--i)

#define DEBUG(x) cout<<#x<<": "<<x<<endl
#define DEBUG_VEC(v) cout<<#v<<":";REP(i,v.size())cout<<" "<<v[i];cout<<endl
#define ALL(a) (a).begin(),(a).end()

#define CHMIN(a,b) a=min((a),(b))
#define CHMAX(a,b) a=max((a),(b))

// source : 0
// sink : 1
// problems : 2 ~ 2+n-1
// friends : 2+n ~ 2+n+m-1
// pf node : 2+n+m ~ 2+n+m + nm-1


const int INF = 0;
vi eids[125252];
struct edge{
  int u,v,cap,cost,rev;
};
edge edges[452521];
map<pii,int> rev;
int tail;
void addedge(int u,int v,int cap,int cost){
  int xid = tail++;
  int yid = tail++;
  edges[xid] = (edge){u,v,cap,cost,yid};
  edges[yid] = (edge){v,u,0,-cost,xid};
  eids[u].push_back(xid);
  eids[v].push_back(yid);
  rev[pii(u,v)] = xid;
  rev[pii(v,u)] = yid;
}

int n,m,k;

int main(){
  scanf("%d%d%d",&n,&m,&k);
  REP(i,n){
    int a;
    scanf("%d",&a);
    addedge(0, 2+i, 1, INF);
    addedge(2+i, 1, 1, INF-a);
  }
  REP(j,m){
    REP(i,n){
      int b;
      scanf("%d",&b);
      int id = 2+n+m+i*m+j;
      addedge(2+i, id, 1, INF-b);
      addedge(id, 2+n+j, 1, INF);
    }
  }
  REP(j,m){
    int t;
    scanf("%d",&t);
    addedge(2+n+j, 2+n+m+n*m, t, INF);
  }
  addedge(2+n+m+n*m, 1, n-k, INF);

  int flow = n;
  int ans = 0;
  while(flow--){
    // dijkstra
  vi dist;
  vi bef;
  dist.assign(tail,1e9);
  bef.assign(tail,-1);
  priority_queue<pll> Q;
  Q.push(pll(-0, 0));
  dist[0] = 0;
  while(!Q.empty()){
    pll P = Q.top(); Q.pop();
    int p = P.second;
    // DEBUG(p);
    ll d = dist[p];
    for(int id : eids[p]){
      edge e = edges[id];
    // DEBUG(p);
      if(e.cap<=0)continue;
      int to = e.v;
      ll cost = e.cost;
    // DEBUG(p);
      ll nd = d + cost;
      if(dist[to] <= nd)continue;
    // DEBUG(p);
      dist[to] = nd;
      bef[to] = p;
      Q.push(pll(-nd, to));
    }
  }

  // gyaku
  int pos = 1;
  while(pos != 0){
    int b = bef[pos];
    int eid = rev[pii(b,pos)];
    edge &e = edges[eid];
    edge &r = edges[e.rev];
    e.cap--;
    r.cap++;
    ans += INF-e.cost;
    pos = b;
  }

  }
  printf("%d\n",ans);
  return 0;
}

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

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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define inf 1e18
int main()
{
      ll n,temp=n;
      cin>>n;
      ll ans=360;
    for (ll i = 2; i <= n+1; i++)  
    {  
         if(n<2) break;
        while (n % i == 0)  
        {  
            if(ans%i==0)
			{
				ans=ans/i;
			 } 
            n = n/i;  
            if(n<2) break;
        }  
    }  
	  cout<<ans<<endl;
}


Measured memory_bytes: 3628
def main():
    n, m, x = map(int, input().split())
    num_list = list(map(int, input().split()))

    low_count = 0
    high_count = 0
    for i in num_list:
        if i < x:
            low_count += 1
        elif i > x:
            high_count += 1

    print(min(low_count, high_count))

if __name__ == '__main__':
    main()

Measured memory_bytes: 38384
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    String S = scan.next();
    scan.close();

    if(S.charAt(2) ==  S.charAt(3) && S.charAt(4) == S.charAt(5)) {
      System.out.println("Yes");
    }
    else {
      System.out.println("No");
    }
  }
}

Measured memory_bytes: 25300
import java.io.IOException;

import java.util.Scanner;

public class Main {
    public static void main (String[] args) throws IOException {

        Scanner scan = new Scanner(System.in);
        int[] DiceBox = new int[6];
        for(int i = 0; i < 6; i++){
            DiceBox[i] = scan.nextInt();
        }

        Dice dice = new Dice(DiceBox[0], DiceBox[1], DiceBox[2], DiceBox[3], DiceBox[4], DiceBox[5]);
        String line = scan.next();
        int i = 0;
        while(true){

            if(i == line.length()){
                break;
            }
            switch(line.charAt(i)){
                case 'N':
                    dice.TurnN();
                    break;
                case 'E':
                    dice.TurnE();
                    break;
                case 'S':
                    dice.TurnS();
                    break;
                case 'W':
                    dice.TurnW();
                    break;
            }

            i++;

        }
        
        System.out.println(dice.Top);


    }
}

class Dice {
    int Top;
    int Bottom;
    int N;
    int S;
    int W;
    int E;

    Dice(int a, int b, int c, int d, int e, int f){
        Top = a;
        S = b;
        E = c;
        W = d;
        N = e;
        Bottom = f;
    }

    public void TurnN() {
        int tmp = Top;
        Top = S;
        S = Bottom;
        Bottom = N;
        N = tmp;
    }

    public void TurnS() {
        int tmp = Bottom;
        Bottom = S;
        S = Top;
        Top = N;
        N = tmp;
    }

    public void TurnW() {
        int tmp = Bottom;
        Bottom = W;
        W = Top;
        Top = E;
        E = tmp;
    }

    public void TurnE() {
        int tmp = Bottom;
        Bottom = E;
        E = Top;
        Top = W;
        W = tmp;
    }
}



Measured memory_bytes: 26284
use std::io::*;
use std::str::FromStr;

pub fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let stdin = stdin.lock();
    let token: String = stdin
        .bytes()
        .map(|c| c.expect("failed to read char") as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect();
    token.parse().ok().expect("failed to parse token")
}

pub fn read_n<T: FromStr>(n: usize) -> Vec<T> {
    read_n_logic::<T>(n, vec![])
}

pub fn read_n_logic<T: FromStr>(n: usize, mut a: Vec<T>) -> Vec<T> {
    match n {
        0 => a,
        _ => {
            a.push(read::<T>());
            read_n_logic(n - 1, a)
        }
    }
}
use std::cmp::{max, min};

fn main() {
    let n: usize = read();
    let k: i64 = read();
    let mut a: Vec<usize> = read_n(n);
    let mut f: Vec<usize> = read_n(n);
    a.sort();
    f.sort();
    f.reverse();

    let mut maxv: i64 = 1_000_000_000_000;
    let mut minv: i64 = -1;
    while minv + 1 < maxv {
        let mid = (maxv + minv) / 2;
        // println!("mid{}, maxv: {}, minv: {}", mid, maxv, minv);
        let mut s: i64 = 0;
        for i in 0..n {
            s += max((a[i] as i64 - (mid / f[i] as i64) as i64), 0);
        }
        if s <= k {
            maxv = mid;
        } else {
            minv = mid;
        }
    }

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


Measured memory_bytes: 29180
#include<cstdio>
#include<algorithm>

using namespace std;

int main(){
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    int x[n];
    int ans = 0;
    for(int i = 0; i < n; i++){
        scanf("%d", &x[i]);
        ans += min(2 * x[i], 2 * (k - x[i]));
    }
    printf("%d\n", ans);
}

Measured memory_bytes: 760
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 500010;
int n,q,d[N],sta,mn[N],cur[N],tmp;
signed main() {
  scanf("%lld%lld",&n,&sta);
  for (int i = 1 ; i <= n ; ++ i)
    scanf("%lld",&d[i]);
  cur[0] = sta;
  for (int i = 1 ; i <= n ; ++ i)
    cur[i] = min(cur[i-1],abs(cur[i-1] - d[i]));
  mn[n] = 1;
  for (int i = n - 1 ; i >= 1 ; -- i) {
    if (d[i+1] / 2 >= mn[i+1]) mn[i] = mn[i+1];
    else mn[i] = mn[i+1] + d[i+1];
  }
  scanf("%lld",&q);
  for (int i = 1 ; i <= q ; ++ i) {
    scanf("%lld",&tmp);
    if (cur[tmp-1] >= mn[tmp]) puts("YES");
    else puts("NO");
  }
  return 0;
}

Measured memory_bytes: 13696
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;
using System.Text;
using System.IO;
using static System.Math;
using System.Numerics;

namespace AtCoder
{
    class Program
    {
        static public long[] Sarray() { return ReadLine().Split().Select(long.Parse).ToArray(); }
        static public List<long> Slist() { return ReadLine().Split().Select(long.Parse).ToList(); }
        static long Mod = (long)1e9 + 7;
        static void Main(string[] args)
        {
            SetOut(new StreamWriter(OpenStandardOutput()) { AutoFlush = false });
            Solve();
            Out.Flush();
            Read();
        }
        static void Solve()
        {
            var NK = Sarray();
            var N = NK[0];
            var K = NK[1];
            var TDs = new (long t, long d)[N];
            for (var i = 0; i < N; ++i)
            {
                var td = Sarray();
                TDs[i] = (td[0], td[1]);
            }
            var gTDs = TDs.GroupBy(td => td.t);

            var selOrders = new List<(long t, long d)>();
            var remOrders = new List<(long t, long d)>();
            foreach (var td in gTDs)
            {
                var t = td.OrderBy(e => e.d).ToList();
                selOrders.Add(t.Last());
                t.RemoveAt(t.Count - 1);
                remOrders.AddRange(t);
                
            }
            //選択したもの。小さい方から消していくので降順(計算量のため最後から使う)
            selOrders.Sort((l, r) => (int)(r.d - l.d));
            while (K < selOrders.Count)
                selOrders.RemoveAt(selOrders.Count - 1);
            var tNums = (long)selOrders.Count;
            var sum = selOrders.Sum(s=>s.d) + tNums * tNums;
            //未使用のもの。大きい方から使っていくので昇順(計算量のため以下略)
            remOrders.Sort((l, r) => (int)(l.d - r.d));
            for (var i = 0; i < K - selOrders.Count; ++i)
            {
                sum += remOrders.Last().d;
                remOrders.RemoveAt(remOrders.Count - 1);
            }
            var max = sum;
            while (remOrders.Any())//入れ替え
            {
                var ro = remOrders.Last();
                remOrders.RemoveAt(remOrders.Count - 1);
                var o = selOrders.Last();
                if (o.d < ro.d)
                {
                    var diff = ro.d + (tNums - 1) * (tNums - 1) - (o.d + tNums * tNums);
                    sum += diff;
                    max = Max(max, sum);
                    selOrders.RemoveAt(selOrders.Count - 1);
                    --tNums;
                }
            }
            WriteLine(max);
        }
    }
}

Measured memory_bytes: 63888
s = gets.chomp.chars
a = Array.new(s.size + 1, 0)

cnt = 0
s.chunk{|c| c }.each do |c, items|
  l = items.length
  if c == "<"
    a[cnt] = 0
    1.step(l) do |i|
      a[cnt + i] = a[cnt] + i
    end
  else
    a[cnt + l] = 0
    a[cnt] = [l, a[cnt]].max

    1.step(l) do |i|
      a[cnt + l - i] = [a[cnt + l] + i, a[cnt + l - i]].max
    end
  end
  cnt += l
end

#p s.chunk{|c| c }.map{|c, items| [c, items.length] }
#p a
puts a.inject(:+)
# [0, 3, 2, 1, 0, 1, 2, 0, 1, 2, 3, 4, 5, 2, 1, 0, 1]

Measured memory_bytes: 50440
open Printf
open Scanf

let id x = x

let solve n k =
  let aa = Array.init n @@ fun _ -> scanf "%d " id in
  for i = k to n - 1 do
    printf "%s\n" @@ if aa.(i-k) < aa.(i) then "Yes" else "No"
  done

let () =
  scanf "%d %d " solve


Measured memory_bytes: 7428
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define rrep2(ri,x,n) for(int ri = (int)(n-1); ri >= (int)(x); ri--)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

void dfs(const vector<vector<int>> &tree, vector<ll> &q, int now, int bf){
  if(now != 0) q.at(now) += q.at(bf);
  for(auto nx : tree.at(now)){
    if(nx == bf) continue;
    dfs(tree, q, nx, now);
  }
}

int main(){
  int n, qe;
  cin >> n >> qe;
  vector<vector<int>> tree(n, vector<int>());
  rep(i, n-1){
    int a, b;
    cin >> a >> b;
    a--; b--;
    tree.at(a).push_back(b);
    tree.at(b).push_back(a);
  }
  vector<ll> q(n, 0);
  rep(i, qe){
    int qin, x;
    cin >> qin >> x;
    qin--;
    q.at(qin) += x;
  }
  dfs(tree, q, 0, -1);
  rep(i, n){
    if(i != 0) cout << " ";
    cout << q.at(i);
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 28316
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
int main(){
  int k,x;
  cin>>k>>x;
  for(int i=max(-1000000,x-k+1);i<=min(1000000,x+k-1);i++){
    if(i!=max(-1000000,x-k+1))cout<<" ";
    cout<<i;
  }
  cout<<endl;
  return 0;
}

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

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

Measured memory_bytes: 640
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		//電車(通常切符)
		int A = scanner.nextInt();
		//電車(乗り放題)
		int B = scanner.nextInt();
		//バス(通常切符)
		int C = scanner.nextInt();
		//バス(乗り放題)
		int D = scanner.nextInt();

		//運賃合計最小値
		int train = A < B ? A : B;
		int bus = C < D ? C : D;
		int fare = train + bus;
		System.out.println(fare);
	}
}


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

using namespace std;

int n;
string s;

int main(){
    cin >> n >> s;
    int ans = 0;
    for (int i = 0; i < n - 2; i++) {
        if (s[i] == 'A' && s[i + 1] == 'B' && s[i + 2] == 'C') {
            ans++;
        }
    }
    
    cout << ans;
    return 0;
}

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

int main() {
    int i = 0;
    int j = 0;
    int n;
    scanf("%d", &n);
    int* c;
    int* s;
    int* f;
    int ans = 0;
    c = malloc(sizeof(int) * (n - 1));
    s = malloc(sizeof(int) * (n - 1));
    f = malloc(sizeof(int) * (n - 1));
    for (i = 0; i < n - 1; i++)
        scanf("%d %d %d", &c[i], &s[i], &f[i]);

    for (i = 0; i < n - 1; i++) {
        ans = c[i] + s[i];
        j = i + 1;
        while (j <= n - 2) {
            if (ans - s[j] >= 0 && (ans - s[j]) % f[j] == 0) {
                ans += c[j];
                j += 1;
            }
            else
                ans += 1;
            }
        printf("%d\n", ans);
        }
    printf("0\n");

    return 0;
}


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

using namespace std;

const int maxn = 1e6 + 10;
int a[maxn], dp[maxn], n, k;

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> k;

    for (int i = 0; i < n; i++)
        cin >> a[i];
    memset(dp, 63, sizeof dp);
    dp[0] = 0;
    for (int i = 0; i < n; i++)
        for (int j = 1; j <= k; j++)
            dp[i + j] = min(dp[i + j], dp[i] + abs(a[i + j] - a[i]));

    cout << dp[n - 1];

    return 0;
}

Measured memory_bytes: 6400
#include<iostream>
#include<vector>
#include <algorithm>
#include <string>
#include <utility>
#include <set>
#include <map>
#include<cmath>

//using lli = long long int;
int inf = 1000000007;
using namespace std;
#define sort(X) sort(X.begin(),X.end())

int N, K;
string S;

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

	for (int i = 0; i < N; i++) {
		if (i + 1 == K) {
			if (S[i] == 'A')cout << 'a';
			else if (S[i] == 'B')cout << 'b';
			else if (S[i] == 'C')cout << 'c';
		}
		else cout << S[i];
	}
	cout << endl;
	return 0;
}

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

int main() {
	int n;
	cin>>n;
	int arr[n];
	for (int i=0; i<n; i++){
		cin >> arr[i];
	}
	sort(arr, arr+n);
	int odd = 0;
	int i = 0;
	while (i<n){
		int x = arr[i];
		int cnt = 0;
		int j = i;
		while (j<n and x==arr[j]){//2266
			cnt++;
			j++;
		}
		//cout << cnt << " ";
		if (cnt%2==1) odd++;
		i=j;
		//cout << j << endl;
	}

	cout << odd << endl;
}
//loop aroun 500000


Measured memory_bytes: 3580
// dile a la jardinera que traigo flores

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define sz(x) int(x.size())
#define all(v) (v).begin(),(v).end()
#define trace(x) cout << #x << " = " << x << endl
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
#define FER(i,a,b) for(int i = int(a); i < int(b); ++i)
#define IFR(i,a,b) for(int i = int(a); i >= int(b); i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;


int main(){	
	fastio;
	int A,B,C;cin>>A>>B>>C;
	cout<<min(B/A,C)<<endl;
	return 0;
}


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

int main()
{
    int n, lastdig;
    scanf("%d", &n);
    lastdig=n%10;

    if(lastdig==2 || lastdig==4 || lastdig==5 || lastdig==7 || lastdig==9)
    {
        printf("hon");
    }
    else    if(lastdig==0 || lastdig==1 || lastdig==6 || lastdig==8)
            {
                printf("pon");
            }
            else    if(lastdig==3)
                    {
                        printf("bon");
                    }
}


Measured memory_bytes: 3752
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        
        String[] strNum = br.readLine().split(" ");
        String[] strPrice = br.readLine().split(" ");
        int n = Integer.parseInt(strNum[0]);
        int k = Integer.parseInt(strNum[1]);
        Integer[] price = new Integer[n];
        
        for(int i = 0; i < price.length; i++){
            price[i] = Integer.valueOf(strPrice[i]);
        }
        
        Arrays.sort(price);
        
        int sum = 0;
        
        for(int i = 0; i < k; i++){
            sum += price[i];
        }
        
        out.println(sum);
        
        out.flush();
        out.close();
        
    }
}

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

using namespace std;

#define int long long
const double PI = 3.14159265358979323846;
typedef vector<int> vint;
typedef pair<int, int> pint;
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
// cout << fixed << setprecision(20);

#include <vector>

// FenwickTree (0 - indexed)
// T: 可換モノイド
template<class T>
class FenwickTree {
    const int n;
    std::vector<T> data;
public:
    // 要素数を指定し、全要素0で初期化
    FenwickTree(int n) : n(n), data(n + 1) {}

    // 元となるstd::vectorを用意して初期化
    FenwickTree(std::vector<T> source) : n(source.size()), data(n + 1) {
        std::copy(source.begin(), source.end(), data.begin() + 1);
        for (int i = 1; i < n; i++) data[i + (i & -i)] += data[i];
    }

    // [0, i]の区間和を取得
    T getSum(int i) const {
        T ret = 0;
        for (i++; i > 0; i -= i & -i)ret += data[i];
        return ret;
    }

    // 要素iにxを加算
    void add(int i, T x) { for (i++; i <= n; i += i & -i)data[i] += x; }

    // 以下、T: 可換群

    // [l, r]の区間和を取得
    T getSum(int l, int r) const {
        return getSum(r) - getSum(l - 1);
    }

    // [0, i]の区間和がx以上となる最小のiを取得 (区間和の単調性が必要)
    int getLowerBound(T x) const {
        if (x <= 0) return 0;
        int i = 0, r = 1;
        while (r < n) r <<= 1;
        for (int k = r; k > 0; k >>= 1) {
            if (i + k <= n && data[i + k] < x) {
                x -= data[i + k];
                i += k;
            }
        }
        return i;
    }
};

int N, M;
int A[110000], B[110000];
pint BA[110000];

signed main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> A[i] >> B[i];
        BA[i] = pint(B[i], A[i]);
    }
    sort(BA, BA + N);
    reverse(BA, BA + N);
    FenwickTree<int> ft(M + 1);
    int ans = 0;
    for (int i = 0; i < N; i++) {
        int lb = BA[i].second - 1, ub = M + 1;
        while (ub - lb > 1) {
            int mid = (lb + ub) / 2;
            if (ft.getSum(BA[i].second, mid) < mid - (BA[i].second - 1)) {
                ub = mid;
            } else lb = mid;
        }
        if (ub != M + 1)ft.add(ub, 1), ans += BA[i].first;
    }
    cout<<ans<<endl;
}

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

using namespace std;

int n;
queue<int> q[1001];
bool vis[1001];

int f() {
    memset(vis, 0, sizeof vis);
    bool flag = 0;
    for (int i = 1; i <= n; ++i) {
        if(vis[i]) continue;
        if(q[i].empty()) continue;
        int x = q[i].front();
        if(q[x].empty()) continue;
        if(q[x].front() == i and !vis[i] and !vis[x]) {
            flag = 1;
            vis[x] = vis[i] = 1;
            q[x].pop();
            q[i].pop();
        }
    }
    if(!flag) return -1;
    for (int i = 1; i <= n; ++i)
        if(q[i].size()) return 1;
        
    return 0;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < n - 1; ++j) {
            int x;
            scanf("%d", &x);
            q[i].push(x);
        }
    }

    int ans = 0;
    int ini = 1;
    int lim = 1000010;
    while(ini == 1 and lim--) ini = f(), ans++;
    if(ini == -1) puts("-1");
    else printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 6784
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n=0,k=0,sum=0;
  vector<int> A;
  cin>>n>>k;
  for(int i=0;i<n;i++){
  cin>>sum;
    A.push_back(sum);
  }
  sum=0;
  sort(A.begin(),A.end());
  for(int i=0;i<k;i++){
  sum+=A[i];
  }
  cout<<sum<<"\n";
  return 0;
}

Measured memory_bytes: 3644
# -*- coding: utf-8

n = int(input())
bs = []
bh = []
bc = []
bd = []

for i in range(n):    
    a = input().split()
    if a[0] == 'S':
        bs.append(int(a[1]))  
    if a[0] == 'H':
        bh.append(int(a[1]))  
    if a[0] == 'C':
        bc.append(int(a[1]))  
    if a[0] == 'D':
        bd.append(int(a[1]))

for ks in range(1,14):
    if ks not in bs:
        print('S '+str(ks))

for kh in range(1,14):
    if kh not in bh:
        print('H '+str(kh))
        
for kc in range(1,14):
    if kc not in bc:
        print('C '+str(kc))
        
for kd in range(1,14):
    if kd not in bd:
        print('D '+str(kd))


Measured memory_bytes: 5612
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())
class WarshallFloyd(object):
    def __init__(self):
        self.max_v = 10
        self.min_dist = [readInts() for _ in range(10)]
    def compute(self):
        for k,i,j in product(range(self.max_v), repeat = 3):
            # i -> j と i -> k -> j のうち、長くない方の距離
            self.min_dist[i][j] = min(self.min_dist[i][j], self.min_dist[i][k] + self.min_dist[k][j])
    def solve(self, n):
        if n == 1:
            return 0
        else:
            return self.min_dist[n][1]
h,w = readInts()
w = WarshallFloyd()
w.compute()
ans = 0
A = [readInts() for _ in range(h)]
for a in A:
    for i in a:
        if i == -1:
            continue
        ans += w.solve(i)
print(ans)


Measured memory_bytes: 10584
#include <cstdio>
#include <algorithm>
#include <utility>

using namespace std;

long long get_gcd(long long m, long long n) {
    /* Euclidean Algorithm */
    while (n)
        swap(m%=n, n);

    return m;
}

int main() {
    while (true) {
        long long a, b;
        if (scanf("%lld %lld", &a, &b) == EOF)
            break;

        long long gcd=get_gcd(a, b);
        printf("%lld %lld\n", gcd, a*b/gcd);
    }

    return 0;
}

Measured memory_bytes: 2724
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<math.h>
#include<string>
#include<string.h>
#include<stack>
#include<queue>
#include<vector>
#include<utility>
#include<set>
#include<map>
#include<stdlib.h>
#include<iomanip>

using namespace std;

#define ll long long
#define ld long double
#define EPS 0.0000000001
#define INF 1e9
#define MOD 1000000007
#define rep(i,n) for(i=0;i<n;i++)
#define loop(i,a,n) for(i=a;i<n;i++)
#define all(in) in.begin(),in.end()
#define shosu(x) fixed<<setprecision(x)

typedef vector<int> vi;
typedef pair<int,int> pii;

int main(void) {
  int i,j;
  int t,n;
  int dx[6]={0,1,1,0,-1,-1};
  int dy[6]={1,1,0,-1,-1,0};
  while(1){
    cin>>t>>n;
    if(t==0 && n==0)break;
    vector<vi> v(300,vi(300,INF));
    rep(i,n){
      int x,y;
      cin>>x>>y;
      v[x+100][y+100]=-1;
    }
    int sx,sy;
    cin>>sx>>sy;
    queue<pii> q;
    q.push(pii(sx+100,sy+100));
    v[sx+100][sy+100]=0;
    while(q.size()){
      int x=q.front().first;
      int y=q.front().second;
      q.pop();
      if(v[x][y]>=t)continue;
      rep(i,6){
	int nx=x+dx[i];
	int ny=y+dy[i];
	if(v[nx][ny]>=0 && v[nx][ny]>v[x][y]+1){
	  v[nx][ny]=v[x][y]+1;
	  q.push(pii(nx,ny));
	}
      }
    }

    int ans=0;
    rep(i,300)rep(j,300)
      if(v[i][j]>=0 && v[i][j]<INF)ans++;
    cout<<ans<<endl;
  }
}

Measured memory_bytes: 3192
N = int(input())
A = [int(x) for x in input().split()]

pair = []
unpair = set()
for a in A:
    if a in unpair:
        pair.append(a)
        unpair.remove(a)
    else:
        unpair.add(a)

pair.sort()
pair.reverse()
if len(pair) <= 1:
    ans = 0
else:
    ans = pair[0] * pair[1]
print(ans)

Measured memory_bytes: 20076
s = input()
st1=[]
st2=[]
st3=[]
total=0
for i in range(len(s)):
	c=s[i]
	if c=='\\':
		st1.append(i)
	elif c=='/':
		if len(st1) > 0:
			j = st1.pop()
			a = i - j
			total+=a
			tmp=0
			while len(st2)>0 and st2[-1]>j:
				st2.pop()
				tmp+=st3.pop()
			st3.append(a+tmp)
			st2.append(j)
			
print(total)
n = len(st3)
print(n,end='')
for i in range(n):
	print(' '+str(st3[i]),end='')
print()



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


int main(void) {
  int x;
  cin >> x;

  int ans = 0;
  int sum = 0;
  while (sum < x) {
    ans++;
    sum += ans;
  }

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

Measured memory_bytes: 3620
#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;
#define ll long long
#define pb push_back

int main() {
  ll N, M;
  cin >> N >> M;
  // 問題回答済みかどうかの配列
  vector<ll> p(N, 0);
  // wrongの配列
  vector<ll> wa(N, 0);

  ll pn;
  string s;
  for(int i = 0; i < M; i++){
    cin >> pn >> s;
    // ACの場合
    if (s == "AC"){
      p.at(pn-1) = 1;
    } else { // WAの場合
      if (p.at(pn-1) == 0) { // 不正解の場合
        wa.at(pn-1)++;
      }
    }
  }

  ll rp = 0, rw=0;
  // ACとWAの数を数える
  for (int i = 0; i < N; i++) {
    rp += p.at(i);
    if (p.at(i) == 1) {
      rw += wa.at(i);
    }
  }
  
  cout << rp << " " << rw << endl;
}




Measured memory_bytes: 1792
#include"bits/stdc++.h"

using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;
	vector<int>A(N);

	for (int  i = 0; i < N; i++)
	{
		cin >> A[i];
	}

	sort(A.begin(), A.end());
	int ans = 0;
	int cnt = 0;
	while(cnt<N){
		int tmp = A[cnt], f = 0;
		while (cnt < N&&A[cnt] == tmp) {
			f++;
			cnt++;
		}
		ans += f % 2;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 640
#include<stdio.h>
#include<stdlib.h>
#define INF (1e9+1)
 
typedef struct state{
  int pos,cost;
} state;
 
state A[2000001];
int N=0;
  
int parent(int i){return i/2;}
int left(int i){return i*2;}
int right(int i){return i*2+1;}
  
void exchange(state* a,state* b){
  state tmp=*a;
  *a=*b;
  *b=tmp;
}
  
void minHeapify(int i){
  int l=left(i);
  int r=right(i);
  int small;
   
  if( l<=N && A[l].cost<A[i].cost )small=l;
  else small=i;
   
  if( r<=N && A[r].cost<A[small].cost)small=r;
   
  if(small!=i){
    exchange(&A[i],&A[small]);
    minHeapify(small);
  }
   
}
  
state heapExtractMin(){
  if(N<1)return (state){0,0};
  state min=A[1];
  A[1]=A[N];
  N--;
  minHeapify(1);
  return min;
}
 
  
void heapIncreaseKey(int i,state key){
  if(key.cost>A[i].cost)return;
  
  A[i]=key;
  while(i>1&&A[parent(i)].cost>A[i].cost){
    exchange(&A[i],&A[parent(i)]);
    i=parent(i);
  }
}
  
void minHeapInsert(state key){
  N++;
  A[N]=(state){INF,INF};
  heapIncreaseKey(N,key);
}
 
 
typedef struct edge{
  int to,cost;
} edge;
 
edge* G[10000];
int size[10000];
int n;
int d[10000];
edge e;
state s;
int main(){
  int i,j,a,b;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d %d",&a,&b);
    G[a] = malloc( sizeof( edge ) *b );
    size[a]=b;
    for(j=0;j<b;j++){
      scanf("%d %d",&G[a][j].to,&G[a][j].cost);
    }
    d[i]=INF;
  }
  d[0]=0;
  minHeapInsert( (state){0,0} );
  while(N!=0){
    s = heapExtractMin();
    if(s.cost>d[s.pos])continue;
    for(i=0;i<size[s.pos];i++){
      e=G[s.pos][i];
      if(d[e.to]<=d[s.pos]+e.cost)continue;
      d[e.to]=d[s.pos]+e.cost;
      minHeapInsert((state){e.to,d[e.to]});
    }
  }
  for(i=0;i<n;i++)
    printf("%d %d\n",i,d[i]);
   
  return 0;
}

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

int main() {
    int n;
    cin >> n;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    sort(a, a + n);
    int sum = a[n - 1] / 2;
    for (int i = 0; i < n - 1; i++) {
        sum += a[i];
    }
    cout << sum << endl;
    return 0;
}

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

using namespace std;

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

#define fi first
#define se second

li a, b;

int main () {
    cin >> a >> b;
    if (a<b) cout << 0;
    else cout << 10;
}


Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
using namespace std;

int main(){
    string s; cin >> s;
    if(s[0] != s[1] && s[0] != s[2] && s[1] != s[2]) cout << "Yes";
    else cout << "No";
    cout << endl;
    return 0;
}


Measured memory_bytes: 256
// [besto] implementatiano
#include <bits/stdc++.h>

using namespace std;

#define intt long long
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

intt n;

int main() {

	FAST;

	cin >> n;
	string ans = "";
	while (n) {
		n --;
		ans += char('a' + n % 26);
		n /= 26;
	}
	reverse(ans.begin(), ans.end());
	cout << ans << '\n';
	return 0;
}

Measured memory_bytes: 3608
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>

int main(void) {
  int N, K;
  
  std::cin >> N >> K;
  std::vector<int> l(N);
  for (int i = 0; i < N; ++i) {
    std::cin >> l[i];
  }
  
  std::sort(l.begin(), l.end(), std::greater<int>());
  
  auto sum = std::accumulate(l.begin(), l.begin()+K, 0);

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

Measured memory_bytes: 256
// Do you knOW what it feels like?

		// To be TorTured by your own MinD?
	
	// I don't wanna feel the PAIN.

// I BeG you to KILL me, pleASE...

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

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("Os") 

#define F first
#define S second
#define pb push_back
#define SZ(x) (ll)(x.size())
#define all(x) x.begin(),x.end()
#define mp make_pair

typedef long long ll;
typedef pair<ll,ll> pll;
typedef long double ld;

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll maxn=1e5+10, lg=23, mod=1e9+7, inf=1e18;

ll n,a[2*maxn];
bool check(ll x){
	bool beg=(a[n]>=x);
	for(int i=1;i<=n-1;i++){
		if(i%2 && ((a[n-i]>=x)==beg || (a[n+i]>=x)==beg))       return beg;
		if((i+1)%2 && ((a[n-i]>=x)==!beg || (a[n+i]>=x)==!beg)) return !beg;
	}
	return (n%2 ? beg:!beg);
}

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

	cin>>n;
	for(int i=1;i<=2*n-1;i++) cin>>a[i];
	ll l=1,r=2*n-1;
	while(r-l>1){
		ll mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else           r=mid;
	}
	cout<<l<<endl;

	return 0;
}








 






Measured memory_bytes: 1920
import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        final int H = Integer.parseInt(sc.next());
        final int W = Integer.parseInt(sc.next());
        String[] ss = new String[H];
        for (int i = 0; i < H; i++) {
            ss[i] = sc.next();
        }
        
        for (int i = 0; i < H; i++) {
                out.println(ss[i]);
                out.println(ss[i]);
        }
        
        out.flush();
    }
}

Measured memory_bytes: 22904
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
typedef long long int lli;

int main()
{
    int K, A, B;
    cin >> K;
    cin >> A >> B;
    int temp = (A / K);
    if(((temp * K) == A) || (((temp + 1) * K) <= B))
    {
        cout << "OK" << endl;
    }
    else
    {
        cout << "NG" << endl;
    }
    return 0;
}

Measured memory_bytes: 3596
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;
#define fst first
#define snd second

/* clang-format off */
template <class T, size_t D> struct _vec { using type = vector<typename _vec<T, D - 1>::type>; };
template <class T> struct _vec<T, 0> { using type = T; };
template <class T, size_t D> using vec = typename _vec<T, D>::type;
template <class T> vector<T> make_v(size_t size, const T& init) { return vector<T>(size, init); }
template <class... Ts> auto make_v(size_t size, Ts... rest) { return vector<decltype(make_v(rest...))>(size, make_v(rest...)); }
/* clang-format on */

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

struct UnionFind {
  vector<int> parent;  // parent[root] is the negative of the size.
  UnionFind(int n)
      : parent(n, -1){};
  bool unite(int u, int v) {
    u = root(u);
    v = root(v);
    if (u == v) return false;
    if (parent[u] > parent[v]) swap(u, v);
    parent[u] += parent[v];
    parent[v] = u;
    return true;
  }
  bool find(int u, int v) {
    return root(u) == root(v);
  }
  int root(int u) {
    return parent[u] < 0 ? u : parent[u] = root(parent[u]);
  }
  int size(int u) {
    return -parent[root(u)];
  }
};

using P = pair<ll, int>;

struct Edge {
  int x, y;
  ll w;

  bool operator<(const Edge& rhs) const {
    return w < rhs.w;
  }
};

void push(vector<P>& ps, P x) {
  bool found = false;
  for (auto& y : ps) {
    if (y.snd == x.snd) {
      y = min(y, x);
      found = true;
    }
  }
  if (!found) ps.push_back(x);
  sort(ps.begin(), ps.end());
  if (ps.size() > 2)
    ps.resize(2);
}

const ll INF = 1ll << 60;

int main() {
  int N;
  ll D;
  while (cin >> N >> D) {
    vector<ll> A(N);
    for (int i = 0; i < N; i++) cin >> A[i];
    UnionFind uf(N);
    int components = N;
    ll res = 0;
    while (components >= 2) {
      vector<Edge> edges(N, Edge{-1, -1, INF});
      vector<P> L, R;
      for (int i = 0; i < N; i++) {
        int r = uf.root(i);
        for (auto p : L) {
          if (p.snd != r)
            chmin(edges[r], Edge{r, p.snd, p.fst + i * D + A[i]});
        }
        push(L, P(-i * D + A[i], r));
      }
      for (int i = N - 1; i >= 0; i--) {
        int r = uf.root(i);
        for (auto p : R) {
          if (p.snd != r)
            chmin(edges[r], Edge{r, p.snd, p.fst - i * D + A[i]});
        }
        push(R, P(+i * D + A[i], r));
      }
      for (auto& e : edges) {
        if (e.w >= INF)
          continue;
        if (uf.unite(e.x, e.y)) {
          res += e.w;
          --components;
        }
      }
    }
    cout << res << endl;
  }
  return 0;
}


Measured memory_bytes: 5836
#include <iostream>
using namespace std;
int main()
{
	int N,a,q;
	cin >> N;
	int x[N],y[N],b[N],p[N];
	for(int i=0;i<N;i++){	
		cin >> x[i] >> y[i] >> b[i] >> p[i];
		if(b[i] >=5 && p[i] >=2){
			cout << (x[i]*b[i]+y[i]*p[i])*0.8 << endl;
		}
		else if(b[i] < 5 && p[i] >=2){
			a = x[i]*b[i]+y[i]*p[i];
			q = (x[i]*5+y[i]*p[i])*0.8;
			if(a > q)
				a = q;
			cout << a << endl;
		}
		else if(b[i] >= 5 && p[i] < 2){
			a = x[i]*b[i]+y[i]*p[i];
			q = (x[i]*b[i]+y[i]*2)*0.8;
			if(a > q)
				a = q;
			cout << a << endl;
		}
		else{
			a = x[i]*b[i]+y[i]*p[i];
			q = (x[i]*5+y[i]*2)*0.8;
			if(a > q)
				a = q;
			cout << a << endl;
		}
	}
	return 0;
}
					

Measured memory_bytes: 1244
#include<iostream>
#include<vector>
#include<string>

using namespace std;

int W, H;
char g[100][100];
bool s[100][100];

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

void dfs(int x, int y, char c)
{
    s[x][y] = true;

    for(int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx >=0 && nx < H && ny>=0 && ny < W && g[nx][ny] == c && !s[nx][ny])
        {
            dfs(nx, ny, c);
        }
    }
    
}

int main()
{
    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)
            {
                cin>> g[i][j];
                s[i][j] = false;
            }
        
        int ans = 0;

        for(int i = 0; i < H; ++i)
            for(int j = 0; j < W; ++j)
            {
                if(!s[i][j])
                {
                    ans++;
                    dfs(i, j, g[i][j]);
                }
                    
            }
        cout<<ans <<endl;
    }

}


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

#define rep(i,n) for(int i=0;i<(int)n;i++)
#define all(c) (c).begin(),(c).end()
#define mp make_pair
#define pb push_back
#define each(i,c) for(__typeof((c).begin()) i=(c).begin();i!=(c).end();i++)
#define dbg(x) cerr<<__LINE__<<": "<<#x<<" = "<<(x)<<endl

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pi;
const int inf = (int)1e9;
const double INF = 1e12, EPS = 1e-9;

int main(){
	
	int n, p1 = inf, p2 = inf, cnt = 0;
	cin >> n;
	vi a(n), ans(5);
	rep(i, n){
		cin >> a[i];
		if(p1 != inf && p2 != inf){
			if(cnt && p2 < p1 && p1 > a[i]) ans[0]++;
			if(cnt && p2 > p1 && p1 < a[i]) ans[1]++;
			if(cnt && p2 < p1 && p1 < a[i]) ans[2]++;
			if(cnt && p2 > p1 && p1 > a[i]) ans[2]++;
			if(!cnt && p2 < p1 && p1 > a[i]) ans[3]++;
			if(!cnt && p2 > p1 && p1 < a[i]) ans[4]++;
		}
		
		if(p1 != a[i]){
			p2 = p1; p1 = a[i];
			cnt = 0;
		}
		else cnt++;
	}
	cout << ans[0] << " " << ans[1] << " " << ans[2] << " " << ans[3] << " " << ans[4] << endl;
	

	return 0;
}


Measured memory_bytes: 1532
#define _GLIBCXX_DEBUG
#define _LIBCPP_DEBUG 0
#include <iostream>
#include <vector>
using namespace std;
using ll = long long;

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

  vector<ll> H(N);
  for (int i = 0; i < N; i++) cin >> H[i];

  vector<vector<int>> G(N, vector<int>());
  for (int i = 0; i < M; i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    G[a].emplace_back(b);
    G[b].emplace_back(a);
  }

  vector<int> good(N, 0);
  for (int i = 0; i < N; i++) {
    bool flag = true;
    if (G[i].size() == 0) {
      good[i] = 1;
      continue;
    }

    for (int j = 0; j < G[i].size(); j++) {
      if (H[G[i][j]] >= H[i]) flag = false;
    }
    if (flag) good[i] = 1;
  }

  int ans = 0;
  for (int i = 0; i < N; i++) {
    if (good[i] == 1) ans++;
  }

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

Measured memory_bytes: 12696