Submission #1001822

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001822		snpmrnhlol	Lamps (JOI19_lamps)	C++17	100 / 100	123 ms	27988 KiB

lamp

#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
**/

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