Submission #376182

#	Time	Username	Problem	Language	Result	Execution time	Memory
376182		daniel920712	Lamps (JOI19_lamps)	C++14	4 / 100	261 ms	129644 KiB

lamp

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <queue>
#include <time.h>

using namespace std;
char a[1000005];
char b[1000005];
bool have[15][1000005]={0};
int DP[15][1000005],N;
bool vis[1000005]={0};
queue < pair < int , int > > BFS;
int F(int what,int here)
{
    if(here==N) return 0;
    if(have[what][here]) return DP[what][here];
    DP[what][here]=2e9;
    have[what][here]=1;

    if(a[here]==b[here]) DP[what][here]=min(DP[what][here],F(0,here+1));
    if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1)+1);

    if(b[here]=='1')
    {
        DP[what][here]=min(DP[what][here],F(3,here+1)+2);
        DP[what][here]=min(DP[what][here],F(5,here+1)+1);
        DP[what][here]=min(DP[what][here],F(6,here+1)+2);
        DP[what][here]=min(DP[what][here],F(9,here+1)+2);
    }
    else
    {
        DP[what][here]=min(DP[what][here],F(2,here+1)+2);
        DP[what][here]=min(DP[what][here],F(4,here+1)+1);
        DP[what][here]=min(DP[what][here],F(7,here+1)+2);
        DP[what][here]=min(DP[what][here],F(8,here+1)+2);
    }
    if(what==1)
    {
        if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
        else
        {
            if(b[here]=='1') DP[what][here]=min(DP[what][here],F(6,here+1)+1);
            else DP[what][here]=min(DP[what][here],F(7,here+1)+2);
        }
    }
    if(what==2)
    {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(5,here+1));
            DP[what][here]=min(DP[what][here],F(6,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(2,here+1));
    }
    if(what==3)
    {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(4,here+1));
            DP[what][here]=min(DP[what][here],F(7,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(3,here+1));
    }
    if(what==4)
    {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(3,here+1)+1);
            DP[what][here]=min(DP[what][here],F(9,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(4,here+1));
    }
    if(what==5)
    {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(2,here+1)+1);
            DP[what][here]=min(DP[what][here],F(8,here+1)+1);
        }
        else DP[what][here]=min(DP[what][here],F(5,here+1));
    }
    if(what==6)
    {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(8,here+1)+1);
            DP[what][here]=min(DP[what][here],F(2,here+1)+1);
            if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(6,here+1));
    }
    if(what==7)
    {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(9,here+1)+1);
            DP[what][here]=min(DP[what][here],F(3,here+1)+1);
            if(a[here]!=b[here]) DP[what][here]=min(DP[what][here],F(1,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(7,here+1));
    }
   if(what==8)
   {
        if(b[here]=='1')
        {
            DP[what][here]=min(DP[what][here],F(9,here+1)+1);
            DP[what][here]=min(DP[what][here],F(3,here+1)+1);
            DP[what][here]=min(DP[what][here],F(5,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(8,here+1));
   }
    if(what==9)
   {
        if(b[here]=='0')
        {
            DP[what][here]=min(DP[what][here],F(8,here+1)+1);
            DP[what][here]=min(DP[what][here],F(2,here+1)+1);
            DP[what][here]=min(DP[what][here],F(4,here+1));
        }
        else DP[what][here]=min(DP[what][here],F(9,here+1));
   }

    return DP[what][here];
}
int main()
{
    //srand(time(NULL));
    int M,ans=0,i,j,x=0,y=0,aa,tt;
    scanf("%d",&N);
    scanf("%s %s",a,b);
    printf("%d\n",F(0,0));
    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:129:9: warning: unused variable 'M' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |         ^
lamp.cpp:129:11: warning: unused variable 'ans' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |           ^~~
lamp.cpp:129:17: warning: unused variable 'i' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |                 ^
lamp.cpp:129:19: warning: unused variable 'j' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |                   ^
lamp.cpp:129:21: warning: unused variable 'x' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |                     ^
lamp.cpp:129:25: warning: unused variable 'y' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |                         ^
lamp.cpp:129:29: warning: unused variable 'aa' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |                             ^~
lamp.cpp:129:32: warning: unused variable 'tt' [-Wunused-variable]
  129 |     int M,ans=0,i,j,x=0,y=0,aa,tt;
      |                                ^~
lamp.cpp:130:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  130 |     scanf("%d",&N);
      |     ~~~~~^~~~~~~~~
lamp.cpp:131:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  131 |     scanf("%s %s",a,b);
      |     ~~~~~^~~~~~~~~~~~~

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