oj.uz

Submission #337224

# Submission time Handle Problem Language Result Execution time Memory
337224 2020-12-19T01:46:37 Z penguinhacker Split the sequence (APIO14_sequence) C++14
0 / 100
 70 ms 131076 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN = 100001;
int n, k, a[mxN];
ll pre[mxN];
ll dp[mxN][201];
int last[mxN][201];

struct Line {
	ll m, b, ind;
	ll eval(ll x) {return m * x + b;}
};
double isect(Line& a, Line& b) {
	return (double)(a.b - b.b) / (b.m - a.m);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		pre[i] = pre[i - 1] + a[i];
	}
	for (int i = 1; i <= n; ++i) {
		dp[i][1] = pre[i] * (pre[n] - pre[i]);
	}
	for (int rep = 2; rep <= k; ++rep) {
		deque<Line> dq;
		for (int i = rep; i < n; ++i) {
			Line cur = {pre[i - 1], dp[i - 1][rep - 1] - pre[n] * pre[i - 1], i - 1};
			while(dq.size() >= 2 && isect(cur, dq[dq.size() - 2]) < isect(dq.back(), dq[dq.size() - 2]))
				dq.pop_back();
			dq.push_back(cur);
			while(dq.size() >= 2 && dq[1].eval(pre[i]) > dq[0].eval(pre[i]))
				dq.pop_front();
			dp[i][rep] = pre[i] * (pre[n] - pre[i]) + dq[0].eval(pre[i]);
			last[i][rep] = dq[0].ind;
		}
	}
	int ind = -1;
	for (int i = k; i < n; ++i) {
		if (ind == -1 || dp[i][k] > dp[ind][k]) {
			ind = i;
		}
	}
	cout << dp[ind][k] << "\n";
	for (int i = k; i >= 1; --i) {
		cout << ind << " ";
		ind = last[ind][i];
	}
	return 0;
}
// notes
// dp[i] = dp[j] + (pre[i] - pre[j]) * (pre[n] - pre[i]);
// dp[i] = pre[i] * (pre[n] - pre[i]) + max(pre[j] * pre[i] + dp[j] - pre[n] * pre[j])

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB contestant found the optimal answer: 108 == 108
2 Correct 1 ms 364 KB contestant found the optimal answer: 999 == 999
3 Correct 1 ms 364 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 364 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 1 ms 364 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 1 ms 364 KB contestant found the optimal answer: 1 == 1
7 Correct 0 ms 364 KB contestant found the optimal answer: 1 == 1
8 Correct 1 ms 364 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 384 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 364 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 1 ms 376 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 1 ms 364 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Incorrect 1 ms 364 KB contestant didn't find the optimal answer: 140067 < 140072
14 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB contestant didn't find the optimal answer: 1092256 < 1093956
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 876 KB contestant didn't find the optimal answer: 407161746 < 610590000
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2796 KB contestant didn't find the optimal answer: 20166072 < 21503404
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 24324 KB contestant didn't find the optimal answer: 1197227828 < 1818678304
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 70 ms 131076 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -