Submission #354292

#	Time	Username	Problem	Language	Result	Execution time	Memory
354292		denkendoemeer	Robots (APIO13_robots)	C++14	100 / 100	1012 ms	156564 KiB

robots

#include<bits/stdc++.h>
using namespace std;
int dx[]={-1,0,1,0},dy[]={0,1,0,-1},dp[50][505][505],cost[10][10],n,m;
const int inf=1e9;
vector<array<int,2>>b[2250005];
array<int,2>nex[505][505][5],cost2[50];
string s[505];
array<int,2>dfs(int x,int y,int dir)
{
    if (nex[x][y][dir][0]==-1){
        nex[x][y][dir][0]=-2;
        int auxi=dir;
        if (s[x][y]=='C')
            auxi=(dir+1)%4;
        if (s[x][y]=='A')
            auxi=(dir+3)%4;
        int x2,y2;
        x2=x+dx[auxi];
        y2=y+dy[auxi];
        if (x2<0 || x2>=n || y2<0 || y2>=m || s[x2][y2]=='x')
            nex[x][y][dir]=(array<int,2>){x,y};
        else
            nex[x][y][dir]=dfs(x2,y2,auxi);
    }
    return nex[x][y][dir];
}
void path(int aux[505][505],int x,int y,int dir)
{
    if (dir<2250000 && aux[x][y]>dir){
        aux[x][y]=dir;
        b[dir].push_back((array<int,2>){x,y});
    }
}
void bfs(int aux[505][505])
{
    int i,dir;
    for(i=0;i<2250000;i++)
        for(auto it:b[i]){
            for(dir=0;dir<4;dir++){
                array<int,2>auxi=nex[it[0]][it[1]][dir];
                path(aux,auxi[0],auxi[1],i+1);
            }
        b[i].clear();
        }
}
int main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    int cnt,i,j,dir,k;
    scanf("%d%d%d\n",&cnt,&m,&n);
    for(i=0;i<n;i++)
        cin>>s[i];
    memset(nex,-1,sizeof(nex));
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            for(dir=0;dir<4;dir++)
                dfs(i,j,dir);
    memset(dp,0x3f,sizeof(dp));
    int ind=0,i2,j2;
    for(i=0;i<cnt;i++)
        for(j=i;j>=0;j--){
            cost[j][i]=ind;
            cost2[ind]=(array<int,2>){j,i};
            if (j<i){
                for(i2=0;i2<n;i2++)
                    for(j2=0;j2<m;j2++)
                        for(k=j;k<i;k++)
                            path(dp[ind],i2,j2,dp[cost[j][k]][i2][j2]+dp[cost[k+1][i]][i2][j2]);
            }
            else{
                for(i2=0;i2<n;i2++)
                    for(j2=0;j2<m;j2++)
                        if (s[i2][j2]-48==j+1)
                            path(dp[ind],i2,j2,0);
            }
            bfs(dp[ind]);
            ind++;
        }
    int ans=inf;
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            ans=min(ans,dp[cost[0][cnt-1]][i][j]);
    if (ans==inf)
        printf("-1\n");
    else
        printf("%d\n",ans);
return 0;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%d%d%d\n",&cnt,&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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