akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
using namespace std;

int main() {
  int n;
  string s;
  cin >> n;
  cin >> s;

  int dp_sharp[n];
  int dp_dot[n];
  
  dp_sharp[0] = (s[0] == '#' ? 1 : 0);
  dp_dot[n-1] = (s[n-1] == '.' ? 1 : 0);

  for (auto i=1; i<n; i++)
    dp_sharp[i] = dp_sharp[i-1] + (s[i] == '#' ? 1 : 0);

  for (auto i=n-2; 0<=i; i--)
    dp_dot[i] = dp_dot[i+1] + (s[i] == '.' ? 1 : 0);
 
  int res = 1e9;
  for (auto i=0; i<n; i++) {
    auto r = dp_sharp[i] + dp_dot[i] - 1;
    if (r < res)
      res = r;
  }
  
  cout << res;
}

Measured memory_bytes: 2676
// ------------------------------------
// Date:2018/ 4/ 2
// Problem:D- Grid Repainting re_d.cpp
//
// ------------------------------------

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 50;

int H, W;

string s[MAX_N];

int d[MAX_N][MAX_N];

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

int bfs()
{
  queue< pair< int, int > > q;
  q.push({0, 0});
  REP(hi, H)
    fill_n(d[hi], W, INF);

  d[0][0] = 0;

  while(!q.empty()) {
    int fromX, fromY;
    tie(fromY, fromX) = q.front(); q.pop();
    if (fromY == H - 1 && fromX == W - 1) return d[H - 1][W - 1];

    REP(i, 4) {
      int nextX = fromX + dx[i];
      int nextY = fromY + dy[i];

      if (!(0 <= nextY && nextY < H &&
	    0 <= nextX && nextX < W)) continue;
      if (d[nextY][nextX] != INF) continue;
      if (s[nextY][nextX] == '#') continue;
      d[nextY][nextX] = d[fromY][fromX] + 1;
      q.push({nextY, nextX});
    }
  }
  return INF;
}

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

  int cnt = 0;
  cin >> H >> W;
  REP(hi, H) {
    cin >> s[hi];
    REP(wi, W) {
      if (s[hi][wi] == '#') cnt++;
    }
  }
  int ans = H * W - cnt - bfs() - 1;
  if (ans < 0) ans = -1;
  cout << ans << endl;
  
  return 0;
}



Measured memory_bytes: 256
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] C = sc.next().toCharArray();
        sc.close();

        int n = C.length;
        int st = 0;
        for (int i = 0; i < n; ++i) {
            if (C[i] == 'A') {
                st = i;
                break;
            }
        }
        int gl = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (C[i] == 'Z') {
                gl = i;
                break;
            }
        }

        System.out.println(gl - st + 1);
	}
}


Measured memory_bytes: 27908
#include <bits/stdc++.h>
 
using namespace std;
 
#define lli long long int
#define lld long double
#define REP(i,s,n) for(lli i=s;i<n;i++)
#define RREP(i,s,n) for(lli i=s;i>=n;i--)
#define MOD 1000000007
#define NUM 2520
#define DEBUG 1
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define INF (1LL<<50)

signed main(){

	lli n,z,w;
	cin>>n>>z>>w;

	vector<lli> a(n);
	REP(i,0,n)cin>>a[i];

	if(n==1){
		cout<<abs(a[0]-w)<<endl;
		return 0;
	}

	cout<<max(abs(a[n-1]-w),abs(a[n-1]-a[n-2]))<<endl;


	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<math.h>
#include<iomanip>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<stdlib.h>
#include<stack>
using namespace std;
#define PI 3.14159265358979
typedef  long long ll;
#define rep(i,n) for(int i=0;i<n;i++)
#include<set>

int fn(int x,int y,int z)
{
    return x*x+y*y+z*z+x*y+y*z+z*x;
}



int main(void)
{
    string s;
    cin>>s;

    ll sum =0;

    rep(i,s.size())
    {
        sum += s[i] -'0';
    }

    if(sum%9==0) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;


     
}

Measured memory_bytes: 3372
#include<iostream>
#include<vector>
#include<cstring>
#include<map>
#include<bitset>
#include<assert.h>
#include<algorithm>
#include<iomanip>
#include<cmath>
#include<set>
#include<queue>
#define long long long
using namespace std;
const long N=1e6,mod=1e9+7;
long aa[N+2],bb[N+2];
int main()
{
  ios_base::sync_with_stdio(0);cin.tie(0);
  for(long i=1;i<=7;i++)cin>>aa[i],bb[i]=aa[i];
  long ans=0;
  ans+=aa[2]*2LL;
  long mn=min({aa[1],aa[4],aa[5]});
  ans+=mn*6LL;aa[1]-=mn,aa[4]-=mn,aa[5]-=mn;
  ans+=((long)(aa[1]/2))*4LL;
  ans+=((long)(aa[4]/2))*4LL;
  ans+=((long)(aa[5]/2))*4LL;
  
  for(int i=1;i<=7;i++)aa[i]=bb[i];
  long ant=0;
  ant+=aa[2]*2LL;
  ant+=((long)(aa[1]/2))*4LL;aa[1]%=2;
  ant+=((long)(aa[4]/2))*4LL;aa[4]%=2;
  ant+=((long)(aa[5]/2))*4LL;aa[5]%=2;
  mn=min({aa[1],aa[4],aa[5]});
  ant+=mn*6LL;

  for(int i=1;i<=7;i++)aa[i]=bb[i];
  long thr=0;
  thr+=aa[2]*2LL;
  mn=min({aa[1],aa[4],aa[5]});if(mn)mn--;
  thr+=mn*6LL;aa[1]-=mn,aa[4]-=mn,aa[5]-=mn;
  thr+=((long)(aa[1]/2))*4LL;
  thr+=((long)(aa[4]/2))*4LL;
  thr+=((long)(aa[5]/2))*4LL;

  cout<<max({ans,ant,thr})/2<<endl;

  return 0;
}

Measured memory_bytes: 2304
import scala.io.StdIn._

object Main extends App {

  val s = readLine()
  val qNum = readInt()
  val Q = Array.fill(qNum)(readLine().split(" "))

  def solve() = {
    val chrSeq = s.toVector
    val (chars, reverseCnt) = Q.foldLeft((chrSeq, 0)) { case ((acc, reverseCnt), q) =>
      if(q.length == 1) (acc, reverseCnt+1)
      else (f(q(2).head, acc, reverseCnt, q(1)), reverseCnt)
    }
    if(reverseCnt % 2 == 0) chars.mkString("") else chars.reverse.mkString("")
  }

  def f(chr: Char, chrSeq: Vector[Char], reverseCnt: Int, direction: String): Vector[Char] = {
    val isHead = direction == "1"
    if(reverseCnt % 2 == 0)
      if(isHead) chr +: chrSeq else chrSeq :+ chr
    else
      if(isHead) chrSeq :+ chr else chr +: chrSeq
  }

  println(solve())

}



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

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

    ll now = X[0];
    ll ix = 0;
    ll ans = 0;
    while(ix<N-1){
        if(A*(X[ix+1]-X[ix])>B){
            ans += B;
        }else{
            ans += A*(X[ix+1]-X[ix]);
        }
        ix++;
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 1024
H, W = map(int, input().split())
lst = []
for _ in range(H):
    lst.append(input())

A = []
whites = 0

for i in range(H):
    row_i = []
    for j in range(W):
        if lst[i][j] == '.':
            whites += 1
            tmp = []
            if i != 0:
                if lst[i-1][j] == '.':
                    tmp.append((i-1, j))
            if j != 0:
                if lst[i][j-1] == '.':
                    tmp.append((i, j-1))
            if i != H-1:
                if lst[i+1][j] == '.':
                    tmp.append((i+1, j))
            if j != W-1:
                if lst[i][j+1] == '.':
                    tmp.append((i, j+1))
            row_i.append(tmp)
        else:
            row_i.append([])
    A.append(row_i)

Q = [(0, 0, 0)]
visited = []

flag = False

while len(Q) != 0:
    x, y, path_length = Q.pop(0)
    if (x,y) == (H-1, W-1):
        flag = True
        break
    if (x,y) not in visited:
        visited.append((x,y))
        Q += [(i, j, path_length + 1) for (i, j) in A[x][y]]

if flag:
    print(whites - path_length - 1)
else:
    print(-1)

Measured memory_bytes: 4084
s = input()
odd = []
even =[]
flag = "Yes"
for i in range(1,len(s)+1):
    if i % 2 != 0:
        odd.append(s[i-1])
    else:
        even.append(s[i-1])
if "L" in odd:
    flag = "No"
if "R" in even:
    flag = "No"
print(flag)

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

template<typename First, typename Second, typename Third>
struct triple {
   First first;
   Second second;
   Third third;
};

using namespace std;

void solve(){
      int n;
      cin>>n;
      vector<int>v(n+2);
      v[0]=0;
      v[n+1]=0;
      long long sum=0;
      for(int i=1;i<=n;i++){
          cin>>v[i];
          sum+=abs(v[i]-v[i-1]);
      }  
      sum+=abs(v[n+1]-v[n]);
     for(int i=1;i<=n;i++){
            cout<<(sum-abs(v[i]-v[i+1])-abs(v[i]-v[i-1])+abs(v[i+1]-v[i-1]))<<"\n";
      }
}

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


Measured memory_bytes: 1664
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdint>
#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...)); }
template <class T> inline void chmin(T &a, const T& b) { if (b < a) a = b; }
template <class T> inline void chmax(T &a, const T& b) { if (b > a) a = b; }
/* clang-format on */

const ll base = 1e9;

int main() {
#ifdef DEBUG
  ifstream ifs("in.txt");
  cin.rdbuf(ifs.rdbuf());
#endif
  ll S;
  while (cin >> S) {
    ll a, b, c, d;
    // ad - bc
    a = base;
    d = S / base;
    b = 1;
    c = S % base;
    if (S % base != 0) {
      ++d;
      c = base - c;
    }
    cout << 0 << " " << 0 << " " << a << " " << b << " " << c << " " << d << endl;
  }
  return 0;
}


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

int main(void) {
    string s;
    cin >> s;

    int n = s.length();
    int mask = 0;
    int ans = n;
    unordered_map<int, int> dp;
    dp[0] = 0;
    for (int i = 0; i < n; ++ i) {
        mask ^= 1<<(s[i] - 'a');
        if (dp.find(mask) != end(dp)) ans = dp[mask];
        else ans = n;

        for (int j = 0; j < 26; ++ j) if (dp.find(mask ^ (1<<j)) != end(dp)) {
            ans = min(ans, dp[mask ^ (1<<j)] + 1);
        }
        if (dp.find(mask) == end(dp)) dp[mask] = ans;
        else if (dp[mask] > ans) dp[mask] = ans;
    }
    if (ans == 0) ++ ans;
    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 8652
n, Y = map(int, input().split())

for x in range(n+1):
  for y in range(n-x+1):
    z = n - x - y
    if 10000*x + 5000*y +1000*z == Y and 0<=z<=2000:
      print('{} {} {}' .format(x, y, z))
      exit()

print('-1 -1 -1')

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

class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader buffer = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(buffer.readLine());
        if (n>=30)
            sb.append("Yes\n");
        else
            sb.append("No\n");
        System.out.println(sb);
    }
}


Measured memory_bytes: 32608
#n = 10; a = 2; b = 5
#   n = 10; a = 1; b = 2
n, a, b = gets.chomp.split(' ').map(&:to_i)
# n = 100; a = 4; b = 16
ans = 0

1.upto(n) do |num|
  sum = num.to_s.chars.map{|i|i.to_i}.inject(:+)
  if a <= sum && sum <= b
    ans += num
  end
end


puts ans

  


Measured memory_bytes: 1788
#include<iostream>
#include<vector>
#include<numeric>
#include<algorithm>
#include<string>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;

ll gcd(ll a,ll b){
	if (a >= b) {
		ll q0 = a;
		ll q1 = b;
		while (q0 % q1) {
			ll temp = q1;
			q1 = q0%q1;
			q0 = temp;
		}
		return q1;
	}
	else gcd(b, a);
}

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

	int T;
	cin >> T;
	vector<ll> A(T), B(T), C(T), D(T);
	REP(i, T) {
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	}
	
	
	REP(i, T) {
		bool yes = true;
		if (A[i] < B[i]) yes = false;
		else {
			if (A[i] % B[i] > C[i] || B[i] > D[i]) yes = false;
			else {
				ll g = gcd( B[i], D[i] );
				if (A[i] % g - g + B[i] > C[i]) yes = false;
			}
		}
		if (yes) cout << "Yes\n";
		else cout << "No\n";
	}

	return 0;
}

Measured memory_bytes: 256
/* ~ Programmer >> Tushar Mahajan */
#include <iostream>
#include <bits/stdc++.h> 
using namespace std;
#define ll long long int
#define MOD 1000000007
#define ios ios_base::sync_with_stdio(false);cin.tie(NULL); 

int main() {
	ios;
	ll a;
	cin>>a;
	cout<<a+a*a+a*a*a<<endl;
	return 0;
}


Measured memory_bytes: 3648
def main():
    mod = 10**9+7
    H,W = list(map(int,input().split()))
    grid = [list(input()) for i in range(H)]
    DP = [[0]*W for i in range(H)]
    for i in range(H):
        if grid[i][0] == '.':
            DP[i][0] = 1
        else:
            break
    for i in range(W):
        if grid[0][i] == '.':
            DP[0][i] = 1
        else:
            break

    for i in range(1,H):
        for j in range(1,W):
            DP[i][j] = (DP[i-1][j]+DP[i][j-1])%mod if grid[i][j] == '.' else 0

    print(DP[H-1][W-1])

if __name__ == "__main__":
    main()

Measured memory_bytes: 51428
fn read<T: std::str::FromStr>() -> T {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().parse().ok().unwrap()
}

fn read_vec<T: std::str::FromStr>() -> Vec<T> {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).ok();
    s.trim().split_whitespace()
        .map(|e| e.parse().ok().unwrap()).collect()
}

fn main() {
    let _: i32 = read();
    let mut a: Vec<i32> = read_vec();
    a.sort();
    a.reverse();
    let mut score = 0;
    let mut turn = 1;
    for element in a {
        score += turn * element;
        turn *= -1;
    }
    println!("{}", score);
}

Measured memory_bytes: 4352
def main():
  n = int(input())
  task_list = [list(map(int,input().split())) for _ in range(n)]
  task_list.sort(key = lambda x:x[1])
  curr_time = 0 
  ans = 0 # if 1, say No
  
  for k in task_list:
    curr_time += k[0]
    if curr_time > k[1]:
      ans = 1
      break

  if ans == 1:
    print("No")
  else:
    print("Yes")

main()


Measured memory_bytes: 88024
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lld;

#define forn(i,n) for(ll i = 0;i<n;i++)
#define forne(i,j,n) for(ll i = j;i<n;i++)
const ll mod = 1e9+7;
const ll mod2 = 998244353;
const ll INF = 1000000001;
const ll N = 100001;
const lld PI = 3.141593;
#define F first
#define pb(a) push_back(a)
#define S second
#define pii pair<int,int>
typedef pair<ll,ll> pll;

ll powm(ll base,ll exp) {
	ll ans=1;
	while(exp){
		if(exp&1) ans=(ans*base)%mod;
		exp>>=1,base=(base*base)%mod;
	}
	return ans;
}

// ll dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
// bool valid(ll i, ll j) {
// 	return i >= 1 && i <= n && j >= 1 && j <= m; 
// }
// int maxdepth = INT_MAX;
// vector<int> edgeVector[100000];
// ll minans = 1;
// printf("1 %d D\n",abs(r));
// priority_queue<ll,vector<ll>,greater<ll>> pq;
// ll a[N],b[N];
// vector<vector<ll>> adj(N);
// vector<set<ll>> adjs(N);
// ll adj[1001][1001];
// vector<vector<ll>> ans(1001);
// bool visited[N];
// ll cnt[1001];
// ll h,c,t;
// vector<pair<int, pair<int, int> > > g[300043];

ll fact[5*N],invfact[5*N];

ll ncr(ll m,ll n){
	if(n > m) return 0;
	if(n < 0 || m < 0) return 0;
	ll f = fact[m];
	f = (f*invfact[n]%mod)%mod;
	f = (f*(invfact[m-n]%mod))%mod;
	return f;
}

void factorial(){
	fact[0] = 1;
	invfact[0] = 1;
	forne(i,1,5*N){
		fact[i] = (fact[i-1]*i)%mod;
		invfact[i] = (ll)(powm(fact[i],mod-2))%mod;
	}
}

int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output1.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

ll n,m;
cin>>n>>m;
factorial();
ll fa = 0;
// forn(i,n+1) cout<<fact[i]<<" ";cout<<endl;
// forn(i,n+1) cout<<invfact[i]<<" ";cout<<endl;
ll p = 1;
forne(i,0,n+1){
	fa+=(p)*((((ncr(n,i)*fact[n-i])%mod)*ncr(m-i,n-i))%mod);
	p*=(-1);
	fa = (fa+mod)%mod;
}
fa = ((((fa*ncr(m,n))%mod)*fact[n])%mod+mod)%mod;
cout<<fa<<endl;

}

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

using namespace std;

#define DIM 300009
#define INF ((long long)1e18+9ll)
#define pairll pair<long long,long long>
#define fi first
#define se second
#define ld long double
#define amen exit(0)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define endl '\n'
#define MODULO 1000000007

long long i,j,k,l,n,m;

int main()
{   
    fast;

    cin>>n>>m;

    if(n==1 || m==1)return cout<<1<<endl,0;

    cout<<(n*m+1)/2<<endl;

    amen;
}
/*
10101
01010
10101
*/

Measured memory_bytes: 256
#include <bits/stdc++.h>
using i64 = std::int_fast64_t;
using std::cout;
using std::cerr;
using std::endl;
using std::cin;

template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

int main() {
  int h, w, k; scanf("%d%d%d", &h, &w, &k);
  int x0, y0, x1, y1; scanf("%d%d%d%d", &x0, &y0, &x1, &y1);
  std::vector<std::string> s(h);
  for(int i = 0; i < h; i++) cin >> s[i];
  x0--; y0--; x1--; y1--;

  std::vector<int> dx = {0, 1, 0, -1};
  std::vector<int> dy = {1, 0, -1, 0};
  using P = std::tuple<i64, int, int, int>; // {cost, direction, x, y}

  auto dp = make_v<i64>(h, w, 4);
  for(int i = 0; i < h; i++) for(int j = 0; j < w; j++) for(int k = 0; k < 4; k++) dp[i][j][k] = 1LL << 60;
  dp[x0][y0][0] = 0;

  std::priority_queue<P, std::vector<P>, std::greater<P>> qu; qu.push(P{0, x0, y0, 0});
  while(!qu.empty()) {
    auto p = qu.top(); qu.pop();
    auto [cost, x, y, d] = p;
    if(dp[x][y][d] < cost) continue;
    
    { // change direction
      int nx = x, ny = y, to = (d + 1) % 4;
      i64 nxt = (cost + k - 1) / k * k;
      if(dp[nx][ny][to] > nxt) qu.push(P{dp[nx][ny][to] = nxt, nx, ny, to});
    }
    { // forward
      int nx = x + dx[d], ny = y + dy[d], to = d;
      if(nx < 0 or nx >= h or ny < 0 or ny >= w or s[nx][ny] == '@') continue;
      i64 nxt = (cost + 1);
      if(dp[nx][ny][to] > nxt) qu.push(P{dp[nx][ny][to] = nxt, nx, ny, to});
    }
  }
  i64 ans = 1LL << 60;
  for(int k = 0; k < 4; k++) ans = std::min(ans, dp[x1][y1][k]);
  if(ans == 1LL << 60) printf("-1\n");
  else printf("%lld\n", (ans + k - 1) / k);
  return 0;
}


Measured memory_bytes: 144944
inf = 10**15
mod = 10**9+7
n = int(input())
rs = [list(map(int, input().split())) for i in range(n)]
rs.sort(key = lambda x : x[0]+x[1])
pre = -inf
ans=0
for i in range(n):
    dis = rs[i][0] - rs[i][1]
    if dis >= pre:
        ans+=1
        pre = rs[i][0] + rs[i][1]
print(ans)

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

using namespace std;

typedef long long ll;
const ll INF = 1LL<<60;

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

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

ll modpow(ll a, ll n, ll mod) {
  ll res = 1;
  while (n > 0) {
    if (n & 1) res = res * a % mod;
    a = a * a % mod;
    n >>= 1;
  }
  return res;
}

ll d[200][200] = {0};
ll dr[8][8] = {0};

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

  int N, M, R;
  cin >> N >> M >> R;

  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      if(i==j){
        d[i][j] = 0;
      }else{
        d[i][j] = INF;
      }
    }
  }

  vector<int> r_vec(R);
  int r;
  for(int i = 0; i < R; i++){
    cin >> r;
    r--;
    r_vec[i] = r;
  }

  int A, B;
  ll C;
  for(int i = 0; i < M; i++){
    cin >> A >> B >> C;
    A--;
    B--;
    d[A][B] = C;
    d[B][A] = C;
  }

  for (int k = 0; k < N; k++){       // 経由する頂点
    for (int i = 0; i < N; i++) {    // 始点
      for (int j = 0; j < N; j++) {  // 終点
        d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
      }
    }
  }

  for(int i = 0; i < R; i++){
    for(int j = 0; j < R; j++){
      dr[i][j] = d[r_vec[i]][r_vec[j]];
    }
  }

  vector<int> p(R);
  for(int i = 0; i < R; i++){
    p[i] = i;
  }

  ll ans = INF;
  do{
    ll tmp_ans = 0;
    for(int i = 0; i < R-1; i++){
      tmp_ans += dr[p[i]][p[i+1]];
    }
    chmin(ans, tmp_ans);
  }while(next_permutation(p.begin(), p.end()));

  cout << ans << endl;

  return 0;
}


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

int main()
{
	int N,q;
	cin>>N;
	q=N%10;
	if(q==2 || q==4 || q==5 || q==7 || q==9) cout<<"hon"<<endl;
	else if(q==0 || q==1 || q==6 || q==8) cout<<"pon"<<endl;
	else cout<<"bon"<<endl;

  return 0;
}

Measured memory_bytes: 3648
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pi 3.141592653589793238
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define mod 1000000007
int main(){
	fast;
	int a,b;
	cin>>a>>b;
	int arr[a],sum=0;
	for(int i=0;i<a;i++)
		cin>>arr[i];
	sort(arr,arr+a);
	for(int i=a-1;i>a-b-1;i--)
		sum+=arr[i];
	cout<<sum;
	return 0;
}



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

using namespace std;

typedef long long LL;

#define fin "\n"

#define FOR(i,bg,ed) for(int i=(bg);i<(ed);i++)
#define REP(i,n) FOR(i,0,n)
template <typename T>
inline void chmin(T &l,T r){l=min(l,r);}
template <typename T>
inline void chmax(T &l,T r){l=max(l,r);}

typedef tuple<int,int,int> T;
typedef pair<int,int> P;


namespace _DSU{
#define SZ 212345
    int mem[2][SZ];
}
class UnionFind{
private:
    int *par,*rank;
    int find(int x){
	if (par[x] == x) return x;
	else return par[x] = find(par[x]);
    }
public:
    UnionFind(int n,int *par,int *rank) :par(par),rank(rank){
	for(int i = 0; i < n; i++)par[i] = i,rank[i] = 0;
    }
    UnionFind(int n):UnionFind(n,_DSU::mem[0],_DSU::mem[1]){}
    bool unite(int x, int y){
	x = find(x);y = find(y);
	if (x == y)return false;
	if (rank[x] < rank[y]) par[x] = y;
	else{
	    par[y] = x;
	    if (rank[x] == rank[y])rank[x]++;
	}
	return true;
    }
    bool same(int x, int y){
	return find(x) == find(y);
    }
};

#define fi first
#define se second
int N,Q;

T abc[212345];
vector<P> que[412345];
int main(){
    scanf("%d %d",&N,&Q);
    int LB=1e9;
    REP(i,Q){
        int a,b, c;
        scanf("%d %d %d",&a,&b,&c);
        abc[i]=T(a,b,c);
        chmin(LB,c);
    }
    
    REP(i,Q){
        int a,b,c;
        tie(a,b,c)=abc[i];
        c-=LB;
        if(c<2*N&&a!=b){
            que[c].push_back(P(a,b));
        }
        a=(a+1)%N;
        c++;
        if(c<2*N&&a!=b){
            que[c].push_back(P(a,b));
        }
    }
    UnionFind uf(N);
    LL res=LB*(LL)(N-1);
    
    REP(i,2*N){
        while(!que[i].empty()){
            auto v=que[i].back();que[i].pop_back();
            int a,b;
            tie(a,b)=v;
            int c=i;
            //cout<<a<<b<<c<<endl;
            if(!uf.same(a,b)){
                res+=c;
                uf.unite(a,b);
                que[c+2].push_back(P((a+1)%N,(b+1)%N));
            }
        }
    }
    
    
    
    
    cout<<res<<endl;

    return 0;
}


Measured memory_bytes: 24832
#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
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; }


int main() {
    int a, b, c; cin >> a >> b >> c;
    int k; cin >> k;
    int ans = 0;
    // aには何もしない
    if(a >= b) {
        for(int i = 0; ; ++i) {
            ans++;
            b *= 2;
            if(a < b) break;
        }
    }
    if(b >= c) {
        for(int i = 0; ; ++i) {
            ans++;
            c *= 2;
            if(b < c) break;
        }
    }

    if(ans <= k) cout << "Yes" << endl;
    else cout << "No" << endl;
}

Measured memory_bytes: 3632
import bisect

n = int(input())
ps = [0] * (1 << 16)
for i in range(1 << 16):
    temp = 0
    for j in range(16):
        if (i >> j) & 1:
                temp += (-2) ** (2 *j)
    ps[i] = temp

"""
for index, value in enumerate(ps):
    print(bin(index)[2:].zfill(16), value)
"""

pattern1 = None
pattern2 = None

for i in range(1 << 16):
    temp2 = 0
    for j in range(16):
        if (i >> j) & 1:
                temp2 += (-2) ** (2 *j + 1)
    n2 = n - temp2
    pattern1 = bisect.bisect_left(ps, n2)
    if pattern1 != (1 << 16) and ps[pattern1]==n2:
        pattern2 = bin(i)[2:].zfill(16)
        pattern1 = bin(pattern1)[2:].zfill(16)
        break

ans = ""
for i in range(16):
    ans += pattern2[i]
    ans += pattern1[i]
    
true_ans = ""
flag = False
for i in range(len(ans)):
    if ans[i]=="1":
        true_ans += "1"
        flag = True
    elif flag:
        true_ans += "0"

if true_ans == "":
    true_ans = "0"
        
print(true_ans)

Measured memory_bytes: 43484
#include<bits/stdc++.h>
using namespace std;
int main(){
	int s;
	string ss;
	cin>>s;
	ss=to_string(s);
	int l=ss.size();
	int nowl=1,total=0;
	while(nowl<=l){
		if(nowl<l){
			total+=pow(10,nowl)-pow(10,nowl-1);
		}else{
			total+=s-pow(10,nowl-1)+1;
		}
		nowl+=2;
	}
	cout<<total<<endl;
}

Measured memory_bytes: 512
import bisect
A, B, Q = map(int, input().split())
sl = []
tl = []
xl = []
for i in range(A):
    sl.append(int(input()))
for i in range(B):
    tl.append(int(input()))
for i in range(Q):
    xl.append(int(input()))
sl.sort()
tl.sort()
def func(i):
    slm = bisect.bisect_right(sl, xl[i])
    try:
        sleft = xl[i] - sl[slm-1]
        assert sleft >= 0
    except:
        sleft = float('inf')
    
    try:
        sright = sl[slm] - xl[i]
    except:
        sright = float('inf')
    
    tlm = bisect.bisect_right(tl, xl[i])
    try:
        tleft = xl[i] - tl[tlm-1]
        assert tleft >= 0
    except:
        tleft = float('inf')
        
    try:
        tright = tl[tlm] - xl[i]
    except:
        tright = float('inf')
    
    ll = max(sleft, tleft)
    lr = sleft + tright + min(sleft, tright)
    rl = sright + tleft + min(sright, tleft)
    rr = max(sright, tright)
    
    print(min(ll, lr, rl, rr))

for i in range(Q):
    func(i)

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

bool solve() {
    ll D, T, S;
    cin >> D >> T >> S;
    if ( S * T >= D ) return true;
    else return false;
}

int main() {
    string ans = solve() ? "Yes" : "No";
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 3588
#include <bits/stdc++.h>
using namespace std;
#define X ios_base::sync_with_stdio(false); cin.tie(NULL);
#define FIXED_FLOAT(x) std::fixed <<std::setprecision(2)<<(x)


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

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif


long long p = 1e9+7;
typedef pair<int, int> pi;
typedef unordered_map<int, int> UMP;
typedef long long ll;
typedef vector<ll> VI;
#define FOR(i,b) for(i=0;i<b;i++)
#define pb push_back


void printa(VI x,ll n){
    ll i;
    FOR(i, n){
        cout<<x[i]<<" ";
    }
    cout<<endl;
}

int main(){

    long double l;
    cin>>l;
    long double x = pow(l/3, 3);
    // cout<<
    cout<<fixed<<setprecision(7)<<x;
}

// 2017634310362021

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

#define rep(i,s,t) for(int i = s; i <= t; ++ i)

const int MaxN = 105;

int K, N, M, A[MaxN];

int main()
{
	scanf("%d%d",&K,&N);
	rep(i,1,N) scanf("%d",&A[i]);
	M = N-1;
	sort(A+1,A+N+1);
	if(A[N]*2 <= K){puts("0"); return 0;} 
	rep(i,1,M)
	{
		sort(A+1,A+N+1);
		A[N] -= A[N-1];
		A[N-1] = A[N];
		-- N;
	}
	printf("%d",A[1]-1);
	return 0;
}

Measured memory_bytes: 256
# include <iostream>
# include <algorithm>
#include <array>
# include <cassert>
#include <cctype>
#include <climits>
#include <numeric>
# include <vector>
# include <string>
# include <set>
# include <map>
# include <cmath>
# include <iomanip>
# include <functional>
# include <tuple>
# include <utility>
# include <stack>
# include <queue>
# include <list>
# include <bitset>
# include <complex>
# include <chrono>
# include <random>
# include <limits.h>
# include <unordered_map>
# include <unordered_set>
# include <deque>
# include <cstdio>
# include <cstring>
#include <stdio.h>
#include<time.h>
#include <stdlib.h>
#include <cstdint>
#include <cfenv>
#include<fstream>
//#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using ULL = unsigned long long;
const long long MOD = 1000000000 + 7;//1000000000 + 7 998244353 924844033 1000000000 + 9;
constexpr long long INF = 1LL << 60;//numeric_limits<LL>::max();
const double PI = acos(-1);
#define fir first
#define sec second
#define thi third
#define debug(x) cerr<<#x<<": "<<x<<'\n'
typedef pair<LL, LL> Pll;
typedef pair<double, double> Dll;
typedef pair<LL, pair<LL, LL>> Ppll;
typedef pair<LL, pair<LL, bitset<100001>>> Pbll;
typedef pair<LL, pair<LL, vector<LL>>> Pvll;
typedef pair<LL, LL> Vec2;
struct Tll { LL first, second, third; };
struct Fll { LL first, second, third, fourth; };
typedef pair<LL, Tll> Ptll;
#define rep(i,rept) for(LL i=0;i<rept;i++)
#define Rrep(i,mf) for(LL i=mf-1;i>=0;i--)
void YN(bool f) {
	if (f)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
void yn(bool f) {
	if (f)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}
struct Edge { LL to, cost; };
struct edge {
	LL from, to, cost;
};
vector<vector<Edge>>g;
vector<edge>ed;
vector<Pll>pv;
set<LL>st;
map<Pll, LL>ma;
int di[4][2] = { { 0,1 },{ 1,0 },{ 0,-1 },{ -1,0 } };
string str, ss;
bool f;
LL n, m, s, t, h, w, k, q, p, ans, sum, cnt, a[5100];
int main() {
	cin >> k;
	cout << 50 << endl;
	m = k / 50;
	k -= m * 50;
	rep(i, 50)a[i] = i + m;
	LL cur = 49;
	while (k>0) {
		a[cur]++;
		cur--;
		k--;
	}
	rep(i, 50) {
		if (i)cout << " ";
		cout << a[i];
	}
	cout << endl;
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<string>
using namespace std;
int main(){
    int dice,face[6]={},l;
    string command;
    for(int i=0;i<6;i++){
        cin >> face[i];
    }
    
    cin >> command;
    l=command.size();
    for(int i=0;i<l;i++){
        if(command[i]=='N'){
            int tmpa=face[0];
            int tmpb=face[4];
            face[0]=face[1];
            face[1]=face[5];
            face[4]=tmpa;
            face[5]=tmpb;
        }
        
        if(command[i]=='S'){
            int tmpc=face[0];
            int tmpd=face[1];
            face[0]=face[4];
            face[1]=tmpc;
            face[4]=face[5];
            face[5]=tmpd;
        }
            if(command[i]=='E'){
            int tmpe=face[0];
            int tmpf=face[2];
            face[0]=face[3];
            face[2]=tmpe;
            face[3]=face[5];
            face[5]=tmpf;
        }   
            if(command[i]=='W'){
            int tmpg=face[0];
            int tmph=face[3];
            face[0]=face[2];
            face[2]=face[5];
            face[3]=tmpg;
            face[5]=tmph;
        }
    }
    cout << face[0] << endl;
    return 0;
}



Measured memory_bytes: 3224
#include <iostream> // cout, endl, cin
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include<cmath>
#include<limits>
#define ll long long
#define ALL(x) (x).begin(),(x).end()
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define int_INF 2147483647
#define pint_INF 2000000000
#define ll_INF 	9223372036854775807
#define MOD 1000000007
#define vi vector<int>
#define vvi vector<vector<int>>
#define vvll vector<vector<long long>>
#define vvc vector<vector<char>>
#define vll vector<long long>
#define pii pair<int,int>
#define vpii vector<pair<int,int>>
#define sysp system("PAUSE")
#define pno cout << "no" << endl
#define pyes cout << "yes" << endl
#define pYes cout << "Yes" << endl
#define pNo cout << "No" << endl
using namespace std;

class Arithmetics {
private:
	bool is_prime[300000 + 13];// Up to 3e5 + 1
	vector<long long> Prime_table;
public:
	vector<long long> Eratosthenes(const long long N = 300007) { // return primes up to N
		for (int i = 0; i <= N; i++)
		{
			is_prime[i] = true;
		}
		for (int i = 2; i <= N; i++)
		{
			if (is_prime[i])
			{
				for (int j = 2 * i; j <= N; j += i)
				{
					is_prime[j] = false;
				}
				Prime_table.emplace_back(i);
			}
		}
		return Prime_table;
	}

	vector<vector<long long>> Factorization(long long N) const {
		if (N == 1) {
			return { {-1} };
		}
		vector<vector<long long>> res;
		for (int i = 0; i < Prime_table.size() && N != 1; i++) {
			if (N % Prime_table[i] == 0) {
				res.push_back({ Prime_table[i],1 });
				N /= Prime_table[i];
				while ((N %= Prime_table[i]) == 0 && N != 0) {
					int index = res.size() - 1;
					res[index][1]++;
					N /= Prime_table[i];
				}
			}
		}

		if (N > Prime_table.back()) {
			res.push_back({ N,1 });
		}
		return res;
	}

	bool isPrime(long long x) {
		if (x == 0 || x == 1) {
			return false;
		}
		return is_prime[x];
	}
};

int main() {
	Arithmetics ars;
	ars.Eratosthenes();
	int M = 100007;
	vector<int> acc(M);
	acc[1] = 0;
	for (int i = 1; 2 * i + 1 < M; i++) {
		int J = 2 * i + 1;
		bool bN = ars.isPrime(J);
		bool bN1 = ars.isPrime((J + 1) / 2);
		if (bN && bN1) {
			acc[J] = acc[J - 2] + 1;
		}
		else {
			acc[J] = acc[J - 2];
		}
	}


	int Q; cin >> Q;
	for (int t = 0; t < Q; t++) {
		int l, r; cin >> l >> r;
		int u = 0;
		if (ars.isPrime(l) == true && ars.isPrime((l+1)/2) == true) {
			u++;
		}
		cout << acc[r] - acc[l] + u << endl;
	}
}

Measured memory_bytes: 4080
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

lia, lib = [0], [0]
for i in range(n):
    lia.append(lia[i] + a[i])
for i in range(m):
    lib.append(lib[i] + b[i])

ans, j = 0, m
for i in range(n + 1):
    if lia[i] > k:
        break

    while lib[j] > k - lia[i]:
        j -= 1
    ans = max(ans, i + j)

print(ans)


Measured memory_bytes: 134324
#include <bits/stdc++.h>
 
using namespace std;
 
#define MAX 35
#define EPS 1e-10
#define equal(a,b) (fabs(a-b) < EPS)
 
struct Point{
    double x,y;
 
    Point(){}
    Point(double x,double y) : x(x),y(y) {}
 
    Point operator + (const Point &p)const{ return Point(x+p.x,y+p.y); }
    Point operator - (const Point &p)const{ return Point(x-p.x,y-p.y); }
    Point operator * (const double &k)const{ return Point(x*k,y*k); }
    Point operator / (const double &k)const{ return Point(x/k,y/k); }
    bool operator < (const Point &p)const{ return x != p.x ? x < p.x : y < p.y; }
};
 
typedef Point Vector;
typedef vector<Point> Polygon;
 
double cross(const Point &a,const Point &b){ return a.x*b.y - b.x*a.y; }
 
ostream &operator << (ostream &os,Point &p){ 
    return os << "(" << p.x << "," << p.y << ")";
}
 
struct Segment{
    Point s,t;
    Segment(){}
    Segment(Point s,Point t) : s(s),t(t) {}
};
 
Point crosspointSS(const Segment &a,const Segment &b){
    Vector va = a.t-a.s, vb = b.t-b.s;
    double d = cross(vb,va);
    return a.s+va*cross(vb,b.t-a.s)*(1.0/d);
}
 
double getArea(const Polygon &p){
    int N = p.size();
    double res = 0;
    for(int i = 1 ; i < N+1 ; i++){
	res += (p[i%N].x-p[i-1].x)*(p[i%N].y+p[i-1].y);
    }
    res /= 2.0;
    return abs(res);
}
 
int main(){
    int N;
    while(cin >> N,N){
	double in;
	vector<Point> p[4];
	Point q[MAX][MAX];
	q[0][0] = Point(0,0);
	q[0][N+1] = Point(0,1);
	q[N+1][0] = Point(1,0);
	q[N+1][N+1] = Point(1,1);
	for(int i = 0 ; i < 2 ; i++){
	    p[i].resize(N);
	    for(int j = 0 ; j < N ; j++){
		cin >> in;
		p[i][j] = Point(in,i);
		if(i == 0){
		    q[j+1][0] = p[i][j];
		}else{
		    q[j+1][N+1] = p[i][j];
		}
	    }
	}
	for(int i = 2 ; i < 4 ; i++){
	    p[i].resize(N);
	    for(int j = 0 ; j < N ; j++){
		cin >> in;
		p[i][j] = Point(i-2,in);
		if(i == 2){
		    q[0][j+1] = p[i][j];
		}else{
		    q[N+1][j+1] = p[i][j];
		}
	    }
	}
	vector<Segment> s[2];
	for(int i = 0 ; i < N ; i++){
	    s[0].push_back(Segment(p[0][i],p[1][i]));
	}
	for(int i = 0 ; i < N ; i++){
	    s[1].push_back(Segment(p[2][i],p[3][i]));
	}
	for(int i = 0 ; i < N ; i++){
	    for(int j = 0 ; j < N ; j++){
		Point cp = crosspointSS(s[0][i],s[1][j]);
		q[i+1][j+1] = cp;
	    }
	}
	double res = 0;
	for(int i = 0 ; i <= N ; i++){
	    for(int j = 0 ; j <= N ; j++){
		Polygon pg(4);
		pg[0] = q[i][j];
		pg[1] = q[i][j+1];
		pg[2] = q[i+1][j+1];
		pg[3] = q[i+1][j];
		res = max(res,getArea(pg));
	    }
	}
	printf("%.10f\n",res);
    }
    return 0;
}

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

#define MOD 1000000007
#define rep(i, n) for(ll i=0; i < (n); i++)
#define rrep(i, n) for(ll i=(n)-1; i >=0; i--)
#define ALL(v) v.begin(),v.end()
#define rALL(v) v.rbegin(),v.rend()
#define FOR(i, j, k) for(ll i=j;i<k;i++)
#define DUMP(i, v)for(ll i=0;i<v.size();i++)cerr<<v[i]<<" "

using namespace std;
typedef long long int ll;
typedef vector<ll> llvec;
typedef vector<double> dvec;
typedef pair<ll, ll> P;
typedef long double ld;
struct edge{ll x, c;};

ll mod(ll a, ll mod){
  ll res = a%mod;
  if(res<0)res=res + mod;
  return res;
}

ll modpow(ll a, ll n, ll mod){
  ll res=1;
  while(n>0){
    if(n&1) res=res*a%mod;
    a=a*a%mod;
    n>>=1;
  }
  return res;
}

ll modinv(ll a, ll mod){
  return modpow(a, mod-2, mod);
}

ll gcd(ll a, ll b){
  ll r = a%b;
  if(r==0) return b;
  else return gcd(b, a%b);
}

bool is_prime(ll n){
  ll i = 2;
  if(n==1)return false;
  if(n==2)return true;
  bool res = true;
  while(i*i <n){
    if(n%i==0){
      res = false;
    }
    i = i+1;
  }

  //if(i==1)res = false;
  if(n%i==0)res=false;
  return res;
}

struct UnionFind{
  ll N;
  llvec p;
  llvec cnt;
  UnionFind(ll n){
    N = n;
    p=llvec(N);
    cnt=llvec(N, 0);
    rep(i, N){
      p[i] = i;
      cnt[i] = 1;
    }
  }

  void con(ll a, ll b){
    P at = root(a);
    P bt = root(b);
    if(at.second!=bt.second){
      if(at.first>bt.first){
        swap(at, bt);
        swap(a, b);
      }
      p[at.second] = bt.second;
      cnt[bt.second]+=cnt[at.second];
      p[a]=bt.second;
    }
  }

  P root(ll a){
    ll atmp = a;
    ll c=0;
    while(atmp!=p[atmp]){
      atmp = p[atmp];
      c++;
    }
    p[a] = atmp;
    return {c, atmp};
  }

  bool is_con(ll a, ll b){
    P at=root(a);
    P bt=root(b);
    return at.second == bt.second;
  }
  
};

struct dijkstra{
  ll N;
  llvec d;
  llvec mark;
  vector<vector<edge>> e;
  dijkstra(ll n){
    N = n;
    //d = llvec(N, 1e18);
    e = vector<vector<edge>>(N);
  }

  void add_edge(ll from, ll to, ll cost){
    e[from].push_back({to, cost});
  }

  void run(ll start){
    priority_queue<P, vector<P>, greater<P>> que;
    que.push({0, start});
    d = llvec(N, 1e18);
    mark = llvec(N, 1e18);
    d[start]=0;
    while(!que.empty()){
      P q = que.top();que.pop();
      ll dc = q.first;
      ll x = q.second;
      if(dc>d[x]){
        continue;
      }else{
        for(auto ip: e[x]){
          if(d[ip.x]<=d[x]+ip.c){
            continue;
          }else{
            d[ip.x]= d[x]+ip.c;
            mark[ip.x] = x+1;
            que.push({d[ip.x], ip.x});
          }
        }
      }
    }
  }  
};


/**************************************
** A main function starts from here  **
***************************************/
int main(){
  ll N, M;
  cin >> N >> M;
  dijkstra dijk(N);
  rep(i, M){
    ll a, b;
    cin >> a  >> b;
    a--;b--;
    dijk.add_edge(a,b,1);
    dijk.add_edge(b,a,1);
  }

  dijk.run(0);
  cout << "Yes"<<endl;
  rep(i, N-1){
    cout << dijk.mark[i+1]<<endl;
  }
  
  return 0;
}


Measured memory_bytes: 19548
from numba import njit


@njit
def solve(a, b, c, x, y):
    ans = 10000000000000000
    for i in range(100000 + 1):
        X = i * (2 * c) + max(0, x - i) * a + max(0, y - i) * b
        ans = min(ans, X)
    return ans


a, b, c, x, y = map(int, input().split())
print(solve(a, b, c, x, y))


Measured memory_bytes: 109152
# -*- coding: utf-8 -*-
# 回数N
N = int(input())
# 最低人数とポイント
num_temp = 0
num_point = 0
# 最低人数を探す
for n in range(N):
    num , point = map(int, input().split())
    if num_temp < num:
        num_temp = num
        num_point = point
# 最低人数+ポイント=参加人数のありうる最大値
print(num_temp + num_point)

Measured memory_bytes: 3060
require 'pp'
# IS_DEBUG = true
IS_DEBUG = false
def dputs str
	if(IS_DEBUG)
		puts str
	end
end
def dpp str
	if(IS_DEBUG)
		pp str
	end
end

N,d=gets.chomp.split(' ').map{|n| n.to_i}
A = Array.new(N+2)	# 1 index
A=[0] + gets.chomp.split(' ').map{|n| n.to_i} + [0]
# pp A
sum = 0
0.upto(N){|i|
	sum += (A[i+1]-A[i]).abs
}
# pp sum
1.upto(N){|i|
	# when skip A_i
	a=A[i-1]
	b=A[i]
	c=A[i+1]
	if(a<=b && b<=c || a>=b && b>=c)
		puts sum
	elsif(b<a && a<c || c<a && a<b)
		puts sum - (b-a).abs * 2
	else
		puts sum - (b-c).abs * 2
	end
}


Measured memory_bytes: 15980
#include<bits/stdc++.h>
// #include <boost/lexical_cast.hpp>
using namespace std;

#define ll long long int
#define vll vector<ll>
#define vllv vector<vector<ll>> 
#define vpii vector<pair<ll,ll>>
#define sz size()
#define pb push_back
#define ff first
#define ss second
#define all(v) v.begin(),v.end()
#define allr(v) v.rbegin(),v.rend()
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
ll MOD=1000000000+7;
ll ceil1(ll n,ll m){if(n%m==0){return n/m;}return n/m +1;}
ll factor(ll n){
    vll ans;
	if(n==2)ans.pb(2);
	else
    {for(ll i=2;i*i<=n;i++){if(n%i==0 && n%i!=i){ans.pb(i);if(n/i!=i)ans.pb(n/i);}}ans.pb(n);}
    return ans.sz+1;
}
ll fact(ll n){ll res = 1;for (ll i = 2; i <= n; i++)res = res * i; 
    return res; } 
  
ll nCr(ll n, ll r){ return fact(n) / (fact(r) * fact(n - r)); } 
  
void dfs(vllv &v,ll k,vll &par,vll &dis,ll p)
{
    par[k]=p;
    dis[k]=dis[p]+1;
    for(ll i=0;i<v[k].sz;i++){
        if(v[k][i]!=p){
            dfs(v,v[k][i],par,dis,k);
        }
    }
}
bool sortbysec(const pair<string,int> &a,const pair<string,int> &b){return (a.second<b.second);} 

ll pow2(ll n,ll k){ll ans=1;
    while(k>0){
        if(k%2==1)ans=ans*n;n=n*n;k/=2;
    }return ans;}
bool prime(int n){
    int i,j;
    for(i=2;i<=sqrt(n);i++){
        if(n%i==0){
            return false;
        }
    }
    return true;
}
bool bserch(vector<string> a, string s){
	ll l=0,r=a.sz-1,mid;
	while(l<=r){
		mid=(l+r)/2;
		if(a[mid]==s)return true;
		if(a[mid]<s){
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	return false;
}

bool sortcol(const vector<int>& v1, 
               const vector<int>& v2){ 
 return v1[0] < v2[0]; } 

 ll sumdegit(ll n)
 {
 	ll sum=0;
 	while(n>0)
 	{
 		sum+=(n%10);
 		n/=10; 	}
 		return sum;
 }

void solve()
{
	/*ll h,w,k;
	vector<string> s;
	for(ll i=0;i<n;i++)
		cin>>s;*/
	ll n;
	cin>>n;
	vll a(n);
	for(ll i=0;i<n;i++)
		cin>>a[i];
	sort(all(a));
	ll ans=0;
	ans+=a[n-1];
	
	ll k=n-2;
	
	ll c=n-2;
	while(1)
	{
		if(c==0)
			break;
		if(c>1)
		{
			// cout<<a[k]<<" ";
			ans+=(2*a[k]);
			k--;
			c-=2;
			if(c==0)
				break;
		}
		else if(c==1)
		{
			// cout<<a[k]<<" ";
			ans+=a[k];
			k--;
			break;
		}
		
	}
	cout<<ans;
	return;
}  
int main()
{
	fast;
    ll q;
    q=1;
    // cin>>q;
    while(q--)
    {
        solve();
    }
    return 0;
}

Measured memory_bytes: 4784
#include<iostream>
#include<math.h>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<algorithm>
#include<bitset>
using namespace std;
#define _GLIBCXX_DEBUG
#define pq priority_queue
#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define pii pair<long long,long long>
#define ppii pair<long long,pair<long long,long long>>
#define all(x) (x).begin(),(x).end()
#define rep(x) for(int i = 0;i < (x);i++)
#define repj(x) for(int j = 0;j < (x);j++)
#define REP(i,x) for(int (i) = 0;(i) < (x);(i)++)
#define rrep(x) for(int i = (x);i >= 0;i--)
#define mins(x,y) x = min(x,y)
#define maxs(x,y) x = max(x,y)
#define mod 1000000007
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
#define pyes cout << "Yes" << endl
#define pno cout << "No" << endl
typedef vector<vector<long long>> vii;
typedef long long lint;
typedef long long ll;
lint qp(int a, ll b) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a; a = 1ll * a*a; } while (b >>= 1); return ans; }
lint qp(int a, ll b, int mo) { int ans = 1; do { if (b & 1)ans = 1ll * ans*a%mo; a = 1ll * a*a%mo; } while (b >>= 1); return ans; }
lint gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
//int dx[4] = { 1,0,-1,0 };
//int dy[4] = { 0,1,0,-1 };
long long INF = 1e14;
const int MAX_N = 1 << 17;
const int cf = 100010;
///////////////////////////////////////////////////////////////////////////////
 
template<class T>
vector<pair<T,int>> runlength(vector<T> arr) {
	int i = 0;
	int n = arr.size();
	vector<pair<T, int>> run;
	while (i < arr.size()) {
		T t = arr[i];
		int k = 0;
		while (i + k < n && arr[i + k] == t) k++;
		run.push_back(pair<T, int>(t, k));
		i += k;
	}
	return run;
}
 
template<class T>
int freq(vector<T> arr,int k) {
	vector<T> vec = arr;
	int n = arr.size();
	sort(all(vec));
	int i = 0;
	vector<pair<int, T>> run;
	while (i < arr.size()) {
	    T t = arr[i];
		int k = 0;
		while (i + k < n && arr[i + k] == t) k++;
		run.push_back(pair<int, T>(k, t));
		i += k;
	}
	sort(all(run));
	int lyn = run.size();
	lint sum = 0;
	for (int i = 0; i < lyn - k; i++) sum += run[i].first;
	return sum;
}
 
int main(void) {
	int n, k; cin >> n >> k;
	vector<int> a(n); rep(n)cin >> a[i];
	sort(all(a));
	cout << freq(a, k) << endl;
	return 0;
 
}

Measured memory_bytes: 4724
N,B=map(int,input().split())
num=0
x=-1
y=-1
z=-1
for X in range(N+1):
    for Y in range(N-X+1):
        Z=N-X-Y
        money=10000*X+5000*Y+1000*Z
        if money==B:
            x=X
            y=Y
            z=Z
print(x," ",y," ",z)

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

ll n,i;
double a[105],sum;

int main()
{
	cin>>n;
  	for(i=0;i<n;i++)
      cin>>a[i];
    sort(a,a+n);
    sum=a[0];
  	for(i=1;i<n;i++)
      sum=(sum+a[i])/2.0;
  	
	printf("%0.6lf",sum);  	
}

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

int main()
{
	int n;
	cin >> n;
	int64_t a[n];
	for (auto &i : a)
	{
		cin >> i;
	}
	map<int64_t, int64_t> m;
	int64_t dp[n + 1]{};
	for (int i = 0; i < n; i++)
	{
		dp[i + 1] = dp[i] + a[i];
	}
	int64_t ans = 0;
	for (int i = 0; i <= n; i++)
	{
		ans += m[dp[i]]++;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 15872