Submission #16069

#	Time	Username	Problem	Language	Result	Execution time	Memory
16069		erdemkiraz	Split the sequence (APIO14_sequence)	C++14	100 / 100	961 ms	88760 KiB

sequence

#include <algorithm>
#include <iostream>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <map>
#include <set>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)

typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + 333;

const int N = 1e5 + 5;
const int K = 200 + 5;

class line{ public:
    ll m, n;
    int id;
    line(ll m, ll n, int id) {
        this -> m = m;
        this -> n = n;
        this -> id = id;
    }
    double intersect(line oth) {
        return (double) (n - oth.n) / (oth.m - m);
    }
};

class convex{ public:
    int ptr;
    vector < line > v;
    void init() {
        ptr = 0;
        v.clear();
    }
    void add(ll m, ll n, int id) {
        while(ptr + 1 < v.size()) {
            line l1 = v[ptr];
            line l2 = v[ptr + 1];
            line l3 = {m, n, id};
            if(l1.intersect(l2) < l1.intersect(l3))
                break;
            v.pop_back();
        }
        v.push_back({m, n, id});
    }
    pair < int, ll > query(int x) {
        while(ptr + 1 < v.size()) {
            line l1 = v[ptr];
            line l2 = v[ptr + 1];
            if(l1.intersect(l2) > x)
                break;
            ptr++;
        }
        return {v[ptr].id, v[ptr].m * x + v[ptr].n};
    }
}trick;

int n, k;
int a[N], sum[N], opt[K][N];
ll dp[N], ndp[N];

void pass_one(int k) {
    trick.init();
    for(int i = 1; i <= n; i++) {
        trick.add(sum[i - 1], dp[i - 1] - (ll) sum[i - 1] * sum[i - 1], i);
        pair < int, ll > res = trick.query(sum[i]);
        opt[k][i] = res.first - 1;
        ndp[i] = res.second;
    }
    for(int i = 1; i <= n; i++)
        dp[i] = ndp[i];
}

int main() {
    
    scanf("%d %d", &n, &k);
    
    for(int i = 1; i <= n; i++) {
        scanf("%d", a + i);
        sum[i] = sum[i - 1] + a[i];
    }
    
    for(int i = 1; i <= k; i++)
        pass_one(i);
    
    printf("%lld\n", dp[n]);
    
    while(k)
        printf("%d ", n = opt[k--][n]);
    
    puts("");
    
    return 0;
    
}

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