Submission #340636

#	Time	Username	Problem	Language	Result	Execution time	Memory
340636		wwdd	Lamps (JOI19_lamps)	C++14	100 / 100	97 ms	51516 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MN = 1001000;
const ll INFL = 1e18;
ll dp[3][2][MN];
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	ll n;
	cin >> n;
	string s,t;
	cin >> s >> t;
	for(int i=0;i<3;i++) {
		for(int j=0;j<2;j++) {
			for(int e=0;e<MN;e++) {
				dp[i][j][e] = INFL;
			}
		}
	}
	dp[2][0][0] = 0;
	for(int i=0;i<n;i++) {
		int sc = s[i]-'0';
		int tc = t[i]-'0';
		for(int sv=0;sv<3;sv++) {
			for(int st=0;st<2;st++) {
				for(int to=0;to<2;to++) {
					dp[tc^to][to][i+1] = min(dp[tc^to][to][i+1],dp[sv][st][i] + (sv != (tc^to)) + (to > st));
					if(sc == tc) {
						dp[2][0][i+1] = min(dp[2][0][i+1], dp[sv][st][i]);
					} else {
						dp[2][1][i+1] = min(dp[2][1][i+1], dp[sv][st][i] + (st != 1));
					}
				}
			}
		}
	}
	ll res = INFL;
	for(int i=0;i<3;i++) {
		for(int j=0;j<2;j++) {
			res = min(res,dp[i][j][n]);
		}
	}
	cout << res << '\n';
}

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