Submission #753814

#	Time	Username	Problem	Language	Result	Execution time	Memory
753814		bgnbvnbv	Let's Win the Election (JOI22_ho_t3)	C++14	10 / 100	1544 ms	8268 KiB

Main

#include<bits/stdc++.h>
#define TASKNAME "codeforce"
#define pb push_back
#define pli pair<int,int>
#define fi first
#define se second
#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL);
using namespace std;
using ll=long long;
const ll maxN=2e5;
const ll inf=1e8;
const ll mod=1e9+7;

ll n,k;
struct qq
{
    ll a,b;
    bool operator<(const qq&o)
    {
        return b<o.b;
    }
}a[maxN];
using ld=long double;
ld dp[2][505][505];
void solve()
{
    cin >> n >> k;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i].a >> a[i].b;
        if(a[i].b==-1) a[i].b=1e14;
    }
    sort(a+1,a+n+1);
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<=k;j++) dp[0][i][j]=inf;
    }
    dp[0][0][0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=n;j++)
        {
            for(int q=0;q<=k;q++)
            {
                dp[i&1][j][q]=dp[(i-1)&1][j][q];
                //lay vote
                if(q>=1) dp[i&1][j][q]=min(dp[i&1][j][q],dp[(i-1)&1][j][q-1]+(ld)a[i].a/(j+1));
                //lay nguoi
                if(j>=1&&q>=1) dp[i&1][j][q]=min(dp[i&1][j][q],dp[(i-1)&1][j-1][q-1]+(ld)a[i].b/(j));
            }
        }
    }
    ld ans=inf;
    //cout << dp[1][1][1]<<'\n';
    for(int j=0;j<=n;j++)
    {
        ans=min(ans,dp[n&1][j][k]);
    }
    cout << fixed<< setprecision(5)<<ans;
}
int main()
{
    fastio
    //freopen(TASKNAME".INP","r",stdin);
    //freopen(TASKNAME".OUT","w",stdout);
    solve();
}

• 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