QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#210310#5303. No Bug No GameFr1nGeLoveWA 57ms74172kbC++201.2kb2023-10-11 11:09:302023-10-11 11:09:31

Judging History

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

  • [2023-10-11 11:09:31]
  • 评测
  • 测评结果:WA
  • 用时:57ms
  • 内存:74172kb
  • [2023-10-11 11:09:30]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;

constexpr int inf = 1044266559;
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, k;
	std::cin >> n >> k;

	int dp[n + 1][k + 1][2];
	memset(dp, -0x3f, sizeof dp);
	for (int i = 0; i < n; i++) {
		dp[i][0][0] = 0;
	}

	for (int i = 1; i <= n; i++) {
		int p;
		std::cin >> p;

		std::vector<int> w(p + 1);
		for (int j = 1; j <= p; j++) {
			std::cin >> w[j];
		}

		for (int j = 1; j <= k; j++) {
			if (j >= p) {
				dp[i][j][0] = std::max({dp[i][j][0], dp[i - 1][j - p][0] + w[p], dp[i - 1][j][0]});
				dp[i][j][1] = std::max({dp[i][j][1], dp[i - 1][j - p][1] + w[p], dp[i - 1][j][1]});
			}

			for (int t = 1; t <= std::min(j, p - 1); t++) {
				dp[i][j][1] = std::max({dp[i][j][1], dp[i - 1][j - t][0] + w[t]});
			}
		}
	}

	int ans = 0;
	for (int j = 0; j <= k; j++) {
		for (int t = 0; t < 2; t++) {
			ans = std::max(ans, dp[n][j][t]);
		}
	}

	// for (int i = 1; i <= n; i++) {
	// 	for (int j = 0; j <= k; j++) {
	// 		for (int t = 0; t < 2; t++) {
	// 			std::cout << "i: " << i << " j: " << j << " t: " << t << " " << dp[i][j][t] << "\n";
	// 		}
	// 	}
	// }
	std::cout << ans << "\n";

	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3684kb

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: 57ms
memory: 74172kb

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:

68236481

result:

wrong answer 1st numbers differ - expected: '68279788', found: '68236481'