oj.uz

Submission #684342

# Submission time Handle Problem Language Result Execution time Memory
684342 2023-01-20T23:33:36 Z vjudge1 Selotejp (COCI20_selotejp) C++17
110 / 110
 272 ms 8428 KB 
#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.0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 7764 KB Output is correct
3 Correct 4 ms 2260 KB Output is correct
4 Correct 6 ms 4196 KB Output is correct
5 Correct 12 ms 8276 KB Output is correct
6 Correct 13 ms 8276 KB Output is correct
7 Correct 13 ms 8020 KB Output is correct
8 Correct 8 ms 7764 KB Output is correct
9 Correct 10 ms 7764 KB Output is correct
10 Correct 85 ms 8428 KB Output is correct

Subtask #2
35.0 / 35.0

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

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 9 ms 7764 KB Output is correct
3 Correct 4 ms 2260 KB Output is correct
4 Correct 6 ms 4196 KB Output is correct
5 Correct 12 ms 8276 KB Output is correct
6 Correct 13 ms 8276 KB Output is correct
7 Correct 13 ms 8020 KB Output is correct
8 Correct 8 ms 7764 KB Output is correct
9 Correct 10 ms 7764 KB Output is correct
10 Correct 85 ms 8428 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 1 ms 320 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 316 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 5 ms 2388 KB Output is correct
21 Correct 11 ms 4308 KB Output is correct
22 Correct 6 ms 8148 KB Output is correct
23 Correct 7 ms 8008 KB Output is correct
24 Correct 10 ms 8020 KB Output is correct
25 Correct 21 ms 8276 KB Output is correct
26 Correct 63 ms 7892 KB Output is correct
27 Correct 146 ms 7880 KB Output is correct
28 Correct 272 ms 8148 KB Output is correct