fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. #include <algorithm>
  5.  
  6. using namespace std;
  7.  
  8. void solve() {
  9.     int n, q;
  10.     if (!(cin >> n >> q)) return;
  11.     string s;
  12.     cin >> s;
  13.  
  14.     // Precalculation variables
  15.     long long base_val = 0;
  16.     long long base_pairs = 0;
  17.  
  18.     // Gap counts
  19.     long long num_cheap_H = 0; // Type 1: I...I
  20.     long long num_cheap_L = 0; // Type 4: H...H
  21.     long long num_dual = 0;    // Type 2: I...H
  22.     long long total_standard_cap = 0; // Internal capacity for all gaps
  23.  
  24.     long long cnt_q = 0; // Total count of '?'
  25.  
  26.     // Helpers
  27.     auto is_H = [](char c) { return c == 'V' || c == 'X'; };
  28.     auto is_L = [](char c) { return c == 'I'; };
  29.     auto val_char = [](char c) {
  30.         if (c == 'X') return 10;
  31.         if (c == 'V') return 5;
  32.         if (c == 'I') return 1;
  33.         return 0;
  34.     };
  35.  
  36.     // calculate base value and count '?'
  37.     for (int i = 0; i < n; ++i) {
  38.         if (s[i] != '?') {
  39.             base_val += val_char(s[i]);
  40.         } else {
  41.             cnt_q++;
  42.         }
  43.     }
  44.  
  45.     // Count existing pairs in the template string (ignoring '?')
  46.     for (int i = 0; i < n - 1; ++i) {
  47.         if (s[i] == 'I' && (s[i+1] == 'V' || s[i+1] == 'X')) {
  48.             base_pairs++;
  49.         }
  50.     }
  51.  
  52.     // Analyze gaps
  53.     for (int i = 0; i < n; ) {
  54.         if (s[i] == '?') {
  55.             int j = i;
  56.             while (j < n && s[j] == '?') j++;
  57.             long long len = j - i;
  58.  
  59.             // Determine boundaries
  60.             // Virtual 'X' at start, Virtual 'I' at end
  61.             char left = (i == 0) ? 'X' : s[i-1];
  62.             char right = (j == n) ? 'I' : s[j];
  63.  
  64.             bool left_is_L = is_L(left); 
  65.             bool right_is_H = is_H(right); 
  66.  
  67.             if (left_is_L && !right_is_H) { // I ... I (Type 1)
  68.                 num_cheap_H++;
  69.                 if (len > 0) total_standard_cap += (len - 1) / 2;
  70.             } else if (!left_is_L && right_is_H) { // H ... H (Type 4)
  71.                 num_cheap_L++;
  72.                 if (len > 0) total_standard_cap += (len - 1) / 2;
  73.             } else if (left_is_L && right_is_H) { // I ... H (Type 2)
  74.                 num_dual++;
  75.                 if (len > 0) total_standard_cap += (len - 1) / 2;
  76.             } else { // H ... I (Type 3)
  77.                 total_standard_cap += len / 2;
  78.             }
  79.  
  80.             i = j;
  81.         } else {
  82.             i++;
  83.         }
  84.     }
  85.  
  86.     // Process queries
  87.     for (int k = 0; k < q; ++k) {
  88.         long long cX, cV, cI;
  89.         cin >> cX >> cV >> cI;
  90.  
  91.         // Greedy choice of counts to minimize base sum
  92.         long long uI = min(cnt_q, cI);
  93.         long long rem = cnt_q - uI;
  94.         long long uV = min(rem, cV);
  95.         long long uX = rem - uV;
  96.  
  97.         long long N_L = uI;
  98.         long long N_H = uV + uX;
  99.  
  100.         long long current_pairs = base_pairs;
  101.  
  102.         long long cur_cheap_H = num_cheap_H;
  103.         long long cur_cheap_L = num_cheap_L;
  104.         long long rem_dual = num_dual;
  105.  
  106.         // 1. Process Duals (Type 2)
  107.         // Prefer using L because L is usually cheaper/more abundant, 
  108.         // converting Type 2 -> Type 1 (Cheap H opportunity).
  109.         long long use_L_dual = min(rem_dual, N_L);
  110.         current_pairs += use_L_dual;
  111.         N_L -= use_L_dual;
  112.         rem_dual -= use_L_dual;
  113.         cur_cheap_H += use_L_dual; 
  114.  
  115.         // If out of L, use H for remaining duals
  116.         long long use_H_dual = min(rem_dual, N_H);
  117.         current_pairs += use_H_dual;
  118.         N_H -= use_H_dual;
  119.         cur_cheap_L += use_H_dual; // Type 2 -> Type 4 (Cheap L opportunity)
  120.  
  121.         // 2. Process Cheap L slots (Type 4)
  122.         long long use_L = min(cur_cheap_L, N_L);
  123.         current_pairs += use_L;
  124.         N_L -= use_L;
  125.  
  126.         // 3. Process Cheap H slots (Type 1)
  127.         long long use_H = min(cur_cheap_H, N_H);
  128.         current_pairs += use_H;
  129.         N_H -= use_H;
  130.  
  131.         // 4. Process Standard slots (Internal pairs, cost 1L + 1H)
  132.         long long use_std = min({N_L, N_H, total_standard_cap});
  133.         current_pairs += use_std;
  134.  
  135.         long long ans = base_val + uX * 10 + uV * 5 + uI * 1 - 2 * current_pairs;
  136.         cout << ans << "\n";
  137.     }
  138. }
  139.  
  140. int main() {
  141.     ios_base::sync_with_stdio(false);
  142.     cin.tie(NULL);
  143.     int t;
  144.     if (cin >> t) {
  145.         while(t--) {
  146.             solve();
  147.         }
  148.     }
  149.     return 0;
  150. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
4
3 3
???
3 0 0
2 3 1
0 1 2
10 7
??IV?VXIV?
0 0 4
4 4 0
1 1 2
1 1 3
1 1 4
1 2 1
2 2 0
9 5
?V????IVV
9 2 4
4 1 5
0 1 4
4 8 1
3 2 7
3 2
I?V
0 1 0
0 0 1
stdout
copy 
30
9
5
25
43
36
27
25
42
53
19
17
19
33
17
9
5
https://ideone.com/01to3w
language:
C++ (gcc 8.3)
created:
17 hours 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!