#623881 (C++17) No.1413 Dynamic Sushi

• 問題: No.1413 Dynamic Sushi
• ユーザー: 👑 Nachia
• 提出日時: 2021-02-28 22:08:55
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 483 ms / 4,000 ms
• コード長: 1,088 bytes
• コンパイル時間: 4,339 ms
• コンパイル使用メモリ: 262,660 KB
• 実行使用メモリ: 5,248 KB
• 最終ジャッジ日時: 2024-10-02 22:30:21
• 合計ジャッジ時間: 14,782 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 5,248 KB
testcase_01	AC	415 ms; 5,248 KB
testcase_02	AC	2 ms; 5,248 KB
testcase_03	AC	2 ms; 5,248 KB
testcase_04	AC	417 ms; 5,248 KB
testcase_05	AC	465 ms; 5,248 KB
testcase_06	AC	475 ms; 5,248 KB
testcase_07	AC	466 ms; 5,248 KB
testcase_08	AC	459 ms; 5,248 KB
testcase_09	AC	479 ms; 5,248 KB
testcase_10	AC	467 ms; 5,248 KB
testcase_11	AC	460 ms; 5,248 KB
testcase_12	AC	468 ms; 5,248 KB
testcase_13	AC	456 ms; 5,248 KB
testcase_14	AC	476 ms; 5,248 KB
testcase_15	AC	460 ms; 5,248 KB
testcase_16	AC	472 ms; 5,248 KB
testcase_17	AC	483 ms; 5,248 KB
testcase_18	AC	474 ms; 5,248 KB
testcase_19	AC	472 ms; 5,248 KB
testcase_20	AC	200 ms; 5,248 KB
testcase_21	AC	3 ms; 5,248 KB
testcase_22	AC	468 ms; 5,248 KB
testcase_23	AC	469 ms; 5,248 KB
testcase_24	AC	471 ms; 5,248 KB

ソースコード

#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;
}