Submission #280218

#	Time	Username	Problem	Language	Result	Execution time	Memory
280218		MKopchev	Lamps (JOI19_lamps)	C++14	100 / 100	261 ms	121980 KiB

lamp

#include<bits/stdc++.h>
using namespace std;

const int nmax=1e6+42;

int dp[nmax][3][2];
/*dp[pos][type_1][type_2]
type_1: 0->set 0, 1->set 1, 2->nothing
type_2: 0->nothing, 1-> flip
*/

int n;
string a,b;

int rec(int pos,int type_1,int type_2)
{
    if(pos==n)return 0;
    if(dp[pos][type_1][type_2]!=-1)return dp[pos][type_1][type_2];

    int ret=2*n;

    for(int type_1_new=0;type_1_new<3;type_1_new++)
        for(int type_2_new=0;type_2_new<2;type_2_new++)
        {
            char cur=a[pos];

            if(type_1_new==0)cur='0';
            if(type_1_new==1)cur='1';

            if(type_2_new==1)cur='1'-cur+'0';

            if(cur==b[pos])
            {
                int add=0;

                if(type_1_new!=2&&type_1_new!=type_1)add++;

                if(type_2==0&&type_2_new==1)add++;

                ret=min(ret,add+rec(pos+1,type_1_new,type_2_new));
            }
        }
    dp[pos][type_1][type_2]=ret;

    //cout<<pos<<" "<<type_1<<" "<<type_2<<" -> "<<ret<<endl;

    return ret;
}
int main()
{
    memset(dp,-1,sizeof(dp));

    ios_base::sync_with_stdio(false);

    cin>>n;

    cin>>a>>b;

    cout<<rec(0,2,0)<<endl;
    return 0;
}

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