Submission #197477

#	Time	Username	Problem	Language	Result	Execution time	Memory
197477		red1108	Split the sequence (APIO14_sequence)	C++17	0 / 100	120 ms	84576 KiB

sequence

#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false);cin.tie(0)
#define eb emplace_back
typedef long long ll;
typedef pair<ll,ll> pll;
struct A{
	ll a, b;
	int ind;
	A(){}
	A(ll x, ll y, int z){a=x;b=y;ind=z;}
};
struct CHT{
	int top = 0;
	vector<A> line;
	void clear(){
		top = 0;
		line.clear();
	}
	double cross(A a, A b){
		return (double)(b.b-a.b)/(double)(a.a-b.a);
	}
	void add(A l){
		while(line.size()>1&&cross(line[line.size()-2], line.back())>=cross(line.back(), l)) line.pop_back();
		line.eb(l);
	}
	pll get(ll x){
		top = min(top, (int)line.size()-1);
		while(top+1<line.size()&&cross(line[top], line[top+1])<=x) top++;
		return pll(line[top].a * x + line[top].b, line[top].ind);
	}
}cht, nxt;
ll s[100010];
int bac[100010][201];
int n, k;
vector<int> h;
int main(){
	fastio;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		int a;cin>>a;
		s[i]=s[i-1]+a;
	}
	cht.add(A(0,0,0));
	ll ans=0;
	for(int i=0;i<=k;i++){
		for(int j=1;j<=n;j++){
			pll g = cht.get(s[j]);
			nxt.add(A(s[j], g.fi-s[j]*s[j],j));
			bac[j][i] = g.se;
			if(j==n&&i==k) ans = g.fi;
		}
		cht = nxt;
		nxt.clear();
	}
	cout<<ans<<endl;
	while(n){
		n = bac[n][k];
		k--;
		h.eb(n);
		if(k==0) break;

	}
	reverse(h.begin(), h.end());
	for(int i=0;i<h.size();i++) cout<<h[i]<<" ";
}

Compilation message (stderr)

sequence.cpp: In member function 'pll CHT::get(ll)':
sequence.cpp:31:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while(top+1<line.size()&&cross(line[top], line[top+1])<=x) top++;
         ~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<h.size();i++) cout<<h[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