akhauriyash/Code-Regression huggingface dataset:
N = int(input())
a = list(map(int, input().split()))
c = []
i=1
for k in range(N): 
    if a[k]==i:
        i += 1
    else:
        c.append(a[k])
if len(c)>=len(a):
    print(-1)
else:
    print(len(c))

Measured memory_bytes: 24872
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using P = pair<int, int>;

const ll INF64 = 1LL << 60;
const int INF32 = 1 << 29;

int main(){
    int h, w, d; cin >> h >> w >> d;
    vector<vector<P> >vec(d, vector<P>((h*w)/d+1) );
    for(int i = 0; i < h; ++i){
    	for(int j = 0; j < w; ++j){
    	    int a; cin >>a;
            vec[a%d][a/d]= {i+1, j+1};
        }
    }
    vector<vector<int> >sum(d, vector<int>((h*w)/d+2));
    
    for(int i = 0; i < d; ++i){
    	  for(int j = 1; j < (h*w)/d+1; ++j){
    	      int tmp1 = abs(vec[i][j].first - vec[i][j-1].first );
              int tmp2 = abs(vec[i][j].second - vec[i][j-1].second );
    	      sum[i][j+1] = sum[i][j] + tmp1+ tmp2;
         }
    }

    int q; cin >> q;
    for(int i = 0; i < q; ++i){
    	  int l, r; cin >> l >> r; 
          cout << sum[l%d][r/d+1] - sum[l%d][l/d+1] << endl;
    }
    return 0;
}

Measured memory_bytes: 10240
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
const int N = 505;
const int INF = 1e9;


ll arr[N][N];
int h, w, H, W;

int main()
{                                                     
	ios_base::sync_with_stdio(0);
		
	cin >> H >> W >> h >> w;

	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			if (i % h == h - 1 && j % w == w - 1)
				arr[i][j] = - INF;
			else if (i % h == 0 && j % w == 0)
				arr[i][j] = INF - 1;
			else
				arr[i][j] = 0;

	ll sum = 0;

	for (int i = 0; i < H; i++)
		for (int j = 0; j < W; j++)
			sum += arr[i][j];


	if (sum > 0)
	{
		cout << "Yes\n";
		for (int i = 0; i < H; i++)
		{
			for (int j = 0; j < W; j++)
				cout << arr[i][j] << ' ';
			cout << '\n';
		}
	}
	else
		cout << "No\n";


	return 0;
}


Measured memory_bytes: 4864
#include <bits/stdc++.h>
using namespace std;
void read(int &x){
	char ch=getchar();x=0;
	for (;ch==' '||ch=='\n';ch=getchar());
	for (;ch!=' '&&ch!='\n';x=x*10+ch-'0',ch=getchar());
}
void write(int x){
	if (x>9) write(x/10);
	putchar(x%10+'0');
}
int n;
vector<int>g[100004];
vector<int>get_[100004];
bool cmp(int a,int b){
	return a>b;
}
int dfs(int x){
	int res=0;
	for (int i=0;i<g[x].size();i++)
		get_[x].push_back(dfs(g[x][i]));
	sort (get_[x].begin(),get_[x].end(),cmp);
	for (int i=0;i<get_[x].size();i++) res=max(res,get_[x][i]+i+1);
	return res;
}
int main(){
	read(n);
	for (int i=2;i<=n;i++){
		int p;read(p);
		g[p].push_back(i);
	}
	write(dfs(1));
}

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

using namespace std;


void solve() {
    int n,m;
    cin >> n >> m;
    int a = m/2;
    int b = m - a;
    int l = 1, r = l + a*2;
    int L = r+1, R = L + b*2-1;
    assert(R<=n);
    while (a--) {
        cout << l << ' ' << r << '\n';
        l++;r--;
    }
    while (b--) {
        cout << L << ' ' << R << '\n';
        L++;R--;
    }
    
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
    return 0;
}


Measured memory_bytes: 3592
#include<iostream>
#include<iomanip>
#include<cmath>
#include<string>
#include<vector>
#include<list>
#include<algorithm>
#include<map>
#include<set>
#include<queue>
#include<stack>
using namespace std;
typedef long long ll;
#define fi first
#define se second
#define mp make_pair
#define rep(i, n) for(int i=0;i<n;++i)
#define rrep(i, n) for(int i=n;i>=0;--i)
const int inf=1e9+7;
const ll mod=1e9+7;
const ll big=1e18;
const double PI=2*asin(1);

int main() {
  int N;
  cin>>N;
  vector<string> S(N);
  for(int i=0;i<N;++i) cin>>S[i];
  vector<vector<int> > edge(N);
  for(int i=0;i<N;++i) {
    for(int j=0;j<N;++j) {
      if(S[i][j]=='1') edge[i].push_back(j);
    }
  }
  bool can;
  int ans = -1;
  queue<int> que;
  int state;
  for (int l=0;l<N;++l) {
    map<int, int> amap;
    amap[l] = 1;
    can = true;
    que.push(l);
    while(!que.empty()) {
      state = que.front();que.pop();
      for(int i=0;i<edge[state].size();++i) {
        if(amap[edge[state][i]]>0) {
          if(abs(amap[edge[state][i]]-amap[state])!=1) can = false;
          continue;
        }
        amap[edge[state][i]] = amap[state]+1;
        que.push(edge[state][i]);
      }
    }
    if(can){
      for(int i=0;i<N;++i) ans = max(ans, amap[i]);
    }
  }
  cout<<ans<<endl;
}



Measured memory_bytes: 3812
#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <queue>
#include <map>
#include <algorithm>
#include <functional>
#include <string>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <tuple>
using namespace std;

#define REP(i,p,n) for(ll i=p;i<ll(n);++i)
#define rep(i,n) REP(i,0,n)

using ll = unsigned long long int;
using pll = pair<ll, ll>;

int main()
{
    ll X;
    cin >> X;

    ll x = 100, k = 0;

    while (x < X)
    {
        x += x / 100;
        ++k;
    }

    cout << k << endl;

    return 0;
}


Measured memory_bytes: 3652
N, Q = map(int, input().split())

S = input()
items = []
for i in range(Q):
    t, d = input().split()
    items.append((t, d))

left_ok = -1
left_ng = N

while left_ng - left_ok > 1:
    mid = (left_ok + left_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "L":
                if tmp - 1 == -1:
                    flag = True
                    break
                start = S[tmp - 1]
                tmp -= 1
            else:
                if tmp + 1 >= N:
                    break
                start = S[tmp + 1]
                tmp += 1

    if flag:
        left_ok = mid
    else:
        left_ng = mid


right_ok = N
right_ng = -1

while right_ok - right_ng > 1:
    mid = (right_ok + right_ng) // 2
    flag = False
    start = S[mid]
    tmp = mid
    for t, d in items:
        if t == start:
            if d == "R":
                if tmp + 1 == N:
                    flag = True
                    break
                start = S[tmp + 1]
                tmp += 1
            else:
                if tmp - 1 == -1:
                    break
                start = S[tmp - 1]
                tmp -= 1

    if flag:
        right_ok = mid
    else:
        right_ng = mid
ans = N
if left_ok != -1:
    ans -= left_ok + 1

if right_ok != N:
    ans -= N - right_ok

if left_ok >= right_ok:
    ans = 0

print(ans)


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

int main() {
    int n,a[100];
    cin >> n;
    for(int i=0; i<n; i++) 
     cin >> a[i];
    for(int i=n-1; i>=0; i--) 
     cout << a[i] << (i==0?'\n':' ');
    
}



Measured memory_bytes: 3092
#include <iostream>
#include <queue>
#include <map>
#include <set>

using namespace std;

typedef long long ll;

ll v[101][101][304], t[101][2], n, w;

int main() {
    cin >> n >> w;
    for (ll i = 0; i < n; i++) cin >> t[i][0] >> t[i][1];
    for (ll i = 0; i < n; i++) {
        for (ll j = 0; j < 100; j++) {
            for (ll k = 0; k < 300; k++) {
                v[i + 1][j + 1][k + (t[i][0] - t[0][0])] = max(v[i + 1][j + 1][k + (t[i][0] - t[0][0])],
                                                               v[i][j][k] + t[i][1]);
                v[i + 1][j][k] = max(v[i + 1][j][k], v[i][j][k]);
            }
        }
    }
    ll r = 0;
    for (ll j = 0; j < 100; j++) {
        for (ll k = 0; k < 300; k++) {
            if (j * t[0][0] + k <= w) r = max(r, v[n][j][k]);
        }
    }
    cout << r << endl;
}

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

using namespace std;
typedef long long ll;
typedef long int li;
typedef long double lb;
#define rep(i,j,n) for (ll i = j; i < (n); i++)
#define repr(i,j,n) for(ll i = j; i >= (n); i--)
#define all(x) (x).begin(),(x).end()
#define CLR(mat,f) memset(mat, f, sizeof(mat))
#define IN(a, b, x) (a<=x&&x<b)
#define out(ans) cout << ans << endl
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
typedef pair<ll,ll>P;
const ll mod=1e9+7;
const ll INF = 1LL<<60;

int main(){

  ll n;cin>>n;
  bool e[4][13];
  char mark[]={'S','H','C','D'};
  rep(i,0,4)CLR(e[i],true);

  rep(i,0,n){
    char c;cin>>c;
    ll m;
    rep(j,0,4)if(mark[j]==c)m=j;

    ll num;cin>>num;
    e[m][--num]=false;
  }

  rep(i,0,4){
    rep(j,0,13){
      if(e[i][j])out(mark[i]<<" "<<j+1);
    }
  }


  return 0;
}



Measured memory_bytes: 3084
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <queue>
#include <algorithm>
using namespace std;
typedef unsigned int uint;
typedef long long ll;
typedef pair<int, int> P;
const int c_INF = 111111111;
const int c_mINF = -111111111;
const int c_YET = -1;
const int c_Dx[4] = { 0,0,1,-1 };
const int c_Dy[4] = { 1,-1,0,0 };
const int c_div = 1000000007; //10^9 + 7


int main() {

	int A,B,C;
	scanf("%d%d%d", &A, &B,&C);

	if (A*C <= B) {
		printf("%d", C);
	}
	else {
		printf("%d", B / A);
	}



}

Measured memory_bytes: 128
#include<iostream>
#include<iomanip>
#include<climits>
#include<vector>
#include<list>
#include<functional>
#include<algorithm>
#include<string>
#include<cmath>
#include<complex>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<tuple>
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;
typedef long long ll;
typedef pair<int, int> P;



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

	string s[3] = { "Sunny", "Cloudy", "Rainy" };
	string S;
	cin >> S;
	int i = 0;
	while (s[i] != S) i++;
	cout << s[(i + 1) % 3] << endl;

	return 0;
}

Measured memory_bytes: 256
import sys
import copy
sys.setrecursionlimit(4100000)

n,m = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for i in range(m)]
t = [int(i) for i in input().split()]
from collections import defaultdict
steps = defaultdict(list)
for a,b in l:
    steps[a].append(b)
seen = set()
counter = 0
queue = [t[0]]
nextqueue = []
ans = False
depth = 0
while queue:
    current = queue.pop(0)
    if counter == 0 and current == t[1]:
        ans = True
        break
    if counter == 3 and current == t[1]:
        ans = True
        break
    for a in steps[current]:
        if (a,counter+1) not in seen:
            seen.add((a,counter+1))
            nextqueue.append(a)
    if queue == []:
        if counter == 3:
            counter = 1
        else:
            counter += 1
        queue = copy.deepcopy(nextqueue)
        nextqueue = []
        depth += 1

if ans is True:
    print(depth//3)
else:
    print(-1)


Measured memory_bytes: 68812
/*************************************************************************
    > File Name: D.cpp
    > Author: Roundgod
    > Mail: wcysai@foxmail.com 
    > Created Time: 2018-09-02 12:20:11
 ************************************************************************/

#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define MAXN 100005
#define INF 1000000000
#define MOD 1000000007
#define F first
#define S second
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int n,m,L;
struct edge{int u,v,cost;};
vector<edge> ans;
int main()
{
    scanf("%d",&L);
    int t=1;n=1;
    while(t*2<=L) t*=2,n++;
    for(int i=1;i<n;i++)
    {
        ans.push_back((edge){i,i+1,1<<(i-1)});
        ans.push_back((edge){i,i+1,0});
    }
    int cur=t;
    for(int i=n-1;i>=1;i--)
    {
        if((cur+(1<<(i-1)))<=L)
        {
            ans.push_back((edge){i,n,cur});
            cur+=(1<<(i-1));
        }
    }
    printf("%d %d\n",n,(int)ans.size());
    for(int i=0;i<(int)ans.size();i++)
        printf("%d %d %d\n",ans[i].u,ans[i].v,ans[i].cost);
    return 0;
}



Measured memory_bytes: 256
#include <iostream>
#include <cstdio>
#include <string>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
typedef long long int ll;
int N,Q,K;
vector<int> G[100001],H[100001];
ll dist[100001];
//int x[100001],y[100001];

void dfs(int x,int p){
  for(int i=0;i<G[x].size();i++){
    if(G[x][i]==p)continue;
    dist[G[x][i]]=dist[x]+H[x][i];
    dfs(G[x][i],x);
  }
}
int main(){
  cin >> N;
  for(int i=0;i<N-1;i++){
    int a,b,c;
    cin >> a >> b >> c;
    a--;b--;
    G[a].push_back(b);
    H[a].push_back(c);
    G[b].push_back(a);
    H[b].push_back(c);
  }
  cin >> Q >> K;
  K--;
  dfs(K,-1);
  for(int i=0;i<Q;i++){
    //cin >> x[i] >> y[i];
    int x,y;
    cin >> x >> y;
    x--;y--;
    cout << dist[x]+dist[y] << endl;
  }
 
  //for(int i=0;i<N;i++) printf("%d ",dist[i]);
  
  
  return 0;
}


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

string zeros[] = {"", "0", "00", "000", "0000", "00000"};

struct Data {
    int Prefecture, City, pos, rank;
    //演算子をオーバーロードすることで比較関数を作成
    bool operator<(const Data& another) const {
        if (Prefecture != another.Prefecture) return Prefecture < another.Prefecture; // 昇順に並べる
        if (City != another.City) return City < another.City; // 同様に比較演算子を定義
        if (pos != another.pos) return pos < another.pos;
        return rank < another.rank;
    }
};


struct Ans {
    string ans;
    int pos;
    bool operator<(const Ans& another) const {
        if(pos != another.pos) return pos < another.pos;
        return ans < another.ans;
    }
};

int main(){
    int n, m;
    cin >> n >> m;
    vector<Data> v(m);

    for(int i=0; i<m; i++){
        cin >> v[i].Prefecture >> v[i].City;
        v[i].pos = i;
    }

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

    //ランクを計算
    int j = 0;
    for(int i=1; i<=n; i++){
        int r = 1;
        while(i == v[j].Prefecture){
            v[j].rank = r;
            r++;
            j++;
        }
    }

    vector<Ans> ans(m);

    //output result
    for(int i=0; i<m; i++){
        string prefix = to_string(v[i].Prefecture);
        prefix = zeros[(6-prefix.size())] + prefix;

        string code = to_string(v[i].rank);
        code = zeros[(6-code.size())] + code;

        ans[i].pos = v[i].pos;
        ans[i].ans = prefix + code;
    }

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

    for(int i=0; i<m; i++) cout << ans[i].ans << endl;

    return 0;
    
}


Measured memory_bytes: 10880
#include <stdio.h>

long gcd(int a,int b);
long lcm(int a,int b,int n);

int main(void) {

  int a,b;
  
  while(scanf("%d %d",&a,&b)!=EOF) {

    printf("%ld %ld\n",gcd(a,b),lcm(a,b,gcd(a,b)));

  }

  return 0;

}

long gcd(int a,int b) {

  int temp;

  if(a<b) {
    temp=a;
    a=b;
    b=temp;
  }

  if(b==0) return a;

  else return gcd(b,a%b);

}

long lcm(int a,int b,int n) {

  return a/n*b;

}

Measured memory_bytes: 0
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace Sorting_Three_Number
{
    class Program
    {
        static void Main(string[] args)
        {
            int a, b, c;
            string[] str = Console.ReadLine().Split(' ');
            a = int.Parse(str[0]);
            b = int.Parse(str[1]);
            c = int.Parse(str[2]);

            if (a >= b && b >= c)
                Console.WriteLine(c + " " + b + " " + a);
            else if (a >= c && c >= b)
                Console.WriteLine(b + " " + c + " " + a);
            else if (b >= a && a >= c)
                Console.WriteLine(c + " " + a + " " + b);
            else if (b >= c && c >= a)
                Console.WriteLine(a + " " + c + " " + b);
            else if (c >= a && a >= b)
                Console.WriteLine(b + " " + a + " " + c);
            else
                Console.WriteLine(a + " " + b + " " + c);
        }
    }
}

Measured memory_bytes: 9172
package main

import (
	"fmt"
	"sort"
	"strings"
)

func main() {
	var n int
	fmt.Scan(&n)

	dic := make(map[string]int , n)
	for i := 0; i < n; i++ {
		var s string
		fmt.Scan(&s)

		ss := split(s)
		sort.Strings(ss)
		//si = append(si, strings.Join(ss,""))
		dic[strings.Join(ss,"")]++
	}

	cnt := 0
	for _, v := range dic {
		cnt+= v * (v-1) / 2
	}

	fmt.Println(cnt)
}

func split(s string) []string {
	ret := make([]string, len([]rune(s)))
	for i, v := range []rune(s) {
		ret[i] = string(v)
	}
	return ret
}


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

typedef pair<ll, ll>P;
typedef pair<ll, P>PP;

int main(){


    ll N, Q;
    cin >> N >> Q;
    vector<PP>v;
    for(ll i = 0; i < N; i++){
        ll s, t, x;
        cin >> s >> t >> x;
        v.push_back(PP(x, P(s - x, t - x - 1)));
    }
    sort(v.begin(), v.end());
    set<P>S;
    S.insert(P(1111111111LL,-1));
    vector<ll>ans(Q, -1);
    for(ll i = 0; i < Q; i++){
        ll d;
        cin >> d;
        S.insert(P(d, i));
    }
    for(ll i = 0; i < N; i++){
        ll x = v[i].first;
        ll L = v[i].second.first;
        ll R = v[i].second.second;
        for(;;){
            set<P>::iterator it = S.lower_bound(P(L, 0));
            if((*it).first > R)break;
            ans[(*it).second] = x;
            S.erase(it);
        }        
    }
    for(ll i = 0; i < Q; i++){
        cout << ans[i] << endl;
    }

    return 0;
}

Measured memory_bytes: 21356
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second
#define dbg(x) cout<<#x" = "<<((x))<<endl
template<class T,class U> ostream& operator<<(ostream& o, const pair<T,U> &p){o<<"("<<p.fi<<","<<p.se<<")";return o;}
template<class T> ostream& operator<<(ostream& o, const vector<T> &v){o<<"[";for(T t:v){o<<t<<",";}o<<"]";return o;}

const int N = 100000;
vector<int> G[N];

using pl = pair<ll,ll>;

ll base[2] = {101119, 101141};
ll mod[2] = {1000000007,1000000021};
pl h[N];
void dfs(int v, int p){
    pl ret(0,0);
    for(int c:G[v])if(c!=p){
        dfs(c, v);
        (ret.fi += h[c].fi) %= mod[0];
        (ret.se += h[c].se) %= mod[1];
    }

    (ret.fi *= base[0]) %= mod[0];
    (ret.se *= base[1]) %= mod[1];

    (ret.fi += 1) %= mod[0];
    (ret.se += 1) %= mod[1];

    h[v] = ret;
}

int main(){
    int n;
    cin >>n;
    rep(i,n-1){
        int a,b;
        cin >>a >>b;
        --a; --b;
        G[a].pb(b);
        G[b].pb(a);
    }

    dfs(0,-1);

    map<pl,ll> ct;
    rep(i,n) ++ct[h[i]];

    ll ans = 0;
    for(const auto &p:ct){
        ll x = p.se;
        ans += x*(x-1)/2;
    }
    cout << ans << endl;
    return 0;
}



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

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define REP1(i,n) for(int i=1, i##_len=(n); i<i##_len; ++i)
#define ll long long
static const int MAX = 10000;
static const ll INFTY = 1e12;

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }


const ll MRINF = 5000000000000000;
int main() {

    ll A, V, B, W, T;
    cin >> A >> V >> B >> W >> T;
    if(W >= V){
        cout << "NO" << endl;
        return 0;
    }

    ll D = abs(A-B);
    ll D2 = (V-W)*T;

    if(D > D2 ){
        cout << "NO" << endl;
    }else{
        cout << "YES" << endl;
    }
}
/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
         pass System Test!
*/

Measured memory_bytes: 3628
n,x = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
cnt = 0
while a[cnt] <= x:
    x = x - a[cnt]
    cnt += 1
    if cnt >= len(a):
        break
if x > 0 and len(a) == cnt:
    cnt -= 1
print(cnt)

Measured memory_bytes: 3060
#include <iostream>
#include <vector>
#include <algorithm>
#include <limits>
#include <cmath>
#include <queue>
#include <tuple>

using namespace std;

struct edge {
  int to;
  int distance;
};

const long long int NOT_CONNECT = numeric_limits<long long int>::max() / 2;

int main() {
  int n,m,l,a,b,c;
  cin >> n >> m >> l;

  vector<vector<long long int>> distances(n+1, vector<long long int>(n+1, NOT_CONNECT));
  for (int i = 0; i < m; i++) {
    cin >> a >> b >> c;
    distances[a][b] = c;
    distances[b][a] = c;
  }

  // ワーシャル・フロイド法で全点間の距離を算出する
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (distances[i][j] > distances[i][k] + distances[k][j]) {
          distances[i][j] = distances[i][k] + distances[k][j];
        }
      }
    }
  }

  // l以下の部分だけ辺を残す
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      if (distances[i][j] <= l) {
        distances[i][j] = 1;
      } else {
        distances[i][j] = NOT_CONNECT;
      }
    }
  }

  // もう一度ワーシャル・フロイド法で全点間の距離を算出する
  for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
      for (int j = 1; j <= n; j++) {
        if (distances[i][j] > distances[i][k] + distances[k][j]) {
          distances[i][j] = distances[i][k] + distances[k][j];
        }
      }
    }
  }

  int q,s,t;
  cin >> q;
  for (int i = 0; i < q; i++) {
    cin >> s >> t;
    long long int result = distances[s][t];
    if (result == NOT_CONNECT) {
      result = -1; // 到達できない
    } else {
      result--; // 補給する回数は、通る街-1 (最初の町までは無補給なので)
    }
    cout << result << endl;
  }
}


Measured memory_bytes: 1280
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define INF 0x3f3f3f3f 
#define MEM(x,y) memset(x,y,sizeof(x))
#define int long long
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
#define P pair<int,int>
#define  sc(a) scanf("%lld",&a)
#define pf(a) printf("%lld ",a)
using namespace std;
string q;
signed main()
{       

	cin >> q;
	if (q[2] == q[3] && q[4] == q[5])
		cout << "Yes" << endl;
	else
		cout << "No" << endl;
}


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

int main() {
    int S;
    cin >> S;
    int a = S/1000;
    int b = (S%1000)/100;
    int c = (S%100)/10;
    int d = (S%10);
    if(a == b or b == c or c== d){
        cout << "Bad" << endl;
    }
    else{
        cout <<"Good" << endl;
    }

}

Measured memory_bytes: 256
def sieve(n):
    is_prime = [True]*(n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]:
            continue
        else:
            for j in range(i*2, n+1, i):
                is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

n = int(input())
prime_lst = sieve(55555)

res = []
for p in prime_lst:
    if p%5==1:
        res.append(p)
print(*res[:n])

Measured memory_bytes: 3700
#include<bits/stdc++.h>
using namespace std;
int main() {
	int n;
	cin>>n;
    if(n%10==9||n/10==9) {
        cout<<"Yes"<<'\n';
        return 0;
    } else {
        cout<<"No"<<'\n';
	    return 0;
    }
}

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

#define rep(i,n) for(ll i = 0; i < n; i++)
#define per(i,n) for(ll i = n-1; i >= 0; i--)
#define REP(i,n) for(ll i = 1; i < n; i++)
#define PER(i,n) for(ll i = n; i >= 1; i--)
#define sz(x) int(x.size())
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define YesorNo(a) printf(a ? "Yes\n" : "No\n")
#define endl '\n'
#define fi first
#define se second
using ll = long long;
using P = pair<int,int>;
using Pl = pair<ll,ll>;
using vi = vector<int>;
using vii = vector<vi>;
using vl = vector<ll>;
using vll = vector<vl>;
using vs = vector<string>;
using vb = vector<bool>;
using vc = vector<char>;
using vcc = vector<vc>;
using vP = vector<P>;
using vPP = vector<vP>;
using vPl = vector<Pl>;
const int dx[] = {0,1,0,-1,1,1,-1,-1};
const int dy[] = {1,0,-1,0,1,-1,-1,1};
const int inf = (1<<30)-1;
const ll infll = (1LL<<62)-1;
ll ceil(const ll &a, const ll &b){return ((a)+(b)-1)/b;}
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; }


long long Digsum(long long x){
  long long res = 0;
  while(x > 0){
    res += x % 10;
    x /= 10;
  }
  return res;
}


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

  int n;
  cin >> n;
  YesorNo(n % Digsum(n) == 0);
}

Measured memory_bytes: 256
#define _USE_MATH_DEFINES

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <string>
#include <utility>
#include <climits>
#include <vector>
#include <map>
#include <queue>
using namespace std;

#define ll long long
const int MOD = 1000000007;//10^9+7
const string SPACE = " ";

ll max(ll a, ll b) {

	if (a > b)return a;
	else return b;

}
double max(double a, double b) {

	if (a > b)return a;
	else return b;

}
//aとbの大きい方

ll min(ll a, ll b) {

	if (a < b)return a;
	else return b;

}
//aとbの小さい方

ll avd_i(ll a, ll b) {

	if (a > b)return a - b;
	else return b - a;

}
double avd_d(double a, double b) {

	double re;
	if (a > b)re = a - b;
	else re = b - a;
	return re;

}
//aとbの差の絶対値

ll powsur(ll a, ll b, ll p) {

	if (b == 0) {

		return 1;

	}
	else if (b % 2 == 0) {

		ll d = powsur(a, b / 2, p);
		return ((d%p)*(d%p)) % p;

	}
	else {

		return ((a%p)*powsur(a, b - 1, p) % p) % p;

	}

}
//pは素数,aのb乗をpで割った余り

ll CMOD(ll n, ll r, ll p) {

	ll a = 1, b = 1, c = 1, re;
	for (int i = 1; i <= n; i++) {

		a *= i;
		a = a%p;

	}
	for (int i = 1; i <= r; i++) {

		b *= i;
		b = b%p;

	}
	for (int i = 1; i <= n - r; i++) {

		c *= i;
		c = c%p;

	}
	b = powsur(b, p - 2, p);
	c = powsur(c, p - 2, p);
	re = ((a%p)*(b%p)) % p;
	re = ((re%p)*c%p) % p;

	return re;

}
//pは素数,(nCr)%p

ll gcd(ll a, ll b) {

	if (a > b) {

		ll tmp = a;
		a = b;
		b = tmp;

	}
	ll r;
	r = b%a;
	if (r == 0)return a;
	else return gcd(r, a);

}
//最大公約数

ll lcm(ll a, ll b) {

	return (a / gcd(a, b))*b;

}
//最小公倍数

int main() {

	string S;
	bool check = false;

	cin >> S;

	for (int i = 0; i < S.size() - 1; i++) {

		if (S[i] == 'A'&&S[i + 1] == 'C')check = true;

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

	return 0;
}

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

int main(){
    int days = 0;
    string S;
    cin >> S;

    if(S[0] == 'R' && S[1] == 'R' && S[2] == 'R'){
        days = 3;
    }else if(S[0] == 'R' && S[1] == 'R'){
        days = 2;
    }else if(S[1] == 'R' && S[2] == 'R'){
        days = 2;
    }else if(S[0] == 'R'){
        days = 1;
    }else if(S[1] == 'R'){
        days = 1;
    }else if(S[2] == 'R'){
        days = 1;
    }

    cout << days << endl;
}



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

int main(){
  string s;
  cin >> s;
  int count=0;
  bool judge=true;
  for(int i=0; i<s.size()/2; i++){
    if(s.substr(count,2)=="hi"){
      count +=2;
    }
    else judge=false;
  }
  if(s.size()%2==1) judge=false;
  if(judge==true) cout << "Yes" << endl;
  else cout << "No" << endl;
}

Measured memory_bytes: 256
import java.util.*;

public class Main {
	public static boolean is_prime(int x){
		switch(x){
		case 2 : return true;
		case 3 : return true;
		default:
			for(int e = 2 ; e <= Math.sqrt(x) ; e++){
				if(x % e ==0) return false;
			}
		return true;
		
		}
	}
	public static void main(String[] args) {
		int c = 0;
		Scanner scn = new Scanner(System.in);
		int N = scn.nextInt();
		boolean[] tof = new boolean[100000000];
		Arrays.fill(tof, false);
		for(int i = 1 ; i <= N ; i++){
			int k = scn.nextInt();
			if(tof[k-1] == false){
				tof[k-1] = is_prime(k);
			}
		}
		for(int j = 0 ; j < 100000000 ; j++){
			if(tof[j] == true) c++;
		}
		System.out.println(c);
	}

}

Measured memory_bytes: 134564
#include <bits/stdc++.h>
using Int = long long;  // clang-format off
#define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++)
#define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__)
#define ALL(v) std::begin(v), std::end(v)
struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io;
#ifndef dump
#define dump(...)
#endif  // clang-format on

/**
 *    author:  knshnb
 *    created: Tue Jul 21 18:31:19 JST 2020
 **/

void solve() {
    Int n;
    std::cin >> n;
    std::vector<std::vector<Int>> bl(n), br(n);
    Int ans = 0;
    REP(i, n) {
        Int k, l, r;
        std::cin >> k >> l >> r, k--;
        ans += std::min(l, r);
        if (l > r) {
            bl[k].push_back(l - r);
        } else {
            if (n - 2 - k >= 0) br[n - 2 - k].push_back(r - l);
        }
    }
    for (auto& v : {bl, br}) {
        std::priority_queue<Int> pq;
        for (Int i = n - 1; i >= 0; i--) {
            for (Int x : v[i]) pq.push(x);
            if (pq.size()) ans += pq.top(), pq.pop();
        }
    }
    std::cout << ans << "\n";
}
signed main() {
    Int T;
    std::cin >> T;
    while (T--) solve();
}


Measured memory_bytes: 31340
#include<bits/stdc++.h>
using namespace std;
int main(){
        int n;cin>>n;
        int arr[101];
        memset(arr,0,sizeof(arr));
        int u,v;
        for(int i=1;i<=n;i++)
        {
            cin>>u>>v;
            if(u==v){
                arr[i]=1;
            }    
        }
        bool isT=false;
        for(int i=1;i<101 - 2;i++){
            if(arr[i]==1 && arr[i+1]==1 && arr[i+2]==1) isT = true;
        }
        if(isT) cout<<"Yes\n";
        else cout<<"No\n";
    return 0;
}

Measured memory_bytes: 3632
#include <bits/stdc++.h>
using namespace std;
//#include <boost/multiprecision/cpp_int.hpp>
//using multiInt = boost::multiprecision::cpp_int;

using ll = long long int;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename Q_temp>
using smaller_queue = priority_queue<Q_temp, vector<Q_temp>, greater<Q_temp>>;

const ll MOD = (ll)(1e9 + 7);
const int INF = (int)1e9;
const ll LINF = (ll)4e18;
const double PI = acos(-1.0);

#define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i)
#define rep(i, n) REP(i, 0, n)
#define MP make_pair
#define MT make_tuple
#define YES(n) cout << ((n) ? "YES" : "NO") << endl
#define Yes(n) cout << ((n) ? "Yes" : "No") << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible") << endl
#define possible(n) cout << ((n) ? "possible" : "impossible") << endl
#define Yay(n) cout << ((n) ? "Yay!" : ":(") << endl
#define all(v) v.begin(), v.end()
#define NP(v) next_permutation(all(v))
#define dbg(x) cerr << #x << ":" << x << endl;

vector<int> Dx = {0, 0, -1, 1, -1, 1, -1, 1, 0};
vector<int> Dy = {1, -1, 0, 0, -1, -1, 1, 1, 0};

inline ll CEIL(ll a, ll b)
{
  return (a + b - 1) / b;
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << setprecision(20) << setiosflags(ios::fixed);
  int h, w, n;
  cin >> h >> w >> n;
  cout << CEIL(n, max(h, w)) << endl;
  return 0;
}


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

#define rep(i, first, to) for(ll i = first; i < to; ++i)

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

const int MAXN = (int)1e5;
int head = 0;
int tail = 0;
P que[MAXN];
bool isEmpty() {
	return head == tail;
}

bool isFull() {
	return head == (tail + 1) % MAXN;
}

void enqueue(P p) {
	que[tail] = p;
	tail = (tail + 1) % MAXN;
}
P dequeue() {
	P v = que[head];
	head = (head + 1) % MAXN;
	return v;
}

void solve() {
	int n, q;
	cin >> n >> q;
	rep(i, 0, n) {
		string s; int v;
		cin >> s;
		cin >> v;
		enqueue(make_pair(s, v));
	}
	int time = 0;
	while(!isEmpty()) {
		P now = dequeue();
		if (now.second > q) {
			time += q;
			now.second -= q;
			enqueue(now);
		} else {
			time += now.second;
			cout << now.first << " " << time << endl;
		}
	}
}
void test() {
	string ss[] = {"a", "b", "c", "d", "e"};
	rep(i, 0, 5) {
		enqueue(make_pair(ss[i], i));
	}
	int i = 0;
	while(!isEmpty()) {
		P p = dequeue();
		cout << p.first << " " << p.second << endl;
	}
}

int main() {
	solve();
	//test();
	return 0;
}

Measured memory_bytes: 6948
#ABC081C
N, K=map(int, input().split())
A=list(map(int,input().split()))
#N=1の時の例外処理
if N==1:
    print(0)
    exit()
#昇順に並べ替える
A_sorted=sorted(A)
#Aの要素の個数を格納するリストの準備
BallCount=[N+1]*N
BallCount_order=0   #ボールの種類と一致する
BallCount_count=1   #注目しているボールの個数
#Aの各要素の個数を数える
for i in range(N-1):
    if A_sorted[i]==A_sorted[i+1]:
        BallCount_count+=1
    else:
        BallCount[BallCount_order]=BallCount_count
        BallCount_order+=1
        BallCount_count=1
    # 末尾処理
    if i == N - 2:
        BallCount[BallCount_order] = BallCount_count
#昇順に並び替え
BallCount_sorted=sorted(BallCount)
#減らすべきボールの種類数
remains=BallCount_order+1-K
#書き換え作業
act_count=0     #作業回数
i=0     #ボール種の序列
while remains>0:
    act_count+=BallCount_sorted[i]
    remains-=1
    i+=1
print(act_count)


Measured memory_bytes: 25472
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long LL;
const int MaxN = 1e5 + 4;

int a[10];

int main() {
	scanf("%d %d %d", &a[1], &a[2], &a[3]);
	int ans = 0;
	while(1) {
		sort(a + 1, a + 4);
		if(a[1] == a[2]) {ans += a[3] - a[1]; break;}
		else a[1] += 2, ans += 1;
	}
	printf("%d\n", ans);
	return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
#define FOR(i, m, n) for (int i = m; i < (n); i++)
#define RFOR(i, m, n) for (int i = (m - 1); i >= 0; i--)
#define REP(i, n) FOR(i, 0, n)
#define RREP(i, n) RFOR(i, n, 0)
#define ALL(v) v.begin(), v.end()
#define RALL(v) v.rbegin(), v.rend()
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;

ll gcd(ll x, ll y) { return y ? gcd(y, x % y) : x; }

ll factorial(ll n) {
  ll answer = 1;
  while (n > 1) {
    answer *= n;
    answer %= mod;
    n--;
  }
  return answer;
}

ll combination(ll n, ll r) {
  return factorial(n) / (factorial(r) * factorial(n - r));
}

ll permutation(ll n, ll r) { return factorial(n) / factorial(n - r); }

template <typename T>
void remove(std::vector<T>& vector, unsigned int index) {
  vector.erase(vector.begin() + index);
}

map<ll, ll> prime_factor(ll n) {
  map<ll, ll> ret;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      ret[i]++;
      n /= i;
    }
  }
  if (n != 1) ret[n] = 1;
  return ret;
}
// for (auto p : prime_factor(n)) {
//	while (p.second--) {
//		cout << p.first << endl;
//	}
//}

vector<ll> divisor(ll n) {
  vector<ll> ret;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      ret.push_back(i);
      if (i * i != n) ret.push_back(n / i);
    }
  }
  sort(begin(ret), end(ret));
  return (ret);
}

int main() {
  string s;
  cin >> s;
  int n = s.size();
  vector<int> a(n + 1);
  REP(i, n) {
    if (s[i] == '<') {
      a[i + 1] = max(a[i + 1], a[i] + 1);
    }
  }
  RREP(i, n) {
    if (s[i] == '>') {
      a[i] = max(a[i], a[i + 1] + 1);
    }
  }
  ll ans = 0;
  REP(i, n + 1) { ans += a[i]; }
  cout << ans << endl;
  return 0;
}

Measured memory_bytes: 2820
#include <iostream>

using namespace std;

int main()
{
    char c;
    cin >> c;
    if (c == 'a' || c == 'i' || c == 'u' || c == 'e' || c == 'o') {
        cout << "vowel" << endl;
    } else {
        cout << "consonant" << endl;
    }
    return 0;
}


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

int gcd(int a,int b)
{
	if (a%b==0)
	{
		return(b);
    }
	else
	{
		return(gcd(b,a%b));
    }
}

int main()
{
    int N;
  cin >> N;
  vector<int> vec(N);
  for (int i=0; i<N; i++){
    cin >> vec.at(i);
  }
  vector<int> hidari(N);
  hidari.at(0)=vec.at(0);
  for (int i=1; i<N; i++){
    hidari.at(i)=gcd(hidari.at(i-1),vec.at(i));
  }//ひだりはひだりからi番目までの最大公約数
    vector<int> migi(N);
  migi.at(N-1)=vec.at(N-1);
    for (int i=N-2; i>=0; i--){
    migi.at(i)=gcd(migi.at(i+1),vec.at(i));
  }//みぎはみぎから(ひだりから)i番目までの最大公約数
  int kouho1 = hidari.at(N-2);
  int kouho2 = migi.at(1);
  int kouho3 =1;
  int aa;
  for (int j =1; j<(N-1); j++){
    aa=gcd(hidari.at(j-1),migi.at(j+1));
    kouho3 = max(aa,kouho3);
  }
  int ans;
  ans = max(kouho1,kouho2);
  ans = max(ans,kouho3);
  cout << ans <<endl;
}




Measured memory_bytes: 1536
#include <iostream>
#include <string>
#include<vector>
#include<algorithm>
#include<math.h>
#include<limits.h>
#include<string>
#include<iomanip>
#include<numeric>
#include<queue>
using namespace std;

long long  mod = 1000000007;

long max(long x, long y) {
	return x > y ? x : y;
}

long min(long x, long y) {
	return x < y ? x : y;
}

long factorial(long n) {
	if (n == 1) {
		return 1;
	}
	else {
		return n * factorial(n - 1);
	}
}

long long  fel(long long  n,long long  f) {

		if (f == 1) {
			return n % mod;
		}
		else if (f % 2 == 0) {
			return (fel(n,f / 2) * fel(n,f / 2)) % mod;
		}
		else {
			return ((n  * fel(n,f / 2) %mod) * fel(n,f / 2))% mod;
		}
	

}


int main()
{
	long a, b;
	cin >> a;
	cin >> b;
	for (int i = max(-100000, b - a + 1); i <= min(1000000, b + a - 1); i++) {
		if (i == min(100000, b + a - 1)) {
			cout << i;
		}
		else {
			cout << i << " ";
		}
	}

 

}



Measured memory_bytes: 256
n, k = map(int, input().split())

res = 0
if k == 0:
    print(n*n)
    exit()

for i in range(k+1, n+1):
    cnt = (i-1)-k+1
    add = n // i * cnt
    if n % i >= k:
        add += (n % i) - k + 1
    res += add

print(res)


Measured memory_bytes: 2940
#include <iostream>
using namespace std;
int main()
{
	int a,b,c,x,ans=0;
	cin>>a>>b>>c>>x;
	for(int i=0;i<=a&&i*500<=x;i++)
		for(int j=0;j<=b&&i*500+j*100<=x;j++)
			for(int k=0;k<=c&&i*500+j*100+k*50<=x;k++)
				if(i*500+j*100+k*50==x) ans++;
	cout<<ans<<endl;
    return 0;
}

Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0; i<(int)(n); i++)
#define RNG(i,from,to) for(int i=(from); i<(int)(to); i++)
#define gcd(i,j) __gcd((i), (j))
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<ll> vecll;
template<typename S, typename T> string to_string(pair<S, T> p) { return "("+to_string(p.first)+","+to_string(p.second)+")"; }
template<typename T> string to_string(T p[2]) { return "["+to_string(p[0])+","+to_string(p[1])+"]"; }
template<typename T> void println(T e){ cout << to_string(e) << endl; }
template<typename T> void println(const vector<T>& v){ cout << "[";for(const auto& e : v){ cout << to_string(e) << ","; }cout << "]";cout << endl; }
template<typename T> void println(const vector<vector<T>>& vv){ for(const auto& v : vv){ println(v); } }
template<typename Iter> void println(Iter first, Iter last){ for(auto it=first; it != last; it++){ cout << *it << " "; }; cout << endl; }
template<typename T> T mod_pow(T x, T n, const T &p) { T ret = 1; while(n > 0) { if(n & 1) (ret *= x) %= p; (x *= x) %= p; n >>= 1; } return ret; }
template<typename T> T mod_inv(T x, const T &p) { return mod_pow(x, p-2, p); }
const ll DVSR = 1e9+7;


int main(int argc, char const *argv[])
{
  ll N; cin >> N;
  unordered_set<string> st;
  string S;
  REP(i, N) {
    cin >> S;
    st.insert(S);
  }
  cout << st.size() << endl;
  return 0;
}


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

int n;
int a[101];
long long dp[101][21];
// dp[ ??????????????°?????§?¨????????????? ][ ??? ]

long long search(int i, int sum)
{
	if (sum < 0 || sum > 20) return (0);
	
	long long &res = dp[i][sum];
	
	if (res != -1) return (res);
	
	if (i == n){
		if (sum == a[i]) return (res = 1);
		else return (res = 0);
	}
	
	long long add = search(i + 1, sum + a[i]);
	long long sub = search(i + 1, sum - a[i]);
	
	return (res = add + sub);
}

int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++){
		scanf("%d", &a[i]);
	}
	
	memset(dp, -1, sizeof(dp));
	
	printf("%lld\n", search(1, a[0]));
	
	return 0;
}

Measured memory_bytes: 1212
n, a, b = gets.chomp.split(" ").map(&:to_i)
x = gets.chomp.split(" ").map(&:to_i)

d = []
for i in 0..x.size - 2
	d << x[i + 1] - x[i]
end

result = 0
d.each do |di|
	result += [a * di, b].min
end
puts result

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

typedef uint64_t u64;
typedef int64_t i64;
typedef uint32_t u32;
typedef int32_t i32;

#define MAX_NUM (1000000000 + 7)

using namespace std;

template <typename T>
static inline void ArrayInput(vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cin >> *itr;
}

template <typename T>
static inline void ArrayPut(const vector<T>& A) {
  for (auto itr = A.begin(); itr < A.end(); ++itr) cout << *itr << " ";
  cout << endl;
}

template <typename T>
static inline T ArraySum(vector<T>& A) {
  T res = 0;
  for (auto itr = A.begin(); itr < A.end(); ++itr) res += *itr;
  return res;
}

bool Sec_compare(pair<uint64_t, uint64_t> a, pair<uint64_t, uint64_t> b) {
  if (a.second != b.second) {
    return a.second < b.second;
  } else {
    return a.first < b.first;
  }
}

u64 dec_dig(u64 num) {
  u64 res = 0;
  while (num > 0) {
    num /= 10;
    ++res;
  }
  return res;
}

i64 modinv(i64 a, i64 m) {
  i64 b = m, u = 1, v = 0;
  while (b) {
    i64 t = a / b;
    a -= t * b;
    swap(a, b);
    u -= t * v;
    swap(u, v);
  }
  u %= m;
  if (u < 0) u += m;
  return u;
}

u64 gcd(u64 a, u64 b) {
  if (a < b) {
    a ^= b;
    b ^= a;
    a ^= b;
  }

  return b ? gcd(b, a % b) : a;
}

u64 My_Comb(u64 n, u64 k, i64 m) {
  if (n < k) return 0;
  if (k == 0 || n == k) return 1;
  u64 res = 1;
  k = (n / 2 < k) ? n - k : k;
  for (u64 i = 1; i <= k; ++i)
    res = (((res * (n + 1 - i)) % m) * modinv(i, m)) % m;
  return res;
}

u64 My_Pow(u64 a, u64 n, i64 m) {
  u64 tmp = n, calc = 1;
  while (tmp > 0) {
    if (tmp % 2) {
      tmp--;
      calc *= a;
      calc %= m;
    } else {
      a *= a;
      a %= m;
      tmp /= 2;
    }
  }
  return calc;
}

int main() {
  cout << setprecision(18);
  i32 N, X, Y;
  cin >> N >> X >> Y;
  X--, Y--;
  vector<u32> res(N - 1, 0);
  for (i32 i = 0; i < N; ++i) {
    for (i32 j = i + 1; j < N; ++j) {
      i32 dist = min(abs(j - i), abs(X - i) + 1 + abs(j - Y));
      dist = min(dist, abs(j - X) + 1 + abs(Y - i));
      res[dist - 1]++;
    }
  }
  for (auto itr = res.begin(); itr != res.end(); ++itr) {
    cout << *itr << endl;
  }
  return 0;
}


Measured memory_bytes: 256
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
  public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] str = in.readLine().split(" ");
    int n = Integer.parseInt(str[0]);
    int t = Integer.parseInt(str[1]);
    int[] c = new int[n];
    int[] t_s = new int[n];
    int min = 10000;
    boolean flg = false;
    for(int i=0; i<n; i++) {
      str = in.readLine().split(" ");
      c[i] = Integer.parseInt(str[0]);
      t_s[i] = Integer.parseInt(str[1]);
    }
    for(int i=0; i<n; i++) {
      if(t_s[i]<=t){
        min = Math.min(min,c[i]);
        flg = true;
      }
    }
    System.out.println(flg==true?min:"TLE");
  }
}

Measured memory_bytes: 22484
import queue
N,M=map(int,input().split())
G=[[1 for i in range(N)] for i in range(N)]
H=[[] for i in range(N)]
for i in range(N):
    G[i][i]-=1
for i in range(M):
    a,b=map(int,input().split())
    G[a-1][b-1]-=1
    G[b-1][a-1]-=1
for i in range(N):
    for j in range(N):
        if G[i][j]==1:
            H[i].append(j)
A=[[[],[]]]
k=0
q=queue.Queue()
reached=[0 for i in range(N)]
dist=[-1 for i in range(N)]
for i in range(N):
    if reached[i]==1:
        continue
    q.put(i)
    reached[i]=1
    dist[i]=0
    while(not(q.empty())):
        r=q.get()
        A[k][dist[r]].append(r)
        for p in H[r]:
            if reached[p]==0:
                q.put(p)
                dist[p]=(dist[r]+1)%2
                reached[p]=1
    k+=1
    A.append([[],[]])
for i in range(k):
    for j in range(2):
        for x in A[i][j]:
            for y in A[i][j]:
                if x==y:
                    continue
                if G[x][y]==1:
                    print(-1)
                    exit()
B=[]
for i in range(k):
    B.append((len(A[i][0]),len(A[i][1])))
dp=[[0 for i in range(N+1)] for i in range(k+1)]
dp[0][0]=1
for i in range(1,k+1):
    for j in range(N+1):
        if dp[i-1][j]==0:
            continue
        dp[i][j+B[i-1][0]]=1
        dp[i][j+B[i-1][1]]=1
delta=N
for i in range(N+1):
    if dp[k][i]==1:
        tmp=abs(N-2*i)
        if tmp<delta:
            delta=tmp
X=(N+delta)//2
Y=(N-delta)//2
print((X*(X-1)+Y*(Y-1))//2)


Measured memory_bytes: 57560
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
typedef pair<int, int> P;
ll Mod = 1000000007;
int main() {
  int N;
  cin >> N;
  ll A[N];
  ll odd = 0;
  for (int i = 0; i < N; i++) {
    cin >> A[i];
    if (A[i] % 2 == 1) {
      odd++;
    }
  }
  if (odd % 2 == 0) {
    cout << "YES" << endl;
  } else {
    cout << "NO" << endl;
  }
  return 0;
}

Measured memory_bytes: 1024
#include<cstdio>
#include<cmath>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
    int A,B;
    int m;
    int a[100005];
    int b[100005];
    while(cin>>A>>B>>m)
    {
    	memset(a,0,sizeof(a));
    	memset(b,0,sizeof(b));
    	int min1=100000000,min2=100000000;
    for(int i=1;i<=A;i++)
	{
		cin>>a[i];
		if(min1>a[i])
		{
			min1=a[i];
		}
	}	
	for(int i=1;i<=B;i++)
	{
		cin>>b[i];
		if(min2>b[i])
		{
			min2=b[i]; 
		}
	}
	int sum=min2+min1;
	for(int i=0;i<m;i++)
	{
		int x,y,c;
		cin>>x>>y>>c;
		if(a[x]+b[y]-c<sum)
		{
			sum=a[x]+b[y]-c;
		}
		}
		cout<<sum<<endl;	
	}

    
    return 0;
}

Measured memory_bytes: 1024
n = int(input())
 
mlst = [int(i) for i in input().split()]
 
min = 1000000
ans = 0
 
for i in range(1, n):
  if abs(sum(mlst[0:i]) - sum(mlst[i:n])) < min:
    min = abs(sum(mlst[0:i]) - sum(mlst[i:n]))
    #ans = i
    
print(min)

Measured memory_bytes: 3060
#![doc = " # Bundled libraries"]
#![doc = ""]
#![doc = " ## `kyopro_lib` (private)"]
#![doc = ""]
#![doc = " ### Modules"]
#![doc = ""]
#![doc = " - `::__kyopro_lib::unionfind` → `$crate::unionfind`"]
#[allow(unused_imports)]
use itertools::Itertools;
use proconio::input;
#[allow(unused_imports)]
use proconio::marker::*;
fn main() {
    input! { n : usize , q : usize , tuv : [(i32 , usize , usize) ; q] , }
    let mut uf = unionfind::UnionFind::new(n);
    for (t, u, v) in tuv {
        if t == 0 {
            uf.unite(u, v);
        } else {
            println!("{}", if uf.is_same(u, v) { 1 } else { 0 });
        }
    }
}
pub mod unionfind {
    #[derive(Clone)]
    enum Node {
        Root(usize),
        Leaf(usize),
    }
    pub struct UnionFind {
        node: Vec<Node>,
    }
    impl UnionFind {
        pub fn new(n: usize) -> Self {
            Self {
                node: vec![Node::Root(1); n],
            }
        }
        pub fn root(&mut self, i: usize) -> usize {
            if let Node::Leaf(p) = self.node[i] {
                let r = self.root(p);
                self.node[i] = Node::Leaf(r);
                r
            } else {
                i
            }
        }
        pub fn unite(&mut self, u: usize, v: usize) -> bool {
            let mut u = self.root(u);
            let mut v = self.root(v);
            if u == v {
                return false;
            }
            if let (Node::Root(us), Node::Root(vs)) = (&self.node[u], &self.node[v]) {
                if us < vs {
                    std::mem::swap(&mut u, &mut v);
                }
                self.node[u] = Node::Root(us + vs);
                self.node[v] = Node::Leaf(u);
            }
            true
        }
        pub fn size(&mut self, i: usize) -> usize {
            let r = self.root(i);
            if let Node::Root(s) = self.node[r] {
                s
            } else {
                0
            }
        }
        pub fn is_same(&mut self, i: usize, j: usize) -> bool {
            self.root(i) == self.root(j)
        }
    }
}


Measured memory_bytes: 10804