oj.uz

Submission #490721

# Submission time Handle Problem Language Result Execution time Memory
490721 2021-11-29T02:21:32 Z Rainbowbunny Robots (APIO13_robots) C++17
100 / 100
 443 ms 91772 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 505;
const int INF = 1e9;

int n;
int w, h;
pair <int, int> nxt[MAXN][MAXN][4];
int dx[] = {0, -1, 0, 1};
int dy[] = {1, 0, -1, 0};
char a[MAXN][MAXN];
int dp[10][10][MAXN][MAXN];
vector <pair <int, int> > Pos[MAXN * MAXN];

pair <int, int> Cal(int i, int j, int dir)
{
    // cout << i << ' ' << j << ' ' << dir << endl;
    if(nxt[i][j][dir].first != -1)
    {
        return nxt[i][j][dir];
    }
    // cout << dir << endl;
    int rdir = dir;
    if(a[i][j] == 'A')
    {
        rdir++;
        if(rdir == 4)
        {
            rdir = 0;
        }
    }
    else if(a[i][j] == 'C')
    {
        rdir--;
        if(rdir == -1)
        {
            rdir = 3; 
        }
    }
    // cout << rdir << endl;
    int nx = i + dx[rdir], ny = j + dy[rdir];
    nxt[i][j][dir] = make_pair(-2, -2);
    if(nx == 0 or nx == h + 1 or ny == 0 or ny == w + 1)
    {
        return nxt[i][j][dir] = make_pair(i, j);
    }
    if(a[nx][ny] == 'x')
    {
        return nxt[i][j][dir] = make_pair(i, j);
    }
    return nxt[i][j][dir] = Cal(nx, ny, rdir);
}

int main()
{
    // freopen("Input.txt", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> w >> h;
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            cin >> a[i][j];
        }
    }
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            for(int k = 0; k < 4; k++)
            {
                nxt[i][j][k] = make_pair(-1, -1);
            }
        }
    }
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            for(int k = 0; k < 4; k++)
            {
                if(a[i][j] != 'x')
                {
                    Cal(i, j, k);
                    // cout << i << ' ' << j << ' ' << k << '\n';
                    // cout << nxt[i][j][k].first << ' ' << nxt[i][j][k].second << '\n';
                }   
            }
        }
    }
    for(int diff = 0; diff < n; diff++)
    {
        for(int vx = 1; vx + diff <= n; vx++)
        {
            int vy = vx + diff;
            for(int i = 0; i < MAXN * MAXN; i++)
            {
                Pos[i].clear();
            }
            if(diff == 0)
            {
                for(int i = 1; i <= h; i++)
                {
                    for(int j = 1; j <= w; j++)
                    {
                        if(a[i][j] - '0' == vx)
                        {
                            dp[vx][vy][i][j] = 0;   
                            Pos[0].emplace_back(i, j);
                        }
                        else
                        {
                            dp[vx][vy][i][j] = INF;
                        }
                    }
                }
            }
            else
            {
                for(int i = 1; i <= h; i++)
                {
                    for(int j = 1; j <= w; j++)
                    {
                        dp[vx][vy][i][j] = INF;
                        for(int k = vx; k < vy; k++)
                        {
                            dp[vx][vy][i][j] = min(dp[vx][vy][i][j], dp[vx][k][i][j] + dp[k + 1][vy][i][j]);
                        }
                        if(dp[vx][vy][i][j] != INF)
                        {
                            Pos[dp[vx][vy][i][j]].emplace_back(i, j);
                        }
                    }
                }
            }
            for(int vv = 0; vv < MAXN * MAXN; vv++)
            {
                while(!Pos[vv].empty())
                {
                    int x = Pos[vv].back().first, y = Pos[vv].back().second;
                    Pos[vv].pop_back();
                    if(dp[vx][vy][x][y] == vv)
                    {
                        for(int dir = 0; dir < 4; dir++)
                        {
                            int nx = nxt[x][y][dir].first, ny = nxt[x][y][dir].second;
                            if(nx >= 1 and nx <= h and ny >= 1 and ny <= w)
                            {
                                if(dp[vx][vy][nx][ny] > vv + 1)
                                {
                                    dp[vx][vy][nx][ny] = vv + 1;
                                    Pos[vv + 1].emplace_back(nx, ny);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = INF;
    for(int i = 1; i <= h; i++)
    {
        for(int j = 1; j <= w; j++)
        {
            ans = min(ans, dp[1][n][i][j]);
        }
    }
    if(ans == INF)
    {
        ans = -1;
    }
    cout << ans << '\n';
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6220 KB Output is correct
2 Correct 5 ms 6220 KB Output is correct
3 Correct 5 ms 6220 KB Output is correct
4 Correct 5 ms 6348 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6220 KB Output is correct
2 Correct 5 ms 6220 KB Output is correct
3 Correct 5 ms 6220 KB Output is correct
4 Correct 5 ms 6348 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct
6 Correct 6 ms 6348 KB Output is correct
7 Correct 5 ms 6220 KB Output is correct
8 Correct 8 ms 6308 KB Output is correct
9 Correct 5 ms 6348 KB Output is correct
10 Correct 7 ms 6320 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6220 KB Output is correct
2 Correct 5 ms 6220 KB Output is correct
3 Correct 5 ms 6220 KB Output is correct
4 Correct 5 ms 6348 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct
6 Correct 6 ms 6348 KB Output is correct
7 Correct 5 ms 6220 KB Output is correct
8 Correct 8 ms 6308 KB Output is correct
9 Correct 5 ms 6348 KB Output is correct
10 Correct 7 ms 6320 KB Output is correct
11 Correct 104 ms 41024 KB Output is correct
12 Correct 11 ms 11596 KB Output is correct
13 Correct 56 ms 27324 KB Output is correct
14 Correct 183 ms 46296 KB Output is correct
15 Correct 88 ms 38320 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 6220 KB Output is correct
2 Correct 5 ms 6220 KB Output is correct
3 Correct 5 ms 6220 KB Output is correct
4 Correct 5 ms 6348 KB Output is correct
5 Correct 5 ms 6348 KB Output is correct
6 Correct 6 ms 6348 KB Output is correct
7 Correct 5 ms 6220 KB Output is correct
8 Correct 8 ms 6308 KB Output is correct
9 Correct 5 ms 6348 KB Output is correct
10 Correct 7 ms 6320 KB Output is correct
11 Correct 104 ms 41024 KB Output is correct
12 Correct 11 ms 11596 KB Output is correct
13 Correct 56 ms 27324 KB Output is correct
14 Correct 183 ms 46296 KB Output is correct
15 Correct 88 ms 38320 KB Output is correct
16 Correct 147 ms 59360 KB Output is correct
17 Correct 443 ms 91772 KB Output is correct
18 Correct 157 ms 63508 KB Output is correct
19 Correct 129 ms 59412 KB Output is correct
20 Correct 275 ms 74320 KB Output is correct