fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. const int Dx[] = {1, -1, 0, 0};
  4. const int Dy[] = {0, 0, 1, -1};
  5. #define all(x) x.begin(),x.end()
  6. #define fi first 
  7. #define se second
  8. const int N = 4e5 + 5, base = 300;
  9. int n, nextp[N][37], ans = 1e9;
  10. long long s[N], k;
  11. int main()
  12. {   
  13.     if(fopen("vd.inp", "r")){
  14.         freopen("vd.inp", "r", stdin);
  15.         freopen("vd.out", "w", stdout);        
  16.     }
  17.     ios_base::sync_with_stdio(0);   
  18.     cin.tie(0); cout.tie(0);
  19.     cin >> n >> k;
  20.     int len = n;
  21.     for(int i = 1; i <= n; i++) {
  22.         cin >> s[i];
  23.         s[i + n] = s[i];
  24.     }
  25.     n *= 2;
  26.     for(int i = 1; i <= n; i++)
  27.         s[i] += s[i - 1];
  28.     for(int i = 1; i <= n; i++) {
  29.         nextp[i][0] = upper_bound(s + 1, s + n + 1, s[i - 1] + k) - s;
  30.     }
  31.     for(int i = 1; i <= 20; i++) 
  32.         for(int j = 1; j <= n; j++)
  33.             nextp[j][i] = nextp[nextp[j][i - 1]][i - 1];
  34.  
  35.     for(int i = 1; i <= len; i++) {
  36.         int x = i, d = 0;
  37.         for(int j = 20; j >= 0; j--) {
  38.             if(nextp[x][j] && nextp[x][j] <= i + len - 1) {
  39.                 x = nextp[x][j];
  40.                 d += (1 << j);
  41.             }
  42.         }
  43.         ans = min(ans, d + 1);
  44.     }
  45.     cout << ans;
  46.     return 0;    
  47. }
Success #stdin #stdout 0s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1000000000
https://ideone.com/442DkR
language:
C++14 (clang 8.0)
created:
15 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!