Submission #982615

#	Time	Username	Problem	Language	Result	Execution time	Memory
982615		asdfGuest	Split the sequence (APIO14_sequence)	C++14	0 / 100	376 ms	84432 KiB

sequence

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long ll;

int n, m;
ll s[100001], dp[2][100001];
int from[201][100001], path[200];

struct Line {
    ll w, b;
    int idx;
    double x;
};
double cross(const Line &l1, const Line &l2) {
    return (l2.b - l1.b) / (l1.w - l2.w);
}

int main(void) {
    scanf("%d %d", &n, &m);
    s[0] = 0ll;
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &s[i]);
        s[i] += s[i - 1];
    }

    for (int i = 1; i <= n; i++)
        dp[0][i] = 0ll;

    vector<Line> buff;
    buff.reserve(n);

    for (int k = 1; k <= m; k++) {

        buff.clear();
        buff.push_back({s[k], dp[0][k] - s[k] * s[k], k, 0.0});

        int j = 0;
        for (int i = k + 1; i <= n; i++) {
            
            while (j + 1 < buff.size() && buff[j + 1].x <= (double)s[i])
                j++;

            dp[1][i] = buff[j].w * s[i] + buff[j].b;
            from[k][i] = buff[j].idx;
            
            // makek new line
            Line new_line = {s[i], dp[0][i] - s[i] * s[i], i, 0.0};

            while (!buff.empty() && (
                (buff.back().w != new_line.w && cross(buff.back(), new_line) <= buff.back().x) ||
                (buff.back().w == new_line.w && buff.back().b < new_line.b)
                )) {
                buff.pop_back();
            }

            if (!buff.empty() && buff.back().w != new_line.w)
                new_line.x = cross(buff.back(), new_line);
            if (buff.empty() || buff.back().w != new_line.w)
                buff.push_back(new_line);
        }

        for (int i = k + 1; i <= n; i++)
            dp[0][i] = dp[1][i];
    }

    int tmp = n;
    for (int i = 0; i < m; i++) {
        tmp = from[m - i][tmp];
        path[m - i - 1] = tmp;
    }

    printf("%lld\n", dp[0][n]);
    for (int i = 0; i < m; i++)
        printf("%d ", path[i]);
    printf("\n");
  
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:44:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |             while (j + 1 < buff.size() && buff[j + 1].x <= (double)s[i])
      |                    ~~~~~~^~~~~~~~~~~~~
sequence.cpp:23:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:26:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   26 |         scanf("%lld", &s[i]);
      |         ~~~~~^~~~~~~~~~~~~~~

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