oj.uz

Submission #915796

# Submission time Handle Problem Language Result Execution time Memory
915796 2024-01-24T17:41:22 Z stefanneagu OBELISK (NOI14_obelisk) C++17
5 / 25
 19 ms 11352 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

/*

3 1
5 2
1 6
1 5 5
1 3 2

*/


const int nmax = 696;

int sz[nmax];

struct str {
  int i, j;
} mat[nmax][nmax];

int dp[nmax][nmax];

int32_t main() {
  for(int i = 0; i < nmax; i ++) {
    for(int j = 0; j < nmax; j ++) {
      dp[i][j] = 1e9;
    }
  }
  int n, useless, si, sj, ei, ej;
  cin >> n >> useless >> si >> sj >> ei >> ej;
  if(n == 1) {
    cout << abs(si - ei) + abs(sj - ej);
    return 0;
  }
  for(int i = n; i > 1; i --) {
    int x;
    cin >> x;
    sz[i] = x;
    for(int j = 1; j <= x; j ++) {
      cin >> mat[i][j].i >> mat[i][j].j;
    }
  }
  for(int i = 1; i <= sz[n]; i ++) {
    dp[n][i] = abs(si - mat[n][i].i) + abs(sj - mat[n][i].j);
  }
  for(int et = n - 1; et > 1; et --) {
    for(int sus = 1; sus <= sz[et + 1]; sus ++) {
      for(int jos = 1; jos <= sz[et]; jos ++) {
        int x = dp[et + 1][sus] + abs(mat[et + 1][sus].i - mat[et][jos].i) + abs(mat[et + 1][sus].j - mat[et][jos].j);
        dp[et][jos] = min(dp[et][jos], x);
      }
    }
  }
  int ans = 1e9;
  for(int ult = 1; ult <= sz[2]; ult ++) {
    int x = dp[2][ult] + abs(mat[2][ult].i - ei) + abs(mat[2][ult].j - ej);
    ans = min(ans, x);
  }
  cout << ans;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4700 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 2 ms 4696 KB Output is correct

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 4696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 10844 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 19 ms 11352 KB Output isn't correct
2 Halted 0 ms 0 KB -