Submission #104979

#TimeUsernameProblemLanguageResultExecution timeMemory
104979antimirageLamps (JOI19_lamps)C++14
51 / 100
1081 ms20032 KiB
# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
 
int n, dp[N][2], pref[N][2];

unordered_set <char> st;
 
string a, b;
 
inline int calc (int l, int r, int type){
 
	  if (type == 0)
			return pref[r][0] - pref[l - 1][0] + (b[l - 1] == b[l] && b[l] == '0');
 
	  return pref[r][1] - pref[l - 1][1] + (b[l - 1] == b[l] && b[l] == '1');
}
main(){
 
	  memset( dp, 0x3f3f3f3f, sizeof(dp) );
 
	  cin >> n >> a >> b;
 
	  a = ' ' + a;
	  b = ' ' + b;
 
	  for (int i = 1; i <= n; i++){
		  
			st.insert(a[i]);
 
			if (b[i] != b[i - 1])
				  pref[i][ b[i] - 48 ] = 1;
 
			pref[i][0] += pref[i - 1][0];
			pref[i][1] += pref[i - 1][1];
	  }
	  if (st.size() == 1 && a[1] == '0'){
		cout << calc(1, n, 1) << endl;
		return 0;
	  }
	  dp[0][0] = 0;
 
	  for (int i = 1; i <= n; i++){
 
			if (a[i] == b[i])
				  dp[i][0] = min( dp[i - 1][1], dp[i - 1][0] );
 
			if (a[i] != b[i])
				  dp[i][1] = min( dp[i - 1][1], dp[i - 1][0] + 1);
 
			for (int j = i; j >= 1; j--){
				  dp[i][0] = min( dp[i][0], dp[j - 1][0] + calc( j, i, 1 ) + 1 );
				  dp[i][0] = min( dp[i][0], dp[j - 1][0] + calc( j, i, 0 ) + 1 );
				  
				  dp[i][0] = min( dp[i][0], dp[j - 1][1] + calc( j, i, 1 ) - (b[j] == '1') + 1 );
				  dp[i][0] = min( dp[i][0], dp[j - 1][1] + calc( j, i, 0 ) - (b[j] == '0') + 1 );
 
				  dp[i][1] = min( dp[i][1], dp[j - 1][1] + calc( j, i, 0 ) + 1 );
 
				  dp[i][1] = min( dp[i][1], dp[j - 1][0] + calc( j, i, 0 ) - (b[i] == '0') + 2 );
				  dp[i][1] = min( dp[i][1], dp[j - 1][1] + max(0, calc( j, i, 0 ) - (b[j] == '0') - (b[i] == '0') ) + 2 );
 
				  dp[i][1] = min( dp[i][1], dp[j - 1][1] + calc( j, i, 1 ) + 1 );
 
				  dp[i][1] = min( dp[i][1], dp[j - 1][0] + calc( j, i, 1 ) -  (b[i] == '1') + 2 );
				  dp[i][1] = min( dp[i][1], dp[j - 1][1] + max(0, calc( j, i, 1 ) - (b[j] == '1') - (b[i] == '1') ) + 2 );
			}
	  }
	  cout << min(dp[n][0], dp[n][1]) << endl;
}
/**
13
0101100101001
1011111000000

13
0001101001101
0101100011011
**/

Compilation message (stderr)

lamp.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...