제출 #285606

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
285606		ToMmyDong	휴가 (IOI14_holiday)	C++11	0 / 100	410 ms	32364 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define first X
#define second Y
#define eb emplace_back
#define ALL(i) i.begin(),i.end()
#define SZ(i) int(i.size())
#ifdef tmd
#define debug(...) fprintf(stderr,"#%d-(%s)=",__LINE__,#__VA_ARGS__);_do(__VA_ARGS__);
template<typename T> void _do (T &&x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y) {cerr<<x<<",";_do(y...);}
template<typename IT> ostream &__printRng (ostream& os, IT bg, IT ed) {
    for (IT it=bg; it!=ed; it++) {
        if (it == bg) os << "{" << *it;
        else os << "," << *it;
    }
    return os << "}";
}
template<typename T> ostream &operator << (ostream& os, const vector<T> &vec) {
    return __printRng(os,ALL(vec));
}
#else
#define debug(...)
#endif

#include"holiday.h"

struct KSum {
    int k = 0, ptr = 0;
    multiset<int> mx;
    multiset<int> mn;
    ll sum = 0;

    void inc () {
        assert(mn.size());
        auto ptr = prev(mn.end());
        mx.insert(*ptr);
        sum += *ptr;
        mn.erase(ptr);
        k++;
    }
    
    void dec () {
        assert(mx.size());
        auto ptr = mx.begin();
        mn.insert(*ptr);
        sum -= *ptr;
        mx.erase(ptr);
        k--;
    }

    void add (int val) {
        mn.insert(val);
        if (mx.size()) {
            dec();
            inc();
        }
    }
};
ll solve (int n, int s, int d, vector<int> a) {
    if (d == 0) return 0;
    vector<int> sg;

    sg.eb(0);
    for (int i=s+1; i<n; i++) {
        sg.eb(a[i]);
    }
    for (int i=0; i<d+13; i++) {
        sg.eb(0);
    }

    vector<ll> msg(d+1, 0);
    KSum l, r;
    l.add(sg[1]);
    r.add(sg[1]);
    r.add(sg[2]);
    int bst = 1;
    for (int i=2; i<=d; i++) {
        while (l.k < bst && l.k+bst < i) {
            l.inc();
        }
        while (r.k < bst+1 && r.k+bst+1 < i) {
            r.inc();
        }
        while (bst + 2 <= SZ(sg) && r.sum >= l.sum) {
            l.add(sg[++bst]);
            r.add(sg[bst+1]);
            if (l.k) {
                l.dec();
            }
            if (r.k) {
                r.dec();
            }
            debug(bst, l.sum, r.sum);
            while (l.k < bst && l.k+bst < i) {
                l.inc();
            }
            while (r.k < bst+1 && r.k+bst+1 < i) {
                r.inc();
            }
        }
        debug(l.k, bst);
        msg[i] = l.sum;
    }
    debug(sg, msg);
    return max(a[s] + msg[d-1], msg[d]);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
    vector<int> a;
    for (int i=0; i<n; i++) {
        a.eb(attraction[i]);
    }

    ll la = solve(n, start, d, a);
    reverse(ALL(a));
    ll ra = solve(n, n-1-start, d, a);

    return max(la, ra);
}

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