답안 #832992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832992 2023-08-21T18:32:58 Z samgiz 십자가 놓기 (FXCUP4_cross) C++17
100 / 100
68 ms 14584 KB
#include <bits/stdc++.h>

using namespace std;

struct Cross {
  uint64_t inner, outer;
};

uint64_t SelectCross(int32_t K, vector<int32_t> I, vector<int32_t> O) {
  const uint32_t N = I.size();
  vector<Cross> crosses(N);
  for (uint32_t i = 0; i < N; i++) {
    crosses[i].inner = I[i];
    crosses[i].outer = O[i];
  }

  sort(crosses.begin(), crosses.end(), [](Cross a, Cross b) {
    return a.inner > b.inner;
  });

  // Comparator for priority queue that will force the smallest outer to the top
  const auto cmp = [](Cross a, Cross b) {
    return a.outer > b.outer;
  };
  // Priority queue that keeps the k Cross elements with the largest
  //  outer diameter out of the ones that we have processed so far.
  // And allows popping the one with the smallest outer diameter.
  priority_queue<Cross, vector<Cross>, decltype(cmp)> q(cmp);

  // Keep track of the best area so far
  uint64_t best_area = 0;

  for(const auto &c : crosses) {
    q.push(c);
		if (q.size() < static_cast<uint32_t>(K)) {
			continue;
		} else if (q.size() > static_cast<uint32_t>(K)) {
      q.pop();
    }
    const auto inner_size = c.inner;
    const auto outer_size = q.top().outer;
    best_area = max(best_area, 2 * inner_size * outer_size - inner_size * inner_size);
  }

  return best_area;
}
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 57 ms 9896 KB Output is correct
7 Correct 56 ms 9852 KB Output is correct
8 Correct 56 ms 9868 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 57 ms 9896 KB Output is correct
7 Correct 56 ms 9852 KB Output is correct
8 Correct 56 ms 9868 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 30 ms 5584 KB Output is correct
14 Correct 67 ms 10504 KB Output is correct
15 Correct 57 ms 10540 KB Output is correct
16 Correct 57 ms 10424 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 300 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 57 ms 9896 KB Output is correct
7 Correct 56 ms 9852 KB Output is correct
8 Correct 56 ms 9868 KB Output is correct
9 Correct 0 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 4 ms 852 KB Output is correct
13 Correct 30 ms 5584 KB Output is correct
14 Correct 67 ms 10504 KB Output is correct
15 Correct 57 ms 10540 KB Output is correct
16 Correct 57 ms 10424 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 4 ms 1364 KB Output is correct
20 Correct 34 ms 5864 KB Output is correct
21 Correct 47 ms 7360 KB Output is correct
22 Correct 60 ms 8724 KB Output is correct
23 Correct 64 ms 8756 KB Output is correct
24 Correct 68 ms 9592 KB Output is correct
25 Correct 65 ms 14536 KB Output is correct
26 Correct 58 ms 14584 KB Output is correct