Submission #790621

#	Time	Username	Problem	Language	Result	Execution time	Memory
790621		tvladm2009	Cake 3 (JOI19_cake3)	C++17	24 / 100	4048 ms	8128 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

/**const int INF = (int) 1e9;

vector<int> v;

void run(int lvl = 0) {
  if (lvl == 4) {
    vector<int> cv = v;
    sort(cv.begin(), cv.end());
    int best = INF;
    while (next_permutation(cv.begin(), cv.end())) {
      int now = 0;
      for (int i = 1; i < (int) cv.size(); i++) {
        now += abs(cv[i] - cv[i - 1]);
      }
      now += abs(cv.back() - cv[0]);
      if (now < best) {
        best = now;
      }
    }
    cv = v;
    sort(cv.begin(), cv.end());
    cout << "[";
    for (int i = 0; i < (int) v.size(); i++) {
      cout << v[i];
      if (i < v.size() - 1) {
        cout << " ";
      }
    }
    cout << "] ";
    cout << " -> ";
    while (next_permutation(cv.begin(), cv.end())) {
      int now = 0;
      for (int i = 1; i < (int) cv.size(); i++) {
        now += abs(cv[i] - cv[i - 1]);
      }
      now += abs(cv.back() - cv[0]);
      if (now == best) {
        cout << "[";
        for (int i = 0; i < (int) cv.size(); i++) {
          cout << cv[i];
          if (i < cv.size() - 1) {
            cout << " ";
          }
        }
        cout << "] sau ";
      }
    }
    cout << "\n";
    return;
  }
  for (int i = 1; i <= 4; i++) {
    v.push_back(i);
    run(lvl + 1);
    v.pop_back();
  }
}**/

#define int ll

const int N = (int) 2e5 + 7;
const ll INF = (ll) 1e18;
pair<int, int> a[N];
int n, m;


signed main() {
  ios::sync_with_stdio(0); cin.tie(0);

  // freopen("input", "r", stdin);

  /// run();

  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i].first >> a[i].second;
  }
  sort(a + 1, a + n + 1, [&](pair<int, int> a, pair<int, int> b) {
    return a.second < b.second;
  });
  ll ret = -INF;
  for (int i = m; i <= n; i++) {
    priority_queue<int> pq;
    ll s = 0;
    vector<int> v;
    for (int j = i - 1; j >= 1; j--) {
      if (i - j - 1 >= m - 2) {
        v.push_back(a[j].first + s + a[i].first - (2 * a[i].second - 2 * a[j].second));
        ret = max(ret, a[j].first + s + a[i].first - (2 * a[i].second - 2 * a[j].second));
      }
      pq.push(-a[j].first);
      s += a[j].first;
      if ((int) pq.size() > m - 2) {
        s -= -pq.top();
        pq.pop();
      }
    }
    /**vector<int> sgn;
    for (int j = 1; j < (int) v.size(); j++) {
      if (v[j] > v[j - 1]) {
        sgn.push_back(-1);
      } else {
        sgn.push_back(+1);
      }
    }
    int changes = 0;
    for (int j = 0; j < (int) sgn.size() - 1; j++) {
      changes += (sgn[j] != sgn[j + 1]);
    }
    assert(changes <= 2);**/
  }
  cout << ret << "\n";
  return 0;
}

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