Submission #601273

#	Time	Username	Problem	Language	Result	Execution time	Memory
601273		jjiangly	Split the sequence (APIO14_sequence)	C++14	50 / 100	189 ms	19572 KiB

sequence

//#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#define TASK "QNOI"
#define ll long long
#define f first
#define s second
#define pb push_back
#define For(i,l,r) for (int i=l;i<=r;i++)
#define Fod(i,r,l) for (int i=r;i>=l;i--)
#define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
using namespace std;

typedef pair<int,int> ii;
typedef unsigned long long ull;
const int N = 1000;
const ll oo = 1e15;

ll dp[N + 5][N + 5];
int main () {
	faster;
	

	int n, k;
	cin >> n >> k;

	vector <ll> a(n + 1, 0);
	vector <ll> pre(n + 1, 0);

	For(i, 1, n) cin >> a[i], pre[i] = pre[i - 1] + a[i];

	For(i, 0, N) For(j, 0, N) dp[j][i] = -oo;
	dp[0][0] = 0;

	For(i, 1, n)
		For(j, 1, k) {
			For(l, 0, i - 1)
				dp[i][j] = max(dp[i][j], dp[l][j - 1] + 1ll * (pre[n] - pre[i]) * (pre[i] - pre[l]));
		}

	ll ans = 0;

	For(i, 1, n) ans = max(ans, dp[i][k]);

	cout << ans << endl;

	vector <int> res;

	int cnt = k - 1;

	int tmp = 1;

	For(i, 1, n) {
		if(dp[i][k] == ans) {
			res.pb(i);

			tmp = i;

			Fod(j, i - 1, 1) {
				if(cnt == 0) break;

				if(dp[j][cnt] + 1ll * (pre[n] - pre[tmp]) * (pre[tmp] - pre[j]) == ans) {
					res.pb(j);
					cnt--;
					ans = dp[j][cnt + 1]; 
					tmp = j;
				}
			}
			break;
		}
	}

	reverse(res.begin(), res.end());
	for(int i : res) cout << i << " ";
}

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