문제
요즘 정올 학생들 사이에서 유행하는 카드게임이 있다.
게임 방식은 다음과 같다.
n개의 카드를 가지고 시작한다.
각 카드에는 1부터 m까지의 숫자가 써 있다. 숫자 중 일부는 앞면에, 나머지는 뒷면에 써 있다.
1부터 m까지 수 중 어떤 수도 앞, 뒷면 모두에 써 있거나, 아무 데도 안 써 있는 경우는 없다.
카드는 한 쪽 면만 보이게 테이블에 차례대로 놓여 있다.
한 턴에 l과 r을 정하고 시작한다.
이는 이 턴에는 l번 카드부터 r번 카드까지만 사용해서 게임을 한다는 것을 의미한다. 처음에는 모든 카드가 앞면만 보이게 놓여져 있다.
게임을 하는 플레이어는 l번부터 r번 카드까지 사용해서 횟수 제한 없이 원하는 만큼의 카드를 뒤집어서, 뒷면이 보이게 할 수 있다.
이 과정이 끝난 후 플레이어는 1부터 m까지 수 중 하나라도 카드에 보이면, 그 수의 제곱을 점수에 더한다.
점수가 가장 높은 플레이어가 이긴다.
예를 들어보자
l=1이고, r=2인 경우에 대해서 살펴보자. 즉 3번 카드는 이번 게임에 쓰지 않는다.
승민이는 카드를 뒤집지 않았다. 현재 테이블에 보이는 수는 1,2,4,5로 그들을 모두 제곱해서 더하면 46점이다.
서진이는 첫번째 카드만 뒤집었다. 보이는 수는 3,4,5로 제곱의 합은 50이다.
(점수를 계산할 때 중복된 수는 점수계산에 하나씩만 반영되는 것에 유의한다.
4와 5가 두 번씩 등장하지만 점수 계산시에는 하나씩만 계산에 적용한다.)
서연이는 둘 다 뒤집었다. 둘 다 뒤집으면 1,2,3,4,5가 모두 보이므로 그들의 제곱의 합은 55이다.
그래서 둘 다 뒤집은 서연이가 승리자다.
이 게임이 유행이 된 후, 아직 브론즈인 당신은 플레티넘, 다이아몬드로 올라가기 위하여 프로그래밍의 도움을 받기로 했다.
카드가 주어졌을 때 각 판마다 낼 수 있는 최대 점수를 구하는 프로그램을 작성하라.
입력
첫 줄에 n, m, q가 각각 주어진다.
n과 m은 문제에 주어진 대로 카드의 수와 번호의 수이다.
q는 총 판의 수이다.
다음 n줄에 1번부터 n번까지 각 카드의 앞면에 써있는 번호들이 입력된다.
각 줄에는 첫 번째 수로 앞면에 써있는 번호의 개수인 xi 가 주어지고, 공백을 사이에 두고 xi개의 앞면에 써있는 번호들이 입력된다.
1부터 m까지 번호 중에서 입력되지 않은 번호들은 모두 뒷면에 써있는 번호이다.
그 다음 q개의 줄엔 li과 i이 입력된다.
이는 각 판의 l과 r값이며, 이번 판에서 li번 카드부터 ri번 카드만 사용한다는 것을 의미한다.
부분문제의 제약 형식
모든 부분문제에 있어서 1 ≤ n×m ≤ 106, 1 ≤ q ≤ 106 를 만족한다.
모든 부분문제에서 0 ≤ xi ≤ m, 1 ≤ li ≤ ri ≤ n을 만족한다. 모든 입력값은 정수이다.
출력
부분문제
| 번호 | 점수 | 조건 |
|---|---|---|
| #1 | 40점 | m≤10, q≤10 |
| #2 | 60점 | 주어진 제약 조건 외에 아무 제약조건이 없다. |
예제 #1
2 3 2
2 2 1
2 2 3
1 1
1 2
9
14
예제 #2
2 5 1
3 4 2 1
2 4 3
1 2
50
로그인해야 코드를 작성할 수 있어요.