oj.uz

Submission #218017

# Submission time Handle Problem Language Result Execution time Memory
218017 2020-03-31T12:27:56 Z SamAnd Robots (APIO13_robots) C++17
60 / 100
 241 ms 75568 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 303, K = 11, INF = 1000000009;
const int xx[4] = {-1, 0, 1, 0};
const int yy[4] = {0, 1, 0, -1};
struct ban
{
    short x, y;
    ban(){}
    ban(int x, int y)
    {
        this->x = x;
        this->y = y;
    }
};

int n, m, k;
char a[N][N];
int sx[K], sy[K];

int c[N][N][4];
ban u[N][N][4];
void dfs(int x, int y, int z)
{
    c[x][y][z] = 1;
    int hx = x + xx[z];
    int hy = y + yy[z];
    int hz = z;
    if (!(hx >= 1 && hx <= n && hy >= 1 && hy <= m) || a[hx][hy] == 'x')
    {
        hx = x;
        hy = y;
    }
    else if (a[hx][hy] == 'C')
        hz = (z + 1) % 4;
    else if (a[hx][hy] == 'A')
        hz = (z - 1 + 4) % 4;
    if (hx == x && hy == y)
    {
        u[x][y][z] = ban(x, y);
        c[x][y][z] = 2;
        return;
    }
    if (!c[hx][hy][hz])
    {
        dfs(hx, hy, hz);
        u[x][y][z] = u[hx][hy][hz];
        c[x][y][z] = 2;
        return;
    }
    if (c[hx][hy][hz] == 2)
    {
        u[x][y][z] = u[hx][hy][hz];
        c[x][y][z] = 2;
        return;
    }
    u[x][y][z] = ban(-1, -1);
    c[x][y][z] = 2;
    return;
}

int dp[K][K][N][N];

bool cc[N][N];
vector<ban> q[N * N * K];

int main()
{
    //freopen("input.txt", "r", stdin);
    scanf("%d%d%d", &k, &m, &n);
    for (int i = 1; i <= n; ++i)
        scanf(" %s", (a[i] + 1));
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            if ('1' <= a[i][j] && a[i][j] <= '9')
            {
                sx[a[i][j] - '0'] = i;
                sy[a[i][j] - '0'] = j;
                a[i][j] = '.';
            }
        }
    }
    for (int i0 = 0; i0 < K; ++i0)
        for (int i1 = 0; i1 < K; ++i1)
            for (int i2 = 0; i2 < N; ++i2)
                for (int i3 = 0; i3 < N; ++i3)
                    dp[i0][i1][i2][i3] = INF;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            for (int k = 0; k < 4; ++k)
            {
                if (!c[i][j][k])
                {
                    dfs(i, j, k);
                }
            }
        }
    }
    for (int d = 1; d <= k; ++d)
    {
        for (int l = 1; l <= k - d + 1; ++l)
        {
            int r = l + d - 1;
            if (l == r)
                dp[l][r][sx[l]][sy[l]] = 0;
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    for (int m = l; m < r; ++m)
                        dp[l][r][i][j] = min(dp[l][r][i][j], dp[l][m][i][j] + dp[m + 1][r][i][j]);
                }
            }
            memset(cc, false, sizeof cc);
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    if (dp[l][r][i][j] != INF)
                        q[dp[l][r][i][j]].push_back(ban(i, j));
                }
            }
            for (int ii = 0; ii < N * N * K; ++ii)
            {
                while (!q[ii].empty())
                {
                    ban t = q[ii].back();
                    q[ii].pop_back();
                    if (cc[t.x][t.y])
                        continue;
                    cc[t.x][t.y] = true;
                    for (int i = 0; i < 4; ++i)
                    {
                        ban h = u[t.x][t.y][i];
                        if (h.x == -1)
                            continue;
                        if (dp[l][r][t.x][t.y] + 1 < dp[l][r][h.x][h.y])
                        {
                            dp[l][r][h.x][h.y] = dp[l][r][t.x][t.y] + 1;
                            q[dp[l][r][h.x][h.y]].push_back(h);
                        }
                    }
                }
            }
        }
    }
    int ans = INF;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            ans = min(ans, dp[1][k][i][j]);
        }
    }
    if (ans == INF)
        printf("-1\n");
    else
        printf("%d\n", ans);
    return 0;
}

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 67576 KB Output is correct
2 Correct 56 ms 67600 KB Output is correct
3 Correct 48 ms 67704 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 49 ms 67704 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 67576 KB Output is correct
2 Correct 56 ms 67600 KB Output is correct
3 Correct 48 ms 67704 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 49 ms 67704 KB Output is correct
6 Correct 51 ms 67576 KB Output is correct
7 Correct 48 ms 67584 KB Output is correct
8 Correct 50 ms 67576 KB Output is correct
9 Correct 49 ms 67572 KB Output is correct
10 Correct 49 ms 67840 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 67576 KB Output is correct
2 Correct 56 ms 67600 KB Output is correct
3 Correct 48 ms 67704 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 49 ms 67704 KB Output is correct
6 Correct 51 ms 67576 KB Output is correct
7 Correct 48 ms 67584 KB Output is correct
8 Correct 50 ms 67576 KB Output is correct
9 Correct 49 ms 67572 KB Output is correct
10 Correct 49 ms 67840 KB Output is correct
11 Correct 180 ms 73208 KB Output is correct
12 Correct 53 ms 70904 KB Output is correct
13 Correct 114 ms 70520 KB Output is correct
14 Correct 241 ms 75568 KB Output is correct
15 Correct 167 ms 71416 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 67576 KB Output is correct
2 Correct 56 ms 67600 KB Output is correct
3 Correct 48 ms 67704 KB Output is correct
4 Correct 50 ms 67704 KB Output is correct
5 Correct 49 ms 67704 KB Output is correct
6 Correct 51 ms 67576 KB Output is correct
7 Correct 48 ms 67584 KB Output is correct
8 Correct 50 ms 67576 KB Output is correct
9 Correct 49 ms 67572 KB Output is correct
10 Correct 49 ms 67840 KB Output is correct
11 Correct 180 ms 73208 KB Output is correct
12 Correct 53 ms 70904 KB Output is correct
13 Correct 114 ms 70520 KB Output is correct
14 Correct 241 ms 75568 KB Output is correct
15 Correct 167 ms 71416 KB Output is correct
16 Execution timed out 17 ms 24064 KB Time limit exceeded (wall clock)
17 Halted 0 ms 0 KB -