제출 #844291

#제출 시각아이디문제언어결과실행 시간메모리
844291vjudge1Holding (COCI20_holding)C++17
110 / 110
68 ms209672 KiB
#include <bits/stdc++.h> using namespace std; #define sp " " #define endl "\n"; #define fastio() cin.tie(0), ios_base::sync_with_stdio(0) #define pb push_back #define pii pair<int, int> #define st first #define nd second #define N 105 const int modulo = 1e9 + 7; int arr[N], dp[N][N][10005]; int32_t main() { fastio(); int n, l, r, k; cin>>n>>l>>r>>k; for (int i = 1; i <= n; i++){ cin>>arr[i]; } int ans = 0; for (int i = l; i <= r; i++){ ans += arr[i]; } for (int i = r; i >= l; i--){ for (int j = n; j >= 1; j--){ if (j >= l && j <= r) continue; for (int m = 0; m <= k; m++){ int nxt = j + 1; if (nxt == l) nxt = r + 1; int t1 = dp[i][nxt][m]; int t2 = dp[i + 1][j][m]; int t3 = 0; if (m >= abs(i - j)) t3 = arr[j] - arr[i] + dp[i + 1][nxt][m - abs(i - j)]; dp[i][j][m] = min(t3, min(t1, t2)); } } } cout<<dp[l][1][k] + ans<<endl; cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...