Submission #655709

#	Time	Username	Problem	Language	Result	Execution time	Memory
655709		benjaminkleyn	Aliens (IOI16_aliens)	C++17	0 / 100	1 ms	212 KiB

aliens

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

#define COL first
#define ROW second

vector<pair<ll,ll>> pts, dp;
pair<ll,ll> eval(int i, int j, ll cost)
{
    ll new_square = (pts[i].COL - pts[j+1].ROW);
    ll overlap = max(pts[j].COL - pts[j+1].ROW, 0LL);
    ll total_area = new_square * new_square - overlap * overlap;

    return {dp[j].first + total_area + cost, dp[j].second + 1};
}

pair<ll,ll> calc(int n, ll cost)
{
    deque<int> cht;
    dp[0] = {0, 0};
    for (int i = 1; i <= n; i++)
    {
        dp[i] = {LLONG_MAX, LLONG_MAX};
        for (int j = 0; j < i; j++)
            dp[i] = min(dp[i], eval(i, j, cost));
    }

    return dp[n];
}

ll take_photos(int n, int m, int k, vector<int> r, vector<int> c)
{
    vector<pair<ll,ll>> temp_pts(n);
    for (int i = 0; i < n; i++)
    {
        if (r[i] > c[i])
            swap(r[i], c[i]);
        temp_pts[i] = {c[i], r[i] - 1};
    }
    sort(temp_pts.begin(), temp_pts.end());
    pts.push_back({0, 0});
    for (pair<ll,ll> pt : temp_pts)
    {
        while (!pts.empty() && pts.back().ROW >= pt.ROW)
            pts.pop_back();
        pts.push_back(pt);
    }

    n = pts.size() - 1;
    dp.resize(n + 1);

    ll lo = 0, hi = 1e12, mid;
    while (lo < hi)
    {
        mid = (lo + hi) / 2;

        calc(n, mid);

        if (dp[n].second > k)
            lo = mid + 1;
        else
            hi = mid;

    }

    calc(n, lo);
    return dp[n].first - k * lo;
}

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