제출 #684342

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
684342		vjudge1	Selotejp (COCI20_selotejp)	C++17	110 / 110	272 ms	8428 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define pb push_back

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int n,m; cin>>n>>m;
	const int MAX = 1e9;
	vector<vector<int> > dp1(n+1,vector<int>((1<<m),MAX)); // [row][mask] = min...
	vector<vector<int> > dp2(n+1,vector<int>((1<<m),MAX)); // [row][mask] = min...
	
	char ma[n][m];
	for (int i=0; i<n; i++){
		for (int j=0; j<m; j++) cin>>ma[i][j];
	}
	
	// SI O SI los unos
	vector<int> rows={-1};
	for (int i=0; i<n; i++){
		int c=0;
		for (int j=0; j<m; j++){
			if (ma[i][j]=='#'){
				c|=(1<<j);
			}
		}
		rows.pb(c);
	}
	
	dp1[0][0]=dp2[0][0]=0; // = que una fila de puntos
	for (int i=1; i<=n; i++){ // do row by row
		// process dp1:
		for (int mk=0; mk<(1<<m); ++mk){
			int ch=rows[i]|mk;
			if (ch!=rows[i]) continue; // can't do (not valid)
			int zeros=0;
			//for (int pos=0; pos<m; pos++){
				// greedy with zeros ***
			//}
			int numi=rows[i]^mk;
			if (numi&1) numi<<=1;
			bool zero=true;
			while(numi){
				numi>>=1;
				if (zero && (numi&1)) zeros++; //
				if (numi&1) zero=false;
				else zero=true;
			}
			for (int s=mk; ; s=(s-1)&mk){
				if (dp2[i-1][s]==MAX) continue; // before is not valid
				dp1[i][mk]=min(dp1[i][mk], zeros+__builtin_popcount(s^mk)+dp2[i-1][s]);
				if (s==0) break;
			}
		}
		// process dp2:
		for (int mk=0; mk<(1<<m); ++mk){ // teniendo si o si estos bits (al menos)
			int ch=rows[i]|mk;
			if (ch!=rows[i]) continue; // can't do (not valid)
			int newmk = (1<<m)-1; //
			newmk = newmk^mk;
			for (int s=newmk; ; s=(s-1)&newmk){
				dp2[i][mk]=min(dp2[i][mk], dp1[i][s|mk]);
				if (s==0) break;
			}
		}
	}
	int answer=MAX;
	for (int mk=0; mk<(1<<m); mk++){
		answer=min(answer,dp1[n][mk]);
	}
	cout<<answer<<'\n';
	
	return 0;
}

• Subtask 1: 35 / 35
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40