제출 #378741

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378741		balbit	Lamps (JOI19_lamps)	C++14	0 / 100	3 ms	2816 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define y1 zck_is_king
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MN(a,b) a = min(a,(__typeof__(a))(b))
#define MX(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define REP(i,n) for (int i = 0; i<n; ++i)
#define RREP(i,n) for (int i = n-1; i>=0; --i)
#define REP1(i,n) for (int i = 1; i<=n; ++i)
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#ifdef BALBIT
#define IOS()
#define bug(...) fprintf(stderr,"#%d (%s) = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define bug(...)
#endif


void GG(){cout<<"0\n"; exit(0);}
const ll mod = 1e9+7;
ll mpow(ll a, ll n, ll mo = mod){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mo;
        a = a*a %mo;
        n>>=1;
    }
    return re;
}

ll inv (ll b, ll mo = mod){
    if (b==1) return b;
    return (mo-mo/b) * inv(mo%b,mo) % mo;
}

const int maxn = 1e5+5;
const int inf = 0x3f3f3f3f;

bool a[maxn], b[maxn];
int dp[maxn][2][3];

signed main(){
    IOS();
    int n; cin>>n;
    REP1(i,n) {
        char c; cin>>c; a[i] = c=='1';
    }
    REP1(i,n) {
        char c; cin>>c; b[i] = c=='1';
    }
    memset (dp, 0x3f, sizeof dp);
    int re = inf;
    dp[0][0][0] = 0;
    REP1(i,n) {
        REP(flip, 2) {
            REP(fl, 3) {
                int &me = dp[i][flip][fl];
                if (fl == 0) {
                    if (flip == (a[i] ^ b[i])) {
                        MN(me, dp[i-1][flip^1][fl]+(flip==1));
                        MN(me, dp[i-1][flip][1]);
                        MN(me, dp[i-1][flip][2]);
                        MN(me, dp[i-1][flip][0]);
                        MN(me, dp[i-1][flip^1][1] + (flip==1));
                        MN(me, dp[i-1][flip^1][2] + (flip==1));
                    }
                }else{
                    if (fl == 1)
                        MN(me, dp[i-1][flip][0]+1);

                    if (b[i] != b[i-1]) {
                        MN(me, dp[i-1][flip][fl^3] + (fl == 2));
                    }else{
                        MN(me, dp[i-1][flip][fl]);
                    }
                }
                if (i == n) {
                    MN(re, dp[i][flip][fl]);
                }
            }
        }
    }
    bug(dp[1][0][1]);
    bug(dp[3][0][1]);
    bug(dp[4][0][1]);
    bug(dp[5][0][1]);
    bug(dp[6][0][1]);
    bug(dp[7][0][1]);
    bug(dp[8][0][1]);
    bug(dp[9][0][1]);
    bug(dp[10][0][1]);

    bug(dp[1][0][2]);
    bug(dp[3][0][2]);
    bug(dp[4][0][2]);
    bug(dp[5][0][2]);
    bug(dp[6][0][2]);
    bug(dp[7][0][2]);
    bug(dp[8][0][2]);
    bug(dp[9][0][2]);
    bug(dp[10][0][2]);

    bug(dp[10][1][0]);
    bug(dp[11][1][0]);
    bug(dp[12][1][0]);
    cout<<re<<endl;
}

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