oj.uz

Submission #622804

# Submission time Handle Problem Language Result Execution time Memory
622804 2022-08-04T14:48:23 Z inksamurai Domino (COCI15_domino) C++17
30 / 160
 4000 ms 36652 KB 
#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

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) 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 get_mid=[&](auto a,int n,int k)->vec(vi){
		vec(vec(vec(vi))) dp(n,vec(vec(vi))(k+4,vec(vi)(8,vi(8))));
		// 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.back()[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]));
								}
							}
						}
					}
				}
			}
		}

		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);
							}
						}
					}
				}
			}
		}

		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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3140 ms 5040 KB Output is correct
2 Correct 3168 ms 5072 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 468 KB Output is correct
2 Correct 42 ms 468 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4067 ms 34732 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 340 KB Output is correct
2 Correct 3 ms 340 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4059 ms 21208 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4054 ms 11048 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4045 ms 36652 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 233 ms 32300 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 233 ms 32304 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 64 ms 8492 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #16
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 259 ms 32320 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -