| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 645559 |
2022-09-27T10:45:52 Z |
google |
Robots (APIO13_robots) |
C++17 |
|
1500 ms |
28644 KB |
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int N,W,H;
vector<string> G;
vector<vector<int>> h;
vector<vector<vector<int>>> dist,dp;
vector<vector<vector<pair<int,int>>>> ma;
bool legal(int i, int j, int d){
if (d == 0 && (i+1 == H || G[i+1][j] == 'x')) return 0;
if (d == 1 && (j+1 == W || G[i][j+1] == 'x')) return 0;
if (d == 2 && (i == 0 || G[i-1][j] == 'x')) return 0;
if (d == 3 && (j == 0 || G[i][j-1] == 'x')) return 0;
return 1;
}
/*
2 3 4
...
.2.
xxx
.1.
4 10 5
1.........
AA...x4...
..A..x....
2....x....
..C.3.A...
*/
pair<int,int> move(int i, int j, int d){
int oi = i,oj = j,od = d;
while (1){
if (ma[i][j][d].first != -1) {
return ma[oi][oj][od] = ma[i][j][d];
}
if (G[i][j] == 'A') {
d++;
if (d == 4) d = 0;
}
if (G[i][j] == 'C'){
d--;
if (d == -1) d = 3;
}
if (!legal(i,j,d)) return ma[oi][oj][od] = {i,j};
if (d == 0) i++;
if (d == 1) j++;
if (d == 2) i--;
if (d == 3) j--;
}
}
void calc(int i, int j, int l){
queue<pair<pair<int,int>,int>> q;
q.push({{i,j},0});
while (!q.empty()){
auto [t,tt] = q.front();q.pop();
if (dist[l][t.first][t.second] < tt) continue;
dist[l][t.first][t.second] = tt;
for (int ii = 0;ii<4;ii++)q.push({{ma[t.first][t.second][ii].first,ma[t.first][t.second][ii].second},tt+1});
}
}
vector<vector<int>> calc1(vector<vector<int>> &v1, vector<vector<int>> &v2){
vector<vector<int>> ans(H,vector<int>(W));
priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
for (int i = 0;i<H;i++){
for (int j = 0;j<W;j++){
ans[i][j] = min(INF,v1[i][j]+v2[i][j]);
if (ans[i][j] != INF) pq.push({ans[i][j],{i,j}});
}
}
while (!pq.empty()){
auto [tt,t] = pq.top();pq.pop();
if (ans[t.first][t.second] < tt) continue;
ans[t.first][t.second] = tt;
for (int ii = 0;ii<4;ii++)pq.push({tt+1,{ma[t.first][t.second][ii].first,ma[t.first][t.second][ii].second}});
}
return ans;
}
int main(){
cin.tie(0)->sync_with_stdio(0);
cin >> N >> W >> H;
G.resize(H);
ma.resize(H,vector<vector<pair<int,int>>>(W,vector<pair<int,int>>(4,{-1,-1})));
dist.resize(N+1,vector<vector<int>>(H,vector<int>(W,INF)));
for (int i = 0;i<H;i++) cin >> G[i];
for (int i = 0;i<H;i++){
for (int j = 0;j<W;j++){
move(i,j,0);
move(i,j,1);
move(i,j,2);
move(i,j,3);
}
}
for (int l = 1;l<=N;l++){
for (int i = 0;i<H;i++){
for (int j = 0;j<W;j++){
if (G[i][j] == l+'0') calc(i,j,l);
}
}
}
h.resize(N+1,vector<int>(N+1));
int cnt = 1;
for (int i = 1;i<=N;i++){
for (int j = i;j<=N;j++){
h[i][j] = cnt++;
}
}
dp.resize(cnt,vector<vector<int>>(H,vector<int>(W,INF)));
for (auto &a:dp[0]) for (auto &aa:a) aa = 0;
for (int i = 1;i<=N;i++) dp[h[i][i]] = dist[i];
for (int k = 1;k<N;k++){
for (int i = 1;i+k<=N;i++){
vector<vector<int>> t;
t = calc1(dp[h[i][i]],dp[h[i+1][i+k]]);
for (int I = 0;I<H;I++){
for (int J = 0;J<W;J++){
dp[h[i][i+k]][I][J] = min(dp[h[i][i+k]][I][J],t[I][J]);
}
}
if (k == 1) continue;
t = calc1(dp[h[i][i+k-1]],dp[h[i+k][i+k]]);
for (int I = 0;I<H;I++){
for (int J = 0;J<W;J++){
dp[h[i][i+k]][I][J] = min(dp[h[i][i+k]][I][J],t[I][J]);
}
}
}
}
int ans = INF;
for (auto &a:dp[h[1][N]]) for (auto &aa:a) ans = min(ans,aa);
if (ans == INF) ans = -1;
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Execution timed out |
1582 ms |
28644 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
212 KB |
Output is correct |
| 2 |
Correct |
0 ms |
212 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Correct |
1 ms |
292 KB |
Output is correct |
| 5 |
Correct |
0 ms |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
212 KB |
Output is correct |
| 8 |
Correct |
0 ms |
212 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Execution timed out |
1582 ms |
28644 KB |
Time limit exceeded |
| 12 |
Halted |
0 ms |
0 KB |
- |
