結果

問題 No.1413 Dynamic Sushi
ユーザー 👑 NachiaNachia
提出日時 2021-02-28 22:08:55
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 482 ms / 4,000 ms
コード長 1,088 bytes
コンパイル時間 4,679 ms
コンパイル使用メモリ 256,616 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-04-12 10:50:53
合計ジャッジ時間 15,511 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 425 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 422 ms
6,940 KB
testcase_05 AC 467 ms
6,940 KB
testcase_06 AC 474 ms
6,940 KB
testcase_07 AC 470 ms
6,940 KB
testcase_08 AC 460 ms
6,940 KB
testcase_09 AC 482 ms
6,940 KB
testcase_10 AC 476 ms
6,940 KB
testcase_11 AC 468 ms
6,940 KB
testcase_12 AC 477 ms
6,940 KB
testcase_13 AC 463 ms
6,940 KB
testcase_14 AC 478 ms
6,944 KB
testcase_15 AC 478 ms
6,944 KB
testcase_16 AC 481 ms
6,940 KB
testcase_17 AC 475 ms
6,948 KB
testcase_18 AC 481 ms
6,940 KB
testcase_19 AC 479 ms
6,940 KB
testcase_20 AC 203 ms
6,944 KB
testcase_21 AC 4 ms
6,940 KB
testcase_22 AC 470 ms
6,940 KB
testcase_23 AC 468 ms
6,940 KB
testcase_24 AC 474 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using ull=unsigned long long;
#define rep(i,n) for(int i=0; i<(n); i++)

using C=complex<double>;


int N;
double W;
double A[13][5];

C f(int i,double t){ return C(A[i][0],A[i][1]) + polar<double>(A[i][2],A[i][3]*t+A[i][4]); }

double T(int u,int v,double t){
  C pos=f(u,t);
  double l=0.0, r=1000.0;
  while(r-l>1.0e-8){
    double m=(l+r)/2;
    C pos_to=f(v,t+m);
    ((abs(pos_to-pos)<(m*W))?r:l) = m;
  }
  //printf("T(%d,%d,%.5f) = %.5f\n",u,v,t,t+r);
  return t+r;
}

int main(){
  cin>>N>>W;
  rep(i,N) rep(j,5) cin>>A[i][j];
  rep(i,N){ A[i][3] *= acos(-1.0)/180.0; A[i][4] *= acos(-1.0)/180.0; }
  rep(i,5) A[N][i]=0.0;
  double dp[1<<12][12]; rep(i,1<<N) rep(j,N) dp[i][j]=1.0e50;
  rep(i,N) dp[1<<i][i]=T(N,i,0.0);
  rep(F,1<<N) rep(i,N) rep(j,N){
    if(!(F&(1<<i))) continue;
    if(F&(1<<j)) continue;
    dp[F|(1<<j)][j] = min(dp[F|(1<<j)][j],T(i,j,dp[F][i]));
  }
  double ans=1.0e50; rep(i,N) ans=min(ans,dp[(1<<N)-1][i]);
  cout<<setprecision(6)<<fixed<<ans<<endl;
  return 0;
}
0