結果

問題 No.1413 Dynamic Sushi
ユーザー merom686merom686
提出日時 2021-02-28 22:39:36
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 200 ms / 4,000 ms
コード長 2,084 bytes
コンパイル時間 834 ms
コンパイル使用メモリ 97,960 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-04-12 10:56:41
合計ジャッジ時間 5,536 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 102 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 150 ms
6,940 KB
testcase_05 AC 171 ms
6,940 KB
testcase_06 AC 178 ms
6,940 KB
testcase_07 AC 188 ms
6,944 KB
testcase_08 AC 184 ms
6,940 KB
testcase_09 AC 182 ms
6,940 KB
testcase_10 AC 168 ms
6,944 KB
testcase_11 AC 179 ms
6,940 KB
testcase_12 AC 198 ms
6,944 KB
testcase_13 AC 198 ms
6,944 KB
testcase_14 AC 195 ms
6,944 KB
testcase_15 AC 195 ms
6,940 KB
testcase_16 AC 183 ms
6,940 KB
testcase_17 AC 192 ms
6,940 KB
testcase_18 AC 200 ms
6,940 KB
testcase_19 AC 178 ms
6,940 KB
testcase_20 AC 78 ms
6,940 KB
testcase_21 AC 2 ms
6,940 KB
testcase_22 AC 171 ms
6,940 KB
testcase_23 AC 196 ms
6,940 KB
testcase_24 AC 196 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
using ll = long long;

template <class T>
void chmin(T &a, T b) {
    if (b < a) a = b;
}

constexpr double INF = 1e+9;
constexpr int N = 12;
double dp[1 << N][N];

struct P {
    int x, y, r;
    double v, a;
};

int main() {
    int n, w;
    cin >> n >> w;

    P p[N];
    for (int i = 0; i < n; i++) {
        int x, y, r, v, a;
        cin >> x >> y >> r >> v >> a;

        double t = acos(-1) / 180;
        p[i] = { x, y, r, v * t, a * t };
    }

    auto f = [&](int i, double t) {
        double z = p[i].v * t + p[i].a;
        return pair<double, double>(p[i].x + p[i].r * cos(z), p[i].y + p[i].r * sin(z));
    };

    auto r2 = [](double x, double y) {
        return x * x + y * y;
    };

    auto g = [&](double x, double y, double t, int i) {
        double t0 = 0, t1 = (hypot(x - p[i].x, y - p[i].y) + p[i].r) / w, t2;
        while (t1 - t0 > 1e-8 * max(1.0, t0)) {
            t2 = (t0 + t1) * 0.5;
            auto [x1, y1] = f(i, t + t2);
            (r2(x - x1, y - y1) > r2(t2 * w, 0) ? t0 : t1) = t2;
        }
        return t + (t0 + t1) * 0.5;
    };

    for (int k = 0; k < 1 << n; k++) {
        for (int i = 0; i < n; i++) {
            dp[k][i] = INF;
        }
    }
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = g(0, 0, 0, i);
    }

    for (int k = 0; k < 1 << n; k++) {
        for (int i = 0; i < n; i++) {
            if (k & 1 << i) {
                double s = dp[k][i];
                int l = k ^ 1 << i;
                for (int j = 0; j < n; j++) {
                    if (l & 1 << j) {
                        double t = dp[l][j];
                        auto [x, y] = f(j, t);
                        chmin(s, g(x, y, t, i));
                    }
                }
                dp[k][i] = s;
            }
        }
    }

    double r = INF;
    for (int i = 0; i < n; i++) {
        chmin(r, dp[(1 << n) - 1][i]);
    }
    printf("%.12f\n", r);

    return 0;
}
0