Submission #109761

#	Time	Username	Problem	Language	Result	Execution time	Memory
109761		PeppaPig	Split the sequence (APIO14_sequence)	C++14	0 / 100	636 ms	86932 KiB

sequence

#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 1e5+5;

struct line {
    long m, c;
    int idx;
    line(long m, long c, int idx) : m(m), c(c), idx(idx) { }
    long f(long x) { return m * x + c; }
};

struct cht {
    int ptr = 0;
    vector<line> l;
    bool bad(line a, line b, line c) { return 1.0 * (c.c - a.c) / (a.m - c.m) <= 1.0 * (b.c - a.c) / (a.m - b.m); }
    void add(long m, long c, int idx) {
        line now(m, c, idx);
        while(l.size() > 1 && bad(l[l.size()-2], l[l.size()-1], now))
            l.pop_back();
        l.emplace_back(now);
    }
    line query(long x) {
        while(ptr + 1 < l.size() && l[ptr].f(x) < l[ptr+1].f(x)) ++ptr;
        return l[ptr];
    }
    void clear() { l.clear(), ptr = 0; }
} hull[2];

int n, k, opt[205][N];
long dp[2][N], pref[N];

int main() {
    scanf("%d %d", &n, &k), ++k;
    for(int i = 1; i <= n; i++) scanf("%lld", pref+i), pref[i] += pref[i-1];
    for(int i = 0; i <= n; i++) dp[0][i] = -1e18;
    dp[0][0] = 0;
    for(int i = 1; i <= k; i++) {
        int now = i & 1, pre = now ^ 1;
        hull[now].clear();
        dp[now][0] = -1e18;
        for(int j = 1; j <= n; j++) {
            dp[now][j] = -1e18;
            if(dp[pre][j-1] != -1e18) 
                hull[now].add(pref[j-1], dp[pre][j-1] - pref[j-1] * pref[j-1], j-1);
            if(!hull[now].l.empty()) {
                line ret = hull[now].query(pref[j]);
                dp[now][j] = ret.f(pref[j]);
                opt[i][j] = ret.idx;
            }
        }
    }
    vector<int> ans;
    for(int i = k, j = n; i > 1; i--) {
        j = opt[i][j];
        ans.emplace_back(j);
    }
    reverse(ans.begin(), ans.end());
    printf("%lld\n", dp[k & 1][n]);
    for(int i : ans) printf("%d ", i);
    printf("\n");

    return 0;
}

Compilation message (stderr)

sequence.cpp: In member function 'line cht::query(long long int)':
sequence.cpp:27:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ptr + 1 < l.size() && l[ptr].f(x) < l[ptr+1].f(x)) ++ptr;
               ~~~~~~~~^~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:37:27: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k), ++k;
     ~~~~~~~~~~~~~~~~~~~~~~^~~~~
sequence.cpp:38:54: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%lld", pref+i), pref[i] += pref[i-1];
                                 ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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