Submission #1085061

#	Time	Username	Problem	Language	Result	Execution time	Memory
1085061		ZeroCool	Split the sequence (APIO14_sequence)	C++14	0 / 100	40 ms	17948 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define ar array

const int LOG = 20;
const int MOD = 1e9 + 7;
const int INF = 1e18;

const int N = 3005;

namespace CHT{
    struct Line{
        __int128_t a, b, id;
        int operator()(int x){
            return a * x + b;
        }
    };
    bool bad(Line l1, Line l2, Line l3){
        return (l3.b - l1.b) * (l1.a - l2.a) <= (l2.b - l1.b) * (l1.a - l3.a);
    }

    vector<Line> h;
    void init(){
        h = vector<Line>();
    }

    void insert(Line l){
        while(h.size() >= 2 && bad(h[h.size() - 2], h[h.size() - 1], l))h.pop_back();
        h.push_back(l);
    }

    ar<int, 2> qry(int x){
        if(h.empty())return {INF, 0};
        int lo = 0, hi = h.size() - 1;
        while(lo < hi){
            int m = (lo + hi) / 2;
            if(h[m](x) <= h[m + 1](x))hi = m;
            else lo = m + 1;
        }
        return {h[lo](x), h[lo].id};
    }
};

signed main() {
    int n, k;
    cin>>n>>k;
    int A[n];
    for(int i = 0;i < n;i++)cin>>A[i];
    int pref[n];
    int prv[n][k + 1];
    pref[0] = A[0];
    for(int i= 1;i < n;i++)pref[i] = pref[i - 1] + A[i];
    int dp[n][k + 1];
    for(int i = 0;i < n;i++)dp[i][0] = 0;
    for(int j = 1;j < k;j++){
        CHT::init();
        for(int i = 0;i < n;i++){
            ar<int, 2> c = CHT::qry(pref[i]);
            dp[i][j] = -c[0];
            prv[j][i] = c[1]; 
            CHT::insert(CHT::Line{-pref[i], -(dp[i][j - 1] - pref[i] * pref[i]), i});
        }
    }
    int res = -1;
    int opt = -1;
    for(int i = 0;i < n;i++){
        if(res < dp[i][k - 1] + (pref[n - 1] - pref[i]) * pref[i]){
            res = dp[i][k - 1] + (pref[n - 1] - pref[i]) * pref[i];
            opt = i;

        }
    }
    cout<<res<<'\n';
    vector<int> ans;
    for(int j = k - 1;j >= 0;j--){
        ans.push_back(opt);
        opt = prv[j][opt];
    }
    for(auto u:ans)cout<<u + 1<<" ";
}

Compilation message (stderr)

sequence.cpp: In function 'std::array<long long int, 2> CHT::qry(long long int)':
sequence.cpp:42:33: warning: narrowing conversion of 'CHT::h.std::vector<CHT::Line>::operator[](((std::vector<CHT::Line>::size_type)lo)).CHT::Line::id' from '__int128' to 'long long int' [-Wnarrowing]
   42 |         return {h[lo](x), h[lo].id};

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