Problem in 5C

Revision en2, by ContestFucker, 2019-06-18 09:05:25

Hi, I have used the same logic as editorial in problem 5C but my code gets the wrong answer. https://codeforces.com/contest/5/problem/C

#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6;
int dp[MAXN];

int main()
{
    string str;cin >> str;
    stack<int> s;int maxs=0,su0;
    for(int i=0;i<str.size();++i){
        if(str[i]=='('){
            s.push(i);dp[i]=-1;
        }else{
            if(s.empty()) dp[i]=-1;
            else{
                int top = s.top();int res = i-top+1;
                if(top!=0 && str[top-1]==')' && dp[top-1]!=-1) res += dp[top-1];
                dp[i]=res;maxs=max(maxs,dp[i]);
            }
        }
    }cout << maxs;
}
Tags #problem c, #dynamic programing, #greedy, #stack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English ContestFucker 2019-06-18 09:05:25 20
en1 English ContestFucker 2019-06-18 09:05:05 718 Initial revision (published)