Submission #1001822

#TimeUsernameProblemLanguageResultExecution timeMemory
1001822snpmrnhlolLamps (JOI19_lamps)C++17
100 / 100
123 ms27988 KiB
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
const int inf = 2e9;
array <int,6> dp[N + 1];
int m[6][6] = {
    {0,1,1,1,2,2},
    {0,0,1,1,1,2},
    {0,1,0,1,2,1},
    {0,1,1,0,1,1},
    {0,0,1,0,0,1},
    {0,1,0,0,1,0}
};
int values[6] = {2,1,0,3,0,1};
bool v[N],v2[N];
int main(){
    int n;
    cin>>n;
    for(int i = 0;i < n;i++){char ch;cin>>ch;v[i] = ch - '0';}
    for(int i = 0;i < n;i++){char ch;cin>>ch;v2[i] = ch - '0';}
    dp[0] = {0,inf,inf,inf,inf,inf};
    ///0 - empty 1 - on 2 - off
    ///3 - toggle 4 - on toggle 5 - off toggle
    for(int i = 0;i < n;i++){
        dp[i + 1] = {inf,inf,inf,inf,inf,inf};
        for(int j = 0;j < 6;j++){
            for(int k = 0;k < 6;k++){
                int cost = m[j][k];
                if((values[k] >= 2 && ((v[i]^v2[i]) == values[k] - 2)) || (values[k] <= 1 && values[k] == v2[i])){
                    dp[i + 1][k] = min(dp[i + 1][k], dp[i][j] + cost);
                }
            }
        }
        /*for(int j = 0;j < 6;j++){
            cout<<dp[i + 1][j]<<' ';
        }
        cout<<'\n';*/
    }
    int ans = inf;
    for(int j = 0;j < 6;j++)ans = min(ans, dp[n][j]);
    cout<<ans;
    return 0;
}
/**
12
010100101101
111000010010
on 0 6
toggle 3 11
**/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...