#include"bits/stdc++.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<class x>
using ordered_set = tree<x, null_type,less<x>, rb_tree_tag,tree_order_statistics_node_update>;
#define int long long
#define endl '\n'
#define mod 1000000007
//\
#define mod 1686876991
const int maxn = 400001;
int n;
int a[maxn], c[maxn], taken[maxn], pref[maxn], preft[maxn];
int dp[maxn][maxn];
int rec (int i, int j, int k) {
if (i == k) return 0;
if (~dp[i][j]) return dp[i][j];
if (~a[i]) {
bool b = a[i] >= j;
while (j <= n && (a[i] >= j)) j++;
return dp[i][j] = rec(i + 1, j, k) + (b ? c[a[i]] : 0);
}
while (j <= n && taken[j]) j++;
if (pref[i] < preft[j]) dp[i][j] = rec(i + 1, j, k);
if (j != n + 1) dp[i][j] = max({dp[i][j], rec(i + 1, j + 1, k) + c[j], rec(i, j + 1, k)});
return dp[i][j];
}
signed main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
for (int i = 1 ; i <= n ; i++) {
cin >> a[i];
if (a[i] != -1) taken[a[i]] = 1;
else pref[i] = 1;
if (i) pref[i] += pref[i-1];
}
for (int i = 1 ; i <= n ; i++) {
if (taken[i] == 0) preft[i] = 1;
preft[i] += preft[i-1];
cin >> c[i];
}
preft[n + 1] = preft[n];
for (int i = 1 ; i <= n ; i++) {
memset(dp, -1, sizeof dp);
cout << rec(1, 1, i + 1) << " ";
}
}
Compilation message
Main.cpp:14:1: warning: multi-line comment [-Wcomment]
14 | //\
| ^
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
