제출 #1009976

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009976		phoenix	Aliens (IOI16_aliens)	C++17	4 / 100	1 ms	348 KiB

aliens

#include "aliens.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll INF = 1e12;

struct CHT {
    struct line {
        ll a, b, i;
        ll f(ll x) { return a * x + b; };        
    };
    ll intersect(line f1, line f2) {
        assert(f1.a != f2.a);
        return ceil(((double)f2.b - f1.b) / ((double)f1.a - f2.a));
    }
    vector<line> st;
    vector<ll> p;

    void insert(line t) {
        if (st.empty()) {
            st.push_back(t);
            p.push_back(-INF);
            return;
        }
        while (!st.empty() && intersect(st.back(), t) <= p.back()) {
            p.pop_back();
            st.pop_back();
        }
        p.push_back(intersect(st.back(), t));
        st.push_back(t);
    }
    int opt = 0;
    // for every 0 <= i < q x[i] < x[i+1]
    line query(ll x) {
        int l = 0, r = (int)st.size();
        while (r - l > 1) {
            int mid = (l + r) / 2;
            if (p[mid] <= x) l = mid;
            else r = mid;
        }
        return st[l];
    }
};

template<typename T1, typename T2>
pair<T1, T2> operator + (pair<T1, T2> a, pair<T1, T2> b) {
    return make_pair(a.first + b.first, a.second + b.second);
};

int n;
vector<long long> l;
vector<long long> r;

pair<long long, int> func(long long lambda) {
    vector<pair<ll, int>> dp(n + 1);
    vector<ll> t(n);
    for (int i = 0; i < n; i++) 
        t[i] = max(0ll, r[i] - l[i + 1] + 1) 
            * max(0ll, r[i] - l[i + 1] + 1);
    
    CHT convex;
    for (int i = 1; i <= n; i++) {
        ll a = (-2) * (l[i] - 1);
        ll b = (l[i] - 1) * (l[i] - 1) - t[i - 1] + dp[i - 1].first + lambda;
        convex.insert({a, b, i});
        auto t = convex.query(r[i]);
        dp[i] = {t.f(r[i]) + r[i] * r[i], dp[t.i].second + 1};
    }
    return dp[n];
}

long long take_photos(int _n, int m, int k, vector<int> _r, vector<int> _c) {
    n = _n;
    for (int i = 0; i < n; i++) 
        if (_r[i] > _c[i]) swap(_r[i], _c[i]);
    
    vector<int> ord(n);
    iota(ord.begin(), ord.end(), 0);
    sort(ord.begin(), ord.end(), [&](int a, int b) {
        if (_r[a] == _r[b]) return _c[a] > _c[b]; 
        return _r[a] < _r[b];
    });

    l.push_back(-1);
    r.push_back(-1);
    for (int cur : ord) {
        if (r.empty() || r.back() < _c[cur]) {
            l.push_back(_r[cur]);
            r.push_back(_c[cur]);
        }
    }
    n = (int)l.size() - 1;

    long long lb = -1, rb = 1e13;
    while (rb - lb > 1) {
        long long mid = (lb + rb) / 2;
        if (func(mid).second <= k) 
            rb = mid;
        else
            lb = mid;
    }
    return func(rb).first - func(rb).second * rb;
    // vector<ll> dp(n + 1, INF);
    // vector<ll> t(n + 1);
    // for (int i = 0; i < n; i++) 
    //     t[i] = max(0ll, r[i] - l[i + 1] + 1) 
    //         * max(0ll, r[i] - l[i + 1] + 1);
    
    // dp[0] = 0;
    // ll ans = INF;
    // for (int iter = 1; iter <= k; iter++) {
    //     CHT convex;
    //     vector<ll> newdp(n + 1, INF);
    //     for (int i = 1; i <= n; i++) {
    //         ll a = (-2) * (l[i] - 1);
    //         ll b = (l[i] - 1) * (l[i] - 1) - t[i - 1] + dp[i - 1];
    //         convex.insert({a, b, i});
    //         newdp[i] = convex.query(r[i]).f(r[i]) + r[i] * r[i];
    //     }
    //     dp = newdp;
    //     ans = min(ans, dp[n]);
    // }
    // return ans;
}

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