fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4. const int INF = 1e9;
  5.  
  6. struct Seg {
  7.     int n;
  8.     vector<pair<int,int>> st;
  9.     Seg(int _n=0){ init(_n); }
  10.     void init(int _n){
  11.         n = 1;
  12.         while(n < _n) n <<= 1;
  13.         st.assign(2*n, {INF, INF});
  14.     }
  15.     void setmin(int pos, pair<int,int> val){
  16.         pos += n;
  17.         if(val < st[pos]) st[pos] = val;
  18.         else return;
  19.         pos >>= 1;
  20.         while(pos){
  21.             st[pos] = min(st[pos<<1], st[(pos<<1)|1]);
  22.             pos >>= 1;
  23.         }
  24.     }
  25.     pair<int,int> query(int l, int r){
  26.         if(l > r) return {INF, INF};
  27.         l += n; r += n;
  28.         pair<int,int> res = {INF, INF};
  29.         while(l <= r){
  30.             if(l & 1) res = min(res, st[l++]);
  31.             if(!(r & 1)) res = min(res, st[r--]);
  32.             l >>= 1; r >>= 1;
  33.         }
  34.         return res;
  35.     }
  36. };
  37.  
  38. vector<int> compute_dp(int n, const vector<ll>& a, ll m){
  39.     vector<ll> pref(n+1);
  40.     pref[0]=0;
  41.     for(int i=1;i<=n;i++) pref[i]=pref[i-1]+a[i];
  42.     vector<ll> vals = pref;
  43.     for(int i=0;i<=n;i++) vals.push_back(pref[i]-m);
  44.     sort(vals.begin(), vals.end());
  45.     vals.erase(unique(vals.begin(), vals.end()), vals.end());
  46.     auto posOf = [&](ll x){ return int(lower_bound(vals.begin(), vals.end(), x) - vals.begin()); };
  47.     int sz = (int)vals.size();
  48.     Seg seg(sz);
  49.     vector<int> dp(n+1, INF);
  50.     dp[0]=0;
  51.     seg.setmin(posOf(pref[0]), {0, 0});
  52.     for(int r=1;r<=n;r++){
  53.         int idx = posOf(pref[r]-m);
  54.         auto best = seg.query(idx, sz-1);
  55.         if(best.first < INF) dp[r] = best.first + 1;
  56.         if(dp[r] < INF) seg.setmin(posOf(pref[r]), {dp[r], r});
  57.     }
  58.     return dp;
  59. }
  60.  
  61. int main(){
  62.     ios::sync_with_stdio(false);
  63.     cin.tie(nullptr);
  64.     int n;
  65.     long long m;
  66.     if(!(cin>>n>>m)) return 0;
  67.     vector<ll> a(n+1);
  68.     for(int i=1;i<=n;i++) cin>>a[i];
  69.  
  70.     auto dp_f = compute_dp(n, a, m);
  71.     int k = dp_f[n];
  72.  
  73.     vector<ll> b(n+1);
  74.     for(int i=1;i<=n;i++) b[i] = a[n-i+1];
  75.     auto dp_rev = compute_dp(n, b, m);
  76.     vector<int> suf_dp(n+2, INF);
  77.     suf_dp[n+1]=0;
  78.     for(int i=1;i<=n;i++) suf_dp[i] = dp_rev[n-i+1];
  79.  
  80.     vector<int> cuts;
  81.     int cur = 1;
  82.     int seg_left = k;
  83.     while(seg_left > 1){
  84.         int choose = -1;
  85.         ll sum = 0;
  86.         for(int i=cur;i<=n;i++){
  87.             sum += a[i];
  88.             if(sum <= m && suf_dp[i+1] == seg_left - 1){
  89.                 choose = i;
  90.                 break;
  91.             }
  92.         }
  93.         if(choose == -1) break;
  94.         cuts.push_back(choose);
  95.         cur = choose + 1;
  96.         seg_left--;
  97.     }
  98.  
  99.     cout << k << "\n";
  100.     for(size_t i=0;i<cuts.size();i++){
  101.         if(i) cout << " ";
  102.         cout << cuts[i];
  103.     }
  104.     cout << "\n";
  105.     return 0;
  106. }
  107.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/ZZAtIS
language:
C++14 (clang 8.0)
created:
6 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!