Submission #1196806

#	Time	Username	Problem	Language	Result	Execution time	Memory
1196806		MuhammadSaram	Split the sequence (APIO14_sequence)	C++20	100 / 100	2000 ms	92880 KiB

sequence

// Time: 06-05-2025 10:23:47
// Problem: B - Splint the sequence
// Contest: Virtual Judge - Contest 3
// URL: https://vjudge.net/contest/714915#problem/B
// Memory Limint: 128 MB
// Time Limint: 2000 ms

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int M = 1e5 + 1, K = 201;

vector<vector<int>> v[2];
int dp[M];
signed bc[M][K];

pair<int,int> poi(int m,int c,int m1,int c1)
{
	return {(c-c1),(m1-m)};
}

bool comp(pair<int,int> p,pair<int,int> p1)
{
	if (p.first/p.second<p1.first/p1.second)
		return 1;
	else if(p.first/p.second==p1.first/p1.second)
		return p.first%p.second*p1.second<p1.first%p1.second*p.second;
	return 0;
}

void add(int m,int c,int id,signed kr)
{
	while (v[id].size()>1)
	{
		pair<int,int> p={v[id][v[id].size()-2][0],v[id][v[id].size()-2][1]},p1={v[id].back()[0],v[id].back()[1]};
		if (comp(poi(p.first,p.second,m,c),poi(p.first,p.second,p1.first,p1.second)))
			v[id].pop_back();
		else
			break;
	}
	v[id].push_back({m,c,kr});
}

pair<int,signed> get(int x,int id)
{
	int ans=v[id][0][0]*x+v[id][0][1];
	signed kr=v[id][0][2];
	int s=0,e=v[id].size();
	while (s+1<e)
	{
		int mid=(s+e)/2;
		int val=v[id][mid-1][0]*x+v[id][mid-1][1];
		int val1=v[id][mid][0]*x+v[id][mid][1];
		if (val<val1)
			ans=max(ans,val1),s=mid;
		else
			ans=max(ans,val),e=mid;
		if (ans==val1)
			kr=v[id][mid][2];
		else if(ans==val)
			kr=v[id][mid-1][2];
	}
	return {ans,kr};
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(NULL), cout.tie(NULL);
	int n,k;
	cin>>n>>k;
	int pre[n+1]={},act[n+1];
	vector<int> ind;
	int id=1,x;
	for (int i=1;i<=n;i++)
	{
		cin>>x;
		if (x)
			pre[id]=pre[id-1]+x,act[id++]=i;
		else
			ind.push_back(i);
	}
	int k1=k;
	n=id-1,k=min(k,n-1),k1-=k;
	add(0,0,0,0);
	for (int i=1;i<=n;i++) add(pre[i],-pre[i]*pre[i],0,i);
	for (int j=1;j<=k;j++)
	{
		v[j%2].clear();
		for (int i=j+1;i<=n;i++)
		{
			pair<int,signed> p=get(pre[i],1-j%2);
			dp[i]=p.first,bc[i][j]=p.second;
			add(pre[i],dp[i]-pre[i]*pre[i],j%2,i);
		}
	}
	cout<<dp[n]<<endl;
	vector<int> ans;
	int cur=n;
	for (int i=k;i>=1;i--)
		ans.push_back(act[cur=bc[cur][i]]);
	for (int i=0;i<k1;i++)
		ans.push_back(ind[i]);
	for (int i:ans)	
		cout<<i<<' ';
	cout<<endl;
	
	return 0;
}

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