oj.uz

답안 #797376

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797376 2023-07-29T10:10:28 Z Sohsoh84 휴가 (IOI14_holiday) C++17
100 / 100
 1053 ms 17240 KB 
#include "holiday.h"
#include <bits/stdc++.h>

typedef long long ll;

#define debug(x)	cerr << #x << ": " << x << endl;
#define sep		' '

const int MAXN = 2e5 + 10;

using namespace std;

ll A[MAXN], n;

namespace sack {
	ll score = 0;
	int len, d;
	multiset<int> st;
	vector<pair<int,  vector<int>>> history;

	inline void init(int d_) {
		d = d_;
		st.clear();
		history.clear();
	}

	inline void add(int x) {
		len++;
		vector<int> er_vec;
		
		st.insert(x);
		score += x;

		while (int(st.size()) > max(0, d - len + 1)) {
			er_vec.push_back(*st.begin());	
			score -= *st.begin();
			st.erase(st.begin());
		}

		history.push_back({x, er_vec});
	}

	inline void rollback() {
		len--;
		auto [x, y] = history.back();
		history.pop_back();

		for (int e : y) {
			st.insert(e);
			score += e;
		}

		st.erase(st.find(x));
		score -= x;
	}

	inline void rollback(int k) {
		while (k--) rollback();
	}
}

ll divide(int l, int r, int optl, int optr) { // (r, optl]
	if (r < l) return 0;

	int mid = (l + r) >> 1;
	for (int i = r; i >= mid; i--) sack::add(A[i]);

	ll ans = sack::score, opt = optl;
	for (int i = optl + 1; i <= optr; i++) {
		sack::add(A[i]);
		if (sack::score > ans) {
			ans = sack::score;
			opt = i;
		}
	}

	sack::rollback(optr - optl);
	ans = max(ans, divide(l, mid - 1, optl, opt));
	sack::rollback(r - mid + 1);
	for (int i = optl + 1; i <= opt; i++) sack::add(A[i]);
	ans = max(ans, divide(mid + 1, r, opt, optr));
	sack::rollback(opt - optl);

	return ans;

}

inline ll solve(int n_, int start, int d, int attraction[]) {
	memset(A, 0, sizeof A);
	n = 0;

	for (int i = 0; i < n_; i++) {
		if (i > start) A[n++] = 0;
		A[n++] = attraction[i];
	}

	sack::init(d);
	return divide(max(0, start - d), start, start, min(ll(start + d), n - 1));
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	ll ans = solve(n, start, d, attraction);
	reverse(attraction, attraction + n);
	ans = max(ans, solve(n, n - 1 - start, d, attraction));
	return ans;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 1 ms 2232 KB Output is correct
6 Correct 1 ms 2260 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 221 ms 15256 KB Output is correct
2 Correct 194 ms 15236 KB Output is correct
3 Correct 234 ms 15252 KB Output is correct
4 Correct 209 ms 15316 KB Output is correct
5 Correct 402 ms 9720 KB Output is correct
6 Correct 85 ms 6724 KB Output is correct
7 Correct 205 ms 8696 KB Output is correct
8 Correct 242 ms 8532 KB Output is correct
9 Correct 56 ms 5816 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 7 ms 2644 KB Output is correct
2 Correct 5 ms 2624 KB Output is correct
3 Correct 5 ms 2644 KB Output is correct
4 Correct 28 ms 2500 KB Output is correct
5 Correct 23 ms 2516 KB Output is correct
6 Correct 4 ms 2260 KB Output is correct
7 Correct 5 ms 2260 KB Output is correct
8 Correct 6 ms 2224 KB Output is correct
9 Correct 6 ms 2260 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 232 ms 17240 KB Output is correct
2 Correct 252 ms 17112 KB Output is correct
3 Correct 166 ms 3408 KB Output is correct
4 Correct 13 ms 2388 KB Output is correct
5 Correct 5 ms 2320 KB Output is correct
6 Correct 6 ms 2316 KB Output is correct
7 Correct 7 ms 2304 KB Output is correct
8 Correct 1052 ms 8760 KB Output is correct
9 Correct 1053 ms 8668 KB Output is correct