oj.uz

Submission #218398

# Submission time Handle Problem Language Result Execution time Memory
218398 2020-04-02T06:28:14 Z spdskatr Split the sequence (APIO14_sequence) C++14
0 / 100
 260 ms 7032 KB 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <utility>
#include <cstring>
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pii;
typedef pair<long double, int> line;
typedef __int128_t ll;

int N, K, ar[100005], ps[100005];
int cnt[100005], from[100005];
ll dp[100005], m[100005], c[100005];
vector<int> cht;

void ins(int j) {
	m[j] = ps[j];
	c[j] = dp[j] - ps[j]*ps[N];
	while (cht.size() > 1) {
		int s = cht[cht.size() - 2];
		int t = cht[cht.size() - 1];
		if ((c[s] - c[j])*(m[t] - m[s]) <= (c[s] - c[t])*(m[j] - m[s])) {
			cht.pop_back();
		} else break;
	}
	cht.push_back(j);
}


void solve(ll x) {
	memset(dp, 0, sizeof(dp));
	memset(m, 0, sizeof(m));
	memset(c, 0, sizeof(c));
	memset(cnt, 0, sizeof(cnt));
	memset(from, 0, sizeof(from));
	cht.clear();
	int ptr = 0;
	cht.push_back(0);
	for (int i = 1; i <= N; i++) {
		dp[i] = m[cht[ptr]] * ps[i] + c[cht[ptr]];
		cnt[i] = cnt[cht[ptr]] + 1;
		from[i] = cht[ptr];
		while (ptr + 1 < cht.size()) {
			ll nv = m[cht[ptr+1]] * ps[i] + c[cht[ptr+1]];
			if (nv <= dp[i]) break;
			dp[i] = nv;
			cnt[i] = cnt[cht[ptr+1]] + 1;
			from[i] = cht[ptr+1];
			ptr++;
		}
		dp[i] += ps[i] * (ps[N] - ps[i]) - x;
		ins(i);
	}
}

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d", ar+i);
		ps[i] = ps[i-1] + ar[i];
	}
	ll lo = -1, hi = 1e18;
	while (lo + 1 < hi) {
		ll mid = (lo + hi) / 2;
		solve(mid);
		if (cnt[N] > K + 1) lo = mid;
		else hi = mid;
	}
	// Minimised maximum is hi
	//printf("Penalty: %lld\n", (long long)hi);
	solve(hi);
	//printf("Splits: %d\n", cnt[N]);
	ll ans = dp[N] + hi * (K+1);
	printf("%lld\n", (long long)ans);
	int cur = N;
	vector<int> pos;
	while (cur != 0) {
		cur = from[cur];
		if (cur != 0) pos.push_back(cur);
	}
	for (int i = (int)pos.size() - 1; i >= 0; i--) {
		if (i == 0) printf("%d\n", pos[i]);
		else printf("%d ", pos[i]);
	}
	return 0;
}

Compilation message

sequence.cpp: In function 'void solve(ll)':
sequence.cpp:46:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   while (ptr + 1 < cht.size()) {
          ~~~~~~~~^~~~~~~~~~~~
sequence.cpp: In function 'int main()':
sequence.cpp:60: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:62:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", ar+i);
   ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5760 KB contestant found the optimal answer: 108 == 108
2 Correct 23 ms 5760 KB contestant found the optimal answer: 999 == 999
3 Incorrect 19 ms 5760 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 5888 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 22 ms 5760 KB contestant found the optimal answer: 302460000 == 302460000
3 Incorrect 20 ms 5760 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 5760 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 21 ms 5760 KB contestant found the optimal answer: 311760000 == 311760000
3 Incorrect 19 ms 5760 KB Unexpected end of file - int32 expected
4 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 5760 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 23 ms 5888 KB contestant found the optimal answer: 140412195 == 140412195
3 Incorrect 23 ms 5760 KB declared answer doesn't correspond to the split scheme: declared = 16195992064253394, real = 17902527208914
4 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

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

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 260 ms 7032 KB declared answer doesn't correspond to the split scheme: declared = 135571871800, real = 6722852920
2 Halted 0 ms 0 KB -