Submission #232090

#	Time	Username	Problem	Language	Result	Execution time	Memory
232090		anonymous	Holiday (IOI14_holiday)	C++14	47 / 100	5068 ms	3452 KiB

holiday

#include"holiday.h"
#include <map>
#define LL long long
#define MAXN 100005
using namespace std;
class DS {
    map <int,int> M;
public:
    void nuke() {M.clear();}
    void add(int v) {
        M[v]++;
    }
    void del(int v) {
        M[v]--;
    }
    LL ask(int num) {
        if (M.empty()) {return(0);}
        if (num < 0) {return(-1LL<<60);}
        LL res = 0;
        auto pt = --M.end();
        while (num) {
            if ((*pt).second > num) {
                res += ((LL) num) * ((LL) (*pt).first);
                num = 0;
            } else {
                res += ((LL) (*pt).second) * ((LL) (*pt).first);
                num -= (*pt).second;
            }
            if (pt == M.begin()) {break;}
            else {--pt;}
        }
        return(res);
    }
} KQ;

LL ans;
int A[MAXN], D, S, N;
void slv(int l, int r, int lo, int hi, int pl, int pr) {
    //printf("%d %d %d %d\n",l,r,lo,hi);
    if (l > r) {return;}
    int p = (l + r) >> 1;
    int pL = pl, pR = pr;
    while (pl > hi+1) {
        KQ.add(A[pl-1]);
        pl--;
    }
    while (pr < p) {
        KQ.add(A[pr+1]);
        pr++;
    }
    while (pl <hi+1) {
        KQ.del(A[pl]);
        pl++;
    }
    while (pr > p) {
        KQ.del(A[pr]);
        pr--;
    }

    LL opt=-1, optval=-1LL<<60;
    for (int i=hi; i>=lo; i--) {
        KQ.add(A[i]);
        LL res = KQ.ask(D-S + 2*i - p);
        if (res >= optval) {
            opt = i;
            optval = res;
            ans = max(ans, res);
        }
    }
    slv(l, p-1, lo, opt, lo, p);
    slv(p+1,r, opt, hi, lo, p);
    //reset pos
    while (lo < pL) {
        KQ.del(A[lo]);
        lo++;
    }
    while (lo > pL) {
        KQ.add(A[lo-1]);
        lo--;
    }
    while (p < pR) {
        KQ.add(A[p+1]);
        p++;
    }
    while (p > pR) {
        KQ.del(A[p]);
        p--;
    }
}

void slvL() {
    for (int i=S; i>=0; i--) { //one direction
        KQ.add(A[i]);
        ans  = max(ans, KQ.ask(D-S+i));
    }
    slv(S+1, N-1, 0, S-1, 0, S);
    KQ.nuke();
}

LL findMaxAttraction(int n, int s, int d, int a[]) { //len, start, days, val
    N = n, S = s, D = d;
    for (int i=0; i<n; i++) {A[i] = a[i];}
    slvL();
    for (int i=0; i<=n/2; i++) {
        swap(A[i], A[n-1-i]);
    }
    S = N - 1 - S;
    /*for (int i=0; i<N; i++) {
        printf("%d ",A[i]);
    }
    printf("\n%d\n",S);
    printf(" Flip\n"); */
    slvL();
    return(ans);
}

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