This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
Compilation message (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);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |