oj.uz

Submission #61500

# Submission time Handle Problem Language Result Execution time Memory
61500 2018-07-26T05:54:19 Z ainta(#1774) Homecoming (BOI18_homecoming) C++11
0 / 100
 95 ms 16152 KB 
#include "homecoming.h"
#include <algorithm>
#define N_ 2010000
using namespace std;

int A[N_], B[N_], n, K;
long long D[N_][2], res;

void Do() {
	int i;
	for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
	D[1][0] = B[1];
	for (i = 2; i <= n; i++) {
		D[i][0] = D[i - 1][0] + B[i];
		if (i >= K)D[i][0] = max(D[i][0], D[i - K + 1][1]);
		D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
	}
	res = max(res, D[n][0]);
	for (i = 0; i <= n; i++)D[i][0] = D[i][1] = -1e18;
	D[1][1] = A[1];
	for (i = 2; i <= n; i++) {
		D[i][0] = D[i - 1][0] + B[i];
		if (i >= K)D[i][0] = max(D[i][0], D[i - K + 1][1]);
		D[i][1] = max(max(D[i - 1][1], D[i - 1][0]) + A[i], D[i][0]);
	}
	res = max(res, max(D[n][0], D[n][1]));
}

void Rotate() {
	int i;
	int ta = A[1], tb = B[1];
	for (i = 1; i < n; i++)A[i] = A[i + 1], B[i] = B[i + 1];
	A[n] = ta, B[n] = tb;
}

long long int solve(int N, int k, int *a, int *b) {
	int i;
	n = N, K = k;
	if (K == 1) {
		long long r = 0;
		for (i = 0; i < n; i++) {
			r += max(a[i]-b[i],0);
		}
		return r;
	}
	for (i = 1; i <= n; i++)A[i] = a[i - 1], B[i] = b[i - 1];
	for (i = 0; i < K; i++) {
		Do();
		Rotate();
	}
	for (i = 1; i <= n; i++)res -= B[i];
	return res;
}

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Incorrect 3 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Incorrect 3 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 16152 KB Output is correct
2 Incorrect 29 ms 16152 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 376 KB Output is correct
2 Correct 6 ms 376 KB Output is correct
3 Incorrect 3 ms 432 KB Output isn't correct
4 Halted 0 ms 0 KB -