제출 #483171

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
483171	2021-10-28 02:38:50	phamhoanghiep	Lamps (JOI19_lamps)	C++17	4 / 100	77 ms	30936 KiB

lamp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+6;
string st;
string en;
int mask[maxn]; // 0: 0, 1: 1, 2: f, 3: 0f, 4: 1f, 5: nothing
int dp[maxn][6];
int n;
signed main() {
    cin>>n;
    cin>>st>>en;
    st=' '+st;
    en=' '+en;
    for(int i=1 ; i<=n ; i++) {
        if(st[i]!=en[i]) mask[i]+=(1<<2);
        if(en[i]=='0') mask[i]+=(1<<4)+(1<<0);
        if(en[i]=='1') mask[i]+=(1<<1)+(1<<3);
        dp[i][0]=dp[i][1]=dp[i][2]=dp[i][3]=dp[i][4]=dp[i][5]=n+1;
    }
    dp[0][0]=dp[0][1]=dp[0][2]=1; dp[0][3]=dp[0][4]=2; dp[0][5]=0;
    for(int i=1 ; i<=n ; i++) {
        if(en[i]=='0') {
            // 0 or 1f
            dp[i][0]=min({dp[i-1][0],dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]+1});
            dp[i][3]=min({dp[i-1][0]+1,dp[i-1][1]+2,dp[i-1][2]+1,dp[i-1][3],dp[i-1][4]+1,dp[i-1][5]+2});
        }
        else {
            dp[i][1]=min({dp[i-1][0]+1,dp[i-1][1],dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]+1});
            dp[i][4]=min({dp[i-1][0]+2,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]+2});
        }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

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