akhauriyash/Code-Regression huggingface dataset:
//Copyright(c)2017 Mstdream
#include<bits/stdc++.h>
using namespace std;

inline void splay(int &v){
	v=0;char c=0;int p=1;
	while(c<'0' || c>'9'){if(c=='-')p=-1;c=getchar();}
	while(c>='0' && c<='9'){v=(v<<3)+(v<<1)+c-'0';c=getchar();}
	v*=p;
}
long long n,a,b,c,d,f;
int main(){
	//freopen("xxx.in","r",stdin);
	cin>>n>>a>>b>>c>>d;
	long long l=a,r=a;
	for(int i=2;i<n;i++){
		l+=c,r+=d;
		int hs=n-i;
		long long p=l-d*hs;
		long long q=r-c*hs;
		if(b<=q && b>=p)f=1; 
	}
	puts(f?"YES":"NO"); 
}

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

int main() {
  
  int N, A, x;
  cin >> N >> A;
  
  x = N % 500;
    
  if (x == 0){
    cout << "Yes" << endl;
  }
    else if (A > x) {
    cout << "Yes" << endl;
  }
    else if (A < x) {
     cout << "No" << endl; 
    }

}

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

ll solve() {
    ll N;
    cin >> N;
    vector<ll> A(N);
    for ( int i = 0; i < N; i++ ) {
        cin >> A[i];
        if ( A[i] == 0 ) return 0;
    }
    __int128_t p = 1;
    for ( int i = 0; i < N; i++ ) {
        p *= A[i];
        if ( p > (ll)1e18 ) return -1;
    }
    ll ans = p;
    return ans;
}

int main() {
    auto ans = solve();
    cout << ans << "\n";
    return 0;
}

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

def cmb(n, r, DIV):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % DIV

DIV=10**9+7
n=10**6
g1=[1, 1] # 元テーブル
g2=[1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, n + 1 ):
    g1.append( ( g1[-1] * i ) % DIV )
    inverse.append( ( -inverse[DIV % i] * (DIV//i) ) % DIV )
    g2.append( (g2[-1] * inverse[-1]) % DIV )

# MAXの合計
ans_max=0
for i in range(K-1,N):
  ans_max+=A[i]*cmb(i,K-1,DIV)

# MINの合計
ans_min=0
for i in range(0,N-(K-1)):
  ans_min+=A[i]*cmb(N-1-i,K-1,DIV)
  
print((ans_max-ans_min)%DIV)

Measured memory_bytes: 127420
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <list>

using namespace std;

typedef pair<long long int, long long int> P;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

double DP[200001], DP2[200001];

int main(){
	
	int N;
	cin >> N;
	
	for(int i = 0; i < N; i++){
		double num;
		cin >> num;
		
		for(int j = 0; j <= 200000; j++){
			DP2[j] = INF;
		}
		
		for(int j = 1; j <= 200000; j++){
			for(int k = j; k <= 200000; k += j){
				DP2[k] = min(DP2[k], max(DP[j], abs(num - j) / num));
			}
		}
		swap(DP, DP2);
	}
	
	double ans = INF;
	
	for(int i = 1; i <= 200000; i++){
		ans = min(ans, DP[i]);
	}
	
	printf("%.10f\n", ans);
	
	return 0;
}


Measured memory_bytes: 6420
A = []
card = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
r = False
for _ in range(3):
    a = list(map(int, input().split()))
    A.append(a)
n = int(input())
B = []
for _ in range(n):
    b = int(input())
    B.append(b)
for b in B:
    for k, a in enumerate(A):
        if b in a:
            card[k][a.index(b)] = 1
for i in range(3):
    if card[0][i] == card[1][i] == card[2][i] == 1:
        r = True
for i in range(3):
    if card[i][0] == card[i][1] == card[i][2] == 1:
        r = True
if (
    card[0][0] == card[1][1] == card[2][2] == 1
    or card[0][2] == card[1][1] == card[2][0] == 1
):
    r = True
print("Yes") if r else print("No")


Measured memory_bytes: 3064
import sys
import math
input = sys.stdin.readline


def main():
    MOD = 10 ** 9 + 7
    sc = Scan()
    n, m = sc.intarr()
    w = sc.intarr_ver(m)
    is_safe = [True] * (n)
    for i in w:
        is_safe[i-1] = False
    dp = [0] * (n+2)
    dp[1] = 1
    for i in range(2, n+2):
        if is_safe[i-2]:
            dp[i] = dp[i-1] + dp[i-2]
            dp[i] %= MOD
        else:
            dp[i] = 0
    print(dp[n+1])


class Scan():

    def intarr(self):
        line = input()
        array = line.split(' ')
        num_array = [int(n) for n in array]
        return num_array

    def intarr_ver(self, n):
        return [int(input()) for _ in range(n)]

    def strarr(self):
        line = input()
        array = line.split(' ')
        array[-1] = array[-1].strip('\n')
        return array


main()


Measured memory_bytes: 8616
square = []
while True:
    data = [int(e) for e in input().split()]
    if data[0]==0 and data[1]==0:
        break
    square.append(data)
    
for i in range(len(square)):
    for j in range(square[i][0]):
        for k in range(square[i][1]):
            print("#", end="")
        print()
    print()


Measured memory_bytes: 7012
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define rep(i, begin, n) for (int i = begin; i < n; i++)
#define repe(i, begin, n) for (int i = begin; i <= n; i++)
#define repr(i, begin, n) for (int i = begin; i > begin - n; i--)
#define repre(i, begin, end) for (int i = begin; i >= end; i--)

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

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

const int inf = 1000000007;
const int MOD = 1000000007;
const long long INF = 1000000000000000007;

// -------------------------------------------------------
int N, K;
int A[101010];

int main() {
  cin >> N >> K;
  rep(i, 0, N) { cin >> A[i]; }
  cout << 1 + ((N - K) + (K - 2)) / (K - 1) << endl;
}

Measured memory_bytes: 640
from heapq import heappush, heappop


def solve():
    N, H = map(int, input().split())
    cut_dmgs = []
    thr_dmgs = []
    for _ in range(N):
        a, b = list(map(int, input().split()))
        heappush(cut_dmgs, -a)
        heappush(thr_dmgs, -b)

    ans = 0
    max_cut_dmg = -min(cut_dmgs)
    while thr_dmgs:
        thr_dmg = -heappop(thr_dmgs) 
        if thr_dmg <= max_cut_dmg:
            break
        ans += 1
        H -= thr_dmg
        if H <= 0:
            return ans
    return ans + (H + max_cut_dmg - 1) // max_cut_dmg


print(solve())


Measured memory_bytes: 11168
#include <stdio.h>

int main(void){
  int a,b,c;
  int n,i;

  scanf("%d",&n);
  for(i=0;i<n;i++){
    scanf("%d%d%d",&a,&b,&c);
    a=a*a;
    b=b*b;
    c=c*c;
    if(a==b+c){printf("YES\n");continue;}
    else if(b==a+c){
      printf("YES\n");continue;
    }
    else if(c==a+b){
      printf("YES\n");continue;
    }
    printf("NO\n");
  }
  return 0;
}

Measured memory_bytes: 576
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(a) (a).begin(),(a).end()
#define overload4(_1, _2, _3, _4, name, ...) name
#define rep1(n) for(ll i = 0;i < (n);i++)
#define rep2(i,n) for(ll i = 0;i < (n);i++)
#define rep3(i,a,b) for(ll i = (a);i < (b);i++)
#define rep4(i,a,b,c) for(ll i = (a);i < (b);i += (c))
#define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__)
#define rrep1(n) for(ll i = (n)-1;i >= 0;i--)
#define rrep2(i,n) for(ll i = (n)-1;i >= 0;i--)
#define rrep3(i,a,b) for(ll i = (a)-1;i >= (b);i--)
#define rrep4(i,a,b,c) for(ll i = (a)-1;i >= (b);i -= (c))
#define rrep(...) overload4(__VA_ARGS__, rrep4, rrep3, rrep2, rrep1)(__VA_ARGS__)
const ll INF=1e18,MOD = 1e9+7;
const int iINF = 1e9;

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


    ll x,k,d,ans;
    cin>>x>>k>>d;
    x = abs(x);

    if(k  <= x / d){
        ans = x - (k * d);
    }
    else{
        ll lim = x / d;
        if((k - lim)%2 == 0){
            ans = abs(x - lim * d);
        }
        else{
            ans = abs(x - (lim + 1) * d);
        }
    }
    cout<<ans<<endl;

    return 0;
}


Measured memory_bytes: 3644
#include <stdio.h>

int a[100005];

int main(void)
{
	int n, k;
	int i, j;
	int max, num;
	
	while (1){
		scanf("%d %d", &n, &k);
		
		if (n == 0 && k == 0) break;
		
		for (i = 0; i < n; i++){
			scanf("%d", &a[i]);
		}
		
		num = 0;
		for (i = 0; i < k; i++){
			num += a[i];
		}
		
		max = num;
		
		for (i = 1; i < n - k; i++){
			num = num + a[i + k - 1] - a[i - 1];
			if (max < num)  max = num;
		}
		
		
		printf("%d\n", max);
	}
	return (0);
}
		

Measured memory_bytes: 988
#include <stdio.h>
#include <stdlib.h>

int BubbleSort(int *a, int n);

int main(void){
  int i, n, *a, ans;

  scanf("%d", &n);
  a = (int *)malloc(sizeof(int) * n);
  if(a == NULL){
    printf("?????¢????¢??????¨??????\n");
    return -1;
  }
  for(i = 0; i < n; i++){
    scanf("%d", &a[i]);
  }
  ans = BubbleSort(a, n);
  for(i = 0; i < n; i++){
    printf("%d", a[i]);
    if(i < n-1){
      printf(" ");
    }
  }
  printf("\n%d\n", ans);
  free(a);
  return 0;
}


int BubbleSort(int *a, int n){
  int flag, i, j, temp, count = 0;

  for(i = n; i > 0; i--){
    flag = 0;
    for(j = 1; j < i; j++){
      if(a[j-1] > a[j]){
	temp = a[j-1];
	a[j-1] = a[j];
	a[j] = temp;
	count++;
	flag = 1;
      }
    }
    if(flag == 0)  break;
  }
  return count;
}

Measured memory_bytes: 604
#include<bits/stdc++.h>
using namespace std;
#define boost ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define mp make_pair
#define pb push_back
#define fp first
#define sp second
typedef long long int ll;
typedef pair<ll,ll> pp;
#define check(x, i) ((x>>i)&1)
#define set(x,i) (x|(1<<i))
#define unset(x,i) (x&~(1<<i))
#define INF LONG_MAX
#define MAX_N 20
#define MAX 4000005
#define mod 1000000007
#define REP(i,n) for(i=0;i<n;i++)
#define FOR(i,a,b) for(i=a;i<=b;i++)
#define RFOR(i,a,b) for(i=a;i>=b;i--)
#define len(i,s) for(i=0;s[i];i++)
#define T() while(t--)
ll gcd (ll a, ll b){return (a?gcd(b%a,a):b);}
ll pow1(ll a,ll b,ll MOD){ll ans=1;while(b!=0){if(b&1)ans=(ans*a)%MOD;a=(a*a)%MOD;b=b/2;}return ans;}
ll modInverse(ll a,ll p){return pow1(a,p-2,p);}

int main()
{
	boost
	#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);    
    freopen("output.txt", "w", stdout);
#endif

ll n,k,i,j;
cin>>n>>k;
ll a[n+1];
for(i=1;i<=n;i++)
cin>>a[i];
set<ll>s;
vector<ll>v;
v.pb(a[1]);
s.insert(a[1]);
i=a[1];
//cout<<"s";
while(s.find(a[i])==s.end())
{
	//cout<<"a";
v.pb(a[i]);
s.insert(a[i]);
i=a[i];
}
//cout<<a[i]<<"\n";
ll l=v.size();
//for(j=0;j<l;j++)
//	cout<<v[j]<<" ";
//cout<<"\n";
ll r=0;
for(j=0;j<l;j++)
{
	if(v[j]==a[i])
	{
		r=j;
		break;
	}
}
ll m=l-r;
//cout<<m<<"\n";
if(k<=r)
	cout<<v[k-1];
else
{
	k=k-r;
    k=k%m;
    k--;
    if(k<0)
    	k=k+m;
    cout<<v[r+k];
}
}

Measured memory_bytes: 15412
#include <stdio.h>
#include <string.h>
int main (){
	int c;
	char str [100];
	scanf ("%d", &c);
	getchar();
	scanf ("%s", str);
	
	int len = strlen (str);
	if (len <= c) {
		printf ("%s\n", str);
	}else {
		for (int i = 0; i < c; i++){
			printf ("%c", str [i]);
		}
		puts ("...");
	}
	return 0;
}

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

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

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }

int main() {
    ios::sync_with_stdio(false);
    ll h, w;
    cin >> h >> w;

    if (h == 1 || w == 1) {
        cout << 1 << endl;
    } else if (h % 2 == 0 || w % 2 == 0) {
        cout << h * w / 2 << endl;
    } else {
        cout << h * w / 2 + 1 << endl;
    }

    return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin >> n;
  int temp;
  map<int,int> cnt;
  while(n--){
    cin >> temp;
    cnt[temp]++;
    if(cnt[temp] > 1){
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 9600
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define _GLIBCXX_DEBUG
#define all(v) v.begin(), v.end()

int main() {
    int64_t X;
    cin >> X;
    int64_t money = 100;
    int64_t count = 0;

    while (money < X) {
        money += money/100;
        count++;
    }
    cout << count << endl;
    return 0;
}

Measured memory_bytes: 3584
import java.util.*;
import java.lang.*;

public class Main{
	static long mod = 1000000007;
	public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        String inp = sc.nextLine();
        long[][] dp = new long[inp.length()+1][13];

        dp[0][0] = 1;
        int n = inp.length();
        for(int i=1;i<=n;i++){
            char c = inp.charAt(i-1);
            if(c == '?'){
                for(int k=0;k<10;k++){
                    for(int j=0;j<13;j++){
                        dp[i][(j*10 + k)%13] += dp[i-1][j];
                        dp[i][(j*10 + k)%13] %= mod;
                    }
                }
            }else{
                int val = Character.getNumericValue(c);
                for(int j=0;j<13;j++){
                    dp[i][(j*10 + val)%13] += dp[i-1][j];
                    dp[i][(j*10 + val)%13] %= mod;
                }
            }
        }

        System.out.println(dp[n][5]%mod);



        sc.close();
	}
}

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

int main() {
	int a, b;
	cin >> a >> b;
	if (a < b) {
		cout << "a < b" << endl;
	} else if (a > b){
		cout <<"a > b" <<  endl;
	}else {
		cout << "a == b" << endl;
	}
	return 0;
}


Measured memory_bytes: 3096
#include <bits/stdc++.h>
using namespace std;
int main(){
int N;
  cin>>N;
  bool nazo=false;
 for(int i=1;i<=9;i++){
 for(int j=1;j<=9;j++){
 	if(i*j==N){
	 nazo=true;
 		}
 	}
 }
  if(nazo){
  cout<<"Yes";
  }
  else{
  cout<<"No";
  }
}

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

#define X first
#define Y second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define rep(i, st, n) for (int i = (st); i < (n); ++i)
#define repinv(i, st, n) for (int i = ((n)-1); i >= (st); --i)
#define MEM(a, b) memset(a, b, sizeof(a));
#ifdef LOCAL
#define debug(x) std::cerr << #x << ": " << x << endl
#else
#define debug(x) 860111
#endif
#define fastIO() ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define fileIO(in, out) freopen(in, "r", stdin); freopen(out, "w", stdout)

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

//mt19937 mrand(random_device{}());
//mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const ll mod=1e9+7;
//int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
pii operator+(const pii&x, const pii&y) { return mp(x.X+y.X, x.Y+y.Y);}
pii operator-(const pii&x, const pii&y) { return mp(x.X-y.X, x.Y-y.Y);}
//INT_MAX, ULLONG_MAX, LLONG_MAX or numeric_limits<int>::min()

inline ll read(){
	char ch=getchar();ll x=0,f=0;
	while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
	while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
	return f?-x:x;
}

//------------------------------------------------------------------------//
int T;
const int maxn = 2e5+7;
int n, m, k;
//ll a[maxn];

//check T
void solve()
{
  cin >> m >> k;
  n = 1 << m;
  /*
  if(k == 0)
  {
    rep(i, 0, n) cout << i << " ";
    repinv(i, 0, n) cout << i << " \n"[i==0];
  }
  else if(k == n-1 && k != 1)
  {
    rep(i, 0, n-1) cout << i << " ";
    cout << k << " "; 
    repinv(i, 0, n-1) cout << i << " ";
    cout << k << endl;
  }
  else cout << "-1\n";
  */
 if(m ==1 )
 {
   if(k >= 1) cout << "-1\n";
   else cout << "0 0 1 1\n";
   return;
 }
 if(k >= n) cout << "-1\n";
 else{
   rep(i, 0, n) {if(i != k) cout << i << " "; }
    cout << k << " "; 
    repinv(i, 0, n) { if(i != k) cout << i << " "; }
    cout << k << endl;
 }
  return;
}


signed main()
{
  fastIO();
  T = 1;
  //cin >> T; //this
  rep(tc, 1, T+1)
  {
    //cout << "Case #" << tc << ": ";
    solve();
  }
  return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define pb push_back
#define ff first
#define ss second
#define sz(x) (int)x.size()
#define all(x) begin(x),end(x)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const char newl = 10;
const string sep = "\n_____\n";
const ll MOD = 1000000007; // 998244353
const int maxN = 300005;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void run(){
   int n;
   string s;
   cin >> n >> s;
   s = "#" + s;
   int cnt[3][4004];
   int alf[128];
   alf['R'] = 0;
   alf['G'] = 1;
   alf['B'] = 2;

   for (int i = 1; i <= n; i++){
      for (int a = 0; a < 3; a++) cnt[a][i] = cnt[a][i - 1];
      cnt[alf[s[i]]][i]++;
   }

   ll ans = 0ll;

   for (int i = 1; i <= n - 2; i++){
      for (int j = i + 1; j <= n - 1; j++){
         if (s[i] == s[j]) continue;
         int other = int('R') + int('G') + int('B') - int(s[i]) - int(s[j]);

         ans += cnt[alf[other]][n] - cnt[alf[other]][j];

         if (j - i + j <= n) if (s[j - i + j] == other) ans--;
      }
   }

   cout << ans;
}
int main(){
   ios_base::sync_with_stdio(0);cin.tie(0);
   cout.tie(0);
   // stress(); return 0;
   int t = 1;
   // cin >> t;
   for (int tc = 1; tc <= t; tc++) {
      // cout << "Case #" << tc << ": ";
      run();
      cout << newl;
   }
   return 0;
}

Measured memory_bytes: 3680
#include <stdio.h>

int main() {
	char s[1100];

	while(true) {
		scanf("%s",s);
		if(s[0] == '0')
			break;
		int sum = 0;

		for(int i = 0;s[i] != '\0';i++) {
			sum += s[i] - '0';
		}
		printf("%d\n",sum);
	}
    return 0;
}


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

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
const int p=31;
const int m=1e9+7;
typedef long long ll;
typedef int in;
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");} 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
#define int ll
in main (){
    int n;
    cin>>n;
    vector<pair<int,int>>v(2*n);
    for(int i=0,x=0;i<n;++i){
    	cin>>x;
    	v[i]={x,0};
    }

    for(int j=n,x=0;j<2*n;++j){
    	cin>>x;
    	v[j]={x,1};
    }
    sort(v.begin(),v.end());
    vector<int>ct(2);
    int ans=1;
    ct[v[0].second]++;
    for(int i=1;i<2*n;++i){
    	if(ct[1-v[i].second]==0){
    		ct[v[i].second]++;
    	}
    	else{
    		ans=(ans*ct[1-v[i].second])%m;
    		--ct[1-v[i].second];
    	}
    }
    cout<<ans;
}
    


Measured memory_bytes: 6424
#include <iostream>
#include <algorithm>
#include <cmath>
#include <iomanip>


using namespace std;

const int N = 200;
const int INF = 1e7;

int n, b[N], sum;

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


Measured memory_bytes: 256
(defun bit-collection (n function)
  (loop :for k :from 0 :upto (expt 2 n)
        :maximize(funcall function (loop :for j :from 0 :upto (1- n) :collect (logbitp j k)))))
(let* ((n (read))
       (lst (loop :repeat n :collect (loop :repeat (read) :collect (cons (read) (read))))))
  (defun f (ll)
    (if (loop :for k :from 0 :upto (1- n)
              :always (if (elt ll k)
                          (loop :for j :in (elt lst k)
                                :always (equal (elt ll (1- (car j))) (= 1 (cdr j))))
                          t))
        (count t ll) 0))
  (princ (bit-collection n #'f)))


Measured memory_bytes: 24804
S = input()

a = [-1] * (len(S) + 1)

# find zero positions
if S[0] == "<":
    a[0] = 0

if S[-1] == ">":
    a[-1] = 0

for i in range(len(S)):
    if S[i:i+2] == "><":
        a[i + 1] = 0

for i in range(len(S)):
    if S[i] == "<":
        a[i + 1] = a[i] + 1

for i in reversed(range(len(S))):
    if S[i] == ">" and a[i + 1] >= 0:
        a[i] = max(a[i], a[i + 1] + 1)

print(sum(a))






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

int main(){
    string a,b,c;
    cin >> a >> b >> c;
    char d='a';

    int i=0;
    while(i==0){
        if(d=='a'){
            if(a.size()>0){
                d=a.at(0);
                a.erase(0,1);
            }
            else{
                cout << 'A' << endl;
                i++;
            }
        }
        else if(d=='b'){
            if(b.size()>0){
                d=b.at(0);
                b.erase(0,1);
                }
            else{
                cout << 'B' << endl;
                i++;
            }
        }
        else if(d=='c'){
            if(c.size()>0){
                d=c.at(0);
                c.erase(0,1);
            }
            else{
                cout <<'C'<<endl;
                i++;
            }
        }
    }

    return 0;
}

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

class Main{

  private static int[] input;
  private static long[][][] data;

  public static void main(String[] args){
    Scanner scanner = new Scanner(System.in);
    int cardN = Integer.parseInt(scanner.next());
    int average = Integer.parseInt(scanner.next());
    input = new int[cardN];
    for(int i=0; i<cardN; i++){
      input[i] = Integer.parseInt(scanner.next());
    }
    scanner.close();

    data = new long[cardN][cardN+1][(cardN+1)*50];
    for(int i=0; i<cardN; i++){
      for(int j=0; j<cardN+1; j++){
        Arrays.fill(data[i][j], -1l);
      }
    }

    long ans = 0l;

    for(int i=1; i<cardN+1; i++){
      ans += merge(cardN, i, i*average);
    }

    System.out.println(ans);
  }

  private static long merge(int totalN, int groupN, int sum){
    if(totalN == 0){
      if(groupN==0 && sum==0){
        data[0][0][0] = 1l;
        return 1l;
      }else{
        data[0][groupN][sum] = 0l;
        return 0l;
      }
    }else if(totalN > 0){
      long ans = 0l;
      if(groupN>=0 && sum>=0){
        if(data[totalN-1][groupN][sum]==-1l){
          data[totalN-1][groupN][sum] = merge(totalN-1, groupN, sum);
        }
        ans += data[totalN-1][groupN][sum];
        if(groupN-1>=0 && sum-input[totalN-1]>=0){
          if(data[totalN-1][groupN-1][sum-input[totalN-1]]==-1){
            data[totalN-1][groupN-1][sum-input[totalN-1]] = merge(totalN-1, groupN-1, sum-input[totalN-1]);
          }
          ans += data[totalN-1][groupN-1][sum-input[totalN-1]];
        }
        return ans;
      }else{
        return 0l;
      }
    }else{
      return 0l;
    }
  }
}


Measured memory_bytes: 87592
// Author : Parth Prajapati
// Institute : Pandit Deendayal Petroleum University
#include<bits/stdc++.h>

using namespace std;

#define l long // -2^31 to +2^31-1 (upper limit ~ 2*(10^9))
#define ul unsigned long // 0 to +2^32-1
#define ll long long // -2^63 to +2^63-1 (upper limit ~ 9*(10^18))
#define ull unsigned long long // 0 to +2^64-1
#define mod(x, m) ((((x)%(m))+(m))%(m))
#define vi vector<int>
#define pi pair<int,int>
#define vl vector<ll int>
#define pl pair<ll int,ll int>
#define FASTIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

const ll MOD = 1e9 + 7;
const double pie = 3.141592653589793;

#define setcount(x) __builtin_popcount(x) // counts set bits
#define parity(x) __builtin_parity(x) // checks parity of the number
#define lzcount(x) __builtin_clz(x) // count leading zeros in binary representation of number
#define tzcount(x) __builtin_ctz(x) // count trailing zeros in binary representation of number

template<typename T> T inf() { return (T)__builtin_inf();} // syntax for use inf<datatype>();
template<typename T> T gcd(T a,T b){ if(b>a) return gcd(b,a);return b==0?a:gcd(b,a%b); }
template<typename T> T lcm(T a, T b) { return (a*b)/gcd(a,b); }
template<typename T> T fast_power(T x,T y,ll m=MOD){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%m;y>>=1LL;x=(x*x)%m;}return ans%m;}

string IntToString(ll a){ ostringstream temp; temp << a; return temp.str();}
ll findMMI_fermat(ll n,ll M) {ll ans= fast_power(n,M-2,M);return ans;}//i.e In (a/b)%M..it calculates MMI of b wrt M,only if M is prime
ll add(ll a,ll b,ll M) { return ( mod(a,M ) + mod(b,M ))%M; }
ll sub(ll a, ll b,ll M) { return (mod(a,M ) + M - mod(b,M ))%M; }
ll mult(ll a,ll b,ll M) { return  ( mod(a,M)*mod(b,M) ) %M ; }
bool isprime(ll a){ if(a==2) {return 1;}if(!(a&1) ) {return 0;}for(ll i=3;i*i<=a;i+=2){if(a%i==0) {return 0;} } return 1;} 

/************************** main program **************************/

int main()
{
	FASTIO
	//code
	ll int n,a,b,i;
	cin>>n;
	for(i=sqrt(n)+1;i>=1;i--)
	{
		if(n%i==0)
		{
			a = i;
			b = n/i;
			break;
		}
	}
	cout<<a+b-2;
    return 0;
}

Measured memory_bytes: 256
n, *a = map(int, open(0).read().split())
f = 0
t = 0
o = 0
for i in a:
    if i % 4 == 0:
        f += 1
    elif i % 2 == 0:
        t += 1
    else:
        o += 1
if f >= o - 1 and t == 0:
    print('Yes')
elif f >= o:
    print('Yes')
else:
    print('No')

Measured memory_bytes: 91608
#include <bits/stdc++.h>
using namespace std;
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0);
    string s;
    cin >> s;
    smatch mat;
    if (regex_search(s, mat, regex("^A[a-z]+C[a-z]+$"))) {
        cout << "AC\n";
    } else {
        cout << "WA\n";
    }
    return 0;
}


Measured memory_bytes: 256
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<iostream>
#include<queue>
#include<vector>
#include <bitset>
#include <cmath>
#include <limits>
#include <iostream>
#include<set>
#include<tuple>
using namespace std;
#define INF 11000000000
#define MAX 100000
#define MOD 1000000007
typedef long long ll;
typedef pair<ll,ll> P;
typedef pair<pair<int,int>,int> p;
typedef pair< pair<int,int>, int> p; 
#define bit(n,k) ((n>>k)&1) /*nのk bit目*/
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)


int main(){
    int N,A[210000];
    ll K;
    vector<int> B[210000];
    cin>>N>>K;
    for(int i=0;i<N;i++){
        cin>>A[i];
        B[A[i]].push_back(i);
    } 
    int count=1,now=0;
    while(true){
        auto it=upper_bound(B[A[now]].begin(),B[A[now]].end(),now);
        if(it==B[A [now] ].end()){
            now=(B[ A[now] ][0] +1)%N;
            count++;
        }else{
            now=((*it)+1)%N;
        }
        if(now==0) break;
    }
    K=(K-1)%count+1;
    count=1; now=0;
    if(K>=2){
        while(true){
            auto it=upper_bound(B[A[now]].begin(),B[A[now]].end(),now);
            if(it==B[A [now] ].end()){
                now=(B[ A[now] ][0]+1)%N;
                count++;
            }else{
                now=((*it)+1)%N;
            }
            if(count>=K) break;
        }
    }
    vector<int> ans;
    for(int i=now;i<N;){
        int a=A[i];
        auto it=upper_bound(B[a].begin(),B[a].end(),i);
        if(it==B[a].end()){
            ans.push_back(a);
            i++;
        }else{
            i=(*it)+1;
        }
    }
    for(int i=0;i<(int)ans.size();i++){
        if(i) cout<<" ";
        cout<<ans[i];
    }
    cout<<endl;

}



Measured memory_bytes: 14328
n,t = input().split()
N = int(n)
T = int(t)
t_list = []

t = list(input().split())
t_list = list(map(int,t))

sum_time = 0

for j in range(1,len(t_list)):
	if(t_list[j]-t_list[j-1] <= T):
		sum_time += t_list[j]-t_list[j-1]
	elif(t_list[j]-t_list[j-1] > T):
		sum_time += T

sum_time += T
print(sum_time)

Measured memory_bytes: 26860
//AtCoder ABC044 C - 高橋君とカード / Tak and Cards
#include <bits/stdc++.h>
using namespace std;
using ll=int64_t;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
ll dp[51][51][51*51]={}; //xiまでkまい選んで合計が何組?
int main() {
#if LOCAL&0
    std::ifstream in("./test/sample-1.in"); //input.txt
    std::cin.rdbuf(in.rdbuf());
#endif
    ll N,A; cin>>N>>A;
    vector<ll> xn(N+1,0);
    for(ll i=1;i<=N;++i){
        cin>>xn[i];
    }
    dp[0][0][0]=1;
    for(ll i=1;i<=N;++i){
        for(ll k=0;k<=i; ++k){
            for(ll s=0;s<=N*50;++s){
                dp[i][k][s] = dp[i-1][k][s];
                if (s>=xn[i]&&k>=1){
                    dp[i][k][s] += dp[i-1][k-1][s-xn[i]];
                }
            }
        }
    }
    ll ans=0;
    for(ll k=1;k<=N;++k){
        ans += dp[N][k][k*A];
    }
    cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 51072
#include "bits/stdc++.h"
 
using namespace std;

using ll = long long;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using vvvll = vector<vector<vector<ll>>>;
using vvvvll = vector<vector<vector<vector<ll>>>>;
using pl4 = pair<ll,ll>;
using str = string;
using vpl4 = vector<pair<ll,ll>>;

#define sz size()
#define be begin()
#define en end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

#define llin(x) ll (x);cin >>(x);
#define stin(x) str (x);cin >>(x);
#define vllin(x,n) vll (x)(n);FOR(i,0,n-1){cin >>(x)[i];}
#define vllin2(a,b,n) vll (a)(n);vll (b)(n);FOR(i,0,n-1){cin >>(a)[i]>>b[i];}
#define vpl4in(x,n) vpl4 (x)((n),mp(0,0));FOR(i,0,n-1){cin >>x[i].fi>>x[i].se;}
#define FOR(i,a,b) for(ll i = a ; i <= b ; i++)
#define rFOR(i,b,a) for(ll i = a; i >= b ; i--)
#define SORT(x) sort(x.be, x.en)
#define rSORT(x) sort(x.rbegin(), x.rend())
#define say(x) cout<<(x);
#define sal(x) cout<<(x)<<endl;
#define says(x) cout<<(x)<<(' ');
#define sas cout<<(' ');
#define sayR(x) cout<<fixed<<setprecision(10)<<(x);
#define salR(x) cout<<fixed<<setprecision(10)<<(x)<<endl;
#define yn(a) cout <<((a)?"yes":"no")<<endl;
#define Yn(a) cout <<((a)?"Yes":"No")<<endl;
#define YN(a) cout <<((a)?"YES":"NO")<<endl;
#define Imp(a) cout <<((a)?"Possible":"Impossible")<<endl;
#define IMP(a) cout <<((a)?"POSSIBLE":"IMPOSSIBLE")<<endl;
#define pow(a,b) ll(pow(a,b))

ll MOD=1000000007;

signed main(){
	llin(n);
	llin(k);
	vllin(h,n);
	vll d(n,1e10);
	d[0]=0;
	FOR(i,0,n-1){
		FOR(j,1,k){
			if(i-j>=0){
				d[i]=min(d[i],d[i-j]+abs(h[i]-h[i-j]));
			}
		}
	}
	sal(d[n-1]);
}


Measured memory_bytes: 1792
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
using namespace std;
#define rep(i,q) for(int i = 0; (q) > i; i++)

typedef pair<int,int> Paint;

bool Pairfirst(const Paint& pf,Paint&ps){
  return pf.first < ps.first;
}

int main(){
  int N,M;cin >> N>>M;
  vector<Paint> koro;
  rep(i,M){
    int tmp,tmp2;cin>>tmp>>tmp2;
    koro.push_back(Paint(tmp,tmp2));
  }
  set<int> s;
  rep(i,M){
    if(koro[i].first == 1){
      s.insert(koro[i].second);
    }
  }
  bool ok = false;
  rep(i,M){
    if(koro[i].second == N){
      if(s.count(koro[i].first)){
        ok = true;
        break;
      }
      s.insert(koro[i].first);
    }
  }
  
  if(ok)cout << "POSSIBLE" << endl;
  else cout << "IMPOSSIBLE" << endl;
  
}

Measured memory_bytes: 11120
/* monkukui 競技プログラミング用のテンプレート  (ここから) */
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <deque>
#include <list>
#include <queue>
#include <stack>
#include <vector>
#include <utility>
#include <algorithm>
#include <map>
#include <set>
#include <complex>
#include <cmath>
#include <limits>
#include <climits>
#include <ctime>
#include <cassert>
#include <numeric>
#include <functional>
#include <bitset>

using namespace std;
using lint = long long int;
using ll = long long int;
using lnt = long long int;
using Graph = vector<vector<int>>;
using Wgraph = vector<vector<pair<int, long long int>>>;
constexpr long long int INF = 1001001001001001LL;
constexpr long long int MOD = 1000000007LL;
constexpr double PI = 3.1415926535897932;
constexpr long long int di[] = {-1, 0, 1, 0, -1, 1, 1, -1};
constexpr long long int dj[] = {0, 1, 0, -1, 1, 1, -1, -1};

template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
inline void yes(){ cout << "yes" << endl; }
inline void Yes(){ cout << "Yes" << endl; }
inline void YES(){ cout << "YES" << endl; }
inline void no(){ cout << "no" << endl; }
inline void No(){ cout << "No" << endl; }
inline void NO(){ cout << "NO" << endl; }
inline void possible(){ cout << "possible" << endl; }
inline void Possible(){ cout << "Possible" << endl; }
inline void POSSIBLE(){ cout << "POSSIBLE" << endl; }
inline void impossible(){ cout << "impossible" << endl; }
inline void Impossible(){ cout << "Impossible" << endl; }
inline void IMPOSSIBLE(){ cout << "IMPOSSIBLE" << endl; }

#define REP(i,n) for(int i = 0; i < (n); i++)
#define RREP(i,n) for(int i = 1; i <= (n); i++)
#define DREP(i,n) for(int i = (n)-1; i >= 0; i--)
#define SREP(i,s,t) for(int i = s; i < t; i++)
#define ALL(a) a.begin(),a.end()
#define RALL(a) a.rbegin(),a.rend()
#define PB push_back

/* monkukui 競技プログラミング用のテンプレート (ここまで)*/

int main(){
  
  lint dis[500][500];
  for(int i = 0; i < 500; i++) for(int j = 0; j < 500; j++) dis[i][j] = INF;
  for(int i = 0; i < 500; i++) dis[i][i] = 0;
  
  lint n, m, l; cin >> n >> m >> l;
  for(int i = 0; i < m; i++) {
    lint a, b, c; cin >> a >> b >> c;
    a--;
    b--;
    dis[a][b] = dis[b][a] = c;
  }

  for(int k = 0; k < n; k++) {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
      }
    }
  }

  lint G[500][500];

  for(int i = 0; i < 500; i++) for(int j = 0; j < 500; j++) G[i][j] = INF;
  for(int i = 0; i < 500; i++) G[i][i] = 0;

  for(int i = 0; i < n; i++) {
    for(int j = 0; j < n; j++) {
      if(dis[i][j] <= l) G[i][j] = 1;
    }
  }

  for(int k = 0; k < n; k++) {
    for(int i = 0; i < n; i++) {
      for(int j = 0; j < n; j++) {
        G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
      }
    }
  }


  int q; cin >> q;
  for(int i = 0; i < q; i++) {
    int s, t; cin >> s >> t;
    s--;
    t--;
    if(G[s][t] == INF) cout << -1 << endl;
    else cout << G[s][t] - 1 << endl;
  }
  return 0;
}


Measured memory_bytes: 4480
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define REP(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i)
#define REPR(i, n) for (int i = n - 1; i >= 0; i--)
#define INF 1145141919
#define LLINF 1145148101919
#define PI 3.14159265359
int dy[] = {0, 0, 1, -1};
int dx[] = {1, -1, 0, 0};
int ny, nx;
typedef long long ll;
using namespace std;

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

ll lcm(ll m, ll n)
{
    if ((0 == m) || (0 == n))
        return 0;
    return ((m / gcd(m, n)) * n);
}

ll llpow(ll x, ll y)
{
    ll ans = 1;
    REP(i, y)
    ans *= x;
    return ans;
}

int ctoi(char c)
{
    if (c >= '0' && c <= '9')
    {
        return c - '0';
    }
    return 0;
}

class UnionFind
{
public:
    vector<ll> par; // 各元の親を表す配列
    vector<ll> siz; // 素集合のサイズを表す配列(1 で初期化)

    // Constructor
    UnionFind(ll sz_) : par(sz_), siz(sz_, 1LL)
    {
        for (ll i = 0; i < sz_; ++i)
            par[i] = i; // 初期では親は自分自身
    }
    void init(ll sz_)
    {
        siz.assign(sz_, 1LL); // assign: 再代入
        par.resize(sz_);      // resize: 再確保
        for (ll i = 0; i < sz_; ++i)
            par[i] = i; // 初期では親は自分自身
    }

    // Member Function
    // Find
    ll root(ll x)
    { // 根の検索
        while (par[x] != x)
        {
            x = par[x] = par[par[x]]; // x の親の親を x の親とする
        }
        return x;
    }

    // Union(Unite, Merge)
    bool merge(ll x, ll y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        // merge technique（データ構造をマージするテク．小を大にくっつける）
        if (siz[x] < siz[y])
            swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y)
    { // 連結判定
        return root(x) == root(y);
    }

    ll size(ll x)
    { // 素集合のサイズ
        return siz[root(x)];
    }
};

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

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

template <typename Container>
bool exist_in(const Container &c, const typename Container::value_type &v)
{
    return (c.end() != std::find(c.begin(), c.end(), v));
}

vector<ll> decom;

void decompositPrime(ll n)
{
    ll a = 2;
    while (n >= a * a)
    {
        if (n % a == 0)
        {
            decom.push_back(a);
            n /= a;
        }
        else
        {
            a++;
        }
    }
    decom.push_back(n);
}

////////////////////////////////////////

string S, T;
int ctoi_alpha(char c)
{
    if (c >= 'a' && c <= 'z')
    {
        return c - 'a';
    }
    return 0;
}

////////////////////////////////////////

int main()
{
    int A,B;
    cin >> A >> B;
    int ans=0, res=1;

    while(res<B){
        res--;
        res+=A;
        ans++;
    }

    cout << ans << endl;

    return 0;
}


Measured memory_bytes: 256
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;


int main(void) {
	ll n, a, i, b, ans = 2;

	cin >> n;

	if (n == 2) {
		cout << 1 << endl;
		return 0;
	}

	for (a = 2; a * a <= n; a++) {
		if (n % a == 0) {
			b = n;
			while (b % a == 0) b /= a;
			if (b % a == 1) ans++;

			if (a * a == n) continue;
			b = n;
			while (b % (n / a) == 0) b /= (n / a);
			if (b % (n / a) == 1) ans++;
		}
		if (n % a == 1) ans += 2;
		if (a * a == n - 1) ans--;
	}

	cout << ans << endl;

	return 0;
}

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

const ll mod = 1e9+7;

ll repsq(ll n,ll p,ll m){
    if(p==0) return 1;
    if(p%2==0){
        ll t= repsq(n,p/2,m) %m;
        return t*t %m;
    }
    return ( n * repsq(n,p-1,m) ) % m;
}

int main(){
    ll n,a,b;cin>>n>>a>>b;
    ll ans = (repsq(2,n,mod)-1) % mod;

    ll dis_a=1,dis_b=1;
    ll Y_a=1,Y_b=1;

    for(ll i=0;i<a;i++){
        dis_a = ( dis_a *(n-i) ) % mod;
        Y_a = ( Y_a *(i+1) ) % mod;
    }
    dis_a *= repsq(Y_a,mod-2,mod);
    dis_a = dis_a % mod;

    for(ll i=0;i<b;i++){
        dis_b = ( dis_b *(n-i) ) % mod;
        Y_b = ( Y_b *(i+1) ) % mod;
    }
    dis_b *= repsq(Y_b,mod-2,mod);
    dis_b = dis_b % mod;

    ans = (ans -dis_a -dis_b +311*mod) % mod;
    cout<< ans <<endl;
}

Measured memory_bytes: 256
// E - Coprime
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
#define rpd(i,s,e,d) for(int i=(s);i<(int)(e);i+=(d))

vi gen_d_prim(int n){
	vi D(n+1, 0);
	rpd(i, 2, n+1, 1)
		if(!D[i]) rpd(j, i, n+1, i) D[j] = i;
	return D;
}

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

	int N; cin>>N;
	int g = 0;
	bool is_not_pairwise = false;
	vi D = gen_d_prim(1000000);
	set<int> past;
	rpd(i, 0, N, 1){
		int a; cin>>a;
		g = gcd(g, a);
		if(is_not_pairwise) continue;
		set<int> now;
		while(a != 1){
			// 素数 D[a]: 今回は未済 & 過去は済
			if(( is_not_pairwise = !now.count(D[a]) && past.count(D[a]) )) break;
			now.insert(D[a]);
			past.insert(D[a]);
			a /= D[a];
		}
	}
	int t = 0;
	if(g > 1) t = 2;
	else t = is_not_pairwise;
	cout<< vector<string>{"pairwise","setwise","not"}[t] <<" coprime\n";
}


Measured memory_bytes: 10848
#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n) ; ++i)

using namespace std;

int main(){
  int n , m;
  cin >> n >> m;
  vector <int> ac(n) , pe(n);
  rep(i,m){
    int p;
    string s;
    cin >> p >> s;
    --p;
    if(ac[p]) continue;
    if(s == "AC"){
      ac[p] = 1;
    }else{
      pe[p]++;
    }
  }
  int addAC = 0 , addPena =0;
  rep(i,n){
    addAC+= ac[i];
    if(ac[i]) addPena += pe[i];
  }
  cout << addAC << " " << addPena << endl;
  return 0;
}


Measured memory_bytes: 1024
using System;
using System.Collections.Generic;
using System.Text;

namespace AtTest.GridSearch
{
    class AtTemplate
    {
        static void Main(string[] args)
        {
            Method(args);
            Console.ReadLine();
        }

        static void Method(string[] args)
        {
            string[] input = Console.ReadLine().Split(' ');
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            int c = int.Parse(input[2]);
            int d = int.Parse(input[3]);

            int time = 0;
            int p1, p2, p3, p4;
            if (a < c)
            {
                int max = b < d ? b : d;
                time = max - c;
                if (time < 0)
                {
                    time = 0;
                }
            }
            else
            {
                int max = d < b ? d : b;
                time = max - a;
                if (time < 0)
                {
                    time = 0;
                }
            }
            Console.WriteLine(time);
        }
    }
}


Measured memory_bytes: 13140
N, Q = map(int, input().split())
S = input()
S_sum_list = [0,0]
S_sum = 0
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        S_sum += 1
        S_sum_list.append(S_sum)
    else:
        S_sum_list.append(S_sum)
ans = []
for j in range(Q):
    l, r = map(int, input().split())
    ans.append(S_sum_list[r] - S_sum_list[l])

for k in range(len(ans)):
    print(ans[k])



Measured memory_bytes: 10320
A, B, K = map(int, input().split())
lista = [a for a in range(1, A + 1) if A % a == 0]
listb = [b for b in range(1, B + 1) if B % b == 0]
listc = sorted(list(set(lista) & set(listb)))
#print(lista)
#print(listb)
#print(listc)

print(listc[-K])


Measured memory_bytes: 2940
import Data.List
import qualified Data.ByteString.Char8 as B
import Control.Monad 
import Data.Ord 

main :: IO ()
main = breads >>= main'
    where
        main' [n, h] = replicateM n breads >>= print . solve h

solve :: Int -> [[Int]] -> Int
solve h xs
        | h < bsum = calc h bs
        | otherwise = length bs + an
    where
        bs = sortBy (flip compare) . filter (> fa) $ fmap last xs
        fa = head $ maximumBy (comparing head) xs
        bsum = sum bs
        (ar, am) = (h - bsum) `divMod` fa
        an
            | am > 0 = ar + 1
            | otherwise = ar

        calc r (y : ys)
            | r > 0 = 1 + calc (r - y) ys
            | otherwise = 0
        calc _ _ = 0

breads :: IO [Int]
breads = unfoldr uff <$> B.getLine
    where
        uff b = check <$> B.readInt b
        check (a, b)
            | B.null b = (a, b)
            | otherwise = (a, B.tail b)

Measured memory_bytes: 42748
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

using pi = pair<int,int>;

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

bool is_edge(int x, char c){
    if(x<2) return c=='-';
    return c=='|';
}

int main(){
    int h,w;
    char s,t;
    cin >>h >>w >>s >>t;

    vector<string> f(h);
    rep(i,h) cin >>f[i];

    pi start,goal;
    rep(i,h)rep(j,w){
        if(f[i][j] == s) start = {i,j};
        if(f[i][j] == t) goal = {i,j};
    }

    auto IN = [&](int y, int x){ return 0<=y && y<h && 0<=x && x<w; };

    vector<vector<int>> d(h,vector<int>(w,INF));
    queue<pi> que;
    d[start.fi][start.se] = 0;
    que.push(start);
    while(!que.empty()){
        pi now = que.front();
        que.pop();

        rep(i,4){
            int xx = now.se+2*dx[i], yy = now.fi+2*dy[i];
            if(IN(yy,xx) && is_edge(i,f[yy][xx])){
                while( !('A'<=f[yy][xx] && f[yy][xx]<='Z') ){
                    yy += dy[i];
                    xx += dx[i];
                }

                if(('A'<=f[yy][xx] && f[yy][xx]<='Z')){
                    if(d[yy][xx] > d[now.fi][now.se]+1){
                        d[yy][xx] = d[now.fi][now.se]+1;
                        que.push({yy,xx});
                    }
                }
            }
        }
    }

    cout << d[goal.fi][goal.se] << endl;
    return 0;
}



Measured memory_bytes: 3240
/*  -*- coding: utf-8 -*-
 *
 * 1601.cc: Short Phrase
 */

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<deque>
#include<algorithm>
#include<numeric>
#include<utility>
#include<complex>
#include<functional>
 
using namespace std;

/* constant */

const int MAX_N = 40;
const int K = 5;
const int ts[K] = { 5, 7, 5, 7, 7 };

/* typedef */

/* global variables */

char s[16];
int wls[MAX_N];

/* subroutines */

/* main */

int main() {
  for (;;) {
    int n;
    scanf("%d", &n);
    if (n == 0) break;

    for (int i = 0; i < n; i++) {
      scanf("%s", s);
      wls[i] = strlen(s);
    }

    for (int st = 0; st < n; st++) {
      int k = 0, sum = 0;
      for (int i = st; i < n && k < K; i++) {
	sum += wls[i];
	if (sum == ts[k])
	  k++, sum = 0;
	else if (sum > ts[k])
	  break;
      }

      if (k == K && sum == 0) {
	printf("%d\n", st + 1);
	break;
      }
    }
  }
  return 0;
}



Measured memory_bytes: 3160
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static readonly int INFTY = int.MaxValue;
        static int[] segment;
        static int size;

        static void Main(string[] args)
        {
            string[] input1 = Console.ReadLine().Split(' ');
            int n = int.Parse(input1[0]);
            int q = int.Parse(input1[1]);

            Init(n);

            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < q; i++)
            {
                string[] input2 = Console.ReadLine().Split(' ');
                int c = int.Parse(input2[0]);
                int x = int.Parse(input2[1]);
                int y = int.Parse(input2[2]);

                if (c == 0) Update(x, y);
                else
                {
                    sb.AppendLine(Query(x, y + 1, 0, 0, size).ToString());
                }
            }
            Console.Write(sb);
        }

        static void Init(int n)
        {
            size = 1;

            while (size < n) size *= 2;

            segment = Enumerable.Repeat(INFTY, 2 * size - 1).ToArray();
        }

        static void Update(int i, int a)
        {
            i += size - 1;
            segment[i] = a;

            while (i > 0)
            {
                i = (i - 1) / 2;
                segment[i] = Math.Min(segment[i * 2 + 1], segment[i * 2 + 2]);
            }
        }

        static int Query(int a, int b, int k, int l, int r)
        {
            if (r <= a || b <= l) return INFTY;

            if (a <= l && r <= b) return segment[k];
            else
            {
                int vl = Query(a, b, k * 2 + 1, l, (l + r) / 2);
                int vr = Query(a, b, k * 2 + 2, (l + r) / 2, r);

                return Math.Min(vl, vr);
            }
        }
    }
}

Measured memory_bytes: 12968
#include<bits/stdc++.h>
using namespace std;
int main() {
    char s[1010];
    scanf("%s", s);
    int len = strlen(s);
    if (s[len - 1] == 's')  s[len++] = 'e';
    s[len++] = 's';
    s[len] = '\0';
    printf("%s\n", s);
}


Measured memory_bytes: 3680