시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
5 초 | 256 MB | 17 | 3 | 3 | 42.857% |
폴리매스 문명은 기원전 8500년 경, 이웃 나라 사이언스보드를 복속시키기 위해 1차 동아전쟁이라 불리는 대규모 전쟁을 벌였던 것으로 알려져 있습니다. 당신은 그 당시 폴리매스 문명의 육군 전술에 관해 연구하고자 합니다. 다행히도, 당신은 고문헌에서 몇 가지 유용한 정보를 얻을 수 있었습니다.
그들의 전법서에 따르면 폴리매스 문명의 군대는 정확한 직사각형 모양의 방진으로 이루어져 있었다고 합니다. 즉 $X$행 $Y$열의 직사각형을 정확히 $XY$명의 병사가 채우고 있는 형태인 것입니다. 병사의 수가 정확히 떨어지지 않아 몇 명이 남거나 부족한 경우는 허용되지 않았습니다.
또한 폴리매스 문명은 본래 강력한 군사력으로 주변의 약소국을 다수 복속시켰으므로 군대에도 서로 다른 $N$개의 민족이 섞여 있었습니다. 특히, 1차 동아전쟁에 참가한 병사들 중 $i$번째 민족 출신인 병사는 정확히 $A_i$명이었다는 기록이 남아 있습니다.
폴리매스 문명에서는 출신 민족에 따라 시민들을 차별대우했는데 군대 또한 이 영향을 받았습니다. 특히 $i<j$일 때 $i$번째 민족 출신인 병사는 항상 $j$번째 민족 출신인 병사보다 앞에 서야 했습니다. 이 때 $a$행 $b$열에 위치한 병사가 $a'$행 $b'$열에 위치한 병사보다 앞에 선다는 말은 다음 둘 중 하나가 성립함을 의미합니다.
그러나 이 방식에는 약간의 문제가 있었는데, 서로 다른 민족인 병사끼리 양옆으로 인접해 있다면 항상 싸움이 벌어진다는 것이었습니다. 이 때 $a$행 $b$열에 위치한 병사와 $a'$행 $b'$열에 위치한 병사가 양옆으로 인접해 있다는 말은 $a=a'$이고 $|b-b'|=1$임을 뜻합니다.
폴리매스 문명의 육군 장교들은 싸움을 막기 위해 평화의 돌을 사용했습니다. 평화의 돌의 힘을 사용하면 서로 다른 민족인 병사가 인접해 있더라도 싸움이 나는 것을 막을 수 있지만, 한 개의 돌 당 하나의 싸움밖에 막을 수 없습니다. 즉 평화의 돌을 $k$개 가지고 있다면 민족이 다르고 서로 인접한 병사의 쌍이 $k$쌍 이하여야 싸움이 일어나지 않는 것입니다.
당신은 여러 기록들을 통해 폴리매스 문명의 장교들은 방진이 옆으로 넓을수록, 즉 $Y$가 최대한 클수록 군대가 강하다고 생각했다는 사실을 밝혀냈습니다. 따라서 당신은 1차 동아전쟁에 사용된 방진 또한 완벽한 직사각형 모양이고 싸움이 일어나지 않는 형태의 방진 중 가장 큰 $Y$값을 가지는 방진일 것이라고 추측하고 있습니다. 그러나 당신은 아직 폴리매스 문명이 정확히 몇 개의 평화의 돌을 가지고 있었는지는 밝혀내지 못했기 때문에, $0 \le k \le N-1$인 모든 정수 $k$에 대해서 가능한 $Y$의 최댓값을 모두 구하기로 했습니다.
첫 줄에 민족의 수 $N$이 주어집니다.
다음 줄에는 각 민족의 병사의 수 $A_1, A_2, \cdots, A_N$이 주어집니다.
첫 줄에 $0 \le k \le N-1$에 대해 가능한 $Y$의 최댓값을 각각 공백으로 구분하여 출력합니다.
번호 | 배점 | 제한 |
---|---|---|
1 | 6 | $A_1 = A_2 = \cdots = A_N$ |
2 | 5 | $N \le 20$, $M \le 10^9$ |
3 | 24 | $N \le 10^3$, $M \le 10^9$ |
4 | 33 | $M \le 10^{12}$ |
5 | 32 | 추가 제한 조건이 없습니다. |
5 3 1 2 1 1
1 1 2 4 8
4 6 2 14 14
2 2 6 36
Contest > 폴리매스 코드 챔피언십 > 폴리매스 제2회 코드 챔피언십 Division 1 F번