Submission #490721

#	Time	Username	Problem	Language	Result	Execution time	Memory
490721		Rainbowbunny	Robots (APIO13_robots)	C++17	100 / 100	443 ms	91772 KiB

robots

#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 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 40 / 40