QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511040#5303. No Bug No Game114514abcWA 10ms4612kbC++141.3kb2024-08-09 15:34:172024-08-09 15:34:17

Judging History

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

  • [2024-08-09 15:34:17]
  • 评测
  • 测评结果:WA
  • 用时:10ms
  • 内存:4612kb
  • [2024-08-09 15:34:17]
  • 提交

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'