Submission #1005389

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005389		AdamGS	Lamps (JOI19_lamps)	C++17	6 / 100	5 ms	5800 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=2e3+7, INF=1e9+7;
int dp[LIM][4][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, n+1) rep(a, 4) rep(b, 4) rep(c, 4) dp[i][a][b][c]=INF;
	dp[0][3][3][3]=0;
	rep(i, n) {
		rep(a, 4) rep(b, 4) rep(c, 4) {
			dp[i+1][a][b][c]=min(dp[i+1][a][b][c], dp[i][a][b][c]);
			dp[i+1][a][b][3]=min(dp[i+1][a][b][3], dp[i][a][b][c]);
			dp[i+1][a][c][3]=min(dp[i+1][a][c][3], dp[i][a][b][c]);
			dp[i+1][b][c][3]=min(dp[i+1][b][c][3], dp[i][a][b][c]);
			dp[i+1][a][3][3]=min(dp[i+1][a][3][3], dp[i][a][b][c]);
			dp[i+1][b][3][3]=min(dp[i+1][b][3][3], dp[i][a][b][c]);
			dp[i+1][c][3][3]=min(dp[i+1][c][3][3], dp[i][a][b][c]);
			dp[i+1][3][3][3]=min(dp[i+1][3][3][3], dp[i][a][b][c]);
		}
		rep(a, 4) dp[i+1][a][3][3]=min(dp[i+1][a][3][3], dp[i+1][3][3][3]+1);
		rep(a, 4) rep(b, 4) dp[i+1][a][b][3]=min(dp[i+1][a][b][3], dp[i+1][a][3][3]+1);
		rep(a, 4) rep(b, 4) rep(c, 4) dp[i+1][a][b][c]=min(dp[i+1][a][b][c], dp[i+1][a][b][3]+1);
		rep(a, 4) rep(b, 4) rep(c, 4) {
			if((a==3 && b!=3) || (a==3 && c!=3) || (b==3 && c!=3)) {
				dp[i+1][a][b][c]=INF;
				continue;
			}
			int p=s[i]-'0';
			p=rob(p, a);
			p=rob(p, b);
			p=rob(p, c);
			if(p!=t[i]-'0') {
				dp[i+1][a][b][c]=INF;
				continue;
			}
		}
	}
	int ans=INF;
	rep(a, 4) rep(b, 4) rep(c, 4) ans=min(ans, dp[n][a][b][c]);
	cout << ans << '\n';
}

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