제출 #491478

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
491478		Mondeus	수열 (APIO14_sequence)	C++17	71 / 100	2096 ms	125000 KiB

sequence

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <set>
#include <cassert>
#include <algorithm>
using namespace std;
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize("Ofast")
struct CHT
{
    vector<int> a;
    vector<long long> b;
    vector<int> id;
    bool cross(int i, int j, int k)
    {
        return (b[k] - b[i]) * (a[j] - a[i]) >= (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 = x * a[mid] + b[mid];
            long long f2 = x * a[mid+1] + b[mid+1];
            if(f1 > f2) r = mid;
            else l = mid+1;
        }
        return {1ll * a[l] * x + b[l], id[l]};
    }
};
int a[100005];
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 i = 1; i <= n; i++)
    {
        for(int j = min(i,k+1); j >= 1; j--)
        {
            auto calc = hull[j-1].query(a[i]);
            pre[i][j] = calc.second;
            if(i == n && j == k+1)
            {
                cout << calc.first << '\n';
                break;
            }
            hull[j].add(a[i],calc.first - 1ll * a[i] * a[i], i);
        }
    }
    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: 11 / 11
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 17 / 17
• Subtask 5: 21 / 21
• Subtask 6: 0 / 29