Skyline Photo Help - Codeforces

№	Пользователь	Рейтинг
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	atcoder_official	162
3	maomao90	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	155
8	TheScrasse	154
9	Dominater069	153
10	djm03178	152

I was solving the 1482E - Skyline Photo, and it turns out to be WA. I am not sure why did this happen please help me out.

I have used a 2D dp array where dp[i][0] stores the maximum beauty that can be achieved if we combine ith building with the last building dp[i][1] stores the maximum beauty that can be achieved if put in a new photo

While storing the value in dp[i][0] I also took note that in some cases using dp[i-1][0] and dp[i-1][1] both may result with same beauty. So, I took the one that had the greater beauty for the smallest building in the last photo cause that will give a better solution if we happen to find a smaller building with better beauty.

for this "combine" I used a 2D mn_idx array that stores for each state the index of building with minimum height in the current photo ending at ith building.

I could not see the testcases, it shows WA on test 8. So is the logic completely wrong (it will be better if you could please explain why is that so?)?

Here is my code

Code

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> indexed_set;

#define mem(dp,a)           memset(dp,a,sizeof dp)
#define rep(i,a,b)          for(ll i=a;i<b;i++)
#define pb(x)               push_back(x)
#define mp(x,y)             make_pair(x,y)
#define fastio              ios_base::sync_with_stdio(false);cin.tie(NULL)
#define F                   first
#define S                   second
#define all(v)              (v).begin(),(v).end()

const ld pi=3.14159265359;
ll MOD=998244353;
ll mod=1e9+7;
ll INF = 1e18;

int n;
vector<ll> h, b;

int main(){
    
    fastio;
    cin>>n;
    h.assign(n, 0);
    b.assign(n, 0);
    rep(i,0,n)cin>>h[i];
    rep(i,0,n)cin>>b[i];

    vector<vector<ll>> dp(n, vector<ll> (2, -INF));
    ll mn_idx[n][2];
    dp[0][0] = dp[0][1] = b[0];
    mn_idx[0][0] = mn_idx[0][1] = 0;
    rep(i,1,n){
        ll l1 = dp[i-1][0] + (h[mn_idx[i-1][0]] < h[i] ? 0 : -b[mn_idx[i-1][0]] + b[i]);
        ll lb1 = (h[mn_idx[i-1][0]] < h[i] ? b[mn_idx[i-1][0]] : b[i]);
        ll l2 = dp[i-1][1] + (h[mn_idx[i-1][1]] < h[i] ? 0 : -b[mn_idx[i-1][1]] + b[i]);
        ll lb2 = (h[mn_idx[i-1][1]] < h[i] ? b[mn_idx[i-1][1]] : b[i]);
        if(l1 > l2)
            dp[i][0] = l1, mn_idx[i][0] = (l1 == dp[i-1][0] ? mn_idx[i-1][0] : i);
        else if(l2 > l1)
            dp[i][0] = l2, mn_idx[i][0] = (l2 == dp[i-1][1] ? mn_idx[i-1][1] : i);
        else {
            if(lb1 > lb2)
                dp[i][0] = l1, mn_idx[i][0] = (l1 == dp[i-1][0] ? mn_idx[i-1][0] : i);
            else 
                dp[i][0] = l2, mn_idx[i][0] = (l2 == dp[i-1][1] ? mn_idx[i-1][1] : i);
        }
        dp[i][1] = max(dp[i-1][0], dp[i-1][1]) + b[i];
        mn_idx[i][1] = i;
    }
    cout<<max(dp[n-1][0], dp[n-1][1])<<endl;
}