【Link】:http://codeforces.com/contest/839/problem/B

【Description】



给你n排的如题目所示的位置;

同一排中(1,2) 算相邻;

(3,4),(4,5),(5,6)算相邻,然后(7,8)算相邻;

这里的(x,y)表示某个人坐在x,另外一个人坐在y的话.

问你够不够安排k组的人;

使得相邻座位的人都是相同组的人;

是则输出YES….

【Solution】



中间的那4个位置;

是没办法用来放不同组的成对的.

也即

xxyy不能放在中间那4个位置.

但xx和yy可以放在最左边和最右边的那两个连续位置;

则,我们中间那4个位置;

先尽可能地放同一组的4个人

这样,能尽量避免不同组的人到中间那4个位置

不同组的人到了中间那4个位置肯定不能最大化利用这4个位置的

因为肯定会有空座位

剩余的不同组的人,则可以安排在两侧的连续位置

中间那4个位置安排过后;

有两种情况.

第一种

n排所有的中间4个位置的都被安排光了;

剩下的组中可能还有大于4的人.

这个时候,只有最左边和最右边的连续两个块可以使用了;

则还剩下n*2个连续的对的空间;

如果某一组为奇数;

则那个多出来的人单独占据一对的空间即可;

否则就贪心地用这n*2个连续对就好;

第二种

这n排中,有一些排中间的4个位置还是空的.

这个时候,所有组的人数都已经小于4了;

我们先考虑一组中还有2..3个人的.

先把其中两个人优先安排到最左和最右的(1,2)或(7,8)位置;

我们有n*2个那样的(1,2)或(7,8)位置;

(即每行两边都有两个)

但可能这n*2个对还不够用;

可能还是有一些组有2..3个人;

则,我们再给他安排在(4,5)的位置;

注意,

这个时候,我们一旦安排在了(3,4);

那么那一行就只有位置6还能放单个的人了;

可能(4,5)的位置放完了以后还是不够;

也即还是有一些组有2..3个人

这个时候;就利用我们刚才在中间放了(3,4),而6还能放单个的人这一点;

两个那个位置5,就又能凑成一对了;

(这种放一对的方案,很容易被漏掉)

如果还是有一些组有2..3个人,那么就不行了;

输出无解;

否则,考虑剩下的组中还剩一个人的组

那一个人可以放在n*2个对里面(如果对还没用完的话),或者放在

中间连续的4个空位也即(3,4)和(5,6)中的3和6,这个时候中间的4个位置可以用其中的两个,所以减去了连续的4个空位置的个数之后,还有递增单个位置,也即上面提到的当个的位置6

或者

放在单个的位置6

这3种考虑后如果还不行就无解;

(就是说那一个人放不下的话)



【NumberOf WA】



4



【Reviw】



分成两行放一对那种方法没想到.

一开始认为超过8就直接放一整行的天真想法是错的。



【Code】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define ri(x) scanf("%d",&x)

#define rl(x) scanf("%lld",&x)

#define rs(x) scanf("%s",x+1)

#define oi(x) printf("%d",x)

#define ol(x) printf("%lld",x)

#define oc putchar(' ')

#define os(x) printf(x)

#define all(x) x.begin(),x.end()

#define Open() freopen("F:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int N = 100;

int n,k,a[N+10],cur4,cur2,cur;

int main(){

    //Open();

    //Close();

    ri(n),ri(k);

    rep1(i,1,k) {

        ri(a[i]);

    }

    cur4 = n;

    if (cur4)

        rep1(i,1,k)

            if (a[i]>=4){

                int temp = min(a[i]/4,cur4);

                cur4-=temp;

                a[i] -= temp*4;

                if (cur4==0) break;

            }

    if (cur4 > 0){//全都小于4了

        int pairs = n*2;

        for (int i = 1;i <= k && pairs > 0;i++)

            if (a[i] > 1){

                pairs--;

                a[i]-=2;

            }

        int singlec = 0;

        rep1(i,1,k)

            if (a[i] > 1){

                if (cur4 > 0){

                    cur4--;

                    singlec++;

                    a[i]-=2;

                    continue;

                }

                if (singlec >= 2){

                    singlec-=2;

                    a[i]-=2;

                    continue;

                }

                return puts("NO");

            }

        rep1(i,1,k)

            if (a[i]==1){

                if (pairs){

                    pairs--;

                    continue;

                }

                if (singlec){

                    singlec--;

                    continue;

                }

                if (cur4){

                    cur4--;

                    singlec++;

                    continue;

                }

                return puts("NO"),0;

            }

        puts("YES");

    }else{ //cur4==0

        int pairs = n*2;

        rep1(i,1,k)

            if (a[i] > 0){

                pairs-=((a[i]-1)/2+1);

                if (pairs < 0) return puts("NO"),0;

            }

        puts("YES");

    }

    return 0;

}