Submission #70172

#	Time	Username	Problem	Language	Result	Execution time	Memory
70172		zubec	Holiday (IOI14_holiday)	C++14	47 / 100	5023 ms	6908 KiB

holiday

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

const int N = 100100;

int n, a[N], suff[N];

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    ::n = n;
    for (int i = 1; i <= n; i++)
        a[i] = attraction[i-1];
    ++start;
    if (start == 1){
        ll ans = 0;
        multiset<int> q;
        int curd = 0;
        ll sum = 0;
        for (int i = 1; i <= n; i++){
            ++curd;
            q.insert(a[i]);
            sum += a[i];
            while(!q.empty() && curd > d){
                sum -= *q.begin();
                q.erase(q.begin());
                --curd;
            }
            if (curd <= d){
                ans = max(ans, sum);
            }
            ++curd;
        }

        return ans;
    }
    ll ans = 0;
    for (int i = start; i >= 1; i--){
        multiset<int> q;
        int curd = 0;
        ll sum = 0;
        for (int j = start-1; j >= i; j--){
            ++curd;
            ++curd;
            sum += a[j];
            q.insert(a[j]);
            while(!q.empty() && curd > d){
                sum -= *q.begin();
                q.erase(q.begin());
                --curd;
            }
            if (curd <= d){
                ans = max(ans, sum);
            }
        }
        curd += abs(i-start);
        for (int j = start; j <= n; j++){
            ++curd;
            sum += a[j];
            q.insert(a[j]);
            while(!q.empty() && curd > d){
                sum -= *q.begin();
                q.erase(q.begin());
                --curd;
            }
            //cout << i << ' ' << j << ' ' << curd << ' ' << sum << endl;
            if (curd <= d){
                ans = max(ans, sum);
            }
            ++curd;
        }
    }
    reverse(a+1, a+n+1);
    start = n-start+1;

    for (int i = start; i >= 1; i--){
        multiset<int> q;
        int curd = 0;
        ll sum = 0;
        for (int j = start-1; j >= i; j--){
            ++curd;
            ++curd;
            sum += a[j];
            q.insert(a[j]);
            while(!q.empty() && curd > d){
                sum -= *q.begin();
                q.erase(q.begin());
                --curd;
            }
            if (curd <= d){
                ans = max(ans, sum);
            }
        }
        curd += abs(i-start);
        for (int j = start; j <= n; j++){
            ++curd;
            sum += a[j];
            q.insert(a[j]);
            while(!q.empty() && curd > d){
                sum -= *q.begin();
                q.erase(q.begin());
                --curd;
            }
            //cout << i << ' ' << j << ' ' << curd << ' ' << sum << endl;
            if (curd <= d){
                ans = max(ans, sum);
            }
            ++curd;
        }
    }
    /*multiset<int> q;
    int curd = 0;
    ll sum = 0;
    for (int i = start; i <= n; i++){
        ++curd;
        sum += a[i];
        q.insert(a[i]);
        while(!q.empty() && curd > d){
            sum -= *q.begin();
            q.erase(q.begin());
            --curd;
        }
        if (curd <= d)
            ans = max(ans, sum);
        ++curd;
    }*/

    return ans;

}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

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