Submission #31122

#	Time	Username	Problem	Language	Result	Execution time	Memory
31122		tatatan	Split the sequence (APIO14_sequence)	C++11	0 / 100	0 ms	1844 KiB

sequence

#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<LL,LL>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=100005,MAXK=201;
LL n,k,dp[MAXN][MAXK],sum[MAXN],t,pnt[MAXK],used[MAXN][MAXK];
vector<pair<pii,int> > line[MAXK];

double inter(pii a,pii b) {
	
	return 1.0*(b.nd-a.nd)/(a.st-b.st);

}

void upd(int x,LL val) {

	while(pnt[x]+1<line[x].size()&&inter(line[x][pnt[x]].st,line[x][pnt[x]+1].st)<=1.0*val)
		++pnt[x];

}

void add(int x,pii ll,int y) {

	while(line[x].size()>=2&&inter(line[x].back().st,line[x][line[x].size()-2].st)>=inter(ll,line[x].back().st)) 
		line[x].pop_back();
	line[x].pb(mp(ll,y));
	pnt[x]=min(pnt[x],(LL)line[x].size()-1);

}

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n>>k;
	for(int i=1;i<=n;++i) {
		cin>>t;
		sum[i]=sum[i-1]+t;
	}
	for(int i=1;i<=n;++i) {
		add(0,mp(sum[i],-sum[i]*sum[i]),i);
		for(int j=1;j<i;++j){
			upd(j-1,sum[i]);
			dp[i][j]=line[j-1][pnt[j-1]].st.st*sum[i]+line[j-1][pnt[j-1]].st.nd;
			used[i][j]=line[j-1][pnt[j-1]].nd;
			add(j,mp(sum[i],-sum[i]*sum[i]+dp[i][j]),i);
		}
	}
	cout<<dp[n][k]<< endl;
	int cur=n;
	for(int i=k;i>=1;--i) {
		cur=used[cur][i];
		cout<<cur<<" ";
	}
	cout<<endl;

}

Compilation message (stderr)

sequence.cpp: In function 'void upd(int, long long int)':
sequence.cpp:23:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(pnt[x]+1<line[x].size()&&inter(line[x][pnt[x]].st,line[x][pnt[x]+1].st)<=1.0*val)
                ^

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