Submission #1013864

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013864		vjudge1	Lamps (JOI19_lamps)	C++17	100 / 100	95 ms	31752 KiB

lamp

#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) num = 0;
    else if(x/2 == 1) num = 1;
    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;
}

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