QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#228827 | #5822. 城市建设 | Terryjoy | 100 ✓ | 0ms | 3676kb | C++14 | 953b | 2023-10-28 14:19:31 | 2023-10-28 14:19:31 |
Judging History
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