QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#497049 | #9115. Contour Multiplication | ucup-team3282 | RE | 0ms | 0kb | C++14 | 492b | 2024-07-28 18:26:22 | 2024-07-28 18:26:22 |
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=2e5+10;
int n;
ll a[maxn];
ll f[maxn];
int main(){
ios::sync_with_stdio(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+n+1);
f[1]=0;
for(int i=2;i<=n;i++){
int p=lower_bound(f+1,f+i,f[i-1])-f;
f[i]=min(f[i-1]+a[i]/a[i-1],p==1?(ll)1e18:f[p-1]+a[i]/a[p-1]);
}
// for(int i=1;i<=n;i++)
// cout<<f[i]<<' ';
// cout<<endl;
cout<<f[n]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Runtime Error
input:
3 100 2 0 2 4 3 0 25