oj.uz

Submission #354292

# Submission time Handle Problem Language Result Execution time Memory
354292 2021-01-21T16:46:53 Z denkendoemeer Robots (APIO13_robots) C++14
100 / 100
 1012 ms 156564 KB 
#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

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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 113004 KB Output is correct
2 Correct 83 ms 113132 KB Output is correct
3 Correct 82 ms 113004 KB Output is correct
4 Correct 83 ms 113132 KB Output is correct
5 Correct 83 ms 113004 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 113004 KB Output is correct
2 Correct 83 ms 113132 KB Output is correct
3 Correct 82 ms 113004 KB Output is correct
4 Correct 83 ms 113132 KB Output is correct
5 Correct 83 ms 113004 KB Output is correct
6 Correct 92 ms 113028 KB Output is correct
7 Correct 83 ms 113096 KB Output is correct
8 Correct 86 ms 113004 KB Output is correct
9 Correct 85 ms 113004 KB Output is correct
10 Correct 85 ms 113116 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 113004 KB Output is correct
2 Correct 83 ms 113132 KB Output is correct
3 Correct 82 ms 113004 KB Output is correct
4 Correct 83 ms 113132 KB Output is correct
5 Correct 83 ms 113004 KB Output is correct
6 Correct 92 ms 113028 KB Output is correct
7 Correct 83 ms 113096 KB Output is correct
8 Correct 86 ms 113004 KB Output is correct
9 Correct 85 ms 113004 KB Output is correct
10 Correct 85 ms 113116 KB Output is correct
11 Correct 372 ms 118124 KB Output is correct
12 Correct 83 ms 113900 KB Output is correct
13 Correct 227 ms 113388 KB Output is correct
14 Correct 516 ms 125420 KB Output is correct
15 Correct 338 ms 114796 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 113004 KB Output is correct
2 Correct 83 ms 113132 KB Output is correct
3 Correct 82 ms 113004 KB Output is correct
4 Correct 83 ms 113132 KB Output is correct
5 Correct 83 ms 113004 KB Output is correct
6 Correct 92 ms 113028 KB Output is correct
7 Correct 83 ms 113096 KB Output is correct
8 Correct 86 ms 113004 KB Output is correct
9 Correct 85 ms 113004 KB Output is correct
10 Correct 85 ms 113116 KB Output is correct
11 Correct 372 ms 118124 KB Output is correct
12 Correct 83 ms 113900 KB Output is correct
13 Correct 227 ms 113388 KB Output is correct
14 Correct 516 ms 125420 KB Output is correct
15 Correct 338 ms 114796 KB Output is correct
16 Correct 380 ms 113964 KB Output is correct
17 Correct 1012 ms 156564 KB Output is correct
18 Correct 418 ms 118116 KB Output is correct
19 Correct 387 ms 113924 KB Output is correct
20 Correct 648 ms 131128 KB Output is correct