Submission #698156

#	Time	Username	Problem	Language	Result	Execution time	Memory
698156		finn__	City (BOI06_city)	C++17	100 / 100	5 ms	468 KiB

city

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

vector<uint64_t> c;

pair<uint64_t, uint64_t> num_assignable_workers(
    uint64_t n, uint64_t t, uint64_t max_cost)
{
    uint64_t total_cost = 0, w = 0;

    for (size_t i = 0; i < c.size() && w < n; i++)
    {
        if (c[i] > max_cost)
            break;
        uint64_t d = (max_cost - c[i]) / t,
                 num_workers = 2 * ((d + 1) * (d + 1) + d + 1);
        w += num_workers;
        total_cost += num_workers * c[i] +
                      t * 2 * (d * (d + 1) * (2 * d + 1) / 3 + d * (d + 1));
    }

    return {w, total_cost};
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    uint64_t n, t, k;
    cin >> n >> t >> k;

    c = vector<uint64_t>(k);
    for (uint64_t &x : c)
        cin >> x;

    // Search for the maximal cost, such that almost all workers can be assigned.
    // The remaining ones must take a house with one additional distance.
    uint64_t a = 0, b = 1000000000000000;
    while (a < b)
    {
        uint64_t mid = (a + b + 1) / 2;
        if (num_assignable_workers(n, t, mid).first < n)
            a = mid;
        else
            b = mid - 1;
    }

    auto const [w, total_cost] = num_assignable_workers(n, t, a);
    cout << total_cost + (n - w) * (a + 1) << '\n';
}

• Subtask 1: 100 / 100