Jobs

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) {
           ~~~~~~~~~~~~~^~~~

#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 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: TIME LIMIT EXCEEDED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED