Submission #70200

#	Time	Username	Problem	Language	Result	Execution time	Memory
70200		zubec	Holiday (IOI14_holiday)	C++14	23 / 100	5038 ms	6048 KiB

holiday

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

const int N = 100100;

int n, a[N];
ll 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;
    ++d;
    for (int i = start; i >= 1; i--){
        vector <int> vec;
        for (int j = i; j <= n; j++){
            vec.push_back(a[j]);
        }
        sort(vec.begin(), vec.end());
        for (int j = i; j <= n; j++){
            suff[j] = suff[j-1] + vec[j-i];
        }
        for (int j = i; j <= n; j++){
            int curd = abs(start-i)*2+abs(start-j);
            int sz = min(j-i+1, d-curd);
            if (sz <= 0)
                break;
            if (start <= j)
            ans = max(ans, suff[j]-suff[j-sz]);
        }
    }

    reverse(a+1, a+n+1);
    start = n-start+1;


    for (int i = start; i >= 1; i--){
        vector <int> vec;
        for (int j = i; j <= n; j++){
            vec.push_back(a[j]);
        }
        sort(vec.begin(), vec.end());
        for (int j = i; j <= n; j++){
            suff[j] = suff[j-1] + vec[j-i];
        }
        for (int j = i; j <= n; j++){
            int curd = abs(start-i)*2+abs(start-j);
            int sz = min(j-i+1, d-curd);
            if (sz <= 0)
                break;
            if (start <= j)
            ans = max(ans, suff[j]-suff[j-sz]);
        }
    }


    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: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53