Submission #1354105

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354105		kiensosad	Lamps (JOI19_lamps)	C++20	100 / 100	40 ms	33692 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000;
int dp[N+2][8];
int get(int n,int k){
    return (n>>k)&1;
}
int change(int b,int mask){
    for(int i=0;i<3;i++){
        if(get(mask,i)==0) continue;
        if(i==0) b=0;
        if(i==1) b=1;
        if(i==2) b^=1;
        // cout<<i<<" "<<mask<<" "<<get(mask,i)<<'\n';
    }
    return b;
}
int main(){
    #define task ""
    if(fopen(task ".inp", "r")){
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    string s,t;
    cin>>s>>t;
    s=" "+s;
    t=" "+t;
    // int n=s.size()-1;
    for(int i=0;i<=n;i++){
        for(int j=0;j<=7;j++){
            dp[i][j]=1e9;
        }
    }
    dp[0][0]=0;
    // cout<<change(0,2)<<'\n';
    for(int i=1;i<=n;i++){
        for(int mask=0;mask<=7;mask++){
            if(change(s[i]-'0',mask)!=t[i]-'0') continue;
            // cout<<mask<<'\n';
            dp[i][mask]=dp[i-1][mask];
            for(int k=0;k<3;k++){
                int nm=mask^(1<<k);
                dp[i][mask]=min(dp[i][mask],dp[i-1][nm]+(nm<mask));
            }
        }
    }
    int ans=1e9;
    for(int mask=0;mask<=7;mask++){
        ans=min(ans,dp[n][mask]);
    }
    cout<<ans<<'\n';
    
    return 0;
}

Compilation message (stderr)

lamp.cpp: In function 'int main()':
lamp.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(task ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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