Submission #285627

#	Time	Username	Problem	Language	Result	Execution time	Memory
285627		ToMmyDong	Holiday (IOI14_holiday)	C++11	0 / 100	175 ms	1280 KiB

holiday

#include <bits/stdc++.h>
using namespace std;
#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);
//}

typedef long long ll;
long long int findMaxAttraction (int n, int start, int d, int attraction[]) {
    assert(start == 0);

    ll ans = 0;
    for (ll _i=1002; _i>=0; _i--) {

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

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

}

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