Submission #171319

#	Time	Username	Problem	Language	Result	Execution time	Memory
171319		gs18103	Lamps (JOI19_lamps)	C++14	0 / 100	2 ms	376 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[3][MAX];

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

    int n;
    string s, t;
    cin >> n >> s >> t;
    dp[0][0] = 1 + (t[0] == '1');
    dp[1][0] = 1 + (t[0] == '0');
    dp[2][0] = 0 + (s[0] != t[0]);
    for(int i = 1; i < n; i++) {
        bool b = (t[i] == '1');
        dp[0][i] = min(dp[0][i-1] + (b && t[i-1] == '0'), 
                dp[2][i-1] + 1 + (b && s[i-1] == t[i-1]));
        dp[1][i] = min(dp[1][i-1] + (!b && t[i-1] == '1'), 
                dp[2][i-1] + 1 + (!b && s[i-1] == t[i-1]));
        dp[2][i] = min({
            dp[0][i-1] + (s[i] != t[i] && t[i-1] == '0'), 
            dp[1][i-1] + (s[i] != t[i] && t[i-1] == '1'), 
            dp[2][i-1] + (s[i] != t[i] && t[i-1] == s[i-1])
        });
    }
    for(int i = 0; i < n; i++) {
        cout << dp[0][i] << ' ' << dp[1][i] << ' ' << dp[2][i] << endl;
    }
    cout << min({dp[0][n-1], dp[1][n-1], dp[2][n-1]});
}

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