QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#536120#5303. No Bug No Gameucup-team1329#WA 59ms144344kbC++201.4kb2024-08-28 18:46:392024-08-28 18:46:39

Judging History

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

  • [2024-08-28 18:46:39]
  • 评测
  • 测评结果:WA
  • 用时:59ms
  • 内存:144344kb
  • [2024-08-28 18:46:39]
  • 提交

answer

#include <bits/stdc++.h>

using i64 = long long;
using A2 = std::array<i64, 2>;

#define Fast_IOS std::ios::sync_with_stdio(false), std::cin.tie(0), std::cout.tie(0)

const i64 mod = 998244353;

i64 MAX(i64 &a, i64 b) {
	return a = std::max(a, b);
}

class WORK {
public:
	int N;

	WORK() {}

	void solve() {
		int n, m;
		std::cin >> n >> m;
		std::vector<i64> w(n + 1);
		std::vector val(n + 1, std::vector<i64>());
		for (int i = 1; i <= n; i++) {
			std::cin >> w[i];
			val[i].push_back(0);
			for (int j = 1; j <= w[i]; j++) {
				i64 x;
				std::cin >> x;
				val[i].push_back(x);
			}
		}
		std::vector f(n + 1, std::vector<A2>(m + 1));
		for (int i = 1; i <= n; i++) {
			for (int k = m; k >= 0; k--) {
				f[i][k][0] = f[i - 1][k][0];
				f[i][k][1] = f[i - 1][k][1];
			}
			for (int j = 1; j <= w[i] - 1; j++) {
				for (int k = m; k >= j; k--) {
					MAX(f[i][k][1], std::max(f[i - 1][k - j][0], f[i - 1][k - j][1]) + val[i][j]);
				}
			}
			for (int k = m; k >= w[i]; k--) {
				MAX(f[i][k][0], f[i - 1][k - w[i]][0] + val[i][w[i]]);
				MAX(f[i][k][1], f[i - 1][k - w[i]][1] + val[i][w[i]]);
			}
		}
		i64 ans = 0;
		for (int i = 0; i <= m; i++) {
			ans = std::max({ans, f[n][i][0], f[n][i][1]});
		}
		std::cout << ans << '\n';
	}
};

int main() {
	Fast_IOS;
	WORK work;
	int T = 1;
	// std::cin >> T;
	while (T--) {
		work.solve();
	}
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 59ms
memory: 144344kb

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:

171648352

result:

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