Submission #318227

#	Time	Username	Problem	Language	Result	Execution time	Memory
318227		FlashGamezzz	Lamps (JOI19_lamps)	C++17	100 / 100	885 ms	4532 KiB

lamp

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <string>

using namespace std;

string a, b, vals[16] = {"", "2", "0", "1", "01", "02", "10", "12", "20", "21", "012", "021", "102", "120", "201", "210"};
int n, dp[16] = {0, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3} , sw[16], num[16] = {0, 0, 48, 49, 49, 49, 48, 48, 48, 49, 48, 49, 49, 48, 49, 48};

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cin >> n >> a >> b;
	for (int i = 0; i < n; i++){
		sw[0] = 1000000000; sw[1] = 1000000000;
		if (a[i] == b[i]){
			sw[0] = dp[0];
			for (int j = 1; j < 16; j++){
				sw[0] = min(sw[0], dp[j]);
			}
		} else {
			sw[1] = dp[0]+1;
			for (int j = 1; j < 16; j++){
				int sub = 0;
				for (char a : vals[j]){
					if (a == '2'){
						sub++; break;
					}
				}
				sw[1] = min(sw[1], dp[j]+1-sub);
			}
		}
		for (int j = 2; j < 16; j++){
			if (num[j] == b[i]){
				int vs = vals[j].size();
				sw[j] = dp[0]+vs;
				for (int k = 1; k < 16; k++){
					int count = 0, num = 0, ns = vals[k].size();
					for (char a : vals[j]){
						for (int l = count; l < ns; l++){
							if (vals[k][l] == a){
								count = l+1; num++; break;
							}
						}
					}
					sw[j] = min(sw[j], dp[k]+vs-num);
				}
			} else {
				sw[j] = 1000000000;
			}
		}
		swap(sw, dp);
	}
	int ans = 1000000000;
	for (int i = 0; i < 16; i++){
		ans = min(ans, dp[i]);
	}
	cout << ans << endl;
}

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