QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#712994 | #8236. Snake Move | KafuuChinocpp# | WA | 301ms | 382716kb | C++14 | 3.5kb | 2024-11-05 17:45:12 | 2024-11-05 17:45:12 |
Judging History
answer
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int max1 = 3000, max2 = 1e5;
const int inf = 0x3f3f3f3f;
int n, m, k;
int num[max1 + 5][max1 + 5];
char Map[max1 + 5][max1 + 5];
int f[max1 + 5][max1 + 5], g[max1 + 5][max1 + 5];
struct Point
{
int x, y;
Point () {}
Point ( int __x, int __y )
{ x = __x, y = __y; }
};
vector <Point> bin[max1 * max1 + max2];
int main ()
{
int x, y, startx, starty;
scanf("%d%d%d", &n, &m, &k);
for ( int i = 1; i <= k; i ++ )
{
scanf("%d%d", &x, &y);
num[x][y] = i;
if ( i == 1 )
startx = x, starty = y;
}
for ( int i = 1; i <= n; i ++ )
scanf("%s", Map[i] + 1);
memset(g, 0x3f, sizeof(g));
f[startx][starty] = k, g[startx][starty] = 0;
bin[0].push_back(Point(startx, starty));
for ( int i = 0; i <= n * n + m; i ++ )
{
for ( auto now : bin[i] )
{
x = now.x, y = now.y;
--x;
if ( x >= 1 && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y] - g[now.x][now.y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
++x;
++x;
if ( x <= n && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y] - g[now.x][now.y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
--x;
--y;
if ( y >= 1 && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y] - g[now.x][now.y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
++y;
++y;
if ( y <= m && Map[x][y] != '#' && g[x][y] == inf )
{
if ( num[x][y] && num[x][y] + 1 <= f[now.x][now.y] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
f[x][y] = num[x][y], g[x][y] = g[now.x][now.y] + 1 + f[now.x][now.y] - num[x][y] - g[now.x][now.y], bin[g[x][y]].push_back(Point(x, y));
else
f[x][y] = f[now.x][now.y], g[x][y] = g[now.x][now.y] + 1, bin[g[x][y]].push_back(Point(x, y));
}
--y;
}
}
unsigned long long ans = 0;
for ( int i = 1; i <= n; i ++ )
for ( int j = 1; j <= m; j ++ )
if ( g[i][j] != inf )
ans += 1uLL * g[i][j] * g[i][j];
printf("%llu\n", ans);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 24ms
memory: 257888kb
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: 37ms
memory: 256880kb
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: 22ms
memory: 257412kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 204ms
memory: 380904kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 280ms
memory: 355864kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 56ms
memory: 270476kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 60ms
memory: 268440kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 167ms
memory: 378524kb
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: 0
Accepted
time: 301ms
memory: 358884kb
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:
22509095749285
result:
ok single line: '22509095749285'
Test #10:
score: 0
Accepted
time: 59ms
memory: 270708kb
input:
3000 2900 10 326 1781 325 1781 325 1782 325 1783 325 1784 324 1784 324 1783 323 1783 323 1782 324 1782 ##.#....#.###.######..#.#.....##.#.##..####.####.##..#..#.###.#####....##.#.##.#..###..##.###.##.#####.###..##.#..##..##.#..##.#.#.##...##..#.##.##........#..#..###.##.###.####.#..########.##.....#...
output:
40571
result:
ok single line: '40571'
Test #11:
score: 0
Accepted
time: 73ms
memory: 267596kb
input:
2900 3000 10 2447 135 2447 136 2447 137 2447 138 2447 139 2447 140 2448 140 2448 139 2449 139 2449 138 .#.##.##..#.###########.#####.###....#####.########..##..#.####.##.##.####.####..#.#####.##.#.#.###.##.#.##.####..##.#.####..###..###...##...##.#####.#####.#...#####.####..##.##.#.#..#..####.##..##...
output:
2705
result:
ok single line: '2705'
Test #12:
score: -100
Wrong Answer
time: 189ms
memory: 382716kb
input:
3000 3000 100 2573 1917 2572 1917 2572 1916 2573 1916 2574 1916 2574 1915 2573 1915 2572 1915 2571 1915 2571 1914 2570 1914 2570 1915 2569 1915 2569 1916 2568 1916 2568 1917 2569 1917 2570 1917 2570 1916 2571 1916 2571 1917 2571 1918 2570 1918 2569 1918 2569 1919 2570 1919 2571 1919 2571 1920 2572 1...
output:
41693682056445
result:
wrong answer 1st lines differ - expected: '41693682087973', found: '41693682056445'