Submission #450197

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

cake3

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
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;
        }
        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;

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

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