Submission #1227550

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227550		madamadam3	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	328 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;

const ll INF = 1e18;

int n, m, k;
vi r, c, L, R;

void preprocess(int N, int M, int K, vi Row, vi Col) {
    set<int> points; for (int i = 0; i < N; i++) points.insert(i);
    vector<int> to_erase;

    for (int i = 0; i < N; i++) {
        if (!points.count(i)) continue;

        int Li = min(Row[i], Col[i]), Ri = max(Row[i], Col[i]);
        for (auto &el : points) {
            if (i == el) continue;
            if (Li <= Col[el] && Col[el] <= Ri && Li <= Row[el] && Row[el] <= Ri) {
                to_erase.push_back(el);
            }
        }

        for (auto &el : to_erase) {
            points.erase(el);
        }

        to_erase.clear();
    }

    vector<int> sorted_points(points.begin(), points.end());
    sort(sorted_points.begin(), sorted_points.end(), [&](int a, int b) {
        int La = min(Row[a], Col[a]), Ra = max(Row[a], Col[a]), Lb = min(Row[b], Col[b]), Rb = max(Row[b], Col[b]);
        return La == Lb ? Ra < Rb : La < Lb;
    });

    n = points.size(); m = M; k = K;
    r.resize(n); c.resize(n); L.resize(n); R.resize(n);
    for (int i = 0; i < n; i++) {
        r[i] = Row[sorted_points[i]]; c[i] = Col[sorted_points[i]];

        L[i] = min(r[i], c[i]);
        R[i] = max(r[i], c[i]);
    }
}

// n <= 50, m <= 100
ll sub1() {
    vvi used(m, vi(m, 0));
    for (int i = 0; i < n; i++) {
        for (int x = L[i]; x <= R[i]; x++) {
            for (int y = L[i]; y <= R[i]; y++) {
                used[x][y]++;
            }
        }
    }

    ll ans = 0;
    for (int x = 0; x < m; x++) {
        for (int y = 0; y < m; y++) {
            if (used[x][y]) ans++;
        }
    }
    return ans;
}

// n <= 500, m <= 1000, r[i] = c[i]
// essentially DP[i][k] = min cost to cover first i using k
// DP[i][k] = min(DP[j[k-1] + (r[i] - r[j+1] + 1)^2)
ll sub2() {
    vvl DP(n, vl(k+1, INF)); DP[0][0] = 1;
    ll ans = INF;

    for (int kv = 1; kv <= k; kv++) {
        DP[0][kv] = 1;
        for (int i = 1; i < n; i++) {
            DP[i][kv] = DP[i-1][kv-1] + 1; 
            for (int j = 0; j < i; j++) {
                ll prev = j == 0 ? 0 : DP[j-1][kv-1];
                ll delta = (c[i] - c[j] + 1);
                delta *= delta; 

                DP[i][kv] = min(DP[i][kv], prev + delta);
            }
        }

        ans = min(ans, DP[n-1][kv]);
    }

    return ans;
}

ll take_photos(int N, int M, int K, vi Row, vi Col) {
    preprocess(N, M, K, Row, Col);

    // return sub1();
    return sub2();
}

Compilation message (stderr)

aliens.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
aliens_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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