QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#89722	#5822. 城市建设	zhyz	100 ✓	4ms	3492kb	C++14	710b	2023-03-21 00:03:35	2023-03-21 00:03:37

Judging History

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

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-21 00:03:37]
评测

测评结果：100
用时：4ms
内存：3492kb

查看

[2023-03-21 00:03:35]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define LL long long

LL f(LL n,LL k)
{
    if(k==1) return n*n/4;
    LL p = n/k, r = n%k;
    LL tol = p*p/4*(k-r)+(p+1)*(p+1)/4*r;
    if(r==0) tol += n-p/2*2-1;
    else if(r==1) tol += n-p/2-(p+1)/2-1;
    else tol += n-(p+1)/2*2-1;
    return tol;
}

int main()
{
    LL n,c;
    cin>>n>>c;
    LL ans = n*n/4+c;
    for(LL k=2;k*k<=n;k++)
        ans = min(ans,f(n,k)+c*k);
    for(LL p=1;p*p<=n;p++)
    {
        LL k = n/p;
        ans = min(ans,f(n,k)+c*k);
        k--;
        if(k>=1 && k<=n) ans = min(ans,f(n,k)+c*k);
        k = n/(p+1)+1;
        ans = min(ans,f(n,k)+c*k);
    }
    cout<<ans;
    return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 5

Accepted

time: 3ms

memory: 3296kb

input:

14
7

output:

result:

ok single line: '45'

Test #2:

score: 5

Accepted

time: 2ms

memory: 3276kb

input:

15
9

output:

result:

ok single line: '53'

Test #3:

score: 5

Accepted

time: 0ms

memory: 3224kb

input:

15
32

output:

result:

ok single line: '88'

Test #4:

score: 5

Accepted

time: 3ms

memory: 3316kb

input:

18
47

output:

result:

ok single line: '128'

Test #5:

score: 5

Accepted

time: 0ms

memory: 3300kb

input:

691
13

output:

result:

ok single line: '3152'

Test #6:

score: 5

Accepted

time: 2ms

memory: 3316kb

input:

723
381

output:

result:

ok single line: '14800'

Test #7:

score: 5

Accepted

time: 2ms

memory: 3492kb

input:

530
4577

output:

result:

ok single line: '36261'

Test #8:

score: 5

Accepted

time: 2ms

memory: 3312kb

input:

873
71661

output:

result:

ok single line: '239024'

Test #9:

score: 5

Accepted

time: 2ms

memory: 3296kb

input:

50512
6380

output:

result:

ok single line: '4084971'

Test #10:

score: 5

Accepted

time: 2ms

memory: 3340kb

input:

94371
8943

output:

result:

ok single line: '9018507'

Test #11:

score: 5

Accepted

time: 2ms

memory: 3320kb

input:

51969
2391

output:

result:

ok single line: '2593001'

Test #12:

score: 5

Accepted

time: 2ms

memory: 3468kb

input:

90967
8394

output:

result:

ok single line: '8424956'

Test #13:

score: 5

Accepted

time: 0ms

memory: 3376kb

input:

903367404
61

output:

7949633140

result:

ok single line: '7949633140'

Test #14:

score: 5

Accepted

time: 0ms

memory: 3300kb

input:

619459664
4190

output:

40716267253

result:

ok single line: '40716267253'

Test #15:

score: 5

Accepted

time: 2ms

memory: 3224kb

input:

714829312
304390

output:

395097112253

result:

ok single line: '395097112253'

Test #16:

score: 5

Accepted

time: 4ms

memory: 3296kb

input:

760183494
45248537

output:

5114288962225

result:

ok single line: '5114288962225'

Test #17:

score: 5

Accepted

time: 3ms

memory: 3492kb

input:

500350887
499

output:

11674853991

result:

ok single line: '11674853991'

Test #18:

score: 5

Accepted

time: 4ms

memory: 3292kb

input:

837064072
96455

output:

260805440727

result:

ok single line: '260805440727'

Test #19:

score: 5

Accepted

time: 3ms

memory: 3344kb

input:

784256648
6177252

output:

1949981815499

result:

ok single line: '1949981815499'

Test #20:

score: 5

Accepted

time: 3ms

memory: 3224kb

input:

650371022
480071734

output:

14250630194974

result:

ok single line: '14250630194974'

Extra Test:

score: 0

Extra Test Passed