Submission #1125975

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125975		Mike_Vu	Holiday (IOI14_holiday)	C++17	0 / 100	14 ms	10680 KiB

holiday

#ifndef mikevui
    #include "holiday.h"
#endif // mikevui

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
#define ALL(v) (v).begin(), (v).end()

template<typename T> bool maximize(T &x, const T &y) {
    if (x < y) {x = y; return 1;}
    return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
    if (x > y) {x = y; return 1;}
    return 0;
}

const int maxn = 1e5+5;
int n, d;
vector<int> a, b;
ll dp1[maxn*3][2], dp2[maxn*3][2]; //left, right | 1 -> ret
multiset<int> st1, st2; //chosen, waiting
ll cursum = 0, ans = 0;
//ll debugsum = 0;

void dnc(int l, int r, int opl, int opr, bool ret, vector<int> &a, ll dp[][2]) {///assume 1 -> opl-1
//    cout << l << ' ' << r << ' ' << opl << ' ' << opr << ' ' << ret << endl;
//    system("pause");
//    debugsum += opr-opl+1;
    int mid = (l+r)>>1; ///d = mid
    int opt = -1; ///case -1 when cannot move anywhere
    ll best = -1;
    for (int i = opl; i <= opr; i++) {
        //inc dis -> remove 1/2 element(s)
        int numele = mid-i*(1+ret);
        st2.insert(a[i]);
//        if (numele < 0) break;
        //move 1 -> 2
        while ((int)st1.size() > numele && !st1.empty()) {
            int val = (*st1.begin());
            st1.erase(st1.begin());
            cursum -= val;
            st2.insert(val);
        }
        while ((int)st1.size() < numele && !st2.empty()){
            auto it = prev(st2.end());
            int val = (*it);
            st2.erase(it);
            cursum += val;
            st1.insert(val);
        }
        while ((!st1.empty() && !st2.empty()) && (*st1.begin()) < (*st2.rbegin())) {
            auto it = prev(st2.end());
            int val1 = (*st1.begin()), val2 = (*it);
            st1.erase(st1.begin());
            st2.erase(it);
            st1.insert(val2);
            st2.insert(val1);
            cursum += val2-val1;
        }
        if (maximize(best, cursum)) {
            opt = i;
        }
    }
//    cout << "case " << l << ' ' << r << ' ' << mid << ' ' << opl << ' ' << opr << ' ' << ret << "\n";
//    cout << "opt here " << opt << endl;
//    for (auto it : st1) {
//        cout << it << ' ';
//    }
//    cout << endl;
//    for (auto it : st2) {
//        cout << it << ' ';
//    }
//    cout << endl;
    dp[mid][ret] = best;
    for (int i = opt; i <= opr; i++) {
//        cout << i << endl;
        int val = a[i];
        auto it = st2.find(val);
        if (it == st2.end()) {
            assert(st1.find(val) != st1.end());
            st1.erase(st1.find(val));
            cursum -= val;
        }
        else {
            st2.erase(it);
        }
//        cout << "ok" << endl;
    }
//    cout << "ok phase 1" << endl;
    if (mid != r) {
        dnc(mid+1, r, opt, opr, ret, a, dp);
    }
    for (int i = opl; i < opt; i++) {
        int val = a[i];
        auto it = st2.find(val);
        if (it == st2.end()) {
            st1.erase(st1.find(val));
            cursum -= val;
        }
        else {
            st2.erase(it);
        }
    }
//    cout << "ok phase 2" << endl;
    if (mid != l) {
        dnc(l, mid-1, opl, opt, ret, a, dp);
    }
}

ll findMaxAttraction(int N, int S, int D, int A[]) {
    for (int i = S; i >= 0; i--) {
        a.pb(A[i]);
    }
    for (int i = S; i < N; i++) {
        b.pb(A[i]);
    }
    d = D;
    //dnc
    memset(dp1, 0, sizeof(dp1));
    memset(dp2, 0, sizeof(dp2));
    dnc(1, d, 1, (int)a.size()-1, 0, a, dp1);
    cursum = 0;
    st1.clear();
    st2.clear();
    dnc(2, d, 1, (int)a.size()-1, 1, a, dp1);
    cursum = 0;
    st1.clear();
    st2.clear();
//    cout << "HERE COME THE 2ND" << endl;
    dnc(1, d, 1, (int)b.size()-1, 0, b, dp2);
    cursum = 0;
    st1.clear();
    st2.clear();
    dnc(2, d, 1, (int)b.size()-1, 1, b, dp2);
//    cout << debugsum << "\n";
//    for (int i= 1; i <= d; i++) {
//        cout << dp1[i][0] << ' ';
//    }
//    cout << "\n";
//    for (int i= 1; i <= d; i++) {
//        cout << dp1[i][1] << ' ';
//    }
//    cout << "\n";
//    for (int i= 1; i <= d; i++) {
//        cout << dp2[i][0] << ' ';
//    }
//    cout << "\n";
//    for (int i= 1; i <= d; i++) {
//        cout << dp2[i][1] << ' ';
//    }
//    cout << "\n";
    //for each d1, d2 -> cal with/without st
    for (int d1 = 0; d1 <= d; d1++) {
        int d2 = d-d1;
        //case left right
        maximize(ans, dp1[d1][1]+dp2[d2][0]);
        //case right left
        maximize(ans, dp1[d1][0]+dp2[d2][1]);
        //consider start
        if (d1 < d) {
            d2 = d-d1-1;
            maximize(ans, dp1[d1][1]+dp2[d2][0]+a[0]);
            maximize(ans, dp1[d1][0]+dp2[d2][1]+a[0]);
        }
    }
    return ans;
}

#ifdef mikevui
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    #define name "task"
//    if (fopen(name".inp", "r")) {
//        freopen(name".inp", "r", stdin);
//        freopen(name".out", "w", stdout);
//    }
    int N, S, D, A[maxn];
    cin >> N >> S >> D;
    for (int i = 0; i < N; i++) {
        cin >> A[i];
    }
    cout << findMaxAttraction(N, S, D, A);
}
#endif // mikevui
/**
5 2 7
8 10 1 1 21

7 4 16
1 4 3 9 2 4 9

10 7 20
32 13 82 81 93 22 10 43 21 98

20 11 40
32 13 82 81 93 22 10 43 21 98 43 12 43 82 95 32 18 90 43 12
*/

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