제출 #238142

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
238142		super_j6	Split the sequence (APIO14_sequence)	C++14	0 / 100	17 ms	1664 KiB

sequence

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
#define endl '\n'
#define ll long long
#define pi pair<ll, ll>
#define f first
#define s second

const int inf = 0x3f3f3f3f;
const int maxn = 1001, maxk = 202;
int n, k;
ll a[maxn];
pi l[maxk][maxn];
int s[maxk], e[maxk];
ll c;

bool cp(pi x, pi y, pi z){
	return (x.f - z.f) * (y.s - x.s) >= (x.f - y.f) * (z.s - x.s);
}

ll f(ll x, ll y, ll z){
	return l[x][y].f * z + l[x][y].s;	
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	k++;
	
	l[0][0] = {0, 0};
	for(int i = 1; i <= k; i++) l[i][0] = {inf, inf};
	for(int i = 1; i <= n; i++){
		ll x;
		cin >> x;
		c += x;
		for(int j = k; j; j--){
			while(e[j - 1] - s[j - 1] > 1 && f(j - 1, s[j - 1], c) >= f(j - 1, s[j - 1] + 1, c)) s[j - 1]++;
			pi p = {-2 * c, 2 * c * c + f(j - 1, s[j - 1], c)};
			while(e[j] - s[j] > 2 && cp(l[j][e[j] - 2], l[j][e[j] - 1], p)) e[j]--;
			l[j][e[j]++] = p;
		}
	}
	
	cout << ((2 * c * c - l[k][e[k] - 1].s) / 2) << endl;

	return 0;
}

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