제출 #453218

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
453218		blue	Cake 3 (JOI19_cake3)	C++17	24 / 100	4062 ms	15644 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;
}

long long res = -1'000'000'000'000'000'000LL;

int N, M;
vector<piece> P;

int L;
int R; //exclusive endpoints
multiset<long long> high_values;
multiset<long long> low_values;
long long high_values_sum;

void insert_to_set(long long insert_value)
{
    high_values.insert(insert_value);
    high_values_sum += insert_value;

    if(high_values.size() > M-2)
    {
        high_values_sum -= *high_values.begin();
        low_values.insert(*high_values.begin());
        high_values.erase(high_values.find(*high_values.begin()));
    }
}

void expand_left()
{
    L--;
    insert_to_set(P[L+1].V);
}

void expand_right()
{
    R++;
    insert_to_set(P[R-1].V);
}

void remove_from_set(long long remove_value)
{
    if(low_values.find(remove_value) != low_values.end())
    {
        low_values.erase(low_values.find(remove_value));
    }
    else
    {
        high_values.erase(high_values.find(remove_value));
        high_values_sum -= remove_value;

        if(high_values.size() < M-2 && low_values.size() >= 1)
        {
            high_values_sum += *low_values.rbegin();
            high_values.insert(*low_values.rbegin());
            low_values.erase(low_values.find(*low_values.rbegin()));
        }
    }
}

void contract_left()
{
    long long remove_value = P[L+1].V;
    L++;
    remove_from_set(remove_value);
}

void contract_right()
{
    long long remove_value = P[R-1].V;
    R--;
    remove_from_set(remove_value);
}



long long get_curr_score()
{
    return P[L].V + high_values_sum + P[R].V  -  2*(P[R].C - P[L].C);
}


void solve(int l1, int l2, int r1, int r2)
{
    int l = (l1+l2)/2;

    // cerr << "\n\n\n";
    // cerr << "solve " << l1 << ' ' << l2 << ' ' << r1 << ' ' << r2 << '\n';
    // cerr << "l = " << l << '\n';

    while(l < L)
        expand_left();

    // cerr << "A\n";

    while(R < max(r1, l+M-1))
        expand_right();
// cerr << "B\n";
    while(L < l)
        contract_left();
// cerr << "C\n";
    // cerr << r1 << ' ' << l << ' ' << M << ' ' << l+M-1 << ' ' << R << '\n';
    while(max(r1, l+M-1) < R)
        contract_right();

    // cerr << "D\n";

    // cerr << "L, R = " << L << ' ' << R << '\n';

    int bestR = R;
    long long best_score = get_curr_score();

    while(R+1 <= r2)
    {
        // cerr << "! ";
        // cerr << R << ' ' << r2 << '\n';
        expand_right();
        if(get_curr_score() > best_score)
        {
            best_score = get_curr_score();
            bestR = R;
        }
    }

    // cerr << l << ' ' << bestR << ' ' << best_score << '\n';

    res = max(res, best_score);
    if(l1 <= l-1)
        solve(l1, l-1, r1, bestR);
    if(l+1 <= l2)
        solve(l+1, l2, bestR, r2);
}

int main()
{
    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());

    // cerr << "\n\n";
    // for(int i = 0; i < N; i++) cerr << P[i].V << ' ' << P[i].C << '\n';


    L = 0;
    R = 1;

    solve(0, N-M, M-1, N-1);

    cout << res << '\n';
}

컴파일 시 표준 에러 (stderr) 메시지

cake3.cpp: In function 'void insert_to_set(long long int)':
cake3.cpp:34:27: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     if(high_values.size() > M-2)
      |        ~~~~~~~~~~~~~~~~~~~^~~~~
cake3.cpp: In function 'void remove_from_set(long long int)':
cake3.cpp:65:31: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   65 |         if(high_values.size() < M-2 && low_values.size() >= 1)
      |            ~~~~~~~~~~~~~~~~~~~^~~~~

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