제출 #1236329

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1236329		coderpemula	Lamps (JOI19_lamps)	C++20	4 / 100	49 ms	65036 KiB

lamp

//              +-- -- --++-- +-In the name of ALLAH-+ --++-- -- --+              \\

/* Some Makoto Shinkai's : 

  “Who cares if we can't see any sunshine? I want you more than any blue sky!!!”
    - Tenki no Ko
    
  "By the time the date is over, the comet will be visible in the sky."
    - Kimi no Nawa
    
  “No matter what happens, even if the stars fall, I will live.”
    - Byōsoku 5 Centimeter
  
*/
#include <bits/stdc++.h>
#define Raveluk ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define ll long long
#define ld long double
#define pb push_back
#define fi first
#define se second
#define pii pair<int,int>
#define tii tuple<int,int,int>
#define g1 get<0>
#define g2 get<1>
#define g3 get<2>
#define qf q.front()
#define all(x) (x).begin(), (x).end()
using namespace std;

int main()
{
  Raveluk
  int n,i,j,ans=1e9,k;
  string a,b;
  cin>>n>>a>>b;
  int dp[n+1][4][4];
  // 0 = off 
  // 1 = on 
  // 2 = invers
  // 3 = ga ngapa ngapain
  for(i=0;i<4;i++){
    for(j=0;j<4;j++){
      if(i == j or i == 3 or j == 3) dp[0][i][j] = 1;
      else dp[0][i][j] = 2;
    }
  }
  dp[0][3][3] = 0;
  for(i=1;i<=n;i++){
    int mn = 1e9;
    //cout<<i<<" :\n";
    for(j=0;j<4;j++){
      for(k=0;k<4;k++){
        mn = min(mn,dp[i-1][j][k]);
        dp[i][j][k] = 1e9;
      }
    }
    if(a[i-1] == b[i-1]){
      // gaboleh invers (2)
      // boleh ga ngapa ngapain (3)
      if(b[i-1] == '1'){
        // boleh on (1)
        // gaboleh off (0)
        // boleh apapun selama akhirnya -> on
        // bisa juga off, terus invers [0][2]
        dp[i][0][2] = min(dp[i-1][0][2],mn+2);
        int nm = 1e9;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][2]);
        dp[i][0][2] = min(dp[i][0][2],nm+1);
        //cout<<"off invers "<<dp[i][0][2]<<endl;
        nm = 1e9;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][1]);
        dp[i][1][1] = min(dp[i-1][1][1],nm);
        dp[i][1][1] = min(dp[i][1][1],mn+1);
        dp[i][0][1] = min(dp[i-1][0][1],mn+2);
        dp[i][0][1] = min(dp[i][0][1],nm+1);
        dp[i][2][1] = min(dp[i-1][2][1],mn+2);
        dp[i][2][1] = min(dp[i][2][1],nm+1);
        dp[i][3][1] = min(dp[i-1][3][1],mn+1);
        dp[i][3][1] = dp[i][1][3] = min(dp[i][3][1],nm);
        //for(j=0;j<4;j++) cout<<j<<" "<<dp[i][j][1]<<endl;
      }
      else{
        // gaboleh on (1)
        // boleh off (0)
        // boleh apapun selama akhirnya -> off
        // bisa juga on, terus invers [1][2]
        dp[i][1][2] = min(dp[i-1][1][2],mn+2);
        int nm = 1e9;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][2]);
        dp[i][1][2] = min(dp[i][1][2],nm+1);
        nm = 1e9;
        //cout<<"on invers "<<dp[i][1][2]<<endl;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][0]);
        dp[i][0][0] = min(dp[i-1][0][0],mn+2);
        dp[i][0][0] = min(dp[i][0][0],nm);
        dp[i][1][0] = min(dp[i-1][1][0],mn+2);
        dp[i][1][0] = min(dp[i][1][0],nm+1);
        dp[i][2][0] = min(dp[i-1][2][0],mn+2);
        dp[i][2][0] = min(dp[i][2][0],nm+1);
        dp[i][3][0] = min(dp[i-1][3][0],mn+1);
        dp[i][3][0] = dp[i][0][3] = min(dp[i][3][0],nm);
        //for(j=0;j<4;j++) cout<<j<<" "<<dp[i][j][0]<<endl;
      }
      dp[i][3][3] = mn;
      //cout<<dp[i][3][3]<<endl;
    }
    else{
      // boleh invers (2)
      // gaboleh ngapa ngapain (3)
      if(b[i-1] == '1'){
        // boleh on (1)
        // gaboleh off (0)
        // boleh apapun selama akhirnya -> on
        // bisa juga off, terus invers [0][2]
        dp[i][0][2] = min(dp[i-1][0][2],mn+2);
        int nm = 1e9;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][2]);
        dp[i][0][2] = min(dp[i][0][2],nm+1);
        //cout<<"off invers "<<dp[i][0][2]<<endl;
        nm = 1e9;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][1]);
        dp[i][1][1] = min(dp[i-1][1][1],mn+1);
        dp[i][0][1] = min(dp[i-1][0][1],mn+2);
        dp[i][0][1] = min(dp[i][0][1],nm+1);
        dp[i][2][1] = min(dp[i-1][2][1],mn+2);
        dp[i][2][1] = min(dp[i][2][1],nm+1);
        dp[i][3][1] = min(dp[i-1][3][1],mn+1);
        dp[i][3][1] = dp[i][1][3] = min(dp[i][3][1],nm);
        //for(j=0;j<4;j++) cout<<j<<" "<<dp[i][j][1]<<endl;
      }
      else{
        // gaboleh on (1)
        // boleh off (0)
        // boleh apapun selama akhirnya -> off
        // bisa juga on, terus invers [1][2]
        dp[i][1][2] = min(dp[i-1][1][2],mn+2);
        int nm = 1e9;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][2]);
        dp[i][1][2] = min(dp[i][1][2],nm+1);
        //cout<<"on invers "<<dp[i][1][2]<<endl;
        nm = 1e9;
        for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][0]);
        dp[i][0][0] = min(dp[i-1][0][0],nm);
        dp[i][0][0] = min(dp[i][0][0],mn+1);
        dp[i][1][0] = min(dp[i-1][1][0],mn+2);
        dp[i][1][0] = min(dp[i][1][0],nm+1);
        dp[i][2][0] = min(dp[i-1][2][0],mn+2);
        dp[i][2][0] = min(dp[i][2][0],nm+1);
        dp[i][3][0] = dp[i-1][3][0];
        dp[i][0][3] = dp[i-1][0][3];
        dp[i][3][0] = min(dp[i][3][0],mn+1);
        dp[i][3][0] = dp[i][0][3] = min(dp[i][3][0],nm);
        //for(j=0;j<4;j++) cout<<j<<" "<<dp[i][j][0]<<endl;
      }
      dp[i][3][2] = min(dp[i-1][3][2],mn+1);
      int nm = 1e9;
      for(j=0;j<4;j++) nm = min(nm,dp[i-1][j][2]);
      dp[i][3][2] = min(dp[i][3][2],nm);
      dp[i][2][3] = dp[i][3][2];
      dp[i][2][2] = min(dp[i-1][2][2],mn+1);
      dp[i][2][2] = min(dp[i-1][2][2],nm);
      //cout<<dp[i][2][2]<<" "<<dp[i][3][2]<<endl;
    }
  }
  for(i=0;i<4;i++){
    for(j=0;j<4;j++) ans = min(ans,dp[n][i][j]);
  }
  cout<<ans;
  
  return 0;
}

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