Advertisement
rotti321

Untitled

Mar 8th, 2017
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.32 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. constexpr int maxn = 1010;
  5.  
  6. int v[maxn][maxn], h[maxn] = {}, st[maxn], dr[maxn], stiva[maxn] = {}, poz = -1,
  7.     n, m;
  8.  
  9. ifstream f("hambar.in");
  10. ofstream g("hambar.out");
  11.  
  12. void do_st_dr(){
  13.     stiva[poz=0] = -1;
  14.     for(int i = 0; i < n; ++i){
  15.         while(stiva[poz] != -1 && h[stiva[poz]] >= h[i]) --poz;
  16.         st[i] = stiva[poz]+1;
  17.         stiva[++poz] = i; }
  18.    
  19.     stiva[poz=0] = n;
  20.     for(int i = n-1; i >= 0; --i){
  21.         while(stiva[poz] != n && h[stiva[poz]] >= h[i]) --poz;
  22.         dr[i] = stiva[poz]-1;
  23.         stiva[++poz] = i; } }
  24.  
  25. int main(){
  26.     f >> n >> m;
  27.     for(int i = 0, x, y; i < m; ++i)
  28.         f >> x >> y,
  29.         v[x-1][y-1] = 1;
  30.  
  31.     int rez = 0;
  32.     for(int i = 0; i < n; ++i){
  33.         for(int j = 0; j < n; ++j)
  34.             if(!v[i][j]) ++h[j];
  35.             else h[j] = 0;
  36.         do_st_dr();
  37.         for(int j = 0; j < n; ++j) cout << h[j] << ' ';
  38.         cout << endl;
  39. /**
  40.         for(int j = 0; j < n; ++j) cout << dr[j] << ' ';
  41.         cout << endl;
  42.         cout << endl;
  43. /**
  44.         for(int j = 0; j < n; ++j) cout << dr[j] << ' ';
  45.         cout << endl;
  46.         cout << endl;
  47. **/
  48.         for(int j = 0; j < n; ++j)
  49.             rez = max(rez, h[j] * (dr[j] - st[j] + 1));
  50.     }
  51.     g << rez << endl;
  52.     return 0; }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement