Advertisement
Guest User

Untitled

a guest
Oct 23rd, 2016
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.69 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define ii pair<ll, ll>
  5. #define vi vector<ll>
  6. #define vii vector<ii>
  7. #define each(x) for(auto it = x.begin(); it != x.end(); it++)
  8. #define gc() getchar_unlocked()
  9. #define pc(x) putchar_unlocked(x)
  10.  
  11. #define DEBUG
  12. #ifdef DEBUG
  13.     #define debug(x) cout << #x << " = " << x << endl
  14. #else
  15.     #define debug(x) ;
  16. #endif
  17.  
  18. using namespace std;
  19.  
  20. int mat[305][305];
  21. int R, C, K;
  22.  
  23. int roll(int arr[], int siz) {
  24.     int left = 0, right = 0, cur_sum = 0, min_area = 10000;
  25.    
  26.     while(right < siz) {
  27.         while(cur_sum < K && right < siz) {
  28.             cur_sum += arr[right++];
  29.         }
  30.         while(cur_sum >= K) {
  31.             min_area = min(min_area, right - left);
  32.             cur_sum -= arr[left++];
  33.         }
  34.     }
  35.  
  36.     return (min_area == 10000) ? -1 : min_area;
  37. }
  38.  
  39. void scan_int(int &x);
  40.  
  41. int main() {
  42.     ios_base::sync_with_stdio(false);
  43.  
  44.     while(1) {
  45.         scan_int(R);
  46.         scan_int(C);
  47.         scan_int(K);
  48.         if(!(R | C | K)) {
  49.             break;
  50.         }
  51.  
  52.         memset(mat, 0, sizeof(mat));
  53.         for(int i = 0; i < R; i++) {
  54.             for(int j = 0; j < C; j++) {
  55.                 char c;
  56.                 c = gc();
  57.                 mat[i][j] = c == '.';
  58.             }
  59.             gc();
  60.         }
  61.  
  62.         int best = 100000000;
  63.         int tmp[305];
  64.         for(int i = 0; i < R; i++) {
  65.             memset(tmp, 0, sizeof(tmp));
  66.             for(int j = i; j < R; j++) {
  67.                 for(int k = 0; k < C; k++) {
  68.                     tmp[k] += mat[j][k];
  69.                 }
  70.                 int it = roll(tmp, C);
  71.                 if(it != -1) {
  72.                     best = min(best, it * ((j - i) + 1));
  73.                 }
  74.             }
  75.         }
  76.  
  77.         printf("%d", best);
  78.         pc('\n');
  79.     }      
  80.  
  81.     return 0;
  82. }
  83.  
  84. void scan_int(int &x) {
  85.     register int c = gc();
  86.     x = 0;
  87.     while(c < 48 || c > 57) {
  88.         c = gc();
  89.     }
  90.     for(; c > 47 && c < 58; c = gc()) {
  91.         x = (x << 1) + (x << 3) + c - 48;
  92.     }
  93. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement