QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#511205#5303. No Bug No Gamechengning0909TL 1ms3908kbC++141.8kb2024-08-09 17:32:332024-08-09 17:32:34

Judging History

你现在查看的是最新测评结果

  • [2024-08-09 17:32:34]
  • 评测
  • 测评结果:TL
  • 用时:1ms
  • 内存:3908kb
  • [2024-08-09 17:32:33]
  • 提交

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];

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 <= n; t++) {
        for (int j = 0; j <= k; j++) tmp[t][j] = dp[t][j];
    }
    for (int x : tr[i]) f[x] = 1;
    for (int t = 1; t <= n; t++) {
        for (int j = 0; j <= k; j++) {
            dp[t][j] = max(dp[t][j], dp[t - 1][j]);
            if (f[t] && j >= p[t]) {
                dp[t][j] = max(dp[t][j], dp[t - 1][j - p[t]] + w[t][p[t]]);
            }
        }
    }
    for (int x : tr[i]) f[x] = 0;
    if (l == r) {
        for (int j = 0; j <= k; j++) {
            ans = max(ans, dp[n][j] + w[l][min(p[l], k - j)]);
        }
        for (int t = 1; t <= n; t++) {
            for (int j = 0; j <= k; j++) dp[t][j] = tmp[t][j];
        }
        return ;
    }
    int mid = (l + r) >> 1;
    query(i * 2, l, mid), query(i * 2 + 1, mid + 1, r);
    for (int t = 1; t <= n; t++) {
        for (int j = 0; j <= k; j++) dp[t][j] = tmp[t][j];
    }
}

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;
}

详细

Test #1:

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

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: