oj.uz

Submission #478069

# Submission time Handle Problem Language Result Execution time Memory
478069 2021-10-05T13:16:29 Z ThaiBaHung Robots (APIO13_robots) C++14
30 / 100
 471 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; 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 47 ms 106224 KB Output is correct
2 Correct 46 ms 106172 KB Output is correct
3 Correct 44 ms 106180 KB Output is correct
4 Correct 43 ms 106212 KB Output is correct
5 Correct 43 ms 106200 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 106224 KB Output is correct
2 Correct 46 ms 106172 KB Output is correct
3 Correct 44 ms 106180 KB Output is correct
4 Correct 43 ms 106212 KB Output is correct
5 Correct 43 ms 106200 KB Output is correct
6 Correct 44 ms 106272 KB Output is correct
7 Correct 48 ms 106264 KB Output is correct
8 Correct 48 ms 106276 KB Output is correct
9 Correct 44 ms 106180 KB Output is correct
10 Correct 46 ms 106184 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 106224 KB Output is correct
2 Correct 46 ms 106172 KB Output is correct
3 Correct 44 ms 106180 KB Output is correct
4 Correct 43 ms 106212 KB Output is correct
5 Correct 43 ms 106200 KB Output is correct
6 Correct 44 ms 106272 KB Output is correct
7 Correct 48 ms 106264 KB Output is correct
8 Correct 48 ms 106276 KB Output is correct
9 Correct 44 ms 106180 KB Output is correct
10 Correct 46 ms 106184 KB Output is correct
11 Correct 471 ms 140216 KB Output is correct
12 Correct 52 ms 110276 KB Output is correct
13 Correct 56 ms 110800 KB Output is correct
14 Runtime error 371 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 47 ms 106224 KB Output is correct
2 Correct 46 ms 106172 KB Output is correct
3 Correct 44 ms 106180 KB Output is correct
4 Correct 43 ms 106212 KB Output is correct
5 Correct 43 ms 106200 KB Output is correct
6 Correct 44 ms 106272 KB Output is correct
7 Correct 48 ms 106264 KB Output is correct
8 Correct 48 ms 106276 KB Output is correct
9 Correct 44 ms 106180 KB Output is correct
10 Correct 46 ms 106184 KB Output is correct
11 Correct 471 ms 140216 KB Output is correct
12 Correct 52 ms 110276 KB Output is correct
13 Correct 56 ms 110800 KB Output is correct
14 Runtime error 371 ms 163844 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -