Submission #750708

#TimeUsernameProblemLanguageResultExecution timeMemory
750708bgnbvnbvHolding (COCI20_holding)C++14
110 / 110
24 ms26996 KiB
#include<bits/stdc++.h> #define TASKNAME "codeforce" #define pb push_back #define pli pair<int,int> #define fi first #define se second #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL); using namespace std; using ll=int; const ll maxN=103; const ll inf=1e18; const ll mod=1e9+7; ll n,l,r,k; ll a[maxN],dp[maxN][maxN][maxN*maxN/4],sum=0; void solve() { cin >> n >> l >> r >> k; k=min(k,n*n/4+1); for(int i=1;i<=n;i++) cin >> a[i]; for(int i=l;i<=r;i++) sum+=a[i]; // dpr for(int i=r+1;i<=n;i++) { for(int j=r;j>=l;j--) { for(int q=0;q<=k;q++) { dp[i][j][q]=max({dp[i-1][j][q],dp[i][j+1][q]}); if(q-(i-j)>=0) dp[i][j][q]=max(dp[i][j][q],dp[i-1][j+1][q-(i-j)]+a[j]-a[i]); } } } for(int i=l-1;i>=1;i--) { for(int j=l;j<=r;j++) { for(int q=0;q<=k;q++) { dp[i][j][q]=max({dp[i+1][j][q],dp[i][j-1][q]}); if(q-(j-i)>=0) dp[i][j][q]=max(dp[i][j][q],dp[i+1][j-1][q-(j-i)]+a[j]-a[i]); } } } ll ans=sum; for(int i=l-1;i<=r;i++) { for(int j=0;j<=k;j++) { if(j-1>=0) dp[1][i][j]=max(dp[1][i][j],dp[1][i][j-1]); } } for(int i=l;i<=r+1;i++) { for(int j=0;j<=k;j++) { if(j-1>=0) dp[n][i][j]=max(dp[n][i][j],dp[n][i][j-1]); } } for(int i=l;i<=r+1;i++) { for(int ss=0;ss<=k;ss++) ans=min(ans,sum-dp[1][i-1][ss]-dp[n][i][k-ss]); } cout << ans; } int main() { fastio //freopen(TASKNAME".INP","r",stdin); //freopen(TASKNAME".OUT","w",stdout); solve(); }

Compilation message (stderr)

holding.cpp:11:14: warning: overflow in conversion from 'double' to 'll' {aka 'int'} changes value from '1.0e+18' to '2147483647' [-Woverflow]
   11 | const ll inf=1e18;
      |              ^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...