Submission #769940

#	Time	Username	Problem	Language	Result	Execution time	Memory
769940		shrimb	Fruits (NOI22_fruits)	C++17	0 / 100	31 ms	660 KiB

Main

#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 = 202;

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 (~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 (~dp[i][j]) return dp[i][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 (stderr)

Main.cpp:14:1: warning: multi-line comment [-Wcomment]
   14 | //\
      | ^

• Subtask 1: 0 / 6
• Subtask 2: 0 / 5
• Subtask 3: 0 / 11
• Subtask 4: 0 / 13
• Subtask 5: 0 / 23
• Subtask 6: 0 / 42