Submission #1042460

#	Time	Username	Problem	Language	Result	Execution time	Memory
1042460		lyis	Holiday (IOI14_holiday)	C++17	0 / 100	18 ms	5084 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;
 
#define int ll
 
int n, s, d;
int a[maxn];
int res = 0;
bool del[maxn];
 
int 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);
    }
    res = max(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 'll solve()':
holiday.cpp:24:49: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   24 |         while (q.size() > 0 && i - s + q.size() > d) {
      |                                ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:36:49: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   36 |         while (q.size() > 0 && i - s + q.size() > d) {
      |                                ~~~~~~~~~~~~~~~~~^~~
holiday.cpp:51:57: warning: comparison of integer expressions of different signedness: 'long long unsigned int' and 'll' {aka 'long long int'} [-Wsign-compare]
   51 |         while (q.size() > 0 && pos.top() - i + q.size() > j) {
      |                                ~~~~~~~~~~~~~~~~~~~~~~~~~^~~
holiday.cpp:65:1: warning: no return statement in function returning non-void [-Wreturn-type]
   65 | }
      | ^

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