oj.uz

Submission #61586

# Submission time Handle Problem Language Result Execution time Memory
61586 2018-07-26T07:45:43 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 891 ms 102508 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(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);
			}
		}
	}
	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 504 KB Output is correct
2 Correct 6 ms 616 KB Output is correct
3 Correct 11 ms 5536 KB Output is correct
4 Correct 7 ms 5536 KB Output is correct
5 Correct 4 ms 5536 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 6 ms 616 KB Output is correct
3 Correct 11 ms 5536 KB Output is correct
4 Correct 7 ms 5536 KB Output is correct
5 Correct 4 ms 5536 KB Output is correct
6 Correct 31 ms 5536 KB Output is correct
7 Correct 32 ms 5536 KB Output is correct
8 Correct 93 ms 5536 KB Output is correct
9 Correct 37 ms 5536 KB Output is correct
10 Correct 279 ms 5740 KB Output is correct

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 24200 KB Output is correct
2 Correct 556 ms 24200 KB Output is correct
3 Incorrect 891 ms 102508 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 504 KB Output is correct
2 Correct 6 ms 616 KB Output is correct
3 Correct 11 ms 5536 KB Output is correct
4 Correct 7 ms 5536 KB Output is correct
5 Correct 4 ms 5536 KB Output is correct
6 Correct 31 ms 5536 KB Output is correct
7 Correct 32 ms 5536 KB Output is correct
8 Correct 93 ms 5536 KB Output is correct
9 Correct 37 ms 5536 KB Output is correct
10 Correct 279 ms 5740 KB Output is correct
11 Correct 213 ms 24200 KB Output is correct
12 Correct 556 ms 24200 KB Output is correct
13 Incorrect 891 ms 102508 KB Output isn't correct
14 Halted 0 ms 0 KB -