Submission #873257

#	Time	Username	Problem	Language	Result	Execution time	Memory
873257		Turkhuu	Aliens (IOI16_aliens)	C++17	25 / 100	337 ms	94548 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll sq(int x) {
    return (ll)x * x;
}
ll take_photos(int M, int N, int K, vector<int> R, vector<int> C) {
    vector<vector<int>> v(N);
    for (int i = 0; i < M; i++) {
        v[max(R[i], C[i])].push_back(min(R[i], C[i]));
    }
    vector<pair<int, int>> h;
    vector dp(N, vector<ll>(K + 1, 1e9));
    for (int i = 0; i < N; i++) {
        if (v[i].empty()) {
            dp[i] = !i ? vector<ll>(K + 1, 0) : dp[i - 1];
            continue;
        }
        for (int j : v[i]) h.emplace_back(j, i);
        sort(h.begin(), h.end());
        int t = -1;
        for (auto [y, x] : h) {
            for (int k = 1; k <= K; k++) {
                if (t == -1) {
                    dp[i][k] = min(dp[i][k], sq(i - y + 1));
                } else {
                    dp[i][k] = min(dp[i][k], dp[t][k - 1] + sq(i - y + 1) - (t < y ? 0 : sq(t - y + 1)));
                }
            }
            t = max(t, x);
            if (x == i) break;
        }
    }
    return *min_element(dp[N - 1].begin(), dp[N - 1].end());
}

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