Submission #233497

#	Time	Username	Problem	Language	Result	Execution time	Memory
233497		Dan13llljws	Split the sequence (APIO14_sequence)	C++14	100 / 100	518 ms	81912 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define sp ' '
#define nl '\n'
void sc(){}template<class T,class...A>void sc(T&t,A&...a){cin>>t,sc(a...);}
void pr(){}template<class T,class...A>void pr(T t,A...a){cout<<t,pr(a...);}
#define ms(x, y) memset(x, y, sizeof(x))
#define sz(x) (int)(x.size())
#define af(x) x.begin(), x.end()
#define mp make_pair
#define pb push_back
#define f first
#define s second
const int mod = 1e9 + 7, base = 131;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
const int MM = 1e5 + 5;
int n, K, tmp, pre[205][MM], q[MM];
ll dp[MM][2], s[MM];
ll get(int j, int k, int l){
	return dp[k][j] - dp[l][j] - s[k] * s[k] + s[l] * s[l];
}
int main(){
	cin.sync_with_stdio(0); cin.tie(0); cout.tie(0);
	sc(n, K);
	for (int i = 1; i <= n; i++) sc(s[i]), s[i] += s[i - 1];
	for (int k = 1; k <= K; k++, tmp ^= 1){
		int l = 1, r = 1; 
		for (int i = 1; i <= n; i++){
			while(l < r && get(tmp ^ 1, q[l + 1], q[l]) >= s[i] * (s[q[l]] - s[q[l + 1]])) l++;
			dp[i][tmp] = dp[q[l]][tmp ^ 1] + (s[i] - s[q[l]]) * s[q[l]];
			pre[k][i] = q[l];
			while(l < r && get(tmp ^ 1, q[r], q[r - 1]) * (s[q[r]] - s[i]) >= get(tmp ^ 1, i, q[r]) * (s[q[r - 1]] - s[q[r]])) r--;
			q[++r] = i;
		}
	}
	pr(dp[n][tmp ^ 1], nl);
	for (int x = pre[K][n]; x; x = pre[--K][x]) pr(x, sp);
	return 0;
}

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