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

## 注意此题如果写成多case会wa～～

Posted by celia01 at 2012-08-20 14:55:49 on Problem 3017
```#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: