Submission #1007820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1007820		onbert	Holiday (IOI14_holiday)	C++17	23 / 100	19 ms	5912 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e5 + 5;
int n;
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 findMaxAttraction(int32_t N, int32_t S, int32_t d, int32_t A[]) {
    n = N;
    vector<pair<int,int>> v;
    for (int i=1;i<=n;i++) {
        a[i] = A[i-1];
        v.push_back({a[i], i});
    }
    sort(v.rbegin(), v.rend());
    int ans = 0, r = n;
    for (auto [val, id]:v) {
        update(id, val, 0);
        update(id, 1, 1);
        while (r + qry(r-1, 1) > d) r--;
        ans = max(qry(r, 0), ans);
    }
    return ans;
}

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