| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1013929 | vjudge1 | Lamps (JOI19_lamps) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pll pair<long long, long long>
#define pb push_back
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
s
const ll N = 1e6 + 100;
const ll inf = 1e18;
const ll mod = 1e9 + 7;
const ll block = 450;
ll n;
ll a[N], b[N], dp[N][3]; // 0 la dang thuc hien operation 0, 1 la dang thuc hien operation 1, 2 la khong lam j
void to_thic_cau(){
cin >> n;
for(int i = 1; i <= n;i++){
char c; cin >> c;
a[i] = c - '0';
}
for(int i = 1; i <= n;i++){
char c; cin >> c;
b[i] = c - '0';
}
for(int i = 0; i <= n;i++) dp[i][0] = dp[i][1] = dp[i][2] = inf;
dp[1][0] = (b[1] == 1) + 1, dp[1][1] = (b[1] == 0) + 1, dp[1][2] = (a[1] != b[1]);
for(int i = 2; i <= n;i++){
// xet TH thuc hien operation 0
dp[i][0] = min(dp[i][0], dp[i-1][0] + (b[i] == 1 && b[i-1] == 0));
dp[i][0] = min(dp[i][0], dp[i-1][1] + (b[i] == 1 && b[i-1] == 1) + 1);
dp[i][0] = min(dp[i][0], dp[i-1][2] + (b[i] == 1 && a[i-1] == b[i-1]) + 1);
// xet TH thuc hien operation 1
dp[i][1] = min(dp[i][1], dp[i-1][0] + (b[i] == 0 && b[i-1] == 0) + 1);
dp[i][1] = min(dp[i][1], dp[i-1][1] + (b[i] == 0 && b[i-1] == 1));
dp[i][1] = min(dp[i][1], dp[i-1][2] + (b[i] == 0 && a[i-1] == b[i-1]) + 1);
// xet TH khong thuc hien j
dp[i][2] = min(dp[i][2], dp[i-1][0] + (a[i] != b[i] && b[i-1] == 0));
dp[i][2] = min(dp[i][2], dp[i-1][1] + (a[i] != b[i] && b[i-1] == 1));
dp[i][2] = min(dp[i][2], dp[i-1][2] + (a[i] != b[i] && a[i-1] == b[i-1]));
}
cout << min({dp[n][0], dp[n][1], dp[n][2]}) << "\n";
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
ll tc = 1;
//cin >> tc;
while(tc--) to_thic_cau();
}