akhauriyash/Code-Regression huggingface dataset:
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <iostream>
#include <string>
#include <set>
#include <map>
#include <unordered_map>
#include <complex>
#include <iomanip>
#include <cmath>
#include <tuple>
using namespace std;

long long const MOD = 1000000007LL;

int main() {
    int w, h, n;
    cin >> w >> h >> n;

    int chart[h + 1][w + 1];
    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) {
            if (i == 0 || j == 0) chart[i][j] = 0;
            else chart[i][j] = 1;
        }
    }

    for (int i = 0; i < n; i++) {
        int x, y, a;
        cin >> x >> y >> a;
        if (a == 1) {
            for (int i = 1; i <= h; i++) {
                for (int j = 1; j <= x; j++) chart[i][j] = 0;
            }
        } else if (a == 2) {
            for (int i = 1; i <= h; i++) {
                for (int j = x + 1; j <= w; j++) chart[i][j] = 0;
            }
        } else if (a == 3) {
            for (int i = 1; i <= y; i++) {
                for (int j = 1; j <= w; j++) chart[i][j] = 0;
            }
        } else if (a == 4) {
            for (int i = y + 1; i <= h; i++) {
                for (int j = 1; j <= w; j++) chart[i][j] = 0;
            }
        }
    }

    int res = 0;
    for (int i = 0; i <= h; i++) {
        for (int j = 0; j <= w; j++) res += chart[i][j];
    }
    cout << res << endl;
}


Measured memory_bytes: 256
# C
a,b,c,d = map(int,input().split())

import fractions

f=fractions.gcd(c,d)           #最大公約数
f2=c*d//f                          #最小公倍数

# a未満でcかdで割れるかず
a-=1
x = a//c
y = a//d
z = a//f2
ac = x+y-z

# b以下でcかdで割れるかず
x = b//c
y = b//d
z = b//f2
bc = x+y-z

print(b-a-(bc-ac))

Measured memory_bytes: 64620
#include <stdio.h>
#include <stdlib.h>
int main()
{
	int S[200000],T[200000];
	int i,n;
	scanf("%d",&n);
	for(i=0;i<n;i++)
		scanf("%d",&S[i]);
	for(i=0;i<n;i++)
		T[(n/2)+((i+1)/2)*(n%2?((i%2)*2-1):((i+1)%2)*2-1)]=S[i];
	for(i=0;i<n;i++)
		printf("%d ",T[i]);
	return 0;
}


Measured memory_bytes: 3712
#include<bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
using ll = long long;
using P=pair<int,int>;
int main(){
  int X;
  cin>>X;
  
  int c500=X/500*1000;
  int c5=(X%500)/5 *5;
  int ans=c500+c5;

  cout<<ans<<endl;



}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, a, n) for(ll i = a; i < (ll)(n); i++)
#define memi cout << endl
#define kono(n) cout << fixed << setprecision(n)
#define all(c) (c).begin(), (c).end()
#define pb push_back
#define hina cout << ' '
#define in(n) cin >> n
#define in2(n, m) cin >> n >> m
#define in3(n, m, l) cin >> n >> m >> l
#define out(n) cout << n
const ll mei = (ll)1e9 + 7;

int main(){
  ll a, b, c, d;
  in2(a, b);
  in2(c, d);
  a = max(a, c);
  b = min(b, d);
  c = max(0ll, b - a);
  out(c);
  memi;
}

Measured memory_bytes: 256
H, W, K = map(int, input().split())
MOD = 10 ** 9 + 7

factorial = [1, 1]  # 元テーブル
inverse = [1, 1]  # 逆元テーブル
inverse_from = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, H * W + 1):
    factorial.append((factorial[-1] * i) % MOD)
    inverse_from.append((-inverse_from[MOD % i] * (MOD // i)) % MOD)
    inverse.append((inverse[-1] * inverse_from[-1]) % MOD)


def nCr(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % MOD


ans = 0
# Hについて
for d in range(1, H):
    ans += d * (H - d) * pow(W, 2, MOD) * nCr(H * W - 2, K - 2) % MOD
    ans %= MOD
# Wについて
for d in range(1, W):
    ans += d * (W - d) * pow(H, 2, MOD) * nCr(H * W - 2, K - 2) % MOD
    ans %= MOD

print(ans % MOD)


Measured memory_bytes: 27024
#ifdef Prateek
  #include "Prateek.h"
#else
  #include <bits/stdc++.h>
  using namespace std;
  #define debug(...) 42
#endif
#define F first
#define S second
#define pb push_back
#define f(i,x,n) for(int i=x;i<n;i++)
#define all(c) c.begin(),c.end()
#define int ll
using ll = long long;
const int MOD = 1e9+7, N = 1e5 + 10; 

int32_t main(){
   ios::sync_with_stdio(false);
   cin.tie(NULL);
   int n,m;
   string s,t;
   cin >> s >> t;
   int ans = 1e9;
   n = s.length(), m = t.length();

   auto match = [&](string a){
      int v = 0;
      debug(a,t);
      for(int i = 0; i < m; ++i){
         v += (a[i] != t[i]);
      }
      debug(v);
      return v;

   };

   for(int i = 0; i < n-(m-1); ++i){
      ans = min(ans,match(s.substr(i,m)));
   }

   cout << ans << '\n';
   return 0;
} 

Measured memory_bytes: 3616
arr=[int(input()) for i in range(5)]

div=list(map(lambda x: x%10, arr))
index=0
min_v=9
for i, v in enumerate(div):
    if v!=0 and v < min_v:
        index = i
        min_v = v

del div[index]

interval = sum(list(map(lambda x: 10-x if x!=0 else 0, div)))
print(sum(arr)+interval)


Measured memory_bytes: 3060
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
const ll inf=((ll)1<<31)-1;
struct segtree{
    private:
    vector<ll> node;
    ll siz;
    public:
    segtree(ll n){
        siz=1;
        while(siz<n) siz*=2;
        node.resize(siz*2,inf);
    }
    void upd(ll pos,ll x){
        pos+=siz-1;
        node[pos]=x;
        while(pos>0){
            pos=(pos-1)/2;
            node[pos]=min(node[pos*2+1],node[pos*2+2]);
        }
    }
    ll seq_min(ll l,ll r,ll pos=0,ll a=0,ll b=-1){
        if(b<0) b=siz;
        if(b<=l||r<=a) return inf;
        if(l<=a&&b<=r) return node[pos];
        ll mid=(a+b)/2;
        ll lb=seq_min(l,r,pos*2+1,a,mid);
        ll rb=seq_min(l,r,pos*2+2,mid,b);
        return min(lb,rb);
    }
};
int main(){
    ll n,q;
    cin>>n>>q;
    segtree seg(n);
    for(int i=0;i<q;i++){
        ll c,x,y;
        cin>>c>>x>>y;
        if(c==0) seg.upd(x,y);
        else cout<<seg.seq_min(x,y+1)<<endl;
    }
}


Measured memory_bytes: 4956
/*
@Author: nonameless
@Date:   2020-05-19 11:26:20
@Email:  2835391726@qq.com
@Blog:   https://www.cnblogs.com/nonameless/
*/
#include <bits/stdc++.h>
#define first x
#define second y
#define push_back pb
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
const double PI  = acos(-1.0);
const double eps = 1e-8;
const int INF = 0x3f3f3f3f;
const ll LNF  = 0x3f3f3f3f3f3f;
inline int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
inline ll  gcd(ll  a, ll  b) { return b ? gcd(b, a % b) : a; }
inline int lcm(int a, int b) { return a * b / gcd(a, b); }


int main(){

    int a, b, h, m;
    cin >> a >> b >> h >> m;
    double angleH = h * 30 + m * 0.5;
    double angleM = m * 6;
    double angle  = fabs(angleH - angleM);
    if(angle > 180.0) angle = 360.0 - angle;
    double ans = sqrt(a * a + b * b - 2 * a * b * cos(PI/180*angle));
    printf("%.20f\n", ans);
    return 0;
}


Measured memory_bytes: 4136
/*
	0073:Surface Area of Quadrangular Pyramid
*/
#include	<iostream>
#include	<cstdio>
#include	<cmath>

using namespace std;

int main(void) {
	while(1) {
		int x, h;
		cin >> x >> h;
		
		if(x == 0 && h == 0) { break; }
		
		printf("%.6f\n", x * sqrt(4 * h * h + x * x) + x * x );
	}
}

Measured memory_bytes: 1192
N,L=map(int,input().strip().split(" "))
a=[]

for i in range(N):
    a.append(input())

a.sort()

b=str(a)
b=b.replace(",","")
b=b.replace("[","")
b=b.replace("]","")
b=b.replace("'","")
b=b.replace(" ","")


print(b)


Measured memory_bytes: 3060
n,m = map(int,input().split())
ken = []
for i in range(m):
    p,y = map(int,input().split())
    ken.append([p,y,i+1])
 
k = sorted(ken)
a = []
cnt = 1
for i in range(m):
    if i >= 1:
        if k[i][0] == k[i-1][0]:
            cnt += 1
        else:
            cnt = 1
    a.append([k[i][-1],k[i][0],cnt])

aa = sorted(a)
for i in range(m):
    print("{0:06d}".format(aa[i][1]) + "{0:06d}".format(aa[i][2]))

Measured memory_bytes: 39372
#include <assert.h>
#include <ctype.h>
#include <errno.h>
#include <float.h>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <set>
#include <queue>
#include <limits>
#include <deque>
#include <locale>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>
#include <algorithm>
#include <bitset>
#include <map>
#include <iomanip>
#include <ios>
#include <iostream>
#include <vector>
#include <cwchar>
#include <cwctype>
#define mp make_pair
#define fs first
#define se second
#define memset(a,t) memset(a,t,sizeof(a))
#define all(v) v.begin(),v.end()
#define eprintf(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define MN 0LL
#define Mx 200000005
#define Mn -Mx
#define MX 20000000000000005
using namespace std;
int readint(){
	char c;
	while(c=getchar(),(c<'0'||c>'9')&&c!='-');
	bool flag=(c=='-');
	if(flag)c=getchar();
	int x=0;
	while(c>='0'&&c<='9'){
		x=x*10+c-48;
		c=getchar();
	}
	return flag?-x:x;
}
inline string tos(int x){
	string s;
	while(x) s=(char)(x%10+'0')+s,x/=10;
	return s;
}

int main(){
	ios_base::sync_with_stdio(false);
	int i,x,cnt=0;
	cin>>x;
	for(i=1;i<=x;i++){
		cnt+=i;
		if(cnt>=x){
			cout<<i<<endl;
			return 0;
		}
	}
}


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

int main()
{
	int n;
	string tmp, f, b, revf,revb;
	set<string> s;
	cin >> n;
	while (n--) {
		s.clear();
		cin >> tmp;
		for (int i = 1; i < tmp.size(); i++) {
			f = revf = tmp.substr(0, i);
			b = revb = tmp.substr(i);
			
			reverse(revf.begin(), revf.end());
			reverse(revb.begin(), revb.end());
			
			s.insert(f + b);
			s.insert(b + f);
			s.insert(revf + b);
			s.insert(b + revf);
			s.insert(f + revb);
			s.insert(revb + f);
			s.insert(revf + revb);
			s.insert(revb + revf);
		}
		cout << s.size() << endl;
	}
	
	return 0;
}

Measured memory_bytes: 1292
#include <bits/stdc++.h>
using namespace std;
int main(){
    double N;

    cin >> N;
    vector<double> vec(N);
    for(int i=0;i<N;i++) cin >> vec.at(i);
    for(int i=0;i<N;i++) vec.at(i)=1/vec.at(i);
    double S =0;
    for(int i=0;i<N;i++) S+=vec.at(i);
    cout << 1/S << endl;

    
}

Measured memory_bytes: 256
#include <stdio.h>

long int a[1000000];
int n;

void maxHeapify(int i){
  int l, r, largest, cont;
  l = 2 * i;
  r = 2 * i + 1;

  if(l<=n && a[l] > a[i])
    largest = l;
  else
    largest = i;

  if(r<=n && a[r] > a[largest])
    largest = r;
  if(largest!=i){
    //printf("cange node:%d %ld and node:%d %ld\n",i,a[i],largest,a[largest]);
    cont = a[i];
    a[i] = a[largest];
    a[largest] = cont;
    maxHeapify(largest);
  }
}

void buildMaxHeap(){
  int i;
  for(i=n/2;1<=i;i--){
    maxHeapify(i);
  }
}

int main(){
  int i,c;

  for(i=1;i<500;i++)a[i]='\0';

  scanf("%d",&n);

  for(i=1;i<=n;i++)
    scanf("%ld",&a[i]);
  buildMaxHeap();

  
  for(i=1;i<=n;i++)
    printf(" %ld",a[i]);

  printf("\n");
  
  
  
  return 0;
}



Measured memory_bytes: 5668
import java.util.Scanner;
public class Main{

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int k = sc.nextInt();
		
		String s = sc.next();
		int m = 0;
		int l = 0;
		int ans = 0;
		
		for(int i = 0 ; i < n-1 ; i++) {
			if(s.charAt(i) == s.charAt(i+1)) {
				m++;
			}
			if(s.charAt(i) != s.charAt(i+1)) {
				l++;
			}
		}
		if(2 * k <= l) {
			ans += (2 * k) + m ;
		}
		if(2 * k > l) {
			ans += m + l;
		}
		System.out.println(ans);

	}
}


Measured memory_bytes: 24468
#include<bits/stdc++.h>
#define F first
#define S second
#define endl '\n'
#define MP make_pair
#define pb push_back

using namespace std;
typedef pair<int, int> P;
typedef pair<int, P> i_P;
typedef long long LL;

static const int INF = INT_MAX;
static const LL L_INF = LLONG_MAX;
static const int MOD = (1000000000 + 7);

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

    int a, b, c;
    cin >> a >> b >> c;
    if( b / a >= c ) cout << c;
    else cout << b / a;
    cout << endl;
    return 0;
}



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

int main() {
	u32 N, K;
	cin >> N >> K;
	
	u32 T = 0;

	while(N > 0) {
		N /= K;
		T++;
	}
	
	cout << T;
	return 0;
}


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

int N, K;
string S;

int main(){
	cin >> N >> K >> S;
	int divi = 1;
	int ok = 0;
	for(long long i = 0; i < S.size() - 1; i++){
		if(S[i] != S[i+1]){
			divi++;
		}else{
			ok++;
		}
	}

	while(K>0){
		if(divi > 2){
			K--;
			divi-=2;
			ok += 2;
		}else if(divi == 2){
			K--;
			divi-=1;
			ok += 1;
		}else{
			break;
		}
	}
	cout << ok << endl;
}


Measured memory_bytes: 512
#include <iostream>
#include <vector>
#include<list>
#include <algorithm>
#include <string>
#include <math.h>
#include<map>
#include <utility>

#include<queue>
using namespace std;
#define REP(i,k,n) for(int i=k;i<n;i++)
 
#define INF 1844674407370955161
typedef long long unsigned int ll;
#define SIZE_OF_ARRAY(array) (sizeof(array)/sizeof(array[0]))
#define MOD 1000000007

template<typename T>
int vector_finder(std::vector<T> vec, T number) {
  auto itr = std::find(vec.begin(), vec.end(), number);
  size_t index = std::distance( vec.begin(), itr );
  if (index != vec.size()) { // 発見できたとき
    return 1;
  }
  else { // 発見できなかったとき
    return 0;
  }
}

template<typename T>
T gcd(T a,T b){
	if(b>0){
		return gcd(b, a % b);
	}else{
		return a;
	}
}

template<typename T>
T lcm(T a,T b){
	T g = gcd(a, b);
	return a * b / g;
}

void clear( std::queue<pair<int,int> > &q )
{
   std::queue<pair<int,int> > empty;
   std::swap( q, empty );
}
bool IsPrime(int num)
{
    if (num < 2) return false;
    else if (num == 2) return true;
    else if (num % 2 == 0) return false; // 偶数はあらかじめ除く

    double sqrtNum = sqrt(num);
    for (int i = 3; i <= sqrtNum; i += 2)
    {
        if (num % i == 0)
        {
            // 素数ではない
            return false;
        }
    }

    // 素数である
    return true;
}
template<typename T>
std::vector<T> enum_div(T n)//nの約数を列挙
{
	std::vector<T> ret;
	for(T i=1 ; i*i<=n ; ++i)
	{
		if(n%i == 0)
		{
			ret.push_back(i);
			if(i!=1 && i*i!=n)
			{
				ret.push_back(n/i);
			}
		}
	}
	return ret;
}

int N,K;


int main()
{
  int A, B;
  cin >> A >> B;
  if(A<=5){
    cout << 0 << endl;
  }else if(A<=12){
    cout << B / 2 << endl;
  }else{
    cout << B << endl;
  }
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
#define ll long long
int d()
{
    int t ;
    scanf( "%d", &t ) ;
    return t ;
}
ll lld()
{
    ll t ;
    scanf( "%lld", &t ) ;
    return t ;
}
const long long N = 1e5+20,OO=0x3f3f3f3f;
int n;
int dp[N][5];
int s[N],c[N],h[N];
int solve(int i,int last){
    if(i==n)return 0;
    int choice1=-1;
    int choice2=-1;
    int choice3=-1;
    if(dp[i][last]!=-1)return dp[i][last];
    if(last!=0)
        choice1=s[i]+solve(i+1,0);
    if(last!=1)
        choice2=c[i]+solve(i+1,1);
    if(last!=2)
        choice3=h[i]+solve(i+1,2);
    return dp[i][last]=max(choice1,max(choice2,choice3));
}

int main()
{

    n=d();
    for(int i=0;i<n;i++)    scanf("%d %d %d",s+i,c+i,h+i);
    memset(dp,-1,sizeof dp);
    cout<<solve(0,3)<<endl;;
}


Measured memory_bytes: 11136
input()
S=list(input())
ans=0

def index(x,l):
    if x in l:
        return l.index(x)
    else:
        return -1

for i in range(1000):
    Si=0
    s=list(str(i).zfill(3))
    si=0
    if index(s[0],S) != -1:
        if index(s[1],S[S.index(s[0])+1:]) != -1:
            if index(s[2],S[S.index(s[0])+1:][S[S.index(s[0])+1:].index(s[1])+1:]) != -1:
                ans += 1
print(ans)

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

int main(){
  int n; cin >> n;
  int ans = 0;
  for(int i=0; i < n; i++){
    int a; cin >> a;
    bool flg = true;
    for(int j=2; j*j <= a; j++){
      if(a % j == 0){
        flg = false;
      }
    }
    if(flg) ans++;
  }

  cout << ans << endl;

}

Measured memory_bytes: 1160
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<functional>
#include<vector>
#include<queue>
#include<stack>
#include<set>
#include<map>
using namespace std;
#define MOD 1000000007
#define f(i,n) for(int i=0;i<int(n);i++)
#define N 200000
long long a[3000][3000];





int main() {
	int n, q, x, y;
	long long z;
	int b[3000];
	scanf("%d %d", &n,&q);
	f(i, n)scanf("%d", &b[i]);
	f(i, n) {
		f(j, n)a[i][j] = 0;
	}
	f(i, n) {
		f(j, i) {
			if (b[j] < b[i]) {
				a[j][i] = 1;
			}
			else if (b[j] > b[i]) {
				a[i][j] = 1;
			}
		}
	}
	f(qq, q) {
		scanf("%d %d", &x, &y);
		x--;
		y--;
		f(i, n) {
			if ((i != x) && (i != y)) {
				z = a[i][x];
				z += a[i][y];
				z *= 500000004;
				z %= MOD;
				a[i][x] = z;
				a[i][y] = z;
			}
		}
		f(i, n) {
			if ((i != x) && (i != y)) {
				z = a[x][i];
				z += a[y][i];
				z *= 500000004;
				z %= MOD;
				a[x][i] = z;
				a[y][i] = z;
			}
		}
		z = a[x][y];
		z += a[y][x];
		z *= 500000004;
		z %= MOD;
		a[x][y] = z;
		a[y][x] = z;
	}
	z = 0;
	f(i, n) {
		f(j, i) {
			z = (z + a[i][j]) % MOD;
		}
	}
	f(i, q)z = (z * 2) % MOD;
	printf("%lld\n", z);
	return 0;
}

Measured memory_bytes: 70528
// 2011/01/15 Tazoe

#include <iostream>
using namespace std;

int main()
{
	while(true){
		int n;
		cin >> n;
		if(n==0)
			break;

		int gen[7];
		for(int i=0; i<7; i++)
			gen[i] = 0;

		for(int i=0; i<n; i++){
			int age;
			cin >> age;
			if(age>=0&&age<10)
				gen[0]++;
			else if(age<20)
				gen[1]++;
			else if(age<30)
				gen[2]++;
			else if(age<40)
				gen[3]++;
			else if(age<50)
				gen[4]++;
			else if(age<60)
				gen[5]++;
			else if(age>=60)
				gen[6]++;
		}

		for(int i=0; i<7; i++)
			cout << gen[i] << endl;
	}

	return 0;
}

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

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<vector<int>> mi;
typedef vector<vector<pair<int, int>>> w_graph;
typedef vector<vector<int>> uw_graph;




int dp[(int)1e5 + 5];
int h[(int)1e5 + 5];

void init(){
	for (int i = 0; i < 1e5 + 5; i++){
		dp[i] = 0;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
   	#ifdef DEBUG
		freopen("out.txt", "w", stdout);
	#endif
	init();
	int n;
	cin >> n;
	for (int i = 1; i <=n; i++){
		cin >> h[i];
	}
	h[0] = 1e6;
	for (int i = 2; i <= n; i++){
		dp[i] = min(dp[i - 1] + abs(h[i] - h[i - 1]), dp[i - 2] + abs(h[i] - h[i - 2]));
	}
	cout << dp[n] << endl;
	return 0;
}


Measured memory_bytes: 1152
#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from fractions import gcd
from itertools import combinations,permutations,accumulate # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
#import bisect
#
#    d = m - k[i] - k[j]
#    if kk[bisect.bisect_right(kk,d) - 1] == d:
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#

import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
def readInts():
  return list(map(int,input().split()))
def I():
  return int(input())
n,m = readInts()
AB = []
for i in range(n):
    a,b = readInts()
    AB.append((a,b))
AB = sorted(AB, key = lambda x:x[0])
#print(AB)
num = 0
cost = 0
for a,b in AB:
    if m >= num + b:
        num += b
        cost += a*b
    else:
        cost += a*(m - num)
        num = m
print(cost)


Measured memory_bytes: 25856
#!/usr/bin/env pypy3
# n,m = map(int,sys.stdin.readline().split())
# a = list(map(int,sys.stdin.readline().split()))
# a = [sys.stdin.readline() for s in range(n)]
# s = sys.stdin.readline().rstrip()
# n = int(sys.stdin.readline())
# d = collections.defaultdict(list)
# import math
# from functools import reduce
import sys
sys.setrecursionlimit(15000)

n = int(sys.stdin.readline())
s = sys.stdin.readline().rstrip()
d = {"R":[],"G":[],"B":[]}
sb = set()
for i in range(n):
    d[s[i]].append(i)
    if s[i]=="B":
        sb.add(i)
s = 0
#s = sum(1 for a in d["R"] for b in d["G"] for c in d["B"] if abs(a-b) != abs(b-c) and abs(a-c) != abs(c-b) and abs(b-a) != abs(a-c))
#s = len(d["R"])*len(d["G"])*len(d["B"])-sum(1 for a in d["R"] for b in d["G"] for c in d["B"] if abs(a-b) == abs(b-c) or abs(a-c) == abs(c-b) or abs(b-a) == abs(a-c))
for a in d["R"]:
    for b in d["G"]:
        s += len(d["B"])
        if 2*b-a in sb:
            s -= 1
        if 2*a-b in sb:
            s -= 1
        if (a+b)%2 == 0 and (a+b)//2 in sb:
            s -= 1
print(s)

Measured memory_bytes: 68580
let content = '';
process.stdin.resume();
process.stdin.setEncoding('utf8');
process.stdin.on('data', buf => {
  content += buf;
});
process.stdin.on('end', () => {
  const [, ...rows] = content
    .trim()
    .split('\n')
    .map(line => line.split(' ').map(n => parseInt(n, 10)));
  const result = rows.map(appendSum);
  const lastRow = [];
  for (let i = 0; i < result[0].length; i++) {
    let sum = 0;
    for (let j = 0; j < result.length; j++) {
      sum += result[j][i];
    }

    lastRow.push(sum);
  }

  result.push(lastRow);

  console.log(result.map(nums => nums.join(' ')).join('\n'));
});

const appendSum = nums => {
  const sum = nums.reduce((prev, cur) => prev + cur);
  return [...nums, sum];
};


Measured memory_bytes: 18176
#include<bits/stdc++.h>
using namespace std;
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define ll long long
#define vi vector<int>
#define vl vector<ll>
#define pb push_back
#define pi pair<int,int>
#define pl pair<ll,ll>
#define vpi vector<pi>
#define vpl vector<pl>
#define umi unordered_map<int,int>
#define uml unordered_map<ll,ll>
#define mp make_pair
#define F first
#define S second
#define mod 1000000007
#define inf 1000000000000000
#define md 998244353
#define endl "\n"

ll prime[1000000];

void sieve()
{
	prime[0]=0;
	prime[1]=0;
	for(int i=2;i<1000000;i++)
		prime[i]=1;

	for(int i=2;i*i<1000000;i++)
		if(prime[i]==1)
			for(int j=i*i;j<1000000;j+=i)
				prime[j]=0;
}

bool isPrime(ll n) 
{ 
    if (n <= 1) 
        return false; 
    for (ll i = 2; i <= floor(sqrt(n)); i++) 
        if (n % i == 0) 
            return false; 
  
    return true; 
}

ll gcd(ll a, ll b)
{ 
	return !b ? a : gcd(b, a % b); 
}
ll lcm(ll a, ll b)
{ 
	return (a / gcd(a, b)) * b; 
}
ll fastExponentiation(ll n, ll x, ll modulo) 
{
	ll res = 1;
	while(x > 0) 
       {
          if(x & 1)
          res = (res*n) % modulo; 
          x = x >> 1;
          n = (n * n) % modulo;
       }
       return res; 
}


ll power(ll n , ll p ){
	if(p==0)
	   return 1;
 
	 ll res = power((n*n)%mod,p/2);
	 if(p%2==1)
	   res = (n*res)%mod;
 
	   	 return res;
}


void solve()
{
	int x;
	ll ans=0;
	cin>>x;
	
	int n=x/500;
	// cout<<n<<endl;
	
	ans+=n*1000;
	// cout<<ans<<endl;
	
	x=x-n*500;
	n=x/5;
	// cout<<x<<" "<<n<<endl;
	
	// cout<<ans<<endl;
	ans+=n*5;
	cout<<ans<<endl;
}


int main()
{
	fastio
	
	// int t; cin>>t; while(t--)
	solve();
	
	return 0;
}

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

typedef long long LL;
typedef long double LD;
typedef pair < int, int > PII;
typedef pair < LL, LL > PLL;
typedef pair < LD, LD > PDD;

#define _upgrade ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define all(x) (x).begin(), (x).end()
#define sz(x) (int)(x).size()
template < typename _T > inline void _DBG(const char *s, _T x) { cerr << s << " = " << x << "\n"; }
template < typename _T, typename... args > void _DBG(const char *s, _T x, args... a) { while(*s != ',') cerr << *s++; cerr << " = " << x << ','; _DBG(s + 1, a...); }

#ifdef LOCAL
#define DBG(...) _DBG(#__VA_ARGS__, __VA_ARGS__)
#else
#define DBG(...) (__VA_ARGS__)
#define cerr if(0) cout
#endif

// ********************** CODE ********************** //

int n, m, cnt[256];
int np, p;

int main()
{
    _upgrade
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        string s; cin >> s;
        for(auto c: s) cnt[c]++;
    }
    for(char i = 'a'; i <= 'z'; i++)
    {
        if(cnt[i] % 2 == 1) np++;
        else if(cnt[i] % 4 == 2) p++;
    }
    if(m % 2 == 1) swap(n, m);
    if(n % 2 == 0 && m % 2 == 0)
    {
        if(p + np) cout << "No\n";
        else cout << "Yes\n";
    }
    else if(m % 2 == 0)
    {
        if(np == 0 && p <= m / 2) cout << "Yes\n";
        else cout << "No\n";
    }
    else
    {
        if(np != 0)
        {
            if(np == 1 && p <= n / 2 + m / 2) cout << "Yes\n";
            else cout << "No\n";
        }
        else
        {
            cout << "No\n";
        }
    }
	return 0;
}


Measured memory_bytes: 256
#include <cstdio>
using namespace std;
int H, N, sum;
int main() {
  scanf("%d %d", &H, &N);
  for(int i = 0, A; i < N; ++i) {
    scanf("%d", &A);
    sum += A;
  }
  printf("%s\n", (sum>=H?"Yes":"No"));
}

Measured memory_bytes: 128
N = int(input())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
sumA = [A[0]]
sumB = [B[0]]
for i in range(1,N):
    sumA.append(sumA[-1] + A[i])
    sumB.append(sumB[-1] + B[i])
sumB = [0] + sumB
ans = 0
for i in range(N):
    ans = max(ans, sumA[i] + sumB[-1] - sumB[i])
print(ans)

Measured memory_bytes: 3064
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#include <queue>
#include <deque>
#include <bitset>
#include <iterator>
#include <list>
#include <stack>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <functional>
#include <numeric>
#include <utility>
#include <limits>
#include <time.h>
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>

using namespace std;

#define FOR(i,n) for(int i = 0; i < n; i++)
#define FORa(i,a,b) for(int i = a; i < b; i++)
#define pb(x) push_back(x)
#define mp(a, b) make_pair(a, b)
#define F first
#define S second
#define SORT(a,n) sort(begin(a), begin(a) + n)
#define VSORT(v) sort(v.begin(), v.end())
#define MAX 1000000
#define ll long long
#define LOW(s) transform(s.begin(),s.end(),s.begin(),::tolower)
#define UP(s) transform(s.begin(),s.end(),s.begin(),::toupper)

//-------------------------------------------------------//

int main() {
	int x;
	cin >> x;
	
	cout << x/500*1000 + (x-x/500*500)/5*5 << endl;
	
	return 0;
}

Measured memory_bytes: 3596
local n, k = io.read("*n", "*n")
local x, y, p = {}, {}, {}
for i = 1, n do
  x[i], y[i] = io.read("*n", "*n")
  p[i] = {x[i], y[i]}
end
table.sort(x)
table.sort(y)

local ret = false
for i = 1, n - 1 do
  for j = i + 1, n do
    local xl, xr = x[i], x[j]
    local py = {}
    for z = 1, n do
      if xl <= p[z][1] and p[z][1] <= xr then
        table.insert(py, p[z][2])
      end
    end
    if k <= #py then
      table.sort(py)
      for z = 1, #py + 1 - k do
        local yl, yr = py[z], py[z + k - 1]
        local val = 1LL * (xr - xl) * (yr - yl)
        if not ret then ret = val
        elseif val < ret then ret = val
        end
      end
    end
  end
end
local str = tostring(ret):gsub("LL", "")
print(str)


Measured memory_bytes: 384
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
int n;
long long a,b;
long long e[100010];
int lsta[100010],lstb[100010];
long long dp1[100010],dp2[100010];
const long long md=1e9+7;
int lst1,lst2;
void pls(long long& x,long long y)
{
	x+=y;
	if(x>md)x-=md;
}
int main()
{
	scanf("%d%lld%lld",&n,&a,&b);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",e+i);
	}
	for(int i=2;i<=n;i++)
	{
		for(lsta[i]=lsta[i-1];e[lsta[i]+1]+a<=e[i];lsta[i]++);
		for(lstb[i]=lstb[i-1];e[lstb[i]+1]+b<=e[i];lstb[i]++);
	}
	dp1[0]=dp2[0]=1;
	for(int i=2;i<=n;i++)
	{
		long long ax=dp2[min(i-2,lsta[i])],ay=dp1[min(i-2,lstb[i])];
		if(lsta[i]!=i-1)
		{
			for(int j=lst1;j<=i-2;j++)dp1[j]=0;
			lst1=i-1;
		}
		if(lstb[i]!=i-1)
		{
			for(int j=lst2;j<=i-2;j++)dp2[j]=0;
			lst2=i-1;
		}
		pls(dp1[i-1],ax+dp1[i-2]);
		pls(dp2[i-1],ay+dp2[i-2]);
	}
	long long ans=(dp1[n-1]+dp2[n-1])%md;
	printf("%lld",ans);
	return 0;
}

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

using namespace std;

const int inf = (int) 1e9;

int main() {
#ifdef __APPLE__
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    int n, m;
    scanf("%d %d", &n, &m);
    vector<vector<int>> g(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        scanf("%d %d", &a, &b);
        --a; --b;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    vector<int> d(n, inf);
    d[0] = 0;
    queue<int> q;
    q.push(0);
    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v]) {
            if (d[to] == inf) {
                d[to] = d[v] + 1;
                q.push(to);
            }
        }
    }
    if (d[n - 1] == 2)
        printf("POSSIBLE");
    else
        printf("IMPOSSIBLE");
    

    return 0;
}

Measured memory_bytes: 13168
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a,b,c;
    cin >> a >> b >> c;
    int d = 0;
    if(b <= c)
    {
        d += b * 2;
        c -= b;
        b = 0;
    }
    if(b > c){
        d += b;
        d += c;
        b = 0; c = 0;
    }
    if(c > 0 && a > 0 && c <= a)
    {
        d += c;
        c = 0;
    }
    else if( c > 0 && a > 0 && c > a){
        d += a;
        c-= a;
    }
    if(c > 0)
    d++;
    cout << d << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i=(b) - 1;i>=(a);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
#define RREP(i,n) for(int i=n-1;i>=0;i--)

#define PB push_back
#define INF (1<<29)
#define ALL(a) (a).begin(),(a).end()
#define RALL(a) (a).rbegin(),(a).rend()
#define CLR(a) memset(a,0,sizeof(a))
const int dx[] = {-1,0,0,1},dy[] = {0,1,-1,0};

typedef long long int ll;

using namespace std;

int main(){
    while(true){
	int n,k;
	cin >> n >> k;
	if(n == 0 && k == 0) break;
	ll a[100001];
	REP(i,n){
	    cin >> a[i];
	}
	REP(i,n-1){
	    a[i+1] += a[i];
	}
	ll ans = -1000000000000000;
	FOR(i,k,n){
	    ans = max(ans,a[i] - a[i-k]);
	}
	cout << ans << endl;
    }
    return 0;
}

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

//積でやるの諦めた。

ll fibo(int n,vector<ll> &memo){
    if(memo[n] != -1) return memo[n];
    else if(n==0) return 1;
    else if(n==1) return 1;
    return memo[n]=(fibo(n-1,memo)+fibo(n-2,memo))%(ll)1000000007;
}


int main(){
    vector<ll> memo(100010,-1);
    int n,m; cin >> n >> m;
    rep(i,m){
        int tt;
        cin >> tt;
        memo[tt]=0;
    } 
    cout << fibo(n,memo) << endl;
}

Measured memory_bytes: 5760
def solve(x):
	if x == []:
		return 0
	if len(x) == 1:
		ans = x[0]
		return ans
	ans = x[0] * 2 ** (len(x) - 2) + solve(x[1:]) + solve([x[0] * 10 + x[1]] + x[2:])
	return ans
S = input()
T = []
for i in S:
	T.append(int(i))
print(solve(T))

Measured memory_bytes: 3060
#include<iostream>
#include<cstdlib>
using namespace std;
 
bool D(int p,int q,int m,int n)
{
  if((m*p+n*q)%(m*m+n*n)==0 && (m*q-n*p)%(m*m+n*n)==0)return true;
  return false;
}
 
bool judge(int p,int q)
{
  int c=0;
  for(int i=0;i*i<=p*p+q*q;i++){
    for(int j=0;j*j<=p*p+q*q;j++){
      if(i+j==0)continue;
      if(D(p,q,i,j))c++;
      if(j!=0 && D(p,q,i,-j))c++;
      if(i!=0 && D(p,q,-i,j))c++;
      if(i!=0 && j!=0 && D(p,q,-i,-j))c++;
    }
  }
  if(c==8)return true;
  return false;
}
 
int main()
{
  int n,m,N;
  cin>>N;
  for(int i=0;i<N;i++){
    cin>>m>>n;
    if(judge(m,n))cout<<"P"<<endl;
    else cout<<"C"<<endl;
  }
  return 0;
}

Measured memory_bytes: 1152
#include<bits/stdc++.h>
#define clr(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long ll;

int n;
string s;
int main(){
    cin >> n;
    cin >> s;
    int cnt = 1;
    for (int i = 1; i < s.size(); i++) {
        if (s[i] != s[i - 1]) cnt++;
    }
    cout << cnt << endl;
}



Measured memory_bytes: 512
s=int(input())
s2=s//3
sm=0
import math
for i in range(1,s2+1):
  #iこに区切る, s-3iがフリー
  sm=(sm+math.factorial(s-3*i+i-1)//math.factorial(s-3*i)//math.factorial(i-1))%(10**9+7)
  
print(sm%(10**9+7))

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

using namespace std;

int n, cnt[26], c2[26], y[200005], z[200005], ta, tb, tc;
char x[200005];
vector< int > v[26];
long long ans;

void go(int a, int b) {
	if (a + 1 == b)
		return;
	int mi = (a + b) / 2;
	go(a, mi);
	go(mi, b);
	ta = a, tb = mi, tc = a;
	// printf("[%d %d]\n", a, b);
	// for (int i = a; i < b; i++) printf("%d%c", y[i], i == b - 1 ? '\n' : ' ');
	while (ta < mi || tb < b) {
		if (tb == b || (ta < mi && y[ta] < y[tb])) {
			z[tc] = y[ta];
			ta++;
		} else {
			ans += mi - ta;
			z[tc] = y[tb];
			tb++;
		}
		tc++;
	}
	// for (int i = a; i < b; i++) printf("%d%c", z[i], i == b - 1 ? '\n' : ' ');
	memcpy(y + a, z + a, 4 * (b - a));
}

int main() {
	scanf("%s", x);
	n = strlen(x);
	for (int i = 0; i < n; i++) {
		x[i] -= 'a';
		cnt[x[i]]++;
	}
	for (int i = 0; i < 26; i++)
		ta += cnt[i] % 2;
	if (ta > 1)
		printf("-1\n");
	else {
		ta = 0;
		for (int i = 0; i < n; i++) {
			if (c2[x[i]] < cnt[x[i]] / 2) {
				y[i] = ta;
				v[x[i]].push_back(ta);
				ta++;
			} else if (c2[x[i]] * 2 + 1 == cnt[x[i]])
				y[i] = n / 2;
			else {
				y[i] = n - 1 - v[x[i]].back();
				v[x[i]].pop_back();
			}
			c2[x[i]]++;
			// printf("%d%c", y[i], i == n - 1 ? '\n' : ' ');
		}
		//for (int i = 0; i < n; i++) printf("%d%c", y[i], i == n - 1 ? '\n' : ' ');
		go(0, n);
		// for (int i = 0; i < n; i++) printf("%d%c", y[i], i == n - 1 ? '\n' : ' ');
		printf("%lld\n", ans);
	}
	return 0;
}

Measured memory_bytes: 2684
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

n = I()

if n < 10:
    print(0)
    quit()

if n % 2:
    print(0)
    quit()

else:
    ans = n//10
    tmp = 10
    cnt = 0
    while n//tmp > 0:
        tmp = (tmp//2)*10
        ans += (n//tmp)
        cnt += 1
        
    print(ans)

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

int main() {
  unsigned num_mountain;
  std::cin >> num_mountain;
  std::vector<unsigned> takahashi(num_mountain);
  std::vector<unsigned> aoki(num_mountain);
  std::vector<bool> takahashi_change(num_mountain);
  std::vector<bool> aoki_change(num_mountain);
  unsigned tmp = 0u;
  for (auto i = 0u; i < num_mountain; ++i) {
    std::cin >> takahashi[i];
    takahashi_change[i] = tmp != takahashi[i];
    tmp = takahashi[i];
  }
  tmp = 0u;
  for (auto i = 0u; i < num_mountain; ++i) {
    std::cin >> aoki[i];
  }
  for (auto i = num_mountain; i > 0; --i) {
    aoki_change[i - 1] = tmp != aoki[i - 1];
    tmp = aoki[i - 1];
  }
  unsigned long long ans = 1ull;
  for (size_t i = 0; i < num_mountain; ++i) {
    if (takahashi_change[i]) {
      if (takahashi[i] > aoki[i]) {
        std::cout << 0;
        return 0;
      }
      if (aoki_change[i] && takahashi[i] != aoki[i]) {
        std::cout << 0;
        return 0;
      }
      continue;
    } else if (aoki_change[i]) {
      if (takahashi[i] < aoki[i]) {
        std::cout << 0;
        return 0;
      }
      continue;
    } else {
      ans *= std::min(takahashi[i], aoki[i]);
      ans %= 1000000007;
    }
  }
  std::cout << ans;
  return 0;
}

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

signed main(){
	int n,g = 0,cnt[40] = {},ans = 0,prev = 0;
	cin >> n;
	for(int i = 0;i < n;i++){
		int a,tmp = 0;
		cin >> a;
		g ^= a;
		while(a % 2 == 0){
			tmp++;
			a /= 2;
		}
		cnt[tmp]++;
	}
	for(int i = 39;i >= 0;i--){
		if(((g >> i) & 1) != prev){
			if(cnt[i]) ans++;
			else{
				cout << -1 << endl;
				return 0;
			}
		}
		prev = (g >> i) & 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 256
import sys
a,b =  sys.stdin.readline().rstrip().split(" ")
#文字列で受け取れば，下のほうの少数桁に影響されることが少なくなる．
#入力で1.10だとしても，本当に1.10とは限らないよってこと
B =b.split(".")
#print(B)
ans = int(a)*(int(B[0])*100+int(B[1]))
print(ans//100)

Measured memory_bytes: 9152
#include<iostream>
#define N 1000000
using namespace std;

int a[N];
int partition(int p,int r){
  int t,x,i;
  x=a[r],i=p-1;
  for(int j=p;j<r;j++)if(a[j]<=x)i++,t=a[i],a[i]=a[j],a[j]=t;
  a[r]=a[i+1],a[i+1]=x;
  return i+1;
}

int main(){
  int n;
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  int t=partition(0,n-1);
  for(int i=0;i<t;i++)cout<<a[i]<<" ";
  cout<<"["<<a[t]<<"] ";
  for(int i=t+1;i<n-1;i++)cout<<a[i]<<" ";
  cout<<a[n-1]<<endl;
  return 0;
}

Measured memory_bytes: 1552
#  Copyright: this code was written at 2020. for AtCoder by Silviase

# Lib
import math


def mod_comb(n1, n2):
    return fac_tab[n1] * fac_tab[n2].inv() * fac_tab[n1 - n2].inv()


class ModInt:
    MOD = int(1e9 + 7)

    # int (演算子) ModIntはダメ

    def __init__(self, x):
        self.x = x % self.MOD

    # ModInt(op){ModInt, Int}に対応している
    def __add__(self, other):
        return self.__class__((self.x + other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x + other) % self.MOD)

    def __sub__(self, other):
        return self.__class__((self.x - other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x - other) % self.MOD)

    def __mul__(self, other):
        return self.__class__((self.x * other.x) % self.MOD) if isinstance(other, ModInt) else self.__class__(
            (self.x * other) % self.MOD)

    # 逆元をかけることに等しい
    def __truediv__(self, other):
        return self.__mul__(other.inv()) if isinstance(other, ModInt) else self.__mul__(ModInt(other).inv())

    # powは第三引数まで指定することで最適化される
    def __pow__(self, power, Modulo=MOD):
        return self.__class__(pow(self.x, power, Modulo))

    def _fac(self):
        mx = ModInt(1)
        for _i in range(self.x, 1, -1):
            mx = mx * _i
        return mx

    # mi_C_kをModInt型で返す
    def _comb(self, _k):
        if isinstance(_k, ModInt):
            if self < _k:
                return ModInt(0)
            return self._fac() * _k._fac().inv() * (self - _k)._fac().inv()
        else:
            if self < _k:
                return ModInt(0)
            return self._fac() * ModInt(_k)._fac().inv() * ModInt(self.x - _k)._fac().inv()

    def inv(self):
        return self.__pow__(self.MOD - 2)

    def __str__(self):
        return str(self.x)

    def __lt__(self, other):
        return self.x < other.x if isinstance(other, ModInt) else self.x < other


# Lib

# Code
# 素因数分解はルートまで,それ以上で残ったら一つ追加していけばいいことがわかる
# 各素因数についてx個あるのであれば(n+x)Cxであればいいことがわかる
# factに関しては毎回計算すると爆発するのでtableを持っておけばいいことがわかる
n, k = map(int, input().split())
result = ModInt(1)
fac_tab = [ModInt(1)] * 200000
for i in range(1, len(fac_tab)):
    fac_tab[i] = fac_tab[i - 1] * i

for i in range(2, int(math.sqrt(k) + 1)):
    tmp_cnt = 0
    while k % i == 0:
        k /= i
        tmp_cnt += 1
    result = result * mod_comb(n + tmp_cnt - 1, tmp_cnt)
    # print(result)

if k != 1:
    result = result * n
print(str(result))


Measured memory_bytes: 60124
time = 0
order_list = []

for i in range(5):
    order_list.append(int(input()))

for i in range(4):
    next_order = order_list[i+1] % 10 if order_list[i+1] % 10 != 0 else 10
    if order_list[i] % 10 < next_order:
        buff = order_list[i]
        order_list[i] = order_list[i+1]
        order_list[i+1] = buff

for i in range(5):
    wait = 10 - order_list[i] % 10
    if wait == 10 or i == 4:
        wait = 0
    time += order_list[i] + wait

print(time)

Measured memory_bytes: 3064
depth = int(input())
vertex = input().split(' ')
vertex = [int(x) for x in vertex]

maxs = []
v_cnt = 1
is_error = False
for i in range(depth + 1):
    v_cnt -= vertex[i]
    if v_cnt > 0 or (i == depth and v_cnt >=0):
        maxs.append(v_cnt)
        v_cnt *= 2
    else:
        is_error = True
        break

output = 0
if is_error:
    output = -1
else:
    for i in range(depth, -1, -1):
        if i == depth:
            output += vertex[i]
            next_v = vertex[i]
        else:
            next_v = min([maxs[i], next_v]) + vertex[i]
            output += next_v
print(output)

Measured memory_bytes: 668632
#include <iostream>

using namespace std;

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  int fcount = 0;
  int scount = 0;
  if (A == 5){fcount+=1;}
  if (B == 5){fcount+=1;}
  if (C == 5){fcount+=1;}
  if (A == 7){scount+=1;}
  if (B == 7){scount+=1;}
  if (C == 7){scount+=1;}
  if (fcount==2 and scount==1){
    cout << "YES" << endl;
  }
  else{
    cout << "NO" << endl;
  }
}


Measured memory_bytes: 256
#include<stdio.h>
int main(){
  int N,K,ok;
  scanf("%d%d",&N,&K);
  int h[N];
  ok=0;
  for(int i=0;i<N;i++){
    scanf("%d",&h[i]);
    if(h[i]>=K)
      ok++;
  }
  printf("%d\n",ok);
  return 0;
}

Measured memory_bytes: 512
C=[list(map(int,input().split())) for i in range(3)]
for n in range(0,2):
  x=C[0][2]-C[0][n]
  y=C[1][2]-C[1][n]
  z=C[2][2]-C[2][n]
  if x!=y or y!=z :
    print('No')
    exit()
else:
  print('Yes')

Measured memory_bytes: 3064
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <queue>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> ps(n);
    for (int i = 0; i < n; ++i) {
        cin >> ps[i];
    }
    vector<int> sums(n);
    for (int i = 0; i < n; ++i) {
        sums[i] = (1 + ps[i]) * ps[i] / 2;
    }
    double ans = 0;
    for (int i = 0; i < k; ++i) {
        ans += (double)sums[i] / (double)ps[i];
    }
    double cur = ans;
    for (int i = k; i < n; ++i) {
        cur -= (double)sums[i - k] / (double)ps[i - k];
        cur += (double)sums[i] / (double)ps[i];
        ans = max(ans, cur);
    }
    printf("%.10f\n", ans);
    return 0;
}


Measured memory_bytes: 1792
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cassert>
#define ll long long
using namespace std;
inline int read(){
	int re=0,flag=1;char ch=getchar();
	while(ch>'9'||ch<'0'){
		if(ch=='-') flag=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9') re=(re<<1)+(re<<3)+ch-'0',ch=getchar();
	return re*flag;
}
int first[100010],cnte,dep[100010],ans=0,n,k;
struct edge{
	int to,next;
}a[100010];
inline void add(int u,int v){
	a[++cnte]=(edge){v,first[u]};first[u]=cnte;
}
int dfs(int u,int f){
//	cout<<"dfs "<<u<<' '<<f<<'\n';
	dep[u]=dep[f]+1;
	int i,v,maxdis=1;
	for(i=first[u];~i;i=a[i].next){
		v=a[i].to;maxdis=max(maxdis,dfs(v,u));
	}
	if(u!=1) assert(maxdis<=k);
//	cout<<"maxdis "<<u<<' '<<maxdis<<'\n';
	if(maxdis==k&&u!=1&&f!=1){
		ans++;return 0;
	}
	return maxdis+1;
}
int main(){
	memset(first,-1,sizeof(first));
	n=read();k=read();int i,t1;
	for(i=1;i<=n;i++){
		t1=read();
		if(i!=1) add(t1,i);
		if(i==1&&t1!=1) ans++;
	}
	dfs(1,0);
	printf("%d\n",ans);
}

Measured memory_bytes: 6528
n =gets.chomp.to_i
a = gets.chomp.split(" ").map{|u|u.to_i}
a[0,n-1].each do |d|
  print("#{d} ")
end
puts "#{a[n-1]}"
(1..n-1).each do |i|
  v = a[i]
  j = i - 1
  while(j >= 0 and a[j] > v)
    a[j+1] = a[j]
    j -= 1
  end
  a[j+1] = v
a[0,n-1].each do |d|
  print("#{d} ")
end
puts "#{a[n-1]}"
end

Measured memory_bytes: 8732
#include<bits/stdc++.h>
#define REP(i,n) for(int i=0;i<n;i++)
#define LOOP(i,x,n) for(int i=x;i<n;i++)
#define ALL(v) (v).begin(),(v).end()
#define PB push_back
#define MP make_pair
#define FIR first
#define SEC second
#define int long long
using namespace std;
const int MOD=1000000007;
const int INF=1000000009;

signed main(){
  int n;
  cin>>n;
  vector<int> v;
  REP(i,35000)v.PB(i*i);
  LOOP(i,1,35000){
    if(v[i]>n){
      cout<<v[i-1]<<endl;
      return 0;
    }
  }
  return 0;
}


Measured memory_bytes: 892
var N = 0
var A = 0

fun main(args: Array<String>) {
    readLine()?.split(" ")?.map {
        it.toInt()
    }?.let {
        N = it[0]
        A = it[1]
    }


    val x = IntArray(N + 1)
    readLine()?.split(" ")?.map {
        it.toInt()
    }?.forEachIndexed { i, n ->
        x[i + 1] = n
    }

    val dp = Array(N + 1) {
        Array(N + 1) {
            LongArray(N * A + 1)
        }
    }
    for (i in 0..N) {
        dp[i][0][0] = 1
    }

    for (i in 1..N) {
        for (j in 1..i) {
            for (k in 1..(N * A)) {
                dp[i][j][k] = if (k < x[i]) {
                    dp[i - 1][j][k]
                } else {
                    dp[i - 1][j][k] + dp[i - 1][j - 1][k - x[i]]
                }
            }
        }
    }

    var ans = 0L
    for (j in 1..N) {
        ans += dp[N][j][j * A]
    }

    println(ans)
}



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

int main(){

  int n,m;
  int taro[100]={0},hana[100]={0};
  int sumt,sumh;
  int numt,numh;
  int min;

  while(cin >> n >> m){
    if(n==0 && m==0){ break; }

    sumt=sumh=0;
    min = -1;

    for(int i=0; i<n; i++){
        cin >> taro[i];
        sumt+=taro[i];
    }
    for(int i=0; i<m; i++){
        cin >> hana[i];
        sumh+=hana[i];
    }

    for(int i=0; i<n; i++){
      for(int j=0; j<m; j++){
        if(sumt-taro[i]+hana[j]==sumh-hana[j]+taro[i]){
          //cout << "hit" << endl;
          if(min==-1 || min>sumt-taro[i]+hana[j]){
            min = sumt-taro[i]+hana[j];
            numt=i , numh=j;
          }
        }
      }
    }

    if(min == -1){
      cout << -1 << endl;
    }
    else{
      cout << taro[numt] << ' ' << hana[numh] << endl;
    }

  }

  return 0;
}

Measured memory_bytes: 1156
#include <iostream>
using namespace std;
int main(void){
    // Your code here!
    int H,A;
    cin >> H >> A;
    int W = H % A;
    if(W == 0){
        cout << H / A << endl;
    }
    else{
        cout << H / A + 1 << endl;
    }
}


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

int main() {
    int k, s;
    cin >> k >> s;
    int count = 0;
    for (int x = 0; x <= k; x++) {
        if (x > s) continue;
        int ypz = s - x;
        if (ypz < k)
            count += (ypz + 1);
        else if (ypz >= k && ypz <= 2 * k)
            count += (k - (ypz - k) + 1);
        else
            count += 0;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3528
N=int(input())
A = [int(i) for i in input().split()]
left = [0] * N
right = [0] * N
for i,a in enumerate(A):
    if 0 <= i-a:
        left[i - a] += 1
    if i + a < N:
        right[i + a] += 1
ans = 0
for i in range(N):
    ans += left[i] * right[i]
print(ans)

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

using namespace std;

class light
{
public:
    light(){ p=0; mask = 0x0000; }

    int p;
    unsigned short int mask;
};

int main()
{
    int N, M;
    unsigned short int sw = 0x0000;

    cin >> N >> M;

    vector<light> light_all;

    light_all.resize(M);

    for(int i=0; i<M; i++){
        int k;

        cin >> k;

        for(int j=0; j<k; j++){
            int s;

            cin >> s;

            light_all[i].mask |= 0x0001 << (s - 1);
        }
    }

    for(int i=0; i<M; i++){
        int p;

        cin >> p;

        light_all[i].p = p;
    }

    int loop = pow(2, N);
    int sum = 0;

    // すべてのスイッチパターンを検索
    for(int i=0; i<loop; i++){
        bool all = true;

        // すべての電球を検索
        for(int j=0; j<M; j++){
            unsigned short int on = 0x0000;

            on = sw & light_all[j].mask;

            int count = 0;
            for(int k=0; k<N; k++){
                if( (on & (0x0001 << k)) > 0){
                    count++;
                }
            }

            if( (count % 2) != light_all[j].p){
                all = false;
            }
        } 

        if(all){
            sum++;
        }

        sw += 0x0001;
    }

    cout << sum << endl;

    return 0;
}

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

using namespace std;

int main(int argc, char const *argv[]) {
	unsigned long long N;
	std::cin >> N;
	std::vector<unsigned long long> v;
	v.push_back(2);
	v.push_back(1);
	for (size_t i = 2; i < N+1; i++) {
		v.push_back(v[i-1] + v[i-2]);
	}
	std::cout << v[N] << '\n';
	return 0;
}


Measured memory_bytes: 256