| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 237053 | crossing0ver | 휴가 (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
#define int long long
#include"holiday.h"
#define ll long long
#define fi first
#define se second
using namespace std;
int n,x,d,val[100005];
ll solveR() {
set <pair<int,int> > s;
ll eaten = 0,ans = val[x];
int left = 0;
eaten = val[x];
s.insert({val[x],x});
for (int i = x + 1; i < n; i++) {
int stamina = i + s.size();
if (i - x >= d) {left = i + 1; break;}
while (stamina >= d) {
eaten -= (*s.begin()).fi;
s.erase(s.begin());
stamina--;
}
if (stamina < d) {
eaten += val[i];
s.insert({val[i],i});
}
ans = max(ans,eaten);
}
return ans;
}
ll solve() {
set <pair<int,int> > s;
set <pair<int,int>,greater< pair<int,int> > > g;
ll eaten = 0,ans = val[x];
int left = 0;
for (int i = x; i >= 0; i--) {
s.insert({val[i],i});
eaten += val[i];
}
int l = 0;
for (int i = x + 1; i < n && i < x + d; i++) {
s.insert({val[i],i});
eaten += val[i];
int stamina = (i - x + i - l) + s.size();
while (stamina > d) {
if (i - x + i - l > d) {
stamina--;
if (s.find({val[l],l}) != s.end()) {
stamina--;
s.erase({val[l],l});
eaten -= val[l];
}
l++;
}
else {
if (s.find({val[l],l}) == s.end() && l < x) {
l++;
stamina--;
continue;
}
int in = (*s.begin()).se;
eaten -= (*s.begin()).fi;
if (in == l && l < x) {
l++;
stamina-=2;
}
else {
stamina--;
g.insert(*s.begin());
}
s.erase(s.begin());
}
}
if (stamina < d && g.size()) {
s.insert(*g.begin());
g.erase(g.begin());
}
ans = max(ans,eaten);
}
return ans;
}
ll findMaxAttraction(int n1, int start, int d1, int attraction[]) {
n = n1;
x = start;
d = d1;
ll ans = 0;
for (int i = 0; i < n; i ++) val[i] = attraction[i];
if (!d) return 0;
if (d == 1) return val[start];
ans = max(ans,solveR());
ans = max(ans,solve());
for (int i = 0 ;i < n; i++) val[i] = attraction[n-i];
x = n - x;
ans = max(ans,solveR());
ans = max(ans,solve());
return ans;
} /*
main(){
freopen("read1.txt","r",stdin);
freopen("write1.txt","w",stdout);
int n,start,d;
cin >> n >> start >> d;
int att[n];
for (int i = 0; i < n ;i ++) cin >> att[i];
cout << findMaxAttraction(n,start,d,att);
} */