結果
問題 | No.844 split game |
ユーザー |
|
提出日時 | 2019-06-28 22:29:42 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 120 ms / 2,000 ms |
コード長 | 962 bytes |
コンパイル時間 | 805 ms |
コンパイル使用メモリ | 78,360 KB |
実行使用メモリ | 9,856 KB |
最終ジャッジ日時 | 2024-07-02 04:55:45 |
合計ジャッジ時間 | 4,817 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 56 |
ソースコード
#include<iostream>#include<vector>#include<algorithm>using namespace std;typedef long long ll;const ll INF = 1ll<<60;int main(){int n, m, a;cin >> n >> m >> a;vector<pair<int,int>> vp[n+1];while(m-- > 0){int l, r, p;cin >> l >> r >> p;vp[l-1].push_back({r, p});}vector<vector<ll>> dp(2, vector<ll>(n+1, -INF));dp[0][0] = dp[1][0] = 0;for(int i = 0; i < n; i++){if(i){dp[0][i] = max({dp[0][i-1],dp[0][i],dp[1][i-1]});dp[1][i] = max(dp[1][i], dp[0][i]-a);}for(pair<int,int> p : vp[i]){int r = p.first, val = p.second;int tmp = (r == n ? 0 : a);dp[1][r] = max({dp[1][r], dp[1][i]+val-tmp, dp[0][i]-a+val-tmp});}}// dirty :(ll ans = 0;for(int i = 0; i < 2; i++) for(int j = 0; j <= n; j++) ans = max(ans,dp[i][j]);cout << ans << endl;return 0;}