507 - Jill Rides Again

[brianfry713]

Input:

Code: Select all

1
11
   1
   1
   1
-100
   2
   2
-100
   1
   1
   1

AC output:

Code: Select all

The nicest part of route 1 is between stops 5 and 7

[moxlotus]

10

6
1
0
0
0
1


6
1
0
0
1
-1

6
0
0
0
0
0

10
4
-5
4
-3
4
4
-4
4
-5

10
4
-5
4
-3
4
4
-4
4
5

6
-1
1
-1
1
-1

6
1
-1
1
-1
1

11
1
-1
1
-1
1
-1
1
-1
1
-1

12
1
-1
1
-1
1
-1
1
-1
1
-1
1

7
1
-1
1
-100
1
-1
1

AC Output:
The nicest part of route 1 is between stops 1 and 6
The nicest part of route 2 is between stops 1 and 5
The nicest part of route 3 is between stops 1 and 6
The nicest part of route 4 is between stops 3 and 9
The nicest part of route 5 is between stops 3 and 10
The nicest part of route 6 is between stops 2 and 5
The nicest part of route 7 is between stops 1 and 6
The nicest part of route 8 is between stops 1 and 10
The nicest part of route 9 is between stops 1 and 12
The nicest part of route 10 is between stops 1 and 4

[d3nd0h]

hi, I am getting TLE within this code for Jill rides again, anyone could help me?

Code: Select all

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<string>
#include<utility>
#include<algorithm>
using namespace std;

int main(){
	int tc,stop,nice[20000],maxi,maxj,max;
	scanf("%d",&tc);
	for(int x=0;x<tc;x++){
		nice[0]=0;max=-10000000;
		scanf("%d",&stop);
		for(int i=1;i<stop;i++){
			int dum;
			scanf("%d",&dum);
			nice[i]=nice[i-1]+dum;
		}
		for(int i=1;i<stop;i++){
			for(int j=i-1;j>=0;j--){
				if(max<nice[i]-nice[j] || (max==nice[i]-nice[j]&&maxi-maxj<i-j)){
					maxi=i+1;
					maxj=j+1;
					max=nice[i]-nice[j];
				}
			}
		}
		if(max<0)printf("Route %d has no nice parts\n",x+1);
		else printf("The nicest part of route %d is between stops %d and %d\n",x+1,maxj,maxi);
	}	
	return 0;
}

[brianfry713]

You can solve each route in O(s) using DP.

[d3nd0h]

I though that I've used DP, so I am not?

[brianfry713]

Your code takes O(s * s) and s can be as large as 20,000.

[d3nd0h]

Well thanks, I just realized that, I guess I still need more practice for DP, thx:)

[Turbat]

Can anyone help me to find test case on which following code fails?

#include<iostream>
#include<cstdio>
#include<algorithm>

using namespace std;

int a[30200],s[30200]={0};

int main(){


int t,r,maxx,minn,maxind,minind1,minind2,i,l=0,nice,k=1;
cin>>t;
while(t--){
scanf("%d", &r);
for(i=1;i<r;i++){
scanf("%d", &a);
s=a+s[i-1];
}
nice=0;
if(s[1]>=s[0]){
minn=s[0];
minind1=minind2=0;
maxind=1;
nice=s[1]-s[0];
l=1;
}
else{
minn=s[1];
minind1=minind2=1;
maxind=1;
}
for(i=2;i<r;i++){
if(s<minn){
minn=s;
minind2=i;
continue;
}
if(s-minn==nice && i-minind2>l){
maxind=i;
l=i-minind2;
minind1=minind2;
continue;
}
if(s-minn>nice ){
nice=s-minn;
maxind=i;
l=i-minind2;
minind1=minind2;
}
}
if(nice<=0) printf("Route %d has no nice parts\n", k);
else printf("The nicest part of route %d is between stops %d and %d\n", k, minind1+1, maxind+1);
k++;
l=0;
}
return 0;
}

[brianfry713]

That is AC code.

[Titanswords]

can anyone could help me???
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
/////////
const int MAXN=80010;
int a[MAXN];
int dp[MAXN];//dp???i???????
int m,sum,ans;
int cases;
int main(){
cases=0;
while(scanf("%d",&m)&&m!=0){

while(m--){
cases++;
int n;
cin>>n;
for(int i=0;i<n-1;i++){
scanf("%d",&a);//????
}
ans=0;
int min[MAXN],max[MAXN];
memset(min,0,sizeof(min));
memset(max,0,sizeof(max));
dp[0]=a[0];
max[0]=2;
min[0]=1;
int minn;
for(int i=1;i<n-1;i++){//????dp??
max=i+2;
if(dp[i-1]>0){
dp=dp[i-1]+a;
}
else{
dp=a;
minn=i+1;
}
min=minn;
}
int large=dp[0];
int temp;
for(int i=1;i<n-1;i++){
if(dp>=dp[i-1]){
large=dp;
temp=i;
}
}
//cout<<temp;
if(large<0){
printf("Route %d has no nice parts\n",cases);
}
else{
//cout<<large<<endl;
printf("The nicest part of route %d is between stops %d and %d\n",cases,min[temp],max[temp]);
}
}
}
return 0;
}

[brianfry713]

The first line of the file is a single integer b representing the number of route descriptions in the file.
You should only read b once.

[richatibrewal]

I am getting run time error for this problem . Plz help. Here is my code

Code: Select all

#include<cstdio>
using namespace std;
void find_sum(int n,long long int arr[],int c)
{
    int i,j,k,len,a,b;
    long long int sum[n+1][n+1],maxlen;
    maxlen=-1;
    for(i=1;i<n;i++)
    {
        sum[i][i+1]=arr[i];
        if(arr[i]>maxlen)
        {
            maxlen=arr[i];
            a=i;
            b=i+1;
        }
       // printf("%d %d %d\n",i,i+1,sum[i][i+1]);
    }
    for(len=2;len<n;len++)
    {
        for(i=1;i<n-len+1;i++)
        {
            j=i+len;
            k=len/2;
            sum[i][j]=sum[i][j-k]+sum[j-k][j];
            //printf("%d %d %d\n",i,j,sum[i][j]);
            if(sum[i][j]>maxlen)
            {
                maxlen=sum[i][j];
                a=i;
                b=j;
            }
            else if(sum[i][j]==maxlen)
            {
                if((b-a)<(j-i))
                {
                    b=j;
                    a=i;
                }
            }
        }
    }
    if(maxlen>=0)
        printf("The nicest part of route %d is between stops %d and %d\n",c,a,b);
    else
        printf("Route %d has no nice parts\n",c);
}
int main()
{
    int r,s,i,j;
    long long arr[21000];
    scanf("%d",&r);
    for(i=1;i<=r;i++)
    {
        scanf("%d",&s);
        for(j=1;j<s;j++)
            scanf("%d",&arr[j]);
        find_sum(s,arr,i);
    }
    return 0;
}

[lighted]

Yes judge gives RE for your code, but it doesn't match sample I/O so try to fix bugs first.

[richatibrewal]

I have tried the output for all the sample input i could get and it is giving me the reqired output. If not , plz give me the input for which the output is wrong

[lighted]

Your code posted above doesn't match sample I/O. http://ideone.com/FZxOoP