結果

問題 No.1413 Dynamic Sushi
コンテスト
ユーザー どらら
提出日時 2021-02-28 22:11:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,133 ms / 4,000 ms
コード長 1,754 bytes
コンパイル時間 4,063 ms
コンパイル使用メモリ 231,532 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-02 22:33:20
合計ジャッジ時間 25,268 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
#define REP(i,a,n) for(int i=(a); i<(int)(n); i++)
#define rep(i,n) REP(i,0,n)
#define FOR(it,c) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define ALLOF(c) (c).begin(), (c).end()
typedef long long ll;
typedef unsigned long long ull;
//using mint = modint1000000007;
//using mint = modint998244353;

static const double PI = acos(0)*2;

struct ST {
  int X, Y, R, V, A;
};

int N, W;
vector<ST> v;

double dp[1<<13][13];

double calc(double t, int x, int y){
  double posx = v[x].X + v[x].R * cos((v[x].V * t + v[x].A) * PI / 180.0);
  double posy = v[x].Y + v[x].R * sin((v[x].V * t + v[x].A) * PI / 180.0);

  double l=0, r=1e15;
  rep(i,100){
    double m = (l+r)/2;

    double tx = v[y].X + v[y].R * cos((v[y].V * (t+m) + v[y].A) * PI / 180.0);
    double ty = v[y].Y + v[y].R * sin((v[y].V * (t+m) + v[y].A) * PI / 180.0);

    double dist = sqrt((tx-posx)*(tx-posx) + (ty-posy)*(ty-posy));
    if(m * W < dist) l = m;
    else r = m;
  }
  return (l+r)/2;
}


int main(){
  cin >> N >> W;
  rep(i,N){
    ST st;
    cin >> st.X >> st.Y >> st.R >> st.V >> st.A;
    v.push_back(st);
  }
  v.push_back((ST){0,0,0,0,0});
  
  rep(i,1<<13) rep(j,13) dp[i][j] = 1e300;

  dp[1<<N][N] = 0;
  N++;
  
  rep(i,1<<N){
    rep(j,N){
      rep(k,N-1){
        if((i>>k)&1) continue;
        if(dp[i][j] > 1e299) continue;
        //cerr << i << " " << j << " " << k << " " << dp[i][j] << " " << calc(dp[i][j],j,k) << endl;
        dp[i|(1<<k)][k] = min(dp[i|(1<<k)][k], dp[i][j] + calc(dp[i][j],j,k));
      }
    }
  }

  double ret = 1e300;
  rep(i,N-1){
    ret = min(ret, dp[(1<<N)-1][i]);
  }

  printf("%.12lf\n", ret);
  
  return 0;
}
0