# 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) {
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