oj.uz

Submission #769940

# Submission time Handle Problem Language Result Execution time Memory
769940 2023-06-30T14:26:58 Z shrimb Fruits (NOI22_fruits) C++17
0 / 100
 31 ms 660 KB 
#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

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

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 660 KB Output is correct
2 Incorrect 0 ms 212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 596 KB Output isn't correct
2 Halted 0 ms 0 KB -