Submission #569186

#	Time	Username	Problem	Language	Result	Execution time	Memory
569186		zaneyu	Robots (APIO13_robots)	C++14	100 / 100	968 ms	114368 KiB

robots

/*input
2 3 1
1x2

*/
#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("unroll-loo8ps,no-stack-protector")
//order_of_key #of elements less than x
// find_by_order kth element
#define ll long long
#define ld long double
#define pii pair<int,int>
#define f first
#define s second
#define pb push_back
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define FIlim(n,x) memset(n,x,sizeof(n))
#define ALL(_a) _a.begin(),_a.end()
#define sz(x) (int)x.size()
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()),c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
const ll INF64=4e18;
const ll INF=0x3f3f3f3f;
const ll MOD=1e9+7;
//const ld PI=acos(-1);
const ld eps=1e-9;
const int maxn=5e2+5;
#define lowb(x) x&(-x)
#define MNTO(x,y) x=min(x,(__typeof__(x))y)
#define MXTO(x,y) x=max(x,(__typeof__(x))y)
#define FILL(x,y) memset(x,y,sizeof(x))
inline ll mult(ll a,ll b){
    a%=MOD,b%=MOD;
    return (a*b)%MOD;
}
inline ll mypow(ll a,ll b){
    if(b<=0) return 1;
    a%=MOD;
    ll res=1;
    while(b){
        if(b&1) res=mult(res,a);
        a=mult(a,a);
        b>>=1;
    }
    return res;
}
char arr[maxn][maxn];
int dp[maxn][maxn][10][10];
vector<pii> v[maxn*maxn];
pii to[maxn][maxn][4];
int n,m;
bool isin(int x,int y){
    if(x<0 or x>=n or y<0 or y>=m) return false;
    return true;
}
int dx[4]={-1,0,1,0};
int dy[4]={0,1,0,-1};
int32_t main(){
    ios::sync_with_stdio(false),cin.tie(0);
    int rob;
    cin>>rob>>n>>m;
    swap(n,m);
    REP(i,n) cin>>arr[i];
    REP(i,n) REP(j,m) REP(a,rob) REP(b,rob) dp[i][j][a][b]=INF;
    REP(i,n){
        REP(j,m){
            if(isdigit(arr[i][j])){
                int z=arr[i][j]-'0'-1;
                dp[i][j][z][z]=0;
            }
        }
    }
    REP(i,n){
        REP(j,m){
            if(arr[i][j]=='x') continue;
            REP(k,4){
                
                int dir=k;
                if(arr[i][j]=='A') dir+=3;
                if(arr[i][j]=='C') dir++;
                dir%=4;
                int x=i,y=j;
                while(true){
                    int nx=x+dx[dir],ny=y+dy[dir];
                    if(!isin(nx,ny) or arr[nx][ny]=='x') break;
                    x=nx,y=ny;
                    if(arr[x][y]=='A') dir+=3;
                    if(arr[x][y]=='C') dir++;
                    dir%=4;
                }
                to[i][j][k]={x,y};
                //cout<<i<<' '<<j<<' '<<k<<' '<<x<<' '<<y<<'\n';
            }
        }
    }
   // return 0;
    REP(i,rob){
        REP(l,rob-i){
            int r=i+l;
            REP(a,n){
                REP(b,m){
                    if(arr[a][b]=='x') continue;
                    for(int k=l;k<r;k++){
                        MNTO(dp[a][b][l][r],dp[a][b][l][k]+dp[a][b][k+1][r]);
                    }
                    if(dp[a][b][l][r]!=INF) v[dp[a][b][l][r]].pb({a,b});
                }
            }
            REP(a,n*m){
                for(auto x:v[a]){
                    //cout<<x.f<<' '<<x.s<<'\n';
                    if(dp[x.f][x.s][l][r]!=a) continue;
                    REP(k,4){
                        pii z=to[x.f][x.s][k];
                        if(dp[z.f][z.s][l][r]>dp[x.f][x.s][l][r]+1){
                            dp[z.f][z.s][l][r]=dp[x.f][x.s][l][r]+1;
                            v[dp[z.f][z.s][l][r]].pb(z);
                        }
                    }
                }
                v[a].clear();
                v[a].shrink_to_fit();
            }
        }
    }
    int ans=INF;
    REP(i,n) REP(j,m) MNTO(ans,dp[i][j][0][rob-1]);
    if(ans==INF) ans=-1;
    cout<<ans;
}

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