oj.uz

Submission #1014346

# Submission time Handle Problem Language Result Execution time Memory
1014346 2024-07-04T17:24:52 Z anHiep Lamps (JOI19_lamps) C++14
4 / 100
 84 ms 68012 KB 
#include<bits/stdc++.h>
#ifdef LOCAL
#include "D:\debug.h"
#else
#define cebug(...) "Orz_chUoNgnn_khanhtb"
#endif

using namespace std;

#define int long long
#define fi first 
#define se second
#define pb push_back
#define ll long long
#define ii pair<int, int>
#define vi vector<int> 
#define vll vector<ll>
#define vii vector<ii>
#define cd complex<double>
const ll mod = 1e9 + 7;
const ll INF = 1e18L + 5;
const double PI = acos(-1);
const int block = 320;
const int N = 1e6;
int tc, tt = 1;

int n;
string a, b;
int dp[N + 5][4][2];
bool ck(int i, int t) {
    if(a[i] == b[i] && t == 0) return true;
    if(b[i] == '0' && t == 1) return true;
    if(b[i] == '1' && t == 2) return true;
    if(a[i] != b[i] && t == 3) return true;
    return false;
}
void solve() {
    cin>>n>>a>>b;
    for(int i=0; i<=n; i++)
        for(int j=0; j<4; j++)
            for(int k=0; k<2; k++)
                dp[i][j][k] = INF;
    a = ']' + a;
    b = '[' + b;
    dp[0][0][0] = 0;
    for(int i=1; i<=n; i++)
        for(int j=0; j<4; j++)
            for(int k=0; k<2; k++) 
                if((k == 0 && ck(i, j)) || (k == 1 && !ck(i, j))){
                    dp[i][j][k] = dp[i - 1][j][k];
                    if(k == 1)
                        dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][1 ^ k]);
                    for(int h=0; h<4; h++)
                        if(h != j) {
                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][h][k] + (j != 0));
                            if(k == 1) dp[i][j][k] = min(dp[i][j][k], dp[i - 1][h][1 ^ k] + 1);
                        }
                }
    int ans = INF;
    for(int i=0; i<4; i++) {
        ans = min(ans, dp[n][i][0]);
        ans = min(ans, dp[n][i][1] + 1);
    }
    cout<<ans;
}
signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    // freopen(".INP", "r", stdin);
    // freopen(".OUT", "w", stdout);
    for(int tc=1; tc<=tt; tc++) solve();
    // cerr<<"\nTime elapsed: "<<1000.0*clock()/CLOCKS_PER_SEC<<" ms.\n";
    return 0;
}

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #2
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #3
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 67 ms 67996 KB Output is correct
8 Correct 70 ms 67912 KB Output is correct
9 Correct 66 ms 67936 KB Output is correct
10 Correct 63 ms 68004 KB Output is correct
11 Correct 84 ms 68004 KB Output is correct
12 Correct 67 ms 68012 KB Output is correct
13 Correct 63 ms 67904 KB Output is correct
14 Correct 61 ms 68004 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 348 KB Output isn't correct
14 Halted 0 ms 0 KB -