akhauriyash/Code-Regression huggingface dataset:
from sys import stdin
from itertools import accumulate, dropwhile, takewhile, groupby
import bisect
import copy
import math
import itertools
import math
from functools import reduce
n = int(stdin.readline().rstrip())
name = []
span = []
for el in range(n):
    inputter = stdin.readline().rstrip().split()
    name.append(inputter[0])
    span.append(int(inputter[1]))
target = stdin.readline().rstrip()
pos = name.index(target) + 1
res = 0
for el in range(pos, len(span)):
    res += span[el]
print(res)


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

long long A[200005];

int main() {

    ios::sync_with_stdio(0);
    cin.tie(NULL), cout.tie(NULL);
    
    long long N, K;
    cin >> N >> K;
    
    for(int i=1; i<=N; i++)
        A[i % K]++;
    
    long long ans = A[0] * A[0] * A[0];
    
    if(K % 2 == 0)
        ans += A[K/2] * A[K/2] * A[K/2];
    
    cout << ans << "\n";
    return 0;
}

Measured memory_bytes: 1024
#include <iostream>
#include <cstring>
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b) {
    if (!b) return a;
    return gcd(b, a % b);
}

int main(int argc, char const *argv[]) {
    
    int n, k;
    cin >> n >> k;
    int tmp = 0;
    int maxA = -1;
    for (int i = 0; i < n; i ++) {
        int x; scanf("%d", &x);
        tmp = gcd(tmp, x);
        maxA = max(maxA, x);
    }

    if (k <= maxA && k % tmp == 0)
        puts("POSSIBLE");
    else
        puts("IMPOSSIBLE");

    return 0;
}

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

int main() {
  int A=0,B=0,AB=0,O=0,to;
  string str,type;
  while(getline(cin ,str)) {
    to = str.find(",");
    type = str.substr(to+1);
    if(type == "A")
      A++;
    if(type == "B")
      B++;
    if(type == "AB")
      AB++;
    if(type == "O")
      O++;
  }
  cout << A << endl << B << endl << AB << endl << O << endl;
}

Measured memory_bytes: 0
#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define ll long long int
#define pii pair<int,int>
#define pll pair<long long int,long long int>
#define pci pair<char,int
#define mii map<int,int>
#define mll map<long long int,long long int>
#define mci map<char,int>
#define umii unordered_map<int,int>
#define umll unordered_map<long long int,long long int>
#define umci unordered_map<char,int>
#define F first
#define S second
#define pb push_back
#define endl '\n'
#define mod 1000000007
using namespace std;
#define maxval 10003000

int main(){
   IOS;
ll t;t=1;//cin>>t;
while(t--){
ll n;cin>>n;n=n%10;
  if(n==2||n==4||n==5||n==7||n==9) cout<<"hon";
  else if(n==3)cout<<"bon";
  else cout<<"pon";
     
} 
    
    

    
return 0;    
}

Measured memory_bytes: 3620
#include <iostream>
#include <iomanip>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <math.h>
#include <sstream>
#include <numeric>
#include <string>
#include <cassert>
#include <bitset>

using namespace std;
typedef long long ll;

int main() {
  int A, B, C;
  cin >> A >> B >> C;
  swap(A, B);
  swap(A, C);
  cout << A << " " << B << " " << C << endl;
  return 0;
}


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

using namespace std;
typedef long long ll;

#define rep(i, n) for (int i = 0; i < (n); i++)
#define rep2(i, a, b) for (int i = (a); i < (b); ++i)
#define all(a) (a).begin(), (a).end()
#define all2(a, b) (a).begin(), (a).begin() + (b)
#define debug(vari) cerr << #vari << " = " << (vari) << endl;

int main()
{
    int N, M;
    cin >> N >> M;
    vector<vector<int>> vec(M);
    rep(i, M)
    {
        int k;
        cin >> k;
        vec[i].resize(k);
        rep(j, k)
        {
            cin >> vec[i][j];
            vec[i][j]--;
        }
    }
    vector<int> p(M);
    rep(i, M) cin >> p[i];
    int ans = 0;

    for (int bit = 0; bit < (1 << N); bit++)
    {
        int cnt = 0;
        debug(bit);
        rep(i, M)
        {
            int on = 0;
            int n = vec[i].size();
            rep(j, n)
            {
                if (bit & (1 << vec[i][j]))
                {
                    on++;
                }
            }
            if (on % 2 == p[i])
            {
                cnt++;
            }
            debug(on);
            debug(cnt);
        }
        if (cnt == M)
            ans++;
    }

    cout << ans << endl;

    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
double e(int x){
    return (x+1)/2.0;
}
int main(){
    int n,k ;
    cin >> n >> k;
    vector<int> p(n);
    for(auto &x: p) cin >> x;
    double ans = 0, cur = 0;
    for(int i=0;i<k;i++){
        cur += e(p[i]);
    }
    ans = cur;
    for(int i=0;i + k< n; i ++){
        cur = cur - e(p[i]) + e(p[i+k]);
        ans = max(ans, cur);
    }
    cout << setprecision(12) << ans << endl;
}


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

int main(){
  int A, B, C, D, E, F;
  cin >> A >> B >> C >> D >> E>> F;
  vector<int> water;
  vector<int> sugar;
  for(int i=0; i<=F/(100*A); i++){
    for(int j=0; j<=F/(100*B); j++){
      int W = 100*A*i + 100*B*j;
      if(W<=F) water.push_back(W);
    }
  }
  sort(water.begin(), water.end());
  for(int i=0; i<=F/C; i++){
    for(int j=0; j<=F/D; j++){
      int S = C*i + D*j;
      if(S<=F) sugar.push_back(S);
    }
  }
  sort(sugar.begin(), sugar.end());
  int MAXW = 100*A;
  int MAXS = 0;
  double div = 0;
  for(int i=1; i<water.size(); i++){
    for(int j=0; j<sugar.size(); j++){
      if(water.at(i)+sugar.at(j)>F) continue;
      if(water.at(i)*E<sugar.at(j)*100) continue;
      if((double)100*sugar.at(j)/((double)water.at(i)+(double)sugar.at(j))>div){
        MAXW = water.at(i)+sugar.at(j);
        MAXS = sugar.at(j);
        div = (double)100*sugar.at(j)/((double)water.at(i)+(double)sugar.at(j));
      }
    }
  }
  cout << MAXW << ' ' << MAXS << endl;
}

Measured memory_bytes: 1400
#include<iostream>
#include<cmath>
#include<map>
#include<deque>
#include<string>
#include<algorithm>

#define all(x) (x).begin(),(x).end()
#define puts(x) cout<< x << endl;
#define rep(i,m,n) for(int i=m;i<n;i++)
#define fore(i,a) for(auto i:a)
#define ll long long
using namespace std;
string s;
int main(){
    cin>>s;
    int n=s.length();
    int checker=0;
    rep(i,0,n){
        if(s[i]!=s[n-i-1])checker=1;
    }
    rep(i,0,(n-1)/2){
        if(s[i]!=s[(n-1)/2-i-1])checker=1;
        if(s[n-1-i]!=s[n-1-((n-1)/2-i-1)])checker=1;
    }
    if(checker==0){
        puts("Yes");
    }else{
        puts("No");
    }
}

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

typedef long long LL;

#define REP(i, n) for(int i = 0; i < (int)(n); i++)
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ALL(x) (x).begin(),(x).end()
const int IINF = 1e9;
const LL LINF = 1e18;
const LL MOD = 1e9+7;

int main() {
    int N;
    cin >> N;
    vector<pair<LL, LL>> p(N);
    REP(i, N) {
        LL x, y;
        cin >> x >> y;
        p[i] = make_pair(x + y, x - y);
    }

    LL max_x = -LINF, max_y = -LINF, min_x = LINF, min_y = LINF;
    REP(i, N) {
        LL x, y;
        tie(x, y) = p[i];
        max_x = max(max_x, x);
        max_y = max(max_y, y);
        min_x = min(min_x, x);
        min_y = min(min_y, y);
    }

    LL r = max(max_x - min_x, max_y - min_y);
    cout << r << endl;

    return 0;
}


Measured memory_bytes: 6416
import java.io.*;
 
class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder output = new StringBuilder();
        while(true) {
            String str = br.readLine();
            if(str.equals("0 0")) break;
            int x = Integer.parseInt(str.substring(0, str.indexOf(' ')));
            int y = Integer.parseInt(str.substring(str.indexOf(' ')+1));
            if(x<=y) output.append(x+" "+y+"\n");
            else output.append(y+" "+x+"\n");
        }
        System.out.print(output);
    }
 
}

Measured memory_bytes: 22380
#include<iostream>
#include<algorithm>

using namespace std;
int main(){
int N;
cin >> N;
int H[N];
for(int i=0;i<N;i++)cin >> H[i];
int Sea=1,see=0;
for(int l=1;l<N;l++){
see=1;
for(int i=0;i<l;i++){
if(H[i]>H[l]){
see=0;
break;
}
}
Sea+=see;
}
cout << Sea << endl;

 return 0;
}


Measured memory_bytes: 256
function main(){
	var n = scan();
	var x = 100000;
	rep(n, function(){
		x += x / 20;
		if(x % 1000 > 0){
			x = (Math.floor(x / 1000) + 1) * 1000;
		}
	});
	print(x);
}
 
function rep(a, b, c){
	if(c == null){
		c = b;
		b = a;
		a = 0;
	}
	for(var i = a; i < b; ++i){
		c(i);
	}
}
 
process.stdin.resume();
process.stdin.setEncoding('utf8');
 
var input = '';
var input_index = 0;
 
function scan(type){
	if(type === 'string'){
		return input[input_index++];
	}
	else{
		return +input[input_index++];
	}
}
 
function print(val){
	console.log(val);
}
 
process.stdin.on('data', function(chunk){
	input += chunk;
});
process.stdin.on('end', function(){
	input = input.split(/\s+/);
	main();
});

Measured memory_bytes: 15496
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		string[] str = Console.ReadLine().Split();
		long N = long.Parse(str[0]);
		long K = long.Parse(str[1]);
		long mod = 1000000007;
		long[]A = new long[2010];
		long[]NA = new long[2010];
		A[0] = 1;
		NA[0] = 1;
		A[1] = 1;
		NA[1] = 1;
		for(var i=1;i<2008;i++){
			A[i+1] = A[i] * (i+1) % mod;
			NA[i+1] = NA[i] * Mpow(i+1,mod-2,mod) % mod;
		}
		for(var i=1;i<=K;i++){
          	long a = 0;
          	if(N-K+1-i >= 0){
				a = A[N-K+1]%mod*NA[N-K+1-i]%mod*NA[i]%mod;
            }
			long b = A[K-1]%mod*NA[K-i]%mod*NA[i-1]%mod;
        	Console.WriteLine(a*b%mod);
		}
	}
	
	public static long Mpow(long x,long n,long m)
	{
		long ans = 1;
		while(n > 0){
			if(n % 2 == 1){
				ans = ans * x % m;
				n -= 1;
			}
			x = x * x % m;
			n /= 2;
		}
		return ans;
	}
	public static long Ncr(long n,long r,long m)
	{
		long ans = 1;
		for(var i=n-r+1;i<=n;i++){
			ans = ans * i % m;
		}
		for(var i=2;i<=r;i++){
			ans = ans * Mpow(i,m-2,m) % m;
		}
		return ans;
	}
}

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

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int N;
const ll mo=998244353;
int ret=0;
int p2[10101010];

ll comb(ll N_, ll C_) {
	const int NUM_=11400001;
	static ll fact[NUM_+1],factr[NUM_+1],inv[NUM_+1];
	if (fact[0]==0) {
		inv[1]=fact[0]=factr[0]=1;
		for (int i=2;i<=NUM_;++i) inv[i] = inv[mo % i] * (mo - mo / i) % mo;
		for (int i=1;i<=NUM_;++i) fact[i]=fact[i-1]*i%mo, factr[i]=factr[i-1]*inv[i]%mo;
	}
	if(C_<0 || C_>N_) return 0;
	return factr[C_]*fact[N_]%mo*factr[N_-C_]%mo;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	
	ll ret=1;
	p2[0]=1;
	FOR(i,N) {
		ret=ret*3%mo;
		p2[i+1]=p2[i]*2%mo;
	}
	FOR(i,N+1) if(i*2>N) {
		ll pat=comb(N,i)*p2[N-i]%mo;
		ret-=pat*2;
	}
	
	cout<<(ret%mo+mo)%mo<<endl;
	
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n'; FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	cout.tie(0); solve(); return 0;
}


Measured memory_bytes: 306944
#include <queue>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
struct edge {
	int to, cost;
	edge(int to_, int cost_) : to(to_), cost(cost_) {};
};
bool operator<(const edge& e1, const edge& e2) {
	return e1.cost < e2.cost;
}
using namespace std;
template<class Type>
std::vector<Type> shortest_path_dijkstra(std::vector<std::vector<edge> > &G, int s) {
	std::priority_queue<edge> que; que.push(edge(s, 0));
	std::vector<Type> ret(G.size(), std::numeric_limits<Type>::max()); ret[s] = 0;
	while (!que.empty()) {
		edge u = que.top(); que.pop();
		for (edge e : G[u.to]) {
			if (ret[e.to] > ret[u.to] + e.cost) {
				ret[e.to] = ret[u.to] + e.cost;
				que.push(edge(e.to, -ret[e.to]));
			}
		}
	}
	return ret;
}
int n, a, b, w;
int main() {
	cin >> n;
	vector<vector<edge> > G(n);
	for (int i = 1; i < n; i++) {
		scanf("%d%d%d", &a, &b, &w);
		G[a].push_back(edge(b, w));
		G[b].push_back(edge(a, w));
	}
	vector<int> v1 = shortest_path_dijkstra<int>(G, 0);
	int pos1 = max_element(v1.begin(), v1.end()) - v1.begin();
	vector<int> v2 = shortest_path_dijkstra<int>(G, pos1);
	int pos2 = max_element(v2.begin(), v2.end()) - v2.begin();
	vector<int> v3 = shortest_path_dijkstra<int>(G, pos2);
	for (int i = 0; i < n; i++) printf("%d\n", max(v2[i], v3[i]));
	return 0;
}

Measured memory_bytes: 3880
import sys
input = sys.stdin.readline

def main():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    ans = 0
    for i in range(N):
        if h[i] >= K:
            ans += 1
    print(ans)

if __name__ == "__main__":
    main()

Measured memory_bytes: 11904
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

void ABC165D()
{
	ll A, B, N;
	cin >> A >> B >> N;
	N = min(B - 1, N);
	ll r = 0, q = 0;
	while (N > 0)
	{
		ll qq = A / B;
		ll rr = A % B;
		ll x = 1;
		while (x * 2 < N)
		{
			qq *= 2;
			rr *= 2;
			if (rr > B)
			{
				rr -= B;
				++qq;
			}
			x *= 2;
		}
		q += qq;
		r += rr;
		if (r > B)
		{
			q += r / B;
			r = r % B;
		}
		N -= x;
	}

	cout << q << endl;
}

int main()
{
	ABC165D();
	return 0;
}


Measured memory_bytes: 3624
#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <stack>
#include <queue>
#include <vector>
typedef long long int ll;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000001
using namespace std;

int main(){

	int N,num,tmp,ans,count;
	bool check[50][50];
	vector<int> V[31];

	while(true){
		scanf("%d",&N);
		if(N == 0)break;

		for(int i = 1; i <= 30; i++){
			V[i].clear();
		}

		for(int i = 0; i < N; i++){
			for(int k = 0; k < N; k++){
				if(i == k)check[i][k] = true;
				else{
					check[i][k] = false;
				}
			}
		}

		ans = -1;

		for(int i = 0; i < N; i++){
			scanf("%d",&num);

			for(int k = 0; k < num; k++){
				scanf("%d",&tmp);
				V[tmp].push_back(i);
			}
		}

		if(N == 1){
			printf("1\n");
			continue;
		}

		for(int day = 1; day <= 30; day++){
			for(int i = 0; i < V[day].size();i++){
				for(int k = i+1; k < V[day].size();k++){
					count = 0;
					for(int a = 0; a < N; a++){
						if(check[V[day][i]][a] == true || check[V[day][k]][a] == true){
							check[V[day][i]][a] = true;
							check[V[day][k]][a] = true;
							count++;
						}
					}
					if(count == N){
						ans = day;
						break;
					}
				}
				if(ans != -1)break;
			}
			if(ans != -1)break;
		}

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

	return 0;
}

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

const int N = 100000;

int n, p;
int pre[N+1];

int find(int x)
{
    while (x != pre[x])
        x = pre[x];
    return x;
}

int main(void)
{
    while (scanf("%d%d", &n, &p) != EOF) {
        if (!n && !p) break;
        pre[1] = 1;
        for (int i = 2; i <= n; i ++)
            scanf("%d", &pre[i]);
        long long sum = 0;
        for (int i = 1; i <= p; i ++) {
            char s[2];
            int x;
            scanf("%s%d", s, &x);
            if (s[0] == 'M')
                pre[x] = x;
            else
                sum += find(x);
        }
        printf("%lld\n", sum);
    }

    return 0;
}

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

const int INF = 1 << 28;
const int N = 1 << 17;

int seg[1 << 18], a[1 << 17];
int n, r, l;
int d[1000002], t[1000002], x[1000002];
int sum[1 << 17];

void init()
{
	for (int i = 0; i < N; i++) seg[i + N - 1] = i;
	for (int i = N - 2; i >= 0; i--){
		seg[i] = seg[i * 2 + 1];
	}
}

void add(int i, int x)
{
	int k = i + N - 1;
	a[i] += x;
	while (k){
		k = (k - 1) / 2;
		if (a[seg[k * 2 + 1]] >= a[seg[k * 2 + 2]]){
			seg[k] = seg[k * 2 + 1];
		}
		else if (a[seg[k * 2 + 1]] < a[seg[k * 2 + 2]]){
			seg[k] = seg[k * 2 + 2];
		}
	}
}

int get()
{
	return seg[0];
}

int main()
{
	scanf("%d %d %d", &n, &r, &l);
	for (int i = 1; i <= r; i++){
		scanf("%d %d %d", d + i, t + i, x + i);
	}
	t[r + 1] = l;
	
	init();
	for (int i = 1; i <= r + 1; i++){
		sum[get()] += t[i] - t[i - 1];
		add(d[i] - 1, x[i]);
	}
	
	int maxi = 0;
	for (int i = 0; i < n; i++){
		if (sum[maxi] < sum[i]) maxi = i;
	}
	printf("%d\n", maxi + 1);
	
	return 0;
}

Measured memory_bytes: 14452
n,*v = map(int,open(0).read().split())
v0,v1 = {},{}
flg = True
for i in v:
    if flg:
        v0[i]= v0[i]+1 if i in v0 else 1
    else:    
        v1[i]= v1[i]+1 if i in v1 else 1
    flg = not flg
len0,len1 = len(v0),len(v1)
if len0==1 and len1==1:
    if v0.keys() != v1.keys():
        print(0)
    else:
        sv = sorted(v1.values())[0]
        print(sv)
elif len0 == 1:
    sort_v1 = sorted(v1.items(),key=lambda x:x[1])
    sum1 = sum(v1.values())
    print(sum1 - max(v1.values()))
elif len1 == 1:
    sort_v0 = sorted(v0.items(),key=lambda x:x[1])
    sum0 = sum(v0.values())
    print(sum0 - max(v0.values()))
else:
    sort_v1 = sorted(v1.items(),key=lambda x:x[1])
    sort_v0 = sorted(v0.items(),key=lambda x:x[1])
    #print(sort_v0,sort_v1)
    if sort_v0[-1][0] != sort_v1[-1][0]:
        sum0 = sum(v0.values()) - sort_v0[-1][1]
        sum1 = sum(v1.values()) - sort_v1[-1][1]
        print(sum0 + sum1)
    else:
        sum0 = sum(v0.values())
        sum1 = sum(v1.values())
        sum0_1 = sum0 - sort_v0[-1][1]
        sum0_2 = sum0 - sort_v0[-2][1]
        sum1_1 = sum1 - sort_v1[-1][1]
        sum1_2 = sum1 - sort_v1[-2][1]
        print(min(sum0_1 + sum1_2 , sum0_2 + sum1_1))



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

# define REP(i,n) for (int i=0;i<(n);++i)
# define rep(i,a,b) for(int i=a;i<(b);++i)
# define p(s) std::cout << s ;
# define pl(s)  std::cout << s << endl;
# define printIf(j,s1,s2) cout << (j ? s1 : s2) << endl;
# define YES(j) cout << (j ? "YES" : "NO") << endl;
# define Yes(j) std::cout << (j ? "Yes" : "No") << endl;
# define yes(j) std::cout << (j ? "yes" : "no") << endl;
# define all(v) v.begin(),v.end()
# define showVector(v) REP(i,v.size()){p(v[i]);p(" ")} pl("")
template<class T> inline bool chmin(T &a, T b){ if(a > b) { a = b; return true;} return false;}
template<class T> inline bool chmax(T &a, T b){ if(a < b) { a = b; return true;} return false;}
typedef long long int ll;
typedef pair<ll,ll> P_ii;
typedef pair<double,double> P_dd;

template<class T>
vector<T> make_vec(size_t a){
    return vector<T>(a);
}

template<class T, class... Ts>
auto make_vec(size_t a, Ts... ts){
  return vector<decltype(make_vec<T>(ts...))>(a, make_vec<T>(ts...));
}

template<typename T,typename V>
typename enable_if<is_class<T>::value==0>::type
fill_v(T &t,const V &v){t=v;}

template<typename T,typename V>
typename enable_if<is_class<T>::value!=0>::type
fill_v(T &t,const V &v){
  for(auto &e:t) fill_v(e,v);
}


const int MOD = 1000000007;
const int inf=1e9+7;
const ll longinf=1LL<<60 ;

typedef pair<ll,ll> P_ll;
struct edge {int to , cost;};
typedef vector<vector<edge>> wgraph; // cost, to

vector<P_ll> dijkstra(wgraph G,int s){
    priority_queue<P_ll, vector<P_ll>, greater<P_ll>> que;
    vector<ll> dist(G.size(), longinf);
    vector<P_ll> prev(G.size(), {-1, -1});

    dist[s]=0;
    que.push({0LL, s});

    while(!que.empty()){
        P_ll p = que.top();que.pop();

        ll v = p.second,d = p.first;
        if(dist[v] < d) continue;
        for(auto e:G[v]){
            if(dist[e.to] > dist[v] + e.cost){
                dist[e.to] = dist[v] + e.cost;
                prev[e.to] = {v, e.cost};
                que.push({dist[e.to], e.to});
            }
        }
    }
    return prev;
}

int main(void) {
  int N, M;
  cin >> N >> M;

  ll L;
  cin >> L;

  auto g = make_vec<ll>(N, N);
  auto ans = make_vec<ll>(N, N);
  fill_v(g, longinf);
  fill_v(ans, longinf);

  REP(i, M){
    int a, b, c;
    cin >> a >> b >> c;
    a--, b--;

    g[a][b] = c;
    g[b][a] = c;
  }

  REP(i, N) REP(j, N) if(i == j) g[i][j] = 0;
  REP(k, N) REP(i, N) REP(j, N) chmin(g[i][j], g[i][k] + g[k][j]);
  REP(i, N) REP(j, N) if(g[i][j] <= L) ans[i][j] = 1;
  REP(k, N) REP(i, N) REP(j, N) chmin(ans[i][j], ans[i][k] + ans[k][j]);
  
  int Q;
  cin >> Q;

  REP(i, Q){
    int s, t;
    scanf("%d %d", &s, &t);
    s--;t--;

    cout << (ans[s][t] == longinf ? -1 : ans[s][t] - 1) << endl;
  }

  return 0;
}

Measured memory_bytes: 1920
MOD = 10**9+7
N,K = map(int,input().split())
A = list(map(int,input().split()))
sign = dict({-1:0,0:0,1:0})
for a in A:
    if a<0:
        sign[-1]+=1
    elif a>0:
        sign[1]+=1
    else:
        sign[0]+=1
if sign[1]==0 and K%2!=0:
    A.sort(reverse=True)
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
elif sign[1]==0 and K%2==0:
    A.sort()
    ans = 1
    for i in range(K):
        ans *= A[i]
        ans %= MOD
else:
    A.sort()
    ans = 1
    i,j = 0,N-1
    while K>0:
        if K>1 and A[i]*A[i+1]>=A[j]*A[j-1]:
            ans *= A[i]*A[i+1]
            ans %= MOD
            i += 2
            K -= 2
        else:
            ans *= A[j]
            ans %= MOD
            j -= 1
            K -= 1
print(ans)

Measured memory_bytes: 31692
#include<bits/stdc++.h>
using namespace std;
 
int main(){
  int n;
  cin >> n;
  int count = 0;
  
  vector<int> l(n);
  for(int i = 0; i < n; i++){
    cin >> l.at(i);
  }
  sort(l.begin(), l.end());
  
  
  for(int i = 0; i < n; i++){
    for(int j = i + 1; j < n; j++){
      for(int k = j + 1; k < n; k++){
        if(l.at(i) + l.at(j) > l.at(k) && l.at(i) < l.at(j) && l.at(j) < l.at(k)){
          count++;
        }
      }
    }
  }
  cout << count << endl;
}

Measured memory_bytes: 3628
/**
 * code generated by JHelper
 * More info: https://github.com/AlexeyDmitriev/JHelper
 * @author
 */

#include <iostream>
#include <fstream>

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define PI 3.141592653589793
#define rep(i, n) for (int i = 0; i < (n); i++)
#define all(x) (x).begin(), (x).end()
template<class T> istream &operator>>(istream&is,vector<T>&v){for(auto &elemnt:v)is>>elemnt;return is;}
template<class T,class U> istream &operator>>(istream&is,pair<T,U>&p){is>>p.first>>p.second;return is;}
template<class T>vector<T> make_vector(size_t a){return vector<T>(a);}

class ATOrT {
public:
	void solve(std::istream& in, std::ostream& out) {
	    ll N, A, B;
	    in >> N >> A >> B;
	    out << min(N * A, B) << endl;
	}
};


int main() {
	ATOrT solver;
	std::istream& in(std::cin);
	std::ostream& out(std::cout);
	solver.solve(in, out);
	return 0;
}


Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
#define LEN 100005
struct P{
    char name[100];
    int t;
};

P Q[LEN];
int head,tail,n;

void enqueue(P x){
    Q[tail]=x;
    tail=(tail+1)%LEN;
}

P dequeue(){
    P x=Q[head];
    head=(head+1)%LEN;
    return x;
}

int min(int a,int b){return a<b?a:b;}
int main(){
    int elaps=0,c;
    int i,q;
    P u;
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>Q[i].name>>Q[i].t;
    }
    head=1;tail=n+1;
    while(head!=tail){
        u=dequeue();
        c=min(q,u.t);
        u.t-=c;
        elaps+=c;
        if(u.t>0)enqueue(u);
        else{
            cout<<u.name<<" "<<elaps<<endl;
        }
    }
    return 0;
}


Measured memory_bytes: 13248
#include<stdio.h>
void showData(int*,int);

int main()
{
	int a[100],i,j,tmp,count=0;
	int length,min_index=0;
	scanf("%d",&length);
	
	for(i=0; i<length; i++){
		scanf("%d",&a[i]);
	}
	
	for(i=0; i<length-1; i++){
		min_index=i;
		for(j=i+1; j<length; j++){
			if(a[min_index] > a[j]){
				min_index=j;
			}
		}
		
		if(min_index!=i){
			tmp=a[i];
			a[i]=a[min_index];
			a[min_index]=tmp;
			
			count++;
		}
	}
	showData(a,length);
	printf("%d\n",count);
        return 0;
}
void showData(int*array,int length){
	int i;
	for(i=0; i<length; i++){
		if(i<length-1) printf("%d ",array[i]);
		else printf("%d\n",array[i]);
	}
}
		

Measured memory_bytes: 600
n,m = map(int,input().split())
li = list(map(int,input().split()))
lia = []
li.sort()
for i in range(m-1):
    lia.append(abs(li[i]-li[i+1]))
lia.sort(reverse=True)
del lia[:n-1]
print(sum(lia))

Measured memory_bytes: 13968
#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <tuple>
#include <bitset>
#include <memory>
#include <cmath>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <numeric>
#include <climits>
#include <cfloat>
int main(){
	int n; std::cin >> n;
	std::vector<long long int> numbers(1 << n); for (auto& a : numbers) std::cin >> a;
	std::vector<std::vector<int>> result(1 << n);
	for (auto k = 0; k < (1 << n); ++k) {
		std::vector<int> indices{k};
		for (auto d = 0; d < n; ++d) if ((k & (1 << d)) != 0) {
			for (const auto i : result[(k - (1 << d))]) indices.push_back(i);
		}
		std::sort(indices.begin(), indices.end(), [&numbers](const int a, const int b) {return numbers[a] > numbers[b]; });
		indices.erase(std::unique(indices.begin(), indices.end()), indices.end());
		if (indices.size() > 2) indices.erase(indices.begin() + 2, indices.end());
		result[k] = std::move(indices);
	}
	long long int max = 0;
	for (auto k = 1; k < result.size(); ++k) {
		max = std::max(max, numbers[result[k][0]] + numbers[result[k][1]]);
		//std::cout << "k :" << std::setbase(2) << k << " - ";
		std::cout << max << "\n";
	}
}

Measured memory_bytes: 44160
s = list(input())
t = list(input())
min_cnt = 1000
x = len(s)
y = len(t)
for i in range(x - y + 1):
    cnt = 0
    for j in range(y):
        if s[i + j] != t[j]:
            cnt += 1
    min_cnt = min(min_cnt, cnt)
print(min_cnt)


Measured memory_bytes: 9048
from sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    s = 'ABC' if S=='ARC' else 'ARC'
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(s)


Measured memory_bytes: 61596
#include <stdio.h>
 
int main(){
  char S[25];
  scanf("%s",S);

  for(int i=0;i<19;i++){
    if(S[i]==','){
         printf(" ");
    }
    else{
         printf("%c",S[i]);
       }
    }
  printf("\n");
  return 0;
}

Measured memory_bytes: 3160
#include <stdio.h>

const double PERCENT = 1.01;

int main(int argc, const char **argv)
{
    long long start = 100LL, goal = 0LL, year = 0LL;

    fscanf(stdin, "%lld", &goal);

   for ( year = 1LL;  ; year++ )
   {
       start *= PERCENT;
       if ( start >= goal ) break;
   }

    fprintf(stdout, "%lld\n", year);
    return 0;
}

Measured memory_bytes: 2128
#include <iostream>
#include <stdio.h>
using namespace std;

int main() {
  char n1, n2, comma;
  int cup[3];
  cup[0] = 1;
  cup[1] = 0;
  cup[2] = 0;
  int temp;

  while(cin >> n1 >> comma >> n2){
    temp = cup[n1-'A'];
    cup[n1-'A'] = cup[n2-'A'];
    cup[n2-'A'] = temp;
  }

  for(int i = 0; i < 3; i++) {
    if(cup[i] == 1) {
       putchar(i+65);
       putchar('\n');
    }
  }

  return 0;
}



Measured memory_bytes: 3068
using System;
using System.Collections.Generic;
class Program
{
	static void Main(string[] args)
	{
		// 文字列の入力
		string S = Console.ReadLine();
        string T = Console.ReadLine();
        int L = S.Length;
        int[] S_arr = new int[L];
        int[] T_arr = new int[L];
        string res = "Yes";
        int k = 0;
        Dictionary<char, int> S_dict = new Dictionary<char, int>();
        for (int i = 0; i < L; i++){
            char s = S[i];
            if (S_dict.ContainsKey(s)){
                S_arr[i] = S_dict[s];
            } else {
                S_arr[i] = k;
                S_dict.Add(s, k);
                k++;
            }
        }
        int l = 0;
        Dictionary<char, int> T_dict = new Dictionary<char, int>();
		for (int j = 0; j < L; j++){
            char t = T[j];
            if (T_dict.ContainsKey(t)){
                T_arr[j] = T_dict[t];
            } else {
                T_arr[j] = l;
                T_dict.Add(t, l);
                l++;
            }
            if (S_arr[j] != T_arr[j]){
                res = "No";
            }

        }

        
        //出力
		Console.WriteLine(res);
	}
}

Measured memory_bytes: 16352
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO 自動生成されたメソッド・スタブ
		Scanner sc=new Scanner(System.in);
		int a=sc.nextInt();
		if(a==1)a=14;
		int b=sc.nextInt();
		if(b==1)b=14;
		if(a>b)System.out.println("Alice");
		else if(a<b)System.out.println("Bob");
		else System.out.println("Draw");
		
		}
		
	}


Measured memory_bytes: 21844
using System;
using System.Collections.Generic;
using System.Linq;
using static Constans;

public static class Constans
{
    public const long Mod = (long)1e9 + 7;
}

public struct ModInt
{
    public long Num;

    public ModInt(long num)
    {
        Num = num;
    }

    // x^n
    public static long Power(long x, long n)
    {
        long pow = 1;
        while (n > 0)
        {
            if (n % 2 == 0)
            {
                x *= x;
                x %= Mod;
                n /= 2;
            }
            else
            {
                pow *= x;
                pow %= Mod;
                n--;
            }
        }

        return pow;
    }

    public static ModInt GetInv(long f)
    {
        // フェルマーの小定理 a^(-1) = a^(mod-2)
        return new ModInt(Power(f, Mod - 2));
    }

    public ModInt GetInv()
    {
        return GetInv(Num);
    }

    public override string ToString()
    {
        return Num.ToString();
    }

    public static ModInt operator +(ModInt l, ModInt r)
    {
        l.Num += r.Num;
        if (l.Num >= Mod)
        {
            l.Num -= Mod;
        }
        return l;
    }

    public static ModInt operator -(ModInt l, ModInt r)
    {
        l.Num -= r.Num;
        if (l.Num < 0)
        {
            l.Num += Mod;
        }
        return l;
    }

    public static ModInt operator *(ModInt l, ModInt r)
    {
        return new ModInt(l.Num * r.Num % Mod);
    }

    public static implicit operator ModInt(long n)
    {
        n %= Mod;
        if (n < 0)
        {
            n += Mod;
        }
        return new ModInt(n);
    }
}

public class Solution
{
    public static void Main()
    {
        var vals = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
        var N = vals[0];
        var M = vals[1];
        var ng = new bool[N];
        for (int i = 0; i < M; i++)
        {
            var v = int.Parse(Console.ReadLine());
            ng[v] = true;
        }

        var pattern = new ModInt[N + 1];
        pattern[0] = 1;
        for (int i = 0; i < N; i++)
        {
            if (ng[i])
            {
                continue;
            }

            for (var j = 1; j <= 2; j++)
            {
                var next = i + j;
                if (next <= N)
                {
                    pattern[next] += pattern[i];
                }
            }
        }

        Console.WriteLine(pattern[N]);
    }
}

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

using namespace std;

int popcount(int x) {
  int ret{};
  while (x) {
    if (x & 1) ++ret;
    x >>= 1;
  }
  return ret;
}

int main() {
  int N, A, x, y;
  cin >> N;
  vector<vector<pair<int, bool>>> m(N);
  for (int i = 0; i != N; ++i) {
    cin >> A;
    m[i].resize(A);
    for (int j = 0; j != A; ++j) {
      cin >> x >> y;
      m[i][j] = {x-1, y};
    }
  }

  bool flag;
  int ans{};
  for (int i = (1 << N) - 1; i; --i) {
    if (popcount(i) < ans) continue;
    flag = true;
    for (int j = 0; j != N; ++j) {
      if (!(i & (1 << j))) continue;
      for (auto &p: m[j]) {
        if (p.second != (1 & (i >> p.first))) {
          flag = false;
          break;
        }
      }
      if (!flag) break;
    }
    if (flag) ans = popcount(i);
  }

  cout << ans << endl;
}


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

#define ll long long
#define pb push_back
#define pr pair<ll, ll>
#define vct vector<ll>
#define vpt vector<pr>
#define st set<ll>
#define pq priority_queue<ll>
#define mat vector<vector<ll> >
#define F(i, n) for (i = 0; i < (1LL*n); i++)
#define Fr(i, n) for (i = n - 1; i >= 0; i--)

struct custom_hash
{
    static uint64_t splitmix64(uint64_t x)
    {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const
    {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
#define umap unordered_map<long long, int, custom_hash>
void prv(vct v)
{
    for (ll i = 0; i < v.size(); i++)
        cout << v[i] << " ";
    cout << "\n";
}
ll poww(ll x, ll y, ll m)
{
    ll res = 1;
    while (y)
    {
        if (y % 2 == 0)
        {
            x = (x * x) % m;
            y = y / 2;
        }
        else
        {
            res = (res * x) % m;
            y--;
        }
    }
    return res;
}
void deb(string s, ll n)
{
    cout << s << " : " << n << "\n";
}
void prn(ll n) { cout << n << "\n"; }
void prs(string n) { cout << n << "\n"; }

mat mt;
void setmtsize(ll m,ll n, ll ini=0){
    mt.resize(m,vector<ll>(n,ini));
}
void prmt(mat m){
    for(ll i=0;i<(1LL*m.size());i++)prv(m[i]);
}
vct divsors(ll n)
{
    vct ans;//ans.push_back(1);
    for(ll i=1;i<=sqrt(n);i++)
    {if(n%i==0){ans.push_back(i);if(i!=(n/i))ans.push_back(n/i);}}
    sort(ans.begin(),ans.end());
    return ans;
}
vct sieve(ll n){
    vct ans(n+1,-1);
    for(ll i=2;i<=n;i++){
        if(ans[i]==-1){
            for(ll j=i;j<=n;j+=i)if(ans[j]==-1)ans[j]=i;
        }
    }
    return ans;
}
ll n, k, m, l, r, x, y, z, ans=0;
ll t, t1, t2;
ll q;
ll i, j;
ll a, b, c;
ll mod = 1000000007;



void solve()
{
    string s1,s2;
    cin>>s1>>s2;
    n=s1.size();m=s2.size();
    ll dp[n+1][m+1];
    memset(dp,0,sizeof(dp));

    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            if(s1[i-1]==s2[j-1])dp[i][j]=1+dp[i-1][j-1];
            else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
        }
    }
    
    string s="";
    i=n,j=m;
    while(i>0 && j>0){
        if(s1[i-1]==s2[j-1]){
            s+=s1[i-1];
            i--;j--;
            continue;
        }
        ll tk1=dp[i-1][j];
        ll tk2=dp[i][j-1];
        if(tk1>tk2)i--;
        else j--;
    }
    reverse(s.begin(),s.end());
    prs(s);
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll t = 1;
    // cin >> t;
    // stress();
    while (t--)
        solve();
    return 0;
}

Measured memory_bytes: 73956
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
int main()
{
	int N; cin>>N;
	int arr[N],arr1[N];
	for(int i=0;i<N;i++)
	{
		cin>>arr[i];
		arr1[i] = arr[i];
	}
	sort(arr1,arr1+N);
	int cnt = 0;
	for(int i=0;i<N;i++)
	{
		if(arr[i]!=arr1[i])
			cnt++;
	}
	if(cnt==0||cnt==2)
		cout<<"YES"<<endl;
	else
		cout<<"NO"<<endl;
	return 0;
}

Measured memory_bytes: 384
#!/usr/bin/env python3
import sys
import bisect

MOD = 1000000007  # type: int

def is_ok(i,a):
    ii = bisect.bisect_left(a,i)
    if ii >= len(a):
        return True
    return i != a[ii]


def solve(N: int, M: int, a: "List[int]"):
    dp = [0]*N
    dp[0] = 1 if is_ok(1,a) else 0

    if N > 1:
        if is_ok(2,a):
            if is_ok(1,a):
                dp[1] = 2
            else:
                dp[1] = 1

    if N > 2:
        for i in range(2,N):
            if is_ok(i+1,a):
                dp[i] = dp[i-1] + dp[i-2]
                dp[i] %= MOD

    print(dp[N-1] % MOD)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    a = [ int(next(tokens)) for _ in range(M) ]  # type: "List[int]"
    solve(N, M, a)

if __name__ == '__main__':
    main()



Measured memory_bytes: 7840
Program Batcoder2;
//uses crt;
var A:array[1..200] of longint;
    i,n,l,sum,res,min :longint;
    f:text;
//--------------------------------
begin
//clrscr;
//assign(f,'Batcoder2.inp');
//reset(f);
readln(n,l);
min:=1000;
for i:=1 to n do begin
                 A[i]:=l+i-1;
                 sum:=sum+A[i];
                 end;
for i:=1 to n do begin
                 if abs(A[i]) < min then begin
                                             min:=abs(A[i]);
                                             res:=A[i];
                                             end;
                 end;
Writeln(sum-res);
//readln;
end.



Measured memory_bytes: 128
/* The journey is what brings us pleasure, not the destination <3 */

#include<bits/stdc++.h>

#define PI acos(-1)
#define _fastIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define MOD 1000000007
#define MAX 1000000
#define all(v) v.begin(),v.end()

using namespace std;
typedef long long ll;

int tc;

void solve(){

    int x;
    cin>>x;
    cout<<!x<<endl;
    
}

int main(){

    _fastIO;

    //cin>>tc; while(tc--)
    solve();

    return 0;
}


Measured memory_bytes: 3644
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <complex>
#include <stack>
#include <queue>
#include <unordered_map>
#include <map>
#define rep(i, a) for (int i = 0; i < (a); i++)
using namespace std;

int main(){
    int n, k;
    string s;
    string ans = "";
    
    cin >> n >> s >> k;
    
    for(int i = 0; i < n; i++){
        if(s[i] != s[k-1]){
            ans += "*";
        }else{
            ans += s[i];
        }
    }
    
    cout << ans << endl;
}


Measured memory_bytes: 256
#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#define int long long
using namespace std;

int n;
int l, r;

signed main() {
	int ans = 0;
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> l >> r;
		ans += r - l + 1;
	}
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 888
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(),(x).end()
#define dlog(x) cerr<<#x<<'='<<x<<endl
#define f first
#define s second
#define endl '\n'
#define sq(x) (x)*(x)*1ll
typedef long long ll;
typedef pair<int,int> pii;

/* stuff you should look for
	* int overflow, array bounds
	* special cases (n=1?)
	* do something instead of nothing and stay organized
*/


int main () {
      int n;
      cin >> n;
      cout << (n + 1) / 2 << endl;
      return 0;
}

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

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

typedef long long ll;
const ll MOD = 1e9 + 7;

int main() {
  int N;
  std::string S;
  std::cin >> N >> S;

  if(N % 2 != 0) {
    std::cout << "No" << '\n';
    return 0;
  }
  for(int i = 0; i < N / 2; ++i) {
    if(S[i] != S[N / 2 + i]) {
      std::cout << "No" << '\n';
      return 0;
    }
  }

  std::cout << "Yes" << '\n';
}


Measured memory_bytes: 256
// ProblemURL : https://atcoder.jp/contests/agc039/tasks/agc039_a
// ---------------------------------------------
package main

import (
	"fmt"
	"strings"
)

func countAlphabet(s string) int {
	m := make(map[rune]int, 26)
	for _, ss := range s {
		m[ss]++
	}
	return len(m)
}

func calcCostNaive(s string) int {
	t := []byte(s)
	cost := 0
	for i := 1; i < len(t); i++ {
		if t[i-1] == t[i] {
			t[i] = '#'
			cost++
		}
	}
	return cost
}

func main() {
	var s string
	var k int
	fmt.Scan(&s, &k)

	if countAlphabet(s) == 1 {
		length := len(s) * k
		cost := length / 2
		fmt.Println(cost)
		return
	}

	if s[0] == s[len(s)-1] {
		t := string(s[0])
		ctHead := len(s) - len(strings.TrimLeft(s, t))
		ctTail := len(s) - len(strings.TrimRight(s, t))
		u := strings.Trim(s, t)
		cost := ctHead/2 + ctTail/2 + calcCostNaive(u)*k + (ctHead+ctTail)/2*(k-1)
		fmt.Println(cost)
	} else {
		cost := calcCostNaive(s)
		cost *= k
		fmt.Println(cost)
	}
}


Measured memory_bytes: 640
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
string s;
int main() {
	cin>>s;
	int len=s.length();
	char base='a';
	for(int i=0;i<=len-1;i++) {
		if(s[i]==base) {
			base=base+1;
			i=0;
		}
	}
	if(base=='{') {
		cout<<"None"<<endl;
	} else {
		cout<<base<<endl;
	}
	return 0;
}

Measured memory_bytes: 512
#include <cmath>
#include <iostream>
#include <string>
#include <vector> 
#include <algorithm>
#include <numeric>
#include <map>   
#include <stdio.h>

#define FOR(i,a,b) for(i=(a);i<(b);++i) 
#define FORR(i,a,b) for(i=(a);i>(b);--i)
#define REP(i,n) for(i=0;i<(n);++i)
#define REPR(i,n) for(i=(n);i>0;--i)
#define PB push_back
#define ll long long
#define INT_MAX 2147483647
#define LL_MAX 9223372036854775807
#define sortR(a,b) sort(a, b, greater<int>())

using namespace std;

	long long GCD(long long a, long long b) {
		if (a < b)
			swap(a, b);
		if (b == 0) return a;
		else return GCD(b, a % b);
	}
	bool sosuu_check(int num) {
		int i;
		for (i = 2; i <= sqrt(num); ++i) {
			if (num%i == 0)
				return false;
		}
		return (num < 2) ? false : true;
	}
	int check(int N, int a, int b) {
		int A,B,i;
		if (a > b) {
			A = a;
			B = b;
		}
		else {
			A = b;
			B = a;
		}
		for (i = N / b; i > 0; i--) {
			if ((N - b * i) % a == 0) {
				return i;
			}
		}
		return 0;
	}


int main() {
	int N, M,i,Ai,K,j;
	cin >> N >> M;
	vector<int> A(31),ans(31);
	cin >> K;
	REP(j, K) {
		cin >> Ai;
		ans[Ai] = 1;
	}
	REP(i, N - 1) {
		cin >> K;
		REP(j, K) {
			cin >> Ai;
			A[Ai] = 1;
		}
		REP(j, 31)
			if (A[j] == 0) 
				ans[j] = 0;
		REP(j, 31) 
			A[j] = 0;
	}
	int sum = 0;
	REP(i, 31) {
		if (ans[i] == 1) {
			sum++;
		}
	}
	cout << sum << endl;
}

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

int main() {
  double n,a;
  int s,max;
  max=0;
  cin>>n;
  if(n==1000) max=n;
  else
    for(double i=2;i<10;i++){
      a=pow(n,1/i);
      s=a;
      s=pow(s,i);
      if(s>max) max=s;  
    }
  cout<<max<<endl;  
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
void debug() {cout<<endl;}
template<typename T,typename... Args>
void debug(T x,Args... args) {cout<<x<<" ";debug(args...);}
#define forn(i,a,b) for(int i=a;i<b;++i)
#define pb push_back
#define F first
#define S second
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pii;

const int MAX = 100005;
vector<int> g[MAX];
int dp[MAX], n, m;

int f(int u){
    int &ans = dp[u];
    if(ans != -1)return ans;
    ans = 0;
    for(int v: g[u]){
        ans = max(ans, f(v)+1);
    }
    return ans;
}


int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  
  int u, v;
  cin >> n >> m;
  forn(i, 0, m){
      cin >> u >> v;
      u--, v--;
      g[u].pb(v);
  }
  memset(dp, -1, sizeof dp);
  int ans = 0;
  forn(i, 0, n){
      if(dp[i]==-1)ans = max(ans, f(i));
  }
  cout << ans << endl;



}





Measured memory_bytes: 11420
N,M,X,Y = map(int, input().split())
Z = 300

x_list = [int(n) for n in input().split()]
y_list = [int(n) for n in input().split()]
if max(x_list) >= min(y_list):
    Z=300
else:
    for i in range(max(x_list)+1,min(y_list)+1):
        if X<i and i<=Y and max(x_list)<i and min(y_list)>=i:
            Z = i
print("War" if Z==300 else "No War")


Measured memory_bytes: 3060
#include <bits/stdc++.h>
#define rep(i, a, b) for(ll i = ll(a); i < ll(b); i++)
#define rer(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)
#define sz(v) (int)(v).size()
#define pb push_back
#define sc second
#define fr first
#define sor(v) sort(v.begin(),v.end())
#define rev(s) reverse(s.begin(),s.end())
#define lb(vec,a) lower_bound(vec.begin(),vec.end(),a)
#define ub(vec,a) upper_bound(vec.begin(),vec.end(),a)
#define uniq(vec) vec.erase(unique(vec.begin(),vec.end()),vec.end())
using namespace std;
typedef long long int ll;
typedef pair <int, int> P;

const ll MOD=1000000007;
ll b[200000];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N;
    cin>>N;
    int p[N];
    rep(i,0,N) cin>>p[i];
    ll a[N];
    rep(i,0,N){
        a[p[i]-1]=20010*p[i]+i+1;
    }
    rep(i,0,N){
        if(i==N-1) cout <<a[i]<<"\n";
        else cout <<a[i]<<" ";
    }
    rep(i,0,N){
        if(i==N-1) cout <<20010*(N-1-i)+1<<"\n";
        else cout <<20010*(N-1-i)+1<<" ";
    }
}

Measured memory_bytes: 896
#include<bits/stdc++.h>
using namespace std;
int i,j,n,m;
string a;
int main(){
    cin>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(cin>>a && a[0]=='s' && a[1]=='n' && a[2]=='u' && a[3]=='k' && a[4]=='e')
                cout<<char('A'+j-1)<<i<<endl;
    return 0;
}

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

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	#endif

	int n, a;
	cin >> n;
	double sum = 0;
	vector<int> arr;
	for(int i = 0; i < n; i++) {
		cin >> a;
		arr.push_back(a);
		sum += a;
	}
	sum /= n;
	sum = round(sum);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		ans += (arr[i] - sum) * (arr[i] - sum);
	}
	cout << ans;
	return 0;
}

Measured memory_bytes: 3676
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<vector>
#include<iostream>
using namespace std;
#define rep(i,s,t) for(register int i=s;i<=t;++i)
#define _rep(i,s,t) for(register int i=s;i>=t;--i)
const int N=1e7+11;
string las,now;
char s[N];
int ans;
int main(){
	scanf("%s",s+1);
	for(int i=1;s[i];++i){
		now+=s[i];
		if(now!=las)
			las=now,++ans,now="";
	}
	printf("%d\n",ans);
	return 0;
}

Measured memory_bytes: 384
#include <vector>
#include <iostream>
#include <algorithm>

#pragma warning(disable : 4996)

using namespace std;

int main()
{
	int n, k, c; bool t;

	while (true)
	{
		t = false;

		scanf("%d", &n);
		scanf("%d", &k);
		
		if (n == 0 && k == 0) { break; }

		vector<bool> r(n, false);

		for (int i = 0; i < k; i++)
		{
			scanf("%d", &c);

			if (c != 0)
			{
				r[c - 1] = true;
			}
			else
			{
				t = true;
			}
		}

		vector<bool> d; vector<int> e; int sum = 1;

		for (int i = 1; i < n; i++)
		{
			if (r[i - 1] != r[i])
			{
				d.push_back(r[i - 1]);
				e.push_back(sum);

				sum = 1;
			}
			else
			{
				sum++;
			}
		}

		d.push_back(r[n - 1]);
		e.push_back(sum);

		int ret = 0;

		if (t)
		{
			if (d.size() >= 3)
			{
				for (int i = 0; i < d.size(); i++)
				{
					if (d[i] && i >= 2)
					{
						if (e[i - 1] == 1)
						{
							ret = max(ret, e[i - 2] + e[i] + 1);
						}
						else
						{
							ret = max(ret, max(e[i - 2], e[i]) + 1);
						}
					}
					else if(d[i])
					{
						ret = max(ret, e[i] + i);
					}
				}
			}
			else
			{
				for (int i = 0; i < d.size(); i++)
				{
					if (d[i])
					{
						ret += e[i];
					}
				}

				ret += 1;
			}
		}
		else
		{
			for (int i = 0; i < d.size(); i++)
			{
				if (d[i])
				{
					ret = max(ret, e[i]);
				}
			}
		}

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

	return 0;
}

Measured memory_bytes: 3320