QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#681004 | #8236. Snake Move | 1ockhart | WA | 395ms | 157684kb | C++20 | 2.2kb | 2024-10-27 00:08:17 | 2024-10-27 00:08:22 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("unroll-loops")
//#pragma GCC target("avx2")
using ll = long long;
//using i128 = __int128_t;
#define endl "\n"
#define int long long
#define db cout << "db" << endl;
#define x first
#define y second
typedef pair<int, int> PII;
const int N = 1e5 + 10, M = 3010;
ll inf = 2e18;
int n, m, k;
int a[N], b[N], dis[M][M], ma[M][M], vis[M][M];
string s[M];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
void bfs(int x, int y) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
dis[i][j] = inf;
}
}
dis[x][y] = 0;
queue<PII> q;
q.push({x, y});
while (q.size()) {
int x1 = q.front().x, y1 = q.front().y;
q.pop();
if (vis[x1][y1]) {
continue;
}
vis[x1][y1] = 1;
for (int i = 0; i < 4; i++) {
int x2 = x1 + dx[i], y2 = y1 + dy[i];
if (x2 < 0 || x2 >= n || y2 < 0 || y2 >= m || s[x2][y2] == '#') {
continue;
} else if (ma[x2][y2] && dis[x1][y1] < k - ma[x2][y2]) {
//dis[x2][y2] = min(dis[x2][y2], max(k - ma[x2][y2], dis[x1][y1] + 1));
dis[x2][y2] = min(dis[x2][y2], k - ma[x2][y2] + 1);
q.push({x2, y2});
} else if (dis[x2][y2] > dis[x1][y1] + 1){
if (ma[x2][y2]) {
dis[x2][y2] = min(max(dis[x2][y2], k - ma[x2][y2]), max(k - ma[x2][y2], dis[x1][y1] + 1));
} else {
dis[x2][y2] = dis[x1][y1] + 1;
}
q.push({x2, y2});
}
}
}
}
void solve() {
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) {
cin >> a[i] >> b[i];
a[i]--; b[i]--;
ma[a[i]][b[i]] = i;
}
for (int i = 0; i < n; i++) {
cin >> s[i];
}
bfs(a[1], b[1]);
for (int i = 2; i <= k; i++) {
dis[a[i]][b[i]] = max(dis[a[i]][b[i]], k - i);
}
int ans = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = dis[i][j];
if (x != inf) {
ans += x * x;
//cout << i + 1 << " " << j + 1 << " " << x * x << endl;
}
}
}
cout << ans << endl;
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int q = 1;
//cin >> q;
while (q --) {
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 9800kb
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: 1ms
memory: 7752kb
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: 1ms
memory: 9872kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 327ms
memory: 157616kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 395ms
memory: 155020kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 16ms
memory: 89152kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 21ms
memory: 86688kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 337ms
memory: 157052kb
input:
2900 3000 10 2883 1758 2883 1759 2883 1760 2883 1761 2883 1762 2884 1762 2884 1763 2883 1763 2882 1763 2882 1764 ........................................................#............................#........................................................................................................
output:
49803365625286
result:
ok single line: '49803365625286'
Test #9:
score: -100
Wrong Answer
time: 359ms
memory: 157684kb
input:
3000 3000 10 2015 1932 2015 1931 2015 1930 2015 1929 2016 1929 2017 1929 2018 1929 2018 1928 2018 1927 2017 1927 #...#...#..#.........#.......#####....#...###..#..###..###....##.....#..#..#...#.....##...##.#..#..##.###.........##.....#....#..##.##.#.#.##.#.#.#.....#....##.##.#..##....#....#...#.#......
output:
22509095749317
result:
wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749317'