Submission #881728

#TimeUsernameProblemLanguageResultExecution timeMemory
881728alexddSchools (IZhO13_school)C++17
40 / 100
2054 ms4948 KiB
#include<bits/stdc++.h> using namespace std; const int NRIT = 8e5; const int NRSHUFFLES = 50; int n,m,s; pair<int,pair<int,int>> v[300005]; int unde[300005]; mt19937 rnd(293123); signed main() { ios_base::sync_with_stdio(0);cin.tie(0); cin>>n>>m>>s; int a,b; for(int i=1;i<=n;i++) { cin>>a>>b; v[i] = {a-b,{a,b}}; } sort(v+1,v+1+n); long long mxm=0; for(int pas2=0;pas2<NRSHUFFLES;pas2++) { for(int i=1;i<=n;i++) unde[i]=0; for(int i=1;i<=s;i++) unde[i]=2; for(int i=1;i<=m;i++) unde[n-i+1]=1; for(int pas=0;pas<NRIT;pas++) { int x = rnd()%n + 1; int y = rnd()%n + 1; if(unde[x]==unde[y]) continue; if(unde[y]==0) swap(x,y); if(unde[x]==0) { if(unde[y]==1) { if(v[x].second.first - v[y].second.first > 0) swap(unde[x],unde[y]); } else { if(v[x].second.second - v[y].second.second > 0) swap(unde[x],unde[y]); } } else { if(unde[x]==2) swap(x,y); if(v[x].second.second - v[x].second.first + v[y].second.first - v[y].second.second > 0) { swap(unde[x],unde[y]); } } } long long sum=0; for(int i=1;i<=n;i++) { if(unde[i]==1) sum += v[i].second.first; else if(unde[i]==2) sum += v[i].second.second; } mxm=max(mxm,sum); random_shuffle(v+1,v+1+n); } cout<<mxm; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...