제출 #393082

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
393082		Tc14	Aliens (IOI16_aliens)	C++17	60 / 100	2085 ms	361380 KiB

aliens

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define ve vector
typedef long long ll;
typedef pair<int, int> pii;
const int INF = 1e9 + 10;
const ll LLINF = (ll)1e18 + 10;

struct segment {
    ll m, b, l, r;
};

double intersect(ll m1, ll m2, ll b1, ll b2) {
    return (double) (b1 - b2) / (double) (m2 - m1);
}

ll sq(int x) { return (ll)x*x; }

ll take_photos(int n, int m, int k, ve<int> R, ve<int> C) {

    map<int, int> M;
    ve<pii> P;

    for (int i = 0; i < n; i++) {
        int r = R[i];
        int c = C[i];
        if (c < r) swap(r, c);
        if (M.find(r) == M.end()) M[r] = c;
        else M[r] = max(M[r], c);
    }

    int cOld = -1;
    n = 0;
    for (pii p : M) {
        int r, c;
        tie(r, c) = p;
        if (c > cOld) {
            cOld = c;
            P.push_back({r, c});
            n++;
        }
    }

    ve<ll> L(n);
    for (int i = 1; i < n; i++) {
        if (P[i - 1].second >= P[i].first) {
            L[i] = sq(P[i - 1].second - P[i].first + 1);
        }
    }

    ve<ve<ll>> DP(k + 1, ve<ll>(n));
    for (int i = 0; i < n; i++) {
        DP[1][i] = sq(P[i].second - P[0].first + 1);
    }

    for (int i = 2; i <= k; i++) {

        list<segment> H;
        for (int j = i - 1; j < n; j++) {
            
            ll x = -P[j].first + 1;
            ll b = DP[i - 1][j - 1] - L[j] + x * x;
            ll m = 2 * x;

            while (H.size() > 0 && intersect(H.back().m, m, H.back().b, b) < (double)H.back().l) {
                H.pop_back();
            }

            ll l = -LLINF;
            if (H.size() > 0) {
                double z = intersect(H.back().m, m, H.back().b, b);
                l = (ll)ceil(z);
                H.back().r = (ll)floor(z);
            }

            H.push_back({m, b, l, LLINF});

            while (H.begin()->r < P[j].second) {
                H.pop_front();
            }

            ll q = H.begin()->m * P[j].second + H.begin()->b;

            DP[i][j] = q + sq(P[j].second);
        }
    }

    return DP[min(k, n)][n - 1];
}

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