Alex_tz307

USACO 2016 December Contest, Gold Problem 2. Cow Checklist

Jul 26th, 2021
530
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define sqr(x) (x) * (x)
  3.  
  4. using namespace std;
  5.  
  6. ifstream fin("checklist.in");
  7. ofstream fout("checklist.out");
  8.  
  9. const int64_t INF = 1e18L;
  10.  
  11. int cost(const pair<int,int> &a, const pair<int,int> &b) {
  12.   return sqr(b.first - a.first) + sqr(b.second - a.second);
  13. }
  14.  
  15. void min_self(int64_t &x, int64_t y) {
  16.   x = min(x, y);
  17. }
  18.  
  19. int main() {
  20.   int n, m;
  21.   fin >> n >> m;
  22.   vector<pair<int,int>> a(n), b(m);
  23.   for (auto &it : a)
  24.     fin >> it.first >> it.second;
  25.   for (auto &it : b)
  26.     fin >> it.first >> it.second;
  27.   vector<vector<vector<int64_t>>> dp(2, vector<vector<int64_t>>(n + 1, vector<int64_t>(m + 1, INF)));
  28.   dp[0][1][0] = 0;
  29.   for (int i = 0; i <= n; ++i)
  30.     for (int j = 0; j <= m; ++j) {
  31.       int add;
  32.       if (i && j) {
  33.         add = cost(a[i - 1], b[j - 1]);
  34.         min_self(dp[0][i][j], dp[1][i - 1][j] + add);
  35.         min_self(dp[1][i][j], dp[0][i][j - 1] + add);
  36.       }
  37.       if (i > 1) {
  38.         add = cost(a[i - 2], a[i - 1]);
  39.         min_self(dp[0][i][j], dp[0][i - 1][j] + add);
  40.       }
  41.       if (j > 1) {
  42.         add = cost(b[j - 2], b[j - 1]);
  43.         min_self(dp[1][i][j], dp[1][i][j - 1] + add);
  44.       }
  45.     }
  46.   fout << dp[0][n][m] << '\n';
  47.   fin.close();
  48.   fout.close();
  49.   return 0;
  50. }
  51.  
RAW Paste Data