아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

클레이 사격 게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약
N개의 점토를 어떤 순서로 맞힐지 정한다. i번 점토를 j번째 라운드에 맞히면 b[i]*j점을 얻고, 한 번 사용한 경로로는 다시 점토가 오지 않는다.
난이도

보통10점 중 7점

유형
동적 계획법, 비트 연산, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

클레이 사격 게임은 날아오는 클레이를 총으로 맞춰 떨어뜨리는 게임이다. 게임의 규칙은 다음과 같다.

  • 클레이는 화면 오른쪽에서 왼쪽으로 날아오며, 경로의 가운데를 지나가는 타이밍에 맞춰 총을 쏘아 클레이를 떨어뜨리면 점수를 얻는다.
  • 클레이가 날아오는 경로는 화면 아래에서 가까운 순서대로 1번 경로부터 N번 경로까지 모두 N개가 있다.
  • 총은 화면 아래 정중앙에서 발사된다. 발사된 총알은 즉시 경로상에서 가장 가까운 클레이를 맞춰 떨어뜨리지만, 클레이를 관통하지는 못한다.
  • 게임은 라운드 방식으로 진행되며, 첫 라운드는 1번 라운드이고 마지막 라운드는 N번 라운드이다.
  • 화면 아래에서 i번째로 가까운 클레이의 경로를 i번 경로라고 하면, 각 경로를 지나는 클레이는 라운드 시작 후 a[i]초마다 화면 중앙을 지나간다.
  • 클레이를 맞추면 다음 라운드가 시작된다. 단, 이전 라운드에서 맞춘 클레이가 지나가던 경로에서는 라운드가 초기화되어도 더 이상 클레이가 지나가지 않는다.
  • j번 라운드에 명중시킨 클레이가 지나가던 경로가 화면 아래에서부터 i번째 경로라면, 이번에 얻는 점수는 b[i] × j이다.
  • 더 이상 맞출 수 있는 클레이가 없으면 게임이 종료된다.

정진이는 게임을 플레이해서 얻을 수 있는 최고 점수가 궁금하다. 정진이를 도와주자.

입력

첫째 줄에는 클레이가 지나가는 경로의 개수 N이 주어진다.

다음 N개의 줄에는 두 정수 쌍 (a[i], b[i])가 주어진다. 화면 아래에서 가까운 순서가 i번째인 경로에서 클레이가 화면 중앙을 지나가는 간격이 a[i]이고, 그 클레이를 맞추었을 때의 점수가 b[i]이다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

제한

1 ≤ N ≤ 16

1 ≤ a[i] ≤ 100

1 ≤ b[i] ≤ 100

예제4

  1. 예제 1

    입력
    4
2 4
4 2
6 8
8 6
    예상 출력
    58

  2. 예제 2

    입력
    16
2 1
2 2
2 3
2 4
2 5
2 6
2 7
2 8
2 9
2 10
2 11
2 12
2 13
2 14
2 15
2 16
    예상 출력
    1496

  3. 예제 3

    입력
    16
2 100
3 99
5 98
7 97
11 96
13 95
17 94
19 93
23 92
29 91
31 90
37 89
41 88
43 87
47 86
53 85
    예상 출력
    12920

  4. 예제 4

    입력
    5
17 1
23 2
17 2
23 3
17 1
    예상 출력
    31