oj.uz

Submission #61621

# Submission time Handle Problem Language Result Execution time Memory
61621 2018-07-26T08:20:43 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 779 ms 102588 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(13, 1300000 / 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);

	return Ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 6 ms 540 KB Output is correct
5 Correct 4 ms 540 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 6 ms 540 KB Output is correct
5 Correct 4 ms 540 KB Output is correct
6 Correct 15 ms 764 KB Output is correct
7 Correct 18 ms 816 KB Output is correct
8 Correct 69 ms 816 KB Output is correct
9 Correct 33 ms 860 KB Output is correct
10 Correct 8 ms 860 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 222 ms 24136 KB Output is correct
2 Correct 689 ms 24136 KB Output is correct
3 Incorrect 779 ms 102588 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 3 ms 540 KB Output is correct
4 Correct 6 ms 540 KB Output is correct
5 Correct 4 ms 540 KB Output is correct
6 Correct 15 ms 764 KB Output is correct
7 Correct 18 ms 816 KB Output is correct
8 Correct 69 ms 816 KB Output is correct
9 Correct 33 ms 860 KB Output is correct
10 Correct 8 ms 860 KB Output is correct
11 Correct 222 ms 24136 KB Output is correct
12 Correct 689 ms 24136 KB Output is correct
13 Incorrect 779 ms 102588 KB Output isn't correct
14 Halted 0 ms 0 KB -