Submission #855387

#	Time	Username	Problem	Language	Result	Execution time	Memory
855387		vjudge1	Split the sequence (APIO14_sequence)	C++17	0 / 100	5 ms	4444 KiB

sequence

//srand(time(0)) - always changing
//order_of_key(k): Number of items strictly smaller than k .
//find_by_order(k): K-th element in a set (counting from zero).

//#pragma GCC optimize("O3,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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

#define file(s) if(fopen(s".in","r")) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define all(x) (x).begin(), (x).end()
#define len(x) (int)x.size()
#define tm (tl + tr >> 1)
#define ls v << 1, tl, tm
#define rs v << 1 | 1, tm + 1, tr
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define elif else if
#define F first
#define S second
#define int long long

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef unsigned long long ull;
typedef long long ll;
typedef double db;
typedef long double ld;

const int MOD = 1e9 + 7;
const int N = 2e5 + 7;
const int P = 911;
const ll INF = 1e18;

int gcd(int a, int b) {
	while (b) {
		a %= b;
		swap (a, b);
	}
	return a;
}

ll __sqrt(ll x) {
	ll result = 0;
	for (ll k = 1ll << 30; k != 0; k >>= 1) {
		if ((result + k) * (result + k) <= x) {
			result += k;
		}
	}
	return result;
}

int a[1010], p[1010], dp[1010][1010][2];

int sum(int l, int r) {
	return p[r] - p[l - 1];
}

void GazizMadi() {
	int n, m, ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		p[i] = p[i - 1] + a[i];
	}
	for (int i = 1; i < n; i++) {
		for (int k = 1; k <= min(i, m); k++) {
			for (int j = 1; j <= i; j++) {
				if (dp[i][k][0] < dp[j - 1][k - 1][0] + sum(j, i) * sum(i + 1, n)) {
					dp[i][k][0] = dp[j - 1][k - 1][0] + sum(j, i) * sum(i + 1, n);
					dp[i][k][1] = j;
				}
			}
//			cout << i << ' ' << k << ' ' << dp[i][k][0] << '\n';
		}
		if (dp[ans][m][0] < dp[i][m][0]) {
			ans = i;
		}
	}
	
	cout << dp[ans][m][0] << '\n';
	vector <int> act;
	while (m--) {
		act.pb(ans);
		ans = dp[ans][m][1];
	}
	reverse(all(act));
	for (int it: act) {
		cout << it << ' ';
	}
}

const bool Cases = 0;

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int TT = 1;
	if (Cases) cin >> TT;
	for (int i = 1; i <= TT; i++) {
		//cout << "Case " << i << ": ";
		GazizMadi();
	}
}

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