oj.uz

Submission #218009

# Submission time Handle Problem Language Result Execution time Memory
218009 2020-03-31T12:07:58 Z SamAnd Robots (APIO13_robots) C++17
60 / 100
 527 ms 163844 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 502, K = 11, INF = 1000000009;
const int xx[4] = {-1, 0, 1, 0};
const int yy[4] = {0, 1, 0, -1};
struct ban
{
    int 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;

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 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);
                }
            }
        }
    }
    dp = new int***[K];
    for (int i = 0; i < K; ++i)
    {
        dp[i] = new int**[K - i];
        for (int j = 0; j < K - i; ++j)
        {
            dp[i][j] = new int*[N];
            for (int x = 0; x < N; ++x)
            {
                dp[i][j][x] = new int[N];
                for (int y = 0; y < N; ++y)
                    dp[i][j][x][y] = INF;
            }
        }
    }
    for (int d = 1; d <= k; ++d)
    {
        for (int l = 1; l <= k - d + 1; ++l)
        {
            if (d == 1)
                dp[l][d][sx[l]][sy[l]] = 0;
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    for (int m = 1; m < d; ++m)
                        dp[l][d][i][j] = min(dp[l][d][i][j], dp[l][m][i][j] + dp[l + m][d - m][i][j]);
                }
            }
            memset(cc, false, sizeof cc);
            for (int i = 1; i <= n; ++i)
            {
                for (int j = 1; j <= m; ++j)
                {
                    if (dp[l][d][i][j] != INF)
                        q[dp[l][d][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][d][t.x][t.y] + 1 < dp[l][d][h.x][h.y])
                        {
                            dp[l][d][h.x][h.y] = dp[l][d][t.x][t.y] + 1;
                            q[dp[l][d][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 99 ms 131324 KB Output is correct
2 Correct 97 ms 131320 KB Output is correct
3 Correct 96 ms 131320 KB Output is correct
4 Correct 104 ms 131320 KB Output is correct
5 Correct 97 ms 131448 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 131324 KB Output is correct
2 Correct 97 ms 131320 KB Output is correct
3 Correct 96 ms 131320 KB Output is correct
4 Correct 104 ms 131320 KB Output is correct
5 Correct 97 ms 131448 KB Output is correct
6 Correct 98 ms 131372 KB Output is correct
7 Correct 97 ms 131320 KB Output is correct
8 Correct 96 ms 131320 KB Output is correct
9 Correct 97 ms 131320 KB Output is correct
10 Correct 95 ms 131320 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 131324 KB Output is correct
2 Correct 97 ms 131320 KB Output is correct
3 Correct 96 ms 131320 KB Output is correct
4 Correct 104 ms 131320 KB Output is correct
5 Correct 97 ms 131448 KB Output is correct
6 Correct 98 ms 131372 KB Output is correct
7 Correct 97 ms 131320 KB Output is correct
8 Correct 96 ms 131320 KB Output is correct
9 Correct 97 ms 131320 KB Output is correct
10 Correct 95 ms 131320 KB Output is correct
11 Correct 408 ms 141688 KB Output is correct
12 Correct 96 ms 138232 KB Output is correct
13 Correct 279 ms 138104 KB Output is correct
14 Correct 483 ms 146808 KB Output is correct
15 Correct 391 ms 139000 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 131324 KB Output is correct
2 Correct 97 ms 131320 KB Output is correct
3 Correct 96 ms 131320 KB Output is correct
4 Correct 104 ms 131320 KB Output is correct
5 Correct 97 ms 131448 KB Output is correct
6 Correct 98 ms 131372 KB Output is correct
7 Correct 97 ms 131320 KB Output is correct
8 Correct 96 ms 131320 KB Output is correct
9 Correct 97 ms 131320 KB Output is correct
10 Correct 95 ms 131320 KB Output is correct
11 Correct 408 ms 141688 KB Output is correct
12 Correct 96 ms 138232 KB Output is correct
13 Correct 279 ms 138104 KB Output is correct
14 Correct 483 ms 146808 KB Output is correct
15 Correct 391 ms 139000 KB Output is correct
16 Correct 474 ms 143352 KB Output is correct
17 Runtime error 527 ms 163844 KB Execution killed with signal 9 (could be triggered by violating memory limits)
18 Halted 0 ms 0 KB -