Submission #1270768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1270768		cmiuc	Split the sequence (APIO14_sequence)	C++20	0 / 100	0 ms	320 KiB

sequence

#include <iostream>
#include <vector>

using namespace std;
const int N = 1<<17;
int strt[N], dp[N][201], a[N];

int intersection(int i1, int i2, int k){
	int m1 = a[i1], m2 = a[i2], c1 = dp[i1][k] - a[i1] * a[i1], c2 = dp[i2][k] - a[i2] * a[i2];
	int x = (c2 - c1 + (m1 - m2 - 1)) / (m1 - m2);
	return x;
}

int main(){
	int n, K;
	cin>>n>>K;

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

	for (int k=1;k<=K;k++){
		vector<int> vec;
		for (int i=1;i<=n;i++){
			// cout<<i<<" "<<k<<endl;
			int l = 0, r = vec.size();
			while (l + 1 < r){
				int mid = (l + r) / 2;
				if (strt[vec[mid]] <= a[i])
					l = mid;
				else
					r = mid;
			}
			// cout<<i<<" "<<k<<endl;

			if (vec.size() > 0){
				// cout<<i<<" "<<k<<" "<<vec[l]<<endl;
				dp[i][k] = dp[vec[l]][k-1] + a[vec[l]] * (a[i] - a[vec[l]]);
			}
			// cout<<i<<" "<<k<<endl;

			while (vec.size() > 0 and intersection(vec.back(), i, k-1) <= strt[vec.back()])
				vec.pop_back();
			// cout<<i<<endl;
			if (vec.size() > 0)
				strt[i] = intersection(vec.back(), i, k - 1);
			vec.push_back(i);
			// cout<<i<<" "<<k<<endl;
		}
		// cout<<k<<" :: ";
		// for (int i=1;i<=n;i++)
		// 	cout<<dp[i][k]<<' ';
		// cout<<'\n';
	}

	cout<<dp[n][K-1]<<'\n';
}

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