Submission #102520

#	Time	Username	Problem	Language	Result	Execution time	Memory
102520		Bruteforceman	Lamps (JOI19_lamps)	C++11	100 / 100	419 ms	120340 KiB

lamp

#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;
}

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49