fork(1) download
copy 
  1. #include "bits/stdc++.h"
  2. using namespace std;
  3. const int N = 1e3 + 3;
  4. const long long inf = 1e18;
  5. int a , b , d;
  6. int c[N];
  7. long long dp[N][N][2];
  8. long long solve(int pos , int buk , bool bucket_being_moved){
  9.     if(pos > a){
  10.         return 0;
  11.     }
  12.     if(buk > a){
  13.         return inf;
  14.     }
  15.     if(dp[pos][buk][bucket_being_moved] != -1){
  16.         return dp[pos][buk][bucket_being_moved];
  17.     }
  18.     long long ret = inf;
  19.     if(!bucket_being_moved){
  20.         ret = min(ret , solve(pos + 1 , buk , 0) + 1LL * b * (abs(buk - pos) * (1LL + (pos < a))));
  21.         ret = min(ret , solve(pos , buk + 1 , 1) + d + c[a - pos + 1]);
  22.     }
  23.     if(bucket_being_moved){
  24.         ret = min(ret , solve(pos , buk + 1 , bucket_being_moved) + c[a - pos + 1]);
  25.         ret = min(ret , solve(pos , buk , 0));
  26.     }
  27.     return dp[pos][buk][bucket_being_moved] = ret;
  28. }
  29. int main(){
  30.     cin >> a >> b >> d;
  31.     for(int i = 0 ; i <= a ; ++i){
  32.         cin >> c[i];
  33.     }
  34.     memset(dp , -1 , sizeof(dp));
  35.     cout << solve(1 , 0 , 0);
  36. }
Success #stdin #stdout 0s 19192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/UcEuNl
language:
C++14 (gcc 8.3)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!