QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#88227#2420. KitesurfingxiaoyaowudiWA 4ms3464kbC++141.2kb2023-03-15 17:45:272023-03-15 17:45:29

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-15 17:45:29]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3464kb
  • [2023-03-15 17:45:27]
  • 提交

answer

#include <algorithm>
#include <iostream>
constexpr int N(510);
using ll=long long;
constexpr ll inf(1e18);
ll s,d,t,l[N],r[N],ed[N];int n;
ll calc(ll k)
{
	if(k<0) return 0;
	ll q=k/d;
	return std::min(k,std::min(t*q+k-d*q,t*(q+1)));
}
int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cin>>s>>d>>t;
	std::cin>>n;++n;s+=d;
	for(int i(2);i<=n;++i) std::cin>>l[i]>>r[i],l[i]+=d,r[i]+=d;
	l[1]=0;r[1]=d;
	l[n+1]=s;r[n+1]=s+d;++n;r[n+1]=inf;l[n+1]=inf;ed[n+1]=inf;
	for(int i(1);i<=n;++i)
	{
		ed[i]=r[i]-d;
		if(ed[i]<=0)
		{
			ed[i]=0;
		}
		else
		{
			int t(0);
			while(l[t]<ed[i]) ++t;
			--t;ed[i]=std::max(r[t],ed[i]);
		}
	}
	static ll f[N];
	f[1]=calc(ed[1]);for(int i(2);i<=n;++i) f[i]=inf;
	for(int i(1);i<n;++i)
	{
		ll bs(0),pos(ed[i]);
		int idx(i+1);
		for(int j(i);j<n;++j)
		{
			if(pos<ed[j+1])
			{
				ll k((r[j]-pos-1)/d+1);
				pos+=(k-1)*d;pos=std::min(pos,l[j]);pos+=d;
				bs+=k*t;
				int t(j);while(r[t]<=pos) ++t;pos=std::min(l[t],pos);
			}
			while(ed[idx]<=l[j+1]) f[idx]=std::min(f[idx],calc(ed[idx]-pos)+f[i]+bs),++idx;
		}
	}
	std::cout<<f[n]-t<<std::endl;
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 3336kb

input:

10 4 5
0

output:

10

result:

ok single line: '10'

Test #2:

score: 0
Accepted
time: 2ms
memory: 3424kb

input:

10 4 1
0

output:

3

result:

ok single line: '3'

Test #3:

score: 0
Accepted
time: 2ms
memory: 3300kb

input:

10 4 3
0

output:

8

result:

ok single line: '8'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3284kb

input:

4 2 1
1
2 3

output:

2

result:

ok single line: '2'

Test #5:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

18 10 11
2
3 5
7 14

output:

23

result:

ok single line: '23'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3340kb

input:

1000000000 100 90
0

output:

900000000

result:

ok single line: '900000000'

Test #7:

score: 0
Accepted
time: 2ms
memory: 3312kb

input:

697 310 191
1
384 497

output:

459

result:

ok single line: '459'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3280kb

input:

337489234 846388201 210392939
3
63127010 66068111
137080824 196209361
222495016 320924100

output:

210392939

result:

ok single line: '210392939'

Test #9:

score: 0
Accepted
time: 2ms
memory: 3300kb

input:

10 4 3
1
8 9

output:

8

result:

ok single line: '8'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3208kb

input:

20 5 1
4
3 6
9 12
13 14
16 18

output:

5

result:

ok single line: '5'

Test #11:

score: 0
Accepted
time: 2ms
memory: 3284kb

input:

33030012 846831 33589
39
161 845994
846322 1692906
1693528 2540025
2540916 3387100
3388072 4234575
4234724 5081265
5082139 5928664
5928757 6774943
6775186 7621539
7622286 8468627
8469012 9315723
9316381 10162503
10162589 11008927
11009763 11855714
11856173 12702595
12703320 13549158
13549619 1439643...

output:

1316718

result:

ok single line: '1316718'

Test #12:

score: 0
Accepted
time: 3ms
memory: 3284kb

input:

16402055 52929 20498
310
682 53041
53330 105659
106127 158313
158555 210588
210683 262653
263552 315903
316339 368368
369016 421340
421430 474340
474720 527035
527601 580020
580694 633214
633293 685739
686700 739471
740043 792705
793505 846126
846245 898627
898897 951544
951790 1004434
1004438 10566...

output:

6376311

result:

ok single line: '6376311'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3308kb

input:

13153613 692256 91753
19
559 691928
692102 1383372
1384161 2075581
2076566 2768565
2768838 3460562
3461196 4152671
4153436 4844918
4845111 5536419
5537285 6229200
6229277 6921310
6921965 7613605
7614210 8305940
8306367 8998200
8999129 9690640
9690727 10382841
10383328 11075429
11075713 11767874
1176...

output:

1745083

result:

ok single line: '1745083'

Test #14:

score: 0
Accepted
time: 3ms
memory: 3284kb

input:

82115478 203242 69057
404
262 202564
203528 406080
407051 609666
610451 812905
813117 1016319
1016840 1220048
1220581 1423262
1424199 1626507
1626634 1829488
1830375 2033146
2033679 2235945
2236278 2438593
2439061 2642025
2642265 2844846
2845079 3048133
3048374 3250757
3251120 3453756
3454629 365767...

output:

27940099

result:

ok single line: '27940099'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3396kb

input:

29335567 116846 40442
251
225 116409
116439 232649
233560 350204
350230 467023
467878 584662
585109 701637
702441 818761
819270 935236
935945 1052503
1053243 1169292
1170209 1286614
1287286 1403776
1404001 1520216
1520856 1637360
1638327 1754500
1754932 1870801
1871003 1987200
1988083 2104665
210500...

output:

10177681

result:

ok single line: '10177681'

Test #16:

score: 0
Accepted
time: 2ms
memory: 3348kb

input:

218600004 437224 85101
500
888 437805
438464 875298
875777 1312070
1312484 1749025
1749857 2186435
2187013 2623340
2623461 3060491
3061198 3497959
3498077 3934649
3935509 4372102
4372609 4809085
4810077 5247054
5247613 5683976
5684304 6120781
6121714 6558148
6558541 6995273
6995554 7431884
7432864 7...

output:

42590274

result:

ok single line: '42590274'

Test #17:

score: 0
Accepted
time: 4ms
memory: 3464kb

input:

128831209 257660 63190
500
625 257686
258082 515262
516103 772873
773239 1030295
1030812 1287752
1288307 1545114
1545897 1803275
1803405 2060563
2061516 2319019
2319686 2577066
2577610 2835055
2835193 3092685
3092766 3350294
3351210 3608490
3609288 3866029
3866311 4122988
4123012 4380060
4380557 463...

output:

31641939

result:

ok single line: '31641939'

Test #18:

score: 0
Accepted
time: 2ms
memory: 3464kb

input:

125276177 250560 78140
500
722 250916
251038 501352
502257 752157
752879 1002578
1003495 1253174
1253746 1503673
1504045 1753687
1754095 2003776
2004670 2254534
2255150 2505200
2505332 2755553
2755766 3006161
3006336 3256063
3256430 3506057
3506335 3756554
3757506 4007077
4007115 4257400
4257701 450...

output:

39109343

result:

ok single line: '39109343'

Test #19:

score: 0
Accepted
time: 2ms
memory: 3320kb

input:

264371637 528764 97681
500
103 528526
529466 1057762
1058174 1586289
1587208 2115830
2116164 2644422
2645204 3173225
3173840 3701659
3702461 4230701
4230729 4759043
4759595 5287391
5288094 5816467
5816597 6344423
6344586 6872911
6873806 7402394
7402429 7931181
7931579 8460107
8460237 8988622
8988652...

output:

48882951

result:

ok single line: '48882951'

Test #20:

score: 0
Accepted
time: 4ms
memory: 3316kb

input:

252544224 505102 36816
500
380 504514
504703 1009498
1009539 1514049
1514260 2018369
2018802 2522952
2523138 3027494
3027802 3532040
3532505 4036787
4037590 4542239
4543134 5047894
5048686 5553247
5553678 6057856
6058257 6562630
6562695 7066882
7067812 7572528
7573304 8077696
8077735 8582050
8582501...

output:

18447578

result:

ok single line: '18447578'

Test #21:

score: -100
Wrong Answer
time: 2ms
memory: 3348kb

input:

44889530 221464 52660
75
70401 130674
812086 826693
897081 1107861
1946062 2116748
2318239 2412590
3040677 3136502
3904286 4081784
4879978 5039656
5224799 5370041
5418855 5578091
6101958 6104689
6532762 6719409
7090342 7183005
7781076 7972270
8706353 8709684
9446847 9507548
10207293 10302521
1050608...

output:

11270364

result:

wrong answer 1st lines differ - expected: '11269189', found: '11270364'