fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define bye return
  5. #define yes "YES"
  6. #define no "NO"
  7. #include <ext/pb_ds/assoc_container.hpp>
  8. #include <ext/pb_ds/tree_policy.hpp>
  9. using namespace __gnu_pbds;
  10. #define Shoyo ios_base::sync_with_stdio(0);cin.tie(NULL);
  11. #define ff first
  12. #define ss second
  13. #define pii pair<ll,ll>
  14. #define all(v) v.begin(), v.end()
  15. #define allr(v) v.rbegin(), v.rend()
  16. #define cl(x,y)  (x + y - 1) / y
  17. #define el "\n"
  18. #define os tree<ll, null_type, less<>, \
  19. rb_tree_tag, tree_order_statistics_node_update>
  20. ll MOD = 1e9+7;
  21. const ll N=1e5+10;
  22. const ll INF = 1e17;
  23. const ll Log=20;
  24. ll n,c,mx;
  25. vector<ll> v;
  26. bool can(ll mid) {
  27.     if (mid*n>mx)return false;
  28.     ll x=c;
  29.     for (ll i=0;i<(n+n);i++) {
  30.         x+=v[i%n]-mid;
  31.         x=min(x,c);
  32.         if(x<0)return false;
  33.     }
  34.     return true;
  35. }
  36. void solve() {
  37.     cin>>n>>c;
  38.     v.assign(n,0);
  39.     for(ll i=0;i<n;i++)cin>>v[i];
  40.     mx=accumulate(all(v),ll(0));
  41.     ll l=0,r=2e9,ans=0;
  42.     while(l<=r) {
  43.         ll mid=(l+r)>>1;
  44.         if (can(mid)) {
  45.             ans=mid;
  46.             l=mid+1;
  47.         }else r=mid-1;
  48.     }
  49.     cout<<ans<<endl;
  50. }
  51. int main(){
  52.     Shoyo;
  53.     ll t = 1;
  54.     if(!(cin >> t)) return 0;
  55.     while (t--) {
  56.         solve();
  57.     }
  58.     return 0;
  59. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/W9fAgH
language:
C++14 (gcc 8.3)
created:
3 hours 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!