Submission #1286639

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286639		namhh	Split the sequence (APIO14_sequence)	C++20	100 / 100	644 ms	83832 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define pll pair<long long,long long>
#define fi first
#define se second
const int N = 1e5+5;
int n,k,a[N],trace[N][201];
long long dp[N],pref[N],suf[N],pre[N];
struct line{
	int id;
	long long a,b;
};
bool bad(const line &l1, const line &l2, const line &l3){
    __int128 left = (__int128)(l2.b-l1.b)*(__int128)(l2.a-l3.a);
    __int128 right = (__int128)(l3.b-l2.b)*(__int128)(l1.a-l2.a);
    return left >= right;
}
signed main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		pref[i] = pref[i-1]+a[i];
	}
	for(int i = n; i >= 1; i--) suf[i] = suf[i+1]+a[i];
	for(int j = 1; j <= k; j++){
		deque<line>dq;
		dq.push_back({0,0,0});
		for(int i = 1; i <= n; i++){
			while(dq.size() >= 2 && -suf[i+1]*dq[0].a+dq[0].b <= -suf[i+1]*dq[1].a+dq[1].b) dq.pop_front();
			if(i >= j){
				if(dq.empty()) dp[i] = suf[i+1]*pref[i];
			    else{
				    dp[i] = -suf[i+1]*(dq[0].a-pref[i])+dq[0].b;
			        trace[i][j] = dq[0].id;
			    }
			}
			if(i >= j-1){
				line nw = {i,pref[i],pre[i]};
                while(dq.size() >= 2 && bad(dq[dq.size()-2],dq[dq.size()-1],nw)) dq.pop_back();
                dq.push_back(nw);
			}
		}
		for(int i = 1; i <= n; i++){
			if(i < j) pre[i] = 0;
			else pre[i] = dp[i];
		}
	}
	long long ans = -1;
	int idx;
	for(int i = k; i <= n; i++){
	    if(ans < dp[i]){
	    	ans = dp[i];
	    	idx = i;
		}
	}
	cout << ans << "\n";
	vector<int>res;
	while(k > 0){
		res.push_back(idx);
		idx = trace[idx][k];
		k--;
	}
	for(int i = res.size()-1; i >= 0; i--) cout << res[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