Submission #785685

#TimeUsernameProblemLanguageResultExecution timeMemory
785685SamNguyenCake 3 (JOI19_cake3)C++14
0 / 100
6 ms15956 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...