Submission #921765

#	Time	Username	Problem	Language	Result	Execution time	Memory
921765		Arp	Split the sequence (APIO14_sequence)	C++17	100 / 100	1434 ms	93756 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
 
using i64 = long long;
 
const i64 inf = 1e18;
struct Line{
  i64 m,c;
  int i;
  Line() {
    cin >> m >> c;
  }
  Line(i64 _m,i64 _c,int _i) : m(_m),c(_c),i(_i) {}
  i64 getval(i64 x){
    i64 y =  m*1LL*x + c;
    return y;
  }
  i64 inc(Line L){
    if(this->m == L.m){
      return (this->c > L.c ? -inf : inf);
    }
    double x = 1.0 * (L.c - this->c) / (this->m - L.m);  
    // if(x < 0) return inf; 
    return floor(x);
  }    
};
struct Hull{
  vector<Line> lines;
  vector<i64> rng;
  void init(){
    lines.clear();
    rng.clear();
    lines.push_back(Line(0,-1,-1));
    rng.push_back(inf);
    // cout << "Line size is " << lines.size() << '\n';
  }
  void insert_line(Line L){
    // removing 100% faltu lines
    while(lines.size() >= 2){
      i64 x = L.inc(lines.back());
      i64 l = rng[rng.size() - 2] + 1;
      // assert(l > -inf);
      if(x < l){
        lines.pop_back();
        rng.pop_back();
      }else{
        break;
      }
    }
    if(lines.empty()){
      lines.push_back(L);
      rng.push_back(inf);
    }else{
      i64 x = L.inc(lines.back());
      if(x == inf) return;
      rng[rng.size() - 1] = x;
      rng.push_back(inf);
      lines.push_back(L);
    }
  }
  Line query(i64 x){
    int low = lower_bound(rng.begin(),rng.end(),x) - rng.begin();
    return lines[low];
  }
};
 
int main(){
 
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int n,k;
  cin >> n >> k;
  vector<int> a(n + 1);
  for(int i = 1;i <= n;i++){
    cin >> a[i];
  }
  vector<i64> pref(n + 1);
  for(int i = 1;i <= n;i++){
    pref[i] = pref[i - 1] + a[i];
  }
  auto S = [&](int i,int j){
    return pref[j] - pref[i]; 
  };
  vector<vector<int>> best(n + 1,vector<int>(k + 1,-1));
  // vector<vector<i64>> dp(n + 1,vector<i64>(k + 1,-inf));
  vector<i64> cur_dp(n + 1,-inf),prev_dp(n + 1,0);
  Hull hull;
  hull.insert_line(Line(0,0,0));
  for(int i = 1;i <= k;i++){
    vector<Line> lines(n);
    for(int j = 1;j < n;j++){
      if(best[j][i - 1] == -1) continue;
      // assert(dp[j][i - 1] >= 0);
      i64 m = S(0,j);
      i64 c = -m * 1LL * S(0,n) + prev_dp[j];
      lines[j] = (Line(m,c,j));
    }  
    for(int j = 1;j < n;j++){
      i64 x = S(0,j);
      Line ans = hull.query(x);
      i64 val = ans.getval(x);
      if(best[j][i - 1] != -1){
        hull.insert_line(lines[j]);
      }
      if(val < 0) continue;
      i64 C = x * 1LL * (S(0,n) - x);
      cur_dp[j] = val + C;
      best[j][i] = ans.i;
    }
    prev_dp = cur_dp;
    cur_dp = vector<i64>(n + 1,-inf);
    hull.init();
  }
  int x = 0;
  i64 maxi = 0;
  for(int i = n - 1;i >= 1;i--){
    if(prev_dp[i] >= maxi){
      x = i;
      maxi = prev_dp[i];
    }
  }
  vector<int> ans;
  while((int) ans.size() < k){
    ans.push_back(x);
    x = best[x][k - ans.size() + 1];
  }
  // assert(ans.size() == k);
  cout << maxi << '\n';
  for(int i = ans.size() - 1;i >= 0;i--){
    cout << ans[i] << " ";
  }
  cout << '\n';
  return 0;
}

• Subtask 1: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29