Submission #693696

#	Time	Username	Problem	Language	Result	Execution time	Memory
693696		MurotY	Split the sequence (APIO14_sequence)	C++14	0 / 100	23 ms	27492 KiB

sequence

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define ios ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define all(a) a.begin(), a.end()
#define sz size()
using namespace std;
const ll N=1e6+7, M=1e9+7;

ll a[N];
int pos[N];
ll memo[1005][205];
void solve()
{
	int n, k;
	cin >> n >> k;
	
	ll sum=0;
	for (int i=1;i<=n;i++) cin >> a[i], sum+=a[i];
	
	if (k == 0){
		cout << sum;
		return ;
	}
	auto dp = [&] (auto& dp, int i, int k, ll sum) -> ll {
		
		vector <int> vc;
		vc.clear();
		if (k <= 0 || i >= n+1) {
		     return 0;
		}
		if (memo[i][k] != -1) return memo[i][k];
		ll cur=0, ans=0;
		for (int j=i;j<=n;j++){
			sum-=a[j], cur+=a[j];
			ll res=dp(dp, j+1, k-1, sum);
			if (ans < sum*cur+res){
			     ans=sum*cur+res;
		          pos[i]=j;
			}
			
		}
		memo[i][k]=ans;
		return ans;
	};
	for (int i=0;i<=n;i++){
		for (int j=0;j<=k;j++) memo[i][j]=-1;
	}
	ll res=dp(dp, 1, k, sum);
//	for (int i=1;i<=n;i++) cout << pos[i] <<" ";
	
	cout << res <<"\n";
	int tmp=pos[1], cnt=0, ccc=0;
	while (tmp <= n && tmp >= 1 && cnt < k){
		cout << tmp <<" ";
		tmp=pos[tmp+1]; cnt++;
	}
	return ;
}
int main(){
	ios;
	int t=1;	
//	cin >> t;
	while (t--){ 
	    solve();
	    cout << "\n";
	}
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:56:25: warning: unused variable 'ccc' [-Wunused-variable]
   56 |  int tmp=pos[1], cnt=0, ccc=0;
      |                         ^~~

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