結果
問題 | No.448 ゆきこーだーの雨と雪 (3) |
ユーザー |
![]() |
提出日時 | 2016-11-18 23:45:06 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 153 ms / 2,000 ms |
コード長 | 1,975 bytes |
コンパイル時間 | 852 ms |
コンパイル使用メモリ | 89,628 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-11 19:31:30 |
合計ジャッジ時間 | 4,676 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <algorithm> #include <utility> #include <functional> #include <cstring> #include <queue> #include <stack> #include <math.h> #include <iterator> #include <vector> #include <string> #include <set> #include <math.h> #include <iostream> #include<map> #include <iomanip> #include <stdlib.h> #include <list> #include <typeinfo> #include <list> #include <set> using namespace std; #define MAX_MOD 1000000007 #define REP(i,n) for(long long i = 0;i < n;++i) #define LONGINF 1000000000000000000 long long pass[300000] = {}; vector<pair<int, int>> listing; int n, k; bool can_do(long long border) { int ans = -1*k; for (int i = 0;i < n;++i) { if (listing[i].second >= border) { if (listing[i].first - ans < k) { return false; } else { ans = listing[i].first; } } } return true; } int main() { cin >> n >> k; REP(i, n) { int a, b; cin >> a >> b; listing.push_back(make_pair(a, b)); } long long top = 2000000000; long long bot = 0; while (top - bot > 1) { long long mid = (top + bot) / 2; if (can_do(mid)) { top = mid; } else { bot = mid; } } int setting = 0; if (can_do(bot)) { setting = bot; } else { setting = top; } listing.insert(listing.begin(), make_pair(-1 * k, 0)); int now_reading = 0; for (int i = 1;i < n+1;++i) { while (now_reading + 1 != i) { if (listing[i].first - listing[now_reading + 1].first < k) break; now_reading++; } if (listing[i].first - listing[now_reading].first >= k) { pass[i] = max(pass[now_reading] + listing[i].second, pass[i - 1]); if (listing[i].second >= setting) { now_reading = i; } } else { pass[i] = pass[i - 1]; } } long long max_ans = 0; long long ans = 0; for (int i = 0;i < n + 1;++i) { ans += listing[i].second; if(listing[i].second < setting) max_ans = max(max_ans,(long long)listing[i].second); } cout << max_ans << endl; cout << ans - pass[n] << endl; return 0; }