Submission #285660

#	Time	Username	Problem	Language	Result	Execution time	Memory
285660		ToMmyDong	Holiday (IOI14_holiday)	C++11	7 / 100	5046 ms	1248 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 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);
//}
//

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[]) {
    //return start_left(n, start,d, attraction);
    return bf(n, start, d, attraction);
}

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