제출 #239963

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
239963		cfalas	Lamps (JOI19_lamps)	C++14	100 / 100	211 ms	90728 KiB

lamp

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID (l+r)/2
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6

string a,b;

// operations:
// 0 none
// 1 toggle
// 2 set 0
// 3 toggle + set 0
// 4 set 1
// 5 toggle + set 1

#define Q(w, cost) dp[n][x] = min(dp[n][x], rec(n-1, w)+cost);

int dp[1004000][6];
int rec(int n, int x){
	if(n<0) return 0;
	if(dp[n][x]!=-MOD) return dp[n][x];

	dp[n][x] = MOD;


	if(b[n]=='1'){
		if(x==2 || x==3){		Q(2,0);}
		else{					Q(2,1);}
		
		if(x==5){				Q(5,0);}
		else if(x==1 || x==4){	Q(5,1);}
		else{					Q(5,2);}
	}
	else if(b[n]=='0'){
		if(x==4 || x==5){		Q(4,0);}
		else{					Q(4,1);}
		
		if(x==3){				Q(3,0);}
		else if(x==1 || x==2){	Q(3,1);}
		else{					Q(3,2);}

	}
	if(a[n]==b[n]){				Q(0, 0);}
	else{
		if(x%2==1){				Q(1, 0);}
		else{					Q(1, 1);}
	}

	return dp[n][x];
}

int main(){
	int n;
	cin>>n;
	cin>>a>>b;
	for(int i=0;i<n;i++){
		for(int j=0;j<6;j++) dp[i][j] = -MOD;
	}
	cout<<rec(n-1, 0);


}

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