QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#533907 | #3960. F1 Racing | Yarema# | AC ✓ | 0ms | 3704kb | C++20 | 1.1kb | 2024-08-26 16:36:24 | 2024-08-26 16:36:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define RFOR(i, a, b) for(int i = (a) - 1; i >= (b); i--)
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
LL f(LL n, LL b, LL x, LL p)
{
LL r = n / x;
int bg = n % x;
int sm = x - bg;
LL res = b * (sm * (r * (r - 1)) / 2 + bg * (r * (r + 1)) / 2);
//cerr << x << ' ' << res << '\n';
return res + (x - 1) * p;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
LL n, p, R, b;
cin >> n >> p >> R >> b;
//FOR (i, 1, n + 1)
//{
// cerr << i << ' ' << f(n, b, i, p) << '\n';
//}
LL ans = (n - 1) * n / 2 * b;
int l = 1, r = n;
while (l + 4 < r)
{
int ml = l + (r - l) / 3;
int mr = r - (r - l) / 3;
if (f(n, b, ml, p) < f(n, b, mr, p))
r = mr;
else
l = ml;
}
FOR (i, l, r + 1)
ans = min(ans, f(n, b, i, p));
cout << ans + R * n << '\n';
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3612kb
input:
10 10 100 2
output:
1044
result:
ok single line: '1044'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
122 505 64 3
output:
13847
result:
ok single line: '13847'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
585574164 991960948 27 3
output:
45189632804058
result:
ok single line: '45189632804058'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
152104730 501970178 100 0
output:
15210473000
result:
ok single line: '15210473000'
Test #5:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
887307333 193529999 97 2
output:
24772550551288
result:
ok single line: '24772550551288'
Test #6:
score: 0
Accepted
time: 0ms
memory: 3680kb
input:
640060486 661421162 43 0
output:
27522600898
result:
ok single line: '27522600898'
Test #7:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
736922375 297625189 53 3
output:
31178629203095
result:
ok single line: '31178629203095'
Test #8:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
658630071 373326171 6 1
output:
18000276268443
result:
ok single line: '18000276268443'
Test #9:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
621746237 475361779 71 1
output:
19214160260482
result:
ok single line: '19214160260482'
Test #10:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
36382642 516101487 39 1
output:
1169783173875
result:
ok single line: '1169783173875'
Test #11:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
70 20 8 1
output:
949
result:
ok single line: '949'
Test #12:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
433173131 501984581 94 1
output:
13765294997014
result:
ok single line: '13765294997014'
Test #13:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
758415659 485892050 26 2
output:
33453925349906
result:
ok single line: '33453925349906'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
423868757 702171417 1 0
output:
423868757
result:
ok single line: '423868757'
Test #15:
score: 0
Accepted
time: 0ms
memory: 3704kb
input:
345019835 439024075 50 1
output:
10240224870365
result:
ok single line: '10240224870365'
Test #16:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
385972797 415226457 40 2
output:
15744655070252
result:
ok single line: '15744655070252'
Test #17:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
123164287 943673429 96 0
output:
11823771552
result:
ok single line: '11823771552'
Test #18:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
399953400 522430076 95 2
output:
18320326415984
result:
ok single line: '18320326415984'
Test #19:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
717196656 647323763 97 2
output:
36562838750646
result:
ok single line: '36562838750646'
Test #20:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
109427949 736845552 32 4
output:
8404136033532
result:
ok single line: '8404136033532'
Test #21:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
439367856 327592168 11 4
output:
22496245862812
result:
ok single line: '22496245862812'
Test #22:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
790 315 63 1
output:
68895
result:
ok single line: '68895'
Test #23:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
275035131 601075116 53 3
output:
16530449224518
result:
ok single line: '16530449224518'
Test #24:
score: 0
Accepted
time: 0ms
memory: 3656kb
input:
23914117 32825277 92 0
output:
2200098764
result:
ok single line: '2200098764'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
532193572 131162646 45 1
output:
8643202953266
result:
ok single line: '8643202953266'
Test #26:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
218666852 490337874 1 0
output:
218666852
result:
ok single line: '218666852'
Test #27:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
47649709 396756172 16 3
output:
2325159084536
result:
ok single line: '2325159084536'
Test #28:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
852526326 81639864 29 4
output:
21810262423542
result:
ok single line: '21810262423542'
Test #29:
score: 0
Accepted
time: 0ms
memory: 3556kb
input:
517905169 136650874 9 2
output:
12112397917319
result:
ok single line: '12112397917319'
Test #30:
score: 0
Accepted
time: 0ms
memory: 3612kb
input:
691829074 713204364 53 2
output:
36987079122956
result:
ok single line: '36987079122956'
Test #31:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
811879864 319236663 34 1
output:
20541483275836
result:
ok single line: '20541483275836'
Test #32:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
986047440 265081472 40 4
output:
45445216918768
result:
ok single line: '45445216918768'
Test #33:
score: 0
Accepted
time: 0ms
memory: 3644kb
input:
1 200 5 3
output:
5
result:
ok single line: '5'
Test #34:
score: 0
Accepted
time: 0ms
memory: 3540kb
input:
754733345 772210354 73 1
output:
29714301054756
result:
ok single line: '29714301054756'
Test #35:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1000000000 0 1 1
output:
1000000000
result:
ok single line: '1000000000'
Test #36:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1000000000 1 1 1
output:
1999999999
result:
ok single line: '1999999999'
Test #37:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
1000000000 2 1 1
output:
2499999998
result:
ok single line: '2499999998'
Test #38:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1000000000 10 1 0
output:
1000000000
result:
ok single line: '1000000000'
Test #39:
score: 0
Accepted
time: 0ms
memory: 3696kb
input:
1000000000 10 1 1
output:
4999999990
result:
ok single line: '4999999990'
Test #40:
score: 0
Accepted
time: 0ms
memory: 3608kb
input:
1000000000 10 1 2
output:
6333333324
result:
ok single line: '6333333324'
Test #41:
score: 0
Accepted
time: 0ms
memory: 3604kb
input:
1000000000 1000000000 1 0
output:
1000000000
result:
ok single line: '1000000000'
Test #42:
score: 0
Accepted
time: 0ms
memory: 3544kb
input:
1000000000 1000000000 1 1
output:
44720859556840
result:
ok single line: '44720859556840'
Test #43:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
1000000000 1000000000 1 2
output:
63244553212762
result:
ok single line: '63244553212762'
Test #44:
score: 0
Accepted
time: 0ms
memory: 3616kb
input:
4 10 2 2
output:
20
result:
ok single line: '20'
Test #45:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1000000000 1000000000 100 4
output:
89539719113680
result:
ok single line: '89539719113680'
Test #46:
score: 0
Accepted
time: 0ms
memory: 3640kb
input:
1000000000 1 100 4
output:
100999999999
result:
ok single line: '100999999999'
Test #47:
score: 0
Accepted
time: 0ms
memory: 3628kb
input:
1000000000 10 100 4
output:
106999999990
result:
ok single line: '106999999990'
Test #48:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
2 2 3 4
output:
8
result:
ok single line: '8'
Test #49:
score: 0
Accepted
time: 0ms
memory: 3636kb
input:
1000000000 700 100 4
output:
172842104564
result:
ok single line: '172842104564'
Test #50:
score: 0
Accepted
time: 0ms
memory: 3624kb
input:
1000000 1000000000 2 2
output:
62251000000
result:
ok single line: '62251000000'
Test #51:
score: 0
Accepted
time: 0ms
memory: 3548kb
input:
1000000000 1000000000 100 4
output:
89539719113680
result:
ok single line: '89539719113680'
Test #52:
score: 0
Accepted
time: 0ms
memory: 3632kb
input:
5 10 2 2
output:
28
result:
ok single line: '28'
Test #53:
score: 0
Accepted
time: 0ms
memory: 3700kb
input:
201874807 215317746 7 4
output:
8379308650579
result:
ok single line: '8379308650579'
Test #54:
score: 0
Accepted
time: 0ms
memory: 3552kb
input:
70 0 1 1
output:
70
result:
ok single line: '70'