oj.uz

답안 #763998

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
763998 2023-06-23T05:09:00 Z SanguineChameleon 휴가 (IOI14_holiday) C++17
100 / 100
 2416 ms 19008 KB 
#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;

const long long inf = 1e18L + 20;
const int maxn = 1e5 + 20;

struct tree {
	vector<long long> *A;
	vector<long long> *B;
	int tree[maxn * 16];

	void build(int id, int lt, int rt) {
		tree[id] = -1;
		if (lt == rt) {
			return;
		}
		int mt = (lt + rt) / 2;
		build(id * 2, lt, mt);
		build(id * 2 + 1, mt + 1, rt);
	}

	long long eval(int off, int pos) {
		if (off == -1) {
			return -inf;
		}
		else {
			return (*A)[off] + (*B)[pos - off];
		}
	}

	void update(int id, int lt, int rt, int off, int ql, int qr) {
		if (qr < lt || ql > rt) {
			return;
		}
		if (lt == rt) {
			if (eval(off, lt) > eval(tree[id], lt)) {
				tree[id] = off;
			}
			return;
		}
		int mt = (lt + rt) / 2;
		if (ql <= lt && rt <= qr) {
			bool cmp1 = eval(off, lt) > eval(tree[id], lt);
			bool cmp2 = eval(off, mt) > eval(tree[id], mt);
			if (cmp1 != cmp2) {
				if (cmp2) {
					swap(tree[id], off);
				}
				update(id * 2, lt, mt, off, ql, qr);
			}
			else {
				if (cmp1) {
					swap(tree[id], off);
				}
				update(id * 2 + 1, mt + 1, rt, off, ql, qr);
			}
			return;
		}
		update(id * 2, lt, mt, off, ql, qr);
		update(id * 2 + 1, mt + 1, rt, off, ql, qr);
	}

	long long get(int id, int lt, int rt, int pos) {
		if (lt == rt) {
			return eval(tree[id], pos);
		}
		int mt = (lt + rt) / 2;
		if (pos <= mt) {
			return max(eval(tree[id], pos), get(id * 2, lt, mt, pos));
		}
		else {
			return max(eval(tree[id], pos), get(id * 2 + 1, mt + 1, rt, pos));
		}
	}

} T;

vector<long long> calc(vector<int> a) {
	int n = a.size();
	vector<long long> res(n * 2 + 1);
	if (n == 0) {
		return res;
	}
	if (n == 1) {
		res[2] = a[0];
		return res;
	}
	vector<int> left(a.begin(), a.begin() + n / 2);
	vector<int> right(a.begin() + n / 2, a.end());
	vector<long long> best_l = calc(left);
	vector<long long> best_r = calc(right);
	for (int i = 0; i <= (n / 2) * 2; i++) {
		res[i] = best_l[i];
	}
	for (int i = 0; i < n / 2; i++) {
		best_l[i] = -inf;
	}
	best_l[n / 2] = 0;
	sort(left.begin(), left.end(), greater<int>());
	for (int i = n / 2 + 1; i <= (n / 2) * 2; i++) {
		best_l[i] = best_l[i - 1] + left[i - n / 2 - 1];
	}
	T.A = &best_r;
	T.B = &best_l;
	T.build(1, n / 2, n * 2);
	for (int i = 0; i <= (n - n / 2) * 2; i++) {
		T.update(1, n / 2, n * 2, i, i + n / 2, i + (n / 2) * 2);
	}
	for (int i = n / 2; i <= n * 2; i++) {
		res[i] = max(res[i], T.get(1, n / 2, n * 2, i));
	}
	for (int i = 1; i <= n / 2; i++) {
		res[i] = max(res[i], res[i - 1]);
	}
	return res;
}

long long solve(int n, int start, int d, int attraction[]) {
	vector<int> left(start * 2);
	for (int i = 0; i < start; i++) {
		left[i * 2] = 0;
		left[i * 2 + 1] = attraction[start - 1 - i];
	}
	vector<int> right(n - 1 - start);
	for (int i = start + 1; i < n; i++) {
		right[i - start - 1] = attraction[i];
	}
	vector<long long> best_l = calc(left);
	vector<long long> best_r = calc(right);
	best_l.resize(d + 1);
	best_r.resize(d + 1);
	for (int i = 1; i <= d; i++) {
		best_l[i] = max(best_l[i], best_l[i - 1]);
		best_r[i] = max(best_r[i], best_r[i - 1]);
	}
	long long res = 0;
	for (int i = 0; i <= d; i++) {
		res = max(res, best_l[i] + best_r[d - i]);
	}
	for (int i = 0; i <= d - 1; i++) {
		res = max(res, best_l[i] + best_r[d - 1 - i] + attraction[start]);
	}
	return res;
}

long long findMaxAttraction(int n, int start, int d, int attraction[]) {
	long long res1 = solve(n, start, d, attraction);
	for (int i = 0; i < n - 1 - i; i++) {
		swap(attraction[i], attraction[n - 1 - i]);
	}
	start = n - 1 - start;
	long long res2 = solve(n, start, d, attraction);
	return max(res1, res2);
}

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2332 ms 17980 KB Output is correct
2 Correct 2218 ms 18388 KB Output is correct
3 Correct 2416 ms 18292 KB Output is correct
4 Correct 2144 ms 18332 KB Output is correct
5 Correct 2149 ms 15172 KB Output is correct
6 Correct 513 ms 6536 KB Output is correct
7 Correct 1055 ms 8680 KB Output is correct
8 Correct 1307 ms 10104 KB Output is correct
9 Correct 336 ms 6216 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 34 ms 1224 KB Output is correct
2 Correct 32 ms 1228 KB Output is correct
3 Correct 34 ms 1124 KB Output is correct
4 Correct 27 ms 1040 KB Output is correct
5 Correct 25 ms 980 KB Output is correct
6 Correct 8 ms 852 KB Output is correct
7 Correct 8 ms 820 KB Output is correct
8 Correct 8 ms 724 KB Output is correct
9 Correct 10 ms 852 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2308 ms 16072 KB Output is correct
2 Correct 2292 ms 19008 KB Output is correct
3 Correct 771 ms 5748 KB Output is correct
4 Correct 26 ms 980 KB Output is correct
5 Correct 9 ms 824 KB Output is correct
6 Correct 8 ms 692 KB Output is correct
7 Correct 8 ms 696 KB Output is correct
8 Correct 2143 ms 10508 KB Output is correct
9 Correct 2092 ms 10436 KB Output is correct