akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;


int main()
{
	int a, b;
	cin >> a >> b;
	int s = (a-b);
	if( s < 0) s *= -1;
	//cout << s << endl;
	int a_h = 0;
	for( int i = 1; i < s ; i++ ) {
		a_h += i;
	}
	cout << (a_h -a) << endl;
}


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

#define fr(i,b,e) for(int i=(b); i!=(e); ++i)
#define rep(i,e) for(int i=0; i!=(e); ++i)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long int li;
typedef long long int ll;
using graph = vector<vector<int>>;
using edgedp = vector<vector<pair<int,ll>>>;
constexpr int INF=1000000;
//constexpr int MOD=998244353;
constexpr int MOD=1e9+7;

int calc_pw(ll n, ll p){
    if(n/p==0){
        return 0;
    }else{
        return calc_pw(n/p,p)+1;
    }
}


int main(void){
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int N;
    cin >> N;
    set<string> s;
    string str;
    rep(i,N){
        cin >> str;
        s.insert(str);
    }
    cout << s.size() << endl;
}   




Measured memory_bytes: 19248
#include<iostream>
#include<cmath>
#include<numeric>
#include<functional>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<n;i++)
#define ll long long
#define INF 2147483647
using namespace std;
using Graph=vector<vector<int>>;

ll RepSq(ll a,ll n,ll mod){
  if(n==0){
    return 1;
  }else if(n%2!=0){
    return (a*RepSq(a,n-1,mod))%mod;
  }else{
    ll x=RepSq(a,n/2,mod);
    return (x*x)%mod;
  }
}

int main(){
  ll n; cin>>n;
  ll mod=1000000007;
  cout<<(RepSq(10,n,mod)+RepSq(8,n,mod)+2*(mod-RepSq(9,n,mod)))%mod;
}


Measured memory_bytes: 3608
import java.util.*;
import java.io.*;
class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    String S = sc.next();
    String T = sc.next();
    int cnt = 0;
    char Sc[] = S.toCharArray();
    char Tc[] = T.toCharArray();
    for(int i = 0, len = S.length(); i < len; i++){
      if(Sc[i] != Tc[i]){
        cnt++;
      }
    }
    PrintWriter out = new PrintWriter(System.out);
    out.print(cnt);
    out.flush();
  }
}

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

using namespace std;

/* g++ -g -fsanitize=address -lasan -std=c++11 -Dfoo_ */

/* freopen("input.txt", "rt", stdin); */
/* freopen("output.txt", "wt", stdout); */

#define ALL(c)          (c).begin(), (c).end()
#define ALLR(c)         (c).rbegin(), (c).rend()
#define FOR(i,a,b)      for (int i=(a); i < (b); ++i)
#define FORR(i,a,b)     for (int i=(a); i > (b); --i)
#define FOR_ALL(i,c)    for (__typeof((c).begin()) i=(c).begin();   \
                             i != (c).end(); ++i)
#define FOR_ALLR(i,c)   for (__typeof((c).rbegin()) i=(c).rbegin(); \
                             i != (c).rend(); ++i)
#define SZ(array)       (sizeof(array)/sizeof(array[0]))
#define lc(x)           (x<<1)     /* 2*x */
#define rc(x)           (x<<1 | 1) /* 2*x+1 */
#define lowbit(x)       (x & (-x)) /* 0b10100 -> 0b100 */

typedef long long       LL;
typedef map<int,int>    MII;
typedef pair<int,int>   PII;
typedef set<int>        SI;
typedef vector<bool>    VB;
typedef vector<double>  VD;
typedef vector<int>     VI;
typedef vector<string>  VS;

/* check if a key is in container C */
template <class C>
inline bool in_(const typename C::key_type& k, const C& A)
{ return A.find(k) != A.end(); }
inline bool in_(const string& s, const string& S)
{ return S.find(s) != string::npos; }

const int inf = 1e9;
const int mod = 1e9+7;
const int maxn = 2002;
int A[maxn][maxn], sum[4][maxn][maxn];

int main()
{
#ifdef foo_
    freopen("foo", "rt", stdin);
#endif
    ios::sync_with_stdio(false);
    int h,w;
    while (cin >> h >> w) {
        FOR(i,1,h+1) FOR(j,1,w+1) {
            char ch; cin >> ch;
            if (ch == '#')
                A[i][j] = 0;
            else
                A[i][j] = 1;
        }
        memset(sum,0,sizeof(sum));
        FOR(i,1,h+1) FOR(j,1,w+1) if (A[i][j])
            sum[0][i][j] = sum[0][i][j-1] + 1;
        FOR(i,1,h+1) FORR(j,w,0) if (A[i][j])
            sum[1][i][j] = sum[1][i][j+1] + 1;
        FOR(j,1,w+1) FOR(i,1,h+1) if (A[i][j])
            sum[2][j][i] = sum[2][j][i-1] + 1;
        FOR(j,1,w+1) FORR(i,h,0) if (A[i][j])
            sum[3][j][i] = sum[3][j][i+1] + 1;
        int ans = 0;
        FOR(i,1,h+1) FOR(j,1,w+1) if (A[i][j]) {
            const int a = sum[0][i][j-1] + sum[1][i][j+1];
            const int b = sum[2][j][i-1] + sum[3][j][i+1];
            ans = max(ans, a+b+1);
        }
        cout << ans << endl;
    }
    return 0;
}


Measured memory_bytes: 78592
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i,n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
const long long INF = 1LL << 60;
const int MOD = 1000000007;
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; }
signed main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, k; cin>>n>>k;
    vector <int> a(n);
    rep(i,n) cin>>a[i];
    int ans = INF;
    rep(i,n-k + 1){
        //cout<<a[i]<<' '<<a[i+k-1]<<endl;
        if(a[i] * a[i+k-1]  >=0){
            chmin(ans,max(abs(a[i]), abs(a[i + k - 1])));
        }else{
            int a1 = abs(a[i]), a2 = abs(a[i + k - 1]);
            chmin(ans ,2 * min(a1,a2) + max(a1,a2));
        }
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define per(i,n) for (int i = (n)-1; i >=0; --i)
using namespace std;
using ll = long long;
using vi = vector<int>;
using vv = vector<vi>;

int main(){
    int a,b,c;cin>>a>>b>>c;
    
    int cap = max(a, max(b,c));
    int sum = a+b+c;
    
    if((sum-cap)%2==0){
        cout << (3*cap-sum)/2 << endl;
    }else{
        cout << (3*cap+3-sum)/2 << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(){


 int x[10],a=0,b=0,i;

 for(i=1;i<=3;i++){
    scanf("%d",&x[i]);

    if(x[i]==5){
        a++;
    }
     else if(x[i]==7){
        b++;
    }
}
    if(a==2&&b==1){
        printf("YES");
    }
     else {
        printf("NO");
    }

   return 0;
}


Measured memory_bytes: 1712
/*
* じょえチャンネル
* 高評価・チャンネル登録よろしくおねがいします！
* https://www.youtube.com/channel/UCRXsI3FL_kvaVL9zoolBfbQ
*/

#include <bits/stdc++.h>


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


#define inf (int)(3e18)
#define int long long
#define mod (int)(1000000007)

#define intt long long
#define P pair<int,int>

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

using namespace std;

//Library
//モッドパウ
int modpow(int x, int y, int m = mod) {
    int res = 1;
    while (y) {
        if (y % 2) {
            res *= x;
            res %= m;
        }
        x = x * x % mod;
        y /= 2;
    }
    return res;
}

int mypow(int x, int y) {
    int res = 1;
    while (y) {
        if (y % 2) {
            res *= x;
        }
        x = x * x;
        y /= 2;
    }
    return res;
}
//is the number (x) a prime number?
bool prime(int x) {
    for (int i = 2; i * i <= x; i++) {
        if (!(x % i)) {
            return false;
        }
    }
    return true;
}


//saidai-kouyakusuu
inline int gcd(int x, int y) {
    if (!y) {
        return x;
    }
    return gcd(y, x % y);
}


//number of keta
int keta(int x) {
    int ans = 0;
    while (x) {
        x /= 10;
        ans++;
    }
    return ans;
}

//sum of keta
int ketasum(int x) {
    int ans = 0;
    while (x) {
        ans += x % 10;
        x /= 10;
    }
    return ans;
}

inline int lcm(int x, int y) {
    int ans = x / gcd(x, y) * y;
    return ans;
}
int twobeki(int x) {
    int ans = 0;
    while (1) {
        if (!(x & 1)) {
            ans++;
            x /= 2;
        }
        else {
            break;
        }
    }
    return ans;
}


template <class T, class U>
inline bool chmax(T& lhs, const U& rhs) {
    if (lhs < rhs) {
        lhs = rhs;
        return 1;
    }
    return 0;
}
template <class T, class U>
inline bool chmin(T& lhs, const U& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return 1;
    }
    return 0;
}
void Yes(){
    cout<<"Yes"<<endl;
}
void No(){
    cout<<"No"<<endl;
}
void YES(){
    cout<<"YES"<<endl;
}
void NO(){
    cout<<"NO"<<endl;
}


#define fin(i) scanf("%lld",&i)
#define fout(i) printf("%lld",i)
#define fendl printf("\n")
//Library-End

int n,a[200004],ans,l,r,cnt,sum;
string s;
signed main() {
    cin>>n;
    r=1;
    rep(i,n)fin(a[i]);
    cnt=a[0];
    sum=a[0];
    while (l<n) {
        while (!(sum&a[r])&&r!=n) {
            sum^=a[r];
            r++;
        }
        ans+=r-l;
        sum^=a[l];
        l++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 1792
n = gets.to_i
s = gets.split.map(&:to_i)
q = gets.to_i
t = gets.split.map(&:to_i)

sum = 0

for i in 0..(q-1)
  left = 0
  right = n-1
  key = t[i]
  while left < right || left==499
    mid = (right+left)/2
    if key == s[mid]
      sum += 1
      break
    elsif key < s[mid]
      right = mid
    else
      left = mid+1
    end
  end
end
puts sum

Measured memory_bytes: 17920
#include <stdio.h>
typedef long long ll;
int main() {
	int n, a[100];
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &a[i]);
	}
	ll money = 1000;
	ll kabu = 0;
	for (int i = 0; i < n - 1; i++) {
		if (a[i] < a[i + 1]) {
			kabu += money / a[i];
			money %= a[i];
		} else {
			money += kabu * a[i];
			kabu = 0;
		}
	}
	money += kabu * a[n - 1];
	printf("%lld\n", money);
	return 0;
}

Measured memory_bytes: 1700
import collections
n = int(input())
S = []
for i in range(n):
    s = input()
    S.append(s)
c = collections.Counter(S)
M = c.most_common()
l = []
for i in range(len(M)):
    if M[i][1]==M[0][1]:
        l.append(M[i][0])
l.sort()
[print(ans) for ans in l]

Measured memory_bytes: 48660
#include<bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class T> using oset=tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define pb push_back
#define N 200001
#define ll long long
#define int ll 
#define pi pair<int , int>
#define pip pair<pair ,int>
#define mp make_pair 
#define f first
#define s second
#define mod 998244353
ll Mod(ll x, ll y, int p) 
{ll res = 1; x = x % p;
while (y > 0) 
{if(y & 1) res = (res*x) % p; 
y = y>>1;x = (x*x) % p; 
}return res; 
}
int* getlps(string pattern){
 int len = pattern.length();
 int * lps = new int[len];
 lps[0] = 0;
 int i = 1 , j = 0;
 while(i < len){
  if(pattern[i] == pattern[j]){
	  lps[i] = j+1;
   i++;
   j++;
  }
  else{
		if(j != 0){
		 j = lps[j-1];
		}
		else{
		 lps[i] = 0;
		 i++;
		}
  }
 }
 return lps;
}
class Triplet{
 public:
 int x ;
 int y ;
 int gcd;
};
Triplet extendedEuclid(int a , int b){
 if(b == 0){Triplet ans; ans.gcd = a;ans.x = 1;ans.y = 0;return ans;}
 Triplet smallAns = extendedEuclid(b , a%b);
 Triplet ans;
 ans.gcd = smallAns.gcd;
 ans.x = smallAns.y;
 ans.y = smallAns.x - (a/b)*smallAns.y;
 return ans;
}
int mmInverse(int a , int m){
 Triplet ans = extendedEuclid(a , m);
 return ans.x;
}
int n;
int arr[N];
map<pi , int> dp;
const int MIN = -1e18;
int fun(int idx , int k){
   //if(idx >= n && k > 0)return MIN;
   if(k ==0 && idx >= n)return 0;
   if(idx >= n)return MIN;
    if(n-idx < 2*k - 1)return MIN;
   if(dp.count({idx , k}) > 0)return dp[{idx , k}];
   //if(v[idx])return dp[idx];
  // v[idx] = true;
   int sum = 0;
   if(k > 0){
     sum = arr[idx]+fun(idx+2 , k-1);
 }
   int op2 = fun(idx+1 , k);
   return dp[{idx , k}] = max(sum , op2);
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin>>n;
for(int i = 0 ; i < n ; i++){
		cin>>arr[i];
}
//memset(v , false , sizeof(v));
cout<<fun(0 , n/2)<<endl;
}


Measured memory_bytes: 33316
#include "bits/stdc++.h"
using namespace std;

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


int main() {
	int N; cin >> N;
	vector<int> A(N);

	rep(i, N) {
		cin >> A[i];
	}
	vector<int> B(A);
	sort(B.begin(), B.end());
	int max=B[B.size()-1], second=B[B.size()-2];
	rep(i, N) {
		if (A[i] != max) {
			cout << max << endl;
		}
		else {
			cout << second << endl;
		}
	}
}

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

int main(){
  int N,T;
  cin>>N>>T;
  vector<int>c;
  vector<int>t;
  int count=0;
  for(int i=0;i<N;i++){
    int cc,tt;
    cin>>cc>>tt;
    if(tt<=T){
      c.push_back(cc);
      t.push_back(tt);
      count++;
    }
  }

  double min=1000;
  if(count==0){
    cout<<"TLE"<<endl;
  }else{
  for(int i=0;i<c.size();i++){
    if(c.at(i)<min){
      min=c.at(i);
    }
  }
  cout<<min<<endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    string S;
    deque<char> s, t;
    cin >> S;
    for (auto c: S) {
        s.push_back(c);
        t.push_front(c);
    }
    int Q;
    cin >> Q;
    for (int i = 0; i < Q; i++) {
        int a;
        cin >> a;
        if (a == 1) {
            swap(s, t);
        }
        else {
            int F;
            char C;
            cin >> F >> C;
            if (F == 1) {
                s.push_front(C);
                t.push_back(C);
            }
            else {
                s.push_back(C);
                t.push_front(C);
            }
        }
    }
    for (auto c: s) {
        cout << c;
    }
    cout << endl;
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
typedef long long ll;
#define REP(i,n) for(int i = 0;i < (n);i++)
#define rep(i,m,n) for(int i = (m);i < (n);i++)
#define P pair<int,int>
#define pb push_back
#define mk make_pair
using namespace std;
#define Vec(a) vector <int> a
const int INF = 1 << 20;
const int MOD = 1e9+7;





int main(){
  ll n;
  cin >> n;
  ll a[100001] = {};
  REP(i,100001){
    a[i] = 0;
  }
  REP(i,n){
    ll b;
    cin >> b;
    a[b]++;
  }
  ll sum = 0;
  REP(i,99999){
    ll b = a[i]+a[i+1]+a[i+2];
    //cout << b << endl;
    sum = max(sum,b);
  }
  cout << sum << endl;
  return 0;
}


Measured memory_bytes: 1024
#include <stdio.h>  /*入出力*/
#include <stdlib.h> /*標準ライブラリ*/
#include <string.h> /*文字列*/
#include <math.h>   /*計算*/
#include <assert.h> /*確認*/
#include <ctype.h>  /*文字操作*/
#include <stdbool.h>/*bool型*/
#include <limits.h> /*限界*/

#define rep(i, n) for(int  i = 0; i < (n); i++)
#define max(a,b) ((a>b)?a:b)
#define ABS(a) (((a)>(0))?a:-(a))
#define LL long long
#define MOD 1000000007//10^9+7(素数)

//abc159 A

int main(void)
{
  int M,N;
  int ans = 0;
  scanf("%d %d",&N, &M);
  if (N > 1) {
    ans += N * (N-1) / 2;
  }
  if (M > 1) {
    ans += M * (M-1) / 2;
  }
  printf("%d\n", ans);
  return 0;
}


Measured memory_bytes: 128
#import string,itertools,fractions,heapq,re,array,bisect
#from math import *
#from collections import Counter
def rl(s): return xrange(len(s))

INF = 2147483647


import sys
stdin = sys.stdin

X, Y = map(int, stdin.readline().strip().split())

if X == Y or abs(X - Y) == 1:
    print "Brown"
else:
    print "Alice"


Measured memory_bytes: 2568
from collections import defaultdict
from itertools import groupby, accumulate, product, permutations, combinations
from bisect import *
def solve():
  ans = 0
  N = int(input())
  S = input()
  d = defaultdict(lambda: [])
  for i,s in enumerate(S):
    d[int(s)].append(i)
  for p in product(range(10),repeat=3):
    if not len(d[p[0]]):
      continue
    ind1 = d[p[0]][0]
    ind2 = bisect_right(d[p[1]],ind1)
    if ind2==len(d[p[1]]):
      continue
    ind2 = d[p[1]][ind2]
    ind3 = bisect_right(d[p[2]],ind2)
    if ind3==len(d[p[2]]):
      continue
    ans += 1
  return ans
print(solve())

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

using namespace std;
#define ll long long int
#define X first
#define Y second
const int MAXN = 1e5 + 5;
ll n, dp[MAXN], arr[MAXN];

ll solve(int idx = 1)
{
	if (idx > n) return 0;

	ll &ret = dp[idx];
	if (~ret) return ret;
	ret = 0;

	if (idx < n) ret = solve(idx + 1) + abs(arr[idx] - arr[idx + 1]);
	if (idx + 1 < n) ret = min(ret, solve(idx + 2) + abs(arr[idx] - arr[idx + 2]));

	return ret;
}

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
	memset(dp, -1, sizeof dp);
	cout << solve() << endl;
	return 0;
}

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

int main(){
  int n, k, i, j;
  cin >> n >> k;
  vector<double> P(n);
  //vector<double> E(n);
  rep(i, n) cin >> P[i];
  //rep(i, n) cout << P[i];
  double ch = 0;
  //int q = 0;
  //double sum = 0;
  /*for(i=0; i<=n-k; i++){
    for(j=i; j<=i+k-1; j++){
      sum += P[j];
      //cout << sum << endl;
    }
    if(sum > ch){
      //q = i;
      ch = sum;
      sum = 0;
    }
    else sum = 0;
    //cout << ch << endl;
  }*/
  for(i=0; i<k; i++) ch += P[i];
  double sum = ch;
  int tmp = 0;
  for(j=k; j<n; j++){
    sum = sum - P[tmp] + P[j];
    if(sum>ch) {ch = sum;
                 tmp++;}
    else tmp++;
  }
  
  double ans = (ch+k)/2;
  //double a = 7.0/2;
  //printf("%lf\n", a);
  printf("%.12f\n", ans);
  
}

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

#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define ALL(v) (v).begin(), (v).end()
#define p(s) cout<<(s)<<endl
#define p2(s, t) cout << (s) << " " << (t) << endl
#define br() p("")
#define pn(s) cout << (#s) << " " << (s) << endl
#define p_yes() p("Yes")
#define p_no() p("No")

const ll mod = 1e9 + 7;
const ll inf = 1e18;

template < typename T >
void vprint(T &V){
	for(auto v : V){
    	cout << v << " ";
	}
	cout << endl;
}

ll ll_pow(ll a, ll n){
    ll ans = 1;
    FOR(i, 0, n){
        ans *= a;
    }
    return ans;
}

vector<ll> coins;
ll memo[100010];

// a円で支払う最小回数
ll rec(ll a){
    if(memo[a]!=0){
        return memo[a];
    }

    if(a==0) return 0;

    ll min_num = inf;
    for(ll c : coins){
        if(a-c<0) continue;

        ll num = rec(a-c) + 1;
        min_num = min(min_num, num);
    }

    return memo[a] = min_num;
}

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

    // input
    ll N;
    cin >> N;

    coins.push_back(1);
    FOR(i, 1, 7){
        coins.push_back(ll_pow(6, i));
    }
    FOR(i, 1, 6){
        coins.push_back(ll_pow(9, i));
    }
    sort(ALL(coins), greater<ll>());

    ll ans = rec(N);
    p(ans);
    
    return 0;
}

Measured memory_bytes: 1024
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();

		Set<Integer> set = new HashSet<>();
		for (int i = 0; i < N; i++) {

			int A = sc.nextInt();
			if(set.contains(A)) {
				System.out.println("NO");
				return;
			}
			set.add(A);
		}
		System.out.println("YES");
	}
}

Measured memory_bytes: 99948
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int NMAX = 110;
const int VMAX = 1010;
const long INF = 10000000000000;

int N, W;
int v[NMAX + 1];
int w[NMAX + 1];
long dp[NMAX + 1][NMAX * VMAX + 1];

int main()
{
    cin >> N >> W;
    for (size_t i = 0; i < N; i++) {
        cin >> w[i] >> v[i];
    }

    fill(dp[0], dp[0] + NMAX * VMAX + 1, INF);
    dp[0][0] = 0;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j <= NMAX * VMAX; j++) {

            if (j - v[i] < 0) {
                dp[i + 1][j] = dp[i][j];
            } else {
                dp[i + 1][j] = min(dp[i][j], w[i] + dp[i][j - v[i]]);
            }
        }
    }

    long result = 0;
    for (int i = 0; i <= NMAX * VMAX; i++) {
        if (dp[N][i] <= W) {
            result = i;
        }
    }

    cout << result << '\n';

    return 0;
}


Measured memory_bytes: 88448
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdint.h>
#include<tgmath.h>
#include<stdbool.h>
#include<sys/queue.h>
#include<time.h>
#define ll long long
#define min(a, b) ((a) > (b) ? (b) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
int cmp(const void *a, const void *b){return *(int *)a - *(int *)b;}

int n, k, p[1111];
int main(){
    scanf("%d%d", &n, &k);
    for(int i=0; i<n; i++)scanf("%d", p+i);
    qsort(p, n, 4, cmp);
    int sum = 0;
    for(int i=0; i<k; i++)sum += p[i];
    printf("%d\n", sum);
    return 0;
}

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

int main() {
  cin.tie(0);
  std::ios::sync_with_stdio(false);
  int N,D,X;
  cin>>N>>D>>X;
  int A[N];
  for (int i=0; i<N; i++) {
    cin>>A[i];
  }
  int ans=X;
  for (int i=0; i<N; i++) {
    ans+=(D-1)/A[i]+1;
  }
  cout<<ans<<endl;
  return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <vector>
#define forsn(i, s, n) for(int i=s;i<n;i++)
#define forn(i, n) forsn(i, 0, n)
using namespace std;
const int MAX = 100000;
vector<vector<int>> v;
bool seen[MAX];
int comp[MAX];
vector<int> permuta;
void DFS (int c, int i){
	for(int neigh : v[i]){
		if(!seen[neigh]){
			seen[neigh]=true, comp[neigh]=c;
			DFS(c, neigh);
		}
	}
}
int cuantosPuedenCoincidir(int p){
	int cont=0;
	forn(i, p){
		 if(comp[i]==comp[permuta[i]-1]){
			 cont++;
		 }
 }
	return cont;
}
int main(){
	int p; cin >> p;
	int pa; cin >> pa;
	permuta.resize(p);
	vector<int> parA (pa);
	vector<int> parB (pa);
	v = vector<vector<int>> (p, vector<int>());
	forn(i, p){
		cin >> permuta[i];
	}
	forn(i, pa){
		cin >> parA[i] >> parB[i];
		parA[i]--;
		parB[i]--;
	}
	forn(i, pa){
		v[parA[i]].push_back(parB[i]);
		v[parB[i]].push_back(parA[i]);
	}
	forn(i, p){
		seen[i]=false;
	}
	forn(i, p){
		comp[i] = i;
	}
	int c = p+1;
	forn(i, p){
		if(!seen[i]){
			DFS(c++, i);
		}
	}
	cout << cuantosPuedenCoincidir(p) << endl;
}

Measured memory_bytes: 9344
from collections import defaultdict

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

d=defaultdict(int)

for i in a:
    d[i] += 1

for _ in range(m):
    b,c = map(int,input().split())
    d[c] += b

d=sorted(d.items(), reverse=True) 

sum=0
cnt=0

for i,j in d:
    for _ in range(j):
        sum += i
        cnt+=1
        if cnt >= n:
            print(sum);exit()


Measured memory_bytes: 40992
/*
      author : nishi5451
      created: 11.08.2020 20:21:07
*/

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


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

Measured memory_bytes: 3524
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int k = sc.nextInt();
		int s = sc.nextInt();//sum
		int cnt = 0;
		for (int i = 0; i <= k; i++) {
			for (int j = 0; j <= k; j++) {
				if (0 <= s - i - j && s - i - j <= k) {
					cnt++;
				}
			}
		}
		System.out.println(cnt);
	}

}


Measured memory_bytes: 23636
#include <algorithm>
#include <iostream>
#include <stdio.h>
#include <string>

#define MAX_N 100

using namespace std;

string S[MAX_N];

int main() {
  int N, L;
  cin >> N >> L;
  for (int i = 0; i < N; ++i) {
    cin >> S[i];
  }
  sort(S, S + N);
  for (int i = 0; i < N; ++i) {
    printf("%s", S[i].c_str());
  }
  printf("\n");
}

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

int main(int argc, const char * argv[]) {
    // insert code here...
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    
    if (A + B > C + D) cout << "Left" << endl;
    else if (A + B < C + D) cout << "Right" << endl;
    else cout << "Balanced" << endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
using namespace std;
#define MOD 1000000007

int main(int argc, char const *argv[]) {
  char a,b;
  std::cin >> a >> b;
  if(a=='H'){
    if(b=='H') std::cout << "H" << endl;
    else std::cout << "D" << endl;
  }

  else{
    if(b=='H') std::cout << "D" << endl;
    else std::cout << "H" << endl;
  }
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG //これつけるとA[N]でもいいらしい
//for文のマクロ
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define mp(a,b) make_pair(a,b)
#define big 1000000007
#define all(a) sort((a).begin(),(a).end()) //ソートのマクロ
#define Re(a) reverse((a).begin(),(a).end())
#define YN(a) if(a){cout<<"Yes"<<endl;}else cout<<"No"<<endl;//条件によってYes、Noを出力する
const int MOD=1000000007;
const double pi = 3.141592653589793;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<int64_t> a(n);
    rep(i,n){
        cin>>a[i];
    }
    all(a);
    Re(a);
    int64_t sum=0;
    rep(i,n){
        sum += a[i/2];
    }
    sum -=a[0];
    cout<<sum<<endl;
}

Measured memory_bytes: 4720
#include <bits/stdc++.h>
using namespace std;
 
int gcd(int x,int y){
    if(y==0)return x;

    return gcd(y,x%y);
}
int lcm(int x,int y){
    return x*y/gcd(x,y);
}

int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

int main()
{

    int H,W;
    char c[110][110]={};

    cin>>H>>W;

    for(int i=1;i<=H;i++){
        for(int j=1;j<=W;j++){
            cin>>c[i][j];
        }
    }

    for(int i=1;i<=2*H;i++){
        for(int j=1;j<=W;j++){
            int temp=(i+1)/2;
            cout<<c[temp][j];
        }
        cout<<endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors


a,b=map(int,input().split())

lst=make_divisors(a)
sin_lst=[]

for i in lst:
  if b%i==0:
    sin_lst.append(i)

if len(sin_lst)==1:
  print(1)
  exit()

lst=[]
lst.append(sin_lst[1])

for i in sin_lst[2:]:
  flag=True
  for j in lst:
    if i%j==0:
      flag=False
      break
  
  if  flag:
    lst.append(i)


print(len(lst)+1)

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

using namespace std;
int main(){
    int n;
    cin >> n;
    n%=10;
    if(n==2||n==4||n==5||n==7||n==9) cout << "hon" << endl;
    else if(n==3) cout << "bon" << endl;
    else cout << "pon" << endl;
    return 0;
}

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

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 1
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())
#define PI (3.141592653589794)
#define TO_STRING(VariableName) # VariableName
#define LOG(x) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<endl;
#define LOG2(x,y) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<endl;
#define LOG3(x,y,z) if(DEBUG)cout<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;
#define LOG4(w,x,y,z) if(DEBUG)cout<<TO_STRING(w)<<"="<<w<<" "<<TO_STRING(x)<<"="<<x<<" "<<TO_STRING(y)<<"="<<y<<" "<<TO_STRING(z)<<"="<<z<<endl;

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

    lli ans = 0;
    priority_queue<pair<lli,lli>> q;
    priority_queue<pair<lli,lli>,vector<pair<lli,lli>>,greater<pair<lli,lli>>> qq;

    lli n;
    cin>>n;
    REP(i,0,n){
        lli k,l,r;
        cin>>k>>l>>r;
        if(l-r>0){
            q.push({k,l-r});
            ans += r;
        }
        else{
            qq.push({k,r-l});
            ans += l;
        }
    }

    lli now = 0;

    multiset<lli> s;
    lli cnt = 0;
    for(lli i=n;i>=1;i--){
        while(q.size() && q.top().first >= i){
            s.insert(q.top().second);
            q.pop();
        }
        if(s.size()==0)continue;
        auto iter = s.end();
      	--iter;
        ans += (*iter);
        s.erase(iter);
    }

    s.clear();
    for(lli i=cnt+1;i<=n;i++){
        while(qq.size() && qq.top().first < i){
            s.insert(qq.top().second);
            qq.pop();
        }
        if(s.size()==0)continue;
      	auto iter = s.end();
      	--iter;
        ans += (*iter);
        s.erase(iter);
    }
    cout<<ans<<endl;

}


int main(){

    lli t;
    cin>>t;
    while(t--)solve();

    return 0;
}


Measured memory_bytes: 7204
let N = Int(readLine()!)!
let TA: [Int] = readLine()!.split(separator: " ").map { Int($0)! }
let diffA: [Int] = readLine()!.split(separator: " ").map { abs(TA[0]*1000 - Int($0)!*6 - TA[1]*1000) }
print(diffA.firstIndex(of: diffA.min()!)! + 1)

Measured memory_bytes: 8260
N, M = map(int, input().split())

a = {i for i in range(1, N+1)}
L_list = []
R_list = []
for i in range(M):
    L, R = map(int, input().split())
    L_list.append(L)
    R_list.append(R)
    # print(a, set([i for i in range(L, R+1)]))
    # a = a & {i for i in range(L, R+1)}
    # print(a, set([i for i in range(L, R+1)]))

print(max(min(R_list) - max(L_list) + 1, 0))

Measured memory_bytes: 60260
#include <iostream>

using namespace std;

int main(){
	int N;
	while(cin >> N){
		long long sum = 0LL;
		long long sub = 1LL << 60;
		for(int i=0;i<N;i++){
			long long A, B; cin >> A >> B;
			if(A > B) sub = min(sub, B);
			sum += A;
		}
		cout << max(0LL, sum - sub) << endl;
	}
}


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

int main(void){
    long long n,x;
    cin >> n >> x;
    vector<long long> vec(n);
    long long count2 = 0;
    long long sum = 0;
    rep(i,n){
        cin >> vec.at(i);
        sum += vec.at(i);
    }
    
    sort(vec.begin(),vec.end());

    long long count = 0;
    rep(i,n){

        if(sum < x){
            cout << n-1 << endl;
            return 0;
        }
        
        else if(sum > x){
            count = 0;
            for(int i=0;i<n;i++){
                if(x >= vec.at(i)){
                    x -= vec.at(i);
                    count++;
                }
            }
            cout << count << endl;
            return 0;
        }

        else{
            cout << n << endl;
            return 0;
        }
    }
    
}

Measured memory_bytes: 256
def calc_sum(width, wall):
    for i in wall:
        width -= Xs[i] - Xs[i-1]
    return width

N, M = map(int, input().split())
Xs = sorted([int(i) for i in input().split()])
diff_ls = [Xs[i+1] - Xs[i] for i in range(M-1)]
max_diff = sorted(diff_ls, reverse=True)[:N-1]
print(Xs[-1] - Xs[0] - sum(max_diff))

Measured memory_bytes: 13840
#include <iostream>
using namespace std;
int main() {
	int a[200], N,i, k, check, flag;
	flag = 0;
	cin >> N; //黒板に書かれている正の整数の個数を決定
	for (i = 0;i < N;i++) {
		cin >> a[i]; //N個、正の整数を入力
	}
	check = 0;
	while (check == 0) { /*checkが0の限り実行*/
		for (i = 0;i < N;i++) {
			k = a[i] % 2;
			if (k == 1) { /*1つ奇数があった時点でcheckに1を代入*/
				check = 1;
			}
		}
		if (check == 0) { /*すべて偶数の場合、すべて2で割ってflagに1を加算*/
			for (i = 0;i < N; i++) {
				a[i] = a[i] / 2;
			}
			flag++;
		}
	}
	cout << flag << endl; /*2で割った回数を出力*/
	return 0;
}

Measured memory_bytes: 256
a = input()
b = input()

a_chars = list(a)
b_chars = list(b)

a_char_len = len(a)
k = 0
count = 0
for i in range(a_char_len):
    if(a_chars[i] != b_chars[i]):
        count = count + 1
        k = k + 1

print(count)

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

#define fi first
#define se second

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

  stack<pair<char, int>> st;
  int max_l = 0;

  st.emplace(str[0], 1);
  for (int i = 1; i < str.size(); i++){
    auto n = st.top();
    if (str[i] == n.fi){
      n.se++;
      st.pop();
      st.emplace(n);
      continue;
    }
    st.emplace(str[i], 1);
  }

  char ex = 'I';
  char j, o, i;
  int a, b, c;
  while (!st.empty()){
    pair<char, int> po = st.top(); st.pop();
    j = po.fi; a = po.se;
    if (a >= b && c >= b && j == 'J' && o == 'O' && i == 'I'){
      max_l = max(max_l, b);
    }
    c = b; b = a;
    i = o; o = j;
  }

  cout << max_l << endl;
}

Measured memory_bytes: 12104
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);

		int H = sc.nextInt();
		int W = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();

		int g = H - a;
		int r = W - b;

		System.out.println(g * r);

		sc.close();

	}
}


Measured memory_bytes: 35560
#include<bits/stdc++.h>
#include<map>
using namespace std;
map<char ,int>mp;

void init_map(){
	mp['a']=0;
	mp['b']=0;
	mp['c']=0;
	mp['d']=0;
	mp['e']=0;
	mp['f']=0;
	mp['g']=0;
	mp['h']=0;
	mp['i']=0;
	mp['j']=0;
	mp['k']=0;
	mp['l']=0;
	mp['m']=0;
	mp['n']=0;
	mp['o']=0;
	mp['p']=0;
	mp['q']=0;
	mp['r']=0;
	mp['s']=0;
	mp['t']=0;
	mp['u']=0;
	mp['v']=0;
	mp['w']=0;
	mp['x']=0;
	mp['y']=0;
	mp['z']=0;
}
using namespace std;
int main(){
	int ans = 0;
	int max = 0;
	int n;
	
	
	char s[101];
	
	
	cin >>n;
	cin >>s;
	
	char temp[101];
	//区切り全探で通る説
	for(int i=1;i<n;i++){
		//left register
		for(int n=0;n<i;n++){
			mp[s[n]]=1;
		//	cout <<s[n]<<endl;
		}
		
		//right serch 
		for(int j=i;j<n;j++){
			if(mp[s[j]] == 1){
				ans++;
			//	cout <<mp[s[j]]<<s[j]<<endl;
				mp[s[j]]++;
			}
		}
		
		if(max < ans){
			max = ans;
			init_map();
		}
		ans=0;
		
	}
	cout <<max<<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main(void){
    long long int n;
    cin >> n;
    vector<long long int> a(n), b(n);
    for (int i=0; i<n; i++) cin >> a[i];
    for (int i=0; i<n; i++) cin >> b[i];
    
    // roop = accumulate(b.begin(), b.end(), 0) - accumulate(a.begin(), a.end(), 0);
    
    long long int sum = 0;
    for (int i = 0; i < n; i++) {
        if(b[i] > a[i]) sum -= (b[i] - a[i])/2;
        else if(b[i] < a[i]) sum += a[i] - b[i];
    }

    if (sum <= 0) cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
}


Measured memory_bytes: 384
#include <bits/stdc++.h>
//#include <boost/multiprecision/cpp_int.hpp>
#define rep(X,N) for(ll X = 0; X < (N); X++)
#define PI (acos(-1.0))
#define pback push_back
#define mpair make_pair
#define MODN 1000000007
#define ALL(V) (V).begin(),(V).end()
#define CERR if(false) cerr
#define INT_MAX_HALF (INT_MAX / 2)

typedef long long ll;

using namespace std;
//using namespace boost::multiprec

int main(){

    int n;
    cin >> n;

    vector<int> a(n + 1);
    vector<int> ans(n + 1);

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

        a[i] = tmp;

        if(i > n / 2){
            ans[i] = tmp;
        }
    }

    for(int i = n / 2; i >= 1; i--){

        int count = a[i];
        int tmpcount = 0;

        for(int j = i * 2; j <= n; j = j + i){
            if(ans[j] == 1) tmpcount++; 
        }

        tmpcount = tmpcount % 2;

        if(count == tmpcount){
            ans[i] = 0;
        }else{
            ans[i] = 1;
        }
    }

    vector<int> ans2;

    for(int i = 1; i <= n; i++){
        if(ans[i] == 1){
            ans2.pback(i);
        }
    }

    cout << ans2.size() << endl;

    rep(i, ans2.size()){
        cout << ans2[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 3064
#include<iostream>
using namespace std;
int main(){
  int a,b;
  cin>>a>>b;
  if(a==b)
    cout<<"Draw"<<endl;
  else if(a==1)
    cout<<"Alice"<<endl;
  else if(b==1)
    cout<<"Bob"<<endl;
  else if(a>b)
    cout<<"Alice"<<endl;
  else
    cout<<"Bob"<<endl;
}

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

using namespace std;

using int64 = long long;
const int INF = 1 << 30;


int main() {
  int A, B, X;
  cin >> A >> B >> X;
  X = (X + 499) / 500;

  int ret = INF;
  for(int i = 0; i <= min(X, B); i++) {
    int rest = (X - i + 1) / 2;
    ret = min(ret, rest * A + i * B);
  }
  cout << ret << endl;
}



Measured memory_bytes: 3104
require 'pp'
$DEBUG ? define_method(:dpp){|e|pp e} : define_method(:dpp){|e|}

# 入力値を数値で返却する
def gets_i()
  gets.chomp.to_i
end
x = gets_i

if x < 100
  puts 0
else
  xc = x.to_s.chars
  a = xc.pop
  b = xc.pop
  m = [b, a].join.to_i
  n = m % 5 == 0 ? m / 5 : m / 5 + 1
  if xc.join.to_i >= n
    puts 1
  else
    puts 0
  end
end

Measured memory_bytes: 14556
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int x=n%10;
        if(x==2|| x== 4|| x== 5 || x== 7 || x== 9){
            System.out.println("hon");
        }else if(x==0 || x==1 ||x== 6 ||x==8){
            System.out.println("pon");
        }else{
            System.out.println("bon");
        }
    }
}

Measured memory_bytes: 27012
n = int(input())
a = list(map(int,input().split()))

b = [a[i]-i-1 for i in range(n)]
b.sort()
c = b[0]
for i in range(n):
    b[i] -= c

ans = sum(b)

for i in range(n-1):
    ans = min(ans,ans-(b[i+1]-b[i])*(n-2*i-2))

print(ans)


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

using namespace std;

const int N = 200010;
const int M = 4010;
const int MAX = 2000;
const int md = 1e9 + 7;

int n, a[N], b[N], f[M][M], fact[2 * M], ifact[2 * M];

void add(int &a, int b) {
  a += b;
  if (a >= md) {
    a -= md;
  }
}

int mul(int a, int b) {
  return (long long) a * b % md;
}

int power(int a, int e) {
  int r = 1;
  for (; e; e >>= 1, a = mul(a, a)) {
    if (e & 1) {
      r = mul(r, a);
    }
  }
  return r;
}

int main() {
  fact[0] = 1;
  for (int i = 1; i < 2 * M; i++) {
    fact[i] = mul(fact[i - 1], i);
  }
  for (int i = 0; i < 2 * M; i++) {
    ifact[i] = power(fact[i], md - 2);
  }
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    scanf("%d %d", &a[i], &b[i]);
    f[MAX - a[i]][MAX - b[i]]++;
  }
  for (int i = 0; i < M; i++) {
    for (int j = 0; j < M; j++) {
      if (i > 0) {
        add(f[i][j], f[i - 1][j]);
      }
      if (j > 0) {
        add(f[i][j], f[i][j - 1]);
      }
    }
  }
  int ans = 0;
  for (int i = 0; i < n; i++) {
    add(ans, f[MAX + a[i]][MAX + b[i]]);
    add(ans, md - mul(fact[2 * a[i] + 2 * b[i]], mul(ifact[2 * a[i]], ifact[2 * b[i]])));
  }
  printf("%d\n", mul(ans, ifact[2]));
  return 0;
}

Measured memory_bytes: 64640
#include "bits/stdc++.h"
using namespace std;
using ld = long double;
const ld eps = 1e-9;

int N;

bool check(const vector<pair<ld, ld>>&cs, const ld amid) {
	map<ld, int>mp;
	for (auto c : cs) {
		const ld r = c.second;
		const ld x = c.first;
		if (r > amid) {
			ld dis = sqrt(r*r - amid*amid);
			mp[x - dis]++;
			mp[x + dis]--;
		}
	}
	ld pre = -1;
	int num = 0;
	ld len = 0;
	bool preok = false;
	for (auto m : mp) {
		num += m.second;
		if (num) {
			if (!preok) {
				pre = m.first;
			}
		}
		else {
			if (preok) {
				len = max(len, m.first - pre);
			}
		}
		preok = num;
	}
	return amid*2 < len;
}
int main() { 
	while (1) {
		cin >> N;
		if (!N)break;
		vector<pair<ld, ld>>cs;
		for (int i = 0; i < N; ++i) {
			int x, r; cin >> x >> r;
			cs.push_back(make_pair(x, r));
		}
		ld amin = 0;
		ld amax = 1e6;
		int atime = 40;
		while (atime--) {
			ld amid = (amin + amax) / 2;
			if (check(cs, amid)) {
				amin = amid;
			}
			else {
				amax = amid;
			}
		}
		cout << setprecision(22) << fixed << amin*2 << endl;
	}
	
	return 0;
}

Measured memory_bytes: 12444
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <time.h>
#include <set>
using namespace std;
const int N=100001;
struct node
{
	int d,p;
	bool operator<(const node &e)const
	{
		if(d<e.d)	return true;
		return false;
	};
}x[N],y[N];
struct edge
{
	int d;
	int u,v;
	bool operator<(const edge &e)const
	{
		if(d<e.d)	return true;
		return false;
	};
};
int n,a[N],b[N],f[N];
multiset<edge> s;
int dist(int x,int y)
{
	return min(abs(a[x]-a[y]),abs(b[x]-b[y]));
}
int findr(int x)
{
	if(x==f[x])	return x;
	return f[x]=findr(f[x]);
}
int uniont(int x,int y)
{
	int gx=findr(x),gy=findr(y);
	if(gx==gy)	return 0;
	f[gx]=gy;	return 1;
}
int main()
{
    int i;
	long long ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
	{
		scanf("%d %d",&x[i].d,&y[i].d),x[i].p=y[i].p=i;
		a[i]=x[i].d,b[i]=y[i].d;
		f[i]=i;
	}
    sort(x+1,x+n+1);sort(y+1,y+n+1);
    for(i=1;i<=n-1;i++)
    {
    	edge tmp;
    	tmp.d=dist(x[i].p,x[i+1].p);
    	tmp.u=x[i].p,tmp.v=x[i+1].p;
    	s.insert(tmp);
    	//cout<<s.size()<<endl;
    	tmp.d=dist(y[i].p,y[i+1].p);
    	tmp.u=y[i].p,tmp.v=y[i+1].p;
    	s.insert(tmp);
    	//cout<<s.size()<<endl;
	}
	for(set<edge>::iterator l=s.begin();l!=s.end();l++)
		ans+=(long long)uniont(l->u,l->v)*l->d;
		//cout<<l->u<<' '<<l->v<<endl;*/
	cout<<ans;
	//for(i=1;i<=n;i++)	cout<<x[i].d<<' '<<x[i].p<<endl;
	return 0;
}


Measured memory_bytes: 16384
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(v) (v).begin(),(v).end()
#define out(a) cout << (a) << endl
using namespace std;
using ll = long long;
int main(){
    int a, b, c, k;
    int ans=0;
    cin >> a >> b >> c >> k;
    if (a<k) {
        ans += a;
        k -= a;
    }
    else {
        ans += k;
        out(ans);
        return 0;
    }
    if (b<k) {
        k -= b;
    }
    else {
        out(ans);
        return 0;
    }
    if (c<k) {
        ans -= c;
        k -= c;
    }
    else {
        ans -= k;
        out(ans);
        return 0;
    }
    
    out(ans);
    return 0;
}

Measured memory_bytes: 3636
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <complex>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
using namespace std;
typedef pair<int,int> P;
typedef pair<int,P> T;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vll;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define INF 2000000000
#define sz(x) ((int)(x).size())
#define fi first
#define sec second
#define SORT(x) sort((x).begin(),(x).end())
#define all(x) (x).begin(),(x).end()
#define EQ(a,b) (abs((a)-(b))<eps)
#define SQ(X) ((X)*(X))
int AN,BN,R,ans;
int AX[100100],AY[100100],BX[100100],BY[100100];
vector<T> event;
set<P> fighter,energy;
bool ok(int a,int b)
{
	return (SQ(AX[a]-BX[b])+SQ(AY[a]-BY[b]) <= 16*R*R);
}
int main()
{
	while(1)
	{
		scanf("%d %d %d",&AN,&BN,&R);
		if(AN==0&&BN==0)break;
		ans=0;
		event.clear();
		fighter.clear();
		energy.clear();
		for(int i=0;i<AN;i++)
		{
			scanf("%d %d",&AX[i],&AY[i]);
			event.pb(T(AX[i]-2*R,P(-1,i)));
			event.pb(T(AX[i]+2*R,P(1,i)));
		}
		for(int i=0;i<BN;i++)
		{
			scanf("%d %d",&BX[i],&BY[i]);
			event.pb(T(BX[i]-2*R,P(-2,i)));
			event.pb(T(BX[i]+2*R,P(2,i)));
		}
		sort(event.begin(),event.end());
		for(int i=0;i<event.size();i++)
		{
			T cur = event[i];
			int k = cur.sec.sec;
			int type = cur.sec.fi;
			set<P>::iterator it,it1,it2;
			if(abs(type)==1)
			{
				if(type<0)
				{
					it1 = energy.lower_bound(P(AY[k]-4*R,-1));
					it2 = energy.upper_bound(P(AY[k]+4*R,INF));
					for(it=it1;it!=it2;it++)if(ok(k,it->sec))ans++;
					fighter.insert(P(AY[k],k));
				}
				else fighter.erase(P(AY[k],k));
			}
			else
			{
				if(type<0)
				{
					it1 = fighter.lower_bound(P(BY[k]-4*R,-1));
					it2 = fighter.upper_bound(P(BY[k]+4*R,INF));
					for(it=it1;it!=it2;it++)if(ok(it->sec,k))ans++;
					energy.insert(P(BY[k],k));
				}
				else energy.erase(P(BY[k],k));
			}
		}
		cout << ans << endl;
	}
	return 0;
}

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

using namespace std;

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

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

int main(void) {
  int i,j;
  int n;
  cin>>n;
  vi v(n);
  rep(i,n) cin>>v[i];
  sort(all(v));
  for(i=1;i<=v[0];i++){
    int c=0;
    rep(j,n)if(v[j]%i==0)c++;
    if(n==c)cout<<i<<endl;
  }
}

Measured memory_bytes: 3120
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
long long rui(long long n, long long k, long long p) {
	if (k == 0) {
		return 1;
	}
	else {
		long long a = rui(n, k / 2, p);
		if (k % 2 == 0) {
			return (a*a) % p;
		}
		return (((a*a) % p)*n) % p;
	}
}
int main(){
	int ans = 0;
	int n; cin >> n;
	for (int i = 0; i < n; i++) {
		int a;
		cin >> a;
		ans += 1 - a % 2;
	}
	cout << ans << endl;
}


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

const int MOD = 1e9 + 7;

signed main() {
  int N, M;
  cin >> N >> M;
  int a[101010] = {0};
  for (int i = 0; i < M; i++) {
    int tmp;
    cin >> tmp;
    a[tmp] = 1;
  }

  int dp[101010] = {0};
  dp[0] = 1;

  for (int i = 0; i < N; i++) {
    if (a[i]) dp[i] = 0;
    dp[i + 1] += dp[i];
    dp[i + 1] %= MOD;
    dp[i + 2] += dp[i];
    dp[i + 2] %= MOD;
  }

  cout << dp[N] << endl;
  return 0;
}


Measured memory_bytes: 1792
#include <iostream>
#include <queue>
#include <utility>
#include <map>
#include <cmath>
#include <string>
#include <stdio.h>
#include <sstream>

using namespace std;

int main(){
    int n, ans=0;
    cin >> n;
    
    for(int i=1;i<=n;i++){
        ostringstream oss;
        oss << i;
        string str = oss.str().c_str();
        
        if((int)(str.length())%2==1) {ans++;}
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>  
#include <algorithm>  
#include <assert.h>
#include <bitset>
#include <cmath>  
#include <complex>  
#include <deque>  
#include <functional>  
#include <iostream>  
#include <limits.h>  
#include <map>  
#include <math.h>  
#include <queue>  
#include <set>  
#include <stdlib.h>  
#include <string.h>  
#include <string>  
#include <time.h>  
#include <unordered_map>  
#include <unordered_set>  
#include <vector>  
#define ll long long
#define rep2(i,a,b) for(ll i=a;i<=b;++i)
#define rep(i,n) for(int i=0;i<n;i++)
#define rep3(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tii tuple<int,int,int>
#define pq priority_queue<int>
#define pqg priority_queue<int,vector<int>,greater<int>>
#define pb push_back
#define edge(v,a,b) v[a].pb(b);v[b].pb(a);
#define MAX_V 400010
#define vec vector<int>
#define vecll vector<ll>
#define vecpii vector<pii>
#define endl "\n"
#define ALL(c) (c).begin(),(c).end()
using namespace std;
int in() {int x;scanf("%d",&x);return x;}
ll lin() {ll x;scanf("%lld",&x);return x;}
template<typename A, size_t NNN, typename T>
void Fill(A (&array)[NNN], const T &val){
    fill( (T*)array, (T*)(array+NNN), val );
}
#define INF 1e9+7
#define LLINF 1e18+7
ll MOD=1e9+7;
#define N 205050

ll n;
ll p;
int m[500][500];
int memo[500][500];
ll cnt[200000][2];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};
void dfs(int x,int y,int z,int num){
    rep(i,4){
        int xx=x+dx[i],yy=y+dy[i];
        if(!memo[xx][yy]&&m[xx][yy]==-z){
            memo[xx][yy]=num;
            if(z==1)
            cnt[num][0]++;
            else 
            cnt[num][1]++;
            dfs(xx,yy,-z,num);
        }
    }
    return ;
}
main(){
    int h=in(),w=in();
    rep2(i,1,h){
        string s;
        cin>>s;
        rep2(j,1,w){
            if(s[j-1]=='#')m[i][j]=1;
            else m[i][j]=-1;
        }
    }
    int id=1;
    ll ans=0;
    rep2(i,1,h){
        rep2(j,1,w){
            if(memo[i][j])continue;
            else{
                dfs(i,j,m[i][j],id);
                ans+=cnt[id][0]*cnt[id][1];
                id++;
            }
        }
    }
    cout<<ans;
}

Measured memory_bytes: 15616