oj.uz

Submission #701892

# Submission time Handle Problem Language Result Execution time Memory
701892 2023-02-22T09:43:01 Z Dan4Life Robots (APIO13_robots) C++17
60 / 100
 1500 ms 100360 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+10;
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;
    priority_queue<pair<int,pair<int,int>>> pq; 
    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]);
                    pq.push({-dp[i][j][x][y], mp(x,y)});
                }
            }
            while(!pq.empty()){
                auto cur = pq.top().se; pq.pop();
                int x = cur.fi, y = cur.se;
                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;
                        pq.push({-dp[i][j][nx][ny], mp(nx,ny)});
                    }
                }
            }
        }
    }
    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:63:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   63 |                 if(vis[i][j][x][y]) continue; vis[i][j][x][y]=1;
      |                 ^~
robots.cpp:63:47: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   63 |                 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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 608 KB Output is correct
5 Correct 1 ms 604 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 608 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 608 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 638 ms 62076 KB Output is correct
12 Correct 33 ms 7500 KB Output is correct
13 Correct 420 ms 40580 KB Output is correct
14 Correct 917 ms 62068 KB Output is correct
15 Correct 635 ms 62136 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 608 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 352 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 596 KB Output is correct
11 Correct 638 ms 62076 KB Output is correct
12 Correct 33 ms 7500 KB Output is correct
13 Correct 420 ms 40580 KB Output is correct
14 Correct 917 ms 62068 KB Output is correct
15 Correct 635 ms 62136 KB Output is correct
16 Execution timed out 1557 ms 100360 KB Time limit exceeded
17 Halted 0 ms 0 KB -