QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#556167#9129. Quotient SumhezlikWA 1ms5652kbC++141.1kb2024-09-10 15:32:502024-09-10 15:32:50

Judging History

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

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

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;
typedef long double db;

const int N=200000;
const db eps=1e-10L;

int n;
int64 a[N+9],dp[N+9];

void DivideDP(int l,int r){
  if (l==r) return;
  int mid=(l+r)>>1;
  DivideDP(l,mid);
  std::vector<int> cv;
  auto check=[&](int x,int y,int z){
    return (dp[z]-dp[y])*(1.0L/a[y]-1.0L/a[x])<=(dp[y]-dp[x])*(1.0L/a[z]-1.0L/a[y])+eps;
  };
  for (int i=l;i<=mid;++i){
    for (;!cv.empty()&&a[cv.back()]==a[i]&&dp[cv.back()]>=dp[i];cv.pop_back());
    for (;cv.size()>=2&&check(cv.end()[-2],cv.back(),i);cv.pop_back());
    cv.push_back(i);
  }
  for (int i=mid+1,j=0;i<=r;++i){
    auto val=[&](int x){
      return a[i]/a[x]+dp[x];
    };
    for (;j+1<(int)cv.size()&&val(cv[j+1])<=val(cv[j]);++j);
    dp[i]=val(cv[j]);
  }
  DivideDP(mid+1,r);
}

void solve() {
  std::cin>>n;
  for (int i=1;i<=n;++i)
    std::cin>>a[i];
  std::sort(a+1,a+n+1);
  DivideDP(1,n);
  std::cout<<dp[n]<<'\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t=1;
  // cin >> t;
  while (t--) {
    solve();
  }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3532kb

input:

3
2 3 6

output:

3

result:

ok "3"

Test #2:

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

input:

2
15 4

output:

3

result:

ok "3"

Test #3:

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

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: 3756kb

input:

9
12 9 5 17 2 6 7 1 15

output:

9

result:

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