akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
#define int long long
#define ull unsigned long long
#define ld long double
#define rep(a) rep1(i,a)
#define rep1(i,a) rep2(i,0,a)
#define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++)
#define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--)
#define all(a) a.begin(),a.end()
#define pii pair<int,int>
#define pb push_back
#define mp make_pair
#define sz(a) ((int)a.size())
#define pow2(x) (1ll<<(x))
#define print0(a) cout << (a) << ' '
#define print1(a) cout << (a) << '\n'
#define print2(a,b) cout << (a) << ' ',print1(b)
#define print3(a,b,c) cout << (a) << ' ',print2(b,c)
#define print4(a,b,c,d) cout << (a) << ' ',print3(b,c,d)
#ifdef i_am_noob
#define debug(a) print2(#a,a)
#else
#define debug(a) 
#endif
#define ordered_set tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>
 
using namespace std;
using namespace __gnu_pbds;
 
const int Mod=1000000007,Mod2=998244353;
const int MOD=Mod2;
 
inline int add(int a, int b){return (a+b>=MOD?a+b-MOD:a+b);}
inline int sub(int a, int b){return (a+MOD-b>=MOD?a-b:a+MOD-b);}
int Pow(int a, int b){
	if(!b) return 1;
	int tmp=Pow(a*a%MOD,b>>1);
	return (b&1?tmp*a%MOD:tmp);
}
inline int inverse(int n){return Pow(n,MOD-2);}

const int maxn=100005;
//i_am_noob
int n,a[maxn],cur=0,ans=0;

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	cin >> n;
	rep(n) cin >> a[i];
	rep(n){
		cur++;
		if(i<n-1) if(a[i]<a[i+1]){
			ans=max(ans,cur-1);
			cur=0;
		}
	}
	ans=max(ans,cur-1);
	print1(ans);
	return 0;
}

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

int main() {
  int n; cin >>n;
  int shou=INT_MAX;
  int sa=-1*INT_MAX;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(a-shou>sa)sa=a-shou;
    shou=min(shou,a);
  }
  cout<<sa<<endl;
  return 0;
}


Measured memory_bytes: 3116
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
#define fr(i,n) for(int i=0;i<(n);++i)
#define Fr(i,n) for(int i=1;i<=(n);++i)
#define ifr(i,n) for(int i=(n)-1;i>=0;--i)
#define iFr(i,n) for(int i=(n);i>0;--i)
 
int main(void) {
  int a,b,c,k;cin>>a>>b>>c>>k;
  int ans = 0;
  ans += min(a,k);
  if(k-a-b>0) ans-=k-a-b;

  
  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3576
#include <bits/stdc++.h>
using namespace std;
#define rad(x) x * M_PI / 180

int main(){
  double x = 0.0;
  double y = 0.0;
  int angle = 0.0;
  int d = 0;
  int r = 0;

  while (1){
    scanf("%d, %d", &r, &d);
    if (r == 0 && d == 0) break;
    y += r * sin(rad(angle));
    x += r * cos(rad(angle));

    angle += d;
  }

  printf("%d\n%d\n", (int)y, (int)x);
  return 0;
}

Measured memory_bytes: 1192
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#include <atcoder/all>
// #include <bits/stdc++.h> 
#include <complex>
#include <queue>
#include <set>
#include <unordered_set>
#include <list>
#include <chrono>
#include <random>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <map>
#include <unordered_map>
#include <stack>
#include <iomanip>
#include <fstream>

using namespace std;
using namespace atcoder;
 
typedef long long ll;
typedef long double ld;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
typedef pair<double,double> pdd;
typedef vector<ll> v64;
typedef vector<int> v32;
typedef vector<vector<int> > vv32;
typedef vector<vector<ll> > vv64;
typedef vector<vector<p64> > vvp64;
typedef vector<p64> vp64;
typedef vector<p32> vp32;
ll MOD = 1e9+7;
double eps = 1e-12;
#define forn(i,e) for(ll i = 0; i < e; i++)
#define forsn(i,s,e) for(ll i = s; i < e; i++)
#define rforn(i,s) for(ll i = s; i >= 0; i--)
#define rforsn(i,s,e) for(ll i = s; i >= e; i--)
#define ln '\n'
#define dbg(x) cout<<#x<<" = "<<x<<ln
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define INF 101
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define all(x) (x).begin(), (x).end()
#define sz(x) ((ll)(x).size())
#define zero ll(0)
#define set_bits(x) __builtin_popcountll(x)
 
ll mpow(ll a, ll b){
	if(a==0) return 0;
	if(b==0) return 1;
	ll t1 = mpow(a,b/2);
	t1 *= t1;
	t1 %= MOD;
	if(b%2) t1 *= a;
	t1 %= MOD;
	return t1;
}
 
ll mpow(ll a, ll b, ll p){
	if(a==0) return 0;
	if(b==0) return 1;
	ll t1 = mpow(a,b/2,p);
	t1 *= t1;
	t1 %= p;
	if(b%2) t1 *= a;
	t1 %= p;
	return t1;
}
 
ll modinverse(ll a, ll m){
	ll m0 = m; 
    ll y = 0, x = 1; 
    if (m == 1) return 0; 
    while (a > 1){
        ll q = a / m; 
        ll t = m; 
        m = a % m, a = t; 
        t = y; 
        y = x - q * y; 
        x = t; 
    }
    if (x < 0) x += m0; 
    return x; 
}

mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
 
ll range(ll l, ll r){
	return l + mt()%(r-l+1);
}
 
ll rev(ll v){
	return mpow(v,MOD-2);
}


void solve(){
	ll n;
	cin >> n;
	n *= 2;
	ll ans = n-1;
	v64 factor;
	for(ll i = 2; i*i<=n; i++){
		if(n%i == 0){
			ll cur = 1;
			while(n%i==0){
				cur *= i;
				n/=i;
			}
			factor.pb(cur); 
		}
	}
	if(n>1) factor.pb(n);
	ll tot = sz(factor);
	forn(i,(1<<tot)){
		ll v1 = 1, v2 = 1;
		forn(j,tot){
			if(i&(1<<j)) v1*=factor[j];
			else v2*=factor[j];
		}
		// cout << v1 << " " << v2 << ln;
		if(v1>1) v2 *= inv_mod(v2, v1);
		if(v2<v1) v2 = v1+1;
		// cout << v1 << " " << v2 << ln;
		ans = min(ans,v2-1);
		// cout << ans << ln;
	} 
	cout << ans << ln;
}
 
int main()
{
	fast_cin();
	ll t=1;
    // cin >> t;
    forn(i,t) {
    	// cout << "Case #" << i+1 << ": ";
    	solve();
    }
    return 0;
}

Measured memory_bytes: 3716
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		// standard input
		int numBoxes = sc.nextInt();
		int numLimit = sc.nextInt();
		int[] candyArray = new int[numBoxes];
		for (int i = 0; i < numBoxes; i++) {
			candyArray[i] = sc.nextInt();
		}

		//
		long totalAteCandies = 0;
		for (int i = 1; i < numBoxes; i++) {
			int numExcessCandies = calculateExcessCandies(numLimit, candyArray[i - 1], candyArray[i]);
			totalAteCandies += numExcessCandies;
			eatCandies(candyArray, i, numExcessCandies);
		}
		System.out.println(totalAteCandies);
	}

	public static int calculateExcessCandies(int limit, int candy1, int candy2) {
		int numCandies = candy1 + candy2 - limit;
		if (numCandies < 0) {
			return 0;
		} else {
			return numCandies;
		}
	}

	public static void eatCandies(int[] array, int index, int numExcessCandies) {
		array[index] -= numExcessCandies;
		if (array[index] < 0) {
			array[index - 1] += array[index];
			array[index] = 0;
		}
	}
}

Measured memory_bytes: 34132
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int A = sc.nextInt();
        int B = sc.nextInt();
        int C = sc.nextInt();

        sc.close();

        if (A > B) {

            System.out.println(0);
            System.exit(0);
        }

        if (B/A >= C) {

            System.out.println(C);
        } else {

            System.out.println(B/A);
        }

        System.exit(0);
    }

}

Measured memory_bytes: 21844
#include<stdio.h>
#include<stdlib.h>
#define MAX_R (300000000)
#define min(x,y) ((x<y)?x:y)
typedef struct stone{
	int x,r;
}Stone;
Stone p[155][15];
int xn[155],dp[155][15][80];
int main(){
	int i,j,k,h,n,m,x,y,z,ans;
	while(1){
		scanf("%d%d",&n,&m);
		if(n==0)break;
		for(i=0;i<n;i++){
			scanf("%d",&xn[i]);
			for(j=0;j<xn[i];j++){
				scanf("%d%d",&p[i][j].x,&p[i][j].r);
				for(k=0;k<=m;k++)dp[i][j][k]=MAX_R;
			}
		}
		for(i=0;i<xn[0];i++)dp[0][i][0]=0;
		for(i=0;i<xn[1];i++)dp[1][i][1]=0;
		for(i=0;i<n-1;i++){
			for(h=0;h<=m;h++){
				for(j=0;j<xn[i];j++){
					for(k=0;k<xn[i+1];k++){
						y=(p[i][j].r+p[i+1][k].r)*abs(p[i][j].x-p[i+1][k].x);
						dp[i+1][k][h]=min(dp[i+1][k][h],dp[i][j][h]+y);
					}
					for(k=0;k<xn[i+2];k++){
						y=(p[i][j].r+p[i+2][k].r)*abs(p[i][j].x-p[i+2][k].x);
						dp[i+2][k][h+1]=min(dp[i+2][k][h+1],dp[i][j][h]+y);
					}
				}
			}
		}
		ans=MAX_R;
		for(i=0;i<=m;i++)
			for(j=0;j<xn[n-1];j++)
				ans=min(ans,dp[n-1][j][i]);
		for(i=0;i<m;i++)
			for(j=0;j<xn[n-2];j++)
				ans=min(ans,dp[n-2][j][i]);
		
		printf("%d\n",ans);
	}
	return 0;
}

Measured memory_bytes: 1132
#include <iostream>
#include <iterator>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <numeric>
#include <iomanip>
#include <limits>
#include <set>
#include <map>
#include <type_traits>
#include <cstdint>

typedef long long ll;

using namespace std;

//素因数分解
void factoring(ll n, map<ll, ll>& mp) {
	for (ll i = 2; i * i <= n; i++) {
		while (n % i == 0) {
			mp[i]++;
			n /= i;
		}
	}
	if (n != 1) mp[n]++;
}

//絶対値
template<class T, class U = std::make_unsigned_t<T>>
U SafeAbs( T x ) {
    return x < 0 ? -static_cast<uintmax_t>(x) : x;
}

//最大・最小
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;
}

//xのn乗
ll mod_pow(ll x, ll n, ll mod) {
    ll res = 1;
    while (n > 0) {
        if (n & 1) res = res * x % mod;
        x = x * x % mod;
        n >>= 1;
    }
    return res;
}
//xの逆元
ll mod_inv(ll x, ll mod) {//O(log(mod))
    return mod_pow(x, mod - 2, mod);
}

//nCr
ll ncr(ll n, ll r, ll mod){
	ll res=1;
	ll num=1,den=1;
	for(ll i=n;i>=n-r+1;i--){
		(den*=i)%=mod;
	}
	for(ll i=1;i<=r;i++){
		(num*=i)%=mod;
	}
	
	res=den*mod_inv(num,mod);

	return res%mod;
}


//二分探索
bool isOk(ll index, ll key,vector<ll> &a, bool g){
	if(g){
		if(a[index]<key){
			return true;
		}
	}
	else{
		if(a[index]>key){
			return true;
		}
	}
	return false;
}

ll bin_search(ll key, vector<ll> &a, bool g){
	
	ll l=-1;
	ll r=a.size();

	if(g){
		l=a.size();
		r=-1;
	}

	while(abs(r-l)>1){
		ll mid = (l+r)/2;
		if(isOk(mid, key, a, g)){
			r=mid;
		}
		else{
			l=mid;
		}
	}
	return r;
}

//深さ優先探索
void dfs(vector<vector<ll>> &gra, ll v, ll p, ll x, vector<ll> &con){
	con[v]+=x;
	
	for(auto i : gra[v]){
		if(i==p){
			continue;
		}
		dfs(gra,i,v,con[v],con);
	}
	

}

void solve(){
	ll n,q;
	cin>>n>>q;

	vector<vector<ll>> gra(n);

	for(ll i=0;i<n-1;i++){
		ll a,b;
		cin>>a>>b;
		a--;
		b--; //0indexに直す

		gra[a].push_back(b);
		gra[b].push_back(a);
	}

	vector<ll> con(n,0);

	for(ll i=0;i<q;i++){
		ll p,x;
		cin>>p>>x;
		p--;

		con[p]+=x;

	}

	dfs(gra,0,-1,0,con);

	for(ll i=0;i<n;i++){
		cout<<con[i]<<endl;
	}

}

int main(){

	

	solve();
	
	
    return 0;
}


Measured memory_bytes: 30464
#include<bits/stdc++.h>
using namespace std;
int const nax = 3e5 + 10;

int main () {
    string s;

    cin >> s;

    if (s == "ARC") {
        cout << "ABC";
    } else cout << "ARC";
}

/*
    Good Luck
        -Lucina
*/


Measured memory_bytes: 3628
#include <iostream>//cout<<right で右揃え
#include <iomanip>//cout<<setw(数字) で空白による桁揃え
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <cstdlib>//abs()で整数絶対値
#include <cmath>//abs()かfabs()で少数絶対値
#include <functional>//sort第三引数greater<型名>()で降順
#include <map>

using namespace std;
using ll = long long int;

int main(){
    int N;cin>>N;
    int all = 0;
    vector<int> A(N);
    for(int i=0;i<N;i++){
        cin >> A[i];
        all = all^A[i];
    }
    for(int i=0;i<N;i++){
        int ans;
        ans = all^A[i];
        cout << ans << " ";
    }
    cout << endl;
    return 0;
}

Measured memory_bytes: 4028
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define all(V) V.begin(),V.end()

ll fdiv(ll x, ll y) {
	if (y < 0) {
		x = -x, y = -y;
	}
	if (x < 0) {
		return x / y;
	}
	else {
		if (x % y == 0)return x / y;
		else return x / y + 1;
	}
}

int main() {
	ll N, K;
	cin >> N >> K;

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

	sort(all(A));
	ll ng = LLONG_MIN / 3, ok = LLONG_MAX / 3, mid, cnt = 0, ser = 0, id;
	ll ans = 0;
	while (ok - 1 != ng) {
		mid = (ok - ng) / 2 + ng;

		ans = 0;
		for (ll i = 0;i < N;i++) {
			if (A[i] < 0) {
				ser = fdiv(mid, A[i]);
				auto it = lower_bound(all(A), ser);
				//そこより上のすべて
				id = it - A.begin();
				if (id <= i) {
					cnt = N - i - 1;
				}
				else {
					cnt = N - id;
				}
			}
			else if (A[i] > 0) {
				ser = mid / A[i];
				auto it = upper_bound(all(A), ser);
				id = it - A.begin();
				if (i < id) {
					cnt = id - ((ll)i + 1);
				}
				else {
					cnt = 0;
				}
			}
			else {
				if (mid < 0)cnt = 0;
				else cnt = N - (i + 1);
			}
			ans += cnt;
		}

		//mid以下が何個か
		if (ans >= K) {
			ok = mid;
		}
		else {
			ng = mid;
		}
	}
	cout << ok << endl;
}


Measured memory_bytes: 1792
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scan = new Scanner(System.in);
		while (scan.hasNext()) {
			double a = scan.nextInt();
			double b = scan.nextInt();
			double c = scan.nextInt();
			double d = scan.nextInt();
			double e = scan.nextInt();
			double f = scan.nextInt();

			double x;
			double y;

			x = ((c * e) - (f * b)) / ((a * e) - (d * b));
			y = ((c * d) - (f * a)) / ((b * d) - (e * a));
			
			if(x == 0) x = 0;
			if(y == 0) y = 0;
			
			System.out.printf("%.3f",x);
			System.out.print(" ");
			System.out.printf("%.3f",y);
			System.out.println();
		}
	}

}

Measured memory_bytes: 26324
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


a,b,c = list(map(int, input().split()))
k = int(input())
ans = 0
while a>=b:
    b *= 2
    ans += 1
while b>=c:
    c *= 2
    ans += 1
if ans<=k:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 61732
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define all(x) (x).begin(),(x).end()
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;}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll x;cin>>x;
    ll now=0;
    ll t = 100;
    while(1){
        t=t*1.01;
        now++;
        if(t>=x){
            cout<<now<<endl;
            return 0;
        }
    }
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define NUM 1000000007
#define MAX 100001
#define INF LLONG_MAX
ll modu(ll a, ll n){
    ll res=1;
    while(n){
        if(n&1){
            res=(res*a)%NUM;
        }
        a=(a*a)%NUM;
        n/=2;
    }
    return res%NUM;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll n;
    cin>>n;
    if(n==1)
        cout<<0<<endl;
    else{
        ll one = modu(10,n);
        ll two = 2*modu(9,n);
        ll thr = modu(8,n);
        cout<<(one-two+thr+2*NUM)%NUM<<endl;
    }
    return 0;
}


Measured memory_bytes: 3640
#include <iostream>
using namespace std;
const int MAX_N=40;
int a,b,n;
int undrcnst[MAX_N];
int isunderconstruction(int x,int y){//1 means yes,0 means no.
	int hash=x*100+y;
	for(int i=0;i<MAX_N;i++){
		if(undrcnst[i]==hash)
			return 1;
	}
	return 0;
}

int solve(){
	int roadnet[a][b];
	for(int i=0;i<a;i++)//initialization of roadnet.
		for(int j=0;j<b;j++)
			roadnet[i][j]=0;
	roadnet[0][0]=1;
	for(int i=0;i<a;i++){
		for(int j=0;j<b;j++){
			if(isunderconstruction(i+1,j+1)==0){
				if(i>0)
					roadnet[i][j]+=roadnet[i-1][j];
				if(j>0)
					roadnet[i][j]+=roadnet[i][j-1];
			}
		}
	}
	return roadnet[a-1][b-1];
}

int main() {
	// your code goes here
	for(;;){
		cin >> a >> b >> n;
		if(a==0&&b==0)break;
		for(int i=n;i<MAX_N;i++)undrcnst[i]=0;
		for(int i=0;i<n;i++){
			int xi,yi;
			cin >> xi >> yi;
			undrcnst[i]=xi*100+yi;
		}
		cout << solve() << endl;
	}
	return 0;
}

Measured memory_bytes: 1160
typedef long long ll;
#include <bits/stdc++.h>
using namespace std;
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

ll cnt[510][510];

int main() {
    Fill(cnt,0);
    ll n,m,q;
    std::cin >> n>>m>>q;
    
    ll sum[510][510];
    
    for (int i = 0; i < m; i++) {
        ll tmp_l,tmp_r;
        std::cin >> tmp_l>>tmp_r;
        tmp_l--;
        tmp_r--;
        cnt[tmp_l][tmp_r]++;
    }
    
    for (int i = 0; i < n; i++) {
        sum[i][i] = 0;
        for (int j = i; j < n; j++) {
            sum[i][j+1] = sum[i][j] + cnt[i][j];
        }
    }
    for (int i = 0; i < q; i++) {
        ll tmp_l,tmp_r;
        std::cin >> tmp_l>>tmp_r;
        tmp_l--;
        tmp_r--;
        ll result = 0;
        for (int j = tmp_l; j <= tmp_r; j++) {
            result += sum[j][tmp_r+1] - sum[j][j];
        }
        std::cout << result << std::endl;
    }
}


Measured memory_bytes: 4992
#include <stdio.h>

int main()
{
     int a, b, c;
     scanf("%d %d %d", &a, &b, &c);

     if(a == b) printf("%d\n", c);
     else if(a == c) printf("%d\n", b);
     else if(b == c) printf("%d\n", a);
     else return 0;

     return 0;
}


Measured memory_bytes: 128
#include<iostream>
using namespace std;
int main(){
  int N;
  cin>>N;
  int t[N+1],x[N+1],y[N+1];
  t[0]=x[0]=y[0]=0;
  for(int i=1;i<=N;i++)cin>>t[i]>>x[i]>>y[i];
  for(int i=0;i<N;i++){
    int d,r;
    d=abs(x[i+1]-x[i])+abs(y[i+1]-y[i]);
    r=t[i+1]-t[i]-d;
    if(r<0||r%2==1){
      cout<<"No";
      return 0;
    }
  }
  cout<<"Yes";
  return 0;
}

Measured memory_bytes: 1408
#include <stdio.h>
#include <stdbool.h>
int main(void){
    int how_data;
    scanf("%d",&how_data);
    int data[how_data];
    int loop1;
    int ans=0;
    int count[100009]={'0'};
    for(loop1=0;loop1<how_data;loop1++){
        scanf("%d",&data[loop1]);
        if(count[data[loop1]]==0)ans++;
        count[data[loop1]]++;
        if(count[data[loop1]]>=3){
            count[data[loop1]]-=2;
        }
    }
    int how2=0;
    for(loop1=0;loop1<=100002;loop1++){
        if(count[loop1]==2){
            how2++;
        }
    }
    if(how2%2)ans--;
    
    printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 896
#include<iostream>
#include<iomanip>
#include<cstdlib>
#include<math.h>
#include<algorithm>
#include<string>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<deque>
#include<set>
#include<map>
#define REP(i, N) for(ll i = 0; i < N; ++i)
#define FOR(i, a, b) for(ll i = a; i < b; ++i)
#define ALL(a) (a).begin(),(a).end()
#define pb push_back
#define INF 1000000000
#define MOD 1000000007
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int qx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
int qy[8] = {0, 1, 1, 1, 0, -1, -1, -1};

int main(void) {
	ll T, N;
	cin>>N>>T;
	vector<ll> t(N);
	REP(i, N) cin>>t[i];
	ll ans = 0;
	for(ll i = 0; i < N - 1; ++i) {
		if(t[i + 1] - t[i] > T) ans += T;
		else ans += t[i + 1] - t[i];
	}
	ans += T;
	cout<<ans<<endl;
}


Measured memory_bytes: 1792
#include <stdio.h>

int main(){
	int T, plus;
	scanf("%d %d", &T, &plus);
	int hasil = 1;
	for(int i=1; i<=T; i++){
		int x = hasil*2;
		int y = hasil + plus;
		if(x<=y){
			hasil = x;
		}
		else{
			hasil = y;
		}
	}
	printf("%d\n", hasil);
	
	
	return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <map>

#define rep(i,x) for(int i = 0; i < x; i++)
#define rrep(i,x) for(int i = 1; i <= x; i++)
#define srep(i,s,t) for (int i = s; i < t; ++i)
using ll = long long;
using namespace std;
const int INF = 1001001001;
const ll LINF = 1002003004005006007;

int main(){
    int n, m; cin >> n >> m;
    int ans = n * (n-1) / 2 + m * (m-1) / 2;
    cout << ans << endl;
}



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

int main(){
        int N, hoge;
        cin >> N;
        vector<int> A(N + 1, 0); 
        for(int i = 1; i < N; ++i){
                cin >> hoge;
                ++A.at(hoge);
        }

        for(int i = 1; i <= N; ++i){
                cout << A.at(i) << endl;
        }

        return 0;
}


Measured memory_bytes: 4032
N = int(input())
F = []
for _ in range(N):
    F.append(list(map(int, input().split())))
P = []
for _ in range(N):
    P.append(list(map(int, input().split())))

n = 10
answer = -float("inf")
for bit in range(1, 1<<n):
    ans = 0
    for i in range(N):
        count = 0
        for j in range(n):
            if F[i][j] and (bit>>j & 1):
                count += 1
        ans += P[i][count]
    answer = max(ans, answer)

print(answer)

Measured memory_bytes: 43372
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <set>
#include <cctype>
#define mst(a,b) memset((a),(b),sizeof(a))
#define debug printf("debug\n")
#define INF 0x3f3f3f3f
#define lson lef,mid,rt<<1
#define rson mid+1,rig,rt<<1|1
const int maxn=1e5+5;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int arr[2005][2005];
char str[2005];
int sum[2005][2005];
int hori_sum[2005][2005];
int ver_sum[2005][2005];
int main()
{
	mst(sum,0);
	mst(hori_sum,0);mst(ver_sum,0);
	int n,m,q;
	scanf("%d %d %d",&n,&m,&q);
	getchar();
	for(int i=1;i<=n;i++){
		scanf("%s",str+1);
		for(int j=1;j<=m;j++)
			arr[i][j]=(str[j]=='1');
		getchar();
	}
	
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+arr[i][j];
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=2;j<=m;j++){
			hori_sum[i][j]=(arr[i][j])&(arr[i][j-1]);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			hori_sum[i][j]=hori_sum[i-1][j]+hori_sum[i][j-1]-hori_sum[i-1][j-1]+hori_sum[i][j];
		}
	}
	for(int i=2;i<=n;i++){
		for(int j=1;j<=m;j++){
			ver_sum[i][j]=(arr[i-1][j])&(arr[i][j]);
		}
	}
	
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			ver_sum[i][j]=ver_sum[i-1][j]+ver_sum[i][j-1]-ver_sum[i-1][j-1]+ver_sum[i][j];
		}
	}
	int x1,y1,x2,y2;
	int ans=0;
	while(q--){
		scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
		ans=sum[x2][y2]-sum[x1-1][y2]-sum[x2][y1-1]+sum[x1-1][y1-1];
		ans-=(hori_sum[x2][y2]-hori_sum[x1-1][y2]-hori_sum[x2][y1]+hori_sum[x1-1][y1]);
		ans-=(ver_sum[x2][y2]-ver_sum[x1][y2]-ver_sum[x2][y1-1]+ver_sum[x1][y1-1]);
		printf("%d\n",ans); 
	}
	return 0;
}

Measured memory_bytes: 64640
#define _CRT_SECURE_NO_WARNINGS

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>

using namespace std;

#define N_MAX 2010
#define MOD 1000000007

long long int memo[N_MAX][N_MAX];

long long int comb(int n, int k)
{
	if (k > n){
		return 0;
	}
	if (k < 0){
		return 0;
	}
	if (1 == n){
		return 1;
	}
	if (k == n){
		return 1;
	}
	if (-1 != memo[n][k]){
		return memo[n][k];
	}

	return memo[n][k] = (comb(n - 1, k - 1) + comb(n - 1, k))%MOD;
}

long long int sep(int n, int k)
{
	if (k >= n) return 0;

	return comb(n - 1, k);
}

int main()
{
	FILE *fin = NULL, *fout = NULL;
	//fin = freopen("input.txt", "r", stdin);
	//fout = freopen("output.txt", "w", stdout);
	
	int N, K; scanf("%d%d", &N, &K);
	for (int i = 0; i < N_MAX; i++){
		fill(memo[i], memo[i] + N_MAX, -1);
	}

	if (1 == K){
		printf("%d\n", N);
	}
	else if (N == K){
		printf("1\n");
		for (int i = 1; i < K; i++){
			printf("0\n");
		}
	}
	else{
		for (int i = 0; i < K; i++){
			long long int blue = sep(K, i);
			long long int red = (sep(N - K, i - 1) + sep(N - K, i) * 2 + sep(N - K, i + 1)) % MOD;
			printf("%lld\n", (blue*red) % MOD);
		}
	}


	//finalize
	if (NULL != fin) fclose(fin);
	if (NULL != fout) fclose(fout);

	return 0;
}

Measured memory_bytes: 31872
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
int head[100005],arrive[200005],nxt[200005],tot;
void add_edge(int from,int to){
	arrive[++tot]=to;
	nxt[tot]=head[from];
	head[from]=tot;
}
struct Node{
	int id;
	int value;
	friend bool operator >(Node p,Node q){
		return p.value>q.value;
	}
};
priority_queue<Node,vector<Node>,greater<Node> > q;
int value[100005];
int ab(int a){
	return a<0?-a:a;
}
int main(){
	int n;
	scanf("%d",&n);
	int u,v;
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		add_edge(u,v);
		add_edge(v,u);
	}
	memset(value,-1,sizeof value);
	int k;
	scanf("%d",&k);
	for(int i=1;i<=k;i++){
		scanf("%d%d",&u,&v);
		value[u]=v;
		q.push((Node){u,v});
	}
	while(!q.empty()){
		u=q.top().id;
		v=q.top().value;
		q.pop();
		for(int i=head[u];i;i=nxt[i]){
			if(value[arrive[i]]!=-1){
				continue;
			}
			value[arrive[i]]=v+1;
			q.push((Node){arrive[i],v+1});
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=nxt[j]){
			if(ab(value[i]-value[arrive[j]])!=1){
				puts("No");
				return 0;
			}
		}
	}
	puts("Yes");
	for(int i=1;i<=n;i++){
		printf("%d\n",value[i]);
	}
	return 0;
}


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

ans = 0
f = 1
num = 0
for i in range(n):
    num += a[i]
    if f:
        if num <= 0:
            ans += 1 - num
            num = 1
        f = 0
    else:
        if num >= 0:
            ans += abs(-1 - num)
            num = -1
        f = 1

ans_2 = 0
f = 1
num = 0
for i in range(n):
    num += a[i]
    if f:
        if num >= 0:
            ans_2 += abs(-1 - num)
            num = -1
        f = 0
    else:
        if num <= 0:
            ans_2 += 1 - num
            num = 1
        f = 1

print(min(ans,ans_2))
        
            


Measured memory_bytes: 63216
#include <stdio.h>

int main(void)
{
    int N = 0;
    scanf("%d", &N);
    int i = 0;
    for (i = 1; i < 11; i++)
    {
        if ((i * 1000) >= N)
        {
            printf("%d", (i * 1000) - N);
            break;
        }
    }
    return 0;
}


Measured memory_bytes: 1732
n = int(input())

W = [input()]
s = W[0][-1]
flag = True

for i in range(n-1):
    w = input()
    if w[0] != s:
        flag = False
        break
    W.append(w)
    s = w[-1]

if len(set(W)) != n:
    flag = False

if flag:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 3060
module.exports=function(r){var t={};function e(n){if(t[n])return t[n].exports;var o=t[n]={i:n,l:!1,exports:{}};return r[n].call(o.exports,o,o.exports,e),o.l=!0,o.exports}return e.m=r,e.c=t,e.d=function(r,t,n){e.o(r,t)||Object.defineProperty(r,t,{enumerable:!0,get:n})},e.r=function(r){"undefined"!=typeof Symbol&&Symbol.toStringTag&&Object.defineProperty(r,Symbol.toStringTag,{value:"Module"}),Object.defineProperty(r,"__esModule",{value:!0})},e.t=function(r,t){if(1&t&&(r=e(r)),8&t)return r;if(4&t&&"object"==typeof r&&r&&r.__esModule)return r;var n=Object.create(null);if(e.r(n),Object.defineProperty(n,"default",{enumerable:!0,value:r}),2&t&&"string"!=typeof r)for(var o in r)e.d(n,o,function(t){return r[t]}.bind(null,o));return n},e.n=function(r){var t=r&&r.__esModule?function(){return r.default}:function(){return r};return e.d(t,"a",t),t},e.o=function(r,t){return Object.prototype.hasOwnProperty.call(r,t)},e.p="",e(e.s=0)}([function(r,t,e){e(1)(e(2).readFileSync("/dev/stdin","UTF-8").split("\n"))},function(r,t){function e(r,t){return function(r){if(Array.isArray(r))return r}(r)||function(r,t){var e=[],n=!0,o=!1,u=void 0;try{for(var i,f=r[Symbol.iterator]();!(n=(i=f.next()).done)&&(e.push(i.value),!t||e.length!==t);n=!0);}catch(r){o=!0,u=r}finally{try{n||null==f.return||f.return()}finally{if(o)throw u}}return e}(r,t)||function(){throw new TypeError("Invalid attempt to destructure non-iterable instance")}()}r.exports=function(r){var t=e(r[0].split(" ").map(function(r){return Number(r)}),2),n=t[0],o=t[1],u=r[1].split(" ").map(function(r){return Number(r)});u.push(o),u.sort(function(r,t){return r-t});var f=[];for(i=0;i<n;i++)f.push(u[i+1]-u[i]);for(var l=f[0],a=1;a<n;a++){for(var c=f[a],p=l;0!=p;){var s=c;c=p,p=s%p}l=c}console.log(l)}},function(r,t){r.exports=require("fs")}]);

Measured memory_bytes: 30544
#include<iostream>
#include<math.h>
#include<vector>
#include<algorithm>
#include<numeric>
#include<map>
#include<queue>
using namespace std;

int main(){
    int D;cin>>D;
    if(D==22)cout<<"Christmas Eve Eve Eve"<<endl;
    if(D==23)cout<<"Christmas Eve Eve"<<endl;
    if(D==24)cout<<"Christmas Eve"<<endl;
    if(D==25)cout<<"Christmas"<<endl;
    return 0;
}

Measured memory_bytes: 256
/*
    Author:zeke

    pass System Test!
    GET AC!!
*/
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using ll = long long;
using ld = long double;
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(), (x).end()
#define rep3(var, min, max) for (ll(var) = (min); (var) < (max); ++(var))
#define repi3(var, min, max) for (ll(var) = (max)-1; (var) + 1 > (min); --(var))
#define Mp(a, b) make_pair((a), (b))
#define F first
#define S second
#define Icin(s) \
    ll(s);      \
    cin >> (s);
#define Scin(s) \
    ll(s);      \
    cin >> (s);
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;
}
typedef pair<ll, ll> P;
typedef vector<ll> V;
typedef vector<V> VV;
typedef vector<P> VP;
ll mod = 1e9 + 7;
ll MOD = 1e9 + 7;
ll INF = 1e18;
// cout << "Case #" << index << " :IMPOSSIBLE";
const int MAX = 1e7;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++) {
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k) {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}
long long COM_smallK(ll n, ll k) {
    ll res = 1;
    rep3(i, n - k + 1, n + 1) {
        res *= i;
        res %= MOD;
    }
    return res * finv[k] % MOD;
}
int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(10);
    ll n,m;
    cin>>n>>m;
    COMinit();
    ll res=0;
    V reg(n);
    reg[0]=1;
    rep3(i,1,n){
        reg[i]=reg[i-1]*(m-n+i);
        reg[i]%=MOD;
    }
    reverse(all(reg));
 //   rep(i,n)cout<<reg[i]<<" ";
   // cout<<endl;
    rep3(i,1,n+1){
       /* if(i==n){
            if(i%2==0){
                res+=MOD;
                res--;
            }else{
                res++;
            }
            res%=MOD;
            break;
        }*/
        if(i%2==0){
            res+=MOD;
            ll f=COM(n,i)*reg[i-1];
            f%=MOD;
            res-=f;
            res+=MOD;
        }else{
            ll f=COM(n, i) * reg[i-1];
            f%=MOD;
            res += f;
        }
        res%=MOD;
     //   cout<<n<<" "<<i<<" "<<res<<" "<<reg[i-1]<<endl;
    }
    ll hoge=1;
    rep3(i,m-n+1,m+1){
        hoge*=i;
        hoge%=MOD;
    }
  //  cout<<res<<" "<<hoge<<endl;
    res=(hoge+MOD-res)%MOD;
   // cout<<res<<endl;
    //cout<<res<<endl;
    rep3(i,m-n+1,m+1){
        res*=i;
        res%=MOD;
    }
    cout<<res<<endl;
}


Measured memory_bytes: 241464
import numpy as np
q = int(input())
b = [True] * (10**5+1)
for i in range(2, 10**5):
    if not b[i]:
        continue
    x = 2 * i
    while x <= 10**5:
        b[x] = False
        x += i
b[0] = b[1] = False
a = [False] *  (10**5+1)
for i in range(1, 10**5, 2):
    if b[i] and b[int((i+1)/2)]:
        a[i] = True
cumsum = np.array(a).cumsum()
for _ in range(q):
    l, r = map(int, input().split())
    print(cumsum[r] - cumsum[l-1])

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

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

#define pb(x) push_back(x)
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repp(i, s, e) for (int i = (s); i < (e); i++)
#define all(x) x.begin(), x.end()

#define INF 2123456789
#define IINF 9123456789123456789

void use_cio() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
}

//--------------------------------------------------//
int chk[210];
int n;
int main() {
    use_cio();
    cin >> n;
    rep(i, 210) {
        if (!i) continue;
        int cnt = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) cnt++;
        }
        if (cnt == 8) chk[i] = 1;
    }
    int ans = 0;
    rep(i, n + 1) ans += (i % 2 && chk[i]);
    cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define ll long long
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main() {
    int H, W;
    cin >> H >> W;
    vector<string>a(H);
    for (int i=0; i<H; i++)cin >> a[i];

    for (int i=0; i<W+2; i++)cout << "#";
    cout << endl;
    
    for (int i=0; i<H; i++){
        cout << "#" << a[i] << "#" << endl;
    }
    for (int i=0; i<W+2; i++)cout << "#";
    cout << endl;
}

Measured memory_bytes: 256
// Aizu Vol-2 0286: Computation of Salary
// 2017.8.20 bal4u@uu
// 2017.11.5 retry

#include <stdio.h>

#define MAX 10000
#define MAX2 500000

typedef struct { int n, nxt, end; } WAK;
typedef struct { int nxt, t, e; } LNK;

WAK wak[MAX+5];
LNK lnk[MAX2+5]; int used;
int b[MAX+5];

char buf[100002], *p;
int getint()
{
	int n = 0;
	while (*p >= '0') n = (n<<3) + (n<<1) + (*p++ & 0xf);
	return n;
}

char tmp[13], *q;
void pr(int n)
{
	if (!n) { *p++ = '0'; return; }
	q = tmp; while (n) {
		*++q = '0' + (n % 10);
		n /= 10;
	}
	while (*q) *p++ = *q--;
}

int main()
{
	int N, M, L, i, j, k, ans;
	WAK *w;

	fgets(p=buf, 20, stdin), N = getint(), p++, M = getint();
	while (fgets(p=buf, 30, stdin) && *p != '0') {
		w = wak + getint(), p++, lnk[used].t = getint(), p++, lnk[used].e = getint();
		if (w->n == 0) w->nxt = used;
		else lnk[w->end].nxt = used;
		w->end = used++, w->n++;
	}
	fgets(p=buf, 10, stdin), L = getint();
	while (L--) {
		fgets(p=buf, 100000, stdin);
		for (i = 1; i <= M; i++) b[i] = getint(), p++;
		p = buf;
		for (w = wak+1, i = 1; i <= N; i++, w++) {
			if (i > 1) *p++ = ' ';
			if (w->n == 0) { *p++ = '0'; continue; }
			for (ans = 0, k = w->nxt, j = w->n; j > 0; j--, k = lnk[k].nxt)
				ans += lnk[k].e * b[lnk[k].t];
			pr(ans);
		}
		*p = 0,	puts(buf);
	}
	return 0;
}

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

using namespace std;

#define rep(i, n) for(int i = 0; i < (int)n; ++i)
#define FOR(i, a, b) for(int i = a; i < (int)b; ++i)
#define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i)

typedef long long ll;
typedef long double ld;

const ll INF = 1e18;
const int Inf = 1e9;
const double EPS = 1e-9;
const int MOD = 1e9 + 7;

template <typename T>
class SegmentTree {
    public:
        int n;
        vector<T> data;
        T e;
        function<T(T, T)> operation;
        function<T(T, T)> process;

        SegmentTree() {}
        SegmentTree(int n_, T e_, function<T(T, T)> operation_, 
            function<T(T, T)> process_) : e(e_), operation(operation_), process(process_) {
            n = 1;
            while (n < n_) n <<= 1;
            data.assign(2 * n, e);
        }

        void build() {
            for (int i = n - 1; i > 0; --i) {
                data[i] = operation(data[i * 2 + 0], data[i * 2 + 1]);
            }
        }

        void set(int idx, T v) {
            data[idx + n] = process(data[idx + n], v);
        }

        void update(int idx, T v) {
            idx += n;
            data[idx] = process(data[idx], v);
            while (idx >>= 1) {
                data[idx] = operation(data[2 * idx + 0], data[2 * idx + 1]);
            }
        }

        T query(int a, int b) {
            return query(a, b + 1, 1, 0, n);
        }

        T query(int a, int b, int k, int l, int r) {
            if (a >= r || b <= l) return e;
            if (a <= l && b >= r) return data[k];
            T c = query(a, b, 2 * k + 0, l, (l + r) / 2);
            T d = query(a, b, 2 * k + 1, (l + r) / 2, r);
            return operation(c, d);
        }

        T operator[](int idx) {
            return data[idx + n];
        }
};

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    SegmentTree<ll> seg = SegmentTree<ll>(n, 0, 
            [](ll a, ll b) { return a + b; }, [](ll a, ll b) { return a + b; });
    ll res = 0;
    vector<ll> a(n), b(n);
    rep (i, n) {
        cin >> a[i];
        b[i] = a[i];
    }
    sort(b.begin(), b.end());
    map<ll, int> mp;
    int start = 0;
    rep (i, n) mp[b[i]] = start++;
    rep (i, n) {
        res += i - seg.query(0, mp[a[i]] - 1);
        seg.update(mp[a[i]], 1);
    }
    cout << res << endl;

    return 0;
}




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

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

const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;

#define pb push_back
#define REP(i, n) for (int i = 0; i < (int)(n); ++i)
#define REP2(i, b, e) for (int i = (b); i <= (int)(e); ++i)
#define DEBUG(x) cout << #x << ": " << (x) << endl
#define DEBUGA(a) cout << #a << ": "; for (const auto& v: (a)) cout << v << endl
#define ALL(x) x.begin(), x.end()

ll N, K;
vi A, F;

bool ok(ll x) {
    ll sum = 0;
    REP(i, N) {
        sum += max(0LL, A[i] - x / F[i]);
    }
    return sum <= K;
}

signed main() {
    cin >> N >> K;

    A.resize(N), F.resize(N);
    REP(i, N) cin >> A[i];
    REP(i, N) cin >> F[i];

    sort(ALL(A));
    sort(ALL(F), greater<int>());

    // 二分探索
    ll left = -1, right = 1e12;
    while (left + 1 < right) {
        ll mid = (left + right) / 2;
        if (ok(mid)) {
            right = mid;
        } else {
            left = mid;
        }
    }
    cout << right << endl;
}


Measured memory_bytes: 1792
while 1:
    n,l = map(int,raw_input().split())
    if n == 0: break
    
    tube = [[] for i in xrange(l-1)]
    for i in xrange(1,n+1):
        d,p = raw_input().split()
        tube[int(p)-1].append(i if d == "R" else -i)
    t = num = 0
    while sum(len(ele) for ele in tube) != 0:
        for s in [-1,1]:
            for i in range(l-1)[::s]:
                for a in tube[i]:
                    if -s*a > 0:
                        tube[i].remove(a)
                        if i == (l-2 if s == -1 else 0):
                            num = abs(a)
                        else:
                            tube[i-s].append(a)
        for i in xrange(l-1):
            if len(tube[i]) > 1:
                tube[i] = [-a for a in tube[i]]
        t += 1
    print t,num

Measured memory_bytes: 4276
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdlib>
#include<vector>
#include<queue>

using namespace std;


int main() {
	int n, d;

	cin >> n >> d;

	int ans = 0;

	d = 2 * d + 1;

	while (n>0) {
		n -= d;
		ans++;
	}

	cout << ans;
	return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <math.h>
#include <vector>
#include <map>
#include <set>
#include <climits>
#include <algorithm>
using namespace std;


int main() 
{
	long long n;
	cin>>n;
	long long res=0;
	for(int i=1;i<=n;++i){
		if(i%15!=0 &&i%3!=0 && i%5!=0){
			res+=i;

		}
	}
	cout<<res;
	return 0;

}


Measured memory_bytes: 3624
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.*;

public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long a0 = sc.nextLong();
        BigDecimal MAX_LIMIT = new BigDecimal(BigInteger.valueOf(10), -17);
        BigDecimal result = new BigDecimal(a0);
        for (int i=1; i<n; i++) {
            long ai = sc.nextLong();
            result = result.multiply(new BigDecimal(ai));
            if (result.compareTo(MAX_LIMIT) > 0) {
                result = new BigDecimal(-1);
                for (int j=i+1; j<n; j++) {
                    long a = sc.nextLong();
                    if (a == 0) {
                        result = BigDecimal.ZERO;
                    }
                }
                break;
            }
        }
        System.out.println(result.toPlainString());
    }
}

Measured memory_bytes: 49424
import bisect

D=[]
N=[]
count=0

def insert(D,N,count,key,x):
    y=bisect.bisect_left(D,key)
    if y<count and D[y]==key:
        N[y]=x
    else:
        D.insert(y,key)
        N.insert(y,x)
        count+=1
    return D,N,count

def get(D,N,count,key):
    y=bisect.bisect_left(D,key)
    if y<count and D[y]==key:
        print(N[y])
    else:
        print(0)

def erase(D,N,count,key):
    y=bisect.bisect_left(D,key)
    if y<count and D[y]==key:
        D.pop(y)
        N.pop(y)
        count-=1
    return D,N,count

q=int(input())
for i in range(q):
    query=list(map(str,input().split()))
    query[0]=int(query[0])
    if query[0]==0:
        D,N,count=insert(D,N,count,query[1],int(query[2]))
    elif query[0]==1:
        get(D,N,count,query[1])
    else:
        D,N,count=erase(D,N,count,query[1])



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

const int64_t INF = 1e18;
struct MinCostFlow{
    struct edge { int64_t to, cap, cost, rev;};

    int N, S, T;
    int64_t flow;
    int64_t cost;
    vector<vector<edge>> G;
    vector<pair<int, int>> prv; // {v, e};
    vector<int64_t> h;

    MinCostFlow(int N, int S, int T):N(N), S(S), T(T){
        flow = cost = 0;
        G.resize(N);
        prv.resize(N);
        h.resize(N);
    }

    void add_edge(int64_t from, int64_t to, int64_t cap, int64_t cost){
        G[from].push_back({to, cap, cost, G[to].size()});
        G[to].push_back({from, 0, -cost, G[from].size()-1});
    }

    int64_t calculate(int64_t f){
        typedef pair<int64_t, int> P;
        
        int64_t res = 0;
        vector<int64_t> dist(N);

        while(f > flow){
            priority_queue<P, vector<P>, greater<P>> que;
            fill(dist.begin(), dist.end(), INF);
            dist[S] = 0;
            que.push({0, S});
            while(que.size()){
                auto p = que.top(); que.pop();
                int64_t d = p.first;
                int i = p.second;
                if(d > dist[i]) continue;
                for(int idx=0; idx<G[i].size(); idx++){
                    auto& e = G[i][idx];
                    int j = e.to;
                    int64_t d2 = d + e.cost + h[i] - h[j];
                    if(e.cap > 0 && dist[j] > d2){
                        dist[j] = d2;
                        prv[j] = {i, idx};
                        que.push({dist[j], j});
                    }
                }
            }
            if(dist[T] == INF) return -1;
            for(int i=0; i<N; i++) h[i] += dist[i];
            
            int64_t d = f - flow;
            for(int i=T; i!=S; i=prv[i].first){
                auto& e = G[prv[i].first][prv[i].second];
                d = min(d, e.cap);
            }
            flow += d;
            res += d * h[T];
            for(int i=T; i!=S; i=prv[i].first){
                auto& e = G[prv[i].first][prv[i].second];
                e.cap -= d;
                G[i][e.rev].cap += d;
            }
        } 
        return res;
    }
};

int main(){
    int N, RX[1000], RY[1000], RC[1000], BX[1000], BY[1000], BC[1000];
    cin >> N;
    for(int i=0; i<N; i++) cin >> RX[i] >> RY[i] >> RC[i];
    for(int i=0; i<N; i++) cin >> BX[i] >> BY[i] >> BC[i];
    int sum = accumulate(RC, RC+N, 0);

    int64_t OFFSET = 1e10;

    int M[] = {2000, 2001, 2002, 2003};
    int cx[] = {1, 1, -1, -1};
    int cy[] = {1, -1, 1, -1};
    int S = 2004, T = 2005;
    MinCostFlow solver(T+1, S, T);
    for(int i=0; i<N; i++){
        solver.add_edge(S, i, RC[i], 0);
        for(int k=0; k<4; k++){
            int64_t c = cx[k]*RX[i] + cy[k]*RY[i];
            solver.add_edge(i, M[k], RC[i], OFFSET - c);
            c = -cx[k]*BX[i] - cy[k]*BY[i];
            solver.add_edge(M[k], 1000+i, BC[i], OFFSET - c);
        }
        solver.add_edge(1000+i, T, BC[i], 0);
    }
    int64_t res = solver.calculate(sum);
    int64_t ans = 2*OFFSET*sum - res;
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 1480
#include <iostream>
#include <string>
#include <algorithm>
#include <utility> 
#include <unordered_set>
#include <vector>
#include <list> 
#include <string>
#include <iterator> 
#include <deque>
#include <array>
#include <forward_list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <cmath>
#include <climits>
#include <bitset>
using namespace std;

#define N 1e5
#define EPS 1e-9

long long arr[(int)N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	long long lim = 1e18, ans;
	int n;
	cin >> n;
	for (int i = 0; i < n; ++i) cin >> arr[i];
	sort(arr, arr + n);
	ans = 1;
	for (int i = 0; i < n; ++i) {
		if (arr[i] == 0) {
			ans = 0;
			break;
		}

		if (ans > lim/arr[i]) {
			ans = -1;
			break;
		}

		ans *= arr[i];
	}

	cout << ans << '\n';
}


Measured memory_bytes: 3908
#include <stdio.h>
int main(void){
    int a,b,d,r;
    double a1,b1,f;
    scanf("%d %d",&a,&b);
    a1=a;
    b1=b;
    d = a / b;
    r = a % b;
    f = a1 / b1;
    printf("%d %d %f",d,r,f);
    return 0;
}

Measured memory_bytes: 636
#include <iostream>
#include<vector>

#include <algorithm>




using namespace std;



















int main (){
int n,k,q;
  int t=0;

  cin>>n;
  cin>>k;
 
  
vector<int> vec(n);



for(int i=0; i<vec.size(); i++){
    cin>>vec.at(i);

}
  sort(vec.begin(),vec.end());
  reverse(vec.begin(),vec.end());

for(int i=0; i<vec.size(); i++){
    if(k<=vec.at(i))t++;
  else{break;}

}
  
  
  cout<<t<<endl;
  
  
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
int main(){
	int h,w,n,m;
	n=m=0;
	cin>>h>>w;
	char a[h][w];
	for(int i=0;i<h;i++){
		cin>>a[i];
	}
		n=m;
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				if(a[i][j]=='#')break;
				if(j==w-1){
					for(int j=0;j<w;j++){
						a[i][j]='0';
					}
					m++;
				}
			}
		}
		for(int j=0;j<w;j++){
			for(int i=0;i<h;i++){
				if(a[i][j]=='#')break;
				if(i==h-1){
					for(int i=0;i<h;i++){
						a[i][j]='0';
					}
					m++;
				}
			}
		}
	int x;
	x=0;
	for(int i=0;i<h;i++){
		for(int j=0;j<w;j++){
			if(a[i][j]!='0')cout<<a[i][j];
			if(a[i][j]=='0')x++;
		}
		if(x!=w)cout<<endl;
		x=0;
	}
}

Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
  int N, K, Q;
  cin >> N >> K >> Q;
  vector<int> S(N, 0);
  int A;
  for(int i = 0; i < Q; i++) {
    cin >> A;
    S[A - 1]++;
  }
  for(int i = 0; i < N; i++) {
    if(S[i] + K - Q <= 0) {
      cout << "No" << endl;
    } else {
      cout << "Yes" << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1024
#include <stdio.h>
#include <math.h>
#include <iostream>
#include<string>
#include<vector>
#include <algorithm>
#define REP(a,b) for (int i = a; i <= (b); i++)
using namespace std;
int main() {
	int b, a;
	cin >> a >> b;
	if (a % 500 <= b) {
		cout << "Yes" << endl;
	}
	else cout << "No" << endl;
}

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

using namespace std;

int main(){
	while(1){
	int d[1002];
	int n,m;
	cin >> n >> m;
	if(n == 0 && m == 0)break;
	for(int i = 1;i <= n;i++)cin >> d[i];
	int nau = 1;
	int ans = 0;
	while(m--){
		int tmp;
		cin >> tmp;
		nau += tmp;
		ans++;
		if(nau >= n)break;
		nau += d[nau];
		if(nau >= n)break;
	}
	printf("%d\n",ans);
	while(m--)cin >> ans;
	}
	return 0;
}


Measured memory_bytes: 1148