HDOJ -- 4699

Editor

Time Limit: 3000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 1236 Accepted Submission(s): 391

Problem Description

Sample Input

8 I 2 I -1 I 1 Q 3 L D R Q 2

Sample Output

2 3

Hint

The following diagram shows the status of sequence after each instruction:

一直wa，谁能告诉我哪错了！

 1 #include<stack>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define MAX 1000005
 5 using namespace std;
 6 stack<int>l, r;
 7 long long int dp[MAX], sum[MAX], n, temp;
 8 char str[5];
 9 int main(){
10     freopen("in.c", "r", stdin);
11     while(~scanf("%lld", &n)){
12         while(!l.empty()) l.pop();
13         while(!r.empty()) r.pop();
14         memset(sum, 0, sizeof(sum));
15         memset(dp, 0, sizeof(dp));
16         dp[0] = -100000000;
17         for(int i = 0;i < n;i ++){
18             scanf("%s", str);
19             if(str[0] == 'I'){
20                 scanf("%lld", &temp);
21                 l.push(temp);
22                 sum[l.size()] = sum[l.size()-1] + temp;
23                 dp[l.size()] = max(sum[l.size()], dp[l.size()-1]);
24             }else if(str[0] == 'L'){
25                 if(!l.empty()){
26                     int del = l.top();
27                     l.pop();
28                     r.push(del);
29                 }
30             }else if(str[0] == 'Q'){
31                 scanf("%lld", &temp);
32                 temp = min(temp, (long long int)l.size());
33                 l.size() == 0 ? printf("0
") : printf("%lld
", dp[temp]);
34             }else if(str[0] == 'D') l.pop();
35             else{
36                 if(!r.empty()){
37                     int del = r.top();
38                     r.pop();
39                     l.push(del);
40                     sum[l.size()] = sum[l.size()-1] + del;
41                     dp[l.size()] = max(sum[l.size()], dp[l.size()-1]);
42                 }
43             }
44         }
45     }
46 }