| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 258559 |
2020-08-06T06:28:26 Z |
pure_mem |
Robots (APIO13_robots) |
C++14 |
|
364 ms |
163840 KB |
#include <bits/stdc++.h>
#define ll long long
#define X first
#define Y second
#define MP make_pair
using namespace std;
const int inf = 50000 + 1, N = 501;
int n, len, w, h, a[N][N], dp[10][10][N][N];
pair<int, int> end_pos[5][N][N];
queue< pair<int, int> > q[inf];
queue< pair< int, pair< int, int > > > temp;
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
memset(dp, 0x3f, sizeof(dp));
cin >> n >> w >> h;
for(int i = 1;i <= h;i++){
for(int j = 1;j <= w;j++){
char x;
cin >> x;
if(x >= '0' && x <= '9'){
a[i][j] = x - '0';
dp[x - '0'][x - '0'][i][j] = 0;
// q.push(MP(MP(i, j), MP(a[i][j], a[i][j])));
}
else if(x == 'x'){
a[i][j] = 13;
}
else if(x == 'A'){
a[i][j] = 11;
}
else if(x == 'C'){
a[i][j] = 12;
}
//cerr << a[i][j] << " ";
}
//cerr << "\n";
}
if(n == 1)
return cout << 0, 0;
for(int x = 1;x <= h;x++){
for(int y = 1;y <= w;y++){
if(a[x][y] == 13 || (x != 1 && x != h && y != 1 && y != w && a[x + 1][y] != 13 && a[x - 1][y] != 13 && a[x][y + 1] != 13 && a[x][y - 1] != 13))
continue;
for(int bdr = 1;bdr <= 4;bdr++){
pair<int, int> pos = MP(x, y);
int dr = bdr;
if(a[pos.X][pos.Y] == 12)
dr = (dr + 2) % 4 + 1;
else if(a[pos.X][pos.Y] == 11)
dr = dr % 4 + 1;
while(true){
if(dr == 1){
if(pos.X - 1 >= 1 && pos.X - 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X - 1][pos.Y] != 13)
pos.X -= 1;
else
break;
}
else if(dr == 2){
if(pos.X >= 1 && pos.X <= h && pos.Y - 1 >= 1 && pos.Y - 1 <= w && a[pos.X][pos.Y - 1] != 13)
pos.Y -= 1;
else
break;
}
else if(dr == 3){
if(pos.X + 1 >= 1 && pos.X + 1 <= h && pos.Y >= 1 && pos.Y <= w && a[pos.X + 1][pos.Y] != 13)
pos.X += 1;
else
break;
}
else{
if(pos.X >= 1 && pos.X <= h && pos.Y + 1 >= 1 && pos.Y + 1 <= w && a[pos.X][pos.Y + 1] != 13)
pos.Y += 1;
else
break;
}
if(end_pos[dr][pos.X][pos.Y] != MP(0, 0)){
pos = end_pos[dr][pos.X][pos.Y];
break;
}
else{
temp.push(MP(dr, pos));
}
if(a[pos.X][pos.Y] == 12)
dr = (dr + 2) % 4 + 1;
else if(a[pos.X][pos.Y] == 11)
dr = dr % 4 + 1;
}
end_pos[bdr][x][y] = pos;
while(!temp.empty()){
end_pos[temp.front().X][temp.front().Y.X][temp.front().Y.Y] = pos;
temp.pop();
}
}
}
}
int ans = inf;
for(len = 1;len < n;len++){
for(int A = 1;A + len - 1 <= n;A++){
int B = A + len - 1;
for(int x = 1;x <= h;x++){
for(int y = 1;y <= w;y++){
if(a[x][y] != 13 && dp[A][B][x][y] < inf)
q[dp[A][B][x][y]].push(MP(x, y));
}
}
for(int it = 0;it < inf;it++){
while(!q[it].empty()){
pair<int, int> pos = q[it].front();
q[it].pop();
for(int dr = 1;dr <= 4;dr++){
if(dp[A][B][end_pos[dr][pos.X][pos.Y].X][end_pos[dr][pos.X][pos.Y].Y] > dp[A][B][pos.X][pos.Y] + 1){
dp[A][B][end_pos[dr][pos.X][pos.Y].X][end_pos[dr][pos.X][pos.Y].Y] = dp[A][B][pos.X][pos.Y] + 1;
q[it + 1].push(end_pos[dr][pos.X][pos.Y]);
}
}
}
}
}
for(int A = 1;A + len <= n;A++){
for(int C = A;C < A + len;C++){
for(int x = 1;x <= h;x++){
for(int y = 1;y <= w;y++){
if(a[x][y] != 13){
dp[A][A + len][x][y] = min(dp[A][A + len][x][y], dp[A][C][x][y] + dp[C + 1][A + len][x][y]);
if(A == 1 && A + len == n)
ans = min(ans, dp[A][A + len][x][y]);
}
}
}
}
}
}
if(ans >= inf)
ans = -1;
cout << ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 2 |
Correct |
91 ms |
132220 KB |
Output is correct |
| 3 |
Correct |
74 ms |
132216 KB |
Output is correct |
| 4 |
Correct |
76 ms |
132472 KB |
Output is correct |
| 5 |
Correct |
76 ms |
132472 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 2 |
Correct |
91 ms |
132220 KB |
Output is correct |
| 3 |
Correct |
74 ms |
132216 KB |
Output is correct |
| 4 |
Correct |
76 ms |
132472 KB |
Output is correct |
| 5 |
Correct |
76 ms |
132472 KB |
Output is correct |
| 6 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 7 |
Correct |
74 ms |
132356 KB |
Output is correct |
| 8 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 9 |
Correct |
74 ms |
132344 KB |
Output is correct |
| 10 |
Correct |
74 ms |
132480 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 2 |
Correct |
91 ms |
132220 KB |
Output is correct |
| 3 |
Correct |
74 ms |
132216 KB |
Output is correct |
| 4 |
Correct |
76 ms |
132472 KB |
Output is correct |
| 5 |
Correct |
76 ms |
132472 KB |
Output is correct |
| 6 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 7 |
Correct |
74 ms |
132356 KB |
Output is correct |
| 8 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 9 |
Correct |
74 ms |
132344 KB |
Output is correct |
| 10 |
Correct |
74 ms |
132480 KB |
Output is correct |
| 11 |
Correct |
148 ms |
137848 KB |
Output is correct |
| 12 |
Correct |
75 ms |
132856 KB |
Output is correct |
| 13 |
Correct |
98 ms |
137592 KB |
Output is correct |
| 14 |
Runtime error |
364 ms |
163840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 2 |
Correct |
91 ms |
132220 KB |
Output is correct |
| 3 |
Correct |
74 ms |
132216 KB |
Output is correct |
| 4 |
Correct |
76 ms |
132472 KB |
Output is correct |
| 5 |
Correct |
76 ms |
132472 KB |
Output is correct |
| 6 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 7 |
Correct |
74 ms |
132356 KB |
Output is correct |
| 8 |
Correct |
75 ms |
132344 KB |
Output is correct |
| 9 |
Correct |
74 ms |
132344 KB |
Output is correct |
| 10 |
Correct |
74 ms |
132480 KB |
Output is correct |
| 11 |
Correct |
148 ms |
137848 KB |
Output is correct |
| 12 |
Correct |
75 ms |
132856 KB |
Output is correct |
| 13 |
Correct |
98 ms |
137592 KB |
Output is correct |
| 14 |
Runtime error |
364 ms |
163840 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 15 |
Halted |
0 ms |
0 KB |
- |
