Submission #557405

#	Time	Username	Problem	Language	Result	Execution time	Memory
557405		Ai7081	Split the sequence (APIO14_sequence)	C++17	100 / 100	498 ms	83824 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll, ll>

const int N = 100005;
const int K = 205;

struct Line{
    ll m, c, idx;
    ll operator() (ll x) {return m*x + c;}
};

ll n, k, a, dp[2][N], sum[N];
int rev[K][N], ptr;
vector<Line> v;

bool check(Line x, Line y, Line z) {
    return (z.c-y.c)*(x.m-y.m) < (y.c-x.c)*(y.m-z.m);
}

void add(Line L) {
    while (v.size()>=2 && check(v[v.size()-2], v.back(), L)) v.pop_back();
    while (!v.empty() && v.back().m == L.m && v.back().c <= L.c) v.pop_back();
    v.push_back(L);
}

pii query(ll x) {
    ptr = min(ptr, (int)v.size()-1);
    while (ptr != v.size()-1 && v[ptr](x) <= v[ptr+1](x)) ptr++;
    return {v[ptr](x), v[ptr].idx};
}

int main() {
    scanf(" %lld %lld", &n, &k);
    k++;
    for (int i=1; i<=n; i++) scanf(" %lld", &a), sum[i] = sum[i-1] + a;
    for (int i=2; i<=k; i++) {
        ptr = 0;
        v.clear();
        for (int j=i; j<=n; j++) {
            add({sum[j-1], dp[(i-1)&1][j-1] - sum[j-1]*sum[j-1], j-1});
            pii res = query(sum[j]);
            dp[i&1][j] = res.first;
            rev[i][j] = res.second;
        }
    }
    printf("%lld\n", dp[k&1][n]);
    vector<ll> out;
    while (rev[k][n]) {
        out.push_back(rev[k][n]);
        n = rev[k][n];
        k--;
    }
    for (int i=out.size()-1; i>=0; i--) printf("%lld ", out[i]);
    return 0;
}

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

Compilation message (stderr)

sequence.cpp: In function 'std::pair<long long int, long long int> query(long long int)':
sequence.cpp:30:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     while (ptr != v.size()-1 && v[ptr](x) <= v[ptr+1](x)) ptr++;
      |            ~~~~^~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |     scanf(" %lld %lld", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:37:35: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     for (int i=1; i<=n; i++) scanf(" %lld", &a), sum[i] = sum[i-1] + a;
      |                              ~~~~~^~~~~~~~~~~~~

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