#include #include #include #define MAXN 300005 #define INF 1000000000 #define max(a, b) ((a) > (b) ? (a) : (b)) typedef struct { int score, resist, r, c; } State; // 최대 힙 State heap[MAXN * 10]; int heap_size = 0; void push(State s) { int i = ++heap_size; while (i > 1 && (heap[i/2].score < s.score || (heap[i/2].score == s.score && heap[i/2].resist < s.resist))) { heap[i] = heap[i/2]; i /= 2; } heap[i] = s; } State pop() { State top = heap[1]; State last = heap[heap_size--]; int parent = 1, child = 2; while (child <= heap_size) { if (child + 1 <= heap_size && (heap[child+1].score > heap[child].score || (heap[child+1].score == heap[child].score && heap[child+1].resist > heap[child].resist))) child++; if (last.score > heap[child].score || (last.score == heap[child].score && last.resist > heap[child].resist)) break; heap[parent] = heap[child]; parent = child; child *= 2; } heap[parent] = last; return top; } // 점수 배열 및 스테이지 정보 int elite1[MAXN], elite3[MAXN]; int A1[MAXN], A2[MAXN+1], A3[MAXN]; // 점수 및 저항력 DP 배열 (중앙줄만 저장) int maxScore[4][MAXN]; // row 1~3, col 최대 N+2 int N; int K; void update(int r, int c, int new_score, int new_resist) { if (new_resist < 0) return; if (maxScore[r][c] < new_score) { maxScore[r][c] = new_score; push((State){ new_score, new_resist, r, c }); } } int main() { scanf("%d %d", &N, &K); for (int i = 1; i <= N; i++) scanf("%d", &elite1[i]); for (int i = 1; i <= N; i++) scanf("%d", &elite3[i]); for (int i = 1; i <= N; i++) scanf("%d", &A1[i]); for (int i = 1; i <= N+1; i++) scanf("%d", &A2[i]); for (int i = 1; i <= N; i++) scanf("%d", &A3[i]); // 초기화 memset(maxScore, -1, sizeof(maxScore)); push((State){ 0, K, 2, 0 }); maxScore[2][0] = 0; while (heap_size > 0) { State cur = pop(); int s = cur.score; int r = cur.r; int c = cur.c; int resist = cur.resist; if (r == 2 && c == N+2) { printf("%d\n", s); return 0; } // 다음 이동 if (r == 2) { if (c == 0) { // START → (2,1) int ns = s + A2[1]; update(2, 1, ns, resist); // 일반 스테이지: 소모1 회복1 => 변화없음 } else if (1 <= c && c <= N) { // (2,c) → (1,c) int cost = 1 + (elite1[c] == 2); int ns = s + A1[c]; update(1, c, ns, resist - cost); // (2,c) → (2,c+1) ns = s + A2[c+1]; update(2, c+1, ns, resist); // 소모1 회복1 // (2,c) → (3,c) cost = 1 + (elite3[c] == 2); ns = s + A3[c]; update(3, c, ns, resist - cost); } else if (c == N+1) { // (2,N+1) → (2,N+2) update(2, N+2, s, resist - 1); // GOAL: 점수 없음, 소모만 } } else if (r == 1 && c < N) { // (1,c) → (1,c+1) int cost = 1 + (elite1[c+1] == 2); int ns = s + A1[c+1]; update(1, c+1, ns, resist - cost); // (1,c) → (2,c+1) ns = s + A2[c+1]; update(2, c+1, ns, resist); // 일반: 소모1 회복1 } else if (r == 3 && c < N) { // (3,c) → (2,c+1) int ns = s + A2[c+1]; update(2, c+1, ns, resist); // 일반 // (3,c) → (3,c+1) int cost = 1 + (elite3[c+1] == 2); ns = s + A3[c+1]; update(3, c+1, ns, resist - cost); } } return 0; }

제출 #111495

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: