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

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:62:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (avals.size() < a || sa[i] > small) {
           ~~~~~~~~~~~~~^~~
input/code.cpp:64:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (avals.size() == a) {
      ~~~~~~~~~~~~~^~~~
input/code.cpp:81:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       if (bvals.size() < b || sb[i] > small) {
           ~~~~~~~~~~~~~^~~
input/code.cpp:83:19: 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];
  }

  if (a>0) {
    multiset<ll> avals;
    avals.insert(0);
    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;
    }
  }
    
  if (b>0) {
    multiset<ll> bvals;
    bvals.insert(0);
    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;
    }
  }

  if (a==0 && b==n) {
    cout << bestb[0] << endl;
    return 0;
  }
  if (a==n && b==0) {
    cout << besta[n-1] << endl;
    return 0;
  }
  
  bestb.push_back(0);
  ll res = 0;
  for (int i=max(0LL,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: ACCEPTED

input
0 0 1
1 1

correct output
0

user output
0

Test 5

Verdict: ACCEPTED

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

correct output
15

user output
15

Test 6

Verdict: ACCEPTED

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

correct output
15

user output
15

Test 7

Verdict: ACCEPTED

input
2 0 3
3 1
1 1
2 1

correct output
5

user output
5

Test 8

Verdict: ACCEPTED

input
0 2 3
1 3
1 1
1 2

correct output
5

user output
5