Submission #232089

#	Time	Username	Problem	Language	Result	Execution time	Memory
232089		anonymous	Holiday (IOI14_holiday)	C++14	47 / 100	5068 ms	2972 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]++;
    }
    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) {
    //printf("%d %d %d %d\n",l,r,lo,hi);
    if (l > r) {return;}
    int p = (l + r) >> 1;
    LL opt=-1, optval=-1LL<<60;
    for (int i=hi+1; i<=p; i++) {
        KQ.add(A[i]);
    }
    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);
        }
    }
    KQ.nuke();
    slv(l, p-1, lo, opt);
    slv(p+1,r, opt, hi);
}

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

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