QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#556167 | #9129. Quotient Sum | hezlik | WA | 1ms | 5652kb | C++14 | 1.1kb | 2024-09-10 15:32:50 | 2024-09-10 15:32:50 |
Judging History
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'