akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<cstdint>

int64_t const MOD = 1e9+7;
int64_t const MAXN = 2e5;

int64_t fact[MAXN+1];
int64_t ifact[MAXN+1];
int64_t inv[MAXN+1];

void init(int64_t n) {
  fact[0] = fact[1] = 1;
  ifact[0] = ifact[1] = 1;
  inv[0] = inv[1] = 1;
  for(int i = 2; i <= n; ++i) {
    fact[i] = fact[i-1]*i%MOD;
    inv[i] = MOD - (MOD/i)*inv[MOD%i]%MOD;
    ifact[i] = ifact[i-1]*inv[i]%MOD;
  }
}

int64_t comb(int64_t n, int64_t a) {
  int64_t res = fact[n]*ifact[a]%MOD;
  (res *= ifact[n-a]) %= MOD;
  return res;
}

int64_t hcomb(int64_t n, int64_t a) { return comb(n+a-1, a); }

int main() {
  int64_t n, k; std::cin >> n >> k;
  k = std::min(k, n-1);
  init(n);
  int64_t ans = 0;
  // we have to remove the count of original state when k = 1
  // however, the constraint says k >= 2
  /* if(k == 1) ans += MOD-1; */
  // count of states with #empty rooms <= k
  // sum of i in [0,k] comb(n,i)*hcomb(n-i, i)
  for(int i = 0; i <= k; ++i) (ans += comb(n, i)*hcomb(n-i, i)%MOD) %= MOD;
  std::cout << ans << std::endl;
  return 0;
}


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

using namespace std;

typedef long long ll;

vector<bool> valid;
vector<ll> nums;
vector<ll> nums1;
vector<ll> nums2;

int main(){
	ll n;
	ll max = 1;
	cin >> n;

	nums.resize(n);
	nums1.resize(n,0);
	nums2.resize(n,0);
	for(ll i=0; i<n; i++) cin >> nums[i];
	
	for(ll i=0; i<n-1; i++){
		nums1[i+1] = __gcd(nums1[i],nums[i]);
	}
	for(ll i=n-1; i>0; i--){
		nums2[i-1] = __gcd(nums2[i],nums[i]);
	}

	for(ll i=0; i<n; i++){
		if(max<__gcd(nums1[i],nums2[i])) max = __gcd(nums1[i],nums2[i]);
	}

	cout << max << endl;

	return 0;
}

Measured memory_bytes: 2560
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll a[26];
string s;
int main()
{
	cin>>s;
	for(int i=0;i<s.size();i++)
		a[s[i]-'a']++;
	ll L=s.size();
	ll ans=L*(L-1)/2+1;
	for(int i=0;i<26;i++)
		ans-=a[i]*(a[i]-1)/2;
	cout<<ans<<endl;
	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#include <cmath>
using namespace std;
#define fast                                                                   \
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
#define ll long long
#define f(i, n) for (int i = 0; i < n; i++)
#define fo(i,a,n) for (i = a; i <= n; i++)
#define F first
#define S second
#define pii pair<int,int>
#define sz size()
#define all(v) v.begin(),v.end()
#define pb push_back
#define pf push_front    
#define PB pop_back
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<int>
#define mp make_pair
#define mod 1000000007
typedef unsigned long long ull;
const int N = 200005;
const int MOD = 998244353 ;


int dp[10010];
void solve(){
    int h, n;
    cin>>h>>n;
    vector<pair<int,int> > v;
    f(i,10011)dp[i] = LLONG_MAX;
    f(i,n){
        int x, y;
        cin>>x>>y;
        v.pb(mp(x,y));
        dp[x] = y;
    }
    for(int i = 1; i <= h; i++){
        f(j,v.size()){
            if(v[j].F >= i)dp[i] = min(dp[i],v[j].S);
            else dp[i] = min(dp[i],((v[j].S) + dp[(i - (v[j].F))]));
        }
    } 
    cout<<dp[h];
}

int32_t main() {
    fast
    int t;
    t = 1;
    //cin >> t;
    while(t--)solve();
    return 0;
}


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

// 約数列挙
vector<long long> calc_divisor(long long n) {
    vector<long long> res;
    for (long long i = 1LL; i*i <= n; ++i) {
        if (n % i == 0) {
            res.push_back(i);
            long long j = n / i;
            if (j != i) res.push_back(j);
        }
    }
    sort(res.begin(), res.end());
    return res;
}

int main(void){
    // Your code here!
    long long A,B;
    cin >> A>>B;
    if(A>B)swap(A,B);
    vector<long long> div1 = calc_divisor(A);
    vector<long long> div2 = calc_divisor(B);   
    vector<long long> intersection;
    // vector<int>::iterator it = // iterator is not needed anymore
    set_intersection(div1.begin(), div1.end()
                     , div2.begin(), div2.end()
                     , inserter(intersection, intersection.end()));
    
    //for(int i = 0; i <intersection.size();i++)cout << intersection[i]<<endl;
        
    vector<long long> ans;
    int cnt = 0;

    bool flag = true;
    for(int i = 0; i <intersection.size();i++){
        for(int j = 0; j <ans.size();j++){
            
                //cout <<intersection[i]<<" "<<ans[j]<<endl;
                if(intersection[i]%ans[j]==0&&ans[j]!=1){
                    flag = false;
                    break;
                }

        }
        
        if(flag == true){
            cnt++;
            //cout << intersection[i]<<endl;
            ans.push_back(intersection[i]);
        }
        flag = true;
    }       
    
    cout << cnt<<endl;
    
}


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

int main(){
#ifndef ONLINE_JUDGE
    freopen("ip.txt", "r", stdin);
    freopen("op.txt", "w", stdout);
#endif
	long long n, w;
	cin >> n >> w;
	vector<long long> v(n +1), wt(n +1);
	for(int i = 0; i < n; ++i){
		cin >> wt[i +1] >> v[i +1];
	}

	long long dp[n +1][w +1];
	memset(dp, 0, sizeof dp);

	for(int i = 1; i <= n; ++i){
		for(int j = 1; j <= w; ++j){
			if(wt[i] <= j){
				dp[i][j] = max(dp[i -1][j], dp[i -1][j - wt[i]] + v[i]);
			}else{
				dp[i][j] = dp[i -1][j];
			}
		}
	}

	cout << dp[n][w] << endl;


}

Measured memory_bytes: 82388
#include<bits/stdc++.h>
using namespace std;
#define fs first
#define sc second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define ALL(A) A.begin(),A.end()
#define RALL(A) A.rbegin(),A.rend()
typedef long long LL;
typedef pair<LL,LL> P;
const LL mod=1e9+7;
const LL LINF=1LL<<62;


vector<int> M[100001],ch(100001,false);
vector<int> fr,bf;

void dfs(int u,int v,int c){
    ch[u]=true;
    for(int i=0;i<M[u].size();i++){
        if(!ch[M[u][i]]&&M[u][i]!=v){
            if(c==0) fr.pb(M[u][i]);
            else bf.pb(M[u][i]);
            dfs(M[u][i],u,c);
            if(c==1||(c==0&&u!=1)) break;
            if(u==1) c++;
        }
    }
}

int main(){
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a >> b;
        M[a].pb(b);
        M[b].pb(a);
    }
    dfs(1,1,0);
    reverse(ALL(bf));
    cout << bf.size()+fr.size()+1 << endl;
    for(int i=0;i<bf.size();i++){
        cout << bf[i] << " ";
    }
    cout << 1 << (fr.size()?" ":"\n");
    for(int i=0;i<fr.size();i++){
        cout << fr[i] << (i==fr.size()-1?"\n":" ");
    }
    return 0;
}

Measured memory_bytes: 14328
#include <bits/stdc++.h>
#define repd(i,a,b) for (int i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define int long long
typedef long long ll;
const int MOD = 1000000007;
const int INF = 1010000000;
const double EPS = 1e-10;
using namespace std;
const pair<int,int> fd[] = {make_pair(1,0),make_pair(-1,0),make_pair(0,1),make_pair(0,-1)}; 

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

Measured memory_bytes: 256
#include <bits/stdc++.h>
#include <stdio.h>
#include <math.h>
#include <cmath>
using namespace std;
#define vsort(vec) sort(vec.begin(), vec.end())
#define vreverse(vec) reverse(vec.begin(), vec.end())
using ll =long long;
const ll INF =1001001001;

//最大公約数
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);
}



//階乗　20くらいが限界
ll factorial(ll n){
  ll a=1;ll b=n;
  for(int i=0;i<n;i++){
    a*=b;
    b--;
  }
  return a;
}

//組み合わせ　nCr
ll comb(ll a,ll b){
  ll c;
  c=factorial(a)/(factorial(a-b)*factorial(b));
  return c; 
}




/*10億7。　　　100000007
2*2行列 H*W
vector<vector<int>> vec(H,vector<int>(W));
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
cin>>vec[i][j];
  }
}

文字列→数列
string S;int A=atoi(S.c_str());
数列→文字列
int A;string S=to_string(A);
数字判定　isdigit(a)
pair宣言　pair<int,int> p(5,7);
ソート　sort(vec.begin(),vec.end());
キュー　queue<int> q;
   q.push(7);　//７が入る
   cout << q.front() << endl;  // 先頭の値を出力
   q.pop();  // 先頭の値を削除
*/



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

ll X;
  cin>>X;
  ll i=0;ll a=0;
      while(1){a++;
        i+=a;
        
        if(i>=X){
          cout<<a<<endl;
          return 0;
        }
              }
  
          
          
      
  
  

}




Measured memory_bytes: 3556
#include <iostream>
#include <set>
#include <array>

int count = 0;
std::array<std::string, 3> str753 = {"3", "5", "7"};

std::set<std::string> create753Num(int numOfDigits)
{
    std::set<std::string> strNumSet;
    if(numOfDigits == 3) {
        strNumSet.insert("357");
        strNumSet.insert("375");
        strNumSet.insert("537");
        strNumSet.insert("573");
        strNumSet.insert("735");
        strNumSet.insert("753");

        count += strNumSet.size();

        return strNumSet;
    } else if (numOfDigits > 3) {
        std::set<std::string> bufSet = create753Num(numOfDigits - 1);
        for (const std::string& buf : bufSet) {
            for (std::size_t i = 0; i <= buf.size(); ++i) {
                for (const std::string& s : str753) {
                    std::string str = buf.substr(0, i) + s + buf.substr(i, buf.size());
                    strNumSet.insert(str);
                }
            }
        }

        count += strNumSet.size();
        return strNumSet;
    }
}

int main()
{
    int n;
    std::cin >> n;

    int numOfDigits = 1;
    int buf = n;
    while ((buf = buf / 10) != 0) {
        numOfDigits++;
    }

    std::set<std::string> strNumSet = create753Num(numOfDigits);
    for (const std::string& strNum : strNumSet) {
        int num = std::stoi(strNum);
        if (n < num) {
            count--;
        }
    }

    std::cout << count << std::endl;

    return 0;
}

Measured memory_bytes: 2560
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ll_s long
#define mod 1000000007
#define forn(i,start,lim) for(ll i=start;i<lim;i++)
#define forn_d(i,start,lim) for(ll i=start;i>=lim;i--)
#define f first
#define s second
#define pb push_back
#define pf push_front
#define mp make_pair
#define debug1(a) cout<<a<<endl
#define debug2(a,b) cout<<a<<" "<<b<<endl
#define debug3(a,b,c) cout<<a<<" "<<b<<" "<<c<<endl
#define debug4(a) cout<<"chu "<<a<<endl
#define sz(a) (ll)(a.size())
#define endl "\n"

ll memo[405][405];
ll sum[405];

ll fn(ll i,ll j){
  if(i==j) return 0;
  if(memo[i][j]!=-1)
    return memo[i][j];
  ll ans=1e18;
  for(ll k=i;k<j;k++){
    ll cost=sum[j]-sum[i-1];
    ans=min(ans,fn(i,k)+fn(k+1,j)+cost);
  }
  memo[i][j]=ans;
  return ans;
}

int main()
{
  ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  ll n,x;
  cin>>n;
  memset(memo,-1,sizeof(memo));
  forn(i,1,n+1){
    cin>>x;
    sum[i]=sum[i-1]+x;
  }
  ll ans=fn(1,n);
  cout<<ans<<endl;
  return 0;
}


Measured memory_bytes: 1536
#include<iostream>
#include<cmath>
#include<vector>
using namespace std;
int main()
{
    int N,D,x;
    cin >> N>>D;
    int arr[N][D];
    vector<double>vc;
    for (int i=0;i<N ;i++ )
    {
        for (int j=0 ;j<D ;j++ )
            {
                cin >>x;
                arr[i][j] = x;
            }
    }
    double sum=0;
    for (int i=0 ;i<N-1 ;i++ )
    {
        for (int j=i+1;j<N ;j++ )
        {
            sum=0;
            for (int k=0;k<D ;k++ )
            {
                sum=sum+(arr[i][k]-arr[j][k])*(arr[i][k]-arr[j][k]);
            }
            vc.push_back(sqrt(sum));
        }
    }
    int c=0;
    for (int i=0;i<vc.size() ;i++ )
    {
        if(vc[i]==int(vc[i]))
            c++;
    }
    cout << c <<endl;
    return 0;
}


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

using namespace std;

int main()
{
    char a[100]={0};
    int i;
    a[0]=' ';
    scanf("%[^\n]s",a+1);
    for(i=0;i<strlen(a);i++)
    {
        if(a[i]==' ') printf("%c",a[i+1]+'A'-'a');
    }
    return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
A = list(map(int, input().split()))

MOD = 10 ** 9 + 7
in_A, out_A = 0, 0

for i in range(N):
  for j in range(i + 1, N):
    if A[i] > A[j]:
      in_A += 1
  for j in range(N):
    if A[i] > A[j]:
      out_A += 1

print((in_A * K + out_A * K * (K - 1) // 2) % MOD)



Measured memory_bytes: 41964
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<numeric>
#include<utility>

using namespace std;

typedef long long int ll;
const int INF = 1<<30;
const long long LINF = 1LL<<60;

int z_algorithm(string s){
    vector<int> a(s.size());
    a[0] = s.size();
    int i = 1, j = 0;
    while(i < s.size()){
        while(i + j < s.size() && s[j] == s[i + j]){
            j++;
        }
        a[i] = j;
        if(j == 0){
            i++;
            continue;
        }
        int k = 1;
        while(i + k < s.size() && k + a[k] < j){
            a[i + k] = a[k];
            k++;
        }
        i += k;
        j -= k;
    }
    int res = 0;
    for(int i = 0; i < s.size(); i++){
        res = max(res, min(i, a[i]));
    }
    return res;
}

int main(){
    int n, ans = 0;
    string s;
    cin >> n >> s;
    for(int i = 0; i < n - 1; i++){
        string s2 = s.substr(i);
        ans = max(ans, z_algorithm(s2));
    }
    cout << ans << endl;
    return 0;
}


Measured memory_bytes: 256
#[allow(unused_macros)]
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

    ($next:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };

    ($next:expr, mut $var:ident : $t:tt $($r:tt)*) => {
        let mut $var = read_value!($next, $t);
        input_inner!{$next $($r)*}
    };
}

#[allow(unused_macros)]
macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

    ($next:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
    };

    ($next:expr, chars) => {
        read_value!($next, String).chars().collect::<Vec<char>>()
    };

    ($next:expr, usize1) => {
        read_value!($next, usize) - 1
    };

    ($next:expr, $t:ty) => {
        $next().parse::<$t>().expect("Parse error")
    };
}

#[allow(unused_macros)]
macro_rules! debug {
    ($($a:expr),*) => {
        #[cfg(debug_assertions)]
        writeln!(&mut std::io::stderr(), concat!("[DEBUG] ", $(stringify!($a), "={:?} "),*), $($a),*);
    }
}

#[allow(unused_imports)]
use std::cmp::{min, max};
#[allow(unused_imports)]
use std::io::{stdout, stdin, BufWriter, Write};

fn main() {
    let out = std::io::stdout();
    let mut out = BufWriter::new(out.lock());
    macro_rules! puts {
        ($($format:tt)*) => (write!(out,$($format)*).unwrap());
    }

    input!{
      n: usize,
      s: String,
    }

    let is_ok = |len| {
        for i in 0..n-len+1 {
            if s[i+len..].find( &s[i..i+len] ).is_some() {
                return true
            }
        }
        false
    };

    let mut ng = n as i64;
    let mut ok = 0;
    while (ok-ng).abs() > 1 {
        let mid = (ok + ng) / 2;
        if is_ok(mid as usize) {
            ok = mid;
        } else {
            ng = mid;
        }
    }
    puts!("{}\n", ok);
}


Measured memory_bytes: 4352
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<typename Q_temp>
using smaller_queue = priority_queue <Q_temp, vector<Q_temp>, greater<Q_temp> >;

const int INF = (int) 1e9;
const ll LINF = (ll) 4e18;
const ll MOD = (ll) (1e9 + 7);
const double PI = acos(-1.0);

#define REP(i,m,n) for(ll i = m; i < (ll)(n); ++i)
#define rep(i,n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x_) cerr << #x_ << ":" << x_ << endl;
#define dbg2(x_) for(auto a_ : x_) cerr << a_ << " "; cerr << endl;
#define dbg3(x_ , sx_) rep(i, sx_) cerr << x_[i] << " "; cerr << endl;
vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

inline ll CEIL(ll a, ll b) {
    return (a + b - 1) / b;
}

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

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int n, a, b, c, d;
    string s;
    cin >> n >> a >> b >> c >> d;
    cin >> s;
    a--, b--, c--, d--;

    bool can = true;

    REP(i, a, c) {
        if (s[i] == '#' && s[i + 1] == '#') can = false;
    }

    REP(i, b, d) {
        if (s[i] == '#' && s[i + 1] == '#') can = false;
    }

    if (c > d) {
        bool space = false;
        for (int i = b - 1; i <= min(d - 1, n - 3); ++i) {
            if (s[i] == '.' && s[i + 1] == '.' && s[i + 2] == '.') space = true;
        }
        if (!space) can = false;
    }
    Yes(can);
    return 0;
}


Measured memory_bytes: 592
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull B = 1000000007ULL;

int main(){
  int N; // N is the size of string s
  string s,P;
  cin >> s >> P;
  N=s.size();
  vector<ull> p(N+1); // p is power (base B)
  vector<ull> hash(N+1); // hash values
  p[0] = 1; hash[0] = 0;
  for (int i = 0; i < N; i++) {
    hash[i+1] = hash[i]*B + s[i];
    p[i+1] = p[i]*B;
  }
  /*
    s?????¨????????????s[L,R]??????????????\????????\?????????????????????.
    hash[L,R] := hash[R+1]-hash[L]*p[R-L+1];
  */
  ull base=0,ans=0;
  for(int i=0;i<P.size();i++){
    base=base*B+P[i];
  }
  for(int i=0;i+P.size()<=N;i++){
    int L=i,R=i+P.size()-1;
    if(hash[R+1]-hash[L]*p[R-L+1]==base) cout<<i<<endl;
  }
  return 0;
}

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

#define int long long
#define vvi vector<vector<int>>
#define vec vector
#define pq priority_queue
#define all(v) (v).begin(), (v).end()
#define uniqueV(x) sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end());
#define rep(i, n) for (int (i) = (0); (i) < (n); ++(i))
#define repp(i, m, n) for (int (i) = (m); (i) < (n); ++(i))
#define dbg(x) cerr << #x << ": " << x << endl;
#define dbg2(x, y) cerr<<"("<<#x<<", "<<#y<<") = "<<"("<<x<<", "<<y<<")"<<endl;
#define dbg3(x, y, z) cerr<<"("<<#x<<", "<<#y<<", "<<#z<<") = "<<"("<<x<<", "<<y<<", "<<z<<")"<<endl;
#define dbgB(value, size) cerr<<#value<<": "<<bitset<size>(value) << endl;
#define line() cerr << "---------------" << endl;

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

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

template<typename T>
void print1(T begin, T end) {
  while (begin != end) {
    cout << (*begin) << " ";
    *begin++;
  }
  cout << endl;
}

template<typename T>
void print2(T Array, int height, int width) {
  for (int i = 0; i < height; i++) {
    for (int j = 0; j < width; j++) {
      cout << " " << Array[i][j];
    }
    cout << endl;
  }
}

void print() { std::cerr << endl; }
template <class Head, class... Tail>
void print(Head&& head, Tail&&... tail) {
  std::cerr << head << " ";
  print(std::forward<Tail>(tail)...);
}

template<class T>
void Add(T &a, const T &b, const T &mod=1000000007) {
  int val = ((a % mod) + (b % mod)) % mod;
  if (val < 0) { val += mod; }
  a = val;
}

template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }

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

signed main() {
  int n;
  cin >> n;
  vec<int> v;
  rep (i, n) {
    int x;
    cin >> x;
    v.push_back(x);
  }

  int Min = v[0];
  int ans = 0;
  rep (i, n) {
    if (v[i] >= Min) ans++;
    chmax(Min, v[i]);
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <stdio.h>

int n, m, connect[12][12] = {0}, p[12];

int main(){
  scanf("%d %d", &n, &m);
  for(int i=1; i<=m; i++){
    int k;  scanf("%d", &k);
    while(k--){
      int s;  scanf("%d", &s);
      connect[i][s] = 1;
    }
  }
  for(int i=1; i<=m; i++)  scanf("%d", p+i);

  int ans = 0;

  for(int bit=0; bit<(1<<n); bit++){
    int on[12] = {0};
    for(int i=1; i<=n; i++)
      if(bit & (1<<(i-1)))
	on[i] = 1;

    int light = 0;
    for(int i=1; i<=m; i++){
      int swi = 0;
      for(int j=1; j<=n; j++)
	if(connect[i][j] && on[j])
	  swi++;
      if(swi%2 == p[i])  light++;
    }
    if(light == m)  ans++;
  }
  printf("%d\n", ans);

  return 0;
}


Measured memory_bytes: 128
import java.io.IOException;
import java.math.BigDecimal;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) throws IOException {

		Scanner scan = new Scanner(System.in);

		int a = scan.nextInt();
		int b = scan.nextInt();
		int c = scan.nextInt();

		if (c >= a && c <= b) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}

	}

	//***********************以下共通関数************************************************
	/**
	 * 文字列を反転して返す
	 * @param pStr 文字列
	 * @return 反転した文字列
	 */
	public static String myReverse(String pStr) {
		if (pStr.length() < 1) {
			return "";
		}

		StringBuffer sb = new StringBuffer(pStr);
		return sb.reverse().toString();
	}

	/**
	 * 余りを求める。
	 * @param a
	 * @param b
	 * @return 余り。余りがマイナスの時はプラスで返す。
	 */
	public static long myMod(long a, long b) {
		long ret = 0;

		ret = a % b;

		if (ret < 0) {
			ret += b;
		}

		return ret;
	}

	/**
	 * 乗数を求める ※mod対応
	 * @param kisu 基数
	 * @param josu 乗数
	 * @param primeNumMod_0 法 mod値 使わない場合は「0」
	 * @return
	 */
	public static long myPowWithMod(long kisu, long josu, long primeNumMod_0) {

		long ans = 1;

		//乗数が0の場合→1
		if (josu == 0)
			return 1;

		if (primeNumMod_0 == 0) {
			//modを使わないとき

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= kisu;
					josu = josu / 2;
				} else {
					//累乗が奇数の時
					ans *= kisu;
					josu--;
				}
			}

			return ans;

		} else {
			//modを使うとき

			//初めに桁を落とす
			kisu = myMod(kisu, primeNumMod_0);

			while (josu > 0) {

				if (josu % 2 == 0) {
					//累乗が偶数の時

					kisu *= myMod(kisu, primeNumMod_0);
					josu = josu / 2;

				} else {
					//累乗が奇数の時
					ans *= myMod(kisu, primeNumMod_0);
					josu--;

				}
			}

			return myMod(ans, primeNumMod_0);

		}

	}

}


Measured memory_bytes: 26940
import java.util.Scanner;

public class Main {
    static int n;
    static int[] A;

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        n = s.nextInt();
        A = new int [n];
        for (int i = 0; i < n; i++) {
            A[i] = s.nextInt();
        }
        int cmp = mergeSort(A, 0, n);

        for (int i = 0; i < n; i++) {
            if (i != 0) {
                System.out.print(" ");
            }
            System.out.print(A[i]);
        }
        System.out.println();
        System.out.println(cmp);
    }

    static int merge(int[] B, int left, int middle, int right) {
        int [] L, R;
        L = new int [middle - left + 1];
        R = new int [right - middle + 1];

        for (int k = 0; k < middle - left; k++) {
            L[k] = A[left + k];
        }

        for (int k = 0; k < right - middle; k++) {
            R[k] = A[middle + k];
        }

        L[middle - left] = Integer.MAX_VALUE;
        R[right - middle]  = Integer.MAX_VALUE;

        int i = 0, j = 0, k = 0;
        while (i < middle - left || j < right - middle) {
            if (L[i] < R[j]) {
                A[left + k] = L[i];
                i++;
            } else {
                A[left + k] = R[j];
                j++;
            }
            k++;
        }
        return k;
    }

    static int mergeSort(int []B, int left, int right) {
        if (left + 1 == right) {
            return 0;
        }
        int middle = (left + right) / 2;

        int s = mergeSort(B, left, middle);
        int t = mergeSort(B, middle, right);
        int cmp = merge(B, left, middle, right);
        return cmp + s + t;
    }
}



Measured memory_bytes: 174024
def get_candy(num):
    global candies, step
    candies += num
    step += 1

n = int(input())
a = list([0] * n for i in range(2))
a[0] = list(map(int, input().split()))
a[1] = list(map(int, input().split()))

ans = 0

for timing in range(n):
    step = 0
    i, j = 0, 0
    candies = a[0][0]
    while step < n:
        if step < timing:
            j += 1
            get_candy(a[i][j])
        elif step == timing:
            i += 1
            get_candy(a[i][j])
        else:
            j += 1
            get_candy(a[i][j])
    if ans < candies:
        ans = candies

print(ans)


Measured memory_bytes: 3064
#include<bits/stdc++.h>
using namespace std;
#define ll  long long
#define fio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define endl '\n'
#define mod 1000000007
int main() {
    fio;
    ll x, k, d;
    ll ans = 0;
    cin >> x >> k >> d;
    if (x <= 0)
    {
        ll n = (-1 * x) / d;
        ll temp = k - n;

        if (temp <= 0)
        {
            cout << abs(x + k * d) << endl;
            return 0;
        }
        x = x + n * d;
        k = k - n;
    }
    if (x < d)
    {
        x = x + d;
        k--;
    }
    ll steps = x / d;
    ll rem = k - steps;
    if (rem > 0 and rem % 2 == 0) {
        ans = abs(x % d);
    }
    else if (rem > 0 and rem % 2 != 0) {
        ans = abs((x % d) - d);
    }
    else if (rem <= 0) {
        ans = abs(x - k * d);
    }
    cout << ans;
    return 0;
}

Measured memory_bytes: 3640
def how_many_ways(n, x)
  ary = [*1..n].combination(3).to_a
  cnt = 0
  ary.each do |i|
    cnt += 1 if i.inject(&:+) == x
  end
  return cnt
end

loop do
  n, x = gets.chomp.split(" ").map(&:to_i)
  break if [n, x] == [0, 0]
  puts how_many_ways(n, x)
end

Measured memory_bytes: 43204
a, b = map(int, input().split())

if (b-a+1) % 2 == 0:
    if a % 2 == 0:
        print((b-a+1) // 2 % 2)
    else:
        print(((b - a + 1 - 2) // 2 % 2) ^ a ^ b)
else:
    if a % 2 == 0:
        print(((b - a + 1 - 1) // 2 % 2) ^ b)
    else:
        print(((b - a + 1 - 1) // 2 % 2) ^ a)


Measured memory_bytes: 3060
#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (int) n; i++)
using ll = long long;
template <class T>
using vt = vector<T>;
using vvi = vector<vector<int>>;

int main() {
  int x,a;
  cin >> x >> a;

  cout << (x < a ? 0 : 10); 
  return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll>pi;
const int MAXN=10;
const int MOD=1000000007;
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define DEC(i,a,b) for(int i=(a);i>=(b);i--)
#define fst first
#define snd second
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define db(x) cerr<<#x<<" = "<<x<<"\n"
#define LOW(v,x) (lower_bound(all(v),(x))-(v).begin())


int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	int n,k;string s;cin>>n>>k>>s;
	s[k-1]+='a'-'A';
	cout<<s<<"\n";
}
/*
1 3
#.#


2 3
#.#
..#

3 3
##.
#.#
..#

3
2 5
6 1
3 7
Ans:6

4
3 7
2 9
8 16
10 8
Ans:9
*/


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

using namespace std;

using ll = long long;

#define FOR(i, a, b) for(int i=(a);i<(b);++i)
#define REP(i, n) for(int i=0;i<(n);++i)
#define ALL(v) (v).begin(),(v).end()
#define SP cout<<fixed<<setprecision(10)

typedef pair<int, int> P;

const int INF = (int) 1e9;
const int MOD = (int) 1e9 + 7;

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

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

int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

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

int dp[11][2000000];

int floor(int j, int i) {
	if (j % i == 0) return j / i;
	else return j / i + 1;
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	
	int d;
	ll g;
	cin >> d >> g;
	g /= 100;
	int p[d + 1], c[d + 1];
	FOR(i, 1, d + 1) {
		cin >> p[i] >> c[i];
		c[i] /= 100;
	}
	
	REP(i,11) REP(j,2000000) dp[i][j]=INF;
	
//	int dp[11][100000];
	
	// i=1
//	REP(j, p[1] + 1) {
//		dp[1][j] = j;
//	}
//	FOR(j, p[1] + 1, p[1] + c[1] + 1) {
//		dp[1][j] = dp[1][p[1]];
//	}
	
	FOR(i, 1, d + 1) {
		REP(j, 200000) {
			if (j <= i * p[i]) {
				dp[i][j] = floor(j, i);
			} else if (j <= i * p[i] + c[i]) {
				dp[i][j] = dp[i][i * p[i]];
			} else {
				int minValue = INF;
				FOR(k, 1, i) {
					minValue = min(minValue, dp[k][j - (i * p[i] + c[i])]);
				}
				dp[i][j] = dp[i][i*p[i]] + minValue;
			}
		}
//		REP(j, i * p[i] + 1) {
//			if (dp[i][j - 1] != 0) {
//				dp[i][j] = min(floor(j, i), dp[i][j - i]);
//			} else {
//				dp[i][j] = floor(j, i);
//			}
//		}
//		FOR(j, i * p[i] + 1, i * p[i] + c[i] + 1) {
//			dp[i][j] = dp[i][i * p[i]];
//		}
	}
	
	int minValue = INF;
	FOR(i, 1, d + 1) {
//		cout << "g: " << g << "i: " << i << endl;
//		cout << dp[][] << endl;
		minValue = min(minValue, dp[i][g]);
	}
	
//	REP(i, d + 1) {
//		REP(j, 100000) {
//			cout << dp[i][j] << " ";
//		}
//		cout << endl;
//	}
	
	cout << minValue << endl;
	
	return 0;
}

Measured memory_bytes: 86144
function strDel(str, idx){
  var res = str.slice(0, idx) + str.slice(idx + 1);
  return res;
};

function Main(input) {
  input = input.split('\n');
  var s = parseInt(input[0], 10);
  var n = input[1];
  var ii = 0;
  for (var i = 0; i <= s - 1; i++) {
    if (n.charAt(ii) === n.charAt(ii + 1)) {
      n = strDel(n, ii);
    } else {
      ii++;
    }
  }
  console.log(n.length);
}

Main(require('fs').readFileSync('/dev/stdin', 'utf8'));

Measured memory_bytes: 38968
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define ll long long
#define pll pair<ll, ll>
#define pii pair<int,int>
#define pb push_back
#define F first
#define S second
#define mod 1000000007
#define maxn 100005
#define boost ios::sync_with_stdio(false);cin.tie(0)
#define fr freopen("source.txt","r",stdin),freopen("output.txt","w",stdout)
#define SET(a,b) memset(a,b,sizeof(a))

int a[maxn];

int main(){
	boost;
	
	int n,c,k;
	cin>>n>>c>>k;

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

	sort(a+1,a+1+n);

	int cnt=0;
	int j=1;
	rep(i,1,n){
		cnt++;
		while(i<=n&&a[i]-a[j]<=k && i-j+1<=c)i++;
		j=i;
		i--;
	}
	cout<<cnt;

	return 0;
}

Measured memory_bytes: 640
#include <bits/stdc++.h>
#define ll long long
#define MODV 1000000007
#define INF INT_MAX // 2147483647
#define INFLL LLONG_MAX // 9223372036854775807
#define rep(i, n) for(ll i=0, i##_len=(ll)(n); i<i##_len; i++)
#define repf(i, n) for(ll i=1, i##_len=(ll)(n+1); i<i##_len; i++)
#define per(i, n) for(ll i=((ll)(n))-1; i>=0; i--)
#define perf(i, n) for(ll i=((ll)(n)); i>0; i--)
#define all(v) v.begin(), v.end()
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vector<ll>>
#define Yes() cout << "Yes" << endl
#define YES() cout << "YES" << endl
#define No() cout << "No" << endl
#define NO() cout << "NO" << endl
template<class T>bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(10);
    ll n, ansH; cin >> n;
    vi x(n), y(n), h(n);
    ll minX = INFLL, minY = INFLL, maxX = -1, maxY = -1;

    rep(i, n){
        cin >> x[i] >> y[i] >> h[i];
        chmin(minX, x[i]); // xの最小値
        chmin(minY, y[i]); // yの最小値
        chmax(maxX, x[i]); // xの最大値
        chmax(maxY, y[i]); // yの最大値
    }

    // 中心座標は([minX, maxX], [minY, maxY])に存在するため全探索
    for(ll posX=minX; posX<=maxX; posX++){
        for(ll posY=minY; posY<=maxY; posY++){
            // 初期化
            ansH = -1;
            // 入力された全ての点で矛盾が起きないか探索
            for(ll i=0; i<n; i++){
                // 高さ0のケースは後で確かめるため飛ばす
                if(h[i] == 0) continue;
                // 中心座標の高さ（候補）を求める
                if(ansH == -1) ansH = h[i] + abs(posX-x[i]) + abs(posY-y[i]);
                // 中心座標の高さ（候補）と矛盾がないか確かめる
                else if(ansH != h[i] + abs(posX-x[i]) + abs(posY-y[i])){
                    ansH = -INFLL;
                    break;
                }
            }
            // 矛盾があった場合は中心座標を変えて探索し直す
            if(ansH == -INFLL) continue;

            // 高さ0の入力点で矛盾がないか確認
            for(ll i=0; i<n; i++){
                // 高さが0以外なら前のループで確認済みなので飛ばす
                if(h[i] != 0) continue;
                ll distance = abs(posX-x[i]) + abs(posY-y[i]);
                if(ansH > distance){
                    ansH = -INFLL;
                    break;
                }
            }
            // 矛盾があった場合は中心座標を変えて探索し直す
            if(ansH == -INFLL) continue;

            // 答えの出力
            cout << posX << " " << posY << " " << ansH << endl;
        }
    }
}

Measured memory_bytes: 256
n=gets.chomp.to_i
array=gets.split.map(&:to_i)
counts = 0
array.select!{|e| e % 2 == 0}
n=array.count
k=0
while array.any?{ |e| e.even? } do
  while k < n do
    while array[k].even? do
      array[k] = array[k] / 2
      counts += 1
    end
    k += 1
  end
end
puts counts


Measured memory_bytes: 2300
#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

  vector<int> b(N+1, 0);
  vector<int> w(N+1, 0);

  int tb = 0, tw = 0;
  for( int i=0;i<N;i++ )
    {
      b[i] = tb;
      w[i] = tw;      
      if(S[i] == '.')
	tw++;
      else
	tb++;
    }
  b[N] = tb;
  w[N] = tw;

  int ans = N;
  for( int i=0;i<N+1;i++ )
    ans = min(ans, w[N]-w[i]+b[i]);
  
  cout << ans << endl;
  return 0;
}


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

unsigned int colors(char c) {
  switch (c) {
    case 'R': return 0x4;
    case 'G': return 0x2;
    case 'B': return 0x1;
  }
  return 0x0;
}

int main()
{
  int N;
  string S;
  cin >> N >> S;
  int rgb[3] = {0};
  for (int i = 0; i < N; i++) {
    switch (S[i]) {
      case 'R': rgb[0]++; break;
      case 'G': rgb[1]++; break;
      case 'B': rgb[2]++; break;
    }
  }
  long long ans = (long long)rgb[0]*rgb[1]*rgb[2];
  for (int space = 1; space < N; space++) {
    for (int i = 0; (i+space*2) < N; i++) {
      int j = i + space;
      int k = j + space;
      if ((colors(S[i])|colors(S[j])|colors(S[k]))==0x7) {
        ans--;
      }
    }
  }
  cout << ans << endl;
  return 0;
}


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

using namespace std;

int main(){
    int N,M,count=0,ans=0;
    cin >> N >> M;
    vector<vector<int>> swt(N);
    vector<int> p(M);
    vector<int> sum(M,0);
    for(int i=0;i<M;i++){
        int k,s;
        cin >> k;
        for(int j=0;j<k;j++){
            cin >> s;
            swt[s-1].push_back(i);
        }
    }

    for(int i=0;i<M;i++){
        cin >> p[i];
    }

    while(count != pow(2,N)){
        int dmy = count;
        for(int i=0;i<N;i++){
            if(dmy&1){
                for(int j=0;j<swt[i].size();j++){
                    sum[swt[i][j]]++;
                }
            }
            dmy >>= 1;
        }
        
        for(int i=0;i<M;i++){
            if(sum[i]%2!=p[i]){
                ans--;
                break;
            }
        }
        ans++;
        count++;
        sum.clear();
        sum.resize(M);
    }

    cout << ans << endl;
}

Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Main main = new Main();
        main.solve();
    }
    public void solve() {
        Scanner scan = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        int N = scan.nextInt();
        long e_t = scan.nextLong();
        long e_a = scan.nextLong();
        for (int i = 2; i <= N; i++) {
            long t = scan.nextLong();
            long a = scan.nextLong();
            long j = Math.max(ceil(e_t, t), ceil(e_a, a));
            e_t = t * j;
            e_a = a * j;
        }
        System.out.println(e_t + e_a);
    }
    public long ceil(long x, long y) {
        if (x % y == 0) {
            return x / y;
        } else {
            return x / y + 1;
        }
    }
}


Measured memory_bytes: 25044
#include <bits/stdc++.h>
using namespace std;
int main() {
  int N, A;
  bool a = false;
  cin >> N;
  for( int i = 0; i < N; i++){
    cin >> A;
    if( (A % 2) == 0 ){
      if((A % 3) != 0 && (A % 5) != 0){
      	cout << "DENIED" << endl;
        a = true;
        break;
      }
    }
  }
  if(!a){ cout << "APPROVED" << endl;}
  
}


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

using namespace std;

const int mod = 1e9 + 7;

int main()
{
  int N, K, A[100];

  cin >> N >> K;
  for(int i = 0; i < N; i++) {
    cin >> A[i];
  }

  vector< vector< int > > dp(N + 1, vector< int >(256));
  dp[0][0] = 1;
  for(int i = 0; i < N; i++) {
    auto dp2(dp);
    for(int j = 0; j <= i; j++) {
      for(int k = 0; k < 256; k++) {
        (dp2[j + 1][k ^ A[i]] += 1LL * dp[j][k] * (j + 1) % mod) %= mod;
      }
    }
    dp.swap(dp2);
  }
  int ret = 0;
  for(int i = 1; i <= N; i++) (ret += dp[i][K]) %= mod;
  cout << ret << endl;
}

Measured memory_bytes: 512
N, A, B = map(int, input().split())
dis = B - A
if dis % 2 == 0:
    print(dis // 2)
else:
    A_end = A - 1
    B_end = N - B
    if A_end <= B_end:
        ans = A_end
        A = 1
        B -= A_end
        ans += 1
        print(ans + (B - A) // 2)
    else:
        ans = B_end
        B = N
        A += B_end
        ans += 1
        print(ans + (B - A) // 2)


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

using namespace std;

int ok (int n) {
    int res = 0;
    while (n) {
        res += n % 10;
        n /= 10;
    }
    return res;
}

int main() {
    int n, a, b;
    scanf("%d %d %d", &n, &a, &b);
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        int x = ok(i);
        if (x >= a && x <= b)
                ans += i;
    }
    printf("%d\n", ans);
    return 0;
}


Measured memory_bytes: 256
N = int(input())
X = list(map(int, input().split()))

p_min = min(X)
p_max = max(X)

ans = p_min
cost_min = N * p_max ** 2
for p in range(p_min, p_max + 1):
  tmp_cost = sum(map(lambda x: (x - p) ** 2, X))
  if tmp_cost < cost_min:
    ans = p
    cost_min = tmp_cost
    
print(cost_min)

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

#define rp(i, k, n) for (int i = k; i < n; i++)
typedef long long ll;

ll mod = 1e9 + 7;



int main() {
    double t, x;
    scanf("%lf%lf", &t, &x);
    double ans = t/x;
    printf("%lf", ans);
    return 0;
} 

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

int main() {
  int n, d, x;
  cin >> n >> d >> x;
  vector<int> a(n);
  for(int i=0;i<n;i++) {
    cin >> a[i];
  }

  vector<int> choko(n);

  for(int i=0;i<n;i++) {
    int total = 0;
    int times = 0;
    while(times * a[i] + 1 <= d) {
      total++;
      times++;
    }
    choko[i] = total;
  }

  int ans = 0;

  for(int i=0;i<n;i++) {
    ans += choko[i];
  }

  cout << ans + x << endl;
}

Measured memory_bytes: 256
// atcoder/edpc/Y/main.cpp
// author: @___Johniel
// github: https://github.com/johniel/

#include <bits/stdc++.h>

#define each(i, c) for (auto& i : c)
#define unless(cond) if (!(cond))

using namespace std;

typedef long long int lli;
typedef unsigned long long ull;
typedef complex<double> point;

template<typename P, typename Q> ostream& operator << (ostream& os, pair<P, Q> p) { os << "(" << p.first << "," << p.second << ")"; return os; }
template<typename P, typename Q> istream& operator >> (istream& is, pair<P, Q>& p) { is >> p.first >> p.second; return is; }
template<typename T> ostream& operator << (ostream& os, vector<T> v) { os << "("; each (i, v) os << i << ","; os << ")"; return os; }
template<typename T> istream& operator >> (istream& is, vector<T>& v) { each (i, v) is >> i; return is; }

template<typename T> inline T setmax(T& a, T b) { return a = std::max(a, b); }
template<typename T> inline T setmin(T& a, T b) { return a = std::min(a, b); }


constexpr lli mod = 1e9 + 7;
constexpr int N = 100000 * 2 + 5;
namespace math {
  lli  fact[N], finv[N], inv[N];

  void init()
  {
    fact[0] = fact[1] = 1;
    finv[0] = finv[1] = 1;
    inv[1] = 1;
    for (int i = 2; i < N; i++){
      fact[i] = fact[i - 1] * i % mod;
      inv[i] = mod - inv[mod % i] * (mod / i) % mod;
      finv[i] = finv[i - 1] * inv[i] % mod;
    }
  }

  lli mod_comb(int n, int k)
  {
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fact[n] * (finv[k] * finv[n - k] % mod) % mod;
  }
};

int main(int argc, char *argv[])
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  math::init();

  int h, w, n;
  while (cin >> h >> w >> n) {
    vector<pair<int, int>> v(n);
    cin >> v;
    v.push_back({1, 1});
    v.push_back({h, w});
    sort(v.begin(), v.end());

    constexpr int M = 3000 + 5;
    static lli dp[M][2];
    fill(&dp[0][0], &dp[M - 1][2 - 1] + 1, 0);
    dp[0][0] = 1;
    for (int i = 0; i < v.size(); ++i) {
      for (int j = i + 1; j < v.size(); ++j) {
        if (v[i].first <= v[j].first && v[i].second <= v[j].second) {
          int a = (v[j].first - v[i].first);
          int b = (v[j].second - v[i].second);
          lli x = math::mod_comb(a + b, b);
          (dp[j][0] += (dp[i][1] * x) % mod) %= mod;
          (dp[j][1] += (dp[i][0] * x) % mod) %= mod;
        }
      }
    }

    cout << (dp[v.size() - 1][1] - dp[v.size() - 1][0] + mod) % mod << endl;
  }

  return 0;
}


Measured memory_bytes: 4992
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define rep(i,b) FOR(i,0,b)
#define INF mugen
#define dump(x) cerr<<#x<<"="<<x<<endl


using ll = long long;
const ll mod = LLONG_MAX;

string s;
int b[26];
string alpha="abcdefghijklmnopqrstuvwxyz";

int main(){
  cin>>s;
  int n=s.size();
  for(int i=0;i<n;i++){
    for(int j=0;j<26;j++){
      if('a'+j == s[i]){
        b[j]++;
      }
    }
  }

  bool flag=false;
  rep(i,26){
    if(b[i]==0){
      cout<<alpha[i]<<endl;
      flag=true;
      return 0;
    }
  }
  if(!flag){
    cout<<"None"<<endl;
  }
}


Measured memory_bytes: 512
#include <iostream>

using namespace std;

int m,d;

int main(){
    cin >> m >> d;
    int count = 0;
    for(int i=1;i<=m;i++){
        for(int j=2;j<10;j++){
            for(int k=2;k<10;k++){
                if(j * 10 + k > d) break;
                if(j * k == i) count++;
            }
        }
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 256
import java.util.Scanner;
public class Main {
public static void main(String[]srgs) {
	Scanner scan=new Scanner(System.in);
	String a=scan.next();
	String b=scan.next();
	if(a.length()<b.length()) {
		System.out.println("LESS");
	}
	else if(a.length()>b.length()){
		System.out.println("GREATER");
	}
	else {
		for(int i=0;i!=a.length()+1;i++) {
			if(i==a.length()) {
				System.out.println("EQUAL");
			break;
			}
			char cha=a.charAt(i);
			char chb=b.charAt(i);
			int A=Character.getNumericValue(cha);
			int B=Character.getNumericValue(chb);
			if(A>B){
				System.out.println("GREATER");
				break;
			}
			else if(A<B){
				System.out.println("LESS");
			break;
			}
	}
	}
}
}

Measured memory_bytes: 23252
def fact(n)
  @memo ||= []
  @memo[n] ||= (n==0) ? 1 : (n * fact(n-1)) % MOD;
end

def modpow(x,n)
  ret = 1
  while n > 0
    ret = (ret * x) % MOD if n&1 == 1
    x = (x*x) % MOD
    n >>= 1
  end
  return ret
end

def combin(n,k)
  return (((fact(n) * modpow(fact(n-k),MOD-2)) % MOD) * modpow(fact(k),MOD-2)) % MOD
end

MOD = 10**9 + 7
n,m,k = gets.split.map(&:to_i)

(n*m).times do |i|
  fact(i)
end

x = [n,m].max
csum = [0]*(x+1)
1.upto(x) do |i|
  csum[i] = (csum[i-1] + i) % MOD
end

sum = 0
n.times do |i|
  m.times do |j|
    sum += (csum[i] * m) % MOD
    sum += (csum[j] * n) % MOD
    sum %= MOD
  end
end

mul = combin(n*m-2,k-2)
p (sum*mul) % MOD


Measured memory_bytes: 5064
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
    
        List<Integer> h = new ArrayList<>();
        
        for (int i=0; i<N; i++) {
            h.add(sc.nextInt());
        }
        
        int count = 0;
        for (int j=0; j<N; j++) {
            if (h.get(j) >= K) {
                count++;
            }
        }
        
        System.out.println(count);
    }

}

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



int main(){
	int sum=0,M;
	string s;
	cin >> s;
	for(int i=0;i<s.size();i++){
		sum+=s[i]-'0';
	}
	M=sum;
	sum=0;
	
	bool ok;
	for(int i=s.size()-1;i>0;i--){
		s[i]='9';
		sum=0;
		ok=true;
		for(int j=i-1;j>=0;j--){
			if(s[j]!='0'){
				s[j]--;
				ok=false;
				break;
			}
			s[j]='9';
		}
		if(ok) goto aa;
		
		for(int j=s.size()-1;j>=0;j--){
			sum+=s[j]-'0';
		}
		M=max(sum,M);
	}
	
	aa:;
	cout << M << endl;
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
namespace io{
    const int l=1<<20;
    char buf[l],*s,*t,c;
    inline void gc(){
        if(s==t){
            t=(s=buf)+fread(buf,1,l,stdin);
            c=s==t?EOF:*s++;
        }else c=*s++;
    }
    template<class IT>inline void gi(IT &x){
        x=0;gc();while(c<'0'||c>'9')gc();
        while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}
    }
    char buf0[20];int a;
    template<class IT>inline void pi(IT x){
        if(x<0){putchar('-');x=-x;}
        do buf0[++a]=x%10+48;while(x/=10);
        while(a)putchar(buf0[a--]);
        putchar('\n');
    }
};
using io::gi;
using io::pi;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll > pil;
typedef pair<ll ,int> pli;
typedef pair<ll ,ll > pll;
typedef vector<int> vi;
typedef vector<ll > vl;
#define pque priority_queue
#define rep(i,l,r) for(i=(l);i<=(r);++i)
#define per(i,l,r) for(i=(l);i>=(r);--i)
#define REP(i,l,r) for(i=(l);i< (r);++i)
#define PER(i,l,r) for(i=(l);i> (r);--i)
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const ll p=1000000007ll;
const int p1=1000000006,N=1000005;
ll dp[N][3],inv[N],ifa[N];
inline ll add(ll a){return a<p?a:a-p;}
inline ll expo(ll a,int b=1000000005){
	ll c=1ll;
	while(b){
		if(b&1)c=c*a%p;
		b>>=1; a=a*a%p;
	}
	return c;
}
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    int n,i;ll fn=1ll,fc=1ll,s=0ll;
    scanf("%d",&n);
    REP(i,2,n)fn=fn*i%p;
	ifa[n]=expo(fn*n%p);
	fn=fn*expo(3ll,p1-n)%p;
	per(i,n,1)ifa[i-1]=ifa[i]*i%p;
	rep(i,1,n){
		inv[i]=fc*ifa[i]%p;
		fc=fc*i%p;
	}
	dp[0][1]=1ll;
	REP(i,0,n){
		dp[i+1][0]=add(dp[i][1]+dp[i][2]);
		dp[i+1][1]=add(dp[i][2]+dp[i][0]);
		dp[i+1][2]=add(dp[i][0]+dp[i][1]);
	}
	//printf("9fn=%lld\n",9ll*fn%p);
	//rep(i,1,n)printf("dp=%lld prob=fn/%lld\n",dp[i][0],expo(inv[i]*(ifa[i]*ifa[n-i]%p)%p));
	rep(i,1,n)s=(s+(dp[i][0]*inv[i]%p)*(ifa[i]*ifa[n-i]%p))%p;
	printf("%lld",fn*s%p);
    return 0;
}

Measured memory_bytes: 39296