akhauriyash/Code-Regression huggingface dataset:
<?php
    $a = [];
    $tmp = [];
    for ($i = 3; $i <= 9; $i++) {
        for ($j = 0; $j < pow(3, $i); $j++) {
            $x = str_pad(trans($j, 3), $i, "0", STR_PAD_LEFT);
            $tmp[0] = substr_count($x, "0");
            $tmp[1] = substr_count($x, "1");
            $tmp[2] = substr_count($x, "2");
            if (min($tmp) === 0) continue;
            $y = str_replace("0", "3", $x);
            $y = str_replace("1", "5", $y);
            $y = str_replace("2", "7", $y);
            $a[] = intval($y);
        }
    }
    $a[] = pow(10, 9);
    
    fscanf(STDIN, "%d", $N);
    $ans = 0;
    $cnt = count($a);
    for ($i = 0; $i < $cnt; $i++) {
        if ($a[$i] <= $N) {
            $ans++;
        } else {
            break;
        }
    }
    echo $ans;

    function trans($x, $d) {
        $a = [];
        $keta = 1;
        while(true) {
            $amari = $x % $d;
            $x -= $amari;
            $a[] = $amari;
            $x /= $d;
            if ($x === 0) break;
        }
        return implode("", array_reverse($a));
    }


Measured memory_bytes: 4728
import math
def main():

    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    A = sorted([a // 2 for a in A])
    if max(A) > M: return 0

    pows = set()
    for a in A:
        b = a
        count = 0
        while b % 2 == 0:
            count += 1
            b = b  // 2
        pows.add(count)
    if len(pows) > 1: return 0

    def gcd(a, b):
        if a > b:
            a, b = b, a
        if a == 0: return b
        return gcd(b % a, a)

    prev = 1
    for i in range(len(A)):
        c = gcd(prev, A[i])
        prev = (prev // c) * A[i]

    return (M // prev  + 1) // 2

if __name__ == '__main__':
    print(main())

Measured memory_bytes: 65184
S = input().rstrip()
N = len(S)
for i in range((N - 1) // 2):
    if S[i] != S[N-1-i]:
        print("No")
        exit(0)
s = S[:(N-1) // 2]
n = len(s)
if n == 2 and s[0] != s[1]:
    print("No")
    exit(0)

for i in range((n - 1) // 2):
    if s[i] != s[n-1-i]:
        print("No")
        exit(0)
print("Yes")


Measured memory_bytes: 3064
#include <cstdio>
#include <cstring>
#include <stack>
#include <vector>
#include <algorithm>
#include<iostream>
#include<cmath>
#define MAXN 1000
using namespace std;
int n,k,mins;
int s[3000];
int ln=0;
int main () {
   cin>>n;
   int flag=1;
   if(n<0){
   	flag=-1;
   }
   int ans=0,i=0;
   int k,t;
   int base=-2;
   if(n==0){
   	cout<<ans;
   }else{
   	while(n!=0){
   		k=n%(-2);
   		t=n/(-2);
   		if(k<0){
		k-=(-2);
		t++;
	   }
	   i++;
		n=t;
	 	s[i]=k;
   }
	for(int j=i;j>0;j--){
		cout<<s[j];
	}
}
   
    return 0;
}


Measured memory_bytes: 256
datas = []

while data = gets
  datas << data.split(",").map(&:to_i)
end

x = 0
y = 0
prev_rad = 90 * Math::PI / 180.0

datas.each do |data|
  x += data[0] * Math.cos(prev_rad)
  y += data[0] * Math.sin(prev_rad)
  prev_rad -= data[1] * Math::PI / 180.0
end

puts x.to_i
puts y.to_i

Measured memory_bytes: 6172
#include <stdio.h>

int read()
{
	char c;
	while((c = getchar()) < 48 || c > 57);
	int x = c - 48;
	while((c = getchar()) > 47 && c < 58) x = x * 10 + c - 48;
	return x;
}

int main()
{		
	int n, i;
	int c[4] = {0};
	
	n = read();
	for(i = 0; i < n; i++){
		c[read() % 4]++;
	}
	if(c[1] + c[3] <= c[0] + (!c[2])) puts("Yes");
	else puts("No");
				
	return 0;
}

Measured memory_bytes: 1528
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		String op = scan.next();
		int b = scan.nextInt();

		if(op.equals("+")) {
			System.out.println(a+b);
		}else {
			System.out.println(a-b);
		}
	}

}


Measured memory_bytes: 21844
n = gets.to_i
a = [nil] + gets.split.map(&:to_i)
b = [nil] + gets.split.map(&:to_i)
c = [nil] + gets.split.map(&:to_i)
s = 0
i = 1
prev = nil
while i < n+1
  s += b[a[i]]
  s += c[prev] if prev && a[i] == prev + 1
  prev = a[i]
  i += 1
end
p s


Measured memory_bytes: 1788
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

int main(){
	char s[567];
	int i,q[4],l;
	for(i=0;i<300;i++){
		s[i]=0;
	}
	for(i=0;i<4;i++){
		q[i]=0;
	}
	cin >> s;
	for(i=0;i<300;i++){
		if(s[i]=='K'){
			q[0]++;
		}
		if(s[i]=='U'){
			q[1]++;
		}
		if(s[i]=='P'){
			q[2]++;
		}
		if(s[i]=='C'){
			q[3]++;
		}
	}
	for(i=1;i<4;i++){
		for(int j=0;j<4;j++){
			if(q[j]>q[j+1]){
				l=q[j]; q[j]=q[j+1]; q[j+1]=l;
			}
		}
	}
	cout << q[0] << "\n";
return 0;
}

Measured memory_bytes: 1148
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
int n;
vector<int> shift(int x, vector<int> v) {
    vector<int> ans(n);
    ans = v;
    int tmp = ans[n-1];
    for(int i=x;i<=n-1;i++) ans[i] = v[i-1];
    ans[x-1] = tmp;
    return ans;
}
void print(vector<int> a) {
    rep(i, n) printf("%d ",a[i]);
    puts("");
}
int main() {
    int k; cin >> n >> k;
    vector<int> v(n);
    rep(i, n) cin >> v[i];
    int ans = 0;
    rep(x, min(k,n)){
        if(x!=0)
        v = shift(x,v);
        //print(v);
        for(int i=1;i<=k&&i<=n;++i) {
            int tmp = 0;
            priority_queue<int,vector<int>,greater<int>> q;
            for(int j=i;j>0;j--) {
                q.push(v[j-1]);
                tmp += v[j-1];
            }
            for(int j=k-i;j>0;j--) {
                int bk = q.top();
                if(!q.empty()&&bk<0) {
                    q.pop();
                    tmp -= bk;
                }
                else break;
            }
            ans = max(ans, tmp);
        }
    }
    cout << ans;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const ll INF = mod * mod;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)

int main() {
    int K, A, B; cin >> K >> A >> B;
    bool flag = false;
    for (int i = A; i <= B; i++) {
        if (i % K == 0) flag = true;
    }
    if (flag) cout << "OK" << endl;
    else cout << "NG" << endl;
}

Measured memory_bytes: 3636
def next(i, j):
    nextI = i
    nextJ = j
    if i % 2 == 0:
        nextJ = j + 1
    else:
        nextJ = j - 1
    if nextJ < 0 or nextJ >= W:
        nextJ = j
        nextI = i+1
    return nextI, nextJ


H, W = [int(x) for x in input().split()]
a = []
for n in range(0, H):
    a.append([int(x) for x in input().split()])


isFinded = (a[0][0] % 2 == 1)
cI, cJ = 0, 0

list = []
for n in range(0, H*W-1):
    nextI, nextJ = next(cI, cJ)
    if (isFinded):
        # print("{},{},{},{}".format(cI+1, cJ+1, nextI+1, nextJ+1))
        list.append("{} {} {} {}".format(cI+1, cJ+1, nextI+1, nextJ+1))
    if (a[nextI][nextJ] % 2 == 1):
        isFinded = not (isFinded)
    cI = nextI
    cJ = nextJ

print(len(list))
for l in list:
    print(l)


Measured memory_bytes: 16220
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;



public class Main {

	public static class pair implements Comparable<pair> {
		int id;
		int ans;
 
		pair(int x, int y) {
 
			id = x;
			ans = y;
 
		}
 
		public pair() {
 
		}
 
		public int compareTo(pair o) {
			// TODO Auto-generated method stub
 
			return this.id - o.id;
		}
	}
 
//	static int mod = (int) 998244353.;
	static ArrayList<Integer> gr[];
	static int[] ar;
	static Scanner sc = new Scanner(System.in);
	static int pri[] = new int[(int) 1e6 + 5];
	static StringBuilder out = new StringBuilder();
 
	//static long dp[];
 
	public static void main(String[] args) throws IOException {
		int t =1;//sc.nextInt();
		
		while (t-- > 0) {
 
			long ru=sc.nextLong();
			long val=100;
			long n=0;
			while(val<ru) {
				val+=val/100;
				n++;
			}
			System.out.println(n);
			
			
		}
		
		System.out.println(out);
	}
	
 
	
}

Measured memory_bytes: 39608
w =str(input())

length = len(w)
z = sorted(w)
i=1
m=0
   
if length%2 == 1:
    m = 1
    pass
else:
    while i < length:        
        if z[i]==z[i-1]:
            i += 2
        else:
            m = 1
            break
        
if m == 1:
    print("No")
else:
    print("Yes")
    

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




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

  int a[n];

  for(int i = 0 ;i < n ; i++)
    cin >> a[i];


int count = 1;
int minsofar = a[0];

for(int i = 1; i < n; i++)
{
    if(a[i] <= minsofar)
    {
        count++;
        minsofar = a[i];
    }
    
}


    cout << count << endl;

  

  return 0;
}


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

using namespace std;

int main(){
	string s;
	cin >> s;
	int ans = 0;
	for(int i = 0;i < s.size();i++){
		if(s[i] == '+'){
			ans++;
		}else{
			ans--;
		}
	}
	cout << ans << endl;
	return 0;
}

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

using namespace std;
#define rep(i, n) for (int64_t i = 0; i < n; i++)

const double PI = 3.14159265358979323846;

vector<vector<int64_t>> data1;

void search(vector<int64_t> data, int depth)
{
}


int main()
{
	int n;
	cin >> n;
	switch(n % 10)
	{
	case 3:
		puts("bon");
		break;
	case 0:
	case 1:
	case 6:
	case 8:
		puts("pon");
		break;
	default:
		puts("hon");
		break;
	}
	return 0;
}

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

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  for (auto &v : vec) {
    int tmp;
    cin >> tmp;
    v = tmp - 1;
  }

  int cnt = 0;
  for (int i = 0; i < n; ++i) {
    cnt += vec[vec[i]] == i;
  }

  cout << cnt / 2 << endl;
}


Measured memory_bytes: 3784
a,b,c,x,y = map(int,input().split())
ab = min(a + b,c * 2)
ccc = min(x,y)
ans = ccc * ab
x-=ccc
y-=ccc
if y == 0:
	print(ans + min(x * a,x * ab))
else:
	print(ans + min(y * b,y * ab))

Measured memory_bytes: 3060
#include <iostream>
#include <string>
#include <cmath>
#include<algorithm>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#define _USE_MATH_DEFINES
#include <math.h>
#include <functional>
using namespace std;

#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)

typedef long long ll;
const ll INF = 1e17;
const ll MOD = 998244353;
const ll MAX = 4000001;

ll max(ll a, ll b) {
	if (a > b) { return a; }
	return b;
}

ll min(ll a, ll b) {
	if (a > b) { return b; }
	return a;
}

ll gcd(ll a, ll b) {
	if (b == 0) { return a; }
	if (a < b) { return gcd(b, a); }
	return gcd(b, a % b);
}

ll lcm(ll a, ll b) {
	return a / gcd(a, b) * b;
}

struct edge {
	ll ind;
	ll fr;
	ll to;
	ll d;
};

class mint {
    long long x;
public:
    mint(long long x = 0) : x((x% MOD + MOD) % MOD) {}
    mint operator-() const {
        return mint(-x);
    }
    mint& operator+=(const mint& a) {
        if ((x += a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator-=(const mint& a) {
        if ((x += MOD - a.x) >= MOD) x -= MOD;
        return *this;
    }
    mint& operator*=(const  mint& a) {
        (x *= a.x) %= MOD;
        return *this;
    }
    mint operator+(const mint& a) const {
        mint res(*this);
        return res += a;
    }
    mint operator-(const mint& a) const {
        mint res(*this);
        return res -= a;
    }
    mint operator*(const mint& a) const {
        mint res(*this);
        return res *= a;
    }

    mint operator^(const ll& t)const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }
    // for prime MOD
    mint inv() const {
        return pow(MOD - 2);
    }
    mint& operator/=(const mint& a) {
        return (*this) *= a.inv();
    }
    mint operator/(const mint& a) const {
        mint res(*this);
        return res /= a;
    }

    friend ostream& operator<<(ostream& os, const mint& m) {
        os << m.x;
        return os;
    }
};

//////////////////////////

vector<mint> frac;
vector<mint> ivfrac;
void fracinit(ll N) {
    frac.assign(N + 1, 0);
    ivfrac.assign(N + 1, 0);
    frac[0] = 1;
    ivfrac[0] = 1;
    repn(i, N) {
        frac[i] = frac[i - 1] * i;
        ivfrac[i] = ivfrac[i - 1] / i;
    }

}

mint com(ll i, ll j) {
    if (i < 0 || j < 0) { return 0; }
    if (j > i) { return 0; }
    return frac[i] * ivfrac[j] * ivfrac[i - j];
}

mint hom(ll i, ll j) {
    return com(i + j - 1, i);
}

mint ans(ll x,ll N, ll K) {
    mint ret = 0;
    rep(i, x + 1) {
        ret += com(x, i) * hom(N - i, K - x);
    }
    return ret;
}

int main() {
    ll N, K;
    cin >> K >> N;
    fracinit(K + N + 1);
    for (ll i = 2; i <= 2 * K; i++) {
        ll x = min(i, 2 * K + 2 - i) / 2;
        cout << ans(x,N,K) << endl;
    }



    
    

    system("PAUSE");
}

Measured memory_bytes: 632
#include<bits/stdc++.h>
using namespace std;
int main(){
    int N, M, a, b;
    cin >> N >> M;
    vector<int> A(N);
    for(int i = 0; i < M; i++){
        cin >> a >> b;
        A.at(a - 1)++;
        A.at(b - 1)++;
    }
    for(int i = 0; i < N; i++){
        cout << A.at(i) << endl;
    }
    return 0;
}

Measured memory_bytes: 3628
#include <bits/stdc++.h>
using namespace std;
int main(){
    int N;
    cin >> N;
    int tmp1, tmp2;
    long long sum;
    cin >> tmp1;
    sum = tmp1;
    for(int i=0;i<N-2;i++){
        cin >> tmp2;
        if(tmp1 < tmp2) sum += tmp1;
        else sum += tmp2;
        tmp1 = tmp2;
    }
    
    cout << sum + tmp1 << "\n";
}


Measured memory_bytes: 256
#include <iostream>
#include <cassert>
#define DEVISOR 1000000007ULL
using namespace std;
typedef unsigned long long ull;

ull power(int m, int n, ull d) {
    assert(m>0 && n>=0 && d>0);

    ull ans = 1;

    if(n>0){
        ans = power(m, n/2, d);
        if(n%2) {
            ans = (((ans * ans ) % d) * m) % d;
        } else {
            ans = (ans * ans ) % d;
        }
    }
    return ans;
}

int main(void) {
    int m,n;
    cin >> m >> n;
    
    cout << power(m,n,DEVISOR) << endl;
    return 0;
}


Measured memory_bytes: 3092
n,c=map(int,input().split())
S=[]
for i in range(n):
    x,v=map(int,input().split())
    S.append([x,v])

F=[0]
rF=[0]
s=0
for i in range(n):
    s+=S[i][1]
    F.append(max(s-S[i][0],F[-1]))
    rF.append(max(s-2*S[i][0],rF[-1]))

S=list(reversed(S))
R=[0]
rR=[0]
s=0
for i in range(n):
    s+=S[i][1]
    R.append(max(s+S[i][0]-c,R[-1]))
    rR.append(max(s+2*(S[i][0]-c),rR[-1]))
    
R=list(reversed(R))
rR=list(reversed(rR))

ans=0
for i in range(n+1):
    ans=max(F[i]+rR[i],ans)
    ans=max(R[i]+rF[i],ans)
    
print(ans)

Measured memory_bytes: 33688
#include<stdio.h>
int main(){
  int n,h,m,t,i;
  char s[3][10]={"lunch","dinner","midnight"};
  while(scanf("%d",&n),n){
    int o[3]={0};
    int c[3]={0};
    while(n--){
      scanf("%d%*c%d %d",&h,&m,&t);
      if(m>t)t+=60;
      h=h*100+m;
      i=3;
      if(1100<=h&&h<=1459)i=0;
      if(1800<=h&&h<=2059)i=1;
      if(2100<=h&&h<=2400)i=2;
      if(   0<=h&&h<= 159)i=2;
      if(3-i){
	if(t-m<9)o[i]++;
	c[i]++;
      }
    }
    for(i=0;i<3;i++){
      printf("%s ",s[i]);
      if(c[i])printf("%d\n",(o[i]*100)/c[i]);
      else    printf("no guest\n");
    }    
  }
    return 0;
}

Measured memory_bytes: 612
#include<iostream>
#include<string>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<utility>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<unordered_set>
#include<unordered_map>
#include<bitset>
#include<iomanip>
#include<list>
#include<deque>
using namespace std;
//#define MODE 1
#ifdef MODE
#define DEB(X) cout<< #X <<": "<<X<<" ";
#define DEB2(X) cout<<X<<" ";
#define END cout<<endl;
#else
#define DEB(X) {}
#define DEB2(X) {}
#define END {}
#endif
typedef long long ll;
#define int ll
#define uset unordered_set
#define umap unordered_map
//typedef std::pair<int,int> P;
struct edge{int to,cost;};
const int INF=100000000000000000;
const int INF2=9223372036854775807;
const int MOD=1000000007;
#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define min(X,Y) (((int)(X)<(int)(Y))?(X):(Y))
#define max(X,Y) (((int)(X)>(int)(Y))?(X):(Y))
#define NP(X,Y) next_permutation(X,Y)
#define setdouble(X,Y) cout<<fixed<<setprecision(X)<<Y
int ceil2(int a,int b){if(a%b==0){return a/b;}else{return a/b+1;}}
int pow2(int a,int b){int r=1;for(int i=1;i<=b;i++){r*=a;}return r;}
int Log2(int a){int t=0;while(1){if(a==0||a==1){break;}a/=2;t++;}return t;}

int N;
int A[200010];
int B[200010];

signed main(){
	cin>>N;
	REP(i,N-1){
		cin>>A[i];
	}
	REP(i,N-1){
		B[A[i]-1]++;
	}
	REP(i,N){
		cout<<B[i]<<endl;
	}
	return 0;
}


Measured memory_bytes: 6716
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define PI 3.1415927


using namespace std;

char a[19];



int main()
{
	cin >> a;
	for (int i = 0;i < 19;i++)
	{
		if (a[i] == ',')
		{
			a[i] = ' ';
		}
	}

	cout << a;

	
	//system("pause");
}

Measured memory_bytes: 256
#include <stdio.h>
#include <iostream>
#include <string>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <sstream>
#include <fstream>
#include <iomanip>

#define rep(i,a,b) for(long long i=a;i<b;i++)

using namespace std;
int combination(int n, int r)
{
	if (r == 0 || r == n)
		return (1);
	else if (r == 1)
		return (n);
	return (combination(n - 1, r - 1) + combination(n - 1, r));
}


int main(void) {

	long long N = 0, A = 0, B = 0, X = 0, Y = 0;
	long long big = 0, big2 = 0;
	long long c = 0;
	long long a[10000];
	cin >> N;

	rep(i, 0, N) {
		cin >> a[i];
		//cout << a[i] << endl;
	}
	
	long long j = 0;

	while(j<N) {

		if(a[j] % 2 != 0 || a[j] == 0){
			j++;
			
		}
		else {
			a[j] /= 2;
			c++;
		}
		//cout << a[0] << a[1]<< a[2]<<endl;
		
	}

	cout << c << endl;

	return 0;

}

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

int main() {
  int x;
  cin >> x;
  int count1 = 0;
  int ans = 0;
  int y = x;

  while(x >= 500){
    x -= 500;
    ans += 1000;
    count1++;
  }

  y -= 500 * count1;

  while(y >= 5){
    y -= 5;
    ans += 5;
  }

  cout << ans << endl;
  
}



Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
int main(){
    int n;
    cin>>n;
    int f=0;
    int cnt=0;
    for(int i=0;i<n;i++)
    {
        int x,y;
        cin>>x>>y;
        if(x==y)
        {
            if(cnt==2 ) f=1;
            cnt=(cnt+1)%3;

        }
        else cnt=0;
    }
    if(f) cout<<"Yes";
    else cout<<"No";

}

Measured memory_bytes: 3632
import qualified Data.ByteString.Char8 as BS
import qualified Data.List as L
import qualified Data.Set as S
import qualified Control.Monad as M
import Data.Maybe (fromJust)
import Data.Ord
import qualified Data.Vector.Unboxed as V



main = do

 [a,b,c,k] <- map (fst.fromJust.BS.readInt) <$>BS.words<$>BS.getLine :: IO [Int]
 print $ if a>k
  then k
  else
   if b>(k-a)
    then a
    else a-(k-a-b)

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

int main() {
	std::string A;
	std::cin >> A;

	if (A == "000")
		std::cout << 0 << std::endl;
	else if (A == "110")
		std::cout << 2 << std::endl;
	else if (A == "101")
		std::cout << 2 << std::endl;
	else if (A == "011")
		std::cout << 2 << std::endl;
	else if (A == "111")
		std::cout << 3 << std::endl;
	else
		std::cout << 1 << std::endl;

	return 0;
}

Measured memory_bytes: 256
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define int long long
#define y second
#define inf 1000000000000000000
#define N 1000000007
#define speed ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
template<class L,class R> ostream& operator<<(ostream& cout,pair<L, R> P)
{return cout<<'('<<P.x<<','<< P.y<<')';}
template<class T> ostream& operator<<(ostream& cout,vector<T> V)
{cout<<"[ ";for(auto v:V)cout<<v<<' ';return cout<<']';}

set<int> zro;
set<int> one;
vector<vector<int>> g;
//edge cases when n=1,m=1.wrong variable in loop.if<->while;merge resize;LLONG_MAX
signed main()
{
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt","r",stdin);
    //#endif
    speed
    //global var
    int n,sum=0;
    cin>>n;
    int diff=0;
    for(int i=0;i<n;++i){
        int tmp;cin>>tmp;sum+=tmp;sum%=N;
        diff+=tmp*tmp;diff%=N;
    }
    int ans=(((((sum*sum)%N)-diff)*500000004)%N);
    ans+=N;
    ans%=N;
    cout<<ans<<"\n";
}
//try thinking from a different angle after spending some time


Measured memory_bytes: 3648
import math
n,d = map(int,input().split())
point = [list(map(int,input().split())) for _ in range(n)]

def dist(x,y):
    distance = math.sqrt(x**2 + y**2)
    return distance

cnt = 0
for i in range(n):
    if dist(point[i][0],point[i][1]) <= d:
        cnt += 1

print(cnt)

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

#define rep(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define rng(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define rbf(i, v) for (auto& (i) : (v))
#define All(x) (x).begin(),(x).end()
#define cAll(x) (x).cbegin(),(x).cend()
#define COL(x) cout << x << endl
#define CO(x) cout << x
//#define int long long

template<typename T> inline constexpr auto square(T x) { return (x) * (x); }

typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef vector<PII> VP;

const int MOD = 1000000007;
const int INF = INT_MAX;

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

	VI d(N);
	rbf(dd, d) {
		cin >> dd;
	}

	sort(All(d));

	int sub = d[N / 2] - d[N / 2 - 1];

	COL(sub);

	return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <map>

using namespace std;

int main() {
  int n;
  cin >> n;
  map<char, int> m, s;
  string S;
  for (char c = 'a'; c <= 'z'; ++c) m[c] = 50;
  while (cin >> S) {
    s.clear();
    for (char c : S) ++s[c];
    for (char c = 'a'; c <= 'z'; ++c) m[c] = min(m[c], s[c]);
  }
  S = "";
  for (char c = 'a'; c <= 'z'; ++c) S += string(m[c], c);
  cout << S << endl;
}


Measured memory_bytes: 3544
n,k=map(int,input().split())
c=list(map(int,input().split()))
dp=[0]*n
dp[0]=0
for i in range(1,n):
    dp[i]=min([dp[j]+abs(c[i]-c[j]) for j in range(max(0,i-k),i)])
print(dp[-1])

Measured memory_bytes: 52592
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
ans=0
for i in range(N):
  tmp=min(A[i],B[i])
  ans+=tmp
  tmp=min(A[i+1],B[i]-tmp)
  A[i+1]-=tmp
  ans+=tmp
print(ans)

Measured memory_bytes: 24124
#include <bits/stdc++.h> // Tomasz Nowak
using namespace std;     // XIII LO Szczecin
using LL = long long;    // Poland
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define REP(i, n) FOR(i, 0, (n) - 1)
template<class T> int size(T &&x) {
	return int(x.size());
}
template<class A, class B> ostream& operator<<(ostream &out, const pair<A, B> &p) {
	return out << '(' << p.first << ", " << p.second << ')';
}
template<class T> auto operator<<(ostream &out, T &&x) -> decltype(x.begin(), out) {
	out << '{';
	for(auto it = x.begin(); it != x.end(); ++it)
		out << *it << (it == prev(x.end()) ? "" : ", ");
	return out << '}';
}
void dump() {}
template<class T, class... Args> void dump(T &&x, Args... args) {
	cerr << x << ";  ";
	dump(args...);
}
#ifdef DEBUG
  struct Nl{~Nl(){cerr << '\n';}};
# define debug(x...) cerr << (strcmp(#x, "") ? #x ":  " : ""), dump(x), Nl(), cerr << ""
#else
# define debug(...) 0 && cerr
#endif
mt19937_64 rng(0);
int rd(int l, int r) {
	return uniform_int_distribution<int>(l, r)(rng);
}
// end of templates

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

	int a, b;
	cin >> a >> b;
	FOR(x, 0, int(1e6))
		if((x * 8) / 100 == a and (x * 10) / 100 == b) {
			cout << x << '\n';
			return 0;
		}
	cout << "-1\n";
}


Measured memory_bytes: 256
from itertools import combinations


def main():
    N = int(input())
    points = [list(map(int, input().split())) for _ in range(N)]
    ans = N
    for i, j in combinations(range(N), 2):
        p1, p2 = points[i], points[j]
        if p1 == p2:
            continue
        dx, dy = p1[0] - p2[0], p1[1] - p2[1]
        cost = N
        for k, l in combinations(range(N), 2):
            p3, p4 = points[k], points[l]
            if (p3[0] + dx == p4[0] and p3[1] + dy == p4[1]) or \
                    (p4[0] + dx == p3[0] and p4[1] + dy == p3[1]):
                cost -= 1
        ans = min(ans, cost)
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 9200
N,K = map(int,input().split())
P = list(map(int,input().split()))
if K==N:
    print(1)
    exit()

cum_asc = [0]
for p,q in zip(P,P[1:]):
    cum_asc.append(cum_asc[-1] + int(p<q))
all_asc = []
for i in range(N-K+1):
    all_asc.append(cum_asc[i+K-1] - cum_asc[i] == K-1)

from collections import deque
sldmin = []
sldmax = []
qmin = deque()
qmax = deque()
for i,p in enumerate(P):
    while qmin and qmin[-1] > p:
        qmin.pop()
    qmin.append(p)
    if i-K-1 >= 0 and P[i-K-1] == qmin[0]:
        qmin.popleft()
    while qmax and qmax[-1] < p:
        qmax.pop()
    qmax.append(p)
    if i-K-1 >= 0 and P[i-K-1] == qmax[0]:
        qmax.popleft()
    if i >= K:
        sldmin.append(qmin[0])
        sldmax.append(qmax[0])

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1
        self.count += 1
    def components(self):
        return len(self.parent) - self.count

uf = UnionFind(N-K+2)
for i,(l,r,mn,mx) in enumerate(zip(P,P[K:],sldmin,sldmax)):
    if l==mn and r==mx:
        uf.unite(i,i+1)
if all(f == False for f in all_asc):
    print(uf.components() - 1)
    exit()

def_i = N-K+1 #same as default P
for i,f in enumerate(all_asc):
    if f:
        uf.unite(i, def_i)
print(uf.components())

Measured memory_bytes: 37288
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();
		int d = scan.nextInt();
		do {
			c -= b;
			if (c <= 0) {
				System.out.println("Yes");
				break;
			}
			a -= d;
			if (a <= 0) {
				System.out.println("No");
				break;
			}
		} while (true);
	}
}

Measured memory_bytes: 35760
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
struct Dice{
  int s[6];
  void roll(char c){
    //the view from above
    // N
    //W E
    // S
    //s[0]:top
    //s[1]:south
    //s[2]:east
    //s[3]:west
    //s[4]:north
    //s[5]:bottom
    int b;
    if(c=='E'){
      b=s[0];
      s[0]=s[3];
      s[3]=s[5];
      s[5]=s[2];
      s[2]=b;
    }
    if(c=='W'){
      b=s[0];
      s[0]=s[2];
      s[2]=s[5];
      s[5]=s[3];
      s[3]=b;
    }
    if(c=='N'){
      b=s[0];
      s[0]=s[1];
      s[1]=s[5];
      s[5]=s[4];
      s[4]=b;
    }
    if(c=='S'){
      b=s[0];
      s[0]=s[4];
      s[4]=s[5];
      s[5]=s[1];
      s[1]=b;
    }
    
    // migi neji 
    if(c=='R'){
      b=s[1];
      s[1]=s[2];
      s[2]=s[4];
      s[4]=s[3];
      s[3]=b;
    }
    
    if(c=='L'){
      b=s[1];
      s[1]=s[3];
      s[3]=s[4];
      s[4]=s[2];
      s[2]=b;
    }
    
  }
  int top() {
    return s[0];
  }
  int hash(){
    int res=0;
    for(int i=0;i<6;i++) res=res*256+s[i];
    return res;
  }
};
vector<Dice> makeDices(Dice d){
  vector<Dice> res;
  for(int i=0;i<6;i++){
    Dice t(d);
    if(i==1) t.roll('N'); 
    if(i==2) t.roll('S'); 
    if(i==3) t.roll('S'),t.roll('S');
    if(i==4) t.roll('L'); 
    if(i==5) t.roll('R'); 
    for(int k=0;k<4;k++){
      res.push_back(t);
      t.roll('E');
    }
  }
  return res;
}
//END CUT HERE

signed ITP1_11_A(){
  Dice d;
  for(int i=0;i<6;i++) cin >> d.s[i];
  string s;cin >> s;
  for(int i=0;i<(int)s.size();i++) d.roll(s[i]);
  cout << d.top() << endl;
  return 0;
}

/*
  verified on 2018/02/09
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_11_A
*/

signed AOJ_0502(){
  Int n;
  while(cin>>n,n){
    Dice d;
    for(Int i=0;i<6;i++) d.s[i]=i+1;

    Int ans=d.top();
    for(Int i=0;i<n;i++){
      string s;
      cin>>s;
      d.roll(s[0]);
      ans+=d.top();
    }
    cout<<ans<<endl;
  }
  
  return 0;
}


/*
  verified on 2018/02/09
  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0502
*/

signed main(){
  AOJ_0502();
  return 0;
}



Measured memory_bytes: 3084
#include <bits/stdc++.h>
#define rep( i, n ) for( int ( i ) = 0; ( i ) < ( n ); ( i )++ )
#define repr( i, n ) for( int ( i ) = ( n ); ( i ) >= 0; ( i )-- )
#define FOR( i, m, n ) for( int ( i ) = ( m ); ( i ) < ( n ); ( i )++ )
#define all( x ) ( x ).begin(), ( x ).end()
typedef long long lint;
using namespace std;

int main( void ){
	
	double t, x;
	
	cin >> t >> x;
	
	double ret ;
	
	ret = t / x;
	
	cout << ret << endl;
	
	return 0;
	
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <array>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <list>
#include <numeric>
#include <stack>
#include <iomanip>
#include <random>
#include <complex>
#include <functional>
#include <tuple>

using namespace std;

#define Rep(i,a,b) for(int i = a; i < b; ++i)
#define rep(i,b) Rep(i,0,b)
#define allof(a) (a).begin(), (a).end()

#define Yes(q) ((q) ? "Yes" : "No")
#define YES(q) ((q) ? "YES" : "NO")
#define Possible(q) ((q) ? "Possible" : "Impossible")
#define POSSIBLE(q) ((q) ? "POSSIBLE" : "IMPOSSIBLE")

using ll = long long;

using pint = std::pair<int, int>;
using pll = std::pair<ll, ll>;


constexpr int inf = 1e9 + 7;
constexpr ll infll = 1ll << 62ll;
constexpr ll mod = 1e9 + 7;
// 0~3までは右左下上 4~7までは斜め
constexpr int dx[] = { 1, 0, -1, 0, 1, 1, -1, -1 };
constexpr int dy[] = { 0, -1, 0, 1, 1, -1, -1, 1 };

namespace {
    template<typename T> void chmax(T& a, T b) { a = std::max(a, b); }
    template<typename T> void chmin(T& a, T b) { a = std::min(a, b); }
    template<typename T> void chadd(T& a, T b) { a = a + b; }

    void Cout(long long x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const T& x, const char* end = "\n") { std::cout << x << end; }
    template <typename T> void Cout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cout << x[i] << (i == sz - 1 ? end : sep); } }

    void CCout(long long x, const char* end = "\n") { std::cerr << x << end; }
    template <typename T> void CCout(const T& x, const char* end = "\n") { std::cerr << x << end; }
    template <typename T> void CCout(const std::vector<T>& x, const char* sep = " ", const char* end = "\n") { for (std::size_t i = 0, sz = x.size(); i < sz; i++) { std::cerr << x[i] << (i == sz - 1 ? end : sep); } }

    // 標準入出力
    struct inp {
        std::size_t sz;
        inp(std::size_t _sz = 1) : sz(_sz) {}
        template <typename T> operator T () const { T a; std::cin >> a; return a; }
        template <typename T> operator std::vector<T>() const { vector<T> a(sz); for (std::size_t i = 0; i < sz; i++) std::cin >> a[i]; return a; }
        template <typename T, typename U> operator std::pair<T, U>() const { T f; U s; std::cin >> f >> s; return std::pair<T, U>(f, s); }
    };

    inp inp1; // input one
}

int main() {

    string s = inp1;

    int num = 0;

    bool out = false;

    if (s[0] != 'A') out = true;

    Rep(i, 2, s.length() - 1) {
        if (s[i] == 'C') {
            ++num;
        }
        else {
            if (s[i] < 'a') out = true;
        }
    }

   
    if (num != 1) out = true;
    if (s[s.length() - 1] < 'a') out = true;
    if (s[1] < 'a') out = true;

    if (out) Cout("WA");
    else Cout("AC");

    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


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

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <queue>
#include <algorithm>
#include <string>
#include <vector>
#include <map>
#include <functional>
using namespace std;

int main() {
	int x0, y0, x1, y1;
	cin >> x0 >> y0 >> x1 >> y1;

	int XX = x1 - x0, YY = y1 - y0;
	int x2 = x1 - YY, y2 = y1 + XX;
	int x3 = x2 - XX, y3 = y2 - YY;
	cout << x2 << " " << y2 << " " << x3 << " " << y3 << endl;
	return 0;
}

Measured memory_bytes: 256
#include<algorithm>
#include<string>
#include<stdio.h>
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<utility>
#include<functional>
#include<cassert>
#include<cmath>
#include<math.h>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef vector<int> vint;
typedef vector<vint> vvint;
#define PI 3.1415926535;
#define MOD 1000000007;
#define rep(i, n) for(int i=0;i<(n);i++)


int main(void) {
	string s;
	cin >> s;
	int ans = 0;
	int n = s.size();
	for (int i = 0; i < n / 2; i++) {
		if (s[i] != s[n - 1-i]) {
			ans++;
		}
	}
	cout << ans << endl;
}

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

using namespace std;
//15min
const int N = 55;

const int mod = 1e9+7;

long long s;

long long l(long long    x){
    int cnt = 0;
    while(x){
        cnt++;
        x /= 10;
    }
    return cnt;
}

long long get(int msk){
    long long sum = 0;
    long long sofar = 0;


    long long idx = 0;
    long long tmp = s;
    long long ten = 1;
    //cout << msk << ": ";
    while(tmp){
        sum = (tmp % 10) * ten + sum;
        ten *= 10;
        if(msk & (1 << idx)){
            //cout << sum << " ";
            sofar += sum;
            sum = 0;
            ten = 1;
        }
        idx ++;
        tmp /= 10;
    }
    sofar += sum;
    //cout << sum << "\n";
    return sofar;
}

int main(){
    cin >> s;
    if(s <= 9){
        cout << s << "\n";
        return 0;
    }
    int lg10 = log10(s);
    long long ans = s;
    for(int i = 1; i < (1 << lg10); i++){
        ans += get(i);
    }
    cout << ans << "\n";
}


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

using namespace std; 
  int main()
  {
      int n;
      cin>>n;
      int a[n][3];
      int i;
      for(i=0;i<n;i++)
      {
          cin>>a[i][0]>>a[i][1]>>a[i][2];
      }
      long long int dp[3][n];
      dp[0][0]=a[0][0];
      dp[1][0]=a[0][1];
       dp[2][0]=a[0][2];
       //int i;
       for(i=1;i<n;i++)
       {
           dp[0][i]=max(dp[1][i-1],dp[2][i-1])+a[i][0];
           dp[1][i]=max(dp[0][i-1],dp[2][i-1])+a[i][1];
           dp[2][i]=max(dp[1][i-1],dp[0][i-1])+a[i][2];
       }
       cout<<max(dp[0][n-1],max(dp[1][n-1],dp[2][n-1]))<<endl;
     
      
      return 0;
  }

Measured memory_bytes: 3712
#include<bits/stdc++.h>
using namespace std;
struct Node{
  int key;
  Node *right,*left,*parent;
};
  Node *root=NULL,*NIL=NULL;//番兵（何もない）

Node *find(Node*u,int k){
  while(u!=NIL && u->key!=k){
    if(k<u->key){
      u=u->left;
    }else{
      u=u->right;
    }
  }
  return (u);
}

void insert(int k){
  Node *x_parent=NIL;//xの親
  Node *x=root;//挿入する場所・・・rootから始まる
  Node *node=NIL;//新たに挿入するノード
  node = (Node*)malloc(sizeof(Node));// 
  node->key=k;//    新たに
  node->right=NIL;//　　挿入するノードの
  node->left=NIL;//　　　　要素をセットする
  
  //挿入する位置を決める。
  while(x!=NIL){
    x_parent=x;
    if(node->key<x->key){//親より大きい
      x=x->left;//xを左に
    }else{//小さい
      x=x->right;//xを右に
    }
  }
  node->parent=x_parent;
  if(x_parent==NIL){
    root=node;//木が空の場合
  }else{
    if(node->key < x_parent->key){//親より大きい
      x_parent->left=node;//左にセット
    }else {//小さい
      x_parent->right=node;//右にセット
    }
  }
  return ;
}

void preorder(Node *u){
  if(u==NIL) return ;
  printf(" %d",u->key);
  preorder(u->left);
  preorder(u->right);
}

void inorder(Node *u){
  if(u==NIL) return;
  inorder(u->left);
  printf(" %d",u->key);
  inorder(u->right);
}

int main(){
  int n,i,x;
  string com;
  
  scanf("%d",&n);

  for(int i=0;i<n;i++){
    cin>>com;
    if(com=="insert"){
      cin>>x;
      insert(x);
    }
    else if(com=="find"){
      cin>>x;
      if(find(root,x)!=NIL) cout<<"yes"<<endl;
      else cout<<"no"<<endl;
    }
    else if(com=="print"){
      inorder(root);
      cout<<endl;
      preorder(root);
      cout<<endl;
    }
  }
  return 0;
}

Measured memory_bytes: 22008
from collections import deque, defaultdict

d = [[1, 0], [-1, 0], [0, 1], [0, -1]]

H, W, N = map(int, input().split())

G = []

sx = sy = 0
for i in range(H):
    G.append(input())
    for j, c in enumerate(G[i]):
        if c == 'S':
            sx, sy = i, j


Q = deque()
Q.append((sx, sy, 0))
visited = defaultdict(lambda: defaultdict(int))
visited[sx][sy] = 1

target = '1'

while len(Q):
    x, y, step = Q.popleft()
    if G[x][y] == target:
        visited.clear()
        Q.clear()
        target = str(int(target) + 1)
        if target == str(N + 1):
            print(step)
            break
    for dx, dy in d:
        nx, ny = x + dx, y + dy
        if 0 <= nx < H and 0 <= ny < W and G[nx][ny] != 'X':
            if not visited[nx][ny]:
                visited[nx][ny] = 1
                Q.append((nx, ny, step + 1))


Measured memory_bytes: 33656
def segfunc(x,y):
    return max(x,y)



ide_ele = -float('inf')


class SegTree:
    """
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """
    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        k: index(0-index)
        x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        l: index(0-index)
        r: index(0-index)
        """
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res
      
n,k=map(int,input().split())
a=[ int(input()) for _ in range(n)]
A=[0 for _ in range(303030)]
seg=SegTree(A,segfunc,ide_ele)
for x in a:
  seg.update(x,seg.query(max(0,x-k),min(303030,x+k+1))+1)
  
ans=seg.query(0,303030)
print(ans)

Measured memory_bytes: 130080
#include <stdio.h>
#define N 101

int P[N];
int M[N][N];

void MatricChainMultiplication(int p[],int n){
 int i,l,j,tmp,k;

 for(i=1;i<=n;i++){
  M[i][i]=0;
 }

 for(l=2;l<=n;l++){
  for(i=1;i<=n-l+1;i++){

      j=i+l-1;
      M[i][j] = 1000000000;

    for(k=i;k<=j-1;k++){

    tmp=M[i][k]+M[k+1][j]+P[i-1]*P[k]*P[j];

    if(M[i][j]>tmp){
    M[i][j]=tmp;

     }
    }
   }
 }
   printf("%d\n",M[1][n]);
}

int main(){

  int n,i,r,c;

  scanf("%d",&n);

  for(i=0;i<n;i++){

  scanf("%d %d",&r,&c);
   if(i==0){
    P[0]=r;
     P[1]=c;
   }
     else {
    P[i+1]=c;
    } 
   } 
    MatricChainMultiplication (P,n);
  return 0;
}

Measured memory_bytes: 636
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef long long ll;
int main() {
  ll n; cin>>n;
  vector<ll> a(n);
  rep(i, n) cin>>a.at(i);
  rep(i, n-1) {
    if(a.at(i)==1+a.at(i+1)) a.at(i+1)++;
  }
  bool ans=true;
  rep(i, n-1) {
    if(a.at(i)>a.at(i+1)) ans=false;
  }
  if(ans==true) cout << "Yes";
  else cout << "No";
}


Measured memory_bytes: 1024
#include <stdio.h>
#include <stdlib.h>
#define MAX 2000001
#define VMAX 10000

int main(){
    unsigned short *A, *B;
    
    int C[VMAX+1];
    int n, i, j;
    scanf("%d", &n);
    
    A = (unsigned short*)malloc(sizeof(short)* n+1);
    B = (unsigned short*)malloc(sizeof(short)* n+1);
    
    for(i=0; i<=VMAX; i++) C[i]=0;
    
    for(i=0; i<n; i++){
        scanf("%hu", &A[i+1]);
        C[A[i+1]]++;
    }
    
    for(i=1; i<=VMAX; i++) C[i] = C[i] + C[i-1];
    
    for(j=1; j<=n; j++){
        B[C[A[j]]] = A[j];
        C[A[j]]--;
    }
    
    for(i=1; i<=n; i++){
        if(i>1) printf(" ");
        printf("%d", B[i]);
    }
    printf("\n");
    
    return 0;
}


Measured memory_bytes: 10616
#include <iostream>
int main(){int n,c=0,l[100];std::cin>>n;bool f=0;for(int i=0;i<n;i++){std::cin>>l[i];i>0?l[i-1]==l[i]&&f==0?c++,f=1:f=0:0;}std::cout<<c<<"\n";}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static ll INF = 1e9;
const static ll MOD = 1e9+7;

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

    vector<vector<int>> ans(H, vector<int>(W));
    //int c = 1;
    int c = 1;
    queue<int> idx;
    for(int i = 0; i < H; i++){
        int snum = 0;
        for(int j = 0; j < W; j++){
            
            if(C[i][j] == '#') {
                snum++;
                if(snum > 1) c++;
            }
            ans[i][j] = c;
            
            
            //cout << ans[i][j] << " ";
            
        }
        if(snum != 0)c++;
        else idx.push(i);
        
        //cout << endl;
    }
    while(!idx.empty()){
        int x = idx.front(); idx.pop();
        int cnt = x;
        while(idx.front() == cnt+1) {
            cnt = idx.front();
            idx.pop();
        }
        if(cnt == H-1){
            cnt = cnt-x+1;
            for(int i = 0; i < cnt; i++){
                for(int j = 0; j < W; j++){
                    ans[x+i][j] = ans[x-1][j];
                }
            }

        }
        else{
            cnt = cnt-x+1;
            for(int i = 0; i < cnt; i++){
                for(int j = 0; j < W; j++){
                    ans[x+i][j] = ans[x+cnt][j];
                }
            }
        }
    }

    for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++) cout << ans[i][j] << " ";
        cout << endl;
    }
}

Measured memory_bytes: 1280
#include<bits/stdc++.h>
#define ll          long long int
#define lld          long double
#define pb          push_back
#define pii         pair<ll,ll>
#define mi          map<ll,ll>
#define vec         vector<ll>
#define all(a)     (a).begin(),(a).end()
#define F           first
#define S           second
#define mod         1000000007
#define rep(i,a,b)	for(ll  i=a;i<b;i++)
#define repi(i,a,b)	for(ll  i=a;i<=b;i++)
#define per(i,a,b)  for(ll i=a;i>=b;i--)
#define mp          make_pair
#define mit         map<ll,ll>::iterator
#define sit         set<ll>::iterator
#define pit         pair<ll,ll>::iterator
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;
ll xo(ll x, ll y) 
{ 
   return (x | y) & (~x | ~y); 
}  
ll bin_Expo(ll x,ll n)
{
		if(x==0)
		return 0;
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return bin_Expo(x*x,n/2);
    else                             //n is odd
        return x*bin_Expo(x*x,(n-1)/2);
}
ll mod_Expo(ll x,ll n,ll M)
{
		if(x==0)
		return 0;
    if(n==0)
        return 1;
    else if(n%2 == 0)        //n is even
        return mod_Expo((x*x)%M,n/2,M);
    else                             //n is odd
        return (x*mod_Expo((x*x)%M,(n-1)/2,M))%M;
 
}
ll NcR(int n, int r) 
{ 
    ll p = 1, k = 1; 
    if (n - r < r) 
        r = n - r; 
  
    if (r != 0) { 
        while (r) { 
            p *= n; 
            k *= r; 
            ll m=__gcd(p, k); 
            p /= m; 
            k /= m; 
            n--; 
            r--; 
        } 
    } 
    else
        p = 1; 
    return p;
}
bool prime_check(ll x)
{
    bool prime = (x >= 2);
    for (ll i = 2; i * i <= x; i++) 
    {
        if (x % i == 0) 
        {
            prime = false;
            break;
        }
    }
    return prime;
}
ll logg(ll base,ll x)
{
    return (ll)(log(x)/log(base));
}
bool vis[441];
ll n,m,P,Q,f,lev[441];
char s[441]; 
vec adj[441];
ll bfs(ll i)
{
	queue<ll> q;
	q.push(i);
	vis[i]=true;
	lev[i]=0;
	while(!q.empty())
	{
		P=q.front();
		q.pop();
		rep(j,0,adj[P].size())
		{
			Q=adj[P][j];
			if(!vis[Q])
			{
				lev[Q]=lev[P]+1;
				f=max(f,lev[Q]);
				q.push(Q);
				vis[Q]=true;
			}
		}
	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int TESTS=1;
//	cin>>TESTS;
    while(TESTS--)
    {
    	ll i,j,l,d,k,ac,J;
    	cin>>n>>m;
    	k=0; d=0;
    	rep(i,0,n*m)
    	{
    		cin>>s[i];
    		vis[i]=false;
    		lev[i]=0;
		}
		rep(i,0,n)
		{
			rep(j,0,m-1)
			{
				if(s[m*i+j]!='#' && s[m*i+j+1]!='#')
				{
					adj[m*i+j].pb(m*i+j+1);
					adj[m*i+j+1].pb(m*i+j);
				}
			}
		}
		rep(j,0,m)
		{
			rep(i,0,n-1)
			{
				if(s[m*i+j]!='#' && s[m*(i+1)+j]!='#')
				{
					adj[m*i+j].pb(m*(i+1)+j);
					adj[m*(i+1)+j].pb(m*i+j);
				}
			}
		}
		f=0;
		rep(i,0,n*m)
		{
			if(s[i]!='#')
			bfs(i);
			rep(j,0,n*m)
			{
				vis[j]=false;
				lev[j]=0;
			}
		}
    	cout<<f;
    }
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
using lli = long long;
#define rep(i,n) for(int i=0;i<n;i++)
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; }

lli n;

lli posmod(lli x, lli mod){
    if(x >= 0) return x%mod;
    else return (x+mod)%mod;
}

int main(void){
    cin >> n;
    vector<lli> x(n), y(n);
    rep(i, n) cin >> x[i] >> y[i];
    lli ans = n;
    rep(i, n){
        rep(j, n){
            if(j == i) continue;
            lli p = x[i]-x[j];
            lli q = y[i]-y[j];
            lli s = 0;
            rep(u, n){
                rep(v, n){
                    lli dx = x[u]-x[v];
                    lli dy = y[u]-y[v];
                    if(dx == p && dy == q) s++;
                }
            }
            ans = min(ans, n-s);
        }
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3620
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int H = sc.nextInt();
    int W = sc.nextInt();
    int N = sc.nextInt();
    sc.close();
    
    int max = Math.max(H, W);
    
    int ans = (N + max - 1) / max;
    System.out.println(ans);    
  }
}

Measured memory_bytes: 22868
#include<bits/stdc++.h>
using namespace std;
string a,b;
int main()
{
    cin>>a;
    cin>>b;
    int la=a.size(),lb=b.size();
    int l=min(la,lb),ll=max(la,lb);
    for(int i=0;i<=l-1;i++)
        cout<<a[i]<<b[i];
    if(la>lb)
        for(int i=l;i<=ll-1;i++)
            cout<<a[i];
    else 
        for(int i=l;i<=ll-1;i++)
            cout<<b[i];
    return 0;
}

Measured memory_bytes: 256