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>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define MAX 505
typedef std::pair<double,int> pdd;
typedef std::pair<long long ,long long> pii;
using ll = long long;
pdd tab[MAX][MAX];
int K=0;
std::vector<pii> regs;
int N;
long long C;
double inf = 1LL<<50LL;
pdd dp(void){
for(int i=0;i!=MAX;++i){
tab[N][i]={inf,0};
}
tab[N][0]={0.0,0};
for(int i=N-1;i!=-1;--i){
for(int j=0;j<=K;++j){
tab[i][j]={inf,0};
const double pegou = K-j+1;
if(j){
double custo = (double)regs[i].first/pegou;
pdd g = tab[i+1][j-1];
g.first+=custo;
tab[i][j]=std::min(tab[i][j],g);
}
if(regs[i].second<=C){
double custo = (double)regs[i].second/(double)(K+1);
pdd g = tab[i+1][j];
g.first+=custo-((double)C/(double)(K+1));
g.second--;
tab[i][j]=std::min(tab[i][j],g);
}else tab[i][j]=std::min(tab[i+1][j],tab[i][j]);
}
}
return tab[0][K];
}
pdd simula(ll kok){
C=kok;
return dp();
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
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;
ll last=1000;
for(K=0;K<=obj;++K){
while(K!=obj&&last!=1){
auto vec = simula(last-1);
if(abs(vec.second)>=obj-K&&last){
--last;
}else break;
}
auto kek = simula(last);
kek.second*=-1;
kek.first+=(double)kek.second*((double)last/(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*last))/(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... |