The closing ceremony of Squanch Code Cup is held in the big hall with n × m seats, arranged in n rows, m seats in a row. Each seat has two coordinates (x, y) (1 ≤ x ≤ n, 1 ≤ y ≤ m).
There are two queues of people waiting to enter the hall: k people are standing at (0, 0) and n·m - k people are standing at (0, m + 1). Each person should have a ticket for a specific seat. If person p at (x, y) has ticket for seat (xp, yp) then he should walk |x - xp| + |y - yp|to get to his seat.
Each person has a stamina — the maximum distance, that the person agrees to walk. You should find out if this is possible to distribute all n·m tickets in such a way that each person has enough stamina to get to their seat.
The first line of input contains two integers n and m (1 ≤ n·m ≤ 104) — the size of the hall.
The second line contains several integers. The first integer k (0 ≤ k ≤ n·m) — the number of people at (0, 0). The following k integers indicate stamina of each person there.
The third line also contains several integers. The first integer l (l = n·m - k) — the number of people at (0, m + 1). The following lintegers indicate stamina of each person there.
The stamina of the person is a positive integer less that or equal to n + m.
If it is possible to distribute tickets between people in the described manner print "YES", otherwise print "NO".
2 2
3 3 3 2
1 3
YES
2 2
3 2 3 3
1 2
NO
题目大意：n*m个座位， 有n*m个人，一开始有k个人在(0,0)点上，l个人在(0，m+1)点上，每个人有对应的体力值，体力值即为可以行走的距离（曼哈顿距离），问是否存在一种方案是每个人花费的体力不超过上限，且每个人都有位置坐。
贪心：对于前k个人，我们按照体力排序，显然找到一个以距离（0，m+1)尽可能远为第一关键字，与（0,0）尽可能远为第二关键字的位置，那么这个人就应该在这个位置。之后l个人放到与（0，m+1)尽可能远的且没有人的位置，检测是否存在这种可能。
AC code
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cstdlib> 5 #include<algorithm> 6 #include<vector> 7 #include<cmath> 8 #include<ctime> 9 #include<cstring> 10 #define yyj(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout); 11 #define llg long long 12 #define maxn 10010 13 using namespace std; 14 llg i,j,k,n,m,k1,k2,t1,t2,bj[maxn],x,y,l,len,a[maxn],b[maxn],maxl; 15 bool f; 16 int main() 17 { 18 yyj("1"); 19 cin>>n>>m>>k1; 20 for (i=1;i<=k1;i++) cin>>a[i]; 21 sort(a+1,a+k1+1); 22 cin>>k2; 23 for (j=1;j<=k2;j++) cin>>b[j]; 24 sort(b+1,b+k2+1); 25 int c[n+10][m+10]; 26 for (i=0;i<=n;i++) for (j=0;j<=m;j++) c[i][j]=0; 27 for (k=1;k<=k1;k++) 28 { 29 f=false; maxl=0; 30 for (i=1;i<=n;i++) 31 for (j=1;j<=m;j++) 32 if (i+j<=a[k] && i+m+1-j>maxl && c[i][j]==0) 33 { 34 f=true; 35 x=i,y=j; 36 maxl=i+m-j+1; 37 } 38 if (f) 39 { 40 c[x][y]=1; 41 } 42 else 43 { 44 cout<<"NO"; 45 return 0; 46 } 47 } 48 for (k=1;k<=k2;k++) 49 { 50 maxl=0,f=false; 51 for (i=1;i<=n;i++) 52 for (j=1;j<=m;j++) 53 if (c[i][j]==0 && i+m+1-j>maxl && i+m+1-j<=b[k]) 54 { 55 f=true; 56 x=i; y=j; 57 maxl=i+m+1-j; 58 } 59 if (f) 60 { 61 c[x][y]=1; 62 } 63 else 64 { 65 cout<<"NO"; 66 return 0; 67 } 68 } 69 cout<<"YES"; 70 return 0; 71 }