Submission #285615

#	Time	Username	Problem	Language	Result	Execution time	Memory
285615		ToMmyDong	Holiday (IOI14_holiday)	C++11	0 / 100	58 ms	1932 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
#define X first
#define Y second
#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 full (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);
}

long long int findMaxAttraction (int n, int start, int d, int a[]) {

    vector<pii> pos;
    for (int i=0; i<n; i++) {
        pos.eb(a[i], i);
    }
    sort(ALL(pos));
    reverse(ALL(pos));

    vector<int> on(n);
    ll ans = 0;
    for (int i=102, ptr=0; i>=0; i--) {
        while (ptr<n && pos[ptr].X >= i) {
            on[pos[ptr].Y] = true; 
            ptr++;
        }

        int cnt = 0;
        ll cur = 0;
        for (int i=0; i<n; i++) {
            if (on[i]) {
                cnt++;
                cur += a[i];
            }
            if (cnt + i > d) break;
            ans = max(ans, cur);
        }
    }
    return ans;

}

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