Submission #1227645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227645		madamadam3	Aliens (IOI16_aliens)	C++20	25 / 100	2093 ms	22344 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;
vl r, c, L, R;

void preprocess(int N, int M, int K, vi Row, vi Col) {
    vector<int> sorted_points(N); iota(sorted_points.begin(), sorted_points.end(), 0);
    sort(sorted_points.begin(), sorted_points.end(), [&](int a, int b) {
        ll 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;
    });

    vector<int> points; int lastR = -1;
    for (int i = 0; i < N; i++) {
        int cur = sorted_points[i];
        int rcur = max(Row[cur], Col[cur]);
        if (rcur > lastR) {
            points.push_back(cur);
            lastR = rcur;
        }
    }

    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[points[i]]; c[i] = Col[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));
    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;
}

// n <= 500, m <= 1000
// same dp but we need to account for the squares, as well as overlap between them
ll sub3() {
    vvl DP(n, vl(k+1, INF));
    ll ans = INF;

    for (int kv = 1; kv <= k; kv++) {
        DP[0][kv] = (R[0] - L[0] + 1) * (R[0] - L[0] + 1);
        for (int i = 1; i < n; i++) {
            ll width = (R[i] - L[i] + 1), overlap_width = (R[i-1] - L[i] + 1);
            ll wd = width*width, owd = overlap_width > 0 ? overlap_width*overlap_width : 0;
            
            DP[i][kv] = DP[i-1][kv-1] + wd - owd; 

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

                ll delta = (R[i] - L[j] + 1);
                delta *= delta; 

                ll overlap = 0;
                if (j > 0 && R[j-1] - L[j] + 1 > 0) {
                    overlap = (R[j-1] - L[j] + 1);
                    overlap *= overlap;
                }

                if (prev + delta - overlap < DP[i][kv]) {
                    DP[i][kv] = prev + delta - overlap;
                }
            }
        }

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

    return ans;
}

// n <= 4000, m <= 1m
/*
    let P = prev
    let O = max(0, R[j-1] - L[j] + 1)^2
    let L = L[j]-1
    let R = R[i]
    f(x) = (R-L)^2 + P + O
            = R^2 - 2LR + L^2 + P + O
    let C = L^2 + P + O
    ∴ f(x) = R^2 - 2LR + C
    so we can do a cht/li chao tree
*/

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

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

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: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 0 / 16
• Subtask 5: 0 / 19
• Subtask 6: 0 / 40