fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. namespace std {
  6. #ifndef LOCAL
  7. #define cerr \
  8.   if (0) cerr
  9. #endif
  10. }  // namespace std
  11.  
  12. int64_t prf[100005];
  13. int a[100005];
  14. int64_t dp[100005];
  15.  
  16. int32_t main() {
  17.   ios_base::sync_with_stdio(0);
  18.   cin.tie(0);
  19.   int n;
  20.   int64_t m;
  21.   cin >> n >> m;
  22.   for (int i = 1; i <= n; i++) {
  23.     cin >> a[i];
  24.     prf[i] = prf[i - 1] + a[i];
  25.   }
  26.   deque<int> dq;
  27.   memset(dp, 0x3f, sizeof(dp));
  28.   const int64_t inf = dp[0];
  29.   dp[0] = 0;
  30.   for (int i = 1, j = 0; i <= n; i++) {
  31.     while (j < i && prf[i] - prf[j] > m) {
  32.       ++j;
  33.     }
  34.     while (!dq.empty() && dq.front() <= j) {
  35.       dq.pop_front();
  36.     }
  37.     while (!dq.empty() && a[dq.back()] < a[i]) {
  38.       dq.pop_back();
  39.     }
  40.     dq.push_back(i);
  41.     int last = j;
  42.     for (auto it : dq) {
  43.       dp[i] = min(dp[i], dp[last] + a[it]);
  44.       last = it;
  45.     }
  46.   }
  47.   cout << (dp[n] == inf ? -1 : dp[n]);
  48.   return 0;
  49. }
  50.  
Success #stdin #stdout 0.04s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/AF4Y1I
language:
C++14 (gcc 8.3)
created:
12 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!