## [ACM_ZJUT_1063]Lily's Puzzle

### Lily's puzzle

Time Limit:1000MS Memory Limit:32768K

```
16
10 8
2 2
2 5
2 7
3 3
3 8
4 2
4 5
4 8
6 4
6 7
7 5
7 8
8 1
8 4
9 6
10 3
4 3
8
6 4
1 2
2 1
2 4
3 4
4 2
5 3
6 1
6 2
3 2
0
```

```
5
3
```

#### Source

ZJUT1063

```#include<stdio.h>
#include<memory>

int a[101][101];
int b[101][101];

int Solve(int w, int h, int s, int t){
int row, col, i, j, k, max;
for(i = 1; i <= t; ++i){
for(j = 1; j <= s; ++j){
b[1][1] += a[i][j];
}
}
max = b[1][1];
for(i = 2; i <= h - t + 1; ++i){
b[i][1] = b[i - 1][1];
for(j = 1; j <= s; ++j){
b[i][1] += a[i - 1 + t][j] - a[i - 1][j];
}
if(max < b[i][1])
max = b[i][1];
}
for(k = 2; k <= w - s + 1; ++k){
b[1][k] = b[1][k - 1];
for(i = 1; i <= t; ++i){
b[1][k] += a[i][k - 1 + s] - a[i][k - 1];
}
if(max < b[1][k])
max = b[1][k];
for(i = 2; i <= h - t + 1; ++i){
b[i][k] = b[i - 1][k];
for(j = k; j <= k + s - 1; ++j){
b[i][k] += a[i - 1 + t][j] - a[i - 1][j];
}
if(max < b[i][k])
max = b[i][k];
}
}
return max;
}

int main(){
int trees, w, h, s, t, i, j;
while(scanf("%d", &trees) && trees){
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
scanf("%d%d", &w, &h);
while(trees--){
scanf("%d%d", &j, &i);
a[i][j] = 1;
}
scanf("%d%d", &s, &t);
int max = Solve(w, h, s, t);
if(s != t){
memset(b, 0, sizeof(b));
int tmp = Solve(w, h, t, s);
if(tmp > max)
max = tmp;
}
printf("%d\n", max);
}
return 0;
}
```

```#include<stdio.h>
#include<memory>
#include<vector>
using namespace std;
int a[101][101];

struct T{
int row, col;
T(int row, int col):row(row), col(col){}
};

int Solve(vector<T> &v, int w, int h, int s, int t){
int i, j, max = 0;
memset(a, 0, sizeof(a));
for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){
for(i = (*it).row; i > (*it).row - s && i > 0; --i){
for(j = (*it).col; j > (*it).col - t && j > 0; --j){
++a[i][j];
if(a[i][j] > max)
max = a[i][j];
}
}
}
return max;
}

int main(){
int trees, w, h, s, t, i, j;
while(scanf("%d", &trees) && trees){
vector<T> v;
scanf("%d%d", &w, &h);
while(trees--){
scanf("%d%d", &j, &i);
v.push_back(T(j, i));
}
scanf("%d%d", &s, &t);
int max = Solve(v, w, h, s, t);
if(s != t){
int tmp = Solve(v, w, h, t, s);
if(tmp > max)
max = tmp;
}
printf("%d\n", max);
}
return 0;
}
```

```#include<iostream>
#include<memory>
using namespace std;
int a[101][101];
int b[101][101];

int Solve(int w, int h, int s, int t){
int row, col, i, j, k, max;
for(i = 1; i <= t; ++i){
for(j = 1; j <= s; ++j){
b[1][1] += a[i][j];
}
}
max = b[1][1];
for(i = 2; i <= h - t + 1; ++i){
b[i][1] = b[i - 1][1];
for(j = 1; j <= s; ++j){
b[i][1] += a[i - 1 + t][j] - a[i - 1][j];
}
if(max < b[i][1])
max = b[i][1];
}
for(k = 2; k <= w - s + 1; ++k){
b[1][k] = b[1][k - 1];
for(i = 1; i <= t; ++i){
b[1][k] += a[i][k - 1 + s] - a[i][k - 1];
}
if(max < b[1][k])
max = b[1][k];
for(i = 2; i <= h - t + 1; ++i){
b[i][k] = b[i - 1][k];
for(j = k; j <= k + s - 1; ++j){
b[i][k] += a[i - 1 + t][j] - a[i - 1][j];
}
if(max < b[i][k])
max = b[i][k];
}
}
return max;
}

int main(){
int trees, w, h, s, t, i, j;
while(cin >>  trees && trees){
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
cin >> w >> h;
while(trees--){
cin >> j >> i;
a[i][j] = 1;
}
cin >> s >> t;
int max = Solve(w, h, s, t);
if(s != t){
memset(b, 0, sizeof(b));
int tmp = Solve(w, h, t, s);
if(tmp > max)
max = tmp;
}
cout << max << endl;
}
return 0;
}
```
```#include<iostream>
#include<memory>
#include<vector>
using namespace std;
int a[101][101];

struct T{
int row, col;
T(int row, int col):row(row), col(col){}
};

int Solve(vector<T> &v, int w, int h, int s, int t){
int i, j, max = 0;
memset(a, 0, sizeof(a));
for(vector<T>::iterator it = v.begin(); it != v.end(); ++it){
for(i = (*it).row; i > (*it).row - s && i > 0; --i){
for(j = (*it).col; j > (*it).col - t && j > 0; --j){
++a[i][j];
if(a[i][j] > max)
max = a[i][j];
}
}
}
return max;
}

int main(){
int trees, w, h, s, t, i, j;
while(cin >> trees && trees){
vector<T> v;
cin >> w >> h;
while(trees--){
cin >> j >> i;
v.push_back(T(j, i));
}
cin >> s >> t;
int max = Solve(v, w, h, s, t);
if(s != t){
int tmp = Solve(v, w, h, t, s);
if(tmp > max)
max = tmp;
}
cout << max << endl;
}
return 0;
}
```

```#include<memory>
#include<iostream>
#include<vector>
using namespace std;
struct T{
int row, col;
T(int row, int col):row(row), col(col){}
};

int Solve(int i,int j,int s,int t,vector<T> v)
{
int suma=0;
int sumb=0;
for(int k=0;k<v.size();k++)
{
if(v[k].row<i+t && v[k].row>=i && v[k].col<j+s && v[k].col>=j)
suma++;
if(v[k].row<i+s && v[k].row>=i && v[k].col<j+t && v[k].col>=j)
sumb++;
}
if(suma>=sumb)
return suma;
else
return sumb;
}
int main()
{
int trees, w, h, s, t, i, j;
while(cin>>trees && trees)
{
vector<T> v;
cin >> w >> h;
while(trees--)
{
cin >> j >> i;
v.push_back(T(j, i));
}
cin >> s >> t;
int maxtree=0,temptree=0;
for(int i=0;i<=w;i++)
{
for(int j=0;j<=h;j++)
{
temptree=Solve(i,j,s,t,v);
if(temptree>maxtree)
maxtree=temptree;
}
}
cout << maxtree << endl;
}
return 0;
}
```

Method Result Time(MS) Memory(K) Length Language