akhauriyash/Code-Regression huggingface dataset:
#include<iostream>
#include<algorithm>
#include<climits>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define scan(arg) cin>>arg
#define prin(arg) cout<<arg<<"\n"
#define prin2(arg1,arg2) cout<<arg1<<" "<<arg2<<"\n"
using namespace std;
typedef long long ll;
const int NMAX=1<<17;
int n,m;
int x[100010],y[100010];
int dp[100010];
vector<int> g[100010];
int rec(int i){
  if(dp[i]>=0) return dp[i];
  int res=0;
  rep(j,g[i].size()){
    res=max(res,rec(g[i][j])+1);
  }
  return dp[i]=res;
}
int main(){
  scan(n);scan(m);
  rep(i,m){
    scan(x[i]);scan(y[i]);
  }
  memset(dp,-1,sizeof(dp));
  rep(i,m){
    g[x[i]].push_back(y[i]);
  }
  int ans=0;
  rep1(i,n){
    ans=max(ans,rec(i));
  }
  prin(ans);
  
  
  

  return 0;
}


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

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

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

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

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

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

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

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

    ($next:expr, bytes) => {
        read_value!($next, String).into_bytes()
    };

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

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

fn main() {
    input! {
        n: usize,
        a: [i64; n],
    }
    let mut result = std::i64::MAX;
    let length : i64 = a.iter().sum();
    let mut left = 0;
    for i in 0..n {
        left += a[i];
        let right = length - left;
        if (left - right).abs() < result {
            result = (left - right).abs();
        }
    }
    println!("{}", result);
}


Measured memory_bytes: 6396
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <functional>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>
using namespace std;

typedef long long ll;
typedef pair<int, int> Pair;

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

// Self settings
// clang-format off
#define MAX_N 100000
#define REP(i, N) for (int i = 0; i < (int)(N); ++i)
#define SLN(i,N) (i == N-1 ? "\n" : " ")
ll fact(ll n) { ll res = 1; for(ll i=2;i<=n;++i) res = res * i; return res;}
ll nCr(ll n, ll r) {return (fact(n)/fact(n-r)*fact(r)) ;}
ll gcd(ll a,ll b){if(b==0)return a;return gcd(b,a%b);}
ll lcm(ll a,ll b){return a/gcd(a,b)*b;}
const ll MOD = 1e9+7;
const ll INF = 1LL << 60;
const int inf = 1000100011;
// clang-format on
int N, M;
int T[MAX_N], P[MAX_N], X[MAX_N];

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cin >> N;
  REP(i, N) cin >> T[i];
  cin >> M;
  REP(i, M) cin >> P[i] >> X[i];

  REP(j, M) {
    int ans = 0;
    REP(i, N) {
      if (i + 1 == P[j]) {
        ans += X[j];
      } else {
        ans += T[i];
      }
    }
    cout << ans << endl;
  }

  return 0;
}


Measured memory_bytes: 256
let split_on_char sep s =
  let open String in
  let r = ref [] in
  let j = ref (length s) in
  for i = length s - 1 downto 0 do
    if get s i = sep then begin
      r := sub s (i + 1) (!j - i - 1) :: !r;
      j := i
    end
  done;
  sub s 0 !j :: !r

let dfs vs n =
  let d = Array.make n (-1) in
  let rec doit i id =
    d.(i) <- id;
    List.iter (fun v -> if d.(v) = (-1) then doit v id) vs.(i) in
  Array.iteri (fun i e -> if e = (-1) then doit i i) d;
  d

let read_ns () =
  match read_line () |> split_on_char ' ' |> List.map int_of_string with
  | [x; y] -> (x, y)
  | _ -> assert false

let () =
  let (n, m) = read_ns () in
  let vs = Array.make n [] in
  for _ = 0 to m - 1 do
    let (s, t) = read_ns () in
    vs.(s) <- t :: vs.(s);
    vs.(t) <- s :: vs.(t);
  done;
  let d = dfs vs n in
  let q = read_int () in
  for _ = 0 to q - 1 do
    let (s, t) = read_ns () in
    Printf.printf (if d.(s) = d.(t) then "yes\n" else "no\n")
  done

Measured memory_bytes: 18736
import java.util.*;

class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int ans = 0;

        Integer n = sc.nextInt();
        Integer a[] = new Integer[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        Arrays.sort(a, Comparator.reverseOrder());

        int alice = 0, bob = 0;
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0)
                alice += a[i];
            else
                bob += a[i];
        }

        System.out.println(alice - bob);
        sc.close();
    }
}


Measured memory_bytes: 25172
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int main() {
  int n,a[100],cnt=0,b=1000,c_nt=0;
  cin >> n;
  for(int i=0; i<n; i++) {
    cin >> a[i];
    cnt+=a[i];
    if(a[i]%10==0) {
      c_nt++;
    }
    if(a[i]%10!=0) {
      b=min(b,a[i]);
    }
  }
  if(c_nt==n) {
    cout << 0 << endl;
    return 0;
  }
  if(cnt%10!=0) {
    cout << cnt << endl;
  }
  else {
    cout << cnt-b << endl;
  }
}


Measured memory_bytes: 256
#!ruby -narprime
A=$F.map &:to_i
d=A.tally
print Prime.each(1e6).all?{|b|a=((b..10**6)%b).sum{d[_1]||0}<2}?:pairwise:A.reduce(:gcd)<2?:setwise: :not,' coprime'if/ /

Measured memory_bytes: 135028
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define all(v) v.begin(), v.end()
#define sz(v) v.size()
#define INF 100000000000000 //10^14
template <typename T>
bool chmax(T &a, const T& b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &a, const T& b) {
  if (a > b) {
    a = b;
    return true;
  }
  return false;
}
int main()
{
    string s;
    cin >> s;
    rep(i, sz(s)-1){
        if(s.at(i) == s.at(i+1)){
            cout << i+1 << " " << i+2 << endl;
            return 0;
        }
    }
    rep(i, sz(s)-2){
        if(s.at(i) == s.at(i+2)){
            cout << i+1 << " " << i+3 << endl;
            return 0;
        }
    }
    cout << -1 << " " << -1 << endl;
}

Measured memory_bytes: 3772
#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
typedef  long long ll;
using namespace std;
int main(){   
   int n;
   cin>>n;
   vector<int> a(n);
   int flag=1;
   rep(i,n){
      cin>>a[i];
   }
   sort(a.begin(),a.end());
   rep(i,n-1){
      if(a[i]==a[i+1]) flag=0;
   }
   flag==1? cout<<"YES":cout<<"NO";
   
   return 0;
}

Measured memory_bytes: 1024
from bisect import bisect_left,bisect

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

def is_ok(arg):
  L = bisect(A, arg)
  cnt = 0
  for i in range(L, N):
    p, q = divmod(A[i], arg)
    if q == 0:
      cnt += p-1
    else:
      cnt += p
  return cnt <= K

ng = 0
ok = max(A) + 1

def m_bisect(ng, ok):
  while (abs(ok - ng) > 1):
    mid = (ok + ng) // 2
    if is_ok(mid):
      ok = mid
    else:
      ng = mid
  return ok

print(m_bisect(ng, ok))

Measured memory_bytes: 31108
#include <iostream>
#include <stdio.h>

using namespace std;

int main(){
    int a,b;
    int d,r;
    double f;
    
    cin >> a >> b;
    
    d = a / b;
    r = a % b;
    f = a * 1.0 / b;
    
    printf("%d %d %6f",d,r,f);
    
    return 0;
}


Measured memory_bytes: 3216
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define space ' '
typedef long long ll;
typedef long double ld;
const long double PI = 3.14159265358979323846;

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

	ll n;
	cin >> n;
	ll ans = 0;
	while (n > 0) {
        ans += n;
        --n;
	}
	cout << ans << endl;

    return 0;
}


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

bool f[150];
string depname[150];//グループ名
vector<string> member[150];//所属しているメンバ名

vector<string> saiki(int now,int n)
{
	vector<string> ret;
	f[now]=true;
	for(int i=0;i<member[now].size();i++)
	{
		int ind=-1;
		//グループ名を全探索
		for(int j=0;j<n;j++)
		{
			if(now!=j && depname[j]==member[now][i])
				ind=j;
		}
		if(ind==-1)
			ret.push_back(member[now][i]);
		else if(!f[ind]){
			vector<string> ketu=saiki(ind,n);
			for(int j=0;j<ketu.size();j++)
				ret.push_back(ketu[j]);
		}
	}
	return ret;
}

int main()
{
	while(1)
	{
		int n;
		string s[150];
		for(int i=0;i<150;i++)
			member[i].clear();
		vector<string> ans;
		fill(f,f+150,false);
		cin>>n;
		if(n==0)
			break;
		for(int i=0;i<n;i++)
			cin>>s[i];
		
		//depnameとmemberを求める
		for(int i=0;i<n;i++)
		{
			string tmp;
			int j=0;
			while(s[i][j]!=':')
			{
				tmp+=s[i][j];
				j++;
			}
			depname[i]=tmp;
			j++;
			while(j<s[i].size())
			{
				tmp="";
				while(s[i][j]!=',' && s[i][j]!='.')
				{
					tmp+=s[i][j];
					j++;
				}
				member[i].push_back(tmp);
				j++;
			}
		}
		
		//ここから処理
		//再帰でメンバ一覧を得る
		ans=saiki(0,n);
		sort(ans.begin(),ans.end());
		auto res=unique(ans.begin(),ans.end());
		ans.erase(res,ans.end());
		/*
		for(int i=0;i<ans.size();i++)
			cerr<<ans[i]<<endl;
			*/
		cout<<ans.size()<<endl;
	}
	return 0;
}


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

int main() {
	int n, i, m, a[111],sum=0,count=0;
	cin >> n >> m;
	for (i = 0; i < n;i++){
		cin >> a[i];
		sum += a[i];
	}
	for (i = 0; i < n;i++)
		if(a[i]*4*m>=sum)
			count++;
	if(count>=m)
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}

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

using namespace std;

#define fst(t) std::get<0>(t)
#define snd(t) std::get<1>(t)
#define thd(t) std::get<2>(t)
#define unless(p) if(!(p))
#define until(p) while(!(p))

using ll = long long;
using P = std::tuple<int,int>;

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

int N, Q, S, T;
ll A[200100], B[200100];

ll contribution(int i){
    if(B[i] > 0){
        return -(B[i] * S);
    }
    return (-B[i]) * T;
}

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

    std::cin >> N >> Q >> S >> T;

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

    ll t = 0;
    for(int i=1;i<=N;++i){
        B[i] = A[i] - A[i-1];
        t += contribution(i);
    }

    for(int i=0;i<Q;++i){
        int l, r, x;
        std::cin >> l >> r >> x;

        t -= contribution(l);        
        B[l] += x;
        t += contribution(l);

        if(r + 1 <= N){
            t -= contribution(r + 1);
            B[r+1] -= x;
            t += contribution(r + 1);
        }

        std::cout << t << std::endl;
    }
}



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

typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
//const ull mod = 1e9 + 7;
const ll mod = 1e9 + 7;
#define REP(i,n) for(int i=0;i<(int)n;++i)

// debug
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define debug(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << " " << __FILE__ << endl;

template<class S, class T> ostream& operator << (ostream& os, const pair<S, T> v){
  os << "(" << v.first << ", " << v.second << ")"; return os;
}
template<class T> ostream& operator << (ostream& os, const vector<T> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << " ";} os << v[i];} return os;
}
template<class T> ostream& operator << (ostream& os, const vector<vector<T>> v){
  for(int i = 0; i < (int)v.size(); i++){if(i > 0){os << endl;} os << v[i];} return os;
}
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; }

// conversion number to bit
string num2bit(ll num, ll len){
  string bit = "";
  REP(i, len){
    bit += char('0'+(num>>i & 1));
  }
  return bit;
}

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

    ll A, B, M;
    cin >> A >> B >> M;
    vector<ll> a(A), b(B);
    REP(i, A) cin >> a[i];
    REP(i, B) cin >> b[i];
    vector<ll> x(M), y(M), c(M);
    REP(i, M){
    	cin >> x[i] >> y[i] >> c[i];
    	x[i]--;
    	y[i]--;
    }

    ll res = (1ll<<60);
    REP(i, M){
    	chmin(res, a[x[i]]+b[y[i]]-c[i]);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    chmin(res, a[0]+b[0]);
    cout << res << endl;
    return 0;
}

Measured memory_bytes: 4224
#include <stdio.h>
#include <math.h>

int isPrime(int n);

int main(){
  int i, n, m = 0,l = 0;
    scanf("%d", &n);
    l = n;
    for(i = 0; i < l; i++){scanf("%d", &n);
    if (isPrime(n)) {
      m += 1;
    } else {
      m += 0;
    }
    }
    printf("%d\n", m);
    return 0;
}

int isPrime(int n){
  
  if(n == 2)return 1;
  else if(n < 2 || n%2 == 0)return 0;
  
  int i = 3;
  double j;
  j = sqrt(n);

  while(i <= j){
  if (n % i == 0)return 0;
  else i = i+2;}
  return 1;
}







Measured memory_bytes: 2048
#include <cstdio>

int
main(void)
{
  int a, b;
  scanf("%d %d", &a, &b);

  if (a < b) {
    printf("a < b\n");
  } else if (a > b) {
    printf("a > b\n");
  } else {
    printf("a == b\n");
  }

  return 0;
}



Measured memory_bytes: 2652
f=lambda:map(int,input().split())
_,m=f()
d,t,c={},0,0
for p,y,i in sorted(list(f())+[i] for i in range(m)):
  if p>t: t,c=p,1
  else: c+=1
  d[i]=str(p).zfill(6)+str(c).zfill(6)
for _,v in sorted(d.items()): print(v)

Measured memory_bytes: 38088
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;

constexpr ll mod=1e9+7;

ll f[1000100];
ll fac[1000100];

ll mod_pow(ll a,ll b){
    a%=mod;
    if(b==0)return 1;
    if(b==1)return a;
    ll res=mod_pow(a,b/2)%mod;
    res*=res; res%=mod;
    if(b%2)res*=a;
    return res%mod;
}

struct perm{
private:
    int sz;
    vector<ll> p,invp;
public:
    perm(int n){
        sz=n+1;
        p.resize(sz),invp.resize(sz);
        p[0]=1;
        for(int i=1;i<=sz-1;i++){
            p[i]=p[i-1]*i%mod;
        }
        invp[sz-1]=mod_pow(p[sz-1],mod-2);
        for(int i=sz-2;i>=0;i--){
            invp[i]=invp[i+1]*(i+1)%mod;
        }
    }
    ll comb(ll x,ll y){
        if(x<y||y<0)return 0;
        return (p[x]*invp[x-y]%mod)*invp[y]%mod;
    }
};
perm p(1<<20);


int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll res=0;
    ll n; cin >> n;
    fac[0]=1;
    for(ll i=1;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
    }
    for(ll k=1;k<n;k++){
        f[k]=p.comb(k-1,n-1-k)*fac[k]%mod*fac[n-1-k]%mod;
    }
    for(ll k=1;k<n;k++){
        (res+=k*(f[k]-f[k-1])%mod)%=mod;
    }
    if(res<0)res+=mod;
    cout << res << endl;
}


Measured memory_bytes: 35116
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i = 0; i < (n); i++)
using ll = long long;
using ull = unsigned long long;
using P = pair<int,int>;
using PP = pair<int,pair<int,int>>;
using T = tuple<string,int,int>;
const string EMP = " ";
const ll INF = 1LL<<60;
const ll MOD = 1000000007;

int main(){
  int n,m; ull k;
  cin >> n >> m >> k;

  vector<ull> a(n+1,0),b(m+1,0);
  for(int i = 0; i < n; i++){
    ull aa; cin >> aa;
    a[i+1] = aa + a[i];
  }
  for(int i = 0; i < m; i++){
    ull bb; cin >> bb;
    b[i+1] = bb + b[i];
  }
  int ans = 0, j = m;
  for(int i = 0; i <= n; i++){
    if(a[i] > k) break;
    while(a[i] + b[j] > k) j--;
    ans = max(ans, i+j);
  }
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 6432
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int a();
void b();
int c[1000],top=0;
 
int main() {
 
  int d,e;
  char s[100];
 
  while(scanf("%s",s)!=EOF) {
    if(s[0]=='+') {
      d = a();
      e = a();
      b(d+e);
    }
    else if(s[0]=='*') {
      d = a();
      e = a();
      b(d*e);
    }
    else if(s[0]=='-') {
      d = a();
      e = a();
      b(e-d);
    }
    else b(atoi(s));
  }
  printf("%d\n",a());
 
  return 0;
}
 
int a() {
  top--;
  return c[top+1];
}
 
void b(int x) {
  c[++top] = x;
}

Measured memory_bytes: 548
import java.util.Scanner;

class Main{

	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int S = sc.nextInt();
		int h = 0;
		int m = 0;
		int s = 0;

		s = S%60;
		m = S/60;

		h = m/60;
		m = m%60;
		// String input = sc.nextLine();
	  // String nums[] = input.split(" ");

	  // long A = Long.parseLong(nums[0]);
	  // long B = Long.parseLong(nums[1]);
	  // long sum = Long.parseLong(nums[2]);

		System.out.println(h + ":" + m + ":" + s);
		// System.out.println(S.toString());

	}
}



Measured memory_bytes: 26232
#include<iostream>
using namespace std;
char a[101][101];
bool dn[101];
bool dn1[101];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
		cin>>a[i][j];
		if(a[i][j]=='#') {
			dn[i]=true;
			dn1[j]=true;
		  } 	
		}
	}
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			if(dn[i]&&dn1[j]){
				cout<<a[i][j];
			}
		}
		cout<<endl;
	}
}

Measured memory_bytes: 256
#include <cstdio>
#include <stack>
#include <iostream>
using namespace std;
int main()
{
    int n;
    while(scanf("%d",&n)!=EOF)
    {
        int a=0,b=0,m=n;
        for(int i=0;i<n;i++)
        {
            int x;
            scanf("%d",&x);
            if(x%4==0) b++;
            else
                if(x%2==0) a++;
        }
        if(a>1) m=n-a+1;
        if(n==1) printf("%s\n",(b>=n)?"Yes":"No");
        else printf("%s\n",(b>=m/2)?"Yes":"No");
    }
    return 0;
}


Measured memory_bytes: 256
#include "bits/stdc++.h"
 
#define ALL(g) (g).begin(),(g).end()
#define REP(i, x, n) for(int i = x; i < n; i++)
#define rep(i,n) REP(i,0,n)
#define RREP(i, x, n) for(int i = x; i >= n; i--)
#define rrep(i, n) RREP(i,n,0)
#define pb push_back
 
using namespace std;
 
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,int>;
 
const int mod=1e9+7,INF=1<<30;
const double EPS=1e-12,PI=3.1415926535897932384626;
const ll lmod = 1e9+7,LINF=1LL<<60;
const int MAX_N = 1003;
 
int main(){
  ll N; cin >> N;
  map<ll,ll> mp;
  mp[0] = 1LL; mp[1] = 2LL;
  function<ll(ll)> solve = [&](ll n){
    if(mp.count(n)) return mp[n];
    return mp[n] = (solve(n/2) + solve((n-1)/2) + solve(n/2-1)) % lmod;
  };
  cout << solve(N) << endl;
  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define int long long
#define ALL(v) (v).begin(),(v).end()
#define Vi vector<int>
#define pb push_back
#define rep(i,a,b) for(int i=a;i<b;i++)
#define repr(i,a,b) for(int i=a;i>b;i--)
#define leng(n) (int)(log10(n)+1)
#define INF 9000000000000000000
using namespace std;

int gcd(int a,int b){return b?gcd(b,a%b):a;}  //  最大公約数gcd
int lcm(int a,int b){return a/gcd(a,b)*b;}  //  最小公倍数lcm

signed main() {
  int n,a,b,c,d,e;
  cin >> n >> a >> b >> c >> d >> e;
  cout << 5 + (n-1)/(min({a,b,c,d,e})) << endl;
}


Measured memory_bytes: 256
import java.io.IOException;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.util.ArrayList;

public class Main {
    private static final StringBuilder builder = new StringBuilder();
    public static void main(String[] args) {
        read();
        String s = builder.toString();
        read();
        String t = builder.toString();

        int min = t.length();
        for (int i = 0; i <= s.length() - t.length(); i++) {
            String sub = s.substring(i, i + t.length());
            int diff = 0;
            for (int j = 0; j < t.length(); j++) {
                if (sub.charAt(j) != t.charAt(j)) diff++;
                if (diff > min) break;
            }

            if (diff < min) min = diff;
            if (min == 0) break;
        }

        System.out.print(min);
    }

    private static void read() {
        builder.setLength(0);
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) {
                    break;
                } else {
                    builder.appendCodePoint(b);
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static int readInt() {
        read();
        return Integer.parseInt(builder.toString());
    }

    private static int readInt(int radix) {
        read();
        return Integer.parseInt(builder.toString(), radix);
    }

    private static long readLong() {
        read();
        return Long.parseLong(builder.toString());
    }

    private static long readLong(int radix) {
        read();
        return Long.parseLong(builder.toString(), radix);
    }

    private static BigInteger readBigInteger() {
        read();
        return new BigInteger(builder.toString());
    }

    private static BigInteger readBigInteger(int radix) {
        read();
        return new BigInteger(builder.toString(), radix);
    }

    private static double readDouble() {
        read();
        return Double.parseDouble(builder.toString());
    }

    private static BigDecimal readBigDecimal() {
        read();
        return new BigDecimal(builder.toString());
    }

    private static float readFloat() {
        read();
        return Float.parseFloat(builder.toString());
    }

    private static void skipLine() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == '\n' || b == -1) {
                    break;
                }
            } catch (IOException e) {
                break;
            }
        }
    }

    private static void skip() {
        while (true) {
            try {
                int b = System.in.read();
                if (b == ' ' || b == '\n' || b == -1) break;
            } catch (IOException e) {
                break;
            }
        }
    }

}


Measured memory_bytes: 33356
#include <iostream>
#include <cstdio>
#include <iomanip>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip> 
#include <cstring>
#include <queue>
#include <stack> 
#include <vector>
#include <map>
#include <set>
using namespace std;
typedef long long ll;
set<string> st;
int n;
string s;
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	while(n--){
		cin >> s;
		st.insert(s);
	}
	cout << st.size() << endl;
	return 0;
}

Measured memory_bytes: 15708
#include <stdio.h>
#include<iostream>
#include<string>
#include <string.h>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <climits>
#include <map>
using namespace std;
int cnt[1000005],a[1000005];
int gcd(int a,int b)
{
    if(a%b==0) return b;
    return gcd(b,a%b);
}
int main() {
    int n,f1=1;
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        int t=a[i];
        for(int j=2;j*j<=t;j++)
        {
            if(t%j==0)
            {
                while(t%j==0) t/=j;
                cnt[j]++;
                if(cnt[i]>1)
                {
                    f1=0;
                    break;
                }
            }
        }
        if(t>1){
            cnt[t]++;
            if(cnt[t]>1)
            {
                f1=0;
                break;
            }
        }
        if(f1==0) break;
    }
    if(f1){
        cout<<"pairwise coprime"<<endl;
        return 0;
    }
    int now=a[1];
    for(int i=2;i<=n;i++) now=gcd(now,a[i]);
    if(now==1) cout<<"setwise coprime"<<endl;
    else cout<<"not coprime"<<endl;
    return 0;
}

Measured memory_bytes: 7948
#include <cstdio>
#include <cctype>
#include <cassert>
#include <algorithm>
#include <string>
#include <vector>

std::string times(const std::string &s, size_t n) {
  std::string res;
  for (std::string dbl=s; n; n>>=1) {
    if (n & 1) res += dbl;
    dbl += dbl;
  }
  return res;
}

std::string parse(const std::string &s, size_t &i, size_t n) {
  std::string res;
  while (i < s.length()) {
    intmax_t k=1;
    if (isdigit(s[i])) {
      k = s[i]-'0';
      while (++i < s.length() && isdigit(s[i]))
        k = 10*k+s[i]-'0';
    }
    std::string t;
    if (s[i] == '(') {
      t = parse(s, ++i, n);
      assert(s[i] == ')');
      ++i;
    } else if (isupper(s[i])) {
      t = s[i++];
    } else {
      return res;
    }

    if (t.length()*k > n) throw t[n%t.length()];
    n -= t.length()*k;
    res += times(t, k);
  }
  throw '0';
}

int testcase_ends() {
  char buf[128];
  size_t n;
  scanf("%s %zu", buf, &n);
  std::string s=buf;
  if (s == "0" && n == 0) return 1;

  size_t i=0;
  try {
    parse(s, i, n);
    printf("0\n");
  } catch (char c) {
    printf("%c\n", c);
  }
  return 0;
}

int main() {
  while (!testcase_ends()) {}
}



Measured memory_bytes: 5536
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

int main(void)
{
    int n;
    scanf(" %d", &n);
    for(int i = 0; i < n; i++){ // main loop
        int y, m, d;
        scanf(" %d %d %d", &y, &m, &d);
        int count = 0;
        // this year count
        for(int j = m + 1; j <= 10; j++){ // month
            if(y % 3 == 0){
                count += 20;
            } else{
                if(j % 2 == 0){
                    count += 19;
                } else if(j % 2 == 1){
                    count += 20;
                }
            }
         }
        int t = count;
        //printf("month: \t%d\n", count);
        // day
        if(y % 3 == 0){
            count += (20 - d + 1);
        }else{
            if(m % 2 == 0){
                count += (19 - d + 1);
            }else if(m % 2 == 1){
                count += (20 - d + 1);

            }
        }
       // printf("day: \t%d\n", count - t);
        // next year count
        for(int j = y + 1; j < 1000; j++){
            if(j % 3 == 0){
                count += (20 * 10);
            } else if (j % 3 != 0){
                count += (20 * 5 + 19 * 5);
            }

        }
        printf("%d\n", count);
    }

    return 0;
}

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

using namespace std;

int main()
{
	int n;
	cin >> n;
	int key;
	vector<int> seq(n);
	for (int i = 0; i < n; i++)
	{
		cin >> seq[i];
	}
	for (int i = 0; i < n; i++)
	{
		key = seq[i];
		for (int j = i - 1; j >= 0; j--)
		{
			if (seq[j] > key)
			{
				seq[j + 1] = seq[j];
			}
			else
			{
				break;
			}
			seq[j] = key;
		}
		for (int j = 0; j < n; j++)
		{
			cout << seq[j];
			if (j == n - 1)
			{
				cout << endl;
			}
			else
			{
				cout << " ";
			}
		}
	}
}


Measured memory_bytes: 3112
#include <string.h>

#include <algorithm>
#include <iostream>

using namespace std;
using ll = long long;

int main(void) {
  int D, T, S;
  cin >> D >> T >> S;
  float DD, TT, SS;
  DD = (float)D;
  TT = (float)T;
  SS = (float)S;

  if ((DD / SS) > TT) {
    cout << "No" << endl;
  } else {
    cout << "Yes" << endl;
  }
  // cout<<ans<<endl;
  return 0;
}

Measured memory_bytes: 3632
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <ctime>
#include <cassert>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <cassert>
#include <string.h>

using namespace std;

int main()
{
	string s;
	cin >> s;
	int len = s.size();
	
	string res;
	
	for (int i = 0; i<len; i++){
		if (s[i] == '1') res.push_back('1');
		if (s[i] == '0') res.push_back('0');
		if (s[i] == 'B' && !res.empty()) res.pop_back();
	}
		
	int len2 = res.size();
		
	for (int i=0; i<len2; i++) cout << res[i];
	cout << endl;

	return 0;
}



Measured memory_bytes: 256
n = int(input())
s_p_list = []

for i in range(n):
    s_p_list.append(input().split())
    s_p_list[i].append(i+1)

result = sorted(s_p_list, key=lambda x: (x[0], -int(x[1]))) #sortedは非破壊的

for i in result:
  print(i[2])

Measured memory_bytes: 3060
#include "bits/stdc++.h"
#define rep(i,n) for (int i=0; i<(n); ++i)
using namespace std;
using ll =long long;
using P =pair<int,int>;

int main(){
    ll n,k;
    cin >> n >> k;
    vector <vector <ll>> a(n+1,vector <ll> (2,0));
    ll aa;
    rep(i,n){
        cin >> aa;
        if(i==0){
            a[i+1][0]=aa;
        }
        else{
            a[i+1][0]=a[i][0]+aa;
        }
        a[i+1][1]=i+1;
    }
    

    rep(i,n){
        a[i+1][0]-=(i+1);
        a[i+1][0]=a[i+1][0]%k;
        //a2[i+1]=a[i];
        //cout << a[i+1][0] << endl;
    }

    a[0][0]=0;
    a[0][1]=0;

    sort(a.begin(),a.end());

    ll nn=0,now=0;
    ll ans=0;
    ll l=0,r=0;
    int ka=0;


    /*rep(i,n+1){
        cout << a[i][0] << " " << a[i][1] << endl;
    }*/

    
    while(l<n+1){
        while(a[r][0]==a[l][0] and (a[r][1]-a[l][1])<k){
            if(r==n){
                ka=1;
                break;
            }
            ++r;
        }
        if(ka==1){
            ans+=r-l;
        }
        else{
            ans+=r-l-1;
        }
        //cout << l << " " << ans << endl;
        if(a[r][0]!=a[l][0]){
            ans+=(r-l-2)*(r-l-1)/2;
            l=r;
        }
        else{
            ++l;
        }
        //cout << l << " " << ans << endl;

    }


    
    cout << ans << endl;




    

    return 0;
}

Measured memory_bytes: 14352
import java.io.InputStream;
import java.io.PrintStream;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	InputStream in = System.in;
	PrintStream out = System.out;

	void dfs(int w, int h, int[][] c, int x, int y, boolean[][] v) {
		if (v[y][x] || c[y][x] == 0) {
			return;
		}
		v[y][x] = true;

		for (int dx = -1; dx <= 1; dx++) {
			for (int dy = -1; dy <= 1; dy++) {
				if (x + dx >= 0 && x + dx < w && y + dy >= 0 && y + dy < h) {
					dfs(w, h, c, x + dx, y + dy, v);
				}
			}
		}

	}

	void solv(int w, int h, int[][] c) {
		boolean[][] v = new boolean[h][w];

		int ans = 0;
		for (int y = 0; y < h; y++) {
			for (int x = 0; x < w; x++) {
				if (!v[y][x] && c[y][x] == 1) {
					ans++;
					dfs(w, h, c, x, y, v);
				}
			}
		}

		out.println(ans);

	}

	public void _main(String[] args) {
		Scanner sc = new Scanner(in);

		while (true) {

			int w = sc.nextInt();
			int h = sc.nextInt();

			if (w == 0 && h == 0) {
				break;
			}

			int[][] c = new int[h][w];
			for (int i = 0; i < h; i++) {
				for (int j = 0; j < w; j++) {
					c[i][j] = sc.nextInt();
				}
			}

			solv(w, h, c);
		}
		sc.close();
	}

	public static void main(String[] args) {
		new Main()._main(args);
	}
}



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

int main() {
	string A, B;
	cin >> A >> B;
	if(A.size() != B.size()){
		if(A.size() < B.size()){
			cout << "LESS" << endl;
			return 0;
		}
		else{
			cout << "GREATER" << endl;
			return 0;
		}
	}
	else if(A == B){
		cout << "EQUAL" << endl;
		return 0;
	}
	else{
		for(int i = 0;true;i++){
			if(A.at(i) == B.at(i)){
				//やり直しですwwwwwwww
			}
			else{
				if(A.at(i) < B.at(i)){
					cout << "LESS" << endl;
					return 0;
				}
				else{
					cout << "GREATER" << endl;
					return 0;
				}
			}
		}
	}
}

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

using namespace std;

#define rep(i, b, e) for(int (i) = (b); (i) < (e); (i)++)

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

  vector<int> V(N);
  vector<int> C(N);

  rep(i, 0, N) cin >> V[i];
  rep(i, 0, N) cin >> C[i];

  int ans = 0;
  rep(i, 0, N) {
    if ((V[i] - C[i]) > 0) ans += V[i] - C[i];
  }

  cout << ans << endl;

  return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n)  FOR(i,0,n)
#define req(i,n) for(int i = 1;i <=n;i++)
#define pai 3.14159265358979323846
const int INF = 1001001001;
typedef long long ll;
int A[3][3], N;
bool punched[3][3];
bool ok[3][3];
using Graph = vector<vector<int>>;
vector<vector<int>> field;
vector<bool> seen;

const int MOD = 1000000007;
typedef pair<int,int> P;

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

}

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

//素数判定
bool is_prime(long long N) {
    if (N == 1) return false;
    for (long long i = 2; i * i <= N; ++i) {
        if (N % i == 0) return false;
    }
    return true;
}



  








      

 
int main(){
  ll n,a,b;
  cin >> n >> a >> b;
  if (a > b || (n == 1 && a != b)) {
    cout << 0 << endl;
    return 0;
  }
  cout << ((b*(n-1)+a)-(a*(n-1)+b))+1 << endl;

}


Measured memory_bytes: 3632
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <cstring>
#include <functional>
#include <queue>

using namespace std;

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

int X,Y,Z,K;

signed main()
{
	cin >> X >> Y >> Z >> K;

	vector<int> A(X), B(Y), C(Z);
	rep(i, X) cin >> A[i];
	rep(i, Y) cin >> B[i];
	rep(i, Z) cin >> C[i];

	vector<int> S;
	rep(i, X) rep(j, Y) S.push_back(A[i] + B[j]);

	sort(begin(S), end(S), greater<int>());
	sort(begin(C), end(C), greater<int>());

	vector<int> ans;

	int len = min(K, (int)S.size());
	rep(i, len) rep(j, Z) ans.push_back(S[i] + C[j]);

	sort(begin(ans), end(ans), greater<int>());

	rep(i, K) cout << ans[i] << endl;
}


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

const int maxn = 105, maxk = 1e5+5;
int N, K, a[maxn];
int dp[2][maxk];

int f(bool i, int k) {
    if (dp[i][k] != -1) return dp[i][k];
    if (k == 0) return dp[i][k] = !i;
    bool poss = false;
    for (int j = 1; j <= N; j++) {
        if (k-a[j] >= 0) {
            if (f(!i,k-a[j]) == i) {
                poss = true;
                dp[i][k] = i;
                break;
            }
        }
    }
    if (poss) return dp[i][k];
    else return dp[i][k] = !i;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> a[i];
    memset(dp,-1,sizeof dp);
    int ans = f(0,K);
    cout << (ans == 0 ? "First" : "Second") << '\n';

    return 0;
}



Measured memory_bytes: 8832
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef pair<int,int> P;
int main(void){
  long h,w;
  int n,i,j,k,a,b;
  set<P> bl,lm;
  cin >> h >> w >> n;
  for (i=0;i<n;i++){
    cin >> a >> b;
    bl.insert(P(a,b));
    for (j=-1;j<=1;j++) for (k=-1;k<=1;k++){
      int ni=a+j,nj=b+k;
      if (ni>1 && ni<h && nj>1 && nj<w) lm.insert(P(ni,nj));
    }
  }
  
  int t;
  long ans[15]={};
  set<P>::iterator ite1,ite2;
  for (ite1=lm.begin();ite1!=lm.end();ite1++){
    int f=ite1->first,s=ite1->second;
    t=0;
    for (i=-1;i<=1;i++) for (j=-1;j<=1;j++){
      int ni=f+i,nj=s+j;
      ite2=bl.find(P(ni,nj));
      if (ite2!=bl.end()) t++;
    }
    ans[t]++;
  }
  
  long sum=(h-2)*(w-2);
  for (i=1;i<10;i++) sum-=ans[i];
  cout << sum << endl;
  for (i=1;i<10;i++) cout << ans[i] << endl;
  return 0;
}

Measured memory_bytes: 47104
use std::cmp::*;
use std::io::*;
use std::num::*;
use std::str::*;

fn read<T: FromStr>() -> T {
    let stdin = stdin();
    let s = stdin
        .bytes()
        .map(|c| c.unwrap() as char)
        .skip_while(|c| c.is_whitespace())
        .take_while(|c| !c.is_whitespace())
        .collect::<String>();
    s.parse::<T>().ok().unwrap()
}

fn string() -> String {
    read()
}

fn int() -> i64 {
    read()
}

fn char() -> char {
    read::<String>().pop().unwrap()
}

fn vecchar() -> Vec<char> {
    string().chars().collect()
}

fn vecint(n: i64) -> Vec<i64> {
    let mut vec = Vec::new();
    for i in 0..n {
        vec.push(int())
    }
    vec
}

fn main() {
    let n = int();
    println!("{}", n * 800 - (n / 15) * 200)
}


Measured memory_bytes: 4352
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace AtCorder
{
	public class Program
	{
		static void Main(string[] args)
		{
			Scanner cin = new Scanner();
			int n = cin.Int();
			string s = cin.Next();

			int ans = 0;
			for (int i = 0; i < n; i++) {
				var length = ZAlogorithm(s, i);
				for (int j = 0; j < length.Length; j++) {
					if (j + i >= length[j] + i) {
						ans = Math.Max(ans, length[j]);
					}
				}
			}

			Console.WriteLine(ans);
		}

		public static int[] ZAlogorithm(string s, int index)
		{
			int n = s.Length - index;
			int[] a = new int[n];
			int c = 0;
			for (int i = 1; i < n; i++) {
				if (i + a[i - c] < c + a[c]) {
					a[i] = a[i - c];
				} else {
					int j = Math.Max(0, c + a[c] - i);
					while (i + j < n && s[j + index] == s[i + j + index]) {
						++j;
					}
					a[i] = j;
					c = i;
				}
			}

			a[0] = n;

			return a;
		}
	}

	public class Scanner
	{
		private readonly char[] delimiter_ = new char[] { ' ' };
		private string[] buf_;
		private int index_;

		public Scanner()
		{
			buf_ = new string[0];
			index_ = 0;
		}

		public string Next()
		{
			if (index_ < buf_.Length) {
				return buf_[index_++];
			}

			string st = Console.ReadLine();
			while (st == "") {
				st = Console.ReadLine();
			}

			buf_ = st.Split(delimiter_, StringSplitOptions.RemoveEmptyEntries);
			if (buf_.Length == 0) {
				return Next();
			}

			index_ = 0;
			return buf_[index_++];
		}

		public int Int()
		{
			return int.Parse(Next());
		}
		public int[] ArrayInt(int N, int add = 0)
		{
			int[] Array = new int[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Int() + add;
			}
			return Array;
		}

		public long Long()
		{
			return long.Parse(Next());
		}

		public long[] ArrayLong(int N, long add = 0)
		{
			long[] Array = new long[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Long() + add;
			}
			return Array;
		}

		public double Double()
		{
			return double.Parse(Next());
		}

		public double[] ArrayDouble(int N, double add = 0)
		{
			double[] Array = new double[N];
			for (int i = 0; i < N; i++) {
				Array[i] = Double() + add;
			}
			return Array;
		}
	}
}

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

#define N 100001
//root??§??????????????????
#define Origin -1

int depth(int);
void c_out(int);

struct Node{
	int p;
	int left;
	int right;
};

struct Node tree[N];
int cnt;

int main(){
	int n, k, new_node, child, l;
	
	cin >> n;
	
	for(int i = 0 ; i < n ; i++){
		tree[i].p = tree[i].left = tree[i].right = Origin;
	}
	
	for(int i = 0 ; i < n ; i++){
		cin >> new_node >> k;
		for(int j = 0 ; j < k ; j++){
			cin >> child;
			if(j == 0){
				tree[new_node].left = child;
			}else{
				tree[l].right = child;
			}
			
			l = child;
			tree[child].p = new_node;
		}
	}
	//??¶??????????????¨??????
	for(int i = 0 ; i < n ; i++){
		cnt = 0;
		
	cout << "node " << i << ": parent = " << tree[i].p << ", depth = " << depth(i) << ", ";
	if(tree[i].p == Origin){
		cout << "root, ";
	}
	else if(tree[i].left == Origin){
		cout << "leaf, ";
	}else{
		cout << "internal node, ";
	}
		cout << "[";
		
	cnt = 0;
	c_out(tree[i].left);
	cout << "]" << endl;
	}
	return 0;
}

//??±???????????°??§?±???????
int depth(int x){
	if(tree[x].p != Origin){
		cnt++;
		return depth(tree[x].p);
	}else{
		return cnt;
	}
}

//????????????
void c_out(int y){
	if(y != Origin){
		if(cnt != 0){
			cout << ", ";
		}
		
		cnt++;
		cout << y;
		c_out(tree[y].right);
	}
}

Measured memory_bytes: 2332
n = int(input())
a = [int(a) for a in input().split()]

def f(times, prefix_sum):
    for i in range(1, n):
        if prefix_sum < 0:
            if prefix_sum + a[i] > 0:
                prefix_sum += a[i]
            else:
                times += 1 - (prefix_sum + a[i])
                prefix_sum = 1      
        elif prefix_sum > 0:
            if prefix_sum + a[i] < 0:
                prefix_sum += a[i]
            else:
                times += abs(-1 - (prefix_sum + a[i]))
                prefix_sum = -1
    
    return times

if a[0] > 0:
    t1 = 0
    p1 = a[0]
else:
    t1 = 1 - a[0]
    p1 = 1


if a[0] < 0:
    t2 = 0
    p2 = a[0]
else:
    t2 = abs(-1 - a[0])
    p2 = -1
    

print(min(f(t1, p1), f(t2, p2)))

Measured memory_bytes: 14468
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

const ll MOD = 1000000007;

template <typename T>
struct BIT
{
    int n;
    vector<T> bit;
    
    BIT(){}
    
    BIT(int n) : n(n){
        bit.resize(n + 1);
    }
    
    T sum(int i){
        i++;
        T res = 0;
        while(i){
            res += bit[i];
            i -= (i & -i);
        }
        return res;
    }
    
    void add(int i, T x){
        i++;
        while(i <= n){
            bit[i] += x;
            i += (i & -i);
        }
    }
};

ll dp[1000005];

int main()
{
    ll n, h, d;
    cin >> n >> h >> d;
    ll f = 1;
    ll s = 0;
    for(ll i = 1; i <= n; i++){
        f = f * i % MOD;
        s = (s + f) % MOD;
    }
    BIT<ll> bit(h + 2);
    dp[0] = 1;
    for(int i = 1; i <= h; i++){
        dp[i] = (bit.sum(i - 1) - bit.sum(max(0ll, i - d - 1))) % MOD * s % MOD;
        if(i - d <= 0) dp[i] = (dp[i] + f) % MOD;
        bit.add(i, dp[i]);
    }
    cout << dp[h] << endl;
}


Measured memory_bytes: 15872
#include <bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
#define all(v) (v).begin(), (v).end()
#define rep(i,n) for(ll i=0;i<n;i++)
#define reps(i,n) for(ll i=0;i<=n;i++)
 
 
ll MOD = 1000000007;
const long long L_INF = 1LL << 60;
const int INF = 2147483647; // 2^31-1
const double PI = acos(-1);
 
const ll dx[8] = {1, 1, 0, -1, -1, -1, 0, 1};
const ll dy[8] = {0, 1, 1, 1, 0, -1, -1, -1};
 
int main(){
    ll n,k,ans=0;
    cin >> n >> k;
    vector<ll> H(n,0);
    rep(i,n){
        cin >> H[i];
    }
    sort(H.begin(),H.end());

    for(int i=0;i<n-k;i++){
        ans+=H[i];
    }
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 4760
#include <bits/stdc++.h>
#include <complex>
#include <iomanip>
using namespace std;
#define reps(i,s,n) for(int i = s; i < n; i++)
#define rep(i,n) reps(i,0,n)
#define fi first
#define se second
#define mp make_pair
typedef long long ll;
typedef vector<ll> vec;
typedef vector<vec> mat;

ll N,M,H,W,K,Q,A,B,C,L,R;
string S,T;
const ll MOD = (1e+9) + 7;
const ll INF = 1LL << 60;
const long double EPS = 1e-9;
typedef pair<ll,ll> P;

typedef vector<P> vp;
typedef vector<vp> matP;

int main() {
    cin>>N;
    map<ll,ll> a;
    multiset<ll> rec;
    rep(i,N){
        cin>>A;
        ++a[A];
        if(a[A] == 2) rec.insert(A);
        if(a[A] == 4) rec.insert(A);
    }
    if(rec.size() < 2){
        cout<<0<<endl;
    }else{
        auto rite = rec.rbegin();
        ll ans = *rite;
        ++rite;
        ans *= *rite;
        cout<<ans<<endl;
    }
}


Measured memory_bytes: 6528
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <cmath>
#include <vector>
#define rep(i, n) for(int i = 0; i < n; i++)
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    ll a[n], b[n];
    rep(i, n) {
        cin >> a[i] >> b[i];
    }
    ll ans = 0;

    for(int i = n-1; i >= 0; i--) {
        if(a[i]%b[i] != 0) {
            ans += b[i] - a[i]%b[i];
        }
        if(1 <= i) {
            a[i-1] += ans;
        }
    }

    cout << ans;

    cout << endl;
    return 0;
}

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

using namespace std;

typedef long long int llint;

class UnionFind {
public:
  UnionFind(int n) :par_(vector<int>(n))
  {
    for (int i = 0; i < n; ++i) {
      par_[i] = i;
    }
  }

  int find(int x) {
    if (par_[x] == x) {
      return x;
    } else {
      return par_[x] = find(par_[x]);
    }
  }

  bool same(int x, int y) {
    return find(x) == find(y);
  }

  void unite(int x, int y) {
    x = find(x);
    y = find(y);

    if (x == y) return;

    par_[y] = x;
  }
private:
  vector<int> par_;
};

const int inf = 1e9 + 9;

int n;
pair<llint, int> x[100010], y[100010];

typedef vector<pair<llint, pair<int, int>>> vecP;
llint solve() {
  sort(x, x+n);
  sort(y, y+n);

  vecP vec;
  for (int i = 0; i < n - 1; ++i) {
    vec.push_back(make_pair(x[i+1].first - x[i].first, make_pair(x[i+1].second, x[i].second)));
    vec.push_back(make_pair(y[i+1].first - y[i].first, make_pair(y[i+1].second, y[i].second)));
  }

  sort(vec.begin(), vec.end());
  UnionFind uf(n);
  llint ret = 0;
  for (int i = 0; i < vec.size(); ++i) {
    int a = vec[i].second.first;
    int b = vec[i].second.second;

    if (!uf.same(a, b)) {
      ret += vec[i].first;
      uf.unite(a, b);
    }
  }

  return ret;
}

void input() {
  cin >> n;
  int a, b;
  for (int i = 0; i < n; ++i) {
    cin >> a >> b;
    x[i] = pair<llint, int>(a, i);
    y[i] = pair<llint, int>(b, i);
  }
}

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

  input();

  cout << solve() << endl;

  return 0;
}

Measured memory_bytes: 9584
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <cmath>
using namespace std;
typedef long long i64;
typedef long double ld;
typedef pair<i64,i64> P;
#define rep(i,s,e) for(int i = (s);i <= (e);i++)

int main()
{
    string s;
  cin >> s;
    set<char> st;
    for(char c :s)
    {
        if(st.count(c))
        {
            cout << "no" << endl;
            return 0;
        }
        st.insert(c);
    }
    cout << "yes" << endl;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std ;
int temp[105]  ;
int main()
{
  string str ;
 cin >> str ;
int cnt = 0 ;
 memset(temp,0,sizeof temp) ;
for(int i = 0 ; i < str.size() ; i++)
{ 
  temp[str[i]]++ ;
if(temp[str[i]] == 1)
  cnt++ ;
}
if(cnt == str.size())
 cout << "yes\n" ;
else cout << "no\n"; 
return 0 ;
}

Measured memory_bytes: 256
a = int(input())
b = int(input())
c = int(input())
x = int(input())

result = 0
for i in range(a + 1):
    for j in range(b + 1):
        for k in range(c + 1):
            if 500 * i + 100 * j + 50 * k == x:
                result += 1

print(result)


Measured memory_bytes: 3060
# -*- coding: utf-8 -*-

"""
参考：http://tutuz.hateblo.jp/entry/2018/08/06/074104
　　　https://www.hamayanhamayan.com/entry/2018/08/05/232127
・別解
・予め必要なA,C,?の個数は集めておく。
・Bの位置を決めて、4つの選び方パターンを全部数え上げる。
・3べきの計算はpowの第三引数modで高速化
"""

MOD = 10 ** 9 + 7
S = input()

# あるBの位置よりも左にあるAと?の個数
A, LQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1):
    a = lq = 0
    if S[i] == 'A':
        a += 1
    if S[i] == '?':
        lq += 1
    A[i+1] = A[i] + a
    LQ[i+1] = LQ[i] + lq
# あるBの位置よりも右にあるCと?の個数
C, RQ = [0] * len(S), [0] * len(S)
for i in range(len(S)-1, 0, -1):
    c = rq = 0
    if S[i] == 'C':
        c += 1
    if S[i] == '?':
        rq += 1
    C[i-1] = C[i] + c
    RQ[i-1] = RQ[i] + rq

ans = 0
for i in range(len(S)):
    if S[i] == '?' or S[i] == 'B':
        # (A,B,C) と選ぶ場合(後ろの3べきは使わなかった?の分)
        case1 = (A[i] * C[i] * pow(3, LQ[i] + RQ[i], MOD)) % MOD
        # (A,B,?) と選ぶ場合
        case2 = (A[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        # (?,B,C) と選ぶ場合
        case3 = (LQ[i] * C[i] * pow(3, max(LQ[i] + RQ[i] - 1, 0), MOD)) % MOD
        # (?,B,?) と選ぶ場合
        case4 = (LQ[i] * RQ[i] * pow(3, max(LQ[i] + RQ[i] - 2, 0), MOD)) % MOD
        # 全部足し合わせてMOD
        ans = (ans + case1 + case2 + case3 + case4) % MOD

print(ans)


Measured memory_bytes: 18992