Submission #1181652

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181652		Gray	Lamps (JOI19_lamps)	C++20	4 / 100	86 ms	106136 KiB

lamp

#include <algorithm>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define ld long double
#define ff first
#define ss second
#define ln "\n"
#define mp make_pair
#define pb push_back
#define INF (ll)2e18
#define MOD 998244353

ll get(ll n, string a, string b){
    vector<ll> pz(n), po(n), pi(n), pd(n);
    for (ll i=0; i<n; i++){
        if (a[i]!=b[i]) pd[i]++;
        if (i) pd[i]+=pd[i-1];
        if (i==0 or b[i]!=b[i-1]){
            if (b[i]=='1') pz[i]++;
            else po[i]++;
        }
        if (a[i]==b[i] and (i==0 or a[i-1]!=b[i-1])){
            pi[i]++;
        }
        if (i) {
            pz[i]+=pz[i-1]; po[i]+=po[i-1];
            pi[i]+=pi[i-1];
        }
    }
    vector<vector<ll>> dp(n, vector<ll>(4, INF));
    ll mn0 = 1, mn1=1, mn2=1, mn4=0;
    for (ll i=0; i<n; i++){
        dp[i][0] = mn0+pz[i];
        dp[i][1] = mn1+po[i];
        dp[i][2] = mn2+pi[i];
        dp[i][3] = mn4+pd[i];
        // cout << i << ": " << dp[i][0] << " - " << dp[i][1] << " - " << dp[i][2] << " - " << dp[i][3] << " |- " << pz[i] << " " << po[i] << " " << pi[i] << ln;
        if (i+1<n){
            mn0 = min({mn0, dp[i][0]-pz[i], dp[i][1]-pz[i]+1, dp[i][2]-pz[i]+1, dp[i][3]-pz[i]+1});
            mn1 = min({mn1, dp[i][1]-po[i], dp[i][0]-po[i]+1, dp[i][2]-po[i]+1, dp[i][3]-po[i]+1});
            mn2 = min({mn2, dp[i][2]-pi[i], dp[i][1]-pi[i]+1, dp[i][0]-pi[i]+1, dp[i][3]-pi[i]+1});
            mn4 = min({mn4, dp[i][0]-pd[i], dp[i][1]-pd[i], dp[i][2]-pd[i], dp[i][3]-pd[i]});
        }
    }
    return min({dp[n-1][0], dp[n-1][1], dp[n-1][2], dp[n-1][3]});
}

void solve(){
    ll n; string a, b; cin >> n >> a >> b;
    ll res=get(n, a, b);
    for (auto &ch:a){
        ch^=('1'^'0');
    }
    // cout << a << " -&- " << b << ln;
    // cout << get(n, a, b)+1 << ln;
    // res=min(res, get(n, a, b)+1);
    cout << res << ln;
}

/*

0101101101011
0000111001011

*/

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #ifdef LOCAL
    auto start = chrono::high_resolution_clock::now();
    #endif
    ll t=1;
    // cin >> t;
    while (t--) solve();
    #ifdef LOCAL
    auto duration = chrono::duration_cast<chrono::microseconds>(chrono::high_resolution_clock::now() - start);
    cout << setprecision(0) << fixed << "time: " << (double)duration.count()/1000.0 << " milliseconds" << endl;
    #endif
}

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