Submission #43646

#	Time	Username	Problem	Language	Result	Execution time	Memory
43646		sorry_Benq	Split the sequence (APIO14_sequence)	C++14	71 / 100	137 ms	16752 KiB

sequence

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

#define FOR(i, a, b) for (int i=a; i<(b); i++)
#define F0R(i, a) for (int i=0; i<(a); i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)

ll S[10005];
ll DP[10005][205];
const ll INF = 1e18;

void fill(int lev, int l, int r, int optl, int optr) {
    if (l > r) return;
    optr = min(optr,r);
    int m = (l+r)/2;
    
    DP[m][lev] = 1e18;
    int bes = -1;
    FOR(i,optl,min(optr+1,m)) {
        if ((S[m] - S[i])*(S[m] - S[i])+DP[i][lev-1] < DP[m][lev]) {
            DP[m][lev] = (S[m] - S[i])*(S[m] - S[i])+DP[i][lev-1];
            bes = i;
        }
    }
    fill(lev,l,m-1,optl,bes);
    fill(lev,m+1,r,bes,optr);
}

int main(){
	S[0] = 0;
	int N, K; cin >> N >> K;
	for (int i = 1; i <= N; i++){
		ll x; cin >> x;
		S[i] = S[i - 1] + x;
	}
	for (int i = 1; i <= N; i++){
		DP[i][1] = S[i]*S[i];
	}
	for (int j = 2; j <= K + 1; j++){
		fill(j, 1, N, 1, N);
	}
	int curpos = N;
	vector<int> idx; 
	for (int j = K + 1; j >= 2; j--){
		for (int i = curpos - 1; i >= 0; i--){
			if (DP[curpos][j] == DP[i][j - 1] + (S[i] - S[curpos])*(S[i] - S[curpos])){
				idx.push_back(i);
				curpos = i;
				break;
			}
		}
	}
	sort(idx.begin(), idx.end());
	cout << (S[N] * S[N] - DP[N][K + 1])/2 << endl;
	for (int j: idx){
		cout << j << ' ';
	}
	cout << endl;
}

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