IOI '04 P1 - Artemis (85pts - TLE)

Jul 21st, 2022
577
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <iostream>
2. #include <vector>
3. #include <algorithm>
4.
5. using namespace std;
6.
7. const int MX = 2001;
8. const int INF = 1e8;
9.
10. struct Point {
11.     int x, y;
12. };
13. int vertical[2][MX], horizontal[2][MX]; // vertical and horizontal
14. /* v[y] = min moves to deliver all messages in current prefix and end up at point with y coordinate
15. at y and x coordinate being the same as x of last point in prefix. Vice versa with h[x] */
16.
17. const int startX = 1000, startY = 1000;
18.
19. int main() {
20.     int n; cin >> n;
21.     vector<Point> points(n);
22.     for (Point &p : points) {
23.         cin >> p.x >> p.y;
24.         p.x += startX, p.y += startY;
25.     }
26.     points.insert(points.begin(), {startX, startY});
27.     for (int i = 0; i < MX; ++i) vertical[0][i] = horizontal[0][i] = INF;
28.     vertical[0][startY] = horizontal[0][startX] = 0;
29.
30.     for (int i = 1; i <= n; ++i) {
31.         Point p1 = points[i-1], p = points[i];
32.         int *v1 = vertical[(i-1)&1], *h1 = horizontal[(i-1)&1]; // previous dp states
33.         int *v = vertical[i&1], *h = horizontal[i&1]; // next dp states
34.         for (int j = 0; j < MX; ++j) v[j] = h[j] = INF;
35.
36.         // calculate h
37.         for (int x = 0; x < MX; ++x) {
38.             if (x == p.x) continue;
39.             if (x == p1.x) {
40.                 for (int y = 0; y < MX; ++y) {
41.                     h[x] = min(h[x], v1[y] + abs(p.y-y));
42.                 }
43.             } else {
44.                 h[x] = h1[x] + abs(p.y-p1.y);
45.             }
46.         }
47.
48.         // calculate v
49.         for (int y = 0; y < MX; ++y) {
50.             if (y == p.y) continue;
51.             if (y == p1.y) {
52.                 for (int x = 0; x < MX; ++x) {
53.                     v[y] = min(v[y], h1[x] + abs(p.x-x));
54.                 }
55.             } else {
56.                 v[y] = v1[y] + abs(p.x-p1.x);
57.             }
58.         }
59.
60.         // calculate for the point itself
61.         if (p.y == p1.y) h[p.x] = v[p.y] = h1[p.x];
62.         else if (p.x == p1.x) h[p.x] = v[p.y] = v1[p.y];
63.     }
64.
65.     int *v = vertical[n&1], *h = horizontal[n&1];
66.     cout << min(*min_element(v, v+MX), *min_element(h, h+MX)) << endl;
67.     return 0;
68. }