結果
問題 |
No.2542 Yokan for Two
|
ユーザー |
|
提出日時 | 2023-11-25 11:38:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 1,448 bytes |
コンパイル時間 | 2,302 ms |
コンパイル使用メモリ | 201,064 KB |
最終ジャッジ日時 | 2025-02-18 00:47:56 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 2 MLE * 2 -- * 36 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main() { int L, N; cin >> L >> N; vector<int> X(N + 2); X[0] = 0; X[N + 1] = L; for (int i = 0; i < N; i++) { int x; cin >> x; X[i + 1] = x; } vector<int> A; for (int i = 0; i < N + 1; i++) { A.push_back(X[i + 1] - X[i]); } N = A.size(); int M = 2 * L + 10; vector<vector<vector<int>>> dp(N + 1, vector<vector<int>>(M, vector<int>(2))); dp[0][L][0] = 1; for (int i = 0; i < N; i++) { int a = A[i]; for (int j = 0; j < M; j++) { for (int k = 0; k < 2; k++) { if (dp[i][j][k] == 0) { continue; } if (k == 0) { dp[i + 1][j + a][k] = 1; if (i > 0) { dp[i + 1][j - a][1 - k] = 1; } } else { dp[i + 1][j - a][k] = 1; if (i > 0) { dp[i + 1][j + a][1 - k] = 1; } } } } } int ans = pow(10, 9); for (int j = 0; j < M; j++) { if (dp[N][j][1] == 1) { ans = min(ans, abs(j - L)); } } cout << ans << endl; }