fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <string>
  4. #include <algorithm>
  5. using namespace std;
  6.  
  7. int main(){
  8.     ios::sync_with_stdio(false);
  9.     cin.tie(nullptr);
  10.  
  11.     int t;
  12.     cin >> t;
  13.     while(t--){
  14.         int n, k;
  15.         cin >> n >> k;
  16.         string s;
  17.         cin >> s;
  18.         vector<int> a(n);
  19.         int maxA = 0;
  20.         for (int i = 0; i < n; i++){
  21.             cin >> a[i];
  22.             maxA = max(maxA, a[i]);
  23.         }
  24.  
  25.         auto canAchieve = [&](int X) -> bool {
  26.             int ops = 0;
  27.             for (int i = 0; i < n; ){
  28.                 if(a[i] > X && s[i] == 'R'){
  29.                     i++;
  30.                     continue;
  31.                 }
  32.                 bool needBlue = false;
  33.                 int j = i;
  34.                 while(j < n && !(a[j] > X && s[j]=='R')){
  35.                     if(a[j] > X && s[j]=='B') needBlue = true;
  36.                     j++;
  37.                 }
  38.                 if(needBlue) ops++;
  39.                 i = j;
  40.             }
  41.             return ops <= k;
  42.         };
  43.  
  44.         int lo = 0, hi = maxA, ans = maxA;
  45.         while(lo <= hi){
  46.             int mid = lo + (hi - lo) / 2;
  47.             if(canAchieve(mid)){
  48.                 ans = mid;
  49.                 hi = mid - 1;
  50.             } else {
  51.                 lo = mid + 1;
  52.             }
  53.         }
  54.  
  55.         cout << ans << "\n";
  56.     }
  57.     return 0;
  58. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
5
4 1
BRBR
9 3 5 4
4 1
BRBR
9 5 3 4
4 2
BRBR
9 3 5 4
10 2
BRBRBBRRBR
5 1 2 4 5 3 6 1 5 4
5 5
RRRRR
5 3 1 2 4
stdout
copy 
3
3
0
4
0
https://ideone.com/A2MdA0
language:
C++ (gcc 8.3)
created:
10 days 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!