akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>
using namespace std;

#define int long long
typedef pair<int, int> P;
#define mod 1000000007
#define INF (1LL<<60)
 
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)
#define YES puts("YES")
#define Yes puts("Yes")
#define NO  puts("NO")
#define No  puts("No")
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }
 
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };
 
 
#if 1
//-------------
// DUMPマクロ
// https://www.creativ.xyz/dump-cpp-652/
 
// vector
template <typename T>
istream& operator>>(istream& is, vector<T>& vec) {
    for (T& x : vec) is >> x;
    return is;
}
// pair
template <typename T, typename U>
ostream& operator<<(ostream& os, pair<T, U>& pair_var) {
    os << "(" << pair_var.first << ", " << pair_var.second << ")";
    return os;
}
// vector
template <typename T>
ostream& operator<<(ostream& os, const vector<T>& vec) {
    os << "{";
    for (int i = 0; i < vec.size(); i++) {
        os << vec[i] << (i + 1 == vec.size() ? "" : ", ");
    }
    os << "}";
    return os;
}
// map
template <typename T, typename U>
ostream& operator<<(ostream& os, map<T, U>& map_var) {
    os << "{";
    repi(itr, map_var) {
        os << *itr;
        itr++;
        if (itr != map_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
// set
template <typename T>
ostream& operator<<(ostream& os, set<T>& set_var) {
    os << "{";
    repi(itr, set_var) {
        os << *itr;
        itr++;
        if (itr != set_var.end()) os << ", ";
        itr--;
    }
    os << "}";
    return os;
}
 
#define DUMPOUT cerr
 
void dump_func() {
    DUMPOUT << endl;
}
template <class Head, class... Tail>
void dump_func(Head&& head, Tail&& ... tail) {
    DUMPOUT << head;
    if (sizeof...(Tail) > 0) {
        DUMPOUT << ", ";
    }
    dump_func(std::move(tail)...);
}
#ifdef _DEBUG
#define DEB
#define dump(...)                                                              \
    DUMPOUT << "  " << string(#__VA_ARGS__) << ": "                            \
            << "[" << to_string(__LINE__) << ":" << __FUNCTION__ << "]"        \
            << endl                                                            \
            << "    ",                                                         \
        dump_func(__VA_ARGS__)
#else
#define DEB if (false)
#define dump(...)
#endif
#endif

signed main() {

    string a, b;
    cin >> a >> b;
    int x = atoi((a+b).c_str());
    
    rep(i,1000){
        if(i*i==x) {Yes; return 0;}
    }
    No;
    
    
    return 0;
}


Measured memory_bytes: 256
#include<iostream>
#include<string>
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<functional>
#include<iomanip>
#include<queue>
#include<ciso646>
#include<random>
#include<map>
#include<set>
#include<complex>
#include<bitset>
#include<stack>
#include<unordered_map>
#include<utility>
using namespace std;
typedef long long ll;
typedef unsigned int ui;
const ll mod = 1000000007;
typedef long double ld;
const ll INF = 1e+14;
typedef pair<int, int> P;
#define stop char nyaa;cin>>nyaa;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define Rep(i,sta,n) for(int i=sta;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define per1(i,n) for(int i=n;i>=1;i--)
#define Rep1(i,sta,n) for(int i=sta;i<=n;i++)
typedef complex<ld> Point;
const ld eps = 1e-8;
const ld pi = acos(-1.0);
typedef pair<ld, ld> LDP;
typedef pair<ll, ll> LP;
#define fr first
#define sc second
#define all(c) c.begin(),c.end()
#define pb push_back

void Yes(){
	cout<<"Yes"<<endl;
	exit(0);
}

void No(){
	cout<<"No"<<endl;
	exit(0);
}

#define MAX_V 100
vector<ll> graph[MAX_V];
bool used_v[MAX_V], used_e[MAX_V][MAX_V];
ll ord[MAX_V], lowlink[MAX_V];
ll k=0;
void dfs(ll v){
  used_v[v]=true;
  ord[v]=lowlink[v]=k++;
  ll s=graph[v].size();
  rep(i,s){
    if(!used_v[graph[v][i]]){
      used_e[v][graph[v][i]]=true;
      dfs(graph[v][i]);
      lowlink[v]=min(lowlink[v],lowlink[graph[v][i]]);
    }
    else if(!used_e[graph[v][i]][v]){
      lowlink[v]=min(lowlink[v],ord[graph[v][i]]);
    }
  }
  return;
}


int main(){
  ll N; cin>>N;
  ll M; cin>>M;
  rep(i,M){
    ll a,b; cin>>a>>b;
    graph[b].push_back(a);
    graph[a].push_back(b);
  }
  ll count=0;
  dfs(1);
  rep1(i,N){
    ll s=graph[i].size();
    rep(j,s){
      ll v=graph[i][j];
      if(ord[i]<ord[v]){
        if(ord[i]<lowlink[v]) count++;
      }
      else continue;
    }
  }
  
  cout<<count<<endl;
}

        

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

int parent(int i) {
  return i/2;
}

int left(int i) {
  return 2*i;
}

int right(int i) {
  return 2*i+1;
}

int main() {
  int H;
  cin >> H;
  int A[H+1];
  for (int i=1; i<=H; i++) {
    cin >> A[i];
  }

  for (int i=1; i<=H; i++) {
    cout << "node " << i << ": key = " << A[i] << ", ";
    if (parent(i)>0) {
      cout << "parent key = " << A[parent(i)] << ", ";
    }
    if (left(i)<=H) {
      cout << "left key = " << A[left(i)] << ", ";
    }
    if (right(i)<=H) {
      cout << "right key = " << A[right(i)] << ", ";
    }
    cout << endl;
  }
  return 0;
}



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

using namespace std;
using ll = long long;

template <class T>
T GCD(T a, T b) { return b == 0 ? a : GCD(b, a%b); }

int main()
{
  ll N, M; string S, T;
  cin >> N >> M >> S >> T;

  ll l = N*M/GCD(N, M);

  map<int, char> tmp;
  for (int i = 0; i < N; ++i) {
    tmp[1+i*l/N] = S[i];
  }

  for (int i = 0; i < M; ++i) {
    if (tmp[1+i*l/M] != 0 && tmp[1+i*l/M] != T[i]) {
      cout << -1 << endl;
      return 0;
    }
  }

  cout << l << endl;
}

Measured memory_bytes: 8192
n = int(input())
a_lst = [int(input()) for _ in range(n)]

button = a_lst[0]

cnt = 1 #必ずボタン1は押すため一回はカウント
ans = 0
for i in range(n):
    button = a_lst[button-1]
    if a_lst[0] == 2:
        ans = 1
        break
    if button == 2:
        ans = cnt + 1 #2と書かれたボタンを押す分の一回を追加
        break
    cnt += 1

if cnt == n+1 and ans == 0: #cntの初期値が1だからn+1
    print("-1")
else:
    print(ans)

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

int main(){
    int h, w;
    cin >> h >> w;
    long long all= 0;
    vector<vector<int>>a(h, vector<int>(w));
    for(int i=0; i < h; i++)for(int j=0; j < w; j++)cin >> a[i][j];

    for(int i=0; i < h; i++){
        int sum=0;
        for(int j=0; j < w; j++){
            cout << a[i][j] << ' ';
            sum += a[i][j];
        }
        cout << sum << endl;
    }
    for(int i = 0; i < w; i++){
        int sum = 0;
        for(int j=0; j < h; j++){
            sum += a[j][i];
        }
        all += sum;
        cout << sum << ' ';
    }
    cout << all << endl;
    return 0;
    
}


Measured memory_bytes: 3152
#include<iostream>
#include<string>

using namespace std;

int main(){
    string s;
    cin >> s;
    if(s == "SUN"){
        cout << 7 << endl;
    }else if(s == "MON"){
        cout << 6 << endl;
    }else if(s == "TUE"){
        cout << 5 << endl;
    }else if(s == "WED"){
        cout << 4 << endl;
    }else if(s == "THU"){
        cout << 3 << endl;
    }else if(s == "FRI"){
        cout << 2 << endl;
    }else if(s == "SAT"){
        cout << 1 << endl;
    }
    return 0;
}

Measured memory_bytes: 256
/* Ahmed Maher ( Acro_14 ) */
/*while(WA)try();*/
#include <bits/stdc++.h>
typedef long long ll;
const ll oo = 0x3f3f3f3f;
int const N = 1e6+5;
int const mod = 1e9+7;
using namespace std;
/*string Alphabet="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
string alphabet="abcdefghijklmnopqrstuvwxyz";*/
ll gcd(ll a, ll b) 
{ 
    if (a == 0) 
        return b; 
    return gcd(b % a, a); 
} 
vector<pair<ll, ll>>prime; 
void prime_fuct(ll x){
    for (ll i = 2; i * i <= x; i++){
        if(x % i == 0){
            pair<ll, ll> p = {i,0};
            while (x % i == 0){
                x /= i;
                p.second++;
            }
            prime.push_back(p);
        }
    }
    if(x > 1){
        pair<ll, ll> p = {x,1};
        prime.push_back(p);
    }
}

void solve(){
	ll a,b;
    cin>>a>>b;
    prime_fuct(gcd(a,b));
    cout<<(ll)prime.size()+1;
	cout<<endl;
}

int main()
{
  int t;
	t=1;
     while(t--)
    {
       
		solve();
 
    }
	return 0;
}
 
//       int anss[t+1]; 
//            anss[j]=ans;
//     for(int j=1;j<=t;j++) printf("Case %d: %d\n",j,anss[j]);

Measured memory_bytes: 3620
#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <map>
#include <vector>
#include <list>
using namespace std;

int main()
{

	long int sum = 0, n, a;

    cin >> n;

    for (int i = 0; i < n; i++){
        cin >> a;
        sum += a;
    }

    cout << sum - n << endl;

    return 0;

}


Measured memory_bytes: 256
#include<iostream>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
#include<bitset>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<ll,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define fi first
#define sc second
#define rep(i,x) for(ll i=0;i<x;i++)
#define repn(i,x) for(ll i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())

const int MAX = 2100000;
const int MOD = 1000000007;

// MAXの値に注意 !!!!!
long long fac[MAX], finv[MAX], inv[MAX];

// a^n mod を計算する
long long modpow(long long a, long long n, long long mod) {
    long long res = 1;
    while (n > 0) {
        if (n & 1) res = res * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

// テーブルを作る前処理
void COMinit() {
    fac[0] = fac[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < MAX; i++){
        fac[i] = fac[i - 1] * i % MOD;
        inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
        finv[i] = finv[i - 1] * inv[i] % MOD;
    }
}

// 二項係数計算
long long COM(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

int main() {
    // 前処理
    COMinit();
    ll K; cin >> K;
    string s; cin >> s;
    ll N = s.size();

    ll ans = 0;
    rep(i,K + 1){
      // i文字が最後の自由な文字の数
      ans += modpow(25, K - i , MOD) * COM(K - i + N - 1 , N - 1)
      % MOD * modpow(26 , i , MOD) % MOD;
      ans %= MOD;
    }
    cout << ans << endl;
}


Measured memory_bytes: 54436
# coding: utf-8


def solve(*args: str) -> str:
    x, y = map(int, args[0].split())
    ret = 0
    if x == 1 and y == 1:
        ret += 400000

    if x == 1:
        ret += 300000
    elif x == 2:
        ret += 200000
    elif x == 3:
        ret += 100000

    if y == 1:
        ret += 300000
    elif y == 2:
        ret += 200000
    elif y == 3:
        ret += 100000

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


Measured memory_bytes: 3060
use std::io::*;
use std::str::FromStr;
use utils::*;

pub fn main() {
    let i = stdin();
    let mut o = Vec::new();
    run(i.lock(), &mut o);
    stdout().write_all(&o).unwrap();
}

fn run<R: BufRead, W: Write>(i: R, o: &mut W) {
    let mut i = CpReader::new(i);
    let n = i.read::<usize>();
    let a = i.read_vec::<usize>(n);

    writeln!(o, "{}", solve(a)).unwrap();
}
fn counts(a: &[usize]) -> Vec<usize> {
    let mut ss = vec![[None; 16]; a.len()];
    let mut rs = Vec::new();
    let mut cs = Vec::new();

    rs.push(0);
    rs.push(0);

    for i in 1..a.len() {
        cs.clear();
        let mut c = 0;
        let mut j = i;
        while j > 0 {
            let mut c_ext = 0;
            if c >= 16 {
                c_ext = c - 16 + 1;
                c -= c_ext;
            }

            if let Some(c_j) = ss[j][c] {
                c = c_j + c_ext * (j + 1);
                break;
            }
            cs.push((c, c_ext));

            let mut a0 = a[j - 1];
            let mut a1 = a[j];
            while a0 < a1 {
                a0 *= 4;
                c += 1;
            }
            while c > 0 && a0 >= a1 * 4 {
                a1 *= 4;
                c -= 1;
            }
            j -= 1;
        }
        while let Some((c_j, c_j_ext)) = cs.pop() {
            j += 1;
            ss[j][c_j] = Some(c + c_j);
            c += c_j + c_j_ext * (j + 1);
        }
        rs.push(c);
    }
    rs
}
fn solve(mut a: Vec<usize>) -> usize {
    let cs0 = counts(&a);
    a.reverse();
    let cs1 = counts(&a);

    (0..a.len())
        .map(|x| cs0[x] * 2 + x + cs1[a.len() - x] * 2)
        .min()
        .unwrap()
}

mod utils {
    use super::*;

    pub struct CpReader<R: BufRead> {
        r: R,
        s: String,
    }

    macro_rules! fn_read {
        { $f:ident($($t:ident),*) } => {
            #[allow(dead_code)]
            pub fn $f<$($t: FromStr),*>(&mut self) -> ($($t),*) {
                let i = &mut self.read_line().split(' ');
                ($(read_next::<$t,_>(i)),*)
            }
        };
    }

    impl<R: BufRead> CpReader<R> {
        pub fn new(r: R) -> Self {
            CpReader {
                r: r,
                s: String::new(),
            }
        }
        pub fn read_line(&mut self) -> &str {
            self.s.clear();
            self.r.read_line(&mut self.s).unwrap();
            self.s.trim()
        }

        pub fn read<T: FromStr>(&mut self) -> T {
            self.read_line().parse().ok().unwrap()
        }
        fn_read! { read2(T1, T2) }
        fn_read! { read3(T1, T2, T3) }
        fn_read! { read4(T1, T2, T3, T4) }
        fn_read! { read5(T1, T2, T3, T4, T5) }

        pub fn read_vec<T: FromStr>(&mut self, n: usize) -> Vec<T> {
            self.read_line()
                .split(' ')
                .take(n)
                .map(|x| x.parse().ok().unwrap())
                .collect()
        }
    }
    fn read_next<'a, T: FromStr, I: Iterator<Item = &'a str>>(i: &mut I) -> T {
        i.next().unwrap().parse().ok().unwrap()
    }

}


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

const int INF = 1 << 28;

int main()
{
    int n;
    int dp[101][101];
    int r[102];
    
    cin >> n;
    
    fill((int*)dp, (int*)(dp + n), INF);
    
    for(int i = 0; i < n; ++i){
        cin >> r[i] >> r[i + 1];
        dp[i][i] = 0;
    }
    
    for(int w = 1; w < n; ++w){
        for(int i = 0, j ; j = i + w, j < n; ++i){
            for(int k = i; k < j; ++k){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + r[i] * r[k + 1] * r[j + 1]);
            }
        }
    }
    
    cout << dp[0][n-1] << endl;
    
}

Measured memory_bytes: 1200
#define _CRT_SECURE_NO_WARNINGS
#pragma comment(linker, "/STACK:256000000")
#define _USE_MATH_DEFINES
#include<iostream>
#include<vector>
#include<string>
#include<stack>
#include<algorithm>
#include<cmath>
#include<set>
#include<queue>
#include<sstream>
#include<utility>
#include<map>
#include<ctime>
#include<cstdio>
#include<cassert>
#include<functional>
#include<unordered_map>
#include<deque>
#include<cmath>





using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<char, char> pcc;
typedef pair<double, double> pdd;

#define show(x) cerr << x
#define debug(x) show(#x << ": " << (x) << endl)

const long double PI = 3.14159265358979323846;
const long double eps = 1e-5;
const ll INF = numeric_limits<int>::max();
const ll LINF = numeric_limits<ll>::max();
const ll mod = 1000 * 1000 * 1000 + 7;

vector<vector<pii> > g;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<pii> d(n);
    for (int i = 0; i < n; ++i) cin >> d[i].first;
    vector<int> d0(n);
    for (int i = 0; i < n; ++i)
        d0[i] = d[i].first;
    for (int i = 0; i < n; ++i) d[i].second = i;
    sort(d.begin(), d.end());
    g.resize(n);
    int u, v;
    for (int i = 0; i < m; ++i) {
        cin >> u >> v;
        --u, --v;
        g[u].push_back(pii(v, i));
        g[v].push_back(pii(u, i));
    }
    for (int i = 0; i < n; ++i) {
        int ok = 0;
        for (int j = 0; j < g[i].size(); ++j) {
            if (d0[g[i][j].first] <= d0[i])
                ok = 1;
        }
        if (ok == 0) {
            cout << -1 << endl;
            return;
        }
    }
    vector<int> col(n, -1);
    vector<int> w(m, 1000000000);
    for (int i = 0; i < n; ++i) {
        int id = d[i].second;
        if (col[id] != -1)
            continue;
        int ok = 0;
        for (auto to:g[id]) {
            int p = to.first;
            if (col[p] != -1) {
                col[id] = 1 - col[p];
                w[to.second] = d0[id];
                ok = 1;
                break;
            }
        }
        if (ok)
            continue;
        for (auto to:g[id]) {
            int p = to.first;
            if (d0[p] == d0[id]) {
                ok = 1;
                col[id] = 0;
                col[p] = 1;
                w[to.second] = d0[id];
                break;
            }
        }
        if (!ok) {
            cout << "huy\n";
            cout << -1 << endl;
            return;
        }
    }
    for (int i = 0; i < n; ++i) {
        if (col[i] == 0)
            cout << "W";
        else cout << "B";
    }
    cout << endl;
    for (int i = 0; i < m; ++i) {
        cout << w[i] << "\n";
    }

}


//#define LOCAL

int main() {
    ios_base::sync_with_stdio(0);cin.tie(nullptr);cout.tie(nullptr);
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    solve();



#ifdef LOCAL
    cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif	
    return 0;
}


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

using namespace std;

int main()
{
	int X;
	
	cin >> X;
	
	if(X < 4)
		cout << X << '\n';
		
	else
	{
		vector<int> primos {3};
		
		for(int k = 5; k <= 100003; k += 2)
		{
			bool is_prime = true;
			
			for(int i = 0; 1LL * primos[i] * primos[i] <= k; ++i)
			{
				if(k % primos[i] == 0)
				{
					is_prime = false;
					break;
				}
			}
			
			if(is_prime)
			{
				if(k >= X)
				{	
					cout << k << '\n';
					break;
				}
				
				primos.push_back(k);
			}
		}
	}
		
 	return 0; 
}

Measured memory_bytes: 384
A, B, M = (int(i) for i in input().split())
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
ans = min(a) + min(b)
for i in range(M):
    x, y, c = (int(i) for i in input().split())
    ans = min(ans, a[x-1] + b[y-1] - c)
print(ans)

Measured memory_bytes: 72644
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String s1 = br.readLine();
		String s2 = br.readLine();
		int n = s1.length();
		int m = s2.length();
		
		int dp [][] = new int [n+1][m+1];
		
		for (int i=1; i<n+1; i++) dp[i][0]=i;
		for (int j=1; j<m+1; j++) dp[0][j]=j;
		
		int cost=0;
		for (int i=1; i<n+1; i++){
			for (int j=1; j<m+1; j++){
				if (s1.charAt(i-1)==s2.charAt(j-1)) cost=0;
				else cost=1;
				dp[i][j]=Math.min(Math.min(dp[i-1][j]+1, dp[i][j-1]+1), dp[i-1][j-1]+cost);
			}
		}
		System.out.println(dp[n][m]);
	}
}

Measured memory_bytes: 29284
#include<iostream>
#include<string>
using namespace std;
string name[10000];
int y, a, b, n; string S[10000];
int main() {
	S[0] = "kogakubu10gokan";
	cin >> a >> b;
	n = 0;
	for (int i = 1; i <= a; i++) {
		cin >> y >> S[i];
		for (int j = n; j < y; j++) {
			name[j] = S[i - 1];
		}
		n = y;
	}
	for (int i = n; i < 9999; i++) {
		name[i] = S[a];
	}
	cout << name[b] << endl;
	return 0;
}

Measured memory_bytes: 1364
use proconio::input;
use proconio::marker::{Chars};

// x ** n % mods を求める
pub fn mod_pow(x: i64, n: i64, mods: i64) -> i64 {
    if n == 0 {
        return 1;
    }
    let mut res = mod_pow(x * x % mods, n / 2, mods);
    if n % 2 == 1 {
        res = res * x % mods;
    }
    return res;
}

// (1/n) % mods を求める
pub fn mod_inv(n: i64, mods: i64) -> i64 {
    return mod_pow(n, mods-2, mods);
}

// nCk % mods を求める
pub fn mod_comb(n: i64, k: i64, mods: i64) -> i64 {
    let sum1 = (n-k+1..n+1).fold(1, |ac, x| ac * x % mods);
    let sum2 = (1..k+1).fold(1, |ac, x| ac * x % mods);
    return sum1 * mod_inv(sum2, mods) % mods;
}

// nCk の組み合わせを列挙する
pub fn combination(n: usize, k: usize) -> Vec<Vec<usize>> {
    let mut ans = Vec::new();
    if k == 1 {
        for i in 1..n+1 {
            let mut tmp = Vec::new();
            tmp.push(i);
            ans.push(tmp);
        }
    }
    else {
        for iter in combination(n-1, k-1) {
            let max = iter.iter().max().unwrap();
            for j in *max+1..n+1 {
                let mut tmp = iter.clone();
                tmp.push(j);
                ans.push(tmp);
            }
        }
    }
    ans
}

use std::cmp::max;

fn main() {
    input!{
        _n: usize,
        mut c: Chars,
    }
    let mut r = c.iter().filter(|&n| *n == 'R').count();
    let mut w = 0;
    let mut ans = r;
    for iter in c {
        if iter == 'R' {
            r -= 1;
        }
        else {
            w += 1;
        }
        if max(r, w) < ans {
            ans = max(r, w);
        }
    }
    println!("{}", ans);
}


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

#define ll long long
#define rep(i,x,y) for(int i=x;i<y;i++)
#define rel(i,x,y) for(int i=x-1;i>=y;i--)
#define all(x) x.begin(),x.end()

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int n,m;
    cin >> n >> m;
    int p[m];
    int wacnt[100010] = {};
    string s[m];
    bool cnt[100010] = {};
    int ac = 0;
    rep(i,0,m) cin >> p[i] >> s[i]; 
    rep(i,0,m){
        if(cnt[p[i]]) continue;
        if(s[i] == "WA") wacnt[p[i]]++;
        if(s[i] == "AC"){
            ac++;
            cnt[p[i]] = true;
        }
    }
    int wa = 0;
    rep(i,0,100010){
        if(cnt[i]) wa += wacnt[i];
    }
    cout << ac << " " << wa << endl;
}

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

int top = 0, S[1000];

int pop(){
	top--;
	return S[top + 1];
}

void push(int x){
	S[++top] = x;
}

int main(){
	char s[100];
	while(scanf("%s", s) != EOF){
		
		if(s[0] == '+'){
			int a = pop();
			int b = pop();
			push(a + b);
		}else if(s[0] == '*'){
			int a = pop();
			int b = pop();
			push(a * b);
		}else if(s[0] == '-'){
			int a = pop();
			int b = pop();
			push(b - a);
		}else{
			push(atoi(s));
		}
		//break;
	}
	
	printf("%d\n", S[1]);
	return 0;
}

Measured memory_bytes: 3224
#include <bits/stdc++.h>
#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <random>
#define rep(i,n) for (int i = 0; i < (n); ++i)
#define repp(i,n,m) for (int i = m; i < (n); ++i)
#define repl(i,n) for (long long i = 0; i < (n); ++i)
#define reppl(i,n,m) for (long long i = m; i < (n); ++i)
using namespace std;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using PL = pair<long long, long long>;
using Pxy = pair<double, double>;
using T = tuple<int, int, bool>;
const int INF = 1001001007;
const int mod = 1000000007;
const int MOD = 998244353;
const ll inf = 1e18;
template <typename AT>
void printvec(vector<AT> &ar){
    rep(i,ar.size()-1) cout << ar[i] << " ";
    cout << ar[ar.size()-1] << endl;
}
template <typename Q>
void printvvec(vector<vector<Q>> &ar){
    rep(i,ar.size()){
        rep(j,ar[0].size()-1) cout << ar[i][j] << " ";
        cout << ar[i][ar[0].size()-1] << endl;
    }
}
template <typename S>
bool range(S a, S b, S x){
    return (a <= x && x < b);
}

void yes(int n){
    cout << "Yes" << endl;
}

void no (int n){
    cout << "No" << endl;
}

int main() {
    ll n, k; cin >> n >> k;
    vector<ll> ar(n);
    repl(i,n) cin >> ar[i];
    ll cnt = 0;
    rep(i,n) cnt += ar[i];
    if (cnt <= k){
        cout << 1 << endl;
        return 0;
    }
    ll le = 1;
    ll ri = 1e9 + 10;
    ll mid = (le + ri) / 2;
    while (ri - le > 1){
        ll c = 0;
        rep(i,n){
            c += (ar[i] - 1) / mid;
        }
        //cout << mid << " " << c << endl;
        if (c <= k) ri = mid;
        else le = mid;
        mid = (le + ri) / 2;
    }
    cout << ri << endl;
}

Measured memory_bytes: 4680
#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <functional>
#include <cmath>
#include <set>
#include <queue>
#include <deque>
#include <vector>
#include <climits>
#include <sstream>
#include <iomanip>
#include <map>
#include <stack>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;

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

	auto num = 0;
	auto pre = 0;
	for (auto i = 0; i < N; ++i)
	{
		if (S[i] == ')')
		{
			if (num > 0)
			{
				--num;
			}
			else
			{
				++pre;
			}
		}
		else
		{
			++num;
		}
	}

	for (auto i = 0; i < pre; ++i)
	{
		cout << "(";
	}
	cout << S;
	for (auto i = 0; i < num; ++i)
	{
		cout << ")";
	}
	cout << endl;

	return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;

#define ff              first
#define ss              second
#define int             long long
#define pb              push_back
#define mp              make_pair
#define pii             pair<int,int>
#define vi              vector<int>
#define mii             map<int,int>
#define pqb             priority_queue<int>
#define pqs             priority_queue<int,vi,greater<int> >
#define setbits(x)      __builtin_popcountll(x)
#define zrobits(x)      __builtin_ctzll(x)
#define mod             1000000007
#define inf             1e18
#define ps(x,y)         fixed<<setprecision(y)<<x
#define mk(arr,n,type)  type *arr=new type[n];
#define w(x)            int x; cin>>x; while(x--)
#define FIO             ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
mt19937                 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

int check(int n, int k)
{
	while (n >= k && (n % k) == 0)
		n /= k;

	n %= k;

	if (n != 1)
		n = 0;

	return n;
}

int32_t main()
{
	FIO;
	int n; cin >> n;
	int ans = 0;
	n--;

	for (int i = 1; i * i <= n; ++i)
	{
		if (n % i)
			continue;
		ans++;

		if (i * i != n)
			ans++;
	}

	n++;

	for (int i = 2; i * i <= n; ++i)
	{
		if (n % i)
			continue;

		ans += check(n, i);

		if (i * i != n)
			ans += check(n, n / i);
	}

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

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

using namespace std;

#define M 1000000007
#define pb push_back
#define f first
#define s second
#define rep(i, st, ed) for(int i=st; i<ed; i++)
#define repn(i, st, ed) for(int i=st; i<=ed; i++)
#define repb(i, ed, st) for(int i=ed; i>=st; i--)

typedef long long ll;
typedef unsigned long long int llt;
typedef long double ld;

const long double PI  =3.141592653589793238463;
const int N = 5e5 + 10;
const ll INF = 1LL << 60;

template<class T> void chmax(T &a,T b) { if (a<b) a=b;}
template<class T> void chmin(T &a,T b) { if (a>b) a=b;}


vector<int> g[N];
bool viss[N];
int vis[N];

// Normal DFS
void dfs(int curr, int par)
{
  for(auto x: g[curr])
    if(x != par)
      dfs(x, curr);
}

// DFS with visiting status
void dfs1(int curr, int par)
{
  viss[curr] = 1;
  for(auto x: g[curr])
    if(!viss[x])
      dfs1(x, curr);
}

// DFS with strongly connected component
void dfs2(int curr, int par, int num)
{
  vis[curr] = num;
  for(auto x: g[curr])
    if(vis[x] == 0 || vis[x] > (num+1))
      dfs2(x, curr, num+1);
}

// XOR from 0 to n
ll fxor(ll n)
{
  if(n < 0) return 0;
  if(n % 4 == 3) return 0;
  else if(n % 4 == 0) return n;
  else if(n % 4 == 1) return n^(n-1);
  else if(n%4 == 2) return n^(n-1)^(n-2);
}

// Power in logn with mod 1000000007
llt ppow(llt x, llt y)
{
  llt res = 1;
  while(y > 0){
    if(y&1)
      res = (res * x)%M;
    y = y >> 1;
    x = (x * x)%M;
  }
  return res;
}

// Factorial with dp
llt factdp[N];
llt fact(llt x)
{
  if(x == 0) return 1;
  if(x == 1) return 1;
  if(factdp[x] != 0) return factdp[x];
  return factdp[x] = (x*fact(x-1))%M;
}
// Combination
ll modcomb(ll n, ll r)
{
  if(n < r) return 0;
  ll res = fact(n);
  (res *= ppow(fact(r), M-2)) %= M;
  (res *= ppow(fact(n-r), M-2)) %= M;
  return res;
}

// String return to base b
string ansConv ="";
void convert10tob(llt N, int b)
{
     if (N == 0)
        return;
     int x = N % b;
     N /= b;
     if (x < 0)
        N += 1;
     convert10tob(N, b);
     ansConv += to_string(x);
     return;
}

// Convert string to num wiht base b
llt convertstrtob(string a, int b)
{
  llt aa = 0;
  llt mul = 1;
  for(int i=a.length()-1; i>=0; i--)
  {
    int curr = a[i] - '0';
    aa += (curr * mul);
    mul *= b;
  }
  return aa;
}

// Union Find
// Find()
int parent[N], ran[N];
int find(int x)
{
    if(parent[x]==x)return x;
    else return parent[x]=find(parent[x]);
}
// Union()
void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;

    if(ran[x]<ran[y])
        parent[x]=y;
    else{
        parent[y]=x;
        if(ran[x]==ran[y])ran[x]++;
    }
}

// Main Code

int main()
{
  llt k;
  cin>>k;
  llt n = 50;
  llt z = k / n;
  llt rem = k % n;
  llt arr[n];
  rep(i, 0, n) arr[i] = i + z;
  rep(i, 0, rem) arr[n-1-i]++;
  cout<<n<<endl;
  rep(i, 0, n)
    cout<<arr[i]<<" ";
  cout<<endl;
}


Measured memory_bytes: 14080
X,K,D = map(int,input().split())
if K*D<=abs(X):
    print(abs(X)-K*D)
elif (K-(abs(X)//D))%2==0:
    print(abs(X)%D)
elif (K-(abs(X)//D))%2==1:
    print(-(abs(X)%D-D))

Measured memory_bytes: 9080
"""


第5回 ドワンゴからの挑戦状 予選　　B - Sum AND Subarrays

N<=1000より美しさの全列挙は可能
K個選んでbitごとの論理積の最大値

K個選ぶ方法はnCk(10**6?, K)とかなので、全探索は間に合わない

K個選んだもののうちの最大、を言い換えを考える。
bitごとの論理積をとるので、選ばれたK個の中で、bitが大きいものについて、K個すべてで1が立っていると嬉しい。
また、2**0 + ... + 2**(N-1) <= 2**N なので、大きいbitが一個立ってる方が、それより小さいもの全てが立っているより嬉しい。
→大きいbitから見ていって、各美しさでそのbitに1が立っているか調べて、K個以上立っていれば、その美しさの中からK個採用される
　この時いずれの美しさも、今見ているbitが立っているので、答えにそのbit分加える。
　で、次のbitをみていって～を繰り返す。
　最下位bitまで見ても、美しさがK個以上のこっているなら、そこから適当にK個選んだら同じ答えになるので気にしなくてよい

bitごとの論理積が大きくなるようにK個選ぶ　→　大きいbitから、そのbitが立っているものがK個以上ある物が選ばれる
の言いかえ
"""

N,K = map(int, input().split())
A = list(map(int, input().split()))

accum = [0] * N
accum[0] = A[0]
for i in range(1,N):
    accum[i] = accum[i-1] + A[i]

beauty = []
for l in range(N):
    for r in range(l, N):
        if l == 0:
            beauty.append(accum[r])
        else:
            beauty.append(accum[r] - accum[l-1])


# 10**9 * 1000 から、だいたい2**40ぐらい
ans = 0
candidate = beauty
for i in range(40, -1, -1):
    nxt_candidate = []
    cnt = 0
    for b in candidate:
        if b & (1 << i):
            cnt += 1
            nxt_candidate.append(b)
    
    # iビット目が立っている個数がKに満たなければ、現在の美しさ集合について、より下位のビットを見る
    # K個以上あれば、iビット目が立ってない奴は選ばれないので除外できる
    if cnt >= K:
        ans += 2**i
        candidate = nxt_candidate

print(ans)

Measured memory_bytes: 65916
#include <stdio.h>
#include <string.h>

int main(void){
  int N, L, i, j;
  char string[101][101], save[101];
  scanf("%d %d", &N, &L);
  for(i=0; i<N; i++) scanf("%s",string[i]);
  for(i=0; i<N; i++){
    for(j=i+1; j<N; j++){
      if(strcmp(string[i],string[j]) > 0){
        strcpy(save,string[i]);
        strcpy(string[i],string[j]);
        strcpy(string[j],save);
      }
    }
  }
  for(i=0; i<N; i++) printf("%s",string[i]);
  return 0;
}

Measured memory_bytes: 1716
#include <bits/stdc++.h>
#define fi first
#define se second
#define repl(i,a,b) for(int i=(int)(a);i<(int)(b);i++)
#define rep(i,n) repl(i,0,n)
#define sort(a) sort((a).begin(),(a).end())
#define rev(a) reverse((a).begin(),(a).end())
using db = double;
using namespace std;
typedef long long ll;


int main() {
  int a, b, t;
  cin >> a >> b >> t;
  int ans = t / a * b;
  cout << ans << endl;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define REP(i,m,n) for(int i=(int)(m); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i,m,n) for(int i=(int)(m); i>=(int)(n); i--)
#define rrep(i,n) RREP(i,n-1,0)
#define all(v) v.begin(), v.end()
const int inf = 1e9+7;
const ll longinf = 1LL<<60;
const ll mod = 1e9+7;
const ld eps = 1e-10;

#define vec point
struct point {
  ld x, y;
  point(ld x, ld y) : x(x), y(y) {}
  point operator+(const point& rhs) const {
    return point(x+rhs.x, y+rhs.y);
  }
  point operator-(const point& rhs) const {
    return point(x-rhs.x, y-rhs.y);
  }
  point operator*(const ld& d) const {
    return point(x*d, y*d);
  }
  point operator/(const ld& d) const {
    assert(d != 0);
    return point(x/d, y/d);
  }
  ld length() {
    return sqrt(x*x+y*y);
  }
  point perpendicular() {
    ld d = this->length();
    assert(d != 0);
    return point(y, -x) / d;
  }
};
point midpoint(point p1, point p2) {
  return (p1+p2)/2;
}
struct circle {
  point center;
  ld r;
  circle(ld cx=0, ld cy=0, ld r=1) : center(point(cx, cy)), r(r) {}
  circle(point center, ld r) : center(center), r(r) {}
};
vector<point> intersection(circle c1, circle c2) { // c1.r == c2.r
  ld r = c1.r;
  point mid = midpoint(c1.center, c2.center);
  vec dir = c2.center - c1.center;
  ld dh = dir.length();
  vec perp = dir.perpendicular();
  ld dv = sqrt(r*r-(dh/2)*(dh/2));
  vector<point> ret;
  if(dh > r*2+eps) { // no intersection
  } else if(dv == 0) {
    ret.push_back(mid);
  } else {
    ret.push_back(mid+perp*dv);
    ret.push_back(mid-perp*dv);
  }
  return ret;
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);
  int n; cin >> n;
  vector<pair<ld, ld>> P(n);
  rep(i, n) cin >> P[i].first >> P[i].second;
  auto test = [&](ld r) {
    vector<circle> C(n);
    rep(i, n) C[i] = circle(P[i].first, P[i].second, r);
    bool ret = false;
    rep(i, n) REP(j, i+1, n) {
      auto inter = intersection(C[i], C[j]);
      if(inter.size() == 0) continue;
      for(auto p: inter) {
        bool ok = true;
        rep(k, n) {
          if((p-C[k].center).length() > r+eps) ok = false;
        }
        if(ok) ret = true;
      }
    }
    return ret;
  };
  auto bsearch = [&]() {
    ld ok = 2000, ng = 0;
    rep(i, 50) {
      ld mid = (ok+ng)/2;
      if(test(mid)) ok = mid;
      else ng = mid;
    }
    return ok;
  };
  cout << bsearch() << "\n";
  return 0;
}


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

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int n,cnt=0,ma=0;
	cin>>n;
	vector<int>v(n);
	for(int i=0;i<n;i++){
		cin>>v.at(i);
		if(i>0){
			if(v.at(i-1)>=v.at(i)){
				cnt++;
				ma=max(cnt,ma);
			}else{
				cnt=0;
			}
		}
	}
	cout<<ma<<endl;
}


Measured memory_bytes: 640
#include<bits/stdc++.h>
using namespace std;
#define ll long long
namespace io{
	const int l=1<<19;
	char *s,*t,buf[l],c;
	char gc(){
		if(s==t){
			t=(s=buf)+fread(buf,1,l,stdin);
			return s==t?EOF:*s++;
		}
		return *s++;
	}
	template<class IT>void gi(IT &x){
		x=0;c=gc();while(c<'0'||c>'9')c=gc();
		while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);c=gc();}
	}
}
using io::gc;
using io::gi;
template<class IT>void chkmin(IT &a,IT b){if(b<a)a=b;}
template<class IT>void chkmax(IT &a,IT b){if(a<b)a=b;}

const int N=186;

int n,m,a[N][N],f[2][N][N][N],g[2][N][N][N],cur;
char c[N];
int chk(int x,int y,int X,int Y){
	if(X>n||Y>m)return 0;
	--x;--y;
	static int s,t;
	s=a[X][Y]-a[X][y]-a[x][Y]+a[x][y];
	t=(X-x)*(Y-y);
	return s==0||s==t;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",c+1);
		for(int j=1;j<=m;j++){
			a[i][j]=a[i][j-1];
			if(c[j]=='#')++a[i][j];
		}
		for(int j=1;j<=m;j++)a[i][j]+=a[i-1][j];
	}
	for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)for(int k=1;k<=m;k++){
		if(f[0][i][j][k-1]>=k)f[0][i][j][k]=f[0][i][j][k-1];
		else{
			int t=k;
			while(chk(i,k,j,t))++t;
			f[0][i][j][k]=t-1;
		}
	}
	for(int i=1;i<=m;i++)for(int j=i;j<=m;j++)for(int k=1;k<=n;k++){
		if(g[0][i][j][k-1]>=k)g[0][i][j][k]=g[0][i][j][k-1];
		else{
			int t=k;
			while(chk(k,i,t,j))++t;
			g[0][i][j][k]=t-1;
		}
	}
/*	for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){
		printf("f[%d][%d]=",i,j);
		for(int k=1;k<=m;k++)printf(" %d",f[cur][i][j][k]);
		printf("\n");
	}
	for(int i=1;i<=m;i++)for(int j=i;j<=m;j++){
		printf("g[%d][%d]=",i,j);
		for(int k=1;k<=n;k++)printf(" %d",g[cur][i][j][k]);
		printf("\n");
	}*/
	for(int o=0;o<=20;o++){
		if(f[cur][1][n][1]>=m||g[cur][1][m][1]>=n){printf("%d",o);return 0;}
		memset(f[cur^1],0,sizeof(f[cur^1]));
		memset(g[cur^1],0,sizeof(g[cur^1]));
		for(int i=1;i<=n;i++)for(int j=i;j<=n;j++)for(int k=1;k<=m;k++){
			int t=f[cur][i][j][k];
			if(t>=m){f[cur^1][i][j][k]=m;continue;}
			t=f[cur][i][j][t+1];
			while(1){
				int T=g[cur][k][t+1][i];
				if(T>=j){++t;continue;}
				T=g[cur][k][t+1][T+1];
				if(T>=j)++t;else break;
			}
			f[cur^1][i][j][k]=t;
		}
		for(int i=1;i<=m;i++)for(int j=i;j<=m;j++)for(int k=1;k<=n;k++){
			int t=g[cur][i][j][k];
			if(t>=n){g[cur^1][i][j][k]=n;continue;}
			t=g[cur][i][j][t+1];
			while(1){
				int T=f[cur][k][t+1][i];
				if(T>=j){++t;continue;}
				T=f[cur][k][t+1][T+1];
				if(T>=j)++t;else break;
			}
			g[cur^1][i][j][k]=t;
		}
		cur^=1;
	}
	return 0;
}

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

#define pb push_back
#define mp make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef complex<double> point;
#define xx real()
#define yy imag()

#define REP(i, a, b) for(int i = (a); i < (int)(b); i++)
#define REPN(i, a, b) for(int i = (a); i <= (int)(b); i++)
#define FA(it, x) for(__typeof((x).begin()) it = (x).begin(); it != (x).end(); it++)
#define SZ(x) (int)(x).size()
#define BE(x) (x).begin(), (x).end()
#define SORT(x) sort(BE(x))
#define _1 first
#define _2 second

#define x1 gray_cat_x1
#define y1 gray_cat_y1

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

#define file "I1"

const double EPS = 1e-9;
const double PI = acos(-1.);
const int INF = 1e9;
const ll MOD = 1e9 + 7;

const int MAXN = 6e2 + 5;

char c[MAXN][MAXN];

int add[MAXN][MAXN];

void solve(){
	int n;
	scanf("%d", &n);
	REP(i, 0, n){
		scanf("%s", &c[i][0]);
		REP(j, n, 2 * n - 1){
			c[i][j] = c[i][j - n];
		}
	}
	REP(i, n, 2 * n - 1){
		REP(j, 0, 2 * n - 1){
			c[i][j] = c[i - n][j];
		}
	}
	
	REP(i, 0, 2 * n - 1){
		REP(j, 0, 2 * n - 1){
			for(int i1 = i - 1, j1 = j + 1, k = 1; k < n && i1 >= 0 && j1 < 2 * n - 1; k++, i1--, j1++){
				if (c[i][j] != c[i1][j1]){
					add[i1 + 1][j + 1]--;
					int i2 = i - n + 1, j2 = j1 - n + 1;
					if (i2 < 0){
						j2 += (-i2);
						i2 = 0;
					}
					if (j2 < 0){
						i2 += (-j2);
						j2 = 0;
					}
					/*if (i2 == 1 && j2 == 0){
						printf("333 %d %d %d %d\n", i, j, i1, j1);
					}*/
					add[i2][j2]++;
				}
			}
		}
	}
	int ans = 0;
	REP(i, 0, n){
		REP(j, 0, n){
			if (i && j){
				add[i][j] += add[i - 1][j - 1];
			}
			if (!add[i][j]){
				ans++;
			}
		}
	}
	
	/*REP(i, 0, n){
		REP(j, 0, n){
			printf("%d ", add[i][j]);
		}
		putchar('\n');
	}*/
	
	printf("%d\n", ans);
}   

int main(){

    //freopen(file".in", "r", stdin); freopen(file".out", "w", stdout);
    int t = 1;
    //cin >> t;
    while(t--){
        solve();    
    }
}


Measured memory_bytes: 2048
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue> //C++
#include <string> //C++
#include <iostream> //C++
#include <vector> //C++
#include <algorithm> //C++
#include<map> //C++
using namespace std; //C++
#define rep(i, a, n) for (i = (a); i < (n); i++)
#define  max(x,y) ((x)>(y)?(x):(y))
#define  min(x,y) ((x)>(y)?(y):(x))

//C++で提出



// string s="AAA";    s.size() =3    (sのサイズ) ...1
// vector <int> a;    配列a(サイズは0) ...2
// a.push_back(10);   配列のサイズが一つ増えて一番後ろに10を代入 ...2
// A.pop_back();   最後の要素が消去される
// sort(A.begin(),A.end());   配列Aの最初の要素から最後の要素(/.)より前までを小さい順に並び替えてa[0]から代入していく...3
// reverse(A.begin(),A.end());   配列Aの最初の要素から最後の要素(/.)までを逆の順にしてa[0]から代入していく
// s.substr(3,2)   配列s[3]から2個の文字を抜き出した文字列 (s[3]とs[4]) ...4
// strcmp(s1,s2)  文字列が等しければ0を出力　s1>s2なら1 s1<s2なら-1を出力　C言語用なので配列は、s1[100]にする...5





int main()
{
	long long int s, c;
	cin >> s >> c;
	long long int count=0;
	
	if (s * 2 <= c) {
		count = s;
		count += (c - s * 2) / 4;
	}
	else {

		count +=(c / 2);
	
	}


    cout << count;


	return 0;
}
	




Measured memory_bytes: 384
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        long res = 0;
        for (int i = 0; i < a.length; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a);
        for (int i = 0; i < n - 1; i++) {
            res += a[n - 1 - ((i + 1) / 2)];
        }
        System.out.println(res);
        sc.close();
    }
}

Measured memory_bytes: 60656
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10005];
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	sort(a+1,a+n+1);
	int ans=0;
	for(int i=n;i>n-m;i--) 
	{
		ans+=a[i];
	}
	cout<<ans;

	return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <tuple>
using namespace std;
typedef long long ll;

int main(){

    int n; cin >> n;

    ll cnt[5] = {};
    string march = "MARCH";
    string str;

    for(int i=0; i<n; i++){
        cin >> str;
        for(int i=0; i<5; i++){
            if(str[0] == march[i]){
                cnt[i]++;
                break;
            }
        }
    }

    // for(int i=0; i<5; i++) cout << cnt[i] << endl;

    ll ans = 0;
    for(int i=0; i<5; i++){
        for(int j=i+1; j<5; j++){
            for(int k=j+1; k<5; k++){
                ans += cnt[i]*cnt[j]*cnt[k];
            }
        }
    }

    cout << ans;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (int)(n); i++)
#define rrep(ri,n) for(int ri = (int)(n-1); ri >= 0; ri--)
#define rep2(i,x,n) for(int i = (int)(x); i < (int)(n); i++)
#define repit(itr,x) for(auto itr = x.begin(); itr != x.end(); itr++)
#define rrepit(ritr,x) for(auto ritr = x.rbegin(); ritr != x.rend(); ritr++)
#define ALL(x) x.begin(), x.end()
using ll = long long;
using namespace std;

int main(){
  ll n, k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n){
    int in;
    cin >> in;
    in--;
    a.at(i) = in;
  }
  int l = log2(k);
  l++;
  vector<vector<int>> nx(l, vector<int>(n));
  nx.at(0) = a;
  rep2(i, 1, l){
    rep(j, n){
      nx.at(i).at(j) = nx.at(i-1).at(nx.at(i-1).at(j));
    }
    // rep(j, n){
    //   cerr << nx.at(i).at(j) << " ";
    // }
    // cerr << endl;
  }

  int now = log2(k);
  now++;
  int ans = 0;
  rrep(i, now){
    if((k & (1LL << i)) != 0){
      ans = nx.at(i).at(ans);
    }
  }
  cout << ans+1 << endl;
  return 0;
}

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

int main()
{
  vector<vector<int>> c(3, vector<int>(3));
  int i, j;
  for(i = 0; i < 3; i++)
  {
	for(j = 0; j < 3; j++)
    {
		cin >> c.at(i).at(j);
    }
  }
  int x, y, z;
  bool found;
  for(x = 0; x <= 100; x++)
  {
	for(y = 0; y <= 100; y++)
    {
	  for(z = 0; z <= 100; z++)
      {
        found = true;
		for(i = 0; i < 3; i++)
        {
		    if(c.at(0).at(i)-x != c.at(1).at(i)-y || c.at(1).at(i)-y != c.at(2).at(i)-z)
            {
              found = false;
			  break;
            }
        }
        if(found)break;
      }
      if(found)break;
    }
    if(found)break;
  }
  if(found) cout << "Yes" << endl;
  else cout << "No" << endl;
}   

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <numeric>
#include <string>
using namespace std;

long long calcXOR(long long n){
  long long tmp = (n + 1) / 2;
  long long ans = tmp % 2 == 0? 0 : 1;
  if (n % 2 == 1)
    return ans;
  return ans ^ max(n, 0LL);
}

int main(){
  long long a, b;
  cin >> a >> b;
  long long answer = calcXOR(a - 1) ^ calcXOR(b);
  cout << answer << endl;
  return 0;
}


Measured memory_bytes: 256
#include"iostream"
#include"stdio.h"
#include"string"

using namespace std;

int a[100];

int main()
{
    int a, b, c, k;
    int ans = 0;
    scanf("%d%d%d%d" ,&a, &b, &c, &k);
    int M = max(max(a, b), c);
    ans = -M;
    for(int i = 1; i <= k; i++)
        M <<= 1;
    ans += M + a + b + c;
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll MOD = (ll)1e9 + 7;

string A, B, C;

int main() {
	while(cin >> A, A != "0") {
		cin >> B >> C;

		reverse(A.begin(), A.end());
		reverse(B.begin(), B.end());
		reverse(C.begin(), C.end());

		int n = B.size();

		ll dp[55][2] = { 0 };

		dp[0][0] = 1;
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < 2; j++) {
				int q = 0, s = 0, t = 0;
				if(A[i] == '?') q++;
				else s += A[i] - '0';
				if(B[i] == '?') q++;
				else s += B[i] - '0';
				if(C[i] != '0') t = C[i] - '0';

				if(q == 2) {
					for(int a = 0; a <= 9; a++) {
						if(i == n - 1 && a == 0) continue;
						for(int b = 0; b <= 9; b++) {
							if(i == n - 1 && b == 0) continue;
							if(i == n - 1 && (t == 0 || (a + b + j) % 10 == 0)) continue;
							if((C[i] == '?' || (a + b + j) % 10 == t)) {
								if(a + b + j >= 10) {
									(dp[i + 1][1] += dp[i][j]) %= MOD;
								}
								else {
									(dp[i + 1][0] += dp[i][j]) %= MOD;
								}
							}
						}
					}
				}
				else if(q == 1) {
					for(int a = 0; a <= 9; a++) {
						if(i == n - 1 && a == 0) continue;
						if((i == n - 1 && (s + a + j) % 10 == 0)) continue;
						if(C[i] == '?' || (s + a + j) % 10 == t) {
							if(s + a + j >= 10) {
								(dp[i + 1][1] += dp[i][j]) %= MOD;
							}
							else {
								(dp[i + 1][0] += dp[i][j]) %= MOD;
							}
						}
					}
				}
				else { // q == 0
					if((i == n - 1 && (s + j) % 10 == 0)) continue;
					if(C[i] == '?' || (s + j) % 10 == t) {
						if((s + j) >= 10) {
							(dp[i + 1][1] += dp[i][j]) %= MOD;
						}
						else {
							(dp[i + 1][0] += dp[i][j]) %= MOD;
						}
					}
				}
			}// for j
		}// for i
		cout << dp[n][0] << endl;
	}// while
}// main

Measured memory_bytes: 3000
#include <iostream>
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<math.h>
#define ll long long
using namespace std;
const ll val=1e9+7;
long long s_modu(long long  x)
{
    if(x<3) return x;
    ll res=x;
    for(long long  i=x-1;i>1;i--)
    {
        res=((i%val)*(res%val))%val;
    }
    return res;

}


int main()
{
    ll n,m;
    scanf("%lld%lld",&n,&m);
    if(llabs(n-m)>1)
        printf("%lld",0);
    else if(n != m)
        printf("%lld",(s_modu(n)*s_modu(m))%val);
    else
    {
        ll temp=( s_modu(n) * s_modu(m) )%val;
        temp = ((temp % val)*2)%val;
        printf("%lld",temp);
    }
    return 0;
}


Measured memory_bytes: 256