QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#416431 | #8236. Snake Move | Godwang# | WA | 600ms | 94408kb | C++14 | 3.5kb | 2024-05-21 20:35:33 | 2024-05-21 20:35:36 |
Judging History
answer
#include <iostream>
using namespace std;
#include <set>
#include <algorithm>
#include <cmath>
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <string.h>
#include <stdlib.h>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <stack>
#include <queue>
#include <ctype.h>
#include <vector>
#include <random>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define rep(i, a, n) for (int i = a; i <= n; i++)
#define per(i, a, n) for (int i = n; i >= a; i--)
#define pii pair<int, int>
#define pli pair<ll, int>
#define pil pair<int, ll>
#define pll pair<ll ,ll >
#define endl '\n'
const double pai = acos(-1);
ll extend_gcd(ll a, ll b, ll &x, ll &y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
ll d = extend_gcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
ll fastpow(ll a, ll n, ll mod)
{
ll ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a)%mod; //% mod
a = (a * a)%mod; //% mod
n >>= 1;
}
return ans;
}
int dir[4][2] =
{
{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; // d a w s
const int inf = 1000000000;
const ll mod = 1e9 + 7, P1 = 13331;
const double eps = 1e-7;
const int N =3000 + 10, M = 1e6 + 10;
int n,m,k;
bool vis[N][N];
ull ans[N][N];
string ss[N];
int a[N][N];
struct node
{
int x,y,t,s;
node(int a,int b,int c,int d)
{
x=a;
y=b;
t=c;
s=d;
}
bool operator <(const node &b) const
{
return t>b.t;
}
// bool operator > (const node &b)const{
// return t>b.t;
// }
};
int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
// freopen("ain.txt", "r", stdin);freopen("aout.txt", "w", stdout);
cin>>n>>m>>k;
int xx,yy;
rep(i,1,k)
{
int x,y;
cin>>x>>y;
if(i==1)
{
xx=x;
yy=y;
}
a[x][y]=k-i+1;
}
rep(i,1,n)
{
cin>>ss[i];
ss[i]=' '+ss[i];
}
rep(i,1,n)
{
rep(j,1,m)
{
ans[i][j]=inf;
}
}
priority_queue<node> q;
q.push(node(xx,yy,0,0));
vis[xx][yy]=1;
while(q.size())
{
//
//cout<<111111;
node u=q.top();
q.pop();
int x=u.x,y=u.y,t=u.t,s=u.s;
ans[x][y]=min(ans[x][y],(ull)t);
// cout<<"vis: "<<x<<' '<<y<<endl;
rep(i,0,3)
{
int xx=x+dir[i][0],yy=y+dir[i][1];
if(xx<1||xx>n||yy<1||yy>m||vis[xx][yy]||ss[xx][yy]=='#')
{
continue;
}
if(t+s+1>=a[xx][yy])//buhui
{
q.push(node(xx,yy,t+1,s));
vis[xx][yy]=1;
//
// cout<<11111;
}
else
{
int temp=a[xx][yy]-(t+1+s);
q.push(node(x,y,t+ temp , s+temp ));
// cout<<2222222;
}
}
}
ull anss=0;
rep(i,1,n)
{
rep(j,1,m)
{
if(ans[i][j]==inf)
{
continue;
}
ull temp=ans[i][j]*ans[i][j];
//
//cout<<ans[i][j]<<" ";
//
anss+=temp;
}
//
// cout<<endl;
//
}
cout<<anss;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 7756kb
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: 1ms
memory: 7652kb
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: 1ms
memory: 7948kb
input:
5 5 3 1 2 1 1 2 1 ..... .###. .#.#. .###. .....
output:
407
result:
ok single line: '407'
Test #4:
score: 0
Accepted
time: 591ms
memory: 94224kb
input:
3000 2900 1 1882 526 ........................................................................................................#................................................................................................................................................................#................
output:
35141960580077
result:
ok single line: '35141960580077'
Test #5:
score: 0
Accepted
time: 590ms
memory: 92484kb
input:
2900 3000 1 1333 1773 .....#....#......#.#..#...#.....#.#.#.#....#...###.#..#.....##....####..#......#.......######.#........#..#......#...###.#.#..#.....#.#........##..#..#.#..#.###.#.#...#..#.##..#...#....#..#.##..#......#.######............#.#...#......#......#..#.#.#.#...#...#..##........#.###.....
output:
17464052497724
result:
ok single line: '17464052497724'
Test #6:
score: 0
Accepted
time: 24ms
memory: 86784kb
input:
3000 3000 1 2755 225 ##..#.##.....####..#...###.#.##.#.##.#......###.#####..#..####....#.#.####..##..##.#...#...##..#.#.##..#....##.#...#.....##.#...##.##.##..##..#######.####.####......##.##.#....#..#.....#..##.#.#...#.####..##.#..#...###..###.#.#...##.#.....###.####......##...#...#....#.#...#.#.#....
output:
255915
result:
ok single line: '255915'
Test #7:
score: 0
Accepted
time: 24ms
memory: 85964kb
input:
3000 2900 1 878 738 #.##.##..##.#.#.###.#...###.####.#.###.####.##.#.#####.#.####..#.#.###.###..####.####...###..####.########..##..#####.#....#####.#.#########..#.###.##.##.#####.#####.#.##..###..##.#####.#.############..##.###.##.##..########.#.###..###...######.####...#######.###.###..####.######...
output:
1
result:
ok single line: '1'
Test #8:
score: 0
Accepted
time: 600ms
memory: 91208kb
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: -100
Wrong Answer
time: 599ms
memory: 94408kb
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:
22509095749225
result:
wrong answer 1st lines differ - expected: '22509095749285', found: '22509095749225'