oj.uz

Submission #1014341

# Submission time Handle Problem Language Result Execution time Memory
1014341 2024-07-04T17:03:58 Z anHiep Lamps (JOI19_lamps) C++14
4 / 100
 87 ms 68092 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];
                    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] + 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 344 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 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 464 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 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 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 464 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 344 KB Output is correct
2 Correct 1 ms 504 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 87 ms 67924 KB Output is correct
8 Correct 69 ms 67996 KB Output is correct
9 Correct 70 ms 68016 KB Output is correct
10 Correct 85 ms 67992 KB Output is correct
11 Correct 68 ms 68092 KB Output is correct
12 Correct 71 ms 68016 KB Output is correct
13 Correct 67 ms 68000 KB Output is correct
14 Correct 81 ms 68008 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 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 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 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Incorrect 0 ms 464 KB Output isn't correct
14 Halted 0 ms 0 KB -