Submission #960693

#	Time	Username	Problem	Language	Result	Execution time	Memory
960693		Darren0724	Lamps (JOI19_lamps)	C++17	100 / 100	65 ms	37724 KiB

lamp

#pragma GCC optimize("Ofast","O3","unroll-loops")
#pragma GCC target("avx2")
#include <bits/stdc++.h>
using namespace std;
#define LCBorz ios_base::sync_with_stdio(false); cin.tie(0);
#define all(x) x.begin(), x.end()
#define endl '\n'
const int N=200005;
const int INF=1e9;
 
int32_t main() {
    LCBorz;
    int n;cin>>n;
    vector<int> s(n+1),t(n+1);
    for(int i=1;i<=n;i++){
        char c;cin>>c;
        s[i]=c-'0';
    }
    for(int i=1;i<=n;i++){
        char c;cin>>c;
        t[i]=c-'0';
    }
    vector dp(6,vector(n+1,INF));
    dp[0][0]=0;
    // 0->none 1->no0 2->no1 3->flip 4->flip0 5-> flip1
    int a[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
    };
    for(int i=1;i<=n;i++){
        if(s[i]==0&&t[i]==0){
            for(int k:{0,1,5}){
                for(int j=0;j<6;j++){
                    dp[k][i]=min(dp[k][i],dp[j][i-1]+a[j][k]);
                }
            } 
        }
        if(s[i]==1&&t[i]==0){
            for(int k:{1,3,5}){
                for(int j=0;j<6;j++){
                    dp[k][i]=min(dp[k][i],dp[j][i-1]+a[j][k]);
                }
            } 
        }
        if(s[i]==0&&t[i]==1){
            for(int k:{2,3,4}){
                for(int j=0;j<6;j++){
                    dp[k][i]=min(dp[k][i],dp[j][i-1]+a[j][k]);
                }
            } 
        }
        if(s[i]==1&&t[i]==1){
            for(int k:{0,2,4}){
                for(int j=0;j<6;j++){
                    dp[k][i]=min(dp[k][i],dp[j][i-1]+a[j][k]);
                }
            } 
        }
    }
    int ans=INF;
    for(int i=0;i<6;i++){
        ans=min(ans,dp[i][n]);
    }
    cout<<ans<<endl;
 
    return 0;
}

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