Submission #285680

#	Time	Username	Problem	Language	Result	Execution time	Memory
285680		ToMmyDong	Holiday (IOI14_holiday)	C++11	0 / 100	5043 ms	13672 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<pii> sg;

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

    vector<ll> msg(d+1, 0);
    KSum l, r;
    l.add(sg[0].X);
    r.add(sg[0].X);
    r.add(sg[1].X);
    int ptr = 0;
    for (int i=2, lptr, rptr; i<=d; i++) {

        lptr = sg[ptr].Y - s;
        rptr = sg[ptr+1].Y - s;
        while (l.k < ptr+1 && l.k+lptr < i) {
            l.inc();
        }
        while (r.k < ptr+2 && r.k+rptr < i) {
            r.inc();
        }
        while (ptr < SZ(sg)-2 && r.sum > 0 && r.sum >= l.sum) {
            debug(ptr, SZ(sg));
            ptr++;
            lptr = sg[ptr].Y - s;
            rptr = sg[ptr+1].Y - s;
            l.add(sg[ptr].X);
            r.add(sg[ptr+1].X);
            debug(ptr, SZ(sg));
            if (l.k) {
                l.dec();
            }
            if (r.k) {
                r.dec();
            }
            while (l.k < ptr+1 && l.k+lptr < i) {
                l.inc();
            }
            while (r.k < ptr+2 && r.k+rptr < i) {
                r.inc();
            }
            debug(lptr, rptr, l.sum, r.sum, l.k, r.k);
        }
        debug(lptr, rptr, i, l.sum, r.sum);
        msg[i] = l.sum;
    }
    debug(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);
    return la;
}


ll start_left (int n, int start, int d, int *a) {
    assert(start == 0);
    ll ans = 0;
    for (ll mn=1002; mn>=0; mn--) {

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

    //assert(ans == full(n, start, d, a));
    return ans;

}

ll bf (int n, int start, int d, int *a) {
    ll ans = 0;
    for (int i=start; i>=0; i--) {
        for (int j=start; j<n; j++) {
            vector<int> v;
            for (int k=i; k<=j; k++) v.eb(a[k]);
            sort(ALL(v));

            ll cur = 0;
            int ld = abs(i-start), rd = abs(j-start);
            int dd = min(ld, rd) + ld + rd;
            for (int k=0; k<min(SZ(v),d-dd); k++) {
                cur += v[SZ(v)-k-1];
            }
            ans = max(ans, cur);

        }
    }

    return ans;
}

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

    ll lf = full(n, start,d, attraction);
    ll ba = bf(n, start, d, attraction);
    debug(lf, ba);
    assert(lf == ba);
    return lf;
}

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