Submission #171301

#	Time	Username	Problem	Language	Result	Execution time	Memory
171301		gs18103	Lamps (JOI19_lamps)	C++14	0 / 100	9 ms	420 KiB

lamp

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()

using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 1010101;
const int INF = 1e9;
const ll LINF = 1e18;

int dp[4][MAX];

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    int n;
    string s, t;
    cin >> n >> s >> t;
    if(s[0] != t[0]) {
        dp[0][0] = INF;
        if(t[0] == '0') dp[1][0] = 1, dp[2][0] = 2;
        if(t[0] == '1') dp[1][0] = 2, dp[2][0] = 1;
        dp[3][0] = 1;
    }
    for(int i = 1; i < n; i++) {
        if(s[i] == t[i]) {
            dp[0][i] = min({dp[0][i-1], dp[1][i-1], dp[2][i-1], dp[3][i-1]});
            if(t[i] == '0') dp[1][i] = dp[1][i-1], dp[2][i] = dp[2][i-1]+1;
            if(t[i] == '1') dp[2][i] = dp[2][i-1], dp[1][i] = dp[1][i-1]+1;
            dp[3][i] = dp[3][i-1]+1;
        }
        else {
            dp[0][i] = INF;
            if(t[i] == '0') {
                dp[1][i] = min({dp[0][i-1]+1, dp[1][i-1], dp[2][i-1]+1, dp[3][i-1]+1});
                dp[2][i] = dp[1][i] + 1;
            }
            else {
                dp[2][i] = min({dp[0][i-1]+1, dp[1][i-1]+1, dp[2][i-1], dp[3][i-1]+1});
                dp[1][i] = dp[2][i] + 1;
            }
            dp[3][i] = min({dp[0][i-1]+1, dp[1][i-1]+1, dp[2][i-1]+1, dp[3][i-1]});
        }
    }
    cout << min({dp[0][n-1], dp[1][n-1], dp[2][n-1], dp[3][n-1]});
}

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