Submission #1003846

#TimeUsernameProblemLanguageResultExecution timeMemory
1003846HanksburgerLamps (JOI19_lamps)C++17
0 / 100
0 ms348 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; 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...