akhauriyash/Code-Regression huggingface dataset:
#pragma region
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <set>
#include <list>
#include <iomanip>
#include <cstdint>
#include <bitset>
#include <sstream>
#include <regex>
//#include <atcoder/all>

using namespace std;
//using namespace atcoder;
typedef long long ll;
//#define rep(i, s, e) for (int(i) = (s); (i) < (e); ++(i))
#define rep(i, e) for (int(i) = 0; (i) < (e); ++(i))
#define rrep(i, s) for (int(i) = (s) - 1; (i) >= 0; --(i))
#define all(x) x.begin(),x.end()

#pragma region UnionFind
struct UnionFind
{
	vector<int> par;

	UnionFind(int n) : par(n, -1) {}
	void init(int n) { par.assign(n, -1); }

	int root(int x)
	{
		if (par[x] < 0) return x;
		else return par[x] = root(par[x]);
	}

	bool issame(int x, int y)
	{
		return root(x) == root(y);
	}

	bool merge(int x, int y)
	{
		x = root(x); y = root(y);
		if (x == y) return false;
		if (par[x] > par[y]) swap(x, y);
		par[x] += par[y];
		par[y] = x;
		return true;
	}

	int size(int x)
	{
		return -par[root(x)];
	}
};
#pragma endregion
#pragma region GCD
ll gcd(ll a, ll b)
{
	if (b == 0)return a;
	return gcd(b, a%b);
}
#pragma endregion
#pragma region LCM
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
#pragma endregion
#pragma region chmin
template<class T> inline bool chmin(T& a, T b)
{
	if (a > b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma region chmax
template<class T> inline bool chmax(T& a, T b)
{
	if (a < b)
	{
		a = b;
		return true;
	}
	return false;
}
#pragma endregion
#pragma endregion


int main()
{
	int n, k, l; cin >> n >> k >> l;
	UnionFind auf(n), buf(n);
	rep(i, k)
	{
		int a, b; cin >> a >> b;
		--a, --b;
		auf.merge(a, b);
	}
	rep(i, l)
	{
		int a, b; cin >> a >> b;
		--a, --b;
		buf.merge(a, b);
	}
	vector<int> res(n);
	map<pair<int, int>, int> mp;
	rep(i, n)++mp[{auf.root(i), buf.root(i)}];
	rep(i, n)cout << mp[{auf.root(i), buf.root(i)}] << " ";
}

Measured memory_bytes: 16920
#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = 1LL<<60;
const long long int Mod = 1000000007;
using ll = long long int; using ci = const int;
using vi = vector<int>;  using Vi = vector<long long int>;
using P = pair<int, int>;  using PLL = pair<ll, ll>;
using matrix = vector<vector<ll>>;
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define all(x) (x).begin(),(x).end()
#define rp(i,N) for(ll i = 0; i < (ll)N; i++)
#define repi(i,a,b) for(ll i = ll(a); i < ll(b); ++i)
template<class T>bool chmax(T &former, const T &b) { if (former<b) { former=b; return true; } return false; }
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
template<class T>T sqar(T x){ return x*x; }//sqrt(x)は平方根;
#define Sort(v) std::sort(v.begin(), v.end(), std::greater<decltype(v[0])>()) //降順でVをソート
#define p_queue(v) priority_queue<v, vector<v>, greater<v> >
template<class T> inline void princ(T x){cout<<x<<" ";}; 
template<class T> inline void print(T x){cout<<x<<"\n";};
template<class T> inline void Yes(T condition){ if(condition) cout << "Yes" << endl; else cout << "No" << endl; }
template<class T> inline void YES(T condition){ if(condition) cout << "YES" << endl; else cout << "NO" << endl; }
///////////////////////////////////////////////////////////////////////////////////
const ll MAX = 5000001;//10^7が限界
const ll MOD = Mod;
//const ll MOD = INT64_MAX;
ll fac[MAX], finv[MAX], inv[MAX];

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

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

void dfs(ll v,ll p,ll depth){
    ll chs=0;
    for(auto ch:mat[v]){
        if(ch==p) continue;
        ++chs;
        dfs(ch,v,depth+1);
    }
    if(depth==0) ans*=COM(k-1,chs)*fac[chs]%Mod;
    else ans*=COM(k-2,chs)*fac[chs]%Mod;
    ans%=Mod;
}
void solve(){
    COMinit();
    cin >> n >> k;
    ans=k;
    mat.assign(n,Vi(0));
    rp(i,n-1){
        ll a,b;
        cin >> a >> b;
        --a; --b;
        mat[a].pb(b);
        mat[b].pb(a);
    }
    dfs(0,-1,0);
    print(ans);
    return;
}
int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    std::cout<<std::fixed<<std::setprecision(30);
    solve();
    return 0;
}

Measured memory_bytes: 131768
S = input()
T = input()

s_shelv = [None for x in range(26)]
t_shelv = [None for x in range(26)]

a_z = list('abcdefghijklmnopqrstuvwxyz')


for i in range(len(S)):
  s = S[i]
  t = T[i]
  si = a_z.index(s)
  ti = a_z.index(t)

  if s_shelv[si] is None:
    s_shelv[si] = ti
  elif s_shelv[si] != ti:
    print('No')
    exit()

  if t_shelv[ti] is None:
    t_shelv[ti] = si
  elif t_shelv[ti] != si:
    print('No')
    exit()

print('Yes')

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
int main(){
  int n;
  cin>>n;
  bool f=1;
  for(int i=0;i<n;i++){
    int a;
    cin>>a;
    if(a%2==0)
      if(a%3!=0&&a%5!=0)
        f=0;
  }
  cout<<(f?"APPROVED":"DENIED")<<endl;
}

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

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
#define mem(a,b) memset(a,b,sizeof(a))
#define shutdown ios::sync_with_stdio(false)
#define MAX 10e18+1000

int ma[200010];
int mb[200010];

int main() {
    shutdown;
    int a,b,s=0;
    cin>>a;
    for(int i=0;i<a;i++)
        cin>>ma[i];
    cin>>b;
    for(int i=0;i<b;i++)
        cin>>mb[i];
    sort(ma,ma+a);
    sort(mb,mb+b);
    int flag=0;
    for(;s<b;s++){
        for(;flag<a;flag++){
            if(ma[flag]<mb[s])
                continue;
            else if(ma[flag]>mb[s]){
                cout<<"NO"<<endl;
                return 0;
            }
            else{
                flag++;
                break;
            }
        }
    }
    if(s==b){
        cout<<"YES"<<endl;
    }
    return 0;
}


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

using namespace std;

void solve() {
  int64_t N, num_judge, num_sel, num_pass;
  cin >> N >> num_judge >> num_sel >> num_pass;
  vector<int64_t> scores(N);
  for (int64_t i = 0; i < N; ++i) {
    cin >> scores[i];
  }
  sort(scores.begin(), scores.end());
  int64_t can_pass = num_pass - 1;
  num_sel = max((int64_t)0, num_sel - num_pass);
  scores.resize(scores.size() - num_pass + 1);




  vector<int64_t> inte(scores.size() + 1);
  for (size_t i = 0; i < scores.size(); ++i) {
    inte[i + 1] = inte[i] + scores[i];
  }
  for (auto it = scores.begin(); it != scores.end(); ++it) {
    auto score = *it + num_judge;
    if (score < scores.back()) continue;
    auto idx = it - scores.begin();
    auto right = scores.end() - it - 1;
    auto sel = max((int64_t)0, num_sel - idx);
    // cerr << " sel " << sel << endl;
    auto right_area = inte.back() - inte[idx + 1];
    // cerr << " right_area " << right_area << endl;
    auto mass = sel * num_judge + right_area;
    // cerr << " mass " << mass << endl;
    auto height = mass ? (mass - 1) / right + 1 : 0;
    height = max(height, scores.back());
    if (height <= score) {
      // cerr << "### PASS ### : " << *it << " h " << height << " sc " << score<<endl;
      ++can_pass;
    } else {
      // cerr << "### NO   ### : " << *it << " h " << height << " sc " << score<<endl;
    }
  }
  cout << can_pass << endl;
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i < (n);i++)
#define ALL(obj) (obj).begin(),(obj).end()
#define SCANF(i) int i;scanf("%d",&i)
typedef long long ll;
using namespace std;
using P = pair<int,int>;
const long long INF = 1LL << 60;
const int IINF=100000000;
const int MOD = (int)1e9 + 7;
//約数列挙
vector<long long> divisor(long long n) {
    vector<long long> ret;
    for (long long i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            ret.push_back(i);
            if (i * i != n) ret.push_back(n / i);
        }
    }
    //sort(ret.begin(), ret.end()); // 昇順に並べる
    return ret;
}
vector<int> dx={1,0,-1,0};vector<int> dy={0,-1,0,1};

signed main () {
    int a,b,c;cin >> a >> b >> c;
    int ans = 0;int tmp = 0;
    while(tmp<a){
        tmp+=b;
        ans+=c;
    }
    cout << ans << endl;
}//https://atcoder.jp/contests/abc176/tasks/abc176_a

Measured memory_bytes: 3616
aa = list(map(int,input().split()))
bb = ["Left","Right","Balanced"]
a,b,c,d = [i for i in aa]

if a + b > c +d:
    print(bb[0] )
if a + b < c +d:
    print(bb[1] )
if a + b == c +d:
    print(bb[2] )

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

int main()
{
 int n;
  cin>>n;
  int t=n,sum=0;
  while(t){
    sum+=t%10;
    t/=10;
  }
  if(n%sum==0)
    cout<<"Yes\n";
  else
    cout<<"No\n";
  
  
  return 0;
}

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
#include <set>
#include <iomanip>
#include <stdio.h>
#include <sstream>
#include <string>
using namespace std;
int main(void){
  string s;
  cin>>s;
  if(s[2]==s[3]&&s[4]==s[5]){
    cout<<"Yes"<<endl;
  }else{
    cout<<"No"<<endl;
  }
}

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

using namespace std;

int main() {

  int n, g = 0, GG = 0;
  string p;
  cin >> n >> p;
  for(int i = 0;i < p.size();i++){
    if(p[i] == 'I'){
      g++;
    }else{
      g--;
    }
    GG = max(GG, g);
  }
  cout << GG;
  return 0;
}


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

class UnionFind {
public:
    vector < ll > par;
    vector < ll > siz;

    UnionFind(ll sz_): par(sz_), siz(sz_, 1){
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }
    void init(ll sz_) {
        par.resize(sz_);
        siz.assign(sz_, 1);
        for (ll i = 0; i < sz_; ++i) par[i] = i;
    }


    ll root(ll x){
        while(par[x] != x){
            x = par[x] = par[par[x]];
        }
        return x;
    }

    bool merge(ll x, ll y) {
        x = root(x);
        y = root(y);
        if (x == y) return false;
        if (siz[x] < siz[y]) swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool issame(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

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

    UnionFind uf(n);


    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        a--;
        b--;
        uf.merge(a, b);
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        int t = uf.size(i);
        if(ans < t){
            ans = t;
        }
    }

    cout << ans << endl;
}

Measured memory_bytes: 6360
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;


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

  int cntB = 0;
  for(int i = 0; i < S.length(); i++){
    if(i % 2 == 0){
      if(S[i] != '0'){
        cntB++;
      }
    }
    else{
      if(S[i] != '1'){
        cntB++;
      }
    }
  }

  int cntW = 0;
  for(int i = 0; i < S.length(); i++){
    if(i % 2 == 0){
      if(S[i] != '1'){
        cntW++;
      }
    }
    else{
      if(S[i] != '0'){
        cntW++;
      }
    }
  }


  cout << min(cntB, cntW) << endl;

  return 0;
}


Measured memory_bytes: 512
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
sum1 = 0
sum2 = 0
sum3 = 0
sum8 = 0
for i in range(n):
    d = abs(x[i]-y[i])
    sum1 += d
    sum2 += d**2
    sum3 += d**3
    if sum8 < d:
        sum8 = d
print(sum1)
print(sum2**0.5)
print(sum3**(1/3))
print(sum8)


Measured memory_bytes: 5644
a=list(input())
b=list(input())
c=list(input())
oner='a'
while True:
        if oner=='a':
            if len(a)==0:break
            oner=a.pop(0)
        if oner=='b':
            if len(b)==0:break
            oner=b.pop(0)
        if oner=='c':
            if len(c)==0:break
            oner=c.pop(0)
print(oner.upper())

Measured memory_bytes: 3060
#include<iostream>

long long gcd(long long a, long long b) //GCDを求める. Euclidの互除法を再帰関数で実装する. ベースケースはa = p * bでresidue = 0
{
	if (a%b==0)
	{
		return(b);
    }
	else
	{
		return(gcd(b,a%b));
    }
}

long long lcm(long long a, long long b){
    return a  / gcd(a, b) * b; //LCMの求め方: LCM * GCD = a * bより求める //a * b / gcdとするとオーバーフローを起こすため注意せよ
}

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

    long long t[n];
    for(int i = 0; i < n; i++){
        std::cin >> t[i];
    }

    long long ans = 1;
    for(int i = 0; i < n; i++){
        ans = lcm(ans, t[i]);
    }
    std::cout << ans << std::endl;
    return 0;
}

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

int main() {
  vector<int> vec(3);
  
  for(int i=0; i < 3; i++) {
    cin >> vec.at(i);
    }
  
  sort(vec.begin(), vec.end());
  
  int count=3;
  for(int i=0; i<2; i++) {
    if(vec.at(i) == vec.at(i+1)) {
      count--;
      }
    }
  
  cout << count << endl;
  }

Measured memory_bytes: 256
#CODE FESTIVAL 2016 qual C-C 二人のアルピニスト
"""
左右一列に並んでいる山を、左右から見ていった時に今まで見た中の最大値が分かる。
この状態で、山の高さの列が何通りあるか求めよ。

単純に、山の高さの"幅"を求めて、その分だけかけ合わせれば良さそう。

辻褄が合わないのは
1.高さが確定している場所同士で、辻褄が合わない
2.片方の高さが確定している場所で、もう片方の値がそれより小さい
このとき0
"""
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
n = int(readline())
L = list(map(int,readline().split()))
R = list(map(int,readline().split()))
mod = 10**9 + 7

mx = 0
L1 = []
for i in range(n):
    if mx < L[i]:
        L1.append((1,L[i]))
        mx = L[i]
    else:
        L1.append((0,L[i]))

R1 = []
mx = 0
for i in range(n-1,-1,-1):
    if mx < R[i]:
        R1.append((1,R[i]))
        mx = R[i]
    else:
        R1.append((0,R[i]))
R1.reverse()
ans = 1
for i in range(n):
    if L1[i][0] == 1:
        if R1[i][0] == 1:
            if L1[i][1] != R1[i][1]:
                ans = 0
                break
        else:
            if L1[i][1] > R1[i][1]:
                ans = 0
                break
    elif R1[i][0] == 1:
        if R1[i][1] > L1[i][1]:
            ans = 0
            break
    else:
        ans *= min(L1[i][1],R1[i][1])
        ans %= mod

print(ans)

Measured memory_bytes: 105836
#include<cstdio>
int N;
int main()
{
scanf("%d",&N);
int res=N;
for(int i=0;i<=N;i++)
{
int cc=0;
int t=i;
while(t>0)cc+=t%6,t/=6;
t=N-i;
while(t>0)cc+=t%9,t/=9;
if(res>cc)res=cc;
}
printf("%d\n",res);
}

Measured memory_bytes: 128
#include<bits/stdc++.h>
#define INF 1e9
#define llINF 1e18
#define MOD 1000000007
#define pb push_back
#define mp make_pair 
#define F first
#define S second
#define ll long long
#define ull unsigned long long
#define vi vector<ll>
#define vvi vector<vi>
#define BITLE(n) (1LL<<((ll)n))
#define BITCNT(n) (__builtin_popcountll(n))
#define SUBS(s,f,t) ((s).substr((f)-1,(t)-(f)+1))
#define ALL(a) (a).begin(),(a).end()
using namespace std;

int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  ll a,b,c,d,e,n;
  string s,ss,sss;
  cin>>n;
  for(ll i=1;i<=50000;i++){
    ll hoge = (i*108/100);
    if(hoge==n){cout<<i<<endl;return 0;}
  }
  cout<<":("<<endl;
  return 0;
}

Measured memory_bytes: 256
n = int(input())

stack = [["",0] for i in range(10**6*4)]
stack[0] = ["a",1]
pos = 0    
while(pos>=0):
    if(len(stack[pos][0]) == n):
        print(stack[pos][0])
        pos-=1
    else:
        
        nowstr = stack[pos][0]
        nowlen = stack[pos][1]
        #print(nowlen)
        pos-=1
        for ii in range(nowlen+1):
            i = nowlen-ii
            pos+=1
            stack[pos][0] = nowstr+chr(ord('a')+i)
            if(i == nowlen):
                stack[pos][1] = nowlen+1
            else:
                stack[pos][1] = nowlen





Measured memory_bytes: 486968
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, srt, end) for (long long i = (srt); i < (long long)(end); i++)

int main(){
    ll a, b, c;
    cin >> a >> b >> c;
    ll mn = min(a, min(b, c));
    ll mx = max(a, max(b, c));
    ll md = (a+b+c) - mx -mn;
    ll ans = 0;
    ans += (md - mn + 1)/2;
    if((md - mn)%2 == 1){
        ans++;
        md++;
        mx++;
    }
    mn = md;
    ans += (mx - md);
    cout << ans << endl;
    return 0;
}

Measured memory_bytes: 256
package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

type ProblemGroup struct {
	point     int
	nProblems int
	compBonus int
}

func main() {
	sc := bufio.NewScanner(os.Stdin)
	sc.Split(bufio.ScanWords)

	nGroups := scanInt(sc)
	goal := scanInt(sc)

	groups := make([]ProblemGroup, nGroups)
	for i := 0; i < nGroups; i++ {
		groups[i] = ProblemGroup{
			point:     (i + 1) * 100,
			nProblems: scanInt(sc),
			compBonus: scanInt(sc),
		}
	}

	// コンプリートするグループの組み合わせ数。
	nPatterns := 1 << uint(nGroups)

	minSolves := 10 * 100
	for p := 0; p < nPatterns; p++ {
		maxIncompIdx := -1
		score := 0
		nSolves := 0
		for i := nGroups - 1; i >= 0; i-- {
			isComp := (p >> uint(i) & 1) == 1
			g := groups[i]
			if isComp {
				score += g.point*g.nProblems + g.compBonus
				nSolves += g.nProblems
				if score >= goal {
					break
				}
			} else if maxIncompIdx < 0 {
				maxIncompIdx = i
			}
		}

		if score < goal && maxIncompIdx >= 0 {
			for i := maxIncompIdx; i >= 0; i-- {
				isComp := (p >> uint(i) & 1) == 1
				if isComp {
					continue
				}

				g := groups[i]
				n := (goal - score) / g.point
				if n > g.nProblems-1 {
					n = g.nProblems - 1
				}
				score += g.point * n
				nSolves += n

				if score >= goal {
					break
				}
			}
		}

		if score >= goal && nSolves < minSolves {
			minSolves = nSolves
		}
	}

	fmt.Println(minSolves)
}

func scanInt(sc *bufio.Scanner) int {
	sc.Scan()
	v, _ := strconv.Atoi(sc.Text())
	return v
}


Measured memory_bytes: 640
#include<stdio.h>
 
int gcd( int x, int y )
{
    if( 0 == y ) {
        return x;
    } else {
        return gcd( y, x%y );
    }
}
 
 
int main( void ) 
{
    int a,b;
     
    scanf( "%d%d", &a, &b );
     
    int tmp;
    if( b < a ) {
        tmp=a;
        a=b;
        b=tmp;
    }
     
    printf( "%d\n", gcd( b, a ) );
     
    return 0;
}

Measured memory_bytes: 592
import sys

input_list = sys.stdin.readlines()

count = 1
get_count = 0
get_value_count = 0
output = 0
for i in input_list:
  get_values = i.split()
  if count == 1:
    get_value_count = int(get_values[0])
    get_count = int(get_values[1])
  else:
    if get_value_count == 1:
      output = get_values[0]
    else:
      new_list = sorted(get_values, key=int)
      count_value = 1
      for c in new_list:
        if count_value > get_count:
          break
        else:
          output = output + int(c)
        count_value = count_value + 1
  count = count + 1
print(str(output))

Measured memory_bytes: 9200
x1,y1,x2,y2= map(int,input().split())


v = [x2-x1,y2-y1]
v1 = [-v[1],v[0]]
v2 = [-v[0],-v[1]]

x3,y3 = x2+v1[0],y2+v1[1]
x4,y4 = x3+v2[0],y3+v2[1]
print(x3,y3,x4,y4)


Measured memory_bytes: 3060
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<functional>
#include<string>
#include<string.h>
#include<limits.h>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<unordered_set>
#define int long long
using namespace std;

int n;
int MAX;
int a[101];
bool k[101];//false 使わない true 使う
void saiki(int b) {
	if (b == 24||b==n+1) {
		int t = 0;
		for (int i = 1; i <= 23; i++) { if (k[i])t += a[i]; }
		for (int i = 24; i <= n; i++) {
			for (int j = 1; j <= 23; j++) {
				if (i%j == 0 && k[j]) {
					t += a[i];
					k[i] = true;
					break;
				}
				else {
					k[i] = false;
				}
			}
		}
		for (int i = n; i > 23; i--) {
			if (k[i])continue;
			bool OK = true;//自由に使えるか？
			for (int j = i*2; j <= n; j+=i) {
				if (!k[j])OK = false;
			}
			if (OK) {
				if (a[i] >= 0) {
					k[i] = true;
					t += a[i];
				}
			}
			else {
				int o = 0;
				if (a[i] >= 0) {
					for (int j = i; j <= n; j+=i) {
						if(!k[j])o += a[j];
					}
					if (o >= 0) {
						for (int j = i; j <= n; j += i) {
							k[j] = true;
						}
						t += o;
					}
				}
			}
		}
		MAX = max(MAX, t);
		return;
	}
	for (int i = 1; i < b; i++) {
		if (b%i == 0 && k[i]) {
			k[b] = true;
			saiki(b + 1);
			return;
		}
	}
	k[b] = false;
	saiki(b + 1);
	k[b] = true;
	saiki(b + 1);
}
signed main() {
	cin >> n;
	int sum = 0;
	for (int i = 0; i < n; i++) {
		cin >> a[i + 1];
		sum += a[i + 1];
		a[i + 1] *= -1;
	}
	saiki(1);
	cout << sum + MAX << endl;
}


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

int main(void) {
  int N, C;
  cin >> N >> C;
  vector<int> s(N), t(N), c(N);
  vector<vector<int>> used(C, vector<int>(100001));

  for (int i = 0; i < N; i++) {
    cin >> s[i] >> t[i] >> c[i];
    c[i]--;
    for (int j = s[i]; j <= t[i]; j++) {
      used[c[i]][j] = 1;
    }
  }
    
  int ret = 0;
  for (int i = 0; i < 100001; i++) {
    int cnt = 0;
    for (int j = 0; j < C; j++) {
      cnt += used[j][i];
    }
    ret = max(cnt, ret);
  }
  cout << ret << endl;
  
  return 0;
}

Measured memory_bytes: 13568
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <vector>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

void solve() {
  int n;
  vector<pll> v;
  cin >> n;
  v.resize(n);
  for(int i = 0; i < n; i++) cin >> v[i].second >> v[i].first;
  sort(v.begin(), v.end());
  ll curr = 0;
  bool good = true;
  for(pll out: v) {
    curr += out.second;
    good &= curr <= out.first;
  }
  if(good) cout << "Yes\n";
  else cout << "No\n";
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  solve();
  /*
  ll t;
  cin >> t;
  for(ll i = 1; i <= t; i++) {
    cout << "Case #" << i << ": ";
    solve();
  }
  */
}


Measured memory_bytes: 3328
#include<bits/stdc++.h>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
	long long n, k=2, cnt = 0;
	string ans = "No";
  	cin >> n;
  	for(int i=1;(i*(i+1)/2)<=n;i++){
  		if((i*(i+1)/2)==n){
  			k = i+1;
  			ans = "Yes";
  		}
  	}
  	
  	
	  	
	vector<vector<int>> s(k);
  	s[0].push_back(1);
  	s[1].push_back(1);
  	if(ans == "Yes"){
  		for(int i=2;i<=n;i++){
  			for(int j=1;j<=i;j++){
  				if(i <=j*(j+1)/2){
  					cnt = j;
  					break;
  				}
  			}
  			for(int j=0;j<k;j++){
  				int l = s[j].size();
  				if(l < cnt){
  					s[j].push_back(i);
  					break;
  				}
  			}
  			s[cnt].push_back(i);
  		}
  	}
  	
  	
  	
  	
  	if(ans == "No"){
  		cout << ans <<endl;
  	}else{
  		cout << ans <<endl;
  		cout << k <<endl;
  		for(int i=0;i<k;i++){
  			cout << k-1;
  			for(int j=0;j<k-1;j++){
  				if(j!=k-2){
  					cout << " "<<s[i][j];
  				}else{
  					cout << " "<<s[i][j] <<endl;
  				}
  			}
  		}
  	}
}



Measured memory_bytes: 2304
H,W,K = map(int,input().split())
c = [list(input()) for _ in range(H)]

ans = 0
for nh in range(2**H):
    for nw in range(2**W):
        count = 0
        for h in range(H):
            for w in range(W):
                if 2**h&nh!=2**h and 2**w&nw!=2**w and c[h][w]=='#':
                    count += 1
        if count==K:
            ans += 1
print(ans)

Measured memory_bytes: 68140
#include <string>
#include <vector>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <map>
#include <list>
#include <set>
#include <numeric>
#include <queue>
#include <stack>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <cstring>
#include <climits>
#include <cfloat>
#include <ctime>
#include <complex>
#include <cassert>
#include <array>
#include <bitset> 
#include <unordered_map>

using namespace std;
typedef long long LL;
typedef pair<int,int> P;

const int L=1e5+1;

LL l[L];
LL w[L];
int main() {
	int N;
	cin >> N;
	for(int i=0;i<N;i++){
		LL r;
		cin >> l[i] >> r;
		w[i]=r-l[i];
	}
	multiset<LL> left,right;
	LL lo=0,ro=0;
	left.insert(l[0]);
	right.insert(l[0]);
	LL h=0;
	for(int i=1;i<N;i++){
		ro+=w[i-1];
		lo-=w[i];
		auto a=left.end();
		a--;
		auto b=right.begin();
		if(l[i]<*a+lo){
			h+=*a+lo-l[i];
			right.insert(*a+lo-ro);
			left.erase(a);
			left.insert(l[i]-lo);
			left.insert(l[i]-lo);
		}
		else if(l[i]<=*b+ro){
			left.insert(l[i]-lo);
			right.insert(l[i]-ro);
		}
		else{
			h+=l[i]-(*b+ro);
			left.insert(*b+ro-lo);
			right.erase(b);
			right.insert(l[i]-ro);
			right.insert(l[i]-ro);
		}
	}
	cout << h << endl;


	return 0;
}



Measured memory_bytes: 11136
#include<bits/stdc++.h>
#define ll long long int

using namespace std;

ll dp[3001][3001][2];

ll recurse(int l, int r,int turn, vector<ll> &arr)
{
    if(l>r) return 0;
    if (dp[l][r][turn] != -1) return dp[l][r][turn];
    else
    {
        if(turn == 1) return dp[l][r][turn] = max(recurse(l+1,r,0,arr)+arr[l],recurse(l,r-1,0,arr)+arr[r]);
        else return dp[l][r][turn] = min(recurse(l+1,r,1,arr),recurse(l,r-1,1,arr));
    }
    
}

int main(int argc, char const *argv[])
{
    int n,temp;
    cin >> n;
    vector<ll> arr(n,0);
    ll sum = 0;

    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        arr[i] = temp;
        sum+= temp;
    }

    for(int i =0 ; i <= n ; i++)for(int j =0; j <=n ;j++)for(int k=0 ; k<=2 ;k++) dp[i][j][k] = -1;

    ll x = recurse(0,n-1,1,arr);
    ll y = sum -x ;

    cout << x-y;
    
    return 0;
}


Measured memory_bytes: 144596
import java.util.*;
public class Main{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    int x = sc.nextInt();
    if(x == 1){
      System.out.println("Hello World");
    }else{
      int a = sc.nextInt();
      int b = sc.nextInt();
      System.out.println(a+b);
    }   
  } 
}

Measured memory_bytes: 21844
#include<iostream>
    #include<cstdio>
    #include<math.h>
    #include<string>
    #include<algorithm>
    #include<functional>
    #include<vector>
    #include<set>
    #include<map>
    #define INF 999999
    #define EPS 1.0e-6
     
    using namespace std;
     
    typedef long long ll;
    typedef pair<int, int> P;
    typedef pair<int, P> PP;
     
     
    ll a[2100];
     
    int main()
    {
    	int n;
    	int z, w;
    	cin >> n >> z >> w;
    	for (int i = 0; i < n; i++) {
    		cin >> a[i];
    	}
    	if (n == 1) {
    		ll cur = abs(z - w);
    		ll ne = abs(a[0] - w);
    		cout << ne << endl;
    		return 0;
    	}
    	if (n >= 2) {
    		ll s = abs(z - w);
    		ll k = a[n - 2];
    		ll l = a[n - 1];
    		cout << max(abs(k - l), abs(l - w)) << endl;
    		return 0;
    	}
     
     
    	return 0;
    }

Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <iomanip>
#include <cassert>
using namespace std;

#define GET_ARG(a,b,c,F,...) F
#define REP3(i,s,e) for (i = s; i <= e; i++)
#define REP2(i,n) REP3 (i,0,(int)(n)-1)
#define REP(...) GET_ARG (__VA_ARGS__,REP3,REP2) (__VA_ARGS__)
#define RREP3(i,s,e) for (i = s; i >= e; i--)
#define RREP2(i,n) RREP3 (i,(int)(n)-1,0)
#define RREP(...) GET_ARG (__VA_ARGS__,RREP3,RREP2) (__VA_ARGS__)
#define DEBUG(x) cerr << #x ": " << x << endl

int main(void) {
    string s;
    cin >> s;
    int a = 0;
    for (auto c: s) {
        if (a == 0) {
            if (c == 'C')
                a = 1;
        }
        else {
            if (c == 'F')
                a = 2;
        }
    }
    if (a == 2)
        puts("Yes");
    else
        puts("No");
    return 0;
}


Measured memory_bytes: 256
#include <stdio.h>
#include <math.h>
#include <stdlib.h>

struct sort_data {
    int value;//値
    int index;//インデックス
};

int compare(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}

int main(){
	int N;
	scanf("%d", &N);
	int i, j;
    struct sort_data A[N];
    for (i=0; i<N; i++){
        scanf("%d", &A[i].value);
        A[i].index = i;
    }

    qsort(A, N, sizeof(struct sort_data), compare);

	for(i=0; i<N; i++){
		printf("%d ", A[i].index + 1 );
	}

}

Measured memory_bytes: 1660
#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <map>
#include <queue>
#include <set>
#define rep(i,n) for(int i = 0; i < n; i++)
#define rep1(i,n) for(int i = 1; i <= n; i++)
#define co(x) cout << x <<endl
#define cs(x) cout << x <<" "
#define ALL(a) (a).begin(),(a).end()
typedef long long ll;
using namespace std;
ll mod = 1e9 + 7;

int main()
{
	string s;
	cin >> s;
	int k;
	cin >> k;
	vector<string>sv;
	for (int i = 0; i < s.size(); i++)
	{
		for (int j = i; j <= i+k; j++)
		{
			string ssub = s.substr(i, j - i + 1);
			sv.push_back(ssub);
		}
	}
	sort(ALL(sv));
	sv.erase(unique(ALL(sv)), sv.end());
	co(sv[k - 1]);
}

Measured memory_bytes: 1916
#include <iostream>

using namespace std;

int main()	{
  long long ways;
  long long x;
  cin >> x;
  ways = 2 * (x / 11);
  int remaining = (x % 11);
  if (remaining > 0 && remaining <= 6)	{
    ways++;
  }
  else if (remaining > 6)
    ways+=2;
  cout << ways;
  cout << endl;
  return 0;
}

Measured memory_bytes: 3636
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <algorithm>
#include <cmath>
#include <queue>
#include <iterator>
#include <functional>
#include <numeric>
#include <cmath>

using namespace std;

#define ll long long
#define f0(i,n)for(i=0;i<n;i++)
#define f1(i,n)for(i=1;i<=n;i++)
#define fc(i,c,n)for(i=c;i<=n;i++)
#define f0r(i,n)for(i=n-1;i>=0;i--)
#define f1r(i,n)for(i=n;i>0;i--)
#define fcr(i,c,n)for(i=n;i>=c;i--)
#define IO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

typedef list<ll> LST;
typedef vector<ll> VEC;
typedef map<ll, ll> MAP;

ll i, j, q;
ll n, m, p, k, t, s, v;
ll a, b, c, d;
ll x, y, z, l, r;
ll one = 1, zero = 0, ans = 0;
ll mod = 1000000007;
ll ii;
ll INF = 223372036854775807;
ll ln1, ln2, lnc;
ll a1, a2, a3, a4, a5, a6, a7, a8, a9;
string st1, st2, st3;
char ch1, ch2, ch3;



int main() {
	int t;
	ifstream fin("Text.txt");

	cin >> n;
	VEC vc(n),vc2(n);
	f0(i, n) {
		cin >> vc[i];
		vc2[i] = vc[i];
	}
	sort(vc.begin(), vc.end());
	a1 = vc[(n / 2)-1];
	a2 = vc[n/2];

	f0(i, n) {
		if (vc2[i] >= a2) 
			cout << a1 << endl;
		else 
			cout << a2 << endl;
	}
	return 0;
}

Measured memory_bytes: 5376
#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define REPR(i, n) for(int i = n; i >= 0; i--)
#define FOR(i, m, n) for(int i = m; i < n; i++)
#define INF 2e9
#define ALL(v) (v).begin(), (v).end()
using namespace std;
typedef long long ll;

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

	int cake, donut;

	cake = n / 4;
	donut = n / 7;

	REP(i, cake + 1){
		REP(j, donut + 1){
			if (4 * i + 7 * j == n){
				cout << "Yes" << endl;
				return 0;
			}
		}
	}

	cout << "No" << endl;
}


Measured memory_bytes: 256
using System.Linq;
using System.Security.Cryptography.X509Certificates;
using System.Text;
using System;
using System.Collections;
using System.Collections.Generic;
using System.Globalization;
using System.IO;

namespace AtCoder
{
    class Program
    {

        const int BiggestMod = 1000000007;
        public static void Main()
        {

            var nums = int.Parse(Console.ReadLine()) + 1;
            var list = new KeyValuePair<long, long>[nums]; // Key = 枝, Value = 葉
            var args = Console.ReadLine().Split(' ').Select(x => long.Parse(x)).ToArray();

            for (int i = args.Length - 1; args[i] == 0; i--)
                Array.Resize(ref args, args.Length - 1);

            if (args[0] == 0)
            {
                list[0] = new KeyValuePair<long, long>(1, 0);
                if (args.Length == 1)
                {

                    Console.WriteLine(-1);
                    return;

                }
            }
            else if (args[0] == 1) list[0] = new KeyValuePair<long, long>(0, 1);
            else
            {

                Console.WriteLine(-1);
                return;

            }

            for (int i = 1; i < nums; i++)
            {

                if ((list[i - 1].Key << 1) < args[i])
                {

                    Console.WriteLine(-1);
                    return;

                }
                
                else
                {

                    var leaf = args[i];
                    var branch = (list[i - 1].Key << 1) - args[i];
                    if (branch > 2000000000000000) branch = 2000000000000000;

                    list[i] = new KeyValuePair<long, long>(branch, leaf);
                }

            }

            list[nums - 1] = new KeyValuePair<long, long>(0, args[nums - 1]);
            
            for (int i = nums - 2; 
                i >= 0; i--)
            {

                if (list[i].Key > (list[i + 1].Key + list[i + 1].Value))
                    list[i] = new KeyValuePair<long, long>(list[i + 1].Value + list[i + 1].Key, list[i].Value);

            }

            Console.WriteLine(list.Sum(x => x.Key + x.Value));


        }

    }

}

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

#define REP(i, n) for (int (i) = 0 ; (i) < (int)(n) ; ++(i))
#define REPN(i, m, n) for (int (i) = m ; (i) < (int)(n) ; ++(i))
#define REP_REV(i, n) for (int (i) = (int)(n) - 1 ; (i) >= 0 ; --(i))
#define REPN_REV(i, m, n) for (int (i) = (int)(n) - 1 ; (i) >= m ; --(i))

#define INF 2e9
#define INF_LL 1LL<<60
#define ll long long
#define ALL(v) (v).begin(), (v).end()
typedef pair<ll, ll> P;

int main(){
    int n, m;
    cin >> n >> m;
    vector<P> info[n+1];
    vector<ll> ans(m);

    REP(i, m) {
        int p, y;
        cin >> p >> y;
        info[p].push_back(make_pair(y, i));
    }

    REP(i, n) {
        sort(info[i+1].begin(), info[i+1].end());
    }

    REP(i, n) {
        REP(j, info[i+1].size()) {
            ans[info[i+1][j].second] = (ll)(i+1) * 1000000 + (ll)(j+1);
        }
    }

    REP(i, m) {
        printf("%012lld\n", ans[i]);
    }

    return 0;
}


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

using namespace std;

struct Process {
  string name;
  int time;
};

int main () {
  int n, q;
  Process P[1000000];

  cin >> n >> q;

  for (int i = 0; i < n; i++) {
    cin >> P[i].name >> P[i].time;
  }

  int count = 0;
  int origin = n;

  for (int i = 0; i < n; i++) {
    P[i].time -= q;
    if (P[i].time <= 0) {
      count += q + P[i].time;
      cout << P[i].name << " " << count << endl;
    } else {
      n++;
      P[n-1] = P[i];
      count += q;
    }
  }

}

Measured memory_bytes: 21004
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <fstream>
#include <sstream>
#include <iomanip>

using namespace std;

long long MOD = 1000000007;

int main(){
    int A, B;
    cin >> A >> B;
    for(int i=1; i<4; i++){
        if(A==i || B==i)continue;
        cout << i << endl;
    }
}

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

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int max = 0;

		String s = sc.next();
		for(int i = 0; i < s.length(); i++) {
			for(int j = s.length(); j >i;j--) {
				String temp = s.substring(i,j);
				if(temp.matches("[A,T,C,G]{0,}")) {
					
				if(temp.length() > max) {
					max = temp.length();
				}
				}
			}
		}
		System.out.println(max);
	}

}

Measured memory_bytes: 23124
import java.util.*;
public class Main {
	public static void main(String args[]){
		Scanner sc = new Scanner(System.in);
		int H = sc.nextInt();
		int W = sc.nextInt();
		int[][] data = new int[H][W];
		int N = sc.nextInt();
		int r = 0;
		int c = 0;
		boolean add = true;
		for(int i = 1 ; i<=N; i++){
			int cnt = sc.nextInt();
			for(int j = 0 ; j<cnt; j++){
				if(c == W){
					c = W-1;
					r++;
					add = false;
				}
				else if(c == -1){
					c = 0;
					r++;
					add = true;
				}
				data[r][c] = i;
				if(add){
					c++;
				}
				else{
					c--;
				}
			}
		}
		for(int i = 0 ; i <H; i++){
			for(int j = 0 ; j<W; j++){
				System.out.print(data[i][j]);
				if(j!=W-1)System.out.print(" ");
			}
			System.out.println();
		}
	}
}


Measured memory_bytes: 31688
mod = 10 ** 9 + 7
n = int(input())

n10 = 1
for _ in range(n):
    n10 = n10 * 10 % mod
n9 = 1
for _ in range(n):
    n9 = n9 * 9 % mod
n8 = 1
for _ in range(n):
    n8 = n8 * 8 % mod

ans = n10 - 2 * n9 + n8
print(ans % mod)


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

int main(){

  int a,b;

  if(-1000<=a && b<=1000){
    cin>>a >>b;
    if(a<b) cout<<"a < b" <<endl;
    else if(a>b) cout<<"a > b" <<endl;
    else cout<<"a == b" <<endl;
  }
  return 0;
}

Measured memory_bytes: 1156
#include<string>
#include<iostream>
#include<algorithm>
#include<set>
#include<math.h>
#include<vector>
#include<sstream>
#include<queue>
#include<functional>
#include<bitset>
#include<cstdio>
#include<iomanip>
#include<map>
#include<unordered_map>
#include<unordered_set>
#include <string.h>
using ll = long long;
 
#define rep(i, n) for(ll i = 0; i < (int)(n); i++)
#define reps(i,x) for(ll i=1;i<=(int)(x);i++)
#define rrep(i,x) for(ll i=((int)(x)-1);i>=0;i--)
#define rreps(i,x) for(ll i=(int)(x);i>0;i--)
#define all(x) (x).begin(),(x).end()
#define m0(x) memset(x,0,sizeof(x))
#define vll vector<ll>
#define vi vector<int>
#define mp make_pair
#define vpll vector<pair<ll,ll>>
#define vpi vector<pair<int,int>>
#define mod 1000000007 
using namespace std;
char a[101][101];
int b[101];
int c[101];

int main() {
	int a, b;
  cin >> a >> b;
  if(a*b % 2)
    cout << "Yes" << endl;
  else
    cout << "No" << endl;
}


Measured memory_bytes: 256
import sys

def main():
    N = int(input())
    A = [int(sys.stdin.readline()) for i in range(N)]
    anoA = sorted(A)
    mA = max(A)

    for j in range(N):
        if mA == A[j]:
            print(anoA[-2])

        else:
            print(mA)


main()

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

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

const int MAXN=4E6+10;
const int P=1E9+7;

template<typename T1,typename T2>
	void Inc(T1 &a,T2 b){a+=b;if(a>=P) a-=P;}

template<typename T1,typename T2>
	void Dec(T1 &a,T2 b){a-=b;if(a<0) a+=P;}

template<typename T1,typename T2>
	T1 Add(T1 a,T2 b){a+=b;return a>=P?a-P:a;}

template<typename T1,typename T2>
	T1 Sub(T1 a,T2 b){a-=b;return a<0?a+P:a;}

ll ksm(ll a,ll b)
{
	ll ret=1;
	for(;b;b>>=1,(a*=a)%=P)
		if(b&1)
			(ret*=a)%=P;
	return ret;
}

int n,k;
ll fac[MAXN],ifac[MAXN],f[2010][2010];

ll C(int n,int m)
{
	if(n<0||m<0||n<m)
		return 0;
	return fac[n]*ifac[n-m]%P*ifac[m]%P;
}

int main()
{
	fac[0]=ifac[0]=1;
	for(int i=1;i<MAXN;i++)
		fac[i]=fac[i-1]*i%P;
	ifac[MAXN-1]=ksm(fac[MAXN-1],P-2);
	for(int i=MAXN-2;i;i--)
		ifac[i]=ifac[i+1]*(i+1)%P;
	scanf("%d%d",&n,&k);
	if(k==1)
		return puts("1"),0;
	f[0][0]=1;
	for(int i=1;i<=n;i++)
		for(int j=i;~j;j--)
			f[i][j]=Add(f[i][j+1],j?(C(i*k-j-1,k-2)*f[i-1][j-1]%P):0);
	printf("%lld\n",f[n][0]*fac[n]%P);
}


Measured memory_bytes: 92800
using System;
using System.Linq;
using System.Collections.Generic;
using static System.Console;

class Program
{
    internal static void Main(string[] args)
    {
        var N = int.Parse(ReadLine());
        var a = ReadLine().Split(' ').Select(s => int.Parse(s)).ToList();

        int alice = 0;
        int bob = 0;

        for (int i = 0; i < N; i++) {
            if (i % 2 == 0) {
                alice += a.Max();
            } else {
                bob += a.Max();
            }
            a.Remove(a.Max());
        }

        WriteLine(alice - bob);
    }
}


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

typedef long long ll;

#define REP(i, N) for (int i = 0; i < (int)(N); i++)

// chmax, chmin
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 = 1LL<<60;
int N,M,L;

void warshall_floyd( vector<vector<ll>>& d ){
    REP(k,N) REP(i,N) REP(j,N) {
        d[i][j] = min(d[i][j],d[i][k] + d[k][j]);
    }
}

int main() {
    cin >> N >> M >> L;
    
    vector<vector<ll>> d(N,vector<ll>(N,INF));
    REP(i,M){
        int a,b;
        ll c;
        cin >> a >> b >> c;
        d[a-1][b-1] = c;
        d[b-1][a-1] = c;
    }
    REP(i,N) d[i][i] = 0;
    
    warshall_floyd(d);
    
    vector<vector<ll>> d2(N,vector<ll>(N,INF));
    REP(i,N) REP(j,N){
        if ( i == j ) {
            d2[i][j] = 0;
        } else if ( d[i][j] <= L ) {
            d2[i][j] = 1;
            d2[j][i] = 1;
        }
    }
    
    warshall_floyd(d2);
    
    int Q;
    cin >> Q;
    vector<int> s(Q),t(Q);
    REP(i,Q) cin >> s[i] >> t[i];
    REP(i,Q) {
        ll dis = d2[s[i]-1][t[i]-1];
        ll ans = 0;
        if ( dis == INF ) ans = 0;
        else ans = dis;
        cout << ans-1 << endl;
    }
    
    
    
    return 0;
}


Measured memory_bytes: 5336
//include
//------------------------------------------
#include <vector>
#include <list>
#include <map>
#include <climits>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <ctime>
#include <queue>
#include <random>
#include <cctype>
#include <complex>
#include <regex>

using namespace std;

#define C_MAX(a, b) ((a)>(b)?(a):(b))
#define SHOW_VECTOR(v) {std::cerr << #v << "\t:";for(const auto& xxx : v){std::cerr << xxx << " ";}std::cerr << "\n";}
#define SHOW_MAP(v) {std::cerr << #v << endl; for(const auto& xxx: v){std::cerr << xxx.first << " " << xxx.second << "\n";}}

#define MAX_N 1200
#define INF 10000000

struct edge {
    int to;
    int cap;
    int rev;
};


vector<vector<edge>> G;
vector<bool> used;

void add_edge(int from, int to, int cost) {
    G[from].push_back((edge) {to, cost, (int) G[to].size()});
    G[to].push_back((edge) {from, 0, (int) G[from].size() - 1});
}

int dash_flow(int v, int t, int f) {
    if (v == t) return f;
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        edge &e = G[v][i];
        if (e.cap > 0 && !used[e.to]) {
            int d = dash_flow(e.to, t, min(f, e.cap));
            if (d > 0) {
                e.cap -= d;
                G[e.to][e.rev].cap += d;
                return d;
            }
        }
    }
    return 0;
}

int max_flow(int s, int t) {
    int flow = 0;
    while (true) {
        used = vector<bool>(MAX_N, false);
        int f = dash_flow(s, t, INF);
        if (f == 0)return flow;
        flow += f;
    }
}

int gcd(int x, int y) {
    return y == 0 ? x : gcd(y, x % y);
}

int main() {

    while (true) {

        int M, N;
        cin >> M >> N;

        if (M == 0 && N == 0) break;

        G = vector<vector<edge>>(MAX_N);

        vector<int> b(M);
        for (int i = 0; i < M; i++)cin >> b[i];

        vector<int> r(N);
        for (int i = 0; i < N; i++) cin >> r[i];

        int s = 0;
        int t = N + M + 1;

        for (int i = 0; i < M; i++) add_edge(s, i + 1, 1);
        for (int i = 0; i < N; i++) add_edge(M + i + 1, t, 1);

        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                if (gcd(b[i], r[j]) > 1) {
                    add_edge(i + 1, M + j + 1, 1);
                }
            }
        }

        int ans = max_flow(s, t);
        cout << ans << endl;
    }

    return 0;
}





























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

int main(){
	int r=0;
	char a[3];
	cin>>a;
    if(a[0]=='R' && a[1]=='R' && a[2]=='R')
       cout<<"3"<<endl;
    else if(a[0]=='R' && a[1]=='R' ||a[1]=='R' && a[2]=='R'){
    	cout<<"2"<<endl;
	}else if(a[0]=='S' && a[1]=='S' && a[2]=='S'){
		cout<<"0"<<endl;
	}else{
		cout<<"1"<<endl;
	}   
}

Measured memory_bytes: 3632
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=3000005,M=998244353;
int fac[N],inv[N],n,m,ans;
int ksm(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%M)
		if (y&1)(ans*=x)%=M;
	return ans;	
}
int C(int x,int y){
	if (x<y)return 0;
	return fac[x]*inv[y]%M*inv[x-y]%M;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	fac[0]=inv[0]=1;
	for (int i=1;i<N;i++)fac[i]=fac[i-1]*i%M,inv[i]=ksm(fac[i],M-2);
	for (int i=m&1;i<=m;i+=2)
		(ans+=C(n+(3*m-i)/2-1,n-1)*C(n,i))%=M;
	for (int i=m&1;i<=m;i+=2)
		(ans+=M-n*C(n+(m-i)/2-1,n-1)%M*C(n,i)%M)%=M;
	n--;
	for (int i=m&1;i<=m;i+=2)
		(ans+=(n+1)*C(n+(m-i)/2-1,n-1)%M*C(n,i)%M)%=M;		
	printf("%lld\n",ans);
	return 0;
} 

Measured memory_bytes: 47232
import java.util.Scanner;

class Main {

	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int N = sc.nextInt(),i, h[] = new int[N],K=sc.nextInt();
		for(i=0;i<N;i++)h[i]=sc.nextInt();
		int dp[]=new int[N+1];
		dp[0]=0;
		for(i=1;i<N;i++) {
			dp[i]=dp[i-1]+Math.abs(h[i]-h[i-1]);
			for(int k=1;k<=Math.min(K, i);k++) {
				dp[i]=Math.min(dp[i-k]+Math.abs(h[i]-h[i-k]), dp[i]);
			}
		}
		System.out.println(dp[N-1]);
	}
}

Measured memory_bytes: 58952
#include <bits/stdc++.h>
using namespace std;
int main(){
    int d, n;
    cin >> d >> n;
    if (n != 100){
        cout << (long long int) (pow(100, d) * n) << endl;
    }
    else{cout << (int) pow(100, d) * 101 << endl;}
    return 0;
}

Measured memory_bytes: 3688
#include <bits/stdc++.h>
#define rep(i, a, b) for(int i = a; i < b; i++)
#define Rep(i, a, b) for(int i = a; i <= b; i++)
#define _GLIBCXX_DEBUG
#define Vl vector<ll>
#define Vs vector<string>
#define ll long long
#define ALL(v) (v).begin(),(v).end()
using namespace std;


void solve(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    ll n; cin >> n;
    Vl A1(n), A2(n);
    rep(i, 0, n) cin >> A1[i];
    rep(i, 0, n) cin >> A2[i];

    ll ans = 0;
    rep(i, 0, n){
        ll a = 0;
        Rep(j, 0, i) a += A1[j];
        rep(j, i, n) a += A2[j];
        ans = max(ans, a);
    }

    cout << ans << "\n";
}


int main() {
    solve();
}


Measured memory_bytes: 256
#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <numeric>
#include <queue>
#include <deque>
#include <cmath>
#include <iomanip>
#include <cstdio>
#include <limits>
#include <climits>

using namespace std;

int main(){
    int n; cin >> n;
    vector<int> as(n);
    for(int i=0; i<n; ++i){
        cin >> as[i];
    }
    int ans=0;
    int target=1;
    for(int i=0; i<n; ++i){
        if(as[i]==target) ++target;
        else ++ans;
    }
    if(ans==n) ans=-1;
    cout << ans << endl;
    return 0;
}


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

#define pi 3.141592654
#define fix(n) cout << fixed << setprecision(n)

#define rep(i,a,b) for(int i=a;i<b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)

#define ll  long long
#define ull unsigned long long

#define mp make_pair
#define pb push_back
#define fi first
#define se second

#define vi      vector<int>
#define pii     pair<int,int>
#define piii    pair<pair<int,int>,int>
#define all(v)  v.begin(), v.end()

int mod = 1000000007;
const int N = 1005;

// gcd
ll gcd(ll a , ll b)
{
    if ( b == 0)
    return a;
    return gcd( b, a % b);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int k;
	cin >> k;
	ll a[k+1];
	for ( int i = 0; i < k; i++)
	{
		cin >> a[i];
	}
	ll l = 2, r = 2;
	for ( int i = k - 1; i >= 0; i --)
	{
		ll L = (l + a[i] - 1) / a[i] * a[i], R = r / a[i] * a[i];
		if ( L > R)
		{
			cout << "-1";
			return 0;
		}
		l = L;
		r = R + a[i] - 1;
	}
	cout << l << " " << r << endl;
	
	return 0;
}


Measured memory_bytes: 1152