Submission #407195

#	Time	Username	Problem	Language	Result	Execution time	Memory
407195		tempus	Split the sequence (APIO14_sequence)	C++17	50 / 100	2093 ms	31948 KiB

sequence

#include <bits/stdc++.h>

#define ll long long
#define endl "\n"
#define ios ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);

using namespace std;

const ll inf = 1e14;

int main() {
    ios
    int n, k;
    cin >> n >> k;
    ll p[n + 1];
    p[0] = 0;
    for (int i = 1; i <= n; ++ i) {
        cin >> p[i];
        p[i] += p[i - 1];
    }
    ll dp[n + 1][k + 2], opt[n + 1][k + 2];

    for (int i = 1; i <= n; ++ i) {
        dp[i][1] = p[i] * p[i];
        for (int j = 2; j <= k + 1; ++ j) {
            dp[i][j] = inf;
            for (int h = 1; h < i; ++ h) {
                if (dp[h][j - 1] + (p[i] - p[h]) * (p[i] - p[h]) <= dp[i][j]) {
                    dp[i][j] = dp[h][j - 1] + (p[i] - p[h]) * (p[i] - p[h]);
                    opt[i][j] = h;
                }
            }
        }
    }
    cout << (p[n] * p[n] - dp[n][k + 1]) / 2 << endl;
    int nw = k + 1, cur = n;
    vector <int> v;
    while(nw != 0) {
        v.push_back(cur);
        cur = opt[cur][nw];
        -- nw;
    }
    reverse(v.begin(), v.end());
    for (int i = 0; i < v.size() - 1; ++ i) {
        cout << v[i] << " ";
    }
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 0; i < v.size() - 1; ++ i) {
      |                     ~~^~~~~~~~~~~~~~

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