oj.uz

답안 #7442

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
7442 2014-08-05T18:48:51 Z ainta 휴가 (IOI14_holiday) C++
100 / 100
 1224 ms 6628 KB 
#include"holiday.h"
#include<algorithm>
using namespace std;
#define SZ 131072
#define N_ 100010
long long Res;
struct A{
	int a, num;
	bool operator <(const A &p)const{
		return a < p.a;
	}
}ord[N_];
struct ST{
	long long Sum;
	int C;
}IT[SZ*2+2];
int num[N_], N;
void Ins(int node, int b, int e, int x, int ck){
	if (b == e){
		if (ck == IT[node].C)return;
		if (ck){
			IT[node].C = 1;
			IT[node].Sum = ord[b].a;
		}
		else{
			IT[node].C = 0, IT[node].Sum = 0;
		}
		return;
	}
	int m = (b + e) >> 1;
	if (x <= m)Ins(node * 2, b, m, x, ck);
	else Ins(node * 2 + 1, m + 1, e, x, ck);
	IT[node].Sum = IT[node * 2].Sum + IT[node * 2 + 1].Sum;
	IT[node].C = IT[node * 2].C + IT[node * 2 + 1].C;
}
long long Gap(int node, int x){
	if (IT[node].C <= x)return IT[node].Sum;
	if (IT[node * 2 + 1].C >= x) return Gap(node * 2 + 1, x);
	else return IT[node * 2 + 1].Sum + Gap(node * 2, x - IT[node * 2 + 1].C);
}
void DP(int st, int b, int e, int s, int l, int d){
	if (b > e)return;
	int m = (b + e) >> 1, i, t, x;
	long long M = 0, S;
	for (i = m; i <= e; i++)
		Ins(1, 0, SZ-1, num[i], 1);
	for (i = s; i <= l; i++){
		Ins(1, 0, SZ-1, num[i], 1);
		t = d - st - i + m + m;
		if (t <= 0)break;
		S = Gap(1, t);
		if (M < S){
			M = S, x = i;
		}
	}
	if (Res < M)Res = M;
	for (i = s; i <= l; i++)Ins(1, 0, SZ-1, num[i], 0);
	DP(st, b, m - 1, s, x, d);
	for (i = m; i <= e; i++)Ins(1, 0, SZ-1, num[i], 0);
	for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 1);
	DP(st, m + 1, e, x, l, d);
	for (i = s; i < x; i++)Ins(1, 0, SZ-1, num[i], 0);
}
void Do(int st, int d){
	int i;
	DP(st, max(0, st - (d-1)/2), st, st, N - 1, d);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	int i;
	N = n;
	for (i = 0; i < n; i++){
		ord[i].a = attraction[i];
		ord[i].num = i;
	}
	sort(ord, ord + n);
	for (i = 0; i < n; i++)num[ord[i].num] = i;
	Do(start, d);
	for (i = 0; i < n; i++)num[n - 1 - ord[i].num] = i;
	Do(n - 1 - start, d);
	return Res;
}

Subtask #1
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 6624 KB Output is correct
2 Correct 0 ms 6628 KB Output is correct
3 Correct 0 ms 6624 KB Output is correct
4 Correct 0 ms 6620 KB Output is correct
5 Correct 0 ms 6624 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 360 ms 6620 KB Output is correct
2 Correct 816 ms 6620 KB Output is correct
3 Correct 368 ms 6624 KB Output is correct
4 Correct 324 ms 6628 KB Output is correct
5 Correct 344 ms 6624 KB Output is correct
6 Correct 112 ms 6624 KB Output is correct
7 Correct 208 ms 6620 KB Output is correct
8 Correct 204 ms 6620 KB Output is correct
9 Correct 80 ms 6628 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 6620 KB Output is correct
2 Correct 8 ms 6624 KB Output is correct
3 Correct 8 ms 6624 KB Output is correct
4 Correct 24 ms 6624 KB Output is correct
5 Correct 20 ms 6624 KB Output is correct
6 Correct 4 ms 6620 KB Output is correct
7 Correct 4 ms 6624 KB Output is correct
8 Correct 4 ms 6624 KB Output is correct
9 Correct 4 ms 6620 KB Output is correct

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 364 ms 6624 KB Output is correct
2 Correct 356 ms 6628 KB Output is correct
3 Correct 256 ms 6624 KB Output is correct
4 Correct 12 ms 6628 KB Output is correct
5 Correct 0 ms 6620 KB Output is correct
6 Correct 4 ms 6624 KB Output is correct
7 Correct 4 ms 6620 KB Output is correct
8 Correct 1216 ms 6624 KB Output is correct
9 Correct 1224 ms 6624 KB Output is correct