제출 #104999

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104999		antimirage	Lamps (JOI19_lamps)	C++14	47 / 100	1080 ms	22648 KiB

lamp

# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
 
int n, dp[N][2];
 
char a[N], b[N];
 
struct st{
	int must, val;
};

st t[3][3][N * 4], t11[N * 4], t10[N * 4];

inline int min(int a, int b)
{
	return a < b ? a : b;
}

void push (int i, int j, int v, int tl, int tr)
{
	if (i == -1)
		t11[v].val += t11[v].must;
	else if (j == -1)
		t10[v].val += t10[v].must;
	else
		t[i][j][v].val += t[i][j][v].must;
	
	if (tl != tr){

		if (i == -1)
			t11[v + v].must += t11[v].must,
			t11[v + v + 1].must += t11[v].must;
		else if (j == -1)
			t10[v + v].must += t10[v].must,
			t10[v + v + 1].must += t10[v].must;
		else		
			t[i][j][v + v].must += t[i][j][v].must,
			t[i][j][v + v + 1].must += t[i][j][v].must;
	}
	if (i == -1)
		t11[v].must = 0;
	else if (j == -1)
		t10[v].must = 0;
	else 
		t[i][j][v].must = 0;
}

void update (int i, int j, int l, int r, int val, int v = 1, int tl = 0, int tr = n)
{
	push(i, j, v, tl, tr);
	if (l > tr || tl > r) return;
	
	if (l <= tl && tr <= r){
		
		if (i == -1)
			t11[v].must += val;
		else if (j == -1)
			t10[v].must += val;
		else
			t[i][j][v].must += val;
		push(i, j, v, tl, tr);
		return;
	}
	int tm = (tl + tr) >> 1;
	
	update(i, j, l, r, val, v + v, tl, tm);
	update(i, j, l, r, val, v + v + 1, tm + 1, tr);
	
	if (i == -1)
		t11[v].val = min( t11[v + v].val, t11[v + v + 1].val );
	else  if (j == -1)
		t10[v].val = min( t10[v + v].val, t10[v + v + 1].val );
	else
		t[i][j][v].val = min( t[i][j][v + v].val, t[i][j][v + v + 1].val );
}
int get (int i, int j, int l, int r, int v = 1, int tl = 0, int tr = n)
{
	push(i, j, v, tl, tr);
	
	if (l > tr || tl > r)
		return 1e9 + 7;
		
	if (l <= tl && tr <= r){
		
		if (i == -1)
			return t11[v].val;
		if (j == -1)
			return t10[v].val;
			
		return t[i][j][v].val;
	}
	int tm = (tl + tr) >> 1;
	
	return min( get(i, j, l, r, v + v, tl, tm), get(i, j, l, r, v + v + 1, tm + 1, tr) );
}

main(){
 
	  memset( dp, 0x3f3f3f3f, sizeof(dp) );
 
	  cin >> n;
	  scanf("\n%s", a + 1);
	  scanf("\n%s", b + 1);

	  dp[0][0] = 0;
	  update( 1, 0, 0, 0, dp[0][1] );
	  update( 1, 1, 0, 0, dp[0][1] );
	  update( -1, 0, 0, 0, dp[0][1] );
	  update( 0, -1, 0, 0, dp[0][1] );
 
		for (int i = 1; i <= n; i++){
		  
			if (b[i] != b[i - 1] && i - 2 >= 0){
				update(0, b[i] - 48, 0, i - 2, +1);
				update(1, b[i] - 48, 0, i - 2, +1);
				
				if (b[i] == '1')
					update(-1, 0, 0, i - 2, +1);
				if (b[i] == '0')
					update(0, -1, 0, i - 2, +1);
			}
			if (b[i] == '1')
				update(-1, 0, i - 1, i - 1, -1);
			if (b[i] == '0')
				update(0, -1, i - 1, i - 1, -1);
			
			if (b[i] == '1')
				update(-1, 0, i - 1, i - 1, +1);
			if (b[i] == '0')
				update(0, -1, i - 1, i - 1, +1);
				
			update(0, b[i] - 48, i - 1, i - 1, +1);
			update(1, b[i] - 48, i - 1, i - 1, +1);

			if (a[i] == b[i])
				  dp[i][0] = min( dp[i - 1][1], dp[i - 1][0] );

			if (a[i] != b[i])
				  dp[i][1] = min( dp[i - 1][1], dp[i - 1][0] + 1);
				  
				 
			dp[i][0] = min( dp[i][0], get(0, 1, 0, i - 1) + 1 );
			dp[i][0] = min( dp[i][0], get(0, 0, 0, i - 1) + 1 );
			
			dp[i][1] = min( dp[i][1], get(1, 0, 0, i - 1) + 1 );
			dp[i][1] = min( dp[i][1], get(1, 1, 0, i - 1) + 1 );
			
			dp[i][1] = min( dp[i][1], get(0, 0, 0, i - 1) - (b[i] == '0') + 2 );
			dp[i][1] = min( dp[i][1], get(0, 1, 0, i - 1) - (b[i] == '1') + 2 );

			dp[i][0] = min( dp[i][0], get(-1, 0, 0, i - 1) + 1 );
			dp[i][0] = min( dp[i][0], get(0, -1, 0, i - 1) + 1 );

			dp[i][1] = min( dp[i][1], get(0, -1, 0, i - 1) - (b[i] == '0') + 2 );
			dp[i][1] = min( dp[i][1], get(-1, 0, 0, i - 1) - (b[i] == '1') + 2 );
		
			update( 0, 0, i, i, dp[i][0] );
			update( 0, 1, i, i, dp[i][0] );
			
			update( 1, 0, i, i, dp[i][1] );
			update( 1, 1, i, i, dp[i][1] );
		
			update( -1, 0, i, i, dp[i][1] );
			update( 0, -1, i, i, dp[i][1] );
		}
		cout << min( dp[n][0], dp[n][1] ) << endl;
}
/**
13
0101100101001
1011111000000

13
0001101001101
0101100011011

8
11011100
01101001
**/

컴파일 시 표준 에러 (stderr) 메시지

lamp.cpp:100:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
lamp.cpp: In function 'int main()':
lamp.cpp:105:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("\n%s", a + 1);
    ~~~~~^~~~~~~~~~~~~~~
lamp.cpp:106:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("\n%s", b + 1);
    ~~~~~^~~~~~~~~~~~~~~

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