oj.uz

Submission #698156

# Submission time Handle Problem Language Result Execution time Memory
698156 2023-02-12T15:30:39 Z finn__ City (BOI06_city) C++17
100 / 100
 5 ms 468 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 5 ms 468 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct