akhauriyash/Code-Regression huggingface dataset:
//ヘッダー
#include<bits/stdc++.h>
using namespace std;

//型定義
typedef long long ll;

//定数
const int INF=1e+9;
const int MOD=1e+9+7;

//REPマクロ
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REP2(i,a,b) for(ll i=a;i<(ll)(b);i++)
#define REPD2(i,a,b) for(ll i=a;i>(ll)(b);i--)

// 多次元 vector 生成
template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}
template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

//vectorの扱い
#define ALL(x) (x).begin(),(x).end() //sortなどの引数省略
#define SIZE(x) ((ll)(x).size()) //size
#define MAX(x) *max_element(ALL(x)) //最大値
#define MIN(x) *min_element(ALL(x)) //最小値

int main(){
    int N;
    cin>>N;
    vector<ll> A(N);
    REP(i,N) cin>>A[i];
    REP(i,N){
      if(A[i]==0){
        cout<<0<<endl;
        return 0;
      }
    }
    ll ans=1;
    REP(i,N){
      if((double)A[i]-(double)(((double)(1000000000000000000))/(double)ans)>0){
        cout<<-1<<endl;
        return 0;
      }
      ans*=A[i];

    }

    if(ans>1000000000000000000){
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans<<endl;
}

Measured memory_bytes: 4048
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MAX_N = 100005;

ll distSum [MAX_N];
int subSize [MAX_N];

vector<int> adj [MAX_N];
void addEdge (int u, int v) {
  adj[u].push_back(v);
  adj[v].push_back(u);
}

void distSumDfs (int vertex, int parent, int source, int lvl, ll &ans) {
  ans += lvl;
  for (int nxt : adj[vertex]) {
    if (nxt != parent) {
      distSumDfs(nxt, vertex, source, lvl + 1, ans);
    }
  }
}

int main () {
  int vertexc;
  cin >> vertexc;

  vector<pair<ll, int>> elems;
  map<ll, int> src;
  fill(subSize + 1, subSize + vertexc + 1, 1);
  for (int i = 1; i <= vertexc; i++) {
    cin >> distSum[i];
    
    src[distSum[i]] = i;    
    elems.push_back(make_pair(distSum[i], i));
  }

  sort(elems.begin(), elems.end(), greater<pair<ll, int>>());

  for (pair<ll, int> pr : elems) {
    if (pr == elems.back()) {
      break;
    }
    
    int vertex = pr.second;
    ll parentSum = distSum[vertex] + subSize[vertex] - (vertexc - subSize[vertex]);
    if (src.count(parentSum) == 0) {
      cout << -1 << endl;
      return 0;
    }

    int parent = src[parentSum];
    addEdge(vertex, parent);
    subSize[parent] += subSize[vertex];
  }

  ll realD = 0;
  distSumDfs(elems.back().second, -1, elems.back().second, 0, realD);
  if (realD != elems.back().first) {
    cout << -1 << endl;
    return 0;
  }

  for (int i = 1; i <= vertexc; i++) {
    for (int u : adj[i]) {
      if (u > i) {
        cout << i << " " << u << '\n';
      }
    }
  }
}


Measured memory_bytes: 20208
#include <stdio.h>

int main(){
    int n,k;
    scanf("%d %d", &n,&k);
    long long int input[n];
    for(int i=0;i<n;i++){
        scanf("%lld", &input[i]);
    }

    for(int i=0;i<n-k;i++){
        if(input[i]<input[i+k]){
            puts("Yes");
        } else {
            puts("No");
        }  
    }
    return 0;
}

Measured memory_bytes: 3200
#include <iostream>

using namespace std;

int main() {
  int n, m, l;
  cin >> n >> m >> l;
  int as[n][m], bs[m][l];
  long long cs[n][l];
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < l; j++) {
      cs[i][j] = 0;
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> as[i][j];
    }
  }
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < l; j++) {
      cin >> bs[i][j];
    }
  }
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < l; j++) {
      for (int k = 0; k < m; k++) {
        cs[i][j] += (as[i][k] * bs[k][j]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << cs[i][0];
    for (int j = 1; j < l; j++) {
      cout << " " << cs[i][j];
    }
    cout << endl;
  }
}


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

int main(){
  int N,D;cin>>N>>D;
  vector<vector<int>>X(N,vector<int>(D));
  for(int i=0;i<N;i++){
    for(int j=0;j<D;j++){
      cin>>X[i][j];
    }
  }
  int ans=0;
  for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){
      int norm=0;
      for(int k=0;k<D;k++){
        int a=abs(X[i][k]-X[j][k]);
        norm+=a*a;
      }
      bool flag= false;
      for(int k=0;k<=norm;k++){
        if(k*k==norm) flag=true;
      }
      if(flag) ans++;
    }
  }
  cout<<ans<<endl;
}

      

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
 
int main() {
  vector<int> N(3);
  for(int i=0;i<3;i++){
    cin>>N[i];
  }
  sort(N.begin(),N.end());
  int ans=N[2]*10+N[1]+N[0];
  cout<<ans<<endl;
}

Measured memory_bytes: 256
function main(arg) {

    let n = Number(arg.split("\n")[0])
    let a = arg.split("\n")[1].split(" ").map(BigInt)

    let mod = BigInt(10**9+7)
    let sum = a.reduce((a,b)=>a+b, BigInt(0))

//  console.log(Number(sum))

    let ans=BigInt(0)
    for(let i=0; i<n; i++) {
        sum -= a[i]
        ans += a[i] * sum
        ans %= mod
    }
    console.log(Number(ans))

}
process.env.MYTEST
  ? (process.env.MYTEST === 'test' ? test() : main(require('fs').readFileSync('dev/stdin', 'utf8')))
  : main(require('fs').readFileSync('/dev/stdin', 'utf8'))

Measured memory_bytes: 73524
#include <string>
#include <iostream>
#include <array>
#include <algorithm>
#include <limits>
using namespace std;
typedef long long ll;

int main()
{
    int A, B, C, X, Y;
    cin >> A >> B >> C >> X >> Y;
    int min_price = numeric_limits<int>::max();
    int num_AB = 0;
    while (X >= num_AB / 2 || Y >= num_AB / 2)
    {
        int price = max(X - num_AB / 2, 0) * A + max(Y - num_AB / 2, 0) * B + num_AB * C;
        if (price < min_price)
            min_price = price;
        num_AB += 2;
    }
    cout << min_price << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using Graph = vector<vector<int>>;
#define rep(i,a,b) for (int i = (a); i < (b); i++ )
typedef pair<int,int> P;
typedef long long ll;
const int INF = 100000000;

int N;
long double dist(vector<int> &v, vector<vector<int>> &x) {
    long double ans_tmp = 0;
    rep(i,1, N) {
        ans_tmp += sqrt(pow(x[v[i]][0]-x[v[i-1]][0],2)+pow(x[v[i]][1]-x[v[i-1]][1],2));
    }
    return ans_tmp;

}

int main (){
    
    cin >> N;
    vector<int> v;
    rep(i,0,N) {
        v.push_back(i);
    }

    vector<vector<int>> x(N,vector<int> (2));
    rep(i,0,N) {
        cin >> x[i][0] >> x[i][1];
    }

    int p=1;
    rep(i,1,N+1) {
        p*=i;
    }

    long double ans = 0;
    do {
        ans += dist(v,x)/p;
    } while(next_permutation(v.begin(), v.end()));

    cout << fixed;
    cout << setprecision(9);
    cout << ans << endl;
}



Measured memory_bytes: 256
# Fast IO (only use in integer/float input)

# import os,io
# input=io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

constant = 10 ** 9

N = int(input())
numList = []
for _ in range(N):
    a = float(input())
    numList.append(round(constant * a))

ListTwoandFive = [] # 2 and 5 index
ListTwoandFivePartialSum = [] # sum of upper rectangle

for i in range(19):
    ListTwoandFive.append([])
    ListTwoandFivePartialSum.append([])
    for j in range(19):
        ListTwoandFive[i].append(0)
        ListTwoandFivePartialSum[i].append(0)

for elem in numList:
    cnt2 = 0
    cnt5 = 0
    while elem % 2 == 0:
        elem //= 2
        cnt2 += 1
    while elem % 5 == 0:
        elem //= 5
        cnt5 += 1
    ListTwoandFive[min(cnt2,18)][min(cnt5,18)] += 1

for i in range(18,-1,-1):
    for j in range(18,-1,-1):
        if i == 18 and j == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j]
        elif i == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i][j+1]
        elif j == 18:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i+1][j]
        else:
            ListTwoandFivePartialSum[i][j] = ListTwoandFive[i][j] + ListTwoandFivePartialSum[i+1][j] +\
                 ListTwoandFivePartialSum[i][j+1] - ListTwoandFivePartialSum[i+1][j+1]

cnt = 0

for i in range(19):
    for j in range(19):
        cnt += ListTwoandFive[i][j] * ListTwoandFivePartialSum[18 - i][18 - j]


cnt -=  ListTwoandFivePartialSum[9][9]
cnt //= 2

print(cnt)


Measured memory_bytes: 83384
import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        //Compute c1 = new Compute();//calc

        int count = 0;
        boolean sw = false;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        double dMax = Double.MIN_VALUE;
        double dMin = Double.MAX_VALUE;
        //StringBuilder answer=new StringBuilder();

        //input
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int s = sc.nextInt();

        for (int i=0;i<=k;++i)
        {
            for (int j = 0;j<=k;++j)
            {
                int a=s-i-j;
                if (a<=k && a>=0)
                {
                    ++count;
                }
            }
        }
        System.out.println(count);
    }
}

Measured memory_bytes: 22612
#!/usr/bin/env python3

import sys
import math
import random

def calc_sat_change(d, q): # d日目をコンテストqにチェンジしたときの満足度の差
  dif_sat = s[d-1][q-1] - s[d-1][ans[d-1]-1]

  lastday = 0
  nextday = D+1
  for i in reversed(range(d-1)):
    if ans[i] == q:
      lastday = i+1
      break
  for i in range(d, D):
    if ans[i] == q:
      nextday = i+1
      break
  dif_sat += c[q-1]*(d+1-lastday)*(nextday-d+1)

  lastday = 0
  nextday = D+1
  for i in reversed(range(d-1)):
    if ans[i] == ans[d-1]:
      lastday = i+1
      break
  for i in range(d, D):
    if ans[i] == ans[d-1]:
      nextday = i+1
      break
  dif_sat -= c[ans[d-1]-1]*(d+1-lastday)*(nextday-d+1)

  return dif_sat


D = int(input())
c = list(map(int, input().split()))
s = [list(map(int, input().split())) for _ in range(D)]

lastdays = [0] * 26
ans = [0] * D

for i in range(D):
  maxtmpsat = -1000000
  for j in range(26):
    tmpsat = s[i][j] + c[j] * (i+1 - lastdays[j]) # その日に何も開催しなかった場合との満足度の差
    if tmpsat > maxtmpsat:
      maxtmpsat = tmpsat
      ans[i] = j+1
  lastdays[ans[i]-1] = i+1

for _ in range(100000):
  d = random.randint(1, 5)
  q = random.randint(1, 26)
  if calc_sat_change(d, q) > 0:
    ans[d-1] = q

for i in range(D):
  print(ans[i])




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

int main() {
    string s;
    cin >> s;
    int n = s.size();
    int ans = 0;
    int cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (s[i] != 'A' && s[i] != 'C' && s[i] != 'G' && s[i] != 'T') continue;
        for (int j = i; j < n; ++j) {
            if (s[j] == 'A' || s[j] == 'C' || s[j] == 'G' || s[j] == 'T') cnt++;
            else break;
        }
        ans = max(ans, cnt);
        cnt = 0;
    }
    cout << ans << endl;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL);
	int a;
	cin>>a;
	int b;
	cin>>b;
	if(b==1)
	{
		cout<<0<<'\n';
		return 0;
	}
	float x=ceil(float(b-1)/(a-1));
	cout<<(int)x<<'\n';
	return 0;
}

Measured memory_bytes: 256
import sys
readline = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
#mod = 998244353
INF = 10**18
eps = 10**-7

s = readline().rstrip()
a = int(s[:2])
b = int(s[2:])
if 0 < a < 13 and 0 < b < 13:
    ans = "AMBIGUOUS"
elif 0 < a < 13:
    ans = "MMYY"
elif 0 < b < 13:
    ans = "YYMM"
else:
    ans = 'NA'
print(ans)


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



int main(){
    int h,w,k;
    cin >> h >> w >> k;
    vector<string> s(h);
    rep(i,h) cin >> s[i];
    int c[10][1005];
    int ans = 1e9;
    rep(div,1<<(h-1)){
        int g = 0;
        vector<int> id(h);
        id[0] = g;
        rep(i,h-1){
            if(div>>i&1) ++g;
            id[i+1]=g;
        }
        ++g;
        rep(i,g)rep(j,w) c[i][j] = 0;
        rep(i,h)rep(j,w) c[id[i]][j] += s[i][j] - '0';

        int num = g-1;
        vector<int> now(g);
        auto add = [&](int j){
            rep(i,g) now[i] += c[i][j];
            rep(i,g) if(now[i]>k) return false;
            return true;
        };

        bool ok = true;
        rep(j,w){
            if(!add(j)){
                num++;
                now = vector<int>(g);
                if(!add(j)) {
                    ok = false;
                    break;
                }
            }
        }
        if(ok) ans = min(ans,num);
        // if(ok)cout << ans << " "<< num<< endl;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3640
#include <stdio.h>
int main(){
    int a,b,c,x;
    
    scanf("%d %d %d",&a,&b,&c);
    
    if (a > b){
        x = a;
        a = b;
        b = x;
    }
    if (b > c){
        x = b;
        b = c;
        c = x;
    }
    if (a > b){
        x = a;
        a = b;
        b = x;
    }
    printf("%d %d %d\n",a,b,c);
    
    return 0;
}


Measured memory_bytes: 2100
using System;


namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            for (int i=1;i<10;i++)
            {
                for(int j=1;j<10;j++)
                {
                    Console.WriteLine(i+"x"+j+"="+i*j);
                }
            }
            
        }
    }
}

Measured memory_bytes: 5572
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


h,w = list(map(int, input().split()))
c = [None]*h
for i in range(h):
    c[i] = input()
# def sub(i):
#     c0 = c[i]
#     c1 = c[i+1]
#     dp = [[None]*(h+1) for _ in range(h+1)]
#     for i in range(h+1):
#         dp[i][0] = 0
#         dp[0][i] = 0
#     val = [None]*(2*h+1) # c0がc1よりi-h高いときの衝突数の累積和
#     for i in range(h):
#         # c1がh, c0がi
#         l = []
#         v = 0
#         for j in range(i):
#             if c1[h-i+j]==c0[j]:
#                 v += 1
#             l.append(v)
#         val[i] = l
#     for i in range(h, -1, -1):
#         # c0がh, c1がi
#         l = []
#         v = 0
#         for j in range(i):
#             if c0[h-i+j]==c1[j]:
#                 v += 1
#             l.append(v)
#         val[h+(h-i)] = l
        
#     for i in range(1, h+1):
#         for j in range(1, h+1):
#             dp[i][j] = min(dp[i+1][j]+val[(i+1)-j+h][i], dp[i][j+1]+val[i-(j+1)+h][i-1])
#     return dp[h][h]
ans = 0
for i in range(w-1):
    c0 = [c[j][i] for j in range(h)]
    c1 = [c[j][i+1] for j in range(h)]
    dp = [[None]*(h+1) for _ in range(h+1)]
    for i in range(h+1):
        dp[i][0] = 0
        dp[0][i] = 0
    val = [None]*(2*h+1) # c0がc1よりi-h高いときの衝突数の累積和
    for i in range(h):
        # c1がh, c0がi
        l = []
        v = 0
        for j in range(i):
            if c1[h-i+j]==c0[j]:
                v += 1
            l.append(v)
        val[i] = l
    for i in range(h, -1, -1):
        # c0がh, c1がi
        l = []
        v = 0
        for j in range(i):
            if c0[h-i+j]==c1[j]:
                v += 1
            l.append(v)
        val[h+(h-i)] = l
        
    for i in range(1, h+1):
        for j in range(1, h+1):
            cost = val[(i)-j+h][min(i,j)-1]
            dp[i][j] = min(dp[i-1][j]+cost, dp[i][j-1]+cost)
    ans += dp[h][h]
#     return dp[h][h]

#     ans += sub(i)
print(ans)

Measured memory_bytes: 232800
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
const int MOD=1e9+7;
 
int main() {
    int a,b;
    cin >> a >> b;
    cout << 6-a-b << endl;
}

Measured memory_bytes: 256
var input = require('fs').readFileSync('/dev/stdin', 'utf8');
var arr=input.trim().split("\n");
var n=arr.shift()-0;
var yx=[];
var zero=[];
for(var i=0;i<n+1;i++)zero.push(0);
yx.push(zero);
for(var i=0;i<n;i++)yx.push(("0 "+arr.shift()).split(" ").map(Number));
n=n+1;
var sum=[];
for(var i=0;i<n;i++){
   sum[i]=[];
   sum[i][0]=yx[i][0];
}
for(var i=0;i<n;i++){
   for(var j=1;j<n;j++){
      sum[i][j]=sum[i][j-1]+yx[i][j];
   }
}
for(var i=1;i<n;i++){
   for(var j=0;j<n;j++){
      sum[i][j]=sum[i-1][j]+sum[i][j];
   }
}
var max=-Infinity;
for(var i=0;i<n;i++){
   for(var j=0;j<n;j++){
      for(var y=i+1;y<n;y++){
         for(var x=j+1;x<n;x++){
            max=Math.max(max,sum[y][x]-sum[i][x]-sum[y][j]+sum[i][j]);
         }
      }
   }
}
console.log(max);

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

using namespace std;

#define int long long

const int dx[8] = { 1, 1, 1, 0, -1, -1, -1, 0 }, dy[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
int W, H;

void DFS(int x, int y, int fld[50][50])
{
	if (fld[y][x] == 0) return;
	fld[y][x] = 0;
	for (int i = 0; i < 8; i++)
	{
		int nx = x + dx[i], ny = y + dy[i];
		if (nx < 0 || W <= nx || ny < 0 || H <= ny) continue;
		DFS(nx, ny, fld);
	}
}

signed main()
{
	while (cin >> W >> H, W || H)
	{
		int fld[50][50];
		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				cin >> fld[i][j];
			}
		}

		int cnt = 0;
		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
			{
				if (fld[i][j] == 1) cnt++;
				DFS(j, i, fld);
			}
		}
		printf("%lld\n", cnt);
	}
}

Measured memory_bytes: 1276
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

int main() {
    int i=0, j, n;
    int pt =0, ph =0;
    string t,h;

    cin >> n;
    
    for(i =0; i < n; i++) {
        cin >> t >> h;
        transform(t.begin(), t.end(), t.begin(), ::toupper);
        transform(h.begin(), h.end(), h.begin(), ::toupper);
        if( t < h) ph +=3;
        if( t > h) pt +=3;
        if( t == h) {
            ph++; pt++;
        }
    }
    cout << pt << " " << ph << endl;
}




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

using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;

    if(n % 2 != 0) {
        n += 1;
    }
    if((n / k) >= 2) {
        cout << "YES";
    }else{
        cout << "NO";
    }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(nullptr); cout.tie(0)
#define endl "\n"
#define int long long
typedef vector<int> vi;
#define all(x) x.begin(),x.end()
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define FORD(i,a,b) for(int i=(a);i>=(b);i--)
#define pii              pair <int,int>
#define DEBUG(x) cerr << '>' << #x << ':' << x << endl;
typedef long long ll;
//#pragma comment(linker, "/STACK:667772160")
#define in_range(x, y, r, c) ((x >= 0 && x < r && y >= 0 && y < c))

const double eps=1e-9;
const int MOD=1e9+7;
const int N=1e5+30;
const int inf = 1e17+995;

template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
inline int ones(int n) { int res = 0; while(n && ++res) n-=n&(-n); return res; }
inline bool EQ(double a, double b) { return fabs(a-b) < 1e-9; }
void boostIO() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
int mem[N],n ,tall[N];
int dp(int idx){
 if(idx==n-1)
     return 0;
 if(idx>n-1)
     return inf;
    int &ret=mem[idx];
    if(ret!=-1)
   return ret;
    ret=min(abs(tall[idx]-tall[idx+1])+dp(idx+1),abs(tall[idx]-tall[idx+2])+dp(idx+2));

    return ret;
}
int32_t main() {
boostIO();
cin>>n;
    for (int i = 0; i < n; ++i) {
        cin>>tall[i];
    }
    memset(mem,-1, sizeof(mem));
    int ans=dp(0);
    cout<<ans<<endl;
}

Measured memory_bytes: 3328
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define int long long
#define inf 1000000007
#define LINF 100000000000000007LL
#define ll long long
using namespace std;
vector<int> nex[5001];
int dp[5001][5001];
bool ap[5001][5001];
int deg[5001];
bool used[5001];
int siz[5001];
int im[5001],tg[5001];
bool am[5001],ag[5001];
vector<int> a(6000);
void calc(int pos){
	vector<int> ch;
	for(int i=0;i<nex[pos].size();i++){
		int nx = nex[pos][i];
		if( used[nx] ){
			ch.pb(nx);
			siz[pos] += siz[nx];
		}
	}
	siz[pos]++; // pos itself
	for(int i=0;i<=siz[pos];i++){
		tg[i] = LINF;
		im[i] = a[pos];
		am[i] = false;
		ag[i] = false;
	}
	if( a[pos] > 0 )am[0]=true;
	int cur = 0;
	for(int i=0;i<ch.size();i++){
		int ma = siz[ ch[i] ] - 1;
		for(int j=0;j<=ma;j++){
			for(int k=0;k<=cur;k++){
				tg[j+k] = min(tg[j+k],im[k]+dp[ch[i]][j]);
				//cout<<i<<j<<k<<" "<<tg[j+k]<<" "<<dp[ch[i]][j]<<endl;
				if( dp[ch[i]][j] < 0 || ap[ch[i]][j] ){
					tg[j+k+1] = min( tg[j+k+1], im[k]);
					//cout<<j+k+1<<" "<<k<<" "<<im[k]<<endl;
				}
				if( am[k] && ap[ch[i]][j] ){ ag[j+k] = true; ag[j+k+1] = true; }
				if( am[k] && dp[ch[i]][j]<0 ) ag[j+k+1] = true;
			}
		}
		cur += ma+1;
		for(int j=0;j<=cur;j++){
			im[j] = tg[j];
			am[j] = ag[j];
			tg[j] = LINF;
			ag[j] = false;
		}
	}
	for(int i=0;i<siz[pos];i++){
		dp[pos][i] = im[i];
		ap[pos][i] = am[i];
		//cout<<"!!"<<pos<<" "<<i<<" "<<im[i]<<" "<<am[i]<<endl;
	}
}
signed main(){
	int n;
	cin>>n;
	a[0]=0;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=0;i<n-1;i++){
		int x,y;
		cin>>x>>y;
		nex[x].pb(y);
		nex[y].pb(x);
		deg[x]++;
		deg[y]++;
	}
	queue<int> que;
	for(int i=2;i<=n;i++){
		if( deg[i] == 1 ){
			que.push(i);
		}
	}
	while(!que.empty()){
		int cur = que.front(); que.pop();
		used[cur] = true;
		calc(cur);
		for(int i=0;i<nex[cur].size();i++){
			int nx = nex[cur][i];
			deg[nx]--;
			if( deg[nx] == 1 && nx != 1){
				que.push(nx);
			}
		}
	}
	calc(1);
	for(int i=0;i<n;i++){
		if( dp[1][i] < 0 || ap[1][i] ){
			cout<<i<<endl;
			return 0;
		}
	}
	return 0;
}

Measured memory_bytes: 220160
#include <iostream>
#include <limits>
#include <cfenv>
#include <cmath>
#include <algorithm>
#include <array>
#include <bitset>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <tuple>
#include <queue>
#include <vector>
#include <cmath>
#include <random>
#include <math.h>
#include <list>
#include <random>
#include <functional>


#define FOR(i, a, b) for(int (i) = (a); (i) < (b); ++(i))
#define REP(i, n) FOR(i, 0, n)
#define rREP(i, n) for(int (i) = (n) - 1; (i) >= 0; --(i))
#define ALL(TheArray) TheArray.begin(), TheArray.end()

using lli = long long int;
using pii = std::pair<int, int>;

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;
}


// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


constexpr int N = 1000;
constexpr int mod = 1e9 + 7;
std::array<std::array<lli, N + 1>, N + 1> A;
std::array<lli, N+1> F, invF;

struct faster{
    lli Power[N+1], invP[N+1];
    constexpr faster(): Power(), invP(){
        Power[0] = 1;
        for(int i = 1; i <= N; ++i) Power[i] = (Power[i-1] * i) % mod;
        invP[N] = inverse(Power[N]);
        for(int i = N; i > 0; --i) invP[i-1] = (invP[i] * i) % mod;
    }
    constexpr void swap(lli &a, lli &b) const {
        a ^= b; b ^= a; a ^= b;
    }
    constexpr lli inverse(lli a) const noexcept{
        lli b = mod, u = 1, v = 0;
        while (b != 0) { 
            lli t = a / b; a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        u %= mod; if (u < 0) u += mod;
        return u;
    }
};

// 累乗の余りを求める関数
inline lli power(lli a, int n, lli mod_number___ = mod){
    lli res = 1, waiting = a;
    while(n){ if(n & 1){ 
        (res *= waiting) %= mod_number___;}
        (waiting *= waiting) %= mod_number___; 
        n >>= 1;
    }
    return res;
}

/* n人でp人グループを k 個作る分け方は
    nCpk * pkCp * (k-1)pCp * ... * pCp / k!
    = {n!/(n-pk)!pk!} * {pk!/(k-1)p!p!} * {(p-1)k!/(k-2)p!p!} * ... * pCp / k!
    = {n!/(n-pk)!pk!} * pk! / (p!)^k / k!
    = n! / { (n - pk)! * (p!)^k * k! }
*/

constexpr faster Init;

int main(void){
    int n, a, b, c, d; scanf("%d%d%d%d%d", &n, &a, &b, &c, &d);

    int bMa = b - a;
    A[0][0] = 1;
    for(int i = 0; i <= bMa; ++i){
        int p = a + i;
        for(int j = 0; j <= n; ++j){
            (A[i+1][j] += A[i][j]) %= mod;
            lli C = power(Init.invP[p], c) * Init.invP[j] % mod;
            int ptr = j + c * p; 
            for(int k = c; k <= d and ptr <= n; ++k, ptr += p){
                lli c = (Init.Power[ptr] * Init.invP[k] % mod) * C % mod;
                (A[i + 1][ptr] += c * A[i][j]) %= mod;
                (C *= Init.invP[p]) %= mod;
            }
        }
    }
    printf("%lld\n", A[bMa+1][n]);
    return 0;
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOR(i, m, n) for (int i = m; i < n; i++)
#define ALL(v) v.begin(), v.end()
using namespace std;
typedef long long ll;

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  vector<int> x(5);
  REP(i,5) cin >> x[i];
  REP(i,5){
    if(x[i]==0) cout << i+1 << endl;
  }
  

  return 0;
}


Measured memory_bytes: 3600
def main():
  #n = int(input())
  #s = input()
  #s = input().split()
  a,b = list(map(int,input().split()))
  c,d = list(map(int,input().split()))
  #a = [input() for i in range(n)]
  #a = [int(input()) for i in range(n)]
  #a = [input().split() for i in range(n)]
  #a = [list(map(int,input().split())) for i in range(n)]
  ans = 0
  count = 0
  lis = []
  
  print(a*b-(c*b+d*a-c*d))

if __name__ == '__main__':
  main()

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

typedef long long ll;

int main(){
	int K;
	cin >> K;
		
	int ans = 0;	
	for(int i=1; i<=K; i++){
	  for(int j=1; j<=i; j++){
	  	for(int k=1; k<=j; k++){
	  		int g = __gcd(i,__gcd(j,k));
	  		if(i==j && j==k){ ans += g; }
	  		else if(i==j || j==k){ ans += g*3; }
	  		else { ans += g*6; }
	  	}
	  }
	}

	cout << ans << endl;
}


Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
//#define MOD 998244353
const double EPS = 1e-9;
#define INF (1LL<<60)
#define D double
#define fs first
#define sc second
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define RFOR(i,a,b) for(int i = (b-1);i>=(a);--i)
#define REP(i,n)  FOR(i,0,(n))
#define RREP(i,n) RFOR(i,0,(n))
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define range(i,a,b) ((a)<=(i) && (i)<(b))
#define debug(x)  cout << #x << " = " << (x) << endl;
#define SP << " " << 
typedef pair<int,int> P;
typedef vector<int> vec;
typedef vector<vector<int>> mat;

//自作関数 a^n mod MODを求める
int m_pow(int a, int n){
  if(n == 0) return 1;
  if(n % 2 == 0){
    int t = m_pow(a, n / 2);
    return t * t % MOD;
  }
  return a * m_pow(a, n - 1) % MOD;
}

signed main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.precision(20);

  int n;
  cin >> n;

  cout << ceil((double)n / 2) << endl;

  return 0;
}

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


int N, X;
int L[100];
int D[101];

int main() {
    D[0] = 0;
    cin >> N >> X;
    int cnt = 0;
    for ( int i = 0; i < N; i++ ) cin >> L[i];
    for ( int i = 1; i < N+1; i++ ) D[i] = D[i-1] + L[i-1];
    for ( int i = 0; i < N+1; i++ ) {
        if ( D[i] <= X ) cnt += 1;
    }
    cout << cnt << endl;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b;
	cin>>a>>b;
	if(a>b)
	{
		for(int i=1;i;i++)
		{
			if(a-b==1||a-b==0)
			{
			cout<<a;
			return 0;
			}
		a--;
		b++;
		
		}
	}
	else
	{
		
		for(int i=1;i;i++)
		{
			if(b-a==1||b-a==0)
			{
			cout<<b;
			return 0;
			}
		a++;
		b--;
		
		}
	}

}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <bitset>
#include <cmath>
#include <functional>
#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))
#define vvi vector<vector<int> >
#define vvl vector<vector<ll> >
#define vll vector<ll>
#define rep(c, a, b) for(ll c=a;c<b;c++)
#define re(c, b) for(ll c=0;c<b;c++)
typedef long long int ll;
typedef long double ld;
using namespace std;

struct Merge{
  set<vll> lr;
  ll INF = 1000000000000000009;
  vll remove(ll a, ll b){
    if(a>b) swap(a, b);
    auto itr = lr.lower_bound(vll{b+1, 0});
    if(itr==lr.begin()) return vll{a, b};
    itr--;
    ll lef = a, ri = b;
    while((*itr)[1]>=a){
      ll now_x = (*itr)[0], now_y = (*itr)[1];
      lef = min(lef, now_x), ri = max(ri, now_y);
      if(itr==lr.begin()){
        lr.erase(itr);
        break;
      }
      itr--;
      lr.erase(vll{now_x, now_y});
    }
    return vll{lef, ri};
  }
  void merge(ll a, ll b){lr.insert(remove(a, b));}
  vll get(ll a){
    auto itr = lr.lower_bound(vll{a+1, 0});
    if(itr==lr.begin()) return vll{INF, INF};
    itr--;
    if((*itr)[1]<a) return vll{INF, INF};
    return *itr;
  }
  bool same(ll a, ll b){
    if(get(a)[0]==-1) return false;
    return get(a)[0]==get(b)[0];
  }
};
int main(int argc, char const *argv[]) {
  ll x, y, z, n, c;std::cin >> n >> c;
  vector<Merge> mg(c+1);
  re(i, n){
    std::cin >> x >> y >> z;
    mg[z].merge(x, y);
  }
  multimap<ld, ll> mp;
  re(i, c+1){
    for(auto itr = mg[i].lr.begin();itr!=mg[i].lr.end();itr++){
      mp.emplace((ld)(*itr)[0] - 0.5, 1);
      mp.emplace((*itr)[1], -1);
    }
  }
  ll now = 0;
  ll ans = 0;
  for(auto itr = mp.begin();itr!=mp.end();itr++){
    if((*itr).second==1) now++;
    else now--;
    ans = max(ans, now);
    //std::cout << (*itr).first << " " << (*itr).second << '\n';
  }
  std::cout << ans << '\n';
  return 0;
}


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

P ll_to_p(ll m){
  ll r = m%10;
  ll l;
  ll k = log10(m);
  l=m/pow(10,k);
  P p = P(l,r);
  //cout << k << "P" << l << "," << r << endl;
  return p;
}


int main(){
  ll n;
  cin >> n;
  map <P,ll> m;
  vector <P> p(n);
  rep(i,n){
    p[i]=ll_to_p(i+1);
    m[p[i]]+=1;
  }
  ll ans =0;
  rep(i,n){
    P q = P(p[i].second,p[i].first);
    ans+=m[q];
  }
  cout << ans << endl;
}



Measured memory_bytes: 1792
s = input().split();
import sys;

n = int(s[0]);
k = int(s[1]);
count = [];
cnt = 0;
for i in range(n):
    count.append(False);

for i in range (k):
    d = int(input());
    num = list(map(int,input().split()));
    for i in range(d):
        count[num[i] - 1] = True;

for i in range(n):
    if(count[i] == False):
        cnt += 1;

print(cnt);





Measured memory_bytes: 9084
n = $stdin.gets.to_i
ary = []
result = 0
a = 0
b = 0
docchimo = 0
lk=false
n.times do |i|
  s = $stdin.gets
  ary[i] = s
  if s[0] == 'B'
    b += 1
  end
  if s[-2] == 'A'
    a += 1
  end
  if s[0] == 'B' && s[-2] == 'A'
    docchimo += 1
  end

  if s[0] != 'B' && s[-2] == 'A'
    lk=true
  end

  result += ary[i].scan("AB").size
end


if docchimo > 0 && a==b && docchimo == a
  result -=1
end
puts result + [a,b].min

Measured memory_bytes: 2940
using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;


public class D
{
	public static void Main()
	{
		string[] args = Console.ReadLine().Split(' ');
		long A = Int64.Parse(args[0]);
		long B = Int64.Parse(args[1]);

		Console.WriteLine(fZero(A-1) ^ fZero(B));
	}


	private static long fZero(long x)
	{
		switch((x + 4) % 4)
		{
			case 0:
				return x;

			case 1:
				return 1;

			case 2:
				return 1^x;

			case 3:
				return 0;

			default:
				throw new Exception();
		}
	} 
}





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

int main(){
		int h,w;
		
		while(1){
				cin>>h>>w;

				if(h==0 && w==0) break;

				for(int i=0 ; i<h ; i++){
						for(int j=0 ; j<w ; j++){
								if(i==0 || i==h-1){
								cout<<'#';
								}else{
										if(j==0 || j==w-1){
												cout<<'#';
										}else{
												cout<<'.';
										}
								}
						}
						cout<<endl;
				}
		cout<<endl;}

		return 0;
}

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

int cnt[50];
int main() {
	int n, p;
	while (scanf("%d%d", &n, &p), n) {
		int k = p;
		memset(cnt, 0, sizeof(cnt));
		for (int i = 0;; i = (i + 1) % n) {
			if (k == 1 && cnt[i] == p - 1) {
				printf("%d\n", i);
				break;
			}
			if (k) { cnt[i]++; k--; }
			else { k = cnt[i]; cnt[i] = 0; }
		}
	}
}

Measured memory_bytes: 3200
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define ff first
#define ss second
#define file_se_input  freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define pp long long int
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define pb push_back
#define mp make_pair
#define pi 3.141592653589793238
#define eb emplace_back
#define rep(i,a,b) for (int i = a; i <= b; i++)
#define zip(i,a,b) for(int i=a;i<b;i++)
#define ll unsigned long long int
#define test long int t;cin>>t; while(t--)
#define um unordered_map
#define en '\n'
#define us unordered_set
#define mm 1000000007

bool check_prime(long long n)
{
    int flag=0;
    for(long long i=2;i*i<=n;i++)
    {
        if(n%i==0)
        {
            flag=1;
            break;
        }
    }
    if(n==1)
	   return false;
    else if(flag==0 || n==2 ||n==3)
    {
        return true;
    }
    else
    {
        return false;
    }

}

int binaryExponentiation(int x,int n)//function to calculate x raise to power n
{
    int result=1;
    while(n>0)
    {
        if(n % 2 ==1)
            result=result * x;
        x=x*x;
        n=n/2;
    }
    return result;
}

int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(NULL);
   cout.tie(0);
   #ifndef ONLINE_JUDGE
    if(fopen("input.txt","r"))
    {
    freopen ("input.txt" , "r" , stdin);
    freopen ("output.txt" , "w" , stdout);
    }
   #endif
    //_______________________________-code starts-______________________________________________________________________________

int s,w;
cin>>s>>w;
if(w>=s)
{
	cout<<"unsafe"<<en;
}
else
{
	cout<<"safe"<<en;
}

  return 0;
}


Measured memory_bytes: 3612
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
#define int ll
#define double long double
#define YES {cout<<"YES"<<'\n';}
#define NO {cout<<"NO"<<'\n';}
#define Yes {cout<<"Yes"<<'\n';}
#define No {cout<<"No"<<'\n';}
#define yes {cout<<"yes"<<'\n';}
#define no {cout<<"no"<<'\n';}
void YN(bool flg){cout<<(flg?"YES":"NO")<<'\n';}
void Yn(bool flg){cout<<(flg?"Yes":"No")<<'\n';}
void yn(bool flg){cout<<(flg?"yes":"no")<<'\n';}
#define SORT(a) sort(a.begin(),a.end())
#define REVERSE(a) reverse(a.begin(),a.end())
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define out(n) {cout << n << '\n';}
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<bool> VB;
typedef vector<VI> VVI;
const int MOD = 1000000007;
const long long INF = 10e10;
const double PI = acos(-1.0);
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; }
template<class T>auto MAX(const T& a) { return *max_element(a.begin(),a.end()); }
template<class T>auto MIN(const T& a) { return *min_element(a.begin(),a.end()); }
int ABS(int a) {if(a<0) a = -a; return a;}
template<class T, class U>U SUM(const T& a, const U& v) { return accumulate(a.begin(),a.end(), v); }
template<class T, class U>U COUNT(const T& a, const U& v) { return count(a.begin(),a.end(), v); }
template<class T, class U>int LOWER(const T& a, const U& v) { return lower_bound(a.begin(),a.end(), v) - a.begin(); }
template<class T, class U>int UPPER(const T& a, const U& v) { return upper_bound(a.begin(),a.end(), v) - a.begin(); }
int GCD(int a, int b) { return b ? GCD(b, a%b) : a; }
int LCM(int a, int b) { int g = GCD(a, b); return a / g * b; }
int POW(int a, int n) { int r = 1; while (n > 0) { if (n & 1)r *= a; a *= a; n /= 2; }return r; }
int isPrime(int n){if(n<2){return 0;}for(int i=2; i*i<=n; i++){if(n%i==0){return 0;}}return 1;}
/*素因数分解*/map< int, int >prime_factor(int n){map< int, int > ret;for(int i = 2; i * i <= n; i++) {while(n % i == 0) {ret[i]++;n /= i;}}if(n != 1) ret[n] = 1;return ret;}
/*約数列挙*/vector<int> divisor(int n){vector<int> v; for(int i=1; i*i<=n; i++){if(n%i==0){v.push_back(i);if(i!=n/i){v.push_back(n/i);}}}sort(v.begin(),v.end()); return v;}
//----------------ライブラリとか----------------

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    cout<<fixed<<setprecision(15);

    int n; cin >> n;
    for(int i=n; i<=999; i++){
        if(i%111==0){out(i); return 0;}
    }

    return 0;
}

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

int main() {

  int A, B, number;
  cin >> A >> B;
  number = 0;

  for(int i = A; i <= B; i++){

  if(i % 10 == i / 10000 % 10 && i / 1000 % 10 == i / 10 % 10)
    number += 1;

  }   
  

cout << number;

}

Measured memory_bytes: 256
using System;
using System.Diagnostics;
using System.IO;
using System.Text;
using System.Linq;
using System.Collections.Generic;

class Program
{
    static void Main(string[] args) {
#if DEBUG
        //MyDebugger.MakeTestCase("../TextFile2.txt"); return;
        MyDebugger.Test(process, "../TextFile1.txt");
#else
        object ret = process(new StreamReader(Console.OpenStandardInput()));
        Console.WriteLine(ret);
#endif
    }

    static object process(TextReader input) {
        var n = long.Parse(input.ReadLine());

        if (n % 2 == 1) return 0;

        long i = 5*2;
        long c = 0;

        while (i<=n) {
            c += n / i;
            //Debug.WriteLine(i + "/" + (n/i));
            i *= 5;
        }
        return c;

        //return func(n);
    }
    
    static long func(long n) {
        Debug.WriteLine(n);

        if (n < 2) return 1;
        return n * func(n - 2);
    }
}


Measured memory_bytes: 13140
#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;

int N;
int BIT[6000000];

void add(int a, int w){
	
	// a?????????????´????w????¶???? O(log N)
	
	for(int x = a; x <= N; x += x & -x){
		BIT[x] += w;
	}
}

int sum(int a){
	
	// 1??????a?????§???????´????????¨?????????? O(log N)
	
	int ret = 0;
	for(int x = a; x > 0; x -= x & -x){
		ret += BIT[x];
	}
	return ret;
}

int main(){
	
	N = 2000000;
	int num_max = 1000000;
	
	bool a[1000000];
	
	for(int i = 0; i < num_max; i++){
		a[i] = true;
	}
	
	a[0] = false;
	a[1] = false;
	
	for(int i = 2; i < num_max; i++){
		if(a[i]){
			for(int j = i * 2; j < num_max; j += i){
				a[j] = false;
			}
		}
	}
	
	for(int i = 0; i < 6000000; i++){
		BIT[i] = 0;
	}
	
	for(int i = 0; i < num_max; i++){
		if(a[i]){
			add(i, 1);
		}
	}
	
	while(true){
		
		int n;
		
		cin >> n;
		
		if(n == 0){
			break;
		}
		
		int ans = 0;
		
		for(int i = 0; i < n; i++){
			int p, m, hit_num;
			cin >> p >> m;
			if(p - m <= 2){
				hit_num = sum(p + m);
			}else{
				hit_num = sum(p + m) - sum(p - m - 1);
			}
			
			//cout << hit_num << endl;
			
			ans = ans + hit_num - 1;
			
		}
		
		if(ans < 0){
			ans = 0;
		}
		
		cout << ans << endl;
		
	}
	
	return 0;
}

Measured memory_bytes: 27396
n=int(input())
a=list(map(int, input().split()))
b=list(map(int, input().split()))
count=0


if sum(a)>sum(b):
    print('No')
    exit()

else:
    for i in range(n):
        if a[i]<b[i]:
            count+=-(-(b[i]-a[i])//2)
    
    v=sum(b)-sum(a)
    if v>=count:
        print('Yes')
    else:
        print('No')
            
            

Measured memory_bytes: 4600
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>

#define rep(i,j) REP((i), 0, (j))
#define REP(i,j,k) for(int i=(j);(i)<(k);++i)
#define between(a,x,b) ((a)<=(x)&&(x)<=(b))
using namespace std;
typedef pair<int, pair<int, int> > tpair;


bool cmp(const tpair &a, const tpair &b){
  if(a.second.first != b.second.first) return a.second.first > b.second.first;
  else if(a.second.second != b.second.second) return a.second.second < b.second.second;
  else return a.first < b.first;
}


int main(){
  int T, P, R;
  while(scanf("%d%d%d", &T, &P, &R) && (T||P||R)){
    //    vector<pair<int, pair<int, int> > > t(T); // team ac p
    vector<tpair> t(T);
    int fail[64][64] = {};
    int tid, pid, time;
    char message[64];
    rep(i, T) t[i] = make_pair(i+1, make_pair(0, 0));
    rep(i, R){
      scanf("%d%d%d", &tid, &pid, &time);
tid--;
      scanf("%s", message);
      if(message[0] == 'C'){
	  t[tid].second.first += 1;
	  t[tid].second.second += fail[tid][pid] * 1200 + time;
	  fail[tid][pid] = -1;
      }else  fail[tid][pid]++;
    }
    sort(t.begin(), t.end(), cmp);
    rep(i, T) printf("%d %d %d\n", t[i].first, t[i].second.first, t[i].second.second);
  }
  return 0;
}

Measured memory_bytes: 1220
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 131072;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
int n, s, t, cnt, a[MAXN], ans[MAXN], lft[18], bit[18];
void work(int depth, int pos) {
	if (lft[depth]) {
		lft[depth]--;
		if ((n - depth) % 2) a[pos] = depth - 1;
		else a[pos] = depth + 1;
	} else a[pos] = depth;
	if (depth == 1) return;
	work(depth - 1, pos - (1 << (depth - 2)));
	work(depth - 1, pos + (1 << (depth - 2)));
}
int main() {
	read(n), read(s), read(t);
	for (int val = s ^ t; val; cnt++)
		val ^= val & -val;
	if (cnt % 2 == 0) {
		puts("NO");
		return 0;
	}
	puts("YES");
	for (int i = 2; i <= cnt; i += 2) {
		lft[n - i + 1] = 1;
		lft[n - i] = 2;
	}
	work(n, 1 << (n - 1));
	int l = 1, r = n;
	for (int i = 0; i < n; i++) {
		int tmp = 1 << i;
		if ((s ^ t) & tmp) bit[r--] = tmp;
		else bit[l++] = tmp;
	}
	ans[0] = s;
	for (int i = 1; i < (1 << n); i++)
		ans[i] = ans[i - 1] ^ bit[a[i]];
	for (int i = 0; i < (1 << n); i++)
		printf("%d ", ans[i]);
	return 0;
}

Measured memory_bytes: 2048
//https://atcoder.jp/contests/abc138/tasks/abc138_b
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int64_t i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
int main() {
    ll N; cin>>N;
    vector<double> an(N);
    for(auto&& a:an){
        cin>>a;
    }
    double sum0=0.0;
    for(const auto& a:an){
        sum0 += 1.0/a;
    }
    double ans = 1.0/sum0;
    cout<<fixed<<std::setprecision(10)<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
parseint(x) = parse(Int, x)
int() = readline() |> parseint
ints() = map(parseint, readline() |> split)

mod = 1_000_000_007

function set(dp)
    dp[1:2] += [1, 2]
    for i = 3:length(dp)
        dp[i] += dp[i-1] + dp[i-2]
        dp[i] %= mod
    end
    dp
end


function main()
    n, m = ints()
    a = append!([-1], push!([int() for _ = 1:m], n+1))
    d = [a[i+1] - a[i] - 2 for i = 1:m+1]
    dp = set(zeros(Int, n + 2))
    ans = 1
    for k in d
        if k < 0
            ans = 0
        elseif k == 0
            ans *= 1
        else
            ans *= dp[k]
            ans %= mod
        end
    end
    println(ans)
end

main()


Measured memory_bytes: 151676
n=int(input())
a=list(map(int,input().split()))
a.append(0)
a.insert(0,0)
total=0
for i in range(len(a)-1):
    total+=abs(a[i+1]-a[i])
for i in range(n):
    temp=total
    temp-=(abs(a[i+1]-a[i])+abs(a[i+2]-a[i+1]))
    temp+=abs(a[i+2]-a[i])
    print(temp)

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

int main()
{
	int n;
	cin >> n;
	vector<int> x(n),y(n);
	for (int i=0;i<n;++i)
	{
		cin >> x[i] >> y[i];
	}

	vector<pair<int,int>> xpy(n),xmy(n);
	for (int i=0;i<n;++i)
	{
		xpy[i]=make_pair(x[i]+y[i],i);
		xmy[i]=make_pair(x[i]-y[i],i);
	}

	sort(xpy.begin(),xpy.end());
	sort(xmy.begin(),xmy.end());

	auto itp1=xpy.begin();
	auto itp2=xpy.end();
	--itp2;
	auto itm1=xmy.begin();
	auto itm2=xmy.end();
	--itm2;

	for (;;)
	{
		int diffp=0;
		while (itp1!=itp2)
		{
			if (itp2->first-itp1->first != (abs(x[itp1->second]-x[itp2->second])+abs(y[itp1->second]-y[itp2->second])) )
			{
				if ( ((itp1+1)->first - itp1->first) < ((itp2-1)->first - itp2->first) )
				{
					++itp1;
				}
				else
				{
					--itp2;
				}
			}
			else
			{
				diffp=itp2->first-itp1->first;
				break;
			}
		}


		int diffm=0;
		while (itm1!=itm2)
		{
			if (itm2->first-itm1->first != (abs(x[itm1->second]-x[itm2->second])+abs(y[itm1->second]-y[itm2->second])) )
			{
				if ( ((itm1+1)->first - itm1->first) < ((itm2-1)->first - itm2->first) )
				{
					++itm1;
				}
				else
				{
					--itm2;
				}
			}
			else
			{
				diffm=itm2->first-itm1->first;
				break;
			}
		}

		cout << max(diffp,diffm) << endl;
		return 0;
	}
}






Measured memory_bytes: 8004
//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_B&lang=ja
#define _DEBUG
#include "bits/stdc++.h"
#define CHOOSE(a) CHOOSE2 a
#define CHOOSE2(a0,a1,a2,a3,a4,x,...) x
#define debug_1(x1) cout<<#x1<<": "<<x1<<endl
#define debug_2(x1,x2) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<endl
#define debug_3(x1,x2,x3) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<endl
#define debug_4(x1,x2,x3,x4) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<endl
#define debug_5(x1,x2,x3,x4,x5) cout<<#x1<<": "<<x1<<", "#x2<<": "<<x2<<", "#x3<<": "<<x3<<", "#x4<<": "<<x4<<", "#x5<<": "<<x5<<endl
#ifdef _DEBUG
#define debug(...) CHOOSE((__VA_ARGS__,debug_5,debug_4,debug_3,debug_2,debug_1,~))(__VA_ARGS__)
#else
#define debug(...)
#endif
#define rep(index,num) for(int index=0;index<(int)num;index++)
#define rep1(index,num) for(int index=1;index<=(int)num;index++)
#define brep(index,num) for(int index=(int)num-1;index>=0;index--)
#define brep1(index,num) for(int index=(int)num;index>0;index--)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-7
#define mp(a1,a2) make_pair(a1,a2)
#define ALL(a) (a).begin(),(a).end()
#define rALL(a) (a).rbegin(),(a).rend()
typedef long long ll;
typedef long double ld;
using namespace std;
typedef pair<ll,ll> pll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<ll> vll;
typedef vector<pint> vpint;
typedef vector<pll> vpll;
ll INFl=(ll)1e+18+1;
int INF=1e+9+1;
template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;
  //内部は1-indexedだけどmainでは0-indxedで動く
  int sz;//size 葉がsz個、葉以外がsz-1個
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);//子を用いて親を更新
    }
  }

  void add(int k, const Monoid &x) {
	k += sz;
	seg[k] += x;
	while(k >>= 1) {
	  seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
	}
  }

  Monoid query(int a, int b) {//半開区間
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};
int main(){
	int N,Q;
	scan(N>>Q);
	SegmentTree<int> seg(N,[](int a, int b){return a+b;},0);
	rep(i,Q){
		int T,X,Y;
		scan(T>>X>>Y);
        X--;
		if(T==0){
			seg.add(X,Y);
		}
		else{
            Y--;
			prin(seg.query(X,Y+1));
		}
	}
	return 0;
}



Measured memory_bytes: 3880