OJ Board

Code: Select all

 
1
5
3
-3
4
1

Code: Select all

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

Code: Select all

#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;
#define S 99999
struct lar
{
	int lar;
	int a,b;
}st[99999];
int main()
{
	int num[S], sum[S];
	int i,j,k;
	int n;
	int t;
	cin >> t;
	for(k=1; k<=t; k++)
	{
		cin >> n;
		if(n==0)
		{cout <<"Route "<<k<<" has no nice parts\n";continue;}
		
		n--;
		int m;
		for(i=0; i<n; i++)
			cin >>  num[i];
		
		m=sum[0]=num[0];
		int x,y;
		int largest=0;
		int l=0;
		x=y=0;
		for(i=1; i<n; i++)
		{	
			sum[i]=num[i]+sum[i-1];
			
			if(sum[i]<num[i])
			{
				st[l].lar=y-x;
				st[l].a=x;
				st[l].b=y; l++;
				x=y=i;
				sum[i]=max(sum[i],num[i]);
			} 
			if(sum[i]>=m)	 
			{
				y=i;
			}
			
			m=max(m,sum[i]);
		}
		for(i=0; i<l; i++)
		{
			if(st[i].lar>largest)
			{
				x=st[i].a;
				y=st[i].b;
			}
		}
		
		if(m>0)
			cout << "The nicest part of route "<<k<<" is between stops "<< x+1 <<" and " <<y+1+1 <<endl;
		else 
			cout <<"Route "<<k<<" has no nice parts\n";
		
	}
	return 0;
}

Code: Select all

#include <iostream>
#include <sstream>
#include <vector>
#include <cstdio>

using namespace std;
struct route
{
	int start;
	int last;
};
int main()
{
	int n;
	scanf("%d",&n);
	int m,l;
	
	
	int sum=0;
	int max_sum=0;
	for(int loop=1;loop<=n;loop++)
	{
		struct route temp;
		scanf("%d",&m);
		temp.start=m-2;
		max_sum=0;
		sum=0;
		
		int a[m-1];
		
		for(int i=0;i<m-1;i++)
			scanf("%d",&a[i]);
		for(int i=m-2;i>=0;i--)
		{
			//scanf("%d",&l);
			l=a[i];
			sum+=l;
			if(sum<0)
			{
				sum=0;				
				temp.start=i-1;
			}
			else if(sum>=0&&max_sum<=sum)
			{
				max_sum=sum;
				//printf("ksdj");				
				temp.last=i;
				//cout<<sum<<" "<<max_sum<<" "<<temp.start<<" "<<temp.last<<endl;
			}
			//cout<<sum<<" "<<max_sum<<" "<<temp.start<<" "<<temp.last<<endl;
		}
		if(max_sum==0)
		{
			//cout<<max_sum<<endl;
			cout<<"Route "<<loop<<" has no nice parts"<<endl;
		}
		else
		{
			cout<<"The nicest part of route "<<loop<<" is between stops "<<temp.last+1<<" and "<<temp.start+2<<endl;
		}		
	}
	return 0;
}

Code: Select all

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

Code: Select all

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

Code: Select all

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

Code: Select all

Code: Select all

1
7
1
2
3
-34
3
3