akhauriyash/Code-Regression huggingface dataset:
#最小全域木問題、プリム法
from heapq import *
def solve():
    N = int(input())
    A = [list(map(int, input().split()))+[i] for i in range(N)]
    edge = [[] for _ in range(N)]
    A.sort()
    for i in range(N-1):
        w = A[i+1][0]-A[i][0]
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    A.sort(key=lambda x:x[1])
    for i in range(N-1):
        w = A[i+1][1]-A[i][1]
        edge[A[i][2]].append((w,A[i+1][2]))
        edge[A[i+1][2]].append((w,A[i][2]))
    bridges = []
    heapify(bridges)
    used = [False]*N
    used[0] = True
    ans = 0
    for w,v in edge[0]:
        heappush(bridges,(w,v))
    while len(bridges)>0:
        w,v = heappop(bridges)
        if used[v]==False:
            ans += w
            used[v] = True
            for w,u in edge[v]:
                if used[u]==False:
                    heappush(bridges,(w,u))
    return ans
print(solve())

Measured memory_bytes: 74308
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rng(i, a, b) for (int i = int(a); i < int(b); i++)
#define rep(i, b) rng(i, 0, b)
#define gnr(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define per(i, b) gnr(i, 0, b)
#define bg begin()
#define ed end()
#define all(x) x.bg, x.ed
#define vi vector<int>
template <class t, class u>
bool chmax(t &a, u b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
template <class t, class u>
bool chmin(t &a, u b)
{
    if (b < a)
    {
        a = b;
        return true;
    }
    return false;
}

int main()
{
    ll n, a, b;
    cin >> n >> a >> b;
    if (n == 1 && a != b)
    {
        cout << 0 << endl;
    }
    else if (n == 1)
    {
        cout << 1 << endl;
    }
    else
    {
        if (a > b)
        {
            cout << 0 << endl;
        }
        else
        {
            cout << (b * (n - 1) + a) - (a * (n - 1) + b) + 1 << endl;
        }
    }
    return 0;
}

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

#define CEIL(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))

using namespace std;
using ll = long long;
using pii = pair<int, int>;

constexpr int MOD = 1'000'000'007;
constexpr int INF = 1'000'000'001;
constexpr ll LLINF = 4'000'000'000'000'000'001;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(10);
    int n;
    cin >> n;
    vector<int> h(n);
    for(int i = 0; i < n; ++i){
        cin >> h[i];
    }
    for(int i = n - 1 - 1; i >= 0; --i){
        if(h[i+1] >= h[i]) continue;
        if(h[i+1] + 1 == h[i]) --h[i];
        else {
            cout << "No\n";
            return 0;
        }
    }
    cout << "Yes\n";
    return 0;
}

Measured memory_bytes: 640
#include <iostream>
 
using namespace std;
 
 
int main(){
  int n;
  cin >> n;
  if(n%2==0){
    cout << n/2*n/2;
    return 0;
  }else{
    cout << (n-1)/2*(n+1)/2;
    return 0;
  }
  return -1;
}

Measured memory_bytes: 256
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <iostream>
#include <functional>
#include <bitset>
#include <algorithm>
#include <vector>
#include <forward_list>
#include <set>
#include <map>
#include <queue>
#include <deque>
#include <stack>
#include <tuple>
#include <numeric>
#define rep(i, s, g) for ((i) = (s); (i) < (g); ++(i))
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
const ll MOD = 1e9 + 7;
const ll INF = (1ll << 60);

int main(void)
{
    int n, m, k, a;
    map<ll, ll> res;
    ll ans = 0;

    cin >> n >> m;

    for (int i = 0; i < n; i++)
    {
        cin >> k;

        for (int j = 0; j < k; j++)
        {
            cin >> a;
            res[a]++;
        }
    }

    for (auto x : res)
    {
        if (x.second == n)
        {
            ans++;
        }
    }

    cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
int main(){
    string s,ans;
    cin >> s;
    int n = s.size();
    REP(i,n){
        if(s[i] == '0' || s[i] == '1')ans += s[i];
        else if(ans.size() > 0) ans.pop_back();
    }
    cout << ans << endl;
}

Measured memory_bytes: 256
function Main(input) {
	input = input.split("\n");
	var st = input[0].split(" ");
	var st1 = st[0];
	var st2 = st[1];
	var num = input[1].split(" ");
	var a = parseInt(num[0], 10);
	var b = parseInt(num[1], 10);
	var st3 = input[2];
	if(st3 == st1){
      a--;
    }else{
      b--;
    }
	console.log(a+' '+b);
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 21064
//#include<iostream>
//#include<algorithm>
//#include<string>
//#include <cmath>
//#include <vector>
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define REP(x,n) for(int x=0;x<n;x++)

//vector//
#define vei vector<int> 
#define velli vector<long long int> 
#define pb(x) push_back(x) // 末尾にxを加える
#define pb2 pop_back() // 末尾削除
#define all(x) (x).begin(),(x).end() //イテレーター
#define be(x) (x).begin()
//auto  auto begin = v.begin()とか

typedef pair<int,int> P;  //q(p.first,p.second)

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

    int tai1 = a;
    int tai2 = c;
    while(1){
        tai2 -= b;
        if(tai2<=0){
            cout << "Yes";
            break;
        }
        
        tai1 -= d;
        if(tai1<=0){
            cout << "No";
            break;
        }
    }
}

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

using namespace std;

string str;

int min(int p, int q){
	if( p > q ) return q;
	return p;
}
int main(void){

	int dp[2][2][9][9];

	while( 1 ) {
		str = "";
		cin >> str;
		if( str == "#" ) break;
		int arrow = str[0] - '1';

		for(int i = 0; i < 2; i++)
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					for(int l = 0; l < 2; l++)
						dp[l][i][j][k] = 1 << 30;

			for(int j = 0; j < 9; j++) { 
				dp[1][1][j][arrow] = 0;
				dp[1][0][arrow][j] = 0;
			}

		for(int i = 1; i < str.length(); i++) {
			arrow = str[i] - '1';

			for(int j = 0; j < 2; j++)
				for(int k = 0; k < 9; k++)
					for(int l = 0; l < 9; l++) {
						dp[0][j][k][l] = dp[1][j][k][l];
						dp[1][j][k][l] = 1 << 30;
					}
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++) {
					if( arrow % 3 <= k % 3 && j != k && j % 3 <= k % 3 && arrow != k )
						dp[1][0][arrow][k] = min( dp[0][0][j][k] + 1, dp[1][0][arrow][k] );
					if( arrow % 3 >= j % 3 && j != k && j % 3 <= k % 3 && arrow != j )
						dp[1][1][j][arrow] = min( dp[0][1][j][k] + 1, dp[1][1][j][arrow] );
					if( arrow % 3 <= k % 3 && j != k && j % 3 <= k % 3 && arrow != k )
						dp[1][0][arrow][k] = min( dp[0][1][j][k], dp[1][0][arrow][k] );
					if( arrow % 3 >= j % 3 && j != k && j % 3 <= k % 3 && arrow != j )
						dp[1][1][j][arrow] = min( dp[0][0][j][k], dp[1][1][j][arrow] );
				}	
		}

		int min = 1 << 30;

 		for(int i = 0; i < 2; i++)  
			for(int j = 0; j < 9; j++)
				for(int k = 0; k < 9; k++)
					if(min > dp[1][i][j][k] ) min = dp[1][i][j][k];

		cout << min << endl;
	}
	return 0;
}

Measured memory_bytes: 1316
#include<iostream>
using namespace std;
long a,b,c,d,n;
main()
{
	cin>>n>>a>>b>>c>>d;
	for(int i=0;i<n;i++)
	{
		long f=-d*i+c*(n-1-i),l=-c*i+d*(n-1-i);
		if(f<=a-b&&a-b<=l)
		{
			cout<<"YES"<<endl;
			return 0;
		}
	}
	cout<<"NO"<<endl;
}

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

ll n, k, c, x, y;

ll a[300005];

int main()
{
	scanf("%lld%lld",&n,&k);
	if(n % 2 == 0) {
		printf("%lld ",n/2);
		for(ll i=1;i<k;i++) printf("%lld ",n);
		puts(""); return 0;
	}
	for(x=1,y=k/2;y>0;x=x*n+1,c++) {
		a[c] = n/2+1;
		while(a[c] && y > 0) {
			a[c]--;
			ll V = (a[c] ? x : 1);
			y -= V;
		}
	}
	for(ll i=c;i--;) {
		x=(x-1)/n;
		while(true) {
			ll V = (a[i] ? x : 1);
			if(y + V > 0) break;
			y += V; a[i]++;
		}
	}
	for(ll i=c;i<k;i++) printf("%lld ",n/2+1);
	for(ll i=c;i--;) {
		if(!a[i]) break;
		printf("%lld ",a[i]);
	}
	puts("");
}


Measured memory_bytes: 2304
#include<iostream>
#include<iomanip>
#include<cassert>
#include<math.h>
#include<complex>
#include<algorithm>
#include<utility>
#include<queue>
#include<string.h>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<functional>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
const ll INF=2e18;
const ll MOD=1e9+7;

ll N;
ll a[300010];
priority_queue<ll,vector<ll>,greater<ll>> leftQ;
priority_queue<ll> rightQ;
ll leftSum[300010];
ll rightSum[300010];
int main(){
    cin>>N;
    for(ll i=0;i<3*N;i++){
        cin>>a[i];
    }
    leftSum[N-1]=0;
    for(ll i=0;i<N;i++){
        leftSum[N-1]+=a[i];
        leftQ.push(a[i]);
    }
    for(ll i=N;i<2*N;i++){
        leftSum[i]=a[i]+leftSum[i-1];
        leftQ.push(a[i]);
        leftSum[i]-=leftQ.top();
        leftQ.pop();
    }

    rightSum[2*N]=0;
    for(ll i=3*N-1;i>=2*N;i--){
        rightSum[2*N]+=a[i];
        rightQ.push(a[i]);
    }
    for(ll i=2*N-1;i>=N;i--){
        rightSum[i]=a[i]+rightSum[i+1];
        rightQ.push(a[i]);
        rightSum[i]-=rightQ.top();
        rightQ.pop();
    }


    ll ans=-INF;
    for(ll i=N-1;i<2*N;i++){
        ans=max(ans,leftSum[i]-rightSum[i+1]);
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 7668
def sort1(A):
    for i in range(0, len(A)-1):
        select_min(A,i)
    return A

def select_min(A,i):
    min = i
    for j in range(i+1, len(A)):
        if A[min][0] == A[j][0]:
            if A[min][1] < A[j][1]:
                min = j
    A[i], A[min] = A[min], A[i]

N = int(input())
SPlist = []
for i in range(N):
    S, P =  input().split(" ")
    au = [S, int(P), i+1]
    SPlist.append(au)
SPlist.sort()

SPlist = sort1(SPlist)
        
for u in range(N):
    print(SPlist[u][2])


Measured memory_bytes: 3064
#include<iostream>
#include<string>
#include<sstream>
#include<algorithm>
#include<vector>
#include<iomanip>
#include<cmath>
#include<complex>
#include<queue>
#include<deque>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<functional>
#include<numeric>
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
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)
using ll = long long;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;
const ll mod=1e9+7 ;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};

// int a[(int)1e9+1]; //配列ではこんなにメモリ確保できない

int main()
{
    int n;
    cin >> n;
    vector<ll> x;
    for (int i=0; i<n; ++i)
    {
        ll tmp;
        cin >> tmp;
        x.push_back(tmp);
    }

    sort(x.begin(), x.end());
    double max = x.back();
    ll r = 0;
    double dif = 1e9;
    for (int i=0; i<n-1; ++i)
    {
        if(dif>abs(x[i]-max/2))
        {
            dif = abs(x[i]-max/2);
            r = x[i];
        }
        // else//更新されなくなったら
        // {
        //     break;
        // }
    }
    // double型のままだと，WA
    cout << (ll)max << " " << (ll)r << endl;
    return 0;
}

Measured memory_bytes: 1400
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define fastio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define  mp make_pair
#define pb push_back
void findAns()
{
    int n;
    cin >> n;

    int data[n][3];
    for (int i = 0; i < n; i++) for (int j = 0; j < 3; j++) cin >> data[i][j];

    int dp[n][3] = {0};

    dp[0][0] = data[0][0];
    dp[0][1] = data[0][1];
    dp[0][2] = data[0][2];

    for (int i = 1; i < n; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            if (j == 2)
                dp[i][j] = data[i][j] + max(dp[i - 1][0], dp[i - 1][1]);
            else if (j == 1)
                dp[i][j] = data[i][j] + max(dp[i - 1][0], dp[i - 1][2]);
            else
                dp[i][j] = data[i][j] + max(dp[i - 1][1], dp[i - 1][2]);

            //out << dp[i][j] << " ";
        }
        // cout << "\n";
    }
    cout << max(dp[n - 1][2], max(dp[n - 1][1], dp[n - 1][0]));
    return;
}
int main()
{
// #ifndef ONLINE_JUDGE
//     freopen("input.txt", "r", stdin);
//     freopen("output.txt", "w", stdout);
// #endif
    fastio;
    // ll int t;
    // cin >> t;

    // while (t--)
    findAns();

    return 0;
}

Measured memory_bytes: 2560
n = int(input())
mod = 10 ** 9 + 7

fact = [1] * (n + 1)
revfact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = ((i + 1) * fact[i]) % mod
revfact[n] = pow(fact[n], mod - 2, mod)
for i in reversed(range(n)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod

def combination(n, k, p):
    return (fact[n] * revfact[k] * revfact[n - k]) % p

ans = 0
for i in range(1, n // 3 + 1):
    ans += combination(n - i * 2 - 1, i - 1, mod)
    ans %= mod
print(ans)

Measured memory_bytes: 9160
n=int(input())
a=sorted(list(map(int,input().split())))

def calc(lis,m):
    res=0
    for i in range(len(lis)):
        res+=(lis[i]-m)**2
    return res
  
mi=calc(a,a[0])
for i in range(a[0]+1,a[-1]+1):
    tmp=calc(a,i)
    if tmp<mi: mi=tmp
print(mi)

Measured memory_bytes: 38512
#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i,n) for(int i=0;i<(n);++i)
#define all(a) (a).begin(),(a).end()
#define dunk(a) cout << (a) << endl
using namespace std;
typedef long long ll;

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

	if ((a + b - c) * (a + b - c) > 4 * a * b && a + b - c < 0) dunk("Yes");
	else dunk("No");

	return 0;
}


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

using namespace std;
using ll =long long;
typedef pair<int,int> P;
#define SORT(a) sort((a).begin(),(a).end())
#define REV(a) reverse((a).begin(),(a).end())
#define For(i, a, b)    for(int i = (a) ; i < (b) ; ++i)
#define rep(i, n)       For(i, 0, n)
#define debug(x)  cerr << #x << " = " << (x) << endl;
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

void coY() {cout <<"Yes"<<endl;}
void coN(){cout <<"No"<<endl;}
 
//Write From this Line

//const ll mod = 1e9+7;
//const ll mod = 998244353;
int main()
{
	string s;
	cin >> s;
	int ans = 0;
	int con = 0;
	rep(i,3){
		if(s[i] == 'R'){
			con++;
			ans = max(ans,con);
		} else {
			con = 0;
		}
	}
	cout << ans << endl;
}


Measured memory_bytes: 3600
#include <bits/stdc++.h>
using namespace std;
const int N = 100005;

int n;
char a[N];

int main()
{
    cin >> a;
    n = strlen(a);
    int ans1 = 0;
    int ans2 = 0;
    for (int i = 0; i < n; ++i)
    {
        if (i % 2 == 0 && a[i] == '1')
            ++ans1;
        if (i % 2 == 1 && a[i] == '0')
            ++ans1;
        if (i % 2 == 0 && a[i] == '0')
            ++ans2;
        if (i % 2 == 1 && a[i] == '1')
            ++ans2;
    }
    cout << min(ans1, ans2) << endl;
    return 0;
}


Measured memory_bytes: 384
#include <stdlib.h>
#include <stdio.h>
#define MAX_SIZE 40
#define SENTINEL -1
typedef struct { int left, right; } node;

static int build(node *nodes, int *pre, int *in, int left, int right) {
  int i, m;

  if (right - left == 1) return in[left];
  if (left == right) return SENTINEL;
  for (i = m = left; i < right; ++i) {
    if (in[i] == *pre) {
      m = i; break;
    }
  }
  nodes[*pre].left = build(nodes, pre + 1, in, left, m);
  nodes[*pre].right = build(nodes, pre + (m - left + 1), in, m + 1, right);
  return *pre;
}

static int postorder(const node *nodes, int id, int is_first) {
  if (id < 1 || id > 40) return is_first; // FIXME: WTF
  is_first = postorder(nodes, nodes[id].left, is_first);
  is_first = postorder(nodes, nodes[id].right, is_first);
  if (!is_first) printf(" ");
  printf("%d", id);
  return 0;
}

int main(int argc, char **argv) {
  int n, i, root, pre[MAX_SIZE], in[MAX_SIZE];
  node nodes[MAX_SIZE];

  scanf("%d", &n);
  for (i = 0; i < MAX_SIZE; ++i) pre[i] = in[i] = nodes[i].left = nodes[i].right = SENTINEL;
  for (i = 0; i < n; ++i) scanf("%d", &pre[i]);
  for (i = 0; i < n; ++i) scanf("%d", &in[i]);
  root = build(nodes, pre, in, 0, n);
  postorder(nodes, root, 1); printf("\n");
  exit(0);
}


Measured memory_bytes: 2108
N = list(map(int, str(input())))
K = int(input())

flag = 1
i = -1

while (flag == 1) : 
    i += 1
    
    if N[i] == 1 : 
        if K > 1 : 
           K = K -1
        else : 
            print(1)
            flag = 0
    else : 
        print(N[i])
        flag = 0

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

int main(){
int a[100][100], b[100], n;
for(int i = 1;i <= 3;i++){
for(int j = 1;j <= 3;j++){
cin >> a[i][j];
}
}
cin >> n;
for(int k = 0;k < n;k++){
cin >> b[k];
}
for(int k = 0;k < n;k++){
for(int i = 1;i < 4;i++){
for(int j = 1;j < 4;j++){
if(a[i][j] == b[k]){
a[i][j] = 1000;
}
}
}
}
if(a[1][1] == 1000 && a[2][1] == 1000 && a[3][1] == 1000){
cout << "Yes";
}
else if(a[1][2] == 1000 &&  a[2][2] == 1000 && a[3][2] == 1000){
cout << "Yes";
}
else if(a[1][3] == 1000 && a[2][3] == 1000 && a[3][3] == 1000){
cout << "Yes";
}
else if(a[1][1] == 1000 && a[1][2] == 1000 && a[1][3] == 1000){
cout << "Yes";
}
else if(a[2][1] == 1000 && a[2][2] == 1000 && a[2][3] == 1000){
cout << "Yes";
}
else if(a[3][1] == 1000 && a[3][2] == 1000 && a[3][3] == 1000){
cout << "Yes";
}
else if(a[1][1] == 1000 && a[2][2] == 1000 && a[3][3] == 1000){
cout << "Yes";
}
else if(a[3][1] == 1000 && a[2][2] == 1000 && a[1][3] == 1000){
cout << "Yes";
}
else{
cout << "No";
}
}

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

int main(){
  cin.tie(nullptr);
  ios_base::sync_with_stdio(false);
  int N, Q;
  cin >> N >> Q;
  dsu d(N);
  while(Q--){
    int t, u, v;
    cin >> t >> u >> v;
    if(t == 1)cout << d.same(u, v) << '\n';
    else d.merge(u, v);
  }
  return 0;
}

Measured memory_bytes: 3960
#include <bits/stdc++.h>
using namespace std;
int n,t,a[100003];
int max1,max2,ans;
int main() {
	scanf("%d%d",&n,&t);
	for(int i=1;i<=n;++i) scanf("%d",a+i);
	for(int i=n;i>=1;--i) {
		max1=max(max1,a[i]);
		a[i]=max1-a[i];
		max2=max(max2,a[i]);
	}
	for(int i=1;i<=n;++i) if (a[i]==max2) ans++;
	printf("%d\n",ans);
    return 0;
}

Measured memory_bytes: 640
import sys

blank = [i for i in range(64)]
nump = int(sys.stdin.readline())
qpos = []
for _ in range(nump):
    j, i = map(int, sys.stdin.readline().split())
    qpos.append([j*8+i, j-i, j+i])
    for x in range(8):
        if j*8+x in blank: blank.remove(j*8+x)
        if x*8+i in blank: blank.remove(x*8+i)
        if 8*(j-i+x)+x in blank: blank.remove(8*(j-i+x)+x)
        if 8*(j+i-x)+x in blank: blank.remove(8*(j+i-x)+x)

idx = [0] * (8-nump)
used = [False] * len(blank)

def combination(n, k, m=0):
  if m==k:
    board = ['.'] * 64
    for qp, _, _ in qpos:  board[qp] = 'Q'
    for i in range(8):  print(''.join(board[i*8:i*8+8]))
  else:
    for i in range(n):
      if m>0 and idx[m-1]<i:  continue
      if used[i]: continue
      idx[m] = i
      q = blank[i]

      x,y = q%8, q//8
      for p, b, c in qpos:
          if x==p%8 or y==p//8: break
          if y==x+b or y==-x+c: break
      else:
          used[i]=True
          qpos.append([q, y-x, y+x])
          combination(n, k, m+1)
          qpos.pop()
          used[i]=False


combination(len(blank), 8-nump)


Measured memory_bytes: 5624
package main

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

func main() {
	scanner := Scanner()
	h := ReadInt(scanner)
	w := ReadInt(scanner)
	k := ReadInt(scanner)

	board := make([][]string, h)
	for i := range board {
		board[i] = make([]string, w)
	}

	for i := 0; i < h; i++ {
		row := ReadString(scanner)
		for j, v := range row {
			board[i][j] = string(v)
		}
	}

	// fmt.Println(strconv.FormatInt(1<<h, 2), strconv.FormatInt(1<<w, 2))

	answer := 0

	for i := 0; i < (1 << h); i++ {
		for j := 0; j < (1 << w); j++ {
			count := 0
			for l := 0; l < h; l++ {
				for m := 0; m < w; m++ {
					// fmt.Println(strconv.FormatInt(int64(i), 2), strconv.FormatInt(int64(j), 2), strconv.FormatInt(int64(i>>l)&1, 2), strconv.FormatInt(int64(j>>m)&1, 2))

					if (i>>l)&1 == 1 {
						continue
					}
					if (j>>m)&1 == 1 {
						continue
					}
					if board[l][m] == string('#') {
						count++
					}
				}
			}
			// fmt.Println(count)
			if count == k {
				answer++
			}
		}
	}
	fmt.Println(answer)
}

func Scanner() *bufio.Scanner {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	return scanner
}

func ReadInt(scanner *bufio.Scanner) int {
	var t string

	if scanner.Scan() {
		t = scanner.Text()
	}

	n, err := strconv.Atoi(t)
	if err != nil {
		log.Fatal(err)
	}

	return n
}

func ReadString(scanner *bufio.Scanner) string {
	var t string

	if scanner.Scan() {
		t = scanner.Text()
	}

	return t
}


Measured memory_bytes: 1836
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <cmath>
const double eps = 1e-8;
const double pi = acos(-1);

struct Point {
    double x, y;
    Point() {}
    Point(double _x, double _y) : x(_x), y(_y) { }

    bool operator == (const Point &r) const {
        return fabs(x - r.x) < eps && fabs(y - r.y) < eps;
    }

    Point operator + (const Point &r) const {
        return Point(x + r.x, y + r.y);
    }

    Point operator * (const double &k) const {
        return Point(x * k, y * k);
    }

    Point operator / (const double &k) const {
        return Point(x / k, y / k);
    }

    Point operator - (const Point &r) const {
        return Point(x - r.x, y - r.y);
    }

    // 叉积的模
    double operator ^ (const Point &r) const {
        return x * r.y - y * r.x;
    }

    // 点积
    double operator * (const Point &r) const {
        return x * r.x + y * r.y;
    }

    double length() {
        return hypot(x, y);
    }

};
Point operator * (const double &k, const Point &v) {
    return Point(v.x * k, v.y * k);
}
double distance(const Point &l, const Point &r) {
    return hypot(r.x - l.x, r.y - l.y);
}
typedef Point Vector;



// 直线或线段
struct Line {
    Point s, e;
    double len;
    Line() :len(INFINITY) {}
    Line(Point _s, Point _e) : s(_s), e(_e), len(distance(_s, _e)) {}
};

// 点向直线的投影点
Point projection(const Point &p, const Line &l) {
    Vector vec = (l.e - l.s) / l.len;
    return l.s + (p - l.s) * vec * vec;
}
using namespace std;

int main() {
    // freopen("in", "r", stdin);
    int xp1, yp1, xp2, yp2, q;
    cin >> xp1 >> yp1 >> xp2 >> yp2 >> q;
    Line l(Point(xp1, yp1), Point(xp2, yp2));
    while (q--) {
        int x, y; cin >> x >> y;
        Point p(x, y);
        Point ans = projection(p, l);
        cout << fixed << setprecision(8) << ans.x << ' ' << ans.y << '\n';
    }
    return 0;
}


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

class Proc{
    public:
        string nam;
        int tim;
        Proc(){
            nam = ""; tim = 0;
        }
};

int main(){
    queue<Proc> Q;

    int n,q;
    cin >> n >> q;

    for(int i=0;i<n;i++){
        Proc P;
        cin >> P.nam >> P.tim;

        Q.push(P);
    }

    int total_tim = 0;

    while(!Q.empty()){
        Proc P = Q.front(); Q.pop();
        if(P.tim<=q){
            total_tim += P.tim;

            cout << P.nam << " " << total_tim << endl;
        }
        else{
            total_tim += q;
            P.tim -= q;

            Q.push(P);
        }
    }
    return 0;
}


Measured memory_bytes: 6224
#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <numeric>
#include <queue>
#include <stack>
#include <set>
#include <string>
#include <utility>
#include <vector>
#include <cstdio>
#include <cmath>

#define REP(i,n) for(int i = 0; i < (n); ++i)
#define REP1(i,n) for(int i = 1; i <= (n); ++i)
#define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
#define ALL(a) begin(a), end(a)
#define MP(a,b) make_pair((a), (b))
#define ROUNDUP(a,b) ((a) / (b) + ((a) % (b) == 0 ? 0 : 1))
#define X first
#define Y second
#define DEBUG(a) cout << #a << ": " << a << "\n"
// #define DEBUG(a) {}

using namespace std;
using ll = long long;
using vi = vector<int>;
using pii = pair<int, int>;

constexpr int MOD = 1e9 + 7;
constexpr int INF = 1e9 + 1;
constexpr ll LLINF = 4 * 1e18 + 1;
// constexpr int INF = 2147483647; // 2 * 1e9
// constexpr ll LLINF = 9223372036854775807; // 9 * 1e18

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

template<typename T>
T debug(T x) {
	DEBUG(x);
	return x;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int a, b, c;
  cin >> a >> b >> c;
  cout << min(a * b, c) << "\n";
	return 0;
}


Measured memory_bytes: 256
# 04:58 sec    63276 KB     912 bytes
import sys

class Node:
    __slots__ = ['key', 'left', 'right']
    def __init__(self, key):
        self.key = key
        self.left = self.right = None

class BST:
    def __init__(self):
        self.root = None
    def insert(self, key):
        x, y, z = self.root, None, Node(key)
        while x != None: x, y = x.left if z.key < x.key else x.right, x
        if y == None: self.root = z
        else:
            if z.key < y.key: y.left = z
            else: y.right = z
    def print_tree(self):
        def inorder(node):
            return inorder(node.left) + f' {node.key}' + inorder(node.right) if node else ''
        def preorder(node):
            return f' {node.key}' + preorder(node.left) + preorder(node.right) if node else ''
        print(inorder(self.root))
        print(preorder(self.root))

tree = BST()
input()
for e in sys.stdin:
    if e[0] == 'i': tree.insert(int(e[7:]))
    else: tree.print_tree()


Measured memory_bytes: 63468
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using std::cin;
using std::cout;
using std::endl;

using std::string;
using std::pair;

using std::vector;
using std::sort;

int main(){
    int a,b,c;
    int x;

    cin >> a >> b >> c;
    cin >> x;

    int ans=0;

    for(int i=0;i*500<=x && i<=a;i++){
        for(int j=0;i*500+j*100<=x && j<=b;j++){
            int k=(x-i*500-j*100)/50;
            if(k<=c){
                ans++;
            }
        }
    }

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



Measured memory_bytes: 256
import math

def makelist(n, m):
    return [[0 for _ in range(m)] for _ in range(n)]

pi = math.pi

a, b, x = list(map(float, input().split()))

taiseki = a * a * b
shahen = math.sqrt(a*a + b*b)

def check(r):
    theta = r * pi
    t = a / math.cos(theta)

    if t <= shahen:
        hoge = taiseki - (a * a * math.tan(theta) * 0.5 * a)
        #print(hoge)
        return x <= hoge
    else:
        theta = 0.5 * pi - theta
        s = b * math.tan(theta)
        hoge = b * s * 0.5 * a
        return x <= hoge
    

# 条件を満たす最大の値を返す
def binarySearch(small, big):
    mid = (big + small) / 2
    if big - small < 1e-9:
        return mid
    else:
        if check(mid):
            return binarySearch(mid, big)
        else:
            return binarySearch(small, mid)

ans = binarySearch(0, 0.5)

print(ans * 180)



Measured memory_bytes: 38384
#include<bits/stdc++.h>
#define ll long long
#define ld long double
#define pi acos(-1)
#define mod 1000000007
using namespace std;

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

    int n;
    cin >> n;
    int a[n];
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    if(n == 2){
        cout << abs(a[1] - a[0]);
        return 0;
    }
    int dp[n];
    memset(dp, 1e9, sizeof dp);
    dp[0] = 0;
    dp[1] = abs(a[1] - a[0]);
    dp[2] = abs(a[2] - a[0]);
    for(int i = 3; i < n; i++){
        dp[i] = min(dp[i-1] + abs(a[i] - a[i-1]), dp[i-2] + abs(a[i] - a[i-2]));
    }
    cout << dp[n-1];
    return 0;
}


Measured memory_bytes: 1024
#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <vector>

using namespace std;

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

  int A,B,C;
  cin >> A >> B >> C;
  int cnt = 0;
  for(int i = 0; i < 100000000; i++){
    if(A % 2 == 1 || B % 2 == 1 || C % 2 == 1){
      cout << cnt << endl;
      return 0;
    }
    cnt++;
    int tmpA = A/2, tmpB = B/2, tmpC = C/2;
    A /= 2;
    B /= 2;
    C /= 2;
    A += tmpC;
    B += tmpA;
    C += tmpB;
  }
  cout << -1 << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  private static class FastScanner {
    private BufferedReader reader = null;
    private StringTokenizer tokenizer = null;

    public FastScanner(InputStream in) {
      reader = new BufferedReader(new InputStreamReader(in));
      tokenizer = null;
    }

    public String next() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public String nextLine() {
      if (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          return reader.readLine();
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }

      return tokenizer.nextToken("\n");
    }

    public long nextLong() {
      return Long.parseLong(next());
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

    public double nextDouble() {
      return Double.parseDouble(next());
    }

    public int[] nextIntArray(int n) {
      int[] a = new int[n];
      for (int i = 0; i < n; i++)
        a[i] = nextInt();
      return a;
    }

    public long[] nextLongArray(int n) {
      long[] a = new long[n];
      for (int i = 0; i < n; i++)
        a[i] = nextLong();
      return a;
    }
  }

  public static void main(String[] args) {
    FastScanner sc = new FastScanner(System.in);
    int h = sc.nextInt();
    int w = sc.nextInt();
    int r = sc.nextInt();
    int c = sc.nextInt();
    System.out.println(h * w - r * w - c * h + r * c);
  }
}

Measured memory_bytes: 21460
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#include <cctype>
#include <set>
#include <map>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <cstdio>
#include <numeric>
#include <functional>
#include <cstdlib>
#include <regex>
#include <list>
int main() {
	int N;
	std::cin >> N;
	std::vector<int>L(N);
	for (int i = 0; i < N;++i) {
		std::cin >> L[i];
	}
	int sum = 0;
	int A = *std::max_element(L.begin(), L.end());
	for (int i = 0;i < N;++i) {
		sum += L[i];
	}
	int D = sum - A;
	if (A < D) {
		std::cout << "Yes" << std::endl;
	}
	else {
		std::cout << "No" << std::endl;
	}
	return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <string>
#include <cmath>
#include <complex>
#include <map>
using namespace std;

#define rep(i,n) for(int i=0;i<int(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define EPS 1e-8
#define F first
#define S second

static const double PI=6*asin(0.5);
typedef pair<double,double> P;
typedef complex<double> CP;
typedef long long ll;

double x[4],y[4];
double x2[4];
double y2[4];
double ang;
char t;

int main(){
	while(cin>>x[0]>>t>>y[0]>>t>>x[1]>>t>>y[1]>>t>>x[2]>>t>>y[2]){
		ang=atan((y[1]-y[0])/(x[1]-x[0]));
		rep(i,3){
			x2[i]=x[i]*cos(ang)+y[i]*sin(ang);
			y2[i]=-1*x[i]*sin(ang)+y[i]*cos(ang);
		}
		//rep(i,3)cout<<x[i]<<" "<<y[i]<<"  "<<x2[i]<<" "<<y2[i]<<endl;
		x2[3]=x2[2];
		y2[3]=-1*y2[2]+2.0*y2[1];
		ang*=-1;
		x[3]=x2[3]*cos(ang)+y2[3]*sin(ang);
		y[3]=-1*x2[3]*sin(ang)+y2[3]*cos(ang);
		printf("%.6f %.6f\n",x[3],y[3]);
	}
	return 0;
}

Measured memory_bytes: 1288
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
int main() {
    string S, T;
    cin >> S >> T;
 
    int ans = T.size();
 
    for (int start = 0; start <= S.size() - T.size(); start++)
    {
        int diff = 0;
        for (int i = 0; i < T.size(); i++)
        {
            if (T[i] != S[start + i]) {
                diff++;
            }
        }
        ans = min(ans, diff);
    }
 
    cout << ans << endl;
}

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

typedef long long ll;

#define REP(i, N) for (int i = 0; i < (int)(N); i++)

// chmax, chmin
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() {
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) {
        cin >> A[i];
        A[i] += 1;
    }
    
    vector<int> S(1e+5+2,0);
    
    REP(i,N){
        S[A[i]-1] += 1;
        S[A[i]] += 1;
        S[A[i]+1] += 1;
    }
    
    int ans = 0;
    REP(i,1e+5+2){
        ans = max(ans,S[i]);
    }
    
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 3868
#include<iostream>
using namespace std;
int main(){
int n;cin>>n;
int y=n%10;
if(y==2 ||y==4|| y==5 ||y==7 || y==9){
cout<<"hon";}
else if(y==0 ||y==1|| y==6 ||y==8 ){ cout<<"pon";}

else if(y==3 ){ cout<<"bon";}
}

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

using namespace std;

using ll = long long;
using P = pair<ll, ll>;
using Graph = vector<vector<ll>>;
#define rep(i, n) for(ll i=0;i<(ll)(n);i++)
#define rep2(i, m, n) for(ll i=m;i<(ll)(n);i++)
#define rrep(i, n, m) for(ll i=n;i>=(ll)(m);i--)
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int ddx[8] = {0, 1, 1, 1, 0, -1, -1, -1};
const int ddy[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll MOD = 1000000007;
const ll INF = 1000000000000000000L;
#ifdef __DEBUG

/**
 * For DEBUG
 * https://github.com/ta7uw/cpp-pyprint
 */
#include "cpp-pyprint/pyprint.h"

#endif

void solve() {
    ll K;
    cin >> K;
    queue<ll> que;
    rep2(i, 1, 10) {
        que.push(i);
    }
    ll ans = 0;
    while (true) {
        ans++;
        ll q = que.front();
        que.pop();
        if (ans == K) {
            cout << q << '\n';
            return;
        } else {
            ll last = q % 10;
            if (last != 0) {
                que.push(q * 10 + last - 1);
            }
            que.push(q * 10 + last);
            if (last != 9) {
                que.push(q * 10 + last + 1);
            }
        }
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}


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

using namespace std;

using ll = long long;

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> p(n), q(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
    }
    for (int i = 0; i < n; ++i) {
        cin >> q[i];
    }

    if (p > q) swap(p, q);
    
    int ans = 0;
    do {
        if (p == q) break;
        ans++;
    } while (next_permutation(p.begin(), p.end()));
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define F(i,a,n) for(int i=a; i<n; i++)
#define INF 100000000


int main(){
    int n;
    scanf("%d",&n);
    long h[n];
    F(i,0,n){
        scanf("%ld",h+i);
    }
    long dp[n];
    F(j,0,n) dp[j]=INF;
    dp[0]=0;
    dp[1]=abs(h[1]-h[0]);
    F(k,2,n){
        long l1=dp[k-1]+abs(h[k]-h[k-1]);
        long l2=dp[k-2]+abs(h[k]-h[k-2]);
        if(l1>l2) dp[k]=l2;
        else dp[k]=l1;
    }
    printf("%ld\n",dp[n-1]);
    return 0;
}

Measured memory_bytes: 1664
// I SELL YOU...! 
#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>
#include<queue>
#include<chrono>
using namespace std;
using ll = long long;
using P = pair<ll,ll>;
signed main(){
  ll a,b;
  cin >> a >> b;
  if(a!=1&&b!=1){
    cout <<1<<endl;
  }else if(a!=2&&b!=2){
    cout <<2<<endl;
  }else{
    cout << 3<<endl;
  }
}


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

namespace _0561
{
	class Program
	{
		static void Main(string[] args)
		{
			int[] x = Console.ReadLine().Split().Select(int.Parse).ToArray();
			List<int>[] books = new List<int>[11];
			for (int i = 0; i <= 10; i++) books[i] = new List<int>();
			for (int i = 0; i < x[0]; i++)
			{
				int[] a = Console.ReadLine().Split().Select(int.Parse).ToArray();
				books[a[1]].Add(a[0]);
			}
			int[] dp = new int[x[1] + 1];
			for (int i = 1; i <= 10; i++)
			{
				int[] arr = books[i].ToArray();
				Array.Sort(arr); Array.Reverse(arr);
				int[] sum = new int[arr.Count() + 1];
				for (int j = 0; j < arr.Count(); j++) sum[j + 1] = sum[j] + arr[j];
				int[] afterdp = new int[x[1] + 1];
				for (int j = 0; j <= x[1]; j++)
				{
					for (int k = 0; k <= Math.Min(j, arr.Count()); k++)
					{
						afterdp[j] = Math.Max(afterdp[j], dp[j - k] + sum[k] + ((k - 1) * k));
					}
				}
				dp = afterdp;
			}
			Console.WriteLine(dp[x[1]]);
		}
	}
}


Measured memory_bytes: 20588
#include <algorithm>
#include <cmath>
#include <ctime>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#include <cstring>
#include <tuple>
using namespace std;
typedef long long ll;
int main() {
    double r;
    const double PI = atan(1) * 4;
    cin >> r;
    cout.precision(6);
    cout << fixed << r * r * PI << " " << 2 * r * PI << endl;

    return 0;
}

Measured memory_bytes: 1288
N,M = map(int,input().split())
MOD = 10**9+7
MAXN = N+200
fac = [1,1] + [0]*MAXN
finv = [1,1] + [0]*MAXN
inv = [0,1] + [0]*MAXN
for i in range(2,MAXN+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD
def nhr(n,r):
    return ncr(n+r-1, r)

from collections import Counter
def factorize(n):
    d = Counter()
    m = 2
    while m*m <= n:
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] += 1
    return d

factors = factorize(M)
ans = 1
for v in factors.values():
    n = nhr(N,v)
    ans *= n
    ans %= MOD
print(ans)

Measured memory_bytes: 15844
n = int(input())
h = list(map(int, input().split()))


w = 1
for i in range(n-1):
    if h[i] - h[i+1] >= 2:
        w = 0

for j in range(n-2):
    if h[j] - h[j+1]  == 1:
        for k in range(j,n-2):
            if h[k+1] - h[k+2] == 0:
                continue
            if h[k+1] - h[k+2] == 1:
                w = 0
                break
            break


        
if w == 0:
    print("No")
else:
    print("Yes")

Measured memory_bytes: 14396
#include <stdio.h>

int
main(void)
{
        int x, y;
        int a = -1;
        int b;

        scanf("%d %d", &x, &y);

        if (x < y) {
                b = x;
                x = y;
                y = b;
        }

        while (a != 0) {
                a = x % y;
                x = y;
                y = a;
        }

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

        return 0;
}



Measured memory_bytes: 2092
A,B,C = map(int, input().split())
K = int(input())

AA = A
BB = B
CC = C

count = 0

for i in range(K):
    if AA < BB < CC:
        print("Yes")
        break
    elif CC <= AA or CC <= BB:
        CC *= 2
        count +=1
    elif BB <= AA:
        BB *= 2
        count +=1

if count == K:
    if AA < BB < CC:
        print("Yes")
    else:
        print("No")

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

long long mod=1000000007,ara[200007];

long long bigmod(long long n,long long p)
{
     if(p==0)return 1;
     if(p%2==0)
     {
         long long ret=bigmod(n,p/2);
         return ((ret%mod)*(ret%mod))%mod;
     }
     else
        return ((n%mod)*(bigmod(n,p-1)%mod))%mod;
}

int main()
{
        long long n,m,a,b,c,d,e,f,g,h,p,q,r,fr,sc,tr,sz,tz,i,j,k,mx=LLONG_MIN,mn=LLONG_MAX;
        long long x=0,y=0,cnt=0,res=0,ttl=0,ans,sum=0; long long flg=0,flag=1,na=0,as=1;
        vector<long long>u,v,w; vector< pair<long long,long long> >vct; vector<string>vst;
        set<long long>st,nt,tt; map<long long,long long>mp,nq,qr; string str,ttr,ntr;

        scanf("%lld %lld %lld",&n,&a,&b);

        fr=bigmod(2LL,n); fr--;

        ara[0]=1;

        for(i=1;i<=b;i++)
        {
            ara[i]=(ara[i-1]*i)%mod;
        }

        f=a; g=n-a; d=min(f,g); e=max(f,g);

        p=1;

        for(i=n;i>e;i--)
        {
            p=(p*i)%mod;
        }

        q=bigmod(ara[d],mod-2); r=(p*q)%mod; sc=r;

        f=b; g=n-b; d=min(f,g); e=max(f,g);

        p=1;

        for(i=n;i>e;i--)
        {
            p=(p*i)%mod;
        }

        q=bigmod(ara[d],mod-2); r=(p*q)%mod; sc=(sc+r)%mod;


        if(fr>=sc)printf("%lld\n",fr-sc);
        else{  printf("%lld\n",mod-sc+fr);   }





    return 0;
}





Measured memory_bytes: 5180
#ifdef DEBUG

#else

#    pragma GCC optimize("O3,no-stack-protector")
#    pragma GCC optimize("unroll-loops")

#    if __cplusplus < 201703L
#        pragma GCC target("avx")
#    else
#        pragma GCC target("avx2")
#    endif

#endif
// 実数の場合
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#define _USE_MATH_DEFINES
#include <bits/stdc++.h>
#define dump(x) cout << x << endl
typedef int64_t Int;
typedef long double Ld;

using namespace std;
using Graph = vector<vector<Int>>;

const double pi = M_PI;
const Int MOD = 1000000007;

// 二分累乗法
template <typename T>
T modpow(T a, T n, T mod) {
    T ret = 1;

    if (mod == 1) {
        while (n > 0) {
            if (n & 1) {
                ret = ret * a;
            }
            a = a * a;
            n >>= 1;
        }
    } else {
        while (n > 0) {
            if (n & 1) {
                ret = ret * a % mod;
            }
            a = a * a % mod;
            n >>= 1;
        }
    }

    return ret;
}

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

    Int n;
    cin >> n;
    map<Int, Int> m;
    for (Int i = 0; i < n; i++) {
        Int in;
        cin >> in;
        if (!m.insert({in, 1}).second) {
            m[in]++;
        }
    }

    bool isok = true;
    Int ans = 0;
    if (n % 2 == 1) {
        if (m.count(0) == 0) {
            isok = false;
        } else {
            if (m[0] != 1) {
                isok = false;
            }
        }

        n--;
        for (Int i = 2; i <= n; i += 2) {
            if (m.count(i) == 0) {
                isok = false;
                break;
            } else {
                if (m[i] != 2) {
                    isok = false;
                    break;
                }
            }
        }

    } else {
        if (m.count(0) == 1) {
            isok = false;
        }

        n--;
        for (Int i = 1; i <= n; i += 2) {
            if (m.count(i) == 0) {
                isok = false;
                break;
            } else {
                if (m[i] != 2) {
                    isok = false;
                    break;
                }
            }
        }
    }

    n++;
    if (isok) {
        ans = modpow((Int)2, (Int)(n / 2), MOD);
    } else {
        ans = 0;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 4224
import math
n, d = [int(i) for i in input().split()]
A = []
for i in range(n):
    A.append([int(i) for i in input().split()])
def distance_truth(x,y):
    dist = 0
    for i in range(d):
        dist += (x[i]-y[i])**2
    tmp = math.sqrt(dist)
    return int(tmp) == tmp
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if distance_truth(A[i],A[j]):
            ans += 1
print(ans)

Measured memory_bytes: 3064
#include <stdio.h>
#include <math.h>
#define PI 3.14159265359

int main(){
  double a, b, c;
  double sum, length, height;
  double deg;

  scanf("%lf %lf %lf", &a, &b, &c);
  deg=c*PI/180.0;
  sum=a*b*sin(deg)/2.0;
  height=b*sin(deg);
  length=sqrt(a*a+b*b-2.0*a*b*cos(deg))+a+b;
  printf("%lf\n", sum);
  printf("%lf\n", length);
  printf("%lf\n", height);
  return 0;
}



Measured memory_bytes: 2052
#include <bits/stdc++.h>
#include <unistd.h>
#include <sys/time.h>
#include <stdlib.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<P, ll> T;
typedef pair<long double , ll> Ps;
 
const ll INF = 2e18;
const ll fact_table = 3200008;
long double Pi = 3.1415926535897932384626;

priority_queue <ll> pql;
priority_queue <P> pqp;
priority_queue <P> bag;
//big priority queue
priority_queue <ll,vector<ll>,greater<ll> > pqls;
priority_queue <P,vector<P>,greater<P> > pqps;
//small priority queue
//top pop
 
ll dx[8]={1,0,-1,0,1,1,-1,-1};
ll dy[8]={0,1,0,-1,1,-1,-1,1};
char dir[] = "DRUL";
//↓,→,↑,←

#define endl "\n"
#ifdef ENJAPMA
    #undef endl
#endif
#define p(x) cout<<x<<endl;
#define el cout<<endl;
#define pe(x) cout<<x<<" ";
#define ps(x) cout<<fixed<<setprecision(25)<<x<<endl;
#define pu(x) cout<<(x);
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define CLEAR(a) a = decltype(a)(); 
#define pc(x) cout << x << ",";
#define rep(i, n) for (ll i = 0; i < (n); i ++)

// const ll mod = 998244353ll;
const ll mod = 1000000007ll;

ll mypow(ll a, ll b, ll mod){ll x=1;while(b){while(!(b&1)){(a*=a)%=mod;b>>=1;}(x*=a)%=mod;b--;}return x;}
void YES(bool cond){ if(cond){ p("YES");}else{ p("NO");} return;}
void Yes(bool cond){ if(cond){ p("Yes");}else{ p("No");} return;}


ll fact[fact_table + 5],rfact[fact_table + 5]; 
 
void c3_init(){
    fact[0] = rfact[0] = 1;
    for(ll i=1; i<=fact_table; i++){
        fact[i] = (fact[i-1]*i) % mod;
    }
    rfact[fact_table] = mypow(fact[fact_table],mod - 2, mod);
    for(ll i=fact_table; i>=1; i--){
       rfact[i-1] = rfact[i] * i;
       rfact[i-1] %= mod;
    }
    return;}
ll c3(ll n,ll r){
    return (((fact[n] * rfact[r]) % mod ) * rfact[n-r]) % mod;}


bool multicase = false;

ll n,m,num,a,b,c,d,e,h,q;
ll w, k, ans;

ll x[500005], y[500005], z[500005];
ll dp[5005][5005];
string s;

ll mul(ll a, ll b){
    if(b == 0)return 0;
    if(a > INF / b){
        return INF;
    }else{
        return a * b;
    }
}

void solve(){
    cin >> n;
    for(ll i=1;i<=50;i++){
        x[i] = i * (i + 1) / 2;
    }
    vector<ll> v;
    for(ll i=2;i*i<=n;i++){
        ll cnt = 0;
        if(n % i == 0){
            while(n % i == 0){
                n /= i;
                cnt ++;
            }
            for(ll j=1;j<=50;j++){
                if(x[j] > cnt){
                    ans += j - 1;
                    break;
                }
            }
            
        }
    }
    if(n != 1)ans ++;
    p(ans);
    return;
}


int main(){
    // init();
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll q, testcase = 1;
    if(multicase){
        cin >> q;
    }else{
        q = 1; 
    }
    while(q--){
        // pu("Case ");pu("#");pu(testcase);pu(": ");
        solve();
        testcase++;
    }
    // solve();
    return 0;
}
















Measured memory_bytes: 3668
#include<stdio.h>

int main()
{
  short rate_before,rate_after;
  int price_before,i,a,b,max;
  int n,m,p,q,r;

  // i,p = ?¨???????????????????                                                       
  // n,r = ????¨???????????????????                                                     
  // a,b = ????¨???????????????????                                                     

  while(1){
    max = 0;
    scanf("%hd %hd %d",&rate_before,&rate_after,&price_before);

    if(rate_before == 0 && rate_after == 0 && price_before == 0){
      break;
    }

    for(i = 1;i <= price_before/2;i++){
      n = i * (100+rate_before) / 100;
      m = price_before - n;
      p = m * 100 / (100+rate_before);

      while(1){
	p++;
	q = p * (100+rate_before) / 100;
	if(n + q != price_before){
          p--;
          break;
	}
      }

      r = p * (100+rate_before) / 100;                                                  

     if(n + r == price_before){                                              
      a = i * (100+rate_after) / 100;
      b = p * (100+rate_after) / 100;
      if(a+b > max){
	max = a + b;
      }
     }                                                                       
    }
    printf("%d\n",max);
  }

  return 0;
}

Measured memory_bytes: 600