Submission #857552

#	Time	Username	Problem	Language	Result	Execution time	Memory
857552		Nuraly_Serikbay	Split the sequence (APIO14_sequence)	C++14	0 / 100	12 ms	11560 KiB

sequence

#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <cassert>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <fstream>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef long double ld;
#define all(x) x.begin(),x.end()
#define pb push_back
 
const int maxn = (int)1e5 + 13;
const ll inf = (long long)1e9 + 20;
const int mod = 1e9 + 7;
#define int long long
int n,a[maxn],k;
ll pref[maxn],suf[maxn],r,l = 1;
pair<ll,ll> dp[maxn],dp1[maxn];
pair<int,int>v[maxn];
int v1[maxn],pr[201][10001];
ld inter(pair<int,int>x,pair<int,int>y){
	if(x.first == y.first){
		return 0;
	}
	return 1.0 * (y.second - x.second) / (x.first - y.first);
}
pair<ll,int> get(ll x){
	if(l > r)return {0,0};
	int mn = v[l].first * x + v[l].second,ans = v1[l];
	while(r - l + 1 >= 2 && inter(v[l],v[l + 1]) < x){
		ll y = v[l].first * x + v[l].second;
		if(y > mn ){
			mn = y;
			ans = v1[l];
		}
		l ++;
	}
	ll y = v[l].first * x + v[l].second;
	if(y > mn ){
		mn = y;
		ans = l;
	}
	return {mn,ans};
}
void add(pair<int,int>x,int ind){
	while(r>=2 && inter(v[r - 1],x) < inter(v[r],v[r - 1]))r --;
	v[++r] = x;
	v1[r] = ind;
}
void solve(){
	cin >> n >> k;
	for(int i = 1 ; i <= n ; i ++){
		cin >> a[i];
		pref[i] = pref[i - 1] + a[i];
	}
	for(int i = n ; i >= 1 ; i --){
		suf[i] = suf[i + 1] + a[i];
	}
	for(int i = 1 ; i < n ;i ++){
		dp[i] = {pref[i] * suf[i + 1],i};
	}
	int mx = -inf,ind = 0;
	for(int kol = 2 ; kol <= k ; kol ++){
		r = 0,l = 1;
		add({pref[kol-1],dp[kol-1].first},kol-1);
		for(int i = kol ; i < n ; i ++){
			pair<int,int> y = get(-suf[i + 1]);
			ll x = pref[i] * suf[i + 1] + y.first;
			dp1[i] = {x,y.second};
			pr[kol][i] = y.second;
			add({pref[i],dp[i].first},i);
		}
		//cout << "\n";
		for(int i = kol - 1; i <= n ; i ++){
			dp[i] = dp1[i];
		}
	}
	for(int i = k ; i <= n ; i ++){
		if(mx <= dp[i].first){
			mx = dp[i].first;
			ind = i;
		}
	}
	cout << mx << "\n";
	vector<int>v;
	v.pb(ind);
	int ok = pr[k][ind];
	while(ok){
		v.pb(ok);
		ok = pr[--k][ok];
	}
	for(int i = v.size() - 1 ; i >= 0 ; i --){
		cout << v[i] << ' ';
	}
}
signed main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while(t --){
		solve();
	}
	return 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