Submission #921599

#	Time	Username	Problem	Language	Result	Execution time	Memory
921599		Arp	Split the sequence (APIO14_sequence)	C++17	0 / 100	34 ms	21300 KiB

sequence

#include<bits/stdc++.h>
using namespace std;

using i64 = long long;

const i64 inf = 1000;
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<int> 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));
  for(int i = 1;i <= n;i++){
    best[i][0] = 0;
    dp[i][0] = 0;
  }
  Hull hull;
  hull.insert_line(Line(0,0,0));
  for(int i = 1;i <= k;i++){
    vector<Line> lines(n + 1);
    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) + dp[j][i - 1];
      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);
      dp[j][i] = val + C;
      best[j][i] = ans.i;
    }
    hull.init();
  }
  int x = 0;
  i64 maxi = 0;
  for(int i = 1;i<n;i++){
    if(dp[i][k] > maxi){
      x = i;
      maxi = dp[i][k];
    }
  }
  vector<int> ans;
  while(x > 0){
    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;
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sequence.cpp:1:
sequence.cpp: In function 'int main()':
sequence.cpp:128:21: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  128 |   assert(ans.size() == k);
      |          ~~~~~~~~~~~^~~~

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