QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#88227 | #2420. Kitesurfing | xiaoyaowudi | WA | 4ms | 3464kb | C++14 | 1.2kb | 2023-03-15 17:45:27 | 2023-03-15 17:45:29 |
Judging History
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'