QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#536169 | #5303. No Bug No Game | ucup-team1329# | RE | 0ms | 0kb | C++20 | 1.4kb | 2024-08-28 19:27:22 | 2024-08-28 19:27:23 |
answer
#include <bits/stdc++.h>
using i64 = long long;
using A2 = std::array<i64, 2>;
#define Fast_IOS std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)
const i64 mod = 998244353;
i64 MAX(i64 &a, i64 b) {
return a = std::max(a, b);
}
class WORK {
public:
int N;
WORK() {}
void solve() {
i64 n, m;
std::cin >> n >> m;
std::vector<i64> w(n + 1);
std::vector val(n + 1, std::vector<i64>());
i64 sum = 0;
for (int i = 1; i <= n; i++) {
std::cin >> w[i];
sum += w[i];
val[i].push_back(0);
for (int j = 1; j <= w[i]; j++) {
i64 x;
std::cin >> x;
val[i].push_back(x);
}
}
m = std::min(m, sum);
sum = 0;
std::vector f(n + 1, std::vector<A2>(m + 1));
for (int i = 1; i <= n; i++) {
for (int k = 0; k <= sum; k--) {
f[i][k][0] = f[i - 1][k][0];
f[i][k][1] = f[i - 1][k][1];
}
for (int j = 1; j <= w[i] - 1; j++) {
for (int k = j; k <= sum + j; k++) {
MAX(f[i][k][1], f[i - 1][k - j][0] + val[i][j]);
}
}
for (int k = w[i]; k <= sum + w[i]; k--) {
MAX(f[i][k][0], f[i - 1][k - w[i]][0] + val[i][w[i]]);
MAX(f[i][k][1], f[i - 1][k - w[i]][1] + val[i][w[i]]);
}
sum += w[i];
}
std::cout << std::max(f[n][m][0], f[n][m][1]) << '\n';
}
};
int main() {
Fast_IOS;
WORK work;
int T = 1;
// std::cin >> T;
while (T--) {
work.solve();
}
return 0;
}
详细
Test #1:
score: 0
Runtime Error
input:
4 5 2 1 3 2 1 1 2 3 1 2 1 3