제출 #1054209

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1054209		1ne	수열 (APIO14_sequence)	C++14	22 / 100	2082 ms	131072 KiB

sequence

/*
*  author : Apiram                  
*  created: 26.06.2023 00:43:43
*/

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

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int n,k;cin>>n>>k;
	vector<long long>arr(n);
	for (int i = 0;i<n;++i){
		cin>>arr[i];
	}
	vector<long long>pref(n + 1,0);
	for (int i = 0;i<n;++i){
	 pref[i + 1] = pref[i] + arr[i];
	}
	auto query = [&](int u,int v){
	  return pref[v + 1] - pref[u];
	};
	vector<vector<vector<long long>>>dp(n + 1,vector<vector<long long>>(n + 1,vector<long long>(k + 1,-1)));
	function<long long(int,int,int)>solve = [&](int l,int r,int kk){
		if (l == r)return dp[l][r][kk] = 0LL;
		if (kk == 0)return dp[l][r][kk] = 0LL;
		if (dp[l][r][kk] != -1)return dp[l][r][kk];
		long long ans = 0;
		for (int i = l;i<r;++i){
			for (int j = 0;j<kk;++j){
				if (i - l >= j && r - i - 1 >= kk - j - 1)
					ans = max(ans,solve(l,i,j) + solve(i + 1,r,kk - j - 1) + query(l,i) * query(i + 1,r));	
			}
		}
		return dp[l][r][kk] = ans;
	};
	vector<int>pos;
	cout<<solve(0,n - 1,k)<<'\n';
	queue<pair<int,pair<int,int>>>q;
	q.push({0,{n - 1,k}});
	for (int i = 0;i<k;++i){
		auto u = q.front();
		q.pop();
		//cout<<u.first<<" "<<u.second.first<<" "<<u.second.second<<'\n';
		int ans = -1;
		for (int j = u.first;j<u.second.first;++j){
			if (ans != -1)break;
			for (int p = 0;p<u.second.second;++p){
				if (dp[u.first][j][p] + dp[j + 1][u.second.first][u.second.second - p - 1] + query(u.first,j) * query(j + 1,u.second.first) == dp[u.first][u.second.first][u.second.second]){
					ans = 1;
					if (p > 0){
						q.push({u.first,{j,p}});
					}
					if (u.second.second - p > 0){
						q.push({j + 1,{u.second.first,u.second.second - p - 1}});
					}
					pos.push_back(j + 1);	
					break;	
				}
			}
		}							
	}
	for (auto x:pos)cout<<x<<" ";
	cout<<'\n';		
	return 0;
}

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