Submission #1100249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1100249		_rain_	Selotejp (COCI20_selotejp)	C++14	110 / 110	177 ms	16544 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define ll long long 
#define BIT(mask,x) ((mask)>>(x)&(1))
#define MASK(x) ((ll)(1)<<(x))
#define all(datastructure) datastructure.begin(),datastructure.end()
void compress(vector<int>&x){
	x.resize(unique(all(x))-x.begin());
}
template <class T1 , class T2>
	bool minU(T1 &a, T2 b){
		if (a>b) return a = b , true;
		return false;
	}
template <class T1 , class T2>
	bool maxU(T1 &a, T2 b){
		if (a<b) return a = b,true;
		return false;
	}
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
int Rand(int l , int r){
	return uniform_int_distribution<int> (l,r)(rng);
}

const int maxn = 1e3;
const int maxm = 10;
char c[maxn+2][maxm+2];
int dp[maxn+2][MASK(maxm)];
int tmp[MASK(maxm)] , add[maxn+2][MASK(maxm)] ;
bool go[MASK(maxm)];
int numrow , numcol;


bool ok(int id , int mask){
	for (int i = 0; i < numcol; ++i){
		if (BIT(mask,i) && c[id][i]=='.') return false;
	}
	return true;
}
int calc(int id , int mask){
	int ngang = 0 , ans = 0;
	for (int i = 0; i < numcol; ++i){
		if (BIT(mask,i)){
			ans += ngang;
			ngang = 0;
		}
		else {
			if (c[id][i]=='.'){
				ans += ngang;
				ngang = 0;
			}
			else {
				if (i==0||BIT(mask,i-1)||c[id][i-1]=='.') ngang = 1;
			}
		}
	}
	ans += ngang;
	return ans;
}
void upstate(int id){
	for (int mask = 0; mask < MASK(numcol); ++mask){
		tmp[mask] = dp[id-1][mask];
	}
	for (int mask = 0; mask < MASK(numcol); ++mask){
		for (int j = 0; j < numcol; ++j){
			if (BIT(mask,j))
				tmp[mask] = min(tmp[mask] , tmp[mask^MASK(j)]+1);
		}
	}
	for (int mask = MASK(numcol); mask >= 0; --mask){
		for (int j = 0; j < numcol; ++j){
			if (!BIT(mask,j))
				tmp[mask] = min(tmp[mask] , tmp[mask|MASK(j)]);
		}
	}
	return;
}

int32_t main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	#define name "main"
	if (fopen(name".inp","r")){
		freopen(name".inp","r",stdin);
		freopen(name".out","w",stdout);
	}
	cin >> numrow >> numcol;
	for (int i = 1; i <= numrow; ++i){
		for (int j = 0; j < numcol; ++j){
			cin >> c[i][j];
		}
	}
	memset(dp,0x3f,sizeof dp);
	dp[0][0] = 0;
	for (int i = 1; i <= numrow; ++i){
		for (int mask = 0; mask < MASK(numcol); ++mask) {
			add[i][mask] = calc(i,mask);
			go[mask] = ok(i,mask);
		}
		upstate(i);
		for (int mask = 0; mask < MASK(numcol); ++mask){
			if (go[mask]) dp[i][mask] = tmp[mask] + add[i][mask];
		}
	}
	int ans = numrow*numcol;
	for (int mask = 0; mask < MASK(numcol); ++mask)
	{
		ans = min(ans , dp[numrow][mask]);
		int id = 3;
		// cout << dp[id][mask] << "\n";
		// for (int j = 0; j < numcol; ++j) cout << BIT(mask,j);
		// cout << '\n';
	}
	cout << ans;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:110:7: warning: unused variable 'id' [-Wunused-variable]
  110 |   int id = 3;
      |       ^~
Main.cpp:85:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |   freopen(name".inp","r",stdin);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:86:10: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   86 |   freopen(name".out","w",stdout);
      |   ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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