Submission #696574

#	Time	Username	Problem	Language	Result	Execution time	Memory
696574		Deepesson	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	1648 ms	4404 KiB

Main

#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;
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";
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 11 / 11
• Subtask 4: 12 / 12
• Subtask 5: 33 / 33
• Subtask 6: 11 / 11
• Subtask 7: 23 / 23