제출 #931116

#제출 시각아이디문제언어결과실행 시간메모리
931116caterpillowCake 3 (JOI19_cake3)C++17
24 / 100
4041 ms8032 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using pl = pair<ll,ll>; #define vt vector #define f first #define s second #define all(x) x.begin(), x.end() #define pb push_back #define FOR(i, a, b) for (int i = (a); i < (b); ++i) #define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i) #define F0R(i, b) FOR(i, 0, b) #define endl '\n' #define debug(x) do{auto _x = x; cerr << #x << " = " << _x << endl;} while(0) const ll INF = 1e18; /* its always optimal to arrange your chosen cake slices monotonically n <= 2000: - sort all slices by increasing colour - for each L, answer the best value u can get for all R - iterate through R with a priority queue of cake values - replace cake whenever u reach a better one - n^2 log n */ ll n, m; vt<pl> cakes; main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; cakes.resize(n); F0R (i, n) cin >> cakes[i].s >> cakes[i].f; sort(all(cakes)); // colour, value ll best = -INF; F0R (l, n) { ll tot = cakes[l].s; priority_queue<ll, vt<ll>, greater<ll>> pq; FOR (r, l + 1, n) { tot += cakes[r].s; if (pq.size() + 2 > m) { tot -= pq.top(); pq.pop(); } pq.push({cakes[r].s}); if (pq.size() + 1 == m) { best = max(best, tot - 2 * (cakes[r].f - cakes[l].f)); } } } cout << best << endl; }

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

cake3.cpp:35:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   35 | main() {
      | ^~~~
cake3.cpp: In function 'int main()':
cake3.cpp:48:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   48 |             if (pq.size() + 2 > m) {
      |                 ~~~~~~~~~~~~~~^~~
cake3.cpp:53:31: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int, std::vector<long long int>, std::greater<long long int> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   53 |             if (pq.size() + 1 == m) {
      |                 ~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...