Submission #931116

#	Time	Username	Problem	Language	Result	Execution time	Memory
931116		caterpillow	Cake 3 (JOI19_cake3)	C++17	24 / 100	4041 ms	8032 KiB

cake3

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using pl = pair<ll,ll>;
#define vt vector
#define f first
#define s second
#define all(x) x.begin(), x.end() 
#define pb push_back
#define FOR(i, a, b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define F0R(i, b) FOR(i, 0, b)
#define endl '\n'
#define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0)
const ll INF = 1e18;

/*

its always optimal to arrange your chosen cake slices monotonically

n <= 2000:
    - sort all slices by increasing colour
    - for each L, answer the best value u can get for all R
        - iterate through R with a priority queue of cake values
        - replace cake whenever u reach a better one
    - n^2 log n

*/

ll n, m;
vt<pl> cakes;

main() {
    cin.tie(0)->sync_with_stdio(0);
    
    cin >> n >> m;
    cakes.resize(n); F0R (i, n) cin >> cakes[i].s >> cakes[i].f;
    sort(all(cakes)); // colour, value

    ll best = -INF;
    F0R (l, n) {
        ll tot = cakes[l].s;
        priority_queue<ll, vt<ll>, greater<ll>> pq;
        FOR (r, l + 1, n) {
            tot += cakes[r].s;
            if (pq.size() + 2 > m) {
                tot -= pq.top();
                pq.pop();
            }
            pq.push({cakes[r].s});
            if (pq.size() + 1 == m) {
                best = max(best, tot - 2 * (cakes[r].f - cakes[l].f));
            }
        }
    }
    cout << best << endl;
}

Compilation message (stderr)

cake3.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main() {
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:48:31: 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]
   48 |             if (pq.size() + 2 > m) {
      |                 ~~~~~~~~~~~~~~^~~
cake3.cpp:53:31: 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]
   53 |             if (pq.size() + 1 == m) {
      |                 ~~~~~~~~~~~~~~^~~~

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