Codeforces 720A. Closing ceremony

A. Closing ceremony

time limit per test

2 seconds

memory limit per test

256 megabytes

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.

Input

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.

Output

If it is possible to distribute tickets between people in the described manner print "YES", otherwise print "NO".

Examples

input

2 2
3 3 3 2
1 3

output

YES

input

2 2
3 2 3 3
1 2

output

NO

题目大意：n*m个座位，有n*m个人，一开始有k个人在(0,0)点上，l个人在(0，m+1)点上，每个人有对应的体力值，体力值即为可以行走的距离（曼哈顿距离），问是否存在一种方案是每个人花费的体力不超过上限，且每个人都有位置坐。

贪心：对于前k个人，我们按照体力排序，显然找到一个以距离（0，m+1)尽可能远为第一关键字，与（0,0）尽可能远为第二关键字的位置，那么这个人就应该在这个位置。之后l个人放到与（0，m+1)尽可能远的且没有人的位置，检测是否存在这种可能。

AC code

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstdlib>

 #include<algorithm>

 #include<vector>

 #include<cmath>

 #include<ctime>

 #include<cstring>

 #define yyj(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout);

 #define llg long long

 #define maxn 10010

 using namespace std;

 llg i,j,k,n,m,k1,k2,t1,t2,bj[maxn],x,y,l,len,a[maxn],b[maxn],maxl;

 bool f;

 int main()

 {

     yyj("");

     cin>>n>>m>>k1;

     for (i=;i<=k1;i++) cin>>a[i];

     sort(a+,a+k1+);

     cin>>k2;

     for (j=;j<=k2;j++) cin>>b[j];

     sort(b+,b+k2+);

     int c[n+][m+];

     for (i=;i<=n;i++) for (j=;j<=m;j++) c[i][j]=;

     for (k=;k<=k1;k++)

     {

         f=false; maxl=;

         for (i=;i<=n;i++)

             for (j=;j<=m;j++)

                 if (i+j<=a[k] && i+m+-j>maxl && c[i][j]==)

                 {

                     f=true;

                     x=i,y=j;

                     maxl=i+m-j+;

                 }

         if (f)

         {

             c[x][y]=;

         }

         else

         {

             cout<<"NO";

             return ;

         }

     }

     for (k=;k<=k2;k++)

     {

         maxl=,f=false;

         for (i=;i<=n;i++)

             for (j=;j<=m;j++)

                 if (c[i][j]== && i+m+-j>maxl && i+m+-j<=b[k])

                 {

                     f=true;

                     x=i; y=j;

                     maxl=i+m+-j;

                 }

         if (f)

         {

             c[x][y]=;

         }

         else

         {

             cout<<"NO";

             return ;

         }

     }

     cout<<"YES";

     return ;

 }

巴特西

Codeforces 720A. Closing ceremony

最新文章

热门文章