fork(1) download
copy 
  1. #include <iostream>
  2. #include <sstream>
  3. #include <cstdio>
  4. #include <cmath>
  5. #include <cstring>
  6. #include <cctype>
  7. #include <string>
  8. #include <vector>
  9. #include <list>
  10. #include <set>
  11. #include <map>
  12. #include <unordered_map>
  13. #include <limits.h>
  14. #include <cassert>
  15. #include <queue>
  16. #include <stack>
  17. #include <algorithm>
  18. #include <functional>
  19. #include <iomanip>
  20. using namespace std;
  21. //////////////////
  22. // Aditya Kumar //
  23. //  BITS H      //
  24. //////////////////
  25.  
  26. #define mod 1000000007
  27. #define ll long long
  28. #define ss second
  29. #define ff first
  30. #define FastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  31. #define int long long
  32. #define pb push_back
  33.  
  34. int n , d; 
  35. int a[200040]; 
  36. int brute()
  37. {
  38.     int ans = 1e9;
  39.     for(int i=0;i<n;i++)
  40.     {
  41.         for(int j=i;j<n;j++)
  42.         {
  43.             int lol = 0;
  44.             int s=0;
  45.             for(int k=i;k<=j;k++)
  46.             {
  47.                 lol ++;
  48.                 s += a[k];
  49.             }
  50.             if(s >= d)
  51.                 ans = min(ans, (lol));
  52.         }
  53.     }
  54.     if(ans == 1e9) ans = -1;
  55.     return ans;
  56. }
  57.  
  58. int32_t main()
  59. {
  60.         FastIO;
  61.         #ifndef ONLINE_JUDGE
  62.         freopen("input.txt","r",stdin);    
  63.         freopen("output.txt","w",stdout);
  64.         #endif    
  65.         int tc ; cin >> tc; 
  66.         while(tc--)
  67.         {
  68.             cin >> n >> d;
  69.             for(int i=0;i<n;i++) {
  70.                 cin >> a[i];
  71.             }
  72.             int dne = 0;
  73.             for(int i=0;i<n;i++) {
  74.                     if(a[i] >= d) 
  75.                         {
  76.                             cout << 1 << endl;
  77.                             dne  = 1;
  78.                             break;
  79.                         }
  80.                 }
  81.                 if(dne == 1) {
  82.                     continue;
  83.                 }
  84.             if(d <= 0)
  85.             {                 
  86.                 cout << -1 << endl; 
  87.                 continue;
  88.             }
  89.             int ans = 200005;  
  90.             int cs = 0;
  91.             int l = 0 ; int r = -1;
  92.             while( r < n-1){
  93.                 while( cs < d && r < n-1)
  94.                 { 
  95.                     r++;
  96.                     cs += a[r];
  97.                     if(cs <= 0)
  98.                     {
  99.                         l = r+1;
  100.                         cs = 0;
  101.                     }
  102.                 }
  103.                 if(cs >= d)
  104.                  ans = min(ans, r-l+1);
  105.                 while( (cs >= d && l <= r) || (a[l] <= 0 && l <=r))
  106.                 {
  107.                     cs -= a[l];
  108.                     l++;    
  109.                     if(cs >=d ) ans = min(ans, r-l+1);
  110.                 }
  111.             }
  112.             if(ans == 200005) ans = -1;
  113.             // assert(ans == brute());
  114.             cout << ans << endl;
  115.         }
  116.         return 0;
  117.  
  118. }
Success #stdin #stdout 0s 4504KB
comments (?)
stdin
copy 
3
5 4
1 2 1 2 1
6 -2
-5 -6 -7 -8 -9 -10
5 3
-1 1 1 1 -1
stdout
copy 
3
-1
3
https://ideone.com/e8hV4M
language:
C++ 4.3.2 (gcc-4.3.2)
created:
6 years ago
visibility:
secret

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!