結果

問題 No.3049 Contest Coordinator
コンテスト
ユーザー suisen
提出日時 2025-01-18 15:57:38
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,482 bytes
コンパイル時間 1,151 ms
コンパイル使用メモリ 85,888 KB
実行使用メモリ 17,696 KB
最終ジャッジ日時 2025-01-18 15:59:13
合計ジャッジ時間 83,794 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32 TLE * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

// TLE

#include <algorithm>
#include <deque>
#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, t, x, y;
    std::cin >> n >> t >> x >> y;

    std::vector<int> d(n);
    for (auto& e : d) std::cin >> e;
    std::sort(d.begin(), d.end());

    std::vector<int> min_cost(n + 1, n);
    min_cost[1] = 0;

    std::vector<int> pd(n, n);
    for (int i = 0; i < n; ++i) {
        pd[i] = 0;
    }
    for (int k = 2; k <= n; ++k) {
        std::vector<int> dp(n, n);

        int min_pref = n;
        std::deque<std::pair<int, int>> min_suff;
        int m = 0;
        for (int i = 0; i < n; ++i) {
            while (d[m] < d[i] - t) {
                min_pref = std::min(min_pref, pd[m]);
                ++m;
            }
            while (min_suff.size() and min_suff.front().second < m) {
                min_suff.pop_front();
            }
            dp[i] = std::min(dp[i], min_pref + 1);
            if (min_suff.size()) dp[i] = std::min(dp[i], min_suff.front().first);
            while (min_suff.size() and min_suff.back().first >= pd[i]) {
                min_suff.pop_back();
            }
            min_suff.emplace_back(pd[i], i);

            min_cost[k] = std::min(min_cost[k], dp[i]);
        }
        pd.swap(dp);
    }
    for (int k = 1; k <= n; ++k) {
        if (k != 1) std::cout << ' ';
        std::cout << 1LL * std::min(x, y) * min_cost[k];
    }
    std::cout << '\n';
}
0