Submission #821745

#	Time	Username	Problem	Language	Result	Execution time	Memory
821745		SUNWOOOOOOOO	Split the sequence (APIO14_sequence)	C++17	100 / 100	423 ms	83776 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int mxN = 100005, mxK = 205;
LL s[mxN], dp[2][mxN];
int track[mxK][mxN], lno;

struct Data {int no; LL m, c;};
vector <Data> lines;

void addline(Data lc){
    while (lines.size() > 1){
        Data lb = lines[lines.size() - 1], la = lines[lines.size() - 2];
        if (lb.no == lno) break;
        if ((lb.c - la.c) * (lc.m - lb.m) <= (la.m - lb.m) * (lb.c - lc.c)) lines.pop_back();
        else break;
    }
    lines.push_back(lc);
}

Data query(LL px){
    while (lno + 1 < lines.size()){
        Data lb = lines[lno + 1], la = lines[lno];
        if ((lb.c - la.c) >= px * (la.m - lb.m)) lno++;
        else break;
    }
    return lines[lno];
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    for (int i = 1, a; i <= n; i++){
        scanf("%d", &a);
        s[i] = s[i - 1] + a;
    }

    for (int t = 0; t <= k; t++){
        lno = 0;
        lines.clear();
        addline({0, 0, 0});
        for (int i = 1; i <= n; i++){
            Data lj = query(s[i]);
            track[t][i] = lj.no;
            dp[t % 2][i] = lj.m * s[i] + lj.c + s[i] * (s[n] - s[i]);
            addline({i, s[i], dp[1 - t % 2][i] - s[i] * s[n]});
        }
    }

    printf("%lld\n", dp[k % 2][n]);
    vector <int> path;
    for (int t = k, i = n; t >= 1; t--){
        i = track[t][i];
        path.push_back(i);
    }
    reverse(path.begin(), path.end());
    for (int elm : path) printf("%d ", elm); printf("\n");

    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'Data query(LL)':
sequence.cpp:22:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Data>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     while (lno + 1 < lines.size()){
      |            ~~~~~~~~^~~~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:58:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   58 |     for (int elm : path) printf("%d ", elm); printf("\n");
      |     ^~~
sequence.cpp:58:46: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   58 |     for (int elm : path) printf("%d ", elm); printf("\n");
      |                                              ^~~~~~
sequence.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d %d", &n, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d", &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