oj.uz

답안 #920840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
920840 2024-02-03T05:36:58 Z rxlfd314 휴가 (IOI14_holiday) C++17
47 / 100
 5000 ms 2260 KB 
#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.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 604 KB Output is correct

Subtask #2
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 2004 KB Output is correct
2 Correct 11 ms 2000 KB Output is correct
3 Correct 11 ms 2004 KB Output is correct
4 Correct 11 ms 2000 KB Output is correct
5 Correct 20 ms 1492 KB Output is correct
6 Correct 5 ms 1240 KB Output is correct
7 Correct 12 ms 1496 KB Output is correct
8 Correct 14 ms 1496 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct

Subtask #3
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 651 ms 888 KB Output is correct
2 Correct 125 ms 860 KB Output is correct
3 Correct 488 ms 860 KB Output is correct
4 Correct 252 ms 864 KB Output is correct
5 Correct 429 ms 856 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 14 ms 604 KB Output is correct
8 Correct 21 ms 836 KB Output is correct
9 Correct 24 ms 604 KB Output is correct

Subtask #4
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 5078 ms 2260 KB Time limit exceeded
2 Halted 0 ms 0 KB -