oj.uz

답안 #388410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
388410 2021-04-11T11:50:11 Z jjang36524 로봇 (APIO13_robots) C++14
60 / 100
 231 ms 124160 KB 
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define itn int
pair<int,int>lastp[401][401][4];
int dp[9][9][401][401];
char arr[401][401];
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[200100];
int vis[401][401];
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 27 ms 61548 KB Output is correct
2 Correct 27 ms 61644 KB Output is correct
3 Correct 27 ms 61576 KB Output is correct
4 Correct 27 ms 61560 KB Output is correct
5 Correct 27 ms 61576 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 61548 KB Output is correct
2 Correct 27 ms 61644 KB Output is correct
3 Correct 27 ms 61576 KB Output is correct
4 Correct 27 ms 61560 KB Output is correct
5 Correct 27 ms 61576 KB Output is correct
6 Correct 26 ms 61756 KB Output is correct
7 Correct 30 ms 61508 KB Output is correct
8 Correct 27 ms 61552 KB Output is correct
9 Correct 30 ms 61580 KB Output is correct
10 Correct 31 ms 61560 KB Output is correct

Subtask #3
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 61548 KB Output is correct
2 Correct 27 ms 61644 KB Output is correct
3 Correct 27 ms 61576 KB Output is correct
4 Correct 27 ms 61560 KB Output is correct
5 Correct 27 ms 61576 KB Output is correct
6 Correct 26 ms 61756 KB Output is correct
7 Correct 30 ms 61508 KB Output is correct
8 Correct 27 ms 61552 KB Output is correct
9 Correct 30 ms 61580 KB Output is correct
10 Correct 31 ms 61560 KB Output is correct
11 Correct 126 ms 77540 KB Output is correct
12 Correct 37 ms 63168 KB Output is correct
13 Correct 54 ms 61944 KB Output is correct
14 Correct 231 ms 86212 KB Output is correct
15 Correct 94 ms 65600 KB Output is correct

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 27 ms 61548 KB Output is correct
2 Correct 27 ms 61644 KB Output is correct
3 Correct 27 ms 61576 KB Output is correct
4 Correct 27 ms 61560 KB Output is correct
5 Correct 27 ms 61576 KB Output is correct
6 Correct 26 ms 61756 KB Output is correct
7 Correct 30 ms 61508 KB Output is correct
8 Correct 27 ms 61552 KB Output is correct
9 Correct 30 ms 61580 KB Output is correct
10 Correct 31 ms 61560 KB Output is correct
11 Correct 126 ms 77540 KB Output is correct
12 Correct 37 ms 63168 KB Output is correct
13 Correct 54 ms 61944 KB Output is correct
14 Correct 231 ms 86212 KB Output is correct
15 Correct 94 ms 65600 KB Output is correct
16 Runtime error 94 ms 124160 KB Execution killed with signal 11
17 Halted 0 ms 0 KB -