oj.uz

Submission #287779

# Submission time Handle Problem Language Result Execution time Memory
287779 2020-08-31T23:56:17 Z Namnamseo Robots (APIO13_robots) C++17
30 / 100
 513 ms 32836 KB 
#include <cstdio>
#include <cstring>
#include <utility>
#include <vector>
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=1;i<=n;++i)
#define x first
#define y second
#define eb emplace_back
using namespace std;
using pp=pair<int,int>;
int n, m, k;
char q[510][510];
pp e[510][510][4];
pp il[10];

using t4=tuple<int,int,int,int>;

int dp[510][510][50];

vector<pp> rm[510][510];

const int dx[5] = {0, 1, 0, -1}, *dy = dx+1;
pp E(int x, int y, int d) {
    pp &ret = e[x][y][d];
    if (ret.x) return ret;
    int nx=x+dx[d], ny=y+dy[d];
    if (1<=nx && nx<=n && 1<=ny && ny<=m && q[nx][ny]!='x') {
        switch(q[nx][ny]) {
            case 'A': ret = E(nx, ny, (d+3)%4); break;
            case 'C': ret = E(nx, ny, (d+1)%4); break;
            default: ret = E(nx, ny, d); break;
        }
        return ret;
    } else return ret={x, y};
}

int C[10][10];
int f(int x, int y, int l, int r)
{
    if (l == r && q[x][y] == 48+l) return 0;

    int p = C[l][r];
    int &ret = dp[x][y][p];
    if (ret) return ret;
    ret = 1e9;
    for(int i=l; i<r; ++i)
        ret = min(ret, f(x, y, l, i) + f(x, y, i+1, r));

    for(pp &t:rm[x][y])
        ret = min(ret, 1+f(t.x, t.y, l, r));

    return ret;
}

int main()
{
    scanf("%d%d%d",&k,&m,&n);
    rrep(i, n) {
        scanf("%s", q[i]+1);
        rrep(j, m) if ((q[i][j]&48)==48) il[q[i][j]-48]={i,j};
    }

    rrep(i, n) rrep(j, m) rep(d, 4) {
        pp x = E(i, j, d);
        if (x != pp{i, j}) rm[x.x][x.y].eb(i, j);
    }

    { static int p = 0; rrep(i, k) rrep(j, i) C[j][i] = ++p; }

    int ans = 2e9;
    rrep(i, n) rrep(j, m) if (q[i][j] != 'x') {
        ans = min(ans, f(i, j, 1, k));
    }

    if (ans > n*m*k*2) ans = -1;
    printf("%d\n", ans);

    return 0;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     scanf("%d%d%d",&k,&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |         scanf("%s", q[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 4 ms 6400 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 5 ms 6400 KB Output is correct
7 Correct 4 ms 6400 KB Output is correct
8 Correct 4 ms 6400 KB Output is correct
9 Correct 5 ms 6400 KB Output is correct
10 Correct 5 ms 6528 KB Output is correct
11 Incorrect 513 ms 32836 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6400 KB Output is correct
2 Correct 4 ms 6400 KB Output is correct
3 Correct 4 ms 6400 KB Output is correct
4 Correct 4 ms 6528 KB Output is correct
5 Correct 5 ms 6528 KB Output is correct
6 Correct 5 ms 6400 KB Output is correct
7 Correct 4 ms 6400 KB Output is correct
8 Correct 4 ms 6400 KB Output is correct
9 Correct 5 ms 6400 KB Output is correct
10 Correct 5 ms 6528 KB Output is correct
11 Incorrect 513 ms 32836 KB Output isn't correct
12 Halted 0 ms 0 KB -