akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
#define int unsigned
#define fastio ios::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define pb push_back
#define ll long long
#define fi first
#define se second
#define maxn 5001
 
const int mod = 1e9+7 ;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
 
ll dp[maxn][maxn];
 
signed main()
{
	fastio;
	int n;	cin >> n;
	string str;	cin >> str;
	int m = str.length();
	if(n == m) {
		cout << 1; return 0;
	}
	dp[0][0] = 1;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 0; j <= i; j++)
		{
			if (j == 0 && i == 1)
			{
				dp[i][j] = 1;
			}
			else if (j == 0 && i > 1)
			{
				dp[i][j] = (dp[i-1][j] + (2*dp[i-1][1])%mod) % mod;
			}
			else
			{
				dp[i][j] = ((2*dp[i-1][j+1])%mod + dp[i-1][j-1]) % mod;
			}
		}
	}
	cout << dp[n][m];
}

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

using ll = long long;

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rrep(i, n) for (int i = 1; i <= (n); ++i)
#define drep(i, n) for (int i = (n)-1; i >= 0; --i)
#define ddrep(i, n) for (int i = n; i > 0; --i)
#define srep(i, s, t) for (int i = s; i < t; ++i)
#define ssrep(i, s, t) for (int i = s; i <= t; ++i)

#define rng(a) a.begin(), a.end()
#define pb push_back
#define eb emplace_back
#define fi first
#define se second

#define chmax(x, y) (x = max(x, y))
#define chmin(x, y) (x = min(x, y))

using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using ld = long double;

template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}

template <class T> ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "{";
  rep(i, (int)v.size()) {
    if (i)
      os << ",";
    os << v[i];
  }
  os << "}";
  return os;
}

template <typename T, size_t S> void printArray(const T (&array)[S]) {
  for (auto val : array)
    std::cout << val << ", ";
  std::cout << "\n";
}

const int mod = 1e9 + 7;
const int inf = 1e9 + 5;

struct mint {
  ll x;
  mint(ll x=0) : x(x%mod) {}
  mint& operator+=(const mint a) {
    if ((x += a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator-=(const mint a) {
    if ((x -= a.x) >= mod) x -= mod;
    return *this;
  }
  mint& operator*=(const mint a) {
    (x *= a.x) %= mod;
    return *this;
  }
  mint operator+(const mint a) {
    mint res(*this);
    return res+=a;
  }
  mint operator-(const mint a) {
    mint res(*this);
    return res-=a;
  }
  mint operator*(const mint a) {
    mint res(*this);
    return res*=a;
  }
};

mint c[4005][4005];
void init() {
  c[0][0] = 1;
  rep(i, 4001) rep(j, i+1) {
    c[i+1][j] += c[i][j];
    c[i+1][j+1] += c[i][j];
  }
}

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

  int n, k; std::cin >> n >> k;
  init();
  auto comb = [&](int n, int k) -> mint {
    return c[n][k];
  };
  auto ff = [&](int n, int k) -> mint {
    return comb(n+k-1, k-1);
  };
  auto f = [&](int n, int k) -> mint {
    if (n == 0 && k == 0) return 1;
    if (n < k) return 0;
    if (k < 1) return 0;
    return ff(n-k, k);
  };
  rrep(i, k) {
    mint blue = f(k, i);
    mint red = 0;
    {
      red += f(n-k, i-1);
      red += f(n-k, i);
      red += f(n-k, i);
      red += f(n-k, i+1);
    }
    mint ans = blue * red;
    printf("%lld\n", ans.x);
  }
}


Measured memory_bytes: 125568
n = int(input())
H = list(map(int, input().split(' ')))

for i in range(n):
    node = i+1
    key = H[i]
    parent = H[int(node/2)-1] if node != 1 else None
    left = H[node*2-1] if node*2 <= n else None
    right = H[node*2] if node*2+1 <= n else None
    print('node %d: key = %d, '%(node, key), end='')
    if parent != None: print('parent key = %d, '%parent, end='')
    if left != None: print('left key = %d, '%left, end='')
    if right != None: print('right key = %d, '%right, end='')
    print('')


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

int N, M;

int main() {
    cin >> N >> M;
    int l,r;
    int maxl = -1 ,minr = N;
    for (int i = 0; i < M; i++) {
        cin >> l >> r;
        if (l > maxl) maxl = l;
        if (r < minr) minr = r;
    }
    if (minr >= maxl) {
        cout << minr - maxl + 1 << endl;
    } else {
        cout << 0 << endl;
    }
}

Measured memory_bytes: 256
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <algorithm>
#include <math.h>
#include <cmath>
#include <deque>
using namespace std;


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

    deque<char> dq;
    for(int i = 0; i <s.size(); i++){
        if(s[i] == 'A'){
            dq.push_back('A');
        } else if(s[i] == 'B'){
            dq.push_back('B');
        } else {
            if(!(dq.empty()) && dq.back() == 'B'){
                dq.pop_back();
                dq.push_back('D');
            } else {
                dq.push_back('C');
            }
        }
    }
    int n = dq.size();
    
    int cntA = 0;
    long long ans = 0;
    while(!(dq.empty())){
        if(dq.front() == 'A'){
            cntA++;
            dq.pop_front();
        } else if(dq.front() == 'D'){
            ans += cntA;
            dq.pop_front();
        } else {
            cntA = 0;
            dq.pop_front();
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 644
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <complex>
#include <list>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <utility>
#include <functional>
#include <iterator>

using namespace std;

#define dump(n) cerr<<"# "<<#n<<"="<<(n)<<endl
#define repi(i,a,b) for(int i=int(a);i<int(b);i++)
#define peri(i,a,b) for(int i=int(b);i-->int(a);)
#define rep(i,n) repi(i,0,n)
#define per(i,n) peri(i,0,n)
#define iter(c) __typeof__((c).begin())
#define foreach(i,c) for(iter(c) i=(c).begin();i!=(c).end();++i)
#define all(c) (c).begin(),(c).end()
#define mp make_pair

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<double> vd;
typedef vector<vd> vvd;
typedef vector<string> vs;
typedef pair<int,int> pii;

struct Rect{
	int x,y,w,h;
	Rect(){}
	Rect(int x,int y,int w,int h):x(x),y(y),w(w),h(h){}
};

int main()
{
	for(int n,w,h;cin>>n>>w>>h,n|w|h;){
		list<Rect> rs;
		rs.push_back(Rect(0,0,w,h));
		rep(i,n){
			int p,s; cin>>p>>s;
			
			iter(rs) it=rs.begin(); advance(it,p-1);
			int len=(it->w+it->h)*2;
			Rect r1,r2;
			if((s%=len)<it->w){
				r1=Rect(it->x,it->y,s,it->h);
				r2=Rect(it->x+s,it->y,it->w-s,it->h);
			}
			else if((s-=it->w)<it->h){
				r1=Rect(it->x,it->y,it->w,s);
				r2=Rect(it->x,it->y+s,it->w,it->h-s);
			}
			else if((s-=it->h)<it->w){
				r1=Rect(it->x,it->y,it->w-s,it->h);
				r2=Rect(it->x+it->w-s,it->y,s,it->h);
			}
			else if((s-=it->w)<it->h){
				r1=Rect(it->x,it->y,it->w,it->h-s);
				r2=Rect(it->x,it->y+it->h-s,it->w,s);
			}
			
			if(r1.w*r1.h>r2.w*r2.h)
				swap(r1,r2);
			rs.push_back(r1);
			rs.push_back(r2);
			rs.erase(it);
		}
		
		vi as;
		foreach(i,rs)
			as.push_back(i->w*i->h);
		sort(all(as));
		rep(i,as.size())
			printf("%d%c",as[i],i==as.size()-1?'\n':' ');
	}
	
	return 0;
}

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

#define mod 1000000007
#define ll long long

ll bow(ll x, ll y) {
  ll res = 1;
  for (ll i = 1; i <= y; ++i) {
    res = res * x % mod;
  }
  return res;
}

void solve() {
  ll x;
  cin >> x;
  cout << 1 - x << endl;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  solve();
  return 0;
}

Measured memory_bytes: 3640
import math

n = int(input())
d = [[0] * n for _ in range(n)]
p = []
for i in range(n):
    p.append(tuple(map(int, input().split())))

s = 0
for i in range(n):
    xi, yi = p[i]
    for j in range(i+1, n):
        xj, yj = p[j]
        s += math.sqrt((xi - xj) ** 2 + (yi - yj) ** 2)
s = s * 2 / n
print(s)

Measured memory_bytes: 62288
#include <bits/stdc++.h>
using namespace std;
// #include <ext/pb_ds/assoc_container.hpp> 
// #include <ext/pb_ds/tree_policy.hpp> 
// using namespace __gnu_pbds;   
#define ll long long
#define ull unsigned long long
// #define ordered_set tree<pair<ll, ll>, null_type, less<pair<ll, ll>>, rb_tree_tag, tree_order_statistics_node_update> 
ll mod=1e9+7;
#define PI 3.1415926535897932385
#define inf 9e18
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
string char_to_str(char c){string tem(1,c);return tem;}
typedef pair<long long, long long> ii;
#define S second
#define F first
ll max(ll a,ll b){if(a>b){return a;}return b;}
ll min(ll a,ll b){if(a<b){return a;}return b;}
#define MAXN 200005
// Comment this out for interactice problem
// #define endl '\n'
// string to integer stoi() Remember: it takes string not character
// string to long long stoll()
// string.substr(position,length);
// integer to string to_string();
 
// To compile--> g++ -std=c++0x -o output one.cpp
// To run--> ./output

int main()
{ 
    fastio;
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);

    ll n;
    cin>>n;
    ll a[n+1];
    ll sum[n+1];
    sum[0]=0;
    for (int i = 1; i < n+1; ++i)
    {
        sum[i]=0;
        cin>>a[i];
    }
    
    for (int i = 1; i < n+1; ++i)
    {
        sum[i]=(sum[i-1]+a[i])%mod;
    }

    ll ans=0;

    for (int i = 1; i < n; ++i)
    {
        ans = (ans+(a[i]*(sum[n]-sum[i]+mod)%mod)%mod)%mod;
    }

    cout<<ans;

    return 0;
}

Measured memory_bytes: 6728
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<iomanip>
using namespace std;

int main()
{
	int n, k;
	int ans,tmp;
	cin >> n >> k;
	ans = 0;
	for (int i = 0;i < n;i++)
	{
		cin >> tmp;
		if (tmp >= k)
			ans++;
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 256
n=int(input())
a=[int(i) for i in input().split()]

for i in range(n):
    a[i]-=i+1

a.sort()
if n % 2 == 0:
    print(sum(a[int(n / 2):]) - sum(a[:int(n / 2)]))
else:
    print(sum(a[int((n + 1) / 2):]) - sum(a[:int((n - 1) / 2)]))


Measured memory_bytes: 26360
use std::str::FromStr;
use std::fmt::Debug;
use std::cmp;

fn read_line<T>() -> Vec<T>
where T: FromStr, <T as FromStr>::Err : Debug {
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    s.trim().split_whitespace().map(|c| T::from_str(c).unwrap()).collect()
}

fn main() {
    let _vec: Vec<usize> = read_line();
    let hs: Vec<i32> = read_line();

    let mut dp: Vec<i32> = Vec::new();
    for _ in 0..hs.len() { dp.push(0); }
    dp[0] = 0;
    dp[1] = (hs[0] - hs[1]).abs();

    for i in 2..hs.len() {
        dp[i] = cmp::min(
                    dp[i - 2] + (hs[i] - hs[i - 2]).abs(),
                    dp[i - 1] + (hs[i] - hs[i - 1]).abs(),
                );
    }
    println!("{}", dp.last().unwrap());
}


Measured memory_bytes: 4352
package main

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

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	x := NextIntArray()

	distance := 0
	for _, val := range x {
		if val <= k-val {
			distance += val
		} else {
			distance += k - val
		}
	}
	fmt.Println(distance * 2)
}

// reader

var size = 1000000
var rdr = bufio.NewReaderSize(os.Stdin, size)

func ReadLine() string {
	buf := make([]byte, 0, size)
	for {
		line, isPrefix, err := rdr.ReadLine()
		if err != nil {
			panic(err)
		}
		buf = append(buf, line...)
		if !isPrefix {
			break
		}
	}
	return string(buf)
}

func NextStrArray() []string {
	s := ReadLine()
	return strings.Split(s, " ")
}

func NextIntArray() []int {
	a := NextStrArray()
	na := make([]int, 0)

	for _, v := range a {
		if n, e := strconv.Atoi(v); e == nil {
			na = append(na, n)
		}
	}

	return na
}


Measured memory_bytes: 768
N, M = map(int, input().split())
nodes = [[] for i in range(N)]

for i in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    nodes[u].append(v)

s, t = map(int, input().split())
s -= 1
t -= 1

num = s
step = 0
q = [[num, step]]
check = [[False for i in range(N)] for j in range(3)]
ok = False
while len(q) > 0:
    num, step = q.pop(0)
    tmp = step % 3
    if tmp == 0 and num == t:
        print(step//3)
        ok = True
        break
    for next in nodes[num]:
        if not check[tmp][next]:
            check[tmp][next] = True
            q.append([next, step+1])
if not ok:
    print(-1)


Measured memory_bytes: 20388
import numpy as np

N,M = [int(i) for i in input().split(" ")]
H = [int(i) for i in input().split(" ")]
mh = np.zeros([N])
for i in range(M):
    a,b = [int(i)-1 for i in input().split(" ")]
    mh[a] = max(mh[a],H[b])
    mh[b] = max(mh[b],H[a])

ans = 0
for i in range(N):
    if mh[i] < H[i]:
        ans += 1

print(ans)

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

using namespace std;

typedef long long ll;

const ll MOD = 1000000007;

vector<ll> sil(3000000);

ll Pot(ll p, ll w)
{
    if (w == 0)
        return 1;
    if (w % 2 == 0)
    {
        ll pol = Pot(p, w / 2);
        return pol * pol % MOD;
    }
    return Pot(p, w - 1) * p % MOD;
}

ll Inv(ll x)
{
    return Pot(x, MOD - 2);
}

ll C(ll n, ll k)
{
    return sil[n] * (Inv(sil[k]) * Inv(sil[n - k]) % MOD) % MOD;
}

int main()
{
    ios_base::sync_with_stdio(0);
    sil[0] = 1;
    for (ll i = 1; i < 3000000; ++i)
        sil[i] = (sil[i - 1] * i) % MOD;
    ll k;
    string s;
    cin >> k >> s;
    ll n = s.size();
    ll odp = 0;
    for (ll i = n; i <= n + k; ++i)
    {
        ll il = (C(i - 1, n - 1) * Pot(25, i - n)) % MOD;
        il = (il * Pot(26, n + k - i)) % MOD;
        odp = (odp + il) % MOD;
    }
    cout << odp;
    return 0;
}


Measured memory_bytes: 27768
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define UNIQUE(v) v.erase(unique(all(v)), v.end());
#define ZIP(v) sort(all(v)),UNIQUE(v)
#define repi(i,m,n) for(int i = m;i < n;i++)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rep(i,n) repi(i,0,n)
#define rrep(i,n) repi(i,1,n+1)
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(), v.rend()
#define pb(x) push_back(x)
#define fi first
#define se second
typedef pair<int,int> P;
typedef pair<int, P> PP;
typedef vector<int> vi;
const int inf = 1e9+7;
const int INF = 1e18+7;
int mod = 1e9+7;

int a[100];
signed main(){
	int n;
	scanf("%lld", &n);
	rep(i,n)scanf("%lld", &a[i]);
	
	int s = 0, ans = inf;
	rep(i,n)s += a[i];
	s /= n;
	repi(j,-1,2){
		int sum = 0;
		rep(i,n)sum += (a[i]-s+j)*(a[i]-s+j);
		chmin(ans, sum);
	}
	printf("%lld\n", ans);
	return 0;
}




Measured memory_bytes: 256
#include<iostream>
#include<algorithm>
using namespace std;
int n;
long dp[2<<17][5];
main()
{
	cin>>n;
	for(int i=0;i++<n+1;)
	{
		long a=0;cin>>a;
		long now=9e18;
		for(int j=0;j<5;j++)
		{
			now=min(now,dp[i-1][j]);
			dp[i][j]=now+(j-2?j%2?a?a%2:2:a:1-a%2);
		}
	}
	cout<<dp[n+1][4]<<endl;
}


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

int n,k;
int arr[107];
ll dp[107][100007];

int rec( int i, int x )
{
    if( x>k )
        return 0;

    if( i>n )
    {
        if(x==k)
            return 1;
        return 0;
    }
    int ret= 0;

    for( int j=0; j<=arr[i]; j++ )
        ret= ( ret+rec( i+1, x+j ) )%mod;

    return ret;
}

int main()
{
    cin>>n>>k;

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

    vector<ll>sum;
    for( int i=0; i<k; i++ )
        sum.push_back(0);
    sum.push_back(1);


    for( int peep=n; peep>=1; peep-- )
    {
        vector<ll>now;

        for( int total=0; total<=k; total++ )
        {
            if(total)
                dp[peep][total]= (sum[ min(k,total+arr[peep]) ]-sum[total-1]+mod)%mod;
            else
                dp[peep][total]= sum[ min(k,total+arr[peep]) ];

            if(total)
                now.push_back( (now.back()+dp[peep][total])%mod );
            else
                now.push_back( dp[peep][total] );
     }

        sum.swap(now);
    }

    cout<< dp[1][0] <<endl;
}


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

int n, m, q;
int a[50];
int b[50];
int c[50];
int d[50];

int rec(vector<int>& v) {
  if (v.size() == n) {
    int sum = 0;
    for (int i = 0; i < q; ++i) {
      if (v[b[i]] - v[a[i]] == c[i]) {
        sum += d[i];
      }
    }
    return sum;
  }
  
  int mn = v.empty() ? 1 : v.back();
  int ans = 0;
  for (int j = mn; j <= m; ++j) {
    v.push_back(j);
    ans = max(ans, rec(v));
    v.pop_back();
  }
  return ans;
}

int main() {
  cin >> n >> m >> q;
  for (int i = 0; i < q; ++i) {
    cin >> a[i] >> b[i] >> c[i] >> d[i];
    --a[i]; --b[i];
  }
  
  vector<int> v;
  cout << rec(v) << endl;
}

Measured memory_bytes: 3616
package main

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

func getScanner(fp *os.File) *bufio.Scanner {
	scanner := bufio.NewScanner(fp)
	scanner.Split(bufio.ScanWords)
	scanner.Buffer(make([]byte, 500001), 500000)
	return scanner
}

func getNextString(scanner *bufio.Scanner) string {
	scanner.Scan()
	return scanner.Text()
}

func getNextInt(scanner *bufio.Scanner) int {
	i, _ := strconv.Atoi(getNextString(scanner))
	return i
}

func getNextInt64(scanner *bufio.Scanner) int64 {
	i, _ := strconv.ParseInt(getNextString(scanner), 10, 64)
	return i
}

func getNextUint64(scanner *bufio.Scanner) uint64 {
	i, _ := strconv.ParseUint(getNextString(scanner), 10, 64)
	return i
}

func getNextFloat64(scanner *bufio.Scanner) float64 {
	i, _ := strconv.ParseFloat(getNextString(scanner), 64)
	return i
}

func main() {
	fp := os.Stdin
	wfp := os.Stdout

	if os.Getenv("MASPY") == "ますピ" {
		fp, _ = os.Open(os.Getenv("BEET_THE_HARMONY_OF_PERFECT"))
	}
	if os.Getenv("MASPYPY") == "ますピッピ" {
		wfp, _ = os.Create(os.Getenv("NGTKANA_IS_GENIUS10"))
	}

	scanner := getScanner(fp)
	writer := bufio.NewWriter(wfp)

	n := getNextInt(scanner)
	counter := make([]int, n)
	for i := 0; i < n; i++ {
		a := getNextInt(scanner) - 1
		counter[a]++
	}
	sort.Ints(counter)
	ss := make([]int, n+1)
	for i := 0; i < n; i++ {
		ss[i+1] = ss[i] + counter[i]
	}

	ans := n
	r := n
	for k := 1; k <= n; k++ {
		for ans > 0 {
			for r > 0 {
				if counter[r-1] < ans {
					break
				}
				r--
			}
			if (n-r)*ans+ss[r] < ans*k {
				ans--
				continue
			}
			break
		}
		fmt.Println(ans)
	}
	writer.Flush()
}


Measured memory_bytes: 8448
#define DEBUG(...) cerr << __VA_ARGS__ << endl;

#ifndef CDEBUG
#undef DEBUG
#define DEBUG(...) ((void)0);
#define NDEBUG
#endif

#define ran(i, a, b) for (auto i = (a); i < (b); i++)

#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
using namespace std;
const int mod = 1e9 + 7;
#ifndef M_PI
const double M_PI = acos(-1.0);
#endif
int h[2], m[2], k;

int main() {
  cin>>h[0]>>m[0]>>h[1]>>m[1]>>k;
  cout<<(60*(h[1]-h[0])+m[1]-m[0]-k)<<endl;
  return 0;
}


Measured memory_bytes: 3632
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int h = sc.nextInt();
        int m = sc.nextInt();
        double hm = h + (m / 60.0);
        double degH = h * 30.0 + m / 60.0 * 30.0;
        double degM = m / 60.0 * 360.0;
        double deg = Math.abs(degH - degM);
        double res = Math.pow((a*a) + (b*b) - 2 * a * b * Math.cos(Math.toRadians(deg)),0.5);
        System.out.println(res);
    }
}


Measured memory_bytes: 35964
MOD = 1_000_000_007

def memoize(name)
  original = "__original_#{name}__"
  self.class.class_eval {
    alias_method(original, name)
    private(original)
    cache = {}
    define_method(name){|*args|
      cache[args] ||= send(original, *args)
    }
  }
end 

def f(n, k)
  return 1 if n == 0
  return 0 if n < 0
  return 0 if k == 0
  (f(n, k-1) + f(n-k, k)) % MOD
end

memoize :f

n, k = gets.split.map(&:to_i)
p f(n - k, k)


Measured memory_bytes: 27176
/*
this code is contributed by shrey patel
*/
#include <bits/stdc++.h>
using namespace std;
#define lld long long int
#define M 1000000007
#define fors(i,n) for(int i=0;i<n;i++)
#define fore(i,a,b) for(int i=a,i<=b;i++)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define vv vector<int>
#define end "\n"
#define test(i) cout<<i<<endl
#define t int t=1; fors(i,t)

int main(){
  fastio;
  t{
    string s;
    cin>>s;
    for (int i = 0; i < s.length(); i++) {
 if (i % 2 == 0) {
 if (s[i] == 'L') {
   puts("No");
 return 0;
 }
 } else {
 if (s[i] == 'R') {
 puts("No");
 return 0;
 }
 }
 }
 puts("Yes");
 return 0;
  }
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define watch(x) cout << (#x) << " is " << (x) << endl
#define eps 1e-9

typedef long long ll;

using namespace std;

const ll inf = 1e18;
const ll mod = 1e9+7;
const int N = 1e5+5;

int main()

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

    char x, y;

    cin >> x >> y;

    if (x > y) cout << ">";
    else if (x < y) cout << "<";
    else cout << "=";

    return 0;
}


Measured memory_bytes: 256
#include"bits/stdc++.h"
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)

int N, X, Y;
int ans[2000] ={};
signed main(){
	cin >> N >> X >> Y;
	X--; Y--;
	rep(i, N){
		for(int j=i+1; j<N; j++){
			int d = j-i;
			d = min(d, abs(X-i)+1+abs(Y-j));
			ans[d]++;
			//cout << i+1 << " " << j+1 << " " << d << endl;
		}
	}
	for(int i=1; i<N; i++) cout << ans[i] << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <cstdlib>

using namespace std;

int main(void) {

	int n, num;
	int S[13], H[13], C[13], D[13];
	char mark;

	for (int i = 0; i < 13; i++) {
		S[i] = 1;
		H[i] = 1;
		C[i] = 1;
		D[i] = 1;
	}

	cin >> n;

	for (int i = 0; i < n; i++){
		cin >> mark >> num;
		if (mark == 'S')
			S[num - 1] = 0;

		else if (mark == 'H')
			H[num - 1] = 0;

		else if (mark == 'C')
			C[num - 1] = 0;

		else 
			D[num - 1] = 0;
	}

	for (int i = 0; i < 13; i++) {
		if (S[i] != 0)
			cout << "S " << i + 1 << endl;
	}

	for (int i = 0; i < 13; i++) {
		if (H[i] != 0)
			cout << "H " << i + 1 << endl;
	}

	for (int i = 0; i < 13; i++) {
		if (C[i] != 0)
			cout << "C " << i + 1 << endl;
	}

	for (int i = 0; i < 13; i++) {
		if (D[i] != 0)
			cout <<"D " << i + 1 << endl;
	}

	return 0;
}

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

ll GCD(ll a, ll b){
    if(b==0) return a;
    else return GCD(b,a%b);
}

ll LCM(ll a, ll b){
    ll t = a/GCD(a,b);
    return t*b;
}

int main() {
    ll n; cin >> n;
    vector<ll> a(n);
    rep(i,n) cin >> a[i];
    ll ans = 1;
    rep(i,n){
        ans = LCM(ans,a[i]);
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
using ll = long long;
using namespace std;
template <typename T> using vec = std::vector<T>;

int main() {
    int X;
    cin >> X;
    if (X >= 1800) {
        cout << 1 << endl;
    } else if (X >= 1600) {
        cout << 2 << endl;
    } else if (X >= 1400) {
        cout << 3 << endl;
    } else if (X >= 1200) {
        cout << 4 << endl;
    } else if (X >= 1000) {
        cout << 5 << endl;
    } else if (X >= 800) {
        cout << 6 << endl;
    } else if (X >= 600) {
        cout << 7 << endl;
    } else if (X >= 400) {
        cout << 8 << endl;
    }
}


Measured memory_bytes: 3616
#include<stdio.h>
int main(void) {
	int n;
	int st;
	int a[20];
	int b[20];
	int c[20];
	int i;
	st=0;

	scanf("%d", &n);
	for (i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (i = 1; i <= n; i++) {
		scanf("%d", &b[i]);
	}
	for (i = 1; i <= n; i++) {
		scanf("%d", &c[i]);
	}

	for (i = 1; i < n; i++) {
		if (a[i + 1] == a[i] + 1) {
			st = st + c[a[i]];
		}
	}
	for (i = 1; i <= n; i++) {
		st = st + b[i];
	}

	printf("%d", st);

	return 0;
}

Measured memory_bytes: 128
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <bitset>
#include <deque>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <iterator>
#include <string>
#include <chrono>
#include <random>
#include <tuple>
#include <utility>
#include <fstream>
#include <complex>

const long INF = (1l << 30);
const long LINF = (1l << 60);

long d;

int main(){
    scanf("%ld", &d);
    printf("Christmas");
    for(int i = 0; i < 25 - d; i++){
        printf(" Eve");
    }
    printf("\n");
}


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

long long N, M;

int main(){
  cin >> N >> M;
  if(N>M){
	long long tmp = N;
	N = M;
	M = tmp;
  }
  if(N==1&&M==1) cout << 1 << endl;
  else if(N==1) cout << M-2 << endl;
  else cout << (N-2)*(M-2) << endl;
  return 0;
}

Measured memory_bytes: 256
const main = stdin => {
  const input = stdin.trim().split('\n')

  const [N, K] = input[0].split(' ').map(x => parseInt(x))
  const S = input[1]

  let ans = ''
  for (let i = 0; i < N; i++) {
    if (i === K - 1) {
      ans += S[i].toLowerCase()
    } else {
      ans += S[i]
    }
  }

  console.log(ans)
}
// 標準入力
main(require("fs").readFileSync("/dev/stdin", "utf8"))


Measured memory_bytes: 30596
from collections import deque

class Process:
    def __init__(self,name,time):
        self.name=name
        self.time=int(time)
    
    def __str__(self):
        return f'({self.name},{self.time})'

n,q=map(int,input().split())
ps=deque()
for i in range(n):
    name,time=input().split()
    ps.append(Process(name,time))

t=0
while len(ps)>0:
    p=ps.popleft()
#    print(f't={t}')
#    print(p)
    if p.time<=q:
        t+=p.time
        print(p.name,t)
    else:
        t+=q
        p.time-=q
        ps.append(p)


Measured memory_bytes: 17736
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main(){
    ll n;
    cin>>n;
    ll a[n],i;
    for(i=0;i<n;i++){
        cin>>a[i];
    }
    i = 1;
    ll req = 0,ans = 0;
    ll maxhei = a[0];
    while(i<n){
        if(a[i]>=maxhei){
            maxhei = max(maxhei,a[i]);
            i++;
            continue;
        }
        ans+=(maxhei-a[i]);
        a[i]+=(maxhei-a[i]);
        maxhei = max(maxhei,a[i]);
        i++;
    }
    cout<<ans;
    return 0;
}

Measured memory_bytes: 5168
#define _USE_MATH_DEFINES
#define INF 0x3f3f3f3f

#include <cstdio>
#include <iostream>
#include <sstream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#include <limits>
#include <map>
#include <string>
#include <cstring>
#include <set>
#include <deque>
#include <bitset>
#include <list>
#include <cctype>
#include <utility>
 
using namespace std;
 
typedef long long ll;
typedef pair <int,int> P;
typedef pair <int,P > PP;

class Node {
public:
  int to;
  int dist;
  Node() {}
  Node(int _t,int _d) : to(_t),dist(_d){}
};

bool is_LPG[6001];
bool dp[6001][2001]; //dp[city_id][remaining_LPG] = dist;

int get_city_id(map<string,int>& cities,const string& city){
  if(cities.find(city) == cities.end()){
    int idx = cities.size();
    cities[city] = idx;
  }
  return cities[city];
}

class State {
public:
  int city_id;
  int dist;
  int remaining_LPG;
  State(int _city_id,int _dist,int _con){
    city_id = _city_id;
    dist = _dist;
    remaining_LPG = _con;
  }

  bool operator <(const State& s) const{
    return (dist < s.dist);
  }

  bool operator >(const State& s) const{
    return (dist > s.dist);
  }
};

int main(){
  int total_roads;
  int total_LPG_stations;
  int capacity;
  while(cin >> total_roads >> total_LPG_stations >>capacity){
    if(total_roads == 0
       && total_LPG_stations == 0
       && capacity == 0) break;

    map<string,int> cities;
    memset(is_LPG,false,sizeof(is_LPG));
    memset(dp,false,sizeof(dp));

    string src,dst;
    cin >> src >> dst;
    get_city_id(cities,src);
    get_city_id(cities,dst);

    vector<Node> nodes[6001];
    for(int road_idx = 0; road_idx < total_roads; road_idx++){
      string from_str,to_str;
      int dist;

      cin >> from_str >> to_str >> dist;
      int from_num = get_city_id(cities,from_str);
      int to_num = get_city_id(cities,to_str);

      nodes[from_num].push_back(Node(to_num,dist));
      nodes[to_num].push_back(Node(from_num,dist));
    }

    for(int LPG_idx = 0; LPG_idx < total_LPG_stations; LPG_idx++){
      string city;
      cin >> city;
      is_LPG[get_city_id(cities,city)] = true;
    }

    priority_queue<State,vector<State>, greater<State> > que;
    que.push(State(get_city_id(cities,src),0,10*capacity));

    int dst_id = get_city_id(cities,dst);

    int res = INF;

    while(!que.empty()){
      State s = que.top();
      que.pop();

      if(dp[s.city_id][s.remaining_LPG]) continue;
      dp[s.city_id][s.remaining_LPG] = true;

      if(s.city_id == dst_id){
	res = s.dist;
	goto found;
      }

      for(int to_idx=0;to_idx<nodes[s.city_id].size();to_idx++){
	int to = nodes[s.city_id][to_idx].to;
	int dist = nodes[s.city_id][to_idx].dist;
	if(s.remaining_LPG < dist) continue;

	int next_remaining_LPG = (is_LPG[to] ? 10 * capacity : s.remaining_LPG - dist);

	que.push(State(to,s.dist + dist,next_remaining_LPG));
      }
    }
  found:;
    printf("%d\n",res >= INF ? -1 : res);
  }
  return 0;
}

Measured memory_bytes: 65044
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <string>
#include <map>
#include <queue>
using namespace std;

const int INF = 1000000;

int n;
vector<vector<int>> graph;

vector<int> bfs(int start){
    vector<int> dFrom(n+1,INF);
    queue<int> que;
    que.push(start);
    dFrom[start] = 0;

    while(que.size()){
        int tmpPoint = que.front();
        que.pop();

        for(int i=0; i<graph[tmpPoint].size(); i++){
            int nextPoint = graph[tmpPoint].at(i);

            //　訪れたことのない
            if(dFrom[nextPoint] == INF){
                que.push(nextPoint);
                dFrom[nextPoint] = dFrom[tmpPoint] + 1;
            }
        }
    }
    return dFrom;
}

int main() {
    cin >> n;
    graph.resize(n+1);

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

    vector<int> dFrom1 = bfs(1);
    vector<int> dFromN = bfs(n);

    int black=0, white=0;
    for(int i=1; i<=n; i++){
        if(dFrom1[i] <= dFromN[i]){
            black++;
        }else{
            white++;
        }
    }

    if (white >= black){
        printf("Snuke\n");
    }else{
        printf("Fennec\n");
    }
}

Measured memory_bytes: 6528
macro_rules! scan {
      ($t:ty) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.trim().parse::<$t>().unwrap()
          }
      };
      ($($t:ty),*) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              let mut iter = line.split_whitespace();
              (
                  $(iter.next().unwrap().parse::<$t>().unwrap(),)*
              )
          }
      };
      ($t:ty; $n:expr) => {
          (0..$n).map(|_|
              scan!($t)
          ).collect::<Vec<_>>()
      };
      ($($t:ty),*; $n:expr) => {
          (0..$n).map(|_|
              scan!($($t),*)
          ).collect::<Vec<_>>()
      };
      ($t:ty;;) => {
          {
              let mut line: String = String::new();
              std::io::stdin().read_line(&mut line).unwrap();
              line.split_whitespace()
                  .map(|t| t.parse::<$t>().unwrap())
                  .collect::<Vec<_>>()
          }
      };
      ($t:ty;;$n:expr) => {
          (0..$n).map(|_| scan!($t;;)).collect::<Vec<_>>()
      };
}

fn main() {
    let (n, c) = scan!(usize, usize);

    let mut chans = Vec::new();
    for _ in 0..c {
        chans.push([0; 2 * 100001])
    }
    for _ in 0..n {
        let (s, t, c) = scan!(usize, usize, usize);
        chans[c - 1][2 * s - 1] += 1;
        chans[c - 1][2 * t] -= 1
    }

    let mut tvs = [0; 2 * 100001];
    for i in 0..chans.len() {
        for j in 1..chans[i].len() {
            chans[i][j] += chans[i][j - 1];
        }

        for (j, tv) in tvs.iter_mut().enumerate() {
            if chans[i][j] > 0 {
                *tv += 1
            }
        }
    }
    println!("{}", tvs.iter().max().unwrap())
}


Measured memory_bytes: 33788
#coding:utf-8

if __name__ == "__main__":
    o_str = raw_input()
    e_str = raw_input()

    password = ""
    for o, e in zip(o_str, e_str):
        password += o
        password += e

    if len(o_str) != len(e_str):
        password += o_str[-1]

    print password



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

int main(){
	int n,a,b;
	cin >> n >> a >> b;
	int qAll = a+b;
	int qForeign = b;
	string s;
	cin.ignore();
	getline(cin, s, '\n');
	for(int i=0;i<n;i++){
		if(s[i]=='c'){
			printf("No\n");
		}else if(s[i]=='a'){
			if(qAll>0){
				qAll--;
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}else{
			if(qAll > 0 && qForeign > 0){
				qAll--;
				qForeign--;
				printf("Yes\n");
			}else{
				printf("No\n");
			}
		}
	}
}

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

using namespace std;

int main(){
    int N, l;
    cin >> N;
    int maxl = 0;
    int suml = 0;
    for(int i = 0; i < N; ++i){
        cin >> l;
        if(maxl < l) maxl = l; 
        suml += l;
    }

    if((suml-maxl) > maxl) cout << "Yes" << endl;
    else cout << "No" << endl; 


    return 0;
}

Measured memory_bytes: 256
/**
 *    This code has been written by YueGuang, feel free to ask me question. Blog: http://www.yx.telstudy.xyz
 *    created:
 */
#include <cstdio>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
#define REP(i, a, b) for(int i = a; i < b; i++)
#define REP_(i, a, b) for(int i = a; i <= b; i++)
#define sl(n) scanf("%lld", &n);
#define si(n) scanf("%d", &n);
#define RepAll(a) for(auto x: a)
#define cout(ans) cout << ans << endl;
typedef long long ll;

using namespace std;


int n, m, mx;
string s[105], t;
map<string, int> mp;
int main()
{
    int i;
    cin>>n;
    for(i=0; i<n; i++)
        cin>>s[i], mp[s[i]]++;
    cin>>m;
    while(m--)
        cin>>t, mp[t]--;
    for(i=0; i<n; i++)
        mx = max(mx, mp[s[i]]);
    cout<<mx;
    return 0;
}



Measured memory_bytes: 256
/* Dsingh_24 */

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define	endl		'\n'
#define pii         pair<ll int,ll int>
#define vi          vector<ll int>
#define all(a)      (a).begin(),(a).end()
#define F           first
#define S           second
#define sz(x)       (ll int)x.size()
#define hell        1000000007
#define rep(i,a,b)	for(ll int i=a;i<b;i++)
#define lbnd        lower_bound
#define ubnd        upper_bound
#define bs          binary_search
#define mp          make_pair
#define ios	    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;

#define N  100005

int main()
{
	ios
	ll n,i,j,ans=0;
	cin>>n;
	ans=(n*(n+1))/2;
	ll s1=0;
	if(n>=3)ans-=((3+(n-n%3))*(n/3))/2;
	ll s2=0;
	if(n>=5)ans-=((5+(n-n%5))*(n/5))/2;
	ll s3=0;
	if(n>=15)ans+=((15+(n-n%15))*(n/15))/2;
	cout<<ans;
	return 0;
}

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

#define array_sort_asc(array,size) sort(array, array+size);
#define array_sort_desc(array,size) sort(array, array+size,greater<>());

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

    int student_id_list[n];
    REP(i, n){
        cin >> student_id_list[i];
    }

    int student_touko_list[n];
    REP(i, n){
        int tmp = student_id_list[i] - 1;
        student_touko_list[tmp] = i + 1;
    }

    REP(i, n){
        cout << student_touko_list[i];
        if(i != n - 1) cout << " ";
    }
    cout << endl;
}

Measured memory_bytes: 1536
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
using namespace std;

int main() {
	int n;
	cin >> n;
	string s, t;
	cin >> s >> t;
	vector<char> a;
	rep(i, 2 * n) {
		if (i % 2 == 0) a.push_back(s[i / 2]);
		else a.push_back( t[i / 2]);
	}
	rep(i, 2 * n) {
		cout << a[i];
	}
	cout << endl;
}

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

int main() {
long long h,w,k,p=1000000007,x[108][10];
map<int,long long> y{{-1,1},{0,1},{1,2},{2,3},{3,5},{4,8},{5,13},{6,21}};
cin>>h>>w>>k;

if(w==1){
    cout<<1<<endl;
    return 0;
}

x[0][1]=1;
for(int i=2;i<=w;i++){
    x[0][i]=0;
}
for(int i=1;i<=h;i++){
    x[i][1]=(x[i-1][1]*y[w-2]+x[i-1][2]*y[w-3])%p;

    for(int j=2;j<=w-1;j++){
        x[i][j]=(x[i-1][j-1]*y[j-3]*y[w-j-1]+x[i-1][j]*y[j-2]*y[w-j-1]+x[i-1][j+1]*y[j-2]*y[w-j-2])%p;
    }
    x[i][w]=(x[i-1][w-1]*y[w-3]+x[i-1][w]*y[w-2])%p;
}

cout<<x[h][k]<<endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-


def insertionSort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g

        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v

    return cnt


def shellSort(A, n):
    cnt = 0
    m = 1
    G = []
    while True:
        if n < int((3 ** m - 1) / 2):
            m -= 1
            break
        else:
            G.append(int((3 ** m - 1) / 2))
            m += 1

    G.reverse()

    for i in range(m):
        cnt += insertionSort(A, n, G[i])

    print_line(A, G, m, cnt)


def print_line(A, G, m, cnt):
    print(m)
    for i in range(len(G)):
        if i == len(G) - 1:
            print(G[i])
        else:
            print("{0}".format(G[i]), end=' ')
    print(cnt)
    for i in range(len(A)):
        print(A[i])

A = []
n = int(input())
for i in range(n):
    A.append(int(input()))

shellSort(A, n)


Measured memory_bytes: 45520
n=int(input())
l=[]
q=0
for i in range(n):
    p=[int(j) for j in input().split()]
    q=max(q,p[1]+1)
    l.append([p[0],p[1]+1])
a=[]
table=[0]*(q+1)
for i in range(n):
    table[l[i][0]]+=1
    table[l[i][1]]-=1
for i in range(1,q+1):
    table[i]+=table[i-1]
ans=0
for i in range(len(table)):
    if i<=table[i]+1 and i<=n+1:
        ans=max(ans,i)



print(ans-1)



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

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

  string result = "No";
  rep(i,n) {
    rep(j,n) {
      if (n == 4*i + 7*j) result = "Yes";
    }
  }

  cout << result << endl;
  return 0;
}

Measured memory_bytes: 256
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)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $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, [ $t:tt ]) => {
        {
            let len = read_value!($next, usize);
            (0..len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
        }
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_imports)]
use std::cmp::{min, max};

fn main() {
    input!{
        n: usize,
        k: usize
    }
    let d = 1000000007;
    let mut st = vec![1; n + 1];
    for i in 1..n + 1 {
        st[i] = st[i - 1] * i % d;
    }
    let sti: Vec<usize> = st.iter().map(|&x| inv_m(x, d)).collect();
    for i in 1..k + 1 {
        if n - k + 1 < i {
            println!("0");
            continue;
        }
        println!("{}", st[k - 1] * sti[k - i] % d * sti[i - 1] % d * st[n - k + 1] % d * sti[n - k + 1 - i] % d * sti[i] % d);
    }
}

fn pow_m(n: usize, mut p: usize, d: usize) -> usize {
    let mut r = n;
    let mut ret = 1;
    while p > 0 {
        if p % 2 == 0 {
            r = r * r % d;
            p /= 2;
        } else {
            ret = ret * r % d;
            p -= 1;
        }
    }
    ret
}

fn inv_m(n: usize, d: usize) -> usize {
    pow_m(n, d - 2, d)
}


Measured memory_bytes: 4352
s = list(input())
t = ['dream','dreamer','erase','eraser']
ans = 0
for i in range(100000):
    check = 0
    #print(s)
    for j in t:
        #print(str(s[-1 * (len(j)):]),list(j))
        if s[-1 * (len(j)):] == list(j):
            del s[-1 * (len(j)):]
            check = 1
            break
    if len(s) == 0:
        ans = 1
        break
if ans == 1:
    print('YES')
else:
    print('NO')





Measured memory_bytes: 3956
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define fi first
#define se second
#define pb push_back
#define all(v) v.begin(),v.end()
#define repf(i,a,b) for(ll i=a;i<b;i++)
#define repb(i,a,b) for(ll i=a;i>=b;i--)
#define IOS ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define mod 1000000007
#define MOD 998244353 

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

ordered_set<ll> ods;

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

ll power(ll a, ll n, ll m)
{
    ll ans=1;
    while(n)
    {
        if(n&1) ans=(ans*a)%m;
        n>>=1;
        a=(a*a)%m;
    }
    return ans;
}

ll invmod(ll a, ll m)
{
    return power(a,m-2,m);
}

void solve(ll t)
{
    // cout<<"Case #"<<t<<":\n";
    ll n,m;
    cin>>n>>m;
    ll s=0;
    repf(i,0,m) 
    {
        ll x;
        cin>>x;
        s+=x;
    }
    if(n-s>=0) cout<<n-s<<endl;
    else cout<<-1<<endl;
}

int main()
{
    IOS;
    ll t;
    // cin>>t;
    t=1;
    ll tt=1;
    while(t--)
    {
        solve(tt);
        tt++;
    }
}     


Measured memory_bytes: 3656
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N = int(input())
S = input()
tmp = 0
MIN = 0
for s in S:
	if s == '(':
		tmp += 1
	else:
		tmp -= 1
	MIN = min(tmp,MIN)

ans1 = ''
if MIN < 0:
	for i in range(-MIN):
		ans1 = ans1 + '('

ans2 = ''
tmp -= MIN
if tmp > 0:
	for i in range(tmp):
	 	ans2 = ans2 + ')'

print(ans1+S+ans2)


Measured memory_bytes: 4212
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <cmath>

using namespace std;

int main(){
    int N,sum=0,count=0;
    cin>>N;
    int A[N],B[N],C[N];
    for(int i=0;i<N;i++) cin>>A[i];
    for(int i=0;i<N;i++) cin>>B[i];
    for(int i=0;i<N-1;i++) cin>>C[i];
    for(int i=0;i<N;i++){
        sum+=B[A[i]-1];
        if(A[i-1]+1==A[i]){
            sum+=C[A[i-1]-1];
        }
    }
    cout<<sum<<endl;
    return 0;
}

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

int main( void )
{
    int a,b;
    cin >> a >> b;
    
    if ( a % 3 == 0 || b % 3 == 0 || (a + b) % 3 == 0 )
        cout << "Possible" << endl;
    else
        cout << "Impossible" << endl;
}


Measured memory_bytes: 256
#include <algorithm>
#include <bitset>
#include <cmath>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>

#define repd(i, a, b) for (ll i = (a); i < (b); i++)
#define rep(i, n) repd(i, 0, n)
typedef long long ll;

using namespace std;

template <typename T> void output(T, int);
int gcd(int a, int b);

int main() {
    // source
    string s;
    cin >> s;
    vector<string> t = {"dream", "dreamer", "erase", "eraser"};
    queue<string> q;
    q.push(s);
    bool ans = false;
    while (!q.empty() || ans) {
        bool judge = false;
        string temp = q.front();
        if (temp.size() == 0) {
            break;
        }
        q.pop();
        rep(i, 4) {
            if (t[i].size() > temp.size()) {
                continue;
            }
            bool b = true;
            rep(l, t[i].size()) {
                if (t[i][l] != temp[l]) {
                    b = false;
                }
            }

            if (b) {
                if (temp.size() == t[i].size()) {
                    ans = true;
                    cout << "YES" << endl;
                    return 0;
                } else {
                    q.push(temp.substr(t[i].size(), temp.size() - t[i].size()));
                }
            }
        }
    }
    if (ans) {
        cout << "YES" << endl;
    } else {
        cout << "NO" << endl;
    }
    return 0;
}

template <typename T> void output(T a, int precision) {
    if (precision > 0) {
        cout << setprecision(precision) << a << "\n";
    } else {
        cout << a << "\n";
    }
}

template <typename T> T min(T a, T b) {

    if (a < b) {
        return a;
    } else {
        return b;
    }
}

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


Measured memory_bytes: 892
n, m = list(map(int, input().split(" ")))
a_list = list(map(int, input().split(" ")))
a_sum = sum(a_list)
criteria = (1 / (4 * m)) * a_sum
a_list.sort()
a_list.reverse()
def check(a_list, m):
  for a in a_list:
    if a < criteria:
      return False
    m -= 1
    if m == 0:
      return True
result = check(a_list, m)
if result:
  print("Yes")
else:
  print("No")


Measured memory_bytes: 3064
#include <stdio.h>
void book(int v[],int x,int n)
{
	int i;
	for(i=0;i<n;i++)
		scanf("%d",&v[i]);
	for(i=0;i<n;i++)
		x-=v[i];
	printf("%d\n",x);
}
	
int main(void)
{
	int sum;
	int b[9];
	
	scanf("%d",&sum);
	
	while(sum){
		book(b,sum,9);
		scanf("%d",&sum);
	}
	
	return 0;
}

Measured memory_bytes: 596
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
#define fo(i,s,e) for( i=s;i<e;i++)
#define rfo(i,s,e) for(i=s;i>e;i--)
#define LL long long int 
const LL MOD=1e9+7;
#define pb push_back
#define pob pop_back()
#define sp " "
#define ff first
#define ss second
//            When something is important enough, you do it even if the odds are not in your favor.

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    // code goes here
    int t=1;//cin>>t;
    while(t--){
      LL n,m,i;cin>>n>>m;
      set<LL> s;
      fo(i,0,m){
        LL x;cin>>x;
        s.insert(x);
      }
      LL dp[n+4];
      dp[n]=1;
      rfo(i,n-1,-1){
        if(s.count(i)) dp[i]=0;
        else{
          dp[i]=dp[i+1];
          if(i!=n-1) dp[i]+=dp[i+2],dp[i]%=MOD;
        }
      }
      cout<<dp[0];
    }
    return 0;
}

Measured memory_bytes: 9044