QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#134215 | #1076. Flooding Fields | ChatGPT | RE | 0ms | 0kb | C++23 | 2.2kb | 2023-08-03 13:42:58 | 2023-08-03 13:43:03 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int INF = 1e9;
int dr[] = {-1, 0, 1, 0}, dc[] = {0, 1, 0, -1}; // up, right, down, left
int grid[105][105], dist[105][105], n;
vector<pii> cows;
priority_queue<pii, vector<pii>, greater<pii>> pq;
bool valid(int r, int c) {
return r >= 0 && r < n && c >= 0 && c < n;
}
void bfs() {
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
dist[i][j] = INF;
for(pii cow : cows)
dist[cow.first][cow.second] = grid[cow.first][cow.second], pq.push({grid[cow.first][cow.second], cow.first*n + cow.second});
while(!pq.empty()) {
pii top = pq.top();
pq.pop();
int d = top.first, r = top.second / n, c = top.second % n;
if(dist[r][c] != d)
continue;
for(int dir=0; dir<4; ++dir) {
int nr = r + dr[dir], nc = c + dc[dir];
if(!valid(nr, nc) || min(d, grid[nr][nc]) < dist[nr][nc])
dist[nr][nc] = min(d, grid[nr][nc]), pq.push({dist[nr][nc], nr*n + nc});
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int k, h;
while(cin >> n >> k >> h, n || k || h) {
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
cin >> grid[i][j];
cows.clear();
while(k--) {
int r, c;
cin >> r >> c;
cows.push_back({r, c});
}
bfs();
int water[25];
for(int i=0; i<h; ++i)
cin >> water[i];
water[h] = INF;
sort(water, water+h+1);
vector<pii> cells;
for(int i=0; i<n; ++i)
for(int j=0; j<n; ++j)
cells.push_back({dist[i][j], i*n + j});
sort(cells.begin(), cells.end());
int ans = 0, ptr = 0;
priority_queue<int> pq;
for(int i=0; i<=h; ++i) {
while(ptr < cells.size() && cells[ptr].first <= water[i])
pq.push(grid[cells[ptr].second / n][cells[ptr].second % n]), ++ptr;
while(!pq.empty() && pq.top() <= water[i])
pq.pop();
if(!pq.empty())
++ans, pq.pop();
}
cout << ans << '\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 1 3 2 1 2 3 1 3 2 4 2 1 1 0 2 1 2 4 2 0 1 1 2 0 0 0 1 1 1 1 0 1 0 50 50 24 5 20 21 3 2 9 22 15 19 22 18 14 19 14 15 4 22 22 7 12 7 2 2 0 25 0 7 6 4 3 2 17 1 12 7 12 1 19 12 3 23 5 5 10 22 15 17 3 13 4 10 21 7 12 10 22 23 18 17 5 17 18 2 14 12 13 13 19 19 18 8 11 3 0 24 0 6 1 9 12 14 13 20 22 5 13 ...