Submission #856388

#	Time	Username	Problem	Language	Result	Execution time	Memory
856388		yuricon	Holiday (IOI14_holiday)	C++17	47 / 100	270 ms	1752 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const int N = 1e5 + 6;
int n, s, d, a[N];
ll sub2()
{
    priority_queue <int, vector <int>, greater <int>> pq;
    ll sum = 0, ans = 0;
    int cnt = 0;
    for(int i = s; i < n; ++i)
    {
        sum += a[i];
        cnt++;
        pq.push(a[i]);
        while(!pq.empty() && cnt + i - s > d)
        {
            sum -= pq.top();
            pq.pop();
            cnt--;
        }
        ans = max(ans, sum);
    }
    return ans;
}
ll sub3()
{
    ll ans = 0;
    for(int i = 0; i < n; ++i)
    {
        int c = d - abs(s - i);
        if(i <= s)
        {
            priority_queue <int, vector <int>, greater <int> > pq;
            ll sum = 0;
            int cnt = 0;
            for(int j = i; j < n; ++j)
            {
                sum += a[j];
                cnt++;
                pq.push(a[j]);
                while(!pq.empty() && cnt + j - i > c)
                {
                    sum -= pq.top();
                    pq.pop();
                    cnt--;
                }
                ans = max(ans, sum);
            }
        }
        if(i >= s)
        {
            priority_queue <int, vector <int>, greater <int> > pq;
            ll sum = 0;
            int cnt = 0;
            for(int j = i; j >= 0; --j)
            {
                sum += a[j];
                cnt++;
                pq.push(a[j]);
                while(!pq.empty() && cnt + (i - j) > c)
                {
                    sum -= pq.top();
                    pq.pop();
                    cnt--;
                }
                ans = max(ans, sum);
            }
        }
    }
    return ans;
}
long long int findMaxAttraction(int na, int sa, int da, int aa[]) {
    n = na;
    s = sa;
    d = da;
    for(int i = 0; i < n; ++i)
    {
        a[i] = aa[i];
    }
    if(n <= 3000)
    {
        return sub3();
    }
    return sub2();
}

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