만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

서버 과부하

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

요약
n×n 격자의 접속 수에서 겹치지 않는 1×3 부분 격자를 최대 k개 골라 덮는 합의 최댓값을 구합니다.
난이도

보통10점 중 7점

유형
동적 계획법, 그리디, 배열
정답자
아직 제출이 없습니다

문제

SY 회사의 IT 팀은 서버 로그 데이터를 관리한다. 로그 데이터는 n×nn \times n 격자로 구성되며, 각 칸에는 특정 시간대의 서버 접속 횟수가 적혀 있다. 서버에 최근 과부하가 걸려 다운될 위험이 있다. 원인을 찾기 위해 IT 팀은 전용 1×31 \times 3 분석 도구를 사용한다. 이 도구는 n×nn \times n 격자 안의 1×31 \times 3 부분 격자 하나를 덮는다. 세로 길이는 1, 가로 길이는 3이다. 도구는 덮은 칸들의 접속 횟수 합을 보고한다. 도구는 최대 kk번까지 사용할 수 있고, 도구가 덮는 1×31 \times 3 부분 격자끼리는 겹치면 안 된다.

n×nn \times n 격자와 양의 정수 kk가 주어졌을 때, 도구를 최대 kk번 사용하고 덮은 부분 격자가 서로 겹치지 않을 때, 덮은 칸들의 접속 횟수 합의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫 줄에 두 정수 nn과 kk가 주어진다 (3≤n≤1 0003 \le n \le 1\,000, 1≤k≤5 0001 \le k \le 5\,000). nn은 격자의 크기이고, kk는 도구를 사용할 수 있는 최대 횟수이다. 이어지는 nn개의 줄에 격자의 값이 주어진다. ii번째 줄에는 ii번째 행의 nn개 접속 횟수가 첫 번째 열부터 마지막 열까지 차례로 들어 있다. 모든 접속 횟수는 1 이상 1 000 000 0001\,000\,000\,000 이하의 정수이다.

출력

도구를 최대 kk번 사용하고 덮은 1×31 \times 3 부분 격자가 서로 겹치지 않을 때, 덮은 칸들의 접속 횟수 합의 최댓값을 한 줄에 출력한다.

예제2

  1. 예제 1

    입력
    5 2
1 2 3 1 2
3 4 2 5 6
2 4 2 3 5
5 4 3 2 5
6 5 4 3 5
    예상 출력
    28

  2. 예제 2

    입력
    6 3
1 2 3 1 2 1
3 4 2 5 6 2
2 4 2 3 5 5
8 8 8 8 8 8
9 9 9 9 9 1
1 2 1 2 3 1
    예상 출력
    75