Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2016
68
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.37 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define MAX 305
  4. #define oo  0x2f2f2f2f
  5.  
  6. using namespace std;
  7. using ii = pair<int, int>;
  8.  
  9. char grid[MAX][MAX];
  10. int  free_seats[MAX][MAX];
  11.  
  12. ii subinterval_sum(int* A, int n, int sum) {
  13.     int current_sum = A[1], start = 1, current_length = oo;
  14.     ii  subinterval(0, 0);
  15.     for(int i = 2; i <= n + 1; ++i) {
  16.         while(current_sum > sum and start <= i) {
  17.             current_sum -= A[start++];
  18.         }
  19.         if(current_sum >= sum) {
  20.             if(current_length > (i - start)) {
  21.                 current_length = i - start;
  22.                 subinterval = ii(start, i - 1);
  23.             }
  24.             current_sum -= A[start++];
  25.         }
  26.         if(i <= n) {
  27.             current_sum += A[i];
  28.         }
  29.     }
  30.     return subinterval;
  31. }
  32.  
  33. int main(void) {
  34.     int n, m, k;
  35.     while(scanf("%d %d %d", &n, &m, &k), n | m | k) {
  36.         for(int i = 1; i <= n; ++i) {
  37.             for(int j = 1; j <= m; ++j) {
  38.                 scanf(" %c", &grid[i][j]);
  39.             }
  40.         }
  41.  
  42.         for(int i = 1; i <= n; ++i) {
  43.             for(int j = 1; j <= m; ++j) {
  44.                 free_seats[i][j] = grid[i][j] ==  '.';
  45.             }
  46.         }
  47.  
  48.         int ans = oo;
  49.         for(int i = 1; i <= m; ++i) {
  50.             int tmp[n + 1]; memset(tmp, 0, sizeof tmp);
  51.             for(int j = i; j <= m; ++j) {
  52.                 for(int k = 1; k <= n; ++k) {
  53.                     tmp[k] += free_seats[k][j];
  54.                 }
  55.                 auto s = subinterval_sum(tmp, n, k);
  56.                 if(s.first and s.second) {
  57.                     ans = min(ans, (s.second - s.first + 1) * (j - i + 1));
  58.                 }
  59.             }  
  60.         }
  61.         printf("%d\n", ans);
  62.     }
  63.     return 0;
  64. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement