akhauriyash/Code-Regression huggingface dataset:
import java.io.*;
import java.util.*;

public class Main{
	public static void main(String[] args){
		solve();
	}
	public static void solve(){
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[] a = new int[n];
		int[] b = new int[n];
		int[] c = new int[n];
		for(int i=0;i<n;i++){
			a[i] = sc.nextInt();
		}
		for(int i=0;i<n;i++){
			b[i] = sc.nextInt();
		}
		for(int i=0;i<n;i++){
			c[i] = sc.nextInt();
		}
		Arrays.sort(a);
		Arrays.sort(b);
		Arrays.sort(c);
		long count = 0;
		for(int i=0;i<n;i++){
			int l = -1;
			int r = n;
			int min = 0;
			int max = 0;
			while(r-l>1){
				int center = (r + l) / 2;
				if(a[center]>=b[i]){
					r = center;
				}
				else{
					l = center;
				}
			}
			min = r;
			l = -1;
			r = n;
			while(r-l>1){
				int center = (r + l) / 2;
				if(c[center]<=b[i]){
					l = center;
				}
				else{
					r = center;
				}
			}
			max = n - r;
			count += (long)max * (long)min;
		}
		System.out.println(count);
	}
}


Measured memory_bytes: 92956
N, Q = map(int, input().split())
L, R = [None] * Q, [None] * Q

S = input()

for i in range(Q):
    L[i], R[i] = map(int, input().split())

counts = [0] * N
count_tmp = 0
is_before_char_A = False

for i in range(N):
    if S[i] == 'A':
        is_before_char_A = True
        counts[i] = count_tmp
        continue
    if S[i] == 'C' and is_before_char_A:
        count_tmp += 1

    counts[i] = count_tmp
    is_before_char_A = False
    #if S[i-1] == 'A' and S[i] == 'C':
    #    count_tmp += 1

# print(counts)

for i in range(Q):
    print(counts[R[i] - 1] - counts[L[i] - 1])

Measured memory_bytes: 14312
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#include <stdio.h>
#include <stdlib.h>
#include <float.h>

using namespace std;
#define ll long long


int main(void){
    int N,M,syou,dai;
    cin>>N>>M;
    syou=1;
    dai=N;
    vector<int>  L(M),R(M);
    for(int i=0;i<M;i++){
        cin>>L.at(i)>>R.at(i);
        syou=max(syou,L.at(i));
        dai=min(dai,R.at(i));
    }
    if(syou>dai) cout<<0<<endl;
    else cout<<dai-syou+1<<endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
const int INF = 1e9;
#define FOR(i, a, n) for(int i = (int)(a); i < (int)(n); ++i)
#define REP(i, n) FOR(i, 0, n)
#define SORT(a) sort(a.begin(),a.end())
using namespace std;
int main(){
    int N,L;
    cin >> N>>L;

    vector<string> vec(N);

    REP(i,N){
        cin >> vec[i];
    }
    SORT (vec);

    REP(i,N){
        cout << vec[i];
    }
    
    cout << endl;
}

Measured memory_bytes: 256
#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
#define rep(i, n) for(ll i = 0; i < (n); ++i)
#define FOR(i, m, n) for(ll i = m; i < (n); i++)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
using vi = vector<int>;
using vii = vector<vi>;
using pii = pair<int, int>; 
using vl = vector<ll>;
using vll = vector<vl>;
using pll = pair<ll, ll>;

const int MOD = 1000000007;
const int MAX = 210000;

ll choose[MAX];

int main() {
    ll N, K;
    cin >> N >> K;
    ll ans = 0;

    FOR(i, 1, N+2){
        ll mini = (0 + i-1) * i / 2;
        ll maxi = (N-i+1 + N) * i / 2;
        choose[i] = maxi - mini + 1;
    }

    FOR(i, K, N+2){
        ans += choose[i];
        ans %= MOD;
    }
    cout << ans << endl;
}

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

int main() {
	int M[28],A[31];
	for(int i=0;i<28;i++){
		cin >> M[i];
	}
	for(int i=0;i<28;i++){
		A[M[i]]=M[i];
	}
	for(int i=1;i<31;i++){
		if(A[i]==i){}
		else{
			cout << i << endl;
		}
	}
	return 0;
}

Measured memory_bytes: 1160
#include <stdio.h>

int a,b ;

int main(void){

    scanf ("%d %d",&a,&b) ;
    
    if ( a<=8 && b<=8 ) {
        printf ("Yay!\n") ;
    } 
    
    else {
        printf (":(\n") ;
    }
    
    return 0 ;
    
}


Measured memory_bytes: 128
Edge = Struct.new(:from, :to, :cost)

class UnionFindTree
  def initialize(n)
    @parent = (0...n).to_a
    @rank = Array.new(n, 0)
  end
     
  def find(x)
    return x if @parent[x] == x
    return @parent[x] = find(@parent[x])
  end
     
  def unite(a, b)
    a = find(a)
    b = find(b)
    return if a == b
    if @rank[a] < @rank[b]
      @parent[a] = b
    else
      @parent[b] = a
      @rank[a] += 1 if @rank[a] == @rank[b]
    end
  end
  
  def same?(a, b)
    find(a) == find(b)
  end
end

N = gets.to_i
xy = Array.new(N) { |i| x, y = gets.split.map(&:to_i); [x, y, i] }

queue = []
xy.sort{|a, b| a[0] <=> b[0]}.each_cons(2) do |(x1, y1, i1), (x2, y2, i2)|
  queue << Edge.new(i1, i2, (x1-x2).abs)
end
xy.sort{|a, b| a[1] <=> b[1]}.each_cons(2) do |(x1, y1, i1), (x2, y2, i2)|
  queue << Edge.new(i1, i2, (y1-y2).abs)
end

tree = UnionFindTree.new(N)
n = 0
sum = 0
queue.sort{|e1, e2| e1.cost <=> e2.cost}.each do |e|
  unless tree.same?(e.from, e.to)
    tree.unite(e.from, e.to)
    n += 1
    sum += e.cost
  end
  
  break if n == N-1
end
puts sum


Measured memory_bytes: 23016
#include <stdio.h>
#include <iostream>
using namespace std;
// node最大量
#define MAX 100005
#define NIL -1

struct Node {
    int parent;
    int left;
    int right;
};

// 配列で保持する
Node gNode[MAX];
int gDepth[MAX],gHeight[MAX];

// 兄弟を返す
int getSibling(int u){
    // rootの場合
    if(gNode[u].parent == NIL)return NIL;
    // 自身が右の子だった場合
    if(gNode[gNode[u].parent].left != u && gNode[gNode[u].parent].left != NIL){
        return gNode[gNode[u].parent].left;
    }
    // 自身が左の子だった場合
    if(gNode[gNode[u].parent].right != u && gNode[gNode[u].parent].right != NIL){
        return gNode[gNode[u].parent].right;
    }
    // 親が一つしか子を持たない状態
    return NIL;
}

void print(int node){
    cout << "node " << node << ": ";
    cout << "parent = " << gNode[node].parent << ", ";
    cout << "sibling = " << getSibling(node) << ", ";
    
    int deg = 0;
    if(gNode[node].left != NIL) deg++;
    if(gNode[node].right != NIL) deg++;
    cout << "degree = " << deg << ", ";
    cout << "depth = " << gDepth[node] << ", ";
    cout << "height = " << gHeight[node] << ", ";
    
    if(gNode[node].parent == NIL){
        cout << "root\n";
    }else if(gNode[node].left == NIL && gNode[node].right == NIL){
        cout << "leaf\n";
    }else{
        cout << "internal node\n";
    }
}

// 深さを設定する
void setDepth(int u,int d){
    // 親の節点が葉のケース
    if(u == NIL) return;
    gDepth[u] = d;
    // 左右の子にもセットする
    setDepth(gNode[u].left, d + 1);
    setDepth(gNode[u].right, d + 1);
}

// 高さの設定をする
int setHeight(int u){
    int h1,h2;
    h1 = h2 = 0;
    if(gNode[u].left != NIL){
        h1 = setHeight(gNode[u].left) + 1;
    }
    if(gNode[u].right != NIL){
        h2 = setHeight(gNode[u].right) + 1;
    }
    return gHeight[u] = (h1 > h2) ? h1 : h2;
}

int main(){
    int left,right,v,n,root = 0;
    cin >> n;
    // 初期化
    for(int i = 0;i < n;++i){
        gNode[i].parent = gNode[i].left = gNode[i].right = NIL;
    }
    
    for(int i = 0;i < n;++i){
        cin >> v >> left >> right;
        gNode[v].left = left;
        gNode[v].right = right;
        // 親の設定
        if(left != NIL){
            gNode[left].parent = v;
        }
        if(right != NIL){
            gNode[right].parent = v;
        }
    }

    // rootを探す
    for(int i = 0;i < n;++i){
        if(gNode[i].parent == NIL){
            root = i;
        }
    }
    
    // 根からはじめて深さを代入する
    setDepth(root, 0);
    setHeight(root);
    
    for(int i = 0;i < n;++i){
        print(i);
    }
    return 0;
}



Measured memory_bytes: 3116
i=0
sigma=[]
while True:
    N=int(input())
    goukei=0
    if N==0:
        break
    else:
        sample=list(map(int,input().split()))
        for j in range(len(sample)):
            heikin=sum(sample)/len(sample)
            goukei+=(sample[j]-heikin)**2
        sigma.append((goukei/len(sample))**0.5)
        i+=1
for k in range(i):
    print(sigma[k])



Measured memory_bytes: 5672
import sys

s = sys.stdin.readline().rstrip()
n = len(s)
s += 'R'

def main():
    l = []
    for i in range(1, n):
        if s[i] == 'L':
            if s[i-1] == 'R':
                ls = i
            if s[i+1] == 'R':
                lg = i
                l.append((ls, lg))
    
    res = [0] * n
    j = 0
    ls, lg = l[j]
    for i in range(n):
        if i > lg:
            j += 1
            ls, lg = l[j]
        d = abs(ls - i)
        if d & 1:
            res[ls-1] += 1
        else:
            res[ls] += 1

    return res
    
if __name__ == '__main__':
    ans = main()
    print(*ans, sep=' ')

Measured memory_bytes: 9084
menus = readlines.map(&:to_i)
temp = menus.map { |x| x % 10 == 0 ? 10 : x%10 }
last_index = temp.index(temp.min)
last_menu = menus.delete_at(last_index)
menus.map! { |x| x % 10 == 0 ? x : (x/10+1)*10 }
puts menus.inject(:+) + last_menu


Measured memory_bytes: 1788
#include<bits/stdc++.h>
using namespace std;
long long n,m,i,j,d,k,a,b,c,h;
int main()
{
 cin>>a>>b>>k;
 if(k>a+b)k=a+b;
 if(k<a)cout<<a-k<<" "<<b,0;
 else cout<<0<<" "<<b+a-k,0;
}

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

using namespace std;

const int DZIESTYS = 1e5;

int main()
{
	int n;
	scanf("%d", &n);

	int p[DZIESTYS];
	for (int i = 0; i < n; ++i)
		scanf("%d", &p[i]);

	int dlAktSpojn = 0;
	int sumaZamian = 0;
	for (int i = 0; i < n; ++i)
	{	
		if (p[i] == i + 1) // czyli np. p[0] == 1
		{
			dlAktSpojn++;
		}
		else 
		{
			if (dlAktSpojn > 0) // jezeli wlasnie skonczyl sie jakis niepusty spojny
			{
				sumaZamian += (dlAktSpojn / 2 + dlAktSpojn % 2);
			}
			dlAktSpojn = 0;

		}
	}

	if (dlAktSpojn > 0) // spr na koniec
		sumaZamian += (dlAktSpojn / 2 + dlAktSpojn % 2);
	
	printf("%d\n", sumaZamian);
}

Measured memory_bytes: 768
import sys
fin = sys.stdin.readline
from collections import defaultdict
from heapq import heappop, heappush


def initialize(adj, s):
    MAX_NUM = float('inf')
    parent = {s: None}
    d = {vertex: MAX_NUM for vertex in adj.keys()}
    d[s] = 0
    return d, parent


# Dijkstra can work using a minheap which does not have decrease_key.
# and also we do not have to implement Vertex class.
# Instead, we can use (distance, vertex).
# in this case, the time it takes is O(ElgE).
# E is at most O(V^2), thus O(ElgE) = O(ElgV).
def dijkstra_simple(adj, w, s):
    d, parent = initialize(adj, s)
    priority_queue = []
    heappush(priority_queue, (d[s], s))
    while priority_queue:
        distance, source = heappop(priority_queue) 
        for neighbor in adj[source]:
            new_distance = distance + w[(source, neighbor)]
            if new_distance < d[neighbor]:
                d[neighbor] = new_distance
                parent[neighbor] = source
                heappush(priority_queue, (new_distance, neighbor))
    return d


n, m, s, t = [int(elem) for elem in fin().split()]
adj = defaultdict(list)
yen_weights = dict()
snuuk_weights = dict()
for _ in range(m):
    u, v, a, b = [int(elem) for elem in fin().split()]
    for v1, v2 in [(u, v), (v, u)]:
        adj[v1].append(v2)
        yen_weights[(v1, v2)] = a
        snuuk_weights[(v1, v2)] = b

d_yen = dijkstra_simple(adj, yen_weights, s)
d_snuuk = dijkstra_simple(adj, snuuk_weights, t)
min_cost = float('inf')
min_cost_after_each_year_reversed = []
for vertex in range(n, 0, -1):
    min_cost = min(min_cost, d_yen[vertex] + d_snuuk[vertex])
    min_cost_after_each_year_reversed.append(min_cost)

initial_money = 10**15
for cost in reversed(min_cost_after_each_year_reversed):
    print(initial_money - cost)


Measured memory_bytes: 121248
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
int main(){
    string s,t;
    cin>>s>>t;
    int ans=1000;
    for(int i=0; i<s.size()-t.size()+1; i++){
        int cnt=0;
        for(int j=0; j<t.size(); j++){
            if(s[i+j]!=t[j]) cnt++;
        }
        ans=min(ans,cnt);
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 3588
// In the name of God

#include <bits/stdc++.h>

using namespace std;

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

	int n;
	cin >> n;

	vector<int> v(n);

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

	int x = 0;

	for(int i = 0; i < n - 2; i += 2) {
		x ^= v[i];
		x ^= v[i + 1];
	}

	vector<int> a(n);

	a[n - 1] = x ^ v[n - 2];

	for(int i = 0; i < n - 1; i++) {
		a[i] = a[n - 1] ^ v[n - 1] ^ v[i];
	}

	for(int i = 0; i < n; i++) cout << a[i] << " ";

	
	return 0;
}


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

#define int long long
#define double long double
#define ff first
#define ss second
#define endl '\n'
#define ii pair<int, int>
#define mp make_pair
#define mt make_tuple
#define DESYNC                      \
  ios_base::sync_with_stdio(false); \
  cin.tie(0);                       \
  cout.tie(0)
#define pb push_back
#define vi vector<int>
#define vii vector<ii>
#define all(x) x.begin(), x.end()
#define EPS 1e-9
#define INF 1e18
#define ROOT 1
#define M 1000000007
#define curtime chrono::steady_clock::now().time_since_epoch().count
#define rep(i, beg, n, s) for (int i = beg; i < n; i += s)
const double PI = acos(-1);

using namespace std;

inline int mod(int n, int m = M) {
  int ret = n % m;
  if (ret < 0) ret += m;
  return ret;
}

int exp(int n, int k) {
  if (k == 0) return 1;
  if (k == 1) return n;
  int ax = exp(n, k / 2);
  ax = mod(ax * ax);
  if (k % 2) ax = mod(ax * n);
  return ax;
}

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

int calc(vector<ii>& v) {
  int ans = 0;
  for (ii p : v) {
    ans = max(ans, abs(p.ff - v[0].ff) + abs(p.ss - v[0].ss));
  }
  return ans;
}
//#define MULTIPLE_TEST_CASE
void solution() {
  int n;
  cin >> n;
  vector<ii> v(n);
  int max_x = -INF, min_x = INF, max_y = -INF, min_y = INF;
  for (ii& p : v) {
    int x, y;
    cin >> x >> y;
    max_x = max(max_x, x + y);
    min_x = min(min_x, x + y);
    max_y = max(max_y, x - y);
    min_y = min(min_y, x - y);
    p.ff = x + y;
    p.ss = x - y;
  }

  cout << max(max_x - min_x, max_y - min_y) << endl;
}

int32_t main() {
  DESYNC;
  mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  int t = 1;
#ifdef MULTIPLE_TEST_CASE
  cin >> t;
#endif
  while (t--) solution();
}


Measured memory_bytes: 6400
#include<bits/stdc++.h>
#define STDIO
#define MOD 1000000007
#define testbit(mask,i) (((mask)>>(i))&1)
#define setbit(mask,i) ((mask)|(1<<i))
#define delbit(mask,i) ((mask)^(1<<i))
#define lowbit(x) ((x)&(-x))
#define INF MOD
using namespace std;
int h,w,k;
int qzh[12][1020];
int ngrid[12][1020];
char c;
vector<int> cuts;
int pre[12];
int get(int mask){
	int res=__builtin_popcount(mask);
	cuts.clear();
	for(int i=1;i<h;i++){
		if(mask&1)
			cuts.push_back(i);
		mask>>=1;
	}
	cuts.push_back(h);
	int lst=0;
	for(int i=0;i<cuts.size();i++){
		//lst+1...i separate
		for(int j=1;j<=w;j++){
			ngrid[i+1][j]=(qzh[cuts[i]][j]-qzh[lst][j]);
			if(ngrid[i+1][j]>k)
				return 2e9;
		}
		lst=cuts[i];
		pre[i+1]=0;
	}
	bool canok;
	for(int i=1;i<=w;i++){
		canok=true;
		for(int j=1;j<=cuts.size();j++){
			if(ngrid[j][i]+pre[j]>k){
				canok=false;
				break;
			}
		}
		if(!canok){
			res++;
			for(int j=1;j<=cuts.size();j++)
				pre[j]=0;
		}
		for(int j=1;j<=cuts.size();j++){
			pre[j]+=ngrid[j][i];
		}
	}
	return res;
}
int main(){
	#ifndef STDIO
		freopen("input.in","r",stdin);
		freopen("output.out","w",stdout);
	#endif
	ios::sync_with_stdio(0);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>h>>w>>k;
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			cin>>c;
			qzh[i][j]=(c-'0');
		}
	}
	for(int i=1;i<=h;i++){
		for(int j=1;j<=w;j++){
			qzh[i][j]+=qzh[i-1][j];
		}
	}
	int rrr=1e9,cnd; 
	for(int i=0;i<(1<<(h-1));i++){
		cnd=get(i);
		rrr=min(rrr,cnd);
	}
	cout<<rrr<<endl;
	return 0;
}


Measured memory_bytes: 384
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <complex>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef string str;
typedef std::pair<ll,ll> pl;
typedef std::map<string, ll> msl;
typedef std::map<ll, ll> mll;
typedef std::vector<ll> vl;
typedef std::vector<pl> vpl;
const long double EPS = 1e-9;

#define rep(i, n) for(ll (i) = 0; (i) < (n) ; (i)++ )
#define For(i, a, b) for(ll (i) = (a); (i) < (b) ; (i)++ )
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define tol(c) char((c)+0x20)
#define tou(c) char((c)-0x20)
#define pb push_back
#define mp make_pair
#define pr(a) cout << (a)
#define prl(a) cout << (a) << endl
#define prl2(a,b) cout << (a) << " " << (b) << endl
#define prs(a) cout << (a) << " "
#define yn(condition) if ((condition)) prl("Yes"); else prl("No");
#define YN(condition) if ((condition)) prl("YES"); else prl("NO");
#define rpr(i,n,ans) rep((i),(n)) prs((ans[(i)]))
#define cpr(i,n,ans) rep((i),(n)) prl((ans[(i)]))
#define in1(a) cin >> (a)
#define in2(a,b) cin >> (a) >> (b)
#define in3(a,b,c) cin >> (a) >> (b) >> (c)
#define in4(a,b,c,d) cin >> (a) >> (b) >> (c) >> (d)
#define rin1(i,n,a) rep((i),(n)) cin >> (a[(i)])
#define rin2(i,n,a,b) rep((i),(n)) cin >> (a[(i)]) >> (b[(i)])
#define rin3(i,n,a,b,c) rep((i),(n)) cin >> (a[(i)]) >> (b[(i)]) >> (c[(i)])
#define e1 first
#define e2 second
#define ctol(c) ll((c)) - ll('0')
#define ltos(n) to_string((n))
#define items(kv, v) for(auto &(kv): (v))
#define ndig(N, n) ctol(ll(ltos((N))[ll(ltos((N)).length()) - (n)]))
#define beto(a,b,c) (a) < (b) && (b) < (c)
#define betc(a,b,c) (a) <= (b) && (b) <= (c) 
#define rsort(a,n) sort(a,a+n,greater<>())

const ll mod = 1e9 + 7;
const ll INF = mod * mod;
const ll MAX_N = 100000;

int main(void){
    str s,t;

    in2(s,t);

    sort(all(s));
    sort(rall(t));
    yn(s<t);

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define MAX 10000005
#define ll long long
#define upperlimit 1000100
#define INF 1e18
#define inf 1e9
#define eps 1e-8
#define endl '\n'
#define pcc pair<char,char>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define tr(container,it) for(typeof(container.begin()) it=container.begin();it!=container.end();it++)
#define mod 1000000007
#define slld(t) scanf("%lld",&t)
#define sd(t) scanf("%d",&t)
#define pd(t) printf("%d\n",t)
#define plld(t) printf("%lld\n",t)
#define mp(a,b) make_pair(a,b)
#define FF first
#define SS second
#define pb(x) push_back(x)
#define vi vector<int>
#define clr(a) memset(a,0,sizeof(a))
#define debug(a) printf("check%d\n",a)
#define ios ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
ll x[100004];
long long int modpow (long long int a) {
	int res = 1;
ll j=mod-2LL;
	while (j > 0)
		if (j & 1) {
			res = (res * a) % mod;
			--j;
		}
		else {
			a = (a * a) % mod;
			j >>= 1;
		}
	return res %mod;
}
ll dp[1003][1034];
ll ff[1004];ll pinv[1003][1034];
ll powr(ll i,ll j)
{
    if(j==0)return 1;
    ll h=powr(i,j/2);
    h=h*h;
    h=h%mod;
    if(j%2==0)return h;
    h=h*i;
    h=h%mod;
    return h;
}
ll fact[1032];
int main()
{
    ios;
    ll n,a,b,c,d;
    cin>>n>>a>>b>>c>>d;
    b=min(b,n/c);
    dp[a][0]=1;
    fact[0]=1;
    ff[0]=modpow(1LL);
    for(ll i=1;i<=1003;i++){fact[i]=fact[i-1]*i;fact[i]%=mod;ff[i]=modpow(fact[i]);}
    for(ll i=a;i<=b;i++)
    {
        for(ll j=c;j<=d;j++)
        {
            pinv[i][j]=modpow(powr(fact[i],j));
        }

    }
    for(ll i=c;i<=d&&i*a<=n;i++)
    {
        dp[a][i*a]=fact[i*a]*modpow(powr(fact[a],i));
        dp[a][i*a]=dp[a][i*a]%mod;
        dp[a][i*a]*=modpow(fact[i]);
        dp[a][i*a]%=mod;
    }
   // b=min(b,n/c);

    for(ll i=a+1;i<=b;i++)
    {
        for(ll j=0;j<=n;j++)
        {
            dp[i][j]=dp[i-1][j];
            for(ll k=c;k<=d&&j-i*k>=0;k++)
            {
               // cout<<i<<" "<<j<<" "<<k<<endl;
             //  if(dp[i-1][j-i*k]==0)continue;
                ll h=fact[j]*ff[k];
                h=h%mod;
                h=h*pinv[i][k];
                h=h%mod;
                h=h*ff[j-i*k];
                h=h%mod;
                h=h*dp[i-1][j-i*k];
                h=h%mod;
                dp[i][j]+=h;
                dp[i][j]%=mod;
            }

        }
        //cout<<i<<endl;
    }
    cout<<dp[b][n]<<endl;



}


Measured memory_bytes: 16384
H,N = map(int,input().split())
Magic =[]
A =[]
E =[]
for i in range(N):
    a,b = map(int,input().split())
    Magic.append((a,b))
    A.append(a)
    E.append(a/b)
MAX_A = H+max(A)
E_MIN = min(E)
WORST = int(MAX_A/E_MIN) +2
DP = [[WORST] * (MAX_A+1) for i in range(N)]
for i in range(N):
    if i == 0:
        for j in range(1,MAX_A//Magic[0][0]+1):
            DP[0][j*Magic[0][0]] = Magic[0][1]*j
    else:
        for j in range(Magic[i][0]-1):
            DP[i][j] = DP[i-1][j]
        DP[i][Magic[i][0]] = min(DP[i-1][Magic[i][0]],Magic[i][1])
        for j in range(Magic[i][0]+1,(MAX_A+1)):
            DP[i][j]=min(DP[i-1][j],DP[i-1][j-Magic[i][0]]+Magic[i][1],DP[i][j-Magic[i][0]]+Magic[i][1])
print(min(DP[N-1][H:MAX_A]))

Measured memory_bytes: 126704
#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    if (a < b) {
        cout << string(b, '0' + a) << "\n";
    }
    else {
        cout << string(a, '0' + b) << "\n";
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
#define rg register
#define oo 0x7fffffff
#define ll long long
using namespace std;
inline int read()
{
	int out=0,fh=1;
	char jp=getchar();
	while ((jp>'9'||jp<'0')&&jp!='-')
		jp=getchar();
	if (jp=='-')
		{
			fh=-1;
			jp=getchar();
		}
	while (jp>='0'&&jp<='9')
		{
			out=out*10+jp-'0';
			jp=getchar();
		}
	return out*fh;
}
const int MAXN=5e2+10;
const int MAXM=1e5+10;
int n;
ll Mat[MAXN][MAXN];
int pcnt=0,prime[MAXM],vis[MAXM];
void Linear_Shaker()
{
	for(rg int i=2;i<=MAXM;++i)
		{
			if(!vis[i])
				prime[++pcnt]=i;
			for(rg int j=1;i*prime[j]<=MAXM;++j)
				{
					vis[i*prime[j]]=1;
					if(i % prime[j]==0)
						break;
				}
		}
}
ll GCD(ll x,ll y)
{
	return y==0? x: GCD(y,x%y);
}
ll LCM(ll x,ll y)
{
	return x / GCD(x,y) * y;
}
int main()
{
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	n=read();
	if(n==2)
		{
			printf("4 7\n23 10");
			return 0;
		}
	Linear_Shaker();
	for(rg int i=1;i<=n;++i)
		for(rg int j=1;j<=n;++j)
			Mat[i][j]=1ll;
	for(rg int i=1;i<=n;++i)
		for(rg int j=1;j<=n;++j)
			{
				if((i&1)==(j&1))
					{
						Mat[i][j]=1ll* prime[(i+j)/2] * prime[(i+n+1-j)/2+n];
						Mat[i+1][j]=LCM(Mat[i+1][j],Mat[i][j]);
						Mat[i-1][j]=LCM(Mat[i-1][j],Mat[i][j]);
						Mat[i][j+1]=LCM(Mat[i][j+1],Mat[i][j]);
						Mat[i][j-1]=LCM(Mat[i][j-1],Mat[i][j]);
					}
			}
	for(rg int i=1;i<=n;++i)
		for(rg int j=1;j<=n;++j)
			printf("%lld%c",(i&1)==(j&1)?Mat[i][j]:Mat[i][j]+1,j==n?'\n':' ');
	//fclose(stdin);
	//fclose(stdout);
	return 0;
}


Measured memory_bytes: 5632
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		List<Long> list = new ArrayList<>();
		for(int i = 0; i < N; i++) {
			list.add(sc.nextLong());
		}
		Collections.sort(list);
		List<Pair> con = new ArrayList<>();
		for(int i = 0; i < M; i++) {
			int b = sc.nextInt();
			long c = sc.nextLong();
			con.add(new Pair(c, b));
		}
		con.sort(Comparator.comparing(Pair::getValue).reversed());
		long ans = 0;
		boolean end = false;
		for(Pair pair : con) {
			long value = pair.getValue();
			int sum = pair.getSum();
			while(sum > 0) {
				long first = list.get(0);
				list.remove(0);
				if(value > first) {
					ans += value;
				} else {
					ans += first;
					end = true;
				}
				if(list.isEmpty()) {
					end = true;
					break;
				}
				sum--;
			}
			if(end) {
				break;
			}
		}
		for(Long j : list) {
			ans += j;
		}
		System.out.println(ans);
	}

}

class Pair {
	private long value;
	private int sum;

	protected Pair(long value, int sum) {
		super();
		this.value = value;
		this.sum = sum;
	}

	public long getValue() {
		return value;
	}

	public void setValue(long value) {
		this.value = value;
	}

	public int getSum() {
		return sum;
	}

	public void setSum(int sum) {
		this.sum = sum;
	}

	@Override
	public String toString() {
		return "Pair [value=" + value + ", sum=" + sum + "]";
	}

}


Measured memory_bytes: 106388
import java.util.*;

public class Main{
    public static void main (String[] args){
        Scanner scan = new Scanner(System.in);
//
        String str1 = scan.next();
        String str2 = scan.next();
        if(str1.length() != str2.length()){
            System.out.println("No");
            return;
        }
        if(str1.length() == 1){
            if(str1.equals(str2)){
                System.out.println("Yes");
            }else{
                System.out.println("No");
            }            
            return;
        }
//
        String[] strArry1 = new String[str1.length()];
        String[] strArry2 = new String[str2.length()];
//
        setArray(strArry1, str1);
        setArray(strArry2, str2);
//
        String[] wstrArry = new String[str1.length()];
            for (int i = 0; i < strArry1.length; i++){
                cnvArry(wstrArry,strArry1);
                if(comp(wstrArry,strArry2) == 0){
                    System.out.println("Yes");
                    return;
                }
            }            
            System.out.println("No");
            return;
    }
/*
    split strings
*/
    public static void setArray(String[] array, String str){
        for (int i = 0; i < array.length; i++){
            array[i] = String.valueOf(str.charAt(i));
        }
    }
/*
    compare strings
*/
    public static int comp(String[] wstrArry, String[] strArry2){
        for (int i = 0; i < wstrArry.length; i++){
            if(wstrArry[i].equals(strArry2[i])){
                continue;
            }else{                
                return 1;
            }
        }
        return 0;        
    }
/*
    convert
*/
    public static void cnvArry(String[] wstrArry, String[] strArry1){
        wstrArry[0] = strArry1[strArry1.length - 1];
        for (int j = 0; j < strArry1.length-1; j++){
            wstrArry[j+1] = strArry1[j];
        }
//
        for (int k = 0; k < strArry1.length; k++){
            strArry1[k] = wstrArry[k];
        }
    }
}



Measured memory_bytes: 22996
import math

def strictintsqrt(N):
    tmp=int(math.sqrt(N))
    while(tmp**2-N>0):
        tmp-=1
    return tmp

N=int(raw_input())
for n in range(N):
  a,b=map(int, raw_input().split())
  a,b=min(a,b),max(a,b)
  #tmp=int(math.sqrt(a*b-1))
  tmp=strictintsqrt(a*b-1)
  ans=tmp*2
  if ans!=0:
      if a<=tmp: ans-=1
      if (a*b-1)/tmp== a:
          ans-=1
      elif (a*b-1)/tmp == tmp:
          ans-=1
  print ans
  """  if a==b:    ans-=0
  else: ans-=1
  if (a*b-1)/a == a: ans-=1
  if tmp*tmp==a*b-1: ans-=1
  print max(ans,0)
  """


Measured memory_bytes: 2692
/*
g++ -ggdb -fsanitize=address -std=c++14 B.cpp && ./a.out <<< "1024"
*/

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

#define rep(i, a, b) for (int i = a; i < (b); i++)
#define trav(a, x) for (auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

template <typename A>
string to_string(A v) { int cnt = 0; string res; for (const auto &x : v) { if (cnt++) res += " "; res += to_string(x); } return "[" + res + "]"; }
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string) s); }

void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) { cerr << " " << to_string(H); debug_out(T...); }
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)

int main() {
    cin.sync_with_stdio(0); cin.tie(0);
    cin.exceptions(cin.failbit);

    ll x; cin >> x;

    ll h = (x / 500) * 1000;

    x = x % 500;
    h += (x / 5) * 5;

    cout << h << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <set>
#include <stdio.h>
#include <queue>
#include <math.h>
using namespace std;
typedef long long int lli;
const long long int MaxN=100005;
const lli mod=1e9+7;
#define fst first
#define snd second
#define mp make_pair
	queue <int> cola;
   vector <int> ady[MaxN];
	int vis[MaxN];
	int padre[MaxN];
	void bfs(int inicio){
		int i,j,p,q;
		int e,v;
		e=inicio;
		cola.push(e);
		vis[e]=1;
		while(!cola.empty()){
			e=cola.front();
			cola.pop();
			for(i=0;i<ady[e].size();i++){
				v=ady[e][i];
				if(vis[v])continue;
				padre[v]=e;
				vis[v]=1;
				cola.push(v);
			}
		}
					
	}
int main(){
	cin.tie(0),ios_base::sync_with_stdio(0);
	int N,M,i,j,p,q;
	cin>>N>>M;
	for(i=1;i<=N;i++)padre[i]=-1;
	for(i=0;i<M;i++){
		cin>>p>>q;
		ady[p].push_back(q);
		ady[q].push_back(p);
	}
	bfs(1);
	for(i=2;i<=N;i++){
		if(padre[i]==-1){
			cout<<"No\n";
			return 0;
		}		
	}
	cout<<"Yes\n";
	for(i=2;i<=N;i++){
		cout<<padre[i]<<"\n";
	}
}


Measured memory_bytes: 10496
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()
count_of_a = Counter(A)
# すでに出現した倍数の場合はアウト
ans = 0
max_A = max(A)
dp = [True] * (max_A+1)
happpend = set()
for a in A:
    if count_of_a[a] >= 2:
        # 複数出現するとしても，初めての要素の場合は処理を行う
        if a in happpend:
            continue
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
    else:
        if dp[a]:
            ans += 1
        x = a*2
        while x <= max_A:
            dp[x] = False
            x += a
        happpend.add(a)
print(ans)


Measured memory_bytes: 51324
#include <iostream>
#include <string>

char chshift(char ch){
  if(ch>='a' && ch<='z'){
    return (ch-'a'+1)%26+'a';
  }else{
    return ch;
  }
}

std::string strshift(std::string s){
  for(int i=0; i<s.length(); i++){
    s[i] = chshift(s[i]);
  }
  return s;
}

bool valid_text_p(std::string str){
  return str.find("the") != -1 || str.find("that") != -1 || str.find("this") != -1;
}

int main(){
  std::string s;
  while(std::getline(std::cin,s), !std::cin.eof()){
    for(;;s = strshift(s)){
      if(valid_text_p(s)){
	std::cout << s << std::endl;
	break;
      }
    }
  }
  return 0;
}

Measured memory_bytes: 1184
#include<bits/stdc++.h>
#include<stdio.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define _USE_MATH_DEFINES
#define f first
//#define s second
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define INF 1000000000000000000
#define MAXN (int)(1e7)+1
#define MOD 1000000007
 
using namespace std;
 
typedef long long int ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pwi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector< vector<pair<ll,ll > > > wGraph;
typedef vector<vector<ll> > graph;
//typedef vector<vector<ll> > matrix;

int main(){
 
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout<<std::fixed;
    cout<<std::setprecision(2);

    ll a;
    cin>>a;
    cout<<a+a*a+a*a*a<<endl;

    return 0;   
}


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

int ctoi(char c) {
	return c - '0';
}

int main() {
	string a, b, ans;
	cin >> a >> b;
	if (a.size() > b.size())ans = "GREATER";
	else if (a.size() < b.size())ans = "LESS";
	else {
		bool f = true;
		for (int i = 0; i < a.size(); i++) {
			if (a[i] != b[i]) {
				if(ctoi(a[i])>ctoi(b[i]))ans= "GREATER";
				else ans = "LESS";
				f = false;
				break;
			}
		}
		if (f)ans = "EQUAL";
	}
	cout << ans << endl;
	return 0;
}

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

int main() {
    int A, B, res=0;
    cin >> A >> B;

    for(int i=0; i<2; i++) {
        if (A>=B) {
            res += A;
            A -= 1;
        } else {
            res += B;
            B -= 1;
        }
    }

    cout << res << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
#define all(x) x.begin(),x.end()
#define rep(i,j,n) for (long long i = j; i < (long long)(n); i++)
#define _GLIBCXX_DEBUG
#define MOD 1000000007
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
//name[i][j]-> vvl name(i,vl(j))
//map<int,int>mp
//余りを切り上げる =>  (a + b - 1) / b 

signed main(){
	int n; cin>>n;
	vi a(n),b(n),c(n-1);
	rep(i,0,n) cin>>a[i];
	rep(i,0,n) cin>>b[i];
	rep(i,0,n-1) cin>>c[i];
	int ans=0;
	rep(i,0,n){
		ans+=b[a[i]-1];
		if(i>0){
			if(a[i-1]+1==a[i]){
				//cout<<"i:"<<i<<endl;
				ans+=c[a[i-1]-1];
			}
		}
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;
	
	return 0;
}

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

int main(int argc, char *argv[])
{
  int a, b, c, ans = 0;
  cin >> a >> b >> c;
  for(int i = a; i <= b; i++) {
    if((c % i) == 0) ans++;
  }
  cout << ans << endl;

  return 0;
}



Measured memory_bytes: 3100
N = int(input())
F = []
for i in range(N):
    F.append(list(map(int,input().split())))
P = []
for i in range(N):
    P.append(list(map(int,input().split())))

ans = -999999999999999999
for i in range(1 << 10):
    A = [0] * N

    cnt = 0
    for j in range(10):
        if (i >> j) & 1:
            cnt += 1
            for k in range(N):
                if F[k][j] == 1:
                    A[k] += 1
    if cnt == 0:
        continue
    tmp = 0
    for t in range(N):
        tmp += P[t][A[t]]

    if tmp > ans:
        ans = tmp
print(ans)


Measured memory_bytes: 3064
n = int(raw_input())
for l in range(n):
	x1,y1,x2,y2,x3,y3,x4,y4 = map(float,raw_input().split())
	if abs((y4-y3)*(x2-x1)-(y2-y1)*(x4-x3))< 1e-10:
		print "YES"
	else:
		print "NO"

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

struct py {
    int x;
    int y;
    int h;
};

int height[100][100] = {-1};

int main() {

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<py> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i].x >> v[i].y >> v[i].h;
    }

    int idx;
    for (int i = 0; i < n; i++) {
        if (v[i].h > 0) {
            idx = i;
            break;
        }
    }

    bool b;
    py ans;
    for (int y = 0; y <= 100; y++) {
        for (int x = 0; x <= 100; x++) {
            b = true;

            int height = v[idx].h + fabs(v[idx].x - x) + fabs(v[idx].y - y);

            for (int i = 0; i < n; i++) {
                int t = max((int)(height - fabs(v[i].x - x) - fabs(v[i].y - y)), 0);

                if (t != v[i].h) {
                    b = false;
                    break;
                }
            }

            if (b) {
                ans.x = x;
                ans.y = y;
                ans.h = height;
                break;
            }
        }
        if (b) {
            break;
        }
    }

    cout << ans.x << " " << ans.y << " " << ans.h << endl;
}

Measured memory_bytes: 256
import sys
read = sys.stdin.read

M = int(input())
dc = map(int, read().split())
dig = [0] * 10
cnt = 0
answer = 0
for d, c in zip(*[iter(dc)] * 2):
    dig[d] += c

trans = dict()
for i in range(10):
    if i < 5:
        trans[i] = i + i
    elif i == 5:
        trans[i] = 1
    else:
        trans[i] = trans[i - 1] + 2

while True:
    tmp = [0] * 10
    for i, x in enumerate(dig):
        q, r = divmod(x, 2)
        if x >= 2:
            if i < 5:
                answer += q
                tmp[trans[i]] += q
                tmp[i] += r
            else:
                answer += q * 2
                tmp[trans[i]] += q
                tmp[i] += r
        else:
            tmp[i] += x

    dig = tmp.copy()
    for i in dig:
        if i > 1:
            break
    else:
        break

last = [i for i in range(10) if dig[i] == 1]
while len(last) > 1:
    a = last.pop()
    b = last.pop()
    c = a + b
    if c >= 10:
        answer += 2
        last.append(c // 10 + c % 10)
    else:
        answer += 1
        last.append(c)

print(answer)

Measured memory_bytes: 24132
#include<iostream>

using namespace std;

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

	if (d == 0 && n == 100) {
		cout << 101 << endl;
	}
	else if (d == 1 && n == 100) {
		cout << 101 * 100 << endl;
	}
	else if (d == 2 && n == 100) {
		cout << 101 * 10000 << endl;
	}
	else if (d == 0) {
		cout << n << endl;
	}
	else if (d == 1) {
		cout << n * 100 << endl;
	}
	else if (d == 2) {
		cout << n * 10000 << endl;
	}
	

	return 0;
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

int main()
{ios_base::sync_with_stdio(false);
ll n,x,a[100005];
cin>>n>>x;

int ans=0;

rep(i,0,n-1)
{
	cin>>a[i];
}
sort(a,a+n);

rep(i,0,n-1)
{
	x-=a[i];
	if(x>=0)ans++;
}
if(x>0)ans--;
ol(ans);

return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <functional>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <tuple>
#include <cassert>
#include <exception>
#include <iomanip>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> P;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<P> vp;
#define rep(i,a,n) for(ll i = (a);i < (n);i++)
#define per(i,a,n) for(ll i = (a);i > (n);i--)
#define lep(i,a,n) for(ll i = (a);i <= (n);i++)
#define pel(i,a,n) for(ll i = (a);i >= (n);i--)
#define clr(a,b) memset((a),(b),sizeof(a))
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(),(c).end()
#define sz size()
#define print(X) cout << (X) << endl
static const int INF = 1e+9+7;
ll n,m,l;
string s,t;
int d[200010],dp[1010][1010];
double w[1000],v[1000];
double box[200010];
char field[200][200];

vll vec;

void func(){
  for(int i = 0;i <= sqrt(pow(2,15));i++)vec.pb(i*i);
  // rep(i,0,vec.sz)print(vec[i]);
}

bool bs(int p){
  if(p < 0)return false;
  int mx = vec.sz;
  int mn = 0;
  while(mx - mn > 1){
    int mid = (mn + mx) / 2;
    if(vec[mid] == p)return true;
    if(vec[mid] < p)mn = mid;
    else mx = mid;
  }
  return false;
}

int main(){
  func();
  while(cin >> n && n){
    ll ans = 0;
    rep(i,0,vec.sz){
      if(n - vec[i] < 0)break;
      rep(j,i,vec.sz){
        if(n - vec[i] - vec[j] < 0)break;
        rep(k,j,vec.sz){
          if(n - vec[i] - vec[j] - vec[k] < 0 || (n - vec[i] - vec[j] - vec[k]) < max(max(vec[i],vec[j]),vec[k]))break;
          if(bs(n - (vec[i] + vec[j] + vec[k]))){
            // cout << vec[i] << ":" << vec[j] << ":" << vec[k] << ":" << n-vec[i]-vec[j]-vec[k] << endl;
            ans++;
          }
        }
      }
    }
    print(ans);
  }
  return 0;
}


Measured memory_bytes: 3016
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;

int main()
{
	string s; cin>>s;
	int n=s.size();
	int k; cin>>k;
	string ans[5*n-4];
	for(int i=0;i<(5*n-4);i++) ans[i]="zzzzz";
	for(int i=0;i<n;i++){
		ans[i]=s.substr(i,1);
	}
	for(int i=0;i<n-1;i++){
		ans[i+n]=s.substr(i,2);
	}
	for(int i=0;i<n-2;i++){
		ans[i+n*2]=s.substr(i,3);
	}
	for(int i=0;i<n-3;i++){
		ans[i+n*3]=s.substr(i,4);
	}
	for(int i=0;i<n-4;i++){
		ans[i+n*4]=s.substr(i,5);
	}
	sort(ans,ans+5*n-5);
	string tmp=ans[0],out[5]; out[0]=ans[0];
	int x=1,i=0;
	while(x<k){
		if(tmp!=ans[i]){
			out[x]=ans[i]; tmp=ans[i]; x++;
		}
		i++;
	}
	cout<<out[k-1]<<endl;
	return 0;
}


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

#ifdef DEBUG
    #include "debug.h"
    #define DEB
    #define dump(...)                                                              \
        DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
                << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
                << endl                                                            \
                << "    ",                                                         \
            dump_func(__VA_ARGS__)
#else
    #define DEB if (false)
    #define dump(...)
#endif


// http://beet-aizu.hatenablog.com/entry/2018/04/08/145516
template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
  return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}

//////////////////

#define int long long
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)

#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
#define ALL(v) (v).begin(), (v).end()
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
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; }

//*
#define mod 1000000007 /*/
#define mod 998244353 //*/

typedef pair<int, int> P;
#define INF (1LL<<60)



void solve(){
    int N;
    cin >> N;
    vector<int> A(N), B(N);
    rep(i,N) cin >> A[i] >> B[i];
    
    sort(ALL(A));
    sort(ALL(B));
    
    if(N%2==1){
        int midA = A[(N-1)/2];
        int midB = B[(N-1)/2];
        cout << midB - midA + 1 << endl;
    }else{
        int midA = A[N/2-1] + A[N/2];
        int midB = B[N/2-1] + B[N/2];
        cout << midB - midA + 1 << endl;
    }
    
}


signed main(){
    cout << fixed << setprecision(18);
    cerr << fixed << setprecision(18);
    solve();
}


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

int a[100],b[100];
int dp[100][100];

int main(){
	int n,i,j,k;
	cin >> n;
	for(i=0;i<n;i++) cin >> a[i] >> b[i];
	for(i=0;i<n;i++) for(j=0;j<n;j++) dp[i][j] = INT_MAX;
	for(i=0;i<n;i++) dp[i][i] = 0;
	for(i=2;i<=n;i++){
		for(j=0;j<=n-i;j++){
			for(k=j+1;k<j+i;k++){
				dp[j][j+i-1] = min(dp[j][j+i-1] , dp[j][k-1] + dp[k][j+i-1] + a[j] * b[k-1] * a[k] * b[j+i-1]);
			}
		}
	}
	cout << dp[0][n-1] << endl;
}

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

using namespace std;
#define rep(i, N) for(int i=0;i<int(N);++i)
#define rep1(i, N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
#define print(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<_<<", "; cerr<<"]"<<endl; }
#define printpair(v) { cerr<<#v<<": [ "; for(auto _ : v) cerr<<"{"<<_.first<<","<<_.second<<"}"<<", "; cerr<<"]"<<endl; }
#define dump(x) cerr<<#x<<": "<<x<<endl;
#define bit(k) (1LL<<(k))
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template<class T> using vec = vector<T>;
template<class T> using vvec = vector<vec<T>>;

template<typename T1, typename T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
    os << "{" << p.first << ", " << p.second << "}";
    return os;
}

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 INF = (ll) 1e9;
const ll INFLL = (ll) 1e18 + 1;
const ll MOD = (ll) 1e9 + 7;
const double PI = acos(-1.0);

/*
const int dx[8] = {1, 0, -1, 0, 1, -1, -1, 1};
const int dy[8] = {0, 1, 0, -1, 1, 1, -1, -1};
const string dir = "DRUL";
*/

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    int a,b;
    cin >> a >> b;
    cout << a * b << endl;
}

Measured memory_bytes: 3644
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
using namespace::std;
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
// #include <boost/multiprecision/cpp_dec_float.hpp>
// #include <boost/multiprecision/cpp_int.hpp>
// #include <boost/numeric/interval.hpp>
// #include <boost/numeric/interval/io.hpp>
// #include <boost/intrusive/rbtree.hpp>
// #include <boost/geometry.hpp>
// #include <boost/geometry/geometries/linestring.hpp>
// #include <boost/geometry/geometries/polygon.hpp>
// #include <boost/geometry/geometries/point_xy.hpp>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace __gnu_pbds;
using namespace::std;
// namespace mp = boost::multiprecision;
// typedef mp::number<mp::cpp_dec_float<0>> cfloat;
// typedef mp::cpp_int cint;
typedef long long lint;
typedef long long ll;
typedef long double ldouble;
typedef vector<lint> vec;
typedef vector<vector<lint>> mat;
typedef vector<vector<vector<lint>>> mat3;
typedef vector<double> dvec;
typedef vector<vector<double>> dmat;
typedef vector<vector<vector<double>>> dmat3;
typedef vector<string> svec;
typedef vector<vector<string>> smat;
typedef vector<vector<vector<string>>> smat3;
typedef vector<pair<lint,lint>> pvec;
typedef vector<vector<pair<lint,lint>>> pmat;
typedef vector<vector<vector<pair<lint,lint>>>> pmat3;
#define rep(i, n) for(lint i = 0; i < (lint)(n); i++)
#define irep(i) for(lint i = 0;; i++)
#define irep1(i) for(lint i = 1;; i++)
#define irep2(i) for(lint i = 2;; i++)
#define rrep(i, n) for(lint i = (lint)(n-1); i >-1; i--)
#define rrepi(i,a,b) for(lint i = (lint)(b-1); i >a-1; i--)
#define repi(i,a,b) for(lint i=lint(a);i<lint(b);i++)
#define rep2(i,a,b,c) for(lint i=lint(a);i>lint(b);i+=c)
#define all(x) (x).begin(),(x).end()
#define PI 3.141592653589793
#define dist(x1,y1,x2,y2) (pow(pow(x2-x1,2)+pow(y2-y1,2),0.5))
#define output(v) do{bool f=0;for(auto i:v){cout<<(f?" ":"");if(i>INF/2)cout<<"INF";else cout<<i;f=1;}cout<<"\n";}while(0)
#define output2(v) for(auto j:v)output(j);
#define input(a,n) lint n;cin>>n;vector<lint>a(n);rep(i,n)cin>>a[i];
#define SUM(v) accumulate(all(v),0LL)
#define INF (1LL<<60)
#define IINF (1<<30)
#define EPS (1e-10)
#define LINF 9223372036854775807
#define MOD 1000000007
#define endl "\n"
template<typename T=lint>T in(){return *istream_iterator<T>(cin);}
inline lint gcd(lint a,lint b){return b?gcd(b,a%b):a;}
inline lint lcm(lint a,lint b){return a*b/gcd(a,b);}
inline bool chmin(auto& s,const auto& t){bool res=s>t;s=min(s,t);return res;}
inline bool chmax(auto& s,const auto& t){bool res=s<t;s=max(s,t);return res;}
vector<lint> dx={-1,1,0,0,1,1,-1,-1};
vector<lint> dy={0,0,-1,1,1,-1,1,-1};

int main(){
    string s;
    cin>>s;
    rep(i,s.size()){
        if(i%2==0&&s[i]=='L'){
            cout<<"No"<<endl;
            return 0;
        }
        if(i%2==1&&s[i]=='R'){
            cout<<"No"<<endl;
            return 0;
        }
    }
    cout<<"Yes"<<endl;
}

Measured memory_bytes: 256