제출 #1199239

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

aliens

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

const int MAX = 500001;
const int INF = 0x3f3f3f3f3f3f3f3f;

using namespace std;

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

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

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

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 = M * M, md, ans = INF, P = 0;
    vector<ftp> F;
    ftp fnc;

    while (st <= en) {
        md = st + en >> 1, F.clear(), P = 0;
        F.push_back({-2 * X[1], 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] = (2 + 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], 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 = min(ans, dp[N][0] + md * K);
        if (dp[N][1] <= K)
            en = md - 1;
        else
            st = md + 1;
    }

    return ans;
}

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