oj.uz

Submission #1100249

# Submission time Handle Problem Language Result Execution time Memory
1100249 2024-10-13T10:51:20 Z _rain_ Selotejp (COCI20_selotejp) C++14
110 / 110
 177 ms 16544 KB 
#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

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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10320 KB Output is correct
2 Correct 119 ms 16544 KB Output is correct
3 Correct 19 ms 16468 KB Output is correct
4 Correct 40 ms 16460 KB Output is correct
5 Correct 120 ms 16460 KB Output is correct
6 Correct 123 ms 16460 KB Output is correct
7 Correct 127 ms 16544 KB Output is correct
8 Correct 128 ms 16536 KB Output is correct
9 Correct 120 ms 16536 KB Output is correct
10 Correct 148 ms 16536 KB Output is correct

Subtask #2
35.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10064 KB Output is correct
2 Correct 4 ms 10064 KB Output is correct
3 Correct 4 ms 10064 KB Output is correct
4 Correct 4 ms 10064 KB Output is correct
5 Correct 5 ms 10064 KB Output is correct
6 Correct 4 ms 10064 KB Output is correct
7 Correct 4 ms 10064 KB Output is correct
8 Correct 4 ms 10064 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10320 KB Output is correct
2 Correct 119 ms 16544 KB Output is correct
3 Correct 19 ms 16468 KB Output is correct
4 Correct 40 ms 16460 KB Output is correct
5 Correct 120 ms 16460 KB Output is correct
6 Correct 123 ms 16460 KB Output is correct
7 Correct 127 ms 16544 KB Output is correct
8 Correct 128 ms 16536 KB Output is correct
9 Correct 120 ms 16536 KB Output is correct
10 Correct 148 ms 16536 KB Output is correct
11 Correct 4 ms 10064 KB Output is correct
12 Correct 4 ms 10064 KB Output is correct
13 Correct 4 ms 10064 KB Output is correct
14 Correct 4 ms 10064 KB Output is correct
15 Correct 5 ms 10064 KB Output is correct
16 Correct 4 ms 10064 KB Output is correct
17 Correct 4 ms 10064 KB Output is correct
18 Correct 4 ms 10064 KB Output is correct
19 Correct 4 ms 16376 KB Output is correct
20 Correct 23 ms 16468 KB Output is correct
21 Correct 47 ms 16460 KB Output is correct
22 Correct 116 ms 16460 KB Output is correct
23 Correct 119 ms 16460 KB Output is correct
24 Correct 118 ms 16460 KB Output is correct
25 Correct 128 ms 16540 KB Output is correct
26 Correct 135 ms 16536 KB Output is correct
27 Correct 147 ms 16472 KB Output is correct
28 Correct 177 ms 16540 KB Output is correct