oj.uz

Submission #478071

# Submission time Handle Problem Language Result Execution time Memory
478071 2021-10-05T13:18:37 Z ThaiBaHung Robots (APIO13_robots) C++14
30 / 100
 507 ms 163844 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int N = 503;
int m, n, k;
const int X[] = {0, 1, 0, -1};
const int Y[] = {1, 0, -1, 0};
typedef pair < int, int > ii;
ii nxt[N][N][4];
bool vs[N][N][4];
int dp[N][N][10][10];
char a[N][N];
typedef pair < ii, ii > iii;
vector < iii > val[N * N];

bool thoaman(int i, int j)
{
    if (i < 1 || j < 1 || i > m || j > n) return false;
    if (a[i][j] == 'x') return false;
    return true;
}

ii tim_pos(int i, int j, int dir)
{
    //cout << i << " " << j << " " << dir << '\n';
    if (vs[i][j][dir]) return nxt[i][j][dir];

    vs[i][j][dir] = true;
    int nxt_i = i + X[dir], nxt_j = j + Y[dir];
    if (!thoaman(nxt_i, nxt_j))
        nxt[i][j][dir] = {i, j};

    if (a[nxt_i][nxt_j] == '.')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, dir);

    if ('1' <= a[nxt_i][nxt_j] && a[nxt_i][nxt_j] <= '9')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, dir);

    if (a[nxt_i][nxt_j] == 'A')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, (dir + 3) % 4);

    if (a[nxt_i][nxt_j] == 'C')
        nxt[i][j][dir] = tim_pos(nxt_i, nxt_j, (dir + 1) % 4);

    return nxt[i][j][dir];
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("t.inp","r",stdin); freopen("t.out","w",stdout);

    cin >> k >> n >> m;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
        {
            cin >> a[i][j];
            for (int t = 0; t < 4; t++)
                nxt[i][j][t] = {-1, -1};
        }

    memset(vs, false, sizeof vs);
    memset(dp, 0x3f, sizeof dp);

    tim_pos(5, 5, 0);

    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            if (a[i][j] != 'x')
            {
                for (int t = 0; t < 4; t++)
                    nxt[i][j][t] = tim_pos(i, j, t);

                int cs = 0;

                if ('1' <= a[i][j] && a[i][j] <= '9')
                dp[i][j][a[i][j] - '1' + 1][a[i][j] - '1' + 1] = 0,
                cs = a[i][j] - '1' + 1,
                val[0].push_back({{i, j}, {cs, cs}});
            }

    int res = 1e9 + 3;
    for (int gt = 0; gt <= m * n / 2; gt++)
        for (iii cur : val[gt])
        {
            int i = cur.fi.fi, j = cur.fi.se;
            int lo = cur.se.fi, hi = cur.se.se;
            if (dp[i][j][lo][hi] != gt) continue;

            if (lo == 1 && hi == k)
            {
                res = min(res, gt);
                cout << res;
                return 0;
            }

            for (int u = lo - 1; u >= 1; u--)
                if (dp[i][j][u][lo - 1] < 1e9 && dp[i][j][u][hi] > dp[i][j][u][lo - 1] + dp[i][j][lo][hi])
                {
                    dp[i][j][u][hi] = dp[i][j][u][lo - 1] + dp[i][j][lo][hi];
                    val[dp[i][j][u][hi]].push_back({{i, j}, {u, hi}});
                    if (u == 1 && hi == k) res = min(res, dp[i][j][u][hi]);
                }

            for (int v = hi + 1; v <= k; v++)
                if (dp[i][j][hi + 1][v] < 1e9 && dp[i][j][lo][v] > dp[i][j][lo][hi] + dp[i][j][hi + 1][v])
                {
                    dp[i][j][lo][v] = dp[i][j][hi + 1][v] + dp[i][j][lo][hi];
                    val[dp[i][j][lo][v]].push_back({{i, j}, {lo, v}});
                    if (lo == 1 && v == k) res = min(res, dp[i][j][lo][v]);
                }

            for (int u = lo - 1; u >= 1; u--)
                for (int v = hi + 1; v <= k; v++)
                    if (dp[i][j][u][lo - 1] < 1e9 && dp[i][j][hi + 1][v] < 1e9)
                    {
                        if (dp[i][j][u][v] > dp[i][j][u][lo - 1] + gt + dp[i][j][hi + 1][v])
                        {
                            dp[i][j][u][v] = dp[i][j][u][lo - 1] + gt + dp[i][j][hi + 1][v];
                            val[dp[i][j][u][v]].push_back({{i, j}, {u, v}});
                            if (u == 1 && v == k) res = min(res, dp[i][j][u][v]);
                        }
                    }

            for (int u = 1; u <= k; u++)
            for (int v = u; v <= k; v++)
            if (dp[i][j][u][v] < 1e9)
            for (int t = 0; t < 4; t++)
            {
                int nxt_i = nxt[i][j][t].fi, nxt_j = nxt[i][j][t].se;

                if (nxt_i == -1) continue;

                if (dp[nxt_i][nxt_j][u][v] > dp[i][j][u][v] + 1)
                {
                    dp[nxt_i][nxt_j][u][v] = dp[i][j][u][v] + 1;
                    val[dp[i][j][u][v] + 1].push_back({{nxt_i, nxt_j}, {u, v}});
                }
            }
        }

    if (res > 1e9) res = -1;
    cout << res;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106180 KB Output is correct
2 Correct 47 ms 106180 KB Output is correct
3 Correct 45 ms 106224 KB Output is correct
4 Correct 43 ms 106284 KB Output is correct
5 Correct 45 ms 106240 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106180 KB Output is correct
2 Correct 47 ms 106180 KB Output is correct
3 Correct 45 ms 106224 KB Output is correct
4 Correct 43 ms 106284 KB Output is correct
5 Correct 45 ms 106240 KB Output is correct
6 Correct 42 ms 106236 KB Output is correct
7 Correct 46 ms 106228 KB Output is correct
8 Correct 43 ms 106260 KB Output is correct
9 Correct 46 ms 106188 KB Output is correct
10 Correct 43 ms 106308 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106180 KB Output is correct
2 Correct 47 ms 106180 KB Output is correct
3 Correct 45 ms 106224 KB Output is correct
4 Correct 43 ms 106284 KB Output is correct
5 Correct 45 ms 106240 KB Output is correct
6 Correct 42 ms 106236 KB Output is correct
7 Correct 46 ms 106228 KB Output is correct
8 Correct 43 ms 106260 KB Output is correct
9 Correct 46 ms 106188 KB Output is correct
10 Correct 43 ms 106308 KB Output is correct
11 Correct 507 ms 140220 KB Output is correct
12 Correct 50 ms 110248 KB Output is correct
13 Correct 52 ms 110744 KB Output is correct
14 Runtime error 360 ms 163844 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 106180 KB Output is correct
2 Correct 47 ms 106180 KB Output is correct
3 Correct 45 ms 106224 KB Output is correct
4 Correct 43 ms 106284 KB Output is correct
5 Correct 45 ms 106240 KB Output is correct
6 Correct 42 ms 106236 KB Output is correct
7 Correct 46 ms 106228 KB Output is correct
8 Correct 43 ms 106260 KB Output is correct
9 Correct 46 ms 106188 KB Output is correct
10 Correct 43 ms 106308 KB Output is correct
11 Correct 507 ms 140220 KB Output is correct
12 Correct 50 ms 110248 KB Output is correct
13 Correct 52 ms 110744 KB Output is correct
14 Runtime error 360 ms 163844 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -