結果

問題 No.1413 Dynamic Sushi
ユーザー どららどらら
提出日時 2021-02-28 22:11:31
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 1,271 ms / 4,000 ms
コード長 1,754 bytes
コンパイル時間 3,822 ms
コンパイル使用メモリ 230,828 KB
実行使用メモリ 4,864 KB
最終ジャッジ日時 2023-07-26 05:21:53
合計ジャッジ時間 29,680 ms
ジャッジサーバーID
(参考情報)
judge13 / judge12
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
4,612 KB
testcase_01 AC 1,155 ms
4,692 KB
testcase_02 AC 3 ms
4,752 KB
testcase_03 AC 2 ms
4,696 KB
testcase_04 AC 881 ms
4,668 KB
testcase_05 AC 1,227 ms
4,612 KB
testcase_06 AC 1,243 ms
4,736 KB
testcase_07 AC 1,220 ms
4,612 KB
testcase_08 AC 1,184 ms
4,628 KB
testcase_09 AC 1,264 ms
4,748 KB
testcase_10 AC 1,231 ms
4,740 KB
testcase_11 AC 1,232 ms
4,860 KB
testcase_12 AC 1,210 ms
4,640 KB
testcase_13 AC 1,072 ms
4,848 KB
testcase_14 AC 1,271 ms
4,628 KB
testcase_15 AC 1,255 ms
4,864 KB
testcase_16 AC 1,268 ms
4,800 KB
testcase_17 AC 1,264 ms
4,720 KB
testcase_18 AC 1,257 ms
4,844 KB
testcase_19 AC 1,254 ms
4,624 KB
testcase_20 AC 520 ms
4,632 KB
testcase_21 AC 7 ms
4,644 KB
testcase_22 AC 1,216 ms
4,724 KB
testcase_23 AC 1,193 ms
4,740 KB
testcase_24 AC 1,215 ms
4,632 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