Submission #544899

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
544899	2022-04-03T05:37:32 Z	wenqi	Hotel (CEOI11_hot)	C++17	100 / 100	449 ms	30412 KB

// 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

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.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct

Subtask #3
10.0 / 10.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

Subtask #4
10.0 / 10.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

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	468 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	33 ms	1480 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	59 ms	2616 KB	Output is correct
2	Correct	45 ms	1940 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	192 ms	6024 KB	Output is correct
2	Correct	104 ms	3932 KB	Output is correct

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	362 ms	11736 KB	Output is correct
2	Correct	357 ms	27212 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	391 ms	13928 KB	Output is correct
2	Correct	449 ms	14608 KB	Output is correct
3	Correct	447 ms	30412 KB	Output is correct