Submission #41897

#	Time	Username	Problem	Language	Result	Execution time	Memory
41897		RockyB	Split the sequence (APIO14_sequence)	C++14	50 / 100	286 ms	16668 KiB

sequence

/// In The Name Of God

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>

#define f first
#define s second

#define pb push_back
#define pp pop_back
#define mp make_pair

#define sz(x) (int)x.size()
#define sqr(x) ((x) * 1ll * (x))
#define all(x) x.begin(), x.end()

#define Kazakhstan ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

#define nl '\n'
#define ioi exit(0);

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int N = (int)1000 + 7;
const int inf = (int)1e9 + 7;
const int mod = (int)1e9 + 7;
const ll linf = (ll)1e18 + 7;

const int dx[] = {-1, 0, 1, 0, 1, -1, -1, 1};
const int dy[] = {0, 1, 0, -1, 1, -1, 1, -1};

using namespace std;

int n, k;
int a[N], s[N];
ll dp[N][N];
int opt[N][N];

bool upd(ll &x, ll y) {
	if (x < y) {
		x = y;
		return 1;
	}
	return 0;
}

int main() {
	#ifdef IOI2018
		freopen ("in.txt", "r", stdin);
	#endif
	Kazakhstan
	cin >> n >> k;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		s[i] = a[i];
	}
	for (int i = n; i >= 1; i--) {
		s[i] += s[i + 1];
	}
	memset(dp, -0x3f, sizeof(dp));
	for (int i = 1, p = 0; i <= n; i++) {
		p += a[i];
		dp[i][1] = (ll)p * s[i + 1];
		opt[i][1] = i;
	}
	for (int o = 2; o <= k; o++) {
		for (int i = 1; i <= n; i++) {
			int sum = 0;
			for (int j = i; j >= 1; j--) {
				sum += a[j];
				if (upd(dp[i][o], dp[j - 1][o - 1] + (ll)sum * s[i + 1])) {
					opt[i][o] = j;
				}
			}		
		}
	}	
	ll ans = -linf;
	int ptr = -1;
	for (int i = 1; i < n; i++) {
		if (upd(ans, dp[i][k])) {
			ptr = i;
		}
	}
	cout << ans << nl;
	vector <int> res;
	for (int i = k; i >= 1; i--) {
		res.pb(ptr);
		ptr = opt[ptr][i] - 1;
	}	
	reverse(all(res));
	for (auto it : res) {
		cout << it << ' ';
	}
	ioi
}

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