Submission #256289

#TimeUsernameProblemLanguageResultExecution timeMemory
256289amoo_safarVim (BOI13_vim)C++17
50 / 100
5 ms2816 KiB
// Zende bad Shoma nasime faghat ! #include <bits/stdc++.h> #define pb push_back #define F first #define S second #define all(x) x.begin(), x.end() #define debug(x) cerr << #x << " : " << x << '\n' using namespace std; typedef long long ll; typedef long double ld; typedef string str; typedef pair<ll, ll> pll; const ll Mod = 1000000007LL; const int N = 5e2 + 10; const int Inf = 1e9; const ll Log = 30; str s; int dp[N][N]; int nx[N][12], nxe[N], ps[N], ps2[N]; int main(){ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n >> s; memset(nx, -1, sizeof nx); nxe[n - 1] = n - 1; for(int i = n - 2; i >= 0; i--){ for(int j = 0; j < 10; j++) nx[i][j] = nx[i + 1][j]; nx[i][s[i + 1] - 'a'] = i + 1; nxe[i] = (s[i] == 'e' ? nxe[i + 1] : i); } vector<int> E; ps2[0] = 1; for(int i = 1; i < n; i++){ if(s[i] == 'e') E.pb(i); ps[i] = ps[i - 1] + (s[i] == 'e' ? 1 : 0); ps2[i] = ps2[i - 1] + (s[i] == 'e' ? 0 : 1); } int ce = E.size(); memset(dp, 31, sizeof dp); dp[0][0] = 0; for(int j = 0; j < ce; j++){ for(int i = 0; i < n; i++){ if(s[i] == 'e') continue; for(int c = 0; c < 10; c++){ if(nx[i][c] != -1) dp[nx[i][c]][j] = min(dp[nx[i][c]][j], dp[i][j] + 2); } if(E[j] < i){ dp[ nxe[E[j]] ][ps[i]] = min(dp[ nxe[E[j]] ][ps[i]], dp[i][j] + ps2[i] - ps2[nxe[E[j]]]); } } } int ans = Inf; for(int i = 0; i < n; i++){ ans = min(ans, dp[i][ce] + ce + ce); } //debug(dp[3][2]); //debug(nx[3][5]); //debug(dp[9][2]); cout << ans << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...