제출 #1306299

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1306299		peteza	Lamps (JOI19_lamps)	C++20	100 / 100	84 ms	25028 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
 
int n;
string a, b, ch[3];
int dp[1000005][5];
 
//0 can go to 1(+1) or 3(+1) or 0
//1 can go 2(+1) or 0
//2 can go 1 or 0
//3 can go 4(+1) or 0
//4 can go 3 or 0
 
int no[5];
int cst[5][5];
//int cst[3][3] = {{2000000, 2000000, 2000000}, {2000000, 2000000, 2000000}, {2000000, 2000000, 2000000}};
 
int main() {
	// your code goes here
	cin >> n >> a >> b;
	ch[0] = ch[1] = ch[2] = b;
	for(int i=0;i<n;i++) {
		ch[0][i] = llabs(a[i] - b[i]) + '0';
		ch[2][i] = (b[i] == '1' ? '0' : '1');
	}
	no[0] = 0; no[1] = no[2] = 1; no[3] = no[4] = 2;
	for(int i=0;i<5;i++) for(int j=0;j<5;j++) cst[i][j] = 2000000;
	cst[0][1] = 1; cst[0][3] = 1; cst[0][0] = 0;
	cst[1][2] = 1; cst[1][0] = 0; cst[1][1] = 0;
	cst[2][1] = 0; cst[2][0] = 0; cst[2][2] = 0;
	cst[3][4] = 1; cst[3][0] = 0; cst[3][3] = 0;
	cst[4][3] = 0; cst[4][0] = 0; cst[4][4] = 0;
	for(int j=0;j<3;j++) ch[j].insert(ch[j].begin(), '0');
 
	for(int i=0;i<=n;i++) {
		for(int j=0;j<5;j++) {
			dp[i][j] = 2000000;
		}
	}
	dp[0][0] = 0;
	for(int i=0;i<n;i++) {
		for(int nn=0;nn<5;nn++) {
			for(int nx=0;nx<5;nx++) {
				dp[i+1][nx] = min(dp[i+1][nx], dp[i][nn] + cst[nn][nx] + (ch[no[nn]][i] == '0' && '1' == ch[no[nx]][i+1]));
			}
		}
	}
	int ans = 2000000;
	//for(int i=0;i<=n;i++) {
	for(int j=0;j<5;j++) {
		//cout << dp[i][j] << ' ';
		ans = min(ans, dp[n][j]);
	}
		//cout << '\n';}
	cout << ans;
	return 0;
}

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