QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#602176 | #7810. 公路 | tiankonguse | 100 ✓ | 11ms | 4884kb | C++20 | 1.4kb | 2024-09-30 20:43:59 | 2024-09-30 20:44:04 |
Judging History
answer
/*
ID: tiankonguse
TASK: road
LANG: C++
CONTEST: CSP-J 2023
OJ: https://qoj.ac/contest/1427/problem/7810
*/
#define TASK "road"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void InitIO() {
// #ifndef USACO_LOCAL_JUDGE
// freopen(TASK ".in", "r", stdin);
// freopen(TASK ".out", "w", stdout);
// #endif
}
/*
题目:一条路上n个加油站,告诉你相邻加油站的距离,每个加油站的价格,问车油箱无限大时,从第一个加油站开到最后一个加油站,最少需要多少钱。
*/
vector<ll> v;
vector<ll> a;
void Solver() { //
ll n, d;
scanf("%lld%lld", &n, &d);
v.resize(n - 1, 0);
for (int i = 0; i < n - 1; i++) {
scanf("%lld", &v[i]);
}
a.resize(n, 0);
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
ll ans = 0;
ll all_dis = 0; // 总共需要跑的公里数
ll all_oil = 0; // 加的总油
ll pre_min_price = a[0];
for (int i = 1; i < n; i++) {
ll dis = v[i - 1];
all_dis += dis;
ll need_oil = (all_dis + d - 1) / d;
if (all_oil < need_oil) { // 油不够,需要买油
ll buy_oil = need_oil - all_oil;
ans += buy_oil * pre_min_price;
all_oil += buy_oil;
}
pre_min_price = min(pre_min_price, a[i]);
}
printf("%lld\n", ans);
}
int main() {
InitIO();
Solver();
return 0;
}
/*
5 4
10 10 10 10
9 8 9 6 5
79
*/
详细
Pretests
Final Tests
Test #1:
score: 5
Accepted
time: 1ms
memory: 3908kb
input:
4 6279 90560 55497 63624 171 103 126 112
output:
4522
result:
ok single line: '4522'
Test #2:
score: 5
Accepted
time: 1ms
memory: 3952kb
input:
7 9690 90508 65420 66793 69375 78851 67135 165 176 168 189 147 116 190
output:
7103
result:
ok single line: '7103'
Test #3:
score: 5
Accepted
time: 1ms
memory: 3744kb
input:
4 8630 91179 76475 75728 91741 57780 81768 98881
output:
2049191
result:
ok single line: '2049191'
Test #4:
score: 5
Accepted
time: 0ms
memory: 3772kb
input:
5 5033 84133 52775 58439 62857 135 123 135 147 129
output:
6600
result:
ok single line: '6600'
Test #5:
score: 5
Accepted
time: 1ms
memory: 3820kb
input:
4 4318 96481 89072 69540 153 157 134 127
output:
8857
result:
ok single line: '8857'
Test #6:
score: 5
Accepted
time: 0ms
memory: 3900kb
input:
641 1675 60321 54585 94048 58181 90810 50626 91247 52014 51184 57198 64521 63837 81550 83573 96718 97173 96724 62386 87534 84455 79386 97695 82803 81799 52083 78375 62675 94194 76826 60418 50006 51586 59803 75088 90209 92188 97581 66227 63234 91503 62501 99041 88434 87911 56070 93349 90092 51249 780...
output:
2854829
result:
ok single line: '2854829'
Test #7:
score: 5
Accepted
time: 1ms
memory: 3832kb
input:
777 7931 51354 94451 87896 68547 74519 83059 63833 98039 89383 53268 87485 65225 54337 79422 63067 61120 74188 56220 58540 97695 55585 58206 82124 50884 86644 60876 61059 69425 79908 61302 80615 88948 89605 74656 85951 71285 50336 55717 60620 54192 53076 50304 62810 75687 81356 74091 90004 95192 881...
output:
367838763
result:
ok single line: '367838763'
Test #8:
score: 5
Accepted
time: 0ms
memory: 3860kb
input:
517 1273 90695 54095 57711 68083 67848 65649 78028 80692 58419 76318 81594 95748 50271 92277 51385 50306 77920 98983 74706 71882 50645 71177 60294 73968 76668 74489 59575 87829 59286 92691 67194 75251 98638 74998 71205 68000 82236 80786 73137 85687 60298 63960 99568 64122 51885 73830 95848 89901 686...
output:
3065915
result:
ok single line: '3065915'
Test #9:
score: 5
Accepted
time: 1ms
memory: 3776kb
input:
608 8236 77795 92587 73591 79904 50985 79073 72381 94444 94302 62378 55222 64930 50309 82936 90309 70762 58844 78024 90531 62849 71026 52985 51178 57394 84019 82069 97828 78748 63938 54063 68138 59523 93644 65437 81564 74576 62087 90830 63269 83675 74581 59281 82387 58861 67865 65279 56457 94865 653...
output:
552062
result:
ok single line: '552062'
Test #10:
score: 5
Accepted
time: 1ms
memory: 3812kb
input:
808 5235 67098 81809 86701 69624 86125 71194 80800 80895 53295 71905 65428 57265 82538 70994 70832 91234 51735 94310 89637 96404 69194 53112 73164 88032 82645 58753 68942 60184 67339 92080 70228 72512 74507 97940 79332 96925 59284 67148 66617 81128 76742 97118 78437 84514 87501 73519 77044 65253 510...
output:
1165312
result:
ok single line: '1165312'
Test #11:
score: 5
Accepted
time: 10ms
memory: 4468kb
input:
79919 4614 98615 83678 57365 95907 51875 99601 74494 58033 98694 50422 71128 55638 54056 79929 92176 96849 82395 95345 55246 53448 79836 80041 87514 64004 69902 55059 73077 92612 94893 82757 94777 90710 52542 95541 89898 86906 70366 91454 61165 98277 80819 55783 81712 60807 97861 66730 70144 52196 7...
output:
65009650000
result:
ok single line: '65009650000'
Test #12:
score: 5
Accepted
time: 7ms
memory: 4712kb
input:
94421 3561 59252 66268 93783 93531 80030 59253 68359 53826 81218 85345 56375 71331 63849 83016 67908 61779 97029 70958 88184 81439 92742 57255 65504 60132 61898 59001 72603 84869 62431 74993 55333 59772 98383 98218 75147 56851 83791 58699 84899 53588 95752 91797 91946 81423 62469 52621 65210 51385 9...
output:
198698900
result:
ok single line: '198698900'
Test #13:
score: 5
Accepted
time: 6ms
memory: 4088kb
input:
51556 1151 88054 94307 74764 97740 63019 50029 58953 55202 94098 51183 58005 61416 52251 62189 63949 90433 82527 92331 67247 90220 98643 54410 91322 99667 82561 67495 73485 81463 75348 64817 90186 80988 84613 80513 81294 62599 79756 99025 76305 77167 83389 64201 71207 59059 91742 79434 83057 82445 7...
output:
167853300000
result:
ok single line: '167853300000'
Test #14:
score: 5
Accepted
time: 6ms
memory: 4612kb
input:
87414 455 74620 58240 85085 73710 84175 80080 95095 85540 77350 75530 97370 50505 56420 99190 51415 94640 85085 82810 66430 66885 72800 74165 96915 76440 92820 63700 63245 79625 56875 67795 57330 61425 63700 99190 60970 68250 74165 60515 82810 64610 56875 52780 70525 55055 85995 95550 84175 87815 51...
output:
1433340496
result:
ok single line: '1433340496'
Test #15:
score: 5
Accepted
time: 10ms
memory: 4480kb
input:
85763 9147 54882 73176 64029 91470 91470 82323 82323 45735 64029 45735 91470 45735 45735 54882 73176 64029 45735 82323 54882 82323 73176 64029 54882 45735 45735 64029 82323 91470 73176 54882 82323 91470 54882 73176 91470 45735 54882 91470 54882 91470 64029 73176 45735 64029 73176 91470 82323 82323 7...
output:
64290855
result:
ok single line: '64290855'
Test #16:
score: 5
Accepted
time: 10ms
memory: 4372kb
input:
85048 3963 83223 83223 83223 71334 75297 91149 59445 47556 55482 47556 83223 99075 75297 75297 55482 63408 91149 75297 87186 95112 55482 67371 59445 67371 75297 91149 83223 51519 47556 87186 95112 79260 75297 99075 83223 47556 59445 67371 71334 63408 71334 47556 63408 59445 87186 63408 51519 99075 8...
output:
157225661
result:
ok single line: '157225661'
Test #17:
score: 5
Accepted
time: 11ms
memory: 4884kb
input:
92109 5827 71291 92100 88805 97390 92433 90944 52444 95069 66628 84474 59949 57121 52472 80707 93907 54706 86980 83324 99981 61411 53081 71666 97207 96746 95175 87669 91465 83266 59493 78788 83781 96577 91685 99952 96215 81079 76930 84666 58092 64544 62885 53991 86380 62296 85817 50190 62939 92289 7...
output:
59325406889
result:
ok single line: '59325406889'
Test #18:
score: 5
Accepted
time: 4ms
memory: 4204kb
input:
67082 9716 81190 67338 83768 78829 87233 70970 52684 65635 82233 85970 83624 77007 86862 98091 90281 90611 52167 78156 61000 69807 86339 57437 62976 51972 97502 77655 67159 62104 94973 86148 51053 73667 98413 54581 57842 85434 57611 73209 51677 56090 98810 99455 97686 95859 79549 58010 81757 97200 7...
output:
51748819
result:
ok single line: '51748819'
Test #19:
score: 5
Accepted
time: 8ms
memory: 4216kb
input:
66850 2814 55961 95417 95979 63151 71710 57581 54268 75160 60438 97790 81597 97610 95525 59552 88795 87019 96372 73247 73767 51664 82581 51924 87915 51338 61882 83378 53925 96348 68324 97967 97220 52522 61121 53760 73348 78572 95623 81706 93800 50506 58861 96960 64624 81984 52482 60133 55506 93740 5...
output:
178193850
result:
ok single line: '178193850'
Test #20:
score: 5
Accepted
time: 10ms
memory: 4476kb
input:
87336 997 72406 56890 88358 68529 85879 80519 51901 79396 59895 88914 96933 59189 56696 55611 97964 51275 62849 88147 50343 74547 54946 56795 97515 57144 88168 69753 90715 90587 98638 55044 90862 77784 65788 75447 82959 83218 59931 81512 67269 63226 57009 92306 94170 65751 56740 91647 79825 94656 83...
output:
656253307
result:
ok single line: '656253307'