QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#228827#5822. 城市建设Terryjoy100 ✓0ms3676kbC++14953b2023-10-28 14:19:312023-10-28 14:19:31

Judging History

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

  • [2023-10-28 14:19:31]
  • 评测
  • 测评结果:100
  • 用时:0ms
  • 内存:3676kb
  • [2023-10-28 14:19:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#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);
	}
	return tot + 1ll * num * c + ccc(a) * ca + ccc(b) * cb;
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> c;
	int l = 1, r = n;
	ll ans = 1e18;
	for (int i = 1; i <= 1000; ++i) {
		int lm = l + (r - l) / 3, rm = r - (r - l) / 3;
		ans = min({ans, cal(lm), cal(rm)});
		if (cal(lm) < cal(rm))
			r = rm;
		else
			l = lm;
	}
//	ll ans = 1e18;
	ans = min(ans, cal(l));
	cout << ans;
	return 0;
}

詳細信息

Test #1:

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

input:

14
7

output:

45

result:

ok single line: '45'

Test #2:

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

input:

15
9

output:

53

result:

ok single line: '53'

Test #3:

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

input:

15
32

output:

88

result:

ok single line: '88'

Test #4:

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

input:

18
47

output:

128

result:

ok single line: '128'

Test #5:

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

input:

691
13

output:

3152

result:

ok single line: '3152'

Test #6:

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

input:

723
381

output:

14800

result:

ok single line: '14800'

Test #7:

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

input:

530
4577

output:

36261

result:

ok single line: '36261'

Test #8:

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

input:

873
71661

output:

239024

result:

ok single line: '239024'

Test #9:

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

input:

50512
6380

output:

4084971

result:

ok single line: '4084971'

Test #10:

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

input:

94371
8943

output:

9018507

result:

ok single line: '9018507'

Test #11:

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

input:

51969
2391

output:

2593001

result:

ok single line: '2593001'

Test #12:

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

input:

90967
8394

output:

8424956

result:

ok single line: '8424956'

Test #13:

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

input:

903367404
61

output:

7949633140

result:

ok single line: '7949633140'

Test #14:

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

input:

619459664
4190

output:

40716267253

result:

ok single line: '40716267253'

Test #15:

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

input:

714829312
304390

output:

395097112253

result:

ok single line: '395097112253'

Test #16:

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

input:

760183494
45248537

output:

5114288962225

result:

ok single line: '5114288962225'

Test #17:

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

input:

500350887
499

output:

11674853991

result:

ok single line: '11674853991'

Test #18:

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

input:

837064072
96455

output:

260805440727

result:

ok single line: '260805440727'

Test #19:

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

input:

784256648
6177252

output:

1949981815499

result:

ok single line: '1949981815499'

Test #20:

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

input:

650371022
480071734

output:

14250630194974

result:

ok single line: '14250630194974'

Extra Test:

score: 0
Extra Test Passed