Submission #631929

#TimeUsernameProblemLanguageResultExecution timeMemory
631929radalLamps (JOI19_lamps)C++17
0 / 100
7 ms4476 KiB
#include <bits/stdc++.h> #define rep(i,l,r) for (int i = l; i < r; i++) #define repr(i,r,l) for (int i = r; i >= l; i--) #define pb push_back #define X first #define Y second #define debug(x) cerr << #x << " : " << x << endl; #define all(x) x.begin() , x.end() using namespace std; typedef pair<int,int> pll; typedef long long ll; constexpr int N = 2e3+10; int dp[N],a[N][3],pd[N][N][3]; int main(){ ios_base :: sync_with_stdio(0); cin.tie(0); int n; cin >> n; string s,t; cin >> s >> t; s = '#'+s; t = '#'+t; rep(i,1,n+1){ if (t[i] == '1') a[i][1] = 1+a[i-1][1]; else a[i][0] = 1+a[i-1][0]; if (s[i] == t[i]) a[i][2] = 1+a[i-1][2]; } repr(l,n,1){ rep(r,l,n+1){ if (t[r] == '1'){ pd[l][r][1] = pd[l][r-1][1]; if (a[r][1] >= r-l+1){ pd[l][r][0] = 1; continue; } pd[l][r][0] = pd[l][r-a[r][1]][0]+1; } else{ pd[l][r][0] = pd[l][r-1][0]; if (a[r][0] >= r-l+1){ pd[l][r][1] = 1; continue; } pd[l][r][1] = pd[l][r-a[r][0]][1]+1; } } rep(r,l,n+1){ if (s[r] != t[r]){ pd[l][r][2] = pd[l][r-1][2]; continue; } pd[l][r][2] = pd[l][r-1][2]+1; rep(m,l,r+1){ pd[l][r][2] = min(pd[l][r][2],1+min(pd[m][r][0],pd[m][r][1])+pd[l][m-1][2]); } } } rep(i,1,n+1){ if (s[i] == t[i]){ dp[i] = dp[i-1]; continue; } dp[i] = 1+dp[i-1]; bool fl = 1; repr(j,i-1,1){ fl &= (s[j] != t[j]); dp[i] = min(dp[i],dp[j-1]+min({pd[j][i][0],pd[j][i][1],pd[j][i][2]})+1); } } cout << dp[n] << endl; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...