oj.uz

Submission #389539

# Submission time Handle Problem Language Result Execution time Memory
389539 2021-04-14T07:14:54 Z jjang36524 Robots (APIO13_robots) C++14
30 / 100
 235 ms 62692 KB 
#include <iostream>
#include <algorithm>
#include <string.h>
#include <queue>
using namespace std;
#define itn int
pair<short,short>lastp[501][501][4];
int dp[45][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');
}
int ge(int n,int m)
{
    int ans=m;
    int i;
    for(i=0;i<n;i++)
        ans+=n-i;
    return ans;
}
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[ge(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[ge(s,e)][l][m]=min((int)dp[ge(s,e)][l][m],dp[ge(s,k)][l][m]+dp[ge(k+1,e)][l][m]);
                        if(i==K-1)
                            ans=min(ans,(int)dp[ge(s,e)][l][m]);
                    }
                }
            }
            for(l=0;l<N;l++)
            {
                for(m=0;m<M;m++)
                {
                      if(dp[ge(s,e)][l][m]<=N*M)
                        co[dp[ge(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[ge(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:113: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]
  113 |                 for(l=0;l<co[k].size();l++)
      |                         ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56432 KB Output is correct
2 Correct 28 ms 56436 KB Output is correct
3 Correct 30 ms 56400 KB Output is correct
4 Correct 30 ms 56452 KB Output is correct
5 Correct 33 ms 56404 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56432 KB Output is correct
2 Correct 28 ms 56436 KB Output is correct
3 Correct 30 ms 56400 KB Output is correct
4 Correct 30 ms 56452 KB Output is correct
5 Correct 33 ms 56404 KB Output is correct
6 Correct 31 ms 56524 KB Output is correct
7 Correct 30 ms 56388 KB Output is correct
8 Correct 30 ms 56448 KB Output is correct
9 Correct 30 ms 56460 KB Output is correct
10 Correct 29 ms 56476 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56432 KB Output is correct
2 Correct 28 ms 56436 KB Output is correct
3 Correct 30 ms 56400 KB Output is correct
4 Correct 30 ms 56452 KB Output is correct
5 Correct 33 ms 56404 KB Output is correct
6 Correct 31 ms 56524 KB Output is correct
7 Correct 30 ms 56388 KB Output is correct
8 Correct 30 ms 56448 KB Output is correct
9 Correct 30 ms 56460 KB Output is correct
10 Correct 29 ms 56476 KB Output is correct
11 Incorrect 235 ms 62692 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 56432 KB Output is correct
2 Correct 28 ms 56436 KB Output is correct
3 Correct 30 ms 56400 KB Output is correct
4 Correct 30 ms 56452 KB Output is correct
5 Correct 33 ms 56404 KB Output is correct
6 Correct 31 ms 56524 KB Output is correct
7 Correct 30 ms 56388 KB Output is correct
8 Correct 30 ms 56448 KB Output is correct
9 Correct 30 ms 56460 KB Output is correct
10 Correct 29 ms 56476 KB Output is correct
11 Incorrect 235 ms 62692 KB Output isn't correct
12 Halted 0 ms 0 KB -