Logo Wy Online Judge

WyOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#937#206. 「CSP-J2019」纪念品gctiruct1001260ms20780kbC++14703b2025-07-05 08:18:022025-07-05 11:15:19

answer

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

const int N = 110, V = 10010;

int t, n, m;
int f[N][2*V], g[N];
int v[N][N], w[N][N];

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> t >> n >> g[0];
	for(int i=1; i<=t; i++)
		for(int j=1; j<=n; j++)
			cin >> v[i][j];
	for(int i=1; i<=t; i++)
	{
		for(int j=1; j<=n; j++)
			w[i][j] = v[i+1][j] - v[i][j];
		memset(f, 0, sizeof(f));
		int V = g[i-1];
		for(int j=1; j<=n; j++)
			for(int k=V; k>=0; k--)
				f[j][k] = max(f[j-1][k], (k+v[i][j]<=V)*(f[j][k+v[i][j]]+w[i][j]));
		for(int j=0; j<=V; j++)
			g[i] = max(g[i], f[n][j]+V-j);
	}
	cout << g[t];
	return 0;
}
Source code, Language: C++14

Details

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

Test #1:

score: 5
Accepted
time: 1ms
memory: 20348kb

input:

1 3 88
86 54 73

output:

88

result:

ok "88"

Test #2:

score: 5
Accepted
time: 0ms
memory: 20480kb

input:

1 4 100
64 35 78 55

output:

100

result:

ok "100"

Test #3:

score: 5
Accepted
time: 2ms
memory: 20380kb

input:

3 3 72
35 37 35
30 13 43
37 16 37

output:

108

result:

ok "108"

Test #4:

score: 5
Accepted
time: 1ms
memory: 20424kb

input:

4 3 96
28 46 67
11 69 32
16 36 38
19 36 52

output:

272

result:

ok "272"

Test #5:

score: 5
Accepted
time: 3ms
memory: 20360kb

input:

3 4 89
49 39 32 10
66 43 17 14
39 61 16 20

output:

170

result:

ok "170"

Test #6:

score: 5
Accepted
time: 6ms
memory: 20480kb

input:

4 4 100
12 13 31 50
16 19 16 51
18 25 24 63
25 15 18 21

output:

283

result:

ok "283"

Test #7:

score: 5
Accepted
time: 67ms
memory: 20616kb

input:

80 1 500
105
106
107
107
107
107
108
109
104
105
106
107
108
101
102
102
103
104
105
105
105
106
107...

output:

730

result:

ok "730"

Test #8:

score: 5
Accepted
time: 85ms
memory: 20644kb

input:

100 1 1000
265
267
270
272
272
271
271
274
275
277
282
284
287
265
269
274
278
283
284
284
286
286
2...

output:

1890

result:

ok "1890"

Test #9:

score: 5
Accepted
time: 88ms
memory: 20728kb

input:

100 1 1000
658
667
670
621
622
600
611
612
613
613
625
636
642
653
658
661
662
667
673
682
690
704
7...

output:

1867

result:

ok "1867"

Test #10:

score: 5
Accepted
time: 5ms
memory: 20484kb

input:

2 100 1000
329 759 613 859 65 926 552 624 660 448 469 454 596 711 280 452 401 173 435 844 316 52 897...

output:

9497

result:

ok "9497"

Test #11:

score: 5
Accepted
time: 5ms
memory: 20436kb

input:

2 100 1000
509 784 23 672 601 1593 759 181 663 257 92 622 959 39 226 39 550 413 800 978 4064 7033 32...

output:

2900

result:

ok "2900"

Test #12:

score: 5
Accepted
time: 3ms
memory: 20480kb

input:

2 100 1000
417 5 68 266 961 212 6264 43 231 592 406 238 4930 713 888 726 6501 83 780 744 623 350 25 ...

output:

9395

result:

ok "9395"

Test #13:

score: 5
Accepted
time: 81ms
memory: 20716kb

input:

80 80 500
8695 188 27 372 259 425 139 269 371 213 108 311 6432 139 34 232 472 65 357 431 222 380 243...

output:

2188

result:

ok "2188"

Test #14:

score: 5
Accepted
time: 84ms
memory: 20516kb

input:

80 100 500
6369 397 420 1560 1673 267 246 86 9396 162 139 105 265 74 364 499 239 189 371 103 7198 34...

output:

2211

result:

ok "2211"

Test #15:

score: 5
Accepted
time: 123ms
memory: 20652kb

input:

100 80 800
219 354 6931 64 595 521 718 587 404 5044 790 311 557 383 43 484 401 620 6099 83 8921 1022...

output:

5801

result:

ok "5801"

Test #16:

score: 5
Accepted
time: 132ms
memory: 20492kb

input:

100 100 800
765 1802 94 1882 421 495 384 4428 327 7 767 446 798 8 592 206 666 633 3421 349 541 679 7...

output:

5916

result:

ok "5916"

Test #17:

score: 5
Accepted
time: 144ms
memory: 20644kb

input:

100 100 1000
183 266 232 163 107 1552 680 558 580 743 861 356 865 9009 514 768 100 416 90 390 2142 7...

output:

7679

result:

ok "7679"

Test #18:

score: 5
Accepted
time: 145ms
memory: 20780kb

input:

100 100 1000
478 615 949 663 949 741 678 934 6541 6549 5863 142 540 5100 8854 636 620 424 35 976 572...

output:

7720

result:

ok "7720"

Test #19:

score: 5
Accepted
time: 142ms
memory: 20640kb

input:

100 100 1000
473 520 1823 216 865 736 717 3277 272 595 990 615 873 335 783 142 815 669 5853 222 5116...

output:

7765

result:

ok "7765"

Test #20:

score: 5
Accepted
time: 143ms
memory: 20536kb

input:

100 100 1000
4860 5022 188 75 180 397 767 204 8507 785 2828 530 915 94 879 281 386 8570 695 5556 696...

output:

7692

result:

ok "7692"
中文 English

鲁ICP备2025150228号

Server Time: 2025-07-08 14:44:16 | OpenSource Project