Submission #1042462

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042462		lyis	Holiday (IOI14_holiday)	C++17	100 / 100	39 ms	5924 KiB

holiday

#include <holiday.h>
#include <bits/stdc++.h>
 
#define fi  first
#define se  second
 
using namespace std;
 
typedef long long ll;
const int       maxn  = 1e5 + 10;
 
template <class an, class lyis>
    bool minimize(an &x, const lyis y){
        if(x > y){
            x = y;
            return true;
        } else return false;
    }
 
template <class an, class lyis>
    bool maximize(an &x, const lyis y){
        if(x < y){
            x = y;
            return true;
        } else return false;
    }
 
#define int ll
 
int n, s, d;
int a[maxn];
int res;
bool del[maxn];
 
void solve() {
    int ans = 0, cur = 0;
    priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> q;
    for (int i = s; i <= n; i++) {
        q.push({a[i], -i}), cur += a[i];
        while (q.size() > 0 && i - s + q.size() > d) {
            cur -= q.top().first;
            q.pop();
        }
        ans = max(cur, ans);
    }
    while (q.size() > 0) q.pop();
    cur = 0;
    priority_queue <int> pos;
    memset(del, 0, sizeof(del));
    for (int i = s; i <= n; i++) {
        q.push({a[i], -i}), pos.push(i), cur += a[i];
        while (q.size() > 0 && i - s + q.size() > d) {
            pair <int, int> x = q.top();
            q.pop();
            cur -= x.first;
            del[-x.second] = 1;
        }
        if (cur == ans) break;
    }
    while (pos.size() > 0) {
        int x = pos.top();
        if (del[x]) pos.pop(), del[x] = 0;
        else break;
    }
    for (int i = s - 1, j = d - 1; i >= 1 && j >= 1; --i, --j) {
        q.push({a[i], -i}), pos.push(i), cur += a[i];
        while (q.size() > 0 && pos.top() - i + q.size() > j) {
            pair <int, int> x = q.top();
            q.pop();
            cur -= x.first;
            del[-x.second] = 1;
            while (pos.size() > 0) {
                int x = pos.top();
                if (del[x]) pos.pop(), del[x] = 0;
                else break;
            }
        }
        ans = max(cur, ans);
    }
    maximize(res, ans);
}
 
int findMaxAttraction(int32_t N, int32_t S, int32_t D, int32_t attraction[]) {
  s = S;
  d = D;
  n = N;
  for (int i = 1; i <= n; i++) a[i] = attraction[i - 1];
  ++s;
    solve();
    reverse(a + 1, a + n + 1);
    s = n - s + 1;
    solve();
    return res;
}

Compilation message (stderr)

holiday.cpp: In function 'void solve()':
holiday.cpp:40:49: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   40 |         while (q.size() > 0 && i - s + q.size() > d) {
      |                                ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:52:49: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   52 |         while (q.size() > 0 && i - s + q.size() > d) {
      |                                ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:67:57: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   67 |         while (q.size() > 0 && pos.top() - i + q.size() > j) {
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~

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