Submission #1037587

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037587		yanb	Aliens (IOI16_aliens)	C++14	0 / 100	0 ms	440 KiB

aliens

#include <bits/stdc++.h>
    
using namespace std;
    
#define int long long
#define pii pair<long long, long long>

struct Pt {
    int x, y;

    bool operator<(const Pt &p) const {
        if (x + y == p.x + p.y) return x < p.x;
        return x + y < p.x + p.y;
    }
};

int take_photos(signed pts, signed sz, signed k, vector<signed> x, vector<signed> y) {
    for (int i = 0; i < pts; i++) {
        if (x[i] < y[i]) swap(x[i], y[i]);
    }

    vector<Pt> a(pts);
    for (int i = 0; i < pts; i++) a[i].x = x[i], a[i].y = y[i];

    vector<vector<int>> dp(k + 1, vector<int>(pts + 1, 1e9));
    dp[0][0] = 0;
    for (int conn = 0; conn < k; conn++) {
        for (int pt1 = 0; pt1 <= pts; pt1++) {
            dp[conn + 1][pt1] = min(dp[conn + 1][pt1], dp[conn][pt1]);
            int mxx = -1e9, mny = 1e9;
            for (int pt2 = pt1 + 1; pt2 <= pts; pt2++) {
                mxx = max(mxx, a[pt2 - 1].x);
                mny = min(mny, a[pt2 - 1].y);
                dp[conn + 1][pt2] = min(dp[conn + 1][pt2], dp[conn][pt1] + (mxx - mny + 1) * (mxx - mny + 1));
            }
        }
    }

    return dp[k][pts];
}

#ifdef LOCAL
signed main() {
    cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << "\n";
    cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << "\n";
}
#endif

• Subtask 1: 0 / 4
• Subtask 2: 0 / 12
• Subtask 3: 0 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40