akhauriyash/Code-Regression huggingface dataset:
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <cmath>
#include <map>
#include <queue>
#include <iomanip>
#include <set>
#include <tuple>
#define mkp make_pair
#define mkt make_tuple
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const ll MOD=1e9+7;
template<class T> void chmin(T &a,const T &b){if(a>b) a=b;}
template<class T> void chmax(T &a,const T &b){if(a<b) a=b;}

const ll INF=1e15;

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

  ll X;
  cin>>X;
  int K;
  cin>>K;
  vector<ll> R(K);
  rep(i,K) cin>>R[i];
  R.push_back(INF);
  int Q;
  cin>>Q;
  vector<ll> T(Q),A(Q);
  rep(i,Q) cin>>T[i]>>A[i];

  ll left=0,right=X;
  ll lval=0,rval=X;
  int now=0;
  vector<ll> ans(Q,-1);
  for(int i=0;i<R.size();i++){
      while(now<Q&&T[now]<R[i]){
          ll plus=T[now]-(i==0?0:R[i-1]);
          if(i%2==0) plus*=(-1);

          if(A[now]<=left) ans[now]=max(0ll,min(X,lval+plus));
          else if(A[now]>=right) ans[now]=max(0ll,min(X,rval+plus));
          else{
              ans[now]=max(0ll,min(X,lval+(A[now]-left)+plus));
          }
          now++;
      }

      ll d=R[i]-(i==0?0:R[i-1]);
      if(i%2==0){
          left+=max(0ll,d-lval);
          lval=max(0ll,lval-d);
          rval=max(0ll,rval-d);
      }else{
          right-=max(0ll,rval+d-X);
          rval=min(X,rval+d);
          lval=min(X,lval+d);
      }
      if(left>right){
          left=right;
          lval=rval;
      }
  }

  rep(i,Q) cout<<ans[i]<<endl;

  return 0;
}


Measured memory_bytes: 4336
import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int w = sc.nextInt();
		int h = sc.nextInt();
		int n = sc.nextInt();
		int [] [] arrayXY = new int [w] [h];
		int count = 0;

		//白い部分を0とする
		for (int i = 0; i < w; i++) {
			for(int j = 0; j < h; j++) {
				arrayXY[i][j] = 0;
			}
		}

		for (int k = 0; k < n; k++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			int N = sc.nextInt();

			switch (N) { //塗りつぶしたときの値は１
			case 1 : //ｘょり左側を塗りつぶす
				for(int i = 0; i < x; i++) {
					for(int j = 0; j < h; j++) {
						arrayXY[i][j] = 1;
					}
				}
				break;
			case 2 : //xより右側を塗りつぶす
				for(int i = x ; i < w; i++) {
					for(int j = 0; j < h; j++) {
						arrayXY[i][j] = 1;
					}
				}
				break;
			case 3 : //yより下側を塗りつぶす
				for(int i = 0; i < w; i++) {
					for(int j = 0; j < y; j++) {
						arrayXY[i][j] = 1;
					}
				}
				break;
			case 4 : //yより上側を塗りつぶす
				for(int i = 0; i < w; i++) {
					for(int j = y; j < h; j++) {
						arrayXY[i][j] = 1;
					}
				}
			}
		}
		for (int i = 0; i < w; i++) {
			for(int j = 0; j < h; j++) {
				if (arrayXY[i][j] == 0) {
					count++;
				}
			}
		}
		System.out.println(count);
	}
}


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

const double eps = 1e-10;

int dcmp(double x) {
        if(fabs(x) < eps) return 0;
        return x < 0 ? -1 : 1;
}

bool same(double a, double b) {return dcmp(a - b) == 0;}
#define Vector P
struct P {
        double x, y;
        P(double x = 0, double y = 0): x(x), y(y) {}
        P operator + (P b) {return P(x + b.x, y + b.y);}
        P operator - (P b) {return P(x - b.x, y - b.y);}
        P operator * (double b) {return P(x * b, y * b);}
        P operator / (double b) {return P(x / b, y / b);}
        double operator * (P b) {return x * b.x + y * b.y;} // Dot
        double operator ^ (P b) {return x * b.y - y * b.x;} // Cross
        double abs() {return hypot(x, y);}
        P unit() {return *this / abs();}
        P spin(double o) {
                double c = cos(o), s = sin(o);
                return P(c * x - s * y, s * x + c * y);
        }
};

struct Line {
        //ax + by + c = 0
        double a, b, c, theta;
        P pa, pb;
        Line(): a(0), b(0), c(0), theta(0), pa(), pb() {}
        Line(P pa, P pb): a(pa.y - pb.y), b(pb.x - pa.x), c(pa ^ pb), theta(atan2(-a, b)), pa(pa), pb(pb) {}
                P projection(P p) {return pa + (pb - pa).unit() * ((pb - pa) * (p - pa) / (pb - pa).abs());}
                P reflection(P p) {return p + (projection(p) - p) * 2;}
        double get_ratio(P p) {return (p - pa) * (pb - pa) / ((pb - pa).abs() * (pb - pa).abs());}
        P dis(P p) {return ((pb - pa) ^ (p - pa)) / (pb - pa).abs();} // directed distance
};

struct Circle {
        P c;
        double r;
        Circle(P c, double r = 0): c(c), r(r) {}
};
double dis(P a, P b) {return (a - b).abs();}
vector<P> ps;
double rotating(vector<P> ps, int id) {
        // ps must be convex and sorted by counterclockwise order, id is the rightmost point index
        int n = int(ps.size());
        int l = 0, r = id;
        double res = dis(ps[0], ps[r]);
        while(l < id || r < n - 1) {
                if(l < id && r < n - 1) {
                        Vector rvec = ps[r + 1] - ps[r];
                        Vector lvec = ps[l + 1] - ps[l];
                        if(dcmp(lvec ^ rvec) == -1) l++;
                        else r++;
                }
                else if(l == id) r++;
                else l++;
                res = max(res, dis(ps[l], ps[r]));
        }
        return res;
}
int main() {
        ios_base::sync_with_stdio(false); cin.tie(0);
        int n; cin >> n;
        for(int i = 0; i < n; i++) {
                P p; cin >> p.x >> p.y;
                ps.push_back(p);
        }
                int id = 0;
                for(int i = 1; i < n; i++)
                        if(dcmp(ps[i].x - ps[id].x) == 1) id = i;
                double ans = rotating(ps, id);
        cout << fixed << setprecision(12) << ans << '\n';
        return 0;
}


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

int main(){
    int r; cin >> r;
    cout << 2*M_PI*r << endl;
}

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

#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ALL(a) (a).begin(),(a).end()
#define Yes(hoge) cout<<((hoge)?"Yes":"No")<<endl;
#define YES(hoge) cout<<((hoge)?"YES":"NO")<<endl;
using namespace std;
struct Grid{int x,y,t;};
struct Edge{int to,cost;};
struct Graph{vector<vector<Edge>>E;int V;
  const ll Inf = llINF;const int MAX_V=1010;vector<ll>d;
  Graph(int n):E(n){d.resize(MAX_V);E.resize(n);V=n;}
  void init(){for(int i=0;i<MAX_V;i++)d[i]=Inf;}
  void add_edge(int from,int to,int cost){E[from-1].pb({to-1,cost});}
};
int main(){
  int n,m;cin>>n>>m;
  vector<ll>A(n);
  vector<ll>B(m);
  ll num=n*m;
  for(int i=0;i<n;i++){cin>>A[i];}
  for(int j=0;j<m;j++){cin>>B[j];}
  sort(ALL(A),greater<ll>());
  sort(ALL(B),greater<ll>());
  ll ans=1;
  for(int i=0;i<n-1;i++)if(A[i]==A[i+1])ans=0;
  for(int i=0;i<m-1;i++)if(B[i]==B[i+1])ans=0;
  ll apo=0,bpo=0;
  for(ll i=num;i>=1;i--){
    bool afl=false,bfl=false;
    if(apo<n&&A[apo]==i){
      afl=true;
      apo++;
    }
    if(bpo<m&&B[bpo]==i){
      bfl=true;
      bpo++;
    }
    if(afl&&bfl)continue;
    if(afl){
      ans*=bpo;
      ans%=MOD;
    }else if(bfl){
      ans*=apo;
      ans%=MOD;
    }else{
      ans*=max(0LL,apo*bpo-(num-i));
      ans%=MOD;
    }

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


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  char a[51];
  int i,n,c=0;
  scanf("%d",&n);
  scanf("%s",&a);
  for(i=0;i<n-2;i++)
    if(a[i]=='A'&&a[i+1]=='B'&&a[i+2]=='C')
      c++;
  printf("%d",c);
} 

Measured memory_bytes: 256
import * as fs from 'fs'

function solve() {
  const input = (require('fs').readFileSync('/dev/stdin', 'utf8') as string).split('\n');
  const N = +input[0]
  const A = input[1].split(' ').map((x: string):number => +x);
  let ans = 0;
  for (let a of A) {
    ans += 1 / a;
  }
  console.log(1 / ans)
}

solve();


Measured memory_bytes: 7372
/**
        Bismilla- hir rahma-nir rahi-m
    @uthor Md Hasibur Rahman (Evan)
                JKKNIU
*/


#include<bits/stdc++.h>
#define         ll              long long
#define         FI              freopen("input.txt","r",stdin)
#define         FO              freopen("output.txt","w",stdout)
#define         PrintCase(i)    printf("Case %d: ",i)
#define         sc(a)           scanf("%d",&a)
#define         scl(a)          scanf("%lld",&a)
#define         rep(i,n)        for(int i=0;i<n;i++)
#define         pb              push_back
#define         MAX             1000000
#define         fast            ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define		 endl			"\n"


using namespace std;

bool isPrime(ll a)
{
    for(ll i=2;i*i<=a;i++)
        if(a%i==0)
            return false;
    return true;
}






bool isPowerOfTwo(ll a)
{
    if(a==1)
        return true;
    if(a&1)
        return false;
    while(a)
    {
        a/=2;
        if(a!=1 && a&1)
            return false;
        if(a==1)
            return true;
    }
    return true;
}




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



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



ll power(ll base, ll exponent)
{
    ll ans = 1;
    for(ll i=1;i<=exponent;i++)
        ans*=base;
    return ans;
}




bool isPowerOfX(ll x, ll value)
{
    if(value==1)
        return true;
    while(value)
    {
        value/=x;
        if(value%x && value!=1)
            return false;
    }
    return true;
}






int main()
{
    fast;
    int t;
    cin>>t;
    t==0?cout<<1<<"\n":cout<<"0\n";
    return 0;
}


Measured memory_bytes: 3616
#include <stdio.h>
int main(void){
  int a, n, b;
  scanf("%d",&a);
  scanf("%d",&n);
  scanf("%d",&b);
  if(a*n > b){
    printf("%d",b);
  }
  else{
    printf("%d", a*n);
  }
  return 0;
}

Measured memory_bytes: 128
#include <iostream>
#include <iomanip>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <utility>
#include <tuple>
#include <algorithm>
#include <numeric>
#include <cstdio>
#include <cmath>
#define rep(i, n) for (int i = 0; i < (n); i++)
using namespace std;
using ll = long long;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

ll gcd(ll x, ll y) { return x%y ? gcd(y, x%y) : y; }

map<long long, int> prime_factor(long long n) {
  map<long long, int> res;
  for (long long i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      res[i]++;
      n /= i;
    }
  }
  if (n != 1) res[n] = 1;
  return res;
}

int main() {
  ll A, B;
  cin >> A >> B;
  cout << prime_factor(gcd(A, B)).size()+1 << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
int main () {
	int H,W;
	cin >> H >> W;
	char map[H][W];
	for (int yi = 0; yi < H; ++yi)
	{
		for (int xi = 0; xi < W; ++xi)
		{
			cin >> map[yi][xi];
		}
	}
	bool judge = true;
	for (int yi = 0; yi < H; ++yi)
	{
		for (int xi = 0; xi < W; ++xi)
		{
			bool tmp = false;
			if(map[yi][xi] == '.'){
				tmp = true;
			}
			if(xi-1 >= 0){
				if(map[yi][xi - 1] == '#')tmp = true;
			}
			if(xi+1 < W){
				if(map[yi][xi + 1] == '#')tmp = true;
			}
			if(yi-1 >= 0){
				if(map[yi-1][xi] == '#')tmp = true;
			}
			if(yi+1 < H){
				if(map[yi+1][xi] == '#')tmp = true;
			}
			if(!tmp){
				judge = false;
			}
		}
	}
	if(judge){
		cout << "Yes" << endl;
	}else{
		cout << "No" << endl;
	}
}

Measured memory_bytes: 384
#include<iostream>
#include<set>
using namespace std;
int main(){
	int n;
	char temp;
	set<int>array;

	cin >>n;
	for(int i=0;i<n;i++){
		cin >>temp;
		array.insert(temp);
	}
	if((int)array.size()==3)cout<<"Three"<<endl;
	else cout<<"Four"<<endl;
	return 0;
}

Measured memory_bytes: 256
(N,D,A) = map(int,input().split())
l = []
for i in range(N):
    l.append([int(x) for x in input().split()])
l.sort()
k = [0 for i in range(N)]
for i in range(N):
    k[i] = -((-l[i][1])//A)

m = [0] * N
ub = 0
cnt = 1
for i in range(N):
    if ub < N-1:
        while l[ub + 1][0]-l[i][0] <= 2*D:
            cnt += 1
            ub += 1
            if ub == N - 1:
                break
        m[i] = cnt
    else:
        m[i] = cnt
    cnt -= 1

ans = 0
al = 0
s = [0 for i in range(N)]
j = 0
for i in range(N):
    s[i] = max(k[i]-al,0)
    ans += s[i]
    al += s[i]
    if i < N-1:
        while j+m[j]-1 < i+1:
            al -= s[j]
            if j < N-1:
                j += 1

print(ans)

Measured memory_bytes: 136404
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
int n,m,a[200005],i,j,ans,lt,rt,mid;
int main()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=2*n;++i)
		scanf("%d",a+i);
	sort(a+1,a+1+2*n);
	lt=0,rt=n;
	while(lt<rt)
	{
		mid=lt+rt>>1;
		for(i=1,j=2*mid;i<j;++i,--j)
			if(a[i]+a[j]>=m)
				break;
		if(i<j)
		{
			rt=mid;
			continue;
		}
		for(i=2*mid+1,j=2*n;i<j;++i,--j)
			if(a[i]+a[j]<m)
				break;
		if(i<j)
			lt=mid+1;
		else
			rt=mid;
	}
	for(i=1,j=2*lt;i<j;++i,--j)
		ans=max(ans,a[i]+a[j]);
	for(i=2*lt+1,j=2*n;i<j;++i,--j)
		ans=max(ans,a[i]+a[j]-m);
	printf("%d",ans);
	return 0;
}


Measured memory_bytes: 896
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string>
#include <string.h>
#include <queue>
#include <vector>
#include <set>
using namespace std;
int main() {
	int H, W;
	char A[102][102];
	cin >> H >> W;
	for (int i = 0; i < 102; i++)for (int j = 0; j < 102; j++)A[i][j]='#';
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cin >> A[i + 1][j + 1];
		}
	}
	for (int i = 0; i < H+2; i++)
	{
		for (int j = 0; j < W+2; j++)
		{
			cout << A[i][j];
		}
		cout << endl;
	}

}

Measured memory_bytes: 256
x,y=map(int, input().split())

mod=pow(10, 9)+7

def comint(n, mod):
    fac = [0 for _ in range(n)]
    finv = [0 for _ in range(n)]
    inv = [0 for _ in range(n)]
    fac[0]=1
    fac[1]=1
    finv[0]=1
    finv[1]=1
    inv[1]=1

    for i in range(2, n):
        fac[i] = fac[i-1]*i%mod
        inv[i] = mod-inv[mod%i]*(mod//i)%mod
        finv[i] = finv[i-1]*inv[i]%mod
    return fac, finv

def com(n, k, fac, finv, mod):
    if n<k: return 0
    if n<0 or k<0: return 0
    return fac[n]*(finv[k]*finv[n-k]%mod)%mod

if (x+y)%3!=0:
    print(0)
else:
    n=(x+y)//3
    a=x-n
    b=y-n
    fac, finv = comint(a+b+1, mod)
    print(com(a+b,a,fac,finv,mod))


Measured memory_bytes: 88048
#include <stdio.h>
#define MAX 100
#define INF 1000000
#define WHITE 0
#define GRAY 1
#define BLACK 2

int n,num[MAX][MAX];

void  Dijk()
{
  int i,min,u,v,d[MAX],color[MAX];
  for(i=0;i<n;i++){
    d[i]=INF;
    color[i]=WHITE;
  }
  d[0]=0;
  color[0]=GRAY;
  while(1){
    min=INF;
    u=-1;
    for(i=0;i<n;i++){
      if(min>d[i] && color[i]!=BLACK){
        u=i;
        min=d[i];
      }
    }
    if(u==-1) break;
    color[u]=BLACK;
    for(v=0;v<n;v++){
      if(color[v]!=BLACK &&num[u][v]!=INF){
        if(d[v]>d[u]+num[u][v]){
          d[v]=d[u]+num[u][v];
          color[v]=GRAY;
        }
      }
    }
  }
  for(i=0;i<n;i++) printf("%d %d\n",i,d[i]);
}


int main()
{
  int i,j,u,k,v,c;

  scanf("%d",&n);
  for(i=0;i<n;i++)
  {
    for(j=0;j<n;j++){
      num[i][j]=INF;
    }
  }
  for(i=0;i<n;i++)
    {
      scanf("%d%d",&u,&k);
      for(j=0;j<k;j++){
        scanf("%d%d",&v,&c);
        num[u][v]=c;
      }
    }

  Dijk();

  return 0;
}



Measured memory_bytes: 2108
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdio>
#include<cassert>
using namespace std;

typedef vector<int> VI;
typedef long long LL;

#define REP(i, n) for (int i=0;i<n;++i)
#define FOR(i, a, b) for (int i=a;i<b;++i)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define ALL(A) A.begin(), A.end()
#define PB push_back

template<class T> inline bool checkMin(T &a,const T b){return b < a ? a = b, 1 : 0;}
template<class T> inline bool checkMax(T &a,const T b){return a < b ? a = b, 1 : 0;}

/** I/O Accelerator Interface .. **/ //{
#define g (c=getchar())
#define d isdigit(g)
#define p x=x*10+c-'0'
#define n x=x*10+'0'-c
#define pp l/=10,p
#define nn l/=10,n
template<class T> inline T& RD(T &x){
    char c;while(!d);x=c-'0';while(d)p;
    return x;
}
#undef nn
#undef pp
#undef n
#undef p
#undef d
#undef g
inline char* RS(char *s){
    //gets(s);
    scanf("%s", s);
    return s;
}

LL last_ans; int Case; template<class T> inline void OT(const T &x){
    cout << x << endl;
}



const int N = 109, M = 5040;
int a[105], d[105], pos[105];
int n; int ne[M][10]; int dp[105][M];
vector<VI> P; VI p;

int main(){

#define conds P

    RD(n); REP(i, n) RD(d[i]); REP(i, n) RD(a[i]);
    VI p; REP(i, 7) p.PB(i); do P.PB(p); while(next_permutation(ALL(p)));

    REP(i, M) REP(j, 8){
        p = P[i]; REP(i, 7) if (p[i] >= j) ++p[i];
        FOR(i, 1, 7) if (p[i] >= p[0]) --p[i]; p.erase(p.begin());
        ne[i][j] = lower_bound(ALL(P), p) - P.begin();
    }

    int ans = 0; REP(i, n) REP(j, M){

        for(int k = 0;k < 7;k++)pos[conds[j][k]] = k;
        int u = dp[i][j];

        FOR(k, 1, 8) if(i-k >= 0 && k<=d[i]) u += a[i];


#define v  dp[i + 1][ne[j][k]]
        for(int k = 0;k < 8;k++){
            checkMax(v, u);
            checkMax(ans, v);
            if(i - 7 + pos[k] >= 0 && 7 - pos[k] <= d[i])u -= a[i];
            if(i - 7 + pos[k] >= 0 && 7 - pos[k] <= d[i-7+pos[k]])
                u += a[i - 7 + pos[k]];
        }
    }
    cout << ans << endl;
}

Measured memory_bytes: 3812
<?php
$N = trim(fgets(STDIN));
$A = array_map('intval', explode(" ", fgets(STDIN)));
$cnt = 0;
$B = [];

while (1){
    foreach ($A as $i){
        if ($i%2!=0){
            break 2;
        }
        array_push($B, (integer)$i/2);
    }
    $cnt ++;
    $A = $B;
    $B =[];
}
print $cnt;

Measured memory_bytes: 4856
#include<bits/stdc++.h>
using namespace std;
main(){
  int a,b,c,x,y;
  cin>>a>>b>>c>>x>>y;
  int piz=min(x,y),mon=0;
  if(a+b>c*2){
    mon=c*piz*2;
  }else{
    mon=(a+b)*piz;
  }
  if(piz==x){
    piz=y-x;
    if(b>c*2)  mon+=c*2*piz;
    else mon+=b*piz;
  }else{
    piz=x-y;
    if(a>c*2) mon+=c*2*piz;
    else mon+=a*piz;
  }
  cout<<mon<<endl;
  return 0;
}


Measured memory_bytes: 256
#include <map>
#include <algorithm>
#include <cassert>
#include <climits>
#include <complex>
#include <cstdio>
#include <string>
#include <iostream>
#include <queue>
#include <string>
#include <tuple>
#include <vector>
#include <bitset>
using namespace std;
using ll = long long;
using ld = long double;

template<class T> bool chmin(T &a, T b) { return a>b?(a=b,true):false; }
template<class T> bool chmax(T &a, T b) { return a<b?(a=b,true):false; }
#define FOR(i,x,y) for(int i=(x);i<(int)(y);i++)
#define REP(i,y) for(int i=0;i<(int)(y);i++)
#define repp(i,y) for(int i=1;i<=(int)(y);i++)
#define REPB(i,n) for(int i=(int)(n)-1;i>=0;i--)
#define all(a) (a).begin(), (a).end()
#define uni(a) (a).erase(unique(all(a)), (a).end())
#define bit(n, i) (((n) >> (i)) & 1)
#define bitcount(n) __builtin_popcountll(n)
#define bs2int(bs) ((bs).to_ullong())

template<class T> ostream &operator<<(ostream &os, vector<T> &v) {
  for (auto it = v.begin(); it != v.end(); ++it) {
    if (it != v.begin()) os << " ";
    os << *it;
  }
  return os;
}

ll n,k;
ll a[100100], b[100100];

int main() {
  
  cin>>n>>k;
  vector<ll> v;
  int rightmost_zero = -1;
  ll i=0;
  while ((k>>i) > 0) {
    if(bit(k,i)==0) {
      rightmost_zero = i;
      break;
    }
    i++;
  }
  v.push_back(k);
  if (rightmost_zero != -1) {
    for(ll i=rightmost_zero+1; (k>>i)>0; i++) {
      bitset<64> bs(k);
      REP(j,i) {
        bs.set(j);
      }
      bs.reset(i);
      if (bs2int(bs) < k) v.push_back(bs2int(bs));
    }
  }
  // cout << endl << endl << v << endl << endl;
  REP(i,n) {
    cin>>a[i]>>b[i];
  }
  ll mxans = 0;
  for (int k : v) {
    ll ans = 0;
    REP(i,n) {
      if (k==(k | a[i])) ans+=b[i];
    }
    chmax(mxans, ans);
  }
  cout << mxans << endl;
}


Measured memory_bytes: 1792
#include "bits/stdc++.h"
using namespace std;
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
    *this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define cool ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	#define int  long long int
	#define pb push_back
	#define fe first
	#define se second
	#define endl "\n"
	#define pii pair<int, int>
	#define vi vector<int> 
	#define vvi vector<vi>
	#define REP(i,n) for(int i=0;i<n;i++)
	#define FOR(i,a,b) for(int i=a;i<=b;i++)
	#define FORR(i,a,b) for(int i=a;i>=b;i--)
	#define ALL(c) (c).begin(),()c.end() 

	#define PI 3.14159265358979323846
	const int N = 500 + 10;  
   
    vi vp;
   int sum;
   void solve() {
	    int r,d,x;
       
        
        cin>>r>>d>>x;
        
    
        
        int prev=x;
        for(int i=2001;i<=2010;i++) {
            
            int yo=r*(prev)-d;
            prev=yo;            
            vp.pb(yo);
        }
        
       // cout<<vp.size()<<endl;
        
        
        for(auto to:vp)
         cout<<to<<endl;       
	  
	   }
   
   
   
      int32_t main() {
	    cool;
	    int t=1;
	    while(t--)
	       solve();
	       
	       
	       return 0;	   
	   }


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

int main()
{
    long n;
    cin >> n;
    vector<long> a(n + 1);
    for (long i = 0; i < n + 1; i++)
    {
        cin >> a[i];
    }
    vector<long> b(n);
    for (long i = 0; i < n; i++)
    {
        cin >> b[i];
    }

    long ans = 0;
    for (long i = 0; i < n; i++)
    {
        if (a[i] >= b[i])
        {
            ans += b[i];
        }
        else
        {
            ans += a[i];
            long dif = b[i] - a[i];
            if (dif >= a[i + 1])
            {
                ans += a[i + 1];
                a[i + 1] = 0;
            }
            else
            {
                ans += dif;
                a[i + 1] -= dif;
            }
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 4808
N, M, C = map(int, input().split())
b_list = list(map(int, input().split()))

count = 0
for i in range(N):
    a_list = map(int, input().split())
    total = 0
    for a, b in zip(a_list, b_list):
        total += a * b
    if total + C > 0:
        count += 1

print(count)

Measured memory_bytes: 3064
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def dfs(i,j,m):
    m[i][j] = 0
    for k in range(4):
        x = i + dx[k]
        y = j + dy[k]
        if (x < 12 and x >= 0 and y < 12 and y >= 0 and m[x][y] == 1):
            dfs(x,y,m)
    return
while True:
    try:
        m = []
        sum = 0
        for i in range(12):
            m.append(list(map(int, input())))
        for i in range(12):
            for j in range(12):
                if (m[i][j] == 1):
                    dfs(i,j,m)
                    sum += 1
        print(sum)
        input()
    except:
        break


Measured memory_bytes: 5616
// {{{
#include <algorithm>
#include <array>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
// }}}

using namespace std;

using ll [[maybe_unused]] = long long;
using ull [[maybe_unused]] = unsigned long long;
using ld [[maybe_unused]] = long double;

[[maybe_unused]] static constexpr int mod = (int)1e9 + 7;
[[maybe_unused]] static constexpr int inf = 100100100;
[[maybe_unused]] static constexpr ll linf = 1e18;
[[maybe_unused]] static constexpr double eps = 1e-9;
[[maybe_unused]] static constexpr double pi = 3.14159265359;

#define rep(i, n) for (ll i = 0; i < n; ++i)
#define rrep(i, a) for (ll i = a; i >= 0; --i)
#define all(obj) begin(obj), end(obj)
#define rall(obj) rbegin(obj), rend(obj)
#define pb push_back
#define fst first
#define snd second


int main() {
    // cin.tie(0);
    // ios_base::sync_with_stdio(false);
    ll A, B;
    cin >> A >> B;
    if (A > 8 || B > 8) {
        cout << ":(" << endl;
    } else {
        cout << "Yay!" << endl;
    }
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
	int a;
    int b;
    int d;
    int r;
    double f;
    double x;
    double y;
    scanf("%d %d", &a, &b);
    d = a / b;
    r = a % b;
    x = a;
    y = b;
    f = x / y;
    printf("%d %d %f\n", d, r, f);
    return 0;
}


Measured memory_bytes: 2048
#include <iostream>
#include <vector>
#include <string>
using namespace std;

int N, M;
vector<string> id;
bool locked = true;

bool search(string tmp){
  for(int i = 0; i < id.size(); i++){
    if(id[i] == tmp) return true;
  }
  return false;
}

int main(void){
  string tmp;
  cin >> N;
  for(int i = 0; i < N; i++){
    cin >> tmp;
    id.push_back(tmp);
  }
  cin >> M;
  for(int i = 0; i < M; i++){
    cin >> tmp;
    if(search(tmp)){
      if(locked){
        cout << "Opened by " << tmp << endl;
        locked = false;
      }else{
        cout << "Closed by " << tmp << endl;
        locked = true;
      }
    }else{
      cout << "Unknown " << tmp << endl;
    }
  }
  return 0;
}

Measured memory_bytes: 1224
fn main() {
    let n: i32 = read();
    let f = |a:i32, b:i32|
        std::cmp::max(0,std::cmp::min(n,b)-a+1);
    println!("{}",f(1,9)+f(100,999)+f(10000,99999));
}

fn get_line() -> String {
    let mut buf = String::new();
    std::io::stdin().read_line(&mut buf).ok();
    buf.trim().to_owned()
}

fn read<T: std::str::FromStr>() -> T{
    get_line().parse().ok().unwrap()
}


Measured memory_bytes: 4352
from sys import stdin

n = int(stdin.readline().rstrip())
li = [int(stdin.readline().rstrip()) for _ in range(n)]


mins = li[0]
maxs = -100000000000

for i in range(1,n):
    maxs = max(maxs,li[i]-mins)
    mins = min(mins,li[i])
print(maxs)


Measured memory_bytes: 13624
#include <bits/stdc++.h>
using namespace std;
int main () {
    int N;
    cin >> N;
    int ans = 1;
    while (true) {
        bool aaa = false;
        if (N < ans) aaa = true;
        if (aaa) break;
        ans *= 2;
    }
    cout << ans / 2 << endl;

}

Measured memory_bytes: 256
using System;

namespace std
{
    class Program
    {
         static void Main(string[] args){
            var input = Console.ReadLine().Split(' ');  //配列inputに空白で区切って入力文字を格納
            var a = int.Parse(input[0]); //文字列を数値へ変換
            var b = int.Parse(input[1]);
            var c = int.Parse(input[2]);
             
            if((a < b) && (b < c)) {
                Console.WriteLine("Yes");
            } else {
            Console.WriteLine("No");  
            }
        }
    }
}


Measured memory_bytes: 15880
#!/usr/bin/env python3
#
# Author: Tetsuya Ishikawa <tiskw111@gmail.com>
# Date  : July 05, 2020
##################################################### SOURCE START #####################################################

N = int(input().strip())
A = set([])

for _ in range(N - 1):
    u, v = tuple(map(int, input().strip().split()))
    A.add((u, v))

V = 0
for l in range(1, N + 1):
    V += (N - l + 1) * (N - l + 2) // 2

E = 0
for u, v in A:
    a = min(u, v)
    b = max(u, v)
    E += a * (N - b + 1)

print(V - E)

##################################################### SOURCE FINISH ####################################################
# vim: expandtab tabstop=4 shiftwidth=4 fdm=marker


Measured memory_bytes: 42364
# coding: utf-8


def main():
    n, m = map(int, input().split())
    a = list(map(int, input().split()))

    d = {0: 1}

    a_sum = 0
    for i in range(n):
        a_sum += a[i]
        d[a_sum % m] = d.get(a_sum % m, 0) + 1

    answer = 0
    for count in d.values():
        answer += count * (count - 1) / 2

    print(int(answer))


if __name__ == '__main__':
    main()


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

using i64 = long long;
using P = pair<i64, i64>;

#define overload3(_1, _2, _3, name, ...) name
#define rep1(i, n) for(i64 i = 0LL; i < (n); ++i)
#define rep2(i, a, b) for(i64 i = (a); i < (b); ++i)
#define rep(...) overload3(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define all(v) v.begin(), v.end()


void solve(long long a, long long b){
    if(a <= 0 && 0 <= b) cout << "Zero" << endl;
    else if(a < 0 && (abs(a) - abs(b)) % 2 == 0) cout << "Negative" << endl;
    else cout << "Positive" << endl;
}

struct IoSetup {
    IoSetup() {
        cin.tie(nullptr);
        ios::sync_with_stdio(false);
        cout << fixed << setprecision(10);
        cerr << fixed << setprecision(10);
    }
} iosetup;

int main(){
    long long a;
    scanf("%lld",&a);
    long long b;
    scanf("%lld",&b);
    solve(a, b);
    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXV =1e5+10;
const int MAXN = 1e3+10;
const ll INF =1e13;
ll dp[MAXV];
int N,W,V,wi[MAXN],vi[MAXN];
int main()
{
	cin>>N>>W;
	for(int i =1;i<=N;i++)
	{
		cin>>wi[i]>>vi[i];
		V+=vi[i];
	}
	for(int i = 1;i<=V;i++)
		dp[i] =INF;
	dp[0]=0;
	for(int i = 1;i<=N;i++)
	{
		int w = wi[i],v =vi[i];
		for(int j = V;j>=v;j--)
		{
			dp[j]=min(dp[j],dp[j-v]+w);
		}
	}
	for(int i =V;i>=0;i--)
	  {
	  	if(dp[i]<=W)
	  	{
	  		cout<<i<<"\n";
	  		break;
	  	}
	  }
	   return 0;
}

Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#define dbg(x...) do{cout << "\033[32;1m" << #x << "->" ; err(x);} while(0)
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T,typename t,typename... A>
void err(T<t> a,A... x){for (auto v:a) cout << v << ' '; err(x...);}
template<typename T,typename... A>
void err(T a,A... x){cout << a << ' '; err(x...);}
#else
#define dbg(...)
#endif
typedef long long ll;
typedef pair<int,int> pi;
typedef vector<int> vi;
template<class T> using vc=vector<T>;
template<class T> using vvc=vc<vc<T>>;
template<class T> void mkuni(vector<T>&v)
{
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
}
template<class T>
void print(T x,int suc=1)
{
    cout<<x;
    if(suc==1) cout<<'\n';
    else cout<<' ';
}
template<class T>
void print(const vector<T>&v,int suc=1)
{
    for(int i=0;i<v.size();i++)
        print(v[i],i==(int)(v.size())-1?suc:2);
}
const int INF=0x3f3f3f3f;

int main()
{
	ll n,m;
	cin>>n>>m;
	ll ans=min(n,m/2);
	n-=ans,m-=ans*2;
	ans+=m/4;
	cout<<ans<<endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
 
 
#define MAX 52
 
int n;
int a;
int b;
 
long long int v[MAX];
 
long long int dp[MAX][MAX];
 
 
struct fraction{
	long long int A;
	long long int B;
	long long int way;
	fraction(long long int a_, long long int b_, long long int way_){
		A = a_;
		B = b_;
		way = way_;
	}
};
bool big(fraction a, fraction b){
	return a.A*b.B > b.A*a.B;
}
bool eq(fraction a, fraction b){
	return a.A*b.B == b.A*a.B;
}
map<long long int, int> mp;
map<long long int, int> use;
int main(){
	dp[0][0] = 1;
	for (int i = 0; i <50; i++){
		for (int j = 0; j <= i; j++){
			dp[i + 1][j] += dp[i][j];
			dp[i + 1][j + 1] += dp[i][j];
		}
	}
	cin >> n >> a >> b;
	for (int i = 0; i < n; i++){
		long long int A;
		scanf("%lld", &A);
		v[i] = A;
		mp[v[i]]++;
	}
	sort(v, v + n);
	reverse(v, v + n);
	fraction cur(0, 0, 1);
	fraction maxt(0, 1, 0);
	for (int i = 0; i < n; i++){
		cur.A += v[i];
		cur.B++;
		use[v[i]]++;
		if (cur.B >= a&&cur.B <= b){
			if (big(maxt, cur)){
				continue;
			}
			if (eq(maxt, cur)){
 
			}
			else{
				maxt = cur;
				maxt.way = 0;
			}
			maxt.way += dp[mp[v[i]]][use[v[i]]];
		}
	}
	double f = (long double)(maxt.A) / (long double)(maxt.B);
	printf("%.16f\n", f);
	printf("%lld\n", maxt.way);
	return 0;
}

Measured memory_bytes: 256
#  http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP2_1_A&lang=jp
#  Vector

wl = []
for i in range(0,int(input())):
    l = list(map(str,input().split()))
    c = int(l[0])

    if ( c == 0 ):
        d = int(l[1])
        wl.append(d)
    elif(c == 1):
        d = int(l[1])
        print (wl[d])
    elif(c == 2):
        wl.pop()




Measured memory_bytes: 13364
using System;
using System.Collections;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace AtCoder
{
	public class ABC
	{
		static public void Main(string[] args)
		{
			Console.SetOut(new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false });
			Solve();
			Console.Out.Flush();
		}

		const int mod = 1000000007;  // 10^9+7
		static int Mod(long x, int m) { return (int)((x % m + m) % m); }
		static long Mod(long x, long m) { return (x % m + m) % m; }

		static public void Solve()
		{
			//string s = Console.ReadLine();
			//int n = int.Parse(Console.ReadLine());
			//long x = long.Parse(Console.ReadLine());
			//int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			//long[] vs = Console.ReadLine().Split().Select(long.Parse).ToArray();

			int[] vs = Console.ReadLine().Split().Select(int.Parse).ToArray();
			int a = vs[0];
			int b = vs[1];

			int c = b - a;
			int d = (c + 1) * c / 2;
			Console.WriteLine(d - b);

		}
	}
}


Measured memory_bytes: 28296
S = input()
ans = "AC"
tmp = 0
if S[0] != "A":
	ans = "WA"
for i in range(2, len(S) - 1):
	if S[i] == "C":
		tmp += 1
if tmp != 1:
	ans = "WA"
if not S.replace("A", "").replace("C", "").islower():
	ans = "WA"
print(ans)


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

int main(){
  int a,b,c;
  cin >> a >> b >> c;
  int ans = 0;
  if (a != b) ans++;
  if (b != c) ans++;
  if (c != a) ans++;
  if (ans == 2) cout << "Yes" << endl;
  else cout << "No" << endl;
  return 0;
}

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

#include <boost/multiprecision/cpp_int.hpp>
using boost::multiprecision::cpp_int;

int main() {
  int n, m; cin >> n >> m;
  vector<int> arr(m);
  for (int i = 0; i < m; ++i) {
    cin >> arr[i];
  }
  map<int, int> match;
  vector<int> match_nums = {2,5,5,4,5,6,3,7,6};
  for (int i = 1; i < 10; ++i) {
    match[i] = match_nums[i - 1];
  }
  vector<cpp_int> dp(n + 7, -1);
  dp[0] = 0;
  for (int i = 0; i < n; ++i) {
    for (int a: arr) {
      if (dp[i] == -1) continue;
      cpp_int new_dp = (dp[i] << 3) + (dp[i] << 1) + a;
      if (dp[i + match[a]] < new_dp) dp[i + match[a]] = new_dp;
    }
  }
  cout << dp[n] << endl;
}


Measured memory_bytes: 14848
#include<bits/stdc++.h>
#define rep(i,a) for(int i=0;i<a;i++)
using namespace std;
int main()
{
    string s;
    cin>>s;
    if(s=="SAT") cout<<1<<endl;
    if(s=="FRI") cout<<2<<endl;
    if(s=="THU") cout<<3<<endl;
    if(s=="WED") cout<<4<<endl;
    if(s=="TUE") cout<<5<<endl;
    if(s=="MON") cout<<6<<endl;
    if(s=="SUN") cout<<7<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main() {
  vector<int> cnt(100, 0);
  vector<int>::iterator itr = cnt.begin();
  int buf;

  while(cin >> buf) {
	cnt[buf - 1]++;
  }
  for(;;) {
	itr = find(itr, cnt.end(), *max_element(cnt.begin(), cnt.end()));
	if(itr == cnt.end()) break;
	cout << itr - cnt.begin() + 1<< endl;
	++itr;
  }
  return 0;
}

Measured memory_bytes: 3020
#include<bits/stdc++.h>
#define Set(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=3021;
const int mod=1e9+7;
template <typename T> inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}
typedef long long ll;
template<typename T>inline void Inc(T&x,int y){x+=y;if(x>=mod) x-=mod;return;}
template<typename T>inline void Dec(T&x,int y){x-=y;if(x <  0) x+=mod;return;}
template<typename T>inline int fpow(int x,T k){int ret=1;for(;k;k>>=1,x=(ll)x*x%mod) if(k&1) ret=(ll)ret*x%mod;return ret;}
inline int Sum(int x,int y){x+=y;if(x>=mod) return x-mod;return x;}
inline int Dif(int x,int y){x-=y;if(x < 0 ) return x+mod;return x;}
int dp[N][N][2],n,m;

int main()
{
	init(n),init(m);
	for(int i=1;i<=n;++i) dp[0][i][0]=1;
	dp[0][0][1]=1;
	for(int i=1;i<=m;++i) {
		for(int j=0;j<=n;++j) {
			if(j>1) Inc(dp[i][j-1][0],dp[i-1][j][0]),Inc(dp[i][j-1][1],dp[i-1][j][1]); // ww
			else if(j) Inc(dp[i][0][1],dp[i-1][1][0]),Inc(dp[i][0][1],dp[i-1][1][1]);
			
			if(j>1) Inc(dp[i][j][0],dp[i-1][j][0]),Inc(dp[i][j][1],dp[i-1][j][1]);// wb
			else if(j) Inc(dp[i][1][1],dp[i-1][1][0]),Inc(dp[i][1][1],dp[i-1][1][1]);
			
			if(j<n) {
				Inc(dp[i][j][0],dp[i-1][j][0]),Inc(dp[i][j][1],dp[i-1][j][1]); //bw
				Inc(dp[i][j+1][0],dp[i-1][j][0]),Inc(dp[i][j+1][1],dp[i-1][j][1]);//bb
			}
		}
	}
	int ans=0;
	for(int i=0;i<=n;++i) Inc(ans,dp[m][i][1]);
	cout<<ans<<endl;
	return 0;
}


Measured memory_bytes: 71040
#include<stdio.h>

#define MAX 500000
#define SENTINEL 2000000000

int L[MAX/2+2],R[MAX/2+2];
//int cnt=0;  cnt=nlogn

void merge(int A[],int n,int left,int mid,int right){ //分割と統治
    int n1 = mid-left;
    int n2 = right-mid;
    for(int i=0;i<n1;i++) L[i]=A[left+i];
    for(int i=0;i<n2;i++) R[i]=A[mid+i];
    L[n1]=R[n2]=SENTINEL;  //番兵
    int i=0,j=0;
    for(int k=left;k<right;k++){
        //cnt++;
        if(L[i]<=R[j]){
            A[k]=L[i++];
        }else{
            A[k]=R[j++];
        }
    }
}

void mergeSort(int A[],int n,int left,int right){
    if(left+1<right){  //要素数が2つ以上
        int mid = (left+right)/2;
        mergeSort(A,n,left,mid);
        mergeSort(A,n,mid,right);
        merge(A,n,left,mid,right);
    }
}

int main(void){
    int n,k,i;
    long int sum = 0;
    scanf("%d%d",&n,&k);
    int h[n];
    for(i=0;i<n;i++){
        scanf("%d",&h[i]);
        sum+= h[i];
    }
    
    if(k>=n){
        printf("0");
        return 0;
    }
    
    mergeSort(h,n,0,n);
    for(i=n-1;i>n-1-k;i--){
        sum -= h[i];
    }
    
    printf("%ld",sum);
    return 0;
}


Measured memory_bytes: 1664
#include <bits/stdc++.h>
#define repr(i,from,to) for(int (i)=(from);(i)<(to);(i)++)
#define rep(i,n) for(int (i)=0;(i)<(n);(i)++)
// const bool debug=true;
const bool debug=false;
#define DEBUG if(debug==true)
#define vprint(x) for(auto a:(x)) cout << x << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll MOD = 1000000007;
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;
}

class BinaryIndexTree{
    public:
        BinaryIndexTree(long long N) : n(N), data(n*2-1,0) {}
        long long sum(long long i){
            assert(i < n);
            long long s = 0;
            while(i > 0){
                s += data[i];
                i -= i & -i;
            }
            return s;
        } 
        long long add(long long i, long long x){
            assert(i < n);
            while(i <= n){
                data[i] += x;
                i += i & -i;
            }
        }
        long long size(void){
            return n;
        }
    private:
        long long n;
        vector<long long> data;
};

int main(void) {
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll n,k;cin>>n>>k;
    ll p[n];rep(i,n){cin>>p[i];p[i]++;}
    BinaryIndexTree bit = BinaryIndexTree(n+5);
    ll cnt=1;
    rep(i,k){
        bit.add(p[i],1LL);
        if(i>0){
            if(p[i]>p[i-1]){
                cnt++;
            }
            else{
                cnt=1;
            }
        }
    }
    ll res = 1;
    bool flg = cnt==k;
    repr(i,k,n){
        bit.add(p[i-k],-1LL);
        bit.add(p[i],1LL);
        if(p[i]>p[i-1]){
            cnt = min(cnt+1,k);
        }else{cnt=1;}
        if(!flg&&cnt==k){res++;flg=true;}
        else if(cnt!=k&&(bit.sum(p[i])!=k||bit.sum(p[i-k])!=0)){res++;}
        DEBUG{
            cout << cnt << " " << res <<endl;

        }
    }
    cout << res << endl;
    return 0;
}


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

#define REPI(i, n) for(int i = 0; i < n; i++)
#define REPJ(j, n) for(int j = 0; j < n; j++)

using namespace std;

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

    int n; cin >> n;
    int array[2][100005];
    REPI(i, 100005){
        for(int j = 0; j < 2; j++){
            array[j][i] = 0;
        }
    }

    REPI(i, n){
        int x; cin >> x;
        array[i % 2][x]++;
    }

    int max01 = 0; int max02 = 0;
    int max01_num; int max02_num;
    int max11 = 0; int max12 = 0;
    int max11_num; int max12_num;
    REPI(i, 100005){
        if(array[0][i] > max01){
            max02 = max01;
            max01 = array[0][i];

            max02_num = max01_num;
            max01_num = i;
        }else if(array[0][i] > max02){
            max02 = array[0][i];
        }
        if(array[1][i] > max11){
            max12 = max11;
            max11 = array[1][i];

            max12_num = max11_num;
            max11_num = i;
        }else if(array[1][i] > max12){
            max12 = array[1][i];
        }
    }
    
    //cout << max01_num << ' ' << max02_num << endl;
    //cout << max11_num << ' ' << max12_num << endl;

    int ans;
    if(max01_num != max11_num){
        ans = n - max01 - max11;
    }else{
        ans = min(n - max01 - max12, n - max02 - max11);
    }
    cout << ans;
}


Measured memory_bytes: 1024
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 5;
const int P = 1e9 + 7;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
char s[MAXN]; int cnt[26];
int main() {
	int n; read(n);
	scanf("%s", s + 1);
	for (int i = 1; i <= n; i++)
		cnt[s[i] - 'a']++;
	int ans = 1;
	for (int i = 0; i <= 25; i++)
		ans = (1ll + cnt[i]) * ans % P;
	writeln(ans - 1);
	return 0;
}

Measured memory_bytes: 384
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math,O3")

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

typedef unsigned long long int ull;
typedef long long ll;
#define pb push_back

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //your code starts here
    ll n;
    cin >> n;
    ll sum = 0LL;
    for (ll k = 1; k <= n; k++)
    {
        ll lim = n / k;
        sum += (k * lim * (lim + 1)) / 2;
    }
    cout << sum;
    return 0;
}


Measured memory_bytes: 3612
#include<stdio.h>
void quicksort(long int a[],int s,int t){
  if(s<t){
    long int i=s,j=t,p=a[(s+t)/2];
    while(1){
      while(a[i]<p)i++;
      while(p<a[j])j--;
      if(i>=j)break;
      a[i]^=a[j]^=a[i]^=a[j];
      i++;j--;
    }
    quicksort(a,s,i-1);quicksort(a,j+1,t);
  }
}
int main(){
  long int a[200000],n,i,x=0;
  scanf("%ld",&n);
  for(i=0;i<n;i++){scanf("%ld",&a[i]);a[i]-=i;}
  quicksort(a,0,n-1);
  for(i=0;i<n;i++)x+=(a[i]-a[n/2])*(a[i]-a[n/2]>0?1:-1);
  printf("%ld",x);
}


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

int main(){
    int A, B;
    // int N;
    // vector<int>     vA(100010, 0);
    // map<int64_t, int>   mP;
    int res;

    cin >> A >> B;
    // for (int i=0; i<N; i++){
    //     int Ai;
    //     cin >> Ai;
    //     vA.at(Ai)++;
    //     AiMax = max(AiMax, Ai);
    // }

    res = max(A + B, A - B);
    res = max(res,   A * B);
    // for (int i=0; i<N; i++){
        // res = max(res, count3);
    // }

    cout << res << endl;
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <string>
#include <limits>
#include <algorithm>
#include <map>
#include <sstream>
#include <unordered_map>

using ll = long long;
using ull = unsigned long long;
using uint = unsigned int;
static ull tenq = 1000000000;
static ull mod = tenq + 7;

using namespace std;

int main()
{
  ll N;
  cin >> N;
  vector<ll> as(N);
  ll sum = 0;
  for (auto i = 0; i < N; i++) {
    cin >> as[i];
    sum += as[i];
  }

  ll lsum = 0;
  ll min_diff = LONG_LONG_MAX;
  for (auto i = 0; i < N-1; i++) {
    lsum += as[i];
    ll diff = abs(lsum - (sum - lsum));
    min_diff = min(min_diff, diff);
  }

  cout << min_diff << endl;

  return 0;
}


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

using v1 = vector<int>;
using v2 = vector<vector<int>>;
using ll = long long;

int main(){
	int a, b, c, d;
	cin >> a >> b >> c >> d;
 	int time;
	if(c>=b || a>=d){
		time = 0;
	}else{
		time = min(b, d) - max(a,c);
	}
	cout << time << endl;

}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int a[100005], n, k;
int fcnt, cnt, ans;
int fsum[100005], sum[100005];
int main() {
	cin >> n >> k;
	int i, pos = 0;
	for(i = 1; i <= n; ++i) {
		cin >> a[i];
		if(a[i] < 0) fcnt = i;
	}
	cnt = n - fcnt;
	for(i = fcnt; i >= 1; --i) fsum[fcnt - i + 1] = -a[i];
	for(i = 1; i <= cnt; ++i) sum[i] = a[i + fcnt];
	ans = INT_MAX;
	for(i = 0; i <= min(fcnt, k); ++i) {
		if(k - i <= cnt)ans = min(ans, fsum[i] + sum[k - i] + min(fsum[i], sum[k - i]));  
		//if(!ans) cout << i << endl;
	}
	cout << ans;
	return 0;
} 

Measured memory_bytes: 1024
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define Nmax 200010
#define FOR(i,a,b) for(long long i=(a);i<(b);i++)
#define RFOR(i,a,b) for(long long i = (b-1);i>=a;i--)
#define REP(i,n)  FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define dump(x)  cout << #x << " = " << (x) << endl;
#define debug(x) cout << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<P> Graph;
 
int main() {
	int T;
	cin >> T;
	ll A,B,C,D;
	//BとCの間の値になる可能性はあるか
	//B=17,C=14だったら、15,16になるか？ C < ans && ans < B
	REP(i,T){
		cin >> A >> B >> C >> D;
      	if(A < B || B > D){
      		cout << "No" << endl;
      		continue;
    	}
    	if(B <= C){
      		cout << "Yes" << endl;
      		continue;
    	}
		ll ans = A%B;
      	//ll ka=D%B;//katamuki
      	ll g=__gcd(B,D); //最大公約数
      	//if(ka==0){ cout<<"Yes"<<endl; continue;}
      	ll w = B-g+(A%g); 
      	if(C < w) cout << "No" << endl;
		else cout << "Yes" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#define rep(i,a) for(int i = 0; i < a; i++)
using namespace std;

int main(){
	int n, x, ans;
	while(1){
		ans = 0;
		cin >> n >> x;
		if(n == 0 && x == 0) break;

		for(int i = 1; i <= n - 2; i++){
			for(int j = i + 1; j <= n - 1; j++){
				for(int k = j + 1; k <= n; k++){
					if(i + j + k == x) ans++;
				}
			}
		}
		cout << ans << endl;
	}
}

Measured memory_bytes: 1160