Submission #787535

#	Time	Username	Problem	Language	Result	Execution time	Memory
787535		That_Salamander	Aliens (IOI16_aliens)	C++17	25 / 100	2079 ms	143156 KiB

aliens

#include <bits/stdc++.h>
#define int long long

#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;

vector<pii> ranges;
int rangeEnds[100000];

int N;
int dp[4005][4005];
int opt[4005][4005];

int solve(int idx, int photosRemaining, int upperBound = N - 1) {
    if (idx == N) return 0;
    if (photosRemaining == 0) return 1e15;
    if (dp[idx][photosRemaining] != -1) return dp[idx][photosRemaining];

    if (rangeEnds[idx] >= ranges[idx].second) {
        cout << "ERROR!" << endl;
    }

    int penalty = rangeEnds[idx] < ranges[idx].first ? 0 : (rangeEnds[idx] - ranges[idx].first+1)*(rangeEnds[idx] - ranges[idx].first+1);
    int res = 1e15;
    int minPos = -1;
    int e = 0;

    for (int i = idx; i <= upperBound; i++) {
        e = max(e, ranges[i].second);
        int s = (e - ranges[idx].first+1)*(e - ranges[idx].first+1) - penalty;
        int score = solve(i + 1, photosRemaining - 1) + s;
        if (score < res) {
            minPos = i;
            res = score;
        }
    }

    opt[idx][photosRemaining] = minPos;
    return dp[idx][photosRemaining] = res;
}

void solveAll(int l, int r, int photosRemaining, int upperBound = N - 1) {
    if (l > r) return;
    if (l == r) {
        solve(l, photosRemaining);
    }

    int m = (l + r) / 2;

    solve(m, photosRemaining, upperBound);

    solveAll(l, m - 1, photosRemaining, opt[m][photosRemaining]);
    solveAll(m + 1, r, photosRemaining, upperBound);
}

int64_t take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
    N = n;
    memset(dp, -1, sizeof(dp));

    vector<pii> rawRanges(n);

    FOR(i, n) {
        rawRanges[i] = {
            min(r[i], c[i]),
            max(r[i], c[i])
        };
    }

    sort(rawRanges.begin(), rawRanges.end());

    int e = -1;
    FOR(i, n) {
        rangeEnds[i] = e;
        e = max(e, rawRanges[i].second);
    }

    FOR(i, n) {
        if (rangeEnds[i] < rawRanges[i].second) {
            ranges.push_back(rawRanges[i]);
        }
    }

    N = ranges.size();

    e = -1;
    FOR(i, N) {
        rangeEnds[i] = e;
        e = max(e, ranges[i].second);
    }

    for (int i = 1; i <= k; i++) {
        solveAll(0, N - 1, i);
    }

    return solve(0, k);
}

#ifdef LOCAL_TEST
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, m, k;
    cin >> n >> m >> k;

    vector<int32_t> r(n), c(n);
    FOR(i, n) {
        cin >> r[i] >> c[i];
    }

    cout << take_photos(n, m, k, r, c) << endl;
}
#endif

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