제출 #997495

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997495		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	31 ms	16052 KiB

sequence

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

#define int long long
int const N=2e5+5;
int const mod=1e9+7;
int m, n;
vector<long long> dp_before, dp_cur;
vector<int> dp_pr;
vector<long long> dp[205];
vector<int> pr[N];
long long prefix[N];
vector<int> mv;
long long C(int i, int j){
	if(i==0)
		return prefix[j]*prefix[j];
	return (prefix[j]-prefix[i-1])*(prefix[j]-prefix[i-1]);
}

// compute dp_cur[l], ... dp_cur[r] (inclusive)
void compute(int l, int r, int optl, int optr) {
    if (l > r)
        return;

    int mid = (l + r) >> 1;
    pair<long long, int> best = {LLONG_MAX, -1};

    for (int k = optl; k <= min(mid, optr); k++) {
        best = min(best, {(k ? dp_before[k - 1] : 0) + C(k, mid), k});
    }

    dp_cur[mid] = best.first;
    dp_pr[mid]= best.second;
    int opt = best.second;

    compute(l, mid - 1, optl, opt);
    compute(mid + 1, r, opt, optr);
}

long long solve() {
    dp_before.assign(n,0);
    dp_cur.assign(n,0);
    dp_pr.assign(n,0);

    for (int i = 0; i < n; i++)
        dp_before[i] = C(0, i);
    dp[0]=dp_before;
    pr[0]=dp_pr;
    for (int i = 1; i < m; i++) {
        compute(0, n - 1, 0, n - 1);
        
        dp[i]=dp_cur;
        pr[i]=dp_pr;
        dp_before = dp_cur;
    }
    int t=pr[m-1][n-1];
    for(int i=m-2;i>=0;i--){
    	mv.push_back(pr[i][t]);
    	t=pr[i][t];
    }
    return dp_before[n - 1];
}

signed main(){
	cin>>n>>m;
	m++;
	long long total=0;
	int arr[n];
	for (int i = 0; i < n; ++i){
		cin>>arr[i];
		total+=arr[i];
	}
	prefix[0]=arr[0];
	for (int i = 1; i < n; ++i)
		prefix[i]=prefix[i-1]+arr[i];
	total*=total;
	total-=solve();
	total/=2;
	cout<<total<<endl;
	reverse(mv.begin(), mv.end());
	for(auto i:mv)
		cout<<i+1<<' ';
	cout<<endl;
	return 0;
}

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