제출 #964271

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
964271		dubabuba	수열 (APIO14_sequence)	C++14	50 / 100	120 ms	7260 KiB

sequence

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

typedef long long i64;
typedef pair<int, int> pii;
#define ff first
#define ss second
#define MP make_pair

const int mxk = 220;
const int mxn = 1010;
const i64 inf = 1e18;
int a[mxn], p[mxn], n, k;
i64 dp[mxn][mxk], ls[mxn][mxk];

i64 kv(i64 a) { return a * a; }

void solve() {
	cin >> n >> k;
	for(int i = 0; i <= n; i++)
	for(int j = 0; j <= k; j++)
		dp[i][j] = inf;

	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
		dp[i][0] = kv(p[i]);
	}

	for(int i = 2; i <= n; i++)
	for(int j = 1; j <= k; j++) {
		for(int q = 1; q < i; q++)
		if(dp[i][j] > dp[q][j - 1] + kv(p[i] - p[q])) {
			dp[i][j] = dp[q][j - 1] + kv(p[i] - p[q]);
			ls[i][j] = q;
		}
	}

	cout << (kv(p[n]) - dp[n][k]) / 2 << endl;

	int last = ls[n][k];
	for(int i = k - 1; i >= 0; i--) {
		cout << last << ' ';
		last = ls[last][i];
	}
}

signed main() {
	#ifdef LOCAL
		auto start = chrono::high_resolution_clock::now();
	#endif

	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	signed t = 1; // cin >> t;
	while(t--) solve();
	
	#ifdef LOCAL
		auto end = chrono::high_resolution_clock::now();
		cout << "\n"; for(int i = 0; i <= 20; ++i) cout << '-';
		cout << "\nExecution time: " << chrono::duration_cast<chrono::milliseconds> (end - start).count() << "[ms]" << endl;
	#endif
	return 0;
}

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