제출 #143623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
143623		osaaateiasavtnl	Lamps (JOI19_lamps)	C++14	100 / 100	331 ms	51600 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
#define int long long 
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
const int N = 1e6 + 7, INF = 1e9 + 7;
int n;
string a, b;
int dp[N][3][2];
bool check(char c1, char c2, int i, int j) {
    if (i == 0 && j == 0) return c1 == c2;
    if (i == 0) return c1 != c2;
    if (i == 1 && j == 0) return c2 == '0';
    if (i == 1) return c2 == '1';
    if (i == 2 && j == 0) return c2 == '1';
    return c2 == '0';
}   
void upd(int p, int i, int j, int c) {
    if (check(a[p - 1], b[p - 1], i, j)) {
        dp[p][i][j] = min(dp[p][i][j], c);
    }   
}   
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    for (int i = 0; i < N; ++i) for (int j = 0; j < 3; ++j) for (int k = 0; k < 2; ++k) dp[i][j][k] = INF;
    cin >> n >> a >> b;
    dp[0][0][0] = 0;
    for (int p = 0; p < n; ++p) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 2; ++j) {

                for (int ii = 0; ii < 3; ++ii) {
                    for (int jj = 0; jj < 2; ++jj) {
                        upd(p + 1, ii, jj, dp[p][i][j] + (ii && ii != i) + (jj && jj != j));
                    }
                }

            }
        }
    }   
    int ans = INF;
    for (int i = 0; i < 3; ++i) for (int j = 0; j < 2; ++j) ans = min(ans, dp[n][i][j]);
    cout << ans << '\n';
}                        

• Subtask 1: 6 / 6
• Subtask 2: 41 / 41
• Subtask 3: 4 / 4
• Subtask 4: 49 / 49