oj.uz

Submission #580889

# Submission time Handle Problem Language Result Execution time Memory
580889 2022-06-22T05:21:55 Z 반딧불(#8360) Robots (APIO13_robots) C++17
60 / 100
 1500 ms 59396 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int xx[]={0, -1, 0, 1}, yy[]={1, 0, -1, 0};

int n, m, k;
char board[502][502];
int sx[10], sy[10];

void input();
void operate();
void output();

int main(){
    input();
    operate();
    output();
}

void input(){
    scanf("%d %d %d", &k, &m, &n);
    for(int i=0; i<=n+1; i++) for(int j=0; j<=m+1; j++) board[i][j] = 'x';
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        scanf(" %c", &board[i][j]);
        if(isdigit(board[i][j])){
            int tmp = board[i][j] - '0';
            sx[tmp] = i, sy[tmp] = j;
            board[i][j] = '.';
        }
    }
}

int endpointX[502][502][4];
int endpointY[502][502][4];

void calculateEndpoints(){
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) for(int d=0; d<4; d++) endpointX[i][j][d] = -1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(board[i][j]=='x') continue;
            for(int d=0; d<4; d++){
                if(board[i+xx[d]][j+yy[d]]!='x') continue;
                int x=i, y=j, td=d;
                while(board[x][y]!='x'){
                    if(board[x][y]=='A') td=(td+3)%4;
                    if(board[x][y]=='C') td=(td+1)%4;
                    endpointX[x][y][td] = i;
                    endpointY[x][y][td] = j;
                    x-=xx[td], y-=yy[td];
                }
            }
        }
    }
}

int DP[10][10][502][502];

void init(){
    for(int l=1; l<=k; l++) for(int r=l; r<=k; r++) for(int i=1; i<=n; i++) for(int j=1; j<=m; j++){
        DP[l][r][i][j] = 1e9;
    }
    for(int i=1; i<=k; i++){
        DP[i][i][sx[i]][sy[i]] = 0;
    }
}

struct dat{
    int x, y, d;
    dat(){}
    dat(int x, int y, int d): x(x), y(y), d(d){}
    bool operator<(const dat &r)const{
        return d>r.d;
    }
};
bool visited[502][502];

void calculateDP(int l, int r){
    memset(visited, 0, sizeof(visited));
    priority_queue<dat> pq;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            pq.push(dat(i, j, DP[l][r][i][j]));
        }
    }
    while(!pq.empty()){
        dat tmp = pq.top();
        pq.pop();
        int x = tmp.x, y = tmp.y, d = tmp.d;
//        printf("%d %d %d\n", x, y, d);
        if(d>=1e9 || visited[x][y]) continue;
        DP[l][r][x][y] = d;
        visited[x][y] = 1;
        for(int c=0; c<4; c++){
            if(endpointX[x][y][c] == -1) continue;
            if(visited[endpointX[x][y][c]][endpointY[x][y][c]]) continue;
            pq.push(dat(endpointX[x][y][c], endpointY[x][y][c], d+1));
        }
    }
}

void operate(){
    calculateEndpoints();
    init();
    for(int d=0; d<k; d++){
        for(int i=1; i+d<=k; i++){
            int j = i+d;
            for(int mid=i; mid<j; mid++){
                for(int x=1; x<=n; x++){
                    for(int y=1; y<=m; y++){
                        DP[i][j][x][y] = min(DP[i][j][x][y], DP[i][mid][x][y] + DP[mid+1][j][x][y]);
                    }
                }
            }
            calculateDP(i, j);
        }
    }

    #ifdef TEST
    for(int i=1; i<=k; i++) for(int j=i; j<=k; j++){
        printf("Matrix %d %d:\n", i, j);
        for(int x=1; x<=n; x++){
            for(int y=1; y<=m; y++){
                printf("%3d ", DP[i][j][x][y]>100?100:DP[i][j][x][y]);
            }
            puts("");
        }
    }
    #endif
}

void output(){
    int ans = INT_MAX;
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ans = min(ans, DP[1][k][i][j]);
    if(ans >= 1e9) printf("-1");
    else printf("%d", ans);
}

Compilation message

robots.cpp: In function 'void input()':
robots.cpp:24:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |     scanf("%d %d %d", &k, &m, &n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
robots.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %c", &board[i][j]);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 578 ms 34440 KB Output is correct
12 Correct 20 ms 7500 KB Output is correct
13 Correct 323 ms 24776 KB Output is correct
14 Correct 754 ms 34584 KB Output is correct
15 Correct 571 ms 34496 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 596 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 578 ms 34440 KB Output is correct
12 Correct 20 ms 7500 KB Output is correct
13 Correct 323 ms 24776 KB Output is correct
14 Correct 754 ms 34584 KB Output is correct
15 Correct 571 ms 34496 KB Output is correct
16 Correct 1485 ms 59396 KB Output is correct
17 Execution timed out 1576 ms 59124 KB Time limit exceeded
18 Halted 0 ms 0 KB -