Submission #672580

#	Time	Username	Problem	Language	Result	Execution time	Memory
672580		garam1732	Split the sequence (APIO14_sequence)	C++14	71 / 100	72 ms	131072 KiB

sequence

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

#define ff first
#define ss second
#define blank " "
#define endl "\n"
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pll;

const int MAXN = 100100;
const int MOD = 1e9+7;

struct Line {
    ll a, b; double c; int t;
};

double cross(Line x, Line y) {
    if(x.a != y.a) return (double)(y.b-x.b)/(x.a-y.a);
    if(x.b > y.b) return LLONG_MIN;
    return LLONG_MAX;
}

ll sum[MAXN], dp[MAXN][220];
int idx[MAXN][220];
vector<Line> v;

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

    int n, k; cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        int a; cin >> a;
        sum[i] = sum[i-1] + a;
    }

    for(int i = 1; i <= n; i++) dp[i][1] = sum[i]*sum[i];
    for(int j = 2; j <= k+1; j++) {
        int piv = 0;
        v.clear();
        for(int i = j; i <= n; i++) {
            Line g = {-2*sum[i-1], sum[i-1]*sum[i-1]+dp[i-1][j-1], 0, i-1};
            while(v.size() && (g.c = cross(*v.rbegin(), g)) < v.rbegin()->c) v.pop_back();
            v.push_back(g);

            while(piv+1 < v.size() && v[piv+1].c < sum[i]) piv++;
            dp[i][j] = sum[i]*sum[i] + v[piv].a*sum[i] + v[piv].b;
            idx[i][j] = v[piv].t;
        }
    }

//    for(int i = 1; i <= n; i++) {
//        for(int j = 1; j <= k+1; j++) cout << dp[i][j] << blank;
//        cout << endl;
//    }

    cout << (sum[n]*sum[n] - dp[n][k+1])/2 << endl;

    for(int i = idx[n][k+1]; k; i = idx[i][k--]) cout << i << blank;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:49:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |             while(piv+1 < v.size() && v[piv+1].c < sum[i]) piv++;
      |                   ~~~~~~^~~~~~~~~~

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