Untitled
unknown
c_cpp
a month ago
925 B
3
Indexable
Never
int dp[N]; // N = 200200 though max n is 1000 vector<int> steps = {1, 3, 5}; int solve(int idx, int n, string &s) { if (idx > n) { return -1e9; } if (idx == n) { return 0; } if (dp[idx] != -1) { return dp[idx]; } int curr = (s[idx] == '"'), mxg = -1e9; // going forward for (auto x : steps) { if (x + idx <= n && (s[idx + x] != 'w')) { mxg = max(mxg, solve(idx + x, n, s)); } } if (mxg == -1e9) return dp[idx] = -1; // cant go forward return dp[idx] = curr + mxg; } signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); std::freopen("lepus.in", "r", stdin); std::freopen("lepus.out", "w", stdout); memset(dp, -1, sizeof(dp)); int n; cin >> n; string s; cin >> s; s = '#' + s; int ans = solve(1, n, s); cout << ((ans < 0) ? -1 : ans) << endl; return 0; }
Leave a Comment