fork(3) download
copy 
  1. //
  2. // Created by sourabh on 24/2/18.
  3. //
  4.  
  5. #include <bits/stdc++.h>
  6. using namespace std;
  7.  
  8. void solve() {
  9.     long long int n, k;
  10.     // lp and rp are left and right pointers respectively.
  11.     // after both Chef and Chefu complete their turns, total sum will be given by sum of numbers written on the cards
  12.     // in the range [lp, rp]
  13.     long long int sum = 0, rp, lp = 1;
  14.     cin >> n >> k;
  15.     long long int a[n], d[n], b[k];
  16.  
  17.     for(auto &i : a)
  18.         cin >> i;
  19.     for(auto &i : d)
  20.         cin >> i;
  21.     for(auto &i : b)
  22.         cin >> i;
  23.  
  24.     rp = accumulate(d, d + n, 0); // initialise rp to total cards and lp to 1
  25.     for(int i = 0; i < k; ++i) {
  26.         if(i % 2)
  27.             rp = lp + b[i] - 1; // if it Chefu's turn then select first b[k] cards starting from lp 
  28.         else
  29.             lp = rp - b[i] + 1; // if it is Chef's turn then select last b[k] cards starting from rp
  30.     }
  31.  
  32.     pair<long long int, long long int> ar[n];
  33.     for(int i = 0; i < n; ++i) {
  34.         ar[i].first = a[i];
  35.         ar[i].second = d[i];
  36.     }
  37.     // sort cards according to value
  38.     sort(ar, ar + n,[] (pair<long long int, long long int> x, pair<long long int, long long int> y) {
  39.         return x.first < y.first;
  40.     });
  41.  
  42.     // cards_ending_here stores the total card ending at the i'th index
  43.     long long int card_ending_here[n], cards = 0, index = 0;
  44.     for(int i = 0; i < n; ++i) {
  45.         cards += ar[i].second;
  46.         card_ending_here[i] = cards;
  47.         if(card_ending_here[i] < lp)
  48.             ++index;
  49.     }
  50.  
  51.     // while there are still some cards to select
  52.     while(lp <= rp) {
  53.         // if cards at this index are smaller than rp, select all cards falling within this index and increment index
  54.         if(card_ending_here[index] < rp) {
  55.             sum += (card_ending_here[index] - lp + 1) * ar[index].first;
  56.             lp = card_ending_here[index] + 1;
  57.             ++index;
  58.         }
  59.         // else select the remaining cards and increment lp to rp + 1 to indicate selection of all cards    
  60.         else {
  61.             sum += (rp - lp + 1) * ar[index].first;
  62.             lp = rp + 1;
  63.         }
  64.     }
  65.  
  66.     cout << sum << endl;
  67. }
  68.  
  69. int main() {
  70.     int test;
  71.     cin >> test;
  72.  
  73.     while(test--)
  74.         solve();
  75. }
Success #stdin #stdout 0s 4572KB
comments (?)
stdin
copy 
1
4 2
1 2 3 4
2 2 2 2
6 3
stdout
copy 
7
https://ideone.com/EEPDwO
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!