Submission #104559

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
104559	2019-04-08 03:32:49	minhtung0404	Lamps (JOI19_lamps)	C++17	100 / 100	112 ms	27932 KiB

lamp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
const int N = 1e6 + 5;
const int inf = 1e9 + 7;
using namespace std;
string s, x;
int n, dp[N][3][2], ans = inf;
char cal(char c, int i, int j){
    if (i != 2) c = i + '0';
    if (j) c = '1' + '0' - c;
    return c;
}
void up(int&a, int b){
    if (a > b) a = b;
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> s >> x; s = '.' + s; x = '.' + x;
    for (int i = 0; i < N; i++) for (int j = 0; j < 3; j++) for (int k = 0; k < 2; k++) dp[i][j][k] = inf;
    dp[0][2][0] = 0;
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < 3; j++){
            for (int k = 0; k < 2; k++){
                if (cal(s[i], 0, k) == x[i]) up(dp[i][0][k], dp[i-1][j][k] + (j != 0));
                if (cal(s[i], 1, k) == x[i]) up(dp[i][1][k], dp[i-1][j][k] + (j != 1));
                if (cal(s[i], 2, k) == x[i]) up(dp[i][2][k], dp[i-1][j][k]);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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