UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#197037#2384. 进步之星tkswls100532ms1360kbC++11846b2023-11-05 11:09:132023-11-05 12:08:33

answer

#include<bits/stdc++.h>
using namespace std;
int n, a[3005][7], f[2][3005];
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	memset(f, 0x3f, sizeof f);
	f[0][0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> a[i][0];
		for (int j = 1; j <= a[i][0]; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		memset(f[i & 1], 0x3f, sizeof(f[i & 1]));
		for (int j = 1; j <= a[i][0]; j++) {
			for (int k = 0; k <= n; k++) {
				f[i & 1][k] = min(f[i & 1][k], f[!(i & 1)][k] + a[i][j]);
			}
			for (int k = 0; k < n; k++) {
				if (!(i - 1) || f[!(i & 1)][k] < a[i][j] * (i - 1)) {
					f[i & 1][k + 1] = min(f[i & 1][k + 1], f[!(i & 1)][k] + a[i][j]);
				}
			}
		}
	}
	for (int i = n; i >= 0; i--) {
		if (f[n & 1][i] != 0x3f3f3f3f) {
			cout << i;
			return 0;
		}
	}
}

Details

小提示:点击横条可展开更详细的信息

Test #1:

score: 10
Accepted
time: 0ms
memory: 1276kb

input:

20
2 2426 2325
2 73 2997
2 209 618
2 2130 25
2 1957 2824
2 977 1719
2 1404 2822
2 77 484
2 272 435
2...

output:

14

result:

ok 1 number(s): "14"

Test #2:

score: 10
Accepted
time: 0ms
memory: 1280kb

input:

20
2 1 2400
2 1912 653
2 1814 673
2 585 1287
2 192 693
2 35 1836
2 307 2507
2 659 2728
2 2865 2965
2...

output:

18

result:

ok 1 number(s): "18"

Test #3:

score: 10
Accepted
time: 0ms
memory: 1276kb

input:

100
5 883 2514 2323 2117 2844
5 36 2805 1130 2177 1770
5 2877 1096 441 294 1018
5 392 569 633 2617 1...

output:

95

result:

ok 1 number(s): "95"

Test #4:

score: 10
Accepted
time: 0ms
memory: 1280kb

input:

100
5 459 614 2891 2013 352
5 640 1079 852 31 497
5 2927 55 1416 438 1338
5 1017 1173 2441 1659 119
...

output:

97

result:

ok 1 number(s): "97"

Test #5:

score: 10
Accepted
time: 0ms
memory: 1280kb

input:

100
5 1634 870 765 1839 44
5 1486 2713 582 2234 457
5 2058 771 2212 811 2958
5 607 478 1503 2016 133...

output:

95

result:

ok 1 number(s): "95"

Test #6:

score: 10
Accepted
time: 67ms
memory: 1360kb

input:

3000
4 1591 2292 2035 2164
4 87 2179 1731 2938
4 1747 2398 912 2288
4 1648 2731 692 496
4 1219 671 7...

output:

2622

result:

ok 1 number(s): "2622"

Test #7:

score: 10
Accepted
time: 92ms
memory: 1356kb

input:

3000
5 1086 1604 674 2160 215
5 1018 2411 913 2294 275
3 570 2572 2665
3 2940 2369 2489
4 1644 2392 ...

output:

2620

result:

ok 1 number(s): "2620"

Test #8:

score: 10
Accepted
time: 127ms
memory: 1356kb

input:

3000
4 1196 476 673 2151
5 302 1379 1979 885 278
4 1841 924 1704 2234
4 2760 208 818 1549
4 2860 157...

output:

2641

result:

ok 1 number(s): "2641"

Test #9:

score: 10
Accepted
time: 123ms
memory: 1356kb

input:

3000
5 857 186 1243 1385 1437
5 2812 330 1826 692 2142
2 2238 654
4 547 1423 1567 30
4 1683 1377 262...

output:

2608

result:

ok 1 number(s): "2608"

Test #10:

score: 10
Accepted
time: 123ms
memory: 1356kb

input:

3000
5 1036 348 85 16 1506
3 2867 2158 100
5 451 2511 472 370 2171
5 297 643 706 650 674
5 2102 563 ...

output:

2624

result:

ok 1 number(s): "2624"

Extra Test:

score: 0
Extra Test Passed