제출 #844339

#제출 시각아이디문제언어결과실행 시간메모리
844339vjudge1Holding (COCI20_holding)C++17
0 / 110
15 ms17240 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int N = 105; const int M = 10005; const int inf = 1e18 + 7; int dp[M+1][N+1],ndp[M+1][N+1];//0 indexli , kaç kumam kaldı , kaç tane eleman aldım void solve(){ int n,l,r,k;cin >> n >> l >> r >> k; l--;r--; int arr[n]; for(int i = 0;i<n;i++)cin >> arr[i]; for(int j = 0;j<=M;j++){ for(int k = 0;k<=N;k++){ dp[j][k] = inf; ndp[j][k] = inf; } } dp[k][0] = 0; for(int i = 0;i<n;i++){ for(int j = 0;j<=k;j++){ for(int t = 0;t<=(r-l+1);t++){ if(dp[j][t] == inf)continue; //cout << i << " " << j << " " << k << " = " << dp[i][j][k] << " " << (j - abs((l + k) - i)) << endl; //al if((j - abs((l + t) - i)) >= 0){ ndp[(j - abs((l + t) - i))][t+1] = min(ndp[(j - abs((l + t) - i))][t+1] , dp[j][t] + arr[i]); //cout << " -> " << i+1 << " " << (j - abs((l + k) - i)) << " " << k+1 << " = " << dp[i+1][(j - abs((l + k) - i))][k+1] << endl; } //alma ndp[j][t] = min(ndp[j][t] , dp[j][t]); } } for(int j = 0;j<=M;j++){ for(int t = 0;t<=N;t++){ dp[j][t] = ndp[j][t]; } } } int ans = inf; //cout << "ENDED" << endl; for(int i = 0;i<N;i++){ //cout << n << " " << i << " " << r-l+1 << " -> " << dp[n][i][r-l+1] << endl; ans = min(ans , dp[i][r-l+1]); } cout << ans << endl; } signed main(){ ios_base::sync_with_stdio(0);cin.tie(0); int testcase = 1;//cin >> testcase; while(testcase--)solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...