Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 14:49:47
2018-05-26 14:48:15
2018-05-26 14:39:19
2018-05-26 14:25:08
2018-05-26 14:18:52
Task:Jobs
Sender:Wave of Technology
Submission time:2018-05-26 14:49:47
Status:READY
Result:ACCEPTED

Show test data

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;
}