fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define sc              scanf
  4. #define pr              printf
  5. #define mx              20009          //====[10^6]====
  6. #define PI              acos(-1.0)
  7. #define pb              push_back
  8. #define ll              long long
  9. #define NN              100000000        //===[10^8]====
  10. #define pll             pair<ll,ll>
  11. #define pii             pair<int,int>
  12. #define uu              first
  13. #define vv              second
  14. #define INF             1<<29
  15.  
  16. #define readInt(a)      sc("%d",&a)
  17. #define readChar(a)     sc("%c",&a)
  18. #define readString(a)   sc("%s",&a)
  19. #define readLong(a)     sc("%lld",&a)
  20.  
  21. #define FOR(i,a,b)      for(i=a;i<=b;i++)
  22. #define ROF(i,a,b)      for(i=a;i>=b;i--)
  23. #define readLong2(a,b)  sc("%lld %lld",&a,&b)
  24.  
  25. ///     cout<<"Case "<<++cs<<":";
  26.  
  27. ///==============[ Global Variables & Declared Functions Here ]================
  28. //struct Info{
  29. //    int i;
  30. //    int j;
  31. //    int sum;
  32. //};
  33. //
  34. //Info max_con_sum(int *arr,int sz){
  35. //    Info ans;
  36. //    int mx_so_far,mx_cur,st,ed,i;
  37. //    mx_so_far=-INF;
  38. //    ans.sum=-INF;
  39. //    mx_cur=0;
  40. //    st=1;
  41. //
  42. //    FOR(i,1,sz){
  43. //
  44. //        if(mx_cur<0){
  45. //            st=i;
  46. //            mx_cur=0;
  47. //        }
  48. //        mx_cur += arr[i];
  49. //
  50. //        if(mx_cur<0){
  51. //
  52. //        }
  53. //        else if(mx_cur>mx_so_far){
  54. //            mx_so_far=mx_cur;
  55. //
  56. //            ans.sum=mx_so_far;
  57. //            ans.i=st;
  58. //            ans.j=i;
  59. //
  60. //        }
  61. //        else if(mx_cur==mx_so_far){
  62. //
  63. //            if((ans.j-ans.i)<(i-st)){
  64. //                ans.i=st;
  65. //                ans.j=i;
  66. //            }
  67. //        }
  68. //    }
  69. //
  70. //    return ans;
  71. //
  72. //}
  73. ///======================[ Main ]===================================
  74. int main()
  75. {
  76.     std::ios_base::sync_with_stdio(false);
  77.     int tc,n,i,h,cs=0;
  78.     int best_sum,best_start,best_end,cur_sum,val,cur_index;
  79.     int stop;
  80.     int arr[mx];
  81.  
  82.     cin>>tc;
  83.     while(tc--){
  84.         cin>>stop;
  85.         FOR(i,1,stop-1)     cin>>arr[i];
  86.  
  87.  
  88.         best_sum=-INF;
  89.         cur_sum=0;
  90.         best_start=-1;
  91.         best_end=-1;
  92.         cur_index=1;
  93.         arr[0]=-8;
  94.  
  95.         FOR(i,1,stop-1){
  96.             val = cur_sum+arr[i];
  97.             if(val>0){
  98.                 if(cur_sum==0 and arr[i-1]<0)      cur_index=i;
  99.                 cur_sum=val;
  100.             }
  101.             if(val>best_sum){
  102.                 best_sum=val;
  103.                 best_start=cur_index;
  104.                 best_end=i;
  105.             }
  106.             else if(val==best_sum){
  107.                 if((best_end-best_start)<(i-cur_index)){
  108.                     best_end=i;
  109.                     best_start=cur_index;
  110.                 }
  111.             }
  112.  
  113.             if(val<0)  cur_sum=0;
  114.         }
  115.  
  116.         if(best_sum>0)
  117.             cout<<"The nicest part of route "<<++cs<<" is between stops "<<best_start<<" and "<<best_end+1<<"\n";
  118.         else
  119.             cout<<"Route "<<++cs<<" has no nice parts\n";
  120.  
  121.  
  122.     }
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0s 2864KB
comments (?)
stdin
copy 
1
4
3 -3 4
stdout
copy 
The nicest part of route 1 is between stops 1 and 9
https://ideone.com/OOxD9k
Max 1D Sum UVa 507 Jill Rides again
language:
C++ 4.3.2 (gcc-4.3.2)
created:
8 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!