제출 #1238418

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1238418		vicvic	Let's Win the Election (JOI22_ho_t3)	C++20	100 / 100	413 ms	492 KiB

Main

#include <bits/stdc++.h>

using namespace std;
const int NMAX=500;
int n, k, indb[NMAX+5], inda[NMAX+5], rez=0, used[NMAX+5], ind[NMAX+5];
long double b[NMAX+5], a[NMAX+5];
int main ()
{
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n >> k;
    for (int i=0;i<n;i++)
        cin >> a[i] >> b[i], b[i]=b[i]==-1?1e9:b[i], ind[i]=i;
    sort (ind, ind+n, [] (int x, int y) {return b[x]<b[y];});
    long double ans=1e18;
    for (int c=0;c<=k;c++)
    {
        int r=k-c;
        vector <long double> dp (r+1, 1e18);
        dp[0]=0;
        for (int i=0;i<n;i++)
        {
            for (int j=r;j>=0;j--)
            {
                if (j!=r)
                    dp[j+1]=min (dp[j+1], dp[j]+1.0*a[ind[i]]/(c+1));
                int pz=i-j+1;
                if (pz>0 && pz<=c)
                    dp[j]+=1.0*b[ind[i]]/(pz);
            }
        }
        ans=min (ans, dp[r]);
    }
    cout << fixed << setprecision (20) << ans;
    return 0;
}

• 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