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

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

        int a = inp.nextInt();

        int b = inp.nextInt();

        if (a == b) {
            System.out.println("a == b");
        } else if (a < b) {
            System.out.println("a < b");
        } else if (a > b) {
            System.out.println("a > b");
        }
    }
}



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

#define REP(i,m,n) for(int i=(m); i<(int)(n); i++)
#define RREP(i,m,n) for(int i=(int)(n-1); i>=m; i--)
#define rep(i,n) REP(i,0,n)
#define rrep(i,n) RREP(i,0,n)
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()
#define fi first
#define se second
#define debug(...) {cerr<<"[L"<<__LINE__<<"] "; _debug(__VA_ARGS__);}

template<typename T1, typename T2>
ostream& operator<<(ostream& o, const pair<T1, T2>& p){
    return o << "(" << p.first << ", " << p.second << ")";
}
template<typename T>
string join(const vector<T>&v, string del=", "){ stringstream s;
    for(auto x : v) s << del << x; return s.str().substr(del.size());
}
template<typename T>
ostream& operator<<(ostream& o, const vector<T>&v){
    if(v.size()) o << "[" << join(v) << "]"; return o;
}
template<typename T>
ostream& operator<<(ostream& o, const vector<vector<T> >&vv){
    int l = vv.size();
    if(l){ o<<endl; rep(i,l) o << (i==0 ? "[ " : ",\n  " ) << vv[i] << (i==l-1 ? " ]" : ""); }
    return o;
}
inline void _debug(){cerr<<endl;}
template<class First, class... Rest>
void _debug(const First& first, const Rest&... rest){cerr<<first<<" ";_debug(rest...);}

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

const double PI = (1*acos(0.0));
const double EPS = 1e-9;
const int INF = 0x3f3f3f3f;
const ll INFL = 0x3f3f3f3f3f3f3f3fLL;
const ll mod = 1e9 + 7;

inline void finput(string filename) {
    freopen(filename.c_str(), "r", stdin);
}

int main(){
    ios_base::sync_with_stdio(0);
    // finput("./input");
    int n; cin >> n;
    vi a(n), s(n+1);
    rep(i,n) cin >> a[i];
    sort(all(a));

    deque<int> P,M;
    rep(i,n){
        if(a[i] >= 0) P.push_back(a[i]);
        else M.push_back(a[i]);
    }
    if(P.size() == 0){
        P.push_back(M.back());
        M.pop_back();
    }
    if(M.size() == 0){
        M.push_back(P.front());
        P.pop_front();
    }

    vector<pii> ope;
    while(P.size() > 1){
        int x = M.front(); M.pop_front();
        int y = P.back(); P.pop_back();
        M.push_back(x-y);
        ope.emplace_back(x, y);
    }
    while(M.size() > 0){
        int x = P.front(); P.pop_front();
        int y = M.back(); M.pop_back();
        P.push_back(x-y);
        ope.emplace_back(x, y);
    }
    cout << P[0] << endl;
    for(auto p : ope){
        cout << p.fi  << " " << p.se << endl;
    }
    return 0;
}

Measured memory_bytes: 5532
main :: IO ()
main = do
  n <- readLn
  if n == 0
    then return ()
    else do
      ls <- getLine
      let order = take 100 (cycle [1..n])
          init = zip [1..n] (repeat 0)
      putStrLn $ solve init order ls 0
      main

solve :: [(Int,Int)] -> [Int] -> String -> Int -> String
solve hand _ [] field = format ((sort (toList hand)) ++ [field])
  where
    format :: [Int] -> String
    format [] = []
    format [x] = show x
    format (x:xs) = (show x) ++ " " ++ (format xs)
    sort :: [Int] -> [Int]
    sort [] = []
    sort (x:xs) = (sort (filter (\y -> y <= x) xs)) ++ [x] ++ (sort (filter (\y -> y > x) xs))
    toList :: [(Int,Int)] -> [Int]
    toList [] = []
    toList ((a,b):r) = b:(toList r)
solve hand (x:xs) (y:ys) field
  | y == 'M' = solve (plus hand x) xs ys field
  | y == 'S' = solve (zero hand x) xs ys (add field hand x)
  | y == 'L' = solve (get hand x field) xs ys 0
  where
    plus :: [(Int,Int)] -> Int -> [(Int,Int)]
    --plus [] _ = []
    plus ((a,b):r) i
      | a == i = (a,b+1):r
      | otherwise = (a,b):(plus r i)
    zero :: [(Int,Int)] -> Int -> [(Int,Int)]
    --zero [] _ = []
    zero ((a,b):r) i
      | a == i = (a,0):r
      | otherwise = (a,b):(zero r i)
    add :: Int -> [(Int,Int)] -> Int -> Int
    --add field [] _ = field
    add field ((a,b):r) i
      | a == i = field + b + 1
      | otherwise = add field r i
    get :: [(Int,Int)] -> Int -> Int -> [(Int,Int)]
    --get [] _ _ = []
    get ((a,b):r) i field
      | a == i = (a,b+field+1):r
      | otherwise = (a,b):(get r i field)

Measured memory_bytes: 4136
N,M = gets.split.map(&:to_i)
AB = N.times.map { gets.split.map(&:to_i) }

# 金額でソート
AB.sort_by! { |x| x[0] }

bought = 0
pay = 0
N.times do |i|
  p = AB[i][0] * AB[i][1]
  # i番目の店でMに達しない場合(買い占める)
  if M > bought + AB[i][1]
    bought += AB[i][1]
    pay += p
  else
    # Mに達する場合(必要な分だけ買う)
    diff = M - bought
    bought += diff
    pay += diff * AB[i][0]
    break
  end
end

puts pay

Measured memory_bytes: 12664
#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;
using ll = long long;
using P = pair<int,int>;

int f1(int n){
  int x = 1;
  int ans = 0;
  while(6*x*x <= n){
    if(6*x*x == n) ans = 1;
    x++;
  }
  return ans;
}

int f2(int n){
  int cnt = 0;
  int x = 1;
  while(6*x*x <= n){
    int m = n - x*x;
    int y = x+1;
    while(2*x*y+3*y*y <= m){
      if(2*x*y+3*y*y == m) cnt++;
      y++;
    }
    x++;
  }
  return cnt;
}

int f3(int n){
  int cnt = 0;
  int x = 1;
  while(6*x*x <= n){
    int m = n-3*x*x;
    int z = x+1;
    while(z*z+2*x*z <= m){
      if(z*z+2*x*z == m) cnt++;
      z++;
    }
    x++;
  }
  return cnt;
}

int f4(int n){
  int cnt = 0;
  int x=1;
  while(6*x*x <= n){
    int m=n-x*x;
    int y=x+1;
    while(2*x*y+3*y*y <= m){
      int l=m-y*y-x*y;
      int z = y+1;
      while(z*z+z*(x+y) <= l){
        if(z*z+z*(x+y) == l) cnt++;
        z++;
      }
      y++;
    }
    x++;
  }
  return cnt;
}

int main(){
  int n;
  cin >> n;
  for (int i=1; i <= n; i++){
    int cnt = 0;
    cnt += f1(i);
    cnt += 3*f2(i);
    cnt += 3*f3(i);
    cnt += 6*f4(i);
    cout << cnt << endl;
  }
  return 0;
}


Measured memory_bytes: 3560
import sys
input = sys.stdin.readline
 
def main():
    N,W = map(int,input().split())
    dp = [-1 for _ in range(W+1)]
    dp[W] = 0
    for _ in range(N):
        nm,nv = [int(a) for a in input().split()]
        for j in range(nm,W+1):
            a = nm
            if dp[j] == -1:
                continue
            if dp[j-a] < dp[j] + nv:
                dp[j-a] = dp[j] + nv
    print(max(dp))
 
if __name__ == "__main__":
    main()

Measured memory_bytes: 7760
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    private static final int MOD = 1_000_000_007;
    private static final String YES = "Yes";
    private static final String NO = "No";

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

        int N = sc.nextInt();
        int[] A = new int[N];
        for (int i=0; i<N; i++) {
            A[i] = sc.nextInt();
        }

        System.out.println(solve(N, A));
    }

    private static int solve(int N, int[] A) {
        Arrays.sort(A);

        int count = 1;
        long size = A[0];
        for (int i=1; i<N; i++) {
            if (A[i] <= 2*size) {
                count++;
                size += A[i];
            } else {
                count = 1;
                size += A[i];
            }
        }

        return count;
    }
}

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

using namespace std;
#define sqr(x) ((x)*(x))
#define cube(x) ((x)*(x)*(x))
#define GCD(a, b) __gcd(a, b)
#define LCM(a, b) ((a)*(b)/GCD(a,b))
#define PI (3.141592653589793238462643383279502884197169399375105820974944)
#define MP make_pair
#define n1 first
#define n2 second
#define ALL(x) (x).begin(), (x).end()
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define PDB pair<db,db>
#define SI set<int>
#define SL set<ll>
#define MS multiset
#define MSI multiset<int>
#define MSLL multiset<ll>
#define PB push_back
#define PF push_front
#define VI vector<int>
#define VPI vector<pair<int,int>>
#define VLL vector<ll>
#define VS vector<string>
#define SZ(x) ((int)x.size())

typedef long long ll;

typedef unsigned long long ull;
typedef long double ld;
typedef double db;
const db eps = 0.000001;
const int INF = 1000000007;
const ll LINF = 1000000000000000555;
const int N = 1450555;
const int M = 1155;

VI v[N];
int a[N];
bool used[N];
int cnt[N];
void solve() {
    int mln = 1e6;
    for (int i = 1; i <= mln; i++){
        for (int j = i; j <= mln; j += i){
            v[j].PB(i);
        }
    }
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
        cnt[a[i]]++;
        used[a[i]] = true;
    }

    int z = 0;
    for (int i = 1; i <= n; i++){
        if (cnt[a[i]] > 1) continue;
        bool ok = true;
        for (int x : v[a[i]]){
            if (used[x] && x != a[i]){
                ok = false;
                break;
            }
        }
        if (ok) z++;
    }

    cout << z;

}

int main() {
    ios_base::sync_with_stdio(false);
#ifdef dxz05
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else

#endif

    int T = 1;
    //cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

Measured memory_bytes: 133972
import math

def solve():
    num_total = int(input())
    num_transport=[0]*5
    for i in range(5):
        num_transport[i]=int(input())
    time = math.ceil(num_total/num_transport[0])
    x = num_transport[0]
    for i in range(1,5):
        if num_transport[i] < x:
            time = i+ math.ceil(num_total/num_transport[i])
            x = num_transport[i]
        else:
            time += 1
    print(time)


solve()

Measured memory_bytes: 3060
using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {

        static void Main(string[] args)
        {

            while (true)
            {
                int[] inputs = Console.ReadLine()
                    .Split(' ')
                    .Select(x => int.Parse(x))
                    .ToArray();

                int h =  inputs[0];
                int w =  inputs[1];

                bool finished = (h == 0) && (w == 0);

                if(finished)
                    break;

                for (int i = 0; i < h; i++)
                {
                    bool dot = (i % 2) == 0 ? false : true;
                    for (int j = 0; j < w; j++)
                    {
                        Console.Write(dot? ".":"#");
                        dot = !dot;
                    }
                    Console.WriteLine();
                }
                Console.WriteLine();
            }
        }
    }
}

Measured memory_bytes: 9316
#include<bits/stdc++.h>
using namespace std;
int main(){
char a,b;
  cin>>a>>b;
  if(a=='H'){
  cout<<b<<endl;
  }
  if(a=='D'&&b=='H'){
  cout<<'D'<<endl;
  }
  if(a=='D'&&b=='D'){
  cout<<'H'<<endl;
  
  }

}


Measured memory_bytes: 256
import itertools

while True:
    n = int(input())
    
    if n == 0:
    	break
    
    score_lst = [int(i) for i in input().split()]
    
    dist = 1000001
    
    for i1, i2 in itertools.combinations(score_lst, 2):
    	if abs(i1 - i2) < dist:
    		dist = abs(i1 - i2)
    		
    print(dist)


Measured memory_bytes: 5756
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef  unsigned long long int ull;
typedef pair<ll,ll> P;
template<class T> using V=vector<T>; 
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
//const ll mod=998244353;
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
ll lcm(ll c,ll d){return c/gcd(c,d)*d;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
ll dp[101][2][4];//何文字目までみたか,超えてないか,何桁か
int main(){
    string s;
    cin>>s;
    int n,d;
    cin>>d;
    n=s.size();
    dp[0][0][0]=1;
    for(int i=0;i<n;i++){
        int tmp=s[i]-'0';
        for(int j=0;j<2;j++){
            for(int k=0;k<=(j?9:tmp);k++){
            for(int r=d-1;r>=0;r--){
                if(k==0)dp[i+1][j||(j!=1&&tmp!=k)][r]+=dp[i][j][r];
                else dp[i+1][j||(j!=1&&tmp!=k)][r+1]+=dp[i][j][r];
            }
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++)for(int j=0;j<2;j++)ans+=dp[i][j][d];
    cout<<ans<<endl;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<vector>
#include<queue>
#include<map>
#include<tuple>
#define rep(index,num) for(int index=0;index<num;index++)
#define rep1(index,num) for(int index=1;index<=num;index++)
#define scan(argument) cin>>argument
#define prin(argument) cout<<argument<<endl
#define kaigyo cout<<endl
#define eps 1e-15
#define mp(a1,a2) make_pair(a1,a2)
typedef long long ll;
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=1e+18+1;
int INF=1e+9+1;
int dp[41][401][401];
int main(){
	int N,Ma,Mb;
	int a[41],b[41],c[41];
	int asum=0,bsum=0;
	fill(dp[0][0],dp[41][0],INF);
	scan(N);scan(Ma);scan(Mb);
	rep(i,N){
		scan(a[i]);scan(b[i]);scan(c[i]);
		asum+=a[i],bsum+=b[i];
	}
	dp[0][0][0]=0;
	rep(i,N){
		rep(j,asum+1){
			rep(k,bsum+1){
				dp[i+1][j][k]=dp[i][j][k];
				if(j>=a[i]&&k>=b[i]){
					dp[i+1][j][k]=min(dp[i][j-a[i]][k-b[i]]+c[i],dp[i+1][j][k]);
				}
			}
		}
	}
	int ans=INF;
	rep1(i,INF){
		if(i*Ma>asum||i*Mb>bsum) break;
		ans=min(ans,dp[N][i*Ma][i*Mb]);
	}
	if(ans==INF) prin(-1);
	else prin(ans);
	return 0;
}


Measured memory_bytes: 25984
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int h,w;
    cin>>h>>w;
    int g[h][w];
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            char c;
            cin>>c;
            if(c=='.')
                g[i][j]=0;
            else
                g[i][j]=100000;
        }
    }
    int dx[8]={1,0,-1,0,1,-1,1,-1};
    int dy[8]={0,1,0,-1,1,1,-1,-1};
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(g[i][j]==100000)
            {
                for(int k=0;k<8;k++)
                {
                    int newx=i+dx[k];
                    int newy=j+dy[k];
                    if(newx>=0 and newx<h and newy>=0 and newy<w and g[newx][newy]!=100000)
                        g[newx][newy]++;
                }
            }
        }
    }
    for(int i=0;i<h;i++)
    {
        for(int j=0;j<w;j++)
        {
            if(g[i][j]==100000)
                cout<<"#";
            else
                cout<<g[i][j];
        }
        cout<<endl;
    }
    return 0;
}

Measured memory_bytes: 3612
# -*- coding: utf-8 -*-
n = int(input())
d, x = [int(i) for i in input().split()]
a = []
for i in range(n):
    a.append(int(input()))

total = x
for i in range(n):
    for j in range(1, d + 1):
        for h in range(d + 1):
            if h * a[i] + 1 == j:
                total += 1
print(total)


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

int main() {

    string c;
    cin >> c;

    bool isOk = false;
    if (c[0] == c[1] && c[2] == c[3] && c[0] != c[2]) isOk = true;
    if (c[0] == c[2] && c[1] == c[3] && c[0] != c[1]) isOk = true;
    if (c[0] == c[3] && c[1] == c[2] && c[0] != c[1]) isOk = true;

    if(isOk) cout <<"Yes" << endl;
    else cout << "No" << endl;

    return 0;
}

Measured memory_bytes: 256
N = int(input())
A,B,C,D,E = map(int,[input() for i in range(5)])
ans = 0
def mymax(s):
    res = N//s
    if N%s==0:
        return res
    else:
        return res+1

k = max(mymax(A),mymax(B),mymax(C),mymax(D),mymax(E))
print(k+4)

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

using namespace std;

int main() {
	long long n, a, b;
	cin >> n >> a >> b;

	long long sum = a + b;

	long long tempN = n;

	long long res = 0;

	long long totalA = ((n / sum) * a);

	res += ((n / sum) * a);

	n -= totalA;
	n -= ((tempN / sum) * b);

	res += min(n, a);

	cout << res;
}

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

#define foru(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, l, r) for(int i = (l); i >= (r); --i)

#define maxn 30010

int n;
bool mark[maxn];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
//    freopen("abc.inp", "r", stdin); freopen("abc.out", "w", stdout);
    cin >> n;
    if (n == 3) {
      cout << "2 5 63";
      return 0;
    }
    vector<int> ans;
    vector<int> div6, div21, div22, div3;

    for (int i = 2; i <= 30000; ++i) {
      if (i % 6 == 0) div6.push_back(i);
      if (i % 2 == 0) {
        if (i % 3 == 1) div21.push_back(i);
        if (i % 3 == 2) div22.push_back(i);
      } else {
        if (i % 3 == 0) div3.push_back(i);
      }
    }
    int cnt = 0;
    ans.push_back(2); ans.push_back(3);
    ans.push_back(4); ans.push_back(9);
    n -= 4;

    int j = 2;
    while (cnt + 2 <= n) {
      if (j + 1 >= div3.size()) break;
      ans.push_back(div3[j]);
      ++j;
      ans.push_back(div3[j]);
      ++j;
      cnt += 2;
    }

    j = 1;
    while (cnt + 2 <= n) {
      if (j == div21.size() || j == div22.size()) break;
      ans.push_back(div21[j]);
      ans.push_back(div22[j]);
      ++j; cnt += 2;
    }

    j = 0;
    while (cnt + 1 <= n) {
      ans.push_back(div6[j]);
      ++j;
      ++cnt;
    }
    for (auto x : ans) cout << x <<' ';
    return 0;
}


Measured memory_bytes: 3768
s = int(input())

for i in range(1,s+1):
  #1の位
  a = i%10
  #10の位
  b = ((i-a)//10)%10
  #100の位
  c = ((i-(a+b*10))//100)%10
  #1000の位
  d = ((i-(a+b*10+c*100))//1000)%10
  #10000の位
  e = ((i-(a+b*10+c*100+d*1000))//10000)%10

  if a==3 or b==3 or c==3 or d==3 or e==3 or i%3==0:
      print(" %d"%i, end = "")
      
  a = 0
  b = 0
  c = 0
  d = 0
  e = 0
  
print()


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

int main(void){
    int a, b;
    int q;
    int i, j, temp;
    char str[1000];
    char command[1000];
    char rpc[1000];

    scanf("%s", str);
    scanf("%d", &q);
    for(i = 0; i < q; i++){
        scanf("%s %d %d", command, &a, &b);
        if(!strcmp(command, "replace")){
            scanf("%s", rpc);
            for(j = a; j <= b; j++)
                str[j] = rpc[j- a];
        }else if(!strcmp(command,"reverse")){
            for(j = a; j < b; j++, b--){
                temp = str[j];
                str[j] = str[b];
                str[b] = temp;
            }
        }else if(!strcmp(command, "print")){
            for(j = a; j <= b; j++)
                putchar(str[j]);
            puts("");
        }
     }
     return 0;
}


Measured memory_bytes: 2080
#include <bits/stdc++.h>
using namespace std;
#define idfc ios_base::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)
#define ll long long
#define pb push_back
#define mp make_pair
#define nt _int128
#define ld long double
long double PI =3.14159265358979323846;


const ll modo=1e9+7;
const ll inf=2e14;
const ll ms=(1e6) +5;

ll bit[ms]={0};
ll ar[ms];
map<ll,ll> mm;
ll cc;
set<ll> mak;
set<pair<ll,ll>> ss;
void update(ll i,ll v)
{
    ll n=cc;
    //cout<<i<<" "<<v<<" "<<cc<<endl;
    while(i<=n)
    {
        bit[i]+=v;
        i+=(i&-i);
    }
}



ll query(ll i)
{
    ll r=0;
    while(i>0)
    {
        r+=bit[i];
        i-=(i&-i);
    }
    return r;
}



ll bins(ll n)
{
    ll l=1;
    ll r=cc;
    ll m;
    ll ans=0;
    while(l<=r)
    {
        m=(l+r)/2;
        if(ar[m]<=n)
        {
            ans=max(ans,m);
            l=m+1;
        }
        else r=m-1;
    }
    return ans;
}

int main()
{
    idfc;
    ll n,d,a;
    cin>>n>>d>>a;
    ll aa,b;
    ll i;
    for(i=1;i<=n;i++)
    {
        cin>>aa>>b;
        ss.insert({aa,b});
        mak.insert(aa); mak.insert(aa+1+(2*d));
    }
     cc=1;
    
    for(ll ii:mak)
    {
        ar[cc]=ii;
        mm[ii]=cc;
        cc++;
    }
    ll x,y;
    ll val;
    ll num;
    ll ans=0;
    for(auto it:ss)
    {
        aa=it.first;
        b=it.second;
        y=bins(aa-1);
        val=b+query(mm[aa]);
        //cout<<val<<" "<<y<<" "<<mm[aa]<<" "<<query(mm[aa])<<endl;
        if(val>0)
        {
            num=ceil((val*1.0)/a);
            ans+=num;
            y=mm[aa+1+(2*d)];
            //cout<<y<<endl;
            //cout<<num*a<<endl;
            update(mm[aa],-(num*a)); update(y,num*a);
        }
    }
    cout<<ans;
}

Measured memory_bytes: 68736
using System;
using System.Collections.Generic;
using System.Linq;
using System.Diagnostics;

class Program
{
    static void Main(string[] args)
    {
        string s = Console.ReadLine();
        List<bool> cube = new List<bool>();
        for (int i = 0; i < s.Length; i++)
        {
            if (s[i] == '1') cube.Add(true);
            else cube.Add(false);
        }

        for (int i = 0; i < cube.Count - 1; i++)
        {
            if (i < 0) i = 0;
            if (cube[i] != cube[i + 1])
            {
                cube.RemoveAt(i + 1);
                cube.RemoveAt(i);
                i = i - 2;
            }
        }

        Console.WriteLine(s.Length - cube.Count);
    }
}

Measured memory_bytes: 13536
# -*- coding: utf-8 -*-

n=int(input())
a=list(map(int, input().split()))

ans=0
while True:
    for i in range(n):
        if a[i]%2==1:
            break
        a[i]=int(a[i]/2)
    else:
        ans+=1
        continue
    break
print(ans)


Measured memory_bytes: 2940
#include <stdio.h>
 
int main(void) {
    int saikoro[6];
    int q,i;
    int top,front;
    int result;
     
    for(i=0;i<6;i++){
        scanf("%d",&saikoro[i]);
    }
    scanf("%d",&q);
    for(i=0;i<q;i++){
        scanf("%d %d",&top,&front);
        result = dice(saikoro,top,front);
        printf("%d\n",result);
    }
    return 0;
}
int dice(int saikoro[6],int top,int front){
    if(top == saikoro[0]){
        if(front == saikoro[1]) return saikoro[2];
        if(front == saikoro[2]) return saikoro[4];
        if(front == saikoro[3]) return saikoro[1];
        if(front == saikoro[4]) return saikoro[3];
    }
    if(top == saikoro[1]){
        if(front == saikoro[0]) return saikoro[3];
        if(front == saikoro[2]) return saikoro[0];
        if(front == saikoro[3]) return saikoro[5];
        if(front == saikoro[5]) return saikoro[2];
    }
    if(top == saikoro[2]){
        if(front == saikoro[0]) return saikoro[1];
        if(front == saikoro[1]) return saikoro[5];
        if(front == saikoro[4]) return saikoro[0];
        if(front == saikoro[5]) return saikoro[4];
    }
    if(top == saikoro[3]){
        if(front == saikoro[0]) return saikoro[4];
        if(front == saikoro[1]) return saikoro[0];
        if(front == saikoro[4]) return saikoro[5];
        if(front == saikoro[5]) return saikoro[1];
    }
    if(top == saikoro[4]){
        if(front == saikoro[0]) return saikoro[2];
        if(front == saikoro[2]) return saikoro[5];
        if(front == saikoro[3]) return saikoro[0];
        if(front == saikoro[5]) return saikoro[3];
    }
    if(top == saikoro[5]){
        if(front == saikoro[1]) return saikoro[3];
        if(front == saikoro[2]) return saikoro[1];
        if(front == saikoro[3]) return saikoro[4];
        if(front == saikoro[4]) return saikoro[2];
    }
    return 0;
}


Measured memory_bytes: 2108
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef long long ll;
const long long MOD=1e09+7;



#define rep(i,n) for(int i=0;i<n;i++)
#define rep2(i,m,n) for(int i=m;i<n;i++)
#define ALL(v) v.begin(), v.end()
#define pb push_back



ll factorial(ll x, ll n){
  if (n==0){
    return 1;
  }
  if (n==1){
    return x%MOD;
  }
  
  if (n%2==0){
    return (factorial(x,n/2)*factorial(x,n/2))%MOD;
  }
  
  if (n%2==1){
    return (((factorial(x,n/2)*factorial(x,n/2))%MOD)*x)%MOD;
  }
}






int main(){
  

  int x,y;
  cin>>x>>y;
  
  int answer=0;
  
  if ((x+y)%3!=0){
    answer=0;
  }
  
  else {
    int a,b;
    a=x-(x+y)/3;
    b=y-(x+y)/3;
    
    if (a>=0 and b>=0){
      vector<ll> combi(a+1);
      combi.at(0)=1;
      for (int i=1;i<=a;i++){
       combi.at(i)=(((combi.at(i-1)*factorial(i,MOD-2))%MOD)*(a+b-i+1))%MOD;
      }
      answer=combi.at(a);
    }
    else {
      answer=0;
    }
  }
    
      
  
  cout<<answer<<endl;
  

}




















Measured memory_bytes: 2816
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
typedef long double ld;
#define  all(v)     (v).begin(),(v).end()
#define  rall(v)    (v).rbegin(),(v).rend()
#define  pb         push_back
#define  eb         emplace_back
#define  mp         make_pair
#define  ff         first
#define  ss         second
#define  pf         push_front
#define  bs         binary_search
#define  lb         lower_bound
#define  ub         upper_bound
#define  dec(x)   fixed<<setprecision(x)
#define  lcm(a,b)   (a*b/__gcd(a,b))
const ll inf=LLONG_MAX;
const ll mod=1e9+7;
const ld pi=acos(-1);
                    
void solution(){
    string s,t;
    cin>>s>>t;
    ll ans=0;
    for(int i=0;i<s.size();i++){
        if(s[i]!=t[i]) ans++;
    }
    cout<<ans;
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    ll t;
    t=1;
    //cin>>t;
    while(t--){
        solution();
        cout<<"\n";
    }
    return 0;
}


Measured memory_bytes: 3808
# -*- coding: utf-8 -*-
import sys
import fractions
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
write = sys.stdout.write
def ii(): return int(readline())
def mi(): return map(int, readline().rstrip().split())
def li(): return list(readline().rstrip())
def lmi(): return list(map(int, readline().rstrip().split()))
def end(*arg): print(*arg); sys.exit()
# template


def main():
    A, B = mi()
    print(A * B // fractions.gcd(A, B))
    return


if __name__ == '__main__':
    main()


Measured memory_bytes: 66028
#include <iostream>
#include <algorithm>

using namespace std;
 
int main(){
    int w,d;
 
    while(cin >> w >> d , w | d){
	int left[w],right[d];
	for(int i = 0 ; i < w ; i++){
	    cin >> left[i];
	}
	for(int i = 0 ; i < d ; i++){
	    cin >> right[i];
	}
 
	sort(left,left+w);
	sort(right,right+d);
 
	int ans = 0;
	bool useW[w],useD[d];
	fill(useW,useW+w,true);
	fill(useD,useD+d,true);
 
	for(int i = 0 ; i < w ; i++){
	    for(int j = 0 ; j < d ; j++){
		if(left[i] == right[j] && useW[i] && useD[j]){
		    ans += left[i];
		    useW[i] = false;
		    useD[j] = false;
		}
	    }
	} 
 
	for(int i = 0 ; i < w ; i++){
	    if(useW[i]){
		ans += left[i];
	    }
	}
 
	for(int i = 0 ; i < d ; i++){
	    if(useD[i]){
		ans += right[i];
	    }
	}
	cout << ans << endl;
    } 
    return 0;
}

Measured memory_bytes: 3000
#include <stdio.h>

template <const unsigned int N, const unsigned int M>
struct shuumai{
    unsigned int size = 0;
    unsigned int minPrime[N + 1];
    unsigned long long int Prime[M];
    constexpr shuumai(void):minPrime(), Prime(), size(1){
        Prime[0] = 2; for(unsigned int i = 0; i <= N; i += 2) minPrime[i] = 2;
        for(unsigned int i = 3; i <= N; i += 2){
            if(!minPrime[i]){ minPrime[i] = i; Prime[size++] = i; }
            for(unsigned int j = 0; j < size and Prime[j] <= minPrime[i] and i * Prime[j] <= N; ++j){
                minPrime[i * Prime[j]] = Prime[j];
            }
        }
    }
};

constexpr unsigned int Size = 1e6;
constexpr unsigned int Count = 8e4;
constexpr shuumai<Size, Count> kawaii;

unsigned int size = 1;
unsigned long long int f[10000];


int main(void){
    f[0] = 1; unsigned long long int s = 2;

    unsigned long long int n; scanf("%llu", &n);
    if(n <= 2){ puts("0"); return 0; }
    unsigned long long int res = n - 1;

    const unsigned long long int N = n;

    for(unsigned int idx = 0; s * s <= n; s = kawaii.Prime[++idx]) if(!(n % s)){
        const unsigned int sz = size;
        unsigned long long int t = s;
        do{
            for(unsigned int i = 0; i < sz; ++i){

                unsigned long long int v = f[i] * t;
                unsigned long long int u = N / v;
                if(v < u - 1){ res += u - 1; f[size++] = v; }
            }
            n /= s;
            t *= s;
        } while(!(n % s));
    }
    if(n > 1){
        const unsigned int sz = size;
        for(unsigned int i = 0; i < sz; ++i){
            unsigned long long int v = f[i] * n;
            unsigned long long int u = N / v;
            if(v < u - 1){ res += u - 1; f[size++] = v; }
        }
    }

    printf("%llu\n", res);
     
    return 0;
}

Measured memory_bytes: 128
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
	long long n, m, ans = 0;
	cin >> n >> m;
	if(n >= (m / 2)){
		ans = min(n, m / 2);
	}else{
		ans = n + (m - 2 * n) / 4;
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
int main()
{
	std::string S;
	std::cin >> S;
	if (S == "SUN") {
		std::cout << "7" << std::endl;
	}
	if (S == "MON") {
		std::cout << "6" << std::endl;
	}
	if (S == "TUE") {
		std::cout << "5" << std::endl;
	}
	if (S == "WED") {
		std::cout << "4" << std::endl;
	}
	if (S == "THU") {
		std::cout << "3" << std::endl;
	}
	if (S == "FRI") {
		std::cout << "2" << std::endl;
	}
	if (S == "SAT") {
		std::cout << "1" << std::endl;
	}
}

Measured memory_bytes: 256
<?php
error_reporting(0);
//$N = explode(" ",trim(fgets(STDIN)));
//list($D,$X) = explode(" ",trim(fgets(STDIN)));
$N=trim(fgets(STDIN));
list($D,$X) = explode(" ",trim(fgets(STDIN)));
for($i=0;$i<$N;$i++) {
  $A[]=trim(fgets(STDIN));
}
$sum = 0;
foreach($A as $a) {
  $amari = $D % $a;
  if ($amari != 0) {
    $amari = 1;
  }
  if ($a == 1) {
    //日数分
    $sum += $D;
  }
  else {
    $sum += floor($D/$a)+$amari;
  }
}
printf("%d\n",$sum+$X);


Measured memory_bytes: 3828
#include <bits/stdc++.h>
#define rep(i, a, n) for(int (i) = (int)(a);(i) < (int)(n);++(i))
#define repe(i, a, n) for(int (i) = (int)(a);(i) <= (int)(n);++(i))
#define repif(i, a, x) for(int (i) = (int)(a);(x);++(i))
#define repr(i, a, n) for(int (i) = ((int)(a)-1);(i) >= (int)(n);--(i))
#define reper(i, a, n) for(int (i) = (int)(a);(i) >= (int)(n);--(i))
#define chmax(a, b) a = max(a, b)
#define chmin(a, b) a = min(a, b)
#define SIZE(x) ((int)(x).size())
#define ALL(x) (x).begin(), (x).end()
#define RNG(x, a, n) &((x)[a]), &((x)[n])
#define ADD(a, b) ((((a+MOD)%MOD)+((b+MOD)%MOD))%MOD)
#define MUL(a, b) ((((a)%MOD)*((b)%MOD))%MOD)
#define CEIL(x) ((int)ceil(((double)x)))
#define POW(x, y) ((int)pow(x, y))
#define UNIQUE(x) (x).erase(unique(ALL((x))), (x).end())
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define Yes cout << "Yes" << endl
#define No cout << "No" << endl
#define yes cout << "yes" << endl;
#define no cout << "no" << endl;
#define fcout cout << fixed << setprecision(10)
#define pb push_back
#define pf push_front
#define mp make_pair
#define mt make_tuple
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define PI 3.1415926535897
#define EPS (1e-10)
#define INF INT_MAX
#define INFLL LLONG_MAX
#define MOD 1000000007
using llint = long long;
using VI = std::vector<int>;
using PII = std::pair<int, int>;
using SI = std::set<int>;
using MII = std::map<int, int>;
using TIII = std::tuple<int, int, int>;
using MCI = std::map<char, int>;
using VPII = std::vector<PII>;
using namespace std;


int N;
int A, B;
int P[110];


int solve(){
	int x = 0, y = 0, z = 0;
	rep(i, 0, N){
		if(P[i] <= A) x++;
		else if(A+1 <= P[i] && P[i] <= B) y++;
		else if(B+1 <= P[i]) z++;
	}
	return min({ x, y, z });
}


signed main(){
	cin >> N;
	cin >> A >> B;
	rep(i, 0, N) cin >> P[i];
	
	cout << solve() << endl;

	return 0;
}

Measured memory_bytes: 256
n=int(input())
ab=[list(map(int,input().split())) for _ in range(n)]
ab.sort(key=lambda x:x[1])

time=0
for i in range(n):
  time+=ab[i][0]
  if time>ab[i][1]:
    print('No')
    break
else:
  print('Yes')

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

int main(){
    int a,b,c;
    cin >> a >> b >> c;
    
    if(a>b)
        swap(a,b);
    if(b>c)
        swap(b,c);
    if(a>b)
        swap(a,b);
    
    cout << a << " " << b << " " << c << endl;
}


Measured memory_bytes: 3100
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = Integer.parseInt(scanner.next());

        Integer[][] A = new Integer[N][2];
        for (int i = 0; i < N; i++) {
            A[i][0] = i;
            A[i][1] = Integer.parseInt(scanner.next());
        }
        scanner.close();

        // 値の降順ソート
        Arrays.sort(A, (a, b) -> b[1] - a[1]);

        int[] ans = new int[N];
        for (int i = 0; i < N; i++) {
            if (A[0][0] == i) {
                ans[i] = A[1][1];
            } else {
                ans[i] = A[0][1];
            }
        }

        for (int n : ans) {
            System.out.println(n);
        }
    }
}


Measured memory_bytes: 86692
n=int(input())
a=list(map(int,input().split()))
a.sort()
ans=[-1,0]
i=0
while i<=n-1:
    res=0
    cnt=0
    while i+res<=n-1 and a[i+res]-a[i]<=2:
        if a[i+res]==a[i]:
            cnt+=1
        res+=1
    if res>ans[1]:
        ans[1]=res
        ans[0]=i
    i+=cnt
print(ans[1])

Measured memory_bytes: 13964
#include <bits/stdc++.h>
using namespace std;
struct Fast { Fast() { cin.tie(0); ios::sync_with_stdio(false); cout << fixed << setprecision(20);} } fast;
 
long long mod = 1000000007;
 
long long div(long long a, long long b, long long c){
    return b / c - (a - 1) / c;
}
 
void print_binary(long long a) {
    for (int i = 31; i >= 0; i--) {
        cout << (a >> i & 1);
    }
    cout << endl;
}
long long modpow(long long m, long long n) {
    if (n == 0) return 1;
    if (n % 2 == 0) {
        long long t = modpow(m, n / 2);
        return t * t;
    } else {
        return modpow(m, n - 1) * m;
    }
}
 
int main() {
    long long n, w, k, ans = 0, c;
    cin >> n;
    vector<long> as(n);
    vector<long> bs(n);
    map<long, int>cnt;
    for (int i = 0; i < n; i++){
        cin >> as[i];
    }
    for (int i = 0; i < n; i++){
        cnt[as[i]]++;
        if (cnt[as[i]] == 2){
            bs[i] = as[i];
        }else if (cnt[as[i]] == 4){
            bs[i] = as[i];
        }
    }
    sort (bs.rbegin(), bs.rend());
    cout << bs[0] * bs[1] << endl;;
}

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

int main() {
  int n;
  ll k;
  cin >> n >> k;
  vector<int> a(n);
  vector<int> f(n);
  rep(i,n) cin >> a[i];
  rep(i,n) cin >> f[i];
  sort(a.begin(), a.end());
  sort(f.rbegin(), f.rend());
  ll l = -1, r = 1e12;
  while (l+1<r) {
    ll c = (l+r)/2;
    bool ok = [&]{
      ll s = 0;
      rep(i,n) {
        s += max(0ll, a[i]-c/f[i]);
      }
      return s <= k;
    }();
    if (ok) r = c; else l = c;
  }
  cout << r << endl;
  return 0;
}


Measured memory_bytes: 1792
cards = {
        'S': [0 for _ in range(13)],
        'H': [0 for _ in range(13)],
        'C': [0 for _ in range(13)],
        'D': [0 for _ in range(13)],
        }
  
n = int(input())
for _ in range(n):
    (s, r) = input().split()
    r = int(r)
    cards[s][r - 1] = r
  
for s in ('S', 'H', 'C', 'D'):
    for r in range(13):
        if cards[s][r] == 0:
            print( '{0:s} {1:d}'.format(s, r+1))

Measured memory_bytes: 6724
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vl vector<ll>
#define pl pair<ll,ll>
#define TC int t;cin>>t;while(t--)
#define in(n) ll n;cin>>n;
#define inarr(n) ll n;cin>>n;vector<ll>arr;
int main(void){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    in(x);in(k);in(d);
    x = (ll)fabs(x);
    ll div = x/d;
    ll mod = x%d;
    if(div<=k){
        k-=div;
        if(k&1){
            cout<<min((ll)fabs(mod-d),(ll)fabs(mod+d))<<endl;
        }
        else{
            cout<<mod<<endl;
        }
    }
    else{
        cout<<min(x+k*d,x-k*d)<<endl;
    }
    return 0;
}

Measured memory_bytes: 3648
def main():
    import sys
    readline = sys.stdin.readline

    s = readline().rstrip()
    t = readline().rstrip()

    dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

    for i, si in enumerate(s, 1):
        for j, tj in enumerate(t, 1):
            if si == tj:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    rest = dp[len(s)][len(t)]

    ret = ''
    i, j = len(s), len(t)

    while rest > 0:
        if dp[i][j] == dp[i - 1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j - 1]:
            j -= 1
        else:
            ret = s[i - 1] + ret
            rest -= 1
            i -= 1
            j -= 1

        # dp[i][j] == dp[i - 1][j - 1] + 1
        # かどうかを先に調べると、dp[i-1]/dp[j-1]のいずれかで既に+1になっているケースで間違う？

    print(ret)


if __name__ == '__main__':
    main()


Measured memory_bytes: 111964
#include<bits/stdc++.h>
using namespace std;
#define mkp make_pair
#define pb push_back
#define pf push_front
#define ins .insert
#define all(s) s.begin(),s.end()
/*
1、看的快，也要抓住关键点，看错题就不可能做对了；
2、只要WA，就赶紧题目看一遍
*/
typedef long long ll;
typedef map<int,int> mpii;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	vector<pair<int,int>> aa,bb;
	for(int i=0;i<a;i++){int k;cin>>k;aa.pb(mkp(k,i));}
	for(int i=0;i<b;i++){int k;cin>>k;bb.pb(mkp(k,i));}
	map<pair<int,int>,int> mp;
	for(int i=0;i<c;i++){int x,y,z;cin>>x>>y>>z;x--;y--;mp[mkp(x,y)] = max(mp[mkp(x,y)],z);}
	ll sum = 1e9;
	pair<int,int> kk;
	for(map<pair<int,int>,int>::iterator it = mp.begin();it!=mp.end();it++)
	{
		if(aa[it->first.first].first+bb[it->first.second].first-it->second<sum)
		{
			sum = aa[it->first.first].first+bb[it->first.second].first-it->second;
			kk = it->first;
		}
	}
	sort(all(aa));sort(all(bb));
	ll fen = aa[0].first+bb[0].first-mp[mkp(aa[0].second,bb[0].second)];
	fen = min(sum,fen);
	cout<<fen<<endl;
	return 0;
}

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

int main() {
	int n;
	cin>>n;
	int x;
	int b[100001]={};
	for (int i=0; i<n; i++){
		cin>>x;
		if (x>0) b[x-1]++;
		b[x]++;
		b[x+1]++;
	}
	int z=0;
	for (int i=0; i<100001; i++){
		z = max(z, b[i]);
	}
	cout << z;
	

}

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

int main(){
	ll W,H,c,res=0;
	cin>>W>>H;
	vector< pair<ll,bool> > v(W+H);
	rep(i,W+H){
		cin>>c;
		v[i]={c,i<W};
	}
	sort(v.begin(),v.end());
	W++;H++;
	for(auto t:v){
		if(t.second){
			res+=t.first*H;
			W--;
		}else{
			res+=t.first*W;
			H--;
		}
	}
	cout<<res<<endl;
	return 0;
}


Measured memory_bytes: 3328
#include <bits/stdc++.h>
using namespace std;
 
 
#define     ff first
#define     ss second
#define     ll long long
#define     ld long double
#define     pb push_back
#define     MOD 1000000007
 
 
 
/*      author:- Indrajit Sen
        Institution:- Jalpaiguri Government Engineering College
        id:- @Is97
                                                                */
                                                                
                                                                
 
 
int main(){
    
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL);
   
   string s;
   cin>>s;
   string week[]={"","MON", "TUE", "WED", "THU", "FRI", "SAT","SUN"};
   int ind;
    for(int i=0;i<8;i++){
        if(s==week[i]){
            ind=i;
            break;
        }
    }
    int ans=7-ind;
    if(ans==0){
        ans+=7;
    }
    cout<<ans<<endl;
    
    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#define llint long long
#define mod 1000000007

using namespace std;

llint n;
llint mean, mean2;

const int FACT_MAX = 200005;
llint fact[FACT_MAX], fact_inv[FACT_MAX];

llint modpow(llint a, llint n)
{
	if(n == 0) return 1;
	if(n % 2){
		return ((a%mod) * (modpow(a, n-1)%mod)) % mod;
	}
	else{
		return modpow((a*a)%mod, n/2) % mod;
	}
}

void make_fact()
{
	llint val = 1;
	fact[0] = 1;
	for(int i = 1; i < FACT_MAX; i++){
		val *= i;
		val %= mod;
		fact[i] = val;
	}
	fact_inv[FACT_MAX-1] = modpow(fact[FACT_MAX-1], mod-2);
	for(int i = FACT_MAX-2; i >= 0; i--){
		fact_inv[i] = fact_inv[i+1] * (i+1) % mod;
	}
}

llint comb(llint n, llint k)
{
	llint ret = 1;
	ret *= fact[n];
	ret *= fact_inv[k], ret %= mod;
	ret *= fact_inv[n-k], ret %= mod;
	return ret;
}

int main(void)
{
	cin >> n;
	make_fact();
	
	for(int i = 1; i <= n; i++){
		mean += comb(n-1, i-1) * fact_inv[i] % mod;
		mean %= mod;
	}
	for(int i = 1; i <= n; i++){
		mean2 += comb(n+i-1, 2*i-1) * fact_inv[i] % mod;
		mean2 %= mod;
	}
	
	llint ans = mean2 - mean*mean%mod + mod; ans %= mod;
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 6244
#!/usr/bin/env python3
# import sys
# sys.recursionlimit(10**7)
from functools import reduce

def divideCount(k):
    cnt = 0
    while k % 2 == 0:
        k //= 2
        cnt += 1
    return cnt

def solve(a):
    return sum(
        map(
            divideCount,a
        )
    )


def main():
    _ = int(input())
    a = list(map(int,input().split()))
    print('{}'.format(solve(a)))




if __name__ == '__main__':
  main()


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

using namespace std;
int n,m;
int main(int argc, char const *argv[]) {
        cin >> ::n >> ::m;
        int vec1[n][m] = {0};
        int vec2[m] = {0};
        int result[n] = {0};
        for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                        cin >> vec1[i][j];
                }
        }
        for(int i = 0; i < m; i++) cin >> vec2[i];

        for(int i = 0; i < n; i++) {
                for(int j = 0; j < m; j++) {
                        result[i] += vec1[i][j]*vec2[j];
                }
        }
        for(int i = 0; i < n; i++) {
                cout << result[i] << '\n';
        }
        return 0;
}



Measured memory_bytes: 3108
#include <bits/stdc++.h>
#define P 1000000007

using namespace std;

typedef long long ll;

int n, m;

char ch[400010];

ll powmod(ll x, ll y = P - 2, ll p = P) {
	ll ans = 1;
	while(y) {
		if(y & 1) ans = ans * x % p;
		x = x * x % p;
		y >>= 1;
	}
	return ans;
}

ll F[400010][2][2], G[400010][2][2], H[400010], SH[400010], SG[400010][2][2];

// G1 : ABABABA
// G2 : BABABAB

void cmin(int &x, int y) {if(x > y) x = y;}

void add(ll &x, ll y) {x = (x + y) % P;}

int main() {
	scanf("%d%d", &n, &m);
	scanf("%s", ch + 1);
	ll ans = 0;
	// qingyise
	int sub1 = 1;
	for(int i = 2; i <= m; i++) if(ch[i] != ch[1]) sub1 = 0;
	if(sub1 == 1) {
		F[0][0][0] = 1;
		F[0][1][1] = 1;
		for(int i = 1; i <= n; i++)
			for(int j = 0; j < 2; j++) {
				F[i][j][0] = (F[i - 1][j][0] + F[i - 1][j][1]) % P;
				F[i][j][1] = (F[i - 1][j][0]) % P;
			}
		ans = (F[n][0][0] + F[n][1][1]) % P;
		printf("%lld\n", (ans % P + P) % P);
		return 0;
	}
	if(n % 2 == 1) {
		puts("0");
		return 0;
	}
	vector <int> V(1, 1);
	for(int i = 2; i <= m; i++) if(ch[i] == ch[i - 1]) V.back()++; else V.push_back(1);
	int l = 0, r = 0, mnA = n + 5, mnB = n + 5, nw = 0;
	for(int i = 1; i < V.size(); i += 2) {
		if(V[i] % 2 == 1) nw ^= 1;
		if(i + 2 != V.size() && V[i + 1] % 2 == 1) {
			if(nw == 0) cmin(mnA, V[i + 1]); else cmin(mnB, V[i + 1]);
		}
	}
	cmin(mnA, V[0] + !(V[0] % 2));
	H[1] = 1, SH[1] = 1;
	for(int i = 3; i <= n + 1; i += 2) {
		H[i] = SH[i - 2];
		if(i >= min(mnA, mnB) + 3) {
			add(H[i], -SH[i - (min(mnA, mnB) + 3)]);
		}
		//H[i] = -H[i];
		SH[i] = (H[i] + SH[i - 2]) % P;
	}
	for(int i = 1; i <= n; i += 2) {
		//if(n - i <= mnA) add(ans, G[i][1][1] * (n - i + 1));
		//if(n - i <= mnB) add(ans, G[i][0][0] * (n - i + 1));
		if(n - i <= min(mnA, mnB)) add(ans, H[i] * (n - i + 1));
	}
	printf("%lld\n", (ans % P + P) % P);
	return 0;
}

Measured memory_bytes: 8576
A = int(input())
B = int(input())
C = int(input())
X = int(input())

ans = 0

for i in range(A + 1):
    for j in range(B + 1):
        for k in range(C + 1):
            if i * 500 + j * 100 + k * 50 == X:
                ans += 1
print(ans)


Measured memory_bytes: 3060
N = int(input())
T = list(map(int,input().split()))
M = int(input())
P1 = range(M)
P = list(P1)
X1 = range(M)
X = list(X1)
for i in range(0,M):
    P[i],X[i] = map(int,input().split())
    moto = T[P[i]-1]
    T[P[i]-1] = X[i]
    print(sum(T))
    T[P[i]-1] = moto

Measured memory_bytes: 3064
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const int INF = 1e9;
const int MOD = 1e9+7;
using Graph = vector<vector<ll>>;
template<class T> inline bool chmin(T &a, T b) { if(a > b){ a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b) { if(a < b){ a = b; return true;} return false;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll n; cin >> n;
    vector<ll> vec(n+1);
    rep(i, n+1){
        cin >> vec[i];
    }

    if(n == 0){
        if(vec[0] == 1){
            cout << 1 << endl;
            return 0;
        }else{
            cout << -1 << endl;
            return 0;
        }
    }

    vector<ll> vec_reverse(n+1);
    vec_reverse = vec;
    reverse(all(vec_reverse));

    
    vector<pair<ll,ll>> node_num(n+1);

    rep(i, n+1){
        if(i == 0){
            node_num[n-i] = make_pair(vec_reverse[i], vec_reverse[i]);
            continue;
        }
        ll saisyo = vec_reverse[i] + (node_num[n-i+1].first + 1) / 2;
        ll saidai = vec_reverse[i] + node_num[n-i+1].second;
        node_num[n-i] = make_pair(saisyo, saidai);
    }

    if(node_num[0].first > 1){
        cout << -1 << endl;
        return 0;
    }

    ll ans = 0;
    ll now_node = 0;
    rep(i, n+1){
        if(i == 0){
            ans += 1;
            now_node = 1;
            continue;
        }
        ll tmp = min((now_node - vec[i-1]) * 2, node_num[i].second);
        ans += tmp;
        now_node = tmp;
    }

    cout << ans << endl;
    
    

}

Measured memory_bytes: 6364
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
int main(){
  int N;
  cin>>N;
  int H[N];
  for(int i=0;i<N;i++) cin>>H[i];
  for(int i=N-1;i>=0;i--){
    if(H[i]<H[i-1]-1){
      cout<<"No"<<endl;
      break;
    }else if(H[i]<H[i-1]) H[i-1]--;
    if(i==0) cout<<"Yes"<<endl;
  }
}


Measured memory_bytes: 640
n=int(input())
a=[]
for i in range(n):
    ai=int(input())
    a.append(ai)

ans1=max(a)
for i in range(n):
    if a[i]==ans1:
        a[i]=0
        point=i
        break
b=[ans1]
b*=n
ans2=max(a)
b[point]=ans2
for i in range(n):
    print(b[i])

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

int n;
ll k;
vector<pair<int, int>> x;

void solve() {
  int i = 0;

  sort(x.begin(), x.end());

  while (k > 0) {
    k -= x[i].second;
    if (k > 0) {
      i++;
    }
  }

  cout << x[i].first << "\n";
}

int main() {
  int i;

  cin >> n >> k;

  x.resize(n);
  for (i = 0; i < n; i++) {
    cin >> x[i].first >> x[i].second;
  }

  solve();

  return 0;
}


Measured memory_bytes: 1024
a = int(input())
b = int(input())
c = int(input())
x = int(input())
 
ans = 0
 
for ai in range(a+1):
    for bi in range(b+1):
        for ci in range(c+1):
            amount = 500 * ai + 100 * bi + 50 * ci
            if amount == x:
                ans += 1
 
print(ans)

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

Measured memory_bytes: 600