소스탄티노플의 갱단

시간 제한1초메모리 제한128 MB

요약
각 갱단의 소 수가 주어질 때, 1번 갱단이 경기장을 최종적으로 장악할 수 있는지 판정하고, 남는 1번 갱단 소의 수를 최대로 하는 사전순으로 가장 이른 도착 순서를 구한다.
난이도

어려움10점 중 8점

유형
그리디, 구현, 완전 탐색, 동적 계획법
정답자
아직 제출이 없습니다

문제

농장의 삶은 고단하고, 고단할수록 강해져야 한다. 소들은 편의상 11번부터 MM번까지 번호가 매겨진 갱단을 만들었다. 한동안은 평화롭게 지냈지만, 이제 상황이 걷잡을 수 없어졌다.

소들은 넓은 방목장의 지배권을 두고 경쟁한다. 다툼은 여러 분(minute)에 걸쳐 진행된다. 매 분마다 소 한 마리가 방목장에 들어온다.

  • 방목장이 비어 있으면, 새로 들어온 소의 갱단이 방목장을 지배하고 그 소는 풀을 뜯기 시작한다.
  • 방목장을 이미 자신의 갱단이 지배하고 있으면, 그 소는 합류하여 풀을 뜯는다.
  • 그 밖의 경우, 지배 중인 갱단의 소 한 마리가 새로 온 소와 맞선다. 둘은 다투다가 서로 생각보다 닮았다는 것을 깨닫고, 함께 방목장을 떠나 선술집에서 시원한 두유를 마신다. 이 과정으로 방목장이 비게 되면, 어떤 갱단도 방목장을 지배하지 않는다.

베시는 11번 갱단 소속이며 각 갱단에 소가 몇 마리 있는지 정확히 알고 있다. 그녀는 모든 소가 방목장에 남거나 선술집으로 떠난 뒤 자신의 갱단이 방목장을 지배하기를 바란다.

11번 갱단이 결국 방목장을 지배할 수 있는지 판단하라. 가능하다면, 방목장에 남을 수 있는 11번 갱단 소의 최대 마릿수와, 그 최댓값을 만드는 사전순으로 가장 빠른 도착 순서를 구하라. 순서 XX가 YY보다 사전순으로 빠르다는 것은, 어떤 kk에 대해 Xk<YkX_k < Y_k이고 모든 i<ki < k에 대해 Xi=YiX_i = Y_i인 경우를 말한다.

입력

  • 첫째 줄에 두 정수 NN과 MM이 공백으로 구분되어 주어진다 (1≤N≤1001 \le N \le 100, 1≤M≤N1 \le M \le N). NN은 전체 소의 수, MM은 갱단의 수이다. NN마리의 소는 MM개의 갱단에 나뉘어 속한다.
  • 다음 MM개의 줄 중 ii번째 줄에는 ii번 갱단에 속한 소의 수가 주어진다. 각 갱단에는 소가 적어도 한 마리 있다.

출력

  • 첫째 줄에, 다툼이 끝난 뒤 11번 갱단이 방목장을 지배할 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.
  • YES인 경우 둘째 줄에, 방목장에 남을 수 있는 11번 갱단 소의 최대 마릿수를 출력한다.
  • YES인 경우 이어서 NN개의 줄을 출력한다. ii번째 줄에는, 방목장에 남는 11번 갱단 소의 수가 최대가 되는 사전순으로 가장 빠른 도착 순서에서 ii번째 분에 도착하는 소의 갱단 번호를 출력한다.

참고

예를 들어 소가 55마리, 갱단이 33개이고 베시의 11번 갱단에 22마리, 22번 갱단에 11마리, 33번 갱단에 22마리가 있다면, 마지막에 방목장에 남을 수 있는 베시의 소는 최대 한 마리이다.

예제3

  1. 예제 1

    입력
    5 3
    2
    1
    2
    
    예상 출력
    YES
    1
    1
    3
    2
    3
    1
    
  2. 예제 2

    입력
    4 1
    4
    
    예상 출력
    YES
    4
    1
    1
    1
    1
    
  3. 예제 3

    입력
    8 3
    3
    2
    3
    
    예상 출력
    YES
    2
    1
    3
    2
    2
    3
    3
    1
    1