Submission #1238711

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238711		Noname_1900	Let's Win the Election (JOI22_ho_t3)	C++20	10 / 100	1 ms	328 KiB

Main

#include<bits/stdc++.h>
using namespace std;
const int NMAX = 500+1;
//pair<int, int> tempsNec[NMAX];
pair<int, int> tempsNecA[NMAX];

int nbVilles, nbNec;
const int INFINI = 10000000;
struct pourNecB {
    int valA, valB, iVille;
    bool operator<(const pourNecB &other)   const {
        if(valB < other.valB)
        {
            return true;
        }
        if(other.valB < valB)   return false;
        return valA > other.valA;
    }
};
pourNecB tempsNecB[NMAX];
/*
double dejaVu[NMAX][NMAX][NMAX];
double tempsMin(int iVille, int nbPris, int nbCollab)
{
    if(nbPris >= nbNec)
    {
        return 0;
    }
    if(iVille >= nbVilles)
    {
        return INFINI;
    }
    double nbACollab = nbCollab;
    double A = tempsNec[iVille].first;
    double B = tempsNec[iVille].second;
    double opt1 = tempsMin(iVille+1, nbPris, nbCollab);
    double opt2 = tempsMin(iVille+1, nbPris+1, nbCollab) + A/nbACollab;
    double opt3 = tempsMin(iVille+1, nbPris+1, nbCollab+1) + B/nbACollab;
    if(B == -1)
    {
        opt3 = INFINI;
    }
    cout << iVille << " " << nbPris << " " << nbCollab << " : " << min(min(opt1, opt2), opt3) << endl;
    return dejaVu[iVille][nbPris][nbCollab] = min(min(opt1, opt2), opt3);
}
    /** */
bool vuCollab[NMAX];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> nbVilles >> nbNec;
    for(int i = 0; i < nbVilles; i++)
    {
        int a, b;
        cin >> a >> b;
        if(b == -1) b = INFINI;
       // tempsNec[i] = {a, b};
        tempsNecA[i] = {a, i};
        tempsNecB[i] = {a, b, i};
    }
    sort(tempsNecA, tempsNecA+nbVilles);
    sort(tempsNecB, tempsNecB+nbVilles);
    /*/
    for(int i = 0; i < nbVilles; i++)
    {
        cout << tempsNecA[i].first << " " << tempsNecA[i].second << endl;
    }
    cout << endl;
    for(int i = 0; i < nbVilles; i++)
    {
        cout << tempsNecB[i].valA << " " << tempsNecB[i].valB << " " << tempsNecB[i].iVille << endl;
    }
    /**/
    double meillCoup = 0;
    double coupActu = 0;
    double ancCoupCollab = 0;
    for(int i = 0; i < nbNec; i++)  meillCoup += tempsNecA[i].first;
    for(int nbCollabPlus = 0; nbCollabPlus < nbVilles; nbCollabPlus++)
    {
      //  cout << nbCollabPlus << endl;
        double nbCollaborateurs = nbCollabPlus+1;
        coupActu = ancCoupCollab;
        double valCollab = tempsNecB[nbCollabPlus].valB;
        if(valCollab == INFINI) break;
        coupActu += valCollab/nbCollaborateurs;
        nbCollaborateurs += 1;
        vuCollab[tempsNecB[nbCollabPlus].iVille] = true;
        int nbVillesAVoir = nbNec-nbCollabPlus-1;
        int iVilleA = 0;
        ancCoupCollab = coupActu;
        while(nbVillesAVoir > 0)
        {
            while(vuCollab[tempsNecA[iVilleA].second])
            {
                iVilleA++;
            }
            double valA = tempsNecA[iVilleA].first;
            coupActu += valA/nbCollaborateurs;
            nbVillesAVoir--;
            iVilleA++;
        }
        meillCoup = min(meillCoup, coupActu);
    }
    cout << meillCoup;
   // cout << tempsMin(0, 0, 1);
}

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