Codeforce)Edu33_D_Creditcard

The problem in short : 

* 저녁에는 돈을 입금하거나 ( ai < 0 ), 돈을 출금하거나 ( ai > 0) , 돈이 얼마있는지 확인( ai == 0) 을 한다.

* 단  통장에는 항상  d 보다 작거나 같은 돈이 들어있어야 하고,

*  돈을 확인할때 0이상의 돈이 존재해야 한다.

따라서 아침에 은행을 방문하는 횟수를 최소로할 때 방문횟수를 출력하자, ( 불가능하면  -1) 

The solution : 

* 은행 방문 횟수를 최소로 하기 위해서는 돈을 넣을 수 있는 한 많이 넣어야한다.

* 하지만 넣을 수 있는 한도는 뒤에 있는 입금을 고려할 떄 d를 초과하지 않아야 한다.

* 이렇게 넣는게 optimal 한가?

* 귀류법 ) 돈을 이거보다 적게 넣는다고 가정했을 때 -> 전혀 이득 볼 게 없다. 어차피 넘칠 일 은 없고, 나중에 은행 갈 횟수를 늘리게 될뿐

* 돈을 확인하는 날의 아침에 0이상이라면 은행을 가지않고, 0보다 작다면 최대한 넣을 수 있는만큼 많이 넣는다.

* 불가능 한날은? 현재 내 잔고가 음수라서 돈을 넣어야 하는데 뒤에서 넘칠 까봐 돈을 넣을 수 없는 상황이라면.

1) 넣을 수 있는 최댓값을 계산한다.

2) 이 최댓값이 음수라면 돈을 넣을 수 없는 상황이므로 불가능

3) 돈을 넣었는데에도 음수라면 불가능

* 아예 0 이 등장하지 않을 수 도 있으므로 잘 처리해줄 것

The code : 

#include <cstdio>
#include <algorithm>
 
using namespace std;
typedef long long ll;
ll n,d;
ll a[101000];
ll sum[101000];
ll maxifromend[101000];
int main(){
freopen("input.txt","r",stdin);
scanf("%lld %lld",&n,&d);
for(int i = 1 ; i <= n ; i++){
    scanf("%lld",&a[i]);
}
 
for(int i = 1; i <= n ; i++){
    sum[i] = sum[i-1] + a[i];
}
ll maxi = -10000000000;
for(int i = n ; i >=1; i--){
    maxi = max(maxi,sum[i]);
    maxifromend[i] = maxi - sum[i-1];
}
 
if(maxi > d){
    printf("-1");
    return 0;
}
ll curr = 0;
int cnt = 0;
bool flag = 1;
for(int i = 1; i <= n ; i++){
    if(a[i] == 0){
        if(curr >= 0){
            continue;
        }
        else{
 
            int deposit = d - maxifromend[i] - curr;
            if(deposit < 0){
                flag = 0;
                break;
            }
            if(deposit + curr < 0 )
            {
                flag = 0;
                break;
            }
            else{
                curr += deposit;
                cnt++;
            }
        }
    }
    else{
        curr += a[i];    
        if(curr > d){
            flag = 0;
            break;
        }
    }
}
 
if(flag)
printf("%d",cnt);
else
puts("-1");
 
 
 
}

The feedback : 

1.  조건을 하나하나 잘 따지기

2. 나올 수 있는 범위 미리 잘 파악하기. ( maxi 값을 0부터 잡아버리는 실수 때문에 시간잡아먹음)