oj.uz

답안 #102131

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
102131 2019-03-22T17:13:07 Z tpoppo Lamps (JOI19_lamps) C++14
4 / 100
 67 ms 25972 KB 
#include <bits/stdc++.h>
 
using namespace std;
const int MAXN = 1e6 + 100;
int n;
string a,b;
 
int dp[MAXN][2][3];
 
int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);
	cin >> n;
	cin >> a >> b;
	memset(dp,0x66,sizeof(dp));
	
	
	for(int inv=0;inv<2;inv++) {
		for(int z=0;z<3;z++) {
			dp[0][inv][z] = (inv == 1) + (z != 2);
		}
	}
	
	for(int i=0;i<=n;i++) {
		for(int inv=0;inv<2;inv++) {
			for(int z=0;z<3;z++) {
 
				//cout<<setw(10)<<dp[i][inv][z]<<" ";
				if(b[i] == '0') {
					dp[i+1][0][0] = min(dp[i+1][0][0],dp[i][inv][z] + (z != 0) );
					dp[i+1][1][0] = min(dp[i+1][1][0],dp[i][inv][z] + (z != 0) + (inv != 1) );
				}
 
				if(b[i] == '1'){
					dp[i+1][0][1] = min(dp[i+1][0][1],dp[i][inv][z] + (z != 1) );
					dp[i+1][1][1] = min(dp[i+1][1][1],dp[i][inv][z] + (z != 1)  + (inv != 1) );
				
				}
				if(b[i] == a[i]) dp[i+1][0][2] = min(dp[i+1][0][2],dp[i][inv][z]  );
				else dp[i+1][1][2] = min(dp[i+1][1][2],dp[i][inv][z] + (inv != 1) );
			}
		}//cout<<endl;
	}
	int rs = 1e9;
	for(int inv=0;inv<2;inv++) {
		for(int z=0;z<3;z++) {
			rs = min(rs,dp[n][inv][z]);
		}
	}
 
	cout<<rs<<'\n';
 
	return 0;
}

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 26 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23800 KB Output is correct
6 Correct 25 ms 23808 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 25 ms 23844 KB Output is correct
10 Correct 22 ms 23780 KB Output is correct
11 Correct 23 ms 23808 KB Output is correct
12 Correct 21 ms 23808 KB Output is correct
13 Correct 22 ms 23808 KB Output is correct
14 Correct 22 ms 23800 KB Output is correct
15 Correct 24 ms 23808 KB Output is correct
16 Incorrect 21 ms 23800 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 26 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23800 KB Output is correct
6 Correct 25 ms 23808 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 25 ms 23844 KB Output is correct
10 Correct 22 ms 23780 KB Output is correct
11 Correct 23 ms 23808 KB Output is correct
12 Correct 21 ms 23808 KB Output is correct
13 Correct 22 ms 23808 KB Output is correct
14 Correct 22 ms 23800 KB Output is correct
15 Correct 24 ms 23808 KB Output is correct
16 Incorrect 21 ms 23800 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 23852 KB Output is correct
2 Correct 22 ms 23808 KB Output is correct
3 Correct 24 ms 23808 KB Output is correct
4 Correct 21 ms 23856 KB Output is correct
5 Correct 21 ms 23808 KB Output is correct
6 Correct 21 ms 23792 KB Output is correct
7 Correct 52 ms 25972 KB Output is correct
8 Correct 46 ms 25884 KB Output is correct
9 Correct 49 ms 25940 KB Output is correct
10 Correct 55 ms 25940 KB Output is correct
11 Correct 51 ms 25940 KB Output is correct
12 Correct 59 ms 25940 KB Output is correct
13 Correct 67 ms 25904 KB Output is correct
14 Correct 47 ms 25940 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Correct 23 ms 23808 KB Output is correct
2 Correct 26 ms 23808 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 22 ms 23808 KB Output is correct
5 Correct 22 ms 23800 KB Output is correct
6 Correct 25 ms 23808 KB Output is correct
7 Correct 23 ms 23800 KB Output is correct
8 Correct 22 ms 23808 KB Output is correct
9 Correct 25 ms 23844 KB Output is correct
10 Correct 22 ms 23780 KB Output is correct
11 Correct 23 ms 23808 KB Output is correct
12 Correct 21 ms 23808 KB Output is correct
13 Correct 22 ms 23808 KB Output is correct
14 Correct 22 ms 23800 KB Output is correct
15 Correct 24 ms 23808 KB Output is correct
16 Incorrect 21 ms 23800 KB Output isn't correct
17 Halted 0 ms 0 KB -