제출 #293100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
293100		AaronNaidu	휴가 (IOI14_holiday)	C++14	7 / 100	24 ms	1944 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

ll sub1(int n, int start, int d, int attraction[]) {
    ll toRet  = 0;
    for (int i = 0; i <= start; i++)
    {
        for (int j = start; j < n; j++)
        {
            int daysTravel = min(2*(j-start) + (start-i), 2*(start-i) + (j-start));
            if (daysTravel >= d)
            {
                continue;
            }
            vector<int> v;
            for (int k = i; k <= j; k++)
            {
                v.push_back(attraction[k]);
            }
            sort(v.rbegin(), v.rend());
            ll thisToRet = 0;
            for (int k = 0; k < min(d-daysTravel, int(v.size()) ); k++)
            {
                thisToRet += v[k];
            }
            toRet = max(toRet, thisToRet);
        }
    }
    return toRet;
}

ll findMaxAttraction(int n, int start, int d, int attraction[]) {
    if (n <= 20)
    {
        return sub1(n, start, d, attraction);
    }
    ll finAns = 0;
    ll totSum = 0;
    ll toKickOut = 1000000009;
    priority_queue<ll> s;
    for (int i = 0; i < min(n, (d+1)/2); i++)
    {
        s.push(-attraction[i]);
        totSum += attraction[i];
        toKickOut = min(toKickOut, ll(attraction[i]));
    }
    finAns = max(finAns, totSum);
    int parity = (d+1)%2;
    int pointer = min(n, (d+1)/2);
    //cout << "Start with " << totSum << "\n";
    while (!s.empty() and pointer < n)
    {
        //cout << "Pointer is " << pointer << " and parity is " << parity << "\n"; 
        if (parity == 0)
        {
            totSum += s.top();
            //cout << "Removing " << -s.top() << " new sum is " << totSum << "\n";
            s.pop();
        }
        if (attraction[pointer] > -s.top())
        {
            totSum += attraction[pointer];
            totSum += s.top();
            //cout << "Swapping out " << -s.top() << " for " << attraction[pointer] << " new sum is " << totSum << "\n";
            s.pop();
            s.push(-attraction[pointer]);
            finAns = max(finAns, totSum);
        }
        parity = 1-parity;
        pointer++;
    }
    return finAns;
}

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