Submission #631057

#	Time	Username	Problem	Language	Result	Execution time	Memory
631057		cadmiumsky	Cake 3 (JOI19_cake3)	C++14	24 / 100	4069 ms	4368 KiB

cake3

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

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

int dp[nmax], r[nmax];

signed main() {
  cin >> n >> m;
  m -= 2;
  vector<pii> cake(n);
  for(auto &[c, v] : cake)
    cin >> v >> c;
  sort(all(cake));
  
  int mx = -inf;
  for(int i = 0; i < n; i++) {
    dp[i] = -inf;
    r[i] = n + 1;

    priority_queue<int, vector<int>, greater<int>> pq;
    int sum = 0;
    for(int j = i + 1; j < n - 1; j++) {
      pq.push(cake[j].second);
      sum += cake[j].second;
      if(pq.size() > m)
	sum -= pq.top(), pq.pop();
      if(pq.size() == m) {
	if(cake[i].second + cake[j + 1].second - (cake[j + 1].first - cake[i].first) * 2 + sum > dp[i])
	  dp[i] = cake[i].second + cake[j + 1].second - (cake[j + 1].first - cake[i].first) * 2 + sum,
	  r[i] = j + 1;
      }
    }
    mx = max(mx, dp[i]);
  }
  
  for(int i = 1; i < n; i++) {
    assert(r[i] >= r[i - 1]);
  }
  
  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 'int main()':
cake3.cpp:18:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   18 |   for(auto &[c, v] : cake)
      |             ^
cake3.cpp:32:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   32 |       if(pq.size() > m)
      |          ~~~~~~~~~~^~~
cake3.cpp:34:20: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   34 |       if(pq.size() == m) {
      |          ~~~~~~~~~~^~~~

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