Submission #982586

#	Time	Username	Problem	Language	Result	Execution time	Memory
982586		asdfGuest	Split the sequence (APIO14_sequence)	C++14	0 / 100	428 ms	88080 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];
    }

    vector<Line> stack[2];
    stack[0].reserve(n);
    stack[1].reserve(n);

    for (int k = 0; k <= m; k++) {
        stack[1].clear();

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

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

            auto &buff = stack[1];
            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];
        
        stack[0].clear();
        for (int i = 0; i < stack[1].size(); i++)
            stack[0].push_back(stack[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:43:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |                 while (j + 1 < stack[0].size() && stack[0][j + 1].x <= (double)s[i])
      |                        ~~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:71:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for (int i = 0; i < stack[1].size(); 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