QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#511205 | #5303. No Bug No Game | chengning0909 | TL | 1ms | 3908kb | C++14 | 1.8kb | 2024-08-09 17:32:33 | 2024-08-09 17:32:34 |
Judging History
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...