제출 #1270786

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1270786		cmiuc	Split the sequence (APIO14_sequence)	C++20	33 / 100	5 ms	1096 KiB

sequence

#include <iostream>
#include <deque>

using namespace std;
#define int long long
const int N = 1<<17;
int strt[N], dp[N][2], a[N];
signed Par[N][201];

int intersection(int i1, int i2){
	int m1 = a[i1], m2 = a[i2], c1 = dp[i1][0] - a[i1] * a[i1], c2 = dp[i2][0] - a[i2] * a[i2];
	if (m1 == m2){
		if (c1 > c2)
			return 2e9;
		return -1;
	}
	int x = (c2 - c1) / (m1 - m2);
	while (c1 + x * m1 > c2 + x * m2)
		x++;
	return x;
}

void solve(int n, int k){
	if (k == 0){
		cout<<n<<' ';
		return;
	}
	solve(Par[n][k], k - 1);
	cout<<n<<' ';
}

signed main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, K;
	cin>>n>>K;

	for (int i=1;i<=n;i++)
		cin>>a[i], a[i] += a[i-1];

	for (int k=1;k<=K;k++){
		deque<int> vec;
		for (int i=1;i<=n;i++){
			while (vec.size() > 1 and strt[vec[1]] <= a[i])
				vec.pop_front();

			if (vec.size() > 0){
				Par[i][k] = vec[0];
				dp[i][1] = dp[vec[0]][0] + a[vec[0]] * (a[i] - a[vec[0]]);
			}

			while (vec.size() > 0 and intersection(vec.back(), i) <= strt[vec.back()])
				vec.pop_back();

			if (vec.size() > 0)
				strt[i] = intersection(vec.back(), i);
			vec.push_back(i);
		}
		for (int i=1;i<=n;i++)
			dp[i][0] = dp[i][1], dp[i][1] = 0;
	}

	cout<<dp[n][0]<<'\n';
	solve(Par[n][K], K - 1);
	cout<<'\n';
}

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