Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define MAX 305
- #define oo 0x2f2f2f2f
- using namespace std;
- using ii = pair<int, int>;
- char grid[MAX][MAX];
- int free_seats[MAX][MAX];
- ii subinterval_sum(int* A, int n, int sum) {
- int current_sum = A[1], start = 1, current_length = oo;
- ii subinterval(0, 0);
- for(int i = 2; i <= n + 1; ++i) {
- while(current_sum > sum and start <= i) {
- current_sum -= A[start++];
- }
- if(current_sum >= sum) {
- if(current_length > (i - start)) {
- current_length = i - start;
- subinterval = ii(start, i - 1);
- }
- current_sum -= A[start++];
- }
- if(i <= n) {
- current_sum += A[i];
- }
- }
- return subinterval;
- }
- int main(void) {
- int n, m, k;
- while(scanf("%d %d %d", &n, &m, &k), n | m | k) {
- for(int i = 1; i <= n; ++i) {
- for(int j = 1; j <= m; ++j) {
- scanf(" %c", &grid[i][j]);
- }
- }
- for(int i = 1; i <= n; ++i) {
- for(int j = 1; j <= m; ++j) {
- free_seats[i][j] = grid[i][j] == '.';
- }
- }
- int ans = oo;
- for(int i = 1; i <= m; ++i) {
- int tmp[n + 1]; memset(tmp, 0, sizeof tmp);
- for(int j = i; j <= m; ++j) {
- for(int k = 1; k <= n; ++k) {
- tmp[k] += free_seats[k][j];
- }
- auto s = subinterval_sum(tmp, n, k);
- if(s.first and s.second) {
- ans = min(ans, (s.second - s.first + 1) * (j - i + 1));
- }
- }
- }
- printf("%d\n", ans);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement