Submission #136655

#	Time	Username	Problem	Language	Result	Execution time	Memory
136655		junodeveloper	Split the sequence (APIO14_sequence)	C++14	0 / 100	106 ms	82524 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;
	vector<line> ln;
	bool Check(line& a,line& b,line& c) {
		return (double)(a.b-b.b)/(b.a-a.a)<(double)(b.b-c.b)/(c.a-b.a);
	}
	bool Check2(line& a,line& b,ll x) {
		return x*(b.a-a.a)<a.b-b.b;
	}
	void insert(line u) {
		if(!ln.empty()&&ln.back().a==u.a&&ln.back().b>=u.b) return;
		while(sz(ln)>=2&&!Check(ln[sz(ln)-2],ln.back(),u))
			ln.pop_back();
		ln.push_back(u);
	}
	line query(ll x) {
		last=min(last,sz(ln)-1);
		while(last+1<sz(ln)&&!Check2(ln[last],ln[last+1],x))last++;
		return ln[last];
	}
	void clear() {
		ln.clear();
		last=0;
	}
}cht;
int n,k,s[100010],tr[100010][202];
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]=v.a*s[i]+v.b;
			tr[i][j]=v.i;
		}
	}
	printf("%lld\n",dp[n]);
	vector<int> idx;
	while(k>1) {
		idx.push_back(tr[n][k]);
		n=tr[n][k]; k--;
	}
	reverse(all(idx));
	for(auto& it:idx) printf("%d ",it);
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:50: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:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",s+i);
   ~~~~~^~~~~~~~~~

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