QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#511040 | #5303. No Bug No Game | 114514abc | WA | 10ms | 4612kb | C++14 | 1.3kb | 2024-08-09 15:34:17 | 2024-08-09 15:34:17 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 3005;
struct Node{
int l, r;
vector<int>e;
}t[N * 4];
int dp[N], n, k, w[N][30], p[N], ans;
void build(int p, int l, int r){
t[p].l = l, t[p].r = r, t[p].e.clear();
if(l == r){
return;
}
int mid = (l + r) >> 1;
build(p * 2, l, mid), build(p * 2 + 1, mid + 1, r);
}
void updata(int p, int l, int r, int x){
if(l <= t[p].l && t[p].r >= r){
t[p].e.push_back(x);
return;
}
int mid = (t[p].l + t[p].r) >> 1;
if(l <= mid)updata(p * 2, l, r, x);
if(r > mid)updata(p * 2 + 1, l, r, x);
}
void dfs(int pp){
int f[N];
for(int i = 0; i <= k; i++){
f[i] = dp[i];
}
for(auto v : t[pp].e){
for(int i = k; i >= p[v]; i--){
dp[i] = max(dp[i], dp[i - p[v]] + w[v][p[v]]);
}
}
if(t[pp].l == t[pp].r){
for(int i = 0; i <= p[t[pp].l] && k - i >= 0; ++i){
ans = max(ans, dp[k - i] + w[t[pp].l][i]);
}
}
else{
dfs(pp * 2);
dfs(pp * 2 + 1);
}
for(int i = 1; i <= k; ++i){
dp[i] = f[i];
}
}
int main(){
cin >> n >> k;
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];
}
updata(1, 1, i - 1, i);
updata(1, i + 1, 1, i);
}
dfs(1);
cout << ans;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 4096kb
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: 0
Accepted
time: 10ms
memory: 4604kb
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:
68279788
result:
ok 1 number(s): "68279788"
Test #3:
score: -100
Wrong Answer
time: 10ms
memory: 4612kb
input:
3000 3000 7 63414 1471 67699 90007 79945 68096 24021 8 88988 13255 69503 8350 23580 4589 13918 43025 2 7666 45786 2 23237 48565 9 46170 76160 31929 26707 99 76847 64227 82880 99490 8 45937 52389 61039 13440 76101 49424 68485 47682 4 71757 34559 95339 27693 10 55332 93329 61008 26946 44148 73675 3776...
output:
70716942
result:
wrong answer 1st numbers differ - expected: '70716917', found: '70716942'