제출 #952107

#제출 시각아이디문제언어결과실행 시간메모리
952107GrandTiger1729Cake 3 (JOI19_cake3)C++17
0 / 100
1 ms456 KiB
#include <bits/stdc++.h> using namespace std; const long long INF = 1e18; int main() { cin.tie(0)->sync_with_stdio(0); int n, K; cin >> n >> K; vector<pair<int, int>> a(n); for (int i = 0; i < n; i++) { cin >> a[i].second >> a[i].first; } sort(a.begin(), a.end()); long long cur = 0; multiset<int> st, st2; auto add = [&](int x) { st.insert(x); cur += x; while (st.size() > K) { auto it = st.begin(); cur -= *it; st2.insert(*it); st.erase(it); } }; auto del = [&](int x) { auto it = st.find(x); if (it == st.end()) { it = st2.find(x); st2.erase(x); } else { cur -= *it; st.erase(it); while (st2.size() && st.size() < K) { it = --st2.end(); cur += *it; st.insert(*it); st2.erase(it); } } }; int ll = 0, rr = -1; auto query = [&]() -> long long { return st.size() == K ? cur : -INF; }; long long ans = -INF; function<void(int, int, int, int)> solve = [&](int l, int r, int ql, int qr) { if (l > r) { return; } int mid = (l + r) / 2; pair<long long, int> maxn(-INF, -1); while (rr < mid) { add(a[++rr].second); } while (ll > qr) { add(a[--ll].second); } while (rr > mid && rr >= ll) { del(a[rr--].second); } if (rr > mid && rr < ll) { rr = mid; ll = mid + 1; } while (ll <= qr && ll <= rr) { del(a[ll++].second); } while (ll > ql) { add(a[--ll].second); maxn = max(maxn, make_pair(query() - 2ll * (a[mid].first - a[ll].first), ll)); } auto [mx, j] = maxn; ans = max(ans, mx); solve(l, mid - 1, ql, j); solve(mid + 1, r, j, qr); }; solve(K - 1, n - 1, 0, n - 1); cout << ans << '\n'; return 0; }

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

cake3.cpp: In lambda function:
cake3.cpp:22:26: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |         while (st.size() > K)
      |                ~~~~~~~~~~^~~
cake3.cpp: In lambda function:
cake3.cpp:42:44: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   42 |             while (st2.size() && st.size() < K)
      |                                  ~~~~~~~~~~^~~
cake3.cpp: In lambda function:
cake3.cpp:54:26: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         return st.size() == K ? cur : -INF;
      |                ~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...