結果
問題 | No.2854 -1 Subsequence |
ユーザー |
|
提出日時 | 2024-08-25 13:55:21 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 123 ms / 2,000 ms |
コード長 | 593 bytes |
コンパイル時間 | 3,421 ms |
コンパイル使用メモリ | 279,520 KB |
実行使用メモリ | 15,928 KB |
最終ジャッジ日時 | 2024-08-25 13:55:37 |
合計ジャッジ時間 | 6,969 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 40 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;constexpr ll INF = 1LL<<60;int main(){int N;cin >> N;vector<ll> A(N);for(int i=0; i<N; i++){cin >> A[i];}vector dp(N+1, vector<ll>(2, -INF));for(int i=0; i<N; i++){dp[i+1][1] = max(dp[i+1][1], -A[i]);if(dp[i][0]!=-INF){dp[i+1][0] = max(dp[i+1][0], dp[i][0]);dp[i+1][1] = max(dp[i+1][1], dp[i][0] - A[i]);}if(dp[i][1]!=-INF){dp[i+1][1] = max(dp[i+1][1], dp[i][1]);dp[i+1][0] = max(dp[i+1][0], dp[i][1] + A[i]);}}cout << max(dp[N][0], dp[N][1]) << endl;return 0;}