akhauriyash/Code-Regression huggingface dataset:
import collections
n=int(input())
a=list(map(int,input().split()))
a=collections.Counter(a)
values,counts=zip(*a.most_common())
l=len(values)
ans=0
for i in range(0,len(values)):
  if counts[i]<values[i]:
    ans=ans+counts[i]
  elif counts[i]>values[i]:
    ans=ans+counts[i]-values[i]
print(ans)

Measured memory_bytes: 26988
s=int(input())
d = [list(map(int,input().split())) for _ in range(s)]

def p(val):
    print(val)

def calc(s,d):
    for i in range(s-2):
        if d[i][0] == d[i][1] and d[i+1][0]==d[i+1][1] and d[i+2][0] == d[i+2][1]:
            
            return 'Yes'
    
    return 'No'

        
p(calc(s,d))

Measured memory_bytes: 9172
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max()/32*15+208;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> v(n);
    for (auto &&i : v) scanf("%d", &i);
    vector<int> dp(1 << n), dp2(1 << n), cnt(1 << n);
    int s = 0;
    for (int i = 0; i < (1 << n); ++i) {
        for (int j = 0; j < n; ++j) {
            if(i & (1 << j)){
                dp[i] = dp[i^(1 << j)] + v[j];
                cnt[i] = cnt[i^(1 << j)]+1;
                if(dp[i] == k) dp2[(1 << n)-i-1] = -1, s++;
                break;
            }
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < (1 << n); ++j) {
            if(!(j & (1 << i))) dp2[j] += dp2[j|(1 << i)];
        }
    }
    int ans = 100;
    for (int i = 0; i < (1 << n); ++i) {
        if(dp2[i] == 0) ans = min(ans, cnt[i]);
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 15300
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

    cuml_coords = deepcopy(coords)
    for l in range(N):
        for r in range(1, N):
            cuml_coords[l][r] = cuml_coords[l][r - 1] + coords[l][r]

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)

cuml_1d(N, lines, queries)


Measured memory_bytes: 114648
#include<bits/stdc++.h>
#include <iostream>
using namespace std;
#define se second
#define fi first
#define ll long long
#define ld long double
#define pll pair<ll ,ll >
#define plll pair<pll,ll>
#define ppll pair<pll, pll>
#define pii pair<int, int> 
#define piii pair<pii, int>
#define pb push_back
const ll llinf = 2e18 + 7;
const int inf = 2e9 + 7;
const ll mod = 1e9 + 7;
const ll N = 1e6 + 1;
const ll M = 1e3 + 5;
const ld pi = 3.14159265358979; 
void solve() {
    string s,t;
    cin>>s>>t;
    int n = s.size(),cnt = 0;
    for(int i=0;i<n;i++) {
        if(s[i] != t[i]) cnt++;
    }
    cout<<cnt;
}
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int t;
    t=1;
    
    // cin>>t;
    while(t--) {
        solve();
        cout<<"\n";
    }
    return 0; 

}


Measured memory_bytes: 3792
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
using namespace std;
using ll =long long;
const int mod = 1000000007;

class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% mod + mod) % mod) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint & a) {
		if ((x += a.x) >= mod) x -= mod;
		return *this;
	}
	mint & operator-=(const mint & a) {
		if ((x += mod - a.x) >= mod) x -= mod;
		return *this;
	}
	mint & operator*=(const  mint & a) {
		(x *= a.x) %= mod;
		return *this;
	}
	mint operator+(const mint & a) const {
		mint res(*this);
		return res += a;
	}
	mint operator-(const mint & a) const {
		mint res(*this);
		return res -= a;
	}
	mint operator*(const mint & a) const {
		mint res(*this);
		return res *= a;
	}
	mint pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint & a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint & a) const {
		mint res(*this);
		return res /= a;
	}

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

int main() {

		ll x, y;
	cin >> x >>y;
	mint X;
	mint Y;
	ll N;
	N = (x + y) / 3;
	if ((x+y)%3!= 0) {


		cout << 0;
		return 0;
	}
	if (x - N<0||y-N<0) {

		cout << 0;
		return 0;

	}
	
	ll tmp=x-N;
	mint sum=1;
	ll tmp1;
	mint media;
	for (ll i = 1; i <= y - N; i++) {
		media=i;
		X = x-N+i;
		sum = sum * X / media;
		tmp = x-N+i;
		
	}
	for (ll i = tmp+1; i <=N; i++) {
		media = i;
		sum=sum*media;
	}
	cout << sum;
	
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
using Graph = vector<vector<int>>;

ll calc(ll x, ll a, ll b) {
  return floor(a*x/b) - a*floor(x/b);
}

int main() {
  ll a, b, n;
  cin >> a >> b >> n;
  ll ans = calc(min(b-1, n), a, b);
  cout << ans << endl;
  return 0;
}

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

signed main(){

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

  return 0;
}


Measured memory_bytes: 256
N, K = map(int, input().split())
A = [int(a) for a in input().split()]

for _ in range(K):
    B = [0] * (N + 1)
    for i, a in enumerate(A):
        B[max(i - a, 0)] += 1
        B[min(i + a + 1, N)] -= 1
    for i in range(1, N + 1):
        B[i] += B[i-1]
    A = B[:N]
    if A.count(N) == N:
        break
print(*A)

Measured memory_bytes: 128280
#include <bits/stdc++.h> 
#include <vector>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define size_of_array(array) (sizeof(array)/sizeof(array[0]))
using ll =long long;
using namespace std;
using Graph=vector<vector<int>>;
using Field=vector<vector<int>>;

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

int main(){
    int a,b,t;
    cin>>a>>b>>t;
    int n=0;
    while(a*n<=t){
        ++n;
    }
    cout<<b*(n-1)<<endl;
}

Measured memory_bytes: 3600
#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<map>
#include<set>
#define N (1000000000+7)
using namespace std;
typedef long long ll;
typedef pair<int,ll> P;


int main(void){
    int n,t;
    cin>>n>>t;
    vector<ll>a(n);
    map<ll,int>m1,m2;
    set<ll>s1,s2;
    for(int i=0;i<n;i++){
        cin>>a[i];
        m1[a[i]]++;
        m2[a[i]]++;
        s1.insert(a[i]);
        s2.insert(a[i]);
    }
    if(t%2==1)t--;
    ll half = t/2;
    ll ma = 0;
    for(int i=0;i<n-1;i++){
        ll M = *(s1.rbegin());
        if(m1[M]!=0)ma = max(ma,M*half-a[i]*half);
        m1[a[i]]--;
        if(m1[a[i]]==0)s1.erase(a[i]);
    }
    ll ans = 0;
    for(int i=0;i<n-1;i++){
        ll M = ma/half+a[i];
        //cout<<M<<" "<<m2[M]<<endl;
        if(m2[M]!=0){
            ans+=m2[M];
            m2[M]=0;
        }
        m2[a[i]]--;
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 29184
N = int(input())
A = list(map(int, input().split()))

for i in range(N):
    A[i] = A[i] - i - 1

A = sorted(A)

if N % 2 == 1:
    m = A[N//2]
else:
    m = (A[N//2] + A[N//2 - 1]) // 2

ans = 0
for i in range(N):
    ans += abs(A[i] - m)

print(ans)

Measured memory_bytes: 30912
from sys import stdin
import math
import re
import queue

input = stdin.readline

MOD = 1000000007
INF = 122337203685477580

def solve():
    N,H,W = map(int, input().split())
    cnt = 0
    for x in range(N):
        h,w = map(int, input().split())
        if(h >= H and w >= W):
            cnt += 1
    print(cnt)

if __name__ == '__main__':
    solve()


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

typedef pair<int, int> pii;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i,n) rep2(i,0,n)
#define rep2(i,m,n) for(int i=m;i<(n);i++)
#define ALL(c) (c).begin(),(c).end()

int R, C, N;
int MX[100010];

struct edge {
	int to, cost;
	edge(){}
	edge(int to, int cost) : to(to), cost(cost) {}
};

ll d[100010];
int r[100010], c[100010], A[100010];
vector<edge> g[100010];
vector<int> vec[100010];
int vis[100010];
ll ms[100010];

bool dfs(int v, int k)
{
	vis[v] = k;
	for (edge e : g[v]) {
		if (vis[e.to] != -1) {
			if (d[e.to] - d[v] != e.cost) {
				return false;
			}
		} else {
			d[e.to] = d[v] + e.cost;
			if (!dfs(e.to, k)) return false;
		}
	}
	return true;
}

int main() {
	scanf("%d%d%d", &R, &C, &N);
	rep(i, C) MX[i] = INT_MAX;

	rep(i, N) {
		scanf("%d%d%d", &r[i], &c[i], &A[i]);
		--r[i]; --c[i];
		MX[c[i]] = min(MX[c[i]], A[i]);
		vec[r[i]].pb(i);
	}

	rep(i, R) {
		rep(j, (int)vec[i].size()-1) {
			int ii = vec[i][j], jj = vec[i][j+1];
			g[c[ii]].eb(c[jj], A[jj]-A[ii]);
			g[c[jj]].eb(c[ii], A[ii]-A[jj]);
		}
	}

	rep(i, C) ms[i] = LLONG_MAX; 
	memset(vis, -1, sizeof(vis));

	int now = 0;
	rep(i, C) {
		if (vis[i] == -1) {
			if (!dfs(i, now++)) {
				puts("No");
				return 0;
			}
		}
		ms[vis[i]] = min(ms[vis[i]], d[i]);
	}

	rep(i, C) {
		d[i] -= ms[vis[i]];
		if (d[i] > MX[i]) {
			puts("No");
			return 0;
		}
	}

	puts("Yes");

	return 0;
}

Measured memory_bytes: 13952
#include<iostream>
using namespace std;
int main (void)
{
	int N, X, T;
	cin >> N >> X >> T;
	int time;
	time = (N / X);
	int residue = N % X;
	if (residue != 0)
		time++;
	long AllTime = ((long) time) * T;
	cout << AllTime << endl;
	return 0;
}

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

using namespace std;
using ll = long long;

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

    int n, k;

    cin >> n >> k;

    int ans = 0;

    while(n != 0) {
        n /= k;
        ++ans;
    }

    printf("%d\n", ans);

    return 0;
}

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

int main() {
    int a, b, c;
    double S, L, h;
    double rad;
    double PI = acos(-1);

    cin >> a >> b >> c;
    rad = c * PI / 180;

    S = 0.5*a*b*sin(rad);
    L = a + b + sqrt(a*a + b*b - 2*a*b*cos(rad));
    h = b * sin(rad);
    // h = a * sin(rad);

    // cout << S << endl;
    // cout << L << endl;
    // cout << h << endl;

    printf("%lf\n%lf\n%lf\n", S, L, h);

    return 0;
}

Measured memory_bytes: 3444
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i=0; i<(int)n; i++)
#define REPR(i, n) for(int i=(int)n-1; i>=0; i--)
#define FOR(i, m, n) for(int i=(int)m; i<(int)n; i++)
#define FORR(i, m, n) for(int i=(int)m-1; i>=(int)n; i--)
#define ALL(x) (x).begin(), (x).end()
#define ASC(v) sort(ALL(v));
#define DESC(v) sort(ALL(v), greater<int>());
#define UNIQ(a) sort(ALL(a));(a).resize(unique(ALL(a)) - a.begin());
#define PRINTD(x, d) cout << fixed << setprecision(d) << x << "\n";
#define DEBUG(x) cout<<#x<<": "<<x<<"\n"
typedef long long ll;
const double PI = acos(-1);
ll lcm(ll a, ll b) { return a / __gcd(a, b) * b; }
bool isprime(int x){ int i; if(x<2)return 0; else if(x==2) return 1; if(x%2==0) return 0; for(i=3; i*i<=x; i+=2) if(x%i==0) return 0; return 1; }
int digsum(int n) { int r=0; while(n>0) { r+=n%10; n/=10; } return r; }
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 (a>b) { a = b; return 1; } return 0; }



void solve(long long K, long long N, std::vector<long long> A){
	ll res = 0;
	ASC(A);
	ll maxdist = 0;
	REP(i, N-1) {
		ll dist = A[i+1] - A[i];
		chmax(maxdist, dist);
	}
	ll dist = (K+A[0]) - A[A.size()-1];
	chmax(maxdist, dist);
	res = K - maxdist;

	cout << res << "\n";
}

int main(){
    long long K;
    scanf("%lld",&K);
    long long N;
    scanf("%lld",&N);
    std::vector<long long> A(N);
    for(int i = 0 ; i < N ; i++){
        scanf("%lld",&A[i]);
    }
    solve(K, N, std::move(A));
    return 0;
}


Measured memory_bytes: 1920
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFSIZE 1024
char buf[BUFSIZE];
int main(void)
{
	char *p;
	const char *DELIMITER = " ";
	while (p = strtok(fgets(buf, BUFSIZE, stdin), DELIMITER)) {
		int res = 0, one = 0, n;
		if (*p == '0') break;
		do {
			n = atoi(p);
			res += (n < 10 ? n : 10);
			if (n == 1) one++;
		} while (p = strtok(NULL, DELIMITER));
		while (one-- && res + 10 <= 21) res += 10;
		if (res > 21) res = 0;
		printf("%d\n", res);
	}
	return 0;
}

Measured memory_bytes: 0
from functools import reduce
from fractions import gcd
import math
import bisect
import itertools
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline
INF = float("inf")


def main():
    N = int(input())

    res = 0
    for i in range(1,N+1):
        if i % 3 != 0 and i % 5 != 0:
            res += i
    
    print(res)


if __name__ == '__main__':
    main()

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

using namespace std;

#define countof(a) (sizeof(a)/sizeof(*a))

#define vi vector<int>
#define vvi vector<vector<int> >
#define vpi vector<pi >
#define pi pair<int,int>
#define mp make_pair
#define fi first
#define se second
#define all(n) n.begin(), n.end()

#define FROMTO(var, from, to) for (register int var = (from), var##down = ((int)(to)) < ((int)(from));var##down ? (var >= (int)(to)) : (var <= (int)(to));var##down ? var-- : var++)
#define UPTO(var, from, to)   for (register int var = (from); var <= ((int)to); var++)
#define DOWNTO(var, from, to) for (register int var = (from); var >= ((int)to); var--)
#define FOR(var, to)          UPTO(var, 0, (to)-1)
#define DOWN(var, from)       DOWNTO(var, (from)-1, 0)

#define INIT(var, val) FOR(i,countof(var)) var[i] = val
#define INPUT(var) FOR(i,countof(var)) cin >> var[i]
#define INPUT1(var) FOR(i,countof(var)) cin >> var[i], var[i]--

#define SORT(v) qsort(v,countof(v),sizeof(*v),int_less)
#define SORTT(v) qsort(v,countof(v),sizeof(*v),int_greater)
#define QSORT(v,b) qsort(v,countof(v),sizeof(*v),b)

#define MOD 1000000007
#define INF ((1 << 30)-1)
#define LINF ((1LL << 62)-1)

typedef uint8_t u8;
typedef uint16_t u16;
typedef uint32_t u32;
typedef uint64_t u64;
typedef int8_t s8;
typedef int16_t s16;
typedef int32_t s32;
typedef int64_t s64;

struct Comb {
    vector<vector<s64> > data;
    Comb(int n) { // O(n^2)
        data = vector<vector<s64> >(n+1,vector<s64>(n+1,1));
        UPTO(i,1,n) {
            FOR(j,i+1) {
                if (!j || j == i) data[i][j] = 1;
                else data[i][j] = data[i-1][j-1] + data[i-1][j];
            }
        }
    }

    s64 ncr(int n, int r) {
        return data[n][r];
    }
};

static inline int ri() {
  int a;
  scanf("%d", &a);
  return a;
}

int int_less(const void *a, const void *b) {
  return (*((const int*)a) - *((const int*)b));
}
int int_greater(const void *a, const void *b) {
  return (*((const int*)b) - *((const int*)a));
}

int main() {
    int n = ri();
	int m = ri();
	int a[m];
	INPUT(a);
	SORT(a);

	int d[m-1];
	FOR(i,m-1) d[i] = a[i+1] - a[i];

	SORT(d);
	s64 res = 0;
	FOR(i,m-1-(n-1)) res += d[i];
	cout << res << endl;
    return 0;
}


Measured memory_bytes: 1396
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define repI(i, d, n) for (int i = (d); i < (n); ++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using M = map<int, int>;
ll INF = 1ll<<61;
double pi = 3.141592653589793238;
vector<bool> is_prime;
vector<bool> is_2017;
vector<ll> is2017_table;

void Sieve(size_t max){
    if(max+1 > is_prime.size()){     // resizeで要素数が減らないように
        is_prime.resize(max+1,true); // is_primeに必要な要素数を確保
    }
    is_prime[0] = false; // 0は素数ではない
    is_prime[1] = false; // 1は素数ではない

    for(size_t i=2; i*i<=max; ++i) // 0からsqrt(max)まで調べる
        if(is_prime[i]) // iが素数ならば
            for(size_t j=2; i*j<=max; ++j) // (max以下の)iの倍数は
                is_prime[i*j] = false;      // 素数ではない
}

void Calc2017(size_t max) {
  if(max+1 > is_2017.size()){     // resizeで要素数が減らないように
      is_2017.resize(max+1,true); // is_primeに必要な要素数を確保
  }
  is_prime[0] = false; // 0は素数ではない
  is_prime[1] = false; // 1は素数ではない

  rep(i, ll(max)+1) {
    is_2017[i] = is_prime[i] && is_prime[int((i+1)/2)];
  }

}

int main() {
  Sieve(1e5+1);
  Calc2017(1e5+1);
  vector<ll> is_2017_table(1e5+1);
  repI(i, 1, 1e5+2) {
    is_2017_table[i] = is_2017_table[i-1];
    if (is_2017[i]) is_2017_table[i]++;
  }

  ll q;
  cin >> q;

  // rep(i, 100) cout << is_2017_table[i] << " ";
  // cout << endl;
  rep(i, q) {
    ll l, r;
    cin >> l >> r;
    cout << is_2017_table[r] - is_2017_table[l-1] << endl;
  }


  return 0;
}


Measured memory_bytes: 1408
#include <stdio.h>
#include <algorithm>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>

using namespace std;

typedef long long LL;
typedef pair<int , int> P2;
typedef pair<pair<int , int> , int> P3;
typedef pair<pair<int , int> , pair<int , int> > P4;
#define Fst first
#define Snd second
#define MP(a , b) make_pair((a) , (b))
#define M3P(a , b , c) make_pair(make_pair((a) , (b)) , (c))
#define M4P(a , b , c , d) make_pair(make_pair((a) , (b)) , make_pair((c) , (d)));
#define Mx(a , b) ((a) > (b) ? (a) : (b))
#define Mn(a , b) ((a) < (b) ? (a) : (b))

const double EPS = 1e-10;
const int INF = 2147483647;

int a , b , c;

int main(){
	scanf("%d%d%d" , &a , &b , &c);
	if(a % 2 == 0 || b % 2 == 0 || c % 2 == 0){
		printf("0\n");
	} else {
		LL ans = Mn((LL)a * b , Mn((LL)b * c , (LL)c * a));
		printf("%lld\n" , ans);
	}
	return 0;
}


Measured memory_bytes: 128
// ABC159 A

#include <iostream>
#include <string>

using namespace std;

int main(){
    string str;
    cin >> str;
    for(int i=0; i<2; i++){
        if(str.at(i) != str.at(i+1)){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

#define INF 1e9

const int MAXN=16;

int n;
int d[MAXN][MAXN+1];
int dp[1<<MAXN];

bool solve(){
    scanf("%d",&n);
    if(n==0){
        return false;
    }
    //initialize
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            d[i][j]=INF;
        }
    }
    for(int i=0;i<(1<<MAXN);i++){
        dp[i]=INF;
    }
    dp[0]=0;

    //handle input
    for(int i=0;i<n;i++){
        for(int j=0;j<=n;j++){
            scanf("%d",&d[i][j]);
        }
    }

    //bit DP
    for(int cleared_stage=0;cleared_stage<(1<<n) ;cleared_stage++){
        for(int new_stage=0;new_stage<n;new_stage++){
            if (! (cleared_stage&(1<<new_stage))){
                int clear_cost = d[new_stage][0];
                
                for(int k=0;k<n ;k++){
                    if (cleared_stage&(1<<k)){
                        clear_cost=min(d[new_stage][k+1],clear_cost);
                    }
                }
                dp[cleared_stage+(1<<new_stage)] = min(dp[cleared_stage+(1<<new_stage)],dp[cleared_stage]+clear_cost);
            }
        }
    }
    printf("%d\n",dp[(1<<n)-1]);
    return true;
}


int main(){
    while(solve());
}



Measured memory_bytes: 3440
package main

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

var sc = bufio.NewScanner(os.Stdin)

func main() {
	sc.Split(bufio.ScanWords)

	n := nextInt()

	ans := 64
	for i := 0; i < n; i++ {
		v := nextInt()
		cnt := 0
		for v&1 == 0 {
			v = v >> 1
			cnt++
		}

		if ans > cnt {
			ans = cnt
		}
	}

	fmt.Println(ans)
}

func nextLine() string {
	sc.Scan()
	return sc.Text()
}

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi(sc.Text())
	if e != nil {
		panic(e)
	}
	return i
}

func anser(b bool, y string, n string) string {
	if b {
		return y
	}
	return n
}

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

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

int lose(int *ptr)
{
	int i, j;
	int temp[10];
	int sum;
	
	for (i = 0; i < 1 << 10; i++){
		for (j = 0; j < 10; j++){
			temp[j] = ptr[j];
		}
		for (j = 0; j < 10; j++){
			if (((i >> j) & 1) && (temp[j] >= 3)){
				temp[j] -= 3;
			}
		}
		
		for (j = 1; j <= 7; j++){
			while (temp[j] >= 1 && temp[j + 1] >= 1 && temp[j + 2] >= 1){
				temp[j]--;
				temp[j + 1]--;
				temp[j + 2]--;
			}
		}
		
		sum = 0;
		
		for (j = 1; j <= 9; j++){
			sum += temp[j];
		}
		if (sum == 0){
			return (0);
		}
	}
	
	return (-1);
}

int main(void)
{
	char str[14];
	char flag[10];
	int num[10], memo[10];
	int i, j;
	int ok;
	
	while (scanf("%s", str) != EOF){
		getchar();
		memset(num, 0, sizeof(num));
		memset(flag, 0, sizeof(flag));
		
		for (i = 0; i < 13; i++){
			num[str[i] - '0']++;
		}
		
		memcpy(memo, num, sizeof(num));
		
		for (i = 1; i <= 9; i++){
			memcpy(num, memo, sizeof(memo));
			if (num[i] < 4){
				memo[i]++;
				for (j = 1; j <= 9; j++){
					memcpy(num, memo, sizeof(memo));
					if (num[j] >= 2){
						num[j] -= 2;
						if (lose(num) == 0){
							flag[i] = 1;
						}
					}
				}
				
				memo[i]--;
			}
		}
		
		ok = 0;
		for (i = 1; i <= 9; i++){
			if (ok == 1 && flag[i] == 1){
				printf(" ");
			}
			if (flag[i] == 1){
				printf("%d", i);
				ok = 1;
			}
		}
		if (ok == 0){
			printf("0");
		}
		printf("\n");
	}
	
	return (0);
}

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a.at(i);
        sum += a.at(i);
        a.at(i) *= n;
    }
    
    int diff = 100000000;
    int index = 0;
    
    for (int i = 0; i < n; i++) {
        if (abs(sum - a.at(i)) < diff) {
            index = i;
            diff = abs(sum - a.at(i));
        }
    }
    
    cout << index << endl;
}

Measured memory_bytes: 256
import itertools
N,M= map(int, input().split())

n = '2'*N
m = '1'*M
l = list(n + m)

ans = 0

for x in itertools.combinations(l, 2):
  xx = int(x[0]) + int(x[1])
  if xx%2==0:
    ans += 1
print(ans)
  

Measured memory_bytes: 3060
(defn digits [n] (if-not (zero? n)(+ (mod n 10) (digits (quot n 10))) (mod n 10)))
(defn some_sums [[N,A,B]] (apply + (filter #(let [x (digits %)] (and (<= A x) (>= B x))) (range 1 (inc N)))))
(println (some_sums (map bigint(.split (read-line) " "))))

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

class Program
{
	static void Main() => new Program().Solve();

	void Solve()
	{
		var nk = ReadLongArray();
		var n = nk[0];
		var k = nk[1];
		var a = ReadLongArray();

		for (var i = k + 1; i <= n; i++) {
			Console.WriteLine(a[i - 1] > a[i - k - 1] ? "Yes" : "No");
		}
	}

	#region Console.Read 関係
	long[] ReadLongArray() => Array.ConvertAll(Console.ReadLine().Split(), long.Parse);
	long ReadLong() => long.Parse(Console.ReadLine());
	#endregion
}


Measured memory_bytes: 46284
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int N;
cin >> N;
vector<int> v;
for(int i = 0; i < 2*N; i++){
int a;
cin >> a;
v.push_back(a);
}
sort(v.begin(), v.end());
int ans = 0;
for(int i = 0; i < 2*N; i+=2){
ans+=v[i];
}
cout << ans << endl;
}

Measured memory_bytes: 256
import sys
input = sys.stdin.readline
N,K=map(int,input().split())
#x,y,c=[],[],[]
lis=[[[0]*K for _ in range(K)] for i in range(2)]
for i in range(N):
    x,y,c=input().split()
    x=int(x)
    y=int(y)
    """x.append(int(xx))
    y.append(int(yy))
    c.append(cc)"""
    if c=="B" :
        C=1
    if c=="W":
        C=0
    now=(x//K+y//K+C)%2
    lis[now][x%K][y%K]+=1
#print(lis)
for t in range(2):
    for i in range(K):
        for j in range(1,K):
            lis[t][i][j]+=lis[t][i][j-1]
    #print(lis)
    for i in range(1,K):
        for j in range(K):
            lis[t][i][j]+=lis[t][i-1][j]
            #print("A",lis)
"""for t in range(2):
    for i in range(K):
        for j in range(K):
            if i!=0 : lis[t][i][j]+=lis[t][i-1][j]
            if j!=0 : lis[t][i][j]+=lis[t][i][j-1]
            if i!=0 and j!=0:
                lis[t][i][j]-=lis[t][i-1][j-1]"""
#print(lis)
ans=0
for t in range(2):
    for i in range(K):
        for j in range(K):
            cnt=2*lis[t][i][j]+lis[t][-1][-1]-lis[t][i][-1]-lis[t][-1][j]\
            +lis[1-t][i][-1]+lis[1-t][-1][j]-2*lis[1-t][i][j]
            ans=max(ans,cnt)
"""
for i in range(K):
    for j in range(K):
        cnt=-2*lis[i][j]+lis[i][-1]+lis[-1][j]
        ans=max(ans,cnt)"""

print(ans)
#print(x,y,c)


Measured memory_bytes: 60140
#include<iostream>
#include<iomanip>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdio>
#include<set>
#include<stack>
#include<string>
#include<sstream>
#include<map>
#include<queue>
#include<vector>
using namespace std;

int main() {
	int S = 0;
	for (int i = 0; i < 10; i++) {
		int s;
		cin >> s;
		S += s;
	}
	cout << S << endl;
	return 0;
}

Measured memory_bytes: 1160
using System;

class pro{

  static void Main(){
    
    int input = int.Parse(Console.ReadLine());
    int ans = 1;
    for(int b = 2; b * b <= input; b++){
      for(int p = 2;; p++){
        int t = (int)Math.Pow(b,p);
        if(t <= input) ans = Math.Max(ans,t);
        else break;
      }
    }
    Console.WriteLine(ans);
  }
}

Measured memory_bytes: 11092
def resolve():
    mod = 10 ** 9 + 7
    n = int(input())
    dp = [0] * 4
    dp2 = dp[:]
    dp[0] = 1
    for _ in range(n):
        dp2[0] = dp[0] * 8
        dp2[1] = dp[0] + dp[1] * 9
        dp2[2] = dp[0] + dp[2] * 9
        dp2[3] = dp[1] + dp[2] + dp[3] * 10
        dp = [x % mod for x in dp2]
    print(dp[3])


if __name__ == '__main__':
    resolve()


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

int gcd(int a, int b) {
    if(b > a) return gcd(b , a);
    else if (b == 0) return a;
    else return gcd(b, a % b);
}

signed main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int X, Y;
    cin >> X >> Y;
    if(X % Y == 0) {
        cout << -1 << endl;
        return 0;
    }
    cout << X << endl;



    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FI first
#define SE second
#define EPS 1e-9
#define ALL(a) a.begin(),a.end()
#define SZ(a) int((a).size())
#define MS(s, n) memset(s, n, sizeof(s))
#define FOR(i,a,b) for (int i = (a); i <= (b); i++)
#define FORE(i,a,b) for (int i = (a); i >= (b); i--)
#define FORALL(it, a) for (__typeof((a).begin()) it = (a).begin(); it != (a).end(); it++)
#define WHATIS(x) cout << #x << " is " << x << endl;
#define ERROR(args...) { string _s = #args; replace(_s.begin(), _s.end(), ',', ' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); err(_it, args); }
//__builtin_ffs(x) return 1 + index of least significant 1-bit of x
//__builtin_clz(x) return number of leading zeros of x
//__builtin_ctz(x) return number of trailing zeros of x

using namespace std;
using ll = long long;
using ld = double;
typedef pair<int, int> II;
typedef pair<II, ll> III;
typedef complex<ld> cd;
typedef vector<cd> vcd;

void err(istream_iterator<string> it) {}
template<typename T, typename... Args>
void err(istream_iterator<string> it, T a, Args... args) {
    cout << *it << " = " << a << endl;
    err(++it, args...);
}

const ll MODBASE = 1000000007LL;
const int MAXN = 110;
const int MAXM = 35;
const int MAXK = 510;
const int MAXQ = 200010;

string s;
int x, y;
vector<int> a, b;
bool dp[10010];

bool check(vector<int> &a, int k) {
    int sum = 0;
    FOR(i,0,SZ(a)-1) sum += a[i];
    if ((sum - k) % 2) return false;
    int h = (sum - k) / 2;
    if (h < 0) return false;

    FOR(i,0,h) dp[i] = false;
    dp[0] = true;
    FOR(i,0,SZ(a)-1)
        FORE(j,h,a[i]) dp[j] |= dp[j-a[i]];
    return dp[h];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> s;
    cin >> x >> y;
    reverse(ALL(s));
    while (SZ(s) && s[SZ(s)-1] == 'F') {
        x--;
        s.pop_back();
    }
    reverse(ALL(s));
    int now = 0;
    int cnt = 0;
    s = s + "T";
    FOR(i,0,SZ(s)-1) {
        if (s[i] == 'T') {
            if (cnt) {
                if (!now) a.emplace_back(cnt);
                else b.emplace_back(cnt);
                cnt = 0;
            }
            now = 1-now;
        }
        else {
            cnt++;
        }
    }
    if (check(a, x) && check(b, y)) cout << "Yes";
    else cout << "No";
    return 0;
}

Measured memory_bytes: 384
#include <iostream>
    #include <vector>
    #include <cmath>
    #include <string>
    using namespace std;
    int main(){
        int N = 5;
        char a[N];
        scanf("%s",a);
        for(int i=0;i < N; i++){
            int j=i+1;
            if(a[i]==a[j]){
                printf("Bad\n");
                return 0;
            }
        }
        printf("Good\n");
        return 0;
    }

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

int main()
{
	int N, L;

	cin >> N >> L;

	int taste_apple[N];
	int taste_pie = 0;

	int taste_min = 1000;
	int taste_min_i;

	bool minus_flg;

	for (int i = 0; i < N; i++)
	{
		taste_apple[i] = L + i;
		taste_pie += taste_apple[i];

		if (abs(taste_apple[i]) < abs(taste_min))
		{
			taste_min = abs(taste_apple[i]);
			taste_min_i = i;
		}
	}

	int ans = taste_pie - taste_apple[taste_min_i];

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define rep2(i, n) for (int i = 1; i <= (int)(n); i++)
#define ll long long
#define umap unordered_map
using graph = vector<vector<int>>;
using graph2 = vector<vector<pair<int, int>>>;

ll mod(ll x, ll y){if(x>=0||x%y==0) return x%y;return y+x%y;} //mod including minus
ll dv0(ll x, ll y){if(x>=0||x%y==0)return x/y;return x/y-1;} //rnd down
ll dv1(ll x, ll y){if(x%y==0) return dv0(x,y);return dv0(x,y)+1;} //rnd up
ll M=1e9+7;
int quick_pow(int x,int p){
    int a=1,po=x;
    while(p){
        if(p&1)  a=1ll*a*po%M;
        po=1ll*po*po%M;p>>=1;
    }
    return a;
}
//Start from Here
int main(){
    int N, M;
    cin>>N>>M;
    int H[N];
    rep(i, N){
        cin>>H[i];
    }
    vector<int> G[N];
    int a, b;
    rep(i, M){
        cin>>a>>b;
        G[a-1].push_back(b-1);
        G[b-1].push_back(a-1);
    }
    int cnt=0;
    int check;
    rep(i, N){
        if(G[i].size()==0){
            cnt++;
        }else{
            check=0;
            rep(j, G[i].size()){
                if(H[i]<=H[G[i].at(j)]){
                    check=1;
                }
            }
            if(check==0){
                cnt++;
            }
        }
    }
    cout<<cnt<<endl;
}

Measured memory_bytes: 9120
import sys
import math


class Circle:
    def __init__(self, x, y, r):
        self.x = x
        self.y = y
        self.r = r

    def distance(self, other):
        dx = self.x - other.x
        dy = self.y - other.y
        return math.sqrt(dx ** 2 + dy ** 2)

    def intersection(self, other):
        d = self.distance(other)
        if self.r > d + other.r:
            return 2
        elif other.r > d + self.r:
            return -2
        elif d <= self.r + other.r:
            return 1
        else:
            return 0


#input_file = open(sys.argv[1], "r")

sys.stdin.readline()

for line in sys.stdin:
    (xa, ya, ra, xb, yb, rb) = tuple(map(float, line.split(' ')))
    ca = Circle(xa, ya, ra)
    cb = Circle(xb, yb, rb)
    print ca.intersection(cb)

Measured memory_bytes: 4432
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <sstream>
#include <stack>
#include <queue>
#include <list>
#include <stdio.h>
#include <algorithm>
#define MAX 50000
#define INF 100000000
using namespace std;
typedef long long ll;
int t[MAX+1],c[21];
int main()
{	
	int n,m; 
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>c[i];
	}
	for(int i=1;i<=n;i++) t[i]=INF;
	t[0]=0;
	for(int i=1;i<=m;i++)
	{
		for(int j=0;j+c[i]<=n;j++)
		{
			t[j+c[i]]=min(t[j+c[i]],t[j]+1);//在可以用该币凑出该价格时，用或者不用 
		}
	}
	cout<<t[n]<<endl;
}


Measured memory_bytes: 3288
#include <stdio.h>
#include <algorithm>
#include <assert.h>
#include <bitset>
#include <cmath>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits.h>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
//#include <unordered_map>
//#include <unordered_set>
#include <vector>

#pragma warning(disable:4996)
#pragma comment(linker, "/STACK:33554432")
using namespace std;

#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define ldb ldouble
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);

typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <ll, int> pli;
typedef pair <db, db> pdd;
//typedef tuple <int, int, int> t3;

int IT_MAX = 1 << 18;
const ll MOD = 1000000009;
const int INF = 0x3f3f3f3f;
const ll LL_INF = 1234567890123456789ll;
const db PI = acos(-1);
const db EPS = 1e-8;
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)

class edge {
public:
	int s, e, f;
	int of;
	edge() {
		*this = edge(0, 0, 0);
	}
	edge(int s, int e, int f) : s(s), e(e), f(f) {}
};
vector <edge> E;
vector <int> fconn[100050];
void epush(int s, int e, int f) {
	fconn[s].push_back(E.size());
	fconn[e].push_back(E.size() + 1);
	E.emplace_back(s, e, f);
	E.emplace_back(e, s, 0);
}
int dchk[100050];
int DFS(int n, int snk, int C, int F) {
	if (n == snk) return F;
	dchk[n] = C;
	for (auto it : fconn[n]) {
		edge& ed = E[it];
		if (ed.f == 0 || dchk[ed.e] == C) continue;
		int t;
		if (t = DFS(ed.e, snk, C, min(F, ed.f))) {
			ed.f -= t;
			E[it ^ 1].f += t;
			return t;
		}
	}
	return 0;
}
void init(int snk) {
	int i;
	for (i = 0; i <= snk; i++) {
		fconn[i].clear();
		dchk[i] = false;
	}
	E.clear();
}

bool pchk[10000050];

vector <int> Va;
set <int> Sx;
int in[105];

vector <int> V1;
vector <int> V2;
int main() {
	int N, i, j;

	pchk[1] = true;
	for (i = 2; i <= 10000030; i++) {
		if (pchk[i]) continue;
		for (j = 2 * i; j <= 10000030; j += i) pchk[j] = true;
	}

	scanf("%d", &N);
	for (i = 1; i <= N; i++) {
		scanf("%d", &in[i]);
		Va.push_back(in[i] - 1);
		Va.push_back(in[i]);
		Sx.insert(in[i]);
	}
	sort(all(Va));
	for (i = 0; i < Va.size(); i++) {
		int t = 0;
		if (Sx.count(Va[i])) t ^= 1;
		if (Sx.count(Va[i] + 1)) t ^= 1;
		if (!t) continue;
		if (Va[i] % 2) V1.push_back(Va[i]);
		else V2.push_back(Va[i]);
	}

	int src = V1.size() + V2.size();
	int snk = src + 1;
	for (i = 0; i < V1.size(); i++) epush(src, i, 1);
	for (i = 0; i < V2.size(); i++) epush(i + V1.size(), snk, 1);
	for (i = 0; i < V1.size(); i++) {
		for (j = 0; j < V2.size(); j++) {
			int t = abs(V1[i] - V2[j]);
			if (!pchk[t]) epush(i, V1.size() + j, 1);
		}
	}
	
	int f = 0;
	while (DFS(src, snk, f + 1, INF)) f++;

	int ans = f;
	int t1 = (int)V1.size() - f, t2 = (int)V2.size() - f;
	ans += (t1 / 2 + t2 / 2) * 2;
	if (t1 % 2) ans += 3;
	return !printf("%d\n", ans);
}

Measured memory_bytes: 13184
#include <bits/stdc++.h>
#include <chrono>
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1000000007
using namespace std;
random_device rd{};

void init_yotei_and_last(long *yotei, long *last, long d, long n){
  rep(i,d)yotei[i] = rd()%n;
  rep(i,n)last[i] = 0;
}

int change_yotei(long *days, long *yotei, long *pre_cons, long n, long d, long ii){
  vector<bool> flag(d,false);
  long new_con;
  int change_num = (100050-ii)/2000 + 1;
  rep(i,change_num){
    while(1){
      int day = rd()%d;
      if(flag[day] == false){
        days[i] = day;
        flag[day] = true;
        break;
      }
    }
    while(1){
      new_con = rd()%n;
      if(yotei[days[i]] != new_con){
        pre_cons[i] = yotei[days[i]];
        yotei[days[i]] = new_con;
        break;
      }
    }
  }
  return change_num;
}

int main(){
  chrono::system_clock::time_point start,end;
  start = chrono::system_clock::now();
  long d;
  cin >> d;
  long n = 26, csum = 0, ccost = 0;
  long c[n];
  rep(i,n){
    cin >> c[i];
    csum += c[i];
  }
  long s[d][n];
  rep(i,d)rep(j,n)cin >> s[i][j];
  vector<vector<long>> cand;
  vector<long> tmp(d);
  long yotei[d];
  long final_ans = 0, final_index = 0;
  long last[n];

  rep(jj,20){
    long ans = 0;
    init_yotei_and_last(yotei, last, d, n);
    rep(i,d){
      ccost += csum;
      ccost -= c[yotei[i]]*(i+1 - last[yotei[i]]);
      ans -= ccost;
      last[yotei[i]] = i+1;
      ans += s[i][yotei[i]];
    }
    int ii = 0;
    long days[60],pre_cons[60];
    while(ii < 100000){
      int change_num = change_yotei(days,yotei,pre_cons,n,d,ii);
      long tmpans = 0;
      ccost = 0;
      rep(i,n)last[i] = 0;
      rep(i,d){
        tmp[i] = yotei[i];
        ccost += csum;
        ccost -= c[yotei[i]]*(i+1 - last[yotei[i]]);
        tmpans -= ccost;
        last[yotei[i]] = i+1;
        tmpans += s[i][yotei[i]];
      }
      if(tmpans < ans){
        rep(i,change_num)yotei[days[i]] = pre_cons[i];
      }else{
        ans = tmpans;
        cand.push_back(tmp);
      }
      ii++;
    }
    if(final_ans < ans){
      final_ans = ans;
      final_index = int(cand.size()-1);
    }
    end = chrono::system_clock::now();
    auto time = end - start;
    if(static_cast<double>(chrono::duration_cast<chrono::milliseconds>(time).count()) > 1000)break;
  }
  rep(i,d)cout << cand[final_index][i]+1 << endl;
  return 0;
}

Measured memory_bytes: 5676
#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define pb push_back
using namespace std;
using ll = long long;
using vi = vector<ll>;
using pi = pair<ll, ll>;
const int maxn = 4e5 + 4433, mod = 998244353;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct node
{
    int mx;
    node() { mx = -1e9; }
    node(int val) { mx = val; }
};

node temp;

node merge(node l, node r)
{
    temp.mx = max(l.mx, r.mx);
    return temp;
}

struct segment_tree
{
    int n;
    node t[2 * maxn];

    void init(int sz)
    {
        n = sz;
        for(int i = 0; i < n; i++) t[i + n] = node();
        for(int i = n - 1; i > 0; --i)
            t[i] = merge(t[i << 1], t[i << 1 | 1]);
    }

    void modify(int p, const node& value)
    {
        for(t[p += n] = value; p >>= 1; )
            t[p] = merge(t[p << 1], t[p << 1 | 1]);
    }

    node query(int l, int r)
    {
        node resl, resr;
        for(l += n, r += n; l < r; l >>= 1, r >>= 1)
        {
            if(l & 1) resl = merge(resl, t[l++]);
            if(r & 1) resr = merge(t[--r], resr);
        }

        return merge(resl, resr);
    }
};
int n;
vector<pi> a;
vi coords;
segment_tree s;
int seg[maxn];
int dp[maxn];
void solve() {
	dp[0] = 1;
	for(int i = 0; i < n; i++) {
		(dp[i+1] += dp[i])%=mod;
		(dp[seg[i]+1] += dp[i])%=mod;
	}
	cout << dp[n];
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	a.resize(n);
	for(auto &i : a) cin >> i.first >> i.second, coords.pb(i.first);
	sort(all(coords));
	coords.erase(unique(all(coords)), coords.end());
	for(auto &i : a) i.first = lower_bound(all(coords), i.first)-coords.begin();
	sort(all(a));
	s.init(4e5 + 333);
	for(int i = n; i--;) {
		int x = a[i].first, d = a[i].second;
		int ox = coords[a[i].first]+d-1;
		int t = max(i,  s.query(a[i].first, upper_bound(all(coords), ox)-coords.begin()).mx);
		s.modify(x, t);
		seg[i] = t;
	}
	solve();
}



Measured memory_bytes: 10608
//Jai Bhole Ki
#include <bits/stdc++.h>
using namespace std;
#define fast static int fastline = []() { std::ios::sync_with_stdio(false); cin.tie(NULL); return 0; }();
#define ll long long
#define LL unsigned ll
#define pb push_back
#define pi pair<ll,ll>
#define debug(x) cout<<x<<"\n";
#define debug cout<<"debugged\n";
#define minval -2e9
#define maxval 1e9
long double PI =3.14159265358979323846;
 
const ll M=1e12;
const ll inf=1e18;
const ll ms=10000000;
fast;
ll ans,n,m;
void solve()
{
    cin>>n;ll ar[n+2];
    for(int i=1;i<=n;i++)
    {
        cin>>ar[i];
    }
    for(int i=2;i<n;i++)
    {
        if(ar[i-1]<ar[i]&&ar[i]<ar[i+1])
            ans++;
        else if(ar[i-1]>ar[i]&&ar[i]>ar[i+1])
            ans++;
    }
   cout<<ans<<endl;
    
}
int main()
{
    solve();
    return 0;
}

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

int main(){
  long n;
  cin >> n;
  bool b=false;
  for(int i=1;i<10;i++){
  	if(n%i==0 && n/i<10){
    	b=true;
    }
  }
  if(b)cout << "Yes";
  else cout << "No";
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <unordered_map>

using namespace std;

typedef unsigned long long ull;

ull N,V;
ull p[4][1001];

ull solve() {
  unordered_map<ull, ull> c[2];
  for (int i=0; i<2; ++i) {
    for (int j=0; j<N; ++j) {
      for (int k=0; k<N; ++k) {
        ++c[i][p[i*2][j]+p[i*2+1][k]];
        //cout<<i<<" "<<j<<" "<<k<<" "<<p[i*2][j]+p[i*2+1][k]<<" "<<c[i][p[i*2][j]+p[i*2+1][k]]<<endl;
      }
    }
  }
  ull ans = 0;
  for(unordered_map<ull, ull>::const_iterator it = c[0].begin(); it != c[0].end(); ++it) {
    if (V > it->first) {
      ans += (it->second)*c[1][V-it->first];
    }
  }
  return ans;
}

int main() {
  cin>>N>>V;
  for (int i=0; i<4; ++i) {
    for (int j=0; j<N; ++j) {
      cin>>p[i][j];
    }
  }
  cout<<solve()<<endl;
  return 0;
}


Measured memory_bytes: 121476
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define REP(i, l, r) for (int i=(l); i<(r); ++i)
#define RREP(i, r, l) for (int i=(r); i>(l); --i)
#define popcount __builtin_popcountll
 
const int INF = 1LL<<60;
const int MOD = 1000000007;
 
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
 
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ")";
}
 
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> t) {
    return "(" + to_string(get<0>(t)) + ", " + to_string(get<1>(t)) + ", " + to_string(get<2>(t)) + ", " + to_string(get<3>(t)) + ")";
}
 
template <typename A>
string to_string(vector<A> v) {
    bool first = true;
    string result = "[";
    for (A i : v) {
        if (!first) result += ", ";
        first = false;
        result += to_string(i); 
    }
    return result + "]";
}
 
template <typename A>
string to_string(A x[], int n) {
    string result = "{";
    REP(i, 0, n) {
        if (i!=0) result += ", ";
        result += to_string(x[i]); 
    }
    return result + "}";
}
 
string bin_string(int x) {
    const int d = 64;
    string result(d, ' ');
    REP(i, d-1, -1) result[d-1-i] = '0'+((x&1LL<<i)!=0);
    return result;
}
 
vector<int> getZ(string s) {
    int n = s.size();
    vector<int> z(n);
    int x = 0, y = 0;
    REP(i, 1, n) {
        z[i] = max(0LL, min(z[i-x], y-i+1));
        while (i+z[i] < n && s[z[i]] == s[i+z[i]]) {
            x = i;
            y = i+z[i];
            ++z[i];
        }
    }
    return z;
}
 
int powa(int base, int exp) {
    if (exp<=0) return 1;
    if (base<=0) return 0;
    int val = powa(base, exp>>1);
    val = val*val % MOD;
    if (exp&1) {
        val = val*base % MOD;
    }
    return val;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    
    string s;
    cin >> s;
    int n = s.size();
    int res = 0;
    REP(i, 0, n/2) {
        if (s[i] != s[n-i-1]) {
            ++res;
        }
    }
    cout << res;
}

Measured memory_bytes: 256
#include<stdio.h>

int A[1000000],n;

int binarySearch(int key){
  int left=0;
  int right=n;
  int mid;
  while(left<right){
    mid=(left+right)/2;
    if(key==A[mid])return 1;
    if(key>A[mid])left=mid+1;
    else if(key<A[mid])right=mid;
  }
  return 0;
}

int main(){
  int i,q,k,sum=0;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }

  scanf("%d",&q);
  for(i=0;i<q;i++){
    scanf("%d",&k);
    if(binarySearch(k)) sum++;
  }
  printf("%d\n",sum);

  return 0;
}



Measured memory_bytes: 2112
#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
#define rep(i, s, N) for(ll i{s}; i < N; i++)
using namespace std;using ll = long long int;const int MOD = (int)1e9+7;template<class T>vector<T> mvec(size_t a){return vector<T>(a);}template<class T, class... Ts>auto mvec(size_t a, Ts... ts){return vector<decltype(mvec<T>(ts...))>(a, mvec<T>(ts...));}

int main(){
  string S;
  cin >> S;
  ll N = S.size(); reverse(all(S));
  auto DP = mvec<ll>(N+1,13); DP[0][0] = 1;
  auto d13 = [](ll n) -> ll{
    return (13 + n % 13)%13;
  };
  auto deal = [&](ll i, ll j, ll l) -> void{
    ll k{};
    k = l + d13(j*pow(10, i%3)) * pow(-1, i/3);
    DP[i+1][d13(k)] += DP[i][l]%MOD;
  };
  rep(i, 0, N) rep(l, 0, 13){
    if(S[i] == '?') rep(j, 0, 10) deal(i, j, l);
    else deal (i, S[i] - '0', l);
  }
  cout << DP[N][5]%MOD << "\n";
}

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

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> Vi;
typedef tuple<int, int, int> T;
#define FOR(i,s,x) for(int i=s;i<(int)(x);i++)
#define REP(i,x) FOR(i,0,x)
#define ALL(c) c.begin(), c.end()
#define DUMP( x ) cerr << #x << " = " << ( x ) << endl

#define INF 1<<30
#define MAX_V 1024

// graph by adjacency list
struct Edge {
  int dst, weight;
  Edge(int dst, int weight) :
    dst(dst), weight(weight) { }
  bool operator < (const Edge &e) const {
    return weight > e.weight;
  }
};

struct Graph {
  int V;
  std::vector<Edge> E[MAX_V];

  Graph(int V) : V(V) { }

  void add_edge(int src, int dst, int weight) {
    E[src].push_back(Edge(dst, weight));
  }
};

struct ShortestPath {
  const Graph g;
  int start;
  int dist[MAX_V], prev[MAX_V];
  bool negative_loop;

  ShortestPath(const Graph g, int start) :
    g(g), start(start) { }

  void bellman_ford() {
    negative_loop = false;
    std::fill(dist, dist + g.V, INF);
    dist[start] = 0;
    prev[start] = -1;
    for (int cnt = 0; cnt < g.V; cnt++) {
      bool update = false;
      for (int i = 0; i < g.V; i++) {
	for (Edge e : g.E[i]) {
	  if (dist[i] != INF && dist[i] + e.weight < dist[e.dst]) {
	    dist[e.dst] = dist[i] + e.weight;
	    prev[e.dst] = i;
	    if (cnt == g.V - 1) negative_loop = true;
	    update = true;
	  }
	}
      }
      if (!update) break;
    }
  }

  vector<int> build_path(int goal) {
    vector<int> path;
    for (int v = goal; v != -1; v = prev[v]) {
      path.push_back(v);
    }
    std::reverse(path.begin(), path.end());
    return path;
  }

  bool has_negative_loop() {
    return negative_loop;
  }
};

int main() {
  // use scanf in CodeForces!
  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int V, E, start;
  cin >> V >> E >> start;

  Graph g(V);
  REP(i, E) {
    int src, dst, weight;
    cin >> src >> dst >> weight;
    g.add_edge(src, dst, weight);
  }

  ShortestPath sp(g, start);
  sp.bellman_ford();
  if (sp.has_negative_loop()) {
    cout << "NEGATIVE CYCLE" << endl;
  } else {
    REP(i, g.V) {
      if (sp.dist[i] == INF) {
	cout << "INF" << endl;
      } else {
	cout << sp.dist[i] << endl;
      }
    }
  }  

  return 0;
}

Measured memory_bytes: 1384