Submission #491460

#	Time	Username	Problem	Language	Result	Execution time	Memory
491460		Mondeus	Split the sequence (APIO14_sequence)	C++17	49 / 100	308 ms	131072 KiB

sequence

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;

struct CHT
{
    vector<long long> a;
    vector<long long> b;
    vector<long long> id;
    bool cross(int i, int j, int k)
    {
        return 1.d*(b[k] - b[i]) * (a[j] - a[i]) >= 1.d*(b[j] - b[i]) * (a[k] - a[i]);
    }
    void add(long long A, long long B, long long ID)
    {
        a.push_back(A);
        b.push_back(B);
        id.push_back(ID);
        while(a.size() > 2 && cross(a.size()-3,a.size()-2,a.size()-1))
        {
            a.erase(a.end()-2);
            b.erase(b.end()-2);
            id.erase(id.end()-2);
        }
    }
    pair<long long, long long> query(long long x)
    {
        if(a.size()==0) return {0,0};
        int l = 0, r = a.size()-1;
        while(l < r)
        {
            int mid = (l+r)/2;
            long long f1 = a[mid] * x + b[mid];
            long long f2 = a[mid+1] * x + b[mid+1];
            if(f1 > f2) r = mid;
            else l = mid+1;
        }
        return {a[l] * x + b[l], id[l]};
    }
};
long long a[100005];
long long dp[100005][2];
int pre[100005][205];
CHT hull[205];
int n,k;
vector<int> ans;
void solve()
{
    cin >> n >> k;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    for(int i = 1; i <= n; i++)
        a[i] += a[i-1];
    for(int j = 1; j <= k+1; j++)
    {
        for(int i = j; i <= n; i++)
        {
            auto calc = hull[j-1].query(a[i]);
            dp[i][1] = calc.first;
            pre[i][j] = calc.second;
            hull[j].add(a[i],dp[i][1] - a[i] * a[i], i);
        }
        CHT emp;
        hull[j-1] = emp;

    }

    cout << dp[n][1] << '\n';
    int cnt = k + 1;
    int step = n;

    while(cnt > 1)
    {
        step = pre[step][cnt];
        cnt--;
        ans.push_back(step);
    }
    reverse(ans.begin(),ans.end());
    for(auto x: ans)
        cout << x << ' ';
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    solve();
    return 0;
}

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