QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#483207#9129. Quotient Sumucup-team1525#WA 1ms5964kbC++20549b2024-07-18 13:32:242024-07-18 13:32:24

Judging History

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

  • [2024-09-26 15:38:30]
  • hack成功,自动添加数据
  • (/hack/908)
  • [2024-07-18 13:32:24]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:5964kb
  • [2024-07-18 13:32:24]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e5;
int n;
ll a[N+5];
ll st[N+5],tot;
bool chk(ll x,ll y,ll z){
    return x/y+y/z>=x/z;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    sort(a+1,a+1+n);
    ll ans=0;
    st[++tot]=a[1];
    for(int i=2;i<=n;i++){
        while(tot>1&&chk(a[i],st[tot],st[tot-1])) tot--;
        st[++tot]=a[i];
    }
    for(int i=2;i<=tot;i++)
        ans+=st[i]/st[i-1];
    printf("%lld\n",ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5964kb

input:

3
2 3 6

output:

3

result:

ok "3"

Test #2:

score: 0
Accepted
time: 0ms
memory: 3856kb

input:

2
15 4

output:

3

result:

ok "3"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5904kb

input:

9
284791808 107902 13660981249408 4622332661 13405199 24590921 361 244448137 16077087227955422

output:

4580

result:

ok "4580"

Test #4:

score: -100
Wrong Answer
time: 0ms
memory: 3956kb

input:

9
12 9 5 17 2 6 7 1 15

output:

7

result:

wrong answer 1st words differ - expected: '6', found: '7'