fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define faster ios_base::sync_with_stdio(false); cin.tie(NULL)
  4. #define Bit(mask , i) ((mask >> i) & 1)
  5. #define fi first
  6. #define se second
  7. #define _LOG2(nl) 31 - __builtin_clz(nl)
  8. #define c_bit(nl) __builtin_popcount(nl)
  9. #define ii pair<int , int>
  10. #define lii pair<long long , pair<int , int>>
  11. #define iii pair<int , pair<int , int>>
  12. #define iiii pair<pair<int , int> , pair<int , int>>
  13. #define llll pair<pair<__int128 , __int128> , pair<__int128 , __int128>>
  14. #define li pair<long long , int>
  15. #define db long double
  16. #define onBit(mask , i) (mask | (1 << i))
  17. #define offBit(mask , i) (mask & (~(1 << i)))
  18.  
  19. const long long INF = 1e16;
  20. const long long MOD = 1e9 + 7;
  21. const int N = 1e5 + 7;
  22. int n , L[N];
  23. long long m , a[N] , f[N] , t[4 * N] , lazy[4 * N];
  24. bool bl = 1;
  25.  
  26. void ktao(){
  27.     int i = n , j = n;
  28.     long long sum = a[n];
  29.     while (i > 0){
  30.         while (j > 1 && sum + a[j - 1] <= m){
  31.             --j;
  32.             sum += a[j];
  33.         }
  34.  
  35.         L[i] = j;
  36.         sum -= a[i];
  37.         --i;
  38.         if (j > i){
  39.            j = i;
  40.            sum += a[i];
  41.         }
  42.     }
  43. }
  44.  
  45. void inp(){
  46.     cin >> n >> m;
  47.     for (int i = 1 ; i <= n ; ++i){
  48.         cin >> a[i];
  49.         if (a[i] > m) bl = 0;
  50.     }
  51.     if (!bl){
  52.         cout << -1;
  53.         exit(0);
  54.     }
  55.  
  56.     ktao();
  57. }
  58.  
  59. void push(int id){
  60.     if (lazy[id]){
  61.         lazy[id << 1] += lazy[id];
  62.         t[id << 1] += lazy[id];
  63.         lazy[id << 1 | 1] += lazy[id];
  64.         t[id << 1 | 1] += lazy[id];
  65.         lazy[id] = 0;
  66.     }
  67. }
  68.  
  69. void update(int id , int l , int r , int u , int v , long long val){
  70.     if (l > v || r < u) return;
  71.     if (u <= l && r <= v){
  72.         t[id] += val;
  73.         lazy[id] += val;
  74.         return;
  75.     }
  76.  
  77.     int mid = (l + r) >> 1;
  78.     push(id);
  79.     update(id << 1 , l , mid , u , v , val);
  80.     update(id << 1 | 1 , mid + 1 , r , u , v , val);
  81.     if (t[id << 1] == 0) t[id] = t[id << 1 | 1];
  82.     else if (t[id << 1 | 1] == 0) t[id] = t[id << 1];
  83.     else t[id] = min(t[id << 1] , t[id << 1 | 1]);
  84. }
  85.  
  86. long long get(int id , int l , int r , int u , int v){
  87.     if (l > v || r < u) return INF;
  88.  
  89.     if (u <= l && r <= v) return t[id];
  90.  
  91.     int mid = (l + r) >> 1;
  92.     push(id);
  93.     long long t1 = get(id << 1 , l , mid , u , v);
  94.     long long t2 = get(id << 1 | 1 , mid + 1 , r , u , v);
  95.     if (t1 == 0) t1 = INF;
  96.     if (t2 == 0) t2 = INF;
  97.     return min(t1 , t2);
  98. }
  99.  
  100. void solve(){
  101.     stack<iii> st;
  102.     f[1] = a[1];
  103.     st.push({1 , {1 , 1}});
  104.     update(1 , 0 , n , 1 , 1 , f[1]);
  105.     update(1 , 0 , n , 0 , 0 , a[1]);
  106.  
  107.     for (int i = 2 ; i <= n ; ++i){
  108.         update(1 , 0 , n , i - 1 , i - 1 , a[i]);
  109.         int l = i;
  110.         while (st.size() && a[i] >= a[st.top().fi]){
  111.             update(1 , 0 , n , st.top().se.fi - 1 , st.top().se.se - 1 , a[i] - a[st.top().fi]);
  112.             l = st.top().se.fi;
  113.             st.pop();
  114.         }
  115.  
  116.         st.push({i , {l , i}});
  117.         f[i] = get(1 , 0 , n , L[i] - 1 , i - 1);
  118.         update(1 , 0 , n , i , i , f[i]);
  119.     }
  120.  
  121.     cout << f[n];
  122. }
  123.  
  124. int main(){
  125. //    freopen("difmax.inp" , "r" , stdin);
  126. //    freopen("difmax.out" , "w" , stdout);
  127.     faster;
  128.     inp();
  129.     solve();
  130.     return 0;
  131. }
  132.  
Success #stdin #stdout 0s 5720KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/5A4qci
language:
C++14 (gcc 8.3)
created:
13 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!