結果

問題 No.3068 Speedrun (Hard)
ユーザー InTheBloom
提出日時 2025-03-21 22:05:42
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 1,412 bytes
コンパイル時間 2,437 ms
コンパイル使用メモリ 165,616 KB
実行使用メモリ 14,772 KB
最終ジャッジ日時 2025-03-21 22:05:50
合計ジャッジ時間 6,133 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 2 TLE * 1 -- * 29
権限があれば一括ダウンロードができます

ソースコード

diff # 

import std;

void main () {
    auto A = readln.split.to!(int[]);
    auto T = readln.split.to!(int[]);

    int N = A[$ - 1];

    // 解いた数を持つdpだと状態数デカすぎるから厳しい
    // 半分全列挙できそう？
    // -> 一気に列挙すると死ぬので消費した問題数ごとに分けて探索する。

    long f (int x, int y) {
        return x * 4L * 10L ^^ 8 + y;
    }

    Tuple!(int, int)[long] mp;

    foreach (pre; 0 .. N + 1) {
        mp.clear;
        foreach (i; 0 .. A[0] + 1) {
            int j = pre - i;
            if (A[1] < j) continue;
            if (j < 0) break;

            int time = i * T[0] + j * T[1];
            mp[f(time, pre)] = tuple(i, j);
        }

        int aft = N - pre;
        foreach (i; 0 .. A[2] + 1) {
            int j = aft - i;
            if (A[3] < j) continue;
            if (j < 0) break;

            int rem_time = T[$ - 1] - (i * T[2] + j * T[3]);
            int rem_count = N - (i + j);

            if (f(rem_time, rem_count) in mp) {
                auto v = mp[f(rem_time, rem_count)];
                writeln(v[0], " ", v[1], " ", i, " ", j);
                return;
            }
        }
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}
0