Submission #1261615

#	Time	Username	Problem	Language	Result	Execution time	Memory
1261615		k12_khoi	Robots (APIO13_robots)	C++17	60 / 100	424 ms	229376 KiB

robots

#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define piiii pair<pii,pii>
#define X first
#define Y second

const int N=505;
const int K=12;
const int oo=1e9+1;

int n,m,k,mx_dist,l,r,u,v,x,y,d[K][K][N][N];
int dx[]={1,0,0,-1},dy[]={0,1,-1,0};
int A[]={1,3,0,2},C[]={2,0,3,1};
pii nxt[N][N][5];
bool visited[N][N][5];
char s[N][N];

vector <piiii> ve[N*N];

pii dfs(int u,int v,int dir)
{
    if (s[u][v]=='A') dir=A[dir];
    if (s[u][v]=='C') dir=C[dir];

    if (nxt[u][v][dir]!=make_pair(0,0)) return nxt[u][v][dir];


    if (visited[u][v][dir]) return nxt[u][v][dir]=make_pair(-1,-1);
    visited[u][v][dir]=true;


    if (s[u+dx[dir]][v+dy[dir]]=='x') return nxt[u][v][dir]=make_pair(u,v);

    return nxt[u][v][dir]=dfs(u+dx[dir],v+dy[dir],dir);
}

int dial()
{
    mx_dist=0;
    for (int dist=0;dist<=mx_dist;dist++)
    {
        for (int i=0;i<ve[dist].size();i++)
        {
            l=ve[dist][i].X.X;
            r=ve[dist][i].X.Y;
            u=ve[dist][i].Y.X;
            v=ve[dist][i].Y.Y;

//            cout << l << ' ' << r << ' ' << u << ' ' << v << ' ' << dist << ' ' << mx_dist << endl;

            if (l==1 and r==k)
            {
                for (int j=dist;j<=mx_dist;j++)
                ve[j].clear();

                return dist;
            }

            if (dist>d[l][r][u][v]) continue;


            for (int i=l-1;i>=1;i--)
            if (d[i][r][u][v]>d[l][r][u][v]+d[i][l-1][u][v])
            {
                d[i][r][u][v]=d[l][r][u][v]+d[i][l-1][u][v];
                ve[d[i][r][u][v]].push_back(make_pair(make_pair(i,r),make_pair(u,v)));

                mx_dist=max(mx_dist,d[i][r][u][v]);
            }


            for (int j=r+1;j<=k;j++)
            if (d[l][j][u][v]>d[l][r][u][v]+d[r+1][j][u][v])
            {
                d[l][j][u][v]=d[l][r][u][v]+d[r+1][j][u][v];
                ve[d[l][j][u][v]].push_back(make_pair(make_pair(l,j),make_pair(u,v)));

                mx_dist=max(mx_dist,d[l][j][u][v]);
            }


            for (int dir=0;dir<=3;dir++)
            {
                pii j=nxt[u][v][dir];

                if (j!=make_pair(-1,-1) and d[l][r][j.X][j.Y]>dist+1)
                {
                    d[l][r][j.X][j.Y]=dist+1;
                    ve[d[l][r][j.X][j.Y]].push_back(make_pair(make_pair(l,r),make_pair(j.X,j.Y)));

                    mx_dist=max(mx_dist,d[l][r][j.X][j.Y]);
                }
            }
        }

        ve[dist].clear();
    }

    return -1;
}

int main()
{
    ios_base::sync_with_stdio(NULL);
    cin.tie(NULL); cout.tie(NULL);

    cin >> k >> m >> n;
    for (int i=0;i<=n+1;i++)
    s[i][0]=s[i][m+1]='x';

    for (int j=0;j<=m+1;j++)
    s[0][j]=s[n+1][j]='x';

    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    cin >> s[i][j];


    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    for (int dir=0;dir<=3;dir++)
    if (s[i][j]!='x') dfs(i,j,dir);

    for (int l=1;l<=k;l++)
    for (int r=l;r<=k;r++)
    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    d[l][r][i][j]=oo;


    for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
    if (s[i][j]>'0' and s[i][j]<=k+'0')
    {
        int id=s[i][j]-'0';
        d[id][id][i][j]=0;
        ve[0].push_back(make_pair(make_pair(id,id),make_pair(i,j)));
    }


    cout << dial();
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 40