Submission #631131

#	Time	Username	Problem	Language	Result	Execution time	Memory
631131		cadmiumsky	Cake 3 (JOI19_cake3)	C++14	100 / 100	3051 ms	24500 KiB

cake3

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;

#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;
const int nmax = 2e5 + 5;
const ll inf = 2e15 + 5;

int n, m;

namespace DS {
  multiset<int> vals;
  ll sum;
  vector<pii> rollback;
  
  void print() {cerr << "#"; for(auto x : vals) cerr << x << ' '; cerr << "== " << sum << "# "; }
  int gettime() {return rollback.size(); }
  void insert(int x) {
    vals.insert(x);
    sum += x;
    rollback.emplace_back(x, -1);
    if(vals.size() > m)
      sum -= (rollback.back().second = *vals.begin()),
      vals.erase(vals.begin());
    return;
  }
  void pop() {
    if(rollback.back().second != -1)
      sum += rollback.back().second,
      vals.insert(rollback.back().second);
    sum -= rollback.back().first;
    vals.erase(vals.find(rollback.back().first));
    rollback.pop_back();
    return;
  }
  ll query() {return vals.size() != m? -2 * inf : sum;} 
}

ll dp[nmax];
ll atr[nmax], v[nmax], c[nmax];

void divide(int l, int r, int optl, int optr) { // (r, optl), optl - optr, de unde poti sa iei fillere. mereu iei pozitia dupa opt_i
  if(r < l) return;
  int mid = l + r >> 1;
  int T0 = DS::gettime();
  int start;
  if(r < optl) {
    start = optl;
    for(int i = mid + 1; i <= r; i++) {
      DS::insert(v[i]);
    }
  }
  else
    start = mid + 1;
  
  dp[mid] = -inf;
  atr[mid] = -1;
  //cerr << mid << ": ";
  for(int i = start; i <= optr; i++) {
    DS::insert(v[i]);
    ll f_i = -(c[i + 1] - c[mid]) * 2 + v[mid] + v[i + 1] + DS::query();
    //cerr << i << "/ ";
    //DS::print();
    //cerr << f_i << "    ";
    if(dp[mid] <= f_i)
      dp[mid] = f_i,
      atr[mid] = i;
  }
  //cerr << '\n';
  assert(atr[mid] != -1);
  
  while(DS::gettime() > T0) DS::pop();
  for(int i = mid; i <= min(r, optl - 1); i++) DS::insert(v[i]);
  divide(l, mid - 1, optl, atr[mid]);
  
  while(DS::gettime() > T0) DS::pop();
  for(int i = max(r + 1, optl); i < atr[mid]; i++) DS::insert(v[i]);
  divide(mid + 1, r, atr[mid], optr);
  return;
}

signed main() {
  cin >> n >> m;
  m -= 2;
  vector<pii> dummy(n);
  for(auto &[a, b] : dummy) cin >> b >> a;
  sort(dummy.begin(), dummy.end());
  
  //for(auto [a, b] : dummy) cerr << a << '\t' << b << '\n';
  //cerr << '\n';
  
  for(int i = 0; i < n; i++)
    dp[i] = -inf,
    tie(c[i], v[i]) = dummy[i]; 
  
  for(int i = n - m - 1; i < m; i++) DS::insert(v[i]);
  
  divide(0, n - m - 2, m, n - 2);
  
  ll mx = dp[0];
  for(int i = 0; i < n; i++) mx = max(mx, dp[i]);
  //for(int i = 0; i < n; i++) cerr << atr[i] << ' ';
  //cerr << '\n';
  
  cout << mx << '\n';
}

/**
  De-atâtea nopți aud plouând,
  Aud materia plângând..
  Sînt singur, și mă duce un gând
  Spre locuințele lacustre.

  Și parcă dorm pe scânduri ude,
  În spate mă izbește-un val --
  Tresar prin somn și mi se pare
  Că n-am tras podul de la mal.

  Un gol istoric se întinde,
  Pe-același vremuri mă găsesc..
  Și simt cum de atâta ploaie
  Pilonii grei se prăbușesc.

  De-atâtea nopți aud plouând,
  Tot tresărind, tot așteptând..
  Sînt singur, și mă duce-un gând
  Spre locuințele lacustre.
-- George Bacovia, Lacustră
*/

Compilation message (stderr)

cake3.cpp: In function 'void DS::insert(ll)':
cake3.cpp:28:20: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   28 |     if(vals.size() > m)
      |        ~~~~~~~~~~~~^~~
cake3.cpp: In function 'll DS::query()':
cake3.cpp:42:34: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   42 |   ll query() {return vals.size() != m? -2 * inf : sum;}
      |                      ~~~~~~~~~~~~^~~~
cake3.cpp: In function 'void divide(ll, ll, ll, ll)':
cake3.cpp:50:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   50 |   int mid = l + r >> 1;
      |             ~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:92:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   92 |   for(auto &[a, b] : dummy) cin >> b >> a;
      |             ^

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