akhauriyash/Code-Regression huggingface dataset:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please

inline int getint_mae() {
	char C = getchar_unlocked();
	int A = C - '0';
	while (isdigit(C = getchar())) A = A * 10 + C - '0';
	return A;
}

const int cm = 1 << 17;
char cn[cm], *ci = cn + cm, ct;
inline char getcha() {
	if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; }
	return *ci++;
}
inline int getint() {
	int A = 0;
	if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0';
	else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0';
	return A;
}

const int dm = 1 << 21;
char dn[dm], *di = dn, dt;
inline void putint(int X) {
	if (X == 0) {
		*di++ = '0';
		*di++ = '\n';
		return;
	}
	int keta = 0;
	char C[10];
	while (X) {
		*(C + keta) = '0' + X % 10;
		X /= 10;
		keta++;
	}
	for (int i = keta - 1; i >= 0; i--) *di++ = (*(C + i));
	*di++ = '\n';
}

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


	int N = getint_mae(), M = getint_mae(), Q = getint_mae();
	char S[2000][2001];
	rep(i, N) fread_unlocked(S[i], 1, M + 1, stdin);
	int B[2001][2001], C[2001][2001], D[2001][2001];
	rep(i, M + 1) {
		B[0][i] = 0;
		C[0][i] = 0;
		D[0][i] = 0;
	}
	rep(i, N + 1) {
		B[i][0] = 0;
		C[i][0] = 0;
		D[i][0] = 0;
	}
	rep(i, N) {
		rep(j, M) {
			B[i + 1][j + 1] = B[i + 1][j] + B[i][j + 1] - B[i][j] + S[i][j] - '0';
			if (i != 0) C[i + 1][j + 1] = C[i + 1][j] + C[i][j + 1] - C[i][j] + ((S[i - 1][j] - '0') & (S[i][j] - '0'));
			if (j != 0) D[i + 1][j + 1] = D[i + 1][j] + D[i][j + 1] - D[i][j] + ((S[i][j - 1] - '0') & (S[i][j] - '0'));
		}
	}

	rep(q, Q) {
		int a = getint(), b = getint(), c = getint(), d = getint();

		int kotae = B[c][d] - B[c][b - 1] - B[a - 1][d] + B[a - 1][b - 1] - C[c][d] + C[c][b - 1] + C[a][d] - C[a][b - 1] - D[c][d] + D[c][b] + D[a - 1][d] - D[a - 1][b];
		putint(kotae);

	}

	fwrite_unlocked(dn, di - dn, 1, stdout);

	Would you please return 0;
}

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

using namespace std;

int main()
{
	int w, n, t, a, b, i;
	char c;
	cin >> w;
	vector<int> state(w);
	for (i = 1; i <= w; i++) state[i-1] = i;

	cin >> n;
	for (i = 0; i < n; i++) {
		cin >> a >> c >> b;
		t = state[a-1];
		state[a-1] = state[b-1];
		state[b-1] = t;
	}
	for (i = 0; i < w; i++) cout << state[i] << endl;
	return 0;
}

Measured memory_bytes: 1192
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
int A[200];
int main()
{
    int n,sun;
    scanf("%d %d",&n,&sun);
    int zui=99999999;
    for(int i=0;i<n;i++)
    {
            scanf("%d",&A[i]);
            sun=sun-A[i];
            if(A[i]<zui)
                zui=A[i];
    }
    int temp=sun/zui;
    temp=temp+n;
    printf("%d\n",temp);
    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
typedef long long ll;
typedef long double ld;
#define rep(i,n) for(ll i=0;i<(n);i++)
#define repr(i,n) for(ll i=(n-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define br cout << "\n";
using namespace std;
const long long INF = 1e9;
const long long MOD = 1e9+7;
using Graph = vector<vector<ll>>;
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;}

// 0 false, 1 true 
// string to int : -48
// a to A : -32
// ceil(a)  1.2->2.0
// c++17	g++ -std=c++17 a.cpp

int main() {
    std::cout << std::fixed << std::setprecision(15);
    ll q; cin >> q;
    rep(Q, q){
        string s, t; cin >> s >> t;
        ll s_size = s.size(), t_size = t.size();

        vector<vector<ll>> dp(s_size+1, vector<ll>(t_size+1));

        for(ll i = 0; i < s_size; i++){
            for(ll j = 0; j < t_size; j++){
                if(s[i] == t[j]){
                    dp[i+1][j+1] = dp[i][j] + 1;
                }else{
                    dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
                }
            }
        }

        cout << dp[s_size][t_size] << endl;

    }

}


Measured memory_bytes: 10772
#include <iostream>
#include <numeric>
#include <cstring>
#include <cmath>
#include <vector>
#include <algorithm>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <set>
#include <map>
#include <iterator>
#include <stack>
#include <string.h>
#include <cstdlib>
#include <queue>
#include <list>
#include <string>
#include <iterator>
#include <iomanip>
#define rep(i,n) for(int i = 0; i < (n); i++) 
using namespace std;

int main() {
    long long int n;
    string str;
    bool flag = true;
    cin >> str;
    rep(i,str.size()-1) {
        if(str[i] == str[i+1]){
            flag = false;
        }
    }
    if (flag) {
        cout << "Good" << endl;
    } else {
        cout << "Bad" << endl;
    }
    
    return 0;
}

Measured memory_bytes: 256
using System;

namespace B
{
    class Program
    {
        static void Main(string[] args)
        {
            int k =  Int32.Parse(Console.ReadLine().Trim());
            var s =  Console.ReadLine().Trim();
            Console.WriteLine(s.Length > k ? s.Substring(0, k) + "..." : s);
        }
    }
}


Measured memory_bytes: 17484
import java.util.*;

public class Main {
	
  	public static void main(String args[]) {
    	Scanner sc = new Scanner(System.in);
      	String input = sc.nextLine();
      	if(input.substring(0,1).equals(input.substring(2,3))) {
          	System.out.println("Yes");
        }
      	else {
          System.out.println("No");
        }
      
    }

}

Measured memory_bytes: 21716
#include<iostream>
#include<string>
using namespace std;
int main(){
    string str;
    cin >> str;
    int sz;
    sz = str.size();
    int sm=0;
    for(int i=0; i<sz; i++){
        int tmp = str[i]-'0';
        sm = sm + tmp;
    }
    if(sm%9==0){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}



Measured memory_bytes: 3716
#include <bits/stdc++.h> // Integer Product, by Errichto
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    map<pair<int,int>, int> cnt;
    for(int rep = 0; rep < n; ++rep) {
        double x;
        scanf("%lf", &x);
        long long i = llround(x * 1e9);
        int two = 0, five = 0;
        while(i % 2 == 0) {
            two++;
            i /= 2;
        }
        while(i % 5 == 0) {
            five++;
            i /= 5;
        }
        ++cnt[{two,five}];
    }
    long long answer = 0;
    for(auto p1 : cnt) {
        for(auto p2 : cnt) {
            if(p1.first.first+p2.first.first >= 18 && p1.first.second+p2.first.second >= 18) {
                if(p1 < p2) {
                    answer += (long long) p1.second * p2.second;
                }
                else if(p1 == p2) {
                    answer += (long long) p1.second * (p1.second - 1) / 2;
                }
            }
        }
    }
    printf("%lld\n", answer);
}

Measured memory_bytes: 3804
#include <bits/stdc++.h>
using namespace std;
int n,a[101],res;
int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>a[i];
  sort(a,a+n,greater<int>());
  for(int i=0;i<n;i++)res+=a[i]*(i%2 ? -1:1);
  cout<<res;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) FOR(i, 0, n)
#define ll long long
using namespace std;

int gcd(int a, int b) { return b != 0 ? gcd(b, a % b) : a; }
int lcm(int a, int b) { return a * b / gcd(a, b); }

int main()
{
  int m, d;
  cin >> m >> d;
  int ans = 0;
  FOR(i, 1, m + 1)FOR(j, 22, d + 1) {
    int d1 = j % 10, d10 = j / 10;
    if (d1 < 2 || d10 < 2) continue;
    if (d1 * d10 == i) ans++;
  }
  cout << ans << endl;
  return 0;
}


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

#define f first 
#define s second 
#define pb push_back               
#define mp make_pair 

using namespace std;                    

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;

const int N = (int)5e5 + 123, mod = (int)1e9 + 7, inf = (int)1e9;
int n, k, a[N], b[N], t[4*N], cnt[N], c[N];
vector< int > up[N];

void upd(int v, int tl, int tr, int pos, int val){
	if(tl == tr){
		t[v] = val;
		return ;
	}
	int tm = (tl + tr) / 2;
	if(pos <= tm)
		upd(v + v, tl, tm, pos, val);
	else
		upd(v + v + 1, tm + 1, tr, pos, val);
	t[v] = min(t[v + v], t[v + v + 1]);
}
int get(int v, int tl, int tr, int l, int r){
	if(r < tl || tr < l)
		return inf;
	if(l <= tl && tr <= r)
		return t[v];
	int tm = (tl + tr) / 2;
	return min(get(v + v, tl, tm, l, r), get(v + v + 1, tm + 1, tr, l, r));
}

int main(){    

	scanf("%d%d", &n, &k);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
		b[a[i]] = i;
	}
	a[n + 1] = b[n + 1] = n + 1;
	for(int i = 1; i <= n; i++)
		upd(1, 1, n, i, n + 1);
	for(int i = n; i >= 1; i--){
		int x = b[i];
		int l = get(1, 1, n, x - k + 1, x);
		int r = get(1, 1, n, x, x + k - 1);
		upd(1, 1, n, x, i);
		/*
		for(int i = 1; i <= n; i++)
			cerr << get(1, 1, n, i, i) << " ";
		cerr << endl;
		*/
		up[b[l]].pb(i);
    	up[b[r]].pb(i);
    }
    
    priority_queue< int > q;
    vector< int > ans;
    q.push(n + 1);
    
    while(!q.empty()){
    	int v = q.top();
    	ans.pb(v);
    	q.pop();
    	for(int i = 0; i < up[v].size(); i++){
    		int x = up[v][i];
    		cnt[x]++;
    		if(cnt[x] == 2)
    			q.push(b[x]);
    	}	
    }
    
    reverse(ans.begin(),ans.end());
    //sadsad
    for(int i = 0; i < n; i++)
    	c[ans[i]] = i + 1;
    for(int i = 1; i <= n; i++)
    	cout << c[i] << endl;
	return 0;
}

Measured memory_bytes: 48496
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <deque>
#include <queue>
#include <array>
#include <set>
#include <map>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility>
#include <tuple>
#include <functional>
#include <bitset>
#include <cstdint>
#include <cassert>
#include <random>

using namespace std;
using i64 = int64_t;
using i32 = int32_t;
template<class T, class U> void init_n(vector<T>& v, size_t n, U x) 
{ v = vector<T>(n, x); }
template<class T> void init_n(vector<T>& v, size_t n) { init_n(v, n, T()); }
template<class T> void read_n(vector<T>& v, size_t n, size_t o = 0) 
{ v = vector<T>(n+o); for (size_t i=o; i<n+o; ++i) cin >> v[i]; }
template<class T> void read_n(T a[], size_t n, size_t o = 0)
{ for (size_t i=o; i<n+o; ++i) cin >> a[i]; }
template<class T> T gabs(const T& x) { return max(x, -x); }
#define abs gabs

int main() {
    i64 n;
    cin >> n;
    string s;
    if (n >= 0) {
        s += n % 2 == 0 ? '0' : '1';
        n >>= 1;
    } else {
        n = -n;
    }

    for (; n > 0; n >>= 2) {
        int x = n & 3;
        if (x == 0) {
            s += "00";
        }
        if (x == 1) {
            s += "11";
            n -= 1;
        }
        if (x == 2) {
            s += "01";
            n -= 2;
        }
        if (x == 3) {
            s += "10";
            n += 1;
        }
    }

    while (s.size() >= 2 && s.back() == '0') {
        s.pop_back();
    }
    reverse(begin(s), end(s));

    cout << s << endl;
    return 0;
}

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

int main(){
  int n;
  cin >> n;
  vector<string> S(n);
  for (int i=0;i<n;i++){
    cin >> S[i];
  }
  string A="abcdefghijklmnopqrstuvwxyz";
  map<char,int> m;
  for (int i=0;i<26;i++){
    m[A[i]]=51;
  }
  for (int i=0;i<n;i++){
    map<char,int> mx;
    int s=S[i].size();
    for (int j=0;j<s;j++){
      mx[S[i][j]]++;
    }
    for (int j=0;j<26;j++){
      m[A[j]]=min(m[A[j]],mx[A[j]]);
    }
  }
  string ans="";
  for (int i=0;i<26;i++){
    for (int j=0;j<m[A[i]];j++){
      ans+=A[i];
    }
  }
  cout << ans << endl;
}

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

int main() {
  int A,B,i,s,t,u,v,count=0;

  cin >> A >> B;

  for (i=A; i<=B; i++) {
    s = i/10000 % 10;
    t = i%10;
    u = i/1000 % 10;
    v = i/10 % 10;

    if (s==t && u == v) count++;
  }
  cout << count << endl;
}


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

#define REP(i,n) for(ll i=0;i<ll(n);++i)
#define RREP(i,n) for(ll i=ll(n)-1;i>=0;--i)
#define FOR(i,m,n) for(ll i=m;i<ll(n);++i)
#define RFOR(i,m,n) for(ll i=ll(n)-1;i>=ll(m);--i)
#define ALL(v) (v).begin(),(v).end()
#define UNIQUE(v) v.erase(unique(ALL(v)),v.end());
#define INF 1000000001ll
#define MOD 1000000007ll
#define EPS 1e-9

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


using namespace std;

using ll = long long;
using vi = vector<int>;
using vl = vector<ll>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

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


int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vi a(n), b(n), c(n - 1);
	REP(i, n)cin >> a[i];
	REP(i, n)cin >> b[i];
	REP(i, n - 1)cin >> c[i];
	int ans = 0;
	REP(i, n)ans += b[i];
	REP(i, n - 1) {
		if (a[i] + 1 == a[i + 1]) {
			ans += c[a[i] - 1];
		}
	}
	cout << ans << endl;
}

Measured memory_bytes: 256
def frac_with_mod(a,m):
    outlist = [ 1 for i in range(a+1) ]
    for i in range(1,a+1):
        outlist[i] = (outlist[i-1] * i)% m
    return outlist

frac_list = frac_with_mod(2*10**5,10**9+7)

def comb_with_mod(a,b,m):
    global frac_list
    return ( frac_list[a+b-2] * pow(frac_list[a-1],m-2,m) * pow(frac_list[b-1],m-2,m) ) % m

mod = 10**9+7
h, w, a, b = [ int(v) for v in input().split() ]

c = h - a
d = w - b


if c == 1:
    waypoint_list = [ 1 for i in range(d) ]
else:
    waypoint_list = [ comb_with_mod(b+1+i,c-1,mod) for i in range(d) ]
    s = comb_with_mod(b,c,mod)

    for i in range(d):
        waypoint_list[i] = ( s + waypoint_list[i] ) % mod
        s = waypoint_list[i]
        waypoint_list[i] = ( comb_with_mod(a,d-i,mod) * waypoint_list[i] ) % mod

print(sum(waypoint_list)%mod)

Measured memory_bytes: 59212
N = int(input())
dp = [[0] * 4 for i in range(N+1)]
MOD = 10**9+7
dp[0][0] = 1
for i in range(1,N+1):
    dp[i][0] = (dp[i-1][0] * 8) % MOD
    dp[i][1] = (dp[i-1][0] + dp[i-1][1]*9) % MOD
    dp[i][2] = (dp[i-1][0] + dp[i-1][2]*9) % MOD 
    dp[i][3] = (dp[i-1][3]*10 + dp[i-1][1] + dp[i-1][2]) % MOD
#print(dp)
print(dp[N][3])


Measured memory_bytes: 198368
C = int(1e9) + 7
h, w, a, b = [int(x) for x in input().split()]

fact = [1]
for x in range(1, h + w - 2):
    fact.append((x * fact[x - 1]) % C)

factinv = [1] * (h + w - 2)
factinv[h + w - 3] = pow(fact[h + w - 3], C - 2, C)
for x in reversed(range(2, h + w - 3)):
    factinv[x] = (factinv[x + 1] * (x + 1)) % C

def nCr(n, r):
    return (fact[n] * factinv[r] * factinv[n - r]) % C

ans = 0
for i in range(b, w):
    ans = (ans + nCr(i + h - a - 1, h - a - 1) * nCr(a - 1 + w - i - 1, a - 1)) % C

print(ans)


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

using namespace std;

const int N = 2 * 1e5 + 10;
const int M = 2 * 1e5 + 10;
int n, m, maxn;
int s[N], f[N], fa[N];

int get_fa (int x) {
	if (fa[x] == x) return x;
	else return fa[x] = get_fa (fa[x]);
}

int main () {
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i ++ ) {
		s[i] = 1;
		fa[i] = i;
	}
	for (int i = 1; i <= m; i ++ ) {
		int x, y, fx, fy;
		scanf ("%d%d", &x, &y);
		fx = get_fa (x);
		fy = get_fa (y);
		if (fx == fy) continue;
		else {
			fa[fx] = fy;
			s[fy] += s[fx];
			s[fx] = 0;
		}
	}
	for (int i = 1; i <= n; i ++ ) maxn = max (maxn, s[i]);
	printf ("%d\n", maxn);
	return 0;
}

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

int main()
{
    long double a,b,h,m,rad,deg,ans;
    long double pi = 3.141592653589793238462643383279502884;
    cin>>a>>b>>h>>m;

    h=h+m/60.0;
    deg = h*30 - m*6;
    rad = deg*(pi/180);

    ans =sqrt((a*a)+(b*b)-(2*b*a*cos(rad)));

    printf("%.20Lf\n",ans);

}


Measured memory_bytes: 4136
val = input().split()
val = [int(i) for i in val]

a, b, c, d = val

x1 = val[2] - val[0]
y1 = val[3] - val[1]

import numpy as np

if x1 * y1 > 0:
    x2 = -1 * np.sign(x1) * abs(y1)
    y2 = np.sign(y1) * abs(x1)
    x3 = np.sign(x2) * abs(x1)
    y3 = -1 * np.sign(y2) * abs(y1)
elif x1 == 0:
    x2 = -1 * y1
    y2 = 0
    x3 = 0
    y3 = x2
elif y1 == 0:
    x2 = 0
    y2 = x1
    x3 = -1 * x1
    y3 = 0
else:
    x2 = np.sign(x1) * abs(y1)
    y2 = -1 * np.sign(y1) * abs(x1)
    x3 = -1 * np.sign(x2) * abs(x1)
    y3 = np.sign(y2) * abs(y1)

e = c + x2
f = d + y2
g = e + x3
h = f + y3

print(e, f, g, h)

Measured memory_bytes: 21372
use std::io::*;
const MOD: usize = 1_000_000_007;

fn mod_pow(mut x: usize, mut e: usize) -> usize {
    let mut res = 1;
    while e > 0 {
        if e & 1 == 1 {
            res = res * x % MOD;
        }
        x = x * x % MOD;
        e >>= 1;
    }
    res
}

fn main() {
    let mut s: String = String::new();
    std::io::stdin().read_to_string(&mut s).ok();
    let mut itr = s.trim().split_whitespace();
    let n: usize = itr.next().unwrap().parse().unwrap();
    let k: usize = itr.next().unwrap().parse().unwrap();
    let mut table: Vec<usize> = vec![0; k + 1];
    for i in 1..k + 1 {
        table[i] = mod_pow(k / i, n);
    }

    let mut is_prime: Vec<bool> = vec![true; 100010];
    for i in 2..k + 1 {
        if is_prime[i] {
            for j in 1..k / i + 1 {
                is_prime[i * j] = false;
                table[j] = (table[j] + MOD - table[i * j]) % MOD;
            }
        }
    }
    let mut ans = 0;
    for i in 1..k + 1 {
        ans = (ans + table[i] * i) % MOD;
    }
    println!("{}", ans);
}


Measured memory_bytes: 2744
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
char a[100000+5];
int head=0,tail,len,ans=0;

int main()
{
	scanf("%s",a);
	len=strlen(a);
	tail=len-1;
	while(tail>head)
	{
		if(a[head]!=a[tail]&&a[head]!='x'&&a[tail]!='x') 
		{
			cout<<-1<<endl;
			return 0;
		}
		if(a[head]==a[tail]){head++;tail--;}
		if(a[head]!=a[tail]&&a[head]=='x')
		{
			ans++;
			head++;
		}
		if(a[head]!=a[tail]&&a[tail]=='x')
		{
			ans++;
			tail--;			
		}		
	}
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 384
N = int(input())
D = list(map(int,input().split()))

M = int(input())
T = list(map(int,input().split()))

memo = {}

for d in D:
    if d in memo:
        memo[d] += 1
    else:
        memo[d] = 1
        
for t in T:
    if t in memo and 0 < memo[t]:
        memo[t] -= 1
    else:
        print('NO')
        exit()
print('YES')


Measured memory_bytes: 137576
#include <bits/stdc++.h>
// #include <atcoder/all>
#define FOR(i, a, n) for(int (i) = (int)(a); (i) < (int)(n); ++(i))
#define FORe(i, a, n) for(int (i) = (int)(a); (i) <= (int)(n); ++(i))
#define rFOR(i, a, n) for(int (i) = (int)(n)-1; (i) >= (int)(a); --(i))
#define rFORe(i, a, n) for(int (i) = (int)(n); (i) >= (int)(a); --(i))
#define REP(i, n) FOR((i), 0, (n))
#define REPe(i, n) FORe((i), 1, (n))
#define REPo(i, n) FORe((i), 0, (n))
#define rREP(i, n) rFOR((i), 0, (n))
#define rREPe(i, n) rFORe((i), 1, (n))
#define rREPo(i, n) rFORe((i), 0, (n))
#define rep(i, n) FOR((i), 0, (n))
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define fi first
#define se second
#define dup(x, y) (((x)+(y)-1)/(y))
#define vc(T) vector<T>
#define vv(T) v(v(T))
using namespace std;
// using namespace atcoder;
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using pll = pair<ll,ll>;
using T = tuple<int,int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vs = vector<string>;
using vp = vector<P>;
using vt = vector<T>;

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; }

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

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

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

  mint ans = 0;
  ans += mint(10).pow(n);
  ans -= mint(9).pow(n) * 2;
  ans += mint(8).pow(n);

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 3616
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] a = new int[m];
		int[] b = new int[m];
		for(int i = 0 ; i < m ; i++) {
			a[i] = sc.nextInt() - 1;
			b[i] = sc.nextInt() - 1;
		}
		boolean[] bool1 = new boolean[n];
		boolean[] bool2 = new boolean[n];
		for(int i = 0 ; i < m ; i++) {
			if(a[i] == 0) bool1[b[i]] = true;
			if(b[i] == n - 1) bool2[a[i]] = true;
		}
		for(int i = 1 ; i < n - 1 ; i++) {
			if(bool1[i] && bool2[i]) {
				System.out.println("POSSIBLE");
				return;
			}
		}
		System.out.println("IMPOSSIBLE");
	}
}


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

int main(void)
{
  string s;
  cin >> s;
  
  int count_a = 0, count_b = 0;
  for(int i=0; i<s.size(); i++){
      if(s[i] % 2 == i % 2){
          count_a++;
      }
      else{
          count_b++;
      }
  }
  cout << min(count_a, count_b) << endl;
  
  return 0;
}


Measured memory_bytes: 512
import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, core.stdc.stdio, std.bitmanip;


bool ok(ref long[] A, ref long[] B, long n) {
    long s = n * (n+1) / 2;
    if (A.sum % s != 0)
        return false;
    long m = A.sum / s;
    long x = 0;
    foreach (i; 0..n)
        B[i] -= m;

    foreach (i; 0..n) {
        if (B[i] % n != 0)
            return false;
        long d = abs(B[i] / n);
        x += d;
    }
    return x == m;
}

void main() {
    auto N = readln.chomp.to!long;
    auto A = readln.split.map!(to!long).array;
    auto B = new long[](N);
    foreach (i; 0..N) {
        B[i] = A[(i+1)%N] - A[i];
    }

    writeln(ok(A, B, N) ? "YES" : "NO");
}


Measured memory_bytes: 4540
import queue
N = int(input())
U = input().split()
l = [0 for i in range(N)]
for i in range(N):
    l[i]= int(U[i])

l.sort()
l.reverse()
ans = 0
if N%2 == 0:
    for i in range(N//2):
        ans += 2*l[i]
    ans -= l[0]
else:
    for i in range(1,(N+1)//2-1):
        ans += 2*l[i]
    ans += l[0]+l[(N+1)//2-1]

print(ans)


Measured memory_bytes: 32504
#include<stdio.h>
int main(){
	int a[4],b[4],i,s=0,w=0;
	for(i=0;i<=3;i++){
		scanf("%d",&a[i]);
		s=s+a[i];
	}
	for(i=0;i<=3;i++){
		scanf("%d",&b[i]);
		w=w+b[i];
	}
	if(s>w){
		printf("%d\n",s);
	}
	else{
		printf("%d\n",w);
	}
	return 0;
}

Measured memory_bytes: 592
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;

int stair(int n){
	if(n==1)
		return 1;
	else if(n==2)
		return 2;
	else if(n==3)
		return 4;
	else 
		return stair(n-1)+stair(n-2)+stair(n-3);
}

int main(){
	int n;
	while(scanf("%d",&n) && n!=0){
		int year = stair(n)/3650;
		if(stair(n)%3650!=0)  year++;
		cout<<year<<endl;
	}

	return 0;
}

Measured memory_bytes: 1208
x, k, d = map(int, input().split())
x = abs(x)

if x - k*d >= 0:
  print(x - k*d)
  exit()
  
p = x//d
k -= p
x -= p*d

if k%2 == 0:
  print(x)
  
else:
  print(abs(x-d))

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

int main() {
	int a = 0, b = 0, c = 0, k = 0, sum = 0;
	cin >> a >> b >> c >> k;

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

		if (a > i) {
			sum += 1;
			continue;
		}

		else if (a + b > i) {
			continue;
		}

		else if (a + b + c > i) {
			sum -= 1;
		}
	}

	cout << sum << endl;
}


Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<(n); i++)
int ans;
bool t;
string s;
int main(){
	cin >> s;
	rep(i,s.size()-1){
		if(t){
			t = false;
			s[i+1] = '%';
		}else{
			ans++;
			if(s[i] == s[i+1]){
				t = true;
				if(i == s.size() - 2) ans--;
			}
		}
	}
	printf("%d\n", ans + 1);
}

Measured memory_bytes: 640
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>

#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

struct Lonoid {
  int64_t x;
  Lonoid() {}
  Lonoid(int64_t x) : x(x) {}
  static Lonoid ident() { return Lonoid(0); }
  static Lonoid multiply(Lonoid f, Lonoid g) { return Lonoid(f.x + g.x); }
  bool operator==(const Lonoid &rhs) const { return x == rhs.x; }
};

template <typename L>
struct SegmentTree {
  int n;
  L e;
  vector<L> laz;
  SegmentTree(int n0) {
    n = 1;
    e = L::ident();
    while (n < n0) {
      n *= 2;
    }
    laz.resize(n * 2 - 1, e);
  }
  void _update(int i, L f) { laz[i] = L::multiply(f, laz[i]); }
  void update(int ql, int qr, L f) { update(ql, qr, f, 0, 0, n); }
  void update(int ql, int qr, L f, int i, int il, int ir) {
    if (qr <= il or ir <= ql) return;
    if (ql <= il and ir <= qr) {
      _update(i, f);
    } else {
      auto m = (il + ir) / 2, lch = i * 2 + 1, rch = i * 2 + 2;
      _update(lch, laz[i]);
      _update(rch, laz[i]);
      laz[i] = e;
      update(ql, qr, f, lch, il, m);
      update(ql, qr, f, rch, m, ir);
    }
  }
  L composite(int i) {
    auto f = L::ident();
    for (int k = i + n - 1; k > 0; k = (k - 1) / 2) {
      f = L::multiply(laz[k], f);
    }
    return L::multiply(laz[0], f);
  }
};

int main() {

  int n, q;
  cin >> n >> q;
  SegmentTree<Lonoid> seg(n);
  while (q--) {
    int o;
    cin >> o;
    if (o == 0) {
      int s, t;
      int64_t x;
      cin >> s >> t >> x;
      seg.update(s - 1, t, Lonoid(x));
    } else {
      int i;
      cin >> i;
      auto ans = seg.composite(i - 1).x;
      cout << ans << endl;
    }
  }

  return 0;
}



Measured memory_bytes: 4916
#include <algorithm>
#include <climits>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <memory>
#include <queue>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <numeric>

constexpr long long MOD = 1000000007;

struct Event
{
  int time;
  int index;
  // 0: exit
  // 1: start
  // 2: person
  int type;
};

int main()
{
  int N, Q;
  std::cin >> N >> Q;
  std::vector<Event> events;
  std::vector<int> pos(N);
  events.reserve(2 * N + Q);
  for (int i = 0; i < N; ++i)
  {
    int s, t, x;
    std::cin >> s >> t >> x;
    pos[i] = x;
    events.push_back({t - x, i, 0});
    events.push_back({s - x, i, 1});
  }
  while (Q--)
  {
    int d;
    std::cin >> d;
    events.push_back({d, 0, 2});
  }
  std::sort(events.begin(), events.end(), [](auto& x, auto& y) { return x.time == y.time ? x.type < y.type : x.time < y.time; });
  std::map<int, int> inPos;
  std::unordered_set<int> inInterval;
  for (int i = 0; i < events.size(); ++i)
  {
    auto& e = events[i];
    if (e.type == 0)
    {
      inInterval.erase(e.index);
      auto it = inPos.find(pos[e.index]);
      if (it->second == 1)
        inPos.erase(it);
      else
        --it->second;
    }
    else if (e.type == 1)
    {
      inInterval.insert(e.index);
      auto it = inPos.find(pos[e.index]);
      if (it == inPos.end())
        inPos.insert(std::make_pair(pos[e.index], 1));
      else
        ++it->second;
    }
    else
    {
      if (inInterval.empty())
      {
        std::cout << -1 << "\n";
      }
      else
      {
        std::cout << inPos.begin()->first << "\n";
      }
    }
  }
  return 0;
}



Measured memory_bytes: 26696
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define mod 1000000007
int main(){
  int a, b;
    cin >> a >> b;
  int ans=0;
    if(b<a) ans = a--;
    else    ans = b--;
    ans += max(a, b);
    cout << ans << endl;

}


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

using namespace std;
const long long INF = 1LL<<60;
void chmin(long long &a, long long b) { if (a > b) a = b; }

int main(void){
    int n;
    cin >> n;
    
    vector<long long> a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    
    //  区間 [ l, r )の合計値を累積和として事前に保持する
    vector<long long> cumulativeSum(n+1);
    for (int i = 0; i + 1<= n; i++) cumulativeSum[i+1] = cumulativeSum[i] + a[i];
    
    // dpの設定：
    // dp[l][r] : 区間[l,r)において, スライムをすべて合体させるときに支払うcostの最小値を保持する
    //求めるものはdp[0][n]である. n = 配列のサイズ
    vector<vector<long long>> dp(n+1,vector<long long>(n+1,INF));
    
    // dpの初期化をする
    // [l,l]からスライムを合体させるためのコストは0である
    for (int i = 0; i +1 <= n; i++) dp[i][i+1] = 0;
    
    
    for (int offset = 1; offset <= n; offset++){
        for (int left = 0; (left < n && left + offset <= n); left++){
            int right = left + offset;
            
            long long cost = cumulativeSum[right] - cumulativeSum[left];
            
            for (int k = left + 1; k <= right-1; k++){
                chmin(dp[left][right], dp[left][k]+dp[k][right] + cost);
            }
        }
    }
    cout << dp[0][n] << endl;
    
}


/*
問題文が「区間の合体」を求めている
-> 区間のスライムを1つにする一手前の状態を考える
-> 区間は2つに別れていたことに気づく
-> 「区間の除去・圧縮・合体」などがあるときは、区間DP を用いる!!!

dpの設定：
dp[l][r] : 区間[l,r)において, スライムをすべて合体させるときに支払うcostの最小値を保持する
求めるものはdp[0][n]である. n = 配列のサイズ

dpの更新：
dp[ l ][ r ] = min( dp[ l ][ i ] + dp[ i ][ r ] +「 区間 [ l, r )の合計値」 )
支払うコストは, 区間の分割法によらず, 区間 [ l, r )の合計値」に等しい
-> 累積和として事前に保持しておくとよい


*/

Measured memory_bytes: 4900
import sys
stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = na()

import collections
c = collections.Counter(a)

k = 0

for i in c.values():
    if i > 1:
        k += i*(i-1)//2

for j in range(n):
    b = a[j]
    d = 0 if c[b] < 2 else 1 if c[b] == 2 else c[b]-1
    print(k-d)

Measured memory_bytes: 25456
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
#define rep(i,a,n)	for(int i=a;i<n;i++)
int main(){
	int n;
	cin>>n;
	long long int a[200100];
	rep(i,0,n){
		cin>>a[i];
	}
	long long int b[200100];
	b[0]=a[0];
	rep(i,1,n){
		b[i]=b[i-1]+a[i];
	}
	long long int ans=100000000000000;
	rep(i,0,n-1){
		long long int x=b[n-1]-b[i];
		long long int res=abs(x-b[i]);
		if(res<ans)ans=res;
	}
	cout<<ans<<endl;
}

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

using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vd = vector<double>;
using vvd = vector<vector<double>>;
using vvvd = vector<vector<vector<double>>>;
using vb = vector<bool>;
using vvb = vector<vector<bool>>;
using vs = vector<string>;
using pint = pair<int, int>;
using Graph = vvi;

#define rep(i, n) for(int i = 0; i < (int)(n); i++)
#define all(x) (x).begin(),(x).end()

bool cmp(pint a, pint b) {return a.second < b.second;}
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() {
    double n, k;
    cin >> n >> k;
    vd p(n);
    rep(i, n) cin >> p[i];

    vd r(n + 1);
    r[0] = 0;
    rep(i, n) {
        r[i + 1] = r[i] + p[i];
    }

    double mx = -1;
    int idx = 0;
    for(int i = k; i < r.size(); i++) {
        double tmp = r[i] - r[i - k];
        if(tmp > mx) {
            mx = tmp;
            idx = i - k;
        }
    }

    //cout << idx << endl;

    double ans = 0.0;
    for(int i = idx; i < idx + k; i++) {
        ans += ((p[i] * (p[i] + 1.0) / 2) / p[i]);
    }

    printf("%.10f\n", ans);

    return 0;
}

Measured memory_bytes: 3328
using System;

class Program
{
    static void Main(string[] args)
    {
        int N = int.Parse(Console.ReadLine());
        string S = Console.ReadLine();

        if (N % 2 == 1)
        {
            Console.WriteLine("No");
            return;
        }
        if (N != S.Length)
        {
            Console.WriteLine("No");
            return;
        }

        string firstHalf = S.Substring(0, N / 2);
        string lastHalf = S.Substring(N / 2, N / 2);

        if (firstHalf != lastHalf)
        {
            Console.WriteLine("No");
            return;
        }
        Console.WriteLine("Yes");
    }
}


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

constexpr int NOT_FOUND = 8101919;

bool IsNotElem( std::vector<int>& done, int x ){
    for( const auto& g : done ){
        if( g == x ){
            return false;
        }
    }
    done.push_back(x);
    return true;
}

void MySwap( int& a, int& b ){
    int tmp = std::move(a);
    a = std::move(b);
    b = std::move(tmp);
}

bool BinarySearch( std::vector<int>& v, int key ){
    int left = 0;
    int right = v.size();
    int mid;
    //std::cout << key << ": ";
    while( left < right ){
        mid = ( left + right ) / 2;
        if( v[mid] == key ){
            //std::cout << key;
            return true;
        }else if( key < v[mid] ){
            right = mid;
        }else{
            left = mid + 1;
        }
        
        if( key == 1 ){
            //std::cout << v[mid] << " ";
        }
    }
    return false;
}

int main(){
    int n;
    std::cin >> n;
    std::vector<int> S(n);
    for( auto& s : S ){
        std::cin >> s;
    }
    
    int q;
    std::cin >> q;
    std::vector<int> T(q);
    for( auto& t : T ){
        std::cin >> t;
    }

    int num = 0;
    std::vector<int> done;
    for( auto& t : T ){
        if( BinarySearch( S, t )  ){
            ++num;
        }
    }
    std::cout << num << "\n";
}


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

using namespace std;

int main(){
  long int i, N;
  
  cin >> N;
  
  long int *A = new long int[N];
  
  for(i = 0; i < N; i++){
    cin >> A[i];
  }
  
  sort(A, A + N);
  
  for(i = 0; i < N-1; i++){
    if(A[i] == A[i+1]){
      cout << "NO" << endl;
      
      return 0;
    }
  }
  
  cout << "YES" << endl;
  
  return 0;
}

Measured memory_bytes: 1792
import java.util.Scanner;

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

		int n = sc.nextInt();
		int[] a = new int[n];
		int[] cnt = new int[100000];
		int[] around = new int[100000];

		for(int i=0; i<100000; i++){
			around[i] = 0;
		}


		for(int i=0; i<n; i++){
			a[i] = sc.nextInt();
			around[a[i]]++;
			if(a[i]!=0){
				around[a[i]-1]++;
			}
			if(a[i]!=99999){
				around[a[i]+1]++;
			}
		}

		int max=around[0];
		for(int i=1; i<100000; i++){
			if(around[i]>max){
				max=around[i];
			}
		}

		System.out.print(max);
	}
}


Measured memory_bytes: 51844
n = int(input())
a1 = list(map(int, input().split()))
a2 = list(map(int, input().split()))
count = 0
max1 = 0
for i in range(n):
    for j in range(n):
        if j < i:
            count += a1[j]
        elif j==i:
            count += (a1[j] + a2[j])
        else:
            count += a2[j]
    if max1 < count:
        max1 = count
    count = 0
print (max1)

Measured memory_bytes: 3064
n = int(input())
xy = [[] for _ in range(n)]
ans = -float("inf")

for i in range(n):
	a = int(input())
	for _ in range(a):
		xy[i].append(tuple(map(int, input().split())))

for i in range(1 << n):
	true_or_false = [0] * n
	flag = False
	for j in range(n):
		if (i>>j)&1:
			true_or_false[n-1-j] = 1
	for i, l in enumerate(xy):
		for x, y in l:
			if true_or_false[i] == 1:
				if true_or_false[x-1] != y:
					flag = True
	if not flag:
		ans = max(ans, len([i for i in true_or_false if i == 1]))
print(ans)


Measured memory_bytes: 43116
#include <stdio.h>

int main(){
	char sA[100],sB[100],sC[100];
	int pA,pB,pC;
	char player = 'a';
	pA=pB=pC=0;

	scanf("%s",sA);
	scanf("%s",sB);
	scanf("%s",sC);

	while(player != '\0'){
		switch(player){
		case 'a':
			player = sA[pA++];
			if(player == '\0') printf("A");
			break;
		case 'b':
			player = sB[pB++];
			if(player == '\0') printf("B");
			break;
		case 'c':
			player = sC[pC++];
			if(player == '\0') printf("C");
			break;
		}
	}
	return 0;
}


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

typedef pair<string,int> P;
map<int,vector<P> >arr;
int N,S,G;

void bfs(){
	set<P>q;
	q.insert(make_pair("",S));
	for(;!q.empty();){
		P p=*q.begin();q.erase(q.begin());
		if(p.second==G){cout<<p.first<<endl;return;}
		if(p.first.length()>=N*6){cout<<"NO"<<endl;return;}
		vector<P> a=arr[p.second];
		if(!a.empty()){
			string prefix=a[0].first;
			for(int i=0;i<a.size();i++){
				if(a[i].first.substr(0,prefix.length())!=prefix)break;
				q.insert(make_pair(p.first+a[i].first,a[i].second));
			}
		}
	}
}

int r[40][40];
int main(){
	int a,i,j,k;
	map<int,vector<P> >::iterator it;
	vector<P>::iterator it2;
	for(;cin>>N>>a>>S>>G,N;){
		memset(r,0,sizeof(r));
		arr.clear();
		int _a,_b;string _s;
		for(;a;a--)cin>>_a>>_b>>_s,arr[_a].push_back(make_pair(_s,_b)),r[_a][_b]=1;
		for(k=0;k<N;k++)
			for(r[k][k]=1,i=0;i<N;i++)
				for(j=0;j<N;j++)
					r[i][j]|=r[i][k]&r[k][j];
		if(!r[S][G]){cout<<"NO"<<endl;continue;}
		for(it=arr.begin();it!=arr.end();it++){
			vector<P> &x=(*it).second;
			for(it2=x.begin();it2!=x.end();)
				if(!r[(*it2).second][G])x.erase(it2);else it2++;
			sort(x.begin(),x.end());
		}
		bfs();
	}
}

Measured memory_bytes: 1012
#coding:utf-8
import bisect
import sys
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = lambda *something : print(*something) if DEBUG else 0
DEBUG = True



def main(given = sys.stdin.readline):
    input = lambda : given().rstrip()
    LMIIS = lambda : list(map(int,input().split()))
    II = lambda : int(input())
    XLMIIS = lambda x : [LMIIS() for _ in range(x)]

    x, y = LMIIS()

    if (x+y)%3!=0:
      print(0)
      exit()
    n = (x+y)//3
    if 0 > x-n or 0 > y-n:
      print(0)
      exit()

    m = min(x-n,y-n)
    mod = 10**9 + 7

    a = 1
    b = 1
    c = 1
    for i in range(1, n+1):
        a = a * i % mod
    for i in range(1, n - m + 1):
        b = b * i % mod
    for i in range(1, m + 1):
        c = c * i % mod
    print(a * pow(b * c, mod - 2, mod) % mod)




if __name__ == '__main__':
    main()


Measured memory_bytes: 3064
#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>
#include <string.h>

using namespace std;

struct key_auth
{
	int level, space;
};

bool flag[500][500];
void serve(int w, int h, int x, int y, vector<vector<int>>&lev, vector<key_auth>&ret)
{
	memset(flag, false, sizeof(flag));
	int stop = 0;
	int room = 0;
	priority_queue<pair<int, pair<int, int>>>que;
	que.push(make_pair(-1, make_pair(y, x)));
	while (!que.empty())
	{
		auto qq = que.top();
		if (-qq.first > stop)
		{
			ret.push_back({ stop,room });
			stop = -qq.first;
		}
		que.pop();
		if (flag[qq.second.first][qq.second.second])continue;
		++room;
		flag[qq.second.first][qq.second.second] = true;
		const int dxy[5] = { 1,0,-1,0,1 };
		for (int d = 0; d < 4; ++d)
		{
			if (qq.second.first + dxy[d] < 0 || qq.second.first + dxy[d] >= h)
			{
				continue;
			}

			if (qq.second.second + dxy[d + 1] < 0 || qq.second.second + dxy[d + 1] >= w)
			{
				continue;
			}
			if (!flag[qq.second.first + dxy[d]][qq.second.second + dxy[d + 1]])
			{
				que.push(make_pair(-lev[qq.second.first + dxy[d]][qq.second.second + dxy[d + 1]], make_pair(qq.second.first + dxy[d], qq.second.second + dxy[d + 1])));
			}
		}
	}
	ret.push_back({ stop,room });
	return;
}

int main()
{
	for (;;)
	{
		int r;
		scanf("%d", &r);
		if (r == 0)break;
		int w1, w2;
		int h1, h2;
		int x1, x2;
		int y1, y2;
		vector<vector<int>>lev1, lev2;
		vector<key_auth>ret1, ret2;
		scanf("%d %d %d %d", &w1, &h1, &x1, &y1);
		--x1; --y1;
		lev1.resize(h1);
		for (int i = 0; i < h1; ++i)lev1[i].resize(w1);
		for (int i = 0; i < h1; ++i)
		{
			for (int j = 0; j < w1; ++j)
			{
				scanf("%d", &lev1[i][j]);
			}
		}
		scanf("%d %d %d %d", &w2, &h2, &x2, &y2);
		lev2.resize(h2);
		for (int i = 0; i < h2; ++i)lev2[i].resize(w2);
		--x2; --y2;
		for (int i = 0; i < h2; ++i)
		{
			for (int j = 0; j < w2; ++j)
			{
				scanf("%d", &lev2[i][j]);
			}
		}
		serve(w1, h1, x1, y1, lev1, ret1);
		serve(w2, h2, x2, y2, lev2, ret2);
		auto itr = ret2.rbegin();
		int ans = 1234567890;
		for (auto& rr : ret1)
		{
			while (((itr + 1) != ret2.rend()) && ((itr + 1)->space + rr.space >= r))
			{
				++itr;
			}
			if (itr->space + rr.space >= r)ans = min(ans, itr->level + rr.level);
		}
		printf("%d\n", ans);
	}
	return 0;
}

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

int main(){
  int n,m,sum = 0;
  cin >> n >> m;
  int a[m];
  for(int i = 0;i < m;i++){
    cin >> a[i];
    sum += a[i];
  }
  if(n < sum){
    cout << -1 << endl;
    return 0;
  }
  else{
    cout << n - sum << endl;
    return 0;
  }
}


Measured memory_bytes: 3636
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); i++)
typedef long long ll;
const int mod = 1e9 + 7;
int gcd(int a, int b) {

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

int main() {

    long long a, b;
    cin >> a >> b;

    int g = gcd(a, b);
    long long ans = (long long) (a*b)/g;

    cout << ans;    

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i, m, n) for(int i = m; i < (n); i++)
#define print(x) cout << (x) << endl;
#define printa(x,n) for(int i = 0; i < n; i++){ cout << (x[i]) << " ";} cout << endl;
#define printa2(x,m,n) for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ cout << x[i][j] << " ";} cout << endl;}
#define printp(x,n) for(int i = 0; i < n; i++){ cout << "(" << x[i].first << ", " << x[i].second << ") "; } cout << endl;
#define INF (1e18)
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
typedef struct{
    int x;
    int y;
} P;
typedef struct{
    ll to;
    ll cost;
} edge;
typedef pair<ll, ll> lpair;

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    ll N;
    string s,t;
    cin >> N;
    cin >> s >> t;
    rep(i,0,N){
        string ss = s.substr(0,i) + t;
        if(ss.substr(0,N) == s && ss.substr(ss.size() - N, N) == t){
            print(ss.size());
            return 0;
        }
    }
    print(2*N);
    // ll pos = 0;
    // rep(i,0,N){
    //     if(s[N-1-i] == t[i]){
    //         pos++;
    //     }
    // }
    // rep(i,0,N-pos+1){
    //     cout << s[i];
    // }
    // rep(i,pos,N){
    //     cout << t[i];
    // }
    // cout << endl;
}


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

using namespace std;

int main(void){
    int N;
    long mod = 1000000007;
    cin >> N;
    int A[N];
    for(int i = 0; i < N; i++)
    {
    cin >> A[i];
    }
    long long S[N-1];
    long long ans = 0;
    S[0] = A[0];
    for(int i = 1; i < N-1; i++)
    {
        S[i] = S[i-1] + A[i];
    }
    for(int i = 0; i < N-1; i++)
    {
        A[i+1] = A[i+1] % mod;
        S[i] = S[i] % mod;
        ans = ans + S[i]*A[i+1];
        ans = ans % mod;
    }
    cout << ans << endl;
    
}

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

// 型定義
typedef long long ll;
typedef pair<ll, ll> P;

// forループ
#define REP(i,n) for(ll i=0; i<(ll)(n); ++i)

// 定数宣言
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;

// グラフ表現
using Graph = vector<vector<int>>;

// グラフの辺表現
using Edge = map<pair<int,int>,int>;

// n次元配列の初期化。第２引数の型のサイズごとに初期化していく。
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
    std::fill( (T*)array, (T*)(array+N), val );
}

// 最大公約数
ll gcd(ll a,ll b){
   if (a%b == 0) return(b);
   else return(gcd(b, a%b));
}

// 最小公倍数
ll lcm(ll a, ll b){
    return a*b/gcd(a, b);
}

int main()
{
    cout << fixed << setprecision(15);
    ll N;
    cin >> N;

    vector<ll> t(N+1);
    vector<ll> x(N+1);
    vector<ll> y(N+1);

    t[0] = 0;
    x[0] = 0;
    y[0] = 0;

    for(ll i=1; i<=N; i++){
        cin >> t[i] >> x[i] >> y[i];
    }

    for(ll i=1; i<=N; i++){
        ll td = t[i]-t[i-1];
        ll dis = abs(x[i]-x[i-1]) + abs(y[i]-y[i-1]);

        if(td < dis){
            cout << "No" << endl;
            return 0;
        }
        if((td-dis)%2 == 1){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
    return 0;
}

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

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

typedef long long ll;

const int mod = 1e9 + 7;

using namespace std;



int main(void) {
	int X; cin >> X;

	cout << (X >= 30 ? "Yes" : "No") << endl;

	return 0;
}

Measured memory_bytes: 3616