Submission #166137

#	Time	Username	Problem	Language	Result	Execution time	Memory
166137		ZwariowanyMarcin	Split the sequence (APIO14_sequence)	C++14	100 / 100	1421 ms	81916 KiB

sequence

#include <bits/stdc++.h>
#define ll long long
#define mp make_pair
#define pb push_back
#define ld long double
#define ss(x) (int) x.size()
#define FOR(i, n) for(int i = 1; i <= n; ++i)
#define fi first
#define se second
#define cat(x) cout << #x << " = " << x << endl

using namespace std;

const int nax = 1e5 + 111;
const long long inf = 1e18;

int n, k;
int a[nax];
ll dp[nax][2];
int opt[nax][202];
int pref[nax];

int ja, on, K;

void solve(int l, int r, int optl, int optr) {
	if(l > r) return;
	int m = (l + r) / 2;
	opt[m][K] = m;
	for(int i = optl; i <= min(m, optr); ++i) {
		ll w = dp[i - 1][on] + 1ll * (pref[m] - pref[i - 1]) * (pref[m] - pref[i - 1]);
		if(w <= dp[m][ja]) {
			opt[m][K] = i;
			dp[m][ja] = w;
		}
	}
	solve(l, m - 1, optl, opt[m][K]);
	solve(m + 1, r, opt[m][K], optr);
}
 
int main() {
	scanf("%d %d", &n, &k);
	k += 1;
	for(int i = 1; i <= n; ++i) {
		scanf("%d", a + i);
		pref[i] = pref[i - 1] + a[i];
	}
	
	for(int i = 1; i <= n; ++i)
		dp[i][0] = inf;
		
	for(int i = 1; i <= k; ++i) {
		K = i;
		ja = i & 1;
		on = !ja;
		
		for(int j = 0; j <= n; ++j) 
			dp[j][ja] = inf;
		
		solve(1, n, 1, n);
	}
	
	ll kwa = 1ll * pref[n] * pref[n];
	printf("%lld\n", (kwa - dp[n][k & 1]) / 2);
	
	vector <int> v;
	int ind = n;
	while(k > 1) {
		v.pb(opt[ind][k]);
		ind = opt[ind][k] - 1;
		k -= 1;
	}
	
	reverse(v.begin(), v.end());
	
	for(auto it : v)
		printf("%d ", it - 1);
	
		
	
	
	
	return 0;
}

Compilation message (stderr)

sequence.cpp: In function 'int main()':
sequence.cpp:41:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &n, &k);
  ~~~~~^~~~~~~~~~~~~~~~~
sequence.cpp:44:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~

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