Submission #342225

#	Time	Username	Problem	Language	Result	Execution time	Memory
342225		ezdp	Split the sequence (APIO14_sequence)	C++17	0 / 100	239 ms	3820 KiB

sequence

#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>

#define endl '\n'
#define pb push_back
#define fr first
#define sc second
#define ll long long int
#define ld long double
#define bit(idx) idx&(-idx)
#define bin(x) bitset<32>(x)
#define all(A) A.begin(), A.end()
#define de(x) cout << #x << " = " << x << endl;
#define row vector<ll>
#define row_matrix vector<ll>
#define matrix vector<row_matrix>
#define ordered_set_T int

using namespace std;
using namespace __gnu_pbds;

typedef tree<ordered_set_T, null_type, less<ordered_set_T>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
/// find_by_order(x) -> x-th element in the set
/// order_of_key(x)  -> how many elements are smaller than x
/// insert(x)		 -> inserts x into the set

const int MAXN = 1e5 + 5;
const int MAXK = 2e2 + 2;
const ll  INF = 1e18;

int n, k, A[MAXN], prefix[MAXN], opt[MAXK][MAXN];
ll dp[2][MAXN];

ll f(ll l, ll r){
	return (l == 0 ? 0 : prefix[l - 1]) * (prefix[r] - (l == 0 ? 0 : prefix[l - 1]));
}

void solve(ll i, ll l, ll r, ll tl, ll tr){
	if(l > r)
		return;
	ll m = (l + r) / 2;
	for(ll _t = max(tl, i - 1); _t <= min(tr, m); _t ++){
		if(dp[(i - 1) % 2][_t - 1] + f(_t, m) > dp[i % 2][m]){
			opt[i][m] = _t - 1;
			dp[i % 2][m] = dp[(i - 1) % 2][_t - 1] + f(_t, m);
		}
	}
	solve(i, l, m - 1, tl, opt[i][m]);
	solve(i, m + 1, r, opt[i][m], tr);
}

int main(){
	/// ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> k;
	for(int i = 1; i <= n; i ++) cin >> A[i];
	prefix[1] = A[1]; for(int i = 2; i <= n; i ++) prefix[i] = prefix[i - 1] + A[i];
	for(int i = 1; i <= k; i ++){
		for(int j = 1; j <= n; j ++) dp[i % 2][j] = -INF;
		solve(i, i + 1, n, 1, n);
	}
	cout << dp[k % 2][n] << endl;
	row v;
	ll pos = n;
	for(int i = k; i >= 1; i --){
		v.pb(opt[i][pos]);
		pos = opt[i][pos];
	}
	reverse(all(v));
	for(auto x : v) cout << x << " "; cout << endl;
}
/**

*/

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:72:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   72 |  for(auto x : v) cout << x << " "; cout << endl;
      |  ^~~
sequence.cpp:72:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   72 |  for(auto x : v) cout << x << " "; cout << endl;
      |                                    ^~~~

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