Submission #233070

#	Time	Username	Problem	Language	Result	Execution time	Memory
233070		AlexLuchianov	Cake 3 (JOI19_cake3)	C++14	0 / 100	5 ms	384 KiB

cake3

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int const inf = 1000000000;

pair<int,int> v[1 + nmax];

pair<ll,int> _add(pair<ll,int> f1, pair<ll,int> f2){
  return {f1.first + f2.first, f1.second + f2.second};
}

pair<ll,int> eval(int n, ll penal){
  pair<ll,int> sol(v[1].second + penal, 1);
  pair<ll,int> part(v[1].second + penal + 2 * v[1].first, 1);

  for(int i = 2; i <= n; i++){
    sol = max(sol, _add(part, {v[i].second + penal - 2 * v[i].first, 1}));

    part = max(part, _add(part, {v[i].second + penal, 1}));
    part = max(part, {v[i].second + penal + 2 * v[i].first, 1});
  }
  return sol;
}

int main()
{
  int n, m;
  cin >> n >> m;
  for(int i = 1; i <= n; i++)
    cin >> v[i].second >> v[i].first;
  sort(v + 1, v + n + 1);
  int penal = -inf;
  for(ll jump = (1LL << 30); 0 < jump; jump /= 2){
    if(eval(n, penal + jump).second < m)
      penal += jump;
  }
  penal++;
  pair<ll,int> sol = eval(n, penal);
  cout << sol.first - m * penal;

  return 0;
}

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