結果
問題 | No.2196 Pair Bonus |
ユーザー |
![]() |
提出日時 | 2023-01-20 21:56:35 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 258 ms / 2,000 ms |
コード長 | 3,253 bytes |
コンパイル時間 | 4,083 ms |
コンパイル使用メモリ | 235,472 KB |
実行使用メモリ | 18,816 KB |
最終ジャッジ日時 | 2024-06-23 09:55:09 |
合計ジャッジ時間 | 6,165 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 15 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;// 1次元累積和 O(N)template <typename T>vector<T> ruiseki_1d(const vector<T> &s){int n = (int)s.size();vector<T> ret(n);ret[0] = s[0];for(int i = 1; i < n; i++) ret[i] = ret[i - 1] + s[i];return ret;}// 1次元累積和・区間和計算 O(1)// 累積和をとった1次元配列を用いて[x1, x2]区間の和を計算するtemplate <typename T, typename U>T ruiseki_1d_calc(const vector<T> &s, const U x1, const U x2){assert(x1 <= x2);T ret = s[x2];if(x1 != 0) ret -= s[x1 - 1];return ret;}// 2次元累積和 O(HW)template <typename T>vector<vector<T>> ruiseki_2d(const vector<vector<T>> &s){int h = (int)s.size();int w = (int)s[0].size();vector<vector<T>> ret(h, vector<T>(w));ret[0][0] = s[0][0];for(int i = 1; i < w; i++) ret[0][i] = ret[0][i - 1] + s[0][i];for(int i = 1; i < h; i++) ret[i][0] = ret[i - 1][0] + s[i][0];for(int i = 1; i < h; i++) for(int j = 1; j < w; j++) ret[i][j] = ret[i - 1][j] + ret[i][j - 1] - ret[i - 1][j - 1] + s[i][j];return ret;}// 2次元累積和・区間和計算 O(1)// 累積和をとった2次元配列を用いて[x1, x2] × [y1, y2]区間の和を計算するtemplate <typename T, typename U>T ruiseki_2d_calc(const vector<vector<T>> &s, const U x1, const U y1, const U x2, const U y2){assert(x1 <= x2 && y1 <= y2);T ret = s[x2][y2];if(y1 != 0) ret -= s[x2][y1 - 1];if(x1 != 0) ret -= s[x1 - 1][y2];if(x1 != 0 && y1 != 0) ret += s[x1 - 1][y1 - 1];return ret;}// 最大公約数 O(log(min(a, b)))template <typename T>T gcd(T a, T b){if(a % b == 0) return b;else return gcd(b, a % b);}// ランレングス圧縮(文字列) O(|S|)vector<pair<char, int>> rle_string(const string &s){vector<pair<char, int>> ret;int cnt = 1;for(int i = 0; i < (int)s.size() - 1; i++){if(s[i] != s[i + 1]){ret.push_back({s[i], cnt});cnt = 0;}cnt++;}ret.push_back({s.back(), cnt});return ret;}// ランレングス圧縮(配列) O(N)template <typename T>vector<pair<T, int>> rle_vector(const vector<T> &v){vector<pair<T, int>> ret;int cnt = 1;for(int i = 0; i < (int)v.size() - 1; i++){if(v[i] != v[i + 1]){ret.push_back({v[i], cnt});cnt = 0;}cnt++;}ret.push_back({v.back(), cnt});return ret;}int main(){int64_t n;cin >> n;vector<int64_t> a(2 * n);vector<int64_t> b(2 * n);vector<int64_t> x(n);vector<int64_t> y(n);for(int64_t i = 0; i < 2 * n; i++) cin >> a[i];for(int64_t i = 0; i < 2 * n; i++) cin >> b[i];for(int64_t i = 0; i < n; i++) cin >> x[i];for(int64_t i = 0; i < n; i++) cin >> y[i];vector<vector<int64_t>> dp(2 * n, vector<int64_t>(2));dp[0][0] = a[0];dp[0][1] = b[0];for(int64_t i = 1; i < 2 * n; i++){if(i % 2 == 1){dp[i][0] = max(dp[i - 1][0] + a[i] + x[i / 2], dp[i - 1][1] + a[i] + y[i / 2]);dp[i][1] = max(dp[i - 1][0] + b[i] + y[i / 2], dp[i - 1][1] + b[i] + x[i / 2]);}else{dp[i][0] = max(dp[i - 1][0] + a[i], dp[i - 1][1] + a[i]);dp[i][1] = max(dp[i - 1][0] + b[i], dp[i - 1][1] + b[i]);}}cout << max(dp[2 * n - 1][0], dp[2 * n - 1][1]) << endl;return 0;}