akhauriyash/Code-Regression huggingface dataset:
# http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_1_A&lang=ja

class UnionFind():                                              # クラス　＝　インスタンスを返す関数（型とは違う? 、dictを例に説明？）
    def __init__(self, n):                                      # コンストラクタ　＝　インスタンスをどのように生成するか、どのような構造を持たせるかを定義
                                                                # 具体的にはオブジェクトにインスタンス変数を割り当てる事で、複雑な構造を持たせる役割を持つ
                                                                # ここでは 0 ~ n-1 までの整数にインスタンス変数parentsを割り当てる事で、
                                                                # 単なる整数から親子関係という内部構造を持つインスタンスを生成した。

        self.n = n                                              # インスタンスselfのインスタンス変数 n の値を定義
        self.parents = [-1] * n                                 # インスタンスselfのインスタンス変数 parents の値を定義


# 以下でインスタンスに作用する関数を定義。全ての関数はインスタンスを入力値としてインスタンス変数に基づいて処理される。

    def find(self, x):                                          # 根を見つける関数を定義（同時にxを直接根にくっつける操作も行う）
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])        # 右辺で再帰的に根を探索。根に到達すると一つ目のif判定に引っかかるので、
                                                                # 最終的にself.parents[根]が返ってくる。
                                                                # これを左辺に代入することで、根が親になるように変更する。（根までの距離が長いとO(N)になってしまうので）
            return self.parents[x]

    def union(self, x, y):                                      # 二つの木をくっつける（子を多く持つ方を根とした親子関係）。これは破壊的操作を行う。
        x = self.find(x)                                        # xをxの根に置き換える
        y = self.find(y)                                        # yをyの根に置き換える

        if x == y:                                              # 根が同じなら置き換える必要なし
            return

        if self.parents[x] > self.parents[y]:                   # 子がたくさんある方を x とする
            x, y = y, x

        self.parents[x] += self.parents[y]                      # xの子の数を更新
        self.parents[y] = x                                     # yの親を更新

    def same(self, x, y):                                       # xとyが同じ根の子かを判定
        return self.find(x) == self.find(y)

n, q = map(int, input().split())

A = UnionFind(n)

for c,x,y in [list(map(int,input().split())) for _ in range(q)]:
    if not c:
        A.union(x,y)
    else:
        print(int(A.same(x,y)))


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

int main() {
  int N,ans=0;
  cin>>N;
  vector<int> a(N+1);
  for (int i=1;i<=N;i++) {
    cin>>a[i];
    if (i%2==1 && a[i]%2==1) ans++;
  }
  cout<<ans<<endl;
  return 0;
}


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

const int MOD=1e9+7;
ll mod(ll x){
    ll res=x%MOD;
    return res+(res<0?MOD:0);
}
ll inv(ll x){
    ll b=MOD,u=1,v=0;
    while(b){
        ll t=x/b;
        x-=t*b;swap(x,b);
        u-=t*v;swap(u,v);
    }
    return mod(u);
}
vector<ll> prods(int x){
    vector<ll> res(x+1);
    res[0]=1;
    for(int i=1; i<=x; i++)res[i]=mod(i*res[i-1]);
    return res;
}
vector<ll> pows(ll a,int x){
    vector<ll> res(x+1);
    res[0]=1;
    a=mod(a);
    for(ll i=1; i<=x; i++)res[i]=mod(a*res[i-1]);
    return res;
}
ll power(ll a, ll n){
    ll res=1;
    a=mod(a);
    for(;n>0;n>>=1){
        if(n&1)res=mod(res*a);
        a=mod(a*a);
    }
    return res;
}
vector<ll> p;
ll comb(ll a, ll b){
    if(b<0||b>a)return 0;
    return mod(mod(p[a]*inv(p[b]))*inv(p[a-b]));
}



int main(){
    int n,k;
    cin>>n>>k;
    int r=n-k;
    p=prods(4000);
    for(int i=1; i<=k; i++){
        cout<<mod(comb(k-1,i-1)*comb(r+1,i))<<endl;
    }

    return 0;
}

Measured memory_bytes: 256
n,m=map(int,input().split())
j=[0]*n
c=[0]*n
pe=0
ac=0
for i in range(m):
  p,s=input().split()
  p=int(p)-1
  if s[0]=="A" and j[p]==0:
    j[p]=1
    ac+=1
    pe+=c[p]
  elif s[0]=="W":c[p]+=1
print(ac,pe)

Measured memory_bytes: 4724
#include<stdio.h>
int main(void){
  int n,m,sum=0;
  scanf("%d%d",&n,&m);
  int a[m];
  for(int i=0;i<m;i++)
    scanf("%d",&a[i]);
  for(int i=0;i<m;i++)
    sum+=a[i];
  if(n-sum>=0) printf("%d",n-sum);
  else printf("%d",-1);
  return 0;
}

Measured memory_bytes: 1728
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <limits.h>


int main()
{
	int i,j;
	int n;
	int ans;
	char a[3],b[3];

	while(1)
	{
		scanf("%d",&n);
		if(n==0){break;}
		else
		{
			ans=0;
			for(i=0;i<(n/2);i++)
			{
				scanf("%s %s",a,b);
				if((a[0]!=b[0])&&(a[1]==b[1]))
				{
					ans++;
				}
			}
			if(n%2==1){scanf("%s",b);}

		}
		printf("%d\n",ans);
	}
	return 0;
}
	

Measured memory_bytes: 1032
from copy import deepcopy
from sys import exit,setrecursionlimit
import math
from collections import defaultdict,Counter,deque
from fractions import Fraction as frac
import bisect
import sys
import logging
import heapq
logging.basicConfig(level=logging.DEBUG)

input = sys.stdin.readline

setrecursionlimit(1000000)

def main():
    S=input()

    A=[0 for _ in range(len(S)-1)]
    mode="L"
    s=0
    b=0
    e=0
    l=0
    for i in range(len(S)):
        c=S[i]
        if mode=="L" and c==mode:
            mode="R"
            b=i-1
        elif mode=="R" and c==mode:
            mode="L"
            e=i-1

            calc(A,s,b,e)
            
            s=i
        elif c=="\n":
            e=i-1
            calc(A,s,b,e)

    print(*A)

def calc(A, s, b, e):
    l=e-s+1
    if l//2==0:
        A[b]=A[b+1]=l/2
    else:
        A[b]=(b-s)//2+(e-b)//2+1
        A[b+1]=l-A[b]

main()

Measured memory_bytes: 77964
N = int(input())
dp = [[0 for i in range(10)] for j in range(10)]
 
for i in range(1, N + 1):
    i = str(i)
    dp[int(i[0])][int(i[-1])] += 1
 
ans = 0
for i in range(1, 10):
    for j in range(1, 10):
        ans += dp[i][j] * dp[j][i]
print(ans)

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

using namespace std;

bool solve(string s) {
	int n = s.length();
	string tmp = "";
	bool flag[4] = {};
	for (int i = 0; i < n; ) {
		if (s[i] == 'm') {
			if (s.substr(i, 5) != "maerd") return false;
			i += 5;
		} else if (s[i] == 'e') {
			if (s.substr(i, 5) != "esare") return false;
			i += 5;
		} else if (s[i] == 'r') {
			if (s.substr(i, 6) == "resare") i += 6;
			else if (s.substr(i, 7) == "remaerd") i += 7;
			else return false;
		} else {
			return false;
		}
	}
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	string s;
	cin >> s;
	reverse(s.begin(), s.end());
	cout << (solve(s) ? "YES" : "NO") << endl;
	return 0;
}

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

int main(){
  double n,k,p=0,ans=0;
  cin>>n>>k;
  for(int i=1; i<=n; i++){
    for(int j=i; ; ){
      if(j>=k) break;
      p++;
      j *= 2;
    }
    ans += (1/n)*pow(0.5,p);
    p = 0;
  }
  cout<<setprecision(13)<<ans;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = (int)1e9 + 7;

void add(int &x, int y) {
    x = (x + y) % MOD;
}

int main() {
#ifdef HOME
    freopen("in", "r", stdin);
#endif

    int n, m, k;
    while (cin >> n >> m >> k) {
        vector<int> a(k), b(k), c(k);
        for (int i = 0; i < k; i++) {
            cin >> a[i] >> b[i] >> c[i];
            a[i]--; b[i]--;
        }

        n--;
        vector<vector<int> > need(m, vector<int>(n, -1));
        for (int i = 0; i < k; i++) {
            need[a[i]][b[i]] = c[i];
        }

        vector<vector<int> > nxt(1 << n, vector<int>(n, -1));
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if (!((mask >> i) & 1)) {
                    int nmask = mask ^ (1 << i);
                    int j = i + 1;
                    while (j < n) {
                        if ((nmask >> j) & 1) {
                            nmask ^= 1 << j;
                            break;
                        }
                        j++;
                    }
                    nxt[mask][i] = nmask;
                }
            }
        }

        vector<vector<int> > dp(n + 1, vector<int>(1 << n, 0));
        dp[0][0] = 1;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                dp[j + 1].assign(1 << n, 0);
                for (int mask = 0; mask < (1 << n); mask++) {
                    add(dp[j + 1][mask], dp[j][mask]);
                    if (!((mask >> j) & 1)) {
                        add(dp[j + 1][nxt[mask][j]], dp[j][mask]);
                    }
                }
            }
            dp[0] = dp[n];
            for (int mask = 0; mask < (1 << n); mask++) {
                for (int j = 0; j < n; j++) {
                    if (need[i][j] != -1 && ((mask >> j) & 1) != need[i][j]) {
                        dp[0][mask] = 0;
                    }
                }
            }
        }
        int ans = 0;
        for (int mask = 0; mask < (1 << n); mask++) add(ans, dp[0][mask]);
        printf("%d\n", ans);
    }

#ifdef HOME
    cerr << clock() / (double)CLOCKS_PER_SEC << endl;
#endif
    return 0;
}


Measured memory_bytes: 104832
### 17.07.2017
n = []
while (True):
	x = list(map(int,input().split()))
	if x[0] == 0 and x[1] == 0:
		break
	n.append(x)
for i in n:
	if i[0] > i[1]:
		print(i[1], i[0])
	else:
		print(i[0], i[1])

Measured memory_bytes: 8392
#include <bits/stdc++.h>
#define maxn 300005
#define maxa 2000005
#define MOD    100000000  //1000000007 //998244353
#define INF 1000000000000000000
#define ll unsigned long long

using namespace std;

#define pii pair<ll, ll>
#define piii pair<ll, pii>
#define ft first
#define sd second
#define pb push_back
#define rep(i, n) for(ll i = 0; i < n; i++)
#define repr(i, n) for(ll i = n-1; i >= 0; i--)
#define itr(it, x) for(auto it = x.begin(); it != x.end(); it++)
#define mem(a, b) memset(a, (ll)b, sizeof(a))
#define all(v) v.begin(), v.end()
#define edge(v, x, y) v[x].pb(y); v[y].pb(x);
#define popcount __builtin_popcount
#define ANS(s) {cout << s << "\n"; return;}

//~~~~~~fancy print~~~~~~~//
#define printpii(a) cout << a.ft << " " << a.sd << endl;
#define printpiii(a) cout << a.ft << " " << a.sd.ft << " " << a.sd.sd << endl;
#define print(a, n) rep(i, n) cout << a[i] << " "; cout << endl;
#define printv(v) for(auto x: v)cout << x << " "; cout << endl;
#define printm(a, n, m) rep(i, n) { rep(j, m) cout << a[i][j] << " "; cout << endl;}


void fast(){ios_base::sync_with_stdio(false);cin.tie(0);cout << setprecision(12) << fixed;}

void solve(){
    ll a, b, n;
    cin >> a >> b >> n;
    ll x = min(n, b-1);
    cout << (a*x)/b - a*(x/b) << endl;

}

int main(){
    fast();
    ll t = 1; //cin >> t;
    while(t--){
        solve();
    }
}


Measured memory_bytes: 3668
import fractions

A, B, C, D = map(int, input().split())

divc = B//C - (A-1)//C
divd = B//D - (A-1)//D
lcm = C*D // fractions.gcd(C, D)
divgcd = B//lcm - (A-1)//lcm

print((B-A+1) - divc - divd + divgcd)

Measured memory_bytes: 5216
#include<iostream>

using namespace std;

int main() {
  int n;
  cin >> n;
  int ans = 0;
  for(int i = 0; i < n; i++) {
    int a;
    cin >> a;
    while(a % 2 == 0) {
      a /= 2;
      ans++;
    }
  }
  cout << ans << endl;
}


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

using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, x;
  cin >> n >> x;
  vector<int> xs(n);
  for (int i = 0; i < n; i++) cin >> xs[i];
  int ans = abs(x - xs[0]);
  for (int i = 1; i < n; i++) {
    ans = __gcd(ans, abs(x - xs[i]));
  }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;


int N;
vector<double> x,y;
double ans = 0.0;


int main()
{
    cin >> N;
    x.resize(N);
    y.resize(N);
    rep(i,N) cin >> x[i] >> y[i];

    vector<int> v(N);
    rep(i,N) v[i] = i;
    double c = 0;
    do{
        c++;
        double d = 0;
        for (int i = 1; i < N; i++) {
            double dx = x[v[i]] - x[v[i-1]];
            double dy = y[v[i]] - y[v[i-1]];
            d += sqrt(dx*dx + dy*dy);
            
        }
      
        ans += d;
    }while(next_permutation(v.begin(), v.end()));
    
    cout << fixed << setprecision(15) <<  ans/c << endl;
    
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <set>
#include <string>

using namespace std;

int main(int argc, char const *argv[])
{
	int n,m;
	set<string> u;
	string s;

	int k=0; //0:close 1:open

	cin>>n;
	for(int i1=0;i1<n;i1++){
		cin>>s;
		u.insert(s);
	}

	cin>>m;

	for(int i1=0;i1<m;i1++){
		cin>>s;
		if(u.find(s)!=u.end()) {
			if(k==0) {
				cout<<"Opened by "+s<<endl;
				k=1;
			}
			else {
				cout<<"Closed by "+s<<endl;
				k=0;
			}
		}
		else cout<<"Unknown "+s<<endl;

	}

	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vl;
typedef pair<int,int> P;
typedef pair<ll,ll> PL;

#define INF 1<<30
#define LINF 1ll<<60ll
#define MOD 1000000007
#define pb(a) push_back(a)

#define _overload3(_1,_2,_3,_4,name,...) name
#define _rep(i,n) _repi(i,0,n)
#define _repi(i,a,b) for(int i=a, i##_len=(b); i<i##_len; ++i)
#define _repis(i,a,b,s) for(int i=a, i##_len(b); i<i##_len; i+=s)
#define REP(...) _overload3(__VA_ARGS__,_repis,_repi,_rep,)(__VA_ARGS__)

#define REPR(i, n) for(int i = n;i >= 0;--i)
#define REPARR(i, v) for(int i = 0;i < sz(v);++i)

#define all(vec) (vec.begin()),(vec.end())
#define sz(x) ((int)(x).size())
#define bit(n) (1ll<<(n))

template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(a>b){a=b;return true;}return false;}

#define YES(n) cout<<((n)?"YES":"NO")<<endl
#define Yes(n) cout<<((n)?"Yes":"No")<<endl
#define yes(n) cout<<((n)?"yes":"no")<<endl
#define poss(n) cout<<((n)?"possible":"impossible")<<endl
#define Poss(n) cout<<((n)?"Possible":"Impossible")<<endl
#define POSS(n) cout<<((n)?"POSSIBLE":"IMPOSSIBLE")<<endl



int main(){
    int f=0,s=0;
    REP(i,3){
        int a;
        cin>>a;
        if(a==5)f++;
        else if(a==7)s++;
    }
    YES(f==2&&s==1);
    
    
    return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#define N 4

int main(void)
{
    int count=0;
    int max=0;
    char weather[N+1];

    scanf("%s",weather);
    for(int i=0;i<N;i++){
        if(weather[i]=='R'){
            count+=1;
            if(count>max) max=count;
        }
        else count=0;
    }

    printf("%d",max);
    return 0;
}


Measured memory_bytes: 1712
#include<stdio.h>

void longest(int n,int pl,int dl){
  int p,d1,d2;
  if(n!=0){
    scanf("%d %d %d",&p,&d1,&d2);
    if((pl==0)||(dl<d1+d2)){
      longest(n-1,p,d1+d2);
    }
    else{
      longest(n-1,pl,dl);
    }
  }
  else{
    printf("%d %d\n",pl,dl);
  }
}

void doit(){
  int n;

  scanf("%d",&n);
  if(n!=0){
    longest(n,0,0);
    doit();
  }
}

int main(){
  doit();
  return 0;
}

Measured memory_bytes: 1068
#include<stdio.h>

int main(){
  double a,b,c,d,e,f,i,x,y;
  while(scanf("%lf %lf %lf %lf %lf %lf",&a,&b,&c,&d,&e,&f)!=EOF)
    {
      x = (f-e/b*c)/(d-e/b*a);
      y = (f-d/a*c)/(e-d/a*b);
      if(x == 0) x = 0;
      if(y == 0) y = 0;
      printf("%.3f %.3f\n",x,y);
    }
  return 0;
}

Measured memory_bytes: 652
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;

typedef long long ll;
string s, t;

int a[30], b[30], c[100000][30];

int main()
{
    cin >> s >> t;
    memset(c, -1, sizeof c);
    for (int i = 0; i < s.size(); ++i)
        c[i][s[i] - 'a'] = i;

    for (int i = s.size() - 2; i >= 0; --i)
        for (int j = 0; j < 30; ++j)
            if (c[i][j] == -1)
                c[i][j] = c[i + 1][j];

    for (char c : t)
        ++b[c - 'a'];
    for (char c : s)
        ++a[c - 'a'];
    /*
    for (int i = 0; i < s.size(); ++i)
    {
        for (int j = 'a'; j <= 'f'; ++j)
            cout << c[i][j - 'a'] << " ";
        cout << endl;
    }
    */
    bool f = 0;
    for (int i = 0; i <= ('z' - 'a'); ++i)
        if (a[i] == 0 && b[i] != 0)
        {
            f = 1;
            break;
        }
    if (f)
        return (cout << -1 << endl, 0);

    int i = 0, j = 0, cnt = 0;
    while (j < t.size())
    {
        if (i >= s.size() || c[i][t[j] - 'a'] == -1)
            ++cnt, i = 0;
        i = c[i][t[j++] - 'a'] + 1;
    }
    cout << (1ll * cnt * (ll)s.size()) + (ll)i << endl;
}


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



Measured memory_bytes: 2724
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <chrono>

using namespace std;
using namespace chrono;
 
typedef long long ll;
typedef long double ld;

typedef pair<int, int> pi;
typedef pair<ll,ll> pl;
typedef pair<ld,ld> pd;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;

//#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define loop(x,n) for(int x = 0; x < n; ++x)
#define FORd(i,a,b) for (int i = (b)-1; i >= (a); i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
#define trav(a, x) for (auto& a : x)

#define mp make_pair
#define pb push_back
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound

#define sz(x) (int)x.size()
#define beg(x) x.begin()
#define en(x) x.end()
#define all(x) beg(x), en(x)
#define resz resize

const int MOD = 1000000007; // 998244353
const ll INF = 1e18;
const int MX = 100001;

string get_str() {
    string temp;
    cin >> temp;
    return temp;
}
int get_int() {
    int temp;
    cin >> temp;
    return temp;
}

void solve() {

    int n; cin >> n;
    if(n % 1000 == 0) {
        cout << 0 << endl;
    }
    else {
        cout << 1000 - (n % 1000) << endl;
    }

}

int main() {
    
    solve();

}

Measured memory_bytes: 3608
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repi(i, n) for (int i = (n)-1; i >= 0; i--)
#define pp(v) cout << #v << "=" << (v) << endl;
#define div_ceil(a,b) ((a) + ((b) - 1)) / (b)

int f(int n) {
  int ans = -1;
  if (n % 2 == 1) {
    ans = 3 * n + 1;
  } else {
    ans = n / 2;
  }
  // cout << ans << endl;
  return ans;
}

int main() {
  // input
  int s; cin >> s;

  // 数列
  int a[1000001];
  a[1] = s;

  rep(i,1000000) {
    if (i < 2) continue;

    a[i] = f(a[i-1]);
    rep(j,i-1) if (a[i] == a[j]) {
      cout << i << endl;
      exit(0);
    }
  }
}


Measured memory_bytes: 256
#include<stdio.h>
#include<algorithm>
#include<math.h>
using namespace std;
double x[110000];
double y[110000];
pair<double,double>p[110000];
int main(){
    int a;scanf("%d",&a);
    for(int i=0;i<a;i++){
        double X,Y;
        scanf("%lf%lf",&X,&Y);
        x[i]=cos(1)*X-sin(1)*Y;
        y[i]=sin(1)*X+cos(1)*Y;
        p[i]=make_pair(x[i],y[i]);
    }
    std::sort(p,p+a);
    double ret=99999999;
    for(int i=0;i<a;i++){
        for(int j=i-1;j>=0;j--){
            if(p[i].first-p[j].first>ret)break;
            ret=min(ret,sqrt((p[i].first-p[j].first)*(p[i].first-p[j].first)+(p[i].second-p[j].second)*(p[i].second-p[j].second)));
        }
    }
    printf("%.12f\n",ret);
}

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

static const int MOD = 1000000007;
using ll = int64_t;
using u32 = uint32_t;
using namespace std;

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

int main() {
    int n; string s;
    cin >> n >> s;
    ll ans = 0, j = 0, jo = 0, joi = 0, ans2 = 0;
    for (int i = 0; i < n; ++i) {
        if(s[i] == 'J') j++;
        else if(s[i] == 'O') jo += j;
        else joi += jo;
    }
    ans = joi; ans2 = jo;
    vector<ll> J(n);
    J[0] = s[0] == 'J';
    for (int i = 1; i < n; ++i) {
        J[i] = J[i-1]+ (s[i] == 'J');
    }
    ll I = 0, IO = 0;
    for (int i = n-1; i >= 0; --i) {
        if(s[i] == 'I') I++;
        else if(s[i] == 'O') IO += I;
        ans2 = max(ans2, I*J[i]);
    }
    ans2 = max(ans2, IO);


    cout << ans+ans2 << "\n";
    return 0;
}



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

using vi = vector<int>;

int main()
{
    ios_base::sync_with_stdio(0);

    int a, b, c, d, e, f;

    cin >> a >> b >> c >> d >> e >> f;

    int u = 3000;

    vi v(u + 1);

    for(int i = 0; i <= u; i++)
    for(int j = 0; j <= u; j++)
    {
        int k = c * i + d * j;

        if(k <= u) v[k] = k; 
    }

    for(int i = 1; i <= u; i++) if(!v[i])
        v[i] = v[i - 1];

    vector< pair<double, pair<int, int>> > ans;

    for(int i = 0; i <= 30; i++)
    for(int j = 0; j <= 30; j++)
    {
        int k = 100 * a * i + 100 * b * j;

        if(k > f) continue;

        int s = v[min((k / 100) * e, f - k)];

        ans.push_back({k + s ? double(s) / double(k + s) : 0, {k + s, s}});
    }

    sort(begin(ans), end(ans));

    int k = ans.back().second.first;
    int s = ans.back().second.second;

    cout << k << ' ' << s << endl;
    return 0;
}

Measured memory_bytes: 256
n = gets.chomp.to_i
a = gets.chomp.split(" ").map(&:to_i)

for i in 1..n-1
    puts a.join(" ")
    v = a[i]
    j = i - 1
    while j >= 0 && a[j] > v
        a[j+1] = a[j]
        j-=1
    end
    a[j+1] = v
end
puts a.join(" ")

Measured memory_bytes: 8824
#include <bits/stdc++.h>
#define ll long long
#define INF 1000000005
#define MOD 1000000007
#define rep(i,n) for(int i=0;i<n;++i)

using namespace std;

typedef pair<int,int>P;

const int MAX_N = 100005;

int bit[MAX_N+1],n,q;

//i???????????§??????????¨??????????(i???1????????????)
int sum(int i)
{
	int s = 0;
	while(i>0){
		s += bit[i];
		i -= i & -i;
	}
	return s;
}
//i???????????????x????????????(i???1????????????)
void add(int i,int x)
{
	while(i <= n){
		bit[i] += x;
		i += i & -i;
	}
}

int main()
{
	scanf("%d%d",&n,&q);
	rep(i,q){
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		if(x==0){
			add(y,z);
		}else{
			printf("%d\n",sum(z)-sum(y-1));
		}
	}
	return 0;
}

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

void solve(string S){
  long long front_count = 0;
  REP(i, S.size()) {
    if ((((i%2) == 0) ? '0' : '1') == S[i]) front_count++;
  }

  long long back_count = 0;
  REP(i, S.size()) {
    if ((((i%2) == 1) ? '0' : '1') == S[i]) back_count++;
  }

  cout << (S.size() - max(front_count, back_count)) << endl;
}

// Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main(){
    string S;
  cin >> S;
    solve(S);
    return 0;
}


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

using namespace std;
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for (int i = 0; i < (n); i++)
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]"; return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}

void solve() {
    string s;
    cin >> s;
    int K;
    cin >> K;
    for (int i = 0; i < s.size(); i++) {
        if (s[i] == 'a') continue;
        if (26 - (s[i] - 'a') <= K) {
            K -= 26 - (s[i] - 'a');
            s[i] = 'a';
        }
    }
    s.back() += (K % 26);
    cout << s << endl;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.setf(ios::fixed);
    cout.precision(16);
    solve();
    return 0;
}

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

template <class T>
inline void read(T &res)
{
	res = 0; bool bo = 0; char c;
	while (((c = getchar()) < '0' || c > '9') && c != '-');
	if (c == '-') bo = 1; else res = c - 48;
	while ((c = getchar()) >= '0' && c <= '9')
		res = (res << 3) + (res << 1) + (c - 48);
	if (bo) res = ~res + 1;
}

typedef long long ll;

const int N = 1e5 + 5;

int n, p[N], fa[N], sze[N], dis[N];
ll d[N], dsum;
std::map<ll, int> occ;

inline bool comp(int a, int b) {return d[a] < d[b];}

int main()
{
	read(n);
	for (int i = 1; i <= n; i++) read(d[i]), p[i] = i, sze[i] = 1;
	std::sort(p + 1, p + n + 1, comp);
	for (int i = 1; i <= n; i++) occ[d[i]] = i;
	for (int i = n; i >= 2; i--)
	{
		int u = p[i]; occ[d[u]] = 0;
		int v = occ[d[u] - n + (sze[u] << 1)];
		if (!v) return puts("-1"), 0;
		fa[u] = v; sze[v] += sze[u];
	}
	for (int i = 2; i <= n; i++) dis[p[i]] = dis[fa[p[i]]] + 1;
	for (int i = 1; i <= n; i++) dsum += dis[i];
	if (d[p[1]] != dsum) return puts("-1"), 0;
	for (int i = 2; i <= n; i++) printf("%d %d\n", fa[p[i]], p[i]);
	return 0;
}

Measured memory_bytes: 12280
#include <bits/stdc++.h>
using namespace std;
#define logn long
int main() {
   long long N, Q; cin >> N >> Q;
   string S; cin >> S;
   vector<long long>A(S.size() + 1, 0);
   for (long long i = 1; i < S.size(); i++) {
       if (S.at(i - 1) == 'A' && S.at(i) == 'C') A.at(i) = A.at(i - 1) + 1;
       else A.at(i) = A.at(i - 1);
   }
   for (long long i = 0; i < Q; i++) {
       long long a,b;cin>>a>>b;
       cout << A.at(b - 1) - A.at(a - 1) << endl;
   }
}

Measured memory_bytes: 1792
import sys
input = sys.stdin.readline


def read():
    N, A, B, C, D = map(int, input().strip().split())
    return N, A, B, C, D


def solve(N, A, B, C, D, INF=10**28):

    cmin = N * D
    cache = dict()
    cache[0] = 0
    cache[1] = D
    cache[2] = min(D+D, D+A)
    
    def dfs(n):
        if n in cache:
            return cache[n]
        c = n * D
        c = min(c, dfs(n//2) + A + (n%2) * D)
        c = min(c, dfs(n//2+1) + A + ((-n-1)%2+1) * D)
        c = min(c, dfs(n//3) + B + (n%3) * D)
        c = min(c, dfs(n//3+1) + B + ((-n-1)%3+1) * D)
        c = min(c, dfs(n//5) + C + (n%5) * D)
        c = min(c, dfs(n//5+1) + C + ((-n-1)%5+1) * D)
        cache[n] = c
        return c
    
    return min(cmin, dfs(N))


if __name__ == '__main__':
    T = int(input().strip())
    for i in range(T):
        inputs = read()
        outputs = solve(*inputs)
        if outputs is not None:
            print("{}".format(outputs))


Measured memory_bytes: 23048
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,a,n) for(ll i = a;i < n;i++)
#define rrep(i,a,n) for(ll i = n; i >= a;i--)
#define index_check(i,n) if(i > n-1 || i < 0) continue; 
#define LINF 1e18
#define INF 1e9
#define MOD (ll)(1e9+7)
using namespace std;

#define fs first
#define sc second

using P = pair<ll,ll>;
using Pll = pair<P,ll>;
using PQ = priority_queue<P,vector<P>,greater<P>>;

signed main(){
    ll h,w;
    cin >> h >> w;
    ll n;
    cin >> n;
    ll a[n],index = 0;
    ll memo[h][w] = {};
    rep(i,0,n) cin >> a[i];

    rep(i,0,h){
        rep(j,0,w){
            if(i % 2 == 0){
                memo[i][j] = index+1;
            }
            else{
                memo[i][w-j-1] = index+1;
            }

            if(--a[index] <= 0){
                index++;
            }
        }
    }
    rep(i,0,h){
        rep(j,0,w){
            cout << memo[i][j] << ((j == w-1)?"":" ");
        }
        cout << endl;
    }
    return 0;
}

Measured memory_bytes: 384
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<cassert>
#include<iostream>
#include<sstream>
#include<string>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<utility>
#include<numeric>
#include<algorithm>
#include<bitset>
#include<complex>

using namespace std;

typedef long long Int;
typedef vector<int> vint;
typedef pair<int,int> pint;
#define mp make_pair

template<class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cout << *i << " "; cout << endl; }
template<class T> void chmin(T &t, T f) { if (t > f) t = f; }
template<class T> void chmax(T &t, T f) { if (t < f) t = f; }
int in() { int x; scanf("%d", &x); return x; }

int main() {
	int res=0;
	string str;
	for(;cin>>str;){
		int len=str.size();
		int i;
		bool flag=true;
		for(i=0;i<len/2;i++){
			if(str[i]!=str[len-i-1]){flag=false;break;}
		}
		if(flag)res++;
	}
	cout<<res<<endl;
	return 0;
}

Measured memory_bytes: 0
#include<bits/stdc++.h>
using namespace std;
int main(){
  long K;cin>>K;
  if(K<10){cout<<K;return 0;}
  vector<long>X(9);
  for(long i=1;i<10;i++)X[i-1]=i;
  long n=9;
  while(1){
    vector<long>Y;
    for(long x:X){
      for(long i=-1;i<=1;i++){
        if(x%10+i>=0 && x%10+i<=9)Y.push_back(x*10+(x%10+i));
      }
    }
    if(n+Y.size()>=K){
      sort(Y.begin(),Y.end());
      cout<<Y[K-n-1];return 0;
    }
    n+=Y.size(); 
    X.clear();X=Y;
  }
}

/*
再帰?





*/

Measured memory_bytes: 2080
#include <bits/stdc++.h>  // ios_base::sync_with_stdio(false);
#define MAXN 501          // cin.tie(NULL);
#define di pair<int, int>
#define tri pair<int, di>
#define bi pair<bool, int>
using namespace std;
void swap(int ar[],int  i,int j)
    {int aux = ar[j]; ar[j] = ar[i]; ar[i] = ar[j];}

int upperbound(long long ar[],int k, int length){
    int best = k;
    int l = k;
    int r = length;
    int m;
    while(r > l){
        m = (r + l) / 2;
        if(ar[m]/2  +  ar[m] % 2 <= ar[k]){
            best = m;
            l = m + 1;
        }
        else
            r = m;
    }
    return best;
}

int main(){
    int n;
    int k;
    cin >> n >> k;
    string s;
    cin >> s;

    s[k-1] += 32;
    cout << s ;
    return 0;
}

Measured memory_bytes: 256
N = int(input())
S =[]
times = {}
for i in range(N):
  word = input()
  if word in times:
    times[word] = times[word] + 1
  else:
    times[word] = 1
#itemsでタプルにして、mは一番多い回数を取っている。最後の[1]はタプルの二個目の要素の意味で、数字。
#key = lembdaのところはxが引数で、x[1]を参照するという意味、ここで引数は、times.items()のはず
m = max(times.items(), key = lambda x:x[1])[1]
a = []
for t in times.items():
	if(t[1]==m):
		a.append(t[0])
 
a.sort()
for t in a:
	print(t)


Measured memory_bytes: 32096
use io::*;
use std::*;

fn z_algorithm(s: &[char]) -> Vec<i64>
{
    let len = s.len();
    let mut z: Vec<i64> = vec![0i64; len];
    z[0] = len as i64;
    let mut i = 1usize;
    let mut j = 0usize;
    while i < len {
        while i + j < len && s[j] == s[i + j] {
            j += 1usize;
        }
        z[i] = j as i64;
        if j == 0usize {
            i += 1usize;
            continue;
        }
        let mut k = 1usize;
        while i + k < len && (k as i64) + z[k] < (j as i64) {
            z[i + k] = z[k];
            k += 1usize;
        }
        i += k;
        j -= k;
    }
    z
}

fn max_z(s: &[char]) -> i64 {
    let len: usize = s.len();
    let zs = z_algorithm(s);

    let mut result = 0;
    for i in 1..len {
        if (i as i64) >= zs[i] {
            if result < zs[i] {
                result = zs[i];
            }
        }
    }
    result
}

fn solve(n: i64, s: String) {
    let mut result = 0;
    let s: Vec<char> = s.chars().collect();
    for i in 0..((n-1) as usize) {
        let z = max_z(&s[i..]);
        if z > result {
            result = z;
        }
    }
    println!("{}", result);
}

// Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
fn main() {
    let con = read_string();
    let mut scanner = Scanner::new(&con);
    let n: i64;
    n = scanner.next();
    let s: String;
    s = scanner.next();
    // In order to avoid potential stack overflow, spawn a new thread.
    let stack_size = 104_857_600; // 100 MB
    let thd = std::thread::Builder::new().stack_size(stack_size);
    thd.spawn(move || solve(n, s)).unwrap().join().unwrap();
}

pub mod io {
    use std;
    use std::str::FromStr;

    pub struct Scanner<'a> {
        iter: std::str::SplitWhitespace<'a>,
    }

    impl<'a> Scanner<'a> {
        pub fn new(s: &'a str) -> Scanner<'a> {
            Scanner {
                iter: s.split_whitespace(),
            }
        }

        pub fn next<T: FromStr>(&mut self) -> T {
            let s = self.iter.next().unwrap();
            if let Ok(v) = s.parse::<T>() {
                v
            } else {
                panic!("Parse error")
            }
        }

        pub fn next_vec_len<T: FromStr>(&mut self) -> Vec<T> {
            let n: usize = self.next();
            self.next_vec(n)
        }

        pub fn next_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            (0..n).map(|_| self.next()).collect()
        }
    }

    pub fn read_string() -> String {
        use std::io::Read;

        let mut s = String::new();
        std::io::stdin().read_to_string(&mut s).unwrap();
        s
    }

    pub fn read_line() -> String {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        s.trim_right().to_owned()
    }
}


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

#define REP(i, start, count) for(int i=(start); i<(int)(count); ++i)
#define rep(i, count) REP(i, 0, count)
#define ALLOF(c) (c).begin(), (c).end()

typedef long long ll;
typedef unsigned long long ull;

int N, M;
vector<int> X;

int main(void) {
    cin >> N >> M;

    rep(i, M) {
        int a;
        cin >> a;
        X.push_back(a);
    }

    sort(ALLOF(X));

    vector<int> distance;

    rep(i, M - 1) {
        distance.push_back(abs(X[i + 1] - X[i]));
    }

    sort(ALLOF(distance));
    reverse(ALLOF(distance));

    ll sum = 0;

    if (N < M) {
        REP(i, N - 1, M) {
            sum += distance[i];
        }
    }

    cout << sum << endl;

    return 0;
}

Measured memory_bytes: 1400
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <set>
#include <cmath>
#include <queue>
#include <map>
#include <stack>
#include <bitset>
#include <numeric> //lcm
#include <iomanip> //double精度 setprecision

using namespace std;

#define rep(i,n) for(int i = 0; i < (n); ++i)
#define rrep(i,n) for(int i = n-1; i >= 0; --i)
#define rep1(i,n) for(int i = 1; i <= (n); ++i)
#define rrep1(i,n) for(int i = (n); i >= 1; --i)
#define all(vec) (vec).begin(),(vec).end()

#define debug(vec) for(auto v : vec) cerr << v << " "; cerr << endl;
#define debug2D(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << v << " "; cerr << endl; } 
#define debugP(vec) for(auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl;
#define debug2DP(vec2D) for(auto vec : vec2D) { for (auto v : vec) cerr << "(" << v.first << "," << v.second << ") "; cerr << endl; } 

typedef long long ll;

constexpr ll INF = 1000000000; //10^10
//const ll MOD = 998244353;
constexpr ll MOD = 1000000007;

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

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

	int k ; cin >> k;
	string s; cin >> s ;
	
	if (s.size() <= k) cout << s << endl;
	else {
	  rep(i,k) cout << s[i]; cout << "..." << endl;
	}
}

Measured memory_bytes: 3636
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

  public static void main(String[] args) {
    
    new Main().run();
  }
  public void run() {
    
    try(BufferedReader in = new BufferedReader(new InputStreamReader(System.in))) {

      String[] lines = in.readLine().split(" ");
      int n = Integer.parseInt(lines[0]);
      int k = Integer.parseInt(lines[1]);
      int ans = 1;
      int d = k - 1;

      for(int i=n; i>k; i-=d)
        ans++;
      System.out.println(ans);
    }
    catch(IOException e) {
      System.err.println(e);
    }
  }
}

Measured memory_bytes: 22484
#include<bits/stdc++.h>
using namespace std;
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
#define SORT(c) sort((c).begin(),(c).end())
#define IINF INT_MAX
#define LLINF LLONG_MAX
#define DEBUG false

typedef long long ll;
typedef pair<int, int> ii;

vector<int> C = {10, 50, 100, 500};

int main() {
	
	int n;
	bool f = true;
	while(cin >> n, n){
		vector<int> in(4);
		rep(i, 4) cin >> in[i];
		ll sum = in[0] * C[0] + in[1] * C[1] + in[2] * C[2] + in[3] * C[3];
		
		vector<int> ans(in);

		for(int i = 3; i >= 0; i--){
			while(sum >= n + C[i]){
				sum -= C[i];
				ans[i]--;
			}
		}		
		
		if(!f) cout << endl;
		f = false;
		if(ans[0] > 0) cout << C[0] << " " << ans[0] << endl;
		if(ans[1] > 0) cout << C[1] << " " << ans[1] << endl;
		if(ans[2] > 0) cout << C[2] << " " << ans[2] << endl;
		if(ans[3] > 0) cout << C[3] << " " << ans[3] << endl;
	}
	
	return 0;
}

Measured memory_bytes: 3044
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left, bisect_right #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

cA = [0] + A.copy()
for i in range(N):
    cA[i+1] += cA[i]

cB = [0] + B.copy()
for i in range(M):
    cB[i+1] += cB[i]

# print(cA, cB)

maxnum = 0
# for cosA in range(0, K+1):
#     cosB = K - cosA
#     indA = bisect_left(cA, cosA)
#     indB = bisect_left(cB, cosB)
#     num = indA + indB
#     if maxnum < num: maxnum = num
# print(maxnum)
for indA, ca in enu(cA):
    if K < ca: continue
    cosB = K - ca
    indB = bisect_right(cB, cosB) - 1
    num = indA + indB
    if maxnum < num: maxnum = num
    # print(indA, indB)
print(maxnum)

Measured memory_bytes: 114220
#include <stdio.h>

int main(){
    int h=0;
    int m=0;
    int s=0;
    int tmp=0;

    scanf("%d",&tmp);

    h=tmp/3600;
    tmp=tmp%3600;
    m=tmp/60;
    s=tmp%60;
    printf("%d:%d:%d\n",h,m,s);

    return 0;
}

Measured memory_bytes: 1772
#include <iostream>

using namespace std;

int main() {
  size_t N;
  cin >> N;
  for (size_t i = 1; i < 10; i++) {
    for (size_t j = 1; j < 10; j++) {
      if (N == i * j) {
        cout << "Yes" << endl;
        return 0;
      }
    }
  }

  cout << "No" << endl;
  return 0;
}


Measured memory_bytes: 764
#include<bits/stdc++.h>
using namespace std;
char area[1001][1001]; // 調査対象の領域
int rui[3][1001][1001]; // 累積和
int main(){
  int h,w,k,a,b,c,d;
  scanf("%d %d %d",&h,&w,&k);
  for(int i=1;i<=h;i++){
    for(int j=1;j<=w;j++){
      scanf(" %c",&area[i][j]);
      rui[0][i][j] = (area[i][j] == 'J');
      rui[1][i][j] = (area[i][j] == 'O');
      rui[2][i][j] = (area[i][j] == 'I');
      if(i != 1){
	rui[0][i][j] += rui[0][i-1][j];
	rui[1][i][j] += rui[1][i-1][j];
	rui[2][i][j] += rui[2][i-1][j];
      }
      if(j != 1){
	rui[0][i][j] += rui[0][i][j-1];
	rui[1][i][j] += rui[1][i][j-1];
	rui[2][i][j] += rui[2][i][j-1];
      }
      if(i != 1 && j != 1){
	rui[0][i][j] -= rui[0][i-1][j-1];
	rui[1][i][j] -= rui[1][i-1][j-1];
	rui[2][i][j] -= rui[2][i-1][j-1];
      }
    }
  }
  int ans;
  for(int i=0;i<k;i++){
    scanf("%d %d %d %d",&a,&b,&c,&d);
    for(int j=0;j<3;j++){
      ans = 0;
      ans = rui[j][c][d];
      if(a != 1) ans -= rui[j][a-1][d];
      if(b != 1) ans -= rui[j][c][b-1];
      if(a != 1 && b != 1) ans += rui[j][a-1][b-1];
      printf("%d",ans);
      putchar(j==2?'\n':' ');
    }
  }
  return (0);
}

Measured memory_bytes: 15664
#include <iostream>
#include <cstdio>
#include <cstdlib>
#define MOD 1000000007
#define ll long long

using namespace std;

int n;
ll dp[4010][4010], num[4010][4010];
ll fac[8010], invfac[8010];

ll exp(ll a, ll b)
{
	if (!b) return 1;
	ll k = exp(a, b / 2);
	if (b & 1)
		return k * k % MOD * a % MOD;
	return k * k % MOD;
}

void init()
{
	fac[0] = invfac[0] = 1;
	for (int i = 1; i <= 8000; i++)
	{
		fac[i] = fac[i - 1] * i % MOD;
		invfac[i] = exp(fac[i], MOD - 2);
//		cout << fac[i] * invfac[i] % MOD << ' ';
	}
}

ll C(int n, int m)
{
	return fac[n] * invfac[m] % MOD * invfac[n - m] % MOD;
}

int main()
{
	ios::sync_with_stdio(false);
	init();
	cin >> n;
	ll ans = 0;
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		cin >> a >> b;
		dp[2000 - a][2000 - b]++;
		num[2000 + a][2000 + b]++;
		ans = (ans - C(2 * a + 2 * b, 2 * a) + MOD) % MOD;
	}
	for (int i = 0; i <= 4000; i++)
		for (int j = 0; j <= 4000; j++)
		{
			if (i) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD;
			if (j) dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD;
		}
	for (int i = 2000; i <= 4000; i++)
		for (int j = 2000; j <= 4000; j++)
			ans = (ans + dp[i][j] * num[i][j] % MOD) % MOD;
	ll inv2 = exp(2, MOD - 2);
	ans = (ans * inv2) % MOD;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 190080
import           Control.Monad
import qualified Data.ByteString.Char8 as BS
import           Data.List
import           Data.Maybe

readInts :: IO [Int]
readInts = map (fst . fromJust . BS.readInt) . BS.words <$> BS.getLine

main = do
  _ <- BS.getLine
  a <- readInts
  b <- readInts
  print $ solve a b

solve [a] [] = 0
solve (a:a':xa) (b:xb) = min a b + min (b - min a b) a' + solve (a' - min a' (b - min a b) : xa) xb


Measured memory_bytes: 10108
#include<stdio.h>



void trace(int A[],int N);
void insertsort(int A[],int N);




int main(void){

 
  
  int N,i,j;
  
  scanf("%d",&N);

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

  
  trace(A,N);
  insertsort(A,N);

    return 0;
}





void trace(int A[],int N){
  int i;
  for(i=0;i<N;i++){
    if(i==N-1){
      printf("%d",A[i] );
      }
    else printf("%d ",A[i]);
  }
  printf("\n");


}





void insertsort(int A[],int N){
  int j,i,v;
  int k;
  for(i=1;i<N;i++){
    v=A[i];
    j=i-1;
    while((j>=0)&&(A[j]>v)){
      A[j+1]=A[j];
      j--;
    }
    A[j+1]=v;
    trace(A,N);
  }
}



Measured memory_bytes: 2068
#include<bits/stdc++.h>
#define endl '\n'
#define INF (1 << 21)
const int MOD = 1000000007;
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  int n;
  int v[30], c[30];
  int value = 0, cost = 0;
  int ans = 0;

  cin >> n;

  for(int i = 0;i < n;i++){
    cin >> v[i];
  }
  
  for(int i = 0;i < n;i++){
    cin >> c[i];
  }
  
  for(int i = 0;i < n;i++){
    if(ans < (value + v[i]) - (cost + c[i])){
      ans = (value + v[i]) - (cost + c[i]);
      value += v[i];
      cost += c[i];
    }
  }

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



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

 int main(){
 int N;cin>>N;
 vector<int>v(N);
 for(int i=0;i<N;++i){
 cin>>v[i];
 }
 sort(v.begin(),v.end());

 int answer=v[v.size()/2]-v[v.size()/2-1];
 cout<<answer<<endl;
 return 0;
}


Measured memory_bytes: 640
#include <stdio.h>
int main()
{
    int x,a,b;
    scanf("%d %d %d",&x,&a,&b);
    if(b<=a)
    printf("delicious");
    if(x+a>=b&&b>a)
    printf("safe");
    if(x+a<b)
    printf("dangerous");
}


Measured memory_bytes: 128
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e5+7;
long long w[105],v[105],f[N];
int main()
{
    int n,W;cin >> n >> W;
    for(int i = 1;i <= n;++i)   cin >> w[i] >> v[i];
    for(int i = 1;i <= n;++i)
        for(int j = W;j >= w[i];--j)
            f[j] = max(f[j],f[j - w[i]] + v[i]);
    cout << f[W];
    return 0;
}


Measured memory_bytes: 1024
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<iomanip>
#include<cmath>


#define REP(i,n) for (int i = 0; (i) < (n); ++ (i))
#define FOR(i,n) for (int i = 1; (i) <= (n); ++ (i))
#define dump(x)  cout << #x << " = " << (x) << endl;
#define pb push_back
#define int long long
//#define lint long long

const int INF = 1e18;
const int MOD = 1e9+7;
//const lint LINF = 1e18;
const double eps = 0.000000001;//もとの値の10^(-16)まで

using namespace std;

//typedef pair<int, int> P;
//priority_queue< P, vector<P>, greater<P> > q;//ダイクストラの時、greaterで小さい順

signed main(){
  string s;
  cin  >> s;
  string ans = "Yes";
  REP(i,s.size()){
    if(i%2==0){
      if(s[i]=='L') ans = "No";
    }
    else{
      if(s[i]=='R') ans = "No";
    }
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<vector>
using namespace std;
#define rep(i,n) for(int i=0;i<(n);++i)
using ll = long long;
using P = pair<int, int>;
#include<algorithm>
#include<math.h>
#include<map>
#include<queue>
#include<set>

int main() {
	int k = 1000001;
	int n;
	cin >> n;
	vector<int>a(k);
	vector<int>b(n);
	rep(i, n) {
		int x;
		cin >> x;
		b[i] = x;
		if (a[x] != 0) {
			a[x]++;
			continue;
		}
		for (int j = x; j < k; j += x) {
			a[j]++;
		}
	}
	ll ct(0);
	for (int i : b) {
		//cout << i << endl;
		if (a[i]==1) {
			//cout << a[i] << endl;
			++ct;
		}
	}
	cout << ct << endl;
	return 0;
}

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

//{{{
#if ((_WIN32 || __WIN32__) && __cplusplus < 201103L)
#define lld I64d
#else
#define lld lld
#endif
using namespace std;
typedef long long LL;
typedef vector<int> VI;
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define clr(a, b) memset(a, b, sizeof(a))
// clang-format off
#define debug(args...) {vector<string> _v = split(#args, ','); err(_v.begin(), args); cerr<<endl;}
 vector<string> split(const string& s, char c) {vector<string> v; stringstream ss(s); string x;
 while (getline(ss, x, c)) v.push_back(x); return v;} void err(vector<string>::iterator) {}
 template<typename T, typename... Args> void err(vector<string>::iterator it, T a, Args... args)
{cerr << it -> substr((*it)[0] == ' ', it -> length()) << " = " << a << ", "; err(++it, args...);}
// clang-format on
//}}}
//

int T;
const int N = 2e5 + 10;
int n;

struct E
{
    int k, l, r;
} p[N];
vector<pair<LL, LL>> pa, pb;
bool cmp(const pair<LL, LL>& a, const pair<LL, LL>& b)
{
    if (a.second == b.second) return a.first < b.first;
    return a.second > b.second;
}

int arr[N];
int sz;

int lowbit(int x) { return x & (-x); }

void add(int i, int num)
{
    for (; i <= sz; arr[i] += num, i += lowbit(i))
        ;
}
int query(int i)
{
    int s = 0;
    for (; i; s += arr[i], i -= lowbit(i))
        ;
    return s;
}
int getk(int k)
{
    int ans = 0;
    for (int i = 20; i >= 0; i--)
    {
        ans += 1 << i;
        if (ans > sz || arr[ans] >= k)
            ans -= 1 << i;
        else
            k -= arr[ans];
    }
    return ans + 1;
}

LL solve(vector<pair<LL, LL>>& vec)
{
    sz = vec.size();
    if (sz == 0) return 0;
    sort(vec.begin(), vec.end(), cmp);

    LL ans = 0;

    arr[0] = 0;
    for (int i = 1; i <= sz; i++) arr[i] = lowbit(i);
    for (auto pr : vec)
    {
        int pos = pr.first;
        LL w = pr.second;
        pos = min(sz, pos);
        int s = query(pos);
        if (s == 0) continue;

        ans += w;

        int insert_pos = getk(s);
        add(insert_pos, -1);
    }
    return ans;
}

int main()
{
#ifdef LOCAL
    freopen("in", "r", stdin);
    // freopen("out", "w", stdout);
#endif

    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        pa.clear();
        pb.clear();

        LL ans = 0;
        for (int i = 1; i <= n; i++)
        {
            scanf("%d%d%d", &p[i].k, &p[i].l, &p[i].r);
            if (p[i].l > p[i].r)
            {
                pa.push_back({p[i].k, p[i].l - p[i].r});
                ans += p[i].r;
            }
            else if (p[i].l < p[i].r)
            {
                pb.push_back({n - p[i].k, p[i].r - p[i].l});
                ans += p[i].l;
            }
            else
                ans += p[i].l;
        }

        // debug(ans);

        LL va = solve(pa);
        LL vb = solve(pb);
        // debug(va);
        // debug(vb);
        ans = ans + va + vb;
        cout << ans << endl;
    }

    return 0;
}

Measured memory_bytes: 9256