Submission #231454

#	Time	Username	Problem	Language	Result	Execution time	Memory
231454		AlexLuchianov	Split the sequence (APIO14_sequence)	C++14	100 / 100	701 ms	86208 KiB

sequence

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
using ld = long double;

#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 100000;
ll v[1 + nmax];
ll sum[1 + nmax], dp[1 + nmax], dp2[1 + nmax];

struct Line{
  ll a;
  ll b;
  int id;
  ll eval(ll x){
    return 1LL * x * a + b;
  }
};
vector<Line> st;
vector<ld> points;

ld intersect(Line x, Line y){
  return ((long double)(y.b - x.b)) / (x.a - y.a);
}

void addset(Line lin){
  while(0 < st.size()){
    if(st.back().a == lin.a) {
      if(st.back().b < lin.b) {
        st.pop_back();
        points.pop_back();
      } else
        return ;
    } else {
      if(intersect(st.back(), lin) <= points.back()){
        st.pop_back();
        points.pop_back();
      } else
        break;
    }
  }
  if(0 < st.size()){
    points.push_back(intersect(st.back(), lin));
    st.push_back(lin);
  } else {
    points.push_back(0);
    st.push_back(lin);
  }
}

void optimum(int x, int &ptr){
  while(ptr + 1 < points.size() && points[ptr + 1] <= x)
    ptr++;
}

int last[5 + 200][1 + nmax];

void process(int n, int era){
  st.clear();
  points.clear();
  int ptr = 0;
  for(int i = era;i <= n; i++){
    addset({sum[i - 1], dp[i - 1] - sum[i - 1] * sum[i - 1] , i - 1});
    optimum(sum[i], ptr);
    dp2[i] = st[ptr].eval(sum[i]);
    last[era][i] = st[ptr].id;
  }
  for(int i = 1;i <= n; i++)
    dp[i] = dp2[i];
}

void print(int era, int x){
  if(1 < era)
    print(era - 1, last[era][x]);
  cout << x << " ";
}

/*
7 3
4 1 3 4 0 2 3
*/

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  int n, k;
  cin >> n >> k;
  for(int i = 1;i <= n; i++) {
    cin >> v[i];
    sum[i] = sum[i - 1] + v[i];
  }
  for(int i = 1;i <= n; i++)
    dp[i] = 0;
  for(int i = 2; i <= k + 1; i++)
    process(n, i);
  cout << dp[n] << '\n';
  print(k, last[k + 1][n]);
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void optimum(int, int&)':
sequence.cpp:61:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(ptr + 1 < points.size() && points[ptr + 1] <= x)
         ~~~~~~~~^~~~~~~~~~~~~~~

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