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

using namespace std;

#define rep(i, a, b) for (int i = (a), i##_end_ = (b); i <= i##_end_; ++i)
#define drep(i, a, b) for (int i = (a), i##_end_ = (b); i >= i##_end_; --i)
#define clar(a, b) memset((a), (b), sizeof(a))
#define debug(...) fprintf(stderr, __VA_ARGS__)
template <typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T sqr(const T &a) { return a * a; }
typedef long long LL;
typedef long double LD;
void procStatus() {
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}
LL read() {
	LL x = 0, flag = 1;
	char ch = getchar();
	for (;!isdigit(ch); ch = getchar()) if (ch == '-') flag *= -1;
	for (;isdigit(ch); ch = getchar()) x = x * 10 + ch - 48;
	return x * flag;
}
void write(LL x) {
	if (x < 0) putchar('-'), x = -x;
	if (x >= 10) write(x / 10);
	putchar(x % 10 + '0');
}

const int Maxn = 5e5 + 9, Mod = 998244353;
int mmul(int a, int b){
    int ret = 1ll * a * b % Mod;
    return ret;
}
int mplus(int a, int b) {
	a += b;
	if (a >= Mod) a -= Mod;
	return a;
}
int fpm(int base, int tims) {
	int r = 1;
	for (; tims; base = mmul(base, base), tims >>= 1) 
		if (tims & 1) r = mmul(r, base);
	return r;
}
int fac[Maxn], inv[Maxn], invFac[Maxn];

void Init() {
	fac[0] = 1;
	rep (i, 1, Maxn - 1) fac[i] = mmul(fac[i - 1], i);
	inv[1] = 1;
	rep (i, 2, Maxn - 1) inv[i] = mmul(inv[Mod % i], Mod - Mod / i);
	invFac[0] = 1;
	rep (i, 1, Maxn - 1) invFac[i] = mmul(invFac[i - 1], inv[i]);
}

int C(int n, int m) {
	if (n < m || n < 0 || m < 0) return 0;	
	return mmul(fac[n], mmul(invFac[n - m], invFac[m]));
}

int n, m;
int f(int k) {
	return mmul(C(n, k), mmul(C(m, k), mmul(fac[k], mmul(fpm(n + 1, m - k), fpm(m + 1, n - k)))));
}

void Solve() {
	n = read(), m = read();
	int ans = 0;
	rep (k, 0, min(n, m)) {
		int coef = (k & 1) ? (Mod - 1) : 1;
		ans = mplus(ans, mmul(coef, f(k)));
	}
	cout << ans << endl; 
}

int main() {
//	freopen("bosky.in", "r", stdin);
//	freopen("bosky.out", "w", stdout);

	Init();
	Solve();	

#ifdef Qrsikno
//	procStatus();
	debug("\nRunning time: %.3lf(s)\n", clock() * 1.0 / CLOCKS_PER_SEC);
#endif
	return 0;
}


Measured memory_bytes: 6144
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(n); i++)
#define REP2(i,x,n) for(int i=x; i<(n); i++)
#define ALL(n) begin(n),end(n)
#define sz(x) int(x.size())
using ll = long long;
using P = pair<int,int>;
const ll LLINF = numeric_limits<long long>::max();
const int mod = 1000000007;
const int INF = 1001001001;

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

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

    sort(P.begin(),P.end());

    int sum=0;
    for(int i=0;i<K;i++){
        
        sum += P[i];
    }
    cout << sum;

    return 0;
}

Measured memory_bytes: 3628
#pragma GCC optimize ("-O3")
    #include <bits/stdc++.h>  
     
    using namespace std;
     
    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 = 998244353;
    #define forn(i,e) for(ll i = 0; i < e; i++)
    #define forsn(i,s,e) for(int 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 1e18
    #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())
     
    ll mpow(ll a, ll b){
        if(b >= (MOD-1)) b %= (MOD-1);
        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(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; 
    }
    ll range(ll l, ll r){
        return l + rand()%(r-l+1);
    }

    int main()
    {
        int n,k;
        cin>>n>>k;
        vector<bool>arr(n+1,false);
        for(int i=0;i<k;i++)
        {
            int d;cin>>d;
            for(int i=0;i<d;i++)
            {
                int a;cin>>a;
                arr[a]=true;
            }
        }
        int ans=0;
        for(int i=1;i<n+1;i++)
        {
            if(!arr[i])ans++;
        }
        cout<<ans<<endl;
        return 0;
    }

Measured memory_bytes: 3616
#include <algorithm>
#include <climits>
#include <iostream>
#include <vector>
using namespace std;

typedef long long ll;
ll MOD = 1000000007;

struct bit {
	vector<ll> v;
	bit(int n) : v(n + 1) {}
	ll sum(int i) {
		ll res = 0;
		for (; i > 0; i -= i & -i) res += v[i];
		return res;
	}
	void add(int i, ll x) {
		for (i++; i < v.size(); i += i & -i) v[i] += x;
	}
};

int B = 1000;

int main() {
	int N; cin >> N;
	vector<int> p(N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &p[i]);
		p[i]--;
	}
	int Q; cin >> Q;
	vector<vector<int> > query(N);
	vector<int> l(Q), r(Q);
	for (int q = 0; q < Q; q++) {
		scanf("%d%d", &l[q], &r[q]);
		l[q]--; r[q]--;
		query[r[q]].push_back(q);
	}
	vector<int> index(N, -1);
	bit bt(N);
	vector<int> A(N / B + 1);
	vector<vector<int> > v(N / B + 1);
	vector<vector<ll> > sum(N / B + 1, vector<ll>(1));
	ll cur = 0;
	vector<ll> ans(Q);
	for (int i = 0; i < N; i++) {
		for (int x = N - 1; x > p[i];) {
			if (x % B == B - 1 && x - B >= p[i]) {
				A[x / B]++;
				cur += v[x / B].size();
				x -= B;
			}
			else {
				if (index[x] != -1) {
					bt.add(index[x], 1);
					cur++;
				}
				x--;
			}
		}
		int x = p[i];
		index[x] = i;
		ll prev = sum[x / B].back();
		v[x / B].push_back(i);
		sum[x / B].push_back(prev + A[x / B]);
		for (int k = 0; k < query[i].size(); k++) {
			int q = query[i][k];
			ans[q] = cur - bt.sum(l[q]);
			for (int i = 0; i <= N / B; i++) {
				int j = lower_bound(v[i].begin(), v[i].end(), l[q]) - v[i].begin();
				ans[q] -= (ll)j * A[i] - sum[i][j];
			}
		}
	}
	for (int q = 0; q < Q; q++)
		printf("%lld\n", ans[q]);
}

Measured memory_bytes: 13740
x=list(map(int, input().split()))
x.sort()
ans=x[2]-x[1]
x[0]=x[0]+ans
x[1]=x[1]+ans
if ((x[2]-x[0])%2)==1:
	print(ans+((x[2]-x[0])//2)+2)
else:
	print(ans+(x[2]-x[0])//2)

Measured memory_bytes: 3060
#include <vector>
#include <numeric>
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <iomanip>
using namespace std;
typedef vector<double> VecD;
#define rep(n) for(int i=0;i<n;i++)
#define PB push_back

class Point{
friend const double operator*(const Point &, const Point &);
friend const Point operator*(const double, const Point &);
friend const Point operator*(const Point &, const double);
friend const Point operator+(const Point &, const Point &);
friend const Point operator+(const double, const Point &);
friend const Point operator+(const Point &, const double);
friend const Point operator-(const Point &);
friend const Point operator-(const Point &, const Point &);
friend const Point operator-(const double, const Point &);
friend const Point operator-(const Point &, const double);

public:
	Point(){};
	Point(VecD v){
		point = v;
	}
	VecD point;
};

const double operator*(const Point &p0, const Point &p1){ return inner_product( p0.point.begin(), p0.point.end(), p1.point.begin(), 0); }
const Point operator*(const double a, const Point &p1){
	VecD v;
	for(VecD::const_iterator iter1=p1.point.begin();iter1!=p1.point.end();iter1++) v.PB(*iter1 * a);
	const Point p(v);
	return p;
}
const Point operator* (const Point &p, const double a){return a*p;}
const Point operator+(const Point &p0, const Point &p1){
	VecD v;
	VecD::const_iterator iter0 = p0.point.begin();
	for(VecD::const_iterator iter1=p1.point.begin();iter1!=p1.point.end();iter1++){
		v.PB(*iter0 + *iter1);
		iter0++;
	}
	const Point p(v);
	return p;
}
const Point operator+(const double a, const Point &p1){
	VecD v;
	for(VecD::const_iterator iter1=p1.point.begin();iter1!=p1.point.end();iter1++){
		v.PB(*iter1 + a);
	}
	const Point p(v);
	return p;
}
const Point operator+(const Point &p1, const double a){return a+p1;}
const Point operator-(const Point &p1){return (-1)*p1;}
const Point operator-(Point &p0, Point &p1){ return p0+(-p1); }
const Point operator-(double a, Point &p1){ return a+(-p1); }
const Point operator-(Point &p1, double a){return (-a)+p1;}

const Point projection(const Point &p1, const Point &p2){
	// cout << p1*p2 << endl;
	return ((p1*p2) / (p1*p1)) * p1;
}

int main(void){

	double xp0, yp0, xp1, yp1; cin>>xp0>>yp0>>xp1>>yp1;
	int q; cin >> q;
	VecD v0; v0.PB(xp0); v0.PB(yp0); Point p0(v0);
	VecD v1; v1.PB(xp1); v1.PB(yp1); Point p1(v1);
	p1 = p1-p0;
	// cout << p1.point[0] << " " << p1.point[1] << endl;
	rep(q){
		double xp2,yp2; cin>>xp2>>yp2;
		VecD v2; v2.PB(xp2); v2.PB(yp2); Point p2(v2);
		p2 = p2-p0;
		Point ret = projection(p1, p2);
		ret = ret+p0;
		cout << fixed << setprecision(10) << ret.point[0] << " " << fixed << setprecision(10) << ret.point[1] << endl;
	}
}

Measured memory_bytes: 1320
#include<bits/stdc++.h>
using namespace std;
#define int long long int
#define ld long double
#define MOD 1000000007
#define endl "\n"
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(var) (var).begin(), (var).end()
#define MAXX 9000000000000000000
#define pii pair<int,int>
#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pair<int,int> > 
#define vvpi vector<vector<pair<int,int> > >

int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif

	int n,a[200005],i,x=0;
	cin >> n;
	for(i=0;i<n;i++)
	{
		cin >> a[i];
	}
	sort(a, a+n);

	for(i=0;i<n-1;i++)
	{
		x += a[n - (i+1)/2 - 1];
	}
	// cout << a[n-1] << endl;
	cout << x;

	return 0;
}

Measured memory_bytes: 5212
N = int(input())
A = list(map(int, input().split()))
A_ans = []
count = 0

for i in range(0, N):
    if A[i] % 2 == 0:
        A_ans.append(A[i])

for i in range(0, len(A_ans)):
    if A_ans[i] % 3 == 0 or A_ans[i] % 5 == 0:
        count += 1

if count == len(A_ans):
    print('APPROVED')
else:
    print('DENIED')


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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m;
    cin>>n>>m;
    int a[n+1];
    int b[n+1];
    for(int i=1;i<=n;i++){
        b[i]=1;
    }
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    while(m--){
        int x,y;
        cin>>x>>y;
        if(a[x]==a[y]){
            b[x]=b[y]=0;
        }
        else if(a[x]>a[y]){
            b[y]=0;
        }
        else{
            b[x]=0;
        }
    }
    int ct=0;
    for(int i=1;i<=n;i++){
        if(b[i]==1){
            ct++;
        }
    }
    cout<<ct;
    return 0;
}

Measured memory_bytes: 4428
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>
#include <math.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> P;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define REP(i, n) for (ll i = 0; i < (n); ++i)
#define REPR(i, n) for (ll i = (n) - 1; i >= 0; --i)
#define FOR(i, n, m) for (ll i = (n); i < (m); ++i)
#define FORR(i, n, m) for (ll i = (m) - 1; i >= (n); --i) 
#define FORE(x, xs) for (auto &x: (xs))
#define ALL(v) v.begin(), v.end()
#define ZERO(a) memset(a,0,sizeof(a))

const int INF = 1000000009;
const int MOD = 1000000007;
static const double EPS = 1e-14;

ll R, C, N, x, y, xx, yy;
vector<P> vp;
stack<ll> sll;

/// 左上から時計回りで
ll pos(ll x, ll y) {
  if (y == 0) return x;
  if (x == R) return x+y;
  if (y == C) return C+2*R-x;
  if (x == 0) return 2*(R+C)-y;
}

int main() {
  cin >> R >> C >> N;
  REP(i, N) {
    cin >> x >> y >> xx >> yy;
    if (x*y*(x-R)*(y-C) == 0 && xx*yy*(xx-R)*(yy-C) == 0) { /// 両点とも辺上
      vp.push_back(P{pos(x, y), i});
      vp.push_back(P{pos(xx, yy), i});
    }
  }

  sort(ALL(vp));
  REP(i, vp.size()) {
    ll index = vp[i].second;
    if (!sll.empty() && sll.top() == index) sll.pop();
    else sll.push(index);
  }

  cout << ((sll.empty()) ? "YES" : "NO") << endl;

  return 0;
}

Measured memory_bytes: 6256
//
// Created by wulang on 10/23/16.
//

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int N=100000+10;
ll a[N], b[N];
ll x[N], y[N];
ll x2[N], y2[N];
ll n;
const ll MOD=1000000000+7;

int main(int argc, char *argv[]) {
    if (argc == 2) {
        freopen(argv[1], "r", stdin);
    }


    while(cin>>n) {
        for(int i=1;i<=n;i++) cin>>a[i];
        for(int i=1;i<=n;i++) cin>>b[i];


    for(int i=1;i<=n;i++) {
        x[i]=x2[i]=1;
    }

    x[1]=a[1];
    y[1]=a[1];
    for(int i=2;i<=n;i++) {
        if(a[i]==a[i-1]) y[i]=a[i];
        else {
            x[i]=y[i]=a[i];
        }
    }

    x2[n]=y2[n]=b[n];
    for(int i=n-1;i>=1;i--) {
        if(b[i]==b[i+1]) y2[i]=b[i];
        else {
            y2[i]=x2[i]=b[i];
        }
    }

    bool tag=true;
    ll ans=1;
    for(int i=1;i<=n;i++) {
        ll xx = max(x[i],x2[i]);
        ll yy = min(y[i], y2[i]);
        if(xx>yy) {
            tag=false;
            ans=0;
            break;
        }

        ans = ans*(yy-xx+1)%MOD;

    }

    cout<<ans<<endl;

    }

    return 0;
}

Measured memory_bytes: 4992
/*input 
3 5 7 5
*/

#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/rope>

using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
 
typedef long long ll;
typedef long double ld;
typedef complex<ld> cd;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<cd> vcd;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;

#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define F0R(i, a) for (int i = 0; i < (a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)

#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize

const int MOD = 1000000007;
const ll INF = 1e18;
const int MXN = 41;
const int MXM = (1 << 17) + 1;
const ld PI = 4*atan((ld)1);

int N, X, Y, Z;
int dp[MXN][MXM];
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> N >> X >> Y >> Z;

	dp[0][0] = 1;
	int mask = 1 << (X + Y + Z);
	int ansmask = (1 << (Z - 1)) + (1 << (Y + Z - 1)) + (1 << (X + Y + Z - 1));
	F0R(i, N) {
		F0R(j, mask + 1) {
			if (dp[i][j] == 0) continue;
			FOR(d, 1, 11) {
				if (j == mask) {
					dp[i + 1][mask] = (dp[i + 1][mask] + dp[i][mask]) % MOD;
					continue;
				}
				int nmask = ((j << d) | (1 << (d - 1))) & (mask - 1);
				//cout << nmask << '\n';
				if ((nmask & ansmask) == ansmask) nmask = mask;
				//cout << (i + 1) << " " << nmask << '\n';
				dp[i + 1][nmask] = (dp[i + 1][nmask] + dp[i][j]) % MOD;
			}
		}
	}
	cout << dp[N][mask] << '\n';
}



Measured memory_bytes: 19328
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <math.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <sstream>
#include <iostream>
#include <time.h>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <string.h>
#define sf scanf
#define pf printf
#define lf double
#define ll long long
#define p123 printf("123\n");
#define pn printf("\n");
#define pk printf(" ");
#define p(n) printf("%d",n);
#define pln(n) printf("%d\n",n);
#define s(n) scanf("%d",&n);
#define ss(n) scanf("%s",n);
#define ps(n) printf("%s",n);
#define sld(n) scanf("%lld",&n);
#define pld(n) printf("%lld",n);
#define slf(n) scanf("%lf",&n);
#define plf(n) printf("%lf",n);
#define sc(n) scanf("%c",&n);
#define pc(n) printf("%c",n);
#define gc getchar();
#define re(n,a) memset(n,a,sizeof(n));
#define len(a) strlen(a)
using namespace std;
//https://codeforces.com/contest/1228/problems
//https://codeforces.com/contest/1228/submit
int main() {
    int n;
    s(n)
    int count0 = 0;
    int count1 = 0;
    int x;

    for(int i = 0; i < n; i ++) {
        s(x)
        if(x % 4 == 0) {
            count0 ++;
        }else if(x % 2 == 0){
            count1 ++;
        }
    }
    if(n <= count0*2+1){
        puts("Yes");
    }else{
        n-= count0*2;
        if(n <= count1){
            puts("Yes");
        }else{
            puts("No");
        }
        
        
        
    }
    
    
    return 0;
}


Measured memory_bytes: 256
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n, k = intin()
    alist = intina()

    for i, a in enumerate(alist):
        if a == 1:
            i1 = i
            break

    if i1 % (k - 1):
        left = i1 // (k - 1) + 1
    else:
        left = i1 // (k - 1)

    if left == 0:
        right_pos = n - 1
    else:
        right_pos = n - (left * (k - 1) + 1)

    if right_pos % (k - 1):
        right = right_pos // (k - 1) + 1
    else:
        right = right_pos // (k - 1)

    print(left + right)


if __name__ == '__main__':
    main()


Measured memory_bytes: 14452
def main():
    N, A, B = map(int, input().split())
    if A > B or (N <= 1 and A != B):
        print(0)
        return
    ans = (A + B * (N-1)) - (A * (N-1) + B) + 1
    print(ans)


if __name__ == "__main__":
    main()


Measured memory_bytes: 38256
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
const int MX = 100005;
const long long INF = 1e15;
using P = pair<long long, int>;
int n, m, s[2], u, v, a[2], from, to;
long long dist[2][MX], ac, cost, ans[MX];
vector<P> G[2][MX];
priority_queue<P, vector<P>, greater<P>> qu;
void dijkstra(int s, int f){
	fill(dist[f], dist[f]+n, INF);
	qu.push(P(dist[f][s] = 0,s));
	while(!qu.empty()){
		tie(ac,from) = qu.top(); qu.pop();
		if(dist[f][from] == ac) for(P it: G[f][from]){
			tie(cost, to) = it; cost += ac;
			if(dist[f][to] > cost) qu.push(P(dist[f][to] = cost, to));
		}
	}
}
int main(){
	scanf("%d%d%d%d", &n, &m, s, s+1);
	s[0]--; s[1]--;
	rep(i,m){
		scanf("%d%d%d%d", &u, &v, a, a+1);
		u--; v--;
		rep(j,2){
			G[j][u].push_back(P(a[j],v));
			G[j][v].push_back(P(a[j],u));
		}
	}
	rep(i,2) dijkstra(s[i],i);
	for(int i = n-1; i >= 0; i--) ans[i] = max(ans[i+1], INF - dist[0][i] - dist[1][i]);
	rep(i,n) printf("%lld\n", ans[i]);
}

Measured memory_bytes: 19704
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
#define REP(i, n) for(int (i)=0; (i)<(n); (i)++)
#define COUT(a) cout << (a);
#define ENDL cout << "\n";
int main() {
    int n,k,count=0;
    scanf("%d %d\n",&n,&k);
    for(int i=1; i<=n;i+=2) count++;
    if(count<k) COUT("NO")
    else COUT("YES")
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(obj) begin(obj), end(obj)
#define debug(x) cerr << #x << ": " << x << '\n'
using namespace std;
template <class T>
vector<T> make_vec(size_t a) {
    return vector<T>(a);
}
template <class T, class... Ts>
auto make_vec(size_t a, Ts... ts) {
    return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}
template <class T>
bool chmax(T &a, const T &b) {
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    if (b < a) {
        a = b;
        return 1;
    }
    return 0;
}

using ll = long long;
using ull = unsigned long long;
const int INF = 1e9;
// const int MOD = 1e9 + 7;

int main() {
    string T;
    cin >> T;
    for (int i = 0; i < (int)T.size(); i++) {
        if (T[i] == '?') {
            T[i] = 'D';
        }
    }
    cout << T << endl;
}


Measured memory_bytes: 3756
#include <bits/stdc++.h>
        using namespace std;
   #define int long long
   #define PP pair<int,pair<int,int>>
const int MAX = 1000001;
const int MOD =1000000007;
const int INV2 = (MOD+1)/2;



     signed main(){
 string s,t;
 cin>>s>>t;
 for(int i=0;i<s.size();i++)if(s[i]!=t[i]){
   cout<<"No"<<endl;
   return 0;
 }
 cout<<"Yes"<<endl;
 return 0;
 




}


        


Measured memory_bytes: 3624
s = input()
N = len(s)
ls = [0] + [i for i in range(1,N) if (s[i-1]=='L' and s[i] == 'R')]
ls.append(N)
#print(ls)
ls2 = [(ls[i],ls[i+1]) for i in range(len(ls)-1)]
#print(ls2)
ls3 = [i for i in range(1,N) if (s[i-1]=='R' and s[i] == 'L')]
#print(ls3)
res = ['0']*N
for i,tp in enumerate(ls2):
    for j in range(tp[0],tp[1]):
        res[ls3[i]] = str((tp[1]-ls3[i]-1)//2+(ls3[i]-tp[0])//2+1)
        res[ls3[i]-1] = str((tp[1]-ls3[i])//2+(ls3[i]-tp[0]-1)//2+1)
print(' '.join(res))


Measured memory_bytes: 17724
<?php
    $s = explode(' ', trim(fgets(STDIN)));
    $ans = 0;
    if($s[0]>=13){
        $ans=$s[1];
    }elseif($s[0]<=12 && $s[0]>=6 ){
        $ans=$s[1]/2;
    }elseif($s[0]<=5 ){
        $ans = 0;
    }
    echo $ans;
?>

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

int main()
{

    string s, t;

    cin >> s >> t;

    int count = 0;

    for (int i = 0; i < s.length(); i++)
    {
        if (s[i] != t[i])
        {
            count++;
        }
    }

    cout << count;

    return 0;
}

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

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}

//INSERT ABOVE HERE
signed main(){
  Int n,m;
  cin>>n>>m;
  Int ans=0;
  auto check=
    [&](Int x){
      Int k=m/x;
      if(k>=n) chmax(ans,x);
    };
  for(Int x=1;x*x<=m;x++){
    if(m%x) continue;
    check(x);
    check(m/x);
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
vector<pair<int,int> >T;
vector<pair<int,pair<int,int> > >G[1<<17];
int N,Q;
int L[1<<17],R[1<<17];
int parent[20][1<<17];
int depth[1<<17];
void tourdfs(int u,int p,int d)
{
	parent[0][u]=p;
	depth[u]=d;
	L[u]=T.size();
	for(int i=0;i<G[u].size();i++)
	{
		int v=G[u][i].first;
		if(v==p)continue;
		T.push_back(G[u][i].second);
		tourdfs(v,u,d+1);
		T.push_back(make_pair(-G[u][i].second.first,G[u][i].second.second));
	}
	R[u]=T.size();
}
long cumsum[1<<20];
const int W=500;
int cnt[1000][1<<17];
long sum[1000][1<<17];
pair<int,long>get(int l,int r,int c)
{
	pair<int,long>ret=make_pair(0,0);
	while(l<T.size()&&l%W!=0&&l<r)
	{
		int nc=T[l].first,nd=T[l].second;
		if(nc>0&&nc==c)
		{
			ret.first++;
			ret.second+=nd;
		}
		else if(-nc==c)
		{
			ret.first--;
			ret.second-=nd;
		}
		l++;
	}
	while(l+W<=r&&l+W<=T.size())
	{
		int nc=cnt[l/W][c];
		long nd=sum[l/W][c];
		ret.first+=nc;
		ret.second+=nd;
		l+=W;
	}
	while(l<r)
	{
		int nc=T[l].first,nd=T[l].second;
		if(nc>0&&nc==c)
		{
			ret.first++;
			ret.second+=nd;
		}
		else if(-nc==c)
		{
			ret.first--;
			ret.second-=nd;
		}
		l++;
	}
	return ret;
}
long calc(int u,int v,int c,int y)
{
	bool flag=false;
	if(L[u]>R[v])
	{
		swap(u,v);
		flag=true;
	}
	long ret=cumsum[R[v]]-cumsum[L[u]];
	pair<int,long>p=get(L[u],R[v],c);
	ret-=p.second;
	ret+=p.first*y;
	return flag?-ret:ret;
}
int lca(int u,int v)
{
	if(depth[u]>depth[v])swap(u,v);
	for(int k=0;k<20;k++)
	{
		if(depth[v]-depth[u]>>k&1)v=parent[k][v];
	}
	if(u==v)return u;
	for(int k=19;k>=0;k--)
	{
		if(parent[k][u]!=parent[k][v])
		{
			u=parent[k][u];
			v=parent[k][v];
		}
	}
	return parent[0][u];
}
main()
{
	cin>>N>>Q;
	for(int i=1;i<N;i++)
	{
		int a,b,c,d;cin>>a>>b>>c>>d;
		a--,b--;
		G[a].push_back(make_pair(b,make_pair(c,d)));
		G[b].push_back(make_pair(a,make_pair(c,d)));
	}
	tourdfs(0,-1,0);
	for(int i=0;i<T.size();i++)
	{
		cumsum[i+1]=cumsum[i]+(T[i].first<0?-1:1)*T[i].second;
	}
	for(int k=1;k<20;k++)
	{
		for(int i=0;i<N;i++)
		{
			if(parent[k-1][i]>=0)parent[k][i]=parent[k-1][parent[k-1][i]];
			else parent[k][i]=-1;
		}
	}
	for(int i=0;i+W<=T.size();i+=W)
	{
		for(int j=0;j<W;j++)
		{
			int nc=T[i+j].first,nd=T[i+j].second;
			if(nc>0)
			{
				cnt[i/W][nc]++;
				sum[i/W][nc]+=nd;
			}
			else
			{
				cnt[i/W][-nc]--;
				sum[i/W][-nc]-=nd;
			}
		}
	}
	for(;Q--;)
	{
		int x,y,u,v;
		cin>>x>>y>>u>>v;
		u--,v--;
		int pa=lca(u,v);
		cout<<calc(pa,u,x,y)+calc(pa,v,x,y)<<endl;
	}
}


Measured memory_bytes: 643824
//b.c B-AtCoder Beginner Contest 111
#include<stdio.h>

int main(void){
    int n;
    scanf("%d",&n);

    if(100<=n && n<=111){
        printf("111\n");
    }else if(111<n && n<=222){
        printf("222\n");
    }else if(222<n && n<=333){
        printf("333\n");
    }else if(333<n && n<=444){
        printf("444\n");
    }else if(444<n && n<=555){
        printf("555\n");
    }else if(555<n && n<=666){
        printf("666\n");
    }else if(666<n && n<=777){
        printf("777\n");
    }else if(777<n && n<=888){
        printf("888\n");
    }else if(888<n && n<=999){
        printf("999\n");
    }
    return 0;
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
using namespace std;
const long double pi=3.141592653589793;
int main(){
  long double ans,dh,dm;
  int a,b,h,m;
  cin>>a>>b>>h>>m;
  dh=(h*60+m)*pi/360;
  dm=m*pi/30;
  ans=pow((pow(a,2)+pow(b,2)-2*a*b*cos(dm-dh)),0.5);
  cout<<fixed<<setprecision(12);
  cout<<ans<<endl;
}

Measured memory_bytes: 4020
// using A star algorithm
#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
using namespace std;
const int N = 9;
const int XY = 3;
const int LIMIT = 100;

struct state {
  vector<int> board;
  int g;
  state(vector<int> &board) {
    this->board = board;
    this->g = 0;
  }
};
struct compare_state {
  int h_func(state &s) {
    // using Manhattan distance
    int distance = 0;
    vector<int> solve(N,0);
    for(int i=0;i<N;i++) {
      solve[i] = i+1;
    }
    solve[N-1] = 0;
    vector<int> board = s.board;
    int solve_x,solve_y;
    int board_x,board_y;
    for(int i=0;i<N;i++) {
      for(int j=0;j<N;j++) {
        if(solve[i] == board[j]) {
          solve_x = i % XY; solve_y = i / XY;
          board_x = j % XY; board_y = j / XY;
          distance += abs(solve_x - board_x) + abs(solve_y - board_y);
          break;
        }
      }
    }
    return distance;
  }
  bool operator() (state &a,state &b) {
    return (a.g + h_func(a)) > (b.g + h_func(b));
  }
};
priority_queue<state,vector<state>,compare_state> que;
map<vector<int>,int> cost_table;

bool check(state &current,state &end) {
  for(int i=0;i<N;i++) {
    if(current.board[i] != end.board[i])
      return false;
  }
  return true;
}

bool is_infield(int x,int y) {
  return (x < XY && y < XY && x >= 0 && y >= 0);
}

int search(state &start,state &end) {
  // initialize process
  que.push(start);
  cost_table[start.board] = 0;
  while(!que.empty()) {
    state current = que.top(); que.pop();
    // approach goal
    if(check(current,end)) {
      return current.g;
    }
    // not find goal
    if(current.g > LIMIT) {
      break;
    }
    // find zero brocks
    int zero_pos;
    for(int i=0;i<N;i++)
      if(current.board[i] == 0)
        zero_pos = i;
    int x = zero_pos % XY;
    int y = zero_pos / XY;
    // swap zero brocks and find next state
    int dx[] = {0,-1,1,0};
    int dy[] = {-1,0,0,1};
    for(int d=0;d<4;d++) {
      if(!is_infield(x+dx[d],y+dy[d])) continue;
      vector<int> next_board = current.board;
      swap(next_board[x+y*XY],next_board[(x+dx[d])+(y+dy[d])*XY]);
      // make and update cost table
      if(!cost_table.count(next_board)) {
        cost_table[next_board] = current.g + 1;
        state next = *(new state(next_board));
        next.g = current.g + 1;
        que.push(next);
      }
      else {
        if((current.g+1) < cost_table[next_board]) {
          cost_table[next_board] = current.g + 1;
          state next = *(new state(next_board));
          next.g = current.g + 1;
          que.push(next);
        }
      }
    }
  }
  return -1;
}

int main() {
  vector<int> start_vec(N,-1);
  vector<int> end_vec(N,-1);
  for(int i=0;i<N;i++) {
    cin >> start_vec[i];
    end_vec[i] = i+1;
  }
  end_vec[N-1] = 0;

  state start = *(new state(start_vec));
  state end = *(new state(end_vec));

  cout << search(start,end) << endl;
}

Measured memory_bytes: 7796
#define _CRT_SECURE_NO_DEPRECATE
//#include <bits/stdc++.h>
#include <iostream>
#include <algorithm>
#include <numeric>
#include <vector>
#include <unordered_set>
#include <unordered_map>
using namespace std;
#define ll  long long int 
 
int main() {
	//freopen("test.txt", "r", stdin);
	int x,y,a,b,c; cin>>x>>y>>a>>b>>c;
	vector<ll> p,q,r;
	for(int i=0;i<a;i++) {int t; cin>>t; p.push_back(t);}
	for(int i=0;i<b;i++) {int t; cin>>t; q.push_back(t);}
	for(int i=0;i<c;i++) {int t; cin>>t; r.push_back(t);}
	sort(p.rbegin(),p.rend()); sort(q.rbegin(),q.rend());
	vector<ll> v(p.begin(),p.begin()+x);
	v.insert(v.end(),q.begin(),q.begin()+y);
	v.insert(v.end(),r.begin(),r.end());
	sort(v.rbegin(),v.rend());
	cout<<accumulate(v.begin(),v.begin()+x+y,(ll)0)<<endl;
}

Measured memory_bytes: 6324
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i=0; i < (int)(n); i++)
#define rep2(i, s, n) for (int i = (s); i < (int)(n); i++)
using ll = long long;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using P = pair<ll, ll>;

// chmin, chmax関数
template<typename T, typename U, typename Comp=less<>>
bool chmax(T& xmax, const U& x, Comp comp={}) {
    if(comp(xmax, x)) {
        xmax = x;
        return true;
    }
    return false;
}
template<typename T, typename U, typename Comp=less<>>
bool chmin(T& xmin, const U& x, Comp comp={}) {
    if(comp(x, xmin)) {
        xmin = x;
        return true;
    }
    return false;
}

// Yes-Noを出力する問題で楽をする
void Ans(bool f){
    if(f) cout << "Yes" << endl;
    else cout << "No" << endl;
}

//---------------------------

int main(){
    ll n;
    cin >> n;
    if(n%2) cout << 2*n << endl;
    else cout << n << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
int main(void)
{
	int n;
	int m[10];
	int l,s;
	int i;
	
	scanf("%d",&n);
	while(n!=0){
		l=0;
		for(i=0;i<9;i++){
			scanf("%d",&m[i]);
			l=l+m[i];
		}
		s=n-l;
		printf("%d\n",s);
		scanf("%d",&n);
	}
	return 0;
}

Measured memory_bytes: 1028
#include <bits/stdc++.h>
using namespace std;
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
#define mp(a, b) make_pair(a, b)
#define lowbit(x) ((x) & -(x))
typedef pair<int, int> pii;
typedef long long ll;
const ll mod = 1e9 + 7;
const int maxn = 500000 + 10;
typedef bitset<26> bit;
bit Tree[maxn << 2];
char s[maxn];
int n;
void pushup(bit & rt, const bit & l, const bit & r)
{
	rt = l | r;
}
void build(int rt, int l, int r)
{
	if(l == r)
	{
		Tree[rt][s[l] - 'a'] = 1;
		return;
	}
	int mid = l + r >> 1;
	build(ls, l, mid); build(rs, mid + 1, r);
	pushup(Tree[rt], Tree[ls], Tree[rs]);
}
void update(int rt, int l, int r, int pos, int x)
{
	if(l == r)
	{
		Tree[rt].reset();
		Tree[rt][x] = 1;
		return;
	}
	int mid = l + r >> 1;
	if(pos <= mid) update(ls, l, mid, pos, x);
	else update(rs, mid + 1, r, pos, x);
	pushup(Tree[rt], Tree[ls], Tree[rs]);
}	
bit query(int rt, int l, int r, int a, int b)
{
	if(a <= l && r <= b) return Tree[rt];
	int mid = l + r >> 1;
	bit retl, retr, ret;
	if(a <= mid) retl = query(ls, l, mid, a, b);
	if(b > mid) retr = query(rs, mid + 1, r, a, b);
	pushup(ret, retl, retr);
	return ret;
}
int main()
{
	scanf("%d", &n);
	scanf("%s", s + 1);
	build(1, 1, n);
	int q;
	scanf("%d", &q);
	while(q--)
	{
		int op;
		scanf("%d", &op);
		if(op == 1)
		{
			int pos;
			char c[10];
			scanf("%d%s", &pos, c);
			update(1, 1, n, pos, c[0] - 'a');
		}
		else
		{
			int l, r;
			scanf("%d%d", &l, &r);
			printf("%d\n", query(1, 1, n, l, r).count());
		}
	}
	return 0;
}

Measured memory_bytes: 10496
#include <stdio.h>
int main(void)
{
    int a[5], i, min=100, minidx, ans=0;
    for(i=0;i<5;i++){
        scanf("%d", &a[i]);
    }

    for(i=0;i<5;i++){
        if((a[i]%10)<min && (a[i]%10)!=0){
            min=a[i]%10;
            minidx=i;
        }
    }

    for(i=0;i<5;i++){
        if(i!=minidx){
            ans=ans+a[i];
            if(10-(a[i]%10)!=10) ans=ans+10-(a[i]%10);
        }
        else ans=ans+a[i];
    }

    printf("%d\n", ans);
    

    return 0;
}


Measured memory_bytes: 128
#include <bits/stdc++.h>
// #include <atcoder/all>
#define ll long long int
#define ld long double
#define yorn(f) cout<<((f)?"Yes":"No")<<endl;
#define YORN(f) cout<<((f)?"YES":"NO")<<endl;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define repi(i, n) for (ll i = 1; i < (ll)(n); i++)
#define all(x) (x).begin(), (x).end()
#define put(x) cout << x << endl;
#define println(x) cout << x << endl;
using namespace std;
// using namespace atcoder;
void Main()
{
    ll n;
    cin >> n;
    vector<ll> A(n);
    rep(i, n) cin >> A[i];

    ll sum = accumulate(all(A), 0LL);

    vector<ll> S(2 * n);
    S[0] = A[0];
    repi(i, S.size()) S[i] = S[i-1] + A[(i * 2) % n];

    rep(i, n) {
        int start = 0;
        if (i % 2 == 0) {
            start = i / 2;
        }
        else {
            start = (n + 1) / 2 + i / 2;
        }

        ll v = S[start + (n + 1) / 2 - 1] - (start - 1 >= 0 ? S[start - 1] : 0);
        ll M = 2 * v - sum;
        cout << M << (i == n - 1 ? "" : " ");
    }
    cout << endl;
}
signed main(){ Main();return 0;}

Measured memory_bytes: 5564
#include <iostream>
#include <vector>
using namespace std;
typedef vector<vector<int>> tree;
#define MAXN 100000

int main() {
  int n;
  cin >> n;
  int a, b[MAXN-1];
  tree t(MAXN);
  for (int i = 0; i < n-1; i++) {
    cin >> a >> b[i];
    t[--a].push_back(--b[i]);
  }
  int c[MAXN] = {};
  int mcolor = 1;
  vector<int> next = {0};
  while (!next.empty()) {
    int color = 1;
    int now = next[0];
    next.erase(next.begin());
    for (int node : t[now]) {
      if (color == c[now]) color++;
      c[node] = color;
      next.push_back(node);
      mcolor = max(mcolor, color);
      color++;
    }
  }

  cout << mcolor << endl;
  for (int i = 0; i < n-1; i++) {
    cout << c[b[i]] << endl;
  }
}

Measured memory_bytes: 5248
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define fio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define mod 1000000007
int main() {
	fio;
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	int a, b;
	cin >> a >> b;
	for (int i = 0; i <= a; i++) {
		if (2 * i + 4 * (a - i) == b) {
			cout << "Yes";
			return 0;
		}
	}
	cout << "No";
	return 0;
}

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

#define ll long long
#define ar array

int main() {

    ios::sync_with_stdio(false);
	
	int x;
	
	cin >> x;

	if(x == 7 || x == 5 || x == 3){
		cout << "YES" << endl;
	}else{
		cout << "NO" << endl;
	}

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
int W, N, x[50009], dp[50009];
bool solve(int m) {
	int pl = 0, pr = 0;
	dp[1] = dp[2] = 1;
	for (int j = 2; j <= N; j++) {
		while (x[j] - x[pl] > W - (j - pl - 1)) pl++;
		while (j != pr + 1 && x[j] - x[pr] >= W - (j - pr - 1) * m) pr++;
		dp[j + 1] = dp[j] + (dp[pr] > dp[pl] ? 1 : 0);
	}
	for (int j = 0; j <= N; j++) {
		if (dp[j] != dp[j + 1] && x[N] - x[j] + N - j - 1 <= W) return true;
	}
	return false;
}
int main() {
	while (scanf("%d %d", &W, &N), W) {
		for (int i = 0; i < N; i++) scanf("%d", &x[i + 1]), x[i + 1] += x[i];
		int l = 0, r = W + 1;
		while (r - l > 1) {
			int m = (l + r) >> 1;
			if (solve(m)) r = m;
			else l = m;
		}
		printf("%d\n", r);
	}
	return 0;
}


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

#define lli long long int
#define ld long double
#define DEFO(n) lli n = 0;
#define MAX_L lli max = 9000000000000000000;
#define MIN_L lli min = 9000000000000000000;
#define MAX_D ld max = 4500;
#define MIN_D ld min = -4500;
#define LLI(n) \
  lli n;       \
  cin >> n;
#define LD(n)  \
  ld n;        \
  cin > n;
#define LLIV(a, n)            \
  vector<lli> a(n);           \
  for (lli i = 0; i < n; i++) \
  {                           \
    cin >> a.at(i);           \
  };
#define LLIV2(a, b, n)            \
  vector<lli> a(n), b(n);           \
  for (lli i = 0; i < n; i++) \
  {                           \
    cin >> a.at(i) >> b.at(i);           \
  };
#define LDV(a, n)            \
  vector<ld> a(n);           \
  for (lli i = 0; i < n; i++) \
  {                           \
    cin >> a.at(i);           \
  };
#define STR(n) \
  string n;    \
  cin >> n;
#define SUM(n) accumulate(n.begin(), n.end(), 0);
#define SORT(n) sort(n.begin(), n.end());
#define REVE(n) reverse(n.begin(), n.end());
#define yes cout << "Yes" << endl; return 0;
#define no cout << "No" << endl; return 0;
#define C45(n) (n + 1) / 2
#define OUT(n) cout << n << endl;
#define SRC(n, c)                    \
  for (lli i = 0; i < s.size(); i++) \
  {                                  \
    if (s.at(i) == c)                \
    {                                \
      n++;                           \
    }                                \
  };
//こぴー
/*#define ZISYO(s, S)                  \
  for (lli i = 0; i < s.size(); i++) \
  {                                  \
    S.at(i) = s.at(i);               \
  }                                  \
  Sort(S) Reve(S) for (lli i = 0; i < s.size(); i++) { s.at(i) = S.at(i); };
*/

//素数
bool IsPrime(lli num)
{
  if (num < 2)
    return false;
  else if (num == 2)
    return true;
  else if (num % 2 == 0)
    return false;
  long double sqrtNum = sqrt(num);
  for (lli i = 3; i <= sqrtNum; i += 2)
  {
    if (num % i == 0)
      return false;
  }
  return true;
}
//各桁の和
lli KSum(lli n)
{
  lli sum = 0;
  if (n < 0)
    return 0;
  while (n > 0)
  {
    sum += n % 10;
    n /= 10;
  }
  return sum;
}

//数値反転
bool KReve(lli n)
{
  int reverse = 0;
  int remaind;
  int tmp = n;
  while (tmp != 0)
  {
    remaind = tmp % 10;
    reverse = reverse * 10 + remaind;
    tmp /= 10;
  }
  if (reverse == n) 
    return true;
  else
    return false;
}

int main(void)
{
  ios::sync_with_stdio(false);
  LLI(N) MAX_L
  for(lli i = 1;i < N;i++) {
    lli sum;
    sum = KSum(i) + KSum(N - i);
    if(sum < max) {
      max = sum;
    }
  }
  OUT(max)
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define sqr(x) ((x)*(x))
#define mp make_pair
#define uint unsigned
#define PI pair<int,int>
inline char gc(){
    static char buf[100000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
#define gc getchar
inline int read(){
	int x = 0; char ch = gc(); bool positive = 1;
	for (; !isdigit(ch); ch = gc())	if (ch == '-')	positive = 0;
	for (; isdigit(ch); ch = gc())	x = x * 10 + ch - '0';
	return positive ? x : -x;
}
inline void write(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
    if(a>=10)write(a/10);
    putchar('0'+a%10);
}
inline void writeln(int a){
    if(a<0){
    	a=-a; putchar('-');
	}
	write(a); puts("");
}
inline int rnd(int x){
	return rand()%x;
}
inline ull rnd(){
	return ((ull)rand()<<30^rand())<<4|rand()%4;
}
const int M=19,N=200005,inf=1e9+3e5;
int n,v,gao,f[1<<M],g[1<<M],x[N],lst[M][N],nxt[M][N],tong[N];
int main(){
	n=read(); v=read(); x[0]=-inf; x[n+1]=inf;
	for(int i=1;i<=n;i++)x[i]=read();
	for(int i=0;;i++){
		int dali=v>>i; gao=i; nxt[i][n+1]=n; lst[i][0]=1;
		for(int j=1;j<=n;j++)if(x[j]-x[j-1]<=dali)lst[i][j]=lst[i][j-1]; else lst[i][j]=j;
		for(int j=n;j;j--)if(x[j+1]-x[j]<=dali)nxt[i][j]=nxt[i][j+1]; else nxt[i][j]=j;
		if((v>>i)==0)break;
	}
	f[0]=0; g[0]=n+1; 
	for(int i=1;i<(1<<gao);i++){
		f[i]=0; g[i]=n+1;
		for(int j=0;j<gao;j++)if(i>>j&1)f[i]=max(f[i],nxt[j+1][f[i^(1<<j)]+1]);
		for(int j=0;j<gao;j++)if(i>>j&1)g[i]=min(g[i],lst[j+1][g[i^(1<<j)]-1]);
	}
	for(int i=0;i<=n+1;i++)tong[i]=-1;
	for(int i=0;i<(1<<gao);i++){
		int l=f[i],r=g[((1<<gao)-1)^i];
		tong[r]=max(tong[r],l);
	}
	for(int i=1;i<=n;i++)tong[i]=max(tong[i],tong[i-1]);
	for(int i=1;i<=n;i++){
		int l=lst[0][i],r=nxt[0][i];
		puts(tong[r+1]>=l-1?"Possible":"Impossible");
	}
}

Measured memory_bytes: 37248
using System;
using System.Collections.Generic;

class Program
{
    #region library
    static int n = 0;
    static int r = 0;
    static int c = 0;
    static int x = 0;
    static int y = 0;
    static string s = "";
    static string[] ss;
    static long sum = 0;
    static long cnt = 0;
    static long max = -1;
    static long min = 2147483647;
    static bool flg = false;
    static bool flg2 = false;
    static string alpha = "abcdefghijklmnopqrstuvwxyz";
    static int[] arr;
    static char[,] map;
    static int[,] imap;
    static string rl()
    {
        return Console.ReadLine();
    }
    static string[] rls()
    {
        return Console.ReadLine().Split();
    }
    static void wl(object obj = null)
    {
        Console.WriteLine(obj);
    }
    static void w(object obj)
    {
        Console.Write(obj);
    }
    static int Int(string s)
    {
        return int.Parse(s);
    }
    static void yes()
    {
        wl("YES");
    }
    static void no()
    {
        wl("NO");
    }
    static void Sum()
    {
        wl(sum);
    }
    static void Cnt()
    {
        wl(cnt);
    }
    static void setarray(int num = -1)
    {
        if (n == 0)
        {
            n = Int(rl());
        }
        arr = new int[n];
        if (num == -1) ss = rls();
        for (int i = 0; i < n; i++)
        {
            if (num == -1)
                arr[i] = Int(ss[i]);
            else
                arr[i] = num;
        }
    }
    static void setmap(char def = '@')
    {
        if (r == 0 && c == 0)
        {
            ss = rls();
            r = Int(ss[0]);
            c = Int(ss[1]);
        }
        map = new char[r, c];
        for (int i = 0; i < r; i++)
        {
            if (def == '@') s = rl();
            for (int j = 0; j < c; j++)
            {
                map[i, j] = (def == '@') ? s[j] : def;
            }
        }
    }
    static void setimap(int def = -1)
    {
        if (r == 0 && c == 0)
        {
            ss = rls();
            r = Int(ss[0]);
            c = Int(ss[1]);
        }
        imap = new int[r, c];
        for (int i = 0; i < r; i++)
        {
            if (def == -1) s = rl();
            for (int j = 0; j < c; j++)
            {
                imap[i, j] = (def == -1) ? Int(s[j].ToString()) : def;
            }
        }
    }
    #endregion

    static void Main(string[] args)
    {
        ss = rls();
        int a = Int(ss[0]);
        int b = Int(ss[1]);

        for (int i = 1; i <= 999; i++)
        {
            sum += i;
            if(i == b - a)
            {
                wl(sum - b);
            }

        }
    }
}



Measured memory_bytes: 13140
#include <bits/stdc++.h>
using namespace std;
#define modulo 1000000007
#define mod(mod_x) ((((long long)mod_x+modulo))%modulo)
#define Inf 1000000000
#define rep(i,n) for(int i=0;i<n;i++)

int main(){
	int n , h ;	
	cin >> h >> n ;	
	vector<int> dp(h+1,1e9) , a(n) , b(n) ;
	rep(i,n) cin >> a[i] >> b[i] ;
	dp[0] = 0 ; 
	rep(i,n)rep(j,h+1)dp[min(j+a[i],h)]=min(dp[min(j+a[i],h)],dp[j]+b[i]);
	cout <<dp[h] << endl;
}


Measured memory_bytes: 256
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<vector>
using namespace std;
#define N 800002
typedef long long ll;
const int p=1e9+9;
int n,d,x;
double ans,st,ed,c;
int main()
{
	scanf("%d%d%d",&n,&d,&x);
	st=d;ed=st+1.0*(2*n-1)*x;c=x;
	for(int i=2*n;i;i-=2)
	{
		ans+=(st+ed)/2.0;
		st+=(2.0*st+5.0*x)/(1.0*i);
		ed+=(2.0*ed-5.0*x)/(1.0*i);
		if(i>2)c=(ed-st)/(1.0*(i-3));
	}
	printf("%.10lf\n",ans);
}


Measured memory_bytes: 256