제출 #1206859

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206859		catling	Aliens (IOI16_aliens)	C++20	0 / 100	0 ms	328 KiB

aliens

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

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

    int N = n;
    vector<pair<int,int>> pointsArray(N);
    for (int i = 0; i < N; i++) {
        int A = min(r[i], c[i]);
        int B = max(r[i], c[i]);
        pointsArray[i] = {A, B};
    }
    sort(pointsArray.begin(), pointsArray.end());

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

    vector<ll> segmentTree(4 * (N + 1), -INF);
    function<void(int, int, int)> buildTree = [&](int idx, int L, int R) {
        if (L == R) {
            segmentTree[idx] = B[L];
        } else {
            int M = (L + R) / 2;
            buildTree(2 * idx, L, M);
            buildTree(2 * idx + 1, M + 1, R);
            segmentTree[idx] = max(segmentTree[2 * idx], segmentTree[2 * idx + 1]);
        }
    };
    buildTree(1, 1, N);

    function<ll(int, int, int, int, int)> queryMax = [&](int idx, int L, int R, int l, int r) -> ll {
        if (r < L || R < l) return -INF;
        if (l <= L && R <= r) return segmentTree[idx];
        int M = (L + R) / 2;
        return max(queryMax(2 * idx, L, M, l, r), queryMax(2 * idx + 1, M + 1, R, l, r));
    };

    vector<ll> valueDP(N + 1);
    vector<int> segmentsDP(N + 1);
    ll lambdaPenalty;

    function<void(int, int, int, int)> divideSolve = [&](int L, int R, int optL, int optR) {
        if (L > R) return;
        int mid = (L + R) / 2;
        ll bestVal = INF;
        int bestK = -1, bestSeg = 0;
        int ub = min(optR, mid - 1);
        for (int j = optL; j <= ub; ++j) {
            ll maxVal = queryMax(1, 1, N, j + 1, mid);
            ll len = maxVal - A[j + 1] + 1;
            ll cost = len * len + lambdaPenalty;
            ll candidate = valueDP[j] + cost;
            int segs = segmentsDP[j] + 1;
            if (candidate < bestVal || (candidate == bestVal && segs < bestSeg)) {
                bestVal = candidate;
                bestSeg = segs;
                bestK = j;
            }
        }
        valueDP[mid] = bestVal;
        segmentsDP[mid] = bestSeg;
        divideSolve(L, mid - 1, optL, bestK);
        divideSolve(mid + 1, R, bestK, optR);
    };

    auto runLambda = [&](ll lam) -> pair<ll, int> {
        lambdaPenalty = lam;
        fill(valueDP.begin(), valueDP.end(), INF);
        fill(segmentsDP.begin(), segmentsDP.end(), 0);
        valueDP[0] = 0;
        divideSolve(1, N, 0, N - 1);
        return {valueDP[N], segmentsDP[N]};
    };

    ll L = 0, R = 4LL * m * m + 10;
    while (L < R) {
        ll mid = (L + R) / 2;
        auto [cost, segs] = runLambda(mid);
        if (segs > k) {
            L = mid + 1;
        } else {
            R = mid;
        }
    }

    auto [finalVal, usedSegments] = runLambda(L);
    return finalVal - L * usedSegments;
}

컴파일 시 표준 에러 (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