#DP #MIS #UVa #Solved

507 - Jill Rides Again.cpp

//https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=448
#include <bits/stdc++.h>

#define ll long long
#define sz(v) ((int) ((v).size()))
#define clr(v, d) memset(v, d, sizeof(v))
#define lp(i, n) for(int i = 0; i < (int)(n); ++i)
#define rep(i, v) for(int i = 0; i < sz(v); ++i)

using namespace std;

const int MAX = 15;
const int OO = 1e4;
int dp[110][110];
int n, t;

int main() {
    cin>>t;
    lp(k, t) {
        cin>>n;
        int best = -1*OO, x, sum = 0, tmpI=1, tmpJ, bestI, bestJ;
        lp(i, n-1) {
            cin>>x;
            if(sum < 0) { sum = x; tmpI = i+1; tmpJ = i+2;}
            else { sum+=x; tmpJ = i+2;}
            if(sum > best) {
                best = sum;
                bestI = tmpI; bestJ = tmpJ;
            } else if(sum == best) {
                if(tmpJ-tmpI > bestJ - bestI) {
                    best = sum;
                    bestI = tmpI; bestJ = tmpJ;
                } else if(tmpI < bestI) {
                    best = sum;
                    bestI = tmpI; bestJ = tmpJ;
                }
            }
        }
        if(best<0) {
            cout << "Route " << k+1 << " has no nice parts" << endl;
        } else
            cout << "The nicest part of route " << k+1 << " is between stops " << bestI <<" and " << bestJ << endl;
    }
    return 0;
}