Submission #920840

#	Time	Username	Problem	Language	Result	Execution time	Memory
920840		rxlfd314	Holiday (IOI14_holiday)	C++17	47 / 100	5078 ms	2260 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

ll findMaxAttraction(int N, int start, int d, int *A) {
  ll ans = 0, sum = 0;
  priority_queue<ll> pq;
  ROF(i, start, max(0, start - d)) { // left then right
    sum = 0;
    while (size(pq))
      pq.pop();
    int j = i;
    for (; j <= start; j++) {
      pq.push(-A[j]);
      sum += A[j];
    }
    while (size(pq) && size(pq) + start - i > d) {
      sum += pq.top();
      pq.pop();
    }
    ans = max(ans, sum);
    for (; j < N; j++) {
      pq.push(-A[j]);
      sum += A[j];
      while (size(pq) && size(pq) + j + start - 2 * i > d) {
        sum += pq.top();
        pq.pop();
      }
      if (j + start - 2 * i <= d)
        ans = max(ans, sum);
    }
  }
  ROF(i, start, max(0, start - d)) { // right then left
    sum = 0;
    while (size(pq))
      pq.pop();
    int j = i;
    for (; j <= start; j++) {
      pq.push(-A[j]);
      sum += A[j];
    }
    while (size(pq) && size(pq) + start - i > d) {
      sum += pq.top();
      pq.pop();
    }
    ans = max(ans, sum);
    for (; j < N; j++) {
      pq.push(-A[j]);
      sum += A[j];
      while (size(pq) && size(pq) + j * 2 - start - i > d) {
        sum += pq.top();
        pq.pop();
      }
      if (size(pq) + j * 2 - start - i <= d)
        ans = max(ans, sum);
    }
  }
  return ans;
}

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