시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 69 | 18 | 14 | 22.951% |
승규와 의석이는 다트게임을 즐겨한다. 다트게임은 $N \times M$ 형태의 격자모양 다트판에서 이뤄지며 승규와 의석이가 던지는 다트는 항상 다트판에 꽂힌다. 다트판은 1×1크기의 정사각형 칸 $N \times M$개로 나누어져 있다. 각각의 칸은 ($x, y$)로 나타내며 x는 위에서 몇 번째 칸인지를 의미하고 y는 왼쪽에서 몇 번째 칸인지를 의미한다. $x$와 $y$는 1부터 시작한다. 다트게임의 한 라운드는 다음과 같이 진행되며 승규와 의석이는 총 $K$ 라운드를 진행한다. ($R$ 은 $R$ 번째 라운드를 의미한다.)
의석이가 얻는 점수의 계산법은 다음과 같다.
$ f(i,j)=(A_i - C_j)^2 + (B_i - D_j)^2$ 일 때,
R 라운드에서 의석이가 얻는 점수는 $ (\sum_{i=1}^R{(f(i,R) \times X_i)}) $ 이다
게임이 끝난 후 승규가 화장실에 간 틈을 타 의석이는 점수를 조작하려고 한다.
의석이는 자신이 던진 다트중에서 최대 $L$ 개 다트의 좌표를 바꿀 수 있다.(좌표가 바뀐 다트는 다트판 위에 존재해야 한다.)
의석이는 자신이 얻는 원래 점수, 조작해서 얻을 수 있는 최대 점수, 조작해서 얻을 수 있는 최소 점수를 알고싶다.
예를 들어, 위와 같은 상황을 보자. 붉은색 다트는 승규가 던진 다트이고, 검은색 다트는 의석이가 던진 다트이다. 다트 위에 써져있는 숫자는 다트가 던져진 라운드를 의미한다. (가중치는 모두 1로 동일하다.) 위 상황에서 1라운드에서 의석이가 얻는 점수는 1점이고, 2라운드에서 의석이가 얻는 점수는 3점이다. 즉 의석이가 원래 얻는 총점은 4점이다. 여기서 의석이가 자신의 2라운드 다트를 (3,3)으로 옮기게 된다면 의석이가 얻을 수 있는 최대 총점인 14점을 얻게 된다. 혹은 여기서 의석이가 자신의 2라운드 다트를 (1,1)로 옮기게 된다면 의석이가 얻을 수 있는 최소 총점인 2점을 얻게 된다.
우리의 목적은 계산을 손가락으로밖에 못하는 의석이를 위해 대신 계산을 해주는 것이다. 의석이가 얻는 원래 점수, 조작해서 얻을 수 있는 최대 점수, 조작해서 얻을 수 있는 최소 점수를 구해주자. 단, 값이 너무 커질 수 있으므로 1,000,000,007로 나눈 나머지를 구해주자
첫째 줄에 양의 정수 $N, M, K, L$ 이 빈 칸을 사이에 두고 주어진다. $N$ 은 다트판의 세로 크기, $M$ 은 다트판의 가로 크기, $K$ 는 진행할 라운드 수, $L$ 은 바꿀 수 있는 다트의 수다. 둘째 줄부터 $K$ 개의 줄에 걸쳐 라운드의 순서대로 각 줄에 라운드의 정보인 양의 정수 $A_R, B_R, X_R, C_R, D_R$ 이 빈 칸을 사이에 두고 주어진다.
의석이의 원래 점수, 조작해서 얻을 수 있는 최대 점수, 조작해서 얻을 수 있는 최소 점수 각각을 한 줄에 하나씩 출력한다. 출력 할 때에는 1,000,000,007로 나눈 나머지를 출력해야 한다.
3 3 2 1 1 1 1 1 2 2 1 1 2 2
4 14 2
5 5 2 1 4 1 1 1 4 3 1 1 4 2
21 63 3
5 5 4 2 1 1 6 5 1 1 1 6 4 1 2 1 6 5 3 3 4 7 3 2
622 1367 202
5 5 6 2 4 1 2 1 4 3 1 3 4 5 1 5 1 4 1 4 2 8 5 1 4 5 5 3 5 4 5 3 3 2
488 898 300
5 5 20 9 4 1 2 1 4 3 1 3 4 5 1 5 1 4 1 4 2 8 5 1 4 5 5 3 5 4 5 3 3 2 1 1 2 4 3 3 1 4 3 1 3 1 10 4 5 1 1 6 3 2 3 1 8 4 2 1 4 8 4 2 2 4 8 2 2 5 3 6 1 1 5 2 5 1 2 1 4 8 1 3 2 4 6 1 1 3 4 6 1 2 3 5 6 4 4 1 1 7 1 3
7344 13562 4514
University > 인하대학교 > 2020 인하대학교 프로그래밍 경진대회(IUPC) G번