Submission #823220

#TimeUsernameProblemLanguageResultExecution timeMemory
823220t6twotwoTortoise (CEOI21_tortoise)C++17
18 / 100
89 ms2092 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector<int> A(N); for (int i = 0; i < N; i++) { cin >> A[i]; } vector<int> L(N, -1), R(N, N); for (int i = 0; i < N; i++) { if (A[i] == -1) { L[i] = i; } else if (i) { L[i] = L[i - 1]; } int j = N - i - 1; if (A[j] == -1) { R[j] = j; } else if (i) { R[j] = R[j + 1]; } } int ans = 0; vector dp(2 * N + 1, vector<int>(N, -1e9)); dp[0][0] = 0; for (int i = 0; i < N; i++) { if (A[i] != 1) { continue; } auto pd = dp; for (int j = 0; j <= 2 * N; j++) { for (int k = 0; k < N; k++) { if (j + abs(i - k) > 2 * i) { continue; } ans = max(ans, pd[j][k] + 1); if (L[i] != -1) { int p = j + abs(i - k) + i - L[i]; if (p <= 2 * N) { dp[p][L[i]] = max(dp[p][L[i]], pd[j][k] + 1); } } if (R[i] != N) { int p = j + abs(i - k) + R[i] - i; if (p <= 2 * N) { dp[p][R[i]] = max(dp[p][R[i]], pd[j][k] + 1); } } } } } ans = -ans; for (int i = 0; i < N; i++) { if (A[i] != -1) { ans += A[i]; } } cout << ans << "\n"; return 6/22; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...