oj.uz

Submission #544891

# Submission time Handle Problem Language Result Execution time Memory
544891 2022-04-03T05:21:39 Z wenqi Hotel (CEOI11_hot) C++17
20 / 100
 333 ms 12312 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;

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

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

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 1 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 26 ms 1520 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 2668 KB Output is correct
2 Incorrect 41 ms 2000 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 5656 KB Output is correct
2 Incorrect 81 ms 3552 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 285 ms 11144 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 333 ms 12312 KB Output isn't correct
2 Halted 0 ms 0 KB -