fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ii pair<int, int>
  4. #define fi first
  5. #define se second
  6. #define task "PROJECT"
  7. //#define task "task"
  8.  
  9. #define all(x) (x).begin(), (x).end()
  10.  
  11. using namespace std;
  12.  
  13. int n, h, s, d;
  14. vector<int> a;
  15. void ip() {
  16.     cin >> n >> h >> s >> d;
  17.     for(int i = 0; i < n; ++i) {
  18.         int ai; cin >> ai; a.push_back(ai);
  19.     }
  20.     ll ans = 0;
  21.     stack<ii> pq;
  22.     int cur = 0;
  23.     for(int i = 0; i < n; ++i) {
  24.         if(cur < a[i]) {
  25.             int numHire = a[i] - cur;
  26.  
  27.             while(true) {
  28.                 if(!pq.size()) break;
  29.                 if(numHire == 0) break;
  30.                 int num = pq.top().se, tim = pq.top().fi; pq.pop();
  31.                 ll t0 = 1LL * (i - tim) * s;
  32.                 ll t1 = h + d;
  33.                 int used = min(num, numHire); num -= used;
  34.                 if(t0 < t1) {
  35. //                    cout << "waiting: " << t0 << " " << used << '\n';
  36.                     ans += t0 * used;
  37.                     ans -= 1LL * d * used;
  38.                     numHire -= used;
  39.                     if(num > 0)pq.push({tim, num});
  40.                 }
  41.                 else {
  42.                     while(pq.size()) pq.pop();
  43.                     break;
  44.                 }
  45.             }
  46.             if(numHire > 0) {
  47.                 ans += 1LL * numHire * h;
  48.             }
  49.         }
  50.         else if(cur > a[i]) {
  51. //            cout << "queue: " << i << " " << cur - a[i] << '\n';
  52.             ans += 1LL * d * (cur - a[i]);
  53.             pq.push({i, cur - a[i]});
  54.         }
  55.         ans += 1LL * a[i] * s;
  56.         cur = a[i];
  57. //        cout << i << " " << ans << '\n';
  58.     }
  59.     ans += 1LL * cur * d;
  60.     cout << ans;
  61. }
  62. int main() {
  63.     ios_base::sync_with_stdio(0);
  64.     cin.tie(0), cout.tie(0);
  65.     if(fopen(task".INP", "r")){
  66.         freopen(task".INP", "r", stdin);
  67.         freopen(task".OUT", "w", stdout);
  68.     }
  69.     int tt = 1;
  70. //    cin >> tt;
  71.     while(tt--) {
  72.         ip();
  73.     }
  74. }
  75.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
3
4 5 6
10 9 11
stdout
copy 
265
https://ideone.com/8rSh0c
language:
C++14 (gcc 8.3)
created:
3 days 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!