Submission #970534

#TimeUsernameProblemLanguageResultExecution timeMemory
970534RandomUserHolding (COCI20_holding)C++17
22 / 110
166 ms262144 KiB
#include <bits/stdc++.h> #define sz(x) (int)x.size() #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() //#define int long long using namespace std; using ll = long long; using ull = unsigned long long; using ld = long double; using pii = pair<int, int>; using pll = pair<ll, ll>; const int mod = 1e9 + 7; const int LOG = 20; const int maxn = 1e5 + 5; const double eps = 1e-9; int32_t main() { int n, l, r, K; cin >> n >> l >> r >> K; vector<int> v(n+1); for(int i=1; i<=n; i++) cin >> v[i]; ll sum = 0; for(int i=l; i<=r; i++) sum += v[i]; ll dpL[l][n+1][K+1], dpR[n+2][n+2][K+1]; memset(dpR, 0, sizeof(dpR)); memset(dpL, 0, sizeof(dpL)); for(int i=1; i<l; i++) { for(int j=l; j<=r; j++) { for(int k=0; k<=K; k++) { dpL[i][j][k] = min(dpL[i][j][k], dpL[i-1][j][k]); dpL[i][j][k] = min(dpL[i][j][k], dpL[i][j-1][k]); if(j - i <= k) dpL[i][j][k] = min(dpL[i][j][k], dpL[i-1][j-1][k-j+i] + v[i] - v[j]); } } } for(int i=r; i>=l; i--) { for(int j=n; j>=r+1; j--) { for(int k=0; k<=K; k++) { dpR[i][j][k] = min(dpR[i][j][k], dpR[i+1][j][k]); dpR[i][j][k] = min(dpR[i][j][k], dpR[i][j+1][k]); if(j - i <= k) dpR[i][j][k] = min(dpR[i][j][k], dpR[i-1][j-1][k-j+i] + v[j] - v[i]); } } } ll mn = min(dpL[l-1][r][K], dpR[l][r+1][K]); for(int i=l; i<r; i++) for(int j=0; j<=K; j++) mn = min(mn, dpL[l-1][i][j] + dpR[i+1][r+1][K-j]); cout << sum + mn << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...