UVA 507 - Джилл снова едет неверный ответ

Что не так с этим решением UVA 507 - Jill Rides Again, если мое? Я использовал алгоритм Кадана и отслеживал местоположение по LL= локальное левое, LR = локальное правое, GL = глобальное левое, GR = глобальное правое. а также GM = global max, LM = local max?

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;

    while(cin>>t)
    {
        for(int j=0; j<t; j++)
        {
            long long x, sum=0; cin>>x;
            vector<long long> v;

            for(int i=0; i<x-1; i++)
            {
                int vInput; cin>>vInput;
                v.push_back(vInput);
                sum+=vInput;
            }
            //done taking input; Now Using Kadane's ALGO

            long long LM,GM, LL,LR,GL,GR; LM=GM=v[0]; LL=GL=1; LR=GR=2;

            for(int i=1; i<v.size(); i++)
            {
                LM = max(LM+v[i], v[i]);

                if(LM==v[i])
                {
                    LL=i+1;
                    LR=i+2;
                }
                else{
                    LR++;
                }

                if( (LM>GM) || (LM==GM && ((LR-LL)>(GR-GL))) )
                {
                    GM=LM; GL=LL; GR=LR;
                }
            }

            if(GM<1) cout<<"Route "<<j+1<<" has no nice parts"<<endl;
            else cout<<"The nicest part of route "<<j+1<<" is between stops "<<GL<<" and "<<GR<<endl;
        }
    }
}

0 ответов

Другие вопросы по тегам