QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511181#8236. Snake MoveIstleminTL 0ms3824kbC++171.3kb2024-08-09 17:12:282024-08-09 17:12:31

Judging History

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

  • [2024-08-09 17:12:31]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:3824kb
  • [2024-08-09 17:12:28]
  • 提交

answer

#include<bits/stdc++.h>

#pragma GCC optimize ("Ofast")

using namespace std;

#define rep(i,a,b) for(ll i = a; i<b; i++)
#define sz(v) ll(v.size())
#define all(v) v.begin(),v.end()

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    ll n,m,k; cin>>n>>m>>k;

    vector<vl> cost(n,vl(m,0));
    ll x,y; 
    priority_queue<tuple<ll,ll,ll>, vector<tuple<ll,ll,ll>>,greater<tuple<ll,ll,ll>>> q;
    
    rep(i,0,k){
        cin>>x>>y;
        --x; --y;
        if(i==0) q.emplace(0,x,y);
        cost[x][y] = k-i-1;
    }

    vector<string> g(n);
    rep(i,0,n) cin>>g[i];


    vector<vl> dist(n,vl(m,-1));
    
    while(q.size()){
        ll d; tie(d,x,y) = q.top(); q.pop();

        if(dist[x][y]!=-1) continue;
        dist[x][y] = d;

        for(auto [nx,ny] : vector<pll>{{x+1,y},{x-1,y},{x,y-1},{x,y+1},{x,y}}){
            if(nx<0 || nx>=n ||ny<0||ny>=m) continue;
            if(g[nx][ny]=='#') continue;

            q.emplace(max(d,cost[nx][ny])+1,nx,ny);
        }
    }
    unsigned long long ans = 0;

    rep(i,0,n) {
        rep(j,0,m){
            // cout<<(dist[i][j]+10)%10;
            if(dist[i][j]!=-1) ans += dist[i][j]*dist[i][j];
        }
        // cout<<endl;
    }

    cout<<ans<<endl;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3824kb

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

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: 3488kb

input:

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

output:

407

result:

ok single line: '407'

Test #4:

score: -100
Time Limit Exceeded

input:

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

output:


result: