15882번 - Line of Bentham

공리주의 국가의 한 장소에 N명의 사람들이 앞을 보고 일렬로 줄을 설 예정이다. 맨 앞 사람을 1번이라고 하고, 쭉 숫자를 붙여 맨 뒤에 서 있는 사람을 N번이라고 하자.

이 사람들은 좋아하는 사람과 싫어하는 사람이 명확하다. 한 사람은 앞을 봤을 때 자기 앞의 3명까지 분간할 수 있는데, 자기 앞에 보이는 사람 중에 싫어하는 사람이 있으면 싫어하는 만큼 기분이 나빠지고, 좋아하는 사람이 있으면 좋아하는 만큼 기분이 좋아진다.

국가에서는 이를 수치화시켜서 행복 지수를 정의했다. i번 사람이 j번 사람을 좋아하는 정도 p_i,j 를 -10에서 10 사이의 정수로 측정한 뒤, i번 사람의 행복 지수 q_i를 p_i,i−3 + p_i,i−2 + p_i,i−1 로 정의했다. (단, j ≤ 0인 p_i,j는 j번 사람이 실존하지 않기 때문에 0으로 정의한다.) 그리고 N명의 행복 지수를 모두 더한 것인 \(Q =\sum_{i=1}^{N}{q_i}\) 를 종합 행복지수로 정의하고, 이를 최대화 시키는 것을 원한다.

그래서 국가 검열관 정현식은 줄에서 사람들을 임의로 몇 명 제외하고, 그 자리에 대신 누구와도 면식이 없는 정부 파견 요원을 넣는 임무를 받게 되었다.

특정 자리에 요원을 넣게 되면, 요원은 좋아하거나 싫어하는 사람이 없기 때문에 요원의 행복 지수는 0이며, 요원의 뒤에 있는 사람들은 해당 요원을 좋아하지도 싫어하지도 않을 것이다. 투입할 수 있는 요원은 수없이 많기 때문에, 줄의 몇 명을 요원으로 대체해도 문제는 없다.

검열관 정현식을 도와 N명의 사람들로부터 얻을 수 있는 종합 행복 지수의 최댓값을 구해보자.

첫 번째 줄에 사람의 수 N(3 ≤ N ≤ 1, 000, 000)이 들어온다.

두 번째 줄부터는 한 줄 씩 1부터 N 사이의 i번 사람에 대한 정보가 들어온다.

i + 1(1 ≤ i ≤ N)번째 줄에는 정수 3개 p_i,i−3, p_i,i−2, p_i,i−1 가 입력된다.

j ≤ 0인 p_i,j를 입력받는 경우, j번 사람은 실존하지 않는 사람이기 때문에 무조건 p_i,j = 0이다. 그 외의 경우, p_i,j는 -10 이상 10 이하의 정수로 주어진다.

N명 중 일부를 요원으로 바꿔서 얻을 수 있는 종합 행복 수치 중 최댓값을 출력한다.

첫 예시에서 만약 아무도 요원으로 바꾸지 않으면 1번부터 4번까지 각자의 행복 지수는 0, 2, -3, 1로, 종합 행복 지수가 0+2+(−3) + 1 = 0이 된다.

그러나 넷 중 몇을 요원으로 대체하면 종합 행복 지수를 2까지 올릴 수 있다. 1, 2번을 요원으로 대체하면, 0+0+0+2=2로 종합 행복 지수가 2가 되며, 이 예시에서 3이상으로 종합 행복 지수를 늘리는 방법은 없기 때문에 답은 2이다.