제출 #734164

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
734164		SanguineChameleon	수열 (APIO14_sequence)	C++17	50 / 100	2052 ms	44528 KiB

sequence

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

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

const long long inf = 1e18L + 20;
const int maxN = 1e5 + 20;
const int maxK = 2e2 + 20;
int a[maxN];
long long pref[maxN];
long long dp[maxN][maxK];
int best[maxN][maxK];

void just_do_it() {
	int N, K;
	cin >> N >> K;
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= K + 1; j++) {
			dp[i][j] = -inf;
			best[i][j] = -1;
			for (int k = i - 1; k >= 0; k--) {
				long long cur = pref[i] * pref[k] + dp[k][j - 1] - pref[k] * pref[N];
				if (cur > dp[i][j]) {
					dp[i][j] = cur;
					best[i][j] = k;
				}
			}
			dp[i][j] += pref[i] * pref[N] - pref[i] * pref[i];
		}
	}
	cout << dp[N][K + 1] << '\n';
	int cur = N;
	for (int i = K + 1; i >= 2; i--) {
		cout << (cur = best[cur][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