제출 #17255

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
17255		erdemkiraz	휴가 (IOI14_holiday)	C++98	47 / 100	875 ms	10188 KiB

holiday

#include <bits/stdc++.h>

using namespace std;

#define type(x) __typeof((x).begin())
#define foreach(it, x) for(type(x) it = (x).begin(); it != (x).end(); it++)
typedef long long ll;
typedef pair < int, int > ii;

const int inf = 1e9 + 333;
const ll linf = 1e18 + inf;

#include"holiday.h"

const int N = 1e5 + 5;

ll ans = 0;

int n, start, d;
int a[N];

typedef pair < ll, int > pl;

pl t[N << 2];

vector < int > vs;
int id[N];

void add(int x, int l, int r, int x1) {
	if(l == r) {
		t[x].first += vs[x1 - 1];
		t[x].second += 1;
		return;
	}
	int m = l + r >> 1;
	if(x1 <= m)
		add(x + x, l, m, x1);
	else
		add(x + x + 1, m + 1, r, x1);
	t[x] = make_pair(t[x + x].first + t[x + x + 1].first, t[x + x].second + t[x + x + 1].second);
}

void del(int x, int l, int r, int x1) {
	if(l == r) {
		t[x].first -= vs[x1 - 1];
		t[x].second -= 1;
		return;
	}
	int m = l + r >> 1;
	if(x1 <= m)
		del(x + x, l, m, x1);
	else
		del(x + x + 1, m + 1, r, x1);
	t[x] = make_pair(t[x + x].first + t[x + x + 1].first, t[x + x].second + t[x + x + 1].second);
}

ll get(int x, int l, int r, int k) {
	if(l == r) {
		return t[x].second ? t[x].first / t[x].second * min(t[x].second, k) : 0;
	}
	int m = l + r >> 1;
	if(t[x + x + 1].second >= k)
		return get(x + x + 1, m + 1, r, k);
	return t[x + x + 1].first + get(x + x, l, m, k - t[x + x + 1].second);
}

int L, R;

void fix(int l, int r) {
	while(R < r) add(1, 1, n, id[++R]);
	while(R > r) del(1, 1, n, id[R--]);
	while(L > l) add(1, 1, n, id[--L]);
	while(L < l) del(1, 1, n, id[L++]);
}

void solve(int l, int r, int optL, int optR) {
	//printf("l = %d r = %d optL = %d optR = %d\n", l, r, optL, optR);
	if(l > r)
		return;
	int m = l + r >> 1;
	ll res = 0;
	int opt = -1;
	for(int i = optL; i <= optR; i++) {
		if(i > m)
			break;
		fix(i, m);
		ll ret = get(1, 1, n, d - (m - i) - (m - start));
		//printf("i = %d m = %d ret = %d\n", i, m, ret);
		if(opt == -1 or ret > res) {
			ans = max(ans, ret);
			res = ret;
			opt = i;
		}
	}
	solve(l, m - 1, optL, opt);
	solve(m + 1, r, opt, optR);
}

void solveStart() {
	L = 1;
	R = 0;
	memset(t, 0, sizeof(t));
	solve(start, n, 1, n);
}

bool cmp(int x, int y) {
	return a[x] < a[y];
}

int ord[N];

long long int findMaxAttraction(int N, int Start, int D, int Attraction[]) {
	n = N;
	start = Start + 1;
	d = D;
	for(int i = 0; i < n; i++)
		a[i + 1] = Attraction[i];
	for(int i = 1; i <= n; i++) {
		vs.push_back(a[i]);
		ord[i] = i;
	}
	sort(ord + 1, ord + n + 1, cmp);
	for(int i = 1; i <= n; i++)
		id[ord[i]] = i;
	sort(vs.begin(), vs.end());
	solveStart();
	reverse(a + 1, a + n + 1);
	reverse(id + 1, id + n + 1);
	start = n - start + 1;
	solveStart();
	return ans;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53