Submission #1181719

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181719		Gray	Lamps (JOI19_lamps)	C++20	0 / 100	269 ms	301816 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), pdi(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]++;
        }
        pdi[i] = i-pd[i]+1;
        if (i) {
            pz[i]+=pz[i-1]; po[i]+=po[i-1];
            pi[i]+=pi[i-1];
        }
    }
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(4, vector<ll>(2)));
    ll mn00 = 1, mn10=1, mn20=1, mn30=0, mn11, mn21, mn31, mn01; mn11=mn21=mn31=mn01=INF;
    for (ll i=0; i<n; i++){
        dp[i][0][0] = mn00+pz[i]; dp[i][0][1] = mn01+pz[i];
        dp[i][1][0] = mn10+po[i]; dp[i][1][1] = mn11+po[i];
        dp[i][2][0] = mn20+pi[i]; dp[i][2][1] = mn21+pi[i];
        dp[i][3][0] = mn30+pd[i]; dp[i][3][1] = mn31+pdi[i];
        if (i+1<n){
            mn00 = min({mn00, dp[i][0][0]-pz[i], dp[i][1][0]-pz[i]+1, dp[i][2][0]-pz[i]+1, dp[i][3][0]-pz[i]+1});
            mn10 = min({mn10, dp[i][1][0]-po[i], dp[i][0][0]-po[i]+1, dp[i][2][0]-po[i]+1, dp[i][3][0]-po[i]+1});
            mn20 = min({mn20, dp[i][2][0]-pi[i], dp[i][1][0]-pi[i]+1, dp[i][0][0]-pi[i]+1, dp[i][3][0]-pi[i]+1});
            mn30 = min({mn30, dp[i][0][0]-pd[i], dp[i][1][0]-pd[i], dp[i][2][0]-pd[i], dp[i][3][0]-pd[i], dp[i][2][1]-pd[i], dp[i][1][1]-pd[i], dp[i][0][1]-pd[i]});

            mn01 = min({mn01, dp[i][0][1]-pz[i], dp[i][1][1]-pz[i]+1, min(dp[i][2][1], dp[i][2][0])-pz[i]+1, dp[i][3][1]-pz[i]+1});
            mn11 = min({mn11, dp[i][1][1]-po[i], dp[i][0][1]-po[i]+1, min(dp[i][2][1], dp[i][2][0])-po[i]+1, dp[i][3][1]-po[i]+1});
            mn21 = min({mn21, min(dp[i][2][1], dp[i][2][0])-pi[i], dp[i][1][1]-pi[i], dp[i][0][1]-pi[i], dp[i][3][1]-pi[i]});
            mn31 = min({mn31, dp[i][0][1]-pdi[i], dp[i][1][1]-pdi[i], min(dp[i][2][0], dp[i][2][1])-pdi[i], dp[i][3][1]-pdi[i]});
        }
    }
    return min({dp[n-1][0][0], dp[n-1][1][0], dp[n-1][2][0], dp[n-1][3][0], dp[n-1][0][1], dp[n-1][1][1], dp[n-1][2][1], dp[n-1][3][1]});
}

void solve(){
    ll n; string a, b; cin >> n >> a >> b;
    ll res=get(n, a, b);
    cout << res << ln;
}

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: 0 / 4
• Subtask 4: 0 / 49