Submission #868276

#TimeUsernameProblemLanguageResultExecution timeMemory
868276hungntHolding (COCI20_holding)C++14
88 / 110
19 ms110428 KiB
#include <bits/stdc++.h> using namespace std; const int N = 105; int n, L, R, k, s; int a[102]; int dp[N][2505][N], Left[N][2505], Right[N][2505]; void MAX(int &A, int B) { if(A < B) A = B; } void sub2(int L) { int ans = 0; for(int i = L; i <= R; i++) for(int j = L - 1; j > 0; j--) for(int c = 1; c <= k; c++) { MAX(dp[i][c][j], dp[i - 1][c][j]); MAX(dp[i][c][j], dp[i][c][j + 1]); if(c - i + j >= 0) { MAX(dp[i][c][j], dp[i - 1][c - i + j][j + 1] + a[i] - a[j]); } ans = max(ans, dp[i][c][j]); } cout << s - ans; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> L >> R >> k; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = L; i <= R; i++) s += a[i]; k = min(k, n * n / 4); if(R == n) { sub2(L); return 0; } int ans = 0; for(int i = L; i <= R; i++) for(int j = L - 1; j > 0; j--) for(int c = 1; c <= k; c++) { MAX(dp[i][c][j], dp[i - 1][c][j]); MAX(dp[i][c][j], dp[i][c][j + 1]); if(c - i + j >= 0) MAX(dp[i][c][j], dp[i - 1][c - i + j][j + 1] + a[i] - a[j]); } for(int i = L; i <= R; i++) for(int j = 1; j <= k; j++) { Left[i][j] = dp[i][j][1]; // MAX(Left[i][j], Left[i][j - 1]); } memset(dp, 0, sizeof dp); for(int i = R; i >= L; i--) for(int j = R + 1; j <= n; j++) { for(int c = 1; c <= k; c++) { MAX(dp[i][c][j], dp[i + 1][c][j]); MAX(dp[i][c][j], dp[i][c][j - 1]); if(c + i - j >= 0) MAX(dp[i][c][j], dp[i + 1][c - i + j][j - 1] + a[i] - a[j]); } } for(int i = R; i >= L; i--) for(int j = 1; j <= k; j++) { Right[i][j] = dp[i][j][n]; // MAX(Right[i][j], Right[i][j - 1]); } for(int i = L - 1; i <= R; i++) for(int j = 0; j <= k; j++) MAX(ans, Left[i][j] + Right[i + 1][k - j]); cout << s - ans; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...