Editorial for Phần thưởng học sinh giỏi
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k;
vector <pair <int, int>> vecObject;
void Task() {
ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
if (fopen("test.inp", "r")) {
freopen("test.inp", "r", stdin);
freopen("test.out", "w", stdout);
}
}
void Solve() {
cin >> n >> k;
vecObject.resize(n);
for (int i = 0; i < n; ++i) {
cin >> vecObject[i].second >> vecObject[i].first;
// vecObject[i] = {v,m};
}
set <pair <int, int>> setBag;
for (int i = 0; i < k; ++i) {
int c;
cin >> c;
setBag.insert({c, i});
// Mỗi chiếc túi có giá trị c và nhãn i
}
sort(vecObject.begin(), vecObject.end());
// Sắp xếp đồ vật theo tăng dần giá trị v
ll ans = 0;
for (int i = n - 1; i >= 0 && !setBag.empty(); --i) {
int weight = vecObject[i].second;
setBag.insert({weight, - 1});
auto it = setBag.find({weight, - 1});
it++;
// Chiếc túi cần tìm nằm ngay sau giá trị {weight, -1} trong set
if (it != setBag.end()) {
setBag.erase(it);
// Nếu tìm thấy, xóa chiếc túi đó đi và cộng giá trị của đồ vật vào đáp án
ans += (ll)vecObject[i].first;
}
setBag.erase({weight, - 1});
}
cout << ans;
}
int main() {
Task();
Solve();
}
Comments