Submission #221015

#	Time	Username	Problem	Language	Result	Execution time	Memory
221015		cgiosy	Split the sequence (APIO14_sequence)	C++17	61 / 100	1739 ms	3716 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
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=[&](ll 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)>f(j, x);
		};
		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)-m;
			add(i);
		}
		return make_pair(C[N], D[N]);
	};

	ll l=0, r=9e18;
	while(l<r) {
		ll m=l+(r-l>>1);
		if(f(m).first>K) l=m+1;
		else r=m;
	}
	cout<<f(r).second+r*K<<'\n';
	for(int i=N; i=P[i];) cout<<i<<' ';
}

Compilation message (stderr)

sequence.cpp: In lambda function:
sequence.cpp:13: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:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In lambda function:
sequence.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int m=s+e>>1;
           ~^~
sequence.cpp: In function 'int main()':
sequence.cpp:54:12: warning: suggest parentheses around '-' inside '>>' [-Wparentheses]
   ll m=l+(r-l>>1);
           ~^~
sequence.cpp:59: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: 11 / 11
• Subtask 3: 0 / 11
• Subtask 4: 0 / 17
• Subtask 5: 21 / 21
• Subtask 6: 29 / 29