Submission #204944

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
204944	2020-02-27 14:05:54	ics0503	Cake 3 (JOI19_cake3)	C++17	100 / 100	3608 ms	23652 KiB

cake3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<stdio.h>
#include<algorithm>
#include<vector>
#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; }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

cake3.cpp: In function 'void balance()':
cake3.cpp:10: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:24: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:71:15: warning: unused variable 'j' [-Wunused-variable]
  long long i, j; scanf("%lld%lld", &n, &m);
               ^
cake3.cpp:71:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  long long i, j; scanf("%lld%lld", &n, &m);
                  ~~~~~^~~~~~~~~~~~~~~~~~~~
cake3.cpp:72:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for (i = 0; i < n; i++) scanf("%lld%lld", &a[i].v, &a[i].c);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 19 / 19
• Subtask 3: 76 / 76