Submission #1003851

#TimeUsernameProblemLanguageResultExecution timeMemory
1003851HanksburgerLamps (JOI19_lamps)C++17
4 / 100
20 ms27996 KiB
#include <bits/stdc++.h> using namespace std; int dp[1000005], min1[1000005], min2[1000005], num1[1000005], num2[1000005], ind[1000005]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; string s, t; cin >> n >> s >> t; s.insert(s.begin(), 0); t.insert(t.begin(), 0); s.insert(s.end(), 0); t.insert(t.end(), 0); for (int i=1; i<=n; i++) { num1[i]=(t[i]==t[i+1]?num1[i-1]:num1[i-1]+1); num2[i]=(t[i]==t[i-1]?num2[i-1]:num2[i-1]+1); ind[i]=(s[i]==t[i]?i:ind[i-1]); if (num2[i]&1) dp[i]=min1[i-1]+num2[i]/2+1; else dp[i]=min2[i-1]+num2[i]/2+1; dp[i]=min(dp[i], dp[ind[i]]+1); if (s[i]==t[i]) dp[i]=min(dp[i], dp[i-1]); min1[i]=min(min1[i-1], dp[i]-num1[i]/2); min2[i]=min(min2[i-1], dp[i]-(num1[i]+1)/2); } cout << dp[n]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...