Submission #474110

#	Time	Username	Problem	Language	Result	Execution time	Memory
474110		CaroLinda	Selotejp (COCI20_selotejp)	C++14	110 / 110	373 ms	2536 KiB

Main

#include <bits/stdc++.h>

#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()
 
const int MAXN = 1010 ;
const int MAX = 1e4+10 ;
 
using namespace std ;

int N , M , toGet, toFill = 1 , inf ;
int dp[2][(1<<11)] ;
char grid[MAXN][12] ;
vector<int> freq[MAX+100] ;

bool isOn(int m, int i ) { return ((1<<i)&m) != 0 ; }

void dijkstra(int l)
{
	
	for(int i = 0 ; i < MAX ; i++ )
		while( !freq[i].empty() )
		{
			int e = freq[i][0] ;
			
			if( dp[toFill][e] < i ) 
			{
				freq[i][0] = freq[i].back() ;
				freq[i].pop_back() ;
				continue ;
			}
			
			vector<pair<int,int> > neigh ;
						
			for(int g = 0 ; g < M ; g++ )
			{
				
				if(grid[l][g] == '#')
					neigh.push_back( make_pair(e^(1<<g) , i+!isOn(e,g) ) ) ;

			}	
			
			for(auto viz : neigh )
			{
				if(viz.first == 1 && l == 0 && viz.second == 1 ) cout << "----- " << e << endl ;
				if( dp[toFill][viz.first] <= viz.second ) continue ;
				freq[ dp[toFill][viz.first] = viz.second ].push_back(viz.first) ;
			}	
			
			swap(freq[i][0] , freq[i].back()) ;
			freq[i].pop_back() ;
		}
	
}

int main()
{
	scanf("%d %d", &N, &M ) ;
	for(int i = 0 ; i < N ; i++ )
		for(int j = 0 ; j < M ; j++ ) scanf(" %c", &grid[i][j] ) ;
		
	inf = (N*M)+2 ; 
	for(int i = 1 ; i < (1<<M) ; i++ ) dp[0][i] = __builtin_popcount(i) ;
	
	for(int i = 0 ; i < N ; i++, swap(toGet, toFill) ) 
	{
		for(int j = 0 ; j < (1<<M) ; j++ )
		{			
			int t = 0 , m = j ;
			dp[toFill][j] = inf ;
			
			bool ok = false ;
			
			for(int g = 0 ; g < M ; g++ )
			{
				if( !isOn(j,g) ) continue ;
				if( grid[i][g] == '.' ) ok = true ;
				if(i-1 >= 0 && grid[i-1][g] == '.')
				{
					t++ ;
					m^=(1<<g) ;
				}
			}	
			
			if(ok ) continue ;
			
			int qtd = 0 , isGoing = -1 ;
			for(int g = 0 ;g < M ; g++ )
			{
				if( isOn(j,g) ) 
				{
					isGoing = -1 ;
					continue ;
				}
				
				if( grid[i][g] == '.' ) isGoing = -1 ;
				else 
				{
					if(isGoing == -1 ) qtd++ ;
					isGoing = 1 ;
				}
				
			}
			
			dp[toFill][j] = min(inf,qtd+dp[toGet][m]+t) ;
				
		}
		
			
		for(int j = 0 ; j <= N*M+10 ; j++ ) freq[j].clear() ;	
		for(int j = 0 ; j < (1<<M) ; j++ ) freq[ dp[toFill][j] ].push_back(j) ; 

		dijkstra(i) ;


	}
	
	int ans = *min_element(dp[toGet] , dp[toGet]+(1<<M)) ;
	printf("%d\n" , ans ) ;
	
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |  scanf("%d %d", &N, &M ) ;
      |  ~~~~~^~~~~~~~~~~~~~~~~~
Main.cpp:69:38: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |   for(int j = 0 ; j < M ; j++ ) scanf(" %c", &grid[i][j] ) ;
      |                                 ~~~~~^~~~~~~~~~~~~~~~~~~~~

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