Submission #287779

#TimeUsernameProblemLanguageResultExecution timeMemory
287779NamnamseoRobots (APIO13_robots)C++17
30 / 100
513 ms32836 KiB
#include <cstdio> #include <cstring> #include <utility> #include <vector> #define rep(i,n) for(int i=0;i<n;++i) #define rrep(i,n) for(int i=1;i<=n;++i) #define x first #define y second #define eb emplace_back using namespace std; using pp=pair<int,int>; int n, m, k; char q[510][510]; pp e[510][510][4]; pp il[10]; using t4=tuple<int,int,int,int>; int dp[510][510][50]; vector<pp> rm[510][510]; const int dx[5] = {0, 1, 0, -1}, *dy = dx+1; pp E(int x, int y, int d) { pp &ret = e[x][y][d]; if (ret.x) return ret; int nx=x+dx[d], ny=y+dy[d]; if (1<=nx && nx<=n && 1<=ny && ny<=m && q[nx][ny]!='x') { switch(q[nx][ny]) { case 'A': ret = E(nx, ny, (d+3)%4); break; case 'C': ret = E(nx, ny, (d+1)%4); break; default: ret = E(nx, ny, d); break; } return ret; } else return ret={x, y}; } int C[10][10]; int f(int x, int y, int l, int r) { if (l == r && q[x][y] == 48+l) return 0; int p = C[l][r]; int &ret = dp[x][y][p]; if (ret) return ret; ret = 1e9; for(int i=l; i<r; ++i) ret = min(ret, f(x, y, l, i) + f(x, y, i+1, r)); for(pp &t:rm[x][y]) ret = min(ret, 1+f(t.x, t.y, l, r)); return ret; } int main() { scanf("%d%d%d",&k,&m,&n); rrep(i, n) { scanf("%s", q[i]+1); rrep(j, m) if ((q[i][j]&48)==48) il[q[i][j]-48]={i,j}; } rrep(i, n) rrep(j, m) rep(d, 4) { pp x = E(i, j, d); if (x != pp{i, j}) rm[x.x][x.y].eb(i, j); } { static int p = 0; rrep(i, k) rrep(j, i) C[j][i] = ++p; } int ans = 2e9; rrep(i, n) rrep(j, m) if (q[i][j] != 'x') { ans = min(ans, f(i, j, 1, k)); } if (ans > n*m*k*2) ans = -1; printf("%d\n", ans); return 0; }

Compilation message (stderr)

robots.cpp: In function 'int main()':
robots.cpp:58:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   58 |     scanf("%d%d%d",&k,&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   60 |         scanf("%s", q[i]+1);
      |         ~~~~~^~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...