fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. typedef vector<bool> vb;
  5. typedef vector<vb> vvb;
  6. typedef vector<int> vi;
  7. typedef vector<vi> vvi;
  8. typedef vector<ll> vl;
  9. typedef vector<vl> vvl;
  10. typedef vector<char> vc;
  11. typedef vector<vc> vvc ;
  12. typedef vector<string> vs;
  13. typedef vector<pair<ll, ll> > vp;
  14. typedef pair<ll, ll> pl;
  15.  
  16. #define endl "\n"
  17. #define pb push_back
  18. #define F first
  19. #define S second
  20. #define all(v) v.begin(), v.end()
  21. #define rall(v) v.rbegin(), v.rend()
  22. #define sz(a) int(a.size())
  23. const ll mod = 1e9+7;
  24.  
  25. ll n;
  26. ll x, r, d, aux;
  27. vl vPref(3e5, 0), dp(3e5, -1);
  28.  
  29. ll f(ll i){
  30. 	if(i>=n)
  31. 		return 0;
  32.  
  33. 	if(dp[i]!=-1)
  34. 		return dp[i];
  35.  
  36.  
  37. 	dp[i] = x + f(i+1);
  38.  
  39. 	if(i+d<=n)
  40. 		dp[i] = min(dp[i], r + x*(vPref[i+d]-vPref[i]) + f(i+d));
  41.  
  42.  
  43. 	return dp[i];
  44. }
  45.  
  46. void solve(){
  47. 	vl v;
  48. 	cin >> n >> x >> r >> d;
  49.  
  50. 	for(ll i=0; i<n; i++){
  51. 		cin >> aux;
  52. 		v.pb(aux);
  53. 	}
  54.  
  55. 	for(ll i=1; i<=n; i++){
  56. 		vPref[i]=vPref[i-1]+(v[i-1]==0);
  57. 	}
  58.  
  59. 	cout << f(0) << endl;
  60. }
  61.  
  62. int main(){
  63.     ios::sync_with_stdio(false);
  64.     cin.tie(nullptr);
  65.  
  66.     int tt=1; 
  67.  
  68.     // cin >> tt;
  69.  
  70.     while(tt--){
  71.         solve();
  72.     }
  73. }
Success #stdin #stdout 0.01s 7816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/Fj5Na2
language:
C++14 (gcc 8.3)
created:
20 hours ago
visibility:
public

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!