제출 #785685

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785685		SamNguyen	Cake 3 (JOI19_cake3)	C++14	0 / 100	6 ms	15956 KiB

cake3

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

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

using lli = long long;
const lli INF = 0x1f1f1f1f1f1f1f1f;

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;
}

template <int N>
class SegmentTree {
private:
    int n;
    int cnt[4 * N];
    lli st_sum[4 * N], st_min[4 * N];

    void update(int id, int l, int r, int i, lli v, lli c) {
        if (r < i or i < l)
            return;

        if (l == r) {
            cnt[id] = 1;
            st_sum[id] = v;
            st_min[id] = c;
            return;
        }

        int m = (l + r) >> 1;

        update(id << 1, l, m, i, v, c);
        update(id << 1 | 1, m + 1, r, i, v, c);

        cnt[id] = cnt[id << 1] + cnt[id << 1 | 1];
        st_sum[id] = st_sum[id << 1] + st_sum[id << 1 | 1];
        st_min[id] = min(st_min[id << 1], st_min[id << 1 | 1]);
    }

    pair<lli, lli> get_kth(int id, int l, int r, int k) {
        if (k <= 0)
            return make_pair(0, INF);

        if (l == r)
            return make_pair(st_sum[id], st_min[id]);

        int m = (l + r) >> 1;
        if (cnt[id << 1 | 1] > k)
            return get_kth(id << 1 | 1, m + 1, r, k);

        lli v, c;
        tie(v, c) = get_kth(id << 1, l, m, k - cnt[id << 1 | 1]);

        v += st_sum[id << 1 | 1];
        minimise(c, st_min[id << 1 | 1]);
        return make_pair(v, c);
    }

public:
    void init(int _n) {
        n = _n;
        memset(cnt, 0, sizeof cnt);
        memset(st_sum, 0, sizeof st_sum);
        memset(st_min, 0x1f, sizeof st_min);
    }

    inline void update(int i, lli v, lli c) { update(1, 1, n, i, v, c); }
    inline pair<lli, lli> get_kth(int k) { return get_kth(1, 1, n, k); }
};

const int MAX = 2e5 + 7;
int N, M, ord[MAX];
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);

    vector<lli> vals;
    for (int i = 1; i <= N; i++)
        vals.push_back(GET_V(i));
    sort(vals.begin(), vals.end());
    for (int i = 1; i <= N; i++)
        ord[i] = lower_bound(vals.begin(), vals.end(), GET_V(i)) - vals.begin() + 1;
}

SegmentTree<MAX> st;

void solve() {
    st.init(N);

    lli ans = -INF;

    for (int i = 1; i <= N; i++) {
        st.update(ord[i], GET_V(i), GET_C(i));

//        cerr << "update " << ord[i] << ", v = " << GET_V(i) << ", c = " << GET_C(i) << endl;

        if (i < M)
            continue;

        lli sum_v, min_c;
        tie(sum_v, min_c) = st.get_kth(M);

//        cerr << "sum_v = " << sum_v << ", GET_C(" << i << ") = " << GET_C(i) << ", min_c = " << min_c << endl;

        maximise(ans, sum_v - 2 * (GET_C(i) - min_c));
    }

    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;
}

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

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

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