Submission #102520

#TimeUsernameProblemLanguageResultExecution timeMemory
102520BruteforcemanLamps (JOI19_lamps)C++11
100 / 100
419 ms120340 KiB
#include "bits/stdc++.h"
using namespace std;
string s, t;
int n;
const int inf = 1e9;

int mem[2][3][1000010];

int dp(int cur, int xr, int col) {
	if(cur == n) return 0;
	int &ans = mem[xr][col][cur];
	if(ans != -1) return ans;
	ans = inf;
	for(int i = 0; i < 2; i++) {
		for(int j = 0; j < 3; j++) {
			int cost = 0;
			if(xr != i && i > 0) ++cost;
			if(col != j && j > 0) ++cost;
			int c = (j > 0) ? (j - 1) : (t[cur] - '0');
			c ^= i;
			if(c == (s[cur] - '0')) {
				ans = min(ans, dp(cur + 1, i, j) + cost);
			} 
		}
	}
	return ans;
}

int main(int argc, char const *argv[])
{
	memset(mem, -1, sizeof mem);
	cin >> n >> t >> s;
	cout << dp(0, 0, 0) << endl;
	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...