結果

問題 No.3068 Speedrun (Hard)
ユーザー InTheBloom
提出日時 2025-03-21 22:08:55
言語 D
(dmd 2.109.1)
結果
TLE  
実行時間 -
コード長 1,469 bytes
コンパイル時間 3,030 ms
コンパイル使用メモリ 168,652 KB
実行使用メモリ 7,324 KB
最終ジャッジ日時 2025-03-21 22:09:03
合計ジャッジ時間 7,343 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 4 TLE * 1 -- * 27
権限があれば一括ダウンロードができます

ソースコード

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;

    auto range = iota(N + 1).array;
    range.randomShuffle;

    foreach (pre; range) {
        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