oj.uz

Submission #121351

# Submission time Handle Problem Language Result Execution time Memory
121351 2019-06-26T12:07:27 Z OptxPrime Kisik (COCI19_kisik) C++11
90 / 90
 843 ms 53068 KB 
#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
#define ll long long



int main()
{
    long long n,k,u,v;
    vector<pair<long long, long long>> vec;
   // priority_queue<pair<long long,long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>>pq;
//priority_queue<pair<long long,long long>, greater<pair<long long, long long>>, vector<pair<long long, long long>>>pq;
priority_queue<pair<ll,ll>> pq;

    cin>>n>>k;

    for(int i=0;i<n;i++){
        cin>>u>>v;
        vec.pb( mp( v,u ) );
    }

    sort( vec.begin(), vec.end() );
  //  cout<<endl;
  //  for( int i=0;i<vec.size();i++ )cout<<vec[i].first << " " << vec[i].second << " et  "<<endl;

    long long ans=1000000000000000000,w=0,h;
    for( int i=0;i<vec.size();i++ ){
        if( pq.size() < k ){
            pq.push( mp(vec[i].second, vec[i].first ));
            w+=vec[i].second;
            h=vec[i].first;
            if( pq.size() == k ) ans=min( ans,w*h );
        //cout << pq.top().first << " " << pq.top().second << " kontas " <<endl;
        }
        else{
                pair<ll,ll> maxx=pq.top();
   //             cout << maxx.first << " " << maxx.second <<endl;
                w+= vec[i].second - maxx.first;
                h=vec[i].first;
                pq.pop();
                pq.push( mp( vec[i].second, vec[i].first ) );
            ans=min( ans, h*w );
        }
    }

    cout<<ans<<endl;
    return 0;
}

Compilation message

kisik.cpp: In function 'int main()':
kisik.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for( int i=0;i<vec.size();i++ ){
                  ~^~~~~~~~~~~
kisik.cpp:38:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if( pq.size() < k ){
             ~~~~~~~~~~^~~
kisik.cpp:42:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if( pq.size() == k ) ans=min( ans,w*h );
                 ~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 4 ms 384 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 272 ms 12428 KB Output is correct
2 Correct 555 ms 31680 KB Output is correct
3 Correct 494 ms 42564 KB Output is correct
4 Correct 486 ms 41044 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 372 ms 19072 KB Output is correct
2 Correct 69 ms 5732 KB Output is correct
3 Correct 143 ms 10972 KB Output is correct
4 Correct 390 ms 26744 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 226 ms 13884 KB Output is correct
2 Correct 463 ms 24224 KB Output is correct
3 Correct 358 ms 14516 KB Output is correct
4 Correct 782 ms 53068 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 297 ms 16140 KB Output is correct
2 Correct 843 ms 42244 KB Output is correct
3 Correct 232 ms 15444 KB Output is correct
4 Correct 586 ms 44740 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 578 ms 24320 KB Output is correct
2 Correct 539 ms 33748 KB Output is correct
3 Correct 443 ms 26616 KB Output is correct
4 Correct 259 ms 21968 KB Output is correct