結果
問題 |
No.2854 -1 Subsequence
|
ユーザー |
|
提出日時 | 2024-08-24 12:22:43 |
言語 | C++17(clang) (17.0.6 + boost 1.87.0) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 598 bytes |
コンパイル時間 | 1,082 ms |
コンパイル使用メモリ | 131,592 KB |
実行使用メモリ | 14,896 KB |
最終ジャッジ日時 | 2024-08-24 14:32:24 |
合計ジャッジ時間 | 4,704 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 WA * 10 |
ソースコード
#include <iostream> #include <cassert> #include <vector> #include <algorithm> using namespace std; using ll = long long; constexpr ll INF = 1LL << 62; int main() { int n; cin >> n; vector<int> a(n); for (int i = 0; i < n; ++i) cin >> a[i]; assert(1 <= n && n <= 200000); for (int i = 0; i < n; ++i) assert(abs(a[i]) <= 1000'000'000); vector<vector<ll>> dp(n+1, vector<ll>(2, -INF)); dp[0][0] = 0; for (int i = 0; i < n; ++i) { dp[i+1][1] = max({dp[i][1], dp[i][0] - a[i], -(ll)a[i]}); dp[i+1][0] = max({dp[i][0], dp[i][1] + a[i]}); } cout << max(dp[n][0], dp[n][1]) << endl; }