Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
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
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.17 / 1.00details
#2ACCEPTED0.11 / 1.00details
#3ACCEPTED0.23 / 1.00details
#4ACCEPTED0.01 / 1.00details
#5ACCEPTED0.02 / 1.00details
#6ACCEPTED0.01 / 1.00details
#7ACCEPTED0.01 / 1.00details
#8ACCEPTED0.01 / 1.00details

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
569566674 738547565
283913539 485985685
848635113 145229239
284162280 70457537
834664867 425433382
166373172 344735042
380649734 563521748
59198302 211605617
330101755 641217228
542560468 590745697
694446248 781321615
440424568 204322852
202346537 545918198
251738430 977201138
717441898 744870810
...
view   save

correct output
58819226961852
view   save

user output
58819226961852
view   save

Test 2

Verdict: ACCEPTED

input
1 1 200000
664293393 446126294
303053683 177744194
130410611 450516458
645484148 777139798
238359810 606932855
931036875 447269440
509877771 834014103
774911311 929284299
538412557 545523797
105635867 911763961
306972224 705642870
131331343 822428336
679405915 586342231
78805185 772937795
747485005 975483491
865441048 30536750
166737008 917234688
771494373 954578450
978220785 855151144
...
view   save

correct output
1999991597
view   save

user output
1999991597
view   save

Test 3

Verdict: ACCEPTED

input
100000 100000 200000
597408010 262805535
561239330 95992085
690324270 432159964
892983528 703183828
685296107 368197489
346037432 799179471
130421341 979212000
404814282 88390270
610652310 440346439
927164316 426213648
814225730 250353793
851846004 454791269
868583682 762309251
596891558 390323480
400723361 798021028
107798026 121457561
844945072 640034679
127464580 838319710
633994968 817234171
...
view   save

correct output
133340028532768
view   save

user output
133340028532768
view   save

Test 4

Verdict: ACCEPTED

input
0 0 1
1 1
view   save

correct output
0
view   save

user output
0
view   save

Test 5

Verdict: ACCEPTED

input
5 0 5
1 10
2 10
3 10
4 10
5 10
view   save

correct output
15
view   save

user output
15
view   save

Test 6

Verdict: ACCEPTED

input
0 5 5
10 1
10 2
10 3
10 4
10 5
view   save

correct output
15
view   save

user output
15
view   save

Test 7

Verdict: ACCEPTED

input
2 0 3
3 1
1 1
2 1
view   save

correct output
5
view   save

user output
5
view   save

Test 8

Verdict: ACCEPTED

input
0 2 3
1 3
1 1
1 2
view   save

correct output
5
view   save

user output
5
view   save