akhauriyash/Code-Regression huggingface dataset:
#include <stdio.h>
#include <stdlib.h>

#define N 200

typedef struct stack{
    int top;
    int data[N];
} Stack;

void initialize(Stack*);
int top(Stack*);
void push(Stack*, int);
void pop(Stack*);
int is_empty(Stack*);

int main(){
    int in;
    Stack *stack = malloc(sizeof(struct stack));

    initialize(stack);

    while(scanf("%d", &in) != EOF){
        if(in == 0){
            printf("%d\n", top(stack));
            pop(stack);
        }else{
            push(stack, in);
        }
    }

    free(stack);

    return 0;
}

void initialize(Stack *stack){
    stack->top = 0;
}

int top(Stack *stack){
    return stack->data[stack->top - 1];
}

void push(Stack *stack, int e){
    stack->data[stack->top++] = e;
}

void pop(Stack *stack){
    if(is_empty(stack)){
        printf("Error: stack is empty.");
    }else{
        --stack->top;
    }
}

int is_empty(Stack* stack){
    return stack->top == 0;
}

Measured memory_bytes: 600
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int x,y;
    cin>>x>>y;
    if (x==1 && (y==2 || y==4))
        cout<<"Yes"<<endl;
    else if(x*2>y || x*4<y || y%2==1)
        cout<<"No"<<endl;
    else
        cout<<"Yes"<<endl;
    return 0;
}


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

const ll mod = 1e9 + 7;

template <class T> inline bool chmax(T &a, const T &b) {
    if(a >= b) return false;
    a = b;
    return true;
}
template <class T> inline bool chmin(T &a, const T &b) {
    if(a <= b) return false;
    a = b;
    return true;
}

/*-------------------------------------------*/

vector<ll> fact, fact_inv;

template <typename T> T mpow(T x, T n) {
    T ret = 1;
    while(n > 0) {
        if(n & 1) (ret *= x) %= mod;
        (x *= x) %= mod;
        n = n >> 1;
    }
    return ret;
}

void COMinit(ll MAX) {
    fact.resize(MAX + 1);
    fact_inv.resize(MAX + 1);
    fact[0] = fact_inv[0] = 1;
    rep(i, MAX) {
        fact[i + 1] = fact[i] * (i + 1) % mod;
        fact_inv[i + 1] = mpow(fact[i + 1], mod - 2);
    }
}

ll COM(ll n, ll k) {
    if(n < k || k < 0) return 0;
    return (fact[n] * fact_inv[k] % mod) * fact_inv[n - k] % mod;
}

ll f(int n, int m) { return COM(n + m - 1, n); }

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

    int n, k;
    cin >> n >> k;
    COMinit(2 * n);
    if(++k >= n) {
        cout << f(n, n) << endl;
        return 0;
    }

    ll x = f(n, n);

    ll y = 0;
    while(k < n) {
        y += COM(n, k) * f(k, n - k);
        y %= mod;
        k++;
    }

    cout << (x + mod - y) % mod << endl;
}

Measured memory_bytes: 6528
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <queue>
#include <cmath>
#include <stdio.h>

#define _ << " " <<
#define debug(x) #x << " = " << x

#define ll long long
#define ull unsigned long long

int main() {
    std::ios::sync_with_stdio(false);

    ll s, c;
    std::cin >> s >> c;

    if (s * 2 >= c) {
        std::cout <<  c / 2 << std::endl;
    } else {
        ll t1 = s;
        c -= 2 * s;

        std::cout << t1 + c / 4 << std::endl;
    }

    return 0;
}

Measured memory_bytes: 256
# ABC116 C-Grand Garden

n = int(input())
h = [0] + list(map(int, input().split()))

ans = 0
for i in range(0, 101):
    count = 0
    for j in range(n):
        if h[j] - i <= 0 and h[j+1] - i > 0:
            count += 1
    ans += count 
print(ans)

Measured memory_bytes: 39024
#include <iostream>
#include <bitset>
#include <fstream>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <vector>
#include <algorithm>
#include <numeric>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>
#include <functional>
#include <cctype>
#include <list>
#include <limits>
#include <unordered_map>
#define Debug 0
//#include <boost/multiprecision/cpp_int.hpp>

const double EPS = (1e-10);


using namespace std;
using Int = long long;
//using namespace boost::multiprecision;

const Int MOD = 1000000007;

Int mod_pow(Int x, Int n) {
    Int res = 1;
    while(n > 0) {
        if(n & 1) res = (res * x) % MOD; //ビット演算(最下位ビットが1のとき)
        x = (x * x) % MOD;
        n >>= 1; //右シフト(n = n >> 1)
    }
    return res;
}

//最大公約数
template<typename T>
T gcd(T a, T b) {
    return b != 0 ? gcd(b, a % b) : a;
}

//最小公倍数
template<typename T>
T lcm(T a, T b) {
    return a * b / gcd(a, b);
}

void fast_input() {
    cin.tie(0);
    ios::sync_with_stdio(false);
}

int solve(int x, int y, int s) {
    int ret = 0;
    for (int a = 1; a <= s; a++) {
        for (int b = 1; b <= s; b++) {
            int sum = a*(100+x)/100 + b*(100+x)/100;
            if (sum == s) {
                ret = max(ret, a*(100+y)/100 + b*(100+y)/100);
            }
        }
    }
    return ret;
}

int main(){
    int a, b, s;
    vector<int> ans;
    while (1) {
        cin >> a >> b >> s;
        if (!a && !b && !s) break;
        ans.push_back(solve(a, b, s));
    }
    for (auto &i: ans) {
        cout << i << endl;
    }
}





Measured memory_bytes: 3168
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<assert.h>
#include<numeric>
#include<stdio.h>
#include <cstdint>
#include <stdlib.h> 
#include <time.h>
using namespace std;
#define REP(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i )
#define rep(i,n) REP(i,0,n)
#define drep(i,n,m) for(int i = n;i >= m;i--)
#define rrep(i,n) REP(i,1,n+1)
#define all(a) a.begin(), a.end()
#define fi first
#define se second
#define RNG(x, a, n) &((x)[a]), &((x)[n])
long long gcd(long long a, long long b) { return b == 0 ? a : gcd(b, a % b); }
long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
typedef long long ll;
typedef pair<ll, ll> Pll;
typedef pair<int, int> PII;
typedef vector<ll> Vl;
typedef vector<int> VI;
typedef tuple<int, int, int> TT;
#define chmin(x,y) x = min(x,y)
#define chmax(x,y) x = max(x,y)
#define rall(v) v.rbegin(), v.rend()
#define dmp(x,y) make_pair(x,y)
#define dmt(x, y, z) make_tuple(x, y, z)
#define pb(x) push_back(x)
#define pf(x) push_front(x)
const int MAX = 500000;
const int inf = 1000000007;
const ll mod = 1000000007;
const long double PI = (acos(-1));
const long double EPS = 0.0000000001;

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


ll ans;
ll n, a[3000005], bit[65];

int main() {

	cin >> n;
	rep(i, n)cin >> a[i];

	rep(i, n) {
		int j = 0;
		while (a[i]) {
			if (a[i] & 1)bit[j]++;
			a[i] >>= 1;
			j++;
		}
	}

	ll cnt = 1;
	rep(i, 64) {
		ans = (ans + (((bit[i] * (n - bit[i])) % mod) * cnt) % mod) % mod;
		cnt <<= 1;
		cnt %= mod;
	}

	cout << ans << endl;

	return 0;
}


Measured memory_bytes: 5888
# -*- coding: utf-8 -*-
m, d = map(int,input().split())

ans = 0
for i in range(1, m + 1):
    for j in range(1, d + 1):
        d1 = j % 10
        d10 = j // 10
        if d1 >= 2 and d10 >= 2 and d1 * d10 == i:
            ans += 1
print(ans)


Measured memory_bytes: 2940
#include<queue>
#include<stack>
#include<math.h>
#include<cmath>
#include<bitset>
#include<stdio.h>
#include<string>
#include<map>
#include<algorithm>
#include<vector>
#include<iostream>
#include<utility>
#include<functional>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int main(){
  double pi = 3.141592653589793238;
  int a,b,h,m,rad;
  double x,y,z,v,w;
  cin >> a >> b>> h >> m;
  v=h,w=m;
  z=abs(30*v-5.5*w);
  x=a,y=b;
  printf("%.15lf\n",sqrt(x*x+y*y-2*x*y*cos(z/180.0*pi)));
  return 0;
}

Measured memory_bytes: 4196
//#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <time.h>
#include <stdio.h>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
template<typename T>
void vdeb(std::vector<T> &da) {
	for (int i = 0;i < da.size();i++) {
		if (i == da.size() - 1) std::cout << da[i];
		else std::cout << da[i] << ' ';
	}
	std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
	for (int i = 0;i < da.size();i++) vdeb(da[i]);
	std::cout << std::endl;
}
using namespace std;

int dp[2][1000100];

int main(){
	string s;cin >> s;
	int n = s.size();
	dp[0][0] = s[n-1]-'0';
	dp[1][0] = 11-dp[0][0];
	rip(i,n,1){
		if(s[n-i-1] == '9'){
			dp[0][i] = 9 + dp[0][i-1];
			dp[1][i] = min(2 + dp[0][i-1], dp[1][i-1]);
		}
		else{
			dp[0][i] = min(dp[0][i-1], dp[1][i-1]) + s[n-i-1]-'0';
			dp[1][i] = min(dp[0][i-1], dp[1][i-1] - 2) + 11 - s[n-i-1] + '0';
		}
	}
	cout << min(dp[0][n-1], dp[1][n-1]) << endl;
}

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

signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    srand(time(0));
    string s;
    cin >> s;
    int b = 0, ans=0;
    for (int i=0; i < s.size(); i++){
        if (s[i] == 'B') b++;
        else ans += b;
    }
    cout << ans;
}


Measured memory_bytes: 1356
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial



def union_r(node):
    global road_union
    if road_union[node] != node:
        road_union[node] = union_r(road_union[node])
    return road_union[node]

def union_t(node):
    global train_union
    if train_union[node] != node:
        train_union[node] = union_t(train_union[node])
    return train_union[node]


road_union, train_union = [], []


def main():
    node_num, road_num, train_num = map(int, input().split())

    global road_union
    road_union = [i for i in range(node_num + 1)]
    for i in range(road_num):
        a, b = map(int, input().split())
        parent_a = union_r(a)
        parent_b = union_r(b)
        road_union[min(parent_a, parent_b)] = max(parent_a, parent_b)
        # print(road_union)

    global train_union
    train_union = [i for i in range(node_num + 1)]
    for i in range(train_num):
        a, b = map(int, input().split())
        parent_a = union_t(a)
        parent_b = union_t(b)
        train_union[min(parent_a, parent_b)] = max(parent_a, parent_b)

    # print(train_union, road_union)

    ryouhou = [0 for i in range(node_num + 1)]
    for i in range(1, node_num + 1):
        parent_r = union_r(i)
        parent_t = union_t(i)
        ryouhou[i] = (parent_r, parent_t)

    # print(train_union, road_union, 'uuu')

    count_d = Counter(ryouhou)

    for i in range(1, node_num + 1):
        now_flg = ryouhou[i]
        print(count_d[now_flg], end=' ')
    print()





if __name__ == '__main__':
    main()

Measured memory_bytes: 125652
#include <iostream>
using namespace std;
static const int N=100;

int main(){
	
	int M[N][N];//定义邻接矩阵 
	
	int n;
	int u,v,k;
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			M[i][j]=0; 
	for(int i=0;i<n;i++){
		cin>>u>>k;
		u--;
		for(int j=0;j<k;j++){
			cin>>v;
			v--;
			M[u][v]=1;
		}
	} 
	
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(j>0)
				cout<<" ";
			cout<<M[i][j];
		}
		cout<<endl;
	}
	
	return 0;
}


Measured memory_bytes: 3116
#include "iostream"
#include "climits"
#include "list"
#include "queue"
#include "stack"
#include "set"
#include "functional"
#include "algorithm"
#include "string"
#include "map"
#include "unordered_map"
#include "unordered_set"
#include "iomanip"
#include "cmath"
#include "random"
#include "bitset"
#include "cstdio"

using namespace std;

const long long int MOD = 1000000007;


long long int N, M, K, H, W, L, R;

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

	cin >> N >> M;
	cout << max({ N + M,N - M,N*M }) << endl;
	
	return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using vi = vector<int>;
using vl = vector<ll>;
#define rep(i, n) for(ll i = 0;i < n;i++)
#define all(i) i.begin(), i.end()
template<class T, class U> bool cmax(T& a, U b) { if (a<b) {a = b; return true;} else return false; }
template<class T, class U> bool cmin(T& a, U b) { if (a>b) {a = b; return true;} else return false; }

template <ll Mod>
struct modint {
  ll n;

  modint(const ll x = 0) : n(x % Mod) {}
  modint operator+(const modint r) const { return modint(*this) += r; }
  modint operator-(const modint r) const { return modint(*this) -= r; }
  modint operator*(const modint r) const { return modint(*this) *= r; }
  modint operator/(const modint r) const { return modint(*this) /= r; }
  modint &operator+=(const modint r) {
    n += r.n;
    if (n >= Mod) n -= Mod;
    return *this;
  }
  modint &operator-=(const modint r) {
    if (n < r.n) n += Mod;
    n -= r.n;
    return *this;
  }
  modint &operator*=(const modint r) {
    n = n * r.n % Mod;
    return *this;
  }
  modint &operator/=(const modint r) { return *this *= r.inv(); }
  modint pow(ll x) const {
    modint<Mod> ret(1), tmp(*this);
    while (x) {
      if (x&1) ret *= tmp;
      tmp *= tmp;
      x >>= 1;
    }
    return ret;
  }
  modint inv() const { return pow(Mod-2); }
  friend ostream& operator<<(ostream& os, const modint& obj) { return os << obj.n; }
  friend istream& operator>>(istream& is, modint& obj) { return is >> obj.n; }
};
constexpr ll mod = 1000000007;
using mint = modint<mod>;

// T modint
template<class T>
struct Combination {
  vector<T> fact, inv_fact;
  Combination(ll n) : fact(n+1), inv_fact(n+1) {
    fact[0] = T(1);
    for (ll i = 1; i <= n; i++) fact[i] = fact[i-1] * static_cast<T>(i);
    inv_fact[n] = fact[n].inv();
    for (ll i = n; i > 0; i--) inv_fact[i-1] = inv_fact[i] * static_cast<T>(i);
  }

  T P(ll n, ll k) const {
    return fact[n] * inv_fact[n-k];
  }

  T C(ll n, ll k) const {
    if(n<k||k<0) return T(0);
    return fact[n] * inv_fact[n-k] * inv_fact[k];
  }

  T H(ll n, ll k) const {
    return C(n+k-1, n-1);
  }
};

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

  ll n, k;
  cin >> n >> k;
  vector<ll> b(n);
  rep(i, n) {
    cin >> b[i];
  }
  sort(all(b));
  vector<mint> a(n);
  rep(i, n) {
    if (b[i] < 0) {
      b[i] += mod;
    }
    a[i] = mint(b[i]);
  }

  mint ans = 0;
  mint ma = 0;
  mint mi = 0;
  Combination<mint> comb(2*n);
  rep(i, n) {
    ll l = i;
    //cerr << a[i] << endl;
    //cerr << l << endl;
    //cerr << comb.C(l, k-1) << endl;
    //cerr << a[i] * comb.C(l, k-1) << endl;
    //cerr << endl;
    ma += a[i] * comb.C(l, k-1);
  }
  rep(i, n) {
    ll r = n-1-i;
    //cerr << a[i] << endl;
    //cerr << r << endl;
    //cerr << comb.C(r, k-1) << endl;
    //cerr << a[i] * comb.C(r, k-1) << endl;
    //cerr << endl;
    mi += a[i] * comb.C(r, k-1);
  }
  cerr << ma << " " << mi << endl;
  ans = ma-mi;
  cout << ans << endl;
}


Measured memory_bytes: 4992
#include<bits/stdc++.h>
#define ll long long
#define REP(i, n) for (int i=0; i<n; ++i)
#define print(x) cout << x << endl;

using namespace std;

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

}

vector<ll> factorize(ll a) {
    vector<ll> res;
    for (ll i=2; i*i<=a; ++i) {
        if (a % i == 0) {
            res.push_back(i);
            while (a % i == 0) {
                a /= i;
            }
        }
    }
    if (a != 1) res.push_back(a);
    return res;
}

void solve() {
    ll A, B;
    cin >> A >> B;
    
    ll g = gcd(A, B);

    vector<ll> f = factorize(g);
    ll ans = f.size() + 1;
    print(ans);
}

int main() {

    solve();
    return 0;
}


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

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    string s;
    cin >> s;
    rep(i,s.size()-1){
        if(s[i] == 'A' && s[i+1] == 'C'){
            cout << "Yes" << endl;
            return 0;
        }
    }
    cout << "No" << endl;
    return 0;
}

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

int main() {
    int n,m;
    cin>>n>>m;
    int a[60],b[60],c[60],d[60];
    for(int i=0;i<n;i++) {
        cin>>a[i]>>b[i];
    }
    for(int j=0;j<m;j++) {
        cin>>c[j]>>d[j];
    }
    for(int i=0;i<n;i++) {
        int min_dis=abs(a[i]-c[0])+abs(b[i]-d[0]),count=1;
        for(int j=1;j<m;j++) {
            int distance=abs(a[i]-c[j])+abs(b[i]-d[j]);
            if(min_dis>distance) {
                min_dis=distance;
                count=j+1;
            }
        }
        cout<<count<<endl;
    }
    return 0;
}


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

#define endl '\n'

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

    int h,n; cin >> h >> n;
    int a[n], b[n], dp[h+1];
    for (int i=0; i<=h; i++) dp[i] = 1e9;
    dp[0] = 0;
    for (int i=0; i<n; i++){
        cin >> a[i] >> b[i];
        for (int j=0; j<h; j++){
            dp[min(j + a[i], h)] = min(dp[min(j + a[i], h)], dp[j] + b[i]);
        }
    }
    cout << dp[h] << endl;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <cmath>
#include <iomanip>
#include <stack>
#include <queue>
#include <numeric>
#include <map>
#include <unordered_map>
#include <set>
#define rep(i,n) for(int i=0;i<(n);i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define mod 1000000007
using ll = long long;
using namespace std;

int main(){
  int H,W;
  cin >> H >> W;
  vector<vector<char>> V(H+2,vector<char>(W+2));
  for(int x=0;x<W+2;x++){
    V[0][x] = '.';
    V[H+1][x] = '.';
  }
  for(int y=1;y<=H;y++){
    V[y][0] = V[y][W+1] = '.';
    for(int x=1;x<=W;x++){
      cin >> V[y][x];
    }
  }
  for(int y=1;y<=H;y++){
    for(int x=1;x<=W;x++){
      if(V[y][x] == '#') cout << '#';
      else{
        int cnt = 0;
        if(V[y-1][x-1] == '#')cnt++;
        if(V[y-1][x] == '#')cnt++;
        if(V[y-1][x+1] == '#')cnt++;
        if(V[y][x-1] == '#')cnt++;
        if(V[y][x+1] == '#')cnt++;
        if(V[y+1][x-1] == '#')cnt++;
        if(V[y+1][x] == '#')cnt++;
        if(V[y+1][x+1] == '#')cnt++;
        cout << cnt;
      }
    }
    cout << endl;
  }

  return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
    int main(void)
    {
      int N,K,i,denko=1;
     
      scanf("%d",&N);
      scanf("%d",&K);
     
      for(i=0;i<N;i++){
        if(denko*2-denko<=K){
          denko*=2;
        } else {
          denko+=K;
        }
      }
     
      printf("%d\n",denko);
     
      return 0;
    }

Measured memory_bytes: 128
import copy
n = int(input())
t = list(map(int, input().split()))
m = int(input())
d = []
ans = []
for i in range(m):
    d.append(list(map(int, input().split())))
for i in range(m):
    s = copy.copy(t)
    s[d[i][0] - 1] = d[i][1]
    ans.append(sum(s))
for i in ans:
    print(i)

Measured memory_bytes: 3444
#include <cstdio>
#include <string>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
#include <map>
#include <vector>
#include <iomanip>
#include <tuple>
#include <queue>
#include <numeric>
using namespace std;
typedef long long ll;
#define rep(i, a, n) for (int i=a;i<n;++i)
#define repeq(i, a, n) for(int i=a;i<=n;++i)
#define repi(m, itr) for (auto itr = m.begin();itr != m.end();++itr)
#define per(i, a, n) for (int i=n-1; i>=a;--i)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()

// 
ll N;
ll X;
ll ans = 0;

int main(){
    cin >> N >> X;
        ll n = N;
        ll x = X;
    while(true){
        ll burger = pow(2, n+2) - 3;
        ll meat = pow(2, n+1) - 1;
        ll center = (burger+1) / 2;
        if(n==0){
            cout << 1 << endl;
            return 0;
        }
        if(n==1){
            ll a[6] = {0, 0, 1, 2, 3, 3};
            ans += a[x];
            cout << ans << endl;
            return 0;
        }
        if(x == center){
            ans += (meat+1)/2;
            cout << ans << endl;
            return 0;
        }else if(x == burger){
            ans += meat;
            cout << ans << endl;
            return 0;
        }else if(x == 1){
            cout << ans << endl;
            return 0;
        }else if(x<center){
            x -= 1;
            n -= 1;
        }else{
            ans += (meat+1)/2;
            x -= center;
            n -= 1;
        }
    }

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




Measured memory_bytes: 512
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
#define pb push_back 
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)

using namespace std;

int main()
{
    IOS;
    int n;
    cin >> n;
    int ct = 0;
    map<int,int>m;
    for(int i = 1;i<=n;i++)
    {
        int val1 = i%10;
        int val2;
        if(i >=100000)
            val2 = i/100000;
        else if(i>=10000)
            val2 = i/10000;
        else if(i>=1000)
            val2 = i/1000;
        else if(i>=100)
            val2 = i/100;
        else if(i>=10)
            val2 = i/10;
        else
            val2 = i;
        m[val2*10+val1]++;
    }
    ll tot = 0;
    for(int i = 10;i<=99;i++)
    {
        ll x = m[i];
        int j = i/10 + 10*(i%10);
        ll y = m[j];
        tot += x*y;
    }
    cout << tot;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#define ll long long int
#define pb push_back
#define mp make_pair
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);
using namespace std;
//Some custom functions for quick use(fast_power,nCr,lcm,gcd)
ll power(ll a, ll b)
{
  if(b == 0)
   {
      return 1;
   }
   else if(b % 2 == 0)
   {
      return power(a*a, b/2);
   }
   else
   {
      return a * power(a*a, b/2);
   }
}
long long int nChoosek( long long int n, long long int k )
{
if (k > n) return 0;
if (k * 2 > n) k = n-k;
if (k == 0) return 1;
    int result = n;
for( int i = 2; i <= k; ++i )
{
        result *= (n-i+1);
        result /= i;
}
    return result;
}

long long int lcm(long long int a,long long int b)
{
    long long int m,n;
    m=a;
    n=b;
    while(m!=n)
    {
        if(m < n)
        {
            m=m+a;
        }
        else
        {
            n=n+b;
        }
    }
    return m;
}

long long int gcd(long long int a,long long int b)
{ 
if (a == 0) 
return b; 
return gcd(b % a, a);
}
/* Basic DFS Boilerplate */ 
vector<ll> adj[10005]; // graph is stored as adjacency list
bool visited[10005];
void dfs(ll s)  //given node s
{
    if(visited[s])
        return;
    visited[s]=true;
    //the process on node 's'
    for(auto u : adj[s])
    {
        dfs(u);
    }    
}
/* Basic BFS Boilerplate */
ll x;   // given node
queue<ll>q;
bool vis[10005];
ll dist[10005];
//
void bfs(ll x)
{
    vis[x]=true;
    dist[x]=0LL;
    q.push(x);
    while (!q.empty())
    {
        ll s=q.front();
        q.pop();
        //the process
        //on node x
        for(auto u :adj[x])
        {
            if(vis[u]==true)
                continue;
            vis[u]=true;
            dist[u]=dist[x]+1;
            q.push(u);
        }
    }
    
}
int main()
{
    fastio
    ll s,w;
    cin>>s>>w;
    if(s<=w)
    {
        cout<<"unsafe"<<'\n';
    }
    else
    {
        cout<<"safe"<<'\n';
    }
    return 0;
}


Measured memory_bytes: 3892
N, M = [int(nm) for nm in input().split()]
AB = []
for n in range(N):
  A, B = [int(ab) for ab in input().split()]
  AB.append([A, B])
AB.sort()
money = 0
while M > 0:
  Ai, Bi = AB[0][0], AB[0][1]
  if Bi <= M:
    money += Ai * Bi
    M -= Bi
  else:
    money += Ai * M
    M = 0
  AB.remove(AB[0])
print(money)

Measured memory_bytes: 20072
#include<iostream>
#include<vector>
 
int main()
{
  //input
  int n = 0;
  std::cin >> n;
  std::vector<int> array(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> array.at(i);
  }
 
  long prev = array[0];
  long sum = 0;
  for (unsigned int i = 1; i < array.size(); ++i) {
    int dif = prev - array[i];
    if (dif > 0) { sum += dif; }
    else         { prev = array[i]; }
  }
 
  //putput
  std::cout << sum;
  
  return 0;
}

Measured memory_bytes: 3568
reverse_s = input().strip()[::-1]

while True:
    if len(reverse_s) == 0:
        print("YES")
        exit()
    if reverse_s.startswith('maerd'):
        reverse_s = reverse_s[len('maerd'):]
    elif reverse_s.startswith('remaerd'):
        reverse_s = reverse_s[len('remaerd'):]
    elif reverse_s.startswith('esare'):
        reverse_s = reverse_s[len('esare'):]
    elif reverse_s.startswith('resare'):
        reverse_s = reverse_s[len('resare'):]
    else:
        print("NO")
        exit()


Measured memory_bytes: 3188
#include "bits/stdc++.h"
using namespace std;

int main() {
	long long H, W, K, NOW = 1;
	static long long ANS[300][300] = {};
	cin >> H >> W >> K;
	string S[300];
	for (int i = 0; i < H; i++) cin >> S[i];
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (S[i][j] == '#') {
				for (int k = i; k >= 0; k--) {
					if (ANS[k][j] != 0) break;
					ANS[k][j] = NOW;
				}
				NOW++;
			}
		}
	}
	for (int i = 1; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (ANS[i][j] == 0) ANS[i][j] = ANS[i - 1][j];
		}
	}
	for (int j = 1; j < W; j++) {
		if (ANS[0][j] == 0) {
			for (int i = 0; i < H; i++) {
				ANS[i][j] = ANS[i][j - 1];
			}
		}
	}
	for (int j = W - 1; j >= 0; j--) {
		if (ANS[0][j] == 0) {
			for (int i = 0; i < H; i++) {
				ANS[i][j] = ANS[i][j + 1];
			}
		}
	}
	for (int i = 0; i < H; i++) {
		for (int j = 0; j < W; j++) {
			if (j == W - 1) cout << ANS[i][j] << endl;
			else cout << ANS[i][j] << " ";
		}
	}
}

Measured memory_bytes: 1664
#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<math.h>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
using namespace std;
#define REP(i,m,n) for(int i=(int)m ; i < (int) n ; ++i )
#define rep(i,n) REP(i,0,n)
typedef long long ll;
typedef pair<int,int> pint;
typedef pair<ll,int> pli;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;

long double dp[8000],dpp[8000];
int main(){
    int n;
    cin>>n;
    long double p[n];
    rep(i,n)cin>>p[i];
    dp[4000]=1.0;
    rep(i,n){
        rep(j,8000)dpp[j]=0;
        rep(j,8000){
            if(dp[j]==0)continue;
            dpp[j+1]+=p[i]*dp[j];
            dpp[j-1]+=(1.0-p[i])*dp[j];
        }
        rep(j,8000)dp[j]=dpp[j];
    }
    long double ans=0;
    REP(i,4000,8000)ans+=dp[i];
    cout<<setprecision(12)<<ans<<endl;
    return 0;
}

Measured memory_bytes: 512
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <bitset>
#include <stack>
#include <cmath>
#include <time.h>
#include <unordered_set>
#include <unordered_map>
#define ll long long
#define LINF 0x3f3f3f3f3f3f3f3f
#define INF 0x3f3f3f3f
#define PI 3.14159265
#define RAND (rand()*rand())
#define MAX(x, y) ((x) > (y) ? (x):(y)) 
#define MIN(x, y) ((x) > (y) ? (y):(x))
#define ABS(x) ((x) > 0 ? (x) : -(x))
#define CEIL(x, y) (((x) + (y) - 1)/(y))
using namespace std;
const int MAXN = 1e5 + 5;
const ll MOD = 1e9 + 7;
const double eps = 1e-7;
int N, M, K, Q, T;
char str[100];

int main()
{
	int i, j;
	scanf("%s", str + 1);
	if (str[3] == str[4] && str[5] == str[6])printf("Yes");
	else printf("No");
}

Measured memory_bytes: 256
#include<stdio.h>
#define MAX 100005
#define NIL -1

struct Node{ int p, l, r;};
struct Node T[MAX];
int n, H, D[MAX];

int getDepth(int u){
  int d = 0;
  for(; T[u].p != NIL ;d++) u = T[u].p;
  return d;
}

void print(int u){
  int i, c;
  printf("node %d: ", u);
  printf("parent = %d, ", T[u].p);
  printf("depth = %d, ", D[u]);

  if ( T[u].p == NIL ) printf("root, ");
  else if ( T[u].l == NIL ) printf("leaf, ");
  else printf("internal node, ");

  printf("[");
  for(i = 0, c = T[u].l; c != NIL; i++, c = T[c].r){
    if (i) printf(", ");
    printf("%d", c);
  }
  printf("]\n");
}

main(){
  int i, j, d, v, c, l;
  scanf("%d", &n);
  for ( i = 0; i < n; i++ ) T[i].p = T[i].l = T[i].r = NIL;

  for ( i = 0; i < n; i++ ){
    scanf("%d %d", &v, &d);
    for ( j = 0; j < d; j++ ){
      scanf("%d", &c);
      if ( j == 0 ) T[v].l = c;
      else T[l].r = c;
      l = c;
      T[c].p = v;
    }
  }
  
  H = 0;
  for ( i = 0; i < n; i++ ){
    D[i] = getDepth(i);
    if ( D[i] > H ) H = D[i];
  }

  for ( i = 0; i < n; i++ ) print(i);
  return 0;
}


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

#define REP(i, n ,N) for(ll i = (n); i < (N); i++)
#define RREP(i, n ,N) for(ll i = (N-1); i >= 0; i--)
#define p(s) cout<<(s)<<endl
#define p2(a, b) cout<<(a)<<" "<<(b)<<endl
using namespace std;
typedef long long ll;
ll mod = 1e9+7;
ll inf = 1e18;

ll N;
int main(){
	ll N;
	cin >> N;
	string ans="No";
	REP(i,1,10){
		REP(j,1,10){
			if(N==i*j){
				ans="Yes";
			}
		}
	}
	p(ans);
	return 0;
}

Measured memory_bytes: 256
#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() {
    string O, E;
    cin >> O >> E;
    string pass;
    rep(i,min(O.size(),E.size())) {
        pass.push_back(O.at(i));
        pass.push_back(E.at(i));
    }
    if (O.size() != E.size()) {
        pass.push_back(O.at(O.size() - 1));
    }
    cout << pass << endl;
}


Measured memory_bytes: 3636
#include <cstdio>

#define REP(i, n) for(int i = 0;i < n;i++)
#define REPR(i, n) for(int i = n;i >= 0;i--)
#define FOR(i, m, n) for(int i = m;i < n;i++)

int main() {
  int debt = 100000;
  int n;
  scanf("%d", &n);
  REP(i, n) {
    debt += debt * 0.05;
    if(debt%1000 != 0) {
      debt -= debt%1000;
      debt += 1000;
    }
  }
  printf("%d\n", debt);
  return 0;
}

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

const int MAX = 401;
const ll INF = 1001001001001001;

ll dp[MAX][MAX];
ll cum_sum[MAX];
ll a[MAX];

ll rec(int l,int r){
    if(dp[l][r]>0) {
        return dp[l][r];
    }

    if((r-l)==1) {
        dp[l][r] = 0;
        return dp[l][r];
    }

    if((r-l)==2) {
        dp[l][r] = cum_sum[r]-cum_sum[l];
        return dp[l][r];
    }

    ll res = INF;
    for(int i=l+1;i<r;++i){
        res = min(res,rec(l,i)+rec(i,r));
    }

    dp[l][r] = res + cum_sum[r]-cum_sum[l];
    return dp[l][r];

}

int main(){
    int n;
    cin >> n;
    ll res=0;
    cum_sum[0]=0;
    rep(i,n){
        cin >> a[i];
        cum_sum[i+1]=a[i]+cum_sum[i];
    }
    cout << rec(0,n) << endl;
}

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

int main(){
  
  int n;
  cin >> n;
  double ans;
  if(n%2)ans = (n+2-1)/2;
  else ans = n/2;
  
  cout << fixed << setprecision(10) << ans/(double)n << endl;
  return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
#include <algorithm>
#define rep(i,n) for(int i=0;i<(int)n;i++)
#define repp(i,r,n) for(int i=r;i<(int)n;i++)
using namespace std;
int in() {int x; cin >> x; return x;}

int main()
{
	int n;
	cin >> n;
	while (n--)
	{
		bool ans = true;
		int r = -1, l = -2;

		for (int i = 0; i < 10; i++)
		{
			int x;
			cin >> x;
			if (r < l)swap(r, l);

			if (l > x)
			{
				ans = false;
			}

			if(r < x)r=x;
			else l=x;


			if (r < l)swap(r, l);
		}


		if (ans)cout << "YES" << endl;
		else cout << "NO" << endl;
	}


	return 0;

}

Measured memory_bytes: 1152
N = int(input())
A = list(map(int,input().split()))
B1 = 0
B = []
for i in range(0,N):
    if i%2 == 0:
        B1 += A[i]
    else:
        B1 -= A[i]
B.append(B1)
XX = B1
for i in range (0,N-1) :
    X = 2*A[i]-XX
    B.append(X)
    XX = X
for i in range(0,N):
    print(B[i])
    





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

using ll = int64_t;

#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 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 = 1'000'000'000 + 7;
const int INF = 1'000'000'000 + 5;

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

	int n, t; std::cin >> n >> t;
	vector<pi> ab;
	rep(i, n){
		int a, b; std::cin >> a >> b;
		ab.eb(a, b);
	}
	sort(rng(ab));
	vi dp(t);
	int ans = 0;
	rep(i, n) {
		int a = ab[i].fi, b = ab[i].se;
		chmax(ans, dp[t-1] + b);
		drep(j, t) {
			if (j < a) continue;
			chmax(dp[j], dp[j-a] + b);
		}
	}
	std::cout << ans << "\n";
}


Measured memory_bytes: 384
#include <iostream>
#include<string>
using namespace std;
int main(int argc, char *argv[])
{
	string s;
	while(cin>>s){
		if(s[0]!='A')cout<<"WA"<<'\n';
		else {
			int sum2=0;
		    for(int i=2;i<s.length()-1;i++)
		      if(s[i]=='C')sum2++;
		     if(sum2==1){
		     	bool flag=true;
     			for(int i=1;i<s.length();i++)
     			  if(s[i]!='C'&&s[i]>='A'&&s[i]<='Z')flag=false;
     			if(flag)cout<<"AC"<<'\n';
				 else cout<<"WA"<<'\n';  
     		} 
     		else cout<<"WA"<<'\n';
		}
	}
	return 0;
}

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

// http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0522

int main() {
	string str;
	while (cin >> str) {
		int c1 = 0, c2 = 0;
		for (int i = 0; i < str.size() - 2; i++) {
			if (str[i] != 'J' && str[i] != 'I') continue;
			if (str[i + 1] != 'O') continue;
			if (str[i + 2] != 'I') continue;
			if (str[i] == 'J') c1++;
			else c2++;
		}
		cout << c1 << endl << c2 << endl;
	}
	return 0;
}

Measured memory_bytes: 1196
class Combination:
    """
    SIZEが10^6程度以下の二項係数を何回も呼び出したいときに使う
    使い方:
    comb = Combination(SIZE, MOD)
    comb(10, 3) => 120
    """

    def __init__(self, N, MOD=10 ** 9 + 7):
        self.MOD = MOD
        self.fact, self.inv = self._make_factorial_list(N)

    def __call__(self, n, k):
        if k < 0 or k > n:
            return 0
        res = self.fact[n] * self.inv[k] % self.MOD
        res = res * self.inv[n - k] % self.MOD
        return res

    def _make_factorial_list(self, N):
        fact = [1] * (N + 1)
        inv = [1] * (N + 1)
        MOD = self.MOD
        for i in range(1, N + 1):
            fact[i] = (fact[i - 1] * i) % MOD
        inv[N] = pow(fact[N], MOD - 2, MOD)
        for i in range(N, 0, -1):
            inv[i - 1] = (inv[i] * i) % MOD
        return fact, inv


if __name__ == "__main__":
    H, W, A, B = map(int, input().split())
    mod = 10**9+7
    comb = Combination(2*10**5+10, mod)

    ans = 0
    h1 = H - A
    w1 = B + 1
    while True:
        X = comb(h1 + w1 - 2, h1 - 1)
        h2 = H - h1
        w2 = W - w1
        Y = comb(h2 + w2, h2)
        ans += X * Y % mod
        ans %= mod

        h1 -= 1
        w1 += 1
        if h1 <= 0 or w1 > W:
            break

    print(ans)


Measured memory_bytes: 18804
#include<iostream>
using namespace std;
int main(){
    int a,b,c;
    int d;
    int e,f,g;
    cin>>a>>b>>c>>d;
    e=c-a;
    f=c-b;
    g=b-a;
    if(e<0){e=-e;}
    if(f<0){f=-f;}
    if(g<0){g=-g;}
    if(e<=d){
        cout<<"Yes"<<endl;
    }
    else{
        if(f<=d && g<=d){
            cout<<"Yes"<<endl;
        }
        else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 256
s = list(input())
for i in range(len(s)):
    if s[i] == "B":
        s[i] = 1
    elif s[i] == "W":
        s[i] = 0
cnt = 0
for i in range(len(s)-1): 
    if abs(s[i+1] - s[i]) == 1:
        cnt += 1
print(cnt)

Measured memory_bytes: 3956
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;

ll inf=-1e18;

int main() {
  ll n;
  cin >> n;
  priority_queue<ll> a;
  priority_queue<ll> b;
  vector<ll> v(3*n);
  for(ll i=0;i<3*n;i++) {
    cin >> v[i];
  }
  vector<ll> sa(n+1);
  vector<ll> sb(n+1);
  for(int i=0;i<2*n;i++) {
    if(i<n) {
      sa[0]+=v[i];
    }
    a.push(-v[i]);
    if(i>=n) {
      sa[i-n+1]=sa[i-n]+v[i]+a.top();
      a.pop();
    }
  }
  for(int i=2*n-1;i>-1;i--) {
    if(i>n-1) {
      sb[n]+=v[i+n];
    }
    b.push(v[i+n]);
    if(i<n) {
      sb[i]=sb[i+1]+v[i+n]-b.top();
      b.pop();
    }
  }
  ll ans=inf;
  for(int i=0;i<=n;i++) {
    ans=max(ans,sa[i]-sb[i]);
  }
  cout << ans << endl;
}

Measured memory_bytes: 6516
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); i++)
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;




int main()
{
    
    int N;
    cin >> N;
    vector<pair<int, int> > A(N);
    
    rep(i,N){
        cin >> A[i].first;
        A[i].second = i+1;
    
    }
    
    sort(A.begin(), A.end());
    
    rep(i, N) cout << A[i].second << " ";
    cout << endl;
    return 0;
}


Measured memory_bytes: 1536
#include<bits/stdc++.h>
using namespace std;
typedef vector<int>vi;
typedef map<int,int>mp;
int main(){
int N;
cin>>N;
vi A,a;
for(int i=0;i<N;i++){
    int num;
    cin>>num;
    A.push_back(num);
    a.push_back(num);
}
mp m;
sort(A.begin(),A.end());
for(int i=0;i<N-1;i++){
    m[A[i]]=A[N-1];
}
m[A[N-1]]=A[N-2];
for(int i=0;i<N;i++){
    cout<<m[a[i]]<<endl;
}

return 0;
}


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

int charToInt(char c){
    char zero_num = '0';
    return (int)c - (int)zero_num;
}

signed main(){
     int N,X,T;
     cin>>N>>X>>T;
     if(N%X==0){
         cout<<N/X*T<<endl;
     }else{
         cout<<(N/X+1)*T<<endl;
     }


    return 0;
}

Measured memory_bytes: 3564
A, B, C, X, Y = map(int, input().split( ))
direct = A*X + B*Y
if X < Y:
    rearrange = C*2*X+B*(Y-X)
else:
    rearrange = C*2*Y+A*(X-Y)
combi = C*2*max(X,Y)
print(min(direct, rearrange, combi))

Measured memory_bytes: 3060
N, M, K = map(int, input().split())
MOD = 10 ** 9 + 7

P = 200005
fact = [0] * P
fact[0] = 1
for i in range(1, P):
    fact[i] = fact[i - 1] * i
    fact[i] %= MOD

rfact = [0] * P
rfact[P - 1] = pow(fact[P - 1], MOD - 2, MOD)
for i in range(P - 2, -1, -1):
    rfact[i] = rfact[i + 1] * (i + 1)
    rfact[i] %= MOD


def comb(n, k):
    return fact[n] * rfact[k] * rfact[n - k] % MOD


num = 0
for d in range(1, N):
    num += d * (N - d) * (M ** 2)
    num %= MOD

for d in range(1, M):
    num += d * (M - d) * (N ** 2)
    num %= MOD

num *= comb(N * M - 2, K - 2)
print(num % MOD)


Measured memory_bytes: 18804
#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;

int main() {
  int k, s;
  cin >> k >> s;
  int counter = 0;

  for(int i = 0; i <= k; ++i) {
    for(int j = 0; j <= k; ++j) {
      int z = s - i - j;
      if(z >= 0 && z <= k) {
        ++counter;
      }
    }
  }

  cout << counter;
  return 0;
}


Measured memory_bytes: 256
n, cost = int(input()), 0
num = list(map(int, input().split()))
num_s = sorted(num)
n0 = num_s[0]

for i in range(n - 1):
    ni, tmp, cnt = num_s[i], 0, 0
    si = num.index(ni)
    while si != i:
        nsi = num_s[si]
        sj = num.index(nsi)
        num[si], num[sj] = nsi, ni
        tmp += ni + nsi
        cnt += 1
        si = sj
    if cnt:
        cost += min(tmp, (ni + n0) * 2 + tmp - (ni - n0) * cnt)
print(cost)

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

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

    int counter = 0;
    int max = 0;
    for(int i = 0; i < S.size(); i++){
        if(S[i] == 'A' || S[i] == 'C' || S[i] == 'G' || S[i] == 'T'){
                    counter++;
                    if(counter >= max)
                        max = counter;
                }else{
                    counter = 0;
                }
        }
    

    cout << max << endl;

    return 0;
}

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

int main() {
	ll n, a, b, c, resul=0;
	cin >> n >> a >> b;
	c = a + b;
	/*if (c == 0) {
		resul = 0;
	}
	else {*/
		resul += a * (ll)(n / c);
		resul += min(n % c, a);
	//}
	cout << resul << endl;
	return 0;
}

Measured memory_bytes: 256
# -*- coding: utf-8 -*-
n, a, b = map(int, input().split())

diff = abs(b-a)
result = 0
if diff % 2 == 0:
    result = diff // 2
else:
    if a < (n-b+1):
        n_a = 1
        n_b = b - a
        result = a
        tmp = (n_b-1)//2
        result += tmp
    else:
        n_a = a + n - b + 1
        n_b = n
        result = n-b+1
        tmp = (n-n_a)//2
        result += tmp

print(result)


Measured memory_bytes: 38256
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<queue>
#include<unordered_map>
#include<map>
using namespace std;

map<string, int>mp;
int s[55];
int main() {
	int n;
	cin >> n;
	string a;
	int b;
	s[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a;
		cin >> b;
		mp[a] = i;
		s[i] = s[i - 1] + b;
	}
	string ss;
	cin >> ss;
	cout << s[n] - s[mp[ss]] << endl;
	return 0;
}


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


int main() {

    int N,L;
    cin>>N>>L;


    int taste_sum=0;
    int taste_min=2000;
    for(int i=1;i<=N;i++){
      int wk=L+i-1;
      taste_sum+=wk;
      if(abs(wk)<abs(taste_min)){
        taste_min = wk;
      }
    }

    cout<<taste_sum-taste_min<<endl;
    
    return 0;
}

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

typedef pair<int, int> Pair;

int N;
int M;
int C[1145141];
int cnt[1145141];
int ans[1145141];
int order[1145141];
map<Pair, int> dup;

bool cmp(int a, int b) {
  return cnt[a] < cnt[b];
}

void calc(int t, int *C, int N) {
  dup.clear();
  fill(cnt, cnt+M, 0);
  if (t) {
    cnt[C[0]]--;
    dup[Pair(C[0], C[0])]++;
    C++;
    N--;
  }
  
  for (int i=0; i<N/2; i++) {
    cnt[C[i*2]]--;
    cnt[C[i*2+1]]--;
    dup[Pair(C[i*2], C[i*2+1])]++;
    dup[Pair(C[i*2+1], C[i*2])]++;
    if (C[i*2] != C[i*2+1]) {
      dup[Pair(C[i*2], C[i*2])]++;
      dup[Pair(C[i*2+1], C[i*2+1])]++;
    }
  }
  
  if (N%2 == 1) {
    cnt[C[N-1]]--;
    dup[Pair(C[N-1], C[N-1])]++;
  }

  for (int i=0; i<M; i++) {
    order[i] = i;
  }
  sort(order, order+M, cmp);

  if (t) N++;
  for (int i=0; i<M; i++) {
    int a = order[i];;
    for (int j=0; j<M; j++) {
      int b = order[j];
      int d = dup[Pair(a, b)];
      ans[a] = min(ans[a], N+cnt[a]+cnt[b]+d);
      if (!d) break;
    }
  }
}

int main() {
  scanf("%d%d", &N, &M);
  for (int i=0; i<N; i++) {
    scanf("%d", &C[i]);
    C[i]--;
  }
  fill(ans, ans+M, N);

  calc(0, C, N);
  calc(1, C, N);
  for (int i=0; i<M; i++) {
    printf("%d\n", ans[i]);
  }
}

Measured memory_bytes: 206292
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <regex>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <valarray>
#include <vector>
using namespace std;

using ll = long long;
using ld = long double;
const int INF = 1e9;
const double EPS = 1e9;
const ll MOD = 1e9 + 7;

int main()
{
  long long N;
  scanf("%lld", &N);
  long long M;
  scanf("%lld", &M);
  vector<pair<ll, ll>> v(N);
  for (int i = 0; i < N; i++)
  {
    cin >> v[i].first >> v[i].second;
  }
  sort(v.begin(), v.end());
  ll ans = 0;
  for (int i = 0; i < N; ++i)
  {
    if (M >= v[i].second)
    {
      ans += v[i].first * v[i].second;
      M -= v[i].second;
    }
    else
    {
      ans += v[i].first * M;
      break;
    }
  }
  cout << ans << endl;

  return 0;
}


Measured memory_bytes: 1792
n, h = gets.split.map(&:to_i)

count = 0
katanas = []
n.times { katanas << gets.split.map(&:to_i) }

attack = katanas.sort{|a, b| b[0] <=> a[0]}.first[0]

katanas.sort{|a, b|b[1]<=>a[1]}.each do |k|
  if k[1] > attack && h > 0
    h -= k[1]
    count += 1
  end
end

if h > 0
  count += h / attack
  count += (h % attack == 0) ? 0 : 1
end

puts count

Measured memory_bytes: 11888
use proconio::input;
fn main() {
    input!{
        n: u64,
    };
    let mut t = n;
    let mut cs =  String::new(); //chars
    while t > 0 {
        t = t - 1;
        let idx = ('a' as u8 + (t % 26) as u8) as char;
        cs.push(idx);
        t = t / 26;
    }
    print!("{}", cs.chars().rev().collect::<String>());
}

Measured memory_bytes: 2164
import java.util.Scanner;

public class Main {

	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		locateTresure();
	}

	private static void locateTresure() {
		double x = 0;
		double y = 0;
		int angle = 0;

		do {

			String input = sc.nextLine();
			if (input.equals("0,0")) {
				break;
			}

			String[] dt = input.split(",");

			int d = Integer.parseInt(dt[0]);
			int a = Integer.parseInt(dt[1]);

			x += d * Math.sin( Math.toRadians(angle) );
			y += d * Math.cos( Math.toRadians(angle) );

			angle += a;

		}while(true);

		System.out.printf("%d\n%d\n", (int)x, (int)y);



	}

}


Measured memory_bytes: 26172
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); i++)
#define sz(x) int(x.size())
using namespace std;
typedef long long ll;
const int inf = 1001001001;

int main(){
  ll a,b,c,d;
  cin >> a >> b >> c >> d;

  ll ans;
  ll A = a*c;
  ll B = a*d;
  ll C = b*c;
  ll D = b*d;

  ans = max(max(A,B), max(C,D));
  cout << ans << endl;
}


Measured memory_bytes: 3620
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200


int main(){
	char a[N][11];
	f(i, N){
		f(j, 11)a[i][j] = 0;
	}
	int n, k, x;
	bool v = true;
	scanf("%d", &n);
	f(i, n){
		scanf("%s", a[i]);
	}
	f(i, n){
		for (int j = i + 1; j < n; j++){
			k = 0;
			f(ii, 11){
				if (a[i][ii] == a[j][ii])k++;
			}
			if (k == 11)v = false;
		}
	}
	f(i, n - 1){
		x = strlen(a[i]);
		if (a[i][x - 1] != a[i + 1][0])v = false;
	}

	if (v)printf("Yes\n");
	else printf("No\n");


	return 0;
}

Measured memory_bytes: 128