Submission #1199304

#	Time	Username	Problem	Language	Result	Execution time	Memory
1199304		woohyun_jng	Aliens (IOI16_aliens)	C++20	100 / 100	90 ms	12464 KiB

aliens

#include <bits/stdc++.h>
#define int long long

const int MAX = 500001;

using namespace std;

typedef array<int, 2> pr;
typedef array<int, 4> ftp;

int dp[MAX][2], X[MAX], Y[MAX];

int sq(int V) { return V * V; }

int take_photos(signed N, signed M, signed K, vector<signed> R, vector<signed> C) {
    vector<pr> arr, stck;

    for (int i = 0; i < N; i++) {
        if (R[i] > C[i])
            swap(R[i], C[i]);
        arr.push_back({R[i], C[i]});
    }

    sort(arr.begin(), arr.end());

    for (pr i : arr) {
        while (!stck.empty() && stck.back()[0] == i[0])
            stck.pop_back();
        if (stck.empty() || stck.back()[1] < i[1])
            stck.push_back(i);
    }
    arr = stck, stck.clear(), N = arr.size();

    for (int i = 0; i < N; i++)
        X[i + 1] = arr[i][0], Y[i + 1] = arr[i][1];

    int st = 0, en = 4e12, md, ans = 0, P;
    vector<ftp> F;
    ftp fnc;

    while (st <= en) {
        md = st + en >> 1, F.clear(), P = 0;
        F.push_back({-2 * X[1] + 2, sq(X[1] - 1), 0, 0});

        for (int i = 1; i <= N; i++) {
            while (P + 1 < F.size() && F[P + 1][2] < Y[i])
                P++;
            dp[i][0] = F[P][0] * Y[i] + F[P][1] + sq(Y[i]) + md, dp[i][1] = F[P][3] + 1;

            if (i == N)
                break;

            fnc = {-2 * X[i + 1] + 2, sq(X[i + 1] - 1) - sq(max(0ll, Y[i] - X[i + 1] + 1)) + dp[i][0], 0, dp[i][1]};
            while (!F.empty()) {
                fnc[2] = (F.back()[1] - fnc[1]) / (fnc[0] - F.back()[0]);
                if (F.back()[2] < fnc[2])
                    break;
                F.pop_back();
                if (F.size() == P)
                    --P;
            }
            F.push_back(fnc);
        }

        ans = max(ans, dp[N][0] - md * K);
        if (dp[N][1] <= K)
            en = md - 1;
        else
            st = md + 1;
    }

    return ans;
}

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: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 40 / 40