oj.uz

Submission #478046

# Submission time Handle Problem Language Result Execution time Memory
478046 2021-10-05T11:08:32 Z ThaiBaHung Robots (APIO13_robots) C++14
30 / 100
 291 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 (int cs = 0; cs < val[gt].size(); cs++)
        {
            iii cur = val[gt][cs];
            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 (i == 1 && j == 2 && lo == 2) cout << u << " " << hi << " " << dp[i][j][u][hi] << '\n';
                }

            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}});
                }

            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}});
                        }
                    }

            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;
}

Compilation message

robots.cpp: In function 'int main()':
robots.cpp:85:29: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |         for (int cs = 0; cs < val[gt].size(); cs++)
      |                          ~~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 106188 KB Output is correct
2 Correct 45 ms 106176 KB Output is correct
3 Correct 47 ms 106144 KB Output is correct
4 Correct 53 ms 106240 KB Output is correct
5 Correct 51 ms 106308 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 106188 KB Output is correct
2 Correct 45 ms 106176 KB Output is correct
3 Correct 47 ms 106144 KB Output is correct
4 Correct 53 ms 106240 KB Output is correct
5 Correct 51 ms 106308 KB Output is correct
6 Correct 46 ms 106188 KB Output is correct
7 Correct 46 ms 106216 KB Output is correct
8 Correct 49 ms 106220 KB Output is correct
9 Correct 45 ms 106256 KB Output is correct
10 Correct 53 ms 106308 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 106188 KB Output is correct
2 Correct 45 ms 106176 KB Output is correct
3 Correct 47 ms 106144 KB Output is correct
4 Correct 53 ms 106240 KB Output is correct
5 Correct 51 ms 106308 KB Output is correct
6 Correct 46 ms 106188 KB Output is correct
7 Correct 46 ms 106216 KB Output is correct
8 Correct 49 ms 106220 KB Output is correct
9 Correct 45 ms 106256 KB Output is correct
10 Correct 53 ms 106308 KB Output is correct
11 Correct 291 ms 145684 KB Output is correct
12 Correct 55 ms 110284 KB Output is correct
13 Correct 57 ms 110660 KB Output is correct
14 Runtime error 275 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 49 ms 106188 KB Output is correct
2 Correct 45 ms 106176 KB Output is correct
3 Correct 47 ms 106144 KB Output is correct
4 Correct 53 ms 106240 KB Output is correct
5 Correct 51 ms 106308 KB Output is correct
6 Correct 46 ms 106188 KB Output is correct
7 Correct 46 ms 106216 KB Output is correct
8 Correct 49 ms 106220 KB Output is correct
9 Correct 45 ms 106256 KB Output is correct
10 Correct 53 ms 106308 KB Output is correct
11 Correct 291 ms 145684 KB Output is correct
12 Correct 55 ms 110284 KB Output is correct
13 Correct 57 ms 110660 KB Output is correct
14 Runtime error 275 ms 163844 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -