oj.uz

Submission #61592

# Submission time Handle Problem Language Result Execution time Memory
61592 2018-07-26T07:49:23 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 1000 ms 26172 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(11, 1100000 / 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);
			}
		}
	}

	process(0);

	iota(O, O+N, 0);
	srand(20010610);
	random_shuffle(O, O+N);
	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]-A[a] > B[b]-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 4 ms 380 KB Output is correct
2 Correct 8 ms 484 KB Output is correct
3 Correct 8 ms 4760 KB Output is correct
4 Correct 13 ms 4760 KB Output is correct
5 Correct 5 ms 4760 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 8 ms 484 KB Output is correct
3 Correct 8 ms 4760 KB Output is correct
4 Correct 13 ms 4760 KB Output is correct
5 Correct 5 ms 4760 KB Output is correct
6 Correct 38 ms 4760 KB Output is correct
7 Correct 44 ms 4760 KB Output is correct
8 Correct 150 ms 4760 KB Output is correct
9 Correct 54 ms 4760 KB Output is correct
10 Correct 283 ms 5052 KB Output is correct

Subtask #3
0 / 31.0

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

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 380 KB Output is correct
2 Correct 8 ms 484 KB Output is correct
3 Correct 8 ms 4760 KB Output is correct
4 Correct 13 ms 4760 KB Output is correct
5 Correct 5 ms 4760 KB Output is correct
6 Correct 38 ms 4760 KB Output is correct
7 Correct 44 ms 4760 KB Output is correct
8 Correct 150 ms 4760 KB Output is correct
9 Correct 54 ms 4760 KB Output is correct
10 Correct 283 ms 5052 KB Output is correct
11 Correct 325 ms 26172 KB Output is correct
12 Execution timed out 1084 ms 26172 KB Time limit exceeded
13 Halted 0 ms 0 KB -