제출 #742525

#제출 시각아이디문제언어결과실행 시간메모리
742525bogdanvladmihaiT-Covering (eJOI19_covering)C++14
100 / 100
268 ms15948 KiB
#include <iostream> #include <vector> #include <utility> #include <limits.h> #include <queue> const std::vector<std::pair<int, int>> dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; inline bool inside(const std::pair<int, int> &point, int N, int M) { return point.first >= 0 && point.second >= 0 && point.first < N && point.second < M; } int main() { int N, M, K; std::cin >> N >> M; std::vector<std::vector<int>> mat(N, std::vector<int>(M)); for (auto &line : mat) { for (int &x : line) { std::cin >> x; } } std::cin >> K; std::vector<std::vector<bool>> red(N, std::vector<bool>(M)); for (int i = 0; i < K; i++) { int x, y; std::cin >> x >> y; red[x][y] = true; } std::vector<std::vector<int>> color(N, std::vector<int>(M, -1)); std::vector<std::vector<bool>> used(N, std::vector<bool>(M)); std::vector<int> erase, sum, difference; for (int i = 0; i < N; i++) { for (int j = 0; j < M; j++) { if (!used[i][j] && red[i][j]) { std::queue<std::pair<int, int>> Q; Q.emplace(i, j); color[i][j] = erase.size(); erase.push_back(INT_MAX); sum.push_back(0); difference.push_back(0); used[i][j] = true; while (!Q.empty()) { std::pair<int, int> curr = Q.front(); Q.pop(); difference.back() += (red[curr.first][curr.second] ? -3 : 1); sum.back() += mat[curr.first][curr.second]; if (!red[curr.first][curr.second]) { erase.back() = std::min(erase.back(), mat[curr.first][curr.second]); } for (const std::pair<int, int> &dir : dirs) { std::pair<int, int> next = {dir.first + curr.first, dir.second + curr.second}; if (inside(next, N, M) && !used[next.first][next.second] && (red[curr.first][curr.second] || red[next.first][next.second])) { color[next.first][next.second] = color[curr.first][curr.second]; used[next.first][next.second] = true; Q.push(next); } } } } } } int answer = 0; for (size_t i = 0; i < erase.size(); i++) { if (difference[i] < 0) { std::cout << "No\n"; return 0; } answer += sum[i] - erase[i] * (difference[i] > 0); } std::cout << answer << "\n"; return 0; }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...