Submission #970529

#TimeUsernameProblemLanguageResultExecution timeMemory
970529RandomUserHolding (COCI20_holding)C++17
55 / 110
77 ms100404 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]; if(r == n) { ll dp[l][n+1][K+1]; memset(dp, 0, sizeof(dp)); for(int i=1; i<l; i++) { for(int j=l; j<=r; j++) { for(int k=0; k<=K; k++) { dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k]); dp[i][j][k] = min(dp[i][j][k], dp[i][j-1][k]); if(j - i <= k) dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k-j+i] + v[i] - v[j]); } } } cout << sum + dp[l-1][n][K] << '\n'; return 0; } 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...