QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#207847#5822. 城市建设abcpony60 0ms3728kbC++201.2kb2023-10-08 21:28:532023-10-08 21:28:54

Judging History

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

  • [2023-10-08 21:28:54]
  • 评测
  • 测评结果:60
  • 用时:0ms
  • 内存:3728kb
  • [2023-10-08 21:28:53]
  • 提交

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 + 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 + 20 < 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;
}

详细

Test #1:

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

input:

14
7

output:

45

result:

ok single line: '45'

Test #2:

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

input:

15
9

output:

53

result:

ok single line: '53'

Test #3:

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

input:

15
32

output:

88

result:

ok single line: '88'

Test #4:

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

input:

18
47

output:

128

result:

ok single line: '128'

Test #5:

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

input:

691
13

output:

3152

result:

ok single line: '3152'

Test #6:

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

input:

723
381

output:

14800

result:

ok single line: '14800'

Test #7:

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

input:

530
4577

output:

36261

result:

ok single line: '36261'

Test #8:

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

input:

873
71661

output:

239024

result:

ok single line: '239024'

Test #9:

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

input:

50512
6380

output:

4084971

result:

ok single line: '4084971'

Test #10:

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

input:

94371
8943

output:

9018507

result:

ok single line: '9018507'

Test #11:

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

input:

51969
2391

output:

2593001

result:

ok single line: '2593001'

Test #12:

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

input:

90967
8394

output:

8424956

result:

ok single line: '8424956'

Test #13:

score: 0
Wrong Answer
time: 0ms
memory: 3660kb

input:

903367404
61

output:

-1150455747

result:

wrong answer 1st lines differ - expected: '7949633140', found: '-1150455747'

Test #14:

score: 0
Wrong Answer
time: 0ms
memory: 3608kb

input:

619459664
4190

output:

-1287318888

result:

wrong answer 1st lines differ - expected: '40716267253', found: '-1287318888'

Test #15:

score: 0
Wrong Answer
time: 0ms
memory: 3728kb

input:

714829312
304390

output:

-1343640168

result:

wrong answer 1st lines differ - expected: '395097112253', found: '-1343640168'

Test #16:

score: 0
Wrong Answer
time: 0ms
memory: 3616kb

input:

760183494
45248537

output:

-1081339823

result:

wrong answer 1st lines differ - expected: '5114288962225', found: '-1081339823'

Test #17:

score: 0
Wrong Answer
time: 0ms
memory: 3728kb

input:

500350887
499

output:

-1581442863

result:

wrong answer 1st lines differ - expected: '11674853991', found: '-1581442863'

Test #18:

score: 0
Wrong Answer
time: 0ms
memory: 3684kb

input:

837064072
96455

output:

-948376379

result:

wrong answer 1st lines differ - expected: '260805440727', found: '-948376379'

Test #19:

score: 0
Wrong Answer
time: 0ms
memory: 3640kb

input:

784256648
6177252

output:

-894885684

result:

wrong answer 1st lines differ - expected: '1949981815499', found: '-894885684'

Test #20:

score: 0
Wrong Answer
time: 0ms
memory: 3664kb

input:

650371022
480071734

output:

-1023690350

result:

wrong answer 1st lines differ - expected: '14250630194974', found: '-1023690350'