Submission #1308445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1308445		Bahamin	Lamps (JOI19_lamps)	C++20	100 / 100	63 ms	18184 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { os << '{'; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << '}'; }

#define ll long long
#define ld long double
#define all(a) (a).begin(), (a).end()
#define sui cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false)
const int MAX_N = 1e5 + 5;
const int MOD = 1e9 + 7;
const ll INF = 1e9;
const ld EPS = 1e-9;
const int LOG = 30;


void solve() {
    int n;
    cin >> n;
    string a, b;
    cin >> a >> b;
    int dp[n + 1][2][2];
    for (int i = 0; i < 2; i++) for (int j = 0; j < 2; j++) dp[n][i][j] = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = 0; j < (i == 0 ? 1 : 2); j++) for (int k = 0; k < (i == 0 ? 1 : 2); k++)
        {
            dp[i][j][k] = INF;
            int num = -1;
            if (k) num = (j ? 1 - (b[i - 1] - '0') : b[i - 1] - '0');
            for (int p = 0; p < 2; p++) for (int pp = 0; pp < 2; pp++)
            {
                int num1 = a[i] - '0';
                int num2 = -1;
                if (pp) num1 = num2 = (p ? 1 - (b[i] - '0') : b[i] - '0');
                if (p) num1 ^= 1;
                if (num1 != b[i] - '0') continue;
                if (k == 0) dp[i][j][k] = min(dp[i][j][k], (p == 1 && j == 0) + pp + dp[i + 1][p][pp]);
                else if (pp) dp[i][j][k] = min(dp[i][j][k], (p == 1 && j == 0) + (num2 != num) + dp[i + 1][p][pp]);
                else dp[i][j][k] = min(dp[i][j][k], (p == 1 && j == 0) + dp[i + 1][p][pp]);
            }
            // cout << i << " " << j << " " << k << " " << dp[i][j][k] << " " << num << endl;
        }
    }
    cout << dp[0][0][0] << "\n";    
}

int main() {
    sui;
    int tc = 1;
    //cin >> tc;
    for (int t = 1; t <= tc; t++) {
        solve();
    }
}

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