Page 6 of 7
Re: 507 - Jill Rides Again WA
Posted: Tue Oct 01, 2013 10:52 pm
by brianfry713
Input:
AC output:
Code: Select all
The nicest part of route 1 is between stops 5 and 7
Re: 507 - Jill rides again
Posted: Tue Oct 22, 2013 3:22 pm
by 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
507 TLE
Posted: Thu Nov 21, 2013 5:30 am
by 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;
}
Re: 507 TLE
Posted: Fri Nov 22, 2013 12:22 am
by brianfry713
You can solve each route in O(s) using DP.
Re: 507 TLE
Posted: Sat Nov 23, 2013 3:04 pm
by d3nd0h
I though that I've used DP, so I am not?
Re: 507 TLE
Posted: Tue Nov 26, 2013 12:36 am
by brianfry713
Your code takes O(s * s) and s can be as large as 20,000.
Re: 507 TLE
Posted: Tue Nov 26, 2013 5:08 am
by d3nd0h
Well thanks, I just realized that, I guess I still need more practice for DP, thx:)
507-Jill Rides Again, WA
Posted: Fri Mar 14, 2014 11:56 pm
by 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;
}
Re: 507-Jill Rides Again, WA
Posted: Tue Mar 18, 2014 12:37 am
by brianfry713
That is AC code.
Re: 507-Jill Rides Again, WA
Posted: Thu Mar 20, 2014 4:42 am
by 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;
}
Re: 507-Jill Rides Again, WA
Posted: Thu Mar 20, 2014 8:21 pm
by 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.
507 - Jill Rides Again Run Time Error
Posted: Fri Jan 02, 2015 1:37 pm
by 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;
}
Re: 507 - Jill Rides Again
Posted: Fri Jan 02, 2015 6:48 pm
by lighted
Yes judge gives RE for your code, but it doesn't match sample I/O so try to fix bugs first.
Re: 507 - Jill Rides Again
Posted: Sat Jan 03, 2015 8:41 pm
by 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
Re: 507 - Jill Rides Again
Posted: Mon Jan 05, 2015 9:29 am
by lighted
Your code posted above doesn't match sample I/O.
http://ideone.com/FZxOoP