oj.uz

Submission #490839

# Submission time Handle Problem Language Result Execution time Memory
490839 2021-11-29T13:27:10 Z Rainbowbunny Robots (APIO13_robots) C++17
100 / 100
 549 ms 109280 KB 
#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 505;
const int INF = 1e9;
const int IIII = 1e6;
 
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[IIII];
 
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;
            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 < IIII; 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 18 ms 23756 KB Output is correct
2 Correct 18 ms 23832 KB Output is correct
3 Correct 17 ms 23800 KB Output is correct
4 Correct 20 ms 23876 KB Output is correct
5 Correct 21 ms 23884 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23756 KB Output is correct
2 Correct 18 ms 23832 KB Output is correct
3 Correct 17 ms 23800 KB Output is correct
4 Correct 20 ms 23876 KB Output is correct
5 Correct 21 ms 23884 KB Output is correct
6 Correct 20 ms 23736 KB Output is correct
7 Correct 17 ms 23720 KB Output is correct
8 Correct 21 ms 23756 KB Output is correct
9 Correct 19 ms 23856 KB Output is correct
10 Correct 18 ms 23884 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23756 KB Output is correct
2 Correct 18 ms 23832 KB Output is correct
3 Correct 17 ms 23800 KB Output is correct
4 Correct 20 ms 23876 KB Output is correct
5 Correct 21 ms 23884 KB Output is correct
6 Correct 20 ms 23736 KB Output is correct
7 Correct 17 ms 23720 KB Output is correct
8 Correct 21 ms 23756 KB Output is correct
9 Correct 19 ms 23856 KB Output is correct
10 Correct 18 ms 23884 KB Output is correct
11 Correct 175 ms 58604 KB Output is correct
12 Correct 23 ms 29132 KB Output is correct
13 Correct 94 ms 44792 KB Output is correct
14 Correct 259 ms 63940 KB Output is correct
15 Correct 150 ms 55828 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23756 KB Output is correct
2 Correct 18 ms 23832 KB Output is correct
3 Correct 17 ms 23800 KB Output is correct
4 Correct 20 ms 23876 KB Output is correct
5 Correct 21 ms 23884 KB Output is correct
6 Correct 20 ms 23736 KB Output is correct
7 Correct 17 ms 23720 KB Output is correct
8 Correct 21 ms 23756 KB Output is correct
9 Correct 19 ms 23856 KB Output is correct
10 Correct 18 ms 23884 KB Output is correct
11 Correct 175 ms 58604 KB Output is correct
12 Correct 23 ms 29132 KB Output is correct
13 Correct 94 ms 44792 KB Output is correct
14 Correct 259 ms 63940 KB Output is correct
15 Correct 150 ms 55828 KB Output is correct
16 Correct 216 ms 76868 KB Output is correct
17 Correct 549 ms 109280 KB Output is correct
18 Correct 225 ms 81080 KB Output is correct
19 Correct 201 ms 76912 KB Output is correct
20 Correct 333 ms 91896 KB Output is correct