제출 #1032223

#제출 시각아이디문제언어결과실행 시간메모리
1032223HasanV11010238Holding (COCI20_holding)C++17
110 / 110
145 ms208044 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define INF 1000000000 int main(){ int n, l, r, am; cin>>n>>l>>r>>am; vector<int> v(n + 1, 0); for (int i = 1; i <= n; i++){ cin>>v[i]; } int m = (r - l + 1); vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(m + 1, vector<int>(am + 1, INF))); dp[0][0][0] = 0; int ans = INF; for (int i = 1; i <= n; i++){ for (int j = 1; j <= min(i, m); j++){ for (int k = 0; k <= am; k++){ dp[i][0][k] = 0; dp[i][j][k] = dp[i - 1][j][k]; if (k - abs(i - (l + j - 1)) >= 0){ dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j - 1][k - abs(i - (l + j - 1))] + v[i]); } if (j == m){ ans = min(ans, dp[i][j][k]); } } } } cout<<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...