Advertisement
Naxocist

TOI18_Mountain

Mar 29th, 2023
812
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.98 KB | Source Code | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define INF 2e18
  5.  
  6. const int N = 5e2 + 3;
  7. using ll = long long;
  8. using pi = pair<ll, ll>;
  9. ll dp[N][N];
  10. pi ar[N];
  11.  
  12. ll dist(pi a, pi b) {
  13.     return abs(a.first - b.first) + abs(a.second - b.second);
  14. }
  15.  
  16. int main() {
  17.  
  18.     int n, m; scanf("%d%d", &n, &m);
  19.  
  20.     for(int i=1;i<= n; ++i ) {
  21.         ll x, y; scanf("%lld %lld", &x, &y);
  22.         ar[i] = pi(x, y);
  23.     }
  24.  
  25.     for(int i=1; i<=n; ++i) {
  26.         for(int j=1; j<=n; ++j) {
  27.             dp[i][j] = INF;
  28.         }
  29.     }
  30.  
  31.     for(int i=1; i<=n; ++i) dp[1][i] = dist(ar[1], ar[i]);
  32.  
  33.     for(int x=2; x<=n; ++x) {
  34.         for(int i=2; i<=n; ++i) {
  35.             for(int k=2; k<n; ++k) {
  36.                 if(i == k) continue;
  37.                 ll mx = max(dp[x-1][k], dist(ar[k], ar[i]));
  38.                 dp[x][i] = min(mx,dp[x][i]);
  39.             }
  40.         }
  41.     }
  42.  
  43.     ll res = 0;
  44.     while(m--) {
  45.         ll p; scanf("%lld", &p);
  46.  
  47.         int x;
  48.         for(x=1; x<=n; ++x) {
  49.             if(p >= dp[x][n]) break ;
  50.         }
  51.  
  52.         res += x;
  53.     }
  54.  
  55.     printf("%lld", res);
  56.  
  57.     return 0;
  58. }
  59.  
  60. /*
  61. 5 2
  62. 0 1
  63. 2 2
  64. 3 6
  65. 6 6
  66. 9 10
  67. 10
  68. 15
  69. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement