oj.uz

Submission #797532

# Submission time Handle Problem Language Result Execution time Memory
797532 2023-07-29T14:57:00 Z beaboss Split the sequence (APIO14_sequence) C++14
0 / 100
 13 ms 10068 KB 
// Source: https://docs.google.com/document/d/1ryBjActxSlAAeTMRNUmJzWOGQ21ZuS32mQYTD8rHXzE/edit

#include "bits/stdc++.h"

using namespace std;

#define s second
#define f first
#define pb push_back

typedef long long ll;

typedef pair<ll, ll> pii;
typedef vector<pii> vpii;

typedef vector<ll> vi;

#define FOR(i, a, b) for (ll i = (a); i<b; i++)


struct line {
	ll m, b;
	ll eval(ll x) {return m * x + b; }
	ll isectX(line l) {return (l.b - b) / (m - l.m); }
};

vector<deque<line> > lines(300);

vi ints(1000000);

void add(ll i, line l) {

	while (lines[i].size() > 1 && ((l.m == lines[i].back().m) || l.isectX((lines[i].back())) <= l.isectX((lines[i][lines[i].size() - 1])))) {
		lines[i].pop_back();
	}
	lines[i].push_back(l);
}


ll query(ll i, ll x) {
	// if (lines[i].size() > 1) cout << lines[i][1].m << ' ' << lines[i][1].b << endl;
	while (lines[i].size() > 1 && lines[i][0].isectX(lines[i][1]) < x) {

		lines[i].pop_front();
	}

	return lines[i][0].eval(x);
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	iota(ints.begin(), ints.end(), 0);

	ll n, k;
	cin >> n >> k;

	vi vals(n + 1);
	vi pref(n + 1);

	FOR(i, 1, n + 1) {
		cin >> vals[i];
		pref[i] = vals[i] + pref[i-1];
	}

	add(0, {0, 0});

	ll ans = 0;

	FOR(i, 1, n + 1) {
		for (ll j = k; j>= 1; j--) {
			ll cur = pref[i] * pref[n] - pref[i] * pref[i] + query(j-1, pref[i]);
			// cout << i << j << cur << endl;
			add(j, {pref[i], cur - pref[i] * pref[n]});

			if (j == k) ans = max(ans, cur);
		}
	}

	cout << ans << endl;
}

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8276 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8368 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8276 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8368 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 8532 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 10068 KB Unexpected end of file - int32 expected
2 Halted 0 ms 0 KB -