Submission #377826

#	Time	Username	Problem	Language	Result	Execution time	Memory
377826		kshitij_sodani	Selotejp (COCI20_selotejp)	C++14	110 / 110	565 ms	12652 KiB

Main

//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
//define endl '\n'
llo n,m;
llo it[1001][11];
llo dp[1001][2001];
llo val[50][50][10];//first half is i has k bits set in (j^second half of number)

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n>>m;
	for(llo i=0;i<n;i++){
		string s;
		cin>>s;
		for(llo j=0;j<m;j++){
			
			if(s[j]=='#'){
				it[i][j]=1;
			}
			else{
				it[i][j]=0;
			}
		}
	}
	for(llo j=0;j<(1<<m);j++){
		dp[0][j]=1e9;
	}
	dp[0][0]=0;
	for(llo i=1;i<=n;i++){
		//cout<<i<<endl;
		for(llo j=0;j<32;j++){
			for(llo k=0;k<32;k++){
				for(llo p=0;p<=5;p++){
					val[j][k][p]=1e9;
				}
			}
		}
		for(llo j=0;j<(1<<m);j++){
			for(llo k=0;k<32;k++){
				llo kk=__builtin_popcount(k&(((j-(j&31)))/32));

				val[j&31][k][kk]=min(val[j&31][k][kk],dp[i-1][j]);
			}
		}

		for(llo j=0;j<(1<<m);j++){

			dp[i][j]=1e9;
			llo stt=0;
			for(llo k=0;k<m;k++){
				if(it[i-1][k]==0 and (j&(1<<k))){
					stt=1;
					break;
				}
			}
			if(stt){
				continue;
			}

			llo ba=-2;
			llo cot=0;
			for(llo k=0;k<m;k++){
				if(it[i-1][k]==1){
					if((1<<k)&j){

					}
					else{
						if(k>ba+1){
							cot++;
						}
						ba=k;
					}
				}
			}
		/*	for(llo k=0;k<(1<<m);k++){
				dp[i][j]=min(dp[i][j],dp[i-1][k]+cot+__builtin_popcount(j)-__builtin_popcount(j&k));
			}*/
			for(llo k=0;k<32;k++){
				for(llo kk=0;kk<=5;kk++){
					llo co=__builtin_popcount(j)-kk-__builtin_popcount((j&31)&k);
					//if(val[k][(j-(j&31))/32][kk]+co+cot==2){
						//cout<<i<<":"<<j<<":"<<k<<":"<<kk<<endl;

						//cout<<val[k][(j-(j&31))/32][kk]<<"//"<<co<<"//"<<cot<<endl;
					//}
					dp[i][j]=min(dp[i][j],val[k][(j-(j&31))/32][kk]+co+cot);
				}
			}
			
		}
	}
	//cout<<33<<endl;
//	cout<<n<<":"<<m<<endl;
	//return 0;
	llo ans=n*m;
	/*for(llo i=0;i<(1<<m);i++){
		cout<<dp[1][i]<<":";
	}
	cout<<endl;*/
	for(llo i=0;i<(1<<m);i++){
		//cout<<i<<":"<<dp[n][i]<<endl;
	//	continue;
		ans=min(ans,dp[n][i]);
	/*	if(dp[n][i]==2){
			cout<<i<<":"<<endl;
		}*/

	}


	cout<<ans<<endl;







 
	return 0;
}

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