【思考】Codeforces 893 D CreditCard

一週間ぐらい経って、悔しくて(初のRATEDのERs)を打って、C問題は再び私の圧力の下で深く考えていない問題を暴露して、最悪のN方のアルゴリズムは明らかにタイムアウトして、この怠け者を盗むべきではありませんて、幸いにも評価して測定して、その夜機械は特に15分遅れたと言っていますが.
题意:この题意を久しぶりに见ました.全部でN日、口座のメモリは最大D元を入れて、毎晩残高は変動して、ある日口座が横ばいでお金の数が0未満であることを避けて、あるいは夜残高が変動した後に残高がDより大きいことを避けます.毎朝Dまで任意のお金を貯めることができます.
标题:毎朝貯金ができてDまで貯められるのでa[I]=0の日はお金が足りない心配はありませんが、心配するのはお金が多すぎてDを超えることです.そこで、接頭辞を計算し、お金を入れないと毎日口座にいくらあるかを計算し、1つの変数tmpでいくら加算されたかを記録します.o(n)のループを作って、まず現在のtmpに加えた後の最小の接頭辞とDを超えるかどうかを判断し、a[I]=0の点であれば、できるかどうかを判断し、できなければ加算できる最大の数を加える.

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const LL INF = (LL)1 << 62;

LL n, d;
LL a[100010];
LL s[100010];
LL top[100010];
LL mtop[100010];
LL ck[100010];

int main(){
    cin >> n >> d;
    for (int i = 1; i <= n; i++){
        scanf("%I64d", &a[i]);
        if (a[i] == 0) ck[i] = 1;
        s[i] = s[i - 1] + a[i];
        top[i] = d - s[i];
    }
    mtop[n + 1] = top[n];
    for (int i = n; i >= 1; i--){
        mtop[i] = min(mtop[i + 1], top[i]);
    }
    LL ans = 0; LL tmp = 0;
    for (int i = 1; i <= n; i++){
        if (s[i] + tmp > d){
            printf("-1
");
            return 0;
        }
        if (ck[i]){
            if (s[i] + tmp >= 0) continue;
            else{
                if (mtop[i] + s[i]>= 0){
                    tmp = max(tmp, mtop[i]);
                    ans++;
                }
                else{
                    puts("-1");
                    //system("pause");
                    return 0;
                }
            }
        }
    }
    printf("%d
", ans);
    //system("pause");
    return 0;
}