Submission #517078

#	Time	Username	Problem	Language	Result	Execution time	Memory
517078		Gurban	Split the sequence (APIO14_sequence)	C++17	100 / 100	772 ms	81536 KiB

sequence

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

using ll = long long;

const int N = 205;
const int maxn=1e5+5;
int n,k;
ll p[maxn];
ll dp[maxn],now[maxn];
int go[N][maxn];

struct line {
    ll m, c;
    int idx;
    long long eval(long long x) { return m * x + c; }
    long double intersectX(line l) {
    	if(l.m == m){
    		cout<<"HAHAHAHA\n";
    		exit(0);
    	}
    	return (long double) (c - l.c) / (l.m - m);
    }
};

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;
	for(int i = 1;i <= n;i++){
		int x; cin >> x;
		p[i] = x + p[i - 1];
	}

	for(int i = 1;i <= k;i++){
		deque<line>dq;
		dq.push_front({p[i],dp[i] - p[i] * p[i],i});
		for(int j = i + 1;j <= n;j++){
			while(dq.size() >= 2 and dq[0].eval(p[j]) <= dq[1].eval(p[j])) dq.pop_front();
			now[j] = dq[0].eval(p[j]);
			go[i][j] = dq[0].idx;
			line cur = {p[j],dp[j] - p[j] * p[j],j};
			while(dq.size() >= 2 and cur.intersectX(dq[(int)dq.size()-2]) <= dq.back().intersectX(dq[(int)dq.size()-2])) dq.pop_back();
			dq.push_back(cur);
		}
		for(int j = i + 1;j <= n;j++) dp[j] = now[j];
	}
	cout<<dp[n]<<'\n';
	int idx = go[k][n];
	for(int i = k-1;i >= 0;i--){
		cout<<idx<<' ';
		// assert(idx >= 0 and idx <= n);
		idx = go[i][idx];
	}
}

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