oj.uz

답안 #1014332

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1014332 2024-07-04T16:49:29 Z anHiep Lamps (JOI19_lamps) C++14
4 / 100
 93 ms 68268 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(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));
                    }
            }
    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

# 결과 실행 시간 메모리 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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 460 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

# 결과 실행 시간 메모리 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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 460 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

# 결과 실행 시간 메모리 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 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 84 ms 67896 KB Output is correct
8 Correct 81 ms 68000 KB Output is correct
9 Correct 77 ms 68004 KB Output is correct
10 Correct 77 ms 68004 KB Output is correct
11 Correct 71 ms 68268 KB Output is correct
12 Correct 77 ms 68004 KB Output is correct
13 Correct 93 ms 67996 KB Output is correct
14 Correct 79 ms 68008 KB Output is correct

Subtask #4
0 / 49.0

# 결과 실행 시간 메모리 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 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 1 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 460 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 -