Submission #663352

#	Time	Username	Problem	Language	Result	Execution time	Memory
663352		amsraman	Aliens (IOI16_aliens)	C++14	4 / 100	2 ms	336 KiB

aliens

#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;

using namespace std;

const ld eps = 1e-9;

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
    vector<pair<int, int>> pts_uf, pts; // unfiltered, filtered
    for(int i = 0; i < n; i++) {
        if(r[i] > c[i]) swap(r[i], c[i]);
        pts_uf.push_back({r[i], c[i] + 1});
    }
    sort(pts_uf.begin(), pts_uf.end());
    for(int i = 0; i < n; i++) {
        while(!pts.empty() && (pts.back().first == pts_uf[i].first)) {
            pts.pop_back();
        }
        if(pts.empty() || pts.back().second < pts_uf[i].second) {
            pts.push_back(pts_uf[i]);
        }
    }
    n = pts.size();
    auto isect = [](pair<ld, pair<ld, int>> l1, pair<ld, pair<ld, int>> l2) {
        return (l2.second.first - l1.second.first) / (l2.first - l1.first);
    };
    auto try_penalty = [&](ld penalty) { // CHT
        vector<pair<ld, int>> dp(n + 1);
        deque<pair<ld, pair<ld, int>>> hull;
        dp[0] = {0, 0};
        hull.push_back({-2.0 * pts[0].first, {(ld) pts[0].first * pts[0].first, 0}});
        for(int i = 1; i <= n; i++) {
            while(hull.size() > 1 && isect(hull[0], hull[1]) < pts[i - 1].first) {
                hull.pop_front();
            }
            dp[i] = {hull[0].first * pts[i - 1].second + hull[0].second.first, hull[0].second.second};
            dp[i].first += (ld) pts[i - 1].second * pts[i - 1].second;
            dp[i].first -= penalty, dp[i].second++;
            if(i < n) { // insert line
                pair<ld, pair<ld, int>> to_add = {-2 * pts[i].first, dp[i]};
                ld df = max(0, pts[i - 1].second - pts[i].first);
                to_add.second.first += (ld) pts[i].first * pts[i].first - df * df;
                while(hull.size() > 1 && isect(hull[hull.size() - 2], hull[hull.size() - 1]) > isect(hull[hull.size() - 2], to_add)) {
                    hull.pop_back();
                }
                hull.push_back(to_add);
            }
        }
        return dp[n];
    };
    ld lb = 0, ub = 1e12;
    for(int it = 0; it < 400; it++) {
        ld mid = (lb + ub) / 2;
        pair<ld, int> res = try_penalty(mid);
        if(res.second <= k) {
            ub = mid;
        } else {
            lb = mid;
        }
    }
    pair<ld, int> res = try_penalty(ub);
    return (ll) (res.first + (res.second + eps) * ub);
}

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