Submission #450203

#	Time	Username	Problem	Language	Result	Execution time	Memory
450203		blue	Cake 3 (JOI19_cake3)	C++17	0 / 100	1 ms	204 KiB

cake3

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <cassert>
using namespace std;

struct piece
{
    long long V;
    long long C;
};

bool operator < (piece A, piece B)
{
    return A.C < B.C;
}


int main()
{
    int N, M;
    vector<piece> P;
    cin >> N >> M;
    P = vector<piece>(N);
    for(int i = 0; i < N; i++) cin >> P[i].V >> P[i].C;
    sort(P.begin(), P.end());

    long long res = 0;

    for(int L = 0; L <= N-M; L++)
    {
        long long sm = 0;
        multiset<long long> vals;
        for(int i = L+1; i <= L+M-2; i++)
        {
            vals.insert(P[i].V);
            sm += P[i].V;
        }
        assert(vals.size() == M-2);
        res = max(res, P[L].V + sm + P[L+M-1].V  -  2*(P[L+M-1].C - P[L].C));

        for(int i = L+M-1; i+1 < N; i++)
        {
            vals.insert(P[i].V);
            sm += P[i].V;

            if(vals.size() > M-2)
            {
                sm -= *vals.begin();
                vals.erase(vals.begin());
            }
            assert(vals.size() == M-2);
            res = max(res, P[L].V + sm + P[i+1].V  -  2*(P[i+1].C - P[L].C));
        }
    }
    cout << res << '\n';
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from cake3.cpp:5:
cake3.cpp: In function 'int main()':
cake3.cpp:40:28: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   40 |         assert(vals.size() == M-2);
      |                ~~~~~~~~~~~~^~~~~~
cake3.cpp:48:28: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   48 |             if(vals.size() > M-2)
      |                ~~~~~~~~~~~~^~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from cake3.cpp:5:
cake3.cpp:53:32: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |             assert(vals.size() == M-2);
      |                    ~~~~~~~~~~~~^~~~~~

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