QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511221 | #5303. No Bug No Game | __YSC__ | WA | 62ms | 38064kb | C++20 | 1.7kb | 2024-08-09 17:42:34 | 2024-08-09 17:42:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int MAXN = 3001, INF = int(1e9);
int dp[MAXN], last[MAXN], k, ans, w[MAXN][MAXN], p[MAXN];
struct Segment_Tree {
int l[MAXN << 2], r[MAXN << 2];
vector<pii> ve[MAXN << 2];
void build(int u, int s, int t) {
l[u] = s, r[u] = t;
if(s == t) {
return;
}
int mid = (s + t) >> 1;
build(u << 1, s, mid), build((u << 1) | 1, mid + 1, t);
}
void update(int u, int s, int t, pii x) {
if(s > t) {
return;
}
if(l[u] >= s && r[u] <= t) {
ve[u].push_back(x);
return;
}
if(s <= r[u << 1]) {
update(u << 1, s, t, x);
}
if(t >= l[(u << 1) | 1]) {
update((u << 1) | 1, s, t, x);
}
}
void DP(int u) {
for(int i = 0; i <= k; ++i) {
last[i] = dp[i];
}
for(auto [w, v] : ve[u]) {
for(int i = k; i >= w; --i) {
dp[i] = max(dp[i], dp[i - w] + v);
}
}
if(l[u] == r[u]) {
for(int i = 1; i <= min(p[l[u]], k); ++i) {
ans = max(ans, dp[k - i] + w[l[u]][i]);
}
for(int i = 0; i <= k; ++i) {
dp[i] = last[i];
}
return;
}
DP(u << 1), DP((u << 1) | 1);
for(int i = 0; i <= k; ++i) {
dp[i] = last[i];
}
}
}tr;
int n;
int main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> k;
tr.build(1, 1, n);
for(int i = 1; i <= n; ++i) {
cin >> p[i];
for(int j = 1; j <= p[i]; ++j) {
cin >> w[i][j];
}
tr.update(1, 1, i - 1, {p[i], w[i][p[i]]});
tr.update(1, i + 1, n, {p[i], w[i][p[i]]});
}
fill(dp, dp + k + 1, -INF);
dp[0] = 0;
tr.DP(1);
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3880kb
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
Wrong Answer
time: 62ms
memory: 38064kb
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:
172647670
result:
wrong answer 1st numbers differ - expected: '68279788', found: '172647670'