akhauriyash/Code-Regression huggingface dataset:
#関数リスト
import sys
input = sys.stdin.readline


def RD(): return input().rstrip()
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float,input().split()))

def main():
    while True:
        n, x = MI()
        if n == 0 and x == 0:
            exit()
        result = 0
        for i in range(1,n+1):
            for j in range(i+1,n+1):
                k = x - i - j
                if k > j and k <= n:
                    result += 1
        print(result)

if __name__ == "__main__":
    main()



Measured memory_bytes: 5604
n = int(input())
a = list(map(int, input().split()))
occur = [0 for i in range(n + 1)]
MOD = 1000000007
for i in range(n + 1):
    if occur[a[i]] > 0: val = n - 1 - i + occur[a[i]]
    else: occur[a[i]] = i + 1
inv = [0 if i > 2 else 1 for i in range(n + 2)]
pinv = [0 if i > 2 else 1 for i in range(n + 2)]
perm = [0 if i > 2 else 1 for i in range(n + 2)]
for i in range(2, n + 2):
    inv[i] = -int(MOD / i) * inv[MOD % i] + MOD
    pinv[i] = pinv[i - 1] * inv[i] % MOD
    perm[i] = perm[i - 1] * i % MOD
def C(n, m):
    return (perm[m] * pinv[n] % MOD) * pinv[m - n] % MOD if n <= m else 0
for i in range(1, n + 2):
    temp = C(i, n + 1) - C(i - 1, val)
    if temp < 0: temp += MOD
    print(temp)


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

#define int long long

class  Node{ public: int location; int p,l,r; Node(){} };
class Point{ 
public: 
  int id,x,y;
  Point(){}
  Point(int id,int x,int y):id(id),x(x),y(y){}
  bool operator < (const Point &p)const{ return id < p.id; }
  void print(){printf("%d\n",id);}
};

static const int MAX = 1000000ll;
static const int NIL = -1ll;

int N; // Num_of_Point
Point P[MAX];Node T[MAX];
int np;

bool lessX(const Point &p1, const Point &p2){return p1.x<p2.x;}
bool lessY(const Point &p1, const Point &p2){return p1.y<p2.y;}

int makeKDTree(int l,int r,int depth){
  if(!(l<r))return(NIL);
  int mid=(l+r)/2;
  int t=np++;
  if(!(depth%2))sort(P+l,P+r,lessX);
  else          sort(P+l,P+r,lessY);
  T[t].location = mid;
  T[t].l = makeKDTree(l,mid,depth+1);
  T[t].r = makeKDTree(mid+1,r,depth+1);

  return(t);
}
  
void find(int v,int sx,int tx,int sy,int ty,int depth,vector<Point>&ans){
  int x = P[T[v].location].x , y = P[T[v].location].y;
  
  if(sx<=x && x<=tx && sy<=y && y<=ty)ans.push_back(P[T[v].location]);
  if(!(depth%2)){
    if(T[v].l != NIL && sx<=x)find(T[v].l,sx,tx,sy,ty,depth+1,ans);
    if(T[v].r != NIL && x<=tx)find(T[v].r,sx,tx,sy,ty,depth+1,ans);
  }
  else{
    if(T[v].l != NIL && sy<=y)find(T[v].l,sx,tx,sy,ty,depth+1,ans);
    if(T[v].r != NIL && y<=ty)find(T[v].r,sx,tx,sy,ty,depth+1,ans);
  }
}

main(){
  int q; // Num_of_query
  int x,y; // Place of Point
  int sx,tx,sy,ty; // sx -> tx , sy -> ty [ wide and tall ]
  
  scanf("%lld",&N);
  for(int i=0;i<N;i++){
    scanf("%lld %lld",&x ,&y);
    P[i] = Point(i,x,y); T[i].l = T[i].r = T[i].p = NIL;
  }

  np=0;
  int root = makeKDTree(0,N,0);
  vector<Point>ans;

  scanf("%lld",&q);
  for(int i=0;i<q;i++){
    scanf("%lld %lld %lld %lld",&sx,&tx,&sy,&ty);
    ans.clear();
    find(root,sx,tx,sy,ty,0,ans);
    sort(ans.begin(),ans.end());
    for(int j=0;j<ans.size();j++)ans[j].print();printf("\n");
  }
  
  return(0);
}

// DSL_2_C Range-Search

Measured memory_bytes: 29768
#include <bits/stdc++.h>
using namespace std;
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	string s;
	cin >> s;
	if(s.size()  < 6)cout << "No",exit(0);
	if(s[2] == s[3] && s[4] == s[5])cout << "Yes",exit(0); else cout << "No";
	return 0;
}

Measured memory_bytes: 384
Uses math;
var n,m,a,s,i:Longint;
begin
	s:=round(1e9);
	read(n,m);
	for i:=1 to n do
	begin
		read(a);
		m:=m-a;
		if s>a then s:=a;
	end;
	write(n+floor(m/s))
end.


Measured memory_bytes: 128
//
// AOJ0168　
// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0168
//  implementation-1: 配るDP
//

#include <iostream>
using namespace std;

const long long INF = 1LL << 60;
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; }

const int iMax=30+3;
long long dp[iMax];

long long calc(int n) {
	for(int i=0; i<iMax; i++) dp[i]=0;
	dp[0]=1;
	
	for(int i=0; i<=n; i++) {
		dp[i+1] = dp[i+1] + dp[i];
		dp[i+2] = dp[i+2] + dp[i];
		dp[i+3] = dp[i+3] + dp[i];
	}
	
	return dp[n];
}


int main() {
	int N=1;
	while (N!=0) {
		cin >> N;
		if (N==0) break;
		long long ans = calc(N);
		ans = (ans-1)/3650 +1;
		cout << ans << endl;
	}	

	return 0;
}



Measured memory_bytes: 3088
#include <stdio.h>
#include <cctype>
#include <limits.h>
#include <math.h>
#include <complex>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <cstring>
#include <string>
#include <sstream>
#include <algorithm>
#include <iomanip>
#include <iostream>

#define VARIABLE(x) cerr << #x << "=" << x << endl
#define BINARY(x) static_cast<bitset<16> >(x);
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define REP(i,m,n) for (int i=m;i<(int)(n);i++)
#define if_range(x, y, w, h) if (0<=(int)(x) && (int)(x)<(int)(w) && 0<=(int)(y) && (int)(y)<(int)(h))

const int INF = 1000000000;
const double EPS = 1e-8;
const double PI = 3.14159;
int dx[4]={0, 1, 0, -1}, dy[4]={-1, 0, 1, 0};
using namespace std;
typedef pair<int, int> P;



/** Problem2259 : Programming Contest **/
int main()
{
	int M, N;
	cin>>M>>N;
	
	int ans=0;
	rep(i, M) {
		int t=0;
		rep(i, N) {
			int a; cin>>a;
			if (a) t++;
		}
		ans = max(ans, t);
	}
	
	cout << ans << endl;
}

Measured memory_bytes: 1160
<?php
// C
fscanf(STDIN, '%d', $n);
$v = array_map('intval', explode(' ', trim(fgets(STDIN))));

for ($i = 0; $i < $n; $i++) {
    if ($i % 2 === 0) {
        if (isset($vk_cnt[$v[$i]])) {
            $vk_cnt[$v[$i]]++;
        } else {
            $vk_cnt[$v[$i]] = 1;
        }
    } else {
        if (isset($vg_cnt[$v[$i]])) {
            $vg_cnt[$v[$i]]++;
        } else {
            $vg_cnt[$v[$i]] = 1;
        }
    }
}
$qk = new SplPriorityQueue;
$qg = new SplPriorityQueue;

foreach ($vk_cnt as $i => $cnt) {
    $qk->insert([$i, $cnt], $cnt);
}
foreach ($vg_cnt as $i => $cnt) {
    $qg->insert([$i, $cnt], $cnt);
}

$vk = $qk->extract();
$vg = $qg->extract();
if ($vk[0] === $vg[0]) {
    if (!$qk->isEmpty()) {
        $vk2 = $qk->extract();
    } else {
        $vk2 = [-1, 0];
    }

    if (!$qg->isEmpty()) {
        $vg2 = $qg->extract();
    } else {
        $vg2 = [-1, 0];
    }

    if ($vk[1] + $vg2[1] > $vk2[1] + $vg[1]) {
        $vg = $vg2;
    } else {
        $vk = $vk2;
    }
}
$ans = count($v) - $vk[1] - $vg[1];
echo $ans;

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

const int mxN = 22, mod = 1e9 + 7;
int N, a[mxN][mxN];
int dp[mxN][1 << mxN];

int rec(int m, int w) {
	if (m == N) {
		if (w == 0) {
			return 1;
		}
		return 0;
	}
	if (dp[m][w] != -1) {
		return dp[m][w];
	}
	ll tot = 0;
	for (int i = 0; i < N; i++) {
		int woman = 1 << i;
		bool okay = ((w & woman) == 0)? false : true;
		if (okay && a[m][i]) {
			tot = (tot + rec(m + 1, w ^ woman)) % mod;
		}
	}
	return dp[m][w] = tot;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> a[i][j];
		}
	}
	memset(dp, -1, sizeof(dp));
	int ans = rec(0, (1 << N) - 1);
	cout << ans;
	
	return 0;
}


Measured memory_bytes: 364088
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define int long long
#define endl '\n'
#define pb push_back
#define fi first
#define se second
#define all(c) (c).begin(),(c).end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

#define TRACE
#ifndef ONLINE_JUDGE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
	cerr << name << " : " << arg1 << endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
	const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...)
#endif

const ll inf = 2e18;
const int mod = 1e9 + 7;
const int N = 1e5 + 10;

int n, m;
vi g[N];
int dp[N], dp2[N];

void dfs(int v, int p) {
	dp[v] = 1;
	for(auto it : g[v]) {
		if(it != p) {
			dfs(it, v);
			dp[v] = dp[v] * (1 + dp[it]) % m;
		}
	}
}

void dfs2(int v, int p) {
	int sz = g[v].size();
	if(sz) {
		int pref[sz], suff[sz];
		pref[0] = (1 + ((g[v][0] == p) ? 0 : dp[g[v][0]])) % m;
		suff[sz - 1] = (1 + ((g[v][sz - 1] == p) ? 0 : dp[g[v][sz - 1]])) % m;
		for(int i = 1; i < sz; i++) {
			pref[i] = pref[i - 1] * (1 + ((g[v][i] == p) ? 0 : dp[g[v][i]])) % m;
		}
		for(int i = sz - 2; i >= 0; i--) {
			suff[i] = suff[i + 1] * (1 + ((g[v][i] == p) ? 0 : dp[g[v][i]])) % m;
		}
		for(int i = 0; i < sz; i++) {
			if(g[v][i] != p) {
				dp2[g[v][i]] = (1 + dp2[v] * ((i > 0) ? pref[i - 1] : 1) % m * ((i < sz - 1) ? suff[i + 1] : 1) % m) % m;
				dfs2(g[v][i], v);
			}
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for(int i = 0; i < n - 1; i++) {
		int u, v;
		cin >> u >> v;
		g[u].pb(v);
		g[v].pb(u);
	}
	dfs(1, -1);
	dp2[1] = 1;
	dfs2(1, -1);
	for(int i = 1; i <= n; i++) {
		cout << (dp[i] * dp2[i] % m) << endl;
	}

	return 0;
}

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

int main() {
  int n, i;
  cin >> n;
  vector<int> a(n);
  for(i = 0; i < n; i++) cin >> a.at(i);
  sort(a.begin(), a.end());
  cout << a.at(n - 1) - a.at(0) << endl;
}

Measured memory_bytes: 256
process.stdin.resume();
process.stdin.setEncoding('utf8');

var lines = [];
var reader = require('readline').createInterface({
  input: process.stdin,
  output: process.stdout
});
reader.on('line', (line) => {
  lines.push(line);
});
reader.on('close', () => {
    const [Q, H, S, D] = lines[0].split(" ").map(v=>BigInt(v));
    const N = BigInt(lines[1]);
    if(N%2n==0n){
        const unit = min(Q*8n, H*4n, S*2n, D);
        log(N/2n*unit);
    }else{
        const unit1 = min(Q*4n, H*2n, S);
        const unit2 = D;
        if(unit1*2n < D){
            log(N*unit1);
        }else{
            log((N-1n)/2n * unit2 + unit1);
        }
    }
});

min = (...a) => {return a.reduce((a,b)=>a<b?a:b, a[0])}
log = (a)=>{console.log(a.toString())};


Measured memory_bytes: 30016
#include <bits/stdc++.h>
using namespace std;
 
int main(){
  int N;
  int count=0;
  int a[200100];
  cin>>N;
  
  for(int i=0;i<N;i++){
    cin>>a[i];
  }
  
  int temp=a[0];
  for(int i=1;i<N;i++){
    if(a[i]<temp){
      count++;
      temp=a[i];
    }
  }

    cout<<count+1<<endl;
    return 0;
}

Measured memory_bytes: 1024
#define _CRT_SECURE_NO_WARNINGS
#define _USE_MATH_DEFINES
#include <iostream>
#include <cstdio>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
const int num = 100000;
vector<int> m[num];
int n, c[num], pn[num], lo[num], p[num];
int tim = 0;
inline void art(int cu, int pre) {
	pn[cu] = lo[cu] = tim++;
	c[cu] = 1;
	for (int i = 0; i < m[cu].size(); i++) {
		int v = m[cu][i];
		if (!c[v]) {
			p[v] = cu;
			art(v, cu);
			lo[cu] = min(lo[cu], lo[v]);
		}
		else if (v != pre) lo[cu] = min(pn[v], lo[cu]);
	}
}
int main() {
	int e, s, t;
	cin >> n >> e;
	for (int i = 0; i < e; i++) {
		scanf("%d%d", &s, &t);
		m[s].push_back(t);
		m[t].push_back(s);
	}
	for (int i = 0; i < n; i++) c[i] = 0;
	art(0, -1);
	set<int> ans;
	int cn = 0;
	for (int i = 1; i < n; i++) {
		int v = p[i];
		if (v == 0) cn++;
		else if (pn[v] <= lo[i]) ans.insert(v);
	}
	if (cn >= 2) ans.insert(0);
	for (set<int>::iterator it = ans.begin(); it != ans.end(); it++)
		cout << *it << endl;
	return 0;
}

Measured memory_bytes: 6736
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "math.h"
#include "utility"
#include "string"
#include "map"
#include "unordered_map"
#include "iomanip"
#include "random"

using namespace std;
const long long int MOD = 1000000007;

long long int power(long long int x, long long int n, long long int M) {
	long long int tmp = 1;

	if (n > 0) {
		tmp = power(x, n / 2, M);
		if (n % 2 == 0) tmp = (tmp*tmp) % M;
		else tmp = (((tmp*tmp) % M)*x) % M;
	}
	return tmp;
}

long long int N, M, K, Q, W, H, L, R;
long long int ans;

using namespace std;


int main() {
	ios::sync_with_stdio(false);
	cin >> N;
	string s[1000] = {};
	for (int i = 0; i < N; i++)cin >> s[i];
	cin >> M;
	string t;
	bool door = true;
	for (int i = 0; i < M; i++) {
		cin >> t;
		bool f = false;
		for (int j = 0; j < N; j++) {
			if (t == s[j])f = true;
		}
		if (f) {
			if (door) {
				cout << "Opened by " << t << endl;
			}
			else {
				cout << "Closed by " << t << endl;
			}
			door ^= true;
		}
		else {
			cout << "Unknown " << t << endl;
		}
	}
	return 0;
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

template<class V,int NV> class SegTree_3 {
public:
	vector<pair<V,int> > val;
	vector<pair<V,int> > ma;
	static V const def=1LL<<50;
	SegTree_3(){
		int i;
		val.resize(NV*2); ma.resize(NV*2);
		FOR(i,NV) val[i+NV]=ma[i+NV]=make_pair(0,i);
		FOR(i,NV) val[i]=make_pair(0,0);
		for(i=NV-1;i>=1;i--) ma[i]=min(ma[2*i],ma[2*i+1]);
	};
	
	pair<V,int> getval(int x,int y,int l=0,int r=NV,int k=1) {
		if(r<=x || y<=l) return make_pair(def,0);
		if(x<=l && r<=y) return ma[k];
		auto a=min(getval(x,y,l,(l+r)/2,k*2),getval(x,y,(l+r)/2,r,k*2+1));
		a.first += val[k].first;
		return a;
	}
	
	void update(int x,int y, V v,int l=0,int r=NV,int k=1) {
		if(l>=r) return;
		if(x<=l && r<=y) {
			val[k].first+=v;
			ma[k].first+=v;
		}
		else if(l < y && x < r) {
			update(x,y,v,l,(l+r)/2,k*2);
			update(x,y,v,(l+r)/2,r,k*2+1);
			ma[k]=min(ma[k*2],ma[k*2+1]);
			ma[k].first += val[k].first;
		}
	}
};
int N;
ll A[101010];
ll B[101010];
ll SA[101010];
ll SB[101010];

SegTree_3<ll,1<<19> D,F;


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	FOR(i,N) {
		cin>>A[i];
		SA[i+1]=SA[i]+A[i];
	}
	ll ret=0;
	FOR(i,N) {
		cin>>B[i];
		SB[i+1]=SB[i]+B[i];
		if(SA[i+1]>SB[i+1]) {
			F.update(i,i+1,SA[i+1]-SB[i+1]);
			D.update(0,i+1,-1);
		}
		else {
			F.update(i,i+1,1LL<<50);
			D.update(0,i+1,1);
		}
		ret += abs(SB[i+1]-SA[i+1]);
	}
	
	ll flow=SA[N]-SB[N];
	while(flow) {
		
		while(1) {
			auto f=F.getval(0,N);
			if(f.first>0) break;
			D.update(0,f.second+1,2);
			F.update(f.second,f.second+1,1LL<<50);
		}
		//FOR(i,N) _P("%lld/%lld ",D.getval(i,i+1).first,F.getval(i,i+1).first);
		
		auto p = D.getval(0,N);
		if(p.first>=1LL<<40 || p.first==0) break;
		
		ll d = min(flow,F.getval(p.second,N).first);
		//_P(" : %lld:%d %lld\n",p.first,p.second,d);
		
		ret += p.first*d;
		flow-=d;
		F.update(p.second,N,-d);
	}
	cout<<ret<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}


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

int main(){
  int n;
  cin >> n;
  
  vector <int> num(100002, 0);
  for (int i = 0; i < n; i++){
    int a;
    cin >> a;
    num.at(a)++;
  }
  
  int ans = 0;
  for (int x = 1; x <= 100000; x++){
    int count = 0;
    for (int i = -1; i <= 1; i++){
      count += num.at(x + i);
    }
    if (count > ans) ans = count;
  }
  cout << ans << endl;
}

Measured memory_bytes: 640
import collections
li=[]
n,k=map(int,input().split())
for i in range(k):
    d=int(input())
    lik=list(map(int,input().split()))
    li+=lik
li=collections.Counter(li)
ans=0
for j in range(1,n+1):
    if li[j]==0:
        ans+=1
print(ans)


Measured memory_bytes: 9480
#include <stdio.h>

int main(int argc, char *argv[])
{
  long long a, b, c, d;
  long long max;
  
  scanf("%lld %lld %lld %lld", &a, &b, &c, &d);
  
  max = a*c;
  ( max < a*d ) ? ( max = a*d ) : 0;
  ( max < b*c ) ? ( max = b*c ) : 0;
  ( max < b*d ) ? ( max = b*d ) : 0;
  
  printf("%lld\n", max);
  
  return 0;
}

Measured memory_bytes: 1732
#include <iostream>
#include <vector>

int n;
long mark_fold;
long mark_open;

bool input() {
	std::cin >> n;
	std::cin >> mark_fold;
	std::cin >> mark_open;
	if (n == 0 && mark_fold == 0 && mark_open == 0) {
		return false;
	}
	return true;
}

void solve_print() {
	bool ud_list[n]; //true : 上, false : 下
	long pow2 = 1l << (n-1);

	//各段階での印が半分より上か下かを求める
	for (int i = n-1; 0 <= i; i--) {
		if (mark_fold <= pow2) {
			ud_list[i] = true;
			mark_fold = pow2 - mark_fold + 1;
			//std::cout << "u ";
		} else {
			ud_list[i] = false;
			mark_fold = mark_fold - pow2;
			//std::cout << "d ";
		}

		pow2 = pow2 >> 1;
	}
	//std::cout << std::endl;


	//上下の情報を元に折り方を復元
	pow2 = 1l << (n-1);
	for (int i = 0; i < n; i++) {
		if (ud_list[i]) {
			if (mark_open <= pow2) {
				std::cout << "L";
				mark_open = pow2 - mark_open + 1;
			} else {
				std::cout << "R";
				mark_open = pow2*2 - mark_open + 1;
			}
		} else {
			if (mark_open <= pow2) {
				std::cout << "R";

			} else {
				std::cout << "L";
				mark_open = mark_open - pow2;
			}
		}

		pow2 = pow2 >> 1;
	}
	std::cout << std::endl;
}

int main(int argc, char const *argv[])
{
	/* code */

	while (input()) {
	solve_print();
	}
	return 0;
}


Measured memory_bytes: 2984
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text.RegularExpressions;
using Library;
using static Library.Input;

namespace AtCoderTemplate
{
    class ProgramB
    {
        static void Main()
        {
            int n = NextInt;
            var a = IntList;

            System.Console.WriteLine(1 / (a.Sum(x => (decimal) 1 / x)));
        }
    }
}

namespace Library
{
    class Input
    {
        static IEnumerator<string> enumerator = new string[] { }.AsEnumerable().GetEnumerator();

        public static string Line => Console.ReadLine();

        public static string[] StrArr => Line.Split(' ');

        public static int NextInt => int.Parse(NextWord());

        public static long NextLong => long.Parse(NextWord());

        public static List<int> IntList => StrArr.Select(int.Parse).ToList();

        public static List<long> LongList => StrArr.Select(long.Parse).ToList();

        public static IEnumerable<long[]> TakeLine(int N)
        {
            return Enumerable.Repeat(0, N).Select(_ => Console.ReadLine().Split(' ').Select(long.Parse).ToArray());
        }

        public static string NextWord()
        {
            while (!enumerator.MoveNext())
            {
                enumerator = StrArr.AsEnumerable().GetEnumerator();
            }
            return enumerator.Current;
        }
    }
}


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

int main(void){
   int x,y;
   cin>>x>>y;
   int group[13]={0,1,3,1,2,1,2,1,1,2,1,2,1};
   if(group[x]==group[y]){
      cout<<"Yes"<<endl;
   }else{
      cout<<"No"<<endl;
   }
   return 0;
}



Measured memory_bytes: 256
#include<iostream>
#include<iomanip>
using namespace std;
int main()
{
  int n;
  double res;
  cin >> n;
  if(n%2==1)
    res=(double)(n/2+1)/n;
  else
    res=(double)1/2;
  cout << setprecision(10) << res << endl;
  return 0;
}


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

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

	int result = 0;

	vector<int> a(n);
	for(int i = 0; i < n; i++) {
		cin >> a[i];
		result += a[i];
	}

	double d = (1.0 / (4.0 * m)) * result;
	int cnt = 0;
	for(int i = 0; i < n; i++) {
		if(a[i] >= d) cnt++;
	}

	if(m <= cnt) {
		cout << "Yes" << '\n';
	} else {
		cout << "No" << '\n';
	}

    return 0;
}


Measured memory_bytes: 256
//#include "bits/stdc++.h"
#include <iostream>
#include <vector>
#include <map>
#include <utility>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <numeric>
#include <complex>
#include <bitset>
#include <functional>
#include <stack>
#include <regex>
#include <tuple>
#include <iomanip>


#define int long long
#define REP(i,l,r) REPEAT(i,l,r,true) // [l, r)
#define rep(i,n) REP(i,0,n)           // [0, n)
#define REPEAT(i,l,r,condition) for(int i=(condition)?l:r-1;(condition)?i<r:i>=l;(condition)?++i:--i) // false<-[l, r)->true
#define all(e) e.begin(),e.end()
#define rall(e) e.rbegin(),e.rend()
#define pb push_back
#define fs first
#define sc second
#ifdef LOCAL
#define show(...) cerr<<#__VA_ARGS__<<" = ";_DEBUG(__VA_ARGS__)
#define showlr(n,l,r) cerr<<#n<<" = ";for(int i=l;i<r;i++){cerr<<n[i]<<", ";}cerr<<endl // [l, r)
#else
#define show(...)
#define showlr(n,l,r)
#endif

#define YN(condition) puts((condition)?"YES":"NO")
#define Yn(condition) puts((condition)?"Yes":"No")
#define yn(condition) puts((condition)?"yes":"no")
#define YES puts("YES")
#define Yes puts("Yes")
#define yes puts("yes")
#define NO  puts("NO")
#define No  puts("No")
#define no  puts("no")

#define case(i) printf("Case #%lld: ",i)

using namespace std;

using vi=vector<int>;
using pint=pair<int,int>;

struct io{io(){cin.tie(0);ios::sync_with_stdio(false);cout.tie(0);cout<<fixed<<setprecision(20);}}io;

template<class T> istream& operator >>(istream &is, vector<T> &v){for(T &e:v)is>>e;return is;}
template<class T> ostream& operator <<(ostream &os, vector<T> v){os<<"{";for(T &e:v)os<<e<<(v.size()-(int)(&e-&v[0])>1?", ":"");os<<"}";return os;}

void _DEBUG(){}
template<typename H,typename... T> void _DEBUG(H a,T...b){cerr<<a<<(sizeof...(b)?",":"\n");_DEBUG(b...);}

inline void in(){}
template<typename H,typename... T>void in(H &a, T&... b){cin>>a;in(b...);}
inline void out(){}
template<typename H,typename... T> void out(H a, T... b){cout<<a<<(sizeof...(b)?" ":"\n");out(b...);}

template<class T> void resz(int n,T& v){v.resize(n);}
template<class H,class... T> void resz(int n,H& a,T&... b){a.resize(n);resz(n,b...);}

template<typename V,typename H> void resize(vector<V>& v,const H a){v.resize(a);}
template<typename V,typename H,typename... T> void resize(vector<V>& v,const H& a,const T... b){v.resize(a);for(auto &v:v) resize(v,b...);}

const int INF=1LL<<55;
const int MOD=1000000007;
const double EPS=1e-8;
/*------------end of definitions------------*/

int A,B;

signed main(){

    in(A,B);
    out(A<=5?0:A<=12?B/2:B);

    return 0;
}


Measured memory_bytes: 888
#include<cstdio>
#include<functional>
#include<algorithm>
#include<cstring>
using namespace std;
int main(void)
{
	int i,p,len;
	char s[11],t[11];
	scanf("%s",s);
	len=strlen(s);
	p=0;
	for(i=0;i<len;i++)	{
		if(s[i]=='B')	{
			if(p!=0)	p--;
		}
		else {
			t[p]=s[i];
			p++;
		}
	}
	t[p]='\0';
	printf("%s\n",t);
	return 0;
}

Measured memory_bytes: 128
s=input()
l=["A","C","G","T"]
ans=0
for i in range(len(s)):
    for j in range(len(s)):
        part=s[i:len(s)-j]
        if all((part[k] in l) for k in range(len(part))) and len(part)>ans:
            ans=len(part)
print(ans)

Measured memory_bytes: 8912
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))


from collections import defaultdict, deque, Counter
from sys import exit
import math
import copy
from bisect import bisect_left, bisect_right
from heapq import *
import sys

# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007

from fractions import *


def inverse(f):
    # return Fraction(f.denominator,f.numerator)
    return 1 / f


def combmod(n, k, mod=MOD):
    ret = 1
    for i in range(n - k + 1, n + 1):
        ret *= i
        ret %= mod

    for i in range(1, k + 1):
        ret *= pow(i, mod - 2, mod)
        ret %= mod

    return ret

MOD = 10 ** 9 + 7
def solve():
    MOD = 2019
    s = input().strip()
    acc = [0]
    revgen = pow(10, MOD-2, MOD)
    for c in s:
        num = int(c)
        acc.append((acc[-1] * 10 + num) % MOD)

    acc.reverse()
    mul = 1
    res = []
    for ac in acc:
        ac *= mul
        ac %= MOD
        res.append(ac)
        mul *= 10
        mul %= MOD
    res.reverse()

    # print(res)
    cnt = Counter(res)
    ans = 0
    for v in cnt.values():
        ans += v * (v - 1)
    print(ans // 2)
    # print(acc)
    # print((1817 * 100000) % MOD)
    # print((817 * 100000) % MOD)
def main():
    n = getN()
    for _ in range(n):
        solve()


if __name__ == "__main__":
    solve()

Measured memory_bytes: 90836
#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;

char s[8005];

int x[8005],y[8005];

int dpx[16005][4005],dpy[16005][4005];

int main()
{
    cin>>s+1;
    int sx,sy;
    cin>>sx>>sy;
    int l=strlen(s+1);
    s[l+1]='#';
    int t1=0,t2=0;
    int i=1;
    int sum=0,xx=0,yy=0;
    while(s[i]=='F')
    {
        sum++;
        i++;
    }
    xx+=sum;
    sum=0;
    int flag=0;
    for(int j=i;j<=l;)
    {
        if(s[j]=='T')
        {
            flag+=1;
            flag%=2;
            j++;
            continue;
        }
        sum=0;
        while(s[j]=='F')
        {
            sum++;
            j++;
        }
        if(flag==0)
        {
            x[++t1]=sum;
        }
        else
        {
            y[++t2]=sum;
        }
    }

    int sum1=0,sum2=0;
    for(int i=1;i<=t1;i++)
        sum1+=x[i];
    for(int i=1;i<=t2;i++)
        sum2+=y[i];

    memset(dpx,0,sizeof dpx);
    memset(dpy,0,sizeof dpy);
    dpx[8000+xx][0]=1;
    for(int i=1;i<=t1;i++)
    {
        for(int j=0;j<=16000;j++)
        {
            if(j-x[i]>=0&&dpx[j-x[i]][i-1]) dpx[j][i]=1;
            if(j+x[i]<=16000&&dpx[j+x[i]][i-1]) dpx[j][i]=1;
        }
    }
    dpy[8000][0]=1;
    for(int i=1;i<=t2;i++)
    {
        for(int j=0;j<=16000;j++)
        {
            if(j-y[i]>=0&&dpy[j-y[i]][i-1]) dpy[j][i]=1;
            if(j+y[i]<=16000&&dpy[j+y[i]][i-1]) dpy[j][i]=1;
        }
    }
    if(dpx[8000+sx][t1]&&dpy[8000+sy][t2]) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}


Measured memory_bytes: 501120
//package beginner176;

import java.util.Scanner;

public class Main {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);

        String s = in.next();

        int cnt = 0;
        int len = s.length();
        for(int i = 0; i < len; i++){
            cnt += s.charAt(i) - '0';
        }
        if(cnt % 3 == 0){
            System.out.println("Yes");
        }else{
            System.out.println("No");
        }
    }
}


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

using namespace std;


long long Dp(int n , int k,int h[] , bool vis[] , long long dp[]){
    if(vis[n]){
        return dp[n];
    }else{
        vector <int> back;
        for(int step = 1 ; step <= k ; step++){
            if(n - step >= 0){
                int x = Dp(n-step,k,h,vis,dp) + abs(h[n] - h[n-step]);
                back.push_back(x);
            }
        }
        sort(back.begin(),back.end());
        vis[n] = true;
        dp[n] = back[0];
        return dp[n];
    }
}



void init(int n , bool vis[]){
    vis[0] = true;
    for(int i = 1; i < n ; i++){
        vis[i] = false;
    }
}

int main(){

    int n,k;
    cin >> n >> k;
    int h[n];
    bool vis[n];
    long long dp[n];
    dp[0] = 0;
    init(n,vis);
    for(int i = 0 ; i < n ; i++){
        cin >> h[i];
    }
    long long ans = Dp(n-1,k,h,vis,dp);
    cout << ans;
    return 0;
}

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

using namespace std;

#define int long long
#define ar array
#define vt vector
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define sz(x) (int)(x).size()

#define F_OR(i, a, b, s) for (int i=(a); (s)>0?i<(b):i>(b); i+=(s))
#define F_OR1(e) F_OR(i, 0, e, 1)
#define F_OR2(i, e) F_OR(i, 0, e, 1)
#define F_OR3(i, b, e) F_OR(i, b, e, 1)
#define F_OR4(i, b, e, s) F_OR(i, b, e, s)
#define GET5(a, b, c, d, e, ...) e
#define F_ORC(...) GET5(__VA_ARGS__, F_OR4, F_OR3, F_OR2, F_OR1)
#define FOR(...) F_ORC(__VA_ARGS__)(__VA_ARGS__)
#define EACH(x, a) for (auto& x: a)

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

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

template<class A>
void read(vt<A> &v);

template<class A, size_t S>
void read(ar<A, S> &a);

template<class T>
void read(T &x) {
    cin >> x;
}

void read(double &d) {
    string t;
    read(t);
    d = stod(t);
}

void read(long double &d) {
    string t;
    read(t);
    d = stold(t);
}

template<class H, class... T>
void read(H &h, T &... t) {
    read(h);
    read(t...);
}

template<class A>
void read(vt<A> &x) {
    EACH(a, x)read(a);
}

template<class A, size_t S>
void read(array<A, S> &x) {
    EACH(a, x)read(a);
}

string to_string(char c) {
    return string(1, c);
}

string to_string(bool b) {
    return b ? "true" : "false";
}

string to_string(const char *s) {
    return string(s);
}

string to_string(string s) {
    return s;
}

string to_string(vt<bool> v) {
    string res;
    FOR(sz(v))res += char('0' + v[i]);
    return res;
}

template<size_t S>
string to_string(bitset<S> b) {
    string res;
    FOR(S)res += char('0' + b[i]);
    return res;
}

template<class T>
string to_string(T v) {
    bool f = 1;
    string res;
    EACH(x, v) {
        if (!f)
            res += ' ';
        f = 0;
        res += to_string(x);
    }
    return res;
}

template<class A>
void write(A x) {
    cout << to_string(x);
}

template<class H, class... T>
void write(const H &h, const T &... t) {
    write(h);
    write(t...);
}

void print() {
    write("\n");
}

template<class H, class... T>
void print(const H &h, const T &... t) {
    write(h);
    if (sizeof...(t))
        write(' ');
    print(t...);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n) {
    v = vt<T>(n, x);
}

template<class T, class U>
void vti(vt<T> &v, U x, size_t n, size_t m...) {
    v = vt<T>(n);
    EACH(a, v)vti(a, x, m);
}

void solve() {
    int n, A, b;
    read(n, A, b);
    
    vt<int> a(n);
    read(a);
    int ans = 0;
    FOR(i, 1, n) {
        ans += min(b, A * (a[i] - a[i - 1]));
    }
    print(ans);
}

int32_t main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int tt = 1;
//    read(tt);
    FOR(tt) {
//        write("Case #", i + 1, ": ");
        solve();
    }
    
}



Measured memory_bytes: 3976
import sys

A11, A12, A13 = map(int, input().split())
A21, A22, A23 = map(int, input().split())
A31, A32, A33 = map(int, input().split())

card = [[A11, A12, A13],
        [A21, A22, A23],
        [A31, A32, A33]]

h = [[0, 0, 0],
     [0, 0, 0],
     [0, 0, 0]]

a = []

for l in sys.stdin:
    a.append(int(l))

for i in a:
    for j in range(3):
        for k in range(3):
            if card[j][k] == i:
                h[j][k] = 1

if max(sum(h[0]), sum(h[1]), sum(h[2])) == 3:
    print("Yes")
elif max((h[0][0] + h[1][0] + h[2][0]), (h[0][1] + h[1][1] + h[2][1]), (h[0][2] + h[1][2] + h[2][2])) == 3:
    print("Yes")
elif max((h[0][0] + h[1][1] + h[2][2]), (h[0][2] + h[1][1] + h[2][0])) == 3:
    print("Yes")
else:
    print("No")

Measured memory_bytes: 3064
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
using namespace std;
 
int main() {
  int n, k;
  cin >> n >> k;
  vector<int> l(n);
  rep(i, n) cin >> l[i];
  
  sort(l.begin(), l.end());
  reverse(l.begin(), l.end());
  
  int sum = 0;
  
  rep(i, k) {
    sum += l[i];
  }
  
  cout << sum << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long INF = 1LL<<60;

ll GCD(ll x,ll y){
    if(y == 0) return x;
    else return GCD(y,x%y);
}

ll LCM(ll a,ll b){
    return a / GCD(a,b) * b;
}

const int MOD = 1000000007;



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


Measured memory_bytes: 3596
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String S = sc.next();
        sc.close();

        System.out.println(philia(S));
    }
    public static int philia(String S) {
        switch (S.length()) {
        case 0:
        case 1:
            return 0;
        default:
            if (S.charAt(0) == S.charAt(S.length()-1)) {
                return philia(S.substring(1, S.length()-1));
            }
            return 1 + philia(S.substring(1, S.length()-1));
        } 
    }
}


Measured memory_bytes: 23764
N, K = map(int, input().split())

m = 1000000007

result = 0
for i in range(K, N + 2):
    # max: N, N -1, ..., N - i + 1
    a = (N + (N - i + 1)) * i // 2
    # min: 0, 1, .., i - 1
    b = (0 + (i - 1)) * i // 2
    result += a - b + 1
    result %= m
print(result)


Measured memory_bytes: 9184
#include <iostream>
#include <math.h>
using namespace std;

bool isprime(int num)
{
      if(num == 2)return true;
      if(num % 2 == 0) return false;
      for(int j = 3; j < (int)sqrt(num) + 2 ;j += 2){
            if(num % j == 0)return false;
      }
      return true;
}
int main(){
      int count=0,tmp,n;
      cin >> n;
      for(int i = 0; i < n ; i++){
            cin >> tmp;
            if(isprime(tmp))count++;
      }
      cout<<count<<endl;
}

Measured memory_bytes: 1164
def calc(num,capacity):
    dp = [0]*(capacity+1)
    for _ in range(num):
        weight, value = map(int, input().split())
        for w in range(capacity,weight - 1,-1):
            tmp = dp[w - weight] + value
            if dp[w] < tmp:
              dp[w] = tmp
    return dp[capacity]
 
num, capacity = map(int, input().split())
print(calc(num,capacity))

Measured memory_bytes: 9716
import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = Integer.parseInt(sc.next());
		int x = Integer.parseInt(sc.next());

		int ans = Math.abs(x-Integer.parseInt(sc.next()));
		for (int i=0; i<n-1; i++){
			ans = gcd(ans, Math.abs(x-Integer.parseInt(sc.next())));
		}
		System.out.println(ans);
	}

//	public static int gcd(int a,int b) {
//		return a%b==0?b:gcd(b,a%b);
//	}

	public static int gcd(int num1, int num2) {
		int x = Math.max(num1, num2);
		int y = Math.min(num1, num2);

		while (y != 0) {
			int tmp = x;
			x = y;
			y = tmp%y;
		}
		return x;
	}
}


Measured memory_bytes: 42540
#include <bits/stdc++.h>
#include<algorithm>
#include<math.h>
using namespace std;
 
template <class T> using V = vector<T>;
 
using ll = long long;
using db = double;
using st = string;
using ch = char;
using vll = V<ll>;
using vpll =V<pair<ll,ll>>;
using vst = V<st>;
using vdb = V<db>;
using vch = V<ch>;
 
 
#define FOR(i,a,b) for(ll i=(a);i<(ll)(b);i++)
#define rFOR(i,a,b) for(ll i=(a);i>(ll)(b);i--)
#define oFOR(i,a,b) for(ll i=(a);i<(ll)(b);i+=2)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define M(a,b) max(a,b)
#define rM(a,b) min(a,b)
#define fi first
#define se second
#define sz size()
#define gcd(a,b) __gcd(a,b)
#define co(a) cout<<a<<endl;
#define ci(a) cin>>a;
 
 
ll sum(ll n) {
  ll m=0;
  FOR(i,0,20){
    m+=n%10;
    n/=10;
    if(n==0){
      break;
    }
  }
  return m;
}
 
 
ll combi(ll n,ll m) {
  ll ans=1;
  rFOR(i,n,n-m){
    ans*=i;
  }
  FOR(i,1,m+1){
    ans/=i;
  }
  return ans;
}
 
 
ll lcm(ll a,ll b){
  ll n;
  n=a/gcd(a,b)*b;
  return n;
}
 
 
/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
 
 
signed main() {
  ll a,b,c;
  ci(a>>b>>c)
  
    FOR(i,a,b+1){
      if(i<a+c) co(i)
      else if(b-c<i) co(i)
  }
}

Measured memory_bytes: 256
#include <stdio.h>
#include <cstdio>
#include <string>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>


char str[12];


int main()
{

	std::cin >> str;

	if (str[0] == 'Y' &&
		str[1] == 'A' &&
		str[2] == 'K' &&
		str[3] == 'I') puts("Yes");
	else puts("No");



	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define F first
#define S second

using namespace std;
typedef pair<int,int> P;

const int MOD=1000000007;
int INF=100100100100100;

signed main(){
  int a[2];
  cin>>a[0]>>a[1];
  sort(a,a+2);
  rep(i,a[1])cout<<a[0];
  cout<<endl;
  return 0;
}

Measured memory_bytes: 3600
#include <iostream>
#include <vector>
using namespace std;
int main(){
    int N;
    int res = 0;
    cin >> N;
    vector<int> l(N);
    vector<int> r(N);
    for(int i = 0; i < N; i++){
        cin >> l[i] >> r[i];
        res = res + (r[i] - l[i] + 1);
    }
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define IO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define DB(x) cerr << __LINE__ << ": " << #x << " = " << (x) << "\n"
using namespace std;
using ll = long long;

signed main() {
    IO;
	ll n, k;
	cin >> n >> k;
	vector<ll> a(n + 5, 1ll);
	// ll prev = 1, cur = 1;
	for(int i = 1; i <= n; ++i) {
		cin >> a[i];
		// if(i <= k) prev *= a[i];
	}
	// cur = prev;
	for(int i = k + 1; i <= n; ++i) {
		if(a[i] > a[i - k]) {
			cout << "Yes\n";
		}	
		else cout << "No\n";
		// prev = cur;
	}
    return 0;
}

Measured memory_bytes: 4780
#include <iostream>
#include <cstdio>
#include <set>
#include <algorithm>
#define il inline
#define ri register
#define Size 100050
#define yyb 1000000007
using namespace std;
struct pos{
	int x,y;
	il bool operator<(const pos&a)const{
		return x==a.x?y<a.y:x<a.x;
	}
}p[Size];
set<pos>S;
set<pos>::iterator it;
int pt,c[Size],dp[Size];
int x1[Size],x2[Size],a[Size],b[Size];
il void read(int&),change(int,int);
il int dfs(int,int,int,int[]),ask(int);
int main(){
	int n,m;read(n),read(m);
	for(int i(1);i<=n;++i)read(x1[i]);
	for(int i(1);i<=m;++i)read(x2[i]);
	for(int i(1),j;i<=n;++i){
		j=dfs(1,m,x1[i],x2);if(j==1||j>m)continue;
		S.insert({x1[i]-x2[j-1],x2[j]-x1[i]});
	}for(it=S.begin();it!=S.end();++it)p[++pt]=*it;
	for(int i(1);i<=pt;++i)a[i]=p[i].y;sort(a+1,a+pt+1);
	for(int i(1);i<=pt;++i)b[i]=dfs(1,pt,p[i].y,a);
	for(int l(1),r,i;l<=pt;l=r+1){
		r=l;while(p[r+1].x==p[r].x)++r;
		for(i=l;i<=r;++i)dp[i]=ask(b[i]-1)+1;
		for(i=l;i<=r;++i)change(b[i],dp[i]);
	}int ans(1);for(int i(1);i<=pt;++i)ans=(ans+dp[i])%yyb;
	printf("%d",ans);
	return 0;
}
il int ask(int p){
	int ans(0);while(p)ans=(ans+c[p])%yyb,p-=p&-p;return ans;
}
il void change(int p,int x){
	while(p<=pt)c[p]=(c[p]+x)%yyb,p+=p&-p;
}
il int dfs(int l,int r,int x,int a[]){
	int mid;while(l<=r){
		mid=l+r>>1;
		if(a[mid]<x)l=mid+1;
		else r=mid-1;
	}return l;
}
il void read(int &x){
	x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}


Measured memory_bytes: 8064
#include <iostream>

int main (void)
{
	int r, D, x2000;
	scanf("%d %d %d", &r, &D, &x2000);
	int tmp = x2000;
	for (int i = 1; i <= 10; i++)
	{
		printf("%d\n", r * tmp - D);
		tmp = r * tmp - D;
	}
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  int X, N;
  cin >> X >> N;
  vector<int> P(N);
  set<int> se;
  rep(i, N) {
    cin >> P[i];
    se.insert(P[i]);
  }
  int r = X;
  while(r <= 101 && se.count(r)) r++;
  int l = X;
  while(l >= 0 && se.count(l)) l--;
  if(abs(r-X) >= abs(l-X)) {
    cout << l << endl;
  } else {
    cout << r << endl;
  }
  return 0;
}


Measured memory_bytes: 3636
<?php

$stdin = preg_split('/ /', trim(fgets(STDIN)));
$n = intval(array_shift($stdin));
$m = intval(array_shift($stdin));
$l = intval(array_shift($stdin));
$matrix_a = array();
$matrix_b = array();
$matrix_c = array();

for ($i = 0; $i < $n; $i++) {
    $matrix_a[] = preg_split('/ /', trim(fgets(STDIN)));
}
for ($i = 0; $i < $m; $i++) {
    $matrix_b[] = preg_split('/ /', trim(fgets(STDIN)));
}
for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $l; $j++) {
        $matrix_c[$i][$j] = 0;
    }
}

for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $m; $j++) {
        for ($k = 0; $k < $l; $k++) {
            $matrix_c[$i][$k] += $matrix_a[$i][$j] * $matrix_b[$j][$k];
        }
    }
}

for ($i = 0; $i < $n; $i++) {
    for ($j = 0; $j < $l; $j++) {
        print($matrix_c[$i][$j]);
        if ($j != $l-1) {
            print(' ');
        }
    }
    print("\n");
}

Measured memory_bytes: 11704
using System;
using System.Linq;
namespace Sample
{
  class Sample
  {
    static void Main(string[] args)
    {
    int N=int.Parse(Console.ReadLine());
      if(N<=999){
        Console.WriteLine("ABC");
      }else{
        Console.WriteLine("ABD");
      }
    }
    
  }

}


Measured memory_bytes: 27500
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;
const int INT_INF = 2147483647;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }

int main(){
  ll a,b,k;
  cin >> a >> b >> k;
  if(a-k>=0){
    cout << a-k << " " << b << endl;
  }else if(a+b-k>=0){
    cout << 0 << " " << a+b-k << endl;
  }else{
    cout << 0 << " " << 0 << endl;
  }
}


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

typedef long long ll;

const int INF = 1e9 + 10;
const ll INFLL = 3e18;

int main(){
	
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	
	int ans = 1;
	int n;
	cin >> n;
	
	for(int i = 1 ; i*i <= n ; i ++)
		ans = i*i;
	
	cout << ans << "\n";
	
	return 0;
}

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

#define INF 1.1e9
#define LINF 1.1e18
#define FOR(i,a,b) for (int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define BIT(x,n) bitset<n>(x)
#define PI 3.14159265358979323846

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

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

int n,k;
ll a[5000];

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

	cin>>n>>k;
	REP(i,n) {
		cin>>a[i];
	}
	sort(a,a+n,greater<int>());
	ll sum=0;
	int ans=n;
	REP(i,n) {
		if(sum+a[i]<k) sum+=a[i];
		else ans=n-i-1;
	}
	cout<<ans<<endl;

	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=105;
short f[N][N][N][N],sum1[N][N],sum2[N][N];char a[N][N];
inline void ckmax(short&x,short y){
	x=(x<y?y:x);
}
int main (){
	int n,m;scanf ("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		scanf ("%s",a[i]+1);
	int tx,ty;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++){
			if (a[i][j]=='E') tx=i,ty=j;
            sum1[i][j]=sum1[i][j-1]+(a[i][j]=='o');
            sum2[i][j]=sum2[i-1][j]+(a[i][j]=='o');
		}
	int limi=tx-1,limj=n-tx,limk=ty-1,liml=m-ty;
	for (int i=0;i<=limi;i++)
		for (int j=0;j<=limj;j++)
			for (int k=0;k<=limk;k++)
				for (int l=0;l<=liml;l++){
					int L=max(ty-k,l+1),R=min(ty+l,m-k);
					if (L<=R){
						ckmax(f[i+1][j][k][l],f[i][j][k][l]+(tx-i-1>=j+1?sum1[tx-i-1][R]-sum1[tx-i-1][L-1]:0));
						ckmax(f[i][j+1][k][l],f[i][j][k][l]+(tx+j+1<=n-i?sum1[tx+j+1][R]-sum1[tx+j+1][L-1]:0));
					}
					L=max(tx-i,j+1),R=min(tx+j,n-i);
					if (L<=R){
						ckmax(f[i][j][k+1][l],f[i][j][k][l]+(ty-k-1>=l+1?sum2[R][ty-k-1]-sum2[L-1][ty-k-1]:0));
						ckmax(f[i][j][k][l+1],f[i][j][k][l]+(ty+l+1<=m-k?sum2[R][ty+l+1]-sum2[L-1][ty+l+1]:0));
					}
				}
	printf ("%d",f[limi][limj][limk][liml]);
	return 0;
}


Measured memory_bytes: 209280
a = input()
b = input()
c = input()


sign = 'a'

while(True):
    if sign == 'a':
        if a == '':
            print("A")
            break
 #       print("sign = " + sign)
        sign = a[0]
        a = a[1:]
#        print("sign -> " + sign)
 #       print("a = " + a)

        
    elif sign == 'b':
        if b == '':
            print("B")
            break
#        print("sign = " + sign)
        sign = b[0]
        b = b[1:]
#        print("sign -> " + sign)
 #       print("b = " + b)

        
    else:
        if c == '':
            print("C")
            break
 #       print("sign = " + sign)
        sign = c[0]
        c = c[1:]
  #      print("sign -> " + sign)
 #       print("c = " + c)



Measured memory_bytes: 3064
S=input()
T=input()
ns=len(S)
nt=len(T)
ans=ns
for i in range(ns-nt+1):
    count=0
    for j in range(nt):
        if S[i+j]==T[j]:
            count+=1
    ans=min(nt-count,ans)
    #print(ans)
print(ans)


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

void solve(long long N, long long K, string S){
	if (S[K-1] == 'A') S[K-1] = 'a';
	if (S[K-1] == 'B') S[K-1] = 'b';
	if (S[K-1] == 'C') S[K-1] = 'c';
	cout << S << endl;
}

int main(){	
	long long N;
	long long K;
	string S;
	scanf("%lld",&N);
	scanf("%lld",&K);
	cin >> S;
	solve(N, K, S);
	return 0;
}



Measured memory_bytes: 256
import java.io.IOException; 
import java.io.InputStream; 
import java.io.PrintWriter; 

class Main{ 

	static void solve(){ 
		int N =ni();
		int ans = 1000000;
		for(int i=1;i<=N-1;++i){
			int res = 0;
			int B = N-i;
			int A = i;
			while(A>0){
				res+=A%10;
				A/=10;
			}
			while(B>0){
				res+=B%10;
				B/=10;
			}
			ans=Math.min(ans, res);
		}
		out.println(ans);
	} 
 
 
 
 
	public static void main(String[] args){ 
		 solve(); 
		 out.flush(); 
	 } 
	 private static InputStream in = System.in; 
	 private static PrintWriter out = new PrintWriter(System.out); 
 
	 private static final byte[] buffer = new byte[1<<15]; 
	 private static int ptr = 0; 
	 private static int buflen = 0; 
	 private static boolean hasNextByte(){ 
		 if(ptr<buflen)return true; 
		 ptr = 0; 
		 try{ 
			 buflen = in.read(buffer); 
		 } catch (IOException e){ 
			 e.printStackTrace(); 
		 } 
		 return buflen>0; 
	 } 
	 private static int readByte(){ if(hasNextByte()) return buffer[ptr++]; else return -1;} 
	 private static boolean isSpaceChar(int c){ return !(33<=c && c<=126);} 
	 private static int skip(){int res; while((res=readByte())!=-1 && isSpaceChar(res)); return res;} 
 
	 private static double nd(){ return Double.parseDouble(ns()); } 
	 private static char nc(){ return (char)skip(); } 
	 private static String ns(){ 
		 StringBuilder sb = new StringBuilder(); 
		 for(int b=skip();!isSpaceChar(b);b=readByte())sb.append((char)b); 
		 return sb.toString(); 
	 } 
	 private static int[] nia(int n){ 
		 int[] res = new int[n]; 
		 for(int i=0;i<n;++i)res[i]=ni(); 
		 return res; 
	 } 
	 private static long[] nla(int n){ 
		 long[] res = new long[n]; 
		 for(int i=0;i<n;++i)res[i]=nl(); 
		 return res; 
	 } 
	 private static int ni(){ 
		 int res=0,b; 
		 boolean minus=false; 
		 while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); 
		 if(b=='-'){ 
			 minus=true; 
			 b=readByte(); 
		 } 
		 for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); 
		 return minus ? -res:res; 
	 } 
	 private static long nl(){ 
		 long res=0,b; 
		 boolean minus=false; 
		 while((b=readByte())!=-1 && !((b>='0'&&b<='9') || b=='-')); 
		 if(b=='-'){ 
			 minus=true; 
			 b=readByte(); 
		 } 
		 for(;'0'<=b&&b<='9';b=readByte())res=res*10+(b-'0'); 
		 return minus ? -res:res; 
	} 
} 



Measured memory_bytes: 21460