QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511181 | #8236. Snake Move | Istlemin | TL | 0ms | 3824kb | C++17 | 1.3kb | 2024-08-09 17:12:28 | 2024-08-09 17:12:31 |
Judging History
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 ........................................................................................................#................................................................................................................................................................#................