Submission #654985

#	Time	Username	Problem	Language	Result	Execution time	Memory
654985		DJeniUp	Lamps (JOI19_lamps)	C++17	100 / 100	88 ms	59136 KiB

lamp

#include "bits/stdc++.h"
//#pragma GCC optimize("O3")

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll>pairll;
typedef long double ld;

#define fr first
#define sc second
#define pb push_back
#define INF 100000000000000007
#define I 100000000000007
#define N 100007
#define endl '\n'
#define MOD 998244353

ll n,d[N*10][7];

string a,b;

int main()
{
    cin>>n;
    cin>>a>>b;
    a=" "+a;
    b=" "+b;
    d[0][1]=1;
    d[0][2]=1;
    d[0][3]=2;
    d[0][4]=2;
    d[0][5]=1;
    for(int i=1;i<=n;i++){
        if(a[i]==b[i]){
            d[i][5]=INF;
            d[i][0]=min(d[i-1][0],min(d[i-1][1],min(d[i-1][2],min(d[i-1][3],min(d[i-1][4],d[i-1][5])))));
            if(a[i]=='0'){
                d[i][1]=min(d[i-1][0]+1,min(d[i-1][1],min(d[i-1][2]+1,min(d[i-1][3],min(d[i-1][4]+1,d[i-1][5]+1)))));
                d[i][2]=INF;
                d[i][3]=INF;
                d[i][4]=min(d[i-1][0]+2,min(d[i-1][1]+2,min(d[i-1][2]+1,min(d[i-1][3]+1,min(d[i-1][4],d[i-1][5]+1)))));
            }else{
                d[i][1]=INF;
                d[i][2]=min(d[i-1][0]+1,min(d[i-1][1]+1,min(d[i-1][2],min(d[i-1][3]+1,min(d[i-1][4],d[i-1][5]+1)))));
                d[i][3]=min(d[i-1][0]+2,min(d[i-1][1]+1,min(d[i-1][2]+2,min(d[i-1][3],min(d[i-1][4]+1,d[i-1][5]+1)))));
                d[i][4]=INF;
            }
        }else{
            d[i][5]=min(d[i-1][0]+1,min(d[i-1][1]+1,min(d[i-1][2]+1,min(d[i-1][3],min(d[i-1][4],d[i-1][5])))));
            d[i][0]=INF;
            if(a[i]=='0'){
                d[i][1]=INF;
                d[i][2]=min(d[i-1][0]+1,min(d[i-1][1]+1,min(d[i-1][2],min(d[i-1][3]+1,min(d[i-1][4],d[i-1][5]+1)))));
                d[i][3]=min(d[i-1][0]+2,min(d[i-1][1]+1,min(d[i-1][2]+2,min(d[i-1][3],min(d[i-1][4]+1,d[i-1][5]+1)))));
                d[i][4]=INF;
            }else{
                d[i][1]=min(d[i-1][0]+1,min(d[i-1][1],min(d[i-1][2]+1,min(d[i-1][3],min(d[i-1][4]+1,d[i-1][5]+1)))));
                d[i][2]=INF;
                d[i][3]=INF;
                d[i][4]=min(d[i-1][0]+2,min(d[i-1][1]+2,min(d[i-1][2]+1,min(d[i-1][3]+1,min(d[i-1][4],d[i-1][5]+1)))));
            }
        }
        //cout<<i<<" "<<d[i][0]<<" "<<d[i][1]<<" "<<d[i][2]<<" "<<d[i][3]<<" "<<d[i][4]<<" "<<d[i][5]<<endl;
    }
    cout<<min(d[n][0],min(d[n][1],min(d[n][2],min(d[n][3],min(d[n][4],d[n][5])))))<<endl;

    return 0;
}

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