Submission #120447

#TimeUsernameProblemLanguageResultExecution timeMemory
120447OptxPrimeKisik (COCI19_kisik)C++11
0 / 90
489 ms16916 KiB
#include <iostream> #include <cmath> #include<vector> #include <algorithm> #include <utility> #include<stack> #include<queue> using namespace std; #define pb push_back #define mp make_pair int main() { long long n,k,u,v; vector<pair<long long, long long>> rec; priority_queue<pair<long long,long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>>pq; cin>>n>>k; for(int i=0;i<n;i++){ cin>>u>>v; rec.pb( mp( u,v ) ); } sort( rec.begin(), rec.end() ); long long ans; long long currh=-1,currw=0; for( int i=0;i<k;i++ ){ currw+=rec[i].first; currh=max( currh,rec[i].second ); pq.push( mp( rec[i].second, rec[i].first ) ); } ans=currh*currw; for( int i=k;i<n;i++ ){ pair<long long,long long> maxx=pq.top(); long long maxh=maxx.first; /// treba uzimat samo kad poboljsa povrsinu if( rec[i].second < maxh ){ long long prevw=currw; currw-=maxx.second; currw+=rec[i].first; long long prevh=currh; currh=max( currh, rec[i].second ); if( currw*currh < ans ){ ans=currw*currh; pq.pop(); pq.push( mp( rec[i].second, rec[i].first ) ); currh=pq.top().first; } else currh=prevh, currw=prevw; } } cout<<ans<<endl; 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...