oj.uz

Submission #1014335

# Submission time Handle Problem Language Result Execution time Memory
1014335 2024-07-04T16:52:50 Z anHiep Lamps (JOI19_lamps) C++14
4 / 100
 79 ms 68240 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] = 1e9;
    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];
                    dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j][1 ^ k] + 1);
                    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));
                            dp[i][j][k] = min(dp[i][j][k], dp[i - 1][h][1 ^ k] + (j != 0) + 1);
                        }
                }
    int ans = 1e9;
    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 344 KB Output is correct
2 Correct 0 ms 344 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 460 KB Output is correct
6 Correct 0 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 1 ms 344 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 344 KB Output is correct
2 Correct 0 ms 344 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 460 KB Output is correct
6 Correct 0 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 1 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 464 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 79 ms 68060 KB Output is correct
8 Correct 70 ms 67992 KB Output is correct
9 Correct 66 ms 68048 KB Output is correct
10 Correct 71 ms 68012 KB Output is correct
11 Correct 70 ms 68240 KB Output is correct
12 Correct 73 ms 67956 KB Output is correct
13 Correct 66 ms 67996 KB Output is correct
14 Correct 73 ms 67936 KB Output is correct

Subtask #4
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 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 460 KB Output is correct
6 Correct 0 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 1 ms 344 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 -