Submission #221025

#	Time	Username	Problem	Language	Result	Execution time	Memory
221025		cgiosy	Split the sequence (APIO14_sequence)	C++17	21 / 100	2095 ms	2944 KiB

sequence

#pragma GCC optimize("O3,fast-math")
#include <bits/stdc++.h>
using namespace std;
using ld=double;
using ll=long long;

int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	int N, K;
	cin>>N>>K; ++K;
	vector<int> A(N+1), P(N+1);
	for(int i=1; i<=N; i++) cin>>A[i], A[i]+=A[i-1];

	auto f=[&](ld m) {
		vector<int> C(N+1), X(1<<32-__builtin_clz(N));
		vector<ll> D(N+1);
		auto f=[&](int i, int x) {
			return ll(A[i])*A[x] + D[i]-ll(A[i])*A[i];
		};
		auto cmp=[&](int i, int j, int x) {
			return f(i, x)-C[i]*m>f(j, x)-C[j]*m;
		};
		auto add=[&](int b) {
			int s=1, e=N, i=1;
			while(s<=e) {
				int&a=X[i];
				if(cmp(b, a, s)) swap(a, b);
				if(cmp(a, b, e)) break;
				int m=s+e>>1;
				if(cmp(b, a, m)) swap(a, b), e=m-1, i=i*2;
				else s=m+1, i=i*2+1;
			}
		};
		auto get=[&](int x) {
			int s=1, e=N, i=1, k=0;
			while(s<=e) {
				if(cmp(X[i], k, x)) k=X[i];
				int m=s+e>>1;
				if(x<=m) e=m-1, i=i*2;
				else s=m+1, i=i*2+1;
			}
			return k;
		};
		for(int i=1; i<=N; i++) {
			int k=get(i);
			P[i]=k;
			C[i]=C[k]+1;
			D[i]=f(k, i);
			add(i);
		}
		return make_pair(C[N], D[N]);
	};

	ld l=0, r=4e32;
	for(int i=0; i<100; i++) {
		ld m=(l+r)/2;
		if(f(m).first>K) l=m+DBL_EPSILON;
		else r=m;
	}
	cout<<f(r).second<<'\n';
	for(int i=N; i=P[i];) cout<<i<<' ';
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:15:30: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   vector<int> C(N+1), X(1<<32-__builtin_clz(N));
                            ~~^~~~~~~~~~~~~~~~~
sequence.cpp: In lambda function:
sequence.cpp:29:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In lambda function:
sequence.cpp:38:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:61:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
  for(int i=N; i=P[i];) cout<<i<<' ';

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