CSES - HIIT Open 2018 - Results
Submission details
Task:Jobs
Sender:Wave of Technology
Submission time:2018-05-26 14:39:19 +0300
Language:C++
Status:READY
Result:
Test results
testverdicttime
#1ACCEPTED0.15 sdetails
#2ACCEPTED0.11 sdetails
#3ACCEPTED0.26 sdetails
#4--details
#5--details
#6--details
#7--details
#8--details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:60:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (avals.size() < a || sa[i] > small) {
         ~~~~~~~~~~~~~^~~
input/code.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (avals.size() == a) {
           ~~~~~~~~~~~~~^~~~
input/code.cpp:76:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (bvals.size() < b || sb[i] > small) {
         ~~~~~~~~~~~~~^~~
input/code.cpp:78:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (bvals.size() == b) {
           ~~~~~~~~~~~~~^~~~

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PLL;

const ll INF = 1000000000000000LL;

ll n;

template<typename T>
void print_vector(vector<T> & v) {
  for (auto x : v) {
    cout << x << " ";
  }
}


int main() {

  cin.tie(NULL);
  std::ios::sync_with_stdio(false);

  ll a, b;
  cin >> a >> b;

  cin >> n;

  
  vector<ll> satmp (n);
  vector<ll> sbtmp (n);

  vector<PLL> diffs (n);
  
  for (int i=0; i<n; i++) {
    cin >> satmp[i];
    cin >> sbtmp[i];
    diffs[i].first = sbtmp[i]-satmp[i];
    diffs[i].second = i;
  }


  sort(diffs.begin(), diffs.end());

  vector<ll> bestb (n, 0);
  vector<ll> besta (n, 0);

  vector<ll> sa (n);
  vector<ll> sb (n);
  for (int i=0; i<n; i++) {
    sa[i] = satmp[diffs[i].second];
    sb[i] = sbtmp[diffs[i].second];
  }
  
  multiset<ll> avals;
  ll asum = 0;
  for (int i=0; i<n; i++) {
    ll small = *avals.begin();
    if (avals.size() < a || sa[i] > small) {
      asum += sa[i];
      if (avals.size() == a) {
	asum -= small;
	avals.erase(avals.begin());
      }
      avals.insert(sa[i]);
    }
    besta[i] = asum;
    //    cout << "sa: " << sa[i] << " asum: " << asum << endl;
  }

  multiset<ll> bvals;
  ll bsum = 0;
  for (int i=n-1; i>=0; i--) {
    ll small = *bvals.begin();
    if (bvals.size() < b || sb[i] > small) {
      bsum += sb[i];
      if (bvals.size() == b) {
	bsum -= small;
	bvals.erase(bvals.begin());
      }
      bvals.insert(sb[i]);
    }
    bestb[i] = bsum;
    //    cout << "sb: " << sb[i] << " bsum: " << bsum << endl;
  }

  ll res = 0;
  for (int i=a-1; i+b<n; i++) {
    res = max(res, besta[i] + bestb[i+1]);
  }
  
  cout << res << endl;
  
  return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
12345 54321 200000
159509898 981869288
727914829 812494607
382740364 106927167
291351532 356889470
...

correct output
58819226961852

user output
58819226961852

Test 2

Verdict: ACCEPTED

input
1 1 200000
664293393 446126294
303053683 177744194
130410611 450516458
645484148 777139798
...

correct output
1999991597

user output
1999991597

Test 3

Verdict: ACCEPTED

input
100000 100000 200000
597408010 262805535
561239330 95992085
690324270 432159964
892983528 703183828
...

correct output
133340028532768

user output
133340028532768

Test 4

Verdict:

input
0 0 1
1 1

correct output
0

user output
(empty)

Test 5

Verdict:

input
5 0 5
1 10
2 10
3 10
4 10
...

correct output
15

user output
(empty)

Test 6

Verdict:

input
0 5 5
10 1
10 2
10 3
10 4
...

correct output
15

user output
(empty)

Test 7

Verdict:

input
2 0 3
3 1
1 1
2 1

correct output
5

user output
(empty)

Test 8

Verdict:

input
0 2 3
1 3
1 1
1 2

correct output
5

user output
(empty)