oj.uz

Submission #102130

# Submission time Handle Problem Language Result Execution time Memory
102130 2019-03-22T17:12:21 Z tpoppo Lamps (JOI19_lamps) C++14
0 / 100
 27 ms 23808 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][inv][0] = min(dp[i+1][inv][0],dp[i][inv][z] + (z != 0) );
				if(b[i] == '0') dp[i+1][!inv][0] = min(dp[i+1][!inv][0],dp[i][inv][z] + (inv != 0) + (z != 0) );
 
				if(b[i] == '1') dp[i+1][inv][1] = min(dp[i+1][inv][1],dp[i][inv][z] + (z != 1) );
				if(b[i] == '1') dp[i+1][!inv][1] = min(dp[i+1][!inv][1],dp[i][inv][z]+ (inv != 0) + (z != 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 != 0) );
			}
		}//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

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 23780 KB Output is correct
2 Incorrect 27 ms 23808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 23808 KB Output isn't correct
2 Halted 0 ms 0 KB -