akhauriyash/Code-Regression huggingface dataset:
#include <bits/stdc++.h>


using namespace std;

using ll = long long;

#define mp make_pair

const int p = 1000000007;


int mul(int a, int b) {
    return (1LL * a * b) % p;
}

int add(int a, int b) {
    int s = (a+b);
    if (s>=p) s-=p;
    return s;
}

int sub(int a, int b) {
    int s = (a+p-b);
    if (s>=p) s-=p;
    return s;
}

int po(int a, int deg)
{
    if (deg==0) return 1;
    if (deg%2==1) return mul(a, po(a, deg-1));
    int t = po(a, deg/2);
    return mul(t, t);
}

int inv(int n)
{
    return po(n, p-2);
}

/*struct DSU {
    vector<int> sz;
    vector<int> parent;

    void make_set(int v) {
        parent[v] = v;
        sz[v] = 1;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (sz[a] < sz[b])
                swap(a, b);
            parent[b] = a;
            sz[a] += sz[b];
        }
    }

    DSU(int n) {
        sz.resize(n);
        parent.resize(n);
        for (int i = 0; i < n; i++) make_set(i);
    }
};*/

/*const int N = 1000000;

vector<int> facs(N), invfacs(N);

void init()
{
    facs[0] = 1;
    for (int i = 1; i<N; i++) facs[i] = mul(facs[i-1], i);
    invfacs[N-1] = inv(facs[N-1]);
    for (int i = N-2; i>=0; i--) invfacs[i] = mul(invfacs[i+1], i+1);
}

int C(int n, int k)
{
    return mul(facs[n], mul(invfacs[k], invfacs[n-k]));
}*/


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

    int n, d;
    cin>>n>>d;
    vector<int> a(n);
    for (int i = 0; i<n; i++) cin>>a[i];

    vector<int> pos(n+1);
    pos[0] = d;
    for (int i = 1; i<=n; i++)
    {
        pos[i] = min(pos[i-1], abs(pos[i-1] - a[i-1]));
    }

    /*for (int i = 0; i<=n; i++) cout<<pos[i]<<' ';
    cout<<endl;*/

    int cur = 1;
    vector<bool> answer(n+1);

    for (int i = n; i>0; i--)
    {
        if (pos[i-1]>=cur) answer[i] = true;
        if (a[i-1]<2*cur) cur+=a[i-1];
        if (cur>d) break;
        //cout<<cur<<endl;
    }

    int q;
    cin>>q;
    for (int i = 0; i<q; i++)
    {
        int t;
        cin>>t;
        if (answer[t]) cout<<"YES"<<endl; else cout<<"NO"<<endl;
    }


}

Measured memory_bytes: 5888
#include <bits/stdc++.h>
using namespace std;
int main()
{
	int n,k,sum=0;
	cin>>n>>k;
	int a[n];
	for (int i=0;i<n;i++)
	{
		cin>>a[i];
		if (a[i]>=k)
			sum++;
	}
	cout<<sum;
	return 0;
}

Measured memory_bytes: 640
#include<bits/stdc++.h>
#define rep(i, n) for (ll i = 0; i < (ll)(n); ++i)
#define repk(i,k,n) for (ll i = k; i < (ll)(n); ++i)
#define MOD 1000000007
typedef long long  ll;

using namespace std;

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

	int N,K;
	cin >> N >> K;

	double ans=0;
	repk(i,1,N+1){
		int cnt = 0;
		int temp = i;
		while(temp < K){
			cnt++;
			temp *= 2;
		}
		// cout << cnt << endl;
		ans += pow(0.5 ,cnt);
	}

	ans /= N;

	cout << fixed << setprecision(15);
	cout << ans << endl;
	return 0;
}

Measured memory_bytes: 4116
#include "bits/stdc++.h"
using namespace std;
#define ll long long int
#define rep(i,n) for( int i = 0; i < n; i++ )
#define rrep(i,n) for( int i = n; i >= 0; i-- )
#define REP(i,s,t) for( int i = s; i <= t; i++ )
#define RREP(i,s,t) for( int i = s; i >= t; i-- )
#define dump(x)  cerr << #x << " = " << (x) << endl;
#define INF 2000000000
#define mod 1000000007
#define INF2 1000000000000000000


int main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N; cin >> N;
    cout << (N) * (N + 1) / 2 << endl;

    return 0;
}


Measured memory_bytes: 256
/*
  AOJ 0242
  Title:Input Candidates
  @kankichi573
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(x,y) (((x)<(y))?(x):(y))

int n,w_cnt,w_cnt2;
char c;
char line[1025];

struct word_st
{
  char spell[21];
  int  count;
}
  word_inf[10000],word_inf2[10000];

int compare_word(const void *a, const void *b)
{
  int ret;

  if(ret= ((struct word_st *)b)->count - ((struct word_st *)a)->count)
    return(ret);
  return(strcmp(((struct word_st *)a)->spell, ((struct word_st *)b)->spell));
}
void register_word(char word[])
{
  int i;
  for(i=0;i<w_cnt;i++)
    if(0==strcmp(word,word_inf[i].spell))
      {
	word_inf[i].count++;
	return;
      }
  strcpy(word_inf[w_cnt].spell,word);
  word_inf[w_cnt].count=1;
  w_cnt++;
}
dump()
{
  int i;
  for(i=0;i<w_cnt;i++)
    printf("%d:%s[%d]\n",i,word_inf2[i].spell,word_inf2[i].count);
}
main()
{
  int i,ret,cn;
  char *p;
  while(scanf("%d ",&n)  && n)
    {
      memset(word_inf ,0,sizeof(word_inf));
      memset(word_inf2,0,sizeof(word_inf2));

       for(i=0;i<n;i++)
	 {
	   fgets(line,1025,stdin);

	   p=strtok(line," \n");
	   do
	     {
	     register_word(p);
	     }
	   while(p=strtok(NULL," \n"));
	 }
      scanf("%c",&c);
      for(i=w_cnt2=0;i<w_cnt;i++)
	if(word_inf[i].spell[0]==c)
	  {
	    word_inf2[w_cnt2]=word_inf[i];
	    w_cnt2++;
	  }

      //dump();
      qsort(word_inf2,w_cnt,sizeof(struct word_st),compare_word);
      cn=min(5,w_cnt2);
      if(cn>0)
	for(i=0;i<cn;i++)
	  {
	    printf("%s",word_inf2[i].spell);
	    if(i<cn-1)
	      printf(" ");
	    else
	      printf("\n");
	  }
      else
	printf("NA\n");
    }
  return(0);
}

Measured memory_bytes: 1292
# Segment tree (Bitwise Or)
from operator import or_


class SegmentTree:
    _f = None
    _data = None
    _offset = None
    _size = None

    def __init__(self, size, f):
        self._f = f
        self._size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0] * (t * 2 - 1)

    def build(self, iterable):
        f = self._f
        data = self._data
        data[self._offset:self._offset + self._size] = iterable
        for i in range(self._offset - 1, -1, -1):
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def update(self, index, value):
        f = self._f
        data = self._data
        i = self._offset + index
        data[i] = value
        while i >= 1:
            i = (i - 1) // 2
            data[i] = f(data[i * 2 + 1], data[i * 2 + 2])

    def query(self, start, stop):
        def iter_segments(data, l, r):
            while l < r:
                if l & 1 == 0:
                    yield data[l]
                if r & 1 == 0:
                    yield data[r - 1]
                l = l // 2
                r = (r - 1) // 2
        f = self._f
        it = iter_segments(self._data, start + self._offset,
                           stop + self._offset)
        result = next(it)
        for e in it:
            result = f(result, e)
        return result


def conv(c):
    return 1 << (ord(c) - ord('a'))


N = int(input())
S = input()

st = SegmentTree(N, or_)
st.build(conv(c) for c in S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, conv(c))
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))


Measured memory_bytes: 49688
#include <bits/stdc++.h>
using namespace std;
#define db(x) cerr << #x << "=" << x << endl
#define db2(x, y) cerr << #x << "=" << x << "," << #y << "=" << y << endl
#define db3(x, y, z) cerr << #x << "=" << x << "," << #y << "=" << y << "," << #z << "=" << z << endl
typedef long long ll;
typedef long double ld;
vector<int> indices, appear;
bool used[100005];
int P[100005];
vector<int> E[100005];
void go(int x) {
	if (used[x]) return;
	used[x] = true;
	indices.push_back(x);
	appear.push_back(P[x]);
	for (int y : E[x]) go(y);
}
int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; ++i) scanf("%d", &P[i]);
	for (int i = 0; i < M; ++i) {
		int x, y;
		scanf("%d%d", &x, &y);
		E[x].push_back(y);
		E[y].push_back(x);
	}
	int ans = 0;
	for (int i = 1; i <= N; ++i) {
		if (used[i]) continue;
		indices.clear();
		appear.clear();
		go(i);
		sort(indices.begin(), indices.end());
		for (int a : appear)
			if (binary_search(indices.begin(), indices.end(), a))
				++ans;
	}
	printf("%d\n", ans);
}


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

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;

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

Measured memory_bytes: 256
//#i#include "pch.h"
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <bitset>
#include <limits.h>
#include <string>
#include <stack>
#include <deque>
#include <cmath>
#include <bitset>
#include <complex>
#include <functional>
#include <time.h>
#include <stdio.h>

typedef long long ll;
typedef std::pair<int, int> Pii;
typedef std::pair<long long, long long> Pll;
typedef std::pair<double, double> Pdd;

#define rip(i, n, s) for (int i = (s);i < (int)( n ); i++)
#define mapa make_pair
#define all(a) a.begin(), a.end()
#define MM << " " <<

template<typename T>
using MaxHeap = std::priority_queue<T>;
template<typename T>
using MinHeap = std::priority_queue<T, std::vector<T>, std::greater<T>>;

template<typename T>
inline bool chmax(T &a, T b) {
	if (a < b) {
		a = b;
		return true;
	}
	return false;
}
template<typename T>
inline bool chmin(T &a, T b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

template<typename T>
std::vector<T> vec(int len, T elem) { return std::vector<T>(len, elem); }
template<typename T>
void vdeb(std::vector<T> &da) {
	for (int i = 0;i < da.size();i++) {
		if (i == da.size() - 1) std::cout << da[i];
		else std::cout << da[i] << ' ';
	}
	std::cout << std::endl;
}
template<typename T>
void vdeb(std::vector<std::vector<T>> &da) {
	for (int i = 0;i < da.size();i++) vdeb(da[i]);
	std::cout << std::endl;
}

using namespace std;

struct edge{
	int a,b,c;
	edge(){}
	edge(int _a, int _b, int _c){
		a = _a, b = _b, c = _c;
	}
};

ostream& operator<<(ostream &os, const edge &x){
	cout << x.a MM x.b MM x.c << endl;
	return os;
}

int main(){
	int l;cin >> l;
	vector<int> da(0);
	while(l){
		da.push_back(l%3);
		l /= 3;
	}
	reverse(all(da));
	int n = da.size()+1;
	vector<int> li(20);
	li[0] = 1;
	rip(i,20,1){
		li[i] = li[i-1]*3;
	}
	vector<edge> ans(0);
	rip(i,n,2){
		rip(j,3,0){
			ans.push_back(edge(i, i+1, li[n-i-1]*j));
		}
	}
	int now = 0;
	rip(i,n,1){
		rip(j,da[i-1],0){
			ans.push_back(edge(1,i+1,now));
			now += li[n-i-1];
		}
	}
	int m = ans.size();
	cout << n MM m << endl;
	rip(i,m,0){
		cout << ans[i];
	}
}

Measured memory_bytes: 256
using System;
using System.Diagnostics.CodeAnalysis;
using System.Text;

namespace ChokudaiScanner
{
    class MainClass
    {
        static void Main()
        {
            Scanner cin = new Scanner();

            string S = cin.Next();
            string[] d =
            {
                "maerd","esare","resare","remaerd"
            };
            char[] s = new char[S.Length];
            for(int i = 0; i < S.Length; i++)
            {
                s[i]= S[i];
            }
            Array.Reverse(s);
            S = new string(s);
            bool x = true;

            for(int i = 0;x;)
            {
                x = false;

                for(int j = 0; j < 4; j++)
                {
                    if(i+d[j].Length > S.Length)
                    {
                        break;
                    }

                    if (S.Substring(i,d[j].Length) == d[j])
                    {
                        i += d[j].Length;
                        x = true;
                    }

                    if (i == S.Length)
                    {
                        Console.WriteLine("YES");
                        return;
                    }
                }
            }
            Console.WriteLine("NO");
        }
    }

    class Scanner
    {
        string[] s;
        int i;

        char[] cs = new char[] { ' ' };

        public Scanner()
        {
            s = new string[0];
            i = 0;
        }

        public string Next()
        {
            if (i < s.Length) return s[i++];
            string st = Console.ReadLine();
            while (st == "") st = Console.ReadLine();
            s = st.Split(cs, StringSplitOptions.RemoveEmptyEntries);
            if (s.Length == 0) return Next();
            i = 0;
            return s[i++];
        }

        public string[] ArrayNext(int N)
        {
            string[] Array = new string[N];
            for (int i = 0; i < N; i++)
            {
                Array[i] = Next();
            }
            return Array;
        }

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

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

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

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


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



Measured memory_bytes: 13220
N,M=map(int,input().split())
A=list(map(int,input().split()))
weight=[0,2,5,5,4,5,6,3,7,6]
dp=[-1]*(N+1)
dp[0]=0
for i in range(N+1):
    for a in A:
        if i+weight[a]<N+1:
            dp[i+weight[a]]=max(dp[i+weight[a]],dp[i]*10+a)
print(dp[N])

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

char conv(int o)
{
	if(o==0) return '+';
	if(o==1) return '-';
	if(o==2) return '*';
}


int calc(int m,int n,int o)
{
	if(o==0) return m+n;
	if(o==1) return m-n;
	if(o==2) return m*n;
}


int main()
{
	int nums[4];
	while(cin>>nums[0]>>nums[1]>>nums[2]>>nums[3],nums[0])
	{
		sort(nums,nums+4);
		bool flag=false;
		do {
			int o1=0,o2=0,o3=-1;
			for(int i = 0; i < 27; ++i)
			{
				o3++;
				if (o3==3)
				{
					o3=0;
					o2++;
					if (o2==3)
					{
						o1++;
						o2=0;
					}
				}
				
				if( calc(calc(nums[0],nums[1],o1),calc(nums[2],nums[3],o3),o2)==10 )
				{
					printf("(%d%c%d)%c(%d%c%d)\n",nums[0],conv(o1),nums[1],conv(o2),nums[2],conv(o3),nums[3]);
					flag=true; break;
				}
				if( calc(calc(calc(nums[0],nums[1],o1),nums[2],o2),nums[3],o3)==10 )
				{
					printf("((%d%c%d)%c%d)%c%d\n",nums[0],conv(o1),nums[1],conv(o2),nums[2],conv(o3),nums[3]);
					flag=true; break;
				}
				if( calc(nums[0],calc(calc(nums[1],nums[2],o2),nums[3],o3),o1)==10 )
				{
					printf("%d%c((%d%c%d)%c%d)\n",nums[0],conv(o1),nums[1],conv(o2),nums[2],conv(o3),nums[3]);
					flag=true; break;
				}
				if( calc(calc(nums[0],calc(nums[1],nums[2],o2),o1),nums[3],o3)==10 )
				{
					printf("(%d%c(%d%c%d))%c%d\n",nums[0],conv(o1),nums[1],conv(o2),nums[2],conv(o3),nums[3]);
					flag=true; break;
				}
				if( calc(nums[0],calc(nums[1],calc(nums[2],nums[3],o3),o2),o1)==10 )
				{
					printf("%d%c(%d%c(%d%c%d))\n",nums[0],conv(o1),nums[1],conv(o2),nums[2],conv(o3),nums[3]);
					flag=true; break;
				}
			}
			
		} while (!flag&&next_permutation(nums,nums+4));
		if(!flag) cout<<0<<endl;
	}
  return 0;
}

Measured memory_bytes: 1212
#include <bits/stdc++.h>
#include<chrono>
using namespace std;
using ll = long long;

int main() {
  ll A, B, M;
  cin >> A >> B >> M;
  vector<ll> a(A);
  vector<ll> b(B);
  for (int i = 0; i < A; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < B; i++) {
    cin >> b[i];
  }
  
  vector<ll> ans(M);
  for (int i = 0; i < M; i++) {
    ll x, y, c;
    cin >> x >> y >> c;
    ll sum = a[x-1] + b[y-1] - c;
    ans[i] = sum;
  }
  sort(a.begin(), a.end());
  sort(b.begin(), b.end());
  ans.push_back(a[0] + b[0]);
  
  sort(ans.begin(), ans.end());
  
  cout << ans[0] << endl;
}


Measured memory_bytes: 3328
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
typedef long long int ll;
using namespace std;

int digit(int n){
	int cnt=0;
	while(n>0){
		cnt++;
		n/=10;
	}
	return cnt;
}
int main(){
	int a,b;
	while(scanf("%d%d",&a,&b)!=EOF){
		cout << digit(a+b) << endl;
	}
	return 0;
}


Measured memory_bytes: 3136
#include <bits/stdc++.h> 
using namespace std; 
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#define flash ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(x) cerr << " - " << #x << ": " << x << endl;
#define debugs(x, y) cerr << " - " << #x << ": " << x << " " << #y << ": " << y << endl;
#define all(x) (x).begin(),(x).end()
#define sz(x) (ll)x.size()
#define ll long long
#define INF 1000000000
#define MOD 1000000007
#define pb push_back
#define ve vector<ll>
#define dos pair<ll,ll>
#define vedos vector<dos>
#define rand mt19937 rng(chrono::steady_clock::now().time_since_epoch().count())
#define EPS 0.000001
struct greateri
{
    template<class T>
    bool operator()(T const &a, T const &b) const { return a > b; }
};
void setIO(string s) {
    ios_base::sync_with_stdio(0); cin.tie(0); 
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}
int main()
{
  //flash;
    int l,r,d;
    cin>>l>>r>>d;
    int ans=0;
    for (int i = l; i <= r; ++i)
    {
       if(!(i%d))ans++;
    }
    cout<<ans;
  return 0;
}
//code the AC sol !
// BS/queue/map

Measured memory_bytes: 3628
# Problem C - Skip

from fractions import gcd

# input
N, X = map(int, input().split())
x_list = list(map(int, input().split()))
x_list.append(X)
x_list = sorted(x_list)

# initialization
min_d = float('INF')
d_list = [0] * N
for i in range(N):
    d_list[i] = x_list[i+1] - x_list[i]
if len(d_list)==1:
    min_d = d_list[0]
else:
    for i in range(N-1):
        d_1 = d_list[i]
        d_2 = d_list[i+1]
        gcd_d = gcd(d_1, d_2)
        min_d = min(min_d, gcd_d)

# output
print(min_d)


Measured memory_bytes: 88172
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
#include<functional>
using namespace std;
typedef	long long int ll;

int main(){
    int n;
    cin >> n;
    char s[n][n], s_[n][n];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> s[i][j];
        }
    }
    ll sum = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(k+i >= n){
                    s_[j][k] = s[j][k+i-n];
                }
                else s_[j][k] = s[j][k+i];
            }
        }
        bool sy = 1;
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(s_[j][k] != s_[k][j]) sy = 0;
            }
        }
        if(sy == 1) sum += n-i;
    }
    for(int i = 1; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(j+i >= n){
                    s_[j][k] = s[j+i-n][k];
                }
                else s_[j][k] = s[j+i][k];
            }
        }
        bool sy = 1;
        for(int j = 0; j < n; j++){
            for(int k = 0; k < n; k++){
                if(s_[j][k] != s_[k][j]) sy = 0;
            }
        }
        if(sy == 1) sum += n-i;
    }
    cout << sum << endl;
    return 0;
}

Measured memory_bytes: 384
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define int long long

int n, dp[22][1 << 21];
int a[30][30];
const int mod = 1e9 + 7;

void add(int &a, int b){
	a = (a + b) % mod;
}

signed main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			cin >> a[i][j];
		}
	}
	dp[0][(1 << n) - 1] = 1;
	for(int i = 1; i <= n; i++){
		for(int mask = (1 << n) - 1; mask >= 0; mask--){
			if(dp[i - 1][mask] == 0) continue;
			for(int j = 0; j < n; j++){
				if(!(mask & (1 << j))) continue;
				if(a[i][j + 1] == 0) continue;
				int nt = mask - (1 << j);
				add(dp[i][nt], dp[i - 1][mask]);
			}
		}
	}
	cout << dp[n][0];
}


Measured memory_bytes: 309504
#include<iostream>
using namespace std;
#define MAX 100005
#define NIL -1

struct Node {int p, l, r; };

Node T[MAX];
int n, D[MAX];

void print(int u) {
    int i, c;
    cout << "node " << u << ": ";
    cout << "parent = " << T[u].p << ", ";
    cout << "depth = " << D[u] << ", ";
    
    if(T[u].p == NIL) cout << "root, ";
    else if(T[u].l == NIL) cout << "leaf, ";
    else cout << "internal node, ";
    
    cout << "[";
    
    for(i = 0, c = T[u].l; c != NIL; i++, c = T[c].r) {
        if(i) cout << ", ";
        cout << c;
    }
    cout << "]" << endl;
}


int rec(int u, int p) {
    D[u] = p;
    if(T[u].r != NIL) rec(T[u].r, p);
    if(T[u].l != NIL) rec(T[u].l, p + 1); 
}

int main() {
    int i, j, d, v, c, l, r;
    cin >> n;
    for(i = 0; i < n; i++) T[i].p = T[i].l = T[i].r = NIL;
    
    for(i = 0; i < n; i++) {
        cin >> v >> d;
        for(j = 0; j < d; j++) {
            cin >> c;
            if(j == 0) T[v].l = c;
            else T[l].r = c;
            l = c;
            T[c].p = v;
        }
    }
    
    for(i = 0; i < n; i++) {
        if(T[i].p == NIL) r = i;
    }
    
    rec(r, 0);
    
    for(i = 0; i < n; i++) {
        print(i);
    }
    
    return 0;
}


Measured memory_bytes: 7768
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int,int> P;
 
const int INF = 1e9;
const int mod = 1e9+7;
const double EPS = 1e-10;
const double PI = acos(-1.0);

int main(){
    int n;
    cin >> n;
    cout << (n == 3 || n == 5 || n == 7 ? "YES" : "NO") << endl; 
    return 0;
}

Measured memory_bytes: 256
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef map<int,int> mii;
typedef vector<int>vi;
#define pb push_back
#define sc(n) scanf("%d",&n)
#define lsc(n) scanf("%lld",&n)
#define all(x) x.begin(),x.end()
#define rep(i,n) for(i=0;i<n;i++)
#define rep1(i,n) for(i=1;i<=n;i++)
#define rev(i,n) for(i=n-1;i>=0;i--)
#define rev1(i,n) for(i=n;i>0;i--)
#define in insert
#define pr(n) printf("%d\n",n)
#define lpr(n) printf("%lld\n",n);


int main()
{
	int n,i;
	sc(n);
	int p[n];
	rep(i,n)
	{
		sc(p[i]);
	}
	int z=0;
	rep(i,n-1)
	{
		if(p[i]==i+1)
		{
			swap(p[i],p[i+1]);
			z++;
		}
	}
	if(p[n-1]==n)z++;
	cout << z << endl;
	return 0;
}


Measured memory_bytes: 640
import copy
 
N,M,X = map(int,input().split())
 
res = 10**8
 
C = [0] * N
A = [0] * N
 
for i in range(N):
    L = list(map(int,input().split()))
    C[i] = L[0]
    A[i] = L[1:]
 
def check_x(a):
    for i in range(len(a)):
        if a[i] < X:
            return False
    return True
 
# n…2^12(12bit)の整数
def calc_money_under(n):
    global res

    understand = [0] * M
    money = 0
    for s in range(N):
        if (n >> s) & 1:
            money += C[s]
            for j in range(M):
                understand[j] += A[s][j]
            #print(understand)
    
    if check_x(understand):
        res = min(money, res)
    return
 
for n in range(2**N):
    calc_money_under(n)
 
if res == 10**8:
    print(-1)
else:
    print(res)

Measured memory_bytes: 9332
#include<bits/stdc++.h>
using namespace std;
int main(){
  string S,K,L;
  cin >> S;
  int A,B;
  K=S.substr(0,4);
  L=S.substr(5,2);
  A=stoi(K);
  B=stoi(L);
  if(A>2019)cout << "TBD" << endl;
  else if(A<2019)cout << "Heisei" << endl;
  else if(B>4)cout << "TBD" << endl;
  else if(B<5)cout << "Heisei" << endl;
}


Measured memory_bytes: 256
#include <stdio.h>

int main(void)
{
	int i, j;
	int hills[10];
	int temp;

	for (i = 0; i < 10; i++){
		scanf("%d", &hills[i]);
	}

	for (i = 0; i < 9; i++){
		for (j = 0; j < 9 - i; j++){
			if (hills[j] > hills[j + 1]){
				temp = hills[j];
				hills[j] = hills[j + 1];
				hills[j + 1] = temp;
			}
		}
	}

	printf("%d\n", hills[9]);
	printf("%d\n", hills[8]);
	printf("%d\n", hills[7]);

	return (0);
}

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

signed main(){
    int N;cin>>N;
    vector<int> v(N);
    for(int i=0;i<N;i++)cin>>v[i];
    int ans=0;
    vector<int> is_prime(20000,1);
    is_prime[0]=is_prime[1]=0;
    set<int> p;
    for(int i=2;i<20000;i++){
        if(is_prime[i]==0)continue;
        p.insert(i);
        for(int j=i*i;j<20000;j+=i)is_prime[j]=0;
    }
    for(int i=0;i<N;i++){
        if(p.count(v[i])){ans++;continue;}
        int a=0;
        for(auto q:p){
            if(v[i]%q==0)a++;
            if(a)break;
        }
        if(a==0)ans++;
    }
    cout<<ans<<endl;
}


Measured memory_bytes: 3208
#include <iostream>
#include <string>
using namespace std;
int main(){
  string s;
  cin >>s;
  int w;
  cin >> w;
  int cnt=0;
  string t="";
  int a=s.size();
  while(1){
    if(cnt>=a) break;
    if(cnt%w==0) t+=s[cnt];
    cnt++;
  }
  cout << t <<endl;
}


Measured memory_bytes: 256
#include<stdio.h>
#include<string.h>
int main(void){
        int a=0,b=0,i,n;
        char s[10];
        scanf("%s",&s);
        n=strlen(s);
        for(i=0;i<n;i++){
                switch(s[i]){
                        case 'A':
                        case 'T':
                        case 'G':
                        case 'C':
                        a++; if(a>b) b++; break;
                        default:
                        a=0;break;}}
        printf("%d",b);
        return 0;
}

Measured memory_bytes: 128
k = int(input())
#n, m = list(map(int, input().split()))
a, b = list(map(int, input().split()))
# sy, sx = map(int, input().split())
# gy, gx = map(int, input().split())
for i in range(a, b+1):
    if i % k == 0:
        print("OK")
        exit()

print("NG")


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

int main() {
	int a, b;
	cin >> a >> b;
	if (a<b) {
		cout << "a < b" << endl;
	}
	if (a==b) {
		cout << "a == b" << endl;
	}
	if(a>b) {
		cout << "a > b" << endl;
	}
}

Measured memory_bytes: 1160
#include <iostream>
#include <string>
#include <algorithm>
#include <set>
#include <cmath>
#include <vector>
#include <numeric>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <tuple>

using ll = long long int;
using ul = unsigned long long int;
const ll LL_MAX (1LL<<60);
const ll MOD (1000000007);

#define rep(i,s,e) for(ll i=(s); i<(e); i++) 

using namespace std;

using T = tuple<ll,ll>;
using Graph = vector<vector<T>>;

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

    ll n, m;
    cin >> n >> m;

    ll even = n*(n-1) / 2;
    ll odd = m*(m-1) / 2; 
       
    cout << even + odd << endl; 

    return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define _GLIBCXX_DEBUG
#define rep2(i, m, n) for(int i=int(m); i<int(n); i++)
#define rep(i, n) rep2(i, 0, n)
#define ALL(a) a.begin(), a.end()
using ll = long long;
using ld = long double;
using V = vector<int>;
using Vll = vector<ll>;
using Vld = vector<ld>;
using VV = vector<V>;
using VVll = vector<Vll>;
using VVld = vector<Vld>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using Pld = pair<ld, ld>;
const int INF = 1<<30;
const ll INFll = 1ll<<62;
const ld EPS = 1e-10;
const int MOD = int(1e9)+7;
template<typename T> inline bool chmin(T& a, T b) {if(a>b) {a=b; return true;} return false;}
template<typename T> inline bool chmax(T& a, T b) {if(a<b) {a=b; return true;} return false;}


int main() {
  ll N, A, B; cin >> N >> A >> B;
  if ((A - B) % 2 == 0) {
    cout << ((B-A)/2) << endl;
    return 0;
  }
  

  ll ans = min(A - 1, N - B);
  ans++;
  ans += (B-A-1)/2;
  cout << ans << endl;
  return 0;
}


Measured memory_bytes: 256
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define mod 998244353
#define int long long int
#define double long double
#define inf (int)(1e15)
#define all(x) (x).begin(), (x).end()
#define pair pair<int, int>
typedef vector<int> vi;   // Vector of long long
typedef vector<vi> vvi;   // Vector of vi
typedef vector<pair> vii; // Vector of pairs
typedef vector<vii> vvii; // Vector of Vector of pairs
typedef vector<bool> vb;  // Vector of bool
#define pq priority_queue // Max heap (To convert to min heap, use negative sign before every value)
#define ff first          // For pairs
#define ss second
const int dx4[] = {1, 0, -1, 0}, dy4[] = {0, -1, 0, 1};
const int dx8[] = {0, 0, 1, 1, 1, -1, -1, -1}, dy8[] = {1, -1, 1, 0, -1, 1, -0, -1};
#define testcases(t) \
    int(t);          \
    cin >> (t);      \
    while ((t)--)
int n, s, modinv;
vi a;
int power(int a, int b)
{
    int res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % mod;
        b = b / 2;
        a = (a * a) % mod;
    }
    return res;
}
int modi(int a)
{
    return power(a, mod - 2);
}
signed main()
{
    cin >> n >> s;
    modinv = modi(2);
    a.resize(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    vvi dp(n + 1, vi(s + 1, 0));
    dp[0][0] = power(2, n);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= s; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= a[i])
            {
                dp[i][j] += ((dp[i - 1][j - a[i]] * modinv) % mod);
                dp[i][j] %= mod;
            }
        }
    }
    cout << dp[n][s] << endl;
    return 0;
}


Measured memory_bytes: 73760
// input macro from https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        let mut next = || { iter.next().unwrap() };
        input_inner!{next, $($r)*}
    };
    ($($r:tt)*) => {
        let stdin = std::io::stdin();
        let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
        let mut next = move || -> String{
            bytes
                .by_ref()
                .map(|r|r.unwrap() as char)
                .skip_while(|c|c.is_whitespace())
                .take_while(|c|!c.is_whitespace())
                .collect()
        };
        input_inner!{next, $($r)*}
    };
}

macro_rules! input_inner {
    ($next:expr) => {};
    ($next:expr, ) => {};

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

macro_rules! read_value {
    ($next:expr, ( $($t:tt),* )) => {
        ( $(read_value!($next, $t)),* )
    };

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

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

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

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

fn main() {
    input! {
        s1: String,
        _s2: String,
    }

    let mut s2 = _s2;
    s2.pop();

    if s1 == s2 {
        println!("Yes");
    } else {
        println!("No");
    }
}


Measured memory_bytes: 2100
n,k=map(int,input().split())
p=list(map(int,input().split()))
l=[(i+1)/2 for i in p]


s=sum(l[0:k])
ans=s
for i in range(k,n):
    s+=l[i]
    s-=l[i-k]
    ans=max(ans,s)
print(ans)


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

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
#define chmax(x, v) do { x = max(x, v); } while (0)
#define chmin(x, v) do { x = min(x, v); } while (0)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

// Union Find {{{
class UnionFind {
 public:
     int n;
     std::vector<int> par;
     std::vector<int> num;

     explicit UnionFind(int n) {  // [0 n)のunion find
         this->n = n;
         this->par.resize(n);
         this->num.resize(n, 1);
         for (int i = 0; i < n; i++) {
             this->par[i] = i;
         }
     }

     int root(int i) {
         if (par[i] == i)
             return i;
         else
             return par[i] = root(par[i]);
     }

     bool same(int i, int j) {
         return root(i) == root(j);
     }

     bool unite(int i, int j) {
         int t = root(i);
         int k = root(j);

         if (t == k)
           return false;

         par[t] = k;
         num[k] += num[t];
         return true;
     }

     int size(int i) {
         return num[root(i)];
     }
};
// }}}

signed main() {
  ll N, M, K;
  cin >> N >> M >> K;
  UnionFind uf(N);
  vector<ll> ans(N);
  vector<PLL> a, b;

  rep(i, M) {
    ll x, y;
    cin >> x >> y;
    x--;
    y--;
    a.emplace_back(x, y);
    uf.unite(x, y);
  }

  rep(i, K) {
    ll x, y;
    cin >> x >> y;
    x--;
    y--;
    b.emplace_back(x, y);
  }

  rep(i, N) {
    ans[i] = uf.size(i)-1;
  }

  // 直接の友人は除く
  rep(i, M) {
    if (uf.same(a[i].first, a[i].second)) {
      ans[a[i].first]--;
      ans[a[i].second]--;
    }
  }

  // ブロックは除く
  rep(i, K) {
    if (uf.same(b[i].first, b[i].second)) {
      ans[b[i].first]--;
      ans[b[i].second]--;
    }
  }

  rep(i, N) {
    cout << ans[i] << " ";
  }
  cout << endl;
}


Measured memory_bytes: 6768
from collections import defaultdict
import sys
N = int(input())
W = [input() for _ in range(N)]

dict = defaultdict(bool)  # int/bool/list....
dict[W[0]] = True
for i in range(1, N):
    if (W[i][0] is not W[i - 1][-1]) or dict[W[i]]:
        print("No")
        sys.exit()
    dict[W[i]] = True

print("Yes")

Measured memory_bytes: 9472
#include <iostream>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstdlib>

using namespace std;
//DP用
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;
}

//a^n mod を計算する関数
long long modpow(long long a,long long n,long long mod) {
    long long res = 1;
    while(n > 0) {
        if(n & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

//a^(-1) mod すなわちaの逆元を返す関数
long long modinv(long long a,long long mod) {
    return modpow(a,mod-2,mod);
}

//最大公約数をを返す関数
long long gcd (long long a,long long b) {
    if(a % b == 0) {
        return b;
    }else {
        return (gcd(b,a%b));
    }
}

const long long INF = 1LL << 60;
const long long P = 1000000007;

long long conbi (long long n,long long k) {
    long long res = 1;
    long long inv;
    for(long long i = n-k+1; i <= n; i++) {
        res *= i;
        res %= P;
    }
    for(long long i = 1; i <= k; i++) {
        inv = modinv(i,P);
        res *= inv;
        res %= P;
    }
    return res;
}

int main() {
    long long n;
    long long a,b;
    cin >> n >> a >> b;
    long long ans;
    ans = modpow(2,n,P);
    ans = ans-1-conbi(n,a)-conbi(n,b);
    ans = ans % P;
    if(ans < 0) {
        ans += P;
    }
    cout << ans;
    return 0;
}

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

int main(){
  int N, A, B, x;
  int a=0, b=0, c=0;
  cin >> N >> A >> B;
  vector<int> P(N);
  for (int i = 0; i < N; i++){
    cin >> P.at(i);
  }
  sort(P.begin(), P.end());

  for (int i = 0; i < N; i++){
    if(P.at(i)<=A) a++;
    else if(P.at(i)<=B) b++;
    else c++;
  }

  x = min(a,b);
  
  cout << min(x,c) << endl;
}

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

using namespace std;

int main()

{
	
	int n, i, j, k;
	cin >> n;
	
	int arr[n];
	
	for (i = 0; i < n; ++i)
	{
		cin >> arr[i];
	}
	
	sort(arr, arr+n);
	
	cout << arr[n/2] - arr[n/2 - 1];
	
	
	return 0;
}

Measured memory_bytes: 640
#pragma region Macros
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using Graph = vector<vector<int>>;
using WGraph = vector<vector<pair<int, ll>>>;

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

constexpr int dx[4] = {-1, 0, 0, 1}, dy[4] = {0, -1, 1, 0};
constexpr int INF = 1e9;
constexpr long long LINF = 1e18;
constexpr long long MOD = 1e9 + 7;
constexpr double EPS = 1e-10;
constexpr double PI = M_PI;
#pragma endregion

void solve() {
    int n, h;
    cin >> h >> n;
    int sum = 0;
    for (int i=0; i<n; i++) {
        int tmp;
        cin >> tmp;
        sum += tmp;
    }
    if (sum >= h) cout << "Yes" << '\n';
    else cout << "No" << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout << fixed << setprecision(20);

    solve();

    return 0;
}


Measured memory_bytes: 384
#include "bits/stdc++.h"

// マクロ群
#define REP(i,n) for(int i=0;i<n;++i)
#define REP2(i,a,b) for (int i=(a);i<(b);++i)
#define rep(n) REP(i,n)
#define SF(f,v) scanf(f,v)
#define SF_N(v) SF("%d",&v)
#define SF_S(v) SF("%s",v)
#define PF(f,v) printf(f,v)
#define PFS_N(v) PF("%d ",v)
#define PFS_S(v) PF("%s ",v)
#define PFL_N(v) PF("%d\n",v)
#define PFL_S(v) PF("%s\n",v)


using namespace std;

const int ARRMAX = 1024;

void Slove()
{
	int N;
	SF_N(N);
	int a;

	bool ans = true;
	rep(N)
	{
		SF_N(a);
		if (a % 2 == 1) ans = !ans;
	}

	PFL_S( ans ? "YES" : "NO");
}

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

Measured memory_bytes: 256
#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()


int main(){
    int n, x;
    cin >> n >> x;
    vector<int> m(n);
    rep(i,n) cin >> m[i];

    //最低1つずつは作る
    int ans=n;
    rep(i,n){
        x -= m.at(i);
    }

    //昇順に並び替え、一番必要量が少ないものを限界まで作る
    sort(all(m));
    while(true){
        if(m.at(0) <= x){
            ans ++;
            x -= m.at(0);
        }
        else{
            cout << ans << endl;
            return 0;
        }
    }

}

Measured memory_bytes: 3528
#include<bits/stdc++.h>
#define faster  ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ll long long
#define ull unsigned long long
#define pb push_back
const double PI = acos(-1.0);
using namespace std;

int main()
{
    faster

    ll n,m=1000;
    cin>>n;

    ll a[n];

    for(ll i=0; i<n; i++)
        cin>>a[i];




    for(ll i=0; i<n; i++)
    {
        //cin>>a[i];

        if(i!=0)
        {
            if(a[i]>a[i-1])
            {

                ll x=m/a[i-1];

                m=m-(a[i-1]*x);

                while(i+1<n && a[i+1]>a[i])
                {
                    i++;
                }

                //cout<<i<<endl;

                //cout<<a[i]<<endl;
                m=m+(a[i]*x);

                //cout<<m<<"  **"<<endl;

            }
        }
        //cout<<i<<endl;
    }

    cout<<m<<endl;



    return 0;
}



Measured memory_bytes: 3580
#ifdef __GNUC__
#pragma GCC diagnostic ignored "-Wunused-result"
#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#endif

#include <algorithm>
#include <cmath>
#include <cstring>
#include <iostream>
#include <sstream>
#include <numeric>
#include <map>
#include <set>
#include <queue>
#include <vector>

using namespace std;

typedef long long LL;

struct UnionFind {
	std::vector<int> _parent;
	std::vector<int> _size;
	UnionFind(int size) : _parent(size, -1), _size(size, 1) { }
	void unite(int a, int b) {
		int ra = root(a), rb = root(b); if (ra == rb) { return; }
		if (_size[ra] >= _size[rb]) { _parent[rb] = ra, _size[ra] += _size[rb]; } else { _parent[ra] = rb, _size[rb] += _size[ra]; }
	}
	int root(int a) {
		int p = _parent[a];
		if (p < 0) { return a; }
		while (_parent[p] >= 0) { p = _parent[p]; }
		return _parent[a] = p;
	}
	int size(int a) { return _size[root(a)]; }
};

void solve(long long N, long long Q, std::vector<long long> &t, std::vector<long long> &u, std::vector<long long> &v) {
	UnionFind uf(N);
	for (LL i = 0; i < Q; ++i) {
		if (t[i] == 0) {
			uf.unite(u[i], v[i]);
		} else {
			cout << (uf.root(u[i]) == uf.root(v[i])) << endl;
		}
	}
}

int main() {
    long long N;
	std::cin >> N;
	long long Q;
	std::cin >> Q;
	std::vector<long long> t(Q);
	std::vector<long long> u(Q);
	std::vector<long long> v(Q);
	for (int i = 0; i < Q; i++) {
		std::cin >> t[i];
		std::cin >> u[i];
		std::cin >> v[i];
	}
	solve(N, Q, t, u, v);
	return 0;
}


Measured memory_bytes: 8776
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

int main()
{
	while (1) {
		int a,b;
		cin >> a>>b;
		if (a == 0&&b==0)break;
		vector<int>s(a);
		for (int c = 0; c < a; c++) {
			cin >> s[c];
		}
		sort(s.begin(), s.end());
		int goukei = 0;
		for (int e = 0; e < a; e++) {
			if ((e + 1) % b != 0)goukei += s[s.size() - 1 - e];
		}
		cout << goukei << endl;
	}
}

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

#define for_(i,a,b) for(int i=a;i<b;++i)

typedef pair< int, int > pii;

class UnionFind {
private:
	vector< int > data;
	int g_cnt;
	
public:
	UnionFind(int n) : data(n, -1), g_cnt(n) {}
	
	bool unionSet(int x, int y) {
		x = root(x);
		y = root(y);
		
		if (x == y) return 0;
		
		if (data[y] < data[x]) swap(x, y);
		data[x] += data[y];
		data[y] = x;
		--g_cnt;
		
		return 1;
	}
	
	bool sameSet(int x, int y) {
		return root(x) == root(y);
	}
	
	int root(int x) {
		return data[x] < 0 ? x : data[x] = root(data[x]);
	}
	
	int getGroupNum() {
		return g_cnt;
	}
};

struct Edge {
	int u, v, c;
	Edge(int _u, int _v, int _c) : u(_u), v(_v), c(_c) {}
	bool operator < (const Edge& e) const {
		return c < e.c;
	}
};

int N, M;
vector< pii > vh;
bool vis[222];
vector< Edge > edges;

void solve() {
	sort(vh.begin(), vh.end(), greater< pii >());
	sort(edges.begin(), edges.end());
	
	int ans = 0, visc = 0;
	UnionFind uf(N);
	
	for_(i,0,N) {
		vis[vh[i].second] = 1;
		++visc;
		
		while (i < N-1 && vh[i].first == vh[i+1].first) {
			++i;
			vis[vh[i].second] = 1;
			++visc;
		}
		
		for_(j,0,M) {
			Edge e = edges[j];
			
			if (vis[e.u] && vis[e.v] && !uf.sameSet(e.u, e.v)) {
				uf.unionSet(e.u, e.v);
				ans += e.c;
			}
		}
		
		int g_cnt = uf.getGroupNum();
		
		if (g_cnt != N - visc + 1) {
			uf = UnionFind(N);
			ans = 0;
		}
		
		if (g_cnt == 1) break;
	}
	
	cout << ans << endl;
}

int main() {
	while (cin >> N >> M, N) {
		memset(vis, 0, sizeof(vis));
		vh.clear();
		
		for_(i,0,N) {
			int h; scanf("%d", &h);
			vh.push_back(pii(h, i));
		}
		
		edges.clear();
		for_(i,0,M) {
			int a, b, c; scanf("%d %d %d", &a, &b, &c);
			--a; --b;
			edges.push_back(Edge(a, b, c));
		}
		
		solve();
	}
	
	return 0;
}

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

int main(int argc, char const *argv[])
{
  int a, b;
  cin >> a >> b;
  int fir = b - a + 1;
  cout << fir;
  for (int i = 1; i < 2*a-1; i++)
  {
    cout << ' ' << fir + i ;
  }

  return 0;
}


Measured memory_bytes: 256
package main

import "fmt"

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

	p := make([]int, n )
	for i:= 0; i < n; i++ {
		fmt.Scan(&p[i])
	}
	if n == 0 {
		fmt.Println(x)
		return
	}

	for i := 0;i <n+100; i++ {
		lit :=  x - i
		big := x + i
		litOk := true
		bigOk := true
		for _, v := range p {
			if lit == v {
				litOk = false
			}
			if big == v {
				bigOk = false
			}
		}
		if litOk {
			fmt.Println(lit)
			return
		}
		if bigOk {
			fmt.Println(big)
			return
		}
	}
}



Measured memory_bytes: 1760
S = str(input())
T = str(input())
substis = []
for i in range(len(S)-len(T)+1):
    count = 0
    for j in range(len(T)):
        if S[i+j] == T[j]:
            count += 1
    substis.append(len(T)-count)
print(min(substis))

Measured memory_bytes: 8908
function Main(input) {
    tmp = input.split(" ");
    n = parseInt(tmp[0], 10);
    x = parseInt(tmp[1], 10);
    t = parseInt(tmp[2], 10);    
    result = Math.ceil( n / x ) * t;
    console.log(result);    
}
Main(require("fs").readFileSync("/dev/stdin", "utf8"));

Measured memory_bytes: 29688
#include <bits/stdc++.h>
using namespace std;
         
#define fast { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0); }
#define pb push_back
#define ll long long
#define ld long double
#define vll vector<ll>
#define infl LONG_LONG_MAX
#define infd LDBL_MAX
#define F first
#define S second
#define pll pair<ll,ll> 
#define G(a,b) get<a>(b)
#define ALL(v) v.begin(),v.end()
#define MP make_pair
#define MT make_tuple
#define f(i,a,b) for(ll i=a;i<b;i++)
#define fi(i,a,b) for(ll i=(b-1);i>=a;i--)    
#define endl "\n"
#define nl cout<<"\n";
#define pr(x) cout<<x;
#define pr1(x) cout<<x<<" ";
#define pr2(x,y) cout<<x<<" "<<y;
#define sz(x) (ll)x.size() 
#define ara cout<<"ara-ara\n"; 
 


void func()
{
   ll n;
   cin>>n;
   ll cnt[n+1]={};
   f(x,1,101)
   {
      f(y,1,101) 
      {
        f(z,1,101) 
        {
          ll tt=x*x+y*y+z*z+x*y+y*z+z*x;
          if(tt<=n) cnt[tt]++;
        }
      }
   }

   f(i,1,n+1) cout<<cnt[i]<<"\n";
}   
     
     
     
int main() 
{
    fast
    //#ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //#endif // ONLINE_JUDGE
        
     
    ll ntc=1;
    //cin>>ntc;
     
    f(i,1,ntc+1)
    {
      //cout<<"Case #"<<i<<": ";
       func();
    }
     
    return 0;
}

Measured memory_bytes: 3604