oj.uz

답안 #104997

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
104997 2019-04-10T05:22:29 Z antimirage Lamps (JOI19_lamps) C++14
0 / 100
 32 ms 16248 KB 
# include <bits/stdc++.h>
 
using namespace std;
 
const int N = 1e6 + 5;
 
int n, dp[N][2];
 
string a, b;
 
struct st{
	int must, val;
};

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

void push (int i, int j, int v, int tl, int tr)
{
	if (i == -1)
		t11[v].val += t11[v].must;
	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;
		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;
		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 >> a >> b;
 
	  a = ' ' + a;
	  b = ' ' + b;
	  
	  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
**/

Compilation message

lamp.cpp:95:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 16248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 16248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 16120 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 16248 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -