oj.uz

답안 #61568

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
61568 2018-07-26T07:38:41 Z 윤교준(#1780) Homecoming (BOI18_homecoming) C++11
31 / 100
 1000 ms 86868 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(12, 1400000 / 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 0 ms 376 KB Output is correct
2 Correct 6 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 10 ms 484 KB Output is correct
5 Correct 4 ms 484 KB Output is correct

Subtask #2
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 6 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 10 ms 484 KB Output is correct
5 Correct 4 ms 484 KB Output is correct
6 Correct 17 ms 600 KB Output is correct
7 Correct 23 ms 852 KB Output is correct
8 Correct 89 ms 852 KB Output is correct
9 Correct 31 ms 852 KB Output is correct
10 Correct 9 ms 852 KB Output is correct

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 249 ms 26216 KB Output is correct
2 Correct 643 ms 26216 KB Output is correct
3 Execution timed out 1031 ms 86868 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 376 KB Output is correct
2 Correct 6 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 10 ms 484 KB Output is correct
5 Correct 4 ms 484 KB Output is correct
6 Correct 17 ms 600 KB Output is correct
7 Correct 23 ms 852 KB Output is correct
8 Correct 89 ms 852 KB Output is correct
9 Correct 31 ms 852 KB Output is correct
10 Correct 9 ms 852 KB Output is correct
11 Correct 249 ms 26216 KB Output is correct
12 Correct 643 ms 26216 KB Output is correct
13 Execution timed out 1031 ms 86868 KB Time limit exceeded
14 Halted 0 ms 0 KB -