oj.uz

Submission #622808

# Submission time Handle Problem Language Result Execution time Memory
622808 2022-08-04T15:00:29 Z inksamurai Domino (COCI15_domino) C++17
10 / 160
 4000 ms 38140 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

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 348 ms 3852 KB Output is correct
2 Correct 345 ms 3856 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 468 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1496 ms 37772 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3132 ms 11704 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2338 ms 38140 KB Output isn't correct
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 250 ms 32308 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 596 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 253 ms 32312 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 69 ms 8524 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 269 ms 32304 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -