akhauriyash/Code-Regression huggingface dataset:
package main

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

func main() {
	A := nextBytes()
	B := nextBytes()

	a := make([]int, len(A))
	ans := make([]int, len(A)+10)

	for i := 0; i < len(A); i++ {
		a[len(A)-1-i] = int(A[i] - '0')
	}

	for i := 0; i < len(a); i++ {
		s := a[i] * int(B[3]-'0')
		ans[i+0] += s
	}
	for i := 0; i < len(a); i++ {
		s := a[i] * int(B[2]-'0')
		ans[i+1] += s
	}
	for i := 0; i < len(a); i++ {
		s := a[i] * int(B[0]-'0')
		ans[i+2] += s
	}

	// 繰り上がり
	for i := 0; i < len(ans); i++ {
		if ans[i] >= 10 {
			ans[i+1] += ans[i] / 10
			ans[i] = ans[i] % 10
		}
	}

	first := false

	for i := len(ans) - 1; i >= 2; i-- {
		if ans[i] == 0 && !first {
			continue
		}
		first = true
		fmt.Print(ans[i])
	}
	if !first {
		fmt.Print(0)
	}
	fmt.Println()
}

var stdin = initStdin()

func initStdin() *bufio.Scanner {
	bufsize := 1 * 1024 * 1024 // 1 MB
	var stdin = bufio.NewScanner(os.Stdin)
	stdin.Buffer(make([]byte, bufsize), bufsize)
	stdin.Split(bufio.ScanWords)
	return stdin
}

func nextString() string {
	stdin.Scan()
	return stdin.Text()
}

func nextBytes() []byte {
	stdin.Scan()
	return stdin.Bytes()
}

func nextInt() int {
	i, _ := strconv.Atoi(nextString())
	return i
}

func nextInt64() int64 {
	i, _ := strconv.ParseInt(nextString(), 10, 64)
	return i
}


Measured memory_bytes: 1796
#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    s = input()

    if s == "RRR":
        n = 3
    elif "RR" in s:
        n = 2
    elif "R" in s:
        n = 1
    else:
        n = 0
    print(n)

if __name__ == "__main__":
    resolve()


Measured memory_bytes: 61628
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> P;
int INF = 1e9+7;
int mod = 1234567;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int cnt[200005];
signed main() {
    int N;
    cin >> N;
    vector<int>a(N);
    for(int i = 0; i < N; i++) {
        cin >> a[i];
    }
    vector<int>ans;
    for(int i = N; i >= 1; i--) {
        if(cnt[i]%2 == a[i-1]) {
            continue;
        }
        ans.push_back(i);
        for(int j = 1; j*j <= i; j++) {
            if(i%j == 0) {
                if(j*j == i) {
                    cnt[j]++;
                }
                else {
                    cnt[j]++;
                    cnt[i/j]++;
                }
            }
        }
    }
    cout << ans.size() << endl;
    for(int i = 0; i < ans.size(); i++) {
        if(i) {
            cout << " ";
        }
        cout << ans[i];
    }
}


Measured memory_bytes: 7444
#include<stdio.h>

int main(){

  int R[200000];
  int n,i,j,minv;
  int v = 0,maxv = 0;
  
  scanf("%d",&n);

  for(i=0;i<n;i++){
    scanf("%d",&R[i]);
  }
  
  minv = R[0];
  maxv = R[1]-R[0];
  
  for(j=1;j<n;j++){
    v = R[j]-minv;
    if(v>maxv)maxv=v;
    if(minv>R[j])minv=R[j];
  }
      
  printf("%d\n",maxv);
  
  return 0;
}

Measured memory_bytes: 1376
import java.util.*;

public class Main {
	final static long MODULO = 1_000_000_000 + 7;

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int T = sc.nextInt();
		int[] D = new int[N];
		for (int i = 0; i < N; ++i) {
			D[i] = sc.nextInt();
		}
		Arrays.sort(D);
		long ans = 1;
		int s = 0;
		for (int i = 0; i < N; ++i) {
			while (s < i && D[s] < D[i] - T) {
				++s;
			}
			ans = (ans * (i - s + 1)) % MODULO;
		}
		System.out.println(ans);

	}
}

Measured memory_bytes: 70240
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _163A
{
    class Program
    {
        static void Main(string[] args)
        {
            int R = int.Parse(Console.ReadLine());
            double L = 2.0 * Math.PI * R;

            Console.WriteLine(L);
        }
    }
}


Measured memory_bytes: 27380
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <utility>
#include <cstdlib>
#include <cmath>
#include <functional>

#define INF 1000000000000000000
using namespace std;
typedef long long ll;

int n;
ll k;
ll a[5010];
bool dp[5010];

bool need(int m) {
	for (int i = 1; i < k; i++) {
		dp[i] = false;
	}
	dp[0] = true;
	for (int i = 0; i < n; i++) {
		if (i == m)continue;
		for (int j = k - 1; j >= 0; j--) {
			if (dp[j] && (j + a[i]) < k) {
				dp[j + a[i]] = true;
			}
		}
	}
	for (int i = max(0, (int)(k - a[m])); i < k; i++) {
		if (dp[i])return true;
	}
	return false;
}


int main(){
	cin >> n>>k;
	int lo, hi;
	lo = 0; hi = n - 1;

	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a, a + n);
	if (!need(n - 1)) {
		cout << n << endl;
		return 0;
	}
	while (lo != hi) {
		int mid = (lo + hi) / 2;
		if (need(mid)) {
			hi = mid ;
		}
		else {
			lo = mid + 1;
		}
	}
	cout << lo << endl;

	return 0;
}


Measured memory_bytes: 384
S=input()
L=[0]*(len(S)+1)
#print(L)
for i in range(len(S)):
  if S[i]=='<':
    L[i+1]=L[i]+1
for i in range(len(S)-1,-1,-1):
  if S[i]=='>':
    L[i]=max(L[i],L[i+1]+1)
print(sum(L))


Measured memory_bytes: 23336
import java.util.*;
public class Main {
  public static void main(String[] args){
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    //文字用
    String s[] = new String[n];
    //数える用
    int num[] = new int[n];

    for(int i = 0 ; i < n ; ++i){
      s[i] = sc.next();
      num[i] = 0;
    }
    //ソートする
    Arrays.sort(s);
    //数える用
    int count = 0;
    //多いの判断用
    int max = 0;
    
    for(int i = 0 ; i < n ; ++i){
      for(int j = i+1 ; j < n ; ++j){
        if(s[i].equals(s[j])){
          count++;
          num[j] = count;
        }else{
          break;
        }
      }
      if(i+count > i){
        i += count;
      }
      count = 0;
    }
    
    for(int i = 0 ; i < n ; ++i){
      max = Math.max(num[i],max);
    }
    
    for(int i = 0 ; i < n ; ++i){
      if(num[i] == max){
       System.out.println(s[i]);
      }

    }

    
  }
}

Measured memory_bytes: 73068
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
const ll INF = 1LL << 60;
const ll MOD = 1000000007;
template <class T>
bool chmax(T &a, const T &b) {
    return (a < b) ? (a = b, 1) : 0;
}
template <class T>
bool chmin(T &a, const T &b) {
    return (b < a) ? (a = b, 1) : 0;
}
template <class C>
void print(const C &c, std::ostream &os = std::cout) {
    std::copy(std::begin(c), std::end(c), std::ostream_iterator<typename C::value_type>(os, " "));
    os << std::endl;
}

int main() {
    int k, x;
    cin >> k >> x;
    vi ret;
    for (int i = x - (k - 1); i <= x + k - 1; ++i) {
        if (i >= -1000000 && i <= 1000000)
            ret.push_back(i);
    }
    print(ret);
    return 0;
}

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

int main() {
	int x;
	cin >> x;
	bool ok = true;
	if (x == 2) {
		cout << 2;
		return 0;
	}
	while(ok) {
		rep(i, x-2) {
			if (x % (i + 2) == 0) {

				break;
			}
			if (i+2 == x - 1) {
				ok = false;
			}
		}
		++x;
	}
	cout << x-1;
}

Measured memory_bytes: 256
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int A=sc.nextInt();
		int B=sc.nextInt();
		int C=sc.nextInt();
		int K=sc.nextInt();
		int ans=0;
		int K1=0;
		int K2=0;



		if(K>A) {
			ans=ans+1*A;
			K1=K-A;
		}else {
			ans=ans + 1*K;
		}
		if(K1>B) {
			ans=ans+B*0;
			K2=K1-B;
		}else {
			ans=ans + 0*K1;
		}
		if(K2>C) {
			ans=ans+C*(-1);
		}else {
			ans=ans+K2*(-1);
		}
		System.out.println(ans);

		sc.close();

	}
}


Measured memory_bytes: 35812
#include <bits/stdc++.h>
using namespace std;
 
int main() {
    
    string str;cin>>str;
    int cc1=0,cc2=0,ans;
    int n=str.size();
    
    for(int i=0;i<n;++i){
        if(i%2==0 && str[i]=='0')cc1+=1;
        else if(i%2==0 && str[i]=='1')cc2+=1;
        else if(i%2==1 && str[i]=='0')cc2+=1;
        else cc1+=1;
    }
    ans=min(cc1,cc2);
    cout<<ans<<endl;
    
	return 0;
}

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

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
typedef pair<int,ll> pil;
const int maxN = 1e5+10;
const int INF = 999999999;

vector<int> p;
int n;
int a[maxN];
int b[maxN];
int main() {
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);

	}

	for(int i=1;i<=n;i++)
	{
		if(a[i]%2 == 1)
		{
			puts("first");
			return 0;
		}
	}
	puts("second");
	return 0;
}


Measured memory_bytes: 640
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N, M, Xi):
    lengthes = []
    Xi.sort()
    for i in range(1, M):
        lengthes.append(abs(Xi[i - 1] - Xi[i]))
    lengthes.sort()
    num = N if N < M else M
    print(sum(lengthes[:M - num]))


if __name__ == '__main__':
    # S = input()
    # N = int(input())
    N, M = map(int, input().split())
    Xi = [int(i) for i in input().split()]
    # Bi = [int(i) for i in input().split()]
    # ABi = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N, M, Xi)

    # # test
    # from random import randint
    # from func import random_str
    # solve()


Measured memory_bytes: 19772
#include<stdio.h>
int selectionSort(int A[],int n)
{
  int i,j,minj,sw=0,t;
  for(i=0;i<n-1;i++)
    {
      minj =i;
      for(j=i;j<n;j++){
	if(A[j]<A[minj])
	  minj = j;
      }
      t=A[i];
      A[i]= A[minj];
      A[minj]=t;
      if(i != minj) sw++;
    }
  
  return sw;
}
int main(){
  int A[100],n,i,sw;
  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d",&A[i]);
  }
  sw = selectionSort(A,n);
  for(i=0;i<n;i++){
    if(i > 0){
      printf(" ");
    }
      printf("%d",A[i]);
    
  }
    printf("\n");
    printf("%d\n",sw);
    return 0;
 
}



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

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

l = [0]*1000001

A.sort()

for a in A:
    if l[a] == 0:
        l[a] = 1
        tmp = 2
        while tmp*a <= 1000000:
            l[tmp*a] = 2
            tmp+=1
    elif l[a] == 1:
        l[a] = 2

ans = 0
for a in A:
    if l[a] != 2:
        ans += 1

print(ans)


Measured memory_bytes: 135628
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	map<int,string>mp;
	mp[2]="hon";
	mp[4]="hon";
	mp[5]="hon";
	mp[7]="hon";
	mp[9]="hon";
	mp[0]="pon";
	mp[1]="pon";
	mp[6]="pon";
	mp[8]="pon";
	mp[3]="bon";
	ll n;
	cin>>n;
	cout<<mp[n%10];
	return 0;
}

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

int main(){
    int n,m,x,y;
    cin >> n >> m >> x >> y;
    vector<int> X(n);
    vector<int> Y(m);
    for(int i=0;i<n;i++){
        cin >> X[i];
    }
    for(int i=0;i<m;i++){
        cin >> Y[i];
    }
    X.push_back(x);
    Y.push_back(y);
    int Xmax = *max_element(X.begin(), X.end());
    int Ymin = *min_element(Y.begin(), Y.end());

    if(Xmax<Ymin) cout << "No War";
    else cout << "War";


}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
import math
from collections import Counter

# 高速 組み合わせ
def C(n, r):
  a = 1
  b = 1
  for i in range(r):
    a = a*(n-i)
    b = b*(r-i)
  return((a//b))

N = int(input())

def primes(n):
    primfac = []
    d = 2
    while d*d <= n:
        while (n % d) == 0:
            primfac.append(d)  # supposing you want multiple factors repeated
            n //= d
        d += 1
    if n > 1:
        primfac.append(n)
    return primfac

# tmp = [[75],[5,5,3],[25,3],[15,5]]
cnt = Counter(primes(math.factorial(N)))
# cnt = Counter(primes(N))
ans = 0
ans += sum([1 for k,v in cnt.items() if v >= 74])

t1 = sum([1 for k, v in cnt.items() if v >= 24])
t2 = sum([1 for k, v in cnt.items() if v >= 2])

ans += t1 * (t2 - 1)

t1 = sum([1 for k, v in cnt.items() if v >= 14])
t2 = sum([1 for k, v in cnt.items() if v >= 4])

ans += t1 * (t2 - 1)

t3 = sum([1 for k, v in cnt.items() if v >= 4])
if t3 >= 2:
    t1 = C(t3,2)
    t2 = sum([1 for k, v in cnt.items() if v >= 2])

    ans += t1 * (t2 - 2)

# print(cnt)
print(ans)


Measured memory_bytes: 3444
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;
typedef long long ll;

struct int_hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};

struct pair_hash {
    size_t operator()(pair<int, int> x) const {
        return int_hash{}(x.first) ^ (int_hash{}(x.second) << 16);
    }
};

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int MOD = 1000000007;
const ll INF = numeric_limits<ll>::max();
const int inf = 1e8;
const int MX = 100001; //check the limits, dummy

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll h, n; cin >> h >> n;
    vector<ll> a(n), b(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
        cin >> b[i];
    }

    vector<ll> dp(h + 1, inf + 1);
    dp[0] = 0;
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= h; j++)
            dp[j] = min(dp[j], b[i] + dp[max(0LL, j - a[i])]);

    cout << dp[h] << endl;
}

Measured memory_bytes: 384
#include<iostream>
#include <string>
#include<string.h>
using namespace std;
int main(){
string n;
cin >> n;
if(n.size()<4){
cout <<"No";
}
else{
string sub = n.substr(0, 4);  
if(!(sub.find("YAKI"))){
cout <<"Yes";
}
else {
cout <<"No";
}

}
return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N;
    cin >> N;
    
    vector<long long int> A(N), B(N), C(N);
    for(int n=0; n<N; n++) {
        cin >> A[n];
    }
    for(int n=0; n<N; n++) {
        cin >> B[n];
    }
    for(int n=0; n<N; n++) {
        cin >> C[n];
    }
    
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    sort(C.begin(), C.end());
    
    vector<long long int> SB(N+1, 0);
    for(int bi=0; bi<N; bi++) {
        SB[bi+1] = SB[bi];
        SB[bi+1] += C.end() - upper_bound(C.begin(), C.end(), B[bi]);
        // cout << C.end() - upper_bound(C.begin(), C.end(), B[bi]) << ", ";
        // cout << SB[bi+1] << endl;
    }
    long long int ans=0;
    for(int ai=0; ai<N; ai++) {
        ans += SB[N] - SB[upper_bound(B.begin(), B.end(), A[ai])-B.begin()];
    }
    
    cout << ans << endl;

    return 0;
    
}

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

template<typename T, typename U> bool chmin(T &a, const U &b) {
	return (a > b ? a = b, true : false);
}
template<typename T, typename U> bool chmax(T &a, const U &b) {
	return (a < b ? a = b, true : false);
}

typedef long long ll;

#define writeln(n) cout<<n<<"\n";

typedef pair<int, int> P;
typedef pair<string, int> Psi;

ll numct[210000];
ll k[210000];
ll cnb[210000];
int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);

	string s;
	cin>>s;

	if(s =="AAA"){
		writeln("No");
		return 0;
	}
	if( s =="BBB"){
		writeln("No");
		return 0;
	}
		writeln("Yes");



}


Measured memory_bytes: 256
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int Maxn=60,Maxm=1510;
const int inf=0x3f3f3f3f;
char a[Maxn];
int f[Maxn],ans;
inline int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
	while(ch>='0' && ch<='9')s=(s<<3)+(s<<1)+(ch^48),ch=getchar();
	return s*w;
}
int main()
{
	scanf("%s",a+1);
	for(int i=1;i<=3;++i)
	{
		if(a[i]=='S')continue;
		f[i]=f[i-1]+1;
		ans=max(ans,f[i]);
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 3812
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll lcm(ll a,ll b){return a*b/__gcd(a,b);}
int main()
{
    int n,m;
    cin>>n>>m;
    int sum=0;
    for(int i=0,x;i<m;i++)cin>>x,sum+=x;
    if(sum<=n)cout<<n-sum<<endl;
    else cout<<-1<<endl;
}


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


int main()
{
    int N;
    cin >> N;
    int ans = N % 10;
    if (ans== 2 or ans ==4 or ans == 5 or ans == 7 or ans == 9){
        cout << "hon" << endl;
    }else if(ans == 0 or ans == 1 or ans == 6 or ans == 8){
        cout << "pon" << endl;
    }else{
        cout << "bon" << endl;
    }

        return 0;
}

Measured memory_bytes: 3644
import sys 
def primes(m):
    N = range(1,m+1,2)
    r = int(m**.5)
    h = len(N)
    N[0] = 0
    for i in range(h):
        x = N[i]
        if x>r: break
        if x and i+x<h: N[i+x:h:x] = [0]*((h-1-i-x)/x+1)
    x = [2] + filter(None,N)
    return x
 

PRIMES = primes(50100)
for s in sys.stdin:
    n = int(s)
    for a in PRIMES:
        if a>n: break
        elif a<n: b = a
    print b,a

Measured memory_bytes: 5804
n,l = map(x -> parse(Int64, x), split(readline()))

a = Array{Any}(1)
a[1] = chomp(readline())
for i in 2:n
    x = chomp(readline())
  for j in 1:i-1
    if x <= a[j]
      insert!(a, j, x)
      break
    elseif j==i-1
      insert!(a, i, x)
    end
  end
end
print(join(a))

Measured memory_bytes: 122180
import sys

def chmin(a,i,b):
  if a[i] > b:
    a[i] = b
    #print(a)
    return True
  else:
    return False

n,k = map(int,input().split())
h = list( map(int,input().split()))
dp = [sys.maxsize for i in range(n)]

dp[0] = 0
#print(n,h)
#print(dp)

for i in range(len(dp)):
  for j in range(k+1):
    if i - j >= 0:
      #chmin(dp,i, abs(h[i]-h[i-j])+dp[i-j])
      dp[i] = min(dp[i], abs(h[i]-h[i-j])+dp[i-j])

#print(dp)   
print(dp[-1])


Measured memory_bytes: 56544
import sys
import collections


input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    ab = [[] for j in range(N + 1)]
    distance = [0] * (N + 1)
    for _ in range(M):
        a, b = [int(x) for x in input().split()]
        ab[a].append(b)
        ab[b].append(a)

    q = collections.deque()
    q.append([1, 0])

    visited = set()
    visited.add(1)

    while q:
        c, d = q.popleft()

        for n in ab[c]:
            if n not in visited:
                visited.add(n)
                q.append([n, d + 1])
                distance[n] = d + 1

    if distance[N] != 0 and distance[N] <=2:
        print("POSSIBLE")
    else:
        print("IMPOSSIBLE")




    
    
    

if __name__ == '__main__':
    main()



Measured memory_bytes: 60508
#include<bits/stdc++.h>
using namespace std;
long long mi(long long A,long long B,long long C,long long D,long long E){
  return min(min(min(min(A,B),C),D),E);
}
int main(){
  long long N,A,B,C,D,E;cin>>N>>A>>B>>C>>D>>E;
  if(mi(A,B,C,D,E)==A){cout<<(N+A-1)/A+4;return 0;}
  if(mi(A,B,C,D,E)==B){cout<<(N+B-1)/B+4;return 0;}
  if(mi(A,B,C,D,E)==C){cout<<(N+C-1)/C+4;return 0;}
  if(mi(A,B,C,D,E)==D){cout<<(N+D-1)/D+4;return 0;}
  if(mi(A,B,C,D,E)==E){cout<<(N+E-1)/E+4;return 0;}
}

Measured memory_bytes: 3624
#include<string>
#include<iostream>
#include<cstdio>
#define mod 1000000007
using namespace std;
int main() {
	int a, b,temp;
	scanf("%d %d",&a, &b);
	temp = a * b;
	temp=temp - a - b + 1;
	printf("%d", temp);
	return 0;
}

Measured memory_bytes: 256
#include<stdio.h>

int main(void)

{

  int a,b,d,r;

  double f;


  scanf("%d %d",&a,&b);


  d=a/b;


  r=a%b;


  f=(double)a/(double)b;


  printf("%d %d %lf",d,r,f);


  return 0;


}

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

int main() {
	int x, y;
	cin >> x >> y;
	while (x || y){
		if (x > y){
			cout << y << " " << x << endl;
		}else{
			cout << x << " " << y << endl;
		}
		cin >> x >> y;
	}
}

Measured memory_bytes: 1160
#include <algorithm>
#include <cstring>
#include <cstdio>
#define my_abs(x) ((x) < 0 ? -(x) : (x))
typedef long long ll; 
int n, q, a, b; 
ll seg1[200005], seg2[200005], dp[200005], dt; 
inline void modify1(int pos, ll x)
{
	for (; pos <= n; pos += pos & -pos)
		seg1[pos] = std::min(seg1[pos], x); 
}
inline void modify2(int pos, ll x)
{
	for (; pos; pos -= pos & -pos)
		seg2[pos] = std::min(seg2[pos], x); 
}
inline ll query1(int pos)
{
	ll res = 1e18; 
	for (; pos; pos -= pos & -pos)
		res = std::min(res, seg1[pos]); 
	return res; 
}
inline ll query2(int pos)
{
	ll res = 1e18; 
	for (; pos <= n; pos += pos & -pos)
		res = std::min(res, seg2[pos]); 
	return res; 
}
int main()
{
	// freopen("ARC073-F.in", "r", stdin); 
	scanf("%d%d%d%d", &n, &q, &a, &b); 
	memset(dp, 0x3f, sizeof(dp)); 
	memset(seg1, 0x3f, sizeof(seg1)); 
	memset(seg2, 0x3f, sizeof(seg2)); 
	dp[b] = 0; 
	modify1(b, -b); 
	modify2(b, b); 
	while (q--)
	{
		b = a; 
		scanf("%d", &a); 
		ll cur = std::min(query1(a) + a, query2(a) - a) + dt; 
		dt += my_abs(a - b); 
		if (cur - dt < dp[b])
		{
			dp[b] = cur - dt; 
			modify1(b, dp[b] - b); 
			modify2(b, dp[b] + b); 
		}
	}
	ll ans = 1e18; 
	for (int i = 1; i <= n; i++)
		ans = std::min(ans, dp[i]); 
	printf("%lld\n", ans + dt);
	return 0; 
}


Measured memory_bytes: 4864
#include<bits/stdc++.h>
using namespace std;
int main(){
  	int a,b;
  	cin>>a>>b;
  	if(b==1){
    	cout<<0;
  	}
  	else if(a>=b){
    	cout<<1;
  	}
  	else{
	    int num=1,cnt=a;
	    while(1){
	      	cnt=cnt+a-1;
	      	num++;
	      	if(cnt>=b){
	        	break;
	    	}
	    }
	    cout<<num;
  	}
    return 0;
}

Measured memory_bytes: 256
W,H,N = map(int, input().split())
data = [0,W,0,H]
for i in range(0,N):
    xi,yi,ai = map(int, input().split())
    if ai == 1:
        data[0] = max([data[0],xi])
    elif ai == 2:
        data[1] = min([data[1],xi])
    elif ai == 3:
        data[2] = max([data[2],yi])
    else:
        data[3] = min([data[3],yi])

ans = (data[1]-data[0])*(data[3]-data[2])
if data[1]-data[0]<0 or data[3]-data[2]<0: ans = 0
print(ans)

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

int main() {
    int n;
    cin >> n;
    vector<int> es[n + 1];
    for (int i = 1; i < n; i++) {
        int a, b;
        cin >> a >> b;
        es[a].push_back(b);
        es[b].push_back(a);
    }
    int c[n], d[n];
    for (int i = 0; i < n; i++) {
        cin >> c[i];
    }
    sort(c, c + n);
    int m = accumulate(c, c + n - 1, 0);
    cout << m << endl;
    queue<int> que;
    que.push(1);
    int index = n - 1;
    bool used[n + 1];
    fill(used, used + n + 1, false);
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        if (used[x])
            continue;
        used[x] = true;
        d[x - 1] = c[index--];
        for (int v: es[x]) {
            que.push(v);
        }
    }
    cout << d[0];
    for (int i = 1; i < n; i++) {
        cout << ' ' << d[i];
    }
    cout << endl;
    return 0;
}


Measured memory_bytes: 1024
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <math.h>
#include <complex>
#include <cctype>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <assert.h>
#include <numeric>
#include <iomanip>
#include <limits.h>

using ll = long long;
using P = std::pair<ll, ll>;

#define rep(i, a, b) for (ll(i) = (a); i < (b); i++)
#define all(i) i.begin(), i.end()
#define debug(i) std::cout << i << "\n"

const ll INF = 100000000;
const ll MOD = 1000000007;

ll pow_mod(ll a,ll b,ll mod){
    if(a%mod==0){
        return 0;
    }

    ll x = 1;

    while(b>0){
        if(b&1){
            x = (x * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return x;
}

int main()
{
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    //問題文中の添え字が0-indexか1-indexか確認!

    ll n, left = 0, right = 2, ans = INT_MAX;
    ll P=0, Q=0, R=0, S=0;
    std::cin >> n;
    std::vector<ll> a(n);
    rep(i,0,n){
        std::cin >> a[i];
        S += a[i];
    }
    Q = a[0]+a[1];
    S -= Q;
    rep(i, 2, n)
    {
        std::vector<ll> temp(4);
        //P,Qの処理
        while(P+a[left]<Q-a[left]){
            P += a[left];
            Q -= a[left];
            left++;
        }

        //debug(P << " "<<Q);

        if(Q-P<a[left]){
            temp[0] = Q;
            temp[1] = P;
        }else{
            temp[0] = Q - a[left];
            temp[1] = P + a[left];
        }

        Q += a[i];

        //R,Sの処理
        while(R+a[right]<S-a[right]){
            R += a[right];
            S -= a[right];
            right++;
        }

        //debug(R  << " "<<  S);

        if (S - R < a[right])
        {
            temp[2] = S;
            temp[3] = R;
        }
        else
        {
            temp[2] = S - a[right];
            temp[3] = R + a[right];
        }

        R -= a[i];

        //ansの更新
        std::sort(all(temp));
        //rep(i,0,4){
        //    debug("temp"<<temp[i]);
        //}
        ans = std::min(ans, temp[3] - temp[0]);
    }

    std::cout << ans;
    return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define sz(a) int((a).size())
#define all(a) (a).begin(), (a).end()
#define REP(i,n) for(int i=0;i<(n);++i)
#define REPD(i,n) for(int i=(n)-1;i>=0;--i)
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define FORD(i,a,b) for(int i=(a);i>=(b);--i)
#define TLE() cerr<<"\nTime elapsed: "<<1000*clock()/CLOCKS_PER_SEC<<"ms.\n";
const ll MOD = 1E9+7;
const ll IINF = 1E18;
const ll INF = 1e9;
const double EPS = 1E-9;
const double PI = atan(1.0) * 4.0;
template<class T> T getbit(T s, int i) {return s>>i&1;}
template<class T> void flipbit(T& s, int i) {s^=(1LL<<i);}
constexpr int cntbit(ll x) {return __builtin_popcountll(x);}
constexpr int lg2(ll x) {return __lg(x);} // return int(log2(x))
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count()); 
ll fpow(ll a,ll p){ll res=1LL;while(p){if(p&1LL) res=res*a%MOD;a=a*a%MOD;p>>=1LL;} return res;}

int main() {
	ios_base::sync_with_stdio(0);cin.tie(0);
	int n,m,p;
	cin>>n>>m>>p;
	vector<array<int,3>> edges;
	REP(i,m){
		array<int,3> t;
		REP(j,3) cin>>t[j];
		t[2]=-(t[2]-p);
		edges.pb(t);
	}
	ll old_d;
	vector<ll> d(n+5,INF);
	d[1]=0;
	REP(i,n){
		if(i==n-1)
			old_d=d[n];
		for(auto x:edges){
			int u=x[0];
			int v=x[1];
			int w=x[2];
			if(d[u]!=INF&&d[u]+w<d[v])
				d[v]=(i==n-1)?-INF:d[u]+w;
		}
	}
	REP(i,n-1)
		for(auto x:edges){
			int u=x[0];
			int v=x[1];
			int w=x[2];
			if(d[u]!=INF&&d[u]+w<d[v])
				d[v]=d[u]+w;
		}
	if(old_d>d[n]){
		cout<<-1<<'\n';
		return 0;
	}
	cout<<max(0LL,-d[n])<<'\n';
}



Measured memory_bytes: 3800
n = gets.to_i
c = gets.chomp.chars
p = [c.count('W'), c.count('R')]
v = []
v[0] = (c[0] == 'W' ? 1 : 0)
n.pred.times do |i|
  v[i + 1] = v[i] + (c[i + 1] == 'W' ? 1 : 0)
end
ans = p.min
cnt = 0
mm = 0
md = p[0]
-1.downto(-n) do |i|
  if c[i] == 'R'
    mm += 1
    md = p[0] + i
    ans = mm + md if ans > mm + md
  else
    md = p[0] + i
    ans = mm + md if ans > mm + md
  end
  break if p[0] == -i
end
puts ans

Measured memory_bytes: 32304
#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
const long long mod = 1e9 + 7;
int main() {
    int s,w;
    cin >> s >> w;
    if (s > w) {
        cout << "safe";
    }
    else {
        cout << "unsafe";
    }
    return 0;
}

Measured memory_bytes: 3604
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <queue>
#include <string>
#include <cstring>
#include <numeric>
#include <cstdlib>
#include <cmath>
using namespace std;

typedef long long ll;

#define INF 10e10
#define rep(i,n) for(int i=0; i<n; i++)
#define rep_r(i,n,m) for(int i=m; i<n; i++)
#define END cout << endl
#define MOD 1000000007
#define pb push_back
// 昇順sort
#define sorti(x) sort(x.begin(), x.end())
// 降順sort
#define sortd(x) sort(x.begin(), x.end(), std::greater<int>())

int main() {
  int n;
  cin >> n;
  vector<int> p(n);
  ll mmax = 0;
  ll sum = 0;
  rep(i,n) {
    cin >> p[i];
    if (p[i] > mmax) {
      mmax = p[i];
    }
    sum += p[i];
  }

  ll tmp = mmax / 2;
  sum -= tmp;
  cout << sum << endl;
}


Measured memory_bytes: 256
n,k=map(int,input().split())
arr=[list(map(int,input().split())) for _ in range(n)]
ans=0
base=0
for i in range(32,-1,-1):
  if k&(2**i):
    tbase=base+2**i-1
    tmp=0
    for a,b in arr:
      if tbase==(a|tbase):
        tmp+=b
    ans=max(ans,tmp)
    base+=2**i
tmp=0
for a,b in arr:
  if base==(a|base):
    tmp+=b
ans=max(ans,tmp)
print(ans)

Measured memory_bytes: 27252
a, b = map(int, input().split())


def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x


def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a


print(len(list(set(prime_factorize(gcd(a, b))))) + 1)


Measured memory_bytes: 3064
#include <iostream>
#include <vector>
#include <bitset>
#include <utility>
#include <string>
#include <queue>
#include <stack>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long ll;
 
int main(){
  ll p=1000000007;
  ll N;
  cin >> N;

  vector<int> c(N);
  for(auto &ci:c) cin >> ci;

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

  //for(auto ci:c) cout << ci << endl;
  
  ll ans=0;
  for(int i=0;i<N;i++){
    //cout << c[i] << " " << N-i+1 << endl;
    ans+=c[i]*(N-i+1);
    ans%=p;
  }

  N=2*N-2;
  ll tmp=2;
  for(int i=0;i<61;i++){
    if(((ll)1<<i)&N){
      ans*=tmp; ans%=p;
    }
    tmp=tmp*tmp; tmp%=p;
  }
    
  cout << ans << endl;
  
  return 0;
}


Measured memory_bytes: 1152
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

a,b,c,k=map(int,input().split())
ans=0
if k>0 and a>0:
    ans+=min(k,a)
    k-=a

if k>0 and b>0:
    k-=b

if k>0 and c>0:
    ans-=k

print(ans)

Measured memory_bytes: 68144
#include<stdio.h>
#include<queue>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;
int UF[210000];
//set<int>S[210000];
int FIND(int a){
	if(UF[a]<0)return a;
	return UF[a]=FIND(UF[a]);
}
int HP=5;
void UNION(int a,int b){
	a=FIND(a);b=FIND(b);if(a==b)return;UF[a]+=UF[b];UF[b]=a;
}
vector<int>vis[210000];
int main(){
	int a,b;scanf("%d%d",&a,&b);
	priority_queue<pair<pair<int,int>,pair<int,int> > >Q;
	for(int i=0;i<b;i++){
		int s,t,u;
		scanf("%d%d%d",&s,&t,&u);
		Q.push(make_pair(make_pair(-u,HP),make_pair(s,t)));
		Q.push(make_pair(make_pair(-u-1,HP),make_pair(t,(s+1)%a)));
		
	}
	long long ret=0;
	for(int i=0;i<a;i++)UF[i]=-1;
	while(Q.size()){
		int cost=-Q.top().first.first;
		int id=Q.top().first.second;
		int L=Q.top().second.first;
		int R=Q.top().second.second;
		Q.pop();
	//	printf("%d %d %d\n",cost,L,R);
		if(L==R){
		//	Q.push(make_pair(make_pair(-cost-2,id),make_pair((L+1)%a,(R+1)%a)));
			continue;
		}
				
		if(FIND(L)==FIND(R)){
			bool ok=true;
			if(id==0)ok=false;
	//		for(set<int>::iterator it=S[L].begin();it!=S[L].end();it++){
	//			if(S[R].count(*it)){
	//				ok=false;break;
	//			}
	//		}
			if(ok){

	//	S[L].insert(id);
	//	S[R].insert(id);
				Q.push(make_pair(make_pair(-cost-2,id-1),make_pair((L+1)%a,(R+1)%a)));
			}
			continue;
		}
	//	S[L].insert(id);
	//	S[R].insert(id);
		UNION(L,R);

		//printf("%d %d\n",L,R);
		ret+=cost;
		Q.push(make_pair(make_pair(-cost-2,HP),make_pair((L+1)%a,(R+1)%a)));
	}
	printf("%lld\n",ret);
}

Measured memory_bytes: 13420
// Lucas Number

#include <iostream>

using namespace std;

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

	long long l[N+1];
	l[0] = 2; l[1] = 1;

	for (int i = 2; i <= N; ++i)
		l[i] = l[i-1] + l[i-2];

	cout << l[N] << endl;

	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <list>
#include <set>
#include <map>
#include <vector>
#include <math.h>
#include <fstream>
#include <sstream>
#include <unordered_map>
#include <ctime>
#include <assert.h>
using namespace std;

const unsigned long long BASE = (unsigned long long)(1e9 + 7);

#define FROM_0(i, n) for(int i = 0; i < (n); i++)
#define FROM_S(i, s, e) for(int i = (s); i < (e); i++)
#define ITER_BEGIN_END(iter, vec) for(auto iter = vec.begin(); iter != vec.end(); iter++)

int a[200001];

int main()
{
    int n;
    cin >> n;
    int minA = 1e5, maxA = -1e5, minAIdx = -1, maxAIdx = -1;
    FROM_0(i, n)
    {
        cin >> a[i];
        if (a[i] < minA)
        {
            minA = a[i];
            minAIdx = i;
        }
        else if (a[i] > maxA)
        {
            maxA = a[i];
            maxAIdx = i;
        }
    }
    vector<int> pos, neg;
    long long m = maxA - minA;
    FROM_0(i, n)
    {
        if (i == maxAIdx || i == minAIdx)
            continue;
        if (a[i] >= 0)
        {
            pos.push_back(a[i]);
            m += a[i];
        }
        if (a[i] < 0)
        {
            neg.push_back(a[i]);
            m -= a[i];
        }
    }
    cout << m << endl;
    long long now = minA;
    FROM_0(i, pos.size())
    {
        cout << now << ' ' << pos[i] << endl;
        now = now - pos[i];
    }
    cout << maxA << ' ' << now << endl;
    now = maxA - now;
    FROM_0(i, neg.size())
    {
        cout << now << ' ' << neg[i] << endl;
        now = now - neg[i];
    }
    assert(now == m);

    return 0;
}


Measured memory_bytes: 4288
#include <bits/stdc++.h>
#include<iostream>
using namespace std;
 
int main() {
    string x;
    int a(0),b(-1);
    cin >> x;

    for(int i = 0;i < x.size();i++){
       
        if(x.at(i) == 'A' || x.at(i) == 'C' || x.at(i) == 'G' || x.at(i) == 'T'){
             a++;
        }else{
             a = 0;
        }
        b = max(a,b);
    }
    cout << b;
  
}
   


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

int main(){
    int n;
    cin >> n;
    int a[n];
    vector<int> child(n,0);
    for(int i=1;i<n;i++){
        cin >> a[i];
        a[i]--;
        child[a[i]]++;
    }

    for(int i=0;i<n;i++){
        cout << child[i] << endl;
    }
}

Measured memory_bytes: 4844
#include <bits/stdc++.h>
 
using namespace std;
 
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define priority_queue pq 
#define vso(x) sort( x.begin() , x.end() )
#define aso(x) sort( x , x + x.size() )
#define print(x) cout << x << endl 
#define no cout << "NO\n" 
#define yes cout << "YES\n"
typedef long long ll ; 
typedef long double ld ;
typedef pair<ll, ll> pairs ;

// B3

int a[100009] , b[100009] , c[100009] ;
int dp_a[100009] , dp_b[100009] , dp_c[100009] ;

int main()
{
    //freopen("problem_name.out", "w", stdout) ;
    //freopen("problem_name.in", "r", stdin) ;
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //int t ; cin >> t ; while(t--){}
    int n ; cin >> n ;
    for ( int i = 1 ; i <= n ; i++ )
    {
        cin >> a[i] >> b[i] >> c[i] ;
        dp_a[i+1] += a[i] + max( dp_b[i] , dp_c[i] ) ;
        dp_b[i+1] += b[i] + max( dp_c[i] , dp_a[i] ) ;
        dp_c[i+1] += c[i] + max( dp_a[i] , dp_b[i] ) ;
        //cout << dp_a[i+1] << " " << dp_b[i+1] << " " << dp_c[i+1] << "\n" ;
    }
    print( max( dp_a[n+1] , max( dp_b[n+1] , dp_c[n+1] ) ) ) ;
}


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

const double PI=3.14159265358979323846;
int main(){
    double a,b,h,m;
    cin >> a >> b >> h >> m;
    
    double theta;
    theta = 30*h - 5.5*m;
    theta = theta*PI/180;
    double c = sqrt(a*a+b*b - 2*a*b*cos(theta));
    cout << fixed << setprecision(12);
    cout <<c <<endl;
}

Measured memory_bytes: 4144
using System;

class Program {
    private static int Main() {
        // 1行目は読み捨て
        var input = Console.ReadLine();
        // 2行目を読む
        input = Console.ReadLine();
        var values = input.Split( ' ' );

        for( int i = values.Length - 1; i >= 0; --i ) {
            Console.Write( values[ i ] );
            if( i != 0 ) {
                Console.Write( ' ' );
            }
        }
        Console.WriteLine();

        return 0;
    }
}

Measured memory_bytes: 9348
import java.util.*;
    import java.io.*;
     
    public class Main {
      public static void main(String[] args) throws IOException{
        BufferedReader rd = new BufferedReader(new InputStreamReader(System.in));
        int[] arr = new int[10];
        
        String s = rd.readLine();
        for (int i = 0; i < s.length(); i++) {
          int val = Integer.parseInt(Character.toString(s.charAt(i)));
          arr[val]++;
        }
        
        int sum = 0;
        for (int i = 1; i < 10; i++)
          	sum += (arr[i] * i);
        
        if (sum % 9 == 0)
          System.out.print("Yes");
        else
          System.out.print("No");
      }
    }

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

#define ll long long int

ll minCost_BU(int n,int h[]){

    ll dp[n+1] = {0};
    dp[2] = abs(h[1] - h[0]);

    for(int z=3;z<=n;z++){
        dp[z] = min(dp[z-1] + abs(h[z-1] - h[z-2]),dp[z-2] + abs(h[z-1] - h[z-3]));
    }

    return dp[n];
}

int main() {

    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

    int n;
    cin>>n;
    int h[n];
    for(int z=0;z<n;z++) cin>>h[z];

    cout<<minCost_BU(n,h);

    return 0;
}

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

int main(){
    int n;
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        if(i % 3 == 0){
            cout << " " << i;
        }else{
            int x = i;
            while(x){
                if(x % 10 == 3){
                    cout << " " << i;
                    break;
                }
                x /= 10;
            }
        }
    }
    cout << endl;
    
    return 0;
}


Measured memory_bytes: 3116
N, *ABCD = gets.split.map &:to_i
A, B, C, D = ABCD.map &:pred
S = gets.chomp
# p S[B-1..D+1]

if S[A+1..C-1]['##'] || S[B+1..D-1]['##']
  puts :No
elsif C < D
  puts :Yes
elsif S[B-1..D+1]['...']
  puts :Yes
else
  puts :No
end

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

const ll MAX=400005;
long long fac[MAX], finv[MAX], inv[MAX];

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}


int main() {
  ll n,k;
  cin>>n>>k;
  COMinit();
  ll ans=0;
  if(k>n-2){ans=COM(2*n-1,n);}
  else{
      rep(i,k+1){
          ans+=COM(n,i)*COM(n-1,i)%MOD;
          ans%=MOD;
      }
  }
  cout<<ans<<endl;
}

Measured memory_bytes: 9728
#include <iostream>
#include <queue>
#include <algorithm>
#include <functional>
using namespace std;

int n, a[100009], b[100009], c[100009], e[100009], f[16], dist[1 << 16], s;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>Q;

int main() {
	cin >> n;
	for (int i = 1; i <= n - 1; i++) {
		cin >> a[i] >> b[i] >> c[i];
		e[a[i]] ^= c[i]; e[b[i]] ^= c[i];
	}
	for (int i = 0; i < n; i++) { f[e[i]]++; }
	for (int i = 0; i < 16; i++) { if (i >= 1) s += f[i] / 2; f[i] %= 2; }
	for (int i = 0; i < (1 << 16); i++) dist[i] = (1 << 30);
	int I = 0;
	for (int i = 0; i < 16; i++) I += f[i] * (1 << i);
	dist[I] = 0; Q.push(make_pair(dist[I], I));
	while (!Q.empty()) {
		int pos = Q.top().second; Q.pop();
		vector<int>A; int bit[16]; for (int i = 0; i < 16; i++) bit[i] = 0;
		for (int i = 0; i < 16; i++) { if ((pos / (1 << i)) % 2 == 1) { A.push_back(i); bit[i] = 1; } }
		for (int i = 0; i < A.size(); i++) {
			for (int j = i + 1; j < A.size(); j++) {
				for (int k = 0; k < 16; k++) {
					int R = pos, S = bit[A[i]], T = bit[A[j]], U = bit[(A[i] ^ k)], V = bit[(A[j] ^ k)], cost = 1;
					bit[A[i]]--; R -= (1 << A[i]);
					bit[A[j]]--; R -= (1 << A[j]);
					bit[(A[i] ^ k)]++; R += (1 << (A[i] ^ k)); if (bit[(A[i] ^ k)] == 2) { bit[(A[i] ^ k)] = 0; if ((A[i] ^ k) != 0) cost++; R -= (2 << (A[i] ^ k)); }
					bit[(A[j] ^ k)]++; R += (1 << (A[j] ^ k)); if (bit[(A[j] ^ k)] == 2) { bit[(A[j] ^ k)] = 0; if ((A[j] ^ k) != 0) cost++; R -= (2 << (A[j] ^ k)); }
					if (dist[R] > dist[pos] + cost) {
						dist[R] = dist[pos] + cost;
						Q.push(make_pair(dist[R], R));
					}
					bit[A[i]] = S; bit[A[j]] = T; bit[(A[i] ^ k)] = U; bit[(A[j] ^ k)] = V;
				}
			}
		}
	}
	int t = s + min(dist[0], dist[1]);
	cout << t << endl;
	return 0;
}

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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef pair<int, ll> il;
typedef vector<ii> vii;
typedef vector<il> vil;
typedef vector<li> vli;

#define F first
#define S second
#define pb(x) push_back(x)
#define mp(a,b) make_pair(a,b)
#define sz size()
#define all(A)    A.begin(), A.end()
#define mem(a, b) memset(a, b, sizeof(a))
#define f0(i,b)   for(int i=0;i<(b);i++)
#define f1(i,b)   for(int i=1;i<=(b);i++)
#define f2(i,a,b) for(int i=(a);i<=(b);i++)
#define fr(i,b,a) for(int i=(b);i>=(a);i--)
#define rep(i,a,b,c) for(int i=(a);i!=(b);i+=(c))
#define mod 1000000007

#define forr(i,n)    for(i=0; i<n; i++)
#define whilee(i,t)  while(i!=t)
#define  sl(a)  scanf("%lld",&a)
#define  pl(a)  printf("%lld",a)

#define scan(x) do{while((x=getchar())<'0'); for(x-='0'; '0'<=(_=getchar()); x=(x<<3)+(x<<1)+_-'0');}while(0)
char _;

//for(auto it =A.begin(); it!=A.end(); it++)
//sort(A.begin(),A.end());
//binary_search(A.begin(),A.end(),x);
//reverse(A.begin(), A.end());
//cout << *max_element(A.begin(), A.end());
//cout << *min_element(A.begin(), A.end());
//count(A.begin(), A.end(), X); //counts the occurrences of X
//distance(A.begin(),A.end());  //distance between first to last element
//accumulate(A.begin(), A.end(), 0); //add
//next_permutation(A.begin(), A.end());
//prev_permutation(A.begin(), A.end());
//swap(S[0], T[0]);
//scanf("%d",&x);
//printf("%d\n",x);

//vector <int> A;
//deque <int> A;
//queue <int> A;
//stack <int> A;
//set <int> A;
//map <int,int> A;
//pair <int,int> A ;
//vector <pair <int,int>> A ;
//bitset<32> bset1;
//char ch;
//string S, T, U;
ll i, j, k, a, b, c=0, d, f, g, h, l, m, n, p, q, r, s, t, u, v, w, x, y, z, maxx=INT_MIN, minn=INT_MAX, ans=0, sum=0, cnt=0;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);//NULL
    cout.tie(nullptr);//NULL
    //int A[n];
    //scan(n);
    cin>>n>>a>>b;
    x=min(a,b);
    y=max(((a+b)-n),c);

    cout<<x<<" "<<y<<endl;

    return 0;
}



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

using namespace std;

#define rep(i, n) for(int i = 0; i < (n); ++i)
#define per(i, n) for(int i = (n)-1; i >= 0; --i)
#define eee(a) (cerr << (#a) << ": " << (a) << endl);
#define ppp(a) (cout << (a) << endl); 
#define cop(a) for(auto x:(a)){cout << x << endl;}

using ll = long long;
using pint = pair<int, int>;
using pll = pair<ll, ll>;
using mint = map<int, int>;

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

constexpr char sp = ' ';
constexpr char cmm = ',';
constexpr int MOD = 1e9+7;
constexpr int INF = 1e9;
constexpr ll LINF = 1e18;
constexpr double phi = (1+sqrt(5))/2;
constexpr double pi = 3.14159265358979323846264338327950288;

ll mod(ll a, ll b){return (a%b+b)%b;}
ll gcd(ll a, ll b){return b?gcd(b,a%b):a;}
ll lcm(ll a, ll b){return a*b/gcd(a,b);}
inline void Yes(){puts("Yes");}
inline void No(){puts("No");}
inline void Judge(bool b){b?Yes():No();}
inline void YES(){puts("YES");}
inline void NO(){puts("NO");}
inline void JUDGE(bool b){b?YES():NO();}
inline ll powmod(ll b, ll e){ll r=1;while(e>0){if(e&1)r=(r%MOD)*(b%MOD)%MOD;b=(b%MOD)*(b%MOD)%MOD;e>>=1;}return r;}
inline double distance(ll x1, ll y1, ll x2, ll y2){return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));}
inline double d2r(double d){return d*pi/180;}
inline double r2d(double r){return r*180/pi;}

template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& p) {return s << "(" << p.first << ", " << p.second << ")";}
template<typename T> ostream& operator<<(ostream& s, const vector<T>& v) {
    s<<'[';for(size_t i=0;i<v.size();++i){s << v[i];if(i < v.size()-1) s << ", ";}s<<']';return s;
}
struct __f{
    __f(){
        // comment this out when you use scanf or printf
        // cin.tie(0); ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(15);
    }
};

vector<ll> prime;
void eratos(const int max){
    bitset<1000001> isprime; isprime.set();
    isprime.reset(0); isprime.reset(1);
    for(int i = 2; i*i <= max; ++i)
        if(isprime.test(i))
            for(int j = 2; i*j <= max; ++j)
                isprime.reset(i*j);
    for(int i = 0; i <= max; ++i)
        if(isprime.test(i)) prime.emplace_back(i);
}
int main(){

    eratos(100010);
    int x;
    scanf("%d", &x);

    ppp(*lower_bound(prime.begin(), prime.end(), x));





    return 0;
}


Measured memory_bytes: 512
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair < int, int >;

void solve() {
	
}

int main() {
	ios::sync_with_stdio (false);
	int n;
	string s;
	cin >> n;
	map < string, int > mp;
	vector < int > duration (n);
	for (int i = 0; i < n; i++) {
		cin >> s >> duration[i];
		mp[s] = i;
	}
	cin >> s;
	int index = mp[s];
	int ans = 0;
	for (int i = index + 1; i < n; i++) {
		ans += duration[i];
	}
	cout << ans << endl;
	return 0;
}



Measured memory_bytes: 256
fun main(args : Array<String>) {
    var S = readString()

    when(S){
        "SUN"->{
            print(7)
        }
        "MON"->{
            print(6)
        }
        "TUE"->{
            print(5)
        }
        "WED"->{
            print(4)
        }
        "THU"->{
            print(3)
        }
        "FRI"->{
            print(2)
        }
        "SAT"->{
            print(1)
        }
    }
    return
}

fun readString() = readLine()!!

Measured memory_bytes: 31444
#include<bits/stdc++.h>
using namespace std;
int ctoi(const char c){
  switch(c){
    case '0': return 0;
    case '1': return 1;
    case '2': return 2;
    case '3': return 3;
    case '4': return 4;
    case '5': return 5;
    case '6': return 6;
    case '7': return 7;
    case '8': return 8;
    case '9': return 9;
    default : return -1;
  }
}
int main(){
  char s;
  int sum=0;
  while(cin >> s){
    sum+=ctoi(s);
  }
  if(sum%9==0)cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 3608
#define _CRT_SECURE_NO_WARNINGS
#include<cstdio>
#include<algorithm>
#include <cstdlib>
#include <cstring>
#include<iostream>

using namespace std;

int main(){
	int A, B, C, ans = 0;
	scanf("%d %d %d", &A, &B, &C);
	int x, y, z;
	x = max(max(A, B), C);
	y = min(min(A, B), C);;
	z = A + B + C - x - y;
	ans += x - z;
	if ((z - y) % 2 == 0){
		ans += (z - y) / 2;
	}
	else{
		ans += (z - y+1) / 2 + 1;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256