oj.uz

Submission #42504

# Submission time Handle Problem Language Result Execution time Memory
42504 2018-02-28T02:30:17 Z funcsr Robots (APIO13_robots) C++14
30 / 100
 1500 ms 117128 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define INF 1000001919
#define _1 first
#define _2 second
const int DX[4] = {-1, 0, 1, 0};
const int DY[4] = {0, -1, 0, 1};

int N, W, H;
char A[500][500];
P dst[500][500][4];
P f(int x, int y, int d) {
  if (dst[x][y][d] != P(-2, -2)) return dst[x][y][d];
  dst[x][y][d] = P(-1, -1);
  int nx = x+DX[d], ny = y+DY[d], nd = d;
  if (nx<0||nx>=W||ny<0||ny>=H||A[nx][ny]=='x') return dst[x][y][d] = P(x, y);
  if (A[nx][ny] == 'A') nd = (d+3)%4;
  if (A[nx][ny] == 'C') nd = (d+1)%4;
  return dst[x][y][d] = f(nx, ny, nd);
}

const int MAX_D = 10*500*500;
int X[9], Y[9];
int dp[9][9][500][500];
vector<P> Q[MAX_D];
bool used[500][500];
void bfs(int D[500][500]) {
  rep(i, W) rep(j, H) used[i][j] = false;
  rep(i, MAX_D) Q[i].clear();
  rep(x, W) rep(y, H) if (D[x][y] != INF) Q[D[x][y]].pb(P(x, y));
  vector<P> q;
  rep(r, MAX_D) {
    vector<P> nq;
    for (P p : Q[r]) {
      int x = p._1, y = p._2;
      if (!used[x][y]) {
        used[x][y] = true;
        q.pb(P(x, y));
      }
    }
    for (P p : q) {
      int x = p._1, y = p._2;
      rep(k, 4) {
        P np = dst[x][y][k];
        if (np._1 != -1 && !used[np._1][np._2]) {
          used[np._1][np._2] = true;
          D[np._1][np._2] = r+1;
          nq.pb(np);
        }
      }
    }
    q.clear();
    swap(q, nq);
  }
}
int main() {
  cin >> N >> W >> H;
  rep(y, H) rep(x, W) {
    cin >> A[x][y];
    if ('0' <= A[x][y] && A[x][y] <= '9') X[A[x][y]-'1'] = x, Y[A[x][y]-'1'] = y;
  }
  rep(x, W) rep(y, H) rep(d, 4) dst[x][y][d] = P(-2, -2);
  rep(x, W) rep(y, H) if (A[x][y] != 'x') rep(d, 4) f(x, y, d);
  rep(i, N) rep(j, N) rep(x, W) rep(y, H) dp[i][j][x][y] = INF;
  rep(i, N) dp[i][i][X[i]][Y[i]] = 0;
  for (int len=1; len<=N; len++) {
    rep(l, N) {
      int r = l+len-1;
      if (r >= N) break;
      rep(x, W) rep(y, H) for (int k=l; k<r; k++) {
        dp[l][r][x][y] = min(dp[l][r][x][y], dp[l][k][x][y]+dp[k+1][r][x][y]);
      }
      bfs(dp[l][r]);
    }
  }
  int m = INF;
  rep(x, W) rep(y, H) m = min(m, dp[0][N-1][x][y]);
  if (m == INF) m = -1;
  cout << m << "\n";
  return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 59000 KB Output is correct
2 Correct 125 ms 59204 KB Output is correct
3 Correct 127 ms 59264 KB Output is correct
4 Correct 131 ms 59352 KB Output is correct
5 Correct 123 ms 59460 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 59000 KB Output is correct
2 Correct 125 ms 59204 KB Output is correct
3 Correct 127 ms 59264 KB Output is correct
4 Correct 131 ms 59352 KB Output is correct
5 Correct 123 ms 59460 KB Output is correct
6 Correct 124 ms 59548 KB Output is correct
7 Correct 122 ms 59548 KB Output is correct
8 Correct 121 ms 59548 KB Output is correct
9 Correct 130 ms 59548 KB Output is correct
10 Correct 123 ms 59640 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 59000 KB Output is correct
2 Correct 125 ms 59204 KB Output is correct
3 Correct 127 ms 59264 KB Output is correct
4 Correct 131 ms 59352 KB Output is correct
5 Correct 123 ms 59460 KB Output is correct
6 Correct 124 ms 59548 KB Output is correct
7 Correct 122 ms 59548 KB Output is correct
8 Correct 121 ms 59548 KB Output is correct
9 Correct 130 ms 59548 KB Output is correct
10 Correct 123 ms 59640 KB Output is correct
11 Correct 1407 ms 114544 KB Output is correct
12 Correct 87 ms 114544 KB Output is correct
13 Correct 822 ms 114544 KB Output is correct
14 Execution timed out 1546 ms 117128 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 59000 KB Output is correct
2 Correct 125 ms 59204 KB Output is correct
3 Correct 127 ms 59264 KB Output is correct
4 Correct 131 ms 59352 KB Output is correct
5 Correct 123 ms 59460 KB Output is correct
6 Correct 124 ms 59548 KB Output is correct
7 Correct 122 ms 59548 KB Output is correct
8 Correct 121 ms 59548 KB Output is correct
9 Correct 130 ms 59548 KB Output is correct
10 Correct 123 ms 59640 KB Output is correct
11 Correct 1407 ms 114544 KB Output is correct
12 Correct 87 ms 114544 KB Output is correct
13 Correct 822 ms 114544 KB Output is correct
14 Execution timed out 1546 ms 117128 KB Time limit exceeded
15 Halted 0 ms 0 KB -