Submission #363475

#TimeUsernameProblemLanguageResultExecution timeMemory
363475silverfishHotel (CEOI11_hot)C++14
10 / 100
4069 ms54368 KiB
#include <bits/stdc++.h> using namespace std; /*<DEBUG>*/ #define tem template <typename #define can_shift(_X_, ...) enable_if_t<sizeof test<_X_>(0) __VA_ARGS__ 8, debug&> operator<<(T i) #define _op debug& operator<< tem C > auto test(C *x) -> decltype(cerr << *x, 0LL); tem C > char test(...); tem C > struct itr{C begin, end; }; tem C > itr<C> get_range(C b, C e) { return itr<C>{b, e}; } struct debug{ #ifdef _LOCAL ~debug(){ cerr << endl; } tem T > can_shift(T, ==){ cerr << boolalpha << i; return *this; } tem T> can_shift(T, !=){ return *this << get_range(begin(i), end(i)); } tem T, typename U > _op (pair<T, U> i){ return *this << "< " << i.first << " , " << i.second << " >"; } tem T> _op (itr<T> i){ *this << "{ "; for(auto it = i.begin; it != i.end; it++){ *this << " , " + (it==i.begin?2:0) << *it; } return *this << " }"; } #else tem T> _op (const T&) { return *this; } #endif }; string _ARR_(int* arr, int sz){ string ret = "{ " + to_string(arr[0]); for(int i = 1; i < sz; i++) ret += " , " + to_string(arr[i]); ret += " }"; return ret; } #define exp(...) " [ " << #__VA_ARGS__ << " : " << (__VA_ARGS__) << " ]" /*</DEBUG>*/ typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef pair<int, int> pii; //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb push_back #define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define TC int __TC__; cin >> __TC__; while(__TC__--) #define ar array const int INF = 1e9 + 7, N = 5e5; int n, m, o; ar<int,2> room[N], offer[N]; //size room, cost room, size offer, cost offer set<ar<int,2>> rooms; vector<int> profit; int main(void) { FAST; cin >> n >> m >> o; for(int i = 0; i < n; ++i){ cin >> room[i][1] >> room[i][0]; rooms.insert(room[i]); } for(int i = 0; i < m; ++i) cin >> offer[i][1] >> offer[i][0]; sort(offer, offer+m, [](const ar<int,2> &a, const ar<int,2> &b){ if(a[0] == b[0]) return a[1] > b[1]; return a[0] < b[0]; }); for(int i = 0; i < m; ++i){ auto it = rooms.lower_bound({offer[i][0], 0}); debug() << exp(offer[i]) exp(*it); int cur_profit = offer[i][1] - (*it)[1]; if(cur_profit > 0){ profit.pb(cur_profit); rooms.erase(it); } } ll ans = 0; sort(profit.rbegin(), profit.rend()); for(int i= 0; i < min(o, (int)profit.size()); ++i){ ans += 1LL * profit[i]; } cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...