結果

問題 No.448 ゆきこーだーの雨と雪 (3)
ユーザー yosupotyosupot
提出日時 2016-11-18 22:57:01
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 1,331 ms / 2,000 ms
コード長 1,329 bytes
コンパイル時間 610 ms
コンパイル使用メモリ 74,104 KB
実行使用メモリ 17,324 KB
最終ジャッジ日時 2024-06-11 19:30:16
合計ジャッジ時間 20,746 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

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