Submission #1227726

#	Time	Username	Problem	Language	Result	Execution time	Memory
1227726		madamadam3	Aliens (IOI16_aliens)	C++20	4 / 100	4 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;
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;
}

// solve sub4 using wqs binary search
// for a given λ, DP[i] = minimum cost to cover up to i, if splitting costs λ 
// cnt[i] = number of separate squares used

ll area(int left, int right) {
    ll width = (R[right] - L[left] + 1);
    return width * width;
}

void compute_dp(ll lambda, vl &DP, vl &cnt, vl &overlap) {
    DP[0] = area(0, 0) + lambda; cnt[0] = 1;

    for (int i = 1; i < n; i++) {
        DP[i] = DP[i-1] + area(i, i) - overlap[i] + lambda;
        cnt[i] = cnt[i-1] + 1;

        for (int j = 0; j < i; j++) {
            ll prev = j == 0 ? 0 : DP[j-1];
            ll delta = area(j, i);
            ll v = prev + delta - overlap[j] + lambda;

            if (v < DP[i]) {
                DP[i] = v;
                cnt[i] = j == 0 ? 1 : cnt[j-1] + 1;
            }
        }
    }
}

ll sub4() {
    vl overlap(n, 0);
    for (int i = 1; i < n; i++) {
        ll over = max(0LL, R[i-1] - L[i] + 1);
        over *= over;

        overlap[i] = over;
    }

    ll lo = 0, hi = 1e13;

    while (lo < hi) {
        ll lambda = lo + (hi - lo) / 2;
        
        vl DP(n, INF), cnt(n, 0);
        compute_dp(lambda, DP, cnt, overlap);

        if (cnt[n - 1] > k) {
            lo = lambda + 1;
        } else {
            hi = lambda;
        }
    }

    vl DP(n, INF), cnt(n, 0);
    compute_dp(lo, DP, cnt, overlap);

    return DP[n-1] - 1LL * lo * k;
}

// 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
*/

// functions of the form f(x) = x^2 + bx + c
struct Function {
    ll a, b, c;

    Function() : b(0), c(INF) {};
    Function(ll B, ll C) : b(B), c(C) {};

    ll evaluate(ll x) {
        return x*x + b*x + c;
    }
};

struct Node {
    Function best;
    Node *left, *right;

    Node() : best(Function()), left(nullptr), right(nullptr) {};
    Node(Function Best) : best(Best), left(nullptr), right(nullptr) {};
};

// implicit segtree storing minimum function at x for x in [0, 1m]
struct LiChaoTree {
    int lower, upper;
    Node* root;

    LiChaoTree() {};
    LiChaoTree(int L, int U) {
        lower = L;
        upper = U;

        root = new Node();
    }

    Node* update(Node* cur, int l, int r, Function fnew) {
        if (!cur) cur = new Node();
        
        int m = l + (r - l) / 2;
        if (fnew.evaluate(m) < cur->best.evaluate(m)) swap(cur->best, fnew);

        if (fnew.evaluate(l) < cur->best.evaluate(l)) cur->left = update(cur->left, l, m, fnew);
        else if (fnew.evaluate(r) < cur->best.evaluate(r)) cur->right = update(cur->right, m, r, fnew);

        return cur;
    }

    ll query(Node* cur, int l, int r, ll x) {
        if (!cur) return INF;
        if (l + 1 == r) return cur->best.evaluate(x);

        int m = l + (r - l) / 2;
        if (x < m) return min(cur->best.evaluate(x), query(cur->left, l, m, x));
        else return min(cur->best.evaluate(x), query(cur->right, m, r, x));
    }

    void update(Function fnew) {
        update(root, lower, upper+1, fnew);
    }

    ll query(ll x) {
        return query(root, lower, upper+1, x);
    }
};

ll sub45() { // solves 4 & 5 using cht
    vl overlap(n, 0);
    for (int i = 1; i < n; i++) {
        ll over = max(0LL, R[i-1] - L[i] + 1);
        over *= over;

        overlap[i] = over;
    }

    vl prev_dp(n, INF), cur_dp(n, INF);
    for (int i = 0; i < n; i++) {
        prev_dp[i] = (R[i] - L[0] + 1) * (R[i] - L[0] + 1);
    }

    for (int kv = 2; kv <= k; ++kv) {
        cur_dp.assign(n, INF);
        LiChaoTree lct(0, m);       

        ll L0 = L[0] - 1;
        lct.update(Function(-2*L0, L0*L0));  
        cur_dp[0] = (R[0] - L[0] + 1) * 1LL * (R[0] - L[0] + 1);

        for (int i = 1; i < n; ++i) {
            ll Lj = L[i] - 1;
            ll B = -2 * Lj;
            ll C = prev_dp[i-1] + Lj*Lj - overlap[i];
            lct.update(Function(B, C));

            cur_dp[i] = lct.query(R[i]);
        }

        prev_dp.swap(cur_dp);
    }

    return prev_dp.back();
}

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();
    return sub4();
    // return sub45();
}

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