結果

問題 No.1413 Dynamic Sushi
ユーザー どららどらら
提出日時 2021-02-28 22:11:31
言語 C++14
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 982 ms
5,248 KB
testcase_02 AC 3 ms
5,248 KB
testcase_03 AC 2 ms
5,248 KB
testcase_04 AC 782 ms
5,248 KB
testcase_05 AC 1,044 ms
5,248 KB
testcase_06 AC 1,060 ms
5,248 KB
testcase_07 AC 1,041 ms
5,248 KB
testcase_08 AC 1,008 ms
5,248 KB
testcase_09 AC 1,100 ms
5,248 KB
testcase_10 AC 1,081 ms
5,248 KB
testcase_11 AC 1,065 ms
5,248 KB
testcase_12 AC 1,049 ms
5,248 KB
testcase_13 AC 944 ms
5,248 KB
testcase_14 AC 1,103 ms
5,248 KB
testcase_15 AC 1,133 ms
5,248 KB
testcase_16 AC 1,081 ms
5,248 KB
testcase_17 AC 1,088 ms
5,248 KB
testcase_18 AC 1,082 ms
5,248 KB
testcase_19 AC 1,086 ms
5,248 KB
testcase_20 AC 441 ms
5,248 KB
testcase_21 AC 6 ms
5,248 KB
testcase_22 AC 1,034 ms
5,248 KB
testcase_23 AC 1,042 ms
5,248 KB
testcase_24 AC 1,034 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

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