akhauriyash/Code-Regression huggingface dataset:
N,M=map(int,input().split())
LRC=sorted([list(map(int,input().split())) for i in range(M)],key=lambda x:x[0])
class rmq:
    def __init__(self,N):
        self.N0=2**(N-1).bit_length()
        self.INF=2**63-1
        self.data=[self.INF]*(2*self.N0)
        self.lazy=[None]*(2*self.N0)
    def gindex(self,l, r):
        L = l + self.N0; R = r + self.N0
        lm = (L // (L & -L)) >> 1
        rm = (R // (R & -R)) >> 1
        while L < R:
            if R <= rm:
                yield R
            if L <= lm:
                yield L
            L >>= 1; R >>= 1
        while L:
            yield L
            L >>= 1
    def propagates(self,*ids):
        for i in reversed(ids):
            v = self.lazy[i-1]
            if v is None:
                continue
            self.lazy[2*i-1] = self.data[2*i-1] = self.lazy[2*i] = self.data[2*i] = v
            self.lazy[i-1] = None
    def update(self,l, r, x):
        *ids, = self.gindex(l, r)
        self.propagates(*ids)
        L = self.N0 + l; R = self.N0 + r
        while L < R:
            if R & 1:
                R -= 1
                self.lazy[R-1] = self.data[R-1] = x
            if L & 1:
                self.lazy[L-1] = self.data[L-1] = x
                L += 1
            L >>= 1; R >>= 1
        for i in ids:
            self.data[i-1] = min(self.data[2*i-1], self.data[2*i])
    def rmin(self,l, r):
        self.propagates(*self.gindex(l, r))
        L = self.N0 + l; R = self.N0 + r
        s = self.INF
        while L < R:
            if R & 1:
                R -= 1
                s = min(s, self.data[R-1])
            if L & 1:
                s = min(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
d=rmq(N)
d.update(0,1,0)
for l,r,c in LRC:
    d.update(r-1,r,min(d.data[d.N0+r-2],d.rmin(l-1,r-1)+c))
a=d.rmin(N-1,N)
print(a if a<d.INF else -1)

Measured memory_bytes: 129752
import java.util.*;
import java.io.*;
import java.math.*;
 
public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] li = new int[n];
        for(int i = 0; i < n-1; i++) li[sc.nextInt()-1]++;
        for(int i : li) System.out.println(i);
    }

}


Measured memory_bytes: 57804
#include <algorithm>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
#include <cstdio>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>

using namespace std;

int main(int argc, char *argv[])
{
  int N, t[123456], x[123456], y[123456];
  cin >> N;
  for (int i = 0; i < N; i++) cin >> t[i] >> x[i] >> y[i];

  int j = 0, nx = 0, ny = 0;
  for (int i = 0; i < N; i++) {
    for (; j < t[i]; j++) {
      if (nx != x[i]) {
        nx += (nx < x[i] ? 1 : -1);
      } else {
        ny += (ny < y[i] ? 1 : -1);
      }
    }

    if (nx != x[i] || ny != y[i]) {
      puts("No");
      return 0;
    }
  }

  puts("Yes");
  return 0;
}


Measured memory_bytes: 1408
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v){std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}


int main() {

    long long L, K;
    cin >> L >> K;

    vector<long long> a(2);
    a[0] = 2;
    a[1] = K + 1;

    vector<long long> dp1(L + 1, 0);

    if (1 <= L) dp1[1]++;
    if (K <= L) dp1[K]++;

    for (int i = 0; i <= L; i++) {
        for (int j = 0; j < 2; j++) {
            int to = i + a[j];
            if (to <= L) dp1[to] += dp1[i];
        }
    }

    long long ans = accumulate(dp1.begin(), dp1.end(), 0LL);
    cout << ans << endl;

}














































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

int main() {
  int countFive = 0; int countSeven = 0;

  for (int i = 0; i <3; i++) {
    int x; cin >> x;
    if (x == 5)
      ++countFive;
    else if (x == 7)
      ++countSeven;
  }
  if (countFive == 2 && countSeven == 1)
    cout << "YES" << endl;
  else
    cout << "NO" << endl;

  return 0;
}
  

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> pv, nv;
	for(int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if(x >= 0) {
			pv.push_back(x);
		} else {
			nv.push_back(-x);
		}
	}
	reverse(nv.begin(), nv.end());
	int ans = INT_MAX;
	for(int i = 0; i <= k; i++) {
		if(nv.size() < k - i || pv.size() < i) {
			continue;
		}
		if(i == 0) {
			int n_len = nv[k - i - 1];
			ans = n_len < ans ? n_len : ans;
			continue;
		}
		if(i == k) {
			int p_len = pv[i - 1];
			ans = p_len < ans ? p_len : ans;
			continue;
		}
		int n_len = nv[k - i - 1];
		int p_len = pv[i - 1];
		int tmp = n_len + p_len + (n_len > p_len ? p_len : n_len);
		if(ans > tmp)
			ans = tmp;
	}
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 1020
#!/usr/bin/env python3
def main():
    def expected_val(limit):
        return (1 + limit) / 2

    N, K = map(int, input().split())
    P = [int(x) for x in input().split()]

    lst = [0]
    res = 0
    for p in P:
        # res += (p + 1) / 2
        res += expected_val(p)
        lst.append(res)
    ans = 0
    for i in range(N - K + 1):
        res = lst[i + K] - lst[i]
        ans = res if res > ans else ans
    print(ans)


if __name__ == '__main__':
    main()


Measured memory_bytes: 31904
// https://atcoder.jp/contests/abc134/tasks/abc134_a

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

typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
#define INF (1e9)
#define INFL (1e18)
#define MOD (1000000007)
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REPR(i, n) for (int i = n; i >= 0; i--)
#define FOREACH(x, a) for (auto &(x) : (a))
#define ALL(obj) (obj).begin(), (obj).end()
#define ALLR(obj) (obj).rbegin(), (obj).rend()
#define LEN(x) (sizeof(x) / sizeof(*(x)))
// ll gcd(long a, long b) { return b ? gcd(b, a % b) : a; }
// ll lcm(long a, long b) { return a * b / gcd(a, b); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int r;
    cin >> r;
    cout << (3 * r * r) << endl;

    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;

int main(){
	//データの読み込み
	int N;
	cin >> N;
	vector<int> vec(N, -1);
	for (int i = 0; i < N; ++i){
		cin >> vec[i];
	}

	//偶奇判定
	int cnt = 0;
	bool alleven = true;
	while(alleven) {
		for (int i = 0; i < N; ++i){
			if(vec[i]&1 == 1){
				alleven = false;
				break;
			} else {
				vec[i] = vec[i] >> 1;
			}
		}
		if(alleven){
			cnt++;
		}
	}

	printf("%d\n", cnt);

	return 0;
}


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

int main(){
    int num[3];
    cin>>num[0]>>num[1]>>num[2];
    int tmp,i,j;
    for(i=0;i<2;i++){
        for(j=i+1;j<3;j++){
            if(num[i]>num[j]){
                tmp=num[i];
                num[i]=num[j];
                num[j]=tmp;
            }
        }
    }

    cout<<num[0]<<" "<<num[1]<<" "<<num[2]<<endl;

    return 0;
}


Measured memory_bytes: 3036
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
#include <map>
#include <queue>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using namespace std;

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

map<ll, ll> m;

ll f(ll n){
    if(m[n] != 0) return m[n];
    if(n%2 == 0) {
        return (m[n] = (f(n/2) + 2*f(n/2-1)) % MOD);
    }
    else return (m[n] = (2*f(n/2) + f(n/2-1)) % MOD);
}

int main() {
    ll n;
    cin >> n;
    m[0] = 1;
    m[1] = 2;
    cout << f(n) << "\n";
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
#define rep(i,n) for(int i = 0; i < (n); ++i)
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
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; }

int main(){
	cin.tie(0);
	ios::sync_with_stdio(false);
	ll x, y;
	cin >> x >> y;
	int ans = 0;
	while(x <= y){
		x *= 2;
		++ans;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 384
import java.util.Scanner;

public class Main {
	static Scanner in = new Scanner(System.in);
	public static void main(String[] args) {
		int n = Integer.parseInt(in.nextLine());
		String s = in.nextLine(), t = in.nextLine();
		
		int max = 0;
		for(int i = 0; i < n; i++){
			String ts = s.substring(s.length() - 1 - i, s.length());
			String tt = t.substring(0, i + 1);
			if(ts.equals(tt)){
				max = i + 1;
			}
		}
		System.out.println(n * 2 - max);
	}
}


Measured memory_bytes: 23124
#include<cstdio>

int main()
{
	int a,b;
	while(scanf("%d %d",&a,&b)!=EOF)
	{
		int count=1;
		double d=a+b;
		while(d>=10)
		{
			d/=10;
			count++;
		}
		printf("%d\n",count);
	}
	return 0;
}

Measured memory_bytes: 0
import sys
from collections import deque

def main():
    input = sys.stdin.readline
    N = int(input())
    q = deque([[1, 1]])
    d = {1: 1}
    while q:
        n, c = q.popleft()
        a = (n * 10) % N
        if a not in d or d[a] > c:
            d[a] = c
            q.appendleft([a, c])

        b = (n + 1) % N
        if b not in d or d[b] > c+1:
            d[b] = c + 1
            q.append([b, c+1])

    print(d[0])


if __name__ == '__main__':
    main()


Measured memory_bytes: 19720
#include <iostream>
    #include <vector>
    #include <algorithm>
    #include <tuple>
    using namespace std;
     
    long long N, X[1009], Y[1009], H[1009]; vector<tuple<long long, long long, long long>>vec;
     
    int main() {
    	cin >> N; tuple<long long, long long, long long>G = make_tuple(-1, -1, -1);
    	for (int i = 1; i <= N; i++) {
    		cin >> X[i] >> Y[i] >> H[i];
    		if (H[i] >= 1) G = make_tuple(X[i], Y[i], H[i]);
    	}
    	for (int i = 0; i <= 100; i++) {
    		for (int j = 0; j <= 100; j++) {
    			long long V = get<2>(G) + abs(get<0>(G) - i) + abs(get<1>(G) - j); V = max(V, 0LL); bool flag = true;
    			for (int k = 1; k <= N; k++) {
    				long long VV = V - abs(X[k] - i) - abs(Y[k] - j); VV = max(VV, 0LL);
    				if (H[k] != VV) flag = false;
    			}
    			if (flag == true) vec.push_back(make_tuple(i, j, V));
    		}
    	}
    	if (vec.size() == 1) {
    		cout << get<0>(vec[0]) << " " << get<1>(vec[0]) << " " << get<2>(vec[0]) << endl;
    	}
    	return 0;
    }

Measured memory_bytes: 256
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using static System.Console;

class Program
{
    static void Main(string[] args)
    {
        var NK = ReadLine().Split(' ').Select(s => int.Parse(s)).ToArray();
        var (N, K) = (NK[0], NK[1]);
        var S = ReadLine().ToCharArray();

        S[K - 1] = (char)(S[K - 1] + 32);

        var ans = new string(S);

        WriteLine(ans);
    }
}


Measured memory_bytes: 28228
#include <bits/stdc++.h>
using namespace std;
using int64 = long long;
#define int int64
#define rep(i, n) for(int i=0; i<n; i++)
#define FOR(i, a, b) for(int i=a; i<b; i++)
#define SORT(x) sort(x.begin(), x.end())
#define GSORT(x) sort(x.begin(), x.end(), greater<int>())
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define ALL(x) x.begin(), x.end()
#define V(T) vector<T>
typedef pair<int, int> P;
typedef pair<P, P> PP;
typedef vector<int> vi;
typedef vector<vi> vvi;
int max(int a, int b) {if(b>a) return b; else return a;}
int min(int a, int b) {if(b<a) return b; else return a;}
const int INF = 1e18;

//***********************************
//mintを定義
//***********************************
const int mod = 998244353;
struct mint {
  int x;
  mint(int x=0):x(x%mod){}   //メンバ変数xをx%modで初期化
  int get() const { return (int)x; }
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;           //thisは暗黙的に左辺のポインタ
  }
  mint& operator-=(const mint a) {
    if ((x += mod-a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) const {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) const {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) const {
    mint res(*this);
    return res*=a;
  }
 
  //累乗
  mint mpow(int t) const {
    if (!t) return 1;
    mint a = mpow(t>>1);
    a *= a;
    if (t&1) a *= *this;
    return a;
  }
 
  //除算
  mint minv() const {
    return mpow(mod-2);
  }
  mint& operator/=(const mint a) {
    return (*this) *= a.minv();
  }
  mint operator/(const mint a) const {
    mint res(*this);
    return res/=a;
  }
};
 
//標準出力
ostream& operator<<(ostream& st, const mint a) 
{ st << a.get(); return st; };
//--------------------------------------------------
 
//***********************************
//場合の数の計算
//***********************************
const int MAX = 200010;
mint fac[MAX], finv[MAX];
 
//前計算
inline void INIT_F(){
    fac[0] = finv[0] = 1;
    for(int i=1; i<MAX-1; i++) {
        fac[i] = (fac[i-1]*mint(i));
        finv[i] = (finv[i-1]/mint(i));
    }
}
 
//nCk
mint mcomb(int n, int k) {
    if(n<k || k<0) return 0;
    else return ((fac[n]*finv[k])*finv[n-k]);
}
 
//nHk
mint mhcomb(int n, int k) {
  return mcomb(n+k-1, k);
}
//--------------------------------------------------

signed main() {
    INIT_F();
    int N, M, K;
    cin >> N >> M >> K;

    mint res = 0;
    rep(i, K+1) {
        mint t1 = M, t2=M-1;
        t1 *= t2.mpow(N-i-1);
        res += t1*mcomb(N-1, i);
    }

    cout << res << endl;

    return 0;
}

Measured memory_bytes: 6752
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define all(x) (x).begin(),(x).end()
typedef long long lint;
 
int main() {
  int x;
  cin >> x;
  
  if(x<100){
    cout << 0 << endl;
    return 0;
  }
  
  int target = x%100;
  int count = 0; //最低何個必要か
  
  while(target>0){
    for(int i=5;i>0;i--){
      if(target>=i){
        target -= i;
        count += 1;
        break;
      }
    }
  }
  
  if(x/100 >= count)cout << 1 << endl;
  else cout << 0 << endl;
}

Measured memory_bytes: 256
// -*- coding:utf-8-unix -*-

use proconio::input;

fn main() {
    input! {
        n: u64,
        m: u64,
        h: [u64; n],
        ab: [(u64, u64); m],
    }

    let mut good = Vec::with_capacity(n as usize);
    for _i in 0..n {
        good.push(1);
    }

    for pass in &ab {
        if h[(pass.0 - 1) as usize] > h[(pass.1 - 1) as usize] {
            good[(pass.1 - 1) as usize] = 0;
        } else if h[(pass.0 - 1) as usize] < h[(pass.1 - 1) as usize] {
            good[(pass.0 - 1) as usize] = 0;
        } else {
            good[(pass.0 - 1) as usize] = 0;
            good[(pass.1 - 1) as usize] = 0;
        }
    }

    println!("{}", good.into_iter().filter(|v| *v > 0).count());
}


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

string s;
int a;


int main(){
    cin>>s;
    a=s.length();
    for(int i=0;i<a;i++){
      if(i%2==0){
        cout << s[i];
      }
    }
    cout<<endl;
}

Measured memory_bytes: 3748
n = int(input())
mod = 10 ** 9 + 7
def power_func(a,n,p):
    bi = str(format(n,"b"))#2進表現に
    res = 1
    for i in range(len(bi)):
        res = (res*res) %p
        if bi[i] == "1":
            res = (res*a) %p
    return res
a1 = power_func(10,n,mod)
a2 = power_func(9,n,mod)
a3 = power_func(8,n,mod)
print((a1 + a3 - a2 * 2 + mod) % mod)

Measured memory_bytes: 61748
#include <bits/stdc++.h>
using namespace std;
using uint = unsigned int;
using lint = long long int;
using ulint = unsigned long long int;
template<class T = int> using V = vector<T>;
template<class T = int> using VV = V< V<T> >;
template<class T, class U> void assign(V<T>& v, int n, const U& a) { v.assign(n, a); }
template<class T, class... Args> void assign(V<T>& v, int n, const Args&... args) { v.resize(n); for (auto&& e : v) assign(e, args...); }


template<class Int> map<Int, int> factor(Int n) {
  map<Int, int> res;
  for (Int i = 2; i * i <= n; ++i) while (n % i == 0) ++res[i], n /= i;
  if (n != 1) ++res[n];
  return res;
}

lint powll(lint a, int n) {
  assert(n >= 0);
  lint res = 1;
  for (; n > 0; a *= a, n >>= 1) if (n & 1) res *= a;
  return res;
}

int main() {
  cin.tie(nullptr); ios_base::sync_with_stdio(false);
  lint n, p; cin >> n >> p;
  auto mp = factor(p);
  lint res = 1;
  for (const auto& e : mp) {
    res *= powll(e.first, e.second / n);
  }
  cout << res << '\n';
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define repr(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define invrepr(i,a,b) for(int i=b-1;i>=a;i--)
#define invrep(i,n) invrepr(i,0,n)
#define repitr(itr,a) for(auto itr=a.begin();itr!=a.end();++itr)
#define P pair<int,int>
const int MOD=1e9+7;
const int INF=2e9;

bool is_prime(ll n) {
    if (n==1) return false; 
    repr(i,2,int(sqrt(n)+1)) {
        if (n%i==0) return false;
    }
    return true;
}


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

    int q;
    cin >> q;
    vector<int> p(1e5+10),s(1e5+10);
    repr(i,1,1e5+10) {
        if (is_prime(i)) p[i]=1;
    }
    repr(i,1,1e5+10) {
        if (i%2==1 && p[i]==1 && p[(i+1)/2]==1) ++s[i];
        s[i]+=s[i-1];
    }
    rep(i,q) {
        int l,r;
        cin >> l >> r;
        cout << s[r]-s[l-1] << endl;
    }

    return 0;   
}


Measured memory_bytes: 1408
#include <iostream>

int main() {
  int N;
  std::cin >> N;
  if (N == 1) {
    std::cout << "Hello World" << std::endl;
  } else if (N == 2) {
    int A, B;
    std::cin >> A;
    std::cin >> B;
    std::cout << A + B << std::endl;
  }
}


Measured memory_bytes: 256
#include<cstdio>
#include<algorithm>
const int N=1e5+3;
int n,m,v,p,a[N],s;long long b[N];
bool Cmp(const int&a,const int&b){return a>b;}
int main(){
	scanf("%d%d%d%d",&n,&m,&v,&p);
	for(int i=1;i<=n;i++)scanf("%d",a+i);
	std::sort(a+1,a+1+n,Cmp);
	for(int i=1;i<=n;i++)b[i]=a[i]+b[i-1];
	for(int i=1,j=1;i<=n;i=j){
	  for(;j<=n&&a[j]>=a[i];j++);
	  if(i<=p){s+=j-i;continue;}
	  if(a[i]+m<a[p])continue;
	  if(v-(p-1)-(n-j+1)-1<=0){s+=j-i;continue;}
	  s+=(j-i)*((v-(p-1+n-j+2))*(long long)m+b[j-2]-b[p-1]<=(long long)(a[i]+m)*(j-p-1));
	}printf("%d\n",s);
	return 0;
}

Measured memory_bytes: 1280
#include <iostream>

using namespace std;

bool has3(int x){
    while(x){
        if(x%10 == 3){
            return true;
        }
        x /= 10;
    }
    return false;
}

void call(int n){
    for(int x=1; x<=n; x++){
        if(x%3 == 0 || has3(x)){
            cout << " " << x;
        }
    }
    cout << endl;
}

int main(){
    
    int n;

    cin >> n;

    call(n);

    return 0;
}




Measured memory_bytes: 3100
x=int(input())

def eratosthenes(n):
    prime_check=[True for _ in range(100010)]
    prime_check[0]=False
    prime_check[1]=False
    for i in range(2,n+1):
        j=2
        while(i*j<=n):
            prime_check[i*j]=False
            j+=1
        if(i*j<100010):
            prime_check[i*j]=False
    return prime_check


p=eratosthenes(x)
i=x
while(True):
    if(p[i]):
        print(i)
        break
    else:
        i+=1

Measured memory_bytes: 3992
from collections import deque
def bfs01(K,adjlist):
    reached=[False]*K
    d=deque()
    d.append((1,0))
    reached[1]=True
    while True:
        cur=d.popleft()
        reached[cur[0]]=True
        if cur[0]==0:
            return cur[1]
        for j,w in adjlist[cur[0]]:
            if w==0:
                if not reached[j]:
                    d.appendleft((j,cur[1]))
            elif w==1:
                if not reached[j]:
                    d.append((j,cur[1]+1))
                
    

K=int(input())
adjlist=[[] for _ in range(K)]
for i in range(K):
    to1=(i+1)%K
    to2=(10*i)%K
    if to1==to2:
        adjlist[i]=[(to2,0)]
    else:
        adjlist[i]=[(to1,1),(to2,0)]
print(bfs01(K,adjlist)+1)

Measured memory_bytes: 38132
#include <bits/stdc++.h>
using namespace std;
const int64_t MOD = pow(10, 9) + 7;

int main()
{
  int64_t N, res = 1;
  char c;
  cin >> N;
  vector<int64_t> A(27, 0);
  for (int i = 0; i < N; i++)
  {
    cin >> c;
    int idx = (c - '0') % 48;
    A.at(idx)++;
  }
  for (int i = 1; i <= 26; i++)
  {
    if (A.at(i) == 0)
      continue;
    res = res * (A.at(i) + 1) % MOD;
  }
  // 1つも選ばない場合の分、-1する
  cout << (res - 1) % MOD << endl;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main()
{
	int a,b,c;
	cin>>a>>b>>c;
	if(abs(a-b)>abs(a-c))
	{
		cout<<"B";
	}
	else
	{
		cout<<"A";
	}
	return 0;
 } 

Measured memory_bytes: 256
import java.util.*;
import java.io.*;

class Main
{
	public static void main( String[] args )
	{
		Scanner sc = new Scanner(System.in);
		String str = sc.nextLine();
		System.out.println(B(str));
	}

	static int B(String str)
	{
		int cur = Integer.valueOf(str);
		for(int i = 111; i <= 999; i += 111)
			if(cur <= i) return i;
		return cur;	// should not execute this line
	}

	static String update(String str)
	{
		char[] ch = str.toCharArray();
		for(int i = 0; i < 3; i++)
		{
			if(ch[i] == '1') ch[i] = '9';
			else ch[i] = '1';
		}
		return String.valueOf(ch);
	}

}

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

int main()
{
	int day;
	string s = "Christmas", e = " Eve";

	cin >> day;
	day = 25 - day;

	for (int i = 0; i < day; i++) {
		s = s + e;
	}
	cout << s << endl;
}


Measured memory_bytes: 256
#include<stdio.h>
long long int small(long long int a, long long int b) {
	if (a >= b) {
		return b;
	}
	else {
		return a;
	}
}
int main() {
	long long int n, s[5000] = {},m,min=10000000,count=0,x;
	scanf("%lld%lld%lld", &n, &m,&x);
	if (n+x-1>=m-x+1) {
		for (int i = n; i <= m; i++) {
			printf("%lld\n", i);
		}
      return 0;
	}
	for (int i = n; i <= n+x-1; i++) {
		printf("%lld\n", i);
	}
	for (int i = m-x+1; i <= m; i++) {
		printf("%lld\n", i);
	}
}

Measured memory_bytes: 128
N = int(input())
H = list(map(int,input().split()))

l = len(H)
L = [-1]
for i in range(l-1):
    if H[i] < H[i+1]:
        L.append(i)

L.append(l-1)

jump = [L[i+1] - L[i] - 1 for i in range(len(L)-1)]
jump.append(0)
if max(jump) >= 1:
    print(max(jump))
else:
    print(0)

Measured memory_bytes: 14252
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c,x,y;
    long long sum2;
    cin >> a >> b >> c >> x >> y;
    long long ans=a*x+b*y;
    long long sum1=2*c*max(x,y);
    if (x > y) sum2 = 2 * c * y + (x - y) * a;
	else sum2 = 2 * c * x + (y - x) * b;
	ans = min(min(ans, sum1), sum2);
	cout << ans;
}

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


int main() {
	
	int n;
	cin >> n;
	vector<int> p(n);
	int cnt=0;
	int m=n+1;
	for(auto &i : p) {
		cin >> i;
		if(i<m) cnt++;
		m = min(i,m);
	}
	cout << cnt << endl;
	
	return 0;
}

Measured memory_bytes: 1024
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <tuple>
#include <stack>
#include <bitset>

#define MAX_N 100010
#define MAX_M 100010
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;

ll A[MAX_N];
ll B[MAX_M];
ll C[MAX_M];

bool comp(const P &p1, const P &p2) {
  return p1.first > p2.first;
}

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

    ll N, M;
    cin >> N >> M;

    vector<P> v;
    for (ll i = 0; i < N; i++) cin >> A[i];
    for (ll i = 0; i < M; i++) {
      cin >> B[i] >> C[i];
      v.push_back( P(C[i], B[i]) );
    }

    sort(A, A + N);
    sort(v.begin(), v.end(), comp);

    ll ans = 0;
    ll range_min = 0;
    ll range_max = N-1;
    
    for (ll j = 0; j < M; j++) {
      ll lb;
      ll ub;
      lb = range_min - 1;
      ub = range_max + 1;

      ll cval = v[j].first;
      ll bval = v[j].second;
     
      while (lb + 1 < ub) {
	ll mid = (lb + ub) / 2;
	if(A[mid] < cval) lb = mid;
	else ub = mid;
      }

      for (ll i = ub; i <= range_max ; i++) ans += A[i];

      if (bval >= ub - range_min) {
	ans += cval * (ub - range_min);
	range_max = ub - 1;
	range_min = range_min + (ub - range_min);
      }
      else {
	ans += bval * cval;
	range_max = ub - 1;
	range_min = range_min + bval;
      }

      if (range_max < range_min) break;
    }

    for(ll i = range_min; i <= range_max; i++) ans += A[i];

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


Measured memory_bytes: 6908
#include "bits/stdc++.h"

#define rep(a,b) for(int a = 0;a < b;a++)
#define REP(i, x, n) for(int i = x; i < n; i++)
#define P(a) cout << a << endl
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define ssort(v) sort(v.begin(),v.end())
#define rev(v) reverse(v.begin(),v.end())
#define vP(v) for(int i = 0;i < v.size();i++){cout << v[i];if(i != v.size()-1)cout << endl;}
#define vcin(v,n) rep(i,n){int a;cin >> a;v.pb(a);}

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
int dx[] = { 1, -1 , 0 , 0 };
int dy[] = { 0,  0,  1, -1 };
ll MOD = 1000000007;

void solve(){
	int n;
	cin >> n;
	cout << setprecision(0) << fixed << pow((int)sqrt(n),2) << endl;
}

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


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

// TYPEDEF
// ----------------------------------------
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> Pair;
typedef vector<ll> vll;
typedef vector<vector<ll>> Graph;
typedef vector<string> vs;
typedef vector<pair<ll, ll>> Pll;
typedef queue<ll> qll;

// REPEAT
// ----------------------------------------
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define REPA(i,a) for(ll i=0;i<(ll)(a.size());i++);
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
#define COUT(a) cout << (a) << endl;
#define ENDL(a) cout << endl;
#define COUTA(i,a) for(ll i=0;i<(ll)(a.size());i++) {cout << (a)[i] << " ";} cout << endl;

// UTIL
// ----------------------------------------
#define pb push_back
#define paired make_pair
#define ALL(a) (a).begin(),(a).end()
#define SORT(a) sort((a).begin(),(a).end())
#define RSORT(a) sort((a).rbegin(), (a).rend())

// DEBUG
// ----------------------------------------
#ifdef _DEBUG
#define debug(x) cout << "[debug] " << #x << ": " << x << endl
#else
#define debug(x)
#endif

template <typename T>
void debugV(const vector<T> v) {
#ifdef _DEBUG
  rep(i, v.size()) {
    cout << i << ":" << v[i] << " ";
  }
  cout << endl;
#else
  (void)v;
#endif
}

// BIT FLAG
// ----------------------------------------
const unsigned int BIT_FLAG_0 = (1 << 0); // 0000 0000 0000 0001
const unsigned int BIT_FLAG_1 = (1 << 1); // 0000 0000 0000 0010
const unsigned int BIT_FLAG_2 = (1 << 2); // 0000 0000 0000 0100
const unsigned int BIT_FLAG_3 = (1 << 3); // 0000 0000 0000 1000
const unsigned int BIT_FLAG_4 = (1 << 4); // 0000 0000 0001 0000
const unsigned int BIT_FLAG_5 = (1 << 5); // 0000 0000 0010 0000
const unsigned int BIT_FLAG_6 = (1 << 6); // 0000 0000 0100 0000
const unsigned int BIT_FLAG_7 = (1 << 7); // 0000 0000 1000 0000
const unsigned int BIT_FLAG_8 = (1 << 8); // 0000 0001 0000 0000
const unsigned int BIT_FLAG_9 = (1 << 9); // 0000 0010 0000 0000
const unsigned int BIT_FLAG_10 = (1 << 10); // 0000 0100 0000 0000
const unsigned int BIT_FLAG_11 = (1 << 11); // 0000 1000 0000 0000

// CONST
// ----------------------------------------
constexpr ll INF = 0x3f3f3f3f3f3f3f3f;
constexpr double PI=3.14159265358979323846; // or M_PI
constexpr int MOD = 1000000007;


void Main() {
  string s;
  cin >> s;

  REP(i, s.length()) {
    if (i % 2 == 0) {
      if ((s[i] != 'R') and (s[i] != 'U') and  (s[i] != 'D')) {
        COUT("No");
        return;
      }
    }
    else {
      if ((s[i] != 'L') and (s[i] != 'U') and  (s[i] != 'D')) {
        COUT("No");
        return;
      }
    }
  }
  COUT("Yes");


}

int main()
{
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	cout << fixed << setprecision(15);
	Main();
}

/*

3 2
*/


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

ll H[5050], P[5050];
ll dp[5050][5050];
const ll INF=LLONG_MAX/2;

int main(){
  int N; cin>>N;
  vector<pair<ll,int> > V(N);
  rep(i,N){
    cin>>H[i]>>P[i];
    V[i]={H[i]+P[i], i};
  }
  sort(V.begin(),V.end());
  rep(i,5050) rep(j,5050) dp[i][j]=INF;
  dp[0][0]=0;
  int ans=0;
  rep(i,N) rep(j,N+1) if(dp[i][j]!=INF){
    dp[i+1][j]=min(dp[i+1][j],dp[i][j]);
    int ind=V[i].second;
    if(dp[i][j]<=H[ind]){
      dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+P[ind]);
      ans=max(ans,j+1);
    }
  }
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 199680
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
typedef long long ll;
#define MOD 998244353
using namespace std;
ll solve(vector<ll> &a) {
    ll res = 0, n = a.size();
    while(*max_element(all(a)) >= n) {
        *max_element(all(a)) -= n + 1;
        for(int i = 0; i < n; i++) {
            a[i]++;
        }
        res++;
    }
    return res;
}
int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    ll sum = 0, kai = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
    }
    kai = sum - n * (n - 1);
    if(kai <= 0) {
        cout << solve(a) << endl;
    } else {
        for(ll i = kai; i < sum; i++) {
            ll tmp = 0;
            for(int j = 0; j < n; j++) {
                ll x = a[j] + i;
                tmp += (x + 1) / (n + 1);
            }
            if(tmp == i) {
                cout << tmp << endl;
                return 0;
            }
        }
        cout << "fuck" << endl;
    }
}

Measured memory_bytes: 256
import java.util.*;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		int b = sc.nextInt();
		int h = sc.nextInt();
		int m = sc.nextInt();
		double c =0.0;
		double aa = 0.5*(h*60+m);
      	double bb = 6*m;
      	double cc = Math.abs(aa - bb);
      	if (cc>180) {
          cc = 360-cc;
        }
      double cos = Math.cos(Math.toRadians(cc));
		c = Math.sqrt(Math.pow(a,2) + Math.pow(b,2) - 2*a*b*cos);

		System.out.println(c);
	}
}


Measured memory_bytes: 35940
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <iomanip>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/tree_policy.hpp>
// #define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>

#define ll long long
#define int long long
#define Size(v) (int)v.size()

using namespace std;
// using namespace __gnu_pbds;

ll n;

const int nax = 1e6 + 5;
bool prime[nax];
vector<int> primes;

void sieve() {
	prime[1] = true;

	for (int i = 2; i < nax; ++i) {
		if (prime[i] == false) {
			for (int j = i * i; j < nax; j += i) prime[j] = true;
		}
	}

	for (int i = 1; i < nax; ++i) if (prime[i] == false) primes.push_back(i);
}

void solve() {
	cin >> n;
	ll cnt = 0;

	for (int j = 0; j < Size(primes) && primes[j] * primes[j] <= n; ++j) {
		int temp = 0;
		int i = primes[j];
		while (n % i == 0) {
			++temp;
			n /= i;
		}

		temp *= 2;
		int add = sqrt(temp);

		if (add * (add + 1) > temp) --add;
		if ((add + 1) * (add + 2) <= temp) ++add;

		// add * (add + 1) <= temp

		cnt += add;
	}

	if (n > 1) {
		++cnt;
	}

	cout << cnt;
}

signed main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	int t = 1;
	sieve();
	while (t--) 
		solve();
	return 0;
}

Measured memory_bytes: 5224
#include<iostream>
using namespace std;
int main(){
  //std::sync_with_stdio(false); cin.tie(false); cout.tie(false);
  char input;
  cin>>input;
  if(input>='A' && input<='Z') cout<<'A'<<'\n';
    else cout<<'a'<<'\n';
  return 0;
}

Measured memory_bytes: 3452
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <map>
#include <utility>
#include <numeric>
#include <typeinfo>

using namespace std;

int main(){
  int N,T;
  cin >> N >> T;
  vector<int> t(N);
  for(int i=0;i<N;i++)  cin >> t.at(i);

  int ans=T;
  for(int i=1;i<N;i++){
    if(t.at(i)-t.at(i-1)>=T)  ans+=T;
    else  ans+=t.at(i)-t.at(i-1);
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1024
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=100005;
int n,A[N],in[N];
vector <LL> e[N],v[N];
LL solve(int x,int pre){
	vector <LL> &a=v[x];
	for (auto y : e[x])
		if (y!=pre)
			a.push_back(solve(y,x));
	if (a.empty())
		return A[x];
	sort(a.begin(),a.end());
	if (!~a[0])
		return -1;
	reverse(a.begin(),a.end());
	LL tot=0;
	for (auto y : a)
		tot+=y;
	LL u=min((LL)A[x],min(tot/2,tot-a[0])),v=tot-A[x];
	return v>u||v<0?-1:(A[x]-v);
}
int main(){
	cin >> n;
	for (int i=1;i<=n;i++)
		cin >> A[i];
	for (int i=1,a,b;i<n;i++){
		cin >> a >> b;
		e[a].push_back(b);
		e[b].push_back(a);
		in[a]++,in[b]++;
	}
	if (n==2)
		return puts(A[1]==A[2]?"YES":"NO"),0;
	for (int i=1;i<=n;i++)
		if (in[i]>1)
			return puts(solve(i,0)==0?"YES":"NO"),0;
}

Measured memory_bytes: 19968
import java.util.*;
import java.io.*;
public class Main
{
    public static void main(String []args) throws IOException {
    	FastScanner in  = new FastScanner(System.in);
    	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)), false); 
    	solve(in, out);
    	in.close();
    	out.close();
    }
    static long gcd(long a, long b){ return (b==0) ? a : gcd(b, a%b); }
    static int gcd(int a, int b){ return (b==0) ? a : gcd(b, a%b); }
    static class FastScanner{
	BufferedReader reader;
	StringTokenizer st;
	FastScanner(InputStream stream){reader=new BufferedReader(new InputStreamReader(stream));st=null;}	
	String next(){while(st == null || !st.hasMoreTokens()){try{String line = reader.readLine();if(line == null){return null;}		    
	     st = new StringTokenizer(line);}catch (Exception e){throw new RuntimeException();}}return st.nextToken();}
	String nextLine()  {String s=null;try{s=reader.readLine();}catch(IOException e){e.printStackTrace();}return s;}	    	  	
	int    nextInt()   {return Integer.parseInt(next());}
	long   nextLong()  {return Long.parseLong(next());}		
	double nextDouble(){return Double.parseDouble(next());}
	char   nextChar()  {return next().charAt(0);}
	int[]  nextIntArray(int n)         {int[] arr= new int[n];   int i=0;while(i<n){arr[i++]=nextInt();}  return arr;}
	long[] nextLongArray(int n)        {long[]arr= new long[n];  int i=0;while(i<n){arr[i++]=nextLong();} return arr;}	
	int[]  nextIntArrayOneBased(int n) {int[] arr= new int[n+1]; int i=1;while(i<=n){arr[i++]=nextInt();} return arr;}	    	
	long[] nextLongArrayOneBased(int n){long[]arr= new long[n+1];int i=1;while(i<=n){arr[i++]=nextLong();}return arr;}	    	
	void   close(){try{reader.close();}catch(IOException e){e.printStackTrace();}}				
    }
    
    /********* SOLUTION STARTS HERE ************/
    
    private static void solve(FastScanner in, PrintWriter out){
        
        int T = 1;//in.nextInt();
        for(int t = 1; t <= T; t++)
        {
            int n = in.nextInt();
            long a[] = in.nextLongArray(n);
            int pt=1,count=0;
            for(int i=0;i<n;i++){
                if(a[i]==pt){
                    count++;
                    pt++;
                }
            }
            count = n-count;
            if(count==n) out.write("-1\n");
            else out.write(count+"\n");
        }
    }
    
    /************* SOLUTION ENDS HERE **********/
}

Measured memory_bytes: 48012
n, d = map(int, input().split())
x = []
y = []
for _ in range(n):
  tx,ty = map(int, input().split())
  x.append(tx)
  y.append(ty)

cnt = 0
for px,py in zip(x,y):
  dis = ((px**2) + (py**2))**0.5
  if dis<=d:
    cnt += 1
print(cnt)

Measured memory_bytes: 24840
#include <bits/stdc++.h>
 
#define int long long
 
// loop
#define FOR(i, a, b) for (int i = (a); i < (b); i++) 	// a ~ b-1	(ascending)
#define REP(i, n) FOR(i, 0, n)							// 0 ~ n-1
#define NREP(i, n) FOR(i, 1, n + 1)						// 1 ~ n
#define RFOR(i, a, b) for (int i = (a); i >= (b); i--)	// a ~ b	(descending)
#define RREP(i, n) RFOR(i, n, 0)						// n ~ 0
#define RNREP(i, n) RFOR(i, n, 1)						// n ~ 1
 
// container operation
#define EACH(i, c) for (auto i = (c).begin(); i != (c).end(); i++)
#define ASORT(c) std::sort((c).begin(), (c).end())
#define DSORT(c) std::sort((c).begin(), (c).end(), std::greater<typeof((c).front())>())
#define SIZE(x) ((int)(x).size())
 
// debug
#define check(x) std::cout << #x << " = " << x << '\n'
 
// print
#define cout(x) std::cout << x << '\n'
 
// type alias
using VI = std::vector<int>;
using VII = std::vector<VI>;
using VB = std::vector<bool>;
using VBB = std::vector<VB>;
using VS = std::vector<std::string>;
using PII = std::pair<int, int>;

std::string yes = "Yes\n";
std::string no = "No\n";

void solve();

signed main() {
  solve();
  return 0;
}

void solve() {
  int a, b, c;
  std::cin >> a >> b >> c;
  if (a + b == c ||
      b + c == a ||
      c + a == b) {
    cout(yes);
  } else {
    cout(no);
  }
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
  
/* attention
    long longのシフト演算には気をつけよう
    タイポした時のデバッグが死ぬほどきつくなるので変数名は最低3字くらい使った方がいいかも
    sizeは(int)とキャストしよう
    ごちゃごちゃ場合分けを考える前に全探索は考えましたか？
*/

const int MAX = 100000;

int A[MAX], n;

int partition(int p, int r){
    int x = A[r];
    int i = p-1;
    
    for(int j=p; j<r; j++){
        if(A[j] <= x){
            i++;
            swap(A[i], A[j]);
        }
    }

    swap(A[i+1], A[r]);
    return i+1;
}

int main(){

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

    int q = partition(0, n-1);

    for(int i=0; i<n ;i++){
        if(i) printf(" ");
        if(i == q) printf("[");
        printf("%d", A[i]);
        if(i == q) printf("]");
    }
    printf("\n");

    return 0;
}


Measured memory_bytes: 3496
////////////////////////////////////////////
///                                      ///
///        Template ver. 1.2. rapel      ///
/// Fear is Temporary, Regret is Forever ///
///          Must Try and Get AC         ///
///                                      ///
////////////////////////////////////////////
#include <stdio.h>
#include <iostream>
#include <sstream>
#include <iomanip>

#include <algorithm>
#include <stdlib.h>
#include <string.h>
#include <string>
#include <utility>

#include <math.h>
#include <complex>

#include <assert.h>
#include <time.h>
//#include <chrono>
//#include <random>

#include <vector>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <queue>
#include <stack>
#include <list>
#include <bitset>

#define F first
#define S second
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define endl '\n'
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

void desperate_optimization(int precision){
  	ios_base::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	cout.setf(ios::fixed);
  	cout.setf(ios::showpoint);
  	cout.precision(precision);
}

const ll MOD = 1e9 + 7;
const int N = 5e5;

ll fct[N + 5], inv[N + 5];

ll fast(ll A, ll B) {
	ll res = 1;
	while(B) {
		if(B & 1) res = res * A % MOD;
		B /= 2;
		A = A * A % MOD;
	}
	return res;
}

void pre() {
	fct[0] = 1;
	for(int i = 1;i <= N;i++) fct[i] = fct[i - 1] * i % MOD;
	inv[N] = fast(fct[N], MOD - 2);
	for(int i = N - 1;i >= 0;i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

ll combin(int n, int r) {
	if(n < r) return 0;
	return fct[n] * inv[r] % MOD * inv[n - r] % MOD;
}

void hora(int tc) {
	pre();
	int n, k;
	cin>>n>>k;
	if(k >= n) k = n - 1;
	ll res = 0;
	for(int i = 0;i < k + 1;i++) {
		res = (res + combin(n, i) * combin(n - 1, n - i - 1)) % MOD;
	}
	cout<<res<<endl;
}

int main(){
	desperate_optimization(10);
	int ntc = 1;
	//cin>>ntc;
	for(int tc = 1;tc <= ntc;tc++) hora(tc);
	return 0;
}


Measured memory_bytes: 8064
import sys
readline = sys.stdin.readline

H,W = map(int,readline().split())
C = [None] * 10
for i in range(10):
  C[i] = list(map(int,readline().split()))

for k in range(10):
  for i in range(10):
    for j in range(10):
      C[i][j] = min(C[i][j], C[i][k] + C[k][j])
      
ans = 0
for i in range(H):
  line = list(map(int,readline().split()))
  for j in range(len(line)):
    if line[j] == -1:
      continue
    ans += C[line[j]][1]
    
print(ans)

Measured memory_bytes: 9164
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<long long> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<long long, long long>> vpl;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
#define INF (int)(1e9)
#define MAXX 1.1529215e+18
#define inf 999999
#define EPS (1e-7)
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define REP(i, n) for (int i = 1; i <= (int)(n); i++)
#define FOR(i, k, n) for (int i = (k); i < (int)(n); i++)
#define ALL(a) a.begin(), a.end()
#define RALL(a) a.begin(), a.end(), greater<int>()
#define ROT(a) a.begin(), a.begin() + 1, a.end()
#define RROT(a) a.begin(), a.end() - 1, a.end()
#define PB push_back
#define MP make_pair
#define PI acos(-1.0)
#define sz(a) a.size()
const ll MOD = 1e9 + 7;
const int MAX = 10000000;
template <typename T1, typename T2>
inline bool chmin(T1& a, T2 b)
{
    if (a > b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T1, typename T2>
inline bool chmax(T1& a, T2 b)
{
    if (a < b) {
        a = b;
        return 1;
    }
    return 0;
}
template <typename T>
T gcd(T a, T b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}
//cout << 'H' << endl;
/*--------------------------------------------*/
int N, M;
vector<vector<int>> G;
ll ans;
void dfs(int p, vector<int> x)
{
    x[p] = 1;

    bool flag = true;
    rep(i, N)
    {
        if (!x[i]) {
            flag = false;
        }
    }

    if (flag) {
        ans++;
        return;
    }

    ll ret = 0;
    for (int v : G[p]) {
        if (!x[v]) {
            dfs(v, x);
        }
    }
}
int main()
{
    //cout << fixed << setprecision(10)
    cin.tie(0);
    ios::sync_with_stdio(false);

    cin >> N >> M;

    G.resize(N);

    rep(i, M)
    {
        int a, b;
        cin >> a >> b;
        --a;
        --b;

        G[a].PB(b);
        G[b].PB(a);
    }
    ans = 0;
    vector<int> x(N);
    dfs(0, x);

    cout << ans << endl;
}


Measured memory_bytes: 256
// clang-format off
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int i=0;i<(int)(n);++i)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}
// clang-format on

int main() {
    int n, k, p[3];
    cin >> n >> k;
    rep(i, 3) cin >> p[i];

    string t;
    cin >> t;

    vector<int> v(n);
    rep(i, n) {
        if (t[i] == 'r') v[i] = 2;
        if (t[i] == 's') v[i] = 0;
        if (t[i] == 'p') v[i] = 1;
    }

    int ans = 0;
    rep(i, k) {
        vector<int> dp(3);
        dp[v[i]] = p[v[i]];

        for (int j = i + k; j < n; j += k) {
            vector<int> nx(3);
            rep(x, 3) rep(y, 3) {
                if (x == y) continue;
                int add = 0;
                if (x == v[j]) add = p[x];
                nx[x] = max(nx[x], dp[y] + add);
            }
            swap(dp, nx);
        }

        int add = 0;
        for (int j : dp) add = max(add, j);
        ans += add;
    }
    cout << ans << "\n";
    return 0;
}


Measured memory_bytes: 896
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define inf 1001001001001001001
#define mod 1000000007
#define mod2 998244353
#define pi acos(-1)
#define all(v) v.begin(),v.end()
int main(){
    int N,K;cin>>N>>K;
    int ans=0;
    int a;
    rep(i,N){
        cin>>a;
        if(a>=K){
            ans++;
        }
    }
    cout<<ans<<endl;

}

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str[] = br.readLine().split(" ");
        double a = Double.parseDouble(str[0]);
        double b = Double.parseDouble(str[1]);
        double C = Double.parseDouble(str[2]);
        double S = a * b * 0.5 * Math.sin(Math.PI/180*C);
        double L = a + b + Math.sqrt(a*a+b*b-2*a*b*Math.cos(Math.PI/180*C));
        double h = 2 * S / a;
        System.out.printf("%.8f\n", S);
        System.out.printf("%.8f\n", L);
        System.out.printf("%.8f\n", h);
    }
}

Measured memory_bytes: 24636
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char **argv)
{
	char a[100];
	char p[10];
	int b,c,d;
	strcpy(p,"+");
	scanf("%d %s %d",&b,a,&c);
	d = strcmp(p,a);
	if(d==0){
		printf("%d\n", b+c);
	}
	else{
		printf("%d\n", b-c);
	}
	return 0;
}


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

using namespace std;

int N;
vector <int> a;

int f(int y){
	int cost=0;
	for(int i=0; i<N; i++){
		cost+=(a[i]-y)*(a[i]-y);
	}
	return cost;
}

int main(){
	cin>>N;
	a.resize(N);
	for(int i=0; i<N; i++){
		cin>>a[i];
	}

	int now=0;
	int now_cost, r_cost, l_cost;

	while(true){
		now_cost=f(now);
		r_cost=f(now+1);
		l_cost=f(now-1);
		if(l_cost < now_cost && now_cost < r_cost){
			now-=1;
		}else if(l_cost > now_cost && now_cost > r_cost){
			now+=1;
		}else{
			break;
		}
	}

	cout<<now_cost<<endl;

	return 0;

}

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

using ll=long long;
const ll MOD=1000000007;

int main() {
  string s;
  cin >> s;
  int k=s.size();
  for(int i=0;i<k;i++){
    s[i]='x';
  }
  cout << s << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <functional>
#include <algorithm>
#include <cmath>
#include<bits/stdc++.h>
using namespace std;

double d(double a1, double a2, double a3, double a4){
    return(sqrt((a1-a3)*(a1-a3)+(a2-a4)*(a2-a4)));
}

int main(){
    double x1,x2,x3,y1,y2,y3;
    cin >> x1 >> y1;
    cin >> x2 >> y2;
    cin >> x3 >> y3;
    double s = abs((x2-x1)*(y3-y1)-(y2-y1)*(x3-x1))/2;
    double a1 = d(x2-x1,y2-y1,x3-x1,y3-y1);
    double a2 = d(x3-x2,y3-y2,x1-x2,y1-y2);
    double a3 = d(x1-x3,y1-y3,x2-x3,y2-y3);
    double m = max(max(a1,a2),a3);
    double r = 2*s/(a1+a2+a3);
    cout << setprecision(15) << m/(2+m/r) << endl;
}

Measured memory_bytes: 256