akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
typedef int64_t Int;
using namespace std;

map<Int, int> factor;

//---------- 素因数分解 ----------
void prime_factor(Int n) {
  for(Int i = 2; i * i <= n; i++) {
    while(n % i == 0) {
      factor[i]++;
      n /= i;
    }
  }
  if(n != 1) factor[n]++;
}

int main(){
    int N; cin >> N;
    
    for(Int i = 2; i <= N; i++) prime_factor(i);

    int cnt2 = 0, cnt4 = 0, cnt14 = 0, cnt24 = 0, cnt74 = 0;
    for(auto itr = factor.begin(); itr != factor.end(); itr++){
        pair<Int, int> cur = *itr;
        if(cur.second >= 2) cnt2++;
        if(cur.second >= 4) cnt4++;
        if(cur.second >= 14) cnt14++;
        if(cur.second >= 24) cnt24++;
        if(cur.second >= 74) cnt74++;
    }

    //(2,4,4), (2,24), (14,4), (74)
    int ans = 0;
    if(cnt4 > 1) ans += cnt4*(cnt4-1)/2 * (cnt2-2);
    if(cnt24 > 0) ans += cnt24 * (cnt2-1);
    if(cnt14 > 0) ans += cnt14 * (cnt4-1);
    ans += cnt74;
    cout << ans << endl;
}

Measured memory_bytes: 256
h, w = map(int, input().split())
A = [list(str(input())) for _ in range(h)]

#A = [list('a'*100) for _ in range(h)]

idx = 0
d = {}
C = [0]*26
for i in range(h):
    for j in range(w):
        C[ord(A[i][j])-ord('a')] += 1
        d[(i, j)] = idx
        idx += 1

def Find(x, par):
    if par[x] < 0:
        return x
    else:
        par[x] = Find(par[x], par)
        return par[x]

def Unite(x, y, par, rank):
    x = Find(x, par)
    y = Find(y, par)

    if x != y:
        if rank[x] < rank[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1

def Same(x, y, par):
    return Find(x, par) == Find(y, par)

def Size(x, par):
    return -par[Find(x, par)]

n = h*w
par = [-1]*n
rank = [0]*n

for i in range(h):
    for j in range(w):
        p = d[(i, j)]
        q = d[(i, w-1-j)]
        Unite(p, q, par, rank)
        q = d[(h-1-i, j)]
        Unite(p, q, par, rank)

S = []
for i in range(n):
    if par[i] < 0:
        S.append(-par[i])
S.sort(reverse=True)
#print(S)
#print(len(S))
#print(C)

C = [-c for c in C]
import heapq
heapq.heapify(C)
for s in S:
    c = -heapq.heappop(C)
    if c >= s:
        c -= s
        heapq.heappush(C, -c)
    else:
        print('No')
        exit()
else:
    print('Yes')


Measured memory_bytes: 71548
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
typedef long long int lint;
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> h(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i];
    }
    // dp[i]:i段目に達するための最小コスト
    vector<lint> dp(n, LLONG_MAX);
    dp[0] = 0;
    for (int i = 1; i < n; i++) {
        for (int j = 1; j <= k; j++) {
            if (i - j >= 0) {
                dp[i] = min(dp[i], dp[i - j] + abs(h[i] - h[i - j]));
            }
        }
    }
    cout << dp[n - 1] << endl;
}

Measured memory_bytes: 1408
fun main(args: Array<String>) {
    val (H, W, K) = readLine()!!.split(" ").map(String::toInt)
    val F = Array(H) { readLine()!!.toCharArray() }
    val ans = Array(H) { Array(W) { 0 } }
    var p = 1
    for (i in 0..H-1) {
        if (F[i].filter{ x -> x == '#'}.count() != 0) {
            var first = true
            for (j in 0..W-1) {
                if (F[i][j] == '#') {
                    if (!first) { p += 1 }
                    first = false
                }
                ans[i][j] = p
            }
            p += 1
        }
    }
    for (i in 1..H-1) {
        if (F[i].filter { x -> x == '#' }.count() == 0) {
            ans[i] = ans[i-1]
        }
    }
    for (i in (H-2).downTo(0)) {
        if (F[i].filter { x -> x == '#' }.count() == 0) {
            ans[i] = ans[i+1]
        }
    }
    ans.forEach { l -> l.forEach{ s -> print("$s ") }; println() }
}

Measured memory_bytes: 48372
N = int(input())
txy_init = [[0, 0, 0]]
txy = txy_init + [[int(i) for i in input().split(" ")] for i in range(N)]
t, x, y = 0, 1, 2

checker = True
for i in range(N):
    dt = txy[i+1][t] - txy[i][t]
    dxy = abs(txy[i+1][x] - txy[i][x]) + abs(txy[i+1][y] - txy[i][y])
    
    if dt < dxy:
        checker = False
    else:
        if (dt - dxy) % 2 == 0:
            continue
        else:
            checker = False
    
    if checker:
        continue
    else:
        break

if checker:
    print("Yes")
else:
    print("No")

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

int main(){
  int N, L;
  cin >> N >> L;
  vector<string> s(N);
  for(int i = 0; i < N; i++){
    cin >> s.at(i);
  }
  sort(s.begin(), s.end());
  string t = "";
  for(int i = 0; i < N; i++){
    t += s.at(i);
  }
  cout << t << endl;
  return 0;
}

Measured memory_bytes: 256
//nani?
#include<bits/stdc++.h>
#define pi acos(-1);
#define fs first
#define sc second
#define pb push_back
#define mp make_pair
#define f(i,a,b) for( int i = a; i < b ; i++ )
#define sor(a) sort( a.begin(), a.end() )
#define rsor(a) sort( a.rbegin(), a.rend() )
#define fastio ios_base::sync_with_stdio(0);cin.tie(0)
//#define inf 1LL<<62
typedef long long ll;
typedef double ld;
using namespace std;
const ll inf=1e10+6;
const ll MOD=1e9+7;
const ll mod=998244353;
// ac cmtr;
const int MAX_N = 1e6+5;
const int LG = 25;

#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) {
  cout << name << " : " << arg1 << endl;}
 
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
  const char* comma = strchr(names + 1, ',');
  cout.write(names, comma - names) << " : " << arg1<<" | ";
  __f(comma+1, args...);}
#else
#define trace(...)
#endif
//---------------------------

ll a[MAX_N];
ll b[MAX_N];

int main(){
    fastio;
    ll n;
    cin>>n;
    ll aux = sqrt(n);
    while(n%aux != 0){
        aux--;
    }
    cout<<aux+n/aux -2 <<endl;


}






Measured memory_bytes: 3676
#define _GLIBCXX_DEBUG
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
typedef unsigned long long int ulli;
#define vec(s) vector

#define vvec(s) vector<vector
>
typedef vector<lli> vi;
typedef vector<vi> vvi;
typedef pair<lli,lli> pii;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define Yes(x) cout<<(x?"Yes":"No")<<endl;
#define YES(x) cout<<(x?"YES":"NO")<<endl;
#define out(s) cout<<s<<endl;
#define pb(s) push_back(s);
#define sp " " 
#define INF 10000000000
#define LINF 9000000000000000000
#define all(s) s.begin(),s.end()
void vout(vi v){
    for(lli i=0;i<v.size();i++)
    cout<<v.at(i)<<endl;
}
int main(){
    cout << std::fixed << std::setprecision(10);
    lli a;
    cin>>a;
    string s;
    cin>>s;
    out((a<3200?"red":s))
}

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

using namespace std;

int main(){
    int K,T,run,lst=-1,ans=0,sum=0;
    cin >> K >> T;
    vector<int> a(T);
    for(int i=0;i<T;i++){
        cin >> a[i];
        sum += a[i];
    }

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

    if(a.back()<=1+sum-a.back()){
        cout << 0 << endl;
    }else{
        cout << 2*a.back()-sum-1 << endl;
    }
}

Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdlib>
#include<queue>
#include<set>
#include<cstdio>

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 0; i < n; i++)
#define P pair<int, int>

typedef vector<int> vec;
typedef vector<vec> mat;

const ll mod = 1000000007;

mat mul(mat &A, mat &B){
    mat C(A.size(), vec(B[0].size()));
    for (int i = 0; i < A.size(); i++){
        for (int k = 0; k < B.size(); k++){
            for (int j = 0; j < B[0].size(); j++){
                C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod;
            }
        }
    }
    return C;
}

mat pow(mat A, ll n){
    mat B(A.size(), vec(A.size()));
    for (int i = 0; i < A.size(); i++){
        B[i][i] = 1;
    }
    while(n > 0){
        if(n & 1) B = mul(B, A);
        A = mul(A, A);
        n >>= 1;
    }
    return B;
}

int main(){
    int n, x;
    cin >> n >> x;
    int l[n];
    rep(i, n) cin >> l[i];
    int d = 0;
    int ans = 0;
    while(d <= x && ans <= n){
        d += l[ans];
        ans++;
    }
    cout << ans << endl;
}

Measured memory_bytes: 3632
import java.util.*;
import java.util.function.*;
import java.math.*;
public class Main {
    public static void main(String[] args){
		Scanner s = new Scanner(System.in);
		char[] S = s.next().toCharArray();
		char[] T = s.next().toCharArray();
		
		int ret = 0;
		for(int i = 0; i < S.length; i++) {
			if(S[i] != T[i]) {
				ret++;
			}
		}
		System.out.println(ret);
	}
}

Measured memory_bytes: 42112
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int INF = 1e9 + 7, MOD = 1e9 + 7;
const long long LINF = 1e18;
const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
signed main() {
	int h, w;
	cin >> h >> w;
	int ans = INF;
	if (h % 3 == 0 || w % 3 == 0) {
		cout << 0 << endl;
		return 0;
	}
	for (int i = 1; i < h; i++) {
		int H = h - i, W = w;
		int S1 = (h - H) * W, S2 = H * (W / 2);
		int S3 = H * W - S2;
		int Max = max({S1, S2, S3}), Min = min({S1, S2, S3});
		ans = min(ans, Max - Min);
		S2 = (H / 2) * W;
		S3 = H * W - S2;
		Max = max({S1, S2, S3}), Min = min({S1, S2, S3});
		ans = min(ans, Max - Min);
	}
	for (int i = 1; i < w; i++) {
		int H = h, W = w - i;
		int S1 = H * (w - W), S2 = (H / 2) * W;
		int S3 = H * W - S2;
		int Max = max({S1, S2, S3}), Min = min({S1, S2, S3});
		ans = min(ans, Max - Min);
		S2 = H * (W / 2);
		S3 = H * W - S2;
		Max = max({S1, S2, S3}), Min = min({S1, S2, S3});
		ans = min(ans, Max - Min);
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <stdlib.h>
int main(){
  int N,i,j,k,tmp,count;
  count=0;
  scanf("%d",&N);
  int L[N+1];
  for(i=0;i<N;i++) scanf("%d",&L[i]);
  for(i=0;i<N;i++){
    for(j=i+1;j<N;j++){
      if(L[i]>L[j]){
      tmp=L[i];
      L[i]=L[j];
      L[j]=tmp;
      }
    }
  }
  for(i=0;i<N;i++){
    for(j=i+1;j<N;j++){
      if(L[i]==L[j]) continue;
      for(k=j+1;k<N;k++){
        if(L[j]==L[k]) continue;
        if(L[i]+L[j]>L[k]) count++;
      }
    }
  }
  printf("%d",count);
  return 0;
}

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

int main(){

    long long int X, K, D;
    cin >> X >> K >> D;

    X = abs(X);
    long long int a = X / D;
    long long int ans;

    //cout << "a = " << a << endl;

    if( a >= K ){
        ans = X - ( K * D );
        //cout << "a >= K" << endl;
        cout << ans << endl;
    }
    else{
    
        long long int x1 = X - ( a * D );
        long long int x2 = X - ( (a+1) * D );
        
        if( K % 2 == a % 2 ) ans = x1;
        else ans = abs(x2);

        //cout << "a < K" << endl;
        //cout << "x1 = " << x1 << endl;
        //cout << "x2 = " << x2 << endl;
        cout << ans << endl;
    }

}
    



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

#define sp ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define v(t) vector<t>
#define vv(t) vector<vector<t>>
#define vn(t,n,val) vector<t>(n,val)
#define vvn(t,r,c,val) vector<vector<t>>(r, vector<t>(c,val))
#define vvv(t) vector<vector<vector<t>>>
#define vvvn(t,l,b,h,val) vector<vector<vector<t>>>(l,vector<vector<t>>(b,vector<t>(h)))

int main() {
	sp;

	////////////////To Remove//////////////
	// freopen("../../input.txt", "r", stdin);
	// freopen("../../output.txt", "w", stdout);
	///////////////////////////////////////

	int k, n;
	cin>>k>>n;
	vector<int> a(n);
	for(auto& x: a) cin>>x;
	sort(a.begin(), a.end());

	int gap = 0;

	for(int i = 0; i < n-1; ++i){
		gap = max(gap, a[i+1]-a[i]);
	}

	gap = max(gap, k-a[n-1]+a[0]);
	// long long result = 0;
	// long long cr = 0;

	// for(int i = 0; i < n-1; ++i){
	// 	result += abs(a[i]-a[i+1]);
	// 	// cout<<abs(a[i]-a[i+1])<<" ";
	// }
	// // cout<<"\n";
	// cr = result;
	// // cout<<result<<"\n";

	// for(int i = 0; i < n-1; ++i){
	// 	result -= abs(a[i]-a[i+1]);
	// 	result += abs(a[n-1+i]-a[n + i]);
	// 	cr = min(result, cr);
	// }

	// cout<<cr;

	cout<<k-gap;

  	return 0;
}

Measured memory_bytes: 1024
#include<iostream>

using namespace std;

string S;
int K;
int main () {
    cin >> S >> K;
    for(int i=0; i<K; i++) {
        if(S[i] != '1') {
            cout << S[i] << endl;
            return 0;
        }
    }
    cout << 1 << endl;
    return 0;
}


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

int main() {
    string S, T;
    cin >> S >> T;
    int64_t ans = 0;
    for (int64_t i = 0; i < S.size(); i++) {
        if (S[i] != T[i]) {
            ans++;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 3920
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define REP(I, N) for (int I = 0; I < (N); ++I)
#define REPP(I, A, B) for (int I = (A); I < (B); ++I)
#define RI(X) scanf("%d", &(X))
#define RII(X, Y) scanf("%d%d", &(X), &(Y))
#define RIII(X, Y, Z) scanf("%d%d%d", &(X), &(Y), &(Z))
#define DRI(X) int (X); scanf("%d", &X)
#define DRII(X, Y) int X, Y; scanf("%d%d", &X, &Y)
#define DRIII(X, Y, Z) int X, Y, Z; scanf("%d%d%d", &X, &Y, &Z)
#define RS(X) scanf("%s", (X))
#define CASET int ___T, case_n = 1; scanf("%d ", &___T); while (___T-- > 0)
#define MP make_pair
#define PB push_back
#define MS0(X) memset((X), 0, sizeof((X)))
#define MS1(X) memset((X), -1, sizeof((X)))
#define LEN(X) strlen(X)
#define PII pair<int,int>
#define VI vector<int>
#define VPII vector<pair<int,int> >
#define PLL pair<long long,long long>
#define VPLL vector<pair<long long,long long> >
#define F first
#define S second
typedef long long LL;
using namespace std;
const int MOD = 1e9+7;
const int SIZE = 1e6+10;
int a[SIZE];
int main(){
    DRI(n);
    REPP(i,1,n+1)RI(a[i]);
    int an=0;
    REPP(i,1,n+1){
        if(a[a[i]]==i)an++;
    }
    printf("%d\n",an/2);
    return 0;
}


Measured memory_bytes: 640
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
# from fractions import gcd
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from functools import reduce
from bisect import bisect_left, insort_left
from heapq import heapify, heappush, heappop

INPUT = lambda: sys.stdin.readline().rstrip()
INT = lambda: int(INPUT())
MAP = lambda: map(int, INPUT().split())
S_MAP = lambda: map(str, INPUT().split())
LIST = lambda: list(map(int, INPUT().split()))
S_LIST = lambda: list(map(str, INPUT().split()))
ZIP = lambda: zip(*(MAP() for _ in range(n)))

sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
    K, N = MAP()
    A = LIST()

    ans = INF
    for i in range(N):
        if i == 0:
            ans = A[i+N-1] - A[i] if A[i+N-1] - A[i] < ans else ans
        else:
            ans = K + A[(i+N-1)%N] - A[i] if K + A[(i+N-1)%N] - A[i] < ans else ans
    
    print(ans)
    

if __name__ == '__main__':
    main()


Measured memory_bytes: 73128
#include <bits/stdc++.h>
#define rep(a,n) for (ll a = 0; a < (n); ++a)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<vector<ll> > Graph;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const ll INF = 1e18;

int main(){
    ll n;
    cin >> n;
    vector<ll>res(n+1,0);
    for(ll x=1;x<=150;x++){
        for(ll y=1;y<150;y++){
            for(ll z=1;z<150;z++){
                ll ans = x*x+y*y+z*z+x*y+y*z+z*x;
                if(ans>n)continue;
                res[ans]++;
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout << res[i] << endl;
    }
    return 0;
}


Measured memory_bytes: 3548
#include<stdio.h>
 
int main(){
  
  int M_1,D_1,M_2,D_2;
  
  scanf("%d %d",&M_1,&D_1);
  scanf("%d %d",&M_2,&D_2);
  
  if(M_1!=M_2 && D_1>D_2){
    printf("1");
  }else{
    printf("0");
  }
  return 0;
  
}
      

Measured memory_bytes: 128
n, c = map(int,input().split())
x = []
v = []
for i in range(n):
    s, t = input().split()
    x.append(int(s))
    v.append(int(t))
#配列の静的確保ver
vl1 = [0]*(n+1)
vl2 = [0]*(n+1)
suml = 0
vr1 = [0]*(n+1)
vr2 = [0]*(n+1)
sumr = 0
for i in range(n):
    suml += v[i]
    vl1[i+1] = vl1[i] if vl1[i] > suml - x[i] else suml - x[i]
    vl2[i+1] = vl2[i] if vl2[i] > suml - x[i]*2 else suml - x[i]*2
    sumr += v[n-1-i]
    vr1[i+1] = vr1[i] if vr1[i] > sumr - c + x[n-1-i] else sumr - c + x[n-1-i]
    vr2[i+1] = vr2[i] if vr2[i] > sumr - (c - x[n-1-i])*2 else sumr - (c - x[n-1-i])*2
print(max( [max(vl1[i]+vr2[n-i],vr1[i]+vl2[n-i]) for i in range(n+1)] ))


Measured memory_bytes: 28756
A,B,C,D = map(int,input().split())
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
CD = lcm(C,D)
c_div = 0
d_div = 0
cd_div = 0
ans = 0
if A % C == 0:
    first_C = A
else:
    first_C = A + C -(A%C)
last_C = B -(B%C)
c_div = (last_C - first_C)//C + 1

if A % D == 0:
    first_D = A
else:
    first_D = A + D -(A%D)
last_D = B - (B%D)
d_div = (last_D - first_D)//D + 1

if A % CD == 0:
    first_CD =A
else:
    first_CD = A + CD -(A%CD)
last_CD = B -(B%CD)
cd_div = (last_CD - first_CD)//CD + 1

ans = c_div + d_div -cd_div
print(B-A+1-ans)


Measured memory_bytes: 3064
import java.util.*;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    long MOD = 998244353;
    int n = sc.nextInt();
    int s = sc.nextInt();
    long[][] dp = new long[n][s + 1];
    int[] a = new int[n];
    for(int i = 0; i < n; i++) {
      a[i] = sc.nextInt();
    }
    if(a[0] <= s) dp[0][a[0]] = 1;
    dp[0][0] = 2;
    for(int i = 1; i < n; i++) {
      for(int j = 0; j <= s; j++) {
        if(j >= a[i]) {
          dp[i][j] = (dp[i - 1][j - a[i]] + 2 * dp[i - 1][j]) % MOD;
        } else {
          dp[i][j] = (2 * dp[i - 1][j]) % MOD;
        }
      }
    }
    System.out.println(dp[n - 1][s]);
  }
}

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


using namespace std;

#define f first
#define s second


using ll = long long;


int main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int> > adj(n);
    vector<int> indegree(n), toporder;
    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        --x, --y;
        adj[x].push_back(y);
        ++indegree[y];
    }
    queue<int> Q;
    for (int i = 0; i < n; i++) {
        if (indegree[i] == 0) {
            Q.push(i);
        }
    }
    while (Q.size()) {
        int node = Q.front();
        Q.pop();
        for (int i : adj[node]) {
            --indegree[i];
            if (indegree[i] == 0) {
                Q.push(i);
            }
        }
        toporder.push_back(node);
    }
    assert((int)toporder.size() == n);
    vector<int> dp(n, 0);
    for (int i : toporder) {
        for(int j : adj[i]) {
            dp[j] = max(dp[j], 1 + dp[i]);
        }
    }
    cout << *max_element(dp.begin(), dp.end()) << "\n";
}



Measured memory_bytes: 10120
INF = 10 ** 20

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

size = 1
while size < n:
  size *= 2
size = size * 2 - 1

seg_tree = [2 ** 31 - 1 for _ in range(size)]

def update(i, x):
  ind = size // 2 + i 
  seg_tree[ind] = x
  while ind:
    ind = (ind - 1) // 2
    ch1 = seg_tree[ind * 2 + 1]
    ch2 = seg_tree[ind * 2 + 2]
    seg_tree[ind] = min(ch1, ch2)

def _find(s, t, k, l, r):
  if r < s or t < l: return INF
  if s <= l and r <= t:
    return seg_tree[k]
  else:
    vl = _find(s, t, k * 2 + 1, l, (l + r) // 2)
    vr = _find(s, t, k * 2 + 2, (l + r) // 2 + 1, r)
    return min(vl, vr)

def find(s, t):
  return _find(s, t, 0, 0, size // 2)

for _ in range(q):
  com, x, y = map(int, input().split())
  if not com:
    update(x, y)
  else:
    print(find(x, y))


Measured memory_bytes: 9016
#include<set>    
#include<map>    
#include<stack>    
#include<ctime>    
#include<cstdio>    
#include<queue>    
#include<cmath>    
#include<vector>    
#include<cstring>   
#include<climits>    
#include<iostream>   
#include<algorithm>   
using namespace std;
#define LL long long
int read(){   
    int f=1,x=0;char c=getchar();   
    while(c<'0'||'9'<c){if(c=='-')f=-1;c=getchar();}   
    while('0'<=c&&c<='9'){x=x*10+c-'0';c=getchar();}   
    return f*x;
}
#define MAXN int(5e6)
#define INF 0x3f3f3f3f
const LL P=924844033,g=5,rg=554906420;
LL Lim=1,lg2,a[MAXN+5],b[MAXN+5],rev[MAXN+5];
LL Pow(LL x,int y){
	LL ret=1;
	while(y){
		if(y&1) ret=(ret*x)%P;
		x=(x*x)%P;
		y>>=1;
	}
	return ret;
}
#define limit Lim
#define G g
#define Gi rg
void NTT(LL *A, int type) {
    for(int i=0;i<limit;i++) 
        if(i<rev[i]) swap(A[i],A[rev[i]]);
    for(int mid=1;mid<limit;mid <<=1) {  
        LL Wn=Pow(type==1?G:Gi,(P-1)/(mid<<1));
        for(int j=0;j<limit;j+=(mid<<1)) {
            LL w=1;
            for(int k=0;k<mid;k++,w=(w*Wn)%P) {
				int x=A[j+k],y=w*A[j+k+mid]%P;
				A[j+k]=(x+y)%P,A[j+k+mid]=(x-y+P)%P;
            }
        }
    }
}
vector<int> Gra[MAXN+5];
int N,siz[MAXN+5],cnt[MAXN+5];
void DFS(int u,int fa){
	siz[u]=1;
	for(int i=0;i<(int)Gra[u].size();i++){
		int v=Gra[u][i];
		if(v==fa) continue;
		DFS(v,u),siz[u]+=siz[v];
	}
	if(fa!=0)
		cnt[N]++,cnt[siz[u]]--,cnt[N-siz[u]]--;
	return ;
}
LL fac[MAXN+5],inv[MAXN+5];
int main(){
	N=read();
	fac[0]=1;
	for(int i=1;i<=N;i++)
		fac[i]=fac[i-1]*i%P;
	inv[N]=Pow(fac[N],P-2);
	for(int i=N-1;i>=0;i--)
		inv[i]=inv[i+1]*(i+1)%P;
	for(int i=1;i<N;i++){
		int u=read(),v=read();
		Gra[u].push_back(v);
		Gra[v].push_back(u);
	}
	DFS(1,0),cnt[N]=N;
	
	int n=N,m=N;
	for(int i=0;i<=n;i++)
		a[i]=cnt[i]*fac[i]%P;
	for(int i=0;i<=m;i++)
		b[m-i]=inv[i];
	while(Lim<=n+m) Lim<<=1,lg2++;
	for(int i=0;i<Lim;i++)
		rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg2-1));
	NTT(a,1),NTT(b,1);
	for(int i=0;i<Lim;i++)
		a[i]=(a[i]*b[i])%P;
	NTT(a,-1);
	LL inv_Lim=Pow(Lim,P-2);
	for(int i=0;i<=n+m;i++)
		a[i]=a[i]*inv_Lim%P;
	for(int i=1;i<=n;i++)
		printf("%lld\n",a[n+i]*inv[i]%P);
	return 0;
}

Measured memory_bytes: 166656
#include <bits/stdc++.h>
typedef long long ll;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define pb push_back
#define mp make_pair
#define all(x) x.begin(),x.end()
#define br cout << endl;
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の数字をint型にしてアスキーコードになったら -48する
// 切り上げ　ceil(a)



int main() {
    ll n, w;
    cin >> n >> w;

    vector<ll> weight(n);
    vector<ll> value(n);
    vector<vector<ll>> dp(n+1, vector<ll>(w+1));

    rep(i,n){
        cin >> weight.at(i) >> value.at(i);
    }

    rep(i,n){
        for(ll sum_w = 0; sum_w <= w; sum_w++){
            if(sum_w - weight.at(i) >= 0){
                chmax(dp.at(i+1).at(sum_w), dp.at(i).at(sum_w - weight.at(i)) + value.at(i));
            }
            
            chmax(dp.at(i+1).at(sum_w), dp.at(i).at(sum_w));
        }
    }

    cout << dp.at(n).at(w) << endl;

}


Measured memory_bytes: 80256
#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) { cout << #a << " = " << a << endl; }
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); }

#define UNIQUE(xs) sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end());

typedef long long ll;

int G[4040][4040];

int main() {

  int N; cin >> N;
  vector<int> xs, ys;
  vector<int> inx[2], iny[2];
  rep(i, 2) inx[i].resize(N), iny[i].resize(N);
  rep(i, N) {
    cin >> inx[0][i] >> iny[0][i] >> inx[1][i] >> iny[1][i];
    xs.push_back(inx[0][i]), xs.push_back(inx[1][i]);
    ys.push_back(iny[0][i]), ys.push_back(iny[1][i]);
  }

  auto lp = [&](vector<int>& xs, int x) {
    return lower_bound(all(xs), x) - xs.begin();
  };

  UNIQUE(xs);
  UNIQUE(ys);

  const int CMaxX = xs.size(), CMaxY = ys.size();

  rep(i, N) {
    G[lp(ys, iny[0][i])][lp(xs, inx[0][i])]++;
    G[lp(ys, iny[0][i])][lp(xs, inx[1][i])]--;
    G[lp(ys, iny[1][i])][lp(xs, inx[0][i])]--;
    G[lp(ys, iny[1][i])][lp(xs, inx[1][i])]++;
  }

  rep(i, CMaxY + 1)
    REP(j, 1, CMaxX + 1)
      G[i][j] += G[i][j - 1];

  REP(i, 1, CMaxY + 1)
    rep(j, CMaxX + 1)
      G[i][j] += G[i - 1][j];

  ll ans = 0;

  rep(y, ys.size() - 1) rep(x, xs.size() - 1) {
    if(G[y][x])
      ans += (ll)(ys[y + 1] - ys[y]) * (xs[x + 1] - xs[x]);
  }

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

Measured memory_bytes: 66384
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100000];
long long b[100000];
int main(){
	cin>>n;
	for(int i=0;i<n;i++)	cin>>a[i];
	for(int i=0;i<n;i++)	cin>>b[i];
	long long k=0;
	for(int i=0;i<n;i++)	k+=b[i]-a[i];
	long long two=0;
	for(int i=0;i<n;i++)
	{
		long long d=b[i]-a[i];
		if(d>0)	two+=(d+1)/2;
	}
	if(two>k) cout<<"No"<<endl;
	else cout<<"Yes"<<endl;
}

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

int main() {
  int N,K;
  cin >> N >> K;
  double ans = 0;
  for(int i = 1; i <= N; i++) {
    double tmp = 1.0 / N;
    for (int p = i;p < K;) {
      p *= 2;
      tmp /= 2; 
    }
    ans += tmp;
  }
  cout << fixed << setprecision(12);
  cout << ans << endl;
}

Measured memory_bytes: 256
S = input()
numQ = int(input())
lead = 1
front = ""
rear = ""
for i in range(numQ):
  Q = input()
  if Q[0] == "1":
    lead *= -1
  else:
    if Q[2] == "1":
      if lead == 1:
        front = Q[4] + front
      else:
        rear = rear + Q[4]
    else:
      if lead == 1:
        rear = rear + Q[4]
      else:
        front = Q[4] + front
S = front + S + rear
if lead == -1:
  S = S[::-1]

print(S)
      
      

Measured memory_bytes: 4436
#include <bits/stdc++.h>
#define llint long long
#define mod 1000000007

using namespace std;

string s;
llint suma[100005], sumc[100005], sumq[100005];
llint beki[100005];

llint calc(llint x, llint y)
{
	if(y == 0) return x / 3;
	return x * beki[y-1] % mod;
}

int main(void)
{
	cin >> s;
	int n = s.size();
	s = "#" + s;
	
	llint mul = 1;
	for(int i = 0; i < 100005; i++) beki[i] = mul, mul *= 3, mul %= mod;
	
	for(int i = 1; i <= n; i++){
		suma[i] = suma[i-1];
		sumc[i] = sumc[i-1];
		sumq[i] = sumq[i-1];
		
		if(s[i] == 'A') suma[i] +=  3;
		if(s[i] == 'C') sumc[i] +=  3;
		if(s[i] == '?'){
			suma[i] += 1;
			sumc[i] += 1;
			sumq[i] += 1;
		}
	}
	
	llint ans = 0;
	for(int i = 1; i <= n; i++){
		if(s[i] == '?' || s[i] == 'B'){
			ans += calc(suma[i-1], sumq[i-1]) * calc(sumc[n] - sumc[i], sumq[n] - sumq[i]) % mod;
			ans %= mod;
		}
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 3580
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep1(i, n) for (ll i = 1; i < (ll)(n); i++)
const ll mo = 1000000007;
const ll INF = 1LL << 60; //MAX 9223372036854775807
ll ans = 0;

int main()
{
    ll q;
    cin >> q;
    multiset<ll> slow;
    multiset<ll> shigh;
    ll cons = 0;
    ll fx = 0;
    ll med = INF;
    vector<ll> v;
    vector<ll> v1;
    ll le;
    rep(i, q)
    {
        ll a;
        cin >> a;
        if (a == 1)
        {
            ll b, c;
            cin >> b >> c;
            cons += c;
            if (med < b){
                shigh.insert(b);
            }
            else{
                slow.insert(b);
            }

            if (shigh.size() > slow.size())
            {
                auto itr = shigh.begin();
                slow.insert(*itr);
                shigh.erase(shigh.begin());
            }

            else if (shigh.size() + 1 < slow.size())
            {
                auto itr = slow.end();
                itr--;
                shigh.insert(*itr);
                slow.erase(itr);
            }

            auto itrr = slow.end();
            itrr--;
            if(i!=0&&shigh.size() == slow.size())fx+=abs(med-b);
            else if(i!=0&&shigh.size() != slow.size()&&med>b)fx+=abs(med-b);
            else if(i!=0&&shigh.size() != slow.size()&&le<b)fx+=abs(le-b);
            med = *itrr;
            le=*shigh.begin();

        }
        else
        {
            v.push_back(med);
            v1.push_back(fx + cons);
        }
    }
    for (int i = 0; i < v.size(); ++i) {
    cout << v[i] << " "<<v1[i]<< endl;;
    }
    return 0;
}

Measured memory_bytes: 9600
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
 
using namespace std;
 
vector<int> G[500];
int dist[500];
 
int main()
{
    int n, m;
     
    while (scanf("%d\n%d", &n, &m) && n){
        for (int i = 0; i < n; i++) G[i].clear();
        for (int i = 0; i < m; i++){
            int a, b;
            scanf("%d %d", &a, &b);
            G[--b].push_back(--a);
            G[a].push_back(b);
        }
         
        memset(dist, -1, sizeof(dist));
         
        int ans = 0;
        queue<int> q;
         
        for (q.push(0); q.size(); q.pop()){
            int x = q.front();
             
            if (dist[x] < 0) dist[x] = 0;
            if (dist[x] <= 2) ans++;
             
            for (int i = 0; i < G[x].size(); i++){
                if (dist[G[x][i]] >= 0) continue;
                else dist[G[x][i]] = dist[x] + 1;
                q.push(G[x][i]);
            }
        }
         
        printf("%d\n", ans - 1);
    }
     
    return (0);
}

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

int main() {
  int n;
  cin >> n;
  vector<int> mochi(n);
  for (int i=0; i<n; i++) {
    cin >> mochi.at(i);
  }
  int sum=1;
  for (int i=1; i<n; i++) {
    for (int j=i-1; j>=0; j--) {
      if (mochi.at(i) == mochi.at(j))
        break;
      if (j==0)
        sum++;
    }
  }
  cout << sum;
}


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

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

bool used[100005];
int N;
vector<int> G[100005];
vector<int> way;

bool dfs(int now){
    used[now] = true;
    way.push_back(now);
    if(now == N) return true;
    for (int i = 0;i < G[now].size();i++){
        if(!used[G[now][i]] && dfs(G[now][i])) return true;
    }
    used[now] = false;
    way.pop_back();
    return false;
}

int dfs2(int now, int mid){
    used[now] = true;
    int ret = 0;
    if(now == mid) return 0;
    for (int i = 0;i < G[now].size();i++){
        if(!used[G[now][i]]) ret += dfs2(G[now][i],mid);
    }
    used[now] = false;
    return ret+1;
}

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

    cin >> N;

    for (int i = 0;i < N-1;i++){
        int a,b; cin >> a >> b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    memset(used,0,sizeof(used));
    dfs(1);
    
    memset(used,0,sizeof(used));
    int mid = way[(way.size()+1)/2];
    int fsum = dfs2(1,mid);
    //cout << mid << " " <<  fsum << endl;

    if(fsum > N-fsum) cout << "Fennec" << endl;
    else cout << "Snuke" << endl;

    return 0;

}

Measured memory_bytes: 9464
N,M = map(int, input().split())
switch = []
for idx in range(M):
	tmp = [ int(x) - 1 for x in input().split()]
	tmp = tmp[1:]
	switch.append(set(tmp))
P = list(map(int, input().split()))

ans = 0
for combi in range(2**N):
	ok = True
	for idx in range(len(switch)):
		count = 0
		for i in range(N):
			if((combi>>i)&1 and  i in switch[idx]):
				count += 1
		if(count%2 != P[idx]):
			ok = False

	if(ok):
		ans += 1
print(ans)

Measured memory_bytes: 42224
#include<bits/stdc++.h>
using namespace std;
#define MN 300
#define mod 1000000007
const int inv=(mod+1)/2;
inline int read()
{
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-') f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}
bool b1[MN*2+5],b2[MN*2+5];
int n,a[MN*2+5],f[MN*2+5][MN+5][MN+5];
int main()
{
    n=read();int emp=0;
    for(int i=1;i<=n;++i)
    {
        int x=read(),y=read();
        if(x==-1&&y==-1) ++emp;
        else if(x>0&&y>0) b2[2*n+1-x]=b2[2*n+1-y]=1;
        else b1[2*n+1-max(x,y)]=1;
    }
    f[0][0][0]=1;int p=0;
    for(int i=1;i<=n*2;++i) if(!b2[i]) 
    {
        for(int j=0;j<=n;++j) for(int k=n-j;~k;--k) if(f[p][j][k])
        {
            if(b1[i])
            {
                if(j) f[i][j-1][k]=(f[i][j-1][k]+f[p][j][k])%mod;
                f[i][j][k+1]=(f[i][j][k+1]+f[p][j][k])%mod;
            }
            else
            {
                f[i][j-1][k]=(f[i][j-1][k]+f[p][j][k])%mod;
                f[i][j+1][k]=(f[i][j+1][k]+f[p][j][k])%mod;
                if(k) f[i][j][k-1]=(f[i][j][k-1]+1LL*f[p][j][k]*k)%mod;
            }
        }
        p=i;
    }
    int ans=f[p][0][0];
    for(int i=1;i<=emp;++i) ans=1LL*ans*i%mod;
    printf("%d\n",ans);
    return 0;
}

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

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef vector<ii> vii;
typedef vector<int> vi;
typedef long long ll;
typedef long double ld;
typedef vector<ll> vll;
typedef pair<ll,ll> lll;

const ll MOD = 1000000007;
const ll INF = 1e9+5;
const double eps = 1e-7;
const double PI = acos(-1.0);

#define FOR(i,a,b) for(long long i = (long long)(a); i < (long long)(b); i++)
#define RFOR(i,a,b) for(long long i = (long long)(a); i >= (long long)(b); i--)
#define ull unsigned long long
#define deb(x )     cerr << #x << " = "<< x << endl;
#define endl    "\n"
#define coud(a,d) cout << fixed << showpoint << setprecision(d) << a;
#define ff first
#define ss second
#define mp make_pair
#define pb push_back
#define fill(x, y) memset(x, y, sizeof(y))
#define all(x) (x).begin(), (x).end()
#define bitcount(x) __builtin_popcount(x)
#define cps CLOCKS_PER_SEC
#define verify(x) if(x >= MOD) x -= MOD;

inline void debug_vi(vi a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void debug_vll(vll a) {FOR(i, 0, a.size()) cout<<a[i]<<" ";}
inline void print_case(int tn) {cout<<"Case #"<<tn<<": ";}

template<typename T>
using minpq = priority_queue<T, vector<T>, greater<T>>;

template<typename T>
using maxpq = priority_queue<T>;
/*----------------------------------------------------------------------*/

int main(){
    std::ios::sync_with_stdio(false);cin.tie(NULL); cout.tie(NULL);
    // freopen("input.txt", "r", stdin);
    // freopen("output.txt", "w", stdout);

    ll a,v; cin>>a>>v;
    ll b,w; cin>>b>>w;
    ll t; cin>>t;

    ll d = abs(b - a);
    ll rv = v - w;

    if(rv > 0 && d <= rv * t) {
        cout<<"YES";
    } else cout<<"NO";

    return 0;
}

Measured memory_bytes: 3636
/** Which of the favors of your Lord will you deny ? **/

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

#define LL long long
#define PII pair<int,int>
#define PLL pair<LL,LL>
#define MP make_pair
#define F first
#define S second

#define ALL(x) (x).begin(), (x).end()
#define DBG(x) cerr << __LINE__ << " says: " << #x << " = " << (x) << endl
#define READ        freopen("alu.txt", "r", stdin)
#define WRITE       freopen("vorta.txt", "w", stdout)

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<class TIn>using indexed_set = tree<TIn, null_type, less<TIn>,rb_tree_tag, tree_order_statistics_node_update>;

/**

PBDS
-------------------------------------------------
1) insert(value)
2) erase(value)
3) order_of_key(value) // 0 based indexing
4) *find_by_order(position) // 0 based indexing

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p);
template <class T>
ostream &operator <<(ostream &os, vector<T>&v);
template <class T>
ostream &operator <<(ostream &os, set<T>&v);

inline void optimizeIO()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}

const int nmax = 1e2+7;
const int nmax2 = 1e5+7;
const LL LINF = 1e17;

template <class T>
string to_str(T x)
{
    stringstream ss;
    ss<<x;
    return ss.str();
}

//bool cmp(const PII &A,const PII &B)
//{
//
//}

LL w[nmax];
LL v[nmax];

LL dp[nmax][nmax2];

LL solve(int pos,int W)
{
    if(W<0)
        return INT_MIN;

    if(pos<=0 || W==0)
        return 0;

    LL &ret = dp[pos][W];
    if(ret!=-1) return ret;

    LL inc = solve(pos-1,W-w[pos]) + v[pos];
    LL exc = solve(pos-1,W);

    return ret = max(inc,exc);
}

int main()
{
    optimizeIO();

    int n,W;
    cin>>n>>W;

    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];

    memset(dp,-1,sizeof dp);

    cout<<solve(n,W)<<endl;

    return 0;
}

/**

**/

template<class T1, class T2>
ostream &operator <<(ostream &os, pair<T1,T2>&p)
{
    os<<"{"<<p.first<<", "<<p.second<<"} ";
    return os;
}
template <class T>
ostream &operator <<(ostream &os, vector<T>&v)
{
    os<<"[ ";
    for(int i=0; i<v.size(); i++)
    {
        os<<v[i]<<" " ;
    }
    os<<" ]";
    return os;
}

template <class T>
ostream &operator <<(ostream &os, set<T>&v)
{
    os<<"[ ";
    for(T i:v)
    {
        os<<i<<" ";
    }
    os<<" ]";
    return os;
}




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

int main(){
  int A, B, C, D;
  cin >> A >> B >> C >> D;
  while(1){
    C -= B;
    A -= D;
    if(C <= 0){
      cout << "Yes" << endl;
      break;
    }
    if(A <= 0){
      cout << "No" << endl;
      break;
    }
  }
}


Measured memory_bytes: 3596
/*"You can do anything you set your mind to,man" - Eminem*/
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define llpow(a,b) (ll)(pow(a,b)+0.5)
#define l_b(a,val) min((int)a.size()-1, (int)(lower_bound(a.begin(),a.end(),val)-a.begin()))
#define f first
#define up(a,b) max(a,b)
#define s second
#define INF 9223372036854775807
const  int mod = 1000000007;
template <typename T> T add(T& a, T b){a+=b;while(a>=mod)a-=mod;while(a<0)a+=mod;}
template <typename T> T mul(T& a, T b){a*=b;while(a>=mod)a-=mod;while(a<0)a+=mod;}
template <typename T> T up_self(T& a, T b){a = up(a,b);}
template <typename T> T min_self(T& a, T b){a = min(a,b);}
ll binexpomodulo(ll x, ll y){ll res =1;x%=mod;if(!x)return 0;while(y){if(y&1){mul(res, x);}mul(x,x);y>>=1;}return res;}
ll nCrInOr(ll n, ll r){ll res = 1;if(r>n-r)r = n-r;ll rin = 1;for(ll i = 1; i <=r ; i++)rin = (rin*i)%mod;rin = binexpomodulo(rin,mod-2);for(ll i = 1; i <= r; i++)res = (res*(n-i+1))%mod;res = (res*rin)%mod;return res;}
int msb(ll n){int ans;for(int i = 0 ; i < 64;  i++)if(n&(1LL<<i))ans = i+1;return ans;}
int main()
{
	int n; cin>>n;
	vector<vector<ll>> dp(n,vector<ll> (n));
	ll a[n];
	for(int i = 0 ; i < n; i++)
		cin>>a[i];	
	for(int l = n-1; l>=0; l--){
		for(int r = l; r<n; r++){
			if(l==r)
				dp[l][r] = a[l];
			else
				dp[l][r] = up(a[r]-dp[l][r-1],a[l]-dp[l+1][r]); 
		}
	}
	cout<<dp[0][n-1]<<endl;
  	return 0;
}

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

const int dx[4] = {1,0,-1,0};
const int dy[4] = {0,1,0,-1};

int main(){

    int h, w, ch, cw, dh, dw;
    cin >> h >> w >> ch >> cw >> dh >> dw;
    ch--; cw--; dh--; dw--;
    vector<string> s(h);
    rep(i,h) cin >> s[i];

    vector<vector<int>> dist(h, vector<int>(w, -1));
    dist[ch][cw] = 0;

    deque<P> que;
    que.push_front(P(ch,cw));

    while(!que.empty()){
        auto pos = que.front();
        int x = pos.first;
        int y = pos.second;
        que.pop_front();
        if(x == dh && y == dw){
            cout << dist[x][y] << endl;
            return 0;
        }

        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
            if(s[nx][ny] == '#') continue;
            if(dist[nx][ny] <= dist[x][y] && dist[nx][ny] != -1) continue;

            que.push_front(P(nx,ny));
            dist[nx][ny] = dist[x][y];
        }

        for(int i = -2; i <= 2; i++){
            for(int j = -2; j <= 2; j++){
                int nx = x + i;
                int ny = y + j;

                if(nx < 0 || nx >= h || ny < 0 || ny >= w) continue;
                if(s[nx][ny] == '#') continue;
                if(dist[nx][ny] <= dist[x][y] + 1 && dist[nx][ny] != -1) continue;

                dist[nx][ny] = dist[x][y] + 1;
                que.push_back(P(nx,ny));
            }
        }
    }
    cout << dist[dh][dw] << endl;
}

Measured memory_bytes: 9504
import collections

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

v0 = v[0::2]
v1 = v[1::2]

c0 = collections.Counter(v0)
c1 = collections.Counter(v1)

ans0 = n//2 - c0.most_common()[0][1]
ans1 = n//2 - c1.most_common()[0][1]

if c0.most_common()[0][0] == c1.most_common()[0][0]:
    if len(c0.most_common()) > 1:
        ans0_1 = n//2 - c0.most_common()[1][1]
    else:
        ans0_1 = n//2

    if len(c1.most_common()) > 1:
            ans1_1 = n//2 - c1.most_common()[1][1]
    else:
        ans1_1 = n//2

    ans = min(ans0 + ans1_1, ans0_1 + ans1)
else:
    ans = ans0 + ans1

print(ans)

Measured memory_bytes: 19040
#include <bits/stdc++.h>
using namespace std;
#include <math.h>
#include <iomanip>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

const int mod=1e9+7;
const int INF=1001001001;

int main() {
  int N;
  cin>>N;
  vector<int64_t>A(N);
  int64_t sum=0;
  for(int i=0;i<N;i++){
    cin>>A[i];
    sum+=A[i];
    sum%=mod;
  }
  int64_t ans=0;
  for(int i=0;i<N;i++){
    sum-=A[i];
    if(sum<A[i]){sum+=mod;}
    ans+=(A[i]*sum);
    ans%=mod;
  }
  cout<<ans<<endl;
  return 0;  
}

Measured memory_bytes: 4772
def sieve(n):
    prime=[]
    limit=n**0.5
    data=[i+1 for i in range(1,n)]
    while True:
        p=data[0]
        if limit<=p:
            return prime+data
        prime.append(p)
        data=[e for e in data if e%p!=0]

def main():
    n=int(input())
    primes=sieve(n+1)
    l=len(primes)

    factor=[]
    for i in range(l):
        p = primes[i]
        cnt = 0
        fac = p
        while fac <= n:
            cnt += n//fac
            fac *= p
        factor.append(cnt)
    
    l2=len(factor)
    idx=[0,0,0,0,0]
    fac=[2,4,14,24,74]
    j,i=4,0
    while i<l2:
        if  factor[i] < fac[j]:
            idx[j] = i
            j-=1
            if j==-1:
                break
        else:
            i+=1

    ans=idx[4]+idx[3]*max(0,idx[0]-1)+idx[2]*max(0,idx[1]-1)+idx[1]*max(0,idx[1]-1)*max(0,idx[0]-2)//2
    print(ans)

if __name__=='__main__':
    main()

Measured memory_bytes: 3188
def myAnswer(N:int,M:int,dic:dict)-> None:
   for i in dic.values():
      print(i)
   

def modelAnswer():
   tmp=1
def main():
   N,M = map(int,input().split())
   dic ={key:0 for key in range(1,N+1)}
   for _ in range(M):
      a,b = map(int,input().split())
      dic[a]+=1
      dic[b]+=1
   myAnswer(N,M,dic)

if __name__ == '__main__':
   main()

Measured memory_bytes: 3064
#include <cstdio>
#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>
#include <algorithm>

using namespace std;

int main() {
    int A, B;
    int answer;
    double smallA, smallB;
    double x, y;

    cin >> A >> B;

    answer = (100.0 / 8.0) * A;
    smallA = modf(answer * 0.08, &x);
    smallB = modf(answer * 0.1, &y);

while(true) {

    smallA = modf(answer * 0.08, &x);
    smallB = modf(answer * 0.1, &y);

    if (x == A && y == B) {
        cout << answer << endl;
        break;
    }

    if (x > A) {
        printf("-1\n");
        break;
    }

    answer++;
    //printf("x = %lf y = %lf\n", x, y);
}

    return 0;
}

Measured memory_bytes: 256
def main():
    n, factor = getInputs()

    points = []
    for i in range(n):
        points.append([0] * 3)

    # points[day][pile]
    for pile in range(3):
        points[0][pile] = factor[0][pile]

    for day in range(1, n):
        points[day][0] = max(points[day - 1][1], points[day - 1][2]) + factor[day][0]
        points[day][1] = max(points[day - 1][0], points[day - 1][2]) + factor[day][1]
        points[day][2] = max(points[day - 1][0], points[day - 1][1]) + factor[day][2]

    print(max(points[-1]))

def getInputs():
    n = int(input())

    factor = []
    for i in range(n):
        factor.append(tuple(map(lambda x: int(x), input().split())))

    return n, factor

main()


Measured memory_bytes: 106372
n, k, c = map(int, input().split())
s = input()

left = [0] * (n+1)
right = [0] * (n+1)

for i in range(1, n+1):
    if s[i-1] == 'o':
        if i - 1 - c >= 0:
            left[i] = max(left[i-1], left[i-1-c] + 1)
        else:
            left[i] = 1
    else:
        left[i] = left[i-1]

for i in reversed(range(n)):
    if s[i] == 'o':
        if i + 1 + c < n:
            right[i] = max(right[i+1], right[i+1+c] + 1)
        else:
            right[i] = 1
    else:
        right[i] = right[i+1]

l = 0
r = 0

end = False
ans = []
for i in range(n):
    if left[l] > 0:
        r = max(r, l+c, i+1)
    else:
        r = max(r, i+1)
    r = min(r, n)
    while r <= n and left[l] + right[r] < k and l <= i:
        l += 1
        r = max(r, l+c-1)
    if l > i:
        ans.append(i+1)
    if r > n:
        if left[i] < k:
            ans.append(i+1)

for x in ans:
    print(x)

Measured memory_bytes: 28520
PROGRAM taxRate
      IMPLICIT NONE
      integer :: n
      integer :: i,x
      
      read*,n
      
      do i = 1,n
        x = i * 108 / 100
        if( x==n ) goto 100
      end do
      
      
      print'(a)',':('
      RETURN
      
 100  continue
      print*,i
      
      
      
      
      
      END PROGRAM

Measured memory_bytes: 768
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<int(n);i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define show(x) cout<< #x << " = " << x << endl
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int vx[]={0,0,-1,1};
int vy[]={1,-1,0,0};
int dx[]={1,0,-1,1,-1,1,0,-1};
int dy[]={1,1,1,0,0,-1,-1,-1};

int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}	

const ll mod=1e9+7;
const int INF=INT_MAX/2;
const int N_MAX=100010;

int main(){
	int a,b;
	cin>>a>>b;
	int c=b-a;
	cout<<(1+c)*c/2-b<<endl;
	return 0;
}


Measured memory_bytes: 256