Submission #1150995

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150995		weakweakweak	Lamps (JOI19_lamps)	C++20	0 / 100	12 ms	19692 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

int n;
string a, b;
int dp[2100][2100] = {0};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> a >> b;
    for (char &c : a) c -= '0';
    for (char &c : b) c -= '0';
    a = "$"+a, b = "$"+b;
    memset(dp, 63, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (a[i] != b[i]) {
                if (j & 1) dp[i][j] = min(dp[i][j], dp[i-1][j]);
                dp[i][j+1] = min(dp[i][j+1], dp[i-1][j]+1);
                if (j > 0) dp[i][j-1] = min(dp[i][j-1], dp[i-1][j]);    
            }
            if (a[i] == b[i]) {
                if (j % 2 == 0) dp[i][j] = min(dp[i][j], dp[i-1][j]);
                dp[i][j+1] = min(dp[i][j+1], dp[i-1][j]+1);
                if (j > 0) dp[i][j-1] = min(dp[i][j-1], dp[i-1][j]);
            }
            if (b[i] == 0) {
                for (int k = i; k <= n and b[k] == 0; k++) dp[k][j] = min(dp[k][j], dp[i-1][j]+1);
            }
            if (b[i] == 1) {
                for (int k = i; k <= n and b[k] == 1; k++) dp[k][j] = min(dp[k][j], dp[i-1][j]+1);
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i <= n; i++) ans = min(ans, dp[n][i]);
    cout << ans << '\n';
}

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