fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define LOG 20
  4. #define MASK(i) (1LL<<(i))
  5. #define BIT(x,i) (((x)>>(i))&1)
  6. #define FIRST_BIT(mask) __builtin_ctz((mask)&(-mask))
  7. #define ERASE_BIT(mask) (mask)^((mask)&(-mask))
  8. #define left _left
  9. #define right _right
  10. #define task "t"
  11. #define int long long
  12. using namespace std;
  13. const ll INF=1e18;
  14. const int iat=1e5+9;
  15. const int mod=1e9+7;
  16. void fast_IO()
  17. {
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(0);
  20.     cout.tie(0);
  21.     if(fopen(task".inp","r"))
  22.     {
  23.         freopen(task".inp","r",stdin);
  24.         freopen(task".out","w",stdout);
  25.     }
  26. }
  27. int n,d,a[iat],pre[iat],maxi[iat];
  28. signed main()
  29. {
  30.     fast_IO();
  31.     cin>>n>>d;
  32.     for(int i=1; i<=n; i++)cin>>a[i],pre[i]=pre[i-1]+a[i];
  33.     maxi[n]=pre[n];
  34.     for(int i=n-1; i>=1; i--)maxi[i]=max(maxi[i+1],pre[i]);
  35.     int add=0,sum=0,ans=0;
  36.     for(int i=1; i<=n; i++)
  37.     {
  38.         if(a[i]!=0)
  39.         {
  40.             sum+=a[i];
  41.             if(sum>d)
  42.             {
  43.                 cout<<-1;
  44.                 return 0;
  45.             }
  46.         }
  47.         else if(sum<0)
  48.         {
  49.             if(i==n)
  50.             {
  51.                 ans++;
  52.                 break;
  53.             }
  54.             int tmp=d-(maxi[i+1]+add); /// so tien lon nhat ma ta co the them vao de nhung lan cong sau thoa man
  55.             if(sum+tmp<0)
  56.             {
  57.                 cout<<-1;
  58.                 return 0;
  59.             }
  60.             int temp=min((d-sum),tmp);
  61.             sum+=temp;
  62.             add+=temp;
  63.             ans++;
  64.         }
  65.     }
  66.     cout<<ans;
  67. }
  68.  
Success #stdin #stdout 0.01s 5300KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/3VgXTh
language:
C++14 (gcc 8.3)
created:
20 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!