oj.uz

Submission #569186

# Submission time Handle Problem Language Result Execution time Memory
569186 2022-05-27T00:09:45 Z zaneyu Robots (APIO13_robots) C++14
100 / 100
 968 ms 114368 KB 
/*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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 3 ms 6332 KB Output is correct
7 Correct 3 ms 6328 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 4 ms 6356 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 3 ms 6332 KB Output is correct
7 Correct 3 ms 6328 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 4 ms 6356 KB Output is correct
11 Correct 164 ms 46032 KB Output is correct
12 Correct 22 ms 45324 KB Output is correct
13 Correct 89 ms 46888 KB Output is correct
14 Correct 298 ms 46264 KB Output is correct
15 Correct 126 ms 45772 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6228 KB Output is correct
2 Correct 3 ms 6228 KB Output is correct
3 Correct 3 ms 6228 KB Output is correct
4 Correct 3 ms 6356 KB Output is correct
5 Correct 3 ms 6356 KB Output is correct
6 Correct 3 ms 6332 KB Output is correct
7 Correct 3 ms 6328 KB Output is correct
8 Correct 3 ms 6228 KB Output is correct
9 Correct 3 ms 6228 KB Output is correct
10 Correct 4 ms 6356 KB Output is correct
11 Correct 164 ms 46032 KB Output is correct
12 Correct 22 ms 45324 KB Output is correct
13 Correct 89 ms 46888 KB Output is correct
14 Correct 298 ms 46264 KB Output is correct
15 Correct 126 ms 45772 KB Output is correct
16 Correct 563 ms 113532 KB Output is correct
17 Correct 968 ms 114368 KB Output is correct
18 Correct 314 ms 113264 KB Output is correct
19 Correct 379 ms 113544 KB Output is correct
20 Correct 682 ms 113960 KB Output is correct