Submission #773983

#	Time	Username	Problem	Language	Result	Execution time	Memory
773983		Jomnoi	Aliens (IOI16_aliens)	C++17	60 / 100	1092 ms	1048576 KiB

aliens

#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;

const int MAX_N = 1e5 + 5;
const int MAX_M = 1e6 + 5;
const long long INF = 1e18 + 7;

int N, M, K;
long long X[MAX_N], Y[MAX_N];
int minL[MAX_M];

long long divide(long long a, long long b) {
    return a / b - ((a ^ b) < 0 and a % b != 0);
}

struct Line {
    long long m, c;

    long long dot(long long x) {
        return m * x + c;
    }

    long long intersect(const Line &o) {
        return divide(o.c - c, m - o.m);
    }
};

struct ConvexHullTrick {
    deque <Line> dq;

    void addLine(Line f) {
        while (dq.size() >= 2 and dq.back().intersect(f) <= dq[dq.size() - 2].intersect(dq.back())) dq.pop_back();
        dq.push_back(f);
    }

    long long query(long long x) {
        while (dq.size() >= 2 and dq[0].dot(x) <= dq[1].dot(x)) dq.pop_front();
        return dq[0].dot(x);
    }
};

long long take_photos(int n, int m, int k, vector <int> r, vector <int> c) {
    N = n, M = m, K = k;
    for (int i = 0; i < m; i++) minL[i] = M;
    for (int i = 0; i < N; i++) {
        int x = min(r[i], c[i]), y = max(r[i], c[i]);
        minL[y] = min(minL[y], x);
    }

    stack <pair <int, int>> stk;
    for (int i = 0; i < m; i++) {
        if (minL[i] == M) continue;
        while (!stk.empty() and stk.top().first >= minL[i]) stk.pop();
        stk.emplace(minL[i], i);
    }

    N = n = stk.size();
    while (!stk.empty()) {
        auto [x, y] = stk.top();
        stk.pop();

        X[n] = x, Y[n] = y;
        n--;
    }

    X[N + 1] = Y[N + 1] = M;
    
    vector <vector <long long>> dp(K + 1, vector <long long>(N + 1, INF));
    dp[0][0] = 0;
    for (int k = 1; k <= K; k++) {
        ConvexHullTrick cht;
        for (int i = 1; i <= N; i++) {
            long long overlap = 1ll * max(0ll, Y[i] - X[i + 1] + 1) * max(0ll, Y[i] - X[i + 1] + 1);

            cht.addLine({2 * X[i], -X[i] * X[i] - dp[k - 1][i - 1]});
            dp[k][i] = -overlap + (Y[i] + 1) * (Y[i] + 1) - cht.query((Y[i] + 1));
        }
    }

    long long ans = INF;
    for (int k = 1; k <= K; k++) ans = min(ans, dp[k][N]);
    return ans;
}

• Subtask 1: 4 / 4
• Subtask 2: 12 / 12
• Subtask 3: 9 / 9
• Subtask 4: 16 / 16
• Subtask 5: 19 / 19
• Subtask 6: 0 / 40