# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
245652 | 2020-07-07T03:47:38 Z | Mercenary | Schools (IZhO13_school) | C++14 | 144 ms | 11888 KB |
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/trie_policy.hpp> #define pb push_back #define mp make_pair #define taskname "A" using namespace std; using namespace __gnu_pbds; typedef long long ll; typedef long double ld; typedef pair<int,int> ii; typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; const int maxn = 3e5 + 5; const int mod = 1e9 + 7; const int logn = log2(maxn) + 1; int n , m , s; ii a[maxn]; ll pre[maxn] ,suf[maxn]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")){ freopen(taskname".INP", "r",stdin); freopen(taskname".OUT", "w",stdout); } cin >> n >> m >> s; for(int i = 1 ; i <= n ; ++i)cin >> a[i].first >> a[i].second; sort(a + 1 , a + n + 1 , [&](const ii x , const ii y){ return x.first - x.second > y.first - y.second; }); priority_queue<ll,vector<ll>,greater<ll>> pq; for(int i = 1 ; i <= n ; ++i){ pq.push(a[i].first); pre[i] = pre[i - 1] + a[i].first; while(pq.size() > m){ pre[i] -= pq.top(); pq.pop(); } } while(pq.size())pq.pop(); for(int i = n ; i >= 1 ; --i){ pq.push(a[i].second); suf[i] = suf[i + 1] + a[i].second; while(pq.size() > s){ suf[i] -= pq.top(); pq.pop(); } } ll res = 0; for(int i = 0 ; i <= n ; ++i)res = max(res , pre[i] + suf[i + 1]); cout << res; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 5 ms | 384 KB | Output is correct |
2 | Correct | 5 ms | 384 KB | Output is correct |
3 | Correct | 5 ms | 384 KB | Output is correct |
4 | Correct | 5 ms | 384 KB | Output is correct |
5 | Correct | 5 ms | 384 KB | Output is correct |
6 | Correct | 5 ms | 384 KB | Output is correct |
7 | Correct | 7 ms | 512 KB | Output is correct |
8 | Correct | 7 ms | 640 KB | Output is correct |
9 | Correct | 7 ms | 640 KB | Output is correct |
10 | Correct | 7 ms | 640 KB | Output is correct |
11 | Correct | 6 ms | 640 KB | Output is correct |
12 | Correct | 6 ms | 640 KB | Output is correct |
13 | Correct | 22 ms | 2040 KB | Output is correct |
14 | Correct | 38 ms | 3320 KB | Output is correct |
15 | Correct | 65 ms | 6008 KB | Output is correct |
16 | Correct | 77 ms | 8304 KB | Output is correct |
17 | Correct | 111 ms | 8948 KB | Output is correct |
18 | Correct | 117 ms | 9712 KB | Output is correct |
19 | Correct | 134 ms | 10352 KB | Output is correct |
20 | Correct | 144 ms | 11888 KB | Output is correct |