제출 #654882

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

aliens

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

#define COL first
#define ROW second

pair<ll,ll> calc(int n, int m, vector<pair<ll,ll>>& pts, ll cost)
{
    vector<ll> dp(n), cnt(n);
    dp[0] = (pts[0].COL - pts[0].ROW + 1) * (pts[0].COL - pts[0].ROW + 1);
    cnt[0] = 1;
    for (int i = 1; i < n; i++)
    {
        dp[i] = (pts[i].COL - pts[0].ROW + 1) * (pts[i].COL - pts[0].ROW + 1);
        cnt[i] = 1;
        for (int j = 0; j < i; j++)
        {
            ll new_square = (pts[i].COL - pts[j+1].ROW + 1);
            ll overlap = max(pts[j].COL - pts[j+1].ROW + 1, 0LL);

            ll total_area = dp[j] + new_square * new_square - overlap * overlap;

            if (make_pair(total_area + cost, 1 + cnt[j]) < make_pair(dp[i], cnt[i]))
            {
                dp[i] = total_area + cost;
                cnt[i] = 1 + cnt[j];
            }
        }
    }
    /*
    cout << "with a cost of " << cost << " we use " << cnt[n-1] << " squares for a total of " << dp[n-1] << '\n';
    */
    return {cnt[n-1], dp[n-1]};
}

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

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

        auto [count, mini] = calc(n, m, monotone, mid);

        if (count > k)
            lo = mid + 1;
        else
            hi = mid;
    }
    auto [count, mini] = calc(n, m, monotone, lo);
    return mini;
}

/*
int main()
{
    cout << take_photos(5, 7, 2, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6}) << '\n';
    cout << take_photos(2, 6, 2, {1, 4}, {4, 1}) << '\n';

    return 0;
}
*/

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