Submission #1129213

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129213		mnbvcxz123	Crosses on the Grid (FXCUP4_cross)	C++20	100 / 100	77 ms	10936 KiB

cross

#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;
}

• Subtask 1: 8 / 8
• Subtask 2: 55 / 55
• Subtask 3: 37 / 37