結果
| 問題 |
No.3289 Make More Happy Connection
|
| コンテスト | |
| ユーザー |
Kyutatsu
|
| 提出日時 | 2025-10-03 23:04:50 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 339 ms / 2,000 ms |
| コード長 | 1,376 bytes |
| コンパイル時間 | 5,373 ms |
| コンパイル使用メモリ | 334,996 KB |
| 実行使用メモリ | 24,308 KB |
| 最終ジャッジ日時 | 2025-10-03 23:05:02 |
| 合計ジャッジ時間 | 11,673 ms |
|
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 24 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
int main() {
// DP[Nセット目まで見た][前回先置き採用はL:0, R:1] := デカいスコア
int N; cin >> N;
vector<P> xy(N);
ll ss = 0;
for (int i=0;i<N;i++) {
cin >> xy[i].first >> xy[i].second;
if (xy[i].first == xy[i].second) ss += xy[i].first;
}
if (N==1) {
if (xy[0].first == xy[0].second)
cout << xy[0].first << endl;
else
cout << 0 << endl;
return 0;
}
vector DP(N+1, vector<ll>(2, 0));
for (int i=0;i<N-1;i++) {
// l->l
ll mx_ll = DP[i][0] +
((xy[i].second == xy[i+1].first) ? xy[i+1].first : 0);
DP[i+1][0] = max(DP[i+1][0], mx_ll);
// l->r
ll mx_lr = DP[i][0] +
((xy[i].second == xy[i+1].second) ? xy[i+1].second : 0);
DP[i+1][1] = max(DP[i+1][1], mx_lr);
// r->l
ll mx_rl = DP[i][1] +
((xy[i].first == xy[i+1].first) ? xy[i+1].first : 0);
DP[i+1][0] = max(DP[i+1][0], mx_rl);
// r->r
ll mx_rr = DP[i][1] +
((xy[i].first == xy[i+1].second) ? xy[i+1].second : 0);
DP[i+1][1] = max(DP[i+1][1], mx_rr);
}
cout << max(DP[N-1][0], DP[N-1][1]) + ss << endl;
return 0;
}
Kyutatsu