結果
問題 | No.1413 Dynamic Sushi |
ユーザー |
|
提出日時 | 2021-02-28 22:01:58 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 2,595 bytes |
コンパイル時間 | 7,718 ms |
コンパイル使用メモリ | 262,792 KB |
最終ジャッジ日時 | 2025-01-19 08:40:27 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 TLE * 1 |
ソースコード
#include<bits/stdc++.h> using namespace std; #define rep(i,n) for(ll i=0;i<n;i++) #define repl(i,l,r) for(ll i=(l);i<(r);i++) #define per(i,n) for(ll i=(n)-1;i>=0;i--) #define perl(i,r,l) for(ll i=r-1;i>=l;i--) #define fi first #define se second #define pb push_back #define ins insert #define pqueue(x) priority_queue<x,vector<x>,greater<x>> #define all(x) (x).begin(),(x).end() #define CST(x) cout<<fixed<<setprecision(x) #define rev(x) reverse(x); using ll=long long; using vl=vector<ll>; using vvl=vector<vector<ll>>; using pl=pair<ll,ll>; using vpl=vector<pl>; using vvpl=vector<vpl>; ll MOD=1000000007; ll MOD9=998244353; int inf=1e9+10; ll INF=4e18; ll dy[8]={1,0,-1,0,1,1,-1,-1}; ll dx[8]={0,1,0,-1,1,-1,1,-1}; template <typename T> inline bool chmax(T &a, T b) { return ((a < b) ? (a = b, true) : (false)); } template <typename T> inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); } using ld=long double; struct sushi{ ld x,y,r,v,a; }; struct point{ ld x,y; }; ld w; const ld pi=3.1415926535; ld dist(point a,point b){ ld len=(a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y); return sqrt(len); } pair<ld,point> calc(sushi s,point p,ld time){//pとsの出会う最小の時間とその座標 ld ng=0,ok=inf; ll loop=100; point ret; while(loop--){ ld mid=(ok+ng)/2; ld now=time+mid; ret.x=s.x+s.r*cos((s.v*now+s.a)*pi/180); ret.y=s.y+s.r*sin((s.v*now+s.a)*pi/180); ld need=dist(ret,p)/w; if(need<=mid)ok=mid; else ng=mid; } return {time+ok,ret}; } int main(){ ll n;cin >> n >>w; vector<sushi> s(n); rep(i,n){ cin >> s[i].x >> s[i].y >> s[i].r >> s[i].v >> s[i].a; } point start;start.x=0,start.y=0; /*rep(i,3){ auto ans=calc(s[i],start,0); cout << ans.se.x <<" " << ans.se.y <<endl; cout << ans.fi <<endl; }*/ vector<vector<pair<ld,point>>> dp(1<<n,vector<pair<ld,point>>(n)); rep(bit,1<<n)rep(i,n)dp[bit][i]={INF,start}; rep(i,n){ dp[1<<i][i]=calc(s[i],start,0); } rep(bit,1<<n){ rep(i,n){ if(!(bit&(1<<i)))continue; rep(j,n){ if(bit&(1<<j))continue;//i->j auto to=calc(s[j],dp[bit][i].se,dp[bit][i].fi); if(dp[bit|(1<<j)][j].fi>to.fi){ dp[bit|(1<<j)][j]=to; } } } } CST(10); ld ans=INF; rep(i,n){ //cout << dp[(1<<n)-1][i].fi <<endl; chmin(ans,dp[(1<<n)-1][i].fi); } cout << ans <<endl; }