제출 #204364

#제출 시각아이디문제언어결과실행 시간메모리
204364ics0503Cake 3 (JOI19_cake3)C++17
0 / 100
5 ms380 KiB
#include<stdio.h> #include<algorithm> #include<set> using namespace std; long long n, m, allSum = 0; multiset<long long >L, R; // R is big void balance() { if (L.size() == 0 || R.size() == 0)return; if (R.size() < m) { long long lmax = (*L.rbegin()); L.erase(L.find(lmax)); R.insert(lmax); allSum += lmax; return; } long long lmax = (*L.rbegin()), rmin = (*R.begin()); if (lmax > rmin) { L.erase(L.find(lmax)); R.erase(R.find(rmin)); L.insert(rmin); R.insert(lmax); allSum += lmax - rmin; } } void add(long long x) { if (R.size() < m) { R.insert(x); allSum += x; } else L.insert(x); balance(); } void del(long long x) { if (L.find(x) != L.end())L.erase(L.find(x)); else { R.erase(R.find(x)); allSum -= x; } balance(); } struct vc { long long v, c; }a[212121]; bool sort_c(vc a, vc b) { if (a.c != b.c)return a.c < b.c; return a.v > b.v; } long long SS[212121]; int main() { long long i, j, k; scanf("%lld%lld", &n, &m); for (i = 1; i <= n; i++) scanf("%lld%lld", &a[i].v, &a[i].c); sort(a + 1, a + n + 1, sort_c); for (i = 1; i <= n; i++)SS[i] = SS[i - 1] + a[i].v; for (i = 1; i <= m; i++)add(a[i].v); long long ans = allSum - 2ll * (a[m].c - a[1].c), s = 1; for (i = m + 1; i <= n; i++) { add(a[i].v); long long newRes = (SS[i] - SS[i - m]) - 2ll * (a[i].c - a[i - m + 1].c); long long nowRes = allSum - 2ll * (a[i].c - a[s].c); if (nowRes < newRes) { while (s < i - m + 1) { del(a[s].v); s++; } } while (i>=s+m) { long long befRes = allSum - 2ll * (a[i].c - a[s].c); del(a[s].v); long long nxtRes = allSum - 2ll * (a[i].c - a[s + 1].c); if (befRes <= nxtRes) s++; else { add(a[s].v); break; } } ans = max(ans, allSum - 2ll * (a[i].c - a[s].c)); } printf("%lld", ans); return 0; }

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

cake3.cpp: In function 'void balance()':
cake3.cpp:9:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (R.size() < m) {
      ~~~~~~~~~^~~
cake3.cpp: In function 'void add(long long int)':
cake3.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (R.size() < m) { R.insert(x); allSum += x; }
      ~~~~~~~~~^~~
cake3.cpp: In function 'int main()':
cake3.cpp:39:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j, k; scanf("%lld%lld", &n, &m);
               ^
cake3.cpp:39:18: warning: unused variable 'k' [-Wunused-variable]
  long long i, j, k; scanf("%lld%lld", &n, &m);
                  ^
cake3.cpp:39:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long i, j, k; scanf("%lld%lld", &n, &m);
                     ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:40:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 1; i <= n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
                           ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...