Saleh127

UVA 507

Jun 1st, 2021
235
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.11 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5. int main()
  6. {
  7. ios_base::sync_with_stdio(0);
  8. cin.tie(0);cout.tie(0);
  9.  
  10. test
  11. {
  12.  
  13.  
  14. ll n,m=0,i,j,k,l=0;
  15.  
  16. cin>>n;
  17.  
  18. ll a[n+4];
  19.  
  20. ll st=0,en=0,cur=1,ans=INT_MIN;
  21.  
  22. for(i=2;i<=n;i++) cin>>a[i];
  23.  
  24. for(i=2;i<=n;i++)
  25. {
  26. m+=a[i];
  27.  
  28. if(m<0)
  29. {
  30. cur=i;
  31. m=0;
  32. }
  33. else if(m>ans)
  34. {
  35. ans=m;
  36. st=cur;
  37. en=i;
  38. l=en-st;
  39. }
  40. else if(m==ans && (i-cur>l))
  41. {
  42. ans=m;
  43. st=cur;
  44. en=i;
  45. l=en-st;
  46. }
  47. }
  48.  
  49. if(ans<=0) cout<<"Route "<<cs<<" has no nice parts"<<endl;
  50. else
  51. {
  52. cout<<"The nicest part of route "<<cs<<" is between stops "<<st<<" and "<<en<<endl;
  53. }
  54. }
  55.  
  56. return 0;
  57. }
  58.  
Advertisement
Add Comment
Please, Sign In to add comment