Submission #1005376

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005376		AdamGS	Lamps (JOI19_lamps)	C++17	10 / 100	317 ms	64952 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e6+7, INF=1e9+7;
int dp[LIM][4][4];
int rob(int x, int k) {
	if(k==0) return 0;
	if(k==1) return 1;
	if(k==2) return x^1;
	return x;
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n;
	string s, t;
	cin >> n >> s >> t;
	rep(i, 4) rep(j, 4) dp[0][i][j]=INF;
	dp[0][3][3]=0;
	rep(i, n) {
		rep(a, 4) rep(b, 4) dp[i+1][a][b]=INF;
		rep(a, 4) rep(b, 4) {
			if(a==3 && b!=3) continue;
			dp[i+1][a][b]=min(dp[i+1][a][b], dp[i][a][b]);
			dp[i+1][3][3]=min(dp[i+1][3][3], dp[i][a][b]);
			dp[i+1][a][3]=min(dp[i+1][a][3], dp[i][a][b]);
			dp[i+1][b][3]=min(dp[i+1][b][3], dp[i][a][b]);
			rep(c, 3) {
				dp[i+1][a][c]=min(dp[i+1][a][c], dp[i][a][b]+1);
				dp[i+1][b][c]=min(dp[i+1][b][c], dp[i][a][b]+1);
				dp[i+1][c][3]=min(dp[i+1][c][3], dp[i][a][b]+1);
				rep(d, 3) dp[i+1][c][d]=min(dp[i+1][c][d], dp[i][a][b]+2);
			}
		}
		rep(a, 4) rep(b, 4) {
			if(a==3 && b!=3) {
				dp[i+1][a][b]=INF;
				continue;
			}
			int p=s[i]-'0';
			p=rob(p, a);
			p=rob(p, b);
			if(p!=t[i]-'0') dp[i+1][a][b]=INF;
		}
	}
	int ans=INF;
	rep(a, 4) rep(b, 4) ans=min(ans, dp[n][a][b]);
	cout << ans << '\n';
}

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