Submission #46008

#	Time	Username	Problem	Language	Result	Execution time	Memory
46008		sorry_Benq	Split the sequence (APIO14_sequence)	C++17	100 / 100	1417 ms	81832 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[100005];
ll DP1[100005];
ll DP2[100005];
int BES[205][100005];
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;
    
    DP2[m] = 1e18;
    int bes = -1;
    FOR(i,optl,min(optr+1,m)) {
		ll tmp = (S[m] - S[i])*(S[m] - S[i])+DP1[i];
        if ((S[m] - S[i])*(S[m] - S[i])+DP1[i] <= DP2[m]) {
            DP2[m] = (S[m] - S[i])*(S[m] - S[i])+DP1[i];
            bes = i;
        }
    }
    BES[lev][m] = bes;
    fill(lev, l,m-1,optl,bes);
    fill(lev, m+1,r,bes,optr);
}
 
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	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++){
		DP2[i] = S[i]*S[i];
	}
	for (int j = 2; j <= K + 1; j++){
		for (int i = 1; i <= N; i++){
			DP1[i] = DP2[i];
		}
		fill(j, 1, N, 1, N);
	}
	int curpos = N;
	vector<int> idx; 
	for (int j = K + 1; j >= 2; j--){
		idx.push_back(BES[j][curpos]);
		curpos = BES[j][curpos];
	}
	reverse(idx.begin(), idx.end());
	cout << (S[N] * S[N] - DP2[N])/2 << endl;
	for (int j: idx){
		cout << j << ' ';
	}
	cout << endl;
}

Compilation message (stderr)

sequence.cpp: In function 'void fill(int, int, int, int, int)':
sequence.cpp:24:6: warning: unused variable 'tmp' [-Wunused-variable]
   ll tmp = (S[m] - S[i])*(S[m] - S[i])+DP1[i];
      ^~~

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