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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> P;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for (ll i=(a);i<(b);i++)
#define RFOR(i,a,b) for (ll i=(b)-1;i>=(a);i--)
#define REP(i,n) for (ll i=0;i<(n);i++)
#define RREP(i,n) for (ll i=(n)-1;i>=0;i--)
#define debug(x) cout<<#x<<": "<<x<<endl
#define pb push_back
#define ALL(a) (a).begin(),(a).end()

const ll linf = 1e18;
const int inf = 1e9;
const double eps = 1e-12;
const double pi = acos(-1);

template<typename T>
istream& operator>>(istream& is, vector<T>& vec) {
	EACH(x,vec) is >> x;
	return is;
}
template<typename T>
ostream& operator<<(ostream& os, vector<T>& vec) {
	REP(i,vec.size()) {
		if (i) os << " ";
		os << vec[i];
	}
	return os;
}
template<typename T>
ostream& operator<<(ostream& os, vector< vector<T> >& vec) {
	REP(i,vec.size()) {
		if (i) os << endl;
		os << vec[i];
	}
	return os;
}

int main() {
//	std::ios::sync_with_stdio(false);
//	std::cin.tie(0);
	int w; cin >> w;
	vector<int> v(w); REP(i, w) v[i] = i+1;
	int n; cin >> n;
	REP(i, n) {
		int a, b;
		scanf("%d,%d", &a, &b); --a, --b;
		swap(v[a], v[b]);
	}
	REP(i, w) {
		cout << v[i] << endl;
	}
}

Measured memory_bytes: 3128
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for(int i=int(a); i<int(b); ++i)
#define FORD(i,a,b) for(int i=int(a); i<int(b); --i)
#define REP(i,N) for(int i=0; i<int(N); ++i)
#define REPD(i,N) for(int i=0; i<int(N); --i)
#define PB push_back
#define ALL(obj) (obj).begin(), (obj).end()
#define INF 1000000000000 //10^12:∞
#define MOD 1000000007 //10^9+7
#define MAXR 100000 //配列の最大のrenge

int main() {
    string S;cin>>S;
    int a,b,c,d;
    a = S[0]-48;
    b = S[1]-48;
    c = S[2]-48;
    d = S[3]-48;
    int ope[2] = {-1,1};

    bool finish=false;
    REP(i,2){REP(j,2){REP(k,2) {
        int tmp = a + b*ope[i] + c*ope[j] + d*ope[k];
        if (tmp == 7) {
            //cout<<tmp<<i<<j<<k;
            char sa = (i==0 ? '-' : '+');
            char sb = (j==0 ? '-' : '+');
            char sc = (k==0 ? '-' : '+');
            printf("%d%c%d%c%d%c%d=7",a,sa,b,sb,c,sc,d);
            finish=true;
        }
        if(finish) break;
    }
    if(finish) break;
    }
    if(finish) break;
    }
}

Measured memory_bytes: 3716
#[allow(unused_imports)]
use std::cmp::*;
#[allow(unused_imports)]
use std::collections::*;
use std::io::{Write, BufWriter};
// https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, [ $t:tt ]) => {{
        let len = read_value!($next, usize);
        (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    }};

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused)]
macro_rules! debug {
    ($($format:tt)*) => (write!(std::io::stderr(), $($format)*).unwrap());
}
#[allow(unused)]
macro_rules! debugln {
    ($($format:tt)*) => (writeln!(std::io::stderr(), $($format)*).unwrap());
}

fn solve() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }
    input!(n: i64);
    puts!("{}\n", n * (n - 1) / 2);
}

fn main() {
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(|| solve()).unwrap().join().unwrap();
}


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

int main()
{
    ll x,y,z;
    cin>>x;
    y=x/500;
    z=x-(y*500);
    z=z/5;
    cout<<(y*1000)+(z*5)<<endl;
}


Measured memory_bytes: 256
# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define AU(i,x)    for(auto i=x.begin(); i!=x.end(); ++i)
# define ALL(A) A.begin(),A.end()
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline char nc(){
    static char buf[1000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;
}
inline int Scan(){
    char ch=nc();int sum=0, f=1;
    if (ch=='-') f=-1, ch=nc();
    while(!(ch>='0'&&ch<='9'))ch=nc();
    while(ch>='0'&&ch<='9')sum=sum*10+ch-48,ch=nc();
    return sum*f;
}
int ps4[4][2]={0,1,0,-1,1,0,-1,0};
int ps8[8][2]={0,1,0,-1,1,0,-1,0,1,1,1,-1,-1,-1,-1,1};
inline int min(int a,int b,int c) {return min(a,min(b,c));}
inline int max(int a,int b,int c) {return max(a,max(b,c));}
inline int min(int a,int b,int c,int d){return min(min(a,b,c),d);}
inline int max(int a,int b,int c,int d){return max(max(a,b,c),d);}
//struct Edge{int p, next, w;}edge[maxn];
//inline add_edge(int u, int v, int w){edge[cnt]=Edge{v,head[u],w}; head[u]=cnt++;}
const int N=205;
///Code begin..................................................................

int t[N], v[N];
double dp[2][205];

int main ()
{
    int n;
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",t+i), t[i]*=2, t[i]+=t[i-1];
    FOR(i,1,n) scanf("%d",v+i), v[i]*=2;
    int flag=0;
    FOR(i,1,202) dp[0][i]=-1; dp[0][0]=0;
    FOR(i,1,n) {
        FOR(j,t[i-1]+1,t[i]-1) {
            flag^=1;
            FOR(k,0,202) dp[flag][k]=-1;
            FOR(k,0,v[i]) {
                if (k>0&&dp[flag^1][k-1]>-0.5) dp[flag][k]=max(dp[flag][k],dp[flag^1][k-1]+k-0.5);
                if (dp[flag^1][k+1]>-0.5) dp[flag][k]=max(dp[flag][k],dp[flag^1][k+1]+k+0.5);
                if (dp[flag^1][k]>-0.5) dp[flag][k]=max(dp[flag][k],dp[flag^1][k]+k);
            }
        }
        flag^=1;
        FOR(k,0,202) dp[flag][k]=-1;
        FOR(k,0,min(v[i],v[i+1])) {
            if (k>0&&dp[flag^1][k-1]>-0.5) dp[flag][k]=max(dp[flag][k],dp[flag^1][k-1]+k-0.5);
            if (dp[flag^1][k+1]>-0.5) dp[flag][k]=max(dp[flag][k],dp[flag^1][k+1]+k+0.5);
            if (dp[flag^1][k]>-0.5) dp[flag][k]=max(dp[flag][k],dp[flag^1][k]+k);
        }
    }
    printf("%.8f\n",dp[flag][0]/4.0);
    return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <stack>
#include <set>
#include <map>
typedef long long ll;
using namespace std;

int main(){
  int M, D;
  cin >> M >> D;

  int ans = 0;
  for(int i = 1; i <= M; i++){
    for(int j = 1; j <= D; j++){
      int iti = j % 10;
      int jyu = j / 10;

      if(iti >= 2 && jyu >= 2 && iti * jyu == i) ans++;
    }
  }

  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <cmath>
#include <queue>
#include <stack>

#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
typedef long long ll;

using namespace std;

int inputValue(){
    int a;
    cin >> a;
    return a;
};

template<typename T>
void inputArray(T* p, int a){
    rep(i, a){
        cin >> p[i];
    }
};

template<typename T>
void inputVector(vector<T> * p, int a){
    rep(i, a){
        T input;
        cin >> input;
        p -> push_back(input);
    }
}

template <typename T>
void output(T a, int precision = 0) {
    if(precision > 0){
        cout << setprecision(precision)  << a << "\n";
    }
    else{
        cout << a << "\n";
    }
}

#define Max 3
int a[Max];
int b[Max];

int main(int argc, const char * argv[]) {
    rep(i, 3) {
        a[i] = inputValue();
        b[i] = inputValue();
    }

    rep(i, 3) {
        rep(j, 3) {
            if (i == j) continue;
            if (a[i] != a[j] && a[i] != b[j] && b[i] != a[j] && b[i] != b[j]) continue;
            int first = 0;
            int second = 0;
            int third = 0;
            if (a[i] == a[j] || a[i] == b[j]) { 
                first = b[i];
                second = a[i];
                if (a[i] == a[j]) third = b[j];
                else third = a[j];
            }
            else {
                first = a[i];
                second = b[i];
                if (b[i] == a[j]) third = b[j];
                else third = a[j];
            }
            if (third == first) {
                continue;
            }
            rep(k, 3) {
                if (k == j || k == i) continue;
                if (a[k] != third && b[k] != third) continue;
                int forth = 0;
                if (a[k] == third) { 
                    forth = b[k];
                }
                else {
                    forth = a[k];
                }
                if (forth != first && forth != second) {
                    //printf("%d,%d,%d,%d", first,second,third,forth);
                    output("YES");
                    return 0;
                }
            }
        }
    }

    output("NO");
    return 0;
}

Measured memory_bytes: 888
n = int(input())
v = list(map(int, input().split()))
v.sort(reverse=True)
count = 0
for i in range(n):
  if i == n-1:
    count += v[i] / 2**(n-1)
  else:
    count += v[i] / 2**(i+1)
print(count)

Measured memory_bytes: 38384
// DFS
import java.util.*;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] graph = new int[n][n];
		int[][] arr = new int[n][2];
		Stack<Integer> s = new Stack<Integer>();
		
		for(int i=1;i<=n;i++){
			int u = sc.nextInt();
			int k = sc.nextInt();
			for(int j=1;j<=k;j++){
				int index = sc.nextInt();
				graph[u-1][index-1]=1;
			}
		}
		
		int count=n;
		int index=1;
		while(count>0){
			
			for(int i=0;i<n;i++){
				if(arr[i][0]==0){
					s.push(i+1);
					arr[i][0]=index;
					index++;
					count--;
					break;
				}
			}
			
			while(s.size()>0){
				int num = s.peek();
				boolean val = false;
				for(int i=0;i<n;i++){
					if(graph[num-1][i]==1 && arr[i][0]==0){
						s.push(i+1);
						arr[i][0]=index;
						index++;
						count--;
						val = true;
						break;
					}
				}
				if(!val){
					int number = s.pop();
					arr[number-1][1] = index;
					index++;
				}
			}
		}
		
		for(int i=0;i<n;i++){
			System.out.println((i+1)+" "+arr[i][0]+" "+arr[i][1]);
		}
	}
}


Measured memory_bytes: 28156
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,n) for(ll i = 0;i<((ll)(n));i++)
#define reg(i,a,b) for(ll i = ((ll)(a));i<=((ll)(b));i++)
#define irep(i,n) for(ll i = ((ll)(n)-1);i>=0;i--)
#define ireg(i,a,b) for(ll i = ((ll)(b));i>=((ll)(a));i--)
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T = int> void print(vector<T> v){for(auto a:v)cout<<a<<" ";cout<<endl;}

/*
*/

ll h,w;

int main(void){
	cin>>h>>w;
	if(h==1 || w==1){
		cout<<1<<endl;
		return 0;
	}
	if(h*w%2 == 0){
		cout<<h*w/2<<endl;
	}else{
		cout<<(h*w+1)/2<<endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include "bits/stdc++.h"
#include "math.h"
 
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<int> vin;
typedef pair<ll,ll> P;
typedef vector<P> vp;
#define rep(i,a,b) for(ll i=(a);i<(b);++i)
#define drep(i,a,b) for(ll i=(a);i>=(b);--i)
#define SIZE(a) int((a).size())
#define out(a) cout<<(a)<<endl;
const int INF=INT_MAX;
const int MAX = 510000;
const ll MOD = 1L<<32;
ll fac[MAX], finv[MAX], inv[MAX];

int main(){
  ll x,y;cin>>y>>x;
  bool ok=true;
  if(x%2){ok=false;}
  else{
    if(x<2*y||x>4*y){ok=false;} 
  }
  cout<<(ok?"Yes":"No")<<endl;
  
}




Measured memory_bytes: 3628
A = int(input())
B = int(input())
C = int(input())
X = int(input())
ans = 0
for i in range(A+1):
    for j in range(B+1):
        for k in range(C+1):
            if 500*i + 100*j + 50*k == X:
                ans += 1
print(ans)


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

int max(int a,int b){
  if(a>b) return a;
  else return b;
}
int absolute(int a,int b){
  if(a-b<0) return -(a-b);
  else return a-b;
}
void Yes(){
  cout << "Yes" << endl;
}
void YES(){
  cout << "YES" << endl;
}
void No(){
  cout << "No" << endl;
}
void NO(){
  cout << "NO" << endl;
}
int main(){
  int i,j,count;
  int N,Q;
  cin >> N >> Q;
  string s;
  cin >> s;
  vector<int> l(Q);
  vector<int> r(Q);
  vector<int> t(N);
  
  for(i=0;i<Q;i++){
  	cin >> l.at(i) >> r.at(i);
  }
  
  for(i=0;i<N-1;i++){
    t.at(i+1) = t.at(i);
  	if(s.at(i) == 'A' && s.at(i+1) == 'C'){
      t.at(i+1)++;
    }
  }
  

  for(i=0;i<Q;i++){
  	cout << t.at(r.at(i)-1) - t.at(l.at(i)-1) << endl;
  }
}

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

// nPnの順列に対して処理を実行する//
//  https://kamino.hatenablog.com/entry/cpp-permutation-combination
void foreach_permutation(int n, std::function<void(int *)> f) {
  int indexes[n];
  for (int i = 0; i < n; i++) indexes[i] = i;
  do {
    f(indexes);
  } while (std::next_permutation(indexes, indexes + n));
}

ll Fact(int n)//n階乗を求める関数 オーバーフローするのでnが小さい値しか使えないよ
{
  if(n==0) return 1;
  return n * Fact(n-1);
}

double get_distance(int x1, int y1, int x2, int y2)//2点間の距離を求める関数
{
  double distance;
  distance = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2);
  return sqrt(distance);
}

int main() {
  int N;
  cin >> N;
  vector<int> x(N), y(N);
  for(int i = 0; i<N; i++) 
  {
    cin >> x.at(i);
    cin >> y.at(i);
  }
  double ans = 0;
  
  //解1↓↓
  ll n_fact = Fact(N);
  //cout << "Fact("<<N<<") : "<< n_fact << endl;
  foreach_permutation(N, [&](int *indexes)
                      {//&をつけとくと外の変数をラムダ式の中で使えるらしい
    //std::cout << indexes[0] << ',' << indexes[1] << ',' << indexes[2] << std::endl;
    //なんかよくわからんが，foreach_permutationでぐるぐるまわってるのか，n階乗回回っているからこのforいらない
    //for(ll i=0; i<n_fact; i++)
    //{
                        for(int j=0; j<N-1; j++)
                        {
                          ans += get_distance(
                            x.at(indexes[j]), y.at(indexes[j]), x.at(indexes[j+1]), y.at(indexes[j+1]));
                        }
    //}
                      });
  ans /= n_fact;
  cout << fixed;//小数点を確実に8桁で表示するためのもの
  cout << setprecision(8) <<ans << endl; 
  //解1↑↑

  /*解2↓↓
  for(ll i=0; i<N; i++)//各町間の道路の長さを2回ずつ足す
  {
    for(ll j=0; j<N; j++){
      if(i==j) continue;
      ans += get_distance(x.at(i), y.at(i), x.at(j), y.at(j));
    }    
  }

  ans = ans / N;
  cout << fixed;//小数点を確実に8桁で表示するためのもの
  cout << setprecision(8) <<ans << endl; 
  *///解2↑↑
}


Measured memory_bytes: 256
def main():
    mod=998244353
    n,k=map(int,input().split())
    region=[]
    for _ in range(k):
        a,b=map(int,input().split())
        region.append((a,b))

    #dp[i]はマスiに行く方法の個数
    #workにdp[i-1]からの増減分を保持
    dp=[0]*(n+1)
    work=[0]*(n+1)

    #initialize
    for j in region:
        if 1+j[0]<=n:
            work[1+j[0]]+=1
        if 1+j[1]+1<=n:
            work[1+j[1]+1]-=1    

    for i in range(2,n+1):
        dp[i]=dp[i-1]+work[i]
        dp[i]%=mod
        for j in region:
            if i+j[0]<=n:
                work[i+j[0]]+=dp[i]
                work[i+j[0]]%=mod
            if i+j[1]+1<=n:
                work[i+j[1]+1]-=dp[i]
                work[i+j[1]+1]%=mod
    print(dp[n])


main()

Measured memory_bytes: 24592
#pragma GCC optimize (3)
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<algorithm>
#include<unordered_map>
/*#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<ext/pb_ds/trie_policy.hpp>
#include<ext/pb_ds/priority_queue.hpp>*/
//#include<ext/rope>
#define ll long long
#define ull unsigned long long
#define INFI 2147483647
#define INFL 9223372036854775807
#define INFU 18446744073709551615
#define maxn 100005
using namespace std;
//using namespace __gnu_pbds;
//using namespace __gnu_cxx;
const double PI=acos(-1.0);
const double eps=1e-6;
int a[maxn];
multiset<int> s;
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
signed main()
{
    //ios_base::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    int n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++){
        if(s.empty()) s.insert(a[i]);
        else{
            auto it=s.lower_bound(a[i]);
            if(it==s.begin()) s.insert(a[i]);
            else if(it==s.end()){
                it--;
                s.erase(it);
                s.insert(a[i]);
            }
            else{
                it--;
                s.erase(it);
                s.insert(a[i]);
            }
        }
    }
    cout<<s.size()<<endl;
    return 0;
}


Measured memory_bytes: 8660
#include<bits/stdc++.h>
#include<iomanip>
#include <numeric>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=n-1;i>=0;--i)
#define yesno(flg) if(flg){cout<<"YES"<<endl;}else{cout<<"NO"<<endl;}
#define MAX_N 1002
#define i197 1000000007
#define KETA 40

using namespace std;

typedef long long  ll;
typedef pair<ll,ll> P1;
typedef pair<string,int> Pi;
typedef pair<double,Pi> Pdi;
typedef pair<ll,int>Pli;
typedef pair<Pi,int> P2;
const ll INF=1000000000000000001;
struct edge{int to,cost;};
int dy[]={0, 0, 1, -1};
int dx[]={1, -1, 0, 0};
struct Road{double cost;int a,b;};

int main() {

	string s;
	cin>>s;

	if(s[0]==s[s.size()-1]&&s.size()%2==0)cout<<"First"<<endl;
	else if(s[0]!=s[s.size()-1]&&s.size()%2>0)cout<<"First"<<endl;
	else cout<<"Second"<<endl;
	return 0;

}


Measured memory_bytes: 512
/*
    author: kartik8800
*/
#include<bits/stdc++.h>
#define ll long long
#define pb push_back
#define fr(a,b) for(ll i = a; i < b; i++)
#define mod 1000000007
#define inf (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define prDouble(x) cout << fixed << setprecision(10) << x 
#define triplet pair<ll,pair<ll,ll>>
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL)
using namespace std;
 
int solve(vector<int>& v, int n, int k)
{
    ll dp[n+2][k+2];

    for(int j = 0; j <= k; j++)
        dp[1][j] = (j > v[1]) ? 0 : 1;
    
    for(int i = 2; i <= n; i ++)
    {
        for(int j = 0; j <= k; j++)
        {
            if(j == 0)
                dp[i][j] = dp[i-1][j];
            else dp[i][j] = (mod + dp[i][j-1] + dp[i-1][j] - ((j-v[i]-1 >= 0) ? dp[i-1][j-v[i]-1] : 0)) % mod;
        }
    }
    return dp[n][k];
}
 
int main() {
   int n, k;
   cin >> n >>k;
   vector<int> v(n+1);
   for(int i = 1; i <= n; i++)
        cin >> v[i];
   cout << solve(v, n, k);
   return 0;
}


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

int n, m, q;
vector<int> a, b, c, d;
int ans = 0;

void dfs(vector<int> A){
  if(A.size() == n+1){
    int now = 0;
    rep(i,q){
      if(A[b[i]] - A[a[i]] == c[i]) now+= d[i];
    }
    ans = max(ans, now);
    return;
  }
  A.push_back(A.back());
  while(A.back() <= m){
    dfs(A);
    A.back()++;
  }
}

int main() {
  cin >> n >> m >> q;
  a = b = c = d = vector<int>(q);
  rep(i,q){
    cin >> a[i] >> b[i] >> c[i] >> d[i];
  }
  dfs(vector<int>(1, 1));
  cout << ans << endl;
}

Measured memory_bytes: 3596
#include <stdio.h>

int main(){
   int n,a,b,c,d;
   char s[200001];
    
   scanf("%d %d %d %d %d",&n,&a,&b,&c,&d);
   scanf("%s",&s[1]);
   if (d>c) {
      while (b!=d && s[b]!='#')
         if (s[b+1]=='.') b++;
         else             b+=2;
      if (s[b]=='#') {
         puts("No");
         return 0;
      }
      while (a!=c && s[a]!='#')
         if (s[a+1]=='.') a++;
         else             a+=2;
      if (s[a]=='#') puts("No");
      else           puts("Yes");
      return 0;
   }
   while (b!=d && s[b]!='#' && (s[b+1]!='.' || s[b-1]!='.')) 
       if (s[b+1]=='#') b+=2;
       else             b++;
   if ((b==d && s[b+1]=='#') || s[b]=='#') {
      puts("No");
      return 0;
   }
   s[b]='#';
   while (a!=c && s[a]!='#')
      if (s[a+1]=='.') a++;
      else             a+=2;
   if (s[a]=='#') {
      puts("No");
      return 0;
   }
   s[b]='.';
   while (b!=d && s[b]!='#')
      if (s[b+1]=='.') b++;
      else             b+=2;
   if (s[b]=='#') puts("No");
   else           puts("Yes");
   return 0;
}


Measured memory_bytes: 384
//ABC098A
#include <bits/stdc++.h>
#include <iostream>
#include <iomanip>
#include <numeric>
#include <math.h>
#include <stdio.h>
#include <climits>
#include <cfloat>
#include <string>
using namespace std;

int main(){
	int a, b;
	cin >> a >> b;
	int ans = max({a+b,a-b,a*b});
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stdio.h>
#include <string>
#include <vector>
using namespace std;
#define int long long
int MOD = 1000000007;
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int N;
  cin >> N;

  int ans;
  ans = N * N * N;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int a = input.nextInt();
        int b = input.nextInt();
        int c = input.nextInt();
        int d = input.nextInt();

        if (Math.abs(c - a) <= d ||  (Math.abs(a-b) <=d && Math.abs(b-c) <= d))
            System.out.println("Yes");
        else
            System.out.println("No");
    }
}


Measured memory_bytes: 21844
m,d = gets.split.map(&:to_i)
ans = 0
(2..m).each do |i|
    (22..d).each do |j|
        next if j%10 < 2
        if i == j.to_s.split("").map(&:to_i).inject(:*)
            ans += 1
        end
    end
end
puts ans

Measured memory_bytes: 2044
N=int(input())
I=[int(input()) for i in range(N)]
r=max(I)
if I.count(r)>=2:
	for j in range(N):
		print(r)
else:
	for k in range(N):
		X=int(I[k])
		if X!=r:
			print(r)
		else:
			I.remove(I[k])
			print(max(I))
			I.insert(k,X)

Measured memory_bytes: 12524
cnt = 0
SENTINEL = 2000000000

def merge(arr, length, left, mid, right):
#  n1 = mid - left
#  n2 = right - mid

    L = arr[left : mid]
    R = arr[mid : right]

    L.append(SENTINEL)
    R.append(SENTINEL)

    i, j = 0, 0
    for k in range(left, right):
        global cnt
        cnt += 1
        if (L[i] <= R[j]):
            arr[k] = L[i]
            i += 1
        else:
            arr[k] = R[j]
            j += 1

def merge_sort(arr, length, left, right):
    if (left + 1 < right):
        mid = (left + right)//2
        merge_sort(arr, length, left, mid)
        merge_sort(arr, length, mid, right)
        merge(arr, n, left, mid, right)    

if __name__ == '__main__':
    n = int(input())
    S = list(map(int, input().split()))

    merge_sort(S, n, 0, n)
    print(' '.join(map(str, S)))
    print(cnt)



Measured memory_bytes: 66580
n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for i in range(q)]

ans = [0] * n
for i in range(n - 1):
    if s[i] == "A" and s[i + 1] == "C":
        ans[i + 1] = ans[i] + 1
    else:
        ans[i + 1] = ans[i]

for i in lr:
    print(ans[i[1]-1]-ans[i[0]-1])


Measured memory_bytes: 68568
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); ++i)
template<class T> inline bool chmin(T& a, T b) {if (a > b) {a = b;return true;}return false;}
template<class T> inline bool chmax(T& a, T b) {if (a < b) {a = b;return true;}return false;}
using namespace std;
using ll = long long;
using P = pair<int,int>;
using Pl = pair<long long,long long>;
using veci = vector<int>;
using vecl = vector<long long>;
using vecveci = vector<vector<int>>;
using vecvecl = vector<vector<long long>>;

int main() {
    int N; cin >> N;
    string S; cin >> S;
    veci cumW(N+1),cumB(N+1);
    REP(i,N) {
        if(S[i] == '#') {
            cumB[i+1] = cumB[i] + 1;
            cumW[i+1] = cumW[i];
        } 
        else {
            cumW[i+1] = cumW[i]+1;
            cumB[i+1] = cumB[i];
        } 
    }
    int ans = 1e9;
    for(int i = 0; i <= N; i++) {
        //cout << cumB[i]+cumW[N]-cumW[i] << endl;
        chmin(ans,cumB[i]+cumW[N]-cumW[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 5240
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, a, b) for (int i = a; i < (int)b; i++)
#define all(v) v.begin(), v.end()
const int MOD = 1e9 + 7;
const int INF = 1e9;
//'A' = 65, 'Z' = 90, 'a' = 97, 'z' = 122

int main() {
    ll n;
    cin >> n;
    if (n % 2) {
        cout << 0 << endl;
        return 0;
    }
    n /= 2;
    ll ans = 0;
    while (n) {
        ans += n / 5;
        n /= 5;
    }
    cout << ans << endl;
    return 0;
}


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

using namespace std;
using ll=long long;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    for (auto& x: a) cin >> x;
    vector<ll> l(n+2), r(n+2);
    for (int i = n; i >= 0; i--) {
        l[i] = a[i] + (l[i+1]+1)/2;
        r[i] = a[i] + r[i+1];
        if(i < 60) r[i] = min(r[i], 1ll<<i);
        if (l[i] > r[i]) {
            cout << -1; return;
        }
    }
    ll res = 0;
    for (int i = 0; i <= n; i++) {
        res += r[i];
        r[i+1] = min(r[i+1], (r[i]-a[i])*2ll);
    }
    cout << res;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 5276
/*
 ALLAH is Almighty....
*/
#include <bits/stdc++.h>

#define ll  long long
using namespace std;

const ll mx = 1e9 + 7;
ll n, m;
string st1, st2, st;
ll dp[ 1005 ];
char given[ 1000 ][ 1000 ];

void solve( )
{
    cin >> n >> m;

    for ( ll i = 0; i < n; ++i )
        for ( ll j = 0; j < m; ++j )
            cin >> given[ i ][ j ];

    dp[ 0 ] = given[ 0 ][ 0 ] == '.';
    for ( ll i = 1; i < n; ++i ) {
        dp[ i ] = ( given[ i ][ 0 ] == '.' && dp[ i - 1 ] );
    }

    for ( ll i = 1; i < m; ++i )
        for ( ll j = 0; j < n; ++j ) {
            if ( given[ j ][ i ] == '#')
                dp[ j ] = 0;
            else if ( j )
                dp[ j ] = dp[ j ] + dp[ j - 1 ];

            dp[ j ] %= mx;
        }

    cout << dp[ n - 1 ] << endl;;
}

int main()         // Md. Inzamam-ul Haque
{
    solve();
}


Measured memory_bytes: 4544
n, m = input().split()

p = set()
q = set()
for _ in range(int(m)):
    a, b = input().split()
    if a == "1":
        p.add(b)
    elif b == n:
        q.add(a)
else:
    if p & q:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")

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

int main() {
	string s;
	cin>>s;
	long long sum=0;
	for(char i:s)
		sum+= i-'0';
	if(sum%9==0)
	cout<<"Yes";
	else
	cout<<"No";
	return 0;
}

Measured memory_bytes: 3724
#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <stdlib.h>
#include <string.h>
#include <cstring>
#include <cmath>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <stdio.h>
#include <tuple>
#include <bitset>
#include <cfloat>
#include <fstream>
#include <limits.h>
#include <list>
#include <math.h>
#include <random>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <numeric>
#include <utility>
#include <sstream>

template<class T> inline bool chmin(T& a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<class T> inline bool chmax(T& a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}

using namespace std;
#define int long long
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repr(i,n) for(ll i=n;i>=0;i--)
#define P pair<ll, ll>
#define sz(x) (ll)x.size()
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define VE vector<ll>
#define COUT(x) cout<<(x)<<endl
#define MA map<ll,ll>
#define SE set<ll>
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,VE,greater<ll>>
#define COUT(x) cout<<(x)<<endl
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define EPS (1e-10)
ll gcd(ll a, ll b) {
	if (a < b)swap(a, b);
	if (b == 0) return a;
	return gcd(b, a % b);
}
ll lcm(ll a, ll b) {
	ll g = gcd(a, b);
	return a / g * b;
}
bool prime(ll n) {
	for (ll i = 2; i <= sqrt(n); i++) {
		if (n%i == 0)return false;
	}
	return n != 1;
}


const long long MOD = 1000000007;
const long long INF = 1LL << 60;


const int MAX_N = 100010;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	string s, t; cin >> s >> t;
	cout << t << s << endl;
	return 0;
}

Measured memory_bytes: 256
N = int(input())
S = input()

s1 = set()  # 一桁の文字集合
s2 = set()  # 二桁の文字集合
s3 = set()  # 三桁の文字集合

# 30,000 * 100
for c in S:
  for c2 in s2:
    s3.add(c2 + c)
  for c1 in s1:
    s2.add(c1 + c)
  s1.add(c)
  
print(len(s3))  

Measured memory_bytes: 41964
fn main() {
    let (r, w) = (std::io::stdin(), std::io::stdout());
    let mut sc = IO::new(r.lock(), w.lock());
    let n: usize = sc.read();
    let ans = (n + 1) / 2;
    println!("{}", ans);
}

pub struct IO<R, W: std::io::Write>(R, std::io::BufWriter<W>);

impl<R: std::io::Read, W: std::io::Write> IO<R, W> {
    pub fn new(r: R, w: W) -> IO<R, W> {
        IO(r, std::io::BufWriter::new(w))
    }
    pub fn write<S: std::ops::Deref<Target = str>>(&mut self, s: S) {
        use std::io::Write;
        self.1.write(s.as_bytes()).unwrap();
    }
    pub fn read<T: std::str::FromStr>(&mut self) -> T {
        use std::io::Read;
        let buf = self
            .0
            .by_ref()
            .bytes()
            .map(|b| b.unwrap())
            .skip_while(|&b| b == b' ' || b == b'\n' || b == b'\r' || b == b'\t')
            .take_while(|&b| b != b' ' && b != b'\n' && b != b'\r' && b != b'\t')
            .collect::<Vec<_>>();
        unsafe { std::str::from_utf8_unchecked(&buf) }
            .parse()
            .ok()
            .expect("Parse error.")
    }
    pub fn vec<T: std::str::FromStr>(&mut self, n: usize) -> Vec<T> {
        (0..n).map(|_| self.read()).collect()
    }
    pub fn chars(&mut self) -> Vec<char> {
        self.read::<String>().chars().collect()
    }
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < (n); i++)
#define RREP(i, n) for (int i = (n); i >= 0; i--)
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define ALL(obj) begin(obj), end(obj)
using namespace std;
using ll = long long;
using ull = unsigned long long;

const int INF = 2100100100;
const int MOD = 1e9 + 7;

int main(){
  int n;
  cin >> n;
  cout << n*n*n << endl;
  return 0;
  
}

Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <cstring>
#include <numeric>
#include <algorithm>
#include <functional>
#include <array>
#include <map>
#include <queue>
#include <limits.h>
#include <set>
#include <stack>
#include <random>
#define rep(i,s,n) for(int i = (s); (n) > i; i++)
#define REP(i,n) rep(i,0,n)
#define RANGE(x,a,b) ((a) <= (x) && (x) <= (b))
#define POWT(x) ((x)*(x))
#define ALL(x) (x).begin(), (x).end()
#define MOD 1000000007
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;

int main() {
	char str [101];
	scanf("%s", str);
	bool c = 0, f = 0;
	REP(i, strlen(str)) {
		if (str[i] == 'C') c = 1;
		if (c && str[i] == 'F') f = 1;
	}
	printf("%s\n", c&&f ? "Yes\n" : "No\n");
	return 0;
}


Measured memory_bytes: 256
n,m = map(int,input().split())
ls = [list(map(int,input().split())) for _ in range(n)]
di = [list(map(int,input().split())) for _ in range(m)]
mn = [float("inf")]*n
num = [0]*n
for i in range(n):
    for j in range(m):
        k = abs(ls[i][0]-di[j][0]) + abs(ls[i][1]-di[j][1])
        if k < mn[i]:
            mn[i] = k
            num[i] = j+1
for p in range(n):
    print(num[p])


Measured memory_bytes: 3064
from sys import stdin
input = stdin.buffer.readline

def main():
    h, w = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(h)]

    def next_index(x, y):
        if y % 2 == 0:
            if x == w - 1:
                return x, y + 1
            else:
                return x + 1, y
        else:
            if x == 0:
                return x, y + 1
            else:
                return x - 1, y

    ans = []
    x = 0; y = 0
    while True:
        next_x, next_y = next_index(x, y)

        if next_y == h:
            break

        if a[y][x] % 2 == 1:
            ans.append((y+1, x+1, next_y+1, next_x+1))
            a[next_y][next_x] += 1
        x = next_x; y = next_y

    print(len(ans))
    for i in ans:
        print(' '.join(map(str, i)))

main()

Measured memory_bytes: 97604
#include <bits/stdc++.h>
template<class T> inline bool chmin(T&a, T b){if(a > b){a = b; return true;}else{return false;}}
template<class T> inline bool chmax(T&a, T b){if(a < b){a = b; return true;}else{return false;}}
#define ll long long
#define double long double
#define rep(i,n) for(int i=0;i<(n);i++)
#define REP(i,n) for(int i=1;i<=(n);i++)
#define mod (ll)(1e9+7)
#define inf (ll)(3e18+7)
#define pi (double) acos(-1.0)
#define P pair<int,int>
#define PiP pair<int,pair<int,int>>
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
using namespace std;

int d, score;
vector<int> c(26);
vector<vector<int>> s(400, vector<int>(26)), pos(26);

int get_score(vector<int> t){
    vector<int> pos(26, 0);
    int ans = 0;
    rep(i, t.size()){
        int l = i + 1 - pos[t[i]];
        ans -= (l * (l-1) / 2) * c[t[i]];
        ans += s[i][t[i]];
        pos[t[i]] = i+1;
    }
    rep(i, 26){
        int l = t.size() + 1 - pos[i];
        ans -= (l * (l-1) / 2)* c[i];
    }
    return ans;
}

int main() {
    cin >> d;
    rep(i, 26)cin >> c[i];
    rep(i, d)rep(j, 26)cin >> s[i][j];
    //-----code------// 
    vector<int> t(d); 
    rep(i, d)t[i] = rand() % 26;
    vector<int> ans = t;
    double start_temp = 50, end_temp = 10;
    int current_max_score = get_score(t);
    while(clock() < 1.95 * CLOCKS_PER_SEC){
        if(rand() % 2 == 0){
            int D = rand() % d, q = rand() % 26;
            int old = t[D];
            int olds = get_score(t);
            t[D] = q;
            int score = get_score(t);
            double temp = start_temp + (end_temp - start_temp) * clock() / (1.95 * CLOCKS_PER_SEC);
            double prob = exp((olds - score)/temp);

            if(chmax(current_max_score, score)){
                ans = t;
            }else{
                if(prob <= (double)(rand() % 10000) / 10000){
                    t[D] = old;
                }
            }

            if(prob >= ((rand()%inf)/(double)inf))t[D] = old;
        }else{
            int a = rand() % (d-1);
            int b = a + rand() % (min(d-a, 16));
            int olds = get_score(t);
            swap(t[a], t[b]);
            int score = get_score(t);
            if(score < olds){
                swap(t[a], t[b]);
            }
        }
    }
    rep(i, d)cout << ans[i]+1 << endl;
}


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


int main(int argc, const char* argv[]){
    map<string, int> hyo;
    hyo["AC"] = 0;
    hyo["WA"] = 0;
    hyo["TLE"] = 0;
    hyo["RE"] = 0;

    int N;
    cin >> N;
    string line;
    getline(cin, line);//空白避け
    for(int i = 0; i < N; i++){
        getline(cin, line);
        hyo[line]++;
    }

    cout << "AC x " << hyo["AC"] << endl;
    cout << "WA x " << hyo["WA"] << endl;
    cout << "TLE x " << hyo["TLE"] << endl;
    cout << "RE x " << hyo["RE"] << endl;
        
    return 0;
}

Measured memory_bytes: 3632
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

func solve() {
	r := getInt()

	ans := pow(r, 2)
	fmt.Fprintln(wr, ans)
}

func pow(a, b int) int {
	ret := 1
	for i := 0; i < b; i++ {
		ret *= a
	}
	return ret
}

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

const (
	inf = 1 << 60
	// mod = 1000000007
)

var (
	sc = bufio.NewScanner(os.Stdin)
	wr = bufio.NewWriter(os.Stdout)
)

func main() {
	maxBufSize := int(1e8)
	sc.Buffer(make([]byte, 4096), maxBufSize)
	sc.Split(bufio.ScanWords)
	solve()
	wr.Flush()
}

func getInt() (ret int) {
	sc.Scan()
	ret, err := strconv.Atoi(sc.Text())
	if err != nil {
		panic(err)
	}
	return
}

func getIntSlice(n int) (ret []int) {
	ret = make([]int, n)
	for i := range ret {
		ret[i] = getInt()
	}
	return
}

func getString() (ret string) {
	sc.Scan()
	ret = sc.Text()
	return
}

func getRunes() (ret []rune) {
	ret = []rune(getString())
	return
}


Measured memory_bytes: 640
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner (System.in);
        int a = scanner.nextInt();
        int b = scanner.nextInt();
            if (a<b){
            System.out.println("a < b");
            }
            else if (a>b){System.out.println("a > b");}
            else {System.out.println("a == b");}
    }
}

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

int main(){

    int N,cnt=0;
    cin>>N;
    vector<int> S(N+2);
    for(int i=0;i<N;i++){
        cin>>S.at(i+1);
        cnt=cnt+abs(S.at(i+1)-S.at(i));
        }
    cnt+=abs(S.at(N));
    for(int i=0;i<N;i++){
        if((S.at(i)<=S.at(i+1)&&S.at(i+1)<=S.at(i+2))||(S.at(i)>=S.at(i+1)&&S.at(i+1)>=S.at(i+2))){
            cout<<cnt<<endl;
        }
        else cout<<cnt-abs(S.at(i+1)-S.at(i))-abs(S.at(i+2)-S.at(i+1))+abs(S.at(i+2)-S.at(i))<<endl;
    }
}


Measured memory_bytes: 1664
#include<stdio.h>
int main(void)
{
	int a,x,c;
	scanf("%d",&a);
	scanf("%d",&x);
	if(x<=a){
	c=10;
	}
	if(x>a){
	c=0;
	}
	printf("%d\n",c);
	return 0;
}

Measured memory_bytes: 128
package main

import (
	"fmt"
	"strings"
)

func main() {
	var s string
	fmt.Scan(&s)

	small := "abcdefghijklmnopqrstuvwxyz"
	ss := strings.Split(s,"")

	if ss[0] == "A" && strings.Index(small,ss[1]) >= 0{
		substr := string([]rune(s)[2:len(s)])
		substrs := strings.Split(substr,"")
		count := 0
		for k,v := range substrs {
			if v == "C" {
				if k == len(substrs)-1 {
					count += 2
				} else {
					count++
				}
			} else if strings.Index(small,v) < 0{
				count += 2
			}
		}
		if count == 1 {
			fmt.Println("AC")
			return
		}
	}
	fmt.Println("WA")
}

Measured memory_bytes: 640
import sys
input=sys.stdin.readline

class SEGTree:
    def __init__(self,N,op,e):
        self.size=2**(N-1).bit_length()
        self.e=e
        self.op=op
        self.SEG=[self.e]*(self.size*2)
    
    def update(self,i,x):
        i+=self.size
        self.SEG[i]=x
        while i>0:
            i>>=1
            self.SEG[i]=self.op(self.SEG[i*2],self.SEG[i*2+1])
            
    def query(self,l,r):
        l+=self.size
        r+=self.size
        lres,rres=self.e,self.e
        
        while l<r:
            if l&1:
                lres=self.op(lres,self.SEG[l])
                l+=1
            if r&1:
                r-=1
                rres=self.op(self.SEG[r],rres)
            l>>=1
            r>>=1
        res=self.op(lres,rres)
        return res
    
    def get(self,i):
        return self.SEG[i+self.size]

N,K=map(int,input().split())
A=[int(input()) for i in range(N)]
M=max(A)
seg=SEGTree(M+1,max,0)
 
ans=0
for i in range(N):
    l=max(0,A[i]-K)
    r=min(M,A[i]+K)
    res=seg.query(l,r+1)+1
    ans=max(ans,res)
    if seg.get(A[i])<res:
        seg.update(A[i],res)
print(ans)

Measured memory_bytes: 111172
/**********************************************
 *Author*        :XzzF
 *Created Time*  : 2018/8/25 20:04:52
 *Ended  Time*  : 2018/8/25 20:10:44
*********************************************/

#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <stack>
using namespace std;
typedef long long LL;
const int inf = 1 << 30;
const LL INF = 1LL << 60;
const int MaxN = 100000;

int n, k;
int a[MaxN + 5];

int main()
{
	while(scanf("%d %d", &n, &k) != EOF)
	{
		for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
		int ans = inf;
		for(int i = 1; i <= n - k + 1; i++) {
			int L = a[i], R = a[i + k - 1];
			if(L >= 0) ans = min(ans, R);
			else if(R <= 0) ans = min(ans, abs(L));
			else if(L < 0 && R > 0) {
				int tmp = (2 * min(abs(L), R) + max(abs(L), R));
				ans = min(ans, tmp);
			}
		}
		printf("%d\n", ans);
	}
    return 0;
}

Measured memory_bytes: 640
using System;


namespace ConsoleApplication4
{
    class Program
    {
        static void Main(string[] args)
        {

            int H = 1;
            int W = 1;
            for (int a = 0; a < 5;)
            {
                string[] str = Console.ReadLine().Split(' ');
                H = int.Parse(str[0]);
                W = int.Parse(str[1]);
                if (H == 0 && W == 0)
                {
                    break;
                }
                else
                {
                    for (int I = 0; I < H; I++)
                    {
                        int i = 0;
                        int y = I % 2;
                        int x = i % 2;
                        if (y == 0)
                        {
                            for (i = 0; i < W; i++)
                            {
                                x = i % 2;
                                if (x == 0)
                                {
                                    Console.Write("#");
                                }
                                else if (x == 1)
                                {
                                    Console.Write(".");
                                }
                            }
                        }
                        else if (y == 1)
                        {
                            for (i = 0; i < W; i++)
                            {
                                x = i % 2;
                                if (x == 0)
                                {
                                    Console.Write(".");
                                }
                                else if (x == 1)
                                {
                                    Console.Write("#");
                                }
                            }
                        }
                        Console.WriteLine("");
                    }
                     Console.WriteLine("");
                }
            }


        }
    }
}

Measured memory_bytes: 8720
#include <bits/stdc++.h>
#define x first.first
#define y first.second

using namespace std;

typedef long long ll;
typedef pair<int,int> point;
typedef pair< point, int > P;
const int Nmax = 1e5 + 5;
const double PI = acos(-1);

pair< point, int > a[Nmax];
double ans[Nmax], Ans[Nmax];
bool used[Nmax];
int st[Nmax], i, n;

double unghi(P A, P B, P C)
{
    A.x -= B.x; A.y -= B.y; C.x -= B.x; C.y -= B.y;
    double angle = atan2(A.y, A.x) - atan2(C.y, C.x);
    if(angle < 0) angle += 2*PI;
    return angle;
}

bool good(int i, int j, int k)
{
    ll res;
    res = (ll) a[i].x * a[j].y + (ll) a[j].x * a[k].y + (ll) a[k].x * a[i].y;
    res -= (ll) a[i].x * a[k].y + (ll) a[j].x * a[i].y + (ll) a[k].x * a[j].y;
    return (res >= 0);
}

void solve()
{
    sort(a+1, a+n+1);

    int nr, add, i;
    st[nr = 1] = 1;
    for(i=2, add = 1; !used[1]; i += add)
    {
        if(i == n) add = -1;
        if(used[i]) continue;

        while(nr>=2 && !good(st[nr-1], st[nr], i)) used[st[nr--]] = 0;
        st[++nr] = i, used[i] = 1;
    }

    double sum = 0;
    for(i=2; i<nr; ++i)
        ans[st[i]] = PI - unghi(a[st[i-1]], a[st[i]], a[st[i+1]]);
    ans[st[1]] = PI - unghi(a[st[nr-1]], a[st[1]], a[st[2]]);

    for(i=1; i<nr; ++i) sum += ans[st[i]];
    for(i=1; i<nr; ++i) ans[st[i]] /= sum;
}

int main()
{
 //   freopen("input", "r", stdin);
 //   freopen("output", "w", stdout);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i)
        cin >> a[i].x >> a[i].y, a[i].second = i;

    solve();
    cout << setprecision(5) << fixed;
    for(i=1; i<=n; ++i) Ans[a[i].second] = ans[i];
    for(i=1; i<=n; ++i) cout << Ans[i] << '\n';

    return 0;
}


Measured memory_bytes: 768
import java.util.Scanner;


public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = 0, diffValue;
		int number = sc.nextInt();
		//探す文字
		String seekChara = sc.next();
		char chr[][] = new char[number][100];
		
		int numberOfChara [] = new int [number];
		String signboard [] = new String [number];
		//それぞれの看板の文字を保存
		for (int i = 0; i < number; i++) {
			signboard[i] = sc.next();
		}
		//ぞれぞれの看板の文字列数を保存
		for (int i = 0; i < number; i++) {
			numberOfChara[i] = signboard[i].length();
		}
		
		//看板の数だけ繰り返す
		for (int nowBoard = 0; nowBoard < number; nowBoard++) {
			//インデックス格納用
			boolean index [][] = new boolean [seekChara.length()][numberOfChara[nowBoard]];
			
			//合致する文字の場所をインデックスとして保存
			for (int i = 0; i < seekChara.length(); i++) {
				for (int j = 0; j < numberOfChara[nowBoard]; j++) {
					//i番目の文字が看板のj番目の文字と同じならインデックスのi,j番目をtrueに、違うならfalseに
					if (signboard[nowBoard].substring(j, j + 1).equals(seekChara.substring(i, i + 1))) {
						index[i][j] = true;
					}else {
						index[i][j] = false;
					}
				}
			}
			//確認用
			/*
			for (int i = 0; i < seekChara.length(); i++) {
				for (int j = 0; j < numberOfChara[nowBoard]; j++) {
					if (index[i][j]) {
						System.out.printf("1");
					}else {
						System.out.printf("0");
					}
					
				}
				System.out.println();
			}*/
			
			boolean flag = false;
			//インデックスを比較し、すべての文字の間隔が同じ看板があれば数える
			for (int i = 0; i < numberOfChara[nowBoard] && !flag; i++) {
				//最初の文字の場所を見つけたら
				if (index[0][i]) {
					for (int j = 0; j < numberOfChara[nowBoard] && !flag; j++) {
						if (index[1][j] && j > i) {
							diffValue = j - i;
							//この差を残りの文字列でも探す
							flag = seekEqualDiffer(2, j, diffValue, index, seekChara.length(), numberOfChara[nowBoard]);
						}
					}
				}
			}
			//trueならカウント
			if (flag) {
				count++;
			}
			flag = false;
		}
		System.out.println(count);
	}
	
	/*差が同じものを再帰で探していく
	*最後まであればtrueを、なければflaseを返す
	文字番号k開始点j文字差diffValue該当文字かどうかindex配列の長さnumberとnumberOfChara
	*/
	static boolean seekEqualDiffer(int k, int j, int diffValue, boolean index[][], int number, int numberOfChara){
		for (int p = j + 1; p < numberOfChara && k < number; p++) {
			if (index[k][p] && p - j == diffValue) {
				if (k < number - 1) {
					return seekEqualDiffer(k + 1, p , diffValue, index, number, numberOfChara);
				}else {
					return true;
				}	
			}
		}
		return false;
	}
}

Measured memory_bytes: 37168