QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#713070#8236. Snake MoveKafuuChinocpp#WA 341ms385312kbC++143.5kb2024-11-05 18:00:192024-11-05 18:00:20

Judging History

你现在查看的是最新测评结果

  • [2024-11-05 18:00:20]
  • 评测
  • 测评结果:WA
  • 用时:341ms
  • 内存:385312kb
  • [2024-11-05 18:00:19]
  • 提交

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] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y] + g[now.x][now.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] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y] + g[now.x][now.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] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y] + g[now.x][now.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] && f[now.x][now.y] - num[x][y] >= g[now.x][now.y] + 1 )
                    f[x][y] = num[x][y] + g[now.x][now.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;
        }
    }

    // for ( int i = 1; i <= n; i ++, putchar('\n') )
    //     for ( int j = 1; j <= m; j ++ )
    //         printf("%d ", g[i][j]);

    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;
}

詳細信息

Test #1:

score: 100
Accepted
time: 43ms
memory: 257728kb

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: 27ms
memory: 257808kb

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: 40ms
memory: 257604kb

input:

5 5 3
1 2
1 1
2 1
.....
.###.
.#.#.
.###.
.....

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 185ms
memory: 380536kb

input:

3000 2900 1
1882 526
........................................................................................................#................................................................................................................................................................#................

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 341ms
memory: 355696kb

input:

2900 3000 1
1333 1773
.....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 81ms
memory: 266848kb

input:

3000 3000 1
2755 225
##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 71ms
memory: 269388kb

input:

3000 2900 1
878 738
#.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 201ms
memory: 380140kb

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: 296ms
memory: 358796kb

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: 106ms
memory: 267096kb

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: 89ms
memory: 268908kb

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: 230ms
memory: 385312kb

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:

41693682061313

result:

wrong answer 1st lines differ - expected: '41693682087973', found: '41693682061313'