oj.uz

Submission #123237

# Submission time Handle Problem Language Result Execution time Memory
123237 2019-06-30T14:14:47 Z cvele Kisik (COCI19_kisik) C++14
90 / 90
 1289 ms 52948 KB 
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <cstring>
#include <climits>
#include <iomanip>
#include <bitset>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <list>
#include <map>

using namespace std;

const int N = 1000005;

int n, k;
vector < pair <int, int> > vec;
multiset <int> ms;

int main() {
  ios_base::sync_with_stdio(false);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    int w, h;
    cin >> w >> h;
    vec.push_back({h, w});
  }
  sort(vec.begin(), vec.end());
  int pos = 0;
  long long ans = 2e18, sum = 0;
  for (int i = 1; i < N; i++) {
    while (pos < n && vec[pos].first <= i) {
      sum += vec[pos].second;
      ms.insert(vec[pos].second);
      while (ms.size() > k) {
        sum -= *ms.rbegin();
        ms.erase(--ms.end());
      }
      pos++;
    }
    if (ms.size() == k) {
      ans = min(ans, 1ll * sum * i);
    }
  }
  cout << ans << endl;
  return 0;
}

Compilation message

kisik.cpp: In function 'int main()':
kisik.cpp:43:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       while (ms.size() > k) {
              ~~~~~~~~~~^~~
kisik.cpp:49:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (ms.size() == k) {
         ~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 4648 KB Output is correct
2 Correct 608 ms 20152 KB Output is correct
3 Correct 805 ms 33108 KB Output is correct
4 Correct 674 ms 30676 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 9992 KB Output is correct
2 Correct 64 ms 4592 KB Output is correct
3 Correct 139 ms 8420 KB Output is correct
4 Correct 539 ms 26848 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 213 ms 11752 KB Output is correct
2 Correct 251 ms 8768 KB Output is correct
3 Correct 237 ms 7012 KB Output is correct
4 Correct 1289 ms 52948 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 11048 KB Output is correct
2 Correct 1063 ms 30520 KB Output is correct
3 Correct 243 ms 11488 KB Output is correct
4 Correct 878 ms 37588 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 11000 KB Output is correct
2 Correct 727 ms 27584 KB Output is correct
3 Correct 546 ms 19040 KB Output is correct
4 Correct 370 ms 17888 KB Output is correct