#include <bits/stdc++.h>
#define int ll
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
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){
exit(0);
}
auto get_horizontal=[&](auto a,int n,int k)->vi{
vec(vi) dp(n,vi(k+2));
rep(i,n){
rep(j,k+1){
if(i){
dp[i][j]=max(dp[i][j],dp[i-1][j]);
dp[i][j+1]=max(dp[i][j+1],a[i]+a[i-1]+(i>=2?dp[i-2][j]:0));
}
}
}
return dp.back();
};
auto get_vertical=[&](auto a,int n,int k)->vec(vi){
// vec(vec(vi)) dp(n,vec(vi)(k+1,vi(4)));
vec(vec(vec(vi))) dp(n,vec(vec(vi))(k+3,vec(vi)(4,vi(2))));
// 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 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]));
}
}
}
}
}
}
}
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]));
}
}
}
}
}
}
}
int 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);
}
}
}
}
}
}
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 |
Correct |
1563 ms |
7884 KB |
Output is correct |
2 |
Correct |
1439 ms |
7916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
17 ms |
472 KB |
Output is correct |
2 |
Correct |
19 ms |
456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4019 ms |
74368 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
340 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4105 ms |
46920 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4075 ms |
22268 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
4082 ms |
76092 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
328 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
321 ms |
44512 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 |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
364 ms |
45288 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 |
81 ms |
11852 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
323 ms |
45196 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |