Submission #62819

#	Time	Username	Problem	Language	Result	Execution time	Memory
62819		win11905	Split the sequence (APIO14_sequence)	C++11	100 / 100	788 ms	83792 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#define long long long
#define ll pair<long, long>
#define x first
#define y second

const int N = 1e5+5;

struct data {
    long m, c;
    int idx;
    data() { }
    data(long m, long c, int idx) : m(m), c(c), idx(idx) { }
};

struct Convex_Hull {
    vector<data> vec;
    int ptr = 0;
    bool del(data l0, data l1, data ln) { 
        return (l1.c - l0.c) * (l0.m - ln.m) >= (ln.c - l0.c) * (l0.m - l1.m);
    }
    void add(data d) {
        while(vec.size() > 1 && del(vec[vec.size()-2], vec.back(), d)) vec.pop_back();
        while(!vec.empty() && vec.back().m == d.m && vec.back().c <= d.c) vec.pop_back();
        vec.emplace_back(d);
    }
    long get(int pos, long x) { return vec[pos].m * x + vec[pos].c; }
    ll query(long x) {
        if(ptr >= vec.size()) ptr = vec.size() - 1;
        while(ptr+1 < vec.size() && get(ptr, x) <= get(ptr+1, x)) ptr++;
        return ll(get(ptr, x), vec[ptr].idx);
    }
    void clear() {
        vec.clear();
        ptr = 0;
    }
};

int n, k;
long dp[2][N];
int s[201][N];
long pref[N];

int main() {
    scanf("%d %d", &n, &k);
    for(int i = 1; i <= n; ++i) scanf("%lld", pref+i), pref[i] += pref[i-1];
    Convex_Hull hull;
    for(int i = 1; i <= k; ++i) {
        hull.clear();
        for(int j = i+1; j <= n; ++j) {
            hull.add(data(pref[j-1], dp[~i&1][j-1] - pref[j-1] * pref[j-1], j-1));
            tie(dp[i&1][j], s[i][j]) = hull.query(pref[j]);
        }
    }
    printf("%lld\n", dp[k&1][n]);
    for(int i = k, z = n; i; --i) printf("%d ", z = s[i][z]);
}

Compilation message (stderr)

sequence.cpp: In member function 'std::pair<long long int, long long int> Convex_Hull::query(long long int)':
sequence.cpp:31:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(ptr >= vec.size()) ptr = vec.size() - 1;
            ~~~~^~~~~~~~~~~~~
sequence.cpp:32:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         while(ptr+1 < vec.size() && get(ptr, x) <= get(ptr+1, x)) ptr++;
               ~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:47:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &k);
     ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:48: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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29