Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## 果然！！！

Posted by wccy at 2012-10-06 10:44:30 on Problem 3017
In Reply To:注意此题如果写成多case会wa～～ Posted by:celia01 at 2012-08-20 14:55:49
```> #include<iostream>
> #include<cstdio>
> #include<cmath>
> #include<algorithm>
> #include<cstring>
> #include<set>
> #define see(x) cout<<#x<<":"<<x<<endl;
> using namespace std;
> const int maxn = 100005;
> long long dp[maxn], a[maxn];
> int q[maxn];
> multiset<long long> Set;
> int main(){
>     int n, i, j, k, low, ok, l, r;
>     long long sum, m, tmp;
>     while(scanf("%d%lld",&n,&m)!=-1){//这里写成多case就wa了，去掉之后就A了，无语了
>         sum = 0; low = 1;
>         l = 0; r = -1;
>         Set.clear();
>         dp[0] = 0; ok = 1;
>         for(i=1;i<=n;i++){
>             scanf("%lld",&a[i]);
>             sum += a[i];
>             while(sum>m) sum -= a[low++];
>             if(low>i){
>                 ok = 0;break;
>             }
>             while(l<=r&&a[i]>=a[q[r]]){
>                 if(l<r)
>                     Set.erase(dp[q[r-1]]+a[q[r]]);
>                 r--;
>             }
>             q[++r] = i;
>             if(l<r) Set.insert(dp[q[r-1]]+a[q[r]]);
>             while(low>q[l]){
>                 if(l<r)
>                     Set.erase(dp[q[l]]+a[q[l+1]]);
>                 l++;
>             }
>             tmp = *(Set.begin());
>             dp[i] = dp[low-1]+a[q[l]];
>             if(l<r&&dp[i]>tmp) dp[i] = tmp;
>         }
>         if(ok){
>             printf("%lld\n",dp[n]);
>         }
>         else{
>             printf("-1\n");
>         }
>     }
>     return 0;
> }
```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator