QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#57977 | #3892. Efficiently Elevated | Beevo# | RE | 2ms | 3672kb | C++23 | 1.8kb | 2022-10-24 01:23:02 | 2022-10-24 01:23:04 |
Judging History
answer
#include <bits/stdc++.h>
#define el '\n'
#define ll long long
#define ld long double
#define Beevo ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int h, w;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
bool valid(int x, int y) {
return x >= 0 && x < h && y >= 0 && y < w;
}
void testCase() {
cin >> h >> w;
int g[h][w];
vector<pair<int, int>> lvl[h * w];
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
cin >> g[i][j];
if (g[i][j] > 1)
lvl[g[i][j]].emplace_back(i, j);
}
}
bool b[h][w];
memset(b, 0, sizeof b);
int sol = 0;
for (int i = h * w - 1; i >= 2; i--) {
priority_queue<pair<int, pair<int, int>>> pq;
for (auto j: lvl[i]) {
int x = j.first, y = j.second;
pq.push({b[x][y], {x, y}});
for (int k = 0; k < 4; k++) {
int newX = x + dx[k], newY = y + dy[k];
if (valid(newX, newY) && g[newX][newY] < i)
b[newX][newY] = 1;
}
}
while (pq.size()) {
int x = pq.top().second.first;
int y = pq.top().second.second;
pq.pop();
if (!b[x][y])
sol++, b[x][y] = 1;
for (int k = 0; k < 4; k++) {
int newX = x + dx[k], newY = y + dy[k];
if (valid(newX, newY) && g[newX][newY] == i && !b[newX][newY]) {
b[newX][newY] = 1;
pq.push({1, {newX, newY}});
}
}
}
}
cout << sol;
}
signed main() {
Beevo
int T = 1;
// cin >> T;
while (T--)
testCase();
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 2ms
memory: 3556kb
input:
3 3 1 2 3 0 0 4 7 6 5
output:
1
result:
ok single line: '1'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3560kb
input:
6 7 0 0 0 0 0 0 0 0 1 2 3 2 1 0 0 1 2 3 2 1 0 0 0 0 0 0 0 0 0 1 0 5 0 0 0 0 0 0 0 0 0 0
output:
2
result:
ok single line: '2'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3628kb
input:
4 4 1 1 2 1 2 2 1 2 1 2 2 1 2 1 2 2
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 2ms
memory: 3672kb
input:
50 25 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 10 10 0 10 10 0 10 11 0 10 10 0 0 0 0 0 0 0 0 0 4 0 0 0 0 10 0 0 0 10 0 10 0 0 0 11 0 0 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5 4 3 0 3 4 5 0 10 0 0 0 10 0 11 0 0 0 10 0 0 0 0 0 0 0 0 0 3 0 0 0 0 10 10 0 10 1...
output:
28
result:
ok single line: '28'
Test #5:
score: -100
Runtime Error
input:
500 500 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 1000000000 999999999 100000000...