結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー yosupotyosupot
提出日時 2016-11-18 22:57:01
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,630 ms / 2,000 ms
コード長 1,329 bytes
コンパイル時間 621 ms
コンパイル使用メモリ 73,464 KB
実行使用メモリ 17,432 KB
最終ジャッジ日時 2023-09-02 12:50:08
合計ジャッジ時間 23,999 ms
ジャッジサーバーID
(参考情報)
judge13 / judge16
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,376 KB
testcase_01 AC 1 ms
4,376 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1 ms
4,376 KB
testcase_04 AC 3 ms
4,376 KB
testcase_05 AC 4 ms
4,376 KB
testcase_06 AC 6 ms
4,376 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 3 ms
4,380 KB
testcase_09 AC 4 ms
4,376 KB
testcase_10 AC 2 ms
4,380 KB
testcase_11 AC 4 ms
4,380 KB
testcase_12 AC 4 ms
4,376 KB
testcase_13 AC 149 ms
5,128 KB
testcase_14 AC 147 ms
5,164 KB
testcase_15 AC 450 ms
8,696 KB
testcase_16 AC 726 ms
13,016 KB
testcase_17 AC 970 ms
13,396 KB
testcase_18 AC 86 ms
4,528 KB
testcase_19 AC 1,611 ms
15,844 KB
testcase_20 AC 404 ms
7,560 KB
testcase_21 AC 1,389 ms
15,964 KB
testcase_22 AC 382 ms
7,812 KB
testcase_23 AC 1,239 ms
16,096 KB
testcase_24 AC 224 ms
6,184 KB
testcase_25 AC 1,446 ms
15,916 KB
testcase_26 AC 99 ms
4,392 KB
testcase_27 AC 650 ms
13,300 KB
testcase_28 AC 1,065 ms
11,772 KB
testcase_29 AC 373 ms
7,940 KB
testcase_30 AC 1,294 ms
16,108 KB
testcase_31 AC 106 ms
5,012 KB
testcase_32 AC 121 ms
5,228 KB
testcase_33 AC 1,308 ms
17,268 KB
testcase_34 AC 1,366 ms
17,272 KB
testcase_35 AC 1,296 ms
17,244 KB
testcase_36 AC 1,600 ms
17,012 KB
testcase_37 AC 1,630 ms
17,204 KB
testcase_38 AC 1,275 ms
17,432 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <iostream>
#include <vector>
#include <set>
#include <cassert>
#include <tuple>

using namespace std;
using ll = long long;

using S = pair<bool, ll>;
using P = pair<ll, ll>;

int n; ll k;
vector<P> task;

S calc(ll md) {
    multiset<ll> mi;
    vector<ll> dp(n, 0);
    ll la = -1, l = 0;
    mi.insert(0);
    for (int i = 0; i < n; i++) {
        ll t, d;
        tie(t, d) = task[i];
        while (l < i && t-task[l].first >= k) {
            if (la <= l && dp[l] >= 0) mi.insert(dp[l]);
            l++;
        }
        if (!mi.size()) {
            if (md < d) return S(false, -1);
            dp[i] = -1;
        } else {
            dp[i] = (*mi.rbegin()) + d;            
        }
        if (md < d) {
            // must use
            mi.clear();
            la = i;
        }
    }
    return S(true, *mi.rbegin());
}

int main() {
    cin >> n >> k;
    ll sm = 0;
    for (int i = 0; i < n; i++) {
        ll t, d;
        cin >> t >> d;
        task.push_back(P(t, d));
        sm += d;
    }
    task.push_back(P(1LL<<50, 0)); n++;
    ll l = -1, r = (1LL<<40);
    while (r-l > 1) {
        ll md = (l+r)/2;
        if (!calc(md).first) {
            l = md;
        } else {
            r = md;
        }
    }
    auto s = calc(r);
    cout << r << endl << sm-s.second << endl;
    return 0;
}
0