Submission #785669

#	Time	Username	Problem	Language	Result	Execution time	Memory
785669		SamNguyen	Cake 3 (JOI19_cake3)	C++14	24 / 100	4043 ms	8064 KiB

cake3

#include <bits/stdc++.h>
using namespace std;

#define INPFILE "cake3.inp"
#define OUTFILE "cake3.out"

using lli = long long;

template <class T1, class T2>
inline bool maximise(T1 &x, T2 y) {
    if (x < y) { x = y; return true; }
    return false;
}

template <class T1, class T2>
inline bool minimise(T1 &x, T2 y) {
    if (x > y) { x = y; return true; }
    return false;
}

const lli INF = 1e18;
const int MAX = 2e5 + 7;
int N, M;
pair<lli, lli> piece[MAX];

inline lli GET_V(int i) { return piece[i].second; }
inline lli GET_C(int i) { return piece[i].first; }

void input() {
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        lli v, c; cin >> v >> c;
        piece[i] = make_pair(c, v);
    }

    sort(piece + 1, piece + N + 1);
}

void solve() {
    lli ans = -INF;

    for (int l = 1; l <= N; l++) {
        priority_queue<lli, vector<lli>, greater<lli>> pq;
        lli sum_v = 0;

        for (int r = l; r <= N; r++) {
            pq.push(GET_V(r));
            sum_v += GET_V(r);

            while (int(pq.size()) > M) {
                sum_v -= pq.top();
                pq.pop();
            }

            if (int(pq.size()) == M)
                maximise(ans, sum_v - 2 * (GET_C(r) - GET_C(l)));
        }
    }

    cout << ans;
}

int main(void) {
    if (fopen(INPFILE, "r")) {
        freopen(INPFILE, "r", stdin);
        freopen(OUTFILE, "w", stdout);
    }
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

    input();
    solve();

    return 0;
}

Compilation message (stderr)

cake3.cpp: In function 'int main()':
cake3.cpp:65:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |         freopen(INPFILE, "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
cake3.cpp:66:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   66 |         freopen(OUTFILE, "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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