oj.uz

답안 #84423

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
84423 2018-11-15T07:24:17 Z MrTEK 학교 설립 (IZhO13_school) C++14
30 / 100
 459 ms 18164 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;
typedef pair<int,int> ii;

const int N = 3e5 + 5;

multiset <int> l1,l2,r1,r2;
multiset <int> :: iterator it;

int n,m,s,a[N],b[N],id[N];
ll suml,sumr,ans;

void add_l(int x){
  if (l1.size() < m) {
    suml += a[x];
    l1.insert(-a[x]);
  }
  else {
    it = l1.end();
    it--;
    if (-*it < a[x]) {
      suml += a[x];
      suml -= -*it;
      l2.insert(*it);
      l1.erase(it);
      l1.insert(-a[x]);
    }
    else {
      l2.insert(-a[x]);
    }
  }
}

void add_r(int x) {
  if (r1.size() < s) {
    sumr += b[x];
    r1.insert(-b[x]);
  }
  else {
    it = r1.end();
    it--;
    if (-*it < b[x]) {
      sumr += b[x];
      sumr -= -*it;
      r2.insert(*it);
      r1.erase(it);
      r1.insert(-b[x]);
    }
    else
      r2.insert(-b[x]);
  }
}

void remove_r(int x) {
  if (r2.empty()) {
    sumr -= b[x];
    r1.erase(r1.find(-b[x]));
  }
  else {
    it = r2.find(-b[x]);
    if (it != r2.end())
      r2.erase(it);
    else {
      sumr -= b[x];
      r1.erase(r1.find(-b[x]));
    }
  }
}

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL); cout.tie(NULL);
  cin >> n >> m >> s;
  for (int i = 1 ; i <= n ; i++) {
    cin >> a[i] >> b[i];
    id[i] = i;
  }
  sort(id + 1,id + n + 1,[&](int x,int y) {
    if (a[x] - b[x] == a[y] - b[y])
      return a[x] >= a[y];
    return a[x] - b[x] > a[y] - b[y];
  });
  for (int i = 1 ; i <= m ; i++)
    add_l(id[i]);
  for (int i = m + 1 ; i <= n ; i++)
    add_r(id[i]);
  ans = suml + sumr;
  for (int i = m + 1 ; i <= n ; i++) {
    if (n - i < s)
      break;
    add_l(id[i]);
    remove_r(id[i]);
    ans = max(ans,suml + sumr);
  }
  cout << ans << "\n";
}

Compilation message

school.cpp: In function 'void add_l(int)':
school.cpp:17:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (l1.size() < m) {
       ~~~~~~~~~~^~~
school.cpp: In function 'void add_r(int)':
school.cpp:38:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   if (r1.size() < s) {
       ~~~~~~~~~~^~~

Subtask #1
30.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Incorrect 2 ms 508 KB Output isn't correct
5 Incorrect 2 ms 508 KB Output isn't correct
6 Incorrect 2 ms 508 KB Output isn't correct
7 Incorrect 8 ms 748 KB Output isn't correct
8 Correct 5 ms 788 KB Output is correct
9 Incorrect 5 ms 788 KB Output isn't correct
10 Incorrect 5 ms 788 KB Output isn't correct
11 Incorrect 5 ms 788 KB Output isn't correct
12 Incorrect 5 ms 788 KB Output isn't correct
13 Incorrect 33 ms 2632 KB Output isn't correct
14 Incorrect 124 ms 5140 KB Output isn't correct
15 Correct 398 ms 9928 KB Output is correct
16 Correct 180 ms 11088 KB Output is correct
17 Incorrect 247 ms 13548 KB Output isn't correct
18 Incorrect 363 ms 14704 KB Output isn't correct
19 Incorrect 383 ms 15824 KB Output isn't correct
20 Incorrect 459 ms 18164 KB Output isn't correct