시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)84191329.545%

문제

둘레가 1만큼 증가하면? 세미나

2024년부터 고려대학교에서 알고리즘과 관련된 세 동아리인 MatKor, ALPS, AlKor는 기존에 동아리별로 진행하던 세미나들을 하나로 합쳐 합동 세미나로 진행하기로 하였다. 합동 세미나는 수준에 따라 분반을 입문(1학기만 진행), 초급, 중급, 고급 분반으로 나눈 후 동아리별로 분반을 한 개 혹은 두 개씩 담당하여 진행하고 있다. 학생은 수준에 따라 자유롭게 분반을 선택해 세미나를 들으며, 여러 분반을 동시에 들을 수도 있다.

재현이는 $N$명의 강사 후보 중에서 $0$명 이상을 골라 합동 세미나 강사진을 정하고자 한다. 각 강사 후보는 MatKor력, ALPS력, AlKor력, 강의력 네 가지 항목의 수치로 평가되었다. 각 수치는 음수일 수 있으며, 수치의 크기가 좋고 나쁨을 의미하는 것은 아니다. 재현이가 몇 명의 강사를 고르면, 재현이가 고른 모든 강사의 MatKor력의 합, ALPS력의 합, AlKor력의 합, 강의력의 합을 구한 뒤, 각 항목을 제곱하여 더한 값을 강사진의 점수라 할 때, 이를 최대로 하고 싶다.

점수가 최대가 되도록 강사진을 구성해 보자.

입력

첫 번째 줄에 강사 후보의 수 $N(1\le N\le 100)$이 주어진다.

두 번째 줄부터 $N$개의 줄에 걸쳐 $i(1\le i\le N)$번째 강사의 MatKor력, ALPS력, AlKor력, 강의력을 의미하는 정수 $a_i,b_i,c_i,d_i(-10^4\le a_i,b_i,c_i,d_i\le 10^4)$가 공백으로 구분되어 주어진다.

출력

첫 번째 줄에 점수가 최대가 되도록 강사진을 구성할 때, 강사진에 포함된 강사 후보의 수 $M(0\le M\le N)$을 출력한다.

$M$이 $0$이 아니라면 두 번째 줄에 재현이가 구성한 강사진에 포함된 $M$명의 강사 후보의 번호를 공백으로 구분해 오름차순으로 출력한다.

만약, 점수를 최대로 하는 방법이 여러 개 있다면 그중 아무거나 하나를 출력한다.

서브태스크

번호배점제한
124

$N \le 20$

276

추가적인 제한 조건 없음

예제 입력 1

2
0 0 0 2
0 0 0 -3

예제 출력 1

1
2

두 번째 강사만을 골랐을 때 강사진의 점수가 $9$로 최대이다.

예제 입력 2

8
0 0 0 5
0 0 0 -5
0 0 5 0
0 0 -5 0
0 5 0 0
0 -5 0 0
5 0 0 0
-5 0 0 0

예제 출력 2

4
1 3 6 8

출처

University > 고려대학교 > MatKor Cup > 제6회 고려대학교 MatKor Cup: 2025 Winter I번

채점 및 기타 정보

  • 예제는 채점하지 않는다.