#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define per(i,n) for(int i=n-1;i>=0;i--)
#define fi first
#define se second
#define pb push_back
#define sz(a) (int)a.size()
#define vec(...) vector<__VA_ARGS__>
#define _3SgiE60 ios::sync_with_stdio(0),cin.tie(0)
typedef long long ll;
using pii=pair<int,int>;
using vi=vector<int>;
void print(){cout<<'\n';}
template<class h,class ...t>
void print(const h&v,const t&...u){cout<<v<<' ',print(u...);}
// e
int dp[2005][10][10][7];
signed main(){
_3SgiE60;
int n,k;
cin>>n>>k;
vec(vi) a(n,vi(n));
rep(i,n){
rep(j,n){
cin>>a[i][j];
}
}
if(k>5){
assert(0);
}
auto get_horizontal=[&](auto a,int n,int k)->vi{
vec(vi) fdp(n,vi(k+2));
rep(i,n){
rep(j,k+1){
if(i){
fdp[i][j]=max(fdp[i][j],fdp[i-1][j]);
fdp[i][j+1]=max(fdp[i][j+1],a[i]+a[i-1]+(i>=2?fdp[i-2][j]:0));
}
}
}
return fdp.back();
};
auto get_vertical=[&](auto a,int n,int k)->vec(vi){
// vec(vec(vec(vi))) dp(n,vec(vec(vi))(k+3,vec(vi)(4,vi(2))));
rep(i,n){
rep(j,k+3){
rep(msk,9){
rep(t,3){
dp[i][j][msk][t]=0;
}
}
}
}
// i,#of dominos taken,mask,vertical is taken or not.
// 00
// 01
// 10
// 11
rep(i,n){
rep(j,k+1){
rep(msk,4){
rep(t,2){
// i place nothing
int now=(!i?0:dp[i-1][j][msk][t]);
dp[i][j][msk][t]=max(dp[i][j][msk][t],now);
// i place vertical domino
if(!t){
int nj=j+1,nmsk=3,nt=1;
dp[i][nj][nmsk][nt]=max(dp[i][nj][nmsk][nt],a[0][i]+a[1][i]+now);
}
// i place horizontal domino on first row
if((msk==0 or msk==1) and i>0){
int nj=j+1,nmsk=2,nt=t;
dp[i][nj][nmsk][nt]=max(dp[i][nj][nmsk][nt],a[0][i]+a[0][i-1]+now);
}
// i place horizontal domino on second row
if((msk==0 or msk==2) and i>0){
int nj=j+1,nmsk=1,nt=t;
dp[i][nj][nmsk][nt]=max(dp[i][nj][nmsk][nt],a[1][i]+a[1][i-1]+now);
}
// i place horizontal domino on both first and second row
if(msk==0 and i>0){
int nj=j+2,nmsk=3,nt=t;
dp[i][nj][nmsk][nt]=max(dp[i][nj][nmsk][nt],a[0][i]+a[0][i-1]+a[1][i]+a[1][i-1]+now);
}
}
}
}
}
vec(vi) fdp(k+1,vi(2));
rep(j,k+1){
rep(t,2){
rep(msk,4){
fdp[j][t]=max(fdp[j][t],dp[n-1][j][msk][t]);
}
}
}
return fdp;
};
auto get_mid=[&](auto a,int n,int k)->vec(vi){
rep(i,n){
rep(j,k+3){
rep(msk,9){
rep(t,6){
dp[i][j][msk][t]=0;
}
}
}
}
// i,#of dominos taken,mask,number of vertical takes.
// 000
// 001
// 010
// 011
// 100
// 101
// 110
// 111
rep(i,n){
rep(j0,k+1){
rep(msk,8){
rep(j1,5){
int now=(!i?0:dp[i-1][j0][msk][j1]);
dp[i][j0][msk][j1]=max(dp[i][j0][msk][j1],now);
// plce vertical above
{
int nmsk=6;
int nj0=j0;
int nj1=j1+1;
int w=a[0][i]+a[1][i];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place vertical below
{
int nmsk=3;
int nj0=j0;
int nj1=j1+1;
int w=a[1][i]+a[2][i];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place horizontal on line 0
if(!(msk>>2&1) and i){
int nmsk=4;
int nj0=j0+1;
int nj1=j1;
int w=a[0][i]+a[0][i-1];
// if(i==1 and j1==1 and j0==0) print("go",nmsk,w+now);
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place horizontal on line 1
if(!(msk>>1&1) and i){
int nmsk=2;
int nj0=j0+1;
int nj1=j1;
int w=a[1][i]+a[1][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place horizontal on line 2
if(!(msk>>0&1) and i){
int nmsk=1;
int nj0=j0+1;
int nj1=j1;
int w=a[2][i]+a[2][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place horizontal ont line 0,1,2
if(msk==0 and i){
int nmsk=7;
int nj0=j0+3;
int nj1=j1;
int w=a[2][i]+a[2][i-1]+a[1][i]+a[1][i-1]+a[0][i]+a[0][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place horizontal on line 0,1
if(!(msk>>2&1) and !(msk>>1&1) and i){
int nmsk=6;
int nj0=j0+2;
int nj1=j1;
int w=a[1][i]+a[1][i-1]+a[0][i]+a[0][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place horizontal on line 0,2
if(!(msk>>2&1) and !(msk>>0&1) and i){
int nmsk=5;
int nj0=j0+2;
int nj1=j1;
int w=a[2][i]+a[2][i-1]+a[0][i]+a[0][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place horizontal on line 1,2
if(!(msk>>1&1) and !(msk>>0&1) and i){
int nmsk=3;
int nj0=j0+2;
int nj1=j1;
int w=a[2][i]+a[2][i-1]+a[1][i]+a[1][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place vertical below and horizontal on line 0
if(!(msk>>2&1) and i){
int nmsk=7;
int nj0=j0+1;
int nj1=j1+1;
int w=a[1][i]+a[2][i]+a[0][i]+a[0][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
// place vertical above and horizontal on line 2
if(!(msk>>0&1) and i){
int nmsk=7;
int nj0=j0+1;
int nj1=j1+1;
int w=a[0][i]+a[1][i]+a[2][i]+a[2][i-1];
dp[i][nj0][nmsk][nj1]=max(dp[i][nj0][nmsk][nj1],w+now);
}
}
}
}
}
// print("hi ",dp[1][2][3][0]);
// cout<<"hi "<<dp[1][1][4][1]<<"\n";
vec(vi) fdp(k+1,vi(5));
rep(j0,k+1){
rep(msk,8){
rep(j1,5){
fdp[j0][j1]=max(fdp[j0][j1],dp[n-1][j0][msk][j1]);
}
}
}
return fdp;
};
auto af=[&](auto a,int k)->int{
// place at most k/2 vertically
int h=sz(a),w=sz(a[0]);
vec(vec(vi)) sdp(h,vec(vi)(k+1,vi(2)));
// from top to bottom
rep(i,h){
// i place 0 vertical domino
{
vi dp=get_horizontal(a[i],w,k);
rep(j,k+1){
rep(nj,k+1){
if(j+nj>k) continue;
rep(t,2){
sdp[i][j+nj][t]=max(sdp[i][j+nj][t],dp[nj]+(!i?0:sdp[i-1][j][t]));
}
}
}
// if(i==1) print(dp[1]);
}
// i place 1 vertical domino
{
if(i+1<h){
vec(vi) dp=get_vertical(vector<vi>{a[i],a[i+1]},w,k);
rep(j0,k+1){
rep(j1,k+1){
if(j0+j1>k) continue;
rep(t0,2){
rep(t1,2){
if(t0==1 and t1==1) continue;
int nt=max(t0,t1);
int nj=j0+j1;
sdp[i+1][nj][nt]=max(sdp[i+1][nj][nt],dp[j1][t1]+(!i?0:sdp[i-1][j0][t0]));
}
}
}
}
}
}
}
int res=0;
if(h<500){
vec(vec(vi)) pdp(h,vec(vi)(k+1,vi(2)));
// from bottom to top
per(i,h){
// i place 0 vertical domino
{
vi dp=get_horizontal(a[i],w,k);
rep(j,k+1){
rep(nj,k+1){
if(j+nj>k) continue;
rep(t,2){
pdp[i][j+nj][t]=max(pdp[i][j+nj][t],dp[nj]+(i==h-1?0:pdp[i+1][j][t]));
}
}
}
}
// i place 1 vertical domino
{
if(i+1<h){
vec(vi) dp=get_vertical(vector<vi>{a[i],a[i+1]},w,k);
rep(j0,k+1){
rep(j1,k+1){
if(j0+j1>k) continue;
rep(t0,2){
rep(t1,2){
if(t0==1 and t1==1) continue;
int nt=max(t0,t1);
int nj=j0+j1;
pdp[i][nj][nt]=max(pdp[i][nj][nt],dp[j1][t1]+(i==h-2?0:pdp[i+2][j0][t0]));
}
}
}
}
}
}
}
res=0;
rep(i,h){
rep(j0,k+1){
rep(j1,k+1){
rep(t0,2){
rep(t1,2){
if(j0+j1+t0+t1<=k){
int now=(i+1<h?pdp[i+1][j1][t1]:0);
res=max(res,sdp[i][j0][t0]+now);
}
}
}
}
}
}
rep(i,h-2){
vec(vi) now_dp=get_mid(vector<vi>{a[i],a[i+1],a[i+2]},w,k);
rep(j0,k+1){
rep(j1,k+1){
rep(j2,k+1){
rep(t0,2){
rep(t1,2){
rep(t2,5){
if(j0+j1+j2+t0+t1+t2<=k){
int now=now_dp[j2][t2];
if(i){
now+=sdp[i-1][j0][t0];
}
if(i+3<h){
now+=pdp[i+3][j1][t1];
}
// if(now==19){
// print(i);
// }
res=max(res,now);
}
}
}
}
}
}
}
}
}
return res;
};
int res;
res=af(a,k);
vec(vi) na(n,vi(n));
rep(i,n){
rep(j,n){
na[j][n-1-i]=a[i][j];
}
}
// res=max(res,af(na,k));
int sun=0;
rep(i,n){
rep(j,n){
sun+=a[i][j];
}
}
print(sun-res);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
63 ms |
3796 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
5 ms |
520 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1503 ms |
37760 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
972 ms |
22624 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
458 ms |
11320 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2197 ms |
38200 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
274 ms |
32332 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
596 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
241 ms |
32312 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
82 ms |
8508 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
249 ms |
32308 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
