uva507

uva507.cpp

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

typedef long long ll;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }

const int inf = 1e9;
const int maxn=(int)4e5+5;

void print_ans(int r, int s, int e) {
  cout<<"The nicest part of route "<<r<<" is between stops "<<s<<" and "<<e<<endl;
}

void solve(int r) {
  int x; cin>>x;
  vector<int> roads(x);
  for (int i=1; i<=x-1; i++) cin>>roads[i];
  int ans_s = -1, ans_e = -1; int ans_max = -inf;
  
  int s = 1, e = 1;
  int cur = 0;
  for (int i=1; i<=x-1; i++) {
    cur += roads[i];
    e = i+1;
    // update answer
    if (cur > ans_max) {
      ans_s =  s; ans_e = e; ans_max = cur;
    } else if (cur == ans_max) {
      if (e-s > ans_e-ans_s) {
	ans_s =  s; ans_e = e;
      }
    }
    if (cur < 0) {
      s = i+1; e = i+1;
      cur = 0;
    }
  }
  if (ans_s == -1 || ans_max < 0) {
    cout<<"Route "<<r<<" has no nice parts"<<endl;
  } else {
    print_ans(r,ans_s,ans_e);
  }
}

int b;
int main() {
  ios_base::sync_with_stdio(false); cin.tie(0);
  //cout << fixed << setprecision(6);
  cin>>b;
  for (int r=1; r<=b; r++) solve(r);

  return 0;
}