QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#546926	#1408. Straps	UZING	50	612ms	35264kb	C++14	651b	2024-09-04 15:55:20	2024-09-04 15:55:20

Judging History

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

[2024-09-04 15:55:20]
评测

测评结果：50
用时：612ms
内存：35264kb

查看

[2024-09-04 15:55:20]
提交

answer

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2010;
int n,ans,sum;
int dp[N],f[N*N];
signed main()
{
	cin>>n;
	memset(f,128,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
	{
		int x,y;
		cin>>x>>y;
		if(x==0)
		{
			for(int j=n;j>=1;j--)
				dp[j]=max(dp[j],dp[j-1]+y);
		}
		else
		{
			x--;
			if(x==0)
			{
				ans+=max(y,0ll);
				continue;
			}
			sum+=x;
			for(int j=sum;j>=x;j--)
				f[j]=max(f[j],f[j-x]+y);
		}
	}
	dp[n+1]=dp[n];
	for(int i=n+1;i<=sum;i++)
		f[n]=max(f[i],f[n]);
	int ma=0;
	for(int i=0;i<=n;i++)
		ma=max(ma,f[i]+dp[i+1]);
	cout<<ma+ans;
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 35252kb

input:

output:

result:

ok single line: '216'

Test #2:

score: 5

Accepted

time: 0ms

memory: 35168kb

input:

output:

result:

ok single line: '24591'

Test #3:

score: 5

Accepted

time: 0ms

memory: 35132kb

input:

output:

result:

ok single line: '4089949'

Test #4:

score: 5

Accepted

time: 0ms

memory: 35256kb

input:

output:

result:

ok single line: '3881041'

Test #5:

score: 5

Accepted

time: 2ms

memory: 35108kb

input:

output:

result:

ok single line: '5065535'

Test #6:

score: 5

Accepted

time: 0ms

memory: 35236kb

input:

output:

result:

ok single line: '4678317'

Test #7:

score: 5

Accepted

time: 0ms

memory: 35196kb

input:

output:

result:

ok single line: '908830'

Test #8:

score: 5

Accepted

time: 0ms

memory: 35184kb

input:

output:

result:

ok single line: '3436799'

Test #9:

score: 5

Accepted

time: 0ms

memory: 35188kb

input:

output:

result:

ok single line: '2752090'

Test #10:

score: 5

Accepted

time: 0ms

memory: 35124kb

input:

output:

result:

ok single line: '2793112'

Test #11:

score: 5

Accepted

time: 4ms

memory: 35160kb

input:

output:

result:

ok single line: '3755141'

Test #12:

score: 5

Accepted

time: 0ms

memory: 35160kb

input:

output:

result:

ok single line: '3245727'

Test #13:

score: 5

Accepted

time: 0ms

memory: 35192kb

input:

output:

result:

ok single line: '3109959'

Test #14:

score: 5

Accepted

time: 0ms

memory: 35192kb

input:

output:

result:

ok single line: '4070028'

Test #15:

score: 5

Accepted

time: 0ms

memory: 35108kb

input:

output:

result:

ok single line: '956180'

Test #16:

score: 5

Accepted

time: 0ms

memory: 35256kb

input:

output:

result:

ok single line: '5238155'

Test #17:

score: 5

Accepted

time: 3ms

memory: 35180kb

input:

output:

result:

ok single line: '3786990'

Test #18:

score: 5

Accepted

time: 3ms

memory: 35240kb

input:

output:

result:

ok single line: '6323784'

Test #19:

score: 5

Accepted

time: 0ms

memory: 35232kb

input:

output:

result:

ok single line: '2312828'

Test #20:

score: 5

Accepted

time: 0ms

memory: 35180kb

input:

output:

result:

ok single line: '946977'

Test #21:

score: 5

Accepted

time: 2ms

memory: 35192kb

input:

output:

result:

ok single line: '918595'

Test #22:

score: 5

Accepted

time: 7ms

memory: 35168kb

input:

output:

result:

ok single line: '2472987'

Test #23:

score: 5

Accepted

time: 0ms

memory: 35104kb

input:

output:

result:

ok single line: '4093646'

Test #24:

score: 5

Accepted

time: 0ms

memory: 35128kb

input:

output:

result:

ok single line: '4375336'

Test #25:

score: 5

Accepted

time: 2ms

memory: 35096kb

input:

output:

result:

ok single line: '3634441'

Subtask #2:

score: 0

Time Limit Exceeded

Test #26:

score: 5

Accepted

time: 0ms

memory: 35176kb

input:

output:

result:

ok single line: '7475346'

Test #27:

score: 5

Accepted

time: 0ms

memory: 35256kb

input:

output:

34193793

result:

ok single line: '34193793'

Test #28:

score: 5

Accepted

time: 0ms

memory: 35196kb

input:

output:

33904495

result:

ok single line: '33904495'

Test #29:

score: 5

Accepted

time: 0ms

memory: 35108kb

input:

output:

28836586

result:

ok single line: '28836586'

Test #30:

score: 5

Accepted

time: 0ms

memory: 35172kb

input:

output:

28435495

result:

ok single line: '28435495'

Test #31:

score: 5

Accepted

time: 0ms

memory: 35168kb

input:

output:

14854268

result:

ok single line: '14854268'

Test #32:

score: 5

Accepted

time: 0ms

memory: 35200kb

input:

output:

26625993

result:

ok single line: '26625993'

Test #33:

score: 5

Accepted

time: 3ms

memory: 35256kb

input:

output:

310810523

result:

ok single line: '310810523'

Test #34:

score: 5

Accepted

time: 0ms

memory: 35180kb

input:

output:

284797916

result:

ok single line: '284797916'

Test #35:

score: 5

Accepted

time: 3ms

memory: 35188kb

input:

output:

278884229

result:

ok single line: '278884229'

Test #36:

score: 5

Accepted

time: 0ms

memory: 35196kb

input:

output:

244690730

result:

ok single line: '244690730'

Test #37:

score: 5

Accepted

time: 3ms

memory: 35132kb

input:

output:

568422711

result:

ok single line: '568422711'

Test #38:

score: 5

Accepted

time: 3ms

memory: 35136kb

input:

output:

576776733

result:

ok single line: '576776733'

Test #39:

score: 5

Accepted

time: 0ms

memory: 35256kb

input:

output:

524383990

result:

ok single line: '524383990'

Test #40:

score: 5

Accepted

time: 4ms

memory: 35112kb

input:

output:

414846273

result:

ok single line: '414846273'

Test #41:

score: 5

Accepted

time: 4ms

memory: 35176kb

input:

output:

364443840

result:

ok single line: '364443840'

Test #42:

score: 5

Accepted

time: 8ms

memory: 35172kb

input:

output:

368998056

result:

ok single line: '368998056'

Test #43:

score: 5

Accepted

time: 4ms

memory: 35132kb

input:

output:

330426515

result:

ok single line: '330426515'

Test #44:

score: 5

Accepted

time: 4ms

memory: 35208kb

input:

output:

779925426

result:

ok single line: '779925426'

Test #45:

score: 5

Accepted

time: 2ms

memory: 35264kb

input:

output:

850490893

result:

ok single line: '850490893'

Test #46:

score: 5

Accepted

time: 5ms

memory: 35132kb

input:

2000
0 991111
0 929682
0 560562
0 886447
0 422739
0 802476
0 704993
0 495146
0 856347
0 552125
0 968876
0 774223
0 683296
0 865874
0 298814
0 108080
0 815238
0 65280
0 818498
0 912023
0 723605
0 702023
0 914117
0 884744
0 198664
0 451317
70 72898
0 744919
0 814835
0 883810
0 671054
0 999942
0 762925...

output:

996337317

result:

ok single line: '996337317'

Test #47:

score: 5

Accepted

time: 2ms

memory: 35176kb

input:

output:

432410585

result:

ok single line: '432410585'

Test #48:

score: 5

Accepted

time: 4ms

memory: 35264kb

input:

output:

976666351

result:

ok single line: '976666351'

Test #49:

score: 5

Accepted

time: 4ms

memory: 35200kb

input:

output:

486295248

result:

ok single line: '486295248'

Test #50:

score: 5

Accepted

time: 0ms

memory: 35264kb

input:

2000
0 728963
0 970866
0 520406
0 618287
0 204723
0 333129
0 478720
0 254635
0 105274
0 710556
0 119849
0 972559
0 315208
0 457722
0 370424
0 334759
0 136682
0 310410
0 834915
0 921610
0 469511
0 344114
0 58540
0 186606
0 580693
0 918973
0 770673
0 774440
0 394544
0 927541
0 995762
0 974134
0 589415...

output:

1005695686

result:

ok single line: '1005695686'

Test #51:

score: 5

Accepted

time: 4ms

memory: 35108kb

input:

2000
0 573403
0 686578
0 245270
0 814249
0 478003
0 61449
0 363504
0 590517
0 685394
0 487925
0 580211
0 142830
0 938593
0 912871
0 599931
0 817877
0 117311
0 412182
0 794899
0 919780
0 690914
0 120537
0 311281
0 616453
0 573845
0 623318
0 914280
0 460699
0 889578
0 371084
0 740152
0 710247
0 915592...

output:

905189230

result:

ok single line: '905189230'

Test #52:

score: 5

Accepted

time: 0ms

memory: 35176kb

input:

output:

1006062137

result:

ok single line: '1006062137'

Test #53:

score: 5

Accepted

time: 4ms

memory: 35204kb

input:

output:

2000000000

result:

ok single line: '2000000000'

Test #54:

score: 5

Accepted

time: 612ms

memory: 35172kb

input:

output:

990661576

result:

ok single line: '990661576'

Test #55:

score: 0

Time Limit Exceeded

input:

output:

result:

Subtask #3:

score: 45

Accepted

Test #57:

score: 45

Accepted

time: 0ms

memory: 35252kb

input:

output:

result:

ok single line: '8669946'

Test #58:

score: 45

Accepted

time: 0ms

memory: 35260kb

input:

output:

22909865

result:

ok single line: '22909865'

Test #59:

score: 45

Accepted

time: 2ms

memory: 35256kb

input:

output:

result:

ok single line: '8915512'

Test #60:

score: 45

Accepted

time: 0ms

memory: 35164kb

input:

output:

16185496

result:

ok single line: '16185496'

Test #61:

score: 45

Accepted

time: 0ms

memory: 35172kb

input:

output:

16050463

result:

ok single line: '16050463'

Test #62:

score: 45

Accepted

time: 6ms

memory: 35260kb

input:

output:

20955387

result:

ok single line: '20955387'

Test #63:

score: 45

Accepted

time: 0ms

memory: 35124kb

input:

output:

15404784

result:

ok single line: '15404784'

Test #64:

score: 45

Accepted

time: 0ms

memory: 35236kb

input:

output:

12892236

result:

ok single line: '12892236'

Test #65:

score: 45

Accepted

time: 0ms

memory: 35132kb

input:

output:

157820672

result:

ok single line: '157820672'

Test #66:

score: 45

Accepted

time: 0ms

memory: 35260kb

input:

output:

169747354

result:

ok single line: '169747354'

Test #67:

score: 45

Accepted

time: 0ms

memory: 35132kb

input:

output:

145516315

result:

ok single line: '145516315'

Test #68:

score: 45

Accepted

time: 0ms

memory: 35100kb

input:

output:

149791128

result:

ok single line: '149791128'

Test #69:

score: 45

Accepted

time: 0ms

memory: 35192kb

input:

output:

174802359

result:

ok single line: '174802359'

Test #70:

score: 45

Accepted

time: 0ms

memory: 35132kb

input:

output:

152732130

result:

ok single line: '152732130'

Test #71:

score: 45

Accepted

time: 0ms

memory: 35236kb

input:

output:

129364099

result:

ok single line: '129364099'

Test #72:

score: 45

Accepted

time: 5ms

memory: 35180kb

input:

output:

135558630

result:

ok single line: '135558630'

Test #73:

score: 45

Accepted

time: 5ms

memory: 35212kb

input:

output:

318238396

result:

ok single line: '318238396'

Test #74:

score: 45

Accepted

time: 4ms

memory: 35248kb

input:

output:

318211584

result:

ok single line: '318211584'

Test #75:

score: 45

Accepted

time: 0ms

memory: 35188kb

input:

output:

270428799

result:

ok single line: '270428799'

Test #76:

score: 45

Accepted

time: 3ms

memory: 35264kb

input:

output:

264970930

result:

ok single line: '264970930'

Test #77:

score: 45

Accepted

time: 8ms

memory: 35188kb

input:

output:

333179022

result:

ok single line: '333179022'

Test #78:

score: 45

Accepted

time: 4ms

memory: 35248kb

input:

output:

336805487

result:

ok single line: '336805487'

Test #79:

score: 45

Accepted

time: 3ms

memory: 35132kb

input:

output:

260187466

result:

ok single line: '260187466'

Test #80:

score: 45

Accepted

time: 4ms

memory: 35212kb

input:

output:

256561542

result:

ok single line: '256561542'

Test #81:

score: 45

Accepted

time: 2ms

memory: 35184kb

input:

output:

263646470

result:

ok single line: '263646470'

Test #82:

score: 45

Accepted

time: 0ms

memory: 35188kb

input:

2000
4 -635016
1 -149397
0 814158
0 -725125
0 -759422
0 84494
0 -208079
0 538489
0 798676
0 438428
0 -131437
0 -994341
0 -849333
0 -393112
0 862242
2 -520630
0 -89409
0 -684885
0 627513
0 -893956
0 -723492
0 -213509
0 758302
0 706095
0 -195004
0 -531622
0 -918685
0 692568
0 -216292
0 736629
0 319847...

output:

216405089

result:

ok single line: '216405089'

Test #83:

score: 45

Accepted

time: 4ms

memory: 35108kb

input:

output:

191021897

result:

ok single line: '191021897'

Test #84:

score: 45

Accepted

time: 8ms

memory: 35188kb

input:

output:

217406968

result:

ok single line: '217406968'

Test #85:

score: 45

Accepted

time: 4ms

memory: 35180kb

input:

output:

337601884

result:

ok single line: '337601884'

Test #86:

score: 45

Accepted

time: 0ms

memory: 35204kb

input:

output:

194384602

result:

ok single line: '194384602'

Test #87:

score: 45

Accepted

time: 4ms

memory: 35196kb

input:

2000
0 292441
0 -825063
0 -811351
0 343865
0 53019
0 -878815
0 -69455
0 329491
0 -267054
0 -561962
0 -982781
0 608052
0 117567
0 -597788
0 574947
0 141242
0 98023
0 472801
0 -389101
0 -75798
0 183590
0 733628
0 -382373
0 940820
0 426849
0 426225
0 301786
0 530642
0 -139596
0 -124995
0 52397
0 -70499...

output:

222293880

result:

ok single line: '222293880'

Test #88:

score: 45

Accepted

time: 0ms

memory: 35140kb

input:

output:

284931407

result:

ok single line: '284931407'

Test #89:

score: 45

Accepted

time: 18ms

memory: 35160kb

input:

output:

result:

ok single line: '95190'

Subtask #4:

score: 0

Skipped

Dependency #1:

100%

Accepted