Submission #235874

#	Time	Username	Problem	Language	Result	Execution time	Memory
235874		jiahng	Split the sequence (APIO14_sequence)	C++14	100 / 100	1057 ms	84976 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll,ll> pi;
typedef pair<ll,int32_t> pint;
typedef vector <ll> vi;
typedef vector <pi> vpi;
#define f first
#define s second
#define FOR(i,s,e) for(int32_t i=s;i<=int32_t(e);++i)
#define DEC(i,s,e) for(int32_t i=s;i>=int32_t(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0)
#define maxk 201
#define maxn 100001
#define int ll
typedef pair <pi,int32_t> pii;
typedef long double ld;

int32_t N,K,A[maxn];
ll ss[maxn];
deque <pii> dq;
int32_t pre[maxn][maxk];

inline int readInt() {
    int x = 0;
    char ch = getchar_unlocked();
    while (ch < '0' || ch > '9') ch = getchar_unlocked();
    while (ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar_unlocked();
	}
    return x;
}


static inline int f(pi line, int32_t i){
	return line.f * i + line.s;
}
static inline pint query(int x,int32_t i){
	while (dq.size() > 1){
		if (dq[1].s > i) break;
		if (f(dq[0].f,x) < f(dq[1].f,x)){
			dq.pop_front();
		}else break;
	}
	return pint(f(dq[0].f,x),dq[0].s);
}

static inline double intersect(pi line1,pi line2){
	return double(line1.s - line2.s) / double(line2.f - line1.f);
}

static inline void insert(pi line,int32_t i){
	while (dq.size() > 1){
		if (intersect(dq.back().f,line) <= intersect(dq[dq.size() - 2].f,line)){
			dq.pop_back();
		}else break;
	}
	dq.pb(pii(line,i));
}


int32_t main(){
	fast;
	
	N = readInt(); K = readInt();
	
	FOR(i,1,N) A[i] =readInt(),ss[i] = ss[i-1] + A[i];
	

	vector <pii> cur;
	FOR(j,0,K){
		FOR(i,j+1,N){
			int res;

			if (i == 1) res = 0;
			else if (j == 0) res = 0;
			else{
			    pint a = query(ss[i],i);
				res = a.f;
				pre[i][j] = a.s;
			}
			if (i == N && j == K) cout<<res<<'\n';
			cur.pb(pii(pi(ss[i],res - ss[i] * ss[i]),i));
			//cout<<dp[i][j]<<' ';
		}
		dq.clear();
		aFOR(k,cur) insert(k.f,k.s);
		cur.clear();
		//while (!cur.empty()) insert(cur.back().f,cur.back().s),cur.pop_back();
		//cout<<'\n';
	}
	int32_t cr = pre[N][K];
	cout<<cr<<' ';
	DEC(i,K-1,1){
		cout<<pre[cr][i]<<' ';
		cr = pre[cr][i];
	}
}

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