Submission #388412

#	Time	Username	Problem	Language	Result	Execution time	Memory
388412		jjang36524	Robots (APIO13_robots)	C++14	100 / 100	718 ms	137544 KiB

robots

#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define itn int
pair<int,int>lastp[501][501][4];
int dp[9][9][501][501];
char arr[501][501];
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int N,M,K;
int isv(int n,int m)
{
    return (n<0)||(n>=N)||(m<0)||(m>=M)||(arr[n][m]=='x');
}
pair<int,int> findne(int n,int m,int c)
{
    if(lastp[n][m][c].first!=-1)
        return lastp[n][m][c];
    lastp[n][m][c]={-2,-2};
    if(isv(n,m))
    {
        return lastp[n][m][c];
    }
    int on=n;
    int om=m;
    int oc=c;
    if(arr[n][m]=='A')
        c--;
    if(arr[n][m]=='C')
        c++;
    c+=4;
    c%=4;
    n+=dx[c];
    m+=dy[c];
    if(isv(n,m))
    {
        return lastp[on][om][oc]={on,om};
    }
    return lastp[on][om][oc]=findne(n,m,c);
}
vector<pair<short,short>>co[300100];
int vis[501][501];
int main()
{
    memset(lastp,-1,sizeof(lastp));
    memset(dp,1,sizeof(dp));
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> K >> M >>N;
    int i,j,k,l,m;
    for(i=0;i<N;i++)
    {
        cin >> arr[i];
    }
    for(i=0;i<N;i++)
    {
        for(j=0;j<M;j++)
        {
            if(arr[i][j]>='0'&&arr[i][j]<='9')
            {
                dp[arr[i][j]-'1'][arr[i][j]-'1'][i][j]=0;
            }
            for(k=0;k<4;k++)
                findne(i,j,k);
        }
    }
    int ans=123456789;
    for(i=0;i<K;i++)
    {
        int j;
        for(j=0;j<K-i;j++)
        {
            memset(vis,0,sizeof(vis));
            int s=j;
            int e=j+i;
            for(k=0;k<=N*M;k++)
            {
                co[k].clear();
            }
            for(k=s;k<e;k++)
            {
                for(l=0;l<N;l++)
                {
                    for(m=0;m<M;m++)
                    {
                        dp[s][e][l][m]=min(dp[s][e][l][m],dp[s][k][l][m]+dp[k+1][e][l][m]);
                        if(i==K-1)
                            ans=min(ans,dp[s][e][l][m]);
                    }
                }
            }
            for(l=0;l<N;l++)
            {
                for(m=0;m<M;m++)
                {
                      if(dp[s][e][l][m]<=N*M)
                        co[dp[s][e][l][m]].push_back({l,m});
                }
            }
            for(k=0;k<=N*M;k++)
            {
                int l;
                for(l=0;l<co[k].size();l++)
                {
                    if(co[k][l].first<0||vis[co[k][l].first][co[k][l].second])
                        continue;
                    dp[s][e][co[k][l].first][co[k][l].second]=k;
                    if(i==K-1)
                        ans=min(ans,k);
                    vis[co[k][l].first][co[k][l].second]=1;
                    for(m=0;m<4;m++)
                    {
                        co[k+1].push_back(lastp[co[k][l].first][co[k][l].second][m]);
                    }
                }
            }
        }
    }
    if(ans>N*M)
    cout <<-1;
    else
    cout << ans;
}

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:105:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<short int, short int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |                 for(l=0;l<co[k].size();l++)
      |                         ~^~~~~~~~~~~~~

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