QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#533907#3960. F1 RacingYarema#AC ✓0ms3704kbC++201.1kb2024-08-26 16:36:242024-08-26 16:36:24

Judging History

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

  • [2024-08-26 16:36:24]
  • 评测
  • 测评结果:AC
  • 用时:0ms
  • 内存:3704kb
  • [2024-08-26 16:36:24]
  • 提交

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'