oj.uz

Submission #940464

# Submission time Handle Problem Language Result Execution time Memory
940464 2024-03-07T09:41:28 Z Ice_man Robots (APIO13_robots) C++14
100 / 100
 1135 ms 102576 KB 
#include <iostream>
#include <chrono>
#include <vector>
#include <algorithm>
#include <set>
#include <cstring>

#define max 500
#define maxn 505
#define sm 9
#define maxlog 20
#define INF 1000000010
#define mod 998244353
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
#pragma GCC target("avx2")

using namespace std;

char c[maxn][maxn];
int dp[maxn][maxn][sm][sm];
int state[maxn][maxn][4];
pair<int, int> stops[maxn][maxn][4];

int n, h, w;

void read()
{

    cin >> n >> w >> h;

    h += 2;
    w += 2;

    for (int i = 0; i < w; ++i)
        c[0][i] = c[h - 1][i] = 'x';

    for (int i = 0; i < h; ++i)
        c[i][0] = c[i][w - 1] = 'x';

    for (int i = 1; i < h - 1; ++i)
        for (int j = 1; j < w - 1; ++j)
            cin >> c[i][j];

    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            for (int k = 0; k < n; ++k)
                for (int l = 0; l < n; ++l)
                    dp[i][j][k][l] = INF;
}

int dirx[] = {0, 1, 0, -1};
int diry[] = {1, 0, -1, 0};


pair<int, int> dfs(int i, int j, int k)
{
    if (state[i][j][k] == 2)
        return stops[i][j][k];

    if (state[i][j][k] == 1)
        return stops[i][j][k] = {i, j};

    state[i][j][k] = 1;
    int nk = k;
    if (c[i][j] == 'A')
        nk = (k + 3) % 4;

    if (c[i][j] == 'C')
        nk = (k + 1) % 4;

    int ni = i + dirx[nk], nj = j + diry[nk];

    if (c[ni][nj] == 'x')
    {
        state[i][j][k] = 2;
        return stops[i][j][k] = {i, j};
    }
    else
    {
        stops[i][j][k] = dfs(ni, nj, nk);
        if (state[ni][nj][nk] == 1)
            stops[i][j][k] = {i, j};
        else
            state[i][j][k] = 2;
        return stops[i][j][k];
    }
}


void solve()
{
    for (int len = 0; len < n; ++len)
    {
        for (int l = 0; l + len < n; ++l)
        {
            const int r = l + len;

            vector<vector<pair<int, int>>> v(maxn * maxn + 5);

            if (len == 0)
            {
                for (int i = 0; i < h; ++i)
                    for (int j = 0; j < w; ++j)
                        if (c[i][j] - '1' == l)
                        {
                            dp[i][j][l][r] = 0;
                            v[0].push_back({i, j});
                        }
            }
            else
            {
                for (int i = 0; i < h; ++i)
                    for (int j = 0; j < w; ++j)
                    {
                        int minn = INF;
                        for (int k = l; k < r; ++k)
                            minn = min(minn, dp[i][j][l][k] + dp[i][j][k + 1][r]);

                        dp[i][j][l][r] = minn;
                        if (minn < maxn * maxn)
                            v[minn].push_back({i, j});
                    }
            }

            for (int d = 0; d < maxn * maxn; ++d)
                for (pair <int, int> e : v[d])
                    for (int k = 0; k < 4; ++k)
                    {
                        pair <int, int> nb = dfs(e.X, e.Y, k);
                        if (dp[nb.X][nb.Y][l][r] > d + 1)
                        {
                            dp[nb.X][nb.Y][l][r] = d + 1;
                            v[d + 1].push_back({nb.X, nb.Y});
                        }
                    }
        }
    }
}


void print()
{
    int ans = INF;

    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            ans = min(ans, dp[i][j][0][n - 1]);

    if(ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);


    read();
    solve();
    print();



    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8448 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 5 ms 8508 KB Output is correct
4 Correct 7 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8448 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 5 ms 8508 KB Output is correct
4 Correct 7 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8448 KB Output is correct
8 Correct 5 ms 10584 KB Output is correct
9 Correct 5 ms 8540 KB Output is correct
10 Correct 5 ms 10668 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8448 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 5 ms 8508 KB Output is correct
4 Correct 7 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8448 KB Output is correct
8 Correct 5 ms 10584 KB Output is correct
9 Correct 5 ms 8540 KB Output is correct
10 Correct 5 ms 10668 KB Output is correct
11 Correct 226 ms 67152 KB Output is correct
12 Correct 21 ms 66872 KB Output is correct
13 Correct 95 ms 66688 KB Output is correct
14 Correct 417 ms 67740 KB Output is correct
15 Correct 186 ms 66892 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8448 KB Output is correct
2 Correct 5 ms 8540 KB Output is correct
3 Correct 5 ms 8508 KB Output is correct
4 Correct 7 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 4 ms 8540 KB Output is correct
7 Correct 4 ms 8448 KB Output is correct
8 Correct 5 ms 10584 KB Output is correct
9 Correct 5 ms 8540 KB Output is correct
10 Correct 5 ms 10668 KB Output is correct
11 Correct 226 ms 67152 KB Output is correct
12 Correct 21 ms 66872 KB Output is correct
13 Correct 95 ms 66688 KB Output is correct
14 Correct 417 ms 67740 KB Output is correct
15 Correct 186 ms 66892 KB Output is correct
16 Correct 291 ms 99468 KB Output is correct
17 Correct 1135 ms 102576 KB Output is correct
18 Correct 409 ms 100600 KB Output is correct
19 Correct 268 ms 99424 KB Output is correct
20 Correct 881 ms 101196 KB Output is correct