oj.uz

답안 #388411

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388411 2021-04-11T11:51:12 Z jjang36524 로봇 (APIO13_robots) C++14
60 / 100
 476 ms 163844 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<int,int>>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<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  105 |                 for(l=0;l<co[k].size();l++)
      |                         ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95688 KB Output is correct
3 Correct 41 ms 95732 KB Output is correct
4 Correct 40 ms 95684 KB Output is correct
5 Correct 41 ms 95728 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95688 KB Output is correct
3 Correct 41 ms 95732 KB Output is correct
4 Correct 40 ms 95684 KB Output is correct
5 Correct 41 ms 95728 KB Output is correct
6 Correct 46 ms 95720 KB Output is correct
7 Correct 41 ms 95760 KB Output is correct
8 Correct 43 ms 95748 KB Output is correct
9 Correct 41 ms 95660 KB Output is correct
10 Correct 40 ms 95728 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95688 KB Output is correct
3 Correct 41 ms 95732 KB Output is correct
4 Correct 40 ms 95684 KB Output is correct
5 Correct 41 ms 95728 KB Output is correct
6 Correct 46 ms 95720 KB Output is correct
7 Correct 41 ms 95760 KB Output is correct
8 Correct 43 ms 95748 KB Output is correct
9 Correct 41 ms 95660 KB Output is correct
10 Correct 40 ms 95728 KB Output is correct
11 Correct 145 ms 111692 KB Output is correct
12 Correct 56 ms 97216 KB Output is correct
13 Correct 74 ms 96012 KB Output is correct
14 Correct 249 ms 120500 KB Output is correct
15 Correct 111 ms 99660 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 41 ms 95684 KB Output is correct
2 Correct 41 ms 95688 KB Output is correct
3 Correct 41 ms 95732 KB Output is correct
4 Correct 40 ms 95684 KB Output is correct
5 Correct 41 ms 95728 KB Output is correct
6 Correct 46 ms 95720 KB Output is correct
7 Correct 41 ms 95760 KB Output is correct
8 Correct 43 ms 95748 KB Output is correct
9 Correct 41 ms 95660 KB Output is correct
10 Correct 40 ms 95728 KB Output is correct
11 Correct 145 ms 111692 KB Output is correct
12 Correct 56 ms 97216 KB Output is correct
13 Correct 74 ms 96012 KB Output is correct
14 Correct 249 ms 120500 KB Output is correct
15 Correct 111 ms 99660 KB Output is correct
16 Correct 171 ms 96056 KB Output is correct
17 Runtime error 476 ms 163844 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -