結果
問題 | No.1368 サイクルの中に眠る門松列 |
ユーザー | Example0911 |
提出日時 | 2021-01-29 21:54:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,197 bytes |
コンパイル時間 | 2,183 ms |
コンパイル使用メモリ | 210,436 KB |
実行使用メモリ | 12,780 KB |
最終ジャッジ日時 | 2024-06-27 08:07:37 |
合計ジャッジ時間 | 3,600 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 2 ms
5,376 KB |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | AC | 41 ms
12,672 KB |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
ソースコード
#include "bits/stdc++.h"using namespace std;using ll = long long;using P = pair<ll, ll>;const ll INF = (1LL << 61);ll mod = 998244353;bool f(vector<ll>a) {if (a[0] == a[1] || a[1] == a[2] || a[0] == a[2])return false;if ((a[1] > a[0] && a[1] > a[2]) || (a[1] < a[0] && a[1] < a[2]))return true;else return false;}/* RMQ:[0,n-1] について、区間ごとの最小値を管理する構造体update(i,x): i 番目の要素を x に更新。O(log(n))query(a,b): [a,b) での最小の要素を取得。O(log(n))*/template <typename T>struct RMQ {const T INF = numeric_limits<T>::max();int n; // 葉の数vector<T> dat; // 完全二分木の配列RMQ(int n_) : n(), dat(n_ * 4, INF) { // 葉の数は 2^x の形int x = 1;while (n_ > x) {x *= 2;}n = x;}void update(int i, T x) {i += n - 1;dat[i] = x;while (i > 0) {i = (i - 1) / 2; // parentdat[i] = min(dat[i * 2 + 1], dat[i * 2 + 2]);}}// the minimum element of [a,b)T query(int a, int b) { return query_sub(a, b, 0, 0, n); }T query_sub(int a, int b, int k, int l, int r) {if (r <= a || b <= l) {return 0;}else if (a <= l && r <= b) {return dat[k];}else {T vl = query_sub(a, b, k * 2 + 1, l, (l + r) / 2);T vr = query_sub(a, b, k * 2 + 2, (l + r) / 2, r);return min(vl, vr);}}};signed main() {ios::sync_with_stdio(false);cin.tie(0);int T; cin >> T;for (int _ = 0; _ < T; _++) {int N; cin >> N;vector<ll>A(N); for (int i = 0; i < N; i++)cin >> A[i];vector<ll>dp(N+1);vector<bool>ok(N);ll ans = 0;RMQ<ll>seg(N + 1);for (int i = 0; i <= N; i++)seg.update(i, 0);for (int i = 0; i < N; i++) {vector<ll>a = { A[i%N], A[(i + 1) % N],A[(i + 2) % N] };if (f(a)) {if (i == N - 1) {dp[i + 1] = max(dp[i + 1], -seg.query(2, max(2, i - 2)) + A[i]);}else if (i == N - 2) {dp[i + 1] = max(dp[i + 1], -seg.query(1, max(1, i - 2)) + A[i]);}else {dp[i + 1] = max(dp[i + 1], -seg.query(0, max(0, i - 2)) + A[i]);}seg.update(i + 1, -dp[i + 1]);}}for (int i = 0; i <= N; i++)ans = max(ans, dp[i]);cout << ans << endl;}return 0;}