akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n,m;
  cin >> n >> m;
  
  int a = 0;
  int b = 100009;
  for(int i = 0 ; i < m ; i++){
    int c,d;
    cin >> c >> d;
    a = max(a,c);
    b = min(b,d);
  }
  
  if(b-a+1 <= 0){
    cout << 0 << endl;
  }
  else{
    cout << b-a+1;
  }
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main {
	public static void main(String [] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int r = sc.nextInt();

		if(n < 10) {
			System.out.println(100 * (10 - n) + r);
		}else {
			System.out.println(r);
		}
		sc.close();
	}
}


Measured memory_bytes: 23124
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <functional>

using namespace std;

int main() {
	int n, m1, m2;
	while (cin >> n >> m1 >> m2) {
		if (n == 0 && m1 == 0 && m2 == 0) {
			break;
		}
		vector<int> p(n);
		for (int i = 0; i < n; i++) {
			cin >> p[i];
		}
		int ans = m1;
		int ansn = p[m1-1]-p[m1];
		for (int i = m1; i <= m2; i++) {
			if (p[i-1] - p[i] >= ansn) {
				ansn = p[i-1] - p[i];
				ans = i;
			}
			//cout << ans << ' ' << ansn << endl;
		}
		cout << ans << endl;
	}
	return 0;
}

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

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

        int n;
        cin >> n;
        cout << (n / 1000 + (n % 1000 != 0)) * 1000 - n;

        return 0;
}


Measured memory_bytes: 3644
#include<iostream>
#include<numeric>
#include<queue>
using namespace std;
#define ll long long

int main() {
  ll N, M, a, retval = 0;
  cin >> N >> M;
  std::priority_queue<ll> A;
  while (cin >> a) A.push(a);
  for (ll i = 0; i < M; ++i) {
    A.push(A.top()/2);
    A.pop();
  }
  for (ll j = 0; j < N; ++j) {
    retval += A.top();
    A.pop();
  }
  cout << retval << endl;
}


Measured memory_bytes: 1400
#include <stdio.h>
#include <string.h>

int main(void)
{
    int wall[5][5][4];
    int i, j;
    int x, y, d;
    int dx[] = {1, 0, -1, 0};
    int dy[] = {0, 1, 0, -1};

    memset(wall, 0, sizeof(wall));
    for (i = 0; i < 5; i++){
        char s[8];
        scanf("%s", s);
        for (j = 0; j < 4; j++)
            wall[i][j][0] = wall[i][j + 1][2] = (s[j] == '1');
        if (i == 4)
            break;
        scanf("%s", s);
        for (j = 0; j < 5; j++)
            wall[i][j][1] = wall[i + 1][j][3] = (s[j] == '1');
    }
    x = y = d = 0;
    do {
        putchar("RDLU"[d]);
        x += dx[d];
        y += dy[d];

        if (wall[y][x][d + 3 & 3])
            d = d + 3 & 3;
        else if (!wall[y][x][d])
            if (wall[y][x][d + 1 & 3])
                d = d + 1 & 3;
            else
                d = d + 2 & 3;
    } while (x + y + d);
    puts("");
    return (0);
}

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

ll mod = 998244353;

class BIT{
    public:
    int size;
    vector<int> tree;
    
    void set(int n){
        size = n;
        tree = vector<int>(n+1, 0);
        return;
    }
    
    void add(int n, int a) {
        int x = n;
        while (x <= size){
            tree[x] += a;
            x += (x & -x);
        }
        return;
    }
    
    int sum(int n) {
        int x = n;
        int sum = 0;
        while (x > 0) {
            sum += tree[x];
            x -= (x & -x);
        }
        return sum;
    }
    
};

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> points(N);
    vector<int> xs(N), ys(N);
    for (int i = 0; i < N; i++) {
        cin >> xs[i] >> ys[i];
        points[i] = {xs[i], ys[i]};
    }
    sort(points.begin(), points.end());
    sort(ys.begin(), ys.end());
    for (int i = 0; i < N; i++) {
        points[i].second = distance(ys.begin(), lower_bound(ys.begin(), ys.end(), points[i].second))+1;
    }
    
    BIT bit;
    bit.set(N+2);
    
    ll ans = 0;
    
    vector<ll> pow2(N+2, 1);
    for (int i = 1; i <= N; i++) pow2[i] = pow2[i-1]*2%mod;
    
    for (int i = 0; i < N; i++) {
        int y = points[i].second;
        int ss = bit.sum(y), sb = i - ss;
        int bs = y - 1 - ss, bb = N - y - (i - ss);
        ans += (pow2[ss]-1) * (pow2[bb]-1) % mod * (pow2[sb] + pow2[bs] - 1) % mod;
        ans += (pow2[sb]-1) * (pow2[bs]-1) % mod * (pow2[ss] + pow2[bb] - 1) % mod;
        ans += (pow2[sb]-1) * (pow2[bs]-1) % mod * (pow2[ss] - 1)  % mod * (pow2[bb] - 1) % mod;
        ans += pow2[N-1];
        ans %= mod;
        bit.add(y, 1);
    }
    
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
using namespace std;
 
#pragma GCC optimize("O3")
#define MOD 1000000007
#define pb push_back
#define fi first
#define se second
#define fr front()
#define ba back()
#define tp top()
#define mem(x,n) memset(x,n,sizeof(x));
#define sz(x) (int)((x).size())
#define all(x) (x).begin(),(x).end()
#define foreach(it,l) for(auto it=l.begin();it!=l.end();it++)
#define pnl printf("\n")
#define len(x) x.length()
 
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
typedef pair<pii,int> piii;
const int inf=(1<<30);
const LL llinf=(1ll<<60);
const double eps=(1e-10);
//const double pi=2*acos(0.0);
//const double GOLD=((1+sqrt(5))/2);
const int xx[8]={1,0,-1,0,1,-1,1,-1};
const int yy[8]={0,1,0,-1,-1,1,1,-1};
 
/* \( ·w·)~ Clapie ~(·w· )/ */
 
int n,W;
LL wei[105],val[105];
LL memo[105][100005];
 
void LCS(string a,string b){
	int n=len(a);
	int m=len(b);
	
	int arr[n+1][m+1]={0};
	for(int i=0;i<=n;i++){
		for(int j=0;j<=m;j++){
			if(i==0||j==0) arr[i][j]=0;
			else if(a[i-1]==b[j-1]) arr[i][j]=arr[i-1][j-1]+1;
			else arr[i][j]=max(arr[i-1][j],arr[i][j-1]);
		}
	}
	
	string ans;
	int i=n,j=m;
	while(i>0&&j>0){
		if(a[i-1]==b[j-1]) ans+=a[i-1],i--,j--;
		else if(arr[i-1][j]>arr[i][j-1]) i--;
		else j--;
	}
	reverse(all(ans));
	cout<<ans<<endl;
}
 
int main(){
	mem(memo,-1);
	string s,s1;
	cin>>s>>s1;
	LCS(s,s1);
}

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

int main(){

  char b;
  cin >> b;
  
  switch(b){
    case('A'):
      cout << 'T' << endl;
      break;  
    case('C'):
      cout << 'G' << endl;
      break;
    case('G'): 
      cout << 'C' << endl;
      break;
    case('T'): 
      cout << 'A' << endl;
  }
  
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int n,m,js,js1,js2;
int a[110];
vector<int>ans;
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d",&a[i]);
		if(a[i]&1){
			if(js1)js2=a[i];
			else js1=a[i];
			js++;
		}	
		else ans.push_back(a[i]);
	}
	if(js>2){
		cout<<"Impossible"<<endl;
		return 0;
	}
	if(n==1){
		cout<<1<<endl;
		cout<<1<<endl;
		cout<<1<<endl;
		return 0; 
	}
	if(m==1){
		cout<<n<<endl;
		cout<<2<<endl;
		cout<<1<<" "<<n-1<<endl;
		return 0;
	}
	for(int i=1;i<=m;i++){
		if(a[i]&1){
			if(i==1||i==m)continue;
			if(a[1]%2==0){
				swap(a[i],a[1]);
			}
			else if(a[m]%2==0){
				swap(a[i],a[m]);
			}
		}
	}
	for(int i=1;i<=m;i++)cout<<a[i]<<" ";
	a[1]++;a[m]--;
	cout<<endl;
	if(a[m]==0)m--;
	cout<<m<<endl;
	for(int i=1;i<=m;i++)cout<<a[i]<<" ";
	return 0;
}
/*
*/

Measured memory_bytes: 256
'use strict'

function main(input) {
  const inputList = input.split('\n');
  const n = parseInt(inputList[0])
  const l = inputList[1].split(' ').map(i => parseInt(i))

  const max = l.reduce((a,b) => a>b ? a : b)
  let sum = 0
  for (let i=0; i<n; i++) {
    sum += l[i]
  }
  sum -= max

  if (max < sum) {
    console.log('Yes')
  } else {
    console.log('No')
  }
 
}

main(require("fs").readFileSync("/dev/stdin", "utf8"));

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

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vector<int> > vii;

bool is_uruu(int y) {return (y % 4 == 0 && (y % 100 != 0 || y % 400 == 0));}
template <class X> void print(X Target){ cout << Target << '\n'; }

struct PRO{
  int num;
  int t;
};

bool comp(PRO lhs, PRO rhs)
{
  return (lhs.t < rhs.t);
}

signed main()
{
  ios::sync_with_stdio(false);
  int n;

  while (cin >> n, n){
    vector<PRO> rank;
    REP(i, n){
      int c, m1, s1, m2, s2, m3, s3, m4, s4;
      cin >> c >> m1 >> s1 >> m2 >> s2 >> m3 >> s3 >> m4 >> s4;
      rank.pb((PRO){c, (m1 + m2 + m3 + m4) * 60 + s1 + s2 + s3 + s4});
    }
    sort(rank.begin(), rank.end(), comp);
    print(rank[0].num);
    print(rank[1].num);
    print(rank[rank.size() - 2].num);
  }

  return (0);
}

Measured memory_bytes: 1332
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t,u;
  int a,b,ans(0);
  
  cin >> s >> t >> a >> b >> u;
  
  if(s == u){
    a--;
  }else if(t == u){
    b--;
  }
  
  cout << a << " " << b << endl;
}

Measured memory_bytes: 256
#include<iostream>
using namespace std;
int main(){
	
	int a,b,number=0,count=0;
	cin>>a>>b;
	
	
	if(b==1)
	 cout<<0;
	 else{
		 
		while(number<b){
			if(number+a<b){
				
				number+=(a-1);
			
			}
			else{
			
				number+=a;
			
			}
			count++;
		}
		cout<<count;
	}
    
}




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

using lli = long long int;

template <class T>ostream &operator<<(ostream &o,const vector<T>&v)
{o<<"{";for(int i=0;i<(int)v.size();i++)o<<(i>0?", ":"")<<v[i];o<<"}";return o;}

template <class T>ostream &operator<<(ostream &o,const pair<T, T>&p)
{o<<"("<<p.first<<", "<<p.second<<")";return o;}

#define rep(i, n) for(lli i = 0; i < (lli)(n); i++)

const lli MOD = 1000000007LL;

lli modpow(lli a, lli n){
    lli res = 1;

    for(lli ai = a; n; n>>=1){
        if(1&n) res = (res*ai)%MOD;
        ai=(ai*ai)%MOD;
    }
    return res;
}

lli inv(lli n){
    return modpow(n, MOD-2);
}

lli modperm(lli n, lli k){
    lli res = 1;
    rep(i, k){
        res = (res*(n-i))%MOD;
    }
    return res;
}

lli modcomb(lli n, lli k){
    return (modperm(n, k)*inv(modperm(k, k)))%MOD;
}

lli posmod(lli n){
    lli res = n;
    res %= MOD;
    if(res < 0) res += MOD;
    return res;
}
int n, m;
int a[10];
int ai, bi;
bool path[10][10];
int res = 0;

int main(void){
    cin >> n >> m;
    rep(i,m){
        cin >> ai >> bi;
        path[ai][bi] = true;
        path[bi][ai] = true;
    }
    rep(i, n){
        a[i] = i+1;
    }
    res = 0;
    do{
        bool f = true;
        rep(i, n-1){
            if(path[a[i+1]][a[i]] == false) f = false;
        }
        if(f) res++;
    }while(next_permutation(a+1, a+n));
    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
use proconio::{input, fastout};

#[fastout]
fn main() {
    input! {
        n: usize,
        ff: [[usize; 10]; n],
        pp: [[isize; 11]; n],
    }

    let mut max_profit = std::isize::MIN;

    for i in 1..1<<10 {
        let mut profit = 0;
        for (f, p) in ff.iter().zip(pp.iter()) {
            let f_num = bit_to_num(f);
            let count = f_num & i;
            let count = count.count_ones();
            profit += p[count as usize];
        }
        max_profit = std::cmp::max(max_profit, profit);
    }

    println!("{}", max_profit);
}

fn bit_to_num(v: &[usize]) -> usize {
    let mut num = 0;
    for i in v.iter().rev() {
        num *= 2;
        num += i;
    }
    num
}


Measured memory_bytes: 2196
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>
#include <vector>
#include <queue>
#include <functional>
#include <string>
#include <stack>
#include <set>
#include <sstream>
#include <iomanip>
#include <limits>
#include <cstring>

using namespace std;
using ll = long long;
typedef unsigned long long ull;
typedef pair<ll, ll> P;
typedef pair<string, string> sP;
typedef pair<ll, pair<ll, ll>> PP;

const ll mod = 1e4;
const ll MOD = 1e9 + 7;
const ll MOD2 = 998244353;
const ll INF = 1 << 30;
const ll INF2 = 9e18;
const double INF3 = 9e14;
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 };
const int tx[8] = { -1,0,1,-1,1,-1,0,1 }, ty[8] = { -1,-1,-1,0,0,1,1,1 };
#define ALL(x) (x).begin(),(x).end()
#define ALLR(x) (x).rbegin(),(x).rend()
#define pb push_back
#define eb emplace_back
#define fr first
#define sc second



int main() {
	ll n, k, ans = 0;
	cin >> n >> k;
	for (int i = k + 1;i <= n;i++) {
		ll p = n / i;
		ans += p*max(0LL, i - k);
		ans += max(0LL, n - p * i - k + 1);
	}
	if (k == 0)ans -= n;
	cout << ans << endl;
	return 0;
}

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

// #undef DEBUG  // Uncomment this line to forcefully disable debug print.
#if DEBUG
template <typename T>
void debug(T value) {
  std::cerr << value;
}
template <typename T, typename... Ts>
void debug(T value, Ts... args) {
  std::cerr << value << ", ";
  debug(args...);
}
#define dbg(...)                              \
  do {                                        \
    cerr << #__VA_ARGS__ << ": ";             \
    debug(__VA_ARGS__);                       \
    cerr << " (L" << __LINE__ << ")" << endl; \
  } while (0)
#else
#define dbg(...)
#endif

void read_from_cin() {}
template <typename T, typename... Ts>
void read_from_cin(T& value, Ts&... args) {
  std::cin >> value;
  read_from_cin(args...);
}
#define in(type, ...) \
  type __VA_ARGS__;   \
  read_from_cin(__VA_ARGS__);

template <typename T>
void write_to_cout(const T& value) {
  std::cout << value << std::endl;
}
template <typename T, typename... Ts>
void write_to_cout(const T& value, const Ts&... args) {
  std::cout << value << ' ';
  write_to_cout(args...);
}
#define out(...) write_to_cout(__VA_ARGS__);

#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)

using ll = long long;

using namespace std;

double e[600];
double p[600];

int main() {
  in(int, n, m);
  vector<vector<int>> from(n);
  vector<vector<int>> to(n);
  rep(i, m) {
    in(int, s, t);
    --s, --t;
    from[t].push_back(s);
    to[s].push_back(t);
  }
  assert(to[n - 1].empty());
  for (int i = n - 1; i >= 0; --i) {
    for (int j : to[i]) {
      e[i] += (e[j] + 1) / to[i].size();
    }
    dbg(i, e[i]);
  }
  assert(from[0].empty());
  p[0] = 1;
  for (int i = 0; i < n; ++i) {
    dbg(i, p[i]);
    for (int j : to[i]) {
      p[j] += p[i] / to[i].size();
    }
  }
  double maxi = 0;
  for (int i = 0; i < n; ++i) {
    const vector<int>& t = to[i];
    if (t.size() <= 1) continue;
    double sum = 0;
    for (int j : t) sum += e[j];
    for (int j : t) {
      double diff = p[i] * (sum / t.size() - (sum - e[j]) / (t.size() - 1));
      maxi = max(maxi, diff);
    }
  }
  cout << setprecision(10) << fixed;
  out(e[0] - maxi);
}


Measured memory_bytes: 6120
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int INF = int(1E9);
int arr[MAXN + 5], sum[MAXN + 5], temp[MAXN + 5];
long long tot1 = 0, tot2 = 0;
int N;
void MergeSort(int le, int ri) 
{
    if( le == ri ) return ;
    int mid = (le + ri) >> 1;
    MergeSort(le, mid);
    MergeSort(mid+1, ri);
    int p = le, q = mid+1, r = le;
    while( p <= mid && q <= ri ) 
	{
        if( sum[p] < sum[q] ) temp[r++] = sum[p++];
        else 
		{
            tot1 += (p-le);
            temp[r++] = sum[q++];
        }
    }
    while( p <= mid ) temp[r++] = sum[p++];
    while( q <= ri ) 
	{
        tot1 += (p-le);
        temp[r++] = sum[q++];
    }
    for(int i=le;i<=ri;i++) sum[i] = temp[i];
}
bool Check(int x) 
{
    tot1 = 0;
    for(int i=1;i<=N;i++) sum[i] = (arr[i] <= x ? 1 : -1);
    for(int i=1;i<=N;i++) sum[i] += sum[i-1];
    MergeSort(0, N);
    return tot1 >= (tot2/2 + 1);
}
int main() 
{
    int le = INF, ri = -INF;
    scanf("%d", &N);
    for(int i=1;i<=N;i++) 
	{ 
        scanf("%d", &arr[i]);
        le = min(le, arr[i]);
        ri = max(ri, arr[i]);
        tot2 += i;
    }
    while( le < ri ) 
	{
        int mid = (le + ri) >> 1;
        if( Check(mid) ) ri = mid;
        else le = mid + 1;
    }
    printf("%d\n", ri);
}

Measured memory_bytes: 1408
#include <bits/stdc++.h>
#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i, s, n) for (int i = s; i < (n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
typedef pair<int, int> pint;
typedef pair<ll, ll> pll;
const ll MOD = 1000000007;
const ll INF = MOD * MOD;
const int inf = (1<<29);

int main() {

    int N, K;
    cin >> N >> K;
    
    int cnt = 0;

    vector<int> h(N);
    REP(i, N) {
        cin >> h[i];
        if (h[i] >= K) cnt++;
    }

    cout << cnt << endl;
    

    return 0;
}

Measured memory_bytes: 640
#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long int ulli;
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
/* TUMSE NAA HO PAAYEGA HAR DO DIN MAI LAGEGA
   LEKIN RUKNE KA NAHI :P */

int main() {
	// your code goes here
	FASTIO
	int n;
	cin >> n;
	int ans=0;
	for(int i=1;i<n;i++)
	    ans+=((n-1)/i);
	cout << ans;
	return 0;
}


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

#define ll long long int
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define sep(i,b,a) for(ll i=b-1;i>=a;i--)
#define hell (ll)(1e9+7)

using namespace std;

void solve()
{
    ll n,k;
    cin>>n>>k;
    vector <ll> a(n),dp(n,INT_MAX);
    rep(i,0,n)
        cin>>a[i];
    dp[0]=0;
    rep(i,1,n)
    {
        rep(j,max((ll)0,i-k),i)
        {
            dp[i]=min(dp[i],dp[j]+abs(a[i]-a[j]));
        }
    }
    cout<<dp.back()<<"\n";
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll t;
    //cin>>t;
    t=1;
    while(t--)
    {
        solve();
    }
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<string>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<list>
#include<cstdint>
#include<bits/stdc++.h>
#include<queue>
#include<set>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define rep_r(i, n) for(int i = n-1; i >= 0; i--)
#define rep1(i, n) for(int i = 1; i <= (int)(n); i++)
#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define SZ(x) ((ll)(x).size())
#define bit(n) (1LL<<(n))
#define UNIQUE(v) v.erase( unique(v.begin(), v.end()), v.end() );

#define INF bit(60)
#define pb push_back
#define mod 1000000007

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

using namespace std;
using uif=uint_fast64_t;
using ll=long long int;

int qp(int a,ll b){int ans=1;do{if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;}while(b>>=1);return ans;}
int qp(int a,ll b,int mo){int ans=1;do{if(b&1)ans=1ll*ans*a%mo;a=1ll*a*a%mo;}while(b>>=1);return ans;}

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};


#define FACSIZE 2002

ll invfac[FACSIZE];
ll fac[FACSIZE];

ll mod_pow(ll ,ll );
ll mod_add(ll ,ll );
ll mod_mul(ll ,ll );
ll mod_div(ll ,ll );
void make_fact(ll );
void make_invfact(ll );



int main(void){

  ll n,k;
  cin>>n>>k;
  vector<ll> a(n);
  vector<ll> s(n+1);
  vector<ll> m(n+1);
  s[0]=0;
  m[0]=0;
  rep(i,n) cin>>a[i];
  rep1(i,n){
    s[i]=a[i-1]+s[i-1];
    m[i]=(s[i]-i)%k;
  }
  /*
  for(auto x:s) cout << x << " ";
  cout << endl;
  for(auto x:m) cout << x << " ";
  cout << endl;
  */

  ll ans=0;
  unordered_map<ll,ll > um;
  for( ll i=0;i<=n;i++ ){

    ll x=m[i];
    //cout << x << endl;
    if(i>=k){
      ll de=m[i-k];
      um[de]--;
    }
    if(um.find(x)!=end(um)) ans+=um[x];

    um[x]++;
    

  }

  cout << ans << endl;

  return 0;

}

ll mod_pow(ll x,ll r){
  if(r==0) return 1;
  else if(r==1) return x%mod;
  else if(r%2==0){
    ll t=mod_pow(x,r/2)%mod;
    return t*t %mod;
  } 
  else{
    ll t=mod_pow(x,r/2)%mod;
    ll k= t*t %mod;
    return k*x%mod;
  } 
}
ll mod_add(ll a,ll b){
  return (a+b)%mod;
}

ll mod_mul(ll a,ll b){
  return (a*b)%mod;
}

ll mod_div(ll a,ll b){
  return mod_mul(a,mod_pow(b,mod-2));
}

void make_fact(ll n){
  fac[0]=1;
  rep(i,n){
    fac[i+1]=mod_mul(fac[i],i+1);
  }  
}

void make_invfact(ll n){
  invfac[n]= mod_pow( fac[n] ,mod-2);
  for(int i=n-1;i>=0;i--){
    invfac[i]=mod_mul(invfac[i+1],i+1);
  }

}


Measured memory_bytes: 13256
#include<bits/stdc++.h>
#define reg register
using namespace std;
int n,t,x,y;
int main()
{
    scanf("%d",&n);
    for(reg int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&t,&x,&y);
        if(x+y>t||!((x+y)&1)&&t&1||(x+y)&1&&!(t&1))return puts("No"),0;
    }
    puts("Yes");
    return 0;
}

Measured memory_bytes: 256
char r[99],g[99],d[99];main(c,i,j,k){for(;scanf("%s%s%s",r,g,d)>2;puts(""))for(i=j=k=0,c=g[j++];j<=strlen(g);)c==d[k]?k++,c=r[i++]:(putchar(c),c=g[j++]);exit(0);}

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

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

    int ans = 1;
    for (int i = 1; i*i <= m; i++) {
        if(m%i==0){
            if(m/i >= n) ans = max(ans, i);
            if(i >= n) ans = max(ans, m/i);
        }
    }

    cout << ans << endl;
    // printf("%d\n", N);
    return 0;
}

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

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> a(n), b(n), c(n);
	rep(i,n) cin >> a[i];
	rep(i,n) cin >> b[i];
	rep(i,n) cin >> c[i];
	sort(a.begin(), a.end());
	sort(c.begin(), c.end());
	ll ans = 0;
	rep(i,n){
		ll upp = upper_bound(a.begin(), a.end(), b[i]-1) - a.begin();
		ll low = n - (lower_bound(c.begin(), c.end(), b[i]+1) - c.begin());
		ans += upp * low;
	}
	cout << ans << endl;
	return 0;
}

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

int main(void) {
    int A, B;
    cin >> A >> B;

    int cnt = 0;

    while(A <= B) {
        int num[5] = {
            A % 10,
            (A / 10) % 10,
            (A / 100) % 10,
            (A / 1000) % 10,
            (A / 10000) % 10
        };
        if (num[0] == num[4] && num[1] == num[3]) cnt++;
        A++;
    }

    cout << cnt << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cstdlib>
#include <cmath>

using namespace std;

int main()
{
	int d, n, i=0, j;
	long long sum=0;
	cin >> d; cin >> n;

	d = pow(100, d);
	for(j=0; i<n; j++){
		sum += d;
		if (sum%(100*d))
			i++;
	}

	cout << j*d << endl;
	return 0;
}

Measured memory_bytes: 256
import java.io.BufferedInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.stream.IntStream;

public class Main{
	public static void main(String[]$) throws IOException{
		new Main().solve();
	}
	static FastScanner s=new FastScanner(System.in);
	static IntStream REPS(int v){return IntStream.range(0,v);}
	static IntStream REPS(int l,int r){return IntStream.rangeClosed(l,r);}
	static int gInt() throws IOException{return s.nextInt();}
	static long gLong() throws IOException{return s.nextLong();}
	static long gDouble() throws IOException{return s.nextLong();}

	private void solve() throws IOException{
		char[]v;
		{
			String in=s.next();
			if(!isPalindrome(in.replaceAll("x",""))) {
				System.out.println(-1);
				return;
			}
			v=in.toCharArray();
		}
		int l=0,r=v.length-1,c=0;

		for(;l<r;++l) {
			if(v[l]==v[r]) {
				--r;
			}else if(v[l]=='x'&&v[r]!='x') {
				++c;
			}else if(v[l]!='x'&&v[r]=='x') {
				--l;
				--r;
				++c;
			}
		}

		System.out.println(c);
	}

	boolean isPalindrome(String v) {
		for(int i=0;i<v.length();++i) {
			if(v.charAt(i)!=v.charAt(v.length()-1-i))
				return false;
		}
		return true;
	}

	static void yesno(boolean f) {
		yesno(f,"YES","NO");
	}
	static void yesno(boolean f,String yes,String no) {
		System.out.println(f?yes:no);
	}
}
class FastScanner{
	private final BufferedInputStream	in;
	private static final int			bufSize	=1<<16;
	private final byte					buf[]	=new byte[bufSize];
	private int							i		=bufSize;
	private int							k		=bufSize;
	private final StringBuilder			str		=new StringBuilder();

	FastScanner(InputStream in){
		this.in=new BufferedInputStream(in,bufSize);
	}
	int nextInt() throws IOException{
		return (int)nextLong();
	}
	long nextLong() throws IOException{
		int c;
		long x=0;
		boolean sign=true;
		while((c=nextChar())<=32)
			;
		if(c=='-'){
			sign=false;
			c=nextChar();
		}
		if(c=='+'){
			c=nextChar();
		}
		while(c>='0'){
			x=x*10+(c-'0');
			c=nextChar();
		}
		return sign?x:-x;
	}
	int nextChar() throws IOException{
		if(i==k){
			k=in.read(buf,0,bufSize);
			i=0;
		}
		return i>=k?-1:buf[i++];
	}
	String next() throws IOException{
		int c;
		str.setLength(0);
		while((c=nextChar())<=32&&c!=-1)
			;
		if(c==-1){
			return null;
		}
		while(c>32){
			str.append((char)c);
			c=nextChar();
		}
		return str.toString();
	}
	String nextLine() throws IOException{
		int c;
		str.setLength(0);
		while((c=nextChar())<=32&&c!=-1)
			;
		if(c==-1){
			return null;
		}
		while(c!='\n'){
			str.append((char)c);
			c=nextChar();
		}
		return str.toString();
	}
}

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

int sum(std::vector<int> &v, int from, int to);

int main(void)
{
    int n, m;
    std::cin >> n >> m;

    std::vector<int> v; v.reserve(n);
    for (int i = 0; i < n - 1; i++) {
        int tmp;
        std::cin >> tmp;
        v.push_back(tmp);
    }
    int current = 0;
    int total = 0;
    for (int i = 0; i < m; i++) {
        int tmp;
        std::cin >> tmp;
        total += sum(v, current, tmp);
        total %= 100000;
        current += tmp;
    }

    std::cout << total << std::endl;

    return 0;
}

int sum(std::vector<int> &v, int from, int n) {
    if (n < 0) {
        from += n;
        n = -n;
    }
    int total = v[from];
    for (int i = 1; i < n; i++) {
        total += v[from+i];
    }
    return total;
}

Measured memory_bytes: 3092
#!/usr/bin/env python3
import sys
from collections.abc import Iterable
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


def solve(R: int, G: int, B: int, N: int):
    ret = 0
    for r in range((N // R) + 1):
        rc = R * r
        for g in range((N // G) + 1):
            gc = G * g
            bc = N - rc - gc
            if (0 <= bc) and  (bc % B == 0):
                ret += 1
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    R = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    result = solve(R, G, B, N)
    if isinstance(result, Iterable):
        result = '\n'.join([str(v) for v in result])
    print(result)

if __name__ == '__main__':
    main()


Measured memory_bytes: 5752
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  for(int i=0;i<(n);++i)
#define REPr(i,n) for(int i=(n)-1;i>=0; --i)
#define FORq(i, m, n) for(int i = (m);i <= (n);++i)
#define SCD(n) scanf("%d",&n)
#define SCD2(m,n) scanf("%d%d",&m,&n)
#define SCD3(m,n,k) scanf("%d%d%d",&m,&n,&k)
#define SCLLD(n) scanf("%lld",&n)
#define SCLLD2(m,n) scanf("%lld%lld",&m,&n)
#define SCLLD3(m,n,k) scanf("%lld%lld%lld",&m,&n,&k)
#define PB push_back
#define MP make_pair
#define ARSCD(A,N) REP(i,N){SCD(A[i]);}
#define ARSCD1(A,N) FORq(i,1,N){SCD(A[i]);}
#define VSCD(v,N) REP(i,N){int x; SCD(x); v.PB(x);}
#define VSCLLD(v,N) REP(i,N){long long x; SCLLD(x); v.PB(x);}
#define PRINTD(n) printf("%d\n",n)
#define PRINTLLD(n) printf("%lld\n",n)
#define DEBUG printf("%s\n","debug")
#define fst first
#define snd second
#define SIN(x,S) (S.count(x) != 0)
using namespace std;
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector < VI > VVI;
typedef vector<long long> VL;
typedef long long ll;
typedef long long integer;
////////////////////////////////////////////////////////////////////
struct Vertex {
	// edge information
	vector<int> edges_to; //to vertex number
	vector<double> edges_cost; // edge cost
	
	//for dijkstra
	bool done; //conform or not
	double cost; // now cost
	int from;
	
	bool operator<(const Vertex& another) const { // priority --> min
        return another.cost < cost; // order(cost)
    }
	
	bool operator==(const Vertex& another) const {
        return another.cost == cost; // order(cost)
    }
};

int main(){
	struct Vertex v[1002];
	int xs,ys,xt,yt; SCD2(xs,ys); SCD2(xt,yt);
	int N; SCD(N);
	REP(i,N+2){
		v[i].done = false;
		v[i].cost = -1.0;
	}

	static int x[1002];
	static int y[1002];
	static int r[1002];
	x[0] = xs; y[0] = ys; r[0] = 0;
	x[N+1] = xt; y[N+1] = yt; r[N+1] = 0;
	REP(i,N){
		SCD(x[i+1]);
		SCD(y[i+1]);
		SCD(r[i+1]);
	}

	REP(i,N+2){
		REP(j,N+2){
			double xdist = (double)(x[i] - x[j]);
			double ydist = (double)(y[i] - y[j]);

			double dist = sqrt(xdist*xdist + ydist*ydist) - (double)(r[i] + r[j]);
			if (dist < 0) dist = 0;

			v[i].edges_to.PB(j);
			v[i].edges_cost.PB(dist);

		}
	}
	

	v[0].cost = (double)0; //start
	int donenum = 0;
	while(donenum < N+2){
		int minv;
		double minc = -1.0;
		REP(i,N+2){
			if (v[i].done) continue;
			if (v[i].cost < 0) continue;
			if (minc == -1.0){
				minc = v[i].cost;
				minv = i;
			}else if (minc > v[i].cost) {
				minc = v[i].cost;
				minv = i;
			}
		}

			v[minv].done = true;
			donenum++;

			REP(j,v[minv].edges_to.size()){
				int nto = v[minv].edges_to[j];
				double ncost = minc;
				if (v[nto].cost < 0){
					v[nto].cost = ncost + v[minv].edges_cost[j];
				}else{
					v[nto].cost = min(ncost + v[minv].edges_cost[j],v[nto].cost);
				}
			

			}

	}

	printf("%.10f\n",v[N+1].cost);

}


Measured memory_bytes: 12416
N,M=map(int,input().split())
L=[1]*N
S=[-1]*N
S[0]=1
for i in range(M):
	x,y=map(int,input().split())
	if S[x-1]==1:
		S[y-1]=1
	L[x-1]-=1
	L[y-1]+=1
	if L[x-1]==0:
		S[x-1]=-1
print(S.count(1))

Measured memory_bytes: 4596
X = int(input())
# = map(int, input().split())
# = list(map(int, input().split()))
A = [i**5 for i in range(200)]
B = [i**5 for i in range(200)]
# = [list(map(int, input().split())) for i in range(N)]

for i in range(200):
    for j in range(200):
        if A[i] + B[j] == X:
            print(int(A[i]**(1/5)), int(B[j]**(1/5)*(-1)))
            exit()
        if A[i] - B[j] == X:
            print(int(A[i]**(1/5)), int(B[j]**(1/5)))
            exit()


Measured memory_bytes: 9464
#include<bits/stdc++.h>
#define rep(i,N) for(int i=0;i<(N);i++)
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
using namespace std;
const long long MOD = 1e9 + 7;
const long long INF = 1e12;
const int inf = 1e9;
const int mod = 1e9+7;
typedef long long ll;
typedef pair<ll,int> P;
typedef set<int> S;
int main(){
    string s,t,u;
    int a,b;
    cin >> s >> t;
    cin >> a >> b;
    cin >> u;
    if(s==u) cout<<a-1<<" "<<b<<endl;
    else cout<<a<<" "<<b-1<<endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long 
#define ull unsigned long long 
#define ld long double
#define ui unsigned int 
using namespace std;

int main() {
	ll x,y;
	cin >> x>>y;
	cout << x * y << " " << (x * 2) + (y * 2)<<endl;
}



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

bool is_palindrome(string s) {
  int n = s.size() / 2;
  string t, w;
  t = s.substr(0, n);
  reverse(s.begin(), s.end());
  w = s.substr(0, n);
  return t == w;
}

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

  string s;
  cin >> s;
  string ans = (is_palindrome(s) && is_palindrome(s.substr(0, s.size() / 2))) ? "Yes" : "No";
  cout << ans << '\n';
  return 0;
}

Measured memory_bytes: 256
#pragma warning (disable :4996)
#include <bits/stdc++.h>
//#pragma GCC optimize(2)
using namespace std;
typedef long long ll;
const double PI = cos(-1.0);
const double eps = 1e-12;
#define For(i,n,m) for(int i=n;i<=m;++i)

ll a, b, c, d;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> a >> b >> c >> d;
	if (b >= c) cout << "Yes" << "\n";
	else {
		int xa = c / b;
		if (c % b) ++xa;
		int xb = a / d;
		if (a % d) ++xb;
		if (xa <= xb) cout << "Yes" << "\n";
		else cout << "No" << "\n";
	}
	return 0;
}




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

#define int long long
using ll = long long;
using ld = long double;
using intpair = pair<int, int>;
const int MOD = 1e9 + 7;
inline int mod (ll a, int m = MOD) { return (a % m + m) % m; }
struct Fast {Fast(){cin.tie(0);ios::sync_with_stdio(0);}} fast;

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define reps(i, n, m) for (int i = (int)(n); i <= (int)(m); i++)
#define ALL(obj) (obj).begin(), (obj).end()
#define rALL(obj) (obj).rbegin(), (obj).rend()
#define ceiv(a, b) ((ll)((a) + (b) - 1)/(ll)(b))

signed main(){
    int n, k;
    cin >> n >> k;
    vector<int> p(n);
    rep(i,n) cin >> p[i];
    sort(ALL(p));
    
    int ans = 0;
    rep(i,k){
        ans += p[i];
    }
    
    cout << ans << endl;
}

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

int main()
{
    int n;

    cin >> n;

    while (n)
    {
        if (n % 10 == 7)
        {
            cout << "Yes\n";
            return 0;
        }
        n/=10;
    }
    cout<<"No\n";
}

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

//#define int long long
typedef long long ll;

typedef unsigned long long ul;
typedef unsigned int ui;
const ll mod = 1000000007;
const ll INF = mod * mod;
const int INF_N = 1e+9;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
#define all(v) (v).begin(),(v).end()
typedef pair<ll, ll> LP;
typedef long double ld;
typedef pair<ld, ld> LDP;
const ld eps = 1e-12;
const ld pi = acos(-1.0);
//typedef vector<vector<ll>> mat;
typedef vector<int> vec;

//繰り返し二乗法
ll mod_pow(ll a, ll n, ll m) {
	ll res = 1;
	while (n) {
		if (n & 1)res = res * a%m;
		a = a * a%m; n >>= 1;
	}
	return res;
}

struct modint {
	ll n;
	modint() :n(0) { ; }
	modint(ll m) :n(m) {
		if (n >= mod)n %= mod;
		else if (n < 0)n = (n%mod + mod) % mod;
	}
	operator int() { return n; }
};
bool operator==(modint a, modint b) { return a.n == b.n; }
modint operator+=(modint &a, modint b) { a.n += b.n; if (a.n >= mod)a.n -= mod; return a; }
modint operator-=(modint &a, modint b) { a.n -= b.n; if (a.n < 0)a.n += mod; return a; }
modint operator*=(modint &a, modint b) { a.n = ((ll)a.n*b.n) % mod; return a; }
modint operator+(modint a, modint b) { return a += b; }
modint operator-(modint a, modint b) { return a -= b; }
modint operator*(modint a, modint b) { return a *= b; }
modint operator^(modint a, int n) {
	if (n == 0)return modint(1);
	modint res = (a*a) ^ (n / 2);
	if (n % 2)res = res * a;
	return res;
}

//逆元(Eucledean algorithm)
ll inv(ll a, ll p) {
	return (a == 1 ? 1 : (1 - p * inv(p%a, a)) / a + p);
}
modint operator/(modint a, modint b) { return a * modint(inv(b, mod)); }

const int max_n = 1 << 18;
modint fact[max_n], factinv[max_n];
void init_f() {
	fact[0] = modint(1);
	for (int i = 0; i < max_n - 1; i++) {
		fact[i + 1] = fact[i] * modint(i + 1);
	}
	factinv[max_n - 1] = modint(1) / fact[max_n - 1];
	for (int i = max_n - 2; i >= 0; i--) {
		factinv[i] = factinv[i + 1] * modint(i + 1);
	}
}
modint comb(int a, int b) {
	if (a < 0 || b < 0 || a < b)return 0;
	return fact[a] * factinv[b] * factinv[a - b];
}
using mP = pair<modint, modint>;

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




void solve() {
    string s; cin >> s;
    ll n = s.size();
    unordered_map<char, ll> m;
    rep(i, n){
        m[s[i]]++;
    }
    ll res = 0;
    for(auto p: m){
        res += p.second*(p.second-1)/2;
    }
    cout << n*(n-1)/2 + 1 - res << endl;
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  //cout << fixed << setprecision(10);
  //init_f();
  //init();
  //int t; cin >> t; rep(i, t)solve();
  solve();
//   stop
    return 0;
}


Measured memory_bytes: 7816
N, M = map(int, input().split())

graph = [[] for i in range(N)]
left = set()
right = set()
for i in range(M):
  l, r, d = map(int, input().split())
  l -= 1; r -= 1
  graph[l].append((r, d))
  graph[r].append((l, -d))
  left.add(l); right.add(r)

root = left - right
if M and len(root) == 0:
  print('No')
  quit()

X = [None] * N
while root:
  node = root.pop()
  X[node] = 0
  stack = [node]
  while stack:
    node = stack.pop()
    while graph[node]:
      child, d = graph[node].pop()
      if X[child] is None:
        X[child] = X[node] + d
        stack.append(child)
      elif X[child] != X[node] + d:
        print('No')
        quit()

print('Yes')

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

#define rep(i,n) for(ll (i)=0;(i)<(ll)(n);(i)++)
#define all(x) (x).begin(),(x).end()
#define MOD 1000000007LL
#define INF (1LL<<60LL)
#define int long long
typedef long long ll;

using namespace std;



signed main() {
	ll ans = 100000;
	ll n; cin >> n;
	rep(i, n) {
		ans = ll(ans * 1.05);
		if (ans % 1000 != 0) {
			ans = ans - ans % 1000 + 1000;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3016
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const long double PI = (acos(-1));
#define rep(i, x, n) for (int i = x; i < (int)(n); i++)
#define sc(x) scanf("%d",&x)
#define scll(x) scanf("%lld",&x)
int main(){
    int n, m, p, ac = 0, wa = 0; sc(n), sc(m);
    string s;
    vector<bool> check(n, false);
    vector<int> cnt(n,0);
    rep(i, 0, m){
        sc(p), cin >> s; p--;
        if (check[p]) continue;
        if (s == "WA") cnt[p] += 1;
        else check[p] = true, ac += 1, wa += cnt[p];
    }
    cout << ac << " " << wa << endl;
    return 0;
}

Measured memory_bytes: 640
#include<stdio.h>

int main(void){
    int D,N;
    scanf("%d%d",&D,&N);
    if (N == 100) N++;
    switch(D){
        case 0:
        printf("%d",1*N);
        break;
        case 1:
        printf("%d",1*100*N);
        break;
        case 2:
        printf("%d",1*100*100*N);
        break;
    }
    return 0;
}

Measured memory_bytes: 128
n, m, v, p = map(int, input().split())
a = sorted(list(map(int, input().split())), reverse=True)
ans = p
c = [0]
cnt = 0
for i in range(n):
  # 累積和
  cnt += a[i]
  c.append(cnt)
  
from bisect import bisect_right
for i in range(p,n):
  h = a[i]+m
  free = v - (p-1) - (n-i)
  if free >= 0 and h >= a[p-1]:
    d = h * (i-p+1) - (c[i]-c[p-1]) # 余裕
    if d >= free*m:
      ans += 1
  else:
    if h >= a[p-1]:
      ans += 1
print(ans)


Measured memory_bytes: 14480
N = int(input())

# あらかじめf(n)を計算しておく
f_arr = [0 for i in range(10**4 + 3)]


for x in range(1, 10**4):
    for y in range(x, 10**4):
        if x*y > 10**4:
            break

        for z in range(y, 10**4):
            n = x*x + y*y + z*z + x*y + y*z + z*x

            if n > 10**4:
                break

            if x == y and y == z:
                f_arr[n] += 1
            elif (x == y) or (y == z) or (z == x):
                f_arr[n] += 3
            else:
                f_arr[n] += 6

for i in range(1, N+1):
    print(f_arr[i])


Measured memory_bytes: 9196
n,m=map(int,input().split())
l=list(map(int,input().split()))
d={}
d_track={}

for i in range(n):
  d_track[i+1]=1
  d[i+1]=l[i]

#print(d_track,d)
for i in range(m):
  a,b=map(int,input().split())
  
  if d[a]<=d[b]:
    d_track[a]=0

  if d[b]<=d[a]:
    d_track[b]=0

ct=0
#print(d,d_track)
for i in range(n):
  if d_track[i+1]==1:
    ct+=1
print(ct)


Measured memory_bytes: 32992
#include<iostream>
#include<string>
using namespace std;
int main()
{

	int num;
	string s, week[7] = { "SUN","MON","TUE","WED","THU","FRI","SAT" };
	cin >> s;
	for (int i = 0; i < 7; i++)
	{
		if (s == week[i])
			 num = 7 - i;
	}
	cout << num << endl;
	return 0;
}

Measured memory_bytes: 256
using System;
using System.Linq;

namespace AOJ
{
  class Program
  {
    public static void Main(string[] args)
    {
      foreach (var x in Enumerable.Range(1, 9))
        foreach (var y in Enumerable.Range(1, 9))
          Console.WriteLine("{0}x{1}={2}", x, y, x * y);
    }
  }
}

Measured memory_bytes: 5760
#include <bits/stdc++.h>
#define rep(i, a) for(int i = 0; i < a; i++)
#define all(v) v.begin(), v.end()
#define dcout cout << fixed << setprecision(15)
#define arep(i, a) for(auto i : a)
#define F first
#define S second
#define VE vector<int>
#define pb(x) push_back(x)
#define MOD 1000000007
#define INF 10000000000
#define int long long
#define KETA(n) floor(log10(n) + 1)
using namespace std;
signed main() {
    string a, b, c;
    cin >> a >> b >> c;
    cout << (char)(a[0] - 32) << (char)(b[0] - 32) << (char)(c[0] - 32) << endl;
    return 0;
}

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

typedef long long ll;
typedef unsigned long long ull;

int main()
{
    ll N;
    cin >> N;
    ll res = 1;
    ll Ai;
    bool isZero = false;
    for(int i=0;i<N;i++){
        cin >> Ai;
        if(Ai == 0) isZero = true;
        if(res >= 0 && 2.e+18/Ai >= res){
            res *= Ai;
        }else{
            res = -1;
        }
        if(res > (ll)(1e+18)) res = -1;
    }
    if(isZero) cout << "0" << endl;
    else       cout << res << endl;

    return 0;
}

Measured memory_bytes: 3652
#include <bits/stdc++.h>
using namespace std;
int main()
{
  string w, s;
  int N;
  cin >> w >> N;
  int cnt = 0;
  for(int i = 0; i < N; i++) {
    cin >> s;s += s;
    cnt += s.find(w) != string::npos;
  }
  cout << cnt << endl;
  return 0;
}

Measured memory_bytes: 3128
# coding: utf-8
# Your code here!
n=int(input())
num=[0]
ans=0
count=0
k=1
for i in range(n):
    a=int(input())
    num.append(a)

for i in range(n+1):
    k=num[k]
    count+=1
    if k==2:
        ans=1
        break
if ans==1:
    print(count)
else:
    print("-1")


Measured memory_bytes: 7080
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
# define mod 1000000007
# define INF (1 << 29)
# define MAX_N 1000010
/* ちゃんと考えてわかって実装 */

int main(void){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    vector<int> X;
    vector<int> Y;
    for(int i=0; i<n; i++){
        int tmp_x;
        cin >> tmp_x;
        X.push_back(tmp_x);
    }
    for(int i=0; i<m; i++){
        int tmp_y;
        cin >> tmp_y;
        Y.push_back(tmp_y);
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    if(max(x, X[n-1]) < min(y, Y[0])) cout << "No War";
    else cout << "War";
    return 0;
}

Measured memory_bytes: 256
def solve(a, n, k):
    f = [0] * n
    f[1] = abs(a[1] - a[0])

    for i in range(2, n):
        f[i] = float('inf')
        for j in range(max(0, i - k), i):
            f[i] = min(f[i], f[j] + abs(a[i] - a[j]))

    return f[n-1]


def main():
    inp = lambda: [int(x) for x in input().split()]
    n, k = inp()
    a = inp()
    print(solve(a, n, k))


if __name__ == '__main__':
    main()



Measured memory_bytes: 55136
//I love Nanami Chiaki
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=5007;
const int mod=1e9+7;
struct Edge{
	int nxt,to;
}G[maxn<<1];
int bG=0,hG[maxn];
void add(int x,int y){
	G[bG].nxt=hG[x];G[bG].to=y;hG[x]=bG++;
	G[bG].nxt=hG[y];G[bG].to=x;hG[y]=bG++;
} 
int dp[maxn][maxn][2];
int fac[maxn],sz[maxn],n;
void init(){
	fac[0]=1;
	for (int i=2;i<maxn;i+=2) fac[i]=1ll*(i-1)*fac[i-2]%mod;
}
void solve(int v,int p){
	dp[v][1][0]=1;sz[v]=1;
	for (int i=hG[v];i!=-1;i=G[i].nxt){
		int u=G[i].to;if (u==p) continue;
		solve(u,v);
		for (int sz1=sz[v];sz1>0;sz1--){
			int cur[2]={dp[v][sz1][0],dp[v][sz1][1]};
			dp[v][sz1][0]=0;dp[v][sz1][1]=0;
			for (int e1=0;e1<=1;e1++){
				for (int sz2=1;sz2<=sz[u];sz2++){
					for (int e2=0;e2<=1;e2++){
						int nsz=sz1+sz2,ne=(e1+e2)%2;
						dp[v][nsz][ne]=(dp[v][nsz][ne]+1ll*cur[e1]*dp[u][sz2][e2]%mod)%mod;
						if (sz2%2==0){
							ne^=1;
							dp[v][sz1][ne]=(dp[v][sz1][ne]+1ll*cur[e1]*dp[u][sz2][e2]%mod*fac[sz2]%mod)%mod;
						}
					}
				}
			}
		}
		sz[v]+=sz[u];
	}
}
int main(){
	init();
	scanf("%d",&n);
	memset(hG,-1,sizeof(hG));
	for (int i=0;i<n-1;i++){
		int x,y;scanf("%d%d",&x,&y);x--;y--;add(x,y);
	}
	solve(0,-1);
	ll ans=0;
	for (int j=2;j<=n;j+=2){
		ans=(ans+1ll*fac[j]*dp[0][j][0])%mod;
		ans=(ans-1ll*fac[j]*dp[0][j][1]+mod)%mod;
	}
	printf("%lld\n",ans);
	return 0; 
}

Measured memory_bytes: 195072
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, Q = iim()
    A = [0] * (N+1)
    la = N + 1

    def add(i, x):
        while i < la:
            A[i] += x
            i += i & -i

    def getSum(i):
        ans = 0

        while i:
            ans += A[i]
            i -= i & -i

        return ans

    ans = []
    for com, *arg in (map(int, line.split()) for line in sys.stdin):
        if com == 0:
            add(*arg)
        else:
            #print("+", *arg)
            ans.append(getSum(arg[1]) - getSum(arg[0]-1))
        #print(A)
    print(*ans, sep="\n")


if __name__ == "__main__":
    resolve()



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

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

  vector<string> image(N);
  vector<string> piece(M);
  for(int i=0; i<N; i++){
    cin >> image.at(i);
  }
  for(int i=0; i<M; i++){
    cin >> piece.at(i);
  }

  for(int i1=0; i1<=N-M; i1++){
    for(int i2=0; i2<=N-M; i2++){
      bool is_matched= true;
      for(int t1=0; t1<M; t1++){
        for(int t2=0; t2<M; t2++){
          if(image.at(i1+ t1).at(i2+ t2)!=piece.at(t1).at(t2)){
            is_matched= false;
            break;
          }
        }
        if(!is_matched) break;
      }

      if(is_matched){
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
}

Measured memory_bytes: 256
#include<iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<cmath>
#include<math.h>
#include<algorithm>
#include<string.h>
#include <iomanip>
#include <sstream>
using namespace std;

int main() {
  long long  A, B;
  int ans = 0;

  cin >> A >> B;
  if((A+B)%2 == 0){
    cout << (A+B)/2 << endl;
  }else{
    cout << "IMPOSSIBLE" << endl;
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define endl "\n"
using namespace std;
typedef long long int lli;
lli dp[1<<21];
int main()
{
    ios::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);
    lli n;
    cin>>n;
    lli i,j,a[n][n],M=1e9+7;
    
    for(i=0;i<n;i++) for(j=0;j<n;j++) cin>>a[i][j];
    
    dp[0]=1;
    for(i=1;i<1<<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(i&(1<<j) && a[__builtin_popcount(i)-1][j])
                dp[i]=(dp[i]+dp[i^(1<<j)])%M;
        }
    }
    
    cout<<dp[(1<<n)-1];
    return 0;
}

Measured memory_bytes: 16640
# AOJ 0163 Highway Toll
# Python3 2018.6.23 bal4u

g = [ \
	[ 0,  6, 13, 18, 23, 43, 58], \
	[ 6,  0,  7, 12, 17, 37, 52], \
	[13,  7,  0,  5, 10, 30, 45], \
	[18, 12,  5,  0,  5, 25, 40], \
	[23, 17, 10,  5,  0, 20, 35], \
	[43, 37, 30, 25, 20,  0, 15], \
	[58, 52, 45, 40, 35, 15,  0]]

f = [ \
	[   0,  300,  500,  600,  700, 1350, 1650], \
	[ 300,    0,  350,  450,  600, 1150, 1500], \
	[ 500,  350,    0,  250,  400, 1000, 1350], \
	[ 600,  450,  250,    0,  250,  850, 1300], \
	[ 700,  600,  400,  250,    0,  600, 1150], \
	[1350, 1150, 1000,  850,  600,    0,  500], \
	[1650, 1500, 1350, 1300, 1150,  500,    0]]

while 1:
	d = int(input())-1
	if d < 0: break
	h, m = map(int, input().split())
	ti = h*100 + m
	a = int(input())-1
	h, m = map(int, input().split())
	to = h*100 + m
	fee = f[d][a]
	if g[d][a] <= 40 and ((1730 <= ti and ti <= 1930) or (1730 <= to and to <= 1930)):
		fee = ((fee//2 - 1)//50 + 1)*50
	print(fee)


Measured memory_bytes: 5616
S = input()

L = []

def rec(s) :
  L.append(s)
  
  for i in range(len(s)) :
    if s[i] == 'A' :
      rec(s[:i] + s[i+1:])

rec('AKIHABARA')

if S in L :
  print('YES')
else :
  print('NO')

Measured memory_bytes: 38256