시간 여행은 피곤하며 그 과정에서 배고파질 수 있습니다. 다행히도, 시간 여행을 하면서 공룡 고기, 도도새 알, 매머드 우유와 같은 엄청나게 다양한 이국적인 음식을 찾을 수 있습니다. 하지만 불행히도, 타임 머신에는 냉장고를 보관할 공간이 없었기에, Tim이 이국적인 음식을 먹고 싶다면 그 자리에서 즉시 먹어야 합니다. 그러나 Tim이 음식을 먹으면, 그는 너무 배부른 나머지 바로 다음에 타임 머신으로 방문하는 시간대에서는 아무것도 먹지 못할 것입니다. 각 음식들은 Tim에게 줄 수 있는 만족도 값을 갖고 있으며, Tim은 그가 실제로 먹는 모든 음식들의 만족도의 합을 최대화하는 것을 목표합니다. 타임 머신으로 Tim이 방문하는 시간대의 순서는 이미 확정되었으며 수정할 수 없습니다. 그가 먹는 음식을 선택적으로 고를 때, Tim이 얻을 수 있는 만족도의 최댓값을 구하세요.
--------
[입력]
입력의 첫 줄에는 테스트케이스의 수 K가 주어집니다. 이후 각 테스트케이스의 1번째 줄에는 Tim이 먹을 수 있는 음식의 수 n (1 ≤ n ≤ 50000)이 주어지며, 2번째 줄에는 n개 음식들의 만족도 vi (1 ≤ vi ≤ 1000)가 한 줄에 주어집니다. 이때 2번째 줄에 입력되는 vi의 순서는 Tim이 음식을 접하는 순서대로 주어집니다.
--------
[출력]
각 테스트케이스에 대해, 먼저 "Data Set x:"를 출력합니다. 이때 x는 테스트케이스의 번호입니다. 다음 줄에는 Tim이 얻을 수 있는 만족도의 최댓값을 출력합니다. 각 테스트케이스는 하나의 빈 줄로 구분되어야 합니다.
moner_ari 1년 전
[문제]
시간 여행은 피곤하며 그 과정에서 배고파질 수 있습니다. 다행히도, 시간 여행을 하면서 공룡 고기, 도도새 알, 매머드 우유와 같은 엄청나게 다양한 이국적인 음식을 찾을 수 있습니다. 하지만 불행히도, 타임 머신에는 냉장고를 보관할 공간이 없었기에, Tim이 이국적인 음식을 먹고 싶다면 그 자리에서 즉시 먹어야 합니다. 그러나 Tim이 음식을 먹으면, 그는 너무 배부른 나머지 바로 다음에 타임 머신으로 방문하는 시간대에서는 아무것도 먹지 못할 것입니다. 각 음식들은 Tim에게 줄 수 있는 만족도 값을 갖고 있으며, Tim은 그가 실제로 먹는 모든 음식들의 만족도의 합을 최대화하는 것을 목표합니다. 타임 머신으로 Tim이 방문하는 시간대의 순서는 이미 확정되었으며 수정할 수 없습니다. 그가 먹는 음식을 선택적으로 고를 때, Tim이 얻을 수 있는 만족도의 최댓값을 구하세요.
--------
[입력]
입력의 첫 줄에는 테스트케이스의 수 K가 주어집니다. 이후 각 테스트케이스의 1번째 줄에는 Tim이 먹을 수 있는 음식의 수 n (1 ≤ n ≤ 50000)이 주어지며, 2번째 줄에는 n개 음식들의 만족도 vi (1 ≤ vi ≤ 1000)가 한 줄에 주어집니다. 이때 2번째 줄에 입력되는 vi의 순서는 Tim이 음식을 접하는 순서대로 주어집니다.
--------
[출력]
각 테스트케이스에 대해, 먼저 "Data Set x:"를 출력합니다. 이때 x는 테스트케이스의 번호입니다. 다음 줄에는 Tim이 얻을 수 있는 만족도의 최댓값을 출력합니다. 각 테스트케이스는 하나의 빈 줄로 구분되어야 합니다.