oj.uz

답안 #550710

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
550710 2022-04-18T21:25:25 Z sidon 휴가 (IOI14_holiday) C++17
100 / 100
 251 ms 2704 KB 
#include<bits/stdc++.h>
using namespace std;
using i64 = long long;

const int Z = 1e5;

int n, *a, d, o, C[Z], G[Z+1], L = 1, R;
i64 F[Z+1], ans;

void add(const int &j, const int &s) {
	for(int i = 1 + C[j]; i <= n; i += i&-i) {
		G[i] += s;
		F[i] += s * a[j];
	}
}

i64 get(int v) {
	int i {}; i64 res {};
	for(int j = 1<<17; j /= 2; ) if(i + j <= n && G[i + j] <= v) {
		i += j;
		res += F[i];
		v -= G[i];
	}
	return res;
}

void reset(const int &l, const int &r) {
	while(L > l) add(--L, +1);
	while(R < r) add(++R, +1);
	while(L < l) add(L++, -1);
	while(R > r) add(R--, -1);
}

void dfs(int li, int ri, int lv, int rv) {
	if(ri <= li) return;
	int mi = (li + ri) / 2;
	i64 best {};

	int sv = max(mi, lv), mv = sv;
	reset(mi, sv - 1);
	for(int v = sv; v < rv; ++v) {
		add(++R, 1);
		i64 cur = get(max((int)(0), d - min(abs(o - mi), abs(o - v)) - (v - mi)));
		if(cur > best) best = cur, mv = v;
	}
	ans = max(ans, best);

	dfs(li, mi, lv, mv + 1);
	dfs(mi + 1, ri, mv, rv);
}

i64 findMaxAttraction(int _n, int start, int _d, int _a[]) {
	a = _a, n = _n, d = _d, o = start;
	int byA[n];
	iota(byA, byA + n, 0);
	sort(byA, byA + n, [&](const int &i, const int &j) {
		return a[i] > a[j];
	});
	for(int i = 0; i < n; ++i) C[byA[i]] = i;
	dfs(0, n, 0, n);
	return ans;
}

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 162 ms 2628 KB Output is correct
2 Correct 124 ms 2644 KB Output is correct
3 Correct 160 ms 2624 KB Output is correct
4 Correct 119 ms 2628 KB Output is correct
5 Correct 221 ms 2468 KB Output is correct
6 Correct 48 ms 1240 KB Output is correct
7 Correct 86 ms 1620 KB Output is correct
8 Correct 121 ms 1884 KB Output is correct
9 Correct 33 ms 980 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 182 ms 2704 KB Output is correct
2 Correct 162 ms 2628 KB Output is correct
3 Correct 80 ms 1492 KB Output is correct
4 Correct 6 ms 756 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 2 ms 724 KB Output is correct
7 Correct 2 ms 724 KB Output is correct
8 Correct 251 ms 2620 KB Output is correct
9 Correct 238 ms 2620 KB Output is correct