Submission #312024

#	Time	Username	Problem	Language	Result	Execution time	Memory
312024		chctxdy68	Split the sequence (APIO14_sequence)	C++14	62 / 100	410 ms	84364 KiB

sequence

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#pragma GCC optimize ("Ofast")
#pragma GCC optimization ("unroll-loops, no-stack-protector")
#pragma GCC target ("avx")
#pragma GCC target ("avx2")
#pragma GCC target ("fma")
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
#define pii pair <int, int>
#define pll pair <ll, ll>
#define pci pair <char, int>
#define pld pair <ld, ld>
#define ppld pair <pld, pld>
#define ppll pair <pll, pll>
#define pldl pair <ld, ll>
#define vll vector <ll>
#define vvll vector <vll>
#define vpll vector <pll>
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define mll map <ll, ll>
#define fastmap gp_hash_table
#define cd complex <double>
#define vcd vector <cd>
#define PI 3.14159265358979
#define ordered_set tree <ll, null_type, less <ll>, rb_tree_tag, tree_order_statistics_node_update>
#pragma 03
using namespace std;
using namespace __gnu_pbds;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll dp[100005][2];
int trace[100005][205];
ll a[100005], prefix[100005];
int main(){
	fastio;
	ll n, k; cin >> n >> k; k++;
	for (ll i = 1; i <= n; i++) cin >> a[i];
	for (ll i = 1; i <= n; i++) prefix[i] = prefix[i - 1] + a[i];
	for (ll i = 1; i <= n; i++) dp[i][1] = (prefix[i] * prefix[i]);
	for (ll l = 2; l <= k; l++){
		ll ptr = l - 1; 
		ll now = l % 2, prv = now ^ 1;
		for (ll i = l; i <= n; i++){
			while ((ptr < i - 1) && (dp[ptr][prv] + (prefix[i] - prefix[ptr]) * (prefix[i] - prefix[ptr]) >= dp[ptr + 1][prv] + (prefix[i] - prefix[ptr + 1]) * (prefix[i] - prefix[ptr + 1]))) ptr++;
			dp[i][now] = dp[ptr][prv] + (prefix[i] - prefix[ptr]) * (prefix[i] - prefix[ptr]); trace[i][l] = ptr;
		}
	}
	cout << (prefix[n] * prefix[n] - dp[n][k % 2]) / 2 << "\n";
	ll cur = n;
	for (ll l = k; l > 1; l--){
		cout << trace[cur][l] << " "; cur = trace[cur][l]; 
	}
}

Compilation message (stderr)

sequence.cpp:5: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("unroll-loops, no-stack-protector")
      | 
sequence.cpp:34: warning: ignoring #pragma 03  [-Wunknown-pragmas]
   34 | #pragma 03
      |

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