Submission #989355

#	Time	Username	Problem	Language	Result	Execution time	Memory
989355		cowwycow	Split the sequence (APIO14_sequence)	C++14	100 / 100	1006 ms	81512 KiB

sequence

// LUOGU_RID: 160508006
#include<bits/stdc++.h>
using namespace std;
#define name "aaaaaa"
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using ppii = pair<pair<int, int>, int>;

void file(){
	if(fopen(name".inp", "r")) {
		freopen(name".inp", "r", stdin);
		freopen(name".out", "w", stdout);
	}
}

const int maxn = 1e5 + 5;
const int maxk = 205;
int a[maxn];
ll pre[maxn];
ll dp[2][maxn];

int p[maxk][maxn];

ll cost(ll l, ll r){
	return (pre[r] - pre[l - 1]) * pre[l - 1];
}

void cal(int curk, int l, int r, int optl, int optr){
	if(l > r) return;
	int mid = (l + r) / 2;
	pair<ll, int> best = {-1e18, -1};
	for(int i = optl; i <= min(mid, optr); i++){
		best = max(best, {dp[curk & 1 ^ 1][i - 1] + cost(i, mid), i});
	}
	dp[curk & 1][mid] = best.first;
	int pos = best.second;
	p[curk][mid] = pos - 1;

	cal(curk, l, mid - 1, optl, pos);
	cal(curk, mid + 1, r, pos, optr);
}

void solve(){
	int n, k;
	cin >> n >> k;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	for(int i = 1; i <= k; i++){
		cal(i, 1, n, 1, n);
	}
	cout << dp[k & 1][n] << endl;
	int x = k, y = n;
	while(x){
		cout << p[x][y] << ' ';
		y = p[x][y];
		x--;
	}
}

int main(){
	file();
	solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void cal(int, int, int, int, int)':
sequence.cpp:34:29: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   34 |   best = max(best, {dp[curk & 1 ^ 1][i - 1] + cost(i, mid), i});
      |                        ~~~~~^~~
sequence.cpp: In function 'void file()':
sequence.cpp:12:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |   freopen(name".inp", "r", stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
sequence.cpp:13:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |   freopen(name".out", "w", stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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