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

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned __int128 HASH;
typedef pair<int,int> pii;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pullull;
typedef pair<ll,int> plli;
typedef pair<double, int> pdbi;
typedef pair<int,pii> pipii;
typedef pair<ll,pll> plpll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;
typedef vector<vector<int>> mat;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()
#define rall(a) (a).rbegin(),(a).rend()

const ll hmod1 = 999999937;
const ll hmod2 = 1000000000 + 9;
const int INF = 1<<30;
const ll mod = 1000000000 + 7;
const int dx4[4] = {1, 0, -1, 0};
const int dy4[4] = {0, 1, 0, -1};
const int dx8[8] = {1, 1, 1, 0, 0, -1, -1, -1};
const int dy8[8] = {0, 1, -1, 1, -1, 0, 1, -1};
const double pi = 3.141592653589793;

#define addm(X, Y) (X) = ((X) + ((Y) % mod) + mod) % mod

int n, m;
vector<vector<int>> g(100000 + 5);
int color[100000 + 5];

signed main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    rep(i, m) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    fill(color, color + n, -1);
    queue<int> q;
    q.push(0);
    color[0] = 0;
    bool loop = false;
    while (!q.empty()) {
        int now = q.front(); q.pop();
        for (auto nx : g[now]) {
            if (color[nx] == -1) {
                color[nx] = color[now]^1;
                q.push(nx);
            }
            else {
                if (color[now] == color[nx]) {
                    loop = true;
                    break;
                }
            }
        }
    }
    if (loop) {
        cout << n * (n - 1) / 2 - m << endl;
    }
    else {
        int cnt = 0;
        rep(i, n) {
            if (color[i] == 1) cnt++;
        }
        int ans = 0;
        rep(i, n) {
            if (color[i] == 0) {
                ans += cnt - g[i].size();
            }
        }
        cout << ans << endl;
    }

}


Measured memory_bytes: 7424
#include <bits/stdc++.h>
using namespace std;
#define all(v) (v).begin(), (v).end()
#define lp(i, n) for (int i = 0; i < (n) ; ++i)
#define pr1(x) cout<<"[" << #x << ": " << x << "] \n";
#define pr2(x, y) cout<<"[" << #x << ": " << x <<", "<< #y << ": " << y <<"] \n";
#define mod 1000000007
#define int long long
#define sz(v) (int)(v).size()

int n, k;
vector<int> v;

bool can(int md) {
        int cnt= 0;
        for (int i= 0; i< n; i++) {
                cnt+= ((v[i]+ md- 1)/ md)- 1;
        }
        return cnt<= k;
}

void solve() {
        cin >> n>> k;
        v.resize(n);
        lp(i, n) cin >> v[i];

        int lo= 1, hi= 1e12, md, ans= 0;
        while (hi>= lo) {
                md= (lo+ hi)/ 2;
                if (can(md)) {
                        ans= md;
                        hi= md- 1;
                } else lo= md+ 1;
        }
        cout << ans<< "\n";
}

int32_t main(){
ios::sync_with_stdio(0), cin.tie(NULL), cout.tie(NULL);
        int t = 1;
        //cin >> t;
        while ( t-- ) {
                solve();
        }
return 0;
}


Measured memory_bytes: 4692
n, a, b = map(int, input().split())
mod = 10 ** 9 + 7


def mod_cmb(n, r, mod):
    p, q = 1, 1
    for i in range(r):
        p = p * (n - i) % mod
        q = q * (i + 1) % mod
    return p * pow(q, mod - 2, mod) % mod


answer = pow(2, n, mod) - 1
answer -= mod_cmb(n, a, mod) + mod_cmb(n, b, mod)
answer %= mod
print(answer)


Measured memory_bytes: 3064
n = int(input())
dp = [200000] * (n+10)
dp[0] = 0
# dp[1] = 1
for i in range(n):
    dp[i+1] = min(dp[i+1], dp[i]+1)
    six = 6
    while i + six <= n:
        dp[i+six] = min(dp[i+six], dp[i]+1)
        six *= 6 

    nine = 9
    while i + nine <= n:
        dp[i+nine] = min(dp[i+nine], dp[i]+1)
        nine *= 9

print(dp[n])

Measured memory_bytes: 3828
import java.util.*;


public class Main {
    public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//情報を読み込む
		int line = sc.nextInt();
		//配列を作る
		int data[][][] = new int[4][3][10];
		//データを読み込む
		for (int i = 0; i < line; i++) {
		    int b = sc.nextInt();
		    int f = sc.nextInt();
		    int r = sc.nextInt();
		    //部屋の人数
		    int v = sc.nextInt();
		    data[b - 1][f - 1][r -1] += v;
		}
		
		for (int i = 0; i < 4; i++) {
		    for (int t = 0; t < 3; t++) {
		        for (int j = 0; j < 10; j++) {
		            System.out.print(" " + data[i][t][j]);
		        }
		        System.out.println();
		    }
		    if (i != 3) 
		        System.out.println("####################");
		}
    }
}


Measured memory_bytes: 29528
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<iomanip>
#include<queue>

using namespace std;

typedef long long ll;

typedef std::pair<int, int> ipair;
bool lessPair(const ipair& l, const ipair& r){return l.second < r.second;}
bool morePair(const ipair& l, const ipair& r){return l.second > r.second;}

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

const ll MOD = 1e9 + 7;
// const long long INF = 1LL<<60;
void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; }
void sub(long long &a, long long b) { a -= b; if (a < 0) a += MOD; }
void mul(long long &a, long long b) { a *= b; a %= MOD; }
ll llmin(ll a, ll b) { if (a < b) return a; else return b; }
ll llmax(ll a, ll b) { if (a < b) return b; else return a; }
ll llabs(ll a) { if (a >= 0) return a; else return - a; }
ll llmodpow(ll a, ll n) {
   if (n == 0) return 1;
   ll tmp = llmodpow(a, n / 2);
   mul(tmp, tmp);
   if (n & 1) mul(tmp, a);
   return tmp;
}

int main() {
   int A, B;
   cin >> A >> B;
   if (A + B < 10)
      cout << A + B << endl;
   else 
      cout << "error" << endl;
   return 0;
}


Measured memory_bytes: 256
#include <algorithm>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>

using namespace std;
using ll = long long;

constexpr ll infl = 10000000000000007LL;
constexpr int inf = 1000000007;

int main() {
    string s;
    cin >> s;

    vector<bool> existed(26);
    for (int i = 0; i < s.size(); ++i) {
        existed[s[i] - 'a'] = true;
    }

    if (s.size() < 26) {
        for (int i = 0; i < 26; ++i) {
            if (!existed[i]) {
                cout << (s + (char)(i + 'a')) << endl;
                return 0;
            }
        }
    }
    existed[s.back() - 'a'] = false;

    for (int i = s.size() - 1; i >= 1; --i) {
        for (int j = s[i] - 'a' + 1; j < 26; ++j) {
            if (!existed[j]) {
                cout << (s.substr(0, i) + (char)(j + 'a')) << endl;
                return 0;
            }
        }
        existed[s[i - 1] - 'a'] = false;
    }

    if (s.front() == 'z')
        cout << -1 << endl;
    else
        cout << (char)(s.front() + 1) << endl;
    return 0;
}

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

int main()
{

   int n;
   cin>>n;
  vector<string> v;
   for(int i=0;i<n;i++)
   {
       string s;
       cin>>s;
       v.push_back(s);
   }
   map<string,int> mp;

   for(int i=0;i<n;i++)
   {
       mp[v[i]]++;
   }
   int count=0;
   for(auto i=mp.begin();i!=mp.end();i++)
   {
     count++;

   }
   cout<<count<<endl;

   return 0;

}


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

using namespace std;

int SortedData[100];

int main() {
	int n, k, cnt, left, right, mid;

	while (cin >> n, n) {
		for (int i = 0; i < n; i++) {
			cin >> SortedData[i];
		}
		cin >> k;

		left = 0;
		right = n - 1;
		cnt = 0;
		while (1) {
			++cnt;
			mid = (left + right) / 2;
			if (SortedData[mid] == k) {
				break;
			}
			if (SortedData[mid] < k) {
				left = mid + 1;
			}
			else if (SortedData[mid] > k) {
				right = mid - 1;
			}
			if (left > right) {
				break;
			}
		}
		cout << cnt << endl;
	}

	return 0;
}


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

using namespace std;

#define REP(i,m) for(ll i=0; i<m; i++)
#define FOR(i,n,m) for(ll i=n; i<m; i++)
#define INF 1000000007
#define INFL (1LL << 60)
#define MOD 998244353
#define ALL(v) v.begin(),v.end()
#define pb push_back
#define ll long long int
#define P pair<ll, ll>

int main(){
	int rem[100010];
	rem[0] = 1;
	REP(i, 100009) rem[i+1] = (rem[i]*10)%13;
	string s;
	cin >> s;
	int l = s.size();
	ll dp[100010][13] = {};
	if(s[l-1] == '?') REP(i, 10) dp[0][i] = 1;
	else dp[0][s[l-1]-'0'] = 1;
	FOR(i, 1, l){
		if(s[l-1-i] == '?'){
			REP(j, 13){
				REP(k, 10){
					(dp[i][(j+k*rem[i])%13] += dp[i-1][j]) %= INF;
				}
			}
		}
		else{
			REP(j, 13){
				int k = s[l-1-i] - '0';
				(dp[i][(j+k*rem[i])%13] += dp[i-1][j]) %= INF;
			}
		}
	}
	cout << dp[l-1][5] << endl;
	return 0;
} 


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

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int a = scan.nextInt();
		int b = scan.nextInt();

		System.out.print(a*b);
		System.out.print(" ");
		System.out.println(2*(a+b));
	}

}

Measured memory_bytes: 26392
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<string>

using namespace std;

inline int read(){
    int s=0,w=1,ch=getchar();
    while(ch<'0'||ch>'9')if(ch=='-')w=-1,ch=getchar();
    while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar();
    return s*w;
}

inline void write(int x)
{
    char F[16]={};int cnt=0;
    if(x==0)
	{
	    putchar('0');
	    return;
	}
    if(x<0)putchar('-');
    while(x)
    {
        F[cnt++]=x%10+'0';
        x/=10;
    }
    while(cnt>0)putchar(F[--cnt]);
}


int main()
{
	//freopen_init();
	int reads=read();
	write(reads*800-reads/15*200);
	
	putchar('\n');
	return 0;
}


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

void dfs(int n,vector<int>adj[], int dp[], bool vis[]){
	vis[n] = true;
	for(int i=0;i<adj[n].size();i++){
		if(!vis[adj[n][i]]){
			dfs(adj[n][i],adj,dp,vis);
		}
		dp[n] = max(dp[n], 1+ dp[adj[n][i]]);
	}
}

int findLongestpath(vector<int> adj[], int n){
	int dp[n+1];
	memset(dp,0,sizeof(dp));

	bool vis[n+1];
	memset(vis, false, sizeof(vis));

	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i,adj,dp,vis);
		}
	}

	int ans = 0;
	for(int i=1;i<=n;i++){
		ans = max(ans,dp[i]);
	}

	return ans;
}
int main(){
	int n,m;
	cin >> n >> m;
	
	int x,y;
	vector<int>adj[n+1];
	
	for(int i=0;i<m;i++){
		cin >> x >> y;
		adj[x].push_back(y);
	}

	cout << findLongestpath(adj,n);
	return 0;
}

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

int main() {
    int N;
    cin >> N;
    vector<pair<int, int>> A(N);
    for (int i = 0; i < N; i++) {
        A[i].first = i + 1;
        cin >> A[i].second;
    }
    sort(A.begin(), A.end(), [](const auto& p1, const auto& p2){return p1.second < p2.second;});
    for (const auto& a : A) {
        cout << a.first << " ";
    }
}

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

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

    int c = 0;
    for (int i = 1; i <= n; i+=2) {
        int y = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) { 
                y++;
            }
        }
        if (y== 8) {
            c++;
        }
    }

    cout << c << endl;
}



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

int main(){
	double v, t, y, n;
	while(cin >> v){
		t = v / 9.8;
		y = 4.9 * t * t;
		n = (int)(ceil(y/5.0)) + 1;
		cout << n << endl;
	}
	return 0;
}

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

int main() {
  int A[9], N, B[10], C[10] = {0};
  for (int i = 0; i < 9; i++) {
    cin >> A[i];
  }
  cin >> N;
  for (int i = 0; i < N; i++) {
    cin >> B[i];
  }

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 9; j++) {
      if (A[j] == B[i]) {
        C[j] = 1;
      }
    }
  }

  bool ok = false;
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < 3; j++) {
      if (C[j] == 1 && C[j+3] == 1 && C[j+6] == 1) {
        ok = true;
      }
      if (C[j*3] == 1 && C[j*3+1] == 1 && C[j*3+2] == 1) {
        ok = true;
      }
      if (C[0] == 1 && C[4] == 1 && C[8] == 1) {
        ok = true;
      } else if (C[2] == 1 && C[4] == 1 && C[6] == 1) {
        ok = true;
      }
    }
  }

  if (ok) {
    cout << "Yes" << endl;
  } else {
    cout << "No" << endl;
  }
}


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

long long mod = 1000000007;

long long fac(long long x){
    if(x == 1) return 1;
    else return (fac(x - 1)*x)%mod;
}

int main(){
    long long n,m,ans = 0;
    cin >> n >> m;

    if(abs(n - m) > 1){
        ans = 0;
    }
    else{
        ans += fac(n);
        ans = (ans * fac(m))%mod;
        switch(abs(n - m)){
            case 1:
            break;
            case 0:
            ans = (ans*2)%mod;
            break;
        }
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 1792
use std::io;


fn main() {
    let xy = read::<isize>();
    let dx = xy[2] - xy[0];
    let dy = xy[3] - xy[1];
    println!("{} {} {} {}", xy[2] - dy, xy[3] + dx, xy[0] - dy, xy[1] + dx);
}


#[allow(dead_code)]
fn read<T>() -> Vec<T>
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.split_whitespace()
        .map(|s| s.trim().parse().unwrap())
        .collect()
}

#[allow(dead_code)]
fn read_one<T>() -> T
where T:
    std::str::FromStr,
    T::Err: std::fmt::Debug {

    let mut buf = String::new();
    io::stdin().read_line(&mut buf).unwrap();
    buf.trim().parse().unwrap()
}

Measured memory_bytes: 4352
N,M=map(int,input().split())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
mod=10**9+7
sm=[[ 0 for i in range(M)] for j in range(N)]
s1=0
s2=0
if N>M:
  for i in range(N):
    if t[0]==s[i]:
      a=1
    else:
      a=0
    s1=s1+a
    sm[i][0]=s1
    if i<M:
      if s[0]==t[i]:
        a=1
      else:
        a=0
      s2=s2+a
      sm[0][i]=s2
else:
  for i in range(M):
    if s[0]==t[i]:
      a=1
    else:
      a=0
    s2=s2+a
    sm[0][i]=s2
    if i<N:
      if t[0]==s[i]:
        a=1
      else:
        a=0
      s1=s1+a
      sm[i][0]=s1
for i in range(1,N):
  for j in range(1,M):
    if s[i] != t[j]:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1])%mod
    else:
      sm[i][j]=(sm[i-1][j]+sm[i][j-1]-sm[i-1][j-1]+sm[i-1][j-1]+1)%mod
ans=(sm[N-1][M-1]+1)%mod
print(ans)

Measured memory_bytes: 75100
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
vector <vector<int>> vec;
vector <int> dp;
 
void dfs(int i){
    if(vec[i].size()==0)dp[i]=0;
    for(auto v:vec[i]){
        if(dp[v]==-1)dfs(v);
        if((dp[v]+1)>dp[i])dp[i]=dp[v]+1;
    }
}
 
int main() {
    int n,m;
    cin>>n>>m;
    vec.assign(n,vector <int>(0));
    dp.assign(n,-1);
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        a--;b--;
        vec[a].pb(b);
    }
    int mx=-1;
    for(int i=0;i<n;i++){
    if(dp[i]==-1)dfs(i);
    mx=max(mx,dp[i]);}
    cout<<mx<<endl;
    
    
}

Measured memory_bytes: 8192
N,T = gets.chomp.split(" ").map(&:to_i)
ary = Array.new(N).map{Array.new(2)}
N.times do |i|
  ary[i] = gets.chomp.split(" ").map(&:to_i)
end 
min = 1010
ary.each do |ct|
  if ct[1] <= T && ct[0] < min
    min = ct[0]
  end
end

unless min == 1010
  puts min
else 
  puts "TLE"
end

Measured memory_bytes: 1788
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#define rad M_PI/3
#define N 200001
#define Max 10000
#define NTL -1
typedef struct{
    int left,right;
}Node;
Node T[N];
int n;
char root[N];
void previsit(int p){
    printf(" %d",p);
    if(T[p].left != NTL) previsit(T[p].left);
    if(T[p].right != NTL) previsit(T[p].right);
}
void invisit(int p){
    if(T[p].left != NTL) invisit(T[p].left);
    printf(" %d",p);
    if(T[p].right!=NTL) invisit(T[p].right);
}
void postvisit(int p){
    if(T[p].left!=NTL) postvisit(T[p].left);
    if(T[p].right!=NTL) postvisit(T[p].right);
    printf(" %d",p);
}
int main()
{
    int i,r;
    scanf("%d",&n);
    memset(root,1,n);
    for(i=0;i<n;i++){
        T[i].left=T[i].right=NTL;
    }
    for(i=0;i<n;i++){
        int id,l,r;
        scanf("%d%d%d",&id,&l,&r);
        T[id].left=l;
        T[id].right=r;
        root[l]=root[r]=0;
    }
    for(i=0;i<n;i++)
        if(root[i]) r=i;
    printf("Preorder\n");
    previsit(r);
    printf("\n");
    printf("Inorder\n");
  invisit(r);
  printf("\n");
  printf("Postorder\n");
  postvisit(r);
  printf("\n");
  return 0;
}


Measured memory_bytes: 2044
suf = ["dream", "dreamer", "erase", "eraser"]

s = input()
dp = [0] * (len(s) + 1)
dp[0] = 1
for i in range(len(s)):
    if not dp[i]:
        continue
    for it in suf:
        if s[i:i+len(it)] == it:
            dp[i + len(it)] = 1
print("YES") if dp[len(s)] else print("NO")


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

// #define int long long
#define rep(i, n) for (long long i = (long long)(0); i < (long long)(n); ++i)
#define reps(i, n) for (long long i = (long long)(1); i <= (long long)(n); ++i)
#define rrep(i, n) for (long long i = ((long long)(n)-1); i >= 0; i--)
#define rreps(i, n) for (long long i = ((long long)(n)); i > 0; i--)
#define irep(i, m, n) for (long long i = (long long)(m); i < (long long)(n); ++i)
#define ireps(i, m, n) for (long long i = (long long)(m); i <= (long long)(n); ++i)
#define SORT(v, n) sort(v, v + n);
#define REVERSE(v, n) reverse(v, v+n);
#define vsort(v) sort(v.begin(), v.end());
#define all(v) v.begin(), v.end()
#define mp(n, m) make_pair(n, m);
#define cout(d) cout<<d<<endl;
#define coutd(d) cout<<std::setprecision(10)<<d<<endl;
#define cinline(n) getline(cin,n);
#define replace_all(s, b, a) replace(s.begin(),s.end(), b, a);
#define PI (acos(-1))
#define FILL(v, n, x) fill(v, v + n, x);
#define sz(x) long long(x.size())

using ll = long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vs = vector<string>;
using vpll = vector<pair<ll, ll>>;
using vtp = vector<tuple<ll,ll,ll>>;
using vb = vector<bool>;

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 ll INF = 1e9;
const ll MOD = 1e9+7;
const ll LINF = 1e18;



template<typename T>
struct BIT {
  int n;
  vector<T> d;
  BIT(int n=0):n(n),d(n+1) {}
  void add(int i, T x=1) {
    for (; i <= n; i += i&-i) {
      d[i] += x;
    }
  }
  T sum(int i) {
    T x = 0;
    for (; i; i -= i&-i) {
      x += d[i];
    }
    return x;
  }
  T sum(int l, int r) {
    return sum(r-1) - sum(l-1);
  }
};

ll n;
vll a;


ll isOk(ll mid){
  // 中央値がmidに成り得る => 過半数の区間が、mid以下の要素が過半数を占めている
  
  // 区間数の過半数。このborder以上の数の区間が条件を満たすならmidは中央値である可能性がある
  ll border=(n*(n+1)/2)/2;
  
  vll s(n+1); // 数列aにおいてmid以下である要素数の累積和
  rep(i,n){
    s[i+1]=s[i];
    if(a[i]<=mid) s[i+1]++;
    else s[i+1]--;
  }
  
  // midが中央値に成り得る区間の数を以下の方針で数え上げる
  // i<jかつs_j-s_i>=0なるi,jの組数を求める
  // jを固定して、s_j>=s_iなるiの個数の和を求める
  BIT<ll> bit(n*2+10);
  ll cnt=0;
  rep(i,n+1){
    cnt+=bit.sum(1,s[i]+n+1);
    bit.add(s[i]+n+1);
  }
  return cnt>border;
}

signed main()
{
  cin.tie( 0 ); ios::sync_with_stdio( false );
  cin>>n;
  a.resize(n);
  rep(i,n) cin>>a[i];
  
  ll ok=1e9, ng=0;
  while(abs(ok-ng)>1){
    ll mid=(ok+ng)/2;
    if(isOk(mid)) ok=mid;
    else ng=mid;
  }
  cout<<ok<<endl;
}

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

using namespace std;
using ll = long long;
using ull = unsigned long long;

constexpr ll LLINF {1001002003004005006};//ll = 9*LLINF
constexpr int INTINF {1000000000};//int = 2*INTINF

#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)

template<typename T>
void maxs(T& x, T&& y) {
  x=std::max(x,y);
}
template<typename T>
void maxs(T& x, T& y) {
  x=std::max(x,y);
}

template<typename T>
void mins(T& x, T&& y) {
  x=std::min(x,y);
}
template<typename T>
void mins(T& x, T& y) {
  x=std::min(x,y);
}

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

  ull X;
  cin >> X;

  ull tmp {100};
  int answer {};
  while (tmp < X) {
    tmp *= 1.01;
    ++answer;
  }
  cout << answer << '\n';
}


Measured memory_bytes: 3596
#include<iostream>
#include<string>
using namespace std;
int main(){
int n;
cin >> n;
if(n%2==1){
  cout << "No" << endl;
  return 0;
}
char str[105];
for(int i=1;i<=n;i++){
  cin >> str[i];
}
for(int i=1;i<=n/2;i++){
  if(str[i]!=str[i+n/2]){
    cout << "No" << endl;
    return 0;
  }
}
cout << "Yes" << endl;
return 0;
}


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

using namespace std;

int main() {
  int A, B, K;
  cin >> A >> B >> K;
  for (int i = A; i < A + K; i++) {
    if (i > B) break;
    cout << i << endl;
  }
  for (int i = max(B - K + 1, A + K); i <= B; i++) {
    cout << i << endl;
  }

  return 0;
}


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


/* macro */
#define rep(i,a,b) for(int i=a;i<b;i++)
#define revrep(i,a,b) for(int i = a; i > b; i--)
#define int long long
#define exist(s,e) ((s).find(e)!=(s).end())
#define all(v) (v).begin(), (v).end()
#define each(s,itr) for(auto (itr) = s.begin(); (itr) != s.end(); (itr)++)
#define sum(v) accumulate(all(v), (0LL))
#define pb push_back


/* alias */
template<class T> using vec = vector<T>;
typedef vector<int> vi;
typedef pair<int, int> pi;


/* constant */
const int inf = pow(2, 62);
const int mod = 1e9 + 7;
int dx[8]={1,0,-1,0,-1,1,-1,1};
int dy[8]={0,1,0,-1,-1,-1,1,1};
const string alpha = "abcdefghijklmnopqrstuvwxyz";

/* io_method */
int input(){int tmp;cin >> tmp;return tmp;}
string raw_input(){string tmp;cin >> tmp;return tmp;}
string readline(){string s;getline(cin, s);return s;}
template<class T> void printx(T n){cout << n;}
template<class T, class U> void printx(pair<T, U> p){cout << "(" << p.first << "," << p.second << ")";}
template<class T> void printx(vector<T> v){cout << "{";rep(i,0,v.size()){printx(v[i]);if(i != v.size()-1)printx(",");}cout << "}";}
template<class T> void print(T n){printx(n);cout << endl;}
template<class T> void print(set<T> s){cout << "{";each(s, e){if(e != s.begin()) printx(",");printx(*e);}cout << "}" << endl;}
template<class T, class U> void print(map<T, U> mp){cout << "{";each(mp, e){cout << "(" << e -> first << "," << e -> second << ")";}cout << "}" << endl;}


/* general_method */
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; }




/* main */
vi p = {1};
vi stk = {1};

int dfs(int level, int f){

    if(level == 0) return 1;

    if(f == 1) return 0;

    if(f < (stk[level] - 3)/ 2 + 1) return dfs(level - 1, f - 1);

    if(f == (stk[level] - 3)/ 2 + 1) return p[level - 1];

    if(f == (stk[level] - 3)/2 + 2) return p[level - 1] + 1;

    if(f > (stk[level] - 3)/ 2 + 2) return p[level - 1] + 1 + dfs(level - 1, f - stk[level - 1] - 2);


}


signed main(){

    cin.tie(0);
    ios::sync_with_stdio(false);


    int n, x; cin >> n >> x;

    

    rep(i,0,55){
        p.push_back(p.back() * 2 + 1);
        stk.push_back(stk.back() * 2 + 3);
    }

    print(dfs(n, x));


    


    

}

Measured memory_bytes: 256
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <stack>

using std::cin;
using std::cout;
using std::endl;
using std::setprecision;
using std::fixed;
using std::pair;
using std::make_pair;
using std::string;
using std::vector;
using std::list;
using std::map;
using std::set;
using std::queue;
using std::priority_queue;
using std::stack;

typedef vector<long> VI;
typedef vector<vector<long> > VII;
typedef vector<string> VS;
typedef pair<long, long> PII;

int main(void) {
    VI check(100300, 1);
    long size = check.size();
    check[0] = 0;
    check[1] = 0;
    for (long i = 2; i < size; i++) {
        if (check[i] == 1) {
            long j = i * 2;
            while (j < size) {
                check[j] = 0; 
                j += i;
            }
        }
    }


    long n;
    long p;
    while (cin >> n >> p) {
        if (n == -1 && p == -1) {
            break;
        }
        VI prime;
        long count = 0;
        for (long i = n + 1; i < size; i++) {
            if (check[i] == 1) {
                prime.push_back(i); 
                count++;
            }
            if (count == 100) {
                break;
            }
        }
        VI plus;
        for (long i = 0; i < prime.size(); i++) {
            for (long j = i; j < prime.size(); j++) {
                plus.push_back(prime[i] + prime[j]);
            }
        }
        sort(plus.begin(), plus.end());
        cout << plus[p - 1] << endl;
    }
    return 0;
}

Measured memory_bytes: 3884
def main(S=None):
    if not S:
        S = input()
    r = [0]*2019
    r[0] = 1
    tmp = 0
    base = 1
    for s in S[::-1]:
        s = int(s) * base
        base *= 10
        base %= 2019
        tmp += s
        tmp %= 2019
        r[tmp] += 1
    count = 0
    for v in r:
        count += v*(v-1)//2
    print(count)
    return count


if __name__ == "__main__":
    # assert main("1817181712114") == 3
    # assert main("14282668646") == 2
    # assert main("2119") == 0
    main()


Measured memory_bytes: 9400
eval"d,c={};f=->a,b=0{d[[c,b]]||=(f[a+%d,b];f[a+%d,b];f[a,b+%d];f[a,b+%d];a>0?b.quo(a):-1)if a*%d>=b&&%d>=c=a*100+b};f[0];p *d.invert.max[1]"%`dd`.split

Measured memory_bytes: 5384
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define space " "
#define MOD (long long int) 1000000007
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename T> void __f(const char* variable_name, T&& value){cout << variable_name << ": " << value << endl;}
template <typename T1, typename... T2> void __f(const char* names, T1&& arg1, T2&&... args){const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << ": " << arg1 << " |";__f(comma + 1, args...);}

const ll N = 5e5 + 5;
ll *v;
ll n, k, K;

ll _min(ll k){
    ll sum = (k * (k - 1)) / 2;
    return sum;
}

ll _max(ll k){
    ll overall = n * (n + 1) / 2;
    ll t = _min(n - k + 1);
    return overall - t;
}

void solve(){
    cin >> n >> K;
    ll ans = 0;
    for(ll k = K; k <= n + 1; k++){
        ans += (_max(k) - _min(k)) + 1;
        // trace(ans, _max(k), _min(k), (_max(k) - _min(k)) + 1, MOD);
        ans = ans % MOD;
    }
    cout << ans << endl;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    ll t = 1;
    // cout << "\n\nBLAH BLAH BLAH\n\n";
    // cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

Measured memory_bytes: 3596
def examA():
    s = LS()
    ans = (s[0][0]+s[1][0]+s[2][0]).upper()
    print(ans)


import sys
import copy
import bisect
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

examA()


Measured memory_bytes: 38384
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,i,p,k;
    cin>>n>>m>>k;
    p=n/k;
    if(n%k!=0)
    {
        p++;
    }
    if(p<=m)
    {
        cout<<"Yes";
    }
    else cout<<"No";
}


Measured memory_bytes: 3636
#include "bits/stdc++.h"
using namespace std;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
const long long MOD = 1e9+7, MAx = 1e18, larg = 1e5, INF = -1e9;
long long A,B,C,D,E,F,G,H,I,J,K,L,N,M,O,P,Q,R,S,T,U,V,W,x,y,z;
long long max_value = INF, max_index = -1;
long long min_value = MAx, min_index = -1;

typedef long long ll;
typedef pair<ll, ll> Pa;

int main() {
    string s,t;
    cin >> s >> t;
    cout << t+s;
}


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

#define int long long int
#define main signed main()
#define bye return 0
#define loop(i, a, n) for (int i = (a); i < (n); i++)
#define rep(i, n) loop(i, 0, n)
#define each(p, v) for (auto p = (v).begin(); p != (v).end(); p++)
#define all(v) (v).begin(), (v).end()
#define prec(n) fixed << setprecision(n)
#define dump(x) cerr << "(L" << __LINE__ << ") " << #x << " = " << (x) << endl
#define clr(x, a) memset(x, a, sizeof(x))

#define sum(v) accumulate(all(v), 0)
#define stlice(from, to) substr(from, (to) - (from) + 1)
#define odd(n) ((n) % 2)
#define even(n) (!odd(n))

#define INF 1000000000
#define MOD 1000000007

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define fi first
#define se second
#define vi vector<int>
#define vb vector<bool>
#define vc vector<char>

using namespace std;

main {
  int a,b,c,d,e,f,g,h;
  cin>>a>>b>>c>>d>>e>>f>>g>>h;
  cout<<max(a+b+c+d,e+f+g+h)<<endl;
  bye;
}

Measured memory_bytes: 3088
#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <numeric>
#include <string>
#include <string.h>
#include <map>
#include <set>
#include <functional>
#include <complex>
#include <stack>
#include <tuple>
#include <array>
using namespace std;

#define FOR(i,a,b) for (int i=(a);i<(b);i++)
#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)
#define REP(i,n) for (int i=0;i<(n);i++)
#define RREP(i,n) for (int i=(n)-1;i>=0;i--)
#define ALL(u) begin(u),end(u)
#define PB push_back
#define LE(n,m) ((n) < (m) + EPS)
#define GE(n,m) ((n) + EPS > (m))
#define EQ(n,m) (abs((n)-(m)) < EPS)

typedef long long int ll;
const int INF = (1<<30) - 1;
const double EPS = 1e-9;
const int MOD = 1000000007;

int P, Q, A, N;

int dfs(double total, int Atotal, int xmax, int n){
    if(EQ(double(P)/Q, total)){
        return 1;
    }
    
    int res = 0;
    if(n == N)
        return res;
    
    for(int i=xmax; i*Atotal<=A; i++){
        if(total + 1.0/i > double(P)/Q + EPS)
            continue;
        
        res += dfs(total+1.0/i, Atotal*i, i, n+1);
    }
    return res;
}

//g++ -std=c++0x -msse4.2 -O3
//#include <bits/stdc++.h>
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.precision(16);
    //cout.setf(ios::fixed);
    
    while(cin >> P >> Q >> A >> N, P|Q|A|N)
        cout << dfs(0, 1, 1, 0) << endl;
    
    return 0;
}

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

int main(void) {
	string S, rS;
	string frontS, backS, rFrontS, rBackS;
	cin >> S;
	rS = S;
	reverse(rS.begin(), rS.end());
	rFrontS = S.substr(0, (S.size() - 1) / 2);
	frontS = rFrontS;
	reverse(rFrontS.begin(), rFrontS.end());
	rBackS = S.substr((S.size() + 3) / 2 - 1);
	backS = rBackS;
	reverse(rBackS.begin(), rBackS.end());
	if (S == rS && frontS == rFrontS && backS == rBackS) {
		cout << "Yes" << endl;
	}
	else {
		cout << "No" << endl;
	}
	return 0;
}

Measured memory_bytes: 256
N, K = map(int, input().split())
S = []
for _ in range(K):
    l, r = map(int, input().split())
    S.append((l, r))

mod = 998244353
 
dp = [0] * (N+1)
cumsum_dp = [0] * (N+1)
dp[1] = 1
cumsum_dp[1] = 1

for i in range(2, N+1):
    for s in S:
        fr = max(0, i-s[1]-1)
        to = max(0, i-s[0])
        dp[i] += (cumsum_dp[to]-cumsum_dp[fr]) % mod
    cumsum_dp[i] = (cumsum_dp[i-1] + dp[i]) % mod
    
print(dp[N]%mod)

Measured memory_bytes: 76836
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 1000000007
#define in insert
#define mp make_pair
#define F first
#define pb push_back
#define speed ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define test ll t; cin>>t; while(t--)
ll exp(ll x,ll y,ll p){ ll res=1; while(y) {if(y%2) res=(res*x%p)%p; x=(x*x)%p; y/=2; } return res;}
ll exp(ll x,ll y){ ll res=1; while(y) {if(y%2) res=(res*x); x=(x*x); y/=2; } return res;}

int main(){
    ll a[3][3], vis[3][3];
    for(ll i=0;i<3;i++){
        for(ll j=0;j<3;j++){
            cin>>a[i][j];
            vis[i][j]=0;
        }
    }
    ll n; cin>>n;
    for(ll i=0;i<n;i++){
        ll x; cin>>x;
        for(ll i=0;i<3;i++){
            for(ll j=0;j<3;j++){
                if(a[i][j]==x){
                    vis[i][j]=1;
                }
            }
        }
    }
    ll r1=0,r2=0,r3=0,c1=0,c2=0,c3=0,d1=0,d2=0;
    r1+=vis[0][0]+vis[0][1]+vis[0][2];
    r2+=vis[1][0]+vis[1][1]+vis[1][2];
    r3+=vis[2][0]+vis[2][1]+vis[2][2];
    c1+=vis[0][0]+vis[1][0]+vis[2][0];
    c2+=vis[0][1]+vis[1][1]+vis[2][1];
    c3+=vis[0][2]+vis[1][2]+vis[2][2];
    d1+=vis[1][1]+vis[0][0]+vis[2][2];
    d2+=vis[0][2]+vis[1][1]+vis[2][0];
    if(r1==3 ||r2==3 ||r3==3||c1==3||c2==3||c3==3||d1==3||d2==3){
        cout<<"Yes";
    }
    else cout<<"No";
    
    
    return 0;
}


Measured memory_bytes: 256
#include<stdio.h>
int main(void){
  int a,b,kari,i,r;
  long long x;
  scanf("%d %d",&a,&b);
  x=(long long)a*b;
  if(a<b){
    kari=a;
  a=b;
  b=kari;
  }
r=a%b;
  while(r!=0){
    a=b;
    b=r;
    r=a%b;
  }   
     printf("%lld\n",x/b);
     return 0;
}
  

Measured memory_bytes: 128
#include "bits/stdc++.h"
using ll = long long;
using namespace std;


int sod(int x) {
   int ans = 0;
   while(x) {
      ans += (x % 10);
      x /= 10;
   }
   return ans;
}


void solve() {
   int n, a, b;
   cin >> n >> a >> b;

   int ans = 0;
   for(int i = 0; i < n; i++) {
      if(sod(i + 1) >= a && sod(i + 1) <= b) {
         ans += i + 1;
      }
   }
   cout << ans << endl;
}

int main() {
   cin.tie(0);
   cin.sync_with_stdio(0);
   int testcase = 1;
   // cin >> testcase;
 
   for(int i = 0; i < testcase; i++) {
      solve();
   } 
   return 0;
}


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

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, a, b) for(int i=(a); i<(b); ++i)
#define FORR(i, a, b) for(int i=(b)-1; i>=(a); --i)

#define DEBUG(x) cout<<#x<<": "<<(x)<<'\n'
#define DEBUG_VEC(v) cout<<#v<<":";REP(i, v.size())cout<<' '<<v[i];cout<<'\n'
#define ALL(a) (a).begin(), (a).end()

template<typename T> inline void CHMAX(T& a, const T b) {if(a<b) a=b;}
template<typename T> inline void CHMIN(T& a, const T b) {if(a>b) a=b;}

constexpr ll MOD=1000000007ll;
// constexpr ll MOD=998244353ll;
#define FIX(a) ((a)%MOD+MOD)%MOD

const double EPS=1e-11;
#define EQ0(x) (abs((x))<EPS)
#define EQ(a, b) (abs((a)-(b))<EPS)

vi g[125252];
int dp[125252][20];

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  // cout<<setprecision(10)<<fixed;
  int n, m, Q, a, b, v[125252], d[125252], c[125252];
  cin>>n>>m;
  REP(i, m){
    cin>>a>>b;
    --a;--b;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  cin>>Q;
  REP(i, Q){
    cin>>v[i]>>d[i]>>c[i];
    --v[i];
  }
  FORR(i, 0, Q){
    // 頂点、距離、色
    queue<pii> q;
    q.emplace(v[i], d[i]);
    while(q.size()){
      auto x=q.front();
      q.pop();
      int vv=x.first, dd=x.second;
      if(dp[vv][dd]) continue;
      dp[vv][dd]=c[i];
      FORR(j, 0, dd){
        if(dp[vv][j]) break;
        dp[vv][j]=c[i];
      }
      if(!dd) continue;
      for(auto y : g[vv]){
        q.emplace(y, dd-1);
      }
    }
  }
  // REP(i, n){
  //   REP(j, 3){
  //     cout<<dp[i][j]<<" \n"[j==1];
  //   }
  // }
  REP(i, n){
    cout<<dp[i][0]<<'\n';
  }
  return 0;
}


Measured memory_bytes: 18588
#include <bits/stdc++.h>   
#define rep(i, n) for(long long int i = 0; i < n; i++)
#define _rep(i, m, n) for(long long int i = m; i < n; i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll mod = 1000000007;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
string Yes[2] = {"Yes", "No"};
     
ll gcd(ll A, ll B){
    if(B == 0)return A;
    return gcd(B, A % B);
}
ll lcm(ll A, ll B){
    return A * B / gcd(A, B);
}

using Graph = vector<vector<int>>;
Graph G;

/*------------------------------------------------------------------*/

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

    string s;cin >> s;
    if(s[s.size() - 1] == 's') cout << s + "es" << endl;
    else cout << s + "s" << endl;
}


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

using namespace std;

const int INF = 2e9 + 9;
const long long MOD = 998244353;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int n, m;
    string s;
    cin >> n >> s >> m;
    vector<set<int>> a('z'-'a'+1);
    for (int i = 0; i < n; i++) {
        a[s[i] - 'a'].insert(i);
    }
    for (int qi = 0; qi < m; qi++) {
        int op;
        cin >> op;
        if (op == 1) {
            int i;
            char ch;
            cin >> i >> ch;
            i--;
            a[s[i] - 'a'].erase(i);
            s[i] = ch;
            a[ch - 'a'].insert(i);
        } else {
            int l, r;
            cin >> l >> r;
            l--; r--;
            int res = 0;
            for (auto &st: a) {
                auto it = st.lower_bound(l);
                if (it != st.end() && *it <= r) {
                    res++;
                }
            }
            cout << res << "\n";
        }
    }
}



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

using namespace std;

using ll = long long;

template<int MOD>
struct ModInt {
   using Mint = ModInt;
   int val;
   ModInt(ll __val = 0) { fix(__val % MOD + MOD); }
   Mint& fix(int __val) { val = __val; if (val >= MOD) val -= MOD; return *this; }
   explicit operator int() { return val; }
   Mint operator + (const Mint &mt) const { return Mint().fix(val + mt.val); }
   Mint operator - (const Mint &mt) const { return Mint().fix(val - mt.val + MOD); }
   Mint operator * (const Mint &mt) const { return Mint().fix(ll(val) * mt.val % MOD + MOD); }
   Mint& operator += (const Mint &mt) { return *this = *this + mt; }
   Mint& operator -= (const Mint &mt) { return *this = *this - mt; }
   Mint& operator *= (const Mint &mt) { return *this = *this * mt; }
   Mint pow(int y) const {
      Mint x = *this;
      Mint ans(1);
      for (; y > 0; y >>= 1, x *= x) {
         if (y & 1) ans *= x;
      }
      return ans;
   }
   Mint operator -() const { return Mint().fix(MOD - val); }
   Mint inv() const { return pow(MOD - 2); }
   Mint operator / (const Mint &mt) const { return *this * mt.inv(); }
   Mint& operator /= (const Mint &mt) const { return *this / mt; }
   friend ostream& operator<<(ostream& os, const Mint& mt) { return os << mt.val; }
};

using Mint = ModInt<1000000007>;

const int MAXN = 1000100;

Mint fact[MAXN], ifact[MAXN];

void precalc() {
   fact[0] = 1;
   for (int i = 1; i < MAXN; ++i) fact[i] = fact[i - 1] * i;
   ifact[MAXN - 1] = fact[MAXN - 1].inv();
   for (int i = MAXN - 1; i > 0; --i) ifact[i - 1] = ifact[i] * i;
}

Mint C(int N, int K) {
   if (K < 0 || N < K) return 0;
   return fact[N] * ifact[K] * ifact[N - K];
}

Mint ways(int N, int M, int R, int val) {
   Mint ans = 0;
   for (int z = 0; z <= M; ++z) {
      int curR = R - z * val;
      if (curR < 0) break;
      Mint cur = C(M, z) * C(N + curR, N);
      if (z & 1) ans -= cur;
      else ans += cur;
   }
   return ans;
}

Mint solve(int N, int M, int R) {
   Mint ans = C(N + R, N);
   for (int val = 1; val <= R; ++val) {
      int curR = R - M * val;
      if (curR < 0) break;
      ans -= C(N, M) * (ways(N, N - M, curR, val) - ways(N, N - M, curR - M, val));
   }
   return ans;
}

int main() {
   ios_base::sync_with_stdio(false); cin.tie(nullptr);
   precalc();
   int N, M, L, R;
   cin >> N >> M >> L >> R;
   cout << solve(N, M, R) - solve(N, M, L - 1) << "\n";
}


Measured memory_bytes: 8064
# bit全探索
N = int(input())
F = [list(map(int,input().split())) for _ in range(N)]
P = [list(map(int,input().split())) for _ in range(N)]
ans = -float('inf')
for i in range(2**10):
    if i == 0: # 全く営業しないパターン
        continue
    profit = 0
    pattern = [0]*10
    for j in range(10):
        if 1 << j & i:
            pattern[j] = 1
    #print(pattern)

    for k in range(N):
        l = sum([pattern[m] == F[k][m] == 1 for m in range(10)])
        # l = 0
        # for m in range(10):
        #     if pattern[m] == F[k][m] == 1:
        #         l += 1

        #print(l)
        profit += P[k][l]
    ans = max(ans,profit)
print(ans)





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

int main() {

	int n; cin >> n;
	map<string, int> mp;
	for (int i = 0; i < n; i++) {
		string s; cin >> s;
		mp[s]++;
	}
	int m; cin >> m;
	for (int i = 0; i < m; i++) {
		string t; cin >> t;
		mp[t]--;
	}
	int ans = 0;
	for (auto u : mp) {
		ans = max(ans, u.second);
	}
	cout << max(0, ans) << endl;
	return 0;	
}

Measured memory_bytes: 256
<?php
$input=explode(' ',trim(fgets(STDIN)));
//trim = 空白文字を取り除く
//fgets = ファイルから一行取り除く
//STDIN = input streamみたいなもので標準入力（standard input）とも言われます。
if(($input[0] * $input[1])%2 == 0){
    echo "Even";
}else{
    echo 'Odd';
}
?>

Measured memory_bytes: 4728
d['ZZ'],W,N,w,c,j,a;main(t){for(;scanf("%d%d",&W,&N),W;printf("Case %d:\n%d\n%d\n",t++,d[W],a))for(bzero(d,W*5);N--;)for(j=W+scanf("%d,%d",&c,&w);j-->w;)d[j]=fmax(d[j],d[j-w]+c),a=d[j]-d[W]?a:j;}

Measured memory_bytes: 0
n,k=map(int,input().split())
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)

# nCr mod m
# modinvが必要
# rがn/2に近いと非常に重くなる
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res

for i in range(1,k+1):
    if n-k+1>=i:
        ans=(combination(n-k+1, i, mod=10**9+7))*(combination(k-1, i-1, mod=10**9+7))
    else:
        ans=0
    print(ans%(10**9+7))

Measured memory_bytes: 44636
#include <iostream>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <map>
#include <algorithm>
#include <math.h>
#include <cassert>
#define rep(i,n) for(int i = 0; i < n; ++i )
using namespace std;
using ll = unsigned long long;
using P = pair<ll,ll>;

int main() {
  int t;
  cin >> t;
  rep(_,t){
    ll n,a,b,c,x0;
    cin >> n >> a >> b >> c >> x0;
    P x[] = {P(2,a),P(3,b),P(5,c)};
    if(n==1){
      cout << x0 << endl;
      continue;
    }
    queue<P> q; map<ll,ll> ans;
    auto push = [&](ll ni, ll v){
      if(ans.count(ni)>0 && ans[ni]<=v) return;
      ans[ni] = v;
      if(ni==0) return;
      q.emplace(ni,v);
    };
    push(n,0);
    while(!q.empty()){
      P p = q.front(); q.pop();
      ll ni = p.first, v = p.second;
      push(0,v+ni*x0);
      rep(i,3){
        ll p = x[i].first, xi = x[i].second;
        ll m = ni%p;
        if(m==0){
          push(ni/p,v+xi);
        }else{
          push(ni/p,v+xi+x0*m);
          push(ni/p+1,v+xi+x0*(p-m));
        }
      }
    }
    cout << ans[0] << endl;
  }
}

Measured memory_bytes: 4480
#include <iostream>
#include <string>
#include <stdio.h>
#include <numeric>
#include <algorithm>
using namespace std;
int main(){
    int a=0,b=0;
    for(int i=0;i<4;++i){
        int n;
        cin>>n;
        a+=n;
    }
    for(int i=0;i<4;++i){
        int n;
        cin>>n;
        b+=n;
    }
    if(a>b){
        cout<<a<<endl;
    }
    else{
        cout<<b<<endl;
    }
    return 0;
}


Measured memory_bytes: 3084
#pragma GCC optimize("O3")
#include<bits/stdc++.h> 
using namespace std;
using ll=long long;
typedef pair<ll,ll> P;
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
const ll inf=(1e18);
const ll mod=1000000007;
//ios_base::sync_with_stdio(false);
//cin.tie(NULL);
ll gcd(ll a,ll b) {return b ? gcd(b,a%b):a;}
struct __INIT{__INIT(){cin.tie(0);ios::sync_with_stdio(false);cout<<fixed<<setprecision(15);}} __init;
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 (a>b) { a=b; return 1; } return 0; }
template<typename G>
struct DLCA{
    const int Log;
    vector<int> dep;
    const G &g;
    vector<vector<int>> table;
    explicit DLCA(const G &g):g(g),dep(g.size()),Log(32-__builtin_clz(g.size())){
        table.assign(Log,vector<int>(g.size(),-1));
    }
    void dfs(int idx,int par,int d){
        table[0][idx]=par;
        dep[idx]=d;
        for(auto &to:g[idx]){
            if(to!=par)dfs(to,idx,d+1);
        }
    }
    void build(){
        dfs(0,-1,0);
        for(int k=0;k<Log-1;k++){
           for(int i=0;i<table[k].size();i++){
               if(table[k][i]==-1)table[k+1][i]=-1;
               else table[k+1][i]=table[k][table[k][i]];
           }
        }
    }
    int query(int u,int v){
       if(dep[u]>dep[v])swap(u,v);
       for(int i=Log-1;i>=0;i--){
           if(dep[v]-dep[u]&(1<<i))v=table[i][v];
       }
       if(u==v)return u;
       for(int i=Log-1;i>=0;i--){
           if(table[i][u]!=table[i][v]){
               u=table[i][u];
               v=table[i][v];
           }
       }
       return table[0][u];
    }
};
int main(){
    int n;
    cin>>n;
    vector<vector<int>> graph(n);
    for(int i=0;i<n;i++){
        int t;cin>>t;
        for(int j=0;j<t;j++){
            int v;cin>>v;
            graph[i].push_back(v);
        }
    }
   DLCA<vector<vector<int>>>lca(graph);
    lca.build();
    int q;cin>>q;
    while(q--){
        int x,y;
        cin>>x>>y;
        cout<<lca.query(x,y)<<endl;
    }

}



Measured memory_bytes: 18424
n, m = [int(x) for x in input().split()]
img_a = [input() for _ in range(n)]
img_b = [input() for _ in range(m)]

ans = "No"
for a in range(n - m + 1):
    border = 0
    isok = True
    while isok:
        for b in range(m):
            if img_b[b] in img_a[b+a][border:]:
                if b == 0:
                    index = img_a[a].index(img_b[0], border)
                current_index = img_a[b+a].index(img_b[b], border)
                if current_index == index:
                    continue
                elif current_index > index:
                    border = current_index
                    break
                else:
                    border = index
                    break
            else:   # if not substring in string.
                isok = False
                break

        else: # if not loop broken.
            ans = "Yes"
            break
        
print(ans)


Measured memory_bytes: 3064
#![allow(clippy::needless_range_loop)]
#![allow(unused_macros)]
#![allow(dead_code)]
#![allow(unused_imports)]

use itertools::Itertools;
use proconio::input;
use proconio::marker::*;

fn main() {
    input! {
        n: usize,
        k: usize,
        p: [usize; n]
    }
    let cum: Vec<_> = std::iter::once(0)
        .chain(p.iter().scan(0, |acc, x| {
            *acc += x;
            Some(*acc)
        }))
        .collect();
    let sum = cum
        .iter()
        .zip(cum[k..].iter())
        .map(|(x, y)| y - x)
        .max()
        .unwrap();
    println!("{}", (sum + k) as f64 / 2.0);
}


Measured memory_bytes: 6304
from queue import Queue

k = int(input())
q = Queue()
for i in range(1, 10):
    q.put(i)
for i in range(k):
    x = q.get()
    if x % 10 != 0:
        num = 10 * x + (x % 10) - 1
        q.put(num)
    num = 10 * x + (x % 10)
    q.put(num)
    if x % 10 != 9:
        num = 10 * x + (x % 10) + 1
        q.put(num)
print(x)

Measured memory_bytes: 18884
n = int(input())
hight_list = list(map(int, input().split()))
sum_step = 0
max_hight = 0

for i in range(n):
    if hight_list[i] < max_hight:
        
        sum_step += max_hight - hight_list[i] 
    else:
        max_hight = hight_list[i]

print(sum_step)

Measured memory_bytes: 32208