stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ll long long

#define pb push_back

#define mp make_pair

int cnt[501];

bool was[501];

using namespace std;

int N;

bool can = true;

int a[250001];

int pos[500];

vector<pair<int , int> > g;

int main()

{

    memset(a , -1 , sizeof a);

    scanf("%d" , &N);

    for(int i = 1; i <= N; i++)

    {

        cnt[i] = 1;

        int x;

        scanf("%d" , &x);

        pos[i] = x;

        a[x] = i;

        g.pb(mp(x , i));

    }

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

    for(int i = 0; i < g.size(); i++)

    {

        int curPos = g[i].first;

        int x = g[i].second;

        int cur = x;

        for(int i = 1; i < curPos; i++)

        {

            if(a[i] != -1)

                continue;

            if(cnt[cur] < cur)

            {

                a[i] = cur;

                cnt[cur]++;

            }

        }

        if(cnt[cur] != cur)

        {

            printf("No");

            return 0;

        }

    }

    for(int i = 1; i <= N; i++)

    {

        for(int j = pos[i] + 1; j <= N * N; j++)

        {

            if(a[j] != -1)

                continue;

            if(cnt[i] < N)

            {

                a[j] = i;

                cnt[i]++;

            }

        }

        if(cnt[i] < N)

        {

            printf("No");

            return 0;

        }

    }

    if(!can)

    {

        printf("No");

        return 0;

    }

    printf("Yes\n");

    for(int i = 1; i <= N * N; i++)

        printf("%d " , a[i]);

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

#define MAXN 510

#define MAXM 250010

int a[MAXM],f[MAXN],x[MAXN],n,ls=1;

bool cmp(int a,int b)

{

	return x[a]<x[b];

}

int main()

{

	scanf("%d",&n);

	for(int i=1;i<=n;i++)

	{

		scanf("%d",&x[i]);

		a[x[i]]=i;

		f[i]=i;

	}

	sort(f+1,f+1+n,cmp);

	for(int i=1;i<=n;i++)

	{

		int k=f[i];

		for(int j=1;j<k;j++)

		{

			while(a[ls]) ls++;

			if(ls>x[k])

			{

				printf("No\n");

				return 0;

			}

			a[ls]=k;

		}

	}

	for(int i=1;i<=n;i++)

	{

		int k=f[i];

		for(int j=1;j<=n-k;j++)

		{

			while(a[ls]) ls++;

			if(ls<x[k]||ls>n*n)

			{

				printf("No\n");

				return 0;

			}

			a[ls]=k;

		}

	}

	printf("Yes\n");

	for(int i=1;i<=n*n;i++)

		printf("%d ",a[i]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std ;

#define rep( i, s, t ) for( register int i = s; i <= t; ++ i )

#define re register

int gi() {

	char cc = getchar() ; int cn = 0, flus = 1 ;

	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }

	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;

	return cn * flus ;

}

const int N = 500 + 5 ;

int n, a[N], b[N * N], Id[N] ; 

bool cmp( int x, int y ) {

	return a[x] < a[y] ;

}

signed main()

{

	n = gi() ;

	rep( i, 1, n ) a[i] = gi(), Id[i] = i ;

	sort( Id + 1, Id + n + 1, cmp ) ;

	rep( i, 1, n ) if( a[Id[i]] == a[Id[i - 1]] ) {

		puts("No") ; exit(0) ;

	}

	int cnt = 0 ;

	rep( i, 1, n ) {

		int u = Id[i] - 1 ; 

		rep( j, 1, u ) {

			while( b[cnt + 1] ) ++ cnt ;

			b[++ cnt] = Id[i] ; 

		} 

		while( b[cnt + 1] ) ++ cnt ;

		if( cnt >= a[Id[i]] ) {

			puts("No") ; exit(0) ;

		}

		b[a[Id[i]]] = Id[i] ; 

		

	}

	rep( i, 1, n ) {

		int u = n - Id[i] ;

		while( b[cnt + 1] ) ++ cnt ; 

		if( cnt < a[Id[i]] ) {

			puts("No") ; exit(0) ; 

		}

		rep( j, 1, u ) {

			while( b[cnt + 1] ) ++ cnt ; 

			b[++ cnt] = Id[i] ;

		}

	}

	printf("Yes\n") ;

	rep( i, 1, n * n ) printf("%d ", b[i] ) ;

	return 0 ;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

#define N 500

using namespace std;



int a[N + 5], p[N + 5], b[N * N + 5] = {0};



void write(int x)

{

	if(x < 10){

		putchar(x + 48);

		return;

	}

	write(x / 10);

	putchar(x % 10 + 48);

}



int cmp(int x, int y)

{

	return a[x] < a[y];

}



int next(int i)

{

	for(i++; b[i]; i++);

	return i;

}



int main()

{		

	int n, i, head = 1, j, x, t;

	

	scanf("%d", &n);

	for(i = 1; i <= n; i++){

		scanf("%d", a + i);

		p[i] = i;

	}

	sort(p + 1, p + n + 1, cmp);

	

	for(i = 1; i <= n; i++){

		x = p[i], t = a[x];

		for(j = 1; j < x; j++){

			if(head >= t){

				puts("No");

				return 0;

			}

			b[head] = x;

			head = next(head);

		}

		if(head == t) head = next(head);

		b[t] = x;

	}

	for(i = 1; i <= n; i++){

		x = p[i], t = a[x];

		for(j = x + 1; j <= n; j++){

			if(head > t) b[head] = x;

			else{

				puts("No");

				return 0;

			}

			head = next(head);

		}

	}

	puts("Yes");

	write(b[1]);

	for(i = 2, t = n * n; i <= t; i++){

		putchar(32), write(b[i]);

	}

	puts("");

			

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <cmath>

#include <cstdlib>

#define ll long long

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

#define per(i, b, a) for(int i = (b); i >= (a); i--)

using namespace std;

const int N = 505, M = 250005;

int n, sum, b[N], ans[M], ssum[N];

struct node{

    int pl, num;

}a[N];

bool cmp(node x, node y){

    return x.num == y.num ? x.pl < y.pl : x.num < y.num;

}

int main(){

    scanf("%d", &n);

    rep(i, 1, n){

        scanf("%d", &b[i]);

        a[i].pl = i, a[i].num = b[i];

    }

    sort(a + 1, a + n + 1, cmp);

    rep(i, 1, n){

        sum += a[i].pl;

        if(a[i].num < sum || a[i].num == a[i-1].num) {

            printf("No\n");

            return 0;

        }

    }

    sum = 0;

    per(i, n, 1){

        sum += n - a[i].pl + 1;

        if(n * n - a[i].num + 1 < sum) {

            printf("No\n");

            return 0;

        } 

    }

    rep(i, 1, n){

        int num = a[i].pl - 1;

        ans[a[i].num] = a[i].pl, ssum[a[i].pl]++;

        rep(j, 1, a[i].num - 1) {

            if(!num) break;

            if(!ans[j]) ans[j] = a[i].pl, num--, ssum[a[i].pl]++;

        }

    }

    rep(i, 1, n) rep(j, b[i] + 1, n * n) {

        if(ssum[i] == n) break;

        if(!ans[j]) ans[j] = i, ssum[i]++;

    }

    printf("Yes\n");

    rep(i, 1, n * n) printf("%d ", ans[i]);

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 505

int pos[N],id[N],ans[N*N];

bool cmp(int x,int y){return pos[x]<pos[y];}

int main()

{

	int n,i,j,k,x;

	scanf("%d",&n);

	for(i=1;i<=n;i++){

		scanf("%d",&pos[i]);

		id[i]=i;ans[pos[i]]=i;

	}

	sort(id+1,id+n+1,cmp);

	k=1;

	for(i=1;i<=n;i++){

		x=id[i];

		for(j=1;j<x;j++){

			while(ans[k])k++;

			if(k>pos[x]){printf("No\n");return 0;}

			ans[k]=x;

		}

	}

	for(i=1;i<=n;i++){

		x=id[i];

		for(j=x+1;j<=n;j++){

			while(ans[k])k++;

			if(k<pos[x]){printf("No\n");return 0;}

			ans[k]=x;

		}

	}

	printf("Yes\n%d",ans[1]);

	for(i=2;i<=n*n;i++)

		printf(" %d",ans[i]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <queue>

#define FUP(i,x,y) for(int i=(x);i<=(y);i++)

#define FDW(i,x,y) for(int i=(x);i>=(y);i--)

#define MAXN 510

#define INF 0x3f3f3f3f

#define MOD 1000000007

#define ll long long

#define db double

using namespace std;

int read(){

    int w=0,flg=1;

    char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')flg=-1;ch=getchar();}

    while(ch<='9'&&ch>='0'){w=w*10-'0'+ch,ch=getchar();}

    return w*flg;

}

struct node{

	int pos,data;

}b[MAXN];

bool cmp(node p,node q)

{

	return p.pos<q.pos;

}

int n,x[MAXN];

int a[MAXN*MAXN],need[MAXN*MAXN],now[MAXN*MAXN];

int num[MAXN*2],used[MAXN*2],cnt=1;

int main(){

	n=read();

	FUP(i,1,n)

	{

		x[i]=b[i].pos=read();

		b[i].data=i;

		a[x[i]]=i;

		need[x[i]]=i-1;

	}

	sort(b+1,b+n+1,cmp);

	FUP(i,1,n) num[i]=b[i].pos,used[i]=b[i].data-1;

	FUP(i,n+1,2*n) num[i]=b[i-n].pos,used[i]=n-1-used[i-n];

	FUP(i,1,n*n)

	{

		if(a[i])

		{

			if(need[i]!=now[i])

			{

				puts("No");

				return 0;

			}

		}

		else

		{

			while(used[cnt]==0) cnt++;

			used[cnt]--;

			a[i]=a[num[cnt]];

			now[num[cnt]]++;

		}

	}

	puts("Yes");

	FUP(i,1,n*n) printf("%d ",a[i]);

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 505

int pos[N],id[N],ans[N*N];

bool cmp(int x,int y){return pos[x]<pos[y];}

int main()

{

	int n,i,j,k,x;

	scanf("%d",&n);

	for(i=1;i<=n;i++){

		scanf("%d",&pos[i]);

		id[i]=i;ans[pos[i]]=i;

	}

	sort(id+1,id+n+1,cmp);

	k=1;

	for(i=1;i<=n;i++){

		x=id[i];

		for(j=1;j<x;j++){

			while(ans[k])k++;

			if(k>pos[x]){printf("No\n");return 0;}

			ans[k]=x;

		}

	}

	for(i=1;i<=n;i++){

		x=id[i];

		for(j=x+1;j<=n;j++){

			while(ans[k])k++;

			if(k<pos[x]){printf("No\n");return 0;}

			ans[k]=x;

		}

	}

	printf("Yes\n%d",ans[1]);

	for(i=2;i<=n*n;i++)

		printf(" %d",ans[i]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define maxn 250010

template <typename T>inline T read()

{

    register T sum=0;

    register char cc=getchar();

    int sym=1;

    while(cc!='-'&&(cc>'9'||cc<'0'))cc=getchar();

    if(cc=='-')sym=-1,cc=getchar();

    sum=sum*10+cc-'0';

    cc=getchar();

    while(cc>='0'&&cc<='9')sum=sum*10+cc-'0',cc=getchar();

    return sym*sum;

}

template <typename T>inline T read(T &a)

{

    a=read<T>();

    return a;

}

template <typename T,typename... Others> inline void read(T& a, Others&... b)

{

    a=read(a);

	read(b...);

}

int n,m,a[maxn],cnt[maxn],ans[maxn],pos[maxn];

int main()

{

	read(n);

	m=n*n;

	for(int i=1;i<=n;i++)

	{

		read(a[i]);

		if(ans[a[i]])

		{

			puts("No");

			return 0;

		}

		cnt[a[i]]=i;

		ans[a[i]]=i;

		pos[a[i]]=i;

	}

	for(int i=1;i<=m;i++)

	{

		cnt[i]+=cnt[i-1];

		if(cnt[i]>i)

		{

			puts("No");

			return 0;

		}

	}

	int p=1;

	for(int i=1;i<=m;i++)

	{

		if(pos[i])

		{

			for(int s=ans[i]-1;s;s--)

			{

				while(ans[p])

					p+=1;

				if(p>i)

				{

					puts("No");

					return 0;

				}

				ans[p]=ans[i];

			}

		}

	}

	p=m;

	for(int i=m;i>=1;i--)

	{

		if(pos[i])

		{

			for(int s=n-ans[i];s;s--)

			{

				while(ans[p])

					p-=1;

				if(p<i)

				{

					puts("No");

					return 0;

				}

				ans[p]=ans[i];

			}

		}

	}

	puts("Yes");

	for(int i=1;i<=m;i++)

		printf("%d ",ans[i]);

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define N 505

int pos[N],id[N],ans[N*N];

bool cmp(int x,int y){return pos[x]<pos[y];}

int main()

{

	int n,i,j,k,x;

	scanf("%d",&n);

	for(i=1;i<=n;i++){

		scanf("%d",&pos[i]);

		id[i]=i;ans[pos[i]]=i;

	}

	sort(id+1,id+n+1,cmp);

	k=1;

	for(i=1;i<=n;i++){

		x=id[i];

		for(j=1;j<x;j++){

			while(ans[k])k++;

			if(k>pos[x]){printf("No\n");return 0;}

			ans[k]=x;

		}

	}

	for(i=1;i<=n;i++){

		x=id[i];

		for(j=x+1;j<=n;j++){

			while(ans[k])k++;

			if(k<pos[x]){printf("No\n");return 0;}

			ans[k]=x;

		}

	}

	printf("Yes\n%d",ans[1]);

	for(i=2;i<=n*n;i++)

		printf(" %d",ans[i]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

 string S[200001];

int main()

{

    map <string,int> mp;



    int i, cnt = 0, n;

    cin >> n;

    for(i = 0; i < n; i++)

    {

        cin >> S[i];

        mp[S[i]]++;

    }

    for(i = 0; i < n; i++)

    {

        if(mp[S[i]] != 0)

        {

            cnt++;

            mp[S[i]] = 0;

        }

    }

    cout << cnt << endl;



}


// Optimized solution to the same problem (faster):
#include <iostream>

#include <set>

using namespace std;

int main() {

    set<string> dd;

    int n;

    cin>>n;

    string ss;

    while(n--){

    	cin>>ss;

    	dd.insert(ss);

    }cout<<dd.size();

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

string s[200005];

int main()

{

    ios::sync_with_stdio(false);

    int n;

    cin>>n;

    for(int i=0;i<n;i++)

    {

        cin>>s[i];

    }

    sort(s,s+n);

    string s1="";

    long long ans=0;

    for(int i=0;i<n;i++)

    {

        if(s1!=s[i])

        {

            ans++;

            s1=s[i];

        }

    }

    cout<<ans;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

set<string>s;

int main(){

	int n;

	cin>>n;

	while(n--){

		string s1;

		cin>>s1;

		s.insert(s1);

	}

	cout<<s.size();

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<algorithm>

#include<string>

using namespace std;

int n,i,s;

string a[200001];

int main(){

	cin>>n;

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

	sort(a,a+n);

	s=1;

	for(i=1;i<n;i++){

		if(a[i]!=a[i-1]) s++;

	}

	cout<<s<<endl;

	return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <algorithm>

#include <set>

#include <string>

#pragma warning (disable:4996)

using namespace std;





int main() {

	set<string> s;

	int n;

	string a;

	cin >> n;

	for (int i = 0; i < n; i++) {

		cin >> a;

		s.insert(a);

	}

	cout << s.size();



}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <unordered_map>

#include <iterator>

#include <algorithm>

#include <string>

#include <functional>

#include <vector>



using namespace std;



int main(void)

{

  int n;

  cin >> n;

  vector<size_t> v(20000);

  int sum = 0;



  unordered_map<size_t, int> um;

  for (int i = 0; i < n; i++) {

    string str;

    cin >> str;

    size_t hs = hash<string>()(str);

    auto itr = lower_bound(v.begin(), v.end(), hs);



    if (itr == v.end()) {

      v.push_back(hs);

      sum++;

    } else if (*itr != hs) {

     v.insert(itr, hs);

      sum++;

    } else {

    }

  }

  cout << sum << endl;



  return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <stdlib.h>

#include <map>



using namespace std;



int main (void)

{

  int n;

  cin >> n;

  map<string, int> m;

  for (int i = 0; i < n; i++) {

    string s; cin >> s;

    m[s]++;

  }



  cout << m.size() << endl;

  return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int N;

string a[200001];

map<string, int> mp;

int ans = 0;



int main(){

    cin >> N;

    for(int i=0;i<N;i++){

        cin >> a[i];

        mp[a[i]] = 1;

    }

    for(auto i = mp.begin(); i != mp.end(); ++i){

        ans += i->second;

    }

    cout << ans << endl;

    return 0;  

}

// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;

int N, ans = 0;

string str;

map<string, int> mp;



int main(){

    cin >> N;

    for(int i=0;i<N;i++){ cin >> str; mp[str] = 1;}

    for(auto i = mp.begin(); i != mp.end(); ++i) ans += i->second;

    cout << ans << endl;

    return 0;  

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

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

#define Rep(i,n) for(int i=1;i<=n;i++)

const ll MOD = 1000000007;

long long modinv(long long a, long long m=MOD) {

    long long b = m, u = 1, v = 0;

    while (b) {

        long long t = a / b;

        a -= t * b; swap(a, b);

        u -= t * v; swap(u, v);

    }

    u %= m; 

    if (u < 0) u += m;

    return u;

    /*MODの割り算の際に

    a/＝b;

    を

    a *= modinv(b,MOD);

    とする。

        */

}

const int MAXN = 200001;

string S[MAXN];



int main(){

    int N;cin >> N;

    rep(i,N)cin >> S[i];

    map<string,int> ma;

    ll ans = 0;

    rep(i,N){

        if(ma[S[i]]>0){

            ma[S[i]]++;

        }

        else {

            ma[S[i]] = 1;

            ans ++;

        }

    }



    cout <<ans << endl;

    







    return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <set>

using namespace std;

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



int main(){

    int N;cin >> N;

    set<string> se;

    rep(i,N){

        string s;cin >> s;

        se.insert(s);

    }

    cout << se.size() << endl;

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <stdio.h>

#include <algorithm>

using namespace std;

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

#define INF (1<<28)



int n, m, a[64], b[64], c[64];

int dp[64][64][64];



int f(int k, int x, int y) {

    int ans = c[k];

    rep (i, x+1) rep (j, y+1) if (1 <= i+j && i+j <= 8) {

        ans = max(ans, a[k]*i + b[k]*j);

    }

    return ans;

}



int main() {

    scanf("%d%d", &n, &m);

    rep (i, n) scanf("%d%d%d", a+i, b+i, c+i);

    rep (i, 64) rep (j, 64) rep (k, 64) dp[i][j][k] = -INF;

    dp[0][0][0] = 0;

    rep (k, n) rep (x, m+1) rep (i, x+1) if (dp[k][x][i] > -INF) {

        rep (j, m-x+1) {

            dp[k+1][x+j][j] = max(dp[k+1][x+j][j], dp[k][x][i]+f(k, j, i));

        }

    }

    int ans = -INF;

    rep (x, m+1) rep (i, 64) ans = max(ans, dp[n][x][i]);

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

    return 0;

}

// Optimized solution to the same problem (faster):
#include <stdio.h>

#include <algorithm>

using namespace std;

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

#define INF (1<<28)



int n, m, a[64], b[64], c[64];

int f[64][10][10], dp[64][64][10];



int main() {

    scanf("%d%d", &n, &m);

    rep (i, n) scanf("%d%d%d", a+i, b+i, c+i);

    rep (k, 64) rep (x, 10) rep (y, 10) {

        f[k][x][y] = c[k];

        rep (i, x+1) rep (j, y+1) if (1 <= i+j && i+j <= 8) {

            f[k][x][y] = max(f[k][x][y], a[k]*j + b[k]*i);

        }

    }

    rep (i, 64) rep (j, 64) rep (k, 10) dp[i][j][k] = -INF;

    dp[0][0][0] = 0;

    rep (k, n) rep (x, m+1) rep (i, min(8, x)+1) if (dp[k][x][i] > -INF) {

        rep (j, min(8, m-x)+1) {

            dp[k+1][x+j][j] = max(dp[k+1][x+j][j], dp[k][x][i]+f[k][i][j]);

        }

    }

    int ans = -INF;

    rep (x, m+1) rep (i, 10) ans = max(ans, dp[n][x][i]);

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

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

double inf=1000000000000000000;

struct Cir{

	double x,y,r;

}e[1005];

double a[1005][1005],d[1005];

int n,vis[1005];

double xs,ys,xt,yt;

double min(double x,double y){

	return x<y?x:y;

}

double max(double x,double y){

	return x>y?x:y;

}

double dis(double xa,double ya,double xb,double yb){

	return sqrt((xa-xb)*(xa-xb)+(ya-yb)*(ya-yb));

}

double dij(int n,int S,int T){

	int mini;

    for(int i=1;i<=n;i++) d[i]=inf,vis[i]=0;

    d[S]=0,d[0]=inf+1;

    while(!vis[T]){

    	mini=0;

        for(int i=1;i<=n;i++) if(!vis[i]&&d[mini]>d[i]) mini=i;

        vis[mini]=1;

        for(int i=1;i<=n;i++) if(!vis[i]) d[i]=min(d[i],d[mini]+a[mini][i]);

    }

    return d[mini];

}

int main(){

    scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);

    scanf("%d",&n);

    for(int i=1;i<=n;i++) scanf("%lf%lf%lf",&e[i].x,&e[i].y,&e[i].r);

    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){

          double r1=e[i].r,r2=e[j].r;

          a[i][j]=a[j][i]=max(0.0,dis(e[i].x,e[i].y,e[j].x,e[j].y)-r1-r2); 

    }

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

        a[n+1][i]=a[i][n+1]=max(0.0,dis(xs,ys,e[i].x,e[i].y)-e[i].r);

        a[n+2][i]=a[i][n+2]=max(0.0,dis(xt,yt,e[i].x,e[i].y)-e[i].r);

        a[i][i]=0;

    }

    a[n+1][n+1]=a[n+2][n+2]=0;

    a[n+1][n+2]=a[n+2][n+1]=dis(xs,ys,xt,yt);

    printf("%.10lf\n",dij(n+2,n+1,n+2));

    return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

double f[1005][1005],dis[1005],a[1005][3];

bool b[1005];

int main()

{

	int i,j,k,n;

	double xi,xs,ys,xt,yt;

	scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);

	scanf("%d",&n);

	a[0][0]=xs;a[0][1]=ys;a[0][2]=0;

	a[n+1][0]=xt;a[n+1][1]=yt;a[n+1][2]=0;

	for(i=1;i<=n;i++)

		scanf("%lf%lf%lf",&a[i][0],&a[i][1],&a[i][2]);

	n++;

	for(i=0;i<=n;i++)

		for(j=i+1;j<=n;j++)

			f[i][j]=f[j][i]=max(0.0,sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]))-(a[i][2]+a[j][2]));

	for(i=0;i<=1003;i++) dis[i]=1e18;

	dis[0]=0; 

	for(i=0;i<n;i++){ 

		xi=1e18;

		k=0; 

		for(j=0;j<=n;j++){

            if(b[j]==0&&dis[j]<xi){

				xi=dis[j]; 

				k=j; 

			} 

        }

		b[k]=1; 

		for(j=0;j<=n;j++)

			dis[j]=min(dis[j],dis[k]+f[k][j]);

	}

	printf("%.9lf",dis[n]);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <string>

#include <sstream>

#include <complex>

#include <vector>

#include <list>

#include <queue>

#include <deque>

#include <stack>

#include <map>

#include <set>

using namespace std;

typedef long long unsigned int ll;



#define EPS (1e-7)

#define INF (1e9)

#define PI (acos(-1))

const long double zero = 0.0;

ll x[1010], y[1010], r[1010];

long double dist(int i, int j)

{

    ll dx = (x[i] - x[j]);

    ll dy = y[i] - y[j];

    return pow((long double)(dx * dx + dy * dy), 0.5);

}



int main() {

    cout.precision(100);

    ll xs, ys, xt, yt;

    cin >> xs >> ys >> xt >> yt;

    int n;

    cin >> n;

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

        cin >> x[i] >> y[i] >> r[i];

    }

    x[0] = xt;

    y[0] = yt;

    r[0] = 0;

    x[n + 1] = xs;

    y[n + 1] = ys;

    vector<pair<long double, int> > cost;

    for(int i = 0; i <= n; i++){

        pair<long double, int> in;

        in.first = max(zero, dist(i, n + 1) - r[i]);

        in.second = i;

        cost.push_back(in);

    }

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

    for(int i = 0; i <= n; i++){

        if(cost[i].second == 0){

            cout << cost[i].first << endl;

            return 0;

        }

        for(int j = i + 1; j <= n; j++){

            cost[j].first = min(cost[j].first, cost[i].first + max(zero, dist(cost[i].second, cost[j].second) - r[cost[i].second] - r[cost[j].second]));

        }

        sort(cost.begin() + i + 1, cost.end());

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

double f[1005][1005],dis[1005],a[1005][3];

bool b[1005];

int main()

{

	int i,j,k,n;

	double xi,xs,ys,xt,yt;

	scanf("%lf%lf%lf%lf",&xs,&ys,&xt,&yt);

	scanf("%d",&n);

	a[0][0]=xs;a[0][1]=ys;a[0][2]=0;

	a[n+1][0]=xt;a[n+1][1]=yt;a[n+1][2]=0;

	for(i=1;i<=n;i++)

		scanf("%lf%lf%lf",&a[i][0],&a[i][1],&a[i][2]);

	n++;

	for(i=0;i<=n;i++)

		for(j=i+1;j<=n;j++)

			f[i][j]=f[j][i]=max(0.0,sqrt((a[i][0]-a[j][0])*(a[i][0]-a[j][0])+(a[i][1]-a[j][1])*(a[i][1]-a[j][1]))-(a[i][2]+a[j][2]));

	for(i=0;i<=1003;i++) dis[i]=1e18;

	dis[0]=0; 

	for(i=0;i<n;i++){ 

		xi=1e18;

		k=0; 

		for(j=0;j<=n;j++){

            if(b[j]==0&&dis[j]<xi){

				xi=dis[j]; 

				k=j; 

			} 

        }

		b[k]=1; 

		for(j=0;j<=n;j++)

			dis[j]=min(dis[j],dis[k]+f[k][j]);

	}

	printf("%.9lf",dis[n]);

}

// Fastest known solution for this problem: