oj.uz

Submission #61622

# Submission time Handle Problem Language Result Execution time Memory
61622 2018-07-26T08:21:47 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 960 ms 102632 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(16, 1600000 / 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 6 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Correct 6 ms 624 KB Output is correct
5 Correct 3 ms 624 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 6 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Correct 6 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 15 ms 816 KB Output is correct
7 Correct 30 ms 976 KB Output is correct
8 Correct 81 ms 976 KB Output is correct
9 Correct 32 ms 976 KB Output is correct
10 Correct 7 ms 976 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 289 ms 24144 KB Output is correct
2 Correct 749 ms 24144 KB Output is correct
3 Incorrect 960 ms 102632 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 6 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Correct 6 ms 624 KB Output is correct
5 Correct 3 ms 624 KB Output is correct
6 Correct 15 ms 816 KB Output is correct
7 Correct 30 ms 976 KB Output is correct
8 Correct 81 ms 976 KB Output is correct
9 Correct 32 ms 976 KB Output is correct
10 Correct 7 ms 976 KB Output is correct
11 Correct 289 ms 24144 KB Output is correct
12 Correct 749 ms 24144 KB Output is correct
13 Incorrect 960 ms 102632 KB Output isn't correct
14 Halted 0 ms 0 KB -