oj.uz

답안 #348800

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
348800 2021-01-15T18:41:10 Z dennisstar 휴가 (IOI14_holiday) C++17
100 / 100
 1780 ms 7020 KB 
#include <bits/stdc++.h>
#include "holiday.h"
#define em emplace

using namespace std;
using ll = long long;

const int MX = 1e5 + 5;

int N, S, D;
ll H[MX], A;

struct myset {
	multiset<ll> S1, S2;
	ll V; int s, e;
	void init() {
		s=0; e=-1; V=0;
		S1.clear(); S2.clear();
	}
	void ins(int i) {
		if (S1.empty()||*S1.rbegin()<H[i]) S2.em(H[i]), V+=H[i];
		else S1.em(H[i]);
	}
	void er(int i) {
		if (S1.find(H[i])!=S1.end()) S1.erase(S1.find(H[i]));
		else if (S2.find(H[i])!=S2.end()) S2.erase(S2.find(H[i])), V-=H[i];
		else assert(false);
	}
	void res(int ss, int ee) {
		for (int i=s-1; i>=ss; i--) ins(i);
		for (int i=e+1; i<=ee; i++) ins(i);
		for (int i=s; i<ss; i++) er(i);
		for (int i=e; i>ee; i--) er(i);
		s=ss; e=ee;
	}
	ll get(int c) {
		if (c<=0) return 0;
		while (S2.size()<c&&S1.size()>0) V+=*S1.rbegin(), S2.em(*S1.rbegin()), S1.erase(--S1.end());
		while (S2.size()>c) V-=*S2.begin(), S1.em(*S2.begin()), S2.erase(S2.begin());
		return V;
	}
}MS;

void sol(int s, int e, int ss, int ee) {
	if (s>e||ss>ee) return ;
	int m=(s+e)/2, mi=ss; ll mx=0;
	for (int i=ss; i<=ee; i++) {
		MS.res(m, i);
		ll r=MS.get(D-(S+i-2*m));
		if (r>mx) mx=r, mi=i;
	}
	A=max(A, mx);
	if (s==e) return ;
	sol(s, m-1, ss, mi); sol(m+1, e, mi, ee);
}

ll findMaxAttraction(int n, int s, int d, int h[]) {
	N=n, S=s, D=d;
	for (int i=0; i<N; i++) H[i]=h[i];
	MS.init();
	sol(0, S, S+1, N-1);
	reverse(H, H+N); S=N-1-S; MS.init();
	sol(0, S, S+1, N-1);
	return A;
}

Compilation message

holiday.cpp: In member function 'll myset::get(int)':
holiday.cpp:38:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   38 |   while (S2.size()<c&&S1.size()>0) V+=*S1.rbegin(), S2.em(*S1.rbegin()), S1.erase(--S1.end());
      |          ~~~~~~~~~^~
holiday.cpp:39:19: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |   while (S2.size()>c) V-=*S2.begin(), S1.em(*S2.begin()), S2.erase(S2.begin());
      |          ~~~~~~~~~^~

Subtask #1
7.0 / 7.0

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

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 32 ms 6252 KB Output is correct
2 Correct 32 ms 6124 KB Output is correct
3 Correct 33 ms 6124 KB Output is correct
4 Correct 34 ms 6124 KB Output is correct
5 Correct 47 ms 5740 KB Output is correct
6 Correct 11 ms 2028 KB Output is correct
7 Correct 23 ms 3328 KB Output is correct
8 Correct 30 ms 3948 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct

Subtask #3
17.0 / 17.0

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

Subtask #4
53.0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Correct 33 ms 6124 KB Output is correct
2 Correct 35 ms 7020 KB Output is correct
3 Correct 498 ms 3388 KB Output is correct
4 Correct 20 ms 640 KB Output is correct
5 Correct 6 ms 364 KB Output is correct
6 Correct 6 ms 364 KB Output is correct
7 Correct 6 ms 364 KB Output is correct
8 Correct 1754 ms 6532 KB Output is correct
9 Correct 1780 ms 6508 KB Output is correct