akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;
#define ff        first
#define ss        second
#define ll        long long
#define int       long long
#define inf       ((ll)1e18)
#define mod       1000000007
#define double    long double
#define ull       unsigned long long
#define vi        vector<ll>
#define ppi       pair<int,int>
#define pii       pair<pair<int,int>,int>
#define pb        push_back
#define pi        2*acos(0.0)
#define rev       greater<int>()
#define pr(a,x,y) for(int i=x;i<y;i++){cout<<a[i]<<" ";}
#define sp(x,y)   fixed<<setprecision(y)<<x
#define w(x)      ll x; cin>>x; while(x--)
#define all(v)    v.begin(), v.end()
#define rall(v)   v.rbegin(), v.rend()
#define test      cout<<"This is test"<<endl;
#define str       string
#define endl      '\n'
#define e         cout<<'\n';
void kehsihba(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	/*#ifndef ONLINE_JUDGE
		freopen("input.txt", "r", stdin);
		freopen("output.txt", "w", stdout);
	#endif*/
}
void solve(){
	ll x,k,d;cin>>x>>k>>d;
	x=abs(x);
	ll a=min(k,x/d);
	k-=a;
	x-=d*a;
	if(k%2==0){cout<<x;}
	else{cout<<abs(d-x);}
}
int32_t main(){
	kehsihba();
	//init();
	ll t=1;
	//cin>>t;
	for(int k=1;k<=t;k++){
		//cout<<"Case "<<k<<": ";
		solve();
		//e;
	}
}


Measured memory_bytes: 3668
a, b, k = map(int, input().split())
if b-a+1 < 2*k:
    for i in range(a, b+1):
        print(i)
else:
    for i in range(a, a+k):
        print(i)
    for i in range(b-k+1, b+1):
        print(i)

Measured memory_bytes: 38256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
set<ll> s;
int main(){
    ll K,cnt=0,xi=0,x;
    scanf("%lld",&K);
    for(int i=0;i<=14;++i){
        for(int j=0;j<i-(i>=11)+(i<1);++j){
            for(int k=0;k<=9;++k){
                x=xi+1ll*j*(ll)pow(10,i+1)+1ll*k*(ll)pow(10,i);
                if(x==0||s.count(x)) continue;
                ++cnt;
                s.insert(x);
                printf("%lld\n",x);
                if(cnt==K){
                    return 0;
                }
            }
        }
        xi=xi*10+9;
    }
    return 0;
}

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

int main()
{
    int n,i;
    double t,a,x,y,minim=100000,index=0,d;
    cin>>n>>t>>a;
    for(i=1;i<=n;i++)
    {
        cin>>x;
        y=t-x*0.006;
        d=a-y;
        if(d<0)
            d=0-d;
        if(d<minim)
            minim=d,index=i;
    }
    cout<<index;
    return 0;
}


Measured memory_bytes: 256
// Vivek Rai
// Blazer_007

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

#define fastio    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl      '\n'

typedef long long int ll;
const int hell = 1e9 + 7 ;



signed main() {

    fastio

    ll n , d;
    cin >> n >> d;
    ll ans = 0;
    ll dd = d * d;
    while(n--)
    {
    	ll x , y;
    	cin >> x >> y;
    	ll dist = x * x + y * y;
    	if (dist <= dd)
    		ans++;
    }
    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 3652
import java.util.Scanner;

public class Main {
	static Scanner scan = new Scanner(System.in);
	public static void main(String args[]){
		run();
	}
	static void run(){
		
		int n, tmp, count;
		int[] a = new int[100];
		
		boolean flag;
		
		n = scan.nextInt();
		
		for(int i = 0; i < n; i++){
			a[i] = scan.nextInt();
		}
		
		flag = true;
		
		count = 0;
		
		while(flag){
			flag = false;
			for(int i = n - 1; i > 0; i--){
				if(a[i] < a[i - 1]){
					tmp = a[i];
					a[i] = a[i - 1];
					a[i - 1] = tmp;
					flag = true;
					count++;
				}
			}
		}
		for(int i = 0; i < n; i++){
			if(i == n - 1){
				System.out.println(a[i]);
			}else{
				System.out.print(a[i]+" ");
			}
		}
		System.out.println(count);
	}
}

Measured memory_bytes: 26284
r,c = map(int,raw_input().split())
matrix = []
for i in range(r):
    matrix.append(map(int,raw_input().split()))

a = [0 for j in range(c)]

matrix.append(a)

for i in range(r):
    sum = 0
    for j in range(c):
        sum += matrix[i][j]
    matrix[i].append(sum)

for j in range(c):
    sum = 0
    for i in range(r):
        sum += matrix[i][j]
    matrix[r][j] = sum

sum = 0
for j in range(c):  
    sum += matrix[r][j]
matrix[r].append(sum)

for i in range(r):
    for j in range(c):
        print matrix[i][j],
    print matrix[i][c]

for j in range(c + 1):
    print matrix[r][j],

Measured memory_bytes: 6464
#include<stdio.h>
#include<stdlib.h>
#define N 3

int main(void){
  int i = 0;
  int wk = 0;
  int num[3] = {0};
  int sortflag = 0;
  scanf("%d %d %d", &num[0], &num[1], &num[2]);
  
  do{
    sortflag = 0;
    for(i = 0 ; i < N - 1 ; i++){
      if(num[i] > num[i + 1]){
        wk = num[i];
        num[i] = num[i + 1];
        num[i + 1] = wk;
        sortflag = 1;
      }
    }
  }while(sortflag == 1);
  
  printf("%d %d %d\n", num[0], num[1], num[2]);
  return 0;
}



Measured memory_bytes: 2044
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pii pair<int,int>
#define pp pair<pair<ll, ll>,pair<ll, ll>>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define vii vector<int>
#define vll vector<ll>
#define mat vector<vector<ll>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define fi first
#define sc second
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep2(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,n) for(ll i=n-1;i>=0;i--)
#define all(x) x.begin(),x.end()
#define sz(x) (ll) (x).size()
#define pq priority_queue<ll>
#define pqg priority_queue<ll,vector<ll>,greater<ll>>
#define LB(v,x) (lower_bound(v.begin(),v.end(),x)-v.begin())
#define UB(v,x) (upper_bound(v.begin(),v.end(),x)-v.begin())
#define ERASE(v) sort(v.begin(),v.end());v.erase(unique(v.begin(),v.end()),v.end())
// #define int ll
using namespace std;
const ll INF = (1 << 30 ) - 1;
const ll LLINF = (1LL << 60LL);
const ll MOD = 1000000007;
const ll mod = 998244353;
const ll MAX = 1100000;
const double pi = acos(-1);
const double eps = 1e-10;
ll dx[4] ={1,0,-1,0} , dy[4] ={0,1,0,-1};
 
template<class T> 
inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> 
inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
 
struct Timer{
    chrono::system_clock::time_point start, end;
    Timer(){ start = chrono::system_clock::now(); }
    ~Timer(){
        end = chrono::system_clock::now();
        auto msec = chrono::duration_cast<chrono::milliseconds>(end - start).count();
        cerr<<"time : "<<msec<<" ms"<<endl;
    }
};





signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    Timer TM;

   ll a,p;
   cin>>a>>p;
   cout<<(a*3+p)/2<<endl;

    return 0;
}

Measured memory_bytes: 256
#include <vector>
#include <iostream>
#include <utility>
#include <algorithm>
#include <string>
#include <deque>
#include <queue>
#include <tuple>
#include <queue>
#include <functional>
#include <cmath>
#include <iomanip>
#include <map>
#include <set>
#include <numeric>
#include <unordered_map>
#include <unordered_set>
#include <complex>
#include <iterator>
#include <array>
#include <memory>
#include <stack>
#define vi vector<int>
#define vvi vector<vector<int> >
#define ll long long int
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vb vector<bool>
#define vc vector<char>
#define vs vector<string>
#define ld long double
#define INF 1e9
#define EPS 0.0000000001
#define rep(i,n) for(int i=0;i<n;i++)
#define loop(i,s,n) for(int i=s;i<n;i++)
#define all(in) in.begin(), in.end()
template<class T, class S> void cmin(T &a, const S &b) { if (a > b)a = b; }
template<class T, class S> void cmax(T &a, const S &b) { if (a < b)a = b; }
#define MAX 9999999
using namespace std;
typedef pair<int, int> pii;
typedef pair<double,double>pdd;
typedef pair<ll,ll>pll;
vector<vector<int>>graph(101,vector<int>(101));
int main(){
    int h,w; cin>>h>>w;
    int n; cin>>n;
    vi v; rep(i,n){int hoge; cin>>hoge; v.push_back(hoge);}
    
    pii now=pii(0,0);
    bool down=true;
    for(int i=0;i<n;i++){
        while(v[i]-->0){
            graph[now.first][now.second]=i+1;
            if(down==true&&now.first==h-1){now.second++;down=false;}
            else if(down==false&&now.first==0){now.second++; down=true;}
            else if(down){now=pii(now.first+1,now.second);}
            else now=pii(now.first-1,now.second);
            
        }
    }
    rep(i,h){
        rep(j,w){
            if(j)cout<<" ";
            cout<<graph[i][j];
        }
        cout<<endl;
    }
}

Measured memory_bytes: 384
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#define ll long long
#define rep(i,l,r) for(ll i=(l);i<(r);i++)
#define max(p,q) ((p)>(q)?(p):(q))
#define min(p,q) ((p)<(q)?(p):(q))
#define chmax(a,b) ((a)=(a)>(b)?(a):(b))
#define chmin(a,b) ((a)=(a)<(b)?(a):(b))
#define abs(p) ((p)>=(0)?(p):(-(p)))
int cmp(const void *a, const void *b);
//your code here!

int main(void){
    ll N, K, h[100010], dp[100010], MIN;
    scanf("%lld %lld", &N, &K);
    rep(i, 0, N) scanf("%lld", h+i);
    dp[0] = 0;
    rep(i, 1, N){
        dp[i] = dp[i-1] + abs(h[i]-h[i-1]);
        rep(j, 2, K+1){
            if(i-j<0) break;
            chmin(dp[i], dp[i-j] + abs(h[i]-h[i-j]));
        }
    }
    printf("%lld\n", dp[N-1]);
    return 0;
}

int cmp(const void *a, const void *b){
    ll A=*(ll *)a, B=*(ll *)b;
    if(A==B)return 0;
    else return A>B ? 1:-1;//昇順ソート
}


Measured memory_bytes: 1664
inpl = lambda: list(map(int,input().split()))
MOD = 10**9 + 7
N, M = inpl()
 
def factorize(n):
  factorize_list = []
  i = 2
  while i*i <= n:
    k = 0
    while n % i == 0:
      n //= i
      k += 1
    if k > 0:
      factorize_list.append(k)
    i += 1
  if n > 1:
    factorize_list.append(1)
  return(factorize_list)

def H(n,k):
  h = 1
  L = n + k - 1
  k = min(n-1,k)
  for j in range(k):
    h *= L-j
  for j in range(k):
    h //= j+1
  return h

ans = 1
for k in factorize(M):
  ans *= H(N,k) % MOD
  ans %= MOD

print(ans)

Measured memory_bytes: 3064
import itertools
#import time

#t1 = time.time()

num = [int(input()) for _ in range(5)]
#num2 = [n if n % 10 == 0 else n - (n%10) + 10  for n in num]

N = []

for i in list(itertools.permutations(range(5))):
    c = 0
    n = 0
#    print(i)
    for j in i:
        c += 1
 #       print(j)
        if c == 5:
            n += num[j]
#            print(n)
        else:
            if num[j]%10 == 0: n+=num[j]
            else:n += num[j] - (num[j] % 10) + 10
 #           print(n)
    N.append(n)

print(int(min(N)))

#t2 = time.time()

#print(t2-t1)


Measured memory_bytes: 3060
#include <stdio.h>

int attack(int const attack, int HP){
    HP = HP - attack;
    return HP;
}

int main(){
    int A, B, C, D;
    scanf("%d", &A);
    scanf("%d", &B);
    scanf("%d", &C);
    scanf("%d", &D);
    int turn = 0;
    for (; A > 0 && C > 0;turn++){
        if(turn%2){
            A = attack(D, A);
        }else{
            C = attack(B, C);
        }
    }
    if(A>0){
        puts("Yes");
    }else{
        puts("No");
    }
    return 0;
}

Measured memory_bytes: 1660
#include <bits/stdc++.h>
using namespace std;
int main(){
  string a,b;
  cin>>a>>b;
  if(a.size()>b.size()){
    cout<<"GREATER"<<endl;
  }
  else if(a.size()<b.size()){
    cout<<"LESS"<<endl;
  }
  else{
    for(int i=0;i<a.size();i++){
      if(a.at(i)==b.at(i)){
        continue;
      }
      else if(a.at(i)<b.at(i)){
        cout<<"LESS"<<endl;
        return 0;
      }
      else if(a.at(i)>b.at(i)){
        cout<<"GREATER"<<endl;
        return 0;
      }
    }
    cout<<"EQUAL"<<endl;
  }  
  return 0;
}

Measured memory_bytes: 256
from collections import defaultdict

N = int(input())
MOD = 10**9 + 7

def primeCount(N):
    R = int(N**(0.5)) + 1  # 素数の範囲
    primes = {}  # 素数のリスト
    n = N
    for num in range(2, R):
        primes[num] = 0
        while n % num == 0:
            n //= num
            primes[num] += 1
    if n > 1 :
        primes[n] = 1
    return { key : val for key, val in primes.items() if val > 0}  # フィルターをかける

primes = defaultdict(int)
for i in range(1, N + 1):
    ps = primeCount(i)
    for p, c in ps.items():
        primes[p] += c

ans = 1
for c in primes.values():
    ans *= (c + 1)
    ans %= MOD

print(ans % MOD)

Measured memory_bytes: 3444
mountains = [0 for i in range(10)]
for i in range(10):
  mountains[i] = int(input())

highest1 = mountains[0]
if highest1 < mountains[1]:
  highest2 = highest1
  highest1 = mountains[1]
else:
  highest2 = mountains[1]

if highest1 < mountains[2]:
  highest2, highest3 = highest1, highest2
  highest1 = mountains[2]
elif highest2 < mountains[2]:
  highest3 = highest2
  highest2 = mountains[2]
else:
  highest3 = mountains[2]

for i in range(3,10):
  if highest1 < mountains[i]:
    highest1, highest2, highest3 = mountains[i], highest1, highest2
  elif highest2 < mountains[i]:
    highest2, highest3 = mountains[i], highest2
  elif highest3 < mountains[i]:
    highest3 = mountains[i]

print(highest1)
print(highest2)
print(highest3)


Measured memory_bytes: 5596
/*
      author : nishi5451
      created: 12.08.2020 00:15:14
*/

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


int main(){
    int n,h,w;
    cin >> n >> h >> w;
    cout << (n-h+1)*(n-w+1) << endl;
    return 0;
}

Measured memory_bytes: 3568
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<iomanip>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<queue>
#include<set>
#define ll long long
using namespace std;
ll maxn=-1;

int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
	ll a,b,n;
	cin>>a>>b>>n;
	ll i;
	double t;
	t=(double)min(b-1,n)/b*a;
	t=floor(t);
	cout<<t;
    return 0;
}



Measured memory_bytes: 3788
import java.util.Scanner;

class Main {
	public static void main(String args[]) {
		StringBuilder sb = new StringBuilder();
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		int q = sc.nextInt();
		int a;
		int[] x = new int[n];
		for (int i = 0; i < q; i++) {
			a = sc.nextInt();
			x[a - 1]++;
		}
		for (int i = 0; i < n; i++) {
			if (x[i] >= q - k + 1) {
				sb.append("Yes" + "\n");
			} else {
				sb.append("No" + "\n");
			}
		}
		System.out.println(sb);
	}
}

Measured memory_bytes: 50332
#include <bits/stdc++.h>
#define rep(i, n) for (int i=0; i<(int)(n); i++)
#define all(v) v.begin(), v.end()
#define PRINT(v) for (auto x : (V)) cout <<x <<" " <<endl;
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
const ll MOD = 1000000007;
const ll INF = 10000000000000000;
vector<int> x4 = {0, 1, 0, -1}, x8 = {0, 1, 1, 1, 0, -1, -1, -1};
vector<int> y4 = {1, 0, -1, 0}, y8 = {1, 1, 0, -1, -1, -1, 0, 1};
template<class T> struct edge { int from, to; T cost;};
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;}
template<class T> inline T powerM(T a,T b){if (b==0) return 1;
T tmp = powerM(a,b/2); if (b%2==0) return tmp*tmp%MOD; else return tmp*tmp%MOD*a%MOD; }
template<class T> inline T power(T a,T b,T m){ if (b==0) return 1;
  T tmp = power(a,b/2,m); if (b%2==0) return tmp*tmp%m; else return tmp*tmp%m*a%m; }
template<class T> inline T gcd(T a, T b){if (b==0) return a; return gcd(b, a%b);}
template<class T> inline T lcm(T a, T b){return a / gcd(a,b) * b;}
// ax+by=gcd(a,b)を解く
template<class T> inline T extgcd(T a,T b,T &x,T &y){if (b==0){x=1; y=0; return a;} T d=extgcd(b,a%b,y,x); y -= a/b*x; return d;}
void hey(){ cout <<"hey" <<endl; }


// 約数の列挙O(√n)--------------------------------------------
vector<int> divisor(int n){
  vector<int> res;
  for (ll i=1; i*i<=n; i++){ if (n%i==0){ res.push_back(i); if (i != n/i) res.push_back(n/i); } }
  return res;
}

int main() {
  int N,M; cin >>N >>M;
  // 最良だとai = M/N でこれが最大公約数になる
  // 乃ち答えの範囲は 1 <= x <= M/N
  // この範囲のxにおいて、M - x * N が全ai = x としたときの余っている和で、これもxの倍数であるときのみxが公約数になりうる
  // 以上より、求める値は「1<=x<=M/N かつ (M - x*N) % x == 0 を満たすxの最大値」となる
  // …が、2つ目の条件⇔xはMの約数
  // 以上より、求める値は「1<=x<=M/N を満たすMの約数xの最大値」である

  int res = 1;
  for (ll i=1; i*i<=M; i++){
    if (M%i==0){
      // i と M/i はMの約数。M/iの方からチェック
      int x = M/i;
      if (x <= M/N){
        res = x; break;
      }else if (i <= M/N){
        res = i;
      }
    }
  }
  cout <<res <<endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define SORT(x) sort(x.begin(),x.end(),greater<int>())
#define ALL(x) x.begin(),x.end()
#define rep(i, n) for(int i = 0; i < n; i++)
#define reps(i, m, n) for(int i = m; i < n; i++)
#define repr(i, m, n) for(int i = m; i >= n; i--)
#define INF 1000000000000000003 //1000000007
#define PI (acos(-1))
#define MOD 1000000007
using namespace std;
typedef long long ll;


void Main(){

  int N;
  cin>>N;

  int ans=0;

  rep(i,10){
    if(N>>i & 1) ans=i;
  }

  cout<< pow(2,ans)<<"\n";

}

//-----------------------------------
int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(0);
  Main();
}
//-----------------------------------


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {
	for {
		var a, b, c, d, e, f float64
		i, _ := fmt.Scan(&a, &b, &c, &d, &e, &f)
		if i == 0 {
			break
		}

		y := (c*d - a*f) / (b*d - a*e)
		x := (c - b*y) / a

		fmt.Printf("%.3f %.3f\n", x, y)
	}
}



Measured memory_bytes: 1156
#include <iostream>

using namespace std;

int main(int argc, char **argv)
{
	char a, b, c, d, e, f, g, h, i;
	
	while((cin >> a >> b >> c >> d >> e >> f >> g >> h >> i)){
		if(((a == b && b == c)||(a == d && a == g)||(a == e && e == i)) && ( a != 's')){
			cout << a << endl;
		} else if(((b == e && e == h) || (e == d && e == f) || (c == e && c == g)) && (e != 's')){
			cout << e << endl;
		} else if(((c == f && f == i) || (g == h && g == i)) && (i != 's')){
			cout << i << endl;
		} else {
			cout << 'd' << endl;
		}
	}
	
	return 0;
}

Measured memory_bytes: 0
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int s,a[25],b[100],n,k,i; 
int main()
{

  int j,m,t;	 
  char x,y;
cin>>x>>y;  
if (x==y) cout<<'H'<<endl;
  else cout<<'D'<<endl;
 return 0;     
} 

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

using namespace std;

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair

const int MOD = 1e9 + 7;

bool red[100001];
int cnt[100001];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
	{
		cnt[i] = 1;
	}
	red[0] = true;
	for(int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		u--; v--;
		if(red[u])
		{
			if(cnt[u] == 1)
			{
				red[u] = false;
			}
			red[v] = true;
		}
		cnt[u]--; cnt[v]++;
	}
	int ans = 0;
	for(int i = 0; i < n; i++)
	{
		if(red[i]) ans++;
	}
	cout << ans;
	return 0;
}


Measured memory_bytes: 768
# yahoo-procon2019-qualB - Path
def main():
    C = [0] * 4
    for _ in range(3):
        a, b = list(map(int, input().rstrip().split()))
        C[a - 1] += 1
        C[b - 1] += 1
    print("YES" if set(C) == {1, 2} else "NO")


if __name__ == "__main__":
    main()

Measured memory_bytes: 3188
#include <bits/stdc++.h>
    using namespace std;
     
    int main (){
      int a,b,c,d;
      cin>>a>>b>>c>>d;
      if(a+b > c+d){
      cout << "Left" << endl;
      }
        else if(a+b == c+d){
      cout << "Balanced" << endl;
      }
      	else{
       cout <<"Right"<< endl;
        }
    }

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	Scanner sc = new Scanner(System.in);

	void run1() {
		int[][] dp = new int[4][4001];
		for (int i = 0; i <= 1000; i++) dp[0][i] = 1;
		for (int i = 0; i < 3; i++) {
			for (int j = 0; j <= 4000; j++) {
				for (int k = 0; k <= 1000; k++) {
					if (j + k <= 4000) dp[i + 1][j + k] += dp[i][j];
				}
			}
		}
		while (sc.hasNext()) System.out.println(dp[3][sc.nextInt()]);
	}

	void run2() {
		int[] cnt1 = new int[2001];
		int[] cnt2 = new int[4001];
		for (int i = 0; i <= 1000; i++) for (int j = 0; j <= 1000; j++) cnt1[i + j]++;
		for (int i = 0; i <= 2000; i++) for (int j = 0; j <= 2000; j++) cnt2[i + j] += cnt1[i] * cnt1[j];
		while (sc.hasNext()) System.out.println(cnt2[sc.nextInt()]);
	}

	public static void main(String[] args) {
		new Main().run2();
	}
}

Measured memory_bytes: 20516
#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <algorithm>
#include <limits>
#include <ios>
#include <iomanip>
using namespace std;

#define rep(i,N) for(int i=0; i<N; i++)
#define revrep(i,N) for(int i=N-1; i>=0; i--)

typedef long long ll;
typedef unsigned int uint;

int main(void)
{
    uint a[5];
    uint k;
    rep(i,5){
        cin >> a[i];
    }
    cin >> k;
    if (a[4]-a[0] > k) {
        cout << ":(" << endl;
    } else {
        cout << "Yay!" << endl;
    }
    
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i=0; i<n; i++)
#define pb push_back

int main() {
    int N; cin >> N;
    int A[N], B[N];
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];
    
    int dp[1<<N][N];
    rep(i, 1<<N) rep(j, N) dp[i][j] = 10000;
    dp[0][0] = 0;
    
    rep(S, 1<<N) rep(i, N) {
        int cnt = 0;
        rep(j, N) if ((S>>j)&1) cnt++;
        rep(j, N) {
            if ((S>>j)&1) continue;
            if (S!=0) {
                int now;
                if ((cnt-j)%2==0) now = A[j];
                else now = B[j];
                int prev;
                if ((cnt-1-i)%2==0) prev = A[i];
                else prev = B[i];
                if (prev>now) continue;
            }
            int idx = j;
            for (int k=j+1; k<N; k++) if ((S>>k)&1) idx++;
            dp[S|(1<<j)][j] = min(dp[S|(1<<j)][j], dp[S][i]+idx-cnt);
        }
    }
    
    int ans = 10000;
    rep(i, N) ans = min(ans, dp[(1<<N)-1][i]);
    if (ans==10000) cout << -1 << endl;
    else cout << ans << endl;
}

Measured memory_bytes: 18688
#include <cmath>
#include <iostream>
#include <functional>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <stdio.h>
using namespace std;

int main(){    
  string S;
  char a,b,acount=0,bcount=0;

  cin >> S;

  if(S[0] == S[1] && S[2] == S[3] && S[0] != S[2]){
    cout << "Yes" << endl;
    return 0;
  }  
  if(S[0] == S[2]  && S[1] == S[3] && S[0] != S[1]){
    cout << "Yes" << endl;
    return 0;
  }
  if(S[0] == S[3] && S[1] == S[2] && S[0] != S[1]){
    cout << "Yes" << endl;
    return 0;
  }
  else{
    cout << "No" << endl;
  }
}


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

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vector<ll>> vvll;
typedef vector<vector<vector<ll>>> vvvll;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;
typedef vector<vector<vector<bool>>> vvvb;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<vpll> vvpll;
typedef vector<double> vd;
typedef vector<vd> vdd;

#define FOR(i,x,y) for(ll i=(ll)x; i<(ll)y; ++i)
#define REP(i,y) FOR(i, 0, y)
#define RFOR(i,x,y) for(ll i=(ll)x; i>=(ll)y; --i)
#define RREP(i,x) RFOR(i, x, 0)
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define debug_print(x...) cerr << "line " << __LINE__ << " : "; debug_print_in(x);

template <typename First>
void debug_print_in(First first){
  cerr << first << endl;
  return;
}

template <typename First, typename... Rest>
void debug_print_in(First first, Rest... rest){
  cerr << first << " ";
  debug_print_in(rest...);
  return;
}

void IN(void){
  return;
}

template <typename First, typename... Rest>
void IN(First& first, Rest&... rest){
  cin >> first;
  IN(rest...);
  return;
}

template <typename First>
void OUT(First first){
  cout << first << endl;
  return;
}

template <typename First, typename... Rest>
void OUT(First first, Rest... rest){
  cout << first << " ";
  OUT(rest...);
  return;
}

template<class t, class u> void chmax(t&a,u b){if(a<b)a=b;};
template<class t, class u> void chmin(t&a,u b){if(a>b)a=b;};
int popcount(int t){return __builtin_popcount(t);} //GCC
int popcount(ll t){return __builtin_popcountll(t);} //GCC

template <typename T>
void vec_print(vector<T> VEC){
  REP(i, VEC.size()){
    cerr << VEC[i] << " ";
  }
  cerr << endl;
};

template <typename T>
void mat_print(vector<vector<T> > MAT){
  REP(i,MAT.size()){
    REP(j,MAT[i].size()){
      cerr << MAT[i][j] << " ";
    }
    cerr << endl;
  }
};

constexpr int INF = (1<<30);
constexpr ll INFLL = 1LL<<62;
constexpr long double EPS = 1e-12;
constexpr ll MOD = (ll)((1E+9)+7);

int main(){
  cin.tie(0); // cut the cin and cout (default, std::flush is performed after std::cin)
  ios::sync_with_stdio(false); // cut the iostream and stdio (DON'T endl; BUT "\n";)

  ll N;
  IN(N);
  vll A(N);
  unordered_map<ll, ll> mp;
  REP(i,N){
    IN(A[i]);
    mp[A[i]]++;
  }

  ll total = 0;
  for(auto itr : mp){
    total += ((itr.second-1)*itr.second)/2;
  }

  REP(i,N){
    ll c = mp[A[i]];
    ll ans = total - ((c-1)*c)/2 + ((c-2)*(c-1))/2;
    OUT(ans);
  }

  return 0;
}

Measured memory_bytes: 9160
s = input()

length = len(s)
t = ''
word = ''

for a in range(length-1, -1, -1):
    t += s[a]
    if t == 'maerd' or t == 'remaerd' or t == 'esare' or t == 'resare':
        word += t
        t = ''

if s == word[::-1]:
    print('YES')
else:
    print('NO')


Measured memory_bytes: 3316
#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 ){
	
	int n;
	int count = 0;
	int min = 500000;
	string s;
	int w[300000] = { 0 };
	int e[300000] = { 0 };
	cin >> n >> s;
	
	rep( i, n ){
		if( i != 0 ){
			if( s[ i - 1 ] == 'W' ){
				w[ i ] = w[ i - 1 ] + 1;
			}else{
				w[ i ] = w[ i - 1 ];
			}
			if( s[ ( ( n - 1 ) - i ) + 1  ] == 'E' ){
				e[ ( n - 1 ) - i ] = e[ ( ( n - 1 ) -  i ) + 1 ] + 1;
			}else{
				e[ ( n - 1 ) - i ] = e[ ( ( n - 1 ) - i ) + 1 ];
			}
		}
	}
	rep( i, n ){
		if( w[ i ] + e[ i ] < min ){
			min = w[ i ] + e[ i ];
		}
	}
	
	cout << min << endl;
	return 0;
}

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

int main() {
    int n; cin >> n;
    map<string,int> mp;
    rep (i,n) {
        string s; cin >> s;
        if(!mp[s]) mp[s] = 0;
        else
            mp[s]++;
    }
    cout << mp.size() << endl;
    return 0;
}

Measured memory_bytes: 19200
#include<bits/stdc++.h>
using namespace std;
int dis[2000005],f[100005],w[100005],qu[5000005],cur;
vector<int>g[1000005];
vector<pair<int,int>>edge[1000005],a;
int get_f(int x)
{
	if(x==f[x])
		return x;
	return f[x]=get_f(f[x]);
}
void merge(int x,int y)
{
	if(w[x]!=cur)
	{
		w[x]=cur;
		a.push_back(make_pair(0,x));
		f[x]=x;
	}
	if(w[y]!=cur)
	{
		w[y]=cur;
		a.push_back(make_pair(0,y));
		f[y]=y;
	}
	f[get_f(x)]=get_f(y);
}
int main()
{
	int n,m,p,q,c;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&p,&q,&c);
		edge[c].push_back(make_pair(p,q));
	}
	int sum=n;
	for(int i=1;i<=1000000;i++)
	{
		if(edge[i].empty())
			continue;
		cur++;
		a.clear();
		for(int j=0;j<edge[i].size();j++)
		{
			int x=edge[i][j].first,y=edge[i][j].second;
			merge(x,y);
		}
		for(int j=0;j<a.size();j++)
			a[j].first=get_f(a[j].second);
		sort(a.begin(),a.end());
		for(int j=0,k=0;j<a.size();j=k)
		{
			sum++;
			while(k<a.size()&&a[j].first==a[k].first)
			{
				g[sum].push_back(a[k].second);
				g[a[k++].second].push_back(sum);
			}
		}
	}
	for(int i=0;i<=sum;i++)
		dis[i]=-2;
	dis[1]=0;
	qu[0]=1;
	int b=0,e=1;
	while(b<e)
	{
		int k=qu[b];
		b++;
		for(int i=0;i<g[k].size();i++)
		{
			int v=g[k][i];
			if(dis[v]==-2)
			{
				dis[v]=dis[k]+1;
				qu[e]=v;
				e++;
			}
		}
	}
	printf("%d\n",dis[n]/2);	
	return 0;
}


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

using namespace std;

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

	int n,h,w,a,b;
	int res = 0;

	cin >> n >> h >> w;

	for(int i=0;i<n;i++)
	{
		cin >> a >> b;
		if(a>=h && b>=w)
		{
			res++;
		}
	}

	cout << res << '\n';

	return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e10;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
using pll = pair<ll, ll>;
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;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll a, b; cin >> a >> b;
    if(b == 1){
        cout << 0 << endl;
        return 0;
    }
    ll num = 1;
    ll ans = 0;
    while(true){
        if(num >= b){
            break;
        }
        ans++;
        num += (a-1);
    }

    cout << ans << endl;



}

Measured memory_bytes: 3608
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define fe 2*idx
#define fd fe+1
#define mid (l+r)/2
const int MAXN = 3e5+7;
const ll MOD = 1e9+7, UM=1;
ll a[MAXN], poten[62], um[62], zer[62];
inline ll soma_mod(ll x, ll y){return (x+y)%MOD;}
int main(){
    fastio;
    int n; cin>>n;
    poten[0] = 1;
    for(int i=1; i<60; i++)poten[i] = (2LL*poten[i-1])%MOD;

    for(int i=1; i<=n; i++){
        cin>>a[i];
        for(ll j=0; j<60; j++){
            if( ((UM<<j)&a[i]) )um[j]++;
            else zer[j]++;
        }
    }
    ll ans = 0;
    for(ll j=0; j<60; j++){
        ans = soma_mod(ans, poten[j]*( (um[j]*zer[j])%MOD ));
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 2560
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<queue>
using namespace std;

typedef long long ll;
typedef pair<int,int> P;

#define pb push_back
#define fr first
#define sc second

const ll M = 1000000007;

ll fac[5002];
void init_fac(int MAX_N = 5000){
	fac[0] = 1;
	for(int i = 1 ; i <= MAX_N ; i ++){
		fac[i] = fac[i-1]*i;
		fac[i] %= M;
	}
}
ll C[5002][5002];
void init_C(int MAX_N = 5000, int MAX_K = 5000){
	C[0][0] = 1;
	for(int i = 0 ; i <= MAX_N ; i ++){
		for(int j = 0 ; j <= i ; j ++){
			C[i][j] %= M;
			C[i+1][j] += C[i][j];
			C[i+1][j+1] += C[i][j];
		}
	}
}

int N;
vector<int> G[5002];
ll ret[5002];

ll dp[2][5002] = {};
ll memo[5002];

int dfs(int v,int p){
	ret[v] = 1;
	
	vector<ll> vec;
	ll cnt = 1;
	for(int i = 0 ; i < G[v].size() ; i ++){
		if(G[v][i] == p)continue;
		vec.pb(dfs(G[v][i],v));
		cnt += vec[vec.size()-1];
	}
	if(p != 0)vec.pb(N-cnt);
	
	sort(vec.begin(),vec.end());
	reverse(vec.begin(),vec.end());
	if(vec[0] > N-vec[0]){
		ret[v] = 1;
	}
	else if(vec[0] == N-vec[0]){
		ret[v] *= fac[N-vec[0]];
		ret[v] %= M;
	}
	else {
		int t = 0 , t_ = 1;
		int sum = 0;
		dp[t][0] = 1;
		for(int i = 0 ; i < vec.size() ; i ++){
			int d = vec[i];
			for(int j = 0 ; j < 5002 ; j ++){
				dp[t_][j] = 0;
			}
			for(int m = 0 ; m <= min(sum,5000-sum) ; m ++){
				for(int k = 0 ; k <= d ; k ++){
					memo[k] = 1;
					memo[k] *= C[m][k];
					memo[k] *= C[d][k]; memo[k] %= M;
					memo[k] *= fac[k]; memo[k] %= M;
				}
				for(int n = max(0,m-d) ; n <= min(sum+d,min(m+d,5000-sum-d)) ; n ++){
					ll X = 0;
					int MIN_K = max(0,m-n);
					int MAX_K = min(m+d-n,min(d,m));
					for(int k = MIN_K ; k <= MAX_K ; ++k){
						int l = m+d-n-k;
						if(l <= k){
							X *= 2;
							if(l == k){
								X += memo[k]*memo[k];
							}
							break;
						}
						/*int l = m+d-n-k;
						if(l < k && MIN_K <= l){}
						else {
							memo[k] *= memo[l];
							memo[k] %= M;
							memo[l] = memo[k];
						}
						X += memo[k];*/
						ll Y = memo[k];
						Y *= memo[l];
						Y %= M;
						X += Y;
					}
					X %= M;
					dp[t_][n] += dp[t][m]*X;
					dp[t_][n] %= M;
				}
			}
			/*for(int n = 0 ; n <= min(sum+d,5000-sum-d) ; n ++){
				for(int m = max(0,n-d) ; m <= min(sum,min(n+d,5000-sum)) ; m ++){
					ll X = 0;
					for(int k = max(0,m-n) ; k <= min(m+d-n,m) ; k ++){
						ll Y = 1;
						Y *= C[m][k]; Y %= M;
						Y *= C[d][k]; Y %= M;
						Y *= fac[k]; Y %= M;
						int l = m+d-n-k;
						Y *= C[m][l]; Y %= M;
						Y *= C[d][l]; Y %= M;
						Y *= fac[l]; Y %= M;
						X += Y;
					}
					X %= M;
					dp[t_][n] += dp[t][m]*X;
					dp[t_][n] %= M;
				}
			}*/
			sum += d;
			swap(t,t_);
		}
		ret[v] = (dp[t][0]+dp[t][1])%M;
	}
	
	return cnt;
}

int main(){
	init_fac();
	init_C();
	
	scanf("%d",&N);
	for(int i = 0 ; i < N-1 ; i ++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].pb(y);
		G[y].pb(x);
	}
	
	int root = 1;
	dfs(1,0);
	
	ll RET = 1;
	for(int i = 1 ; i <= N ; i ++){
		RET *= ret[i];
		RET %= M;
	}
	cout << RET << endl;
}



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

int main() {
  int N, L;
  cin >> N >> L;
  vector<string> S(N);
  for (int i=0; i<N; i++)
    cin >> S.at(i);
  sort(S.begin(), S.end());
  for (int i=0; i<N; i++)
    cout << S.at(i);
  cout << endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include <stdlib.h>
#include<string.h>
#include<math.h>
#define loop(i, l, r) for(i=l; i<r; i++)/*Instead of function, (for).*/
#define rep(i,r) for(i=0; i<r; i++)
#define Max(a, b) ((a) > (b) ? (a) : (b))
#define Min(a, b) ((a) < (b) ? (a) : (b))
typedef long long int lli;
/*Return Combination ,(nCr)*/
int combi(int n, int r)
{
	if(r==0 || r==n) return 1;
	else return combi(n-1,r) + combi(n-1,r-1);
}
/*Return gcd(a, b)*/
int gcd(int a, int b){
	if(b == 0) return a;
	else return gcd(b, a % b);
}
int main(void)
{
	lli n, a, b, c, d, ans;
	scanf("%lld%lld%lld", &n, &a, &b);
	if(a==0) ans = 0;
	c= n/(a+b);
	d = n%(a+b);
	if(0<=d && d<a) ans = c*a+d;
	if(a<=d && d<a+b) ans = c*a+a;
	printf("%lld", ans);
	return 0;
}

Measured memory_bytes: 128
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll x[111111];
ll dp[111111];
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	ll lmin=ll(1e18); 
	deque<pair<ll,ll> > rmin;
	int n; cin>>n; ll e,t; cin>>e>>t;
	x[0]=0;
	for(int i=1;i<=n;i++)
	{
		cin>>x[i];
	}
	int ptr=1;
	rmin.pb(mp(dp[0]-x[0]+t,1));
	for(int i=1;i<=n;i++)
	{
		while(ptr<=i&&x[i]>=t/2+x[ptr]+1)
		{
			if(!rmin.empty()&&rmin.front().se==ptr) rmin.pop_front();
			lmin = min(lmin, dp[ptr-1]-2*x[ptr]-x[ptr-1]);
			ptr++;
		}
		ll best=lmin;
		if(!rmin.empty()) best=min(best,-2*x[i]+rmin.front().fi);
		dp[i]=best+3LL*x[i];
		ll cost = dp[i]-x[i]+t;
		while(!rmin.empty()&&rmin.back().fi>=cost) rmin.pop_back();
		rmin.pb(mp(cost,i+1));
	}
	cout<<dp[n]+e-x[n];
}


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

#define for_(i,a,b) for(int i=a;i<b;++i)
#define for_rev(i,a,b) for(int i=a;i>=b;--i)
#define allof(a) a.begin(),a.end()
#define minit(a,b) memset(a,b,sizeof(a))
#define size_of(a) (int)a.size()

typedef long long lint;
typedef pair<int, int> pii;

int N, M, A, B, C, T;
int S[55];

typedef int mat_type;
typedef vector< mat_type > mArray;
typedef vector< mArray > mMatrix;

mMatrix operator * (const mMatrix& a, const mMatrix& b) {
	int n = size_of(a), m = size_of(b[0]), b_size = size_of(b);
	mMatrix res(n, mArray(m, 0));
	for_(i,0,n) for_(k,0,b_size) for_(j,0,m) {
		res[i][j] += a[i][k] * b[k][j];
		res[i][j] %= M;
	}
	return res;
}

mMatrix mMatrixI(int n) {
	mMatrix res(n, mArray(n, 0));
	for_(i,0,n) res[i][i] = 1;
	return res;
}

mMatrix POW(mMatrix& a, lint k) {
	int n = size_of(a);
	mMatrix res = mMatrixI(n);
	
	while (k > 0) {
		if (k & 1) res = res * a;
		a = a * a;
		k >>= 1;
	}
	
	return res;
}

void solve() {
	mMatrix ABC(N, mArray(N, 0));
	int p = -1;
	
	for_(i,0,N) {
		for_(j,0,3) {
			if (p + j < 0 || p + j >= N) continue;
			if (j == 0) ABC[i][p + j] = A;
			if (j == 1) ABC[i][p + j] = B;
			if (j == 2) ABC[i][p + j] = C;
		}
		p++;
	}
	/*
	for_(i,0,N) {
		for_(j,0,N) cout << ABC[i][j] << " ";
		cout << endl;
	}*/
	
	mMatrix ABCT = POW(ABC, T);
	/*
	for_(i,0,N) {
		for_(j,0,N) cout << ABC[i][j] << " ";
		cout << endl;
	}*/
	
	mMatrix ss(N, mArray(1, 0));
	for_(i,0,N) ss[i][0] = S[i];
	
	mMatrix ans = ABCT * ss;
	
	for_(i,0,N) {
		if (i < N - 1) cout << ans[i][0] << " ";
		else cout << ans[i][0] << endl;
	}
}

int main() {
	while (cin >> N >> M >> A >> B >> C >> T, N) {
		for_(i,0,N) cin >> S[i];
		solve();
	}
	return 0;
}

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

using namespace std;

#define lli long long int
#define REP(i,s,n) for(int i=s;i<n;i++)
#define MOD 1000000007
#define NUM 2520
#define INF (1LL<<50)
#define DEBUG 0
#define mp(a,b) make_pair(a,b)
#define SORT(V) sort(V.begin(),V.end())

void show(set<lli> &s){
	for(auto e: s){
		cout<<e<<" ";
	}
	cout<<endl;
}

signed main(){

	lli n,k;
	cin>>n>>k;

	vector<lli> p(n);
	REP(i,0,n)cin>>p[i];

	lli ans = n - k + 1;

	/*最長単調増加列を計算する。*/
	vector<lli> d(n);
	lli cnt=0;
	d[0]=1;
	REP(i,0,n-1){
		if(p[i+1]>p[i]){
			d[i+1]=d[i]+1;
		}
		else d[i+1]=1;

		if(d[i+1] >= k)cnt++;
	}

	if(cnt>1)ans -= (cnt-1);

	/*2番目に配列の大きい数小さい数を確保する*/
	set<lli> s;
	for(lli i=0;i<k;i++)s.insert(p[i]);

	auto itr = s.begin();
	itr++;

	lli beforeSmall2nd = *itr;

	itr = s.end();
	itr--;
	lli beforeLarge = *itr;

	if(DEBUG)show(s);

	for(lli i=1;i<n-k+1;i++){
		if(DEBUG)cout<<"beforeSmall2nd = "<<beforeSmall2nd<<" beforeLarge = "<<beforeLarge<<endl;

		s.erase(p[i-1]);
		s.insert(p[i+k-1]);
		if(DEBUG)show(s);

		auto itr2 = s.begin();
		lli nowSmall = *itr2;

		itr2 = s.end();
		itr2--;
		itr2--;

		lli nowLarge2nd = *itr2;
		if(DEBUG)cout<<"nowSmall=" << nowSmall << "nowLarge2nd = "<<nowLarge2nd<<endl;
		if(beforeSmall2nd == nowSmall && beforeLarge == nowLarge2nd&& d[i+k-1]<k) ans--;

		auto itr3 = s.begin();
		itr3++;

		beforeSmall2nd = *itr3;

		itr3 = s.end();
		itr3--;
		beforeLarge = *itr3;

	}


	cout<<ans<<endl;



	return 0;
}

Measured memory_bytes: 12800
using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoder
{
    class Program
    {
        static List<List<int>> A;

        static void Main(string[] args)
        {
            //[summary]B - Bingo
            A = GetCard().ToList();
            var b = ReadLines();

            if (IsBingo(b))
            {
                Console.WriteLine("Yes");
            }
            else
            {
                Console.WriteLine("No");
            }

        }

        static bool IsBingo(List<int> b)
        {
            int count = 0;

            for(int i = 0; i < 3; i++)
            {
                count = 0;

                for(int j = 0; j < 3; j++)
                {
                    if (b.Contains(A[i][j]))
                    {
                        count++;
                    }
                }

                if (count == 3)
                {
                    return true;
                }
            }

            for (int i = 0; i < 3; i++)
            {
                count = 0;

                for (int j = 0; j < 3; j++)
                {
                    if (b.Contains(A[j][i]))
                    {
                        count++;
                    }
                }

                if (count == 3)
                {
                    return true;
                }
            }

            count = 0;

            for(int i = 0; i < 3; i++)
            {
                if (b.Contains(A[i][i]))
                {
                    count++;
                }
            }

            if (count == 3)
            {
                return true;
            }

            count = 0;

            for (int i = 0; i < 3; i++)
            {
                if (b.Contains(A[i][2 - i]))
                {
                    count++;
                }
            }

            if (count == 3)
            {
                return true;
            }

            return false;
        }

        static IEnumerable<List<int>> GetCard()
        {
            for (int i = 0; i < 3; i++)
            {
                yield return ReadLine();
            }
        }

        static List<int> ReadLine()
        {
            var line = Console.ReadLine();
            var arr = line.Split(' ');

            return arr.Select(x => int.Parse(x)).ToList();
        }

        static List<int> ReadLines(int count = 0)
        {
            //[summary]コンソールの値を読み込む
            var lines = new List<int>();
            string s;

            //読み込む行数が未指定のときは、1行目の値を"count"とみなす
            if (count == 0)
            {
                s = Console.ReadLine().TrimEnd();
                count = int.Parse(s);
            }

            for (int i = 0; i < count; i++)
            {
                s = Console.ReadLine().TrimEnd();
                lines.Add(int.Parse(s));
            }

            return lines;
        }
    }
}

Measured memory_bytes: 13396
#include <bits/stdc++.h>
using namespace std;
 
namespace TYC
{
	const int N = 2e5 + 5;
 
	int n, tot, C[N], Fa[N], M[N], R[N];
	vector<int> E[N];
	struct node {  int ls, rs, v; } tr[N * 150];
 
	int add(const int p, const int x, const int w, const int l = 1, const int r = n)
	{
		int o = ++tot;
		tr[o] = tr[p];
		if (l == r)
			return tr[o].v += w, o;
		int mid = (l + r) >> 1;
		if (x <= mid)
			tr[o].ls = add(tr[p].ls, x, w, l, mid);
		else
			tr[o].rs = add(tr[p].rs, x, w, mid + 1, r);
		tr[o].v = tr[tr[o].ls].v + tr[tr[o].rs].v;
		return o;
	}
 
	int merge(const int x, const int y, const int l = 1, const int r = n)
	{
		if (!x || !y)
			return x + y;
		int o = ++tot;
		if (l != r)
		{
			int mid = (l + r) >> 1;
			tr[o].ls = merge(tr[x].ls, tr[y].ls, l, mid);
			tr[o].rs = merge(tr[x].rs, tr[y].rs, mid + 1, r);
		}
		tr[o].v = tr[x].v + tr[y].v;
		return o;
	}
 
	int del(const int p, const int v, const int l = 1, const int r = n)
	{
		if (r <= v)
			return 0;
		if (l == r)
			return p;
		int o = ++tot, mid = (l + r) >> 1;
		if (v <= mid)
		{
			tr[o].ls = del(tr[p].ls, v, l, mid);
			tr[o].rs = tr[p].rs;
		}
		else
		{
			tr[o].ls = 0;
			tr[o].rs = del(tr[p].rs, v, mid + 1, r);
		}
		tr[o].v = tr[tr[o].ls].v + tr[tr[o].rs].v;
		return o;
	}
 
	int query(const int o, const int x, const int l = 1, const int r = n)
	{
		if (!o) 
			return 0;
		if (l == r)
			return tr[o].v;
		int mid = (l + r) >> 1;
		if (x <= mid)
			return query(tr[o].ls, x, l, mid);
		else
			return tr[tr[o].ls].v + query(tr[o].rs, x, mid + 1, r);
	}
 
	void dfs(const int u, const int f)
	{
		Fa[u] = f;
		M[u] = max(M[f], f);
		for (int v : E[u])
			if (v != f)
			{
				dfs(v, u);
				R[u] = merge(R[u], R[v]);
			}
		if (u != 1)
		{
			C[u] = query(R[u], M[u]) + 1;
			if (u < M[f])
				C[u] -= query(R[u], M[f]) + 1;
		}
		int t = query(R[u], u) + 1;
		R[u] = del(R[u], u);
		R[u] = add(R[u], u, t);
	}
 
	void dfs(const int u)
	{
		if (u != 1)
			C[u] += C[Fa[u]];
		for (int v : E[u])
			if (v != Fa[u])
				dfs(v);
	}
 
	void work()
	{
		scanf("%d", &n);
		for (int i = 1, u, v; i < n; i++)
		{
			scanf("%d%d", &u, &v);
			E[u].push_back(v);
			E[v].push_back(u);
		}
		for (int i = 1; i <= n; i++)
			sort(E[i].begin(), E[i].end());
		dfs(1, 0);
		dfs(1);
		for (int i = 2; i <= n; i++)
			printf("%d ", C[i]);
	}
}
 
int main()
{
	TYC::work();
	return 0;
}

Measured memory_bytes: 139764
#include<bits/stdc++.h>
#define p_ pair<int,int>
#define mp_ make_pair
#define ll long long
#define pb push_back
#define fi first
#define se second
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define show1(a) cout<<#a<<" = "<<a<<endl
#define show2(a,b) cout<<#a<<" = "<<a<<"; "<<#b<<" = "<<b<<endl
using namespace std;
const ll INF = 1LL<<60;
const int inf = 1<<30;
const int maxn = 2e5+5;
inline void fastio() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);}
int n,a[maxn];
map<ll,int> mp;
int main()
{
    fastio();
    cin>>n;
    rep(i,1,n) cin>>a[i];
    ll ans = 0;
    rep(i,1,n){
        ll y = i-a[i];
        if(mp[y]) ans += mp[y];
        ll x = i+a[i];
        mp[x]++;
    }
    cout<<ans<<endl;
    return 0;
}


Measured memory_bytes: 27060
def solve():
	arr = "zabcdefghijklmnopqrstuvwxy"
	N = int(input())
	ans = ""
	power = int(26**10)
	while N > 0:
		ans = arr[N % 26] + ans
		if (N % 26 == 0):
			N = N // 26
			N -= 1
		else:
			N = N // 26
	return ans


def main():
	# for _ in range(int(input())):
	print(solve())


if __name__ == '__main__':
	main()


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

int main(){
    int k;
    cin >> k;
    int l = 9*k;
    if(k%7==0){
        l = l/7;
    }
    ll num = 1;
    for(int i=1;i<=l;i++){
        num = (num%l)*10;
        if(num%l==1){
            cout << i << endl;
            return 0;
        }
    }
    cout << -1 << endl;
    return 0;
}

Measured memory_bytes: 3644
import std.stdio, std.string, std.conv;
import std.array, std.algorithm, std.range;
import std.math;

void main()
{
    foreach(q;stdin.byLine().map!(to!real).array().until(-1))
    {
        immutable EPS = 0.00001*q;
        auto x=q/2;
        while(abs(x^^3-q)>=EPS) x-=(x^^3-q)/(3*x^^2);
        writefln("%.6f",x);
    }
}

Measured memory_bytes: 1136
#include <bits/stdc++.h>
#define GET_MACRO(_1,_2,_3,_4,_5,_6,_7,_8,NAME,...) NAME
#define pr(...) cerr<< GET_MACRO(__VA_ARGS__,pr8,pr7,pr6,pr5,pr4,pr3,pr2,pr1)(__VA_ARGS__) <<endl
#define pr1(a) (#a)<<"="<<(a)<<" "
#define pr2(a,b) pr1(a)<<pr1(b)
#define pr3(a,b,c) pr1(a)<<pr2(b,c)
#define pr4(a,b,c,d) pr1(a)<<pr3(b,c,d)
#define pr5(a,b,c,d,e) pr1(a)<<pr4(b,c,d,e)
#define pr6(a,b,c,d,e,f) pr1(a)<<pr5(b,c,d,e,f)
#define pr7(a,b,c,d,e,f,g) pr1(a)<<pr6(b,c,d,e,f,g)
#define pr8(a,b,c,d,e,f,g,h) pr1(a)<<pr7(b,c,d,e,f,g,h)
#define prArr(a) {cerr<<(#a)<<"={";int i=0;for(auto t:(a))cerr<<(i++?", ":"")<<t;cerr<<"}"<<endl;}
using namespace std;
using Int = long long;
using _int = int;
using ll = long long;
using Double = long double;
const Int INF = (1LL<<60)+1e9; // ~ 1.15 * 1e18
const Int mod = (1e9)+7;
const Double EPS = 1e-8;
const Double PI = 6.0 * asin((Double)0.5);
using P = pair<Int,Int>;
template<class T> T Max(T &a,T b){return a=max(a,b);}
template<class T> T Min(T &a,T b){return a=min(a,b);}
template<class T1, class T2> ostream& operator<<(ostream& o,pair<T1,T2> p){return o<<"("<<p.first<<","<<p.second<<")";}
template<class T1, class T2, class T3> ostream& operator<<(ostream& o,tuple<T1,T2,T3> t){
  return o<<"("<<get<0>(t)<<","<<get<1>(t)<<","<<get<2>(t)<<")";}
template<class T1, class T2> istream& operator>>(istream& i,pair<T1,T2> &p){return i>>p.first>>p.second;}
template<class T> ostream& operator<<(ostream& o,vector<T> a){Int i=0;for(T t:a)o<<(i++?" ":"")<<t;return o;}
template<class T> istream& operator>>(istream& i,vector<T> &a){for(T &t:a)i>>t;return i;}



signed main(){
  srand((unsigned)time(NULL));
  cin.tie(0);
  ios_base::sync_with_stdio(0);
  cout << fixed << setprecision(12);

  Int n, t;
  cin>>n>>t;
  vector<Int> h(n);
  cin>>h;

  vector<Int> ans(n);
  ans[0] = t / h[0];
  Int sum = h[0];
  Int t2 = t % h[0];
  Int mx = h[0];
  for(Int i=1;i<n;i++){
    if(mx < h[i]){
      ans[i] = (t - sum) / h[i];
      t2 = (t - sum) % h[i];
      mx = h[i];
    }
    else {
      ans[i] = ans[i-1];
      //pr(i, ans[i], t2, h[i]);
      if(t2 < h[i]) ans[i]--, t2 = mx - (h[i] - t2);
      else t2 -= h[i];
    }
    sum += h[i];
  }
    

  for(Int i=0;i<n;i++) cout<<max(1LL, ans[i]+1)<<endl;    
  
  return 0;
}



Measured memory_bytes: 4420