Submission #1308478

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308478		mohammadsam	Lamps (JOI19_lamps)	C++20	100 / 100	355 ms	41916 KiB

lamp

/*
    in the name of god
*/
//#pragma GCC optimize("Ofast,O3,unroll-loops")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,sse4a,avx,avx2,popcnt,tune=native")

#include <bits/stdc++.h>

using namespace std;

typedef pair<int,int> pii;
typedef pair<long long ,long long> pll;
typedef long long ll ;

#define File          freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout);
#define all(V)        V.begin(),V.end()
#define setprec(x)    fixed << setprecision(x)
#define Mp(a,b)       make_pair(a,b)
#define len(V)        (int)(V.size())
#define sep           ' '
#define endl          '\n'
#define pb            push_back
#define fi            first
#define sec           second
#define popcount(x)   __builtin_popcount(x)
#define lid           u<<1
#define rid           (lid)|1
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

const ll N = 1e6 + 10,SQ=320,LOG=31;
const ll inf = 1e9 , MD = 1e9 + 7;

inline ll md(ll x){ x %= MD; return (x < 0 ? x + MD : x);}
int n ; 
string A,B;
int dp[N][5][2];
vector<vector<int>> V;
int val(int i,int j,int p){
    int now = (A[i] == '1');
    if(!V[j].empty()) now = V[j].back();
    if(p) now ^= 1;
    return now;
}
int cost(int i,int j){
    if(i == j) return 0;
    if(min(len(V[i]),len(V[j])) <= 1){
        if(V[i].empty()) return len(V[j]);
        if(V[j].empty()) return 0;
        if(len(V[i]) == 1){
            bool c = 0;
            for(auto h : V[j]) c |= (h == V[i][0]);
            return len(V[j]) - c;
        }
        bool c = 0;
        for(auto h : V[i]) c |= (h == V[j][0]);
        return 1 - c;
    }
    return 1;
}
int32_t main() {
    ios_base::sync_with_stdio(false);cout.tie(0);cin.tie(0);
    cin >> n >> A >> B;
    A = '#' + A;
    B = '#' + B;
    V.pb({});
    V.pb({1});
    V.pb({0});
    V.pb({0,1});
    V.pb({1,0});
    for(int i =0 ;i <= n;i++){
        for(int j = 0;j < 5;j++) for(int k = 0;k < 2;k++) dp[i][j][k]  = inf;
    }
    dp[0][0][0] = 0;
    for(int i =1 ;i <= n;i++){
        for(int j = 0; j < 5;j++){
            for(int k = 0 ;k < 2;k++){
                for(int p = 0 ;p < 5;p++){
                    for(int r = 0;r < 2;r++){
                        if(val(i,p,r) == (B[i] == '1')) dp[i][p][r] = min(dp[i][p][r],dp[i-1][j][k] + cost(j,p) + (r == 1 && k == 0));
                    }
                }
            }
        }
    }
    int ans = inf;
    for(int j = 0;j < 5;j++){
        for(int r = 0;r < 2;r++) ans = min(ans,dp[n][j][r]);
    }
    cout << ans << endl;
    return 0;
}

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