akhauriyash/Code-Regression huggingface dataset:
//g++  7.4.0

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MOD 1000000007
ll dp[MAXN][2];
vector<ll> adj[MAXN];

void DFS(ll s,ll p)
{
    dp[s][0] = 1;
    dp[s][1] = 1;
    
    for(auto it: adj[s])
    {
        ll v = it;
        if(v != p)
        {
            DFS(v,s);
            
            dp[s][0] = (dp[s][0] * dp[v][1])%MOD;
            dp[s][1] = (dp[s][1] * (dp[v][1] + dp[v][0])) % MOD;
            
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ll N; cin>>N;
    for(ll i=0;i<(N - 1);++i)
    {
        ll u,v; cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    DFS(1,-1);
    
    cout<<(dp[1][0] + dp[1][1])%MOD<<endl;
}

Measured memory_bytes: 17496
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SEP " \r\n"
// https://abc096.contest.atcoder.jp/tasks/abc096_b

//--------------------------------------------------------------
int main(){

	char instr[1000];
	char *sa[3];
	int v[3], t, maxp, i;

	fgets(instr, sizeof(instr), stdin);
	sa[0] = strtok(instr, SEP);
	sa[1] = strtok(NULL, SEP);
	sa[2] = strtok(NULL, SEP);
	v[0] = atoi(sa[0]);
	v[1] = atoi(sa[1]);
	v[2] = atoi(sa[2]);

	maxp = 0;
	if(v[1] > v[0]) maxp=1;
	if(v[2] > v[maxp]) maxp=2;

	fgets(instr, sizeof(instr), stdin);
	sa[0] = strtok(instr, SEP);
	t = atoi(sa[0]);

	for(i=0; i<t; i++){
		v[maxp] += v[maxp];
	}

	printf("%d\n", v[0]+v[1]+v[2]);

	return(0);
}


Measured memory_bytes: 128
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <ctype.h>
#include <stdint.h>
#include <string.h>
#include <wchar.h>
#include <math.h>

#define N_MAX (100)
#define P_MAX (100)
#define DP_ARRAY_SIZE (N_MAX * P_MAX / 32 + 1)

#define MIN(a, b) ((a) < (b) ? (a) : (b))
#define MAX(a, b) ((a) > (b) ? (a) : (b))
#define ABS(a) ((a) < 0 ? -(a) : (a))
#define ABSS(a, b) ((a) > (b) ? (a) - (b) : (b) - (a))

int compare_sz_asc(const void* a, const void* b) {
    return *((size_t*)a) < *((size_t*)b) ? -1 : 1;
}

int compare_sz_desc(const void* a, const void* b) {
    return *((size_t*)a) > * ((size_t*)b) ? -1 : 1;
}

int compare_i64_asc(const void* a, const void* b) {
    return *((int64_t*)a) < *((int64_t*)b) ? -1 : 1;
}

int compare_i64_desc(const void* a, const void* b) {
    return *((int64_t*)a) > * ((int64_t*)b) ? -1 : 1;
}

int compare_c_asc(const void* a, const void* b) {
    return *((char*)a) < *((char*)b) ? -1 : 1;
}

int compare_c_desc(const void* a, const void* b) {
    return *((char*)a) > * ((char*)b) ? -1 : 1;
}

static size_t powSz(const size_t base, const size_t exp) {
    if (exp == 0) {
        return 1;
    }

    if (exp == 1) {
        return base;
    }

    if (exp % 2 == 0) {
        return powSz(base * base, exp / 2);
    }
    else {
        return base * powSz(base, exp - 1);
    }
}

static size_t comb(const size_t n, const size_t r) {
    size_t result = 1;

    for (size_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static uint64_t combU64(const uint64_t n, const uint64_t r) {
    uint64_t result = 1;

    for (uint64_t i = 0; i < r; i++) {
        result *= n - i;
        result /= i + 1;
    }

    return result;
}

static size_t gcdZu(size_t m, size_t n) {
    size_t temp;

    while (m % n != 0) {
        temp = n;
        n = m % n;
        m = temp;
    }

    return n;
}

static uint64_t gcdU64(uint64_t m, uint64_t n)
{
    uint64_t temp;

    while (m % n != 0) {
        temp = n;
        n = m % n;
        m = temp;
    }

    return n;
}

static uint64_t A[100001];
static uint64_t B[100000];

int main(void) {
    uint64_t N;

    scanf("%"PRIu64, &N);
    for (uint64_t i = 0; i < N + 1; i++) {
        scanf("%"PRIu64, &(A[i]));
    }
    for (uint64_t i = 0; i < N; i++) {
        scanf("%"PRIu64, &(B[i]));
    }

    uint64_t sum = 0;
    for (uint64_t i = 0; i < N; i++) {
        if (A[i] <= B[i]) {
            sum += A[i];
            sum += MIN(A[i + 1], B[i] - A[i]);
            A[i + 1] -= MIN(A[i + 1], B[i] - A[i]);
        }
        else {
            sum += B[i];
        }
    }

    printf("%"PRIu64, sum);

    return 0;
}


Measured memory_bytes: 1792
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
import heapq
import math
import fractions
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

N, M = getNM()
if N == 1 and M == 1:
    print(1)
elif N == 1:
    print(M - 2)
elif M == 1:
    print(N - 2)
else:
    print((N - 2) * (M - 2))

Measured memory_bytes: 64620
import java.io.BufferedReader
import java.io.InputStream
import java.io.InputStreamReader
import java.io.PrintWriter
import java.lang.StringBuilder
import java.util.*

fun PrintWriter.solve(sc: FastScanner) {
    var x = sc.nextLong()
    var ans = 0L
    ans += x / 500 * 1000
    x %= 500
    ans += x / 5 * 5
    println(ans)
}

fun main(args: Array<String>) {
    val writer = PrintWriter(System.out, false)
    writer.solve(FastScanner(System.`in`))
    writer.flush()
}

class FastScanner(s: InputStream) {
    private var st = StringTokenizer("")
    private val br = BufferedReader(InputStreamReader(s))

    fun next(): String {
        while (!st.hasMoreTokens()) st = StringTokenizer(br.readLine())

        return st.nextToken()
    }

    fun nextInt() = next().toInt()
    fun nextLong() = next().toLong()
    fun nextLine() = br.readLine()
    fun nextDouble() = next().toDouble()
    fun ready() = br.ready()
}


Measured memory_bytes: 29468
/**
 * Author: Martin Leshko (leshko.martin@gmail.com)
 */
#include <bits/stdc++.h>

using namespace std;

const int N = 1000006, mod = 1000000007;

#define int long long

int factorial[N];

int bpow(int a, int step) {
  if (step == 0) {
    return 1;
  } else if(step & 1) {
    return bpow(a, step - 1) * a % mod;
  } else {
    return bpow(a * a % mod, step / 2);
  }
}

int Cnk(int n, int k) {
  if (n < k) {
    return 0;
  } else {
    return factorial[n] * bpow(factorial[k], mod - 2) % mod *
           bpow(factorial[n - k], mod - 2) % mod;
  }
}

void gen() {
  factorial[0] = factorial[1] = 1;
  for (int i = 2; i <= N; i++) {
    factorial[i] = factorial[i - 1] * i % mod;
  }
}

int32_t main() {
  gen();
  int x, y;
  cin >> x >> y;
  if ((x + y) % 3 != 0) {
    cout << 0 << endl;
    exit(0);
  }
  int n = (x + y) / 3, m = abs(x - y);
//  cout << n << " " << m << endl;
  int ans = Cnk(n, m + (n - m) / 2);
  cout << ans << endl;
  return 0;
}


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

using namespace std;

using ll = long long;
constexpr int mo = 1e9+7;
constexpr int inf = 1<<30;
constexpr ll infl = 1ll<<60;
constexpr ll mo2 = 998244353;
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    
    ll n;
    cin>>n;
    queue<ll> q;
    for(ll i=1;i<=9;++i)q.push(i);
    ll count = 0;
    while(!q.empty()){
        ll cur = q.front();q.pop();
        count++;
        if(count == n){
            cout << cur << endl;
            return 0;
        }
        if(cur%10 > 0)q.push(cur*10+cur%10-1);
        q.push(cur*10+cur%10);
        if(cur%10 < 9)q.push(cur*10+cur%10+1);
    }
    return 0;
}

Measured memory_bytes: 1792
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAXN 2010
#define MO 1000000007
#define LL long long
int n,m,k,M,N,K;
LL dp[MAXN*2][MAXN],ans;
int main()
{
	scanf("%d%d%d",&n,&m,&k);
	for(int i=0;i<=m;i++)
		dp[0][i]=1;
	M=m%(k-1);
	N=(n-1)%(k-1);
	K=(n+m-1)/(k-1);
	for(int i=1,ed=k-1;i<=K;ed+=k-1,i++)
	{
		for(int j=0;j<=m&&j<=ed;j++)
		{
			if(j-k+1<=0)
				dp[i][j]=dp[i-1][j];
			else dp[i][j]=dp[i-1][j]-dp[i-1][j-k];
			if(j%(k-1)==M&&j&&ed-j<n&&(ed-j)%(k-1)==N)
			{
				if(j-k+1<=0)
					ans+=dp[i-1][j-1];
				else ans+=dp[i-1][j-1]-dp[i-1][j-k];
				ans=(ans%MO+MO)%MO;
			}
			if(j!=0)
				dp[i][j]+=dp[i][j-1];
			dp[i][j]=(dp[i][j]%MO+MO)%MO;
		}
		for(int j=ed+1;j<=m;j++)
			dp[i][j]=dp[i][j-1];
	}
	printf("%lld\n",ans);
}

Measured memory_bytes: 62976
#include<bits/stdc++.h>
using namespace std;
int main(){
  string s,t;
  cin>>s>>t;
  int n=s.size();
  for(int i=0;i<n;i++){
    if(s[i]!=t[i]){
      cout<<"No"<<endl;
      return 0;
    }
  }
  cout<<"Yes"<<endl;
  return 0;
}
       
  

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


int main(){
    ll A ,B , C , K;
    ll a,b,c;
    cin >> A >> B >> C >> K;
    
    if(K % 2 == 0){
        cout << A - B << endl;
    }else {
        cout << B - A << endl;
    }
    


}


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

string s,t;
int dp[3100][3100];
string ans[3100];

int main(){
cin >>s >>t;
int S=s.size(),T=t.size();
for (int i=0;i<S;i++){
  int cnt=0,maxv=-1;
  for (int j=0;j<T;j++){
    if (s[i]==t[j] && cnt>=maxv && cnt>=dp[i][j]){
      dp[i][j]=cnt+1;
      maxv=cnt+1;
    }
    else {
      cnt=max(cnt,dp[i][j]);
    }
    dp[i+1][j]=dp[i][j];
  }

}

for (int i=1;i<3100;i++){
  ans[i]="";
}
int x=S-1,y=0,maxv;
for (int j=0;j<T;j++){
  if (dp[x][y]<dp[x][j])
    y=j;
}
int cnt=dp[x][y];
ans[dp[x][y]]=s[x];

while (cnt){
  while (dp[x][y]!=cnt){
    y--;
  }
  while (dp[x-1][y]==cnt){
    x--;
  }
  ans[cnt]=t[y];
  cnt--;
}

int i=1;
while (ans[i]!=""){
  cout<<ans[i];
  i++;
}

return 0;
}


Measured memory_bytes: 37248
#include <bits/stdc++.h>
#define rep(n) for (int I = 0; (I) < (n); ++(I) )
#define repeat(i, n) for( int i = 0; (i) < (n); ++(i) )
#define repeat_to(i, n) for( int i = 0; (i) <= (n); ++(i) )
#define repeat_from(i, m, n) for( int i = (m); (i) < (n); ++(i) )
#define repeat_from_to(i, m, n) for( int i = (m); (i) <= (n); ++(i) )
#define repeat_from_reverse(i, m, n) for( int i = (n) - 1; (i) >= (m); --(i) )
#define dump(x) cout << " " << #x << "=" << x
#define vdump(v) for(size_t t=0; t<v.size(); ++t){cout << " " << #v << "[" << t << "]=" << v[t];} cout << endl
using namespace std;
using lint = long long;
using ld = long double;

int main(void) {
    string s;
    cin >> s;
    s[13] = s[5] = ' ';
    cout << s << endl;
    return 0;
}


Measured memory_bytes: 256
using System;
using System.Collections.Generic;
using System.IO;
class Program
{
	static void Main(string[] args)
	{
		int N = int.Parse(Console.ReadLine());
		var dic = new Dictionary<string,int>();
		int max = 0;
		for(var i=0;i<N;i++){
			string s1 = Console.ReadLine();
			if(dic.ContainsKey(s1)){
				dic[s1]++;
				max = Math.Max(max,dic[s1]);
			} else {
				dic[s1] = 1;
				max = Math.Max(1,max);
			}
		}
		var ans = new List<string>();
		foreach(var i1 in dic.Keys){
			if(dic[i1]==max){
				ans.Add(i1);
			}
		}
		ans.Sort(StringComparer.OrdinalIgnoreCase);
		var sw = new StreamWriter(Console.OpenStandardOutput()){AutoFlush = false};
		Console.SetOut(sw);
		for(var i=0;i<ans.Count;i++){
			Console.WriteLine(ans[i]);
		}
		Console.Out.Flush();
	}
}


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

using namespace std;
using lli = int_fast64_t;
using ulli = uint_fast64_t;
#define debug(x) cerr << #x << " : " << x << endl
#define debugv(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x << ", ";}cerr << endl
#define debugst(x) auto xt = x;cerr << #x << " : {";for(int i=0;i<x.size();i++){ cerr << xt.top() << ", ";xt.pop();}cerr << endl
#define debugvp(x) cerr << #x << " : {";for(auto value_of_x:x){ cerr << value_of_x.first << " : " << value_of_x.second << ", ";}cerr << endl
#define HYPP(x) hypot(x.first,x.second)

const lli MOD = 998244353;
const lli LIMIT = 1000000000000000000 * 5;
const int tenfive = 100000;


int main() {
	string s;
	cin >> s;
	stack<char> st;

	for (int i = 0; i < s.size(); i++) {
		if (s[i] == 'B') {
			if(!st.empty())
			st.pop();
		}
		else {
			st.push(s[i]);
		}
		
	}
	string ans;
	while (!st.empty()) {
		ans += st.top(); st.pop();
	}

	reverse(ans.begin(), ans.end());
	cout << ans << endl;
	return 0;
}


Measured memory_bytes: 256
import Control.Monad (forM_)
import Data.List (sort)

main :: IO ()
main = do
  n <- read <$> getLine :: IO Int
  xs <- map read.words <$> getLine :: IO [Int]
  let sorted = sort xs
      med0 = sorted!!(n`div`2-1)
      med1 = sorted!!(n`div`2)
  forM_ xs $ \x ->
    print $ if x < med1 then med1 else med0


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

using namespace std;

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

  int start = -1;
  for (int i = S.length() -1; i >= 0; i--) {
    if (i + T.length() > S.length()) {
      continue;
    }
    bool find = true;
    for (int j = 0; j < T.length(); j++) {
      if (S[i + j] == '?' || S[i + j] == T[j]) {
        continue;
      }
      find = false;
    }
    if (find) {
      start = i;
      break;
    }
  }
  if (start == -1) {
    cout << "UNRESTORABLE" << endl;
    return 0;
  }
  for (int i = 0; i < S.length(); i++) {
    if (i < start || start + T.length() <= i) {
      if (S[i] == '?') {
        cout << 'a';
      } else {
        cout << S[i];
      }
    } else {
      cout << T[i - start];
    }
  }
  cout << endl;
  return 0;
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES
#include <iostream>
#include <string>
#include <list>
#include <vector>
#include <queue>
#include <algorithm>
#include <climits>
#include <cstring>
#include <cmath>
#include <stack>
#include <iomanip>
#include <tuple>
#include <functional>
#include <deque>
#include <bitset>

#define int long long
#define CONTAINS(v,n) (find((v).begin(), (v).end(), (n)) != (v).end())
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())
#define ARY_SORT(a, size) sort((a), (a)+(size))
#define MAX(a,b) (((a) > (b)) ? (a) : (b))
#define MIN(a,b) (((a) < (b)) ? (a) : (b))
#define REMOVE(v,a) v.erase(remove(v.begin(), v.end(), a), v.end())
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define REPE(i, n) for (int (i) = 0; (i) <= (n); (i)++)
using namespace std;

int Q;

int func(int a, int b)
{
	int sum = 0;

	sum += (a - 1) * 2;

	int min = 0;
	int max = (b - 1 - a) + 1;
	while (true)
	{
		int x = ((max - min) / 2) + min;

		if (max - min <= 1)
		{
			sum += b - 1 - a - x;
			return sum;
		}

		int n = MAX(0, (((a + 1) + (b - 1 - x)) / 2) - (a + 1));
		int k = (a + 1 + n) * (b - 1 - n - x);

		if (k >= a * b)
		{
			min = x;
		}
		else
		{
			max = x;
		}
	}
}

signed main()
{
	cin >> Q;
	REP(i, Q)
	{
		int a_, b_;
		cin >> a_ >> b_;

		int a = MIN(a_, b_);
		int b = MAX(a_, b_);

		if (a == b)
		{
			cout << (2 * a - 2) << endl;
		}
		else if (a == b - 1)
		{
			cout << (2 * a - 2) << endl;
		}
		else
		{
			cout << func(a, b) << endl;
		}
	}
}


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

int main(){
  string s;
  cin>>s;
  if(s[2]==s[3] and s[4]==s[5])cout<<"Yes"<<endl;
  else cout<<"No"<<endl;
  
  return 0;
}

Measured memory_bytes: 3628
#include<iostream>
#include <string> // string, to_string, stoi
#include <vector> // vector
#include <algorithm> // min, max, swap, sort, reverse, lower_bound, upper_bound
#include <utility> // pair, make_pair
#include <tuple> // tuple, make_tuple
#include <cstdint> // int64_t, int*_t
#include <cstdio> // printf
#include <map> // map
#include <queue> // queue, priority_queue
#include <set> // set
#include <stack> // stack
#include <deque> // deque
#include <unordered_map> // unordered_map
#include <unordered_set> // unordered_set
#include <bitset> // bitset
#include <cctype> // isupper, islower, isdigit, toupper, tolower
#include <iomanip>//setprecision
#include<math.h>
#include <functional>
#include<climits>
using namespace std;
#define rep(i, n)        for(int i=0; i<(int)(n); ++i)
int main(){ 
  long long int a,b,c=0,e=INT_MAX,f=0;
  cin>>a>>b;
  vector<long long int>d(a);
  rep(i,a){
    cin>>d[i];
  }
  rep(i,a-1){
    c+=max(d[i]+d[i+1]-b,f);
      //cout<<max(d[i]+d[i+1]-b,0);
    if(d[i]+d[i+1]-b>0)d[i+1]=max(f,d[i+1]-(d[i]+d[i+1]-b));
  }
  cout<<c;
  }


Measured memory_bytes: 1024
#include <bits/stdc++.h>
    #define ll long long
    #define mod 1000000007
    using namespace std;

    int main() {
        int n,a[100010],ans=0;
        bool up,down,flag;
        flag = false;
        up=false;
        down=false;
        cin >> n;
        for(int i=0;i<n;i++)cin >> a[i];
        for(int i=0;i<n;i++){
            if(i==0){
                flag=true;
                continue;
            }
            if(a[i-1] - a[i]>0){
                if(down==true)continue;
                if(up==false&&down==false){
                    flag=true;
                    down=true;
                    continue;
                }
                if(up==true){
                    ans++;
                    up=false;
                }
            }else if(a[i-1]-a[i]<0){
                if(up==true)continue;
                if(up==false&&down==false){
                    flag=true;
                    up=true;
                    continue;
                }
                if(down==true){
                    ans++;
                    down=false;
                }
            }else{
                flag=true;
            }
        }
        if(flag)ans++;
        cout << ans << endl;
    }

Measured memory_bytes: 640
import math
A,B,H,M = map(int,input().split())

#各針の回転角を求める
omega = H*60+M
tanshin = omega*0.5
choshin = omega*6 % 360
#print(tanshin,choshin)#それぞれの，その時間での角度も止まる
#print(max(tanshin,choshin)-min(tanshin,choshin)) 

shita = max(tanshin,choshin)-min(tanshin,choshin)
if shita > 180:
    shita = 360 - shita

#print(shita)
ans = math.sqrt(A**2+B**2-2*A*B*math.cos(math.radians(shita)))
print(ans)

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

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

  int K, P;
  for (int i = 0; i < N; i++) {
    cin >> K >> P;
    if (K % P == 0) {
      cout << P << endl;
    } else {
      cout << K % P << endl;
    }
  }

  return 0;
}


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


def prime_factorize(n):
    r = set()
    while n % 2 == 0:
        r.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.add(n)
    return r


j = 0
a1 = set()
a2 = prime_factorize(A[0])
for a in A[1:]:
    tmp = prime_factorize(a)
    if a1 & tmp:
        j = 1
    a1 |= tmp
    a2 &= tmp
if a2:
    print('not coprime')
elif j:
    print('setwise coprime')
else:
    print('pairwise coprime')


Measured memory_bytes: 189632
#include<bits/stdc++.h>
using namespace std;
#define ll unsigned long long int

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

    int t;
    t=1;

    while(t--){
        int n,x,t;
        cin>>n>>x>>t;

        int ans=n/x;

        if((ans*x)==n)
            cout<<t*ans<<endl;
        else
            cout<<t*(ans+1)<<endl;
    }
    return 0;
}





Measured memory_bytes: 3640
import fractions

N, M = map(int, input().split())
S = input()
T = input()

if N == M:
    print(N if S == T else -1)
else:
    G = fractions.gcd(N, M)
    L = N * M // G
    n = N // G
    m = M // G
    ans = True
    for k in range(G):
        if S[k * n] != T[k * m]:
            ans = False
            break
    print(L if ans else -1)


Measured memory_bytes: 5428
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[10000000];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll k, n;
    cin >> k >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> a[i];
    }
    ll minn = a[n] - a[1];
    for(int i = 2; i <= n; i++)
    {
        ll w = a[i - 1] - a[i] + k;
        //cout << w << " " << i << "\n";
        minn = min(minn, w);
    }
    cout << minn << "\n";
    return 0;
}


Measured memory_bytes: 1792
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define PI 				acos(-1)
#define mp				make_pair
#define pb				push_back
#define all(a)			(a).begin(), (a).end()
#define srt(a)			sort(all(a))
#define mem(a, h)		memset(a, (h), sizeof(a))
#define f 				first
#define s 				second
#define MOD				1000000007
#define MOD1			998244353
#define EPS				1e-9
#define fore(i, b, e)	for(int i = b; i < e; i++)
#define forg(i, b, e, m)	for(int i = b; i < e; i+=m)
int in(){int r=0,c;for(c=getchar();c<=32;c=getchar());if(c=='-') return -in();for(;c>32;r=(r<<1)+(r<<3)+c-'0',c=getchar());return r;}

using namespace std;
using namespace __gnu_pbds;

typedef long long 		ll;
typedef unsigned long long 		ull;
typedef pair<int, int>  ii;
typedef vector<int>     vi;
typedef vector<ii>      vii;
typedef vector<ll>      vll;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const int tam = 100010;
int main()
{
	ios::sync_with_stdio(0); cin.tie(0);
	//freopen("qwe.txt", "r", stdin);
	//freopen("asd.txt", "w", stdout);
	string a, b;
	map<int, int> maa, mab;
	cin>>a>>b;
	int con = 1;
	fore(i, 0, a.size())
	{
		if(maa[a[i]] == 0)
		{
			maa[a[i]] = con;
			con++;
		}
	}
	con = 1;
	fore(i, 0, a.size())
	{
		if(mab[b[i]] == 0)
		{
			mab[b[i]] = con;
			con++;
		}
	}
	fore(i, 0, a.size())
	{
		a[i] = maa[a[i]];
		b[i] = mab[b[i]];
	}
	if(b == a)
		cout<<"Yes\n";
	else
		cout<<"No\n";
	return 0;
}

// read the question correctly (is y a vowel? what are the exact constraints?)
// look out for SPECIAL CASES (n=1?) and overflow (ll vs int?) ARRAY OUT OF BOUNDSS2

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

#define all(x) x.begin(), x.end()

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
 
const int Maxn = 5e3 + 10;
const ll Inf = 0;
const int Log = 20;
const ll Mod = 1e9 + 7;

ll mul(ll a, ll b){
	return (a * b) % Mod;
}

ll bin_pow(ll b, ll p){
	ll res = 1;
	for(ll pw = b, j = 1; j <= p; j <<= 1, pw = mul(pw, pw)) if(p & j) res = mul(res, pw);
	return res;
}
ll inv(ll x){
	return bin_pow(x, Mod - 2);
}

ll p2[Maxn];
ll dp[2][Maxn];

int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	p2[0] = 1;
	for(int i = 1; i < Maxn; i++) p2[i] = mul(p2[i - 1], 2);
	
	int n;
	cin >> n;
	dp[0][0] = 1;
	for(int i = 1; i <= n; i++){
		int ii = i & 1;
		memset(dp[ii], 0, sizeof dp[ii]);
		for(int j = 0; j <= i; j ++){
			dp[ii][j] = 0;
			// write
			if(j) dp[ii][j] += (2LL * dp[ii ^ 1][j - 1]);
			// erase
			dp[ii][j] += dp[ii ^ 1][j + 1];
			if(j == 0) dp[ii][j] += dp[ii ^ 1][j];
			
			dp[ii][j] %= Mod;
		}
	}
	string s;
	cin >> s;
	int m = s.size();
	cout << mul(dp[n & 1][m], inv(p2[m])) << '\n';
	return 0;
}

Measured memory_bytes: 512
// B - Palindrome-phobia
// https://atcoder.jp/contests/cf17-final/tasks/cf17_final_b
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define uli unsigned long long int
#define rep(i, m, n) for (lli i = m; i < (n); i++)
#define repe(i, m, n) for (lli i = m; i <= (n); i++)
#define ALL(x) (x).begin(), (x).end()
#define SIZE(x) ((lli)(x).size())
#define MAX(x) *max_element(ALL(x))
#define MIN(x) *min_element(ALL(x))
#define _GLIBCXX_DEBUG
const lli INF = 2147483647;
const lli MINF = -2147483648;
const lli LINF = 9223372036854775807;
const lli MOD = 1000000007; //10^9+7
const double PI = acos(-1);
#define SORT(n) sort(n.begin(), n.end())
#define SORTR(n) sort(n.begin(), n.end(), greater<int>())
#define REV(n) reverse(n.begin(), n.end())
#define pb push_back
#define eb emplace_back
#define mp make_pair
#pragma GCC optimize("Ofast")
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vlli = vector<lli>;
using vvli = vector<vlli>;
using vs = vector<string>;
using vvs = vector<vs>;
using vb = vector<bool>;
using vvb = vector<vb>;
using ll = long long;
// vector入力
template <typename T>
istream &operator>>(istream &is, vector<T> &vec)
{
  for (T &x : vec)
    is >> x;
  return is;
}
// vector出力
template <typename T>
ostream &operator<<(ostream &os, vector<T> &vec)
{
  // os << '{';
  for (int i = 0; i < vec.size(); i++)
  {
    os << vec[i] << (i + 1 == vec.size() ? "" : "");
  }
  // os << '}';
  return os;
}
// aよりもbが大きいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmax(T &a, const T &b)
{
  if (a < b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}
// aよりもbが小さいならばaをbで更新する(更新されたならばtrueを返す)
template <typename T>
bool chmin(T &a, const T &b)
{
  if (a > b)
  {
    a = b; // aをbで更新
    return true;
  }
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  lli a, b, c, h, n, w, ans = 0, count = 0;
  string s, t;
  vector<pair<string, pair<lli, lli>>> pr;
  cin >> s;
  n = s.size();
  vlli d(26, 0);
  set<char> g;
  rep(i, 0, n)
  {
    for (char x = 'a'; x <= 'z'; x++)
    {
      if (s[i] == x)
      {
        d[count]++;
      }
      count++;
    }
    count = 0;
  }
  rep(i, 0, 26)
  {
    if (d[i] > 0 && 3 * (d[i] - 1) >= n)
    {
      cout << "NO" << endl;
      return 0;
    }
  }
  cout << "YES" << endl;
}

Measured memory_bytes: 3784
ary = list(input())
s1 = []
s = 0

s2 = []

cnt = 0
for _ in ary:

    if _ == '\\':
        s1.append(cnt)
        cnt += 1

    elif _ == '/':
        if s1:
            old_cnt = s1.pop()
            area = cnt - old_cnt
            s += area

            while s2:
                if old_cnt < s2[-1][0]:
                    area += s2.pop()[1]
                else:
                    break

            s2.append((old_cnt, area))

        cnt += 1

    else:
        cnt += 1

print(s)
print(len(s2), *[_[1] for _ in s2])


Measured memory_bytes: 6444
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#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) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define Would
#define you
#define please


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

	
	int N;
	cin >> N;

	map<int, int> MAP;
	rep(i, N) {
		int A;
		cin >> A;
		MAP[A]++;
	}

	int kotae = N;
	int guusuu = 0;
	for (auto itr : MAP) {
		if (itr.second % 2) {
			kotae -= itr.second - 1;
		}
		else if (itr.second){
			kotae -= itr.second - 2;
			guusuu++;
		}
	}
	kotae -= ((guusuu + 1) / 2) * 2;

	co(kotae);

	Would you please return 0;
}

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

using namespace std;
using ll = long long;

int main() {
    int n = 0;
    cin >> n;
    vector<int> p(n);
    vector<int> q(n);
    vector<int> v(n);
    for(int i = 0;i < n;i++){
        cin >> p[i];
        v[i] = i + 1;
    }
    for(int i = 0;i < n;i++){
        cin >> q[i];
    }
    int cnt = 0;
    int a,b = 0;
    do{
        bool flag = true;
        cnt ++;
        for(int i = 0;i < n;i++){
            if(p[i] == v[i]){
                
            }else{
                flag = false;
                break;
            }
        }
        if(flag){
            a = cnt;
            break;
        } 
    }while(next_permutation(v.begin(),v.end()));
    sort(v.begin(),v.end());
cnt = 0;
    do{
        bool flag = true;
        cnt ++;
        for(int i = 0;i < n;i++){
            if(q[i] == v[i]){
                
            }else{
                flag = false;
                break;
            }
        }
        if(flag){
            b = cnt;
            break;
        } 
    }while(next_permutation(v.begin(),v.end()));
    
    cout << abs(a - b) << endl;
    return 0;
}

Measured memory_bytes: 256
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
uvs = [None]*(n-1)
for i in range(n-1):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
    uvs[i] = (u,v)
c = list(map(int, input().split()))
c.sort()
q = [0]
ans = [None]*n
i = 0
def sub(u, prev):
    global i
    for v in ns[u]:
        if prev==v:
            continue
        sub(v, u)
    ans[u] = c[i]
    i += 1
sub(0, -1)
val = 0
for u,v in uvs:
    val += min(ans[u], ans[v])
print(val)
write(" ".join(map(str, ans)))

Measured memory_bytes: 84972
#import<bits/stdc++.h>
using namespace std;
double a,b,c,i,j,k,l,m,n,s,x,y,z,w[105];
main()
{
scanf("%lf%lf%lf%lf",&a,&b,&x,&y);
printf("%g %d",a*b/2,x*2==a&y*2==b);
}

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

using namespace std;

//入力
string s;

int eval(const string& s, int& pos) {
	// 定数の場合
	if (s[pos] == '0' || s[pos] == '1' || s[pos] == '2') {
		int v = s[pos] - '0';
		pos++;
		return v;
	}
	
	// マイナス符号の場合
	if (s[pos] == '-') {
		pos++;
		int v = eval(s, pos);
		return 2 - v;
	}
	
	if (s[pos] == '(') {
		int v;
		pos++;
		int tmp1 = eval(s, pos);
		if (s[pos] == '+') {
			pos++;
			int tmp2 = eval(s, pos);
			v = max(tmp1, tmp2);
		} else if (s[pos] == '*') {
			pos++;
			int tmp2 = eval(s, pos);
			v = min(tmp1, tmp2);
		}
		pos++;
		return v;
	}
}

void solve() {
	int ans = 0;
	
	for (int p = 0; p <= 2; p++) {
		for (int q = 0; q <= 2; q++) {
			for (int r = 0; r <= 2; r++) {
				string tmp = s;
				for (int i = 0; i < (int)tmp.length(); i++) {
					// P, Q, Rを定数0, 1, 2に置換する
					if (tmp[i] == 'P') {
						tmp[i] = p + '0';
					} else if (s[i] == 'Q') {
						tmp[i] = q + '0';
					} else if (s[i] == 'R') {
						tmp[i] = r + '0';
					}
				}
				int pos = 0;
				//cout << tmp << endl;
				int result = eval(tmp, pos);
				if (result == 2) {
					ans++;
				}
			}
		}
	}
	cout << ans << endl;
	
	return;
}

int main() {
	while (true) {
		getline(cin, s);
		if (s[0] == '.') {
			break;
		}
		solve();
	}
	
	return 0;
}

Measured memory_bytes: 1192
#include<bits/stdc++.h>
using namespace std;
typedef unsigned int uint;
#define MAX_N 30005

int n;
uint m;
uint t[MAX_N];
uint u[MAX_N];

int main(){
  while(1){
    cin>>n>>m;
    if(n==0&&m==0)break;
    for(int i=1;i<=n;i++){
      scanf("%u",&t[i]);
      t[i]%=m;
      u[i]=(t[i]+u[i-1])%m;
    }
    set<uint> A;
    set<uint> :: iterator it;
    uint ans=0;
    A.insert(0);
    
    for(int i=1;i<=n;i++){
      it=A.upper_bound(u[i]);
      if(it==A.end()){
        it=A.lower_bound(0);
        ans=max(ans,u[i]-(*it));
      }else{
        ans=max(ans,m+u[i]-(*it));
      }
      A.insert(u[i]);
    }
    cout<<ans<<endl;
  }
  return 0;
}

Measured memory_bytes: 2488
import collections
N,K = map(int,input().split())
A = list(map(int, input().split()))
Ni_block = 0
Ni_inter = 0
bignum = pow(10,9)+7
for i in range(N):
   for j in range(N):
      if A[i]>A[j]:
         Ni_inter += 1
         if j>i:
            Ni_block+=1
# print(Ni_inter,Ni_block)
# c = collections.Counter(A)
# N_multiple = 1
# # print(c)
# for i in c:
#    # print(i, c[i])
#    N_multiple*=c[i]
   
# print(N_multiple)
# print(len(c))
# Ndiff = len(c)
# Ni = Ni_block*K+(((K*(K-1))//2) % bignum)*(((Ni_inter*(Ni_inter-1))//2) % bignum)
Ni = Ni_block*K+(((K*(K-1))//2) % bignum)*Ni_inter
print(Ni%bignum)



Measured memory_bytes: 3572
// READ & UNDERSTAND
// ll, int overflow, array bounds
// special cases (n=1?), n+1 (1-index)
// do smth instead of nothing & stay organized
// WRITE STUFF DOWN

#include <bits/stdc++.h>

using namespace std;

#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(), (x).end() 
#define MOD 1000000007

typedef long long ll;
typedef pair <int, int> ii;
typedef pair <ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef long double ld;

ll INF=LLONG_MAX;

int const mxn=1e5+5;

struct DSU{
	vi par,siz;
	ll cntt=0;
	DSU(int n){
		for(int i=0; i<n+1; i++){
			par.pb(i);
			siz.pb(1);
		}
		cntt = ll(n)*(n-1)/2;
	}
	ll cnt(){
		return cntt;
	}
	int rt(int u){
		if(par[u]!=u)par[u]=rt(par[u]);
		return par[u];
	}
	void merge(int u, int v){
		u=rt(u); v=rt(v);
		if(u==v)return;
		if(siz[v]<siz[u])swap(u,v);
		par[u]=v;
		cntt -= (ll)siz[u] * siz[v];
		siz[v] += siz[u];
		return;
	}
	bool sameset(int u, int v){
		if(rt(u)==rt(v))return 1;
		return 0;
	}
};

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt","r",stdin); freopen("output.txt","w",stdout);
	int n,m,u,v;
	cin >> n >> m;
	vll ans; DSU dsu(n);
	vector<ii>edge;
	for(int i=0; i<m; i++){
		cin >> u >> v;
		edge.pb({u,v});
	}
	ans.pb(dsu.cnt());
	for(int i=m-1; i>0; i--){
		u = edge[i].fi;
		v = edge[i].se;
		if(!dsu.sameset(u,v)){
			dsu.merge(u,v);
		}
		ans.pb(dsu.cnt());
	}
	reverse(all(ans));
	for(ll x:ans)cout << x << endl;
}	


Measured memory_bytes: 3824
// #pragma GCC optimize("Ofast")
// #pragma GCC optimize ("unroll-loops")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace std;
using namespace __gnu_pbds;

typedef long long int ll;
#define endl '\n'
#define ld long double
#define all(a) a.begin(),a.end()
#define int long long
#define pb push_back
#define pii pair <int, int>
#define ff first
#define ss second
#define sz(v) (int)v.size() 
#define UB upper_bound
#define LB lower_bound
#define BP(x) __builtin_popcountll(x)
#define PQS priority_queue <int, vector<int>, greater<int> > 
#define OST tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update>
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int getRand(int l, int r) {
  uniform_int_distribution<int> uid(l, r);
  return uid(rng);
}

const int INF = 1e18 + 0;
const int mod = 1e9 + 7;
//const int mod = 998244353;

const int N = 3e5 + 5;
static int M;

int Data[N];

class segmentTree{
  public:
    vector <int> seg;
    int dummy;

    segmentTree(int n, int dummy) {
      M = n;
      this->dummy = dummy;
      seg.resize(4*n+1, dummy);
    }
    
    int merge(int x, int y) {
      return max(x,y);
    }

    void build(int node = 1, int s = 1, int e = M) {
      if(s == e) {
        seg[node] = Data[s];
        return;
      }
      int m = (s + e) / 2;
      build(2*node, s, m);
      build(2*node+1, m+1, e);
      seg[node] = merge(seg[2*node], seg[2*node+1]);
    }

    void update(int pos, int val, int node = 1, int s = 1, int e = M) {
      if(s == e) {
        seg[node] = max(val, seg[node]);
        return;
      }
      int m = (s+e) / 2;
      if(pos <= m) update(pos, val, 2*node, s, m);
      else update(pos, val, 2*node+1, m+1, e);
      
      seg[node] = merge(seg[2*node], seg[2*node+1]);
    }

    int query(int l, int r, int node = 1, int s = 1, int e = M) {
      if(s > r || e < l) return dummy;
      if(s >= l && e <= r) return seg[node];
      int m = (s+e) / 2;
      return merge(query(l, r, 2*node, s, m), query(l, r, 2*node+1, m+1, e));
    }
};

void solve() {
  int n, k; cin >> n >> k;
  
  int arr[n+5];

  for(int i = 1; i <= n; i++) {
     cin >> arr[i];
  }
  
  int ans = 0;
  segmentTree st(300000, 0);

  for(int i = 1; i <= n; i++) {
    int l = max(1ll, arr[i]-k), r = min(300000ll, arr[i]+k);
    int q = st.query(l,r);
    ans = max(ans, q+1);
    st.update(arr[i], 1+q);
  }

  cout << ans << '\n';
}

/*
  * overflow, array bounds
  * do smth instead of nothing and stay organized
*/
signed main() {   
  ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

  #ifndef ONLINE_JUDGE
   freopen("input.txt", "r", stdin);
   freopen("output.txt", "w", stdout);
  #endif
   int t = 1; // cin >> t;
   for(int i = 1; i <= t; i++) {
   //  cout << "Case #" << i << ": ";
     solve();
  }
}    

/*

*/

Measured memory_bytes: 15132
#include <bits/stdc++.h>
using namespace std;
#define mp(a,b) make_pair(a,b)
#define ff first
#define setp setprecision(6)<<fixed
#define ss second
#define fori(v) for(lli i=0; i<v; i++)
#define forj(v) for(int j=0; j<v; j++)
#define fork(v) for(int k=0; k<v; k++)
#define forl(v) for(int l=0; l<v; l++)
#define fort(v) for(int t=0; t<v; t++)
#define forz(v) for(int z=0; z<v; z++)
#define lli long long int
#define MAX 220020
#define ld long double
#define vi vector<int>
int inf = pow(10,9);
lli modulo = pow(10,9)+7;
double eps = 1e-11;
ifstream in;
ofstream out;
//#define cin in
//#define cout out
int arr[MAX];
int med;
lli cemi;
void div_conquer(int l, int r){
	if(l==r){
		if(arr[l] >= med)
			++cemi;
		return;
	}
	int o = (l+r)/2;
	int nece = (r-o);
	lli dif[2*nece+10] = { };
	nece+=5;
	int sy1 = 0, sy2 = 0;
	for(int i=o+1; i<=r; i++){
		if(arr[i] < med)
			++sy1;
		else
			++sy2;
		dif[(sy1-sy2)+nece]++;
	}
	nece-=5;
	for(int i=1; i<2*nece+10; i++)
		dif[i]+=dif[i-1];
	nece+=5;
	sy1 = 0, sy2 = 0;
	for(int i=o; i>=l; i--){
		if(arr[i] < med)
			++sy1;
		else
			++sy2;
		cemi+=dif[(sy2-sy1)+nece];
	}
	div_conquer(l,o);
	div_conquer(o+1,r);
}
void deal(){
	int n;
	cin>>n;
	fori(n)
		cin>>arr[i];
	int a =  0 ,b = pow(10,9);
	lli umumi = n;
	umumi = umumi*(umumi+1)/2;
	while(a<b){
		med = (a+b)/2+1;
		cemi = 0;
		div_conquer(0,n-1);
		if(cemi>=(umumi+1)/2)
			a=med;
		else
			b=med-1;
	}
	cout<<a;
}
int main() {
	deal();
}   

Measured memory_bytes: 2304
#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int main(){
  int N;
  cin >> N;
  vector<int> A(N);
  for (auto &i:A) cin >> i;
  int fst = *max_element(A.begin(), A.end());
  int flg = 0;
  for (int j = 0; j < N; j++)
    if (A[j] == fst)
      flg += 1;
  int snd = 0;
  for (int i = 0; i < N; i++)
    if (A[i] != fst && A[i] > snd)
      snd = A[i];
  for (int i = 0; i < N; i++){
    if (A[i] == fst && flg == 1)
      cout << snd << endl;
    else
      cout << fst << endl;
  }
  return 0;
}

Measured memory_bytes: 2432
#include<bits/stdc++.h>
#include <iostream>
#include <string>
#include <cmath>
using namespace std;
#define ll long long
#define rep(i, n) for (ll i = 0; i < (n); i++)
#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define FORR(i,a,b)for(ll i=(a);i<=(b);i++)
#define repR(i,n) for(ll i=n;i>=0;i--)
#define all(v)(v).begin(),(v).end()
#define rall(v)(v).rbegin(),(v).rend()
#define F first
#define S second
#define pb push_back
#define pu push
#define COUT(x) cout<<(x)<<endl
#define PQ priority_queue<ll>
#define PQR priority_queue<ll,vector<ll>,greater<ll>>
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define mp make_pair
#define maxs(x,y) (x = max(x,y))
#define mins(x,y) (x = min(x,y))
#define sz(x) (int)(x).size()
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll MOD = 1000000007LL;
const ll INF = 1LL << 60;
using vll = vector<ll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
int main(){
  ll n,m;
  cin>>n>>m;
  priority_queue<pll, vector<pll>, greater<pll>> p;
  rep(i,n){
    ll a,b;
    cin>>a>>b;
    pll o=mp(a,b);
    p.pu(o);
  }
  PQ s;
  ll ans=0;
  ll w=1;
  while(1){
    if(w==m+1) {
      break;
    }
    pll k;
    if(!p.empty()){
      k=p.top();
    }
    else k=mp(100000000,8889);
    if(w<k.F){
      if(!s.empty()){
        ll h=s.top();
        s.pop();
        ans+=h;
      }
      w++;
    }
    else{
      s.push(k.S);
      p.pop();
    }
  }
  COUT(ans);
}


Measured memory_bytes: 3568
n = int(input())
words = ['']
nums = [0]
while n > 0:
    w = input()
    if w not in words:
        words.append(w)
        nums.append(1)
    else:
        index = words.index(w)
        nums[index] += 1
    n -= 1
m = int(input())
while m > 0:
    wb = input()
    if wb in words:
        index = words.index(wb)
        nums[index] -= 1
    m -= 1
print(max(nums))

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

using pii = pair<int,int>;
using ll = long long;
#define rep(i, j) for(int i=0; i < (int)(j); i++)
#define repeat(i, j, k) for(int i = (j); i < (int)(k); i++)
#define all(v) v.begin(),v.end()
#define debug(x) cerr << #x << " : " << x << endl

template<class T> bool set_min(T &a, const T &b) { return a > b  ? a = b, true : false; }
template<class T> bool set_max(T &a, const T &b) { return a < b  ? a = b, true : false; }
// vector
template<class T> istream& operator >> (istream &is , vector<T> &v) { for(T &a : v) is >> a; return is; }
template<class T> ostream& operator << (ostream &os , const vector<T> &v) { for(const T &t : v) os << "\t" << t; return os << endl; }
// pair
template<class T, class U> ostream& operator << (ostream &os , const pair<T, U> &v) { return os << "<" << v.first << ", " << v.second << ">"; }

const int INF = 1 << 30;
const ll INFL = 1LL << 60;

template<typename T>
T gcd(T a,T b){
    T c=a,d=b,r;
    do{r=c%d;c=d;d=r;}while(r);
    return c;
}

template<typename T>
T lcm(T a,T b){return a*b/gcd(a,b);}

const ll MOD = 998244353;

ll pow(const ll n, ll r){
    if(r == 0) return 1ll;
    ll ret = pow(n, r / 2);
    ret = (ret * ret) % MOD;
    if(r % 2 != 0) ret = (ret * n) % MOD;
    return ret;
}

class Solver {
  public:
    bool solve() {
        ll N, A, B, K; cin >> N >> A >> B >> K;


        // K = KM + left
        // left % A = left % B = 0

        if(A < B) swap(A, B);
        ll l = lcm(A, B);
        ll nKM = max(0ll, K / l - 1);
        ll KM = K - nKM * l;
        assert((K - KM) % A == 0 and (K - KM ) % B == 0);
        // init
        vector<ll> factorial(max({N, A, B}) + 1);
        factorial[0] = 1;
        rep(i, factorial.size() - 1) factorial[i + 1] = (factorial[i] * (i + 1)) % MOD;
        auto nCk = [&] (ll n, ll k) {
            ll q = (factorial[k] * factorial[n - k]) % MOD;
            return factorial[n] * pow(q, MOD - 2) % MOD;
        };
        ll ans = 0;

        ll max_na = KM / A;
        set<pair<ll, ll>> s;
        for(ll na = 0; na <= max_na; na++) {
            ll a = na * A;
            if((KM - a) % B != 0) continue;
            ll nb = (KM - a) / B;
            for(ll k = 0; k <= nKM; k++) {
                ll naa = na + k * (l / A);
                ll nbb = nb + (nKM - k) * (l / B);
                if(naa <= N and nbb <= N) {
                    auto p = pair<ll, ll>(naa, nbb);
                    if(s.count(p)) continue;
                    s.insert(p);
                    // cerr << " -- " << na << " - " << nb << " - " << k << endl;
                    // cerr << naa << " v " << nbb << " : " << nCk(N, naa) * nCk(N, nbb) <<endl;
                    ans += nCk(N, naa) * nCk(N, nbb) % MOD;
                    ans %= MOD;
                }
            }
        }
        cout << ans << endl;
        return 0;
    }
};

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    Solver s;
    s.solve();
    return 0;
}


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

using namespace std;

int a, b, c, d;

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  while (cin >> a >> b >> c >> d) {
    int e = min(b, d);
    int s = max(a, c);
    cout << (e - s > 0 ? e - s : 0)<< endl;
  }
  return 0;
}


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

int main(){
    int N,M;
    cin >> N >> M;
    int a[2*M];
    int C[N]={0};

    for(int i=0;i<2*M;i++) cin >> a[i];

    for(int i=0;i<2*M;i++){
        C[a[i]-1]++;
    }

    for(int i=0;i<N;i++){
        cout << C[i] << endl;
    }

}

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

#define rep(i, n) for (int i = 0; i < (n); i++)
#define contains(v, t) (find(v.begin(), v.end(), t) != v.end())
#define MOD 1000000007
typedef long long ll;
typedef unsigned long long ull;

int main() {
  int n;
  ull k;
  cin >> n >> k;
  vector<int> a(n);
  rep(i, n) { cin >> a[i]; }
  set<int> s;
  vector<int> p(n);
  vector<int> r;

  int town = 1;
  int i = 0;
  int geta = 0;
  int mod = 1;
  while (true) {
    auto result = s.insert(town + 1);
    if (!result.second) {
      for (int j = 0;; j++) {
        if (p[j] == town) {
          //          cout << "加算: " << j << endl;
          //          cout << "周期: " << s.size() - j << endl;
          geta = j;
          mod = s.size() - j;
          break;
        }
      }
      break;
    }
    p[i] = town;
    town = a[town - 1];
    i++;
  }
  for (int i = geta; i < geta + mod; i++) {
    r.push_back(p[i]);
  }

  if (k <= geta) {
    cout << p[k];
  } else {
    cout << r[(k - geta) % mod];
  }
}

Measured memory_bytes: 14380
#include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

// 插入此處

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(0);
    int K, N; cin >> K >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    int ans = K;
    for (int i = 0; i < N-1; ++i) {
        ans = min(ans, K - A[i+1] + A[i]);
    }
    ans = min(ans, A[N-1] - A[0]);
    cout << ans << endl;
    return 0;
}


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

public final class Main {

    private static final int MOD = 998244353;

    public static void main(String[] args) {
        final Scanner in = new Scanner(new BufferedReader(new InputStreamReader(System.in)));
        final int n = in.nextInt();
        final int s = in.nextInt();
        final int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        final long[][] dp = new long[n + 1][s + 1];
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= s; j++) {
                dp[i + 1][j] += dp[i][j] * 2;
                if (j + arr[i] <= s) {
                    dp[i + 1][j + arr[i]] += dp[i][j];
                }
            }
            for (int j = 0; j <= s; j++) {
                dp[i + 1][j] %= MOD;
            }
        }
        System.out.println(dp[n][s]);
    }
}


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

int main ()
{
  int N, K;
  cin >> N >> K;
  vector<int> H(N);
  for (int i = 0; i < N; i++) cin >> H.at(i);
  sort(H.begin(), H.end());
  reverse(H.begin(), H.end());
  long long int sum = 0;
  if (K >= N) cout << 0 << endl;
  else
  {
    for (int i = K; i < N; i++) sum += H.at(i);
    cout << sum << endl;
  }
  return 0;
}

Measured memory_bytes: 1024