Submission #1126842

#	Time	Username	Problem	Language	Result	Execution time	Memory
1126842		culver0412	Lamps (JOI19_lamps)	C++20	100 / 100	234 ms	2388 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
const int INF=(1<<30);
int dp[10]={INF,INF,INF,INF,INF,INF,INF,INF,0,INF},clo[10];

bool f(){
    char c;
    cin >> c;
    return (c=='1');
}

void minn(int &a, int b){
    a=min(a,b);
}

void d(int k,vector<int> p,vector<int> q){
    for(int i=0;i<p.size();i++){
        minn(dp[k],clo[p[i]]+q[i]);
    }
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    bool a[n+2],b[n+2];
    for(int i=1;i<=n;i++){
        a[i]=f();
    }
    for(int i=1;i<=n;i++){
        b[i]=f();
    }
    n++; a[n]=0; b[n]=0;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=9;j++){
            clo[j]=dp[j];
            dp[j]=INF;
        }
        if(a[i]==b[i]) d(8,{0,1,2,3,4,5,6,7,8,9},{0,0,0,-1,0,-1,0,0,0,0});
        else d(9,{0,1,2,3,4,5,6,7,8,9},{1,0,0,0,0,0,1,0,1,0});
        if(!b[i]){
            d(0,{0,2,8},{0,0,1});
            d(1,{1,3,9},{0,0,1});
            d(4,{4,6},{0,1});
            d(5,{5,7},{0,1});
        }
        else{
            d(2,{0,2},{1,0});
            d(3,{1,3},{1,0});
            d(6,{4,6,8},{0,0,1});
            d(7,{5,7,9},{0,0,1});
        }
        //for(int j=0;j<=9;j++) cout << dp[j] << ' ';
        //cout << '\n';
    }
    cout << dp[8] << '\n';
}

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