This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define MAX 505
typedef std::pair<double,int> pdd;
typedef std::pair<long long ,long long> pii;
using ll = long long;
double LGD;
int existe[MAX][MAX];
pdd tab[MAX][MAX];
int rodada=52;
int K=0;
std::vector<pii> regs;
int N;
long long C;
double inf = 1LL<<50LL;
pdd dp(int pos,int falta){
if(pos==N&&!falta)return {0.0,0};
if(pos==N){
return {inf,0};
}
if(existe[pos][falta]==rodada)return tab[pos][falta];
existe[pos][falta]=rodada;
double pegou = (K-falta)+1;
pdd ans = {inf,0};
if(falta){
double custo = (double)regs[pos].first/(double)pegou;
pdd g = dp(pos+1,falta-1);
g.first+=custo;
ans=std::min(ans,g);
}
{
if(regs[pos].second<=C){
double custo = (double)regs[pos].second/(double)(K+1);
pdd g = dp(pos+1,falta);
g.first+=custo-((double)C/(double)(K+1));
++g.second;
ans=std::min(ans,g);
}else {pdd g =dp(pos+1,falta);ans=std::min(ans,g);}
}
return tab[pos][falta]=ans;
}
int main()
{
int obj;
std::cin>>N>>obj;
for(int i=0;i!=N;++i){
ll a,b;
std::cin>>a>>b;
if(b==-1)b=inf;
regs.push_back({b,a});
}
std::sort(regs.begin(),regs.end());
double ans=inf;
for(K=0;K<=obj;++K){
ll l=0,r=1000;
while(l<r){
ll m = (l+r)/2;
C=m;
++rodada;
auto x = dp(0,K);
if(x.second>=obj-K){
r=m;
}else l=m+1;
}
++rodada;
C=l;
auto kek = dp(0,K);
int quer = obj-K;
kek.first+=(double)quer*((double)l/(double)(K+1));
///Pegar quantos a mais selecionei
ll dif = kek.second-(obj-K);
///Descontar os extras (note que eu consigo garantir que o custo eh L)
kek.first-=((double)(dif*l))/(double)(K+1);
ans=std::min(ans,kek.first);
}
std::cout<<std::fixed<<std::setprecision(20)<<ans<<"\n";
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |