oj.uz

Submission #443219

# Submission time Handle Problem Language Result Execution time Memory
443219 2021-07-10T07:45:05 Z prvocislo Hotel (CEOI11_hot) C++17
100 / 100
 526 ms 39988 KB 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

struct room { ll c, p; };
bool cmproom(const room &a, const room &b) 
{
    if (a.c == b.c) return a.p < b.p;
    return a.c < b.c;
}
bool cmpoffer(const room &a, const room &b) 
{
    return a.p < b.p;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); 
    int n, m, k;
    cin >> n >> m >> k;
    vector<room> r(n), o(m);
    for (int i = 0; i < n; i++) cin >> r[i].c >> r[i].p;
    sort(r.begin(), r.end(), cmproom);
    for (int i = 0; i < m; i++) cin >> o[i].c >> o[i].p;
    sort(o.begin(), o.end(), cmpoffer);
    multiset<ll, greater<ll>> best;
    vector<ll> v;
    for (int i = 0, j = 0; i < n; i++)
    {
        while (j < m && o[j].p <= r[i].p) best.insert(o[j++].c);
        if (!best.empty())
        {
            ll x = *best.begin(); best.erase(best.begin());
            v.push_back(x - r[i].c);
        }
    }
    sort(v.begin(), v.end(), greater<ll>());
    ll ans = 0, sum = 0;
    for (int i = 0; i < min((int)v.size(), k); i++) sum += v[i], ans = max(ans, sum);
    cout << ans << "\n";
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

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

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 6356 KB Output is correct
2 Correct 47 ms 4352 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 196 ms 16492 KB Output is correct
2 Correct 154 ms 13636 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 412 ms 32928 KB Output is correct
2 Correct 392 ms 32532 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 38616 KB Output is correct
2 Correct 511 ms 39988 KB Output is correct
3 Correct 478 ms 36568 KB Output is correct