Submission #937442

#	Time	Username	Problem	Language	Result	Execution time	Memory
937442		Marco_Escandon	Let's Win the Election (JOI22_ho_t3)	C++11	100 / 100	328 ms	2980 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 P[501]; 
void PSN(ll n,ll m) 
{ 
    for(int i=0; i<=n; i++) 
    { 
        priority_queue<double> q; 
        for(int j = i+1; j <=n; j++) q.push(cad[j].second); 
        while(q.size()>m-i) q.pop(); 
        while(!q.empty()) {P[i]+=q.top();q.pop();} 
        //cout<<P[i]<<" "; 
    } 
} 
double sol(ll l,ll n,ll m) 
{ 
    vector<vector<double>> dp(n+1,vector<double>(l+2,1e9)); 
    double bs=1e9; 
    dp[0][1]=0; 
    for(int i=1; i<=n; i++) 
    { 
        for(int j=1; j<=l; j++) 
        { 
            if(j!=1) 
                dp[i][j]=dp[i-1][j-1]+cad[i].first/(j-1); 
            dp[i][j]=min(dp[i][j],dp[i-1][j]+cad[i].second/(double)l); 
            if(j==l) 
            { 
                bs=min(bs,P[i]/l+dp[i][j]); 
            } 
                 
        } 
    } 
    return 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); 
    PSN(n,m); 
    double bs=1e9; 
    for (int i = 1; i <= m+1; i++) { 
        double f1=sol(i,n,m); 
        //cout<<f1<<"\n"; 
        bs=min(bs,f1); 
    } 
    cout<<min(bs,P[0]); 
}

Compilation message (stderr)

Main.cpp: In function 'void PSN(ll, ll)':
Main.cpp:16:23: warning: comparison of integer expressions of different signedness: 'std::priority_queue<double>::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   16 |         while(q.size()>m-i) q.pop();
      |               ~~~~~~~~^~~~

• 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