oj.uz

Submission #792531

# Submission time Handle Problem Language Result Execution time Memory
792531 2023-07-25T06:29:37 Z vjudge1 Lamps (JOI19_lamps) C++17
0 / 100
 89 ms 135112 KB 
#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

const int N = 2022;

string a, b;
int dp[N][N][4];

// 0 don't touched
// 1 turn off all
// 2 turn on  all
// 3 toggle   all

int change(int pr, int cr) {
    if(!cr) {
        return pr;
    } 
    if(cr < 3) {
        return cr;
    }
    if(!pr) {
        return cr;
    } 
    if(pr < 3) {
        return 3 - pr;
    }
    return 0;
}

int recur(int l, int r, int sts) {
    int &ans = dp[l][r][sts];
    if(ans != -1) {
        return ans;
    }
    if(l + 1 == r) {
        if(sts == 0) {
            return ans = (a[l] != b[l]);
        } 
        if(sts == 1) {
            return ans = ('0' != b[l]);
        } 
        if(sts == 2) {
            return ans = ('1' != b[l]);
        }
        return ans = (a[l] == b[l]);
    }
    ans = r - l;
    for(int m = l + 1; m < r; ++ m) {
        int ansl = recur(l, m, sts);
        for(int nwsts = 1; nwsts < 4; ++ nwsts) {
            ansl = min(ansl, recur(l, m, change(sts, nwsts)) + 1);
        }
        int ansr = recur(m, r, sts);
        for(int nwsts = 1; nwsts < 4; ++ nwsts) {
            ansr = min(ansr, recur(m, r, change(sts, nwsts)) + 1);
        }
        ans = min(ans, ansl + ansr);
    }
    return ans;
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    memset(dp, -1, sizeof dp);
    
    int n;
    cin >> n >> a >> b;
    cout << min( {
    recur(0, n, 0),
    recur(0, n, 1) + 1,
    recur(0, n, 2) + 1,
    recur(0, n, 3) + 1} );
}

Compilation message

lamp.cpp:70:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   70 | main() {
      | ^~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 64312 KB Output is correct
2 Correct 25 ms 64212 KB Output is correct
3 Correct 23 ms 64276 KB Output is correct
4 Correct 22 ms 64276 KB Output is correct
5 Correct 32 ms 64232 KB Output is correct
6 Correct 26 ms 64304 KB Output is correct
7 Correct 25 ms 64212 KB Output is correct
8 Correct 25 ms 64216 KB Output is correct
9 Correct 23 ms 64212 KB Output is correct
10 Correct 24 ms 64264 KB Output is correct
11 Correct 25 ms 64228 KB Output is correct
12 Correct 23 ms 64212 KB Output is correct
13 Correct 23 ms 64212 KB Output is correct
14 Correct 24 ms 64340 KB Output is correct
15 Correct 28 ms 64380 KB Output is correct
16 Correct 22 ms 64288 KB Output is correct
17 Correct 23 ms 64316 KB Output is correct
18 Correct 29 ms 64272 KB Output is correct
19 Correct 23 ms 64252 KB Output is correct
20 Correct 24 ms 64312 KB Output is correct
21 Correct 26 ms 64204 KB Output is correct
22 Correct 24 ms 64228 KB Output is correct
23 Correct 26 ms 64304 KB Output is correct
24 Correct 23 ms 64292 KB Output is correct
25 Correct 23 ms 64212 KB Output is correct
26 Incorrect 25 ms 64212 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 64312 KB Output is correct
2 Correct 25 ms 64212 KB Output is correct
3 Correct 23 ms 64276 KB Output is correct
4 Correct 22 ms 64276 KB Output is correct
5 Correct 32 ms 64232 KB Output is correct
6 Correct 26 ms 64304 KB Output is correct
7 Correct 25 ms 64212 KB Output is correct
8 Correct 25 ms 64216 KB Output is correct
9 Correct 23 ms 64212 KB Output is correct
10 Correct 24 ms 64264 KB Output is correct
11 Correct 25 ms 64228 KB Output is correct
12 Correct 23 ms 64212 KB Output is correct
13 Correct 23 ms 64212 KB Output is correct
14 Correct 24 ms 64340 KB Output is correct
15 Correct 28 ms 64380 KB Output is correct
16 Correct 22 ms 64288 KB Output is correct
17 Correct 23 ms 64316 KB Output is correct
18 Correct 29 ms 64272 KB Output is correct
19 Correct 23 ms 64252 KB Output is correct
20 Correct 24 ms 64312 KB Output is correct
21 Correct 26 ms 64204 KB Output is correct
22 Correct 24 ms 64228 KB Output is correct
23 Correct 26 ms 64304 KB Output is correct
24 Correct 23 ms 64292 KB Output is correct
25 Correct 23 ms 64212 KB Output is correct
26 Incorrect 25 ms 64212 KB Output isn't correct
27 Halted 0 ms 0 KB -

Subtask #3
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 64332 KB Output is correct
2 Correct 24 ms 64328 KB Output is correct
3 Correct 26 ms 64280 KB Output is correct
4 Correct 24 ms 64292 KB Output is correct
5 Correct 23 ms 64340 KB Output is correct
6 Correct 28 ms 64312 KB Output is correct
7 Runtime error 89 ms 135112 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 23 ms 64312 KB Output is correct
2 Correct 25 ms 64212 KB Output is correct
3 Correct 23 ms 64276 KB Output is correct
4 Correct 22 ms 64276 KB Output is correct
5 Correct 32 ms 64232 KB Output is correct
6 Correct 26 ms 64304 KB Output is correct
7 Correct 25 ms 64212 KB Output is correct
8 Correct 25 ms 64216 KB Output is correct
9 Correct 23 ms 64212 KB Output is correct
10 Correct 24 ms 64264 KB Output is correct
11 Correct 25 ms 64228 KB Output is correct
12 Correct 23 ms 64212 KB Output is correct
13 Correct 23 ms 64212 KB Output is correct
14 Correct 24 ms 64340 KB Output is correct
15 Correct 28 ms 64380 KB Output is correct
16 Correct 22 ms 64288 KB Output is correct
17 Correct 23 ms 64316 KB Output is correct
18 Correct 29 ms 64272 KB Output is correct
19 Correct 23 ms 64252 KB Output is correct
20 Correct 24 ms 64312 KB Output is correct
21 Correct 26 ms 64204 KB Output is correct
22 Correct 24 ms 64228 KB Output is correct
23 Correct 26 ms 64304 KB Output is correct
24 Correct 23 ms 64292 KB Output is correct
25 Correct 23 ms 64212 KB Output is correct
26 Incorrect 25 ms 64212 KB Output isn't correct
27 Halted 0 ms 0 KB -