# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
467321 | ivan_tudor | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include"holiday.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 100005;
int a[N];
multiset<int> big, small;
long long sum;
int canhold;
int L, R;
void insert_val(int v){
big.insert(v);
sum += v;
while((int)big.size() > max(canhold, 0)){
int lval = (*big.begin());
sum -= lval;
big.erase(big.find(lval));
small.insert(lval);
}
}
void erase_val(int v){
if(small.count(v)){
small.erase(small.find(v));
}
else if(big.count(v)){
big.erase(big.find(v));
sum -= v;
}
while((int)big.size() < canhold && small.size() > 0){
int val = (*small.rbegin());
big.insert(val);
sum += val;
small.erase(small.find(val));
}
}
void transf(int newL, int newR){
while(L > newL){
canhold -=2;
L--;
insert_val(a[L]);
}
while(R < newR){
canhold --;
R++;
insert_val(a[R]);
}
while(L < newL){
canhold +=2;
erase_val(a[L]);
L++;
}
while(R > newR){
canhold++;
erase_val(a[R]);
R--;
}
}
long long ans = 0;
void solve(int l, int r, int opl, int opr){
if(r < l)
return;
int mid = (l + r)/2;
long long maxi = -1, mpoz;
for(int i = max(opl, mid); i <= opr; i++){
transf(mid, i);
if(maxi < sum){
maxi = sum;
mpoz = i;
}
}
ans = max(ans, maxi);
if(l == r)
return;
if(l <= mid - 1)
solve(l, mid - 1, opl, mpoz);
if(mid + 1 <= r)
solve(mid + 1, r, mpoz, opr);
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
for(int i = 0; i < n; i++)
a[i] = attraction[i];
sum = 0;
L = R = start;
canhold = d;
insert_val(a[start]);
solve(0, start, start, n - 1);
reverse(a, a+n);
start = n - 1 - start;
big.clear();
small.clear();
sum = 0;
L = R = start;
canhold = d;
insert_val(a[start]);
solve(0, start, 0, n - 1);
// cerr<<op;
return op;
}