oj.uz

Submission #955809

# Submission time Handle Problem Language Result Execution time Memory
955809 2024-03-31T12:42:41 Z hqminhuwu Lamps (JOI19_lamps) C++14
47 / 100
 23 ms 34132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a  -  - > (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int n, dp[N][7];
string a, b;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef hqm
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> a >> b;
    
    a = '0' + a;
    b = '0' + b;

    memset (dp, 63, sizeof dp);
    dp[0][0] = 0;

    // 0 1 2 12 3 13
    
    forr (i, 1, n){
        if (b[i] == '0') {
            dp[i][5] = dp[i - 1][5];
            dp[i][5] = min (dp[i][5], dp[i - 1][0] + 2);
            dp[i][5] = min (dp[i][5], dp[i - 1][1] + 1);
            dp[i][5] = min (dp[i][5], dp[i - 1][4] + 1);
            dp[i][2] = min (dp[i - 1][0] + 1, dp[i - 1][2]);
           
        } else {
            dp[i][3] = dp[i - 1][3];
            dp[i][3] = min (dp[i][3], dp[i - 1][0] + 2);
            dp[i][3] = min (dp[i][3], dp[i - 1][1] + 1);
            dp[i][3] = min (dp[i][3], dp[i - 1][2] + 1);
            dp[i][4] = min (dp[i - 1][0] + 1, dp[i - 1][4]);
        }
 
        if(a[i] != b[i]) {
            dp[i][1] = min (dp[i - 1][1], dp[i - 1][0] + 1);
        } else {
            dp[i][0] = dp[i - 1][0];
        }
        
        dp[i][4] = min (dp[i][4], dp[i][5]);
        dp[i][1] = min (dp[i][1], min (dp[i][3], dp[i][5]));
        dp[i][2] = min (dp[i][2], dp[i][3]);
        dp[i][0] = min (dp[i][0], min (dp[i][1], dp[i][2]));
        dp[i][0] = min (dp[i][0], min (dp[i][3], min(dp[i][4], dp[i][5])));
    }

    cout << dp[n][0];

    return 0;
}
/*



*/

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 2 ms 13916 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 2 ms 13916 KB Output is correct
8 Correct 3 ms 14032 KB Output is correct
9 Correct 3 ms 13912 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 3 ms 13916 KB Output is correct
12 Correct 3 ms 13916 KB Output is correct
13 Correct 2 ms 14056 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 2 ms 13928 KB Output is correct
16 Correct 3 ms 13916 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 3 ms 13916 KB Output is correct
19 Correct 3 ms 13916 KB Output is correct
20 Correct 2 ms 13916 KB Output is correct
21 Correct 4 ms 13916 KB Output is correct
22 Correct 3 ms 13916 KB Output is correct
23 Correct 2 ms 13964 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Correct 3 ms 13916 KB Output is correct
26 Correct 2 ms 13916 KB Output is correct
27 Correct 4 ms 13916 KB Output is correct
28 Correct 2 ms 13916 KB Output is correct
29 Correct 3 ms 13916 KB Output is correct
30 Correct 2 ms 13916 KB Output is correct
31 Correct 2 ms 13916 KB Output is correct
32 Correct 3 ms 14168 KB Output is correct
33 Correct 3 ms 13916 KB Output is correct
34 Correct 3 ms 13916 KB Output is correct

Subtask #2
41.0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 2 ms 13916 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 2 ms 13916 KB Output is correct
8 Correct 3 ms 14032 KB Output is correct
9 Correct 3 ms 13912 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 3 ms 13916 KB Output is correct
12 Correct 3 ms 13916 KB Output is correct
13 Correct 2 ms 14056 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 2 ms 13928 KB Output is correct
16 Correct 3 ms 13916 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 3 ms 13916 KB Output is correct
19 Correct 3 ms 13916 KB Output is correct
20 Correct 2 ms 13916 KB Output is correct
21 Correct 4 ms 13916 KB Output is correct
22 Correct 3 ms 13916 KB Output is correct
23 Correct 2 ms 13964 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Correct 3 ms 13916 KB Output is correct
26 Correct 2 ms 13916 KB Output is correct
27 Correct 4 ms 13916 KB Output is correct
28 Correct 2 ms 13916 KB Output is correct
29 Correct 3 ms 13916 KB Output is correct
30 Correct 2 ms 13916 KB Output is correct
31 Correct 2 ms 13916 KB Output is correct
32 Correct 3 ms 14168 KB Output is correct
33 Correct 3 ms 13916 KB Output is correct
34 Correct 3 ms 13916 KB Output is correct
35 Correct 3 ms 13916 KB Output is correct
36 Correct 3 ms 13916 KB Output is correct
37 Correct 2 ms 13916 KB Output is correct
38 Correct 3 ms 13916 KB Output is correct
39 Correct 3 ms 13912 KB Output is correct
40 Correct 3 ms 13916 KB Output is correct
41 Correct 3 ms 13916 KB Output is correct
42 Correct 5 ms 14172 KB Output is correct
43 Correct 3 ms 13916 KB Output is correct
44 Correct 3 ms 13916 KB Output is correct
45 Correct 3 ms 13916 KB Output is correct
46 Correct 3 ms 14036 KB Output is correct
47 Correct 3 ms 13912 KB Output is correct
48 Correct 3 ms 13916 KB Output is correct
49 Correct 3 ms 13916 KB Output is correct
50 Correct 3 ms 13916 KB Output is correct
51 Correct 3 ms 13916 KB Output is correct
52 Correct 2 ms 13916 KB Output is correct
53 Correct 2 ms 13928 KB Output is correct
54 Correct 2 ms 14032 KB Output is correct
55 Correct 3 ms 13912 KB Output is correct
56 Correct 2 ms 13916 KB Output is correct
57 Correct 2 ms 13916 KB Output is correct
58 Correct 3 ms 13912 KB Output is correct

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13916 KB Output is correct
2 Correct 3 ms 13916 KB Output is correct
3 Correct 3 ms 13916 KB Output is correct
4 Correct 2 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13956 KB Output is correct
7 Runtime error 23 ms 34132 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13912 KB Output is correct
2 Correct 2 ms 13916 KB Output is correct
3 Correct 2 ms 13916 KB Output is correct
4 Correct 3 ms 13916 KB Output is correct
5 Correct 3 ms 13916 KB Output is correct
6 Correct 3 ms 13916 KB Output is correct
7 Correct 2 ms 13916 KB Output is correct
8 Correct 3 ms 14032 KB Output is correct
9 Correct 3 ms 13912 KB Output is correct
10 Correct 3 ms 13916 KB Output is correct
11 Correct 3 ms 13916 KB Output is correct
12 Correct 3 ms 13916 KB Output is correct
13 Correct 2 ms 14056 KB Output is correct
14 Correct 3 ms 13916 KB Output is correct
15 Correct 2 ms 13928 KB Output is correct
16 Correct 3 ms 13916 KB Output is correct
17 Correct 3 ms 13916 KB Output is correct
18 Correct 3 ms 13916 KB Output is correct
19 Correct 3 ms 13916 KB Output is correct
20 Correct 2 ms 13916 KB Output is correct
21 Correct 4 ms 13916 KB Output is correct
22 Correct 3 ms 13916 KB Output is correct
23 Correct 2 ms 13964 KB Output is correct
24 Correct 3 ms 13916 KB Output is correct
25 Correct 3 ms 13916 KB Output is correct
26 Correct 2 ms 13916 KB Output is correct
27 Correct 4 ms 13916 KB Output is correct
28 Correct 2 ms 13916 KB Output is correct
29 Correct 3 ms 13916 KB Output is correct
30 Correct 2 ms 13916 KB Output is correct
31 Correct 2 ms 13916 KB Output is correct
32 Correct 3 ms 14168 KB Output is correct
33 Correct 3 ms 13916 KB Output is correct
34 Correct 3 ms 13916 KB Output is correct
35 Correct 3 ms 13916 KB Output is correct
36 Correct 3 ms 13916 KB Output is correct
37 Correct 2 ms 13916 KB Output is correct
38 Correct 3 ms 13916 KB Output is correct
39 Correct 3 ms 13912 KB Output is correct
40 Correct 3 ms 13916 KB Output is correct
41 Correct 3 ms 13916 KB Output is correct
42 Correct 5 ms 14172 KB Output is correct
43 Correct 3 ms 13916 KB Output is correct
44 Correct 3 ms 13916 KB Output is correct
45 Correct 3 ms 13916 KB Output is correct
46 Correct 3 ms 14036 KB Output is correct
47 Correct 3 ms 13912 KB Output is correct
48 Correct 3 ms 13916 KB Output is correct
49 Correct 3 ms 13916 KB Output is correct
50 Correct 3 ms 13916 KB Output is correct
51 Correct 3 ms 13916 KB Output is correct
52 Correct 2 ms 13916 KB Output is correct
53 Correct 2 ms 13928 KB Output is correct
54 Correct 2 ms 14032 KB Output is correct
55 Correct 3 ms 13912 KB Output is correct
56 Correct 2 ms 13916 KB Output is correct
57 Correct 2 ms 13916 KB Output is correct
58 Correct 3 ms 13912 KB Output is correct
59 Correct 3 ms 13916 KB Output is correct
60 Correct 3 ms 13916 KB Output is correct
61 Correct 3 ms 13916 KB Output is correct
62 Correct 2 ms 13916 KB Output is correct
63 Correct 3 ms 13916 KB Output is correct
64 Correct 3 ms 13956 KB Output is correct
65 Runtime error 23 ms 34132 KB Execution killed with signal 11
66 Halted 0 ms 0 KB -