fork download
copy 
  1. #include<cstdio>
  2. using namespace std;
  3. void find_sum(int n,long long int arr[],int c)
  4. {
  5.     int i,j,k,len,a,b;
  6.     long long int sum[n+1][n+1],maxlen;
  7.     maxlen=-1;
  8.     for(i=1;i<n;i++)
  9.     {
  10.         sum[i][i+1]=arr[i];
  11.         if(arr[i]>maxlen)
  12.         {
  13.             maxlen=arr[i];
  14.             a=i;
  15.             b=i+1;
  16.         }
  17.        // printf("%d %d %d\n",i,i+1,sum[i][i+1]);
  18.     }
  19.     for(len=2;len<n;len++)
  20.     {
  21.         for(i=1;i<n-len+1;i++)
  22.         {
  23.             j=i+len;
  24.             k=len/2;
  25.             sum[i][j]=sum[i][j-k]+sum[j-k][j];
  26.             //printf("%d %d %d\n",i,j,sum[i][j]);
  27.             if(sum[i][j]>maxlen)
  28.             {
  29.                 maxlen=sum[i][j];
  30.                 a=i;
  31.                 b=j;
  32.             }
  33.             else if(sum[i][j]==maxlen)
  34.             {
  35.                 if((b-a)<(j-i))
  36.                 {
  37.                     b=j;
  38.                     a=i;
  39.                 }
  40.             }
  41.         }
  42.     }
  43.     if(maxlen>=0)
  44.         printf("The nicest part of route %d is between stops %d and %d\n",c,a,b);
  45.     else
  46.         printf("Route %d has no nice parts\n",c);
  47. }
  48. int main()
  49. {
  50.     int r,s,i,j;
  51.     long long arr[21000];
  52.     scanf("%d",&r);
  53.     for(i=1;i<=r;i++)
  54.     {
  55.         scanf("%d",&s);
  56.         for(j=1;j<s;j++)
  57.             scanf("%d",&arr[j]);
  58.         find_sum(s,arr,i);
  59.     }
  60.     return 0;
  61. }
Success #stdin #stdout 0s 3388KB
comments (?)
stdin
copy 
3
3
  -1
   6
10
   4
  -5
   4
  -3
   4
   4
  -4
   4
  -5
4
  -2
  -3
  -4
stdout
copy 
The nicest part of route 1 is between stops 1 and 3
The nicest part of route 2 is between stops 1 and 10
The nicest part of route 3 is between stops 1 and 4
https://ideone.com/FZxOoP
language:
C++14 (gcc 8.3)
created:
9 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!