QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#511213#5303. No Bug No Game__YSC__WA 80ms39300kbC++201.7kb2024-08-09 17:37:042024-08-09 17:37:04

Judging History

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

  • [2024-08-09 17:37:04]
  • 评测
  • 测评结果:WA
  • 用时:80ms
  • 内存:39300kb
  • [2024-08-09 17:37:04]
  • 提交

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];

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 = 0; i < k; ++i) {
        ans = max(ans, dp[i] + w[l[u]][k - 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, p[MAXN];

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: 1ms
memory: 4012kb

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: 80ms
memory: 39300kb

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'