Submission #1007839

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007839		onbert	Holiday (IOI14_holiday)	C++17	7 / 100	2704 ms	65536 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long

bool cmp(pair<int,int> a, pair<int,int> b) {
    if (a.first != b.first) return a.first > b.first;
    return a.second < b.second;
}

const int maxn = 1e5 + 5;
int n, s, d;
int a[maxn], fen[maxn][2];
void update(int id, int val, int j) {
    for (; id<=n; id += (id & -id)) fen[id][j] += val;
}
int qry(int id, int j) {
    int val = 0;
    for (;id>=1;id -= (id & -id)) val += fen[id][j];
    return val;
}

int get(int l, int r) {
    int k = min(d - (r-l) - min(r-s, s-l), r-l+1);
    vector<int> v;
    for (int i=l;i<=r;i++) v.push_back(a[i]);
    sort(v.rbegin(), v.rend());
    int val = 0;
    for (int i=0;i<k;i++) val += v[i];
    // cout << l << " " << r << " " << val << endl;
    return val;
}

int solve() {
    vector<pair<int,int>> v;
    for (int i=s;i<=n;i++) v.push_back({a[i], i});
    for (int i=0;i<=n;i++) fen[i][0] = 0, fen[i][1] = 0;
    sort(v.rbegin(), v.rend());
    int mx = 0, r = n;
    for (auto [val, id]:v) {
        update(id, val, 0);
        update(id, 1, 1);
        while (r-s + qry(r, 1) > d) r--;
        mx = max(qry(r, 0), mx);
    }
    // cout << mx << endl;
    for (int i=0;i<=n;i++) fen[i][0] = 0, fen[i][1] = 0;
    sort(v.begin(), v.end(), cmp);
    vector<int> vec;
    r = n;
    for (auto [val, id]:v) {
        update(id, val, 0);
        update(id, 1, 1);
        while (r-s + qry(r, 1) > d) r--;
        if (qry(r, 0) == mx) {
            // cout << qry(r, 1) << endl;
            for (int i=s;i<=r;i++) if (qry(i, 1) - qry(i-1, 1) == 1) {
                // cout << i << " ";
                vec.push_back(i);
            }
            // cout << endl;
        }
    }
    int ans = 0;
    for (int l = s, R = vec.size()-1; l>=1; l--) {
        while (R >= 0 && vec[R]-l + s-l + R+1 > d) R--;
        if (R<0 || vec[R] - s < s - l) break;
        ans = max(get(l, vec[R]), ans);
    }
    return ans;
}

int findMaxAttraction(int32_t N, int32_t S, int32_t D, int32_t A[]) {
    n = N, s = S+1, d = D;
    for (int i=1;i<=n;i++) a[i] = A[i-1];
    int ans = solve();
    reverse(a+1, a+n+1);
    s = n+1-s;
    ans = max(solve(), ans);
    return ans;
}

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