Submission #853062

#	Time	Username	Problem	Language	Result	Execution time	Memory
853062		mkorzybski	Let's Win the Election (JOI22_ho_t3)	C++17	21 / 100	562 ms	346132 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<ll,ll>
#define f first
#define s second
#define ld long double


ll n, k, I;
ld odpowiedz = 10000000;
const ll N = 507, dupsko = 213769420;
ll A[N], B[N];
ld kosztB[N][N];
ll maxA[N][N];
ll nextMaxA[N][N];
vector <ll> ciagA[N][N];
ll sumaA[N][N];
vector <pii> tab = {{-10,-10}};


bool cmpB(pii a, pii b)
{
    return a.s < b.s;
}

bool cmpA(ll a, ll b)
{
    return tab[a].f < tab[b].f;
}

void ustal_odp()
{
    vector <ll> tmpA;
    ld tmpOdp = 0;
    for(ll i=1; i<=n; i++) tmpA.push_back(A[i]);
    sort(tmpA.begin(), tmpA.end());

    for(ll i=0; i<k; i++)
    {
        tmpOdp += tmpA[i];
    }

    odpowiedz = tmpOdp;
}


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k;
    for(ll i=1; i<=n; i++)
    {
        cin >> A[i] >> B[i];
        if(B[i] != -1) I++;
        else B[i] = dupsko;
        tab.push_back({A[i], B[i]});
    }
    I = min(I, k);
    sort(tab.begin(), tab.end(), cmpB);

    /*cout << "tab\n";
    for(pii v : tab) cout << v.f << "," << v.s << "  ";
    cout << endl;*/

    ustal_odp();

    for(ll i=1; i<=n; i++)
    {
        if(tab[i].s == dupsko)
        {
            kosztB[1][i] = (ld) dupsko;
            sumaA[1][i] = (ld) dupsko;
            continue;
        }

        for(ll j=1; j<=n; j++)
        {
            ciagA[1][i].push_back(j);
        }
        ciagA[1][i].push_back(0);
        sort(ciagA[1][i].begin(), ciagA[1][i].end(), cmpA);

        ll tmpS = ciagA[1][i].size();
        for(ll j=1; j<tmpS; j++)
        {
            if(ciagA[1][i][j] == i)
            {
                ciagA[1][i].erase(ciagA[1][i].begin() + j);
                break;
            }
        }

        maxA[1][i] = ciagA[1][i][k-1];
        for(ll j=1; j<=k-1; j++) sumaA[1][i] += tab[ciagA[1][i][j]].f;
        kosztB[1][i] = (ld) tab[i].s;

        odpowiedz = min(odpowiedz, kosztB[1][i] + (ld) ((ld) sumaA[1][i] /(ld) 2));

        /*cout << "dla " << 1 << ", " << i << ":\n";
        cout << sumaA[1][i] << " " << fixed << setprecision(2) << kosztB[1][i] << " " << maxA[1][i] << " {";
        for(ll v : ciagA[1][i]) cout << v << ",";
        cout << "} oraz wyn = " << fixed << setprecision(3) << kosztB[1][i] + (ld) ((ld) sumaA[1][i] /(ld) 2) << endl;*/
    }

    for(ll i=2; i<=I; i++)
    {
        for(ll j=1; j<=n; j++)
        {
            if(tab[j].s == dupsko)
            {
                kosztB[i][j] = (ld) dupsko;
                sumaA[i][j] = (ld) dupsko;
                continue;
            }

            ld minWynik = 10000000;
            ll ktoMinWynik = -1;
            for(ll o=1; o<j; o++)
            {
                if(kosztB[i-1][o] == (ld) dupsko) continue;
                
                ld tmpWynik = kosztB[i-1][o] + (ld) ((ld) sumaA[i-1][o] /(ld) (i+1));

                if(tab[maxA[i-1][o]].f >= tab[j].f)
                {
                    tmpWynik -= (ld) tab[j].f /(ld) (i+1);
                }
                else
                {
                    tmpWynik -= (ld) tab[maxA[i-1][o]].f / (ld) (i+1);
                }
                

                if(tmpWynik < minWynik)
                {
                    minWynik = tmpWynik;
                    ktoMinWynik = o;
                }
            }
            
            

            if(ktoMinWynik == -1)
            {
                kosztB[i][j] = (ld) dupsko;
                sumaA[i][j] = (ld) dupsko;
                continue;
            }
            kosztB[i][j] = kosztB[i-1][ktoMinWynik] + (ld)((ld)tab[j].s / (ld)i);
            ciagA[i][j] = ciagA[i-1][ktoMinWynik];
            ll tmpS = ciagA[i][j].size();
            for(ll o=1; o<tmpS; o++)
            {
                if(ciagA[i][j][o] == j)
                {
                    ciagA[i][j].erase(ciagA[i][j].begin() + o);
                    break;
                }
            }
            for(ll o=1; o<=k-i; o++)
            {
                sumaA[i][j] += tab[ciagA[i][j][o]].f;
            }
            maxA[i][j] = ciagA[i][j][k-i];

            
            odpowiedz = min(odpowiedz, kosztB[i][j] + (ld) ((ld) sumaA[i][j] /(ld) (i+1)));

            /*cout << "dla " << i << ", " << j << ":\n";
            cout << sumaA[i][j] << " " << fixed << setprecision(2) << kosztB[i][j] << " " << maxA[i][j] << " {";
            for(ll v : ciagA[i][j]) cout << v << ",";
            cout << "} oraz wyn = " << fixed << setprecision(3) << kosztB[i][j] + (ld) ((ld) sumaA[i][j] /(ld) (i+1)) << endl;*/
        }
    }

    /*cout << "ciagA:\n";
    for(ll i=1; i<=I; i++)
    {
        for(ll j=1; j<=n; j++)
        {
            cout << "{";
            for(ll v : ciagA[i][j]) cout << v << ",";
            cout << "} ";
        }
        cout << endl;
    }*/

    cout << fixed << setprecision(7) << odpowiedz;
}

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