Submission #1101259

#TimeUsernameProblemLanguageResultExecution timeMemory
1101259underwaterkillerwhaleLamps (JOI19_lamps)C++17
100 / 100
41 ms33952 KiB
//#include"holiday.h" #include <bits/stdc++.h> #define ll long long #define rep(i,m,n) for(int i=(m); i<=(n); i++) #define reb(i,m,n) for(int i=(m); i>=(n); i--) #define pii pair<int,int> #define pll pair<ll,ll> #define MP make_pair #define fs first #define se second #define bit(msk, i) ((msk >> i) & 1) #define iter(id, v) for(auto id : v) #define pb push_back #define SZ(v) (ll)v.size() #define ALL(v) v.begin(),v.end() using namespace std; mt19937_64 rd(chrono :: steady_clock :: now ().time_since_epoch().count()); ll Rand (ll l, ll r) { return uniform_int_distribution<ll> (l, r) (rd); } const int N = 1e6 + 7; int Mod = 1e9 + 7;///lon const int INF = 1e9; const ll BASE = 137; const int szBL = 450; int n; int a[N], b[N]; int dp[N][3][2]; void solution () { cin >> n; { string s; cin >> s; rep (i, 1, n) a[i] = s[i - 1] - '0'; } { string s; cin >> s; rep (i, 1, n) b[i] = s[i - 1] - '0'; } memset(dp, 0x3f, sizeof dp); dp[0][2][0] = 0; rep (i, 1, n) { rep (j, 0, 2) rep (k, 0, 1) { int bt = j == 2 ? a[i] ^ k : j ^ k; if (bt != b[i]) continue; rep (j2, 0, 2) rep (k2, 0, 1) { dp[i][j][k] = min(dp[i][j][k], dp[i - 1][j2][k2] + (j2 != j && j != 2) + (k2 != k && k != 0)); } } } int res = INF; rep (j, 0, 2) rep (k, 0, 1) res = min(res, dp[n][j][k]); cout << res <<"\n"; } #define file(name) freopen(name".inp","r",stdin); \ freopen(name".out","w",stdout); int main () { // file("c"); ios_base :: sync_with_stdio(false); cin.tie(0); cout.tie(0); int num_Test = 1; // cin >> num_Test; while (num_Test--) solution(); } /* no bug challenge +10 5 5 01101 10001 00110 10101 00100 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...