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

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

const int MX = 2001;
const int INF = 1e8;

struct Point {
    int x, y;
};
int vertical[2][MX], horizontal[2][MX]; // vertical and horizontal
/* v[y] = min moves to deliver all messages in current prefix and end up at point with y coordinate
at y and x coordinate being the same as x of last point in prefix. Vice versa with h[x] */

const int startX = 1000, startY = 1000;

int main() {
    int n; cin >> n;
    vector<Point> points(n);
    for (Point &p : points) {
        cin >> p.x >> p.y;
        p.x += startX, p.y += startY;
    }
    points.insert(points.begin(), {startX, startY});
    for (int i = 0; i < MX; ++i) vertical[0][i] = horizontal[0][i] = INF;
    vertical[0][startY] = horizontal[0][startX] = 0;

    for (int i = 1; i <= n; ++i) {
        Point p1 = points[i-1], p = points[i];
        int *v1 = vertical[(i-1)&1], *h1 = horizontal[(i-1)&1]; // previous dp states
        int *v = vertical[i&1], *h = horizontal[i&1]; // next dp states
        for (int j = 0; j < MX; ++j) v[j] = h[j] = INF;

        // calculate h
        for (int x = 0; x < MX; ++x) {
            if (x == p.x) continue;
            if (x == p1.x) {
                for (int y = 0; y < MX; ++y) {
                    h[x] = min(h[x], v1[y] + abs(p.y-y));
                }
            } else {
                h[x] = h1[x] + abs(p.y-p1.y);
            }
        }

        // calculate v
        for (int y = 0; y < MX; ++y) {
            if (y == p.y) continue;
            if (y == p1.y) {
                for (int x = 0; x < MX; ++x) {
                    v[y] = min(v[y], h1[x] + abs(p.x-x));
                }
            } else {
                v[y] = v1[y] + abs(p.x-p1.x);
            }
        }

        // calculate for the point itself
        if (p.y == p1.y) h[p.x] = v[p.y] = h1[p.x];
        else if (p.x == p1.x) h[p.x] = v[p.y] = v1[p.y];
    }

    int *v = vertical[n&1], *h = horizontal[n&1];
    cout << min(*min_element(v, v+MX), *min_element(h, h+MX)) << endl;
    return 0;
}