제출 #1013858

#제출 시각아이디문제언어결과실행 시간메모리
1013858khanhphucscratchLamps (JOI19_lamps)C++14
4 / 100
63 ms33768 KiB
#include<bits/stdc++.h>
using namespace std;
int a[1000005], b[1000005], dp[1000005][6];
int transition(int x, int y)
{
    int ans = 0;
    if(x%2 == 0 && y%2 == 1) ans++;
    if(x/2 != y/2 && y/2 != 2) ans++;
    return ans;
}
int result(int num, int x)
{
    if(x/2 == 0) return 0;
    else if(x/2 == 1) return 1;
    else return (num ^ (x%2));
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    for(int i = 1; i <= n; i++){
        char x; cin>>x;
        a[i] = (x == '1');
    }
    for(int i = 1; i <= n; i++){
        char x; cin>>x;
        b[i] = (x == '1');
    }
    for(int i = 0; i <= n; i++) memset(dp[i], 0x3f, sizeof(dp[i]));
    dp[0][4] = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 6; j++) if(dp[i][j] < 1e9){
            for(int k = 0; k < 6; k++){
                if(result(a[i+1], k) == b[i+1]){
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + transition(j, k));
                }
            }
        }
    }
    int ans = 1e9;
    for(int i = 0; i < 6; i++) ans = min(ans, dp[n][i]);
    cout<<ans;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...