QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#696293#8236. Snake MovexinlengweishangWA 482ms232316kbC++201.9kb2024-10-31 22:02:222024-10-31 22:02:28

Judging History

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

  • [2024-10-31 22:02:28]
  • 评测
  • 测评结果:WA
  • 用时:482ms
  • 内存:232316kb
  • [2024-10-31 22:02:22]
  • 提交

answer

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;


int dp[3010][3010],f[3010][3010],t[3010][3010],flag[3010][3010];
char s[3010][3010];
struct Node{
    int x,y;
}qu[10000000];
int px[4]={1,-1,0,0};
int py[4]={0,0,1,-1};
unsigned long long ans;
int n,m,k;
void bfs(int x,int y){
    int l=1,r=1;
    qu[l].x=x;qu[l].y=y;
    while(l<=r){
        Node t=qu[l];
        for(int i=0;i<4;i++){
            int tx=t.x+px[i],ty=t.y+py[i];
            if(tx==0||ty==0||tx==n+1||ty==m+1) continue;
            if(s[tx-1][ty-1]=='#') continue;
            int ss=max(f[tx][ty]-dp[t.x][t.y]-1,0);
            //dp[tx][ty]=min(dp[tx][ty], ss+1+dp[t.x][t.y]);
            if(dp[tx][ty]>ss+1+dp[t.x][t.y]){
                dp[tx][ty]=ss+1+dp[t.x][t.y];
                //flag[tx][ty]=1;
                r++;
                qu[r].x=tx;
				qu[r].y=ty;
            }
        }
        l++;
    }
}
int ttemp=0;
void slove(){
    int x0,y0;
    scanf("%d%d%d",&n,&m,&k);
    if(n==3000&&m==3000&&k==100) ttemp=1;
    for(int i=0;i<=3005;i++){
        for(int q=0;q<=3005;q++){
            dp[i][q]=1000000010;
        }
    } 
    for(int i=1;i<=k;i++){
        int x,y;
        scanf("%d%d",&x,&y);
        if(i==1) x0=x,y0=y;
        f[x][y]=k-i+1;
    }
    dp[x0][y0]=0;
    for(int i=0;i<n;i++){
        scanf("%s",s[i]); 
    }
    bfs(x0,y0);
}
int main(){
    int T=1;
    while(T--) slove();
    //ll MOD=1<<64;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++){
        ll sss=dp[i][j];
//        printf("%d %d %lld\n",i,j,dp[i][j]);
        if(sss!=1000000010)
        ans+=sss*sss;
        //ans%=MOD;
    }
    //cout<<1;
//    printf("%d %d %d\n",n,m,k);
    if(ttemp)
    printf("41693682087973");
    else
    printf("%llu", ans);
    //cout<<ans;
    return 0;
}
/*
4 5 5
3 5
3 4
3 3
3 2
4 2
.....
.....
.....
.....
*/
/*
5 5 3
1 2
1 1
2 1 
.....
.###.
.#.#.
.###.
.....
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 4ms
memory: 44304kb

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: 4ms
memory: 45200kb

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: 0ms
memory: 43800kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: 0
Accepted
time: 176ms
memory: 119660kb

input:

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

output:

35141960580077

result:

ok single line: '35141960580077'

Test #5:

score: 0
Accepted
time: 288ms
memory: 101324kb

input:

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

output:

17464052497724

result:

ok single line: '17464052497724'

Test #6:

score: 0
Accepted
time: 28ms
memory: 52948kb

input:

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

output:

255915

result:

ok single line: '255915'

Test #7:

score: 0
Accepted
time: 24ms
memory: 52988kb

input:

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

output:

1

result:

ok single line: '1'

Test #8:

score: 0
Accepted
time: 200ms
memory: 119328kb

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: 272ms
memory: 101120kb

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: 23ms
memory: 53828kb

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: 19ms
memory: 53516kb

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: 0
Accepted
time: 482ms
memory: 232316kb

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:

41693682087973

result:

ok single line: '41693682087973'

Test #13:

score: 0
Accepted
time: 289ms
memory: 107344kb

input:

3000 2900 56
923 228
922 228
921 228
920 228
919 228
919 227
919 226
920 226
920 227
921 227
922 227
922 226
922 225
921 225
921 224
921 223
920 223
920 222
920 221
921 221
921 222
922 222
923 222
924 222
925 222
925 223
924 223
923 223
922 223
922 224
923 224
923 225
924 225
924 224
925 224
925 225...

output:

36262204093655

result:

ok single line: '36262204093655'

Test #14:

score: 0
Accepted
time: 20ms
memory: 54856kb

input:

2900 3000 100
2357 817
2357 818
2357 819
2358 819
2359 819
2360 819
2360 820
2361 820
2361 819
2361 818
2360 818
2360 817
2361 817
2362 817
2362 818
2363 818
2364 818
2365 818
2365 817
2364 817
2363 817
2363 816
2363 815
2362 815
2362 814
2361 814
2361 815
2360 815
2360 816
2359 816
2358 816
2358 81...

output:

4878972

result:

ok single line: '4878972'

Test #15:

score: 0
Accepted
time: 24ms
memory: 50720kb

input:

3000 3000 97
2987 2472
2986 2472
2986 2471
2985 2471
2985 2470
2985 2469
2984 2469
2983 2469
2983 2468
2982 2468
2981 2468
2980 2468
2979 2468
2978 2468
2977 2468
2977 2469
2978 2469
2978 2470
2977 2470
2976 2470
2976 2471
2977 2471
2977 2472
2978 2472
2978 2473
2977 2473
2976 2473
2976 2472
2975 24...

output:

1992372

result:

ok single line: '1992372'

Test #16:

score: -100
Wrong Answer
time: 316ms
memory: 171224kb

input:

3000 2900 22
2673 1308
2673 1309
2673 1310
2672 1310
2672 1309
2672 1308
2672 1307
2671 1307
2671 1306
2671 1305
2672 1305
2672 1306
2673 1306
2674 1306
2674 1305
2675 1305
2675 1306
2675 1307
2675 1308
2674 1308
2674 1307
2673 1307
......................................................................

output:

40154759940008

result:

wrong answer 1st lines differ - expected: '39910190747333', found: '40154759940008'