Submission #676386

#TimeUsernameProblemLanguageResultExecution timeMemory
676386vjudge1Schools (IZhO13_school)C++17
100 / 100
112 ms10828 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int MAXN=3e5; int n, m, s; int a[MAXN+5]; int b[MAXN+5]; int id[MAXN+5]; bool cmp(int i, int j){ return a[i]-b[i]>a[j]-b[j]; } ll pre[MAXN+5]; ll suf[MAXN+5]; priority_queue<int, vector<int>, greater<int> > pq; int main(){ // freopen("C.INP", "r", stdin); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n>>m>>s; for(int i=1; i<=n; i++){ cin>>a[i]>>b[i]; id[i]=i; } sort(id+1, id+n+1, cmp); ll cur=0; for(int i=1; i<=n; i++){ pq.push(a[id[i]]); cur+=a[id[i]]; if(i>m){ cur-=pq.top(); pq.pop(); } pre[i]=cur; } cur=0; while(!pq.empty()) pq.pop(); for(int i=n; i>=1; i--){ pq.push(b[id[i]]); cur+=b[id[i]]; if(i<n-s+1){ cur-=pq.top(); pq.pop(); } suf[i]=cur; } ll res=0; for(int i=m; i+s<=n; i++){ res=max(res, suf[i+1]+pre[i]); } cout<<res; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...