Submission #221859

#	Time	Username	Problem	Language	Result	Execution time	Memory
221859		lyc	Holiday (IOI14_holiday)	C++14	100 / 100	1433 ms	9040 KiB

holiday

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

#define SZ(x) ((int)(x).size())
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)

long long solve(int n, int s, int d, int a[]) {
    long long lt[d+1], rt[d+1];
    int lo[d+1], ro[d+1];

    lt[0] = rt[0] = 0;

    RFOR(k,17,0){
        priority_queue<int,vector<int>,greater<int>> incl;
        priority_queue<int> excl;
        int ep = s+1;
        long long cur = 0;
        for (int x = 1<<k; x <= d; x += 1<<(k+1)) {
            int lim = (x+(1<<k) <= d ? lo[x+(1<<k)] : 0);
            while (!excl.empty() && SZ(incl) + 2*(s-ep) < x) {
                int v = excl.top(); excl.pop();
                cur += v; incl.push(v);
            }
            lt[x] = cur, lo[x] = ep;
            while (ep > lim) {
                --ep;
                cur += a[ep]; incl.push(a[ep]);
                while (!incl.empty() && SZ(incl) + 2*(s-ep) > x) {
                    int v = incl.top(); incl.pop();
                    cur -= v; excl.push(v);
                }
                if (cur > lt[x]) lt[x] = cur, lo[x] = ep;
            }
        }
    }

    RFOR(k,17,0){
        priority_queue<int,vector<int>,greater<int>> incl;
        priority_queue<int> excl;
        int ep = s;
        long long cur = 0;
        for (int x = 1<<k; x <= d; x += 1<<(k+1)) {
            int lim = (x+(1<<k) <= d ? ro[x+(1<<k)] : n-1);
            while (!excl.empty() && SZ(incl) + (ep-s) < x) {
                int v = excl.top(); excl.pop();
                cur += v; incl.push(v);
            }
            rt[x] = cur, ro[x] = ep;
            while (ep < lim) {
                ++ep;
                cur += a[ep]; incl.push(a[ep]);
                while (!incl.empty() && SZ(incl) + (ep-s) > x) {
                    int v = incl.top(); incl.pop();
                    cur -= v; excl.push(v);
                }
                if (cur > rt[x]) rt[x] = cur, ro[x] = ep;
            }
        }
    }

    //FOR(x,0,d) { cout << x << " :: " << lt[x] << ' ' << rt[x] << endl; }
    //cout << endl;

    long long ans = 0;
    FOR(x,0,d) ans = max(ans, lt[x]+rt[d-x]);
    return ans;
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long ans = solve(n,start,d,attraction);
    reverse(attraction,attraction+n);
    ans = max(ans, solve(n,n-1-start,d,attraction));
    return ans;
}

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