Submission #1003818

#TimeUsernameProblemLanguageResultExecution timeMemory
1003818HanksburgerLamps (JOI19_lamps)C++17
4 / 100
22 ms32164 KiB
#include <bits/stdc++.h> using namespace std; int dp[1000005], dp1[1000005], dp2[1000005], mindp1[1000005], mindp2[1000005], ind[1000005]; vector<int> vec; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, sz=0, state=0; cin >> n; string s, t; cin >> s >> t; vec.push_back(0); for (int i=0; i<n; i++) { if (i && t[i]!=t[i-1]) { sz++; vec.push_back(state); ind[sz]=(state==2?ind[sz-1]:sz); state=0; } if (state%2==0 && s[i]==t[i]) state++; else if (state<2 && s[i]!=t[i]) state+=2; } sz++; vec.push_back(state); ind[sz]=(state==2?ind[sz-1]:sz); for (int i=1; i<=sz; i++) { if (i&1) dp[i]=mindp1[i-1]+i/2+1; else dp[i]=mindp2[i-1]+i/2+1; dp[i]=min(dp[i], dp[ind[i]]+(i-ind[i])/2+1); if (vec[i]==1) dp[i]=min(dp[i], dp[i-1]); dp1[i]=dp[i]-i/2; dp2[i]=dp[i]-(i+1)/2; mindp1[i]=min(mindp1[i-1], dp1[i]); mindp2[i]=min(mindp2[i-1], dp2[i]); } cout << dp[sz]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...