akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
void updateCostP(int n, int *cost, int *tgts, int *exist, int tgt_len){
    int i;
    for(i=0;i<tgt_len;i++){
        if((tgts[i]>n)&&(cost[tgts[i]-1]>cost[tgts[i]]+exist[tgts[i]])){
            tgts[tgt_len]=tgts[i]-1;
            cost[tgts[i]-1]=cost[tgts[i]]+exist[tgts[i]];
            tgt_len++;
        }
        if((tgts[i]<n*n-n)&&(cost[tgts[i]+1]>cost[tgts[i]]+exist[tgts[i]])){
            tgts[tgt_len]=tgts[i]+1;
            cost[tgts[i]+1]=cost[tgts[i]]+exist[tgts[i]];
            tgt_len++;
        }
        if((tgts[i]>n)&&(cost[tgts[i]-n]>cost[tgts[i]]+exist[tgts[i]])){
            tgts[tgt_len]=tgts[i]-n;
            cost[tgts[i]-n]=cost[tgts[i]]+exist[tgts[i]];
            tgt_len++;
        }
        if((tgts[i]<n*n-n)&&(cost[tgts[i]+n]>cost[tgts[i]]+exist[tgts[i]])){
            tgts[tgt_len]=tgts[i]+n;
            cost[tgts[i]+n]=cost[tgts[i]]+exist[tgts[i]];
            tgt_len++;
        }

    }
}
int main(){
    int n;
    cin >> n;
    int cost[n*n],  tgts[n*n], exists[n*n];
    int i,j,k;
    int costzero_len=0,costzero_ofs=0,tgts_len=0;
    int p;

    for(i=0;i<n*n;i++){
        cost[i]=n*n;
        exists[i]=1;
    }
    for(i=0;i<n;i++){
        //上下
        tgts[tgts_len]=i;
        tgts[tgts_len+1]=n*n-n+i;
        cost[i]=0;
        cost[n*n-n+i]=0;
        tgts_len+=2;
    }
    for(i=2;i<n-1;i++){
        //左右
        tgts[tgts_len]=i*n-1;
        tgts[tgts_len+1]=i*n;
        cost[i*n-1]=0;
        cost[i*n]=0;
        tgts_len+=2;
    }
    tgts[tgts_len]=n;
    tgts[tgts_len+1]=n*n-n-1;
    cost[n]=0;
    cost[n*n-n-1]=0;
    tgts_len+=2;

    
    //updateCost(n,cost,costzero,tgts,exists,costzero_len,costzero_ofs);
    updateCostP(n, cost, tgts, exists, tgts_len);
    long ans = 0;
    for(i=0;i<n*n;i++){
        cin >> p;
        p-=1;
        tgts[0]=p;
        tgts_len=1;
        if(cost[p]==0){
            if((p>n)&&(cost[p-1]>0)){
                cost[p-1]=0;
                //costzero[costzero_len]=p-1;
                //costzero_len++;
                tgts[tgts_len]=p-1;
                tgts_len++;
            }
            if((p<n*n-n)&&(cost[p+1]>0)){
                cost[p+1]=0;
                //costzero[costzero_len]=p+1;
                //costzero_len++;
                tgts[tgts_len]=p+1;
                tgts_len++;
            }
            if((p>n)&&(cost[p-n]>0)){
                cost[p-n]=0;
                //costzero[costzero_len]=p-n;
                //costzero_len++;
                tgts[tgts_len]=p-n;
                tgts_len++;
            }
            if((p<n*n-n)&&(cost[p+n]>0)){
                cost[p+n]=0;
                //costzero[costzero_len]=p+n;
                //costzero_len++;
                tgts[tgts_len]=p+n;
                tgts_len++;
            }
        }else{
            //updateCost(n,cost,costzero,tgts,exists,costzero_len,costzero_ofs);
            ans+=cost[p];
        }
        exists[p]=0;
        updateCostP(n, cost, tgts, exists, tgts_len);
    }
    if(n<=2){
        cout << 0 << endl;
    }else{
        cout << ans << endl;
    }
    return 0;
}

Measured memory_bytes: 6536
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <climits>
using namespace std;
#define MOD int(1e9 + 7)
#define INF (long long)(1e18)

int main()
{
    cout.precision(18);

    long long N;
    vector<long long> A;

    cin >> N;
    for (long long i = 0; i < N; i++)
    {
        long long t;
        cin >> t;
        A.push_back(t);
    }

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

    long long c = 0;
    for (long long i = 0; i < N; i++)
    {
        for (long long j = i + 1; j < N; j++)
        {
            long long k = lower_bound(A.begin(), A.end(), A[i] + A[j]) - A.begin();
            c += k - j - 1;
        }
    }

    cout << c << endl;
}

Measured memory_bytes: 256
//#include <bits/stdc++.h>
//#include <stdio.h>
#include<iostream>
#include<cstdio>
#include<bitset>
#include<algorithm>
#include<vector>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<string.h>
#include<cmath>
#include<utility>
#include<functional>
#include<map>
#include<set>
#include<cctype>
#include<fstream>


#define FOR(i, a, b) for( int i=(a);i<=(b);i++)
#define RFOR(i, a, b) for( int i=(a);i>=(b);i--)
#define LFOR(i, a, b) for( long long int i=(a);i<=(b);i++)
#define LRFOR(i, a, b) for(long long int i=(a);i>=(b);i--)
#define MOD 1000000007
#define INF 1000000000 //2000000000
#define LLINF 1000000000000000000 //9000000000000000000
#define PI 3.14159265358979
#define MAXI 7500000

using namespace std;
typedef long long int ll;
typedef pair< long long int, long long  int> P;

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


int main(void) {
	int n;
	double a;
	double t;
	double h[1001] = {};
	double mini = INF;
	int pos;

	cin >> n >> t >> a;
	FOR(i, 1, n) {
		cin >> h[i];
	}

	FOR(i, 1, n) {
		if (mini > fabs((t - h[i] * 0.006) - a)) {
			mini = fabs((t - h[i] * 0.006) - a);
			pos = i;
		}
	}

	cout << pos << endl;


	return 0;
}

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

public class Main {

    private final static int MOD = (int)1e9 + 7;

    public Main(FastScanner in, PrintWriter out) {
        int N = in.nextInt();
        int[] A = new int[N];
        int[] cnt = new int[N + 1];
        for (int i = 0; i < N; i++) {
            int a = in.nextInt();
            A[i] = a;
            cnt[a]++;
        }
        long total = 0;
        for (int x : cnt) {
            total += 1L * x * (x - 1) / 2;
        }
        for(int k = 0; k < N; k++) {
            int x = cnt[A[k]];
            long res = total - x + 1; 
            out.println(res);
        }
        out.flush();
    }

    private int gcd(int a, int b) {
        while (true) {
            if (b == 0) return a;
            int tmp = a;
            a = b;
            b = tmp % b;
        }
    }

    private long powm(long x, long p) {
        long res = 1;
        while (p > 0) {
            if (p % 2 == 1)
                res = res * x % MOD;
            x = x * x % MOD;
            p /= 2;
        }
        return res;
    }


    public static void main(String[] args) {
        PrintWriter out = new PrintWriter(System.out);
        // Scanner in = new Scanner(
                // new BufferedReader(new InputStreamReader(System.in)));
        FastScanner in = new FastScanner(System.in);

        Main sol = new Main(in, out);

        out.close();
    }
}


class FastScanner{
    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;

    public FastScanner(InputStream stream)
    {
        this.stream = stream;
    }

    int read()
    {
        if (numChars == -1)
            throw new InputMismatchException();
        if (curChar >= numChars){
            curChar = 0;
            try{
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0)
                return -1;
        }
        return buf[curChar++];
    }

    boolean isSpaceChar(int c)
    {
        return c==' '||c=='\n'||c=='\r'||c=='\t'||c==-1;
    }

    boolean isEndline(int c)
    {
        return c=='\n'||c=='\r'||c==-1;
    }

    int nextInt()
    {
        return Integer.parseInt(next());
    }

    long nextLong()
    {
        return Long.parseLong(next());
    }

    double nextDouble()
    {
        return Double.parseDouble(next());
    }

    String next(){
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isSpaceChar(c));
        return res.toString();
    }

    String nextLine(){
        int c = read();
        while (isEndline(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do{
            res.appendCodePoint(c);
            c = read();
        }while(!isEndline(c));
        return res.toString();
    }
}


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

const int RLEN=1<<18|1;
inline char nc() {
	static char ibuf[RLEN],*ib,*ob;
	(ib==ob) && (ob=(ib=ibuf)+fread(ibuf,1,RLEN,stdin));
	return (ib==ob) ? -1 : *ib++;
}
inline int rd() {
	char ch=nc(); int i=0,f=1;
	while(!isdigit(ch)) {if(ch=='-')f=-1; ch=nc();}
	while(isdigit(ch)) {i=(i<<1)+(i<<3)+ch-'0'; ch=nc();}
	return i*f;
}

const int N=1e5+50, L=20;
int n,ans,f[N];
vector <int> edge[N]; 
inline void dfs(int x,int fa) {
	int sta=0,lim=0; 
	int *cnt=new int[L];
	for(int i=0;i<L;i++) cnt[i]=0;
	for(int e=edge[x].size()-1;~e;e--) {
		int v=edge[x][e]; if(v==fa) continue;
		dfs(v,x); sta|=f[v];
		for(int j=0;j<L;++j) if(f[v]&(1<<j)) if((++cnt[j])>=2) lim=max(lim,j+1); 
	}
	if(edge[x].size()+(x==1)==1) f[x]=1; //leaf
	else if(edge[x].size()+(x==1)==2) {
		int j;
		for(j=0;j<L;++j) if(!(sta&(1<<j))) break;
		f[x]=sta|(1<<j); ans=max(ans,j);
		for(--j;~j;--j) if(f[x]&(1<<j)) f[x]^=(1<<j);
	} else {
		int j;
		for(j=lim;j<L;++j) if(!(sta&(1<<j))) break;
		f[x]=sta|(1<<j); ans=max(ans,j);
		for(--j;~j;--j) if(f[x]&(1<<j)) f[x]^=(1<<j);
	}
	delete cnt;
}
int main() {
	n=rd();
	for(int i=1;i<n;i++) {
		int x=rd(), y=rd();
		edge[x].push_back(y);
		edge[y].push_back(x);
	} cout<<(dfs(1,0),ans)<<'\n';
	
}

Measured memory_bytes: 17792
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include<queue>
#include<cmath>
#include<map>
#include<set>
using namespace std;
const int INF = 1 << 29;
const double EPS = 1e-9;

typedef long long ll;

#define SORT(c) sort((c).begin(),(c).end())
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
int A,B;
int N;

int main(int argc, char * argv[])
{
    ios::sync_with_stdio(false);
	cin >> N;
	cout << (N+1)*N/2 << endl;
	

    return 0;
}



Measured memory_bytes: 256
<?php
$s = $a[0] = range(1, 9);
$keta = 0;
fscanf(STDIN, "%d", $N);
while(count($s) < $N) {
    foreach ($a[$keta] as $v) {
        $l = $v % 10;
        if ($l !== 0) {
            $a[$keta + 1][] = $v * 10 + $l - 1;
        }
        $a[$keta + 1][] = $v * 10 + $l;
        if ($l !== 9) {
            $a[$keta + 1][] = $v * 10 + $l + 1;
        }
    }
    $s = array_merge($s, $a[$keta + 1]);
    $keta++;
}
printf("%d", $s[$N - 1]);

Measured memory_bytes: 27120
#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#define rep(i, n) for(i = 0; i < (n); i++)
#define chmax(x, y) x = max(x, y)
#define chmin(x, y) x = min(x, y)
#define MOD 1000000007
#define PI 3.14159265358979323846
#define INF 1 << 30

using namespace std;
typedef long long ll;
typedef pair<int, int> pp;

int main(void) {
	int num, i, ok = false;
	int k, a, b;
	cin >> k >> a >> b;
	for (; a <= b; a++) {
		if (a % k == 0) {
			ok = true;
			break;
		}
	}
	if (ok)
		printf("OK\n");
	else
		printf("NG\n");
	return 0;
}

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

int main() {
    int64_t N,A,B,C,D,E;
    cin >> N >> A >> B >> C >> D >> E;
    
    int64_t F = min(A,min(B,min(C,min(D,E))));
    
    if ( N % F == 0 ){
        cout << N / F + 4 << endl;
    } else {
        cout << N / F + 5 << endl;
    }
    return 0;
}


Measured memory_bytes: 3644
//author: chinmay0402
//One day your whole life will flash before your eyes, make sure you make it worth watching
#include<bits/stdc++.h>
using namespace std;

//policy based data structures
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define ll long long int
#define lld long double
#define fl float
#define vs vector<string>
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pair<ll,ll>>
#define fst first
#define scd second
#define sll set<ll>
#define mll map<ll,ll>
#define flash ios_base::sync_with_base(false);cin.tie(NULL);
#define INF (ll)10000000000000000
#define MOD (ll)1000000007
#define pb push_back
#define mll map<ll,ll>
#define test ll t;cin>>t;while(t--)
#define sortv(v) sort(v.begin(),v.end())
#define max3(a,b,c) max(a,max(b,c))

#define forn(i,n) for(ll i=0;i<n;i++)
#define for1(i,n) for(ll i=1;i<=n;i++)
#define fornr(i,n) for(ll i=n-1;i>=0;i--)
#define forab(i,a,b,c) for(ll i=a;i<=b;i+=c)

template<typename T>
void read(T &x){
 cin>>x;
}
template<typename T,typename T1>
void read(T &x, T1 &y){
 cin>>x>>y;
}
template<typename T,typename T1, typename T2>
void read(T &x, T1 &y, T2 &z){
 cin>>x>>y>>z;
}
template<typename T,typename T1, typename T2, typename T3>
void read(T &x, T1 &y, T2 &z , T3 &a){
 cin>>x>>y>>z>>a;
}
template<typename T>
void reada(T oneD,ll n){
 for(ll i=0;i<n;i++)
  cin>>oneD[i];
}
template <typename T>
void readv(vector< T > &oneD,ll n){
 forn(i,n){
  ll x;
  read(x);
  oneD.push_back(x);
 }
}
ll gcd(ll a, ll b){
 if(a==0)
  return b;
 else
  return gcd(b%a,a);
}

ll gcdExt(ll a,ll b, ll &x, ll &y){
 if(a==0){
  x=0;
  y=1;
  return b;
 }
 ll x1,y1;
 ll gcd=gcdExt(b%a,a,x1,y1);
 x=y1-(b/a)*x1;
 y=x1;
 return gcd;
}

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

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

vector<bool>sieve(1000000,true);
void Sieve(){
 sieve[0]=false;
 sieve[1]=false;
 for(ll i=2;i*i<=1000000;i++){
  if(sieve[i]==true){
   for(ll j=i*i;j<1000000;j+=i)
    sieve[j]=false;
  }
 }
}

vll sieve_spf(1000001);
void Sieve_spf(){
 ll n=1000001;
 
 forn(i,n)
  sieve[i]=i;
 
 sieve[0]=-1;
 sieve[1]=-1;
 
 forab(i,2,n,2)
  sieve[i]=2;
 
 forab(i,3,n,2)
  if(sieve[i]==i)
   forab(j,i*i,n,i)
    if(sieve[j]==j)
     sieve[j]=i;
}


int main(){
 ll r;
 read(r);
 lld cir=2.0*(3.14)*(lld)r;
 cout<<cir;
 return 0;
}

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

int main()
{
  for (int i = 1; i <= 9; ++i)
  {
    for (int j = 1; j <= 9; ++j)
    {
      printf("%dx%d=%d\n", i, j, i*j);
    }
  }
  return 0;
}

Measured memory_bytes: 1088
#pragma GCC optimize("2,Ofast,inline")
#include <bits/stdc++.h>
#define LL long long
#define P pair<int, int>
const LL N = 6e4 + 10;
const LL inf = 0x3f3f3f3f;
const LL mod = 998244353;
using namespace std;
template <typename tp>
inline void read(tp &x)
{
    x = 0; char c = getchar(); bool f = 0;
    for (; c < '0' || c > '9'; f |= (c == '-'), c = getchar()) ;
    for (; c >= '0' && c <= '9'; x = (x << 3) + (x << 1) + c - '0', c = getchar()) ;
    if (f) x = -x;
}
LL n,cost[510][510];
LL along[510][510],sum_along[510][510];
LL inverse[510][510],sum_inverse[510][510];
LL dp[510][510];
signed main()
{
    read(n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(i==j) continue;
            read(cost[i][j]);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            sum_along[j][i]=sum_along[j-1][i]+cost[j][i];
    for(int i=1;i<=n;i++)
        for(int j=i+1;j<=n+1;j++)
            along[i][j]=along[i][j-1]+sum_along[j-1][j]-sum_along[i-1][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<i;j++)
            sum_inverse[j][i]=sum_inverse[j-1][i]+cost[i][j];
    for(int i=1;i<=n+1;i++)
        for(int j=n+1;j>i;j--)
            inverse[i][j]=inverse[i][j+1]+sum_inverse[i][j];
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=0;i<=n;i++)
        for(int j=i;j<=n;j++)
            if(dp[i][j]<1e18)
                for(int k=j+1;k<=n+1;k++)
                    dp[j][k]=min(dp[j][k],dp[i][j]+along[j+1][k]+inverse[j][k+1]-inverse[i][k+1]);
    LL ans=1e18;
    for(int i=0;i<=n;i++)
        ans=min(ans,dp[i][n+1]);
    printf("%lld\n",ans);
    return 0;
}


Measured memory_bytes: 12416
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
//#define ll long long
//#define int  unsigned long long
#define pb push_back
#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
const int N = 300000;
int mod = 1e9 + 7;
int x[N], y[N], a[N], b[N];
map < pair < int, int >, int > m;
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a + 1, a + n + 1);
    if (a[1] >= 0){
        int res = 0;
        for (int i = 2; i <= n; i++) res += a[i];
        res -= a[1];
        int s = a[1];
        int r = 2;
        cout << res << endl;
        for (int i = 2; i < n; i++){
            cout << s << " " << a[i] << endl;
            s -= a[i];
        }
        cout << a[n] << " " << s;
        return 0;
    }
    if (a[n] < 0){
        int res = a[n];
        for (int i = 1; i < n; i++){
            res -= a[i];
        }
        cout << res << endl;
        int s = a[n];
        for (int i = 1; i < n; i++){
            cout << s << " " << a[i] << endl;
            s -= a[i];
        }
        return 0;
    }
    int res = 0;
    for (int i = 1; i <= n; i++) res += abs(a[i]);
    int s = a[1];
    int r = 2;
    cout << res << endl;
    for (int i = 2; i < n; i++){
        if (a[i] < 0) continue;
        cout << s << " " << a[i] << endl;
        s -= a[i];
    }
    cout << a[n] << " " << s << endl;
    s = a[n] - s;
    for (int i = 2; i < n; i++){
        if (a[i] < 0){
            cout << s << " " << a[i] << endl;
            s -= a[i];
        }
    }
}


Measured memory_bytes: 3968
from operator import itemgetter
N, M, *pS = open(0).read().split()
p = pS[::2]
S = pS[1::2]
lst = []
for pi, Si in zip(p, S):
    lst.append((pi, Si))
lst.sort(key=itemgetter(0))
AC = [0] * int(N)
WA = [0] * int(N)
acpre = ""
pre = ""
cnt = 0
for li in lst:
    if li[0] == acpre:
        continue
    if li[0] != pre:
        cnt = 0
    if li[1] == "AC":
        AC[int(li[0]) - 1] += 1
        WA[int(li[0]) - 1] += cnt
        cnt = 0
        acpre = li[0]
    else:
        cnt += 1
    pre = li[0]
print(sum(AC), sum(WA))


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

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
        #define eprintf(...) 42
#endif

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define repi(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define all(x) (x).begin(),(x).end()
#define foreach(u,v) for(auto (u) : (v))
#define pb push_back
#define mp make_pair
#define mt make_tuple

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

const int inf = 1e9;
const ll linf = 1LL<<60;
const ll mod = 1e9 + 7;
const double eps = 1e-9;

/*
*/

int main()
{
  int n, m, s, t;
  cin >> n >> m >> s >> t;
  s--; t--;

  vector<pii> gy[n], gs[n];
  rep(i, m){
    int u, v, a, b;
    cin >> u >> v >> a >> b;
    u--; v--;
    gy[u].pb(mp(v, a));
    gy[v].pb(mp(u, a));
    gs[u].pb(mp(v, b));
    gs[v].pb(mp(u, b));
  }

  priority_queue<pll, vector<pll>, greater<pll>> que;
  ll dy[n], ds[n];
  fill(dy, dy+n, linf);
  fill(ds, ds+n, linf);

  que.push(mp(0, s));
  dy[s] = 0;
  while(!que.empty()){
    pll p = que.top();
    que.pop();
    int v = p.second;

    if(p.first < dy[v]) continue;
    for(auto u : gy[v]){
      if(dy[u.first] > dy[v] + u.second){
        dy[u.first] = dy[v] + u.second;
        que.push(mp(dy[u.first], u.first));
      }
    }
  }

  que.push(mp(0, t));
  ds[t] = 0;
  while(!que.empty()){
    pll p = que.top();
    que.pop();
    int v = p.second;

    if(p.first < ds[v]) continue;
    for(auto u : gs[v]){
      if(ds[u.first] > ds[v] + u.second){
        ds[u.first] = ds[v] + u.second;
        que.push(mp(ds[u.first], u.first));
      }
    }
  }

  vl ans(n);
  ans[n-1] = dy[n-1]+ds[n-1];
  for(int i = n-2; i >= 0; i--){
    ans[i] = min(ans[i+1], dy[i]+ds[i]);
  }

  rep(i, n){
    cout << (ll)1e15 - ans[i] << endl;
  }

  return 0;
}


Measured memory_bytes: 16756
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rrep(i, n) for(int i = n-1; i >= 0; i--)
#define  all(x) (x).begin(),(x).end()     // 昇順ソート
#define  rall(v) (v).rbegin(), (v).rend() // 降順ソート
#define  FastIO ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
typedef long long ll;
using P = pair<int,int>;
using VI = vector<int>;
using VVI = vector<vector<int>>;
using VL = vector<ll>;
using VVL = vector<vector<ll>>;
using VP = vector<P>;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return true; } return false; }

const int MAX = 55555;

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

    VI d(MAX + 1);
    for(int i = 1; i <= MAX; i++){
        for(int j = i; j <= MAX; j += i){
            d[j]++;
        }
    }
    

    int cnt = 0, i = 3;
    VI ans;
    while(cnt < n){
        if(d[i] == 2 && i % 5 == 3){
            ans.push_back(i);
            cnt++;
        }
        i++;
    }

    rep(i,n) printf("%d%c", ans[i], i == n-1? '\n' : ' ');
    return 0;
}


Measured memory_bytes: 3684
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <fstream>
#include <complex>
#include <stack>
#include <queue>

using namespace std;
typedef long long LL;
typedef pair<int, int> P;
static const double EPS = 1e-5;

#define FOR(i,k,n) for (int i=(k); i<(int)(n); ++i)
#define REP(i,n) FOR(i,0,n)

int main(void){
  int m,n;
  while(cin>>m){
    if(m==0) break;
    vector<P> seiza;
    set<P> star;
    int x,y;
    REP(i,m){
      cin>>x>>y;
      seiza.push_back(P(x,y));
    }
    cin>>n;
    REP(i,n){
      cin>>x>>y;
      star.insert(P(x,y));
    }
    set<P>::iterator it;
    P fstar = (*seiza.begin());
    for(it = star.begin(); it!=star.end(); it++){
      P target = (*it);
      int dx,dy;
      dx = target.first - fstar.first;
      dy = target.second - fstar.second;
      bool flag = true;
      for(int i=0; i<seiza.size(); i++){
        P tmp = P(seiza[i].first+dx, seiza[i].second+dy);
        if(star.find(tmp)==star.end()){
          flag = false;
          break;
        }
      }
      if(flag){
        printf("%d %d\n",dx,dy);
        break;
      }
    }
  }
  return 0;
}

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

using namespace std;

int main(int argc, const char *argv[])
{
  string s;
  cin >> s;

  if (s[2] == s[3] && s[4] == s[5]) {
    cout << "Yes\n";
  } else {
    cout << "No\n";
  }
  
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
typedef long long ll;
typedef pair<int,int> P;
const int INF = 2e9;
//bit全探索+greedy
int main(){
    int D,G;cin >> D >> G;
    vector<P> pro(D);
    rep(i,D){
        int p,c;cin >> p >> c;
        pro[i] = make_pair(p,c);
    }
    int ans = INF;
    rep(i,1<<D){
        int res = 0;
        int sum = 0;
        rep(j,D){
            if(i&(1<<j)){
                sum += pro[j].first*100*(j+1)+pro[j].second;
                res += pro[j].first;
            }
        }
        if(sum>=G)ans = min(ans,res);
        else{
            for(int j = D-1; j >= 0; j--){
                if(i&(1<<j))continue;
                for(int k = 0; k< pro[j].first; k++){
                    if(sum>=G)break;
                    sum += 100*(j+1);
                    res++;
                }
            }
            ans = min(ans,res);
        }
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
int main(void){
    int H,W,i,j;
   
    while(1){
        scanf("%d %d",&H,&W);
        if(H==0&&W==0) break;
        
        for(i=1;i<=H;i++){
            for(j=1;j<=W;j++){
                if((i+j)%2){
                    putchar('.');
                }else{
                    putchar('#');
                }
            }
            putchar('\n');
            
        }
        putchar('\n');
    }
    
    return 0;
    
}



Measured memory_bytes: 2120
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll MOD = 1'000'000'007;
const ld PI = acos(-1);  
const ld EPS = 0.0000000001;
const ll LINF = 1001002003004005006ll;
const int INF = 1001001001;
#define rep(i, n) for(ll i=0; i<(ll)(n); i++)
#define repd(i, n) for(ll i=n-1; 0<=i; i--)
#define FOR(i, a, b) for(ll i=a; i<(ll)(b); i++)
#define FORD(i, a, b) for(ll i=a-1; (ll)(b)<=i; i--)
#define ALL(x) x.begin(), x.end()
#define rALL(x) x.rbegin(), x.rend()
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};

vector<vector<char>> g;
int main(){
    ll h, w;    cin >> h >> w;
    ll res=LINF;
    for(ll i=1; 2*i<=w; i++){
        set<ll> st, mp;
        st.insert(i*h); mp.insert(i*h);
        mp.insert(((w-i)/2+(w-i)%2)*h);
        mp.insert((w-i)/2*h);
        st.insert((w-i)*(h/2));
        st.insert((w-i)*(h/2+h%2));
        res = min(*st.rbegin()-*st.begin(), min(*mp.rbegin()-*mp.begin(),res));
    }
    for(ll i=1; 2*i<=h; i++){
        set<ll> st, mp;
        st.insert(i*w); mp.insert(i*w);
        mp.insert(((h-i)/2+(h-i)%2)*w);
        mp.insert((h-i)/2*w);
        st.insert((h-i)*(w/2));
        st.insert((h-i)*(w/2+w%2));
        res = min(*st.rbegin()-*st.begin(), min(*mp.rbegin()-*mp.begin(),res));
    }
    cout << res << endl;
}


Measured memory_bytes: 3632
package main

import (
	"fmt"
)

func main() {
	var (
		N    int
		S, T string
	)

	fmt.Scanf("%d", &N)
	fmt.Scanf("%s %s", &S, &T)

	ans := ""
	for i := 0; i < N; i++ {
		ans += string(S[i])
		ans += string(T[i])
	}
	fmt.Println(ans)
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
constexpr long long MOD = 1000000007;
using ll = long long;
int main() {
ll a,b,c;
ll cnt=0;
cin >> a >> b >> c;
if(a%2==1 || b%2==1 || c%2==1){cout << "0" <<endl;
return 0;}
else if(a==b && b==c){cout << "-1" <<endl;
return 0;}
else{
    while(true){
    ll x=(b+c)/2;
    ll y=(a+c)/2;
    ll z=(a+b)/2;
        if(x%2==1||y%2==1||z%2==1){
            cnt++;
            break;
        }
        else{
            a=x;
            b=y;
            c=z;
        cnt++;
        }


    }
}
cout << cnt << endl;
}


Measured memory_bytes: 256
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main {
    public static void main(String[] args) throws Exception {
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int[] t = new int[n];
		int sum = 0;
		for(int i = 0; i < n; i++){
		    t[i] = sc.nextInt();
		    sum += t[i];
		}
		int m = sc.nextInt();
		for(int i = 0; i < m; i++){
		    int p = sc.nextInt()-1;
		    int x = sc.nextInt();
		    System.out.println(sum - t[p] + x);
		}
		
		// 計算
		//int result = 0;
		
		// 出力
		//System.out.println(result);
	}

	public static class Scanner {
		private BufferedReader br; private StringTokenizer tok;
		public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is));}
		private void getLine() throws IOException { while(!hasNext()) tok = new StringTokenizer(br.readLine());}
		private boolean hasNext() { return tok != null && tok.hasMoreTokens();}
		public String next() throws IOException { getLine(); return tok.nextToken();}
		public int nextInt() throws IOException { return Integer.parseInt(next());}
		public long nextLong() throws IOException { return Long.parseLong(next());}
		public double nextDouble() throws IOException { return Double.parseDouble(next());}
	}
}


Measured memory_bytes: 21204
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

int N;
int A[100010];

int main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
  }
  sort(A, A + N);
  ll sum = A[0];
  int ans = 1;
  for (int i = 1; i < N; i++) {
    if (sum * 2 >= A[i]) {
      ans++;
    } else {
      ans = 1;
    }
    sum += A[i];
  }
  cout << ans << endl;

  return 0;
}

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

using namespace std;

#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define N 100001
int main()
{

    ll n,k;
    cin>>n>>k;
    string s;
    cin>>s;
    ll dp[N+1]={0};
    for(ll i=0;i<s.length()-1;i++)
    {
        if(s[i+1]=='C'&&s[i]=='A')
            dp[i+2]=dp[i+1]+1;
        else
            dp[i+2]=dp[i+1];
    }
   // dp[s.length()]=dp[s.length()-1];
    for(int i=0;i<k;i++)
    {
        ll left,right;
        cin>>left>>right;
        cout<<dp[right]-dp[left]<<endl;
    }
}

Measured memory_bytes: 1792
import java.util.*;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int H = sc.nextInt();
        int W = sc.nextInt();
        char [][] s = new char[H+2][W+2];

//        for(int i = 0 ; i <= (H+1) ; i++){
//        	for(int j = 0 ; j <= (W+1) ; j++){
//        		s[i][j] = " ";
//        	}
//        }
        
        String kekka = "Yes";

        for(int i = 1 ; i <= H  ; i++){
            String str = sc.next();
            for(int j = 1 ; j <= W ; j++){
                s[i][j] = str.charAt(j-1);
            }
        }

        for(int i = 1 ; i <= H  ; i++){
            for(int j = 1 ; j <= W ; j++){
                if(s[i][j] == ('#')){
                	if((s[i-1][j] == ('.')) && (s[i][j-1] == ('.')) && (s[i][j+1] == ('.')) && (s[i+1][j] == ('.'))){
                		kekka = "No";
                		break;
                	}
                }
            }
        }

        System.out.println(kekka);
    }
}

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

namespace ConsoleApp1
{
    static class ARedorNot
    {
        static void Main(string[] args)
        {
            var a = int.Parse(Console.ReadLine());
            var s = Console.ReadLine();

            Console.WriteLine(3200 <= a ? s : "red");
            Console.ReadLine();
        }
    }
}

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

#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); 

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define pf push_front
#define mp make_pair
#define pu push
#define pp pop_back
#define in insert
#define ld long double
#define forn(low,high,i) for(i = low;i < high;i++)
#define forrev(high,low,i) for(i = high; i >= low;i--)
#define all(v) v.begin(),v.end()
#define sz(v) (int)v.size()
#define line cout << __LINE__;
#define prv(a) for(auto x : a) cout << x << ' ';cout << '\n';
#define prvp(a) for(auto x : a) cout << "{" << x.ff << ',' << x.ss << "}";cout << '\n';
#define decimal_digits cout << fixed << setprecision(15);
string to_string(string s) { return '"' + s + '"';}
string to_string(char s) { return string(1, s);}
string to_string(const char* s) { return to_string((string) s);}
string to_string(bool b) { return (b ? "true" : "false");}
template <typename A> string to_string(A);
template <typename A, typename B>string to_string(pair<A, B> p) {return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";}
template <typename A> string to_string(A v) {bool f = 1; string r = "{"; for (const auto &x : v) {if (!f)r += ", "; f = 0; r += to_string(x);} return r + "}";}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) {cerr << " " << to_string(H); debug_out(T...);}
#define pr(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

typedef unordered_map<int,int> umi;
typedef unordered_map<ll,ll> uml;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const int inf = 1e9;
const ll INF = 1e18;
const int mod = 1e9 + 7;
const int bit32 = log2(inf) + 3;
const int bit64 = log2(INF) + 3;

inline int add(int a, int b){a += b; if(a >= mod) a -= mod; return a;}
inline int sub(int a, int b){a -= b; if(a < 0) a += mod; return a;}
inline int mul(int a, int b){return (int)((long long) a * b % mod);}
inline int modexpo(int a, int b){int res = 1; while(b > 0){ if(b & 1) res = mul(res, a); a = mul(a, a); b /= 2;} return res;}
inline int divide(int a, int b){ return mul(a, modexpo(b, mod - 2));}

clock_t time_p = clock();

void ktj(){
  time_p = clock() - time_p;
  cerr << "Time elapsed : " << (float)(time_p)/CLOCKS_PER_SEC << "\n";
}

void pre(){ // Reset each global variable (esp. for graphs)
  
}

ll dp(ll n){
  if(n == 1)
    return 1;
  return 1 + 2 * dp(n / 2);
}

void solve(){
  ll n; cin >> n;
  cout << dp(n) << '\n';
}

int main(){
  fastio

  pre();

  int t = 1;
  // cin >> t;
  while(t--){
    solve();
  }

  ktj();
}


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

const int MN = 300010;

int N, B, W;
int A[MN], psum[MN];

bool check(int x) {
    int mx = psum[N - 1];
    for(int i = N - 1; i >= 0; i--) {
        if(i % 2 && mx - psum[i] >= x) {
            mx = max(mx, psum[i] + A[i]);
        }
    }
    return mx >= x;
}

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

    for(int i = 0; i < N; i++) {
        scanf("%d", &A[i]);
        if(i % 2) W += A[i];
        else B += A[i];
    }

    if(N % 2 == 0) {
        printf("%d %d", max(B, W), min(B, W));
        return 0;
    }

    for(int i = 0; i < N; i++) {
        if(i % 2) psum[i] = -A[i];
        else psum[i] = A[i];
        if(i) psum[i] += psum[i - 1];
    }

    int s = 0, e = 1e9, p = -1;
    while(s <= e) {
        int m = (s + e)>>1;

        if(check(m)) {
            p = m;
            s = m + 1;
        }
        else e = m - 1;
    }
    printf("%d %d", W + p, B - p);
}


Measured memory_bytes: 2560
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <set>
#include <map>
#define SIZE 100005
#define INF 100000000000000000LL

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;

P pos[SIZE];
ll left[SIZE],right[SIZE];

int main()
{
	int X,Y,Z;
	scanf("%d %d %d",&X,&Y,&Z);
	int n=X+Y+Z;
	ll ret=0;
	for(int i=0;i<n;i++)
	{
		ll a,b,c;
		scanf("%lld %lld %lld",&a,&b,&c);
		ret+=a;
		pos[i]=P(b-a,c-a);
	}
	sort(pos,pos+n);
	priority_queue <ll> que;
	ll sum=0;
	for(int i=n-1;i>=0;i--)
	{
		P p=pos[i];
		que.push(p.second-p.first);
		sum+=p.first;
		if(n-i<Y) right[i]=-1;
		else
		{
			if(n-i>Y)
			{
				sum+=que.top();
				que.pop();
			}
			right[i]=sum;
		}
	}
	while(!que.empty()) que.pop();
	sum=0;
	for(int i=0;i<n;i++)
	{
		P p=pos[i];
		que.push(p.second);
		if(i+1<X) left[i]=-1;
		else
		{
			if(i+1>X)
			{
				sum+=que.top();
				que.pop();
			}
			left[i]=sum;
		}
	}
	ll rt=-INF;
	for(int i=X-1;i<X+Z;i++)
	{
		rt=max(rt,left[i]+right[i+1]);
	}
	printf("%lld\n",ret+rt);
	return 0;
}


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


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

    
    ll d,t,s;
    cin>>d>>t>>s;
    if(d<=t*s)
    cout<<"Yes";
    else
    cout<<"No";
    return 0;

}

Measured memory_bytes: 3632
#include <stdio.h>
#define NUMBER 10000
int main(void){
  int  i,num;
  int a[NUMBER];
  scanf("%d",&num);

  for(i=0;i<num;i++){
      scanf("%d ",&a[i]);
  }

  int min,max;
  long sum;
  min=max=sum=a[0];
  for(i=1;i<num;i++){
      if(a[i]>max){
      max=a[i];}
      if(a[i]<min){
      min=a[i];}
      sum+=a[i];
  }
  printf("%d %d %ld\n",min,max,sum);
  return 0;
}


Measured memory_bytes: 2104
#include<stdio.h>

int min(int a,int b){return a<b ? a:b;}

int main(void){
    int n,a,b,ans;
    scanf("%d %d %d",&n,&a,&b);
    a=a*n;
    ans=min(a,b);
    printf("%d",ans);
    return 0;
}



Measured memory_bytes: 128
#include<iostream>

using namespace std;

typedef long long ll;

int main(){

  int q;
  cin >> q;
  ll ans = 0;
  while(q--){
    ll p,n;
    char c;
    cin >> p >> c >> n;
    if(c == ')') ans -= n;
    if(c == '(') ans += n;
    if(ans == 0) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}

Measured memory_bytes: 1160
#include <iostream>
#include <algorithm>
#include <math.h>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <utility>
#include <iomanip>  // std::setprecision()
using namespace std;
using ll = long long;
#define rep(i,a,b) for(int i=(a); i<(b); i++)
#define YES cout << "YES" << endl;
#define NO cout << "NO" << endl;
#define yes cout << "Yes" << endl;
#define no cout << "No" << endl;
#define pai 3.14159265358979323846
ll gcd(ll a, ll b){if (a%b == 0)  return(b);else  return(gcd(b, a%b));}
ll lcm(ll a, ll b){return a * b / gcd(a, b);}
/* map<string,int> */
/* 大文字を小文字に変換 tolower*/
/* 小文字を大文字に変換 toupper*/
/* 辞書順 next_permutation(a.begin(),a.end()) */
 
int main() {
    int n;
    cin >> n;
    int div2 =0;
    int div4 =0;
    int tmp;
    rep(i,0,n) {
        cin >> tmp;
        if (tmp %4 == 0) {
            div4++;
        }
        else if (tmp %2 ==0) div2++;
    }
    if (div4 >= n / 2) {
        cout << "Yes" << endl;
    } else if (div2 >= n - div4 * 2) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }

}

Measured memory_bytes: 3084
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define pii pair<int,int>
#define min3(a,b,c) min(a,min(b,c))
#define max3(a,b,c) max(a,max(b,c))
#define all(x) x.begin(),x.end()
#define sz(x) (int)x.size()
#define sp(x) setprecision(x)
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define bs binary_search

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    ll n,k; cin>>n>>k;
    if(500*n>=k) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
}

Measured memory_bytes: 256
/*

    author : s@if

*/

#include<bits/stdc++.h>
using namespace std;

#define 		NIL 			-1
#define		 	fi	 		    first
#define 		sec 			second
#define 		MAX 			INT_MAX
#define			INF 			99999999
#define 		ll 			    long long
#define 		PI 			    acos(-1.0)
#define			MOD 			1000000007
#define 		PLL 			pair<ll,ll>
#define 		PII			    pair<int,int>
#define 		ull 			unsigned long long
#define 		For(i,a,b) 		for(int i=a;i<=(int)b;i++)


bool Check(int N , int pos)	{	return (bool) (N & (1<<pos));}
int Set(int N, int pos) {	return N = N | (1<<pos);}

int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};
int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};
int hr[]={-2,-2,-1,+1,+2,+2,-1,+1};
int hc[]={+1,-1,+2,+2,-1,+1,-2,-2};
int dx[]={+1,-1,+0,+0};
int dy[]={+0,+0,+1,-1};

const int MAXN = (int)1e5+9;

int main()
{
/*	freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);  */

    ll i,j,k,l,m,n,p,q,x,y,u,v,r,tc,t;

    cin>>m>>p>>q;

    for(i=1;i<=10;i++)
    {
        q = q*m-p;

        cout<<q<<endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <iostream>
#include <assert.h>
using namespace std;
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define lc(p) p+p+1
#define rc(p) p+p+2
#define md(s,e) (s+e)/2

int n,k;
int A[300005];
int Max[300005*4];

int rmq( int p, int s, int e , int l, int r ){
	if ( s > r || e < l ) return 0;
	if ( l <= s && e <= r ) return Max[p];
	int m = md(s,e);
	return max(rmq(lc(p),s,m,l,r), rmq(rc(p),m+1,e,l,r));
}

void upd( int p, int s, int e, int x, int v ){
	if ( s == e ){
		Max[p] = max( Max[p], v );
		return;
	}
	int m = md(s,e);
	if ( x <= m ) upd(lc(p),s,m,x,v);
	else upd(rc(p),m+1,e,x,v);
	Max[p] = max(Max[lc(p)], Max[rc(p)]);
}

int main(){

	scanf("%d%d",&n,&k);
	for ( int i = 1; i <= n; i++ ) scanf("%d",&A[i]);

	for ( int i = 1; i <= n; i++ ){
		int L = max(0, A[i] - k), R = min( 300000, A[i] + k );
		upd(0,0,300000, A[i], rmq(0,0,300000,L,R) + 1 );
	}
	printf("%d\n",Max[0]);
	return 0;
}

Measured memory_bytes: 9060
#include <cstdlib>
#include <cmath>
#include <climits>
#include <cfloat>
#include <map>
//#include <utility>
#include <set>
#include <iostream>
//#include <memory>
#include <string>
#include <vector>
#include <algorithm>
//#include <functional>
#include <sstream>
//#include <deque>
#include <complex>
#include <stack>
#include <queue>
#include <cstdio>
//#include <cctype>
#include <cstring>
//#include <ctime>
#include <iterator>
#include <bitset>
//#include <numeric>
//#include <list>
//#include <iomanip>

#if __cplusplus >= 201103L
#include <array>
#include <tuple>
#include <initializer_list>
#include <unordered_set>
#include <unordered_map>
#include <forward_list>

#define cauto const auto&
#else

#endif

using namespace std;


namespace{
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vint;
typedef vector<vector<int> > vvint;
typedef vector<long long> vll, vLL;
typedef vector<vector<long long> > vvll, vvLL;

#define VV(T) vector<vector< T > >

template <class T>
void initvv(vector<vector<T> > &v, int a, int b, const T &t = T()){
    v.assign(a, vector<T>(b, t));
}

template <class F, class T>
void convert(const F &f, T &t){
    stringstream ss;
    ss << f;
    ss >> t;
}


#define reep(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) reep((i),0,(n))
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define F first
#define S second
#define mkp make_pair
#define RALL(v) (v).rbegin(),(v).rend()


#define MOD 1000000007LL
#define EPS 1e-8
static const int INF=1<<24;

void mainmain(){
    ll K, A, B;
    cin >> K >> A >> B;
    if (A+2 >= B) {
        cout << K + 1 << endl;
        return;
    }
    if (A > K) {
        cout << K + 1 << endl;
        return;
    }
    ll ans = A;
    K -= A-1;
    ans += (B-A) * (K/2);
    ans += K%2;
    cout << ans << endl;
}



}

int main() try{
    mainmain();
}
catch(...){
}

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

int main() {
  int N;
  int l;
  int r;
  int x = 0;
  
  cin >> N;
  
  for(int i = 0;i < N;i++){
    cin >> l >> r;
    x = ( r - l  + 1) + x;
  }
  cout << x << endl;
}


Measured memory_bytes: 3588
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <stack>
#include <queue>
using namespace std;

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

#define IS_IN_RANGE(x, w, y, h) ((0 <= x) && (x < w) && (0 <= y) && (y < h))

#define MAX 21
int w, h;
char brd[MAX][MAX];

int sx, sy;

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

int solve(int y, int x)
{
	if (!IS_IN_RANGE(y, h, x, w)) return 0;
	if (brd[y][x] == '#') return 0;
	brd[y][x] = '#';
	int ans = 1;
	rep(i, 4)
		ans += solve(y+dy[i], x+dx[i]);
	return ans;
}

int main()
{
	while (cin >> w >> h, w|h) {
		rep(j, h) rep(i, w) {
			cin >> brd[j][i];
			if (brd[j][i] == '@') {
				sy = j, sx = i;
				brd[j][i] = '.';
			}
		}
		cout << solve(sy, sx) << endl;
	}
	return 0;
}

Measured memory_bytes: 0
import itertools

def main():
  while True:
    n,x=map(int, input().split())
    if n==0:
      break

    nums = [i+1 for i in range(n)]
    c = itertools.combinations(nums, 3)
    
    r=0
    for v in c:
      if v[0]+v[1]+v[2] == x:
        r+=1

    print(r)

if __name__ == '__main__':
  main()


Measured memory_bytes: 5644
#include <stdio.h>

int main(void){
    int x, n;

    scanf("%d", &n);
    for (int i=1; i<=n; i++){
        x = i;
        if (x%3==0){
            printf(" %d", i);
            continue;
        }
        do {
            if (x%10==3){
                printf(" %d", i);
                break;
            }
            x /= 10;
        }while (x);
    }
    printf("\n");
    return 0;
}

Measured memory_bytes: 1028
#include <cstdio>
#include <algorithm>
#include <cstring>

template<int N, typename T, T M>
struct factorial_mod
{
	T mod[N + 1];
	T inv_mod[N + 1];

	constexpr factorial_mod() : mod(), inv_mod()
	{
		mod[0] = 1;
		for (int i = 0; i < N; ++i)
		{
			mod[i + 1] = (mod[i] * (i + 1)) % M;
		}
		inv_mod[N] = power(mod[N], M - 2);
		for (int i = N - 1; i >= 0; --i)
		{
			inv_mod[i] = (inv_mod[i + 1] * (i + 1)) % M;
		}
	}

	constexpr T power(T a, T b) const
	{
		T r = 1;
		while (b > 0)
		{
			if ((b & 1) != 0) r = (r * a) % M;
			a = (a * a) % M;
			b >>= 1;
		}
		return r;
	}

	constexpr T comb(T n, T r) const
	{
		if (r < 0 || r > n || n < 0) return 0;
		return (((mod[n] * inv_mod[r]) % M) * inv_mod[n - r]) % M;
	}
};

constexpr long long MOD = 1000000007;
constexpr factorial_mod<2000020, long long, MOD> fmod;

int main()
{
	long long n, a, b;
	scanf("%lld%lld%lld", &n, &a, &b);
	long long all = (fmod.power(2, n) + (MOD - 1)) % MOD;
	auto c = [&](long long r) {
		long long res = 1;
		for (long long i = 0; i < r; ++i)
		{
			res = (res * (n - i)) % MOD;
		}
		res = res * fmod.inv_mod[r] % MOD;
		return res;
	};
	long long ca = c(a);
	long long cb = c(b);
	long long ans = (all + (MOD - ca) + (MOD - cb)) % MOD;
	printf("%lld\n", ans);
	return 0;
}


Measured memory_bytes: 128
x,n = map(int,input().split())
# p = list(map(int,input().split()))

if n==0:
    print(x)
    exit()

p = set([int(i) for i in input().split()])

for a in range(110):
    if not((x-a) in p):
        print(x-a)
        exit()
    if not((x+a) in p):
        print(x+a)
        exit()

# arr = []
# incc = []
# for i in range(101):
#     for j in range(n):
#         incc.append(p[j])
#     if i in incc:
#         continue
#     else:
#         arr.append(i)
# arr.pop(0)
# # print(arr)
        
# for i in range(1,len(arr)):
#     if n == 0:
#         print(x)
#         break
#     elif x in arr:
#         print(x)
#         break
#     elif x-i or x+i in arr:
#         if x-i in arr:
#             print(x-i)
#             break
#         elif x+i in arr:
#             print(x+i)
#             break

Measured memory_bytes: 9188
import collections

N = int(input())
S = [''] * N

for i in range(N):
        S[i] = str(input())

c = collections.Counter(S)


num = c.most_common()[0][1]
n = 0
ans = []

for k,v in dict(c).items():
        if v != num:
                continue
        else:
                ans.append(k)

for i in sorted(ans):
        print(i)

Measured memory_bytes: 45020
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<ll, ll>;
const ll INF = 1e18;
#define print(x) cout << (x) << endl;
#define rep(i,m,n) for(ll i = (m); i < (n); i++)

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N;
    cin >> N;
    string S;
    cin >> S;
    vector<char> Schar(S.size());
    for (int i = 0; i < S.size(); i++) {
        Schar.at(i) = S.at(i);
    }
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < S.size(); i++) {
            if (Schar.at(i) == 'Z') {
                Schar.at(i) = 'A';
            }
            else {
                Schar.at(i)++;
            }
        }
    }
    for (int i = 0; i < S.size(); i++) {
        cout << Schar.at(i);
    }
    cout << endl;
}

Measured memory_bytes: 256