QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511223#5303. No Bug No Gamechengning0909TL 1ms4060kbC++142.0kb2024-08-09 17:43:132024-08-09 17:43:14

Judging History

This is the latest submission verdict.

  • [2024-08-09 17:43:14]
  • Judged
  • Verdict: TL
  • Time: 1ms
  • Memory: 4060kb
  • [2024-08-09 17:43:13]
  • Submitted

answer

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;

const int N = 3010, M = 15;

int n, k, p[N], w[N][M], top, stk[N];
bool f[N];
int dp[N][N], ans;
vector<int> tr[4 * N], h;

void modify(int i, int l, int r, int ql, int qr, int x) {
    if (qr < l || ql > r) return ;
    if (ql <= l && r <= qr) {
        tr[i].push_back(x); return ;
    }
    int mid = (l + r) >> 1;
    modify(i * 2, l, mid, ql, qr, x), modify(i * 2 + 1, mid + 1, r, ql, qr, x);
}

void query(int i, int l, int r) {
    vector<vector<int> > tmp(n + 1, vector<int> (k + 1));
    for (int t = 1; t <= h.size(); t++) {
        for (int j = 0; j <= k; j++) tmp[t][j] = dp[t][j];
    }
    int ty = h.size();
    for (int t = ty + 1; t <= ty + tr[i].size(); t++) {
        int x = tr[i][t - ty - 1];
        for (int j = 0; j <= k; j++) {
            dp[t][j] = dp[t - 1][j];
            if (j >= p[x]) {
                dp[t][j] = max(dp[t][j], dp[t - 1][j - p[x]] + w[x][p[x]]);
            }
        }
        h.push_back(x);
    }
    if (l == r) {
        for (int j = 0; j <= k; j++) {
            ans = max(ans, dp[n - 1][j] + w[l][min(p[l], k - j)]);
        }
        for (int t = 1; t <= h.size(); t++) {
            for (int j = 0; j <= k; j++) dp[t][j] = tmp[t][j];
        }
        for (int t = 1; t <= tr[i].size(); t++) h.pop_back();
        return ;
    }
    int mid = (l + r) >> 1;
    query(i * 2, l, mid), query(i * 2 + 1, mid + 1, r);
    for (int t = 1; t <= h.size(); t++) {
        for (int j = 0; j <= k; j++) dp[t][j] = tmp[t][j];
    }
    for (int t = 1; t <= tr[i].size(); t++) h.pop_back();
}

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k;
    for (int i = 1; i <= n; i++) {
        cin >> p[i];
        for (int j = 1; j <= p[i]; j++) {
            cin >> w[i][j];
        }
        modify(1, 1, n, 1, i - 1, i);
        modify(1, 1, n, i + 1, n, i);
    }
    query(1, 1, n), cout << ans;
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 4060kb

input:

4 5
2 1 3
2 1 1
2 3 1
2 1 3

output:

9

result:

ok 1 number(s): "9"

Test #2:

score: -100
Time Limit Exceeded

input:

3000 3000
10 70562 30723 79371 82224 63977 3362 26909 96449 48163 66159
4 18007 33590 80674 91139
4 10304 31694 70745 50656
10 63090 17226 13187 73881 38137 15237 55750 82751 75854 39658
8 95640 66120 87735 36388 44046 92415 6952 94772
9 60565 27904 98726 87052 35768 25453 14563 34273 92501
10 66332...

output:


result: