oj.uz

Submission #61614

# Submission time Handle Problem Language Result Execution time Memory
61614 2018-07-26T08:10:39 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 1000 ms 24148 KB 
#include "homecoming.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define revv(V) reverse(allv(V))
#define sz(V) ((int)(V).size())
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;

const int MAXN = 2000005;

int PQF[MAXN]; ll PQS[MAXN]; int PQs, PQe;

ll dp[MAXN], S[MAXN*2];
int A[MAXN], B[MAXN];
int O[MAXN];

ll Ans;
int N, K;

void init() {
	Ans = 0;
}

void process(int XX) {
	rotate(A, A+XX, A+N);
	rotate(B, B+XX, B+N);

	S[0] = 0;
	for(int i = 1; i <= N; i++)
		S[i] = S[i-1] + B[i-1];

	PQs = PQe = 0;
	ll mx1 = -INFLL;
	for(int i = 0; i < N-K; i++) {
		if(0 <= i-K) upmax(mx1, dp[i-K]);
		for(; PQs < PQe && PQF[PQs] < max(0, i-K+1); PQs++);
		ll &ret = dp[i];
		ret = ll(A[i]) - S[i+K] + S[i];
		if(PQs < PQe) upmax(ret, PQS[PQs] + A[i] - S[i+K]);
		upmax(ret, mx1 + A[i] - S[i+K] + S[i]);

		ll t = ret + S[i+K];
		for(; PQs < PQe && PQS[PQe-1] <= t; PQe--);
		PQF[PQe] = i; PQS[PQe] = t; PQe++;

		upmax(Ans, ret);
	}

	rotate(A, A+N-XX, A+N);
	rotate(B, B+N-XX, B+N);
}

ll solve(int _N, int _K, int *_A, int *_B) {
	init();
	N = _N; K = _K;
	for(int i = 0; i < N; i++) {
		A[i] = A[i+N] = _A[i];
		B[i] = B[i+N] = _B[i];
	}

	int __t = max(10, 1000000 / N);

	{
		ll sum = 0;
		for(int i = 0; i < N; i++)
			sum += ll(A[i]) - B[i];
		upmax(Ans, sum);

		sum = 0;
		for(int i = 0; i < N; i++) sum += B[i];

		S[0] = 0;
		for(int i = 1; i <= N; i++)
			S[i] = S[i-1] + A[i-1];
		for(int i = 1; i <= N; i++)
			S[i+N] = S[i+N-1] + A[i-1];
		for(int i = 0; i < N; i++) {
			ll bsum = sum;
			for(int l = 1; l <= __t && l+K <= N; l++) {
				bsum -= B[i+l-1];
				upmax(Ans, S[i+N-K+1] - S[i+l] - bsum);
			}
		}
	}

	for(int i : {N-1, 0, 1}) process(i);

	srand(20010610);
	for(int i = 0; i < __t && i < N; i++)
		process(rand() % N);

	iota(O, O+__t, 0);
	for(int i = __t; i < N; i++) {
		O[__t] = i;
		sort(O, O+__t+1, [&](int a, int b) { return B[a]-A[a] > B[b]-A[b]; });
	}
	for(int i = 0; i < __t && i < N; i++)
		process(O[i]);

	iota(O, O+__t, 0);
	for(int i = __t; i < N; i++) {
		O[__t] = i;
		sort(O, O+__t+1, [&](int a, int b) { return B[a] > B[b]; });
	}
	for(int i = 0; i < __t && i < N; i++)
		process(O[i]);

	iota(O, O+__t, 0);
	for(int i = __t; i < N; i++) {
		O[__t] = i;
		sort(O, O+__t+1, [&](int a, int b) { return A[a] < A[b]; });
	}
	for(int i = 0; i < __t && i < N; i++)
		process(O[i]);

	return Ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 13 ms 484 KB Output is correct
3 Correct 15 ms 4528 KB Output is correct
4 Correct 25 ms 4528 KB Output is correct
5 Correct 8 ms 4528 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 13 ms 484 KB Output is correct
3 Correct 15 ms 4528 KB Output is correct
4 Correct 25 ms 4528 KB Output is correct
5 Correct 8 ms 4528 KB Output is correct
6 Correct 82 ms 4528 KB Output is correct
7 Correct 81 ms 4528 KB Output is correct
8 Correct 286 ms 4528 KB Output is correct
9 Correct 132 ms 4528 KB Output is correct
10 Correct 776 ms 4704 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 534 ms 24148 KB Output is correct
2 Execution timed out 1088 ms 24148 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 13 ms 484 KB Output is correct
3 Correct 15 ms 4528 KB Output is correct
4 Correct 25 ms 4528 KB Output is correct
5 Correct 8 ms 4528 KB Output is correct
6 Correct 82 ms 4528 KB Output is correct
7 Correct 81 ms 4528 KB Output is correct
8 Correct 286 ms 4528 KB Output is correct
9 Correct 132 ms 4528 KB Output is correct
10 Correct 776 ms 4704 KB Output is correct
11 Correct 534 ms 24148 KB Output is correct
12 Execution timed out 1088 ms 24148 KB Time limit exceeded
13 Halted 0 ms 0 KB -