結果
問題 |
No.1536 仕切り直し
|
ユーザー |
![]() |
提出日時 | 2021-06-06 18:52:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,011 bytes |
コンパイル時間 | 2,164 ms |
コンパイル使用メモリ | 195,392 KB |
最終ジャッジ日時 | 2025-01-22 04:07:58 |
ジャッジサーバーID (参考情報) |
judge5 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 10 |
ソースコード
#include "bits/stdc++.h" #define int long long using namespace std; using ll = long long; using P = pair<ll, ll>; const ll INF = (1LL << 61); ll mod = 998244353; // dp[i][j] := i番目の隙間まで見て, j個隙間にボールを入れたときの得点の最大値 int dp[2010][2010]; int prev_j[2010][2010]; signed main() { ios::sync_with_stdio(false); cin.tie(0); int N, M; cin >> N >> M; vector<int>A(N); for (int i = 0; i < N; i++)cin >> A[i]; for (int i = 0; i < 2010; i++)for (int j = 0; j < 2010; j++)dp[i][j] = -INF; dp[0][0] = dp[0][1] = 0; for (int i = 0; i < N; i++) { for (int j = 0; j <= M; j++) { if (j % 2 == 1) { A[i] *= -1; } if (j < M) { if (dp[i + 1][j + 1] < dp[i][j] + A[i]) { dp[i + 1][j + 1] = dp[i][j] + A[i]; prev_j[i + 1][j + 1] = j; } } if (dp[i + 1][j] < dp[i][j] + A[i]) { dp[i + 1][j] = dp[i][j] + A[i]; prev_j[i + 1][j] = j; } if (j % 2 == 1) { A[i] *= -1; } } } cout << dp[N][M] << endl; return 0; }