Submission #281808

#	Time	Username	Problem	Language	Result	Execution time	Memory
281808		SamAnd	휴가 (IOI14_holiday)	C++17	47 / 100	5035 ms	6136 KiB

holiday

#include"holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define m_p make_pair
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
typedef long long ll;
const int N = 100005;

int n;
int a[N];

long long int findMaxAttraction(int n, int start, int d, int attraction[])
{
    ::n = n;
    for (int i = 0; i < n; ++i)
        a[i] = attraction[i];

    ll ans = 0;

    if (start == 0)
    {
        multiset<int> s;
        ll yans = 0;
        for (int i = 0; i < n; ++i)
        {
            s.insert(a[i]);
            yans += a[i];
            while (!s.empty() && sz(s) > d - i)
            {
                yans -= (*s.begin());
                s.erase(s.begin());
            }
            ans = max(ans, yans);
        }
        return ans;
    }

    for (int u = start; u < n; ++u)
    {
        ll yans = 0;
        multiset<int> s;
        for (int i = start; i <= u; ++i)
        {
            s.insert(a[i]);
            yans += a[i];
        }
        while (!s.empty() && sz(s) > d - (u - start))
        {
            yans -= (*s.begin());
            s.erase(s.begin());
        }
        for (int i = start; i >= 0; --i)
        {
            if (i < start)
            {
                s.insert(a[i]);
                yans += a[i];
            }
            while (!s.empty() && sz(s) > d - (2 * min(start - i, u - start) + max(start - i, u - start)))
            {
                yans -= (*s.begin());
                s.erase(s.begin());
            }
            ans = max(ans, yans);
        }
    }
    return ans;
}

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