Untitled

mail@pastecode.io avatar
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