Submission #544891

#	Time	Username	Problem	Language	Result	Execution time	Memory
544891		wenqi	Hotel (CEOI11_hot)	C++17	20 / 100	333 ms	12312 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;

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({d, v});
    }
    sort(customers.begin(), customers.end(), [](const pair<int, int>& a, const pair<int, int>& b){
        return a.second > b.second;
    });
    ll profit = 0;
    for (auto &c : customers)
    {
        if (O <= 0)
            break;

        auto [d, v] = 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;
        if (potential > 0)
        {
            O--;
            V[room]++;
            profit += potential;
        }
    }
    printf("%lld\n", profit);
    return 0;
}

Compilation message (stderr)

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

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