Submission #129745

#	Time	Username	Problem	Language	Result	Execution time	Memory
129745		miguel	Lamps (JOI19_lamps)	C++14	4 / 100	50 ms	3336 KiB

lamp

#include<bits/stdc++.h>
using namespace std;
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define dbg(x) cout << #x << '=' << x << '\n';
#define ll long long
#define sz size()
#define x first
#define y second
#define pi pair <int, int>
#define pii pair <int, pi>
#define vi vector <int>
const ll mod = 1e9 + 7;
int n, dp[4][2];
bool a[1000002], b[1000002];

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
    cin>>n;
    for(int i=1; i<=n; i++){
        char c;
        cin>>c;
        if(c=='1') a[i]=1;
    }
    for(int i=1; i<=n; i++){
        char c;
        cin>>c;
        if(c=='1') b[i]=1;
    }
    ///cout<<a[1];
    dp[0][0]=0;
    dp[1][0]=dp[2][0]=dp[3][0]=1;
    for(int i=1; i<=n; i++){
        dp[0][1]=dp[1][1]=dp[2][1]=dp[3][1]=1e9;

        if(a[i]==b[i]) dp[0][1]=min(dp[0][0], min(dp[1][0], min(dp[2][0], dp[3][0])));
        else dp[3][1]=min(dp[0][0]+1, min(dp[1][0]+1, min(dp[2][0]+1, dp[3][0])));

        if(b[i]==1) dp[1][1]=min(dp[0][0]+1, min(dp[1][0], min(dp[2][0]+1, dp[3][0]+1)));
        else dp[2][1]=min(dp[0][0]+1, min(dp[1][0]+1, min(dp[2][0], dp[3][0]+1)));

        for(int j=0; j<=3; j++) dp[j][0]=dp[j][1];
        //cout<<i<<" "<<dp[1][0]<<" "<<dp[2][0]<<" "<<dp[3][0]<<" "<<dp[4][0]<<endl;
    }
    cout<<min(dp[0][0], min(dp[1][0], min(dp[2][0], dp[3][0])));
}

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