Submission #966542

#	Time	Username	Problem	Language	Result	Execution time	Memory
966542		8pete8	Selotejp (COCI20_selotejp)	C++17	110 / 110	73 ms	17000 KiB

Main

#include<iostream>
#include<stack>
#include<map>
#include<vector>
#include<string>
#include<unordered_map>
#include <queue>
#include<cstring>
#include<limits.h>
#include <cassert>
#include<cmath>
#include<set>
#include<algorithm>
#include <iomanip>
#include<numeric> //gcd(a,b)
#include<bitset>
#include <cstdlib> 
#include <cstdint>
using namespace std;
#define ll long long
#define f first
//#define endl "\n"
#define s second
#define pii pair<int,int>
#define ppii pair<int,pii>
#define vi vector<int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
#define F(n) for(int i=0;i<n;i++)
#define lb lower_bound
#define ub upper_bound
#define fastio ios::sync_with_stdio(false);cin.tie(NULL);
//#pragma GCC optimize ("03,unroll-loops")
//#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
#define int long long
#define double long double
const int mod=998244353,mxn=2e3+5,lg=60,inf=1e18,minf=-1e18,Mxn=1e6+50000;
int dp[mxn+10][mxn+10],cost[mxn+10];
int n,m;
void print(int x){
	for(int i=0;i<m;i++){
		if(x&(1LL<<i))cout<<1;
		else cout<<0;
	}
	cout<<'\n';
}
int32_t main(){
	fastio
	cin>>n>>m;
	for(int i=1;i<(1LL<<m);i++)dp[0][i]=inf;
	int ans=inf;
	for(int i=1;i<=n;i++){
		string a;cin>>a;
		int mask=0;
		for(int j=0;j<m;j++)if(a[j]=='#')mask+=(1LL<<j);
		for(int j=0;j<(1LL<<m);j++){
			dp[i][j]=inf;
			dp[i][(j&mask)]=min(dp[i][(j&mask)],dp[i-1][j]);
		}
		for(int j=0;j<(1LL<<m);j++){
			dp[i][j]=min(dp[i][j],dp[i-1][j]);
			cost[j]=0;
			for(int k=0;k<m;k++){//subset dp to create
				if((a[k]=='#')&&!(j&(1LL<<k))&&(k==m-1||a[k+1]=='.'||(j&(1LL<<(k+1)))))cost[j]++;
				if(j&(1LL<<k))dp[i][j]=min(dp[i][j],dp[i][j^(1LL<<k)]+1);
			}
		}
		for(int j=0;j<(1LL<<m);j++){
			if((j&mask)!=j)dp[i][j]=inf;
			dp[i][j]=min(inf,dp[i][j]+cost[j]);
		}
		//stop
		for(int j=(1LL<<m)-1;j>=0;j--)for(int k=0;k<m;k++)dp[i][j]=min(dp[i][j],dp[i][j|(1LL<<k)]);
	}
	for(int i=0;i<(1LL<<m);i++)ans=min(ans,dp[n][i]);
	cout<<ans;
	return 0;
}
/*
*/

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