oj.uz

Submission #318808

# Submission time Handle Problem Language Result Execution time Memory
318808 2020-11-03T09:19:29 Z anhkhoa0707 Robots (APIO13_robots) C++14
100 / 100
 1036 ms 124696 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " = " << x << endl;
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
const int INF = 250000;
int n, h, w;
char g[500][500];
pair<int, int> end_pos[500][500][4];
int dp[500][500][9][9];
vector<pair<int, int>> q[INF];
bool inside(int x, int y)
{
    return (x >= 0 && y >= 0 && x < h && y < w && g[x][y] != 'x');
}
int main()
{
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> w >> h;
    memset(dp, 0x3f, sizeof(dp));
 
    FOR(i, 0, h) FOR(j, 0, w)
    {
        cin >> g[i][j];
        if (g[i][j] - '0' > 0 && g[i][j] - '0' < 10)
        {
            dp[i][j][g[i][j] - '1'][g[i][j] - '1'] = 0;
        }
    }
    FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x')
    {
        FOR(k, 0, 4)
        {
            pair<int, int> pos = {i, j};
            int d = (k + (g[i][j] == 'A') * 3 + (g[i][j] == 'C')) % 4;
 
            while (true)
            {
                if (d == 0)
                {
                    if (inside(pos.first - 1, pos.second)) pos.first--;
                    else break;
                }
                else if (d == 1)
                {
                    if (inside(pos.first, pos.second + 1)) pos.second++;
                    else break;
                }
                else if (d == 2)
                {
                    if (inside(pos.first + 1, pos.second)) pos.first++;
                    else break;
                }
                else
                {
                    if (inside(pos.first, pos.second - 1)) pos.second--;
                    else break;
                }
 
                if (g[pos.first][pos.second] == 'A') d = (d + 3) % 4;
                if (g[pos.first][pos.second] == 'C') d = (d + 1) % 4;
            }
 
            end_pos[i][j][k] = pos;
        }
    }
    FOR(rng, 0, n)
    {
        FOR(k, 0, n - rng)
        {
            int l = k + rng;
            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x')
            {
                FOR(d, k, l)
                {
                    dp[i][j][k][l] =
                        min(dp[i][j][k][l],
                            dp[i][j][k][d] + dp[i][j][d + 1][l]);
                }
            }
        }
 
        FOR(k, 0, n - rng)
        {
            int l = k + rng;
 
            FOR(i, 0, h) FOR(j, 0, w) if (g[i][j] != 'x')
            {
                if (dp[i][j][k][l] <= INF) q[dp[i][j][k][l]].push_back({i, j});
            }
 
            FOR(i, 0, INF)
            {
                for (pair<int, int> pos : q[i])
                {
                    int x, y;
                    tie(x, y) = pos;
                    if (dp[x][y][k][l] == i)
                    {
                        FOR(d, 0, 4)
                        {
                            int nx, ny;
                            tie(nx, ny) = end_pos[x][y][d];
                            if (dp[nx][ny][k][l] > dp[x][y][k][l] + 1)
                            {
                                q[dp[nx][ny][k][l] = dp[x][y][k][l] + 1].push_back({nx, ny});
                            }
                        }
                    }
                }
                q[i].clear();
            }
        }
    }
    int ans = INT_MAX;
    FOR(i, 0, h) FOR(j, 0, w) ans = min(ans, dp[i][j][0][n - 1]);
    cout << (ans > INF ? -1 : ans);
    return 0;
#ifdef dungctb
    cerr << "Time collapse : " << fixed << setprecision(3) << 1.000*clock()/CLOCKS_PER_SEC;
#endif // dungctb
 
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 85476 KB Output is correct
2 Correct 45 ms 85476 KB Output is correct
3 Correct 45 ms 85476 KB Output is correct
4 Correct 44 ms 85476 KB Output is correct
5 Correct 51 ms 85476 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 85476 KB Output is correct
2 Correct 45 ms 85476 KB Output is correct
3 Correct 45 ms 85476 KB Output is correct
4 Correct 44 ms 85476 KB Output is correct
5 Correct 51 ms 85476 KB Output is correct
6 Correct 45 ms 85476 KB Output is correct
7 Correct 44 ms 85476 KB Output is correct
8 Correct 44 ms 85476 KB Output is correct
9 Correct 44 ms 85476 KB Output is correct
10 Correct 44 ms 85476 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 85476 KB Output is correct
2 Correct 45 ms 85476 KB Output is correct
3 Correct 45 ms 85476 KB Output is correct
4 Correct 44 ms 85476 KB Output is correct
5 Correct 51 ms 85476 KB Output is correct
6 Correct 45 ms 85476 KB Output is correct
7 Correct 44 ms 85476 KB Output is correct
8 Correct 44 ms 85476 KB Output is correct
9 Correct 44 ms 85476 KB Output is correct
10 Correct 44 ms 85476 KB Output is correct
11 Correct 209 ms 92772 KB Output is correct
12 Correct 53 ms 89444 KB Output is correct
13 Correct 158 ms 89828 KB Output is correct
14 Correct 378 ms 97964 KB Output is correct
15 Correct 177 ms 90084 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 85476 KB Output is correct
2 Correct 45 ms 85476 KB Output is correct
3 Correct 45 ms 85476 KB Output is correct
4 Correct 44 ms 85476 KB Output is correct
5 Correct 51 ms 85476 KB Output is correct
6 Correct 45 ms 85476 KB Output is correct
7 Correct 44 ms 85476 KB Output is correct
8 Correct 44 ms 85476 KB Output is correct
9 Correct 44 ms 85476 KB Output is correct
10 Correct 44 ms 85476 KB Output is correct
11 Correct 209 ms 92772 KB Output is correct
12 Correct 53 ms 89444 KB Output is correct
13 Correct 158 ms 89828 KB Output is correct
14 Correct 378 ms 97964 KB Output is correct
15 Correct 177 ms 90084 KB Output is correct
16 Correct 780 ms 93920 KB Output is correct
17 Correct 1036 ms 124696 KB Output is correct
18 Correct 400 ms 96348 KB Output is correct
19 Correct 534 ms 93924 KB Output is correct
20 Correct 777 ms 107132 KB Output is correct