제출 #921968

#제출 시각아이디문제언어결과실행 시간메모리
921968boris_mihovCake 3 (JOI19_cake3)C++17
24 / 100
4022 ms4476 KiB
#include <algorithm> #include <iostream> #include <numeric> #include <cassert> #include <vector> #include <queue> typedef long long llong; const int MAXN = 200000 + 10; const llong INF = 1e18; int n, k; int v[MAXN]; int c[MAXN]; int opt[MAXN]; std::pair <int,int> toSort[MAXN]; std::priority_queue <int> pq; void solve() { std::sort(toSort + 1, toSort + 1 + n); for (int i = 1 ; i <= n ; ++i) { c[i] = toSort[i].first; v[i] = toSort[i].second; } k -= 2; llong ans = -INF; for (int i = 1 ; i <= n ; ++i) { llong sum = 0; llong currAns = -INF; while (pq.size()) pq.pop(); opt[i] = n + 1; for (int j = i + 1 ; j <= n ; ++j) { if (pq.size() == k) { llong curr = sum + v[i] + v[j] - 2 * (c[j] - c[i]); if (currAns < curr) { currAns = curr; opt[i] = j; } } sum += v[j]; pq.push(-v[j]); if (pq.size() > k) { sum += pq.top(); pq.pop(); } } ans = std::max(ans, currAns); } for (int i = 1 ; i < n ; ++i) { assert(opt[i] <= opt[i + 1]); } std::cout << ans << '\n'; } void input() { std::cin >> n >> k; for (int i = 1 ; i <= n ; ++i) { std::cin >> toSort[i].second >> toSort[i].first; } } void fastIOI() { std::ios_base :: sync_with_stdio(0); std::cout.tie(nullptr); std::cin.tie(nullptr); } int main() { fastIOI(); input(); solve(); return 0; }

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

cake3.cpp: In function 'void solve()':
cake3.cpp:39:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |             if (pq.size() == k)
      |                 ~~~~~~~~~~^~~~
cake3.cpp:51:27: warning: comparison of integer expressions of different signedness: 'std::priority_queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |             if (pq.size() > k)
      |                 ~~~~~~~~~~^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...