Submission #977216

#	Time	Username	Problem	Language	Result	Execution time	Memory
977216		happy_node	Lamps (JOI19_lamps)	C++17	100 / 100	387 ms	77960 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

const int MX=2e6+5;
int N;
string A,B;

int dp[MX][8];
vector<pair<int,int>> adj[8];

bool can(int k, char s, char t) {
	if(s=='#') return true;
	assert(t!='#');
	int a=s-'0',b=t-'0';

	if(k==0) {
		return a==b;
	}
	if(k==1) {
		a^=1;
		return a==b;
	}
	if(k==2) {
		a=0;
		a^=1;
		return a==b;
	}
	if(k==3) {
		a^=1;
		a=0;
		return a==b;
	}
	if(k==4) {
		a=1;
		a^=1;
		return a==b;
	}
	if(k==5) {
		a^=1;
		a=1;
		return a==b;
	}
	if(k==6) {
		a=0;
		return a==b;
	}
	if(k==7) {
		a=1;
		return a==b;
	}
	assert(0);
	return 0;
}

void edge(int u, int v, int w) {
	adj[u].push_back({v,w});
}

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	for(int i=0;i<MX;i++) {
		for(int j=0;j<8;j++) {
			dp[i][j]=1e9;
		}
	}

	edge(0,0,0);
	edge(1,1,0);
	edge(2,2,0);
	edge(3,3,0);
	edge(4,4,0);
	edge(5,5,0);
	edge(6,6,0);
	edge(7,7,0);

	edge(0,1,1);
	edge(0,2,2);
	edge(0,3,2);
	edge(0,4,2);
	edge(0,5,2);
	edge(0,6,1);
	edge(0,7,1);

	edge(1,0,0);
	edge(2,0,0);
	edge(3,0,0);
	edge(4,0,0);
	edge(5,0,0);
	edge(6,0,0);
	edge(7,0,0);

	edge(1,2,1);
	edge(1,3,1);
	edge(1,4,1);
	edge(1,5,1);
	edge(2,1,0);
	edge(3,1,0);
	edge(4,1,0);
	edge(5,1,0);

	edge(6,2,1);
	edge(6,3,1);
	edge(2,6,0);
	edge(3,6,0);

	edge(7,4,1);
	edge(7,5,1);
	edge(4,7,0);
	edge(5,7,0);

	cin>>N;

	cin>>A>>B;

	string S="",T="";
	for(int i=0;i<N;i++) {
		S+=A[i];
		S+='#';
	}
	for(int i=0;i<N;i++) {
		T+=B[i];
		T+='#';
	}
	N*=2;

	dp[0][0]=0;

	for(int i=0;i<N;i++) {
		for(int j=0;j<8;j++) {
			for(auto [k,w]:adj[j]) {
				if(can(k,S[i],T[i])) {
					dp[i+1][k]=min(dp[i+1][k],dp[i][j]+w);
				}
			}		
		}
	}

	cout<<dp[N][0]<<'\n';
}

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