Submission #884880

#	Time	Username	Problem	Language	Result	Execution time	Memory
884880		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	48 ms	80636 KiB

sequence

#include<bits/stdc++.h>

using namespace std;

#define read() ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define day() time_t now = time(0);char* x = ctime(&now);cerr<<"Right Now Is : "<<x<<"\n"

#define ii pair<int,int>
#define X first
#define Y second 

const long long MAX = (int)1e5 + 5;
const long long INF = (int)1e18;
const long long MOD = (int)1e9 + 7;
const int N = 200 + 5;

int n,k;
int trace[N][MAX];
long long pref[MAX];
long long a[MAX];
long long f[MAX];
long long g[MAX];

long long cost(int l,int r){
	return (pref[r] - pref[l - 1]) * (pref[n] - pref[r]);
}
int cnt = 0;

void solve(int l,int r,int u,int v){
	if(l > r)return;
	int mid = l + r >> 1;
	
	pair<long long,int> best = {-INF,0};
	
	for(int i = u;i <= min(mid,v);i++){
		best = max(best,{g[i - 1] + cost(i,mid),i});	
	}
	
	
	f[mid] = best.X;
	trace[cnt][mid] = best.Y;
	
	//cout << cnt << " " << mid << " " << best.X << " " << best.Y << '\n';
	solve(l,mid - 1,u,best.Y);
	solve(mid + 1,r,best.Y,v);
}
signed main(){
	
	read();
	
	cin >> n >> k;
	
	for(int i = 1;i <= n;i++){
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	
	for(int j = 1;j <= n;j++){
		f[j] = -INF;
		g[j] = -INF;
	}
	
	f[0] = -INF;
		
	for(int i = 1;i <= k;i++){
		cnt++;
		solve(1,n,1,n);
		for(int j = 0;j <= n;j++){
			g[j] = f[j];
			f[j] = -INF;
		}
	}
	
	int res = -INF;
	int id = 0;
	
	for(int i = 1;i <= n;i++){
		if(g[i] > res){
			res = g[i];
			id = i;
		}
	}
	
	cout << res << '\n';
	
	vector<int> ans;
	
	ans.push_back(id);
	for(int i = k;i > 1;i--){
		id = trace[i][id];
		id--;
		ans.push_back(id);
	}
	
	
	for(int i = (int)ans.size() - 1;i >= 0;i--){
		cout << ans[i] << " ";
	}
}

Compilation message (stderr)

sequence.cpp: In function 'void solve(int, int, int, int)':
sequence.cpp:31:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |  int mid = l + r >> 1;
      |            ~~^~~

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