Submission #1089750

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089750		rlx0090	Split the sequence (APIO14_sequence)	C++14	89 / 100	1247 ms	90524 KiB

sequence

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <limits>
#include <queue>
#include <string.h>
#include <stack>
#include <limits>
 
using namespace std;
int N, K;
int parent[205][100005];
long long p[100005], dp[2][100005];
long long inf = numeric_limits<long long>::max();
long long minf = numeric_limits<long long>::min();
struct line {
    long long m, k, prev, next, l;
    double cross(const line& o) {
        return 1.0 * (o.k - k) / (m - o.m);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> K;
    //N = 3;
    //K = 2;
    long long q;
    for(int i = 1; i <= N; ++i) {
        cin >> q;
        //q = 1000;
        p[i] = p[i - 1] + q;
    }
    int pv = 0;
    int before = 0, cur = 0;
    for(int k = 1; k <= K; ++k) {
        before = k % 2; cur = (k + 1) % 2;
        vector<line> lines;
        
        for(int i = N - k - 1;  i >= 0; --i) {
            bool s = false;
            line new_line = {p[i + 1], -p[i + 1] * p[i + 1] + p[N] * p[i + 1] + dp[before][i + 1], inf, minf, i + 1};
            while(lines.size() > 0) {
                if(new_line.m == lines.back().m) {
                    if(new_line.k > lines.back().k) {
                        lines.pop_back();
                        if(lines.size() > 0) new_line.prev = new_line.cross(lines.back());
                    } else s = true;
                    break;
                }
                if((new_line.prev = new_line.cross(lines.back())) >= lines.back().prev)
                    lines.pop_back();
                else break;
            }
            if(!lines.empty()) lines.back().next = lines.back().cross(new_line);
            //cout << i << "th push back line : " << new_line. m << ", " << new_line.k << ", " << new_line.prev << ", " << new_line.next << endl;
            if(!s) lines.push_back(new_line);
        
            while(pv < lines.size() && lines[pv].next >= p[i]) {
                //cout << "pv next : " << lines[pv].next << " pi : " << p[i] << endl; 
                ++pv;}
            int z = lines.size() - 1;
            pv = min(z, pv);
            
            dp[cur][i] = p[i] * lines[pv].m + lines[pv].k;
            dp[cur][i] -= p[N] * p[i];
            //cout << i << "th lines size : " << lines.size() << " pv : " << pv << " v : " << dp[cur][i] << endl;
            //cout << "k : " << k << " i : " << i << " pv : " << pv << " c : " << dp[cur][i] << endl;
            //cout << p[i] * lines[pv].m << ", " << lines[pv].k << ", " << - p[N] * p[i] << endl;
            //cout << "p[n] : " << p[N] << " p[i] : " << p[i] << endl;
            //cout << "line m : " << lines[pv].m << " line k : " << lines[pv].k << " p i : " << p[i] << endl;
            parent[k][i] = lines[pv].l;
        }
        //cout << lines.size() << endl;
        //cout <<"kth opt : " << dp[cur][0] << endl;
    }
    cout << dp[cur][0] << '\n';
    int s = 0;
    for(int k = K; k >= 1; --k) {
        cout << parent[k][s] << ' ';
        s = parent[k][s];
    }
 
    return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:63:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |             while(pv < lines.size() && lines[pv].next >= p[i]) {
      |                   ~~~^~~~~~~~~~~~~~

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