oj.uz

Submission #701894

# Submission time Handle Problem Language Result Execution time Memory
701894 2023-02-22T09:49:33 Z Dan4Life Robots (APIO13_robots) C++17
100 / 100
 440 ms 137984 KB 
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(a) a.begin(),a.end()
using pii = pair<int,int>;
const int mxN = (int)5e2+2;
const int LINF = (int)1e8;
int n, w, h;
string a[mxN];
pii mov[5][mxN][mxN];
int X[] = {-1,0,1,0};
int Y[] = {0,1,0,-1};
bool vis[10][10][mxN][mxN];
int dp[10][10][mxN][mxN];

inline bool isValid(int x, int y){ return (x>=0 and x<h and y>=0 and y<w and a[x][y]!='x'); }

pii mv(int dir, int x,int y){
    while(isValid(x,y)){
        if(a[x][y]=='A') dir=(dir+3)%4;
        else if(a[x][y]=='C') dir=(dir+1)%4;
        if(!isValid(x+X[dir], y+Y[dir])) break;
        x+=X[dir], y+=Y[dir];
    }
    return mp(x,y);
}

int32_t main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> w >> h; int ans = LINF;
    for(int i = 0; i < h; i++) cin >> a[i];
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 0; k <= h; k++)
                for(int l = 0; l <= w; l++)
                    dp[i][j][k][l]=LINF;   
    for(int k = 0; k < 4; k++)
        for(int i = 0; i < h; i++)
            for(int j = 0; j < w; j++)
                mov[k][i][j] = mv(k,i,j);
    for(int i = 0; i < h; i++)
        for(int j = 0; j < w; j++)
            if(a[i][j]>='0' and a[i][j]<='9')
                dp[a[i][j]-'0'][a[i][j]-'0'][i][j]=0;
    vector<pair<int,int>> q[mxN*mxN];
    for(int l = 1; l <= n; l++){
        for(int i=1,j=i+l-1;j<=n;i++,j++){
            for(int x = 0; x < h; x++){
                for(int y = 0; y < w; y++){
                    for(int k = i; k < j; k++)
                        dp[i][j][x][y] = min(dp[i][j][x][y], 
                            dp[i][k][x][y]+dp[k+1][j][x][y]);
                    if(dp[i][j][x][y]<LINF) q[dp[i][j][x][y]].pb({x,y});
                }
            }
            for(int _ = 0; _ < mxN*mxN; _++){
                for(auto [x,y] : q[_]){
                    if(vis[i][j][x][y]) continue; vis[i][j][x][y]=1;
                    for(int k = 0; k < 4; k++){
                        int nx = mov[k][x][y].fi, ny = mov[k][x][y].se;
                        if(dp[i][j][x][y]+1< dp[i][j][nx][ny]){
                            dp[i][j][nx][ny]=dp[i][j][x][y]+1;
                            q[dp[i][j][nx][ny]].pb({nx,ny});
                        }
                    }
                }
                q[_].clear();
            }
        }
    }
    for(int x = 0; x < h; x++)
        for(int y = 0; y < w; y++)
            ans = min(ans, dp[1][n][x][y]);
    cout << (ans==LINF?-1:ans);
}

Compilation message

robots.cpp: In function 'int32_t main()':
robots.cpp:62:21: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   62 |                     if(vis[i][j][x][y]) continue; vis[i][j][x][y]=1;
      |                     ^~
robots.cpp:62:51: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   62 |                     if(vis[i][j][x][y]) continue; vis[i][j][x][y]=1;
      |                                                   ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6228 KB Output is correct
2 Correct 5 ms 6240 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6484 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6228 KB Output is correct
2 Correct 5 ms 6240 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6484 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Correct 5 ms 6356 KB Output is correct
7 Correct 6 ms 6228 KB Output is correct
8 Correct 5 ms 6356 KB Output is correct
9 Correct 6 ms 6244 KB Output is correct
10 Correct 6 ms 6484 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6228 KB Output is correct
2 Correct 5 ms 6240 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6484 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Correct 5 ms 6356 KB Output is correct
7 Correct 6 ms 6228 KB Output is correct
8 Correct 5 ms 6356 KB Output is correct
9 Correct 6 ms 6244 KB Output is correct
10 Correct 6 ms 6484 KB Output is correct
11 Correct 113 ms 69640 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 89 ms 40592 KB Output is correct
14 Correct 174 ms 74864 KB Output is correct
15 Correct 92 ms 63312 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 6228 KB Output is correct
2 Correct 5 ms 6240 KB Output is correct
3 Correct 5 ms 6228 KB Output is correct
4 Correct 6 ms 6484 KB Output is correct
5 Correct 5 ms 6484 KB Output is correct
6 Correct 5 ms 6356 KB Output is correct
7 Correct 6 ms 6228 KB Output is correct
8 Correct 5 ms 6356 KB Output is correct
9 Correct 6 ms 6244 KB Output is correct
10 Correct 6 ms 6484 KB Output is correct
11 Correct 113 ms 69640 KB Output is correct
12 Correct 10 ms 12244 KB Output is correct
13 Correct 89 ms 40592 KB Output is correct
14 Correct 174 ms 74864 KB Output is correct
15 Correct 92 ms 63312 KB Output is correct
16 Correct 440 ms 95552 KB Output is correct
17 Correct 431 ms 137984 KB Output is correct
18 Correct 151 ms 101952 KB Output is correct
19 Correct 309 ms 95400 KB Output is correct
20 Correct 274 ms 120696 KB Output is correct