Submission #865905

#TimeUsernameProblemLanguageResultExecution timeMemory
865905guagua0407Lamps (JOI19_lamps)C++17
100 / 100
69 ms59420 KiB
//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void setIO(string s) {
    freopen((s + ".in").c_str(), "r", stdin);
    freopen((s + ".out").c_str(), "w", stdout);
}

int main() {_
    int n;
    cin>>n;
    string a,b;
    cin>>a>>b;
    a="."+a;
    b="."+b;
    vector<vector<int>> dp(n+1,vector<int>(6,1e9));
    //0 nothing
    //1 1
    //2 2
    //3 3
    //4 1->3
    //5 2->3
    //6 min of above
    dp[0][0]=0;
    for(int i=1;i<=n;i++){
        if(a[i]==b[i]){
            dp[i][0]=min({dp[i-1][0],dp[i-1][1],dp[i-1][2],dp[i-1][3],dp[i-1][4],dp[i-1][5]});
        }
        if(b[i]=='0'){
            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});
        }
        if(b[i]=='1'){
            dp[i][2]=min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2],dp[i-1][3]+1,dp[i-1][4]+1,dp[i-1][5]});
        }
        if(a[i]!=b[i]){
            dp[i][3]=min({dp[i-1][0]+1,dp[i-1][1]+1,dp[i-1][2]+1,dp[i-1][3],dp[i-1][4],dp[i-1][5]});
        }
        if(b[i]=='1'){
            dp[i][4]=min({dp[i-1][0]+2,dp[i-1][1]+1,dp[i-1][2]+2,dp[i-1][3]+1,dp[i-1][4],dp[i-1][5]+1});
        }
        if(b[i]=='0'){
            dp[i][5]=min({dp[i-1][0]+2,dp[i-1][1]+2,dp[i-1][2]+1,dp[i-1][3]+1,dp[i-1][4]+1,dp[i-1][5]});
        }
    }
    int ans=1e9;
    for(int i=0;i<6;i++){
        ans=min(ans,dp[n][i]);
    }
    cout<<ans<<'\n';
    return 0;
}
//maybe its multiset not set

Compilation message (stderr)

lamp.cpp: In function 'void setIO(std::string)':
lamp.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |     freopen((s + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lamp.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 |     freopen((s + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...