1921G - Mischievous Shooter - CodeForces Solution


data structures divide and conquer dp implementation

Please click on ads to support us..

C++ Code:

#include <bits/stdc++.h>
using namespace std;

void run() {
	int n, m, k; cin >> n >> m >> k;

	vector a(min(n, m), vector<int>(max(n, m)));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			char c; cin >> c;
			if (n <= m) a[i][j] += c == '#';
			else a[j][i] += c == '#';
		}
	}
	if (n > m) swap(n, m);

	for (auto& v : a) {
		for (int i = 1; i < m; i++) {
			v[i] += v[i - 1];
		}
	}

	int ans = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			int cur = 0;
			for (int l = 0; l <= k and i + l < n; l++) {
				cur += a[i + l][min(j + k - l, m - 1)] - (j ? a[i + l][j - 1] : 0);
			}
			ans = max(ans, cur);

			cur = 0;
			for (int l = 0; l <= k and i - l >= 0; l++) {
				cur += a[i - l][min(j + k - l, m - 1)] - (j ? a[i - l][j - 1] : 0);
			}
			ans = max(ans, cur);

			cur = 0;
			for (int l = 0; l <= k and i + l < n; l++) {
				cur += a[i + l][j] - (j - k + l > 0 ? a[i + l][j - k + l - 1] : 0);
			}
			ans = max(ans, cur);

			cur = 0;
			for (int l = 0; l <= k and i - l >= 0; l++) {
				cur += a[i - l][j] - (j - k + l > 0 ? a[i - l][j - k + l - 1] : 0);
			}
			ans = max(ans, cur);
		}
	}

	cout << ans << '\n';
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int t; cin >> t; while (t--) run();
}


Comments

Submit
0 Comments
More Questions

1183A - Nearest Interesting Number
1009E - Intercity Travelling
1637B - MEX and Array
224A - Parallelepiped
964A - Splits
1615A - Closing The Gap
4C - Registration System
1321A - Contest for Robots
1451A - Subtract or Divide
1B - Spreadsheet
1177A - Digits Sequence (Easy Edition)
1579A - Casimir's String Solitaire
287B - Pipeline
510A - Fox And Snake
1520B - Ordinary Numbers
1624A - Plus One on the Subset
350A - TL
1487A - Arena
1520D - Same Differences
376A - Lever
1305A - Kuroni and the Gifts
1609A - Divide and Multiply
149B - Martian Clock
205A - Little Elephant and Rozdil
1609B - William the Vigilant
978B - File Name
1426B - Symmetric Matrix
732B - Cormen --- The Best Friend Of a Man
1369A - FashionabLee
1474B - Different Divisors