| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 982158 | totoro | Aliens (IOI16_aliens) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// UNSOLVED SUBTASK 1 (04 pts)
// UNSOLVED SUBTASK 2 (12 pts)
// UNSOLVED SUBTASK 3 (09 pts)
// UNSOLVED SUBTASK 4 (16 pts)
// UNSOLVED SUBTASK 5 (19 pts)
// UNSOLVED SUBTASK 6 (40 pts)
// [+-+]----------------------
// TOTAL 0/100 pts
#include "aliens.h"
#include <algorithm>
#include <unordered_set>
#include <vector>
struct Coordinate {
long long row, col;
Coordinate(long long row, long long col) : row(std::min(row, col)), col(std::max(row, col)) {}
bool operator<(const Coordinate& other) const {
if (row == other.row) {
return col > other.col;
}
return row < other.row;
}
};
struct Range {
long long start, end;
size_t next;
Range(long long start, long long end, size_t next) : start(start), end(end), next(next){};
long long merge(const Range& other) const {
return 2 * (other.start - start) * (other.end - end) - (other.start <= end ? (end - other.start - 1) * (end - other.start - 1) : 0);
}
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
std::vector<Coordinate> points;
for (size_t i = 0; i < n; ++i) {
points.push_back(Coordinate(r[i], c[i]));
}
std::sort(points.begin(), points.end());
long long area = 0;
std::vector<Range> ranges;
long long furthestStart = -1;
long long furthestEnd = -1;
for (size_t i = 0; i < points.size(); ++i) {
Coordinate point = points[i];
if (point.row > furthestStart && point.col > furthestEnd) {
furthestStart = point.row;
furthestEnd = point.col;
ranges.emplace_back(point.row, point.col, i + 1);
area += (point.col - point.row + 1) * (point.col - point.row + 1);
}
}
size_t excludedCount = 0;
while (ranges.size() - excludedCount > k) {
long long bestAmount = LLONG_MAX;
size_t bestIndex = 0;
for (size_t i = 0; i < ranges.size() - 1; i = ranges[i].next) {
long long score = ranges[i].merge(ranges[ranges[i].next]);
if (score < bestAmount) {
bestAmount = score;
bestIndex = i;
}
}
ranges[bestIndex].end = ranges[ranges[bestIndex].next].end;
area += bestAmount;
ranges[bestIndex].next = ranges[ranges[bestIndex].next].next;
++excludedCount;
}
return area;
}