| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 679337 | Cross_Ratio | 휴가 (IOI14_holiday) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
//#include "holiday.h"
using namespace std;
typedef long long ll;
int N, st, d;
int A[100005];
typedef pair<int, int> P;
ll findMaxAttraction(int _N, int _st, int _d, int attraction[]) {
N = _N, st = _st, d = _d;
int i, j;
for(i=0;i<N;i++) A[i] = attraction[i];
ll ans = 0;
ll sum = 0;
for(i=st;i>=0;i--) {
int val = d;
val -= 2*(st - i);
if(val <= 0) break;
priority_queue<int, vector<int>, greater<int>> PQ;
ll cnt = 0;
for(int j = i; j <= st; j++) {
cnt += A[j];
PQ.push(A[j]);
while(PQ.size()>val) {
cnt -= PQ.top();
PQ.pop();
}
}
ans = max(ans, cnt);
for(j=st+1;j<N;j++) {
cnt += A[j];
PQ.push(A[j]);
val--;
if(val <= 0) break;
while(PQ.size()>val) {
cnt -= PQ.top();
PQ.pop();
}
ans = max(ans, cnt);
}
}
if(st==0) return ans;
st = N-1-st;
reverse(A, A+N);
for(i=st;i>=0;i--) {
int val = d;
val -= 2*(st - i);
if(val <= 0) break;
priority_queue<int, vector<int>, greater<int>> PQ;
ll cnt = 0;
for(int j = i; j <= st; j++) {
cnt += A[j];
PQ.push(A[j]);
while(PQ.size()>val) {
cnt -= PQ.top();
PQ.pop();
}
}
ans = max(ans, cnt);
for(j=st+1;j<N;j++) {
cnt += A[j];
PQ.push(A[j]);
val--;
if(val <= 0) break;
while(PQ.size()>val) {
cnt -= PQ.top();
PQ.pop();
}
ans = max(ans, cnt);
}
}
return ans;
}
int A2[1000005];
signed main() {
int i, j;
int N, st, d;
cin >> N >> st >> d;
for(i=0;i<N;i++) cin >> A2[i];
cout << findMaxAttraction(N, st, d, A2);
}