Advertisement
Guest User

Untitled

a guest
Jun 5th, 2011
144
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.25 KB | None | 0 0
  1. VLL a,s,h,v,sh,sv;
  2. int n,m;
  3. void build() {
  4.     s.assign(n+1,VL(m+1,0));
  5.     sh=sv=h=v=s;
  6.     for (int i=1;i<=n;i++) {
  7.         for (int j=1;j<=m;j++) {
  8.             h[i][j]=a[i][j]*j;
  9.             v[i][j]=a[i][j]*i;
  10.             s[i][j]=a[i][j]+s[i-1][j]+s[i][j-1]-s[i-1][j-1];
  11.             sh[i][j]=h[i][j]+sh[i-1][j]+sh[i][j-1]-sh[i-1][j-1];
  12.             sv[i][j]=v[i][j]+sv[i-1][j]+sv[i][j-1]-sv[i-1][j-1];
  13.         }
  14.     }
  15. }
  16.  
  17. bool getdisk(int x,int y,int r) {
  18.     x++;y++;
  19.     LL hsum=sh[x+r-1][y+r-1]-sh[x-1][y+r-1]-sh[x+r-1][y-1]+sh[x-1][y-1];
  20.     LL vsum=sv[x+r-1][y+r-1]-sv[x-1][y+r-1]-sv[x+r-1][y-1]+sv[x-1][y-1];
  21.     LL sum=s[x+r-1][y+r-1]-s[x-1][y+r-1]-s[x+r-1][y-1]+s[x-1][y-1];
  22.     hsum-=h[x][y]+h[x+r-1][y]+h[x][y+r-1]+h[x+r-1][y+r-1];
  23.     vsum-=v[x][y]+v[x+r-1][y]+v[x][y+r-1]+v[x+r-1][y+r-1];
  24.     sum-=a[x][y]+a[x+r-1][y]+a[x][y+r-1]+a[x+r-1][y+r-1];
  25.     if (2*vsum!=(2*x+r-1)*sum) return 0;
  26.     if (2*hsum!=(2*y+r-1)*sum) return 0;
  27.     return 1;
  28. }
  29.  
  30. void solve() {
  31.     int d;
  32.     cin >> n >> m >> d;
  33.     a.assign(n+1,VL(m+1,0));
  34.     for (int i=1;i<=n;i++) {
  35.         string s;
  36.         cin >> s;
  37.         for (int j=1;j<=m;j++) {
  38.             a[i][j]=s[j-1]-'0'+d;
  39.         }
  40.     }
  41.     build();
  42.     for (int i=min(n,m);i>=3;i--) {
  43.         for (int x=0;x<=n-i;x++)
  44.             for (int y=0;y<=m-i;y++)
  45.                 if (getdisk(x,y,i)) {
  46.                     print(i);
  47.                     return;
  48.                 }
  49.     }  
  50.     print("IMPOSSIBLE");
  51. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement