akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int main()
{
    int h,w,i,j;
    cin>>h>>w;
    char str[h+1][w+1];
    for(i=0;i<h;i++){
        for(j=0;j<w;j++){
            cin>>str[i][j];
        }
    }
    for(i=0;i<w+2;i++){
        cout<<"#";
    }
    cout<<endl;
    int cnt;
    for(i=0;i<h;i++){
        cnt=1;
        for(j=0;j<w;j++){
            if(cnt==1){
               cout<<"#"<<str[i][0];
               cnt++;
                if(w==1){
                    cout<<"#"<<endl;
                }
                continue;
            }
            cout<<str[i][j];
            if(cnt==w){
               cout<<"#"<<endl;
            }
            cnt++;
        }
    }
    for(i=0;i<w+2;i++){
        cout<<"#";
    }
    cout<<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 all(n) begin(n),end(n)
using ll = long long;
using P = pair<int,int>;

int main() {
    string s;
    int k;
    cin >> s >> k;
    int n = s.size();
    rep(i,s.size()){
        if(s[i]=='a') continue;
        int t = s[i]-'a';//tばんめ
        if(t+k >= 26 && k-(26-t)>=0) {
            s[i]='a';
            k-=26-t;
        }
    }
    if(k){
        int t = k%26;
        int now = s[n-1]-'a';
        now+=t;
        s[n-1]='a'+now;
    }
    cout << s << endl;
    return 0;
}

Measured memory_bytes: 3728
s = str(input())
y = int(s[0:4])
m = int(s[5:7])
d = int(s[8:])
if y < 2019:
    print("Heisei")
elif y > 2019:
    print("TBD")
else:
    if m <= 4:
        print("Heisei")
    else:
        print("TBD")
        

Measured memory_bytes: 2940
class Pro
  attr_reader :name, :time
  def initialize(name, time)
    @name = name
    @time = time
  end
end

n, q = gets.split.map(&:to_i)
processes = $stdin.read.split()
queue = []
for i in 0..n-1
  queue[i] = Pro.new(processes[2*i], processes[2*i+1].to_i)
end

total_time = 0
while queue.size > 0 do
  que = queue.shift
  if que.time - q > 0 then
    queue.push(Pro.new(que.name, que.time - q))
    total_time += q
  else
    total_time += que.time
    printf "%s %d\n",que.name, total_time
  end
end

Measured memory_bytes: 21268
n = int(input())
a = list(map(int, input().split()))
a_cs = [0] * (n + 1)
for i in range(n):
    a_cs[i + 1] = a_cs[i] + a[i]

i1 = 1
i3 = 3
ans = 10**14
for i2 in range(2, n - 1):
    while i1 + 1 < i2 and abs(a_cs[i1] * 2 - a_cs[i2]) > abs(a_cs[i1 + 1] * 2 -
                                                             a_cs[i2]):
        i1 += 1

    while i3 + 1 < n and abs(a_cs[-1] + a_cs[i2] - a_cs[i3] *
                             2) > abs(a_cs[-1] + a_cs[i2] - a_cs[i3 + 1] * 2):
        i3 += 1

    p = a_cs[i1]  # [0,i1)
    q = a_cs[i2] - a_cs[i1]  # [i1, i2)
    r = a_cs[i3] - a_cs[i2]  # [i2, i3)
    s = a_cs[n] - a_cs[i3]  # [i3, n)
    cand = max(p, q, r, s) - min(p, q, r, s)
    ans = min(ans, cand)

print(ans)


Measured memory_bytes: 25676
#include <stdio.h>
int main()
{
	int m,f,b,GO,tei;
	scanf("%d%d%d",&m,&f,&b);
	GO=m+f;
	if(GO<b){
		printf("NA\n");
	}
	else if(b>m){
		tei=b-m;
		printf("%d\n",tei);
	}
	else if(b<m){
		tei=0;
		printf("%d\n",tei);
	}
	return 0;
}



Measured memory_bytes: 2044
#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int main(){
	int n; cin >> n;
	vector<int> a(n), b(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	rep(i, n) {
		cin >> b[i];
	}
	int x = 10000; int y = 10000;
	for (int i = 0; i < n; i++) {
		if (a[i] == 0) x = min(x, b[i]);
		else y = min(y, b[i]);
	}
	if (x == 10000 || y == 10000) cout << 0 << endl;
	else cout << x + y << endl;
	return 0;
}


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

const int mod = 1000000007;
struct mint {
    ll x;  // typedef long long ll;
    mint(ll x = 0) : x((x % mod + mod) % mod) {}
    mint operator-() const { return mint(-x); }
    mint& operator+=(const mint a) {
        if ((x += a.x) >= mod) x -= mod;
        return *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 { return mint(*this) += a; }
    mint operator-(const mint a) const { return mint(*this) -= a; }
    mint operator*(const mint a) const { return mint(*this) *= a; }
    mint pow(ll t) const {
        if (!t) return 1;
        mint a = pow(t >> 1);
        a *= a;
        if (t & 1) a *= *this;
        return a;
    }

    // for prime mod
    mint inv() const { return pow(mod - 2); }
    mint& operator/=(const mint a) { return *this *= a.inv(); }
    mint operator/(const mint a) const { return mint(*this) /= a; }
};
istream& operator>>(istream& is, mint& a) { return is >> a.x; }
ostream& operator<<(ostream& os, const mint& a) { return os << a.x; }

void solve(long long N, std::vector<long long> A) {
    mint sum = 0;
    for (int i = 0; i < N; i++) {
        sum += A[i];
    }
    mint ans = 0;
    for (int i = 0; i < N; i++) {
        sum -= A[i];
        ans += mint(A[i]) * sum;
    }
    cout << ans << endl;
}

// Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
int main() {
    long long N;
    scanf("%lld", &N);
    std::vector<long long> A(N);
    for (int i = 0; i < N; i++) {
        scanf("%lld", &A[i]);
    }
    solve(N, std::move(A));
    return 0;
}


Measured memory_bytes: 4848
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<queue>
#include<cmath>
#include<cstdio>
#include<tuple>
#include<bitset>

using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;++i)
#define rep1(i,n) for(int i=1;i<=n;++i)
#define ALL(x) x.begin(),x.end()
#define ll long long
typedef pair<int,int> P;
const int inf=1000000007;
const int MOD=1000000007;
signed main(){
  int n;cin>>n;
  int res=1;
  rep1(i,n){
    res*=i;
    res%=MOD;
  }
  cout<<res<<"\n";
  return 0;
}


Measured memory_bytes: 256
#![allow(non_snake_case)]

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

fn main() {
    input!{
        d: usize,
    }
    let ans = match d {
        25 => "Christmas".to_string(),
        24 => "Christmas Eve".to_string(),
        23 => "Christmas Eve Eve".to_string(),
        22 => "Christmas Eve Eve Eve".to_string(),
        _ => "".to_string(),
    };
    println!("{}", ans);
}

Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
const int N = 100005;

int a[N], b[N];
int main() {
    int n;
    cin >> n;
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (n - 1) / i;
    }
    cout << ans << endl;
    return 0;
}


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

int main() {
  int n;
  cin >> n;
  vector<int> mochi(n);
  for (int i=0; i<n; i++) cin >> mochi.at(i);
  vector<int> kagamimochi(0);
  for (int i=0; i<n; i++) {
    if (!count(kagamimochi.begin(),kagamimochi.end(),mochi.at(i))) kagamimochi.push_back(mochi.at(i));
  }
  cout << kagamimochi.size() << endl;
}

Measured memory_bytes: 256
A = str(input())
B = str(input())
C = str(input())

Set = A
card = A[0]
while card != '': 
    if card == 'a' :
        if A == "":
            print("A")
            break
        else:
            card = A[0]
            A = A[1:] #文字列の先頭から何文字か取り除く
            Set = A
            
    elif  card == 'b' :
        if B == "":
            print("B")
            break
        else:
            card = B[0]
            B = B[1:]
            Set = B
            
    
    elif card == 'c' :
        if C == "":
            print("C")
            break
        else:
            card = C[0]
            C = C[1:]
            Set = C
        

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

vector<int> mynums;

vector<int> div6,div3;
vector<int> div21,div22;
const int MAX=30000;

int main()
{
    int i;
    int n;

    scanf("%d",&n);

    if (n==3)
    {
        printf("2 5 63\n");
    }
    else
    {
        mynums.push_back(2);
        mynums.push_back(4);
        mynums.push_back(3);
        mynums.push_back(9);

        for (i=6;i<=MAX;i+=6)
        {
            div6.push_back(i);
        }

        for (i=8;i<=MAX;i+=2)
        {
            if (i%6==0)
                continue;

            if (i%3==1)
                div21.push_back(i);
            else
                div22.push_back(i);
        }

        for (i=15;i<=MAX;i+=6)
        {
            div3.push_back(i);
        }

        n-=4;

        while(n>1)
        {
            if (!div21.empty() && !div22.empty())
            {
                mynums.push_back(div21.back());
                mynums.push_back(div22.back());

                div21.pop_back();
                div22.pop_back();

                n-=2;
            }
            else if (div3.size()>1)
            {
                mynums.push_back(div3.back());
                div3.pop_back();

                mynums.push_back(div3.back());
                div3.pop_back();

                n-=2;
            }
            else if (!div6.empty())
            {
                mynums.push_back(div6.back());
                div6.pop_back();

                n--;
            }
            else
            {
                printf("BAD\n");
                while(1);
            }
        }

        if (n==1)
        {
            if (div6.empty())
            {
                printf("BAD\n");
                while(1);
            }

            mynums.push_back(div6.back());
        }

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

        for (i=0;i<mynums.size();i++)
        {
            if (i!=0)
                printf(" ");
            printf("%d",mynums[i]);
        }
        printf("\n");
    }

    return 0;
}


Measured memory_bytes: 640
from collections import deque
import sys
input = sys.stdin.readline
n, x, y = map(int, input().split())
g = dict()
for i in range(n):
    if i == 0:
        g[i] = [i+1]
    elif i == n-1:
        g[i] = [i-1]
    else:
        g[i] = [i-1, i+1]
g[x-1].append(y-1)
g[y-1].append(x-1)
# print(g)
distance = [0]*(n-1)
# 1番ノードから各ノードへの最短距離を求めていく.
for i in range(n):
    queue = deque()
    visited = [0]*n
    # まず処理される予定のノードが格納されているqueueに最初のノードを格納する
    queue.append(i)
    while queue:
        target = queue.popleft()
        for j in g[target]:
                if visited[j] == 0 or visited[j] > visited[target] + 1:
                    visited[j] = visited[target] + 1
                    queue.append(j)
    for k, a in enumerate(visited):
        if k > i:
            if a >= 1:
                distance[a-1] += 1
    # print(f"{i}番ノードからの各ノードへの最短距離は{visited}である")
for l in distance:
    print(l)

Measured memory_bytes: 48476
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        
        Scanner scanner = new Scanner(System.in);
        
        String line = scanner.nextLine();
        String[] inputs = line.split(" ");
        
        int x = Integer.parseInt(inputs[0]);
        int y = Integer.parseInt(inputs[1]);
        
        int max = Integer.MIN_VALUE;
        
        if (x + y > max) {
            max = x + y;
        }
        if (x - y > max) {
            max = x - y;
        }
        
        if (x * y > max) {
            max = x * y;
        }
        
        System.out.println(max);
        
        
    }
}


Measured memory_bytes: 22868
import qualified Data.ByteString.Char8 as BS
import qualified Data.Maybe as MA
import qualified Data.Vector.Unboxed as V

main = do
    (n, _) <- MA.fromJust . BS.readInt <$> BS.getLine
    xs' <- fmap (fst . MA.fromJust . BS.readInt) . BS.words <$> BS.getLine
    let m = maximum xs'
    let xs = V.fromList xs'
    putStrLn . show . minimum $ fmap (\p -> V.foldl (\total x -> total + (x - p)^2) 0 xs) [1..m]


Measured memory_bytes: 508
#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define ld long double
#define pb push_back
 
#define sec second
#define fir first
#define mo 1000000007
#define inf 1e18
#define rep(i, s, n) for (ll i = s; i < n; i = i + 1)
#define rrep(i,s,n) for(ll i=s;i>=n;i--)

ll mod(ll n) { return (n % (ll)mo + (ll)mo)%(ll)mo;}

int main(){
	ll k;
	cin>>k;
    ll x = 0;
    set<ll> s;
    ll cnt = 0;
    while(true){
    	cnt++;
    	x = (x*10 + 7)%k;
    	if(x==0) return cout<<cnt,0;
    	if(s.count(x)) return cout<<-1,0;
    	s.insert(x);
    }

}
		 

Measured memory_bytes: 50460
private fun readInts() = readLine()!!.split(" ").map { it.toInt() }

fun main(args: Array<String>) {
    val (N) = readInts()
    val T = readInts()
    val (M) = readInts()
    val px = (0 until M).map { readInts() }

    for ((p, x) in px) {
        println(T.mapIndexed { index, time -> if (index + 1 == p) x else time }.sum())
    }
}

Measured memory_bytes: 37824
#include<bits/stdc++.h>
#include<cmath>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
typedef vector<string> vs;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef pair <double,double> dd;
typedef vector<int> vi;
typedef vector<vi> vvi;
#define inf=1000000000
ll ipow(ll base, ll exp)
{
    ll result = 1;
    for (;;)
    {
        if (exp & 1)
            result *= base;
        exp >>= 1;
        if (!exp)
            break;
        base *= base;
    }

    return result;
}
ll p(ll d){
    ull s=1;
    ll cnt{0};
    while(d>s)s=ipow(2,cnt);
    return s-d;

}

vector<int> a,meme;
int mem(int AJ){
    if(meme[AJ]>=0)return meme[AJ];
    return meme[AJ]=min(mem(AJ-1)+abs(a[AJ-1]-a[AJ]),mem(AJ-2)+abs(a[AJ-2]-a[AJ]));

}
int main(){
 int n;
 cin>>n;
 for(int i=0;i<n;i++)meme.push_back(-1);
     for(int i=0;i<n;i++)a.push_back(0);
 for(int i=0;i<n;i++)
    cin>>a[i];
 meme[0]=0;
 meme[1]=abs(a[1]-a[0]);
 meme[2]=min(abs(a[2]-a[0]),meme[1]+abs(a[2]-a[1]));

 cout<<mem(n-1);
return 0;
}


Measured memory_bytes: 3448
#include <iostream>
using namespace std;
int isValid(int nr) {
	if (nr >= 1 && nr <= 9)
		return 1;
		return 0;
}
int main()
{
	int N;
	cin >> N;
	bool OK = 0;
	int a[] = { 1,2,3,4,5,6,7,8,9 };
	for(int i=0;i<9;i++)
		for (int j = i; j < 9; j++) {
			if (a[i] * a[j] == N)
			{
				OK = 1;
				break;
			}
		}
	if (OK)
		cout << "Yes";
	else cout << "No";

}

Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<vector>
#include<utility>
#include<algorithm>
#include<map>
#include<cstdlib>
#include<cmath>
#include<numeric>
#include<iomanip>
#include<functional>
#include<cstdlib>
#include<queue>
#include<deque>
const double PI = acos(-1);
#define rep(i,n)for(int i=0;i<(n);i++)
using namespace std;
using ll =long long;
const int mod = 1000000007;
class mint {
	long long x;
public:
	mint(long long x = 0) : x((x% mod + mod) % mod) {}
	mint operator-() const {
		return mint(-x);
	}
	mint& operator+=(const mint & a) {
		if ((x += a.x) >= mod) x -= mod;
		return *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 pow(ll t) const {
		if (!t) return 1;
		mint a = pow(t >> 1);
		a *= a;
		if (t & 1) a *= *this;
		return a;
	}
	// for prime mod
	mint inv() const {
		return pow(mod - 2);
	}
	mint& operator/=(const mint & a) {
		return (*this) *= a.inv();
	}
	mint operator/(const mint & a) const {
		mint res(*this);
		return res /= a;
	}

	friend ostream& operator<<(ostream & os, const mint & m) {
		os << m.x;
		return os;
	}
};
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return 0;
}

ll gcd(ll a, ll b) {
	if (a % b == 0) {
		return b;
	}
	else {
		return gcd(b, a % b);
	}
}
ll lcm(ll a, ll b) {
	return a * b / gcd(a, b);
};
//fixed << setprecision(2)
bool a[500][500] = {};
char c[500][500];
bool search(int x,int w,int h,int y) {
	if (x < 0 || x >= w || y < 0 || y >= h) {
		return false;

	}
	else if (c[y][x] == '#') {
		return false;
	}
	if (a[y][x] == true) {
		return false;
	}
	if (c[y][x] == 'g') {
		return true;
	}
	a[y][x] = true;
	if (search(x + 1, w, h, y) || search(x - 1, w, h, y) || search(x, w, h, y + 1) || search(x, w, h, y - 1)) {
		return true;
	}
	else {
		return false;
	}

}

//小文字=大文字+32
int main() {
	int a, b, c, d, e,k;
	cin >> a >> b >> c >> d >> e >> k;
	int Mi, Mx;
	Mi = min({ a, b, c, d, e });
	Mx = max({ a,b,c,d,e });
	if (abs( Mx - Mi <= k )) {
		cout << "Yay!";
	}
	else {
		cout << ":(";
	}
}
	



Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
using ll = long long;

int main() {
    string S;
    cin >> S;
    int temp = 0, ans = 0;
    for (int i = 0; i < S.size(); ++i) {
        if(S[i]=='A' || S[i]=='G' || S[i]=='C' || S[i]=='T') {
            temp++;
            ans = max(ans,temp);
        }else{
            temp = 0;
        }
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define mod 1000000007
#define INF 10000000000000001
#define F first
#define S second
#define LB lower_bound
#define UB upper_bound
#define vc vector
#define vll vector<long long>
#define pll pair<long long,long long> 
#define pb push_back
#define all(v) v.begin(),v.end()
#define T ll test;cin>>test; while(test--)
#define rep(i,a,n) for(ll i=a;i<(long long)n;++i)
#define repr(i,n,a) for(ll i=n;i>(long long)a;--i)
#define MAX 100005
#define sz(x) (ll)x.size()
#define ins insert
#define mp make_pair
//typedef  long long int in;
typedef long long ll;
typedef long double ld;
using namespace std;

inline int add(int a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int sub(int a,int b){a-=b;if(a<0)a+=mod;return a;}
inline int mul(int a,int b){return (a*1ll*b)%mod;}
inline int power(int a,int b){int rt=1;while(b>0){if(b&1)rt=mul(rt,a);a=mul(a,a);b>>=1;}return rt;}
inline int inv(int a){return power(a,mod-2);}


signed  main()
{
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    string s,t;
    cin>>s>>t;
    ll cnt=0;
    rep(i,0,sz(s))
    {
    	if(s[i]!=t[i]) cnt++;
    	
	}
	cout<<cnt<<endl;
	
}

Measured memory_bytes: 3836
import java.util.*;
import java.io.*;
import java.math.BigInteger; 

 public class Main{
// taking inputs
static BufferedReader s1;
static BufferedWriter out;
static String read() throws IOException{String line="";while(line.length()==0){line=s1.readLine();continue;}return line;}
static int int_v (String s1){return Integer.parseInt(s1);}
static long long_v(String s1){return Long.parseLong(s1);}
static int[] int_arr() throws IOException{String[] a=read().split(" ");int[] b=new int[a.length];for(int i=0;i<a.length;i++){b[i]=int_v(a[i]);}return b;}
static long[] long_arr() throws IOException{String[] a=read().split(" ");long[] b=new long[a.length];for(int i=0;i<a.length;i++){b[i]=long_v(a[i]);}return b;}
static void assign(){s1=new BufferedReader(new InputStreamReader(System.in));out=new BufferedWriter(new OutputStreamWriter(System.out));}
// ends

//......................................@uthor_Alx..............................................

   public static void main(String[] args) throws  IOException{
	        		  assign();
              int[] x=int_arr();
              int[] arr=int_arr();
              int sum=0;
              for(int x1:arr){sum+=x1;}
              	if(sum>x[0]){out.write("-1\n");}
              else{out.write((x[0]-sum)+"\n");}
              out.flush();
	        		 
	}
	       
	          
}

	    

	
  





Measured memory_bytes: 37532
#include<iostream>

using namespace std;

int main()
{
    int n,w;
    cin >> n >> w;
    int dp[n+1][w+1]={};
    pair<int,int> p[n];
    int a,b;
    for(int i=0;i<n;i++){
        cin >> a >> b;
        p[i]=make_pair(a,b);
    }
    for(int i=0;i<n;i++)
        for(int j=0;j<w;j++){
            if(j+1-p[i].second>=0)
                dp[i+1][j+1]=max(dp[i+1][j],max(dp[i][j+1],dp[i][j+1-p[i].second]+p[i].first));
            else
                dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
        }
    cout << dp[n][w] << endl;
    return 0;
}



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

int main() {
    long long x, k, d;
    cin >> x >> k >> d;
    x = abs(x);
    long long y = min((x/d), k);
    k -= y;
    x -= d*y;
    if (k&1) {
        cout << abs(x-d);
    }
    else cout << x;
}

Measured memory_bytes: 3604
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,a,b;
	scanf("%d %d %d",&n,&a,&b);
	printf("%d ",min(a,b));
	if(a+b>n)
		printf("%d",a+b-n);
	else
		printf("0"); 
	return 0;
}

Measured memory_bytes: 256
from collections import deque
n, d, a = map(int, input().split())
m = [list(map(int, input().split())) for _ in range(n)]
m.sort()
r = 1
d *= 2
q=deque([])
for i in range(n):
    while r < n and m[i][0] + d >= m[r][0]:
        r += 1
    m[i].append(r)
    m[i][1] = (m[i][1] + a - 1) // a
res = 0
tdamage = 0
for i in range(n):
    while q and q[0][0] <= i:
        minus = q.popleft()
        tdamage -= minus[1]
    m[i][1] -= tdamage
    if m[i][1] > 0:
        res += m[i][1]
        tdamage += m[i][1]
        q.append([m[i][2],m[i][1]])
print(res)


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

int m = 1e9+7;

void add_self(int& a, int b){
    a = a+b;
    if(a>=m) a=a-m;
}
void sub_self(int& a, int b){
    a = a-b;
    if(a<0) a=a+m;
}

int32_t main() {
	int n, k;
	cin>>n>>k;
	int arr[n];
	for(int i=0;i<n;i++) cin>>arr[i];
	
	vector<int> dp(k+1,0);
	dp[0]=1;
	
	for(int i=0;i<n;i++){
	    for(int j=1;j<=k;j++) add_self(dp[j],dp[j-1]);
	    for(int j=k;j>=0;j--){
	        int temp = j-arr[i]-1;
	        if(temp>=0) sub_self(dp[j],dp[temp]);
	        //cout<<dp[j];
	    }
	    //cout<<endl;
	}
	cout<<(dp[k]+m)%m;
	return 0;
}

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

int main(){
  long long int n;
  cin>>n;
  cout<<(1+n)*n/2-(3+n-n%3)*(n-n%3)/3/2-(5+n-n%5)*(n-n%5)/5/2+(15+n-n%15)*(n-n%15)/15/2<<endl;
}
  

Measured memory_bytes: 3620
#include <stdio.h>
int main(void){
    // Your code here!
    int n;
    scanf("%d",&n);
    int d[n],max[2],at[2];
    int i;
    max[0]=0;
    at[0]=0;
    for(i=0;i<n;i++){
        scanf("%d",&d[i]);
        if(max[0]<d[i]){
            max[1]=max[0];
            at[1]=at[0];
            max[0]=d[i];
            at[0]=i;
        }else if(max[1]<d[i]){
            max[1]=d[i];
            at[1]=i;
        }
            
        
    }
    for(i=0;i<n;i++){
        if(at[0]==i){
        printf("%d\n",max[1]); 
            
        }else{
        printf("%d\n",max[0]);
        }
        
    }
   
    return (0);
}

Measured memory_bytes: 2304
n = int(input())
v = int(input())
maxv = v
minv = v
rieki = -(10**9)
for i in range(n-1) :
    v = int(input())
    if rieki < v - minv :
        rieki = v - minv
    if minv > v :
        minv = v
print(rieki)



Measured memory_bytes: 5612
#include <cstdio>
using namespace std;

const int MAX_H = 1000;
int h, w;
int b[MAX_H][MAX_H] = {0};
int row[MAX_H] = {0}, col[MAX_H] = {0};

int main(){
	scanf("%d %d", &h, &w);
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			scanf("%d", &b[y][x]);
			if( b[y][x] == 0 ){
				row[y]++;
				col[x]++;
			}
		}
	}
	for(int y=0 ; y < h ; y++ ){
		for(int x=0 ; x < w ; x++ ){
			int a = (row[y] + col[x] + b[y][x] + 1) % 2;
			printf("%d", a);
			if( x + 1 == w )
				printf("\n");
			else
				printf(" ");
		}
	}
}

Measured memory_bytes: 4680
#define ll long long
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ll n;
    cin>>n;
    ll a[n];
    ll s=0,avg,ans=0,ans1=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        s+=a[i];
    }
    avg = s/n;
    for(int i=0;i<n;i++)
    {
        ans+=pow(a[i]-avg,2);
    }
    avg ++;

    for(int i=0;i<n;i++)
    {
        ans1+=pow(a[i]-avg,2);
    }
    cout<<min(ans,ans1)<<endl;
}


Measured memory_bytes: 256
while n = gets.to_i
  break if n == 0
  m = gets.to_i
  init = Array.new(n){0}
  init[m-1] = 1
  hit = gets.to_i
  ans = Array.new(n){0}
  ans[hit-1] = 1
  d = gets.to_i

  trial = init.clone
  arr = []
  candidate = []
  d.times{|i|
    arr[i] = gets.chomp.split("").map(&:to_i)
    candidate << [i, 0] if arr[i][0] == 0 && arr[i][1] == 0
    1.upto(n-3){|j|
      candidate << [i, j] if arr[i][j-1] == 0 && arr[i][j] == 0 && arr[i][j+1] == 0
    }
    candidate << [i, n-2] if arr[i][n-3] == 0 && arr[i][n-2] == 0
    (n-1).times{|j|
      trial[j], trial[j+1] = trial[j+1], trial[j] if arr[i][j] == 1
    }
  }
  if trial == ans
    puts 0
  else
    flag = false
    candidate.each{|x, y|
      b = arr.map(&:dup)
      b[x][y] = 1
      trial = init.clone
      d.times{|i|
        (n-1).times{|j|
          trial[j], trial[j+1] = trial[j+1], trial[j] if b[i][j] == 1
        }
      }
      if trial == ans
        puts "#{x+1} #{y+1}"
        flag = true
        break
      end
    }
    if flag == false
      puts 1
    end
  end
end

Measured memory_bytes: 8956
import sys
#from collections import defaultdict, deque, Counter
#import bisect
#import heapq
#import math
#from itertools import accumulate
#from itertools import permutations as perm
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as combr
#from fractions import gcd
#import numpy as np

stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)
MIN = -10 ** 9
MOD = 10 ** 9 + 7
INF = float("inf")
IINF = 10 ** 18

def main():
    n = str(stdin.readline().rstrip())
    #A, B, C = map(int, stdin.readline().rstrip().split())
    #l = list(map(int, stdin.readline().rstrip().split()))
    #numbers = [[int(c) for c in l.strip().split()] for l in sys.stdin]
    #word = [stdin.readline().rstrip() for _ in range(n)]
    #number = [[int(c) for c in stdin.readline().rstrip()] for _ in range(n)]
    #zeros = [[0] * w for i in range(h)]

    if int(n[-1]) == 3:
        print("bon")
    elif int(n[-1]) == 0 or int(n[-1]) == 1 or int(n[-1]) == 6 or int(n[-1]) == 8:
        print("pon")
    else:
        print("hon")



main()


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

// types - only for stuff used a lot 
using ll = long long;
#define vv vector
#define Pp pair

// IO
#define get(x) scanf("%d",&x)
#define getl(x) scanf("%lld",&x);

// Operations
#define pb push_back
#define pob pop_back
#define sz(a) int(a.size()) 
#define re(a,b) a=max(a,b) // relax
#define ri(a,b) a=min(a,b) // relaxi

// Debugging

#ifndef LOCAL
#define cerr if (0) cerr
#else
#define cerr cout
#endif

#define print(arr,n) {for (int _ = 0; _ < n; _++) cerr<<arr[_]<<" "; cerr << endl; }
#define printv(vec)  {for (int _ : vec) cerr<<_<<" "; cerr<<endl;}

const int mod = 998244353, oo = 1e9;
const ll loo = 1e18;

// Functions 
ll modpow(ll a, ll b) {
	ll ans = 1; // faster modpow than recursive
	for (; b; b/=2,a=a*a%mod)
		if (b&1) ans = (ans*a)%mod;
	return ans;
}
ll gcd(ll a, ll b) {
	while (a) b%=a,swap(a,b);
	return b;
}
#define bitcount __builtin_popcountll
#define f(i,a,b) for (int i = a; i < b; i++)
#define fr(i,a,b) for (int i = b-1; i >= a; i--)


/* 

   ALRIGHT HACKERS, THIS IS WHERE THE ACTUAL CODE BEGINS

 */

const bool DEBUG = 1;

const int N = 1e6+1;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
#ifdef LOCAL
	if (DEBUG) freopen("input.txt", "r", stdin);
	if (DEBUG) freopen("output.txt", "w", stdout);
	clock_t start = clock();
#endif

	int n; cin>>n;
	int a[n];
	f(i,0,n) cin>>a[i];
	int sieve[N];
	fill(sieve,sieve+N,0);
	f(i,2,N) if (!sieve[i]) {
		sieve[i] = i;
		for (int j = i; j < N; j += i)
			sieve[j] = i;
	}

	auto fac = [&](int i) {
		int cnt = 0;
		while (i>1 && ++cnt) {
			int p = sieve[i];
			if (i%(p*p) == 0) return -1;
			i /= p;
		}
		return cnt&1;
	};

	auto add = [&](ll &a, ll b) {
		a += b;
		if (a>=mod) a-=mod;
	};

	ll sum[N], prodSum[N];
	f(i,0,N) sum[i] = prodSum[i] = 0;

	f(i,0,n) {
		if (sum[a[i]])
			add(prodSum[a[i]],sum[a[i]]*a[i]%mod);
		add(sum[a[i]],a[i]);
	}

	f(i,1,N) {
		for (int j = i+i; j < N; j+=i) {
			if (sum[j]) {
				add(prodSum[i],sum[i]*sum[j]%mod);
				add(prodSum[i],prodSum[j]);
			}
			add(sum[i],sum[j]);
		}
	}

	ll ans = 0;

	f(i,1,N) {
		for (int j = i+i; j < N; j+=i) {
			int ff = fac(j/i);
			if (ff == 1) {
				add(prodSum[i],mod-prodSum[j]);	
			}
			else if (ff == 0) {
				add(prodSum[i],prodSum[j]);
			}
		}	
		add(ans,prodSum[i]*modpow(i,mod-2)%mod);
	}

	cout << ans << endl;
	

#ifdef LOCAL
	cout << setprecision(12) << (long double)(clock()-start) / CLOCKS_PER_SEC << endl;
#endif
	return 0;
}




Measured memory_bytes: 22272
#include "iostream"
#include "vector"
#include "cmath"
using namespace std;

int main() {
    int n;
    cin >> n;
    vector <int> a(n);
    for (auto &i: a) {
        cin >> i;
    }
    sort(a.begin(), a.end(), greater<int>());
    long long ans = a[0], ct = 2; // largest two
    float it = 1;
    while (ct != n) {
        ans += a[(int)it];
        it += 0.5;
        ct++;
    }
    cout << ans << endl;
}


Measured memory_bytes: 3648
(let* ((n (read))
       (m (read))
       (lst (loop :repeat m :collect (read)))
       (arr (make-array (+ 2 n) :element-type 'fixnum :initial-element 0)))
  (setf (aref arr 0) 1)
  (loop :for k :from 0 :upto (1- n)
        :do (if (or (not lst) (not (= k (car lst))))
                (progn (setf (aref arr (+ 1 k))
                             (mod (+ (aref arr (+ 1 k)) (aref arr k)) 1000000007))
                       (setf (aref arr (+ 2 k))
                             (mod (+ (aref arr (+ 2 k)) (aref arr k)) 1000000007)))
                (progn (setf lst (cdr lst))
                       (setf (aref arr k) 0))))
  (princ (aref arr n)))

Measured memory_bytes: 59752
import math

N = int(input())
MAX = min(math.ceil(math.sqrt(N)),101)

d = {}
for i in range(10001):
    d[i] = 0

for x in range(1,MAX):
    for y in range(1,MAX):
        for z in range(1,MAX):
            tmp = x**2 + y**2 + z**2 + x*y + y*z + z*x
            if tmp in d.keys():
                d[tmp] += 1
            else:
                d[tmp] = 1

for i in range(1,N+1):
    print(d[i])

Measured memory_bytes: 72564
from collections import deque
d = [(-1,0),(1,0),(0,1),(0,-1)]

def bfs(y,x,c):
    q =  deque()
    q.append((y,x,c))
    ma = 0
    visit[y][x] = 1
    while q:
        y,x,c = q.popleft()
        ma = max(ma,c)
        for dy,dx in d:
            if 0<=y+dy<h and 0<=x+dx<w:
                if area[y+dy][x+dx] =="." and visit[y+dy][x+dx] == 0:
                    q.append((y+dy,x+dx,c+1))
                    visit[y+dy][x+dx] = 1
    return ma

h,w = map(int,input().split())
area = []
for i in range(h):
    area.append(list(input()))
ans = 0
for i in range(h):
    for j in range(w):
        if area[i][j] ==".":
            visit = [[0]*w for i in range(h)]
            ans = max(ans,bfs(i,j,0))
print(ans)


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

int
main() {
  using namespace std;
  const int MAX=200000;
  int R[MAX], n;

  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> R[i];
  }

  int maxv= -2000000000;
  int minv = R[0];

  for (int i=1; i<n; ++i) {
    maxv = max(maxv, R[i]-minv);
    minv = min(minv, R[i]);
  }
  cout << maxv << endl;
  return 0;
}

Measured memory_bytes: 3856
#pragma region

#include "bits/stdc++.h"
using namespace std;
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define _rep3(i, begin, end) for (register int i = (begin); i < (end); i++)
#define _irep3(i, begin, end) for (register int i = (end)-1; i >= (begin); i--)
#define _rep2(i, n) _rep3(i, 0, n)
#define _irep2(i, n) _irep3(i, 0, n)
#define _overload3(_1, _2, _3, name, ...) name
#define rep(...) _overload3(__VA_ARGS__, _rep3, _rep2, )(__VA_ARGS__)
#define irep(...) _overload3(__VA_ARGS__, _irep3, _irep2, )(__VA_ARGS__)
#define out(x) cout << (x) << '\n';
#define debug(x) cerr << #x << " = " << (x) << " (line: " << __LINE__ << ") " << endl;
typedef long long ll;

template <typename T>
istream &operator>>(istream &is, vector<T> &vec) {
  for (auto &v : vec) is >> v;
  return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << "vec[ ";
  rep(i, vec.size()) i == 0 ? os << vec[i] : os << ", " << vec[i];
  os << " ]";
  return os;
}

#pragma endregion

#define MOD 1000000007
#define INF 2147483647

vector<vector<int>> nodes(100000, vector<int>());

bool findRoute(int from, int node, vector<int> &route, int target) {
  if (node == target) {
    route.push_back(node);
    return true;
  }

  rep(i, nodes[node].size()) {
    if (nodes[node][i] != from) {
      if (findRoute(node, nodes[node][i], route, target)) {
        route.push_back(node);
        return true;
      }
    }
  }

  return false;
}

int maxDistance(int from, int node) {
  vector<int> dist;
  rep(i, nodes[node].size()) {
    if (nodes[node][i] != from) {
      dist.push_back(maxDistance(node, nodes[node][i]));
    }
  }
  if (dist.size() == 0) {
    return 0;
  }
  int maxDist = 0;
  rep(i, dist.size()) {
    maxDist = max(maxDist, dist[i]);
  }
  return maxDist + 1;
}

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(16);

  int N, u, v;
  cin >> N >> u >> v;
  u--;
  v--;
  vector<int> A(N - 1), B(N - 1);
  rep(i, N - 1) {
    cin >> A[i] >> B[i];
    A[i]--;
    B[i]--;
    nodes[A[i]].push_back(B[i]);
    nodes[B[i]].push_back(A[i]);
  }

  vector<int> utov;
  findRoute(-1, v, utov, u);

  int dist = utov.size() - 1;
  if (dist % 2 == 0) {
    out(maxDistance(utov[dist / 2], utov[dist / 2 - 1]) + dist / 2);
  } else {
    out(maxDistance(utov[dist / 2 + 1], utov[dist / 2]) + dist / 2);
  }
}


Measured memory_bytes: 13696
#include<bits/stdc++.h>
#define N 2000005
#define LL long long
using namespace std;
const int mo=1e9+7;
int n,X1,X2,X3,X4,X5,X6,Y1,Y2,Y3,Y4,Y5,Y6; LL fc[N],xf[N],ans;
LL fpm(LL x,LL y){ LL s=1; while(y){ if(y&1) s=(s*x)%mo; y>>=1,x=(x*x)%mo;} return s;}
LL C(int n,int m){ return fc[n]*xf[m]%mo*xf[n-m];}
LL F(int X1,int Y1,int X2,int Y2)
{
	return ((C(X2+Y2+2,X2+1)-C(X2+Y1+1,Y1)-C(X1+Y2+1,X1)+C(X1+Y1,X1))%mo+mo)%mo;
}
int main()
{
	int i;
	cin>>X1>>X2>>X3>>X4>>X5>>X6;
	cin>>Y1>>Y2>>Y3>>Y4>>Y5>>Y6;
	fc[0]=xf[0]=1;
	for(i=1;i<N;i++) fc[i]=(fc[i-1]*i)%mo;
	xf[N-1]=fpm(fc[N-1],mo-2);
	for(i=N-2;i>=0;i--) xf[i]=(xf[i+1]*(i+1))%mo;
	for(i=X3;i<=X4;i++)
		(ans+=F(i-X2,Y3-1-Y2,i-X1,Y3-1-Y1)*F(X5-i,Y5-Y3,X6-i,Y6-Y3)%mo*(mo-i-Y3))%=mo;
	for(i=Y3;i<=Y4;i++)
		(ans+=F(X3-1-X2,i-Y2,X3-1-X1,i-Y1)*F(X5-X3,Y5-i,X6-X3,Y6-i)%mo*(mo-X3-i))%=mo;
	for(i=X3;i<=X4;i++)
		(ans+=F(i-X2,Y4-Y2,i-X1,Y4-Y1)*F(X5-i,Y5-1-Y4,X6-i,Y6-1-Y4)%mo*(i+Y4+1))%=mo;
	for(i=Y3;i<=Y4;i++)
		(ans+=F(X4-X2,i-Y2,X4-X1,i-Y1)*F(X5-1-X4,Y5-i,X6-1-X4,Y6-i)%mo*(X4+i+1))%=mo;
	cout<<ans;
	return 0;
}


Measured memory_bytes: 31488
N=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(N-2):
    if a[i] == a[i+1]:
        if min(a[i],a[i+2]) != 0:
            a[i+1]=(max(a[i],a[i+2])+1)%10001
        else:
            if max(a[i],a[i+2]) <= 1:
                a[i+1] = 2
            else:
                a[i+1] = 1
        ans+=1
if a[N-2] == a[N-1]:
    ans+=1
print(ans)



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

int main(){
  int h,w,count=0;
  string s;
  cin>>h>>w;
  vector<string> vec(h+2,"");
  for(int i=0;i<w+2;i++){
    vec.at(0)+=".";
    vec.at(h+1)+=".";
  }
  for(int i=1;i<h+1;i++){
    cin>>vec.at(i);
    vec.at(i)='.'+vec.at(i)+'.';
  }
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      count=0;
      if((vec.at(i)).at(j)=='.'){
          for(int k=-1;k<2;k++){
            for(int l=-1;l<2;l++){
              if((vec.at(k+i)).at(l+j)=='#'){
                count+=1;
              }
            }
          }
        (vec.at(i)).at(j)=count+'0';
      }
    }
  }
  for(int i=1;i<h+1;i++){
    for(int j=1;j<w+1;j++){
      cout<<(vec.at(i)).at(j);
    }
    cout<<endl;
  }
}
          
   


Measured memory_bytes: 256
#include<bits/stdc++.h>
#include<iostream>
#include<string>
#include<cmath>
#include<cstdio>
#include<cctype>
#include<cstring>
#include<iomanip>
#include<cstdlib>
#include<ctime>
#include<set>
#include<map>
#include<utility>
#include<queue>
#include<vector>
#include<stack>
#include<sstream>
#include<algorithm>
/************************************************/
#define rep(i,n) for(int i=0;i<n;i++)
#define m_p make_pair
#define pb push_back
#define fr first
#define se second
#define forn(i,a,n) for(int i=a;i<n;i++)
#define foreach(i,c) for(__typeof(c.begin())i=(c.begin());i!=(c).end();i++)
#define pii pair<int,int>
#define vi vector<int>
#define ll long long
#define sz(s) s.size()
#define all(s) s.begin(),s.end()
#define zero(x) memset(x,0,sizeof(x))
#define vii vector<pair<int,int> >
#define mpis map<int,string>
#define mpii map<int,int>
#define mpsi map<string,int>
#define re return
#define mod 1000000007
/************************************************/
using namespace std;

long long get(){
	char c=getchar();
	long long x=0LL;
	while(c<'0'||c>'9')
	c=getchar();
	while(c>='0'&&c<='9'){
		x*=10LL;
		x+=(c-'0');
		c=getchar();
	}
	return x;
}
int n;
int main(){
	ios::sync_with_stdio(0);
	cin>>n;
	cout<<(n+1)/2;
	re 0;
}


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

int MOD = 1e9 + 7;
long long pow2(long long x, long long n, int mod=0) {
  if (n == 0) return 1;
  if (mod) {
    if (n & 1) return x * pow2(x, n - 1, mod) % mod;
    long long y = pow2(x, n / 2, mod);
    return y * y % mod;
  } else {
    if (n & 1) return x * pow2(x, n - 1);
    long long y = pow2(x, n / 2);
    return y * y;
  }
}

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

  int n;
  cin >> n;
  vector<int> c(n);
  for (int i = 0; i < n; i++) {
    int a;
    cin >> a;
    c[a]++;
  }

  int ans = 0;
  if (n % 2 == 0 || c[0] == 1) {
    bool flag = true;
    for (int i = 1 + (n & 1); i < n; i += 2) {
      if (c[i] != 2) {
        flag = false;
        break;
      }
    }
    if (flag) ans = pow2(2, n / 2, MOD);
  }
  cout << ans << '\n';
  return 0;
}

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

int main(void){

   int N,ans = 1;
   cin >> N;
   int data[N];
   
   for(int i=0;i<N;i++) cin >> data[i];

   for(int i=1;i<N;i++){
       int sum = 0;
       for(int j=0;j<i;j++){
           if(data[j] <= data[i]) sum++;
           else break;
       }
       
       if(sum == i) ans++;
   }
   
   cout << ans << endl;
}

Measured memory_bytes: 3640
#define  _CRT_SECURE_NO_WARNINGS
#pragma comment (linker, "/STACK:526000000")

#include "bits/stdc++.h"

using namespace std;
typedef string::const_iterator State;
#define eps 1e-11L
#define MAX_MOD 1000000007LL
#define GYAKU 500000004LL

#define MOD 998244353LL
#define seg_size 262144*2LL
#define pb push_back
#define mp make_pair
typedef long long ll;
#define REP(a,b) for(long long (a) = 0;(a) < (b);++(a))
#define ALL(x) (x).begin(),(x).end()

unsigned long xor128() {
	static unsigned long x = 123456789, y = 362436069, z = 521288629, w = time(NULL);
	unsigned long t = (x ^ (x << 11));
	x = y; y = z; z = w;
	return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8)));
}

void init() {
	iostream::sync_with_stdio(false);
	cout << fixed << setprecision(20);
}

#define int ll
int powing(int a, int b) {
	int ans = 1;
	while (b) {
		if (b % 2) {
			ans *= a;
			ans %= MAX_MOD;
		}
		b /= 2;
		a *= a;
		a %= MAX_MOD;
	}
	return ans;
}
int inv(int now) {
	return powing(now, MAX_MOD - 2LL);
}
ll mae[500000];
ll gyaku[500000];
ll combination(int a, int b) {
	ll ans = mae[a];
	ans *= gyaku[b];
	ans %= MAX_MOD;
	ans *= gyaku[a - b];
	ans %= MAX_MOD;
	return ans;
}
void solve() {
	int n, k;
	cin >> n >> k;
	mae[0] = 1;
	gyaku[0] = 1;
	for (int i = 1; i < 500000; ++i) {
		mae[i] = mae[i - 1] * i;
		mae[i] %= MAX_MOD;
		gyaku[i] = inv(mae[i]);
	}
	int ans = 0;
	for (int q = 0; q <= k&&q <= n-1; ++q) {
		ll hoge = combination(n, q);
		hoge *= combination(n - 1, q);
		hoge %= MAX_MOD;
		ans += hoge;
		ans %= MAX_MOD;
	}
	cout << ans << endl;
}
#undef int
int main() {
	init();
	solve();
}

Measured memory_bytes: 8064
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double EPS = 1e-9;
typedef vector<int> vint;
typedef pair<int, int> pint;
#define rep(i, n) REP(i, 0, n)
#define ALL(v) v.begin() , v.end()
#define REP(i, x, n) for(int i = x; i < n; i++)

int main(){
    int n,ans=0;
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        ans = __gcd(ans, x);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <stdio.h>
#include <string.h>
#include <iostream>


int main(){
  char name[10];
  int  N, T[100], M, P[100], X[100];

  std::cin >> N;
  //std::cin.ignore();                                                                               
  for (int i = 0; i < N; i++) {
    std::cin >> T[i];
  }
  std::cin >> M;
  for (int i = 0; i < M; i++) {
    std::cin >> P[i] >> X[i];
  }

  int sum=0;
  for(int i = 0; i < N; i++){
    sum += T[i];
  }
  //std::cout<< X[0]<<" "<<X[1]<<" "<<X[2] <<" "<<X[3] <<std::endl;                                  
  for(int i=0; i<M; i++){
    //std::cout<< sum<<" "<<T[P[i]-1]<<" "<<X[i] <<" "<<P[i] <<std::endl;                            
    std::cout<< sum-T[P[i]-1]+X[i] <<std::endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
#define pi 3.14159265358979323846264
#define pii pair <int, int>
#define pb push_back
#define mp make_pair
#define vi vector <int>
#define vl vector <long long>
#define vpii vector <pair <int, int> >
#define ll long long
#define fi first
#define se second
int n, a[15];
int main() {
    scanf("%d", &n);
    for (int i=0;i<n;i++) scanf("%d", &a[i]);
    int ans = 1, k = 1;
    for (int i=0;i<n;i++) ans *= 3;
    for (int i=0;i<n;i++) {
        if (a[i]%2==0) k *= 2;
    }
    printf("%d\n", ans-k);
    return 0;
}

Measured memory_bytes: 256
/*#include <boost/multiprecision/cpp_dec_float.hpp>
#include <boost/multiprecision/cpp_int.hpp>

#include <boost/rational.hpp>
*/
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
using ll = long long;
using ld = long double;
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define rep3(i, n) for (ll i = 1; i < (ll)(n+1); i++)
#define rep4(i, s, n) for (ll i = (s); i < (ll)(n+1); i++)
#define repr(i,n) for (ll i = (n-1); i>=0;i--)
#define repr3(i,n) for(ll i = (n);i>0;i--)
#define repr4(i,s,n) for(ll i = (n);i>=(s);i--)
#define stlen(s) ll s.size()-1
#define all(v) v.begin(), v.end()
#define allr(v) v.rbegin(), v.rend()
#define cout(n) cout<<std::fixed<<std::setprecision(n)
using Graph = vector<vector<int>>;
using Graphw = vector<vector<pair<ll,ll>>>;
#define INF1  INT_MAX;
#define INF2  LLONG_MAX;
#define PI  3.14159265358979323846;
#define MOD 1000000007;
/*
namespace mp = boost::multiprecision;
// 任意長整数型
using Bint = mp::cpp_int;
// 仮数部長が32の浮動小数点数型
using Real32 = mp::number<mp::cpp_dec_float<32>>;
// 仮数部長が1024の浮動小数点数型
using Real1024 = mp::number<mp::cpp_dec_float<1024>>;
// 有理数型
using Rat = boost::rational<Bint>;
*/
const int mod = 1000000007;
struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N) : par(N) { //最初は全てが根であるとして初期化
        for(int i = 0; i < N; i++) par[i] = i;
    }

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] == x) return x;
        return par[x] = root(par[x]);
    }

    void unite(int x, int y) { // xとyの木を併合
        int rx = root(x); //xの根をrx
        int ry = root(y); //yの根をry
        if (rx == ry) return; //xとyの根が同じ(=同じ木にある)時はそのまま
        par[rx] = ry; //xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
};

int main(){
int N,M;
cin>>N>>M;
pair<int,int> path[M];
rep(i,M){
  int a,b;
  cin>>a>>b;
  path[i]=make_pair(a,b);
}
int count=0;
rep(i,M){
  UnionFind U(N+1);
  rep(j,M){
    if(i==j)continue;
    U.unite(path[j].first,path[j].second);
  }
  int root=U.root(1);
  rep4(j,2,N){
    if(U.root(j)!=root){
      count++;
      break;
    }
  }
}
cout<<count<<endl;
return 0;
}

Measured memory_bytes: 3616
n, q = [int(x) for x in input().split(' ')]
s = input()
lr = [[int(x) for x in input().split(' ')] for _ in range(q)]


indexes = [0] * n

for i in range(1, len(s)):
    if s[i-1] == 'A' and s[i] == 'C':
        indexes[i] = indexes[i-1]+1
    else:
        indexes[i] = indexes[i-1]

for l, r in lr:
    print(indexes[r-1]-indexes[l-1])


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

#define maxn 100000
#define maxm 200000

int n,m;
int a[maxm+5];
int c[maxm+5];

void readin(){
	scanf("%d",&n);
	m=n*2-1;
	for(int i=1;i<=m;i++) {
		scanf("%d",&a[i]);
	}
}

void Turn(int x) {
	for(int i=1;i<=m;i++){
		c[i]=(a[i]>=x);
	}
}

bool judge(int x){
	Turn(x);
	int p1=0,p2=m+1;
	for(int i=n;i>=2;i--){
		if(c[i]==c[i-1]){
			p1=i;
			break;
		}
	}
	for(int i=n;i<m;i++) {
		if(c[i]==c[i+1]) {
			p2=i;
			break;
		}
	}
	if(p1==0&&p2==m+1) return c[1];
	if(n-p1>p2-n) return c[p2];
	else return c[p1]; 
}

int binsearch() {
	int l=0,r=m;
	while(l+1<r) {
		int mid=l+(r-l)/2;
		if(judge(mid)) l=mid;
		else r=mid;
	}
	if(judge(l+1)) return l+1;
	if(!judge(l)) return l-1;
	else return l;
}

int main(){
	readin();
	int ans=binsearch();
	printf("%d",ans);
	return 0;
}

Measured memory_bytes: 1792
#include <bits/stdc++.h>
using namespace std;
#define xfor(i, a, b) for (int i = a; i < b; i++)
#define ifor(i, a, b) for (int i = a; i <= b; i++)
#define rxfor(i, b, a) for (int i = b; i > a; i--)
#define rifor(i, b, a) for (int i = b; i >= a; i--)
#define foreach(v, c)                                                          \
  for (typeof((c).begin()) v = (c).begin(); v != (c).end(); ++v)
#define all(a) a.begin(), a.end()
#define in(a, b) ((b).find(a) != (b).end())
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<string> VS;
typedef vector<PII> VII;
typedef vector<VI> VVI;
typedef map<int, int> MPII;
typedef set<int> SETI;
const double pi = acos(-1.0);
int main() {
  int R;
  cin >> R;
  cout.precision(10);
  cout << fixed;
  cout << 2 * pi * R << endl;
}


Measured memory_bytes: 3772
#define _USE_MATH_DEFINES
#include <algorithm>
#include <cstdio>
#include <functional>
#include <iostream>
#include <cstring>
#include <climits>
#include <cmath>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <time.h>
#include <vector>
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> i_i;
typedef pair<ll, int> ll_i;
typedef pair<double, int> d_i;
typedef pair<ll, ll> ll_ll;
typedef pair<double, double> d_d;
struct edge { int u, v; ll w; };
 
int MOD = 1000000007;

int main() {
	for (;;) {
		int n, x; cin >> n >> x;
		if (n == 0 && x == 0) break;
		int cnt = 0;
		for (int i = 1; i <= n; i++)
			for (int j = i + 1; j <= n; j++)
				for (int k = j + 1; k <= n; k++)
					if (i + j + k == x) cnt++;
		cout << cnt << endl;
	}
}

Measured memory_bytes: 1160