Submission #955809

#	Time	Username	Problem	Language	Result	Execution time	Memory
955809		hqminhuwu	Lamps (JOI19_lamps)	C++14	47 / 100	23 ms	34132 KiB

lamp

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll,ll> pll;
typedef pair <int,int> pii;
typedef pair <int,pii> piii;

#define forr(_a,_b,_c) for(int _a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(int _a = (_b) + 1; _a  -  - > (_c);)
#define forf(_a,_b,_c) for(int _a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define mask(i) (1LL << (i))
#define bit(x, i) (((x) >> (i)) & 1)
#define bp __builtin_popcountll
#define file "test"

const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;

int n, dp[N][7];
string a, b;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifdef hqm
        freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
    #endif

    cin >> n >> a >> b;
    
    a = '0' + a;
    b = '0' + b;

    memset (dp, 63, sizeof dp);
    dp[0][0] = 0;

    // 0 1 2 12 3 13
    
    forr (i, 1, n){
        if (b[i] == '0') {
            dp[i][5] = dp[i - 1][5];
            dp[i][5] = min (dp[i][5], dp[i - 1][0] + 2);
            dp[i][5] = min (dp[i][5], dp[i - 1][1] + 1);
            dp[i][5] = min (dp[i][5], dp[i - 1][4] + 1);
            dp[i][2] = min (dp[i - 1][0] + 1, dp[i - 1][2]);
           
        } else {
            dp[i][3] = dp[i - 1][3];
            dp[i][3] = min (dp[i][3], dp[i - 1][0] + 2);
            dp[i][3] = min (dp[i][3], dp[i - 1][1] + 1);
            dp[i][3] = min (dp[i][3], dp[i - 1][2] + 1);
            dp[i][4] = min (dp[i - 1][0] + 1, dp[i - 1][4]);
        }
 
        if(a[i] != b[i]) {
            dp[i][1] = min (dp[i - 1][1], dp[i - 1][0] + 1);
        } else {
            dp[i][0] = dp[i - 1][0];
        }
        
        dp[i][4] = min (dp[i][4], dp[i][5]);
        dp[i][1] = min (dp[i][1], min (dp[i][3], dp[i][5]));
        dp[i][2] = min (dp[i][2], dp[i][3]);
        dp[i][0] = min (dp[i][0], min (dp[i][1], dp[i][2]));
        dp[i][0] = min (dp[i][0], min (dp[i][3], min(dp[i][4], dp[i][5])));
    }

    cout << dp[n][0];

    return 0;
}
/*



*/

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