답안 #400226

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
400226	2021-05-07T17:32:58 Z	l3nl3	수열 (APIO14_sequence)	C++17	0 / 100	2000 ms	131076 KB

sequence

// meowa

#include <bits/stdc++.h>

#define show(x) cerr << #x << "-> " << x << '\n';
#define ll long long
#define all(a) a.begin(), a.end()

using namespace std;

const int mxsz = 1e5+7;
const int inf = 1e9+1e2;
const int mod = 1e9+7;

int n, k, a[mxsz], s[mxsz], dp[mxsz][202], ans;
map <pair<int, int>, pair<int, int>> pr;

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for (int i = n; i >= 1; i--) {
		s[i] = s[i+1] + a[i];
	}
	for (int i = 1; i <= n; i++) {
		dp[i][1] = (s[1] - s[i+1]) * s[i+1];
		pr[{i, 1}] = {i, 1}; 
		for (int lv = 2; lv <= i; lv++) {
			for (int j = 1; j < i; j++) {
				if (dp[i][lv] < dp[j][lv-1] + (s[j+1] - s[i+1]) * s[i+1]) {
					dp[i][lv] = dp[j][lv-1] + (s[j+1] - s[i+1]) * s[i+1];
					pr[{i, lv}] = {j, lv-1}; 
				}
			}
		}
	}
	ans = 1;
	for (int i = 2; i <= n; i++) {
		if (dp[i][k] > dp[ans][k]) {
			ans = i;
		}		
	}
	cout << dp[ans][k] << '\n';
	vector<int> an;
	pair<int, int> lt = {ans, k};
	while (lt.second != 1) {
		an.push_back(lt.first);
		lt = pr[lt];
	}
	an.push_back(lt.first);
	reverse(all(an));
	for (int x : an) cout << x << ' ';
}  

/*
7 3
4 1 3 4 0 2 3
*/

Subtask #1
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	332 KB	contestant found the optimal answer: 108 == 108
2	Correct	1 ms	332 KB	contestant found the optimal answer: 999 == 999
3	Correct	1 ms	332 KB	contestant found the optimal answer: 0 == 0
4	Correct	1 ms	332 KB	contestant found the optimal answer: 1542524 == 1542524
5	Runtime error	290 ms	131076 KB	Execution killed with signal 9
6	Halted	0 ms	0 KB	-

Subtask #2
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	460 KB	contestant found the optimal answer: 1093956 == 1093956
2	Correct	2 ms	460 KB	contestant found the optimal answer: 302460000 == 302460000
3	Runtime error	388 ms	131076 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-

Subtask #3
0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	106 ms	1732 KB	contestant found the optimal answer: 610590000 == 610590000
2	Correct	105 ms	1732 KB	contestant found the optimal answer: 311760000 == 311760000
3	Runtime error	1038 ms	131076 KB	Execution killed with signal 9
4	Halted	0 ms	0 KB	-