Submission #226715

#	Time	Username	Problem	Language	Result	Execution time	Memory
226715		urd05	휴가 (IOI14_holiday)	C++14	47 / 100	5056 ms	3576 KiB

holiday

#include <bits/stdc++.h>
using namespace std;

int n;
int st;
int d;
long long arr[100000];

long long findMaxAttraction(int nn,int start,int dd,int at[]) {
    n=nn;
    st=start;
    d=dd;
    for(int i=0;i<n;i++) {
        arr[i]=at[i];
    }
    long long ret=0;
    long long sum=0;
    priority_queue<long long,vector<long long>,greater<long long>> pq;
    for(int i=st;i>=0;i--) {
        pq.push(arr[i]);
        sum+=arr[i];
        while ((int)pq.size()>d-st+i&&!pq.empty()) {
            sum-=pq.top();
            pq.pop();
        }
        ret=max(ret,sum);
    }
    while (!pq.empty()) {
        pq.pop();
    }
    sum=0;
    for(int i=st;i<n;i++) {
        pq.push(arr[i]);
        sum+=arr[i];
        while ((int)pq.size()>d-i+st&&!pq.empty()) {
            sum-=pq.top();
            pq.pop();
        }
        ret=max(ret,sum);
    }
    if (st==0||st==n-1) {
        return ret;
    }
    for(int i=st;i>=0;i--) {
        while (!pq.empty()) {
            pq.pop();
        }
        sum=0;
        for(int j=i;j<n;j++) {
            pq.push(arr[j]);
            sum+=arr[j];
            while ((int)pq.size()>d-st-j+2*i&&!pq.empty()) {
                sum-=pq.top();
                pq.pop();
            }
            ret=max(ret,sum);
        }
    }
    for(int i=st;i<n;i++) {
        while (!pq.empty()) {
            pq.pop();
        }
        sum=0;
        for(int j=i;j>=0;j--) {
            pq.push(arr[j]);
            sum+=arr[j];
            while ((int)pq.size()>d+j+st-2*i&&!pq.empty()) {
                sum-=pq.top();
                pq.pop();
            }
            ret=max(ret,sum);
        }
    }
    return ret;
}

• Subtask 1: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 0 / 53