Submission #426095

#	Time	Username	Problem	Language	Result	Execution time	Memory
426095		keta_tsimakuridze	Selotejp (COCI20_selotejp)	C++14	110 / 110	343 ms	4488 KiB

Main

#include<bits/stdc++.h>
#define f first
#define s second
using namespace std;
const int N=2e5+5,mod=1e9+7,Inf=10000;
int t,n,a[1050][15],dp[1005][1050],f[N],cost[N],r;
 main(){
	cin>>n>>r;
	for(int i=1;i<=n;i++){
		for(int j=0;j<r;j++) {
			char c;
			cin>>c;
			if(c == '#') a[i][j] = 1; 	
		}
	}
	for(int j=0;j<=n;j++)
	for(int i=0;i<(1<<r);i++){
		dp[j][i] = Inf;
	}
	dp[0][0] = 0;
	int ans = Inf; 
	for(int i=1;i<=n;i++) {
		int mask = 0;
		for(int j=0;j<r;j++) {
			mask +=(1<<j)*a[i][j];
		} 
		f[0] = 1;
		for(int m = mask;;m=mask&(m-1)) {
			f[m] = 1; cost[m] = 0;
			for(int k=0;k<r;k++){
				int j = k;
				if((1<<k)&m) {
					cost[m]++;  
					while((1<<(j+1))&m) j++;
					k = j;
				}
			}
			if(!m) break;
		}
		
		for(int j=0;j<(1<<r);j++) {
			if(!f[j]) continue;
			for(int m=j;;m=(m-1)&j) {
				dp[i][j] = min(dp[i][j],dp[i-1][m] + cost[mask^j] + __builtin_popcount(j^m));
				if(i == n) ans = min(ans,dp[i][j]);
				if(!m) break;
			}
			f[j] = 0;
		} 
		for(int j=0;j<(1<<r);j++)  {
			for(int m = j;;m=j&(m-1)) {
				dp[i][m] = min(dp[i][j],dp[i][m]);
				if(!m) break;
			}
		}
	}
	cout<<ans;
}

Compilation message (stderr)

Main.cpp:7:2: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
    7 |  main(){
      |  ^~~~

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