| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1002455 |
2024-06-19T15:01:32 Z |
vjudge1 |
Robots (APIO13_robots) |
C++17 |
|
3 ms |
6488 KB |
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<set>
#include<queue>
#include<deque>
using namespace std;
#define int long long
#define len(x) (int)x.size()
#define all(x) (x).begin() , (x).end()
#define Bekabot ios_base::sync_with_stdio(NULL);cin.tie(0);cout.tie(0);
#define pb push_back
#define pii pair<int , int>
#define F first
#define S second
#define fopen(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
const int N = 1e5 + 78 , M = 1e9 + 7 , inf = 1e18;
int h , w , n;
int ans[10][10][505][505];
int dp[505][505];
int dx[] = {1 , 0 , -1 , 0} , dy[] = {0 , 1 , 0 , -1};
char a[505][505];
vector<pii> g[505][505];
pii id[10];
pii s[505][505][5];
bool p(int x , int y){
if(1 <= x and x <= h and 1 <= y and y <= w and a[x][y] != 'x')return 1;
return 0;
}
pii fnd(int x , int y , int t){
if(s[x][y][t].F and s[x][y][t].S)return s[x][y][t];
s[x][y][t] = {-inf , -inf};
int tt = t;
if(a[x][y] == 'A'){
tt = (tt + 1) % 4;
}
else if(a[x][y] == 'C'){
tt = (tt + 3) % 4;
}
int x1 = x + dx[tt] , y1 = y + dy[tt];
if(p(x1 , y1))return s[x][y][t] = fnd(x1 , y1 , tt);
else return s[x][y][t] = {x , y};
}
void build(){
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
if(a[i][j] == 'x')continue;
for(int t = 0 ; t <= 3 ; t++){
pii aa = fnd(i , j , t);
if(a[i][j] != 'x' and aa.F > 0)g[i][j].pb(aa);
}
}
}
}
void skibidi_dop_dop_dop_yes_yes(){
cin >> n >> w >> h;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
cin >> a[i][j];
if(a[i][j] >= '1' and a[i][j] <= '9')id[a[i][j] - '0'] = {i , j};
}
}
build();
for(int l = 1 ; l <= n ; l++){
for(int r = 1 ; r <= n ; r++){
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
ans[l][r][i][j] = inf;
}
}
}
}
for(int i = 1 ; i <= n ; i++){
ans[i][i][id[i].F][id[i].S] = 0;
}
for(int ll = 1 ; ll <= n ; ll++){
for(int l = 1 ; l + ll - 1 <= n ; l++){
int r = l + ll - 1;
set<pair<int , pii>> st;
for(int i = 1 ; i <= h ; i++){
for(int j = 1 ; j <= w ; j++){
for(int md = l ; md < r ; md++){
ans[l][r][i][j] = min(ans[l][r][i][j] , ans[l][md][i][j] + ans[md + 1][r][i][j]);
}
if(ans[l][r][i][j] != inf)st.insert({ans[l][r][i][j] , {i , j}});
}
}
while(len(st)){
auto v = *st.begin();
st.erase(st.begin());
for(auto it : g[v.S.F][v.S.S]){
if(ans[l][r][it.F][it.S] > ans[l][r][v.S.F][v.S.S] + 1){
st.erase({ans[l][r][it.F][it.S] , {it.F , it.S}});
ans[l][r][it.F][it.S] = ans[l][r][v.S.F][v.S.S] + 1;
st.insert({ans[l][r][it.F][it.S] , {it.F , it.S}});
}
}
}
}
}
int mx = inf;
for(int i = 1 ; i <= h ; i++)for(int j = 1 ; j <= w ; j++)mx = min(mx , ans[1][n][i][j]);
cout << mx;
}
signed main(){
int t = 1;
Bekabot
while(t--)skibidi_dop_dop_dop_yes_yes();
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
6488 KB |
Output is correct |
| 2 |
Incorrect |
3 ms |
6488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
