oj.uz

답안 #61564

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61564 2018-07-26T07:36:38 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 831 ms 86784 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;

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, 1000000 / 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+N+1, 0);
	srand(20010610);
	random_shuffle(O, O+N);

	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];
		
		deque<pil> PQ;
		ll mx1 = -INFLL;
		for(int i = 0; i < N-K; i++) {
			if(0 <= i-K) upmax(mx1, dp[i-K]);
			for(; !PQ.empty() && PQ[0].first < max(0, i-K+1); PQ.pop_front());
			ll &ret = dp[i];
			ret = ll(A[i]) - S[i+K] + S[i];
			if(!PQ.empty()) upmax(ret, PQ[0].second + A[i] - S[i+K]);
			upmax(ret, mx1 + A[i] - S[i+K] + S[i]);

			ll t = ret + S[i+K];
			for(; !PQ.empty() && PQ.back().second <= t; PQ.pop_back());
			PQ.pb(pil(i, t));

			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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 548 KB Output is correct
3 Correct 4 ms 548 KB Output is correct
4 Correct 8 ms 548 KB Output is correct
5 Correct 4 ms 632 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 548 KB Output is correct
3 Correct 4 ms 548 KB Output is correct
4 Correct 8 ms 548 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 11 ms 700 KB Output is correct
7 Correct 18 ms 832 KB Output is correct
8 Correct 94 ms 832 KB Output is correct
9 Correct 33 ms 876 KB Output is correct
10 Correct 8 ms 876 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 224 ms 26060 KB Output is correct
2 Correct 743 ms 26060 KB Output is correct
3 Incorrect 831 ms 86784 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 6 ms 548 KB Output is correct
3 Correct 4 ms 548 KB Output is correct
4 Correct 8 ms 548 KB Output is correct
5 Correct 4 ms 632 KB Output is correct
6 Correct 11 ms 700 KB Output is correct
7 Correct 18 ms 832 KB Output is correct
8 Correct 94 ms 832 KB Output is correct
9 Correct 33 ms 876 KB Output is correct
10 Correct 8 ms 876 KB Output is correct
11 Correct 224 ms 26060 KB Output is correct
12 Correct 743 ms 26060 KB Output is correct
13 Incorrect 831 ms 86784 KB Output isn't correct
14 Halted 0 ms 0 KB -