제출 #537235

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
537235		Leonardo_Paes	수열 (APIO14_sequence)	C++17	60 / 100	100 ms	131072 KiB

sequence

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<int,pii> pip;
#define f first
#define s second 
const int maxn = 1e5+10, maxk = 210;

ll dp[maxn][maxk], v[maxn], suf[maxn];
int opt[maxn][maxk];

void solve(int l, int r, int optl, int optr, int k){
	if(l > r) return;
	int mid = (l + r) >> 1;
	dp[mid][k] = 0;
	for(int i=optl; i<=min(mid-1, optr); i++){
		ll c = dp[i][k-1] + (suf[i+1] - suf[mid+1]) * suf[mid+1];
		if(c > dp[mid][k]){
			dp[mid][k] = c;
			opt[mid][k] = i;
		}
	}
	solve(l, mid-1, optl, opt[mid][k], k); solve(mid+1, r, opt[mid][k], optr, k);
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	int n, k;
	cin >> n >> k;
	for(int i=1; i<=n; i++) cin >> v[i];
	for(int i=n; i>=1; i--) suf[i] = v[i] + suf[i+1];
	for(int i=1; i<=n; i++) dp[i][1] = (suf[1] - suf[i+1]) * suf[i+1];
	for(int i=2; i<=k; i++) solve(1, n, 1, n, i);
	int id = 1;
	for(int i=2; i<=n; i++) if(dp[i][k] > dp[id][k]) id = i;
	cout << dp[id][k] << "\n";
	vector<int> ans;
	for(int i=1; i<=k; i++){
		ans.push_back(id);
		id = opt[id][k-i+1];
	}
	for(int i=ans.size()-1; i>=0; i--) cout << ans[i] << " ";
	cout << "\n";
	return 0;
	/*
7 3
4 1 3 4 0 2 3
	*/
}

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