Submission #1235402

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235402		hamanp87	Let's Win the Election (JOI22_ho_t3)	C++17	100 / 100	633 ms	8400 KiB

Main

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using ld=long double;

//#pragma GCC optimize("03,unroll-loops")
//#pragma GCC target("avx2")
//#pragma GCC target("sse4")

#define all(v) v.begin(),v.end()
#define F first
#define S second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
//#define randi uniform_int_distribution<long long>
#define damoon(v) v.resize(unique(all(v))-v.begin())
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//randi dist(0,10000000000000000);

typedef pair<int,int> pii;
typedef pair<long long,long long> pll;
typedef pair<int,bool> pib;
typedef pair<long long,bool> plb;
typedef pair<int,pii> pip;
typedef pair<pii,int> ppi;
typedef vector<int> veci;
typedef vector<long long> vecl;
typedef vector<bool> vecb;
typedef vector<pll> vecp;
typedef set<int> seti;
typedef set<long long> setl;
typedef set<pii> setp;
typedef map<int,int> mapii;
typedef map<long long,long long> mapll;
typedef map<int,bool> mapib;
typedef map<long long,bool> maplb;

const int mod=1e9+7,neginf=-1e9,N=500;
const ll inf=2e18;
const double PI=acos(-1);
ll a[N+5],b[N+5],sum[N+5];
ld dp[2][N+5][N+5];

void solve()
{
    ll n,k;
    cin>>n>>k;
    vecp v(1);
    for(int i=1;i<=n;i++)
    {
        cin>>a[i]>>b[i];
        if(b[i]==-1)
            b[i]=inf;
        v.pub(pll(b[i],a[i]));
    }

    sort(all(v));

    for(int i=0;i<2;i++)
        for(int j=0;j<=n;j++)
            for(int l=0;l<=n;l++)
                dp[i][j][l]=inf;

    vecl krj;
    for(int i=n;i>=1;i--)
    {
        krj.pub(v[i].S);
        sort(all(krj));
        if(k-i+1<=(int)krj.size())
        {
            for(int kk=0;kk<k-i+1;kk++)
                sum[i]+=krj[kk];
        }
        else
        {
            sum[i]=inf;
        }
    }

    ld ans=inf;
    ans=min(ans,(ld)sum[1]);
    for(int i=0;i<=k;i++)
        dp[0][0][i]=0;
    for(int i=1;i<=k;i++)
    {
        for(int kk=0;kk<=i;kk++)
        {
            for(int l=0;l<=k;l++)
            {
                dp[i&1][kk][l]=inf;

                if(kk and v[i].F!=inf)
                    dp[i&1][kk][l]=min(dp[i&1][kk][l],dp[(i&1)^1][kk-1][l]+(1/(1.0*kk))*(1.0*v[i].F));
                dp[i&1][kk][l]=min(dp[i&1][kk][l],dp[(i&1)^1][kk][l]+(1/(1.0*(l+1)))*(1.0*v[i].S));
            }
        }

        for(int j=0;j<=i;j++)
            ans=min(ans,sum[i+1]*(1/(1.0*(j+1)))+dp[i&1][j][j]);
    }

    cout<<fixed<<setprecision(15)<<ans<<"\n";
}

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

    //ifstream fin("in.txt");
    //ofstream fout("out.txt");

    int t=1;
    //cin>>t;
    while(t--)
    {
        solve();
    }
}

• 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