oj.uz

Submission #478047

# Submission time Handle Problem Language Result Execution time Memory
478047 2021-10-05T11:15:37 Z ThaiBaHung Robots (APIO13_robots) C++14
30 / 100
 284 ms 144780 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 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][lo][hi] > gt + 1)
                {
                    dp[nxt_i][nxt_j][lo][hi] = gt + 1;
                    val[gt + 1].push_back({{nxt_i, nxt_j}, {lo, hi}});
                }
            }
        }

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 106156 KB Output is correct
2 Correct 47 ms 106140 KB Output is correct
3 Correct 43 ms 106180 KB Output is correct
4 Correct 49 ms 106304 KB Output is correct
5 Correct 48 ms 106192 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 106156 KB Output is correct
2 Correct 47 ms 106140 KB Output is correct
3 Correct 43 ms 106180 KB Output is correct
4 Correct 49 ms 106304 KB Output is correct
5 Correct 48 ms 106192 KB Output is correct
6 Correct 50 ms 106172 KB Output is correct
7 Correct 49 ms 106216 KB Output is correct
8 Correct 50 ms 106244 KB Output is correct
9 Correct 44 ms 106180 KB Output is correct
10 Correct 48 ms 106204 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 106156 KB Output is correct
2 Correct 47 ms 106140 KB Output is correct
3 Correct 43 ms 106180 KB Output is correct
4 Correct 49 ms 106304 KB Output is correct
5 Correct 48 ms 106192 KB Output is correct
6 Correct 50 ms 106172 KB Output is correct
7 Correct 49 ms 106216 KB Output is correct
8 Correct 50 ms 106244 KB Output is correct
9 Correct 44 ms 106180 KB Output is correct
10 Correct 48 ms 106204 KB Output is correct
11 Incorrect 284 ms 144780 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 106156 KB Output is correct
2 Correct 47 ms 106140 KB Output is correct
3 Correct 43 ms 106180 KB Output is correct
4 Correct 49 ms 106304 KB Output is correct
5 Correct 48 ms 106192 KB Output is correct
6 Correct 50 ms 106172 KB Output is correct
7 Correct 49 ms 106216 KB Output is correct
8 Correct 50 ms 106244 KB Output is correct
9 Correct 44 ms 106180 KB Output is correct
10 Correct 48 ms 106204 KB Output is correct
11 Incorrect 284 ms 144780 KB Output isn't correct
12 Halted 0 ms 0 KB -