Submission #1091381

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091381		nolqf	Split the sequence (APIO14_sequence)	C++14	100 / 100	1132 ms	85420 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;

const int MAXN = 1e5 + 1;
const int MAXK = 200 + 1;
const ll INF = 1e18;

int s[MAXN];

struct Line {
  ll m, b;
  int id;

  ll eval( ll x ) { 
    return m * x + b; 
  }
  ld inter( Line d ) {
    if ( m == d.m ) {
      return (d.b > b ? INF : -INF);
    }
    return (ld)(d.b - b) / (m - d.m); 
  }
};

struct Slice { 
  ld split; 
  Line line; 
  
  bool operator< ( const Slice &x ) {
    return split < x.split;
  }
};

struct CHT {
  vector<Slice> stk;
  
  void insert( Line d ) {
    if ( !stk.size() ) {
      stk.push_back({-INF + 1, d});
      return;
    }
    while ( stk.size() > 1 && stk.back().split > d.inter(stk.back().line) ) {
      stk.pop_back(); 
    }
    stk.push_back({d.inter(stk.back().line), d});
  }
  pair<ll, int> get_max( ll x ) {
    if ( !stk.size() ) return {0, 0};
    auto it = lower_bound(stk.begin(), stk.end(), Slice{(ld)x, {0, 0, 0}});
    --it;
    return {(*it).line.eval(x), (*it).line.id};
  }
  
  void clear() {
    stk.clear();
  }
  void dbg() {
    cout << setprecision(4) << fixed;
    for ( auto sl : stk ) {
      cout << "split: " << sl.split << "; line: " << sl.line.m << " " << sl.line.b << "\n";
    }
    cout << "\n";
  }
} cht;

ll dp[2][MAXN];
int prv[MAXK][MAXN];

void print_sol( int k, int i ) {
  if ( k == 0 ) return;
  print_sol(k - 1, prv[k][i]);
  cout << i << " ";
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k;

  cin >> n >> k;
  for ( int i = 1; i <= n; ++i ) {
    cin >> s[i];
    s[i] += s[i - 1];
  }
  for ( int i = 1; i <= n; ++i ) {
    dp[1][i] = (ll)s[i] * (s[n] - s[i]);
  }
  for ( int p = 2; p <= k; ++p ) {
    for ( int i = p - 1; i <= n; ++i ) {
      auto [mx, who] = cht.get_max(s[i]);
      dp[p % 2][i] = mx + (ll)s[i] * (s[n] - s[i]);
      prv[p][i] = who;
      cht.insert({s[i], dp[(p % 2) ^ 1][i] - (ll)s[n] * s[i], i});
    }
    cht.clear();
  }
  ll res = 0;
  for ( int i = 1; i <= n; ++i ) res = max(res, dp[k % 2][i]);
  cout << res << "\n";
  for ( int i = max(k - 1, 1); i <= n; ++i ) {
    if ( res == dp[k % 2][i] ) {
      print_sol(k, i); 
      break;
    }
  }
  return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:93:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   93 |       auto [mx, who] = cht.get_max(s[i]);
      |            ^

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