QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#638413 | #8236. Snake Move | yangrun | WA | 610ms | 86648kb | C++17 | 1.6kb | 2024-10-13 15:52:14 | 2024-10-13 15:52:19 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define uint unsigned long long
int read() {
int res = 0, flg = 1;
char c = getchar();
while(!isdigit(c)) {
if(c == '-') flg = 0;
c = getchar();
}
while(isdigit(c)) {
res = (res << 3) + (res << 1) + (c ^ 48);
c = getchar();
}
return flg ? res : -res;
}
const int N = 3e3 + 10;
struct Node{
int x, y, d;
bool operator < (const Node& other) const{
return d > other.d;
}
};
priority_queue<Node> q;
int n, m, k;
int f[N][N], vis[N][N];
char ma[N][N];
int nxt[5] = {0, 1, 0, -1, 0};
signed main() {
memset(f, 0x3f, sizeof f);
memset(ma, '#', sizeof ma);
n = read(), m = read(), k = read();
int x, y, d;
x = read(), y = read();
f[x][y] = 0;
q.push({x, y, 0});
for(int i = k - 1; i; --i) {
x = read(), y = read();
vis[x][y] = i;
}
for(int i = 1; i <= n; ++i) {
scanf("%s", ma[i] + 1);
}
while(q.size()) {
Node cur = q.top();
q.pop();
x = cur.x, y = cur.y;
d = cur.d;
for(int i = 0; i < 4; ++i) {
int xx = x + nxt[i], yy = y + nxt[i + 1];
if(ma[xx][yy] == '#') continue;
int dd = max(d + 1, vis[xx][yy]);
if(dd < f[xx][yy]) {
f[xx][yy] = dd;
q.push({xx, yy, dd});
}
}
}
uint res = 0;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(vis[i][j] == -1 || f[i][j] > k * n * n) continue;
res += f[i][j] * f[i][j];
}
}
cout << res << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 86648kb
input:
4 5 5 3 5 3 4 3 3 3 2 4 2 ..... ..... ..... .....
output:
293
result:
ok single line: '293'
Test #2:
score: 0
Accepted
time: 3ms
memory: 84596kb
input:
2 2 4 1 1 1 2 2 2 2 1 .. ..
output:
14
result:
ok single line: '14'
Test #3:
score: 0
Accepted
time: 3ms
memory: 84412kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 610ms
memory: 84544kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: -100
Wrong Answer
time: 558ms
memory: 84680kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17465455560435
result:
wrong answer 1st lines differ - expected: '17464052497724', found: '17465455560435'