akhauriyash/Code-Regression huggingface dataset:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=ST()
    B=ST()
    C=ST()
    ans = 0
    for a,b,c in zip(A,B,C):
        ans += len(set([a,b,c]))-1
    print(ans)
if __name__ == '__main__':
    main()

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

using namespace std;

using ll = long long;
using vi = vector<int>;
using db = double;
#define pb push_back

const int mxn = 100006 * 3;

int n;
int a[mxn];

struct {
	multiset<int> H, L;
	ll s = 0;
	ll max() {
		return s;
	}
	void add(int x) {
		H.insert(x);
		s += x;
		while (H.size() > n) {
			s -= *H.begin();
			L.insert(*H.begin());
			H.erase(H.begin());
		}
	}
	void rem(int x) {
		if (L.find(x) != L.end()) {
			L.erase(L.find(x));
		} else {
			H.erase(H.find(x));
			s -= x;
			if (!L.empty()) {
				H.insert(*L.rbegin());
				s += *L.rbegin();
				L.erase(--L.end());
			}
		}
	}
} A, B;

int main() {
	cin >> n;
	for (int i = 1; i <= n * 3; ++i)
		scanf("%d", &a[i]);
	
	for (int i = 1; i <= n; ++i)
		A.add(a[i]);
	for (int i = n + 1; i <= n * 3; ++i)
		B.add(-a[i]);
	
	ll s = -LLONG_MAX;
	for (int i = n; i <= n * 2; ++i) {
		s = max(s, A.max() - -B.max());
		//cout << A.max() << ' ' << -B.max() << endl;
		if (i + 1 <= n * 2)
			A.add(a[i + 1]), B.rem(-a[i + 1]);
	}
	
	cout << s << endl;
	
	return 0;
}


Measured memory_bytes: 15488
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0, i##_len = (n); i < i##_len; i++)
#define reps(i, s, n) for(int i = (s), i##_len = (n); i < i##_len; i++)
#define rrep(i, n) for(int i = (n) - 1; i >= 0; i--)
#define rreps(i, e, n) for(int i = (n) - 1; i >= (e); i--)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((int)(x).size())
#define uniq(x) (x).erase(unique((x).begin(), (x).end()), (x).end())

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    int A, B;
    cin >> A >> B;
    bool ans = true;
    
    if ((A >= 10) || (B >= 10)) {
        ans = false;
    }
    
    cout << (ans ? (A * B) : -1) << endl;
    return 0;
}

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

using namespace std;
typedef int64_t ll;
typedef uint64_t ull;
typedef long double ld;


const ll Mod = 1e9+7;

ll power(ll a, ll b) {
	if(b == 0) return 1;
	if(b == 1) return a % Mod;
	
	ll res = 1;
	a %= Mod;
	while(b) {
		if(b & 1) res = res*a % Mod;
		b >>= 1;
		a = a*a % Mod;
	}
	return res % Mod;
}

ll C(ll a, ll b) {
	ll x=1, y=1;
	for(ll i = 1; i <= b; i++) {
		x = x*(a-i+1) % Mod;
		y= y*i % Mod;
	}
	return x*power(y, Mod-2) % Mod;
}

int main() {
#ifdef cute
	freopen("in", "r", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	ll x, y;
	cin >> x >> y;
	if((x+y) % 3) {
		cout << 0;
		return 0;
	}

	ll n = (x+y)/3;
	x -= n; y -= n;
	
	if(x < 0 || y < 0) {
		cout << 0;
		return 0;
	}

	cout << C(n, x);

#ifdef cute
	cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << " ms.\n";
#endif
}

// g++ o .cpp -O2 -std=c++11 -D cute -Wall -Wno-unused-result



Measured memory_bytes: 256
N = int(input())
T = []
for i in range(N):
   T.append(tuple(map(int, input().split())))

T = sorted(T, key=lambda x:x[1])
t = 0
for a, b in T:
  t += a
  if t > b:
    print("No")
    quit()
print("Yes")


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

// 添字の mod Nは省略
// A_i xor A_{i+2}= A_{i+1}
// A_{i+1} xor A_{i+3}= A_{i+2} より
// A_i= A_{i+3} が必要
// Nが3の倍数かどうかで場合分けする
int main(){
  int N;
  cin >> N;

  unordered_map<int, int> data;
  int key;
  for(int i=0; i<N; i++){
    cin >> key;
    if(data.count(key)){ data.at(key)++; }
    else               { data[key]= 1; }
  }

  auto solve= [](int N, const unordered_map<int, int> &data){
    if(N % 3 != 0){
      return (data.size()==1) && (data.count(0));
    }
    else{
      const int Ncyc= N/3;

      bool ans= true;
      int cumxor= 0;
      for(auto [key, freq]:data){
        if(freq % Ncyc==0){
          for(int i=0; i< freq/ Ncyc; i++){
            cumxor^= key;
          }
        }
        else{
          ans= false;
        }
      }
      ans&= cumxor==0;

      return ans;
    }
  };

  string ans= solve(N, data) ? "Yes"
                             : "No";

  cout << ans << endl;
}

Measured memory_bytes: 6572
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1000000007;
int p(int A,int B){
  if(!B)return 1;
  if(B&1)return p(A,B-1)*A%mod;
  int C=p(A,B/2);
  return C*C%mod;
}
int k[100100];
int c(int A,int B){
  if(A<B || B<0)return 0;
  return k[A]*p(k[A-B],mod-2)%mod;
}
signed main(){
  k[0]=1;
  for(int i=1;i<=100000;i++)k[i]=k[i-1]*i%mod;
  int N,K;
  cin>>N>>K;
  vector<vector<int>> A(N);
  for(int i=0;i<N-1;i++){
    int a,b;
    cin>>a>>b;
    A[a-1].push_back(b-1);
    A[b-1].push_back(a-1);
  }
  queue<int> Q;
  Q.push(0);
  vector<bool> B(N,true);
  B[0]=false;
  int ans=K*c(K-1,A[0].size())%mod;
  while(!Q.empty()){
    int I=Q.front();
    Q.pop();
    for(int i:A[I])
      if(B[i]){
        ans=ans*c(K-2,(int)A[i].size()-1)%mod;
        B[i]=false;
        Q.push(i);
      }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 11128
#include <stdio.h>
#include <stdlib.h>
#include <math.h>

int main(){
    char c[20];
    int i = 0;
    for(i = 0; i < 19; i++){
	scanf(" %c", &c[i]);
    }
    c[5] = ' ';
    c[13] = ' ';
	printf("%s", c);
	return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
typedef  long long ll;
using vll=vector<ll>;
using vvll=vector<vll>;
using vi=vector<int>;
using vvi=vector<vector<int>>;
using vb=vector<bool>;
using pii=pair<int,int>;
using vpii=vector<pair<int,int>>;
using plli=pair<ll,int>;
using vplli=vector<pair<ll,int>>;
using pllll=pair<ll,ll>;
using vpllll=vector<pair<ll,ll>>;

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

//pow(llpow,modpow)
template<class T> ll llpow(ll x,T n){ll ans=1;if(x==0)ans=0;while(n){if(n&1)ans*=x;x*=x;n>>=1;}return ans;}
long long modpow(long long a, long long n, long long mod) {long long res = 1;while (n > 0) {if (n & 1) res = res * a % mod;a = a * a % mod;n >>= 1;}return res;}
//最大公約数
template<class T> inline T gcd(T x,T y){if(y==0)return x; else {return gcd(y,x%y);}}
//最小公倍数
template<class T> inline T lcm(T x,T y){return x/gcd(x,y)*y;}
//逆元
long long modinv(long long a, long long m) {long long b = m, u = 1, v = 0;while (b) {long long t = a / b;a -= t * b; swap(a, b);u -= t * v; swap(u, v);}u %= m;if (u < 0) u += m;return u;}

#define rep(i, begin_i, end_i) for (ll i = (ll)begin_i; i < (ll)end_i; i++)
//試験導入
#define irep(i, end_i, begin_i) for (ll i = (ll)begin_i-1; i >= (ll)end_i; i--)

long long INF = 1LL<<60;
int main( ){
    int res[3];
    rep(i,0,3)cin>>res[i];
    int k;
    cin>>k;
    rep(i,1,3){
        while(k>0&&res[i]<=res[i-1]){
            k--;
            res[i]*=2;
        }
    }
    bool check=true;
    rep(i,1,3){
        if(res[i]<=res[i-1])check=false;
    }
    if(check)cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}




Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <string>
#include <queue>
#include <numeric>
#include <ctype.h>
#include <limits>
#include <iomanip>

#define rep(i,n) for (int i = 0; i < n; i++)
#define all(x) (x).begin(),(x).end()
using namespace std;

typedef long long ll;

int main()
{
	/*int a, b;
	cin >> a >> b;
	int ans = max(0, a - 2 * b);
	cout << ans;*/


	int n;
	cin >> n;
	vector<int>d(n);
	rep(i, n)cin >> d[i];
	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			ans += d[i] * d[j];
		}
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
import heapq

n,m = map(int,input().split())

AB = [[int(i) for i in input().split()] for j in range(n)]

#ab.sort()

AB = sorted(AB, key=lambda x: x[0])

#print(ab)

tmp = 0
hq = []
ans = 0

for i in range(1,m+1):
    while tmp <= n-1 and AB[tmp][0] <= i:
        heapq.heappush(hq,-AB[tmp][1])
        tmp += 1
    if len(hq) > 0:
        ans += -heapq.heappop(hq)
        
print(ans)

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

long long a, b, h = 100, w = 100;
string ans[100];

void solve();

int main() {
  cin >> a >> b;
  solve();
  cout << h << " " << w << endl;
  for(int i = 0; i < h; ++i) cout << ans[i] << endl;
  return 0;
}

void solve() {
  int cnt = 1;
  for(int i = 0; i < 50; ++i)
    for(int j = 0; j < 100; ++j) ans[i] += "#";
  for(int i = 0; i < 50; ++i)
    for(int j = 0; j < 100; ++j) ans[i + 50] += ".";
  for(int i = 0; i < 50; i += 2) {
    for(int j = 0; j < 100; j += 2) {
      if(cnt == a) break;
      ans[i][j] = '.';
      ++cnt;
    }
    if(cnt == a) break;
  }
  cnt = 1;
  for(int i = 51; i < 100; i += 2) {
    for(int j = 0; j < 100; j += 2) {
      if(cnt == b) break;
      ans[i][j] = '#';
      ++cnt;
    }
    if(cnt == b) break;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0; i<(n); i++)
#define REPR(i,n) for(int i=n; i>=0; i--)
#define FOR(i,m,n) for(int i=m; i<(n); i++)
#define ALL(v) v.begin(),v.end()
#define INF 2e9
using namespace std;
typedef long long ll;
 
 
int main()
{

    int N, M, C;
    cin >> N >> M >> C;
    vector<int> B(M);
    vector<int> A(M);
    int ans = 0;

    REP(i, M) cin >> B[i];

    for (int i = 0; i < N; i++)
    {
        int aa = 0;
        REP(i, M) cin >> A[i];
        REP(i, M) aa += A[i]*B[i];
        if (aa + C > 0)
        {
            ans += 1;
        }
        
    }
     
    
    cout << ans << endl;

    return 0;
}

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

int main() {
  int a[] = {0, 1, 3, 1, 2, 1, 2, 1, 1, 2, 1, 2, 1};
  int x, y; 
  cin >> x >> y;
  if (a[x] == a[y]) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}

/* 簡易版
-5- int x , y; cin >> x >> y;
    cout << (a[x] == a[y] ? "Yes" : "No") << endl;
*/

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

int main()
{
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    M1 += H1 * 60;
    M2 += H2 * 60;
    cout << (M2 - M1 - K) <<endl;
    return 0;
}

Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <string>
#include <iomanip>
#include <cmath>
#include <queue>
#include <map>
#include <bitset>
#include <stack>

using namespace std;

void boostIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    boostIO();

    int cnt5 = 0, cnt7 = 0;
    for (int i = 0; i < 3; ++i) {
        int a;
        cin >> a;
        if (a == 5) ++cnt5;
        if (a == 7) ++cnt7;
    }

    if (cnt5 == 2 && cnt7 == 1)
        cout << "YES\n";
    else
        cout << "NO\n";
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const ll INF=1001001001;
const ll LINF=1001001001001001001;
#define overload4(_1,_2,_3,_4,name,...) name
#define rep1(n) for(ll i=0;i<(n);++i)
#define rep2(i,n) for(ll i=0;i<(n);++i)
#define rep3(i,a,b) for(ll i=(a);i<(b);++i)
#define rep4(i,a,b,c) for(ll i=(a);i<(b);i+=(c))
#define rep(...) overload4(__VA_ARGS__,rep4,rep3,rep2,rep1)(__VA_ARGS__)
#define all(x) (x).begin(),(x).end()
#define vec vector<ll>
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return 1;}return 0;}

void solve(){
    ll n;cin>>n;
    vector<vector<ll>> a(n,vec(2));
    rep(i,2)rep(j,n)cin>>a[j][i];

    vector<vec> dp(1<<n,vec(n,INF));
    rep(i,n)dp[1<<i][i]=0;
    rep(mask,1<<n){
        ll pos=__builtin_popcount(mask);
        rep(i,n){
            if((mask>>i&1)==0)continue;
            rep(j,n){
                if((mask>>j&1)==1)continue;
                ll v1=a[i][abs(pos-1-i)%2];
                ll v2=a[j][abs(pos-j)%2];
                if(v1>v2)continue;
                ll cnt=0;
                rep(k,j+1,n){
                    if((mask>>k&1)==1)cnt++;
                }
                chmin(dp[mask|1<<j][j],dp[mask][i]+cnt);
            }
        }
    }
    ll ans=INF;
    rep(i,n)chmin(ans,dp[(1<<n)-1][i]);
    cout<<(ans==INF?-1:ans)<<endl;
}

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


Measured memory_bytes: 49408
n=int(input())
s=[]
t=[]
for i in range(n):
  st,tt=input().split()
  s.append(st)
  t.append(int(tt))
x=str(input())
temp=0
ans=sum(t)
for i in range(n):
  temp=temp+t[i]
  if s[i]==x:
    break
print(ans-temp)

Measured memory_bytes: 8976
#include "bits/stdc++.h"
 
typedef long long ll;
#define int ll
#define fi first
#define se second
#define SORT(a) sort(a.begin(),a.end())
#define rep(i,n) for(int i = 0;i < (n) ; i++) 
#define REP(i,n) for(int i = 0;i < (n) ; i++) 
#define MP(a,b) make_pair(a,b)
#define pb(a) push_back(a)
#define INF LLONG_MAX/2
#define all(x) (x).begin(),(x).end()
#define debug(x) cerr<<#x<<": "<<x<<endl
#define debug_vec(v) cerr<<#v<<":";rep(i,v.size())cerr<<" "<<v[i];cerr<<endl
 
using namespace std;
int MOD = 1000000007;

signed main(){
    int n,m;

    cin >> n >> m;
    int ans = 0;

    vector<pair<int,int>> d(n);
    rep(i,n){
        int a,b;
        cin >> a >> b;
        d[i] = MP(a,b);
    }
    SORT(d);
    for(int i = 0;i < n;i++){
        if(m <= d[i].se){
            ans += m*d[i].fi;
            break;
        }else{
            ans += d[i].se * d[i].fi;
            m -= d[i].se;
        }
    }

    cout << ans << endl;

    return 0; 
}

// g++ -std=c++14 code1.cpp
// rm -r -f test;oj dl https://abc121.contest.atcoder.jp/tasks/abc121_a
// rm -r -f test;oj dl http://yahoo-procon2017-qual.contest.atcoder.jp/tasks/yahoo_procon2017_qual_c

Measured memory_bytes: 1792
#include<bits/stdc++.h>
#define XX first
#define YY second
#define pb emplace_back
#define FOR(i,a,b) for(int (i)=(a);i<(b);++(i))
#define EFOR(i,a,b) for(int (i)=(a);i<=(b);++(i))
#define rep(X,Y) for (int (X) = 0;(X) < (Y);++(X))
#define REP rep
#define rrep(X,Y) for (int (X) = (Y)-1;(X) >=0;--(X))
#define all(X) (X).begin(),(X).end()
#define eb emplace_back

using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef ll LL;
typedef pii PII;
typedef pll PLL;
const ll MOD=1e9+7;

#define rall(X) (X).rbegin(),(X).rend()
#define UNIQUE(X) (X).erase(unique(all(X)),(X).end())
#define reps(X,S,Y) for (int (X) = S;(X) < (Y);++(X))
#define rreps(X,S,Y) for (int (X) = (Y)-1;(X) >= (S);--(X))
template<class T> inline bool MX(T &l,const T &r){return l<r?l=r,1:0;}
template<class T> inline bool MN(T &l,const T &r){return l>r?l=r,1:0;}

int N;
int A[114514];
int B[114514];
vector<pii> ps;

signed main(){
  ios_base::sync_with_stdio(false);
  cout<<fixed<<setprecision(0);
  cin >> N;
  rep(i, N) {
    cin >> A[i];
  }
  map<int, int> rev;
  rep(i, N) {
    cin >> B[i];
    ps.eb(pii(A[i], B[i]));
    rev[B[i]] = A[i];
  }
  sort(A, A+N);
  sort(B, B+N);
  sort(all(ps));
  rep(i, N) {
    if (A[i] > B[i]) {
      cout << "No\n";
      return 0;
    }
  }

  int rem = N;
  bool f = false;
  vector<int> perm(N);
  vector<char> used(N);
  rrep(i, N) {
    int idx = lower_bound(B, B+N, A[i]) - B;
    if (idx != i || B[idx] == ps[i].YY) {
      cout << "Yes\n";
      return 0;
    }
    perm[i] = lower_bound(A, A+N, rev[B[idx]]) - A;
  }
  assert(rev.size() == N);  

  int v = 0;
  int cnt = 0;
  while (1) {
    used[v] = 1;
    cnt++;
    v = perm[v];
    if (used[v]) break;
  }

  if (cnt == N) {
    cout << "No\n";
  } else {
    cout << "Yes\n";
  }
  return 0;
} 


Measured memory_bytes: 8672
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <bitset>
typedef long long ll;
using namespace std;
const int maxn=100100;
char sz[maxn];
int len;
int main(){
	scanf("%s",sz+1);
	len=strlen(sz+1);
	for(int i=2;i<=len;i++){
		if(i>=3){
			int q1=sz[i]-'a'+1;
			int q2=sz[i-2]-'a'+1;
			if(q1==q2){
				printf("%d %d\n",i-2,i);
				return 0;
			}
		}
		int q1=sz[i]-'a'+1;
		int q2=sz[i-1]-'a'+1;
		if(q1==q2){
			printf("%d %d\n",i-1,i);
			return 0;
		}
	}
	printf("-1 -1\n");
	return 0;
}

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

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

Measured memory_bytes: 256
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(int i=0;i<N;++i)
typedef long long int LL;

LL X, t;

int main()
{
	in >> X >> t;
	out << std::max(X - t, 0LL) << std::endl;
	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int N=200005,mod=998244353;
inline int add(int &a,int b){a+=b;if(a>=mod)a-=mod;}
struct ro
{
	int x,d;
	bool operator<(const ro k)const
	{
		return x<k.x;
	}
}a[N];
int n,r[N],tr[N<<2],dp[N];
void update(int k,int l,int r,int x,int v)
{
	if(l==r)
	{
		tr[k]=v;
		return;
	}
	int mid=l+r>>1;
	if(x<=mid) update(k<<1,l,mid,x,v);
	else update(k<<1|1,mid+1,r,x,v);
	tr[k]=max(tr[k<<1],tr[k<<1|1]);
}
int query(int k,int l,int r,int a,int b)
{
	if(l==a&&r==b)
		return tr[k];
	int mid=l+r>>1;
	if(b<=mid) return query(k<<1,l,mid,a,b);
	else if(a>mid) return query(k<<1|1,mid+1,r,a,b);
	else return max(query(k<<1,l,mid,a,mid),query(k<<1|1,mid+1,r,mid+1,b));
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d%d",&a[i].x,&a[i].d);
	sort(a+1,a+n+1);
	r[n]=n;
	update(1,1,n,n,n);
	for(int i=n-1;i>=1;i--)
	{
		int x=i,y=n+1;
		while(y-x>1)
		{
			int m=x+y>>1;
			if(a[m].x<a[i].x+a[i].d)
				x=m;
			else
				y=m;
		}
		r[i]=x!=i?query(1,1,n,i,x):i;
		update(1,1,n,i,r[i]);
	}
	dp[1]=1;
	for(int i=1;i<=n;i++)
	{
		add(dp[i+1],dp[i]);
		add(dp[r[i]+1],dp[i]);
	}
	printf("%d\n",dp[n+1]);
	return 0;
}

Measured memory_bytes: 6528
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll mod=1000000007;
const int MAX_N = 1000;         // n の最大値
 
// nCk を取得
double nCk(int n, int k) {
double res=1.0;
for(int i=0; i<n; i++){
res*=0.5;}
for(int i=0; i<k; i++){
res*=(double)(n-i);
res/=(double)(k-i);
}
return res;}
 
int main() {
ll a[5]={};
ll f=0;
for(ll i=0; i<5; i++){
cin>>a[i];}
for(ll i=0; i<5; i++){
if(a[i]==0){
cout<<i+1<<endl;
break;}}}


Measured memory_bytes: 3548
#include <bits/stdc++.h>
using namespace std;
 
const int N = 2e5 + 5;
 
int A[N] , n;
 
int main(void) {
	scanf("%d" , &n);
	for(int i = 1;i <= n;++ i) {
		scanf("%d" , &A[i]);
		if(A[i] > A[i - 1] + 1) return 0 * puts("-1");
	}
	if(A[1]) return 0 * puts("-1");
	long long ans = 0;
	int now = n - A[n]; ans += A[n];
	for(int i = n - 1;i >= 1;-- i) 
		if(i - A[i] != now) now = i - A[i] , ans += A[i];
	cout << ans << endl;
}

Measured memory_bytes: 1024
#include<stdio.h>
int main(void){
   int i;
   int num;
   int j;
   int z = 0;
   int sum = 0;
   scanf("%d",&num);
   
   int com[num][3];
   
   for(i=0;i<num;i++){
      scanf("%d%d%d",&com[i][0],&com[i][1],&com[i][2]);
   }
   for(i=0;i<num;i++){
      for(j=1;j<3;j++){
         if(com[i][z] < com[i][j]){
            z = j;
         }
      }
      for(j=0;j<3;j++){
         if(j == z)
            continue;
         
         sum += com[i][j] * com[i][j];
      }
      if(com[i][z] * com[i][z] == sum)
         printf("YES\n");
      else
         printf("NO\n");
      z = 0;
      sum = 0;
   }
   return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
#define mins(a,b) a=min(a,b)
#define maxs(a,b) a=max(a,b)
template < typename T > std::string to_string( const T& n )
  {
    std::ostringstream stm ;
    stm << n ;
    return stm.str() ;
  }
using namespace std;

const long long INF=9000000000000000;
int main(){
  int a,b;
  cin>>a>>b;
  if(a==b){
    cout<<a+b<<endl;
  }
  else if(a>b){
    cout<<a+a-1<<endl;
  }
  else{
    cout<<b+b-1<<endl;
  }
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int dp[5][50][50][1 << 12];
int H, W, K;
char mas[50][50];
int dy[] = { 0, 1, 0, -1}, dx[] = { 1, 0, -1, 0};
int mask;
 
int getdir(int bit, int i){
  return bit >> (i << 1) & 3;
}
bool isover(int y, int x){
  return y < 0 || y >= H || x < 0 || x >= W;
}
int main()
{
  cin >> H >> W >> K;
  mask = (1 << (K * 2 * 2)) - 1;
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> mas[i][j];
    }
  }
  fill_n( ***dp, 5 * 50 * 50 * 1 << 12, -1);
  dp[K][0][0][0] = 0;

  for(int mul = K ; mul >= 0; mul--){
    for(int y = 0; y < H; y++){
      for(int x = 0; x < W; x++){
        for(int bit = 0; bit < 1 << (K * 4) ; bit++){ // 前の街
          if(dp[mul][y][x][bit] == -1 || mas[y][x] == '#') continue;
          int my = y, mx = x, cost = 0;
          bool flag = false;
          if(mas[y][x] != '.'){
            for(int i = 0; i < 2 * K; i++){
              my -= dy[getdir( bit, i)];
              mx -= dx[getdir( bit, i)];
              if(my == y && mx == x){
                flag = true;
                break;
              }
            }
            if(!flag) cost = mas[y][x] - '0';
          }
          for(int i = 0; i < 4; i++){
            int ny = y + dy[i], nx = x + dx[i];
            if(ny < 0 || ny >= H || nx < 0 || nx >= W || mas[ny][nx] == '#') continue;
            if(mul == 0 && i >= 2) break;
            int& next = dp[mul - (i >= 2)][ny][nx][(bit << 2 | i) & mask];
            next = max( next, dp[mul][y][x][bit] + cost);
          }
        }
      }
    }
  }
  int ret = 0;
  for(int i = 0; i < 1 << (4 * K) ; i++){
    ret = max( ret, dp[0][H - 1][W - 1][i]);
  }
  cout << ret << endl;
  return 0;
}

Measured memory_bytes: 201160
///
// File:  b.go
// Author: ymiyamoto
//
// Created on Sun May  6 11:55:12 2018
//
package main

import (
	"fmt"
)

var N, A, B, C, D int

func main() {
	fmt.Scan(&N, &A, &B, &C, &D)

	for m := 0; m < N; m++ {
		if (N-1-m)*C-m*D <= B-A && B-A <= (N-1-m)*D-m*C {
			fmt.Println("YES")
			return
		}
	}

	fmt.Println("NO")
}


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

int main()
{

     int i,j,l;
   char str[110];
   scanf("%s",str);
   l=strlen(str);
   sort(str,str+l);
   int a[100];
   a[0]=1;
   for(i=0,j=0;i<l-1;i++)
   {

       if(str[i]==str[i+1])
       {
           a[j]=a[j]+1;
       }
        else
        {
            j=j+1;
            a[j]=1;
        }



   }
   for(i=0;i<=j;i++)
   {
       if(a[i]%2!=0)
       {
           printf("No\n");
           return 0;
       }
   }

    printf("Yes\n");

   return 0;


}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
bool huiwen(string s)
{   int n=s.size();
   for(int i=0;i<n/2;i++)
     if(s[i]!=s[n-i-1]) return false;
     return true;
}
int main ()
{   string s;
    cin>>s;
    int n=s.size();
    string a=s.substr(0,(n-1)/2);
    string b=s.substr((n+1)/2,(n-1)/2);
     // cout<<a<<endl;
	 // cout<<b;
    if(huiwen(s)&&huiwen(a)&&huiwen(b))
      printf("Yes");
      else
      printf("No");
}

Measured memory_bytes: 256
#include<iostream>
#include<cmath>

using namespace std;

int main(){
	int e;
	while(cin >> e,e){
		int minn = e;
		int res;
		for(int y=0;y<=e/2;y++){
			if(y*y > e) break;
			for(int z=0;z<=e/3;z++){
				if(z*z*z+y*y > e) break;
				int x = e - y*y - z*z*z;
				res = x + y + z;
				if(res < minn){
					minn = res;
				}
			}
		}
		cout << minn << endl;
	}
	return 0;
}

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

namespace AtCoder.Abc
{
    class QuestionB
    {
        public static void Main(string[] args)
        {
            var sw = new System.IO.StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false };
            Console.SetOut(sw);

            // 整数配列の入力
            var inputLongArray = Console.ReadLine().Split(' ').Select(i => long.Parse(i)).ToArray();
            var x = inputLongArray[0];
            var y = inputLongArray[1];

            var ans = (y - (2 * x)) / 2m;

            string result = "No";
            if (ans >= 0 && ans <= x && ans == (long)ans)
            {
                result = "Yes";
            }

            Console.WriteLine(result);

            Console.Out.Flush();
        }
    }
}


Measured memory_bytes: 28236
#include <iostream>
#include <map>
#include <algorithm>    
#include <vector>       
#include <set>
#include <utility>  
#include <cstring>
#include <stdio.h>
#include <limits.h>
#include <queue>
#include <algorithm> 
#define MAX_DOUBLE  40000000000.0 
#include <math.h> 
#include <unistd.h>

using namespace std;

int res[3001][3001];
int dir[3001][3001];

int main(){
	string s,t;
	cin>>s>>t;
	
	
	int s_len = s.size();
	int t_len = t.size();
	
	for(int i = 0; i <= s_len; i++){
		for(int j = 0; j <=t_len; j++){
			if(i == 0 || j == 0){
				res[i][j] = 0;
			}
			else{
				
				if(s[i-1] == t[j-1]){
					res[i][j] = res[i-1][j-1] + 1;
					dir[i][j] = 0;
				} else if(res[i-1][j] >= res[i][j-1] ){
					res[i][j] = res[i-1][j];
					dir[i][j] = -1;
				} else if(res[i-1][j] < res[i][j-1] ){
					res[i][j] = res[i][j-1];
					dir[i][j] = 1;
				}			
				
			}
		}
	}
	
	int i = s_len;
	int j = t_len;
	
	string ans = "";

	while(i > 0 && j > 0){
		if(dir[i][j] == 0){
			ans=s[i-1]+ans;
			i--;
			j--;
		}else if(dir[i][j] == -1){
			i--;
		}else if(dir[i][j] == 1){
			j--;
		}
	}
	cout<<ans;
}


Measured memory_bytes: 70656
n,y = input().split()
n = int(n)
yen = int(y)

for x in range(n+1):
  for y in range(n+1):
    z = (yen - 10000*x - 5000*y)/1000
    if z>=0:
      z = int(z)
      if (x+y+z)==n:
        print(x,y,z)
        exit()

print("-1 -1 -1")

Measured memory_bytes: 3188
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x3f3f3f3f
#define N 100010
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
int n,k,a[N];
ll sum1[N],sum2[N],ans=0;//sum1[i],所有正数得前缀和 sum2[i],所有数得前缀和。
int main(){
//	freopen("a.in","r",stdin);
	n=read();k=read();
	for(int i=1;i<=n;++i){
		a[i]=read();sum2[i]=sum2[i-1]+a[i];sum1[i]=sum1[i-1]; 
		if(a[i]>0) sum1[i]+=a[i];
	}for(int i=1;i+k-1<=n;++i){//枚举一段长为k的区域来中转 
		ll res=sum1[n]-(sum1[i+k-1]-sum1[i-1]);
		if(sum2[i+k-1]-sum2[i-1]>0) res+=sum2[i+k-1]-sum2[i-1];
		ans=max(ans,res);
	}printf("%lld\n",ans);
	return 0;
}

Measured memory_bytes: 2304
n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]
count = 0
 
for x in edges:
    l = list(range(n))
    for y in edges:
        if y != x:
            l = [l[y[0]-1] if l[i] == l[y[1]-1] else l[i] for i in range(n)]
    if len(set(l)) != 1:
        count += 1
 
print(count)

Measured memory_bytes: 3064
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int n;
int v[N];
int dp[N];
int main() {
	scanf("%d", &n);
	for(int i = 0; i < n; ++i) scanf("%d", &v[i]);
	for(int i = n - 2; i >= 0; --i) {
		if(i == n - 2) {
			dp[i] = abs(v[i] - v[i + 1]);
		} else {
			dp[i] = min(
				abs(v[i] - v[i + 1]) + dp[i + 1],
				abs(v[i] - v[i + 2]) + dp[i + 2]
			);
		}
	}
	printf("%d\n", dp[0]);
	return 0;
}


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

typedef long long ll;
constexpr double PI = 3.141592653589793;
constexpr ll INF = 1e18 + 10;
template <class T>
bool chmax(T &a, const T &b)
{
    if (a < b)
    {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b)
{
    if (b < a)
    {
        a = b;
        return 1;
    }
    return 0;
}

using namespace std;
//    cout << setprecision(20) << ans << "\n";

vector<pair<ll, ll>> primeFactorize(ll N)
{
    vector<pair<ll, ll>> res;
    for (ll a = 2; a * a <= N; ++a)
    {
        if (N % a != 0)
            continue;
        ll ex = 0;

        while (N % a == 0)
        {
            ++ex;
            N /= a;
        }
        res.push_back({a, ex});
    }

    if (N != 1)
        res.push_back({N, 1});
    return res;
}

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

    int n;
    cin >> n;
    vector<int> count(100010);
    ll sum = 0;
    for (int i = 0; i < n; i++)
    {
        int a;
        cin >> a;
        count[a]++;
        sum += a;
    }

    int q;
    cin >> q;

    for (int i = 0; i < q; i++)
    {
        int b, c;
        cin >> b >> c;
        int diff = c - b;
        sum += diff * count[b];
        count[c] += count[b];
        count[b] = 0;
        cout << sum << "\n";
    }

    return 0;
}


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

int main() {
	int D, N;
	cin >> D >> N;
	if (!D) {
		if (N == 100)
			cout << 101 << endl;
		else
			cout << N << endl;
	} else if (D == 1) {
		int n = 100*N;
		if (n == 10000)
			cout << 10100 << endl;
		else
			cout << n << endl;
	} else {
		int n = 100*100*N;
		if (n == 100*100*100) 
			cout << 1010000 << endl;
		else
			cout << n << endl;
	}
}


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

static const int alternatives[24][6] = {
    {0, 1, 2, 3, 4, 5},
    {0, 2, 4, 1, 3, 5},
    {0, 3, 1, 4, 2, 5},
    {0, 4, 3, 2, 1, 5},
    {1, 0, 3, 2, 5, 4},
    {1, 2, 0, 5, 3, 4},
    {1, 3, 5, 0, 2, 4},
    {1, 5, 2, 3, 0, 4},
    {2, 0, 1, 4, 5, 3},
    {2, 1, 5, 0, 4, 3},
    {2, 4, 0, 5, 1, 3},
    {2, 5, 4, 1, 0, 3},
    {3, 0, 4, 1, 5, 2},
    {3, 1, 0, 5, 4, 2},
    {3, 4, 5, 0, 1, 2},
    {3, 5, 1, 4, 0, 2},
    {4, 0, 2, 3, 5, 1},
    {4, 2, 5, 0, 3, 1},
    {4, 3, 0, 5, 2, 1},
    {4, 5, 3, 2, 0, 1},
    {5, 1, 3, 2, 4, 0},
    {5, 2, 1, 4, 3, 0},
    {5, 3, 4, 1, 2, 0},
    {5, 4, 2, 3, 1, 0},
};

bool matched_dices(int *dice1, int *dice2)
{
    bool matched = false;
    for (int i = 0; i < 24 && !matched; ++i)
    {
        int j;
        for (j = 0; j < 6; ++j)
        {
            if (dice2[alternatives[i][j]] != dice1[j])
            {
                break;
            }
        }
        matched = (j == 6);
    }
    return matched;
}

int main(int argc, char *argv[])
{
    int n;
    scanf("%d", &n);
    int dices[100][6];
    for (int i = 0; i < n; ++i)
    {
        for (int *elm = dices[i], *const end = elm + 6; elm != end; ++elm)
        {
            scanf("%d", elm);
        }
    }
    bool matched = false;
    for (int i = 0; i < n - 1 && !matched; ++i)
    {
        for (int j = i + 1; j < n && !matched; ++j)
        {
            matched = matched_dices(dices[i], dices[j]);
        }
    }

    printf("%s\n", matched ? "No" : "Yes");
    return 0;
}



Measured memory_bytes: 2064
#include<iostream>
#include<algorithm>
#include<numeric>
using namespace std;
int main(){
int n,m;
cin >> n >> m;
int a[m];
for(int i = 0;i < m;i++){
	cin >> a[i];
	}
int s = accumulate(a,a+m,0);
if(n < s){
	cout << "-1" << '\n';
	}
else{
	cout << n - s << '\n';
	}
return 0;
}

Measured memory_bytes: 3648
char W[9],V[9];Z[2*4],S,N,T,P,M;main(){
	int i,j,k,l,r,d;
	for(;scanf("%d%d%d%s%s%d%d",&S,&N,&T,W,V,&P,&M),S;printf("%.10f\n",1-pow(1-1.0/P,N*r))){
		memset(Z,0,sizeof(Z));
		l=*W=='A'?2:1;
		d=24*60*(*W=='A'?1:7);
		if(*V=='A')for(i=0;i<l;i++)Z[i*4]=Z[i*4+1]=Z[i*4+2]=Z[i*4+3]=1;
		if(*V=='D')for(i=0;i<l;i++)Z[i*4+1]=Z[i*4+2]=1;
		if(*V=='N')for(i=0;i<l;i++)Z[i*4]=Z[i*4+3]=1;
		for(r=j=0;j<24*60;r=r>l?r:l,j++)for(k=j,l=i=0;i<M;i++){
			if(k<24*60)l+=Z[(k+S)%(2*24*60)/360]&Z[k/360];
			k=(k+T)%d;
		}
}exit(0);}

Measured memory_bytes: 692
#include<bits/stdc++.h>
using namespace std;
signed main(){
  cin.tie(NULL);
  ios::sync_with_stdio(false);
  long long a,b,c,i,n[5];
  for(i=0;i<3;i++){
    cin>>n[i];
  }
  sort(n,n +3);
  for(i=0;i<2;i++){
    cout<<n[i]<<" ";
  }
  cout<<n[2]<<'\n';
  return(0);
}



Measured memory_bytes: 3180
import java.math.BigDecimal;
import java.util.*;
import java.util.stream.Collectors;

public class Main {

    private static int MOD = 1_000_000_007;

    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);
        solve(scanner);
    }


    // int N = Integer.parseInt(scanner.nextLine());
    // int N = scanner.nextInt(), M = scanner.nextInt();
    // scanner.nextLine();
    // int[] n = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
    static void solve(Scanner scanner) {
        int N = scanner.nextInt(), M = scanner.nextInt();
        scanner.nextLine();
        int[] n = Arrays.stream(scanner.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int[] available = new int[10];
        for (int i: n) {
            int use = 5;
            if (i == 1) {
                use = 2;
            }
            if (i == 4) {
                use = 4;
            }
            if (i == 6 || i == 9) {
                use = 6;
            }
            if (i == 7) {
                use = 3;
            }
            if (i == 8) {
                use = 7;
            }
            available[use] = Math.max(available[use], i);
        }

        BigDecimal[] dp = new BigDecimal[N + 1];
        Arrays.fill(dp, BigDecimal.valueOf(-1));
        dp[0] = BigDecimal.ZERO;
        for (int i = 1; i < N + 1; i++) {
            for (int j = 0; j < 10; j++) {
                if (available[j] > 0 && i >= j && dp[i - j].compareTo(BigDecimal.ZERO) >= 0) {
                    BigDecimal prev =  dp[i - j].multiply(BigDecimal.valueOf(10)).add(BigDecimal.valueOf(available[j]));
                    if (dp[i].compareTo(prev) < 0) {
                        dp[i] = prev;
                    }
                }
            }
        }
        System.out.println(dp[N]);
    }

}


Measured memory_bytes: 100268
/*
これを入れて実行
g++ code.cpp
./a.out
 */
 
#include <iostream>
#include <stdio.h>
#include <vector>
#include <string>
#include <queue>
#include <deque>
#include <algorithm>
#include <utility>
#include <set>
#include <map>
#include <cmath>
#include <math.h>
#include <tuple>
#include <iomanip>
#include <bitset>
 
using namespace std;
typedef long long ll;
typedef long double ld;
 
int dy4[4] = {-1, 0, +1, 0};
int dx4[4] = {0, +1, 0, -1};
int dy8[8] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dx8[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
const long long INF = 1LL << 60;
const ll MOD = 1e9 + 7;
 
bool greaterSecond(const pair<int, int>& f, const pair<int, int>& s){
    return f.second > s.second;
}
 
ll gcd(ll a, ll b){
	if (b == 0)return a;
	return gcd(b, a % b);
}
 
ll lcm(ll a, ll b){
    return a / gcd(a, b) * b;
}
 
ll nCr(ll n, ll r){
    if(r == 0 || r == n){
        return 1;
    } else if(r == 1){
        return n;
    }
    return (nCr(n - 1, r) + nCr(n - 1, r - 1));
}
 
ll nPr(ll n, ll r){
    r = n - r;
    ll ret = 1;
    for (ll i = n; i >= r + 1; i--) ret *= i;
    return ret;
}
 
//-----------------------ここから-----------

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

    if(500 * k >= x){
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
}

Measured memory_bytes: 256
// #define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 0; i < n; ++i)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x) cout << #x << ' ' << '=' << ' ' << (x) << endl;
#define fs first
#define sc second
#define pb push_back
#define eb emplace_back
typedef long long ll;
typedef pair<ll, ll> P;
typedef tuple<ll, ll, ll> T;
typedef vector<ll> vec;
typedef vector<P> pvec;
typedef vector<vector<ll>> vvec;
typedef vector<vector<P>> pvvec;
typedef priority_queue<ll> PQI;
typedef priority_queue<P> PQP;
typedef priority_queue<ll,vector<ll>,greater<ll>> PQIG;
typedef priority_queue<P,vector<P>,greater<P>> PQPG;
const vector<int> dx = {0, -1, 0, 1, 1, 1, -1, -1};
const vector<int> dy = {1, 0, -1, 0, 1, -1, 1, -1};
constexpr int MOD = (1000000007);
// const int MOD = (998244353);
// const int INF = (1 << 30); // 1073741824
const int INF = (1LL << 60); // 1152921504606846976
const double EPS = (1 >> 30);
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b; return 1;} return 0;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b; return 1;} return 0;}
template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; }

int n;
vec a,b;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(15);
    //---------------------------------------------
    
    cin>>n;
    a.resize(n);
    b.resize(n);
    int e=0,s=0,l=0;
    int sum=0;
    rep(i,n){
        cin>>a[i]>>b[i];
        if(a[i]==b[i]) e++;
        sum+=a[i];
    }
    if(e==n){
        cout<<0<<endl;
        return 0;
    }

    rep(i,n){
        if(a[i]<b[i]){
            l+=b[i]-a[i];
        }
    }
    pvec x;
    ll d=INF;
    rep(i,n){
        if(a[i]>b[i]){
            x.eb(b[i],a[i]);
            chmin(d,b[i]);
        }
    }
    cout<<sum-d<<endl;
    
}

Measured memory_bytes: 1024
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define MOD 1000000007
#define INF (1<<30)
#define LINF (lint)(1LL<<56)
#define endl "\n"
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define reprev(i,n) for(int (i)=(n-1);(i)>=0;(i)--)
#define Flag(x) (1<<(x))
#define Flagcount(x) __builtin_popcount(x)
#define pint pair<int,int>
#define pdouble pair<double,double>
#define plint pair<lint,lint>
#define fi first
#define se second
typedef long long lint;
int dx[8]={1,1,0,-1,-1,-1,0,1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

int main(void){
    lint N,K;
    cin >> N >> K;
    lint ans=0,now=1;
    while(N>=now){
        ans++;
        now*=K;
    }
    cout << ans << endl;
}

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

int main(){
	int InnNum; int DayNum;
	cin >> InnNum >> DayNum;
	vector<int> DistanceCollection;
	for (int i = 0; i < InnNum - 1; ++i){
		int D;
		cin >> D;
		DistanceCollection.push_back(D);
	}
	vector<int> WalkNumCollection;
	for (int i = 0; i < DayNum; ++i){
		int N;
		cin >> N;
		WalkNumCollection.push_back(N);
	}
	vector<int> WalkTimeCollection;
	WalkTimeCollection.resize(InnNum - 1);
	fill(WalkTimeCollection.begin(), WalkTimeCollection.end(), 0);
	auto Iterator = WalkTimeCollection.begin();
	for (int i = 0; i < DayNum; ++i){
		const int aWalkNum = WalkNumCollection[i];
		if (aWalkNum>0){
			for_each(Iterator, Iterator + aWalkNum, [](int& n){return n++; });
		}
		else {
			for_each(Iterator+aWalkNum, Iterator, [](int& n){return n++; });
		}
		Iterator += aWalkNum;
	}
	int a=0;
	for (int i = 0; i < InnNum-1; ++i){
		a += WalkTimeCollection[i] * DistanceCollection[i];
		a = a % 100000;
	}
	cout << a << endl;
	return 0;
}

Measured memory_bytes: 2460
#include <iostream>
#include <string>

using namespace std;


int main(){
    string s;
    cin >> s;
    int cost = 700;
    for (int i = 0; i < 3; i++) {
        if(s[i] == 'o') {
            cost = cost + 100;
        }
    }
    cout << cost << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
typedef long long LL;
const int e[40]={0,1,1,2,2,2,3,3,3,3,4,4,4,4,4,5,5,5,5,5,
                 5,6,6,6,6,6,6,6,7,7,7,7,7,7,7,7,8,8,8,8};
LL IN(void)
{
  LL x=0;short f=0,c=getchar();while(c<48||c>57){f^=c==45,c=getchar();}
  while(c>47&&c<58){x=x*10+c-48,c=getchar();}return f?-x:x;
}
LL BinaryModularPower(LL x,LL y,LL mod)
{int z=y&1;LL p=x,v=1;while(y){if(y&1){v=(v*p)%mod;}p=(p*p)%mod;y>>=1;}return v;}
int Prime(LL a,LL b,LL x,LL mod)
{
  LL y=BinaryModularPower(a,b,x);
  if(y==1)return 1;
  while(x){if(y+1==mod){return 1;}y=(y*y)%mod;x--;}
  return 0;
}
int main(void)
{
  LL a=0,i=3,p=2,N=IN();
  if(N==1)return puts("0"),0;
  while(p*p<N)
  {
    int count=0;LL y=i>>1,loop=1;
    while(!(N%p)){count++,N/=p;}a+=e[count];
    if(i==3||i==5||i==7||i==11){p++;continue;}
    while(!(y&1)){y>>=1;loop++;}
    if(Prime(2,y,loop,i)&&Prime(3,y,loop,i)&&
       Prime(5,y,loop,i)&&Prime(7,y,loop,i)&&Prime(11,y,loop,i)){p++;}
    i+=2;
  }
  if(N>1){a++;}return printf("\n%lld\n",a),0;
}

Measured memory_bytes: 1592
#include <stdio.h>

int main() {
	int a, b, c, d, e, k, check = 0;

	scanf("%d", &a);
	scanf("%d", &b);
	scanf("%d", &c);
	scanf("%d", &d);
	scanf("%d", &e);
	scanf("%d", &k);

	if ((b - a) > k)
		check++;
	if ((c - a) > k)
		check++;
	if ((d - a) > k)
		check++;
	if ((e - a) > k)
		check++;
	if ((e - b) > k)
		check++;
	if ((e - c) > k)
		check++;
	if ((e - d) > k)
		check++;

	if (check == 0)
		printf("Yay!\n");
	else
		printf(":(\n");

	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)   FOR(i,0,n)
#define pb emplace_back
typedef long long ll;
typedef pair<int,int> pint;

double x[101],y[101],z[101],r[101];
const int MAX_N=101;
struct edge{
    int src,dst;
    double cost;
    edge(int src,int dst,double cost):
    src(src),dst(dst),cost(cost){}
    };
bool operator < (const edge &m,const edge &f){
    return m.cost!=f.cost?m.cost<f.cost:
    m.src!=f.src?m.src<f.src:m.dst<f.dst;
}
struct UnionFind{
    int par[MAX_N],rank[MAX_N]; 
    void init(int n){
        for (int i=0;i<n;i++){par[i]=i;rank[i]=0;}
    } 
    int find(int x){
        if (x==par[x]) return (x);
        return (par[x]=find(par[x]));
    }
    void unite(int x, int y){
        x=find(x);y=find(y);       
        if(x==y) return;
        if(rank[x]<rank[y]){par[x]=y;}
        else{par[y]=x;if(rank[x]==rank[y]) rank[x]++;}
    } 
    bool same(int x, int y){return (find(x) == find(y));} 
};
vector<edge> ve;
int n;
double kruskal(){
    sort(ve.begin(),ve.end());
    UnionFind uf;
    uf.init(n);
    double res=0;
    rep(i,ve.size()){
        edge m=ve[i];
        if(!uf.same(m.src,m.dst)){
            uf.unite(m.src,m.dst);
            res +=m.cost;
        }
    }
    return res;
}
int main(){
    while(cin>>n,n){
        ve.clear();
        rep(i,n) cin>>x[i]>>y[i]>>z[i]>>r[i];
        rep(i,n)FOR(j,i+1,n){
            double tx=x[i]-x[j],ty=y[i]-y[j],tz=z[i]-z[j];
            double tr=r[i]+r[j];
            ve.pb(edge(i,j,max(0.0,sqrt(tx*tx+ty*ty+tz*tz)-tr)));
        }
        cout<<fixed<<setprecision(3)<<kruskal()<<endl;
    }
    return 0;
}


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

vector<int> to[100005];
int n;

vector<int> dist;
void dfs(int v, int d=0, int p=-1) {
  dist[v] = d;
  for (int u : to[v]) {
    if (u == p) continue;
    dfs(u,d+1,v);
  }
}
vector<int> calcDist(int s) {
  dist = vector<int>(n);
  dfs(s);
  return dist;
}

int main() {
  cin >> n;
  int s, t;
  cin >> s >> t;
  --s; --t;
  rep(i,n-1) {
    int a, b;
    cin >> a >> b;
    --a; --b;
    to[a].push_back(b);
    to[b].push_back(a);
  }

  vector<int> distS = calcDist(s);
  vector<int> distT = calcDist(t);

  int mx = 0;
  rep(i,n) {
    if (distS[i] < distT[i]) {
      mx = max(mx, distT[i]);
    }
  }
  int ans = mx-1;
  cout << ans << endl;
  return 0;
}

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

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

    int left = 1;
    int right = N;
    int L, R;
    for (int i = 0; i < M; i++)
    {
        cin >> L >> R;
        left = max(left, L);
        right = min(right, R);
    }
    cout << max(0, right - left + 1) << endl;
}


Measured memory_bytes: 256
num = int(input())
shutu = 0
if 400 <= num <= 599:
  shutu = 8
elif 600 <= num <= 799:
  shutu = 7
elif 800 <= num <= 999:
  shutu = 6 
elif 1000 <= num <= 1199:
  shutu = 5  
elif 1200 <= num <= 1399:
  shutu = 4
elif 1400 <= num <= 1599:
  shutu = 3 
elif 1600 <= num <= 1799:
  shutu = 2 
elif 1800 <= num <= 1999:
  shutu = 1
else:
  shutu = 0
print (shutu)

Measured memory_bytes: 9188
#include<cstdio>
#include<cmath>
#define int long long
using namespace std;
int gcd(int x,int y)
{	
	int z=y;
	while(x%y!=0)
	{
		z=x%y;
		x=y;
		y=z;	
	}
	return z;
}
signed main()
{
	int a,b;
	scanf("%lld%lld",&a,&b);
	int qwq=gcd(a,b);
	int qvq=sqrt(qwq)+1;
	int ans=0;
    for(int i=2;i<=qvq;i++)
    {
    	if(qwq%i==0)
    	{
    		ans++;
    		while(qwq%i==0)
    	    qwq/=i;
    	}	
    }
    printf("%lld",ans+1+(qwq>1));
	return 0;
}

Measured memory_bytes: 128
import Control.Monad
import Data.List

main :: IO ()
main = do
  n <- (readLn :: IO Int)
  replicateM_ n $ do
    input <- getLine
    let a:b:c:[] = sort $ map read $ words input :: [Int]
    putStrLn $ if (c ^ 2) == (a ^ 2) + (b ^ 2)
                  then "YES"
                  else "NO"

Measured memory_bytes: 4128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int x;
const int maxn=1e6+7;
int vis[maxn],p[maxn];
int cnt=0;
void prime(){
    memset(vis,0,sizeof vis);
    memset(p,0,sizeof p);
    for(int i=2;i<=maxn;i++){
        if(!vis[i]) p[cnt++]=i;
        for(int j=2*i;j<=maxn;j+=i){
            vis[j]=1;
        }
    }
    
}
int main()
{
    prime();
    cin>>x;
    for(int i=0;i<cnt;i++){
        if(p[i]>=x){
            cout<<p[i];
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 8064
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#include <map>
using namespace std;
int a[100050];
bool vis[100050];
int main(){
	int n,m,x,sum1,sum2;
	sum1=0;
	sum2=0;
	memset(vis,0,sizeof(vis));
	scanf("%d%d%d",&n,&m,&x);
	for(int i=1;i<=m;i++){
		scanf("%d",&a[i]);
		vis[a[i]]=1;
	}
	for(int i=x;i>=1;i--){
		if(vis[i]==1) sum1++;
	}
	for(int i=x;i<=n;i++){
		if(vis[i]==1) sum2++;
	}
	printf("%d\n",min(sum1,sum2));
}

Measured memory_bytes: 384
fun main(args: Array<String>) {
    val (N, K) = listOfInt()
    val M = (N - 1) * (N - 2) / 2
    if (K > M) {
        println(-1)
        return
    }
    val ans = mutableListOf<Pair<Int, Int>>()
    repeat(N-1) { ans.add(Pair(it + 1, N)) }
    val L = M - K
    var edge = mutableListOf<Pair<Int, Int>>()
    for (n in 0 until N - 1) for (m in 0 until n) edge.add(Pair(n + 1, m + 1))
    repeat(L) { ans.add(edge[it]) }
    println("${ans.count()}")
    ans.forEach { println("${it.first} ${it.second}") }
}

fun next() = readLine()!!
fun listOfString() = next().split(" ")
fun listOfInt() = listOfString().map { Integer.parseInt(it) }


Measured memory_bytes: 38636
N,M = list(map(int, input().split()))
A = list(map(int, input().split()))
'''
まず一つで考えてみよう
並び替えて、順々に行くのが最適。
方向性を決めることはできるだろうか。
次に二つの場合、どうするか


'''
if len(A) <= N:
    print(0)
    exit(0)

A.sort()
#print(A)
result =[]

for i,a in enumerate(A):
    if i == 0:
        continue
    result.append(A[i]-A[i-1])

result.sort(reverse=True)

print(sum(result[N-1:]))


Measured memory_bytes: 13960