oj.uz

Submission #61582

# Submission time Handle Problem Language Result Execution time Memory
61582 2018-07-26T07:44:06 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 681 ms 102416 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;
}

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, 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);
			}
		}
	}
	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 oi = 0; oi < __t && oi < N; oi++) {
		rotate(A, A+O[oi], A+N);
		rotate(B, B+O[oi], 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-O[oi], A+N);
		rotate(B, B+N-O[oi], B+N);
	}

	return Ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 7 ms 516 KB Output is correct
3 Correct 9 ms 4672 KB Output is correct
4 Correct 8 ms 4672 KB Output is correct
5 Correct 5 ms 4672 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 7 ms 516 KB Output is correct
3 Correct 9 ms 4672 KB Output is correct
4 Correct 8 ms 4672 KB Output is correct
5 Correct 5 ms 4672 KB Output is correct
6 Correct 31 ms 4672 KB Output is correct
7 Correct 32 ms 4672 KB Output is correct
8 Correct 119 ms 4672 KB Output is correct
9 Correct 45 ms 4672 KB Output is correct
10 Correct 244 ms 5024 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 24124 KB Output is correct
2 Correct 676 ms 24124 KB Output is correct
3 Incorrect 681 ms 102416 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 7 ms 516 KB Output is correct
3 Correct 9 ms 4672 KB Output is correct
4 Correct 8 ms 4672 KB Output is correct
5 Correct 5 ms 4672 KB Output is correct
6 Correct 31 ms 4672 KB Output is correct
7 Correct 32 ms 4672 KB Output is correct
8 Correct 119 ms 4672 KB Output is correct
9 Correct 45 ms 4672 KB Output is correct
10 Correct 244 ms 5024 KB Output is correct
11 Correct 181 ms 24124 KB Output is correct
12 Correct 676 ms 24124 KB Output is correct
13 Incorrect 681 ms 102416 KB Output isn't correct
14 Halted 0 ms 0 KB -