akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
using pll = pair<ll, ll>;

const ll oo = 0x3f3f3f3f3f3f3f3fLL;
const double eps = 1e-9;

#define sz(c) ll((c).size())
#define all(c) begin(c), end(c)
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define eb emplace_back
#define xx first
#define yy second
#define FOR(i, a, b) for (ll i = (a); i < (b); i++)
#define FORD(i, a, b) for (ll i = ll(b) - 1; i >= (a); i--)
#define TR(X)                                                  \
    ({                                                         \
        if (1) cerr << "TR: " << (#X) << " = " << (X) << endl; \
    })

constexpr ll MOD = 998244353ll;

ll exp(ll a, ll n) {
    ll res = 1;
    for (ll acc = a; n; acc = (acc*acc) % MOD, n>>=1) {
        if (n & 1) {
            res = (res * acc) % MOD;
        }
    }
    return res;
}

struct binom {
    vl fac, ifac;
    binom(ll N) : fac(N+1), ifac(N+1) {
        fac[0] = 1;
        FOR(i, 1, N+1) fac[i] = (fac[i-1] * i) % MOD;
        ifac[N] = exp(fac[N], MOD-2);
        FORD(i, 0, N) ifac[i] = (ifac[i+1] * (i+1)) % MOD;
    }

    ll get(ll n, ll k) {
        return (((fac[n] * ifac[k]) % MOD) * ifac[n-k]) % MOD;
    }
};

int main() { cin.sync_with_stdio(0);
    ll N, M, K; cin >> N >> M >> K;
    binom b(N);

    ll ans = 0;
    FOR(i, 0, K+1) {
        ans += ((b.get(N-1, i) * M) % MOD) * exp(M-1, N-1-i);
        ans %= MOD;
    }
    cout << ans << endl;
}  // cin.tie(0) bei schnellem Wechseln


Measured memory_bytes: 6360
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        String[] array = br.readLine().split("");
        long bi = 0;
        int bc = 0;
        long s = array.length;
        for (int i = 0; i < s; i++) {
            if (array[i].equals("B")) {
                bi += i;
                bc++;
            } 
        }
        long m = 0;
        for (int i = 0; i < bc; i++) {
            m += s - i - 1;
        }
        out.println(m - bi);
        out.close();
    }
}


Measured memory_bytes: 37992
def ii():
    return int(input())
def mi():
    return map(int, input().split())
def li():
    return list(mi())

n = ii()
a = []
for i in range(n):
    x, y = mi()
    a.append((x + y, x, y))
a.sort(reverse=True)
ans = 0
for i in range(n):
    if i % 2: ans -= a[i][2]
    else: ans += a[i][1]
print(ans)


Measured memory_bytes: 20988
#include<bits/stdc++.h>
using namespace std;
 
 int N, X;
 int m[1000];

 int A, B;
 int MIN;
 int ans;
 
 int main(){ 


  cin >> N >> X;
 
  for ( int i = 1; i <= N; i++ ){
   cin >> m[i];
  }

  for ( int i = 1; i <= N; i++ ){
   A = A + m[i]; 
  }

  sort (m, m+N+1);

  MIN = m[1];


  B = (X - A) / MIN;

  ans = N+B; 
  cout << ans << endl;


 return 0;
}


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

using namespace std;

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

    int ans = n/(d*2+1);

    if(n%(d*2+1)!=0) cout << ans+1 << "\n";
    else cout << ans << "\n";

    return 0;
}


Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

const (
	plus  = "+"
	minus = "-"
	multi = "*"
	div   = "/"
)

var scan = bufio.NewScanner(os.Stdin)

func main() {
	scanWords()

	for {
		a := readNextInt()
		op := readNextString()
		b := readNextInt()

		if op == "?" {
			break
		}

		answer := executeOperator(a, b, op)
		fmt.Println(answer)
	}
}

func executeOperator(a, b int, op string) int {
	switch op {
	case plus:
		return a + b
	case minus:
		return a - b
	case multi:
		return a * b
	case div:
		return a / b
	default:
		panic("unknow operation")
	}
}

func scanWords() {
	scan.Split(bufio.ScanWords)
}

func readNextInt() int {
	input, err := strconv.Atoi(readNextString())
	if err != nil {
		panic(err)
	}
	return input
}

func readNextString() string {
	scan.Scan()
	return scan.Text()
}



Measured memory_bytes: 1092
#include <bits/stdc++.h>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

vector<string> split(const string &s, char delim) {
  vector<string> elems;
  string item;
  for (char ch: s) {
    if (ch == delim) {
      if (!item.empty()) {
        elems.push_back(item);
      }
      item.clear();
    }
    else {
      item += ch;
    }
  }
  if (!item.empty()) {
    elems.push_back(item);
  }
  return elems;
}

string to_str_with_zero(int i, int w) {
  ostringstream sout;
  sout << std::setfill('0') << std::setw(w) << i;
  string s = sout.str();
  return s;
}

int letter_to_int(char c) {
  return tolower(c) - 'a';
}

int compare_array(vector<int> a1, vector<int>a2) {
  int n1 = a1.size();
  int n2 = a2.size();
  if (n1 != n2) {
    return n1 - n2;
  }
  for (int i=0; i<n1; i++) {
    if (a1.at(i) != a2.at(i)) {
      return a1.at(i) - a2.at(i);
    }
  }
  return 0;
}

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

char int_to_char(int a) {
  if (a == -1) {
    return 'z';
  }
  else {
    return 'a' + a;
  }
}

long nCr(int n, int r) {
    long ans = 1;
    for (int i = n; i > n - r; --i) {
        ans = ans*i;
    }
    for (int i = 1 ; i < r + 1; ++i) {
        ans = ans / i;
    }
    return ans;
}

long modinv(long long a, long long m) {
    long long b = m, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b; swap(a, b);
        u -= t * v; swap(u, v);
    }
    u %= m; 
    if (u < 0) u += m;
    return u;
}

int divide_count(int a, int divider) {
  int r = 0;
  while(a % divider == 0) {
    a /= divider;
    r++;
  }
  return r;
}

bool is_prime(int a) {
  int i = 2;
  while(i * i <= a) {
    if(a % i == 0) {
      return false;
    }
    i++;
  }
  return true;
}

vector<vector<int>> all_comb(int n, int k) {
  vector<vector<int>> combs(nCr(n, k), vector<int>(k));
  for(int i=0; i<k; i++) {
    combs[0][i] = i;
    combs[1][i] = i;
  }
  
  for(long i=1; i<nCr(n, k); i++) {
    int p = 1;
    while(combs[i][k - p] == n - p) {
      p++;
      if(p > k) {
        break;
      }
    }
    combs[i][k - p]++;
    int q = combs[i][k - p];
    for(int j=1; j<p; j++) {
      combs[i][k - p + j] = q + j;
    }

    if(i < nCr(n, k) - 1) {
      for(int j=0; j<k; j++) {
        combs[i + 1][j] = combs[i][j];
      }
    }
  }

  return combs;
}

template <typename TYPE> void co(TYPE a) {
  cout << a << endl;
}

template <typename TYPE> void co_2(TYPE a, TYPE b) {
  cout << a << ' ' << b << endl;
}

template <typename TYPE> void co_l(vector<TYPE> as) {
  int n = as.size();
  for(int i=0; i<n; i++) {
    cout << as[i] << endl;
  }
}

template <typename TYPE> void co_s(vector<TYPE> as) {
  int n = as.size();
  for(int i=0; i<n; i++) {
    if(i > 0) {
      cout << ' ';
    }
    cout << as[i];
  }
  cout << endl;
}

int main() {
  std::cout << std::setprecision(9);
  long mod = 1000000007;
  int n, x, t;
  cin >> n >> x >> t;
  int count = n / x;
  if(n % x != 0) {
    count++;
  }
  cout << count * t << endl;
}

Measured memory_bytes: 3616
#include <iostream>
using namespace std;
int main(void){
    int m,f,r;
    
    while(1){
        cin >> m >> f >> r;
        
        if(m == -1 && f == -1 && r == -1)break;
        else if(m == -1 || f == -1 || m+f < 30)cout << "F" << endl;
        else if(m+f >= 80)cout << "A" << endl;
        else if(m+f < 80 && m+f >= 65)cout << "B" << endl;
        else if(m+f < 50 && m+f >= 30 && r < 50)cout << "D" << endl;
        else cout << "C" << endl;
    }
    return 0;
}



Measured memory_bytes: 3112
import java.util.*;
import java.io.PrintWriter;
public class Main{
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int n=sc.nextInt();
		int[] rec=new int[200000];
		Arrays.fill(rec,n);
		long[] dp=new long[n+1];
		long mod=1000000007;
		dp[0]=1;
		for(int i=1; i<=n; i++){
			int c=sc.nextInt()-1;
			if(rec[c]<i-1){
				dp[i]=dp[rec[c]];
			}
			dp[i]+=dp[i-1];
			dp[i]%=mod;
			rec[c]=i;
		}
		System.out.println(dp[n]);
	}
}


Measured memory_bytes: 87280
n = int(input())
a = list(map(int, input().split()))
p = 1000000007
 
y = 0
for i in range(n):
    y += a[i]
    y = y % (2 * p)
y = (y ** 2) % (2 * p)
 
x = 0
for j in range(n):
    x += a[j] ** 2
    x = x % (2 * p)
 
z = int(((y - x) / 2) % p)
print(z)

Measured memory_bytes: 31604
from itertools import *
N = int(input())
H = []
A = []

for i in range(N):
  for j in range(int(input())):
    x,y = map(int, input().split())
    H+=[[i,x-1,y]]

for P in product([0,1],repeat=N):
  for h in H:
    if P[h[0]]==1 and P[h[1]]!=h[2]:
      break
  else:
    A+=[sum(P)]

print(max(A))

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b;
    cin>>a>>b;
    int c = (a+b)/2;
    if(abs(a-c)==abs(b-c)) cout<<c;
    else cout<<"IMPOSSIBLE";
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=1;i<=n;i++)
# define ALL(x) (x).begin(), (x).end()
# define SZ(x) ((int)(x).size())
# define pb push_back
using namespace std;

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

long long lcm(long long a,long long b){
    return a*b/gcd(a,b);
}
    
int main(){
    long long a,b;
    cin>>a>>b;
    cout<<lcm(a,b)<<endl;
    return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules ! input { ( source = $ s : expr , $ ( $ r : tt ) * ) => { let mut iter = $ s . split_whitespace ( ) ; let mut next = || { iter . next ( ) . unwrap ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; ( $ ( $ r : tt ) * ) => { let stdin = std :: io :: stdin ( ) ; let mut bytes = std :: io :: Read :: bytes ( stdin . lock ( ) ) ; let mut next = move || -> String { bytes . by_ref ( ) . map ( | r | r . unwrap ( ) as char ) . skip_while ( | c | c . is_whitespace ( ) ) . take_while ( | c |! c . is_whitespace ( ) ) . collect ( ) } ; input_inner ! { next , $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! input_inner { ( $ next : expr ) => { } ; ( $ next : expr , ) => { } ; ( $ next : expr , mut $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let mut $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; ( $ next : expr , $ var : ident : $ t : tt $ ( $ r : tt ) * ) => { let $ var = read_value ! ( $ next , $ t ) ; input_inner ! { $ next $ ( $ r ) * } } ; }
#[allow(unused_macros)]
macro_rules ! read_value { ( $ next : expr , ( $ ( $ t : tt ) ,* ) ) => { ( $ ( read_value ! ( $ next , $ t ) ) ,* ) } ; ( $ next : expr , [ $ t : tt ; $ len : expr ] ) => { ( 0 ..$ len ) . map ( | _ | read_value ! ( $ next , $ t ) ) . collect ::< Vec < _ >> ( ) } ; ( $ next : expr , chars ) => { read_value ! ( $ next , String ) . chars ( ) . collect ::< Vec < char >> ( ) } ; ( $ next : expr , usize1 ) => { read_value ! ( $ next , usize ) - 1 } ; ( $ next : expr , $ t : ty ) => { $ next ( ) . parse ::<$ t > ( ) . expect ( "Parse error" ) } ; }

#[allow(unused_macros)]
macro_rules ! vec_md { ( $ init : expr ; $ ( $ dim : expr ) ;* ) => { vec_md ! ( $ ( $ dim ) ;* => $ init ) } ; ( $ head : expr ; $ ( $ tail : expr ) ;* => $ init : expr ) => { vec ! [ vec_md ! ( $ ( $ tail ) ;* => $ init ) ; $ head ] } ; ( $ head : expr => $ init : expr ) => { vec ! [ $ init ; $ head ] } ; }

fn main() {
    input! {
        a: usize, b: usize, c: usize, d: usize, e: usize, f: usize
    }

    let mut dp = vec_md![false;f+1;f+1];
    dp[0][0] = true;
    for i in 0..dp.len() {
        for j in 0..dp[0].len() {
            if i+100*a<dp.len() {
                dp[i+100*a][j] |= dp[i][j];
            }
            if i+100*b<dp.len() {
                dp[i+100*b][j] |= dp[i][j];
            }
            if j+c<dp[0].len() {
                dp[i][j+c] |= dp[i][j];
            }
            if j+d<dp[0].len() {
                dp[i][j+d] |= dp[i][j];
            }
        }
    }
    let mut water = 0;
    let mut sugar = 0;
    for i in 0..dp.len() {
        for j in 0..dp[0].len() {
            if i+j<=f && dp[i][j] && i*e>=100*j && (water==0&&sugar==0 || dens(i,j)>dens(water,sugar)) {
                water=i;
                sugar=j;
            }
        }
    }
    println!("{} {}", water+sugar,sugar);
}

fn dens(water: usize, sugar: usize) -> f64 {
    sugar as f64 / (water + sugar) as f64
}


Measured memory_bytes: 12540
import math
import sys
from functools import reduce
input = sys.stdin.readline

def fullsearch(a):
    for i in range(-100, 101):
        yield reduce(lambda total, x: (x - i) ** 2 + total, a, 0)

def main():
    input()
    A = [int(c) for c in input().split()]

    print(min(fullsearch(A)))

main()

Measured memory_bytes: 3572
#include <bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define INF 1234567890
#define pii pair<int,int>
#define LL long long
using namespace std;

int main () {
    //clock_t start = clock();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    cin >> n;
    int ans = n%1000;
    if (ans == 0) ans = 1000;
    cout << 1000-ans << endl;
    //cerr << fixed << setprecision(3) << (clock()-start)*1./CLOCKS_PER_SEC << endl;
    return 0;
}

Measured memory_bytes: 3576
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

from heapq import heappop, heappush


def main():
    n, m = map(int, input().split())
    edges = [[] for _ in range(n)]
    for i in range(1, n):
        edges[i] = [(i - 1, 0)]
    
    lrc = [tuple(map(int, input().split())) for _ in range(m)]
    for l, r, c in lrc:
        edges[l - 1].append((r - 1, c))

    d = [float("inf") for _ in range(n)]
    d[0] = 0
    h = [(0, 0)]
    while len(h) > 0:
        tmpd, tmpi = heappop(h)
        for toi, tod in edges[tmpi]:
            if d[toi] > tmpd + tod:
                d[toi] = tmpd + tod
                heappush(h, (d[toi], toi))
    
    if d[n - 1] == float("inf"):
        print(-1)
    else:
        print(d[n - 1])
    


if __name__ == '__main__':
    main()


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

int main(int argc, char const *argv[]) {
    int x, y;
    cin >> x >> y;

    for (int i = 0; i <= x; i++) {
        int legs = 2*i + 4*(x-i);
        if (legs == y) {
            cout << "Yes" << endl;
            return 0;
        }
    }

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


Measured memory_bytes: 3632
fun main(args: Array<String>) {
    solve(java.util.Scanner(System.`in`))
}

fun solve(sc: java.util.Scanner) {
    val H = sc.nextInt()
    val W = sc.nextInt()
    val S = Array(H) { sc.next().toCharArray() }

    val A = Array(H) { IntArray(W) }
    for (h in 0 until H) {
        for (w in 0 until W) {
            val prev = mutableListOf<Pair<Int, Int>>()
            if (h > 0) prev.add(Pair(h - 1, w))
            if (w > 0) prev.add(Pair(h, w - 1))
            if (prev.isNotEmpty()) {
                A[h][w] = prev.map {
                    A[it.first][it.second] + if (S[it.first][it.second] == S[h][w]) 0 else 1
                }.min()!!
            }
        }
    }
    val result = (A[H - 1][W - 1] + (if (S[0][0] == '#') 1 else 0) + (if (S[H - 1][W - 1] == '#') 1 else 0)) / 2
    println(result)
}


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

int main() {
  string s, t;
  cin >> s;
  cin >> t;

  string ans = "No";

  if(s.size() < t.size()) {
    if(t.find(s) != std::string::npos)
      ans = "Yes";
  }

  for(int i=0; i<s.size(); i++) {
    for(int j=0; j<t.size(); j++) {
      if(s[i] < t[j]) {
        ans = "Yes";
        break;
      }
    }
  }

  cout << ans << endl;
}

Measured memory_bytes: 256
num = 0
while num < 10000 :
    s = input().split()
    if s[0] == "0" and s[1] == "0":
        break
    if int(s[0]) > int(s[1]):
        x = s[1]
        y = s[0]
    else:
        x = s[0]
        y = s[1]
    print(x, y)
    num += 1



Measured memory_bytes: 5612
# AGC040A - ><
from itertools import groupby


def main():
    S = input().rstrip()
    ans, prev = 0, 0
    for sign, g in groupby(S):
        cnt = len(tuple(g))
        ans += cnt * (cnt + 1) // 2
        if sign == ">":
            ans -= min(cnt, prev)
        prev = cnt
    print(ans)


if __name__ == "__main__":
    main()

Measured memory_bytes: 8840
N = int(input())
a_lst = [int(x) for x in input().split()]
b_lst = []
for i in a_lst:
    b_lst.append(i)

def my_sign(num):
    return (num > 0) - (num < 0)

cnt_p = 0
cnt_n = 0
sum_lst = []
sum2_lst = []

for i in range(N): #偶数でマイナス、奇数でプラスの和
    sum_lst.append(a_lst[i]) if i == 0 else sum_lst.append(a_lst[i] + sum_lst[i - 1])
    if i%2 == 0 and sum_lst[i] >= 0:
        cnt_p += 1 + sum_lst[i]
        a_lst[i] -= 1 + sum_lst[i]
        sum_lst[i] = -1
    elif i%2 == 1 and sum_lst[i] <= 0:
        cnt_p += 1 + abs(sum_lst[i])
        a_lst[i] += 1 + abs(sum_lst[i])
        sum_lst[i] = 1
for i in range(N): #偶数でプラス、奇数でマイナスの和
    sum2_lst.append(b_lst[i]) if i == 0 else sum2_lst.append(b_lst[i] + sum2_lst[i - 1])
    if i%2 == 0 and sum2_lst[i] <= 0:
        cnt_n += 1 + abs(sum2_lst[i])
        b_lst[i] += 1 + abs(sum2_lst[i])
        sum2_lst[i] = 1
    elif i%2 == 1 and sum2_lst[i] >= 0:
        cnt_n += 1 + sum2_lst[i]
        b_lst[i] -= 1 + sum2_lst[i]
        sum2_lst[i] = -1
print(min(cnt_p, cnt_n))


Measured memory_bytes: 14332
#include <cstdio>

using namespace std;

int a[109];

int main() {
  int n;
  scanf("%d", &n);
  for (int i = 0; i < n; ++i) {
    scanf("%d", a + i);
  }
  int ans = 1'000'000'000;
  for (int i = 1; i <= 100; ++i) {
    int cur = 0;
    for (int j = 0; j < n; ++j) {
      cur += (a[j] - i) * (a[j] - i);
    }
    if (cur < ans) {
      ans = cur;
    }
  }
  printf("%d\n", ans);
}


Measured memory_bytes: 128
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

struct state {
	int h;
	long long ans1 = 2;
	long long ans2 = 0;
	
	state(int h) : h(h) {}
};

int n, m = 1000000007;
int h[100];

long long powmod(long long x, long long y) {
	long long ans = 1;
	
	while (y > 0) {
		if (y & 1) ans = ans * x % m;
		x = x * x % m;
		y >>= 1;
	}
	
	return ans;
}

long long mod_inverse(long long a, long long m) {
    long long b = m, x = 1, y = 0;
    
    while (b) {
        long long t = a / b;
        
        a -= t * b;
        x -= t * y;
        
        swap(a, b);
        swap(x, y);
    }
    
    return (m + x % m) % m;
}

long long solve() {
	int i, j;
	vector <state> v;
	
	v.push_back(state(0));
	
	for (i = 0; i < n; i++) {
		v.push_back(state(h[i]));
	}
	
	v.push_back(state(0));
	
	while (v.size() > 3) {
		int x = 0;
		
		for (i = 0; i < v.size(); i++) {
			if (v[i].h > v[x].h) x = i;
		}
		
		if (v[x].h == v[x + 1].h) {
			long long tmp1, tmp2;
			
			tmp1 = v[x].ans1 * v[x + 1].ans1 % m * mod_inverse(2, m) % m;
			tmp2 = ((v[x].ans1 + v[x].ans2) * (v[x + 1].ans1 + v[x + 1].ans2) - tmp1 + m) % m;
			
			v[x].ans1 = tmp1;
			v[x].ans2 = tmp2;
			v.erase(v.begin() + x + 1);
		} else {
			int h = v[x].h - max(v[x - 1].h, v[x + 1].h);
			
            v[x].ans1 = v[x].ans1 * powmod(2, h) % m;
			v[x].h -= h;
		}
	}
	
	return (v[1].ans1 * powmod(2, v[1].h - 1) % m + v[1].ans2) % m;
}

int main() {
	int i;
	
	scanf("%d", &n);
	
	for (i = 0; i < n; i++) scanf("%d", &h[i]);
	
	printf("%lld\n", solve());
	
	return 0;
}


Measured memory_bytes: 256
#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
#include <set>
#include <iomanip>
#include <queue>
#include <string>
#include <map>
#include <fstream>
#include <cassert>
#include <stack>
#include <climits>
#include <array>
#include <unordered_set>
#include <unordered_map>
#include <memory>
#include <functional>
#include <cfloat>
#include <numeric>
#include <atcoder/dsu>
struct Coordinate {
	int x, y;
};
int main() {
	int n; std::cin >> n;
	std::vector<Coordinate> coordinate(n);
	for (auto& c : coordinate) {
		std::cin >> c.x >> c.y;
	}
	atcoder::dsu uft(n);
	std::stack<std::pair<int, int>> stack;
	std::vector<int> indices(n); std::iota(indices.begin(), indices.end(), 0);
	std::sort(indices.begin(), indices.end(), [&](const int i, const int j) {return coordinate[i].x < coordinate[j].x; });
	int min_y_pos = indices.front();
	for (const auto i : indices) {
		if (coordinate[min_y_pos].y < coordinate[i].y) {
			uft.merge(min_y_pos, i);
		}
		else {
			stack.emplace(min_y_pos, coordinate[min_y_pos].y);
			min_y_pos = i;
		}
		while (!stack.empty() && stack.top().second <= coordinate[i].y) {
			uft.merge(i, stack.top().first);
			stack.pop();
		}
		stack.emplace(i, coordinate[i].y);
	}
	std::reverse(indices.begin(), indices.end());
	while (!stack.empty()) stack.pop();
	int max_y_pos = indices.front();
	for (const auto i : indices) {
		if (coordinate[max_y_pos].y > coordinate[i].y) {
			uft.merge(max_y_pos, i);
		}
		else {
			stack.emplace(max_y_pos, coordinate[max_y_pos].y);
			max_y_pos = i;
		}
		while (!stack.empty() && stack.top().second >= coordinate[i].y) {
			uft.merge(i, stack.top().first);
			stack.pop();
		}
		stack.emplace(i, coordinate[i].y);
	}
	for (auto i = 0; i < n; ++i) {
		std::cout << uft.size(i) << '\n';
	}
}


Measured memory_bytes: 7440
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <utility>
#include <tuple>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <cmath>
#include <iomanip>
#include <functional>
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define REP(i, n) for (int i = 1; i < (n); ++i)
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
using namespace std;
using ll = long long;
constexpr int inf = 1000000000;
constexpr ll INF = 3000000000000000000;

int main() {
    int a;
    cin >> a;
    cout << a + a * a + a * a * a << "\n";
    return 0;
}


Measured memory_bytes: 3588
#include <iostream>
#include <string>
#include <cmath>
#define EPS 1e-10
using namespace std;



int main ()
{
    string dir;
    while (cin >> dir, dir != "#") {
        string ins = "" ;
        for (int i = 0; i < dir.size(); i++) {
            ins += dir[i];
            if (dir[i] == 'n') i += 4;
            else i += 3;
        }

        double res = ins[ins.size() - 1] == 'n' ? 0.0 : 90.0;
        double d = 2.0;
        for (int i = ins.size() - 2; i >= 0; i--) {
            res += (ins[i] == 'n' ? -90.0 : 90.0) / d;
            d *= 2.0;
        }

        int t = 1;
        while (abs(res) > (int)((abs(res)))) {
            res *= 2;
            t *= 2;
        }

        if (t > 1) cout << (int)(abs(res)) << "/" << t << endl;
        else cout << (int)(abs(res)) << endl;
    }

    return 0;
}

Measured memory_bytes: 1200
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); i++)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; i--)
#define reps(i, n) for (int i = 1; i <= (n); i++)
#define repi(i, a, b) for (int i = (a); i < (b); i++)
#define all(a) (a).begin(), (a).end()
#define bit(b) (1ull << (b))

using namespace std;
using i32 = long long;
using u32 = unsigned long long;
using i64 = long long;
using u64 = unsigned long long;
using f64 = double;
using vi32 = vector<i32>;
using vu32 = vector<u32>;
using vi64 = vector<i64>;
using vu64 = vector<u64>;
using vf64 = vector<f64>;
using vstr = vector<string>;
using vvi32 = vector<vi32>;
using vvu32 = vector<vu32>;
using vvi64 = vector<vi64>;
using vvu64 = vector<vu64>;
using vvf64 = vector<vf64>;

template<typename T, typename S> void amax(T &x, S y) { if (x < y) x = y; }
template<typename T, typename S> void amin(T &x, S y) { if (y < x) x = y; }

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(16);
  string x;
  cin >> x;
  int n = x.size();
  int ans = 0;
  int s = 0, t = 0;
  bool b = false;
  rep(i, n) {
    if (!b && x[i] == 'S') {
      b = true;
      s++;
      continue;
    }
    if (b) {
      if (x[i] == 'S') {
        s++;
      } else {
        t++;
        if (s == t) {
          b = false;
          ans += s * 2;
          s = 0;
          t = 0;
        }
      }
    }
  }
  ans += min(s, t) * 2;
  cout << n - ans << endl;
  return 0;
}

Measured memory_bytes: 720
#include<bits/stdc++.h>
#define lli long long int
#define ulli unsigned long long int
#pragma GCC target ("sse4.2")
using namespace std;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define time cout<<"\nTime Elapsed: " << 1.0*clock() / CLOCKS_PER_SEC << " sec\n";

int main()
{


    lli n,r;
    cin>>n>>r;
    if(n>=10)
    {
        cout<<r;
    }
    else
    {
        cout<<r+100*(10-n);
    }


    return 0;


}


Measured memory_bytes: 256
import java.util.*;
import static java.lang.Math.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		
		// 入力
		int n = sc.nextInt();
		int a = sc.nextInt();
		int b = sc.nextInt();
		int MOD = 1000000007;
		
		// 計算
		long result = 0;
		Combination comb = new Combination(b);
		result += pow(2, n, MOD)-1;
		result %= MOD;
		result += MOD;
		result -= comb.calc(n, a);
		result %= MOD;
		result += MOD;
		result -= comb.calc(n, b);
		result %= MOD;
		
		
		/*
		for(int i = 0; i < 1<<n; i++){
		    long temp = 0;
		    int cnt = Integer.bitCount(i);
		    if(cnt == a || cnt == b) continue;
		    result += comb.combination(n, i);
		    result %= MOD;
		}
		*/
		
		// 出力
		System.out.println(result);
	}
	
	public static long pow(long a, long n, long MOD) {
	    long res=1;
	    while (n>0) {
	        if ((n-n/2*2)==1) {
	            res=(res*a)%MOD;
	        }
	        a=(a*a)%MOD;
	        n>>=1;
	    }
	    return res%MOD;
	}

	
}

class Combination {
    static final int MOD = 1000000007;
    long[] fact;
    long[] invFact;
    long[] inv;
    
    public Combination (int n) {
        //fact = new long[n+1];
        invFact = new long[n+1];
        inv = new long[n+1];
        //fact[0] = 1;
        //fact[1] = 1;
        invFact[0] = 1;
        invFact[1] = 1;
        inv[1] = 1;
        for (int i = 2; i < n+1; i++) {
            //fact[i] = fact[i - 1] * i % MOD;
            inv[i] = MOD - inv[MOD % i] * (MOD / i) % MOD;
            invFact[i] = invFact[i - 1] * inv[i] % MOD;
        }
    }
    
    public long combination(int n, int k) {
        if (n < k || n < 0 || k < 0) {
            return 0;
        }
        return fact[n] * (invFact[k] * invFact[n - k] % MOD) % MOD;
    }
    
    public long calc(int n, int k) {
	    long res=1;
	    if(n-k < k) k = n-k;
	    for(int i = 0; i < k; i++){
	        res *= n-i;
	        res %= MOD;
	    }
	    res *= invFact[k];
	    
	    return res%MOD;
	}
}


Measured memory_bytes: 25300
#include <bits/stdc++.h>
#define LL long long
#define mod 1000000007
using namespace std;
int main()
{
    int n;
    cin>>n;
    int a[n];
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    int tmp=sum%n;
    sum/=n;
    if(2*tmp>=n)
        sum++;
    LL ans=0;
    for(int i=0;i<n;i++)
    {
        ans+=abs(sum-a[i])*abs(sum-a[i]);
    }
    cout<<ans;
}


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

int dp[20001][256];
const int inf = 1e9;

int main(){
    int n, m;
    while (cin >> n >> m && n){
        vector<int> c(m);
        rep(i,m) cin >> c[i];
        rep(i,n+1) rep(j,256) dp[i][j] = inf;
        dp[0][128] = 0;
        rep(i,n){
            int x; cin >> x;
            rep(j,256){
                rep(k,m){
                    int y = j + c[k];
                    if(y > 255) y = 255;
                    if(y < 0) y = 0;
                    int d = x - y;
                    dp[i+1][y] = min(dp[i+1][y], dp[i][j]+d*d);
                }
            }
        }
        cout << *min_element(dp[n], dp[n+1]) << endl;
    }
}

Measured memory_bytes: 21192
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> G;
vector<int> color;

bool dfs(int u, int c) {
    color[u] = c;
    for(int v : G[u]) {
        if(color[u] == color[v]) return false;
        if(color[v] == 0 && !dfs(v, -c)) return false;
    }
    return true;
}

int main() {
    int N, M;
    cin >> N >> M;
    G.resize(N);
    color.resize(N, 0);
    for(int i=0; i<M; ++i) {
        int A, B;
        cin >> A >> B;
        --A; --B;
        G[A].push_back(B);
        G[B].push_back(A);
    }

    if(dfs(0, 1)) {
        long long b = 0, w = 0;
        for(int i=0; i<N; ++i) {
            if(color[i] == 1) ++b;
            else ++w;
        }
        cout << b * w - M << endl;
    } else {
        cout << (long long)N * (N - 1) / 2 - M << endl;
    }
}

Measured memory_bytes: 6528
#include <algorithm>
#include <deque>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <vector>
using namespace std;
using ll = long long;

int main() {
  int N, A;
  cin >> N >> A;
  bool res = (N % 500 <= A);
  cout << (res ? "Yes" : "No") << endl;
  return 0;
}


Measured memory_bytes: 256
using System;

namespace ABC_132_A_Csharp_ver
{
    class Program
    {
        static void Main(string[] args)
        {
            string S = Console.ReadLine();
            char a = S[0];
            char b = S[1];
            char c = S[2];
            char d = S[3];
            if (a == b && c == d && a != c || a == c && b == d && a != b || a == d && b == c && a != b) Console.WriteLine("Yes");
            else Console.WriteLine("No");
        }
    }
}

Measured memory_bytes: 11092
#include <stdio.h>

#define NIL -2

typedef struct{
  int id;
  int p;
  int l;
  int r;
} Node;

int main(){
  int n,i;

  scanf("%d",&n);

  Node node[n+1];

  for(i=1; i <= n; i++){
    node[i].p = node[i].l = node[i].r = NIL;
    scanf("%d",&node[i].id);
  }

  for(i=1; i <= n; i++){
    if(i != 1){
      node[i].p = node[i/2].id;
    }
    if(2*i <= n){
      node[i].l = node[2*i].id;
    }
    if(2*i+1 <= n){
      node[i].r = node[2*i+1].id;
    }
  }

  for(i=1; i <= n; i++){
    printf("node %d: key = %d, ",i,node[i].id);
    if(node[i].p != NIL){
      printf("parent key = %d, ",node[i].p);
    }
    if(node[i].l != NIL){
      printf("left key = %d, ",node[i].l);
    }
    if(node[i].r != NIL){
      printf("right key = %d, ",node[i].r);
    }
      printf("\n");
  }

  return 0;

}



Measured memory_bytes: 2048
package main

import (
	"bufio"
	"fmt"
	"io"
	"os"
	"strconv"
)

func main() {
	n := readInt()
	var ans float64
	for i := 0; i < n; i++ {
		ans += 1 / readFloat64()
	}

	fmt.Println(1 / ans)
}

// sort ------------------------------------------------------------

type xxx struct {
	x int
}

type sortArray []xxx

func (s sortArray) Len() int           { return len(s) }
func (s sortArray) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func (s sortArray) Less(i, j int) bool { return s[i].x < s[j].x }

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

var (
	readString func() string
	readBytes  func() []byte
)

func init() {
	readString, readBytes = newReadString(os.Stdin)
}

func newReadString(ior io.Reader) (func() string, func() []byte) {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), int(1e+11))
	r.Split(bufio.ScanWords)

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Bytes()
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func sum(a []int) int {
	var ret int
	for i := range a {
		ret += a[i]
	}
	return ret
}

func sumFloat64(a []float64) float64 {
	var ret float64
	for i := range a {
		ret += a[i]
	}
	return ret
}

func gcd(m, n int) int {
	for m%n != 0 {
		m, n = n, m%n
	}
	return n
}

func lcm(m, n int) int {
	return m / gcd(m, n) * n
}


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


int main(int argc, char const *argv[])
{
    int n; 
    cin >> n; 
    if(n < 1200) cout << "ABC"; 
    else if(n < 2800) cout << "ARC"; 
    else cout << "AGC"; 
    return 0; 
}


Measured memory_bytes: 256
#include <bits/stdc++.h> 
#define ll long long
#define F first
#define FF first.first
#define FS first.second
#define S second
#define pb push_back
using namespace std;
const ll N=1000006, INF=1e16;
 
ll n, q=1, m, a[N], b[N], f[N], o, k, t, x, y, z, u, h, mx, mn, ans, Ans;
pair<ll,ll> p[N];
string s;
vector<int> v[N];
 
main(){ios_base::sync_with_stdio(false), cin.tie(0);
   	
//	cin>>q;
   	
   	while(q--){ans=o=0,u=100;
   		cin>>s;
		
		if(s=="ABC")cout<<"ARC";
		else cout<<"ABC";
	}
	
}

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

using namespace std;

#define REP(i,a,b) for(int i=a;i<(int)b;i++)
#define rep(i,n) REP(i,0,n)
#define all(c) (c).begin(), (c).end()
#define zero(a) memset(a, 0, sizeof a)
#define minus(a) memset(a, -1, sizeof a)
#define watch(a) { std::cout << #a << " = " << a << "\n"; }
template<class T1, class T2> inline bool minimize(T1 &a, T2 b) { return b < a && (a = b, 1); }
template<class T1, class T2> inline bool maximize(T1 &a, T2 b) { return a < b && (a = b, 1); }
template<class T, class V> istream& operator>> (istream& ist, pair<T, V>& p) { return ist >> p.first >> p.second; }
template<class T> ostream& operator<< (ostream& ost, pair<T, T>& p) { return ost << p.first << ", " << p.second; }
template<class T> istream& operator>> (istream& ist, vector<T>& vs) { for(auto& e: vs) ist >> e; return ist; }

typedef long long ll;
int const inf = 1<<29;

int main() {
  int H, W; cin >> H >> W;
  vector<string> vs(H);
  rep(i, H) {
    cin >> vs[i];
  }
  vector<bool> bsh(H), bsw(W);
  rep(i, H) {
    bsh[i] = 1;
    rep(j, W) {
      if (vs[i][j] == '#') {
        bsh[i] = 0;
      }
    }
  }
  rep(j, W) {
    bsw[j] = 1;
    rep(i, H) {
      if (vs[i][j] == '#') {
        bsw[j] = 0;
      }
    }
  }
  rep(i, H) {
    bool used = 0;
    rep(j, W) {
      if (bsh[i] || bsw[j]) {}
      else {
        used = 1;
        cout << vs[i][j];
      }
    }
    if (used) cout << "\n";
  }
}


Measured memory_bytes: 256
package main

import (
	"fmt"
)

func main() {

	var S string

	fmt.Scan(&S)

	list := make(map[string]int)

	var temp string

	for i:=0;i<4;i++{

		temp = S[i:i+1]

		val,ok := list[temp]

		if ok==true{

			list[temp] = val +1

		}else{

			list[temp] = 1
		}
	}

	if len(list) ==2 {

		for _,value := range list{

			if(value != 2){

				fmt.Println("No")
				return
			}
		}

	}else{

		fmt.Println("No")
		return
	}

	fmt.Println("Yes")

}

Measured memory_bytes: 512
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define ALL(c) (c).begin(),(c).end()
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MINF(a) memset(a,0x3f,sizeof(a))
#define POW(n) (1LL<<(n))
#define IN(i,a,b) (a <= i && i <= b)
using namespace std;
template <typename T> inline bool CHMIN(T& a,T b) { if(a>b) { a=b; return 1; } return 0; }
template <typename T> inline bool CHMAX(T& a,T b) { if(a<b) { a=b; return 1; } return 0; }
template <typename T> inline void SORT(T& a) { sort(ALL(a)); }
template <typename T> inline void REV(T& a) { reverse(ALL(a)); }
template <typename T> inline void UNI(T& a) { sort(ALL(a)); a.erase(unique(ALL(a)),a.end()); }
const int MOD = 1000000007;
const int INF = 0x3f3f3f3f3f3f3f3f;
const double EPS = 1e-10;
/* ---------------------------------------------------------------------------------------------------- */



signed main() {
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int N,K;
  cin >> N >> K;
  if (K == 1) {
    cout << 0 << endl;
    return 0;
  }
  N -= K;
  cout << N << endl;

  return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define int long long

signed main() {

    int A,B;
    cin >> A >> B;
    if(B >= A) {
        int C;
        C = B;
        B = A;
        A = C;
    }
    if( (A - B)%2 == 0){
        cout << (A - B)/2+B << endl;
    }
    else{
        cout << "IMPOSSIBLE" << endl;
    }
    return 0;


}

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

int a, b, c, d;
string str, ans;

void dfs(int i, string cur, int val) {
  if (i == 0) {
    dfs(i + 1, cur + "+" + to_string(b), val + b);
    dfs(i + 1, cur + "-" + to_string(b), val - b);
  }
  else if (i == 1) {
    dfs(i + 1, cur + "+" + to_string(c), val + c);
    dfs(i + 1, cur + "-" + to_string(c), val - c);
  }
  else if (i == 2) {
    dfs(i + 1, cur + "+" + to_string(d), val + d);
    dfs(i + 1, cur + "-" + to_string(d), val - d);
  }
  else if (i == 3) {
    if (val == 7) {
      ans = cur;
    }
  }
}

int main(void){
    // Here your code !
    cin >> str;
    a = (int)str[0] - 48;
    b = (int)str[1] - 48;
    c = (int)str[2] - 48;
    d = (int)str[3] - 48;

    dfs(0, to_string(a), a);
    cout << ans + "=7"<< endl;

    return 0;
}

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

int N;
ll H[100005];

int solve(int p) {
    int c = 0;
    for(int i = p;i<N-1;i++) {
        if(H[i] >= H[i+1]) c++;
        else break;
    }
    return c;
}

int main() {
    cin >> N;
    for(int i = 0;i<N;i++) cin >> H[i];
    int x = solve(0);
    int p = x+1;
    int ans = x;
    while(p < N) {
        x = solve(p);
        p = p + x + 1; 
        ans = max(ans, x);
    }
    cout << ans << endl;
}

Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static int ReadInt() { return int.Parse(Console.ReadLine()); }
    static int[] ReadInts() { return Console.ReadLine().Split().Select(int.Parse).ToArray(); }
    static string[] ReadStrings() { return Console.ReadLine().Split(); }

    static int Calc(long n) {
        int ans = n.ToString().Length;
        int m = (int)Math.Sqrt(n);
        for (int i = 1; i <= m; i++) {
            if (n % i == 0) {
                int x = Math.Max(i.ToString().Length, (n / i).ToString().Length);
                ans = Math.Min(ans, x);
            }
        }
        return ans;
    }

    static void Main() {
        var n = long.Parse(Console.ReadLine());
        Console.WriteLine(Calc(n));
    }
}

Measured memory_bytes: 11092
A, B = map(int, input().split())

if A%2 == 0 and B%2 == 1:
    if (B - A - 1) % 4 == 0:
        print("1")
    else:
        print("0")
elif A%2 == 0 and B%2 == 0:
    if (B-A) % 4 == 0:
        print(B)
    else:
        print(B ^ 1)
elif A%2 == 1 and B%2 == 1:
    if (B-A) % 4 == 0:
        print(A)
    else:
        print(A ^ 1)
else:
    if (B - A - 1) % 4 == 0:
        print(A ^ B)
    else:
        print(A ^ B ^ 1)

Measured memory_bytes: 3064
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<cstdlib>
#include<math.h>
//#include<iostream>
using namespace std;

int n;
#define maxn 100011
int cnt[3]={0,0,0};
int x;
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)
	{
		scanf("%d",&x);
		if (x%4==0) cnt[2]++;
		else if (x&1) cnt[0]++;
		else cnt[1]++;
	}
	bool ans;
	if (n==2)
	{
		if (cnt[0]>0)
			if (cnt[2]==1) ans=1;
			else ans=0;
		else ans=1;
	}
	else if (cnt[2]>=cnt[0]) ans=1;
	else if (cnt[2]==cnt[0]-1 && !cnt[1]) ans=1;
	else ans=0;
	printf(ans?"Yes\n":"No\n");
	return 0;
}

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

using namespace std;

int n, m, k;

int main() {
	cin >> n >> m >> k;
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= m; j++)
			if (i * m + j * n - 2 * i * j == k) return cout << "Yes", 0;
	cout << "No";
	return 0;
}


Measured memory_bytes: 256
def d_factorization(MOD=10**9 + 7):
    N, M = [int(i) for i in input().split()]

    def prime_factorization_dict(n):
        if n == 1:
            return {2: 0}  # 1は素数の0乗の積とみなす
        i, table = 2, {}
        while i**2 <= n:
            table[i] = 0
            while n % i == 0:
                table[i] += 1
                n //= i
            if table[i] == 0:
                table.pop(i)
            i += 1
        if n > 1:
            table[n] = 1
        return table

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

        def combination_with_repetition(self, n, r):
            return self.combination(n + r - 1, r)

    prime_m = prime_factorization_dict(M)
    h = Combination(max(prime_m.values()) + N - 1).combination_with_repetition
    ans = 1
    for b in prime_m.values():
        ans = (ans * h(N, b)) % MOD
    return ans

print(d_factorization())

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

int main(){
  int n, k;
  cin >> n >> k;
  
  int i=1;
  while(n>=k){
    n = (n - (n%k))/k;
    i++;
  }

  cout << i << endl;
  
  return 0;
}

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

int main(){
  long long N, A, B;
  cin >> N >> A >> B;

  if(A > B)
    cout << 0 << endl;
  else if(N == 1){
    if(A != B)
      cout << 0 << endl;
    else
      cout << 1 << endl;
  }
  else
    cout << (B-A)*(N-2)+1 << endl;

  return 0;
}


Measured memory_bytes: 3600
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
int main(int argc, char *argv[])
{
	long long n,ans=0,total,j,i;
	scanf("%lld",&n);
	for(i=2;i<=sqrt(n);i++){
		if(n%i==0){
			total=0,j=1;
			while(n%i==0){
				n/=i;
				total++;
			}
			while(total-j>=0){
				total-=j;
				j++;ans++;
			}
		}
	}
	if(n!=1)ans++;
	printf("%lld\n",ans);
}

Measured memory_bytes: 2152
import java.io.*;
public class Main {
	public static void main(String[] args) throws IOException{
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String linesum = "";
		char[] alpha = {'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
		int[] alphabet = new int[26];
		String line;
		while((line = reader.readLine()) != null){
			linesum = linesum + line;
		}
		char[] word = new char[linesum.length()];
		for(int i = 0; i < 26; i++){
			alphabet[i] = 0;
		}
		for(int i = 0; i < linesum.length(); i++){
			word[i] = linesum.toLowerCase().charAt(i);
			for(int j = 0; j < 26; j++){
				if(word[i] == alpha[j]){
					alphabet[j]++;
				}
			}
		}
		for(int i = 0; i < 26; i++){
			System.out.println(alpha[i] + " : " + alphabet[i]);
		}
	}
}

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

using namespace std;

#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define REP(i, n) FOR(i, 0, n)
#define RFOR(i, a, b) for(int i=(a);i>=(b);i--)
#define RREP(i, n) RFOR(i, n, 0)
#define MFOR(i, m) for(auto i=(m).begin();i!=(m).end();i++)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((int)(x).size())

typedef long long int ll;
typedef pair<int, int> P;
typedef pair<ll, ll> Pll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;

const double eps = 1e-10;
const int MOD = 1000000007;
const int INF = 1000000000;
const ll LINF = 1 << 30;

template<typename T>
void printv(vector<T> const& s) {
  REP(i, SZ(s)) {
    cout << s[i] << " ";
  }
  cout << endl;
}

int main () {
  cin.tie(0);
  cout << setprecision(10);

  int n, m; cin >> n >> m;
  map<int, int> ma, mb, mp;
  vi va(n), vb(m);

  vi a(n);
  REP(i, n) {
    cin >> a[i];
    if(ma[a[i]] > 0) {
      cout << 0 << endl;
      return 0;
    }
    ma[a[i]] = i+1;
  }

  vi b(m);
  REP(i, m) {
    cin >> b[i];
    if(mb[b[i]] > 0) {
      cout << 0 << endl;
      return 0;
    }
    mb[b[i]] = i+1;
  }

  REP(i, n) {
    REP(j, m) {
      int tmp = min(a[i], b[j]);
      mp[tmp]++;
      if(tmp == a[i]) va[i]++;
      if(tmp == b[j]) vb[j]++;
    }
  }

  ll ans = 1;
  int cnt = 0;
  RFOR(i, n*m, 1) {
    cnt += mp[i];
    if(cnt <= 0) {
      cout << 0 << endl;
      return 0;
    }
    if(ma.count(i) > 0 && mb.count(i) > 0) {
      ans *= 1;
    } else if(ma.count(i) > 0) {
      ans *= va[ma[i]-1];
    } else if(mb.count(i) > 0) {
      ans *= vb[mb[i]-1];
    } else {
      ans *= cnt;
    }
    ans %= MOD;
    cnt--;

  }
  cout << ans << endl;
  
}


Measured memory_bytes: 47232
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }

void _main() {
  int A, B, C, X, Y;
  cin >> A >> B >> C >> X >> Y;

  int ans = inf;
  rep(i, 0, 200001) {
    int x = X - i/2;
    int y = Y - i/2;
    int tmp = i*C;
    if (0 < x) tmp += x * A;
    if (0 < y) tmp += y * B;
    chmin(ans, tmp);
  }

  cout << ans << "\n";
}

Measured memory_bytes: 256
/* ex3_4
   key_tree */

#include <stdio.h>

// Nを1-9で割った商が1-9かつ余りが0になればよい
int main(void) {
  int N;
  scanf("%d", &N);
  int i = 1;
  // 1-9まで調べる
  while(i < 10){
    int quotient = N / i;
    int remainder = N % i;
    //商が1-9かつ余り0
    if(quotient >= 1 && quotient <= 9 && remainder == 0){
      printf("Yes\n");
	  break;/*当てはまったらwhile脱出*/
	}
	i += 1;
  }
  if(i == 10){
    printf("No\n");
  }
  return 0;
}


Measured memory_bytes: 128
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), w = sc.nextInt();
        int[] ws = new int[n];
        long[] vs = new long[n];

        long[][] dp = new long[n][w + 1];
        for (int i = 0; i < n; i++) {
            ws[i] = sc.nextInt();
            vs[i] = sc.nextInt();
        }
        System.out.println(maxKnapsack(ws, vs, w));
    }

    private static long maxKnapsack(int[] ws, long[] vs, int w) {
        long[] dp = new long[w + 1];

        for (int i = 0; i < ws.length; i++) {
            for (int s = w; s >= ws[i]; s--) {
                dp[s] = Math.max(dp[s - ws[i]] + vs[i], dp[s]);
            }
        }
        return dp[w];
    }
}



Measured memory_bytes: 126932