Submission #101024

#	Time	Username	Problem	Language	Result	Execution time	Memory
101024		Retro3014	Split the sequence (APIO14_sequence)	C++17	100 / 100	827 ms	84800 KiB

sequence

#include <bits/stdc++.h>

#define pb push_back
#define all(v) ((v).begin(), (v).end())
#define sortv(v) sort(all(v))
#define sz(v) ((int)(v).size())
#define uniqv(v) (v).erase(unique(all(v)), (v).end())
#define umax(a, b) (a)=max((a), (b))
#define umin(a, b) (a)=min((a), (b))
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define rep(i,n) FOR(i,1,n)
#define rep0(i,n) FOR(i,0,(int)(n)-1)
#define FI first
#define SE second
#define INF 2000000000
#define INFLL 1000000000000000000LL


using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;

const int MAX_N = 100010;
const int MAX_K = 210;
int N, K;
vector<ll> v;
ll S[MAX_N+1];
ll dp[2][MAX_N+1];
int from[MAX_K+1][MAX_N+1];
pll pr[MAX_N+1];
vector<int> st;
int k;

ll calc(int x, int y){
	pll tmp = {S[x], dp[0][x] - S[x]*S[x]};
	return tmp.first * S[y] + tmp.second;
}

bool chk(int x){
	ld x1 = -(ld)(pr[x].second - pr[st.back()].second) / (ld)(pr[x].first - pr[st.back()].first);
	ld x2 = -(ld)(pr[st.back()].second - pr[st[st.size()-2]].second) / (ld)(pr[st.back()].first - pr[st[st.size()-2]].first);
	if(x1<=x2)	return true;
	return false;
}

int main(){
	scanf("%d%d", &N, &K);
	v.push_back(0);
	for(int i=1; i<=N; i++){
		ll x; scanf("%lld", &x); v.push_back(x);
		S[i] = S[i-1] + v[i];
	}
	int idx = 0;
	for(k=1; k<=K; k++){
		idx = 0; 
		while(!st.empty())	st.pop_back();
		st.pb(k);
		pr[k] = {S[k], dp[0][k] - S[k]*S[k]};
		for(int i=k+1; i<=N; i++){
			while(st.size() > idx + 1 && calc(st[idx], i) < calc(st[idx+1], i))	idx++;
			dp[1][i] = calc(st[idx], i);
			from[k][i] = st[idx];
			pr[i] = {S[i], dp[0][i] - S[i]*S[i]};
			if(pr[i].first==pr[st.back()].first){
				if(pr[i].second>pr[st.back()].second){
					if(idx==st.size()-1)	idx--;
					st.pop_back();
				}else{
					continue;
				}
			}
			while(st.size()>1 && chk(i)){
				if(idx==st.size()-1)	idx--;
				st.pop_back();
			}
			st.push_back(i);
			idx = max(idx, 0);
			//cout<<k<<" "<<i<<" "<<dp[k][i]<<" "<<from[k][i]<<endl;
		}
		for(int i=1; i<=N; i++){
			dp[0][i] = dp[1][i];
		}
	}
	printf("%lld\n", dp[0][N]);
	vector<int> ans;
	idx = N;
	while(K>=1){
		idx = from[K][idx];
		K--;
		ans.pb(idx);
	}
	while(!ans.empty()){
		printf("%d ", ans.back());
		ans.pop_back();
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:62:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    while(st.size() > idx + 1 && calc(st[idx], i) < calc(st[idx+1], i)) idx++;
          ~~~~~~~~~~^~~~~~~~~
sequence.cpp:68:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      if(idx==st.size()-1) idx--;
         ~~~^~~~~~~~~~~~~
sequence.cpp:75:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(idx==st.size()-1) idx--;
        ~~~^~~~~~~~~~~~~
sequence.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &K);
  ~~~~~^~~~~~~~~~~~~~~~
sequence.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   ll x; scanf("%lld", &x); v.push_back(x);
         ~~~~~^~~~~~~~~~~~

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