Submission #1206866

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

aliens

#include "aliens.h"
#include <vector>
#include <algorithm>
#include <limits>

long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
    using ll = long long;
    const ll INF = (ll)1e18;

    std::vector<std::pair<int,int>> pts(n);
    for (int i = 0; i < n; ++i)
        pts[i] = { std::min(r[i], c[i]), std::max(r[i], c[i]) };
    std::sort(pts.begin(), pts.end());

    std::vector<ll> A(n+1), B(n+1);
    for (int i = 1; i <= n; ++i) {
        A[i] = pts[i-1].first;
        B[i] = pts[i-1].second;
    }

    std::vector<ll> seg(4*(n+1), -INF);
    auto build = [&](auto&& self, int idx, int L, int R)->void{
        if (L == R) seg[idx] = B[L];
        else {
            int M = (L+R)/2;
            self(self, idx*2, L, M);
            self(self, idx*2+1, M+1, R);
            seg[idx] = std::max(seg[idx*2], seg[idx*2+1]);
        }
    };
    build(build, 1, 1, n);

    auto query = [&](auto&& self, int idx, int L, int R, int ql, int qr)->ll {
        if (qr < L || R < ql) return -INF;
        if (ql <= L && R <= qr) return seg[idx];
        int M = (L+R)/2;
        return std::max(
            self(self, idx*2,    L,   M, ql, qr),
            self(self, idx*2+1,  M+1,  R, ql, qr)
        );
    };

    std::vector<ll> dp(n+1), best(n+1);
    std::vector<int> cnt(n+1), bestCnt(n+1);
    ll lambda = 0;

    auto solveDC = [&](auto&& self, int L, int R, int optL, int optR)->void {
        if (L > R) return;
        int mid = (L+R)/2;
        ll bestVal = INF; int bestK=-1, bestSeg=0;
        int ub = std::min(optR, mid-1);
        for (int j = optL; j <= ub; ++j) {
            ll mx = query(query,1,1,n,j+1,mid);
            ll len = mx - A[j+1] + 1;
            ll cost = len*len + lambda;
            ll cand = dp[j] + cost;
            int segs = cnt[j] + 1;
            if (cand < bestVal || (cand==bestVal && segs<bestSeg)) {
                bestVal = cand;
                bestSeg = segs;
                bestK = j;
            }
        }
        best[mid] = bestVal;
        bestCnt[mid] = bestSeg;
        self(self, L,    mid-1, optL, bestK);
        self(self, mid+1,R,     bestK, optR);
    };

    auto runWith = [&](ll lam)->std::pair<ll,int> {
        lambda = lam;
        std::fill(dp.begin(), dp.end(), INF);
        std::fill(cnt.begin(), cnt.end(), 0);
        dp[0]=0; cnt[0]=0;
        solveDC(solveDC, 1, n, 0, n-1);
        return { best[n], bestCnt[n] };
    };

    ll lo = 0, hi = 4LL*m*m + 10;
    while (lo < hi) {
        ll mid = (lo+hi)/2;
        auto [val, used] = runWith(mid);
        if (used > k) lo = mid + 1;
        else hi = mid;
    }
    auto [finalVal, finalUsed] = runWith(lo);
    return finalVal - lo * finalUsed;
}

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