codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

1985.md (20005B)


      1 Source: https://codeforces.com/blog/entry/129620
      2 
      3 This was our first time setting a Div.4 contest. We sincerely hope you enjoyed the problems!
      4 
      5 ##### [1985A - Creating Words](/contest/1985/problem/A "Codeforces Round 952 (Div. 4)")
      6 
      7 Problem Credits: [cry](/profile/cry "Master cry")   
      8  Analysis: [cry](/profile/cry "Master cry")
      9 
     10 **Solution**
     11 
     12 To swap the first character of the strings, you can use the built-in method std::swap in C++, or for each string, separate the first character from the rest of the string and concatenate it with the other string.
     13 
     14 **Code (C++)**
     15 
     16 ```
     17 #include <bits/stdc++.h>
     18 using namespace std;
     19 
     20 int main(){
     21 	int t; cin >> t;
     22 	while(t--){
     23 		string a, b; cin >> a >> b;
     24 		swap(a[0], b[0]);
     25 		cout << a << " " << b << endl;
     26 	}
     27 }
     28 ```
     29 
     30 ##### [1985B - Maximum Multiple Sum](/contest/1985/problem/B "Codeforces Round 952 (Div. 4)")
     31 
     32 Problem Credits: [cry](/profile/cry "Master cry")   
     33  Analysis: [cry](/profile/cry "Master cry")
     34 
     35 **Solution**
     36 
     37 To maximize the number of multiples of $x$ less than $n$, it optimal to choose a small $x$, in this case, $2$. The only exception is $n = 3$, where it is optimal to choose $3$ instead, since both $2$ and $3$ have only one multiple less than $3$.
     38 
     39 **Code (C++)**
     40 
     41 ```
     42 #include <bits/stdc++.h>
     43 using namespace std;
     44 
     45 int main(){
     46 	int t; cin >> t;
     47 	while(t--){
     48 		int n; cin >> n;
     49 		cout << (n == 3 ? 3 : 2) << endl;
     50  	}
     51 }
     52 ```
     53 
     54 ##### [1985C - Good Prefixes](/contest/1985/problem/C "Codeforces Round 952 (Div. 4)")
     55 
     56 Problem Credits: [sum](/profile/sum "Master sum")   
     57  Analysis: [cry](/profile/cry "Master cry")
     58 
     59 **Solution**
     60 
     61 The only element that can be the sum of all other elements is the maximum element, since all elements are positive. Therefore, for each prefix $i$ from $1$ to $n$, check if $sum(a_1, a_2, ..., a_i) - max(a_1, a_2, ..., a_i) = max(a_1, a_2, ..., a_i)$. The sum and max of prefixes can be tracked with variables outside the loop.
     62 
     63 **Code (C++)**
     64 
     65 ```
     66 #include <iostream>
     67 using namespace std;
     68 
     69 int main(){
     70 	int t; cin >> t;
     71 	while(t--){
     72 		int n; cin >> n;
     73 		int a[n];
     74 		for(int i = 0; i < n; i++)
     75 			cin >> a[i];
     76 		long long sum = 0;
     77 		int mx = 0, ans = 0;;
     78 		for(int i = 0; i < n; i++){
     79 			sum += a[i];
     80 			mx = max(mx, a[i]);
     81 			if(sum - mx == mx) 
     82 				ans++;
     83 		}
     84 		cout << ans << endl;
     85 	}
     86 }
     87 ```
     88 
     89 ##### [1985D - Manhattan Circle](/contest/1985/problem/D "Codeforces Round 952 (Div. 4)")
     90 
     91 Problem Credits: [cry](/profile/cry "Master cry")   
     92  Analysis: [cry](/profile/cry "Master cry")
     93 
     94 **Solution**
     95 
     96 Note that the manhattan circle is always in a diamond shape, symmetric from the center. Let's take notice of some special characteristics that can help us. One way is to find the top and bottom points of the circle. Note that these points will have columns at the center of the circle, so here we can acquire the value of $k$. To find $h$, since the circle is symmetric, it is just the middle of the rows of the top and bottom points.
     97 
     98 Note that we never needed to find the value of $r$.
     99 
    100 **Code (C++)**
    101 
    102 ```
    103 #include <bits/stdc++.h>
    104 using namespace std;
    105 const int INF = 1e9;
    106 
    107 int main(){
    108 	int t; cin >> t;
    109 	while(t--){
    110 		int n, m; cin >> n >> m;
    111 		vector<vector<char>> g(n, vector<char>(m));
    112 		for(int i = 0; i < n; i++){
    113 			for(int j = 0; j < m; j++){
    114 				cin >> g[i][j];
    115 			}
    116 		}
    117 		pair<int, int> top = {INF, INF}, bottom = {-INF, -INF};
    118 		for(int i = 0; i < n; i++){
    119 			for(int j = 0; j < m; j++){
    120 				if(g[i][j] == '#'){
    121 					top = min(top, {i, j});
    122 					bottom = max(bottom, {i, j});
    123 				}
    124 			}
    125 		}
    126 		assert(top.second == bottom.second);
    127 		cout << (top.first + bottom.first) / 2 + 1 << " " << top.second + 1 << endl;
    128 	}
    129 }
    130 ```
    131 
    132 ##### [1985E - Secret Box](/contest/1985/problem/E "Codeforces Round 952 (Div. 4)")
    133 
    134 Problem Credits: [cry](/profile/cry "Master cry")   
    135  Analysis: [cry](/profile/cry "Master cry")
    136 
    137 **Solution**
    138 
    139 Since the side lengths of $S$ has to multiply to $k$, all three side lengths of $S$ has to be divisors of $k$. Let's denote the side lengths of $S$ along the $x$, $y$, and $z$ axes as $a$, $b$, and $c$ respectively. For $S$ to fit in $B$ , $a \leq x$, $b \leq y$, and $c \leq z$ must hold. Because of the low constraints, we can afford to loop through all possible values of $a$ and $b$, and deduce that $c=\frac{k}{a \cdot b}$ (make sure $c \leq z$ and $c$ is an integer). To get the amount of ways we can place $S$, we can just multiply the amount of shifting space along each axes, and that just comes down to $(x−a+1) \cdot (y−b+1) \cdot (z−c+1)$. The answer is the maximum among all possible values of $a$, $b$, and $c$ .
    140 
    141 The time complexity is $\mathcal{O}(n^2)$ where $n$ is at most $2000$.
    142 
    143 **Code (C++)**
    144 
    145 ```
    146 #include <iostream>
    147 using namespace std;
    148 using ll = long long;
    149 
    150 int main(){
    151 	int t; cin >> t;
    152 	while(t--){
    153 		ll x, y, z, k; cin >> x >> y >> z >> k;
    154 		ll ans = 0;
    155 		for(int a = 1; a <= x; a++){
    156 			for(int b = 1; b <= y; b++){
    157 				if(k % (a * b)) continue;
    158 				ll c = k / (a * b);
    159 				if(c > z) continue;
    160 				ll ways = (ll)(x - a + 1) * (y - b + 1) * (z - c + 1);
    161 				ans = max(ans, ways);
    162 			}
    163 		}
    164 		cout << ans << "\n";
    165 	}
    166 }
    167 ```
    168 
    169 ##### [1985F - Final Boss](/contest/1985/problem/F "Codeforces Round 952 (Div. 4)")
    170 
    171 Problem Credits: [cry](/profile/cry "Master cry"), [sum](/profile/sum "Master sum")   
    172  Analysis: [cry](/profile/cry "Master cry"), [sum](/profile/sum "Master sum")
    173 
    174 **About Hacks**
    175 
    176 Unfortunately, there was a lot of hacks on this problem, and we're sorry for it. Since our intended solution is not binary search, we didn't really take overflow using binary search seriously. I ([cry](/profile/cry "Master cry")) prepared this problem and I only took into account about overflow with big cooldown, but I forgot overflow can happen on attacks as well. I apologize and we will do better next time!
    177 
    178 **Solution**
    179 
    180 Since the sum of $h$ is bounded by $2 \cdot 10^5$, and each attack deals at least $1$ damage. If we assume every turn we can make at least one attack, the sum of turns to kill the boss in every test case is bounded by $2 \cdot 10^5$. This means that we can afford to simulate each turn where we make at least one attack.
    181 
    182 But what if we cannot make an attack on this turn? Since the cooldown for each attack can be big, we cannot increment turns one by one. We must jump to the next turn we can make an attack. This can be done by retrieving the first element of a sorted set, where the set stores pairs {$t$, $i$} which means {next available turn you can use this attack, index of this attack} for all $i$. Here, we can set the current turn to $t$ and use all attacks in the set with first element in the pair equal to $t$. Remember to insert the pair to {$c_i + t$, $i$} back into the set after processing the attacks.
    183 
    184 The time complexity is $\mathcal{O}(h \log n)$.
    185 
    186 **Code (C++)**
    187 
    188 ```
    189 #include <bits/stdc++.h>
    190 using namespace std;
    191 
    192 int main(){
    193 	int t; cin >> t;
    194 	while(t--){
    195 		int h, n; cin >> h >> n;
    196 		vector<int> a(n), c(n);
    197 		for(int& i: a) cin >> i;
    198 		for(int& i: c) cin >> i;
    199 		set<pair<long long, int>> S;
    200 		for(int i = 0; i < n; i++){
    201 			S.insert({1, i});
    202 		}
    203 		long long last_turn = 1;
    204 		while(h > 0){
    205 			auto [turn, i] = *S.begin();
    206 			S.erase(S.begin());
    207 			last_turn = turn;
    208 			h -= a[i];
    209 			S.insert({turn + c[i], i});
    210 		}
    211 		cout << last_turn << "\n";
    212 	}
    213 }
    214 
    215 // comment "tomato" if you see this comment
    216 ```
    217 
    218 **Bonus**
    219 
    220 Try to solve this if $1 \le h \le 10^9$.
    221 
    222 **Solution**
    223 
    224 We can do this by binary searching for the answer. For some time $t$, we know that we can perform an attack of cooldown $c$ exactly $\lfloor \frac{t - 1}{c} \rfloor + 1$ times. The total damage we will do in time $t$ will be:
    225 
    226 $ \displaystyle \sum_{i=1}^{n}{a_i\left( \lfloor\frac{t - 1}{c_i}\rfloor + 1 \right)} $
    227 
    228 So we binary search for the first $t$ such that the total damage we do in time $t$ is greater than or equal to $h$. This runs in $\mathcal{O(n \log {(h \cdot \max c_i)})}$. Be careful of long long overflow!
    229 
    230 **Code (C++)**
    231 
    232 ```
    233 #include <bits/stdc++.h>
    234 using namespace std;
    235 
    236 #define ll long long
    237 
    238 void solve(){
    239     ll h, n;
    240     cin >> h >> n;
    241 
    242     vector<ll> A(n), C(n);
    243 
    244     for (ll &i : A)
    245         cin >> i;
    246     for (ll &i : C)
    247         cin >> i;
    248     
    249     auto chk = [&](ll t){
    250         ll dmg = 0;
    251         for (int i = 0; i < n and dmg < h; i++){
    252             ll cnt = (t - 1) / C[i] + 1;
    253 
    254             if (cnt >= h)
    255                 return true;
    256 
    257             dmg += cnt * A[i];
    258         }
    259         return dmg >= h;
    260     };
    261 
    262     ll L = 1, H = 1e12;
    263 
    264     while (L < H){
    265         ll M = (L + H) / 2;
    266         chk(M) ? H = M : L = M + 1;
    267     }
    268     cout << L << "\n";
    269 }
    270 
    271 int main(){
    272     ios_base::sync_with_stdio(0); cin.tie(0); 
    273     int tc;
    274     cin >> tc;
    275 
    276     while (tc--)
    277         solve();
    278 }
    279 ```
    280 
    281 ##### [1985G - D-Function](/contest/1985/problem/G "Codeforces Round 952 (Div. 4)")
    282 
    283 Problem Credits: [cry](/profile/cry "Master cry")   
    284  Analysis: [cry](/profile/cry "Master cry")
    285 
    286 **Solution**
    287 
    288 To satisfy $D(k \cdot n) = k \cdot D(n)$, each digit $d$ in $n$ must become $k \cdot d$ after multiplying $n$ by $k$. In other words, none of $n$'s digits can carry over to the next digit upon multiplication. From this, we can deduce that each digit in $n$ must be less than or equal to $\lfloor \frac{9}{k} \rfloor$. Only thing left is to count all such numbers in the range of $10^l$ inclusive and $10^r$ exclusive.
    289 
    290 Every number below ${10}^r$ has $r$ or less digits. For numbers with less than $r$ digits, let's pad the beginning with zeroes until it becomes a $r$ digit number (for example, if $r = 5$, then $69$ becomes $00069$). This allows us to consider numbers with less than $r$ digits the same way as numbers with exactly $r$ digits. For each digit, we have $\lfloor \frac{9}{k} \rfloor + 1$ choices (including zero), and there are $r$ digits, so the total number of numbers that satisfies the constraint below ${10}^r$ is $(\lfloor \frac{9}{k} \rfloor + 1)^r$.
    291 
    292 To get the count of numbers in range, it suffices to subtract all valid numbers less than $10^l$. Therefore, the answer is $(\lfloor \frac{9}{k} \rfloor + 1)^r - (\lfloor \frac{9}{k} \rfloor + 1)^l$. To exponentiate fast, we can use [modular exponentiation](https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/).
    293 
    294 **Code (Python)**
    295 
    296 ```
    297 MOD = int(1e9+7)
    298 t = int(input())
    299 for _ in range(t):
    300     l, r, k = map(int, input().split())
    301     print((pow(9 // k + 1, r, MOD) - pow(9 // k + 1, l, MOD) + MOD) % MOD)
    302 ```
    303 
    304 ##### [1985H1 - Maximize the Largest Component (Easy Version)](/contest/1985/problem/H1 "Codeforces Round 952 (Div. 4)")
    305 
    306 Problem Credits: [sum](/profile/sum "Master sum")   
    307  Analysis: [sum](/profile/sum "Master sum")
    308 
    309 **Solution**
    310 
    311 Let's first solve the problem if we can only select and fill **rows**. Columns can be handled in the exact same way.
    312 
    313 For each row $r$, we need to find the size of the component formed by filling row $r$ (i.e. the size of the component **containing** row $r$ if we set all cells in row $r$ to be $\texttt{#}$).
    314 
    315 The size of the component **containing** row $r$ if we set all cells in row $r$ to be $\texttt{#}$ will be the **sum** of:
    316 
    317 1. The number of $\texttt{.}$ in row $r$ since these cells will be set to $\texttt{#}$. Let $F_r$ denote this value for some row $r$.
    318 2. The sum of sizes of components containing a cell in either row $r-1$, $r$, or $r+1$ (i.e. components that are touching row $r$). This is since these components will be part of the component containing row $r$. Let $R_r$ denote this value for some row $r$.
    319 
    320 The challenge is computing the second term quickly. For some component, let $s$ be the size of the component and let $r_{min}$ and $r_{max}$ denote the minimum and maximum row of a cell in the component. This means that the component will contain cells with rows $r_{min},r_{min+1},...,r_{max}$. Note that we can find these values with a dfs. Since the component will contribute $s$ to rows in $[r_{min}-1,r_{min},\ldots r_{max}+1]$, we add $s$ to $R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$. This can be done naively or with prefix sums.
    321 
    322 We find the maximum $F_r+R_r$ and then handle columns in the same way. This solution runs in $\mathcal{O}(nm)$ time.
    323 
    324 **Code (C++)**
    325 
    326 ```
    327 #include <bits/stdc++.h>
    328 using namespace std;
    329 
    330 int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 
    331 vector<vector<bool>> vis; vector<vector<char>> A;
    332 
    333 void dfs(int i, int j){
    334     if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
    335         return;
    336     
    337     vis[i][j] = true;
    338 
    339     sz++;
    340     minR = min(minR, i);
    341     maxR = max(maxR, i);
    342     minC = min(minC, j);
    343     maxC = max(maxC, j);
    344 
    345     dfs(i - 1, j);
    346     dfs(i + 1, j);
    347     dfs(i, j - 1);
    348     dfs(i, j + 1);
    349 }
    350 
    351 void solve(){
    352     cin >> n >> m;
    353 
    354     R.assign(n + 5, 0);
    355     C.assign(m + 5, 0);
    356     freeR.assign(n + 5, 0);
    357     freeC.assign(m + 5, 0);
    358     vis.assign(n + 5, vector<bool>(m + 5, false));
    359     A.assign(n + 5, vector<char>(m + 5, ' '));
    360 
    361     for (int i = 1; i <= n; i++){
    362         for (int j = 1; j <= m; j++){
    363             cin >> A[i][j];
    364 
    365             if (A[i][j] == '.'){
    366                 freeR[i]++;
    367                 freeC[j]++;
    368             }
    369         }
    370     }
    371     
    372     for (int i = 1; i <= n; i++){
    373         for (int j = 1; j <= m; j++){
    374             if (vis[i][j] or A[i][j] == '.')
    375                 continue;
    376 
    377             // Reset
    378             sz = 0;
    379             minR = 1e9;
    380             maxR = -1e9;
    381             minC = 1e9;
    382             maxC = -1e9;
    383 
    384             dfs(i, j);
    385 
    386             // Expand by 1 since adjacent cells also connect
    387             minR = max(minR - 1, 1);
    388             maxR = min(maxR + 1, n);
    389             minC = max(minC - 1, 1);
    390             maxC = min(maxC + 1, m);
    391             
    392             // Update prefix sums
    393             R[minR] += sz;
    394             R[maxR + 1] -= sz;
    395 
    396             C[minC] += sz;
    397             C[maxC + 1] -= sz;
    398         }
    399     }
    400 
    401     ans = 0;
    402 
    403     for (int i = 1; i <= n; i++){
    404         R[i] += R[i - 1];
    405         ans = max(ans, freeR[i] + R[i]);
    406     }
    407     for (int i = 1; i <= m; i++){
    408         C[i] += C[i - 1];
    409         ans = max(ans, freeC[i] + C[i]);
    410     }
    411 
    412     cout << ans << "\n";
    413 }
    414 
    415 int main(){
    416     ios_base::sync_with_stdio(0); cin.tie(0);
    417     int tc;
    418     cin >> tc;
    419 
    420     while (tc--)
    421         solve();
    422 }
    423 ```
    424 
    425 ##### [1985H2 - Maximize the Largest Component (Hard Version)](/contest/1985/problem/H2 "Codeforces Round 952 (Div. 4)")
    426 
    427 Problem Credits: [sum](/profile/sum "Master sum")   
    428  Analysis: [sum](/profile/sum "Master sum")
    429 
    430 **Solution**
    431 
    432 For each row $r$ and column $c$, we need to find the size of the component formed by filling both row $r$ and column $c$ (i.e. the size of the component **containing** row $r$ and column $c$ if we set all cells in both row $r$ and column $c$ to be $\texttt{#}$).
    433 
    434 Extending the reasoning in H1, for some row $r$ and column $c$, consider the sum of:
    435 
    436 1. The number of $\texttt{.}$ in row $r$ or column $c$ since these cells will be set to $\texttt{#}$. Let $F_{r,c}$ denote this value for some row $r$ and column $c$.
    437 2. The sum of sizes of components containing a cell in either row $r-1$, $r$, or $r+1$ (i.e. components that are touching row $r$). This is since these components will be part of the component containing row $r$ and column $c$. Let $R_r$ denote this value for some row $r$.
    438 3. The sum of sizes of components containing a cell in either column $c-1$, $c$, or $c+1$ (i.e. components that are touching column $c$). This is since these components will be part of the component containing row $r$ and column $c$. Let $C_c$ denote this value for some column $c$.
    439 
    440 However, components that contain a cell in either row $r-1$, $r$, or $r+1$ as well as in either column $c-1$, $c$, or $c+1$ will be **overcounted** (since it will be counted in both terms $2$ and $3$) (you can think of it as components touching both row $r$ and column $c$). Thus, we need to subtract the sum of sizes of components that contain a cell in either row $r-1$, $r$, or $r+1$ as well as in either column $c-1$, $c$, or $c+1$. Let $B_{r,c}$ denote this for some row $r$ and column $c$.
    441 
    442 Then the size of the component formed by filling both row $r$ and column $c$ will be $F_{r,c}+R_r+C_c-B_{r,c}$ and we want to find the maximum value of this.
    443 
    444 Let's try to calculate these values efficiently. Consider some component.
    445 
    446 1. Let $s$ be its size.
    447 2. Let $r_{min}$ and $r_{max}$ denote the minimum and maximum row of a cell in the component. This means that the component contains cells with rows $r_{min},r_{min+1},...,r_{max}$.
    448 3. Let $c_{min}$ and $c_{max}$ denote the minimum and maximum column of a cell in the component. This means that the component contains cells with columns $c_{min},c_{min+1},...,c_{max}$.
    449 
    450 All these values can be found with a dfs. We then do the following updates:
    451 
    452 1. Add $s$ to $R_{r_{min}-1},R_{r_{min}},\ldots,R_{r_{max}+1}$. This can be done naively or with prefix sums.
    453 2. Add $s$ to $C_{c_{min}-1},C_{c_{min}},\ldots,C_{c_{max}+1}$. This can be done naively or with prefix sums.
    454 3. Add $s$ to the subrectangle of $B$ with top left at ($r_{min}-1,c_{min}-1$) and bottom right at ($r_{max}+1,c_{max}+1$). This can be done with 2D prefix sums. (Note that doing this naively will pass because of low constant factor and the fact that we could not cut this solution without cutting slow correct solutions.)
    455 
    456 We do this for each component. Also, calculating $F_{r,c}$ can be done by looking at the number of $\texttt{.}$ in row $r$, column $c$, and checking whether we overcounted a $\texttt{.}$ at ($r,c$). In all, this solution runs in $\mathcal{O}(nm)$ time.
    457 
    458 **Code (C++)**
    459 
    460 ```
    461 #include <bits/stdc++.h>
    462 using namespace std;
    463 
    464 int n, m, minR, maxR, minC, maxC, sz, ans; vector<int> R, C, freeR, freeC; 
    465 vector<vector<int>> RC; vector<vector<bool>> vis; vector<vector<char>> A;
    466 
    467 void dfs(int i, int j){
    468     if (i <= 0 or i > n or j <= 0 or j > m or vis[i][j] or A[i][j] == '.')
    469         return;
    470     
    471     vis[i][j] = true;
    472 
    473     sz++;
    474     minR = min(minR, i);
    475     maxR = max(maxR, i);
    476     minC = min(minC, j);
    477     maxC = max(maxC, j);
    478 
    479     dfs(i - 1, j);
    480     dfs(i + 1, j);
    481     dfs(i, j - 1);
    482     dfs(i, j + 1);
    483 }
    484 
    485 void solve(){
    486     cin >> n >> m;
    487 
    488     R.assign(n + 5, 0);
    489     C.assign(m + 5, 0);
    490     freeR.assign(n + 5, 0);
    491     freeC.assign(m + 5, 0);
    492     RC.assign(n + 5, vector<int>(m + 5, 0));
    493     vis.assign(n + 5, vector<bool>(m + 5, false));
    494     A.assign(n + 5, vector<char>(m + 5, ' '));
    495 
    496     for (int i = 1; i <= n; i++){
    497         for (int j = 1; j <= m; j++){
    498             cin >> A[i][j];
    499 
    500             if (A[i][j] == '.'){
    501                 freeR[i]++;
    502                 freeC[j]++;
    503             }
    504         }
    505     }
    506     
    507     for (int i = 1; i <= n; i++){
    508         for (int j = 1; j <= m; j++){
    509             if (vis[i][j] or A[i][j] == '.')
    510                 continue;
    511 
    512             // Reset
    513             sz = 0;
    514             minR = 1e9;
    515             maxR = -1e9;
    516             minC = 1e9;
    517             maxC = -1e9;
    518 
    519             dfs(i, j);
    520 
    521             // Expand by 1 since adjacent cells also connect
    522             minR = max(minR - 1, 1);
    523             maxR = min(maxR + 1, n);
    524             minC = max(minC - 1, 1);
    525             maxC = min(maxC + 1, m);
    526             
    527             // Update prefix sums
    528             R[minR] += sz;
    529             R[maxR + 1] -= sz;
    530 
    531             C[minC] += sz;
    532             C[maxC + 1] -= sz;
    533 
    534             RC[minR][minC] += sz;
    535             RC[maxR + 1][minC] -= sz;
    536             RC[minR][maxC + 1] -= sz;
    537             RC[maxR + 1][maxC + 1] += sz;
    538         }
    539     }
    540 
    541     for (int i = 1; i <= n; i++)
    542         R[i] += R[i - 1];
    543 
    544     for (int i = 1; i <= m; i++)
    545         C[i] += C[i - 1];
    546 
    547     for (int i = 1; i <= n; i++)
    548         for (int j = 1; j <= m; j++)
    549             RC[i][j] += RC[i - 1][j] + RC[i][j - 1] - RC[i - 1][j - 1];
    550     
    551     ans = 0;
    552 
    553     for (int i = 1; i <= n; i++)
    554         for (int j = 1; j <= m; j++)
    555             ans = max(ans, (R[i] + C[j] - RC[i][j]) + (freeR[i] + freeC[j] - (A[i][j] == '.')));
    556     
    557     cout << ans << "\n";
    558 }
    559 
    560 int main(){
    561     ios_base::sync_with_stdio(0); cin.tie(0);
    562     int tc;
    563     cin >> tc;
    564 
    565     while (tc--)
    566         solve();
    567 }
    568 ```