제출 #155068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
155068		aer0park	수열 (APIO14_sequence)	C++14	71 / 100	2066 ms	85368 KiB

sequence

#include <bits/stdc++.h>
#define f first
#define s second
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
ll cnt,sz,n,k,p[100006],dp[100002][5];
int sv[100002][202],st[100005],v[100006];
vector<int> anw;
 
double get(ll a,ll b,ll q)
{
	a=st[a],b=st[b];
	ll pb=p[b],pa=p[a];
	if(pa==pb) return -1e15;
	return (double)(pb*pb-pa*pa+dp[a][q%2]-dp[b][q%2])/(double)(pb-pa);
}
 
void push(ll x,ll d)
{
	st[sz]=x;
	while(sz>=2&&get(sz,sz-1,d)<get(sz-1,sz-2,d))
		sz--,st[sz]=x;
	sz++;
}
 
ll val(ll x,ll d)
{
	while(cnt<sz-1&&p[x]>=get(cnt,cnt+1,d)) cnt++;
	ll nw=st[cnt];sv[x][d+1]=nw;
	return p[x]*p[nw]-p[nw]*p[nw]+dp[nw][d%2];
}
 
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>v[i],p[i]=p[i-1]+(ll)v[i];
	for(int i=1;i<=k;i++)
	{
		cnt=0,sz=0;
		push(0,0);
		for(int j=1;j<=n;j++)
		{
			dp[j][i%2]=val(j,i-1);
			push(j,i-1);
		}
	}
	cout<<dp[n][k%2]<<"\n";
	ll g=n;
	for(int i=k;i>=1;i--)
	{
		g=sv[g][i];
		anw.push_back(g);
	}
	reverse(anw.begin(),anw.end());
	for(int i=0;i<k;i++)
		cout<<anw[i]<<" ";
	return 0;
}

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