Submission #915796

#	Time	Username	Problem	Language	Result	Execution time	Memory
915796		stefanneagu	OBELISK (NOI14_obelisk)	C++17	5 / 25	19 ms	11352 KiB

obelisk

#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 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 7