Submission #136784

#	Time	Username	Problem	Language	Result	Execution time	Memory
136784		junodeveloper	Split the sequence (APIO14_sequence)	C++14	100 / 100	616 ms	82076 KiB

sequence

/*
dp[i][j]=max(dp[k][j-1]+(s[i]-s[k])*s[k])
for j-1<=k<i
s[i]*s[k]-s[k]^2+dp[k][j-1]
a=s[k]
b=-s[k]*s[k]+dp[k][j-1]

*/
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
struct line {
	int a;ll b;int i;
};
struct CHT {
	int last,top;
	line ln[100010];
	inline bool Check(line& a,line& b,line& c) {
		return (double)(a.b-b.b)*(c.a-b.a)<(double)(b.b-c.b)*(b.a-a.a);
	}
	inline bool Check2(line& a,line& b,int x) {
		return (ll)x*(b.a-a.a)<a.b-b.b;
	}
	void insert(line u) {
		if(top&&ln[top-1].a==u.a&&ln[top-1].b>=u.b) return;
		while(top>=2&&!Check(ln[top-2],ln[top-1],u)) top--;
		ln[top++]=u;
	}
	line query(int x) {
		last=min(last,top-1);
		while(last+1<top&&!Check2(ln[last],ln[last+1],x))last++;
		return ln[last];
	}
	void clear() {
		last=0; top=0;
	}
}cht;
int n,k,s[100010],tr[202][100010];
ll dp[100010];
int main() {
	scanf("%d%d",&n,&k);k++;
	int i,j;
	for(i=1;i<=n;i++) {
		scanf("%d",s+i);
		s[i]+=s[i-1];
	}
	line v;
	for(j=2;j<=k;j++) {
		cht.clear();
		cht.insert({s[j-1],-(ll)s[j-1]*s[j-1]+dp[j-1],j-1});
		for(i=j;i<=n;i++) {
			v=cht.query(s[i]);
			cht.insert({s[i],-(ll)s[i]*s[i]+dp[i],i});
			dp[i]=(ll)v.a*s[i]+v.b;
			tr[j][i]=v.i;
		}
	}
	printf("%lld\n",dp[n]);
	vector<int> idx;
	while(k>1) {
		idx.push_back(tr[k][n]);
		n=tr[k][n]; k--;
	}
	reverse(all(idx));
	for(auto& it:idx) printf("%d ",it);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:48:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d",&n,&k);k++;
  ~~~~~^~~~~~~~~~~~~~
sequence.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",s+i);
   ~~~~~^~~~~~~~~~

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