Submission #1190366

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190366		lopkus	Cake 3 (JOI19_cake3)	C++20	24 / 100	4091 ms	7748 KiB

cake3

#include <bits/stdc++.h>

void solve() {
  int n, m;
  std::cin >> n >> m;
  std::vector<std::array<int64_t, 2>> a(n + 1);
  for(int i = 1; i <= n; i++) {
    std::cin >> a[i][0] >> a[i][1];
    std::swap(a[i][0], a[i][1]);
  }
  std::sort(a.begin() + 1, a.end());
  int64_t ans = -1e18;
  std::multiset<int64_t> ms;
  std::vector<int64_t> x(n + 1);
  for(int i = 1; i <= n; i++) {
    x[i] = a[i][1] - 2 * a[i][0];
  }
  for(int i = 1; i < n; i++) {
    ms.clear();
    ms.insert(a[i + 1][1]);
    int64_t sum = a[i + 1][1] + 2 * a[i][0] + a[i][1];
    for(int j = i + 2; j <= n; j++) {
      if(j - i + 1 >= m) {
        ans = std::max(ans, sum + x[j]);
      }
      ms.insert(a[j][1]);
      sum += a[j][1];
      if(ms.size() > m - 2) {
        auto small = ms.begin();
        sum -= *small;
        ms.erase(ms.find(*small));
      }
    }
  }
  std::cout << ans;
}

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);

  int t = 1;
  //std::cin >> t;
  while (t--) {
      solve();
  }

  return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 0 / 76