1 #include<cstdlib>  2 #include<cstdio>  3 #include<algorithm>  4 #include<cstring>  5 #include<iostream>  6 #include<map>  7 using namespace std;  8 const int maxn = 510, maxs = maxn * maxn * 5,inf = 0x3f3f3f3f;  9 const int dx[] = {0,0,0,1,1}, 10        dy[] = {0,0,1,0,1}; 11 int ct; 12 struct SEG{ 13     int sg[maxs * 3],tag[maxs * 3]; 14     void down(int x){ 15         if(tag[x]){ 16             sg[x << 1] = max(sg[x << 1], tag[x]); 17             sg[x << 1|1] = max(sg[x << 1|1], tag[x]); 18             tag[x << 1] = max(tag[x << 1], tag[x]); 19             tag[x <<1|1] = max(tag[x << 1|1], tag[x]); 20             tag[x] = 0; 21         } 22     } 23     int qer(int x,int l,int r,int nl,int nr){ 24         down(x); 25         if(l == nl && nr == r) return sg[x]; 26         int mid = (nl + nr) >> 1; 27         if(r <= mid) return qer(x << 1, l, r, nl, mid); 28         else if(l > mid) return qer(x << 1|1, l, r, mid + 1, nr); 29         else{ 30             int t1 = qer(x << 1, l, mid, nl, mid); 31             int t2 = qer(x << 1|1, mid + 1, r, mid+1, nr); 32             return min(t1,t2); 33         } 34     } 35     void mod(int x,int l,int r,int nl,int nr,int val){ 36         down(x); 37         if(l == nl && nr == r){ 38             sg[x] = max(sg[x],val), tag[x] = max(tag[x],val); 39             return; 40         } 41         int mid = (nl + nr) >> 1; 42         if(r <= mid){ 43             mod(x << 1, l, r, nl, mid, val); 44         } 45         else if(l > mid){ 46             mod(x << 1|1, l, r, mid + 1, nr, val);             47         } 48         else{ 49             mod(x << 1, l, mid, nl, mid, val); 50             mod(x << 1|1, mid + 1, r, mid + 1, nr, val);     51         } 52         sg[x] = min(sg[x << 1], sg[x << 1|1]); 53     } 54      55 }seg; 56 int n,vx,vy; 57 int tot; 58 struct grid{ 59     int x,y; 60     long long height; 61 }g[maxn * maxn + 100]; 62 int cmp(grid x, grid y){ 63     if(x.x != y.x) return x.x > y.x; 64     return x.y > y.y; 65 } 66 void trans(){ 67     if(vx > 0){ 68         vx = -vx; 69         for(int i = 1; i <= tot; ++i) g[i].x = n - g[i].x - 1; 70     } 71     if(vy > 0){ 72         vy = -vy; 73         for(int i = 1; i <= tot; ++i) g[i].y = n - g[i].y - 1; 74     } 75     if(vx == 0 && vy != 0){ 76         swap(vx,vy); 77         for(int i = 1; i <= tot; ++i){ 78             swap(g[i].x, g[i].y); 79             g[i].y = n - g[i].y - 1; 80         } 81     } 82 } 83 struct I{ 84     long long it; 85     int rank; 86 }data[maxn][maxn]; 87 map<long long, int>v; 88 map<long long, int>::iterator itr; 89 void inter(int x,int y){ 90     long long t = ((long double) y - vy * x / (long double)vx) * (long long)1e9; 91     data[x][y] = (I){t,0}; 92     v[t] = 0; 93 } 94 void calc(){ 95     for(int i = 0; i <= n; ++i) 96         for(int j = 0; j <= n; ++j) 97             inter(i,j); 98     for(itr = v.begin(); itr != v.end(); ++itr) 99         itr->second = ++ct;100     for(int i = 0; i <= n; ++i)101         for(int j = 0; j <= n; ++j){102             data[i][j].rank = v[data[i][j].it];103         }104 }105 long long ans;106 void ins(){107     sort(g + 1, g + tot + 1, cmp);108     for(int i = 1; i <= tot; ++i){109         int up = -inf, down = inf;110         for(int j = 1; j <= 4; ++j){111             int tx = g[i].x + dx[j], ty = g[i].y + dy[j];112             up = max(up, data[tx][ty].rank);113             down = min(down, data[tx][ty].rank);114         }115         int r = up - 1, l = down;116         if(l <= r && up >= 0){117             int t = seg.qer(1, l , r, 1, ct);118             ans += max(g[i].height - t, 0LL);119             seg.mod(1, l, r, 1, ct, g[i].height);120         }121     }122 }123 void spj(){124     long long ans = 0;125     sort(g + 1, g + tot + 1, cmp);126     for(int i = 1; i <= tot; ++i){127         int x = g[i].x, y = g[i].y;128         data[x][y].it = max(data[x][y].it, data[x+1][y].it);129         ans += max(g[i].height - data[x][y].it, 0LL);130         data[x][y].it = max(data[x][y].it, g[i].height);131     }132     cout << ans;133 }134 int main()135 {136     freopen("cubes.in","r",stdin);137     freopen("cubes.out","w",stdout);138     ios::sync_with_stdio(false);139     cin >> n >> vx >> vy;140     for(int i = 1; i <= n; ++i)141         for(int j = 1; j <= n; ++j){142             int t; cin >> t;143             g[++tot] = (grid){i-1,j-1,t};144         }145     trans();146     calc();147     ins();148     cout << ans;149     return 0;150 }