제출 #982448

#제출 시각아이디문제언어결과실행 시간메모리
982448totoroAliens (IOI16_aliens)C++17
25 / 100
2067 ms17216 KiB
// SOLVED SUBTASK 1 (04 pts) // SOLVED SUBTASK 2 (12 pts) // SOLVED SUBTASK 3 (09 pts) // UNSOLVED SUBTASK 4 (16 pts) // UNSOLVED SUBTASK 5 (19 pts) // UNSOLVED SUBTASK 6 (40 pts) // [+-+]---------------------- // TOTAL 25/100 pts #include "aliens.h" #include <algorithm> #include <climits> #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; Range(long long start, long long end) : start(start), end(end){}; long long merge(const Range& other) const { return 2 * (other.start - start) * (other.end - end) - (other.start > end ? (other.start - end - 1) * (other.start - end - 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()); 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) { ranges.emplace_back(point.row, point.col); furthestStart = point.row; furthestEnd = point.col; } } std::vector<std::vector<long long>> dp; for (size_t range = 0; range < ranges.size(); ++range) { dp.emplace_back(); for (size_t coverCount = 1; coverCount <= k; ++coverCount) { if (coverCount == 1 || range == 0) { dp[range].push_back((ranges[range].end - ranges[0].start + 1) * (ranges[range].end - ranges[0].start + 1)); continue; } long long best = LLONG_MAX; for (size_t earlier = 0; earlier < range; ++earlier) { long long score = dp[earlier][coverCount - 2] + (ranges[range].end - ranges[earlier + 1].start + 1) * (ranges[range].end - ranges[earlier + 1].start + 1); if (ranges[earlier + 1].start <= ranges[earlier].end) { score -= (ranges[earlier].end - ranges[earlier + 1].start + 1) * (ranges[earlier].end - ranges[earlier + 1].start + 1); } if (score < best) { best = score; } } dp[range].push_back(best); } } return dp[ranges.size() - 1][k - 1]; }

컴파일 시 표준 에러 (stderr) 메시지

aliens.cpp: In function 'long long int take_photos(int, int, int, std::vector<int>, std::vector<int>)':
aliens.cpp:37:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   37 |     for (size_t i = 0; i < n; ++i) {
      |                        ~~^~~
aliens.cpp:57:48: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   57 |         for (size_t coverCount = 1; coverCount <= k; ++coverCount) {
      |                                     ~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...