QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#95549#5303. No Bug No GameSnowNorthRE 2ms3468kbC++141.2kb2023-04-10 12:25:042023-04-10 12:25:06

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-04-10 12:25:06]
  • 评测
  • 测评结果:RE
  • 用时:2ms
  • 内存:3468kb
  • [2023-04-10 12:25:04]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int w[3005][15], p[3005];
int f[3005][2], can[3005][2];

void solve() {
	int n, k;
	cin >> n >> k;
	
	for (int i = 1; i <= n; i++) {
		cin >> p[i];
		for (int j = 1; j <= p[i]; j++)
			cin >> w[i][j];
	}
	
	int ans(0);
	for (int t = 0; t <= 10; t++) {	//t空缺的部分 
		memset (f, 0, sizeof f);
		memset (can, 0, sizeof can);
		can[0][0] = 1;
		for (int i = 1; i <= n; i++) {
			for (int j = 0; j <= k - t; j++) {
				if (can[j][0]) {
					if (j + p[i] <= k - t) {
						can[j + p[i]][0] = 1;
						f[j + p[i]][0] = max(f[j + p[i]][0], f[j][0] + w[i][p[i]]);
					}
					
					if (t > 0 && p[i] > t) {
						can[j][1] = 1;
						f[j][1] = max(f[j][1], f[j][0] + w[i][t]);
					}
				}	
				
				if (can[j][1]) {
					can[j + p[i]][1] = 1;
					f[j + p[i]][1] = max(f[j + p[i]][1], f[j][1] + w[i][p[i]]);
				}
					
				ans = max(ans, f[j][0]);
			}
		}
		if (t > 0 && can[k - t][1]) ans = max(ans, f[k - t][1]);
	}
	cout << ans;
}

signed main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

/*
4 5
2 100 1
2 99 1
2 80 1
2 20 1
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 2ms
memory: 3468kb

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
Runtime Error

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:


result: