oj.uz

Submission #123234

# Submission time Handle Problem Language Result Execution time Memory
123234 2019-06-30T14:10:00 Z cvele Kisik (COCI19_kisik) C++14
80 / 90
 2000 ms 61116 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;

#define int long long

const int N = 1000005;

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

int32_t main() {
  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++) {
    bool now = 0;
    if (pos < vec.size() && vec[pos].first == i) now = 1;
    while (pos < vec.size() && vec[pos].first == i) {
      sum += vec[pos].second;
      ms.insert(vec[pos].second);
      pos++;
    }
    while (ms.size() > k) {
      sum -= *ms.rbegin();
      ms.erase(--ms.end());
    }
    if (now && ms.size() == k) {
      ans = min(ans, 1ll * sum * i);
    }
  }
  cout << ans << endl;
  return 0;
}

Compilation message

kisik.cpp: In function 'int32_t main()':
kisik.cpp:42:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (pos < vec.size() && vec[pos].first == i) now = 1;
         ~~~~^~~~~~~~~~~~
kisik.cpp:43:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pos < vec.size() && vec[pos].first == i) {
            ~~~~^~~~~~~~~~~~
kisik.cpp:48:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (ms.size() > k) {
            ~~~~~~~~~~^~~
kisik.cpp:52:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (now && ms.size() == k) {
                ~~~~~~~~~~^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 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 6 ms 376 KB Output is correct
3 Correct 6 ms 376 KB Output is correct
4 Correct 5 ms 256 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 389 ms 9224 KB Output is correct
2 Correct 1200 ms 25640 KB Output is correct
3 Correct 1296 ms 37876 KB Output is correct
4 Correct 1180 ms 35388 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 765 ms 14040 KB Output is correct
2 Correct 131 ms 5476 KB Output is correct
3 Correct 272 ms 10356 KB Output is correct
4 Correct 1012 ms 31056 KB Output is correct

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 451 ms 14320 KB Output is correct
2 Correct 735 ms 17600 KB Output is correct
3 Correct 568 ms 10320 KB Output is correct
4 Execution timed out 2078 ms 61116 KB Time limit exceeded

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 551 ms 13988 KB Output is correct
2 Correct 1837 ms 37960 KB Output is correct
3 Correct 496 ms 14160 KB Output is correct
4 Correct 1568 ms 43132 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1020 ms 17480 KB Output is correct
2 Correct 1225 ms 32700 KB Output is correct
3 Correct 913 ms 23128 KB Output is correct
4 Correct 630 ms 20688 KB Output is correct