Solution UVA: 11790 - Murcia's Skyline

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11790 - Murcia's Skyline	Accepted	C++11	0.030	0.000	639	1 mins ago

Suggest:

- Use dynamic programming basic LIS O(n^2) 

#include<bits/stdc++.h>

using namespace std;

int a[1000111];

int w[1000111];

int I[1000111];

int D[1000111];

int32_t main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int t, cnt=0;   cin >> t;

    while(t--){

        int n;  cin >> n;

        for(int i=1; i<=n; i++) cin >> a[i];

        for(int i=1; i<=n; i++) cin >> w[i];

       

        for(int i=1; i<=n; i++){

            I[i]= w[i];

            D[i]= w[i];

           

            for(int j=1; j<i; j++)

                if (a[i] > a[j]) I[i]= max(I[i], I[j] + w[i]);

                else

                    if (a[i] < a[j]) D[i]= max(D[i], D[j] + w[i]);  

        }

       

        int increa= 0, decrea= 0;

        for(int i=1; i<=n; i++)

            increa= max(increa, I[i]), decrea= max(decrea, D[i]);

       

        if (increa >= decrea)

            cout<<"Case "<<++cnt<<". Increasing ("<<increa<<"). Decreasing ("<<decrea<<").\n";

        else

            cout<<"Case "<<++cnt<<". Decreasing ("<<decrea<<"). Increasing ("<<increa<<").\n";

       

    }

}