로봇 파괴술 스페셜 저지 서브태스크 2초 256MB
문제
N 개의 로봇이 일렬로 있고, 각 로봇은 M 종류의 능력치를 가진다. ( 1 ≤ M ≤ 5 )
각 능력치는 10억 이하의 자연수다.
한 로봇의 M 종류의 능력치가 모두 0이 된다면, 그 로봇은 파괴된다.
우리의 목표는 로봇이 파괴된 가장 긴 연속 구간을 최대한 길게 하는 것이다.
예를 들어 N = 10 일 때,
[1, 3, 5, 7, 9] 번째 로봇을 파괴하는 것 보다는,
[2, 3] 번째 로봇을 파괴하는 것이 더 좋다.
가장 긴 연속 구간의 길이로 따졌을 때 [2, 3] 이 [1, 3, 5, 7, 9] 보다 더 길기 때문이다.
우리는 K 발의 총알을 가지고 있다.
한 총알을 쏠 때마다, M 종류의 능력치 중 하나를 골라, 모든 로봇에 대해 그 능력치 값을 1 감소 시키게 된다. ( 능력치가 0이었다면 그대로 0으로 남음 )
이 때, 각 능력치 당 몇 발의 총알을 쏴야 파괴된 로봇의 최장 구간이 최대가 되는지 출력하시오. ( M 개의 정수를 출력하면 된다. )
꼭 K 발의 총알을 다 사용할 필요는 없다.
가능한 답이 여러 개라면 그 중 아무거나 출력한다.
입력
첫 줄에 N, M, K 가 입력된다. ( 1 ≤ N ≤ 10만, 1 ≤ M ≤ 5, 1 ≤ K ≤ 10억 )
그 후, N 줄에 걸쳐, 한 줄 당 M 개의 능력치 값이 입력된다. ( 각 능력치는 10억 이하의 자연수 )
출력
한 줄로, 각 능력치 당 사용하는 총알 개수를 나타내는 M 개의 정수를 출력한다.
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 20점 | 1 ≤ N ≤ 100 |
| #2 | 20점 | M = 1 |
| #3 | 60점 | 제약 조건 없음 |
예제 #1
5 2 4
4 0
1 2
2 1
0 2
1 3
2 2
첫 능력치에 2발, 두 번째 능력치에 2발의 총을 쏘면,
2 0
0 0
0 0
0 0
0 1
이 된다.
따라서 2 ~ 4번째 로봇까지, 연속적으로 최대 3개의 로봇을 파괴할 수 있다. 이 경우가 최대다.
예제 #2
5 3 1
1 0 0
0 1 0
1 0 0
0 1 0
0 1 0
0 1 0
한 발의 총알을
첫 번째 능력치에 쏘면 1, 3번째 로봇이 파괴되고, (최대 구간 길이 1)
두 번째 능력치에 쏘면 2, 4, 5번째 로봇이 파괴된다. (최대 구간 길이 2)
로그인해야 코드를 작성할 수 있어요.