Submission #221631

#	Time	Username	Problem	Language	Result	Execution time	Memory
221631		lyc	Holiday (IOI14_holiday)	C++14	47 / 100	5067 ms	10412 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 int findMaxAttraction(int n, int start, int d, int attraction[]) {
    long long lt[d+1][2], rt[d+1][2];
    FOR(m,1,2) { 
        priority_queue<int,vector<int>,greater<int>> incl;
        priority_queue<int> excl;
        int cleared = -1;
        int processed = start+1;
        long long sum = 0;
        queue<tuple<int,int,int,int,int>> q;
        q.emplace(0,0,d,0,start);
        while (!q.empty()) {
            int dep,s,e,l,r; tie(dep,s,e,l,r) = q.front(); q.pop();
            //cout << "processing " << s << " " << e << " " << l << " " << r << endl;
            int mid = (s+e)/2;

            if (dep > cleared) {
                while (!incl.empty()) incl.pop();
                while (!excl.empty()) excl.pop();
                processed = start+1;
                sum = 0;
                //cout << "cleared " << endl;
            }

            while (processed > r) {
                sum += attraction[--processed]; incl.push(attraction[processed]);
            }
            while (!excl.empty() && SZ(incl)+(start-r)*m < mid) {
                sum += excl.top();
                incl.push(excl.top());
                excl.pop();
            }
            //cout << "INCL " << SZ(incl) << " EXCL " << SZ(excl) << endl;
            lt[mid][m-1] = 0;
            int idx = r;
            RFOR(i,r,l){
                if (i < processed) {
                    sum += attraction[i]; incl.push(attraction[i]);
                    processed = i;
                }
                while (!incl.empty() && SZ(incl)+(start-i)*m > mid) {
                    sum -= incl.top();
                    excl.push(incl.top());
                    incl.pop();
                }
                if (sum > lt[mid][m-1]) lt[mid][m-1] = sum, idx = i;
            }
            //cout << "\tmid " << mid << " best " << lt[mid][m-1] << " at " << idx << endl;

            if (s < mid) q.emplace(dep+1,s,mid-1,idx,r);
            if (mid < e) q.emplace(dep+1,mid+1,e,l,idx);
        }
    }
    FOR(m,1,2) { 
        priority_queue<int,vector<int>,greater<int>> incl;
        priority_queue<int> excl;
        int cleared = -1;
        int processed = start;
        long long sum = 0;
        queue<tuple<int,int,int,int,int>> q;
        q.emplace(0,0,d,start+1,n-1);
        while (!q.empty()) {
            int dep,s,e,l,r; tie(dep,s,e,l,r) = q.front(); q.pop();
            //if (m == 1) cout << "processing " << s << " " << e << " " << l << " " << r << endl;
            int mid = (s+e)/2;

            if (dep > cleared) {
                while (!incl.empty()) incl.pop();
                while (!excl.empty()) excl.pop();
                processed = start;
                sum = 0;
                cleared = dep;
                //if (m == 1) cout << "cleared " << endl;
            }

            while (processed < l) {
                sum += attraction[++processed]; incl.push(attraction[processed]);
            }
            while (!excl.empty() && SZ(incl)+(l-start)*m < mid) {
                sum += excl.top();
                incl.push(excl.top());
                excl.pop();
            }
            //if (m == 1) cout << processed << " INCL " << SZ(incl) << " EXCL " << SZ(excl) << " :: " << SZ(incl)+(l-start)*m << endl;
            rt[mid][m-1] = 0;
            int idx = l;
            FOR(i,l,r){
                if (i > processed) {
                    sum += attraction[i]; incl.push(attraction[i]);
                    processed = i;
                }
                while (!incl.empty() && SZ(incl)+(i-start)*m > mid) {
                    sum -= incl.top();
                    excl.push(incl.top());
                    incl.pop();
                }
                if (sum > rt[mid][m-1]) rt[mid][m-1] = sum, idx = i;

            }
            //if (m == 1) cout << "\tmid " << mid << " best " << rt[mid][m-1] << " at " << idx << endl;

            if (s < mid) q.emplace(dep+1,s,mid-1,l,idx);
            if (mid < e) q.emplace(dep+1,mid+1,e,idx,r);
        }
    }


    long long ans = 0;
    FOR(x,0,d){
        //cout << x << " :: " << lt[x][0] << ' ' << lt[x][1] << ' ' << rt[x][0] << ' ' << rt[x][1] << endl;
        ans = max({ans,lt[x][0]+rt[d-x][1],lt[x][1]+rt[d-x][0]});
    }
    return ans;
}

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