Submission #544899

#	Time	Username	Problem	Language	Result	Execution time	Memory
544899		wenqi	Hotel (CEOI11_hot)	C++17	100 / 100	449 ms	30412 KiB

hot

// trans rights

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

using ll = long long;

int N, M, O;
int V[500069];
vector<pair<int, int>> rooms, customers;
vector<int> profits;

int getv(int i)
{
    return i == V[i] ? i : V[i] = getv(V[i]);
}

int main(int argc, const char *argv[])
{
    scanf("%d%d%d", &N, &M, &O);
    for (int i = 0; i < N; i++)
    {
        int c, p;
        scanf("%d%d", &c, &p);
        rooms.push_back({p, c});
        V[i] = i;
    }
    V[N] = N;
    sort(rooms.begin(), rooms.end());
    for (int i = 0; i < M; i++)
    {
        int v, d;
        scanf("%d%d", &v, &d);
        customers.push_back({v, d});
    }
    sort(customers.begin(), customers.end(), [](const pair<int, int>& a, const pair<int, int>& b){
        return a.first > b.first;
    });
    for (auto &c : customers)
    {
        auto [v, d] = c;
        int a = 0;
        int b = N + 1;
        while (b - a > 1)
        {
            int m = (a + b) / 2;
            if (rooms[m - 1].first >= d)
                b = m;
            else
                a = m;
        }
        int room = getv(a);
        if (room >= N)
            continue;

        int potential = v - rooms[room].second;
        profits.push_back(-potential);
        V[room]++;
    }
    sort(profits.begin(), profits.end());
    ll profit = 0;
    for (int i = 0; i < min<int>(O, profits.size()); i++)
        profit += max(0, -profits[i]);
    printf("%lld\n", profit);
    return 0;
}

Compilation message (stderr)

hot.cpp: In function 'int main(int, const char**)':
hot.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     scanf("%d%d%d", &N, &M, &O);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
hot.cpp:24:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         scanf("%d%d", &c, &p);
      |         ~~~~~^~~~~~~~~~~~~~~~
hot.cpp:33:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         scanf("%d%d", &v, &d);
      |         ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10