Submission #982620

#	Time	Username	Problem	Language	Result	Execution time	Memory
982620		asdfGuest	Split the sequence (APIO14_sequence)	C++14	100 / 100	330 ms	85384 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 Frac {
    ll a, b;

    bool operator<(const Frac &comp) const {
        // a / b < comp.a / comp.b
        return a * comp.b < comp.a * b;
    }
    bool operator<=(const Frac &comp) const {
        return a * comp.b <= comp.a * b;
    }
};
struct Line {
    ll w, b;
    int idx;
    Frac x;
};
Frac cross(const Line &l1, const Line &l2) {
    ll sign = l1.w - l2.w >= 0ll ? 1ll : -1ll;
    return {(l2.b - l1.b) * sign, (l1.w - l2.w) * sign};
}

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, {0ll, 1ll}});

        int j = 0;
        for (int i = k + 1; i <= n; i++) {
            
            while (j + 1 < buff.size() && buff[j + 1].x <= Frac{s[i], 1ll})
                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, {0ll, 1ll}};

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

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