제출 #685195

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
685195		PoonYaPat	Split the sequence (APIO14_sequence)	C++14	0 / 100	2060 ms	79252 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n,k,ans[100001][201];
ll qs[100001],dp[100001][201];

struct line {
    ll con,slope;
};

deque<line> dq;

double ins(line a, line b) {
    return (double)(a.con-b.con)/(a.slope-b.slope);
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>k;
    for (int i=1; i<=n; ++i) {
        cin>>qs[i];
        qs[i]+=qs[i-1];
    }
    qs[n+1]=qs[n];

    for (int j=1; j<=k+1; ++j) {
        for (int i=1; i<=n; ++i) {

            for (int l=0; l<i; ++l) {
                if (dp[i][j]<dp[l][j-1]+(qs[i]-qs[l])*(qs[n]-qs[i])) {
                    ans[i][j]=l;
                    dp[i][j]=dp[l][j-1]+(qs[i]-qs[l])*(qs[n]-qs[i]);
                }
            }

        }
    }
/*
    for (int j=1; j<=k+1; ++j) {
        for (int i=1; i<=n; ++i) cout<<ans[i][j]<<" ";
        cout<<"\n";
    } */

    cout<<dp[n][k+1]<<"\n";

    vector<int> v;
    while (k) {
        v.push_back(ans[n][k]+1);
        n=ans[n][k];
        --k;
    }
    reverse(v.begin(),v.end());

    for (auto s : v) cout<<s<<" ";

}

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