oj.uz

Submission #312638

# Submission time Handle Problem Language Result Execution time Memory
312638 2020-10-13T22:55:25 Z LucaDantas Lamps (JOI19_lamps) C++17
4 / 100
 37 ms 3996 KB 
#include<bits/stdc++.h>
using namespace std;

constexpr int maxn = 1e6+10;

bool mark[maxn];

string a, b;

int dp[3][2], new_dp[3][2];

// 0 -> melhor com fim preto
// 1 -> fim branco
// 2 -> fim sem fazer nd

// segundo item da dp
// 0 -> termina normal
// 1 -> termina reversed

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n; cin >> n;
	cin >> a >> b;
	dp[0][0] = dp[0][1] = dp[1][0] = dp[1][1] = dp[2][1] = n;
	auto check = [](int i, char val) {
		return (b[i] == val && (i==0||b[i-1]!=val));
	};
	auto check2 = [](int i, char val) {
		return (b[i] == val);
	};
	auto check3 = [](int i) {
		return (a[i] != b[i] && (i==0||a[i-1]==b[i-1]));
	};
	for(int i = 0; i < n; i++) {
		new_dp[0][0] = min(dp[0][0],dp[0][1])+check(i, '1');
		new_dp[0][0] = min(new_dp[0][0], min({dp[1][0], dp[1][1], dp[2][0], dp[2][1]}) + 1 + check2(i, '1'));

      	new_dp[0][1] = dp[0][1]+check(i, '1');
		new_dp[0][1] = min(new_dp[0][1], min(dp[1][1], dp[2][1]) + 1 + check2(i, '1'));
		
      	new_dp[1][0] = min(dp[1][0],dp[1][1])+check(i, '0');
		new_dp[1][0] = min(new_dp[1][0], min({dp[0][0], dp[0][1], dp[2][0], dp[2][1]}) + 1 + check2(i, '0'));

		new_dp[1][1] = dp[1][1]+check(i, '0');
		new_dp[1][1] = min(new_dp[1][1], min(dp[0][1], dp[2][1]) + 1 + check2(i, '0'));

		if(a[i] != b[i])
			new_dp[2][0] = n; // inf
		else new_dp[2][0] = min({dp[0][0], dp[1][0], dp[2][0], dp[0][1], dp[1][1], dp[2][1]});

		if(a[i] == b[i])
			new_dp[2][1] = n; // inf
		else new_dp[2][1] = min({dp[0][0]+1, dp[1][0]+1, dp[2][0]+1, dp[0][1], dp[1][1], dp[2][1]});

		for(int x = 0; x < 3; x++) for(int y = 0; y < 2; y++) swap(new_dp[x][y], dp[x][y]);
	}
	printf("%d\n", min({dp[0][0], dp[1][0], dp[2][0], dp[0][1], dp[1][1], dp[2][1]}));
}

Compilation message

lamp.cpp: In function 'int main()':
lamp.cpp:31:7: warning: variable 'check3' set but not used [-Wunused-but-set-variable]
   31 |  auto check3 = [](int i) {
      |       ^~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Incorrect 1 ms 384 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Incorrect 1 ms 384 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 32 ms 3868 KB Output is correct
8 Correct 35 ms 3996 KB Output is correct
9 Correct 37 ms 3868 KB Output is correct
10 Correct 34 ms 3868 KB Output is correct
11 Correct 35 ms 3868 KB Output is correct
12 Correct 35 ms 3996 KB Output is correct
13 Correct 35 ms 3868 KB Output is correct
14 Correct 35 ms 3996 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 0 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Incorrect 1 ms 384 KB Output isn't correct
27 Halted 0 ms 0 KB -