oj.uz

Submission #388412

# Submission time Handle Problem Language Result Execution time Memory
388412 2021-04-11T11:52:23 Z jjang36524 Robots (APIO13_robots) C++14
100 / 100
 718 ms 137544 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95748 KB Output is correct
3 Correct 41 ms 95700 KB Output is correct
4 Correct 42 ms 95684 KB Output is correct
5 Correct 41 ms 95684 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95748 KB Output is correct
3 Correct 41 ms 95700 KB Output is correct
4 Correct 42 ms 95684 KB Output is correct
5 Correct 41 ms 95684 KB Output is correct
6 Correct 40 ms 95684 KB Output is correct
7 Correct 42 ms 95768 KB Output is correct
8 Correct 41 ms 95752 KB Output is correct
9 Correct 41 ms 95640 KB Output is correct
10 Correct 40 ms 95716 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95748 KB Output is correct
3 Correct 41 ms 95700 KB Output is correct
4 Correct 42 ms 95684 KB Output is correct
5 Correct 41 ms 95684 KB Output is correct
6 Correct 40 ms 95684 KB Output is correct
7 Correct 42 ms 95768 KB Output is correct
8 Correct 41 ms 95752 KB Output is correct
9 Correct 41 ms 95640 KB Output is correct
10 Correct 40 ms 95716 KB Output is correct
11 Correct 172 ms 104288 KB Output is correct
12 Correct 49 ms 96596 KB Output is correct
13 Correct 80 ms 95908 KB Output is correct
14 Correct 280 ms 108596 KB Output is correct
15 Correct 128 ms 98044 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95748 KB Output is correct
3 Correct 41 ms 95700 KB Output is correct
4 Correct 42 ms 95684 KB Output is correct
5 Correct 41 ms 95684 KB Output is correct
6 Correct 40 ms 95684 KB Output is correct
7 Correct 42 ms 95768 KB Output is correct
8 Correct 41 ms 95752 KB Output is correct
9 Correct 41 ms 95640 KB Output is correct
10 Correct 40 ms 95716 KB Output is correct
11 Correct 172 ms 104288 KB Output is correct
12 Correct 49 ms 96596 KB Output is correct
13 Correct 80 ms 95908 KB Output is correct
14 Correct 280 ms 108596 KB Output is correct
15 Correct 128 ms 98044 KB Output is correct
16 Correct 213 ms 95936 KB Output is correct
17 Correct 718 ms 137544 KB Output is correct
18 Correct 256 ms 103096 KB Output is correct
19 Correct 206 ms 96424 KB Output is correct
20 Correct 490 ms 124972 KB Output is correct