結果
問題 |
No.448 ゆきこーだーの雨と雪 (3)
|
ユーザー |
|
提出日時 | 2023-03-26 18:58:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,163 bytes |
コンパイル時間 | 4,394 ms |
コンパイル使用メモリ | 234,516 KB |
実行使用メモリ | 17,152 KB |
最終ジャッジ日時 | 2024-09-19 09:57:06 |
合計ジャッジ時間 | 8,585 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 24 WA * 11 |
ソースコード
#include <bits/stdc++.h> #include <atcoder/all> using namespace std; using ll = long long; using S = pair<int, ll>; using F = int; //単位元 S e(){return make_pair(1 << 30, 1 << 30);} //演算 S op(S l,S r){return min(l, r);} //xにfを作用させた時の値の変化 S mapping(F f,S x){return make_pair(max(x.first, f), x.second);} //gを演算した後にfを演算させると演算子はどうなるか F composition(F f, F g){return max(f, g);} //作用させても変化させないもの F id(){return 0;} int main(){ ios::sync_with_stdio(false); cin.tie(0); int N, K; cin >> N >> K; vector<int> T(N + 1), D(N + 1); for(int i = 1; i <= N; i++) cin >> T[i] >> D[i]; T[0] = -(1 << 30); atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg(N + 1); seg.set(0, {0, 0}); ll s = accumulate(D.begin(), D.end(), 0ll); for(int i = 1, r = 0; i <= N; i++){ while(T[r] + K <= T[i]) r++; auto p = seg.prod(0, r); p.second -= D[i]; seg.set(i, p); seg.apply(0, i, D[i]); } auto p = seg.all_prod(); cout << p.first << '\n'; cout << s + p.second << '\n'; }