Submission #533226

#	Time	Username	Problem	Language	Result	Execution time	Memory
533226		Soumya1	Cake 3 (JOI19_cake3)	C++17	24 / 100	4089 ms	7760 KiB

cake3

#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
void testCase() {
  int n, m;
  cin >> n >> m;
  vector<pair<long long, long long>> a(n);
  for (auto &[x, y] : a) cin >> y >> x;
  sort(a.begin(), a.end());
  vector<long long> dp(m + 1, -1e18);
  long long mx = -1e18;
  for (int i = 0; i < n; i++) {
    vector<long long> new_dp(m + 1, -1e18);
    new_dp[1] = a[i].second + 2 * a[i].first;
    for (int j = 2; j < m; j++) {
      new_dp[j] = dp[j - 1] + a[i].second;
    }
    if (i >= m - 1) mx = max(mx, dp[m - 1] + a[i].second - 2 * a[i].first);
    for (int j = 1; j < m; j++) dp[j] = max(dp[j], new_dp[j]);
  }
  cout << mx << endl;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}

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