QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#207851#5822. 城市建设abcpony100 ✓0ms3736kbC++201.2kb2023-10-08 21:31:022023-10-08 21:31:03

Judging History

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

  • [2023-10-08 21:31:03]
  • 评测
  • 测评结果:100
  • 用时:0ms
  • 内存:3736kb
  • [2023-10-08 21:31:02]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define rep(i, a, b) for (int i = a; i <= (b); i++)
#define drep(i, a, b) for (int i = a; i >= (b); i--)
typedef long long ll;
int n, c;
ll ccc(int x) {
	return (1ll * x * x - x % 2) / 4;
}
ll cal(int num) {
	int a = n / num, b = a + 1, cb = n % num, ca = num - cb;
	ll tot;
	if (num == 1)
		tot = 0;
	else {
		tot = n - 1;
		if (cb >= 2) {
			tot -= 2 * (b / 2);
		} else if (cb == 1) {
			tot -= b / 2 + a / 2;
		} else
			tot -= 2 * (a / 2);
	}
	// cout << "a=" << a << "\n";
	// cout << "b=" << b << "\n";
	// cout << "tot=" << tot << "\n";
	return tot + 1ll * num * c + ccc(a) * ca + ccc(b) * cb;
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> c;

	// cout << "\ncal(1):\n"
	// 	 << cal(1) << "\n";
	// return 0;

	int l = 1, r = n;
	while (l + 100 < r) {
		int lm = l + (r - l) / 3, rm = r - (r - l) / 3;
		if (cal(lm) < cal(rm))
			r = rm;
		else
			l = lm;
	}
	ll ans = 1e18;
	rep(i, l, r) {
		// if (cal(i) == 11)
		// 	cout << "\n\ni=" << i << "\n\n";
		ans = min<ll>(ans, cal(i));
	}
	// cout << "\ncal(2):\n"
	// 	 << cal(2) << "\n";
	cout << ans;

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5
Accepted
time: 0ms
memory: 3620kb

input:

14
7

output:

45

result:

ok single line: '45'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3668kb

input:

15
9

output:

53

result:

ok single line: '53'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3672kb

input:

15
32

output:

88

result:

ok single line: '88'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3684kb

input:

18
47

output:

128

result:

ok single line: '128'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3608kb

input:

691
13

output:

3152

result:

ok single line: '3152'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3672kb

input:

723
381

output:

14800

result:

ok single line: '14800'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3608kb

input:

530
4577

output:

36261

result:

ok single line: '36261'

Test #8:

score: 5
Accepted
time: 0ms
memory: 3668kb

input:

873
71661

output:

239024

result:

ok single line: '239024'

Test #9:

score: 5
Accepted
time: 0ms
memory: 3736kb

input:

50512
6380

output:

4084971

result:

ok single line: '4084971'

Test #10:

score: 5
Accepted
time: 0ms
memory: 3664kb

input:

94371
8943

output:

9018507

result:

ok single line: '9018507'

Test #11:

score: 5
Accepted
time: 0ms
memory: 3608kb

input:

51969
2391

output:

2593001

result:

ok single line: '2593001'

Test #12:

score: 5
Accepted
time: 0ms
memory: 3656kb

input:

90967
8394

output:

8424956

result:

ok single line: '8424956'

Test #13:

score: 5
Accepted
time: 0ms
memory: 3672kb

input:

903367404
61

output:

7949633140

result:

ok single line: '7949633140'

Test #14:

score: 5
Accepted
time: 0ms
memory: 3732kb

input:

619459664
4190

output:

40716267253

result:

ok single line: '40716267253'

Test #15:

score: 5
Accepted
time: 0ms
memory: 3728kb

input:

714829312
304390

output:

395097112253

result:

ok single line: '395097112253'

Test #16:

score: 5
Accepted
time: 0ms
memory: 3672kb

input:

760183494
45248537

output:

5114288962225

result:

ok single line: '5114288962225'

Test #17:

score: 5
Accepted
time: 0ms
memory: 3604kb

input:

500350887
499

output:

11674853991

result:

ok single line: '11674853991'

Test #18:

score: 5
Accepted
time: 0ms
memory: 3660kb

input:

837064072
96455

output:

260805440727

result:

ok single line: '260805440727'

Test #19:

score: 5
Accepted
time: 0ms
memory: 3604kb

input:

784256648
6177252

output:

1949981815499

result:

ok single line: '1949981815499'

Test #20:

score: 5
Accepted
time: 0ms
memory: 3664kb

input:

650371022
480071734

output:

14250630194974

result:

ok single line: '14250630194974'

Extra Test:

score: 0
Extra Test Passed