Submission #00067

ソースコード

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;cin>>n;
    vector<pair<int,int>>s(n),t(n);
    vector<pair<int,pair<int,int>>>p(n);
    for(int i=0;i<n;i++){
        cin>>s[i].first>>s[i].second;
        p[i].second.first=t[i].second=s[i].first;
        p[i].second.second=t[i].first=s[i].second;
        p[i].first=s[i].second+s[i].first;
    }
    sort(s.begin(),s.end());
    sort(t.begin(),t.end());
    sort(p.begin(),p.end());
    double ans=20000000;
 
    int g=50000000;
    do{
        g--;
        double k=sqrt(s[0].first*s[0].first+s[0].second*s[0].second);
        for(int i=0;i<n-1;i++){
            k+=sqrt((s[i].first-s[i+1].first)*(s[i].first-s[i+1].first)+(s[i].second-s[i+1].second)*(s[i].second-s[i+1].second));
        }
        k+=sqrt((1000-s[n-1].first)*(1000-s[n-1].first)+(1000-s[n-1].second)*(1000-s[n-1].second));
        ans=min(ans,k);
        if(g==0)break;
        //printf("%.10lf\n",k);
    }while(next_permutation(s.begin(),s.end()));
    //printf("%.10lf\n",ans);
    g=5000000;
    do{
        g--;
        double k=sqrt(t[0].first*t[0].first+t[0].second*t[0].second);
        for(int i=0;i<n-1;i++){
            k+=sqrt((t[i].first-t[i+1].first)*(t[i].first-t[i+1].first)+(t[i].second-t[i+1].second)*(t[i].second-t[i+1].second));
        }
        k+=sqrt((1000-t[n-1].first)*(1000-t[n-1].first)+(1000-t[n-1].second)*(1000-t[n-1].second));
        ans=min(ans,k);
        if(g==0)break;
    }while(next_permutation(t.begin(),t.end()));
    //printf("%.10lf\n",ans);
    g=5000000;
    do{
        g--;
        double k=sqrt(p[0].second.first*p[0].second.first+p[0].second.second*p[0].second.second);
        for(int i=0;i<n-1;i++){
            k+=sqrt((p[i].second.first-p[i+1].second.first)*(p[i].second.first-p[i+1].second.first)+(p[i].second.second-p[i+1].second.second)*(p[i].second.second-p[i+1].second.second));
        }
        k+=sqrt((1000-p[n-1].second.first)*(1000-p[n-1].second.first)+(1000-p[n-1].second.second)*(1000-p[n-1].second.second));
        ans=min(ans,k);
        if(g==0)break;
    }while(next_permutation(p.begin(),p.end()));
    printf("%.10lf\n",ans);
}

ステータス

項目	データ
問題	0021 - ひとりたび
ユーザー名	ei2326
投稿日時	2023-11-13 15:51:28
言語	C++17
状態	Time Limit Exceeded
得点	0
ソースコード長	2193 Byte
最大実行時間	1000 ms
最大メモリ使用量	708 KB

セット

	セット	得点	Cases
1	ALL	0 / 100	*

テストケース

ファイル名	状態	実行時間	メモリ使用量	#
01.txt	AC	23 ms	604 KB	1
02.txt	AC	24 ms	708 KB	1
03.txt	AC	27 ms	552 KB	1
04.txt	AC	27 ms	392 KB	1
05.txt	AC	20 ms	488 KB	1
06.txt	AC	14 ms	460 KB	1
07.txt	AC	24 ms	436 KB	1
08.txt	AC	30 ms	408 KB	1
09.txt	AC	76 ms	636 KB	1
10.txt	AC	538 ms	480 KB	1
11.txt	TLE	1000 ms	456 KB	1
12.txt	TLE	1000 ms	556 KB	1
13.txt	TLE	1000 ms	532 KB	1
sp.txt	TLE	1000 ms	512 KB	1