Submission #937394

#	Time	Username	Problem	Language	Result	Execution time	Memory
937394		Marco_Escandon	Let's Win the Election (JOI22_ho_t3)	C++11	0 / 100	1341 ms	848 KiB

Main

#include<bits/stdc++.h>
#define optimizar_io ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);cout.setf(ios::fixed);cout.precision(15);
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
#define x first
#define y second
pair<double,double> cad[501];
double mapa[501];
double sol(ll l,ll n,ll m)
{
    if(mapa[l]!=0)
        return mapa[l];
    vector<vector<double>> dp(2,vector<double>(l+3,1e9));
    dp[0][1]=0;
    double bs=1e9;
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=l; j++)
        {
            double temp=1e9;
            temp=min(temp,dp[0][j]+cad[i].y/l);
            if(cad[i].first!=1e9&&j!=1)
                temp=min(temp,dp[0][j-1]+cad[i].x/(j-1));
            dp[1][j]=temp;
            if(j==l)
            {
                //cout<<i<<j<<":"<<temp<<" ";
                priority_queue<ll> q;
                double t2=0;
                for(int k=i+1; k<=n; k++)
                {
                    q.push(cad[k].second);
                    t2+=cad[k].second;
                    if(q.size()==m-i)
                    {
                        bs=min(bs,dp[1][j]+t2/l);
                        t2-=q.top();q.pop();
                    }
                }
            }
            //cout<<"\n";
        }
        swap(dp[0],dp[1]);
        //cout<<"\n\n";
    }
    return mapa[l]= bs;
}
int main()
{
    optimizar_io
    ll n,m;
    cin>>n>>m;
    cad[0]={-1,-1};
    for(int i=1; i<=n; i++)
    {
        cin>>cad[i].second>>cad[i].first;
        if(cad[i].x==-1)
            cad[i].x=1e9;
    }
    sort(cad,cad+n+1);
    double bs=1e9;
    for (int i = 1; i <= m+1; ++i) {
        double f1=sol(i,n,m);
        //cout<<f1<<"\n";
        bs=min(bs,f1);
    }
    /*double lo = 0, hi = m+1;
    for (int i = 0; i < 16; ++i) {
      double delta = (hi-lo)/3.0;
      double m1 = lo+delta;
      double m2 = hi-delta;
      double f1=sol(m1,n,m);
      double f2=sol(m2,n,m);
      bs=min(bs,f1);
      bs=min(bs,f2);
      (f1 > f2) ? lo = m1 : hi = m2;
    }*/
    cout<<bs;
}

Compilation message (stderr)

Main.cpp: In function 'double sol(ll, ll, ll)':
Main.cpp:35:32: warning: comparison of integer expressions of different signedness: 'std::priority_queue<long long int>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   35 |                     if(q.size()==m-i)
      |                        ~~~~~~~~^~~~~

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