Submission #499991

#TimeUsernameProblemLanguageResultExecution timeMemory
499991inksamuraiHolding (COCI20_holding)C++17
55 / 110
15 ms2436 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pb push_back #define sz(a) (int)a.size() #define all(a) a.begin(),a.end() #define rep(i,n) for(int i=0;i<n;i++) #define crep(i,x,n) for(int i=x;i<n;i++) #define drep(i,n) for(int i=n-1;i>=0;i--) #define vec(...) vector<__VA_ARGS__> #define _3qplfh5 ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0) using namespace std; typedef long long ll; typedef long double ld; using pii=pair<int,int>; using vi=vector<int>; using vll=vector<long long>; int main(){ _3qplfh5; int n,l,r,k; cin>>n>>l>>r>>k; vi a(n); rep(i,n){ cin>>a[i]; } assert(r==n); l--,r--; vi rbts; crep(i,l,r+1){ rbts.pb(a[i]); } int m=r-l+1; vi psum=rbts; crep(i,1,m){ psum[i]+=psum[i-1]; } vec(vi) dp(m+1,vi(k+1,1e9)),nedp; dp[0][0]=psum[m-1]; dp[m][0]=0; drep(i,l){ nedp=dp; int x=a[i]; rep(cost,k+1){ rep(j,m+1){ if(dp[j][cost]==1e9) continue; rep(j1,j){ int necost=cost+j1+l-i; int now=psum[j-1]-psum[j1]; if(necost>k) continue; // if(i==2 and cost==0 and j==m) cout<<j1<<" "<<necost<<" "<<now<<"\n"; nedp[j1][necost]=min(nedp[j1][necost],dp[j][cost]+x+now); } } } swap(dp,nedp); // if(i==3) cout<<dp[0][1]<<"\n"; } int ans=1e9; rep(i,m+1){ rep(j,k+1){ ans=min(ans,dp[i][j]+(i==0?0:psum[i-1])); } } cout<<ans<<"\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...